Triangle in frustum
Author
How to check if a triangle is inside/intersecting a view frustum?
If that's heavy to calculate, I can also check if a box is inside (box without rotations), maybe that's easier. But I triangle would be more accurate in my case.
For culling purposes, I need to check which portals are inside the viewers camera frustum. Portals are made of a couple of polygons in my case, so that's why I need to check.
Greetings,
Rick
Probably the easiest way would be to transform the polygons into projection space, since your view frustum then becomes a nice cube. Then you check to see if all the points have a common coordinate that is outside the same extent of this cube, i.e. check to see if all the X values are less than -1, or all the X values are greater than 1. Repeat for Y and Z (noting that Z has a different range for OpenGL and DirectX). If this isn't the case, then the polygon intersects the view frustum.
Quote:Original post by ZipsterTechnically, there are cases where the triangle/polygon does not intersect the frustum and yet the above test will return true. This is generally ok though, as these cases are relatively rare, and frustum tests are usually allowed to be conservative (although the implications of this may be different for culling a portal than for culling a renderable object).
Then you check to see if all the points have a common coordinate that is outside the same extent of this cube, i.e. check to see if all the X values are less than -1, or all the X values are greater than 1. Repeat for Y and Z (noting that Z has a different range for OpenGL and DirectX). If this isn't the case, then the polygon intersects the view frustum.
One other note to the OP: the test described above can also be performed in world space (by testing the vertices against the world-space planes of the frustum).
Author
It doesn't have to be 100% accurate, so if there are rare cases where the result is not always correct, it's not a problem.
I'm not good with matrices and stuff, but if I understand it right I multiply the 3 vertices of a polygon with the modelView matrix (I'm using OpenGL). Then I have to check if all x/y/z coordinates are between -1 and +1... Or is it a little bit different; checking if NOT all x/y/z are <-1 or >+1? What is the range for Z by the way?
Thanks for helping,
Rick
I'm not good with matrices and stuff, but if I understand it right I multiply the 3 vertices of a polygon with the modelView matrix (I'm using OpenGL). Then I have to check if all x/y/z coordinates are between -1 and +1... Or is it a little bit different; checking if NOT all x/y/z are <-1 or >+1? What is the range for Z by the way?
Thanks for helping,
Rick
Quote:Original post by spek
I'm not good with matrices and stuff, but if I understand it right I multiply the 3 vertices of a polygon with the modelView matrix (I'm using OpenGL). Then I have to check if all x/y/z coordinates are between -1 and +1... Or is it a little bit different; checking if NOT all x/y/z are <-1 or >+1? What is the range for Z by the way?
You want to get them all the way into perspective space, so you need to multiply by both the modelview and projection matrices. After that, you check to see if any single coordinate is completely outside of its range. For example, X has a range of -1 to 1. So if all the X values of the points are either less than -1, or they're all greater than 1, the triangle is outside the view frustum. Then do the same for Y -- if all the Y values are less than -1, or all the Y values are greater than 1, the triangle is outside the frustum. Repeat for Z, which has the same range (-1 to 1) in OpenGL as X and Y.
And as jyk mentioned, this is a conservative test that will sometimes return false positives, i.e. say that some triangles are inside the frustum when they aren't. You can alleviate this a little by performing the reverse check, making sure that the view frustum is completely on one side of the triangle plane. However this will also return some false positives in rare cases, since it's just short of a full SAT test, which would handle everything.
Author
Call me an idiot, but I'm still not doing it right.
It's Delphi code, but I think you get the point. Am I still using the wrong matrix? I check the transformed coordinates, but they don't seem to be between -1..+1 when they are insight my view.
Thanks for helping!
Rick
function polyInsideFrustum( const v1,v2,v3 : Vector3f ) : boolean;var projMat, mvMat : Matrix4f; perMat : Matrix4f; p1,p2,p3 : Vector3f;begin { Check if the poly is inside the view frustum } { Get perspective matrix } glGetFloatv( GL_PROJECTION_MATRIX, @projMat ); glGetFloatv( GL_MODELVIEW_MATRIX , @mvMat ); perMat := MatrixMultiply(mvMat, projMat); { Bring polygon coordinates into perspective space } p1 := VectorTransform( v1, perMat ); // v1 * perMat p2 := VectorTransform( v2, perMat ); p3 := VectorTransform( v3, perMat ); { Check if the coordinates are in the range } result := not ( { X } ((p1[0] <-1) and (p2[0] <-1) and (p3[0] <-1) ) or ((p1[0] >+1) and (p2[0] >+1) and (p3[0] >+1) ) or { Y } ((p1[1] <-1) and (p2[1] <-1) and (p3[1] <-1) ) or ((p1[1] >+1) and (p2[1] >+1) and (p3[1] >+1) ) or { Z } ((p1[2] <-1) and (p2[2] <-1) and (p3[2] <-1) ) or ((p1[2] >+1) and (p2[2] >+1) and (p3[2] >+1) ) );end;It's Delphi code, but I think you get the point. Am I still using the wrong matrix? I check the transformed coordinates, but they don't seem to be between -1..+1 when they are insight my view.
Thanks for helping!
Rick
Is your matrix multiplication in the correct order? It should be projMat*mvMat*point.
Also, I just remembered that to do clipping tests for triangles, you need to use homogeneous coordinates. Instead of checking to see if X/Y/Z are outside the [-1,1] range, you should check to see if they're outside the [-W,W] range. So you'll need to use proper 4D matrix/vector multiplication instead of VectorTransform. Other than that everything should work.
Also, I just remembered that to do clipping tests for triangles, you need to use homogeneous coordinates. Instead of checking to see if X/Y/Z are outside the [-1,1] range, you should check to see if they're outside the [-W,W] range. So you'll need to use proper 4D matrix/vector multiplication instead of VectorTransform. Other than that everything should work.
Author
No success yet. I reversed the order in "m := MatrixMultiply(mvMat, projMat);", but no good results either. The matrices are 4D, the vertex points as well now. The W is '1' for each point.
The "vectorTransform" function looks like this:
With "projMat * mvMat", the W of the transformed point is constantly '-2'. When doing the multiplication reversed, the W changes somewhere between 0 and 6. Don't know if that's good, but it doesn't seem to be between [-1,+1] when the polygon is inside my view.
Greetings,
Rick
The "vectorTransform" function looks like this:
Result[X]:=V[X] * M[X, X] + V[Y] * M[Y, X] + V[Z] * M[Z, X] + V[W] * M[W, X];Result[Y]:=V[X] * M[X, Y] + V[Y] * M[Y, Y] + V[Z] * M[Z, Y] + V[W] * M[W, Y];Result[Z]:=V[X] * M[X, Z] + V[Y] * M[Y, Z] + V[Z] * M[Z, Z] + V[W] * M[W, Z];Result[W]:=V[X] * M[X, W] + V[Y] * M[Y, W] + V[Z] * M[Z, W] + V[W] * M[W, W];With "projMat * mvMat", the W of the transformed point is constantly '-2'. When doing the multiplication reversed, the W changes somewhere between 0 and 6. Don't know if that's good, but it doesn't seem to be between [-1,+1] when the polygon is inside my view.
Greetings,
Rick
Yeah, a lot of this is going to depend on which conventions you're using for your matrices and vectors. The post-multiplication (row vector) order would be point*mvMat*projMat, while the pre-multiplication (column vector) order would be what I gave before. In either case, note that the modelview matrix is "closer" to the vector, while the projection matrix is "farther". I also assumed a consistency in convention, i.e. that you're either using column vectors with column-major matrices, or row vectors with row-major matrices, since you don't appear to be transposing whenever you interface with OpenGL.
The W value is actually the camera-space depth of the point, so it shouldn't remain constant if you're moving and rotating the camera. It's probably a math issue though. The last resort would be to do all this in world-space, thereby avoiding the transformations, but I'm personally not a huge fan since each one of those comparisons against W turns into a point-plane test.
The W value is actually the camera-space depth of the point, so it shouldn't remain constant if you're moving and rotating the camera. It's probably a math issue though. The last resort would be to do all this in world-space, thereby avoiding the transformations, but I'm personally not a huge fan since each one of those comparisons against W turns into a point-plane test.
Author
Ok, I got it working now. Not exactly as you said thoug, I used the other approach by checking if a point is between the 6 planes that define the frustum.
However, there comes yet another problem. Now I check if at least one of the 3 triangle vertices is inside the frustum. Ifso, the polygon is visible. But there are cases that all 3 points are outside the frustum, while the polygon itself is visible. When the polygon is very large, or you're really close to it, it might intersect the frustum, but the points are all outside.
How to check that? By the way, this problem would also occur in your solution right?
Greetings and thank for helping,
Rick
However, there comes yet another problem. Now I check if at least one of the 3 triangle vertices is inside the frustum. Ifso, the polygon is visible. But there are cases that all 3 points are outside the frustum, while the polygon itself is visible. When the polygon is very large, or you're really close to it, it might intersect the frustum, but the points are all outside.
How to check that? By the way, this problem would also occur in your solution right?
Greetings and thank for helping,
Rick
This topic is closed to new replies.
Advertisement
Popular Topics
Advertisement
