由电子设备执行的追踪曲面交线方法及装置、电子设备

1.本发明涉及计算机曲面求交技术领域，具体地涉及一种由电子设备执行的追踪曲面交线方法及装置、电子设备。


背景技术：

2.求有理参数曲面和有理参数曲面的交(ssi)是几何和实体建模中最基本的问题之一。有理曲面求交在表示复杂对象、有限元离散化、计算机动画、面部识别等方面是较为重要且常用的，两个参数曲面的交可能具有极其复杂的拓扑性质，如切点，切线，孤立点微小环路，自交点，甚至部分曲面重合，在某些极端情况下，这些奇异的情况会混合在一起，并且在实际系统中实现浮点运算时，不可避免的数值误差回事它们的计算更加复杂。所有这些情况都需要在近交互时间内在复杂几何运算下进行鲁棒处理，这对参数ssi问题的鲁棒性，准确性和效率提出了严峻的挑战。
3.常规曲面求交算法没有考虑到针对各种奇异的情形的拓扑情况，因此无法较好地完成各种场景下下复杂曲面相交情况下的实体建模，建模准确性较低。且由于计算复杂，常规算法无法在较短的时间内以较小的误差完成计算，甚至即便消耗大量的计算资源也根本无法得出计算结果。


技术实现要素：

4.鉴于上述问题，本发明提供了一种由电子设备执行的追踪曲面交线方法及装置、电子设备。
5.本发明的一个方面，提供了一种由电子设备执行的追踪曲面交线的方法，包括：
6.响应于控制器生成的控制指令，通过运算器基于控制指令根据第一参数曲面的函数模型和第二参数曲面的函数模型，生成与第一参数曲面和第二参数曲面关联的四维空间参数曲线，将四维空间参数曲线存储在寄存器中；
7.通过运算器基于控制指令，将第一参数曲面对应的参数空间划分为多个第一曲面盒子，以及将第二参数曲面对应的参数空间划分为多个第二曲面盒子，以使得将多个第一曲面盒子和多个第二曲面盒子中相交的盒子确定为目标盒子，并将目标盒子存储在寄存器中；
8.通过运算器基于控制指令，从寄存器中读取四维空间参数曲线，并构建针对四维空间参数曲线的切向量函数模型，将切向量函数模型存储在寄存器中；
9.通过运算器基于控制指令，从寄存器中读取切向量函数模型，并基于切向量函数模型建立第一判定条件和第二判定条件，以使得将满足第一判定条件的目标盒子标记为第一类盒子，将满足第二判定条件的目标盒子标记为第二类盒子，将目标盒子中除第一类盒子和第二类盒子之外的目标盒子标记为第零类盒子；
10.通过运算器基于控制指令，分别生成第一类盒子、第二类盒子、第零类盒子中的多个追踪点，并将多个追踪点连接以生成第一参数曲面和第二参数曲面的交线；
11.通过显示单元展示第一参数曲面和第二参数曲面的交线。
12.根据本发明的实施例，第一参数曲面和第二参数曲面为基于多种类型的曲面实体，并按照预定制图比例建立的参数曲面，多种类型的曲面实体至少包括：机械元件曲面实体、人体部位曲面实体、动画对象曲面实体。
13.根据本发明的实施例，基于切向量函数模型建立第一判定条件和第二判定条件包括：
14.通过运算器基于控制指令，将目标盒子输入切向量函数模型，输出目标解集，将目标解集存储在寄存器中；
15.通过运算器基于控制指令，从寄存器中读取目标解集，并利用与切向量函数模型相关的目标解集建立第一判定条件和第二判定条件。
16.根据本发明的实施例，其中：
17.切向量函数模型包括第一分向量函数模型、第二分向量函数模型、第三分向量函数模型、第四分向量函数模型；
18.利用切向量函数模型输出的目标解集包括：通过第一分向量函数模型输出的第一解集、通过第二分向量函数模型输出的第二解集、通过第三分向量函数模型输出的第三解集、通过第四分向量函数模型输出的第四解集：
19.第一判定条件为：第一解集和第二解集的交集中存在零解，或者第三解集和第四解集的交集中存在零解；
20.第二判定条件为：在第一解集、第二解集、第三解集、第四解集的交集中存在零解。
21.根据本发明的实施例，分别生成第一类盒子、第二类盒子、第零类盒子中的多个追踪点包括：
22.针对第二类盒子生成多个不同类型的第二追踪点，多个不同类型的第二追踪点至少包括：在第一参数曲面和第二参数曲面相切于点的情况下的切点、在第一参数曲面和第二参数曲面相切于曲线的情况下的切点、在第一参数曲面和第二参数曲面重合的情况下的切点、在第一参数曲面和第二参数曲面相切于孤立切点的情况下的切点、在第一参数曲面和第二参数曲面相切于极小环的情况下的切点；
23.通过追踪第零类盒子生成多个零类追踪点，零类追踪点为在第一参数曲面或第二参数曲面正则相交情况下的正则交点；
24.针对第一类盒子生成多个不同类型的第一追踪点，多个不同类型的第一追踪点至少包括：在第一参数曲面或第二参数曲面上存在的有限个奇异点、在第一参数曲面或第二参数曲面上存在的奇异曲线上的奇异点；
25.从第零类盒子中确定第三类盒子，以使得针对第三类盒子生成多个第三追踪点，第三追踪点为第一参数曲面或第二参数曲面的自交点。
26.根据本发明的实施例，其中，针对第二类盒子生成多个不同类型的第二追踪点包括：
27.根据切向量函数模型和四维空间参数曲线构建第二判别函数系统；
28.根据第二判别函数系统的解的数量，将第二类盒子进行细分，以根据细分后的第二类盒子生成多个不同类型的第二追踪点。
29.根据本发明的实施例，其中，针对第一类盒子生成多个不同类型的第一追踪点包
括：
30.针对第一参数曲面或者第二参数曲面，构建子函数系统；
31.根据子函数系统和四维空间参数曲线构建第一判别函数系统；
32.根据第一判别函数系统的解的数量，将第一类盒子进行细分，以根据细分后的第一类盒子生成多个不同类型的第一追踪点。
33.根据本发明的实施例，其中，从第零类盒子中确定第三类盒子包括：
34.基于切向量函数模型建立第三判定条件，其中，第三判定条件为：满足第一子条件、第二子条件、第三子条件、第四子条件的至少之一；第一子条件为：第一解集中不存在零解，并且第三解集中不存在零解；第二子条件：第一解集中不存在零解，并且第四解集中不存在零解；第三子条件为：第二解集中不存在零解，并且第三解集中不存在零解；第四子条件为：第二解集中不存在零解，并且第四解集中不存在零解；
35.将满足第三判定条件的第零类盒子确定为排除盒子，并将第零类盒子中除排除盒子和正则盒子之外的盒子确定为第三类盒子，其中正则盒子为零类追踪点对应的盒子。
36.本发明的另一个方面提供了一种追踪曲面交线的装置，包括：
37.第一生成模块，用于响应于控制器生成的控制指令，通过运算器基于控制指令根据第一参数曲面的函数模型和第二参数曲面的函数模型，生成与第一参数曲面和第二参数曲面关联的四维空间参数曲线，将四维空间参数曲线存储在寄存器中；
38.划分模块，用于通过运算器基于控制指令，将第一参数曲面对应的参数空间划分为多个第一曲面盒子，以及将第二参数曲面对应的参数空间划分为多个第二曲面盒子，以使得将多个第一曲面盒子和多个第二曲面盒子中相交的盒子确定为目标盒子，并将目标盒子存储在寄存器中；
39.构建模块，用于通过运算器基于控制指令，从寄存器中读取四维空间参数曲线，并构建针对四维空间参数曲线的切向量函数模型，将切向量函数模型存储在寄存器中；
40.标记模块，用于通过运算器基于控制指令，从寄存器中读取切向量函数模型，并基于切向量函数模型建立第一判定条件和第二判定条件，以使得将满足第一判定条件的目标盒子标记为第一类盒子，将满足第二判定条件的目标盒子标记为第二类盒子，将目标盒子中除第一类盒子和第二类盒子之外的目标盒子标记为第零类盒子；
41.第二生成模块，用于通过运算器基于控制指令，分别生成第一类盒子、第二类盒子、第零类盒子中的多个追踪点，并将多个追踪点连接以生成第一参数曲面和第二参数曲面的交线；
42.展示模块，用于通过显示单元展示第一参数曲面和第二参数曲面的交线。
43.本发明的另一个方面提供了一种电子设备，包括：一个或多个处理器；存储器，用于存储一个或多个程序，其中，当所述一个或多个程序被所述一个或多个处理器执行时，使得一个或多个处理器执行上述方法。
44.本发明的上述追踪曲面交线的方法通过建立混合的符号-数字框架来获得拓扑正确，并且在混合的情况下，通过基于切向量函数模型建立第一判定条件和第二判定条件，进行空间盒子区分，通过对各种奇异的情形进行区分，可以将多种混合情形简化为单一情形，从而依次将所有奇异的情况找出，能够在建模过程中追踪到各种奇异情形下的交点，从而生成曲面交线，从而保证计算出的交线的拓扑性质，提高几何建模的精确度。上述方法可以
用于复杂曲面求交建模的各种情形，在机械工程建模、有限元离散化，计算机动画建模，面部识别等领域，具有较高的实际应用价值。
45.本发明的上述追踪曲面交线的方法，在计算过程中，通过运算器将第一参数曲面对应的参数空间和第二参数曲面对应的参数空间划分为多个小的盒子(计算区域)，将全局化计算转化为局部计算，因此，可以在运算器中实现多个局部计算的并行计算，进一步地，由于采用并行计算，寄存器上的多个线程可同步执行计算任务，运算器在求解的过程中，提高了计算速度，在较短的时间内即可获得计算结果，同时由于采用局部计算的方法，将大的计算区域划分为多个小的计算区域，在小的计算区域中，函数系统相对比较简单，对计算机寄存器和运算器等硬件的要求也比较低，提高计算速度的同时也降低了硬件成本。
46.进一步地，在运算器计算过程中，通过将多个第一曲面盒子和多个第二曲面盒子中相交的盒子确定为目标盒子，仅针对数量较少的盒子(相交的目标盒子)进行判别以及后续交点追踪，而无需针对曲面空间中的所有盒子进行计算，如此，较大程度上降低了运算器的运算量，提高了运算器的处理效率。同时上述方法中，也仅将目标盒子、以及针对目标盒子的运算结果存储在寄存器中，较大程度上降低了存储空间，降低了对寄存器的硬件要求，提高了存储效率。
附图说明
47.通过以下参照附图对本发明实施例的描述，本发明的上述内容以及其他目的、特征和优点将更为清楚，在附图中：
48.图1示出了根据本发明实施例的追踪曲面交线的方法的流程图；
49.图2示出了曲面相交情况下的三种奇异情形的示意图；
50.图3示出了一个环在由φ定义的曲线上至少有两个点情形的示意图；
51.图4示出了曲面相切情形下各种子情况的决策树；
52.图5示出了使用图4所示决策树来判定的两曲面相切情形下各种子情况的经典情形示意图；
53.图6示出了曲面奇异情形下各种子情况的决策树；
54.图7示出了使用图6所示决策树来判定的曲面奇异情形下各种子情况的经典情形示意图；
55.图8示出了曲面自交情形下各种子情况的决策树；
56.图9示出了使用图8所示决策树来判定的曲面自交情形下各种子情况的经典情形示意图；
57.图10示意性示出了根据本发明实施例的追踪曲面交线的装置的结构框图；
58.图11示意性示出了根据本发明实施例的适于实现追踪曲面交线的方法的电子设备的方框图。
具体实施方式
59.以下，将参照附图来描述本发明的实施例。但是应该理解，这些描述只是示例性的，而并非要限制本发明的范围。在下面的详细描述中，为便于解释，阐述了许多具体的细节以提供对本发明实施例的全面理解。然而，明显地，一个或多个实施例在没有这些具体细
节的情况下也可以被实施。此外，在以下说明中，省略了对公知结构和技术的描述，以避免不必要地混淆本发明的概念。
60.在此使用的术语仅仅是为了描述具体实施例，而并非意在限制本发明。在此使用的术语“包括”、“包含”等表明了所述特征、步骤、操作和/或部件的存在，但是并不排除存在或添加一个或多个其他特征、步骤、操作或部件。
61.在此使用的所有术语(包括技术和科学术语)具有本领域技术人员通常所理解的含义，除非另外定义。应注意，这里使用的术语应解释为具有与本说明书的上下文相一致的含义，而不应以理想化或过于刻板的方式来解释。
62.在使用类似于“a、b和c等中至少一个”这样的表述的情况下，一般来说应该按照本领域技术人员通常理解该表述的含义来予以解释(例如，“具有a、b和c中至少一个的系统”应包括但不限于单独具有a、单独具有b、单独具有c、具有a和b、具有a和c、具有b和c、和/或具有a、b、c的系统等)。
63.本公开实施例的方法可应用在几何实体建模场景下，例如在对机械元件曲面实体、人体部位曲面实体、动画对象等多种类型的复杂曲面实体建模的过程中，经常会遇到两个曲面相交的建模情形，由于曲面几何结构复杂，相交的情形也多种多样，会出现各种类型的奇异情形，例如曲面奇异、曲面相切，孤立点微小环路，自交点，甚至部分曲面重合等，常规曲面求交算法没有考虑到针对各种奇异的情形的拓扑情况，因此无法较好地完成各种场景下下复杂曲面相交情况下的实体建模，建模准确性较低。且由于计算复杂，常规算法无法在较短的时间内以较小的误差完成计算，甚至即便消耗大量的计算资源也根本无法得出计算结果。
64.有鉴于此，本发明提出了一种追踪曲面交线的方法，能够在建模过程中追踪到各种奇异情形下的交点，从而生成曲面交线，从而保证计算出的交线的拓扑性质。
65.图1示出了根据本发明实施例的追踪曲面交线的方法的流程图。
66.如图1所示，该实施例的追踪曲面交线的方法包括操作s101～操作s106。
67.在操作s101，响应于控制器生成的控制指令，通过运算器基于控制指令根据第一参数曲面的函数模型和第二参数曲面的函数模型，生成与第一参数曲面和第二参数曲面关联的四维空间参数曲线，将四维空间参数曲线存储在寄存器中。
68.其中，第一参数曲面r1函数模型如下式(1)：
[0069][0070]
第二参数曲面r2的函数模型如下式(2)：
[0071][0072]
其中(s，t)∈[0，1]
×
[0，1]，(u，v)∈[0，1]
×
[0，1]，s，t，u，v是独立的参数变量，可根据r1(s，t)和r2(u，v)生成与这两个参数曲面对应的四维空间参数曲线ψ，如下式(3)：
[0073][0074]
这就是所计算的四维参数空间中的曲线。
[0075]
将r1，r2相交的曲线定义为相交的曲线定义为可以看作是ψ的映射，该映射为下式(4)或(5)。
[0076][0077][0078]
其中，π1：＝(s，t，u，v)
→
(s，t)，π2：＝(s，t，u，v)
→
(u，v)。其中v(ψ)是ψ在4d参数空间中的点集，之后描述中用ψ代替v(ψ)。
[0079]
在操作s102，通过运算器基于控制指令，将第一参数曲面对应的参数空间划分为多个第一曲面盒子，以及将第二参数曲面对应的参数空间划分为多个第二曲面盒子，以使得将多个第一曲面盒子和多个第二曲面盒子中相交的盒子确定为目标盒子，并将目标盒子存储在寄存器中。
[0080]
具体地，针对两个有理参数曲面r1，r2，分别建立层次包围盒bvh((bounding volume hierarchy)，得到了细分的两个曲面的一些盒子，将两个曲面上的相交的目标盒子放入盒子集合中。如此，方便快速地检查曲面的交线，这些可以为解的范围限制以及函数范围估计服务，并且可以为解的隔离作区间细分。
[0081]
在操作s103，通过运算器基于控制指令，从寄存器中读取四维空间参数曲线，并构建针对四维空间参数曲线的切向量函数模型，将切向量函数模型存储在寄存器中。
[0082]
在交线追踪的过程中，曲线的切向量是非常重要的，对判别交点类型起到重要作用，以下，先计算四维空间参数曲线ψ的切向量，构建针对四维空间参数曲线的切向量函数模型。
[0083]
四维空间参数曲线ψ的jacobian矩阵如下式(6)：
[0084][0085]
那么ψ在p∈[0，1]4处的切向量为：
[0086][0087]
这里的是j
ψ
去掉第i列的行列式。
[0088]
如上式(7)，切向量函数模型包括第一分向量函数模型第二分向量函数模型第三分向量函数模型第四分向量函数模型
[0089]
图2示出了曲面相交情况下的三种奇异情形的示意图。
[0090]
如图2所示，曲面相交情况下的三种奇异情形包括曲面奇异(参考图2中(1)图所示)、曲面相切(参考图2中(2)图所示)、曲面自交的情形(参考图2中(3)图所示)。
[0091]
基于此，通过建立判别条件，将这三种情形关联的盒子先初步区分出来。
[0092]
具体地，在操作s104，通过运算器基于控制指令，从寄存器中读取切向量函数模型，并基于切向量函数模型建立第一判定条件和第二判定条件，以使得将满足第一判定条件的目标盒子标记为第一类盒子c1，将满足第二判定条件的目标盒子标记为第二类盒子c2，将目标盒子中除第一类盒子和第二类盒子之外的目标盒子暂且标记为第零类盒子c0。
[0093]
其中，第一类盒子c1关联有曲面奇异情形，第二类盒子c2关联有曲面相切情形，第零类盒子c0关联有曲面自交情形和正则情形。需要说明的是，在此是将将两个曲面上的相交的目标盒子进行初分类，暂且标记盒子类别，并不代表第一类盒子c1全部是曲面奇异的盒子，不代表第二类盒子c2全部是曲面相切的盒子，不代表第零类盒子c0全部是曲面自交或正则相交的盒子，具体对应哪类盒子，本发明下述实施例中会对上述初分类的盒子进行进一步细分的情形进行描述。
[0094]
在操作s105，通过运算器基于控制指令，分别生成第一类盒子、第二类盒子、第零类盒子中的多个追踪点，并将多个追踪点连接以生成第一参数曲面和第二参数曲面的交线。
[0095]
根据本公开的实施例，经过之前的处理，同时有多种奇异情形的盒子，也被细分为只有单种情形的盒子，只需将追踪出的点相连即可，必要时可以使用b样条。
[0096]
在操作s106，通过显示单元展示第一参数曲面和第二参数曲面的交线。
[0097]
根据本发明的实施例，参数曲面相交在一个小的区域中甚至有许多不同的分支，如何区分，隔离，并计算所有这些解是一个基本且具有挑战性的问题，而在数值实现时，这些拓扑情况非常近似，这就不可避免地引起了由于浮点计算造成的数值误差。常规曲面求交算法或基于数值计算，或基于符号计算，但是，这些方法对于奇异点，隐式曲面或曲面有一定的限制，或者缺乏理论基础，或效率严重低下。在常规的计算交线的算法中，遇到曲面奇异，相切以及自交的情况下，容易使算出来的交线无法保持其拓扑性质，无法构建准确的实体几何模型。通常，遇到的奇异情况为上述这三种或是它们的混合，增加了曲面求交的复杂性。
[0098]
本发明的上述追踪曲面交线的方法通过建立混合的符号-数字框架来获得拓扑正确，并且在混合的情况下，通过基于切向量函数模型建立第一判定条件和第二判定条件，进行空间盒子区分，通过对各种奇异的情形进行区分，可以将多种混合情形简化为单一情形，从而依次将所有奇异的情况找出，能够在建模过程中追踪到各种奇异情形下的交点，从而生成曲面交线，从而保证计算出的交线的拓扑性质，提高几何建模的精确度。上述方法可以用于复杂曲面求交建模的各种情形，在机械工程建模、有限元离散化，计算机动画建模，面部识别等领域，具有较高的实际应用价值。
[0099]
本发明的上述追踪曲面交线的方法，在计算过程中，通过运算器将第一参数曲面对应的参数空间和第二参数曲面对应的参数空间划分为多个小的盒子(计算区域)，将全局化计算转化为局部计算，因此，可以在运算器中实现多个局部计算的并行计算，进一步地，由于采用并行计算，寄存器上的多个线程可同步执行计算任务，运算器在求解的过程中，提高了计算速度，在较短的时间内即可获得计算结果，同时由于采用局部计算的方法，将大的计算区域划分为多个小的计算区域，在小的计算区域中，函数系统相对比较简单，对计算机寄存器和运算器等硬件的要求也比较低，提高计算速度的同时也降低了硬件成本。
[0100]
进一步地，在运算器计算过程中，通过将多个第一曲面盒子和多个第二曲面盒子中相交的盒子确定为目标盒子，仅针对数量较少的盒子(相交的目标盒子)进行判别以及后续交点追踪，而无需针对曲面空间中的所有盒子进行计算，如此，较大程度上降低了运算器的运算量，提高了运算器的处理效率。同时上述方法中，也仅将目标盒子、以及针对目标盒子的运算结果存储在寄存器中，较大程度上降低了存储空间，降低了对寄存器的硬件要求，提高了存储效率。
[0101]
根据本发明的实施例，第一参数曲面和第二参数曲面为基于多种类型的曲面实体，并按照预定制图比例建立的参数曲面，多种类型的曲面实体例如包括：机械元件曲面实体、人体部位曲面实体、动画对象曲面实体等。
[0102]
例如，在机械工程建模场景下，需对汽车车身外观构件进行建模，由于现代工业生产中不可能直接制造出单张车身曲面，因此必须单独加工出每一张曲面，然后将这些曲面零部件进行拼接而组合成为完整车身。车身外观零部件例如包含引擎盖、前裙、后裙、前后翼子板等，每一个零部件都是一个单独的曲面，车身造型设计可以看作是将整个车身拆分成不同的曲面组合。
[0103]
基于此，对汽车车身外观构件进行建模的过程中，将上述车身外观零部件(例如引擎盖、前裙、后裙、前后翼子板等)，分别转换为本技术中的参数曲面(有理b样条曲面)，则车身的建模即为多个参数曲面求交的过程，需要分别计算相邻两个参数曲面的交线，例如，第一参数曲面对应引擎盖曲面实体，第二参数曲面对应前裙曲面实体，按照本发明实施例的追踪曲面交线的方法计算出第一参数曲面和第二参数曲面的交线后，实现了引擎盖曲面实体和前裙曲面实体的拼接建模；例如第一参数曲面对应前裙曲面实体，第二参数曲面对应前翼子板曲面实体，按照本发明实施例的追踪曲面交线的方法计算出第一参数曲面和第二参数曲面的交线后，实现了前裙曲面实体和前翼子板曲面实体的拼接建模；如此，计算出所有相邻参数曲面的交线后，实现了将所有曲面零部件对应的曲面进行拼接而组合成为完整车身模型，完成了车身的建模。
[0104]
根据本发明的实施例，如上式(7)所示，切向量函数模型包括第一分向量函数模型第二分向量函数模型第三分向量函数模型第四分向量函数模型
[0105]
进一步地，在操作s104中，基于切向量函数模型建立第一判定条件和第二判定条件可包括：
[0106]
首先，通过运算器基于控制指令，将目标盒子输入切向量函数模型，输出目标解集，将目标解集存储在寄存器中；其中，利用切向量函数模型输出的目标解集包括：通过第一分向量函数模型输出的第一解集、通过第二分向量函数模型输出的第二解集、通过第三分向量函数模型输出的第三解集、通过第四分向量函数模型输出的第四解集。
[0107]
之后，通过运算器基于控制指令，从寄存器中读取目标解集，并利用与切向量函数模型相关的目标解集建立第一判定条件和第二判定条件。
[0108]
进一步地，第一判定条件为：第一解集和第二解集的交集中存在零解，或者第三解集和第四解集的交集中存在零解。
[0109]
第二判定条件为：在第一解集、第二解集、第三解集、第四解集的交集中存在零解。
[0110]
以下，对上述判定条件建立的理论基础进行说明：
[0111]
经过四维空间参数曲线ψ的代数理论分析，r1，r2的交线的奇异情况在三维参数空间中的描述分别参见下式(8)、(9)、(10)
[0112]
曲面奇异的情形：
[0113][0114]
或
[0115]
曲面相切的情形：
[0116][0117]
曲面自交的情形：
[0118][0119]
其余的情形被称为正则情形，记为c0。
[0120]
将上述交线c的奇异情况在三维参数空间中的描述以四维参数空间的语言描述得出下式(11)、(12)，分别对应c1和c2的情形。
[0121]
即，建立第一判定条件为：
[0122][0123]
即，第一解集和第二解集的交集中存在零解，或者第三解集和第四解集的交集中存在零解。
[0124]
建立第二判定条件为：
[0125][0126]
即，在第一解集第二解集第三解集第四解集的交集中存在零解。
[0127]
在此，先描述c1和c2的情形，c3的情形在之后实施例中详细描述其与切向量的关系。
[0128]
进一步地，在检验的过程中，涉及到零解的存在性以及唯一性，以下介绍本公开实施例采用的求解零解的数值算法。
[0129]
例如，可以采用改进的牛顿算法，适用于过定的系统或者方程中含有多个零的情况，该算法可以找到系统δ在盒了中的实根。该算法会返还：一个空集，或有限的零维解，或一维的曲线解，或者二维曲面。该算法如下：
[0130]
(1)在的中点对δ使用梯度法可以得到更好的初始点p。
[0131]
(2)在p点处对δ使用牛顿法。
[0132]
(2.1)若牛顿法收敛于外的某一点，输出φ。
[0133]
(2.2)若牛顿法收敛于中的某一点q，输出q。
[0134]
(2.3)若牛顿法因为矩阵不可逆而失败，那么加入一个随机的超平面称为l，将当前点传递给系统δ，计算新系统δ∩{l}。
[0135]
(2.3.1)若δ∩{l}在中没有解，δ可能在中有重数很高的解，我们通过通缩法检验解，会输出一个空集或一个解。
[0136]
(2.3.2)若δ∩{l}在中有一个解，δ在中有一曲线。若牛顿法对于系统δ∩{l}又因为矩阵不可逆失败了，重复上述操作即可。
[0137]
上述改进的牛顿算法的目标是找到一个解，但是无法确定其中是否只有一个解，可能会漏掉解，因此，可结合牛顿区间算法，以保证算出的每一个盒子的解的唯一性，从而不会漏掉解。具体方法如下：
[0138]
(1)使用牛顿算法求解系统δ，无解，输出φ；
[0139]
(2)使用牛顿区间算法检验是否只包含δ的一个解。如果时，则输出解。
[0140]
(3)递归细分，用区间牛顿法检验子盒，确保相关子盒中只有一个解或无解(有必要可以使用通缩法)，输出所有解。
[0141]
基于此，使用上述两个算法就可以将目标盒子检验出来，检验第一判定条件和第二判定条件对应的函数系统中是否有零解，从而对目标盒子做标记。将满足第一判定条件的目标盒子标记为第一类盒子c1，将满足第二判定条件的目标盒子标记为第二类盒子c2，将目标盒子中除第一类盒子和第二类盒子之外的目标盒子暂且标记为第零类盒子c0。
[0142]
根据本发明的实施例，可利用牛顿算法来检验解的存在性，以及区间牛顿算法来检验解的唯一性，而在解方程组的过程中出现了过多的零，可以利用通缩算法。
[0143]
根据本发明的实施例，进一步地，在计算追踪的过程中，可利用步进法。如此，实现了通过细分来保证鲁棒性，通过步进法来保证计算效率，以及拓扑分析的方法来保证拓扑准确性。
[0144]
根据本发明的实施例，基于此，在操作s105中，分别生成第一类盒子、第二类盒子、第零类盒子中的多个追踪点包括以下操作。
[0145]
其中，针对第二类盒子c2，因关联有曲面相切情形，由于相切的情况过于复杂，先处理相切的情况，对于数值的处理是利用牛顿算法以及牛顿区间算法以及通缩算法。
[0146]
针对第二类盒子c2，判断其拓扑性质，根据不同子情况追踪分支，生成多个不同类型的第二追踪点，多个不同类型的第二追踪点至少包括：在第一参数曲面和第二参数曲面相切于点的情况下的切点、在第一参数曲面和第二参数曲面相切于曲线的情况下的切点、在第一参数曲面和第二参数曲面重合的情况下的切点、在第一参数曲面和第二参数曲面相切于孤立切点的情况下的切点、在第一参数曲面和第二参数曲面相切于极小环的情况下的切点。
[0147]
其中，标记为第零类盒子c0关联有曲面自交情形和正则情形，首先可先进行追踪，通过追踪第零类盒子生成多个零类追踪点，零类追踪点为在第一参数曲面或第二参数曲面正则相交情况下的正则交点。
[0148]
该操作中，需要追踪正则情形，为了避免寻找多个追踪初始点而耗费过多的精力
在计算多个初始点上，可以从一个点出发，从初始盒子边界上的点开始追踪交线，将所有盒子都进行追踪，在边界上的初始点的选取则是使用区间牛顿算法，避免遗漏。
[0149]
其中，标记为第一类盒子c1关联有曲面奇异情形，将其分类，根据不同的子情况追踪分支，针对第一类盒子生成多个不同类型的第一追踪点，该操作时在整个初始的区间中进行拓扑分析并追踪分支的。其中，多个不同类型的第一追踪点至少包括：在第一参数曲面或第二参数曲面上存在的有限个奇异点、在第一参数曲面或第二参数曲面上存在的奇异曲线上的奇异点。
[0150]
其中，针对曲面自交的情形，最后来检验这种情况并且进行追踪分支以及拓扑分析，需要从第零类盒子中确定第三类盒子，以使得针对第三类盒子生成多个第三追踪点，第三追踪点为第一参数曲面或第二参数曲面的自交点。
[0151]
根据本发明的实施例，针对曲面相切情形，基于第二类盒子c2生成多个不同类型的第二追踪点包括：
[0152]
首先，根据切向量函数模型和四维空间参数曲线构建第二判别函数系统；之后，根据第二判别函数系统的解的数量，将第二类盒子进行细分，以根据细分后的第二类盒子生成多个不同类型的第二追踪点。
[0153]
对于相切的情形，有两种子情形，一种是正常的相切情形(包括相切点，曲线切线，以及重合曲面)，还有特殊的情形(包括孤立切点以及极小环)。如图3示出了一个环在由φ定义的曲线上至少有两个点情形的示意图。
[0154]
以下，先对正常相切情形的拓扑性质进行分析，从而会有不同的子情况，对于该情形来说，满足下式(13)：
[0155][0156]
则，根据切向量函数模型和四维空间参数曲线构建的第二判别函数系统如下式(14)：
[0157][0158]
则，根据第二判别函数系统的解的数量，将第二类盒子进行细分，确定盒子的类型，具体判别准则如下：
[0159]
函数系统无解，该类盒子对应的情形为：两个曲面在中是分离的或者交于正则曲线。
[0160]
函数系统存在有限个解，该类盒子对应的情形为：两个曲面在中是在某些单独点相切的。
[0161]
函数系统存在无限个解，该类盒子对应的情形为：两个曲面在中是沿奇异曲线相切或是部分重叠。
[0162]
图4示出了曲面相切情形下各种子情况的决策树。图5示出了使用图4所示决策树来判定的两曲面相切情形下各种子情况的经典情形示意图。
[0163]
如图4、图5所示展示了根据式(14)所示的第二判别函数系统进行分类，并更进一步细分的子情形，其中l与l1是随机取的超平面，通过结合随机超平面建立新的子函数系统，并根据子函数系统的解的数量，进行进一步的细分判别。图5中“#(x)”的数值，表示括号中的系统x的解的个数。
[0164]
根据本发明点的实施例，对于特殊相切的情形(包括孤立切点以及极小环)，无法采用上述的方法来解决，这是因为特殊的孤立情况可能与其他奇异点/曲线的情况共存，这些奇异点/曲线都被描述为同一函数系统的解，但很难把他们分离出来。对于特殊情形，使用的子系统φ，会确立一个正则系统。有如下引理：
[0165]
令p是一个孤立的切点在交线ψ上满足是系统{φ1，φ2，φ3，φ4}，有φ1≠φ2∈ψ，φ3≠φ4∈t
ψ
，那么p是在满足以下系统的正则曲线上如下式(15)：
[0166]
φ＝{φ1，φ2，φ3|φ1，φ2∈ψ，φ3∈t
ψ
}
ꢀꢀ
(15)
[0167]
更多的任何闭环必须在正则曲线φ上有两个点。
[0168]
那么根据该引理，该奇异情形转化为正则情形φ，那么便可以用随机生成的超平面l与φ相交，就可以将孤立奇异点与环区分。
[0169]
特殊相切的情形的细分方法，参考图4中决策树节点中涉及第二行带括号的描述。例如，左侧第一列的四个节点中，第一列第二个节点中第二行的括号内的则代表在第二判别函数系统无解的情况下，进一步针对特殊情形建立子函数系统第一列第三个节点中第二行的括号内的描述代表这个系统的解的个数为有限个解；第一列第四个节点中第二行的括号内的描述代表这个系统的解的个数为有限个解的情况下，该类盒子对应特殊相切的情形下的极小环。
[0170]
如此，按照上述方法，将相切的情形下的正常的相切情形以及特殊情形下的盒子都细分完毕，将细分完毕得到的盒子标记为c2。
[0171]
根据本发明的实施例，其中，针对曲面奇异情形，针对第一类盒子c1生成多个不同类型的第一追踪点包括：
[0172]
首先，针对第一参数曲面r1(s，t)或者第二参数曲面r2(u，v)，构建子函数系统。
[0173]
在此，以r1(s，t)为例进行说明，(r2(u，v)采用类似的方法，在此不再赘述)，针对其定义一个子函数系统∑1(s，t)，如下式(16)：
[0174][0175]
之后，根据子函数系统和四维空间参数曲线构建第一判别函数系统曲面奇异的情形可以称其为尖点或曲线，那么交线上的c1的子情况可以有以下的系统在4d盒了的解决定，第一判别函数系统的表达式参见下式(17)。
[0176][0177]
然后，根据第一判别函数系统的解的数量，将第一类盒子进行细分，确定盒子的类型，以根据细分后的第一类盒子生成多个不同类型的第一追踪点。具体判别准则如下：
[0178]
函数系统无解，该类盒子对应的情形为：交线上没有c1类型的奇异点或奇异曲线在r1(s，t)上。
[0179]
函数系统存在有限个解，该类盒子对应的情形为：交线上有有限个奇异点在r1(s，t)上。
[0180]
函数系统存在无限个解，该类盒子对应的情形为：交线上有奇异曲线在r1(s，t)上。
[0181]
一般来说，若则确而若都等于零，那么有可能在该点有t
ψ
＝0，可以利用牛顿算法以及区间牛顿算法解决。
[0182]
图6示出了曲面奇异情形下各种子情况的决策树；图7示出了使用图6所示决策树来判定的曲面奇异情形下各种子情况的经典情形示意图。如图6、图7所示展示了根据第一判别函数系统的解的数量，将第一类盒子进行细分，并更进一步细分的子情形，在整个定义域[0，1]4中计算奇异的情形，其中l是随机取的超平面，通过结合随机超平面建立新的子函数系统，并根据子函数系统的解的数量，进行进一步的细分判别，将奇异的情况全部计算出来，最后将所得到的盒子标记为c1。
[0183]
根据本发明的实施例，标记为第零类盒子c0可能关联有曲面自交情形和正则情形，针对正则的情形的盒子，在前述实施例中通过首先对标记为第零类盒子c0进行追踪后追踪到正则交点。
[0184]
针对曲面自交的情形，最后检验这种情况，并且进行追踪分支以及拓扑分析，需要从第零类盒子c0中确定第三类盒子c3，以使得针对第三类盒子生成多个第三追踪点(自交点)。具体地，可以是先判断盒子是否属于自交的情形，若是，则将其进一步分类，根据不同的子情况追踪分支。
[0185]
其中，从第零类盒子中确定第三类盒子，即判断盒子是否属于自交的情形包括：
[0186]
首先，基于切向量函数模型建立第三判定条件，其中，第三判定条件为：满足第一子条件、第二子条件、第三子条件、第四子条件的至少之一；第一子条件为：第一解集中不存在零解，并且第三解集中不存在零解；第二子条件：第一解集中不存在零解，并且第四解集中不存在零解；第三子条件为：第二解集中不存在零解，并且第三解集中不存在零解；第四子条件为：第二解集中不存在零解，并且第四解集中不存在零解；
[0187]
之后，将满足第三判定条件的第零类盒子确定为排除盒子，并将第零类盒子中除排除盒子和正则盒子之外的盒子确定为第三类盒子，其中正则盒子为零类追踪点对应的盒子。
[0188]
根据本发明的实施例，自交的情形看作四维空间参数曲线上的两个以上的点映射至三维空间中交线上的同一点，在此，以r1(s，t)为例进行说明，(r2(u，v)采用类似的方法，在此不再赘述)，假设r1(s，t)为自交的曲面，建立如下式(18)所示的函数系统：
[0189]
δb(s，t，p，q，u，v)＝{r1(s，t)＝r1(p，q)＝r2(u，v)，
[0190][0191]
其中，
[0192]
为了更好的判定自交情形，以下定理1给出一个规律性检验条件，以确定给定的盒
子由一个一一对应的点在盒了
[0193]
定理1：给定两个参数曲面r1(s，t)与r2(u，v)，它们的交线ψ，一个区间盒子切向量为两个点则有：映射至交线上的点如果盒子满足上述基于切向量函数模型建立的第三判定条件，即满足以下至少一个子条件：
[0194]
第一子条件：并且即第一解集中不存在零解，并且第三解集中不存在零解；
[0195]
第二子条件：并且即第一解集中不存在零解，并且第四解集中不存在零解；
[0196]
第三子条件：并且第二解集中不存在零解，并且第三解集中不存在零解；
[0197]
第四子条件：并且第二解集中不存在零解，并且第四解集中不存在零解。
[0198]
则有以下推论：
[0199]
假设四维空间参数曲线ψ和盒子边界有两个交点，并且没有是零解在上。则有：
[0200]
(1)四维空间参数曲线ψ有唯一的联通曲线段在盒了中；
[0201]
(2)当被映射至3d中时，唯一的曲线段在盒子和没有对应的自交点。
[0202]
如此，通过上述方法，可将满足第三判定条件的第零类盒子确定为排除盒子(不属于自交的情形)，并通过反推的方法，将第零类盒子中除排除盒子和正则盒子(零类追踪点，即正则点对应的盒子)之外的盒子确定为第三类盒子。
[0203]
进一步地，对于包含有四维曲线中的点的盒子，在判断其属于自交的情形后，进一步将其分类，根据不同的子情况追踪分支。
[0204]
图8示出了曲面自交情形下各种子情况的决策树；图9示出了使用图8所示决策树来判定的曲面自交情形下各种子情况的经典情形示意图。
[0205]
如图8、图9所示展示了更进一步细分的子情形，对于属于自交情形的盒子，类似的，可以依据式(18)所示函数系统δb的解的个数来对子情形进行分类，其中l是随机生成的超平面，其中l是随机取的超平面，通过结合随机超平面建立新的子函数系统，并根据子函数系统的解的数量，进行进一步的细分判别，将自交的情况全部计算出来，最后将所得到的盒子标记为c3。
[0206]
基于上述追踪曲面交线的方法，本发明还提供了一种追踪曲面交线的装置。以下将结合图10对该装置进行详细描述。
[0207]
图10示意性示出了根据本发明实施例的追踪曲面交线的装置的结构框图。
[0208]
如图10所示，该实施例的追踪曲面交线的装置1000包括第一生成模块1001、划分
模块1002、构建模块1003、标记模块1004、第二生成模块1005、展示模块1006。
[0209]
其中，第一生成模块1001，用于响应于控制器生成的控制指令，通过运算器基于控制指令根据第一参数曲面的函数模型和第二参数曲面的函数模型，生成与第一参数曲面和第二参数曲面关联的四维空间参数曲线，将四维空间参数曲线存储在寄存器中；
[0210]
划分模块1002，用于通过运算器基于控制指令，将第一参数曲面对应的参数空间划分为多个第一曲面盒子，以及将第二参数曲面对应的参数空间划分为多个第二曲面盒子，以使得将多个第一曲面盒子和多个第二曲面盒子中相交的盒子确定为目标盒子，并将目标盒子存储在寄存器中；
[0211]
构建模块1003，用于通过运算器基于控制指令，从寄存器中读取四维空间参数曲线，并构建针对四维空间参数曲线的切向量函数模型，将切向量函数模型存储在寄存器中；
[0212]
标记模块1004，用于通过运算器基于控制指令，从寄存器中读取切向量函数模型，并基于切向量函数模型建立第一判定条件和第二判定条件，以使得将满足第一判定条件的目标盒子标记为第一类盒子，将满足第二判定条件的目标盒子标记为第二类盒子，将目标盒子中除第一类盒子和第二类盒子之外的目标盒子标记为第零类盒子；
[0213]
第二生成模块1005，用于通过运算器基于控制指令，分别生成第一类盒子、第二类盒子、第零类盒子中的多个追踪点，并将多个追踪点连接以生成第一参数曲面和第二参数曲面的交线；
[0214]
展示模块1006，用于通过显示单元展示第一参数曲面和第二参数曲面的交线。
[0215]
根据本发明的实施例，第一生成模块1001、划分模块1002、构建模块1003、标记模块1004、第二生成模块1005、展示模块1006中的任意多个模块可以合并在一个模块中实现，或者其中的任意一个模块可以被拆分成多个模块。或者，这些模块中的一个或多个模块的至少部分功能可以与其他模块的至少部分功能相结合，并在一个模块中实现。根据本发明的实施例，第一生成模块1001、划分模块1002、构建模块1003、标记模块1004、第二生成模块1005、展示模块1006中的至少一个可以至少被部分地实现为硬件电路，例如现场可编程门阵列(fpga)、可编程逻辑阵列(pla)、片上系统、基板上的系统、封装上的系统、专用集成电路(asic)，或可以通过对电路进行集成或封装的任何其他的合理方式等硬件或固件来实现，或以软件、硬件以及固件三种实现方式中任意一种或以其中任意几种的适当组合来实现。或者，第一生成模块1001、划分模块1002、构建模块1003、标记模块1004、第二生成模块1005、展示模块1006中的至少一个可以至少被部分地实现为计算机程序模块，当该计算机程序模块被运行时，可以执行相应的功能。
[0216]
图11示意性示出了根据本发明实施例的适于实现追踪曲面交线的方法的电子设备的方框图。
[0217]
如图11所示，根据本发明实施例的电子设备1100包括处理器1101，其可以根据存储在只读存储器(rom)1102中的程序或者从存储部分1108加载到随机访问存储器(ram)1103中的程序而执行各种适当的动作和处理。处理器1101例如可以包括通用微处理器(例如cpu)、指令集处理器和/或相关芯片组和/或专用微处理器(例如，专用集成电路(asic))等等。处理器1101还可以包括用于缓存用途的板载存储器。处理器1101可以包括用于执行根据本发明实施例的方法流程的不同动作的单一处理单元或者是多个处理单元。
[0218]
在ram 1103中，存储有电子设备1100操作所需的各种程序和数据。处理器1101、
rom 1102以及ram 1103通过总线1104彼此相连。处理器1101通过执行rom 1102和/或ram 1103中的程序来执行根据本发明实施例的方法流程的各种操作。需要注意，所述程序也可以存储在除rom 1102和ram 1103以外的一个或多个存储器中。处理器1101也可以通过执行存储在所述一个或多个存储器中的程序来执行根据本发明实施例的方法流程的各种操作。
[0219]
根据本发明的实施例，电子设备1100还可以包括输入/输出(i/o)接口1105，输入/输出(i/o)接口1105也连接至总线1104。电子设备1100还可以包括连接至输入/输出(i/o)接口1105的以下部件中的一项或多项：包括键盘、鼠标等的输入部分1106；包括诸如阴极射线管(crt)、液晶显示器(lcd)等以及扬声器等的输出部分1107；包括硬盘等的存储部分1108；以及包括诸如lan卡、调制解调器等的网络接口卡的通信部分1109。通信部分1109经由诸如因特网的网络执行通信处理。驱动器1110也根据需要连接至输入/输出(i/o)接口1105。可拆卸介质1111，诸如磁盘、光盘、磁光盘、半导体存储器等等，根据需要安装在驱动器1110上，以便于从其上读出的计算机程序根据需要被安装入存储部分1108。
[0220]
本发明还提供了一种计算机可读存储介质，该计算机可读存储介质可以是上述实施例中描述的设备/装置/系统中所包含的；也可以是单独存在，而未装配入该设备/装置/系统中。上述计算机可读存储介质承载有一个或者多个程序，当上述一个或者多个程序被执行时，实现根据本发明实施例的方法。
[0221]
根据本发明的实施例，计算机可读存储介质可以是非易失性的计算机可读存储介质，例如可以包括但不限于：便携式计算机磁盘、硬盘、随机访问存储器(ram)、只读存储器(rom)、可擦式可编程只读存储器(eprom或闪存)、便携式紧凑磁盘只读存储器(cd-rom)、光存储器件、磁存储器件、或者上述的任意合适的组合。在本发明中，计算机可读存储介质可以是任何包含或存储程序的有形介质，该程序可以被指令执行系统、装置或者器件使用或者与其结合使用。例如，根据本发明的实施例，计算机可读存储介质可以包括上文描述的rom 1102和/或ram 1103和/或rom 1102和ram 1103以外的一个或多个存储器。
[0222]
本发明的实施例还包括一种计算机程序产品，其包括计算机程序，该计算机程序包含用于执行流程图所示的方法的程序代码。当计算机程序产品在计算机系统中运行时，该程序代码用于使计算机系统实现本发明实施例所提供的追踪曲面交线方法。
[0223]
在该计算机程序被处理器1101执行时执行本发明实施例的系统/装置中限定的上述功能。根据本发明的实施例，上文描述的系统、装置、模块、单元等可以通过计算机程序模块来实现。
[0224]
在一种实施例中，该计算机程序可以依托于光存储器件、磁存储器件等有形存储介质。在另一种实施例中，该计算机程序也可以在网络介质上以信号的形式进行传输、分发，并通过通信部分1109被下载和安装，和/或从可拆卸介质1111被安装。该计算机程序包含的程序代码可以用任何适当的网络介质传输，包括但不限于：无线、有线等等，或者上述的任意合适的组合。
[0225]
在这样的实施例中，该计算机程序可以通过通信部分1109从网络上被下载和安装，和/或从可拆卸介质1111被安装。在该计算机程序被处理器1101执行时，执行本发明实施例的系统中限定的上述功能。根据本发明的实施例，上文描述的系统、设备、装置、模块、单元等可以通过计算机程序模块来实现。
[0226]
根据本发明的实施例，可以以一种或多种程序设计语言的任意组合来编写用于执
行本发明实施例提供的计算机程序的程序代码，具体地，可以利用高级过程和/或面向对象的编程语言、和/或汇编/机器语言来实施这些计算程序。程序设计语言包括但不限于诸如java，c++，python，“c”语言或类似的程序设计语言。程序代码可以完全地在用户计算设备上执行、部分地在用户设备上执行、部分在远程计算设备上执行、或者完全在远程计算设备或服务器上执行。在涉及远程计算设备的情形中，远程计算设备可以通过任意种类的网络，包括局域网(lan)或广域网(wan)，连接到用户计算设备，或者，可以连接到外部计算设备(例如利用因特网服务提供商来通过因特网连接)。
[0227]
附图中的流程图和框图，图示了按照本发明各种实施例的系统、方法和计算机程序产品的可能实现的体系架构、功能和操作。在这点上，流程图或框图中的每个方框可以代表一个模块、程序段、或代码的一部分，上述模块、程序段、或代码的一部分包含一个或多个用于实现规定的逻辑功能的可执行指令。也应当注意，在有些作为替换的实现中，方框中所标注的功能也可以以不同于附图中所标注的顺序发生。例如，两个接连地表示的方框实际上可以基本并行地执行，它们有时也可以按相反的顺序执行，这依所涉及的功能而定。也要注意的是，框图或流程图中的每个方框、以及框图或流程图中的方框的组合，可以用执行规定的功能或操作的专用的基于硬件的系统来实现，或者可以用专用硬件与计算机指令的组合来实现。
[0228]
本领域技术人员可以理解，本发明的各个实施例和/或权利要求中记载的特征可以进行多种组合或/或结合，即使这样的组合或结合没有明确记载于本发明中。特别地，在不脱离本发明精神和教导的情况下，本发明的各个实施例和/或权利要求中记载的特征可以进行多种组合和/或结合。所有这些组合和/或结合均落入本发明的范围。
[0229]
以上对本发明的实施例进行了描述。但是，这些实施例仅仅是为了说明的目的，而并非为了限制本发明的范围。尽管在以上分别描述了各实施例，但是这并不意味着各个实施例中的措施不能有利地结合使用。本发明的范围由所附权利要求及其等同物限定。不脱离本发明的范围，本领域技术人员可以做出多种替代和修改，这些替代和修改都应落在本发明的范围之内。

技术特征：
1.一种由电子设备执行的追踪曲面交线的方法，包括：响应于控制器生成的控制指令，通过运算器基于所述控制指令根据第一参数曲面的函数模型和第二参数曲面的函数模型，生成与第一参数曲面和第二参数曲面关联的四维空间参数曲线，将所述四维空间参数曲线存储在寄存器中；通过运算器基于所述控制指令，将所述第一参数曲面对应的参数空间划分为多个第一曲面盒子，以及将所述第二参数曲面对应的参数空间划分为多个第二曲面盒子，以使得将所述多个第一曲面盒子和所述多个第二曲面盒子中相交的盒子确定为目标盒子，并将所述目标盒子存储在寄存器中；通过运算器基于所述控制指令，从所述寄存器中读取所述四维空间参数曲线，并构建针对所述四维空间参数曲线的切向量函数模型，将所述切向量函数模型存储在寄存器中；通过运算器基于所述控制指令，从所述寄存器中读取所述切向量函数模型，并基于所述切向量函数模型建立第一判定条件和第二判定条件，以使得将满足第一判定条件的所述目标盒子标记为第一类盒子，将满足第二判定条件的所述目标盒子标记为第二类盒子，将所述目标盒子中除所述第一类盒子和所述第二类盒子之外的目标盒子标记为第零类盒子；通过运算器基于所述控制指令，分别生成所述第一类盒子、所述第二类盒子、所述第零类盒子中的多个追踪点，并将所述多个追踪点连接以生成所述第一参数曲面和所述第二参数曲面的交线；通过显示单元展示所述第一参数曲面和所述第二参数曲面的交线。2.根据权利要求1所述的方法，所述第一参数曲面和所述第二参数曲面为基于多种类型的曲面实体，并按照预定制图比例建立的参数曲面，所述多种类型的曲面实体至少包括：机械元件曲面实体、人体部位曲面实体、动画对象曲面实体。3.根据权利要求1所述的方法，基于所述切向量函数模型建立第一判定条件和第二判定条件包括：通过运算器基于所述控制指令，将所述目标盒子输入所述切向量函数模型，输出目标解集，将所述目标解集存储在寄存器中；通过运算器基于所述控制指令，从所述寄存器中读取所述目标解集，并利用与所述切向量函数模型相关的目标解集建立第一判定条件和第二判定条件。4.根据权利要求3所述的方法，其中：所述切向量函数模型包括第一分向量函数模型、第二分向量函数模型、第三分向量函数模型、第四分向量函数模型；利用所述切向量函数模型输出的所述目标解集包括：通过所述第一分向量函数模型输出的第一解集、通过所述第二分向量函数模型输出的第二解集、通过所述第三分向量函数模型输出的第三解集、通过所述第四分向量函数模型输出的第四解集：所述第一判定条件为：第一解集和第二解集的交集中存在零解，或者第三解集和第四解集的交集中存在零解；所述第二判定条件为：在第一解集、第二解集、第三解集、第四解集的交集中存在零解。5.根据权利要求4所述的方法，分别生成所述第一类盒子、所述第二类盒子、所述第零类盒子中的多个追踪点包括：
针对所述第二类盒子生成多个不同类型的第二追踪点，所述多个不同类型的第二追踪点至少包括：在第一参数曲面和第二参数曲面相切于点的情况下的切点、在第一参数曲面和第二参数曲面相切于曲线的情况下的切点、在第一参数曲面和第二参数曲面重合的情况下的切点、在第一参数曲面和第二参数曲面相切于孤立切点的情况下的切点、在第一参数曲面和第二参数曲面相切于极小环的情况下的切点；通过追踪所述第零类盒子生成多个零类追踪点，所述零类追踪点为在所述第一参数曲面或第二参数曲面正则相交情况下的正则交点；针对所述第一类盒子生成多个不同类型的第一追踪点，所述多个不同类型的第一追踪点至少包括：在所述第一参数曲面或第二参数曲面上存在的有限个奇异点、在所述第一参数曲面或第二参数曲面上存在的奇异曲线上的奇异点；从所述第零类盒子中确定第三类盒子，以使得针对所述第三类盒子生成多个第三追踪点，所述第三追踪点为所述第一参数曲面或第二参数曲面的自交点。6.根据权利要求5所述的方法，其中，针对所述第二类盒子生成多个不同类型的第二追踪点包括：根据所述切向量函数模型和所述四维空间参数曲线构建第二判别函数系统；根据所述第二判别函数系统的解的数量，将所述第二类盒子进行细分，以根据细分后的第二类盒子生成多个不同类型的第二追踪点。7.根据权利要求5所述的方法，其中，针对所述第一类盒子生成多个不同类型的第一追踪点包括：针对所述第一参数曲面或者所述第二参数曲面，构建子函数系统；根据所述子函数系统和所述四维空间参数曲线构建第一判别函数系统；根据所述第一判别函数系统的解的数量，将所述第一类盒子进行细分，以根据细分后的第一类盒子生成多个不同类型的第一追踪点。8.根据权利要求5所述的方法，其中，从所述第零类盒子中确定第三类盒子包括：基于所述切向量函数模型建立第三判定条件，其中，所述第三判定条件为：满足第一子条件、第二子条件、第三子条件、第四子条件的至少之一；所述第一子条件为：所述第一解集中不存在零解，并且所述第三解集中不存在零解；所述第二子条件：所述第一解集中不存在零解，并且所述第四解集中不存在零解；所述第三子条件为：所述第二解集中不存在零解，并且所述第三解集中不存在零解；所述第四子条件为：所述第二解集中不存在零解，并且所述第四解集中不存在零解；将满足所述第三判定条件的第零类盒子确定为排除盒子，并将所述第零类盒子中除所述排除盒子和正则盒子之外的盒子确定为第三类盒子，其中所述正则盒子为所述零类追踪点对应的盒子。9.一种追踪曲面交线的装置，包括：第一生成模块，用于响应于控制器生成的控制指令，通过运算器基于所述控制指令根据第一参数曲面的函数模型和第二参数曲面的函数模型，生成与第一参数曲面和第二参数曲面关联的四维空间参数曲线，将所述四维空间参数曲线存储在寄存器中；划分模块，用于通过运算器基于所述控制指令，将所述第一参数曲面对应的参数空间划分为多个第一曲面盒子，以及将所述第二参数曲面对应的参数空间划分为多个第二曲面
盒子，以使得将所述多个第一曲面盒子和所述多个第二曲面盒子中相交的盒子确定为目标盒子，并将所述目标盒子存储在寄存器中；构建模块，用于通过运算器基于所述控制指令，从所述寄存器中读取所述四维空间参数曲线，并构建针对所述四维空间参数曲线的切向量函数模型，将所述切向量函数模型存储在寄存器中；标记模块，用于通过运算器基于所述控制指令，从所述寄存器中读取所述切向量函数模型，并基于所述切向量函数模型建立第一判定条件和第二判定条件，以使得将满足第一判定条件的所述目标盒子标记为第一类盒子，将满足第二判定条件的所述目标盒子标记为第二类盒子，将所述目标盒子中除所述第一类盒子和所述第二类盒子之外的目标盒子标记为第零类盒子；第二生成模块，用于通过运算器基于所述控制指令，分别生成所述第一类盒子、所述第二类盒子、所述第零类盒子中的多个追踪点，并将所述多个追踪点连接以生成所述第一参数曲面和所述第二参数曲面的交线；展示模块，用于通过显示单元展示所述第一参数曲面和所述第二参数曲面的交线。10.一种电子设备，包括：一个或多个处理器；存储装置，用于存储一个或多个程序，其中，当所述一个或多个程序被所述一个或多个处理器执行时，使得所述一个或多个处理器执行根据权利要求1～8中任一项所述的方法。

技术总结
本发明提供了一种由电子设备执行的追踪曲面交线方法及装置、电子设备，该方法包括：生成四维空间参数曲线，将第一参数曲面对应的参数空间划分为多个第一曲面盒子，将第二参数曲面对应的参数空间划分为多个第二曲面盒子，将多个第一曲面盒子和多个第二曲面盒子中相交的盒子确定为目标盒子，构建切向量函数模型，基于切向量函数模型建立第一判定条件和第二判定条件，将满足第一判定条件的目标盒子标记为第一类盒子，将满足第二判定条件的目标盒子标记为第二类盒子，将目标盒子中除第一类盒子和第二类盒子之外的目标盒子标记为第零类盒子，生成各类盒子中的多个追踪点，并将多个追踪点连接以生成第一参数曲面和第二参数曲面的交线。的交线。的交线。


技术研发人员：程进三
受保护的技术使用者：中国科学院数学与系统科学研究院
技术研发日：2023.04.11
技术公布日：2023/8/21