koobas.hobune.stream
A fast triangle triangle intersection algorithm for unity?
Is there any? No physics please.
Thanks for downvote! This is not a homework, I'm a 14 year old hobbyist. Please explain what is the problem.
Best Answer
It would recommend using Möller's approach.
C# implementation of the Möller-Trumbore algorithm.
/// <summary>
/// Checks if the specified ray hits the triagnlge descibed by p1, p2 and p3.
/// Möller–Trumbore ray-triangle intersection algorithm implementation.
/// </summary>
/// <param name="p1">Vertex 1 of the triangle.</param>
/// <param name="p2">Vertex 2 of the triangle.</param>
/// <param name="p3">Vertex 3 of the triangle.</param>
/// <param name="ray">The ray to test hit for.</param>
/// <returns><c>true</c> when the ray hits the triangle, otherwise <c>false</c></returns>
public static bool Intersect(Vector3 p1, Vector3 p2, Vector3 p3, Ray ray)
{
// Vectors from p1 to p2/p3 (edges)
Vector3 e1, e2;
Vector3 p, q, t;
float det, invDet, u, v;
//Find vectors for two edges sharing vertex/point p1
e1 = p2 - p1;
e2 = p3 - p1;
// calculating determinant
p = Vector3.Cross(ray.direction, e2);
//Calculate determinat
det = Vector3.Dot(e1, p);
//if determinant is near zero, ray lies in plane of triangle otherwise not
if (det > -Epsilon && det < Epsilon) { return false; }
invDet = 1.0f / det;
//calculate distance from p1 to ray origin
t = ray.origin - p1;
//Calculate u parameter
u = Vector3.Dot(t, p) * invDet;
//Check for ray hit
if (u < 0 || u > 1) { return false; }
//Prepare to test v parameter
q = Vector3.Cross(t, e1);
//Calculate v parameter
v = Vector3.Dot(ray.direction, q) * invDet;
//Check for ray hit
if (v < 0 || u + v > 1) { return false; }
if ((Vector3.Dot(e2, q) * invDet) > Epsilon)
{
//ray does intersect
return true;
}
// No hit at all
return false;
}
EDIT: Tri-Tri-Intersection I did not have the time to test, so please let me know if everything is working as expected.
using UnityEngine;
using System.Collections;
/// <summary>
/// Tri/Tri intersection. Implementation of Tomas Moller, 1997.
/// See article "A Fast Triangle-Triangle Intersection Test", Journal of Graphics Tools, 2(2), 1997.
/// </summary>
public static class TriTriOverlap
{
private static void Sort(Vector2 v)
{
if (v.x > v.y)
{
float c;
c = v.x;
v.x = v.y;
v.y = c;
}
}
/// <summary>
/// This edge to edge test is based on Franlin Antonio's gem: "Faster Line Segment Intersection", in Graphics Gems III, pp. 199-202
/// </summary>
private static bool EdgeEdgeTest(Vector3 v0, Vector3 v1, Vector3 u0, Vector3 u1, int i0, int i1)
{
float Ax, Ay, Bx, By, Cx, Cy, e, d, f;
Ax = v1[i0] - v0[i0];
Ay = v1[i1] - v0[i1];
Bx = u0[i0] - u1[i0];
By = u0[i1] - u1[i1];
Cx = v0[i0] - u0[i0];
Cy = v0[i1] - u0[i1];
f = Ay * Bx - Ax * By;
d = By * Cx - Bx * Cy;
if ((f > 0 && d >= 0 && d <= f) || (f < 0 && d <= 0 && d >= f))
{
e = Ax * Cy - Ay * Cx;
if (f > 0)
{
if (e >= 0 && e <= f) { return true; }
}
else
{
if (e <= 0 && e >= f) { return true; }
}
}
return false;
}
private static bool EdgeAgainstTriEdges(Vector3 v0, Vector3 v1, Vector3 u0, Vector3 u1, Vector3 u2, short i0, short i1)
{
// test edge u0,u1 against v0,v1
if (EdgeEdgeTest(v0, v1, u0, u1, i0, i1)) { return true; }
// test edge u1,u2 against v0,v1
if (EdgeEdgeTest(v0, v1, u1, u2, i0, i1)) { return true; }
// test edge u2,u1 against v0,v1
if (EdgeEdgeTest(v0, v1, u2, u0, i0, i1)) { return true; }
return false;
}
private static bool PointInTri(Vector3 v0, Vector3 u0, Vector3 u1, Vector3 u2, short i0, short i1)
{
float a, b, c, d0, d1, d2;
// is T1 completly inside T2?
// check if v0 is inside tri(u0,u1,u2)
a = u1[i1] - u0[i1];
b = -(u1[i0] - u0[i0]);
c = -a * u0[i0] - b * u0[i1];
d0 = a * v0[i0] + b * v0[i1] + c;
a = u2[i1] - u1[i1];
b = -(u2[i0] - u1[i0]);
c = -a * u1[i0] - b * u1[i1];
d1 = a * v0[i0] + b * v0[i1] + c;
a = u0[i1] - u2[i1];
b = -(u0[i0] - u2[i0]);
c = -a * u2[i0] - b * u2[i1];
d2 = a * v0[i0] + b * v0[i1] + c;
if (d0 * d1 > 0.0f)
{
if (d0 * d2 > 0.0f) { return true; }
}
return false;
}
private static bool TriTriCoplanar(Vector3 N, Vector3 v0, Vector3 v1, Vector3 v2, Vector3 u0, Vector3 u1, Vector3 u2)
{
float[] A = new float[3];
short i0, i1;
// first project onto an axis-aligned plane, that maximizes the area
// of the triangles, compute indices: i0,i1.
A[0] = Mathf.Abs(N[0]);
A[1] = Mathf.Abs(N[1]);
A[2] = Mathf.Abs(N[2]);
if (A[0] > A[1])
{
if (A[0] > A[2])
{
// A[0] is greatest
i0 = 1;
i1 = 2;
}
else
{
// A[2] is greatest
i0 = 0;
i1 = 1;
}
}
else
{
if (A[2] > A[1])
{
// A[2] is greatest
i0 = 0;
i1 = 1;
}
else
{
// A[1] is greatest
i0 = 0;
i1 = 2;
}
}
// test all edges of triangle 1 against the edges of triangle 2
if (EdgeAgainstTriEdges(v0, v1, u0, u1, u2, i0, i1)) { return true; }
if (EdgeAgainstTriEdges(v1, v2, u0, u1, u2, i0, i1)) { return true; }
if (EdgeAgainstTriEdges(v2, v0, u0, u1, u2, i0, i1)) { return true; }
// finally, test if tri1 is totally contained in tri2 or vice versa
if (PointInTri(v0, u0, u1, u2, i0, i1)) { return true; }
if (PointInTri(u0, v0, v1, v2, i0, i1)) { return true; }
return false;
}
private static bool ComputeIntervals(float VV0, float VV1, float VV2,
float D0, float D1, float D2, float D0D1, float D0D2,
ref float A, ref float B, ref float C, ref float X0, ref float X1)
{
if (D0D1 > 0.0f)
{
// here we know that D0D2<=0.0
// that is D0, D1 are on the same side, D2 on the other or on the plane
A = VV2; B = (VV0 - VV2) * D2; C = (VV1 - VV2) * D2; X0 = D2 - D0; X1 = D2 - D1;
}
else if (D0D2 > 0.0f)
{
// here we know that d0d1<=0.0
A = VV1; B = (VV0 - VV1) * D1; C = (VV2 - VV1) * D1; X0 = D1 - D0; X1 = D1 - D2;
}
else if (D1 * D2 > 0.0f || D0 != 0.0f)
{
// here we know that d0d1<=0.0 or that D0!=0.0
A = VV0; B = (VV1 - VV0) * D0; C = (VV2 - VV0) * D0; X0 = D0 - D1; X1 = D0 - D2;
}
else if (D1 != 0.0f)
{
A = VV1; B = (VV0 - VV1) * D1; C = (VV2 - VV1) * D1; X0 = D1 - D0; X1 = D1 - D2;
}
else if (D2 != 0.0f)
{
A = VV2; B = (VV0 - VV2) * D2; C = (VV1 - VV2) * D2; X0 = D2 - D0; X1 = D2 - D1;
}
else
{
return true;
}
return false;
}
/// <summary>
/// Checks if the triangle V(v0, v1, v2) intersects the triangle U(u0, u1, u2).
/// </summary>
/// <param name="v0">Vertex 0 of V</param>
/// <param name="v1">Vertex 1 of V</param>
/// <param name="v2">Vertex 2 of V</param>
/// <param name="u0">Vertex 0 of U</param>
/// <param name="u1">Vertex 1 of U</param>
/// <param name="u2">Vertex 2 of U</param>
/// <returns>Returns <c>true</c> if V intersects U, otherwise <c>false</c></returns>
public static bool TriTriIntersect(Vector3 v0, Vector3 v1, Vector3 v2, Vector3 u0, Vector3 u1, Vector3 u2)
{
Vector3 e1, e2;
Vector3 n1, n2;
Vector3 dd;
Vector2 isect1 = Vector2.zero, isect2 = Vector2.zero;
float du0, du1, du2, dv0, dv1, dv2, d1, d2;
float du0du1, du0du2, dv0dv1, dv0dv2;
float vp0, vp1, vp2;
float up0, up1, up2;
float bb, cc, max;
short index;
// compute plane equation of triangle(v0,v1,v2)
e1 = v1 - v0;
e2 = v2 - v0;
n1 = Vector3.Cross(e1, e2);
d1 = -Vector3.Dot(n1, v0);
// plane equation 1: N1.X+d1=0 */
// put u0,u1,u2 into plane equation 1 to compute signed distances to the plane
du0 = Vector3.Dot(n1, u0) + d1;
du1 = Vector3.Dot(n1, u1) + d1;
du2 = Vector3.Dot(n1, u2) + d1;
// coplanarity robustness check
if (Mathf.Abs(du0) < Mathf.Epsilon) { du0 = 0.0f; }
if (Mathf.Abs(du1) < Mathf.Epsilon) { du1 = 0.0f; }
if (Mathf.Abs(du2) < Mathf.Epsilon) { du2 = 0.0f; }
du0du1 = du0 * du1;
du0du2 = du0 * du2;
// same sign on all of them + not equal 0 ?
if (du0du1 > 0.0f && du0du2 > 0.0f)
{
// no intersection occurs
return false;
}
// compute plane of triangle (u0,u1,u2)
e1 = u1 - u0;
e2 = u2 - u0;
n2 = Vector3.Cross(e1, e2);
d2 = -Vector3.Dot(n2, u0);
// plane equation 2: N2.X+d2=0
// put v0,v1,v2 into plane equation 2
dv0 = Vector3.Dot(n2, v0) + d2;
dv1 = Vector3.Dot(n2, v1) + d2;
dv2 = Vector3.Dot(n2, v2) + d2;
if (Mathf.Abs(dv0) < Mathf.Epsilon) { dv0 = 0.0f; }
if (Mathf.Abs(dv1) < Mathf.Epsilon) { dv1 = 0.0f; }
if (Mathf.Abs(dv2) < Mathf.Epsilon) { dv2 = 0.0f; }
dv0dv1 = dv0 * dv1;
dv0dv2 = dv0 * dv2;
// same sign on all of them + not equal 0 ?
if (dv0dv1 > 0.0f && dv0dv2 > 0.0f)
{
// no intersection occurs
return false;
}
// compute direction of intersection line
dd = Vector3.Cross(n1, n2);
// compute and index to the largest component of D
max = (float)Mathf.Abs(dd[0]);
index = 0;
bb = (float)Mathf.Abs(dd[1]);
cc = (float)Mathf.Abs(dd[2]);
if (bb > max) { max = bb; index = 1; }
if (cc > max) { max = cc; index = 2; }
// this is the simplified projection onto L
vp0 = v0[index];
vp1 = v1[index];
vp2 = v2[index];
up0 = u0[index];
up1 = u1[index];
up2 = u2[index];
// compute interval for triangle 1
float a = 0, b = 0, c = 0, x0 = 0, x1 = 0;
if (ComputeIntervals(vp0, vp1, vp2, dv0, dv1, dv2, dv0dv1, dv0dv2, ref a, ref b, ref c, ref x0, ref x1))
{
return TriTriCoplanar(n1, v0, v1, v2, u0, u1, u2);
}
// compute interval for triangle 2
float d = 0, e = 0, f = 0, y0 = 0, y1 = 0;
if (ComputeIntervals(up0, up1, up2, du0, du1, du2, du0du1, du0du2, ref d, ref e, ref f, ref y0, ref y1))
{
return TriTriCoplanar(n1, v0, v1, v2, u0, u1, u2);
}
float xx, yy, xxyy, tmp;
xx = x0 * x1;
yy = y0 * y1;
xxyy = xx * yy;
tmp = a * xxyy;
isect1[0] = tmp + b * x1 * yy;
isect1[1] = tmp + c * x0 * yy;
tmp = d * xxyy;
isect2[0] = tmp + e * xx * y1;
isect2[1] = tmp + f * xx * y0;
Sort(isect1);
Sort(isect2);
return !(isect1[1] < isect2[0] || isect2[1] < isect1[0]);
}
}
Just put the whole class into a new c#-file and use the TriTriIntersect method to test.
Variable Epsilon does not exist. It should be float $$anonymous$$athf.Epsilon.
This is not even answer to my question! It is ray-triangle intersection not triangle-triangle.
Sorry, thought triangle triangle was a typo... :) So you want to know if a triangle intersects another triangle, right?
As soon I will have the time I will port the $$anonymous$$öller-Tri-Tri algorithm for you. This code will be much bigger because of the coplanar test etc...
It has been two days, can you get it ready before school starts? :D
my answer here is fairly off-topic because it's line-vs-triangle instead of triangle-vs-triangle, but this article is currently the #1 hit for line-vs-triangle, so here's to deepening a rut in the morphogenic field!
nu-asset's answer is excellent, but if you're looking for a line versus triangle test using the same algorithm, but you'd like to get back the time (or distance) along the ray instead of true/false, here's a port of the wikipedia c++ Möller–Trumbore routine:
const float kEpsilon = 0.000001f;
/// <summary>
/// Ray-versus-triangle intersection test suitable for ray-tracing etc.
/// Port of Möller–Trumbore algorithm c++ version from:
/// https://en.wikipedia.org/wiki/Möller–Trumbore_intersection_algorithm
/// </summary>
/// <returns><c>The distance along the ray to the intersection</c> if one exists, <c>NaN</c> if one does not.</returns>
/// <param name="ray">Le ray.</param>
/// <param name="v0">A vertex of the triangle.</param>
/// <param name="v1">A vertex of the triangle.</param>
/// <param name="v2">A vertex of the triangle.</param>
public static float IntersectRayTriangle(Ray ray, Vector3 v0, Vector3 v1, Vector3 v2) {
// edges from v1 & v2 to v0.
Vector3 e1 = v1 - v0;
Vector3 e2 = v2 - v0;
Vector3 h = Vector3.Cross(ray.direction, e2);
float a = Vector3.Dot (e1 , h );
if ((a > -kEpsilon) && (a < kEpsilon)) {
return float.NaN;
}
float f = 1.0f / a;
Vector3 s = ray.origin - v0;
float u = f * Vector3.Dot(s, h);
if ((u < 0.0f) || (u > 1.0f)) {
return float.NaN;
}
Vector3 q = Vector3.Cross(s, e1);
float v = f * Vector3.Dot(ray.direction, q);
if ((v < 0.0f) || (u + v > 1.0f)) {
return float.NaN;
}
float t = f * Vector3.Dot(e2, q);
if (t > kEpsilon) {
return t;
}
else {
return float.NaN;
}
}
}
I tested this, it doesn't work. It always returns true.
I tested this and it works.
bool IntersectRayTriangle(
in Ray ray,
in Vector3 v0,
in Vector3 v1,
in Vector3 v2,
out Vector3 IntersectionPoint)
{
IntersectionPoint = Vector3.zero;
Vector3 rayOrigin = ray.origin;
Vector3 rayVector = ray.direction;
const float EPSILON = 0.0000001f;
Vector3 edge1, edge2, h, s, q;
float a,f,u,v;
edge1 = v1 - v0;
edge2 = v2 - v0;
h = Vector3.Cross(rayVector, edge2);
a = Vector3.Dot(edge1, h);
if (a > -EPSILON && a < EPSILON)
return false; // This ray is parallel to this triangle.
f = 1.0f / a;
s = rayOrigin - v0;
u = f * Vector3.Dot(s, h);
if (u < 0.0f || u > 1.0f)
return false;
q = Vector3.Cross(s, edge1);
v = f * Vector3.Dot(rayVector, q);
if (v < 0.0f || u + v > 1.0f)
return false;
// At this stage we can compute t to find out where the intersection point is on the line.
float t = f * Vector3.Dot(edge2, q);
if (t > EPSILON) // ray intersection
{
IntersectionPoint = rayOrigin + rayVector * t;
return true;
}
else // This means that there is a line intersection but not a ray intersection.
return false;
}
The code I provided works as advertised. Judging by your statement "it always returns true", I suspect you ignored the input/output types and the parameter comments. The code does not return a bool, it returns a float.
Here is a unity scene demonstrating the code: https://github.com/elenzil/unity_ray_vs_triangle
I tested this code and modify Sort(Vector2 v) to Sort(ref Vector v) and everything goes well.
bool IntersectRayTriangle(
in Ray ray,
in Vector3 v0,
in Vector3 v1,
in Vector3 v2,
out Vector3 IntersectionPoint)
{
IntersectionPoint = Vector3.zero;
Vector3 rayOrigin = ray.origin;
Vector3 rayVector = ray.direction;
const float EPSILON = 0.0000001f;
Vector3 edge1, edge2, h, s, q;
float a,f,u,v;
edge1 = v1 - v0;
edge2 = v2 - v0;
h = Vector3.Cross(rayVector, edge2);
a = Vector3.Dot(edge1, h);
if (a > -EPSILON && a < EPSILON)
return false; // This ray is parallel to this triangle.
f = 1.0f / a;
s = rayOrigin - v0;
u = f * Vector3.Dot(s, h);
if (u < 0.0f || u > 1.0f)
return false;
q = Vector3.Cross(s, edge1);
v = f * Vector3.Dot(rayVector, q);
if (v < 0.0f || u + v > 1.0f)
return false;
// At this stage we can compute t to find out where the intersection point is on the line.
float t = f * Vector3.Dot(edge2, q);
if (t > EPSILON) // ray intersection
{
IntersectionPoint = rayOrigin + rayVector * t;
return true;
}
else // This means that there is a line intersection but not a ray intersection.
return false;
}
