一种点云模型逼近方体复形与网格曲面流形生成方法

摘要

点云模型逼近方体复形与网格曲面流形生成方法，(1)建立一个点云模型的包围体作为第一层的逼近方体复形；(2)将当前层次的方体复形中的每个方体剖分，由剖分后的方体形成新的层次的方体复形，建立层次之间方体的父子关系和同父子方体之间的邻接关系；(3)计算点云模型中的采样点属于新层次方体复形的哪一个方体，同时标记这个方体为非空方体；(4)建立具有不相同父亲的子方体之间的邻接关系；(5)根据控制准则删除空方体，删除相邻空方体，得到新的层次逼近方体复形和网格曲面流形；(6)检查新层次方体复形是否达到预定的层次数和逼近精度，如未达则转到步骤(2)，否则，输出各个层次的逼近方体复形和网格流形。本发明具有快速生成逼近方体复形和网格曲面流形的优点。

说明书

技术领域

本发明涉及一种点云模型逼近方体复形与网格曲面流形生成方法。

背景技术

虚拟现实(Virtual Reality，简称VR)技术是一种关于对现实世界的模拟、逼真体验的综合技术和方法。它涉及计算机图形学、人机接口、传感及人工智能等不同领域的知识。由于人类80％的信息是由视觉获得，所以，对现实世界的视觉模拟和逼真视觉体验，是虚拟现实系统重要的组成部分。三维几何造型技术、基于物力的建模技术、图像与图形相结合的技术、高效的真实感图形渲染技术等关键技术已经成为研究的热点问题。虚拟现实是一项应用技术，目前已被广泛应用于军事、航天、设计、生产制造、信息管理、商贸、建筑、医疗保险、危险及恶劣环境下遥控操纵、教育与培训、信息可视化以及远程通讯等多种领域。

在虚拟现实领域中，点云模型已经成为一种比较流行的模型。由于各类采集设备的发展，包括三维激光扫描、医学图像、遥感等，在现实应用中得到了大量的由三维空间物体采样点数据组成的物体模型。对点云模型图形学技术的研究不断发展，这些模型可以直接用于显示渲染、动态变形、碰撞检测等。由于点云模型的直接采样数据规模很大，点数据之间没有邻接关系，在上述应用中也遇到很多问题需要解决。一般的方法是通过点数据建立Delauney图进而构造三角网格曲面，这类途径往往极为费时，同时在采样间隙、多物体环绕等方面难以控制拓扑的改变，由于几何结构的复杂性，在实时碰撞检测等应用中也难以应用。

发明内容

本发明的技术解决问题是：克服现有技术的不足，提供一种快速的层次逼近方体复形生成方法，该方法同时生成一个点云模型的逼近网格曲面流形。

本发明的技术解决方案：点云模型逼近方体复形与网格曲面流形生成方法，其特征在于：需要建立点云模型的包围体，然后对包围体进行剖分得到子方体，根据控制准则删除空方体得到新的层次的逼近方体复形和网格曲面流形，在未达到逼近精度时继续进行剖分，重复以上逼近删除过程直至得到符合逼近要求的方体复形与网格曲面流形。

具体步骤如下：

(1)建立一个点云模型的包围体作为第一层的逼近方体复形。这个复形仅有一个方体，其表面的六个长方形组成第一层的网格曲面流形。

(2)将当前层次的方体复形中的每个方体剖分，由剖分后的方体形成新的层次的方体复形，建立层次之间方体的父子关系和同父子方体之间的邻接关系。

(3)计算点云模型中的采样点属于新层次方体复形的哪一个方体，同时标记这个方体为非空方体。

(4)建立具有不相同父亲的子方体之间的邻接关系。

(5)根据控制准则删除空方体，采用漫延的方式删除相邻空方体。删除完成后得到新的层次逼近方体复形和网格曲面流形。

(6)检查新层次方体复形是否达到预定的层次数和逼近精度(方体的边长)，如未达则转到步骤(2)，否则，结束运行，输出各个层次的逼近方体复形和网格流形。

本发明与现有技术相比的优点在于：

(1)采用剖分包围体删除空方体的方法实现层次逼近，使用控制准则保证逼近过程中外面网格曲面保持流形特性，避免采用具体的采样点为顶点的复形生成方法的复杂计算量，具有快速生成方体复形的特点。

(2)本发明的逼近方体复形的外面集是二维方体复形，在逼近控制准则的约束下成为网格曲面流形。这类快速生成的逼近网格曲面可以很好反映物体在一定分辨率下的拓扑和几何性质。此类生成网格流形的方法较三角面片方法更为快速有效，并且具有可以计算控制整体拓扑性质的优势。

(3)本发明针对点云模型由基本采样点组成的特性，采用迭代的方法分解方体，然后扫描采样点分配将每个采样点从所包含的方体分配到子方体中，同时标记出空方体。该类方法具有线性复杂性并且可以利用当前层次的方体包含关系计算剖分后子方体的包含关系，可以很快地标记方体空属性。

(4)当一个不影响拓扑变化的方体删除时，依据方体的邻接关系图，删除其周围的不影响拓扑变化的方体，这种方式称为漫延式删除方法，利用该方法可以使逼近过程最少的出现孔洞，这样逼近方体复形和网格曲面不会产生大量奇异的拓扑改变。同时，也可以提供交互操作的软件在逼近过程中进行拓扑改变的控制。

附图说明

图1为本发明中的逼近方体复形生成流程示意图；

图2为本发明中的方体属性描述图；

图3为本发明中的方体邻接关系描述图；

图4为本发明中的逼近方体集层次分类图；

图5为本发明中的方体剖分处理流程图；

图6为本发明中的方体删除分断判断示意图；

图7为本发明中的方体邻接表；

图8为本发明中的方体张力系数示意图。

具体实施方式

图1为本发明中的逼近方体复形生成流程示意图，通过流程中的方向线段标示了实现逼近方体复形的生成过程。图5中将整个逼近方体复形的处理方法分为三个大的部分，同时描述了每个部分的具体处理方法。下面结合图1和图5具体说明本发明的实施过程和主要处理方法。

1.通过计算点云模型中所有采样点的坐标的极大和极小值得到点云模型的包围体，形成第一个层次的逼近方体复形。这个包围体是一个各个面均与坐标轴平行的长方体，其最小坐标的顶点为采样点各个坐标的最小值，最大坐标的顶点为采样点各个坐标的最大值。

所谓方体复形是一些方体的集合，各个方体之间的交集也是方体。所谓方体在本发明中的定义为：0维、一维、二维和三维方体分别指点、线段、长方形和长方体。

2.第二阶段为方体剖分。方体剖分的过程如图5(左)，剖分方法为使用经过方体中心的与坐标轴平行的平面，将本层次的方体剖分为8个子方体。

图2中本发明所给出的一种方体顶点编号(见图2左图)，棱编号(见图2中图)和一个方体剖分后的8个子方体的编号(见图2右图)。

对上一个层次的方体进行线性扫描，逐一剖分未作删除标记的每个方体为8个子方体。剖分一个方体后，建立剖分子方体的位置属性(最小顶点)，几何属性(边长)和编号，给出每个剖分子方体的顶点、棱、面的内邻接关系。面的空间邻接属性具有继承特性，根据所在父方体的面的空间邻接属性给出其内面、外面、连接面三类属性。

方体邻接关系表中将方体的邻接分为三类：面邻接、棱邻接和顶点邻接。为了描述的简洁，邻接表中标记邻接方体在父方体中的子方体编号。顶点邻接分为产生于父方体的面、棱的顶点和内顶点(父方体的中心点)、原顶点(该顶点也是父方体的顶点)。方体的顶点邻接对应关系比较直接：邻接方体号＝8-子方体号+1，不需要建立邻接表。方体的面邻接表和棱邻接表见图7。

根据方体是否属于同一个父亲又将方体之间的邻接分为内邻接和外邻接，内邻接指相邻的两个方体由同一个方体剖分，外邻接指相邻的两个方体由不同的方体剖分产生。

图3中是方体的邻接关系描述，图中指出了外邻接和内邻接，如果两个方体是同一个方体的子方体，它们之间的邻接为内邻接，即8个子方体之间的邻接。不是同一个方体剖分得到的方体之间的邻接则为外邻接。

每个三维方体由六个外表长方形(称为二维方体)包围，如果方体复形的一些二维方体包围成一个有限的空间，则这些二维方体称为内面，如果一个二维方体是两个方体的共享面，则称为邻接面，如果一个二维方体与一个无限的空间邻接，则称为外面。

3.第三阶段为计算点云模型中的采样点在新的层次中的所在方体编号，同时标记新层次中方体的空属性(即是否包含采样点)。首先根据采样点在上个层次中的方体计算其所在子方体编号，然后由子方体编号所对应的新的层次中的方体编号，给出采样点的新层次方体复形中的包含方体编号，设置该方体的空属性为假。

4.第四阶段为建立具有不同父亲的子方体之间的邻接关系。这类邻接关系通过层次方体之间的继承关系和子方体在父方体中的几何位置来确定，具体步骤如下：

(1)确定子方体在父方体中的编号；

(2)通过父方体的邻接属性确定其那些面与其他方体邻接，通过方体-方体(面)外邻接表(图7)确定当前子方体的面是否在这个邻接面上，确定其与那个子方体邻接，然后确定其编号；

(3)通过父方体的邻接属性确定其那些棱与其他方体邻接，通过方体-方体(棱)外邻接表(图7)确定当前子方体的面是否在这个邻接棱上，确定其与那个子方体邻接，然后确定其编号；

(4)通过父方体的邻接属性确定其那些顶点与其他方体邻接，根据特性分析，每个顶点的相邻关系都可用下述公式表示：

i→8-i+1

其中i为当前的子方体编号，8-i+1为邻接方体在父方体中的编号。于是，通过父方体和子方体之间的对应关系就可以求得当前层次方体之间顶点邻接关系。

图7给出了方体之间的内、外邻接关系表，邻接表中使用一个方体作为子方体的编号，同时对其邻接的方体也用子方体编号，同时将邻接关系分为顶点、棱和面的邻接情况，根据邻接关系的规律给出了映射关系表。

5.第五阶段为根据控制准则删除空方体生成逼近方体复形和网格曲面流形，即在新层次的方体复形中删除一些空方体，具体步骤如下：

(1)扫描所有新层次的方体，首先检查是否为空方体，跳过非空方体。

(2)如果是空方体，则检测其邻域方体是否空方体，根据张力最小准则，优先跟踪张力大的邻域方体去删除，这个准则的具体实现过程如下：

当多个空方体邻接且都符合流形保持准则时，优先删除其中心远离其他方体的空方体，远离的特性通过设计张力系数进行计算，张力系数越大时该方体越远离曲面，当需要分析若干个方体中哪一个优先删除时，通过计算比较其张力系数来确定，具体公式如下：