The Portal Connected Zone Scene Manager: SVN Version

[Chaster]

NOTICE: There is a new subforum in the Addons Forum for the PCZSceneManager. Please direct all inquiries to that forum as I will be focusing my monitoring there instead of here.

Chaster


UPDATE 11/25/08: Now that PCZSM is officially part of Ogre as of Ogre 1.6.0, I'm doing away with the separate version numbers. New features since last update: Texture shadows should now work (thanks to L3fthnd). Caelum should now work with PCZSM (thanks Aulcard).

UPDATE 04/28/08: Version 1.4.5 in CVS now includes a fix for the infinite recursion bug which would crop up in certain specific situations when recursing in and out of multiple buildings in a terrain. Also includes better sphere & aab portal crossing testing (simplified to just test for "inside" or "outside" instead of "crossing" only).

UPDATE 03/31/08: Version 1.4.4 in CVS now includes a fix for light traversal through portals. Previous versions were allowing lights to go through portals way too easily causing recursion problems (potential infinite recursion) and general performance slowdown. This latest version has a (hacky) fix which should take care of the problem AND improve performance significantly...

UPDATE 03/25/08: Version 1.4.3 in CVS now includes some additional optimizations courtesy of Aulcard. They give a nice bump up in performance on my machine of ~50 fps in PCZTestApp. Changes are in CVS.

UPDATE 03/19/08: Version 1.4.1 in CVS now avoids dynamic memory allocation/deallocation during portal frustum traversal which should result in a nice speed up (one person reports jump from 500 fps to 900 fps in the PCZTestApp).

UPDATE: Version 1.4 now availble in CVS - now supports multiple cameras (useful for effects such as shadow maps, RTT, etc.). Please report problems to me.

UPDATE: Version 1.3 now has Portal management in the PCZSceneManager class. Portals should be instantiated through the PCZSceneManager::createPortal() function and destroyed through PCZSceneManager::destroyPortal() from now on.

UPDATE: Version 1.2 is now available in CVS. I will be releasing updates through CVS from now on (unless I say differently later).

See this post (http://www.ogre3d.org/phpBB2/viewtopic.php?p=236351#236351)
for more info.


Hi Everyone,

I've finally wrapped up mylast project and officially started delving into something I promised Sinbad I'd look into several months ago: portals.

Yes, I am working on adding an OgrePortal class. No, it will not change the basic nature of Ogre (you will NOT be forced to use a portal-cell hierarchy). The portals will be (hopefully) much more generic and flexible. You should be able to use them in any scene manager with proper consideration and derivation from the base class.

I am starting this thread so that I can keep a public log of my progress and also solicit feedback/technical criticism/code review from the community.

Just to give everyone a little background on myself - I have about a decade of experience now in the game industry as a paid programmer, and the majority of that was in 3D engine technology. I have made numerous engines in the past, so I feel pretty comfortable with this task. However, I have just begun actually looking at Ogre closely, so obviously, I am still learning the ropes of the Ogre engine design.

I may ask some pretty mundane/obvious questions in the coming weeks, but I hope nobody gets annoyed...

Eric

[robin_3d]

Sounds great, it sure will be beneficial to everyone to have a professionally paid graphics programmer doing work like this for the benefit of the community. Cheers

By the way, could you describe what you mean by portal. I thought I knew what you meant until you mentioned that it would be possible to use them regardless of the scenemanager.

[:wumpus:]

Very cool; many people appear to be asking for this.

[Chaster]

Sounds great, it sure will be beneficial to everyone to have a professionally paid graphics programmer doing work like this for the benefit of the community. Cheers

By the way, could you describe what you mean by portal. I thought I knew what you meant until you mentioned that it would be possible to use them regardless of the scenemanager.

Great place to start the discussion as I want to do this RIGHT. (and by "RIGHT" I mean - fits in with the overall design philosophy of Ogre).

My initial plan is for portals to be relatively simple objects. (please keep in mind I only started designing yesterday). They will have the following properties:

1) Defined by a set of points in a plane ( an n-gon). The points form a convex n-gon. They must be coplanar. The winding order of the points determines the "direction" of the portal (portals facing away from the camera are considerred not visible).

2) If a portal is within view of the camera, it can do any/all of the following:
A) Flag an associated sceneNode as visible.
B) Add culling planes derives from the edges of the portal and the camera view point to the current frustum. These "extra" culling planes would allow additional culling on an entity basis (not polygon).
C) Transform the camera viewpoint (temporarily) - basically, so the engine thinks the camera is in a new location.

Note that A, B, and C, would all be OPTIONAL things which a portal COULD do, but wouldn't be required to do. You could use any of them individually or combine them. So, you could have a portal which merely adds additional culling planes to the current view frustum. Or, you could have a portal which flags a scene node as visible when the portal is in view AND adds culling planes... etc..

Note that this type of portal is not predicated on any specific scene hierarchy. So, while it makes it much easier to create the classic "portal-cell" scene hierarchy, it is not just for that.

You could easily use this type of portal to create "remote camera monitors", or mirrors, or "impossible mazes" (example: where a door on one side of a room leads directly to the opposite side of the room - you look through it, and you can see yourself from the back). If anyone is familiar with the Tardis from Dr. Who, you can do a similar type of effect.

Theoretically, users should be able to use these portals in any scene type.

Now, please proceed with the hole poking.. =) (be nice though! I'm a sensitive guy... lol)

Eric

[Kencho]

Glad to hear you're working on this. Sounds great (and really useful!)

[DWORD]

Cool! Sound really promising, and well thought

[sinbad]

Hi Chaster, good to see you back on this again

Your design thoughts are looking good; all I would suggest is that the culling planes you use for culling entities based on a portal would be best simplified so that you are still only dealing with 4 planes, ie the smallest square culling area which covers the portal. You might also want to use this for portal visibility, since realistically portals are likely to be quite regular in shape, and it's less work than trying to cull / detect based on an arbitrary portal shape.

[Chaster]

Hi Chaster, good to see you back on this again

Your design thoughts are looking good; all I would suggest is that the culling planes you use for culling entities based on a portal would be best simplified so that you are still only dealing with 4 planes, ie the smallest square culling area which covers the portal. You might also want to use this for portal visibility, since realistically portals are likely to be quite regular in shape, and it's less work than trying to cull / detect based on an arbitrary portal shape.

You know, I was wrestling with this question (how many "sides" should a portal have? Should it be fixed at 4, or allow more?)... After reading your post, I realized that using 4 sides is probably the best. when all is said and done.. Since I'm already requiring portals to be convex, the extra culling gained by any planes more than the basic 4 would be minimal...

Now should I have the user specify the 4 points directly, or should I put in a algorithm which calculates the 4 points based on n-input points? (for example, if you have an octagonal doorway, you specify the 8 points, and the algorithm would create the bounding "rectangle" to fit those points...)

Chaster

[sinbad]

Yeah, that's initially a tricky one, but I look at it this way - if someone did provide an 8-sided portal, geometry viewed through it would not actually be culled exactly to that shape anyway (since to do so would require 8 hardware clip planes, which no mainstream GPU supports. Therefore the portal must really just a coarse cull, and the detail shape of the doorway etc must dictate the final occlusion using standard depth buffering techniques. This detailed surround must be modelled.

So I think forcing portals to be rectangular in the first place is the best bet, since it makes the modeller consider the fact that the portal itself is quite simple, and does not in fact cull per pixel (even to the 4-plane version), it should really be embedded inside / behind a more complex surround if that's the effect that is desired.

[Cyberdigitus]

hi, interesting topic...

I've been working on a general Portal SceneManager for Axiom for a while now, the basics work but i haven't released it yet. still lot's of work to do, but i have explained my idea's in detail in this project thread at the Axiom forum.

my portals basically work the same way, but i do have a few assumptions on how a scene is set up. It can be used in a very general way, but in practice you come to a certain use that is most balanced for the type of world you try to make.

Concerning the sides, i've also come to the conclusion that just 4 is easiest. I define portal bounds by providing a pos, normal and upvector (all relative to the sector it's in) plus width and height (creating 4 points out of that) the visibility check with that is like aabb but with 4 instead of 8 points.

Anyway, i'd like to hear what you think of it's basic design idea's, maybe we can exchange some thoughts...

Since Portals can use frustums in special ways, i propose some refactoring of the camera / frustum relation too, as described in this thread. What are your feelings to that Sinbad?

[Chaster]

I've decided to make portals 4 sided in all cases, and users will have to specify the points - no "auto-calculation"...

Cyberdigitus, you *should* be able to derive from my portal class easily to create portals which do the same as yours. My own specific project which provided the impetus for adding portal functionality has similar needs as yours.

BTW, when I read how you specify your portals, I was a little surprised because it seemed to be an "artist unfriendly" way of doing it (my level designer prefers to just specify geometry for the portal - and we use the vertices to create the portal). However, I then realized that your way avoids potential "badly defined" portals because there is no chance the portal is "bent" (i.e. no chance the points are not coplanar - which can happen if the artist doesn't obey the "rules"). How are you having your level designer/artist/whoever specify portal location/dimensions? We avoid the "bent portal" situation by slapping hands ("naughty artist! don't do that!") a couple times.. LOL..

Regarding Visibility Check: I've actually tried several different methodologies over the course of a couple engines. Unsurprisingly, different methods work better for different cases. Checking each "side" of the portal for visibility is, of course, most accurate. However, that involves several compares per culling plane, which tends to expand geometrically as you add extra culling planes from multiple portals.

My current plan for the "default" visibility check is to use a more conservative visibility check (by conservative, I mean, it will give more false positives for visibility) - checking the bounding sphere of the portal versus the current culling plane set PLUS checking the direction of the portal vs. the camera direction. In practice I've found that the tradeoff is a win (more false positives, but a lot less computation for typical scenes).

Of course, I will most likely have the visibility check switchable between the two options: most accurate (using the sides of the portals), and less computationally expensive (using the bounding sphere of the portal). BTW, using the bounding box of the portal is more expensive than using just the sides (and it's obviously less accurate), so I don't plan on implementing that.

BTW, Sinbad - my implementation requires (?) that I add a stack (or similar) of "extra" culling planes to the camera frustum. This doesn't seem like a big deal to me (since they will not take up much memory/overhead if not used) but I am open to other ideas...

Chaster

[sinbad]

BTW, Sinbad - my implementation requires (?) that I add a stack (or similar) of "extra" culling planes to the camera frustum. This doesn't seem like a big deal to me (since they will not take up much memory/overhead if not used) but I am open to other ideas...

Sounds reasonable; the extra plane tests will add some overhead of their own though, so if you can guarantee that the planes you provide form a closed volume then you might want to make allow these custom planes to override the standard planes, instead of being additional.

[Chaster]

When they are in use, the extra plane test costs are unavoidable (of course). When not in use, the extra overhead will only be a single conditional (checking if we have extra culling planes or not).

In my implementation there is no guarantee the extra planes will form a closed volume because there are cases when you only want to add some of the planes from the portal - not all of them. For example, if the portal is only partially visible (in the corner of the view frustum) then you would only want to add the planes created by the visible sides of the portal. The sides which are offscreen are redundant and therefore should not be added (because they will cause computational slowdown).

I took a look at the discussion on Axiom which Cyberdigitus talked about adding a frustum per portal, and that seems inefficient to me (because of the reasons stated in the previous paragraph). Of course, I could be interpreting things wrong - please correct me if that's the case..

BTW, this is my first "real" foray into an Open Source project. I must say, the feedback and discussion process is quite refreshing! (I work alone 99% of the time and it's easy to miss the forest for the trees when you are so isolated...)

Chaster

[sinbad]

That's a fair point - I had been thinking of the more simple cases, and that including the offscreen portal edges as cullers wouldn't be too drastic, but if you have a large portal where only a sliver is onscreen, it will of course make a large difference to replace the primary culling with the portal. So I think you're right, carry on

[Cyberdigitus]

for partially visible portals you might do a frustum from the screen space bounds of the portal. Not sure if you should generalise this or combine it with '3d' frustums though.

chaster, what i described about the portal definition is how the engine loads it (width & height on a plane, and several overloads like giving 4 points directly) How they are defined by the artist is much more friendly, just put a certain texture on portal polygon's; or place them manualy in a - yet to be written - editor. The exporter then creates the portal definition.

the frustum per portal visible is to narrow it down recursively. so portals visible from camera or another portals checks visibility of the objects, but also further portals, in a smaller area. this gives you some rough form of both visibility and occlusion culling. That's all for frustum's made in 3d space that just do findVisibleObjects by the way, if you'd use -hardware- occlusion or stencil tests this might not be needed.

i'm more and more getting the feeling frustum should be a math object though.

[Chaster]

Cyberdigitus, I think perhaps either I am missing something in your explanation or you are missing something in mine... Heh..

IF, you were to use portals in a portal/sector hierarchy, you do not need to create full frustums for each portal to gain the benefits of increasing occlusion with recursive portals. The same benefit is given by adding only the necessary planes created from visible sides of each portal with the camera viewpoint. When using a recursive traversal through a portal connected sector hierarchy, each portal will add between 0-4 additional culling planes to the camera frustum which will be used to not only cull objects but other portals - in effect doing the same thing as you describe - but without creating unnecessary planes (which WOULD be created if you were to just assume a full frustum for each portal).

Basically, what I am saying is: creating an additional culling frustum for each portal is overkill - and algorithmically much less efficient.

This becomes especially apparent when you have several portals *partially* visible (say you are looking through a series of rooms all connected by doors behind each other but somewhat offset so they do not fully overlap). Creating a "simple" frustum (4 culling planes in a pyramid configuration) for every portal, will result in always getting Nx4 culling planes (where "N" is the number of portals). Intelligently selecting culling planes will often get you less culling planes (worst case scenario is the same: Nx4 culling planes) with no less quality in culling accuracy.

Sinbad, in my experience, the primary performance hit with most portal-sector hierarchy traversal methods comes from the overhead of multiple culling planes when many portals are visible on screen. That said, usually you will want to have BOTH camera frustum culling AND the portal culling planes active. My goal is just to minimize the number of culling planes created per traversal.

By the way, thank you both (Cyberdigitus & Sinbad) - your feedback in this discussion is really helping me identify the primary issues for the design & implementation.

Chaster

[Cyberdigitus]

Aha, now i understand what you mean, took me a lot of drawings to see that you can reuse planes. This could solve the partially visible portal problem, but you still need to create a frustum out of those 4 planes (5 if you take into account the far plane, probably by reusing the camera far plane), and you'd need a way to pass a previous plane to the next frustum.

maybe i still don't understand something about how you would set up the relational hiearchy of the scene, do you keep all portals in one list or a list per 'sector'?

Testing for portal to camera direction is neat though, didn't think of that yet.

[Chaster]

This is a difficult topic to discuss in text only (and I'm too darn lazy to start drawing diagrams and posting them.. LOL)...

I think our approaches to portal/sector scene hierarchy are fundamentally different... (which is perfectly legit - there are several ways to approach the algorithm).

My method:

1) I wouldn't create any new frustums at all - I would just add "extra" culling planes to the current camera frustum as the sectors are traversed. The connecting sector would not only cull based on the basic 6 culling planes of a standard frustum (left, right ,top, bottom, near, far) but also on these "extra" culling planes. As sectors are recursively traversed, each portal adds culling planes to the camera frustum's list of "extra" culling planes.

2) This might be scene dependent, but I have never found the need to add an extra far culling plane.

But before we go too far on this subject, I think I should point out that we're getting pretty far ahead of ourselves - the portals I am adding are not specific to this application. I need to focus on making them NOT structure oriented, and we're getting pretty focused on that particular facet...

I'll keep you guys posted with my thoughts/progress... =)

Chaster

[Chaster]

Okay, I'm gonna give a quick summary of what I've done in the last day or two...

1) Spent most of the time trying to get up to speed on Ogre's basic design & coding standards... and umm, brushing up on my C++ a little bit (I'm old school - learned C first, and had a hard time letting go... heh..)

2) Set up the skeleton of a class called "Portal". Ogre Portal inherits from MovableObject. I did this because I want portals to be movable.. duh. I did not inherit from Entity because entities have all this stuff for skeletons and skeletal animations which portals don't need.

3) Portals have a local space normal, and 4 local space cornerpoints (vector3's). They also have a pointer to a SceneNode and local AABB and local Bounding Sphere.

A couple questions/uncertainties:

* My local bounding sphere assumes that its' center is relative to the parent node location. However, I see in OgreMovableObject.cpp, that the default movable object assumes the bounding sphere is centered on the parent node location. I hope the fact that portals are not centered on parent node location is not a problem....

* It seems that both AABB and BS (bounding sphere) need to be defined for all movable objects - can someone tell me if they are required for specific functions or are they just there for flexbility? I have them both in there, but I am just curious as to what they are used for inherently (if anything).

* What is the proper procedure for transforming from local coords to world coords? I assume it's just create a transformation matrix from parent node derived orientation/position and use that to transform the portal corner points (which are in local space).. Correct? (and of course rotate the normal)... Anything tricky here that I should be aware of? I'm trying to make this only happen when the parent node (or the portal corners themselves) move or change orientation so we're not doing matrix calcs every frame...

Thanks in advance for your help guys,

Chaster

[Kencho]

* The bounding sphere, as well as the bounding box must contain the whole geometry. So if you have the sphere off-centered, you'll have to make a larger sphere, which may have an impact on performance beacuse of:

* As far as I know, the AABB & BS's are used by scene managers to check when a certain thing is visible or not. Having an AABB or BS inside of a frustum usually means that object "is" visible. They are also used in scene queries, if I recall correctly

* There are ways such as getDerivedPosition () that could be useful for this

[Chaster]

Thanks kencho - you confirmed what I was thinking.

Another question now comes up.

At their simplest form, portals have a pointer to a "target" scene node. If the portal is determined to be visible, then the target scene node is determined to be visible too.

So far, so good. In the portal class, I overrode the _notifyCurrentCamera function to do a visibility check on the portal. If the portal is facing the camera (dotproduct of camera view vector and portal normal is negative) AND the portal bounding sphere intersects the camera view frustum, then the portal is dtermined to be "visible". (I am not implementing the extra culling planes quite yet..)

QUESTION 1: Is this (portal::_notifyCurrentCamera()) the logical spot to put the visibility determination for the portal?

In the same function, I was going to recurse the _findVisible() call to the target scene node. However, this requires that I have additional arguments passed in. Here is the function declaration as is in Ogre currently:

MovableObject::_notifyCurrentCamera(cam);

Whereas _findVisibleObjects is declared as:

SceneNode::_findVisibleObjects(Camera* cam, RenderQueue* queue,
bool includeChildren, bool displayNodes, bool onlyShadowCasters)

Obviously, I can't call SceneNode:: _findVisibleObjects(..) from within MovableObject::_notifyCurrentCamera() because I don't have the queue, includeChildren, displayNodes, and onlyShadowCasters arguments available..

QUESTION 2: Any way to get around this without changing the declaration of _notifyCurrentCamera?

Note that I don't want to simply call SceneNode::setVisible(true, ...) on the target scene node because if the target scene node has portals in it also, the call to SceneNode::setVisible() will force them to be visible too - even if they are not visible.

Basically, what I want to be able to do is call SceneNode::_findVisible(...) from within the Portal class. Any ideas?

Chaster

[sinbad]

1. _notifyCurrentCamera means the portal is visible to the camera according to it's bounds; it is not called if not. The scene manager / scene node already do bounds culling on MovableObject instances before it gets to that stage.

I'm not sure why you wouldn't want to just make entire subtrees visible / invisible. The fact that it would make a portal attached to that subtree 'visible' is correct, because it just means it's 'potentially visible', not 'definitely visible'. If it is visible, then it will cascade and make it's linked node visible too, which sounds like exactly what you would want. Maybe I missed something.

BTW SceneNode::setVisible controls visibility by setting the visibility flag on all objects and objects attached to children, so it's not that efficient (it's meant as a shortcut to doing it individually on objects, but letting you refine that later). You'd be better to use removeChild and addChild to quickly drop and reattach subtrees.

[Chaster]

1. _notifyCurrentCamera means the portal is visible to the camera according to it's bounds; it is not called if not. The scene manager / scene node already do bounds culling on MovableObject instances before it gets to that stage.

Doh, my lack of experience with the engine is certainly a pain in the ass.. LOL.. So SceneNode::_findVisible() is the wrong function.. I see now.. Man, it's hard to break my old habits of tightly integrating the portal into the structure of the scene (bad Chaster!)... Okay, so it looks like I should not bother with trying to make a portal determine its' own visibility - that functionality should be handled by individual scene managers, correct?

I'm not sure why you wouldn't want to just make entire subtrees visible / invisible. The fact that it would make a portal attached to that subtree 'visible' is correct, because it just means it's 'potentially visible', not 'definitely visible'. If it is visible, then it will cascade and make it's linked node visible too, which sounds like exactly what you would want. Maybe I missed something.

I think this was a mistake on my part - I was trying to put functionality that belongs in the scene manager (visibility determination of the portal) into the portal itself. Instead, it seems the correct route is to just provide information about the portal (location, direction, corner points, bounding volumes, target scene node, etc.) and let the scene manager determine if the portal is visible or not and if so, what to do... Yes?

BTW SceneNode::setVisible controls visibility by setting the visibility flag on all objects and objects attached to children, so it's not that efficient (it's meant as a shortcut to doing it individually on objects, but letting you refine that later). You'd be better to use removeChild and addChild to quickly drop and reattach subtrees.

Okay. It *seems* to me that I shouldn't be mucking about with visibility in the first place since that is the realm of the scene manager... Please confirm or dispel...

[sinbad]

Yes, that's right. That way, the SceneManager can use whatever optimised tomfoolery it wants to determine the visibility of your portal, rather than being bound to which visibility algorithm you choose.

[Chaster]

Okay Sinbad, thanks - that simplifies things in the portal a lot.

Some more questions:

1) Why does the movableObject::getWorldBoundingSphere() function assume that the sphere center is at the same location as the parent node?

const Sphere& MovableObject::getWorldBoundingSphere(bool derive) const
{
if (derive)
{
mWorldBoundingSphere.setRadius(getBoundingRadius());
mWorldBoundingSphere.setCenter(mParentNode->_getDerivedPosition());
}
return mWorldBoundingSphere;
}

Is there some special reason for this? Just curious, because for Portals, I am allowing portals to be "off center" compared to their parent node, and have overriden the getWorldBoundingSphere() function accordingly. I just wondered why say, the localBoundingSphere isn't calculated and transformed to world space (similar to how the localBoundingBox is done).

2) I have a function (updatePortal()) which basically makes sure that all the bounding volumes are up-to-date (also makes sure that the world normal is up-to-date as well). How do I ensure this is called properly with every cycle of the engine? I assume there is a standard function in MovableObject which I should be overriding, but can't seem to locate it..

Thanks for the help - sorry I'm asking so many questions..

Chaster