Jump to content

  • Log In with Google      Sign In   
  • Create Account


Member Since 10 Jun 2004
Offline Last Active Sep 17 2016 09:26 PM

#5279642 3D Model Terrain Collision

Posted by on 05 March 2016 - 05:26 AM

I actually disliked that 'remove degrees of freedom' approach in Linahan's article. I disliked the article on the whole, finding issues with it almost as much as I found with Fauerby's. I rambled with displeasure here: http://www.gamedev.net/topic/674540-annoying-things-about-fauerbys-and-nettles-sphere-mesh-collision-detection-guides/


Since you say it was used in Doom, perhaps I simply didn't recognise the proper application for the restricting degrees of freedom approach. Perhaps what I had in mind was something it didn't cater to. I can't remember why I was whining about that particular thing. I'm sure I look stupid in my other thread hehe. 


I believe Fauerby's quadratic coefficients for detecting edge intersections are wrong also. This is because they are a straight copy of Schroeder's coefficients (found in the August 2001 copy of GDmag, at http://www.gdcvault.com/gdmag - you're welcome, people on the internet trying to source that). And Schroeder's coefficients are likely wrong, because Akenine-Moller says they are (in Real Time Rendering), and Akenine-Moller's coefficients are definitely correct.


Since Akenine-Moller used the exact same equations but got different results, and since none of these authors ever show how they get from equations to coefficients, Schroeder's are most likely wrong, which means Fauerby's are too.


The reason I say AK's coefficients are definitely correct is because Ericson (Real Time Collision Detection) produces the same coefficients as Akenine-Moller, and while Ericson - like every other author - doesn't show how he reached from equations to coefficients, Ericson's approach actually can be proven on paper. I believe the others required Mathematica; at least, Schroeder did. But Ericson's coefficients are definitely legit, and Akenine-Moller's are the same, even though Ericson uses a different approach (no simultaneous equations, no dot product = 0 trick).



So Nettle's guide = big mistakes, Fauerby's guide = several mistakes, Schroeder's guide = wrong coefficients.


Interestingly, these 3 authors are the 3 who wrote guides. Ericson and Akenine-Moller didn't write guides, they wrote books. Says something, doesn't it?

BUT having said that, Ericson also totally supports Nettle's completely incorrect approach, now listed as such on his website. Ericson also oddly describes his approach as "the one suggested in Schroeder with corrections in Akenine", when it simply isn't. The difference is the only reason I was able to work it out and confirm it as correct.

#5274484 Finding usable normals from complex embedded sphere-tri situations. Try to po...

Posted by on 05 February 2016 - 11:32 AM

I plan to write a new guide to sphere-mesh collision handling, since I haven't been able to find anything that doesn't come with a few problems. (The next best thing is Fauerby's guide at http://www.peroxide.dk/papers/collision/collision.pdf ).


Part of the approach I'm taking is to support one-way collisions. That is, to ignore back-facing collisions not just for a performance gain, but for practical application as well. The desired result is for the sphere to be able to find itself embedded inside a triangle and still produce "expected" motion and collisions. But not just one triangle; many triangles, at the same time, in perhaps complicated ways.


By "expected" motion, I mean that it slides only in ways that make sense, it doesn't fall through, and if required to push away from the collision, it pushes away along 1 overall normal that also makes sense. (For example, the user might simply press jump.)


Some intersections might be in front of a tri's face, while some are off to the side, while some triangles register the sphere as closest to one edge, while others find it closest to a vertex shared by earlier triangles, etc etc etc., all at once.


Much words. Such confuse. 


I spent entire minutes putting together this example of 3 relatively simple embedded situations. On the left is an embedded situation; on the right is a similar realistic situation that my brain thinks matches the embedded one. The goal is for the sphere in the embedded situation to behave as if it were in the realistic situation. These 3 examples are okay demonstrations of this idea, I believe.


Embedded situations 2.png


Bear in mind these are just 2D; 3D situations must be handled as well.



I believe I have found a process to get a correct set of normals from any situation at all. But mathematical proofs are tough, and I wouldn't know how to begin unit testing this. So instead, I'll describe my solution/algorithm and challenge any readers who might be really keen to dream up an embedded situation that breaks it. 


Hopefully someone will find holes in someone else's ideas. You can use as many triangles as you want. If it's not obvious, specify which side is the front of a tri.



My solution:


Things we know:

* Sphere's centre

* Sphere's radius

* Position of every vertex of every triangle.

* Face intersection == the sphere's centre projects onto the face of a tri that it intersects.

* Edge intersection == the sphere's centre projects onto an edge of a tri that it intersects, but doesn't project onto the face of that tri.

* Vertex intersection == the sphere's centre overlaps a vertex of a tri that it intersects, but doesn't project onto the face of that tri, nor either of that vertex's two edges. 

* Intersection point == closest point on any given intersected triangle to the sphere's centre

* Collision normal (per intersection type) == Direction from intersection point to the sphere's centre





Here's that algorithm:


1. Test every triangle to see if it is intersecting the sphere. If it isn't, discard it. Ignore any back-facing situations (sphere's centre is behind triangle's plane).

2. If a triangle is intersecting the sphere, determine whether it is a face intersection, edge intersection, or vertex intersection.

3. Face intersection? Add its collision normal to "the list" of collision normals discovered so far.

4. Edge intersection? If that edge is not involved in any face intersections, add its collision normal to the list. Else, ignore it.

5. Vertex intersection? If that vertex is not involved in any edge intersections, nor face intersections, add its collision normal to the list. Else, ignore it.

6. To slide the sphere with a new velocity, remove from that velocity any vector component that goes into any collision normal in the list. Then slide.

7. Or to push away from the embedded position, average all the normals' directions and use that as an overall collision normal.



To help the brain think in 3D, recognise that this image is showing 1 face intersection, 2 edge intersections, and 1 vertex intersection. In this example, only the face intersection's normal would be used, not just because it already involves all intersected edges and vertices, but also because the sphere's centre is behind the other 3 triangles' planes.


4 ways.png

#5270112 Annoying things about Fauerby's and Nettle's sphere-mesh collision de...

Posted by on 08 January 2016 - 12:08 PM

When I write about Paul Nettle's guide, that will be along the lines of "I think this is wrong, do you guys agree?"


But that's not what I was doing when writing about Fauerby's guide. Your post is kind of taking incorrect guesses at things my post already explained. That's ok, I admit mine is a long post and it's hard to fully explain problems with a 48-page guide. But I was stating, not guessing, when I said:


The problem is that Fauerby applies this distance along the direction of the sphere's velocity, instead of along a direction that separates sphere from triangle.


The veryCloseDistance value is not a projection, it's just a constant that always gets applied along the velocity vector only. There is no 'normal-based' version of it. That was one of the first fixes I thought of, but if it was a projection I can show how this would lead to another error of colliding well before reaching a triangle. 


Also, colliding gradually is exactly what the first error (the veryCloseDistance ... finger-infinitely-close-to-your-desk error) causes if the second error (the bogus sliding plane normal) isn't happening also. I say that from having toyed with different veryCloseDistances to try to fend off the flaw. It literally makes things soggy as you move around.


Thanks for taking the interest though. smile.png I wanted to email the authors but things are so old it'd feel like emailing Patrick Stewart about Star Trek. So I vented here.



I'm working on my own version of this collision detection that doesn't use padding at all, but instead is insensitive to embedded collisions. It avoids the two mistakes in Fauerby's guide. Plus, Fauerby's guide also always runs vertex sweep tests before edge sweep tests, instead of recognising that edge sweep tests will often make vertex sweep tests redundant (as the whole process is all about delaying unnecessary tests as much as possible).

#5270015 Annoying things about Fauerby's and Nettle's sphere-mesh collision de...

Posted by on 08 January 2016 - 03:26 AM

This is a discussion of the method for colliding a moving sphere against a mesh of triangles.


Here's what Paul Nettle wrote in the year 2000: http://pisa.ucsd.edu/cse125/2003/cse190g2/Collision.pdf

And here's what Kasper Fauerby wrote in 2003: http://www.peroxide.dk/papers/collision/collision.pdf


They've both been annoying me silly because they both have mistakes, and I haven't found anything at all that talks about solutions even though Fauerby's method in particular is referenced quite often. So I find myself looking at a 12-year old document with definite mistakes, yet seemingly no resistance from online communities.


In the case of Fauerby's work, I had coincidentally implemented the same mistake before knowing his code even existed. Once I saw his code, I saw the same logical error. So my question then became, if Fauerby has done the same thing I have, shouldn't his collision detection also fail? I threw his code into Unity and, well, it didn't fail. But the error was definitely there in the code. So what's the deal?


The logical error is in the calculation of the padding distance: the distance that a sphere is supposed to stop short of hitting a tri (in order to avoid floating point errors and wotnot). This distance means that the sphere should never actually touch any tri, but always stop a tiny bit before it.


The problem is that Fauerby applies this distance along the direction of the sphere's velocity, instead of along a direction that separates sphere from triangle. In other words, Fauerby only stops the sphere short of the point it would collide with, not the triangle it would collide with.


To demonstrate, make a point right now on your desk. Now, keeping your finger 5cm away from that point, how close can you get to the actual desk? Infinitely close. Just put your finger on the desk somewhere that's 5cm away from the point you drew. This satisfies Fauerby's padding operation but as you can see, your finger is already colliding with the desk. 


The mistake is on page 46 in Fauerby's code linked above:

VECTOR V = vel; 
V.SetLength(collisionPackage->nearestDistance - veryCloseDistance);
newBasePoint = collisionPackage->basePoint + V;

The padding "veryCloseDistance" is being applied in the direction of the sphere's motion "vel". This separates the sphere from the point of collision, not from the triangle of collision. It comes into effect practically 100% of the time the sphere moves along a surface. 


So why did his collision method still work?


Fauerby's code actually has another error, and the second one really does happen to compensate for the first. As soon as the sphere gets "too close" to a collision point (which should mean too close to a triangle, but it doesn't), his calculation for the plane it's meant to slide along goes wrong. By accident, it gains a slight upwards incline (assuming the plane is the flat ground), pushing the sphere up and out of the "too close" vicinity. This goes back and forth, every 2nd frame, and with no upwards acceleration being applied by the user, and with gravity in effect, close inspection reveals the sphere to actually be jumping up and down as it slides along a perfectly flat plane.


So if you grab Fauerby's code and copy pasta it into your IDE, things will work well enough for your eye to be satisfied. But I don't like it.


Here's a screen of the overall situation. Each cyan or magenta line is a new frame as the sphere moves to the right:





Here's the action at the base, close up:




If you look closely, you can see that every cyan frame is actually lifted off the horizontal that the magenta frames are on. This is because the magenta frames were found to be "too close", and as a result, their sliding plane normals were incorrectly calculated, pushing the sphere upwards a little for the next frame.


Look even closer and you'll see white lines too. Except, only near the magenta lines. Those white lines are actually pure "up" lines, and they're really behind every coloured line there; it's just that the cyan lines hide them perfectly. The magenta lines do not hide the white lines perfectly, because the magenta lines are not going perfectly upwards. 


If we look a little higher, that is made more clear:




So if you haven't guessed it already, the cyan and magenta lines are both showing the sliding plane normal that was calculated for that frame. The plane that the sphere is sliding along is perfectly flat (hardcoded, not modelled), so all those sliding plane normals should be perfectly upwards. But those magenta mistakes are actually the only things that keep Fauerby's sphere from slipping through triangles.




I'll come back to the problems with Nettle's code later. In that case, I haven't implemented his method and I don't plan to, because I believe I can already see a real mistake in it (as well as the same 2 mistakes Fauerby used).