Archived

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

Coluna

Intersection between Frustum - y plane

Recommended Posts

What y plane are you talking about ?
If it''s one of the near or far plane of the frustum, you should check nehe tutorial on frustum culling (octrees) ; you''ve got all needed to get the 6 frustum planes.

Share this post


Link to post
Share on other sites
You have to perform a reverse projection of the corners of the screen to determine the line segments corresponding to the corners of the frustum. Then, simply solve for the intersections of the line segments with the plane in question. Note that if perspective correct projection is in use or the camera is at an angle, the shape defined will be more of a trapezoid than a square.

I don''t know if you are using OpenGL or not, but there is a handy function provided by the OpenGL utilities called gluUnProject(), which accepts the current viewport parameters, the projection matrix and the modelview matrix, and will reverse project an on-screen point for you. A point onscreen does not reverse project to a single point in space, but rather to a line segment with length defined by the distance between the near and far clipping planes of the frustum.

If you are not using OpenGL then I am not certain if Direct3D has an equivalent function; but reverse projection is generally accomplished by calculating the inverse of the current matrices, and transforming the point represented by the on-screen coordinates (in your case, the screen coordinates of the corners), with the z-component of the coordinate being in the range [0,1], where z=0 defines the point on the near plane and z=1 is on the far plane. The result of the transformations is a set of 2 points defining a line-segment in world space representing the corner of the screen. Then, simply determine the equation of the plane and solve for the intersection with the line segment.

Depending on the orientation and location of the view frustum relative to the plane, you might not get an intersection at all, so be ready to check for degenerate cases if you have to.

Do a search to learn how to calculate the inverse of a transformation matrix. You can also Google for gluUnProject() to find a reference to the OpenGL function, which may include the exact formula that function uses. It should be relatively easy to duplicate the functionality of gluUnProject() if you are using Direct3D. Assuming, of course, D3D doesn''t already provide a similar function; I don''t know D3D at all, so I can''t say.

Josh
vertexnormal AT linuxmail DOT org


Check out Golem: Lands of Shadow, an isometrically rendered hack-and-slash inspired equally by Nethack and Diablo.

Share this post


Link to post
Share on other sites
Yes, im using Opengl... do u have it implemented? i wanna use it to do not use recursion, because when i have a lot of nodes it slows me down a lot...so i will only check the nodes that are inside that square...if u could send some code , please do it!!! thanx anyway

Share this post


Link to post
Share on other sites
Okay, first of all you need to get your current viewport, projection matrix and model-view matrix. They can be retrieved using these calls:

GLint viewport[ 4];
GLdouble modelview[ 16];
GLdouble projection[ 16];

glGetDoublev( GL_MODELVIEW_MATRIX, modelview );
glGetDoublev( GL_PROJECTION_MATRIX, projection );
glGetIntegerv( GL_VIEWPORT, viewport );


This copies the current state into your arrays for use with the gluUnProject() function.

Now, you need to un-project the corners of the screen for the near and far clipping planes. The viewport[ ] array from above holds the screen viewport dimensions within it, so you can easily use those values (viewport[ 2] for the width of the screen, viewport[ 3] for the height) for the corners.

What you want to do is calculate a line segment for a corner of the screen. To do that, UnProject the screen coordinates (x,y) for the corner twice, once with a z-value of 0 and once with a z of 1.

The function signature for gluUnProject() is:
gluUnProject(double winX, double winY, double winZ, double *model, double *proj, int *view, double *objX, double *objY, double *objZ);

double x1, y1, z1, x2, y2, z2;

gluUnProject(0, (float)viewport[ 3], 1, modelview, projection, viewport, &x1, &y1, &z1); // Unproject far plane
gluUnProject(0, (float)viewport[ 3], 0, modelview, projection, viewport, &x2, &y2, &z2); // Unproject near plane

This code reverse-projects the upper left-hand corner of the viewport (note that the OpenGL viewport has it''s origin (x=0, y=0) in the lower left hand corner of the physical window, rather than the upper left corner.) Now (x1,y1,z1) and (x2,y2,z2) are the coordinates defining the line segment in world space for one of the corners of the frustum.

Next, you need to calculate the equation of your plane. If the plane is perpendicular to the Y-axis(as it appears you desire) this is very simple to do. For these planes, the plane normal is (0,1,0), which breaks down to the simple equation Y=D, where D is the elevation or height of the plane. What you need to do then is solve the equation of the line segment for this value of Y to determine the point of intersection. One way of doing this is to interpolate the segment endpoints:

double t;
t=(PlaneY-y2) / (y1-y2); // PlaneY is the height of the plane.

// Solve for x and z to get intersection point
double ix = (x1*t) + (1-t)*x2;
double iz = (z1*t) + (1-t)*z2;

Note that if t<0 or t>1 then the line does not intersect with the plane between the segment endpoints; that is, the frustum at that corner does not intersect the plane. Also, if y1==y2, the line itself is parallel to the plane and never intersects, so you get a divide by 0 error. Unless your camera is fixed to never generate these sort of conditions, you will need to perform checking.

So, the point at which that corner of the frustum intersects with the plane Y=PlaneY is defined by the coordinate (ix, PlaneY, iz).

Repeat this process for the other corners, and you will generate the coordinates of a quadrilateral defining the view area.


Josh
vertexnormal AT linuxmail DOT org


Check out Golem: Lands of Shadow, an isometrically rendered hack-and-slash inspired equally by Nethack and Diablo.

Share this post


Link to post
Share on other sites
just gave me an idea here. calculating the corners of the frustum isnt hard, turning that into an aabb isnt a problem and if your data is organized in a fitting way... though i guess its more useful for huge scenes where the frustum is small compared to the rest.

another thing i thought about (because i know how frustrating it is, when your neat quad tree causes enough overhead to not be faster than brute force testing every leaf): if every node stores a pointer to the first leaf and the number of leaves you wouldnt have to continue traversing the tree to collect them, but could just take x leaves starting at address p.

Share this post


Link to post
Share on other sites