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, pOtherEntity
LOCAL 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 Clear
Method D3D_PhysicalEntity.Face_vs_Face,uses esi ,pEntityB,pFaceA,pFaceB
LOCAL tmp
LOCAL tri1:triangle, tri2:triangle
LOCAL plane1:Vec4
LOCAL 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,Penetrating
MethodEnd



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 triangles
TestEdges 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
.endif
endm

;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,pContacts
LOCAL tmp
LOCAL tri1:triangle, tri2:triangle
LOCAL plane1:Vec4
LOCAL E1:Vec3,E2:Vec3
LOCAL numcontacts
LOCAL 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
    .endsw

MethodEnd


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.
Attachments:
Posted on 2009-04-02 23:59:59 by Homer
And here's an update of what the engine layout looks like:

Attachments:
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
    .endif


MethodEnd


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 esi
LOCAL pBodyA,pBodyB
LOCAL fCollisionTime:real8
LOCAL fdepth:real8
LOCAL 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,FoundCollisions
MethodEnd


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 esi
LOCAL fTimeTotal:real8,fTimeTemp:real8
LOCAL 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 fTimeTotal
MethodEnd



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.

Attachments:
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
    .endw
MethodEnd


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,pCollisionPair
LOCAL pBodyInstanceA,pBodyInstanceB
local vAB:Vec3
LOCAL 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