按边缘循环分割3D模型
-
21-12-2019 - |
题
我有一个3D模型,表示这样的东西:
class Vertex
{
double x, y, z;
}
class Edge
{
Vertex *v1, *v2; // no particular order
Face *f1, *f2; // no particular order. f2 may be null.
}
class Face
{
List<Vertex*> vertices; // clockwise order
List<Edge*> edges; // clockwise order
}
class Model
{
List<Face*> faces;
List<Vertex*> vertices;
List<Edge*> edges;
}
当然,这可以转化为任何最方便的表示。
我想将这个模型分割成几个断开的部分,沿着多个连接边的循环,并创建新的面来复盖两端。一个循环的例子:
新面孔应该在相同的位置,并且除了与其他面孔的连接之外相同,但是对于这个例子,我已经将它们分开了。我怎么能这样做?
如果顶点在其他断开的部分之间共享并不重要。
由于每条边恰好连接两个面,因此我尝试将每条边单独拆分为两个副本(每个面一个)。这确实根据需要分离模型,但随后我看不到正确添加新面孔的方法。
这个问题被标记为图算法,因为这个问题似乎与图论有关。
解决方案
- 修复你的模型。
class Edge
应该持有指向Face
和Vertex
而不是价值观。 - 你想用某种
set
而不是List
在你的class Model
.这有助于查找和删除内容,并且您确保没有重复项。
- 拿出你的函数的原型。我建议
pair<Model*, Model*> split_model( const Model* mx, const List<Edge*>& loop );
- 创建两个新的空模型,比如说
ma
和mb
.添加边缘从loop
给他们每个人。 - 从
loop
.让我们称附在它上面的两张脸fa
和fb
. - 添加
fa
到模型ma
.从fa
, ,通过遵循附加到的所有边进行完整的图搜索fa
, ,以及附着在那些边缘上的所有面,等等。必须遵循遇到的所有面和边并将其添加到模型中ma
.如果遇到已经是ma
你不遵循他们。特别是当你遇到一个属于loop
所以你永远不会越过边界。这样你就可以对一侧的所有边和面进行完整的搜索,最终得到一个完整的模型ma
.最后你添加一个代表切割的脸。顶点可以在这里大部分被忽略,但当然最后你可能想添加属于你添加的面的所有顶点。 - 从脸部开始重复此步骤
fb
创建模型mb
代表另一部分。
不隶属于 StackOverflow