确定三角形所在的体素

Question

给定环境的体素化和具有顶点A,B和C的三角形,确定三角形"占据"或居住的哪些体素的最佳方法是什么？换句话说,我怎样才能枚举三角形的任何部分所在的所有体素？

Answer 1

首先,您需要进行体素/三角形相交测试.

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

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

然后,您需要枚举与三角形相交的所有体素.

• 第一种可能的方法:

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

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

     • 对于x在[xmin, xmax]

       • 对于y在[ymin, ymax]

         • 对于z在[zmin, zmax]

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

  这可以通过以下几种方式进行优化:

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

• 第二种可能的方法:

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