定位不规则 3D 网格中包含点的单元格

发布于 2025-01-14 07:12:44 字数 1183 浏览 0 评论 0原文

我有一个不规则的 3D 网格，看起来像这样：网格的典型尺寸为 100/100/100 个单元。每个单元在空间上由 8 个角节点的坐标定义。单元每个面的 4 个顶点不一定共面，因此我将每个面表示为一对三角形，因此单元表示为由 12 个三角形（每个面 2 个）组成的多面体。我正在尝试使用 Python 查找包含 XYZ 点的单元格的 IJK 索引。我按顺序平分 I、J 和 K 方向上的单元格范围，并使用此处描述的方法测试该点位于网格的哪一半测试 3D 点是否在 3D 多面体内部以定位该点。不幸的是，这在某些情况下不起作用。在上图中，A点在物理上位于网格外部，但在当前平分范围内（由棕色虚线定义），而点B在网格内部但在当前范围之外。我认为这样做的原因是，代表当前范围内的细胞面的三角形（例如图中的大棕色三角形）与构成该范围内的各个细胞面的三角形（例如那些阴影的三角形）不共面。黄色、蓝色等）。我尝试在下面以 2D 形式展示这一点：当前的二等分范围由棕色虚线和棕色顶点显示。最初，红点位于当前范围内。我们沿 X 方向一分为二（二等分 1），红点在当前范围内（棕色虚线），因此我们丢弃右半部分。现在我们在 Y 方向上一分为二（二等分 2），红点超出了这个范围，所以我们丢弃上半部分。当我们在每个 I 和 I 中都有一个索引时，我们最终到达了最后一步。 J 方向。如图所示，这将红点放置在错误的单元格中。对于我目前正在尝试实现的算法的替代算法有任何建议，我将不胜感激。退一步来说，我实际上对计算网格内由一系列线段相交的面感兴趣，因此我使用“多面体中的点”方法作为中间步骤。我查看了 geomdl，它可以将每个面表示为 NURBS 对象，但似乎没有实现射线和 NURBS 对象之间的交集。我还快速浏览了与 CGAL 的 Python 绑定，但这看起来像是一个巨大的学习曲线，所以把它放在一边。提前致谢！

原文

I have an irregular 3D grid which looks something like this:
Typical dimensions of the grid are 100/100/100 cells. Each cell is spatially defined by the coords of the 8 corner nodes. The 4 vertices of the each face of a cell are not necessarily co-planar, so I represent each face as a pair of triangles and thus a cell as a polyhedron consisting of 12 triangles (2 per face). I am trying to locate the IJK index of the cell that contains an XYZ point using Python. I bisect sequentially the cell range in the I, J and K directions and test which half of the grid the point lies using the method described here Testing whether a 3D point is inside a 3D polyhedron to locate the point. Unfortunately, this does not work in some cases. In the above figure, point A is physically outside the grid but inside the current bisection range (defined by the brown dotted lines) while point B is inside the grid but outside the current range. I think the reason for this is that triangles representing the faces of the cells within the current range (eg the large brown triangles in the figure) are not co-planar with the triangles that comprise the individual cell faces within that range (eg those shaded yellow, blue etc). I have tried to show this in 2D below:

The current bisection range is shown by the brown dotted line and brown vertices. Initially, the red point is within the current range. We bisect in the X direction (bisection 1) and the red point is within the current range (dotted brown line) so we discard the right half. We now bisect in the Y direction (bisection 2) and the red point is outisde this range so we discard the top half. We eventually arrive at the final step when we have a single index in each of the I & J directions. As shown here, this places the red point in the wrong cell.
Would appreciate any suggestions for an alternative algorithm to the one I am currently trying to implement. Stepping back, I am actually interested in calculating the faces within the grid intersected by a series of line segments, so am using the "point in a polyhedron" method as an intermediate step. I looked at geomdl which could represent each face as a NURBS object but does not seem to implement intersection between a ray and a NURBS object. I also had a quick look at the Python bindings to CGAL but that looked like a massive learning curve to climb, so put that aside. Thanks in advance!