Just before we examine the code for the dual tree walk, lets discuss what we're trying to achieve.

We're walking two bounding volume hierarchies (BVH's) in order to determine which pairs of Triangles are so close that they COULD be intersecting (or colliding)... essentially it's a search for closest pair of features from two bodies, where the features are always triangles.
Having done this, we'll need to be able to test a given pair of Triangles to check if they actually ARE intersecting (or colliding).

I've been looking for an ideal triangle/triangle intersection test for a week now.
Many of them seem to be based on the same algorithm, in that the first thing they do is to classify the points of one triangle (eg triangle A) against the PLANE of the other triangle (eg triangle B).
If all the points clearly fall on the same side of the plane, and the points do not ALL live APON the plane (ie the triangles are NOT COPLANAR) then that Plane must be a Separating Axis, and these two triangles cannot be intersecting, so we can exit the intersection test early.

Many implementations will then go on to test the same pair of triangles in reverse order ... ie, classifying the points of triangle B against the plane of triangle A.
I believe that this second test is REDUNDANT as we have already determined that the PLANES MUST INTERSECT, and that intersection is at least POSSIBLE.
Furthermore, I believe that this situation has occurred through the misunderstanding of a simple statement in an early whitepaper on the subject, which says something along the lines of "if the points of EITHER triangle fall to one side of the plane of the other triangle", which IMPLIES that we need to perform two tests of this kind, so that a programmer who read the notes on the algorithm without TRULY UNDERSTANDING IT would inevitably fall for this trap.

Just remember that we'll be calling these functions a LOT, so any savings we can make will impact dramatically apon the performance of the simulator, especially when it is under load !!!

Anyway, I'll be posting the code for the tree walk, then I'll post the code for the triangle-pair intersection test, and I'll provide descriptions and comments so you can understand exactly what is going on... perhaps someone will see further optimizations that can be made to further accelerate what will become the most cpu-intensive code in the entire engine (an obvious bottleneck).

Posted on 2009-03-01 09:04:59 by Homer

Unfortunately, I can't tell you how well PhysX does on cards that DO support a true physics coprocessor, but I can say that has very little to do with the PhysX engine anyway!

There is no need for a 'true physics coprocessor'. The current Cuda implementation is already faster than a dedicated PhysX card on a GeForce 9800GTX+ or better (this is while the GPU does both graphics and physics vs the GPU doing graphics and the PPU doing physics).
Cuda is an elegant and cost-effective solution. Dedicated physics hardware will probably be marginally faster at best (which I doubt in the first place, given the G80/92/200 architecture), yet cannot be used for anything but physics. So it will either lead to larger, more expensive chips, or chips with smaller GPU portions.
Posted on 2009-03-09 07:58:25 by Scali

I'm beginning to suspect that some (if not most) of the list of game developers using PhysX are startup companies which are indirectly owned by nvidia - this is just an exercise in self promotion, where are the benchmarks? They benchmark everything else. I think the demos that they ship with it tell the real story.

There are also some big names involved... The UT3 engine uses PhysX... and EA has licensed the technology... an A-list game like Mirror's Edge now uses it too.
Aside from that, I've not seen any proof that Havok is any better than PhysX, even in software. So I don't think PhysX is doing all that badly even for those without an nVidia card.
Obviously for those WITH an nVidia card, the performance and realism levels are just well above any alternative solution.
Posted on 2009-03-09 08:02:08 by Scali
Dedicated physics hardware will probably be marginally faster at best (which I doubt in the first place, given the G80/92/200 architecture), yet cannot be used for anything but physics. So it will either lead to larger, more expensive chips, or chips with smaller GPU portions.
I thought the PhysX board was generally programmable?
Posted on 2009-03-09 10:57:14 by f0dder

Dedicated physics hardware will probably be marginally faster at best (which I doubt in the first place, given the G80/92/200 architecture), yet cannot be used for anything but physics. So it will either lead to larger, more expensive chips, or chips with smaller GPU portions.
I thought the PhysX board was generally programmable?

Sure it is, but it's not exactly DX10-compliant shader stuff :)
Aside from that, it lacks the fixed-function hardware that a GPU has.
If it did, it wouldn't be dedicated anymore.

It's only slightly different from the Cuda architecture in nature.
The key to the PPU was not the raw processing power itself, but rather the network-like architecture, which allowed the execution units to quickly forward results.
Cuda has a huge shared cache which allows the shaders to do the same. That's what's unique about nVidia's architecture... it is a feature that has no function whatsoever for graphics (data is never shared between shaders, other than basic cached textures and such), it is solely for improving GPGPU performance.
I'm not sure if ATi has something similar actually.

So basically what I think it boils down to is this:
- The PPU might be slightly more efficient in data forwarding than the Cuda architecture, but not that much.
- The PPU isn't very useful for graphics, if at all.
- Cuda is probably as good or better at other general-purpose tasks.

So to me it makes more sense to do physics on the GPU than the other way around.
nVidia elegantly turned its GPU into an efficient physics processor by adding the shared cache.
Trying to turn a PPU into a GPU/CPU seems to be a bit backwards, especially for a company like nVidia.
So I don't think you can really improve the current nVidia architecture by adding a dedicated physics architecture.
Posted on 2009-03-09 12:24:29 by Scali
So I take a couple of days away from my thread and another thousand views :) Really I must apologize for the delay in my usually regular postings, but I don't want to ramble about something if I don't have the sourcecode to back it up, and just recently I've had a heavy workload, which in the current economic environment is a Good Thing.

I will be posting some more juicy stuff over the coming days, so the wait will have been worth it, but in the meanwhile, here's some stuffing:

``Method D3D_PhysicalEntity.Find_Contacts,uses esi ebx, pOtherEntityLOCAL pNodeA,pNodeB    SetObject esi        ;Obtain ptrs to the Root of each SphereTree    mov edx,.pOwner    m2m pNodeA,.D3D_CollisionMesh.pRootNode,eax    mov edx,pOtherEntity    mov edx,.D3D_PhysicalEntity.pOwner    m2m pNodeB,.D3D_CollisionMesh.pRootNode,ebx        ;vtemp = NodeB's origin in Body A's space    ;If (A.radius+B.radius) < distance(A,B)            ;If NodeA is not a leaf:           ;If NodeB is not a leaf:               ;Recurse A.front, B.front               ;Recurse A.front, B.back               ;Recurse A.back, B.front               ;Recurse A.back, B.back           ;Else               ;Recurse A.front, B               ;Recurse A.back, B           ;EndIf        ;Else            ;If NodeB is not a leaf:                ;Recurse A, B.front                ;Recurse A, B.back            ;Else                ;If A and B are both leaf nodes:                    ;Test A.face, B.face                ;EndIf            ;EndIf        ;EndIf    ;EndIf        MethodEnd``

Posted on 2009-03-11 05:04:19 by Homer
The entire collision algorithm has been reworked. Here's a brief in regards to the revised algorithm:

The main collision detection method finds pairs of entities whose boundingspheres are going to intersect during the current timestep, calculating First and Last moments of contact for each pair (the time when the spheres begin to touch, and the time they begin to separate again).
Each pair is then passed to a function which uses these two times as a 'search window', and proceeds to bisect that search window to find the moment of contact between the underlying geometry of the pair of entities.
This, of course, involves calls to our NarrowPhase separation test at various 'test times'.
Since our search window is one TimeStep (0.100 Seconds) or less (generally far less), we quickly bisect our way to a moment of impact within the tolerance of our epsilon (numerical limit of accuracy).
It's entirely possible that the underlying geometries of the input pair of bodies NEVER ACTUALLY TOUCHED and so false positives are pruned at this point.
Each pair that actually DOES collide is recorded along with the moment of impact, and the record is stored in a list that is sorted by moment of impact.
Note that no actual Contacts have been generated yet.

Once all the collision testing has been completed, the simulator will attempt to exhaust the list of records of colliding pairs of entities.

Starting with the pair at the earliest moment of contact, it integrates the entire simulation to that time, then generates the contacts between these bodies, resolves the contacts and calculates net changes to the physical state of each body BUT DOES NOT APPLY THEM.
Any further records which have the same moment of contact are now consumed.
Now the net changes in physics state are applied to the bodies we touched so far.
And now we repeat all the above until our list of records is exhausted.

The goal of Contact generation is to calculate points of contact, and for each point, a contact normal.
My implementation involves an extension of our NarrowPhase collision code...
We already know that our pair of bodies have been integrated to our best estimate of the moment of contact.
Penetrations, if any, are minimal.
If the primitives collide, or if they intersect, we wish to know where and how.

Posted on 2009-03-19 01:00:41 by Homer
We'll take a look at the entire collision detection algo from start to finish, sorry its taking so long but I keep finding things to improve and I'd rather post stuff I'm happy with than repeat myself in variations.

Basically I've divided the NarrowPhase code into two categories - fast testing for separation / penetration / collision of two bodies (with early-outs for fastest possible response) and thorough searching for Contacts (which can be resolved inline, as long as we accumulate the response deltas until all simultaneous contacts are resolved).

I am tempted to collect Contacts into a proper 'Manifold', however I see no runtime benefit from doing so - its merely a courtesy and so I'll probably refrain from that and simply resolve contacts as I detect them as mentioned above.

Anyway, personally I find it very nice to be monkeying around with the whole collision detection process, based on existing and working code, because I believe that the biggest speedups will be obtained by using better algorithms, rather than optimizing inferior ones.
Posted on 2009-03-20 01:01:29 by Homer
I've just rewritten my Triangle/Triangle test for the fourth time.
Previous versions have been based on existing algorithms (Moller etc).
The new version is my own, it is the culmination of my preconceptions and my observations of existing algorithms.
That is to say - I threw everything away and went back to one of my own early ideas.
This seems to be a recurring theme, perhaps I have a natural affinity to geometric calculation.

Anyway, here's some pseudocode that describes my new test for separation of two triangles, given as Faces in their respective BodySpaces:

-Transform both Faces into WorldSpace
-Calculate Plane of triangle #1
-Classify the Points of triangle #2 against the Plane of triangle #1
-If the three resulting Point/Plane Distances are positive, return Clear
-If one or two points are Coplanar and the other(s) positive, test whether the coplanar point(s) are inside triangle #1, and if so, return Colliding, else return Clear
-return Penetrating

This algorithm clearly defines the classifications 'Clear, Colliding and Penetrating'.
Clear means the triangles are separated, and are in front of one another.
Colliding means the triangles are touching, and are in front of one another.
Anything else means they are Penetrating, regardless of penetration depth.

As with all the NarrowPhase (separation) tests, I have written a more thorough variant which generates Contacts between the triangles. I will describe this in my next post, then we'll begin looking over the entire collision detection pipeline.

Pipeline makes it sound really technical, but each stage is relatively simple by itself so don't worry too much about that buzzword, I'm simply referring to the fact that there ARE several linear stages.
Posted on 2009-03-26 00:43:25 by Homer
We wish to generate Contacts between a pair of triangles.
This is a structure that contains a Point of Impact, and a Collision Normal.
For our purposes, the Normal will always be that of the test Plane.

In order to generate Contacts between two triangles, we need to extend the previous algorithm.
It's worth thinking about the different ways that two triangles can interact, given the three categories of Clear, Colliding or Penetrating.

For collision cases (where one or more points of a triangle are coplanar with the other triangle and within the other triangles bounds) we wish to generate Contacts at those coplanar points of contact.

Penetration cases are more tricky... start by noting that two triangles always intersect in exactly two places... we need to identify which Edges of a triangle are intersecting the Plane of the other triangle, find proposed intersection points on the plane along each edge, check if each proposed intersection point is inside the other triangles bounds, and if so, generate a Contact at that point of intersection.
And depending on how the two triangles are intersecting, we might only find one Contact this way, and we'll need to perform all these tests with the triangles switched around to find the other one.

Then we have the special case of two coplanar triangles, which is solved by performing point-in-triangle tests.

And finally, the case of a deep penetration where all the points of a triangle are behind the plane of the other.
This should never arise, since we're meant to be in a Colliding, or Shallow Penetration situation.
So I won't generate contacts, I'll throw an error here.

In my next post, I'll present code for Separation Test and for Contact Generation.

Posted on 2009-03-26 22:06:20 by Homer
Here's the code which tests for Separation of two Triangles.
My next post will contain code for Contact Generation of two intersecting triangles.
Please note that neither of these functions have been tested in the engine yet, as they've been the subject of recent furious coding sessions and are thereby subject to further change without notice.

``;Test for Separation of two triangles (which belong to two mesh entities);Returns Penetrating,Colliding, or ClearMethod D3D_PhysicalEntity.Face_vs_Face,uses esi ,pEntityB,pFaceA,pFaceBLOCAL tmpLOCAL tri1:triangle, tri2:triangleLOCAL plane1:Vec4LOCAL E1:Vec3,E2:Vec3    SetObject esi    ;Transform the face from this body (FaceA) into worldspace (tri1)    OCall esi.Transform_Face_BodyToWorld,pFaceA,addr .NewState.Orientation,addr tri1    ;Transform the face from other body (pFaceB) into worldspace (tri2)    OCall pEntityB::CollisionBodyInstance.Transform_Face_BodyToWorld,pFaceB,addr .NewState.Orientation,addr tri2    ;compute plane of tri1    ;E1 = tri1[1] - tri1[0]    ;E2 = tri1[2] - tri1[0]    ;planeN = CrossProduct(E1,E2)    ;planeD = - Dotproduct(plane1,tri1[0])    Vec3_Sub   tri1.v1,tri1.v0    Vec3_Stow  E1    Vec3_Sub   tri1.v2,tri1.v0    Vec3_Stow  E2    Vec3_Cross E1,E2    Vec3_Stow  plane1    Vec3_Dot   plane1, tri1.v0    fchs    fstp plane1.w    ;Classify tri2 against plane1     invoke ClassifyTrianglePlane,addr tri2,addr plane1    ;Case 1: tri2 is completely clear of tri1's plane    .if eax==FRONTFRONTFRONT        return Clear    ;Case 2: One point of tri2 is touching the plane of tri1, the others are in front    .elseif eax==COPLANARFRONTFRONT        invoke PointInTriangle,addr tri1, addr tri2.v0        .if eax==TRUE            return Colliding        .endif        return Clear    .elseif eax==FRONTCOPLANARFRONT        invoke PointInTriangle,addr tri1, addr tri2.v1        .if eax==TRUE            return Colliding        .endif        return Clear    .elseif eax==FRONTFRONTCOPLANAR        invoke PointInTriangle,addr tri1, addr tri2.v2        .if eax==TRUE            return Colliding        .endif        return Clear            ;Case 3 : One edge of tri2 is touching the plane of tri1, the other point is infront    .elseif eax==FRONTCOPLANARCOPLANAR        xor edi,edi        invoke PointInTriangle,addr tri1, addr tri2.v1        .if eax==TRUE            return Colliding        .endif        invoke PointInTriangle,addr tri1, addr tri2.v2        .if eax==TRUE            return Colliding        .endif        return Clear    .elseif eax==COPLANARFRONTCOPLANAR         xor edi,edi        invoke PointInTriangle,addr tri1, addr tri2.v0        .if eax==TRUE            return Colliding        .endif        invoke PointInTriangle,addr tri1, addr tri2.v2        .if eax==TRUE            return Colliding        .endif        return Clear    .elseif eax==COPLANARCOPLANARFRONT        xor edi,edi        invoke PointInTriangle,addr tri1, addr tri2.v0        .if eax==TRUE            return Colliding        .endif        invoke PointInTriangle,addr tri1, addr tri2.v1        .if eax==TRUE            return Colliding        .endif        return Clear    .endif        mov eax,PenetratingMethodEnd``

I'm testing the points of the second triangle against the plane of the first triangle, via a procedure called 'ClassifyTrianglePlane', which returns a value that describes each point of the input triangle classified against the input plane,  such as FRONTFRONTCOPLANAR and BACKCOPLANARFRONT.
We return Clear, Colliding or Penetrating, based on the return value.

It certainly appears that in order to quickly determine whether the triangles are clear, colliding or penetrating, we only need to test the points of one triangle against the plane of the other triangle... we don't need to do this test again with the triangles switched about.... do we? Can you see any problems?
Posted on 2009-03-30 00:13:51 by Homer
Here's the code which generates Contacts between two triangles.
Its quite lengthy, but it executes quickly since its just a big bunch of IF cases.

``;This macro is used in the method below;for handling the special case of coplanar trianglesTestEdges macro vstart1,vend1,vstart2,vend2  .if \$invoke (Edge_intersect_Edge,addr vstart1,addr vend1,addr vstart2,addr vend2)==TRUE    Vec3_Stow vIntersection    OCall pContacts::Collection.Insert,\$New(Contact,Init,pPair,addr vIntersection,addr plane1)    inc numcontacts    .if numcontacts==6        return TRUE    .endif.endifendm;Generates Contacts;Returns TRUE (no more tests needed);or FALSE (need second call with triangles switched)Method D3D_PhysicalEntity.Face_Contact_Face,uses esi ,pEntityB,pFaceA,pFaceB,pPair,pContactsLOCAL tmpLOCAL tri1:triangle, tri2:triangleLOCAL plane1:Vec4LOCAL E1:Vec3,E2:Vec3LOCAL numcontactsLOCAL vIntersection:Vec3    SetObject esi    mov numcontacts,0    ;Transform the face from this body (FaceA) into worldspace (tri1)    OCall esi.Transform_Face_BodyToWorld,pFaceA,addr .NewState.Orientation,addr tri1    ;Transform the face from other body (pFaceB) into worldspace (tri2)    OCall pEntityB::CollisionBodyInstance.Transform_Face_BodyToWorld,pFaceB,addr .NewState.Orientation,addr tri2    ;compute plane of tri1    ;E1 = tri1[1] - tri1[0]    ;E2 = tri1[2] - tri1[0]    ;planeN = CrossProduct(E1,E2)    ;planeD = - Dotproduct(plane1,tri1[0])    Vec3_Sub   tri1.v1,tri1.v0    Vec3_Stow  E1    Vec3_Sub   tri1.v2,tri1.v0    Vec3_Stow  E2    Vec3_Cross E1,E2    Vec3_Stow  plane1    Vec3_Dot   plane1, tri1.v0    fchs    fstp plane1.w    ;Classify tri2 against plane1     invoke ClassifyTrianglePlane,addr tri2,addr plane1    .switch eax        ;Special case - triangles are coplanar    .case COPLANARCOPLANARCOPLANAR        ;We must test all Edges of each Tri against the other Tri's 3 edges        ;The maximum number of Contacts for two coplanar triangles is SIX.        ;Just imagine the 'Star of David' configuration of two triangles.          TestEdges tri1.v0,tri1.v1,tri2.v0,tri2.v1        TestEdges tri1.v0,tri1.v1,tri2.v1,tri2.v2        TestEdges tri1.v0,tri1.v1,tri2.v2,tri2.v0        TestEdges tri1.v1,tri1.v2,tri2.v0,tri2.v1        TestEdges tri1.v1,tri1.v2,tri2.v1,tri2.v2        TestEdges tri1.v1,tri1.v2,tri2.v2,tri2.v0        TestEdges tri1.v2,tri1.v0,tri2.v0,tri2.v1        TestEdges tri1.v2,tri1.v0,tri2.v1,tri2.v2        TestEdges tri1.v2,tri1.v0,tri2.v2,tri2.v0        return TRUE    ;Case 1: tri2 is completely clear of tri1's plane    .case FRONTFRONTFRONT        DbgWarning "Warning - Triangle pair is Clear"        return TRUE    ;Case 2: One point of tri2 is touching the plane of tri1, the others are in front    ;Test whether the coplanar point of tri2 is inside tri1    ;If so, generate a Contact there    ;This is a Terminal Case - no further tests are required    .case COPLANARFRONTFRONT        .if \$invoke (PointInTriangle,addr tri1, addr plane1,addr tri2.v0)==TRUE            OCall pContacts::Collection.Insert,\$New(Contact,Init,pPair,addr tri2.v0,addr plane1)        .endif        return TRUE    .case FRONTCOPLANARFRONT           .if \$invoke (PointInTriangle,addr tri1, addr plane1,addr tri2.v1)==TRUE            OCall pContacts::Collection.Insert,\$New(Contact,Init,pPair,addr tri2.v1,addr plane1)        .endif        return TRUE    .case FRONTFRONTCOPLANAR           .if \$invoke (PointInTriangle,addr tri1, addr plane1,addr tri2.v2)==TRUE            OCall pContacts::Collection.Insert,\$New(Contact,Init,pPair,addr tri2.v2,addr plane1)        .endif        return TRUE    ;Case 3 : One edge of tri2 is touching the plane of tri1, the other point is infront    ;test coplanar edge for intersection with 3 edges of tri1     ;until we have 2 contacts or run out of tests.    .case FRONTCOPLANARCOPLANAR        ;find intersections of coplanar edge and edges of t1        invoke Edge_intersect_Edge,addr tri2.v1,addr tri2.v2,addr tri1.v0,addr tri1.v1        .if eax==TRUE            Vec3_Stow vIntersection            OCall pContacts::Collection.Insert,\$New(Contact,Init,pPair,addr vIntersection,addr plane1)            inc numcontacts        .endif        invoke Edge_intersect_Edge,addr tri2.v1,addr tri2.v2,addr tri1.v1,addr tri1.v2        .if eax==TRUE            Vec3_Stow vIntersection            OCall pContacts::Collection.Insert,\$New(Contact,Init,pPair,addr vIntersection,addr plane1)            inc numcontacts            .if numcontacts==2                return TRUE            .endif        .endif        invoke Edge_intersect_Edge,addr tri2.v1,addr tri2.v2,addr tri1.v2,addr tri1.v0        .if eax==TRUE            Vec3_Stow vIntersection            OCall pContacts::Collection.Insert,\$New(Contact,Init,pPair,addr vIntersection,addr plane1)        .endif        return TRUE            .case COPLANARCOPLANARFRONT        invoke Edge_intersect_Edge,addr tri2.v0,addr tri2.v1,addr tri1.v0,addr tri1.v1        .if eax==TRUE            Vec3_Stow vIntersection            OCall pContacts::Collection.Insert,\$New(Contact,Init,pPair,addr vIntersection,addr plane1)            inc numcontacts        .endif        invoke Edge_intersect_Edge,addr tri2.v0,addr tri2.v1,addr tri1.v1,addr tri1.v2        .if eax==TRUE            Vec3_Stow vIntersection            OCall pContacts::Collection.Insert,\$New(Contact,Init,pPair,addr vIntersection,addr plane1)            inc numcontacts            .if numcontacts==2                return TRUE            .endif        .endif        invoke Edge_intersect_Edge,addr tri2.v0,addr tri2.v1,addr tri1.v2,addr tri1.v0        .if eax==TRUE            Vec3_Stow vIntersection            OCall pContacts::Collection.Insert,\$New(Contact,Init,pPair,addr vIntersection,addr plane1)        .endif        return TRUE            .case COPLANARFRONTCOPLANAR         invoke Edge_intersect_Edge,addr tri2.v2,addr tri2.v0,addr tri1.v0,addr tri1.v1        .if eax==TRUE            Vec3_Stow vIntersection            OCall pContacts::Collection.Insert,\$New(Contact,Init,pPair,addr vIntersection,addr plane1)            inc numcontacts        .endif        invoke Edge_intersect_Edge,addr tri2.v2,addr tri2.v0,addr tri1.v1,addr tri1.v2        .if eax==TRUE            Vec3_Stow vIntersection            OCall pContacts::Collection.Insert,\$New(Contact,Init,pPair,addr vIntersection,addr plane1)            inc numcontacts            .if numcontacts==2                return TRUE            .endif        .endif        invoke Edge_intersect_Edge,addr tri2.v2,addr tri2.v0,addr tri1.v2,addr tri1.v0        .if eax==TRUE            Vec3_Stow vIntersection            OCall pContacts::Collection.Insert,\$New(Contact,Init,pPair,addr vIntersection,addr plane1)        .endif        return TRUE            ;Case 4 : One point of tri2 is touching the plane of tri1, the others are behind    ;Test whether coplanar point is inside tri1    ;If so, Generate contacts for the two Penetrating points     .case COPLANARBACKBACK        .if \$invoke (PointInTriangle,addr tri1, addr plane1,addr tri2.v0)==TRUE            OCall pContacts::Collection.Insert,\$New(Contact,Init,pPair,addr tri2.v1,addr plane1)            OCall pContacts::Collection.Insert,\$New(Contact,Init,pPair,addr tri2.v2,addr plane1)        .endif        return TRUE       .case BACKCOPLANARBACK        .if \$invoke (PointInTriangle,addr tri1, addr plane1,addr tri2.v1)==TRUE            OCall pContacts::Collection.Insert,\$New(Contact,Init,pPair,addr tri2.v1,addr plane1)            OCall pContacts::Collection.Insert,\$New(Contact,Init,pPair,addr tri2.v2,addr plane1)        .endif        return TRUE    .case BACKBACKCOPLANAR        .if \$invoke (PointInTriangle,addr tri1, addr plane1,addr tri2.v2)==TRUE            OCall pContacts::Collection.Insert,\$New(Contact,Init,pPair,addr tri2.v1,addr plane1)            OCall pContacts::Collection.Insert,\$New(Contact,Init,pPair,addr tri2.v2,addr plane1)        .endif        return TRUE                    ;Case 5 : One edge of tri2 is touching the plane of tri1, the other point is behind    ;Generate a single contact for the penetrating point    .case BACKCOPLANARCOPLANAR        OCall pContacts::Collection.Insert,\$New(Contact,Init,pPair,addr tri2.v0,addr plane1)        ret    .case COPLANARBACKCOPLANAR        ;Generate one contact for the Penetrating point        OCall pContacts::Collection.Insert,\$New(Contact,Init,pPair,addr tri2.v1,addr plane1)        ret    .case COPLANARCOPLANARBACK        OCall pContacts::Collection.Insert,\$New(Contact,Init,pPair,addr tri2.v2,addr plane1)        ret            ;Case 6 : One point is coplanar, the other two lay each side of the plane    ;Check coplanar Point and spanning Edge    .case BACKCOPLANARFRONT        invoke PointInTriangle,addr tri1, addr plane1,addr tri2.v1        .if eax==TRUE            OCall pContacts::Collection.Insert,\$New(Contact,Init,pPair,addr tri2.v1,addr plane1)        .endif        invoke Edge_intersect_Plane,addr tri2.v2,addr tri2.v0,addr plane1,addr tri1.v0        .if eax==TRUE            Vec3_Stow vIntersection            invoke PointInTriangle,addr tri1, addr plane1,addr vIntersection                     .if eax==TRUE                OCall pContacts::Collection.Insert,\$New(Contact,Init,pPair,addr vIntersection,addr plane1)                ret            .endif          .endif                  .case FRONTCOPLANARBACK        invoke PointInTriangle,addr tri1,addr plane1, addr tri2.v1        .if eax==TRUE            OCall pContacts::Collection.Insert,\$New(Contact,Init,pPair,addr tri2.v1,addr plane1)        .endif        invoke Edge_intersect_Plane,addr tri2.v0,addr tri2.v2,addr plane1, addr tri1.v0        .if eax==TRUE            Vec3_Stow vIntersection            invoke PointInTriangle,addr tri1,addr plane1, addr vIntersection                     .if eax==TRUE                OCall pContacts::Collection.Insert,\$New(Contact,Init,pPair,addr vIntersection,addr plane1)                ret            .endif        .endif            .case COPLANARFRONTBACK        invoke PointInTriangle,addr tri1,addr plane1, addr tri2.v0        .if eax==TRUE            OCall pContacts::Collection.Insert,\$New(Contact,Init,pPair,addr tri2.v0,addr plane1)        .endif        invoke Edge_intersect_Plane,addr tri2.v1,addr tri2.v2,addr plane1,addr tri1.v0        .if eax==TRUE            Vec3_Stow vIntersection            invoke PointInTriangle,addr tri1,addr plane1, addr vIntersection                     .if eax==TRUE                OCall pContacts::Collection.Insert,\$New(Contact,Init,pPair,addr vIntersection,addr plane1)                ret            .endif        .endif            .case COPLANARBACKFRONT        invoke PointInTriangle,addr tri1, addr plane1,addr tri2.v0        .if eax==TRUE            OCall pContacts::Collection.Insert,\$New(Contact,Init,pPair,addr tri2.v0,addr plane1)        .endif        invoke Edge_intersect_Plane,addr tri2.v2,addr tri2.v1,addr plane1,addr tri1.v0        .if eax==TRUE            Vec3_Stow vIntersection            invoke PointInTriangle,addr tri1,addr plane1, addr vIntersection                     .if eax==TRUE                OCall pContacts::Collection.Insert,\$New(Contact,Init,pPair,addr vIntersection,addr plane1)                ret            .endif                .endif    .case FRONTBACKCOPLANAR        invoke PointInTriangle,addr tri1,addr plane1, addr tri2.v2        .if eax==TRUE            OCall pContacts::Collection.Insert,\$New(Contact,Init,pPair,addr tri2.v2,addr plane1)        .endif        invoke Edge_intersect_Plane,addr tri2.v0,addr tri2.v1,addr plane1,addr tri1.v0        .if eax==TRUE            Vec3_Stow vIntersection            invoke PointInTriangle,addr tri1,addr plane1, addr vIntersection                     .if eax==TRUE                OCall pContacts::Collection.Insert,\$New(Contact,Init,pPair,addr vIntersection,addr plane1)                ret            .endif        .endif    .case BACKFRONTCOPLANAR        invoke PointInTriangle,addr tri1,addr plane1, addr tri2.v2        .if eax==TRUE            OCall pContacts::Collection.Insert,\$New(Contact,Init,pPair,addr tri2.v2,addr plane1)        .endif        invoke Edge_intersect_Plane,addr tri2.v1,addr tri2.v0,addr plane1,addr tri1.v0        .if eax==TRUE            Vec3_Stow vIntersection            invoke PointInTriangle,addr tri1,addr plane1, addr vIntersection                     .if eax==TRUE                OCall pContacts::Collection.Insert,\$New(Contact,Init,pPair,addr vIntersection,addr plane1)                ret            .endif        .endif            ;Case 7: triangle intersection    .case FRONTBACKBACK        ;check edges AB and AC        invoke Edge_intersect_Plane,addr tri2.v0,addr tri2.v1,addr plane1,addr tri1.v0        .if eax==TRUE            Vec3_Stow vIntersection            invoke PointInTriangle,addr tri1,addr plane1, addr vIntersection                     .if eax==TRUE                OCall pContacts::Collection.Insert,\$New(Contact,Init,pPair,addr vIntersection,addr plane1)                ret            .endif        .endif        invoke Edge_intersect_Plane,addr tri2.v0,addr tri2.v2,addr plane1,addr tri1.v0        .if eax==TRUE            Vec3_Stow vIntersection            invoke PointInTriangle,addr tri1, addr plane1,addr vIntersection                     .if eax==TRUE                OCall pContacts::Collection.Insert,\$New(Contact,Init,pPair,addr vIntersection,addr plane1)                ret            .endif        .endif    .case BACKFRONTFRONT        ;check edges BA and CA        invoke Edge_intersect_Plane,addr tri2.v1,addr tri2.v0,addr plane1,addr tri1.v0        .if eax==TRUE            Vec3_Stow vIntersection            invoke PointInTriangle,addr tri1, addr plane1,addr vIntersection                     .if eax==TRUE                OCall pContacts::Collection.Insert,\$New(Contact,Init,pPair,addr vIntersection,addr plane1)                ret            .endif        .endif        invoke Edge_intersect_Plane,addr tri2.v2,addr tri2.v0,addr plane1,addr tri1.v0        .if eax==TRUE            Vec3_Stow vIntersection            invoke PointInTriangle,addr tri1, addr plane1,addr vIntersection                     .if eax==TRUE                OCall pContacts::Collection.Insert,\$New(Contact,Init,pPair,addr vIntersection,addr plane1)                ret            .endif        .endif            .case FRONTBACKFRONT        ;check edges AB and CB        invoke Edge_intersect_Plane,addr tri2.v0,addr tri2.v1,addr plane1,addr tri1.v0        .if eax==TRUE            Vec3_Stow vIntersection            invoke PointInTriangle,addr tri1, addr plane1,addr vIntersection                     .if eax==TRUE                OCall pContacts::Collection.Insert,\$New(Contact,Init,pPair,addr vIntersection,addr plane1)                ret            .endif        .endif        invoke Edge_intersect_Plane,addr tri2.v2,addr tri2.v1,addr plane1,addr tri1.v0        .if eax==TRUE            Vec3_Stow vIntersection            invoke PointInTriangle,addr tri1,addr plane1, addr vIntersection                     .if eax==TRUE                OCall pContacts::Collection.Insert,\$New(Contact,Init,pPair,addr vIntersection,addr plane1)                ret            .endif        .endif    .case BACKFRONTBACK        ;check edges BA and BC        invoke Edge_intersect_Plane,addr tri2.v1,addr tri2.v0,addr plane1,addr tri1.v0        .if eax==TRUE            Vec3_Stow vIntersection            invoke PointInTriangle,addr tri1,addr plane1, addr vIntersection                     .if eax==TRUE                OCall pContacts::Collection.Insert,\$New(Contact,Init,pPair,addr vIntersection,addr plane1)                ret            .endif        .endif        invoke Edge_intersect_Plane,addr tri2.v1,addr tri2.v2,addr plane1,addr tri1.v0        .if eax==TRUE            Vec3_Stow vIntersection            invoke PointInTriangle,addr tri1,addr plane1, addr vIntersection                     .if eax==TRUE                OCall pContacts::Collection.Insert,\$New(Contact,Init,pPair,addr vIntersection,addr plane1)                ret            .endif        .endif            .case FRONTFRONTBACK        ;check edges BC and AC        invoke Edge_intersect_Plane,addr tri2.v1,addr tri2.v2,addr plane1,addr tri1.v0        .if eax==TRUE            Vec3_Stow vIntersection            invoke PointInTriangle,addr tri1,addr plane1, addr vIntersection                     .if eax==TRUE                OCall pContacts::Collection.Insert,\$New(Contact,Init,pPair,addr vIntersection,addr plane1)                ret            .endif        .endif        invoke Edge_intersect_Plane,addr tri2.v0,addr tri2.v2,addr plane1,addr tri1.v0        .if eax==TRUE            Vec3_Stow vIntersection            invoke PointInTriangle,addr tri1,addr plane1, addr vIntersection                     .if eax==TRUE                OCall pContacts::Collection.Insert,\$New(Contact,Init,pPair,addr vIntersection,addr plane1)                ret            .endif        .endif    .case BACKBACKFRONT        ;check edges CB and CA        invoke Edge_intersect_Plane,addr tri2.v2,addr tri2.v1,addr plane1,addr tri1.v0        .if eax==TRUE            Vec3_Stow vIntersection            invoke PointInTriangle,addr tri1,addr plane1, addr vIntersection                     .if eax==TRUE                OCall pContacts::Collection.Insert,\$New(Contact,Init,pPair,addr vIntersection,addr plane1)                ret            .endif        .endif        invoke Edge_intersect_Plane,addr tri2.v2,addr tri2.v0,addr plane1,addr tri1.v0        .if eax==TRUE            Vec3_Stow vIntersection            invoke PointInTriangle,addr tri1,addr plane1, addr vIntersection                     .if eax==TRUE                OCall pContacts::Collection.Insert,\$New(Contact,Init,pPair,addr vIntersection,addr plane1)                ret            .endif        .endif            .default        DbgWarning "Unhandled case in Face_Contact_Face"        DbgDec eax,"unhandled switch"        int 3    .endswMethodEnd``

As you can see, testing for separation and finding contacts for just a PAIR OF TRIANGLES is quite intensive, so doing this for two GROUPS of triangles is just out of the question... this is why we extended the BSP algorithm so that the leaf nodes contain no more than one triangle - its cheaper to walk a few tree nodes and test several pairs of triangles than it is to exhaustively test a pair of convex clusters of triangles.

I'm not going to discuss the above code too much, I'll leave it to you to examine and tell me if you think (as I do) that we don't need to call this function again with the triangles switched around - this version handles all cases in a single call.

I'm going to assume there's no problems in the above code, and move on.
I did say the code was subject to change without notice :P

I think we're ready to look over the entire collision detection pipeline from start to finish :)
Posted on 2009-04-02 23:49:36 by Homer
For those brave enough, I've attached a file which contains the core functions for intersection calculations.
Posted on 2009-04-02 23:59:59 by Homer
And here's an update of what the engine layout looks like:

Posted on 2009-04-03 00:25:16 by Homer
It's time to take a look at the entire collision detection pipeline.
We'll begin with the Simulator.Simulate method.
Its purpose is to attempt to advance the simulation by one timestep or less, by calculating the 'new state' of the physics simulation
(ie the new physical state of every physical entity), to detect (and collect) collisions within the current timestep, and if collisions were detected, to resolve them, leaving the simulation at the last known moment of contact.
This method returns (on the fpu) the time delta by which the simulation has been advanced (one timestep, or less).
We can consider this as the entrypoint to the collision detection code.

``;This method will attempt to advance the simulation by one whole TimeStep.;When this method returns, the States of all Bodies have been Swapped,;so that the 'current state' is the OLD state, and the 'next state' is UNKNOWN.;It will return (on the fpu) the deltaTime that the Simulation should advance to.;This is between zero (collisions at end of timestep);and PhysicsTimeStep (no collisions, or collisions at start of timestep).Method Simulator.Simulate,uses esi    SetObject esi    DbgLine    ;Integrate our system forward by one whole timestep    ;We are calculating the 'New States' from 'Old States' after 'deltaTime'    OCall Integrate, PhysicsTimeStep    ;If enabled, perform collision detection and resolution..    .if .IsCollisionEnabled==TRUE        OCall esi.DetectCollisions        .if eax==TRUE            ;This method returns the time we are allowed to advance by...            ;It can be as much as one PhysicsTimeStep            ;(either NO collisions occurred, or collisions were at Time Zero)            ;or it can be as little as Zero            ;(collisions detected at the very end of the timestep)            OCall esi.ResolveCollisions        .else            fld PhysicsTimeStep        .endif            OCall esi.SwapStates       .else        OCall esi.SwapStates        fld PhysicsTimeStep    .endifMethodEnd``

Since I've posted the Integrate method previously, we'll just turn our attention to the DetectCollisions and ResolveCollisions methods.

Posted on 2009-04-05 03:29:09 by Homer
Let's ignore collision response for now, and concentrate on collision detection.

The Simulator.DetectCollisions method operates apon the premise that we know the BoundingSphere of every physical entity, regardless of the shape we choose to represent its collision hull.
It tests pairs of Spheres using a 'swept algorithm' that boils down to solving a Quadratic Equation.
It can tell if the boundingspheres of two entities will collide within the current timestep, and if so, when.... all this happens within the 'BroadCheck_BodyBody' method.
If sphere/sphere collision is detected, we perform a binary search for the exact moment of impact of the two bodies, using whatever collision hulls were selected.
Given that we know the moment of impact for the sphere pairs is within the current timestep, finding the exact time by exhaustive bisection is fairly quick.
We're returned either the exact time of impact, or a time where the penetration is known to be smallest, and in this case the penetration depth is returned too.
All of this information is recorded as a 'CollisionPair' object, which is just a database record being stored in a list, with automatic sorting of the list based on time of impact.
We record all the CollisionPairs that we can find within the current timestep, and return to the caller.

``;This method detects & collects all Collisions in the current TimeStep,;and sorts them by 'Time of Impact'.;Returns TRUE (found one or more collisions) or FALSE (no collisions found);Note: this method deals with INSTANCES of collision bodies.Method Simulator.DetectCollisions,uses esiLOCAL pBodyA,pBodyBLOCAL fCollisionTime:real8LOCAL fdepth:real8LOCAL FoundCollisions    SetObject esi            xor ecx,ecx    mov FoundCollisions,ecx         ;FALSE    .while ecx<.Bodies.dCount        push ecx                mov pBodyA,\$OCall (.Bodies::Collection.ItemAt,ecx)                ;Body A is considered to be the 'aggressor' during collision tests,        ;which implies that it must be free to move, and actually be moving.                .if .CollisionBodyInstance.IsStatic==FALSE && .CollisionBodyInstance.IsAwake==TRUE            ;Compare BodyA against all bodies FURTHER along the list            ;This ensures that we are only testing UNIQUE PAIRS            pop ecx            push ecx            inc ecx            .while ecx<.Bodies.dCount                push ecx                                ;For collision testing, we don't care if BodyB is static or asleep.                ;We just want to know if BodyA collided with it.                OCall .Bodies::Collection.ItemAt,ecx                                ;Make sure this CollisionPair does not already exist in the list...                ;This can ONLY happen if the list stays full through N timesteps                ;which in the current version of the code does not happen...                OCall .CollisionPairs::CollisionPairList.FindCollisionPair,pBodyA,pBodyB                .if eax==NULL                                     ;Sweep the Spheres                    OCall BroadCheck_BodyBody,pBodyA,pBodyB                    .if eax==TRUE                        fmul PhysicsTimeStep                        fstp fCollisionTime                                                ;Find the exact moment of impact (if any)                        or FoundCollisions,\$OCall (esi.FindExactCollisionTime,pBodyA,pBodyB)                        .if eax==Colliding                                                    fstp fCollisionTime                            fldz                            fstp fdepth                            ;Make a new CollisionPair record                            OCall .CollisionPairs::CollisionPairList.Insert,\$New (CollisionPair)                            OCall eax::CollisionPair.Init,pBodyA,pBodyB,fCollisionTime,fdepth                        .elseif eax==Penetrating                            fstp fCollisionTime                            fstp fdepth                            ;Make a new CollisionPair record                            OCall .CollisionPairs::CollisionPairList.Insert,\$New (CollisionPair)                            OCall eax::CollisionPair.Init,pBodyA,pBodyB,fCollisionTime,fdepth                        .endif                                            .endif                                    .endif                pop ecx                inc ecx            .endw        .endif        pop ecx        inc ecx    .endw        mov eax,FoundCollisionsMethodEnd``

Now we have a sorted list of CollisionPair records.
We've detected all the collisions between pairs of entities within the current timestep.
We know which pairs collided, and when.
This is important because we can expect simultaneous collisions to occur.
The ResolveCollisions method must be prepared to cope with sets of CollisionPair records which have the same Time Of Impact, and handle them simultaneously.
Posted on 2009-04-05 04:21:04 by Homer
It's worth noting that the FindExactCollisionTime method also weeds out 'false positives' - cases where a pair of boundingspheres collide, but the geometric entities inside those spheres never actually collide (ie a 'near miss').

Now that we've covered the first half of the collision detection (broadphase : identifying which pairs of entities truly do collide, and at what time they first touch), we can take a look at the ResolveCollisions method, then we'll go back to look more closely at the NarrowPhase collision detection (which is called from FindExactCollisionTime).

``;This method will detect and resolve collisions 'continuously';until collisions fall outside the scope of the hardcoded physics timestep.;Returns FPU = last known moment of impact within the current timestep;(which is the most that we can advance the simulation)Method Simulator.ResolveCollisions,uses esiLOCAL fTimeTotal:real8,fTimeTemp:real8LOCAL pPair    SetObject esi    DbgWarning "Resolving Collisions"    fld PhysicsTimeStep    fstp fTimeTotal            DbgDec .CollisionPairs.dCount    .while .CollisionPairs.dCount!=0            ;Peek at the first CollisionPair on the sorted list        OCall .CollisionPairs::CollisionPairList.ItemAt,NULL                ;Break if the collision time is outside the original scope of one physics timestep        fld fTimeTotal        fld .CollisionPair.CollisionTime        fst fTimeTemp        fsub        fstReg edx        .ifBitSet edx,BIT31             ;This collision event is during the next TimeFrame            DbgWarning "Breaking because CollisionTime is outside scope of TimeStep"            DbgWarning "How the heck did that happen?"            DbgFloat edx            int 3            .break        .endif        fstp fTimeTotal          ;Grab the first CollisionPair on the sorted list         mov pPair,\$OCall (.CollisionPairs::CollisionPairList.DeleteAt,NULL)        ;Integrate the system to the earliest collision time        fld fTimeTemp        fstpReg edx        .if edx==0 || edx==80000000h            DbgWarning "Collision at TIME ZERO - Special Case"            int 3        .else            DbgWarning "Integrating to Time Of Impact"            OCall esi.Integrate, fTimeTemp        .endif                     ;Calculate the Collision Response        ;We will accumulate deltas of lin velocity and ang momentum        OCall esi.CollisionResponse,pPair                ;Add the two entities to an output list of         ;all unique entities which were involved in collisions.              mov ebx,pPair        OCall .CollidedBodies::DwordCollection.Insert, .CollisionPair.pBodyA        OCall .CollidedBodies::DwordCollection.Insert, .CollisionPair.pBodyB                ;Release the CollisionPair        Destroy pPair  @more:               ;Loop for all CollisionPairs with the same Collision Time (simultaneous collision)        .while .CollisionPairs.dCount!=0            ;Peek at the next item on the list            OCall .CollisionPairs::CollisionPairList.ItemAt,NULL            ;Break if the next collision time is greater            fld fTimeTemp            fsub .CollisionPair.CollisionTime            fstpReg edx            .ifBitSet edx,BIT31                .break            .endif            ;Grab the next item from the list            mov pPair,\$OCall (.CollisionPairs::CollisionPairList.DeleteAt,NULL)                        ;Calculate the Collision Response            ;We will accumulate deltas of lin velocity and ang momentum            OCall esi.CollisionResponse,pPair                        ;Add the CollisionPair to list of CollidedBodies                    mov ebx,pPair            OCall .CollidedBodies::DwordCollection.Insert, .CollisionPair.pBodyA            OCall .CollidedBodies::DwordCollection.Insert, .CollisionPair.pBodyB                               .endw         ;Subtract the earliest collision time from all remaining pairs        xor ebx,ebx        .while ecx<.CollisionPairs.dCount            OCall .CollisionPairs::CollisionPairList.ItemAt,ebx            fld .CollisionPair.CollisionTime            fsub fTimeTemp            fstp .CollisionPair.CollisionTime        .endw                                ;Apply the collision impulse deltas and swap the body states        ;of all bodies which were involved in collisions.        ;This exhausts the CollidedBodies collection.        OCall ApplyResponse, addr .CollidedBodies                ;Check if the collision event causes subsequent collisions    ;    OCall esi.DetectCollisions                               ;Repeat until no collision pairs remain, or collisions are outside the current timestep    .endw        DbgWarning "Resolved"        ;Return the time of the last known collision    DbgWarning "Last known collision time:"    DbgFloat fTimeTotal    fld fTimeTotalMethodEnd``

This method exhausts the list of CollisionPairs, advancing the simulation to each Time Of Impact, resolving all collisions at that Time, then advancing to the next Time Of Impact, and so on, until the list of CollisionPairs is exhausted.
If it finds a series of CollisionPairs with the same Time Of Impact, it processes them as a group, creating a list of entities which have been involved in collisions.
Collision Responses are calculated (as delta velocity and delta angular momentum), and are applied to each complete list of simultaneously-colliding entities.

This function could use some work...
Currently, I have commented out a line which causes a recursive test for any further Collisions which are the direct result of our resolving of collisions... ie, where a body involved in a collision bounces off into some other body, causing a subsequent collision.
I'm trying to decide how best to deal with this, however its nice to know that we're able to take advantage of our cache of CollisionPairs, we don't need to test CollisionPairs that are already cached.

In my next post, we'll look at the Simulator.CollisionResponse method, then we'll look deeper into the NarrowPhase collision detection.
Posted on 2009-04-05 21:32:35 by Homer
Attached is an image which shows the layout of the collision detection pipeline.
It should help some of you to better understand how the pieces fit together.

Posted on 2009-04-06 02:42:32 by Homer

Here's the Simulator.CollisionResponse method.
We'll notice that the Simulator supports a global list of Contacts.
After we've looked at the attached code, we'll also notice that this list is temporary - I'm simply avoiding destroying/recreating of this temp list by recycling the same collection object.

``;Generates / Resolves all contacts for a CollisionPair	Method Simulator.CollisionResponse, uses esi ebx, pCollisionPair	SetObject esi    DbgWarning "Simulator.CollisionResponse"        ;Build a list of Contacts between the bodies in this CollisionPair    OCall esi.GenerateContacts, pCollisionPair        ;Resolve all the Contacts    .while .Contacts.dCount != 0        OCall .Contacts::Collection.DeleteAt,0        push eax        ;Resolve the Contact        OCall esi.ResolveContact, eax        ;Destroy the Contact - this version does not support Contact Caching...        ;If we keep Contacts across Frames, we can find 'Rests' and 'Supports'.        ;That's for a future version :)        pop eax        Destroy eax    .endwMethodEnd``

Given a CollisionPair (which have been integrated to the Time Of Impact), this method will generate a set of simultaneous Contacts between these two Bodies, and it will calculate a response impulse for each contact, and the resulting changes to the linear velocity and angular momentum of each Body, accumulating these Deltas in the Bodies, but not Applying them to the physical state of the bodies.

I'm not going to delve too deeply into the calculation of physical response because I'd rather continue to examine the collision detection stuff. However if you're really interested, you can ask :)

So how exactly do we find the set of contacts for a collision between two bodies?
The next post will contain the code for the Simulator.GenerateContacts method.
Posted on 2009-04-06 03:04:02 by Homer

Here is the Simulator.GenerateContacts method.
Given a CollisionPair, it will generate a set of Contacts between the two colliding bodies.
The code presented only handles Sphere/Sphere, Sphere/Mesh and Mesh/Mesh collisions.
I expect to support a number of other collision hulls, including geometric primitives (box, cylinder etc) and complex Convex Hulls. Some code already exists with this in mind.

``;A Pair of bodies are known to Collide at our best estimate of the Moment of Impact.;We have integrated these Bodies to that moment in Time.;This method detects and collects a list of Contacts between this Pair of bodies.Method Simulator.GenerateContacts,uses esi,pCollisionPairLOCAL pBodyInstanceA,pBodyInstanceBlocal vAB:Vec3LOCAL vContactPoint:Vec3    SetObject esi    ;The test function will be determined by the type of bounding hulls involved.    mov eax,pCollisionPair    m2m pBodyInstanceA,.CollisionPair.pBodyA, eax    mov eax,.CollisionBodyInstance.pOwner    .switch .CollisionBody.dShapeID        .case SHAPEID_SPHERE        mov eax,pCollisionPair        m2m pBodyInstanceB,.CollisionPair.pBodyB,eax        mov eax,.CollisionBodyInstance.pOwner        .switch .CollisionBody.dShapeID                .case SHAPEID_SPHERE            ;In the case of two Spheres, there is only one Contact to consider,            ;and it is rather trivial to calculate the Position and Contact Normal.            mov edx,pBodyInstanceB            mov eax,pBodyInstanceA            Vec3_Sub .CollisionBodyInstance.NewState.vPosition, .CollisionBodyInstance.NewState.vPosition            Vec3_Stow vAB            Vec3_Normalize vAB  ;nomalized direction from sphere a to sphere b            mov eax,pBodyInstanceA            mov edx,.CollisionBodyInstance.pOwner            Vec3_Scale vAB,.CollisionBody.fRadius            Vec3_AddFrom .CollisionBodyInstance.NewState.vPosition            Vec3_Stow vContactPoint            OCall .Contacts::Collection.Insert,\$New(Contact,Init,pCollisionPair,addr vContactPoint,addr vAB)        .case SHAPEID_MESH            ;SPHERE versus MESH            ;Usually there will just be one Contact, but there COULD be more.            ;Let's search the Mesh's BVH Tree for Triangles which are            ;either Touching or Intersecting the Sphere.            OCall pBodyInstanceB::CollisionBodyInstance.Find_Contacts_versus_Sphere,pBodyInstanceA,pCollisionPair,addr .Contacts                    .default            DbgWarning "Unhandled BodyShape B in GenerateContacts"                .endsw            .case SHAPEID_MESH        mov eax,pBodyInstanceB        mov eax,.CollisionBodyInstance.pOwner        .switch .CollisionBody.dShapeID        .case SHAPEID_SPHERE            ;MESH versus SPHERE            ;We know how to handle this one, yes?            OCall pBodyInstanceA::CollisionBodyInstance.Find_Contacts_versus_Sphere,pBodyInstanceB,pCollisionPair,addr .Contacts                    .case SHAPEID_MESH            ;MESH versus MESH            ;Search both BVH Trees for all Contacts.            OCall pBodyInstanceA::CollisionBodyInstance.Find_Contacts_versus_Mesh,pBodyInstanceB,pCollisionPair,addr .Contacts                    .default            DbgWarning "Unhandled BodyShape B in GenerateContacts"                .endsw            .default        DbgWarning "Unhandled BodyShape A in GenerateContacts"        int 3    .endsw    MethodEnd``

We can see that the Sphere/Sphere case is trivial... one Contact is generated on the surface of Sphere A , and in the direction of Sphere B.
Next, we'll continue deeper, looking at the code for Mesh/Sphere and Mesh/Mesh contact generation.
Posted on 2009-04-06 06:20:19 by Homer