Portal culling woes

Oh yes, it’s time for portals.
I thought I’d make a simple portal demo to figure out how to set it up and have something that could be used as an example for others.
Unfortunately I’m a bit stuck.
I’ve set up the cells and portals as described in this thread: [url]Occlusion, Portals etc...].
The single test model seems to be hiding and unhiding itself, although at the wrong position/angles. At other angles Panda (the program, not the model) will poof from existence.
Here is what I have so far: http://drop.io/pdw5qoc/asset/portals-zip (portals.zip).
I don’t have any code to select which cell the camera is in yet, so it just assumes that you are in cell “1” which is the exterior area.
WASD is used to move the camera and arrow keys to look around. F toggles wireframe, which is useful for seeing if the panda model is visible.

I have a couple questions regarding portals:

  • Do I need to use the setOpen function somehow?
  • Does the winding order of the points on the portal polygon matter (if we are seeing the front or back of the polygon)?

I’ll paste the code here, but it is also in the zip with the related egg files.

from pandac.PandaModules import loadPrcFileData
loadPrcFileData('', 'coordinate-system yup')
loadPrcFileData('', 'window-title Portal Demo')
loadPrcFileData('', 'allow-portal-cull 1')
#loadPrcFileData('', 'show-portal-debug 1')

import direct.directbase.DirectStart
from direct.showbase.DirectObject import DirectObject
from direct.actor.Actor import Actor
from pandac.PandaModules import BitMask32, Vec3, PerspectiveLens, NodePath



class Game(DirectObject):
    def __init__(self):
        # Setup controls
        self.keys = {}
        for key in ['a', 'd', 'w', 's', 'arrow_left', 'arrow_right', 'arrow_up', 'arrow_down']:
            self.keys[key] = 0
            self.accept(key, self.push_key, [key, 1])
            self.accept('%s-up' % key, self.push_key, [key, 0])
        self.accept('f', base.toggleWireframe)
        self.accept('escape', __import__('sys').exit, [0])
        base.disableMouse()
        # Setup camera
        lens = PerspectiveLens()
        lens.setFov(60)
        lens.setNear(0.01)
        lens.setFar(1000.0)
        base.cam.node().setLens(lens)
        base.camera.setPos(-9, 1, -0.5)
        self.heading = -95.0
        self.pitch = 0.0
        base.camera.setH(self.heading)
        # Load geometry
        level_model = loader.loadModel('level')
        level_model.reparentTo(render)
        # Load cells
        self.cells = {}
        self.cells_by_collider = {}
        cell_model = loader.loadModel('cells')
        for cell_node in cell_model.getChildren()[0].getChildren():
            name = cell_node.getName()
            if name.startswith('cell'):
                cell_id = name[4:]
                cell = Cell(cell_id, cell_node)
                self.cells[cell_id] = cell
                self.cells_by_collider[cell_node] = cell
        # Load portals
        portal_model = loader.loadModel('portals')
        for portal_node in portal_model.getChildren()[0].getChildren():
            name = portal_node.getName()
            if name.startswith('portal_'):
                cell_a, cell_b = name.split('_')[1].split('to')
                cell_a, cell_b = self.cells[cell_a], self.cells[cell_b]
                cell_a.add_portal(portal_node, cell_b)
                cell_b.add_portal(portal_node, cell_a)
        portal_model.removeNode()
        # Put a test model in cell 2 (red hallway)
        panda = loader.loadModel('panda')
        panda.setScale(0.1)
        panda.reparentTo(self.cells['2'].nodepath)
        taskMgr.add(self.update, 'main loop')

    def push_key(self, key, value):
        self.keys[key] = value

    def update(self, task):
        # Update camera
        dt = globalClock.getDt()
        base.camera.setPos(base.camera, dt * 3 * -self.keys['a'] + dt * 3 * self.keys['d'], 0, dt * 3 * self.keys['s'] + dt * 3 * -self.keys['w'])
        self.heading += dt * 90 * self.keys['arrow_left'] + dt * 90 * -self.keys['arrow_right']
        self.pitch += dt * 90 * self.keys['arrow_up'] + dt * 90 * -self.keys['arrow_down']
        base.camera.setHpr(self.heading, self.pitch, 0)
        # Update cells
        # this is where the cell the camera is currently in should be shown
        # for now just set it to always show cell 1 (green exterior)
        for cell in self.cells:
            self.cells[cell].nodepath.hide()
        self.cells['1'].nodepath.show()
        return task.cont


class Cell(object):
    def __init__(self, id, collider):
        self.id = id
        self.collider = collider
        self.nodepath = NodePath('cell_%s_root' % id)
        self.nodepath.reparentTo(render)
        self.nodepath.hide()

    def add_portal(self, portal, cell_out):
        portal = portal.copyTo(self.nodepath)
        portal.node().setCellIn(self.nodepath)
        portal.node().setCellOut(cell_out.nodepath)



Game()
run()

I did play around with portals a while ago, though it was sufficiently long ago for it to be a bit of a blur now. At the time I did release a working demo however - http://thaines.net/content/view/89/1/ Also, if you have seen naith that has a fully working Portal system, which is used for the maze-like level for static objects - http://thaines.net/content/naith/naith.html and http://code.google.com/p/naith/ Might be a bit hard to extract what is happening from that however, as its all integrated.

Looking at the above links might help you - I had a look through your code and nothing jumped out as obviously wrong. (I ran your program but it kept seg-faulting on me.) To answer your question Vertex order for portals defiantly matters. I can’t remember anything about this SetOpen function so can’t help you there however!

Thanks for this!
I was able to pick out two problems:

  • Some of my portals were facing the wrong way. Exactly half of them actually, since I was creating a copy of each one for the opposite direction.
  • Looks like the portal code only works properly with the default coordinate system, I guess I’ll have to take a shot in the dark at fixing that.

OK, problem located!
In panda/src/pgraph/portalClipper.cxx this bit of code is hard-coded for z-up coordinate system:

  // check if the portal intersects with the cameras 0 point (center of projection). In that case the portal will invert itself.
  // portals intersecting the near plane or the 0 point are a weird case anyhow, therefore we don't reduce the frustum any further
  // and just return true. In effect the portal doesn't reduce visibility but will draw everything in its out cell
  if ((temp[0][1] <= 0) || (temp[1][1] <= 0) || (temp[2][1] <= 0) || (temp[3][1] <= 0)) {
      portal_cat.debug() << "portal intersects with center of projection.." << endl;
      return true;
  }

I modified it for y-up coordinate system which is what I use:

  // check if the portal intersects with the cameras 0 point (center of projection). In that case the portal will invert itself.
  // portals intersecting the near plane or the 0 point are a weird case anyhow, therefore we don't reduce the frustum any further
  // and just return true. In effect the portal doesn't reduce visibility but will draw everything in its out cell
  if ((temp[0][2] >= 0) || (temp[1][2] >= 0) || (temp[2][2] >= 0) || (temp[3][2] >= 0)) {
      portal_cat.debug() << "portal intersects with center of projection.." << endl;
      return true;
  }

I figure it deserves a proper fix though. In Python I can do Vec3.up() for example, is there something similar in C++ to get the coordinate system?

Good job!

Sure, you can use

LVector3f::up()

to get the same result.

OK I have the portal code fixed up, although I’ve run into another problem now. Looks like it is possible to have infinitely recursing portals. There needs to be some kind of check so the same cell is not revisited. I’m looking for a hint as to where/how to put this check.
An illustration:

Sure, a workaround would be to split cell 1 in half, but this is sure to cause headaches later on.

Hmm, that’s not a problem in Panda, per se, but bad data on the part of the user: Garbage In, Garbage Out, as they say.

But you’re right, it would be friendly if Panda could detect that situation automatically and report it as an error, rather than simply crashing messily in infinite recursion. We already do that, for instance, if you attempt to create a recursive cycle in the scene graph, by parenting A to B to A. We make this detection inside the low level PandaNode::add_child(), via a call to find_node_above(), which recursively walks from the child to the root, looking for a repeat of the child.

Extending this check to work for portals isn’t possible because there aren’t back-pointers from the cells to the PortalNodes that reference them, which means you can only traverse forward through the portal chain, not backward. I guess it would be possible to add such back-pointers, but it would require creating a new kind of node to be a cell root (so that it can hold the back-pointers to its PortalNodes), so this is a pretty involved change.

Hmm, but on further reflection, that wouldn’t be the right thing to do anyway. It’s not illegal to have chains of rooms that connect via portals, as long as those portals aren’t all lined up in an infinite recursion. It would be too inconvenient to design layouts if we forbade any possibility of cyclic recursion without also checking the view direction.

Hmm, maybe the easiest thing to do is just to add an int _portal_counter to CullTraverserData, and increment it each time we step through a portal. Then stop walking through portals when it reaches a particular limit (as specified by a config variable).

David

As far I can tell from the source, whenever we go through a portal a new CullTraverserData is created. Could we pass the old CullTraverserData to the new one, and set this attribute in the original CullTraverserData to NULL?
This way in the portal clipper we can recurse backwards up a CullTraverserData chain and check if the portal’s “out” node matches any start node of a CullTraverserData from a previous traversal. If we hit NULL then we’re at the top and it’s OK to use this portal.

I tried to add a new argument to CullTraverserData but I’m afraid I’m a bit of a C++ dummy. Pretty sure I could handle the second part of that idea though.

It’s actually normal for a new CullTraverserData to be created at each level of the cull traversal, though most other parts of the code use the third form of the constructor (the one that takes (parent, child)).

But, yeah, passing a chain of CullTraverserDatas should work. You don’t necessarily have to add it to the constructor; you can simply add a pointer to the CullTraverserData class and add a pair of set_prev_data() and get_prev_data() accessors.

Or, just maintain an integer count. It might actually be preferable in some cases. (For instance, I might be implementing a game like Portal, where I really do want to allow a cyclic recursion like this–just so long as I can bound it not to draw more than a certain number of times.)

David

I can see the case for using a counter, but it would have to be a counter per-portal or per-cell if it were to also work with the original purpose of the portal culling.
If it were just a single counter, say I limit the portal count to 100. I might be looking at two doorways, both of which recurse infinitely. Only one of them would ever get traversed because the first recursing portal would eat up the counter and then stop.

No, you use the counter to count the depth of the traversal, not the total number of visited nodes. That is, you increment the counter only when you create a new CullTraverserData, and then you set it to prev_data._counter + 1. If you visit multiple portals within a particular PortalNode, it will create a new CullTraverserData for each one, and set them all to the same value: prev_data._counter + 1.

That way, each branch will independently increment to 100 and then stop.

David

I went ahead and did the counter method, since I couldn’t figure out how to get my idea to work. I also added setMaxDepth and getMaxDepth functions on the PortalNode. This way each portal can be set to stop at a different recursion level, for example you might want most portals to stop being visible after 5 portal steps, but a certain special portal after 100 steps. I set the default at 10 which seemed high enough. I don’t know how to add new PRC settings, but if the default for each portal could point to one that would be ideal. It would be nice I think to additionally check back up the traversal chain, which would guarantee that no extra work is being done. This could be toggled on and off of course.

I uploaded my changes to the source here: http://drop.io/pdw5qoc/asset/portal-source-fix-zip
There are actually three bugs fixed:

  • Portals work with any coordinate system.
  • The initial check if we are looking at the front or back of the portal was incorrect, it is fixed now.
  • Portals can no longer recurse infinitely, avoiding nasty crashes.

Also I turned my test scene into a little tutorial, which might be useful for the SDK: http://drop.io/pdw5qoc/asset/portal-culling-zip
(of course it will crash without the above source changes)

On a side note, I was thinking that the portal system could probably be adapted to work with occluder polygons (think of them as anti-portals) without too much work.
While not as effective as portals (since the whole bounding volume would need to be inside the reduced frustum), they are definitely a lot easier for artists to set up since there is no concept of cells. Plus they would be more useful in an open environment, since you could stick one inside a hill to block stuff on the other side.