Collision Detection and Handling
CollisionHandling.zipThis set of data structures is used to detect and handle collisions for a game engine. The detection of collisions is optimized by the use of an octree subdivison that spatially organizes the triangulated faces of a model. The primary mathematics for detecting a collision is in the CollisionTriangle class.
Feel free to explore the files on the page, or you can download the original C# code in a zip file. The code provided is incomplete. Its purpose is to give a general idea of the code's architecture as well as how the application works.
Bounds - The bounds class is a bounding box used for various dynamics and simulation calculations. For example, it serves as the collision box for a player in an FPS style game. It is also used to define the space contained by an OctreeNode.
(show)//Bounds class... /// <summary> /// The box face enumeration indicates which face of the bounds object /// is intersected with in a ray intersection test /// </summary> public enum BoxFace { None, PositiveX, PositiveY, PositiveZ, NegativeX, NegativeY, NegativeZ } public class Bounds : Node { /* * CONSTANTS */ /// <summary> /// cosine of 45 degrees /// </summary> const float COSINE_OF_45 = 0.70710678f; /// <summary> /// invsere squear root of three /// </summary> const float INVERSE_SQRT_OF_THREE = 0.57735027f; /// <summary> /// array of vertex normals for any axis-aligned rectilinear volume /// </summary> public static Vector3[] vertexNormals = new Vector3[8] { //min vertex new Vector3(-INVERSE_SQRT_OF_THREE,-INVERSE_SQRT_OF_THREE,-INVERSE_SQRT_OF_THREE), //max vertex new Vector3( INVERSE_SQRT_OF_THREE, INVERSE_SQRT_OF_THREE, INVERSE_SQRT_OF_THREE), new Vector3( INVERSE_SQRT_OF_THREE,-INVERSE_SQRT_OF_THREE,-INVERSE_SQRT_OF_THREE), new Vector3(-INVERSE_SQRT_OF_THREE, INVERSE_SQRT_OF_THREE, INVERSE_SQRT_OF_THREE), new Vector3( INVERSE_SQRT_OF_THREE, INVERSE_SQRT_OF_THREE,-INVERSE_SQRT_OF_THREE), new Vector3(-INVERSE_SQRT_OF_THREE,-INVERSE_SQRT_OF_THREE, INVERSE_SQRT_OF_THREE), new Vector3(-INVERSE_SQRT_OF_THREE, INVERSE_SQRT_OF_THREE,-INVERSE_SQRT_OF_THREE), new Vector3( INVERSE_SQRT_OF_THREE,-INVERSE_SQRT_OF_THREE, INVERSE_SQRT_OF_THREE) }; /// <summary> /// array of edge normals for any axis-aligned rectilinear volume /// </summary> public static Vector3[] edgeNormals = new Vector3[12] { new Vector3(-Bounds.COSINE_OF_45, 0, -Bounds.COSINE_OF_45), new Vector3(0, Bounds.COSINE_OF_45, -Bounds.COSINE_OF_45), new Vector3(Bounds.COSINE_OF_45, 0, -Bounds.COSINE_OF_45), new Vector3(0, -Bounds.COSINE_OF_45, -Bounds.COSINE_OF_45), new Vector3(0, Bounds.COSINE_OF_45, Bounds.COSINE_OF_45), new Vector3(-Bounds.COSINE_OF_45, 0, Bounds.COSINE_OF_45), new Vector3(0, -Bounds.COSINE_OF_45, Bounds.COSINE_OF_45), new Vector3( Bounds.COSINE_OF_45, 0, Bounds.COSINE_OF_45), new Vector3(-Bounds.COSINE_OF_45,-Bounds.COSINE_OF_45, 0), new Vector3(-Bounds.COSINE_OF_45, Bounds.COSINE_OF_45, 0), new Vector3( Bounds.COSINE_OF_45, Bounds.COSINE_OF_45, 0), new Vector3( Bounds.COSINE_OF_45,-Bounds.COSINE_OF_45, 0) }; /// <summary> /// face normals for any axis-aligned rectilinear volume /// </summary> public static Vector3[] faceNormals = new Vector3[6] { new Vector3(1,0,0), //X face new Vector3(0,1,0), //Y face new Vector3(0,0,1), //Z face new Vector3(-1,0,0), //-X face new Vector3(0,-1,0), //-Y face new Vector3(0,0,-1) //-Z face }; /* * CLASS PROPERTIES */ /// <summary> /// the bounding box's minimum point /// </summary> protected Vector3 min; /// <summary> /// the bounding box's maximum point /// </summary> protected Vector3 max; /// <summary> /// the dimensions of the box /// </summary> protected Vector3 delta; /// <summary> /// indicates if the delta or center needs to be updated /// </summary> protected bool needsUpdate; /// <summary> /// the center point of the bounding box /// </summary> protected Vector3 centerPosition; /* * CONSTRUCTOR */ /// <summary> /// constructor from min/max vectors /// </summary> /// <param name="min">minimum position</param> /// <param name="max">maximum position</param> public Bounds(TwelveCylinderGame newGame, Vector3 min, Vector3 max) : base(newGame) { this.Min = min; this.Max = max; init(); } /// <summary> /// initializes the index buffer for rendering the box /// </summary> private void init() { needsUpdate = true; } //additional constructors omitted //static constructors omitted //some encapsulators omitted /* * BOX DATA */ /// <summary> /// gets the volume of this box /// </summary> public float Volume { get { if(needsUpdate) updateData(); //update delta and center position //prevent potential negative volume... return Math.Max(0, delta.X * delta.Y * delta.Z); } } /// <summary> /// get the bounding box center point /// </summary> public Vector3 Center { get { if (needsUpdate) updateData(); return centerPosition; } } /// <summary> /// updates the center point definition /// </summary> private void updateData() { delta = max - min; centerPosition = min + (0.5f * delta); needsUpdate = false; } /* * METHODS */ /// <summary> /// adds a point to the bounding box /// extending it if needed /// </summary> /// <param name="p">the point to add</param> public virtual void AddPoint(Vector3 p) { if (p.X >= max.X) max.X = p.X; if (p.Y >= max.Y) max.Y = p.Y; if (p.Z >= max.Z) max.Z = p.Z; if (p.X <= min.X) min.X = p.X; if (p.Y <= min.Y) min.Y = p.Y; if (p.Z <= min.Z) min.Z = p.Z; needsUpdate = true; } /// <summary> /// configures the bounding box to surround all the vertices in the specified array /// </summary> /// <param name="verts">an array of vertices to be bounded</param> public void BoundVertices(VertexPositionNormalTexture[] verts) { max = -Vector3.Max; min = Vector3.Min; for (int i = 0; i < verts.Length; i++) AddPoint(verts[i].Position); } /// <summary> /// inflates the size of the bounding box by the specified buffer /// </summary> /// <param name="buffer">distance to push out each face of the bounding box</param> public virtual void AddBuffer(float buffer) { min.X -= buffer; min.Y -= buffer; min.Z -= buffer; max.X += buffer; max.Y += buffer; max.Z += buffer; needsUpdate = true; } /// <summary> /// checks to see if two bounding boxs overlap any volume of space /// </summary> /// <param name="bb">bounding box to check against this one</param> /// <returns>true if any volume of space is shared by the two boxes</returns> public bool BoxOverlap(Bounds bb) { //verifty that the two boxes don't miss in any dimension... return (max.X >= bb.min.X && min.X <= bb.max.X && max.Y >= bb.min.Y && min.Y <= bb.max.Y && max.Z >= bb.min.Z && min.Z <= bb.max.Z); } /// <summary> /// Calculates and returns the volume of the overlap /// region between two bounding boxes. /// </summary> /// <param name="b1">the first bounds</param> /// <param name="b2">the second bounds</param> /// <returns>the volume of the overlap</returns> public static float GetVolumeOfOverlap(Bounds b1, Bounds b2) { float[] volumeComp = new float[3]{0,0,0}; float innerMax, innerMin; float min1, min2, max1, max2; //loops through the three dimensions of a vector for(int i = 0; i < 3; i++) { min1 = XNAHelper.GetComponent(b1.Min, i); min2 = XNAHelper.GetComponent(b2.Min, i); max1 = XNAHelper.GetComponent(b1.Max, i); max2 = XNAHelper.GetComponent(b2.Max, i); //determine inner (larger) minimum position if(min1 < min2) innerMin = min2; else innerMin = min1; //determine inner (smaller) maximum position if(max1 < max2) innerMax = max1; else innerMax = max2; if (innerMax < innerMin) return 0; //volumes don't overlap in a dimension //thus the overlap has no volume //overlap dimension is the differene between //the inner two delimitors of the bounds //bounding box volumeComp[i] = innerMax - innerMin; } return (volumeComp[0] * volumeComp[1] * volumeComp[2]); } /// <summary> /// check if a point in inside the bounding box /// </summary> /// <param name="p">point to test</param> /// <returns>true if the point is inside</returns> public bool PointInside(Vector3 p) { return (p.X > min.X && p.X <= max.X && p.Y > min.Y && p.Y <= max.Y && p.Z > min.Z && p.Z <= max.Z); } /// <summary> /// Tests for ray intersection with this box. /// </summary> /// <param name="localRay">the intersection ray to test /// (must be in the same coordinate space as the box)</param> /// <param name="tnear">the output distance from the ray /// origin to the first collision point</param> /// <param name="tfar">the output distance from the ray /// origin to the second collision point</param> /// <returns>the box face which the ray intersects with or "none"</returns> public BoxFace RayIntersect(OptimizedRay localRay, out float tnear, out float tfar) { tnear = -float.MaxValue; tfar = float.MaxValue; float paramT1, paramT2, temp; int face, nearFace = -1, farFace = -1; float rayDirectionComp, rayWorldDivDComp, rayPositionComp, bmin, bmax; //for each component of a vector (X,Y,Z) for (int vComp = 0; vComp < 3; vComp++) { //vector components //component from ray direction rayDirectionComp = XNAHelper.GetComponent(localRay.Direction, vComp); //component from ray (1 / direction) rayWorldDivDComp = XNAHelper.GetComponent(localRay.WorldDivD, vComp); //component from ray origin rayPositionComp = XNAHelper.GetComponent(localRay.Position, vComp); //bounding box minimum point position bmin = XNAHelper.GetComponent(this.min, vComp); //bounding box maximum point position bmax = XNAHelper.GetComponent(this.max, vComp); if (Math.Abs(rayDirectionComp) < 0.00001f) { //ray is perpendicular to axis if (rayPositionComp < bmin || rayPositionComp > bmax) //ray start is outside of bounding box return BoxFace.None; } else { paramT1 = (bmin - rayPositionComp) * rayWorldDivDComp; paramT2 = (bmax - rayPositionComp) * rayWorldDivDComp; if (paramT1 > paramT2) { temp = paramT1; paramT1 = paramT2; paramT2 = temp; face = vComp; //positive axis direction face } else face = vComp + 3; //negative axis direction face if (paramT1 > tnear) { //near face tnear = paramT1; nearFace = face; } if (paramT2 < tfar) { //far face tfar = paramT2; if (face > 2) farFace = face - 3; else farFace = face + 3; } if (tnear > tfar || tfar < 0.00001f) return BoxFace.None ; //box is behind the ray } } if (tnear > tfar || tfar < 0.00001f) return BoxFace.None; if (tnear < 0.0f) //intersection with the box from inside return (BoxFace)Enum.ToObject(typeof(BoxFace), farFace); else //intersection with the box from outside return (BoxFace)Enum.ToObject(typeof(BoxFace), nearFace); } //bounds rendering omitted }
Octree - This class stores the root of an octree spatial subdivision. It serves as an encapsulator to create, update, render and manipulate the octree.
(show)//Octree class... public class Octree : SceneItem { /// <summary> /// primitive shader for drawing the octree boxes /// </summary> protected ShaderCustom primitiveShader; /// <summary> /// the root (top) level node of the octree /// </summary> protected OctreeNode root; /// <summary> /// the hierarchical depth of octree /// nodes to draw during a render call /// </summary> protected uint treeDisplayDepth; /// <summary> /// the depth of the octree /// </summary> protected uint treeDepth; /// <summary> /// the volume of the smallest /// leaf nodes in the tree /// </summary> protected float leafVolume; /// <summary> /// the color used to render the /// boundaries of the octree /// </summary> protected Color treeColor; /// <summary> /// the number of leaf nodes in the tree /// </summary> protected int leafNodeCount; /* * CONSTRUCTORS */ /// <summary> /// constructor for an octree with parameters for controlling automatic subdivision /// </summary> /// <param name="newGame">the game object</param> /// <param name="newName">a name for this octree</param> /// <param name="box">the top level box that contains the entire tree</param> /// <param name="maxDepth">the maximum depth to divide the tree</param> /// <param name="minLeafVolume">a threshold that will prevent the trees leaf nodes /// from being subdivided smaller than this volume, or zero to ignore this feature.</param> public Octree(TwelveCylinderGame newGame, string newName, Bounds box, uint maxDepth, float minLeafVolume) : base(newName, NodeType.SceneItem, true, newGame) { DateTime start = DateTime.Now; leafNodeCount = 0; //determine maximum tree depth treeDepth = GetNewMaxDepth(box.Volume, minLeafVolume, maxDepth); root = new OctreeNode(this, null, curGame, box, 0, treeDepth); init(); DateTime end = DateTime.Now; //printTreeData(end - start); } //additional constructors omitted /// <summary> /// init common parameters for the tree /// </summary> private void init() { treeColor = Color.White; this.Visible = false; treeDisplayDepth = 0; if (curGame != null) primitiveShader = curGame.ShaderManager.Primitive3DShader; } /// <summary> /// prints info about the new octree to the log file /// </summary> /// <param name="time">the time span used to /// reate the tree definition</param> protected virtual void printTreeData(TimeSpan time) { curGame.Log(this.Name + " Max depth: " + treeDepth); curGame.Log("Creation Time: " + time.TotalMilliseconds + " ms"); curGame.Log("leaf volume: " + leafVolume); } public override void unload(bool disposeResources) { base.unload(disposeResources); if (root != null) root.unload(disposeResources); if (primitiveShader != null) primitiveShader.unload(disposeResources); root = null; primitiveShader = null; } /* * METHODS */ /// <summary> /// callback to add a leaf node to this tree /// </summary> /// <returns></returns> public virtual int addLeafNode(OctreeNode leaf) { return leafNodeCount++; } /// <summary> /// gets a list of octree leaf nodes which intersect with /// the specified bounding box /// </summary> /// <param name="b">a bounding box to test</param> /// <returns>a list of octree leaf nodes</returns> public virtual List<OctreeNode> GetIntersectedLeafNodes(Bounds b) { List<OctreeNode> leafNodes = new List<OctreeNode>(12); root.GetIntersectedLeafNodes(b, ref leafNodes); return leafNodes; } /// <summary> /// Recursive function to find the octree leaf node /// that contains the specified world position. /// </summary> /// <param name="worldPos">a world space coordinate</param> /// <returns>the containing leaf node</returns> public virtual OctreeNode GetContainingLeaf(Vector3 worldPos) { return root.getContainingLeaf(worldPos); } /// <summary> /// Calculates the maximum tree depth that should be subdivied to. /// This is calculated from a minimum leaf volume and an arbitrary /// maximum depth value. /// </summary> /// <param name="topVolume">the volume of the top level bounds of the tree</param> /// <param name="minLeafVolume">the minimum leaf volume</param> /// <param name="maxDepth">the maximum depth of the tree</param> /// <returns>the new maximum depth of the tree</returns> protected uint GetNewMaxDepth(float topVolume, float minLeafVolume, uint maxDepth) { uint newTreeDepth = 0; float newLeafVolume = topVolume; if (minLeafVolume > 0) { while (true) { newLeafVolume /= 8; newTreeDepth++; //reached arbitrary maximum if(newTreeDepth == maxDepth) break; if (newLeafVolume < minLeafVolume) { //back one step newLeafVolume *= 8; newTreeDepth--; break; } } } else { //negative volume indicates to ignore newTreeDepth = maxDepth; } //limit to 0 if(newTreeDepth < 0) newTreeDepth = 0; return newTreeDepth; } /// <summary> /// calculates the tree depth and leaf volume /// properties from the current tree hierarchy /// </summary> protected virtual void updateTreeData() { treeDepth = root.getMaximumDepth(); leafVolume = root.Box.Volume / (float)Math.Pow(OctreeNode.NUM_TREE_CHILDREN, treeDepth); } //encapsulators omitted /* * UPDATE & RENDER */ public override void update(GameTime gameTime, Camera curCam, Matrix projMatrix, Matrix viewProj) { base.update(gameTime, curCam, projMatrix, viewProj); //update shader if visibility is on if (this.Visible) primitiveShader.WVP = viewProj; //update the tree nodes root.update(gameTime, curCam, projMatrix, viewProj); } /// <summary> /// renders the bounds of the branches of this octree /// </summary> /// <param name="rm"></param> public override void Render(RenderMode rm) { if (curGame == null || primitiveShader == null || !primitiveShader.EffectLoaded) return; //not capable of rendering //sets vertex decleration to VertexPositionColor curGame.beginPrimitiveVertexDecleration(); //use single pass primitive shader primitiveShader.Begin(); primitiveShader.BeginPass(0); RenderTreeBounds(); primitiveShader.EndPass(0); primitiveShader.End(); } protected virtual void RenderTreeBounds() { root.DrawTreeBounds(treeDisplayDepth); } }
//OctreeNode class... public class OctreeNode : Node { /* * CONSTANTS */ /// <summary> /// the number of children in an octree is 8. /// I made this a constant in case the fundemental nature of three dimensional /// pace changes one day and I needed to update it. /// </summary> public const int NUM_TREE_CHILDREN = 8; /* * CLASS PROPERTIES */ /// <summary> /// the parent of this tree node /// </summary> protected OctreeNode curParent; /// <summary> /// the root of this tree node /// </summary> protected Octree curTree; /// <summary> /// the box defining this tree node /// </summary> protected Bounds box; /// <summary> /// the node children (if null node is a leaf) /// </summary> protected OctreeNode[] children; /// <summary> /// depth in the tree that this node defines /// </summary> protected uint treeLevel; /* * CONSTRUCTOR */ /// <summary> /// recursive constructor to create a new octree node and children /// </summary> /// <param name="newTree">an octree object that holds the root of the tree</param> /// <param name="newParent">the tree node that is the parent to this one</param> /// <param name="newGame">the TwelveCylinder game object</param> /// <param name="box">the box that defines the new tree node</param> /// <param name="depth">the current depth in the tree of this node</param> /// <param name="maxDivisions">the maximum subdivision level of the tree node where 0 is the root node</param> public OctreeNode(Octree newTree, OctreeNode newParent, TwelveCylinderGame newGame, Bounds newBox, uint depth, uint maxDivisions) : base(newGame, "octree node", NodeType.SceneItem) { if (newBox == null) throw new ArgumentNullException("Octree node requires non-null bounds."); curTree = newTree; //parent octree curParent = newParent; //parent tree node //tree node bounds box = newBox; treeLevel = depth; // if subdivision still needed if (depth < maxDivisions) subdivide(maxDivisions); else curTree.addLeafNode(this); } //additional constructors omitted /* * UNLOADING */ /// <summary> /// unloads this collision tree node and it's children /// </summary> /// <param name="disposeResources"></param> public override void unload(bool disposeResources) { base.unload(disposeResources); curParent = null; curTree = null; box = null; if (children != null) { for (int i = 0; i < OctreeNode.NUM_TREE_CHILDREN; i++) children[i].unload(disposeResources); children = null; } } /* * METHODS */ /// <summary> /// recursive method to get the leaf nodes which intersect with the specified bound box /// </summary> /// <param name="b">a bounding box to test</param> /// <param name="leafNodes">the output list of leaf nodes that intersect with the bounds</param> public void GetIntersectedLeafNodes(Bounds b, ref List<OctreeNode> leafNodes) { if (!b.BoxOverlap(box)) return; //test box does not overlap with tree node's box if (children != null) { // if not a leaf node, recurse to all children foreach (OctreeNode child in children) child.GetIntersectedLeafNodes(b, ref leafNodes); } else leafNodes.Add(this); } /// <summary> /// recursive function to find the octree leaf node that contains /// the specified world position /// </summary> /// <param name="worldPos">a world space coordinate</param> /// <returns>the containing leaf node</returns> public virtual OctreeNode getContainingLeaf(Vector3 worldPos) { if (box.PointInside(worldPos)) { if (children == null) return this; OctreeNode curLeaf = null; foreach (OctreeNode node in children) { curLeaf = node.getContainingLeaf(worldPos); if (curLeaf != null) return curLeaf; } } return null; } /// <summary> /// recursively gets the maximum depth of this tree branch /// </summary> /// <returns>the maximum tree depth contained by this branch</returns> public virtual uint getMaximumDepth() { if (children == null) return treeLevel; else { uint maxDepth = 0; uint curDepth; for (int i = 0; i < NUM_TREE_CHILDREN; i++) { curDepth = children[i].getMaximumDepth(); if (curDepth > maxDepth) maxDepth = curDepth; } return maxDepth; } } /// <summary> /// Gets an array of child Bounds that subdivide /// this tree node into 8 equal parts. /// </summary> /// <returns>an array of 8 Bounds</returns> protected virtual Bounds[] getChildNodeBounds() { Vector3 center = box.Center; Bounds[] children = new Bounds[NUM_TREE_CHILDREN]; Vector3 min = box.Min; Vector3 max = box.Max; Vector3 center = box.Center; children[0] = new Bounds(curGame, min, center); children[1] = new Bounds(curGame, new Vector3(center.X, min.Y, min.Z), new Vector3(max.X, center.Y, center.Z)); children[2] = new Bounds(curGame, new Vector3(min.X, center.Y, min.Z), new Vector3(center.X, max.Y, center.Z)); children[3] = new Bounds(curGame, new Vector3(center.X, center.Y, min.Z), new Vector3(max.X, max.Y, center.Z)); children[4] = new Bounds(curGame, new Vector3(min.X, min.Y, center.Z), new Vector3(center.X, center.Y, max.Z)); children[5] = new Bounds(curGame, new Vector3(center.X, min.Y, center.Z), new Vector3(max.X, center.Y, max.Z)); children[6] = new Bounds(curGame, new Vector3(min.X, center.Y, center.Z), new Vector3(center.X, max.Y, max.Z)); children[7] = new Bounds(curGame, center, max); return children; } /// <summary> /// Subdivides this node in the octree into 8 children /// and recursively continues octree creation. /// </summary> protected virtual void subdivide(uint maxDivisions) { uint childDepth = treeLevel + 1; // create the 8 children children = new OctreeNode[NUM_TREE_CHILDREN]; Bounds[] childrenBox = getChildNodeBounds(); // increment subdivision level and create new tree nodes for (uint i = 0; i < NUM_TREE_CHILDREN; i++) children[i] = new OctreeNode(curTree, this, curGame, childrenBox[i], childDepth, maxDivisions); } //encapsulators omitted /* * UPDATE */ public override void update(GameTime gameTime, Camera curCam, Matrix projMatrix, Matrix viewProjection) { base.update(gameTime, curCam, projMatrix, viewProjection); //update octree children nodes if (children != null) foreach (OctreeNode treeNode in children) treeNode.update(gameTime, curCam, projMatrix, viewProjection); } /* * RENDER */ /// <summary> /// recursively draws the boundaries of this tree node and its children to the specified depth /// </summary> /// <param name="depth">the maximum depth to drill into this tree and draw bounds</param> public virtual void DrawTreeBounds(uint depth) { box.Render(); if (children != null && depth > 0) { depth--; for (int i = 0; i < OctreeNode.NUM_TREE_CHILDREN; i++) children[i].DrawTreeBounds(depth); } } }
CollisionTree - The root of an octree that uses CollisionTreeNode objects instead of OctreeNodes to create spatial organization for optimizing collision detection.
(show)//CollisionTree class... public class CollisionTree : Octree { /* * CLASS PROPERTIES */ /// <summary> /// The number of searches performed for collision elements in the tree. /// This is used for preventing redundant entries from occuring in the element list. /// </summary> private uint searchCount; /// <summary> /// the root node as a CollisionTreeNode object /// </summary> private CollisionTreeNode collisionRoot; /* * CONSTRUCTOR */ /// <summary> /// Constructor for a new collision octree /// </summary> /// <param name="newGame">the game object</param> /// <param name="box">the top level collision box that contains the entire tree</param> /// <param name="newElems">the array of collideable elements to be organized by the tree</param> /// <param name="maxDepth">the maximum depth to divide the tree</param> /// <param name="minLeafVolume">a threshold that will prevent the trees leaf nodes /// from being subdivided smaller than this volume, or zero to ignore this feature.</param> public CollisionTree(TwelveCylinderGame newGame, string newName, Bounds box, CollideableElement[] newElems, uint maxDepth, float minLeafVolume) : base(newGame, newName, box) { DateTime start = DateTime.Now; //array of all true bool[] allTrue = new bool[newElems.Length]; for (int i = 0; i < allTrue.Length; i++) allTrue[i] = true; treeDepth = GetNewMaxDepth(box.Volume, minLeafVolume, maxDepth); //recursively create tree node hierarchy collisionRoot = new CollisionTreeNode(this, null, curGame, box, allTrue, newElems, 0, treeDepth); root = collisionRoot; //random tree color root.TreeColor = curGame.RandomGenerator.GetNextPalletteColor(); updateTreeData(); searchCount = 0; DateTime end = DateTime.Now; //printTreeData(end - start); } /* * COLLIDEABLE ELEMENT LISTS */ /// <summary> /// adds a new collideable element to the collision tree /// </summary> /// <param name="newElem">the element to add to the tree</param> public void AddElement(CollideableElement newElem) { collisionRoot.AddElement(newElem); } /// <summary> /// removes the specified collideable element from the collision tree /// </summary> /// <param name="elem">the element to remove from the tree</param> public void RemoveElement(CollideableElement xElem) { collisionRoot.RemoveElement(xElem); } /// <summary> /// updates which tree nodes the element is in /// </summary> /// <param name="elem">an element that may already be in the tree</param> public void UpdateElement(CollideableElement elem) { elem.RemoveFromAllNodes(); collisionRoot.AddElement(elem); } /// <summary> /// gets the collideable elements that intersect /// with the specified bounding box /// </summary> /// <param name="testBox">a box to test for collisions</param> /// <param name="elements">the output list of collideable elements</param> public void GetElements(Bounds testBox, ref List<CollideableElement> elements) { collisionRoot.GetElements(testBox, ref elements, searchCount++); } /// <summary> /// gets all collideable elements currently in the tree /// </summary> /// <param name="elements">the output list of elements</param> public void GetAllElements(ref List<CollideableElement> elements) { collisionRoot.GetAllElements(ref elements, searchCount++); } /* * BOX INTERSECT */ /// <summary> /// Find the first (if any) collision between the specified moving /// collision box and the collideable elements in this tree. /// </summary> /// <param name="boxData">the box to check for collisions /// defined in the world coordinate system</param> /// <param name="collisionDistance">output distance from starting /// position to collision point</param> /// <param name="collisionPosition">output position /// at which the collision occured</param> /// <param name="collisionNormal">output normal of the /// surface that the box collided with</param> /// <returns>returns true if an intersection occured</returns> public bool BoxIntersect(MovingBoxData boxData, out float collisionDistance, out Vector3 collisionPosition, out Vector3 collisionNormal) { //default output of no interesection collisionDistance = boxData.OffsetLength; collisionPosition = boxData.WorldEnd; collisionNormal = Vector3.Zero; //get the list of collideable elements that the box may have collided with List<CollideableElement> elems = new List<CollideableElement>(); collisionRoot.GetElements(boxData.ColliderVolume, ref elems, searchCount++); bool collided = false; float distance; Vector3 position; Vector3 normal; //check for collision between moving box and collideable elements foreach (CollideableElement elem in elems) { if (elem.BoxIntersect(boxData, out distance, out position, out normal)) { //intersection found if (distance < collisionDistance) { //current intersect distance is less than previous collisionDistance = distance; collisionPosition = position; collisionNormal = normal; collided = true; } } } return collided; } }
CollisionTreeNode - The CollisionTreeNode class replaces the OctreeNode class in a CollisionTree. In addition to the spatial definition of the OctreeNode, the CollisionTreeNode stores a list of CollideableElements which are at least partially inside the space of this node. This allows the tree to be quickly searched for CollideableElements by their spatial locations.
(show)//CollisionTreeNode class... public class CollisionTreeNode : OctreeNode { /* * CLASS PROPERTIES */ /// <summary> /// list with elements included in the node (only created on leaf nodes) /// </summary> private List<CollideableElement> elems; /* * CONSTRUCTOR */ /// <summary> /// Recursive constructor to create a new /// collision tree node and children. /// </summary> /// <param name="newTree">A collision tree object that is the root of the tree</param> /// <param name="newParent">the collision tree node that is the parent to this one</param> /// <param name="newGame">the TwelveCylinderGame object</param> /// <param name="box">the collision box that defines the new tree node</param> /// <param name="possibleElems">an array of bools indicating if each element in /// the newElems array was contained by the parent tree node</param> /// <param name="newElems">the collideable element array that is contained by this tree</param> /// <param name="depth">the current depth in the tree of this node</param> /// <param name="maxDivisions">the subdivision level of the new tree node where 0 is a leaf node</param> public CollisionTreeNode(Octree newTree, OctreeNode newParent, TwelveCylinderGame newGame, Bounds box, bool[] possibleElems, CollideableElement[] newElems, uint depth, uint maxDivisions) : base(newTree, newParent, newGame, box, depth) { uint numElements = 0; // if subdivision needed if (depth < maxDivisions) { bool[] contained = new bool[newElems.Length]; for (int i = 0; i < newElems.Length; i++) { if (!possibleElems[i]) contained[i] = false; //parent doesn't contain the element else if (newElems[i].box.BoxOverlap(box)) { contained[i] = true; //this tree node contains the element numElements++; } else contained[i] = false; //this tree node does not contain the element } // if collision tree node contains one or zero // collideable elements we can stop subdivision if (numElements == 1) { for (int i = 0; i < contained.Length; i++) if (contained[i]) { this.AddElement(newElems[i]); //add the one element and stop return; } } else if (numElements == 0) return; //no elements in the node, we can stop subdivide(contained, newElems, maxDivisions); } else { //add collideable elements to leaf node for (int i = 0; i < newElems.Length; i++) { if (possibleElems[i]) this.AddElement(newElems[i]); } } } /* * METHODS */ /// <summary> /// subdivides this collision octree node into 8 children /// </summary> /// <param name="possibleElems">the array of bools that describe which /// collideable elements are contained by this tree node1</param> /// <param name="newElems">the elements being added to the tree</param> /// <param name="maxDivisions">the maximum subdivision level to drill down to</param> public virtual void subdivide(bool[] possibleElems, CollideableElement[] newElems, uint maxDivisions) { uint childDepth = treeLevel + 1; // create the 8 children children = new CollisionTreeNode[NUM_TREE_CHILDREN]; //octree subdivisons Bounds[] childrenBox = getChildNodeBounds(); // increment subdivision level and create new tree nodes for (uint i = 0; i < NUM_TREE_CHILDREN; i++) children[i] = new CollisionTreeNode(curTree, this, curGame, childrenBox[i], possibleElems, newElems, childDepth, maxDivisions); } /* * COLLIDABLE ELEMENT LIST */ /// <summary> /// recursive method to add a collidable element to the tree /// </summary> /// <param name="newElem">the collideable element to add to the tree</param> public void AddElement(CollideableElement newElem) { // if element does not intersect with node, return if (newElem.box.BoxOverlap(box) == false) return; if (children == null) { //only add collidable elements to leaf nodes... if (elems == null) //if no elements list, add one elems = new List<CollideableElement>(); // add element to list elems.Add(newElem); newElem.AddTreeNode(this); } else { // if not a leaf, add element to all children foreach (CollisionTreeNode child in children) child.AddElement(newElem); } } /// <summary> /// removes a collidable element from this node /// </summary> /// <param name="e">the collideable element to remove</param> public void RemoveElement(CollideableElement e) { if (elems != null) elems.Remove(e); } /// <summary> /// Recursive function to get all elements that intersect the specified bounding box. /// </summary> /// <param name="elemList">the output list of elements with intersecting bounding boxes</param> /// <param name="testBox">the bounding box to test for intersection</param> /// <param name="searchCount">the ID representing the current iteration of the element search function.</param> public void GetElements(Bounds testBox, ref List<CollideableElement> elemList, uint searchCount) { // if selection box does not intersect node box, return if (!testBox.BoxOverlap(box)) return; //test box does not overlap with tree node's box if (elems != null) { //leaf node that contains elements foreach (CollideableElement elem in elems) { // elements can be repeated in many nodes // only add element to selection list if not already // added by another node in this same recursion if (elem.LastSearchId < searchCount) { // if selection box intersect the element box if (elem.box.BoxOverlap(testBox)) elemList.Add(elem); // add element to selection list // set this recuse id to prevent duplicate results elem.LastSearchId = searchCount; } } } else if (children != null) { // if not a leaf node, recurse to all children foreach (CollisionTreeNode child in children) child.GetElements(testBox, ref elemList, searchCount); } }
CollideableElement - This abstract class is extended by any type of primitive geometry that can be tested for collisions with moving points or boxes. In this sample it is only extended by the CollisionTriangle class.
(show)//CollideableElement class... public abstract class CollideableElement : Node { /* * CLASS PROPERTIES */ /// <summary> /// flag to indicate if the collideable /// element needs it's definition updated /// </summary> public bool NeedsUpdate; /// <summary> /// bounding box of collideable element /// </summary> public Bounds box; /// <summary> /// all tree nodes in which this /// dynamic collidable element is in /// </summary> private List<CollisionTreeNode> treeNodes; /// <summary> /// recurse id used to compute selections /// without getting redundant elements /// </summary> private uint mLastSearchId; /* * CONSTRUCTOR */ /// <summary> /// constructor for a collideable element /// </summary> public CollideableElement(TwelveCylinderGame newGame) : base(newGame) { treeNodes = new List<CollisionTreeNode>(); mLastSearchId = 0; } /* * ABSTRACT METHODS */ /// <summary> /// updates the bounding collision box definition /// to ensure it exactley contains the element /// </summary> public abstract void updateCollisionBox(); /// <summary> /// intersect a moving point with the element /// </summary> public abstract void PointIntersect(ref MovingPointData pointData); /// <summary> /// intersects a moving box with the element /// </summary> public abstract bool BoxIntersect(MovingBoxData boxData, out float collisionDistance, out Vector3 collisionPosition, out Vector3 collisionNormal); /* * TREE NODE LIST */ /// <summary> /// adds a tree node to this collidable element's containing list /// </summary> public virtual void AddTreeNode(CollisionTreeNode treeNode) { treeNodes.Add(treeNode); } /// <summary> /// removes a single tree node from this collidable element's containing list /// </summary> public virtual void RemoveTreeNode(CollisionTreeNode xTreeNode) { treeNodes.Remove(xTreeNode); } /// <summary> /// Removes this element from the tree /// </summary> public void RemoveFromAllNodes() { // remove element from all nodes it is associated with foreach (CollisionTreeNode n in treeNodes) n.RemoveElement(this); treeNodes.Clear(); } }
CollisionModel - A data structure to hold a list of CollisionMesh objects with quick access geometry data.
(show)//CollisionModel class public class CollisionModel : AccessibleModel { /// <summary> /// number of divisions to apply to the octree /// </summary> private uint maxTreeDivisions; /// <summary> /// the threshold limit for leaf node volume /// </summary> private float minTreeNodeVolume; /// <summary> /// constructor with a default XNA model located in the specified file location /// </summary> /// <param name="newName">a name for the object</param> /// <param name="newGame">the game object</param> /// <param name="newLeafNodeVolume"></param> /// <param name="maxTreeDivisions">the maximum number of times to subdivide the octree</param> /// <param name="newModelFile">the path to a model file to load into this accessible model</param> public CollisionModel(string newName, TwelveCylinderGame newGame, float newLeafNodeVolume, uint newMaxTreeDivisions, string newModelFile) : base(newName, newGame, newModelFile) { minTreeNodeVolume = newLeafNodeVolume; maxTreeDivisions = newMaxTreeDivisions; createCollisionTrees(minTreeNodeVolume); } /// <summary> /// Creates an array of meshes from the (XNA class) input Model. /// This method overrides its parent's method and creates CollisionMesh /// objects instead of AccessibleMesh objects. /// </summary> /// <param name="newModel">the XNA Model object</param> protected override void initFromModel(Model newModel) { meshCount = newModel.Meshes.Count; triangleCount = 0; vertexCount = 0; mMeshes = new CollisionMesh[meshCount]; for (int i = 0; i < meshCount; i++) { //create collision mesh objects which make up this collision model... mMeshes[i] = new CollisionMesh(newModel.Meshes[i].Name, curGame, newModel.Meshes[i]); this.addChild(mMeshes[i]); //loads world position data //sum number of primitives triangleCount += mMeshes[i].FaceCount; vertexCount += mMeshes[i].VertexCount; } } /// <summary> /// create collision tree definitions for each mesh in this model /// </summary> protected virtual void createCollisionTrees(float newLeafNodeVolume) { foreach(CollisionMesh mesh in mMeshes) mesh.createCollisionTree(maxTreeDivisions, newLeafNodeVolume); } //encapsulators omitted /// <summary> /// gets the collision mesh at the specified index /// </summary> /// <param name="index">a mesh index</param> /// <returns>the collision mesh</returns> public CollisionMesh getCollisionMesh(int index) { return (mMeshes[index] as CollisionMesh); } /// <summary> /// find the first (if any) collision between the /// specified moving box and this CollisionModel /// </summary> /// <param name="boxData">input description of the moving box to test for collisions</param> /// <param name="collisionDistance">output distance from box's starting position to collision point</param> /// <param name="collisionPosition">output position at which the collision occured</param> /// <param name="collisionNormal">output normal of the surface at the collision point</param> /// <returns>returns true if an intersection occured</returns> public bool BoxIntersect(MovingBoxData boxData, out float collisionDistance, out Vector3 collisionPosition, out Vector3 collisionNormal) { collisionDistance = boxData.OffsetLength; collisionPosition = boxData.WorldEnd; collisionNormal = Vector3.Zero; if (mMeshes == null || mMeshes.Length == 0) return false; bool collision = false; float distance; Vector3 position; Vector3 normal; //find first collision occurence foreach (CollisionMesh mesh in mMeshes) { if (mesh.Tree.BoxIntersect(boxData, out distance, out position, out normal)) { //intersection found if (distance < collisionDistance) { //current intersect distance //is less than any previous collisionDistance = distance; //output distance collisionPosition = position; //output position collisionNormal = normal; //output normal at collision point collision = true; } } } return collision; } //point intersection omitted... }
CollisionMesh - The CollisionMesh class stores a list of CollisionTriangle objects that compose the mesh. The mesh keeps a quick access array of vertex positions in world coordinates that is used to define the CollisionTriangles. This class also stores the CollisionTree that contains this mesh.
(show)//CollisionMesh class... public class CollisionMesh : AccessibleMesh { /* * CLASS PROPERTIES */ /// <summary> /// the collision tree for optimized collision detection /// </summary> protected CollisionTree collisionTree; /// <summary> /// the array of vertices in world coordinates /// </summary> private Vector3[] worldPositions; /// <summary> /// the array of triangular collidable faces that compose this mesh /// </summary> private CollisionTriangle[] collisionTris; /// <summary> /// a bounding box defined in world aligned coordinate space /// </summary> private BoundingBox worldBounds; /* * CONSTRUCTORS */ /// <summary> /// Constructor for a collideable mesh. This constructor /// simply relies on its parent class's constructor. /// </summary> /// <param name="modelName"></param> /// <param name="newGame"></param> /// <param name="model"></param> public CollisionMesh(string meshName, TwelveCylinderGame newGame, ModelMesh mesh) : base(meshName, newGame, mesh) { } /// <summary> /// gets the world position of the vertex at index i /// </summary> /// <param name="i">a vertex index</param> /// <returns>the world coordinate position of the vertex</returns> public override Vector3 getWorldPosition(int i) { return worldPositions[i]; } /* * COLLISION DATA UPDATES */ /// <summary> /// update the array of collision faces to the current world coordinates /// </summary> public void updateCollisionFaces() { foreach(CollisionTriangle triangle in collisionTris) triangle.updateAll(); } /// <summary> /// updates the array of vertex positions in world coordinates /// </summary> public void updateWorldPositions() { if (worldPositions == null || worldPositions.Length != vertices.Length) worldPositions = new Vector3[vertices.Length]; //create array of vertices //transform each vertex in mesh from local coordinates to worlds coordinates for (int i = 0; i < vertices.Length; i++) worldPositions[i] = Vector3.Transform(vertices[i].Position, WorldMatrix); //update the world bounding box worldBounds = BoundingBox.CreateFromPoints(worldPositions); } /// <summary> /// Creates the collision tree used for /// collision detection for this mesh. /// </summary> /// <param name="maxNumDivisions">the maximum number of divisions for the tree</param> /// <param name="minTreeNodeVolume">the minimum volume threshold for a tree node</param> public void createCollisionTree(uint maxNumDivisions, float minTreeNodeVolume) { if (collisionTree != null) collisionTree.unload(false); //unload existing collision tree //create new collision tree definition collisionTree = new CollisionTree(curGame, this.Name + " collision tree", new Bounds(curGame, worldBounds.Min, worldBounds.Max), collisionTris, maxNumDivisions, minTreeNodeVolume); this.addChild(collisionTree); //add the collision tree to scene hiearchy } /// <summary> /// Creates the array of collideable faces from the /// array of vertices and input vertex index array. /// </summary> /// <param name="indices">the array of vertex indices taht define the mesh triangles</param> /// <remarks>called from within the SimpleMesh parseMesh method</remarks> protected override void createTriangleDefinitions(int[] indices) { //collision triangles defined used world coordinate vertices updateWorldPositions(); //create new array of collision triangles if(collisionTris == null || collisionTris.Length != triangleCount) collisionTris = new CollisionTriangle[triangleCount]; int faceIndex = 0; //create each collision triangle in this mesh for (int i = 0; i < indices.Length; i += 3) collisionTris[faceIndex++] = new CollisionTriangle(curGame, indices[i], indices[i + 1], indices[i + 2], this); } }
CollisionTriangle - This class stores a single triangular face in a CollisionMesh. This class performs the actual mathematics of detecting and describing collisions between points or boxes and a triangle.
(show)//CollisionTriangle class... public class CollisionTriangle : CollideableElement { /* * CONSTANTS */ /// <summary> /// cosine of 135 degrees /// </summary> public const float COS_135 = -0.707106781f; /// <summary> /// cosine of 45 degrees /// </summary> public const float COS_45 = 0.707106781f; /// <summary> /// the buffer added to the triangle's bounding box /// </summary> public const float TRIANGLE_BOUNDS_BUFFER = 0.001f; /* * CLASS PROPERTIES */ /// <summary> /// index of the vertices in the accesible mesh structure /// </summary> private int[] vertexIndeces; /// <summary> /// the positions of the vertices in world coordinates /// </summary> private Vector3[] pos; /// <summary> /// the area of the triangle /// </summary> public float Area; /// <summary> /// double the area of the triangle /// </summary> public float DoubleArea; /// <summary> /// the normal of the triangle surface /// </summary> public Vector3 FaceNormal; /// <summary> /// the centroid of the face /// </summary> public Vector3 Centroid; /// <summary> /// the accessible mesh structure this traingle is associated with /// </summary> private CollisionMesh Mesh; /// <summary> /// the array of 3 collideable edges of this triangle /// </summary> private CollisionEdge[] Edges; /* * CONSTRUCTOR */ /// <summary> /// constructor for a new mesh triangles /// </summary> /// <param name="newIndex1">the index in the mesh object of the first vertex of the triangle</param> /// <param name="newIndex2">the index in the mesh object of the second vertex of the triangle</param> /// <param name="newIndex3">the index in the mesh object of the third vertex of the triangle</param> /// <param name="newMesh">the accessible mesh object to which this triangle belongs</param> /// <remarks>vertices should be defined in counter-clockwise order</remarks> public CollisionTriangle(TwelveCylinderGame newGame, int newIndex1, int newIndex2,int newIndex3, CollisionMesh newMesh) : base(newGame) { Mesh = newMesh; pos = new Vector3[3]; vertexIndeces = new int[3] { newIndex1, newIndex2, newIndex3 }; updateVertexPositions(); updateFaceNormal(); updateCollisionBox(); //edge definitions Edges = new CollisionEdge[3]; Edges[0] = new CollisionEdge(Mesh, pos[0], pos[1]); Edges[1] = new CollisionEdge(Mesh, pos[1], pos[2]); Edges[2] = new CollisionEdge(Mesh, pos[2], pos[0]); } /* * PARAMETER UPDATES */ /// <summary> /// updates vertex positions, face normal /// and collision box definitions /// </summary> public void updateAll() { updateVertexPositions(); updateEdges(); updateFaceNormal(); updateCollisionBox(); } /// <summary> /// updates the vertex world positions /// from the collision mesh object /// </summary> public void updateVertexPositions() { pos[0] = Mesh.getWorldPosition(vertexIndeces[0]); pos[1] = Mesh.getWorldPosition(vertexIndeces[1]); pos[2] = Mesh.getWorldPosition(vertexIndeces[2]); } public void updateEdges() { Edges[0].WorldPosition1 = pos[0]; Edges[0].WorldPosition2 = pos[1]; Edges[0].updateEdge(); Edges[1].WorldPosition1 = pos[1]; Edges[1].WorldPosition2 = pos[2]; Edges[1].updateEdge(); Edges[2].WorldPosition1 = pos[2]; Edges[2].WorldPosition2 = pos[0]; Edges[2].updateEdge(); } /// <summary> /// updates the triangles face normal direction /// based on its vertex positions /// </summary> public void updateFaceNormal() { Vector3 v2 = (pos[2] - pos[0]); Vector3 v1 = (pos[1] - pos[0]); Vector3 cross = Vector3.Cross(v2, v1); DoubleArea = cross.Length(); Area = DoubleArea / 2.0f; Centroid = (pos[0] + pos[1] + pos[2]) / 3.0f; FaceNormal = cross / DoubleArea; } /// <summary> /// updates the object oriented /// bounding box of this triangle /// </summary> public override void updateCollisionBox() { box = Bounds.FromPoints(curGame, CollisionTriangle.TRIANGLE_BOUNDS_BUFFER, pos[0], pos[1], pos[2]); } /* * EDGE-EDGE INTERSECTION */ /// <summary> /// intersect BoxEdge moving in direction (dir) colliding with edge (p3,p4) /// return true on a collision with collision distance (dist) and intersection point (ip) /// </summary> /// <param name="boxEdge">the moving box edge definition</param> /// <param name="faceEdge">the static edge of the triangle</param> /// <param name="dist">the output distance from the box start position at which the collision occured</param> /// <param name="intersectPos">the output position at which the intersection occured</param> /// <returns>true if a collision occured, false otherwise</returns> public static bool EdgeIntersect(BoxEdge boxEdge, CollisionEdge faceEdge, out float paramT, out Vector3 intersectPos) { paramT = 0; intersectPos = Vector3.Zero; // if colliding edge (p3,p4) does not cross plane return no collision // same as if p3 and p4 on same side of plane return 0 float temp = (Vector3.Dot(boxEdge.PlaneDir, faceEdge.WorldPosition1) - boxEdge.PlaneW) * (Vector3.Dot(boxEdge.PlaneDir, faceEdge.WorldPosition2) - boxEdge.PlaneW); if (temp > 0) return false; // if colliding edge (p3,p4) and plane are paralell return no collision //v2.Normalize(); temp = Vector3.Dot(boxEdge.PlaneDir, faceEdge.EdgeDir); if (temp == 0) return false; // compute intersection point of plane and colliding edge (p3,p4) intersectPos = faceEdge.WorldPosition1 + (faceEdge.EdgeDir * ((boxEdge.PlaneW - Vector3.Dot(boxEdge.PlaneDir, faceEdge.WorldPosition1)) / temp)); uint i = XNAHelper.GetLargestAbsComponent(boxEdge.PlaneDir); // remove a component from each vector to simply to a 2D problem Vector2 p12d = XNAHelper.Vector3RemoveComponent(boxEdge.WorldPosition1, i); Vector2 v12d = XNAHelper.Vector3RemoveComponent(boxEdge.EdgeVector, i); Vector2 ip2d = XNAHelper.Vector3RemoveComponent(intersectPos, i); Vector2 dir2d = XNAHelper.Vector3RemoveComponent(boxEdge.EdgeMotion, i); // compute distance of intersection from line to line paramT = (v12d.X * (ip2d.Y - p12d.Y) - v12d.Y * (ip2d.X - p12d.X)) / (v12d.X * dir2d.Y - v12d.Y * dir2d.X); if (paramT < 0) return false; // compute intesection point along edge path intersectPos -= paramT * boxEdge.EdgeMotion; // check if intersection point is between egde vertices temp = Vector3.Dot(boxEdge.WorldPosition1 - intersectPos, boxEdge.WorldPosition2 - intersectPos); if (temp >= 0) return false; // no collision return true; // collision found! } /* * RAY-TRIANGLE INTERSECT */ /// <summary> /// ray-triangle intersect from /// http://www.graphics.cornell.edu/pubs/1997/MT97.pdf /// </summary> /// <param name="rayOrigin"> origin of the ray</param> /// <param name="rayDirection">direction of the ray</param> /// <param name="dist">output distance to intersection</param> /// <returns></returns> public bool RayTriangleIntersect(Vector3 rayOrigin, Vector3 rayDirection, out float dist) { Vector3 edge1 = pos[1] - pos[0]; Vector3 edge2 = pos[2] - pos[0]; Vector3 tVector, pVector, qVector; float det, invDet; dist = 0; //parametric distance pVector = Vector3.Cross(rayDirection, edge2); det = Vector3.Dot(edge1, pVector); if (det > -0.00001f) //ray is parallel to triangle return false invDet = 1.0f / det; tVector = rayOrigin - pos[0]; float u = Vector3.Dot(tVector, pVector) * invDet; if (u < -0.0001f || u > 1.0001f) //intersection with plane of triangle is off the face return false; qVector = Vector3.Cross(tVector, edge1); float v = Vector3.Dot(rayDirection, qVector) * invDet; if (v < -0.0001f || u + v > 1.0001f) //intersection with plane of triangle is off the face return false; //intersect distance dist = Vector3.Dot(edge2, qVector) * invDet; if (dist <= 0) //intersection is behind ray origin return false; return true; //intersection occured } /* * COLLIDEABLE ELEMENT INTERSECTION TESTS */ /// <summary> /// ray intersect face and return /// intersection distance, point and normal /// </summary> /// <param name="pointData">point movement data that /// describes movement of point to test for intersection</param> public override void PointIntersect(ref MovingPointData pointData) { float dist; if (this.RayTriangleIntersect(pointData.StartPosition, pointData.MoveDirection, out dist)) { if (dist < pointData.CollisionDistance) pointData.CollisionOccured(this, pointData.StartPosition + (pointData.MoveDirection * dist), this.FaceNormal, dist); } } /// <summary> /// box intersect face and return intersection distance, point and normal /// </summary> /// <param name="boxData"></param> /// <param name="collisionDistance">output distance to intersection</param> /// <param name="collisionPosition">output position of intersection</param> /// <param name="collisionNormal">output normal of intersection</param> /// <returns>true if an intersection occured</returns> public override bool BoxIntersect(MovingBoxData boxData, out float collisionDistance, out Vector3 collisionPosition, out Vector3 collisionNormal) { collisionDistance = float.MaxValue; collisionPosition = boxData.WorldStart; collisionNormal = Vector3.Zero; bool collided = false; //cull triangle if we're moving in the same direction as the triangle's normal if (Vector3.Dot(this.FaceNormal, boxData.OffsetDirection) > 0) return false; uint i, j; float distance; Vector3 position; float tnear, tfar; /* * EDGE TO EDGE */ for (i = 0; i < 12; i++) { //for each edge of the box // skip edges with normal more than 135 degrees away from moving direction if (Vector3.Dot(Bounds.edgeNormals[i], boxData.OffsetDirection) < CollisionTriangle.COS_135) continue; for (j = 0; j < Edges.Length; j++) { //for each edge of the triangle test for intersection with the current box edge if (CollisionTriangle.EdgeIntersect(boxData.BoxEdges[i], Edges[j], out distance, out position)) { //intersection occured if (distance < collisionDistance) { //intersection is closer than previous distance collisionDistance = distance; collisionPosition = position; collisionNormal = Vector3.Normalize(Vector3.Cross( boxData.BoxEdges[i].WorldPosition2 - boxData.BoxEdges[i].WorldPosition1, -Edges[j].EdgeVector)); if (Vector3.Dot(boxData.OffsetDirection, collisionNormal) > 0) collisionNormal = -collisionNormal; collided = true; } } } } /* * TRIANGLE VERTICES WITH BOX */ BoxFace boxFace; for (i = 0; i < 3; i++) { //for each triangle vertex... //intersect with collision box boxFace = boxData.WorldBox.RayIntersect(new OptimizedRay(pos[i], -boxData.OffsetDirection), out tnear, out tfar); if (boxFace != BoxFace.None) { //ray hits the bounds if (tnear < collisionDistance) { //closest distance collisionDistance = tnear; collisionPosition = pos[i]; collisionNormal = -Bounds.faceNormals[(int)boxFace]; collided = true; } } } /* * BOX VERTICES WITH TRIANGLE */ float dist; for (i = 0; i < 8; i++) { // cull vertices with normal more than 135 degree from moving direction if (Vector3.Dot(Bounds.vertexNormals[i], boxData.OffsetDirection) < CollisionTriangle.COS_135) continue; if (this.RayTriangleIntersect(boxData.WorldBoxVerts[i], boxData.OffsetDirection, out dist)) { if (dist < collisionDistance) { collisionDistance = dist; collisionPosition = (boxData.OffsetDirection * dist) + boxData.WorldBoxVerts[i]; collisionNormal = this.FaceNormal; //normal of triangle collided = true; } } } return collided; } }