In this post, I'll provide code for Separation Test of a Sphere and an arbitrary Mesh.
The following post will contain code for Contact Generation of a Sphere/Mesh pair.

As mentioned previously, I use a special kind of Tree for accelerating collision detection against arbitrary meshes. You'll see me calling them SphereTrees, and also BVH's (Bounding Volume Hierarchies).

The CollisionBodyInstance class (baseclass for the various collision shapes) defines several 'Dynamic Abstract' methods which are of interest to us - I'll list them below. These are placeholders for functions which are defined in classes which derive from CollisionBodyInstance... the abstracts we're interested in are:
versus_Sphere
versus_Mesh
Find_Contacts_versus_Sphere
Find_Contacts_versus_Mesh

Now if we look at the D3D_PhysicalEntity class, we can see some of these methods have been 'redefined' - and since they are 'dynamic', any calls to these methods in the Ancestor (CollisionBodyInstance) class are marshalled to those methods in the Derived classes.

We can redefine these methods in EACH derived class, so we can have 'box versus sphere', etc, just by 'overloading' the same method...
When we define D3D_PhysicalEntity.versus_Sphere, we're really defining a 'Mesh Versus Sphere' test.... hope this makes sense :)


Method D3D_PhysicalEntity.versus_Sphere,uses esi,pSphere
LOCAL vtemp:Vec3
    SetObject esi

    ;We will perform our tests in 'this body's space'
    ;(which is where we defined the BVH)
    ;so the triangles and their planes are all legal values
    ;(we avoid transforming the triangles and planes)
    ;Therefore we need to get the input Sphere into 'this space'.
   
    ;Transform the Origin of input Sphere
    ;from WorldSpace into 'this' bodyspace
    ;vtemp = Sphere's origin in 'this' space...
    mov edi,pSphere
    OCall esi.Transform_Vec3_WorldToBody, addr .CollisionBodyInstance.NewState.CMPosition,  addr .NewState.Orientation
    Vec3_Stow vtemp
       
    ;Pass the Root Node of the owner body's SphereTree to our recursive function
    mov edx,.pOwner
    OCall esi.Short_recurse_Sphere,pSphere,.D3D_CollisionMesh.pRootNode,addr vtemp
MethodEnd


Given a pointer to an entity that uses a spherical hull, and called apon an entity that uses a Mesh BVH, this method wraps a call to the recursive function (below).
We 'walk the tree', testing the input sphere against the boundingsphere described by each Tree Node, until we find Leaf Nodes whose boundingsphere intersects the input sphere.
Since our special Tree has Leaf nodes which contain One Triangle each, we can then test for intersection of the input sphere versus each Leaf triangle.
This function will terminate early if Penetration is detected.


;Recursive separation test of BoundingSphere and Mesh's BVH (using 'New' State)
;Test will exit as soon as penetration of a triangle is detected.
;pSphere = ptr to input CollisionBodyInstance (type = sphere)
;pNode   = ptr to input BSPNode (Node in SphereTree)
;pvOrigin= ptr to Vec3 containing Origin of input Sphere, in this Mesh's BodySpace
;Returns Penetrating, Colliding, or Clear
Method D3D_PhysicalEntity.Short_recurse_Sphere,uses esi edi ebx,pSphere,pNode,pvOrigin
LOCAL vtemp:Vec3
LOCAL distance:real8
LOCAL sumrad:real8
LOCAL result

    SetObject esi
   
    mov result,Clear
   
    ;Calculate the distance between the origins of the input boundingsphere
    ;and the input Node's boundingsphere...
    mov edx,pvOrigin
    mov eax,pNode
    Vec3_Distance .BSPNode.vOrigin, .Vec3
    fstp distance
   
    ;Calculate the Sum of the radii
    mov edx,pNode
    fld .BSPNode.fRadius
    mov edx,pSphere
    mov edx,.CollisionBodyInstance.pOwner
    fadd .CollisionBody.fRadius
    fstp sumrad
   
    ;If the distance is greater than the sum of the radii,
    ;then the sign is Positive for separation
    ;Otherwise it is Negative for penetration
   
    ;If sumradsqu >= distance then collision/penetration are possible
    .if $IsGreaterOrEqual(sumrad,distance)==TRUE

    @@: mov eax,pNode
        .if .BSPNode.pFaces==0
            ;It's NOT a Leaf Node, so there MUST be Two Children (right?)
           ;Recurse front
           mov edx,pNode
           or result,$OCall (esi.Short_recurse_Sphere,pSphere,.BSPNode.pFront,pvOrigin)
            .if eax==Penetrating
                ret
            .endif
           ;Recurse back
           mov edx,pNode
           or result,$OCall (esi.Short_recurse_Sphere,pSphere,.BSPNode.pBack,pvOrigin)
            .if eax==Penetrating
                ret
            .endif
        .else
            ;It's a Leaf Node, so it should contain a single triangle
            ;represented by a Face struct... we should find this
            ;lonely triangle as the only element within a Collection (ugh)
            mov edx,pNode
            mov edx,.BSPNode.pFaces
            mov edx,.DataCollection.pItems
            mov edx,      ;ptr to Face struct
            ;Test for intersection of Triangle and Sphere           
             or result,$OCall (esi.Triangle_versus_Sphere,edx,pSphere)
            .if eax==Penetrating
                ret
            .endif
        .endIf
   
    .endif
    mov eax,result
MethodEnd


Given that our Tree is a simple Binary Tree structure, I guess most of you reading this won't have too much trouble understanding the code presented today.
I'll wrap this post up with code for testing Sphere/Triangle.
The remaining code can be found in the Physics_Classify.inc file posted previously.

;Compare (the New State of) a Sphere and a 3D Triangle given as a Face in BodySpace
;Return Penetrating, Separating or Clear
Method CollisionBodyInstance.Triangle_versus_Sphere,uses esi, pTriangleFace, pSphere
LOCAL temp:Vec3
LOCAL vSphereOrigin:Vec3
local dist
LOCAL tri:triangle
    SetObject esi
   
    ;Transform the Sphere into Triangle Space
    mov edx,pSphere
    OCall esi.Transform_Vec3_WorldToBody, addr .CollisionBodyInstance.NewState.CMPosition, addr .NewState.Orientation
    Vec3_Stow vSphereOrigin
   
    ;Find closest point on Sphere to Plane of triangle
    mov eax,pTriangleFace
    mov eax,.Face.pPlane
    Vec3_Neg temp,.Vec3
    mov edx,pSphere
    mov edx,.CollisionBodyInstance.pOwner
    Vec3_Scale temp,.CollisionBody.fRadius
    Vec3_AddFrom vSphereOrigin
    Vec3_Stow temp
   
    ;Find the distance from that point to the plane
    mov edx,pTriangleFace
    mov edx,.Face.pPlane
    Vec3_Distance_Plane temp,.Vec4
    fstp dist
   
    ;If the distance is greater than zero theres no collision
    .if $IsPositive(dist)==TRUE
        ;If the distance is less than Epsilon
        .if $IsLess(dist,fEpsilon)==TRUE
            jmp @F
        .else
            return Clear
        .endif
    .endif
   
    ;We're definitely penetrating the Plane..
    ;Let's project our test point onto the Plane
    ;by moving it in the direction of the Normal
    ;by the amount of Penetration Distance
    mov edx,pTriangleFace
    mov edx,.Face.pPlane
    Vec3_Scale .Vec4,dist
    Vec3_AddFrom vSphereOrigin
    Vec3_Stow temp
   
    ;Convert face to triangle struct
    mov edx,pTriangleFace
    mov eax, .Face.pV0
    Vec3_Load .Vec3
    Vec3_Stow tri.v0
    mov eax, .Face.pV1
    Vec3_Load .Vec3
    Vec3_Stow tri.v1
    mov eax, .Face.pV2
    Vec3_Load .Vec3
    Vec3_Stow tri.v2
    ;Is the point inside the triangle?
    ;If so, we have our intersection point.
@@: invoke PointInTriangle, addr tri,.Face.pPlane, addr temp
    .if eax==TRUE
        .if $IsLess(dist,fEpsilon)==TRUE
            return Colliding
        .else
            return Penetrating
        .endif
    .endif
    mov eax,Clear
   
MethodEnd


As I said, the next post will contain code for Contact Generation of Sphere/Mesh.

Posted on 2009-04-06 19:25:04 by Homer
Generating a list of Contacts been a Mesh and a Sphere is a similar process to collision detection - we must once more recurse the BVH against the Sphere, however this time we will do so more thoroughly, determining points of contact as we do so.
Again, our recursion begins from a 'wrapper' method which passes the Root Node of the BVH to the search function:


;This method finds all the contacts for a Mesh/Sphere CollisionPair.
;pSphere   = 'other body' (derived from CollisionBodyInstance)
;pPair     = CollisionPair
;pContacts = output list of Contacts
Method D3D_PhysicalEntity.Find_Contacts_versus_Sphere,uses esi,pSphere,pPair,pContacts
LOCAL vSphereOrigin:Vec3
   SetObject esi
   
   ;Transform the input Sphere from WorldSpace to this mesh's BodySpace
   mov edi,pSphere
   OCall esi.Transform_Vec3_WorldToBody, addr .CollisionBodyInstance.NewState.CMPosition,  addr .NewState.Orientation
   Vec3_Stow vSphereOrigin
       
   ;Pass the Root Node of the owner body's SphereTree to our recursive function
   mov edx,.pOwner
   OCall esi.Long_recurse_Sphere,pSphere,.D3D_CollisionMesh.pRootNode,addr vSphereOrigin,pPair,pContacts
MethodEnd


Nothing much to see there.
Let's look at the recursive function:

;Recursive search for Contacts between Mesh and Sphere
;Returns nothing
Method D3D_PhysicalEntity.Long_recurse_Sphere,uses esi edi ebx,pSphere,pNode,pvOrigin,pPair,pContacts
LOCAL vtemp:Vec3
LOCAL distance:real8
LOCAL sumrad:real8
LOCAL result

   SetObject esi
   
   mov edx,pvOrigin
   Vec3_Dot .Vec3,.Vec3
   mov edx,pvOrigin
   mov eax,pNode
   Vec3_Distance .BSPNode.vOrigin, .Vec3
   fstp distance
   
   mov edx,pNode
   fld .BSPNode.fRadius
   mov edx,pSphere
   mov edx,.CollisionBodyInstance.pOwner
   fadd .CollisionBody.fRadius
   fstp sumrad

   .if $IsGreaterOrEqual(sumrad,distance)==TRUE
   @@: mov eax,pNode
       .if .BSPNode.pFaces==0
          mov edx,pNode
          OCall esi.Long_recurse_Sphere,pSphere,.BSPNode.pFront,pvOrigin,pPair,pContacts
          mov edx,pNode
          OCall esi.Long_recurse_Sphere,pSphere,.BSPNode.pBack,pvOrigin,pPair,pContacts
       .else
            mov edx,pNode
            mov edx,.BSPNode.pFaces
            mov edx,.DataCollection.pItems
            mov edx,    
            or result,$OCall (esi.Triangle_Contact_Sphere,edx,pSphere,pPair,pContacts)
           .if eax!=Clear
               ret
           .endif
       .endIf
   
   .endif
   mov eax,result
MethodEnd


This method walks the BVH tree until it finds Leaf nodes whose boundingspheres intersect the input sphere, then it tests the Triangle in each discovered leaf against the input sphere using the following method:


;Generate a Contact between Triangle and Sphere
;Returns nothing
Method CollisionBodyInstance.Triangle_Contact_Sphere,uses esi, pTriangleFace, pSphere, pPair, pContacts
LOCAL temp:Vec3,norm:Vec3
LOCAL vSphereOrigin:Vec3
local dist
   SetObject esi
   
   ;Transform the Sphere into Triangle Space (avoid recalculate plane)
   ;or transform the Triangle into World space (need new points and plane)
   mov edx,pSphere
   OCall esi.Transform_Vec3_WorldToBody, addr .CollisionBodyInstance.NewState.CMPosition, addr .NewState.Orientation
   Vec3_Stow vSphereOrigin
   
   ;Find closest point on Sphere to Plane of triangle
   mov eax,pTriangleFace
   mov eax,.Face.pPlane
   Vec3_Neg temp,.Vec3
   mov edx,pSphere
   mov edx,.CollisionBodyInstance.pOwner
   Vec3_Scale temp,.CollisionBody.fRadius
   Vec3_AddFrom vSphereOrigin
   Vec3_Stow temp
   
   ;Find the distance from that point to the plane
   mov edx,pTriangleFace
   mov edx,.Face.pPlane
   Vec3_Distance_Plane temp,.Vec4
   fstp dist
   
   ;If the distance is greater than zero theres no collision
   .if $IsPositive(dist)==TRUE
       ;If the distance is less than Epsilon
       .if $IsLess(dist,fEpsilon)==TRUE
           jmp @F
       .endif
   .endif
   
   ;We're definitely penetrating the Plane..
   ;Let's project our test point onto the Plane
   ;by moving it in the direction of the Normal
   ;by the amount of Penetration Distance
   mov edx,pTriangleFace
   mov edx,.Face.pPlane
   Vec3_Scale .Vec4,dist
   Vec3_AddFrom vSphereOrigin
   Vec3_Stow temp
   
   ;We have our intersection point.
@@:
   ;Transform point 'temp' to WorldSpace
   mov edx,pSphere
   OCall esi.Transform_Vec3_BodyToWorld, addr temp, addr .NewState.Orientation
   Vec3_Stow temp
   ;Rotate the Face Normal from BodySpace to WorldSpace
   mov edx,pTriangleFace
   mov edx,.Face.pPlane
   Mat33_Mul_Vec3 .NewState.Orientation,.Vec3
   Vec3_Stow norm
   ;Generate a Contact
   mov edx,pTriangleFace        
   OCall pContacts::Collection.Insert,$New(Contact,Init,pPair,addr temp,addr norm)        
MethodEnd


There's my Triangle/Sphere test.
It's quite unlike other tests I've seen - it works by back-projecting the most deeply penetrating point on the sphere onto the plane of the triangle, then checking if that point is within the bounds of the triangle.

That is the end of the Mesh/Sphere collision detection and contact generation code.
In the next exciting episode, we'll begin to look at the code for Mesh/Mesh collisions and contacts.
Posted on 2009-04-08 00:20:08 by Homer
Just a quick post to mention the newest code addition to Simulator class.
I've implemented a couple of new methods to sink collision event notifications, implemented at two discrete levels of complexity.
They are:
1 - Simulator.On_Collision_Pair
2 - Simulator.On_Collision_Contact

Your game or app can override them in order to receive these notifications.
The first method is triggered whenever a pair of bodies collides.
The value that you return from this method will determine what the Simulator does next.
0 - Typical collision response (ie continue to Contact generation etc).
1 - Attempt to mark both Bodies for automatic garbage collection (try to destroy both)
More values can be added if it seems worthwhile.

Anyway, the idea is that when we detect a CollisionPair, we ask the game/app what to do with the two objects.... ie, the game/app figures out what two things just collided and thus whether they go 'bounce or boom'.
If they go boom, we can mark them as 'dead', we don't need to deal with them anymore, the internal garbage collection will find them when it is convenient and safe.
But if they didn't explode, the game will receive further notifications as each contact is detected. I may change this. Hell, I might change everything.
At the moment, the Simulator ignores the return value for On_Collision_Contact.

It's not much, but it does make the Simulator easier to plug into different games/apps.

Posted on 2009-04-09 08:24:28 by Homer
The Separation test for Mesh/Mesh looks quite similar to the Sphere/Mesh test... well, at least at the beginning it does.. Essentially, we're going to walk two BVH trees at once in order to identify which triangles from the two meshes are closest together, then we're testing those pairs of triangles for intersection...


;Recursive separation test of two Mesh entities via their BVH trees
;Returns Penetrating, Colliding, or Clear
Method D3D_PhysicalEntity.versus_Mesh,uses esi,pOtherEntity
    SetObject esi
    ;Pass the Root Nodes of the two BVH trees to our recursive function
    mov edx,.pOwner
    mov eax,pOtherEntity
    mov eax,.D3D_CollisionMesh.pOwner
    OCall esi.Short_recurse_Mesh,pOtherEntity,.D3D_CollisionMesh.pRootNode,.D3D_CollisionMesh.pRootNode
MethodEnd



We're going to perform a 'dual tree walk'...
Here's our entrypoint 'wrapper' which passes the root nodes of both trees to the following recursive function:


; Recursive separation test of two Meshes via Dual Tree Recursion
; Arguments: None.
; Return:    Colliding, Penetrating or Clear
Method D3D_PhysicalEntity.Short_recurse_Mesh,uses esi edi ebx,pEntityB,pNodeOnA,pNodeOnB
LOCAL vtemp:Vec3
    SetObject esi
   
    ;vtemp = NodeB's origin in Body A's space...
    ;First, transform NodeB's origin into WorldSpace
    mov edx,pNodeOnB
    mov edi,pEntityB
    OCall edi::CollisionBodyInstance.Transform_Vec3_BodyToWorld, addr .BSPNode.vOrigin, addr .CollisionBodyInstance.NewState.Orientation
    Vec3_Stow vtemp
    ;Next, transform it into A's bodyspace
    OCall esi.Transform_Vec3_WorldToBody, addr vtemp,  addr .NewState.Orientation
    Vec3_Stow vtemp
   
    ;Finally, calculate the distance from A to B
    ;Since we work in A's bodyspace, A's position is ZERO
    ;so distance = sqrt(vtemp.x^2+vtemp.y^2+vtemp.z^2)
    Vec3_Dot vtemp,vtemp
    ;fsqrt  ... we'll avoid the sqrt by squaring the sum of the radii
   
    ;If (A.radius+B.radius) < distance(A,B)
   
    mov edx,pNodeOnA
    fld .BSPNode.fRadius
    mov edx,pNodeOnB
    fadd .BSPNode.fRadius
    fmul st(0),st(0)
   
    fsub
    fstpReg eax
    ;If the distance is greater than the sum of the radii,
    ;then the sign is Positive for separation
    ;Otherwise it is Negative for penetration
   
    .if eax==0
        jmp @F              ;collision, treat as penetration
    .endif
   
    .ifBitSet eax,BIT31     ;negative, so we have penetration
       
@@:     ;If NodeA is not a leaf:
        mov eax,pNodeOnA
        .if .BSPNode.pFaces==0
            ;If NodeB is not a leaf:
            mov edx,pNodeOnB
            .if .BSPNode.pFaces==0
               ;Recurse A.front, B.front
               OCall esi.Short_recurse_Mesh,pEntityB,.BSPNode.pFront,.BSPNode.pFront
               .if eax==Penetrating
                   ret
               .endif
               ;Recurse A.front, B.back
               mov eax,pNodeOnA
               mov edx,pNodeOnB
               OCall esi.Short_recurse_Mesh,pEntityB,.BSPNode.pFront,.BSPNode.pBack
               .if eax==Penetrating
                   ret
               .endif
               ;Recurse A.back, B.front
               mov eax,pNodeOnA
               mov edx,pNodeOnB
               OCall esi.Short_recurse_Mesh,pEntityB,.BSPNode.pBack,.BSPNode.pFront
               .if eax==Penetrating
                   ret
               .endif
               ;Recurse A.back, B.back
               mov eax,pNodeOnA
               mov edx,pNodeOnB
               OCall esi.Short_recurse_Mesh,pEntityB,.BSPNode.pBack,.BSPNode.pBack
            .else
               ;Recurse A.front, B
               OCall esi.Short_recurse_Mesh,pEntityB,.BSPNode.pFront,pNodeOnB               
                .if eax==Penetrating
                   ret
               .endif
               ;Recurse A.back, B
               mov eax,pNodeOnA
               OCall esi.Short_recurse_Mesh,pEntityB,.BSPNode.pBack,pNodeOnB
            .endif
        .else
            ;If NodeB is not a leaf:
            mov edx,pNodeOnB
            .if .BSPNode.pFaces==0
                ;Recurse A, B.front
                OCall esi.Short_recurse_Mesh,pEntityB,pNodeOnA,.BSPNode.pFront               
               .if eax==Penetrating
                   ret
               .endif
                ;Recurse A, B.back
                mov edx,pNodeOnB
                 OCall esi.Short_recurse_Mesh,pEntityB,pNodeOnA,.BSPNode.pBack
            .else
                mov edx,.BSPNode.pFaces
                mov edx,.Collection.pItems
                mov edx,
                mov eax,pNodeOnA
                mov eax,.BSPNode.pFaces
                mov eax,.Collection.pItems
                mov eax,
                OCall esi.Face_vs_Face, pEntityB,eax,edx
            .endif
        .endIf
    .endif
   
   
MethodEnd


The recursive function searches for pairs of proximate triangles (ie whose boundingspheres overlap) and passes those to the following method:


;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 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
    .switch $invoke (ClassifyTrianglePlane,addr tri2,addr plane1)
    ;Case 1: tri2 is completely clear of tri1's plane
    .case FRONTFRONTFRONT
        return Clear

    ;Case 2: One point of tri2 is touching the plane of tri1, the others are in front
    .case COPLANARFRONTFRONT
        invoke PointInTriangle,addr tri1, addr plane1, addr tri2.v0
        .if eax==TRUE
            return Colliding
        .endif
        return Clear
    .case FRONTCOPLANARFRONT
        invoke PointInTriangle,addr tri1,addr plane1, addr tri2.v1
        .if eax==TRUE
            return Colliding
        .endif
        return Clear
    .case FRONTFRONTCOPLANAR
        invoke PointInTriangle,addr tri1,addr plane1, 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
    .case FRONTCOPLANARCOPLANAR
        ;we need to test/generate two contacts at tri2.v1 and tri2.v2
        xor edi,edi
        invoke PointInTriangle,addr tri1, addr plane1,addr tri2.v1
        .if eax==TRUE
            return Colliding
        .endif
        invoke PointInTriangle,addr tri1, addr plane1,addr tri2.v2
        .if eax==TRUE
            return Colliding
        .endif
        return Clear
    .case COPLANARFRONTCOPLANAR
        ;we need to test/generate two contacts at tri2.v0 and tri2.v2
        xor edi,edi
        invoke PointInTriangle,addr tri1, addr plane1,addr tri2.v0
        .if eax==TRUE
            return Colliding
        .endif
        invoke PointInTriangle,addr tri1, addr plane1,addr tri2.v2
        .if eax==TRUE
            return Colliding
        .endif
        return Clear

    .case COPLANARCOPLANARFRONT
        ;we need to test/generate two contacts at tri2.v0 and tri2.v1
        xor edi,edi
        invoke PointInTriangle,addr tri1, addr plane1,addr tri2.v0
        .if eax==TRUE
            return Colliding
        .endif
        invoke PointInTriangle,addr tri1, addr plane1,addr tri2.v1
        .if eax==TRUE
            return Colliding
        .endif
        return Clear
    .endsw
   
    mov eax,Penetrating
MethodEnd


This last method quickly determines whether two given triangles are clear, colliding or penetrating, and will terminate early if penetration is found.

That's enough for this post.
As you can see, its all quite similar to the Mesh/Sphere code, just a little more complex since we have to walk BOTH trees whenever possible.
It's worth noting that we are not solving this problem in the same Space as we did for the Mesh/Sphere problem ;)

Next post will contain the Mesh/Mesh contact generation code.
Posted on 2009-04-11 02:28:38 by Homer
Hang in there guys, I'm just trying to drag the rest of my game engine up to the same standard before I complete the physics engine ;)
Posted on 2009-05-11 02:37:55 by Homer
The game engine is now waiting on the physics engine to be updated!

If you've been following my GameDev thread, you'll be aware that I'm making some hefty changes to the architecture - but the physics code itself is essentially unchanged.

Today I spent some time reading about the physics of Buoyancy (ie, the magical force that makes things float on water despite their mass).

The author had written code which represented the water as a Plane, and implemented an equation which generated a Force in the Direction of the Plane Normal.

I have a few problems with this.
#1 - Is water ever 'inclined'? I mean, we're used to seeing it flat, even if it's flowing.

#2 - Assuming water CAN be inclined, is Buoyant Force acting along the Plane Normal, or is it (as I suspect) always acting in an UPWARD direction (essentially, counteracting Gravity) ??

What is your opinion?
Posted on 2009-07-14 04:37:58 by Homer
Ad #1:
Water always tries to make its plane parallel to ground "plane" because gravity attacts each water particle equally (assuming that it is water and not some variable-density variable-mass liquid). Water can be made "inclined" for some short time (via movement inertia) but it will reach the aforementioned state sooner or later (usually sooner ;) ).

Ad #2:
Buoyancy is a force acting on a body in water (in liquids, generally). The body pushes water particles around it while these particles try to return back to "their place". Buoyancy is a direct effect of the fact stated in point #1, so it is always "upward". It is possible to make it work sideways via some movement inertia but it will be only temporary and -in fact- only apparent to local observer. You know - imagine moving a cup of water left or right very quickly. For some short time the water surface won't be parallel in respect to gravity. And in this exact amount of time, buoyancy won't be acting "upward" - it will be acting perpendicularly to the water's surface because the water particles which are BELOW the body won't be pushing it for some short time. Effectively, force from one side is weakened because of some particles being below the body, while force from another side is strengthened because of some particles right next to the body (of even above it if the inertia is strong). Resulting vector points more or less (depending on the inertia) sideways.

Interesting example od buoyancy is a ball submerged a bit and dropped down a waterfall - while falling down it will move slightly away from the waterfall because some water particles will push it from one side (and the air will push it from another but gases are usually weaker).


I hope it's clear and anderstandable ^^
Posted on 2009-07-14 11:18:01 by ti_mo_n
I think in your last example, you are suggesting that the only reason for "sideways" motion is due to the friction/drag of the waterfall against the half-submerged ball, which is only present because Buoyancy is tending the ball UPWARDS (otherwise the water and the ball would fall at very close to exactly the same speed, and side forces would then be negligable).

So you agree, that Buoyancy always acts UPWARDS, even in extreme examples such as a ship half-way up the side of a tsunami (again, only drag causing side motion)?

This would seem accurate, because flotsam and jetsam tends not to be pushed along by waves, as it has little drag force, but lots of buoyancy.

I think I'm happy to accept that "buoyancy can be considered as opposing Gravity" - apply it only in the UP vector, and take advantage of a few math/code shortcuts that become possible under this premise.
Posted on 2009-07-15 02:13:55 by Homer
I think I have the answer.

Buoyancy is simply a manifestation of a density differential....
If we consider that things which are less dense float in things which are more dense, and if we further consider the AVERAGE density of a buoyant object (IE, its mass divided by its volume), then it becomes clear that an object's buoyancy is related to its mass/space ratio. It then follows that since we've determined that buoyancy is in fact an example of density-displacement, it always acts in the upward (away from the planet) direction!
Posted on 2009-07-15 10:34:35 by Homer
It's not about density, but mass. Of course more density means more mass in a given area but directly it's all about mass and indirectly about density ^^ If the mass of the submerged object is equal than the mass of all water particles around it (multiplied by their angles -- more on this later), then it floats. If the mass of the object is larger - it sinks. And if it's smaller - it moves upwards. And there's more: Every water particle acts on the object in direction perpendicular to the plane between the object's nearest particle and water's particle in question.

Image 1 shows the forces acting on a stationary submerged object. Air pressure is negligible in real-world situation because as atmospheric pressure increases so does the water pressure. Air pressure's effect is then effectively reduced.

If we want an object to float then its mass must be euqal to the mass of all particles touching its submerged area (multiplied by their angles -- more on this later). Every water particle that touches the object will create a force perpendicular to the plane positioned exactly between water's particle and object's particle.

If we submerge an object only slightly (image 2) then we have fewer buoyancy focre vectors (because of smaller area touching the water) so the effective buoyancy is weaker and the object will probably sink more. The object will stop sinking if the mass of all particles pushing it upwards is equal to the object's mass. But there's a catch: if a water particle is acting at an angle different than 180 deg in respect to gravity (in other words: different than "upwards") then it effect on buoyancy is smaller (because it pushes more to the side than upwards).

If we increase liquid's density and therefore mass acting on the submerged objects, its buoyancy (yellow vectors) will increase. If we increase the gas' density without touching the liquid's density (unlikely to happen in real world) then the light-blue vectors will increase withot the yellow ones increasing. So the buoyancy will be reduced.

Therefore we need many particles pushing an object upwards. It will be so if the object is a flat square (image 3). Almost every particle acts upwards in case of a flat square. That's why it's difficult to sink objects like that. The pink object on image 3 will be easy to sink because most of the water's particles act on it sideways, not upwards.

There's yet another thing: stabilization. If most of the water's particles act upwards then the object is difficult to sink but unstable (it easy to rotate it). This is why it's easy to rotate a submerged ball (actually it starts to rotate on its own if you push it in some direction while it's submerged). If we want to stabilize an object we must add some water's particles acting sideways. I don't know if anyone wants me to copy my physics book here but the short story is that if water's particles act sideways then they stabilize an object and it's harder to rotate it. This is exactly what is done with ships (image 4). Ships are made so like most of their area is sunk. Their sides are very steep (for stabilization) and thir bottoms are almost parallel to the ground (for buoyancy). Playing with the bottoms of the ships you can increase buoyancy at the cost of stabilization (usually done with sports ships or fast military ships or any ship which has to be quick and maneuverable) or you can increase stabilization at the cost of buoyancy (cargo/passenger ships - they must be stable so you can easily drink a cup of coffee regardless of height of the waves. but on the other hand it's difficult to maneuver such ships).

Now going back to image 3: the flat square is difficult to sink now but it's unstable - you can easily rotate whichever way you like. You can even align it perpendicularly to the water's surface so it becomes very stable but also ver easy to sink. The pink object is easy to sink but difficult to rotate. If it sinks enough, it will touch the bottom of the water basin. Now you can push its top so it will fall and align itself with water's surface making itself unstable and difficult to sink (this is what happens when trees fall into water).

About flotsam and jetsam: This stuff is usually more or less round/spherical (>link<)- that's why it gets little drag from waves. I have omitted side movement for simplicity here. The entire post assumes stationary object in a waveless, static liquid.

PS: Image 3 has an incorrect label saying it's a ship.
Posted on 2009-07-15 14:42:42 by ti_mo_n
Thanks for the feedback, it's appreciated.
Your comments and images are interesting, the implications are obvious (to me) and agree with my observations of the physical world around us.

The simplistic implementation I looked at computed the intersection of the water's plane with the body's mesh, calculated the submerged and not-submerged half-volumes, and then calculated a force vector that operates along the water plane's normal, and is based largely on the ratio of half-volumes versus a special constant for 'density of water in the context of air".

A more accurate implementation would calculate forces on a per-submerged-vertex basis, weighted by the area of the faces which that vertex shares, calculate the physics deltas for this force, and sum those deltas to compute a total change in linear and angular velocity.

This would make the body ROLL ACCURATELY and find its own angular equilibrium with respect to the water around it, irrespective of the angle of the water.
Posted on 2009-07-16 02:43:01 by Homer
Yup, the more accurate method would be nice ^^ Imagine player character's body falling into water - the more accurate method will rotate it first and keep it properly submerged. Also, the more accurate method will rotate, for example, crates (due to drag) if you push them while they are submerged. I think it's definitely the way to go for :)
Posted on 2009-07-16 08:58:35 by ti_mo_n
Bad things today, I loaded a more complex world model and everything went pear shaped.
I must halt physics work and correct anomolies!

Sorry peoples.
Posted on 2009-07-19 11:36:54 by Homer
Good news - bugs eliminated in the world-processor (portalizer), ready to continue the good work!
Posted on 2009-08-17 04:34:09 by Homer
I am unpinning this thread because noone appears interested in this anymore.
Sad really.
Posted on 2010-01-28 02:26:41 by Homer