j3dcore: flatten the directory structure a bit

Signed-off-by: Harvey Harrison <[email protected]>

1 files changed, 1154 insertions, 0 deletions

diff --git a/src/javax/media/j3d/BHTree.java b/src/javax/media/j3d/BHTree.java
new file mode 100644
index 0000000..260448c
--- /dev/null
+++ b/src/javax/media/j3d/BHTree.java
@@ -0,0 +1,1154 @@
+/*
+ * Copyright 1999-2008 Sun Microsystems, Inc.  All Rights Reserved.
+ * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER.
+ *
+ * This code is free software; you can redistribute it and/or modify it
+ * under the terms of the GNU General Public License version 2 only, as
+ * published by the Free Software Foundation.  Sun designates this
+ * particular file as subject to the "Classpath" exception as provided
+ * by Sun in the LICENSE file that accompanied this code.
+ *
+ * This code is distributed in the hope that it will be useful, but WITHOUT
+ * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
+ * FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License
+ * version 2 for more details (a copy is included in the LICENSE file that
+ * accompanied this code).
+ *
+ * You should have received a copy of the GNU General Public License version
+ * 2 along with this work; if not, write to the Free Software Foundation,
+ * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA.
+ *
+ * Please contact Sun Microsystems, Inc., 4150 Network Circle, Santa Clara,
+ * CA 95054 USA or visit www.sun.com if you need additional information or
+ * have any questions.
+ *
+ */
+
+package javax.media.j3d;
+
+import java.util.ArrayList;
+import java.util.Vector;
+
+import javax.vecmath.Point4d;
+
+class BHTree  {
+
+    Locale locale;
+
+    private BHNode root;
+    private BHInsertStructure insertStructure = null;
+
+    // Temporary point, so we dont generate garbage
+    Point4d tPoint4d = new Point4d();
+
+    // A flag to signal that number of renderAtoms sent to RenderBin is stable.
+    private boolean stable = false;
+
+    // An estimate of the maxmium depth of this tree (upper bound).
+    int estMaxDepth;
+
+    static final double LOG_OF_2 = Math.log(2);
+
+    // Assume that the size avg. leaf node is 256 bytes. For a 64bit system, we'll
+    // down with max depth of 56 for an ideal balance tree.
+    static final int DEPTH_UPPER_BOUND = 56;
+    static final int INCR_DEPTH_BOUND = 5;
+    int  depthUpperBound = DEPTH_UPPER_BOUND;
+
+    BHTree() {
+	locale = null;
+	root = null;
+    }
+
+    BHTree(Locale loc) {
+	locale = loc;
+	root = null;
+    }
+
+    BHTree(BHNode bhArr[]) {
+	locale = null;
+	root = null;
+	create(bhArr);
+    }
+
+    void setLocale(Locale loc) {
+	locale = loc;
+    }
+
+    Locale getLocale() {
+	return locale;
+    }
+
+    void cluster(BHInternalNode root, BHNode[] bhArr) {
+
+	if(J3dDebug.devPhase) {
+	    if(J3dDebug.doDebug(J3dDebug.bHTree, J3dDebug.LEVEL_4,
+				"BHTree.java :In cluster length is " + bhArr.length
+				+ "\n")) {
+
+		for(int i=0; i<bhArr.length; i++) {
+		    System.err.println(bhArr[i]);
+		}
+	    }
+	}
+
+	if((bhArr == null) || (bhArr.length < 2) || (root == null)){
+	    if(J3dDebug.devPhase)
+		J3dDebug.doDebug(J3dDebug.bHTree, J3dDebug.LEVEL_1,
+				 "BHTree.java : cluster : trouble! \n");
+	    return;
+	}
+
+	int centerValuesIndex[] = new int[bhArr.length];
+	float centerValues[][] = computeCenterValues(bhArr, centerValuesIndex);
+
+	constructTree(root, bhArr, centerValues, centerValuesIndex);
+
+    }
+
+    // bhArr can only contains BHLeafNode.
+
+    void boundsChanged(BHNode bhArr[], int size) {
+	// Mark phase.
+	markParentChain(bhArr, size);
+
+	// Compute phase.
+	root.updateMarkedBoundingHull();
+    }
+
+
+    // Return true if bhTree's root in encompass by frustumBBox and nothing changed.
+    boolean getVisibleBHTrees(RenderBin rBin, ArrayList bhTrees,
+			      BoundingBox frustumBBox, long referenceTime,
+			      boolean stateChanged, int visibilityPolicy,
+			      boolean singleLocale) {
+
+	int i, j, size;
+
+	if ((frustumBBox != null) && (root != null)) {
+
+	    boolean inSide = aEncompassB(frustumBBox, root.bHull);
+	    /*
+	      System.err.println("stateChanged is " + stateChanged);
+	      System.err.println("frustumBBox is " + frustumBBox);
+	      System.err.println("root.bHull is " + root.bHull);
+	      System.err.println("inSide is " + inSide);
+	    */
+
+	    if(singleLocale && !stateChanged && inSide && stable) {
+		// just return the whole tree, no change in render mol..
+		// System.err.println("Optimize case 1 ..." + this);
+		bhTrees.add(root);
+		return true;
+	    }
+	    else if(!stateChanged && inSide) {
+		// the whole tree is in, but we've to be sure that RenderBin is
+		// stable ...
+		// System.err.println("Optimize case 2 ..." + this);
+		select(rBin, bhTrees, frustumBBox, root, referenceTime,
+		       visibilityPolicy, true);
+
+		bhTrees.add(root);
+		stable = true;
+	    } else {
+		// System.err.println("Not in Optimize case ..." + this);
+		select(rBin, bhTrees, frustumBBox, root, referenceTime,
+		       visibilityPolicy, false);
+
+		stable = false;
+	    }
+
+	}
+
+	return false;
+    }
+
+    private void select(RenderBin rBin, ArrayList bhTrees, BoundingBox frustumBBox,
+			BHNode bh, long referenceTime, int visibilityPolicy,
+			boolean inSide) {
+
+	if ((bh == null) || (bh.bHull.isEmpty())) {
+	    return;
+	}
+
+	switch(bh.nodeType) {
+	case BHNode.BH_TYPE_LEAF:
+	    if((((BHLeafNode) bh).leafIF instanceof GeometryAtom) &&
+	       (((BHLeafNode) bh).isEnable(visibilityPolicy)) &&
+	       ((inSide) ||  (frustumBBox.intersect(bh.bHull)))) {
+
+	       // do render atom setup.
+		rBin.processGeometryAtom((GeometryAtom)
+					 (((BHLeafNode)bh).leafIF),
+					 referenceTime);
+		if(!inSide) {
+		    bhTrees.add(bh);
+		}
+	    }
+	    break;
+	case BHNode.BH_TYPE_INTERNAL:
+	    if(inSide) {
+		select(rBin, bhTrees, frustumBBox,
+		       ((BHInternalNode)bh).getRightChild(),
+		       referenceTime, visibilityPolicy, true);
+		select(rBin, bhTrees, frustumBBox,
+		       ((BHInternalNode)bh).getLeftChild(),
+		       referenceTime, visibilityPolicy, true);
+	    }
+	    else if(aEncompassB(frustumBBox, bh.bHull)) {
+		bhTrees.add(bh);
+		select(rBin, bhTrees, frustumBBox,
+		       ((BHInternalNode)bh).getRightChild(),
+		       referenceTime, visibilityPolicy, true);
+		select(rBin, bhTrees, frustumBBox,
+		       ((BHInternalNode)bh).getLeftChild(),
+		       referenceTime, visibilityPolicy, true);
+	    }
+	    else if(frustumBBox.intersect(bh.bHull)) {
+		select(rBin, bhTrees, frustumBBox,
+		       ((BHInternalNode)bh).getRightChild(),
+		       referenceTime, visibilityPolicy, false);
+		select(rBin, bhTrees, frustumBBox,
+		       ((BHInternalNode)bh).getLeftChild(),
+		       referenceTime, visibilityPolicy, false);
+	    }
+	    break;
+	}
+    }
+
+    // returns true iff the bBox is completely inside aBox
+    // i.e.  bBoxl values are strictly less than or equal to all aBox values.
+    static boolean aEncompassB(BoundingBox aBox, BoundingBox bBox) {
+	return ((aBox.upper.x >= bBox.upper.x) &&
+		(aBox.upper.y >= bBox.upper.y) &&
+		(aBox.upper.z >= bBox.upper.z) &&
+		(aBox.lower.x <= bBox.lower.x) &&
+		(aBox.lower.y <= bBox.lower.y) &&
+		(aBox.lower.z <= bBox.lower.z));
+    }
+
+
+    BHLeafInterface selectAny(GeometryAtom atom, int accurancyMode) {
+	if (atom.source.geometryList == null)
+	    return null;
+	BHNode bhNode = doSelectAny(atom, root, accurancyMode);
+	if (bhNode == null) {
+	    return null;
+	}
+
+	return ((BHLeafNode) bhNode).leafIF;
+    }
+
+
+    BHLeafInterface selectAny(GeometryAtom atoms[], int size, int accurancyMode) {
+	BHNode bhNode = doSelectAny(atoms, size, root, accurancyMode);
+	if (bhNode == null) {
+	    return null;
+	}
+
+	return ((BHLeafNode) bhNode).leafIF;
+    }
+
+
+    private BHNode doSelectAny(GeometryAtom atoms[],int atomSize,
+			       BHNode bh, int accurancyMode) {
+	if ((bh == null) || (bh.bHull.isEmpty())) {
+	    return null;
+	}
+	switch (bh.nodeType) {
+	case BHNode.BH_TYPE_LEAF:
+	    BHLeafInterface leaf = ((BHLeafNode) bh).leafIF;
+	    GeometryAtom atom;
+	    int i;
+
+	    if (leaf instanceof GeometryAtom) {
+		GeometryAtom leafAtom = (GeometryAtom) leaf;
+
+		if (((BHLeafNode) bh).isEnable() &&
+		    leafAtom.source.isCollidable) {
+
+		    // atom self intersection between atoms[]
+		    for (i=atomSize-1; i >=0; i--) {
+			if (atoms[i] == leafAtom) {
+			    return null;
+			}
+		    }
+		    for (i=atomSize-1; i >=0; i--) {
+			atom = atoms[i];
+			if ((atom.source.sourceNode != leafAtom.source.sourceNode) &&
+			    (atom.source.collisionVwcBound.intersect(leafAtom.source.collisionVwcBound)) &&
+			    ((accurancyMode == WakeupOnCollisionEntry.USE_BOUNDS) ||
+			     ((leafAtom.source.geometryList != null) &&
+			      (atom.source.intersectGeometryList(leafAtom.source))))) {
+			    return bh;
+			}
+		    }
+		}
+	    } else if (leaf instanceof GroupRetained) {
+		if (((BHLeafNode) bh).isEnable() &&
+		    ((GroupRetained) leaf).sourceNode.collidable) {
+		    for (i=atomSize-1; i >=0; i--) {
+			atom = atoms[i];
+			if (atom.source.collisionVwcBound.intersect(bh.bHull) &&
+			    ((accurancyMode == WakeupOnCollisionEntry.USE_BOUNDS) ||
+			     (atom.source.intersectGeometryList(
+			     atom.source.getCurrentLocalToVworld(0), bh.bHull)))) {
+			    return bh;
+			}
+		    }
+		}
+	    }
+	    return null;
+	case BHNode.BH_TYPE_INTERNAL:
+	    for (i=atomSize-1; i >=0; i--) {
+		atom = atoms[i];
+		if (atom.source.collisionVwcBound.intersect(bh.bHull))
+		    {
+			BHNode hitNode = doSelectAny(atoms,
+						     atomSize,
+						     ((BHInternalNode) bh).getRightChild(),
+						     accurancyMode);
+			if (hitNode != null)
+			    return hitNode;
+
+			return doSelectAny(atoms, atomSize,
+					   ((BHInternalNode) bh).getLeftChild(),
+					   accurancyMode);
+		    }
+	    }
+	    return null;
+	}
+	return null;
+    }
+
+
+    private BHNode doSelectAny(GeometryAtom atom, BHNode bh, int accurancyMode) {
+	if ((bh == null) || (bh.bHull.isEmpty())) {
+	    return null;
+	}
+	switch (bh.nodeType) {
+	case BHNode.BH_TYPE_LEAF:
+	    BHLeafInterface leaf = ((BHLeafNode) bh).leafIF;
+	    if (leaf instanceof GeometryAtom) {
+		GeometryAtom leafAtom = (GeometryAtom) leaf;
+		if ((atom.source.sourceNode != leafAtom.source.sourceNode) &&
+		    (((BHLeafNode) bh).isEnable()) &&
+		    (leafAtom.source.isCollidable) &&
+		    (atom.source.collisionVwcBound.intersect(leafAtom.source.collisionVwcBound)) &&
+		    ((accurancyMode == WakeupOnCollisionEntry.USE_BOUNDS) ||
+		     ((leafAtom.source.geometryList != null) &&
+		      (atom.source.intersectGeometryList(leafAtom.source))))) {
+		    return bh;
+		}
+	    } else if (leaf instanceof GroupRetained) {
+		if (((BHLeafNode) bh).isEnable() &&
+		    ((GroupRetained) leaf).sourceNode.collidable &&
+		    atom.source.collisionVwcBound.intersect(bh.bHull) &&
+		    ((accurancyMode == WakeupOnCollisionEntry.USE_BOUNDS) ||
+		     (atom.source.intersectGeometryList(
+			atom.source.getCurrentLocalToVworld(0), bh.bHull)))) {
+		    return bh;
+		}
+	    }
+	    return null;
+	case BHNode.BH_TYPE_INTERNAL:
+	    if (atom.source.collisionVwcBound.intersect(bh.bHull)) {
+		BHNode hitNode = doSelectAny(atom,
+					     ((BHInternalNode) bh).getRightChild(),
+					     accurancyMode);
+		if (hitNode != null)
+		    return hitNode;
+
+		return doSelectAny(atom,
+				   ((BHInternalNode) bh).getLeftChild(),
+				   accurancyMode);
+	    }
+	    return null;
+	}
+	return null;
+    }
+
+    BHLeafInterface selectAny(Bounds bound, int accurancyMode,
+			      NodeRetained armingNode) {
+	if (bound == null) {
+	    return null;
+	}
+	BHNode bhNode = doSelectAny(bound, root, accurancyMode, armingNode);
+	if (bhNode == null) {
+	    return null;
+	}
+	return ((BHLeafNode) bhNode).leafIF;
+    }
+
+    private BHNode doSelectAny(Bounds bound, BHNode bh, int accurancyMode,
+			       NodeRetained armingNode) {
+	if ((bh == null) || (bh.bHull.isEmpty())) {
+	    return null;
+	}
+
+	switch (bh.nodeType) {
+	case BHNode.BH_TYPE_LEAF:
+	    BHLeafInterface leaf = ((BHLeafNode) bh).leafIF;
+	    if (leaf instanceof GeometryAtom) {
+		GeometryAtom leafAtom = (GeometryAtom) leaf;
+		if ((((BHLeafNode) bh).isEnable()) &&
+		    (leafAtom.source.isCollidable) &&
+		    (bound.intersect(leafAtom.source.collisionVwcBound)) &&
+		    ((accurancyMode == WakeupOnCollisionEntry.USE_BOUNDS) ||
+		     ((leafAtom.source.geometryList != null) &&
+		      (leafAtom.source.intersectGeometryList(
+			leafAtom.source.getCurrentLocalToVworld(0), bound))))) {
+		    return bh;
+		}
+	    } else if (leaf instanceof GroupRetained) {
+		if ((leaf != armingNode) &&
+		    ((BHLeafNode) bh).isEnable() &&
+		    ((GroupRetained) leaf).sourceNode.collidable &&
+		    bound.intersect(bh.bHull)) {
+		    return bh;
+		}
+	    }
+	    return null;
+	case BHNode.BH_TYPE_INTERNAL:
+	    if (bound.intersect(bh.bHull)) {
+		BHNode hitNode = doSelectAny(bound,
+				      ((BHInternalNode) bh).getRightChild(),
+				      accurancyMode,
+				      armingNode);
+		if (hitNode != null)
+		    return hitNode;
+
+		return doSelectAny(bound,
+				   ((BHInternalNode) bh).getLeftChild(),
+				   accurancyMode,
+				   armingNode);
+	    }
+	    return null;
+	}
+	return null;
+    }
+
+
+    BHLeafInterface selectAny(Bounds bound, int accurancyMode,
+			      GroupRetained armingGroup) {
+	if (bound == null) {
+	    return null;
+	}
+	BHNode bhNode = doSelectAny(bound, root, accurancyMode, armingGroup);
+	if (bhNode == null) {
+	    return null;
+	}
+	return ((BHLeafNode) bhNode).leafIF;
+    }
+
+    private BHNode doSelectAny(Bounds bound, BHNode bh, int accurancyMode,
+			       GroupRetained armingGroup) {
+	if ((bh == null) || (bh.bHull.isEmpty())) {
+	    return null;
+	}
+	switch (bh.nodeType) {
+	case BHNode.BH_TYPE_LEAF:
+	    BHLeafInterface leaf = ((BHLeafNode) bh).leafIF;
+
+	    if (leaf instanceof GeometryAtom) {
+		GeometryAtom leafAtom = (GeometryAtom) leaf;
+		if ((((BHLeafNode) bh).isEnable()) &&
+		    (leafAtom.source.isCollidable) &&
+		    (bound.intersect(leafAtom.source.collisionVwcBound)) &&
+	 	    (!isDescendent(leafAtom.source.sourceNode,
+				   armingGroup, leafAtom.source.key)) &&
+		    ((accurancyMode == WakeupOnCollisionEntry.USE_BOUNDS) ||
+		     ((leafAtom.source.geometryList != null) &&
+		      (leafAtom.source.intersectGeometryList(
+			leafAtom.source.getCurrentLocalToVworld(0), bound))))) {
+		    return bh;
+		}
+	    } else if (leaf instanceof GroupRetained) {
+		GroupRetained group = (GroupRetained) leaf;
+		if (((BHLeafNode) bh).isEnable() &&
+		    group.sourceNode.collidable &&
+		    bound.intersect(bh.bHull) &&
+		    !isDescendent(group.sourceNode, armingGroup, group.key)) {
+			return bh;
+		}
+	    }
+	    return null;
+	case BHNode.BH_TYPE_INTERNAL:
+	    if (bound.intersect(bh.bHull)) {
+		BHNode hitNode = doSelectAny(bound,
+				      ((BHInternalNode) bh).getRightChild(),
+				      accurancyMode,
+				      armingGroup);
+		if (hitNode != null)
+		    return hitNode;
+
+		return doSelectAny(bound,
+				   ((BHInternalNode) bh).getLeftChild(),
+				   accurancyMode,
+				   armingGroup);
+	    }
+	    return null;
+	}
+	return null;
+    }
+
+    // Return true if node is a descendent of group
+    private boolean isDescendent(NodeRetained node,
+				 GroupRetained group,
+				 HashKey key) {
+
+	synchronized (group.universe.sceneGraphLock) {
+	    if (node.inSharedGroup) {
+		// getlastNodeId() will destroy this key
+		if (key != null) {
+		    key = new HashKey(key);
+		}
+	    }
+
+	    do {
+		if (node == group) {
+		    return true;
+		}
+		if (node instanceof SharedGroupRetained) {
+		    // retrieve the last node ID
+		    String nodeId = key.getLastNodeId();
+		    NodeRetained prevNode = node;
+			Vector<NodeRetained> parents = ((SharedGroupRetained)node).parents;
+		    for(int i=parents.size()-1; i >=0; i--) {
+				NodeRetained link = parents.get(i);
+			if (link.nodeId.equals(nodeId)) {
+			    node = link;
+			    break;
+			}
+		    }
+		    if (prevNode == node) {
+			// branch is already detach
+			return true;
+		    }
+		}
+		node = node.parent;
+	    } while (node != null); // reach Locale
+	}
+	return false;
+    }
+
+
+    void select(PickShape pickShape, UnorderList hitArrList) {
+
+	if((pickShape == null)||(root == null))
+	    return;
+
+	doSelect(pickShape, hitArrList, root, tPoint4d);
+
+    }
+
+
+    private void doSelect(PickShape pickShape, UnorderList hitArrList,
+			  BHNode bh, Point4d pickPos) {
+
+	if ((bh == null) || (bh.bHull.isEmpty())) {
+	    return;
+	}
+
+	switch(bh.nodeType) {
+	case BHNode.BH_TYPE_LEAF:
+	    if (((BHLeafNode)(bh)).isEnable() &&
+		(((BHLeafNode) bh).leafIF instanceof GeometryAtom) &&
+		 ((GeometryAtom) (((BHLeafNode)
+				   bh).leafIF)).source.isPickable &&
+		pickShape.intersect(bh.bHull, pickPos)) {
+		hitArrList.add(bh);
+	    }
+	    break;
+	case BHNode.BH_TYPE_INTERNAL:
+	    if (pickShape.intersect(bh.bHull, pickPos)) {
+		doSelect(pickShape,
+			 hitArrList,
+			 ((BHInternalNode)bh).getRightChild(),
+			 pickPos);
+		doSelect(pickShape,
+			 hitArrList,
+			 ((BHInternalNode)bh).getLeftChild(),
+			 pickPos);
+	    }
+	    break;
+	}
+    }
+
+    BHNode selectAny(PickShape pickShape) {
+
+	if((pickShape == null)||(root == null))
+	    return null;
+
+	return doSelectAny(pickShape, root, tPoint4d);
+
+    }
+
+
+    private BHNode doSelectAny(PickShape pickShape, BHNode bh, Point4d pickPos) {
+
+	BHNode hitNode = null;
+
+	if((bh == null) || (bh.bHull.isEmpty()))
+	    return null;
+
+	switch(bh.nodeType) {
+	case BHNode.BH_TYPE_LEAF:
+	    if (((BHLeafNode)(bh)).isEnable() &&
+		(((BHLeafNode) bh).leafIF instanceof GeometryAtom) &&
+		((GeometryAtom) (((BHLeafNode)
+				   bh).leafIF)).source.isPickable &&
+		pickShape.intersect(bh.bHull, pickPos)) {
+		return bh;
+	    }
+	    break;
+	case BHNode.BH_TYPE_INTERNAL:
+	    if (pickShape.intersect(bh.bHull, pickPos)) {
+		hitNode = doSelectAny(pickShape,
+				      ((BHInternalNode)bh).getRightChild(),
+				      pickPos);
+
+		if (hitNode != null) {
+		    return hitNode;
+		}
+
+		return doSelectAny(pickShape,
+				   ((BHInternalNode)bh).getLeftChild(),
+				   pickPos);
+	    }
+	    break;
+	}
+	return null;
+    }
+
+
+    private void create(BHNode bhArr[]) {
+	int i;
+
+	if(bhArr == null) {
+	    root = null;
+	    return;
+	}
+
+	if(bhArr.length == 1) {
+	    bhArr[0].computeBoundingHull();
+	    root = (BHNode)bhArr[0];
+	    return;
+	}
+
+	int centerValuesIndex[] = new int[bhArr.length];
+	float centerValues[][] = computeCenterValues(bhArr, centerValuesIndex);
+
+	/*
+	  System.err.println("Length of array is " +  bhArr.length);
+	  for(int kk=0; kk<bhArr.length;kk++) {
+	  System.err.println("( " + centerValues[kk][0] + ", " +
+	  centerValues[kk][1] + ", " + centerValues[kk][2] + " )");
+	  }
+	  */
+
+	root = new BHInternalNode();
+	constructTree((BHInternalNode) root, bhArr, centerValues,
+		      centerValuesIndex);
+
+
+	if(J3dDebug.devPhase && J3dDebug.debug)
+	    gatherTreeStatistics();
+
+    }
+
+    void insert(BHNode bhArr[], int size) {
+	// first pass: add all elements to the tree creating k array internal
+	// nodes using the auxiliaryInsertStucture
+	// second pass: go through all elements of the auxiliaryInsertStructure
+	// and then update these nodes reclustering the trees with the new
+	// k element siblings ...
+
+	if(J3dDebug.devPhase && J3dDebug.debug)
+	    J3dDebug.doDebug(J3dDebug.bHTree, J3dDebug.LEVEL_4,
+			     "BHTree.java : Insert - bhArr.length is " +
+			     bhArr.length + "\n");
+
+	if((bhArr == null) || (size < 1) || (bhArr.length < 1))
+	    return;
+
+	if(root == null) {
+	    if(J3dDebug.devPhase)
+		J3dDebug.doDebug(J3dDebug.bHTree, J3dDebug.LEVEL_4,
+				 "BHTree.java : Tree has not be created yet.\n");
+
+	    // This extra "new" is needed, because create() require its input
+	    // array's length be equal to the number of inserted nodes.
+	    BHNode[] newbhArr = new BHNode[size];
+	    System.arraycopy(bhArr, 0, newbhArr, 0, size);
+	    create(newbhArr);
+	    return;
+	}
+
+	if(root.nodeType == BHNode.BH_TYPE_LEAF) {
+	    BHNode[] oldBhArr = bhArr;
+	    bhArr = new BHNode[size + 1];
+	    System.arraycopy(oldBhArr, 0, bhArr, 0, size);
+	    bhArr[size] = root;
+	    create(bhArr);
+	    return;
+	}
+
+	if(insertStructure == null) {
+	    insertStructure = new BHInsertStructure(size);
+	}
+	else {
+	    insertStructure.clear();
+	}
+
+	for (int i=0; i<size; i++) {
+	    // test if its inside the 'root' element
+	    if ( root.isInside(bhArr[i].bHull) ) {
+		((BHInternalNode)root).insert(bhArr[i], insertStructure);
+	    }
+	    else {
+		// extend the bounds of root  by joining with current element
+		root.bHull.combine(bhArr[i].bHull);
+		insertStructure.lookupAndInsert(root, bhArr[i]);
+	    }
+	}
+
+	insertStructure.updateBoundingTree(this);
+	// System.err.println("BHTree - Inserting ...");
+
+        // Issue 353: clear temporary insertStructure so we don't leak.
+        insertStructure.clear();
+
+	// Guard against size<1 is done at the start of this method.
+	estMaxDepth += (int) (Math.log(size)/LOG_OF_2) + 1;
+
+	if(estMaxDepth > depthUpperBound) {
+	    int maxDepth = root.computeMaxDepth(0);
+	    int leafCount = root.countNumberOfLeaves();
+	    double compDepth = Math.log(leafCount)/LOG_OF_2;
+	    /*
+	      System.err.println("BHTree - evaluate for reConstructTree ...");
+	      System.err.println("compDepth " + compDepth);
+	      System.err.println("maxDepth " + maxDepth);
+	      System.err.println("leafCount " + leafCount);
+	      */
+
+	    // Upper bound guard.
+	    if(maxDepth > depthUpperBound) {
+		reConstructTree(leafCount);
+		maxDepth = root.computeMaxDepth(0);
+		/*
+		  System.err.println("BHTree - Did reConstructTree ...");
+		  System.err.println("compDepth " + compDepth);
+		  System.err.println("maxDepth " + maxDepth);
+		  */
+	    }
+
+	    // Adjust depthUpperBound according to app. need.
+	    // If we encounter lots of overlapping bounds, the re-balanced
+	    // tree may not be an ideal balance tree. So there might be a
+	    // likehood of maxDepth exceeding the preset depthUpperBound.
+	    if(maxDepth > depthUpperBound) {
+	    	depthUpperBound = depthUpperBound + INCR_DEPTH_BOUND;
+	    }else if((depthUpperBound != DEPTH_UPPER_BOUND) &&
+		     (maxDepth * 1.5 < depthUpperBound)) {
+		depthUpperBound = depthUpperBound - INCR_DEPTH_BOUND;
+
+		if(depthUpperBound < DEPTH_UPPER_BOUND) {
+		    // Be sure that DEPTH_UPPER_BOUND is the min.
+		    depthUpperBound = DEPTH_UPPER_BOUND;
+		}
+	    }
+
+	    // This is the only place for resetting estMaxDepth to the tree real
+	    // maxDepth. Hence in cases where tree may get deteriorate fast, such
+	    // as multiple inserts and deletes frequently. estMaxDepth is accuminated,
+	    // and will lead to tree re-evaluation and possibly re-balancing.
+	    estMaxDepth = maxDepth;
+	}
+
+    }
+
+
+    // mark all elements of the node and its parent as needing updating
+    private void markParentChain(BHNode[] nArr, int size) {
+	BHNode node;
+
+	for(int i=0; i<size; i++) {
+	    node = nArr[i];
+	    node.mark = true;
+	    while((node.parent != null) && (node.parent.mark == false)) {
+		node = node.parent;
+		node.mark = true;
+	    }
+	}
+    }
+
+    // mark all elements of the node and its parent as needing updating
+    private void markParentChain(BHNode node) {
+	node.mark = true;
+	while((node.parent != null) && (node.parent.mark == false)) {
+	    node = node.parent;
+	    node.mark = true;
+	}
+    }
+
+    // Delete a series of n node elements from the input binary tree.
+    // These elements are removed from the tree in a 2 phase process.
+    // First, all elements to be removed are marked and all parent
+    // chains are marked ... then a second phase of the algorithm goes
+    // through and deletes them and updates all of the bounds ...
+
+    // delete the n elements in the array from the tree
+    void delete(BHNode bhArr[], int size) {
+	BHNode node;
+
+	/*
+	  if((bhArr == null) || (bhArr.length < 1))
+	  return;
+	  System.err.println("BHTree.java : delete - bhArr.length is " +
+	  bhArr.length);
+	  for(int i=0; i<bhArr.length; i++)
+	  System.err.println("bhArr[" + i +"] " + bhArr[i]);
+
+	    */
+
+	for(int i=0; i<size; i++) {
+	    if((bhArr[i] != null) && (bhArr[i].nodeType == BHNode.BH_TYPE_LEAF)) {
+		markParentChain(bhArr[i]);
+	    } else {
+		if(J3dDebug.devPhase)
+		    J3dDebug.doDebug(J3dDebug.bHTree, J3dDebug.LEVEL_1,
+				     "Warning, element " + i + " is null/not leaf node.\n"
+				     + "Error in deletion routine, element " +
+				     bhArr[i] + "\n" +
+				     "In tree = " + this +
+				     " can not delete it ...\n");
+	    }
+
+	}
+
+	root = root.deleteAndUpdateMarkedNodes();
+
+	if(J3dDebug.devPhase)
+	    if (root == null) {
+		J3dDebug.doDebug(J3dDebug.bHTree, J3dDebug.LEVEL_4,
+				 "Tree has been completely deleted ...\n");
+	    }
+    }
+
+    // compute the center values along each of the three dimensions given
+    // the array of leaf objects to be split and joined
+    float[][] computeCenterValues(BHNode[] bhArr, int[] cIndex) {
+	float centers[][] = new float[bhArr.length][3];
+
+	// compute the center values of the input array of nodes
+	for ( int i=0; i < bhArr.length; i++ ) {
+	    cIndex[i] = i;
+
+	    bhArr[i].computeBoundingHull();
+
+	    centers[i][0] =
+		(float)((bhArr[i].bHull.upper.x + bhArr[i].bHull.lower.x))/ 2.0f;
+	    centers[i][1] =
+		(float)((bhArr[i].bHull.upper.y + bhArr[i].bHull.lower.y)) / 2.0f;
+	    centers[i][2] =
+		(float)((bhArr[i].bHull.upper.z + bhArr[i].bHull.lower.z)) / 2.0f;
+
+	}
+	return centers;
+    }
+
+
+    void computeMeansAndSumSquares(float[][] centerValues, int[] centerValuesIndex,
+				   float[] means, float[] ss) {
+
+	int i, arrLen;
+	float sumCenters[] = new float[3];
+	float temp = 0.0f;
+
+	arrLen = centerValuesIndex.length;
+	// Initialization.
+	for(i=2; i>=0; i--) {
+	    sumCenters[i] = 0.0f;
+	    ss[i] = 0.0f;
+	}
+
+	for(i=arrLen-1; i>=0 ; i--) {
+	    sumCenters[0] += centerValues[centerValuesIndex[i]][0];
+	    sumCenters[1] += centerValues[centerValuesIndex[i]][1];
+	    sumCenters[2] += centerValues[centerValuesIndex[i]][2];
+	}
+
+	means[0] = sumCenters[0]/(float)arrLen;
+	means[1] = sumCenters[1]/(float)arrLen;
+	means[2] = sumCenters[2]/(float)arrLen;
+
+	for(i=arrLen-1; i>=0 ; i--) {
+	    temp = (centerValues[centerValuesIndex[i]][0] - means[0]);
+	    ss[0] += (temp*temp);
+	    temp = (centerValues[centerValuesIndex[i]][1] - means[1]);
+	    ss[1] += (temp*temp);
+	    temp = (centerValues[centerValuesIndex[i]][2] - means[2]);
+	    ss[2] += (temp*temp);
+
+	}
+
+    }
+
+    // find the split axis (the highest ss and return its index) for
+    // a given set of ss values
+    int findSplitAxis ( float ss[] ) {
+	int splitAxis = -1;
+	float maxSS = 0.0f;
+
+	// the largest ss  index value
+	for (int i=0; i < 3; i++) {
+	    if ( ss[i] > maxSS ) {
+		maxSS = ss[i];
+		splitAxis = i;
+	    }
+	}
+	return splitAxis;
+    }
+
+    // Recursive method for constructing a binary tree.
+    void constructTree( BHInternalNode parent, BHNode bhArr[],
+			float[][] centerValues,
+			int[] centerValuesIndex ){
+
+	int i, splitAxis;
+	int rightSetCount = 0;
+	int leftSetCount = 0;
+	float means[] = new float[3];
+	float ss[] = new float[3];
+
+	if(J3dDebug.devPhase)
+	    if ( bhArr.length <= 1 ) {
+		// this is only here for debugging can be removed after testing
+		// to ensure that it never gets called
+		J3dDebug.doDebug(J3dDebug.bHTree, J3dDebug.LEVEL_1,
+				 "constructTree - bhArr.length <= 1. Bad !!!\n");
+	    }
+
+	computeMeansAndSumSquares(centerValues, centerValuesIndex, means, ss);
+
+	splitAxis = findSplitAxis(ss);
+
+	// an array of decision variables for storing the values of inside
+	// the right or left set for a particular element of bhArr.
+	// true if its in the left set, false if its in the right set
+	boolean leftOrRightSet[] = new boolean[bhArr.length];
+
+	if ( splitAxis == -1 ) {
+	    // This is bad. Since we can't find a split axis, the best thing
+	    // to do is to split the set in two sets; each with about the
+	    // same number of elements. By doing this we can avoid constructing
+	    // a skew tree.
+
+	    // split elements into half.
+	    for ( i=0; i < bhArr.length; i++) {
+		if(leftSetCount > rightSetCount) {
+		    rightSetCount++;
+		    leftOrRightSet[i] = false;
+		} else {
+		    leftSetCount++;
+		    leftOrRightSet[i] = true;
+		}
+	    }
+	}
+	else {
+	    for ( i=0; i < bhArr.length; i++) {
+		// the split criterion, special multiple equals cases added
+		if ( centerValues[centerValuesIndex[i]][splitAxis] <
+		     means[splitAxis]) {
+
+		    if(J3dDebug.devPhase)
+			J3dDebug.doDebug(J3dDebug.bHTree, J3dDebug.LEVEL_4,
+					 "Found a left element\n");
+		    leftSetCount++;
+		    leftOrRightSet[i] = true;
+		} else if ( centerValues[centerValuesIndex[i]][splitAxis] >
+			    means[splitAxis]) {
+		    if(J3dDebug.devPhase)
+			J3dDebug.doDebug(J3dDebug.bHTree, J3dDebug.LEVEL_4,
+					 "Found a right element\n");
+		    rightSetCount++;
+		    leftOrRightSet[i] = false;
+		} else {
+		    if(J3dDebug.devPhase)
+			J3dDebug.doDebug(J3dDebug.bHTree, J3dDebug.LEVEL_4,
+					 "Found an equal element\n");
+		    if(leftSetCount > rightSetCount) {
+			rightSetCount++;
+			leftOrRightSet[i] = false;
+		    } else {
+			leftSetCount++;
+			leftOrRightSet[i] = true;
+		    }
+		}
+	    }
+	}
+
+	if(J3dDebug.devPhase)
+	    J3dDebug.doDebug(J3dDebug.bHTree, J3dDebug.LEVEL_2,
+			     "LeftSetCount " + leftSetCount + " RightSetCount "+
+			     rightSetCount + "\n");
+
+
+	// Don't think that this guard is needed, but still like to have it.
+	// Just in case, bad means and the sum of squares might lead us into the guard.
+	if (leftSetCount == bhArr.length) {
+	    if(J3dDebug.devPhase)
+		J3dDebug.doDebug(J3dDebug.bHTree, J3dDebug.LEVEL_1,
+				 "Split Axis of = " + splitAxis + " didn't yield "+
+				 "any split among the objects ?\n");
+	    // split elements into half
+	    rightSetCount = 0;
+	    leftSetCount = 0;
+	    for ( i=0; i < bhArr.length; i++) {
+		if(leftSetCount > rightSetCount) {
+		    rightSetCount++;
+		    leftOrRightSet[i] = false;
+		} else {
+		    leftSetCount++;
+		    leftOrRightSet[i] = true;
+		}
+	    }
+	} else if (rightSetCount == bhArr.length) {
+	    if(J3dDebug.devPhase)
+		J3dDebug.doDebug(J3dDebug.bHTree, J3dDebug.LEVEL_1,
+				 "Split Axis of = " + splitAxis + " didn't yield "+
+				 "any split among the objects ?\n");
+	    // split elements into half
+	    rightSetCount = 0;
+	    leftSetCount = 0;
+	    for ( i=0; i < bhArr.length; i++) {
+		if(leftSetCount > rightSetCount) {
+		    rightSetCount++;
+		    leftOrRightSet[i] = false;
+		} else {
+		    leftSetCount++;
+		    leftOrRightSet[i] = true;
+		}
+	    }
+	}
+
+	if(J3dDebug.devPhase)
+	    if(J3dDebug.doDebug(J3dDebug.bHTree, J3dDebug.LEVEL_4))
+		// check to make sure that rightSet and leftSet sum to the
+		// number of elements in the original array.
+		if ( bhArr.length != (rightSetCount + leftSetCount) ) {
+		    System.err.println("An error has occurred in spliting");
+		}
+
+	BHNode rightSet[] = new BHNode[rightSetCount];
+	BHNode leftSet[] = new BHNode[leftSetCount];
+	int centerValuesIndexR[] = new int[rightSetCount];
+	int centerValuesIndexL[] = new int[leftSetCount];
+
+	rightSetCount = 0;
+	leftSetCount = 0;
+
+	for (i=0; i < bhArr.length; i++) {
+	    if ( leftOrRightSet[i] ) { // element in left set
+		leftSet[leftSetCount] = bhArr[i];
+		centerValuesIndexL[leftSetCount] = centerValuesIndex[i];
+		leftSetCount++;
+	    } else {
+		rightSet[rightSetCount] = bhArr[i];
+		centerValuesIndexR[rightSetCount] = centerValuesIndex[i];
+		rightSetCount++;
+	    }
+	}
+
+	if (rightSet.length != 1) {
+	    parent.rChild = new BHInternalNode();
+	    parent.rChild.setParent(parent);
+	    constructTree((BHInternalNode)(parent.rChild),  rightSet, centerValues,
+			  centerValuesIndexR);
+	} else {
+	    parent.rChild = rightSet[0];
+	    parent.rChild.setParent(parent);
+	}
+
+	if (leftSet.length != 1) {
+	    parent.lChild = new BHInternalNode();
+	    parent.lChild.setParent(parent);
+	    constructTree((BHInternalNode)(parent.lChild), leftSet, centerValues,
+			  centerValuesIndexL);
+	} else {
+	    parent.lChild = leftSet[0];
+	    parent.lChild.setParent(parent);
+	}
+
+	parent.combineBHull(parent.rChild, parent.lChild);
+    }
+
+
+    void reConstructTree(int numOfLeaf) {
+	if(root == null)
+	    return;
+
+	BHNode bhArr[] = new BHNode[numOfLeaf];
+	int index[] = new int[1];
+	index[0] = 0;
+	root.destroyTree(bhArr, index);
+
+	/*
+	  if(bhArr.length != index[0])
+	  System.err.println("BHTree - This isn't right!!! - bhArr.length " +
+	  bhArr.length + " index " + index[0]);
+	  */
+
+	create(bhArr);
+
+    }
+
+    void gatherTreeStatistics() {
+
+	int leafCount = root.countNumberOfLeaves();
+	int internalCount = root.countNumberOfInternals();
+	int maxDepth = root.computeMaxDepth(0);
+	float averageDepth = root.computeAverageLeafDepth ( leafCount, 0);
+
+
+	System.err.println("Statistics for tree = " + this);
+	System.err.println("Total Number of nodes in tree = " +
+			   (leafCount + internalCount) );
+	System.err.println("Number of Leaf Nodes = " + leafCount );
+	System.err.println("Number of Internal Nodes = " + internalCount );
+	System.err.println("Maximum Leaf depth = " + maxDepth );
+	System.err.println("Average Leaf depth = " + averageDepth );
+	System.err.println("root.bHull = " + root.bHull);
+	// printTree(root);
+
+    }
+
+
+    void printTree(BHNode bh) {
+	if(bh!= null) {
+	    if(bh.nodeType == BHNode.BH_TYPE_INTERNAL) {
+		System.err.println("BH_TYPE_INTERNAL - bHull : " + bh);
+		System.err.println(bh.bHull);
+		System.err.println("rChild : " + ((BHInternalNode)bh).rChild +
+				   " lChild : " + ((BHInternalNode)bh).lChild);
+		printTree(((BHInternalNode)bh).rChild);
+		printTree(((BHInternalNode)bh).lChild);
+	    }
+	    else if(bh.nodeType == BHNode.BH_TYPE_LEAF) {
+		System.err.println("BH_TYPE_LEAF - bHull : " + bh);
+		System.err.println(bh.bHull);
+	    }
+
+	}
+
+
+    }
+}
+
+
+
+
+
+