《现代计算机图形学基础》课件 chap3-几何建模；chap4-数字几何处理

计算机图形学第三章几何建模供《现代计算机图形学基础》配套使用1提纲基本概念自由曲线曲面建模细分曲面建模三维重建数据结构21.1几何建模计算机图形学中，几何建模主要是指建立二维/三维几何形状的数学形式及数据结构表示。3Beziercurve扫描数据NURBS网格点云1.1几何建模几何建模是CAD/CAM等的核心，通常也是图形处理（绘制、交互等）的首要步骤。4CAD/CAM模型绘制模型交互1.2数学基础1.2.1几何形状数学形式显式表达隐式表达参数表达5

?隐式表达显式表达参数表达代数形式（非参数形式）1.2数学基础1.2.1几何形状数学形式显式表达因变量随自变量而变化的函数形式6平面直线

表达形式二维曲线三维曲面

1.2数学基础1.2.1几何形状数学形式隐式表达多个变量共同定义的函数形式7表达形式二维曲线三维曲面

圆

环面1.2数学基础1.2.1几何形状数学形式参数表达采用若干独立变量的显示表达式组成的集合8表达形式二维曲线三维曲面圆环面

1.2数学基础1.2.1几何形状数学形式参数表达优点具有直观的解释曲线：点p(u)形成的轨迹曲面：点p(u,v)充满的集合91.2数学基础1.2.1几何形状数学形式参数表达优点具有直观的解释:点p(u)或者p(u,v)的轨迹可以写成u或者(u,v)的形式。方便微积分等运算10p

1.2数学基础1.2.2常见几何性质-曲线长度、曲率、挠率11长度曲率挠率1.2数学基础1.2.2常见几何性质-曲线长度、曲率、挠率12P是平面曲线当且仅当P是直线当且仅当1.2数学基础1.2.2常见几何性质-曲面法向、法曲率、主曲率、高斯曲率13法向主曲率法曲率1.3建模类型建模对象自然物体建模人造物体建模建模方式插值（interpolation）拟合（fitting）14型值点插值拟合提纲基本概念自由曲线/曲面建模细分曲面建模三维重建数据结构152.1多项式曲线2.1.1平面三次多项式曲线通过三次多项式插值或拟合给定的型值点集合曲线的参数表达16控制顶点2.1多项式曲线2.1.1平面三次多项式曲线给定4个型值点计算插值曲线17Givenfourdatapoints2.1多项式曲线2.1.1平面三次多项式曲线给定多于4个型值点计算拟合曲线18Givenmorethanfourdatapoints2.1多项式曲线2.1.2平面三次Hermite曲线给定两个型值点及其一阶导数计算插值曲线曲线的参数表达19GivenvaluesandderivativesoftwodatapointsHermite基函数2.1多项式曲线2.1.2平面三次Hermite曲线给定两个型值点及其一阶导数计算插值曲线曲线的参数表达20Givenvaluesandderivativesoftwodatapoints2.2Bezier曲线/曲面2.2.1Bezier曲线多项式曲线，但具有更直观的几何表达式方便外形设计21What’stheshape?Bernstein基函数控制多边形2.2Bezier曲线/曲面2.2.1Bezier曲线历史Bezier曲线于1960年，由法国工程师皮埃尔·贝塞尔（PierreBézier）在汽车外形设计时所采用最早由PauldeCasteljau（保罗·德·卡斯特里奥）于1959年运用deCasteljau算法开发22PierreBézier(1910~1999),雷诺公司，法国工程师。PauldeCasteljau

(1930~),雪铁龙公司，法国工程师2.2Bezier曲线/曲面2.2.1Bezier曲线定义n次Bernstein多项式(n+1)个控制顶点定义n次Bezier曲线23QuadraticCubicQuartic2.2Bezier曲线/曲面2.2.1Bezier曲线性质插值端点曲线的起始点和终点和控制多边形的起始和结束位置是相切的保凸性，即位于控制点的凸包（凸多边形边界）内缺乏局部可控性242.2Bezier曲线/曲面2.2.1Bezier曲线deCasteljau递归算法（作图定理）25…………2.2Bezier曲线/曲面2.2.2Bezier曲面多项式曲面参数表达由两个变量的Bernstein混合函数表示m×n次Bezier曲面需要(m+1)×(n+1)个控制顶点26边界性角点插值性凸包性角点切平面2.2Bezier曲线/曲面2.2.3几何建模特点优点容易编程（deCasteljau递归）端点和切向插值特性参数表达缺点缺乏局部可控性改变其中一个控制顶点的位置，就会改变整个曲线\曲面的形状272.3B样条曲线/曲面2.3.1B样条曲线分段多项式曲线参数表达通过控制点生成28控制顶点节点样条（spline）源于生产实践，是富有弹性的细长条。用压铁使样条通过指定的型值点，并调整样条使它具有满意的形状，然后沿样条画出曲线。2.3B样条曲线/曲面2.3.1B样条曲线历史Schoenberg:样条曲线(1946)deBoor:B样条曲线的递归算法(1966)Riesenfeld:B样条曲线用作几何设计(1970s)Versprille:第一次讨论有理B样条曲线(1975)NUBRS:成为工业标准(1990s)292.3B样条曲线/曲面2.3.1B样条曲线300123452.3B样条曲线/曲面2.3.1B样条曲线定义31控制点

ci(i=0,…,n)称为deBoor点k阶B样条基函数（次数k-1）节点向量T={t0,…,tn+k+1}k阶(k-1次)B样条基函数deBoor-Cox递推定义2.3B样条曲线/曲面2.3.1B样条曲线B样条基函数取代Bernstein基函数1阶（0次）基函数2阶（1次）基函数322.3B样条曲线/曲面2.3.1B样条曲线B样条基函数取代Bernstein基函数3阶（2次）基函数332.3B样条曲线/曲面2.3.1B样条曲线三次B样条曲线342.3B样条曲线/曲面2.3.1B样条曲线性质保留Bezier曲线的优点局部可控性：修改一个控制顶点最多会影响k+1条曲线灵活拼接352.3B样条曲线/曲面2.3.1B样条曲线deBoor递归算法36……………2.3B样条曲线/曲面2.3.2B样条曲面双三次混合多项式曲面参数表达37局部性凸包性磨光性Bezier曲面包含性2.3B样条曲线/曲面2.3.3非均匀有理B样条曲面（NURBS）Non-uniform:节点向量Rational:对圆锥曲线曲面等的精确表示工业标准38权重2.3B样条曲线/曲面2.3.3非均匀有理B样条曲面（NURBS）NURBS曲线权重几何意义如果固定曲线参数u，而使权重变化，则NURBS曲线变成以为参数的直线，即NURBS曲线上相同的点位于同一直线上。

增大或减小，曲线被拉向或推离ci点39ci建模实例2.3B样条曲线/曲面40B-splinecontrolpointsB-splinecurveNURBSsurfaceDemo提纲基本概念自由曲线/曲面建模细分曲面建模三维重建数据结构413.1概念细分曲面：给定多面体，按照指定的细分规则进行无穷细化的极限极限曲面递归生成重新添加边、顶点、面来重新定义网格（拓扑）移动顶点的空间位置来平滑网格（几何）423.1概念细分曲面的特点曲面更灵活也更光滑在计算机动画中有广泛的应用43Catmull-Clark细分（DeRose，Pixar）AcademyAwardforBestAnimatedShortFilm,19983.1细分曲面细分曲面的核心：细分规则Catmull-ClarkDoo-SabinLoopButterfly443.2类型3.2.1Catmull-Clark细分E.Catmull和J.Clark在1978年发现双三次B样条的推广应用到多边形网格中几乎为C^2的连续性（除一些特殊点）453.2类型3.2.1Catmull-Clark细分双三次B样条曲面的切割磨光生成46面点边点新顶点3.2类型3.2.1Catmull-Clark细分任意多边形细分规则（几何）加一个新顶点（表面点）到每个表面的中心给每个边加一个新顶点（边点），这个顶点是两个端点和表面点的平均值用新的顶点替代旧的顶点47FacepointEdgepointVertexpoint3.2类型3.2.1Catmull-Clark细分任意多边形细分规则(拓扑)连接每个表面点到邻接的新边点上连接每个顶点到邻接的新边点上48细化的网格3.2类型3.2.1Catmull-Clark细分连续性作用细分规则一次以后，所有的面均变为四边形，而且从此以后度数不为4的顶点（称为奇异点）的个数保持不变。除了奇异点以外，Catmull-Clark曲面由一系列双三次B样条曲面覆盖而成，从而处处达到曲率连续。在奇异点处，仅切平面保持连续。49度为n的网格顶点3.2类型3.2.1Catmull-Clark细分结果示例50

(Demo)3.2类型3.2.2Doo-Sabin细分D.Doo和M.Sabin在1978年发现双二次B样条的推广应用到多边形网格C^1的连续性513.2类型3.2.2Doo-Sabin细分双二次B样条的切割磨光生成52每个面的每个顶点产生一个新顶点3.2类型3.2.2Doo-Sabin细分任意多边形细分规则（几何）对于每个表面有k个顶点V1,V2,…,VK，形成新的对应的顶点V1’,V2’,….,VK’53

3.2类型3.2.2Doo-Sabin细分任意多边形细分规则（拓扑）连接新的顶点去形成一个新的F类型表面连接围绕一个边周围的4个顶点去形成新的表面E连接围绕一个旧边周围的4个新的顶点，形成V54FEV3.2类型3.2.2Doo-Sabin细分连续性分析经过一次Doo-Sabin细分后，每个顶点的度数均为4；再经过一次细分后，度数不为4的面的个数保持不变。除了有限个奇异点外，由一系列双二次B样条曲面覆盖而成。在奇异点处，Doo-Sabin曲面也是一阶光滑连续。55新顶点3.2类型3.2.2Doo-Sabin细分结果示例56

(Demo)3.2类型3.2.3Loop细分C.Loop在1987年发现

箱样条的推广应用到三角形网格中几乎为C^2的连续性（除一些特殊点）573.2类型3.2.3Loop细分规则(几何/拓扑)对于每个边，计算一个新的点更新顶点位置连接新点形成一个新的网格583.2类型3.2.3Loop细分结果示例59

(Demo)3.2类型3.2.4Butterfly细分N.Dynetal.在1990年发现应用到三角形网格里几乎为C^1的连续性（除一些特殊点）603.2类型3.2.4Butterfly细分规则(几何/拓扑)对于每个边，使用规定的模式创造一个新的点保留旧的顶点，使用旧的边点和定点把一个旧表面转化成四个新表面613.2类型3.2.4Butterfly细分结果示例62

(Demo)3.2类型建模例子633.2类型建模例子64Demo提纲基本概念自由曲线/曲面建模细分曲面建模三维重建数据结构654.1概念在计算机图形学中，三维重建是指获取真实世界中物体形状和表观的过程66斯坦福大学“数字米开朗基罗”项目4.1概念分为被动式和主动式两种方式67基于图像的被动式方法基于视频的基于激光测距的主动式方法基于Kinect的4.1概念4.1.1被动式不需要与重建对象接触通过成像测量物体表面推测三维结构输入的是视频、图像等信息（ShapefromX）684.1概念4.1.1被动式优点破坏性小安全成本较低缺点对透明度敏感不能处理镜面反射和内部折射694.1概念4.1.2主动式通过机械接触或主动观测进行三维扫描例：传感器标记、结构光、激光、超声波等704.1概念4.1.2主动式三维扫描分类（按照测量手段）接触式3D扫描仪，比如坐标测量机71精确度高(μm)价格昂贵需要专业的操作者4.1概念4.1.2主动式三维扫描分类（按照测量方法）“飞时测距”（time-of-flight）：发出一个光脉冲，通常是激光，计算这束光返回所需要的时间，距离为光路长的一半72优点:扫描速度快便携，方便测量范围大缺点:精度有限(~5mm)4.1概念4.1.2主动式三维扫描分类（按照测量方法）三角测距激光扫描：发射一道激光到待测物上，并利用摄影机查找待测物上的激光光点；激光光点、摄影机，与激光发射源本身构成一个三角形。73优点:精度较高适合测量大尺寸物体缺点:扫描速度慢，需要花费较长时间4.1概念4.1.2主动式三维扫描分类（按照测量方法）结构光扫描：例如Kinect，使用红外线发射器和红外线传感器，发射红外线并接收反射回来的红外线来获取深度图像。74优点:价格便宜、易于安装缺点:有限的深度（40cm~3.5m）4.1概念4.1.2主动式优点重建精度高对物体材质不敏感缺点存在一定破坏性成本较高754.2基于图像的三维重建4.2.1概念Image-basedreconstruction从摄影图像对三维物体对象进行自动重建多视角重建、单幅图像重建76输入:图像输出:3D模型4.2基于图像的三维重建4.2.2多视角重建方法流程77用户输入纹理图像几何反射特性光照特性图像基于图像的建模基于图像的绘制逼真的三维场景模型!场景外观场景几何

光照模型反射特性4.2基于图像的三维重建4.2.2多视角重建方法流程摄像机标定三角测量从运动恢复结构（稀疏形状估计）立体匹配（稠密形状估计）7812344.2基于图像的三维重建4.2.2多视角重建摄像机标定从一些已知坐标的三维/二维点计算相机的内参（如焦距、畸变）和外参（相机的姿态）79小孔相机4.2基于图像的三维重建4.2.2多视角重建摄像机标定从一些已知坐标的三维/二维点计算相机的内参（如焦距、畸变）和外参（相机的姿态）80焦距畸变系数4.2基于图像的三维重建4.2.2多视角重建摄像机标定从一些已知坐标的三维/二维点计算相机的内参（如焦距）和外参（相机的姿态）81角点检测投影计算参数计算参数优化进行边缘检测，将各个矩形框边缘拟合成直线求直线交点得到角点，根据先验知识即可得到各角点的二维坐标和对应的空间点的三维坐标4.2基于图像的三维重建4.2.2多视角重建摄像机标定从一些已知坐标的三维/二维点计算相机的内参（如焦距、畸变）和外参（相机的姿态）82角点检测投影计算参数计算参数优化直接线性变换（DLT）4.2基于图像的三维重建4.2.2多视角重建摄像机标定从一些已知坐标的三维/二维点计算相机的内参（如焦距）和外参（相机的姿态）83角点检测投影计算参数计算参数优化从P计算内参矩阵和外参矩阵4.2基于图像的三维重建4.2.2多视角重建摄像机标定从一些已知坐标的三维/二维点计算相机的内参（如焦距）和外参（相机的姿态）84角点检测投影计算参数计算参数优化通过对P的非线性优化对相机参数进行优化4.2基于图像的三维重建4.2.2多视角重建三角测量给定一些点在两幅或更多的图像间（从校准相机）的对应关系，计算这些点的三维位置85特征匹配基准线相机1相机24.2基于图像的三维重建4.2.2多视角重建三角测量给定一些点在两幅或更多的图像间（从校准相机）的对应关系，计算这些点的三维位置86三维视射线相交4.2基于图像的三维重建4.2.2多视角重建从运动恢复结构（structure-from-motion）通过分析物体的运动得到三维结构信息的过程，即给定多个点在几幅图像间的对应关系，恢复得到它们的三维位置和相机参数874.2基于图像的三维重建4.2.2多视角重建从运动恢复结构（structure-from-motion）通过分析物体的运动得到三维结构信息的过程，即给定多个点在几幅图像间的对应关系，恢复得到它们的三维位置和相机参数88光束平差法如果点j在相机i中是可见的否则4.2基于图像的三维重建4.2.2多视角重建立体匹配（stereomatch）对所有的像素点同时应用特征匹配标准来获取它们的三维深度值894.2基于图像的三维重建4.2.2多视角重建立体匹配（stereomatch）对所有的像素点同时应用特征匹配标准来获取它们的三维深度值90极线约束法SSD:平方差和4.2基于图像的三维重建4.2.2多视角重建重建结果（法国Acute3D）91

(Demo)4.2基于图像的三维重建4.2.3单幅图像重建从一幅图像重建物体对象的三维模型高度病态问题92单幅图像高度病态问题病态问题多幅图像4.2基于图像的三维重建4.2.3单幅图像重建需要更多的先验知识作为问题求解的约束条件93输入超像素填充区域标识三维模型基于平面关系基于对称性交互指定线结构线/平面三维模型整体三维模型

(Demo)4.3基于视频的三维重建4.3.1概念将视频帧序列作为输入，进行物体的重建优点容易拍摄可以提供更加完整的数据灵活性缺点冗余数据结构混淆94Demo4.3基于视频的三维重建4.3.2类型根据数据利用方式的不同基于关键帧的视频重建基于深度图恢复的重建954.3基于视频的三维重建4.3.2-1基于关键帧的三维重建重要问题：关键帧的选择几何鲁棒性标准(GRIC)：通过两张图像之间的对应点，可以计算一个3x3的基础矩阵F，也可以计算一个3x3的单应变换H，比较用哪个变换误差小，也就是分数低。如果用单应变换分数小，则相对于第一张图像来说，第二张图像不能作为参考帧。964.3基于视频的三维重建4.3.2-1基于关键帧的三维重建方法流程974.3基于视频的三维重建4.3.2-2基于深度图恢复的三维重建基本思想：恢复视频中每一帧的像素点的深度信息重要问题：对视频每一帧的深度图恢复独立进行，因此恢复的深度图存在时间上的不一致性98…………4.3基于视频的三维重建4.3.2-2基于深度图恢复的三维重建方法流程99SfM视差初始化束优化获取相机的内外参数获取帧间连续深度的初始估计利用极线约束对初始深度进行迭代优化4.3基于视频的三维重建4.3.2-2基于深度图恢复的三维重建重建结果1004.4基于激光测距的三维重建4.4.1概念利用激光测距的原理，通过记录被测物体表面大量的密集的点的三维坐标、反射率和纹理等信息，可快速复建出被测目标的三维模型。1014.4基于激光测距的三维重建4.4.2方法流程1023D扫描视点规划配准合并网格点云多边形重建4.4基于激光测距的三维重建4.4.2重建方法核心问题：从点云得到多边形多面体近似物体表面103数学角度:数据拟合或者插值过程

MarchingcubeDelaunay三角化移动最小二乘方法（MLS）泊松方法……4.4基于激光测距的三维重建4.4.2重建方法4.4.2-1Marchingcube给定采样得到的一个体数据集，即三维物体的点云模型，将其分割为多个小立方体，相邻的8个采样点构成一个立方体。按扫描线顺序在每个立方体中构建等值面作为对应采样点的重建表面，将所有等值面相连得到完整的重建表面。1044.4基于激光测距的三维重建4.4.2重建方法4.4.2-2Delaunay三角化给定一个采样得到的三维体数据，即点云模型，应用Voronoi图对散乱点云进行Delaunay三角化得到，选择Delaunay三角化得到的某个子集作为重构出来的以三角面片表示的曲面。1054.4基于激光测距的三维重建4.4.2重建方法4.4.2-3移动最小二乘曲面拟合给定表面的一些点，寻找一个无网格的方法来定义一个拟合表面满足：平滑逼近局部依赖性1064.4基于激光测距的三维重建4.4.2重建方法4.4.2-4泊松方法给定一个有向点集，使用一个隐函数框架来计算一个三维指示函数（在模型内部的点定义为1，外部的点定义为0），并且通过提取等值面来获取重建的表面。建立八叉树空间计算有向点云向量场解泊松方程求指示函数提取等值面1074.5基于Kinect的三维重建4.5.1概念利用Kinect提供的实时深度图恢复物体对象三维模型1084.5基于Kinect的三维重建4.5.2方法4.5.2-1RGB-Dmapping基本思想：综合图像视觉特征和深度信息进行帧间配准，实时的融合深度图，重建室内场景三维模型。特点：从连续扫描的深度图恢复三维场景，同时避免误差累积及结构歧义性等1094.5基于Kinect的三维重建4.5.2方法4.5.2-1RGB-Dmapping算法流程110视觉特征+深度信息三维模型深度配准RGBD-ICP闭环检测4.5基于Kinect的三维重建4.5.2方法4.5.2-1RGB-DmappingRGBD-ICP（IterativeClosestPoint：迭代最邻近点）利用SIFT+深度作为特征，进行深度图的帧间配准1114.5基于Kinect的三维重建4.5.2方法4.5.2-1RGB-Dmapping闭环检测判断是否回到之前的位置：利用图结构记录帧间配准时误差，没有闭环的重建对应线性链（linearchain）重建的重复物体进行正确归并112surfel点云4.5基于Kinect的三维重建4.5.2方法4.5.2-2KinectFusion基本思想：追踪相机姿态，并将当前的深度数据从相机实时地融合到一个全局的3D模型中。特点：对物体从不同视角持续扫描，三维重建精度可以由粗到细地逐渐提高。1134.5基于Kinect的三维重建4.5.2方法4.5.2-2KinectFusion算法流程114深度图转换姿态配准三维融合模型渲染4.5基于Kinect的三维重建4.5.2方法4.5.2-2KinectFusion深度图转换转换深度值到相机坐标系中计算顶点法向量115像素的深度值Kinect摄像头的内参矩阵深度值在相机坐标系中的3D表示4.5基于Kinect的三维重建4.5.2方法4.5.2-2KinectFusion姿态配准ICP（IterativeClosestPoint：迭代最邻近点）1164.5基于Kinect的三维重建4.5.2方法4.5.2-2KinectFusion立体空间融合根据深度图中像素对应的深度值，构造体积分模型，即像素平面作为定义域，深度值作为函数值。通过积分运算，生成封闭的体模型。1174.5基于Kinect的三维重建4.5.2方法4.5.2-2KinectFusion模型渲染通过投射光线与体模型的相交运算，得到模型表面对应的交点位置、法向等绘制参数。利用光线跟踪方法进行模型绘制和显示。118光线投射4.5基于Kinect的三维重建4.5.2方法4.5.2-2KinectFusion结果1194.6视觉同时定位与地图构建4.6.1概念利用激光雷达、摄像机等传感器数据构建未知环境下的空间位置、运动状态、环境三维模型120同时定位与建图传感器传感器采集数据传感器空间位置、运动状态环境三维模型4.6视觉同时定位与地图构建4.6.2视觉同时定位与建图传感器主要使用摄像机，采集数据主要是视频图像的一类同时定位与建图技术（vSLAM）主要包括前端时间里程计、回环检测、后端优化和建图四个关键部分121视频图像vSLAM三维点云视频帧序列视觉里程计建图优化回环检测4.6视觉同时定位与地图构建4.6.2视觉同时定位与建图视觉里程计提取和匹配图像之间的特征点，以此估计两帧的相机运动采用对极几何、PnP和迭代最近邻（ICP）三种方式计算帧间相机运动122基于ORB特征的图像匹配对极几何迭代最近邻PnP4.6视觉同时定位与地图构建4.6.2视觉同时定位与建图回环检测接收视频帧图像序列，检测相机是否经过之前的位置而形成的环路主要用于解决视觉里程计过程中产生的累积漂移1234.6视觉同时定位与地图构建4.6.2视觉同时定位与建图后端优化接收视觉里程计估计的不同时刻的相机位姿，以及回环检测的信息，进一步对相机位姿进行优化，得到全局一致的轨迹和地图124基于卡尔曼滤波优化基于BA的后端优化4.6视觉同时定位与地图构建4.6.2视觉同时定位与建图建图构建地图的过程，在接收优化后的相机位姿后，根据估计的轨迹构建符合任务要求的三维场景结构度量地图和拓扑地图125度量地图拓扑地图提纲基本概念自由曲线/曲面建模细分曲面建模三维重建数据结构1265.1概念在计算机内部表示、存储几何模型的数据组织形式层次模型构造实体几何模型（CSG）八叉树模型边界模型体素模型127实体建模计算机5.2常用数据结构5.2.1构造实体几何模型Constructivesolidgeometry（CSG）元几何元素通过布尔操作的模型描述元几何：球体，圆柱体，立方体,…布尔操作：或，交集，差,…1285.2常用数据结构5.2.1构造实体几何模型布尔操作或，交集，差129

UnionIntersection

Difference

5.2常用数据结构5.2.1构造实体几何模型布尔操作或，交集，差1305.2常用数据结构5.2.1构造实体几何模型优点数学精确，比如在CAD/CAM固体或者不透水物体模型，比如制造业缺点形式复杂1315.2常用数据结构5.2.2边界模型由顶点和面列表的多边形网格的描述边界表示法（B-rep）：显式模型的顶点，边，和额外的邻接信息存储在网格面1325.2常用数据结构5.2.2边界模型5.2.2-1简单边界模型表示一个多边形网格的一种常见的方法是一个共享的顶点列表和一个存储指向它的顶点的指针列表。这种表示是方便和高效的许多目的，但是在某些领域，它证明是无效的。1335.2常用数据结构5.2.2边界模型5.2.2-1简单边界模型优点简单，方便构造缺点复杂数据操作困难134不容易获得实体之间的相邻关系，并执行插入/删除操作！5.2常用数据结构5.2.2边界模型5.2.2-2半边表示半边数据结构是一条边的一半有向表示，而一对中的两个边有相反的方向135v1v2v3v4v5f1f2f3e1,1e2,1e3,1e3,2e4,1e5,1e4,2e6,1e7,1Twohalf-edgesmakeupanedge.5.2常用数据结构5.2.2边界模型5.2.2-2半边表示一条边的一半136SolidFaceLoopHalfEdgeVertexnextsnextfnextlnxtnextvprevsprevfprevlprvprevvsfacesvtxfloopsledgfsolidlfacefsolid5.2常用数据结构5.2.2边界模型5.2.2-2半边表示顶点为主137v1v2v3v4v5f1f2f3e1,1e2,1e3,1e3,2e4,1e5,1e4,2e6,1e7,1顶点坐标开始点的半边v1(x1,y1,z1)e2,1v2(x2,y2,z2)e1,1v3(x3,y3,z3)e4,1v4(x4,y4,z4)e7,1v5(x5,y5,z5)e5,1顶点存储5.2常用数据结构5.2.2边界模型5.2.2-2半边表示半边为主138v1v2v3v4v5f1f2f3e1,1e2,1e3,1e3,2e4,1e5,1e4,2e6,1e7,1半边开始点相反半边表面下一个半边前一个半边e3,1v3e3,2f1e1,1e2,1e3,2v2e3,1f2e4,1e5,1边存储5.2常用数据结构5.2.2边界模型5.2.2-2半边表示优点直接表示顶点，表面，边,…允许在常量时间内执行所有的邻接查询,e.g,vertex2edge,vertex2face,edge2face,…缺点形式复杂1395.2常用数据结构5.2.3体素模型用符号距离函数（SDF）、示性函数等隐式形式记录三维几何形状。三维空间离散化为稠密的体素块，存储每个体素块索引以及该体素中心位置的隐式函数值。140

5.2常用数据结构5.2.3体素模型体素块集合：隐式函数值：141ReferencesTheNURBSbook.LesA.Piegl,WayneTiller.Springer,2013.Pointcloudsurfacerepresentation.MarkPauly.Eurographicscourse,2003.Asurveyofpoint-basedtechniquesincomputergraphics.LeifKobbelt,MarioBotsch.ComputerandGraphics,2004.Polygonmeshprocessing.Botsch,Kobbelt,Pauly,Alliez,Levy.CRCpress,2010.Multipleviewgeometryincomputervision.R.Hartley,A.Zisserman.2000.142ReferencesFittingB-splinecurvestopointcloudsbycurvature-basedsquareddistanceminimization.W.Wang,etal.,TOG2006.Surfacereconstructionfromunorganizedpoints.Hoppe,DeRose,Duchamp,McDonald,Stuetzle.Siggraph92.Statisticalpointgeometry.Kalaiah,Varshney.SymposiumonGeometryProcessing,2003.Reconstructionandrepresentationof3Dobjectswithradialbasisfunctions.Carr,Beatson,Cherrie,Mitchell,Fright,McCallum,Evans.Siggraph,2001.Spectralsurfacequadrangulation.S.Dong,P.Bremer,M.Garland,V.Pascucci,J.Hart.Siggraph,2007.Variationaltetrahedralmeshing.P.Alliez,D.Cohen-Steiner,M.Yvinec,M.Desbrun.Siggraph2005.All-hexmeshgenerationviavolumetricpolycubedeformation.J.Gregson,A.Sheffer,E.Zhang.ComputerGraphicsForum,2011.Harmonicvolumetricmappingforsolidmodelingapplications.X.Li,X.Guo,H.Wang,Y.He,X.Gu,H.Qin.SPM,2007.143ReferencesAhierarchicalboundarymodelforsolidobjectrepresentation.L.Floriani,B.Falcidieno.TOG1988.Surfacereconstructionfromconstructivesolidgeometryforinteractivevisualization.AdvancesinVisualComputing,2007.OctreerepresentationanditsapplicaionsinCAD.Z.-S.Tang.JCST,1992.Directededges–ascalablerepresentationfortrianglemeshes.S.Campagna,L.Kobbelt,H.Seidel.ACMJournalofGraphicsTools,1998.Passivereconstructionofhighqualitytextured3Dmodelsofworksofart.N.Brusco,L.Ballan,G.Cortelazzo.VAST,2005.Thebundleadjustment-progressandprospects.D.C.Brown.InternationalArchivesofPhotogrammetry,21(3),1976.Bundleadjustment–amodernsynthesis.W.Triggs,etal.Springer,2000R.SzeliskiandS.B.Kang.Recovering3Dshapeandmotionfromimagestreamsusingnonlinearleastsquares.J.VisualCommun.ImageRepresent,1994.144ReferencesSeeingdoublewithoutconfusion:structure-from-motioninhighlyambiguousscenes.N.Jiang,etal.CVPR,2012.Multiple-viewstructureandmotionfromlinecorrespondences.A.Bartoli,P.Sturm.ICCV,2003.Robustplane-basedstructurefrommotion.Z.Zhou,H.Jin,Y.Ma.CVPR,2012.Semanticstructurefrommotionwithpoints,regions,andobjects.S.Bao,M.Bagra,Y.Chao,S.Savarese.CVPR,2012.Marchingcubes:ahighresolution3Dsurfaceconstructionalgorithm.W.LorensenandH.Cline.Siggraph,1987.AnewVoronoi-basedsurfacereconstructionalgorithm.N.Amenta,etal.Siggraph,1998.Robustmovingleast-squaresfittingwithsharpfeature.S.Fleishman,etal.Siggraph,2005.Poissonsurfacereconstruction.M.Kazhdan,etal.SGP,2006.145ReferencesRGB-Dmapping:usingkinect-styledepthcamerasfordense3Dmodelingofindoorenvironments.P.Henry,etal.IJRR,2012.Integratingdepthandcolorcuesfordensemulti-resolutionscenemappingusingRGB-Dcameras.J.StucklerandS.Behnke.MFI,2012.KinectFusion:real-time3Dreconstructionandinteractionusingamovingdepthcamera.S.Izadi.UIST,2012.Modelingbyexample.T.Funkhouser,M.Kazhdan,P.Shilane,P.Min,W.Kiefer,A.Tal.Siggraph,2004.AProbabilisticModelforComponent-BasedShapeSynthesis.EKalogerakis,etal.,Siggraph2012.Plants,FractalsandFormalLanguage.A.R.Smith.ComputerGraphics,1984.146计算机图形学第四章数字几何处理供《现代计算机图形学基础》配套使用147提纲1.基础2.网格去噪3.网格简化

4.重新网格化5.网格编辑6.网格形变1481.1几何数字化媒体数字化进程声音、图像、视频、几何149媒体数字化声音图像视频几何1.1几何数字化2000年左右1995年，“玩具总动员”动画，数字化娱乐1997年，“数字米开朗基罗”计划，数字化文物1998年，“数字地球”，数字化生活1501.2数字几何1.2.1几何表示离散元素表示几何形状点云多边形网格1511.2数字几何1.2.1几何表示1.2.1-1点云采用三维坐标点作为模型几何表示的基本单元1522.5K6K17K1.2数字几何1.2.1几何表示1.2.1-1点云优点简单的数据结构更精致缺点不连续的几何基元大量的数据拓扑结构等性质表示复杂153≈10亿个点1.2数字几何1.2.1几何表示1.2.1-2多边形网格由顶点、边和多边形面组成的集合，定义了三维形状154三角形网格四边形网格1.2数字几何1.2.1几何表示1.2.1-2多边形网格由顶点、边和多边形面组成的集合，定义了三维形状分段线性逼近函数1551.2数字几何1.2.1几何表示1.2.1-2多边形网格156NURBS网格CncontinuityQuadtopologyC0continuityTopologyfree点云网格C-1continuityTopologyfreeNo-connectivityC0continuityTopologyfreeConnectivity1.2数字几何1.2.2几何性质1.2.2-1基本概念顶点的度（degree）：相邻边的数量表面朝向（orientation）：顺时针方向的顶点的顺序或者逆时针方向1571.2数字几何1.2.2几何性质1.2.2-1基本概念拓扑（topology）：网格几何元素的连接关系亏格（genus）：影响表面连续性的分割曲线条数1581.2数字几何1.2.2几何性质1.2.2-2基本性质流形网格：局部同胚与圆盘每个边只连接一个或者两个表面表面上相邻顶点形成一个封闭或开放式扇形非流形网格：局部与圆盘不同胚1591.2数字几何1.2.2几何性质1.2.2-2基本性质开网格：具有一条或多条边界边界边：只连接一个入射的表面，或者说顶点只连接一个开的扇形闭网格：不存在边界1601.2数字几何1.2.2几何性质1.2.2-2基本性质欧拉-庞加莱特性给定一个无边界的流形网格M，顶点、边、面的个数满足：161#V=766#F=1536#E=2304g=2#V=2999#F=5998#E=8997g=1#V=7929#F=15855#E=23782g=01.2数字几何1.2.3三角网格上的微分算子三角面片的线性表示：重心坐标1621.2数字几何1.2.3三角网格上的微分算子三角面片的线性表示：重心坐标一阶导数1631.2数字几何1.2.3三角网格上的微分算子三角面片的线性表示：重心坐标一阶导数1641.2数字几何1.2.3三角网格上的微分算子三角面片的线性表示：重心坐标一阶导数二阶导数1651.3几何深度学习通过在三维几何上定义深度神经网络并进行计算，完成数字几何处理的相关任务。166?1.3几何深度学习1.3.1点云神经网络PointNet：面向三维点云数据的深度神经网络输入：点云转换成n×3的向量结构：多层感知机、向量卷积输出：特征向量1671.3几何深度学习1.3.1点云神经网络PointNet：面向三维点云数据的深度神经网络168点云分割1.3几何深度学习1.3.2网格神经网络MeshCNN：面向三角网格数据的深度神经网络输入：三角网格面片结构：以边为基本单元的卷积算子输出：特征向量169五维向量1.3几何深度学习1.3.2网格神经网络MeshCNN：面向三角网格数据的深度神经网络170网格分割提纲1.基础2.网格去噪3.网格简化

4.网格参数化5.网格编辑6.网格形变1712.1概念现实世界中的物体通过数字化扫描获取与重建后的网格往往是带有噪声的激光扫描的深度图像

从图像重建的三维模型1722.1概念网格去噪消除网格模型表面噪声，获得一个几何光滑模型又称为网格光顺、网格滤波等173网格去噪2.1概念网格去噪的主要挑战什么是网格表面的噪声？表面的凹凸表面的高频部分…没有精确的数学公式检测困难较弯曲的地方高频部分…1742.2方法目标

消除高频噪声：量化模型表面的高频信息保留全局特征：全局特征的几何表示175+=平滑噪声特征2.2方法形状演化策略移动网格顶点保持拓扑：不改变连接关系保持形状：减少曲率变化描述为形状演化1762.2方法形状演化策略直接方案直接拉普拉斯平滑加权拉普拉斯平滑间接方案全局拉普拉斯平滑1772.2方法2.2.1直接拉普拉斯平滑将顶点移动到相邻顶点的平均位置178平均位置移动顶点2.2方法2.2.1直接拉普拉斯平滑示例1792.2方法2.2.1直接拉普拉斯平滑特点循环迭代执行等价于某种能量函数最小化能量：网格中边长平方之和参数：𝜆>

0控制收敛速度不反映网格形状拉普拉斯坐标对旋转敏感局部几何形状会发生扭曲1802.2方法2.2.2加权拉普拉斯平滑伞型权重均值权重简单的平均，获得的精度较低余切权重可获得较好的网格变形结果1812.2方法2.2.2加权拉普拉斯平滑结果182原始直接拉普拉斯加权拉普拉斯(余切)2.2方法2.2.3全局拉普拉斯平滑183网格的拉普拉斯算子其他

线性方程组2.2方法2.2.3全局拉普拉斯平滑求解拉普拉斯方程齐次方程k是网格中连通区域的数量需要加上某些限制184秩(L)=n-k；2.2方法185控制点控制点2.2.3全局拉普拉斯平滑求解拉普拉斯方程加上部分控制点进行约束秩(L)=n3070个顶点，6144个三角形2.2方法2.2.3全局拉普拉斯平滑结果186Demo134359个顶点，268714个三角形提纲1.基础2.网格去噪3.网格简化

4.网格参数化5.网格编辑6.网格形变1873.1概念网格简化（meshsimplification）通过删除或者修改模型中对形状影响不大的部分网格面片信息（包括顶点、边和面片等）来减少多边形面片数量。1883.1概念网格简化（meshsimplification）问题起源：重建的网格模型通常规模较大，不利于存储、传输和显示，因此需要进行满足条件的网格数据简化189≈20亿个三角形移动设备3.1概念遵循原则顶点最少原则：即在给定误差上界的情况下,使得简化模型的顶点数最少误差最小原则：给定简化模型的顶点个数,使得简化模型与原始模型之间的误差最小1903.2简化方法3.2.1顶点聚类思想：空间相邻的近似顶点进行合并方法：将原模型包围盒划分,使得小区域中包含了许多散落其中的顶点；再将此区域中的顶点合并,形成新的顶点；根据原始网格的拓扑关系,把这些顶点三角化后,从而得到简化模型1913.2简化方法3.2.1顶点聚类算法聚类生成通过空间划分将原始模型的包围盒划分成若干区域1923.2简化方法3.2.1顶点聚类算法合并新顶点顶点位置的平均值作为新顶点顶点位置的中值作为新顶点通过二次误差测度求得新顶点1933.2简化方法3.2.1顶点聚类算法合并新顶点顶点位置的平均值作为新顶点顶点位置的中值作为新顶点通过二次误差测度求得新顶点194平均顶点位置中值顶点位置二次误差测度3.2简化方法3.2.1顶点聚类算法网格生成聚类p：{𝑝_0,…𝑝_𝑛}q：{𝑞_0,…𝑞_𝑛}如果(𝑝_𝑖,𝑞_𝑖)中间有边那么就连接(p,q)195Demo3.2简化方法3.2.2渐进式网格（Progressivemesh,PM）思想：基于顶点和边的基本操作进行化简方法：以边合并和点移除为基本操作，记录模型简化过程中原顶点和新顶点位置以及顶点间的连接关系的变动信息,从而生成由原始模型的最简化模型和一系列简化信息组成的渐进表示1963.2简化方法3.2.2渐进式网格（Progressivemesh,PM）迭代算法选取网格区域应用简化算子(减少顶点与边)直到没有更多减少的可能1973.2简化方法3.2.2渐进式网格（Progressivemesh,PM）简化算子：点移除198选择一个即将移除的顶点选择所有和顶点相连的三角形移除选择的三角形添补缺失3.2简化方法3.2.2渐进式网格（Progressivemesh,PM）简化算子：边合并1993.2简化方法3.2.2渐进式网格（Progressivemesh,PM）结果200Demo3.2简化方法方法对比顶点聚类计算快，但难以控制简化网格网格拓扑结构被改变误差在全局范围内，但没有接近最优渐进式网格网格质量与速度之间良好的平衡网格拓扑结构不改变可以限制偏差，提高网格质量2013.3基于深度学习的网格简化简化算子：复杂网格到简单网格的映射深度神经网络进行简化算子的函数拟合202顶点聚类f顶点移除点采样器边预测器面分类器3.3基于深度学习的网格简化点采样器：从原始网格的N个顶点中选取用于构造简化网格的M个顶点。顶点与1-邻域内顶点偏离程度为2033.3基于深度学习的网格简化边预测器：建立采样顶点之间的边连接关系。两个顶点与

之间边连接的概率为2043.3基于深度学习的网格简化面分类器：根据边预测器得到的三角面片作为初值，通过图神经网络挑选能够出现在简化网格中的三角面片。两个三角面片与

之间相对位置关系2053.3基于深度学习的网格简化206通过面分类器获得每个三角面片属于简化网格的概率，并通过和预设的阈值比较，得到保留下来的三角面片，组成简化后的网格。提纲1.基础2.网格去噪3.网格简化

4.网格参数化5.网格编辑6.网格形变2074.1概念4.1.1定义网格表面和参数域之间的连续映射输入：三维多边形网格表面输出：参数域同构多边形2084.1概念4.1.1定义问题起源：1974年，Catmull提出纹理映射技术，通过纹理空间(u,v)和三维曲面(s,t)之间的对应关系，计算三维曲面上每一点颜色值209纹理映射4.1概念4.1.1定义问题起源世界地图绘制球面坐标系2104.1概念4.1.1定义问题起源世界地图绘制211原图球极平面投影墨卡托投影阿尔伯斯投影保角的等积的保角的4.1概念4.1.1定义问题起源世界地图绘制212墨卡托投影4.1概念4.1.2类型理想的参数化：保形参数化保持所有的基本几何量不变：长度、角度、面积仅适用于可展曲面对于一般曲面总会有扭曲！213可展曲面一般曲面4.1概念4.1.2类型按照几何量扭曲分类保长度参数化（等距）保角度参数化（等角）保面积参数化（等积）214保长度参数化保角度参数化保面积参数化长度角度面积4.1概念4.1.2类型按照参数域分类平面参数化参数域是平面非平面参数化球面参数化基域参数化……215平面参数化球面参数化基域参数化4.2方法4.2.1数学模型参数域(u,v)参数化映射X(u,v)Jacobi矩阵反映

几何扭曲2164.2方法4.2.1数学模型Jacobi矩阵奇异值分解217gG奇异值:γ,Γ保角度

γ=Γ保面积

γ

Γ

=1保长度

γ=Γ

=14.2方法4.2.1数学模型Jacobi矩阵奇异值分解2184.2方法4.2.1数学模型定理：每一个保长度的映射都是保角度的和保面积的，反之亦然。保长度参数化是理想的但是并不多见。在实际计算中，我们使用：保角度的保面积的两者之间的平衡219保长度保角度保面积4.2方法4.2.2平面参数化寻找网格表面和平面之间的一一映射开网格（具有边界的网格）固定边界映射自由边界映射闭网格设定边界转化为开网格2204.2方法4.2.2平面参数化4.2.2-1开网格的平面参数化弹簧模型（Springsystem）221弹簧系数4.2方法4.2.2平面参数化4.2.2-1开网格的平面参数化弹簧模型（Springsystem）222仿射组合系数4.2方法4.2.2平面参数化4.2.2-1开网格的平面参数化弹簧模型（Springsystem）仿射组合系数凸组合（convexcombination）线性重构（linearreproduction）223平均系数均值坐标调和坐标4.2方法4.2.2平面参数化4.2.2-1开网格的平面参数化弹簧模型（Springsystem）仿射组合系数线性方程组求解224增加约束条件计算非平凡解！4.2方法4.2.2平面参数化4.2.2-1开网格的平面参数化固定边界映射（重心坐标映射）225正方形已知未知4.2方法4.2.2平面参数化4.2.2-1开网格的平面参数化固定边界映射（重心坐标映射）2264.2方法4.2.2平面参数化4.2.2-1开网格的平面参数化固定边界映射（重心坐标映射）227平均系数均值坐标调和坐标4.2方法4.2.2平面参数化4.2.2-1开网格的平面参数化自由边界映射固定边界（凸边界）产生较大的几何扭曲通过自由边界减少参数化过程中几何扭曲228固定边界自由边界关键问题：寻找合适的约束来计算有效参数化4.2方法4.2.2平面参数化4.2.2-1开网格的平面参数化基于角度的网格展开（Angle-basedflattening,ABF）思想：通过构建参数域三角形内角分布，恢复顶点对应的平面坐标，从而达到保持角度的目的方法：在三角形的内角形成的角度空间定义参数化映射，通过平面三角形的角度约束计算最优参数化坐标2294.2方法4.2.2平面参数化4.2.2-1开网格的平面参数化基于角度的网格展开（Angle-basedflattening,ABF）230角度约束:所有内角为正三角形内角之和为π平面顶点周角为2π平面顶点一周封闭4.2方法4.2.2平面参数化4.2.2-1开网格的平面参数化基于角度的网格展开（Angle-basedflattening,ABF）优点不会发生边“翻转”优化过程收敛缺点非线性优化（牛顿迭代优化）边界可能发生交叉2314.2方法4.2.2平面参数化4.2.2-1开网格的平面参数化最小二乘共形映射（Least-squareconformalmapping,LSCM）思想：保角度映射即共形映射，满足柯西-黎曼方程方法：在三角面上离散柯西-黎曼方程2324.2方法4.2.2平面参数化4.2.2-1开网格的平面参数化最小二乘共形映射（Least-squareconformalmapping,LSCM）233目标函数:4.2方法4.2.2平面参数化4.2.2-1开网格的平面参数化最小二乘共形映射（Least-squareconformalmapping,LSCM）优点保持角度线性优化缺点无法保证参数化的有效性2344.2方法4.2.2平面参数化4.2.2-1开网格的平面参数化直接几何扭曲优化思想：约束三角片参数化映射的几何扭曲方法：直接优化以奇异值为变量的函数235保角度

γ=Γ保面积

γ

Γ

=1保长度

γ=Γ

=1ASAPAAAPARAP4.2方法4.2.2平面参数化4.2.2-1开网格的平面参数化直接几何扭曲优化2364.2方法4.2.2平面参数化4.2.2-1开网格的平面参数化直接几何扭曲优化优点保长度参数化迭代线性优化缺点无法保证参数化结果的有效性2371st2nd3rd4.2方法4.2.2平面参数化4.2.2-1开网格的平面参数化238ABFLSCMARAP4.2方法4.2.2平面参数化4.2.2-2闭网格的平面参数化寻找最优切割线将网格切开，变成开网格采用开网格平面参数化2394.2方法4.2.2平面参数化4.2.2-2闭网格的平面参数化切割线方法方法1：通过最小生成树在网格表面寻找曲率高的网格顶点及边，形成分割线方法2：结合网格顶点的可见性分布，寻找尽可能被隐藏的切割线240方法1方法24.2方法4.2.2平面参数化优点计算复杂度较低显式控制几何扭曲缺点仅适用于与拓扑圆盘同构的网格曲面对于亏格大于0的网格曲面，一般需要按照一定的规则将整个网格分片，会引起参数化结果不连续2414.2方法4.2.3球面参数化将亏格为零的三维网格参数化映射到球面等价于将顶点之间连接结构嵌入到单位球242Steinitz‘stheorem：任何亏格为零且封闭的三角化可以映射成球面三角化。4.2方法4.2.3球面参数化球面重心坐标映射243Laplacian矩阵i-throwofLaplacian4.2方法4.2.3球面参数化球面重心坐标映射2444.2方法4.2.4基域参数化选取几何简单，同时拓扑结构（亏格）一致的基网格作为参数域。最常用的基网格参数域是单纯复形（可以看作是传统网格的一部分，只包含连接信息）。245genus=0genus=3提纲1.基础2.网格去噪3.网格简化

4.网格参数化5.网格编辑6.网格形变2465.1概念网格编辑（Meshediting/deformation）定义：操纵和修改网格表面的几何形状，同时能够保留原始网格几何细节的操作。2475.1概念网格编辑（Meshediting/deformation）问题起源：各种应用中需要动态形状，例如，游戏、电影、计算机辅助设计等。但是，每种状态下的形状单独建模比较费时费力。目标通过内部或者外部作用力改变形状编辑应该是快速的并且尽可能接近现实物体操作2485.2编辑方法5.2.1自由编辑（Free-formdeformation）思想：将网格嵌入到一个简单的控制多面体中控制多面体比原始形状简单方法：对控制多面体进行变形

根据变形后的控制多面体更新嵌入网格的形状249控制网格和原始网格编辑后结果5.2编辑方法5.2.1自由编辑（Free-formdeformation）5.2.1-1基于样条控制顶点的编辑采用三变量张量积样条表示网格形状改变样条控制顶点编辑网格形状2505.2编辑方法5.2.1自由编辑（Free-formdeformation）5.2.1-2基于重心坐标的编辑三角形重心坐标三角网格重心坐标2515.2编辑方法5.2.1自由编辑（Free-formdeformation）5.2.1-2基于重心坐标的编辑结果252Demo5.2编辑方法5.2.1自由编辑（Free-formdeformation）优点任意形状的平滑编辑对编辑的局