计算机研究与发展 ＩＳＳＮ １０００—１２３９／ＣＮ １１—１７７７／ＴＰ Ｊｏｕｒｎａｌ ｏｆ Ｃｏｍｐｕｔｅｒ Ｒｅｓｅａｒｃｈ ａｎｄ Ｄｅｖｅｌｏｐｍｅｎｔ ４９（７）：１３７７—１３８７。２０１２ 基于表面及切向属性的点模型骨架提取方法 何志莹 梁晓辉 赵沁平 （虚拟现实技术与系统国家重点实验室 北京 １００１９１） （北京航空航天大学计算机学院北京 １００１９１） （ｈｅｚｈｙ＠ｖｒｌａｂ．ｂｕａａ．ｅｄｕ．ｃｎ） Ｓｋｅｌｅｔｏｎ Ｅｘｔｒａｃｔｉｏｎ Ａｐｐｒｏａｃｈ Ｂａｓｅｄ ｏｎ ｔｈｅ Ａｔｔｒｉｂｕｔｅｓ ｏｆ Ｓｕｒｆａｃｅ ａｎｄ Ｔａｎｇｅｎｃｙ ｆＯｒ Ｐｏｉｎｔ Ｍｏｄｅｌｓ Ｈｅ Ｚｈｉｙｉｎｇ，Ｌｉａｎｇ Ｘｉａｏｈｕｉ，ａｎｄ Ｚｈａｏ Ｑｉｎｐｉｎｇ （Ｓｔａｔｅ Ｋｅｙ Ｌａｂｏｒａｔｏｒｙ ｏｆ Ｖｉｒｔｕａｌ Ｒｅａｌｉｔｙ Ｔｅｃｈｎｏｌｏｇｙ ａｎｄ Ｓｙｓｔｅｍｓ，Ｂｅｉｊｉｎｇ １００１９１） （Ｓｃｈｏｏｌ ｏｆ Ｃｏｍｐｕｔｅｒ Ｓｃｉｅｎｃｅ ａｎｄ Ｅｎｇｉｎｅｅｒｉｎｇ，Ｂｅｉｈａｎｇ Ｕｎｉｖｅｒｓｉｔｙ，Ｂｅｉｊｉｎｇ １００１９１） Ａｂｓｔｒａｃｔ Ｆｏｒ ｔｈｅ ｌｉｍｉｔａｔｉｏｎｓ ｏｆ ｓｋｅｌｅｔｏｎ ｅｘｔｒａｃｔｉｏｎ ｏｎ ｄｉｓｃｒｅｔｅ ｐｏｉｎｔ ｍｏｄｅｌｓ ａｎｄ ｌＯＷ—ｒｅｓｏｌｕｔｉｏｎ ｍｏｄｅｌｓ，ｔｈｉｓ ｐａｐｅｒ ｐｒｅｓｅｎｔｓ ａ ｎｏｖｅｌ ｓｋｅｌｅｔｏｎ ｅｘｔｒａｃｔｉｏｎ ａｐｐｒｏａｃｈ ｆｏｒ ｐｏｉｎｔ ｍｏｄｅｌｓ ｂａｓｅｄ ｏｎ ｔｈｅ ａｔｔｒｉｂｕｔｅｓ ｏｆ ｓｕｒｆａｃｅ ａｎｄ ｔａｎｇｅｎｃｙ．Ｆｉｒｓｔｌｙ，ｔｈｅ ｄｅｆｉｎｉｔｉｏｎ ａｎｄ ｔｈｅ ｃａｌｃｕｌａｔｉｎｇ ｍｅｔｈｏｄ ｏｆ ｔｈｅ ｔＷＯ ａｔｔｒｉｂｕｔｅｓ ａｒｅ ｇｉｖｅｎ．Ａｎｄ ｔｈｅｎ，ｇｅｏｍｅｔｒｙ ｃｏｎｔｒａｃｔｉｏｎ ｉｓ ｄｏｎｅ ｂｙ ｓｕｒｆａｃｅ ｓｍｏｏｔｈ ｃｏｎｔｒａｃｔｉｏｎ ａｎｄ ｓｋｅｌｅｔｏｎ ａｔｔｒａｃｔｉｏｎ．Ｆｉｎａｌｌｙ，ｔｈｅ ｃｅｎｔｅｒ ｐｏｉｎｔｓ ａｆｔｅｒ ｉｔｅｒａｔｉｏｎ ｃｏｎｔｒａｃｔｉｏｎ ａｒｅ ｃｏｎｎｅｃｔｅｄ，ａｎｄ ｔｈｅ ｓｋｅｌｅｔｏｎ ｏｆ ｔｈｅ ｍｏｄｅｌ ｉＳ ｏｂｔａｉｎｅｄ．Ｅｘｐｅｒｉｍｅｎｔ ｒｅｓｕｌｔｓ ｓｈｏｗ ｔｈａｔ ｔｈｅ ｓｋｅｌｅｔｏｎ ｅｘｔｒａｃｔｅｄ ｆｒｏｍ ｔｈｉｓ ａｐｐｒｏａｃｈ ｃｏｕｌｄ ｅｘｐｒｅｓｓ ｔｈｅ ｇｅｏｍｅｔｒｙ ａｎｄ ｔｏｐｏｌｏｇｙ ｏｆ ｏｒｉｇｉｎａｌ ｍｏｄｅｌ ｂｅｔｔｅｒ．Ｅｖｅｎ ｉｆ ｔｈｅ ｍｏｄｅｌ ｌａｃｋｓ ｃｏｎｎｅｃｔｉｏｎ ｉｎｆｏｒｍａｔｉｏｎ ａｎｄ ｉｎ ｌｏｗ—ｒｅｓｏｌｕｔｉｏｎ，ｔｈｅ ａｐｐｒｏａｃｈ ｃｏｕｌｄ ａｌｓｏ ｇｅｔ ｇｏｏｄ ｓｋｅｌｅｔｏｎ． Ｋｅｙ ｗｏｒｄｓ ｐｏｉｎｔ ｍｏｄｅｌ；ｓｋｅｌｅｔｏｎ ｅｘｔｒａｃｔｉｏｎ；ｌｏｗ—ｒｅｓｏｌｕｔｉｏｎ；ｇｅｏｍｅｔｒｙ ｃｏｎｔｒａｃｔｉｏｎ；ＡＳＴ 摘要针对目前在离散点云模型以及低分辨率模型上提取骨架算法存在的局限性，提出一种基于表面 及切向属性（ａｔｔｒｉｂｕｔｅｓ ｏｆ ｓｕｒｆａｃｅ ａｎｄ ｔａｎｇｅｎｃｙ，ＡＳＴ）的新方法．首先给出两个属性定义及其计算方 式．然后基于上述属性通过表面光滑收缩和骨架吸引的双重作用达到模型的几何收缩，连接迭代收缩完 成后得到的中心点，从而得到模型的骨架．实验表明：该方法得到的骨架能较好地表达原始模型的几何 特征和拓扑结构，在缺少连接信息和低分辨率的情况下也能获得较好的骨架提取效果． 关键词点模型；骨架提取；低分辨率；几何收缩；ＡＳＴ 中图法分类号ＴＰ３９１ 线骨架，简称骨架，能够简洁有效地表示物体的 所有最大相切球的中心集 ，类似于中轴（ｍｅｄｉａｌ 基本几何特征，在许多领域有广泛的应用，如数据分 ａｘｉｓ）．该定义使得骨架对边界非常敏感，边缘一个 析、动画、变形、形状匹配等．因此，骨架的提取算法 微小的变化会导致骨架较大的变化． 是图形学领域的一个研究热点． 针对网格模型或点模型的骨架提取已开展了许 骨架没有一个严格的定义，文献［１］将其定义为 多研究工作 。 ，其中大多数研究结合网格模型进行 收稿日期：２０１０一¨Ｏ４；修回日期：２０１１—０９ １３ 基金项目：国家自然科学基金项目（６１１７０１８６，６０８７３１５９） 通信作者：梁晓辉（１ｘｈ＠ｖｒｌａｂ．ｂｕａａ．ｅｄｕ．ｃｎ） 处理．文献［５—７］给出了对闭合多边形网格模型的骨 架提取方法，在此方面研究工作『８］基于连接关系构 造拉普拉斯矩阵，通过在网格模型微分域的操作进 行几何收缩，取得较好的提取效果，但是该方法只适 用于具有流形连通性的闭合网格模型．另一方面，该 方法虽然对模型的分辨率不敏感，但是在处理低分 辨率（ｉｂ于５ ０００个顶点）的模型时不能得到好的骨 架提取效果． 由于点模型具有数据结构简单灵活的特点，近 年来对其研究日益受到关注．围绕骨架的提取，目前 常用的可直接处理离散模型的方法口 。。。有细化和 边界扩散 ］、距离场方法ｌｌ１ 、广义场函数方 法［１４－１ ５ 等．但是这些方法主要是基于体数据，需要清 楚地知道模型的内部信息，不适用于表面点云模型． 可直接用于表面点云模型处理的方法主要是几 何方法，如Ｖｏｒｏｎｏｉ ｄｉａｇｒａｍ＿】 ］通过提取Ｖｏｒｏｎｏｉ 图内部的边和面得到近似的中值面，修剪之后得到 线骨架．该方法由于基于中值面，通常对噪音敏感， 可能提取出大量不需要的枝节，且计算量较大 ］．目 前常用的Ｒｅｅｂ—ｇｒａｐｈ—ｂａｓｅｄｌ１ 。。 方法将函数值相同 且在同一个连通分量上的点聚类得到骨架．该方法 高度依赖于选取的函数，得到的骨架通常对噪音敏 感，且效果不佳，不能很好地表达模型的几何特征和 拓扑结构．文献Ｅ１９Ｇ提出了一种新颖的针对点模型 的旋转对称轴（ＲＯＳＡ）概念，通过递归的平面切割 和本地ＲＯＳＡ建立从不完整的点数据中提取骨架， 并对非圆柱形的关节区域进行检测．该方法由于只 考虑切平面上的点对骨架点位置的影响，在模型的 形状上具有一定的制约，只适用于近圆柱形模型．最 近，文献Ｅ２ｏ］对文献Ｅ８］方法进行了扩展，在点模型 上应用拉普拉斯矩阵进行骨架提取．但是该方法仍 然需要通过Ｄｅｌａｕｎａｙ三角化构建局部的连接关系， 从而得到拉普拉斯矩阵，在本质上仍然是用的面模 型的方法，而没有考虑点模型自身的特点． 有效利用模型的微分域特性，对于骨架提取的 精度会有好的作用，如文献Ｅ８］使用拉普拉斯算子进 行光滑收缩可以有效去除噪音．由于点模型元连接 拓扑信息，虽然可重构三角网格并利用网格模型的 提取方法，但时间开销大且会带来误差，如何直接在 离散点模型上利用微分几何的方法进行骨架提取是 一个问题．另外，原始点模型数据量庞大，在许多需 要实时应用的领域会用到多分辨率点模型，如实时 动画、移动终端上传输和绘制【２ 等．而其中低分辨 率点模型较难还原原始模型，且由于其丢失大量信 计算机研究与发展２０１２，４９（７） 息，在低分辨率模型上提取骨架通常得到的效果不 佳，如文献Ｅ８］要求模型需多于５ ０００个顶点，以保 证能够提供足够的信息提取骨架．因此，如何在低分 辨率下得到保持原始模型基本几何特征和拓扑结构 的骨架也是一个研究问题． 针对以上问题，本文提出一种在缺少连接信息 和低分辨率的情况下也能得到较好骨架效果的方 法．首先根据模型的表面性质和骨架提取的特性，给 出模型表面属性和切向属性两个概念．为了方便表 述，后文中也用ＡＳＴ（ａｔｔｒｉｂｕｔｅｓ ｏｆ ｓｕｒｆａｃｅ ａｎｄ ｔａｎｇｅｎｅｙ）来简称．然后，通过这两个属性控制模型 的几何收缩，从而尽可能保持住模型的表面特性，并 向理想骨架逼近． 本方法在离散点模型下，通过根据表面邻域直 接获得的表面属性的作用，可以得到在微分域中进 行拉普拉斯光滑收缩的效果，即得到近似于文献Ｅ８］ 的收缩效果而不需要重建连接关系和构建拉普拉斯 矩阵．进一步加入测地线切向邻域的吸引，迭代计 算，逐渐逼近骨架．通过表面和切向两个属性的共同 作用可以保证骨架提取时的足够信息，从而在低分 辨率下也能获得好的骨架． 实验表明，本方法能较好地保持原始模型的几 何特征和拓扑结构，对噪音不敏感．且适用于多分辨 率点模型的骨架提取，在低分辨率（ｉｂ于５ ０００个顶 点）的模型下同样具有较好的骨架提取效果． １基于ＡＳＴ的骨架提取方法 本节给出基于ＡＳＴ进行骨架提取的核心思想． 首先给出表面邻域和测地线切向邻域的定义，用这 两个邻域作为基础进行计算．然后，通过相应的函数 变换得到表面属性和切向属性．最后，在两个属性的 共同作用下进行迭代几何收缩，从而得到骨架．下面 进行详细叙述． １．１表面邻域和测地线切向邻域 根据模型曲面特性和骨架提取之间的关系，本 文提出通过表面邻域和测地线切向邻域来表示某点 Ｐ 在该模型中所能代表的基本信息． １）表面邻域．点模型是由离散的点集组成，任 一离散点在模型中该点所在的曲面上的信息（如各 种微分属性）可以通过其周围邻域点来得到．本文将 其定义为表面邻域的概念． Ｎｅｉ（ｐ ）：某点ｐ 的表面邻域Ｎｅｉ（Ｐ ）即距离该 点最近的 个邻域点．如式（１）所示： 何志莹等：基于表面及切向属性的点模型骨架提取方法 Ｎｅｉ（ｐ ）一｛ＰＮ ，ＰＮ。，…，ＰＮ ｝， （１） ＡＳ ＝＝＝ ．（Ｎｅｉ（ｐ。））； （４） 其中，集合中的元素ｐ ．∈ａｒｇｍｉｎ， ＩＩＰ 一ｐ ＪＩ，Ｊ一１， ２，…， ，Ｐ ∈ｐｏ一｛ＰＮ ，ｐＮ，，…，ＰＮ…）．式（１）中 ０ 表示点模型包含的所有点．范数指的是２范数，下文 中如未说明都指的是２范数． ＡＴｐ．一ｆＡＴ（Ｔａｎ（ｐ ））． （５） 表面邻域Ｎｅｉ（Ｐ ）通过函数变换－厂 得到的表 面属性可以提供一个保持几何形状同时进行光滑收 缩的力，得到近似于在微分域中进行拉普拉斯光滑 ２）测地线切向邻域．表面邻域不足以保证低分 辨率下骨架的有效提取．本文进一步提出测地线切 收缩的效果．测地线切向邻域Ｔａｎ（Ｐ ）通过函数变 换－厂Ａ 得到的切向属性可以提供一个吸引的力，将 点吸引到来．下面详细叙述属性函数的计算 向邻域的概念，通过切向邻域可以提供邻域点与骨 架之间的约束关系． 首先给出测地线距离的概念．曲面上两点问的 测地线距离，是指在曲面上两点之间的最短距离．假 设基准点是ｐ ，则定义某点ｐ 的测地线距离 ｇ（ｐ ）为点ｐ 与Ｐ ａ之间的测地线距离．如式（２） 所示： ｇ（ｐ ）一ｇｅｏｄｅｓｉｃ（ｐ ，Ｐｈ ｄ）． （２） Ｔａｎ（ｐ ）：某点ｐ 的测地线切向邻域 ｎ（Ｐ ） 即与Ｐ 的测地线距离相同且在同一个连通分量的 所有点的集合．如式（３）所示： Ｔａｎ（ｐ ）一｛Ｐ＿ｒｒ ｆｇ（Ｐ ）一ｇ（Ｐ ），Ｐ＿ｒｒ∈Ｃ ）．（３） 式（３）中Ｃ 表示点Ｐ 所在的连通分量，ｒ一１， ２，…，ｍ，ｍ是测地线切向邻域点的个数． 以轮胎模型为例，如图１所示，顶部的点表示基 准点ｐｎ ａ．模型上距离基准点测地线距离与ｇ（Ｐ ） 相同的点如图中左右两边的空心点所示．但右边的 空心点与点ｐ 不属于一个连通分量，因此Ｔａｎ（ｐ ） 即图中左边空心点所示的点集． Ｐｈｅａｄ ｌ’ｈｅ ｓｅｔ ｏｆ ｌｅｆｔ ｈｏｌｌｏｗ ｐｏｉｎｔｓ ｉｓ ｔｈｅ ｇｅｏｄｅｓｉｃ ｔａｎｇｅｎｃｙ ｎｅｉｇｈｂｏｒｈｏｏｄ ｏｆ Ｐ ． Ｆｉｇ．１ Ｓｃｈｅｍａｔｉｃ ｄｉａｇｒａｍ ｏｆ Ｔａｎ（ｐ ）． 图１点Ｐ 的测地线切向邻域Ｔａｎ（ｐ ）示意图 １．２表面属性和切向属性（ＡＳＴ） 表面邻域包含了曲面上的基本信息，测地线切 向邻域含有邻域点之间以及邻域点与骨架之间的关 系．通过对这两个邻域进行特定的函数变换，可以得 到相应的表面属性ＡＳ和切向属性ＡＴ．如式（４）（５） 所示： 方法． １）表面属性函数 ．文献［８］通过求解拉普拉 斯方程Ｌ Ｖ，一０进行顶点收缩，达到了较好的效果． 但在点模型上构建拉普拉斯矩阵需要重建模型顶点 的连接关系．因此本文给出一种在离散点模型下可 以直接得到近似收缩效果的函数． 通过拉普拉斯矩阵Ｌ乘以笛卡儿坐标Ｖ可以 得到微分坐标 ，而微分坐标和曲率法线之间有如 下关系ｌ８］： 一ＬＶ一一４Ａｋｎ， （６） 其中Ａ表示邻域点组成的环形面积，ｋ表示曲率，，ｌ 表示法线．因此文献［８］的本质是使表面的曲率尽量 向０收缩． 要在离散点模型中得到相同的几何效果，本文 给出了如下的方法： 寻找一个平面Ｈ，使得点Ｐ 收缩后的点 （ ∈ Ｈ）与其邻域点Ｎｅｉ（Ｐ ）在某一方向口（口是Ｈ的法 线）上的差的平方和最小，如式（７）（８）所示： ＾ （Ｍ （ｐ ））一∑（（ｎ，Ｐ ，）一（口，ｐ：）） ； Ｊ一１ （７） ｍｉｎ（ｆｎＳ－ｍｂ（Ｎ ｉ（ｐ ）））． （８） 要使点ｐ 收缩后的点ｐ：与其邻域点Ｎｅｉ（ｐ ） 尽量处于一个平面，也可进一步简化为用距离表示， 使其到邻域点的距离平方和最小，如式（９）（１０） 所示： －厂 （ （ｐ ））一∑（ＩＩ ｐ ，一ｐ ）； （９） 一１ ｍｉｎ（ｆＡＳ＿ｄ（Ｎｅｉ（ｐ ）））． （１０） 为了直观说明上述两种情况，图２给出了特殊 情况下的示意图． 当上述两种表面属性函数值最小时，都能提供 一个保持几何形状同时进行收缩的力．因为＾ ， 考虑到了方向的影响，效果较好．而＿厂Ａｓａ是＾ － 的 简化方式，只考虑了距离的影响．在后续的实验中可 以发现，＾ 适用于模型结构简单，模型分支在一个 （ａ）厂Ａｓ＿ｍｌ （ｂ），Ａｓ＿ｄ ｐ ｉｓ ｔｈｅ ｐｏｉｎｔ ａｆｔｅｒ Ｐｉ ｃｏｎｔｒａｃｔｉｎｇ．Ｔｈｅ ｈｏｌｌｏｗ ｐｏｉｎｔｓ ａｒｅ ｓｕｒｆａｃｅ ｎｅｉｇｈｂｏｒｈｏｏｄ Ｎｅｉ（Ｐｉ）． Ｆｉｇ．２ Ｓｃｈｅｍａｔｉｃ ｄｉａｇｒａｍ ｏｆ ｆ ． 图２表面属性函数示意图 方向上的模型． ２）切向属性函数＾ ．＾ 用于提供一个测地线 切向邻域对收缩点吸引的力，最终吸引到骨架上．因 此，本文用Ｔａｎ（ｐ ）的中心点与收缩后的点ｐ：的距 离平方值最小来表示．如式（１１）（１２）所示：令 ｍ ，＾ （Ｔａｎ（ｐ ））一ＩＩＰ ｉ（∑Ｐｒ一１ ）／ ＩＩ２；（１１） ａｒｉｎ（．厂＾Ｔ（Ｔａｎ（Ｐ ）））． （１２） 求解Ｔａｎ（ｐ ）的最理想方式是沿着垂直于骨架 的方向切割，从而得到的一圈切向邻域．但实际上骨 架是未知的，因此只能用近似骨架的方向来代替求 解．文献［１９］沿着表面点的法线方向切割，但只适用 于近圆柱形物体，对于特征细节丰富的模型就会得 到错误的结果．Ｒｅｅｂ图方法通过定义一个函数，将 具有相同函数值且位于同一连通分量上的点归为一 类，这样也可以得到切向邻域，但是很大程度取决于 定义的函数．如高度函数，适用于在高度上变化的物 体，在与高度垂直方向上有分支的物体，则会得到错 误的结果． 本文通过测地线求解切向邻域．将与某个指定 基准点测地线距离相同且在一个连通分量的点归为 一类，从而得到切向邻域．相对于高度函数来说测地 线函数可以得到相对准确的切向邻域．通过该切向 邻域得到的中心点对表面点的吸引进行收缩．每次 收缩后重新计算测地线，得到新的 （Ｐ ）．第１ 次计算出来的切向邻域虽然与理想骨架方向的切向 邻域相差较多，但在收缩过程中渐渐调整，将会逐渐 逼近骨架方向的切向邻域，从而逼近骨架． １．３基于ＡＳＴ的几何收缩原理 骨架提取的一个关键要素是要保持原始模型的 几何特征和拓扑结构，对噪音不敏感．通过上述表面 属性的作用可以得到近似拉普拉斯光滑收缩的效 果，从而保持模型基本结构并对噪音不敏感．而在低 分辨率下提取骨架的关键是得到足够的信息来保证 计算机研究与发展２０１２，４９（７） 骨架提取的效果．ＡＳＴ方法通过表面属性和切向属 性的共同作用，迭代逼近骨架，从而保证在低分辨率 下也可以得到足够的信息进行骨架提取． 表面属性和切向属性共同作用得到的能量场如 式（１３）所示． Ｅ ８ｒｇ 一训ｓ×ＡＳＰ＋叫Ｔ×ＡＴＰ； （１３） ．．训 一Ｚｓ×Ｗｓｔ； （１４） 叫 一ＺＴ×叫ｆＴ； （１５） 其中叫 和叫 是权值，表示各属性的影响因子，每 次收缩后通过式（１４）（１５）进行更新．ｚ 和ｚ 表示每 次迭代收缩后，叫 和叫 的变化比例因子． 将（４）（５）（７）（１１）代入式（１３），可得 Ｅｎｅｒｇｙ 。 ＆ 一叫 ×（∑（（口，Ｐ ，）一＜ｎ，ｐ：＞） ）＋ Ｊ＝１ Ｗ ×（ 一（∑Ｐ ）／ｍ ； （１６） ｒ＝１ Ｐ：一ａｒｇｍｉｎＰ：（Ｅｎｅｒｇｙ １。＆ｔ）． （１７） 根据上文分析，要达到几何收缩的效果需要满 足表面属性和切向属性共同作用得到的能量场最 小．即已知点Ｐ ，Ｎｅｉ（ｐ ）和Ｔａｎ（ｐ ），求满足式（１７） 的收缩后的点Ｐ：． 参考文献［２２］的计算最优化问题的方法，本文 将其分成能量场和矢量场进行计算．主要分为如下 两步： 步骤１．从所有的方向中找出一个最优的方向 ，ｌｂｅｓｔ． 这里最优的方向，就是经过点Ｐ 且能量函数最 小时的方向．即式（１６）中ｐ：用Ｐ 表示时能量函数 最小时的方向ａ．能量函数最小时通常是法线方向， 本文通过协方差分析的方法［２３］根据邻域求点Ｐ 的 法线，将其作为ｎ ． 步骤２．选出在最优方向上能量最小时的点Ｐ：． 将上步中求出的ｎ 代人式（１７），求解出Ｐ：． 当模型较为简单时， 可以采用厂 进行简 化计算，则此时的能量场值如式（１８）所示．收缩后的 点ｐ：即满足（１９）时的值． Ｅｎｅｒｇｙ ＆ 一 Ｘ（∑（１ｊ Ｐ ，一ｐ，ｌ Ｉ））＋ －ｒ×（ 一（ ｐ ）／ｍ ）； （１８） Ｐ；一ａｒｇｍｉｎｐ：（Ｅｎｅｒｇｙｄ＆ｔ）． （１９） ２算法实现 根据第１节的理论基础，本节给出具体实现的 何志莹等：基于表面及切向属性的点模型骨架提取方法 算法细节．为了方便叙述，后文中出现的切向邻域即 指测地线切向邻域． 图３是算法的整体流程图．输入的点模型只需 切向邻域后迭代进行收缩，当收缩至切向邻域的直 径小于某一阈值时，或指定收缩完毕时，结束迭代． 此时得到的切向邻域中心点即可认为在骨架上，连 具有顶点位置信息即可．通过计算得到表面邻域和 接中心点，从而得到骨架．下面分别进行详述． Ｆｉｇ．３ Ｔｈｅ ｐｒｏｃｅｓｓ ｏｆ ＡＳＴ ａｌｇｏｒｉｔｈｍ 图３算法流程图 ２．１表面邻域和法线计算 步骤１．找出在ｚ方向上最大的点Ｐ…，其法线 每次收缩后，模型整体位置都会发生变化，表面 为ｎ…． 邻域和法线也会发生变化．因此，需要在每次迭代收 步骤２．判断，ｌ…与（０，０，１）的点积，如果小于 缩后进行邻域和法线信息的更新．低分辨率模型收 ０，说明两者方向相反，则调整，ｌ 为一 ． 缩时，点的位置会发生较大变化，实时进行更新有助 步骤３．对ｐ 的表面邻域点进行法线调整．如 于进行正确的骨架收缩． 果其表面邻域点法线与，ｌ…的点积小于０，则调整该 目前已经有较多成熟的点模型邻域和法线求解 邻域点法线方向． 方法．本文通过构建ｋｄｔｒｅｅ来求解邻域．法线则通 步骤４．循环遍历邻域点的邻域点，调整其法线 过对邻域进行协方差分析ｌ＿２ ３＿得到．根据邻域构建的 方向，直到遍历所有点． 协方差矩阵的最小特征值对应的特征向量即法线信 ２．２测地线距离计算 息．本文采用文献Ｅｅ４］中所用的协方差矩阵，该矩阵 曲面上两点间的测地线距离，是指在曲面上两 还考虑了邻域点远近带来的影响． 点之间的最短距离．这就决定了测地线和表面的形 通过协方差分析得到的法线信息可能发生方向 状相关．点模型不具备连接拓扑关系，因而不能像网 相反的情况．因此，需要对所有点的法线方向进行调 格模型那样根据边来求解测地线．本文提出一种根 整．主要有如下几步： 据邻域关系求解测地线的方法，具体步骤如下： 步骤１．将基准点Ｐ ａ设为在某一坐标轴方向 上的最大或最小值，即某一方向上的最值． 步骤２．基准点及其表面邻域点的测地线距离 ｇ的计算． ｇｈｅａｄ一０； （２Ｏ） ｇ（Ｎｅｉ （Ｐｈ ｄ））一 ｌ ｌＮ （ｐｈｅａｄ）一Ｐｈｅ ｄ ｌｌ，Ｊ＝＝＝１，２，…，ｎ．（２１） 如式（２０）（２１）所示，基准点的测地线设为０，其一环 邻域内的点为两点间的欧氏距离．式中Ｎｅｉ，（ｐ ａ） 表示 的第Ｊ个邻域点． 步骤３．循环遍历邻域点的邻域点，根据式（２２） 计算测地线距离，直到遍历所有点． ｇ（Ｎｅｉ （ｐ ））一ｇ（ｐ ）＋ｌｌ ＮｅｉＪ（ｐ ）一Ｐ ｌｌ， Ｊ＝＝＝１，２，… ． （２２） 本节将基准点Ｐ 设为某一方向上的最值，不 同的Ｐ 会产生不同的初始测地线切向邻域．但是， 本节方法是一个迭代收缩的过程，即在收缩过程中 逐步调整测地线切向邻域，因而当收缩到一个薄片 时，使用不同的ｐｈｅａｄ也能得到近似的切向邻域． ２．３分带（ｂａｎｄ）和连通性检测 分带是指将具有相同测地线距离或在某一测地 线距离范围内的点归为一个带（ｂａｎｄ）．然而同一个 ｂａｎｄ可能包含好几个部件，因而还需要进行连通分 量检测．点云因为不具有连接关系，无法通过连接关 系得到模型间的连通性．本文用点之间的邻域关系 来代替连接关系进行计算．假设是对ｂａｎｄ 里的点 进行连通分量检测，主要过程如下： 步骤１．将ｂａｎｄ 的初始点设为遍历的初始点 ｂｅｇｉｎ ｐｏｉｎｔ． 步骤２．建立一个新的连通分量ｃ，从ｂｅｇｉｎ ｐｏｉｎｔ开始，遍历其表面邻域点，将其中属于ｂａｎｄ 且未分配到连通分量中的点Ｐ放入连通分量Ｃ中； 继续遍历ｐ的表面邻域点，直到所有未分配的表面 邻域点都不在ｂａｎｄ 内为止． 步骤３．如果ｂａｎｄ 内还有点没有分人连通分 量，则从未分配的点中任选一个点设为ｂｅｇｉｎ ｐｏｉｎｔ， 并回到步骤２．否则，结束程序． 上述过程在对点的遍历时应该采用广度优先搜 索的方法，先遍历某点的表面邻域点，再遍历邻域的 邻域，从而保证距离从近至远的遍历顺序． 通过分带和连通性检测，得到了具有相同测地 线距离或者在相同测地线距离范围内的且在同一个 连通分量的点集，即切向邻域Ｔａｎ（ｐ ）． 图４给出了测地线的效果图．图４（ａ）的基准点 在鼻子部位．用测地线控制颜色的变化，距离越近颜 计算机研究与发展２０１２，４９（７） 色越深．图４（ｂ）是得到的切向邻域和中心点．其基 准点在尾巴处，图中的圈即为切向邻域，切向邻域中 间的点表示每个切向邻域的中心点． （ａｊ Ｕｓｅ ｔｈｅ ｃｏｌｏｒ ｃｈａｎｇｅｓ ｔｏ 【ｂ）Ｔｈｅ ｔａｎｇｅｎｃｙ ｎｅｉｇｈｂｏｒｈｏｏｄｓ ｅｘｐｒｅｓｓ ｔｈｅ ｃｈａｎｇｅｓ ｏｆ ａｎｄ ｔｈｅｉｒ ｃｅｎｔｅｒｓ ｏｂｔａｉｎｅｄ ｇｅｏｄｅｓｉｃ ｄｉｓｔａｎｃｅ ｂｙ ｇｅｏｄｅｓｉｃ Ｆｉｇ．４ Ｔｈｅ ｒｅｓｕｌｔｓ ｏｆ ｇｅｏｄｅｓｉｃ． 图４测地线效果展示 ２．４几何收缩和骨架的获取 通过以上步骤，可以得到某点ｐ 的表面邻域 Ｎｅｉ（ｐ ）和切向邻域Ｔａｎ（ｐ ），下面即可通过第１．３ 节所述方法进行几何收缩，根据式（１７）或（１９）可以 求得能量场值最小时的点Ｐ：，从而得到收缩后的 模型． 模型收缩的极限即将所有的表面点都吸引到理 想骨架上．这时切向邻域的中心点可以近似地表示 骨架点．因此，收缩完毕后，连接中心点即得到模型 的骨架． 得到中心点之后，可以进行分段操作．主要步骤 如下： 步骤１．为ｂａｎｄ。的每个中心点创建一个段厂， 设ｉ一１． 步骤２．遍历ｂａｎｄ 的每个中心点．每获得一个 中心点，就与目前所有段的最后一个中心点求距离， 将该中心点放入最近的一个段的末尾．当所有段都 分配完时，如果ｂａｎｄ 里还有中心点，则为每个中心 点起一个新的段． 步骤３．设ｉ— ＋１，当ｉ小于ｂａｎｄ的数量时， 回到步骤２；否则，结束程序． ３实验结果及分析 实验环境：在一台配置为ＰｅｎｔｉｕｍＤ ３．４ ＧＨｚ ＣＰＵ，１ ＧＢ内存的ＰＣ机上实现． 为了验证ＡＳＴ算法对低分辨率模型提取骨架 的有效性．本文的低分辨率点模型均采用文献［２４］ 的方法对原始大规模点数据进行简化得到．在下述 实验中，式（１４）（１５）中初始值 ， 孚均设为１，ｚｓ一 ２，Ｚ 一１．８．在表面属性函数． 的选取上，ｍａｌｅ模 １３８６ 计算机研究与发展２０１２，４９（７） ２）与Ｒｅｅｂ图方法的比较．Ｒｅｅｂ图的方法是将 函数值相同的聚类成一个点．高度依赖于函数，往往 会得到不好的效果．如果该函数采用高度函数，则只 可能在与高度平行的方向上准确，如果采用测地线 函数，反映的是表面距离的变化，也不能很好地表示 骨架的变化．本文算法在没进行收缩前的初始切向 邻域中心点就是Ｒｅｅｂ图方法采用测地线得到的中 心点．如图１３（ａ）所示的轮胎模型．图１３（ｂ）是迭代 ［２］ 参 考 文 献 ｌｖｅｒ Ｄ，Ｍｉｎ Ｐ．Ｃｕｒｖｅ－ｓｋｅｌｅｔｏｎ ｐｒｏｐｅｒｔｉｅｓ， ［１］ Ｃｏｒｎｅａ Ｎ Ｄ，Ｓｉａｐｐｌｉｃａｔｉｏｎｓ， ａｎｄ ａｌｇｏｒｉｔｈｍｓ［Ｊ］． ＩＥＥＥ Ｔｒａｎｓ ｏｎ Ｖｉｓｕａｌｉｚａｔｉｏｎ ａｎｄ Ｃｏｍｐｕｔｅｒ Ｇｒａｐｈｉｃｓ，２００７，１３（３）：５３０—５４８ Ｌｉｅｕｔｉｅｒ Ａ．Ａｎｙ ｏｐｅｎ ｂｏｕｎｄｅｄ ｓｕｂｓｅｔ ｏｆ Ｒｎ ｈａｓ ｔｈｃ ｓａｍｅ ｈｏｍｏｔｏｐｙ ｔｙｐｅ ｔｈａｎ ｉｔｓ ｍｅｄｉａｌ ａｘｉｓ ＥＣ］／／Ｐｒｏｃ ｏｆ ｔｈｅ ８ｔｈ ＡＣＭ Ｓｙｍｐ ｏｎ Ｓｏｌｉｄ Ｍｏｄｅｌｉｎｇ ａｎｄ Ａｐｐｌｉｃａｔｉｏｎｓ．Ｎｅｗ Ｙｏｒｋ： ＡＣＭ，２００３：６５－７５ 收缩完成后得到的骨架点和原始模型的对比图．可 以看出经过ＡＳＴ收缩，我们的方法得到了较好的骨 架．而Ｒｅｅｂ图方法得到的骨架点不能很好地反映 模型的几何形状． （ａ）Ｒｅｅｂ ｇｒａｐｈ ｍｅｔｈｏｄ （ｂ）ＡＳＴ ｍｅｔｈｏｄ Ｔｈｅ ｔｏｐ ｐｏｉｎｔ ｉｓ ｔｈｅ ｂｅｎｃｈｍａｒｋ． Ｆｉｇ．１ ３ Ｃｏｍｐａｒｉｓｏｎ ｂｅｔｗｅｅｎ Ｒｅｅｂ ｇｒａｐｈ ｍｅｔｈｏｄ ａｎｄ ｏｕｒ ＡｓＴ ｍｅｔｈｏｄ（ｔｏｒｕｓ ｍｏｄｅｌ（４ ８００ ｐｏｉｎｔｓ））． 图１３ Ｒｅｅｂ图方法和ＡＳＴ方法比较（ｔｏｒｕｓ模型（４ ８００ 个点）） ４总结与展望 目前可直接用于表面点云模型骨架提取的算法 得到的骨架效果不佳或是对模型有特殊要求．较好 的提取算法一般都应用在封闭网格模型上，且不适 用于低分辨率下的模型．本文针对这些问题，提出了 基于表面及切向属性（ＡＳＴ）进行几何收缩的骨架 提取方法．首先给出了属性定义、属性函数的求解以 及几何收缩的原理．其次，根据ＡＳＴ原理给出具体 的算法．最后，进行实验分析与比较，验证该方法的 有效性．实验证明，ＡＳＴ方法得到的骨架能较好地 表达原始模型的几何特征和拓扑，具有中心性，对噪 音不敏感，且在低分辨率的模型下也能获得较好的 骨架提取效果． ＡＳＴ方法在每次收缩后需要更新邻域和法线 信息．当处理大规模数据时，计算量较大．下一步工 作考虑对算法进行优化，减少计算量．进一步考虑该 算法在不完全模型上的应用，以及在基于骨架的动 画中的具体应用． ［３］ Ｙｕ Ｙｏｎｇ，Ｍａｏ Ｔｉａｎｌｕ，Ｘｉａ Ｓｈｉｈｏｎｇ，ｅｔ ａ１． Ａ ｐｏｓｅ－ ｉｎｄｅｐｅｎｄｅｎｔ ｍｅｔｈｏｄ ｏｆ ａｎｉｍａｔｉｎｇ ｓｃａｎｎｅｄ ｈｕｍａｎ ｂｏｄｉｅｓ ［ｃ］／／Ｐｒｏｃ ｏｆ Ｉｎｔ Ｃｏｎｆ ｏｎ Ｃｏｍｐｕｔｅｒ Ｇｒａｐｈｉｃｓ．Ｉｓｔａｎｂｕｌ， Ｔｕｒｋｅｙ：ＣＧＩ，２００８：２３２—２３９ Ｅ４］ Ｙｕ Ｙｏｎｇ，Ｗａｎｇ Ｚｈａｏｑｉ，Ｘｉａ Ｓｈｉｈｏｎｇ，ｅｔ ａ１．Ｐｏｓｅ— ｉｎｄｅｐｅｎｄｅｎｔ ｊｏｉｎｔ ｅｘｔｒａｃｔｉｏｎ ｆｒｏｍ ｓｃａｎｎｅｄ ｈｕｍａｎ ｂｏｄｙ［Ｊ］． Ｊｏｕｒｎａｌ ｏｆ Ｃｏｍｐｕｔｅｒ Ｒｅｓｅａｒｃｈ ａｎｄ Ｄｅｖｅｌｏｐｍｅｎｔ，２００８，４５ （７）：１２４９－１２５８（ｉｎ Ｃｈｉｎｅｓｅ） （于勇，王兆其，夏时洪，等．一种姿态无关的人体模型骨骼 提取方法［Ｊ］．计算机研究与发展，２００８，４５（７）：１２４９— １２５８） ［５］ Ｄｅｙ Ｔ Ｋ，Ｓｕｎ Ｊ．Ｄｅｆｉｎｉｎｇ ａｎｄ ｃｏｍｐｕｔｉｎｇ ｃｕｒｖｅ ｓｋｅｌｅｔｏｎｓ ｗｉｔｈ ｍｅｄｉａｌ ｇｅｏｄｅｓｉｃ ｆｕｎｃｔｉｏｎ ＥＣ］／Ｐｒｏｃ ｏｆ ｔｈｅ ４ｔｈ Ｅｕｒｏｇｒａｐｈｉｃｓ Ｓｙｍｐ ｏｎ Ｇｅｏｍｅｔｒｙ Ｐｒｏｃｅｓｓｉｎｇ．Ｎｅｗ Ｙｏｒｋ： ＡＣＭ，２００６：１４３—１５２ ［６］ Ｃｈｕａｎｇ Ｊ Ｈ，Ａｈｕｊａ Ｎ，Ｌｉｎ Ｃ Ｃ，ｅｔ ａ１．Ａ ｐｏｔｅｎｔｉａｌ—ｂａｓｅｄ ｇｅｎｅｒａｌｉｚｅｄ ｃｙｌｉｎｄｅｒ ｒｅｐｒｅｓｅｎｔａｔｉｏｎ［Ｊ］． Ｃｏｍｐｕｔｅｒｓ＆ Ｇｒａｐｈｉｃｓ，２００４，２８（６）：９０７—９１８ ［７］ Ａｕｊａｙ Ｇ，Ｈｅｔｒｏｙ Ｆ，Ｌａｚａｒｕｓ Ｆ，ｅｔ ａ１．Ｈａｒｍｏｎｉｃ ｓｋｅｌｅｔｏｎ ｆｏｒ ｒｅａｌｉｓｔｉｃ ｃｈａｒａｃｔｅｒ ａｎｉｍａｔｉｏｎ［ｃ］／／Ｐｒｏｃ ｏｆ Ｅｕｒｏｇｒａｐｈｉｃｓ／ ＡＣＭ ＳＩＧＧＲＡＰＨ Ｓｙｍｐ ｏｎ Ｃｏｍｐｕｔｅｒ Ａｎｉｍａｔｉｏｎ． Ｎｅｗ Ｙｏｒｋ：ＡＣＭ，２００７：１５１—１６０ ［８］ Ａｕ ＯＫＣ，Ｔａｉ Ｃ Ｌ，Ｃｈｕ Ｈ Ｋ，ｅｔ ａ１．Ｓｋｅｌｅｔｏｎ ｅｘｔｒａｃｔｉｏｎ ｂｙ ｍｅｓｈ ｃｏｎｔｒａｃｔｉｏｎ［Ｊ］．ＡＣＭ Ｔｒａｎｓ ｏｎ Ｇｒａｐｈｉｃｓ：Ｐｒｏｃ ｏｆ ＳＩＧＧＲＡＰＨ ２００８，２００８，２７（３）：＃４４：１—１０ ［９］ Ｚｏｕ Ｗ Ｈ．Ｔｅｃｈｎｉｑｕｅｓ ｆｏｒ ｓｈａｐｅ ｍｏｄｅｌｉｎｇ ｆｒｏｍ ｌａｒｇｅ ｓｃａｌｅ ｐｏｉｎｔ ｃｌｏｕｄｓ［Ｄ］．Ｈａｎｇｚｈｏｎ：Ｚｈｅｊｉａｎｇ Ｕｎｉｖｅｒｓｉｔｙ，２００７（ｉｎ Ｃｈｉｎｅｓｅ） （邹万红．大规模点云模型几何造型技术研究［Ｄ］．杭州：浙 江大学，２００７） ［１Ｏ］ Ｃｏｒｎｅａ Ｎ Ｄ。Ｓｉｌｖｅｒ Ｄ，Ｍｉｎ Ｐ．Ｃｕｒｖｅ—ｓｋｅｌｅｔｏｎ ａｐｐｌｉｃａｔｉｏｎｓ ［Ｒ］． Ｍｉｎｎｅａｐｏｌｉｓ，ＭＮ：Ｐｒｅｓｅｎｔａｔｉｏｎ ｉｎ ｔｈｅ ＩＥＥＥ Ｖｉｓｕａｌｉｚａｔｉｏｎ Ｃｏｎｆ（Ｖｉｓ’Ｏ５），２００５ ［１１］ Ｌｏｈｏｕ Ｃ，Ｂｅｒｔｒａｎｄ Ｇ． Ａ ３Ｄ １ ２－ｓｕｂｉｔｅｒａｔｉｏｎ ｔｈｉｎｎｉｎｇ ａｌｇｏｒｉｔｈｍ ｂａｓｅｄ ｏｎ Ｐ—ｓｉｍｐｌｅ ｐｏｉｎｔｓ［Ｊ］．Ｄｉｓｃｒｅｔｅ Ａｐｐｌｉｅｄ Ｍａｔｂｅｍａｔｉｃｓ，２００４，１３９（１／２／３）：１７１—１９５ ［１２］ Ｗａｎｇ Ｙ Ｓ，Ｌｅｅ Ｔ Ｙ．Ｃｕｒｖｅ ｓｋｅｌｅｔｏｎ ｅｘｔｒａｃｔｉｏｎ ｕｓｉｎｇ ｉｔｅｒａｔｉｖｅ ｌｅａｓｔ ｓｑｕａｒｅｓ ｏｐｔｉｍｉｚａｔｉｏｎ［Ｊ］．ＩＥＥＥ Ｔｒａｎｓ ｏｎ Ｖｉｓｕａｌｉｚａｔｉｏｎ ａｎｄ Ｃｏｍｐｕｔｅｒ Ｇｒａｐｈｉｃｓ，２００８，１４（４）：９２６—９３６ ［１３］ Ｈａｓｓｏｕｎａ Ｍ Ｓ，Ｆａｒａｇ Ａ Ａ．Ｒｏｂｕｓｔ ｃｅｎｔｅｒｌｉｎｅ ｅｘｔｒａｃｔｉｏｎ ｆｒａｍｅｗｏｒｋ ｕｓｉｎｇ ｌｅｖｅｌ ｓｅｔｓ Ｉｔ］／Ｐｒｏｃ ｏｆ ｔｈｅ ２００５ ＩＥＥＥ Ｃｏｍｐｕｔｅｒ Ｓｏｃｉｅｔｙ Ｃｏｎｆ ｏｎ Ｃｏｍｐｕｔｅｒ Ｖｉｓｉｏｎ ａｎｄ Ｐａｔｔｅｒｎ Ｒｅｃｏｇｎｉｔｉｏｎ（ＣＶＰＲ’０５）． Ｗａｓｈｉｎｇｔｏｎ：ＩＥＥＥ Ｃｏｍｐｕｔｅｒ Ｓｏｃｉｅｔｙ，２００５：４５８－４６５ 何志莹等：基于表面及切向属性的点模型骨架提取方法 ［１４３ Ｃｈｕａｎｇ Ｊ Ｈ，Ｔｓａｉ Ｃ Ｈ，Ｋｏ Ｍ Ｃ．Ｓｋｅｌｅｔｏｎｉｚａｔｉｏｎ ｏｆ ｔｈｒｅｅ— ｄｉｍｅｎｓｉｏｎａｌ ｏｂｊｅｃｔ ｕｓｉｎｇ ｇｅｎｅｒａｌｉｚｅｄ ｐｏｔｅｎｔｉａｌ ｆｉｅｌｄ［Ｊ］．ＩＥＥＥ Ｔｒａｎｓ ｏｎ Ｐａｔｔｅｒｎ Ａｎａｌｙｓｉｓ ａｎｄ Ｍａｃｈｉｎｅ Ｉｎｔｅｌｌｉｇｅｎｃｅ，２０００， ２２（１１）：１２４１—１２５１ ｒ１５］Ｃｏｒｎｅａ Ｎ Ｄ，Ｓｉｌｖｅｒ Ｄ，Ｙｕａｎ Ｘ，ｅｔ ａ１． Ｃｏｍｐｕｔｉｎｇ ｈｉｅｒａｒｃｈｉｃａｌ ｃｕｒｖｅ－ｓｋｅｌｅｔｏｎｓ ｏｆ ３Ｄ ｏｂｊｅｃｔｓ［Ｊ］．Ｔｈｃ Ｖｉｓｕａｌ Ｃｏｍｐｕｔｅｒ，２００５，２１（１１）：９４５—９５５ ［１６］Ａｍｅｎｔａ Ｎ，Ｃｈｏｉ Ｓ，Ｋｏｌｌｕｒｉ Ｒ Ｋ．Ｔｈｅ ｐｏｗｅｒ ｃｒｕｓｔ［ｃ］／Ｐｒｏｃ ｏｆ ｔｈｅ ６ｔｈ ＡＣＭ Ｓｙｍｐ ｏｎ Ｓｏｌｉｄ Ｍｏｄｅｌｉｎｇ ａｎｄ ａｐｐｌｉｃａｔｉｏｎｓ． Ｎｅｗ Ｙｏｒｋ：ＡＣＭ，２００１：２４９—２６０ ［１７］Ｖｅｒｒｏｕｓｔ Ａ，Ｌａｚａｒｕｓ Ｆ．Ｅｘｔｒａｃｔｉｎｇ ｓｋｅｌｅｔａｌ ｃｕｒｖｅｓ ｆｒｏｍ ３Ｄ ｓｃａｔｔｅｒｅｄ ｄａｔａ［Ｊ］．Ｔｈｅ Ｖｉｓｕａｌ Ｃｏｍｐｕｔｅｒ，２０００，１６（１）：１５— ２５ ［１８３ Ｘｉａｏ Ｙ，Ｓｉｅｂｅｒｔ Ｐ，Ｗｅｒｇｈｉ Ｎ．Ａ Ｄｉｓｃｒｅｔｅ ｒｅｅｂ ｇｒａｐｈ ａｐｐｒｏａｃｈ ｆｏｒ ｔｈｅ ｓｅｇｍｅｎｔａｔｉｏｎ ｏｆ ｈｕｍａｎ ｂｏｄｙ ｓｃａｎｓ［ｃ］／／ Ｐｒｏｃ ｏｆ ｔｈｅ ４ｔｈ Ｉｎｔ Ｃｏｎｆ ｏｎ ３Ｄ Ｄｉｇｉｔａｌ Ｉｍａｇｉｎｇ ａｎｄ Ｍｏｄｅｌｉｎｇ． Ｗａｓｈｉｎｇｔｏｎ：ＩＥＥＥ Ｃｏｍｐｕｔｅｒ Ｓｏｃｉｅｔｙ，２００３：３７８—３８５ ［１９］Ｔａｇｌｉａｓａｃｃｈｉ Ａ，Ｚｈａｎｇ Ｈ，Ｃｏｈｅｎ－Ｏｒ Ｄ．Ｃｕｒｖｅ ｓｋｅｌｅｔｏｎ ｅｘｔｒａｃｔｉｏｎ ｆｒｏｍ ｉｎｃｏｍｐｌｅｔｅ ｐｏｉｎｔ ｃｌｏｕｄ［Ｊ］．ＡＣＭ Ｔｒａｎｓ ｏｎ Ｇｒａｐｈｉｃｓ：Ｐｒｏｃ ｏｆ ＳＩＧＧＲＡＰＨ ２００９，２００９，２８（３）：＃７１：１— ９ ［２ｏ３ Ｃａｏ Ｊ Ｊ，Ｔａｇｌｉａｓａｃｃｈｉ Ａ，Ｏｌｓｏｎ Ｍ，ｅｔ ａ１．Ｐｏｉｎｔ ｃｌｏｕｄ ｓｋｅｌｅｔｏｎｓ ｖｉａ Ｌａｐｌａｃｉａｎ－ｂａｓｅｄ ｃｏｎｔｒａｃｔｉｏｎ［ｃ］／Ｐｒｏｃ ｏｆ ＩＥＥＥ Ｓｈａｐｅ Ｍｏｄｅｌｉｎｇ Ｉｎｔ．Ｎｅｗ Ｙｏｒｋ：ＡＣＭ，２０１０：１８７—１９７ ［２１］Ｌｉａｎｇ Ｘ Ｈ，Ｚｈａｏ Ｑ Ｐ，Ｈｅ Ｚ Ｙ，ｅｔ ａ１．Ａ ｐｏｉｎｔ—ｂａｓｅｄ ｒｅｎｄｅｒｉｎｇ ａｐｐｒｏａｃｈ ｆｏｒ ｒｅａｌ—ｔｉｍｅ ｉｎｔｅｒａｃｔｉｏｎ ｏｎ ｍｏｂｉｌｅ ｄｅｖｉｃｅｓ ［Ｊ］．Ｓｃｉｅｎｃｅ ｉｎ Ｃｈｉｎａ：Ｓｅｒｉｅｓ Ｆ Ｉｎｆｏｒｍａｔｉｏｎ Ｓｃｉｅｎｃｅｓ，２００９， ５２（８）：１３３５—１３４５（ｉｎ Ｃｈｉｎｅｓｅ） （梁晓辉，赵沁平，何志莹，等．一种面向移动终端实时交互 的点模型绘制方法．中国科学：Ｆ辑信息科学，２００９，３９ （８）：８２２—８３２） １３８７ ［２２３ Ａｍｅｎｔａ Ｎ，Ｋｉｌ Ｙ．Ｄｅｆｉｎｉｎｇ ｐｏｉｎｔ—ｓｅｔ ｓｕｒｆａｃｅｓ［Ｊ］．ＡＣＭ Ｔｒａｎｓ ｏｎ Ｇｒａｐｈｉｃｓ：Ｐｒｏｃ ｏｆ ＳＩＧＧＲＡＰＨ ２００４，２００４，２３（３）： ２６４－２７０ ［２３］ Ｐａｕｌｙ Ｍ，Ｇｒｏｓｓ Ｍ，Ｋｏｂｂｅｈ Ｌ Ｐ．Ｅｆｆｉｃｉｅｎｔ ｓｉｍｐｌｉｆｉｃａｔｉｏｎ ｏｆ ｐｏｉｎｔ—ｓａｍｐｌｅｄ ｓｕｒｆａｃｅｓ［Ｃ］／Ｐｒｏｃ ｏｆ ＩＥＥＥ Ｖｉｓｕａｌｉｚａｔｉｏｎ． Ｗａｓｈｉｎｇｔｏｎ：ＩＥＥＥ Ｃｏｍｐｕｔｅｒ Ｓｏｃｉｅｔｙ，２００２：１ ６３—１ ７０ ［２４］ Ｈｅ Ｚ Ｙ，Ｌｉａｎｇ Ｘ Ｈ．Ａ ｎｏｖｅｌ ｓｉｍｐｌｉｆｉｃａｔｉｏｎ ａｌｇｏｒｉｔｈｍ ｂａｓｅｄ ｏｎ ＭＬＳ ａｎｄ ｓｐｌａｔｓ ｆｏｒ ｐｏｉｎｔ ｍｏｄｅｌｓ［ｃ］／／Ｃｏｍｐｕｔｅｒ Ｇｒａｐｈｉｃｓ Ｉｎｔ ２００９（ＣＧＩ’０９）．Ｎｅｗ Ｙｏｒｋ：ＡＣＭ，２００９：４０—４７ Ｈｅ Ｚｈｉｙｉｎｇ，ｂｏｒｎ ｉｎ １９８２．ＰｈＤ ｃａｎｄｉｄａｔｅ ｏｆ Ｂｅｉｈａｎｇ Ｕｎｉｖｅｒｓｉｔｙ．Ｈｅｒ ｍａｉｎ ｒｅｓｅａｒｃｈ ｉｎｔｅｒｅｓｔｓ ｉｎｃｌｕｄｅ ｃｏｍｐｕｔｅｒ ｇｒａｐｈｉｃｓ， ｖｉｒｔｕａｌ ｒｅａｌｉｔｙ，ｅｔｃ． Ｌｉａｎｇ Ｘｉａｏｈｕｉ，ｂｏｒｎ ｉｎ １ ９７０．ＰｈＤ ａｎｄ ａｓｓｏｃｉａｔｅ ｐｒｏｆｅｓｓｏｒ ｏｆ Ｂｅｉｈａｎｇ Ｕｎｉｖｅｒｓｉｔｙ． Ｈｉｓ ｍａｉｎ ｒｅｓｅａｒｃｈ ｉｎｔｅｒｅｓｔｓ ｉｎｃｌｕｄｅ ｃｏｍｐｕｔｅｒ ｇｒａｐｈｉｃｓ，ｖｉｒｔｕａｌ ｒｅａｌｉｔｙ，ｅｔｃ． Ｚｈａｏ Ｑｉｎｐｉｎｇ，ｂｏｒｎ ｉｎ １９４８．Ｐｒｏｆｅｓｓｏｒ ａｎｄ ＰｈＤ ｓｕｐｅｒｖｉｓｏｒ ｏｆ Ｂｅｉｈａｎｇ Ｕｎｉｖｅｒｓｉｔｙ． Ｓｅｎｉｏｒ ｍｅｍｂｅｒ ｏｆ Ｃｈｉｎａ Ｃｏｍｐｕｔｅｒ Ｆｅｄｅｒａｔｉｏｎ．Ｈｉｓ ｍａｉｎ ｒｅｓｅａｒｃｈ ｉｎｔｅｒｅｓｔｓ ｉｎｃｌｕｄｅ ｖｉｒｔｕａｌ ｒｅａｌｉｔｙ，ｖｉｓｕａｌｉｚａｔｉｏｎ ａｎｄ ａｒｔｉｆｉｃｉａｌ ｉｎｔｅｌｌｉｇｅｎｃｅ．
