Zemedelec:

You know which sector each BSP leaf belongs to by walking the connectivity information like I described in an earlier post (The previous AP). Essentially, it's just a flood fill of the convex leafs produced by the BSP process. When you come across a portal, stop filling. The process will end when you have classified each leaf as being part of a sector.

Interesting. I had thought of trying something like that but could never quite figure out how it would work. Could you give a more in-depth description of how you would implement it.

I tried implementing a similar algorithm to the one I described a few years back. However, it wasn't really successful. But that was due to problems in my maths/BSP code which caused it to fail on all but the most basic two room approach. Errors in the BSP itself couldn't be too much of a problem as engines have used this sort of pre-processing for years. However, I am concerned about making polygon splits which are not required for both performance & a fear of introducing floating point errors. I guess I'll have to find some time to implement it and see what happens.

There was also an old IOTD posted on flipcode (before it died :() where a guy was using a completely automated system for generating portals. In that system, his editor was CSG (like unreal rather than the quakes). When two subtract brushes intersected, a portal would be generated. I can understand how this sort of geometry would make this task easier, but there a so many good quake style editors available (with source too!). Performing sectoring on a poly soup also allows you to be editor agnostic which can only be a good thing.

Anyone else have any alternative approaches to the sector/portal problem? What about ways to reduce numberical errors or redundent splits?

Quote:Original post by Zemedelec
There was another idea (which is faster to program and more stable).
Photon trace the triangle soup, using simple hierarchy (kd-tree) for collision with a bounding ray. Shoot from portals, mark geometry.
After some shooting, start to shoot backwards from unmarked polys to the world hoping to hit something marked... :)

Cool, I like that Idea... No splitting & alot more stable. Did you come up with that idea? Or did you read a paper (if so, where can I get it?). I can't imagine that it would be as fast as using a BSP, although I'm sure it would scale alot better as the scene becomes more complex.

Essentially, the tracing is used to decide what is visible from a given point (a portal in this case). Graphics hardware uses the Z-Buffer to achieve this, I wonder if you could perform the tracing in hardware. It would certainly speed up the pre-processing! You would render the scene from the portals perspective and then use the results to figure out which polygons were visible. Very accurate & fast, now just to figure out how to check which polygons were rendered in the first place! Maybe Hardware Occlusion Queries? (Don't know much about this, so it maybe completely out of the question or even overkill).

Any thoughts?

Quote:Original post by Zemedelec
It should work, IF the geometry has no flying edges, T-junctions, etc.

Yep, your spot on Zemedelec! Infact, there was a guy over on Ogre3d which did just that for the Goole's Summer of Code. You can download the pre-processor he wrote from one of the forums. It seems to work (and at a good speed), but it imposes too many constraints of the Geometry in my opinion.

As calculating visibility information on the GPU. I really like the idea of using unique colours to identify polygons/polygon groups. I too had thought of the grouping that you mentioned. Would you really need a cube map? You could almost use techniques from Shadow mapping to skew the perspective. Resolution isn't really a problem as you just need to know that a poly is visible, not exactly how much of it is.