根据它们包围的 3D 区域将表面分配给区域 [英] Assigning surfaces to zones based on the 3D regions they enclose

问题描述

给定 3D 空间中的一组表面，我试图将每个表面分配给一个区域，该区域指的是该组所包含的最小 3D 区域，如果不适用，则不分配任何区域.我还想确定一个表面是否是两个区域之间的界面.因此，例如，如果我们有 11 个表面代表两个相互堆叠的立方体，则顶部立方体中的表面将在同一区域中，而底部中的表面将在不同区域中(界面表面为在两个区域).

举个例子，我想接收一组曲面，例如

我附上了一张图片，解释了如何使用半边结构来得到你想要的东西:假设你有一个由五个矩形组成的汤(它们组成一个没有顶部的立方体.你处理你的第一个矩形，比如 ABCD，这将创建你的第一个图形，比如说 G1.现在你处理第二个多边形，比如 FEHG，你还没有看到这些顶点，所以你创建第二个图形，G2.现在假设你处理多边形 CDGH.你以前见过这些顶点，所以您无需创建新图，而是合并(连接)共享这些节点的现有图.继续进行，直到处理完所有多边形.您会得到图中的图.

现在，查询图表以获取您的信息.遍历图形后，您将看到恰好有四个顶点(节点)缺少边.这些顶点对应于缺少的盒子顶部(图中的边缘是红色的).因此你知道这个图不是一个封闭的流形.如果你有另一个盒子，它没有与这个盒子共享节点，你会有另一个图.因此，在您处理完多边形后，每个图形对于您来说都是一个区域".

请注意，如果您有两个相交的形状，您也可以使用这些图形来跟踪它们，但它要复杂得多.基本上在处理一个新的多边形时，你不仅要查看它的任何顶点是否属于已经处理过的图形，还要查看这个多边形是否与之前处理过的任何多边形相交，如果是，分割这个多边形并将所有这些添加到相交图.

Given a set of surfaces in three-dimensional space, I am attempting to assign each surface to a zone referring to the smallest 3D region the set encloses, or no zone if this is not applicable. I also want to determine if a surface is an interface between two zones. So, for example, if we had 11 surfaces representing two cubes stacked on top of each other, the surfaces in the top cube would be in the same zone and the surfaces in the bottom would be in a different zone (with the interface surface being in both zones).

As an example, I want to take in a set of surfaces such as this and turn it in to this. Each color here represents a zone, with gray being no zone associated (as in the flap at the bottom).

I have done some searching around trying to find if someone has already come up with an algorithm to do this, but I have not found anything (most seem to identify regions rather than link surfaces to the region they enclose). As such I am trying to come up with my own algorithm and am wondering if there are any other alternatives or if my method would work.

I am assuming all surfaces are connected.

My idea is the following:

1. Select a random surface whose sides each touch exactly one other surface, and add this to zone 1.
2. Add each connected surface to zone 1 provided each of its sides touch exactly one other surface.
3. For those connected surfaces that touch more than one surface on at least one of its sides, add it to the "maybe" list.
4. For each new surface in zone 1, repeat steps 2-3.
5. Once a surface has been added to the "maybe" list twice, add it to zone 1 and remove from the "maybe" list. Mark this surface as a zone interface.
6. Add the zone interface to zone 2.
7. Select one random surface from the "maybe" list and assign it to zone 2 and clear the "maybe" list.
8. Repeat steps 2-7 (updating the zone number of course) until there are no surfaces that are unassigned.

This seems to work for simple scenarios (e.g., two cubes stacked on top of one another), but I am not sure if there are any tricky conditions I need to watch out for, or if it falls apart once there are more than two zones that share a side.

Any improvement on my rough algorithm/alternate ideas for implementation would be appreciated. Thanks!

EDIT: Here are some more details in response to some comments. A zone by my definition is simply a group of surfaces that completely bound a 3D region with no gaps. So if I had two cubes, A and B, that do not touch, I would have two zones: one consisting of all the surfaces of cube A and the other of all the surfaces for cube B. If I had a cube that was missing one side, there would be no zone associated with those surfaces.

My end goal is to make an automated process for grouping surfaces in a modeling tool I am creating. The specifics are classified, but essentially I am dealing with models where certain properties are common only between surfaces in the same "zone" as described above. I want to make an automated process that creates these zones so that the user can apply these properties to all surfaces in the zone at once instead of doing it manually.

Essentially the problem boils down to finding the smallest 3D regions that are completely enclosed by an arbitrary set of surfaces, and keeping track of which surfaces belong to which regions. I hope this makes my question more clear.

解决方案

What you are interested in, then, would be discovering closed surface (volume) mesh topology from a set of input polygons; in other words - polytopes. This is common to pretty much every 3d modeling package. I would guess that Blender has code that does that. There are different ways of doing this, commonly however, some version of half-edge graph is used. See wiki link here: Doubly Linked half edge graph. The idea is to walk your input polies, and build these graphs. Once done, you can easily query each graph to see if there are holes (edges missing, etc).

I attached a picture explaining how to use a half-edge structure to get what you want: Say you are given a soup of five rectangles (they make up a cube with out a top. U process your first rectangle say ABCD, this creates your first graph, say G1. Now you process second polygon, say FEHG, none of these vertices you have seen yet, so you create second graph, G2. Now say you process polygon CDGH. You have seen these vertices before, so instead of creating a new graph, you merge(connect) existing graphs that share these nodes. Proceed until you process all polygons. You get graph in picture.

Now, to query the graph to get your information. Once you walk the graph, you will see that there are exactly four vertices (nodes) that are missing edges. Those verts correspond to the missing top of the box (the edges are red in the illustration). Hence you know that this graph is not a closed manifold. If you had another box, that did not share nodes with this one, you would have another graph. So each graph, once you done processing your polygons, is a "zone" for you.

Note, if you have two say intersecting shapes, you can track those too using these graphs, but its much more complicated. Basically when processing a new polygon, you would not only have to see if any of its verts belong to already processed graphs, but also see if this polygon intersects any of the previously processed polygons, if so, split this polygon and add all this to the intersected graph.

这篇关于根据它们包围的 3D 区域将表面分配给区域的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！