给定环境的体素化和具有顶点A，B和C的三角形，确定三角形“占据”或居住的哪些体素的最佳方法是什么？换句话说，我怎样才能枚举三角形的任何部分所在的所有体素？
首先，您需要进行体素/三角形相交测试 .
为了实现这一点，一种自然的方法是使用立方体六面的半平面在三角形上重复应用多边形裁剪算法（例如3D中的Sutherland-Hodgman）并检查之后剩下的内容 .
图形宝石III，Triangle-Cube Intersection，第236-239页（可用implementation）中描述了一种更好的方法 .
然后，您需要枚举与三角形相交的所有体素 .
第一种可能的方法：
计算三角形的3D轴对齐边界框 .
将此边界框捕捉到体素网格（地板/天花板框的最小/最大顶点）以获得3D范围的体素 [xmin,xmax]x[ymin,ymax]x[zmin,zmax]
[xmin,xmax]x[ymin,ymax]x[zmin,zmax]
扫描体素以找出哪些与三角形相交：
For x in [xmin, xmax]
x
[xmin, xmax]
For y in [ymin, ymax]
y
[ymin, ymax]
For z in [zmin, zmax]
z
[zmin, zmax]
检查体素 (x, y, z) 是否与三角形相交
(x, y, z)
这可以通过以下几种方式进行优化：
体素/三角形相交测试中涉及的量可以在各种 for 循环中递增计算 .
for
通过仅考虑与三角形支撑平面相交的体素，可以减小最后一个 for 循环的范围 .
可以更改循环的顺序以将某个轴优先于另一个轴（以考虑三角形的方向） .
第二种可能的方法：
选择三角形的一个顶点，找出哪个体素包含它 . 该体素将用作种子 .
从此种子体素开始，对与三角形相交的体素进行广度优先搜索（BFS）或深度优先搜索（DFS），即：
跟踪已测试哪些体素与三角形相交，
处理交叉体素的所有未经测试的相邻体素，但是
队列（BFS）或推（DFS）仅与三角形相交的体素 .
1 回答
首先，您需要进行体素/三角形相交测试 .
为了实现这一点，一种自然的方法是使用立方体六面的半平面在三角形上重复应用多边形裁剪算法（例如3D中的Sutherland-Hodgman）并检查之后剩下的内容 .
图形宝石III，Triangle-Cube Intersection，第236-239页（可用implementation）中描述了一种更好的方法 .
然后，您需要枚举与三角形相交的所有体素 .
第一种可能的方法：
计算三角形的3D轴对齐边界框 .
将此边界框捕捉到体素网格（地板/天花板框的最小/最大顶点）以获得3D范围的体素
[xmin,xmax]x[ymin,ymax]x[zmin,zmax]扫描体素以找出哪些与三角形相交：
For
xin[xmin, xmax]For
yin[ymin, ymax]For
zin[zmin, zmax]检查体素
(x, y, z)是否与三角形相交这可以通过以下几种方式进行优化：
体素/三角形相交测试中涉及的量可以在各种
for循环中递增计算 .通过仅考虑与三角形支撑平面相交的体素，可以减小最后一个
for循环的范围 .可以更改循环的顺序以将某个轴优先于另一个轴（以考虑三角形的方向） .
第二种可能的方法：
选择三角形的一个顶点，找出哪个体素包含它 . 该体素将用作种子 .
从此种子体素开始，对与三角形相交的体素进行广度优先搜索（BFS）或深度优先搜索（DFS），即：
跟踪已测试哪些体素与三角形相交，
处理交叉体素的所有未经测试的相邻体素，但是
队列（BFS）或推（DFS）仅与三角形相交的体素 .