Java-Gaming.org Hi !
Featured games (83)
games approved by the League of Dukes
Games in Showcase (539)
Games in Android Showcase (132)
games submitted by our members
Games in WIP (603)
games currently in development
News: Read the Java Gaming Resources, or peek at the official Java tutorials
 
    Home     Help   Search   Login   Register   
Pages: [1]
  ignore  |  Print  
  Triangle Intersection Tests  (Read 6239 times)
0 Members and 1 Guest are viewing this topic.
Offline DrHalfway
« Posted 2013-08-08 11:47:14 »

Hello JGO Community. No I'm not dead, just taking a small Hiatus from Java Game Development!

I come today to share some source code I've been working on for various methods using the Unity framework. Originally I wrote the methods in C#, however for the sake of this tutorial I've converted them in Java just for you! (well not really, I just like Java)

This tutorial is a direct follow up from my previous tutorial for basic collision detection found in the following link http://www.java-gaming.org/topics/basic-collision-detection/27326/view.html.

The methods presented in this tutorial are for processing and intersecting 3D triangles, you will find this useful when creating things such as advanced decal frameworks or object slicers which could work for both 2D and 3D.

For sake of this tutorial, I assume that you have a working Vector2 and Vector3 library. If you don't, libraries such as LibGDX or LWJGL provide one for you. Depending on how you layout your code, you may need to perform some light modifications, otherwise it should work by simply copy pasting the code into your Java projects.

The method presented below is for finding the closest point between a triangle and a point. Very useful method in certain situations.

1  
2  
3  
4  
5  
6  
7  
8  
9  
10  
11  
12  
13  
14  
15  
16  
17  
18  
19  
20  
21  
22  
23  
24  
25  
26  
27  
28  
29  
30  
31  
32  
33  
34  
35  
36  
37  
38  
39  
40  
41  
42  
43  
44  
45  
46  
47  
48  
49  
50  
51  
52  
53  
54  
55  
56  
57  
58  
59  
60  
61  
62  
63  
64  
65  
66  
67  
68  
69  
70  
71  
72  
73  
74  
75  
76  
77  
78  
79  
// for triangle a-b-c return a point q in triangle that is closest to p
public static Vector3 closestPtPointTriangle(Vector3 p, Vector3 a, Vector3 b, Vector3 c) {
   // Optimized version as found in book Real time collision detection
   // b - a
   Vector3 ab = Vector3.subtract(b, a);
   
   // c - a
   Vector3 ac = Vector3.subtract(c, a);
   
   // p - a
   Vector3 ap = Vector3.subtract(p, a);
   
   float d1 = Vector3.Dot(ab, ap);
   float d2 = Vector3.Dot(ac, ap);
   
   if (d1 <= 0.0f && d2 <= 0.0f) {
      return a;  
   }
   
   // p - b
   Vector3 bp = Vector3.subtract(p, b);
   
   float d3 = Vector3.Dot(ab, bp);
   float d4 = Vector3.Dot(ac, bp);
   
   if (d3 >= 0.0f && d4 <= d3) {
      return b;  
   }
   
   float vc = d1 * d4 - d3 * d2;
   
   if (vc <= 0.0f && d1 >= 0.0f && d3 <= 0.0f) {
      float v = d1 / (d1 - d3);
     
      // a + (ab * v)
      return Vector3.add(a, Vector3.multiply(ab, v));
   }
   
   // p - c
   Vector3 cp = Vector3.subtract(p, c);
   
   float d5 = Vector3.Dot(ab, cp);
   float d6 = Vector3.Dot(ac, cp);
   
   if (d6 >= 0.0f && d5 <= d6) {
      return c;  
   }
   
   float vb = d5 * d2 - d1 * d6;
   
   if (vb <= 0.0f && d2 >= 0.0f && d6 <= 0.0f) {
      float w = d2 / (d2 - d6);
     
      // a + (ac * w)
      return Vector3.add(a, Vector3.multiply(ac, w));
   }
   
   float va = d3 * d6 - d5 * d4;
   
   if (va <= 0.0f && (d4 - d3) >= 0.0f && (d5 - d6) >= 0.0f) {
      float w = (d4 - d3) / ((d4 - d3) + (d5 - d6));
     
      // b + w * (c - b)
      return Vector3.add(b, Vector3.multiply(Vector3.subtract(c, b), w));
   }
   
   float denom = 1.0f / (va + vb + vc);
   float vn = vb * denom;
   float wn = vc * denom;
   
   // a + ab * vn + ac * wn
   // this can be done with one line
   
   Vector3 abvn = Vector3.multiply(ab, vn);
   Vector3 acwn = Vector3.multiply(ac, wn);
   
   // return result
   return Vector3.add(a, Vector3.add(abvn, acwn));
}


Below is a quick method to check if a point p is in a triangle defined by points a-b-c

1  
2  
3  
4  
5  
6  
7  
8  
9  
10  
11  
12  
13  
14  
15  
16  
17  
18  
19  
20  
// check if point p is in triangle a-b-c
public static boolean pointInTriangle(Vector3 p, Vector3 a, Vector3 b, Vector3 c) {
   // bring triangle to p coordinate frame
   Vector3 pa = Vector3.subtract(a, p);
   Vector3 pb = Vector3.subtract(b, p);
   Vector3 pc = Vector3.subtract(c, p);
   
   float ab = Vector3.Dot(pa,pb);
   float ac = Vector3.Dot(pa,pc);
   float bc = Vector3.Dot(pb,pc);
   float cc = Vector3.Dot(pc,pc);
   
   if (bc * ac - cc * ab < 0.0f) return false;
   
   float bb = Vector3.Dot(b,b);
   
   if (ab * bc - ac * bb < 0.0f) return false;
   
   return true;
}


Below is a method of intersecting a line made by two vectors. The intersection point can also be computed. The method will return false if no intersection occurs.
Method also very useful for performing ray-triangle intersections.

1  
2  
3  
4  
5  
6  
7  
8  
9  
10  
11  
12  
13  
14  
15  
16  
17  
18  
19  
20  
21  
22  
23  
24  
25  
26  
27  
28  
29  
30  
31  
32  
33  
34  
35  
36  
37  
38  
39  
// for triangle a-b-c, intersect the line made by p-q and store intersection point in r
// returns true if intersected, or false if no intersection occurs
public static boolean intersectLineTriangle(Vector3 p, Vector3 q, Vector3 a, Vector3 b, Vector3 c, Vector3 r) {
   // Bring points to their respective coordinate frame
   Vector3 pq = Vector3.subtract(q, p);
   Vector3 pa = Vector3.subtract(a, p);
   Vector3 pb = Vector3.subtract(b, p);
   Vector3 pc = Vector3.subtract(c, p);
   
   Vector3 m = Vector3.Cross(pq,pc);
   
   float u = Vector3.Dot(pb,m);      
   float v = -Vector3.Dot(pa,m);
   
   if (Math.signum(u) != Math.signum(v)) {
      return false;
   }
   
   // scalar triple product
   float w = Vector3.Dot(pq, Vector3.Cross(pb,pa));
   
   if (Math.signum(u) != Math.signum(w)) {
      return false;
   }
   
   float denom = 1.0f / (u + v + w);
   
   // r = ((u * denom) * a) + ((v * denom) * b) + ((w * denom) * c);
   Vector3 compA = Vector3.multiply(a, u * denom);
   Vector3 compB = Vector3.multiply(b, v * denom);
   Vector3 compC = Vector3.multiply(c, w * denom);
   
   // store result in Vector r
   r.x = compA.x + compB.x + compC.x;
   r.y = compA.y + compB.y + compC.y;
   r.z = compA.z + compB.z + compC.z;
   
   return true;
}


Before we proceed with our next method, we are going to define a Plane in 3D. So what is a plane?

A plane can be considered to be an entity which has a position and a direction that extends to and from infinity. It is very useful in certain intersection tests and with some creativity, it can be used to create interesting bounding volumes in code.

Below is how we will define our Plane

1  
2  
3  
4  
5  
6  
7  
8  
9  
10  
public class Plane {
   
   public Vector3 n;
   public float d;
   
   public Plane(Vector3 direction, Vector3 position) {
      this.n = direction;
      this.d = Vector3.Dot(n,position);
   }
}


Notice how we don't store position directly? The precomputed floating point d is actually more useful for us when performing intersection tests against this Plane which will soon become apparent.

Lets create our first intersection test - A line vs a Plane test, below is the code

1  
2  
3  
4  
5  
6  
7  
8  
9  
10  
11  
12  
13  
14  
15  
16  
17  
// intersect the line a-b with plane p and store result in q
// returns true or false if intersection is found
public static boolean intersectLinePlane(Plane plane, Vector3 a, Vector3 b, Vector3 q) {
   Vector3 ab = Vector3.subtract(b, a);
   
   float t = (plane.d - Vector3.Dot(plane.n, a)) / Vector3.Dot(plane.n, ab);
   
   // floating point errors common here - use own delta values as needed
   if (t >= -0.0001f && t <= 1.0001f) {
      // q = a + t * ab
      q.set(Vector3.add(a, Vector3.multiply(ab, t)));
     
      return true;
   }
   
   return false;
}


And as always, a cheap method exists to see which side a point lies on the Plane. This can be used to early-out most intersection tests before proceeding with expensive mathematics stuff.

1  
2  
3  
4  
5  
// check to see where the point p lies on plane
public static boolean sideOfPlane(Plane plane, Vector3 p) {
   // some bloody math errors here again, modify with delta values as needed
   return Vector3.Dot(plane.n, p) >= plane.d - 0.001f;  
}


I am going to end this tutorial with something very interesting. A concept of Barycentric coordinates, which is a very powerful tool that can be used for both intersection tests and more importantly interpolation inside a 3D triangle.

For example, lets say you wish to cut a Quad made from two triangles with a line. All easy enough, and now you are left with a problem of generating new UV coordinates for the intersection points. As it turns out, if we have a triangle (A,B,C) that has UV coordinates (UVA,UVB,UVC) we can work out "weight" values u,v,w for triangle A,B,C so that for any point P on or in triangle A,B,C will have new UV coordinates of UVP = UVA * u + UVB * v + UVC * w.

1  
2  
3  
4  
5  
6  
7  
8  
9  
10  
11  
12  
13  
14  
15  
16  
17  
18  
19  
20  
21  
22  
23  
24  
25  
26  
27  
28  
29  
30  
31  
32  
33  
34  
35  
36  
37  
38  
39  
40  
41  
42  
43  
44  
// compute the barycentric coordinates of triangle a-b-c in regards to point p and store result in references u-v-w respectively
// where u = uvw[0], v = uvw[1], w = uvw[2], make sure array uvw is length 3.
public static void barycentric(Vector3 a, Vector3 b, Vector3 c, Vector3 p, float[] uvw) {
   Vector3 m = Vector3.Cross(Vector3.subtract(b, c), Vector3.subtract(c, a));
   
   float nu;
   float nv;
   float ood;
   
   float x = Math.abs(m.x);
   float y = Math.abs(m.y);
   float z = Math.abs(m.z);
   
   // compute areas of plane with largest projections
   if (x >= y && x >= z) {
      // area of PBC in yz plane
      nu = triArea2D(p.y, p.z, b.y, b.z, c.y, c.z);
      // area of PCA in yz plane
      nv = triArea2D(p.y, p.z, c.y, c.z, a.y, a.z);
      // 1/2*area of ABC in yz plane
      ood = 1.0f / m.x;
   }
   else if (y >= x && y >= z) {
      // project in xz plane
      nu = triArea2D(p.x, p.z, b.x, b.z, c.x, c.z);
      nv = triArea2D(p.x, p.z, c.x, c.z, a.x, a.z);
      ood = 1.0f / -m.y;
   }
   else {
      // project in xy plane
      nu = triArea2D(p.x, p.y, b.x, b.y, c.x, c.y);
      nv = triArea2D(p.x, p.y, c.x, c.y, a.x, a.y);
      ood = 1.0f / m.z;
   }
   
   uvw[0] = nu * ood;
   uvw[1] = nv * ood;
   uvw[2] = 1.0f - uvw[0] - uvw[1];
}

// helper function used to compute triangles barycentric coordinates
public static float triArea2D(float x1, float y1, float x2, float y2, float x3, float y3) {
   return (x1 - x2) * (y2 - y3) - (x2 - x3) * (y1 - y2);  
}


Like mentioned above, I've used the same methods to create two Editor extensions for Unity in C#, one being a Slicer Framework (ability to slice objects) and another a Decal Framework (ability to place decals on any object surface). More details if interested can be found in my blog!

Being a Java coder by heart I thought this would be a good place to share some of the source, and hopefully some of you readers will find it useful for your applications!

Any feedback, comments, critics are all welcome  Grin

Pages: [1]
  ignore  |  Print  
 
 
You cannot reply to this message, because it is very, very old.

 

Add your game by posting it in the WIP section,
or publish it in Showcase.

The first screenshot will be displayed as a thumbnail.

rwatson462 (37 views)
2014-12-15 09:26:44

Mr.CodeIt (30 views)
2014-12-14 19:50:38

BurntPizza (61 views)
2014-12-09 22:41:13

BurntPizza (98 views)
2014-12-08 04:46:31

JscottyBieshaar (59 views)
2014-12-05 12:39:02

SHC (74 views)
2014-12-03 16:27:13

CopyableCougar4 (77 views)
2014-11-29 21:32:03

toopeicgaming1999 (137 views)
2014-11-26 15:22:04

toopeicgaming1999 (127 views)
2014-11-26 15:20:36

toopeicgaming1999 (37 views)
2014-11-26 15:20:08
Resources for WIP games
by kpars
2014-12-18 10:26:14

Understanding relations between setOrigin, setScale and setPosition in libGdx
by mbabuskov
2014-10-09 22:35:00

Definite guide to supporting multiple device resolutions on Android (2014)
by mbabuskov
2014-10-02 22:36:02

List of Learning Resources
by Longor1996
2014-08-16 10:40:00

List of Learning Resources
by SilverTiger
2014-08-05 19:33:27

Resources for WIP games
by CogWheelz
2014-08-01 16:20:17

Resources for WIP games
by CogWheelz
2014-08-01 16:19:50

List of Learning Resources
by SilverTiger
2014-07-31 16:29:50
java-gaming.org is not responsible for the content posted by its members, including references to external websites, and other references that may or may not have a relation with our primarily gaming and game production oriented community. inquiries and complaints can be sent via email to the info‑account of the company managing the website of java‑gaming.org
Powered by MySQL Powered by PHP Powered by SMF 1.1.18 | SMF © 2013, Simple Machines | Managed by Enhanced Four Valid XHTML 1.0! Valid CSS!