基于文件内存映射和多线程的三角网格模型快速拓扑重构

陈义明，张应中，罗晓芳

（大连理工大学机械工程学院，大连 116023）

0 引言

随着三维数字扫描技术的发展，很多复杂的实体对象，例如复杂零部件、大型建筑物和地理场景等，通过数字扫描获取其三维数字模型，通常会将扫描的点云模型转换成三角网格模型，并且随着模型的精度的提高，由此产生的三角网格规模非常庞大，三角面数量达到几百万或者上千万，其结果是文件大小常常达到了几百MB 甚至数GB。此外，目前三角网格模型采用STL 格式存储，STL 三角网格文件仅仅是一个三角面集的排列，包含大量的重复顶点，缺乏三角面、边顶点之间的拓扑关系，三角网格模型的进一步应用需要进行拓扑关系的重构。因此如此大数据量的三角网格文件，若采用传统的文件处理技术进行三角网格数据的读取及重构，势必模型的处理效率较低，等待的时间过长。

目前对于提高大型数据文件处理效率主要途径是采用文件内存映射技术加快读取速度，该方法通过将文件的全部或部分内容映射到进程的虚拟内存之中，减少了磁盘的I/O 操作，使应用程序可以通过内存直接访问位于磁盘上的文件数据。在大规模计算方面，主要采用并行计算处理技术，对于现代多核计算机，多线程技术由于其高效的处理效率，已经成为多任务处理中的主流方式。但在三角网格模型拓扑重构方面，基于文件内存映射和并行重构研究较少。本文考虑到STL 网格文件中各个面的数据相互独立的特点，多线程技术可以有效运用于文件处理操作中，融合内存映射和多线程技术，实现了对大规模三角网格模型快速重构，通过计算机多核多线程处理数据的优势，模型数据的重构效率得到较大的提升。

1 三角网格模型重构总体方案

1.1 STL三角网格模型重构需求

STL文件存储了三维网格模型中三角形面的几何信息，包括面的法向量及该面的三个顶点坐标。STL三角网格文件格式简单，但仅仅是一个三角面集的排列，包含大量的重复顶点，并且缺乏三角面、边顶点之间的拓扑关系。如果三角网格模型需要进一步应用，例如网格几何运算、网格修复和网格特征识别等，重构其拓扑关系是必要的。

STL三角网格模型重构需求就是将无序的三角面集按照一个三角网格拓扑数据结构重新进行组织，构建三角面、边和顶点之间的拓扑关系，为后续网格模型应用提供支撑。

1.2 基于面的三角网格拓扑数据结构

为了表示三角网格模型面、边和顶点之间的拓扑关系，一个紧凑有效的拓扑数据结构是必要的。三角网格拓扑数据结构有很多，典型代表是半边数据结构，但传统半边数据结构占用较大的内存，如果三角形顶点个数为，则需要180个字节，本文采用文献提出的基于面的数据结构，该数据结构通过面和顶点表示一个三角形拓扑信息，仅占用52个字节（32 位编程），并且能够表示流形和非流形三角网格信息，提供三角拓扑信息访问机制，保证重构后的网格数据能够实现高效的拓扑信息的查询。该数据结构如图1所示。

图1 基于面的三角网格拓扑数据结构

主要内容如下：

顶点类中用3个float变量存储三角面三个顶点坐标，使用一个面类的指针指向该点所在的三角形面，通过该指针，可以访问该点引用的三角面信息。顶点类的编码如下：

面的结构中包含存储面的法向量，存储该面的三个顶点指针，存储该面与相邻的其它3个面的指针，面类的编码如下：

1.3 文件内存映射及多线程并行处理

文件内存映射技术是Windows 系统及Linux系统中广泛使用的大文件读写技术，该技术通过将文件的全部或部分内容映射到进程的虚拟内存之中，减少了数据的拷贝操作，提高了读取速度。映射过程中没有数据的实际拷贝操作，文件只是逻辑上存在于进程的虚拟内存之中，系统通过缺页中断机制访问位于磁盘上的文件数据。由于不再需要执行文件的I/O 操作，并且读取过程中系统不用再为文件申请并分配缓存，使得内存映射技术能够有效提高大文件的读取速度。

多线程并行处理技术是指从软件或者硬件上实现多个线程并发执行的技术。通常在一个Windows程序中，一个独立运行的程序片段称为“线程”（Thread），同时采用多个线程处理同一问题，称为多线程处理。现代计算机通过软硬件的配合能够并行的运行多个线程，使计算机的整体性能得到较大提高。目前大部分计算机系统都有多核心处理器或同时多线程处理器，为开展多线程并行重构三角网格模型提供条件。

1.4 三角网格模型拓扑重构总体方案设计

基于上述分析，为了更高效地重构三角网格模型，本文提出如图2所示的STL三角网格模型多线程并行拓扑重构总体方案。该方案主要包括如下3个步骤。

图2 STL三角网格拓扑并行重构总体方案

首先通过Windows 系统提供的文件内存映射机制，将要重构的三角网格文件映射到应用进程的虚拟内存中，映射过程中没有数据的实际拷贝操作，文件只是逻辑上存在于进程的虚拟内存之中，系统通过缺页中断机制访问位于磁盘上的文件数据。

对于大型网格模型文件采用多线程并行分段处理可以大大提高拓扑重构效率。线程的数量需要综合考虑CPU 核的数量及要处理文件的大小，通过实验确定出一个性能较优化的线程数量，再依据线程数量确定文件分割的段数，使每一个线程对应一个内存映射文件的分段。

将拓扑重构任务分配给多个处理线程，每个线程读取内存映射文件的一个分段，共同并行地完成三角网格模型的拓扑重构。

2 STL三角网格文件映射分段及多线程设计

2.1 STL三角网格文件映射分段

本文采用Windows 提供用于大型文件内存映射机制的API函数实现STL三角网格文件映射分段，具体实现过程如下。

首先使用CreateFile 函数创建文件内核对象，得到文件内核对象的句柄Handle，然后将该句柄传入CreateFileMapping 函数中创建文件映射内核对象，该函数用于指定文件的尺寸及访问文件的方式，并返回映射对象的句柄MapHandle。

将上述文件映射对象句柄作为MapViewOf⁃File函数的参数，该函数负责将文件的全部或部分内容映射到进程的虚拟内存中，若映射成功，返回一个LPVOID 类型的指针，这是一个无类型的指针，通常将该指针强制转换成char*类型的指针，使其指向文件映射的起始位置。最后当不再需要使用该映像数据时，通过Un⁃mapViewOfFile 函数卸载映射，文件读取结束时，使用CloseHandle函数关闭文件映射对象。

由于STL 文件的数据规模可能很大，按照上述总体方案设计，需要对三角网格文件进行分段映射处理。由于Windows 操作系统通常按页存取数据，并且系统中页的分配粒度为64 kB，因此分段偏移地址必须取为64 kB的整数倍。但这样的分段方式容易使一个完整的三角面数据被分在两个不同的段中，导致该面的数据无法得到正常读取。为解决此问题，本文提出如图3所示的分段方法。

图3 STL文件分段内存映射

具体分段步骤如下：

（1）确定分段数量。按照总体方案设计，分段数量取决于选择的线程数量。具体线程数量选择在下一节介绍。

（2）计算跨界长度。二进制的STL 文件中每个三角形的几何信息由固定的字节数表示。开头的84个字节用于描述模型的文件信息，其中80个字节是文件头，用于存储零件名，剩下的4字节为一个整数，用于存储文件中包含的三角形数量，之后用固定的字节数表示三角形的几何信息，每个三角形数据占用50字节。如果，为自然整数，则跨界长度按如下公式计算：

（3）向后偏移跨界长度映射下一个分段。因为上一个分段一次性将64000*字节映射到内存，在读取最后一个三角面时，与映射数据相差一个跨界长度，因此从第2个分段开始，映射开始地址在前一分段结束位置处向后偏移一个跨界长度。

2.2 多线程设计

随着CPU 多核技术的出现，多线程并行读取文件和信息处理可以获得较好的操作性能。但是线程的数量也不是越多越好，因为线程间的切换和调度会消耗CPU 资源和时间，如果设置线程数量过大，会影响处理性能，一个合适的线程数量设置是有必要的。在本文提出的方法中，线程数量设置主要考虑如下因素。

如果文件长度小于8 M，即采用单线程，否则采用多线程，线程数量由以下因素确定。

线程的执行是由CPU 进行调度的，一个CPU 在同一时刻只会执行一个线程，如果多个线程，操作系统一般采用时间片轮转的方式，任务的切换会导致额外的开销。本文涉及的重构计算主要依赖于CPU，因此选择线程数量=CPU核数+1。

如果工作任务是高强度计算，则要适当降低线程数量，否则如果工作任务是事务性的工作，有等待时间，可以适当提高线程数量。

3 基于多线程的三角网格模型并行拓扑重构

3.1 三角网格模型拓扑重构算法分析

按照上述重构总体方案设计，拓扑重构模型是采用文献［6］给出的基于面的拓扑数据结构。文献［6］还给出了面向STL 文件的拓扑重构算法，如图4所示。从给出的算法看，拓扑重构过程主要分为如下3个操作。

图4 基于面的拓扑重构算法［6］

（1）创建三角面对象。每读取一个三角面数据，就创建一个三角面对象，并加入到重构的三角网格模型中。

（2）查找或者创建新的顶点。由于STL 网格文件包含大量的重复顶点，因此创建一个新的顶点对象前要查询在该顶点位置是否已经创建顶点，如果有就直接引用该顶点，否则创建新顶点。一个大型的三角网格模型包含上百万个顶点，查找的效率非常重要，采用文献［6］给出的Hash表查找。

（3）查找相邻三角面。顶点对象完成后，通过顶点对象对面的引用，查找三角面的三个相邻面，一次操作可能完成不了，在所有面完成后还需要执行一遍这样的操作。需要有一个共有的三角面表容器。

3.2 三角网格模型拓扑并行重构策略

根据上述三角网格模型拓扑重构算法分析，可以看出重构过程主要由一系列的重复操作组成，完全可以将重复操作分配给多个线程完成。为此提出如下并行重构策略。

（1）设置共享数据区。每个线程仅需要对部分三角面并行执行相同三角面重构操作，构造生成的顶点和三角面对象存储在共同的Hash 点表和三角面表中，将共同的Hash 点表和三角面表设置为共享区域。

（2）设置共享数据区域加锁保护机制。在多线程重构过程中，为了保证处理数据的安全，可以通过对共享区域加锁，保证同一时刻只有一个线程对共享数据区域进行修改操作。为此设置一个公有的可操作标志，当一个线程在进行顶点或者面创建操作时，可操作标志为0，操作完成后置为1。只有当可操作标志为1 时，线程的所有操作才可进行。这种加锁解锁机制有效实现了线程间的互斥访问，保证了程序运行的稳定性。

3.3 三角网格模型拓扑并行重构实现

基于上述STL 文件分段操作和并行重构策略，本文基于文献［6］给出的三角网格拓扑重构算法基础上，实现了网格模型拓扑并行重构，主要操作步骤如下。

（1）创建并行重构线程。根据设置的线程数量，创建并行重构线程。创建之前文件内存映射分段完毕，每一个线程设置读取相应的文件分段的偏移长度，偏移长度按照3.1给出的方法计算。

（2）启动并行重构算法各个线程。每个线程基本上并行执行相同的操作，其中线程执行过程如图5所示。

图5 三角网格并行拓扑重构算法流程

（3）读取文件分段中的三角面片。每读取一个三角面数据，开始构建顶点对象和面对象，在操作前检查公有标志：opFlag，只有当opFlag等于1时才执行操作，如果要执行顶点对象或者面对象的插入，首先将opFlag 置为0，待插入操作完成后，将opFlag 再置为1。因此当一个线程在执行插入写操作时，其它所有线程的操作被等待，直到opFlag变回到1。

（4）一个三角面的三个顶点都处理完成后，将读取下一个三角面，如果三角面读取处理完成，子线程结束，否则转上面第（3）步。

（5）主线程等待所有子线程读取结束，文件处理完成，主线程结束。

由于文件已经被映射到内存中，读取文件几乎和内存操作速度相当，没必要单独为未重构的模型分配内存，节省了内存空间。

4 重构实验

本文在Windows 10 操作系统上采用Visual C++和OpenGL 编程进行快速重构实验，实验计算机配置i5 2.5 GHz CPU、4 G内存。依次选用箱体模型、端盖模型及马的模型的STL文件为读取对象，模型重构后OpenGL显示如图6所示。

图6 STL三维网格文件模型显示

对以上模型采用普通单线程方法、单线程内存映射方法以及多线程内存映射方法依次读取文件并重构网格数据。由于系统CPU 为双核处理器，故多线程内存映射方法中的线程数确定为三个，经实验验证，三个线程的读取效率最高。从STL 网格文件开始读取到网格数据拓扑关系的重构，记录系统总的运行时间，表1为三种方法对不同数据量的三角网格文件的读取及重构时间：

表1 三种方法重构网格数据的时间对比

通过时间对比可以看到，内存映射技术能有效提高文件读取速度，平均的读取效率比普通单线程提高15%以上。在内存映射的基础上使用多线程技术，由于利用了CPU 并行处理文件的优势，使得读取和重构效率比单线程的内存映射提高20%以上。综合分析，多线程内存映射在读取大规模的三角网格文件时，比起传统的单线程方法效率提升显著。

5 结语

三角网格文件的快速拓扑重构对后续的网格应用至关重要。针对大数据量的网格文件占用空间大，重构速度慢的问题，本文提出了一种基于内存映射和多线程的三角网格模型快速重构方法，通过对大型STL 三角网格文件内存分段映射，采用多线程并行对文件分段内容分别进行网格数据重构，重构出基于面的三角网格模型拓扑数据结构，与传统的重构方法相比，重构效率得到了明显提升，实验表明了该方法的可行性。