如何从中心向外遍历球形空间内的Voxel

核心思路 #

要实现从中心向外逐个遍历Voxel，核心是按与中心的距离分层处理：从距离0（中心本身）开始，依次处理距离1、2……直到指定半径r的所有Voxel。这种方式天然保证从内到外的顺序，且每个Voxel仅被处理一次，避免球坐标转换带来的冗余取整操作。

优化版Java实现（无冗余、低内存） #

这个实现通过分层遍历+整数运算避免浮点冗余，边生成边处理Voxel，无需存储所有点，适合大半径场景：

import java.util.function.Consumer;

public class SphericalVoxelTraversal {
    // 遍历从中心<cx, cy, cz>向外的球形Voxel，半径r，每个Voxel仅处理一次
    public static void traverseSphericalVoxels(int cx, int cy, int cz, int r, Consumer<int[]> voxelProcessor) {
        // 先处理中心Voxel（距离0）
        voxelProcessor.accept(new int[]{cx, cy, cz});
        
        int maxDistSquared = r * r;
        
        // 按距离层级d从1到r遍历
        for (int d = 1; d <= r; d++) {
            int currentDSquared = d * d;
            int prevDSquared = (d - 1) * (d - 1);
            
            // 遍历x轴范围
            for (int x = cx - d; x <= cx + d; x++) {
                int dx = x - cx;
                int dxSquared = dx * dx;
                int remainingForY = currentDSquared - dxSquared;
                if (remainingForY < 0) continue;
                
                // 计算y轴的有效范围
                int yMin = cy - (int) Math.sqrt(remainingForY);
                int yMax = cy + (int) Math.sqrt(remainingForY);
                for (int y = yMin; y <= yMax; y++) {
                    int dy = y - cy;
                    int dySquared = dy * dy;
                    int remainingForZ = remainingForY - dySquared;
                    if (remainingForZ < 0) continue;
                    
                    // 计算z轴的有效范围
                    int zMin = cz - (int) Math.sqrt(remainingForZ);
                    int zMax = cz + (int) Math.sqrt(remainingForZ);
                    for (int z = zMin; z <= zMax; z++) {
                        int dz = z - cz;
                        int distSquared = dxSquared + dySquared + dz * dz;
                        // 确保当前Voxel属于当前层级，且不超过最大半径
                        if (distSquared > prevDSquared && distSquared <= maxDistSquared) {
                            voxelProcessor.accept(new int[]{x, y, z});
                        }
                    }
                }
            }
        }
    }
    
    // 测试示例
    public static void main(String[] args) {
        traverseSphericalVoxels(0, 0, 0, 2, voxel -> {
            System.out.printf("处理Voxel: (%d, %d, %d)%n", voxel[0], voxel[1], voxel[2]);
        });
    }
}

实现说明 #

1. 分层处理：每个层级d对应距离中心在(d-1, d]范围内的Voxel，确保从内到外的顺序。
2. 整数运算优化：用距离平方代替浮点距离计算，仅在计算轴范围时使用一次sqrt取整，避免冗余操作。
3. 无重复遍历：每个Voxel只会在其对应的距离层级被处理一次，没有重复。

折中简化方案（小半径场景） #

如果半径r较小，可采用先收集所有球内Voxel，再按距离排序的方式，代码更简洁，代价是需要存储所有点：

import java.util.ArrayList;
import java.util.Comparator;
import java.util.List;
import java.util.function.Consumer;

public class SimpleSphericalTraversal {
    public static void traverseSphericalVoxelsSimple(int cx, int cy, int cz, int r, Consumer<int[]> voxelProcessor) {
        List<int[]> voxels = new ArrayList<>();
        int maxDistSquared = r * r;
        
        // 遍历所有可能的Voxel，收集球内的点
        for (int x = cx - r; x <= cx + r; x++) {
            int dx = x - cx;
            int dxSq = dx * dx;
            if (dxSq > maxDistSquared) continue;
            
            for (int y = cy - r; y <= cy + r; y++) {
                int dy = y - cy;
                int dySq = dy * dy;
                if (dxSq + dySq > maxDistSquared) continue;
                
                for (int z = cz - r; z <= cz + r; z++) {
                    int dz = z - cz;
                    int distSq = dxSq + dySq + dz * dz;
                    if (distSq <= maxDistSquared) {
                        voxels.add(new int[]{x, y, z, distSq}); // 存储距离平方用于排序
                    }
                }
            }
        }
        
        // 按距离中心的平方从小到大排序，保证从内到外
        voxels.sort(Comparator.comparingInt(v -> v[3]));
        
        // 遍历处理每个Voxel
        for (int[] voxel : voxels) {
            voxelProcessor.accept(new int[]{voxel[0], voxel[1], voxel[2]});
        }
    }
    
    public static void main(String[] args) {
        traverseSphericalVoxelsSimple(0,0,0,2, voxel -> {
            System.out.printf("处理Voxel: (%d, %d, %d)%n", voxel[0], voxel[1], voxel[2]);
        });
    }
}

方案说明 #

• 代码逻辑简单，容易调试，但内存开销随r³增长，适合r≤20的场景。
• 排序后严格保证从内到外的遍历顺序，每个Voxel仅处理一次。

内容的提问来源于stack exchange，提问作者klaytonme