# Moving sphere against triangle collision

## Recommended Posts

See my last post to see where this is all coming from. I invented my own algorithm for this, hehe. All testing so far looks like it works flawlessly. Still, I would like to know if anyone can see and point out any potential problems with it. First, the function's purpose is to report a collision when a sphere moves into or through a triangle. It will also fail to report a collision if the sphere's original position is intersecting a triangle before it moves, but this should never happen [smile] This is how it works. Keep in mind that this is totally unoptimized testing code. Also written more for readablity than efficiency.
// va, vb, and vc are the vertices of the triangle, while "normal" is it's normal.
BOOL MovingSphereTriangleCol(const VEC &pos_old, const VEC &pos_new, FLOAT radius, const VEC &va, const VEC &vb, const VEC &vc, const VEC &normal)
{
// Create a ray (later on, this can be done outside of this method and the ray passed to it. Since all triangles will use the same ray)
VEC ray_pos = pos_old;
VEC ray_dir = normalized( pos_new - pos_old );
FLOAT ray_length = length( pos_new - pos_old );

// Intersect this ray with the triangle plane,
// but push the plane out by the radius of the sphere
// FLOAT IntersectPlane(const VEC &any_plane_pos, const VEC &plane_normal, const VEC &ray_pos, const VEC &ray_dir)
FLOAT distance_to_pushed_plane = IntersectPlane( va + (normal * radius), normal, ray_pos, ray_dir );

// If the distance negative, we are moving the other direction
// Note I have not coded the condition where the ray is parallel to the plane yet
if( distance_to_pushed_plane < 0.0f )
return FALSE;

// If we didn't hit the pushed plane, we can't hit the triangle
if( distance_to_pushed_plane > ray_length )
return FALSE;

// Push this intersect point back to the real plane of the triangle
VEC pushed_hit = ray_pos + (ray_dir * distance_to_pushed_plane);
VEC tri_plane_hit = pushed_hit + ( normal * -radius );

// See where this point is relative to the triangle
// KVal_TriEdge GetTriangleEdgeThatPointIsOutsideOf(const VEC &va, const VEC &vb, const VEC &vc, const VEC &point)
KVal_TriEdge tri_edge = GetTriangleEdgeThatPointIsOutsideOf( va, vb, vc, tri_plane_hit );

// If inside the triangle, it definitely collided on the triangle face
if(tri_edge == TRI_EDGE_INSIDE)
return TRUE;

// Get the closest point on the triangle (edge) to the plane intersect point
VEC closest;
switch( tri_edge )
{
//   GetClosestPointOnLineToPoint(VEC *closest, const VEC &line_a, const VEC &line_b, const VEC &point)
case TRI_EDGE_AB: GetClosestPointOnLineToPoint( &closest, va, vb, tri_plane_hit ); break;
case TRI_EDGE_BC: GetClosestPointOnLineToPoint( &closest, vb, vc, tri_plane_hit ); break;
case TRI_EDGE_CA: GetClosestPointOnLineToPoint( &closest, vc, va, tri_plane_hit ); break;
}

// Do an intersect with a sphere on this edge location
// Note that by "capsule" below, I'm meaning the connection of the two sphere locations by a cylinder
// FLOAT IntersectSphere(const VEC &sphere_pos, FLOAT sphere_radius, const VEC &ray_pos, const VEC &ray_dir)
FLOAT dist_to_edge_from_capsule = IntersectSphere( closest, radius, ray_pos, ray_dir );

return dist_to_edge_from_capsule >= 0.0f && dist_to_edge_from_capsule < ray_length;
}


edit: fixed a terrible typo on the last line What do you think? Too much math for a simple job? [smile] Please let me know if anyone can spot any danger or holes in this routine. Also let me know if something in the function doesn't make sense. I changed it around a lot to make it more friendly. I may have some variable names that are not matching [wink] Thanks for any suggestions [Edited by - Jiia on November 11, 2004 7:36:34 PM]

##### Share on other sites
Have you put this through some tests? Such as carrying out the collision and drawing the results, including contact points and normals?

Just looking over your code, there are a couple of things that don't look quite right to me. I hesitate to say anything though, because I could easily be wrong. But if you were to test it and find that it failed in certain cases, I have some ideas about where the problems might be...

One consideration is that the sphere can be 'behind' two edges, in which case it can potentially collide with either of them. But maybe you're handling that case...

Anyway, blah blah blah. The real question is, does it work? And does it work under all conditions (that you can devise tests for anyway)?

##### Share on other sites
This Article by Paul Nettle does basically the same thing and there is a well known issue with it...

When I tried to implement Nettle's code I ran into this problem:
the closest point on the triangle to the collision point of the plane is not necessarily going to be the point where the sphere collides...

I have absolutely no idea why this is... it seems counterintuitive to me... but I recorded actual instances where the triangle and the sphere are clearly colliding, but not at the closest point on the edge... so my code didn't notice it...

As far as I know, the only real way to accurately do this is to test a "sweeping sphere" against the triangle using quadratic equations... Kaspar Fauerby has a good explanation of this in his article but I can't seem to find it at the moment...

##### Share on other sites
It's hard to explain the closest-point thing without pictures, but just because a sphere happens to hit the *plane* of the triangle at point X doesn't mean that point Y, where it actually hits the triangle, will be the closest point on the triangle to point X.

You are correct about using quadratics - I know of no working implementation that solves the problem geometrically (that doesn't mean there isn't one, though, and I'd certainly be interested if there were).

Get ahold of Kasper Fauerby's paper if you can. I have it but I'm not sure if it's appropriate to just pass it around (?). It contains the equations for sweeping a sphere against a point (commonly available) and against a line segment (a little harder to find).

##### Share on other sites
Actually, this method is not using the triangle's plane intersect point to find the closest edge point. It intersects the plane after it has been pushed out by radius. It then pushes that intersect point back to the real plane and uses that to find the closest edge point. If a sphere hits the triangle, it's ray will always hit on this plane area, unless it hits an edge (hits the side of the triangle, rather than it's face, passing through its plane to do so).

It seems to work perfectly, except when the ray origin starts behind the plane + (normal * radius). This only happens if the sphere is moving mostly parallel to the triangle, and hits it's edge. Like if you didn't lift your foot high enough on a step, it bumps into the corner. Here it is failing, but only on the triangles that would be facing up. The tris facing your foot would still stop ya.

In any rate, the problem lies where I'm trying to place a sphere where the ray will most likely intersect it, but on an edge. This sphere location is slightly off when the ray is at extreme angles to the triangle plane. It is rare, but unacceptable. I think I'm going to be forced to find the closest point on the missed edge to a line, rather than point. I know this will fix all of the problems.

Another potential fix may be to pull the ray origin back farther until it is outside of this pushed plane. I think I'll try this first [smile]

Here is a picture of what I'm saying. If half of the sphere (half sphere = full radius) is as thick as this pushed plane, where can the sphere ray hit the pushed plane that the sphere would not hit on the real plane?

[Edited by - Jiia on November 11, 2004 8:53:52 PM]

##### Share on other sites
Quote:
 Original post by JiiaActually, this method is not using the triangle's plane intersect point to find the closest edge point. It intersects the plane after it has been pushed out by radius. It then pushes that intersect point back to the real plane and uses that to find the closest edge point. If a sphere hits the triangle, it's ray will always hit on this plane area, unless it hits an edge (hits the side of the triangle, rather than it's face, passing through its plane to do so).

Hello again...

I don't want you to feel like I'm putting you down... I think you're doing some really creative thinking here... stuff that I would never have been able to come up with on my own...

But I still think that if you read Nettle's paper you'll find that you are doing almost exactly the same thing... the only difference is that you're pushing the plane out by the sphere's radius and Nettle pushes the ray over by the sphere's radius... and if you think about it, that gives you the same result...

Thus I would imagine (obviously I'm not sure and could be wrong) that the same flaws in his algorithm will pop up in yours...

Trust me, I did not want to believe that I had to use quadratics... I tried all kinds of different methods for picking the point on the triangle that I would test against the sphere... to no avail

With all that said, I have not actually tried your code yet and it is possible that you have fixed the Nettle algorithm... I know there are other people on GDNet who are more proficient at collision detection than I and I'm hoping that they will notice this thread...

by the way, if you are interested, I found Kasper Fauerby's paper: collision.pdf

##### Share on other sites
Quote:
 Original post by TempusElfI don't want you to feel like I'm putting you down... I think you're doing some really creative thinking here... stuff that I would never have been able to come up with on my own...But I still think that if you read Nettle's paper you'll find that you are doing almost exactly the same thing... the only difference is that you're pushing the plane out by the sphere's radius and Nettle pushes the ray over by the sphere's radius... and if you think about it, that gives you the same result...

I don't think there is a way to move the ray after intersection that would have the same effect as intersecting the plane pushed out, is there? Well, unless you did some kind of crazy angle calculation and multiplied that with radius.

Okay, this much I'm almost positive of. Let me know if you can think of a situation where this is not true. If the sphere starts outside of the pushed plane, and the intersecting ray from the start position to the new position intersects the pushed plane, that ray location is exactly where the sphere will hit the triangle along it's movement path. I'm not saying the ray is telling us where on the triangle it hits, I'm saying the ray tells us how far the sphere moved before it intersected the triangle.

The problem I'm having is when the start position starts inside of the pushed plane. This happens when the sphere is moving almost parallel to it. I don't see any other problems so far.

Now it's time to admit that I totally suck at math [lol] My facts = weak theories. But I'm working on it. That's why I'm playing with this stuff. Okay, that's a lie. I just want to have invincible collision for my game. But the math boost is a good thing [wink]

##### Share on other sites
Arg... If I had web hosting I could draw a picture that would show you what I mean... This image from Nettle's article will have to suffice

B is the velocity of the object... it has been moved over by the purple ray which represents the opposite of the plane's normal

OK

now on top of this same image imagine your algorithm (I'm trying to show you that I think you come up with the same result)

you would, instead of moving B, leave it's origin at the center of the sphere and collide it against your pushed plane... you would then project that collision point back onto the original plane, and if I understand your algorithm correctly, you would end up with the exact same point that Nettle has circled here

I know you're not saying that the point is where the sphere collides, but neither is Nettle... that's what I'm trying to tell you... the two algorithms are very similar... so similar that I believe they are nearly the same.. and if you search the forums for his name you'll find that many people have discovered the subtle flaw

##### Share on other sites
Image Shack will let you upload unlimited images that stay on the net until they've not be viewed for a year [smile]

I'm extremely curious to know what this flaw is. I'll look around and see if I can figure it out.

Also, when the ray does not intersect the inside of the triangle, I place a sphere on the closest edge and do another intersect there. This doesn't fix the flaw? Also, I have yet to figure out HOW to place the sphere in exactly the right place on the edges yet. Doing an intersect with a capsule (cylinder on edge, spheres on vertices) on the missed edge, or even all edges would surely be perfect. Or, even if I can find the closest point on a line to another line, the idea is the same. Placing the sphere there should definitely work.

##### Share on other sites
When I was trying to implement Nettle, the problem I kept having was that when I determined that the sphere does not hit the triangle head on (meaning in the middle of the triangle), but it may hit the triangle on the edge, the point on the edge of the triangle that I picked to test against would sometimes not be the point where the sphere actually hits...

I tried many different methods of selecting this point and none worked...

However, I never tried to find the closest point on the edge to a line, the way you described in your other post

After reading your other post and thinking about it some more, I wonder if maybe selecting the closest point on the edge to the path of the sphere would resolve the problems I had...

I wish I had more time this week to test out your idea on my old project

by the way... do I understand what you were saying correctly?: It looks like in the original code you posted you were using the plane intersection point to find the closest point on the triangle, but then in other posts you talked about modifying this so that it picks the point based on the object's path... is that correct?

##### Share on other sites
Quote:
 Original post by TempusElfby the way... do I understand what you were saying correctly?: It looks like in the original code you posted you were using the plane intersection point to find the closest point on the triangle, but then in other posts you talked about modifying this so that it picks the point based on the object's path... is that correct?

The only situation where this routine fails is finding the triangle edge point closest to where the sphere should hit. If you can find that point, doing a sphere-intersect with the sphere ray and that point will tell you if there is a collision or not. It also tells you exactly where on the triangle that the sphere hits.

So you have your sphere ray, which is the ray from start position to new position. Once you know this ray misses the triangle's face, you use that ray to find the closest point on one of the edges to it. Now place an imaginary sphere on this edge-closest-point. Do a sphere intersect between the moving-sphere-ray and the imaginary sphere. If it hits, then the moving sphere hit the triangle edge at that closest point.

My problem is finding the closest point. I can't seem to find any information about finding the closest point on one line to another line on the web. Is it easy?

Here is my visual guess to this idea. If you line_a.cross( line_b ), you get a normal which represents the shared plane of the two lines. If you were to look at these two lines so that the shared normal is facing straight up (so looking down at the lines), the closest point on either line is where they visually cross, or where they would cross. If the segments do not actually cross, it is the end point closest to where they would cross if they were longer.

Is this right? Anyone have an idea on how to go about finding this point in space?

edit2: Most of what Sneftel suggests in that reply is not needed to find the closest point on only one of the lines. If you use one of the points from the line you are most concerned with (the edge) as the arbitrary point, then that line will already be resting on the plane. So you only need to project the other line to the plane, do the line-line intersect, and you're done. The intersect point will be what we need. The intersect would be most useful if it was performed with infinite lines. It won't be useful if the function fails when the lines do not overlap.

[Edited by - Jiia on November 12, 2004 2:35:28 AM]

##### Share on other sites
It works [grin]

I have a lot of optimizing to do, but it is definitely working. I've tested it at every imaginable angle. I also did an extreme test with it. I bounced 300 spheres around in a complex shaped mesh with time per frame ranging from 5 to 1000 milliseconds. If a sphere came out of the mesh, it would fly far into outer-space, and I had a box bound check to let me know if that happened.

I wanted to further the test by checking to make sure the spheres never pushed through any part of a triangle, but I couldn't think of an effortless way to do this, hehe.

I started drawing a little point mesh where the sphere collides with a triangle (contact point), and the point moves smoothly between the plane hit point and edge hit point. So when the sphere hits the triangle face, then hits an edge after moving left, the contact point simply moved left [smile]

The only time the method now fails is if the sphere hits the triangle from behind, or if the sphere was already colliding with the triangle before it ever moved.

[grin][grin][grin]
Thanks for all of the help

##### Share on other sites

I know that many people have given up on methods like this one in favor of sweeping spheres and lots of quadratic equations... but I think you may have resolved the problem that many people had...

##### Share on other sites
Quote:
 Original post by JiiaSee my last post to see where this is all coming from.I invented my own algorithm for this, hehe.

Be sure there can't be anything new on such a simple geometric issue, except implementation details but since you claimed that it's not optimized, there is no new implementation detail. [smile]

Quote:

There is nothing original in accounting the radius, since it's a parameter. It's simply more efficient to do it with a single addition (instead of adding a scaled normal) once you have computed the sphere center to plane distance. Talking about optimizations. [smile]

Quote:
 All testing so far looks like it works flawlessly....What do you think?...Too much math for a simple job?

Not enough tests : edges. It's flawed, you'll miss collisions : the sphere/edge collision cases, that necessarilly happen after the infinite support plane is traversed. since your algo stops when the sphere hits the support plane (<=> center hits the pushed plane, cf the sub radius to distance optimization)... it's flawed.

Please don't feel anything personnal, I don't want to bash you, it's the code. OK [smile]. Geometry algos are one of my specialties. And collision detection/prediction has been discussed a lot earlier at GameDev. Try the Google engine of Gamedev. Else I'll try to reedit and post a link to other more complete threads talking of collision prediction.

Meanwhile : learn about the Voronoi partition around a convex, the separating planes theorem. Once you'll master this, you'll never have any flaws in your algos, and they will all look very obvious to you.

You have 7 cases to compute the contact in the end. Necessarilly :

3 sphere/point.
3 sphere/edge.
1 sphere/plane.

And to know in which case you are you necessarilly have to know in which of the 7 (or 8 if you distinguish the up and down sides) sub spaces you are. These subspaces are bounded by 9 (or 10) planes (with 7 different normals). Still you can write any working code and maybe not see the underlying meaning of the equations, but you necessarilly have to do the tests corresponding to the planes of the Voronoi space partition.

Up view, see the 7 convex subspaces and their 9 boundaries (add the triangle plane and make them resp. 8 and 10) :   .   . 7 . 2 . 3. .*---*.   |1 /    . 6 | /   |/ 4. .*.  5    .

Still you were not so far from the optimal algo. I can give it to you later if I don't see anything already in GameDev.

The main principle for all col det algos is early rejection, that is make the fastest and most probable tests in a conservative order.

Now, think of your first ten lines, and you'll probably anticipate what I'll write.

##### Share on other sites
Quote:
Original post by Charles B
Quote:
 Original post by JiiaSee my last post to see where this is all coming from.I invented my own algorithm for this, hehe.

Be sure there can't be anything new on such a simple geometric issue, except implementation details but since you claimed that it's not optimized, there is no new implementation detail. [smile]

I'm sorry, did I say I made something new? I wasn't trying to make something new. I just wanted something that is simple and works [grin]

Quote:
 Original post by Charles BThere is nothing original in accounting the radius, since it's a parameter. It's simply more efficient to do it with a single addition (instead of adding a scaled normal) once you have computed the sphere center to plane distance. Talking about optimizations. [smile]

Honestly, seriously, I'm not trying to be original. As for the addition thing without scaling the normal, I have no idea what you're talking about [smile] The distance to the plane is a float value. How can I add that distance without using the normal?

Quote:
 You have 7 cases to compute the contact in the end. Necessarilly :3 sphere/point.3 sphere/edge.1 sphere/plane.

That is too many checks, it's flawed [grin]
You don't need to check the vertices. They are part of the edges. And you only need to check a single edge, and only if you miss the flat part of the triangle. So change that to 1 sphere/plane, then possibly 1 sphere/edge.

Quote:
 And to know in which case you are you necessarilly have to know in which of the 7 (or 8 if you distinguish the up and down sides) sub spaces you are. These subspaces are bounded by 9 (or 10) planes (with 7 different normals). Still you can write any working code and maybe not see the underlying meaning of the equations, but you necessarilly have to do the tests corresponding to the planes of the Voronoi space partition.

Huh? I must still be asleep. Most of that is unnecessary. Simply intersect the pushed plane. If the real-plane point is inside the tri, you're done. If not, find the closest point on the lapped over edge (only check 1 edge) which is radius distance from the ray. That's it. Mission accomplished.

I've done extensive tests on this system, and there is no flaw:

Sorry about the size of those. Note that the lines drawn in those images are not something I added later. They were drawn by the engine. So I'm not guessing where it will hit. That is where it hits. Also note that the second image is showing the sphere hit a vertex. But I'm not checking a vertex. I'm checking the edge we missed.

edit: If the images don't look right, the z-buffer was disabled when drawing the spheres + lines. I should have mentioned that [smile]

Quote:
 The main principle for all col det algos is early rejection, that is make the fastest and most probable tests in a conservative order.

The code I posted was simply an idea. Something I wasn't sure would work. It isn't meant to be fast. I thought I made that clear? [smile]

[Edited by - Jiia on November 16, 2004 2:47:34 AM]

##### Share on other sites
Quote:
 Original post by JiiaI'm sorry, did I say I made something new ?

You said "my own algorithm". Nevermind I respect people who dare to try their own way, even reinvent the wheel or make errors. It's what I also do. In the end you earn a deeper understanding when you read papers after you tried your own way. Still you said "my own algorithm". I suppose you understand that it can be perceived in two ways : my own (unique thus new), my own (effort).

Quote:
 As for the addition thing without scaling the normal, I have no idea what you're talking about [smile] The distance to the plane is a float value. How can I add that distance without using the normal ?

Well for the future, and I will show it for all your next questions, just be sure I never write pointless stuff on these subjects. I know perfectly what I mean, not because I am any kind of genius, but because 3D geometry is as simple as basic calculus and addition tables to me, and I thus consider it should be the case for any 3D coder at GameDev. That's what I intend with this short digression.

So next if I have been unclear, at least try to see what I meant by writing calculations or drawing a scheme on paper. See how you could have done :

// used more condensed names for simplicity. More mathematical.
d = PlaneDist( A + (N * r), N, Pos, Dir );

develops to :
Pos*N - N*A - r*N*N

Now tell me : what's the value of N*N since it's a normal ?
Which operator adds (subs) one dimensional variables : the vector::operator+ or the standard float::operator + ?

1 - the ray direction does not count. Why transmit a non parameter ?
2 - you basically compute a distance from a point to a plane. So just call it PlaneDist. Else you just add confusion to your code.

I know you'll possibly feel a bit idiot or ashamed for one second now. But don't worry, I could also fail to see the obvious when I started 3D .... ten years ago. See how many lines I had to spend to correct you from Alpha to Omega. [grin][grin]

Quote:

Quote:
 You have 7 cases to compute the contact in the end. Necessarilly :3 sphere/point.3 sphere/edge.1 sphere/plane.

That is too many checks, it's flawed [grin]

Well don't try this way when you are not confident. Once again I don't spend time to write pointless stuff. Spare my time please. My it's flawed remark was justified, yours is just playground jerks. I have 10 years of professional 3D coding in physics, software and hardware 3D rendering, wrote Quake like soft technologies (better on some aspects, worse on others) before Quake 1 and I have followed one of the hardest formations in math during 5 years (still I forgot 95% of it). OK ? OK you were trying to be fun. Never mind, nothing personnal. Just practical, don't waste our time (our is your, my and others) next.

Quote:
 You don't need to check the vertices. They are part of the edges. And you only need to check a single edge, and only if you miss the flat part of the triangle. So change that to 1 sphere/plane, then possibly 1 sphere/edge.

This shows you still have not understood the problem of polygonal collision detection. You had false intuitions. You just autosuggested wrong things by playing on words and not seeing things (visually). Yes a vertex belongs to two edges, but where is the logical linke next ? Did you read about the pointers I mentionned ? Voronoi and separating planes theorem ?

You should first deal with the static algorithm (collision detection) before trying to write an algo for the dynamic case (collision prediction). I hope this will open your eyes to your mistake :

A vert - vert distance is of the form x*x + y*y + z*z (in the appropriate orthonormal base). An equidistance surface is a sphere.
A vert - edge distance is of the form x*x + y*y on the appropriate 2D orthonormal base. An equidistance surface is a cylinder.
A vert - face distance is of the form x*x on the appropriate 1D orthonormal base (plane normal axis). An equidistance surface is a plane.

These are obviously uncompatible formulas. You necessarilly have several tests or return points in your computations, and the three main cases, one for each d-facet (vert, edge, face). Let's try to show it even more clearly with the Voronoi scheme of my last post.

You sphere center is in the convex subspace #7, you necessarilly have to end up with a result expressed as a 3D distance (point-point) of the form x*x+y*y+z*z in the appropriate axes.

This can be done after a few tests (3-6). It's very comparable to what you do in GetTriangleEdgeThatPointIsOutsideOf, except your function does not deal with enough cases to have a valid algo.

You sphere center is in the convex subspace #6, you necessarilly have the end up with a result expressed as a 2D distance of the form x*x+y*y in the appropriate axes.

...

Now once you get the min distance(point, polyhedron) algo right, you'll be able to understand the exact collision prediction algo.

Quote:
 Most of that is unnecessary.

NO. I hope you realized why now.

Quote:
 Simply intersect the pushed plane.

You have the freedom to choose whatever order of test you feel the most convenient. Cf "early rejection". This step is effectively the most favorable first step, that's common sense. It rejects more than 50% of the cases very quickly.

Quote:
 If the real-plane point is inside the tri, you're done.

Exact in the static case ONLY. You need to have three more plane distance evaluations to conclude that, total : 4 tests and you get an early rejection/contact conclusion. You can consider negative dist. <=> interior half space. Imagine edge perp normals (also perp to the plane normal) pointing outside.

But you forget that the sphere can come from below, hit an edge first and then be in this situation (inside #1) once it lays on the "pushed plane". Think of using this routine for any general mesh. As it is you algo will return a swept-sphere vs face contact, and miss the earlier swept-sphere vs edge contact. (or vert contact).

Quote:
 If not, find the closest point on the lapped over edge (only check 1 edge) which is radius distance from the ray. That's it. Mission accomplished.

FALSE.
- vert/edge you forget vert/vert (cf sphere in #7).
- your swept sphere can cross up to 5 Voronoi cells between the start and end positions. So reach the pushed plane as you did and next, track the evolution of the center in the Voronoi graph till you can conclude.
- for all these reasons, this closest point tells you nothing useful.

Quote:
 It isn't meant to be fast. I thought I made that clear ? [smile]

A good algo is always fast. Also implementations details can also be coded the first time if you are less lazy with your neurons and than you are lazy with your fingers. Thinking a bit more does not cost much. Coding wrong algos, buggy, and thus making unnecessary tests and debugging sessions costs infinitely more. Still I can understand the educational value of erratic coding behaviours, as a hobby. But else, read this :

I have been developping a physics engine based on a generic kernel for a commercial game. It worked with a col. det. implemented by another guy in a so called R&D. The guy obviously did not master the subject at all. He had never heard of the separating axes theorem, never read about Voronoi, never realized how much flawed his algos were. I knew this all by heart for years, and I had to use this crappy library, "a black box" they said (crap Taylorist organization), and deal with bugs such as objects traversing the map near the edges or vertices !. In the end I finally convinced the staff to go to the R&D (600 kms away), leave my tasks for 2 weeks and provide my services, somehow reversing the tacite client(slave)-server(master) hierarchy.

Now you probably understand why I can be a bit rude and strict. But I know what I talk about on this subject. So try to benefit of what I deal to you and others here. Spare us time.

[Edited by - Charles B on November 16, 2004 6:24:52 AM]

##### Share on other sites
Quote:
 Original post by Charles BYou said "my own algorithm". Nevermind I respect people who dare to try their own way, even reinvent the wheel or make errors. It's what I also do. In the end you earn a deeper understanding when you read papers after you tried your own way. Still you said "my own algorithm". I suppose you understand that it can be perceived in two ways : my own (unique thus new), my own (effort).

Nup, I wasn't trying to be creative in my math algos. Only in my game world.

Quote:
 I know you'll possibly feel a bit idiot or ashamed for one second now. But don't worry, I could also fail to see the obvious when I started 3D .... ten years ago. See how many lines I had to spend to correct you from Alpha to Omega. [grin][grin]

I really appreciate your efforts to help me on that bit, but it is a wee bit over my head. When I said my math skills were weak, perhaps I didn't totally get the message across. Compare your ten years to my about 4 months. Not 4 months in 3D, 4 months in math over simple algebra, period. 3-5 months ago, before I even started 3D programming, I didn't know what a vector or matrix was for. Less than a week ago, I didn't know what dot or cross products were. 2 days ago, I had no clue how to find the closest point on a line (or even a plane for that matter) to another point. I didn't even know where to start. So anyways, give me some more time. I'm totally burried in this stuff 22/7.

Quote:

Quote:
 That is too many checks, it's flawed [grin]

Well don't try this way when you are not confident. Once again I don't spend time to write pointless stuff. Spare my time please. My it's flawed remark was justified, yours is just playground jerks. I have 10 years of professional 3D coding in physics, software and hardware 3D rendering, wrote Quake like soft technologies (better on some aspects, worse on others) before Quake 1 and I have followed one of the hardest formations in math during 5 years (still I forgot 95% of it). OK ?

Damn, dude. Lighten up.

Quote:

Quote:
 You don't need to check the vertices. They are part of the edges. And you only need to check a single edge, and only if you miss the flat part of the triangle. So change that to 1 sphere/plane, then possibly 1 sphere/edge.

This shows you still have not understood the problem of polygonal collision detection. You had false intuitions. You just autosuggested wrong things by playing on words and not seeing things (visually). Yes a vertex belongs to two edges, but where is the logical linke next ? Did you read about the pointers I mentionned ? Voronoi and separating planes theorem ?
...
Now once you get the min distance(point, polyhedron) algo right, you'll be able to understand the exact collision prediction algo.

Alright, back to the common sense page. What happens when you find the point where a ray becomes [ radius distance ] from an edge? Finding the point where the ray becomes [radius distance ] from a vertex is simply wasting time. The vertex point is included in the edge. Test it out. Send a sphere into a triangle. Tell me what possible angle the sphere could hit a vertex where it wouldn't be the same distance from an edge?

Quote:

Quote:
 If the real-plane point is inside the tri, you're done.

Exact in the static case ONLY. You need to have three more plane distance evaluations to conclude that, total : 4 tests and you get an early rejection/contact conclusion. You can consider negative dist. <=> interior half space. Imagine edge perp normals (also perp to the plane normal) pointing outside.

Well, I'm not interested in finding collisions into the back of a triangle. That would serve nothing more than to make objects get stuck inside of walls. As long as the movement path's dot product with the triangle normal is zero to negative, my system works.

Quote:
 But you forget that the sphere can come from below, hit an edge first and then be in this situation (inside #1) once it lays on the "pushed plane". Think of using this routine for any general mesh. As it is you algo will return a swept-sphere vs face contact, and miss the earlier swept-sphere vs edge contact. (or vert contact).

Well, if the ray starts inside of the pushed plane (which would be the case if it came from below the triangle), then checking the plane is pointless. The only possible place it could make contact is with an edge. Any edge that the ray is outside of. But this is also not necessary. Any time the sphere is inside of the pushed plane, another triangle's plane will be there to handle it. Unless it's back is exposed, which will never happen.

Quote:

Quote:
 If not, find the closest point on the lapped over edge (only check 1 edge) which is radius distance from the ray. That's it. Mission accomplished.

FALSE.
- vert/edge you forget vert/vert (cf sphere in #7).
- your swept sphere can cross up to 5 Voronoi cells between the start and end positions. So reach the pushed plane as you did and next, track the evolution of the center in the Voronoi graph till you can conclude.
- for all these reasons, this closest point tells you nothing useful.

Please keep in mind that I'm not saying that I find the closest point on the edge to the ray. I'm saying find the closest point on the edge that is [ radius distance ] from the ray. That is the point of contact. There can be no other. The point where the ray intersects the pushed plane shows the first possible contact position. If you find the edge that it passed up while hitting this position, you just found the edge that is closest to the ray. The only exception is when the ray starts inside of the pushed plane. Which I explained above.

Quote:

Quote:
 It isn't meant to be fast. I thought I made that clear ? [smile]

A good algo is always fast. Also implementations details can also be coded the first time if you are less lazy with your neurons and than you are lazy with your fingers.

And this is from the guy who tells me to use more condensed variable names [wink]

Quote:
 Thinking a bit more does not cost much. Coding wrong algos, buggy, and thus making unnecessary tests and debugging sessions costs infinitely more.

I don't understand where you went from slow-code to wrong-code. Writing unoptimized code does not produce bugs. Speeding up the code is easy as pie, after you complete it. I'm learning these routines as I go. Optimizing on the fly would just make it more difficult.

By the way, testing is never unnecessary. Unless your code is always perfect. I'm not that fortunate.

Quote:
 Now you probably understand why I can be a bit rude and strict. But I know what I talk about on this subject. So try to benefit of what I deal to you and others here. Spare us time.

The trick to mastering a subject completely is to be obsessed with it. If you have an undying love for it, mastering it is not an accomplishment. It's just a bonus. It's automatic. On the other hand, if you are trying your damndist to master something that you don't totally enjoy, you're going to end up very unhappy.

The more I learn of math, the more I enjoy it. It seems to build with every new trick I learn. This stuff is fun to me. So why ruin this complete blast by being rude or strict? [grin]

[Edited by - Jiia on November 16, 2004 9:19:18 AM]

##### Share on other sites
Quote:
 So anyways, give me some more time.

no problem, what you try is already great as you started to prove it, despite the fact its mathematically flawed. I would not spend time with you for nothing.

Quote:
 Alright, back to the common sense page. What happens when you find the point where a ray becomes [ radius distance ] from an edge ?

... from the support line of the edge that is infinite cf your GetClosestPointOnLineToPoint() function, unless I misinterpreted what it does. See the difference ? Your error comes from a semantic slip. Math require unambiguous denominations. The point/line and point/edge distances only match in the cells 2, 4, 6 of the diagram. In the cells 3,5,7 you necessarilly need to zero a (distance(vert, ray) - r) function. That's the normal way to do.

Quote:
 Finding the point where the ray becomes [radius distance ] from a vertex is simply wasting time.

You do an intersection prediction primitiveyes/no test, the best algo does not need to compute any point. Your algo needs one. The best algo only requires to compute distances (mainly a few dot products).

You need it to retrieve the contact point if your function is a collision prediction primitive for a physics engine. But you only do it after you are sure that this edge is the nearest d-facet of the triangle.

Quote:
 The vertex point is included in the edge. Test it out.

I never waste time testing 0=0 ;).

Quote:
 Send a sphere into a triangle. Tell me what possible angle the sphere could hit a vertex where it wouldn't be the same distance from an edge?

I already cleared the line <> edge confusion. Still,:
Up view    _      |  C  |    .    _   .   . . *      * *     *  *

The center C is in contact with the vertex still the distance to the support lines of the edges is lower than the radius.

Unless you compute an actual finite edge / ray. But it's not what your code does.

THE CORRECT WAY TO SEE THE PROBLEM :

Imagine your flat triangle extended by radius. This rounds the edges (cut cylinders); and vertices (spheres), the face an extruded triangle. That's the exact shape. The problem becomes ray against this shape.

Quote:
 Well, I'm not interested in finding collisions into the back of a triangle.That would serve nothing more than to make objects get stuck inside of walls. As long as the movement path's dot product with the triangle normal is zero to negative, my system works.

See the side view :     C*     *    * A*B ^  *   E |    *  O      * F

The sphere O will hit the edge AB, before it's above ABC + radius. It comes from behind the support plane of ABC.

Unless you count to deal with convex interior shapes (rooms). Be certain to face wall traversal bugs near the edges for any other kind of mesh.

Quote:
 Please keep in mind that I'm not saying that I find the closest point on the edge to the ray. I'm saying find the closest point on the edge that is [ radius distance ] from the ray.

Of course. Generically that's called a zero point, no problem. You have something like dist(P(t)) - r = 0. It's a root extraction of a second order polynomial in t. The problem is it's not what you compute.

Quote:
 ...If you find the edge that it passed up while hitting this position, you just found the edge that is closest to the ray.

False. Imagine your capsule as a moving sphere. S(t), depends on the time parameter.

Say th is the time when the sphere hits the triangle support plane. Say tc is the point where the contact occurs, assuming one exists.

You define closest as the point closest to tri_plane_hit. This closest is also (sometimes, cf the vertex issue) the point of the triangle nearest your sphere at th.

But this tells absolutely nothing concerning the point that will be closest at tc. I call it closest(tc). BTW you realize that it's the actual contact point.

- closest(th) is not closest(tc). closest(tc) will most probably be somewhere else on the same edge => you will miss collisions and your sphere will penetrate the triangle, even slightly if you sphere moves slowly.

- closest(tc) can even belong to another edge. => you miss collisions again.

- you forget to consider the vertices as a special case of nearest point.

The problem is if you use small time steps, you may not see your mistake. Also don't choose moves perpendicular to your edges, the only case where your capsule (swept sphere) vs sphere is relevant.

Quote:
 I don't understand where you went from slow-code to wrong-code.

I was just arguing on the "think more / code far less" trade. The optimization thus often comes for free as a bonus. I never said don't test. I always test everything through unitary tests. But it's much faster when you already know which are the problematic cases to focus on. Else bugs will easilly pass your tests.

Quote:
 Speeding up the code is easy as pie, after you complete it.

No, the most beautiful optimization are uneasy. They require to already think of them very early in the analysis. Actual optimizations can be very subtle mixing low level coding and algorithmic issues in a very inticated way. You should read the th old Zen of Graphics programming to understand fully what I mean. An orthodox (university biased) programmer would never have succeeded in making Doom when Carmack and Romero did it. But that goes off topic.

Quote:
 The trick to mastering a subject completely is to be obsessed with it ...On the other hand, if you are trying your damndist to master something that you don't totally enjoy, you're going to end up very unhappy.....The more I learn of math, the more I enjoy it.

Good but make the effort to google around all these elements : Voronoi, Separating Axes theorem, Delaunay. Once you get the mental picture, believe me, you'll enjoy such 3D algos power two.

Well this is just like bicycing to me. It's fun when you ride, not when you begin and fall . First days are rude. I am rude against what's false in your maths, not you. Maths require come strictness. Maths objects are true or false. Next comes elegance, that is concision, thus fun and a feeling of magic and power.

Take all my critics positive and negative as encouragement to get the most important elements early and have this new eye on geometry. You said you just started anyway, I say encouraging. But I can't encourage you to follow the wrong tracks.

[Edited by - Charles B on November 16, 2004 5:02:13 PM]

##### Share on other sites
Quote:
 Original post by Charles BYou define closest as the point closest to tri_plane_hit. This closest is also (sometimes, cf the vertex issue) the point of the triangle nearest your sphere at th.But this tells absolutely nothing concerning the point that will be closest at tc. I call it Nc (contact point).- closest(th) is not closest(tc). closest(tc) will most probably be somewhere else on the same edge => you will miss collisions and your sphere will penetrate the triangle.- closest(tc) can even belong to another edge. => you miss collisions again.- you forget to consider the vertices as a special case of nearest point.

As you read this response keep in mind that I am very confused and I'm not really getting this Voronoi math...

but from reading what I have quoted, it sounds to me like you are telling him that his algo will fail because he is using the intersection point on the triangle's plane to find the closest point on the edge of the triangle. The code he has listed does look like it is doing this... and earlier I was trying to tell him that this was the classic flaw in the Nettle-like algorithms. but If you read his other thread about closest point on one line to another, you see that he has changed that into finding the closest point on the edge to a line...

I'm just wondering if you've taken that into consideration and I totally missed it or if you're still looking at his original code...

Also, I've started reading a little bit about Voronoi and I don't have a full grasp of it yet (I'll keep trying) but from what I've read it sounds like people use it more for convex hull collision and I'm having trouble seeing how it relates to this problem of the Sphere vs Triangle...

It's not that I don't believe you it's just that this is all seriously over my head

##### Share on other sites
K I'll recheck the whole thread carefully to see if his change I did not notice makes any difference. But I am pretty sure the algo only looks OK through his test, and will mainly fail in real conditions because of the vertes subspaces stuff. The worst bugs are those that only occur rarely. A debugging hell.

Else a triangle is a special convex hull. It is simply flat (add an up and down face to make it a degenerate closed convex shape. This also means that the Vornoi diagram (graph part)around any triangle is fully determined à priori. That's why you can optimize the code in this special case. Instead of walking in a graph structure you simply have to hardcode a few plane tests.

Else to understand the Voronoi space partition around a convex, take the simpliest convex above the single vertex, that is an edge with vertices A,B. See how you can compute the distance between a vertex V and edge A,B

   1      x V       A .   ----x-----      |   2  | . . x V      |  ----x-----   3  B        .          x V

The infinite space is just subdivided in three (infinite) convex parts. If P is in subspace 1, then the point of [AB] nearest to P is A. Distance is : sqrt(dot(P-A, P-A)).

If P is in subspace 2. The point of [AB] nearest to P is the point of (AB) (infinite line) nearest to P. Then distance just needs to remove the component of AP in the direction of AB (on this scheme it's the y component). Remove the projection of AP on AB. that's what I meant by of the form x*x+y*y. It's in fact a 2D distance in the right coordinate system.

If P is in subspace 3, then B is the nearest point.

Is there any difficulty to understand that ? Just check any algo you know for point/edge and see how it's necessatilly related to this scheme. The usual algo projects on the line and tests a parameter t like this : t>0 ? t<1 ? this gives the three end cases.

Now you can easilly transpose to the triangle/point issue. then to the triangle/sphere. Then to the triangle/swept-sphere (add time). Then click on the link to the thread I mentionned and you'll start to see how powerful this space partition around any convex polyhedron is.

[Edited by - Charles B on November 17, 2004 11:33:51 AM]

##### Share on other sites
Okay, let me just say it one more time. I am not finding the closest point on an edge to any points. I am not finding the closest point on an edge to any rays.

I am finding the point where the ray becomes [radius distance] to the edge. There is a huge difference. Although finding the closest point on the edge to the ray will always detect collisions, if there is one, it will not give very good results when you want the point of contact.

For example, if the ray is moving into a triangle area 6 inches this frame and collides, the closest point on line to line method will report a collision, say at 3 inches. So the contact point is 3 inches after the start point. So now we change that 6 inches of movement this frame to 16 inches of movement this frame, but the exact same direction and starting point. The method will now report that contact was made after 4-5 inches of movement. So it will always report the correct yes/no answer, but the distance is off.

In a game, the point of contact is pretty important. The code you see at the top of this is 2-3 days old (err, I think). The pushed plane idea is all that remains of it in my current code. The new code finds the point where the ray end distance from the edge becomes radius.

Actually, I have learned something from this. If the ray starts inside of the pushed plane, two edges need to be checked. My assumption that another triangle would take care of it was incorrect. But the idea is very simple. When the starting point of the ray starts inside of the pushed plane, check the edges which are facing the opposite direction that the ray is moving. This could be a maximum of 2 edge checks, but sometimes could only be 1. Basically, look at the direction of the third vertex (the vertex that the edge is not connected to) from the center of the edge. If the ray is moving towards that direction to some degree, then it needs checked.

I'm holding on to my idea that the pushed plane intersection holds the first point of contact. I'm also still saying that only one edge needs checked when the ray intersects the pushed plane (starts outside of it). I have been testing this algo for 2 days straight. Mainly because I had a little trouble projecting a fixed path after collision. But the point is that out of all of the angles I've tried, this routine has never failed.

By the way, any suggestions on how to prevent several collisions in one frame and still allow "sliding"? I think I'm going to trap the sphere inside of every sliding plane that it creates. For example, if a sphere hits the ground, and slides into a wall, the wall will not only force the point back onto it's sliding plane, but the floor's as well. So on, so on. I haven't tested this out fully.

Thanks for all of the advice

edit:
Quote:
 develops to :Pos*N - N*A - r*N*N

I'm not really sure I know what vector * vector means at all. Is this a cross product? Dot product? I've seen it on math sites quite often, but I have no idea what operations are being performed.

[Edited by - Jiia on November 17, 2004 1:32:04 AM]

##### Share on other sites
Quote:
 Original post by JiiaBy the way, any suggestions on how to prevent several collisions in one frame and still allow "sliding"? I think I'm going to trap the sphere inside of every sliding plane that it creates. For example, if a sphere hits the ground, and slides into a wall, the wall will not only force the point back onto it's sliding plane, but the floor's as well. So on, so on. I haven't tested this out fully.

I think what you want is recursion... if your collision response moves the object, that movement needs to be tested for collision and so on...

is that what you were looking for or did you already know that?

##### Share on other sites
Quote:
 Original post by TempusElfI think what you want is recursion... if your collision response moves the object, that movement needs to be tested for collision and so on...is that what you were looking for or did you already know that?

Right, but I'm having trouble puting the object back on track in the second, third, fourth, etc recursive hits. For example, if I hit a ground triangle (1st), and that slides me into a wall triangle (2nd), sometimes the wall triangle slide will put me back into the ground triangle, depending on it's angle.

In some complex corners, I was getting up to 8 recursive fixes!

I want to at least allow 4 recursive slides before it stops the sphere completely. But I don't want to waste any of them on the same triangles twice. My routine seems to be doing it a lot. It may be because my world mesh is a bit messy. It is pretty hacked together. It's hard to tell what angles the polys are on.

Still, I don't want to limit my world meshes to perfect 90 degree corners anyways. I'm just not sure how to avoid hitting the same general planes more than once. I especially seem to have trouble on the ground triangles.

##### Share on other sites
sphere is very good for collision - collision of sphere with any mesh(including single triangle) it's intersection of ray with thing that have sphere at each vertice, cylinder at each edge, and each face displaced along it's normal by radius. (i mean ray of sphere center movement and point of intersection with "thing" gives sphere center at time of contact)
It's in fact simple to see... that thing is a volume that iff sphere center is inside that volume, sphere intersects triangle.

##### Share on other sites
Quote:
 Original post by JiiaOkay, let me just say it one more time. I am not finding the closest point on an edge to any points. I am not finding the closest point on an edge to any rays.

Damn, we all know what finding a contact point means. You did not catch what this nearest points stuff means in the algorithm, it's related to the Voronoi partition around the triangle that allows you to know against which d-facet (vert, edge or face) the contact will occur first.

THE THEOREMS CONCERNING NEAREST POINTS ARE ELEMENTS OF THE THEORY. NOT OF THE COMPUTATIONS THAT USE THE THEORY.. The theory is implicit in the computations. That's math ! And that's why they are powerful.

I never told you to compute the nearest point of the triangle to your capsule. This would most probably be after the first contact, and none seeks this info. Of course, the problem is to find when the sphere hits the triangle first. And then at this time, the contact point is obviously the nearest point between the sphere and the triangle. A capsule is simply a moving sphere, that's the correct way to see things clearly and not miss the first time of contact.

I told you, try static sphere/triangle first. Test it toroughly. Frankly do it. Step by step. Then, once you understand it totally, you'll be able to have a flawless time based collision prediction. That's what a capsule test means : collision prediction, it's harder and more subtle than collision detection.

Quote:
 The pushed plane idea is all that remains of it in my current code. The new code finds the point where the ray end distance from the edge becomes radius.

Naturally. It is the first test to make it removes more than 50% of the cases. I think I already mentionned this. But in the end, correcting your code you will just see that all I said about the Voronoi partition is your GetTriangleEdgeThatPointIsOutsideOf() part corrected. In the end you will just rediscover the canonical algorithm.

I think your main false assumptions came from that you tried to reap some conclusions from the situation at the time the sphere hits the support plane of the triangle (cf the pushed plane stuff). This gives no information about where the contact will occur next except in the easy face/sphere case. It's only useful for early rejection or early face/sphere contact conclusion. The rest depends on the movement direction, and which Voronoi cells are crossed afterwards.

Quote:
 Actually, I have learned something from this. ...check the edges which are facing the opposite direction that the ray is moving.

See, it's still too intuitive, and mathematically undefined. You need to elaborate more. How can you tell that an edge is facing something ? I has no surface, it's a segment of line, no normal. Tip : you necesarilly have to speak of planes and positive/negative half spaces. Well again this is the Voroin stuff. It's the Voronoi edge cell that you are talking about.

Beginners often do similar mistakes concerning front facing culling. They think intuitively : "Compare angles between the camera front direction and the face normal, dot product em". But this only works in isometric projections. Intuition is often misleading. The correct way is to think half space, that is volumes instead of angles. It's "Is the camera in front of the face ?" Not : "Is the face in front of the camera" ?. A punctual-projection has no true front direction. Then what about Z or the homogenous coordinate. No, that's something else. If the fov is 360, any direction is frontal ! This depends on which object you focus on. A face has a unique front direction (if oriented ccw or cw). Front-face culling is done through plane equations. You must now realize that plane equations are everywhere. When you transform a vertex in affine space in fact you compute three plane point distances.

Quote:
 By the way, any suggestions on how to prevent several collisions in one frame and still allow "sliding" ?

That's a very complex thing to do, I mean in a global game code context, not just in a demo. Collision prediction and time continuous physics are just used partially. I and others try to explore this way. No 3D engine uses this as far as I know. The issue is to keep tracks of constraints and detect the events when they appear and disappear.

Quote:

Quote:
 develops to :Pos*N - N*A - r*N*N

I'm not really sure I know what vector * vector means at all.

= N*(Pos-A) - r

since N*N = 1

scaling : *, dot product : *, cross product : ^, it should be so in my opinion. But it's not well standardized. Still in your context it was rather clear. In fact I realized that you computed a distance in the ray direction, the fast and meaningful way to do is compute in the normal direction, what I showed you. Talking of distance between a plane and a point (or a sphere), it's the distance in the normal direction.

[Edited by - Charles B on November 17, 2004 11:14:38 AM]

## Create an account

Register a new account

• ### Forum Statistics

• Total Topics
628282
• Total Posts
2981812

• 9
• 10
• 11
• 17
• 15