Jump to content
• Advertisement

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

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

If you intended to correct an error in the post then please contact us.

## 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 this post

##### Share on other sites
Advertisement
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 this post

##### 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

#### Share this post

##### Share on other sites

• Advertisement
• Advertisement

• ### Popular Contributors

1. 1
2. 2
3. 3
4. 4
frob
13
5. 5
• Advertisement

• 16
• 13
• 20
• 12
• 19
• ### Forum Statistics

• Total Topics
632171
• Total Posts
3004555

×

## Important Information

By using GameDev.net, you agree to our community Guidelines, Terms of Use, and Privacy Policy.

We are the game development community.

Whether you are an indie, hobbyist, AAA developer, or just trying to learn, GameDev.net is the place for you to learn, share, and connect with the games industry. Learn more About Us or sign up!

Sign me up!