Fixed issue 444: Transform updates overly expensive

1) Refactored message processing in TransformStructure to use a more
efficient collection (HashSet).

2) Optimized isNanOrInfinity check


git-svn-id: https://svn.java.net/svn/j3d-core~svn/trunk@777 ba19aa83-45c5-6ac9-afd3-db810772062c

4 files changed, 160 insertions, 69 deletions

diff --git a/src/classes/share/javax/media/j3d/MasterControl.java b/src/classes/share/javax/media/j3d/MasterControl.java
index 584c6d3..af3d717 100644
--- a/src/classes/share/javax/media/j3d/MasterControl.java
+++ b/src/classes/share/javax/media/j3d/MasterControl.java
@@ -3361,6 +3361,9 @@ class MasterControl {
 		    timestampUpdateList.clear();
 		    updateMirrorObjects();
 		    done = true;
+
+//                    // Instrumentation of Java 3D renderer
+//                    printTimes();
 		}
 	    }
 	    break;
@@ -3612,4 +3615,59 @@ class MasterControl {
     private int getNumberOfProcessors() {
         return Runtime.getRuntime().availableProcessors();
     }
+
+    //
+    // The following framework supports code instrumentation. To enable this:
+    //     1) Uncomment all of the following code
+    //     2) Uncomment the call to printTimes (in doWork)
+    //     3) Uncomment the calls to nanoTime and recordTimes in the Renderer
+    //
+    // Then add code of the following form to areas that you want to enable for
+    // timing:
+    //
+    //     long startTime = System.nanoTime();
+    //     sortTransformGroups(tSize, tgs);
+    //     long deltaTime = System.nanoTime() - startTime;
+    //     VirtualUniverse.mc.recordTime(MasterControl.TimeType.XXXXX, deltaTime);
+    //
+    // where "XXXXX" is the enum representing the code segment being timed.
+    //
+
+//    static enum TimeType {
+//        TOTAL_FRAME,
+//        RENDER,
+//        // BEHAVIOR,
+//        // TRANSFORM_UPDATE,
+//        // ...
+//    }
+//    
+//    private long[] times = new long[TimeType.values().length];
+//    private int[] counts = new int[TimeType.values().length];
+//    private int frameTick = 0;
+//
+//    synchronized void recordTime(TimeType type, long deltaTime) {
+//        int idx = type.ordinal();
+//        times[idx] += deltaTime;
+//        counts[idx]++;
+//    }
+//    
+//    private synchronized void printTimes() {
+//        if (++frameTick >= 10) {
+//            System.err.println("\n-------------------------------------------------------------------");
+//            for (int i = 0; i < times.length; i++) {
+//                if (counts[i] > 0) {
+//                    System.err.println(TimeType.values()[i] + " [" + counts[i] + "] = " +
+//                            ((double)times[i] / 1000000.0 / (double)counts[i]) + " msec per call" );
+//                    times[i] = 0L;
+//                    counts[i] = 0;
+//                } else {
+//                    assert times[i] == 0L;
+//                    System.err.println(TimeType.values()[i] +
+//                            " [" + 0 + "] = 0.0 msec" );
+//                }
+//            }
+//            frameTick = 0;
+//        }
+//    }
+
 }
diff --git a/src/classes/share/javax/media/j3d/Renderer.java b/src/classes/share/javax/media/j3d/Renderer.java
index 67f5815..82f69b6 100644
--- a/src/classes/share/javax/media/j3d/Renderer.java
+++ b/src/classes/share/javax/media/j3d/Renderer.java
@@ -160,6 +160,9 @@ class Renderer extends J3dThread {
     // It is used when sharedCtx = true;
     ArrayList textureIDResourceTable = new ArrayList(5);
 
+//    // Instrumentation of Java 3D renderer
+//    private long lastSwapTime = System.nanoTime();
+
     private synchronized int newInstanceNum() {
 	return (++numInstances);
     }
@@ -284,6 +287,12 @@ class Renderer extends J3dThread {
                             cv.view.inCanvasCallback = false;
                             // Clear canvasDirty bit ONLY when postSwap() success
 
+//                            // Instrumentation of Java 3D renderer
+//                            long currSwapTime = System.nanoTime();
+//                            long deltaTime = currSwapTime - lastSwapTime;
+//                            lastSwapTime = currSwapTime;
+//                            VirtualUniverse.mc.recordTime(MasterControl.TimeType.TOTAL_FRAME, deltaTime);
+
                             // Set all dirty bits except environment set and lightbin
                             // they are only set dirty if the last used light bin or
                             // environment set values for this canvas change between
@@ -757,6 +766,8 @@ class Renderer extends J3dThread {
 
 		    m[nmesg++].decRefcount();
 		} else { // retained mode rendering
+//                    // Instrumentation of Java 3D renderer
+//                    long startRenderTime = System.nanoTime();
 
 		    m[nmesg++].decRefcount();
                     
@@ -1470,6 +1481,10 @@ class Renderer extends J3dThread {
 			    offBufRetained.geomLock.unLock();
 			}	
 		    }
+
+//                    // Instrumentation of Java 3D renderer
+//                    long deltaTime = System.nanoTime() - startRenderTime;
+//                    VirtualUniverse.mc.recordTime(MasterControl.TimeType.RENDER, deltaTime);
 		}
 	    }
 
diff --git a/src/classes/share/javax/media/j3d/Transform3D.java b/src/classes/share/javax/media/j3d/Transform3D.java
index 75fd54a..c9d4ca4 100644
--- a/src/classes/share/javax/media/j3d/Transform3D.java
+++ b/src/classes/share/javax/media/j3d/Transform3D.java
@@ -2122,7 +2122,7 @@ public class Transform3D {
 	mat[13] = m1.m31;
 	mat[14] = m1.m32;
 	mat[15] = m1.m33;
-
+        
 	dirtyBits = ALL_DIRTY;
 
 	if (autoNormalize)  {
@@ -5778,12 +5778,15 @@ public class Transform3D {
     // Fix for Issue 167 -- don't classify matrices with Infinity or NaN values
     // as affine
     private final boolean isInfOrNaN() {
+        // The following is a faster version of the check.
+        // Instead of 3 tests per array element (Double.isInfinite is 2 tests),
+        // for a total of 48 tests, we will do 16 multiplies and 1 test.
+        double d = 0.0;
         for (int i = 0; i < 16; i++) {
-            if (Double.isNaN(mat[i]) || Double.isInfinite(mat[i])) {
-                return true;
-            }
+            d *= mat[i];
         }
-        return false;
+
+        return d != 0.0;
     }
 
     // Fix for Issue 253
diff --git a/src/classes/share/javax/media/j3d/TransformStructure.java b/src/classes/share/javax/media/j3d/TransformStructure.java
index 347a790..9083888 100644
--- a/src/classes/share/javax/media/j3d/TransformStructure.java
+++ b/src/classes/share/javax/media/j3d/TransformStructure.java
@@ -19,65 +19,49 @@ import java.util.*;
  */
 
 class TransformStructure extends J3dStructure implements ObjectUpdate {
+
     /**
-     * An ArrayList of TransformGroups to traverse
-     */
-    UnorderList traverseList = new UnorderList(TransformGroupRetained.class);
-    
-    /**
-     * A Parallel ArrayList of Transforms for the traverse list
+     * A set of TransformGroups and associated Transform3Ds to traverse
      */
-    UnorderList transformList = new UnorderList(Transform3D.class);
+    private HashSet<TransformData> transformSet = new HashSet<TransformData>();
 
-    ArrayList objectList = new ArrayList();
+    private ArrayList objectList = new ArrayList();
 
     /**
      * arraylist of the bounding leaf users affected by the transform
      */
-    ArrayList blUsers = new ArrayList();
+    private ArrayList blUsers = new ArrayList();
 
     // to gather transform targets
-    UpdateTargets targets = new UpdateTargets();
+    private UpdateTargets targets = new UpdateTargets();
 
     /**
      * An arrayList of nodes that need collisionBounds updates 
      */
-    ArrayList collisionObjectList = new ArrayList();
-
-    // The object that contains the dynamic HashKey - a string type object
-    HashKey key = new HashKey(250);
+    private ArrayList collisionObjectList = new ArrayList();
 
     // List of dirty TransformGroups
-    ArrayList dirtyTransformGroups = new ArrayList();
+    private ArrayList dirtyTransformGroups = new ArrayList();
 
     // Associated Keys with the dirtyNodeGroup
-    ArrayList keySet = new ArrayList();
-
-    // current locale under traversal
-    Locale locale = null;    
-
-    // The transform used in intermediate calc
-    Transform3D currentTrans = new Transform3D();
-
-    TransformGroupRetained tgs[];
-    Transform3D t3ds[];
+    private ArrayList keySet = new ArrayList();
 
     // the active list contains changed TransformGroup minus those that
     // have been switched-off, plus those that have been changed but
     // just switched-on
-    UnorderList activeTraverseList =
-		new UnorderList(TransformGroupRetained.class);
-
+    private ArrayList<TransformGroupRetained> activeTraverseList =
+            new ArrayList<TransformGroupRetained>();
+    
     // contains TG that have been previously changed but just switched-on
-    ArrayList switchDirtyTgList = new ArrayList(1);
+    private ArrayList switchDirtyTgList = new ArrayList(1);
 
-    boolean lazyUpdate = false;
+    private boolean lazyUpdate = false;
 
     // ArrayList of switches that have changed, use for lastSwitchOn updates
-    ArrayList switchChangedList = new ArrayList();
+    private ArrayList switchChangedList = new ArrayList();
 
     // true if already in MasterControl's update object list
-    boolean inUpdateObjectList = false;
+    private boolean inUpdateObjectList = false;
 
     /**
      * This constructor does nothing
@@ -85,12 +69,12 @@ class TransformStructure extends J3dStructure implements ObjectUpdate {
     TransformStructure(VirtualUniverse u) {
 	super(u, J3dThread.UPDATE_TRANSFORM);
     }
-  
+
     void processMessages(long referenceTime) {
 	J3dMessage[] messages = getMessages(referenceTime);
 	int nMsg = getNumMessage();
 	J3dMessage m;
-	int i, index;
+	int i;
 
 	if (nMsg <= 0) {
 	    return;
@@ -107,16 +91,12 @@ class TransformStructure extends J3dStructure implements ObjectUpdate {
 	    for (i = (nMsg-1); i >= 0; i--) {
 		m = messages[i];
 		if (m.type == J3dMessage.TRANSFORM_CHANGED) {
-		    index = traverseList.indexOf(m.args[1]);
-		    // if this transform group isn't in our list, add
-		    // the information
-		    if (index == -1) {
-			traverseList.add(m.args[1]);
-			transformList.add(m.args[2]);
-		    }
+		    // Add the TG and associated transform. Since this is a
+                    // set, duplicates will be culled.
+                    transformSet.add(new TransformData((TransformGroupRetained)m.args[1], (Transform3D)m.args[2]));
 		}
 	    }
-	    
+
 	    for (i=0; i<nMsg; i++) {
 		m = messages[i];
 		
@@ -205,7 +185,7 @@ class TransformStructure extends J3dStructure implements ObjectUpdate {
 
 	lazyUpdate = false;
 
-	tSize = transformList.size();
+        tSize = transformSet.size();
         sSize = switchDirtyTgList.size();
         if (tSize <= 0 && sSize <= 0) {
             return;
@@ -214,11 +194,11 @@ class TransformStructure extends J3dStructure implements ObjectUpdate {
         // process TG with setTransform changes
 	// update Transform3D, switchDirty and lToVwDrity flags
 	if (tSize > 0) {
-            tgs = (TransformGroupRetained[])traverseList.toArray(false);
-            t3ds = (Transform3D[])transformList.toArray(false);
-            for (i=0; i<tSize; i++) {
-	        tg = tgs[i];
-                tg.currentTransform.set(t3ds[i]);
+            Iterator<TransformData> it = transformSet.iterator();
+            while(it.hasNext()) {
+                TransformData lData = it.next();
+                tg = lData.getTransformGroupRetained();
+                tg.currentTransform.set(lData.getTransform3D());
 
                 synchronized(tg) { // synchronized with tg.set/clearLive
                 if(tg.perPathData != null) {
@@ -281,23 +261,20 @@ class TransformStructure extends J3dStructure implements ObjectUpdate {
 
         // merge switchDirty into activeTraverseList
         if (sSize > 0) {
-            int size = switchDirtyTgList.size();
-            for (i=0; i<size; i++) {
-                // Note: UnorderList does not implement addAll
-                activeTraverseList.add(switchDirtyTgList.get(i));
-            }
+            activeTraverseList.addAll(switchDirtyTgList);
             switchDirtyTgList.clear();
 	    lazyUpdate = true;
         }
 
         // activeTraverseList contains switched-on tg as well
-        tgs = (TransformGroupRetained[])activeTraverseList.toArray(false);
         tSize = activeTraverseList.size();
+        TransformGroupRetained[] tgs =
+                (TransformGroupRetained[])activeTraverseList.toArray(new TransformGroupRetained[tSize]);
 
         // process active TGs
         if (tSize > 0) {
 
-            sortTransformGroups(tSize);
+            sortTransformGroups(tSize, tgs);
 
             // update lToVw and gather targets
             for (i=0; i<tSize; i++) {
@@ -310,22 +287,21 @@ class TransformStructure extends J3dStructure implements ObjectUpdate {
 	    }
         }
 
-	transformList.clear();
-	traverseList.clear();
+        transformSet.clear();
         activeTraverseList.clear();
     }
 
 
-    private void sortTransformGroups(int size) {
+    private void sortTransformGroups(int size, TransformGroupRetained[] tgs) {
         if (size < 7) {
-            insertSort(size);
+            insertSort(size, tgs);
         } else {
-            quicksort(0, size-1);
+            quicksort(0, size-1, tgs);
         }
     }
 
     // Insertion sort on smallest arrays
-    private void insertSort(int size) {
+    private void insertSort(int size, TransformGroupRetained[] tgs) {
         for (int i=0; i<size; i++) {
             for (int j=i; j>0 && 
 		 (tgs[j-1].maxTransformLevel > tgs[j].maxTransformLevel); j--) {
@@ -336,7 +312,7 @@ class TransformStructure extends J3dStructure implements ObjectUpdate {
         }
     }
 
-    private void quicksort( int l, int r ) {
+    private void quicksort( int l, int r, TransformGroupRetained[] tgs ) {
         int i = l;
         int j = r;
         double k = tgs[(l+r) / 2].maxTransformLevel;
@@ -353,8 +329,8 @@ class TransformStructure extends J3dStructure implements ObjectUpdate {
              }
          } while (i<=j);
 
-         if (l<j) quicksort(l,j);
-         if (l<r) quicksort(i,r);
+         if (l<j) quicksort(l,j, tgs);
+         if (l<r) quicksort(i,r, tgs);
     }
 
     
@@ -722,4 +698,43 @@ class TransformStructure extends J3dStructure implements ObjectUpdate {
     }
 
     void cleanup() {}
+
+    // Wrapper for a (TransformGroupRetained, Transform3D) pair
+    // TransformGroupRetained is effectively used as the key in the
+    // HashSet
+    private class TransformData {
+        private TransformGroupRetained transformGroupRetained;
+        private Transform3D transform3D;
+
+        TransformData( TransformGroupRetained tgr, Transform3D t3d )  {
+            transformGroupRetained = tgr;
+            transform3D = t3d;
+        }
+
+        // Hashcode and equals test only evaluate TransformGroupRetained
+        @Override
+        public int hashCode() {
+            return transformGroupRetained.hashCode();
+        }
+
+        // Hashcode and equals test only evaluate TransformGroupRetained
+        @Override
+        public boolean equals(Object o) {
+            if (!(o instanceof TransformData)) {
+                return false;
+            }
+
+            return transformGroupRetained.equals(((TransformData)o).getTransformGroupRetained());
+        }
+
+        TransformGroupRetained getTransformGroupRetained() {
+            return transformGroupRetained;
+        }
+
+        Transform3D getTransform3D() {
+            return transform3D;
+        }
+
+    }
+
 }