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.6.2 to 0.6.3
| { | ||
| "name": "three-mesh-bvh", | ||
| "version": "0.6.2", | ||
| "version": "0.6.3", | ||
| "description": "A BVH implementation to speed up raycasting against three.js meshes.", | ||
@@ -5,0 +5,0 @@ "module": "src/index.js", |
@@ -448,3 +448,3 @@ # three-mesh-bvh | ||
| traverseBoundsOrder : ( | ||
| boundsTraverseOrder : ( | ||
| box: Box3 | ||
@@ -482,7 +482,7 @@ ) => Number = null, | ||
| 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`. | ||
| 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 `boundsTraverseOrder`, `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`. | ||
| `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. | ||
| `boundsTraverseOrder` 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. | ||
| `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. | ||
| `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 `boundsTraverseOrder`, 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. | ||
@@ -489,0 +489,0 @@ `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. |
@@ -95,3 +95,3 @@ import { BufferGeometry, Vector3, Side, Material, Ray, Sphere, Matrix4, Color, | ||
| traverseBoundsOrder?: ( | ||
| boundsTraverseOrder?: ( | ||
| box: Box3 | ||
@@ -98,0 +98,0 @@ ) => number, |
@@ -5,6 +5,6 @@ import { Triangle, Vector3, Line3, Sphere, Plane } from 'three'; | ||
| const DIST_EPSILON = 1e-15; | ||
| const ZERO_EPSILON = 1e-15; | ||
| function isNearZero( value ) { | ||
| return Math.abs( value ) < DIST_EPSILON; | ||
| return Math.abs( value ) < ZERO_EPSILON; | ||
@@ -141,2 +141,3 @@ } | ||
| const cachedAxis = new Vector3(); | ||
| const dir = new Vector3(); | ||
| const dir1 = new Vector3(); | ||
@@ -148,3 +149,76 @@ const dir2 = new Vector3(); | ||
| const edge2 = new Line3(); | ||
| const tempPoint = new Vector3(); | ||
| function triIntersectPlane( tri, plane, targetEdge ) { | ||
| // find the edge that intersects the other triangle plane | ||
| const points = tri.points; | ||
| let count = 0; | ||
| let startPointIntersection = - 1; | ||
| for ( let i = 0; i < 3; i ++ ) { | ||
| const { start, end } = edge; | ||
| start.copy( points[ i ] ); | ||
| end.copy( points[ ( i + 1 ) % 3 ] ); | ||
| edge.delta( dir ); | ||
| const startIntersects = isNearZero( plane.distanceToPoint( start ) ); | ||
| if ( isNearZero( plane.normal.dot( dir ) ) && startIntersects ) { | ||
| // if the edge lies on the plane then take the line | ||
| targetEdge.copy( edge ); | ||
| count = 2; | ||
| break; | ||
| } | ||
| // check if the start point is near the plane because "intersectLine" is not robust to that case | ||
| const doesIntersect = plane.intersectLine( edge, tempPoint ); | ||
| if ( ! doesIntersect && startIntersects ) { | ||
| tempPoint.copy( start ); | ||
| } | ||
| // ignore the end point | ||
| if ( ( doesIntersect || startIntersects ) && ! isNearZero( tempPoint.distanceTo( end ) ) ) { | ||
| if ( count <= 1 ) { | ||
| // assign to the start or end point and save which index was snapped to | ||
| // the start point if necessary | ||
| const point = count === 1 ? targetEdge.start : targetEdge.end; | ||
| point.copy( tempPoint ); | ||
| if ( startIntersects ) { | ||
| startPointIntersection = count; | ||
| } | ||
| } else if ( count >= 2 ) { | ||
| // if we're here that means that there must have been one point that had | ||
| // snapped to the start point so replace it here | ||
| const point = startPointIntersection === 1 ? targetEdge.start : targetEdge.end; | ||
| point.copy( tempPoint ); | ||
| count = 2; | ||
| break; | ||
| } | ||
| count ++; | ||
| if ( count === 2 && startPointIntersection === - 1 ) { | ||
| break; | ||
| } | ||
| } | ||
| } | ||
| return count; | ||
| } | ||
| // TODO: If the triangles are coplanar and intersecting the target is nonsensical. It should at least | ||
@@ -241,48 +315,3 @@ // be a line contained by both triangles if not a different special case somehow represented in the return result. | ||
| // find the edge that intersects the other triangle plane | ||
| const points1 = this.points; | ||
| let found1 = false; | ||
| let count1 = 0; | ||
| for ( let i = 0; i < 3; i ++ ) { | ||
| const p = points1[ i ]; | ||
| const pNext = points1[ ( i + 1 ) % 3 ]; | ||
| edge.start.copy( p ); | ||
| edge.end.copy( pNext ); | ||
| edge.delta( dir1 ); | ||
| const targetPoint = found1 ? edge1.start : edge1.end; | ||
| const startIntersects = isNearZero( plane2.distanceToPoint( p ) ); | ||
| if ( isNearZero( plane2.normal.dot( dir1 ) ) && startIntersects ) { | ||
| // if the edge lies on the plane then take the line | ||
| edge1.copy( edge ); | ||
| count1 = 2; | ||
| break; | ||
| } | ||
| // check if the start point is near the plane because "intersectLine" is not robust to that case | ||
| const doesIntersect = plane2.intersectLine( edge, targetPoint ); | ||
| if ( ! doesIntersect && startIntersects ) { | ||
| targetPoint.copy( p ); | ||
| } | ||
| if ( ( doesIntersect || startIntersects ) && ! isNearZero( targetPoint.distanceTo( pNext ) ) ) { | ||
| count1 ++; | ||
| if ( found1 ) { | ||
| break; | ||
| } | ||
| found1 = true; | ||
| } | ||
| } | ||
| const count1 = triIntersectPlane( this, plane2, edge1 ); | ||
| if ( count1 === 1 && other.containsPoint( edge1.end ) ) { | ||
@@ -306,48 +335,3 @@ | ||
| // find the other triangles edge that intersects this plane | ||
| const points2 = other.points; | ||
| let found2 = false; | ||
| let count2 = 0; | ||
| for ( let i = 0; i < 3; i ++ ) { | ||
| const p = points2[ i ]; | ||
| const pNext = points2[ ( i + 1 ) % 3 ]; | ||
| edge.start.copy( p ); | ||
| edge.end.copy( pNext ); | ||
| edge.delta( dir2 ); | ||
| const targetPoint = found2 ? edge2.start : edge2.end; | ||
| const startIntersects = isNearZero( plane1.distanceToPoint( p ) ); | ||
| if ( isNearZero( plane1.normal.dot( dir2 ) ) && startIntersects ) { | ||
| // if the edge lies on the plane then take the line | ||
| edge2.copy( edge ); | ||
| count2 = 2; | ||
| break; | ||
| } | ||
| // check if the start point is near the plane because "intersectLine" is not robust to that case | ||
| const doesIntersect = plane1.intersectLine( edge, targetPoint ); | ||
| if ( ! doesIntersect && startIntersects ) { | ||
| targetPoint.copy( p ); | ||
| } | ||
| if ( ( doesIntersect || startIntersects ) && ! isNearZero( targetPoint.distanceTo( pNext ) ) ) { | ||
| count2 ++; | ||
| if ( found2 ) { | ||
| break; | ||
| } | ||
| found2 = true; | ||
| } | ||
| } | ||
| const count2 = triIntersectPlane( other, plane1, edge2 ); | ||
| if ( count2 === 1 && this.containsPoint( edge2.end ) ) { | ||
@@ -354,0 +338,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
Worsened metrics
- Total package byte prevSize
- decreased by-0.16%
1179010
- Lines of code
- decreased by-0.18%
13162
No dependency changes