确定三角形所在的体素 [英] Determine voxels that a triangle is in

问题描述

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

Given a voxelization of the environment and a triangle with vertices A, B, and C, what would be the best way to determine which voxels that the triangle "occupies" or resides in? In other words, how can can I enumerate all of the voxels in which any part of the triangle is in it?

推荐答案

首先，你需要一个体素/三角形相交测试.

First, you need a voxel / triangle intersection test.

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

• To achieve this, a natural approach is to apply repeatedly a polygon-clipping algorithm (for instance Sutherland-Hodgman in 3D) on the triangle using the half-planes of the six faces of the cube and check what is left afterwards.

一种更好的方法在 Graphics Gems III, Triangle-Cube Intersection, pp. 236-239 (an 实现可用).

A better approach is described in Graphics Gems III, Triangle-Cube Intersection, pp. 236-239 (an implementation is available).

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

Then, you need to enumerate all the voxels intersected by the triangle.

• 第一种可能的方法:

• A first possible approach:

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

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

1. Compute the 3D axis-aligned bounding box of the triangle.
2. Snap this bounding-box to the voxel grid (flooring/ceiling the min/max vertices of the box) to get a 3D range of voxels [xmin,xmax]x[ymin,ymax]x[zmin,zmax]

3. Sweep the voxels to find out which ones are intersected by the triangle:

• 对于 [xmin, xmax]

• 对于 y 在 [ymin, ymax]

• 对于[zmin, zmax]

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

Check whether the voxel (x, y, z) intersects the triangle

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

This can be optimized in at least a few ways:

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

1. The quantities involved in the voxel / triangle intersection test can be computed incrementally in the various for loops.
2. The range of the last for loop might be reduced by considering only voxels intersecting the supporting plane of the triangle.
3. The order of the loops might be changed to prioritize some axis over another one (to take into account the orientation of the triangle).

第二种可能的方法:

A second possible approach:

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

这篇关于确定三角形所在的体素的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！