c++ - 指向3d封闭体积内

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

因此，我想检查给定点是在体积内还是在体积外。我想到的解决方案是:

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

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

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

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.

最佳答案

要考虑您的问题，我们首先必须考虑内部或外部的含义。在具有四个实体的曲面的情况下，每个曲面都将空间精确地划分为两个侧面，通常，四个曲面将空间划分为9个区域，其中只有一个是有界的，从而界定了四面体(但是如果我们仔细选择曲面，我们可以甚至没有边界区域-例如，使其中两个平行)。因此，通常必须确定飞机的哪一侧标记内部或外部(嗯，也没关系，因为在外部与不在内部相同)。

面对更多的面孔，问题会变得复杂(并进一步复杂化)，因为您可能有几个也定义了实体的有界区域，因此您需要更多的信息来仅用平面对其进行界定。如果该区域产生非凸形区域，则问题甚至更加复杂，因为您的点可能在区域的某些部分中，与某些平面的一侧匹配，而对于另一些平面则在错误的一侧，并且继续位于实体内部。只是看到这样的定界多边形

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

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

遇到这种情况后，您将拥有一组脸部，并且每个脸部的 vector 都指向外部(以连续的方式进行，因此您不会以正常的脸部朝上，而下一个脸部朝下而结束)。接下来需要做的是将实体分成凸形实体。可以证明，对于由平面构成的3d实体，可以将其细分为有限的凸实体集。

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

首先，我们有初始的poligon，让我们假设它是凸的(为此，这是一个重要的属性，我将在后面提到):

假设它是一个3D小行星，而您正在有人在其表面行走。如果您开始走路，您将穿过黄色的所有线条。这些是法线，因此您需要从每个面中知道哪些面是可到达的，并像我所做的那样构造这些面的法线图。当您在小行星上行走时，您会标记法线以知道小行星内部的位置，并对其进行界定。现在，我们有了小行星与所有法线的 map 。让我们在我们下方绘制一个半空间(在我们下方的表面的一侧)。在几何中，这可以用一个平面表示(一个平面具有其所有点都正交于 vector 的属性，因此X*V=0其中*表示点乘积。如果我们将多边形的中心点和法线 vector 作为图形中的黄色 vector ，则将得到(X - P)*N = 0，其中X是平面中点的位置，P是我们的位置(面的中心)，并且N是垂直于平面的 vector ，指向上方(指向小行星的外部)

好的，此等式具有的性质是，如果用空间中的任何位置替换X，则平面下方的所有点X都具有值(X - P)*N < 0，而所有天空值均具有> 0。

如果对四个法线执行相同的操作，则可以达到以下目的:

...

处理

并且只有当四个平面给出X时，才会将问题点(X - X_face)*(N_face) < 0埋入小行星，现在X_face是脸的中心，而N_face是指向我们小行星向外的法线。如果满足以下四个条件，则该点将位于小行星内，仅位于内。

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

如果您绘制法线，这将无济于事……因为小行星内部存在点且某些测试未通过(请记住，该点必须位于所有曲面之下，但并非必须如此(如下所示) :

问题在于多边形(或多面体)不是凸的，我们不能在那里应用算法。因此，首先我们必须解决使其凸出的问题。

如果您在穿越边缘时开始跟随小行星的所有表面(保持法线)，则将到达另一个增加或减少坡度的平面，因此，如果增加坡度，则将标记该边缘(在我们的顶点多边形)(异常标记为红色)，如果其减少，则将其标记为正常(标记为绿色):

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

由于我们的边数量有限，并且只有其中一些被标记为异常，因此此过程一定要完成(请记住，您可以让另一面尝试查找多面体(多边形)的面(面)具有顶点向上和顶点向下(就我们之前解释的意义而言))

因此，您已将多面体分为有限的一组凸多面体，可以应用第一种算法。

关于c++ - 指向3d封闭体积内，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/38214038/