0001: /*
0002: * $RCSfile: BHTree.java,v $
0003: *
0004: * Copyright 1999-2008 Sun Microsystems, Inc. All Rights Reserved.
0005: * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER.
0006: *
0007: * This code is free software; you can redistribute it and/or modify it
0008: * under the terms of the GNU General Public License version 2 only, as
0009: * published by the Free Software Foundation. Sun designates this
0010: * particular file as subject to the "Classpath" exception as provided
0011: * by Sun in the LICENSE file that accompanied this code.
0012: *
0013: * This code is distributed in the hope that it will be useful, but WITHOUT
0014: * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
0015: * FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
0016: * version 2 for more details (a copy is included in the LICENSE file that
0017: * accompanied this code).
0018: *
0019: * You should have received a copy of the GNU General Public License version
0020: * 2 along with this work; if not, write to the Free Software Foundation,
0021: * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA.
0022: *
0023: * Please contact Sun Microsystems, Inc., 4150 Network Circle, Santa Clara,
0024: * CA 95054 USA or visit www.sun.com if you need additional information or
0025: * have any questions.
0026: *
0027: * $Revision: 1.8 $
0028: * $Date: 2008/02/28 20:17:19 $
0029: * $State: Exp $
0030: */
0031:
0032: package javax.media.j3d;
0033:
0034: import java.util.ArrayList;
0035: import java.util.Vector;
0036: import javax.vecmath.Point4d;
0037:
0038: class BHTree {
0039:
0040: Locale locale;
0041:
0042: private BHNode root;
0043: private BHInsertStructure insertStructure = null;
0044:
0045: // Temporary point, so we dont generate garbage
0046: Point4d tPoint4d = new Point4d();
0047:
0048: // A flag to signal that number of renderAtoms sent to RenderBin is stable.
0049: private boolean stable = false;
0050:
0051: // An estimate of the maxmium depth of this tree (upper bound).
0052: int estMaxDepth;
0053:
0054: static final double LOG_OF_2 = Math.log(2);
0055:
0056: // Assume that the size avg. leaf node is 256 bytes. For a 64bit system, we'll
0057: // down with max depth of 56 for an ideal balance tree.
0058: static final int DEPTH_UPPER_BOUND = 56;
0059: static final int INCR_DEPTH_BOUND = 5;
0060: int depthUpperBound = DEPTH_UPPER_BOUND;
0061:
0062: BHTree() {
0063: locale = null;
0064: root = null;
0065: }
0066:
0067: BHTree(Locale loc) {
0068: locale = loc;
0069: root = null;
0070: }
0071:
0072: BHTree(BHNode bhArr[]) {
0073: locale = null;
0074: root = null;
0075: create(bhArr);
0076: }
0077:
0078: void setLocale(Locale loc) {
0079: locale = loc;
0080: }
0081:
0082: Locale getLocale() {
0083: return locale;
0084: }
0085:
0086: void cluster(BHInternalNode root, BHNode[] bhArr) {
0087:
0088: if (J3dDebug.devPhase) {
0089: if (J3dDebug.doDebug(J3dDebug.bHTree, J3dDebug.LEVEL_4,
0090: "BHTree.java :In cluster length is " + bhArr.length
0091: + "\n")) {
0092:
0093: for (int i = 0; i < bhArr.length; i++) {
0094: System.err.println(bhArr[i]);
0095: }
0096: }
0097: }
0098:
0099: if ((bhArr == null) || (bhArr.length < 2) || (root == null)) {
0100: if (J3dDebug.devPhase)
0101: J3dDebug.doDebug(J3dDebug.bHTree, J3dDebug.LEVEL_1,
0102: "BHTree.java : cluster : trouble! \n");
0103: return;
0104: }
0105:
0106: int centerValuesIndex[] = new int[bhArr.length];
0107: float centerValues[][] = computeCenterValues(bhArr,
0108: centerValuesIndex);
0109:
0110: constructTree(root, bhArr, centerValues, centerValuesIndex);
0111:
0112: }
0113:
0114: // bhArr can only contains BHLeafNode.
0115:
0116: void boundsChanged(BHNode bhArr[], int size) {
0117: // Mark phase.
0118: markParentChain(bhArr, size);
0119:
0120: // Compute phase.
0121: root.updateMarkedBoundingHull();
0122: }
0123:
0124: // Return true if bhTree's root in encompass by frustumBBox and nothing changed.
0125: boolean getVisibleBHTrees(RenderBin rBin, ArrayList bhTrees,
0126: BoundingBox frustumBBox, long referenceTime,
0127: boolean stateChanged, int visibilityPolicy,
0128: boolean singleLocale) {
0129:
0130: int i, j, size;
0131:
0132: if ((frustumBBox != null) && (root != null)) {
0133:
0134: boolean inSide = aEncompassB(frustumBBox, root.bHull);
0135: /*
0136: System.err.println("stateChanged is " + stateChanged);
0137: System.err.println("frustumBBox is " + frustumBBox);
0138: System.err.println("root.bHull is " + root.bHull);
0139: System.err.println("inSide is " + inSide);
0140: */
0141:
0142: if (singleLocale && !stateChanged && inSide && stable) {
0143: // just return the whole tree, no change in render mol..
0144: // System.err.println("Optimize case 1 ..." + this);
0145: bhTrees.add(root);
0146: return true;
0147: } else if (!stateChanged && inSide) {
0148: // the whole tree is in, but we've to be sure that RenderBin is
0149: // stable ...
0150: // System.err.println("Optimize case 2 ..." + this);
0151: select(rBin, bhTrees, frustumBBox, root, referenceTime,
0152: visibilityPolicy, true);
0153:
0154: bhTrees.add(root);
0155: stable = true;
0156: } else {
0157: // System.err.println("Not in Optimize case ..." + this);
0158: select(rBin, bhTrees, frustumBBox, root, referenceTime,
0159: visibilityPolicy, false);
0160:
0161: stable = false;
0162: }
0163:
0164: }
0165:
0166: return false;
0167: }
0168:
0169: private void select(RenderBin rBin, ArrayList bhTrees,
0170: BoundingBox frustumBBox, BHNode bh, long referenceTime,
0171: int visibilityPolicy, boolean inSide) {
0172:
0173: if ((bh == null) || (bh.bHull.isEmpty())) {
0174: return;
0175: }
0176:
0177: switch (bh.nodeType) {
0178: case BHNode.BH_TYPE_LEAF:
0179: if ((((BHLeafNode) bh).leafIF instanceof GeometryAtom)
0180: && (((BHLeafNode) bh).isEnable(visibilityPolicy))
0181: && ((inSide) || (frustumBBox.intersect(bh.bHull)))) {
0182:
0183: // do render atom setup.
0184: rBin.processGeometryAtom(
0185: (GeometryAtom) (((BHLeafNode) bh).leafIF),
0186: referenceTime);
0187: if (!inSide) {
0188: bhTrees.add(bh);
0189: }
0190: }
0191: break;
0192: case BHNode.BH_TYPE_INTERNAL:
0193: if (inSide) {
0194: select(rBin, bhTrees, frustumBBox,
0195: ((BHInternalNode) bh).getRightChild(),
0196: referenceTime, visibilityPolicy, true);
0197: select(rBin, bhTrees, frustumBBox,
0198: ((BHInternalNode) bh).getLeftChild(),
0199: referenceTime, visibilityPolicy, true);
0200: } else if (aEncompassB(frustumBBox, bh.bHull)) {
0201: bhTrees.add(bh);
0202: select(rBin, bhTrees, frustumBBox,
0203: ((BHInternalNode) bh).getRightChild(),
0204: referenceTime, visibilityPolicy, true);
0205: select(rBin, bhTrees, frustumBBox,
0206: ((BHInternalNode) bh).getLeftChild(),
0207: referenceTime, visibilityPolicy, true);
0208: } else if (frustumBBox.intersect(bh.bHull)) {
0209: select(rBin, bhTrees, frustumBBox,
0210: ((BHInternalNode) bh).getRightChild(),
0211: referenceTime, visibilityPolicy, false);
0212: select(rBin, bhTrees, frustumBBox,
0213: ((BHInternalNode) bh).getLeftChild(),
0214: referenceTime, visibilityPolicy, false);
0215: }
0216: break;
0217: }
0218: }
0219:
0220: // returns true iff the bBox is completely inside aBox
0221: // i.e. bBoxl values are strictly less than or equal to all aBox values.
0222: static boolean aEncompassB(BoundingBox aBox, BoundingBox bBox) {
0223: return ((aBox.upper.x >= bBox.upper.x)
0224: && (aBox.upper.y >= bBox.upper.y)
0225: && (aBox.upper.z >= bBox.upper.z)
0226: && (aBox.lower.x <= bBox.lower.x)
0227: && (aBox.lower.y <= bBox.lower.y) && (aBox.lower.z <= bBox.lower.z));
0228: }
0229:
0230: BHLeafInterface selectAny(GeometryAtom atom, int accurancyMode) {
0231: if (atom.source.geometryList == null)
0232: return null;
0233: BHNode bhNode = doSelectAny(atom, root, accurancyMode);
0234: if (bhNode == null) {
0235: return null;
0236: }
0237:
0238: return ((BHLeafNode) bhNode).leafIF;
0239: }
0240:
0241: BHLeafInterface selectAny(GeometryAtom atoms[], int size,
0242: int accurancyMode) {
0243: BHNode bhNode = doSelectAny(atoms, size, root, accurancyMode);
0244: if (bhNode == null) {
0245: return null;
0246: }
0247:
0248: return ((BHLeafNode) bhNode).leafIF;
0249: }
0250:
0251: private BHNode doSelectAny(GeometryAtom atoms[], int atomSize,
0252: BHNode bh, int accurancyMode) {
0253: if ((bh == null) || (bh.bHull.isEmpty())) {
0254: return null;
0255: }
0256: switch (bh.nodeType) {
0257: case BHNode.BH_TYPE_LEAF:
0258: BHLeafInterface leaf = ((BHLeafNode) bh).leafIF;
0259: GeometryAtom atom;
0260: int i;
0261:
0262: if (leaf instanceof GeometryAtom) {
0263: GeometryAtom leafAtom = (GeometryAtom) leaf;
0264:
0265: if (((BHLeafNode) bh).isEnable()
0266: && leafAtom.source.isCollidable) {
0267:
0268: // atom self intersection between atoms[]
0269: for (i = atomSize - 1; i >= 0; i--) {
0270: if (atoms[i] == leafAtom) {
0271: return null;
0272: }
0273: }
0274: for (i = atomSize - 1; i >= 0; i--) {
0275: atom = atoms[i];
0276: if ((atom.source.sourceNode != leafAtom.source.sourceNode)
0277: && (atom.source.collisionVwcBound
0278: .intersect(leafAtom.source.collisionVwcBound))
0279: && ((accurancyMode == WakeupOnCollisionEntry.USE_BOUNDS) || ((leafAtom.source.geometryList != null) && (atom.source
0280: .intersectGeometryList(leafAtom.source))))) {
0281: return bh;
0282: }
0283: }
0284: }
0285: } else if (leaf instanceof GroupRetained) {
0286: if (((BHLeafNode) bh).isEnable()
0287: && ((GroupRetained) leaf).sourceNode.collidable) {
0288: for (i = atomSize - 1; i >= 0; i--) {
0289: atom = atoms[i];
0290: if (atom.source.collisionVwcBound
0291: .intersect(bh.bHull)
0292: && ((accurancyMode == WakeupOnCollisionEntry.USE_BOUNDS) || (atom.source
0293: .intersectGeometryList(
0294: atom.source
0295: .getCurrentLocalToVworld(0),
0296: bh.bHull)))) {
0297: return bh;
0298: }
0299: }
0300: }
0301: }
0302: return null;
0303: case BHNode.BH_TYPE_INTERNAL:
0304: for (i = atomSize - 1; i >= 0; i--) {
0305: atom = atoms[i];
0306: if (atom.source.collisionVwcBound.intersect(bh.bHull)) {
0307: BHNode hitNode = doSelectAny(atoms, atomSize,
0308: ((BHInternalNode) bh).getRightChild(),
0309: accurancyMode);
0310: if (hitNode != null)
0311: return hitNode;
0312:
0313: return doSelectAny(atoms, atomSize,
0314: ((BHInternalNode) bh).getLeftChild(),
0315: accurancyMode);
0316: }
0317: }
0318: return null;
0319: }
0320: return null;
0321: }
0322:
0323: private BHNode doSelectAny(GeometryAtom atom, BHNode bh,
0324: int accurancyMode) {
0325: if ((bh == null) || (bh.bHull.isEmpty())) {
0326: return null;
0327: }
0328: switch (bh.nodeType) {
0329: case BHNode.BH_TYPE_LEAF:
0330: BHLeafInterface leaf = ((BHLeafNode) bh).leafIF;
0331: if (leaf instanceof GeometryAtom) {
0332: GeometryAtom leafAtom = (GeometryAtom) leaf;
0333: if ((atom.source.sourceNode != leafAtom.source.sourceNode)
0334: && (((BHLeafNode) bh).isEnable())
0335: && (leafAtom.source.isCollidable)
0336: && (atom.source.collisionVwcBound
0337: .intersect(leafAtom.source.collisionVwcBound))
0338: && ((accurancyMode == WakeupOnCollisionEntry.USE_BOUNDS) || ((leafAtom.source.geometryList != null) && (atom.source
0339: .intersectGeometryList(leafAtom.source))))) {
0340: return bh;
0341: }
0342: } else if (leaf instanceof GroupRetained) {
0343: if (((BHLeafNode) bh).isEnable()
0344: && ((GroupRetained) leaf).sourceNode.collidable
0345: && atom.source.collisionVwcBound
0346: .intersect(bh.bHull)
0347: && ((accurancyMode == WakeupOnCollisionEntry.USE_BOUNDS) || (atom.source
0348: .intersectGeometryList(atom.source
0349: .getCurrentLocalToVworld(0),
0350: bh.bHull)))) {
0351: return bh;
0352: }
0353: }
0354: return null;
0355: case BHNode.BH_TYPE_INTERNAL:
0356: if (atom.source.collisionVwcBound.intersect(bh.bHull)) {
0357: BHNode hitNode = doSelectAny(atom,
0358: ((BHInternalNode) bh).getRightChild(),
0359: accurancyMode);
0360: if (hitNode != null)
0361: return hitNode;
0362:
0363: return doSelectAny(atom, ((BHInternalNode) bh)
0364: .getLeftChild(), accurancyMode);
0365: }
0366: return null;
0367: }
0368: return null;
0369: }
0370:
0371: BHLeafInterface selectAny(Bounds bound, int accurancyMode,
0372: NodeRetained armingNode) {
0373: if (bound == null) {
0374: return null;
0375: }
0376: BHNode bhNode = doSelectAny(bound, root, accurancyMode,
0377: armingNode);
0378: if (bhNode == null) {
0379: return null;
0380: }
0381: return ((BHLeafNode) bhNode).leafIF;
0382: }
0383:
0384: private BHNode doSelectAny(Bounds bound, BHNode bh,
0385: int accurancyMode, NodeRetained armingNode) {
0386: if ((bh == null) || (bh.bHull.isEmpty())) {
0387: return null;
0388: }
0389:
0390: switch (bh.nodeType) {
0391: case BHNode.BH_TYPE_LEAF:
0392: BHLeafInterface leaf = ((BHLeafNode) bh).leafIF;
0393: if (leaf instanceof GeometryAtom) {
0394: GeometryAtom leafAtom = (GeometryAtom) leaf;
0395: if ((((BHLeafNode) bh).isEnable())
0396: && (leafAtom.source.isCollidable)
0397: && (bound
0398: .intersect(leafAtom.source.collisionVwcBound))
0399: && ((accurancyMode == WakeupOnCollisionEntry.USE_BOUNDS) || ((leafAtom.source.geometryList != null) && (leafAtom.source
0400: .intersectGeometryList(leafAtom.source
0401: .getCurrentLocalToVworld(0),
0402: bound))))) {
0403: return bh;
0404: }
0405: } else if (leaf instanceof GroupRetained) {
0406: if ((leaf != armingNode)
0407: && ((BHLeafNode) bh).isEnable()
0408: && ((GroupRetained) leaf).sourceNode.collidable
0409: && bound.intersect(bh.bHull)) {
0410: return bh;
0411: }
0412: }
0413: return null;
0414: case BHNode.BH_TYPE_INTERNAL:
0415: if (bound.intersect(bh.bHull)) {
0416: BHNode hitNode = doSelectAny(bound,
0417: ((BHInternalNode) bh).getRightChild(),
0418: accurancyMode, armingNode);
0419: if (hitNode != null)
0420: return hitNode;
0421:
0422: return doSelectAny(bound, ((BHInternalNode) bh)
0423: .getLeftChild(), accurancyMode, armingNode);
0424: }
0425: return null;
0426: }
0427: return null;
0428: }
0429:
0430: BHLeafInterface selectAny(Bounds bound, int accurancyMode,
0431: GroupRetained armingGroup) {
0432: if (bound == null) {
0433: return null;
0434: }
0435: BHNode bhNode = doSelectAny(bound, root, accurancyMode,
0436: armingGroup);
0437: if (bhNode == null) {
0438: return null;
0439: }
0440: return ((BHLeafNode) bhNode).leafIF;
0441: }
0442:
0443: private BHNode doSelectAny(Bounds bound, BHNode bh,
0444: int accurancyMode, GroupRetained armingGroup) {
0445: if ((bh == null) || (bh.bHull.isEmpty())) {
0446: return null;
0447: }
0448: switch (bh.nodeType) {
0449: case BHNode.BH_TYPE_LEAF:
0450: BHLeafInterface leaf = ((BHLeafNode) bh).leafIF;
0451:
0452: if (leaf instanceof GeometryAtom) {
0453: GeometryAtom leafAtom = (GeometryAtom) leaf;
0454: if ((((BHLeafNode) bh).isEnable())
0455: && (leafAtom.source.isCollidable)
0456: && (bound
0457: .intersect(leafAtom.source.collisionVwcBound))
0458: && (!isDescendent(leafAtom.source.sourceNode,
0459: armingGroup, leafAtom.source.key))
0460: && ((accurancyMode == WakeupOnCollisionEntry.USE_BOUNDS) || ((leafAtom.source.geometryList != null) && (leafAtom.source
0461: .intersectGeometryList(leafAtom.source
0462: .getCurrentLocalToVworld(0),
0463: bound))))) {
0464: return bh;
0465: }
0466: } else if (leaf instanceof GroupRetained) {
0467: GroupRetained group = (GroupRetained) leaf;
0468: if (((BHLeafNode) bh).isEnable()
0469: && group.sourceNode.collidable
0470: && bound.intersect(bh.bHull)
0471: && !isDescendent(group.sourceNode, armingGroup,
0472: group.key)) {
0473: return bh;
0474: }
0475: }
0476: return null;
0477: case BHNode.BH_TYPE_INTERNAL:
0478: if (bound.intersect(bh.bHull)) {
0479: BHNode hitNode = doSelectAny(bound,
0480: ((BHInternalNode) bh).getRightChild(),
0481: accurancyMode, armingGroup);
0482: if (hitNode != null)
0483: return hitNode;
0484:
0485: return doSelectAny(bound, ((BHInternalNode) bh)
0486: .getLeftChild(), accurancyMode, armingGroup);
0487: }
0488: return null;
0489: }
0490: return null;
0491: }
0492:
0493: // Return true if node is a descendent of group
0494: private boolean isDescendent(NodeRetained node,
0495: GroupRetained group, HashKey key) {
0496:
0497: synchronized (group.universe.sceneGraphLock) {
0498: if (node.inSharedGroup) {
0499: // getlastNodeId() will destroy this key
0500: if (key != null) {
0501: key = new HashKey(key);
0502: }
0503: }
0504:
0505: do {
0506: if (node == group) {
0507: return true;
0508: }
0509: if (node instanceof SharedGroupRetained) {
0510: // retrieve the last node ID
0511: String nodeId = key.getLastNodeId();
0512: NodeRetained prevNode = node;
0513: Vector parents = ((SharedGroupRetained) node).parents;
0514: for (int i = parents.size() - 1; i >= 0; i--) {
0515: NodeRetained link = (NodeRetained) parents
0516: .elementAt(i);
0517: if (link.nodeId.equals(nodeId)) {
0518: node = link;
0519: break;
0520: }
0521: }
0522: if (prevNode == node) {
0523: // branch is already detach
0524: return true;
0525: }
0526: }
0527: node = node.parent;
0528: } while (node != null); // reach Locale
0529: }
0530: return false;
0531: }
0532:
0533: void select(PickShape pickShape, UnorderList hitArrList) {
0534:
0535: if ((pickShape == null) || (root == null))
0536: return;
0537:
0538: doSelect(pickShape, hitArrList, root, tPoint4d);
0539:
0540: }
0541:
0542: private void doSelect(PickShape pickShape, UnorderList hitArrList,
0543: BHNode bh, Point4d pickPos) {
0544:
0545: if ((bh == null) || (bh.bHull.isEmpty())) {
0546: return;
0547: }
0548:
0549: switch (bh.nodeType) {
0550: case BHNode.BH_TYPE_LEAF:
0551: if (((BHLeafNode) (bh)).isEnable()
0552: && (((BHLeafNode) bh).leafIF instanceof GeometryAtom)
0553: && ((GeometryAtom) (((BHLeafNode) bh).leafIF)).source.isPickable
0554: && pickShape.intersect(bh.bHull, pickPos)) {
0555: hitArrList.add(bh);
0556: }
0557: break;
0558: case BHNode.BH_TYPE_INTERNAL:
0559: if (pickShape.intersect(bh.bHull, pickPos)) {
0560: doSelect(pickShape, hitArrList, ((BHInternalNode) bh)
0561: .getRightChild(), pickPos);
0562: doSelect(pickShape, hitArrList, ((BHInternalNode) bh)
0563: .getLeftChild(), pickPos);
0564: }
0565: break;
0566: }
0567: }
0568:
0569: BHNode selectAny(PickShape pickShape) {
0570:
0571: if ((pickShape == null) || (root == null))
0572: return null;
0573:
0574: return doSelectAny(pickShape, root, tPoint4d);
0575:
0576: }
0577:
0578: private BHNode doSelectAny(PickShape pickShape, BHNode bh,
0579: Point4d pickPos) {
0580:
0581: BHNode hitNode = null;
0582:
0583: if ((bh == null) || (bh.bHull.isEmpty()))
0584: return null;
0585:
0586: switch (bh.nodeType) {
0587: case BHNode.BH_TYPE_LEAF:
0588: if (((BHLeafNode) (bh)).isEnable()
0589: && (((BHLeafNode) bh).leafIF instanceof GeometryAtom)
0590: && ((GeometryAtom) (((BHLeafNode) bh).leafIF)).source.isPickable
0591: && pickShape.intersect(bh.bHull, pickPos)) {
0592: return bh;
0593: }
0594: break;
0595: case BHNode.BH_TYPE_INTERNAL:
0596: if (pickShape.intersect(bh.bHull, pickPos)) {
0597: hitNode = doSelectAny(pickShape, ((BHInternalNode) bh)
0598: .getRightChild(), pickPos);
0599:
0600: if (hitNode != null) {
0601: return hitNode;
0602: }
0603:
0604: return doSelectAny(pickShape, ((BHInternalNode) bh)
0605: .getLeftChild(), pickPos);
0606: }
0607: break;
0608: }
0609: return null;
0610: }
0611:
0612: private void create(BHNode bhArr[]) {
0613: int i;
0614:
0615: if (bhArr == null) {
0616: root = null;
0617: return;
0618: }
0619:
0620: if (bhArr.length == 1) {
0621: bhArr[0].computeBoundingHull();
0622: root = (BHNode) bhArr[0];
0623: return;
0624: }
0625:
0626: int centerValuesIndex[] = new int[bhArr.length];
0627: float centerValues[][] = computeCenterValues(bhArr,
0628: centerValuesIndex);
0629:
0630: /*
0631: System.err.println("Length of array is " + bhArr.length);
0632: for(int kk=0; kk<bhArr.length;kk++) {
0633: System.err.println("( " + centerValues[kk][0] + ", " +
0634: centerValues[kk][1] + ", " + centerValues[kk][2] + " )");
0635: }
0636: */
0637:
0638: root = new BHInternalNode();
0639: constructTree((BHInternalNode) root, bhArr, centerValues,
0640: centerValuesIndex);
0641:
0642: if (J3dDebug.devPhase && J3dDebug.debug)
0643: gatherTreeStatistics();
0644:
0645: }
0646:
0647: void insert(BHNode bhArr[], int size) {
0648: // first pass: add all elements to the tree creating k array internal
0649: // nodes using the auxiliaryInsertStucture
0650: // second pass: go through all elements of the auxiliaryInsertStructure
0651: // and then update these nodes reclustering the trees with the new
0652: // k element siblings ...
0653:
0654: if (J3dDebug.devPhase && J3dDebug.debug)
0655: J3dDebug.doDebug(J3dDebug.bHTree, J3dDebug.LEVEL_4,
0656: "BHTree.java : Insert - bhArr.length is "
0657: + bhArr.length + "\n");
0658:
0659: if ((bhArr == null) || (size < 1) || (bhArr.length < 1))
0660: return;
0661:
0662: if (root == null) {
0663: if (J3dDebug.devPhase)
0664: J3dDebug.doDebug(J3dDebug.bHTree, J3dDebug.LEVEL_4,
0665: "BHTree.java : Tree has not be created yet.\n");
0666:
0667: // This extra "new" is needed, because create() require its input
0668: // array's length be equal to the number of inserted nodes.
0669: BHNode[] newbhArr = new BHNode[size];
0670: System.arraycopy(bhArr, 0, newbhArr, 0, size);
0671: create(newbhArr);
0672: return;
0673: }
0674:
0675: if (root.nodeType == BHNode.BH_TYPE_LEAF) {
0676: BHNode[] oldBhArr = bhArr;
0677: bhArr = new BHNode[size + 1];
0678: System.arraycopy(oldBhArr, 0, bhArr, 0, size);
0679: bhArr[size] = root;
0680: create(bhArr);
0681: return;
0682: }
0683:
0684: if (insertStructure == null) {
0685: insertStructure = new BHInsertStructure(size);
0686: } else {
0687: insertStructure.clear();
0688: }
0689:
0690: for (int i = 0; i < size; i++) {
0691: // test if its inside the 'root' element
0692: if (root.isInside(bhArr[i].bHull)) {
0693: ((BHInternalNode) root).insert(bhArr[i],
0694: insertStructure);
0695: } else {
0696: // extend the bounds of root by joining with current element
0697: root.bHull.combine(bhArr[i].bHull);
0698: insertStructure.lookupAndInsert(root, bhArr[i]);
0699: }
0700: }
0701:
0702: insertStructure.updateBoundingTree(this );
0703: // System.err.println("BHTree - Inserting ...");
0704:
0705: // Issue 353: clear temporary insertStructure so we don't leak.
0706: insertStructure.clear();
0707:
0708: // Guard against size<1 is done at the start of this method.
0709: estMaxDepth += (int) (Math.log(size) / LOG_OF_2) + 1;
0710:
0711: if (estMaxDepth > depthUpperBound) {
0712: int maxDepth = root.computeMaxDepth(0);
0713: int leafCount = root.countNumberOfLeaves();
0714: double compDepth = Math.log(leafCount) / LOG_OF_2;
0715: /*
0716: System.err.println("BHTree - evaluate for reConstructTree ...");
0717: System.err.println("compDepth " + compDepth);
0718: System.err.println("maxDepth " + maxDepth);
0719: System.err.println("leafCount " + leafCount);
0720: */
0721:
0722: // Upper bound guard.
0723: if (maxDepth > depthUpperBound) {
0724: reConstructTree(leafCount);
0725: maxDepth = root.computeMaxDepth(0);
0726: /*
0727: System.err.println("BHTree - Did reConstructTree ...");
0728: System.err.println("compDepth " + compDepth);
0729: System.err.println("maxDepth " + maxDepth);
0730: */
0731: }
0732:
0733: // Adjust depthUpperBound according to app. need.
0734: // If we encounter lots of overlapping bounds, the re-balanced
0735: // tree may not be an ideal balance tree. So there might be a
0736: // likehood of maxDepth exceeding the preset depthUpperBound.
0737: if (maxDepth > depthUpperBound) {
0738: depthUpperBound = depthUpperBound + INCR_DEPTH_BOUND;
0739: } else if ((depthUpperBound != DEPTH_UPPER_BOUND)
0740: && (maxDepth * 1.5 < depthUpperBound)) {
0741: depthUpperBound = depthUpperBound - INCR_DEPTH_BOUND;
0742:
0743: if (depthUpperBound < DEPTH_UPPER_BOUND) {
0744: // Be sure that DEPTH_UPPER_BOUND is the min.
0745: depthUpperBound = DEPTH_UPPER_BOUND;
0746: }
0747: }
0748:
0749: // This is the only place for resetting estMaxDepth to the tree real
0750: // maxDepth. Hence in cases where tree may get deteriorate fast, such
0751: // as multiple inserts and deletes frequently. estMaxDepth is accuminated,
0752: // and will lead to tree re-evaluation and possibly re-balancing.
0753: estMaxDepth = maxDepth;
0754: }
0755:
0756: }
0757:
0758: // mark all elements of the node and its parent as needing updating
0759: private void markParentChain(BHNode[] nArr, int size) {
0760: BHNode node;
0761:
0762: for (int i = 0; i < size; i++) {
0763: node = nArr[i];
0764: node.mark = true;
0765: while ((node.parent != null) && (node.parent.mark == false)) {
0766: node = node.parent;
0767: node.mark = true;
0768: }
0769: }
0770: }
0771:
0772: // mark all elements of the node and its parent as needing updating
0773: private void markParentChain(BHNode node) {
0774: node.mark = true;
0775: while ((node.parent != null) && (node.parent.mark == false)) {
0776: node = node.parent;
0777: node.mark = true;
0778: }
0779: }
0780:
0781: // Delete a series of n node elements from the input binary tree.
0782: // These elements are removed from the tree in a 2 phase process.
0783: // First, all elements to be removed are marked and all parent
0784: // chains are marked ... then a second phase of the algorithm goes
0785: // through and deletes them and updates all of the bounds ...
0786:
0787: // delete the n elements in the array from the tree
0788: void delete(BHNode bhArr[], int size) {
0789: BHNode node;
0790:
0791: /*
0792: if((bhArr == null) || (bhArr.length < 1))
0793: return;
0794: System.err.println("BHTree.java : delete - bhArr.length is " +
0795: bhArr.length);
0796: for(int i=0; i<bhArr.length; i++)
0797: System.err.println("bhArr[" + i +"] " + bhArr[i]);
0798:
0799: */
0800:
0801: for (int i = 0; i < size; i++) {
0802: if ((bhArr[i] != null)
0803: && (bhArr[i].nodeType == BHNode.BH_TYPE_LEAF)) {
0804: markParentChain(bhArr[i]);
0805: } else {
0806: if (J3dDebug.devPhase)
0807: J3dDebug
0808: .doDebug(
0809: J3dDebug.bHTree,
0810: J3dDebug.LEVEL_1,
0811: "Warning, element "
0812: + i
0813: + " is null/not leaf node.\n"
0814: + "Error in deletion routine, element "
0815: + bhArr[i]
0816: + "\n"
0817: + "In tree = "
0818: + this
0819: + " can not delete it ...\n");
0820: }
0821:
0822: }
0823:
0824: root = root.deleteAndUpdateMarkedNodes();
0825:
0826: if (J3dDebug.devPhase)
0827: if (root == null) {
0828: J3dDebug.doDebug(J3dDebug.bHTree, J3dDebug.LEVEL_4,
0829: "Tree has been completely deleted ...\n");
0830: }
0831: }
0832:
0833: // compute the center values along each of the three dimensions given
0834: // the array of leaf objects to be split and joined
0835: float[][] computeCenterValues(BHNode[] bhArr, int[] cIndex) {
0836: float centers[][] = new float[bhArr.length][3];
0837:
0838: // compute the center values of the input array of nodes
0839: for (int i = 0; i < bhArr.length; i++) {
0840: cIndex[i] = i;
0841:
0842: bhArr[i].computeBoundingHull();
0843:
0844: centers[i][0] = (float) ((bhArr[i].bHull.upper.x + bhArr[i].bHull.lower.x)) / 2.0f;
0845: centers[i][1] = (float) ((bhArr[i].bHull.upper.y + bhArr[i].bHull.lower.y)) / 2.0f;
0846: centers[i][2] = (float) ((bhArr[i].bHull.upper.z + bhArr[i].bHull.lower.z)) / 2.0f;
0847:
0848: }
0849: return centers;
0850: }
0851:
0852: void computeMeansAndSumSquares(float[][] centerValues,
0853: int[] centerValuesIndex, float[] means, float[] ss) {
0854:
0855: int i, arrLen;
0856: float sumCenters[] = new float[3];
0857: float temp = 0.0f;
0858:
0859: arrLen = centerValuesIndex.length;
0860: // Initialization.
0861: for (i = 2; i >= 0; i--) {
0862: sumCenters[i] = 0.0f;
0863: ss[i] = 0.0f;
0864: }
0865:
0866: for (i = arrLen - 1; i >= 0; i--) {
0867: sumCenters[0] += centerValues[centerValuesIndex[i]][0];
0868: sumCenters[1] += centerValues[centerValuesIndex[i]][1];
0869: sumCenters[2] += centerValues[centerValuesIndex[i]][2];
0870: }
0871:
0872: means[0] = sumCenters[0] / (float) arrLen;
0873: means[1] = sumCenters[1] / (float) arrLen;
0874: means[2] = sumCenters[2] / (float) arrLen;
0875:
0876: for (i = arrLen - 1; i >= 0; i--) {
0877: temp = (centerValues[centerValuesIndex[i]][0] - means[0]);
0878: ss[0] += (temp * temp);
0879: temp = (centerValues[centerValuesIndex[i]][1] - means[1]);
0880: ss[1] += (temp * temp);
0881: temp = (centerValues[centerValuesIndex[i]][2] - means[2]);
0882: ss[2] += (temp * temp);
0883:
0884: }
0885:
0886: }
0887:
0888: // find the split axis (the highest ss and return its index) for
0889: // a given set of ss values
0890: int findSplitAxis(float ss[]) {
0891: int splitAxis = -1;
0892: float maxSS = 0.0f;
0893:
0894: // the largest ss index value
0895: for (int i = 0; i < 3; i++) {
0896: if (ss[i] > maxSS) {
0897: maxSS = ss[i];
0898: splitAxis = i;
0899: }
0900: }
0901: return splitAxis;
0902: }
0903:
0904: // Recursive method for constructing a binary tree.
0905: void constructTree(BHInternalNode parent, BHNode bhArr[],
0906: float[][] centerValues, int[] centerValuesIndex) {
0907:
0908: int i, splitAxis;
0909: int rightSetCount = 0;
0910: int leftSetCount = 0;
0911: float means[] = new float[3];
0912: float ss[] = new float[3];
0913:
0914: if (J3dDebug.devPhase)
0915: if (bhArr.length <= 1) {
0916: // this is only here for debugging can be removed after testing
0917: // to ensure that it never gets called
0918: J3dDebug.doDebug(J3dDebug.bHTree, J3dDebug.LEVEL_1,
0919: "constructTree - bhArr.length <= 1. Bad !!!\n");
0920: }
0921:
0922: computeMeansAndSumSquares(centerValues, centerValuesIndex,
0923: means, ss);
0924:
0925: splitAxis = findSplitAxis(ss);
0926:
0927: // an array of decision variables for storing the values of inside
0928: // the right or left set for a particular element of bhArr.
0929: // true if its in the left set, false if its in the right set
0930: boolean leftOrRightSet[] = new boolean[bhArr.length];
0931:
0932: if (splitAxis == -1) {
0933: // This is bad. Since we can't find a split axis, the best thing
0934: // to do is to split the set in two sets; each with about the
0935: // same number of elements. By doing this we can avoid constructing
0936: // a skew tree.
0937:
0938: // split elements into half.
0939: for (i = 0; i < bhArr.length; i++) {
0940: if (leftSetCount > rightSetCount) {
0941: rightSetCount++;
0942: leftOrRightSet[i] = false;
0943: } else {
0944: leftSetCount++;
0945: leftOrRightSet[i] = true;
0946: }
0947: }
0948: } else {
0949: for (i = 0; i < bhArr.length; i++) {
0950: // the split criterion, special multiple equals cases added
0951: if (centerValues[centerValuesIndex[i]][splitAxis] < means[splitAxis]) {
0952:
0953: if (J3dDebug.devPhase)
0954: J3dDebug.doDebug(J3dDebug.bHTree,
0955: J3dDebug.LEVEL_4,
0956: "Found a left element\n");
0957: leftSetCount++;
0958: leftOrRightSet[i] = true;
0959: } else if (centerValues[centerValuesIndex[i]][splitAxis] > means[splitAxis]) {
0960: if (J3dDebug.devPhase)
0961: J3dDebug.doDebug(J3dDebug.bHTree,
0962: J3dDebug.LEVEL_4,
0963: "Found a right element\n");
0964: rightSetCount++;
0965: leftOrRightSet[i] = false;
0966: } else {
0967: if (J3dDebug.devPhase)
0968: J3dDebug.doDebug(J3dDebug.bHTree,
0969: J3dDebug.LEVEL_4,
0970: "Found an equal element\n");
0971: if (leftSetCount > rightSetCount) {
0972: rightSetCount++;
0973: leftOrRightSet[i] = false;
0974: } else {
0975: leftSetCount++;
0976: leftOrRightSet[i] = true;
0977: }
0978: }
0979: }
0980: }
0981:
0982: if (J3dDebug.devPhase)
0983: J3dDebug.doDebug(J3dDebug.bHTree, J3dDebug.LEVEL_2,
0984: "LeftSetCount " + leftSetCount + " RightSetCount "
0985: + rightSetCount + "\n");
0986:
0987: // Don't think that this guard is needed, but still like to have it.
0988: // Just in case, bad means and the sum of squares might lead us into the guard.
0989: if (leftSetCount == bhArr.length) {
0990: if (J3dDebug.devPhase)
0991: J3dDebug.doDebug(J3dDebug.bHTree, J3dDebug.LEVEL_1,
0992: "Split Axis of = " + splitAxis
0993: + " didn't yield "
0994: + "any split among the objects ?\n");
0995: // split elements into half
0996: rightSetCount = 0;
0997: leftSetCount = 0;
0998: for (i = 0; i < bhArr.length; i++) {
0999: if (leftSetCount > rightSetCount) {
1000: rightSetCount++;
1001: leftOrRightSet[i] = false;
1002: } else {
1003: leftSetCount++;
1004: leftOrRightSet[i] = true;
1005: }
1006: }
1007: } else if (rightSetCount == bhArr.length) {
1008: if (J3dDebug.devPhase)
1009: J3dDebug.doDebug(J3dDebug.bHTree, J3dDebug.LEVEL_1,
1010: "Split Axis of = " + splitAxis
1011: + " didn't yield "
1012: + "any split among the objects ?\n");
1013: // split elements into half
1014: rightSetCount = 0;
1015: leftSetCount = 0;
1016: for (i = 0; i < bhArr.length; i++) {
1017: if (leftSetCount > rightSetCount) {
1018: rightSetCount++;
1019: leftOrRightSet[i] = false;
1020: } else {
1021: leftSetCount++;
1022: leftOrRightSet[i] = true;
1023: }
1024: }
1025: }
1026:
1027: if (J3dDebug.devPhase)
1028: if (J3dDebug.doDebug(J3dDebug.bHTree, J3dDebug.LEVEL_4))
1029: // check to make sure that rightSet and leftSet sum to the
1030: // number of elements in the original array.
1031: if (bhArr.length != (rightSetCount + leftSetCount)) {
1032: System.err
1033: .println("An error has occurred in spliting");
1034: }
1035:
1036: BHNode rightSet[] = new BHNode[rightSetCount];
1037: BHNode leftSet[] = new BHNode[leftSetCount];
1038: int centerValuesIndexR[] = new int[rightSetCount];
1039: int centerValuesIndexL[] = new int[leftSetCount];
1040:
1041: rightSetCount = 0;
1042: leftSetCount = 0;
1043:
1044: for (i = 0; i < bhArr.length; i++) {
1045: if (leftOrRightSet[i]) { // element in left set
1046: leftSet[leftSetCount] = bhArr[i];
1047: centerValuesIndexL[leftSetCount] = centerValuesIndex[i];
1048: leftSetCount++;
1049: } else {
1050: rightSet[rightSetCount] = bhArr[i];
1051: centerValuesIndexR[rightSetCount] = centerValuesIndex[i];
1052: rightSetCount++;
1053: }
1054: }
1055:
1056: if (rightSet.length != 1) {
1057: parent.rChild = new BHInternalNode();
1058: parent.rChild.setParent(parent);
1059: constructTree((BHInternalNode) (parent.rChild), rightSet,
1060: centerValues, centerValuesIndexR);
1061: } else {
1062: parent.rChild = rightSet[0];
1063: parent.rChild.setParent(parent);
1064: }
1065:
1066: if (leftSet.length != 1) {
1067: parent.lChild = new BHInternalNode();
1068: parent.lChild.setParent(parent);
1069: constructTree((BHInternalNode) (parent.lChild), leftSet,
1070: centerValues, centerValuesIndexL);
1071: } else {
1072: parent.lChild = leftSet[0];
1073: parent.lChild.setParent(parent);
1074: }
1075:
1076: parent.combineBHull(parent.rChild, parent.lChild);
1077: }
1078:
1079: void reConstructTree(int numOfLeaf) {
1080: if (root == null)
1081: return;
1082:
1083: BHNode bhArr[] = new BHNode[numOfLeaf];
1084: int index[] = new int[1];
1085: index[0] = 0;
1086: root.destroyTree(bhArr, index);
1087:
1088: /*
1089: if(bhArr.length != index[0])
1090: System.err.println("BHTree - This isn't right!!! - bhArr.length " +
1091: bhArr.length + " index " + index[0]);
1092: */
1093:
1094: create(bhArr);
1095:
1096: }
1097:
1098: void gatherTreeStatistics() {
1099:
1100: int leafCount = root.countNumberOfLeaves();
1101: int internalCount = root.countNumberOfInternals();
1102: int maxDepth = root.computeMaxDepth(0);
1103: float averageDepth = root.computeAverageLeafDepth(leafCount, 0);
1104:
1105: System.err.println("Statistics for tree = " + this );
1106: System.err.println("Total Number of nodes in tree = "
1107: + (leafCount + internalCount));
1108: System.err.println("Number of Leaf Nodes = " + leafCount);
1109: System.err.println("Number of Internal Nodes = "
1110: + internalCount);
1111: System.err.println("Maximum Leaf depth = " + maxDepth);
1112: System.err.println("Average Leaf depth = " + averageDepth);
1113: System.err.println("root.bHull = " + root.bHull);
1114: // printTree(root);
1115:
1116: }
1117:
1118: void printTree(BHNode bh) {
1119: if (bh != null) {
1120: if (bh.nodeType == BHNode.BH_TYPE_INTERNAL) {
1121: System.err.println("BH_TYPE_INTERNAL - bHull : " + bh);
1122: System.err.println(bh.bHull);
1123: System.err.println("rChild : "
1124: + ((BHInternalNode) bh).rChild + " lChild : "
1125: + ((BHInternalNode) bh).lChild);
1126: printTree(((BHInternalNode) bh).rChild);
1127: printTree(((BHInternalNode) bh).lChild);
1128: } else if (bh.nodeType == BHNode.BH_TYPE_LEAF) {
1129: System.err.println("BH_TYPE_LEAF - bHull : " + bh);
1130: System.err.println(bh.bHull);
1131: }
1132:
1133: }
1134:
1135: }
1136: }
|