确定三角形所在的体素

Question

给定环境的体素化和具有顶点a、B和C的三角形，确定三角形"占据"或驻留在哪些体素中的最佳方法是什么？换句话说，我如何才能枚举三角形任何部分所在的所有体素？

Answer 1

首先，需要进行体素/三角形相交测试。

• 为了实现这一点，一种自然的方法是使用立方体六个面的半平面在三角形上重复应用多边形剪裁算法(例如3D中的Sutherland Hodgman)，然后检查剩下的部分。

• 在Graphics Gems III，Triangle Cube Intersection，pp.236-239中描述了一种更好的方法(可获得一种实现方式)。

然后，需要枚举与三角形相交的所有体素。

• 第一种可能的方法：

  1. 计算三角形的三维轴对齐边界框
  2. 将此边界框捕捉到体素网格(框的最小/最大顶点的地板/天花板)以获得体素的3D范围[xmin,xmax]x[ymin,ymax]x[zmin,zmax]

  3. 扫描体素以找出哪些体素与三角形相交：

     • 对于[xmin, xmax]中的x

       • 对于[ymin, ymax]中的y

         • 对于[zmin, zmax]中的z

           检查体素(x, y, z)是否与三角形相交

  这至少可以通过以下几种方式进行优化：

  1. 体素/三角形相交测试中涉及的量可以在各种for循环中递增计算
  2. 可以通过仅考虑与三角形的支撑平面相交的体素来减小最后一个for循环的范围
  3. 循环的顺序可能会改变，以使某个轴优先于另一个轴(考虑三角形的方向)

• 第二种可能的方法：

  1. 选择三角形的一个顶点，找到包含该顶点的体素。该体素将用作种子
  2. 从该种子体素开始，对与三角形相交的体素进行广度优先搜索(BFS)或深度优先搜索(DFS)，即：
     • 跟踪哪些体素已被测试与三角形相交
     • 处理相交体素的所有未测试的相邻体素，但是
     • 仅排队(BFS)或推送(DFS)与三角形相交的体素

Answer 2

最好的方法是使用DDA进行光栅化，因为它比任何盒中三角形测试都快几倍。光栅化是一种散射技术，因此它只接触三角形表面上的体素。盒测试是一种收集技术，因此它们要求每个体素检查哪些三角形接触到它。前者(散射)为O(n^2)，而后者(收集)为0(n^3)。

要想更好地比较两者的CPU，请参阅：https://github.com/ramakarl/voxelizer

该代码演示了两种采集技术，Schwarz-Seidel和Akenine Moller，以及一种散射技术，即基于边缘的二维DDA。