基于它们包围的三维区域分配表面区域 [英] Assigning surfaces to zones based on the 3D regions they enclose

问题描述

鉴于三维空间中一组的表面，我试图每个表面分配到区域参照最小三维区域设定包围，或没有区，如果这是不适用的。我还希望确定一个表面是两个区域之间的界面。因此，例如，如果我们有11表面重新presenting堆叠在彼此的顶部两个立方体，在顶部立方体表面将是相同的区域和底部的表面将是在一个不同的区域（带接口表面两个区域是）。

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).

作为一个例子，我想在一组曲面，如这，并把它到< A HREF =htt​​p://imgur.com/2ubdxUq相对=nofollow>这个。这里每一种颜色重新presents的区域，以灰色为无（在底部的皮瓣）相关联的区域。

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.

我的想法是这样的：

1. 选择一个随机的表面，其边每个触摸只有一个其它表面，并添加此1区。
2. 将每个连接面1区提供的每个两侧的触摸正好一个其它表面。
3. 对于那些连接的表面，触摸多个表面在其侧面的至少一个，将其添加到说不定之列。
4. 用于1区的每一个新的表面，重复步骤2-3。
5. 一旦表面已经被添加到了也许列表两次，将它添加到1区和从可能列表中删除。标记此表面作为区段接口。
6. 添加区段接口2区。
7. 从可能列表中选择一个随机的表面并指定为2区并清除说不定之列。
8. 在重复步骤2-7（更新课程的防区编号），直到没有表面是未分配。

这似乎工作（堆叠在另一个之上，例如，两个立方体）简单的场景，但我不知道是否有我需要提防任何棘手的情况，或者如果它分崩离析，一旦有更多的共享一个侧比两个区域

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.

这是我的粗略算法/备用思路任何改进的实施将AP preciated。谢谢！

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

编辑：这是在回应一些评论一些更多的细节。 由我定义一个区域就是一组表面是完全绑定一个三维区域而没有间隙。所以，如果我有两个立方体，A和B，不碰，我想有两个区域：一个由立方体的所有表面和其他所有表面的立方体B.如果我有是缺少一个立方体一侧上，就没有与这些表面有关区

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.

推荐答案

您有兴趣的话，会发现封闭面（卷）网从一组输入多边形的拓扑结构是什么;换句话说 - 多面体。这是常见的pretty的多少每个3D建模软件包。我猜想，搅拌机有code，它做到这一点。这样做有不同的方式，通常然而，一些版本半边图形的被使用。看到这里的wiki链接：双向链表半边缘图表。这样做是为了走你的输入polies，并建立这些图。一旦这样做，你可以很容易地查询每个图表看是否有孔（边缘缺失等）。

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).

我附上图片说明如何使用半边结构，以得到你想要的东西：说给你一个汤五个矩形（他们做了了顶部的立方体ü处理您的第一个矩形说ABCD。这将创建你的第一个图，说G1。现在你处理第二个多边形，说FEHG，没有这些顶点你见过的，所以您将创建第二个图形，G2，现在说你处理多边形CDGH。你以前见过这些顶点，所以而不是创建一个新的图，你合并（连接），共享这些节点现有的图形。继续，直到你处理所有的多边形。你的图片得到图表。

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.

请注意，如果您有两个说的交叉形状，你可以跟踪那些使用过这些图，但它的复杂得多。基本上，处理新的多边形的时候，你不仅必须看到，如果任其绿党属于已经处理过的图，但也看到，如果这面相交的任何的$ P $的pviously处理的多边形，如果是的话，拆分这个多边形，并添加这对相交的图表中的所有。

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.

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