剔除内部三角形
我有一个由数千个四边形组成的数组； 4 边 3D 多边形。我只知道四角的坐标。
这些四边形的子集定义了 3D 形状的封闭外壳。其余的四边形位于该封闭实体的内部。
如何确定哪些四边形是外壳的一部分，哪些四边形是内部的一部分？这不是性能关键代码。
编辑：对外壳形状的进一步限制
- 形状内部没有孔，它是单个表面。
- 它包含凸部和凹部。
- 我知道有几个点位于外壳的内部。
I have an array of thousands of quads; 4-sided 3D polygons. All I know are the coordinates of the quad corners.
A subset of these quads define the closed outer shell of a 3D shape. The remaining quads are on the inside of this closed solid.
How do I figure out which quads are part of the shell and which quads are part of the interior? This is not performance critical code.
Edit: Further constraints on the shape of the shell
- There are no holes inside the shape, it is a single surface.
- It contains both convex and concave portions.
- I have a few points which are known to be on the inside of the shell.
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（5）
如果您的形状自相交，这可能很难实现，但如果您可以找到一个已知的四边形在表面上（可能是距质心最远的一个），则可以在其周围绘制四边形的同心圆。然后在其外面找到一个连续的四边形环，依此类推，直到到达“相反”一侧。如果您的四边形相交或内部连接，那就更困难了。我会尝试分解那些相交的表面，然后找到所有可能的光滑表面，并选择内部体积最大的表面。
This might be hard to implement if your shape self intersects, but if you can find one quad that you know is on the surface (possibly one furthest away from the centroid) then map out concentric circles of quads around it. Then find a continuous ring of quads outside that and so on, until you end up at the "opposite" side. If your quads intersect, or are internally connected, then that's more difficult. I'd try breaking apart those which intersect, then find all the possible smooth surfaces, and pick the one with the greatest internal volume.
这个怎么样？
计算四边形的法线向量（称为“当前”四边形）。
对该向量和所有剩余的四边形进行相交测试。
如果它与向量的正部分中的另一个四边形相交，则您知道当前四边形是内部四边形。对所有剩余的四边形重复此操作。
这假设四边形“面”朝外。
How about this?
Calculate the normal vector of a quad (call this the 'current' quad).
Do an intersection test with that vector and all the remaining quads.
If it intersects another quad in the positive portion of the vector you know the current quad is an internal quad. Repeat for all the remaining quads.
This assumes the quads 'face' outward.
考虑所有的四边形都住在一个大的密封盒子里。选择一个四边形。进行光线追踪；将该四边形视为光源，并将所有其他四边形视为反射和模糊，其中击中四边形将从该表面向所有方向发送光，但不会在角落周围发送光。
如果在所有节点都有机会被击中后没有光线击中外部框，则将该四边形视为内部。
如果它是凸的，或者内部四边形不与外部四边形共享边，则有更简单的方法。
Consider that all of the quads live inside a large sealed box. Pick one quad. Do raytracing; treat that quad as a light source, and treat all other quads as reflective and fuzzy, where a hit to a quad will send light in all directions from that surface, but not around corners.
If no light rays hit the external box after all nodes have had a chance to be hit, treat that quad as internal.
If it's convex, or internal quads didn't share edges with external quads, there are easier ways.
如果形状是凸的，则可以很容易地完成。当形状是凹形时，就困难得多。
在凸情况下，通过计算所有点的平均值来找到质心。这给出了内部的一个点，该点具有以下属性：
这两个卷为您提供了一个决策过程来检查四边形是否位于边界上。如果来自另一个四边形的任何点出现在外部体积中，则该四边形不在边界上并且可以作为内部四边形被丢弃。
编辑：刚刚看到您上面的澄清。在更困难的情况下，形状是凹的，那么你需要以下两件事之一；
进一步编辑：刚刚意识到您所描述的将是点的凹壳。尝试查看此搜索页中的一些结果。
It can be done quite easily if the shape is convex. When the shape is concave it is much harder.
In the convex case find the centroid by computing the average of all of the points. This gives a point that is in the interior for which the following property holds:
These two volumes give you a decision process to check if a quad is on the boundary or not. If any point from another quad occurs in the outside volume then the quad is not on the boundary and can be discarded as an interior quad.
Edit: Just seen your clarification above. In the harder case that the shape is concave then you need one of two things;
Further edit: Just realised that what you are describing would be a concave hull for the points. Try looking at some of the results in this search page.
通过减少必须处理的四边形数量，您可以使问题变得更容易。
您知道某些四边形形成一个封闭的壳。因此，这些四边形在其边缘处连接。如果一个四边形的三个相互相邻的边（即，这些边形成闭环）与另一个四边形的边重叠，则这些四边形可能是壳的一部分（这些相互相邻的边充当 2D 区域的边界；让我们将该区域称为四边形的“连通面”）。列出这些“空壳候选人”的名单。现在，浏览此列表并丢弃具有不与另一个候选者重叠的边的任何候选者（即，该边与不在列表中的四边形的边重叠）。重复此剔除过程，直到您不再能够删除任何四边形。你留下的应该是你的外壳。创建一个“非壳四边形”列表，其中包含不在“壳”列表中的所有四边形。
围绕该壳绘制一个边界框（或球体、椭圆形等）。现在，查看非壳四边形列表，并丢弃位于边界区域外部的任何四边形。这些绝对不在室内。
取剩余的非壳四边形。这些可能位于也可能不在形状的内部。对于每个四边形，从每个面的中心绘制垂直于四边形的线，这些线终止于边界形状的表面。跟踪每条线并计算该线穿过 shell 列表中四边形的“连接面”的次数。如果该数字是奇数，则该顶点位于形状的内部。如果是偶数，则顶点在外部。您可以根据四边形的顶点是在内部还是在外部来确定它是在内部还是在外部。
You may be able to make your problem easier by reducing the number of quads that you have to deal with.
You know that some of the quads form a closed shell. Therefore, those quads are connected at their edges. If three mutually adjacent edges of a quad (that is, the edges form a closed loop) overlap the edge of another quad, then these quads might be part of the shell (these mutually adjacent edges serve as the boundary of a 2D region; let's call that region the "connected face" of the quad). Make a list of these "shell candidates". Now, look through this list and throw out any candidate who has an edge that does not overlap with another candidate (that is, the edge overlaps an edge of a quad that is not in the list). Repeat this culling process until you are no longer able to remove any quads. What you have left should be your shell. Create a "non-shell quads" list containing all of the quads not in the "shell" list.
Draw a bounding box (or sphere, ellipse, etc) around this shell. Now, look through your list of non-shell quads, and throw out any quads that lie outside of the bounding region. These are definitely not in the interior.
Take the remaining non-shell quads. These may or may not be in the interior of the shape. For each of these quads, draw lines perpendicular to the quad from the center of each face that end on the surface of the bounding shape. Trace each line and count how many times the line crosses through the "connected face" of a quad in your shell list. If this number is odd, then that vertex lies in the interior of the shape. If it is even, the vertex is on the exterior. You can determine whether a quad is inside or outside based on whether its vertices are inside or outside.