Ellipsoid Collision Detection System

User Code & Projects
1

I wrote a pretty simple ellipsoid collision detection and response system that is easily pluggable into any application.  It is based on the concepts and code found at http://www.peroxide.dk/papers/collision/collision.pdf.  It includes triangle level collisions, sliding, gravity and makes use of the existing JME nodes and collision data (OOBB's).



To use it, create an instance of the MovingEllipseCollision class provided below using the world-dimensions of the ellipse to use as your collision body.  On each update, modify the vector's returned by getEllipseCenter() and getEllipseVelocity() to represent the world coordinate center and velocity of your collision body.  Then call moveEllipseWithCollisions passing the Node which contains all the collideable objects, the interpolation to use for the velocity, and booleans indicating whether or not to use sliding and/or gravity.  The end-point location will now be found in getEllipseCenter().  I have tested this a bit, but I'm sure there are bugs or improvements which can be made.  Because of the message size here, I have split the one class into multiple posts, they should be combined into one file for use.  Please feel free to use this if needed, or include it in this or other projects.



import com.jme.bounding.BoundingSphere;
import com.jme.bounding.BoundingVolume;
import com.jme.bounding.OBBTree;
import com.jme.math.FastMath;
import com.jme.math.Plane;
import com.jme.math.Quaternion;
import com.jme.math.Triangle;
import com.jme.math.Vector3f;
import com.jme.scene.Node;
import com.jme.scene.Spatial;
import com.jme.scene.TriMesh;

/**
 * Class for applying collision detection, response and gravity to a scene based on an ellipsoid representation.
 *
 * Implementation of algorithm found at: http://www.peroxide.dk/papers/collision/collision.pdf
 */
public class MovingEllipseCollision {
   private Vector3f ellipseDimensions = new Vector3f();
   private Vector3f ellipseSpaceScale = new Vector3f();
   private Vector3f ellipseCenter = new Vector3f();
   private Vector3f ellipseVelocity = new Vector3f();
   
   private float veryCloseDistance = 0.001f;
   private Vector3f gravityVector = new Vector3f(0, -40, 0);
   private int recursionDepth = 5;
   
   //collision internal variables
   private Vector3f ellipseSpaceCenter = new Vector3f();
   private Vector3f ellipseSpaceVelocity = new Vector3f();
   private Vector3f ellipseSpaceVelocityNormalized = new Vector3f();
   private Vector3f ellipseSpaceVelocityBuffer = new Vector3f();
   
   private BoundingSphere worldSpaceBounds = new BoundingSphere();
   
   private float resultNearestCollisionDistance = 100000.0f;
   private Vector3f resultCollisionPoint = new Vector3f();
   private Vector3f resultCollisionNormal = new Vector3f();
   private boolean hasCollision = false;
   
   /**
    * Constructor for creating the collision system.  Takes the dimensions of the ellipsoid to test against the scene.
    *
    * @param dimensions The dimensions of the ellipsoid (in world space) to test against the scene.
    */
   public MovingEllipseCollision(Vector3f dimensions) {
      setEllipseDimensions(dimensions);
   }
   
   /**
    * Sets the sliding recursion depth to use for collisions.
    *
    * @param depth The new sliding recursion depth.
    */
   public void setRecursionDepth(int depth) {
      recursionDepth = depth;
   }
   
   /**
    * Sets the dimensions of the collision ellipse
    *
    * @param dims dimensions of the collision ellipse
    */
   public void setEllipseDimensions(Vector3f dims) {
      ellipseDimensions.set(dims);
      ellipseSpaceScale.set(1 / dims.x, 1 / dims.y, 1 / dims.z);
   }
   
   /**
    * Returns the vector used as the base gravity vector.  This will be multiplied by the interpolation to determine the actual per-frame gravity.
    *
    * @return A Vector3f representing the gravity.
    */
   public Vector3f getGravityVector() {
      return gravityVector;
   }
   
   /**
    * This distance which should be used to determine when we are "close" to an object.  If this is set incorrectly, we may appear to pass through
    * certain objects.  The default value is 0.001f
    *
    * @param dist The distance to set as the veryCloseDistance
    */
   public void setVeryCloseDistance(float dist) {
      veryCloseDistance = 0.001f;
   }
   
   /**
    * The center of the ellipse in world coordinates.  Set the center here before calling the moveEllipseWithCollisions method.  Retreive the
    * resulting position from this vector after the collisions occur.
    *
    * @return The Vector which represents the current ellipse center.
    */
   public Vector3f getEllipseCenter() {
      return ellipseCenter;
   }
   
   /**
    * Returns the velocity of the ellipse, in world coordinates.
    *
    * @return The Vector which represents the current ellipse velocity.
    */
   public Vector3f getEllipseVelocity() {
      return ellipseVelocity;
   }
   
   /**
    * Reset the collision result members
    */
   private void resetResults() {
      resultNearestCollisionDistance = 100000.0f;
      hasCollision = false;
   }
   
   /**
    * Check for collisions against the given node.
    *
    * @param collisionNode
    */
   private void checkEllipseCollision(Node collisionNode) {
      //reset our results
      resetResults();
      
      //create a bounding volume for the start/end points of our ellipse for quick culling against the OBBTree
      float minX, maxX, minY, maxY, minZ, maxZ;
      if (ellipseVelocity.x > 0) {
         minX = ellipseCenter.x - ellipseDimensions.x;
         maxX = ellipseCenter.x + ellipseVelocity.x + ellipseDimensions.x;
      } else {
         maxX = ellipseCenter.x + ellipseDimensions.x;
         minX = ellipseCenter.x + ellipseVelocity.x - ellipseDimensions.x;         
      }

      if (ellipseVelocity.y > 0) {
         minY = ellipseCenter.y - ellipseDimensions.y;
         maxY = ellipseCenter.y + ellipseVelocity.y + ellipseDimensions.y;
      } else {
         maxY = ellipseCenter.y + ellipseDimensions.y;
         minY = ellipseCenter.y + ellipseVelocity.y - ellipseDimensions.y;         
      }

      if (ellipseVelocity.z > 0) {
         minZ = ellipseCenter.z - ellipseDimensions.z;
         maxZ = ellipseCenter.z + ellipseVelocity.z + ellipseDimensions.z;
      } else {
         maxZ = ellipseCenter.z + ellipseDimensions.z;
         minZ = ellipseCenter.z + ellipseVelocity.z - ellipseDimensions.z;         
      }
      
      float xRad = (maxX - minX)  / 2;
      float yRad = (maxY - minY)  / 2;
      float zRad = (maxZ - minZ)  / 2;
      worldSpaceBounds.radius = Math.max(Math.max(xRad, yRad), zRad);
      worldSpaceBounds.getCenter().set(minX + xRad, minY + yRad, minZ + zRad);
         
      checkEllipseSpaceCollision(collisionNode, ellipseSpaceCenter, ellipseSpaceVelocity,
            ellipseSpaceScale, worldSpaceBounds);      
   }
   
   private final static Vector3f cescA = new Vector3f(), cescB = new Vector3f(), cescC = new Vector3f(), cescD = new Vector3f(), cescE = new Vector3f();
   /**
    * Check the ellipse collision against an OBBTree
    *
    * @param parentMesh The mesh which owns the OBBTree
    * @param collisionTree The OBBTree to traverse
    * @param ellipseSpaceCenter The ellipse space center for the ellipse
    * @param ellipseSpaceVelocity The ellipse space velocity for the ellipse
    * @param ellipseSpaceScale The scale of ellipse space
    * @param worldSpaceBounds The bounds of the movement area in world space
    */
   private void checkEllipseSpaceCollision(TriMesh parentMesh, OBBTree collisionTree, Vector3f ellipseSpaceCenter, Vector3f ellipseSpaceVelocity, Vector3f ellipseSpaceScale, BoundingVolume worldSpaceBounds) {
        collisionTree.bounds.transform(
              parentMesh.getWorldRotation(),
              parentMesh.getWorldTranslation(),
              parentMesh.getWorldScale(),
                collisionTree.worldBounds);      
       if (!collisionTree.worldBounds.intersects(worldSpaceBounds)) {
          return;
       }
       
       OBBTree left = collisionTree.getLeftTree();
       OBBTree right = collisionTree.getRightTree();
       if (left != null) {
          checkEllipseSpaceCollision(parentMesh, left, ellipseSpaceCenter, ellipseSpaceVelocity,
                ellipseSpaceScale, worldSpaceBounds);
          checkEllipseSpaceCollision(parentMesh, right, ellipseSpaceCenter, ellipseSpaceVelocity,
                ellipseSpaceScale, worldSpaceBounds);          
       } else {
          //this is a leaf, do the actual test          
            Quaternion worldRot = parentMesh.getWorldRotation();
            Vector3f worldScale = parentMesh.getWorldScale();
            Vector3f worldTrans = parentMesh.getWorldTranslation();

            for (int i = 0; i < collisionTree.getTriangleCount(); i++) {
               Triangle tri = collisionTree.getTriangle(i);
             
               worldRot.mult(tri.get(0), cescA).multLocal(worldScale).addLocal(
                     worldTrans);
               worldRot.mult(tri.get(1), cescB).multLocal(worldScale).addLocal(
                     worldTrans);
               worldRot.mult(tri.get(2), cescC).multLocal(worldScale).addLocal(
                     worldTrans);
               
               //we now have a triangle in tempVa, tempVb, tempVc which is in world coordinates

               //move the triangle into collision space
               cescA.multLocal(ellipseSpaceScale);
               cescB.multLocal(ellipseSpaceScale);
               cescC.multLocal(ellipseSpaceScale);
               
               float intersectionDistance = movingUnitSphereTriIntersection(ellipseSpaceCenter, ellipseSpaceVelocity, cescA, cescB, cescC, cescD, cescE);
               
               //if we found a collision better than our current best, store it instead
               if (intersectionDistance < resultNearestCollisionDistance) {
                  resultNearestCollisionDistance = intersectionDistance;
                  resultCollisionPoint.set(cescD);
                  resultCollisionNormal.set(cescE);
                  hasCollision = true;
               }
            }           
       }
   }
   
   /**
    * Attemps to collide the moving ellipes against a spacial.  Only TriMesh spacials are checked.
    *
    * @param collisionSpatial The spacial to check for collisions
    * @param ellipseSpaceCenter The ellipse space center for the ellipse
    * @param ellipseSpaceVelocity The ellipse space velocity for the ellipse
    * @param ellipseSpaceScale The scale of ellipse space
    * @param worldSpaceBounds The bounds of the movement area in world space
    */
   private void checkEllipseSpaceCollision(Spatial collisionSpatial, Vector3f ellipseSpaceCenter, Vector3f ellipseSpaceVelocity, Vector3f ellipseSpaceScale, BoundingVolume worldSpaceBounds) {
      if ((collisionSpatial.getType() & Spatial.TRIMESH) != 0) {
         TriMesh triMesh = (TriMesh)collisionSpatial;
         
         OBBTree collisionTree = triMesh.getCollisionTree();
           if (collisionTree == null)
               return;             
          
           collisionTree.bounds.transform(triMesh.getWorldRotation(), triMesh.getWorldTranslation(),
                 triMesh.getWorldScale(), collisionTree.worldBounds);
           checkEllipseSpaceCollision(triMesh, collisionTree, ellipseSpaceCenter, ellipseSpaceVelocity,
                 ellipseSpaceScale, worldSpaceBounds);
      }
   }
   
   /**
    * Attemps to collide the moving ellipes against a node's children.
    *
    * @param collisionNode The node to check for collisions
    * @param ellipseSpaceCenter The ellipse space center for the ellipse
    * @param ellipseSpaceVelocity The ellipse space velocity for the ellipse
    * @param ellipseSpaceScale The scale of ellipse space
    * @param worldSpaceBounds The bounds of the movement area in world space
    */
   private void checkEllipseSpaceCollision(Node collisionNode, Vector3f ellipseSpaceCenter, Vector3f ellipseSpaceVelocity, Vector3f ellipseSpaceScale, BoundingVolume worldSpaceBounds) {
       if (collisionNode.getWorldBound() != null) {
          if (collisionNode.getWorldBound().intersects(worldSpaceBounds)) {
             for (int i = 0; i < collisionNode.getQuantity(); i++) {
                checkEllipseSpaceCollision(collisionNode.getChild(i), ellipseSpaceCenter, ellipseSpaceVelocity, ellipseSpaceScale, worldSpaceBounds);
             }
          }
       }
   }
   
   private final static Vector3f v = new Vector3f(), newSourcePoint = new Vector3f(), destinationPoint = new Vector3f(), slidePlaneNormal = new Vector3f();
   private final static Vector3f displacementVector = new Vector3f(), newDestinationPoint = new Vector3f(), newVelocityVector = new Vector3f();   
   private final static Plane slidingPlane = new Plane();
   /**
    * Recursive method which finds the collisions for a moving ellipse against a collisionNode.  If the slide flag is set, it will also attempt
    * to slide the ellipse along the collision triangle, and continue recursively.
    *
    * @param depth The current sliding depth
    * @param collisionNode The node to check collisions against
    * @param slide Flag specifying whether or not a slide should be attempted
    */
   private void collideAndSlideEllipse(int depth, Node collisionNode, boolean slide) {
      if (depth > recursionDepth || ellipseSpaceVelocity.length() < veryCloseDistance * 2   )
         return;
      
      ellipseSpaceVelocityNormalized.set(ellipseSpaceVelocity);
      ellipseSpaceVelocityNormalized.normalizeLocal();
      
      //extend the size of the ellipse space vector by just a bit, to give us some collision buffer
      ellipseSpaceVelocityBuffer.set(ellipseSpaceVelocityNormalized);
      ellipseSpaceVelocityBuffer.multLocal(veryCloseDistance);      
      ellipseSpaceVelocity.addLocal(ellipseSpaceVelocityBuffer);
      
      checkEllipseCollision(collisionNode);
      
      if (!hasCollision) {
         ellipseSpaceCenter.addLocal(ellipseSpaceVelocity).subtractLocal(ellipseSpaceVelocityBuffer);
         return;
      }
      
      destinationPoint.set(ellipseSpaceCenter).addLocal(ellipseSpaceVelocity);
      v.set(ellipseSpaceVelocity);
      
      if (resultNearestCollisionDistance == 0.0f)
         resultNearestCollisionDistance = -veryCloseDistance;
      
      float factorx = resultNearestCollisionDistance - veryCloseDistance;
      v.multLocal(factorx);
      newSourcePoint.set(ellipseSpaceCenter).addLocal(v);
      
      if (!slide) {
         ellipseSpaceCenter.set(newSourcePoint);
         return;
      }      
      
      //slidePlaneNormal.set(newSourcePoint).subtractLocal(collisionResults.getCollisionPoint()).normalizeLocal();
      slidePlaneNormal.set(resultCollisionNormal);
      
      v.normalizeLocal().multLocal(veryCloseDistance);
      float factor = v.dot(slidePlaneNormal);
      if (factor != 0.0f)
         factor = veryCloseDistance / factor;
      displacementVector.set(v).multLocal(factor);
      
      newSourcePoint.addLocal(displacementVector);
      resultCollisionPoint.addLocal(displacementVector);
      
      slidingPlane.setNormal(slidePlaneNormal);

      slidingPlane.setConstant(slidePlaneNormal.dot(resultCollisionPoint));      
      
      float dist = slidingPlane.pseudoDistance(destinationPoint);
      newDestinationPoint.scaleAdd(-dist, slidePlaneNormal, destinationPoint);
      newVelocityVector.set(newDestinationPoint).subtractLocal(resultCollisionPoint);
      if (newVelocityVector.length() <= veryCloseDistance) {
         ellipseSpaceCenter.set(newSourcePoint);
         return;         
      }
      
      ellipseSpaceCenter.set(newSourcePoint);
      ellipseSpaceVelocity.set(newVelocityVector);
      collideAndSlideEllipse(depth + 1, collisionNode, slide);
   }



--Ruab
2


   /**
    * Main method for running the collision detection system.  Uses the location and velocity set in ellipseCenter and ellipseVelocity, and the
    * size specificed in ellipseDimensions.  Will check against all children of collisionNode which have their bounding boxes and OBBTrees initialized
    * If slide is set to true, it will also attempt to slide the ellipsoid along the collision triangles.  If gravity is set, it will also
    * apply gravity (using gravityVector * interpolation) after the original collision + slide has been completed.
    *
    * @param collisionNode The node to check collisions against
    * @param interpolation The update interpolation
    * @param slide Flag indicating whether a slide should occur
    * @param gravity Flag indicating wheter gravity should be applied
    */
   public void moveEllipseWithCollisions(Node collisionNode, float interpolation, boolean slide, boolean gravity) {
      ellipseSpaceCenter.set(ellipseCenter);
      ellipseSpaceCenter.multLocal(ellipseSpaceScale);
      ellipseSpaceVelocity.set(ellipseVelocity);
      ellipseSpaceVelocity.multLocal(ellipseSpaceScale);
      
      collideAndSlideEllipse(1, collisionNode, slide);

      if (gravity) {
         ellipseSpaceVelocity.set(gravityVector).multLocal(interpolation).multLocal(ellipseSpaceScale);
         collideAndSlideEllipse(1, collisionNode, false);
      }
      
      ellipseCenter.set(ellipseSpaceCenter).multLocal(ellipseDimensions);
   }
   
   private final static Vector3f possA = new Vector3f();
   private final static Vector3f possB = new Vector3f();
   private final static Vector3f possC = new Vector3f();
   /**
    * Checks to see if two points are on the same side of a line
    *
    * @param p1 First point
    * @param p2 Second point
    * @param line1 Line endpoint
    * @param line2 Second line endpoint
    * @return true if the points are on the same side of a line
    */
   private boolean pointsOnSameSide(Vector3f p1, Vector3f p2, Vector3f line1, Vector3f line2) {
      possA.set(line2).subtractLocal(line1);
      possC.set(possA);
      
      possB.set(p1).subtractLocal(line1);
      possA.crossLocal(possB);
      
      possB.set(p2).subtractLocal(line1);
      possC.crossLocal(possB);
      if (possA.dot(possC) >= 0)
         return true;
      return false;
   }
   
   /**
    * Checks to see if a point is inside of a triangle
    *
    * @param point The point to check
    * @param triangleOne Triangle point 1
    * @param triangleTwo Triangle point 2
    * @param triangleThree Triangle point 3
    * @return true if the point is inside the triangle
    */
   private boolean isPointInTriangle(Vector3f point, Vector3f triangleOne, Vector3f triangleTwo, Vector3f triangleThree) {
      if (pointsOnSameSide(point, triangleOne, triangleTwo, triangleThree) && pointsOnSameSide(point, triangleTwo, triangleOne, triangleThree) &&   pointsOnSameSide(point, triangleThree, triangleOne, triangleTwo))
         return true;
      return false;
   }
   
   private final static Plane mustiP = new Plane();
   private final static Vector3f mustiVa = new Vector3f();
   private final static Vector3f mustiVb = new Vector3f();
   /**
    * Workhorse function that evaluates the moving sphere against a single triangle, and returns the intersection distance, point and normal.
    *
    * @param sphereCenter Center of the unit sphere (ellipsoid in ellipse space)
    * @param sphereVelocity Velocity of the unit sphere (in ellipse space)
    * @param triangleOne First triangle point (in ellipse space)
    * @param triangleTwo Second triangle point (in ellipse space)
    * @param triangleThree Third triangle point (in ellipse space)
    * @param intersectionPoint Return intersection point
    * @param intersectionNormal Return intersection normal
    * @return the intersection distance or Float.NaN if there is no intersection
    */
   private float movingUnitSphereTriIntersection(Vector3f sphereCenter, Vector3f sphereVelocity,
         Vector3f triangleOne, Vector3f triangleTwo, Vector3f triangleThree, Vector3f intersectionPoint, Vector3f intersectionNormal)
   {
      mustiP.setPlanePoints(triangleOne, triangleTwo, triangleThree);
      if (mustiP.normal.dot(sphereVelocity.normalize()) <= 0.0f) {
         float t0, t1;
         boolean embedded = false;
         
         float signedDistanceToPlane = sphereCenter.dot(mustiP.normal) + mustiP.constant;
         float normalDotVelocity = mustiP.normal.dot(sphereVelocity);
         
         if (normalDotVelocity == 0.0f) {
            //we are travelling exactly parrallel to the plane
            
            if (FastMath.abs(signedDistanceToPlane) >= 1.0f) {
               //no collision possible
               return Float.NaN;
            } else {
               //we are embedded
               t0 = 0;
               t1 = 1;
               embedded = true;
            }
         } else {
            t0 = (-1 - signedDistanceToPlane) / normalDotVelocity;
            t1 = (1 - signedDistanceToPlane) / normalDotVelocity;
            
            if (t0 > t1) {
               float temp = t1;
               t1 = t0;
               t0 = temp;
            }
            
            if (t0 > 1.0f || t1 < 0.0f) {
               //collision is out of this velocity range
               return Float.NaN;
            }
            
            //clamp the interval to [0, 1]
            t0 = Math.max(t0, 0.0f);
            t1 = Math.min(t1, 1.0f);
            boolean foundCollision = false;
            float t = 1.0f;
            
            if (!embedded) {
               mustiVa.set(sphereCenter);
               mustiVa.subtractLocal(mustiP.normal);
               mustiVa.scaleAdd(t0, sphereVelocity, mustiVa);
               
               //test to see if the collision is on a triangle interior
               if (isPointInTriangle(mustiVa, triangleOne, triangleTwo, triangleThree)) {                  
                  foundCollision = true;
                  t = t0;
                  intersectionPoint.set(mustiVa);
                  intersectionNormal.set(mustiP.normal);
               }
               
               float velocitySquaredLength = sphereVelocity.lengthSquared();

               //triangleOne
               float newT = checkUnitSphereVertexCollision(sphereCenter, sphereVelocity, velocitySquaredLength, triangleOne, t, intersectionPoint);
               if (!Float.isNaN(newT)) {
                  t = newT;
                  foundCollision = true;
               }
               
               //triangleTwo
               newT = checkUnitSphereVertexCollision(sphereCenter, sphereVelocity, velocitySquaredLength, triangleTwo, t, intersectionPoint);
               if (!Float.isNaN(newT)) {
                  t = newT;
                  foundCollision = true;
               }

               //triangleThree
               newT = checkUnitSphereVertexCollision(sphereCenter, sphereVelocity, velocitySquaredLength, triangleThree, t, intersectionPoint);
               if (!Float.isNaN(newT)) {
                  t = newT;
                  foundCollision = true;
               }
   
               newT = checkUnitSphereEdgeCollision(sphereCenter, sphereVelocity, velocitySquaredLength, triangleOne, triangleTwo, t, intersectionPoint);
               if (!Float.isNaN(newT)) {
                  t = newT;
                  foundCollision = true;
               }
               
               newT = checkUnitSphereEdgeCollision(sphereCenter, sphereVelocity, velocitySquaredLength, triangleTwo, triangleThree, t, intersectionPoint);
               if (!Float.isNaN(newT)) {
                  t = newT;
                  foundCollision = true;
               }
               
               newT = checkUnitSphereEdgeCollision(sphereCenter, sphereVelocity, velocitySquaredLength, triangleThree, triangleOne, t, intersectionPoint);
               if (!Float.isNaN(newT)) {
                  t = newT;
                  foundCollision = true;
               }                                    
               
               if (foundCollision) {
                  mustiVb.scaleAdd(t, sphereVelocity, sphereCenter);
                  intersectionNormal.set(mustiVb).subtractLocal(intersectionPoint).normalizeLocal();
                  return t;
               }
            }
         }
      }
      
      return Float.NaN;
   }
   
   private final static Vector3f cusecA = new Vector3f(), cusecB = new Vector3f();
   /**
    * Check to see if the moving unit sphere collides with a triangle edge
    *
    * @param sphereCenter Center of the unit sphere (ellipsoid space)
    * @param sphereVelocity Velocity of the unit sphere (ellipsoid space)
    * @param velocitySquared Velocity squared (passed in so it doesnt need to be re-computed)
    * @param vertexA First edge vertex
    * @param vertexB Second edge vertex
    * @param t maximum possible intersection distance (based on other collisions)
    * @param intersectionPoint The intersection point returned
    * @return the distance of the collision, or Float.NaN if none is found, or if it is farther away that parameter t.
    */
   public float checkUnitSphereEdgeCollision(Vector3f sphereCenter, Vector3f sphereVelocity, float velocitySquared, Vector3f vertexA, Vector3f vertexB, float t, Vector3f intersectionPoint) {
      cusecA.set(vertexB).subtractLocal(vertexA); //edge vector from pt A to pt B
      cusecB.set(vertexA).subtractLocal(sphereCenter); //vector from the center of the sphere to pt A
      float edgeSquaredLength = cusecA.lengthSquared(); //squared length of the edge
      float edgeDotVelocity = cusecA.dot(sphereVelocity); //cos of the angle between the velocity and the edge
      float edgeDotBaseToVertex = cusecA.dot(cusecB); //cos of the angle between the center->A vector and the edge
      
      float a = edgeSquaredLength * -velocitySquared + edgeDotVelocity * edgeDotVelocity; //-velocity squared * edge len squared + angle between velocity and edge squared
      float b = edgeSquaredLength * (2 * sphereVelocity.dot(cusecB)) - 2 * edgeDotVelocity * edgeDotBaseToVertex;
      float c = edgeSquaredLength * (1 - cusecB.lengthSquared()) + edgeDotBaseToVertex * edgeDotBaseToVertex;
      
      float newT = getLowestRoot(a, b, c, t);
      if (!Float.isNaN(newT)) {
         float f = (edgeDotVelocity * newT - edgeDotBaseToVertex) / edgeSquaredLength;
         
         if (f >= 0 && f < 1) {            
            intersectionPoint.scaleAdd(f, cusecA, vertexA);
            return newT;
         }
      }
      
      return Float.NaN;
   }
   
   /**
    * Finds the lowest root of a quadratic equation
    *
    * @param a quadratic variable A
    * @param b quadratic variable B
    * @param c quadratic variable C
    * @param maxR maximum value to be returned
    * @return the lowest root (if less than maxR) or Float.NaN
    */
   private float getLowestRoot(float a, float b, float c, float maxR) {
      float determinant = b * b - 4 * a * c;
      if (determinant < 0)
         return Float.NaN;
      
      float sqrtd = FastMath.sqrt(determinant);
      float r1 = (-b - sqrtd) / (2 * a);
      float r2 = (-b + sqrtd) / (2 * a);
      
      if (r1 > r2) {
         float temp = r2;
         r2 = r1;
         r1 = temp;
      }
      
      if (r1 > 0 && r1 < maxR) {
         return r1;
      }
      
      if (r2 > 0 && r2 < maxR) {
         return r2;
      }
      
      return Float.NaN;
   }
   
   private final static Vector3f cusvcA = new Vector3f();
   /**
    * Checks the unit sphere against a vertex
    *
    * @param sphereCenter unit sphere center (ellipse space)
    * @param sphereVelocity unit sphere velocity (ellipse space)
    * @param velocitySquared velocity squared (pre-computed to save time)
    * @param vertex the vertex to check against
    * @param t the maximum value to return
    * @param intersectionPoint return intersection point
    * @return the intersection distance
    */
   private float checkUnitSphereVertexCollision(Vector3f sphereCenter, Vector3f sphereVelocity, float velocitySquared, Vector3f vertex, float t, Vector3f intersectionPoint) {
      float a = velocitySquared;
      float b = 2 * sphereVelocity.dot(cusvcA.set(sphereCenter).subtractLocal(vertex));
      float c = cusvcA.set(vertex).subtractLocal(sphereCenter).lengthSquared() - 1.0f;
      float newT = getLowestRoot(a, b, c, t);
      if (!Float.isNaN(newT)) {
         intersectionPoint.set(vertex);
      }
      return newT;      
   }
   
}



--Ruab
3

Do you have any examples/demos to help us understand what we are seeing here? :slight_smile:



You might want to put this on the wiki also.

4

I'm using it in a fairly large project at the moment, but I'll try to spend some time throwing together a quick demo app for it.  I'll try to post something this week.



–Ruab

5

Huge BUMP.



I decided to play around with my collision detection/avoidance systems and thought I'd give this method a shot.  However, when I plug it into my jME 1.0 project the OBBTree class is not found.  Has this class been deprecated/replaced by something else?  Here's the code that shows the class use:



/**

  • Check the ellipse collision against an OBBTree

    *
  • @param parentMesh The mesh which owns the OBBTree
  • @param collisionTree The OBBTree to traverse
  • @param ellipseSpaceCenter The ellipse space center for the ellipse
  • @param ellipseSpaceVelocity The ellipse space velocity for the ellipse
  • @param ellipseSpaceScale The scale of ellipse space
  • @param worldSpaceBounds The bounds of the movement area in world space

    */

    private void checkEllipseSpaceCollision(TriMesh parentMesh, OBBTree collisionTree, Vector3f ellipseSpaceCenter, Vector3f ellipseSpaceVelocity, Vector3f ellipseSpaceScale, BoundingVolume worldSpaceBounds) {

            collisionTree.bounds.transform(

            parentMesh.getWorldRotation(),

            parentMesh.getWorldTranslation(),

            parentMesh.getWorldScale(),

                    collisionTree.worldBounds);

        if (!collisionTree.worldBounds.intersects(worldSpaceBounds)) {

        return;

        }

       

        OBBTree left = collisionTree.getLeftTree();

        OBBTree right = collisionTree.getRightTree();



    Does anyone know if ruab is still around under one nick or another?
6

Just to link it up… there's apparently a "simplephysics" implementation of this code/idea here:



http://www.jmonkeyengine.com/jmeforum/index.php?topic=5073.0