Sign in to follow this  

portal engine visibility math, alternative approaches

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

im thinking about doing a portal engine seems pretty straightforward but seeing as how i have 3d accelerator hardware the perfect portal clipping math traditional to this method is not necessary, and might in fact be a cpu load that could instead be shifted to the gpu so rather than do perfect polygon visibility by clipping against the planes that make up a portal edge im thinking that it might be a lot cheaper to have 'visibility cones' thru portals so instead of calculating 4 bounding planes when looking thru a portal, id create a cone centered on its center, with a width big enought to cover all of its 4 corners, thats only 4 dot products needed... as for actually comparing this cone to other faces to see if they are within it tho...... i really dont know how to do that.... have any suggestions? the math should be cheap... since thats the whole point of this cones idea instead of clip planes..... at first glance i though i could say, if a polygon has at least one vertex whose dot product with my cone center is less than the code width angle, then teh poly must be visible but if the poly happens to 'straddle' the cone, it may well have no vertices within it, but still cross it.... [Edited by - haphazardlynamed on September 13, 2004 7:44:47 AM]

Share this post


Link to post
Share on other sites
You should compare each triangle against a cone, wich will end up doing some quadratic operation, further more you should be sure that you will catch every triangle/cone configuration
Beside these facts, wich are of a mathematical point of view
you should check every node instead , not every triangle, its not important the geometric constrain you use, a cone isn't intrinsically 'cheaper' than a frustum , i think its not the case to shift from a frustum to a cone, i think its more important how you setup the geometry ,and in a portal engine i think that the best method is to build 'sectors' and portals connecting other sectors, this method provides increased locality for the scene, for example , when you are in a sector, you might add more detail , when a sector is partially visible, isn't needed to have a maximum detail, think about it like a lod for each sector. Sorry for the dissertation anyway.
If you are of your idea to use a cone, you should check mathworld , there you will find all the math required for a triangle / cone intersection, check also magic software , THE geometric intersection and collision site,they sell a book, but there is a TON of source code.

Share this post


Link to post
Share on other sites
You can also project the vertices of a portal to screen coords and calculate the bounding square.
When you draw the next sector you clip the bounding squares of the portals with the bounding square of the first portal.
(see http://developer.infi.nl/reinder/portalengine_large.jpg).

This method is simple and works very well with 3d-acceleration (you can use scissors to clip to the bounding square), and I believe Doom III uses it. I wrote a demo using this technique (including sourcecode) you can find here: http://developer.infi.nl/index.php?ID=5

Share this post


Link to post
Share on other sites
hmmmh

that bounding box approach sounds pretty good
but thats 9muls per vertex to transform to camera coordinates
for a square portal thats 36muls

and since im doing cube shaped sectors, like in the old Descent game, thats 72muls per cube.....

then again
my cones method, the more i think about it seems to use just as many

is that a lot of muls?

im thinking if i cache the transforms i could save abot half of them from the way adjacent cubes share half their verts
but maybe the memory access to save and reload is worse than 9 muls each again.....

Share this post


Link to post
Share on other sites
OK
heres an even better idea

seeing as how im planning on really simplistic sectors anyhow

im going to bet that its almost not worth doing visiblity checks
all i need to know is which portals to recurse down or not
but as for the polygons themselves, since each sector is small, just render all its polys if the sector itself is visible

but if all i care about is portal recursion depth

why not preprocess the entire mess?
have every sector include, a visiblity depth attribute
which indicates the maximum depth of portal recursion which will be visible thru its portals
calcualte this depth at preprocess time using accurate visibility tests from all possible locations within the sector

what you think? good/bad idea?

Share this post


Link to post
Share on other sites
'My' aproach works best with large sectors. The sector's can be non-convex (unlike descent) if you render the sectors using z-buffering which is pretty standard today :-).
I think this method is a very good for 'hardware accelerated' rendering because you minimize overdraw using portals, but use just a few (static and large) vertexbuffers for the sectors.

Share this post


Link to post
Share on other sites
Quote:

... and might in fact be a cpu load that could instead be shifted to the gpu

I always find this argument very trendy and fallacious. It neglects the fact that these techniques used to work on machines 50 times less powerful than todays machines ... with advanced GPUs. Now consider than the more you clip polys, the more you'll be able to actually render (with CLOD for instance). Your scenes will be more realistic.

Quote:

perfect polygon visibility by clipping against the planes that make up a portal edge.

Polygon level should be left to hardware. Your role is to remove whole portal branches and whole meshes (a perso, a column, a chair) through their bounding volumes usually.

Quote:
Original post by haphazardlynamed
hmmmh
that bounding box approach sounds pretty good
but thats 9muls per vertex to transform to camera coordinates
for a square portal thats 36muls

and since im doing cube shaped sectors, like in the old Descent game, thats 72muls per cube.....
... is that a lot of muls ?


First the time of computation at this stage is totally secondary behind accuracy questions. If your current visibility area is tight, you have a chance to remove whole meshes at once.
How many portals will you have to clip per frame during portal recursion ? 10 ? How many objects will you have to clip against these portals ? 100 ? How many triangles will you miss if your algorithm is very loose ? 1000 ? 10000 ?

You do not have to clip the sectors in a portal system, you only have to consider the (convex usually) portals (doors) ! Say your camera is in room1. Neighbour (connex) room2 will be invisible if the door between 1 and two is not visible. You don't clip the sector, you clip its doors.

If this door is visible you have to clip every object inside room2 (walls incuded). Apart clipping portals against portals in 2D, which is easier, you can do everything else in world coordinates. Each clipped door is equivalent to a frustum. Clipping an axis aligned bounding box against a generalized convex frustum can be done very quickly. One dot product per 'side' plane of the frustum. Thus usually 4-16 multiplications per object 3D AABox.

Quote:

portal recusion depth

I don't think it's any worth worrying about it. It seems very pointless to precompute the max depth from each sector. In 1995 or so (?) (1 year before Quake1) I have made a demo of software renderer on a Pentium90. I put two mirrors in front of each other, and I stopped the recursion at 1 pixel (in case the camera would be perpendicular to one mirror) ! The FPS did not drop at all (15-20FPS), although the engine was exceptionnallly CPU intensive as you can imagine (640*480*16bits, perspective correction, mip-mapping etc...). I think this example is quite significant compared to the kind of hardware we have now.


[Edited by - Charles B on September 15, 2004 5:19:17 AM]

Share this post


Link to post
Share on other sites

This topic is 4842 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.

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now

Sign in to follow this