chapter11-多边形.pdf

第11章多边形技术 金小刚 Email: jin@ /home/jin/course.htm 浙江大学CADCG国家重点实验室 紫金港校区 信息与控制大楼506 内容简介 ● Tessellation(细化) 将多边形分割为更易于处理的三角形、四边形等基本单位 的过程。 ● Consolidation (合并) 合并包括多边形数据的连接和融合，以及新数据的衍生， 例如物体表面法线。 ● Stripification(条带化) 条带化是将三角形网格转换成多组多边形条带的过程。 ● Simplification(简化) 简化是将数据中不必要或不重要的特征删除的过程。 三维数据的来源 ● 以几何描述方式直接输入模型； ● 将其它形式的数据转化为面或体数据。如将蛋白 质数据转化为球体或圆柱体； ● 通过编写程序来生成模型(Procedural Modeling)； ● 使用建模程序； ● 使用三维数字化仪对真实模型进行采样； ● 基于图像的方法； ● 使用三维扫描仪采集深度信息； 细化与三角剖分 ● 进行多边形细化的原因 ■许多图形API和硬件都针对三角形进行了优化; ■绘制程序只能对凸多边形进行绘制(这种细化也 称为凸分解) ； ■ 为使用辐射度技术进行绘制，需要对物体表面 进行网格化; ■其它非图形学的原因… 如有限元分析、避免狭长三角形等 细化与三角剖分 ● 不同类型的细化示例 (a)没有细化(b)细化为2个凸多边形(c)三角剖分 (d)均匀网格化 细化与三角剖分 ● 表面细化的一个重要步骤是如何最好地将三维多边 形投影成二维图形 ■ 面积测试：丢弃xyz三个坐标中的一个，使得投影多边形 在该坐标平面上具有最大的投影面积，取该坐标平面为投 影平面。可以直接计算投影面积来确定，也可以通过丢弃 多边形法向中绝对值最大的坐标来确定。 ■ 法向测试：根据法向计算公式和多边形是否平坦来决定。 为避免自交等问题，可把多边形投影到平均平面上。 接近视线的弯曲四边形，形成病态的蝴蝶结状或沙漏状图形 细化与三角剖分 ● 三角剖分的方法 ■ 基本方法：检查多边形中任意两顶点间的线段，如果不 相交、不重叠，那么将多边形分割成两部分，采用相同 方法对新生成的多边形继续分割。算法复杂度O(n3) 。 ■ 耳状剪切(Ear Clipping)：下左图为一在顶点v2 、v4 、 v5处有耳状物的多边形。右图中删除了v4处的耳状物。 对邻接顶点v3 、v5重复检查，考虑是否形成耳状物。算 法复杂度O(n2) 。 细化与三角剖分 ● 存储与绘制 ■ 将多边形分解为凸多边形比三角剖分更有效，因 为凸多边形可用扇形或者三角形条带表示； ■ 凸多边形分解方法: (1). Quick and Dirty 方法； (2). 最优化方法。 ● 多轮廓线多边形转换为单轮廓线多边形 将具有三个轮廓线的多边形转化为单轮廓多边形 着色问题 ● 四边形的着色问题 ■ 为便于显示，通常将四边形分割为三角形，而不 同的分割方法会得到不同的显示效果； ■ 分割四边形应采取差异最小化原理； ■ 对于辐射度方法或预光照四边形可选择色彩差异 最小的对角线； (a)四边形绘制(b) 右上角和左下角连接的三角形(c)左上角 和右下角连接的三角形