CODEWITHSUNDEEP
javavector3dlineintersection
Geosearchef
Geosearchef

Reputation: 648

Calculate if a line intersects a face

I'm writing an 3D application. I have to deteminate at which face the user is currently looking (not always axis aligned).

I have the position of each face as four points. I have the line as a vector.

I've looked up that i can calculate the normal of the face and with that the equation(s) of the face. I can also calculate the equation of the line.

If i merge those i am able to calculate the intersection point (on the plane) and then look if that point is on the face. But how do i solve those equations in code?

How can i simply calculate if the line intersects with the face?

Edit: How can i solve these equations using java code?

 Equations of Line
 x = point.x - dir.x * t
 y = point.y - dir.y * t
 z = point.z - dir.z * t

 Equation of Plane
 normal.x * (x - face[0].x) + normal.y * (y - face[0].y) + normal.z * (z - face[0].z) = 0

Upvotes: 2

Views: 1911

Answers (2)

Geosearchef
Geosearchef

Reputation: 648

Thanks for all answers. I now solved it. If someone who has the same problem still needs the equations i'm posting them here:

/*
     * EQUATIONS OF LINE
     * x = point.x - dir.x * t
     * y = point.y - dir.y * t
     * z = point.z - dir.z * t
     * 
     * 
     * EQUATION OF PLANE
     * normal.x * (x - face[0].x) + normal.y * (y - face[0].y) + normal.z * (z - face[0].z) = 0
     * 
     * ax + by + cz = d
     * 
     * a = normal.x
     * b = normal.y
     * c = normal.z
     * d = (-face[0].x * normal.x - face[0].y * normal.y - face[0].z * normal.z) * -1
     * 
     * MERGE THEM
     * normal.x * x + normal.y * y + normal.z * z = (-face[0].x * normal.x - face[0].y * normal.y - face[0].z * normal.z) * -1
     * Deploy
     * normal.x * (point.x - dir.x * t) + normal.y * (point.y - dir.y * t) + normal.z * (point.z - dir.z * t) = (-face[0].x * normal.x - face[0].y * normal.y - face[0].z * normal.z) * -1
     * Multiply out
     * (normal.x * point.x) - (normal.x * dir.x * t) + (normal.y * point.y) - (normal.y * dir.y * t) + (normal.z * point.z) - (normal.z * dir.z * t) = (-face[0].x * normal.x - face[0].y * normal.y - face[0].z * normal.z) * (-1)
     * 
     * Reshaping
     * -(normal.x * point.x) + (normal.x * dir.x * t) - (normal.y * point.y) + (normal.y * dir.y * t) - (normal.z * point.z) + (normal.z * dir.z * t) = (-face[0].x * normal.x - face[0].y * normal.y - face[0].z * normal.z)
     * (normal.x * dir.x * t) + (normal.y * dir.y * t) + (normal.z * dir.z * t) = (-face[0].x * normal.x - face[0].y * normal.y - face[0].z * normal.z) + (normal.x * point.x) + (normal.y * point.y) + (normal.z * point.z)
     * t * ((normal.x * dir.x) + (normal.y * dir.y) + (normal.z * dir.z)) = (-face[0].x * normal.x - face[0].y * normal.y - face[0].z * normal.z) + (normal.x * point.x) + (normal.y * point.y) + (normal.z * point.z)
     * t = ((-face[0].x * normal.x - face[0].y * normal.y - face[0].z * normal.z) + (normal.x * point.x) + (normal.y * point.y) + (normal.z * point.z)) / ((normal.x * dir.x) + (normal.y * dir.y) + (normal.z * dir.z))
     * 
     */

Upvotes: 0

Dici
Dici

Reputation: 25950

You can first check if the line intersects the plane containing your face (it is a very simple linear system). If the intersection I exists, and your face is ABCD, you can compute the barycentric coordinates (alpha,beta) of I in ABC. If alpha or beta < 0 meaning that ABC does not contain I), do the same thing with BCD.

To sum up (in pseudo-code) :

// no intersection, or the line belongs to the plane. Treat both in the same way.
if (line is parallel to the plane) return false

I = intersection(line,plane(A,B,C))
(a,b) = barycentricCoordinates(i,triangle(A,B,C))

if (a >= 0 and b >= 0) return true
(c,d) = barycentricCoordinates(i,triangle(B,C,D))
return c >= 0 and d >= 0

I don't know if it is optimal in terms of performance, but mathematically it works.

EDIT : how exactly do you compute I ?

To do this, it is more comfortable to work with the cartesian representation of the plane (ABC) and the line L = (U,P) where U is the directing vector (u,v,w) and P a point (x0,y0,z0) belonging to L.

  • first, find the normal vector N = (a,b,c) of (ABC). (ABC)'s equation then is (E0) : a.x + b.y + c.z + d = 0. Determine d by injecting the coordinates of A in this equation.

  • the equation of L is (E1) : (x,y,z) = (x0,y0,z0) + lambda.(u,v,w)

Now, if U.N = 0, then the line is parallel to the plane, we consider there is no intersection. Otherwise, we can inject (E1) in (E0) to determine lambda :

lambda = - (a.x0 + b.y0 + c.z0 + d) / (a.u + b.v + c.w)

Following this, you can compute the coordinates of the point I using this value of lambda in (E1).

Upvotes: 4

Related Questions