CONSERVATIVE CELL AND PORTAL GRAPH GENERATION

摘要

Embodiments presented herein provide techniques for creating and simplifying a cell and portal graph. The simplified cell and portal graph may be used to make a conservative determination of whether an element of geometry is visible for a given view frustum (and therefore needs to be rendered). That is, the simplified cell and portal graph retains the encoded visibility for given set of geometry. The simplified cell and portal graph provides a “conservative” determination of visibility as it may indicate that some objects are visible that are not (resulting in unneeded rendering), but not the other way around. Further, this approach allows cell and portal graphs to be generated dynamically, allowing the cell and portal graphs to be used for scenes where the geometry can change (e.g., as 3D world of a video game).

主权项

1. A computer implemented method for generating a cell and portal graph corresponding to graphics data, the method comprising:
voxelizing the graphics data; generating an initial cell and portal graph for the voxelized graphics data; and simplifying the initial cell and portal graph by repeatedly:
selecting a first cell in the initial cell and portal graph, andgrowing the first cell in the initial cell and portal graph by merging cells neighboring the first cell until the first cell cannot be grown further without exceeding a specified measure of occlusion.