resources for computing geodesic

March 4, 2015

There are many implementation for computing geodesic distance on triangle mesh. Some are approximate and some are exact.

1.Fast Marching method. This method is approximate and in practice the average error is below 1%. You can refer to Gabriel Peyre’s implementation of fast marching method in matlab.http://www.mathworks.com/matlabcentral/fileexchange/6110-toolbox-fast-marching

  1. MMP method proposed by [1] and implemented in [2]. This method is exact and the code is inhttps://code.google.com/p/geodesic/ . Same as the comment by Ante. A disadvantage is that when the mesh is larege, MMP method will consume a lot of memory, O(n^2), n is the number of vertices.
  2. CH method proposed in [3] and improved and implemented in [4]. This method is exact and consume less memory than MMP method. The code is inhttps://sites.google.com/site/xinshiqing/knowledge-share
  3. Heat method proposed in [5]. One implementation is in https://github.com/dgpdec/course This method is approximated and require a preprocessing process. It’s faster than Fast Marching method.

[1] Joseph S. B. Mitchell, David M. Mount, and Christos H. Papadimitriou. 1987. The discrete geodesic problem. SIAM J. Comput. 16, 4 (August 1987), 647-668.

[2] Vitaly Surazhsky, Tatiana Surazhsky, Danil Kirsanov, Steven Gortler, Hugues Hoppe. Fast exact and approximate geodesics on meshes. ACM Trans. Graphics (SIGGRAPH), 24(3), 2005.

[3] Chen, J. and Han, Y.1990. Shortest paths on a polyhedron. InSCG ’90: Proceedings of the sixth annual symposium on Computational geometry. ACM Press, New York, NY, USA, 360{369

[4] Shi-Qing Xin and Guo-Jin Wang. 2009. Improving Chen and Han’s algorithm on the discrete geodesic problem. ACM Trans. Graph. 28, 4, Article 104 (September 2009), 8 pages.

[5] Crane K, Weischedel C, Wardetzky M. Geodesics in heat: a new approach to computing distance based on heat flow[J]. ACM Transactions on Graphics (TOG), 2013, 32(5): 152.


Bounded Biharmonic Weights(BBW) point and bone weight

November 12, 2014

notable progress is achieved! today I finished the implementation of Bounded Biharmonic Wights both for point and bone handles. It is achieved by well setting the box bounded constrains [0,1] for handles.

A little more details are explained as follows:

for points, directly set [0,1] constrains as done stated in the paper Bounded Biharmonic Weights.

for bones, we then first compute a bone location as mid-point between two points (provided by users to indictae a bone), this implies that we have to ensure the virtual line connnecting these two points must lie inside the body. Actually, it is a drawback to use bones for skinning. Next, taking the bones as new handles and then to set the constriains as the same as done for points. In implenmentation, smartly, we only need to change the handle ID in the resulting weight matrix, only the parent point will be associated with weights of its corresponding bone.

points:

int N = getNumNodes();
int M = handles.getNumHandles();
// each voxel node will have weights
m_weights.clear();
m_weights.resize(N);

…compute BBW weights assembed into m_weights…

bones:

vector<int> bones;
vector<RowVector3> boneLocs;
for(int i=0;i<handles.getBones();i++)
{
map<int, int> bone = handles.getBone(i);
map<int,int>::iterator it = bone.begin();
bones.push_back(it->second);
RowVector3 cLoc = handles.getHandlePose(it->first);
RowVector3 pLoc = handles.getHandlePose(it->second);

…compute weights assembed into m_weights…

…change the handles ID in the resulting weight matrix…

vector<Weights> tmp_weights = m_weights;
tmp_weights.clear();tmp_weights.resize(N);
for(int j = 0;j<handles.getNumHandles();j++)
{
for(int i = 0 ; i < N ; i++)
{
tmp_weights[i].pushWeight(0.0);
}
}
for(int j = 0;j<M; j++)
{
for(int i = 0 ; i < N ; i++)
{
tmp_weights[i].setCoord(bones[j],m_weights[i].getCoord(j));
}
}
boneLocs.push_back((cLoc+pLoc)/2.0);
}
int N = getNumNodes();
int M = bones.size();

results on a simple cube (bending with 90 degrees), colors indicate weight map.
bw_1

pw_0

bw_5

bw_4

pw_2

pw_3


Deferred rendering and SSAO

June 9, 2014

Sketch:

limited by the modern graphics pipelines,  forward or deferred rendering is alternatively picked with your reason! generally speaking, we will prefer deferred version when have to handle many lights. Simply as in forward version, lighting calculations have to be performed on every vertex, fragment, light in the scene.

but in deferred rendering, first the graphics card projects and breaks your geometries into vertices and then to pixels, stored in the so-called G-buffer. Lighting  calculations are performed using the data (positions, normal, specular) in that buffer, producing the final image.

G-buffer

position, color (normally from texture), normal, specular intensity et.al. are all stored in this buffer. Obviously, limited materials is acceptable.  Just a hint, one solution is by deferred lighting, checking it in gpu gems. For a light, first do determine the screen ares which is influenced by it (using position, only the area closed to this light), and how lit it is (using normal, specular intensity, power) , so only the visible pixels are lighted. But also because of this feature,  it has downside of the inability of handling transparent objects.  What we can do is to incorporate the stencil buffer and multi-pass.

Rendering

using the data in G-buffer, we also want to produce more interesting effects. The normal wish list is (SSAO, fog, HDR,motion blur), and shadows with the usage of shadow maps.

Screen Space

screen space– pixel coordinates and a z-buffer value betwen 0 and 1.

closeup

humanhomer
cornellboxcolor
cornellboxnormal
normal
spanoza

 

Reference

[1]gpu gems 3
[2]johan’stutorial: http://www.john-chapman.net/content.php?id=13


visit Republic Polytechnic, Singapore

September 19, 2011

today, we spent half day in RP, Singapore. and have the chance to have a look at the sports training center there. we tested our STAR tracker system there. good, It’s my first time to see such equipment.


use doxygen

September 14, 2011

doxygen is a very useful tool, to generate documents by HTML or Latex output format from project. great tool to use today.


wishes guys all the best

August 29, 2011

last day with ADSC.

It’s quit a cherished time, work with these group guys.
From left to right, Viet Anh Nguyen, Dongbo Min, Humayun Khan, Yang Hongsheng, me, Johan Vu, Jiangbo Lu.

with all of you the best in the future. miss you:)


Face Recognition from Profiles

August 5, 2011

99′ paper:

 

Face Recognition from Profiles Using Morphological Signature Transform

 

Morphological Signature Transform represent shape of profile