Fastest visibility calculation towards all possible directions

Question

I am searching for your advice. I have a massive voxelized model, like the one in the picture (but with a few million voxels more..). To reduce the total number of the model’s triangulations, I can remove the shared faces among the voxels, nevertheless, the triangles will indeed remain MANY. What I need to do is create an index that will hold a boolean list (of visible/not visible) information, coming from the following procedure:

Define a set of points, like the centroids of the 3 yellow voxels in the picture (but, this set might again contain millions of points) and for each point calculate which voxels (except their corresponding containers) can be seen (direct and unblocked line of site) towards ALL directions (something like a global illumination concept). If the ray-source (coming from a given point) can reach even at the minimum a target voxel, it means we have a "true" condition for that voxel. For example, if we assume that the ray-source point in the picture is the light source, then all voxels in the blue circle are "true" for the specific point.

This has nothing to do with game development, so I am sorry if my post should be somewhere else. I just felt I should better ask here, because most of my searches conclude to ray-casting, hard shadows, visible surface determination, OpenGL, etc which are quite relevant here. I do not need to see any graphics (or have high fps :D), just store the results for future usage into a 3rd simulation process.

I get the feeling that if I go with implementing simply geometric calculations this indexing will run for too long (even though this can be parallelized quite easily I believe). Nonetheless, can I take advantage somehow of OpenGL and GPU maybe? Will this boost significantly my task? How should I approach the problem? I am working on an ASUS ROG-G752VY.

I only have to construct and store this index (which I would not be surprised if it would turn out to be tens of GBytes). The rest of the simulation runs on a cluster continuously. This indexing calculation operation will run more or less only once.

I just don't know what execution time to expect (days/weeks/years) with this amount of ray-source points that I am mentioning along with a "brute" check towards all directions and voxels (with or without the use of OpenGL and GPU). Yet, I can predict that the max number of visible voxels every time will be just a few thousand.

That, because (sorry for not mentioning it) there is a life-termination logic of this ray when the distance of its travel exceeds "x" units ("x" will be much much smaller than the size of the total model). Hence, for a ray further than "x" the searching process should break every time.

Thank you so much already for your time!!!

Answer 1

Minecraft has to solve a similar problem for culling caves and other landscape features that are occluded from view.

There's a detailed write-up here about the Advanced Cave Culling Algorithm they use, which may have some useful inspirations for this problem.

Their algorithm is approximate and conservative (it will err on the side of saying something is visible, even if it really isn't), but something along these lines could be useful as a first broad-phase pass, to thin the number of voxels you need to consider for more precise tests later.

The algorithm works by dividing the world into chunks of 16x16x16 voxels.

For each chunk, they compute whether a ray entering from one face of the chunk could exit through each other face (15 bools). They do this in a conservative way, by checking whether a flood fill starting at one face touches the other faces - so it will report "true" for some configurations that no straight ray could traverse. It works well enough to cull in situations when you have many solid walls/barriers, but if your voxels are more sparsely laid out you might want a more picky test at this stage.

Then they perform a breadth-first search through the grid of connected chunks, searching outward from the viewpoint, to get a list of potentially-visible chunks in front-to-back order (helping subsequent depth ordering early-out faster)

As you can see the results aren't perfect by any means. The method only looks at immediately adjacent chunks, so it can't see that the ravine at the far right is actually occluded by the rise to the left. But it does successfully eliminate much of the interior detail of the subterranean caves.

Subsequent raycasting against the chunk representation might allow further elimination (solving the original problem at a lower level of granularity)

Answer 2

You could assign a different color to each of the voxels, render your scene to a cubemap texture (sevaral times, from each starting point), then copy the texture to RAM and find all unique colors it contains.