八叉树（Octree）Typescript 实现

  1 export class Octree {
  2 
  3   // 父&子树
  4   private parent_node: any;
  5   private children_nodes: Octree[];
  6 
  7   // 原点
  8   private oringePosition: THREE.Vector3;
  9   private halfX: number;
 10   private halfY: number;
 11   private halfZ: number;
 12 
 13   // 树深度
 14   public depth: number;
 15 
 16   // 内部实体
 17   private entities: any[];
 18 
 19   private _all_entities = new Array();
 20   private _to_update: THREE.Mesh[];
 21   // 叶子？叶节点
 22   private _leaves: any;
 23 
 24   private _need_leaves_update: boolean;
 25   private _need_all_entities_update: boolean;
 26 
 27   private BoxGeo: THREE.Geometry;
 28   public BoxMesh: THREE.Mesh;
 29 
 30   entities_per_node = 1;
 31   max_depth = 5;
 32 
 33 
 34   constructor(parent: Octree, origin, halfwidth, halfheight, halfdepth) {
 35     this.oringePosition = origin;
 36     this.halfX = halfwidth;
 37     this.halfY = halfheight;
 38     this.halfZ = halfdepth;
 39 
 40     this.depth = parent === null ? 0 : parent.depth + 1;
 41 
 42     // 设置当前树内无实体
 43     this.entities = new Array();
 44     // 父子节点
 45     this.parent_node = parent;
 46     this.children_nodes = new Array();
 47 
 48     this._to_update = parent === null ? new Array() : parent._to_update;
 49 
 50     this._leaves = new Array();
 51     this._leaves.push(this);
 52 
 53     this._need_leaves_update = false;
 54     this._need_all_entities_update = false;
 55 
 56     // 视觉感受
 57     this.BoxGeo = new THREE.CubeGeometry(this.halfX * 2, this.halfY * 2, this.halfZ * 2);
 58     this.BoxMesh = new THREE.Mesh(this.BoxGeo, new THREE.MeshBasicMaterial({color: 0x0, opacity: 1, wireframe: true}));
 59     this.BoxMesh.position.set(this.oringePosition.clone().x, this.oringePosition.clone().y, this.oringePosition.clone().z);
 60 
 61     if (parent !== null) {
 62       this.BoxMesh.position.sub(parent.oringePosition);
 63       parent.BoxMesh.add(this.BoxMesh);
 64     }
 65   }
 66 
 67   // 当实体位置改变
 68   onEntityPoseChanged(entity) {
 69     if (this._to_update.indexOf(entity) === -1) {
 70       this._to_update.push(entity);
 71     }
 72   }
 73 
 74   // 判断交叉
 75   intersects(entity) {
 76     return this.contains(entity.position);
 77   };
 78 
 79   // 是否包含
 80   contains(point) {
 81     let diff = new THREE.Vector3();
 82     // subVectors方法用来将三维向量的(x,y,z)坐标值分别于参数(a,b)的(x,y,z)相减.并返回新的坐标值的三维向量.
 83     diff.subVectors(point, this.oringePosition);
 84     return Math.abs(diff.x) <= this.halfX
 85       && Math.abs(diff.y) <= this.halfY
 86       && Math.abs(diff.z) <= this.halfZ;
 87   };
 88 
 89   // 子节点更新
 90   needLeavesUpdate() {
 91     let iter = this;
 92     while (iter !== null) {
 93       iter._need_leaves_update = true;
 94       iter = iter.parent_node;
 95     }
 96   };
 97 
 98   // 将实体从当前节点中删除，并将当前this指向根节点
 99   remove(entity) {
100     for (let i = 0; i < this.entities.length; i++) {
101       if (this.entities[i] === entity) {
102         this.entities.splice(i, 1);
103         break;
104       }
105     }
106     // 删除过后将当前this指向根结点
107     let iter = this;
108     while (iter !== null) {
109       iter._need_all_entities_update = true;
110       iter = iter.parent_node;
111     }
112   };
113 
114   // 细分
115   subdivide() {
116     /*       _____________
117          /  4   /  5   /   |         y
118         /_____ /______/ |  |         |
119        /      /      /  |  |         |___ x
120       /_____ / _____/   |/ |        /
121       |   0  |  1   |  |/7 /       /
122       |_____ |_____ |/ | /       z
123       |   2  |  3   | |/
124       |_____ |_____ |/ (lol)
125     */
126 
127     if (this.depth >= this.max_depth) {
128       return;
129     }
130 
131     this.needLeavesUpdate();
132 
133     let qwidth = this.halfX / 2;
134     let qheight = this.halfY / 2;
135     let qdepth = this.halfZ / 2;
136 
137     this.children_nodes[0] = new Octree(this, new THREE.Vector3(this.oringePosition.x - qwidth,
138       this.oringePosition.y + qheight,
139       this.oringePosition.z + qdepth),
140       qwidth, qheight, qdepth);
141 
142     this.children_nodes[1] = new Octree(this, new THREE.Vector3(this.oringePosition.x + qwidth,
143       this.oringePosition.y + qheight,
144       this.oringePosition.z + qdepth),
145       qwidth, qheight, qdepth);
146 
147     this.children_nodes[2] = new Octree(this, new THREE.Vector3(this.oringePosition.x - qwidth,
148       this.oringePosition.y - qheight,
149       this.oringePosition.z + qdepth),
150       qwidth, qheight, qdepth);
151 
152     this.children_nodes[3] = new Octree(this, new THREE.Vector3(this.oringePosition.x + qwidth,
153       this.oringePosition.y - qheight,
154       this.oringePosition.z + qdepth),
155       qwidth, qheight, qdepth);
156 
157     this.children_nodes[4] = new Octree(this, new THREE.Vector3(this.oringePosition.x - qwidth,
158       this.oringePosition.y + qheight,
159       this.oringePosition.z - qdepth),
160       qwidth, qheight, qdepth);
161 
162     this.children_nodes[5] = new Octree(this, new THREE.Vector3(this.oringePosition.x + qwidth,
163       this.oringePosition.y + qheight,
164       this.oringePosition.z - qdepth),
165       qwidth, qheight, qdepth);
166 
167     this.children_nodes[6] = new Octree(this, new THREE.Vector3(this.oringePosition.x - qwidth,
168       this.oringePosition.y - qheight,
169       this.oringePosition.z - qdepth),
170       qwidth, qheight, qdepth);
171 
172     this.children_nodes[7] = new Octree(this, new THREE.Vector3(this.oringePosition.x + qwidth,
173       this.oringePosition.y - qheight,
174       this.oringePosition.z - qdepth),
175       qwidth, qheight, qdepth);
176   };
177 
178   add(entity) {
179 
180     let _this = this;
181 
182     function addToThis() {
183       let iter = _this;
184       while (iter !== null) {
185         iter._need_all_entities_update = true;
186         iter = iter.parent_node;
187       }
188       _this.entities.push(entity);
189       _this.BoxMesh.visible = true;
190     }
191 
192     // 如果不包含=>返回
193     // 也就是说如果新增的Mesh 不在大Mesh中，不进行查找
194     if (!this.intersects(entity)) {
195       return;
196     }
197 
198     if (this.depth >= this.max_depth) {
199       addToThis();
200     }
201     else if (this.children_nodes.length === 0) {
202       // ↑小于最大深度&没有子节点并且它里面没有实体的时候
203       // ↓每个节点中的数量小于规定要求
204       if (this.entities.length < this.entities_per_node) {
205         addToThis();
206       }
207       else {
208         // 如果它里面有实体，则拆分
209         this.subdivide();
210         // 拆分过后，如果内部有实体，则从这个节点中删除，并重新对所有实体做add动作（通过this值的变化）
211         if (this.entities.length !== 0) {
212           let entities_tmp = this.entities.slice();
213           this.entities.length = 0;
214           while (entities_tmp.length > 0) {
215             let ent = entities_tmp.pop();
216             this.remove(ent);
217             this.add(ent);
218           }
219         }
220         // 然后再将这个节点添加到指定位置
221         this.add(entity);
222       }
223     }
224     else {
225       // ↑如果它当前有节点，已经分成八份
226       // check if the obb intersects multiple children
227       let child_id = -1;
228       let multiple_intersect = false;
229       for (let i = 0; i < this.children_nodes.length; i++) {
230         if (this.children_nodes[i].intersects(entity)) {
231           if (child_id !== -1) {
232             multiple_intersect = true;
233             break;
234           }
235           child_id = i;
236         }
237       }
238       // 把当前结点放入制定的位置中
239       if (multiple_intersect) {
240         addToThis();
241       }
242       else {
243         // 放入0节点中
244         this.children_nodes[child_id].add(entity);
245       }
246     }
247   }
248 
249   empty() {
250     if (this.entities.length > 0) {
251       return false;
252     }
253 
254     for (let i = 0; i < this.children_nodes.length; i++) {
255       if (!this.children_nodes[i].empty()) {
256         return false;
257       }
258     }
259     return true;
260   };
261 
262   countChildrenIntersections(max, entity) {
263     let children_idx = new Array();
264     for (let j = 0; j < this.children_nodes.length; j++) {
265       if (this.children_nodes[j].intersects(entity)) {
266         children_idx.push(j);
267       }
268       if (children_idx.length === max) {
269         break;
270       }
271     }
272     return children_idx;
273   }
274 
275   // updates children entities reference
276   updateChildrenEntities() {
277     if (this._need_all_entities_update) {
278       this._all_entities.length = 0;
279       for (let i = 0; i < this.children_nodes.length; i++) {
280         this.children_nodes[i].updateChildrenEntities();
281         this._all_entities = this._all_entities.concat(this.children_nodes[i]._all_entities);
282       }
283 
284       for (let i = 0; i < this.entities.length; i++) {
285         this._all_entities.push([this.entities[i], this]);
286       }
287     }
288   }
289 
290   // updates leaves reference
291   updateLeaves() {
292     if (this._need_leaves_update) {
293       this._leaves.length = 0;
294       for (let i = 0; i < this.children_nodes.length; i++) {
295 
296         this.children_nodes[i].updateLeaves();
297         this._leaves = this._leaves.concat(this.children_nodes[i]._leaves);
298       }
299 
300       if (this.children_nodes.length === 0) {
301         this._leaves.push(this);
302       }
303 
304       this._need_leaves_update = false;
305     }
306   }
307 
308   update() {
309     let _this = this;
310     _this.updateChildrenEntities();
311     let entities_tmp = this._all_entities.slice();
312     entities_tmp.forEach(function (element) {
313       let entity = element[0];
314 
315       for (let i = 0; i < _this._to_update.length; i++) {
316         if (entity === _this._to_update[i]) {
317           let octree;
318           let intersections;
319 
320           // check if multiple intersection with children
321           // if yes do same recursively with parents till we can fit it entirely
322           // in one node, and add it to this node
323           octree = element[1];
324           while (octree !== null) {
325             intersections = octree.countChildrenIntersections(2, entity);
326 
327             if (intersections.length === 1) {
328               // don't perform any operation if no update is required
329               if (element[1] === octree.children_nodes[intersections[0]]) {
330                 break;
331               }
332               element[1].remove(entity);
333               octree.children_nodes[intersections[0]].add(entity);
334               break;
335             }
336             else if (octree.parent_node === null && intersections.length > 0) {
337               element[1].remove(entity);
338               octree.add(entity);
339               break;
340             }
341             else {
342               octree = octree.parent_node;
343             }
344           }
345           _this._to_update.splice(i, 1);
346           break;
347         }
348       }
349     });
350 
351     // update _all_entities arrays
352     _this.updateChildrenEntities();
353 
354     // get rid of dead leaves
355     _this.updateLeaves();
356 
357     function pruneUp(node) {
358       if (node._all_entities.length <= 1) {
359         // remove the children from the leaves array and detach their mesh from parents
360         let removeChildrenNodes = function (nodes) {
361           for (let i = 0; i < nodes.children_nodes.length; i++) {
362             removeChildrenNodes(nodes.children_nodes[i]);
363             let idx = _this._leaves.indexOf(nodes.children_nodes[i]);
364             if (idx !== -1) {
365               _this._leaves.splice(idx, 1);
366             }
367             nodes.BoxMesh.remove(nodes.children_nodes[i].BoxMesh);
368           }
369         };
370 
371         removeChildrenNodes(node);
372 
373         node.needLeavesUpdate();
374         node.children_nodes.length = 0;
375 
376         if (node._all_entities.length === 1 && (node._all_entities[0])[1] !== node) {
377           // if the entity was in a one of the child, put it in current node
378           node._all_entities[0][1] = node;    // will update this ref for parents node too
379           node.add(node._all_entities[0][0]);
380         }
381         if (node.parent_node !== null) {
382           pruneUp(node.parent_node);
383         }
384       }
385     }
386 
387     this._leaves.forEach(function (node) {
388       pruneUp(node);
389     });
390   };
391 
392 }