This article deals with overcoming the unconscious boundaries that are often set in a project to create a 3D configurator. It then describes the various techniques that John Cormack has used to develop his Visible Surface Determination (VSD) and Culling (VSD) algorithms in Quake. This includes a description of the potentially visible set (PVS), also known as visibility lists.

Visible Surface Determination Quake

BSP-based culling.

The biggest challenge for programmers is regularly the shifting of the VSD with the limited tasks of screening such as the perspective correct texture mapping in the hardware. Spatial subdivision is one approach and it mentions the representation of Quake levels as 3D BSP and it is noted that this BSP does not store polygons in tree nodes but in the sheets.

It then explains the culling of polygons completely outside the view frustration and points out the advantages of culling the entire BSP subtress, which requires the maintenance of boundary frames or spheres with each node.

Overlap.

The problem of overdrawing is most obvious when back-to-front BSP traversing the Painter algorithm. Your world won’t be scalable and performance will not only be slow, but even worse, it won’t be even. It’s worth noting that with a Quake level of 10,000 polygons, an overrun of ten or more times was not uncommon in worst-case scenarios.

In order to solve this problem and reduce the overdraft to a manageable and above all flat size, John Carmack tried a variety of different approaches:

  • Beam tree (View Frustum Subdivision by Hierarchy of Clipping Levels)
  • Subdivision of the raycast (8×8 pixel raster)
  • Whirl-free surfaces (infinite level representations)
  • Draw Buffer (a 1-bit “already drawn” flag buffer)
  • Chip-based drawing
  • Portals

Potentially visible sets.

The final solution found by John Cormack was a precalculated lookup that provided a list of Potentially Visible Leaves (PVS) for each leaf of the BSP. This in turn requires the world to be static and the viewing direction to be disregarded (a common misconception with BSP trees as well). A raw PVS is quite large, but the RLE compression and modifications to the BSP Builder have reduced the size to 20K. The modifications mentioned by Cormack are:

  • Change of the split selection by heuristic,
  • Sealing the map.

Sealing here means to calculate a part of the hull of the world to determine surfaces that are not visible from anywhere in the world and to remove them. The idea of Quake-style rendering is in a densely populated world and a sealing process makes perfect sense. It refers to the brush-based CSG modeling used by QuakeEd. Seth Teller mentions a pre-processing step to identify small gaps and other leaks through polygons that are not perfectly contiguous, to map flaws that increase the PVS size immensely.

The BSP heuristic should be changed to produce fewer sheets, preferably the polygons that divide the fewest other polygons. This will result in less balanced trees, which in this case is not a big disadvantage, if I remember correctly.

We hope that we have been able to give you a first brief overview of the subject. If you have any questions or suggestions, please feel free to contact our experts in our forum.

Thank you very much for your visit.