   Portal culling: portals projected volume
  HelloThis is my first post on this forum. My name is Julien Gouesse, I'm the author of the open source first person shooter called T.U.E.R. I have worked on it several years.I have implemented a kind of portal culling but one step is missing:http://geck.bethsoft.com/index.php/Occlusion_Culling"When the camera is within a portal space, the system firsts tests any portals against the view frustum. If a portal is visible, the contents of the space it connects to are accumulated based on an intersection of the view frustum with the portals projected volume - this new volume becoming the new view frustum. If the connected space is a portal space, this process can repeat as necessary."I have the coordinates of the vertices of the portal, I want to project (perspective projection) them onto the near plane of the current view frustum in order to reuse these coordinates to build the new view frustum. For the moment, I tried to use the method getScreenCoordinates(Vector3f vec) of the class com.jme.renderer.Camera (from JMonkeyEngine 2.0) to get the coordinates of the portal in the screen reference mark. Then, I divided them by the size of the screen. After that, I tried to compare them with the frustum left and right values but I get coordinates that are bigger than expected whereas this portal are in the view frustum (its abscissa should be between left and right, see glFrustum). Please find below the source code of getScreenCoordinates:/**  * Implementation contributed by Zbyl.  *  * @see Camera#getScreenCoordinates(Vector3f, Vector3f)  */public Vector3f getScreenCoordinates( Vector3f worldPosition, Vector3f store ) {   if ( store == null ) {  store = new Vector3f();   }   checkViewProjection();   tmp_quat.set( worldPosition.x, worldPosition.y, worldPosition.z, 1 );   modelViewProjection.mult( tmp_quat, tmp_quat );   tmp_quat.multLocal( 1.0f / tmp_quat.w );   store.x = ( ( tmp_quat.x + 1 ) * ( viewPortRight - viewPortLeft ) / 2 ) * getWidth();   store.y = ( ( tmp_quat.y + 1 ) * ( viewPortTop - viewPortBottom ) / 2 ) * getHeight();   store.z = ( tmp_quat.z + 1 ) / 2;   return store;    }What should I do to convert the coordinates of the vertices of the portal into a reference mark that allows to reuse them to compute a new frustum culling? I am trying to solve this problem for months. Thank you for reading.   
  you can simplify things a lot if you use bounding rectangles in screen spacethen every frustum will always have planes that form rectangle on the screenalso finding them is much easier.this describes simple method for doing it.http://www.gamedev.net/community/forums/topic.asp?topic_id=418987&whichpage=1&#2802915just clip your portal to original view frustumfind left/right/top/bottom most vertex and find plane going through it (link)you'll get 4 new planes that you can use to cull geometry behind portal;  I have had far more success with dealing with portals entirely in 3D.Simply clip your portal polygon to your parent set of planes (view frustum to begin with) this will give you a new polygon. Spin round the vertes of your new clipped polygon and construct a new frustum using each edge and the camera position to create each plane. You just need to watch out for degenerates created by clipping, these will obviously not create valid planes.Rinse and repeat.   ;  Hi!I thank you both for your attention and your detailed answers.Quote:Original post by biki_you can simplify things a lot if you use bounding rectangles in screen spacethen every frustum will always have planes that form rectangle on the screenalso finding them is much easier.this describes simple method for doing it.http://www.gamedev.net/community/forums/topic.asp?topic_id=418987&whichpage=1�just clip your portal to original view frustumfind left/right/top/bottom most vertex and find plane going through it (link)you'll get 4 new planes that you can use to cull geometry behind portalThat is close to what I had planned to do, check if I am wrong please:- convert the coordinates of the vertices composing the portal into "screen" space (or rather in "frustum" space to reuse what is already available in JME 2.0)- compute the left/right/top/bottom most values composing the portal- project the vertices that use these extremums onto the near plane of the current frustum ({left,top},{left,bottom},{right,top},{right,bottom}) to get a new square that can be used to extract the left/right/top/bottom values of the new frustumIf I multiply the quaternion representing a vertex of the portal in the "world" space by the projection matrix and the model-view matrix, do I get a vertex of the portal in the "screen" space?The article you quoted is excellent. Thanks.Quote:Original post by MartinI have had far more success with dealing with portals entirely in 3D.Simply clip your portal polygon to your parent set of planes (view frustum to begin with) this will give you a new polygon. Spin round the vertes of your new clipped polygon and construct a new frustum using each edge and the camera position to create each plane. You just need to watch out for degenerates created by clipping, these will obviously not create valid planes.Rinse and repeat.I don't see the difference with the suggestion of biki_ except that he deals with using the bounding rectangles, am I wrong? Does your method rely on non-square frusta? I know that non-square frusta might be more efficient in certain cases (it is more accurate, it allows to eliminate more hidden cells if lots of portals are not squares) but they are more complicated to use. For example, if my levels are often composed of indoor environments, rooms linked together by doors, non-square frusta are useless. However, if I have more complex outdoor environments but that can still be split into cells, non-square frusta may be useful as portals in such cases may not be squares.   ;  ok here's full ideagiven: 6 planes of view frustum  vertices of portal transformed to camera space.1. clip polygon to view frustum (it's done in 3d so no screen space transform needed)2. for each vertex calculate its 'coordinates' inside frustum as follows   d1=distance_to_left_frustum_plane/(distance_to_left_frustum_plane+distance_from_right_frustum_plane)   d2=distance_to_top_frustum_plane/(distance_to_top_frustum_plane+distance_to_bottom_frustum_plane)3. you use vertices with minimal/maximal d1 and d2 to define new frustum planes as follows  new_left=left*(1-d1_min)-right*d1_min  new_right=left*(d1_max-1)+right*d1_max  new_top=top*(1-d2_min)-bottom*d2_min  new_bottom=top*(d2_max-1)+bottom*d2_maxand that's itall done in 3d without any complex transformations;  Hi!I have found why my source code was not working. It was not because of me. JMonkeyEngine 2.0 has another bug. When you use its view frustum culling, the culled test always says that the tested object is inside the frustum. My method should work. Thank you for your advices.   ;  Hi!I had forgotten to call getPlaneState(0)! Now I get between 60 and 142 FPS instead of 16 FPS. Java gaming rocks!   ;  Hi!How can I compute the center of projection of a view frustum? I need it to use the Thalès' theorem to compute a section of the frustum.   ;  Hi!A portal can be split into triangles. Then, I follow what is written in the FAQ to convert the triangles from object coordinates to normalized device coordinates:- Object Coordinates are transformed by the ModelView matrix to produce Eye Coordinates.- Eye Coordinates are transformed by the Projection matrix to produce Clip Coordinates.- Clip Coordinate X, Y, and Z are divided by Clip Coordinate W to produce Normalized Device Coordinates.- Normalized Device Coordinates are scaled and translated by the viewport parameters to produce Window Coordinates.After that, instead of converting the normalized device coordinates into window coordinates, I scale them and translate them by the frustum parameters (to have them projected onto the near plane???) like in the example below:store = getNormalizedDeviceCoordinates( worldPosition , store );store.x = ( ( ( store.x + 1 ) * ( frustumRight - frustumLeft ) / 2 ) ) + frustumLeft;store.y = ( ( ( store.y + 1 ) * ( frustumTop - frustumBottom ) / 2 ) ) + frustumBottom;store.z = ( store.z + 1 ) / 2;Then, I look for the extremums (left most, right most, top most, bottom most coordinates) and I clip them into the current view frustum.Finally, I use the coordinates I get in the previous step to build a sub-frustum that may have different values than the current frustum only for the parameters left, right, bottom and top.My problem is that the obtained sub-frusta are always too small. That is why I would like to know if my method is correct. How would you convert normalized device coordinates into "frustum" coordinates? How would you project vertices onto the near plane of a frustum?   ;  Hi!The portals are correctly computed but when one of them does not contain the center of the screen, the culling does not work (it rejects some geometry that should not be rejected):Is it legal to create a frustum whose left and right parameters are both positive or both negative?   