指向 3d 封闭体积内

Question

我有一个由 6 个曲面定义的 3d 封闭体积，每个曲面都有 4 个顶点。

所以，我想检查给定的点是在体积内还是在体积外。我想到的一个解决方案是：

1. 从给定点绘制一条随机线并检查它与包围体积的表面相交的位置。由于我使用矢量代数来计算线和曲面的交点，因此交点可以位于 3d 无限曲面上的任何位置。

2. 现在我检查这个交点是否恰好位于位于无限平面上并包围体积的那个面上。

为此，我再次想从我的交点到体积的各个面绘制一条随机光线，并检查点是否位于面上。

But I don't know how to check this feature of locating if it is on the surface  
or not. Can someone please suggest how can I do it.



P.S. One way of doing this was extending ray casting to 3d but that involves 
comparison of slopes to check the orientation. So how can I check orientation 
of 3 points in 3d space. I have 4 vertices which make up that face, I know the 
point under consideration. How can I check if this point lies clockwise or   
counter clockwise to the surface. 

Answer 1

要考虑你的问题，首先要考虑内在或外在的含义。对于四面实体，每个面恰好将空间划分为两个边，通常，四个面将空间划分为 9 个区域，其中只有一个区域是有界的，界定了一个四面体（但如果我们仔细选择这些面，我们可以甚至可以到达没有边界的区域——例如使它们中的两个平行）。所以，一般来说，你必须决定平面的哪一边标记内侧或外侧（好吧，这也没关系，因为在外面和不在里面是一样的）。

有了更多的面，问题就会变得复杂（并且进一步复杂化），因为您可以有几个也定义实体的有界区域，因此您需要更多信息，而只有限定它的平面。这个问题甚至更加复杂更多，如果在非凸区域的区域的结果，因为你的观点可以在您所在地区的某些部分将匹配在一个侧面对一些飞机和在错误的一面给别人，并继续在里面的固体. 只需看到像这样的分隔多边形

以及制作有界区域的可能性

您需要做的第一件事是充分定义您的实体，用边定界面，并在某种程度上建立定界一个面的边和顶点，面如何相互连接以形成您的实体。

一旦你遇到这种情况，你就有了一组面，每个面都有指向外部的向量（以连续的方式，所以你不会以一个面法线指向上方，下一个指向下方）结束。您需要做的下一件事是将您的实体划分为一个凸实体。可以证明，对于由平面构成的 3d 实体，它可以细分为有限的凸实体集。

我将尝试在 2D 中说明相同的问题，但在 3D 中本质上是相同的：

首先，我们有初始的 poligon，假设它是凸的（这是一个重要的性质，我将在后面提到）：

假设它是一颗 3D 小行星，而您是在其表面行走的人。如果你开始走路，你会穿过所有黄色的线。这些是法线，为此您需要从每个面了解哪些面是可到达的，并像我所做的那样构建这些表面的法线图。当您在小行星上行走时，您会标记法线以了解小行星内部的位置，并对其进行划界。现在，我们有了一张包含所有法线的小行星地图。让我们绘制我们下方的半空间（表面的一侧在我们下方）在几何学中，这可以用平面表示（平面具有其所有点都与向量正交的特性，因此X*V=0其中*表示点积。如果我们把我们的poligon以及法线作为我们的图中黄色矢量的中心，我们会得到(X - P)*N = 0，其中X在平面上的点的位置，P是我们的位置（脸部的中心）N是一个向量垂直于平面，指向上方（指向小行星的外部）

嗯，这个方程有一个性质，如果我们用X空间中的任何位置代替，X平面以下的所有点都有一个值(X - P)*N < 0，所有天空的值都有它> 0。

如果我对四个法线做同样的事情，我会得到这个： ... 处理 并且X只有当四个平面给出(X - X_face)*(N_face) < 0现在的位置时，有问题的点才会被埋在小行星中，X_face是面的中心，面N_face是指向我们小行星外面的法线。仅当四个条件适用时，该点才会位于小行星内部。

但是如果小行星不是凸面会发生什么？

如果您绘制法线，这将无济于事......因为小行星内部有一些点并且无法通过一些测试（请记住，该点必须在所有表面下方，但不是（如下所示） ：

问题是多边形（或多面体）不是凸的，我们不能在那里应用算法。所以首先我们要解决使它凸的问题。

如果您在越过一条边时开始沿着小行星的所有表面（保留法线），您将到达另一个增加或减少坡度的平面，因此如果它增加坡度，您将标记该边（我们的顶点中的顶点）多边形）作为异常（我们将它们标记为红色），如果它减少，我们会将它们标记为正常（我们将它们标记为绿色）：

当所有边缘都正常时，没问题，因为我们的小行星将是凸面的，但是当它们中的任何一个异常时，我们必须继续在那个平面上（在所有平面上挖掘小行星）直到我们到达另一个表面（我们有延长飞机以划分我们的poligon）如下：

因为我们有有限数量的边，并且只有其中一些被标记为异常，所以这个过程必须完成（请记住，你可以让另一边试图找到你的多面体（多边形）的一个面（边）有顶点向上和顶点向下（在我们之前解释的意义上））

所以你已经把你的多面体分成了一个有限的凸多面体集，可以应用第一个算法。