Find a line connecting two faces of a cubic volume

Question

Imagine a volumetric cube of N³ resolution that is filled with occluding voxels. The cube could be completely filled, or contain curvy "tunnels", or walls - or just a few stray voxels; We now pick any two of the six faces of the bounding cube and attempt to find a line that connects those two faces without hitting any voxel inside it. If such a line exists, the faces can see each other, otherwise, they're completely occluded.

My question is: does an O(n) (or better) algorithm exist to quickly discern if such a line can be drawn? The exact parameters of the line do not matter.

Answer 1

I'm somewhat unclear on the exact parameters of being a straight line in this (continuous? discrete?) space, but I wonder if you're looking for a dynamic programming solution?

Perhaps lets restrict to 2-D left to right case to build the algorithm and then generalize:

Loop over first column of the array, for each opaque square, mark that it is impossible to build a ray which reaches this square for each non opaque square, mark that it is possible to reach this square -AND- track ranges of slopes can reach this square. You may restrict the set of slopes in this initialization by the set of slopes that could potentially reach the opposite end of your voxel volume.

Then loop over the next column Each square is potentially able to be reached by any square in the previous column, but only if the range of slopes that can reach the square in the previous column intersects the range of slopes necessary to reach the current square from the square in the previous column.
You thus set the valid range of slopes in the current square to the union of the intersections of the valid ranges from previous squares with valid ranges to current square.

You continue looping over columns until you hit the far end, and any reachable entries on the far end will report the ranges of slopes of vectors that allow hitting that square.

The speed of the algorithm is heavily dependent on how quickly you can union and intersect ranges of slopes (or in the 3D case, arbitrary ranges of UV coordinates). In 2D continuous space this operation can be done quickly by sorting, in a 3D discrete space, you can use a set of possible vector slopes in X,Y dependent on dimensions of your voxel space. In a 3D continuous space, some type of quadtree would probably approach what can be achieved by sorting in 2D.

The algorithm loops once over each cell in your input (Do you consider this O(n) or O(n^3)?), and takes time that will be bounded by the union of intersections call times the number of elements in your space (Worst case O(n^2) in discrete case I believe, but will shrink dramatically in the initialization step if the opposite end of the volume is far away, and may shrink quickly in the case of many opaque cells and proper data structures)

As far as I can tell, processing order of slices of the volume doesn't actually matter, so if you know that certain spots are very opaque (by sum of opaque cells or whatever), you might use a heuristic to reorder intersection operations.