Jump to content
  • Advertisement
Sign in to follow this  
benryves

Ray/Face Intersection

This topic is 4273 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

If you intended to correct an error in the post then please contact us.

Recommended Posts

This is probably very easy and the sort of thing one could find with a 2 minute web search, but I'm a bit of a thicko when it comes to maths, sorry. [sad] I have a number of faces, each of which lie in a particular plane. I'm trying to move a point from A→B and detecting whether it hits a face as it moves (this is for objects in the game world - when spawned they float above the ground, and they are dropped to the floor by attempting to move them down 256 units). All of the planes are described as a normal and an offset from the origin. As far as I can tell, you can detect which side of a plane you're on by taking the dot product of a position and the plane's normal, then comparing that to the offset. For example,
static bool IsInFront(Vector3 position, Plane plane) {
    return Vector3.Dot(position, plane.Normal) > plane.Offset;
}

static bool IsBehind(Vector3 position, Plane plane) {
    return Vector3.Dot(position, plane.Normal) < plane.Offset;
}
I use this technique to detect which side of the level's BSP partition planes I'm on to calculate what sort of area I'm in (solid, water, lava and so on) so it appears to work. [smile] What I intended on doing was to first check if both points (source and destination) were on the same side of the face's plane, and if so to return (they obviously don't intersect the face). If they do lie on different sides of the plane, however, I'd then like to calculate the point intersection. Once I had that I could check it against the edges of the face to see if it lay inside or outside the face - and if it was I could finally return the point of intersection. My questions, therefore, are: how would you calculate the intersection point of a ray and a plane, and how would you check whether a point lay inside a face or outside it? (I can do the latter in 2D via the cross product and checking the z component of the result).

Share this post


Link to post
Share on other sites
Advertisement
Check out the SIGGRAPH ray-plane intersection page. It does a good job of explaining the test. There's only a slight modification for segments - if Rd is the unit direction from A to B, then you check to see if t is between 0 and ||B-A|| instead of just greater than 0.

As for detecting whether a point is inside a face or not, it really depends on what kind of face it is. You mentioned BSP trees so I'll assume they're convex at least. For simple triangles you could probably get away with calculating the barycentric coordinates of the point, and for other polygons you can use the half-plane method. That's where you create a series of planes that are perpendicular to the polygon plane, yet coincident with each edge, and do a series of front/back tests. Assuming you create the planes such that the normals all face inward, if all the tests return front then the point is inside the face, otherwise it isn't. One advantage of this method is that it works very well for polygons in 3D, since you don't have to project down to a 2D space to perform the test.

Share this post


Link to post
Share on other sites
Edit: The posted code had a bug in it, so I replaced it in case anyone found this thread. Some collisions worked fine, others didn't.

Thanks for the link, it was very helpful. [smile]

/// <summary>Calculate the collision of a point moving through the plane.</summary>
/// <param name="start">The starting position of the point.</param>
/// <param name="end">The desired end position of the point.</param>
/// <returns>Either the end point or the intersection point, depending on whether the point hits the plane or not.</returns>
public Vector3 GetCollision(Vector3 start, Vector3 end) {

// Get the distance along of the intersection:
Vector3 FacingNormal = -this.Normal;
float Distance = -(Vector3.Dot(start, FacingNormal) + this.Offset) / Vector3.Dot(end - start, FacingNormal);

// Check range:
if (Distance < 0 || Distance > 1) {
// Intersection point happens behind or in front of the ends of the line.
// This means that either the line isn't long enough to make contact with the plane, or that the
// line doesn't hit the plane at all (ie, it lies parallel to it).
return end;
} else {
// We intersect the line somewhere along its length.
return start + (end - start) * Distance;
}
}


Yes, faces are convex (sorry for not mentioning that). Your second method sounds exactly like what I was after.

Addendum: For detecting whether the point lies inside the face or not I check each edge, taking the cross product of the edge vector and the offset of the point from the first edge's vertex. This gives a normal that will point one way if the point is inside the face, the other way if it is outside. I then take the dot product of this value for each edge. If the result is > 0 or < 0 for all faces, then the point is inside; if there's a mixure of > 0 and < 0 then it lies outside.



It appears to work quite well, at any rate.

[Edited by - benryves on September 12, 2007 4:13:31 AM]

Share this post


Link to post
Share on other sites
Sign in to follow this  

  • Advertisement
×

Important Information

By using GameDev.net, you agree to our community Guidelines, Terms of Use, and Privacy Policy.

GameDev.net is your game development community. Create an account for your GameDev Portfolio and participate in the largest developer community in the games industry.

Sign me up!