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

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

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

## Create an account

Register a new account

• ### Forum Statistics

• Total Topics
628710
• Total Posts
2984320

• 23
• 11
• 9
• 13
• 14