确定三角形所在的体素 [英] 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 (在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，第236-239页(

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]中的x

• 对于[ymin, ymax]中的y

• 对于[zmin, zmax]中的z

检查体素(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)体素进行排队.

1. Choose one of the vertex of the triangle and find which voxel contains it. This voxel will be used as a seed.
2. Starting from this seed voxel, do a breadth-first search (BFS) or depth-first search (DFS) of the voxels intersecting the triangle, i.e.:
   • Keep track of which voxels have been tested for intersection with the triangle,
   • Process all the untested neighbor voxels of an intersecting voxel, but
   • Queue (BFS) or push (DFS) only voxels intersecting the triangle.

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