Huge News!Announcing our $40M Series B led by Abstract Ventures.Learn More →
three-mesh-bvh
Advanced tools
three-mesh-bvh - npm Package Compare versions
Comparing version 0.4.3 to 0.5.0
@@ -8,3 +8,28 @@ # Changelog | ||
| ## Unreleased | ||
| ### Added | ||
| - `useSharedArrayBuffer` option to `MeshBVH` so `SharedArrayBuffers` are created rather than `ArrayBuffers` making it easier to share and reuse BVH memory across workers. | ||
| - SeparatingAxisTriangle.intersectsTriangle: added `target` field to retrieve the edge describing the intersection. | ||
| - "box" argument to shapecast "intersectsRange" function. | ||
| - `/* @__PURE__ */` indicator to reusable variables. | ||
| ### Fixed | ||
| - `raycast` and `raycastFirst` not properly accounting for material sidedness with geometry groups. | ||
| - Case where the BVH root bounds would be incorrect if the geometry bounding box was incorrect / out of date. | ||
| - MeshBVH.closestPointTGeometry not returning a proper intersection point if triangles intersect. | ||
| - Shapecast function will now ensure a unique triangle / box is provided for each recursive call. | ||
| - Fix `GenerateMeshBVHWorker` not setting the geometry index correctly on return. | ||
| ### Changed | ||
| - Changed function signature for `intersectsGeometry`, `shapecast`, `intersectsBox`, `intersectsSphere`, `closestPointToGeometry`, `closestPointToPoint`, `raycast`, and `raycastFirst`. Specifically at least the first "mesh" argument has been removed. Calling functions with the old signature will log a warning. See documentation for current signatures. | ||
| - `raycast` and `raycastFirst` now return hits in the local space of the geometry rather than world space when querying the BVH directly to conform with other cast functions. Results still match three.js' original results when using `Raycaster.intersectObject(s)` functions. See documentation for more details. | ||
| - `MeshBVHDebug` class has been removed and the function `getJSONStructure` and `validateBounds` are now exported individually. | ||
| - Small observed performance improvements possibly a result of simplified function arguments. | ||
| - The function signatures and options for `MeshBVH.serialize` and `MeshBVH.deserialize` have changed. See documentation for more new signature. | ||
| - Changed `refit` function to take just a single argument with traversed node indices. Calling the function with the old signature will log a warning. See documentation for current signature. | ||
| ### Removed | ||
| - `distanceToGeometry` and `distanceToPoint` functions. | ||
| ## [0.4.3] - 2021-08-20 | ||
| ### Fixed | ||
| - Fixed Surface Area Heuristic (SAH) split strategy to function correctly, improve build performance, and produce more optimal bounds and improved a memory footprint. | ||
@@ -11,0 +36,0 @@ |
| { | ||
| "name": "three-mesh-bvh", | ||
| "version": "0.4.3", | ||
| "version": "0.5.0", | ||
| "description": "A BVH implementation to speed up raycasting against three.js meshes.", | ||
@@ -10,4 +10,5 @@ "module": "src/index.js", | ||
| "scripts": { | ||
| "start": "concurrently \"parcel watch ./example/*.html --out-dir ./example/dev-bundle/ --public-url . --no-cache\" \"rollup -w -c\" \"static-server\"", | ||
| "build": "rollup -c && parcel build ./example/*.html --out-dir ./example/bundle/ --public-url . --no-cache --no-source-maps --no-content-hash", | ||
| "start": "concurrently \"parcel watch ./example/*.html --out-dir ./example/dev-bundle/ --public-url . --no-cache\" \"static-server\"", | ||
| "build": "rollup -c", | ||
| "build-examples": "parcel build ./example/*.html --out-dir ./example/bundle/ --public-url . --no-cache --no-source-maps --no-content-hash", | ||
| "test": "jest", | ||
@@ -31,2 +32,4 @@ "lint": "eslint \"./src/**/*.js\" \"./test/**/*.js\" \"./example/*.js\"", | ||
| "performance", | ||
| "raytracing", | ||
| "pathtracing", | ||
| "geometry", | ||
@@ -55,4 +58,4 @@ "mesh", | ||
| "devDependencies": { | ||
| "@babel/core": "^7.14.3", | ||
| "@babel/preset-env": "^7.14.2", | ||
| "@babel/core": "^7.15.5", | ||
| "@babel/preset-env": "^7.15.4", | ||
| "babel-jest": "^26.6.3", | ||
@@ -72,5 +75,5 @@ "concurrently": "^5.3.0", | ||
| "stats.js": "^0.17.0", | ||
| "three": "^0.126.1" | ||
| "three": "^0.133.0" | ||
| }, | ||
| "dependencies": {} | ||
| } |
212
README.md
@@ -18,2 +18,4 @@ # three-mesh-bvh | ||
| [CPU Path Tracing demo](https://gkjohnson.github.io/three-mesh-bvh/example/bundle/cpuPathTracing.html) | ||
| [Clipped edges demo](https://gkjohnson.github.io/three-mesh-bvh/example/bundle/clippedEdges.html) | ||
@@ -113,8 +115,12 @@ | ||
| raycaster.ray.applyMatrix4( invMat ); | ||
| const hit = bvh.raycastFirst( mesh, raycaster, raycaster.ray ); | ||
| const hit = bvh.raycastFirst( raycaster ); | ||
| // results are returned in local spac, as well, so they must be transformed into | ||
| // world space if needed. | ||
| hit.point.applyMatrixWorld( mesh.matrixWorld ); | ||
| // spherecasting | ||
| // ensure the sphere is in the lcoal space of hte geometry being cast against | ||
| // ensure the sphere is in the local space of the geometry being cast against | ||
| sphere.applyMatrix4( invMat ); | ||
| const intersects = bvh.intersectsSphere( mesh, sphere ); | ||
| const intersects = bvh.intersectsSphere( sphere ); | ||
| ``` | ||
@@ -127,3 +133,3 @@ | ||
| const bvh = new MeshBVH( geometry ); | ||
| const serialized = MeshBVH.serialize( bvh, geometry ); | ||
| const serialized = MeshBVH.serialize( bvh ); | ||
@@ -194,26 +200,47 @@ // ... | ||
| Note that all query functions expect arguments in local space of the BVH and return results in local space, as well. If world space results are needed they must be transformed into world space using `object.matrixWorld`. | ||
| ### static .serialize | ||
| ```js | ||
| static serialize( bvh : MeshBVH, geometry : BufferGeometry, copyIndexBuffer = true : Boolean ) : SerializedBVH | ||
| static serialize( bvh : MeshBVH, options : Object = null ) : SerializedBVH | ||
| ``` | ||
| Generates a representation of the complete bounds tree and the geometry index buffer which can be used to recreate a bounds tree using the [deserialize](#static-deserialize) function. The `serialize` and `deserialize` functions can be used to generate a MeshBVH asynchronously in a background web worker to prevent the main thread from stuttering. | ||
| Generates a representation of the complete bounds tree and the geometry index buffer which can be used to recreate a bounds tree using the [deserialize](#static-deserialize) function. The `serialize` and `deserialize` functions can be used to generate a MeshBVH asynchronously in a background web worker to prevent the main thread from stuttering. The BVH roots buffer stored in the serialized representation are the same as the ones used by the original BVH so they should not be modified. If `SharedArrayBuffers` are used then the same BVH memory can be used for multiple BVH in multiple WebWorkers. | ||
| `bvh` is the MeshBVH to be serialized and `geometry` is the bufferGeometry used to generate and raycast against using the `bvh`. | ||
| `bvh` is the MeshBVH to be serialized. The `options` object can have the following fields: | ||
| If `copyIndexBuffer` is true then a copy of the `geometry.index.array` is made which is slower but useful is the geometry index is intended to be modified. | ||
| ```js | ||
| { | ||
| // if true then a clone of the `geometry.index.array` and MeshBVH buffers are made which slightly slower but | ||
| // ensures modifications do not affect the serialized content. Can be set to "false" if it is guaranteed that | ||
| // no modifications will be made, to save memory, or transfer and share them across WebWorkers if SharedArrayBuffers | ||
| // are being used. | ||
| cloneBuffers: true | ||
| } | ||
| ``` | ||
| ### static .deserialize | ||
| ```js | ||
| static deserialize( data : SerializedBVH, geometry : BufferGeometry, setIndex = true : Boolean ) : MeshBVH | ||
| static deserialize( data : SerializedBVH, geometry : BufferGeometry, options : Object = null ) : MeshBVH | ||
| ``` | ||
| Returns a new MeshBVH instance from the serialized data. `geometry` is the geometry used to generate the original bvh `data` was derived from. If `setIndex` is true then the buffer for the `geometry.index` attribute is set from the serialized data attribute or created if an index does not exist. | ||
| Returns a new MeshBVH instance from the serialized data. `geometry` is the geometry used to generate the original BVH `data` was derived from. The root buffers stored in `data` are set directly on the new BVH so the memory is shared. | ||
| The `options` object can have the following fields: | ||
| ```js | ||
| { | ||
| // If true then the buffer for the `geometry.index` attribute is set from the serialized | ||
| // data attribute or created if an index does not exist. | ||
| setIndex: true, | ||
| } | ||
| ``` | ||
| _NOTE: In order for the bounds tree to be used for casts the geometry index attribute must be replaced by the data in the SeralizedMeshBVH object._ | ||
| _NOTE: The returned MeshBVH is a fully generated, buffer packed BVH instance to improve memory footprint and uses the same buffers passed in on the `data.root` property._ | ||
| ### .constructor | ||
@@ -246,2 +273,7 @@ | ||
| // If true then the MeshBVH will use SharedArrayBuffer rather than ArrayBuffer when | ||
| // initializing the BVH buffers. Geometry index data will be created as a | ||
| // SharedArrayBuffer only if it needs to be created. Otherwise it is used as-is. | ||
| useSharedArrayBuffer: false, | ||
| // Print out warnings encountered during tree construction. | ||
@@ -258,14 +290,22 @@ verbose: true, | ||
| ```js | ||
| raycast( mesh : Mesh, raycaster : Raycaster, ray : Ray, intersects : Array ) : Array<RaycastHit> | ||
| raycast( ray : Ray, side : FrontSide | BackSide | DoubleSide = FrontSide ) : Array<RaycastHit> | ||
| ``` | ||
| ```js | ||
| raycast( ray : Ray, material : Array<Material> | Material ) : Array<RaycastHit> | ||
| ``` | ||
| Adds all raycast triangle hits in unsorted order to the `intersects` array. It is expected that `ray` is in the frame of the mesh being raycast against and that the geometry on `mesh` is the same as the one used to generate the bvh. | ||
| Returns all raycast triangle hits in unsorted order. It is expected that `ray` is in the frame of the BVH already. Likewise the returned results are also provided in the local frame of the BVH. The `side` identifier is used to determine the side to check when raycasting or a material with the given side field can be passed. If an array of materials is provided then it is expected that the geometry has groups and the appropriate material side is used per group. | ||
| Note that unlike three.js' Raycaster results the points and distances in the intersections returned from this function are relative to the local frame of the MeshBVH. When using the [acceleratedRaycast](#acceleratedRaycast) function as an override for `Mesh.raycast` they are transformed into world space to be consistent with three's results. | ||
| ### .raycastFirst | ||
| ```js | ||
| raycastFirst( mesh : Mesh, raycaster : Raycaster, ray : Ray ) : RaycastHit | ||
| raycastFirst( ray : Ray, side : FrontSide | BackSide | DoubleSide = FrontSide ) : RaycastHit | ||
| ``` | ||
| ```js | ||
| raycastFirst( ray : Ray, material : Array<Material> | Material ) : RaycastHit | ||
| ``` | ||
| Returns the first raycast hit in the model. This is typically much faster than returning all hits. | ||
| Returns the first raycast hit in the model. This is typically much faster than returning all hits. See [raycast](#raycast) for information on the side and material options as well as the frame of the returned intersections. | ||
@@ -275,3 +315,3 @@ ### .intersectsSphere | ||
| ```js | ||
| intersectsSphere( mesh : Mesh, sphere : Sphere ) : Boolean | ||
| intersectsSphere( sphere : Sphere ) : Boolean | ||
| ``` | ||
@@ -284,3 +324,3 @@ | ||
| ```js | ||
| intersectsBox( mesh : Mesh, box : Box3, boxToBvh : Matrix4 ) : Boolean | ||
| intersectsBox( box : Box3, boxToBvh : Matrix4 ) : Boolean | ||
| ``` | ||
@@ -295,3 +335,3 @@ | ||
| ```js | ||
| intersectsGeometry( mesh : Mesh, geometry : BufferGeometry, geometryToBvh : Matrix4 ) : Boolean | ||
| intersectsGeometry( geometry : BufferGeometry, geometryToBvh : Matrix4 ) : Boolean | ||
| ``` | ||
@@ -301,3 +341,3 @@ | ||
| The `geometryToBvh` parameter is the transform of the geometry in the mesh's frame. | ||
| The `geometryToBvh` parameter is the transform of the geometry in the BVH's local frame. | ||
@@ -310,14 +350,23 @@ Performance improves considerably if the provided geometry _also_ has a `boundsTree`. | ||
| closestPointToPoint( | ||
| mesh : Mesh, | ||
| point : Vector3, | ||
| target : Vector3, | ||
| target : Object = {}, | ||
| minThreshold : Number = 0, | ||
| maxThreshold : Number = Infinity | ||
| ) : Number | ||
| ) : target | ||
| ``` | ||
| Returns the closest distance from the point to the mesh and puts the closest point on the mesh in `target`. | ||
| Computes the closest distance from the point to the mesh and gives additional information in `target`. The target can be left undefined to default to a new object which is ultimately returned by the function. | ||
| If a point is found that is closer than `minThreshold` then the function will return that result early. Any triangles or points outside of `maxThreshold` are ignored. | ||
| If a point is found that is closer than `minThreshold` then the function will return that result early. Any triangles or points outside of `maxThreshold` are ignored. If no point is found within the min / max thresholds then `null` is returned and the `target` object is not modified. | ||
| ```js | ||
| target : { | ||
| point : Vector3, | ||
| distance : Number, | ||
| faceIndex : Number | ||
| } | ||
| ``` | ||
| The returned faceIndex can be used with the standalone function [getTriangleHitPointInfo](#getTriangleHitPointInfo) to obtain more information like UV coordinates, triangle normal and materialIndex. | ||
| ### .closestPointToGeometry | ||
@@ -327,18 +376,21 @@ | ||
| closestPointToGeometry( | ||
| mesh : Mesh, | ||
| geometry : BufferGeometry, | ||
| geometryToBvh : Matrix4, | ||
| target1 : Vector3 = null, | ||
| target2 : Vector3 = null, | ||
| target1 : Object = {}, | ||
| target2 : Object = {}, | ||
| minThreshold : Number = 0, | ||
| maxThreshold : Number = Infinity | ||
| ) : Number | ||
| ) : target1 | ||
| ``` | ||
| Returns the closest distance from the geometry to the mesh and puts the closest point on the mesh in `target1` and the closest point on the other geometry in `target2` in the frame of the BVH. | ||
| Computes the closest distance from the geometry to the mesh and puts the closest point on the mesh in `target1` (in the frame of the BVH) and the closest point on the other geometry in `target2` (in the geometry frame). If `target1` is not provided a new Object is created and returned from the function. | ||
| The `geometryToBvh` parameter is the transform of the geometry in the mesh's frame. | ||
| The `geometryToBvh` parameter is the transform of the geometry in the BVH's local frame. | ||
| If a point is found that is closer than `minThreshold` then the function will return that result early. Any triangles or points outside of `maxThreshold` are ignored. | ||
| If a point is found that is closer than `minThreshold` then the function will return that result early. Any triangles or points outside of `maxThreshold` are ignored. If no point is found within the min / max thresholds then `null` is returned and the target objects are not modified. | ||
| `target1` and `target2` are optional objects that similar to the `target` parameter in [closestPointPoint](#closestPointToPoint) and set with the same fields as that function. | ||
| The returned in `target1` and `target2` can be used with the standalone function [getTriangleHitPointInfo](#getTriangleHitPointInfo) to obtain more information like UV coordinates, triangle normal and materialIndex. | ||
| _Note that this function can be very slow if `geometry` does not have a `geometry.boundsTree` computed._ | ||
@@ -350,4 +402,2 @@ | ||
| shapecast( | ||
| mesh : Mesh, | ||
| callbacks : { | ||
@@ -372,3 +422,4 @@ | ||
| depth : Number, | ||
| nodeIndex : Number | ||
| nodeIndex : Number, | ||
| box: Box3 | ||
| ) => Boolean = null, | ||
@@ -388,27 +439,19 @@ | ||
| A generalized cast function that can be used to implement intersection logic for custom shapes. This is used internally for [intersectsBox](#intersectsBox) and [intersectsSphere](#intersectsSphere). The function returns as soon as a triangle has been reported as intersected and returns `true` if a triangle has been intersected. The bounds are traversed in depth first order calling `traverseBoundsOrder`, `intersectsBoundsFunc`, `intersectsRange`, and intersectsTriangle for each node and using the results to determine traversal depth. The `depth` value passed to callbacks indicates the depth of the bounds the provided box or bounds belongs to unless the triangles are indicated to be `CONTAINED`, in which case depth is the depth of the parent bounds that were contained. It can be used to precompute, cache, and then read information about a parent bound to improve performance while traversing. | ||
| A generalized cast function that can be used to implement intersection logic for custom shapes. This is used internally for [intersectsBox](#intersectsBox), [intersectsSphere](#intersectsSphere), and more. The function returns as soon as a triangle has been reported as intersected and returns `true` if a triangle has been intersected. The bounds are traversed in depth first order calling `traverseBoundsOrder`, `intersectsBoundsFunc`, `intersectsRange`, and `intersectsTriangle` for each node and using the results to determine when to end traversal. The `depth` value passed to callbacks indicates the depth of the bounds the provided box or triangle range belongs to unless the triangles are indicated to be `CONTAINED`, in which case depth is the depth of the parent bounds that were contained. The depth field can be used to precompute, cache to an array, and then read information about a parent bound to improve performance while traversing because nodes are traversed in a dpeth first order. The `triangleIndex` parameter specifies the index of the triangle in the index buffer. The three vertex indices can be computed as `triangleIndex * 3 + 0`, `triangleIndex * 3 + 1`, `triangleIndex * 3 + 2`. | ||
| `mesh` is the is the object this BVH is representing. | ||
| `traverseBoundsOrder` takes as an argument the axis aligned bounding box representing an internal node local to the BVH and returns a score (often distance) used to determine whether the left or right node should be traversed first. The shape with the lowest score is traversed first. | ||
| `callbacks` is a list of callback functions (defined below) used for traversing the tree. All functions except for `intersectsBounds` are optional. | ||
| `intersectsBounds` takes the axis aligned bounding box representing an internal node local to the bvh, whether or not the node is a leaf, the score calculated by `traverseBoundsOrder`, the node depth, and the node index (for use with the [refit](#refit) function) and returns a constant indicating whether or not the bounds is intersected or contained meaning traversal should continue. If `CONTAINED` is returned (meaning the bounds is entirely encapsulated by the shape) then an optimization is triggered allowing the range and / or triangle intersection callbacks to be run immediately rather than traversing the rest of the child bounds. | ||
| `traverseBoundsOrder` takes the axis aligned bounding box representing an internal node local to the bvh and returns a score (often distance) used to determine whether the left or right node should be traversed first. The shape with the lowest score is traversed first. | ||
| `intersectsBounds` takes the axis aligned bounding box representing an internal node local to the bvh, whether or not the node is a leaf, and the score calculated by `orderNodesFunc`, the node depth, and the node index (for use with the [refit](#refit) function) and returns a constant indicating whether or not the bounds is intersected or contained meaning traversal should continue. If `CONTAINED` is returned then and optimization is triggered allowing the range and / or triangle intersection callbacks to be run immediately rather than traversing the rest of the child bounds. | ||
| `intersectsRange` takes a triangle offset and count representing the number of triangles to be iterated over. 1 triangle from this range represents 3 values in the geometry's index buffer. If this function returns true then traversal is stopped and `intersectsTriangle` is not called if provided. | ||
| `intersectsTriangle` takes a triangle and the index buffer indices used by the triangle from the geometry and returns whether or not the triangle has been intersected with. If the triangle is reported to be intersected the traversal ends and the `shapecast` function completes. If multiple triangles need to be collected or intersected return false here and push results onto an array. `contained` is set to `true` if one of the parent bounds was marked as entirely contained in the `intersectsBoundsFunc` function. | ||
| `intersectsTriangle` takes a triangle and the triangle index and returns whether or not the triangle has been intersected. If the triangle is reported to be intersected the traversal ends and the `shapecast` function completes. If multiple triangles need to be collected or intersected return false here and push results onto an array. `contained` is set to `true` if one of the parent bounds was marked as entirely contained (returned `CONTAINED`) in the `intersectsBoundsFunc` function. | ||
| ### .refit | ||
| ```js | ||
| refit( | ||
| traversedNodeIndices : Array<Number> | Set<Number> = null, | ||
| endNodeIndices : Array<Number> | Set<Number> = null | ||
| ) : void | ||
| refit( nodeIndices : Array<Number> | Set<Number> = null ) : void | ||
| ``` | ||
| Refit the node bounds to the current triangle positions. This is quicker than regenerating a new BVH but will not be optimal after significant changes to the vertices. `traversedNodeIndices` is a set of node indices (provided by the [shapecast](#shapecast) function) that need to be refit including all internal nodes. `endNodeIndices` is the set of nodes that traversal ended at and that triangles need to be updated for. If neither index set is provided then the whole BVH is updated which is significantly slower than surgically updating the nodes that need to be updated. | ||
| Refit the node bounds to the current triangle positions. This is quicker than regenerating a new BVH but will not be optimal after significant changes to the vertices. `nodeIndices` is a set of node indices (provided by the [shapecast](#shapecast) function, see example snippet below) that need to be refit including all internal nodes. If one of a nodes children is also included in the set of node indices then only the included child bounds are traversed. If neither child index is included in the `nodeIndices` set, though, then it is assumed that every child below that node needs to be updated. | ||
@@ -418,7 +461,5 @@ Here's how to get the set of indices that need to be refit: | ||
| ```js | ||
| const traversedNodeIndices = new Set(); | ||
| const endNodeIndices = new Set(); | ||
| const nodeIndices = new Set(); | ||
| bvh.shapecast( | ||
| mesh, | ||
| { | ||
@@ -430,3 +471,3 @@ | ||
| traversedNodeIndices.add( nodeIndex ); | ||
| nodeIndices.add( nodeIndex ); | ||
| return INTERSECTED; | ||
@@ -442,5 +483,8 @@ | ||
| // collect triangles to update | ||
| endNodeIndices.add( nodeIndex ); | ||
| /* collect triangles / vertices to move */ | ||
| // the nodeIndex here will have always already been added to the set in the | ||
| // `intersectsBounds` callback. | ||
| nodeIndices.add( nodeIndex ); | ||
| } | ||
@@ -452,5 +496,6 @@ | ||
| // update the positions of the triangle vertices | ||
| /* update the positions of the triangle vertices */ | ||
| bvh.refit( traversedNodeIndices, endNodeIndices ); | ||
| // update the BVH bounds of just the bounds that need to be updated | ||
| bvh.refit( nodeIndices ); | ||
| ``` | ||
@@ -471,3 +516,3 @@ | ||
| ```js | ||
| roots : Array< ArrayBuffer > | ||
| roots : Array<ArrayBuffer> | ||
| ``` | ||
@@ -575,3 +620,3 @@ | ||
| The the `Raycaster` member `firstHitOnly` is set to true then the [.acceleratedRaycast](#acceleratedRaycast) function will call the [.raycastFirst](#raycastFirst) function to retrieve hits which is generally faster. | ||
| If the `Raycaster` member `firstHitOnly` is set to true then the [.acceleratedRaycast](#acceleratedRaycast) function will call the [.raycastFirst](#raycastFirst) function to retrieve hits which is generally faster. | ||
@@ -608,3 +653,3 @@ ### .computeBoundsTree | ||
| An accelerated raycast function with the same signature as `THREE.Mesh.raycast`. Uses the BVH for raycasting if it's available otherwise it falls back to the built-in approach. | ||
| An accelerated raycast function with the same signature as `THREE.Mesh.raycast`. Uses the BVH for raycasting if it's available otherwise it falls back to the built-in approach. The results of the function are designed to be identical to the results of the conventional `THREE.Mesh.raycast` results. | ||
@@ -623,2 +668,4 @@ If the raycaster object being used has a property `firstHitOnly` set to `true`, then the raycasting will terminate as soon as it finds the closest intersection to the ray's origin and return only that intersection. This is typically several times faster than searching for all intersections. | ||
| _See note in [Asyncronous Generation](#asynchronous-generation) use snippet._ | ||
| ### .running | ||
@@ -692,23 +739,50 @@ | ||
| ## Extra Functions | ||
| _NOTE The when using the [refit](#refit) function the `surfaceAreaScore` can be used to check how significantly the structure of the BVH has degraded and rebuild it if it has changed beyond some threshold ratio._ | ||
| List of functions stored in the `src/workers/` and are not exported via index.js because they require extra effort to integrate with some build processes. UMD variants of these functions are not provided. | ||
| ## Individual Functions | ||
| ### generateAsync | ||
| Functions exported individually not part of a class. | ||
| ### getTriangleHitPointInfo | ||
| ```js | ||
| generateAsync( geometry : BufferGeometry, options : Object ) : Promise<MeshBVH> | ||
| getTriangleHitPointInfo( | ||
| point: Vector3, | ||
| geometry : BufferGeometry, | ||
| triangleIndex: Number | ||
| target: Object | ||
| ) : Object | ||
| ``` | ||
| Generates a BVH for the given geometry in a WebWorker so it can be created asynchronously. A Promise is returned that resolves with the generated BVH. During the generation the `geometry.attributes.position` array and `geometry.index` array (if it exists) are transferred to the worker so the geometry will not be usable until the BVH generation is complete and the arrays are transferred back. | ||
| This function returns information of a point related to a geometry. It returns the `target` object or a new one if passed `undefined`: | ||
| ```js | ||
| target : { | ||
| face: { | ||
| a: Number, | ||
| b: Number, | ||
| c: Number, | ||
| materialIndex: Number, | ||
| normal: Vector3 | ||
| }, | ||
| uv: Vector2 | ||
| } | ||
| ``` | ||
| - `a`, `b`, `c`: Triangle indices | ||
| - `materialIndex`: Face material index or 0 if not available. | ||
| - `normal`: Face normal | ||
| - `uv`: UV coordinates. | ||
| This function can be used after a call to [closestPointPoint](#closestPointToPoint) or [closestPointToGeometry](#closestPointToGeometry) to retrieve more detailed result information. | ||
| ## Gotchas | ||
| - This is intended to be used with complicated, high-poly meshes. With less complex meshes, the benefits are negligible. | ||
| - When querying the MeshBVH directly all shapes and geometry are expected to be specified in the local frame of the BVH. When using three.js' built in raycasting system all results are implicitly transformed into world coordinates. | ||
| - A bounds tree can be generated for either an indexed or non-indexed `BufferGeometry`, but an index will | ||
| be produced and retained as a side effect of the construction. | ||
| - The bounds hierarchy is _not_ dynamic, so geometry that uses morph targets or skinning cannot be used. | ||
| - If the geometry is changed then a new bounds tree will need to be generated. | ||
| - The bounds hierarchy is _not_ dynamic, so geometry that uses morph targets or skinning cannot be used. Though if vertex positions are modified directly the [refit](#refit) function can be used to adjust the bounds tree. | ||
| - If the geometry is changed then a new bounds tree will need to be generated or refit. | ||
| - [InterleavedBufferAttributes](https://threejs.org/docs/#api/en/core/InterleavedBufferAttribute) are not supported with the geometry index buffer attribute. | ||
| - A separate bounds tree is generated for each [geometry group](https://threejs.org/docs/#api/en/objects/Group), which could result in poorer raycast performance on geometry with lots of groups. | ||
| - A separate bounds tree is generated for each [geometry group](https://threejs.org/docs/#api/en/objects/Group), which could result in less than optimal raycast performance on geometry with lots of groups. | ||
| - Due to errors related to floating point precision it is recommended that geometry be centered using `BufferGeometry.center()` before creating the BVH if the geometry is sufficiently large or off center so bounds tightly contain the geometry as much as possible. |
@@ -1,58 +0,6 @@ | ||
| import { Ray, Matrix4, Mesh } from 'three'; | ||
| import MeshBVH from './MeshBVH.js'; | ||
| import Visualizer from './MeshBVHVisualizer.js'; | ||
| import { CENTER, AVERAGE, SAH, NOT_INTERSECTED, INTERSECTED, CONTAINED } from './Constants.js'; | ||
| import { getBVHExtremes, estimateMemoryInBytes } from './Utils/Debug.js'; | ||
| import { MeshBVHDebug } from './MeshBVHDebug.js'; | ||
| const ray = new Ray(); | ||
| const tmpInverseMatrix = new Matrix4(); | ||
| const origMeshRaycastFunc = Mesh.prototype.raycast; | ||
| function acceleratedRaycast( raycaster, intersects ) { | ||
| if ( this.geometry.boundsTree ) { | ||
| if ( this.material === undefined ) return; | ||
| tmpInverseMatrix.copy( this.matrixWorld ).invert(); | ||
| ray.copy( raycaster.ray ).applyMatrix4( tmpInverseMatrix ); | ||
| if ( raycaster.firstHitOnly === true ) { | ||
| const res = this.geometry.boundsTree.raycastFirst( this, raycaster, ray ); | ||
| if ( res ) intersects.push( res ); | ||
| } else { | ||
| this.geometry.boundsTree.raycast( this, raycaster, ray, intersects ); | ||
| } | ||
| } else { | ||
| origMeshRaycastFunc.call( this, raycaster, intersects ); | ||
| } | ||
| } | ||
| function computeBoundsTree( options ) { | ||
| this.boundsTree = new MeshBVH( this, options ); | ||
| return this.boundsTree; | ||
| } | ||
| function disposeBoundsTree() { | ||
| this.boundsTree = null; | ||
| } | ||
| export { | ||
| MeshBVH, Visualizer, Visualizer as MeshBVHVisualizer, MeshBVHDebug, | ||
| acceleratedRaycast, computeBoundsTree, disposeBoundsTree, | ||
| CENTER, AVERAGE, SAH, NOT_INTERSECTED, INTERSECTED, CONTAINED, | ||
| estimateMemoryInBytes, getBVHExtremes | ||
| }; | ||
| export { MeshBVH } from './core/MeshBVH.js'; | ||
| export { MeshBVHVisualizer } from './objects/MeshBVHVisualizer.js'; | ||
| export { CENTER, AVERAGE, SAH, NOT_INTERSECTED, INTERSECTED, CONTAINED } from './core/Constants.js'; | ||
| export { getBVHExtremes, estimateMemoryInBytes, getJSONStructure, validateBounds } from './debug/Debug.js'; | ||
| export { acceleratedRaycast, computeBoundsTree, disposeBoundsTree } from './utils/ExtensionUtilities.js'; | ||
| export { getTriangleHitPointInfo } from './utils/TriangleUtilities.js'; |
@@ -5,3 +5,3 @@ import { | ||
| } from 'three'; | ||
| import MeshBVH from '../MeshBVH.js'; | ||
| import { MeshBVH } from '../core/MeshBVH.js'; | ||
@@ -23,3 +23,3 @@ global.onmessage = function ( { data } ) { | ||
| const bvh = new MeshBVH( geometry, options ); | ||
| const serialized = MeshBVH.serialize( bvh, geometry, false ); | ||
| const serialized = MeshBVH.serialize( bvh, { copyIndexBuffer: false } ); | ||
@@ -26,0 +26,0 @@ global.postMessage( { |
@@ -1,3 +0,3 @@ | ||
| import { Box3 } from 'three'; | ||
| import MeshBVH from '../MeshBVH.js'; | ||
| import { Box3, BufferAttribute } from 'three'; | ||
| import { MeshBVH } from '../core/MeshBVH.js'; | ||
@@ -38,3 +38,3 @@ export class GenerateMeshBVHWorker { | ||
| const bvh = MeshBVH.deserialize( serialized, geometry, false ); | ||
| const bvh = MeshBVH.deserialize( serialized, geometry, { setIndex: false } ); | ||
| const boundsOptions = Object.assign( { | ||
@@ -53,2 +53,7 @@ | ||
| } else { | ||
| const newIndex = new BufferAttribute( serialized.index, 1, false ); | ||
| geometry.setIndex( newIndex ); | ||
| } | ||
@@ -55,0 +60,0 @@ |
Sorry, the diff of this file is too big to display
Sorry, the diff of this file is not supported yet
Sorry, the diff of this file is not supported yet
Sorry, the diff of this file is not supported yet
New alerts
License Policy Violation
LicenseThis package is not allowed per your license policy. Review the package's license to ensure compliance.
Found 1 instance in 1 package
Fixed alerts
License Policy Violation
LicenseThis package is not allowed per your license policy. Review the package's license to ensure compliance.
Found 1 instance in 1 package
Improved metrics
- Total package byte prevSize
- increased by19.66%
885826
- Number of package files
- increased by7.14%
30
- Lines of code
- increased by19.1%
9497
- Number of lines in readme file
- increased by10.71%
765
No dependency changes