没有合适的资源?快使用搜索试试~ 我知道了~
广义映射上拓扑运算的推导:细分模式中的操作推理
→图形和视觉计算6(2022)200049技术部分广义映射上拓扑运算的推导:在细分模式中的应用Romain Pascuala,L.S.,Hakim Belhaouarib,Agnès Arnouldb,Pascale Le GallaaMathématiques et Informatique pour la Complexité et les Systèmes(MICS),CentraleSupélec,Université Paris Saclay,France法国普瓦捷大学XLIM UMR CNRS 7252ar t i cl e i nf o文章历史记录:2021年12月3日收到2022年5月9日收到修订版,2022年2022年5月14日网上发售保留字:基于拓扑的几何造型细分方案运算推理实例推理拓扑运算计算拓扑a b st ra ct正确的拓扑建模操作的设计是一项耗时且费力的任务。然而,这些操作可以通过修改前后的代表性对象的简单绘图直观地理解。我们建议从一个应用实例中推断拓扑建模操作。我们的算法利用了一个紧凑和富有表现力的基于图形的语言。在这个框架中,广义映射上的拓扑建模操作被表示为来自图变换理论的规则。大多数情况下,操作是通用的拓扑单元(顶点,面,体积)。因此,规则被参数化,轨道类型指示涉及哪种小区。我们的主要思想是推断一个通用的规则,通过折叠一个图,包括修改前的对象的副本,修改后的副本,和有关修改的信息。我们根据设计中操作的单元参数化折叠此图。我们用一些细分方案来说明我们的方法,因为它们的对称性简化了操作推理。版权所有2022作者。爱思唯尔有限公司出版这是CC BY许可下的开放获取文章(http://creativecommons.org/licenses/by/4.0/)中找到。1. 介绍在交互式建模中,毫不费力地创建专用操作的可能性是一个长期渴望的目标。这些操作旨在简化特定于域的对象的生成。几何建模器[1-这样的解决方案允许跨许多应用领域(诸如计算机辅助设计、建筑或动画电影)构造几何对象。我们的目标是从一个有代表性的例子中推断出一般的操作。事实上,领域专家通常在目标对象复杂时对简单实例进行分析,以至于他们经常可以描述我们的行动-一个精心挑选的用例。此外,从实例中推断操作减少了实现新操作的繁琐性,解决了领域专家对工具实现的不熟悉我们渴望利用直觉专家可以提供推断操作的拓扑修改网格上的特定情况下。我们的方法在于基于拓扑的几何建模领域[4]。对象由拓扑结构组成,即,其拓扑单元(体积、面、边和顶点)和几何方面。所有非拓扑信息都称为✩这篇文章是由L. 巴特*通讯作者。电子邮件地址:romain. centralesupelec.fr(R. Pascual)。https://doi.org/10.1016/j.gvc.2022.200049嵌入信息,并且可以对顶点的位置、边缘的曲率或映射到面上的纹理进行编码。我们利用广义映射或G-映射的形式[4一般化地图类似于(组合)地图,等同于图旋转系统[7,8]在2D中。该模型的主要好处是在所有维度上都被均匀定义。G映射的标准构造利用了一组飞镖上的排列。在这里,我们将它们表示为图形,类似于[9,10]的方法。由于对象是使用图形式化的,因此建模操作可以在图变换的框架中作为规则来研究[11 直观地,规则被写为L R,并且允许在更一般的上下文中将对象L变换为对象R基于规则的语言已经被研究用于在预定义对象上应用预定义操作,例如L系统语言[14,15]。在[16]中,作者使用了一种类似于图变换的方法来定义曲面细分算法。基于规则的专用语言允许通过专用规则应用引擎对建模操作进行用户友好的描述和对这些操作的通用操纵在[10]中,作者展示了如何在应用于广义映射的图转换规则的上下文中设计建模器内核作为规则应用引擎。这些规则分别处理拓扑修改和几何修改。此外,当操作应用于一个格式良好的对象时,应该产生一个格式良好的对象,规则受到确保拓扑保持的句法条件的约束[17,18]。2666-6294/©2022作者。 由Elsevier Ltd.发布。这是CC BY许可下的开放获取文章(http://creativecommons.org/licenses/by/4.0/)。可在ScienceDirect上获得目录列表图形与视觉计算期刊首页:www.elsevier.com/locate/gvcR. Pascual,H.Belhaouari,A.Arnould等人图形和视觉计算6(2022)2000492图1.一、四 边 形细分操作:应用于立方体(a),迭代应用于立方体(b),应用于四边形网格(c)。和几何一致性[19]。操作可以通过拓扑单元来参数化。拓扑单元,以及更一般的轨道,对规则参数进行编码,以提供一种紧凑且富有表现力的基于图形的语言来设计建模操作。这些扩展的规则,称为规则方案,表达了对给定轨道类型的所有可能形状有效的变换,提供了所需的泛化。应用建模操作是通过基于修改对象将规则方案实例化为具体规则来实现的。我们希望提供一个工具,可以推断拓扑部分从一个典型的例子。该操作应适用于类似对象。用户指定初始对象A,修改它,并提供最终对象B。我们提出推导将A直接变换为B的运算。例如,图1(a)所示的立方体的细分是一种变换,其中对象A是细分之前的立方体,对象B是细分之后的对象。由于我们希望操作适用于更广泛的上下文,而不仅仅是对象A,因此我们推断操作通用到用户指定的拓扑单元。例如,我们可以要求图1中描述的细分的推断操作。1(a)一般为一个表面。推断操作可以再次应用于结果对象(见图1)。1(b))。该操作还允许修改不同的对象,例如图1中描绘的奶牛的四边形网格。1(c). 本文主要研究细分格式的推理操作,以利用细分格式的正则性。事实上,这种变换依赖于局部修改,类似地应用于整个对象,创建许多对称性。这些对称性简化了运算的推论我们的主要贡献是一个算法,推断拓扑操作被描述为规则。该算法作为输入的两个对象描述为G-映射,由操作和轨道描述的操作的一般性被推断保留的元素的映射我们证明了算法我们还说明了我们的算法推断标准的细分方案和应用规则的各种例子。本文提出了一种构造拓扑模型的算法eling操作,而无需任何广义映射或图重写的知识。我们将说明我们的方法的帮助下,细分计划。在第2节中,我们通过介绍推导建模操作的其他方法来提供操作推理的上下文。我们回顾了第3节中广义映射的形式主义,并在第4节中对用于建模操作的图变换规则进行了一些见解。我们在第5节中提出了用于重构规则方案的拓扑折叠算法,并在第6节中用示例和反例说明了它。我们将在第7节中解释如何将这两个实例收集到一个图中,作为我们算法的输入。我们在第8节中分析了拓扑折叠算法。我们在第9节中提出了一个验证我们的方法与几个细分方案的说明。我们将在第10节讨论我们的推理机制的一些实际副作用。所提出的算法的正确性的完整证明在附录A中提供。2. 相关作品有几个类别的以前的作品,涉及到我们的贡献。它们主要属于过程建模,更一般地说,是规则、场景和建模操作的推理过程建模和逆过程建模。 过程建模是指计算机图形学中使用的从规则导出模型的技术。这些技术避免了手动编辑对象,证明了对常规对象建模是富有成效的,即,具有许多重复的子图案的对象。程序建模技术已被用于生成植物[14],地形[20],建筑物[21]或城市[22]。由于这些技术不能保证输出忠实于设计者的想法,他们被扩展到逆过程建模。由于机器学习,这些新方法试图发现正确的参数化规则和值。逆过程建模技术已被证明在大多数使用过程建模的领域中是成功的,即树木[23],建筑立面[24],城市模型上的天气模拟[25],虚拟世界[26]和纹理建模[27]。在这样的方法中,可能的规则的集合描述特定的域,并且操作推理被定制为该域。相反,我们将在本文中介绍的方法构建拓扑操作,允许编辑对象,而不管应用领域。事实上,我们的基于规则的方法发现正确的规则参数化的拓扑信息,而不是域特定的值。L系统在[28]中,作者提出了规则的定义是“过程建模的关键挑战”,并使用聚类方法来构建参数上下文无关L系统的规则和参数,给定矢量2D图像。他们利用L系统,引入来描述植物细胞这样的重写系统通过递归地应用从公理词到满足停止条件的产生式规则来构建对象。产生的字符串通过解释转换为几何对象[30,II.6,III.5]。最近,[31]扩展了[28]的工作,使用深度学习技术来检测元素,并使用派生树来检索规则。在这些作品中,重点放在场景的生成,而我们专注于操作的推理。L-系统已被用于表示细分曲线的细化操作[15],其中作者展示了如何从细分矩阵推断L-系统。然而,L-系统本质上是单词的几何解释,因此本质上等价于字符串重写。因此,它们不适合处理曲面和体积。图重写扩展了字符串重写,允许找到一个图模式的出现,并将其替换为另一个模式。在某种意义上,G-映射重写代表了比L-系统更一般的方法。因此,本文的目标可以理解为[32]从L-系统到图重写的推广R. Pascual,H.Belhaouari,A.Arnould等人图形和视觉计算6(2022)2000493=∪∪⟨⟩×--=[客户端]·−·==[]重新评估为了避免繁琐的实现,一些建模者支持通过记录一系列已经存在的操作来定义建模操作。序列的重新评估[33,34]提供了一种解决方案,通过修改实体的特定命名应用此新操作[35]。因此,重新评估方法允许修改类似的观测,即,具有相同命名实体的对象。然而,构造的操作通常不是定义修改的优化解决方案,因为序列的每一步都是忠实地再现的。神经网络和几何方法。最近,[36]提出了几何运算的自动生成。该方法采用Loop细分方案[37]作为细化的原子操作。然后使用神经网络来学习细分的几何值因此,该方法通过目标几何的直接计算从初始对象产生结果。这种构造与我们的构造是对偶的,因为我们只关注拓扑。尽管如此,我们的泛化能力更广泛,因为推断的操作不假设固定的拓扑结构。例如,我们可以重建任何细分方案。图变换规则的推理。 我们的方法利用特定于域的语言内的图形变换为基于拓扑的几何建模。我们提供了一个算法,从一个例子中重建建模操作。在[38]中使用了类似的想法,使用yED为特定领域的语言在[39]中,作者使用图变换作为一种学习机制来检测和修复JavaScript程序中的错误。几何建模操作的基于规则的定义已在[40]中用于预测操作。在这里,我们使用一种特殊的形式主义:广义映射与特定领域的语言。因此,我们推断图形转换规则专用于几何造型。然而,我们不假设一组给定的规则,并检索更一般的操作。构造立体几何中造型顺序的推断。 在[41]中,作者将建模操作的序列推断为草图、挤出和布尔操作的序列。它扩展了以前的工作,如[42,43]或[44],使用了平行立体几何(CSG)。这些工作检索CSG树以获得特定对象。推导出的树产生一个确切的对象结构,但不赋予操作的定义。人们可以很容易地使用这些技术来构建细分方案的第一次迭代。然而,得到的树不会给出一个解决方案,以建立连续迭代的细分方案。3. 广义映射对象的边界表示依赖于称为基于边缘的模型[45]的拓扑数据结构,其编码几何对象的单元细分。一些数据,通常称为嵌入,被附加到对象的单元格以定义其几何形状。广义映射被定义为这些基于边缘的模型的形式化,以表示任何维度中的无向(准)流形[4在[10]中,选择广义映射模型主要是因为它在操纵维度方面的同质性,即,因为细分的操作不依赖于其尺寸。在这里,广义映射同质性允许通过简单的图遍历沿着所有维度搜索搜索在本节中,我们将首先给出基于图的定义广义映射,并提供一些直观的关于它如何描述一个对象的拓扑结构(3.2节)。然后,我们将在第3.3节中描述如何使用轨道检索细胞。最后,在3.4节中,我们将简要介绍嵌入式G-映射的构造。3.1. 词汇在本节中,我们将介绍几种符号。请注意,某些元素在不同的社区中可能有相同的名称,但我们会注意使用不同的单词。(a) 我们称顶点为0-cell,边为1-cell。例如,我们可以讨论图1所示的堆叠立方体的顶点和边。第 3(a)段。(b) 我们保留了节点和弧这两个术语来指代图的连续元素,这与用于建模操作的代数图重写[11,12]一致(c) 我们把广义映射的元素称为箭头和链环,遵循[4]的组合定义。因此,我们说,图3(e)中用G-映射表示的堆叠立方体包含96个箭头,48个0-链接,48个1-链接,48个2-链接和88个3-链接。G-映射的组合方法(c)和基于图的方法(b)是严格等价的,但是我们使用图来利用图重写技术。我们将在整篇文章中保留这些词汇,以便更好地指出应该考虑哪些观点。因此,我们将在使用单词“顶点”和“边”时引用几何对象3.2. 拓扑结构我们依赖于广义映射的基于图的定义(参见[18]),使建模操作的表达成为规则。如果存在规则应用程序引擎,规则可以简化操作的设计并减轻其实现。此外,我们的算法依赖于G-映射的遍历,表示为一个图形算法。在这篇文章中,我们称图为经典的无向图,可能有平行的弧和环。我们将图G(V, E)记为V为节点集,E为弧集。更准确地说,我们将使用弧标记图。标记为i的弧 也将被称为i弧。当两个节点u和v相连时通过i-arc,我们写u我v.我们将标记弧与尺寸来编码对象子部分之间的相邻关系G-映射的组合定义[4]利用了一组对合I1,. . . ,在一组飞镖D上。我们认为每个invol- lutionIi是D上的对称关系,即,D的一个子集。因此,我们可以将结构D,I1, . . . , 成图(D,I1. . .I n)。每个箭头被认为是图的节点,而每个对合Ii产生连接这些节点的i标记(无向)弧的集合。最后一组边由I的这种结构的图示见图1。二、 两个曲线图2(a)和2(b)共享D a, b, c, d, e,因为节点集合具有从对合推导出的弧集合,分别用红色和蓝色绘制最终的图2(c)具有相同的节点和来自两个图的弧的并集。由于G-映射子脚本对合的组合定义[4]具有适当的维数,我们用适当的维数标记每个定义3.1(广义映射[18])。广义n维映射或n-G-映射是指图G(D,α)中α中的弧标在0,n上。图的节点称为箭头,其弧称为链接。图G(D,α) 0,n 是n-G-映射,如果它满足以下拓扑约束:关联约束G的任意矢d是唯一的i-linkd·−i·d′,对于[0,n]中的每个维度i。R. Pascual,H.Belhaouari,A.Arnould等人图形和视觉计算6(2022)2000494−−+≤[客户端]关于我们⟨ ⟩∪联系我们联系我们·−··−··−··−·⟨⟩⟨⟩⟨⟩•⟨⟩⟨⟩⟨⟨ ⟩ []o⟩[客户端]图二. 对合集的表示I1、I2在集合D上a,b,c,d,e作为图:(a)I1(a,d),(b,e),(c,c),(d,a),(e,b)表示为图(D,I1);(b)I2(a,b),(b,a),(c,e),(d,d),(e,c)表示为图(D,I2);(c)D,I1,I2表示为图(D,I1I2)。类似的例子可以在[4]中找到2.5.2]。中所有尺寸i和j的循环约束0,n使得我2j,由ijij标记的长度为4的任何路径是循环,也就是说,源u和目标v在路径u·-i·-j·-i·-j·v中相等。定义3.1忠实地将广义映射[ 4 ]的对合概念转换为图形词汇,但保留了构成元素的组合术语,即箭头和链接。特别是,图是受两个本地的限制,翻译组合定义中使用的对合属性这些约束保证了一个(i1)-cell最多可以分裂两个i-cell,并且保证了任意两个i-cell只能沿着一个i 1维的cell粘合。例如,在2D对象中,三个面不能共享一条边,并且面不能沿顶点粘合。G-maps的形式主义要求连接两个面的唯一方法是沿着唯一的边将它们粘合。将几何对象表示为G-映射可以通过将其分解为维数递减的拓扑单元单元格分解的最后元素是G图的箭头,而分解提供了例如,两个堆叠立方体(3D对象)的递归细分如图所示。 3,从图中的立方体。3(a)到图3-G-地图。3(e).在后者中,弧根据其标签着色:3,2,1和0。让我们详细的重建G-地图从两个堆叠的立方体的帮助下图。第三节:图3(a)的物体由两个共享一个面的体积组成:一个绿色立方体通过紫色正方形粘到一个蓝色立方体上。因此,物体首先被分成两个体积,如图3(b)所示。三维拓扑单元或三维单元(体积)现在沿其共享面用绿色弧链接()。这些3-链接编码两个实体之间的相邻关系:它们是相邻的体积。从图3(b)的表示中,我们通过分割每个体积中的面来分解。每个立方体产生8个面,如图所示。3(c).同一体积内相邻的任何两个面沿其公共边使用蓝色弧进行2链接()。通过降维迭代,我们得到了图。3(d)分解维度1后在每个体积块的每个面中,边将断开连接,并使用红色弧()链接(表示1-链接)。最后,分裂0-细胞,即,顶点(0-链接绘制为黑色弧())结束细分过程。在最后一次分解之后获得的原子元素对应于G图的箭头。循环被添加到每个错过链接的省道上(对于每个可能的维度),以获得正确的G图。对于图的对象。3,只有不属于共享紫色面的飞镖缺少一些链接,并将3-循环添加到所有这些。图中显示的图表。3(e)提供了3-G图表示两个堆叠的立方体。在下文中,有时会省略循环以简化图形。请注意,分割立方体会为初始紫色面生成两个面。上面的一个对应于绿色立方体内的紫色面,而下面的一个代表蓝色立方体内的紫色面。3-链接特征在于两个面实际上是全局对象中的同一个面。如果我们将这种直觉扩展到所有维度,我们就会理解省道同时编码顶点、边、面和体积的一部分。例如,让图的尖紫色飞镖。4、被称为E。这个飞镖是绿色体积的一部分。在绿色体积中,它对应于紫色的脸。在此面中,它属于右侧边。在该边内,它编码前顶点。这些拓扑单元中的每一个分别在图1A和1B中示出。图4(a)至4(d),并通过我们接下来介绍的轨道回收。3.3. 细胞和轨道其次,我们考虑了一个n-G-映射G。如第3.2节所述,拓扑单元(顶点、边、面、体积)表示的几何对象中的但可以隐式检索。单元格可以通过限制到维度子集的图形遍历来计算。例如,在图1中描绘了与紫色尖镖e相关联的细胞。 四、图4(a)给出了与箭头e相关联的0-胞腔(顶点)。此单元格包含箭头,以及除0-链接之外的所有链接可到达的每个箭头(即,1、2和3-链接),以及链接本身。这个子图记为G1,2, 3(e)。1-细胞入射到飞镖e,代表边缘入射到紫色飞镖显示在图。4(b). 这个单元格包含从e开始遍历G时收集的所有箭头和链接,其中除了1以外的所有维度。子图G0, 2, 3(e)对应于该边。图4(c)中示出了入射到e的2-胞元G0, 1, 3(e),并且表示面。• 关联到e的3-胞腔(体积)是子图G= 0,1,2(e),如图所示。4(d).更一般地说,细胞对应于轨道的特定情况定义3.2(轨道)。G的一个轨道由一个子图组成,该子图是由从一个初始箭头可到达的所有箭头诱导的,只使用来自0,n的子集的链接。轨道写为G o(v),其中o是0,n或(v)当图表上没有歧义时。这样的轨道被称为双轨道或称为双轨道。检索一个轨道直观地提供了对应于一个公共拓扑元素的G的所有箭头。此类拓扑元素包含像元(如顶点或体积)或更多受限元素(如半面、半边或角的面孔。例如,图1中描述的轨道G0,1(e)。4(e)表示入射到e的一个体积的面(也称为半面)。实际上,入射到e的面是轨道G0, 1, 3(e),因此去除维度3会分裂两个半面(绿色立方体中的一个和蓝色立方体中的一个) 由于图G的全图。3(e)包含一个连通分支,它对应于轨道G<$0,1, 2, 3<$(e)。3.4. 嵌入式G-maps广义映射的这种表示只具有拓扑内容。虽然本文旨在推断建模操作的拓扑部分,但我们简要介绍如何在G-地图上处理几何数据更多的细节可以在[19]中找到······R. Pascual,H.Belhaouari,A.Arnould等人图形和视觉计算6(2022)2000495:→:→:→⟨ ⟩ →:⟨ ⟩:→:→:→图三. 三维几何对象的拓扑分解:(a)共享一个面的两个立方体,(b)在三维上分裂,(c)二维,(d)一维,和(e)维度0。图G是对应的G-映射(e)。弧颜色图例:3、2、1和0。见图4。在图1中的G图G中,入射到紫色箭头e的轨道。3(e):(a)顶点G1, 2, 3(e),(b)边G0, 2, 3(e),(c)面G0, 1, 3(e),(d)体积G0,1, 2(e),以及(e)体积G0, 1(e)的面图五. 堆叠立方体的嵌入表示:(a)顶点位置的嵌入位置为pos 1,2,3点3D,两个立方体的长度为1;(b)面颜色的嵌入颜色为0,1,3RGB,所描述的颜色RGB值显示在值旁边弧色图例:3,2,1和0。所有的非拓扑信息,如位置或颜色是通过一个嵌入函数,映射到每个拓扑细胞的相关数据表示。在本文中,每个顶点(0-cell)有一个位置,每个面(2-cell)有一个颜色。这些是最小的嵌入信息,允许对象的简单显示,边缘表示为直线段。更正式地说,嵌入是通过函数πoτ来描述的,其中π是操作名称,τ是数据类型,o是描述为轨道类型的域。例如,嵌入颜色0, 1,3RGB为拓扑面提供RGB坐标,而pos1, 2,3Point 3D将每个拓扑顶点映射到某些3D坐标。这两个嵌入数据支持图3中的G-map表示,并且是本文中我们唯一使用的数据。两个立方体的嵌入的直观描述在图中提供。 五、4. 建模操作由于表示几何对象的拓扑结构图重写是项重写到非线性结构的扩展。我们建议阅读[46]以快速介绍图重写,或者[13]以更深入地解释软件工程。图重写允许匹配图中的模式,并将其替换为新的模式。在这样的框架中,两种模式都是图。4.1. 图重写一个图形变换规则rLR是一个简单的规则,其中左手边L和右手边R是图。对于我们的需要,图转换规则可以理解为一对(L, R),其中通过唯一标识符访问节点。如果R中的节点具有相同的标识符,则L的节点被保留。 如果不存在这样的节点,则将其删除。对称地,R中的节点如果来自L的节点没有共享相同的标识符,则是添加的节点。在本文中,我们将使用节点名作为标识符。图1中提供了图形转换规则的示例。第6(a)段。该规则删除节点x和y之间的弧,添加新节点z,节点x和z之间的弧以及z和y之间的弧。由转换保留的元素通过它们的名称来标识。这里只保留了节点x和y规则R的应用L图G上的R依赖于左模式的出现或匹配的说明L在变换后的图G中。对于我们来说,图G中L的一个匹配对应于图G中类似于L的一个子图。更确切地说,“类似于”意味着同构,即,存在G的子图GL,对于该子图GL,存在从L到GL的保持节点邻接的双射f从一个给定的匹配,我们可以应用该规则。出现在L和R中的保留元素用于R. Pascual,H.Belhaouari,A.Arnould等人图形和视觉计算6(2022)2000496⇒=:→⟨⟩⟨⟩·−··−··−·↦→↦→·−·↦→·−··−·⟨ ⟩⟨ ⟩·−··−·见图6。通 过 匹配x的图变换规则(a)及其应用(b)a,yb,和(x年)的(a)(b)。匹配的上域,即,节点a、b,并且为了可读性,突出显示它们之间的弧将R中添加的元素与周围的上下文联系起来。这个上下文由图G组成,其中GL的元素已经被移除。形式构造利用了一个monic态射mL G,即,从L到G的内射映射,保持图的结构(节点、弧和标签)。一旦提供匹配m,将r应用于图G,通过删除子图GL m(L)并添加R,得到图H。推导记为Gr,m H,并通过范畴构造实现(见[12])。操作被定义为一个规则的直觉通过移除和添加元素足以理解本文中的讨论。在图6(b)中示出了来自图6(a)的规则的应用。从L到G的匹配映射x到a,y到b,x和y之间的弧到a和B.将规则应用于G时,任何不在匹配范围内的元素都保持不变,并传播规则所描述的修改。它删除了节点a和b之间的弧,在节点a和c之间添加了一条弧,并在c和B.规则的出现以绿色突出显示,而修改以黄色突出显示。4.2. G映射重写作为第一步,我们说明了使用图变换来表示拓扑操作与简单的例子。图7基于边的自由度提供了2-G-映射中的顶点插入的两种可能性。自由边是一个0, 2 -轨道,其中2-链接是循环,而缝合边是一个0, 2 -轨道,其中2-链接是非循环弧。这种区别导致了顶点插入操作的两种配置:一种是自由边(见图2)。7(a)为规则和图。7(b)的应用程序的例子)和一个用于缝合边缘(见图7(c)和7(d))。应用图形转换规则依赖于从左侧模式到重写图形的映射。图重写的标准方法需要节点和边的完整映射,以保持节点邻接和标签。在这里,规则不适用于任何图,而只适用于广义映射,定义为具有正则性的图。特别是,G-map的每个箭头需要在每个维度上恰好有一个入射弧选择单个节点就足够了,因为我们可以通过左模式和重写图的联合遍历来构建完整的映射我们用图1的规则应用说明了构造。7(b). 此应用程序假设匹配将节点x映射到节点b。因为匹配必须保持节点邻接和标签,所以唯一可能的匹配将与x关联的弧映射到与b关联的弧上。因此x2x映射到b2b,而x0y映射到b0d.现在,将弧事件映射到x提供了有关match应该映射与x相邻的节点。实际上,将x0y映射到b0d的有效匹配必须将y映射到d.通过递归地探索与新发现的节点相关的弧,我们可以从x映射到b的唯一信息中明确地重新创建匹配。直观地,入射弧约束,并且因此,一般化的映射,允许从部分映射重建匹配。所需的最少信息是L的每个连通分支的一个节点的映射。因此,[10]为每个连接的组件指定一个特定的节点,称为hook,而不是显式地提供整个匹配映射。4.3. 重新标记函数如果建模操作被描述为图形变换,则应单独指定每种可能的配置。然而,建模操作通常是为特定的拓扑单元定义的例如,我们可以定义一个面的挤出,而不考虑其arity,即,其边缘数为此,[9,17]在规则的节点上引入了标签。这些标签实际上是广义轨道类型,并允许重写广义地图,而不管具体的布局。这些扩展的规则被称为规则模式,其中左模式和右模式被称为图模式。理解用规则方案描述的操作的应用的最简单的构造可能是[19],使用重新标记函数。其基本思想是规则方案由轨道类型参数化,而规则方案的所有轨道标签描述通过遵循轨道类型参数中的维度的位置而获得的重新标签函数。这些重新标记函数允许重写轨道,给定相同类型的初始轨道图参数化规则方案。这个过程称为节点的实例化。我们现在将提供关系函数的形式构造和图方案的实例化。本小节的其余部分可以跳过,因为第4.4节提供了一些非正式的解释。第4.4节的非正式解释应该足以理解第5节中提出的算法,这是我们工作的主要贡献。然而,需要以下细节来理解算法的正确性证明。单元格支持建模操作的定义。操作的一些示例是面的细分和体积定义这些操作而不管特定拓扑,即,而不考虑面中的边的数量或面在体积中的布置因此,在[9,17]中,图变换规则被扩展为轨道类型参数化。规则被指定一个轨道类型作为参数,直观地描述规则的修改轨道。每个节点也被分配了一个轨道类型,但作为用于计算操作的标签这些扩展规则允许编写通用规则,而不管特定的布局。它们的实例化将通用规则专门化为特定配置,即,一个基本的图形变换规则。实际上,规则方案描述了变换的折叠表示,其必须被展开以获得可以修改对象的实际图变换。例如,顶点插入的两种配置可以通过沿其2-连杆折叠边来统一。我们得到图8(a)的规则。该规则使用轨道类型2进行参数化。为了获得图级规则,我们选择一个由轨道2组成的图。然后使用该图展开所有节点标签。如果展开为2-环,则规则方案提供图7(a)的图形变换规则,而用共享2-链路的两个节点展开产生图7(c)的规则。我们将看到,我们甚至可以进一步折叠图变换规则以获得图1的规则方案。8(b). 形式上,折叠和展开通过重新标记函数定义。R. Pascual,H.Belhaouari,A.Arnould等人图形和视觉计算6(2022)2000497↦→↦→′′⟨ ⟩↦→个文件夹⟨ ⟩我 的天⟨ ⟩=⟨ ⟩ ⟨ ⟩⟨ =:[]→[]{}[]⟨ ⟩ ↦→ ⟨⟩{→→}=↦→个文件夹⟨ ⟩ ⟨ ⟩{ ↦→⟨⟩↦→⟨⟩联系我们联系我们⟨⟩↦→·−··−·⟨⟩↦→·−··−··−·见图7。自由边(a)顶点插入的图变换规则及其在外边(b)2-G-映射上的应用B.缝边(c)顶点插入的图变换规则及其在2-G-映射内边(d)上的应用e.弧颜色图例:3、2、1和0。见图8。顶点插入的规则方案:(a)通过折叠2-链接和(b)0和2-链接。4.3.1. 重新标记功能在[19]中引入,重新标记函数允许重写轨道类型。定义4.1(重新标记功能)。重标记函数是一个偏函数f0,n0,n_,在0,n上的内射,其中_是一个特殊的符号,称为去符号.将重新标记函数应用于轨道类型是它在轨道内的每个维度上的应用比如说,0 1, 2 2(0, 2)1, 2 .如果我们假设参考轨道类型为o和重新标记的轨道类型 否,则位置 在轨道类型内的尺寸的完全描述了重新标记功能。 例如,给定0, 2,1, 2,可以明确地重建重新标记函数0一,二,二。使用重新标记函数的动机是对轨道重写进行编码。因此,我们通常将这样的函数表示为轨道类型的重新标记。设o(oi)i≤k是定义f的维数集(按递增值排序),则f为记作<$o<$$>→<$i(f(oi))i≤k <$。 内射性简单地意味着维度d不能在o′(f (o i ))i≤k中出现两次。让我们注意到,严格地说,o不是轨道类型,因为它可能包含符号在这个意义上,它是一个广义的轨道类型,为方便起见,我们也称之为轨道类型。请注意,重新标记函数的域o不能包含删除符号。见图9。轨道(a)和(d)的类型为0,2π,通过重新标记函数0,2ππ→1,2π标记修改(b)和(e),通过重新标记函数0,2π→1,2π标记删除(c)和(f)。弧颜色图例:三、2,1和0。重新标记功能自然地从轨道类型重写扩展到轨道重写。给定一个重新标记函数o o′和一个轨道o(v),可以通过根据函数重新标记所有弧来构建轨道o′(v例如,应用于图1的图的重新标记函数01,22。9(a)产生图的图形。9(b).图中的突出显示。 9以后会被利用。在这里,我们只对弧重新标记感兴趣弧颜色的修改。与节点a和b关联的2-环产生与节点a1和b1关联的2-环,如重新标记2 2所描述的。同样,01将弧变换为0b变成a11b1.应用在图9(d)的曲线图上的相同函数产生图9(d)的曲线图。9(e).移除符号“_”将轨道类型扩展为广义轨道类型。这个特殊的符号扩展了重新标记函数的定义及其在轨道上的应用例如,0_,2 2表示删除0标签,同时保留2。与任何维类似,删除符号可能出现在节点标签的轨道类型例如,_,2是一个有效的节点标签。假设参考轨道类型为0, 2,则可以明确地重建重新标记函数0, 2,2。当应用于动态观察时,所有重新标记为_的弧实际上都将被删除。在图1A和1B中提供了两个示例。图9(c)和9(f),使用图9(a)和9(d)的曲线图作为参考。在这些示例中,弧a0b,c0e和d0f没有相应的a0和b0,c0和e0,d0和f0之间的弧线R. Pascual,H.Belhaouari,A.Arnould等人图形和视觉计算6(2022)2000498⟨⟩S⟨⟩S⟨ ⟩⟨ ⟩S⟨⟩↦→⟨ ⟩⋃⋃∅S⋃⋃重标记函数允许对称为图模式的图的折叠表示进行编码。定义4.2(图形方案和规则方案)。设[0,n]是定义在[0,n]上的轨道类型。关于n维图的一个概型,(n,n,n)-图概型,或者简单地说,图方案由图S组成,图S的弧被标记在[0,n]上,节点被标记有与图S相同长度的广义轨道类型。对于S的每个节点v,我们写o v一个规则方案在图上,或简单的规则方案,是一个图transfor-见图10。从图1右侧图案中提取的孤立节点。8(b).当被认为是轨道0,2上的图形方案时,其在图1的轨道图上的实例化。9(a)产生图的图形。9(b).类似地,其在图1B的轨道图上的实例化。9(d)产生图的图形。9(e).运动规则L−ε→oε在圣西罗。其中L和R是定义为规则模式的轨道类型也被称为它的参数,当上下文清楚时可以省略。规则方案的两个图形方案必须共享相同的轨道类型。图方案的节点标签用作占位符来编码给定轨道类型的任何轨道。更准确地说,图模式的每个节点都要被其类型与其标签匹配的轨道所替代。例如,简化为由轨道类型0、2标记的唯一节点的图形方案可以用自由或缝合边缘来实例化,如图1A和1B所示。9(a)和9(d)。一旦图方案包含多个节点,一个附加条件就开始起作用。标记节点的轨道类型的大小条件意味着它们都与o共享相同数量的符号。因此,节点替换可以从用o构建的重新标记函数中获得。的所有节点将被替换为类型为o的相同轨道,其弧将被附加到节点的重新标记函数重新标记。图形方案可用于定义规则,要求-注意,左模式和右模式都是定义在相同轨道类型上的图形方案。4.3.2. 实例化通过重新标记函数重构对应于给定图形方案的展开图这个过程被归纳地定义并称为图模式的实例化。我们提供了实例化过程的一步一步的构造,以便于理解。对于下面的定义,我们考虑一个定义在轨道类型为o上的图模式S和一个由o类型的轨道组成的图O。孤立节点。第一个组件是隔离节点s的实例化,即,没有弧的节点。在这种情况下,实例化过程被简化为将重新标记函数应用于为实例化选择的轨道图。 这种图表方案的一个例子在图中提供。图10中描绘了其实例化中的一些。图9(b)和9(e)(当被认为是轨道上的图形方案时)。定义4.3(独立节点的实例化)。如果S具有({s},n)的形式,则它与O的实例化是通过将重新标记函数o→os应用于O而获得的图。<$o(({s},),O)=[<$o →<$os](O)离散图离散图的实例化,即,没有弧的图由其标记节点的实例化的并集组成图中给出了一个例子。 十一岁见图11。离散图方案(a)从图1的右侧图案提取。8(b),实例化(b)与图的轨道图。9(a),和实例化(c)与图的轨道图。9 (d)。见图12。图方案(a)具有两个节点之间的弧,以及(b)和(c)通过添加0-链路的两个实例化。弧颜色图例:3、2、1和0.弧两个节点之间的弧的实例化通过两个重新标记函数在相同初始省道的省道图像之间添加链接。图中提供了一个例子。 12个。定义4.5(弧的实例化)。对于s是S的节点,u是O的节点,我们将(u,s)作为u在<$o<$(({s},<$),O)中的镜像。如果S的形式为({s,t},{s·−i·t}),则它的实例化为Oextends<$o<$(({s,t},n),O)来链接来自O的相同节点的副本:<$o<$(({s,t},{s·−i·t}),O)=<$o <$(({s,t},),O)<$(u,s)·−i·(u,t)u∈O对于u∈O(u,s)· − i ·(u,t),我们记为<$o<$(s ·− i · t,O)。完整的图形方案。从离散图的实例化出发,通过对每个弧进行实例化,得到图方案的完整实例化。定义4.6(图方案的实例化)。如果是(V,E)的形式,它的O实例化扩展了<$o((V,),O),以根据E的所有弧链接副本:定义4.4(离散方案的实例化)。如果S是形式(V,V),则它与O的实例化是Io((V,E),O)=Io((V,E),O)v·−i·v′∈Eιo(v·−i·v′,O)用O实例化S的每个节点。Io((V,),O)=Io(({v},),O)v∈V实例化图形方案直观地对应于:1. 统一了重标记函数的应用(按节点上的轨道类型R. Pascual,H.Belhaouari,A.Arnould等人图形和视觉计算6(2022)2000499⟨⟩⟨ ⟩⟨ ⟩⟨ ⟩⟨ ⟩L→R⟨⟩⟨ ⟩LR⟨ ⟩↦→⟨⟩⟨⟩⟨⟩⟨⟩⟨ ⟩ ⟨⟩⟨⟩↦→↦→↦→⟨⟩⟨⟩2. 每当图形方案中有弧时,规则方案。 规则模式L−→oR是定义为具有类型为o的相同轨道O的和的实例化。所得到的实例化直接产生图变换<$o(,O)<$o(,O),如第4.2节中所讨论的。让我们用图2的两个规则的重建来说明。7(a)和7(c)通过图的规则方案。8(b).我们分别
下载后可阅读完整内容,剩余1页未读,立即下载
cpongm
- 粉丝: 4
- 资源: 2万+
上传资源 快速赚钱
- 我的内容管理 收起
- 我的资源 快来上传第一个资源
- 我的收益 登录查看自己的收益
- 我的积分 登录查看自己的积分
- 我的C币 登录后查看C币余额
- 我的收藏
- 我的下载
- 下载帮助
会员权益专享
最新资源
- zigbee-cluster-library-specification
- JSBSim Reference Manual
- c++校园超市商品信息管理系统课程设计说明书(含源代码) (2).pdf
- 建筑供配电系统相关课件.pptx
- 企业管理规章制度及管理模式.doc
- vb打开摄像头.doc
- 云计算-可信计算中认证协议改进方案.pdf
- [详细完整版]单片机编程4.ppt
- c语言常用算法.pdf
- c++经典程序代码大全.pdf
- 单片机数字时钟资料.doc
- 11项目管理前沿1.0.pptx
- 基于ssm的“魅力”繁峙宣传网站的设计与实现论文.doc
- 智慧交通综合解决方案.pptx
- 建筑防潮设计-PowerPointPresentati.pptx
- SPC统计过程控制程序.pptx
资源上传下载、课程学习等过程中有任何疑问或建议,欢迎提出宝贵意见哦~我们会及时处理!
点击此处反馈
安全验证
文档复制为VIP权益,开通VIP直接复制
信息提交成功