给定一个环境的体素化和一个由顶点 A、B 和 C 组成的三角形，如何确定三角形所“占用”或存在的所有体素？换句话说，如何枚举所有包含三角形任意部分的体素？
2个回答
7
首先，您需要进行体素/三角形相交测试。
为了实现这一点，一种自然的方法是使用六个立方体面的半平面重复应用多边形裁剪算法（例如在3D中的Sutherland-Hodgman），并检查之后剩下的部分。
更好的方法在《图形宝石III》中有描述，三角形-立方体相交，第236-239页（有实现可用）。
然后，您需要枚举所有被三角形相交的体素。
为了实现这一点，一种自然的方法是使用六个立方体面的半平面重复应用多边形裁剪算法（例如在3D中的Sutherland-Hodgman），并检查之后剩下的部分。
更好的方法在《图形宝石III》中有描述，三角形-立方体相交，第236-239页（有实现可用）。
然后，您需要枚举所有被三角形相交的体素。
第一种可能的方法：
- 计算三角形的3D轴对齐包围盒。
- 将此包围盒捕捉到体素网格上（将框的最小/最大顶点向下取整/向上取整），以获得一个3D体素范围
[xmin,xmax]x[ymin,ymax]x[zmin,zmax] 扫描体素以找出哪些体素与三角形相交：
对于
x在[xmin, xmax]中对于
y在[ymin, ymax]中对于
z在[zmin, zmax]中检查体素
(x, y, z)是否与三角形相交
这可以通过以下至少几种方式进行优化：
- 在各种
for循环中可以逐步计算涉及到的数量。 - 通过仅考虑与三角形支撑平面相交的体素，可以减少最后一个
for循环的范围。 - 可以更改循环的顺序，以优先考虑某个轴（以考虑三角形的方向）。
第二种可能的方法：
- 选择三角形的一个顶点并找出其中包含的体素。该体素将用作种子。
- 从此种子体素开始，对与三角形相交的体素进行广度优先搜索（BFS）或深度优先搜索（DFS），即：
- 跟踪已经测试了哪些体素与三角形相交，
- 处理与相交体素相邻但未经测试的所有体素，但
- 仅将与三角形相交的体素排队（BFS）或推入（DFS）。
- user3146587
6
1
最好的方法是使用DDA进行光栅化，因为它比任何三角形盒测试快几倍。光栅化是一种分散技术，因此它只触及三角形表面上的体素。盒测试是一种聚集技术，因此需要每个体素检查哪些三角形与其接触。前者（分散）是O(n^2)，而后者（聚集）是O(n^3)。
有关两者的良好CPU比较，请参见： https://github.com/ramakarl/voxelizer 此代码演示了两种聚集技术Schwarz-Seidel和Akenine-Moller，以及一种分散技术，基于边缘的2D DDA。
有关两者的良好CPU比较，请参见： https://github.com/ramakarl/voxelizer 此代码演示了两种聚集技术Schwarz-Seidel和Akenine-Moller，以及一种分散技术，基于边缘的2D DDA。
- Rama Carl Hoetzlein
1
你的演示甚至无法编译，能否请您将缺失的函数添加到项目中？https://github.com/ramakarl/voxelizer/issues/1 - Mashpoe
网页内容由stack overflow 提供, 点击上面的可以查看英文原文，
原文链接
原文链接
[xmin,xmax] x [ymin,ymax] x [zmin,zmax]的体素，请对三角形进行平移，使立方体的中心点((xmin+xmax)/2,(ymin+ymax)/2,(zmin+zmax)/2)位于原点，然后对三角形进行非均匀缩放，缩放比例为(xmax-xmin,ymax-ymin,zmax-zmin)，最后调用提供的实现代码（即不要更改代码，而是转换您的三角形）。 - user3146587(1/(xmax-xmin), 1/(ymax-ymin), 1/(zmax-zmin))，而不是(xmax-xmin, ymax-ymin, zmax-zmin)。 - Matheus Gadelha