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.

Yes. I first wrote straight line, then thought that this was probably redundant to mention. — paniq, Mar 26 '15 at 15:26
O(n) seems a little optimistic to me; what's the worst complexity you would be comfortable with? — G. Bach, Mar 26 '15 at 16:02
Less than the worst complexity possible, which is O(N^5), marching from each possible entry point to each possible exit point. — paniq, Mar 26 '15 at 16:16
wouldn't it be more efficient to ask an inverse question, that is, if the conditions exist so that such a line *cannot* be drawn? — גלעד ברקן, Mar 26 '15 at 16:23
Can the line only pass through voxels that share a face, or is it sufficient for them to share a corner? — G. Bach, Mar 26 '15 at 18:03
Must share face, but both kinds of solutions might be interesting. — paniq, Mar 26 '15 at 19:20
Maybe here's something to get you started: every blocked voxel occludes paths that go through two pyramid stumps similar to double cones. If you can merge all blocked space efficiently, you could try to derive a characterization of unoccluded space that admits such a line. — G. Bach, Mar 26 '15 at 20:33
If i understood right, then in case of opposite faces at one layer a line can cross up to three voxels? — Yola, Mar 27 '15 at 09:18
Wait - does that mean in a cube of side length 2, we are not allowed to use straight lines from, say, (0,0,0) to (1,1,1)? — G. Bach, Mar 28 '15 at 01:52
oh, you're right. Yes, you can. I was thinking Chebyshev distance, but of course that doesn't apply here. — paniq, May 01 '15 at 16:21
The worst-case complexity is O(n^4). The depth does not matter if you consider the rays you have to cast from one n . n plane to the other n . n plane. If the observer is not a point-source, the occlusion question becomes a test if there is any 2d coordinate (x,y) that is not part of the blocking voxel coordinates (x,y,z). You can simply count them by using the x + y.n as a bucket index when going over all blocking cells. If all buckets are non-zero, the plane is completely occluded. — StarShine, Sep 01 '15 at 12:46
Hah paniq. Is this a troll or do you really want a fast approximation? Build a hierarchy of probability. 1x1x1 cubes are either 100% or 0% for a ray to pass through. What happens if we combine eight of them? etc... — starmole, Apr 20 '16 at 09:19

score 1 · Answer 1 · answered Dec 10 '20 at 01:15

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.

Khaled.K · Answer 2 · 2015-03-29T08:55:53.037

A Voxel cube would look like a Rubik Cube, voxel structure is a 3D matrix of blocks, so to draw a line from one side to the other, we need to draw within each related block the line that connects to the next, together the lines form one continuous line through the cube.

The following algorithm works fine if implemented well, since you're going to work on local coordinates within the cube, any transformations of the cube itself will be applied automatically by the 3D engine when it translate it into world coordinates.

Time Complexity

MATRIX.MAX_Z * (
                   Time(MATRIX.GET_VOXEL(x,y,z))
                 + Time(VOXEL.DRAW-LINE(0,0,0, 0,0,VOXEL_DEPTH))
               )

Algorithm

FUNCTION DRAW (INTEGER X, INTEGER Y)

    INTEGER VOXEL_X = X / MATRIX.VOXEL_WIDTH
    INTEGER VOXEL_Y = Y / MATRIX.VOXEL_HEIGHT

    FOR i = 0 .. (MATRIX.MAX_Z-1)

        VOXEL V = MATRIX.GET_VOXEL(VOXEL_X, VOXEL_Y, i)

        INTEGER X_0 = X % MATRIX.VOXEL_WIDTH
        INTEGER Y_0 = Y % MATRIX.VOXEL_HEIGHT
        INTEGER Z_0 = 0

        INTEGER X_1 = X_0
        INTEGER Y_1 = Y_0
        INTEGER Z_1 = (MATRIX.VOXEL_DEPTH-1)

        V.DRAW-LINE(X_0,Y_0,Z_0, X_1,Y_1,Z_1)

    END-FOR

END-FUNCTION

score 0 · Answer 3 · answered Apr 20 '15 at 03:32

So one easy way to do this test is to render the view (orthographic) from the source to the target cube at arbitrary resolution. If there is any background pixel left, there exists a line between the two rectangles. So the complexity comes down to two things:

The resolution at which you render
How fast can you render an orthographic, binary view

Now for that binary rendering the only thing you need to know is covered/not covered. That comes down to two octrees, one for minimum and one for maximum. The minimum tree tracks "is there any open child node (or)" the maximum tracks "is there any closed child node (and)". Building those trees is n log(n), but the query is only log(n).

For the target resolution, m, it should be only log(m). Even if you go up to m=2^23 for float size.

I'm afraid I don't understand what you mean by "source cube" and "target cube", nor by open or closed child nodes. If you approach this from a ray-tracing angle, you still need to check every pixel on the target side of the cube for light coming from any angle, i.e. any pixel on the source side of the cube. Sounds like O(n^4) to me... — Christian Severin, Jan 22 '16 at 20:06

score 0 · Answer 4 · edited May 23 '17 at 12:14

Breaking the problem down to two dimensions, it is clear that some voxel configurations are obviously impenetrable from, say, left to right:

    +-+-+-+          +-+-+-+-+-+
    | |#| |          |#| | | | |
    +-+-+-+          +-+-+-+-+-+
    | |#| |          |#| | |#| |
    +-+-+-+          +-+-+-+-+-+
    | |#| |          |#| | |#| |
    +-+-+-+          +-+-+-+-+-+
                     |#| | |#| |
                     +-+-+-+-+-+
                     | | | |#| |
                     +-+-+-+-+-+

... but this might not be impenetrable, depending on how you handle your corners:

  +-+-+-+-+-+
  |#| | | |/|
  +-+-+-+-+-+
  |#| | |/| |
  +-+-+-+-+-+
  |#| |/|#| |
  +-+-+-+-+-+
  |#|/| |#| |
  +-+-+-+-+-+
  |/| | |#| |
  +-+-+-+-+-+

... and this is definitely possible:

  +-+-+-+-+-+
  |#| | | | |
  +-+-+-+-+-+
  |#| | | | |
  +-+-+-+-+-+
  |#| | | | |
  +-+-+-+-+-+
  | | | |#| |
  +-+-+-+-+-+
  | | | |#| |
  +-+-+-+-+-+

Now, if you can think of any trick that can tell the upper 2D-cubes from the lower one, that might eliminate at least some impossible pixel/voxel configurations -- but I'm afraid you need to test every pixel on your target side for light coming through from your source side from any angle, which sounds awfully like an n-squared problem (2D), or n^4 in 3D.

In 2D, I'd start at the top of the left side and check if the line connecting my voxel centre to the top right hits an occluding pixel: if not, we're done; if it does, you advance your angle so that the ray passes the lower left corner of the occlusion and continue checking until you either find a passage or get to the end of the right side.

Continue with every pixel on your source side, until you are done -- one way or the other.

But that's brute-force, and I'd be interested to see a more elegant solution, perhaps by G. Bach ...?

Find a line connecting two faces of a cubic volume

4 Answers4