TriangleCollisionResults are wrong, here's how

Lets see if I can articulate this clear enough to be understood.



I have reason to believe that TriangleCollisionResults are unreliable. I have proof but no solution, but hopefully thats where you guys come in.



My scenario:



I built a test case to demonstrate/debug some collision detection code I’ve written extended from simplegame, and in the process have made a discovery.



In my test I have three objects. There are two boxes to collide into, which are stationary, and one sphere which is movable. When a collision occurs between the sphere and a box, the normal of the surface on the box is printed out to the console.



So I can move the sphere up into the red box and it prints the normal as (0, -1, 0) from the triangle indexed as 11 in the meshAsTriangles list for the red box, this is correct.





I can then slide the sphere left into the yellow box and it reports (1, 0, 0) from the triangle indexed as 2 for the yellow box, this is also correct.





Now my collision code sums the normals of each triangle collided and normalizes it. So in theory, I can collide with both the red and yellow boxes at the same time, and the resulting normal should be (1, -1, 0). I have setup this test to demonstrate exactly that. But when the collision occurs against both boxes my sphere is allowed to penetrate one on them (its always been the red for me).





I have stepped through the process many times with a debugger and have discovered the the Triangle collision results are incorrect when two abjects are involved. In this case, the TriangleCollisionResults indicate two CollisionResults in the node list. One (the first one) is the red box, the second is the yellow box. So far so good.



But after this it gets complicated. I iterate through each collision data and calculate normals for each triangle. The first collision data is for the red box(named ‘col1’), the triangle results for the targetMesh (red box mesh) all have the index 2. Next I calculate all normals for triangles from collision data 2 (the yellow box, named ‘col2’). All triangles returned from CollisionData.getTargetTris() are index 2 in their respective mesh. Did you get that?



The getTargetTris() for the red box should all be index 11, and the yellow ones should be 2. But somehow, the collision data for the first collision is getting the indexes from the second collision data. So when I calculate the triangle normals for the red box, I’m getting the wrong triangles! Everything else contained in the collision data appears to be correct for both. It just the first one gets the wrong indices!



Now I don’t know how triangle collisions are calculated, but I’m sure this has caused all sorts of grief. I don’t even know where to look as far as fixing this problem. But I have the test class and I will post it so that anyone can try it out and see whats happening.



I hope I’ve narrowed it down enough that someone can fix this for us.

And here is the test…



The controls for the sphere are:

move left = ','

move right = '.'

move up = 'i'

move down = 'k'



…a little random (i know  ;)).




package src;

import java.util.ArrayList;

import com.jme.app.SimpleGame;
import com.jme.bounding.BoundingBox;
import com.jme.input.KeyBindingManager;
import com.jme.input.KeyInput;
import com.jme.intersection.BoundingCollisionResults;
import com.jme.intersection.CollisionData;
import com.jme.intersection.TriangleCollisionResults;
import com.jme.math.FastMath;
import com.jme.math.Triangle;
import com.jme.math.Vector3f;
import com.jme.renderer.ColorRGBA;
import com.jme.scene.Node;
import com.jme.scene.TriMesh;
import com.jme.scene.shape.Box;
import com.jme.scene.shape.Sphere;
import com.jme.scene.state.MaterialState;

public class CollisionTest extends SimpleGame {

   private Sphere character;

   private Node collisionGeoms;

   private BoundingCollisionResults boundCollision;

   private TriangleCollisionResults triCollision;

   private Vector3f prevLoc;

   private Vector3f temp;

   private Vector3f delta;

   /**
    * Entry point for the test,
    *
    * @param args
    */
   public static void main(String[] args) {

      CollisionTest app = new CollisionTest();
      app.setDialogBehaviour(ALWAYS_SHOW_PROPS_DIALOG);
      app.start();
   }

   public CollisionTest() {

      super();
   }

   @Override
   protected void simpleInitGame() {

      collisionGeoms = new Node("collisionGeoms");
      rootNode.attachChild(collisionGeoms);

      prevLoc = new Vector3f();
      temp = new Vector3f();
      delta = new Vector3f();

      boundCollision = new BoundingCollisionResults();
      triCollision = new TriangleCollisionResults();

      initBoxes();

      KeyBindingManager.getKeyBindingManager().set("left", KeyInput.KEY_COMMA);
      KeyBindingManager.getKeyBindingManager().set("right", KeyInput.KEY_PERIOD);
      KeyBindingManager.getKeyBindingManager().set("up", KeyInput.KEY_I);
      KeyBindingManager.getKeyBindingManager().set("down", KeyInput.KEY_K);
      KeyBindingManager.getKeyBindingManager().set("reset", KeyInput.KEY_SPACE);
   }

   private void initBoxes() {

      character = new Sphere("character", 10, 10, 1f);
      character.setModelBound(new BoundingBox());
      character.setLocalTranslation(new Vector3f(0, 0, -10));
      MaterialState ms = display.getRenderer().createMaterialState();
      ms.setAmbient(ColorRGBA.blue);
      character.setRenderState(ms);
      character.setIsCollidable(true);
      character.updateRenderState();
      character.updateModelBound();
      character.updateGeometricState(0.0f, true);
      character.updateCollisionTree();

      Box coll1 = new Box("coll1", new Vector3f(), 5, 5, 1);
      coll1.setModelBound(new BoundingBox());
      coll1.setLocalTranslation(new Vector3f(-6, 5, -10));
      //coll1.getLocalRotation().fromAngleAxis(-FastMath.PI / 4, new Vector3f(0, 1, 0));
      ms = display.getRenderer().createMaterialState();
      ms.setAmbient(ColorRGBA.red);
      coll1.setRenderState(ms);
      coll1.setIsCollidable(true);
      coll1.updateRenderState();
      coll1.updateModelBound();
      coll1.updateGeometricState(0.0f, true);
      coll1.updateCollisionTree();

      Box coll2 = new Box("coll2", new Vector3f(), 2, 5, 1);
      coll2.setModelBound(new BoundingBox());
      coll2.setLocalTranslation(new Vector3f(-6, 0, -10));
      //coll2.getLocalRotation().fromAngleAxis(FastMath.PI / 2, new Vector3f(0, 0, 1));
      ms = display.getRenderer().createMaterialState();
      ms.setAmbient(ColorRGBA.yellow);
      coll2.setRenderState(ms);
      coll2.setIsCollidable(true);
      coll2.updateRenderState();
      coll2.updateModelBound();
      coll2.updateGeometricState(0.0f, true);
      coll2.updateCollisionTree();

      rootNode.attachChild(character);
      rootNode.updateGeometricState(0.0f, true);

      collisionGeoms.attachChild(coll1);
      collisionGeoms.attachChild(coll2);
      collisionGeoms.updateCollisionTree();
      collisionGeoms.updateGeometricState(0.0f, true);
   }

   protected void simpleUpdate() {

      prevLoc.set(character.getLocalTranslation());

      if(KeyBindingManager.getKeyBindingManager().isValidCommand("left", true)) {
         character.getLocalTranslation().addLocal(-0.01f, 0, 0);
      }
      if(KeyBindingManager.getKeyBindingManager().isValidCommand("right", true)) {
         character.getLocalTranslation().addLocal(0.01f, 0, 0);
      }
      if(KeyBindingManager.getKeyBindingManager().isValidCommand("up", true)) {
         character.getLocalTranslation().addLocal(0, 0.01f, 0);
      }
      if(KeyBindingManager.getKeyBindingManager().isValidCommand("down", true)) {
         character.getLocalTranslation().addLocal(0, -0.01f, 0);
      }
      if(KeyBindingManager.getKeyBindingManager().isValidCommand("reset", false)) {
         character.getLocalTranslation().zero();
      }

      delta.set(character.getLocalTranslation().subtract(prevLoc));

      checkForCollision();
   }

   private void checkForCollision() {

      boundCollision.clear();
      character.calculateCollisions(collisionGeoms, boundCollision);

      // check for bounding collision
      if(boundCollision.getNumber() > 0) {

         triCollision.clear();
         character.calculateCollisions(collisionGeoms, triCollision);

         // check for actual triangle collision
         if(triCollision.getNumber() > 0) {

            temp.zero();

            for(int index = 0; index < triCollision.getNumber(); index++)
               temp.addLocal(getCollisionNormal(triCollision.getCollisionData(index)));

            temp.normalizeLocal();
            temp.multLocal(delta.length());
            temp.addLocal(delta);

            character.setLocalTranslation(prevLoc.add(temp));
         }
      }
   }

   private Vector3f getCollisionNormal(CollisionData data) {

      Vector3f normal = new Vector3f();

      if(data.getTargetTris().size() > 0) {

         for(int colIndex = 0; colIndex < triCollision.getNumber(); colIndex++) {

            CollisionData triData = triCollision.getCollisionData(colIndex);
            TriMesh mesh = (TriMesh) triData.getTargetMesh();
            Triangle[] triangles = mesh.getMeshAsTriangles(triData.getTargetBatchId(), null);
            ArrayList<Integer> triIndex = triData.getTargetTris();

            for(Integer i : triIndex) {

               Triangle t = triangles[i];
               t.calculateNormal();
               normal.addLocal(triData.getTargetMesh().getLocalRotation().mult(t.getNormal()));
            }
         }
      }
      
      if((normal.x != 0) || (normal.y != 0) || (normal.z != 0))
         System.out.println("Collision Surface Normal: " + normal.normalize());
      
      return normal.normalizeLocal();
   }
}

You are right: TriangleCollisionResults uses the same list for triangle indices over and over. So this error is obviously caused by trying to save some memory/reduce garbage. What should be done here - create a list per result, or does anybody have a better idea?

Triangle collision/picking is incredibly poor on multiple levels. Bad enough that I'd rather discuss a different system altogether. I see three major possibilities:


  1. Wrapping OPCODE (or stripping only what is needed for collision out of ODE (which uses OPCODE) and moving that into core as the collision system, or wrapping something better (Mr. Coder fancies Bullet) for similar design.
  2. Write a new one from scratch in pure Java
  3. Continue working with what is there. It's major problems are the errors an inaccuracies obvious (these are probably just attributed to bugs, so doesn't really go against its favor), and memory usage. The creation of the OBBTrees are so incredibly expensive that in any real game scene they become worthless. Not to mention the code is hard to follow and read, so maintenance will be difficult.

Personally I would vote for #1.  Out OBBTree is so memory intensive as mojo says that I had to throw it out as a possibility when working with this at work.  Fortunately in my case I was working with picking the terrain, so implementing a grid walking solution was cheaper, faster and accurate.  :confused:

if someone has a code that resolve this, or anyone knows hot to fix this problem, using a code as example, I would like, if its possible, that you post this code here, ok???

I really need to know how to fix this problem, to finish my college job :confused: …  :D  :smiley:



Thanks a lot, everyone, especially nymon that posted this code here… Thanks man!!!  :smiley:

@GuilhermeFranchi: I updated the collision example in the other post. Theres an additional method named reCalcCollision, which works around the problem. That fact that I have to do this extra method is far from efficient, but for my app I have noticed no perfermance decrease.



Check out the changes and give them a try, if you have a question just yell.

Thanks nymon!!! Now it's working…  :smiley:

Thanks a lot…  :wink:



Now, getting back to work, hehehehehe… any question, I'll be posting here…



Guilherme  8)

Just an update (this thread was linked from elsewhere so it reminded me). I've been spending the last few weeks on the collision system at work and have made a few improvements. We ended up going with option #3 above. Initial profiling showed that creation of an OBBTree of a 522,000 poly mesh (an extreme case):



took 6 seconds to create and took 125 MB of RAM.



I have optimized quite a bit and now that same mesh is:



takes 1.2 seconds to create and takes 5 MB of RAM.



I also removed the Concept of OBBTree and created a CollisionTree, this tree can use OBB, AABB or Sphere. There is also now a CollisionTreeManager that takes care of these trees for you (no longer do you have to update a collision tree for each Spatial and waste memory for objects that aren't colliding. Instead, the collision tree manager dynamically creates and deletes the collision trees as needed. More information will be provided when it is checked in.

Awesome  :slight_smile:

That sounds excellent mojomonk :slight_smile:



This may be completely off topic, but there was some discussion of recoding stuff, and I've been thinking about something hopefully related for a while. I was profiling my game, and I realised that a lot of object creation was coming from my use of Node.calculatePick to find collisions between "bullets" and bounding volumes, to tell when a bullet hits a plane, etc. It seems pretty inefficient to do this by creating a list and new PickData instances every time you want to pick. So the alternative I thought of was to use a callback system. calculatePick would be called with an instance of an interface PickListener which would have a method "createPickData" and a method "acceptPickData". calculatePick would use createPickData to get PickData instances, and would then fill these out and call acceptPickData with the filled out instance. This allows for a lot of different ways of using the system:


  1. Duplicate the current system - a default implementation of PickListener would create a new PickData instance on every call of createPickData, and add the PickData it gets back to a list. After calculatePick returns, this default implementation would contain a list of PickData as at present.


  2. Greatly reduce object creation. The PickListener would always provide the same PickData on every call of createPickData, and when it received this back via acceptPickData, it would immediately handle the collision. e.g. in aircarrier, it would deal with the bullet-plane collision, after which there is no more need for the PickData, and it can be overwritten by the next collision.



    I hope the description of that makes some sense, it seems like it's a system that might work in other places as well, to reduce object creation, and it seems fairly straight forward.



    I agree with the comments above that the collision system could do with some improvements, at the moment most of the difficulty I am having with my game is down to collisions - trying to assemble a mixture of jme-physics, existing collision data and some new track/capsule collision code I've put together that gives reasonable performance (speed and accuracy).

Thanks mojomonk.

if you move fast enough, you can get through the fence because in the first frame you're in front of it, and in the next one, you're behind it. there never is a collision.

the correct solution would be to stretch the model like the ships from star trek do when they accelerate to warp speed and check that model for collisions.

So, how does the code look like after the change with CollisionTree? is there already any tutorial on collision detection topic?

because when i tried to test collision detection in flagrush tutorial, the vehicle can sometimes passes through the wall  :frowning:

Which code are you asking about? Is it the test posted above or the actual CollisionTreeManager stuff?

i was trying to do a simple collision detection and response by continuing the flag rush tutorial from lesson 9 (because there hasnt been any collision detection, has it?), i wrote something like this:



protected void update(float interpolation) {
        // Update the GameTaskQueue
        GameTaskQueueManager.getManager().getQueue(GameTaskQueue.UPDATE).execute();
       
        // update the time to get the framerate
        timer.update();
       
        // for collision
        prev.set(player.getLocalTranslation());
              
        interpolation = timer.getTimePerFrame();

        // update the keyboard input (move the player around)
        input.update(interpolation);
       
        checkCollision();



and below is the check collision method, to see whether the vehicle collided with force field fence or tower:


private void checkCollision() {
        ArrayList<Spatial> fenceChildren = fence.getChildren();
        for (int i = 0; i < fenceChildren.size(); i++) {
            Node fc = (Node) fenceChildren.get(i);
            if (fc.getName().equals("tower")) {
                ArrayList<Spatial> towers = fc.getChildren();
                for (int j = 0; j < towers.size(); j++) {
                    SharedMesh tow = (SharedMesh) towers.get(j);
                    if (player.getWorldBound().intersects(tow.getWorldBound())) {
                        // System.out.println("Colllided with tower");
                        player.setLocalTranslation(new Vector3f().set(prev));
                    }
                }
            } else if (fc.getName().equals("forceFieldNode")) {
                ArrayList fences = fc.getChildren();
                for (int j = 0; j < fences.size(); j++) {
                    SharedMesh fn = (SharedMesh) fences.get(j);
                    if (player.getWorldBound().intersects(fn.getWorldBound())) {
                        // System.out.println("Colllided with fence");
                        player.setLocalTranslation(new Vector3f().set(prev));
                    }
                }
            }
        }
    }



then i found that it is not perfect, because the vehicle can sometimes go through the wall, so i searched in the forum and found your(@nymon) code, but when i tried your code, the updateCollisionTree has been deprecated and changed with CollisionTreeManager which i still dont know how to use it,. .