Coluna 314 Report post Posted January 23, 2004 How do i get a square over the y plane, that represents the intersection between the frustum and this plane? 0 Share this post Link to post Share on other sites

MV 122 Report post Posted January 23, 2004 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. 0 Share this post Link to post Share on other sites

JTippetts 13015 Report post Posted January 23, 2004 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. Joshvertexnormal AT linuxmail DOT orgCheck out Golem: Lands of Shadow, an isometrically rendered hack-and-slash inspired equally by Nethack and Diablo. 0 Share this post Link to post Share on other sites

Coluna 314 Report post Posted January 23, 2004 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 0 Share this post Link to post Share on other sites

JTippetts 13015 Report post Posted January 23, 2004 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 pointdouble 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. Joshvertexnormal AT linuxmail DOT orgCheck out Golem: Lands of Shadow, an isometrically rendered hack-and-slash inspired equally by Nethack and Diablo. 0 Share this post Link to post Share on other sites

Coluna 314 Report post Posted January 23, 2004 Thanx!! the frustum extraction and unprojection i already knew...but the trick of the corners was very helpfull....see ya 0 Share this post Link to post Share on other sites

Trienco 2555 Report post Posted January 24, 2004 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. 0 Share this post Link to post Share on other sites