# Distance-to-surface gradient of a triangle mesh.

This topic is 4519 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

## Recommended Posts

I have a closed triangle mesh, and I imagine every point in the world has a distance value corresponding to the distance from that point to the surface, -'ve for outside and +'ve for inside, say (signed-distance transform, so I hear). For each vertex in the triangle mesh I want to compute the gradient of this distance 'field'. The naive way would be to discretize the space, compute the distance at every point, then use this discretization to find gradients - certainly that's what you would do for any other scalar field. But I figure, since this scalar field is just a load of distances, I should be able to calculate just using the vertex position and the position of the vertices around it. But thats about as far as I've got with this train of thought. Any suggestions on how I can use neighbouring vertex positions/distances to calculate this distance gradient much appreciated... Cheers,

##### Share on other sites
What do you peeps think of this algorithm to solve it? I think its right, but I'm making a few assumptions:

for (int i = 0; i < (int)getNeighbours().size()-1; i++){	for (int j = i+1; j < (int)getNeighbours().size(); j++){							FLOATTRIPLE vecMid = (getNeighbours()->getPos() + getNeighbours()[j]->getPos())*0.5;		FLOATTRIPLE vecDistMid = this->getPos() - vecMid;		FLOATTRIPLE vecDistNeigh = getNeighbours()->getPos() - getNeighbours()[j]->getPos();		FLOATTRIPLE vecVertNorm = vecDistMid * (1.0f/!vecDistMid);		FLOATTRIPLE vecGrad = vecVertNorm * (!vecDistNeigh/!vecDistMid);		vecGradSurf = vecGradSurf + vecGrad;	}}vecGradSurf = vecGradSurf*(1.0f/(int)getNeighbours().size());

Where +/- are vector operations, * is vector*scalar, ! is magnitude of a vector. This loop is called every time step for every vertex ('this'). Hopefully everthing else is fairly self-explanatory...

##### Share on other sites
The method you need is the Fast Marching Method.
It computes the (signed) distance function of all points in some grid to the surface.
It has a worst case complexity of O(N log N), where N is the number of grid points, and it's very fast. The guy who mainly did it is J. Sethian. (I hope Stanley Osher doesn't read this, but anyway...) There is a lot of interesting stuff on his homepage.

One publication I've found about it is this one. If you have problems with the implementation or if you want to have a sample code, please PM me.

Lutz

1. 1
Rutin
44
2. 2
3. 3
4. 4
5. 5

• 10
• 28
• 20
• 9
• 20
• ### Forum Statistics

• Total Topics
633409
• Total Posts
3011705
• ### Who's Online (See full list)

There are no registered users currently online

×