# Calculating exact distance from a point to a static object (Fast)

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

## Recommended Posts

##### Share on other sites
hi!

seems like the best choice to me. basically precalc the distance for some points and save it...at runtime just check the distancefield for the current distance.

take a look at this:
http://www.graphicon.ru/2003/Proceedings/Technical/paper495.pdf

hope this helps

##### Share on other sites
Quote:
 Original post by n0rmanfreakhi!if your collisionobject it totally static...how about distancefields ? seems like the best choice to me. basically precalc the distance for some points and save it...at runtime just check the distancefield for the current distance.take a look at this:http://www.graphicon.ru/2003/Proceedings/Technical/paper495.pdfhope this helps

Thank you. Basically that's what I'm doing right now (the n³ cellgrid - in fact without knowing that the technique is called Distance fields ;) ). Gonna look at the paper anyway - maybe I'll find some good suggestions in there.

Any more suggestions are welcome.

##### Share on other sites
hi!

okay...sorry...so i misread your post...i thought your cells where just pointing to a triangle. and you then use this triangle to calculate the actual distance...in the distancefield you directly store the distance to the object

good luck

##### Share on other sites
Yeah - actually it was me who misread your post ;-) After looking at the paper I noticed that they're indeed using what I'd call a discrete distance approximation field. Thanks for pointing me in that direction.

It's a little bit harder for me to calculate the actual field (because I have to know the exact distance even when I'm far away from the object - they only establish the field in a very limited area around the triangles) but that doesn't matter because I'm only dealing with one rigid object - so there's plenty of time for (slow) precalculations.

I also need exact distances and (more important) facings (in or outside). That's where the paper is cheating to get a little timeboost.

Anyway - what I'm using now is a discrete 128³ field in which I trilinear interpolate inbetween values. Seems to be working quite well - maybe I'll switch to spline interpolation if I really need more quality. But as of know trilinear seems to be the way to go.

Thanks again, Rogalon

##### Share on other sites
If I don't misunderstand your question, you have to find the nearest triangle for a given joint. What you can do is not computing the actual distance, but the squared distance (i.e. you don't extract the square root from the distance formula) and compare them. When you found the neares one, you take the square root only on that one.
This would avoid thousand of sqrt but I don't know if this is enaugh for you.
If the mesh is convex and has normals on it, then perhaps you can use the fact that triangle on the back side are always farer than those on the front side.

##### Share on other sites
Thank you - but square roots are the least of my problems ;-) In my first version I already pointed to a few (eg < 20) triangles per cell - and as I need the squared distances for energy calculations I never took squareroots. Still - this is too slow with the given task of minimizing a highly complex numerical function w/o derivatives.;)

Thank you anyway, Rogalon

##### Share on other sites
is the shape convex or concave?

Is it for a moving point? If so, the initial test might be slow, but using time coherence, the folloing frames should be much faster, since you have an approximate distance from the previous frame.

##### Share on other sites
The shape is highly concave (in fact it is the (static) model of the human heart with vessels, chambers - you can guess the complexity when computing the movement of a wire inside the object...).

You're suggesting some sort of cache mechanism? Already though about this. As far as I can see the distance field seems the way to go. A trilinear interpolation can be done quite fast and I don't worry about time consuming precalculations as long as I can save the results to hd ;-)

But thank you anyway - and if anyone hears about efficient ways to compute a moving wire inside a complex object (not just tubes and spheres) - let me know ;-)

Greetings, Rogalon

##### Share on other sites
hi!

well the distancefield normally stores a signed distance so you can detect if you're inside or outside... i didn't read the paper for a long time..so i'm not sure what you're talking about...if you say they're cheating..their modell might be little easier to detect inside and outside but as you pointed out precalculations aren't timerelevent ;)

so good luck for your project.

>> and if anyone hears about efficient ways to compute a moving wire inside a complex object (not just tubes and spheres) - let me know ;-) <<

i remember a project at the igd (part of fraunhofer) which simulated the process of applying wires and tubes inside a car.. i don't remember the name right now...but i'll post it as soon as i remember ;)

here's a link to the project discreption..not sure if it's really what you need:

http://www.igd.fhg.de/igd-a2/projects/DMUCabling/index.html

1. 1
2. 2
3. 3
Rutin
18
4. 4
5. 5

• 13
• 14
• 9
• 9
• 9
• ### Forum Statistics

• Total Topics
632925
• Total Posts
3009238
• ### Who's Online (See full list)

There are no registered users currently online

×