How does a BSP compiler decide which leafs make up a cluster or 'room' and which windings make a portal?
How does a BSP compiler decide which leafs make up a cluster or 'room' and which windings make a portal?
http://www.cs.utah.edu/~jsnider/SeniorProj/BSP/default.htm
The inner nodes of the tree only describe splitting planes, and the leaves themselves are the geometry formed by all the splitting planes. Convex hulls are formed, and where they are missing a polygon (a splitting plane is there instead) that is the portal shared with another convex hull.
I think from my sparse knowledge, that its about random, so actually the VIS algo will not create portals that makes much sense to a human. Like normally we would think good places are at windows and doors, but an automated VIS system will create portals at crate/boxes (or whatever geometry) planes, cutting a room in 2 when it makes no sense. And then, there are algorithms to optimize the portal subdivisions. Like, around the crate, the auto-portal generator will potentially make 5 regions, some can be fused to make only 3.
Note that this kind of engine are totally impracticable on today's geometry complexity level. it works only if a room is 6 polygons, and you have barely more constituting the details in each room.
Nontrivial question.
How does a BSP compiler decide which leafs make up a cluster or 'room' and which windings make a portal?
ID software took three product iterations to get this right and that was still not enough.
I'd link to a message I wrote years ago but it seems I'm getting a virus positive (???).
I honestly don't know why you guys keep pulling this BSP thing. The simple fact we need to do splits was enough for me to look elsewhere and it's not like there are no alternatives. It's a boatload of work simply put. If you want to just have a lot of work, write your own Z-only rasterizer, it looks quite more promising!
Keep in mind that Quake went with BSP because it allowed them to sort the world's polygons and then render them in order without any need for a Z-buffer. At the time, implementing a Z-buffer in their software renderer was an issue -- today Z-buffers are ubiquitous :)