Jump to content
  • Advertisement

Archived

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

CoderTCD

triangle in frustrum?

This topic is 5529 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

Advertisement
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

  • 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!