Sign in to follow this  

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

This topic is 4592 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
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
And that's all shape-shifting as well I guess, with deformable elastic geometry, not just static geometry...

Man you must have some pretty awful nightmares...

to get back to the original question, a fast point-triangle distance, ...


//-------------------------------------------------------------------
// Calculate the squared distance of a point to the triangle
//
// Nicked code from David Eberly's most excelent physics site
// (http://www.magic-software.com)
//-------------------------------------------------------------------
float TrianglePointDistanceSquared(const Vector* V, const Vector& P, float* s, float* t)
{
//-------------------------------------------------------------------
// 2 edges of the triangle
//-------------------------------------------------------------------
Vector E0 = V[1] - V[0];
Vector E1 = V[2] - V[0];

Vector kDiff = V[0] - P;
float fA00 = E0 * E0;
float fA01 = E0 * E1;
float fA11 = E1 * E1;
float fB0 = kDiff * E0;
float fB1 = kDiff * E1;
float fC = kDiff * kDiff;
float fDet = (float) fabs(fA00*fA11-fA01*fA01);
float fS = fA01*fB1-fA11*fB0;
float fT = fA01*fB0-fA00*fB1;
float fSqrDist;

if (fabs(fDet) < 0.00000001f)
return 100000000.0f;

if ( fS + fT <= fDet )
{
if ( fS < (float)0.0 )
{
if ( fT < (float)0.0 ) // region 4
{
if ( fB0 < (float)0.0 )
{
fT = (float)0.0;
if ( -fB0 >= fA00 )
{
fS = (float)1.0;
fSqrDist = fA00+((float)2.0)*fB0+fC;
}
else
{
fS = -fB0/fA00;
fSqrDist = fB0*fS+fC;
}
}
else
{
fS = (float)0.0;
if ( fB1 >= (float)0.0 )
{
fT = (float)0.0;
fSqrDist = fC;
}
else if ( -fB1 >= fA11 )
{
fT = (float)1.0;
fSqrDist = fA11+((float)2.0)*fB1+fC;
}
else
{
fT = -fB1/fA11;
fSqrDist = fB1*fT+fC;
}
}
}
else // region 3
{
fS = (float)0.0;
if ( fB1 >= (float)0.0 )
{
fT = (float)0.0;
fSqrDist = fC;
}
else if ( -fB1 >= fA11 )
{
fT = (float)1.0;
fSqrDist = fA11+((float)2.0)*fB1+fC;
}
else
{
fT = -fB1/fA11;
fSqrDist = fB1*fT+fC;
}
}
}
else if ( fT < (float)0.0 ) // region 5
{
fT = (float)0.0;
if ( fB0 >= (float)0.0 )
{
fS = (float)0.0;
fSqrDist = fC;
}
else if ( -fB0 >= fA00 )
{
fS = (float)1.0;
fSqrDist = fA00+((float)2.0)*fB0+fC;
}
else
{
fS = -fB0/fA00;
fSqrDist = fB0*fS+fC;
}
}
else // region 0
{
// minimum at interior point
float fInvDet = ((float)1.0)/fDet;
fS *= fInvDet;
fT *= fInvDet;
fSqrDist = fS*(fA00*fS+fA01*fT+((float)2.0)*fB0) +
fT*(fA01*fS+fA11*fT+((float)2.0)*fB1)+fC;
}
}
else
{
float fTmp0, fTmp1, fNumer, fDenom;

if ( fS < (float)0.0 ) // region 2
{
fTmp0 = fA01 + fB0;
fTmp1 = fA11 + fB1;
if ( fTmp1 > fTmp0 )
{
fNumer = fTmp1 - fTmp0;
fDenom = fA00-2.0f*fA01+fA11;
if ( fNumer >= fDenom )
{
fS = (float)1.0;
fT = (float)0.0;
fSqrDist = fA00+((float)2.0)*fB0+fC;
}
else
{
fS = fNumer/fDenom;
fT = (float)1.0 - fS;
fSqrDist = fS*(fA00*fS+fA01*fT+2.0f*fB0) +
fT*(fA01*fS+fA11*fT+((float)2.0)*fB1)+fC;
}
}
else
{
fS = (float)0.0;
if ( fTmp1 <= (float)0.0 )
{
fT = (float)1.0;
fSqrDist = fA11+((float)2.0)*fB1+fC;
}
else if ( fB1 >= (float)0.0 )
{
fT = (float)0.0;
fSqrDist = fC;
}
else
{
fT = -fB1/fA11;
fSqrDist = fB1*fT+fC;
}
}
}
else if ( fT < (float)0.0 ) // region 6
{
fTmp0 = fA01 + fB1;
fTmp1 = fA00 + fB0;
if ( fTmp1 > fTmp0 )
{
fNumer = fTmp1 - fTmp0;
fDenom = fA00-((float)2.0)*fA01+fA11;
if ( fNumer >= fDenom )
{
fT = (float)1.0;
fS = (float)0.0;
fSqrDist = fA11+((float)2.0)*fB1+fC;
}
else
{
fT = fNumer/fDenom;
fS = (float)1.0 - fT;
fSqrDist = fS*(fA00*fS+fA01*fT+((float)2.0)*fB0) +
fT*(fA01*fS+fA11*fT+((float)2.0)*fB1)+fC;
}
}
else
{
fT = (float)0.0;
if ( fTmp1 <= (float)0.0 )
{
fS = (float)1.0;
fSqrDist = fA00+((float)2.0)*fB0+fC;
}
else if ( fB0 >= (float)0.0 )
{
fS = (float)0.0;
fSqrDist = fC;
}
else
{
fS = -fB0/fA00;
fSqrDist = fB0*fS+fC;
}
}
}
else // region 1
{
fNumer = fA11 + fB1 - fA01 - fB0;
if ( fNumer <= (float)0.0 )
{
fS = (float)0.0;
fT = (float)1.0;
fSqrDist = fA11+((float)2.0)*fB1+fC;
}
else
{
fDenom = fA00-2.0f*fA01+fA11;
if ( fNumer >= fDenom )
{
fS = (float)1.0;
fT = (float)0.0;
fSqrDist = fA00+((float)2.0)*fB0+fC;
}
else
{
fS = fNumer/fDenom;
fT = (float)1.0 - fS;
fSqrDist = fS*(fA00*fS+fA01*fT+((float)2.0)*fB0) +
fT*(fA01*fS+fA11*fT+((float)2.0)*fB1)+fC;
}
}
}
}

if ( s ) *s = fS;
if ( t ) *t = fT;

return fabs(fSqrDist);
}




as another suggestion, a Solid BSP tree?

Oh, and I've used the code above for sphere-triangle collisions, and it runs at decent framerates on its own for a huge amount of tris (5,000 would be ok). That can also be speed up by using octrees and what not, if you have some distance threshold.

Say, you are only interested about the distance when the distance breaks a small threshold barrier (say 2 cms). Then you just have to make some sort of tree, and do a sphere-AABBtree test to cull triangles closer than 2 cm from the point. That would be very fast, as you'll end up with a handful of tris (hopefully).

here is an example. It has a tree so faster than raw triangles, but could be a lot faster if optimised properly (tree structure is pretty dumb).

http://uk.geocities.com/olivier_rebellion/simple_collision.zip

if you need the disatnce at all time, that will be tricky without using convexities.

Share this post


Link to post
Share on other sites
Don't know if this is your case, but if you have 5000 triangles you are creating and transforming 5000 matrices... why dont you just 'backtransform' your point to a position relative to your untransformed triangles and compute all as an identity (that is... your original tris). Maybe that helps a little.

Luck!
Guimo

Share this post


Link to post
Share on other sites
That's basically the same test I use for triangle point distance so I guess I won't be able to improve here... (I even precalculated transformation matrices that rotate, scale and shear my initial triangle so it's in a plane at (0,0,0) (1,0,0) (0,1,0) - makes things even easier (at least if you don't need exact distances).

But that's another story - as I already said I need pretty exact distances and so I stuck with the standardized triangle that's been rotated in the x/y plane for calculations.

Thanks anyway for posting your algorithm. And... you were right about those nightmares you know. - The ones where wires become poisonous snakes that haunt me ;-) (And yeah - I thought about actually using snakes for the simulation but stuck to a spline that's approximatly fitted through the joints...)

The Frauenhofer project is a little bit far off from the things I'm doing (as far as I could see they don't even have a realtime constraint.)

Thanks for all your help - Bye, Rogalon

Share this post


Link to post
Share on other sites

This topic is 4592 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.

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now

Sign in to follow this