octree.js 5.9 KB

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135
  1. import { SmartArrayNoDuplicate } from "../../Misc/smartArray.js";
  2. import { OctreeBlock } from "./octreeBlock.js";
  3. /**
  4. * Octrees are a really powerful data structure that can quickly select entities based on space coordinates.
  5. * @see https://doc.babylonjs.com/features/featuresDeepDive/scene/optimizeOctrees
  6. */
  7. export class Octree {
  8. /**
  9. * Creates a octree
  10. * @see https://doc.babylonjs.com/features/featuresDeepDive/scene/optimizeOctrees
  11. * @param creationFunc function to be used to instantiate the octree
  12. * @param maxBlockCapacity defines the maximum number of meshes you want on your octree's leaves (default: 64)
  13. * @param maxDepth defines the maximum depth (sub-levels) for your octree. Default value is 2, which means 8 8 8 = 512 blocks :) (This parameter takes precedence over capacity.)
  14. */
  15. constructor(creationFunc, maxBlockCapacity,
  16. /** Defines the maximum depth (sub-levels) for your octree. Default value is 2, which means 8 8 8 = 512 blocks :) (This parameter takes precedence over capacity.) */
  17. maxDepth = 2) {
  18. this.maxDepth = maxDepth;
  19. /**
  20. * Content stored in the octree
  21. */
  22. this.dynamicContent = [];
  23. this._maxBlockCapacity = maxBlockCapacity || 64;
  24. this._selectionContent = new SmartArrayNoDuplicate(1024);
  25. this._creationFunc = creationFunc;
  26. }
  27. // Methods
  28. /**
  29. * Updates the octree by adding blocks for the passed in meshes within the min and max world parameters
  30. * @param worldMin worldMin for the octree blocks var blockSize = new Vector3((worldMax.x - worldMin.x) / 2, (worldMax.y - worldMin.y) / 2, (worldMax.z - worldMin.z) / 2);
  31. * @param worldMax worldMax for the octree blocks var blockSize = new Vector3((worldMax.x - worldMin.x) / 2, (worldMax.y - worldMin.y) / 2, (worldMax.z - worldMin.z) / 2);
  32. * @param entries meshes to be added to the octree blocks
  33. */
  34. update(worldMin, worldMax, entries) {
  35. OctreeBlock._CreateBlocks(worldMin, worldMax, entries, this._maxBlockCapacity, 0, this.maxDepth, this, this._creationFunc);
  36. }
  37. /**
  38. * Adds a mesh to the octree
  39. * @param entry Mesh to add to the octree
  40. */
  41. addMesh(entry) {
  42. for (let index = 0; index < this.blocks.length; index++) {
  43. const block = this.blocks[index];
  44. block.addEntry(entry);
  45. }
  46. }
  47. /**
  48. * Remove an element from the octree
  49. * @param entry defines the element to remove
  50. */
  51. removeMesh(entry) {
  52. for (let index = 0; index < this.blocks.length; index++) {
  53. const block = this.blocks[index];
  54. block.removeEntry(entry);
  55. }
  56. }
  57. /**
  58. * Selects an array of meshes within the frustum
  59. * @param frustumPlanes The frustum planes to use which will select all meshes within it
  60. * @param allowDuplicate If duplicate objects are allowed in the resulting object array
  61. * @returns array of meshes within the frustum
  62. */
  63. select(frustumPlanes, allowDuplicate) {
  64. this._selectionContent.reset();
  65. for (let index = 0; index < this.blocks.length; index++) {
  66. const block = this.blocks[index];
  67. block.select(frustumPlanes, this._selectionContent, allowDuplicate);
  68. }
  69. if (allowDuplicate) {
  70. this._selectionContent.concat(this.dynamicContent);
  71. }
  72. else {
  73. this._selectionContent.concatWithNoDuplicate(this.dynamicContent);
  74. }
  75. return this._selectionContent;
  76. }
  77. /**
  78. * Test if the octree intersect with the given bounding sphere and if yes, then add its content to the selection array
  79. * @param sphereCenter defines the bounding sphere center
  80. * @param sphereRadius defines the bounding sphere radius
  81. * @param allowDuplicate defines if the selection array can contains duplicated entries
  82. * @returns an array of objects that intersect the sphere
  83. */
  84. intersects(sphereCenter, sphereRadius, allowDuplicate) {
  85. this._selectionContent.reset();
  86. for (let index = 0; index < this.blocks.length; index++) {
  87. const block = this.blocks[index];
  88. block.intersects(sphereCenter, sphereRadius, this._selectionContent, allowDuplicate);
  89. }
  90. if (allowDuplicate) {
  91. this._selectionContent.concat(this.dynamicContent);
  92. }
  93. else {
  94. this._selectionContent.concatWithNoDuplicate(this.dynamicContent);
  95. }
  96. return this._selectionContent;
  97. }
  98. /**
  99. * Test if the octree intersect with the given ray and if yes, then add its content to resulting array
  100. * @param ray defines the ray to test with
  101. * @returns array of intersected objects
  102. */
  103. intersectsRay(ray) {
  104. this._selectionContent.reset();
  105. for (let index = 0; index < this.blocks.length; index++) {
  106. const block = this.blocks[index];
  107. block.intersectsRay(ray, this._selectionContent);
  108. }
  109. this._selectionContent.concatWithNoDuplicate(this.dynamicContent);
  110. return this._selectionContent;
  111. }
  112. }
  113. /**
  114. * Adds a mesh into the octree block if it intersects the block
  115. * @param entry defines the mesh to try to add to the block
  116. * @param block defines the block where the mesh should be added
  117. */
  118. Octree.CreationFuncForMeshes = (entry, block) => {
  119. const boundingInfo = entry.getBoundingInfo();
  120. if (!entry.isBlocked && boundingInfo.boundingBox.intersectsMinMax(block.minPoint, block.maxPoint)) {
  121. block.entries.push(entry);
  122. }
  123. };
  124. /**
  125. * Adds a submesh into the octree block if it intersects the block
  126. * @param entry defines the submesh to try to add to the block
  127. * @param block defines the block where the submesh should be added
  128. */
  129. Octree.CreationFuncForSubMeshes = (entry, block) => {
  130. const boundingInfo = entry.getBoundingInfo();
  131. if (boundingInfo.boundingBox.intersectsMinMax(block.minPoint, block.maxPoint)) {
  132. block.entries.push(entry);
  133. }
  134. };
  135. //# sourceMappingURL=octree.js.map