Hugging Face's logo

Spaces:
SimWorld-AI
/
industrial-harbor-viewer
Running

App Files Community
industrial-harbor-viewer / node_modules /three-mesh-bvh /src /math /ExtendedTriangle.js
KoeYe's picture
KoeYe
Add viewer app, scene data, and three.js runtime
b797337 verified
Raw History Blame Contribute Delete
20.4 kB
/** @import { Sphere } from 'three' */
import { Triangle, Vector3, Vector2, Line3, Plane } from 'three';
import { SeparatingAxisBounds } from './SeparatingAxisBounds.js';
import { closestPointsSegmentToSegment, sphereIntersectTriangle } from './MathUtilities.js';
const componentKeys = [ 'x', 'y', 'z' ];
const ZERO_EPSILON = 1e-15;
const ZERO_EPSILON_SQR = ZERO_EPSILON * ZERO_EPSILON;
function isNearZero( value ) {
return Math.abs( value ) < ZERO_EPSILON;
}
/**
* An extended version of three.js' Triangle class. A variety of derivative values are cached on
* the object to accelerate the intersection functions. `.needsUpdate` must be set to true when
* modifying the triangle parameters.
* @extends Triangle
*/
export class ExtendedTriangle extends Triangle {
constructor( ...args ) {
super( ...args );
this.isExtendedTriangle = true;
this.satAxes = new Array( 4 ).fill().map( () => new Vector3() );
this.satBounds = new Array( 4 ).fill().map( () => new SeparatingAxisBounds() );
this.points = [ this.a, this.b, this.c ];
this.plane = new Plane();
this.isDegenerateIntoSegment = false;
this.isDegenerateIntoPoint = false;
this.degenerateSegment = new Line3();
/**
* Indicates that the triangle fields have changed so cached variables to accelerate other
* function execution can be updated. Must be set to true after modifying the triangle
* `a`, `b`, `c` fields.
* @type {boolean}
*/
this.needsUpdate = true;
}
/**
* Returns whether the triangle intersects the given sphere.
* @param {Sphere} sphere
* @returns {boolean}
*/
intersectsSphere( sphere ) {
return sphereIntersectTriangle( sphere, this );
}
update() {
const a = this.a;
const b = this.b;
const c = this.c;
const points = this.points;
const satAxes = this.satAxes;
const satBounds = this.satBounds;
const axis0 = satAxes[ 0 ];
const sab0 = satBounds[ 0 ];
this.getNormal( axis0 );
sab0.setFromPoints( axis0, points );
const axis1 = satAxes[ 1 ];
const sab1 = satBounds[ 1 ];
axis1.subVectors( a, b );
sab1.setFromPoints( axis1, points );
const axis2 = satAxes[ 2 ];
const sab2 = satBounds[ 2 ];
axis2.subVectors( b, c );
sab2.setFromPoints( axis2, points );
const axis3 = satAxes[ 3 ];
const sab3 = satBounds[ 3 ];
axis3.subVectors( c, a );
sab3.setFromPoints( axis3, points );
const lengthAB = axis1.length();
const lengthBC = axis2.length();
const lengthCA = axis3.length();
this.isDegenerateIntoPoint = false;
this.isDegenerateIntoSegment = false;
if ( lengthAB < ZERO_EPSILON ) {
if ( lengthBC < ZERO_EPSILON || lengthCA < ZERO_EPSILON ) {
this.isDegenerateIntoPoint = true;
} else {
this.isDegenerateIntoSegment = true;
this.degenerateSegment.start.copy( a );
this.degenerateSegment.end.copy( c );
}
} else if ( lengthBC < ZERO_EPSILON ) {
if ( lengthCA < ZERO_EPSILON ) {
this.isDegenerateIntoPoint = true;
} else {
this.isDegenerateIntoSegment = true;
this.degenerateSegment.start.copy( b );
this.degenerateSegment.end.copy( a );
}
} else if ( lengthCA < ZERO_EPSILON ) {
this.isDegenerateIntoSegment = true;
this.degenerateSegment.start.copy( c );
this.degenerateSegment.end.copy( b );
}
this.plane.setFromNormalAndCoplanarPoint( axis0, a );
this.needsUpdate = false;
}
}
/**
* Returns the distance to the provided line segment. `target1` and `target2` are set to the
* closest points on the triangle and segment respectively.
* @function
* @param {Line3} segment
* @param {Vector3} [target1]
* @param {Vector3} [target2]
* @returns {number}
*/
ExtendedTriangle.prototype.closestPointToSegment = ( function () {
const point1 = /* @__PURE__ */ new Vector3();
const point2 = /* @__PURE__ */ new Vector3();
const edge = /* @__PURE__ */ new Line3();
return function distanceToSegment( segment, target1 = null, target2 = null ) {
const { start, end } = segment;
const points = this.points;
let distSq;
let closestDistanceSq = Infinity;
// check the triangle edges
for ( let i = 0; i < 3; i ++ ) {
const nexti = ( i + 1 ) % 3;
edge.start.copy( points[ i ] );
edge.end.copy( points[ nexti ] );
closestPointsSegmentToSegment( edge, segment, point1, point2 );
distSq = point1.distanceToSquared( point2 );
if ( distSq < closestDistanceSq ) {
closestDistanceSq = distSq;
if ( target1 ) target1.copy( point1 );
if ( target2 ) target2.copy( point2 );
}
}
// check end points
this.closestPointToPoint( start, point1 );
distSq = start.distanceToSquared( point1 );
if ( distSq < closestDistanceSq ) {
closestDistanceSq = distSq;
if ( target1 ) target1.copy( point1 );
if ( target2 ) target2.copy( start );
}
this.closestPointToPoint( end, point1 );
distSq = end.distanceToSquared( point1 );
if ( distSq < closestDistanceSq ) {
closestDistanceSq = distSq;
if ( target1 ) target1.copy( point1 );
if ( target2 ) target2.copy( end );
}
return Math.sqrt( closestDistanceSq );
};
} )();
/**
* Returns whether the triangles intersect. `target` is set to the line segment representing
* the intersection.
* @function
* @param {Triangle} other
* @param {Line3} [target]
* @param {boolean} [suppressLog=false]
* @returns {boolean}
*/
ExtendedTriangle.prototype.intersectsTriangle = ( function () {
const saTri2 = /* @__PURE__ */ new ExtendedTriangle();
const cachedSatBounds = /* @__PURE__ */ new SeparatingAxisBounds();
const cachedSatBounds2 = /* @__PURE__ */ new SeparatingAxisBounds();
const tmpVec = /* @__PURE__ */ new Vector3();
const dir1 = /* @__PURE__ */ new Vector3();
const dir2 = /* @__PURE__ */ new Vector3();
const tempDir = /* @__PURE__ */ new Vector3();
const edge1 = /* @__PURE__ */ new Line3();
const edge2 = /* @__PURE__ */ new Line3();
const tempPoint = /* @__PURE__ */ new Vector3();
const bounds1 = /* @__PURE__ */ new Vector2();
const bounds2 = /* @__PURE__ */ new Vector2();
function coplanarIntersectsTriangle( self, other, target, suppressLog ) {
// Perform separating axis intersection test only for coplanar triangles
// There should be at least one non-degenerate triangle when calling this
// Otherwise we won't know the plane normal
const planeNormal = tmpVec;
if ( ! self.isDegenerateIntoPoint && ! self.isDegenerateIntoSegment ) {
planeNormal.copy( self.plane.normal );
} else {
planeNormal.copy( other.plane.normal );
}
const satBounds1 = self.satBounds;
const satAxes1 = self.satAxes;
for ( let i = 1; i < 4; i ++ ) {
const sb = satBounds1[ i ];
const sa = satAxes1[ i ];
cachedSatBounds.setFromPoints( sa, other.points );
if ( sb.isSeparated( cachedSatBounds ) ) return false;
tempDir.copy( planeNormal ).cross( sa );
cachedSatBounds.setFromPoints( tempDir, self.points );
cachedSatBounds2.setFromPoints( tempDir, other.points );
if ( cachedSatBounds.isSeparated( cachedSatBounds2 ) ) return false;
}
const satBounds2 = other.satBounds;
const satAxes2 = other.satAxes;
for ( let i = 1; i < 4; i ++ ) {
const sb = satBounds2[ i ];
const sa = satAxes2[ i ];
cachedSatBounds.setFromPoints( sa, self.points );
if ( sb.isSeparated( cachedSatBounds ) ) return false;
tempDir.crossVectors( planeNormal, sa );
cachedSatBounds.setFromPoints( tempDir, self.points );
cachedSatBounds2.setFromPoints( tempDir, other.points );
if ( cachedSatBounds.isSeparated( cachedSatBounds2 ) ) return false;
}
if ( target ) {
// TODO find two points that intersect on the edges and make that the result
if ( ! suppressLog ) {
console.warn( 'ExtendedTriangle.intersectsTriangle: Triangles are coplanar which does not support an output edge. Setting edge to 0, 0, 0.' );
}
target.start.set( 0, 0, 0 );
target.end.set( 0, 0, 0 );
}
return true;
}
function findSingleBounds( a, b, c, aProj, bProj, cProj, aDist, bDist, cDist, bounds, edge ) {
let t = aDist / ( aDist - bDist );
bounds.x = aProj + ( bProj - aProj ) * t;
edge.start.subVectors( b, a ).multiplyScalar( t ).add( a );
t = aDist / ( aDist - cDist );
bounds.y = aProj + ( cProj - aProj ) * t;
edge.end.subVectors( c, a ).multiplyScalar( t ).add( a );
}
/**
* Calculates intersection segment of a triangle with intersection line.
* Intersection line is snapped to its biggest component.
* And triangle points are passed as a projection on that component.
* @returns {boolean} whether this is a coplanar case or not
*/
function findIntersectionLineBounds( self, aProj, bProj, cProj, abDist, acDist, aDist, bDist, cDist, bounds, edge ) {
if ( abDist > 0 ) {
// then bcDist < 0
findSingleBounds( self.c, self.a, self.b, cProj, aProj, bProj, cDist, aDist, bDist, bounds, edge );
} else if ( acDist > 0 ) {
findSingleBounds( self.b, self.a, self.c, bProj, aProj, cProj, bDist, aDist, cDist, bounds, edge );
} else if ( bDist * cDist > 0 || aDist != 0 ) {
findSingleBounds( self.a, self.b, self.c, aProj, bProj, cProj, aDist, bDist, cDist, bounds, edge );
} else if ( bDist != 0 ) {
findSingleBounds( self.b, self.a, self.c, bProj, aProj, cProj, bDist, aDist, cDist, bounds, edge );
} else if ( cDist != 0 ) {
findSingleBounds( self.c, self.a, self.b, cProj, aProj, bProj, cDist, aDist, bDist, bounds, edge );
} else {
return true;
}
return false;
}
function intersectTriangleSegment( triangle, degenerateTriangle, target, suppressLog ) {
const segment = degenerateTriangle.degenerateSegment;
const startDist = triangle.plane.distanceToPoint( segment.start );
const endDist = triangle.plane.distanceToPoint( segment.end );
if ( isNearZero( startDist ) ) {
if ( isNearZero( endDist ) ) {
return coplanarIntersectsTriangle( triangle, degenerateTriangle, target, suppressLog );
} else {
// Is this fine to modify target even if there might be no intersection?
if ( target ) {
target.start.copy( segment.start );
target.end.copy( segment.start );
}
return triangle.containsPoint( segment.start );
}
} else if ( isNearZero( endDist ) ) {
if ( target ) {
target.start.copy( segment.end );
target.end.copy( segment.end );
}
return triangle.containsPoint( segment.end );
} else {
if ( triangle.plane.intersectLine( segment, tmpVec ) != null ) {
if ( target ) {
target.start.copy( tmpVec );
target.end.copy( tmpVec );
}
return triangle.containsPoint( tmpVec );
} else {
return false;
}
}
}
function intersectTrianglePoint( triangle, degenerateTriangle, target ) {
const point = degenerateTriangle.a;
if ( isNearZero( triangle.plane.distanceToPoint( point ) ) && triangle.containsPoint( point ) ) {
if ( target ) {
target.start.copy( point );
target.end.copy( point );
}
return true;
} else {
return false;
}
}
function intersectSegmentPoint( segmentTri, pointTri, target ) {
const segment = segmentTri.degenerateSegment;
const point = pointTri.a;
segment.closestPointToPoint( point, true, tmpVec );
if ( point.distanceToSquared( tmpVec ) < ZERO_EPSILON_SQR ) {
if ( target ) {
target.start.copy( point );
target.end.copy( point );
}
return true;
} else {
return false;
}
}
function handleDegenerateCases( self, other, target, suppressLog ) {
if ( self.isDegenerateIntoSegment ) {
if ( other.isDegenerateIntoSegment ) {
// TODO: replace with Line.distanceSqToLine3 after r179
const segment1 = self.degenerateSegment;
const segment2 = other.degenerateSegment;
const delta1 = dir1;
const delta2 = dir2;
segment1.delta( delta1 );
segment2.delta( delta2 );
const startDelta = tmpVec.subVectors( segment2.start, segment1.start );
const denom = delta1.x * delta2.y - delta1.y * delta2.x;
if ( isNearZero( denom ) ) {
return false;
}
const t = ( startDelta.x * delta2.y - startDelta.y * delta2.x ) / denom;
const u = - ( delta1.x * startDelta.y - delta1.y * startDelta.x ) / denom;
if ( t < 0 || t > 1 || u < 0 || u > 1 ) {
return false;
}
const z1 = segment1.start.z + delta1.z * t;
const z2 = segment2.start.z + delta2.z * u;
if ( isNearZero( z1 - z2 ) ) {
if ( target ) {
target.start.copy( segment1.start ).addScaledVector( delta1, t );
target.end.copy( segment1.start ).addScaledVector( delta1, t );
}
return true;
} else {
return false;
}
} else if ( other.isDegenerateIntoPoint ) {
return intersectSegmentPoint( self, other, target );
} else {
return intersectTriangleSegment( other, self, target, suppressLog );
}
} else if ( self.isDegenerateIntoPoint ) {
if ( other.isDegenerateIntoPoint ) {
if ( other.a.distanceToSquared( self.a ) < ZERO_EPSILON_SQR ) {
if ( target ) {
target.start.copy( self.a );
target.end.copy( self.a );
}
return true;
} else {
return false;
}
} else if ( other.isDegenerateIntoSegment ) {
return intersectSegmentPoint( other, self, target );
} else {
return intersectTrianglePoint( other, self, target );
}
} else {
if ( other.isDegenerateIntoPoint ) {
return intersectTrianglePoint( self, other, target );
} else if ( other.isDegenerateIntoSegment ) {
return intersectTriangleSegment( self, other, target, suppressLog );
} /* else this is a general triangle-traingle case, so return undefined */
}
}
/* TODO: If the triangles are coplanar and intersecting the target is nonsensical. It should at least
* be a line contained by both triangles if not a different special case somehow represented in the return result.
*
* General triangle intersection code is based on Moller's algorithm from here: https://web.stanford.edu/class/cs277/resources/papers/Moller1997b.pdf
* Reference implementation from here: https://github.com/erich666/jgt-code/blob/master/Volume_08/Number_1/Shen2003/tri_tri_test/include/Moller97.c#L570
* All degeneracies are handled before the general algorithm.
* Coplanar check is different from Moller's and based on SAT tests.
*/
return function intersectsTriangle( other, target = null, suppressLog = false ) {
if ( this.needsUpdate ) {
this.update();
}
if ( ! other.isExtendedTriangle ) {
saTri2.copy( other );
saTri2.update();
other = saTri2;
} else if ( other.needsUpdate ) {
other.update();
}
const res = handleDegenerateCases( this, other, target, suppressLog );
if ( res !== undefined ) {
return res;
}
const plane1 = this.plane;
const plane2 = other.plane;
let a1Dist = plane2.distanceToPoint( this.a );
let b1Dist = plane2.distanceToPoint( this.b );
let c1Dist = plane2.distanceToPoint( this.c );
if ( isNearZero( a1Dist ) )
a1Dist = 0;
if ( isNearZero( b1Dist ) )
b1Dist = 0;
if ( isNearZero( c1Dist ) )
c1Dist = 0;
const a1b1Dist = a1Dist * b1Dist;
const a1c1Dist = a1Dist * c1Dist;
if ( a1b1Dist > 0 && a1c1Dist > 0 ) {
return false;
}
let a2Dist = plane1.distanceToPoint( other.a );
let b2Dist = plane1.distanceToPoint( other.b );
let c2Dist = plane1.distanceToPoint( other.c );
if ( isNearZero( a2Dist ) )
a2Dist = 0;
if ( isNearZero( b2Dist ) )
b2Dist = 0;
if ( isNearZero( c2Dist ) )
c2Dist = 0;
const a2b2Dist = a2Dist * b2Dist;
const a2c2Dist = a2Dist * c2Dist;
if ( a2b2Dist > 0 && a2c2Dist > 0 ) {
return false;
}
dir1.copy( plane1.normal );
dir2.copy( plane2.normal );
const intersectionLine = dir1.cross( dir2 );
let componentIndex = 0;
let maxComponent = Math.abs( intersectionLine.x );
const comp1 = Math.abs( intersectionLine.y );
if ( comp1 > maxComponent ) {
maxComponent = comp1;
componentIndex = 1;
}
const comp2 = Math.abs( intersectionLine.z );
if ( comp2 > maxComponent ) {
componentIndex = 2;
}
const key = componentKeys[ componentIndex ];
const a1Proj = this.a[ key ];
const b1Proj = this.b[ key ];
const c1Proj = this.c[ key ];
const a2Proj = other.a[ key ];
const b2Proj = other.b[ key ];
const c2Proj = other.c[ key ];
if ( findIntersectionLineBounds( this, a1Proj, b1Proj, c1Proj, a1b1Dist, a1c1Dist, a1Dist, b1Dist, c1Dist, bounds1, edge1 ) ) {
return coplanarIntersectsTriangle( this, other, target, suppressLog );
}
if ( findIntersectionLineBounds( other, a2Proj, b2Proj, c2Proj, a2b2Dist, a2c2Dist, a2Dist, b2Dist, c2Dist, bounds2, edge2 ) ) {
return coplanarIntersectsTriangle( this, other, target, suppressLog );
}
if ( bounds1.y < bounds1.x ) {
const tmp = bounds1.y;
bounds1.y = bounds1.x;
bounds1.x = tmp;
tempPoint.copy( edge1.start );
edge1.start.copy( edge1.end );
edge1.end.copy( tempPoint );
}
if ( bounds2.y < bounds2.x ) {
const tmp = bounds2.y;
bounds2.y = bounds2.x;
bounds2.x = tmp;
tempPoint.copy( edge2.start );
edge2.start.copy( edge2.end );
edge2.end.copy( tempPoint );
}
if ( bounds1.y < bounds2.x || bounds2.y < bounds1.x ) {
return false;
}
if ( target ) {
if ( bounds2.x > bounds1.x ) {
target.start.copy( edge2.start );
} else {
target.start.copy( edge1.start );
}
if ( bounds2.y < bounds1.y ) {
target.end.copy( edge2.end );
} else {
target.end.copy( edge1.end );
}
}
return true;
};
} )();
/**
* Returns the distance to the provided point.
* @function
* @param {Vector3} point
* @returns {number}
*/
ExtendedTriangle.prototype.distanceToPoint = ( function () {
const target = /* @__PURE__ */ new Vector3();
return function distanceToPoint( point ) {
this.closestPointToPoint( point, target );
return point.distanceTo( target );
};
} )();
/**
* Returns the distance to the provided triangle.
* @function
* @param {Triangle} other
* @param {Vector3} [target1]
* @param {Vector3} [target2]
* @returns {number}
*/
ExtendedTriangle.prototype.distanceToTriangle = ( function () {
const point = /* @__PURE__ */ new Vector3();
const point2 = /* @__PURE__ */ new Vector3();
const cornerFields = [ 'a', 'b', 'c' ];
const line1 = /* @__PURE__ */ new Line3();
const line2 = /* @__PURE__ */ new Line3();
return function distanceToTriangle( other, target1 = null, target2 = null ) {
const lineTarget = target1 || target2 ? line1 : null;
// `intersectsTriangle` returns a zero-length segment for coplanar
// intersecting triangles, which is fine for our purposes here. We
// don't need the segment itself in this function. So we can suppress
// the warning about coplanar triangles.
if ( this.intersectsTriangle( other, lineTarget, true ) ) {
if ( target1 || target2 ) {
if ( target1 ) lineTarget.getCenter( target1 );
if ( target2 ) lineTarget.getCenter( target2 );
}
return 0;
}
let closestDistanceSq = Infinity;
// check all point distances
for ( let i = 0; i < 3; i ++ ) {
let dist;
const field = cornerFields[ i ];
const otherVec = other[ field ];
this.closestPointToPoint( otherVec, point );
dist = otherVec.distanceToSquared( point );
if ( dist < closestDistanceSq ) {
closestDistanceSq = dist;
if ( target1 ) target1.copy( point );
if ( target2 ) target2.copy( otherVec );
}
const thisVec = this[ field ];
other.closestPointToPoint( thisVec, point );
dist = thisVec.distanceToSquared( point );
if ( dist < closestDistanceSq ) {
closestDistanceSq = dist;
if ( target1 ) target1.copy( thisVec );
if ( target2 ) target2.copy( point );
}
}
for ( let i = 0; i < 3; i ++ ) {
const f11 = cornerFields[ i ];
const f12 = cornerFields[ ( i + 1 ) % 3 ];
line1.set( this[ f11 ], this[ f12 ] );
for ( let i2 = 0; i2 < 3; i2 ++ ) {
const f21 = cornerFields[ i2 ];
const f22 = cornerFields[ ( i2 + 1 ) % 3 ];
line2.set( other[ f21 ], other[ f22 ] );
closestPointsSegmentToSegment( line1, line2, point, point2 );
const dist = point.distanceToSquared( point2 );
if ( dist < closestDistanceSq ) {
closestDistanceSq = dist;
if ( target1 ) target1.copy( point );
if ( target2 ) target2.copy( point2 );
}
}
}
return Math.sqrt( closestDistanceSq );
};
} )();