Conservative cell and portal graph generation

A non-transitory computer-readable storage medium storing code for execution by a processor, wherein the code, when executed, performs an operation for generating a cell and portal graph corresponding to graphics data, the operation comprising:

• voxelizing the graphics data;
• tagging, in the voxelized graphics data, voxels that do not intersect geometry in the graphics data as empty and voxels that intersect geometry as solid;
• 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, and
• growing 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 by repeatedly:
• casting, between the first cell and a cell neighboring the first cell, a specified plurality of rays between points on portals of the first cell and points on portals of the cell neighboring the first cell,
• for each ray, determining whether the ray is occluded by a solid voxel, and
• determining a percentage of occluded rays relative to the specified plurality of rays.

A system, comprising:

• a memory;
• and
• a processor storing a game platform application, which, when executed on the processor, perform an operation for generating a cell and portal graph corresponding to graphics data, the operation comprising:
• voxelizing the graphics data,
• tagging, in the voxelized graphics data, voxels that do not intersect geometry in the graphics data as empty and voxels that intersect geometry as solid,
• 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, and
• growing 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 by repeatedly:
• casting, between the first cell and a cell neighboring the first cell, a specified plurality of rays between points on portals of the first cell and points on portals of the cell neighboring the first cell,
• for each ray, determining whether the ray is occluded by a solid voxel, and
• determining a percentage of occluded rays relative to the specified plurality of rays.