001: /*
002: * $RCSfile: BHInternalNode.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: class BHInternalNode extends BHNode {
037:
038: static boolean debug2 = true;
039:
040: BHNode rChild;
041: BHNode lChild;
042:
043: BHInternalNode() {
044: super ();
045: nodeType = BH_TYPE_INTERNAL;
046: this .rChild = null;
047: this .lChild = null;
048: }
049:
050: BHInternalNode(BHNode parent) {
051: super (parent);
052: nodeType = BH_TYPE_INTERNAL;
053: this .rChild = null;
054: this .lChild = null;
055: }
056:
057: BHInternalNode(BHNode parent, BHNode rChild, BHNode lChild) {
058: super (parent);
059: nodeType = BH_TYPE_INTERNAL;
060: this .rChild = rChild;
061: this .lChild = lChild;
062: }
063:
064: BHInternalNode(BHNode parent, BoundingBox bHull) {
065: super (parent, bHull);
066: nodeType = BH_TYPE_INTERNAL;
067: this .rChild = null;
068: this .lChild = null;
069: }
070:
071: BHInternalNode(BHNode parent, BHNode rChild, BHNode lChild,
072: BoundingBox bHull) {
073: super (parent, bHull);
074: nodeType = BH_TYPE_INTERNAL;
075: this .rChild = rChild;
076: this .lChild = lChild;
077: }
078:
079: BHNode getLeftChild() {
080: return (BHNode) lChild;
081: }
082:
083: BHNode getRightChild() {
084: return (BHNode) rChild;
085: }
086:
087: void setLeftChild(BHNode child) {
088: lChild = child;
089: }
090:
091: void setRightChild(BHNode child) {
092: rChild = child;
093: }
094:
095: void computeBoundingHull(BoundingBox bHull) {
096: computeBoundingHull();
097: bHull.set(this .bHull);
098: }
099:
100: void computeBoundingHull() {
101: BoundingBox rChildBound = null;
102: BoundingBox lChildBound = null;
103: int i;
104:
105: if ((lChild == null) && (rChild == null)) {
106: bHull = null;
107: return;
108: }
109:
110: if (lChild != null)
111: lChildBound = lChild.getBoundingHull();
112:
113: if (rChild != null)
114: rChildBound = rChild.getBoundingHull();
115:
116: if (bHull == null)
117: bHull = new BoundingBox();
118:
119: // Since left child is null. bHull is equal to right child's Hull.
120: if (lChild == null) {
121: bHull.set(rChildBound);
122: return;
123: }
124:
125: // Since right child is null. bHull is equal to left child's Hull.
126: if (rChild == null) {
127: bHull.set(lChildBound);
128: return;
129: }
130:
131: // Compute the combined bounds of the children.
132: bHull.set(rChildBound);
133: bHull.combine(lChildBound);
134:
135: }
136:
137: void updateMarkedBoundingHull() {
138:
139: if (mark == false)
140: return;
141:
142: rChild.updateMarkedBoundingHull();
143: lChild.updateMarkedBoundingHull();
144: computeBoundingHull();
145: mark = false;
146:
147: }
148:
149: // this method inserts a single element into the tree given the stipulation
150: // that the current tree node already contains the child ... 3 cases
151: // one --node is inside the left child, and not inside the right
152: // so recurse placing it inside the left child
153: // two -- node is not inside the left but is inside the right
154: // recurse placing it inside the right child
155: // three -- node is not inside either one, added it to the current
156: // element
157:
158: void insert(BHNode node, BHInsertStructure insertStructure) {
159: // NOTE: the node must already be inside this node if its not then fail.
160: if (debug2)
161: if (!this .isInside(node.bHull)) {
162: System.err
163: .println("Incorrect use of insertion, current node");
164: System.err
165: .println("must contain the input element ...");
166: }
167:
168: boolean insideRightChild = false;
169: boolean insideLeftChild = false;
170:
171: // leaf children are considered inpenetrable for insert so returns false
172: if (this .rChild.nodeType == BHNode.BH_TYPE_LEAF) {
173: insideRightChild = false;
174: } else {
175: insideRightChild = this .rChild.isInside(node.bHull);
176: }
177: if (this .lChild.nodeType == BHNode.BH_TYPE_LEAF) {
178: insideLeftChild = false;
179: } else {
180: insideLeftChild = this .lChild.isInside(node.bHull);
181: }
182:
183: if (insideLeftChild && !insideRightChild) {
184: ((BHInternalNode) this .lChild)
185: .insert(node, insertStructure);
186: } else if (!insideLeftChild && insideRightChild) {
187: ((BHInternalNode) this .rChild)
188: .insert(node, insertStructure);
189: } else if (insideLeftChild && insideRightChild) {
190: // choose randomly to put it in the left or right
191: if (insertStructure.randomNumber.nextBoolean()) {
192: ((BHInternalNode) this .lChild).insert(node,
193: insertStructure);
194: } else {
195: ((BHInternalNode) this .rChild).insert(node,
196: insertStructure);
197: }
198: } else {
199: // doesn't fit in either one ....
200: // lookup the current node this in the auxilaryInsertStructure
201: // if it appears then add element to the array of sub elements
202: // if not then allocate a new element to the array
203: insertStructure.lookupAndInsert(this , node);
204: }
205: }
206:
207: void destroyTree(BHNode[] bhArr, int[] index) {
208:
209: if (rChild != null)
210: rChild.destroyTree(bhArr, index);
211:
212: if (lChild != null)
213: lChild.destroyTree(bhArr, index);
214:
215: rChild = null;
216: lChild = null;
217: }
218: }
|