Archived

This topic is now archived and is closed to further replies.

CoderTCD

triangle in frustrum?

Recommended Posts

Once you see it, it means it''s inside the frustum . More seriously, matter is complicated mathematically. Actually you know eye position (vector e) and the point you look at (vector l) and a result of difference

v = (l-e)

is a vector v collinear with axis of frustum. Now you need to know far and near and some other parameters to construct frustum in 3d space and using certain mathematical methods check for some eventual intersections. As i said, it is non-trivial task and i don''t think I can present the solution of it in conceited way using this editor.

Best regards
rafalp

Share this post


Link to post
Share on other sites
It's not simple!!! However If you are intersted about 3d (OpenGL, D3D, ...) you need your own math classes/function.
Check for a triangle in frustum is the same to clip a polygon against a frustum and check if it's empty (out) or not (in).

First, you need a view frustum (six planes delimiting your FOV). There are different methods to do this. You can for example get the coordinates left, right, bottom, top on the znear plane that are mapped on the viewport and znear, zfar values (from PROJECTION_MATRIX you can obtain these values...see OpenGL reference for details).

Transform every plane accordingly to your viewer orientation/position...note that you need special formulas to transform plane and d coefficient with your viewer matrix.

When you have your frustum you need to apply the algorithm

for every plane i in frustum
polygon = ClipPolygon(plane, polygon)

if(polygon.IsEmpty())
polygon is out

The plane-polygon clip algorithm is the same you know from BSP...
in this algorithm you split your polygon in two new polygons(front and back) but in this case we can discard the back one.

Difficult? You asked...












[edited by - blizzard999 on October 21, 2003 6:28:35 PM]

Share this post


Link to post
Share on other sites
yes difficult reallly.. I didn''t really understand your way..
I found a frustrum code from gametutorials..
it can find out if a point is in frustrum. it checks if the distance between all frustrum planes are positive (this means the point is inside). But when checking a triangle there''s another problem.
I can check for 3 vectors if there''re in frustrum. but maybe all 3 are out of frustrum and triangle is still in. do you have any idea about this possibility?
or do you have any example code?
thanks for your concern

serdar

Share this post


Link to post
Share on other sites
Check if a point is in frustum is very simple; if the point lies in front of every plane it''s int otherwise it''s out.
Given a triangle...if every vertex is inside the frustum, the triangle (and in general a convex polygon) is in but you can''t say too much...you must test for an intersection between your triangle and your frustum.
The intersection is a sub-polygon that lies entirely in the frustum.
The algorithm is very very simple



INT Frustum::ClipPolygon(const Polygon& polygon, Polygon& clippolygon)const
{

// I create some (compatible-)copy

Polygon poly(polygon);
Polygon clippoly(polygon.GetVertexType());
Polygon outpoly(polygon.GetVertexType());

// Entirely in ?

bool bIn = true; // interamente contenuto?


// for every plane and if the polygon is not completely out

for(SIZET i=0; i<GetPlaneNumber() && poly.GetVertexNumber(); i++)
{
// I use plane i to split poly

if(GetPlane(i).SplitPolygon(poly, clippoly, outpoly)!=AC_FRONT)
{
bIn = false;
}

// take frontpolygon and discard the previous and the back one

poly = clippoly;
}

clippolygon = poly;

// 3 results : IN (entirely), OUT , INTERSECT

return(poly.GetVertexNumber()?(bIn?AC_IN:AC_INTERSECT):AC_OUT);
}



How to clip the polygon against a plane ?



INT Plane::SplitPolygon(const Polygon& polygon, Polygon& frontpolygon, Polygon& backpolygon)const
{

Polygon* pPoly1 = &frontpolygon;
Polygon* pPoly2 = &backpolygon;

pPoly1->RemoveAll();
pPoly2->RemoveAll();

// we add vertices to pPoly1 and pPoly2


SIZET n = polygon.GetVertexNumber();

if(!n)
{
return(AC_FRONT);
}

bool bBack = false;
bool bIntersect = false;

// check first vertex

if(!IsInFront(polygon.GetCoord(0)))
{
// we start with back

SwapObjects(pPoly1, pPoly2);
bBack = true;
}

// for every segment

for(SIZET i=0; i<n; i++)
{
Vertex A = polygon.GetVertex(i);
Vertex B = polygon.GetVertex((i+1)%n);

if(IsInFront(A.m_coord) != IsInFront(B.m_coord))
{
// simply compute line intersection with this plane

// we are sure that it exists

REAL f;
LineIntersection(Line(A, B), &f);
Vertex C = Vertex::Interpolate(A, B, f);

pPoly1->Push(C);
pPoly2->Push(C);
SwapObjects(pPoly1, pPoly2);
bIntersect = true;
}

pPoly1->Push(B);

}

return(bIntersect?AC_INTERSECT:(bBack?AC_BACK:AC_FRONT));
}



Now you can ask how to compute line-plane intersection?
Simply create a ray on your line and check if the intersection exixts and it is in the range [0,1].

How to intersect a ray with a plane ?



INT Plane::RayIntersection(const Ray& ray,REAL* param)const
{
if(*this||ray) // parallel ?

{
if(this->Contains(ray)){
return(AC_INF);
}
else{
return(AC_NONE);
}
}

REAL t;

Vector N = m_normal; // plane normal (plane has N and d)


Vector v = ray.m_dir; // ray vector (ray has dir and p0)


REAL Nv = N*v; // note that Nv=0 is equal to parallelism

if(!Math::IsSmall(Nv)){
t = - (N * ray.m_p0 + m_d)/Nv;
}
else{
t = (REAL)0; // unreachable...

}

if(param!=NULL){
*param = t;
}

return(AC_INTERSECT);
}




I rewritten the code and never checked however it seems simple and you should be able to get some idea...

Share this post


Link to post
Share on other sites
Another problem is to create a view-frustum...when you have your view frustum you can use the method (because it''s a frustum).

How to create a view-frustum?

You need l,r,b,t,n,f of your projection (and you know how )

These values indentify 4 points (ABCD)(viewport in 3d coordinate) and zfar
Create the planes containing for example OAB, OBC, OCD, ODA plus plane z=-znear and z=zfar (please use a paper to draw the frustum and pay attention to cross-products...). Every plane must have a normal that points inside your frustum.
For example your viewer is in the origin so it''s behind znear but in front of zfar!

Now your viewer is not in the origin! And you are looking somewhere so you must transform your frustum!
Transform every plane by your view matrix; I use my own camera matrix but I suppose it''s the same to use the MODELVIEW_MATRIX that describe your viewer (for example after a gluLookAt())



Plane& Plane::Transform(const Matrix& matrix)
{
Vector n = m_normal;
REAL d = m_d;

Vector n1 = matrix.GetNormalTransform() * n;
REAL d1 = n1 * (matrix * n * d / n.Len2());

m_normal = n1;
m_d = d1;

return(*this);
}



Note that you should use a special matrix to transform matrix (OpenGL use a special matrix when you pass normals for lightning)

What is this matrix? It''s similar to the inverse of the linear (3x3) sub matrix


Matrix Matrix::GetNormalTransform(void)const
{
// m will points to a REAL16 array (cast operator)

REAL* m = _tmpMat.LoadIdentity();

const REAL* mt = *this;

m[0|(0<<2)]=mt[1|(1<<2)]*mt[2|(2<<2)]-mt[1|(2<<2)]*mt[2|(1<<2)];
m[0|(1<<2)]=mt[1|(2<<2)]*mt[2|(0<<2)]-mt[1|(0<<2)]*mt[2|(2<<2)];
m[0|(2<<2)]=mt[1|(0<<2)]*mt[2|(1<<2)]-mt[1|(1<<2)]*mt[2|(0<<2)];
m[1|(0<<2)]=mt[2|(1<<2)]*mt[0|(2<<2)]-mt[2|(2<<2)]*mt[0|(1<<2)];
m[1|(1<<2)]=mt[2|(2<<2)]*mt[0|(0<<2)]-mt[2|(0<<2)]*mt[0|(2<<2)];
m[1|(2<<2)]=mt[2|(0<<2)]*mt[0|(1<<2)]-mt[2|(1<<2)]*mt[0|(0<<2)];
m[2|(0<<2)]=mt[0|(1<<2)]*mt[1|(2<<2)]-mt[0|(2<<2)]*mt[1|(1<<2)];
m[2|(1<<2)]=mt[0|(2<<2)]*mt[1|(0<<2)]-mt[0|(0<<2)]*mt[1|(2<<2)];
m[2|(2<<2)]=mt[0|(0<<2)]*mt[1|(1<<2)]-mt[0|(1<<2)]*mt[1|(0<<2)];

return(_tmpMat);
}



If you apply this matrix to a normal and the matrix is not a roto-translation the normal need a renormalization bur you dont need to have normals ''normalized'' in your plane transform because
you recompute d accordingly.

Share this post


Link to post
Share on other sites
quote:
Original post by blizzard999
Check if a point is in frustum is very simple; if the point lies in front of every plane it''s int otherwise it''s out.
Given a triangle...if every vertex is inside the frustum, the triangle (and in general a convex polygon) is in but you can''t say too much...you must test for an intersection between your triangle and your frustum.
The intersection is a sub-polygon that lies entirely in the frustum.
The algorithm is very very simple


Clipping the polys to each plane would work, but is more work than nessisary, especially if using OpenGL, since it will do clipping for you.

All you really need is a simple in/out test, the Cohen-Sutherland can be extended to 3d quite simply for this

Share this post


Link to post
Share on other sites
quote:
Original post by OrangyTang
Clipping the polys to each plane would work, but is more work than nessisary, especially if using OpenGL, since it will do clipping for you.

All you really need is a simple in/out test, the Cohen-Sutherland can be extended to 3d quite simply for this



You see I've posted tons of code and added some comment in english...
You came here and wrote bullshits (to appear intelligent?) without any idea about what we was talking about! Good!

I written software renderers (with texture mapping and lightning) in C, C++ and java and yes I've used Cohen-Sutherland to clip polygon in 2d space againt viewport.
So i know this algorithm. Have you read my code? Probably not!

You have understood nothing!!! These algorithm are the basis of 3d (BSP, portals, view-frustum-culling,...)
Apply culling on every triangles is not efficient but you can apply culling on quadtree, octree, portals,...and clip out thousands triangles...and collisons? OpenGL resolve collisions for you?

[edited by - blizzard999 on October 22, 2003 7:27:06 PM]

[edited by - blizzard999 on October 22, 2003 7:28:19 PM]

Share this post


Link to post
Share on other sites
OrangyTang is quite correct. There is no need to clip the polygon like your code demostrates.

In fact, there''s no need to use the plane equations at all. You could just perform the calculation in post-perspective space (after multiplying the vertices by the MVP matrix); that way you''re just testing against an axis-aligned cube.

Either way, blizzard999, if you have a point to make, you''re not going about it in the right way. If you have something valid to say, say it, don''t just be gratuitously offensive.

Share this post


Link to post
Share on other sites
quote:
Original post by blizzard999
You see I''ve posted tons of code and added some comment in english...
You came here and wrote bullshits (to appear intelligent?) without any idea about what we was talking about! Good!

If you know of any technical error in my above post feel free to point them out, I''m always willing to learn more.


quote:
I written software renderers (with texture mapping and lightning) in C, C++ and java and yes I''ve used Cohen-Sutherland to clip polygon in 2d space againt viewport.
So i know this algorithm. Have you read my code? Probably not!

I have read your posts and looked at the code. I see no reason to study your code in great detail - the simple fact is that you don''t need to do a full blown clipping routine just for a simple in view frustum check. You perhaps feel I should have included vast amount of code in my own reply? But why? Any off-the-cuff code written by me will not be as clear or descriptive than the numerous samples to be found via google.


quote:
You have understood nothing!!! These algorithm are the basis of 3d (BSP, portals, view-frustum-culling,...)
Apply culling on every triangles is not efficient but you can apply culling on quadtree, octree, portals,...and clip out thousands triangles...and collisons? OpenGL resolve collisions for you?

I will skip over these and the earlier personal insults. I will however say that when a poster comes asking for frustum culling then i see no point in giving them incorrect advice.

Share this post


Link to post
Share on other sites
I absolutely love how people make the simplest tasks overly complex. The first answer should be:
If any of the points of the triangle is in the frustum then the triangle is in the frustum.
Then, if he doesn't know how to do frustum stuff, he can ask with a follow up question

EDIT: Blizzard there's no point in splitting polygons when doing view tests, I don't care who you are or what you've done.

[edited by - Shadow12345 on October 22, 2003 9:44:03 PM]

[edited by - Shadow12345 on October 22, 2003 10:56:48 PM]

Share this post


Link to post
Share on other sites
quote:

If any of the points of the triangle is in the frustum then the triangle is in the frustum.



Shadow: that''s not sufficient. You can have one point that''s above the top edge of the screen, and another point that''s to the left of the left edge of the screen, and a third point that''s below the bottom of the screen. The triangle covers half the screen, but none of its points (vertices) are in the frustum.

Triangle-frustum intersection, as featured in many real games:
If at least one vertex is inside the frustum, the triangle is inside.
If a single plane clips out ALL the vertices of a triangle, it is outside.
Else say that it''s too expensive to test whether it''s inside or outside, and assume it''s inside.

And, of course, like other posters have said, you don''t cull a single triangle; you cull an entire mesh (or a specific vertex buffer) by testing its bounding volume (sphere or box) against the frustum. Sphere is simpler, but less tight fitting.

Saying that you can test in post-projective space is still not good enough, because a bounding volume (sphere, box, etc) stretches and becomes irregular in shape after projection.

Share this post


Link to post
Share on other sites
yeah all of the points need to be behind a single frustum plane in order to be culled. What I said was right just not complete. I initially had that problem with bounding boxes of bsp leaves.

[edited by - Shadow12345 on October 22, 2003 12:27:55 AM]

Share this post


Link to post
Share on other sites
quote:
Original post by hplus0603

Saying that you can test in post-projective space is still not good enough, because a bounding volume (sphere, box, etc) stretches and becomes irregular in shape after projection.


at least for a box or sphere thats ok (though in the end im testing a cube around the sphere and not the sphere itself). a point wont be distorted and the same "1+ inside -> visible, all outside one plane -> not visible" still works. though im only doing the first half and compare the x,y,z coords with near/far +/-ylimit (=z*tan(fovy/2) and +/- ylimit*aspect. compared to typical frustum test its 3 less planes to calc the distance and no frustum extraction/transform. though paid for by loosing a little precision with spheres.

and no, throwing a ton of code at someone isnt really helpful, especially if that makes him actually USE a ton of code to cull a lousy triangle. so as long as coder doesnt need this for his own software renderer to really do the clipping himself that "ton of code" was nothing but confusing to him.

Share this post


Link to post
Share on other sites
Bla bla bla...

Everyone talk about BSP, view-frustum, ... and no one that gives some good ideas (have you ever tried to resolve these problems?)

This is the only way to perform a polygon-in-frustum test (it''s not an idea of mine of course...).

In (Un)real engines, portals are polygons that links different sectors...to choose the set of visible polygons to be rendered the engine starts with a view frustum and render every polygon in that sector that is inside the frustum (perhaps fast culling).
When it encounters a portal-polygon, the portal is clipped exactly against the view-frustum; it creates a new frustum (a shadow frustum) on the clipped polygon. This new frustum is used to render the linked sector recursively...

Previous engines used extensively BSP

If you are going to implements realistic lightning (real-time, off-line) you need this kind of test.

Share this post


Link to post
Share on other sites
I thank all of you for your discussion about my question. After reading all I understood that checking triangle-frustrum is not very easy. it''s not easy to prove the triangle is in but it''s very easy to prove it''s out. Maybe I could write a istriangleoutoffrustrum function ). so I''m going to send some unnecessary triangles but it''s less expensive than tones of CPU... ofcourse I won''t check for every triangle in the screen that would be stupid .

serdar

Share this post


Link to post
Share on other sites
actually you have to clip a polygon to proove it is inside the frustrum

imagine the case where all vertices are outside but one edge of the polygon intersects 2 frustrum planes

so the proper way is performing a RAY-FRUSTRUMPLANE test

correct me if i am wrong with my statement but i am pretty sure it s correct

P.S.:correct me with a normal tone

Share this post


Link to post
Share on other sites
quote:
Original post by Basiror
actually you have to clip a polygon to proove it is inside the frustrum

imagine the case where all vertices are outside but one edge of the polygon intersects 2 frustrum planes

so the proper way is performing a RAY-FRUSTRUMPLANE test

correct me if i am wrong with my statement but i am pretty sure it s correct

P.S.:correct me with a normal tone



What I''ve proposed is the unique way to perform an accurate (non conservative) test. Of course I suppose that my frustum is a convex volume itself...but it''s implicit!

When I clip a polygon against a plane I discard the part of the poly outside my frustum and take the part that is inside.
When I''ve clipped my poly against all planes I''ve a polygon that is in front of every plane (or it''s an empty polygon).
To simplify you can consider the Cohen-Sutherland (algorithm?) and generalize it. Imagine to see a triangle so big to fill the viewport: in 2D it''s clipped to a quad!!!

Note that the algorithm can be optimized by this way

1) if all vertices are in front of every plane -> poly is in

2) if all vertices are in back respect the SAME plane -> poly is out

3) if 1) and 2) are false we can say nothing without clipping


The same problem is to check if a box is inside/outside a frustum...in this case we can apply the algorithm to every face of the box to see if something is in. Note that case 3) is very usual so you risk to implement a no-culling algorithm.

To check collision is common to use bounding sphere/box but when you want to perform an accurate test you can create an object-frustum for one object: every face become a plane(the object must be convex).
Check if there is a face of the second object that intersects the frustum.

Exercise
Check if a polygon is inside/outside a simple box.

The algorithm appear expensive but if you think about there are not so much op...for example view-frustum is computed one time per frame.









Share this post


Link to post
Share on other sites
quote:
Original post by Basiror
actually you have to clip a polygon to proove it is inside the frustrum

imagine the case where all vertices are outside but one edge of the polygon intersects 2 frustrum planes

so the proper way is performing a RAY-FRUSTRUMPLANE test

correct me if i am wrong with my statement but i am pretty sure it s correct

P.S.:correct me with a normal tone




Yes, you have to perform some line-segment/plane intersection tests. You don''t have to actually split the polygon, like blizzard999''s code demonstrates.

Share this post


Link to post
Share on other sites
The polygon clip algorithm is a segment plane intersection...the only way we use today to describe a polygon in 3d space is with vertices and/or segments!!!

Another solution:

You can check if there is a segment in your poly that intersects a plane of the frustum...AND check if this intersection lies ''inside'' the other planes.
But this is ugly, need more code, it requires the same CPU work and finally you have no idea about the part of the polygon visible...and I like functions like this


INT Frustum::ClipPolygon(const Polygon& poly, Polygon& clippoly)const;


If you know different methods...please, tell me!!! Explore your theory!

Share this post


Link to post
Share on other sites
Guest Anonymous Poster
about this with the triangle, just find the center of the triangle and use this point to see if it''s inside the frustum.
And finding the center of a triangle is very easy: w*0.5 h*0.5 == p(x, y) == p(x, y, triangle.z)

frustum::hasPoint(p)? yes: no

Share this post


Link to post
Share on other sites
quote:
Original post by blizzard999
The polygon clip algorithm is a segment plane intersection...the only way we use today to describe a polygon in 3d space is with vertices and/or segments!!!

Another solution:

You can check if there is a segment in your poly that intersects a plane of the frustum...AND check if this intersection lies ''inside'' the other planes.
But this is ugly, need more code, it requires the same CPU work and finally you have no idea about the part of the polygon visible...and I like functions like this


INT Frustum::ClipPolygon(const Polygon& poly, Polygon& clippoly)const;


If you know different methods...please, tell me!!! Explore your theory!

Your solution works, but its overkill for the problem the OP suggested, and as such it''s needlessly inefficient. You seem intent to suggest ways to clip the polygon, pasting in your code which you''re obviously very proud of, while ignoring the actual question which was asked.

quote:
If you know different methods...please, tell me!!! Explore your theory!

I and others have suggested more efficient ways to solve the original problem. What part of my suggestion are you unsure about?

Share this post


Link to post
Share on other sites
id say, just see if any of the verticies of a triangle are inside the view frustrum, if so, draw it. Imagine a human model standing on the right side of your screen/frustrum. The human model is half way in the frustrum and half way out of the frustrum. It's not all that expensive to just draw him anyways. Imagine that there are 100 human models, standing all next to each other. You're looking at 5.5 humans, 6 are being drawn, the other 94 aren't. No big deal, not that expensive.

In my engine, ill be drawing triangles if any of the points is inside the frustrum.

Now, if you're dealing with doom3 type models/doom3 type worlds or something, you might want to make more tests to decide if a triangle should be drawn or not, because the geometry is more complicated. In my engine, a quake 2 type model (male model 1 from the retail game for example) is acceptable, only it has a higher quality texture. It all depends on how complicated the geometry is.

[edited by - fireking on October 23, 2003 8:35:02 PM]

Share this post


Link to post
Share on other sites
quote:
Original post by Anonymous Poster
about this with the triangle, just find the center of the triangle and use this point to see if it''s inside the frustum.
And finding the center of a triangle is very easy: w*0.5 h*0.5 == p(x, y) == p(x, y, triangle.z)

frustum::hasPoint(p)? yes: no


So if the center of a triangle is not visible, the whole triangle is not visible? Do I really have to explain why this is wrong? This is not even useful as a coarse intersection test, because it can''t tell you for definite if a triangle is outside the frustrum.

Share this post


Link to post
Share on other sites