三角形立方体/体素交叉点

检测三维空间中三维像素/立方体是否与三角形相交的最佳算法是什么？我有这个源码，用C：http://tog.acm.org/resources/GraphicsGems/gemsiii/triangleCube.c写成。我试图重构并将此代码转换为C++，但我意识到我真的不知道发生了什么。此外，评论指出三角形交点与单位立方体进行比较，但我无法找到一种方法来扩展算法以处理任何立方体/体素。三角形立方体/体素交叉点

检测三角形立方体交集有更清晰的实现（最好用C++）吗？如果不是，那么扩展C代码以使用任意多维数据集的最佳方式是什么？

预先感谢您

来源

2014-02-10 Cenk Baykal

的限制到一个单位立方体不应该是一个问题。您可以简单地翻译和缩放坐标系，使体素与单位立方体占据相同的空间。 –

一个简单的算法就是：

计算上的三角形所在的平面。
找到该平面与立方体（如果有的话）之间的交点。
如果没有交集，那么问题就解决了。
否则，找到穿过每个三角形边缘的直线。
对于每一行：如果交叉点位于“外部”，则不存在交集。
否则有一个十字路口。

如果您的“最佳”算法的标准是简单的，那么这将是一个很好的。如果你在寻找表现，那么可能会有更快的表现。

您也可以尝试寻找在托管代码：

http://fileadmin.cs.lth.se/cs/Personal/Tomas_Akenine-Moller/code/

来源

2014-02-10 04:14:38

这不是一个完整或正确的算法，立方体可能完全位于三角形的中心，与三角形的“面”相交而不与任何边相交。类似地，体素可以位于三角形的平面上，但离三角形非常远而没有相交。 –

我不认为你理解这个算法。它首先查看2D平面与立方体之间的交点，然后检查该交点是否位于三角形之外。该算法从不直接检查三角形边缘与立方体之间的交点。 –

我同意我不明白你写的是什么。那么，第二步和第三步中的交点是什么？一个点？一条线？多边形？这是第四步中提到的相同交叉点吗？当你写在三角形边缘的“外侧”时，你的意思是检查某个点是否位于与三角形穿过该边缘正交的平面所定义的左侧或右侧半空间中？我担心，如果在计算这个初始平面 - 立体交叉点（点？）时不小心，最终可能会出现误报和负面情况。 –

三角形立方体/体素交叉点

回答

相关问题