Java-Gaming.org Hi !
 Featured games (90) games approved by the League of Dukes Games in Showcase (683) Games in Android Showcase (196) games submitted by our members Games in WIP (751) games currently in development
 News: Read the Java Gaming Resources, or peek at the official Java tutorials
Pages: [1]
 ignore  |  Print
 Triangle Intersection Tests  (Read 9024 times) 0 Members and 1 Guest are viewing this topic.
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 ppublic 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-cpublic 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 occurspublic 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 foundpublic 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 planepublic 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 coordinatespublic 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

Pages: [1]
 ignore  |  Print

You cannot reply to this message, because it is very, very old.

 orrenravid (221 views) 2016-07-16 03:57:23 theagentd (291 views) 2016-07-11 14:28:54 Hydroque (379 views) 2016-07-06 05:56:57 Hydroque (530 views) 2016-07-03 08:52:54 GrandCastle (400 views) 2016-07-01 09:13:47 GrandCastle (393 views) 2016-07-01 09:09:45 CopyableCougar4 (446 views) 2016-06-25 16:56:52 Hydroque (421 views) 2016-06-22 02:17:53 SwampChicken (386 views) 2016-06-20 13:22:57 SwampChicken (306 views) 2016-06-20 13:22:49
 Archive 30x Slyth2727 24x Brynn 23x EgonOlsen 22x orangepascal 22x TritonDreyja 21x orange451 20x DavidBVal 19x Spasi 18x KaiHH 11x LiquidNitrogen 11x Phased 11x Opiop 11x princec 11x Longor1996 10x ziozio 10x
 Making a Dynamic Plugin Systemby Hydroque2016-06-25 00:13:25Java Data structures2016-06-13 21:22:09Java Data structures2016-06-13 21:20:42FPS Camera Tutorialby Hydroque2016-05-22 05:40:58Website offering 3D Models specifically for games for freeby vusman2016-05-18 17:23:09Website offering 3D Models specifically for games for freeby vusman2016-05-09 08:50:56Website offering 3D Models specifically for games for freeby vusman2016-05-06 11:10:21Website offering 3D Models specifically for games for freeby vusman2016-04-29 12:56:17
 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