aboutsummaryrefslogtreecommitdiffstats
path: root/src/javax/media/j3d/BHNode.java
diff options
context:
space:
mode:
Diffstat (limited to 'src/javax/media/j3d/BHNode.java')
-rw-r--r--src/javax/media/j3d/BHNode.java281
1 files changed, 281 insertions, 0 deletions
diff --git a/src/javax/media/j3d/BHNode.java b/src/javax/media/j3d/BHNode.java
new file mode 100644
index 0000000..23c4a93
--- /dev/null
+++ b/src/javax/media/j3d/BHNode.java
@@ -0,0 +1,281 @@
+/*
+ * 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;
+
+
+abstract class BHNode {
+
+ static final byte BH_TYPE_INTERNAL = 1;
+ static final byte BH_TYPE_LEAF = 2;
+
+ static final int NUMBER_OF_PLANES = 6;
+
+ static final boolean debug = false;
+ static final boolean debug2 = false;
+
+ BHNode parent;
+ byte nodeType;
+ BoundingBox bHull = null;
+ boolean mark;
+
+ BHNode () {
+ this.parent = null;
+ mark = false;
+ }
+
+ BHNode (BHNode parent) {
+ this.parent = parent;
+ mark = false;
+ }
+
+ BHNode (BHNode parent, BoundingBox bHull) {
+ this.parent = parent;
+ mark = false;
+
+ this.bHull = bHull;
+ }
+
+ BHNode getParent () {
+ return (this.parent) ;
+ }
+
+ abstract void computeBoundingHull();
+ abstract void updateMarkedBoundingHull();
+ abstract void destroyTree(BHNode[] bhArr, int[] index);
+
+ void setParent (BHNode node) {
+ this.parent = node;
+ }
+
+ BoundingBox getBoundingHull() {
+ return (this.bHull);
+ }
+
+ void setBoundingHull(BoundingBox bHull) {
+ this.bHull = bHull;
+ }
+
+ // given two nodes determine the bHull surrounding them, ie. the parent hull
+ void combineBHull(BHNode node1, BHNode node2 ) {
+ BoundingBox bHull1 = null;
+ BoundingBox bHull2 = null;
+
+ bHull1 = node1.getBoundingHull();
+ bHull2 = node2.getBoundingHull();
+
+ if(this.bHull==null)
+ this.bHull = new BoundingBox(bHull1);
+ else
+ this.bHull.set(bHull1);
+
+ this.bHull.combine(bHull2);
+
+ }
+
+ // returns true iff the bHull is completely inside this
+ // bounding hull i.e. bHull values are strictly less
+ // than or equal to all this.bHull values
+ boolean isInside(BoundingBox bHull) {
+ if(bHull == null)
+ return false;
+
+ if( this.bHull.isEmpty() || bHull.isEmpty() ) {
+ return false;
+ }
+
+ if( this.bHull.upper.x < bHull.upper.x ||
+ this.bHull.upper.y < bHull.upper.y ||
+ this.bHull.upper.z < bHull.upper.z ||
+ this.bHull.lower.x > bHull.lower.x ||
+ this.bHull.lower.y > bHull.lower.y ||
+ this.bHull.lower.z > bHull.lower.z )
+ return false;
+ else
+ return true;
+ }
+
+ // finds the node matching the search element in the tree and returns
+ // the node if found, else it returns null if the node couldn't be found
+ BHNode findNode(BHNode node) {
+ BHNode fNode = null;
+
+ if ( this.nodeType == BHNode.BH_TYPE_LEAF) {
+ if ( this == node ) {
+ return this;
+ }
+ }
+ else {
+ if (((BHInternalNode) this).rChild.isInside(node.bHull)) {
+ fNode = ((BHInternalNode)this).rChild.findNode(node);
+ if(fNode != null) {
+ return fNode;
+ }
+ }
+ if (((BHInternalNode)this).lChild.isInside(node.bHull)) {
+ return ((BHInternalNode)this).lChild.findNode(node);
+ }
+ }
+ return null;
+ }
+
+ void deleteFromParent() {
+ BHInternalNode parent;
+
+ // System.err.println("deleteFromParent - this " + this );
+ parent = (BHInternalNode) (this.parent);
+ if(parent != null) {
+ if(parent.rChild == this)
+ parent.rChild = null;
+ else if(parent.lChild == this)
+ parent.lChild = null;
+ else {
+ if(debug2) {
+ System.err.println("BHNode.java: Trouble! No match found. This can't happen.");
+ System.err.println("this " + this );
+ if ( this.nodeType == BHNode.BH_TYPE_INTERNAL) {
+ System.err.println("rChild " + ((BHInternalNode)this).rChild +
+ " lChild " + ((BHInternalNode)this).lChild);
+ }
+ System.err.println("parent " + parent +
+ " parent.rChild " + parent.rChild +
+ " parent.lChild " + parent.lChild);
+ }
+ }
+ }
+ }
+
+ // delete all leaf nodes marked with DELETE_UPDATE and update the
+ // bounds of the parents node
+ BHNode deleteAndUpdateMarkedNodes() {
+
+ if (this.mark == true) {
+ if (this.nodeType == BH_TYPE_LEAF) {
+ this.deleteFromParent();
+ return null;
+
+ } else {
+ if(debug)
+ if(((BHInternalNode)(this)).rChild == ((BHInternalNode)(this)).lChild)
+ System.err.println("rChild " + ((BHInternalNode)(this)).rChild +
+ " lChild " + ((BHInternalNode)(this)).lChild);
+
+
+ if(((BHInternalNode)(this)).rChild != null)
+ ((BHInternalNode)(this)).rChild =
+ ((BHInternalNode)(this)).rChild.deleteAndUpdateMarkedNodes();
+ if(((BHInternalNode)(this)).lChild != null)
+ ((BHInternalNode)(this)).lChild =
+ ((BHInternalNode)(this)).lChild.deleteAndUpdateMarkedNodes();
+
+ if ((((BHInternalNode)(this)).rChild == null) &&
+ (((BHInternalNode)(this)).lChild == null)) {
+ this.deleteFromParent();
+ return null;
+ } else {
+ if ( ((BHInternalNode)this).rChild == null ) {
+ BHNode leftChild = ((BHInternalNode)this).lChild;
+ leftChild.parent = this.parent;
+ // delete self, return lChild
+ this.deleteFromParent();
+ return leftChild;
+ } else if ( ((BHInternalNode)this).lChild == null ) {
+ BHNode rightChild = ((BHInternalNode)this).rChild;
+ rightChild.parent = this.parent;
+ // delete self, return rChild
+ this.deleteFromParent();
+ return rightChild;
+ } else {
+ // recompute your bounds and return yourself
+ this.combineBHull(((BHInternalNode)this).rChild,
+ ((BHInternalNode)this).lChild);
+ // update the parent's pointers
+ ((BHInternalNode)this).rChild.parent = this;
+ ((BHInternalNode)this).lChild.parent = this;
+ this.mark = false;
+ return this;
+ }
+ }
+ }
+ } else {
+ // mark is NOT set, simply return self
+ return this;
+ }
+ }
+
+
+ // generic tree gathering statistics operations
+
+ int countNumberOfInternals() {
+ if ( this.nodeType == BHNode.BH_TYPE_LEAF ) {
+ return 0;
+ } else {
+ return (((BHInternalNode)this).rChild.countNumberOfInternals() +
+ ((BHInternalNode)this).lChild.countNumberOfInternals() + 1 );
+ }
+ }
+
+ // recursively traverse the tree and compute the total number of leaves
+ int countNumberOfLeaves() {
+ if ( this.nodeType == BHNode.BH_TYPE_LEAF ) {
+ return 1;
+ } else {
+ return ( ((BHInternalNode)this).rChild.countNumberOfLeaves() +
+ ((BHInternalNode)this).lChild.countNumberOfLeaves() );
+ }
+ }
+
+
+ // traverse tree and compute the maximum depth to a leaf
+ int computeMaxDepth (int currentDepth) {
+ if ( this.nodeType == BHNode.BH_TYPE_LEAF ) {
+ return (currentDepth);
+ } else {
+ int rightDepth = ((BHInternalNode)this).rChild.computeMaxDepth(currentDepth + 1);
+ int leftDepth = ((BHInternalNode)this).lChild.computeMaxDepth(currentDepth + 1);
+ if( rightDepth > leftDepth )
+ return rightDepth;
+ return leftDepth;
+ }
+ }
+
+ // compute the average depth of the leaves ...
+ float computeAverageLeafDepth ( int numberOfLeaves, int currentDepth ) {
+ int sumOfDepths = this.computeSumOfDepths(0);
+ return ( (float)sumOfDepths / (float)numberOfLeaves );
+ }
+
+ int computeSumOfDepths ( int currentDepth ) {
+ if ( this.nodeType == BHNode.BH_TYPE_LEAF ) {
+ return ( currentDepth );
+ } else {
+ return (((BHInternalNode)this).rChild.computeSumOfDepths(currentDepth + 1) +
+ ((BHInternalNode)this).lChild.computeSumOfDepths(currentDepth + 1) ) ;
+ }
+ }
+
+
+}
generated by cgit v1.2.3 (git 2.39.1) at 2025-04-23 11:51:31 +0000