three-mesh-bvh - npm Package Compare versions

Comparing version 0.5.17 to 0.5.18

package.json

 {
   "name": "three-mesh-bvh",
-  "version": "0.5.17",
+  "version": "0.5.18",
   "description": "A BVH implementation to speed up raycasting against three.js meshes.",
@@ -76,5 +76,5 @@ "module": "src/index.js",
     "stats.js": "^0.17.0",
-    "three": "^0.145.0",
+    "three": "^0.146.0",
     "typescript": "^4.4.3"
   }
 }

README.md

@@ -28,2 +28,4 @@ # three-mesh-bvh
 
+[SDF generation](https://gkjohnson.github.io/three-mesh-bvh/example/bundle/sdfGeneration.html)
+
 [WebWorker generation](https://gkjohnson.github.io/three-mesh-bvh/example/bundle/asyncGenerate.html)
@@ -65,3 +67,2 @@
 
-
 **External Projects**
@@ -68,0 +69,0 @@

src/core/buildFunctions.js

@@ -0,0 +0,0 @@ import { BufferAttribute } from 'three';

src/core/bvhcast.js

@@ -0,0 +0,0 @@ /**

src/core/castFunctions.js

@@ -0,0 +0,0 @@ import { Box3, Vector3, Matrix4 } from 'three';

src/core/Constants.js

@@ -0,0 +0,0 @@ // Split strategy constants

src/core/MeshBVH.js

@@ -0,0 +0,0 @@ import { Vector3, BufferAttribute, Box3, FrontSide, Matrix4 } from 'three';

src/core/MeshBVHNode.js

@@ -0,0 +0,0 @@ export class MeshBVHNode {

src/core/nodeBufferFunctions.js

@@ -0,0 +0,0 @@ export function IS_LEAF( n16, uint16Array ) {

src/debug/Debug.js

@@ -0,0 +0,0 @@ import { Box3, Vector3 } from 'three';

src/gpu/MeshBVHUniformStruct.js

@@ -0,0 +0,0 @@ import {

src/gpu/shaderFunctions.js

@@ -0,1 +1,4 @@
+// Note that a struct cannot be used for the hit record including faceIndices, faceNormal, barycoord,
+// side, and dist because on some mobile GPUS (such as Adreno) numbers are afforded less precision specifically
+// when in a struct leading to inaccurate hit results. See KhronosGroup/WebGL#3351 for more details.
 export const shaderStructs = /* glsl */`
@@ -19,6 +22,2 @@ #ifndef TRI_INTERSECT_EPSILON
 };
-
-// Note that a struct cannot be used for the hit record including faceIndices, faceNormal, barycoord,
-// side, and dist because on some mobile GPUS (such as Adreno) numbers are afforded less precision specifically
-// when in a struct leading to inaccurate hit results. See KhronosGroup/WebGL#3351 for more details.
 `;
@@ -28,2 +27,3 @@
 
+// Utilities
 uvec4 uTexelFetch1D( usampler2D tex, uint index ) {
@@ -95,2 +95,3 @@
 
+// Raycasting
 float intersectsBounds( vec3 rayOrigin, vec3 rayDirection, vec3 boundsMin, vec3 boundsMax ) {
@@ -278,3 +279,179 @@
 }
+`;
 
+// Distance to Point
+export const shaderDistanceFunction = /* glsl */`
+
+float dot2( in vec3 v ) {
+
+	return dot( v, v );
+
+}
+
+
+// https://www.shadertoy.com/view/ttfGWl
+vec3 closestPointToTriangle( vec3 p, vec3 v0, vec3 v1, vec3 v2, out vec3 barycoord ) {
+
+    vec3 v10 = v1 - v0;
+    vec3 v21 = v2 - v1;
+    vec3 v02 = v0 - v2;
+
+	vec3 p0 = p - v0;
+	vec3 p1 = p - v1;
+	vec3 p2 = p - v2;
+
+    vec3 nor = cross( v10, v02 );
+
+    // method 2, in barycentric space
+    vec3  q = cross( nor, p0 );
+    float d = 1.0 / dot2( nor );
+    float u = d * dot( q, v02 );
+    float v = d * dot( q, v10 );
+    float w = 1.0 - u - v;
+
+	if( u < 0.0 ) {
+
+		w = clamp( dot( p2, v02 ) / dot2( v02 ), 0.0, 1.0 );
+		u = 0.0;
+		v = 1.0 - w;
+
+	} else if( v < 0.0 ) {
+
+		u = clamp( dot( p0, v10 ) / dot2( v10 ), 0.0, 1.0 );
+		v = 0.0;
+		w = 1.0 - u;
+
+	} else if( w < 0.0 ) {
+
+		v = clamp( dot( p1, v21 ) / dot2( v21 ), 0.0, 1.0 );
+		w = 0.0;
+		u = 1.0-v;
+
+	}
+
+	barycoord = vec3( u, v, w );
+    return u * v1 + v * v2 + w * v0;
+
+}
+
+float distanceToTriangles(
+	BVH bvh, vec3 point, uint offset, uint count, float closestDistanceSquared,
+
+	out uvec4 faceIndices, out vec3 faceNormal, out vec3 barycoord, out float side, out vec3 outPoint
+) {
+
+	bool found = false;
+	uvec3 localIndices;
+	vec3 localBarycoord;
+	vec3 localNormal;
+	for ( uint i = offset, l = offset + count; i < l; i ++ ) {
+
+		uvec3 indices = uTexelFetch1D( bvh.index, i ).xyz;
+		vec3 a = texelFetch1D( bvh.position, indices.x ).rgb;
+		vec3 b = texelFetch1D( bvh.position, indices.y ).rgb;
+		vec3 c = texelFetch1D( bvh.position, indices.z ).rgb;
+
+		// get the closest point and barycoord
+		vec3 closestPoint = closestPointToTriangle( point, a, b, c, localBarycoord );
+		vec3 delta = point - closestPoint;
+		float sqDist = dot2( delta );
+		if ( sqDist < closestDistanceSquared ) {
+
+			// set the output results
+			closestDistanceSquared = sqDist;
+			faceIndices = uvec4( indices.xyz, i );
+			faceNormal = normalize( cross( a - b, b - c ) );
+			barycoord = localBarycoord;
+			outPoint = closestPoint;
+			side = sign( dot( faceNormal, delta ) );
+
+		}
+
+	}
+
+	return closestDistanceSquared;
+
+}
+
+float distanceSqToBounds( vec3 point, vec3 boundsMin, vec3 boundsMax ) {
+
+	vec3 clampedPoint = clamp( point, boundsMin, boundsMax );
+	vec3 delta = point - clampedPoint;
+	return dot( delta, delta );
+
+}
+
+float distanceSqToBVHNodeBoundsPoint( vec3 point, BVH bvh, uint currNodeIndex ) {
+
+	vec3 boundsMin = texelFetch1D( bvh.bvhBounds, currNodeIndex * 2u + 0u ).xyz;
+	vec3 boundsMax = texelFetch1D( bvh.bvhBounds, currNodeIndex * 2u + 1u ).xyz;
+	return distanceSqToBounds( point, boundsMin, boundsMax );
+
+}
+
+float bvhClosestPointToPoint(
+	BVH bvh, vec3 point,
+
+	// output variables
+	out uvec4 faceIndices, out vec3 faceNormal, out vec3 barycoord,
+	out float side, out vec3 outPoint
+ ) {
+
+	// stack needs to be twice as long as the deepest tree we expect because
+	// we push both the left and right child onto the stack every traversal
+	int ptr = 0;
+	uint stack[ 60 ];
+	stack[ 0 ] = 0u;
+	float closestDistanceSquared = pow( 100000.0, 2.0 );
+	bool found = false;
+	while ( ptr > - 1 && ptr < 60 ) {
+
+		uint currNodeIndex = stack[ ptr ];
+		ptr --;
+
+		// check if we intersect the current bounds
+		float boundsHitDistance = distanceSqToBVHNodeBoundsPoint( point, bvh, currNodeIndex );
+		if ( boundsHitDistance > closestDistanceSquared ) {
+
+			continue;
+
+		}
+
+		uvec2 boundsInfo = uTexelFetch1D( bvh.bvhContents, currNodeIndex ).xy;
+		bool isLeaf = bool( boundsInfo.x & 0xffff0000u );
+		if ( isLeaf ) {
+
+			uint count = boundsInfo.x & 0x0000ffffu;
+			uint offset = boundsInfo.y;
+			closestDistanceSquared = distanceToTriangles(
+				bvh, point, offset, count, closestDistanceSquared,
+
+				// outputs
+				faceIndices, faceNormal, barycoord, side, outPoint
+			);
+
+		} else {
+
+			uint leftIndex = currNodeIndex + 1u;
+			uint splitAxis = boundsInfo.x & 0x0000ffffu;
+			uint rightIndex = boundsInfo.y;
+			bool leftToRight = distanceSqToBVHNodeBoundsPoint( point, bvh, leftIndex ) < distanceSqToBVHNodeBoundsPoint( point, bvh, rightIndex );//rayDirection[ splitAxis ] >= 0.0;
+			uint c1 = leftToRight ? leftIndex : rightIndex;
+			uint c2 = leftToRight ? rightIndex : leftIndex;
+
+			// set c2 in the stack so we traverse it later. We need to keep track of a pointer in
+			// the stack while we traverse. The second pointer added is the one that will be
+			// traversed first
+			ptr ++;
+			stack[ ptr ] = c2;
+			ptr ++;
+			stack[ ptr ] = c1;
+
+		}
+
+	}
+
+	return sqrt( closestDistanceSquared );
+
+}
 `;

src/gpu/VertexAttributeTexture.js

@@ -0,0 +0,0 @@ import {

src/index.d.ts

@@ -0,0 +0,0 @@ import { BufferGeometry, Vector3, Side, Material, Ray, Sphere, Matrix4, Color,

src/index.js

@@ -0,0 +0,0 @@ export { MeshBVH } from './core/MeshBVH.js';

src/math/ExtendedTriangle.js

@@ -274,3 +274,3 @@ import { Triangle, Vector3, Line3, Sphere, Plane } from 'three';
 
-			if ( count1 === 1 && this.containsPoint( edge1.end ) ) {
+			if ( count1 === 1 && other.containsPoint( edge1.end ) ) {
 
@@ -277,0 +277,0 @@ if ( target ) {

src/math/MathUtilities.js

@@ -0,0 +0,0 @@ import { Vector3, Vector2, Plane, Line3 } from 'three';

src/math/OrientedBox.js

@@ -0,0 +0,0 @@ import { Vector3, Matrix4, Line3 } from 'three';

src/math/SeparatingAxisBounds.js

@@ -0,0 +0,0 @@ import { Vector3 } from 'three';

src/objects/MeshBVHVisualizer.js

@@ -0,0 +0,0 @@ import { LineBasicMaterial, BufferAttribute, Box3, Group, MeshBasicMaterial, Object3D, BufferGeometry } from 'three';

src/utils/ArrayBoxUtilities.js

@@ -0,0 +0,0 @@ export function arrayToBox( nodeIndex32, array, target ) {

src/utils/ExtensionUtilities.js

@@ -0,0 +0,0 @@ import { Ray, Matrix4, Mesh } from 'three';

src/utils/GeometryRayIntersectUtilities.js

@@ -0,0 +0,0 @@ import { intersectTri } from './ThreeRayIntersectUtilities.js';

src/utils/PrimitivePool.js

@@ -0,0 +0,0 @@ export class PrimitivePool {

src/utils/StaticGeometryGenerator.js

@@ -333,3 +333,3 @@ import { BufferAttribute, BufferGeometry, Vector3, Vector4, Matrix4, Matrix3 } from 'three';
 		this.applyWorldTransforms = true;
-		this.attributes = [ 'position', 'normal', 'tangent', 'uv', 'uv2' ];
+		this.attributes = [ 'position', 'normal', 'color', 'tangent', 'uv', 'uv2' ];
 		this._intermediateGeometry = new Array( finalMeshes.length ).fill().map( () => new BufferGeometry() );
@@ -336,0 +336,0 @@

src/utils/ThreeRayIntersectUtilities.js

@@ -0,0 +0,0 @@ import { Vector3, Vector2, Triangle, DoubleSide, BackSide } from 'three';

src/utils/TriangleUtilities.js

@@ -0,0 +0,0 @@

src/workers/generateAsync.worker.js

@@ -0,0 +0,0 @@ import {

New alerts

License Policy Violation

License

This 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

License

This package is not allowed per your license policy. Review the package's license to ensure compliance.

Found 1 instance in 1 package

Improved metrics

Lines of code

12850

increased by3.06%

Number of lines in readme file

1090

increased by0.09%

Worsened metrics

Total package byte prevSize

1149263

decreased by-1.65%

No dependency changes