Jump to content
  • Advertisement
Sign in to follow this  
Rogalon

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.

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

Recommended Posts

Hi there, first - let me introduce myself. I'm from Heidelberg, Germany and not exactly what you'd call a game programmer. Well - anyway I'm into the physical realtime simulation business at my university so I basically have to deal with the same problems as "real" game programmers. So - in advance thanks for all the interesting topic I've seen in the last few weeks when I was just looking as a humble guest. Enough talk, time to participate... So lets start with my first question. To solve a rather complicated equation in my simulation (Real time calculation of the behaviour of wires in complex objects) I need to compute the exakt distance from specific points on the wire (lets call them joints) to the object wall. I also need the orientation (inside/outside of the object). The object consists of about 5.000 - 10.000 static triangles. What I've done so far is a precalculation of a transformation matrix for each triangle (p0,p1,p2) that rotates and translates the triangle into the x/z plane. (with p0 lying at the origin) A calculation of the distance from the point to the triangle is quite fast as it can be done in 2D - but... If I want the distance to the object I have to test against 10.000 triangles - for each joint. (And solving my equation needs about 5000 joint calculations. Nothing you can do about it.) I already constructed a n³ cellGrid around the object so I can point to the triangles that are next to the cell I'm in - but that's not fast engough. (Besides, if there are no triangles next to the cell the joint is located in I have to search the surrounding cells etc.) Is there some other, significally faster way to do it (Already though about using Octrees). Or does anyone of you have an idea how to do a fast wire simulation (well, would be much to ask - but if anyone has ideas - spit it out) The object iteslf is quite complex - intertwined tubes, holes etc. And I can be inside the object as well as outside. Thanks for your help, greetings Rogalon

Share this post


Link to post
Share on other sites
Advertisement
hi!

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.pdf

hope this helps

Share this post


Link to post
Share on other sites
Quote:
Original post by n0rmanfreak
hi!

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.pdf

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


Link to post
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 this post


Link to post
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 this post


Link to post
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 this post


Link to post
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 this post


Link to post
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 this post


Link to post
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 this post


Link to post
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.

about :
>> 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

Share this post


Link to post
Share on other sites
Sign in to follow this  

  • Advertisement
×

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!