Sign in to follow this  
scarypajamas

Portal Renderer: Determine the zone an entity is inside.

Recommended Posts

I'm building a portal renderer and I'm trying to find an efficient way of determining which zone (or sector) an entity is inside.  In my case, a zone is defined as a manifold mesh (convex or concave).  A portal is defined as the connection of two surfaces (AKA mesh faces) from two different zones.

I need to know the zone the player/camera is inside so the portal algorithm can be executed: e.g. start clipping the frustum against the current zones portals, etc...  It would be nice to know the zone for other things too.  For example, if a zone has been flagged as liquid and if an entity is inside it, then physics logic for the entity can flex accordingly.

My background in PVS algorithms mostly just includes quadtree's and octree's.  I've started reading up on BSP's now, but I'm not sure if that's the way to go about solving this problem or if there is a better, known solution.
 

Share this post


Link to post
Share on other sites
I've started reading up on BSP's now, but I'm not sure if that's the way to go about solving this problem or if there is a better, known solution.

The advantage of BSP is that you get the final answer without any additional refinement - e.g. with a octree or BVH you would get only a set of possible zones (because their boundig boxes may intersect).

BSP can also help to determinate the exact PVS per zone, see: http://www.cs.utah.edu/~jsnider/SeniorProj/BSP/default.htm

 

I don't know a better solution to get exact results. Other approaches for visibility determination mostly give less exact results but work much better with detailed / outdoor / dynamic scenes.

Edited by JoeJ

Share this post


Link to post
Share on other sites

Thank you both for your answers.  They have helped a great deal.

 

Lets suppose I did use a BSP.  I understand how to compute the location of a point within the tree, but how would I compute the location of an AABB in the tree?  It seems to me an AABB can cross multiple splitting planes which confuses me on how the tree traversal should be performed.

Share this post


Link to post
Share on other sites

Lets suppose I did use a BSP. I understand how to compute the location of a point within the tree, but how would I compute the location of an AABB in the tree? It seems to me an AABB can cross multiple splitting planes which confuses me on how the tree traversal should be performed.

 

If the box intersects the splitting plane, traverse BOTH child nodes - that's all :)

The result is a set of all leave nodes intersecting the box.

 

For better understanding, imagine we would clip the box polygons at each plane intersection, so cutting the box into two pieces.

Also we add a new polygon to each piece to close the hole.

We would end up with many convex polyhedras, one for each leave node the box intersects.

 

Operations like this are useful to do boolean operations on two meshes (merge / subtract / add...), PVS determination (see http://www.gamedev.net/topic/683910-determine-visibility-among-n-points-in-obstacle-filled-enviornment/) etc.

Share this post


Link to post
Share on other sites

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