一种表示流形形体和非流形形体的统一数据结构研究  

An Uniform Data Structure Supporting Manifold and Non-Manifold Modeling

作　　者：张成林 朱琳 文珊珊 王卓 王联凤 

机构地区：[1]中国科学技术大学工程科学学院,安徽合肥230026 [2]上海交通大学机械与动力工程学院,上海200240 [3]上海航天设备制造总厂,上海200245

出　　处：《上海航天》2017年第4期158-163,共6页Aerospace Shanghai

基　　金：航天先进技术联合研究中心技术创新项目资助(USCAST2015-23)

摘　　要：为弥补3D打印中非流形拓扑数据结构的存储空间大、运算效率低,流行拓扑数据结构形体表示的局限性,研究了一种可表示流形形体(正则形体)和非流形形体(非正则形体)的统一数据结构。分析了半边数据结构、放射边数据结构、混合边数据结构、单元复形和粘合边数据结构等非流形形体的边界表示法,发现现有的数据结构未能综合考虑几何模型、存储数据和效率。提出了一种基于复形的非流形数据结构:利用引用面、边及点结构完整地表示非流形几何模型,实现线框、表面、实体和自由曲面模型的统一;采用面向对象的设计方法,使用类的继承与派生,以减少数据存储量,提高存储和运算效率;扩展欧拉算子可为更高级的欧拉操作和布尔操作提供基础。设计的方法在模型的面、边和点的数据设计中,以指针的形式管理和组织拓扑结构,避免信息的重复存储,既满足了丰富的形体表示需求,扩大了传统3D打印模型的覆盖域,又有效减少了存储空间,提高了运算效率。To solve the large storage space and low computation efficiency in non-manifold modeling data structure and the limitation in manifold modeling in 3D printing,an uniform data structure supporting manifold（regularized）and non-manifold（non-regularized）modeling was studied in this paper.Some boundary representation methods which were half edge data structure,radial data structure,hybrid edge data structure,cell complex and adjunction edge data structure for non-manifold modeling were analyzed.It found that the present data structures did not put effectively expressing non-manifold model,reducing data storage and improving operational efficiency together.So the data structure for non-manifold modeling based on complex was put forward.The geometrical model of non-manifold is represented completely through face,edge and vertex by reference,which realizes the uniform models of the wireframe,surface,solid and free curved surface.The object-oriented design is used and successiveness and derivation of class are applied also to reduce the data storage and improve the efficiency of the storage and computation.The extended Euler operator can provide the base for higher level Euler operation and Boolean operation.The unified data structure proposed uses pointer format in data structures of face,edge and vertex to avoid duplicated information.Tests have shown that it can represent the manifold and non-manifold modeling with enlarging domain of traditional 3dmodel and effectively reducing the storage space.

关 键 词：3D打印 几何模型 流形形体 非流形形体 数据结构 拓扑结构 运算效率 存储空间 

分 类 号：TP391.73[自动化与计算机技术—计算机应用技术]