Scaling leads to inccorect triangle-accurate collision detection

I just spent two days struggling with JME's collision detection trees; I was using shapes that were scaled, and found that triangle accuracy was incorrectly detecting collisions if the shapes were also rotated - but had no problems if they were not rotated.



I'm pretty sure that the problem is in the following lines of the collision tree's intersection method (marked 'Problem!':


   public boolean intersect(CollisionTree collisionTree, ArrayList<Integer> aList,
         ArrayList<Integer> bList) {
      
      if (collisionTree == null) {
         return false;
      }
      
      // our two collision bounds do not intersect, therefore, our triangles must
      // not intersect. Return false.
      collisionTree.bounds
            .transform(collisionTree.parent.getWorldRotation(),
                  collisionTree.parent.getWorldTranslation(),
                  collisionTree.parent.getWorldScale(),
                  collisionTree.worldBounds);
      
      if (!intersectsBounding(collisionTree.worldBounds)) {
         return false;
      }
      
      //if our node is not a leaf send the children (both left and right) to
      // the test tree.
      if (left != null) { // This is not a leaf
         boolean test = collisionTree.intersect(left, bList, aList);
         test = collisionTree.intersect(right, bList, aList) || test;
         return test;
      }

      // This node is a leaf, but the testing tree node is not. Therefore,
      // continue processing the testing tree until we find its leaves.
      if (collisionTree.left != null) {
         boolean test = intersect(collisionTree.left, aList, bList);
         test = intersect(collisionTree.right, aList, bList) || test;
         return test;
      }

      // both this node and the testing node are leaves. Therefore, we can
      // switch to checking the contained triangles with each other. Any
      // that are found to intersect are placed in the appropriate list.
      Quaternion roti = parent.getWorldRotation();
      Vector3f scalei = parent.getWorldScale();
      Vector3f transi = parent.getWorldTranslation();

      Quaternion rotj = collisionTree.parent.getWorldRotation();
      Vector3f scalej = collisionTree.parent.getWorldScale();
      Vector3f transj = collisionTree.parent.getWorldTranslation();
      
      boolean test = false;
      
      for (int i = start; i < end; i++) {
         batch.getTriangle(triIndex[i], verts);
         roti.mult(verts[0], tempVa).multLocal(scalei).addLocal(transi);      //Problem!
         roti.mult(verts[1], tempVb).multLocal(scalei).addLocal(transi);      //Problem!
         roti.mult(verts[2], tempVc).multLocal(scalei).addLocal(transi);      //Problem!
         for (int j = collisionTree.start; j < collisionTree.end; j++) {
            collisionTree.batch.getTriangle(collisionTree.triIndex[j],
                  target);
            rotj.mult(target[0], tempVd).multLocal(scalej).addLocal(transj);  //Problem!
            rotj.mult(target[1], tempVe).multLocal(scalej).addLocal(transj);  //Problem!
            rotj.mult(target[2], tempVf).multLocal(scalej).addLocal(transj);  //Problem!
            if (Intersection.intersection(tempVa, tempVb, tempVc, tempVd,
                  tempVe, tempVf)) {
               test = true;
               aList.add(triIndex[i]);
               bList.add(collisionTree.triIndex[j]);
            }
         }
      }
      return test;

   }



The order of those six lines, in transforming the triangle vertices into world coordinates, is different from the order in the Spatial.localToWorld() function. If you rearrange those lines as follows, my problems go away and collision detection seems to work correctly in general:


roti.mult(tempVa.set(verts[0]).multLocal(scalei), tempVa).addLocal(transi);
roti.mult(tempVb.set(verts[1]).multLocal(scalei), tempVb).addLocal(transi);
roti.mult(tempVc.set(verts[2]).multLocal(scalei), tempVc).addLocal(transi);


and

rotj.mult(tempVd.set(target[0]).multLocal(scalej), tempVd).addLocal(transj);
rotj.mult(tempVe.set(target[1]).multLocal(scalej), tempVe).addLocal(transj);
rotj.mult(tempVf.set(target[2]).multLocal(scalej), tempVf).addLocal(transj);


Nice catch.  Posting the patch would save me time i you have one.

Like this?


   public boolean intersect(CollisionTree collisionTree, ArrayList<Integer> aList,
         ArrayList<Integer> bList) {
      
      if (collisionTree == null) {
         return false;
      }
      
      // our two collision bounds do not intersect, therefore, our triangles must
      // not intersect. Return false.
      collisionTree.bounds
            .transform(collisionTree.parent.getWorldRotation(),
                  collisionTree.parent.getWorldTranslation(),
                  collisionTree.parent.getWorldScale(),
                  collisionTree.worldBounds);
      
      if (!intersectsBounding(collisionTree.worldBounds)) {
         return false;
      }
      
      //if our node is not a leaf send the children (both left and right) to
      // the test tree.
      if (left != null) { // This is not a leaf
         boolean test = collisionTree.intersect(left, bList, aList);
         test = collisionTree.intersect(right, bList, aList) || test;
         return test;
      }

      // This node is a leaf, but the testing tree node is not. Therefore,
      // continue processing the testing tree until we find its leaves.
      if (collisionTree.left != null) {
         boolean test = intersect(collisionTree.left, aList, bList);
         test = intersect(collisionTree.right, aList, bList) || test;
         return test;
      }

      // both this node and the testing node are leaves. Therefore, we can
      // switch to checking the contained triangles with each other. Any
      // that are found to intersect are placed in the appropriate list.
      Quaternion roti = parent.getWorldRotation();
      Vector3f scalei = parent.getWorldScale();
      Vector3f transi = parent.getWorldTranslation();

      Quaternion rotj = collisionTree.parent.getWorldRotation();
      Vector3f scalej = collisionTree.parent.getWorldScale();
      Vector3f transj = collisionTree.parent.getWorldTranslation();
      
      boolean test = false;
      
      for (int i = start; i < end; i++) {
         batch.getTriangle(triIndex[i], verts);

         roti.mult(tempVa.set(verts[0]).multLocal(scalei), tempVa).addLocal(transi);
         roti.mult(tempVb.set(verts[1]).multLocal(scalei), tempVb).addLocal(transi);
         roti.mult(tempVc.set(verts[2]).multLocal(scalei), tempVc).addLocal(transi);
         
         for (int j = collisionTree.start; j < collisionTree.end; j++) {
            collisionTree.batch.getTriangle(collisionTree.triIndex[j],
                  target);

            rotj.mult(tempVd.set(target[0]).multLocal(scalej), tempVd).addLocal(transj);
            rotj.mult(tempVe.set(target[1]).multLocal(scalej), tempVe).addLocal(transj);
            rotj.mult(tempVf.set(target[2]).multLocal(scalej), tempVf).addLocal(transj);

            if (Intersection.intersection(tempVa, tempVb, tempVc, tempVd,
                  tempVe, tempVf)) {
               test = true;
               aList.add(triIndex[i]);
               bList.add(collisionTree.triIndex[j]);
            }
         }
      }
      return test;

   }

No, but that's ok, I've got it fixed and checked in for this method and its sibling method in the same class.