Jump to content

  • Log In with Google      Sign In   
  • Create Account


Member Since 10 Jun 2004
Online Last Active Today, 09:14 AM

Topics I've Started

Finding usable normals from complex embedded sphere-tri situations. Try to poke holes i...

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.


Attached File  Embedded situations 2.png   12.26KB   1 downloads


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


Attached File  Intersections.png   13.85KB   0 downloads



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.


Attached File  4 ways.png   157.68KB   0 downloads

Annoying things about Fauerby's and Nettle's sphere-mesh collision detection gu...

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:


Attached File  whole.png   353.83KB   0 downloads



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


Attached File  bottom.png   207.98KB   0 downloads


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:


Attached File  Top.png   253.71KB   0 downloads


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

How do I unit test complicated ideas?

30 December 2015 - 07:36 AM

The problem is largely that to write test cases, I would have to manually work out quite a lot of things that really I am relying on a computer to process in the first place. 


My troubles with this are around writing some code for collision detection. Sphere-Polygon collision detection. 


A good example is given by this: http://www.peroxide.dk/papers/collision/collision.pdf


It's a guide for writing the kind of thing I want, complete with code at the end. This algorithm combines several functions: rays intersecting planes, spheres intersecting lines, and all that. I could run unit tests over those, sure, it's just a heap of maths. But the algorithm on the whole actually has 2 mistakes. Both bugs are of a nature such that I can't think of a way to test for them without actually being aware of them before they happen. And that's why I haven't described what those 2 bugs are; to demonstrate how hard/unreliable it is to think we can predict every mistake in an algorithm.


So I still don't know how to design an algorithm this way without being at the mercy of the bug that appears in 2 weeks. How can I test this stuff in a smart way?


Thanks smile.png

Unity: Beginner asking advanced question about interacting with dynamic slopes

18 February 2013 - 09:22 AM

I've only recently started learning how to use Unity and 3D development tools in general, so this question is pretty naive about what can and can't be done. 


Basically, can I create an scene with an interactive character running around, where the landscape changes shapes beneath the character's feet and the character 1. stays connected to the land, and more importantly 2. reacts to the gradient beneath his feet as said gradient is changing. 


For example, imagine the following takes place over 4 seconds:


Attached File  curvingFloor2.jpg   7.8KB   34 downloads


In the 2nd step, the character should start being pulled down the slope due to the change in gradient.

In the 3rd step, assuming some magical force is keeping their feet on the inverted ground, they are still being affected by the new gradient but less severely, as the gradient here is more shallow than the 2nd image.


Is this hard to do in Unity?

If it isn't too hard, could someone give a quick and general semi-layman's terms description of how?






DirectX - Where did my window icon go after fullscreen?

23 September 2010 - 08:58 AM

I thought I'd post this here as I don't know if it's really a problem of DirectX code. EDIT - This is a DirectX issue, as it turns out.

Basically my window can toggle between windowed and fullscreen mode fine, saving previous position and state. But one thing I don't know how to bring back is the little window icon up in the top-left. The one that brings up the restore, move, size, etc menu.

I'm not sure where in my code the mistake is, because I'm missing something fundamental it seems. But here are some snippets: EDIT - The following code snippets are fine really. The problem doesn't exist unless DirectX changes the display mode.

Creating the icon:
    WNDCLASS wc;
wc.hIcon = LoadIcon(GetModuleHandle(NULL), MAKEINTRESOURCE(IDI_ICON1));
Before changing the display mode for fullscreen mode:
        SetWindowLongPtr(g_parentWindow, GWL_style, WS_POPUP|WS_VISIBLE); 
SetWindowPos(g_parentWindow, NULL, 0, 0, 0, 0, SWP_NOSIZE | SWP_NOMOVE | SWP_FRAMECHANGED);
Before changing the display mode for returning to windowed mode:
        if (g_maximised)

viewCopy.right - viewCopy.left,
viewCopy.bottom - viewCopy.top + (g_statBarIsOn?statRec.bottom:0),

The results are the same whether the window is maximised or not.

I imagine the solution is simply a necessary call that I'm missing... but I don't know what that is. :S Cheers. :)

[Edited by - ApochPiQ on September 25, 2010 1:04:37 PM]