基于AIF的三角形网格切割重建方法转让专利
申请号 : CN200810035539.5
文献号 : CN100595796C
文献日 : 2010-03-24
发明人 : 杨杰 , 黄洁
申请人 : 上海交通大学
摘要 :
一种计算机应用技术领域的基于AIF的三角形网格切割重建方法。本发明首先将三角形三维网格模型数据表现形式转化为具有邻接入射关系的AIF数据结构形式，并进一步对该形式的数据进行网格模型重建处理，在处理的过程中，先将切割路径经过的三角形网格模式化分类，然后根据分类的结果再进行快速的AIF结构查询和修改，最终获得全新的切分后网格数据，实现切割体的网格重建。本发明避免了切割过程中全局性的修正网格，充分利用AIF结构特点，以局部网格重建实现拓扑结构的改变，从而有效地提高了三角形网格切割时网格重建的速度，并且该速度不随三角形网格数据量规模而改变，能达到很好的稳定性。
权利要求 :
1、一种基于邻接入射框架结构AIF的三角形网格切割重建方法，其特征在于：首先将三角形三维网格模型数据表现形式转化为具有邻接入射关系的AIF数据结构形式，进一步对该形式的数据进行网格模型重建处理，在处理的过程中，先将切割路径经过的三角形网格模式化分类，然后根据分类的结果再进行快速的AIF结构查询和修改，最终获得全新的切分后网格数据，实现切割体的网格重建； 所述将三角形三维网格模型数据表现形式转化为具有邻接入射关系的AIF数据结构形式的具体步骤为： 首先，获取原始的三角形网格模型数据，其存储的形式为一个含有所有顶点坐标的一维数组以及一个含有所有三角形面片的顶点索引的一维数组； 然后根据三角形每一个顶点建立一个相应的顶点AIFVertex对象，其数据内容为：顶点三维坐标、顶点的法方向坐标、顶点为端点的所有边对象列表，所述顶点为端点的所有边对象列表即入射于该顶点的所有边对象列表，根据原始数据，填写每一个顶点AIFVertex对象的三维坐标以及法方向坐标； 接下来，建立一张边信息的查询表，遍历所有三角形面片的顶点索引的一维数组，分别将每个三角形顶点两两成对，按两个顶点的索引升序排列，组成一对信息，把此对信息在已经建立的边信息查询表中进行查找，如果信息没有匹配到，则生成一个新的边AIFEdge对象并填写其顶点信息，如果已经存在，则更新边信息查询表、边AIFEdge对象和顶点对象信息，其中，边AIFEdge结构包含有边的两个顶点对象、入射于边的面列表，每完成一个三角形面片的边操作时，将这些边构造成邻接边列表，存储在三角形面AIFFace对象中； 最终，当扫描完所有的三角形面片，实现原始数据到新的AIF邻接入射关系结构的转化； 所述将切割路径经过的三角形网格模式化分类，具体为：首先假定每一个三角形面片至多仅有两个采样点，并且采样频率相对于整个三角形网格模型的规模足够高，从而，将采样点与三角形的位置关系概括为四种基本情况，即： 第一种，采样点在三角形的任意两条边上； 第二种，某一个采样点交于三角形任意一个顶点上，而另一个采样点则交在该顶点的对边上； 第三种，某一个采样点交于三角形任意一条边上，而另外一个顶点则落在三角形内部； 第四种，两个采样点都落在三角形任意两个顶点上； 所述根据分类的结果再进行快速的AIF结构查询和修改，最终获得全新的切分后网格数据的具体步骤为： 首先构造基本分类模式，获得三角形面、边、顶点的增减模式； 然后根据既定的增减模式，先对由于切割而添加的三角形顶点AIFVertex对象进行创建，再创建新添加的三角形，在创建新三角形面AIFFace的过程中，通过三角形每两个AIFVertex对进行组合查询，即匹配两个AIFVertex对象中入射边列表是否有相同内容，如果存在，则直接填写入新的AIFFace对象中，如果不存在，则创建一个新的AIFEdge对象，然后填写入新的AIFFace对象中； 最后，对于由于切分而需要被删除的三角形面AIFFace和三角形边AIFEdge对象，要先查找AIFEdge对象内顶点AIFVertex对象中该AIFEdge对象，并把它从顶点的入射边列表中删除，同样，首先从AIFFace对象内边AIFEdge对象的入射面AIFFace列表中找到该AIFFace对象，并把它从边的入射面列表中删除； 所述新添加的三角形，采用三角形顶点连接顺序继承方法来保持新产生的三角形具有原来三角形的法方向，即只需要继承被切割三角形某一个边的连接关系，就能确定整个三角形顶点的连接顺序； 当采样点与三角形的两个顶点完全重合，经过了两个及两个以上的三角形时，利用以下步骤来实现其网格重建： 步骤1：选择一个被切割到边的三角形为起始三角形，通过切割的边以及交汇的切割点查询到三角形的另一条边，和该边的另一个入射三角形； 步骤2：察看新查询到的三角形与另一个被切割到边的三角形是否相同，如果相同则转到步骤4处理，否则继续； 步骤3：修改该查询到的三角形共享的顶点信息，然后继续查找以共享顶点为端点，即入射于共享顶点的另一个三角形边，和该边的另一个入射三角形；重复步骤2； 步骤4：结束处理。
说明书 :
基于AIF的三角形网格切割重建方法
技术领域
本发明涉及一种计算机应用技术领域的图像重建方法，具体是一种基于AIF的三角形网格切割重建方法。背景技术
近年来，随着医学成像技术的发展，计算机虚拟现实技术在医学中的应用得到了飞速的发展。计算机利用这些图像信息进行三维图像重建，为外科医生进行手术模拟、手术导航、手术定位、制定手术方案提供了客观、准确、直观、科学的手段。同时，由于这些图像信息具有准确性和可靠性，故被广泛应用于医疗机器人系统，进而使微创手术也得到了快速的发展。与之密切相关的计算机辅助系统，是一种具有大量数据信息的高速处理及控制能力，通过虚拟的手术环境从技术上提供支援，使手术更安全、更准确的一门新技术。可以认为计算机辅助手术系统是应用在医学领域的虚拟现实技术的一部分，并且在微创性和精准性上给医疗水平带来了相当的提升。
基于三维模型的切割技术是计算机辅助手术系统中最为基础的交互式操作，尤其是基于表面重建的三维网格模型切割技术，由于其结果的精确性、可测量性和绘制的真实性，从而成为国内外科学研究与应用领域的热点。在基于三角形网格模型的切割技术中，切割路径定义后的网格重建是最终切割体形成的主要步骤。因此高效准确地实现沿切割路径的网格重建方法既是三维交互式切割的技术关键，同样也是计算机辅助手术系统得以实现的关键之一。
AIF是Frutuoso等人于2003年提出的一种邻接入射框架结构，它是通过构建多边形之间的邻接入射关系，来记录多边形网格拓扑结构的数据结构。主要应用于多边形网格简化，多分辨率多边形绘制等算法中，具有高效通用等特性。较之一般的算法结构，AIF可以快速而高效地实现创建、搜索和网格重建。切割算法的目的是改变三角形的连接关系，创建新的网格结构，而在算法的实现过程中，本质是在对三角形网格的拓扑结构进行更改，如果基于传统的顶点索引结构来实现多边形网格在切割过程中的删除、添加与修改则需要修改整体数据，尤其是随着三角形片数的增加，十分耗费时间。而将AIF应用于此，则可以充分发挥其算法特点，高效地完成局部网格的重建计算。
经对现有技术的文献检索发现，布雷克成像有限公司的专利《在网格表面和立体对象上产生和测量表面线的系统和方法以及网格分割技术（"曲线测量"）》，专利（申请）号：200580040444.7，提出了建立一种新的三角形网格数据结构，并且利用此结构和定义的切割路径实现了网格切割重建。其不足之处在于切割实现必须基于闭合或者通过边界的切割曲线，且用于切割所构建的三维模型结构存储冗余度较大，査询、修改运算较为复杂。
近年来，随着医学成像技术的发展，计算机虚拟现实技术在医学中的应用得到了飞速的发展。计算机利用这些图像信息进行三维图像重建，为外科医生进行手术模拟、手术导航、手术定位、制定手术方案提供了客观、准确、直观、科学的手段。同时，由于这些图像信息具有准确性和可靠性，故被广泛应用于医疗机器人系统，进而使微创手术也得到了快速的发展。与之密切相关的计算机辅助系统，是一种具有大量数据信息的高速处理及控制能力，通过虚拟的手术环境从技术上提供支援，使手术更安全、更准确的一门新技术。可以认为计算机辅助手术系统是应用在医学领域的虚拟现实技术的一部分，并且在微创性和精准性上给医疗水平带来了相当的提升。
基于三维模型的切割技术是计算机辅助手术系统中最为基础的交互式操作，尤其是基于表面重建的三维网格模型切割技术，由于其结果的精确性、可测量性和绘制的真实性，从而成为国内外科学研究与应用领域的热点。在基于三角形网格模型的切割技术中，切割路径定义后的网格重建是最终切割体形成的主要步骤。因此高效准确地实现沿切割路径的网格重建方法既是三维交互式切割的技术关键，同样也是计算机辅助手术系统得以实现的关键之一。
AIF是Frutuoso等人于2003年提出的一种邻接入射框架结构，它是通过构建多边形之间的邻接入射关系，来记录多边形网格拓扑结构的数据结构。主要应用于多边形网格简化，多分辨率多边形绘制等算法中，具有高效通用等特性。较之一般的算法结构，AIF可以快速而高效地实现创建、搜索和网格重建。切割算法的目的是改变三角形的连接关系，创建新的网格结构，而在算法的实现过程中，本质是在对三角形网格的拓扑结构进行更改，如果基于传统的顶点索引结构来实现多边形网格在切割过程中的删除、添加与修改则需要修改整体数据，尤其是随着三角形片数的增加，十分耗费时间。而将AIF应用于此，则可以充分发挥其算法特点，高效地完成局部网格的重建计算。
经对现有技术的文献检索发现，布雷克成像有限公司的专利《在网格表面和立体对象上产生和测量表面线的系统和方法以及网格分割技术（"曲线测量"）》，专利（申请）号：200580040444.7，提出了建立一种新的三角形网格数据结构，并且利用此结构和定义的切割路径实现了网格切割重建。其不足之处在于切割实现必须基于闭合或者通过边界的切割曲线，且用于切割所构建的三维模型结构存储冗余度较大，査询、修改运算较为复杂。
发明内容
本发明目的是针对现有技术的不足，提出一种基于AIF的三角形网格切割重建方法，解决了大数据量三角形网格模型在切割路径定义后网格重建速度慢的问题。本发明首先实现完全和不完全切割的网格重建，即允许切割路径的起点和终点不重合或者不在曲面的边界上，具有更大的通用性；另外，充分发挥了AIF结构的存储精简性，通过有限的模式定义并利用其AIF结构简便的查询方法则可以较为快速地实现切割路径定义后的网格重建，构造新的切割体部分。
本发明是通过以下技术方案实现的，首先将传统的三角形三维网格模型数据表现形式转化为具有邻接入射关系的AIF数据结构形式，并进一步对该形式的数据进行网格模型重建处理。在处理的过程中，先将切割路径经过的三角形网格模式化分类，然后根据分类的结果再进行快速的AIF结构査询和修改，最终获得全新的切分后网格数据，实现切割体的网格重建。
所述把传统的三角形三维网格模型数据表现形式转化为具有邻接入射关系的AIF数据结构形式，具体步骤为-
- 首先获取原始的三角形网格模型数据，其存储的形式为一个含有所有顶点坐标的一维数组以及一个含有所有三角形面片的顶点索引的一维数组；
然后根据三角形每一个顶点建立一个相应的顶点AIFVertex对象，其数据内容为顶点三维坐标，顶点的法方向坐标，顶点为端点的所有边对象列表，即入射于该顶点的所有边对象列表，根据原始数据，可以填写每一个顶点AIFVertex对象的三维坐标以及法方向坐标；接下来，建立一张边信息的査询表，遍历所有三角形面片的顶点索引的一维数组，分别将每个三角形顶点两两成对，按两个顶点的索引升序排列，组成一对信息，把此对信息在已经建立的边信息查询表中进行查找，如果信息没有匹配到，则生成一个新的边AIFEdge对象并填写其顶点信息，如果已经存在，则更新边信息查询表以及边AIFEdge对象，顶点对象信息，其中，边AIFEdge结构包含有边的两个顶点对象，入射于边的面列表，每完成一个三角形面片的边操作时，将这些边构造成邻接边列表，存储在三角形面AIFFace对象中；
最终，当扫描完所有的三角形面片，就可以实现原始数据到新的AIF邻接入射关系结构的转化。
所述将切割路径经过的三角形网格模式化分类，具体为：首先假定每一个三角形面片至多仅有两个采样点，并且采样频率相对于整个三角形网格模型的规模足够高。从而，可以将采样点与三角形的位置关系概括为四种基本情况，S卩：（1)采样点在三角形的任意两条边上，这样是对三角形实现了完全切割；（2)某一个采样点交于三角形任意一个顶点上，而另一个采样点则交在该顶点的对边上，这样也可能产生完全切割；（3)某一个采样点交于三角形任意一条边上，而另外一个顶点则落在三角形内部，这样的情况产生了不完全切割；（4)两个采样点都落在三角形任意两个顶点上，这样的情况可能产生完全切割。由于模式化分类只是限定了采样点即切割线穿越三角形的模式，任何一个情况都可以经过旋转的方式去匹配这个分类，所以在之后的处理步骤上，具有概括抽象的先导作用。
所述根据分类的结果再进行快速的AIF结构查询和修改，最终获得全新的切分后网格数据，具体步骤为：
首先构造基本分类模式，获得三角形面、边、顶点的增减模式；
然后根据既定的增减模式，先对由于切割而添加的三角形顶点AIFVertex对象进行创建，再创建新添加的三角形。在创建新三角形面AIFFace的过程中，需要通过三角形每两个AIFVertex对进行组合查询，即匹配两个AIFVertex对象中入射边列表是否有相同内容，如果存在，则直接填写入新的AIFFace对象中，如果不存在，则创建一个新的AIFEdge对象，然后填写入新的AIFFace对象中。
最后，对于由于切分而需要被删除的三角形面AIFFace和三角形边AIFEdge对象，要先查找AIFEdge对象内顶点AIFVertex对象中该AIFEdge对象，并把它从顶点的入射边列表中删除；同样，首先要从AIFFace对象内边AIFEdge对象的入射面AIFFace列表中找到该AIFFaceAIFEdge对象，并把它从边的入射面列表中删除。这样，才能真正地删除被切分到的三角形面AIFFace和三角形边AIFEdge对象。
所述新添加的三角形，采用三角形顶点连接顺序继承方法来保持新产生的三角形具有原来三角形的法方向。继承方法主要是考虑到三角形顶点连接呈环状，具有顺时针或者逆时针两种连接模式，只需要继承原三角形，即被切割三角形某一个边的连接关系，就可以确定整个三角形顶点的连接顺序。
在网格重建的过程中，存在一个极其特殊的情况，即采样点（即切割线）与三角形的两个顶点（一条边）完全重合，经过了两个及两个以上的三角形。该情况存在着采样点只经过三角形一个顶点的问题，并且这个模式并不是基本模式分
类中的一种，需要利用以下方法来实现其网格重建，具体步骤为：
步骤l:选择一个被切割到边的三角形为起始三角形，通过切割的边以及交汇的切割点査询到三角形的另一条边，和该边的另一个入射三角形；
步骤2:察看新查询到的三角形与另一个被切割到边的三角形（非起始三角形）是否相同，如果相同则转到步骤4，否则继续；
步骤3:修改该查询到的三角形共享的顶点信息，然后继续査找以共享顶点为端点，即入射于共享顶点的另一个三角形边，和该边的另一个入射三角形；重复步骤2;
步骤4:结束处理。
本发明都是在AIF结构的顶点、边、面三种列表元素中进行的数据查询与处理，因此实现网格重建的过程，仅仅通过修改部分的几何片元及其连接关系的信息，就得到了全新的三角形网格数据。整个网格重建的处理只关注于"有效"三角形部分，因此工作量非常有限，使得网格重建的速度很快。
本发明通过以上设计方法发现：（l)采用AIF结构来进行切割后的网格重建只需要修改切割路径经过的三角形以及这些三角形的部分相邻三角形，这样即使三角形网格数目增加，最终影响处理时间的三角形个数还是有限规模的，并不与
三角形网格模型的数据量呈现任何关系。（2)采用新增三角形继承原始三角形网
格顶点连接顺序，可以省去新三角形法方向的判断处理，保持新产生切割路径周过程中， 利用模式匹配的方法，对原始的AIF结构中由面査询入射顶点进行了修正，利用 边入射顶点集的模式匹配获得保持三角形正确法方向的顶点顺序。这样充分发挥 了 AIF的快速拓扑结构査询特点，也大大提高了网格重建的速度以及各种数据规 模下网格重建速度的稳定性能。 附图说明
图1为网格重建4种基本模式图，
其中：双线表示切割路径，单线表示重新构建的三角形边缘；A采样点在三 角形的任意两条边上，B某一个采样点交于三角形任意一个顶点上，而另一个采 样点则交在该顶点的对边上，C某一个采样点交于三角形任意一条边上，而另外 一个顶点则落在三角形内部，D两个采样点都落在三角形任意两个顶点上，这样 的情况可能产生完全切割。
图2为网络重建的特殊情况，双线表示切割路径。
图3为切割后网格重建面绘制以及边绘制结果图。
本发明是通过以下技术方案实现的，首先将传统的三角形三维网格模型数据表现形式转化为具有邻接入射关系的AIF数据结构形式，并进一步对该形式的数据进行网格模型重建处理。在处理的过程中，先将切割路径经过的三角形网格模式化分类，然后根据分类的结果再进行快速的AIF结构査询和修改，最终获得全新的切分后网格数据，实现切割体的网格重建。
所述把传统的三角形三维网格模型数据表现形式转化为具有邻接入射关系的AIF数据结构形式，具体步骤为-
- 首先获取原始的三角形网格模型数据，其存储的形式为一个含有所有顶点坐标的一维数组以及一个含有所有三角形面片的顶点索引的一维数组；
然后根据三角形每一个顶点建立一个相应的顶点AIFVertex对象，其数据内容为顶点三维坐标，顶点的法方向坐标，顶点为端点的所有边对象列表，即入射于该顶点的所有边对象列表，根据原始数据，可以填写每一个顶点AIFVertex对象的三维坐标以及法方向坐标；接下来，建立一张边信息的査询表，遍历所有三角形面片的顶点索引的一维数组，分别将每个三角形顶点两两成对，按两个顶点的索引升序排列，组成一对信息，把此对信息在已经建立的边信息查询表中进行查找，如果信息没有匹配到，则生成一个新的边AIFEdge对象并填写其顶点信息，如果已经存在，则更新边信息查询表以及边AIFEdge对象，顶点对象信息，其中，边AIFEdge结构包含有边的两个顶点对象，入射于边的面列表，每完成一个三角形面片的边操作时，将这些边构造成邻接边列表，存储在三角形面AIFFace对象中；
最终，当扫描完所有的三角形面片，就可以实现原始数据到新的AIF邻接入射关系结构的转化。
所述将切割路径经过的三角形网格模式化分类，具体为：首先假定每一个三角形面片至多仅有两个采样点，并且采样频率相对于整个三角形网格模型的规模足够高。从而，可以将采样点与三角形的位置关系概括为四种基本情况，S卩：（1)采样点在三角形的任意两条边上，这样是对三角形实现了完全切割；（2)某一个采样点交于三角形任意一个顶点上，而另一个采样点则交在该顶点的对边上，这样也可能产生完全切割；（3)某一个采样点交于三角形任意一条边上，而另外一个顶点则落在三角形内部，这样的情况产生了不完全切割；（4)两个采样点都落在三角形任意两个顶点上，这样的情况可能产生完全切割。由于模式化分类只是限定了采样点即切割线穿越三角形的模式，任何一个情况都可以经过旋转的方式去匹配这个分类，所以在之后的处理步骤上，具有概括抽象的先导作用。
所述根据分类的结果再进行快速的AIF结构查询和修改，最终获得全新的切分后网格数据，具体步骤为：
首先构造基本分类模式，获得三角形面、边、顶点的增减模式；
然后根据既定的增减模式，先对由于切割而添加的三角形顶点AIFVertex对象进行创建，再创建新添加的三角形。在创建新三角形面AIFFace的过程中，需要通过三角形每两个AIFVertex对进行组合查询，即匹配两个AIFVertex对象中入射边列表是否有相同内容，如果存在，则直接填写入新的AIFFace对象中，如果不存在，则创建一个新的AIFEdge对象，然后填写入新的AIFFace对象中。
最后，对于由于切分而需要被删除的三角形面AIFFace和三角形边AIFEdge对象，要先查找AIFEdge对象内顶点AIFVertex对象中该AIFEdge对象，并把它从顶点的入射边列表中删除；同样，首先要从AIFFace对象内边AIFEdge对象的入射面AIFFace列表中找到该AIFFaceAIFEdge对象，并把它从边的入射面列表中删除。这样，才能真正地删除被切分到的三角形面AIFFace和三角形边AIFEdge对象。
所述新添加的三角形，采用三角形顶点连接顺序继承方法来保持新产生的三角形具有原来三角形的法方向。继承方法主要是考虑到三角形顶点连接呈环状，具有顺时针或者逆时针两种连接模式，只需要继承原三角形，即被切割三角形某一个边的连接关系，就可以确定整个三角形顶点的连接顺序。
在网格重建的过程中，存在一个极其特殊的情况，即采样点（即切割线）与三角形的两个顶点（一条边）完全重合，经过了两个及两个以上的三角形。该情况存在着采样点只经过三角形一个顶点的问题，并且这个模式并不是基本模式分
类中的一种，需要利用以下方法来实现其网格重建，具体步骤为：
步骤l:选择一个被切割到边的三角形为起始三角形，通过切割的边以及交汇的切割点査询到三角形的另一条边，和该边的另一个入射三角形；
步骤2:察看新查询到的三角形与另一个被切割到边的三角形（非起始三角形）是否相同，如果相同则转到步骤4，否则继续；
步骤3:修改该查询到的三角形共享的顶点信息，然后继续査找以共享顶点为端点，即入射于共享顶点的另一个三角形边，和该边的另一个入射三角形；重复步骤2;
步骤4:结束处理。
本发明都是在AIF结构的顶点、边、面三种列表元素中进行的数据查询与处理，因此实现网格重建的过程，仅仅通过修改部分的几何片元及其连接关系的信息，就得到了全新的三角形网格数据。整个网格重建的处理只关注于"有效"三角形部分，因此工作量非常有限，使得网格重建的速度很快。
本发明通过以上设计方法发现：（l)采用AIF结构来进行切割后的网格重建只需要修改切割路径经过的三角形以及这些三角形的部分相邻三角形，这样即使三角形网格数目增加，最终影响处理时间的三角形个数还是有限规模的，并不与
三角形网格模型的数据量呈现任何关系。（2)采用新增三角形继承原始三角形网
格顶点连接顺序，可以省去新三角形法方向的判断处理，保持新产生切割路径周过程中， 利用模式匹配的方法，对原始的AIF结构中由面査询入射顶点进行了修正，利用 边入射顶点集的模式匹配获得保持三角形正确法方向的顶点顺序。这样充分发挥 了 AIF的快速拓扑结构査询特点，也大大提高了网格重建的速度以及各种数据规 模下网格重建速度的稳定性能。 附图说明
图1为网格重建4种基本模式图，
其中：双线表示切割路径，单线表示重新构建的三角形边缘；A采样点在三 角形的任意两条边上，B某一个采样点交于三角形任意一个顶点上，而另一个采 样点则交在该顶点的对边上，C某一个采样点交于三角形任意一条边上，而另外 一个顶点则落在三角形内部，D两个采样点都落在三角形任意两个顶点上，这样 的情况可能产生完全切割。
图2为网络重建的特殊情况，双线表示切割路径。
图3为切割后网格重建面绘制以及边绘制结果图。
具体实施方式
下面结合附图对本发明的实施例作详细说明：本实施例在以本发明技术方案
为前提下进行实施，给出了详细的实施方式和具体的操作过程，但本发明的保护 范围不限于下述的实施例。
本实施例采用〔++语言实现并在具有CPU 3. 0 GHz ，内存1024MB的Pentium 4个人电脑上对个数为1， 435， 325个的三角形网格数据进行测试。 具体处理过程如下： 1、表面模型转化
首先根据AIF结构的基本定义方式，利用〔++语言定义如下的数据结构：
typedef vectorstruct ctmAIFVertex{ P0INT3DXYZ m—xPoint; 〃double[3] VECT0R3DXYZ m—xNormal; 〃double[3] evector m—xLine—i; //incident edgesstruct ctmAIFEdge{ ctmAIFVertex氺m—pPointl; ctmAIFVertex* m_pPoint2; fvector m一xFace—i;//incident faces
}; 一
struct ctmAIFFace{
evector m—xEdge—a://adjacent edges }; 一 — .
struct ctraAIFMesh{ vvector m一xVertex; evector m一xEdges: fvector m一xFaces;
其次，就是根据原始的三角形网格顶点索引格式完成表面模型的转化。其主 要方法是首先将创建一个ctmAIFVertex列表，每一个元素的空间坐标和法向量 可以通过复制获得。然后依次读取三角形索引表中每一个三角形，并且创建一个 新的ctmAIFFace对象，'同时分别遍历三角形的3个顶点，获得顶点对应于 ctmAIFVertex列表中的指针，每两个顶点进行一次査询操作，如果顶点已经构 成ctmAIFEdge对象，则不需要创建，否则创建新的ctmAIFEdge对象，然后完成 该ctmAIFEdge对象的顶点指针和面列表的添加。最后，把这些边元素添加到该 三角形面ctmAIFFace对象的邻接边列表中，完成表面模型从顶点索引式到AIF 网格模型的转化。
原始数据到AIF数据结构的转化示范性伪代码：
函数名：102AIFMesh
输入：ra一unVertices顶点数组的个数
m一unTriangles三角形面数组的个数 m_ppt3dVertices顶点坐标数组首指针 tiU)vec3dNormals顶点法向量数组首指针 . m一piTrianglelndices三角形面顶点索引数组首指针 输出：m_xVertex AIFVertex顶点对象列表 m—xEdge AIFEdge边对象列表 m_xFace AIFFace面对象列表102AIFMesh()
For每一个m—ppt3dVertices元素禾口 m—pvec3dNormals
创建AIFVertex对象，并添加到m—xVertex列表中；
创建一个基于AIFVertex对以及AIFEdge对象的查询表edgetable; For每一个m_piTriangleIndices元素
{
创建AIFFace对象； For三角形每一条边 {
获得边的两个顶点索引，及顶点AIFVertex对象； 将顶点AIFVertex对象按照索引的升序排列； 査询edgetable是否存在此条记录； K存在
获取AIFEdge对象，并添加到两个AIFVertex对象的入射边列表中； Else不存在
创建一个新的AIFEdge对象，添加到查询表中，再添加到两个AIFVertex对 象的入射边列表中；
将AIFEdge对象添加到AIFFace对象的邻接边列表中；
同时，需要定义AIF查询函数，用来实现由点、边、面任意一几何元素对其 邻接、入射关系的几个元素的査询。 2、切割模式分类
如图1所示，将切割路径经过的三角形网格按照4种基本模式分类，用计算
清空edgetable表5机实现时可以拓展分类，利用切割线端点与三角形边的相交方式分成O， 1， 2三 种情况，0表示没有交点，即采样点在三角形内部；l表示采样点与三角形边相 交于边的内部；2表示采样点与三角形两条边相交，即采样点与三角形的顶点重 合。每一条切割线段一共有2个端点，即切割线具有至多两个采样点，如此利用 排列组合思想展开模式，从而实现基本分类。在这个过程中，要注意其中{0， 0} 组合并不存在，其代表没有产生切割，不需要考虑。因此最终得到的组合内容如 下：
{0， 1}， {1， 0}， {0, 2}， {2， 0}， {1, 2}， {2， 1}， {1， 1}， {2， 2}。模式分 类的设计中把旋转、对称等情况进行的概括总结，而在本实施例中为了方便计算 机语言对于设计的实现，进行了进一步的细化。 3、网格重建中数据处理
本实施例在进行网格重建的数据处理过程中，主要通过计算机程序代码实现 了发明中的3个主要设计。其一是对于切割所涉及到的三角形AIF邻接入射结构 数据的网格重建与修正UnitRemesh函数和Rene满esh函数；其二是对于切割所 涉及到的三角形顶点连接顺序（即法向量）中采用的继承思想，用SPLITPNT数 据结构实现；其三是对特殊化的切割情况设计流程的函数UnitRemesh22实现， 所述特殊化的切割情况即采样点（即切割线）与三角形的两个顶点（一条边）完 全重合，经过了两个及两个以上的三角形，见附图2。
对于切割所涉及到的三角形AIF邻接入射结构数据的网格重建与修正示范 性伪代码-
函数名：UnitR匿sh
输入：vertices [3] AIFVertex顶点对象数组
mesh修正前的AIFMesh网格对象 输出：mesh修正后的AIFMesh网格对象 UnitRemesh ()
创建一个新的三角形AIFFace对象； For每一条三角形边查询获得vertices数组中两个顶点的边对象；
If不存在，即边对象为空
{
创建一个新的AIFEdge对象，添加到两个顶点的入射边列表中； 把AIFEdge添加到mesh的m—xEdge列表中；
把AIFEdge边对象添加到AIFFace对象的邻接边列表中； 把AIFFace对象添加到AIFEdge对象的入射面列表中；
把AIFFace对象添加到mesh的m一xFace列表中；
其中査询获得vertices数组中两个顶点的边对象是通过
重勺
的集合运算得到。
函数名：RenewMeshUnitRemesh
输入：edge被切割到需要删除AIFEdge边象数组
Face被切割到需要删除AIFFace面象数组
mesh修正前的AIFMesh网格对象 输出：mesh修正后的AIFMesh网格对象 RenewMeshUnitRemesh 0
査询到与edge邻接的两个顶点AIFVertex对象；
删除AIFVertex对象中入射边列表含有edge的对象；
査询到与edge入射的面AIFFace对象；
删除AIFFace对象中邻接边列表含有edge的对象；
査询到与face邻接的3个AIFEdge对象；
删除AIFEdge对象中入射面列表的face对象；
从mesh中tn一xEdge列表中删除edge对象；从mesh中m一xFace列表中删除face对象；
其中查询到与edge邻接的两个顶点AIFVertex对象是通过 M。(W丄i,^，7^/Z丄）^ {^,1;2}的集合运算得到；査询到与edge入射的面
AIFFace对象是通过MjiVC/i^,q,iVC/i:丄）={/;，/;+1}的集合运算得到；查询到
与face邻接的3个A工FEdge对象是通过^Kl,(W丄i:, W丄丄,/) = {el5e2，e3} 的集合运算得到。
本实施例中对于切割所涉及到的新三角形顶点连接顺序的继承思想，是用 SPLITPNT数据结构实现。SPLITPNT结构利用〔++语言定义如下： struct SPLITPNTA分裂点V
ctmAIFVertex本vertex;/氺顶点指针氺/ int vertex—index;/承顶点索弓iV ctmAIFVertex氺splitpnt ;/氺分裂;^f旨针承/ int splitpnt一index;/氺分裂点索弓l伞/
在实现继承方法的时候，将分割点的对象保存在splitpnt中，然后将与之 构造新的三角形边的顶点以及顶点的索引号保存在vertex和vertex—index中， 而将原先与vertex组成三角形边的另一个顶点索引号赋值给splitpnt—index, 这样的操作就实现了对于新增分割后三角形继承原始三角形连接顺序的设计。在 构造新的三角形过程中，只需要根据这vertexjndex和splitpnt—index的序号 顺序确定新的三角形连接顺序，其可能的所有顺序组合为{0, 1}, {1， 2}， {2， 0}，最终实现了新的三角形法方向与原始方向的一致性。
对特殊化的切割情况设计流程的示范性伪代码-
函数名：UnitRemesh22
输入：front一face前一个被切割到边的三角形 end_face 后一个被切割到边的三角形mesh修正前的AIFMesh网格对象 输出：mesh修正后的AIFMesh网格对象 UnitRemesh22 ()
査询front—face的后一个采样点所入射的所有边； 査询front—face的所有邻接边；
获得两种边列表的交集，取得不含有前一个采样点的边e; 查询与边e入射非front_face的三角形tempface; While tempface不等于endface
根据front—face的内容修改te卿face顶点AIFVertex， AIFEdge， AIFFace内相关参数；
将tempface设置为front—face;
査询front—face的后一个采样点所入射的所有边；
查询front_face的所有邻接边；
获得两种边列表的交集，取得不含有前一个采样点的边e; 査询与边e入射非front—face的三角形tempface;
其中查询fr0nt_face的后一个采样点所入射的所有边是
^^(^,ivw:i:，A^i:丄）={ey...}的集合运算得到。
通过以上主要步骤，本实施例实现最终的局部网格重建，只需要在列表中删 除三角形面、边以及相关的信息，然后添加顶点、边、面就可以实现整个网格结 构的修改，计算仅仅涉及到切割路径周围的三角形网格，大大节省了运算量，降 低了三角形数目与网格重建运算量之间的耦合关系，本实施例结果如附图3所 示。
由以上实施例可以看出，本发明在AIF结构基础上，首先将传统的三角形网 格顶点索引模式进行转换构造得到AIF结构模型，其次将切割模式进行了分类， 简化了实现的复杂度，最后利用AIF快速高效的査询以及本身存储的结构特点，用局部的网格重建来实现切割体的网格重建。本发明避免了切割过程中全局性的 修正网格，充分利用AIF结构特点，以局部网格重建实现拓扑结构的改变，从而 有效地提高了三角形网格切割时网格重建的速度，并且该速度不随三角形网格数 据量规模而改变，能达到很好的稳定性，尤其是对大规模数据有着较快的处理速 度和较好的质量。
为前提下进行实施，给出了详细的实施方式和具体的操作过程，但本发明的保护 范围不限于下述的实施例。
本实施例采用〔++语言实现并在具有CPU 3. 0 GHz ，内存1024MB的Pentium 4个人电脑上对个数为1， 435， 325个的三角形网格数据进行测试。 具体处理过程如下： 1、表面模型转化
首先根据AIF结构的基本定义方式，利用〔++语言定义如下的数据结构：
typedef vector
}; 一
struct ctmAIFFace{
evector m—xEdge—a://adjacent edges }; 一 — .
struct ctraAIFMesh{ vvector m一xVertex; evector m一xEdges: fvector m一xFaces;
其次，就是根据原始的三角形网格顶点索引格式完成表面模型的转化。其主 要方法是首先将创建一个ctmAIFVertex列表，每一个元素的空间坐标和法向量 可以通过复制获得。然后依次读取三角形索引表中每一个三角形，并且创建一个 新的ctmAIFFace对象，'同时分别遍历三角形的3个顶点，获得顶点对应于 ctmAIFVertex列表中的指针，每两个顶点进行一次査询操作，如果顶点已经构 成ctmAIFEdge对象，则不需要创建，否则创建新的ctmAIFEdge对象，然后完成 该ctmAIFEdge对象的顶点指针和面列表的添加。最后，把这些边元素添加到该 三角形面ctmAIFFace对象的邻接边列表中，完成表面模型从顶点索引式到AIF 网格模型的转化。
原始数据到AIF数据结构的转化示范性伪代码：
函数名：102AIFMesh
输入：ra一unVertices顶点数组的个数
m一unTriangles三角形面数组的个数 m_ppt3dVertices顶点坐标数组首指针 tiU)vec3dNormals顶点法向量数组首指针 . m一piTrianglelndices三角形面顶点索引数组首指针 输出：m_xVertex AIFVertex顶点对象列表 m—xEdge AIFEdge边对象列表 m_xFace AIFFace面对象列表102AIFMesh()
For每一个m—ppt3dVertices元素禾口 m—pvec3dNormals
创建AIFVertex对象，并添加到m—xVertex列表中；
创建一个基于AIFVertex对以及AIFEdge对象的查询表edgetable; For每一个m_piTriangleIndices元素
{
创建AIFFace对象； For三角形每一条边 {
获得边的两个顶点索引，及顶点AIFVertex对象； 将顶点AIFVertex对象按照索引的升序排列； 査询edgetable是否存在此条记录； K存在
获取AIFEdge对象，并添加到两个AIFVertex对象的入射边列表中； Else不存在
创建一个新的AIFEdge对象，添加到查询表中，再添加到两个AIFVertex对 象的入射边列表中；
将AIFEdge对象添加到AIFFace对象的邻接边列表中；
同时，需要定义AIF查询函数，用来实现由点、边、面任意一几何元素对其 邻接、入射关系的几个元素的査询。 2、切割模式分类
如图1所示，将切割路径经过的三角形网格按照4种基本模式分类，用计算
清空edgetable表5机实现时可以拓展分类，利用切割线端点与三角形边的相交方式分成O， 1， 2三 种情况，0表示没有交点，即采样点在三角形内部；l表示采样点与三角形边相 交于边的内部；2表示采样点与三角形两条边相交，即采样点与三角形的顶点重 合。每一条切割线段一共有2个端点，即切割线具有至多两个采样点，如此利用 排列组合思想展开模式，从而实现基本分类。在这个过程中，要注意其中{0， 0} 组合并不存在，其代表没有产生切割，不需要考虑。因此最终得到的组合内容如 下：
{0， 1}， {1， 0}， {0, 2}， {2， 0}， {1, 2}， {2， 1}， {1， 1}， {2， 2}。模式分 类的设计中把旋转、对称等情况进行的概括总结，而在本实施例中为了方便计算 机语言对于设计的实现，进行了进一步的细化。 3、网格重建中数据处理
本实施例在进行网格重建的数据处理过程中，主要通过计算机程序代码实现 了发明中的3个主要设计。其一是对于切割所涉及到的三角形AIF邻接入射结构 数据的网格重建与修正UnitRemesh函数和Rene满esh函数；其二是对于切割所 涉及到的三角形顶点连接顺序（即法向量）中采用的继承思想，用SPLITPNT数 据结构实现；其三是对特殊化的切割情况设计流程的函数UnitRemesh22实现， 所述特殊化的切割情况即采样点（即切割线）与三角形的两个顶点（一条边）完 全重合，经过了两个及两个以上的三角形，见附图2。
对于切割所涉及到的三角形AIF邻接入射结构数据的网格重建与修正示范 性伪代码-
函数名：UnitR匿sh
输入：vertices [3] AIFVertex顶点对象数组
mesh修正前的AIFMesh网格对象 输出：mesh修正后的AIFMesh网格对象 UnitRemesh ()
创建一个新的三角形AIFFace对象； For每一条三角形边查询获得vertices数组中两个顶点的边对象；
If不存在，即边对象为空
{
创建一个新的AIFEdge对象，添加到两个顶点的入射边列表中； 把AIFEdge添加到mesh的m—xEdge列表中；
把AIFEdge边对象添加到AIFFace对象的邻接边列表中； 把AIFFace对象添加到AIFEdge对象的入射面列表中；
把AIFFace对象添加到mesh的m一xFace列表中；
其中査询获得vertices数组中两个顶点的边对象是通过
重勺
的集合运算得到。
函数名：RenewMeshUnitRemesh
输入：edge被切割到需要删除AIFEdge边象数组
Face被切割到需要删除AIFFace面象数组
mesh修正前的AIFMesh网格对象 输出：mesh修正后的AIFMesh网格对象 RenewMeshUnitRemesh 0
査询到与edge邻接的两个顶点AIFVertex对象；
删除AIFVertex对象中入射边列表含有edge的对象；
査询到与edge入射的面AIFFace对象；
删除AIFFace对象中邻接边列表含有edge的对象；
査询到与face邻接的3个AIFEdge对象；
删除AIFEdge对象中入射面列表的face对象；
从mesh中tn一xEdge列表中删除edge对象；从mesh中m一xFace列表中删除face对象；
其中查询到与edge邻接的两个顶点AIFVertex对象是通过 M。(W丄i,^，7^/Z丄）^ {^,1;2}的集合运算得到；査询到与edge入射的面
AIFFace对象是通过MjiVC/i^,q,iVC/i:丄）={/;，/;+1}的集合运算得到；查询到
与face邻接的3个A工FEdge对象是通过^Kl,(W丄i:, W丄丄,/) = {el5e2，e3} 的集合运算得到。
本实施例中对于切割所涉及到的新三角形顶点连接顺序的继承思想，是用 SPLITPNT数据结构实现。SPLITPNT结构利用〔++语言定义如下： struct SPLITPNTA分裂点V
ctmAIFVertex本vertex;/氺顶点指针氺/ int vertex—index;/承顶点索弓iV ctmAIFVertex氺splitpnt ;/氺分裂;^f旨针承/ int splitpnt一index;/氺分裂点索弓l伞/
在实现继承方法的时候，将分割点的对象保存在splitpnt中，然后将与之 构造新的三角形边的顶点以及顶点的索引号保存在vertex和vertex—index中， 而将原先与vertex组成三角形边的另一个顶点索引号赋值给splitpnt—index, 这样的操作就实现了对于新增分割后三角形继承原始三角形连接顺序的设计。在 构造新的三角形过程中，只需要根据这vertexjndex和splitpnt—index的序号 顺序确定新的三角形连接顺序，其可能的所有顺序组合为{0, 1}, {1， 2}， {2， 0}，最终实现了新的三角形法方向与原始方向的一致性。
对特殊化的切割情况设计流程的示范性伪代码-
函数名：UnitRemesh22
输入：front一face前一个被切割到边的三角形 end_face 后一个被切割到边的三角形mesh修正前的AIFMesh网格对象 输出：mesh修正后的AIFMesh网格对象 UnitRemesh22 ()
査询front—face的后一个采样点所入射的所有边； 査询front—face的所有邻接边；
获得两种边列表的交集，取得不含有前一个采样点的边e; 查询与边e入射非front_face的三角形tempface; While tempface不等于endface
根据front—face的内容修改te卿face顶点AIFVertex， AIFEdge， AIFFace内相关参数；
将tempface设置为front—face;
査询front—face的后一个采样点所入射的所有边；
查询front_face的所有邻接边；
获得两种边列表的交集，取得不含有前一个采样点的边e; 査询与边e入射非front—face的三角形tempface;
其中查询fr0nt_face的后一个采样点所入射的所有边是
^^(^,ivw:i:，A^i:丄）={ey...}的集合运算得到。
通过以上主要步骤，本实施例实现最终的局部网格重建，只需要在列表中删 除三角形面、边以及相关的信息，然后添加顶点、边、面就可以实现整个网格结 构的修改，计算仅仅涉及到切割路径周围的三角形网格，大大节省了运算量，降 低了三角形数目与网格重建运算量之间的耦合关系，本实施例结果如附图3所 示。
由以上实施例可以看出，本发明在AIF结构基础上，首先将传统的三角形网 格顶点索引模式进行转换构造得到AIF结构模型，其次将切割模式进行了分类， 简化了实现的复杂度，最后利用AIF快速高效的査询以及本身存储的结构特点，用局部的网格重建来实现切割体的网格重建。本发明避免了切割过程中全局性的 修正网格，充分利用AIF结构特点，以局部网格重建实现拓扑结构的改变，从而 有效地提高了三角形网格切割时网格重建的速度，并且该速度不随三角形网格数 据量规模而改变，能达到很好的稳定性，尤其是对大规模数据有着较快的处理速 度和较好的质量。