12
$\begingroup$

I was reading this paper about Voxelpipe, a voxelization library from NVIDIA and I found on section 2 Voxelization the terms 6-separating and 26-separating

I found this website that tries to explain the basic ideas on voxelization but it wasn't very much helpful understanding the terms mentioned.

Can anybody explain or point out to some other resource that can help me understand?

$\endgroup$
18
$\begingroup$

The terms have to do with the "thickness" of the voxelization. I'll illustrate with the help of a diagram about 2D line rasterization (from this unrelated question).

enter image description here

On the right is the typical line rasterization: the algorithm finds the one pixel nearest the line within each row (or column, depending on slope). This produces what we usually think of as a "1-pixel-thick" line. On the left is a conservative rasterization, which finds every pixel whose rectangle is touched by the line, and it produces a thicker line.

6-separating voxelization is like the thin line on the right, and 26-separating is like the thick line on the left, but in 3D. If you imagine the line is actually a triangle viewed on-edge, this is analogous to what the voxelization would look like.

Different types of voxelization may be better depending on what you're going to do with the voxelized data later. If you're using the voxels as a spatial hierarchy to find triangles that intersect a given region, you probably want the thick voxelization, as it's conservative. The thick voxelization might also be preferable for ray-marching, as the thin voxelization could be missed by a diagonal ray. On the other hand, the thin voxelization is a more faithful representation of the original surface, which is probably better for visibility tests, collision detection, fluid simulation, and suchlike.

The "n-separating" terminology is a bit unfortunate, but here's what it's getting at. Imagine you're doing a 3D flood-fill in the voxel grid, but in the flood-fill you only look at the 6 direct neighbors of each voxel (±1 step along each axis). Then the "6-separating" (thin) voxelization will stop the flood-fill: it suffices to separate the two sides of the surface, if only 6 neighbors are considered. On the other hand, suppose your flood-fill was allowed to go to diagonal neighbors as well—26 neighbors in all (3×3×3 neighborhood of voxels). Then the 6-separating voxelization wouldn't stop the flood fill, but the 26-separating (thick) one would.

$\endgroup$
2
  • $\begingroup$ Nice ! Your explanation gives me the intuition about it. Do you happen to have some sources where I can read a bit more about rasterization? I suppose this n-separating stuff comes from 2D where is easier to understand and then I can do more thinking to grasp the 6- and 26-separating in 3D. $\endgroup$
    – BRabbit27
    Dec 9 '15 at 14:47
  • 1
    $\begingroup$ @BRabbit27 I don't think the "n-separating" terminology is used much in 2D rasterization; I've only seen it when discussing voxelization. It just refers to the number of neighbors. I'll add a bit to the answer about that. $\endgroup$ Dec 9 '15 at 18:11

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.