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 :)
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.
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.
As I said, the next post will contain code for Contact Generation of Sphere/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.
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:
Nothing much to see there.
Let's look at the recursive function:
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:
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.
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.
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.
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.
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...
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:
The recursive function searches for pairs of proximate triangles (ie whose boundingspheres overlap) and passes those to the following method:
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.
;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.
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 ;)
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?
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?
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 ^^
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 ^^
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.
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.
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!
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!
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.
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.
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.
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.
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 :)
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.
I must halt physics work and correct anomolies!
Sorry peoples.
Good news - bugs eliminated in the world-processor (portalizer), ready to continue the good work!
I am unpinning this thread because noone appears interested in this anymore.
Sad really.
Sad really.