001: /*
002: * $RCSfile: BHInsertStructure.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.6 $
028: * $Date: 2008/02/28 20:17:19 $
029: * $State: Exp $
030: */
031:
032: package javax.media.j3d;
033:
034: import java.util.*;
035:
036: class BHInsertStructure {
037:
038: static boolean debug = false;
039: static boolean debug2 = false;
040:
041: Random randomNumber;
042: ArrayList[] bhListArr = null;
043: ArrayList[] oldBhListArr = null;
044: BHNode[] bhListArrRef = null;
045: BHNode[] oldBhListArrRef = null;
046: int bhListArrCnt = 0;
047: int bhListArrMaxCnt = 0;
048: int blockSize = 0;
049:
050: BHInsertStructure(int length) {
051: randomNumber = new Random(0);
052:
053: if (length > 50) {
054: length = 50;
055: }
056:
057: blockSize = 50;
058: bhListArr = new ArrayList[length];
059: bhListArrRef = new BHNode[length];
060: bhListArrCnt = 0;
061: bhListArrMaxCnt = length;
062:
063: }
064:
065: void clear() {
066:
067: for (int i = 0; i < bhListArrCnt; i++) {
068: bhListArr[i].clear();
069: bhListArrRef[i] = null;
070: }
071: bhListArrCnt = 0;
072: }
073:
074: void lookupAndInsert(BHNode parent, BHNode child) {
075: boolean found = false;
076:
077: for (int i = 0; i < bhListArrCnt; i++) {
078: // check for current parent
079: if (bhListArrRef[i] == parent) {
080: // place child element in currents array of children
081: bhListArr[i].add(child);
082: found = true;
083: break;
084: }
085: }
086:
087: if (!found) {
088:
089: if (bhListArrCnt >= bhListArrMaxCnt) {
090: // allocate a bigger array here....
091: if (debug)
092: System.err
093: .println("(1) Expanding bhListArr array ...");
094: bhListArrMaxCnt += blockSize;
095: oldBhListArr = bhListArr;
096: oldBhListArrRef = bhListArrRef;
097:
098: bhListArr = new ArrayList[bhListArrMaxCnt];
099: bhListArrRef = new BHNode[bhListArrMaxCnt];
100: System.arraycopy(oldBhListArr, 0, bhListArr, 0,
101: oldBhListArr.length);
102: System.arraycopy(oldBhListArrRef, 0, bhListArrRef, 0,
103: oldBhListArrRef.length);
104: }
105:
106: bhListArrRef[bhListArrCnt] = parent;
107: bhListArr[bhListArrCnt] = new ArrayList();
108: bhListArr[bhListArrCnt].add(child);
109: bhListArrCnt++;
110: }
111:
112: }
113:
114: void updateBoundingTree(BHTree bhTree) {
115:
116: // based on the data in this stucture, update the tree such that
117: // all things work out now .. i.e for each element of the array list
118: // of bhListArr ... create a new reclustered tree.
119: int size, cnt;
120: BHNode child1, child2;
121:
122: for (int i = 0; i < bhListArrCnt; i++) {
123: // extract and form an array of all children : l, r, and n1 ... nk
124: cnt = 0;
125: child1 = ((BHInternalNode) (bhListArrRef[i]))
126: .getLeftChild();
127: child2 = ((BHInternalNode) (bhListArrRef[i]))
128: .getRightChild();
129: if (child1 != null)
130: cnt++;
131: if (child2 != null)
132: cnt++;
133:
134: size = bhListArr[i].size();
135:
136: BHNode bhArr[] = new BHNode[cnt + size];
137:
138: bhListArr[i].toArray(bhArr);
139:
140: //reset cnt, so that we can reuse it.
141: cnt = 0;
142: if (child1 != null) {
143: bhArr[size] = child1;
144: cnt++;
145: bhArr[size + cnt] = child2;
146: }
147:
148: if (debug2)
149: if ((child1 == null) || (child2 == null)) {
150: System.err.println("child1 or child2 is null ...");
151: System.err
152: .println("This is bad, it shouldn't happen");
153:
154: }
155:
156: ((BHInternalNode) (bhListArrRef[i])).setRightChild(null);
157: ((BHInternalNode) (bhListArrRef[i])).setLeftChild(null);
158:
159: bhTree.cluster((BHInternalNode) bhListArrRef[i], bhArr);
160: }
161: }
162:
163: }
|