三维网格模型的处理技术研究进展-唐杰2005.ppt

三维网格模型的处理技术研究进展 唐杰2005年11月 Content 什么是三维网格模型三维网格模型的应用三维网格模型的处理技术三维网格模型研究的相关资源 什么是三维网格模型 三维网格模型的定义 三角网格模型的描述 三角片只能在其边上与其它三角片相交每条内部边只能有两个相邻三角片边界边只能有一个相邻三角片三角网格模型的定义 三角网格模型M定义为一个二元组 即M K V 其中 V v1 vm vi R3 表示网格M的顶点在三维空间中的位置 K为表征网格拓扑结构的单纯复形 一个单纯复形包含一组单形 其中 1 m 称为顶点 i j 等称为边 i j k 称为面 网格的类型 StructuredorUnstructuredRegularorIrregularManifoldorNonmanifold 网格模型的邻接关系 三维模型的优点 三角网格模型的描述较为简单相关基础算法较简单 成熟可做到硬件加速描述自由曲面的能力强有体积信息 三维模型的缺点 模型通常较大 不易存储 传输 浏览模型具有固定分辨率定义在二维流形上 传统的数字信号处理技术不易直接应用 DigitalMichelangeloproject20亿个三角片 7000幅彩色照片 三维网格模型的应用 计算机辅助设计和制造 三维传真科学计算可视化 有限元分析虚拟现实 虚拟装配 飞行模拟数字博物馆 数字图书馆娱乐业 游戏 电影医疗 远程手术 培训 下一代数字媒体 三维网格模型的处理技术 研究热点问题 SIGGRAPHwww siggraph org连续三年 每年3个有关mesh的sessionEUROGRAPHwww eg orgPACIFICGRAPH 三维网格模型处理技术的食物链 基本算法网格模型的获取网格模型的表示网格模型的编辑网格模型的传输网格模型的展示 网格模型的数据结构 分类 简单法WingededgeHalfedge 要求 方便地进行邻接关系查询 简单法 vertices 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 Faces 124578156348 structSM face SM vert vert 3 structSM edge SM vert vert 2 SM face face 2 structSM vert floatcoord 3 SM face nbFace SM edge nbEdge structSM mesh SM vert vert SM face face SM edge edge 例如Garland的qslim等 简单法的缺点 邻接关系的检索很困难邻接点的检索 边的邻接三角片的检索 voidGetVertexStar CVertex pVertex CVertex arrPVertex CTriangle arrTriangle pVertex GetNeighborTriangles for inti 0 iGetVertex j SetMark 0 pVertex SetMark 1 for i 0 iGetVertex j GetMark arrPVertex Add arrTriangle i GetVertex j arrTriangle i GetVertex j SetMark byte 1 WingedEdge structwe structwe l next structwe l prev structwe r next structwe r prev structvert st vert structvert end vert structface l f structface r f structvert structwe rep floatcoord 3 structface structwe rep WingedEdge的不足 邻接关系的查询关于边的查询为常值其它查询仍然较复杂孔洞的处理 HalfEdge structHE edge HE vert vert HE edge pair HE face face HE edge next structHE vert floatx floaty floatz HE edge edge structHE face HE edge edge 邻接关系的查询 边edge的端点和邻接三角片查询 HE vert vert1 edge vert HE vert vert2 edge pair vert HE face face1 edge face HE face face2 edge pair face 三角片face的三条边 HE edge edge face edge do edge edge next while edge face edge 点vert的邻接边 HE edge edge vert edge do edge edge pair next while edge vert edge 进一步的研究方向 非结构化的网格模型描述非流形网格模型的描述三维流形网格模型的描述 网格模型的离散曲率 基本概念 曲率用来衡量曲面在某一点处的弯曲程度高斯曲率K Gaussiancurvature 平均曲率H meancurvature 用于分割 光顺等 式中E G F 是曲面的第一类基本量 L M N是曲面第二类基本量 曲率计算的直接法 高斯曲率 其中 i为三角片在该顶点处内角的度数 Ai为三角片的面积 n为网格模型中包含该顶点的三角片的个数减1 平均曲率 其中 n为该点法矢 A为三角片面积和 N1 i 为点vi的一阶邻接点集 j和 j分别是边vivj所对应的角 Taubin法 网格上某点P的方向曲率 构建矩阵 计算曲率 曲率计算的拟合法 拟合法 用最小平方法 以高次曲面 大于2次 对网格模型上某顶点周围的局部区域 二阶邻域以上 进行拟合 并以该顶点处的曲率作为近似曲率 参数曲面拟合隐函数曲面拟合 算法概述 确定C1不连续的边拟合点的选取及参数化NURBS曲面拟合曲率计算 确定C1不连续的边 定义 c s 两边的曲面沿c s 的一阶偏导矢不连续 缺点 在C1不连续的边附近的拟合曲面不能很好反映曲面实际情况 解决 标注所有C1不连续的边 限制拟合点不跨越C1不连续的边 拟合点的选取及参数化 拟合点的要求 能反映网格模型在该点处的实际形状不能跨越网格模型上的C1不连续界限不能小于9个 拟合点的参数化投影到切平面旋转到XOY平面包围盒调整比例变换 曲面拟合与曲率计算 曲面拟合 曲率计算 其中 R为顶点向量 n维 M为n 9的矩阵 与B样条基函数值有关 其中 E G F 是曲面的第一类基本量 L M N是曲面第二类基本量 实验结果 网格模型的测地线距离计算 定义 定义 曲面上一条曲线是测地线 当且仅当它是直线 或者它的主法向量处处是曲面的法向量 如同平面上两点之间直线距离最短一样 曲面上两点之间测地线距离最短 分类 精确计算法时间复杂度为O n2 或O nlog2n 近似计算法计算速度较快 虚拟起点 测地线距离计算 构造虚拟起点 交点的三种情况 初始化 初始化步骤 将网格模型所有点分为三类 即 测地线已知点邻近点 一个按测地线距离的从小到大排序的堆 未知点 测地线计算 计算过程 在初始化步骤的基础上由近至远的计算所有点的测地线距离 直至计算到vj或邻近点集为空 实验结果 任意网格模型相似度评估 目标与应用 目标 对两个任意网格模型的相似程度进行判定和评估 即建立一个映射E M M R 而E M M 能够量化地评估M与M 之间的相似程度 E M M 越小 表明M与M 越相似 应用 简化网格模型与原始网格模型之间误差的评估网格模型的搜索匹配网格模型的识别等 几何相似度 网格模型的几何相似性 空间一点x到网格模型M的距离dE定义为 网格M到M 的单向Hausdorff距离ds定义为 网格M0到M的对称Hausdorff距离dH定义为 外观相似度 网格模型的外观相似性评估 其中 Ij为M上第j个采样点处的RGB向量 I j为M 上距离采样点j最近的点处的RGB向量 Ij I j 为向量Ij与I j之间的欧氏距离 n为采样点的个数 算法 输入三角网格模型M和M 在M上抽取采样点集S 对每个vi S 计算其到M 的最小距离di 则M到M 单向Hausdorff距离为max di 类似地 计算M 到M的单向Hausdorff距离 点到三角片的距离 平均单元格 平均单元格法首先确定M和M 的外接包围盒的范围 长方体包围盒划分成l m n个小立方体栅格若某三角片与一个单元格相交 则将该三角片分配给该单元格单元格的大小 单元格的大小决定了每个单元格中三角片的数量 几何相似度结果 0 014389 0 1 0 0 1 732 0 外观相似度结果 网格模型的获取 分类 正向方法三角化 triangulation 从解析曲面 参数曲面等生成网格模型反向方法网格重构 reconstruction 从已有的真实模型重建网格模型从照片等重建网格模型 散乱点集重构网格模型 工具 测量现场 测量结果 Pointscloud Mesh Hoppe smethod切平面确定切平面方向调整有向距离计算网格生成 MarchingCubes 结果 网格模型的多分辨分析 网格模型的缺点 网格通常较大固定分辨率 相关工作 网格简化层次细节模型递进网格多分辨模型 多分辨分析的分类 细分法网格简化 vi vj 拆分点 删除边 算法概述 本文算法具有以下优点 可以通过全局最大简化误差或三角片数目来控制简化的进程 严格控制简化过程中的连通性变化 确保简化网格模型拓扑的正确性 在简化过程中利用体积优化法确定新顶点的位置 较好地保持了初始网格模型的体积特征 采样 难点网格模型定义在二维流形上复杂的连通性 connectivity 信息不易均匀采样分类子分连通性方法网格简化方法删除边法 采样步骤 初始向下采样步骤选择待删除边选择采样点计算删除每条待删除边所产生的简化误差连续性检查对所有待删除边按其简化误差从低到高排序 并将其放入一个堆中重复以下操作直至停止条件满足取出堆中简化误差最小的边在网格模型中删除此边及其相邻的三角片重新分配采样点更新所有受影响的待删除边的信息 并在堆中重新排序 采样点的选取 采样点的选取目的用于计算简化误差选取方法所有初始顶点尖锐边的中点分配至三角片 确定删除后新顶点位置 v vi vj 1 1 确定删除后新顶点位置 vi vj v 2 2 确定删除后新顶点位置 v vi v vj 3 3 确定删除后新顶点位置 v vi vj 4 4 确定删除后新顶点位置 v vi vj 5 5 确定删除后新顶点位置 v vi vj v vi vj 6 6 确定删除后新顶点位置 v vi vj v vi vj 7 7 确定删除后新顶点位置 v vi vj v vi vj 8 8 确定删除后新顶点位置 v vi vj v vi vj 8 8 v vi vj 1 2 3 4 5 6 7 8 1 2 3 4 5 6 7 8 确定删除后新顶点位置 计算新定点位置 对于每个四面体有 所有四面体的体积平方和为 为使f v 值达到最小 如果矩阵A奇异 没有逆矩阵 则采用子集法确定目标点的位置 计算删除误差 记Vs为受影响区域所有采样点的集合 T为删除边后受影响区域的三角片的集合 则删除误差为 其它 连续性检查 病态三角片检查 实验结果 8000040000200001000050002500 多分辨模型 各修改操作之间的关系 增大网格模型分辨率时 m5 m4 m3 m2 m1减小网格模型分辨率时 m1 m2 m3 m4 m5 实验结果 网格光顺 基本概念 光顺定义 光顺应用去噪有光顺性要求的设计 考虑的问题 体积收缩特征保持噪声与高频信号的区分几何光顺与参数域光顺 光顺算法分类 1 其中 0 1 其中 L为Laplace算子 为比例引子 p q为由用户指定的系数 Laplace及其改进法 优化法 其中 H为平均曲率 K为Gaussian曲率 a b为用户指定的系数 光顺算法分类 2 Jones在SIGGRAPH2003 其中 q为一个三角片 S为点vi周围三角片集 aq为三角片q的面积 q vi 为点vi在q所在平面上的投影 cq为三角片q的质心 f为空间权函数 g为影响权函数 都采用Gaussian函数 Bilateralfiltering 改进的BMD算法 邻居点选取算法的改进偏移量计算的改进 增加法矢惩罚函数 实验结果 保特征性 a b c d e g f h 实验结果 续 网格水印 概述 定义 在不影响使用的情况下 在载体作品中不可感知地嵌入一些特殊信息 目的 版权保护要求 抵御各种攻击仿射变换RemeshingReindexing简化光顺加噪声不影响模型正常使用 需注意的问题 加载空间网格模型会受到许多严厉的攻击 例如裁剪 简化等 如果将水印直接加在网格模型的某个固定分辨率上 当网格模型遇简化攻击时 易造成水印丢失 误差控制当模型面向工程应用时 加载水印引起的误差应控制在用户制定范围内 有意义水印信息应有意义 加载流程 原始网格M0 水印字串str 加载空间 水印长度字串长度s 加载点的分布表示同一个比特信息的r个顶点分布应尽量均匀以抵抗裁剪 简化等操作的攻击 通过多分辨模型实现 误差控制计算该顶点的一阶邻接三角片上的采样点到初始网格模型的距离 放弃或调低水印强度 加载算法 其中 vi为网格模型中第i个顶点 v i为加载水印后的顶点wj为水印信息中的一位信息 wj 0 1 f wi 为符号函数 为水印强度 目的是方便用户控制水印强度 li表示网格模型中第i个顶点的1阶邻接边中最短边的长度 水印加载算法 水印比对文件水印比特流的长度 水印加载顶点数和顶点分布 提取流程 原始网格M0 水印网格Mw 水印比对文件 提取算法 其中 wik为第i个比特中第k个顶点所表示的信息 vj和vj 分别为加载wik的初始网格模型顶点和水印网格顶点 nj为对应的初始网格该顶点法矢 提取wik 确定wi 相关度计算 基于内容的三维模型检索 概述 动机世界从2D转为3D基于文本的3D检索什么样的模型是相似的 Gunnestimatesthat only20 ofthepartsinitiallythoug