graphics - 确定三角形所在的体素

Question

关闭。这个问题需要多问 focused 。目前不接受答案。

---

想要改进此问题吗？更新问题，使其仅关注一个问题 editing this post .

已关闭 3 年前。

Improve this question

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

Answer 1

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

• 要实现此目的，一种自然的方法是使用立方体六个面的半平面在三角形上重复应用多边形裁剪算法(例如 3D 中的 Sutherland-Hodgman)，并检查什么是随后离开。

• Graphics Gems III，Triangle-Cube Intersection，第 236-239 页描述了一种更好的方法(implementation 可用)。

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

• 第一种可能的方法:

  1. 计算三角形的 3D 轴对齐边界框。
  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)。