fast-triangle-triangle-intersection
Fast and robust triangle-triangle intersection test with high precision for cross and coplanar triangles based on the algorithm by Devillers & Guigue [1].
- Uses Three.js
- Computes the intersection shape (point, line or polygon).
- Typescript definitions included.
Demo
Online Triangles Intersection demo
Install
npm i fast-triangle-triangle-intersection
Documentation
trianglesIntersect(t1: Triangle, t2: Triangle, target?: Array<Vector3>): Intersection
Computes wether triangle t1 and t2 are intersecting and returns Intersection.Cross if triangles are cross-intersecting, Intersection.Coplanar if triangles are coplanar-intersecting, otherwise returns null. If target array is given, it is emptied and intersection points are then computed and put in the array.
Example
Check if triangles are simply intersecting.
import {Triangle} from 'three';
import {trianglesIntersect, Intersection} from 'fast-triangle-triangle-intersection';
const t1 = new Triangle();
t1.a.set(-1, 0, 0);
t1.b.set(2, 0, -2);
t1.c.set(2, 0, 2);
const t2 = new Triangle();
t2.a.set(1, 0, 0);
t2.b.set(-2, -2, 0);
t2.c.set(-2, 2, 0);
const intersection = trianglesIntersect(t1, t2);
if (intersection === Intersection.Cross) {
console.log("Triangles are cross-intersecting.");
} else if (intersection === Intersection.Coplanar) {
console.log("Triangles are coplanar-intersecting.");
} else {
console.log("Triangles are not intersecting.");
}
Obtening the intersection points.
const points = new Array<Vector3>();
if (trianglesIntersect(t1, t2, points)) {
console.log("Intersection points: ", points); // [Vector3(1, 0, 0), Vector3(-1, 0, 0)]
}
Info
This algorithm is based on the publication by Devillers & Guigue [1].
@techreport{devillers:inria-00072100,
TITLE = {{Faster Triangle-Triangle Intersection Tests}},
AUTHOR = {Devillers, Olivier and Guigue, Philippe},
URL = {https://hal.inria.fr/inria-00072100},
NUMBER = {RR-4488},
INSTITUTION = {{INRIA}},
YEAR = {2002},
MONTH = Jun,
KEYWORDS = {LOW DEGREE PREDICATE ; COLLISION DETECTION ; GEOMETRIC PREDICATES},
PDF = {https://hal.inria.fr/inria-00072100/file/RR-4488.pdf},
HAL_ID = {inria-00072100},
HAL_VERSION = {v1},
}
4 May 3, 2022
14 Jan 3, 2023
10 Nov 24, 2022
942 Dec 30, 2022
16 Nov 5, 2022
54 Dec 12, 2022
89 Dec 20, 2022
7 Nov 5, 2022
5.7k Jan 4, 2023