六维知识的获取与应用.ppt

第六章 三维形状的形式化表示计算 形状表示 表面逼近与重建 网格的子划分与计算 曲面可视方向计算 6-1 形状表示 凸分析中的相关定义 点的仿射组合 质心坐标 计算几何中的三角形与网格 点的仿射组合 给定线性矢量空间R3的有限点集S＝{p1,p2,…,pm}，m＝|S|为集合S的大小，其仿射组合p定义为 点集的凸组合 如图6.1 点集的凸包 如图6.2 图6.1 点集的凸组合 图6.2 点集的凸包 质心坐标 如果定义点pi为 pi=O+vi,p0=O 定义c0为 c0=1-(c1+c2+…+cn) 那么p可以等价地写为 p=c0p0+c1p1+c2p2…+cnpn (1) 式中c0+c1+c2…+cn=1 在式(1)中，(c0,c1,c2，…，cn)称为点p相对于点集(p0,p1,p2,…,pn)的质 6-1-2 计算几何中的三角形与网格 点集拓扑的基本概念 在拓扑学中，一个表面意味着可嵌入R3空间的连通和可定向的2D流形，表面可能具有边界无边界的表面称作封闭表面 Delaunay三角化与Voronoi图 三角网格模型表示方法 Hoppe等采用分段线性三角网格表示方法给出了表面模型的拓扑分析 Delaunay三角化与Voronoi图 每个Voronoi区域是一个凸多面体(polyhedron)，S中所有点的Voronoi区域的集合定义了一种空间分区，被称作S的Voronoi图，记做V(S) Voronoi图把空间分区为一系列凸单元，基于Voronoi图可以建立有效的点定位数据结构 点集S的Delaunay三角化与其Voronoi图(Voronoi diagram)是拓扑对偶的 6-2 表面逼近与重建 点集形状的表达 表面重建方法 6-2-1 点集形状的表达 表面重建概念 表面表达模型 参数样条曲面 隐式曲面 多边形网格 细分曲面 可变形网格 表面重建概念 通常把正确地连接采样点以重建表面的问题称作表面重建(surface reconstruction) 关于可定向流形的概念是表面重建方法中研究模型拓扑的基础 表面重建的目的是找出物理表面形状的数字化描述，能够精确地逼近物理表面，并给出形式简洁的表达。其中一个关键的问题是点集的连接关系，即给定从2D流形上采样得到的离散点集，如何获得模型的拓扑 在各种拓扑重建方法的研究中，三维alpha形状是一个核心的概念 6-2-2 表面重建方法 目前，主要的重建方法大体上可划分为四个类别 表面重建中的关键技术问题 基于可变形网格的表面重构 表面重建技术发展趋势 近年来的一个主要趋势是，一些基于计算几何中几何结构的表面重构方法研究，进一步把计算拓扑方法引入非结构化三维点集数据形状重建中，寻求把几何结构与采样点的邻域微分结构或可变形连续表面结合起来，解决非均匀采样和任意拓扑形状的重建问题。 表面重建中的关键技术问题 有待解决的主要问题可以概括为： ①处理具有任意拓扑的表面；②允许非均匀的采样；③产生可证明的拓扑保证(guarantees)模型，如精确逼近实际表面的光滑流形。只有在充分采样的条件下，才能正确重建表面 建立拓扑连接关系是重建的关键 点序列的方向 如图6.3 切平面估计 采样点的自然邻居坐标 基于可变形网格的表面重构 在采用可变形网格模型进行表面重构的过程中，核心问题之一是如何把几何数据与拓扑信息结合起来，维护重构表面拓扑的一致性 基于可变形网格模型的表面重构方法一般应考虑下面两个关键问题：①首先建立采样点集的初始网格模型，并确定其内部和外部方向。 ②基于物理约束定义网格变形行为，动态维护网格上点的连接关系，保证网格的可定向性（Orientability）。 基于可变形网格进行模型重构的方法首先建立数据点的凸包，初始网格模型基于行为约束函数向数据点变形。算法实现一个迭代的变形、细分过程。主要步骤如图6.4 图6.3 点序列的方向 图6.4 基于可变形网格进行表面重构的框架 6-3 网格的子划分与计算 子划分曲面的性质 子划分曲面的绘制方法 6-3-1 子划分曲面的性质(1) 用多边形网格来描述曲面的方法避开了闭形数学表达，并且可以表达多种类型的曲面。由于它们基于均匀B样条曲线曲面的二分，这种曲面通常被称为子划分曲面 目前，子划分曲面及交互式图形学应用算法研究内容主要包括 内插子划分方法 逼近子划分方法 基于子划分算法的多分辨率表达方法 6-3-1 子划分曲面的性质(2) 子划分曲面具有下列性质 局部性质 连续性 仿射不变性 6-3-2 子划分曲面的绘制方法 静态均匀子划分方法 静态均匀子划分规则 如图6.