标签: mesh

假设您有一个3维对象,以某种常见文件格式表示为3d网格.你将如何设计一种算法将网格分解为一个或多个2d'网' - 也就是说,可以剪切和折叠以创建原始3d对象的二维表示.

除此之外,该算法还需要考虑:

• 对任何给定对象进行多次可能的分解
• 处理将网格装配到固定尺寸的画布(纸张).
• 识别网中的两个面板何时重叠(因此无效).
• 由于重叠或页面大小限制,如果网格无法表示为单个网格,则将网格分成多个网络.
• 在适当的位置生成制表符,用于附加相邻的面.

明显的退化情况就是每面创建一个网,边缘有一半.这显然不是理想的:理想的情况是单个连续网.复杂形状的现实很可能在中间.

我意识到找到最佳网络(最少网络/最少页面)可能计算成本很高,但是找到"足够好"的网络的良好启发式就足够了.

介绍

作为一个更大的程序(与渲染体积图形相关)的一部分,我有一个小而棘手的子问题,其中任意(但有限)三角形2D网格需要以特定方式进行标记.我刚刚写了一个解决方案(见下文),它对我当时的测试网格来说已经足够好了,尽管我意识到这种方法对于人们可以想到的每个可能的网格都可能不会很好.现在我终于遇到了一个网格,目前的解决方案根本不能很好地执行 - 看起来我应该想出一种完全不同的方法.不幸的是,我似乎无法重置我的思路,这就是为什么我以为我会问这里.

问题

请看下面的图片.(颜色不是问题的一部分;我只是添加它们来改进(？)可视化.而且变化的边缘宽度是一个完全不相关的工件.)

对于每个三角形(例如,橙色ABC和绿色ABD),三个边缘中的每一个都需要被给予两个标签中的一个,例如"0"或"1".只有两个要求:

1. 并非三角形的所有边都可以具有相同的标签.换句话说,对于每个三角形,必须有两个"0"和一个"1",或两个"1"和一个"0".
2. 如果边缘由两个三角形共享,则它们必须具有相同的标签.换句话说,如果图像中的边缘AB对于三角形ABC标记为"0",则对于ABD也必须标记为"0".

网格是真正的2D网格,它是有限的:即,它不包裹,并且它具有明确定义的外边界.显然,在边界上很容易满足要求 - 但内部变得更加困难.

直观地说,看起来至少应该存在一个解决方案,即使我无法证明它.(通常有几个 - 其中任何一个都足够了.)

当前解决方案

我目前的解决方案是一个非常强力的解决方案(此处仅为完整性而提供 - 可以跳过此部分):

• 保持四组三角形 - 每个可能的计数(0..3)一个剩余的标记.在开始时,每个三角形都在集合中,其中三个边缘仍然被标记.
• 只要存在具有非标记边的三角形:
  找到仍然存在三角形的最小非零数量的未分配边.换句话说:在任何给定时间,我们都会尽量减少标签已部分完成的三角形数量.剩余的边数将是1到3之间的任何值.然后,只需选择一个这样的三角形,剩下要分配的特定边数.对于此三角形,请执行以下操作:
  • 查看是否已经通过标记其他三角形来标记任何剩余边缘.如果是,请按上述要求#2暗示的标签进行分配.
  • 如果这导致死胡同(即,当前三角形不能满足要求#1),那么从一开始就重新开始整个过程.
  • 分配任何剩余边缘如下:
    • 如果到目前为止没有标记边,则随机分配第一个边.
    • 当已经分配了一个边缘时,分配第二个边缘以使其具有相反的标签.
    • 分配两条边时:如果它们具有相同的标签,则指定第三条标签具有相反的标签(显然); 如果两者有不同的标签,则随机分配第三个标签.
  • 更新未分配边数的不同计数的三角形集.
• 如果我们到达这里,那么我们有一个解决方案 - 万岁!

通常这种方法发现只是一对夫妇的迭代内的解决方案,但最近我遇到了该算法趋于结束后,才一两个网上千重试......这显然表明,有可能的网格,它永远不会结束.

现在,我希望有一个确定性的算法,保证总能找到解决方案.计算复杂性不是一个大问题,因为网格不是很大,并且标签基本上只需要在加载新网格时完成,这不会一直发生 - 所以一个算法(例如)指数复杂性应该没问题,只要它有效.(但当然:效率越高越好.)

感谢您阅读此内容.现在,任何帮助将不胜感激!

编辑:基于建议的解决方案的结果

不幸的是,我无法让Dialecticus建议的方法起作用.也许我没弄错......无论如何,考虑以下网格,起点由绿点表示: 让我们放大一点...... 现在,让我们开始算法.在第一步之后,标签看起来像这样(红色="星号路径",蓝色="环形路径"): 到现在为止还挺好.第二步之后: 第三个: ......第四名: 但是现在我们遇到了问题!让我们再做一轮 - 但请注意以洋红色绘制的三角形: 根据我目前的实现,洋红三角的所有边缘都在环形路径上,所以它们应该是蓝色的 - 这实际上是一个反例.现在也许我以某种方式弄错了......但无论如何,最接近起始节点的两条边显然不能是红色; 如果第三个标记为红色,那么似乎解决方案不再符合这个想法.

顺便说一下,这是使用的数据.每行代表一条边,列的解释如下:

1. 第一个节点的索引
2. 第二个节点的索引
3. 第一个节点的x坐标
4. 第一个节点的y坐标
5. 第二个节点的x …

我正在开发用户在运行时生成网格的游戏(所有时间),因此网格有很多顶点,同时有一个GameObject - 玩家需要在运行时网格中生成的区域中触发事件.

这个游戏中的相机是3D,但这个生成的网格是平的.在我附图中,我在顶视图中显示了这一点,以便更好地展示它的外观.

现在我每隔几秒就更新一次Mesh Collider,但是在生成的网格有越来越多的顶点之后,它会非常慢.

我相信这是一个非常简单的碰撞方法,所以也许还有其他任何方法来检测这个,而不是附加到动态生成网格的网格对撞机？

更新#1

我知道Mesh Collider非常慢,不应该在运行时更新.我也知道应该使用像盒子对撞机这样的原语.

但是在这种情况下,当这个平面网格每秒更新一次(并且它会增长)时,它将成千上万的盒子对撞机,并且每秒都需要添加新的.这种方法也行不通.

更新#2

我的第二个想法是为玩家找到最近的三角形并为它们创建碰撞器(盒子碰撞器应该是最快的).但我真的不知道从哪里开始,甚至可能？有人吗？

什么是用于确定点是否在3D网格内的快速算法？为简单起见,您可以假设网格是所有三角形并且没有孔.

到目前为止我所知道的是,确定光线是否穿过网格的一种流行方法是计算光线/三角形交叉点的数量.它必须很快,因为我将它用于触觉医疗模拟.所以我无法测试光线交叉的所有三角形.我需要某种散列或树数据结构来存储三角形,以帮助确定哪个三角形是相关的.

另外,我知道如果我对顶点进行任意2D投影,则需要进行简单的点/三角交点测试.但是,我仍然需要知道哪些三角形是相关的,此外,哪些三角形位于该点的前面并且仅测试这些三角形.

切片3D网格的正确方法是什么？网格都是闭合曲面,切片需要是网格内部的二进制图像.因此,例如,表示球体和切片图像的网格是实心圆的网格.

我正在寻找一个可以集成到我当前的C++项目中的软件库或算法.

我想在运行时使网格的一部分不可见.我可以将这些部件设置为不可见/透明,例如通过更改单个面的属性吗？网格本身仅使用一种材质.

示例性说明作为编辑理解这个问题:设想一个目(这里为20个顶点的几何形状),其中的四个顶点每个四边形积聚一个Face4.现在,网格的某些部分应该是不可见的(这里两个面是不可见的).

我想在OpenGL中为一个模型(例如人类,行走)制作动画.我知道有像骨架动画这样的东西(有狡猾的数学),但是这个......

1. 在Blender中创建一个模型
2. 在Blender中为该模型创建骨架
3. 现在使用该模型和骨架在Blender中进行步行动画
4. 获取该动画的一些"keyFrames"并将每个"keyFrame"导出为单个模型(例如作为obj文件)
5. 为OpenGL创建一个OBJ文件加载器(获取顶点,纹理,法线和面数据)
6. 使用VBO在OpenGL中绘制动画模型(并获得一些棘手的想法如何在VBO中更改当前的"keyFrame"/模型...也许与 glMapBufferRange

好的,我知道这个想法只是一个小脚本,但值得进一步研究吗？改变VBO中的"keyFrame"/模型有什么好主意？

我知道记忆问题,但是我认为可以用小型号(而不是太多的动画)来完成.

是否可以在同一对象上显示对象的线框以及其面的纯色？我找到了一种方法,使用对象的克隆并分配不同的材料,例如

var geometry = new THREE.PlaneGeometry(plane.width, plane.height,width - 1, height - 1);
var materialWireframe = new THREE.MeshPhongMaterial({color:"red",wireframe:true});
var materialSolid = new THREE.MeshPhongMaterial({color:"green",wireframe:false});
var plane = new THREE.Mesh(geometry, materialWireframe );
var plane1 = plane.clone();
plane1.material = materialSolid ;
plane1.material.needsUpdate = true;

有什么想法吗？

我已经尝试在Google上搜索几种不同的内容.似乎我找不到任何东西.以为我不妨将问题上传到Stack Overflow.

谢谢!

我正在尝试从网格中生成点云数据,例如Maya的(.obj)文件.但是,我只能找到相反的情况,在互联网上点云点.有没有办法使用MeshLab或Maya等3D工具创建"网格点云数据"？(我更喜欢使用MeshLab)

谢谢.:)