I've written a solid-leaf BSP compiler and it's working fine except for one particular scenario:

If I position my convex hulls into the shape of a "room" (see the black rectangles in picture #1) and I encase all of them in one large hull (the blue box), then depending upon which order the splitter planes are selected I can end up with areas that are considered "empty" when they should be "solid".

Take for example the splitting planes chosen in pictures 2 through 5.  If the splitting planes are selected in that order, then the interior of the "room" will be considered empty space.  This is incorrect because everything is encased by the blue hull so everything should be considered "solid".

What is the correct way to deal with this?

I think it would work if you build a regular BSP first, and finally remove non solid leaves to convert it to 'solid-leaf BSP'.

So while building the tree, each split generates a convex polygon by splitting the parent.

Each edge segment of the polygons can store multiple brush IDs for their front and back side. (the blue box has its own ID as input data, and also each of the black boxes.)

After no more split can be found and a polygon turns out to be a leaf, you search for the ID that is common to all edges and assign it to the polygon. (The empty space in your image would have the ID of the blue box, so it's solid.)

In case of multiple IDs have been found, you would just use the highest ID or have some other way of pre-defined order. (Highest ID means probably last user edit, so makes some sense.)

Hope this works... can't remember how i did this myself

Thank you for the suggestion!  I need clarification on a few things:

On 7/27/2018 at 5:32 AM, JoeJ said:

I think it would work if you build a regular BSP first, and finally remove non solid leaves to convert it to 'solid-leaf BSP'.

Could you clarify what a "regular" BSP is?  I'm aware of three distinct kinds: node-storing, leaf-storing, and solid-leaf.

On 7/27/2018 at 5:32 AM, JoeJ said:

Each edge segment of the polygons can store multiple brush IDs for their front and back side.

Would there be two separate lists (one for the brushes in front and one for the brushes behind) or just one list combining both?

Assuming there are two separate lists and a child node only considers brush Id's belonging to either the front or back list of its parent node (depending upon which side its on) when creating its own lists, then won't it fail in the following case?:

In picture #5 only the front list of the new splitter would contain the Id of the blue brush.  That means the splitter created in picture #6 would only consider its parents back list which lacks the blue brush.

3 hours ago, scarypajamas said:

Could you clarify what a "regular" BSP is?  I'm aware of three distinct kinds: node-storing, leaf-storing, and solid-leaf.

Sorry, i'm not well informed about those kinds. However, the idea should work with minor modification for any approach i guess.

What i mean is that the BSP needs to be build for the entire area, and only after completition the brush for a leaf can be determinated. As a post process you could remove branches of the tree that turn out useless.

3 hours ago, scarypajamas said:

Would there be two separate lists (one for the brushes in front and one for the brushes behind) or just one list combining both?

Yes. Two lists because for any split you can already be sure what is at front and back - you are only unsure about which IDs will matter later.

I don't think a single list is sufficient.

Edit:

hmm... you're probably right. Following my own advice of thinking about spaces not splits, yes there should be only one list that just contains all brushes intersecting the nodes space (defined by it's convex polygon).

That's the origin of all the confusion i guess - makes sense now, almost  

Likely it's not necessary to iterate over edges to find a common ID for leafs. There may be more ID than one for intersecting brushes, but for the openeng post the leaf marked 'empty' would contain only the blue box ID.

3 hours ago, scarypajamas said:

In picture #5 only the front list of the new splitter would contain the Id of the blue brush.

No, all splits in the images would contain the blue brush at front and back.

A parent ID could be ignored for the child only if the child space does no longer intersect the brush, but all spaces we see intersect the blue brush. So the blue brush ID would propagate down to all the leaf nodes that intersect it.

I think it's easier to imagine if you think about the polygon shape for each nodes space, but hard to imagine if you focus only on the split line.