octreeBlock.js 7.9 KB

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199
  1. import { Vector3 } from "../../Maths/math.vector.js";
  2. import { BoundingBox } from "../../Culling/boundingBox.js";
  3. /**
  4. * Class used to store a cell in an octree
  5. * @see https://doc.babylonjs.com/features/featuresDeepDive/scene/optimizeOctrees
  6. */
  7. export class OctreeBlock {
  8. /**
  9. * Creates a new block
  10. * @param minPoint defines the minimum vector (in world space) of the block's bounding box
  11. * @param maxPoint defines the maximum vector (in world space) of the block's bounding box
  12. * @param capacity defines the maximum capacity of this block (if capacity is reached the block will be split into sub blocks)
  13. * @param depth defines the current depth of this block in the octree
  14. * @param maxDepth defines the maximal depth allowed (beyond this value, the capacity is ignored)
  15. * @param creationFunc defines a callback to call when an element is added to the block
  16. */
  17. constructor(minPoint, maxPoint, capacity, depth, maxDepth, creationFunc) {
  18. /**
  19. * Gets the content of the current block
  20. */
  21. this.entries = [];
  22. this._boundingVectors = new Array();
  23. this._capacity = capacity;
  24. this._depth = depth;
  25. this._maxDepth = maxDepth;
  26. this._creationFunc = creationFunc;
  27. this._minPoint = minPoint;
  28. this._maxPoint = maxPoint;
  29. this._boundingVectors.push(minPoint.clone());
  30. this._boundingVectors.push(maxPoint.clone());
  31. this._boundingVectors.push(minPoint.clone());
  32. this._boundingVectors[2].x = maxPoint.x;
  33. this._boundingVectors.push(minPoint.clone());
  34. this._boundingVectors[3].y = maxPoint.y;
  35. this._boundingVectors.push(minPoint.clone());
  36. this._boundingVectors[4].z = maxPoint.z;
  37. this._boundingVectors.push(maxPoint.clone());
  38. this._boundingVectors[5].z = minPoint.z;
  39. this._boundingVectors.push(maxPoint.clone());
  40. this._boundingVectors[6].x = minPoint.x;
  41. this._boundingVectors.push(maxPoint.clone());
  42. this._boundingVectors[7].y = minPoint.y;
  43. }
  44. // Property
  45. /**
  46. * Gets the maximum capacity of this block (if capacity is reached the block will be split into sub blocks)
  47. */
  48. get capacity() {
  49. return this._capacity;
  50. }
  51. /**
  52. * Gets the minimum vector (in world space) of the block's bounding box
  53. */
  54. get minPoint() {
  55. return this._minPoint;
  56. }
  57. /**
  58. * Gets the maximum vector (in world space) of the block's bounding box
  59. */
  60. get maxPoint() {
  61. return this._maxPoint;
  62. }
  63. // Methods
  64. /**
  65. * Add a new element to this block
  66. * @param entry defines the element to add
  67. */
  68. addEntry(entry) {
  69. if (this.blocks) {
  70. for (let index = 0; index < this.blocks.length; index++) {
  71. const block = this.blocks[index];
  72. block.addEntry(entry);
  73. }
  74. return;
  75. }
  76. this._creationFunc(entry, this);
  77. if (this.entries.length > this.capacity && this._depth < this._maxDepth) {
  78. this.createInnerBlocks();
  79. }
  80. }
  81. /**
  82. * Remove an element from this block
  83. * @param entry defines the element to remove
  84. */
  85. removeEntry(entry) {
  86. if (this.blocks) {
  87. for (let index = 0; index < this.blocks.length; index++) {
  88. const block = this.blocks[index];
  89. block.removeEntry(entry);
  90. }
  91. return;
  92. }
  93. const entryIndex = this.entries.indexOf(entry);
  94. if (entryIndex > -1) {
  95. this.entries.splice(entryIndex, 1);
  96. }
  97. }
  98. /**
  99. * Add an array of elements to this block
  100. * @param entries defines the array of elements to add
  101. */
  102. addEntries(entries) {
  103. for (let index = 0; index < entries.length; index++) {
  104. const mesh = entries[index];
  105. this.addEntry(mesh);
  106. }
  107. }
  108. /**
  109. * Test if the current block intersects the frustum planes and if yes, then add its content to the selection array
  110. * @param frustumPlanes defines the frustum planes to test
  111. * @param selection defines the array to store current content if selection is positive
  112. * @param allowDuplicate defines if the selection array can contains duplicated entries
  113. */
  114. select(frustumPlanes, selection, allowDuplicate) {
  115. if (BoundingBox.IsInFrustum(this._boundingVectors, frustumPlanes)) {
  116. if (this.blocks) {
  117. for (let index = 0; index < this.blocks.length; index++) {
  118. const block = this.blocks[index];
  119. block.select(frustumPlanes, selection, allowDuplicate);
  120. }
  121. return;
  122. }
  123. if (allowDuplicate) {
  124. selection.concat(this.entries);
  125. }
  126. else {
  127. selection.concatWithNoDuplicate(this.entries);
  128. }
  129. }
  130. }
  131. /**
  132. * Test if the current block intersect with the given bounding sphere and if yes, then add its content to the selection array
  133. * @param sphereCenter defines the bounding sphere center
  134. * @param sphereRadius defines the bounding sphere radius
  135. * @param selection defines the array to store current content if selection is positive
  136. * @param allowDuplicate defines if the selection array can contains duplicated entries
  137. */
  138. intersects(sphereCenter, sphereRadius, selection, allowDuplicate) {
  139. if (BoundingBox.IntersectsSphere(this._minPoint, this._maxPoint, sphereCenter, sphereRadius)) {
  140. if (this.blocks) {
  141. for (let index = 0; index < this.blocks.length; index++) {
  142. const block = this.blocks[index];
  143. block.intersects(sphereCenter, sphereRadius, selection, allowDuplicate);
  144. }
  145. return;
  146. }
  147. if (allowDuplicate) {
  148. selection.concat(this.entries);
  149. }
  150. else {
  151. selection.concatWithNoDuplicate(this.entries);
  152. }
  153. }
  154. }
  155. /**
  156. * Test if the current block intersect with the given ray and if yes, then add its content to the selection array
  157. * @param ray defines the ray to test with
  158. * @param selection defines the array to store current content if selection is positive
  159. */
  160. intersectsRay(ray, selection) {
  161. if (ray.intersectsBoxMinMax(this._minPoint, this._maxPoint)) {
  162. if (this.blocks) {
  163. for (let index = 0; index < this.blocks.length; index++) {
  164. const block = this.blocks[index];
  165. block.intersectsRay(ray, selection);
  166. }
  167. return;
  168. }
  169. selection.concatWithNoDuplicate(this.entries);
  170. }
  171. }
  172. /**
  173. * Subdivide the content into child blocks (this block will then be empty)
  174. */
  175. createInnerBlocks() {
  176. OctreeBlock._CreateBlocks(this._minPoint, this._maxPoint, this.entries, this._capacity, this._depth, this._maxDepth, this, this._creationFunc);
  177. this.entries.splice(0);
  178. }
  179. /**
  180. * @internal
  181. */
  182. static _CreateBlocks(worldMin, worldMax, entries, maxBlockCapacity, currentDepth, maxDepth, target, creationFunc) {
  183. target.blocks = new Array();
  184. const blockSize = new Vector3((worldMax.x - worldMin.x) / 2, (worldMax.y - worldMin.y) / 2, (worldMax.z - worldMin.z) / 2);
  185. // Segmenting space
  186. for (let x = 0; x < 2; x++) {
  187. for (let y = 0; y < 2; y++) {
  188. for (let z = 0; z < 2; z++) {
  189. const localMin = worldMin.add(blockSize.multiplyByFloats(x, y, z));
  190. const localMax = worldMin.add(blockSize.multiplyByFloats(x + 1, y + 1, z + 1));
  191. const block = new OctreeBlock(localMin, localMax, maxBlockCapacity, currentDepth + 1, maxDepth, creationFunc);
  192. block.addEntries(entries);
  193. target.blocks.push(block);
  194. }
  195. }
  196. }
  197. }
  198. }
  199. //# sourceMappingURL=octreeBlock.js.map