SAT - Same Plane Triangle

Finn The Human · 2016-07-07T17:46:13

I've implemented a Seperating Axis test for two triangles. The test seems to work in all cases, except if the two triangles happen to be on the same plane. For the seprating axis, i'm testing the normals for both triangles, then the 9 axis i get from crossing the sides of the triangles. My best guess is that because the two triangles lie on the same plane, the cross product of their normals returns a zero vector? But how would you go about fixing that? Any idea why it would fail only when the triangles are on the same plane? If it's any help, i've attached my code: public static bool Intersects(Triangle triangle1, Triangle triangle2) { Vector3 t1_v0 = triangle1.p0.ToVector(); Vector3 t1_v1 = triangle1.p1.ToVector(); Vector3 t1_v2 = triangle1.p2.ToVector(); Vector3 t1_f0 = t1_v1 - t1_v0; // B - A Vector3 t1_f1 = t1_v2 - t1_v1; // C - B Vector3 t1_f2 = t1_v0 - t1_v2; // A - C Vector3 t2_v0 = triangle2.p0.ToVector(); Vector3 t2_v1 = triangle2.p1.ToVector(); Vector3 t2_v2 = triangle2.p2.ToVector(); Vector3 t2_f0 = t2_v1 - t2_v0; // B - A Vector3 t2_f1 = t2_v2 - t2_v1; // C - B Vector3 t2_f2 = t2_v0 - t2_v2; // A - C Vector3[] axisToTest = new[] { Vector3.Cross(t1_f0, t1_f1), Vector3.Cross(t2_f0, t1_f1), Vector3.Cross(t2_f0, t1_f0), Vector3.Cross(t2_f0, t1_f1), Vector3.Cross(t2_f0, t1_f2), Vector3.Cross(t2_f1, t1_f0), Vector3.Cross(t2_f1, t1_f1), Vector3.Cross(t2_f1, t1_f2), Vector3.Cross(t2_f2, t1_f0), Vector3.Cross(t2_f2, t1_f1), Vector3.Cross(t2_f2, t1_f2), }; foreach(Vector3 axis in axisToTest) { if (!TriangleTriangleSAT(triangle1, triangle2, axis)) { return false; } } return true; } protected static bool TriangleTriangleSAT(Triangle triangle1, Triangle triangle2, Vector3 raw_axis) { Vector3 axis = Vector3.Normalize(raw_axis); Vector2 range1 = GetTriangleInterval(triangle1, axis); Vector2 range2 = GetTriangleInterval(triangle2, axis); float min1 = range1.X; float max1 = range1.Y; float min2 = range2.X; float max2 = range2.Y; if (max1 < min2 || max2 < min1) { return false; } /*if (range1.Y < range2.X || range2.Y < range1.X) { return false; }*/ return true; } protected static Vector2 GetTriangleInterval(Triangle triangle, Vector3 axis) { Vector3[] vertices = new Vector3[] { triangle.p0.ToVector(), triangle.p1.ToVector(), triangle.p2.ToVector() }; float min = Vector3.Dot(axis, vertices[0]); float max = min; for (int i = 0; i < vertices.Length ; ++i) { float value = Vector3.Dot(axis, vertices[i]); min = Min(min, value); max = Max(max, value); } return new Vector2(min, max); }

Math and Physics Programming

Started by mathematical July 06, 2016 12:51 AM

11 comments, last by Dirk Gregorius 7 years, 9 months ago

Irlan Robson

4,091

July 07, 2016 12:29 AM

Only two *supporting edges* (a.k.a a face on the MK sum) need to be tested for separation (and the faces obviously).

This can be done with brute force checking: Build a plane from the first edge in the direction of the cross edges product (pointing to the second poly) and make sure all the first poly vertices are behind this plane. Do the same for the second edge and poly but negating the normal direction for acount for the support. Finally, for the separation get a support from the second poly in the opposite normal direction. The distance between the support and the first plane is your (correct) separation.

Or you can be smart and use gauss maps as pointed out by Dirk to prune edge pairs. Use Game Physics Pearls to visualize more examples on this.

Hope this helps and sorry for extending the discussion more than needed.

mathematical

504

Author

July 07, 2016 04:34 AM

@Dirk, thank you for the resource link! You are freaking awesome!

Dirk Gregorius

2,918

July 07, 2016 05:46 PM

Thanks, I am glad you like it. If you are interested in these kind of presentations (what your name suggests) you kind find a lot similar presentations on the GDC Physics Tutorial website hosted on Box2D: http://box2d.org/downloads/

Similarly, the GDC Math tutorial has lots of presentations collected over the years as well:

http://www.essentialmath.com/tutorial.htm

SAT - Same Plane Triangle

This topic is closed to new replies.

Popular Topics

Recommended Tutorials

SAT - Same Plane Triangle

This topic is closed to new replies.

Popular Topics

Recommended Tutorials

Reticulating splines