Portals and objects

[Orangy Tang]

I've been thinking about portal based space division and rendering recently (nice collumn over at flipcode.com if anyone is wondering what I mean by portals) but while most of it makes sense and sounds like a good system, I've become stuck on an important point: moving objects.

Static level geometry is ok, lets assume that we've nicely carved up our world into convex sectors and portals storing their connectivity. Portals join two sectors via a plane/portal geometry. Theres nothing to stop T junctions between three sectors though, and these are likely to be pretty common.

So where do we insert our dynamic objects? If its totally within a sector then it'll be stored in an ArrayList or similar expandable data structure, but what to do when it overlaps two sectors? Store in a list in the portal? But then what to do if the object overlaps a T junction of three or more sectors (and therefore more than one sector).

Ideally I'd like to avoid storing multiple references to the same object, since this makes it easier in many areas (mainly for removing/adding when the object moves).

Anyone any ideas?

[EgonOlsen]

In my engine, i'm not storing references to objects in the sector but references (in fact not even that but simple sector-numbers...anyway...) to the sectors an objects covers in the object itself.
I'm using three kinds of objects:

1 - Objects without any sector binding...they will always be rendered/processed. This could be usefull for short-living, simple objects like particles, gunshots etc.

2 - Static objects that belong to a specific sector and that don't move at all...no problem here...

3 - Moving objects with an automated sector-detection. I detect all sectors such an object covers and if it's only one, i simply process them like they were static. If it covers more than one sector, i assume that it is visible if at least one of the sectors it covers is visible.

I'm not doing pixel-perfect clipping on the portals but polygon wise culling in a way that i assume a polygon of a multi-sectored object as being visible if it is visible through at least on portal into a sector it covers.

[Orangy Tang]

So how do you get from a Sector object to all of the dynamic objects contained within it? This is pretty important for fast collision detection (amongst other things) so some sort of global search isnt really practical (and would defeat the point somewhat).

Games published by our own members! Check 'em out!

[EgonOlsen]

...so some sort of global search isnt really practical (and would defeat the point somewhat).

In theory: yes, you are right. In practice: It's a very cheap operation. What i'm actually doing is this: I detect which sectors are visible (or covered by an object for collision detection in that case) and store them in a list. Then i'm iterating through the objects that are attached to my world-object (i'm doing this anyway) and simply ask them, if they are in one of the relevant sectors. If they are, they need further processing (rendering, collision detection...). This is really a very cheap operation and nothing compared to the more advanced operations that are happening later in the pipeline (per polygon and even per pixel because it's a software renderer).
What i'm not doing is to collect all objects that belong to a specific sector. I simply don't need this information. My portals are an option, not a must. You can build a level without using a single portal (you don't even have to care about the fact that they are an option...you can just ignore them completely). This will be slower of course, but it's possible.