findTrianglePick problem

Troubleshooting General Help
1

Excuse the code, I just mashed together a bunch of examples so I could code my AlterTerrain function.  This example works fine, until you click on the same spot multiple times, then it will stop returning triangles in findTrianglePick.  To test, just run the code, and right click near the corner.  You will see it raise a patch of terrain around your cursor - right click a few more times in the same spot and you will notice it stops lowering.  If you look at the console output you will see that RAL.size() is returning zero at this point.  This doesn't make sense - since if you look at the code, you can't even get to that point in the code without TrianglePickResults confirming that our TerrainBlock is the one the ray is touching.



So why does TrianglePickResults think the ray is touching the TerrainBlock (which it is), but findTrianglePick is not returning any triangles (sometimes)?






import com.jme.bounding.*;
import com.jme.math.*;
import com.jme.scene.shape.Box;
import com.jmex.editors.swing.settings.*;
import com.jmex.game.*;
import com.jmex.game.state.*;


import com.jmex.terrain.util.ImageBasedHeightMap;
import com.jmex.terrain.TerrainBlock;
import com.jme.scene.Node;
import com.jme.renderer.Camera;
import com.jmex.terrain.util.ProceduralTextureGenerator;
import com.jme.renderer.ColorRGBA;
import com.jme.math.Ray;
import com.jme.intersection.TrianglePickResults;
import com.jme.scene.Geometry;
import com.jme.math.Vector2f;
import com.jme.image.Texture;
import com.jme.util.TextureManager;
import com.jme.scene.state.TextureState;
import javax.swing.ImageIcon;

import java.util.concurrent.Callable;
import com.jme.util.GameTaskQueue;
import com.jme.util.GameTaskQueueManager;
import com.jme.input.MouseInput;
import com.jme.input.MouseInputListener;
import com.jme.scene.TriMesh;
import java.util.ArrayList;
import com.jme.scene.state.WireframeState;
import com.jme.scene.Line;
import com.jme.scene.state.LightState;
import com.jme.scene.state.ClipState;
import com.jme.light.PointLight;

/**
 * TestStandardGame is meant to be an example replacement of
 * jmetest.base.TestSimpleGame using the StandardGame implementation
 * instead of SimpleGame.
 *
 * @author Matthew D. Hicks
 */
public class TestStandardGame {
   StandardGame game;
   DebugGameState state;
   ImageBasedHeightMap ib;
   TerrainBlock tb;
   LightState ls;
   ClipState cs;
   TextureState ts;
   ProceduralTextureGenerator pg;

   boolean[] ButtonDown = new boolean[3];

   public static void main(String[] args)
   {
      TestStandardGame TSG = new TestStandardGame();
   }

   public TestStandardGame()
   {
      // Instantiate StandardGame
      game = new StandardGame("A Simple Test");
      // Show settings screen
      try
      {
         GameSettingsPanel.prompt(game.getSettings());
      } catch (Exception myE) {}
      // Start StandardGame, it will block until it has initialized successfully, then return
      game.start();

      // Create a DebugGameState - has all the built-in features that SimpleGame provides
      // NOTE: for a distributable game implementation you'll want to use something like
      // BasicGameState instead and provide control features yourself.
      state = new DebugGameState();
      // Put our box in it
      Box box = new Box("my box", new Vector3f(0, 0, 0), 2, 2, 2);
       box.setModelBound(new BoundingSphere());
       box.updateModelBound();
       // We had to add the following line because the render thread is already running
       // Anytime we add content we need to updateRenderState or we get funky effects
       box.updateRenderState();
       state.getRootNode().attachChild(box);
      // Add it to the manager
      GameStateManager.getInstance().attachChild(state);

        //  Create an image height map based on the gray scale of our image.
         ib = new ImageBasedHeightMap(new ImageIcon(guidevtools.class.getClassLoader().getResource("test_hm.gif")).getImage());

        // Create a terrain block from the image's grey scale
        /*TerrainBlock tb=new TerrainBlock("image icon",ib.getSize(),
                new Vector3f(.5f,.05f,.5f),ib.getHeightMap(),
                new Vector3f(0,0,0),false); */

                tb=new TerrainBlock("image icon",ib.getSize(),
                new Vector3f(.5f,.05f,.5f),ib.getHeightMap(),
                new Vector3f(0,0,0),false);

        //  Create an object to generate textured terrain from the image based height map.
        pg=new ProceduralTextureGenerator(ib);
        //  Look like water from height 0-60 with the strongest "water look" at 30
        pg.addTexture(new ImageIcon(guidevtools.class.getClassLoader().getResource("water.png")),0,30,60);
        //  Look like dirt from height 40-120 with the strongest "dirt look" at 80
        pg.addTexture(new ImageIcon(guidevtools.class.getClassLoader().getResource("dirt.jpg")),40,80,120);
        //  Look like highest (pure white) from height 110-256 with the strongest "white look" at 130
        // pg.addTexture(new ImageIcon("highest.jpg"),110,130,256);

        //  Look like highest (pure white) from height 110-256 with the strongest "white look" at 130
        pg.addTexture(new ImageIcon(guidevtools.class.getClassLoader().getResource("highest.jpg")),110,250,256);

        //  Tell pg to create a texture from the ImageIcon's it has recieved.
        pg.createTexture(256);

      boolean doTexture = false;

      if (doTexture)
      {
         ts=game.getDisplay().getRenderer().createTextureState();
         // Load the texture and assign it.
         ts.setTexture(
               TextureManager.loadTexture(
                     pg.getImageIcon().getImage(),
                     Texture.MM_LINEAR_LINEAR,
                     Texture.FM_LINEAR,
                     true
               )
         );

         // tb to rootNode
         tb.setRenderState(ts);
        }
      else
      {
         WireframeState ws = game.getDisplay().getRenderer().createWireframeState();
         tb.setRenderState(ws);
      }

        // Give the terrain a bounding box
        tb.setModelBound(new BoundingBox());
        tb.updateModelBound();

        // Move the terrain in front of the camera
        tb.setLocalTranslation(new Vector3f(0, 0, -10));

      tb.updateRenderState();

      state.getRootNode().attachChild(tb);



      ls = game.getDisplay().getRenderer().createLightState();
      cs = game.getDisplay().getRenderer().createClipState();
      System.out.println("ls qty:'" + ls.getQuantity() + "'");



      // Activate the game state
      state.setActive(true);

      MouseInput.get().setCursorVisible(true);

      MouseInputListener windowMouse = new MouseInputListener()
      {
         public void onButton(int button, boolean pressed, int x, int y)
         {
            if (button == 0)
            {
               // left
               if (pressed == true)
               {
                  ButtonDown[0] = true;
                  System.out.println("evt mouse1 down");
                  AlterTerrain(x,y,5,true,5);
               }
               else
               {
                  ButtonDown[0] = false;
                  System.out.println("evt mouse1 up");
               }
            }
            else if (button == 1)
            {
               // right
               System.out.println("evt mouse2");

               if (pressed == true)
               {
                  ButtonDown[1] = true;
                  AlterTerrain(x,y,5,false,5);
               }
               else
               {
                  ButtonDown[1] = false;
               }
            }
            else if (button == 2)
            {
               // middle
               System.out.println("evt mouse3");

               if (pressed == true)
               {
                  ButtonDown[2] = true;
                  AlterTerrain(x,y,5,false,5);
               }
               else
               {
                  ButtonDown[2] = false;
               }
            }
            else if (pressed == true)
            {
               System.out.println("button press:'" + button + "'");
            }
         }

         public void onMove(int xDelta, int yDelta, int newX, int newY)
         {
            if (ButtonDown[0] == true)
            {
               AlterTerrain(newX,newY,5,true,5);
            }
            else if (ButtonDown[1] == true)
            {
               AlterTerrain(newX,newY,5,false,5);
            }
            else if (ButtonDown[2] == true)
            {
               AlterTerrain(newX,newY,5,false,5);
            }
         }

         public void onWheel(int wheelDelta, int x, int y) {}
      };


        MouseInput.get().addListener(windowMouse);
   }

   public void AlterTerrain(float x, float y, int BrushSize, boolean RaiseTerrain, int AlterAmount)
   {
      if (BrushSize < 1)
      {
         BrushSize = 5;
      }

      System.out.println("incoming gt x:'" + x + "' y:'" + y + "'");
      game.getCamera().update();

      Ray ResultsRay = game.getDisplay().getPickRay(new Vector2f(x,y), false, null);

      TrianglePickResults PResults = new TrianglePickResults();
      PResults.setCheckDistance(true);
      Node rootNode = state.getRootNode();
      rootNode.findPick(ResultsRay, PResults);

      int ResultCount = PResults.getNumber();

      if (ResultCount > 0)
      {
         // use result 0, should be closest...
         TriMesh TMesh = (TriMesh)PResults.getPickData(0).getTargetMesh().getParentGeom();
         ArrayList<Integer> RAL = new ArrayList<Integer>();
         if (TMesh.getBatchCount() == 1)
         {
            // Pick the actual triangles out of the mesh now
            TMesh.findTrianglePick(ResultsRay,RAL,0);

            System.out.println("ralsize:'" + RAL.size() + "'");

            if (RAL.size() > 0)
            {
               int ClosestTri = -1;
               float ClosestDist = -1;

               // Find the closest triangle from all the results
               for (int i=0;i<RAL.size();i++)
               {
                  Vector3f[] myTri = new Vector3f[3];
                  TMesh.getTriangle(RAL.get(i).intValue(), myTri);

                  Vector3f newValues = new Vector3f();

                  if (ResultsRay.intersectWherePlanar(myTri[0].addLocal(TMesh.getWorldTranslation()), myTri[1].addLocal(TMesh.getWorldTranslation()), myTri[2].addLocal(TMesh.getWorldTranslation()), newValues))
                  {
                     if (newValues.getX() < ClosestDist || ClosestDist == -1)
                     {
                        ClosestDist = newValues.getX();
                        ClosestTri = RAL.get(i).intValue();
                     }

                  }
                  else
                  {
                     System.out.println("error no intersect!");
                  }
               }

               System.out.println("closesttri:'" + ClosestTri + "'");

               if (ClosestTri > -1)
               {
                  // Got one particular triangle.. start routine to alter the terrain based on this location...
                  Vector3f[] myTri2 = new Vector3f[3];
                  TMesh.getTriangle(ClosestTri, myTri2);
                  myTri2[0].addLocal(TMesh.getWorldTranslation());
                  myTri2[1].addLocal(TMesh.getWorldTranslation());
                  myTri2[2].addLocal(TMesh.getWorldTranslation());

                  /*
                  Vector3f[] tmpLines = {ResultsRay.getOrigin(),myTri2[0], ResultsRay.getOrigin(), myTri2[1], ResultsRay.getOrigin(), myTri2[2]};
                  Line myLine = new Line("my Pointer",tmpLines,null,null,null);
                  myLine.setSolidColor(ColorRGBA.red);
                  System.out.println("linewidth:'" + myLine.getLineWidth() + "'");
                  state.getRootNode().attachChild(myLine);
                  */

                  Vector3f tbwt = tb.getWorldTranslation();
                  Vector3f tmp3fValues = new Vector3f();

                  tmp3fValues.x = (int)((myTri2[0].x - tbwt.x) * 2);
                  tmp3fValues.z = (int)((myTri2[0].z - tbwt.z) * 2);
                  tmp3fValues.y = tb.getSize();

                  System.out.println("tempvals x:'" + tmp3fValues.x + "' z:'" + tmp3fValues.z + "'");

                  for (int i=(int)tmp3fValues.x-BrushSize;i<=(int)(tmp3fValues.x+BrushSize);i++)
                  {
                     for (int j=(int)tmp3fValues.z-BrushSize;j<=(int)(tmp3fValues.z+BrushSize);j++)
                     {
                        //System.out.println("adjusting height at point x:'" + i + "' z:'" + j + "'");
                        if ((i >= 0 && i <= tb.getSize()) && (j >= 0 && j <= tb.getSize()))
                        {
                           int CurrentHeight = ib.getTrueHeightAtPoint(i,j);

                           if (RaiseTerrain)
                           {
                              CurrentHeight += AlterAmount;
                           }
                           else
                           {
                              CurrentHeight -= AlterAmount;
                           }

                           if (CurrentHeight > 255)
                           {
                              CurrentHeight = 255;
                           }
                           else if (CurrentHeight < 0)
                           {
                              CurrentHeight = 0;
                           }

                           ib.setHeightAtPoint(CurrentHeight,i,j);
                           //tb.setHeightMapValue(i,j,CurrentHeight);
                        }
                        /*else
                        {
                           System.out.println("setHM out of range...");
                        }*/
                     }
                  }

                  tb.updateFromHeightMap();

                  // if we call updateRenderState() here it screws up our lighting...
                  //state.getRootNode().updateRenderState();
                  //tb.updateRenderState();
               }
            }
         }

      }

   }

}



Edit:  I changed the code so you can "paint" with it if you hold down the button while you try to raise/lower the terrain - this makes the large amount of non-detection especially apparent when you try this
2

I'm unsure whether this is a problem with the way I'm using the function repetitively (do I need to update the terrain somehow in between each findTrianglePick?), or if it is a bug in jME itself.  If someone could at least point me in the right direction that would be nice.  I'm sure I can work around it using other methods, but I would like to understand why this doesn't work before I do that.



Thanks

3

Okay, it's a problem with the CollisionTree.



If I replace

            TMesh.findTrianglePick(ResultsRay,RAL,0);



with

            TriangleBatch TBatch = TMesh.getBatch(0);

            if (TBatch != null)
            {
               CollisionTreeManager.getInstance().getCollisionTree(TBatch).construct(TBatch, TMesh, false);
               TBatch.findTrianglePick(ResultsRay, RAL);
            }



then it gets rid of the problem.  However that obviously makes the code exponentially slower, rebuilding the CollisionTree every time the map is altered.  Is there a fast (code speed wise) way to reproduce this fix, or do I need to patch in my own code to rebuild part of the CollisionTree, instead of the entire tree?

EDIT:
I figured out the problem, and made a patch for it.  I'll post it shortly in case anyone else is interested, or you want to integrate it into jME.
4

can you post the changes as an eclipse patch?  easier to eval.

5

Okay, here's my solution.  Keep in mind this may not affect the adjacent triangles, if they are not in the same leaf.



These would be added to com.jme.bounding.CollisionTree:

   /*
    *  Find a particular CollisionTree leaf.  This is used recursively
    *
    * @param TriangleIndex The index indicating which leaf to find
    * @param RebuildBounds If true rebuild all the branches leading up to the leaf where the TriangleIndex resides, and the leaf itself.
    *
    * @return The leaf which contains the TriangleIndex, or null if not found
    */
   public CollisionTree getLeaf(int TriangleIndex, boolean RebuildBounds)
   {
      CollisionTree rtnVal = null;

      if (this.left == null && this.right == null)
      {
         // leaf
         if (TriangleIndex >= this.start && TriangleIndex < this.end)
         {
            // correct value
            rtnVal = this;
            if (RebuildBounds == true)
            {
               bounds.computeFromTris(triIndex, batch, start, end);
            }
         }
      }
      else if (TriangleIndex >= this.start && TriangleIndex < this.end) // make sure the triangle is in this branch
      {
         if (RebuildBounds == true)
         {
            bounds.computeFromTris(triIndex, batch, start, end);
         }
         
         if (this.left != null)
         {
            rtnVal = this.left.getLeaf(TriangleIndex, RebuildBounds);
         }
         
         if (rtnVal == null && this.right != null)
         {
            rtnVal = this.right.getLeaf(TriangleIndex, RebuildBounds);
         }
      }

      return rtnVal;
   }
   
   /*
    *  Checks if this branch or one of its subbranches/leaves contains the given TriangleIndex
    *
    * @return true if the index is contained, false otherwise
    */
   public boolean BranchContainsTriangle(int TriangleIndex)
   {
      if (TriangleIndex >= this.start && TriangleIndex < this.end)
      {
         return true;
      }
      else
      {
         return false;
      }
   }
   



Recommended usage would be to add triangle indexes to an arraylist or w/e as you alter them. 
Then, if you try a findTrianglePick as usual and it returns zero results, you can use getLeaf to retrieve the indexes one at a time, and rebuild the unique ones.
If this fails you would end up having to rebuild the entire tree, but that should only rarely happen.  The time that would come into play would be if an adjacent triangle in a different leaf had its size changed due to one you modified (raise one triangle and all the rest around it will slope somewhat, etc).

   ArrayList<Integer> AlteredTiles = new ArrayList<Integer>();

   public void AlterTriangleHeight(float x, float y, boolean RaiseTerrain, int AlterAmount)
   {
      game.getCamera().update();

      Ray ResultsRay = game.getDisplay().getPickRay(new Vector2f(x,y), false, null);

      TrianglePickResults PResults = new TrianglePickResults();
      PResults.setCheckDistance(true);
      Node rootNode = state.getRootNode();
      rootNode.findPick(ResultsRay, PResults);

      int ResultCount = PResults.getNumber();

      if (ResultCount > 0)
      {
         // use result 0, should be closest...
         TriMesh TMesh = (TriMesh)PResults.getPickData(0).getTargetMesh().getParentGeom();
         ArrayList<Integer> RAL = new ArrayList<Integer>();
         TriangleBatch TBatch;
         
         if (TMesh.getBatchCount() == 1)
         {
            // Pick the actual triangles out of the mesh now
            TMesh.findTrianglePick(ResultsRay,RAL,0);

            if (RAL.size() == 0)
            {
               TBatch = TMesh.getBatch(0);
               
               if (TBatch != null)
               {
                  System.out.println("rebuilding out of sync branches...");

                  while (AlteredTiles.size() > 0)
                  {
                  
                     CollisionTree tmpCT = CollisionTreeManager.getInstance().getCollisionTree(TBatch).getLeaf(AlteredTiles.get(0).intValue(), true);
                     AlteredTiles.remove(0);
                     int k=0;

                     while (k < AlteredTiles.size())
                     {
                        if (tmpCT.BranchContainsTriangle(AlteredTiles.get(k).intValue()))
                        {
                           AlteredTiles.remove(k);
                        }
                        else
                        {
                           k++;
                        }
                     }
                  }

                  TBatch.findTrianglePick(ResultsRay, RAL);

                  if (RAL.size() == 0)
                  {
                     System.out.println("rebuilding entire collisiontree...");
               
                     CollisionTreeManager.getInstance().getCollisionTree(TBatch).construct(TBatch, TMesh, false);
                     TBatch.findTrianglePick(ResultsRay, RAL);
                  }
               }
            }
            
            System.out.println("ralsize:'" + RAL.size() + "'");

            if (RAL.size() > 0)
            {
               int ClosestTri = -1;
               float ClosestDist = -1;

               // Find the closest triangle from all the results
               for (int i=0;i<RAL.size();i++)
               {
                  Vector3f[] myTri = new Vector3f[3];
                  TMesh.getTriangle(RAL.get(i).intValue(), myTri);

                  Vector3f newValues = new Vector3f();

                  if (ResultsRay.intersectWherePlanar(myTri[0].addLocal(TMesh.getWorldTranslation()), myTri[1].addLocal(TMesh.getWorldTranslation()), myTri[2].addLocal(TMesh.getWorldTranslation()), newValues))
                  {
                     if (newValues.getX() < ClosestDist || ClosestDist == -1)
                     {
                        ClosestDist = newValues.getX();
                        ClosestTri = RAL.get(i).intValue();
                     }

                  }
                  else
                  {
                     System.out.println("error no intersect!");
                  }
               }

               if (ClosestTri > -1)
               {
                  // Got one particular triangle.. start routine to alter the terrain based on this location...
                  Vector3f[] myTri2 = new Vector3f[3];
                  TMesh.getTriangle(ClosestTri, myTri2);
                  myTri2[0].addLocal(TMesh.getWorldTranslation());
                  myTri2[1].addLocal(TMesh.getWorldTranslation());
                  myTri2[2].addLocal(TMesh.getWorldTranslation());
                  AlteredTiles.add(new Integer(ClosestTri));

                  // DO ALTERING AND STUFF HERE...

                  tb.updateFromHeightMap();
               }
            }
         }

      }

   }



I didn't test the code in the last example, it is just there to give you an idea of the intended use of the functions...

EDIT:
After a bit of testing, for one leaf my code is way more efficient than rebuilding the entire tree.  For practical applications it would probably be better to pass a reference to an arraylist of indexes into the CollisionTree itself.  This would save the extra cycles of rebuilding some of the trunk sections multiple times, and help the performance scale better.  If it was done this way, the performance of this rebuild function should almost always beat rebuilding the entire tree, unless for some reason you were trying to rebuild nodes on almost every leaf of the tree.
6

Okay… now I really feel like I'm talking to myself.  Here's my final result, using an ArrayList of indexes to be rebuilt.  These go in CollisionTree as before.  As I predicted the rates on these are far better than my previous functions which only rebuilt one branch at a time.  It averages about 300 milliseconds per time you run this, maybe one of you guys can figure out a way to make it even faster…  (though 300 milliseconds is lightyears faster than rebuilding the entire tree)



   /*
    *  Rebuild all the leaves listed in TriangleIndexes, and any branches leading up to them.
    */
   public void RebuildLeaves(ArrayList<Integer> TriangleIndexes)
   {
      int i=0;
      
      if (this.left == null && this.right == null)
      {
         // is a leaf, get rid of any matching indexes and rebuild
         boolean AlreadyRebuilt = false;
         while (i < TriangleIndexes.size())
         {
            if (TriangleIndexes.get(i).intValue() >= this.start && TriangleIndexes.get(i).intValue() < this.end)
            {
               TriangleIndexes.remove(i);
               if (AlreadyRebuilt == false)
               {
                  AlreadyRebuilt = true;
                  bounds.computeFromTris(triIndex, batch, start, end);
               }
            }
            else
            {
               i++;
            }
         }
      }
      else if (ContainsAnyLeaf(TriangleIndexes))
      {   
         if (this.left != null)
         {
            this.left.RebuildLeaves(TriangleIndexes);
         }
         
         if (this.right != null)
         {
            this.right.RebuildLeaves(TriangleIndexes);
         }
         
         bounds.computeFromTris(triIndex, batch, start, end);
      }
   }
   
   /*
    *  Checks if this branch or one of its subbranches/leaves contains any of the given TriangleIndexes
    *
    * @return true if the index is contained, false otherwise
    */
   public boolean ContainsAnyLeaf(ArrayList<Integer> TriangleIndexes)
   {
      boolean rtnVal = false;
      
      for (int i=0;i<TriangleIndexes.size();i++)
      {
         if (TriangleIndexes.get(i).intValue() >= this.start && TriangleIndexes.get(i).intValue() < this.end)
         {
            rtnVal = true;
            break;
         }
      }
      
      return rtnVal;
   }

7

One suggestion for an even faster approach is to not use triangle picking for terrain.  :)  I use a class that walks the heightmap grid using your pick ray using a form of Bresenham’s line alg.  This way you only have to check the triangles along the line under your pick ray.  It’s even possible to modify this alg to do a height check instead, looking for where you go from above to below the terrain, then do triangle checks only where it makes sense.

8
renanse said:

One suggestion for an even faster approach is to not use triangle picking for terrain.  :)  I use a class that walks the heightmap grid using your pick ray using a form of Bresenham's line alg.  This way you only have to check the triangles along the line under your pick ray.  It's even possible to modify this alg to do a height check instead, looking for where you go from above to below the terrain, then do triangle checks only where it makes sense.


I'll check that out, I'm not real good at math and somewhat new to this whole 3D thing though, so I'm not sure if I can make it work (part of the reason I am using an engine like jME rather than attempting to write one from scratch!)

I will say though, that I sped up the CollisionTree method even further.  I realized that the first 2-3 largest bounding boxes take the longest to generate, and they almost never matter.  So, the methods that go in my CollisionTree now look like this:


   /*
    *  Rebuild all the leaves listed in TriangleIndexes, and any branches leading up to them.
    * 
    *  @param TriangleIndexes a list of all the leaves to rebuild
    *  @param StartLevel how many trunk levels to ignore, for none put zero (ignoring the first 2-3 levels increases speed greatly)
    */
   public void RebuildLeaves(ArrayList<Integer> TriangleIndexes, int StartLevel)
   {
      RebuildLeaves(TriangleIndexes, StartLevel, 0);
   }
      
   private void RebuildLeaves(ArrayList<Integer> TriangleIndexes, int StartLevel, int CurrentLevel)
   {
      int i=0;
      CurrentLevel++;
      
      if (this.left == null && this.right == null)
      {
         // is a leaf, get rid of any matching indexes and rebuild
         boolean AlreadyRebuilt = false;
         while (i < TriangleIndexes.size())
         {
            if (TriangleIndexes.get(i).intValue() >= this.start && TriangleIndexes.get(i).intValue() < this.end)
            {
               TriangleIndexes.remove(i);
               if (AlreadyRebuilt == false)
               {
                  AlreadyRebuilt = true;
                  bounds.computeFromTris(triIndex, batch, start, end);
               }
            }
            else
            {
               i++;
            }
         }
      }
      else if (ContainsAnyLeaf(TriangleIndexes))
      {   
         if (this.left != null)
         {
            this.left.RebuildLeaves(TriangleIndexes, StartLevel, CurrentLevel);
         }
         
         if (this.right != null)
         {
            this.right.RebuildLeaves(TriangleIndexes, StartLevel, CurrentLevel);
         }
         if (CurrentLevel > StartLevel)
         {
            bounds.computeFromTris(triIndex, batch, start, end);
         }
      }
   }
   
   /*
    *  Checks if this branch or one of its subbranches/leaves contains any of the given TriangleIndexes
    *
    * @return true if the index is contained, false otherwise
    */
   public boolean ContainsAnyLeaf(ArrayList<Integer> TriangleIndexes)
   {
      boolean rtnVal = false;
      
      for (int i=0;i<TriangleIndexes.size();i++)
      {
         if (TriangleIndexes.get(i).intValue() >= this.start && TriangleIndexes.get(i).intValue() < this.end)
         {
            rtnVal = true;
            break;
         }
      }
      
      return rtnVal;
   }



This works pretty acceptably (40-90 milliseconds per rebuild), especially considering I have updates limited to every 100ms for other reasons.  However there definitely is room for improvement there, so I might give implementing your method a shot - though at least my code is actually usable now, even though it isn't as smooth as glass.

Again, if you ever want to integrate that code into jME you have my full permission - seems like it might be useful to have sometimes.
9

Wasn't sure if you guys use unified or standard format, I see both posted on the forum - is one preferred?  Here are both formats for good measure.


Index: CollisionTree.java
===================================================================
RCS file: /cvs/jme/src/com/jme/bounding/CollisionTree.java,v
retrieving revision 1.4
diff -r1.4 CollisionTree.java
583a584,661
>    
>    /*
>     *  Rebuild all the leaves listed in TriangleIndexes, and any branches leading up to them.
>     *
>     *  @param TriangleIndexes a list of all the leaves to rebuild
>     *  @param StartLevel how many trunk levels to ignore, for none put zero (ignoring the first 2-3 levels increases speed greatly)
>     */
>    public void RebuildLeaves(ArrayList<Integer> TriangleIndexes, int StartLevel)
>    {
>       RebuildLeaves(TriangleIndexes, StartLevel, 0);
>    }
>
>    private void RebuildLeaves(ArrayList<Integer> TriangleIndexes, int StartLevel, int CurrentLevel)
>    {
>       int i=0;
>       CurrentLevel++;
>
>       if (this.left == null && this.right == null)
>       {
>          // is a leaf, get rid of any matching indexes and rebuild
>          boolean AlreadyRebuilt = false;
>          while (i < TriangleIndexes.size())
>          {
>             if (TriangleIndexes.get(i).intValue() >= this.start && TriangleIndexes.get(i).intValue() < this.end)
>             {
>                TriangleIndexes.remove(i);
>                if (AlreadyRebuilt == false)
>                {
>                   AlreadyRebuilt = true;
>                   bounds.computeFromTris(triIndex, batch, start, end);
>                }
>             }
>             else
>             {
>                i++;
>             }
>          }
>       }
>       else if (ContainsAnyLeaf(TriangleIndexes))
>       {
>          if (this.left != null)
>          {
>             this.left.RebuildLeaves(TriangleIndexes, StartLevel, CurrentLevel);
>          }
>
>          if (this.right != null)
>          {
>             this.right.RebuildLeaves(TriangleIndexes, StartLevel, CurrentLevel);
>          }
>
>          if (CurrentLevel > StartLevel)
>          {
>             bounds.computeFromTris(triIndex, batch, start, end);
>          }
>       }
>    }
>
>    /*
>     *  Checks if this branch or one of its subbranches/leaves contains any of the given TriangleIndexes
>     *
>     * @return true if the index is contained, false otherwise
>     */
>    public boolean ContainsAnyLeaf(ArrayList<Integer> TriangleIndexes)
>    {
>       boolean rtnVal = false;
>
>       for (int i=0;i<TriangleIndexes.size();i++)
>       {
>          if (TriangleIndexes.get(i).intValue() >= this.start && TriangleIndexes.get(i).intValue() < this.end)
>          {
>             rtnVal = true;
>             break;
>          }
>       }
>
>       return rtnVal;
>    }
>    



Index: src/com/jme/bounding/CollisionTree.java
===================================================================
RCS file: /cvs/jme/src/com/jme/bounding/CollisionTree.java,v
retrieving revision 1.4
diff -u -r1.4 CollisionTree.java
--- src/com/jme/bounding/CollisionTree.java   23 Dec 2007 03:57:49 -0000   1.4
+++ src/com/jme/bounding/CollisionTree.java   6 Apr 2008 17:54:47 -0000
@@ -581,4 +581,82 @@
       comparator.setBatch(batch);
       SortUtil.qsort(triIndex, start, end - 1, comparator);
    }
+   
+   /*
+    *  Rebuild all the leaves listed in TriangleIndexes, and any branches leading up to them.
+    *
+    *  @param TriangleIndexes a list of all the leaves to rebuild
+    *  @param StartLevel how many trunk levels to ignore, for none put zero (ignoring the first 2-3 levels increases speed greatly)
+    */
+   public void RebuildLeaves(ArrayList<Integer> TriangleIndexes, int StartLevel)
+   {
+      RebuildLeaves(TriangleIndexes, StartLevel, 0);
+   }
+
+   private void RebuildLeaves(ArrayList<Integer> TriangleIndexes, int StartLevel, int CurrentLevel)
+   {
+      int i=0;
+      CurrentLevel++;
+
+      if (this.left == null && this.right == null)
+      {
+         // is a leaf, get rid of any matching indexes and rebuild
+         boolean AlreadyRebuilt = false;
+         while (i < TriangleIndexes.size())
+         {
+            if (TriangleIndexes.get(i).intValue() >= this.start && TriangleIndexes.get(i).intValue() < this.end)
+            {
+               TriangleIndexes.remove(i);
+               if (AlreadyRebuilt == false)
+               {
+                  AlreadyRebuilt = true;
+                  bounds.computeFromTris(triIndex, batch, start, end);
+               }
+            }
+            else
+            {
+               i++;
+            }
+         }
+      }
+      else if (ContainsAnyLeaf(TriangleIndexes))
+      {
+         if (this.left != null)
+         {
+            this.left.RebuildLeaves(TriangleIndexes, StartLevel, CurrentLevel);
+         }
+
+         if (this.right != null)
+         {
+            this.right.RebuildLeaves(TriangleIndexes, StartLevel, CurrentLevel);
+         }
+
+         if (CurrentLevel > StartLevel)
+         {
+            bounds.computeFromTris(triIndex, batch, start, end);
+         }
+      }
+   }
+
+   /*
+    *  Checks if this branch or one of its subbranches/leaves contains any of the given TriangleIndexes
+    *
+    * @return true if the index is contained, false otherwise
+    */
+   public boolean ContainsAnyLeaf(ArrayList<Integer> TriangleIndexes)
+   {
+      boolean rtnVal = false;
+
+      for (int i=0;i<TriangleIndexes.size();i++)
+      {
+         if (TriangleIndexes.get(i).intValue() >= this.start && TriangleIndexes.get(i).intValue() < this.end)
+         {
+            rtnVal = true;
+            break;
+         }
+      }
+
+      return rtnVal;
+   }
+   
 }

10

Cool, see cvs.  (Cleaned up to match our style and formatting)

11

If you have time, check and see if your method would speed up the CollisionTreeManager for updatingCollisionTree.

12

Yeah, depending on the use.  It would be program specific, so you would want to make sure the default was still a rebuild of the whole CT, with an argument for how many levels to skip rebuilding.  I don't know what people usually need to rebuild the CT for, but if the changes to the model are minor it would speed it up considerably.  Because of the way the CT is arranged, each level you need to rebuild basically doubles the time it takes.



If you time it, it should look something like this:

All Levels: 2 seconds (318402 triangles)

All except top level: 1 second (159201 triangles)

All except top two: .5 second (79600 triangles)

All except top three: .25 seconds (39800 triangles)



Those numbers aren't exact but they're a pretty fair approximation of the results I was getting during the time I wrote RebuildLeaves


13

Hmm, well one example I can think of off the top of my head is the CollidingClothPatch.  Would be cool if your addition could be used to speed that up.