PDA

View Full Version : Mouse testing triangles in clip space

bsupnik
09-30-2013, 08:21 PM
Hi Y'all,

I wrote some code a while ago to click-test and marquee select 3-d triangles in viewport space; to test the triangles of my 3-d model, I apply the combined mode-view + projection matrix, perspective divide, and then the triangle test is easy and cheap, because it's basically 2-d. The transformed Z coordinate provides ordering to select the nearest triangle. It seemed like a good idea at the time.

Recently I hit an unfortunate fail case: if the triangle being tested goes through the near clip plane and behind the camera, the vertex with positive Z (in eye coordinates) becomes flipped after perspective divide, causing my 2-d triangles tests to fail pretty badly.

My best band-aid idea right now is to clip the triangle against the near clip plane...but I was wondering...

1. Is it possible to do a triangle-ray intersection test entirely in clip space (using homogeneous coordinates) and
2. If the triangle goes behind the camera, will the intersection test produce something useful (e.g. an intersection point that can be clearly identified as fictitious if the unclipped part of the triangle doesn't intersect the test point) and
3. If the intersection actually is useful, are there more optimized hit-tests than intersecting the triangle's supporting plane and then checking the returned point? (For example, is it possible to find the barycentric coordinate of the intersection if the inputs are all in homogeneous coordinates)?

I did a bunch of googling but didn't find anyone doing intersection tests except in cartesian coordinates.

Thanks!
Ben

Dark Photon
10-04-2013, 03:32 PM
Yeah, doing the perspective divide when you're not sure that you've got points that are in-frustum (or at least in front of the eye) is ill-defined. AFAIK, you need to do an in-frustum test before that (i.e. before NDC).

What you can do is do an in-frustum test with the tri's 3 clip-space points:

-w <= x,y,z <= w

If they're all in, you can just do what you're doing -- simple and cheap. And if they're all outside the same plane, just ditch the triangle. But if not one of these simple cases, you've gotta have some way to handle the clipping issue. Seems like you can do a vector-tri intersection tests in either clip-space or eye-space, and then then do an in-frustum test on the hit point. Discard if not.

Or you can as you suggest and always do the vector-tri intersection tests in clip space.

To intersect in homogenous clip-space, recall the plane equation in 3D:

A*X + B*Y + C*Z + D = 0

Now plug in homogenous coords and you have it in 4D:

A*(x/w) + B*(y/w) + C*(z/w) + D = 0
aka A*x + B*y + C*z + D*w = 0
aka P * (x,y,z,w) = 0 where P = (A,B,C,D), * = dot product

Now plug the equation of a line:

p(t) = (p2-p1)*t + p1

into it:

t = (-P * p1) / (P * p2 - P * p1)

3 dot products, a subtract, and a divide. And can prob simplify the bottom as (P*v), where v=(p2-p1), to get rid of a dot product.

Assuming you chose your vector start point (p1) on the near clip and v pointing into the frustum, then if your denominator is 0 or t < 0, then you can't have an in-frustum plane intersect. Otherwise you can, so plug in t, do the cheap in-frustum test on the resulting 4D point (-w <= x,y,z <= w), and if it passes do a cheap 2D in-triangle test on it.

For this latter intersect-point frustum test, you probably don't need to check x and y, because you "know" you're shooting a vector that's in-frustum in x and y already.

There may be more efficient ways but that's what comes to mind.

bsupnik
10-04-2013, 03:38 PM
Right -- for now my work-around is: I am testing for near-plane intersection in clip space, clipping the triangle first, then intersecting, then converting to NDC, which works.

What I'm looking for is the math to do a triangle-ray intersection in clip space - the math would have to be correct for homogeneous coordinate systems, I think.

Dark Photon
10-04-2013, 04:43 PM
What I'm looking for is the math to do a triangle-ray intersection in clip space

I didn't expect you to read that so fast :D -- had edited my comment above with the math for that before I noticed your follow-up.

bsupnik
10-04-2013, 04:49 PM
I didn't expect you to read that so fast :D -- had edited my comment above with the math for that before I noticed your follow-up.

Thanks for the math...I'm having a face-palm moment. In my previous exploration it looked like I could do a ray-plane intersection but I didn't have a good way to get the UV coords to determine if I was in-tri.

But of course, your comment is exactly right - I really don't need to. The ray-plane test is good enough to know if I am on the right side of the frustum and then I either reject, or it's safe to divide. :-)

Thanks for the help!
Ben