将列表/网格划分为子列表/子网格 [英] Seperate list / mesh into sub-lists / sub-meshes
问题描述
给出一个关于我拥有哪种类型的网格的想法:
想象一下一个乐高积木，顶部有四个旋钮.我读了一个包含整个砖块表面的STL文件.在确定了所有具有唯一坐标的节点(并将其下一个邻居保存在列表中)之后，我切掉了大部分积木，以便仅保留四个旋钮.不幸的是，这四个旋钮仍然在一个大列表中(一个用于节点，一个用于下一个邻居).如果我指定一个我知道属于该旋钮的节点，我想以最快的方式获得一个旋钮的所有节点.
我有一个(相对)大的List<cNode> nodes其中
I have a (relatively) big List<cNode> nodes where
class cNode
{
int nodeNumber;
cVector vector;
}
甚至更大(约14e6个条目)List<cNodeCoincidence> coincidences其中
and an even bigger (ca. 14e6 entries) List<cNodeCoincidence> coincidences where
class cNodeCoincidence
{
cNode node1;
cNode node2;
}
我的节点代表3D点，而我的巧合类似于以前由STL文件压缩而成的由三角形组成的网格.我知道一个事实(用户相应地进行了输入)，我的节点网格实际上是一个节点/巧合列表中的4个单独的网格.我的目标是将每个子网格的节点提取到其自己的节点列表中.为此，我从每个子网格的一个节点开始，我知道它是所述子网格的一部分.提示一个递归函数:
My nodes represent points in 3D and my coincidences resembles what was formerly a mesh consisting of triangles, condensed from a STL file. I know for a fact (and the user made his input accordingly), that my node-mesh is actually 4 seperate meshes in one node/coincidence list. My goal is to extract the nodes of each sub-mesh to its own nodelist. To achieve this, I start with one node for each sub-mesh, which I know to be part of said sub-mesh. Cue a recursive function:
private void AssembleSubMesh(ReadOnlyCollection<cNode> in_nodesToRead, List<cNode> in_nodesAlreadyRead)
{
List<cNode> newNodesToRead = new List<cNode>();
List<cNodeCoincidence> foundCoincidences = coincidences.Where(x => (in_nodesToRead.Any(y => y == x.node1)) || in_nodesToRead.Any(z => z == x.node2)).ToList();
in_nodesAlreadyRead.AddRange(in_nodesToRead);
List<cNode> allRemainingNodes = new List<cNode>();
foreach (cNodeCoincidence nc in foundCoincidences)
{
allRemainingNodes.Add(nc.node1);
allRemainingNodes.Add(nc.node2);
}
allRemainingNodes = allRemainingNodes.Distinct().ToList();
allRemainingNodes.RemoveAll(x => in_nodesAlreadyRead.Contains(x));
if (allRemainingNodes.Count != 0)
AssembleSubMesh(new ReadOnlyCollection<cNode>(allRemainingNodes), in_nodesAlreadyRead);
}
，它被AssembleSubMesh(new ReadOnlyCollection<cNode>(firstNodeIKnow), globalResultListForSubmesh);调用，从而将递归的结果写到一个更全局的列表中.
which is called by: AssembleSubMesh(new ReadOnlyCollection<cNode>(firstNodeIKnow), globalResultListForSubmesh); thus writing the results of the recursion to a more global list.
此过程可以工作(使用小网格物体进行测试)，但是非常缓慢(在我中止该过程之前的15个小时之内).
This procedure works (tested with small mesh), but is painfully slow (over 15 hours before I aborted the process).
有没有办法以更快，更优雅的方式分离网格?
我找到了这篇SO帖子，并查看了
I found this SO post and had a look at this lecture and it seems, that there might be a chance that this (especially WQUPC) is what I need, but I don't understand how exactly it could help, because they only have a node list and I additionally have the coincidence list which would be a shame not to use, really (?).
数据库能帮上忙吗(由于建立索引)?
Could a database help (because of indexing)?
推荐答案
您需要能够识别 edge .这是2个顶点之间的单个连接(找不到更多其他连接).我假设所有三角形都有所有顶点，因此它们是重复的.当然，这取决于网格的尺寸，但是不应该花费太多时间.
You need to be able to identify edge. which is a a single connection between 2 vertices (no more other connections found). I assume that there are all vertices for all triangles, so they are duplicated. It depends on the dimension of your mesh sure, but it shouldn't take so much time.
您需要定义字典，这将增加应用程序的内存，但是在保证O(1)访问的情况下，也将大大提高速度.
You need to define dictionaries, which will pump your app's memory, but will also dramatically increase speed with guaranteed O(1) access.
简而言之:
1)加载数据
2)对其进行扫描并构建适当的数据结构 如果您观察到任何CAD建模软件，则花费的时间要比加载网格时花费的时间多得多，这是出于相同的原因:他们需要扫描加载的数据并构建适当的数据结构，以便能够尽可能快地处理该数据.
2) scan it and construct appropriate data structures If you observe any CAD modelling software it takes much more time then it should during loading of meshes, for the same reason: they need to scan data loaded and construct appropriate data structures to be able to process that data after as fast as it possible.
3)使用这些数据结构来尽可能快地获取您所需的信息.
3) use those data structures to get information you need as fast as it possible.
因此，明智地选择数据结构和键，以满足您的应用程序的需求.
So choose data structures and keys wisely, to meet requirements of your application.
这篇关于将列表/网格划分为子列表/子网格的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
