001: /*
002: * $RCSfile: BHNode.java,v $
003: *
004: * Copyright 1999-2008 Sun Microsystems, Inc. All Rights Reserved.
005: * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER.
006: *
007: * This code is free software; you can redistribute it and/or modify it
008: * under the terms of the GNU General Public License version 2 only, as
009: * published by the Free Software Foundation. Sun designates this
010: * particular file as subject to the "Classpath" exception as provided
011: * by Sun in the LICENSE file that accompanied this code.
012: *
013: * This code is distributed in the hope that it will be useful, but WITHOUT
014: * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
015: * FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
016: * version 2 for more details (a copy is included in the LICENSE file that
017: * accompanied this code).
018: *
019: * You should have received a copy of the GNU General Public License version
020: * 2 along with this work; if not, write to the Free Software Foundation,
021: * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA.
022: *
023: * Please contact Sun Microsystems, Inc., 4150 Network Circle, Santa Clara,
024: * CA 95054 USA or visit www.sun.com if you need additional information or
025: * have any questions.
026: *
027: * $Revision: 1.7 $
028: * $Date: 2008/02/28 20:17:19 $
029: * $State: Exp $
030: */
031:
032: package javax.media.j3d;
033:
034: import javax.vecmath.*;
035:
036: abstract class BHNode {
037:
038: static final byte BH_TYPE_INTERNAL = 1;
039: static final byte BH_TYPE_LEAF = 2;
040:
041: static final int NUMBER_OF_PLANES = 6;
042:
043: static final boolean debug = false;
044: static final boolean debug2 = false;
045:
046: BHNode parent;
047: byte nodeType;
048: BoundingBox bHull = null;
049: boolean mark;
050:
051: BHNode() {
052: this .parent = null;
053: mark = false;
054: }
055:
056: BHNode(BHNode parent) {
057: this .parent = parent;
058: mark = false;
059: }
060:
061: BHNode(BHNode parent, BoundingBox bHull) {
062: this .parent = parent;
063: mark = false;
064:
065: this .bHull = bHull;
066: }
067:
068: BHNode getParent() {
069: return (this .parent);
070: }
071:
072: abstract void computeBoundingHull();
073:
074: abstract void updateMarkedBoundingHull();
075:
076: abstract void destroyTree(BHNode[] bhArr, int[] index);
077:
078: void setParent(BHNode node) {
079: this .parent = node;
080: }
081:
082: BoundingBox getBoundingHull() {
083: return (this .bHull);
084: }
085:
086: void setBoundingHull(BoundingBox bHull) {
087: this .bHull = bHull;
088: }
089:
090: // given two nodes determine the bHull surrounding them, ie. the parent hull
091: void combineBHull(BHNode node1, BHNode node2) {
092: BoundingBox bHull1 = null;
093: BoundingBox bHull2 = null;
094:
095: bHull1 = node1.getBoundingHull();
096: bHull2 = node2.getBoundingHull();
097:
098: if (this .bHull == null)
099: this .bHull = new BoundingBox(bHull1);
100: else
101: this .bHull.set(bHull1);
102:
103: this .bHull.combine(bHull2);
104:
105: }
106:
107: // returns true iff the bHull is completely inside this
108: // bounding hull i.e. bHull values are strictly less
109: // than or equal to all this.bHull values
110: boolean isInside(BoundingBox bHull) {
111: if (bHull == null)
112: return false;
113:
114: if (this .bHull.isEmpty() || bHull.isEmpty()) {
115: return false;
116: }
117:
118: if (this .bHull.upper.x < bHull.upper.x
119: || this .bHull.upper.y < bHull.upper.y
120: || this .bHull.upper.z < bHull.upper.z
121: || this .bHull.lower.x > bHull.lower.x
122: || this .bHull.lower.y > bHull.lower.y
123: || this .bHull.lower.z > bHull.lower.z)
124: return false;
125: else
126: return true;
127: }
128:
129: // finds the node matching the search element in the tree and returns
130: // the node if found, else it returns null if the node couldn't be found
131: BHNode findNode(BHNode node) {
132: BHNode fNode = null;
133:
134: if (this .nodeType == BHNode.BH_TYPE_LEAF) {
135: if (this == node) {
136: return this ;
137: }
138: } else {
139: if (((BHInternalNode) this ).rChild.isInside(node.bHull)) {
140: fNode = ((BHInternalNode) this ).rChild.findNode(node);
141: if (fNode != null) {
142: return fNode;
143: }
144: }
145: if (((BHInternalNode) this ).lChild.isInside(node.bHull)) {
146: return ((BHInternalNode) this ).lChild.findNode(node);
147: }
148: }
149: return null;
150: }
151:
152: void deleteFromParent() {
153: BHInternalNode parent;
154:
155: // System.err.println("deleteFromParent - this " + this );
156: parent = (BHInternalNode) (this .parent);
157: if (parent != null) {
158: if (parent.rChild == this )
159: parent.rChild = null;
160: else if (parent.lChild == this )
161: parent.lChild = null;
162: else {
163: if (debug2) {
164: System.err
165: .println("BHNode.java: Trouble! No match found. This can't happen.");
166: System.err.println("this " + this );
167: if (this .nodeType == BHNode.BH_TYPE_INTERNAL) {
168: System.err.println("rChild "
169: + ((BHInternalNode) this ).rChild
170: + " lChild "
171: + ((BHInternalNode) this ).lChild);
172: }
173: System.err.println("parent " + parent
174: + " parent.rChild " + parent.rChild
175: + " parent.lChild " + parent.lChild);
176: }
177: }
178: }
179: }
180:
181: // delete all leaf nodes marked with DELETE_UPDATE and update the
182: // bounds of the parents node
183: BHNode deleteAndUpdateMarkedNodes() {
184:
185: if (this .mark == true) {
186: if (this .nodeType == BH_TYPE_LEAF) {
187: this .deleteFromParent();
188: return null;
189:
190: } else {
191: if (debug)
192: if (((BHInternalNode) (this )).rChild == ((BHInternalNode) (this )).lChild)
193: System.err.println("rChild "
194: + ((BHInternalNode) (this )).rChild
195: + " lChild "
196: + ((BHInternalNode) (this )).lChild);
197:
198: if (((BHInternalNode) (this )).rChild != null)
199: ((BHInternalNode) (this )).rChild = ((BHInternalNode) (this )).rChild
200: .deleteAndUpdateMarkedNodes();
201: if (((BHInternalNode) (this )).lChild != null)
202: ((BHInternalNode) (this )).lChild = ((BHInternalNode) (this )).lChild
203: .deleteAndUpdateMarkedNodes();
204:
205: if ((((BHInternalNode) (this )).rChild == null)
206: && (((BHInternalNode) (this )).lChild == null)) {
207: this .deleteFromParent();
208: return null;
209: } else {
210: if (((BHInternalNode) this ).rChild == null) {
211: BHNode leftChild = ((BHInternalNode) this ).lChild;
212: leftChild.parent = this .parent;
213: // delete self, return lChild
214: this .deleteFromParent();
215: return leftChild;
216: } else if (((BHInternalNode) this ).lChild == null) {
217: BHNode rightChild = ((BHInternalNode) this ).rChild;
218: rightChild.parent = this .parent;
219: // delete self, return rChild
220: this .deleteFromParent();
221: return rightChild;
222: } else {
223: // recompute your bounds and return yourself
224: this .combineBHull(
225: ((BHInternalNode) this ).rChild,
226: ((BHInternalNode) this ).lChild);
227: // update the parent's pointers
228: ((BHInternalNode) this ).rChild.parent = this ;
229: ((BHInternalNode) this ).lChild.parent = this ;
230: this .mark = false;
231: return this ;
232: }
233: }
234: }
235: } else {
236: // mark is NOT set, simply return self
237: return this ;
238: }
239: }
240:
241: // generic tree gathering statistics operations
242:
243: int countNumberOfInternals() {
244: if (this .nodeType == BHNode.BH_TYPE_LEAF) {
245: return 0;
246: } else {
247: return (((BHInternalNode) this ).rChild
248: .countNumberOfInternals()
249: + ((BHInternalNode) this ).lChild
250: .countNumberOfInternals() + 1);
251: }
252: }
253:
254: // recursively traverse the tree and compute the total number of leaves
255: int countNumberOfLeaves() {
256: if (this .nodeType == BHNode.BH_TYPE_LEAF) {
257: return 1;
258: } else {
259: return (((BHInternalNode) this ).rChild
260: .countNumberOfLeaves() + ((BHInternalNode) this ).lChild
261: .countNumberOfLeaves());
262: }
263: }
264:
265: // traverse tree and compute the maximum depth to a leaf
266: int computeMaxDepth(int currentDepth) {
267: if (this .nodeType == BHNode.BH_TYPE_LEAF) {
268: return (currentDepth);
269: } else {
270: int rightDepth = ((BHInternalNode) this ).rChild
271: .computeMaxDepth(currentDepth + 1);
272: int leftDepth = ((BHInternalNode) this ).lChild
273: .computeMaxDepth(currentDepth + 1);
274: if (rightDepth > leftDepth)
275: return rightDepth;
276: return leftDepth;
277: }
278: }
279:
280: // compute the average depth of the leaves ...
281: float computeAverageLeafDepth(int numberOfLeaves, int currentDepth) {
282: int sumOfDepths = this .computeSumOfDepths(0);
283: return ((float) sumOfDepths / (float) numberOfLeaves);
284: }
285:
286: int computeSumOfDepths(int currentDepth) {
287: if (this .nodeType == BHNode.BH_TYPE_LEAF) {
288: return (currentDepth);
289: } else {
290: return (((BHInternalNode) this ).rChild
291: .computeSumOfDepths(currentDepth + 1) + ((BHInternalNode) this ).lChild
292: .computeSumOfDepths(currentDepth + 1));
293: }
294: }
295:
296: }
|