Triangle Picking

First cut at triangle picking. Works great as long as I don’t scale my inbound mesh… still working on it. It’ll be pretty easy to convert to vertex picking from here… and then texture picking.




         Vector3f mouseLoc = _mouseInputHandler.getMouse().getLocalTranslation();
         Vector2f screenPosition = new Vector2f( mouseLoc.x, mouseLoc.y + 30);
         Vector2f screenPosition2 = new Vector2f( mouseLoc.x, mouseLoc.y + 30);
         Vector3f startPoint = Application._app.getDisplay().getWorldCoordinates(screenPosition, 0.01f);
         Vector3f farWorldCoordinates = Application._app.getDisplay().getWorldCoordinates(screenPosition2, 0.99f);


         getPick( startPoint, farWorldCoordinates, _mesh);


   public boolean isTriPicked( Vector3f a, Vector3f b, Vector3f[] plane) {
      
       Vector3f normal = plane[0].subtract( plane[1]).cross( plane[0].subtract( plane[2]));
      
       float distance = -(plane[0].x * normal.x + plane[0].y * normal.y + plane[0].z * normal.z);
       float final_x,final_y,final_z,final_t;
       float t,i;
       Vector3f temp = new Vector3f();
      
       t=(float)0; i=(float)0;
       i+=(float)(normal.x*b.x)+(normal.y*b.y)+(normal.z*b.z)+(distance);
       t+=(float)(normal.x*(b.x*-1))+(normal.y*(b.y*-1))+(normal.z*(b.z*-1));
       t+=(float)(normal.x*a.x)+(normal.y*a.y)+(normal.z*a.z);
      
       if (t != 0.0f)
           final_t = (-i)/t;
       else
           final_t = 0.0f;
      
       if ((a.x == b.x)&&(a.z == b.z)) {
           temp.x = a.x;
           temp.y = (-((normal.x*a.x)+(normal.z*a.z)+(distance)))/(normal.y);
           temp.z = a.z;
       } else {
           final_x = (((a.x)*(final_t))+((b.x)*(1-final_t)));
           final_y = (((a.y)*(final_t))+((b.y)*(1-final_t)));
           final_z = (((a.z)*(final_t))+((b.z)*(1-final_t)));
          
           temp.set( final_x, final_y, final_z);
       }
      
       return pointInTri( temp, plane[0], plane[1], plane[2]);
   }
   
   public boolean pointInTri( Vector3f point, Vector3f a, Vector3f b, Vector3f c) {
       float total_angles = 0.0f;
      
       Vector3f TempVect = new Vector3f();
       TempVect.set( point.x - a.x, point.y - a.y, point.z - a.z);
       Vector3f v1 = (Vector3f) TempVect.clone();
       TempVect.set( point.x - b.x, point.y - b.y, point.z - b.z);
       Vector3f v2 = (Vector3f) TempVect.clone();
       TempVect.set( point.x - c.x, point.y - c.y, point.z - c.z);
       Vector3f v3 = (Vector3f) TempVect.clone();
      
       v1 = v1.normalize();
       v2 = v2.normalize();
       v3 = v3.normalize();
      
       float dot1 = v1.dot( v2);
       if( dot1 < -1) {
           dot1 = -1;
       }
       if( dot1 > 1) {
           dot1 = 1;
       }
       total_angles += Math.acos(dot1);
       float dot2 = v2.dot( v3);
       if( dot2 < -1) {
           dot2 = -1;
       }
       if( dot2 > 1) {
           dot2 = 1;
       }
       total_angles += Math.acos(dot2);
       float dot3 = v3.dot( v1);
       if( dot3 < -1) {
           dot3 = -1;
       }
       if( dot3 > 1) {
           dot3 = 1;
       }
       total_angles += Math.acos(dot3);
      
       if ( Math.abs(total_angles-2* Math.PI) <= 0.005) {
           return true;
       }
      
       return false;
   }
   
   public void getPick( Vector3f a, Vector3f b, TriMesh mesh) {
      
       int tris = mesh.getTriangleQuantity();
      
       for( int t = 0; t < tris; t++) {
           Vector3f[] plane = new Vector3f[3];
           mesh.getTriangle( t, plane);
           if( isTriPicked( a, b, plane)) {
               System.out.println( "TRI found: " + t);
               break;
           }
       }
      
   }



It's kind of brute force.. I just loop through the triangles of a mesh (I figured you'd pick your mesh with a bounding volume first) but the mesh I tested with has 60K+ triangles and I get sub second picks. You could probably speed this up with a specialized hash where your intersection point could be 'close' to it's destination based on an initial hash, and then just loop through the bucket.. or some such.

Special thanks to: Alan Baylis (http://members.net-tech.com.au/alaneb/selection_tutorial.html) from whom I pretty much plagerized this... I don't get quite get all the math yet.

Side NOTE: TriMesh getTriangle has a System.out that will slow things down if you don't comment it out. I'll commit a new one this evening for that issue.

Good I nead picking for my editer.

I would like to point out… kind of an afterthought and unexpected boon.



This returns the intercept point of where the ray hits the plane of the triangle that is picked. …



Now you can add your bulet hole at that location, adjusting for the size of the bullet hole texture.

Make sure you check in a Test to demonstrate new functionality.

I personally think so, as long as it is new code that compiles and isn’t going to be touched by other tests and so forth… and you don’t mind fielding questions about code you are still working on… XD remembering my water demo…