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.
// 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
// 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.
// 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
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
// 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.
// 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.
// 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 ;D