babylon.octree.ts 4.5 KB

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110
  1. module BABYLON {
  2. export interface IOctreeContainer<T> {
  3. blocks: Array<OctreeBlock<T>>;
  4. }
  5. export class Octree<T> {
  6. public blocks: Array<OctreeBlock<T>>;
  7. public dynamicContent = new Array<T>();
  8. private _maxBlockCapacity: number;
  9. private _selectionContent: SmartArray<T>;
  10. private _creationFunc: (entry: T, block: OctreeBlock<T>) => void;
  11. constructor(creationFunc: (entry: T, block: OctreeBlock<T>) => void, maxBlockCapacity?: number, public maxDepth = 2) {
  12. this._maxBlockCapacity = maxBlockCapacity || 64;
  13. this._selectionContent = new BABYLON.SmartArray<T>(1024);
  14. this._creationFunc = creationFunc;
  15. }
  16. // Methods
  17. public update(worldMin: Vector3, worldMax: Vector3, entries: T[]): void {
  18. Octree._CreateBlocks(worldMin, worldMax, entries, this._maxBlockCapacity, 0, this.maxDepth, this, this._creationFunc);
  19. }
  20. public addMesh(entry: T): void {
  21. for (var index = 0; index < this.blocks.length; index++) {
  22. var block = this.blocks[index];
  23. block.addEntry(entry);
  24. }
  25. }
  26. public select(frustumPlanes: Plane[], allowDuplicate?: boolean): SmartArray<T> {
  27. this._selectionContent.reset();
  28. for (var index = 0; index < this.blocks.length; index++) {
  29. var block = this.blocks[index];
  30. block.select(frustumPlanes, this._selectionContent, allowDuplicate);
  31. }
  32. if (allowDuplicate) {
  33. this._selectionContent.concat(this.dynamicContent);
  34. } else {
  35. this._selectionContent.concatWithNoDuplicate(this.dynamicContent);
  36. }
  37. return this._selectionContent;
  38. }
  39. public intersects(sphereCenter: Vector3, sphereRadius: number, allowDuplicate?: boolean): SmartArray<T> {
  40. this._selectionContent.reset();
  41. for (var index = 0; index < this.blocks.length; index++) {
  42. var block = this.blocks[index];
  43. block.intersects(sphereCenter, sphereRadius, this._selectionContent, allowDuplicate);
  44. }
  45. if (allowDuplicate) {
  46. this._selectionContent.concat(this.dynamicContent);
  47. } else {
  48. this._selectionContent.concatWithNoDuplicate(this.dynamicContent);
  49. }
  50. return this._selectionContent;
  51. }
  52. public intersectsRay(ray: Ray): SmartArray<T> {
  53. this._selectionContent.reset();
  54. for (var index = 0; index < this.blocks.length; index++) {
  55. var block = this.blocks[index];
  56. block.intersectsRay(ray, this._selectionContent);
  57. }
  58. this._selectionContent.concatWithNoDuplicate(this.dynamicContent);
  59. return this._selectionContent;
  60. }
  61. public static _CreateBlocks<T>(worldMin: Vector3, worldMax: Vector3, entries: T[], maxBlockCapacity: number, currentDepth: number, maxDepth: number, target: IOctreeContainer<T>, creationFunc: (entry: T, block: OctreeBlock<T>) => void): void {
  62. target.blocks = new Array<OctreeBlock<T>>();
  63. var blockSize = new BABYLON.Vector3((worldMax.x - worldMin.x) / 2, (worldMax.y - worldMin.y) / 2, (worldMax.z - worldMin.z) / 2);
  64. // Segmenting space
  65. for (var x = 0; x < 2; x++) {
  66. for (var y = 0; y < 2; y++) {
  67. for (var z = 0; z < 2; z++) {
  68. var localMin = worldMin.add(blockSize.multiplyByFloats(x, y, z));
  69. var localMax = worldMin.add(blockSize.multiplyByFloats(x + 1, y + 1, z + 1));
  70. var block = new BABYLON.OctreeBlock<T>(localMin, localMax, maxBlockCapacity, currentDepth + 1, maxDepth, creationFunc);
  71. block.addEntries(entries);
  72. target.blocks.push(block);
  73. }
  74. }
  75. }
  76. }
  77. public static CreationFuncForMeshes = (entry: AbstractMesh, block: OctreeBlock<AbstractMesh>): void => {
  78. if (entry.getBoundingInfo().boundingBox.intersectsMinMax(block.minPoint, block.maxPoint)) {
  79. block.entries.push(entry);
  80. }
  81. }
  82. public static CreationFuncForSubMeshes = (entry: SubMesh, block: OctreeBlock<SubMesh>): void => {
  83. if (entry.getBoundingInfo().boundingBox.intersectsMinMax(block.minPoint, block.maxPoint)) {
  84. block.entries.push(entry);
  85. }
  86. }
  87. }
  88. }