how can I find out if a triangle is in frustrum?

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

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]

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

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 , INTERSECTreturn(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 = &frontpolygonPolygon* 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...

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.

Welcome to 3d!

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]