越大（如图２（ａ）所示），因为ａ：＞ｄ。，显然三角形１２
２（ａ）顶的面积增大，而顶角ａ：和ａ，则保持不变。由 于顶点口Ⅲ进一步远离顶点ｔ，ｉ，因此边矢量Ｅ¨＋：对
因为
Ａｉ＝÷Ｉ Ｅ¨＋ｌ｜Ｉ Ｅ州＋２ ８ｉｎａ。
（７）
将式（７）代入式（６），即得到 ０’●＿…ｓ‘ｉｎ‘２‘ｎｆｆ‘Ⅳ’ＩＩ
定义２ 由３维网格模型上某顶点矽ｉ和其相邻 顶点Ⅳ（口ｉ）所围成的环称为ｌ—ｒｉｎｇ；点彭ｉ为ｌ—ｒｉｎｇ的 中心点，Ⅳ（∥ｉ）为ｌ—ｒｉｎｇ的边界点；以点口ｉ为顶点的 三角形集合ｔ＝（ｆ。，￡：，…，ｔ。），称为点和；的ｌ一一ｎｇ 三角形。
定义３任一顶点ｑ的单位法矢记为厅。；第ｍ 个三角形ｔ。的面积为Ａ。，其所在平面的单位法矢记 为Ⅳ。。
本文首先对目前具有代表性的５种三角网格模 型的顶点法矢估算方法进行了分析，通过比较各种 估算方法在顶角、面积等权重方面的处理特点以及 存在的缺陷，并引入了一种评价因子，用来对三角形 形状质量进行量化，且在理论上给予了证明，据此提 出了一种改进的基于三角形形状修正的法矢估算方 法，该方法充分考虑了三角形的形状、面积、顶角等 因素对顶点法矢的影响。最后通过对规则和不规则 的６种不同的二次曲面网格模型进行实验验证，并 以顶点法矢的算术平均误差和标准方差来分别评价 各估算方法的准确度和稳定性。结果证明，本文改 进方法估算的顶点法矢具有较其他方法更高的精度， 特别对于不规则及三角形形状存在较大差异的三角 网格模型，该方法的计算精度最好、稳定性最高。
基于上述分析，本文提出了一种改进的基于三 角形形状修正的法矢估算方法，该方法同时考虑了 面积的影响权重。
２基于三角形形状修正的法突估算
２．１三角形形状评价指标 三角形形状评价指标用于对三角形的形状的规
整度进行量化评价，Ｈａｍａｎｎ提出以３个内角的余弦 和为评价指标…１；Ｇｕｅｚｉｅｃ采用面积与边长平方和 之比最大来衡量三角形形状的规整程度¨“；张必强 等人则以最大边长与最小边长的差值与第３边长之 比来进行评价Ⅲ１。但上述各方法都缺乏理论上的 完备性，至今也没有公认的最好的评价方法¨“。
∑Ｍ
露ｉ＝—｝一
（２）
Ｉ｜∑Ｍ ０
方法２‘５１ Ｔｈｕ姗ｅｒ和ｗｕｔｈｒｉｃｈ认为，式（２） 使得顶点口。的法矢过于依赖点Ｆ；的与ｌ－ｒｉｎｇ的边 界点之间的拓扑结构，因此提出用各三角形在点ｔ，。 的夹角加权对式（２）进行修正的方法，其计算公 式为
∑ａｔ眠
露露ｉ ２ｉ—＝１Ｊ■｝—一一
（Ｌｊ３，）
崦哦｜｜
￥ｈａｐｅ． Ｆｉｎａｌｌｙ． ｔｈｅ ａｎｉｃｌｅ ｔｅｓｔｓ ａｌｌ ａｌｇｏｒｉｔｈｍ８ ｗｉｔｈ ｒｅｇｕｌａｒ ａｎｄ ｉｒｒｅｇｕｌ盯ｔｒｉａｎｇｕｌａｒ ｍｅｓｈｅｓ ｏｆ ｑｕａｄｒａｔｉｃ ８ｕ—．ａｃｅｓ ｆｏｒ ｅＶａｌｕａｔｉｎｇ ｔｈｅ ａｌｇｏｒｉｔｈｍ’ｓ ａｃｃｕｒａｃｙ ａｎｄ ｓｔａｂｉｌｉｔｙ． Ｅｘｐｅｒｉｍｅｎｔａｌ ｒｅｓｕｌｔｓ ｄｅｍｏｎｓｔｒａｔｅ ｔｈｅ ｉｍｐｍｖｅｄ ａｐｐｒｏａｃｈ ｉ８ ｅｆ艳ｃｔｉｖｅ．
摘 要 为了提高三角网格模型的顶点法矢计算的准确度和稳定性，提出了一种改进的基于三角形形状修正的法 矢估算方法，并首先对具有代表性的５种顶点法矢估算方法进行了分析，通过比较各估算方法在顶角、面积等权重 方面的处理特点及存在的缺陷，提出了一种评价因子对三角形形状质量进行量化，且在理论上给予了证明；然后据 此对顶点法矢估算方法进行了改进；最后利用规则和不规则的二次曲面网格模型进行了实验验证，并以顶点法矢 误差的算术平均值和标准方差来分别评价各种估算方法估算结果的准确度和稳定性。实验结果证明，该新方法较 其他估算方法估算的顶点法矢精度更高，稳定性更好。 关键词形状修正三角网格法矢误差分析 中图法分类号：ＴＰ３９１．７２ 文献标志码：Ａ 文章编号：１００６．８９６１（２０ｌＯ）０１．０１４２－０７
基金项目：国家自然科学基金项目（５０６０５００７）；福建省重大科技项目（２００７Ｈ２０１１）；福建省教育厅科研资助项目（ＪＡ０８０２８） 收稿日期：２００８－０７一０９；改回日期：２００９．Ｏｌ—１６ 第一作者简介：彭育辉（１９７５一）。男。２０００年获南京理工大学车辆工程专业硕士学位，现为福州大学机械工程及自动化学院讲师， 在职博士研究生。主要研究方向为反求工程、快速制造等。Ｅ－ｍａｉｌ：ｐｅｎｇｙｕｈｕｉ＠ｆｚｕ．ｅｄｕ．ｃｎ。 通讯作者：高诚辉。Ｅ－ｍａｉｌ：ｇｃｈ＠ｆｚｕ．ｅｄｕ．ｃｎ
定义４若顶点ｔ，属于点移ｉ的ｌ－ｒｉｎｇ的边界点， 则将点吩与点秽；的连接边矢量记为Ｅ∽方向由点巧 指向点移；。
根据上述定义，三角形ｆ。所在平面的单位法矢
踽＝最暑簧等晶㈩ Ⅳ。可以通过以下公式计算： Ⅳ。＝
｜｜Ｅ“＋２×曰¨＋ｌ ＩＩ—ＩＩ（Ｊ；＋：一ｚ；）×（工，＋．一工ｒ）０、１ ７ 其中，工；，ｚ…，工Ⅲ代表三角形ｔ。的３个顶点的坐标 矢量。 １．２法矢估算方法回顾
３）图３（ｃ）与图３（ｄ）的三角形面积和顶角相 等，如果利用式（５）或式（６）计算，则图３（ｃ）与图３ （ｄ）中的不同形状的三角形对露；的影响是等同的，
万方数据
第ｌ期
彭育辉等：基于形状修正的三角网格模型顶点法矢估算方法
１４５
但也无法修正三角形形状差异对顶点法矢露ｊ的 影响。
式（３）、式（５）、式（６）将顶角作为三角形的形 状因素用于法矢估算方法的修正，但是顶角作为三 角形的一个内角并不能完全体现三角形的形状，这 就使得上述算法在理论上存在一定的缺陷。
Ｋｅｙｗｏｒｄｓ ８ｈａｐｅ ｃｏｒｒｅｃｔｉｏｎ，ｔｒｉａｎｇｕｌａｒ ｍｅ８ｈ，ｖｅｎｅｘ ｎｏｍａｌ，ｅｒｒｏｒ ａｎａｌｙｓｉｓ
Ｏ引 言
三角网格模型是３维空间中由一系列相互连接 的三角形面片组成的一种曲面离散逼近的表达形
式。由于三角形网格比四边形网格更为稳定，更能 灵活反映实际曲面复杂的形貌，因此适用于任意分 布的散乱数据点集，而且使得它在计算机图形学、计 算机视觉、反求工程、快速原型制造等许多领域得到 广泛应用。由于三角网格模型的顶点法矢表达了重
矢计算公式：
ｔ
∑ａ；Ａ。Ｍ
玎ｉ＝—｝—一
（５）
ＩＩ∑叫＾０
方法５… Ｍａｘ认为各三角形在点秽，处的夹角
和连接边长同样影响该三角形法矢对露；的贡献，因
”峨２熹爵当翮 此提出了以下修正公式： 毒’ｆ
ｓ：ｉ：ｎ：ｄ：ｊ＝Ⅳ！：‘：！
．婶（’６）
（ａ）原三角网格
ｑ＋２ （ｂ）顶点％＋：延伸后的三角网格
图２三角网格变形 Ｆｉｇ．２ Ｔｒｉａｎｇｕｌ８ｒ ｍｅ８ｈｅ８ ｗｉｔｈ ｄｉｆｂｒｅｎｔ￥ｈａｐｅ
第１５卷第ｌ期 ２０１０年１月
中国图象图形学报 Ｊｏｕｍａｌ ｏｆ Ｉｍａｇｅ ａｎｄ Ｇｒａｐｈｉｃｓ
Ｖ０１．１５．Ｎｏ．１ Ｊａｎ．２０ｌＯ
基于形状修正的三角网格模型顶点法矢估算方法
彭育辉１’’２’ 高诚辉１’
’（福州大学福建省制造业数字化设计工程研究中心，福州３５０００２）２’（福州大学机械工程及自动化学院，福州３５０１０８）
２’（ｃｏｚｚｅ班矿｜｜Ｉｆ８曲口厅池ｚ Ｅ增ｉｎ卵＾，孵ｎ，“Ａ珊Ｄｍ口ｔ幻ｎ，Ｆｕ她ｏⅡ踟ｉ俐１渺，，五瞄＾ＤⅡ３５０１０８）
Ａｂｓｔｒａｃｔ Ａｎ ｉｍｐ∞ｖｅｄ ａｌｇｏｒｉｔｈｍ ｂａｓｅｄ ｏｎ ｃｏｒｒｅｃｔｉｎｇ ｔｒｉａｎｇｌｅ ８ｈａｐｅ ｉｓ ｐｒｅｓｅｎｔｅｄ ｔ０ ｉｍｐｒｏｖｅ ａｃｃｕｍｃｙ ａｎｄ ８ｔａｂｉｌｉｔｙ ｏｆ
万方数据
第ｌ期
彭育辉等：基于形状修正的三角网格模型顶点法矢估算方法
１４３
要的微分几何信息，因此在曲面重构…、曲面分 割¨１、模型光顺口１等方面经常把它作为已知前提， 且顶点法矢计算的准确与否严重影响着后续的计算 结果。对三角网格模型的顶点法矢进行估算，尽管 Ｇｏｕｒａｕｄ、Ｔｈｕ瑚ｅｒ、Ｔａｕｂｉｎ、Ｍａｘ以及神会存等人先后 提出了不同的估算方法Ｈ。８－，但各种方法的理论依 据、权重法则都不相同。Ｊｉｎ等人对早期的３种估算 方法进行了比较一Ｊ，却未能系统地对各方法的权重 特点进行分析比较；姜寿山等人基于数学推理提出 了判别３维多面体顶点法矢计算方法优劣的准 则¨…，但是其理论却基于顶点邻接三角面片是具有 外接球的四面体，在实际应用中具有较大的局限性。 因此，需对各种三角网格模型的顶点法矢估算算法的 特点进行系统地分析和比较，以期进行改进，即提高 离散点法矢计算的准确度和稳定性显得十分必要。
当前，具有代表性的三角网格模型的顶点法矢 估算方法有Ｇｏｕｒａｕｄ、Ｔｈｕ珊ｅｒ、Ｔａｕｂｉｎ、Ｍａｘ和神会 存等人提出的５种方法。
方法ｌ【４ ３ 它是Ｇｏｕｒａｕｄ于１９７１年提出的三角 网格模型顶点法矢估算方法，其基本思想是认为顶 点秽ｉ的１一ｒｉｎｇ三角形各法矢对于顶点口；的法矢肛；的 贡献是相等的，其计算公式为
ｃｏｍｐｕｔｉｎｇ ｖｅｒｔｅｘ ｎｏ瑚ａｌ ｏｆ ｔｒｉａｎｇｕｌａｒ ｍｅｓｈｅｓ． Ｆｉ玛ｄｙ， ｆｉｖｅ ｒｅｐｒｅ８ｅｎｔａｔｉｏｎａｌ ａｌｇｏｒｉｔｈｍｓ ａｒｅ ａｎａｌｙｚｅｄ ｂｙ ｃｏｍｐａｒｉｎｇ ｔｈｅｉｒ ｗｅｉｇｈｔｉｎｇ ｃｈ８ｍｃｔｅｒｉ８ｔｉｃ８． Ｆｏｌｌｏｗｉｎｇ ｔｈａｔ， ａ ｑｕａｎｔｉｔａｔｉｖｅ ａ８８ｅ８Ｂｍｅｎｔ ｐａｒａｍｅｔｅｒ ｔｏ ｅ８ｔｉｍａｔｅ ｔｈｅ ｑｕａｌｉｔｙ ｏｆ ｔｒｉａｎｇｌｅ Ｂｈａｐｅ ｉ８ ｐｒｏｐｏｓｅｄ ａｎｄ ｄｅｍｏｎｓｔｒａｔｅｄ ｉｎ ｔｈｅｏｒｙ， ａｎｄ ｔｈｅｎ ｗｅ ｐｕｔ ｆｏｒｗａｒｄ ａｎ ｉｍｐｒｏｖｅｄ ｅｑｕａｔｉｏｎ ｔｏ ａｍｅｎｄ ｔｈｅ ｉｎｎｕｅｎｃｅ ｏｆ ｔｒｉａｎｇｌｅ
万方数据
中国图象图形学报
第１５卷
方法３‘６ ３ Ｔａｕｂｉｎ考虑了各三角片面积大小
对顶点口。的单位法矢订；的影响，其基本思想是按三
角形的面积对式（２）进行修正，面积越大的三角形，
其对ｎｉ的贡献越大，修正后公式为