aboutsummaryrefslogtreecommitdiffstats
path: root/src/javax/media/j3d/BHTree.java
diff options
context:
space:
mode:
Diffstat (limited to 'src/javax/media/j3d/BHTree.java')
-rw-r--r--src/javax/media/j3d/BHTree.java1154
1 files changed, 0 insertions, 1154 deletions
diff --git a/src/javax/media/j3d/BHTree.java b/src/javax/media/j3d/BHTree.java
deleted file mode 100644
index 260448c..0000000
--- a/src/javax/media/j3d/BHTree.java
+++ /dev/null
@@ -1,1154 +0,0 @@
-/*
- * 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);
- }
-
- }
-
-
- }
-}
-
-
-
-
-
-
generated by cgit v1.2.3 (git 2.39.1) at 2025-04-23 11:35:48 +0000