点在 3d 封闭体积内
Point inside a 3d closed volume
我有一个由 6 个曲面定义的 3d 封闭体积，每个曲面都有 4 个顶点。
因此，我想检查给定点是在体积内部还是外部。我想到的解决方案是：
从给定点随机绘制一条线，并检查它与封闭体积的表面相交的位置。由于我使用矢量代数来计算线和面的交点，因此交点可以位于 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.
您可以为每个曲面创建一个布尔条件，以确定给定点是在曲面内部还是外部。这可能需要您添加有关每个表面法线的信息（即表面的哪一侧是 'outwards'）。如果此条件对六个表面中的每一个都成立，则该点在体积内。
另一种类似的思考方式是创建一个线性不等式系统，使用每个表面创建一个不等式，创建一个封闭的 space 代表您的体积。这也归结为满足该点是 'inside' 还是 'outside' 每个表面，并检查该点是否在所有表面内。
看看这个问题：signed distance between plane and point
现在，您只需要检查您的点是否位于每个体积曲面的右侧（正确的符号）。像这样：
bool isInside(const std::vector<Planes>& planes, const Point& point){
for(const auto& plane : planes){
const auto dist =
dotProduct(plane.normal, vectorSubtract(point, plane.point));
if(dist>0) return false;
}
return true;
};
所以，我认为我可以做到这一点的一种方法是：
将光线投射扩展到 3d 表面，但这涉及从所考虑的点发出的光线穿过体积的次数。这涉及找到线与体积面的交点。
So what I can do is for a single face (and I will extend it to all the faces)
is, I check for the point of intersection of 3d line and plane by doing simple
algebra and then check if the point lies inside the cuboid formed by
extremities of the vertices forming the face. i.e check if P(x.y,z) which is
the point of intersection of line and plane lies inside the region defined by
extremities of the surface.
i.e.
x > xlow and x < xhigh and y > ylow and y < yhigh and z > zlow and z < zhigh.
These two conditions i.e. ray intersects the 3d plane and the intersection
lies in this region proves that the intersection of ray and plane lies on the
surface which encloses the volume.
I can count the number of such intersections if it is odd, the point
lies inside the volume if it is even the point lies outside the volume.
Does anyone see a problem with this algorithm?
考虑你的问题，首先要考虑inside或outside是什么意思。对于四面立体，每个面将 space 恰好划分为两侧，通常，四个面将 space 划分为 9 个区域，其中只有一个区域是有界的，界定了一个四面体（但如果我们 select 仔细地处理表面，我们甚至可以到达没有边界的区域——例如使其中两个平行）。所以，一般来说，你必须决定平面的哪一侧标记内部或外部（好吧，这也没关系，因为在外面和不在里面是一样的）。
有了更多的面，问题就变得复杂了（并且变得更加复杂），因为您可以有几个也定义实体的有界区域，所以您需要更多的信息，而不仅仅是界定它的平面。如果该区域导致非凸区域，问题甚至会更加复杂，因为您的点可能位于您区域的某些部分，与某些平面的 在一侧 和 在错误的一边 为别人，并继续在你的固体里面。只看到像这样的分隔多边形
以及制作有界区域的可能性
您需要做的第一件事是充分定义您的实体，用边界定面，并在一定程度上建立界定一个面的边和顶点，以及面如何相互连接以形成实体。
一旦你遇到这种情况，你就会有一组面孔，每张面孔都指向外部的向量（以连续的方式，所以你不会以一个面朝上，下一个朝下）。接下来需要做的是将实体分成凸实体。可以证明，对于一个由平面组成的3d立体，它可以细分为一组有限的凸立体。
我将尝试在 2D 中说明相同的问题，但在 3D 中本质上是相同的：
首先，我们有初始的多边形，假设它是凸的（这是一个重要的属性，我稍后会提到）：
让我们想象它是一颗 3D 小行星，而您是在其表面行走的人。如果你开始走路，你会穿过所有用黄色标出的线。这些是法线，为此您需要从每个面上知道哪些面是可到达的，并像我所做的那样构建这些表面的法线图。当您在小行星上行走时，您标记法线以了解小行星内部的位置，并且您正在划定它的边界。现在，我们有了一张包含所有法线的小行星地图。让我们画出我们下方的semispace（我们下方的表面的一侧）在几何中，这可以用一个平面来表示（一个平面具有属性，它的所有点都与a正交向量，所以 X*V=0 其中 * 表示点积。如果我们将多边形的中心和法向量作为我们绘图中的黄色向量，我们将得到 (X - P)*N = 0，其中X 是平面中一点的位置，P 是我们的位置（面的中心），N 是垂直于平面的向量，指向上方（向外）小行星）
嗯，这个等式有 属性 如果我们用 space 中的任何位置替换 X，平面下面的所有点 X 都有一个值(X - P)*N < 0 和所有的天空值都有它 > 0.
如果我对四个法线做同样的事情，我会得到这个：
...
处理
只有当四个平面给出 (X - X_face)*(N_face) < 0 时，所讨论的点 X 才会被埋入小行星中，现在 X_face 是表面的中心， N_face 是面对我们小行星的正常指向。该点将在小行星内部 仅 如果满足四个条件。
但是如果小行星不是凸面的会怎样？
如果绘制法线，这将无济于事...因为小行星内部有些点无法通过某些测试（请记住，该点必须在所有表面下方，但不是（如下图）：
问题是多边形（或多面体）不是凸的，我们不能在那里应用算法。所以首先要解决凸的问题
如果您在越过边缘时开始跟随小行星的所有表面（保持法线），您将到达另一个增加或减少坡度的平面，因此如果它增加坡度，您将标记边缘（我们多边形中的顶点）为异常（我们将它们标记为红色），如果它减少，我们将它们标记为正常（我们将它们标记为绿色）：
当所有边缘都正常时，没问题，因为我们的小行星将是凸的，但是当其中任何一个异常时，我们必须继续在那个平面上（在所有平面上挖掘小行星）直到我们到达另一个表面（我们延长了平面以划分我们的多边形）：
因为我们有有限数量的边，并且只有其中一些被标记为异常，所以这个过程一定会完成（记住你可以得到另一边试图找到顶点向上和顶点向下的多面体（多边形）的面（侧面）（在我们之前解释的意义上））
因此您已将多面体划分为一组有限的凸多面体，可以应用第一种算法。
我有一个由 6 个曲面定义的 3d 封闭体积，每个曲面都有 4 个顶点。
因此，我想检查给定点是在体积内部还是外部。我想到的解决方案是：
从给定点随机绘制一条线，并检查它与封闭体积的表面相交的位置。由于我使用矢量代数来计算线和面的交点，因此交点可以位于 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.
您可以为每个曲面创建一个布尔条件，以确定给定点是在曲面内部还是外部。这可能需要您添加有关每个表面法线的信息（即表面的哪一侧是 'outwards'）。如果此条件对六个表面中的每一个都成立，则该点在体积内。
另一种类似的思考方式是创建一个线性不等式系统，使用每个表面创建一个不等式，创建一个封闭的 space 代表您的体积。这也归结为满足该点是 'inside' 还是 'outside' 每个表面，并检查该点是否在所有表面内。
看看这个问题：signed distance between plane and point
现在，您只需要检查您的点是否位于每个体积曲面的右侧（正确的符号）。像这样：
bool isInside(const std::vector<Planes>& planes, const Point& point){
for(const auto& plane : planes){
const auto dist =
dotProduct(plane.normal, vectorSubtract(point, plane.point));
if(dist>0) return false;
}
return true;
};
所以，我认为我可以做到这一点的一种方法是：
将光线投射扩展到 3d 表面，但这涉及从所考虑的点发出的光线穿过体积的次数。这涉及找到线与体积面的交点。
So what I can do is for a single face (and I will extend it to all the faces)
is, I check for the point of intersection of 3d line and plane by doing simple
algebra and then check if the point lies inside the cuboid formed by
extremities of the vertices forming the face. i.e check if P(x.y,z) which is
the point of intersection of line and plane lies inside the region defined by
extremities of the surface.
i.e.
x > xlow and x < xhigh and y > ylow and y < yhigh and z > zlow and z < zhigh.
These two conditions i.e. ray intersects the 3d plane and the intersection
lies in this region proves that the intersection of ray and plane lies on the
surface which encloses the volume.
I can count the number of such intersections if it is odd, the point
lies inside the volume if it is even the point lies outside the volume.
Does anyone see a problem with this algorithm?
考虑你的问题，首先要考虑inside或outside是什么意思。对于四面立体，每个面将 space 恰好划分为两侧，通常，四个面将 space 划分为 9 个区域，其中只有一个区域是有界的，界定了一个四面体（但如果我们 select 仔细地处理表面，我们甚至可以到达没有边界的区域——例如使其中两个平行）。所以，一般来说，你必须决定平面的哪一侧标记内部或外部（好吧，这也没关系，因为在外面和不在里面是一样的）。
有了更多的面，问题就变得复杂了（并且变得更加复杂），因为您可以有几个也定义实体的有界区域，所以您需要更多的信息，而不仅仅是界定它的平面。如果该区域导致非凸区域，问题甚至会更加复杂，因为您的点可能位于您区域的某些部分，与某些平面的 在一侧 和 在错误的一边 为别人，并继续在你的固体里面。只看到像这样的分隔多边形
以及制作有界区域的可能性
您需要做的第一件事是充分定义您的实体，用边界定面，并在一定程度上建立界定一个面的边和顶点，以及面如何相互连接以形成实体。
一旦你遇到这种情况，你就会有一组面孔，每张面孔都指向外部的向量（以连续的方式，所以你不会以一个面朝上，下一个朝下）。接下来需要做的是将实体分成凸实体。可以证明，对于一个由平面组成的3d立体，它可以细分为一组有限的凸立体。
我将尝试在 2D 中说明相同的问题，但在 3D 中本质上是相同的：
首先，我们有初始的多边形，假设它是凸的（这是一个重要的属性，我稍后会提到）：
让我们想象它是一颗 3D 小行星，而您是在其表面行走的人。如果你开始走路，你会穿过所有用黄色标出的线。这些是法线，为此您需要从每个面上知道哪些面是可到达的，并像我所做的那样构建这些表面的法线图。当您在小行星上行走时，您标记法线以了解小行星内部的位置，并且您正在划定它的边界。现在，我们有了一张包含所有法线的小行星地图。让我们画出我们下方的semispace（我们下方的表面的一侧）在几何中，这可以用一个平面来表示（一个平面具有属性，它的所有点都与a正交向量，所以 X*V=0 其中 * 表示点积。如果我们将多边形的中心和法向量作为我们绘图中的黄色向量，我们将得到 (X - P)*N = 0，其中X 是平面中一点的位置，P 是我们的位置（面的中心），N 是垂直于平面的向量，指向上方（向外）小行星）
嗯，这个等式有 属性 如果我们用 space 中的任何位置替换 X，平面下面的所有点 X 都有一个值(X - P)*N < 0 和所有的天空值都有它 > 0.
如果我对四个法线做同样的事情，我会得到这个：
(X - X_face)*(N_face) < 0 时，所讨论的点 X 才会被埋入小行星中，现在 X_face 是表面的中心， N_face 是面对我们小行星的正常指向。该点将在小行星内部 仅 如果满足四个条件。
但是如果小行星不是凸面的会怎样？
如果绘制法线，这将无济于事...因为小行星内部有些点无法通过某些测试（请记住，该点必须在所有表面下方，但不是（如下图）：
问题是多边形（或多面体）不是凸的，我们不能在那里应用算法。所以首先要解决凸的问题
如果您在越过边缘时开始跟随小行星的所有表面（保持法线），您将到达另一个增加或减少坡度的平面，因此如果它增加坡度，您将标记边缘（我们多边形中的顶点）为异常（我们将它们标记为红色），如果它减少，我们将它们标记为正常（我们将它们标记为绿色）：
当所有边缘都正常时，没问题，因为我们的小行星将是凸的，但是当其中任何一个异常时，我们必须继续在那个平面上（在所有平面上挖掘小行星）直到我们到达另一个表面（我们延长了平面以划分我们的多边形）：
因为我们有有限数量的边，并且只有其中一些被标记为异常，所以这个过程一定会完成（记住你可以得到另一边试图找到顶点向上和顶点向下的多面体（多边形）的面（侧面）（在我们之前解释的意义上））
因此您已将多面体划分为一组有限的凸多面体，可以应用第一种算法。