ConvexSubspaces, BSP builder performance
I have now merged my convex-subspace branch to the master. This branch achieves three primary goals:
This is work that I originally committed to the revise-map-geometry-generation branch back in Spring this year. I didn't want this work to become stranded in that branch (as it has since moved on to some large scale renderer changes, which won't be ready for a while).
ConvexSubspace
Replacing BspLeaf as the public representation of a convex map-subspace, this new class fully separates the concepts of a binary tree half-space and convex subspace, which to date have both been represented using the same component. A single component which combines these critically different interpretations of the map space has significant architectural design drawbacks in an object-oriented model of the map geometry.
It is because of the dual nature of the BSP leafs (i.e., SUBSECTORS) in the id Tech 1 map format, combined with the vanilla software renderer's flood-fill algorithm for drawing planes, that allows for all manner of maphacks to even work. Essentially, the software render's algorithm will "switch definitions" of a BSP leaf at very specific points.
Separating the two definitions into discreet components has cleaned up many areas of the engine. In the process, separating the structure of the BSP tree from the description of the subspaces themselves. Another more subtle improvement is that the old concept of a "degenerate" BSP leaf has been replaced with the more intuitive "is a convex subspace present".
Hidden BSP
While completely irrelevant to the end user, this is a significant architectural milestone from the engine's (and our) perspective. Hiding the BSP within the engine (aside for opaque BspLeaf pointers in map objects, such as mobjs) will facilitate fundamental design changes to the map data model in the future. (The most likely next step will be reading the id Tech 1 BSP data stored in the map (if present) for use with the playsim only; collision detection, etc...)
The upshot of these changes is that BspLeaf and BspNode are no longer addressable via the Map API (DMU) and in general one does not need to be concerned about the BSP at all on game side.
BSP builder performance
The built-in BSP builder now utilizes multitasking to accelerate generation through concurrent evaluation of candidate-partition lines.
Evaluating the suitability and potential cost of a would-be partition line is perhaps the most computationally expensive part of a BSP generation algorithm. In our version, the idea is to examine each line segment (in the id Tech 1 map format, these are produced from LineDefs) in order to pick the most effective partition with which to subdivide space during the next iteration. Naturally one cannot be altering the BSP during the evaluation process (at least, not in the same half-space...), so each evaluation task is examining the same data. This results in an algorithm that is well suited for a multitasking solution, allowing these evaluation tasks to be performed concurrently.
Fortunately libcore's TaskPool provided exactly the kind of mechanism I needed for this. The BSP builder and data model would require some significant changes, however.
After revising the algorithm and achieving a basic model for multitasking I tried out a couple of (successively more complex) alternative models. The model I settled on was that which performed the best in my benchmarks; prepare the candidate work set, wait for all tasks to complete and then select the partition with the least cost from the work set. More complex models involving the cancelling of tasks when a new best choice was found actually turned out to be significantly worse due to the overhead involved in managing the tasks, locking, etc...
This yielded a healthy ~55% performance improvement in BSP generation time. Obviously, it is large and/or complex maps that stand to benefit the most.
I'm now pretty happy with the performance of Doomsday's BSP builder. Most of the time a BSP can be generated quickly enough that the user won't notice its being done. There are some obvious trajectories for future improvement (e.g., concurrent half-space subdivision) but once a caching mechanism is introduced for the most complex of maps it becomes largely irrelevant to tune this further.
- Extracted ConvexSubspace from de::BspLeaf improving SoC
- The Map's BSP is effectively hidden on game side
- Improved BSP builder performance significantly (~55%)
This is work that I originally committed to the revise-map-geometry-generation branch back in Spring this year. I didn't want this work to become stranded in that branch (as it has since moved on to some large scale renderer changes, which won't be ready for a while).
ConvexSubspace
Replacing BspLeaf as the public representation of a convex map-subspace, this new class fully separates the concepts of a binary tree half-space and convex subspace, which to date have both been represented using the same component. A single component which combines these critically different interpretations of the map space has significant architectural design drawbacks in an object-oriented model of the map geometry.
It is because of the dual nature of the BSP leafs (i.e., SUBSECTORS) in the id Tech 1 map format, combined with the vanilla software renderer's flood-fill algorithm for drawing planes, that allows for all manner of maphacks to even work. Essentially, the software render's algorithm will "switch definitions" of a BSP leaf at very specific points.
Separating the two definitions into discreet components has cleaned up many areas of the engine. In the process, separating the structure of the BSP tree from the description of the subspaces themselves. Another more subtle improvement is that the old concept of a "degenerate" BSP leaf has been replaced with the more intuitive "is a convex subspace present".
Hidden BSP
While completely irrelevant to the end user, this is a significant architectural milestone from the engine's (and our) perspective. Hiding the BSP within the engine (aside for opaque BspLeaf pointers in map objects, such as mobjs) will facilitate fundamental design changes to the map data model in the future. (The most likely next step will be reading the id Tech 1 BSP data stored in the map (if present) for use with the playsim only; collision detection, etc...)
The upshot of these changes is that BspLeaf and BspNode are no longer addressable via the Map API (DMU) and in general one does not need to be concerned about the BSP at all on game side.
BSP builder performance
The built-in BSP builder now utilizes multitasking to accelerate generation through concurrent evaluation of candidate-partition lines.
Evaluating the suitability and potential cost of a would-be partition line is perhaps the most computationally expensive part of a BSP generation algorithm. In our version, the idea is to examine each line segment (in the id Tech 1 map format, these are produced from LineDefs) in order to pick the most effective partition with which to subdivide space during the next iteration. Naturally one cannot be altering the BSP during the evaluation process (at least, not in the same half-space...), so each evaluation task is examining the same data. This results in an algorithm that is well suited for a multitasking solution, allowing these evaluation tasks to be performed concurrently.
Fortunately libcore's TaskPool provided exactly the kind of mechanism I needed for this. The BSP builder and data model would require some significant changes, however.
After revising the algorithm and achieving a basic model for multitasking I tried out a couple of (successively more complex) alternative models. The model I settled on was that which performed the best in my benchmarks; prepare the candidate work set, wait for all tasks to complete and then select the partition with the least cost from the work set. More complex models involving the cancelling of tasks when a new best choice was found actually turned out to be significantly worse due to the overhead involved in managing the tasks, locking, etc...
This yielded a healthy ~55% performance improvement in BSP generation time. Obviously, it is large and/or complex maps that stand to benefit the most.
I'm now pretty happy with the performance of Doomsday's BSP builder. Most of the time a BSP can be generated quickly enough that the user won't notice its being done. There are some obvious trajectories for future improvement (e.g., concurrent half-space subdivision) but once a caching mechanism is introduced for the most complex of maps it becomes largely irrelevant to tune this further.