Thomas Bellet

Agnès Arnould

Pascale Le Gall

Ceo R William

B Roland

R Banner

W Simpson

J F Scott

G Garfield

Ceo J K Smith

Constraint-preserving labeled graph transformations for topology-based geometric modeling

Keywords: DPO graph transformation, topology-based geometric modeling, graph transformation with variables, labeled graphs, generalized maps, consistency preservation, static analysis, algebraic data types

de documents scientifiques de niveau recherche, publiés ou non, émanant des établissements d'enseignement et de recherche français ou étrangers, des laboratoires publics ou privés.

Introduction

In the early 1970s, the concept of graph transformation became of interest in computer science. Derived from string and tree rewriting techniques, this rule-based approach offers a very natural way to describe complex transformations on an intuitive level. For example, anyone observing the transformation given in Figure 1 easily understands the change made in the company organization: the new CEO hires a plant director who is in charge of manufacturing and purchase. Nowadays, thanks to their expressiveness, graph transformations have applications in many areas such as software engineering [START_REF] Baresi | Tutorial introduction to graph transformation: A software engineering perspective[END_REF], concurrent and distributed systems [START_REF]Handbook of Graph Grammars and Computing by Graph Transformation: Concurrency, Parallelism, and Distribution[END_REF], visual modeling [START_REF] Taentzer | AGG: A graph transformation environment for modeling and validation of software[END_REF] or database design [START_REF] Paredaens | A graph-oriented object database model[END_REF].

Our interest concerns the application of graph transformations to topology-based geometric modeling [START_REF] Damiand | Combinatorial Maps: Efficient Data Structures for Computer Graphics and Image Processing[END_REF], a field that deals with the representation and manipulation of objects according to their topological structure (cell subdivision) and their embedding (other types of information attached to their topological cells). As topological structures can be represented as a particular class of graphs, the use of graph transformations to define modeling operations have already been proposed in the past [START_REF] Poudret | Graph Transformation for Topology Modelling[END_REF][START_REF] Spicher | Declarative mesh subdivision using topological rewriting in MGS[END_REF][START_REF] Smith | Local specification of surface subdivision algorithms[END_REF].

In this article, we propose a generic graph transformation approach that allows the implementation of modeling operations of any application domain. Indeed, object constructions and transformations depend on the targeted domain; e.g. add or remove some matter to sculpt (arts), add a window on a wall (architecture), rotate a gear (engineering), combine partial scans (archaeology), etc. The definition and implementation of such operations are always time-comsuming and tedious. Every single operation has to be designed, coded, debugged and optimized. It is even common nowadays that modelers include a cleaning post-treatment function to fix inconsistencies in transformed objects when operations are too complex to maintain object consistency along the operation code. As this article will show, this need for a reliable and flexible framework to define and implement modeling operations can be efficiently addressed by graph transformations.

Let us take consider two operation examples with the face triangulation of Figure 2(a) and the edge removal of Figure 2(b)) in the case of colored 2D objects. In both figures, the topological structure of the object under transformation contains four faces (two triangles, a square and a pentagon) glued all together, while the embedding associates a color to each face. Note that both operations simultaneously transform the topological structure and the embedding. The face triangulation topologically subdivides the face into triangles, while from the embedding point of view, colors are computed for the new faces as the mix of the subdivided face color and the neighboring face color. The edge removal topologically consists in merging two neighboring faces by removing the shared edge while the embedding modification consists in mixing the two original face colors. Using the topological model of generalized maps [START_REF] Lienhardt | Topological models for boundary representation: a comparison with n-dimensional generalized maps[END_REF][START_REF] Lienhardt | N-dimensional generalised combinatorial maps and cellular quasimanifolds[END_REF][START_REF] Damiand | Combinatorial Maps: Efficient Data Structures for Computer Graphics and Image Processing[END_REF], objects are defined as a particular subclass of labeled graphs in which arc labels encode their topological structure and labeling constraints define their consistency. The implementation of modeling operations with graph transformations requires some dedicated features of graph transformations. In [START_REF] Poudret | Topology-based Geometric Modelling for Biological Cellular Processes[END_REF][START_REF] Poudret | Graph Transformation for Topology Modelling[END_REF][START_REF] Poudret | Transformations de graphes pour les opérations topologiques en modélisation géométrique -Application à l'étude de la dynamique de l'appareil de Golgi[END_REF], we previously introduced dedicated rule variables to generically handle the topological genericity of modeling operations, i.e. to automatically compute the topological transformation depending on the cell size. For example, such variables allow to define the topological triangulation of any face (triangle, rectangle, pentagon, etc.) by a single rule. This article addresses the embedding aspect of modeling operations. Considering a representation of embedded generalized maps as labeled graphs introduced in [START_REF] Bellet | Rule-based transformations for geometric modeling[END_REF] and in which node labels and associated labeling constraints encode object embedding, we will study under which conditions relabeling graph transformations of [START_REF] Habel | Relabelling in graph transformation[END_REF] preserve the embedding consistency of the object under modeling. For example, in the case of the edge removal of Figure 2(b), we will ensure that by construction, after the application of the corresponding rules, all nodes of the resulting face end up labeled with the same color. Based on [START_REF] Hoffmann | Graph transformation with variables[END_REF], we will then introduce a rule-based language that allows the new embedding to be generically computed (e.g. to compute the mix of face colors for any colored object). Using dedicated graph transformation variables and terms, the resulting rule schemes will provide the means of both accessing the existing embedding through the topological structure and applying functions provided by the user with embedding data types. For example, the triangulation of Figure 2(a) will be defined by a rule scheme in which the colors of the created faces are computed by applying the user function "mix of two colors" to the subdivided face color and the respective adjacent face colors. As the safety of this user-oriented language is as essential as its expressiveness, we will provide syntactic conditions to guide rule scheme design and ensure object consistency preservation.

The presented variables and terms are comparable to the attribute variables introduced by B. Hoffman in [START_REF] Hoffmann | Graph transformation with variables[END_REF] which allow one to associate new labels to arcs and nodes by applying computations on initial labels associated to arcs and nodes of the graph under transformation. However, aside from their embedding manipulation possibilities, they offer two additional benefits from a graph transformation point of view. First, they take advantage of the regularity of graphs representing nD objects (which can be retrieved in other graph structures) to avoid any additional identifier naming for variables: nodes are directly used as identifiers to access embedding data and are considered as the default variables of a rule (they are called node variables in the sequel). Secondly, the design of geometric modeling operations requires accessing and modifying embedding values of not only nodes occurring in the matched pattern of the rule, but also of nodes located beyond the rule pattern. Let us briefly illustrate this novelty. For the face triangulation of Figure 2(a), we need to access the colors of neighbor faces without matching the face in the rule pattern in order to allow the possibility of a non-existent neighbor (e.g. the yellow triangle has no adjacent face on the right). Similarly, for the edge removal of Figure 2(a), all nodes of the two adjacent faces must have their color changed to the mixed color, while the rule pattern must be limited to the removed edge in order to keep the operation generic in respect to the face sizes (otherwise, the rule would specifically define the removal of an edge between a triangle and a rectangle). We therefore introduce operators dedicated to the traversal of topological structures starting from a given node, and a step-by-step rule scheme instantiation mechanism that carefully propagates modifications of embedding values.To our knowledge, such traversals and modifications of graphs beyond the pattern matched by the rule are original with respect to all existing frameworks of graph transformations with variables, including our own approach for topological transformations [START_REF] Poudret | Topology-based Geometric Modelling for Biological Cellular Processes[END_REF][START_REF] Poudret | Graph Transformation for Topology Modelling[END_REF]. This paper is organized as follows. First, Section 2 presents related works mostly consisting of the existing L-sytem approaches of geometric modeling (usually referred as procedural modeling), and of some successful graph transformation applications which include the biological study case at the origin of this work. Section 3 then presents the labeled graph transformation fundamentals of our work. In particular, we describe relabeling graph transformations introduced by [START_REF] Habel | Relabelling in graph transformation[END_REF] that will allow us to modify objects. We also present the use of variables in graph transformations as introduced by [START_REF] Hoffmann | Graph transformation with variables[END_REF]. The context of topological-based geometric modeling is then presented in Section 4. We focus on the topological model of generalized maps [START_REF] Lienhardt | N-dimensional generalised combinatorial maps and cellular quasimanifolds[END_REF] and we give the conditions from [START_REF] Poudret | Graph Transformation for Topology Modelling[END_REF] under which graph transformations preserve the topological consistency. Section 5 then similarly presents our embedded version of generalized maps and conditions under which basic graph transformations preserve the embedding consistency. The next three sections focus on the rule-based language dedicated to embedding modifications. Section 6 introduces the rule scheme syntax, in particular terms that allow generic computation of new embedding values from existing ones in the object (e.g. to mix two unspecified face colors). Section 7 presents the rule scheme application, especially how schemes are instantiated to propagate minimally defined modifications (e.g. automatically change the color of all nodes of one face). Section 8 provides syntactic conditions on rule schemes to ensure embedding consistency preservation. Section 9 then presents some applications of this work. In particular, after providing few other rule examples, we present both a practical application to physical simulation and the implemented software tool that runs this simulation and any other prototyped modeler. Finally, Section 10 presents some concluding remarks.

Related works

This section presents the motivations and the origins of our graph transformation-based approach of geometric modeling. First, we present the rule-based approaches of geometric modeling (mostly based on L-systems) that have already proved to be successful in order to model some particular object classes. Secondly, we present similar issues (i.e. issues involving similar structural transformations in a controlled and safe manner) that have already been tackled by graph transformations.

Procedural modeling

Formal rule languages have been used for twenty-five years in the context of geometric modeling, and are usually referred as procedural modeling techniques. These techniques focus on creating a model from a rule set, rather than editing the model via user input. They are particularly useful to model objects that are too cumbersome to be modeled by hand or objects that already exists in the physical world. The concept of procedural modeling originates in the fractal notion introduced by Benoit Mandelbrot [START_REF] Mandelbrot | Fractals: Form, chance, and dimension[END_REF]. Fractals are mathematical sets that exhibit repeating patterns displayed at every scale. They have proved particularly useful as similar regular patterns can be found in the shape of natural objects (e.g. symmetries, trees, spirals, meanders, waves, foams, tessellations, cracks and stripes). For example, the Romanesco broccoli, the nautilus shell and the frost fractals of Figure 3 can all be mathematically modeled by fractals. From the observation of similar, but weaker, regularities in most plants, biologist Aristid Lindenmayer introduced L-systems [START_REF] Prusinkiewicz | The algorithmic beauty of plants (The Virtual Laboratory)[END_REF] to model plant growth and development. L-Systems basically consist in a set of production rules that have to be successively applied from a given axiom until a stop condition is satisfied. They are therefore suited to represent arborescent structures, such as the flowers in Figure 4(a) [START_REF] Prusinkiewicz | Animation of plant development[END_REF], or the trees in Figure 4(b) [START_REF] Měch | Visual models of plants interacting with their environment[END_REF]. Moreover, L-systems have already been used in a topological-based context in [START_REF] Peyrat | Generating vast varieties of realistic leaves with parametric 2Gmap L-systems[END_REF] to model leaf growth as in Figure 4(d), in [START_REF] Petrenko | Flower modelling using natural interface and 3gmap l-systems[END_REF] to model flowers, or in [START_REF] Bohl | Modeling Fruits and Their Internal Structure Using Parametric 3Gmap L-systems[END_REF] to model internal structure of fruits as in Figure 4(d). Nowadays, L-systems are behind the vegetation of most video games or movies involving CGI, usually created through the SpedTree toolkit1 .

Applications of L-systems are not limited to plants. In particular, [START_REF] Wonka | Instant architecture[END_REF] introduced a new type of grammar dedicated to automatically model buildings. In the same way as with plants, building designs are derived using grammars that define building shapes. For example, the three buildings in Figure 5(a) from [START_REF] Müller | Procedural modeling of buildings[END_REF] are generated from the same shape grammar. Moreover, 3D models of existing buildings can also be generated from aerial pictures [START_REF] Vanegas | Building reconstruction using Manhattan-world grammars[END_REF] in order to be displayed in navigation applications. For the [START_REF] Parish | Procedural modeling of cities[END_REF]. Note that similar grammars are also used as a corrective measure to build navigation maps from construction plans and aerial photographs. Indeed, because of human errors and necessary adaptive measures, the reality on the ground frequently differs from the construction plans.

Let us finally emphasize the reason why we ruled out L-systems to design the language of a generic geometric modeler. Such a language must cover any potential application domain (computer-aided design and manufacturing, mechanical engineering, architecture, geology, archaeology, medical image processing, scientific visualization, movies, video games, . . . ), and therefore it must address a large class of modeling operations. In all the presented applications, L-systems and graph grammars are defined by a limited set of high-level operations such as creating a new branch, inserting a floor or subdividing a district with a road. These high-level rules do not contain all the low-level transformations on actual object representations and therefore each of them has its own dedicated implementation and consistency preservation mechanism. This lack of adaptability and robustness entails that every added rule requires additional implementation and debugging efforts, which is particularly undesirable for a generic modeler. L-systems are therefore a good solution for specific modeling issues but not for generic modeling purposes.

Graph transformation applications

As Section 3 will present the graph transformation theory, the following subsection outlines the advantages of this approach without going into every detail. First, conversely to L-systems, graph transformations operate at low-level on graph structures and therefore rules are self-contained. For a given graph transformation class, it is therefore possible to apply all rules with a single rule application engine. This point is crucial in the design of a generic modeling tool as it minimizes the implementation and debugging efforts. Moreover, such a low-level definition ensures that given some required graph properties (e.g. for geometric consistency), it is therefore possible to express conditions on rules that will consistently maintain those properties along graph transformations. Finally, graph transformations also allow the use of high-level variables based on this strong low-level theoretical ground, therefore offering as much expressive power as L-systems.

Among applications that already take advantage of graph transformations, the best known is surely software engineering as graph transformations provide the tools to tackle the variety of problems inherent to software design. Graph transformations already address program refactoring, syntax and semantics of visual languages, visual modeling of behavior and programming, software specifications and evolution, security policies, etc. [START_REF]Handbook of Graph Grammars and Computing by Graph Transformation: Concurrency, Parallelism, and Distribution[END_REF][START_REF] Baresi | Tutorial introduction to graph transformation: A software engineering perspective[END_REF][START_REF] Ehrig | Fundamentals of Algebraic Graph Transformation[END_REF]. The variety of problems is also reflected in the multiplication of dedicated tools (e.g. EMorF, Fujaba, Gremlin, Henshin, eMoflon, DiaGen) in addition to the established generic graph transformation tools (e.g. GrGen.NET, GP, Groove, AGG, GMTE).

But graph transformations also have numerous applications aside from software engineering. In the field of computer graphics, graph transformations have been used for shape recognition purposes. In particular, in [START_REF] You | A syntactic approach to shape recognition using attributed grammars[END_REF][START_REF] Tsai | Attributed grammar-a tool for combining syntactic and statistical approaches to pattern recognition[END_REF], attributed grammars were defined to describe and classify the syntactic structures of two-dimensional shapes. However, although it proved to be functional, the final system that was using a combination of syntactic and statistical pattern recognition techniques was abandoned for purely statistical approaches that were shown to be more efficient. As L-systems, graph transformations also have applications in biology. But as they operate at a lower level on graph structures, their applications concern more specifically molecular biology [START_REF] Rosselló | Graph transformation in molecular biology[END_REF][START_REF] Blinov | Graph theory for rule-based modeling of biochemical networks[END_REF][START_REF] Danos | Graphs, Rewriting and Pathway Reconstruction for Rule-Based Models[END_REF], i.e. the synthesis and interactions of DNA, RNA, and proteins. Among them, we investigated in [START_REF] Poudret | Topology-based Geometric Modelling for Biological Cellular Processes[END_REF] the processing of proteins by the Golgi apparatus. In particular, as this process involves the packaging of proteins into membrane-bound vesicles, the use of graph transformations is particularly useful to model the involved topological evolutions illustrated in Figure 6(a). Transition vesicles carrying proteins are absorbed by the Golgi apparatus and secretion vesicles are created while proteins have been processed and packaged. To implement and run simulations on the different hypotheses proposed by biologists for the Golgi's operation (e.g. the "plates" and the "tower" hypothesis simulations illustrated in Figure 6(b) and 6(c)), we proposed in [START_REF] Poudret | Graph Transformation for Topology Modelling[END_REF] graph transformation variables dedicated to topological transformations, along with syntactic conditions on rules that ensure the topological consistency of transformed objects. These variables allowed us to generically abstract topological cells (vertices, edges, faces, volumes) and their transformations.

To extend the use of these variables, we showed that they offer a safer and easier design of topological operations to design a topological-based geometric modeler [START_REF] Bellet | Designing a topological modeler kernel: a rule-based approach[END_REF], rather that the use of traditional ad-hoc implementations that are fastidious to code and vulnerable to consistency bugs. But the topological transformations are not the only issues at stake to design topological-based geometric modeler. Concrete applications deal with several data types attached to the topological structure and called embeddings. Embeddings usually include standart geometric data describing the shape of the objects (e.g. points, curves, surfaces) and specific data that depend on the targeted application (e.g. molecule concentration for biology, rock density for geology, material for architecture). For example, the Golgi simulations of Figure 6 involved several embeddings whose transformations had to be carefully hard-coded: vertex 3D positions to define the evolving model shape, protein quantities carried by the different volumes, and membrane porosity associated to the faces between volumes.

Therefore, the proposed graph transformation-based language must also address these multiple embeddings. In [START_REF] Bellet | Rule-based transformations for geometric modeling[END_REF], we defined a new graph category that allow nodes to have multiple labels in order to simultaneously represent the multiple embedding types (e.g. a face being labelled by both its color and its porosity) and proved the existence of graph transformations in this category. We also introduced a new type of dedicated variables and operators to express embedding transformations in rules. In this article, we present the final version of these variables as they are implemented in the tool set Jerboa [START_REF] Belhaouari | JERBOA: A graph transformation library for topology-based geometric modeling[END_REF] that allows a geometric modeler kernel to be generated from a set of rules and that will be presented in Section 9. As for topological variables, we also introduce syntactic conditions on rules that ensure the embedding consistency of transformed objects.

Graph transformations

Graphs are non-linear structures, defined by a set of objects, usually called vertices or nodes, and a set of links between these objects, usually called edges or arcs. To avoid confusion with the specific vocabulary of geometric modeling, we will subsequently prefer to use the word "node" rather than the word "vertex", and the word "arc" rather than "edge" when refering to graph elements. Graphs are often depicted in a diagrammatic form with dots or circles to represent nodes and lines or curves to represent arcs between nodes, directed or undirected. Graph transformations commonly refer to rule-based languages designed to manipulate graphs. Among all graph transformation approaches, we choose the so-called double-pushout approach (or DPO) [START_REF] Ehrig | Introduction to the algebraic theory of graph grammars[END_REF][START_REF] Corradini | Handbook of Graph Grammars and Computing by Graph Transformation[END_REF][START_REF] Ehrig | Fundamentals of Algebraic Graph Transformation[END_REF] for several reasons: our previous works took place in the DPO framework; to our knowledge, [START_REF] Hoffmann | Graph transformation with variables[END_REF] is the only framework dedicated to the generic manipulation of variables in graph transformations, which is expressed in the DPO framework; most importantly, we want to take advantage of the well-founded DPO framework given in [START_REF] Habel | Relabelling in graph transformation[END_REF] which allows the relabeling of nodes and arcs in graph transformations.

Double-pushout graph transformation

In the DPO approach, a transformation is expressed using two gluing diagrams defined in terms of category theory. More precisely, these diagrams are pushouts in the category of graphs and graph morphisms. In order to make the presentation more intuitive, let us consider the simple example of a DPO graph transformation given in Figure 7. The rule is given at the top of Figure 7 by the three graphs L, K and R and by the two graph inclusions2 L ← K → R. In this example, nodes of graphs are identified by letters (a, b or c) and are labeled by numbers (1, 3 or 5 while arcs are anonymous and labeled by numbers (2 or 4). Intuitively, the left-hand side of the rule L is the pattern to transform, the right-hand side R is the transformed pattern, and the interface K is the preserved part common to both L and R. The graph morphism L → G allows the matched pattern (graph L) to be identified inside the graph under transformation (graph G) (in Figure 7, the match morphism coincides with the inclusion). In the first pushout (1), all elements (nodes and arcs) in L that are not in K are removed in D. In the example, the two arcs that loop on nodes a and b are removed: graph D results from the removing of loops on both nodes a and b in graph G. In the second pushout (2), all elements of R that are not already in K are added while all elements in K are preserved. In the example, an arc is added between the two preserved nodes a and b (graph H). When the match L → G meets some conditions, then the transformation is well defined, and the double-pushout construction defines a unique graph H (up to graph isomorphism), that is the result of the application of the graph transformation L ← K → R through the match morphism L → G. In classical DPO transformations, graph morphisms have to preserve both arc and nodes labels, and therefore prevent relabeling. Note that the relabeling of an arc can still be achieved by removing it while adding an arc with the new label between the same source and target nodes, but this not the case for the relabeling of a node. Consequently, we prefer the DPO approach of [START_REF] Habel | Relabelling in graph transformation[END_REF] that considers partially labeled graphs and therefore allows relabeling. Let us take the example of the relabeling rule of Figure 8. In the left-hand side L, node b is initially labeled by 7 while it is relabeled by 3 in the right-hand side R, and therefore unlabeled in the interface K. Note that the two morphisms K → L and K → R on partially labeled graphs L, K, R do not preserve labeling, in particular the undefined label of b.

a b (L) 1 3 a b (K) 1 a b (R) 1 3 2 3 a b (G) 1 3 c 5 a b (D) 1 3 c 5 a b (H) 1 3 c 5 (1) (2) 2 2 2 2 2 4 4 4
We now present the main definitions and results of [START_REF] Habel | Relabelling in graph transformation[END_REF] on partially labeled graph transformations.

Graph transformations on partially labeled graphs

A partially labeled graph G = (V G , E G , s G , t G , l G,V , l G,E
) consists of two finite sets V G and E G of nodes and arcs, two source and target functions s G , t G : E G → V G , and two partial labeling functions 3 l G,V : V G → C V and l G,E : E G → C E , where C V and C E are fixed sets of node and arc labels. We say that G is totally labeled if l G,V and l G,E are total functions. A path in a graph G is a sequence e 1 ...e k of arcs of G with 1 ≤ k, such t G (e i ) = s G (e i+1 ) for each 1 ≤ i < k. s G (e 1 ) and t G (e k ) are respectively called the path source and the path target and the word l G,E (e 1 )...l G,E (e k ) is called the path label. Moreover, if s G (e 1 ) = t G (e k ), the path is called a cycle. From now on, partially labeled graphs are simply called graphs. Let us point out that in the following, all graphs G of the form (V G , E G , s G , t G , l G,V , l G,E ) will be symmetric, that is, for all edge e in E G , there will be an edge e in E G , such that s G (e ) = t G (e), t G (e ) = s G (e) and l G,E (e ) is defined if and only if l G,E (e) is defined, and in this case, l G,E (e ) = l G,E (e). So, instead of considering a framework built over directed graphs, we could have considered only undirected graphs. We finally prefer to manipulate directed graphs and to require them to be symmetric, both to directy benefit from the results of [START_REF] Habel | Relabelling in graph transformation[END_REF] expressed for directed graphs and to anticipate the adaptation of our work for topological models other than generalized maps.

A graph morphism g : G → H between two graphs G and H consists of two functions g V : V G → V H and g E : E G → E H that preserve sources, targets and labels, that is, s H

• g E = g V • s G , t H • g E = g V • t G ,
and l H (g(x)) = l G (x) for all 4 x in Dom(l G ). A morphism g is injective (resp. surjective) if g V and g E are injective (resp. surjective), and is an isomorphism if it is injective, surjective and preserves undefinedness 5 . In the latter case, G and H are isomorphic. Furthermore, we call g an inclusion if g(x) = x for all x in G. An inclusion is denoted by the symbol → (or the symbol ← if the target graph is introduced first). Finally, morphism composition is defined componentwise as function compositions.

Definition 1 (Rule). A rule r : L ← K → R consists of two inclusions K → L and K → R such that:

(1) for all x ∈ L, l L (x) = ⊥ implies x ∈ K and l R (x) = ⊥, (2) for all x ∈ R, l R (x) = ⊥ implies x ∈ K and l L (x) = ⊥.

3 Given two sets A and B, a partial function f : A → B is a function from subset A of A to B. The set A is the domain of f and is denoted by Dom(f ). We say that f (x) is undefined, and write f (x) =⊥, if x is in A -Dom(f ). 4 To simplify, we amalgamate nodes and arcs in statements that hold for both sets, by omitting the indices E and V . 5 i.e. if l H (g(x)) =⊥ for all x in G\Dom(l G ).

Regarding [START_REF] Habel | Relabelling in graph transformation[END_REF], our rules are simplified since they are built with two inclusions for both sides instead of only one for the left-hand side. We call L the left-hand side, R the right-hand side and K the interface of r. Note that conditions (1) and (2) are trivially satisfied when L and R are totally labeled. Since objects will be represented by totally labeled graphs, a first idea would be to only consider totally labeled graphs in order to simplify definitions: unlabeled elements could be then handle with a dedicated label denoting its own irrelevance. However, this trick would later be inadequate to instantiate rule schemes in Section 7 as this process requires dedicated propagation mechanisms on partially labeled graphs in order to build consistently labeled graphs.

A diagram of graph morphisms, as Figure 9 In [START_REF] Habel | Relabelling in graph transformation[END_REF], authors studied under which conditions usual constructions in the category of totally labeled graphs such as pushouts, pullbacks or direct derivations can be transferred into the category of partially labeled graphs. In particular, properties concerning direct derivations are similar to those on totally labeled graphs. A match morphism m : L → G satisfies the dangling condition with respect to the inclusion L ← K, if no node in m(L)\m(K) is incident to an arc in G\m(L). Given a rule r : L ← K → R and a match morphism m : L → G, there exists a direct derivation as in Figure 9(b) if and only if m satisfies the dangling condition. Moreover, in this case, D and H are unique up to isomorphism, and H is totally labeled if and only if G is totally labeled.

(a), is a pushout if (i) K → R → H = K → D → H and (ii) for every pair of graph morphisms (R → H , D → H ) with K → R → H = K → D → H , there is a unique morphism H → H such that R → H = R → H → H and D → H = D → H → H . The same diagram is a pullback if property (i) holds and (iii) if for every pair of graph morphisms (K → R, K → D) with K → R → H = K → D → H, there is a unique morphism K → K such that K → R = K → K → R and K → D = K → K → D. A pushout is natural if it is also a pullback. K / / R D / / H 0 (a) L o o ? _ m (1)
K / / (2) R G o o ? _ D / / H 0 (b)

Graph transformation with variables

To meet the various application needs, graph transformations have been enriched with variables to make them generic. Intuitively, rules with variables describe as many concrete rules as there are possibilities to instantiate variables with concrete elements. Different types of variables have been introduced to enrich graph transformations. For example, attribute variables allow label computations [START_REF] Hoffmann | Graph rewrite rules with structural recursion[END_REF] or labeling constraints [START_REF] Orejas | Symbolic attributed graphs for attributed graph transformation[END_REF][START_REF] Orejas | Lazy graph transformation[END_REF], while graph variables [START_REF] Drewes | Hierarchical graph transformation[END_REF][START_REF] Hoffmann | More on graph rewriting with contextual refinement[END_REF] and hyperedge variables [START_REF] Habel | Hyperedge replacement: grammars and languages[END_REF][START_REF] Habel | Expressiveness of graph conditions with variables[END_REF] allow structural transformations (i.e. modifications of whole graphs connected to some attachment nodes designated by the rule pattern).

We will not use these variables in this article, but we will use the framework for graph transformation with variables introduced in [START_REF] Hoffmann | Graph transformation with variables[END_REF] as it provides general guidelines to deal with any variable type in graph transformations. We briefly describe its main elements: the rule scheme syntax, the instantiation of variables, and the whole rule application process.

Rule scheme. The sets C V and C E of node and arc labels are extended by a set X of variable names. Graphs built over6 are called graph schemes. Then a rule scheme is a rule r : L ← K → R where L, K, and R are graph schemes. The kernel G of G is the graph obtained by removing all labels that contain a variable occurrence.

Instantiation. A substitution function σ specifies how variable names occurring in a rule scheme are substituted. From the instanciation of variables in the graphs L, K, R, yielding to the graphs denoted respectively as L σ , K σ and R σ , the instanciation of a rule scheme r : L ← K → R according to σ defines a particular rule instance r σ : L σ ← K σ → R σ . Note that r σ is a rule without variables as defined in Definition 1.

Rule application. Let G be a graph, and r : L ← K → R be a rule scheme. 1. Identify a kernel match m : L → G of the kernel L of L in G (if it exists); 2. If possible, find a substitution σ such that there exists a morphism m : L σ → G extending m; 3. Construct the instance r σ : L σ ← K σ → R σ and apply r σ to get the direct derivation G ⇒ rσ,m H.

In [START_REF] Hoffmann | Graph transformation with variables[END_REF], this framework is used for three types of variables with specific purposes: attribute variables, clone variables and graph variables. Depending on the variable type, the substitution, and therefore the instantiation, differ, but the generic framework remains valid. By following it, we already introduced in [START_REF] Poudret | Graph Transformation for Topology Modelling[END_REF][START_REF] Bellet | Designing a topological modeler kernel: a rule-based approach[END_REF] another type of variables that allow generic transformations of topological structures and which proved the relevance of [START_REF] Hoffmann | Graph transformation with variables[END_REF] for introducing new types of graph transformation variables. For the embedding aspect of geometric operations, we first thought that the attribute variables of [START_REF] Hoffmann | Graph transformation with variables[END_REF] were expressive enough. Their usage is illustrated by the rule scheme of Figure 10. For the matched arc, the new label of the target node becomes the sum of the initial label of the source node and of the initial label of the arc. Intuitively, the application of this rule scheme to a graph allows one to deduce a substitution of attributed variables occurring on the left-hand side L, and to compute the new labels by evaluation of the expressions of the right-hand side R. Note that the substitution σ = {x → 1, y → 2, z → 7} would allow to derive the previous rule of Figure 8, according that + is evaluated as the usual addition operation.

a x b (L) z a x (R) x+y y a b (K) b y x
But attribute variables do not exactly fit our usage as we need to access the node labels through the node names to allow topological structure traversal (e.g. to access the adjacent face color in the case of the colored triangulation given in the introduction). In the sequel, we will introduce dedicated variables, but, roughly speaking, they will come down to attribute variable indirections in the most basic cases. Note also that by convention, rule schemes will be identified by dotted double lines circling their L, K and R graphs (see Figure 10) while single dotted lines are used for rule instance graphs (see Figure 8).

Data types

In our setting, objects will be modeled by labeled graphs whose nodes are labeled by geometric or dedicated data (thereafter referred to as embedding) such as the color of a face or the 2D position of a point. These data are clearly typed and provided with functions to perform computations on them.

In addition, as a same embedding value can appear multiple times in an object (e.g. in the transformed object of Figure 2, two faces have the same color), we need to identify these multiple occurrences when collecting object embedding values. We therefore consider for each type τ , the type τ • , multiset of elements of type τ . A multiset may be viewed as a function that associates its multiplicity (a natural number) to each element. We use the following notation:

for the empty multiset (of any type τ • ), a 1 , . . . a p for a multiset with p occurrences of elements of type τ . For example, the multiset that contains the element A with the multiplicity 1, the element B with the multiplicity 2, and where all other elements are of multiplicity 0, is denoted A, B, B . Similarly, the multiset of face colors of the transformed object of Figure 2 is denoted , , , .

We then present the main elements of term construction and evaluation.

Signature. A data type signature Ω = (S, F ) consists of a set S of type names and a family of function names provided with a profile on S ∪ S • where S

• = {s • | s ∈ S} is the set of multisets over types in S. A function name f provided with a profile s 1 . . . s m+1 with s i ∈ S ∪ S • for i ∈ 1..m + 1 is denoted f : s 1 × . . . × s m → s m+1 .
Terms. For an S-indexed family X = s∈S X s of variables, the set T Ω (X) = s∈S∪S • T Ω (X) s of terms over Ω is the least set satisfying:

• for all variables x in X s , x ∈ T Ω (X) s ;

• for all function names f :

s 1 ×. . .×s m → s m+1 in F , for all terms t 1 ∈ T Ω (X) s1 , . . . , t m ∈ T Ω (X) sm , then f (t 1 , . . . , t m ) ∈ T Ω (X) sm+1 .
We note t : s a term t in T Ω (X) s .

Algebra. An Ω-algebra A consists of an S-indexed family of nonempty sets s∈S A s and for each f :

s 1 × . . . × s m → s m+1 in F , of a function f A : A s1 × . . . × A sm → A sm+1 where for s i ∈ S • , that is s i = s • for some s in S, A si = { a 1 , . . . , a p | 0 ≤ p, ∀k ∈ 0..p, a k ∈ A s }.
Evaluation. For σ = s∈S σ s an S-indexed family of assignments σ s : X s → A s , the evaluation σ : T Ω (X) s → A s of a term t : s is defined as:

• for all variables x in X s , σ(x) = σ s (x);

• for all function names f : s 1 × . . . × s m → s m+1 in F and all terms t 1 : s 1 , . . . , t m : s m , σ(f (t 1 , . . . , t m )) = f A (σ(t 1 ), . . . , σ(t m )).

In order to design a modeling operation, the user is expected to provide both a data type signature Ω = (S, F ) and an Ω-algebra A, with all the data types and functions required by its application domain to define its modeling operations. In the sequel, the considered user types are point 2D, vector 2D and color, that respectively model 2D positions, 2D vectors and face colors. They are provided with all classical functions such as + : point 2D × vector 2D → point 2D that represents the translation of a point by a vector, center : point 2D × point 2D → point 2D that computes the center of two points, bary : point 2D • → point 2D that computes the barycenter of a multiset of points, or mix : color × color → color that defines the average color of two given colors. The algebra A will be left implicit. When needed, the carrier set A τ of a data type τ will be simply denoted τ .

Note that multisets could also have been introduced by considering a higher order approach as a starting point, i.e. by introducing type constructions such as sets, lists or tuples of elements of the same type. But the resulting data types would have been richer than necessary, since we would have at our disposal types such as sets of sets of elements, and we only need a generic type for denoting multisets of basic type elements. Our presentation of data types minimally meets this need by semantically imposing all multiset properties such as commutativity of the element insertion, specification of the element multiplicity, etc., but also offers a simple and concise notation for multisets.

Topological generalized maps as partially labeled graphs

In topology-based modeling, objects are defined according to: • their topological structure -i.e. their cell subdivision (vertices, edges, faces, volumes) and the adjacency relations between these cells; for example, the three objects of Figure 11(a) have the same topological structure: a closed face F that has four edges and four vertices;

• their embedding, which includes all other types of information attached to their topological cells, including the geometric information required to capture their shape; for the objects of Figure 11(a), geometric points are attached to topological vertices and colors are attached to faces.

There are many topological structures that allow one to represent different classes of objects: tetrahedral [START_REF] Lang | Simplicial Sets and Triangular Patches[END_REF] or polyhedral [START_REF] Mantyla | Introduction to Solid Modeling[END_REF][START_REF] Weiler | The radial edge structure: A topological representation for non-manifold geometric boundary modeling[END_REF][START_REF] Damiand | Combinatorial Maps: Efficient Data Structures for Computer Graphics and Image Processing[END_REF], fixed dimension (2D [START_REF] Mantyla | Introduction to Solid Modeling[END_REF] or 3D [START_REF] Weiler | The radial edge structure: A topological representation for non-manifold geometric boundary modeling[END_REF]) or dimension-independent [START_REF] Lang | Simplicial Sets and Triangular Patches[END_REF][START_REF] Damiand | Combinatorial Maps: Efficient Data Structures for Computer Graphics and Image Processing[END_REF], and most of them can be seen as a particular class of graphs. Among those, we choose the topological model of generalized maps (or G-maps) [START_REF] Lienhardt | Topological models for boundary representation: a comparison with n-dimensional generalized maps[END_REF][START_REF] Lienhardt | N-dimensional generalised combinatorial maps and cellular quasimanifolds[END_REF][START_REF] Damiand | Combinatorial Maps: Efficient Data Structures for Computer Graphics and Image Processing[END_REF] because its mathematical definition can be rather easily encoded within a formal framework. In G-maps, the topological structure is handled by both the graph structure and the arc labels, while the embedding is defined by the node labels.

More precisely, the class of G-maps that represents valid objects is defined by labeling constraints. Hence, to define modeling operations with graph transformations, we investigate under which conditions G-map constraints, and so object consistency, are preserved along transformations. Examples of inconsistencies are given in Figure 11: an edge with a single extremity instead of two, or two faces glued along a vertex instead of an edge are topological inconsistencies, while a face embedded with two colors instead of one, or without any defined color are embedding inconsistencies. The representation of an object as a G-map intuitively comes from its decomposition into topological cells (vertices, edges, faces, volumes, etc.). For example, the 2D topological object of Figure 12(a) can be decomposed into a 2-dimensional G-map. The object is first decomposed into faces in Figure 12(b). These faces are linked along their common edge with a 2-relation: the index 2 indicates that two cells of dimension 2 (faces) share an edge. In the same way, faces are split into edges connected with the 1-relation in Figure 12(c). At last, edges are split into vertices by the 0-relation to obtain the 2-G-map of Figure 12(d). Nodes obtained at the end of the process are the G-map ones and the different i-relations become labeled arcs: for a 2-dimensional G-map, i belongs to {0, 1, 2}. Therefore, G-maps are particular graphs whose arcs are labeled by integers: for a dimension n, n-G-maps are partially labeled graphs such that arcs are totally labeled in C E = [0, n] where [0, n] is the interval of integers between 0 and n. G-maps are undirected7 : thus, for each i-arc of source v, of target v , there is also a corresponding reversed i-arc of source v and target v. As usual, double reversed arcs are graphically represented by undirected arcs (see Figure 12(d)). Note that in order to be more readable, in all figures given subsequently, we use the graphical codes introduced in Figure 12 (black line for 0-arcs, red dashed line for 1-arcs and blue double line for 2-arcs) instead of writing a label near the corresponding arc. So, the way undirected arcs will be drawn will implicitly indicate their label values. (e) CC 0 1 2 (e)

Generalized maps

A B C D E F G u v w x y z (a) 2 2 2 2 2 2 (b) 1 1 1 1 1 1 1 (c)
Figure 13: Orbits adjacent to e Topological cells are not explicitly represented in G-maps but implicitly defined as subgraphs. They can be computed using graph traversals defined by an originating node and a given set of arc labels. For example, in Figure 13(a), the 0-cell (vertex) adjacent to e is the subgraph which contains e, the nodes that can be reached from node e using 1-arcs or 2-arcs (nodes c, e, g and i) and the arcs themselves. This subgraph is denoted by G 1 2 (e), or simply 1 2 (e) if the context (graph G) is obvious, and models the vertex B of Figure 12(a). In Figure 13(b), the 1-cell adjacent to e (edge w) is the subgraph G 0 2 (e) that contains node e and nodes reachable through 0-arcs and 2-arcs (nodes e, f, g and h), and the corresponding arcs. Finally, in Figure 13(c), the 2-cell adjacent to e (face F) is the subgraph denoted by 0 1 (e) and built from node e with 1-arcs and 2-arcs.

In fact, topological cells (face, edge or vertex) are particular cases of orbits denoting subgraphs built from an originating node and a set of labels. The different orbit types of an n-G-map are all possible subsets of [0, n] and are classically denoted by an ordered word o of edge labels placed in brackets o . In addition to the already mentioned orbit types ( 0 1 for face, 0 2 for edge, 1 2 for vertex), let us give some other examples of orbit types: the orbit 0 (e) in Figure 13(d) represents the half-edge adjacent to e, and the orbit 0 1 2 (e) in Figure 13(e) represents the whole connected component. We say that a label i belongs to an orbit o if i occurs in the word o.

The following definition introduces the notions of topological graphs (which include G-maps but also their transformation patterns), orbits, orbit equivalences, and orbit completions. In particular, these last two notions will be useful later in the article to handle embedding transformations. Note also that according to the notation commonly used in geometric modeling, the arc labeling function of topological graph is denoted by α.

Definition 3 (n-topological graph and orbit). A partially labeled graph

G = (V, E, s, t, l V , α) is an n-dimensional topological graph if the arc labeling function α is a total function with codomain C E = [0, n].
For o an orbit type of dimension n, let ≡ G o be the equivalence orbit relation defined on V × V as the reflexive, symmetric and transitive closure built from arcs with labels in o, i.e., ensuring that for each arc e of G labeled by a letter in o, we have s(e) ≡ G o t(e).

For any node

v of G, the o -orbit of G = (V, E, s, t, l V , α) adjacent to v, denoted by G o (v), is defined as the least subgraph (V , E , s , t , l V , α ) of G whose set V of nodes includes {v} ∪ {v | v ∈ E, ∃w ∈ V , v ≡ G o
w}, whose set E of arcs includes {e | s(e) ∈ V , t(e) ∈ V , α(e) ∈ o} and whose s , t , l V and α are restrictions of corresponding fonctions in G to the sets Let us now give the consistency constraints that objects defined as G-maps must satisfy. Definition 4 (Generalized map). An n-dimensional generalized map, or n-G-map, is a partially labeled n-topological graph G = (V, E, s, t, l V , α) that satisfies the following topological consistency constraints:

V or E . If the context is clear, G o (v) is simply denoted o (v).

More generally, for any subgraph

G → G, the o -completion of G in G, denoted by G o (G ), is defined as the least subgraph (V , E , s , t , l V , α ) of G whose set V of nodes includes V G ∪ {v | v ∈ E, ∃w ∈ V , v ≡ G o w}, whose set E of arcs includes {e | s(e) ∈ V , t(e) ∈ V , α(e) ∈
• Symmetry constraint: G is undirected,

• Adjacent arc constraint: each node is the source node of exactly n + 1 arcs respectively labeled from 0 to n,

• Cycle constraint: for every i and j such that 0 ≤ i ≤ i + 2 ≤ j ≤ n, there exists a cycle labeled by ijij starting from each node.

These constraints ensure that objects represented by embedded G-maps are consistent manifolds [START_REF] Lienhardt | N-dimensional generalised combinatorial maps and cellular quasimanifolds[END_REF]. In particular, the cycle constraint ensures that in G-maps, two i-cells can only be adjacent along (i -1)-cells. For instance, in the 2-G-map of Figure 12(d), the 0202-cycle constraint implies that faces are stuck along topological edges. Let us notice that thanks to loops (see 2-loops in Figure 12(d)), these three constraints also hold at the border of objects.

Basic topological transformations

Within a geometric modeler, operations defined on objects are called topological (respectively geometric) if their main purpose is to change the topological structure (respectively the embedding). Obviously, some operations fall under both aspects, as the rounding operation that consists in the replacement of a vertex or a sharp edge by a curved surface [START_REF] Ledoux | Geometric Modelling with CASL[END_REF].

Roughly speaking, topological operations are applications that allow one to build new generalized maps from generalized maps. The definition of topological operations by graph transformation rules advantageously facilitates the study of stating whether or not the resulting graphs are also generalized maps. To achieve this, rules on generalized maps have to preserve by construction the topological constraints of Definition 4.

In previous works [START_REF] Poudret | Topology-based Geometric Modelling for Biological Cellular Processes[END_REF][START_REF] Poudret | Graph Transformation for Topology Modelling[END_REF][START_REF] Poudret | Transformations de graphes pour les opérations topologiques en modélisation géométrique -Application à l'étude de la dynamique de l'appareil de Golgi[END_REF], we elaborated the following syntactic conditions that precisely ensure the preservation of topological consistency: Theorem 1 (Topological consistency preservation). Let r : L ← K → R be a graph transformation rule, G an n-G-map and m : L → G a match morphism.

The direct transformation G ⇒ r,m H produces an n-G-map H if the following conditions of topological consistency preservation are satisfied:

• Symmetry condition: the three graphs L, K and R are undirected n-topological graphs.

• Adjacent arcs condition:

preserved nodes of K are sources of arcs having the same labels in both the left-hand side L and the right-hand side R; removed nodes of L\K and added nodes of R\K must be source of exactly n+1 arcs respectively labeled from 0 to n.

• Cycle condition: for all (i, j) such

0 ≤ i ≤ i + 2 ≤ j ≤ n,
any added node of R\K is the source of an ijij-cycle;

any preserved node of K which is the source of an ijij-cycle in L, is also the source of an ijij-cycle in R; any preserved node of K which is not the source of an ijij-cycle in L is source of the same i-arcs and j-arcs in L and R.

The interested reader can find the proof of this theorem in [START_REF] Poudret | Graph Transformation for Topology Modelling[END_REF]. In particular, we demonstrated that the dangling condition (see Subsection 3.2) is always ensured when a rule that satisfies those conditions is applied to a G-map.

Theorem 1 only expresses sufficient conditions to produce G-maps starting from G-maps, and not necessary conditions. It is intended to be like this: first of all, in line with the way experts in geometric modeling manipulate models, we restrict ourselves to undirected graphs and thus, we require that all graphs are undirected, without this condition being necessary. Indeed, clearly, we could write rules with graphs which are not symmetric. Thus, conditions provided by Theorem 1 have the interest of corresponding to the intuitions of experts in geometric modeling: this is particularly the case for the last two conditions: for example, the adjacent arcs condition simply requires that after transformation, all nodes should have exactly n + 1 arcs labeled from 0 to n, which is exactly part of the definition of G-maps. It is the same for the third condition of Theorem 1, with respect to the cycle constraint. Up to our knowlege, these conditions make it possible to write a sufficiently large class of representative modeling operations.

Intuitively, the adjacent arcs condition (combined with the symmetry condition) ensures that every node concerned by the rule application ends up being the source and the target of exactly one i-arc for each i ∈ [0, n] in the transformed object. The first point requires that preserved nodes have their adjacent i-arcs in both sides of the rule. Indeed, by construction, i-arcs that are not matched by the rule are preserved in the transformed graph. For example, the rule of Figure 15(a) adds a 0-arc between nodes e and h in R without matching any 0-arc in L. Consequently, in the resulting graph H, nodes e and h have both their original 0-arc issued from G and the 0-arc added in R, and therefore H is not a G-map. The second point requires that added or removed nodes have exactly one i-arc for each i ∈ [0, n]. Indeed, nodes can only be consistently added with all their adjacent arcs. Similarly, removing a node without matching a given i-arc would imply that an i-arc remains in the transformed G-map with the source node or the target node missing. For example, the rule of Figure 15(b) removes node f without matching its adjacent 1-arc and 2-arc. Consequently, the resulting graph H contains two dangling arcs. The cycle condition ensures that every node transformed by the rule ends up belonging to an ijij-cycle for all 0 ≤ i ≤ i + 2 ≤ j ≤ n. The first point requires that added nodes belong to an ijij-cycle in R, as all their adjacent arcs belong to R. For example, the rule of Figure 16(a) adds two nodes o and p without their 0202-cycle in R. Consequently, they do not belong to such a cycle in the resulting graph H. The second point requires that preserved nodes which belong to an ijij-cycle in L also belong to such a cycle in R. Similarly to the previous point, their adjacent i-arcs and j-arcs belong to R, therefore the ijij-cycle has to belong to R. The last point requires that preserved nodes which do not belong to an ijij-cycle in L have their adjacent i-arcs and j-arcs also preserved. As a matter of fact, any modification of those arcs might break the ijij-cycle as it is only partially matched by the rule. For example, in Figure 16(b), by removing the 0-arc between nodes e and h in the rule, we break the 0202-cycle in the resulting graph H.

Embedded generalized maps and their basic transformations

Our approach is generic, both in terms of the dimension of the objects and of the nature of the considered embedding. For simplicity purposes, in the following n-G-maps will be simply denoted as G-maps. Moreover, all illustrative examples will be given for 2D objects with either one of the two embedding data types of Figure 11(a): we will either consider 2D positions attached to topological vertices or colors attached to faces. However, realistic objects simultaneously handle several data types holding on different topological cells.

Embedding representation

The topological structure of n-G-maps have been defined as labeled graphs where the arc label set is

C E = [0, n].
We complete here this definition with node labels to represent the embedding. We already sketched that every dedicated embedding has its own data type and is defined on a particular kind of topological cell: in our example, positions are attached to vertices and colors to faces.

A node labeling function defining an embedding will be typed both by a topological orbit type and a data type. We characterize such a node labeling function as an embedding operation π : o → τ where π is the operation name, τ is its data type and o is its domain given as an n-dimensional orbit type. Hence, for a G-map embedded on an embedding π : o → τ , the node label set C V is the set of values τ of type τ and when the profile of π is obvious, the node labeling function is simply noted π. Thus, a G-map provided with a single embedding will be a particular case of partially labeled graph, generically denoted as a tuple (V, E, s, t, π, α). In this article, we consider the following embedding operations:

• pos : 1 2 → point 2D the embedding that associates 2D positions (values of type point 2D) with vertices ( 1 2 -orbits) of 2-G-maps (see Figure 17(a));

• col : 0 1 → color the embedding that associates colors (values of type color) with faces ( 0 1orbits) of 2-G-maps (see Figure 17(b)).

Moreover, as an embedding operation π : o → τ is characterized by its domain orbit, it is expected that in an embedded G-map G = (V, E, s, t, π, α), all nodes of a common o -orbit share the same label by π, also called π-label. For example, in Figure 17(a), nodes c, e, g and i that belong to the same vertex orbit 1 2 are labeled by the same value B. Similarly, in Figure 17(b), nodes a, b, c, d, e andf that belong to the same face are labeled with the same yellow color. This property is captured by an embedding constraint that embedded8 G-maps have to satisfy [START_REF] Bellet | Rule-based transformations for geometric modeling[END_REF].

Definition 5 (Embedded graph and embedded generalized map). Let π : o → τ be an embedding operation of dimension n ≥ 0 with o an orbit type of dimension n and τ a data type.

• Embedded graph: A graph embedded on π, or π-embedded graph, is an n-topological graph G = (V, E, s, t, π, α) where π labels nodes on C V = τ .

• Embedding consistency constraint: A π-embedded graph satisfies the embedding consistency constraint if for all nodes v and w such that v ≡ o w, π(v) = π(w) or π(v) = ⊥ or π(w) = ⊥.

• Embedded G-map: A π-embedded G-map is an n-G-map embedded on π satisfying the embedding consistency constraint and such that π is a total function (i.e. Dom(π) = V ).

Note that the embedding consistency constraint allows an o -orbit to be partially π-labeled as long as the defined π-labels are equal. Therefore, as embedded G-maps are totally labeled, the constraint entails that all nodes of any o -orbit share the same embedding value, i.e. for all nodes v and w such that

v ≡ o w, π(v) = π(w) with π(v) = ⊥.
Intuitively, the topological structure of any π-embedded graph G can then be found by forgetting node labels. For G = (V, E, s, t, π, α), G α = (V, E, s, t, ⊥, α) denotes the underlying topological structure where the everywhere undefined function ⊥ replaces the node labeling function π.

As ≡ o defines a partition of the set V of nodes of a π-embedded graph G that satisfies the embedding consistency constraint, it allows to build a quotient graph of G along o -orbits. For the quotient set of nodes, we consider the set of o -orbits of G. As all nodes of an o -orbit of G are unlabelled or share the same π-label, the resulting quotient node directly inherits this shared π-label if this label exists. For the quotient set of arcs, we consider the set of arcs inherited from G by redefining source and target nodes with their corresponding quotient nodes and by preserving their labels. For example, the quotient along 1 2 -orbits of the embedded G-map of Figure 17(a) is the graph of Figure 18(a). As nodes c, g, e and i belong to the same vertex orbit, they share the same embedding B and give rise to the B-labeled quotient node v in Figure 18(a). The resulting quotient graph contains 5 nodes, one per 1 2 -orbit, with a well-defined π-label. Let us note that by construction, arcs with labels belonging to the orbit type 1 2 become loops. As a consequence, all 1-arcs and 2-arcs adjacent to c, e, g or i are transformed into loops on node v in the quotient graph.

Similarly, Figure 18(b) presents the quotient along 0 1 -orbits of the 2-G-map of Figure 17(b). Nodes a, b, c, d, e and f of the triangle face give rise to the yellow quotient node u while the nodes of the square face give rise the blue quotient node v. In the case of Figure 17(b), we get two nodes with two different colors. Of course, it would have been possible to get nodes sharing the same color. Indeed, it would suffice that the initial G-map contains several faces sharing the same color.

Definition 6 (Embedding quotient). Let G = (V, E, s, t, π, α) be a graph embedded on π : o → τ that satisfies the embedding consistency constraint.

The π-quotient9 graph of G is the graph G /π = (V /π , E /π , s /π , t /π , π /π , α /π ) defined by:

• V /π = V /≡ o ;
• E /π = E with ∀e ∈ E /π , α /π (e) = α(e), s /π (e) = [s(e)] and t /π (e) = [t(e)];

• for [v] in V /≡ o , π /π ([v]) = π(w) if there exists w in G o (v) such that π(w) = ⊥, otherwise π /π ([v]) = ⊥. The π-quotient morphism q : G → G /π is defined by: ∀v ∈ V , q V (v) = [v] and q E = id.
Note that as embedded G-maps both satisfy the embedding consistency constraint and are totally labeled, their quotient graphs are also totally labeled.

Basic embedding transformations

As π-embedded G-maps constitute a particular class of partially labeled graphs, we now investigate how modeling operations on embedded G-maps that modify their geometry can be defined using graph transformation rules (see Definition 1). As an example, we consider the two operations given in Figure 19 that apply on objects with the position embedding pos : 1 2 → point 2D. The vertex translation of Figure 19(a) in a purely geometric operation as it does not affect the topological structure. Position B is translated to F . Conversely, the edge folding of Figure 19 In this section, we explore to what extent basic geometric modeling operations designed for a particular embedded G-map can be defined as basic graph transformations as introduced in Definition 1.

The key point is to ensure these consistency constraints of embedded G-maps are preserved along rules applications, provided that rules satisfy some syntactic conditions.

In the same way that we gave in Theorem 1 syntactic conditions for the preservation of topological consistency constraints, we here investigate syntactic conditions to ensure that embedded G-maps are transformed into embedded G-maps. Let us take the example of the vertex translation of Figure 19(a). Intuitively, we could consider at first sight the rule of Figure 20(a). Unfortunately, such a rule is not appropriate for our needs. Indeed, by matching node e of the rule of Figure 20(a) with node e of the G-map of Figure 17(a), its application results in the graph given in Figure 20(b). Clearly, this graph does not satisfy the embedding consistency constraint as node e does not have the same label as the other nodes of its vertex orbit (c, g and i). To avoid this, all node labels of an embedding orbit should be modified simultaneously and in the same manner. For example, the rule of Figure 21(a) matches (respectively rewrites) a full vertex orbit in L (respectively in R): indeed, all nodes are connected with both 1-arcs and 2-arcs. In fact, both L and R are full 1 2 -orbits. Thus, the application of this rule to the pos-embedded 2-G-map of Figure 17(a) along the identity match morphism gives the pos-embedded 2-G-map of Figure 21(b). The following theorem introduces syntactic conditions on rules that ensure embedding consistency preservation. The direct transformation G ⇒ r,m H produces a π-embedded G-map if the following conditions of embedding consistency preservation are satisfied:

• Embedding consistency: L, K and R satisfy the embedding consistency constraint of Definition 5.

• Full match of transformed embeddings:

if v is a node of K such that π L (v) = π R (v), then every node of R o (v)
is labeled and is the source of exactly one i-arc for each i of o .

• Labeling of extended embedding orbits: if v is a node of K and there exits a node

w in R o (v) such that w is not in L o (v), then there exist v in K with v ≡ L o v and v ≡ R o v such that π L (v ) = ⊥.
Proof. Let π : o → τ be an embedding operation, r : L ← K → R be a graph transformation rule that satisfies the conditions of topological consistency preservation, G a π-embedded G-map and m : L → G a match morphism. We consider the following direct transformation:

L o o ? _ m (1) K / / b (2) R c G o o ? _ D / / H
In double-pushout transformation, each element of H (node, arc, or label) comes either from the right-hand side of the rule R, or from the graph G (through D), or from both. Therefore, to check whether two nodes of H linked with an arc labeled in o are labeled with the same embedding value, the proof considers all cases for the arc source, target and labelling.

Since the rule r satisfies the conditions of topological consistency preservation of Theorem 1, the direct transformation G ⇒ r,m H is well-defined (i.e. the dangling condition is satisfied) and the resulting graph H is an n-G-map. Moreover, with the result of [START_REF] Habel | Relabelling in graph transformation[END_REF] stating that total labeling is preserved by rule application, we know that H is totally labeled, in particular that π is defined on every node of H.

It remains to prove that thanks to the conditions listed in Theorem 2, H is a π-embedded G-map.

We then show by exhaustion10 that for any label i of the orbit type o , and for any i-arc e of H, the source node v of e and the target node w of e have the same defined π-label, i.e. π H (v) = π H (w). As this will ease some symmetrical cases, let us note that thanks to the symmetry preservation (see Theorem 1), e has always a symmetric i-arc with source w and target v in H and also in D (resp. G) if e is also an arc of D (resp. G).

1. e has no antecedent in R. Then e necessarily comes from G. More precisely e, v and w are arc and nodes of D and G respectively.

(a) Both v and w have no antecedent in R. Then v (resp. w) has the same π-label in G (π As G is a π-embedded G-map, π G (v) = π G (w) and therefore π H (v) = π H (w). (c) v has an antecedent v in R, and w has no antecedent in R. According to case 1a, w has the same defined π-labels in G and H (π G (w) = π H (w)). According to case1b, v has the same defined π-labels in G and H (π

G (v) = π H (v) and π G (w) = π H (w)), D and H. As G is a π-embedded G-map, π G (v) = π G (w). Therefore π H (v) = π H (w
G (v) = π H (v)). Finally, as G is a π-embedded G-map, π G (v) = π G (w)
and therefore π H (v) = π H (w). (d) v has no antecedent in R and w has an antecedent in R. This case is similar to case 1c.

2. e has an antecedent e in R. Let v and w be the source and target nodes of e in R, respectively. (c) v has a defined π-label in R but not w , i.e. π R (v ) = ⊥ and π R (w ) = ⊥. Thanks to the rule definition, w is a node of K and thus of L with π L (v ) = ⊥. Because of the condition of full match of transformed embeddings, v can not be an added node and is therefore also a node of K and thus of L with π L (v ) = ⊥. The proof is then similar to case 2b, with two cases depending on wether v and w come from the same o -orbit, but using directly v instead of x as it is labeled. (d) w has a defined π-label in R but not v , i.e. π R (w ) = ⊥ and π R (v ) = ⊥. This case is similar to case 2c.

By transitivity of arcs labeled in o , all nodes v and w of H in the same o -orbit (v ≡ H o w) have the same defined π-label, i.e. π H (v) = π H (w). Thus H is a π-embedded G-map. Let us now make some comments on the constraints given in Theorem 2.

g h q r (R) g h (K) g h (L)
The first of these conditions is straightforward: it requires that all parts of the rule satisfy the embedding consistency constraint. For example, the rule of Figure 22(a) breaks this condition as it adds a new vertex (nodes o, p, q and r) embedded with two different positions F and G.

The second condition forbids the partial redefinition of the embedding shared by an o -orbit as it would break the embedding consistency. If a preserved node has a transformed embedding, then its o -orbit in R is a totally labeled full orbit. The rule of Figure 20(a) falls in this case as node e has its label changed from B to F without fully matching the topological vertex (1-arc and 2-arc are missing). Hence, an embedding value can only be modified if it is modified for the whole support orbit.

The last condition forbids the extension of an o -orbit (by adding new nodes or merging with another o -orbit) without matching the existing embedding value of the orbit. For exemple, the rule of Figure 22(b) breaks this condition as an half-edge whose embedding is unmatched is added to another half-edge whose vertices are embedded by the two positions F and G. Therefore, the application of this rule to the object of Figure 17(a) along the identity morphism would break the embedding consistency: e.g. node b would be labeled by A while its added 2-neighbor u would be labeled by F . As this third condition entails that nodes b and d are labeled in L (and thus in R), the rule labeling should be completed. In R, nodes b and d should be labeled by F and G respectively due to the embedding consistency condition. In L, they should also be labeled by F and G as the condition of full match of transformed embeddings prevents to change their labels while the two vertex orbits are not fully matched by the rule (1-neighbors of b and d are not matched). At last, let us illustrate some of the cases occurring in the proof of Theorem 2 with the example of Figure 23 that details the application of the edge folding operation presented in Figure 19(b) on the embedded G-map of Figure 17(a). The 1-arc that links nodes a and b in H falls into the trivial case 1a. The arc and the two nodes belong to object G and are not matched by the rule. As G satisfies the embedding consistency constraint of embedded G-maps, nodes a and b have the same pos-label in G and therefore in H. The 1-arc that links nodes i and g in H falls into the case 1c, as the arc and node g are not matched by the rule, conversely to node i. As the vertex orbit that contains both nodes i and g in G is not fully matched, the condition of the full match of transformed embeddings prevents the rule to modify the pos-labels of node i. This ensures that nodes i and g have the same pos-label in H as they have the same pos-label in G. Finally, the 1-arc that links nodes u and v with define labels in H falls into the case 2a and the embedding consistency condition ensures that their π-labels are equal in R.

Rule schemes

This section introduces the rule scheme syntax that allows us to define modeling operations independently from the object embedding values. Following the approach of [START_REF] Hoffmann | Graph transformation with variables[END_REF], this syntax includes the use of dedicated variables.

Node variables

As mentioned in Section 3, attribute variables of [START_REF] Hoffmann | Graph transformation with variables[END_REF] do not exactly fit our usage. Computing the new embedding requires both to access the existing embedding (node labels in the transformed object) and to traverse the topological structure (neighboring nodes in the transformed object). Therefore, taking benefit from G-maps regular structures, this article introduces new variables called node variables and provides dedicated operators. Instead of defining a new set of variable names, this approach consists in directly using the identifiers of the nodes of L as variables, and therefore variable names freely exist for all transformations.

The rule schemes of Figure 24 respectively define the translation of a vertex and the folding of an edge, both previously illustrated in Figure 19. Scheme nodes are labelled with terms11 over node variables of L, allowing both to match the existing embedding and to express the new embedding computation. In Figure 24(a), the term e.pos in L gives access to the 2D position associated to the matched vertex, while the term e.pos + v defines in R the new position fo the translated position 12 . At scheme application, the node variable e of L will be substituted by the node matched by e in the transformed object. The operator .pos (resp. .π) will then simply grant access to its pos-label (resp. π-label). Similarly in Figure 24 As described in Section 4, n-G-maps are highly regular graphs. Every node has n + 1 neighbors respectively connected by 0, 1, . . . , n. Therefore, for all i in [0, n], we can define an .α i operator on node variables that gives access to their unique i-neighbor. Let us consider the face triangulation of Figure 25 in the case of the color embedding col : 0 1 → color. To smooth face colors, each created triangle is colored by the mix between the original color of the triangulated face and the color of its adjacent face. Using the .α 2 operator to access adjacent faces, this operation is defined by the rule scheme of Figure 26(b). In the term v = mix(e.col, e.α 2 .col) that defines the color of the bottom face, e.α 2 allows the access to the 2-neighbor of e in the transformed object. At application to the object of 26(a) along the identity morphism (as in Figure 25(a)), this neighbor is g and the face color is therefore defined as mix(e.col, g.col) = mix( , ) = . Similarly, if the scheme is applied as in Figure 25 with a match morphism that associates node e in the rule with node l in the transformed object, the face color is defined as mix(l.col, l.α 2 .col) = mix( , ) = . Finally, note that the case of nodes without adjacent face is covered thanks to the 2-loops -e.g in the first case of Figure 25(a), the term u = mix(b.col, b.α 2 .col) is evaluated as mix(b.col, b.col) = mix( , ) = .

Collect operators

In addition to basic operators (.π and .α i ), we introduce operators that collect all the embedding values carried by a given orbit. Let us illustrate these operators with the face triangulation, but in the case of the position embedding pos : 1 2 → point 2D. It is usually expected that the created vertex is positioned at the center of the triangulated face. For example, to triangulate the top triangle of the object of Figure 27(a), the added vertex should be positioned at the barycenter of A, B and C. To compute this barycenter, the rule scheme of Figure 27 uses the operator pos 0 1 to collect the positions carried by the adjacent face (adjacent 0 1 -orbit). At scheme application to the object of Figure 27(a) along the identity match morphism, pos 0 1 (a) will collect the multiset A, B, C . Similarly, its application to the second triangle will result in B, C, D . Intuitively, this operator is based on the quotient representation introduced in Definition 6 that associates each embedding orbit to a single node, and therefore to a single label.

Consequently, each position value appears only once in the resulting multisets regardless of how many times they appears in the object (e.g A appears 4 times while B appears 6 times in Figure 27(a)). If a same position was collected multiple times, this would entail that multiple vertices would be embedded with this same position. In the case of geometrical points, we usually do not want two vertices to coincide. However, for most applicative data such as colors, quantities or densities, it is common that the same value appears multiple time in the modeled object. Let us consider the example of the operator col 0 1 2 that collects the face colors of the adjacent connected component. The evaluation of col 0 1 2 (a) on the colored object of Figure 26(a) results in the multiset , , , in which has two occurrences as it labels two faces.

More generally, for all embedding π : o → τ and all orbit type o , we can define an operator π o on nodes v. π o (v) collects the embedding values of the o -orbit adjacent to v and stores the collecting values with their multiplicity in a multiset, regardless of embedding orbit sizes. Until now, the family of collect operators has be introduced only from an intuitive point of view, we will formally define it in the next sections, syntactically in Section 6.3 and semantically in Section 6.4 using graph quotients introduced in Definition 6.

Terms and schemes

To sum up, node variables are available straightaway as they are the node identifiers of the left-hand side of the rule scheme L, and they will be substituted by nodes of the transformed G-map at rule scheme application. New embedding values are defined by terms upon these nodes with the introduced G-map operators: the embedding access .π, the neighbor access .α i , and the collect of orbit embeddings π o . Note that in addition to these operators, terms may include various operators and types provided by the user. For example, the translation scheme of Figure 24(a) uses the classical addition between a point and a vector, while the triangulation scheme of Figure 27(b) uses the operator bary that defines the barycenter of a point multiset. These operators and types provided by the user are referred in the following as the user signature.

As in Subsection 3.4, we define embedding terms on the user signature extended by the node variables. A dedicated type (called N ode) provided with some predefined operations is introduced to manipulate these variables in relation the underlying graph structure.

Definition 7 (Terms signature and rule schemes). Let π : o → τ be an embedding operation of dimension n.

Terms signature. Let Ω π = (S π , F π ) be a user signature with S π a set of type names including the π-type τ and F π a set of functions defined on S π ∪ S • π . Ω Map = (S Map , F Map ) is the embedding term signature extended on G-maps defined as S Map = S π ∪ {Node} and F Map = F π ∪ F Node with F Node the set of function names that contains :

• .π : Node → τ ;

• .α i : Node → Node for all i ∈ [0, n];

• π o : Node → τ • for all orbit type o of dimension n.

Graph schemes. Let X be a set of node variables.

A graph scheme G = (V, E, s, t, π, α) on (Ω π , X) is a graph embedded on π : o → T ΩMap (X) τ .
Rule schemes. A rule scheme r : L ← K → R on Ω π is a rule on graph schemes on (Ω π , V L ) with V L the node set of L.

For example, the triangulation rule scheme of Figure 26(b) on Ω col = (S col , F col ) such that S col includes the type color and F col includes the operation mix : color × color → color. Similarly, the rule scheme of Figure 27(b) on Ω pos = (S pos , F pos ) such that S pos includes the type point 2D and F pos includes the operation bary : point 2D • → point 2D.

Evaluation of embedding terms

At rule scheme application, embedding terms have to be evaluated on the embedded G-map under transformation. For example, when the triangulation scheme of Figure 27(b) is applied to the top triangle Figure 27(a), the term pos 0 1 (a) has to be evaluated by the point multiset A, B, C in order to compute the barycenter. The evaluation of terms on G-maps operators is given in the following definition as an extension of the algebra provided by the user on the signature Ω π of his/her sorts and functions. More precisely, given a π-embedded G-map and an Ω π -algebra, we define the extended Ω Map -algebra on embedding terms (see Section 3.4).

Definition 8 (Algebra extension by a G-map).

Let G = (V, E, s, t, π, α) be an n-G-map embedded on π : o → τ , Ω π = (S π , F π ) be a user signature and an Ω π -algebra A.

The extended algebra A G from A by G is the Ω Map -algebra defined as:

• (A Map ) s = A s for s ∈ S π ∪ S • π ; • (A Map ) Node = V ; • for each f of F π , f AMap = f A ;
• .π AMap is the labeling function π;

• for all i ∈ [0, n], for each node v ∈ V , there exists a unique i-arc e ∈ E such that s(e) = v and the .α i AMap function associates v to t(e);

• for all orbit type o , for each node v ∈ V , let G o (v) /π = (V , E , s , t , π , α ) be the embedding quotient of the orbit graph, the π o AMap function associates v to the label multiset of the orbit quotient 13 In particular, the evaluation of collect operators is defined with the graph quotient introduced in Definition 6. For example, to evaluate the term pos 0 1 (a) for the object of Figure 28, we construct the quotient 0 1 (a) /pos of the orbit 0 1 (a). The term evaluation is then defined as the multiset of node labels of that quotient, i.e. A, B, C .

π (v ) | v ∈ V .
Note that an algebra extension from a G-map is well defined. Especially, thanks to G-maps constraints, one node is the source of one and only one i-arc and so .α A G i is a well defined function. As a consequence, collect operators are also well defined functions. To be evaluated, a scheme only requires a kernel match as described in Subsection 3.3. In our case, we will use a match morphism of the topological structure of the left-hand-side m : L α → G in order to remove variable occurrences with node labels, while still properly matching the structure thanks to arc labels. Practically, the node matching part m V of this morphism will be directly used for the substitution σ : X → V G . For example, an identity match morphism between the rule scheme and the object of Figure 26 assigns the variables a, b and e to the nodes a, b and e of the object, resulting in the rule Figure 29(a). Similarly, the rule of rule Figure 29(b) result from a match morphism assigning those nodes to the nodes i, g and l of the object. Definition 9 (Rule scheme evaluation). Let G be a π-embedded G-map, Ω π a user signature and A an Ω π -algebra.

Graph scheme evaluation. Let S = (V, E, s, t, π, α) be a graph scheme on (Ω π , X) and σ : X → V G an assignment of X. The evaluated graph S σ = (V, E, s, t, π σ , α) of S along σ is the π-embedded graph such as π σ (v) = σ(π(v)) for each node v ∈ V .

Rule scheme evaluation. Let r : L ← K → R be a rule scheme on Ω π and m : L α → G a kernel match morphism. The evaluated rule of r along m is the π-embedded rule r m

V : L m V ← K m V → R m V .

Rule scheme instantiation

In this section, we define how rule schemes are instantiated without considering the consistency preservation which is postponed to Section 8. So far, every considered operation has been defined in relation to the specific topological structure of the transformed object. This problem was illustrated in Section 5.2 by the rule of Figure 21 which specifically defines the translation for a vertex adjacent to three edges. This is very restrictive and counter-intuitive from a user-end perspective. On a semantic level, the translation of a vertex has a single meaning, independent from the number of adjacent edges. A user friendly rule scheme should be as simple as in Figure 30 in which a single node relabeling encodes a single embedding transformation. Let us take a more significant example with the edge removal of Figure 31. This operation that will be the red thread of this section involves both topological and embedding modifications: on the topological aspect, the edge is removed and the two adjacent faces are merged; on the embedding aspect, the color of the resulting face is obtained by mixing the colors of the two original faces.

Semantically, this operation does not depend on the configurations of the two faces and should be defined by the simple rule scheme of Figure 32(a). But similarly to the translation, the application of the evaluated rule of Figure 32(b) to the object of Figure 26(a) results in the inconsistent object of Figure 32(c). Indeed, the embedding modifications must be propagated to all nodes of the two faces in order to preserve the G-map consistency. Therefore, it is the task of the instantiation process to extend the evaluated rule to propagate the embedding modification. In our example, the evaluated rule of Figure 32(b) has to be extended into the correct rule of Figure 32(d). This process is divided into two steps: the topological extension that matches all required nodes and the embedding propagation that ensures their consistent relabeling.

d c j i g h e f d c j i (K) (L) d c j i (R) t = mix (e. col, g. col) t t t t u = e. col v = g. col u u u u v v v v (a) Rule scheme d c j i g h e f d c j i (K) (L) d c j i (R) (b) Evaluated rule l j k i a b d c (c) Inconsistent application (L) l j k i g h a b d e c f l j k i a b d c l j k i a b d c (K) (R) (d) Correct rule
Figure 32: Rule scheme of the edge removal and its evaluation

Topological extension

Intuitively, the topological extension uses the match morphism to complete the partial embedding orbits defined by the the evaluated rule with the actual full orbits of the transformed G-map. First, the extension L ⊕m of the left-hand side is computed in Figure 33(a) by pushout between the topological structure of the o -orbit adjacent to the matched pattern G α o (m(L α ) α ), and the left-hand side of the evaluated rule L. The full extended rule L ⊕m ← K ⊕m → R ⊕m is then computed in Figure 33(b) by application of the evaluated rule on the extended left-hand side. Let L ⊕m be the result of the pushout between m o : L α → G α o (m(L α ) α ), the restriction of m to the topological structure of the o -orbit adjacent to the matched pattern, and the inclusion L α → L:

(L ⊕m ) l j k i g h a b d e c f (L ) l j k i g h a b d e c f (G ⟨o⟩ (m(L ) )) α α (L) d c j i g h e f d c j i g h e f α α m ⟨o⟩ (a) Extension of the left-hand side (L ⊕m ) l j k i g h a b d e c f d c j i g h e f d c j i (K) (L) d c j i (R) l j k i a b d c l j k i a b d c (K ⊕m ) (R ⊕m ) (b) Application of the evaluated rule
L α / / m o L m G α o (m(L α ) α ) / / L ⊕m
The topological extension of r along the match morphism m is the rule r ⊕m : L ⊕m ← K ⊕m → R ⊕m defined by the following direct transformation:

L o o ? _ m K / / R L ⊕m o o ? _ K ⊕m / / R ⊕m
Note that the pushout construction of L ⊕m is well founded since the morphisms L α → L and m : L α → G meet the conditions given in [START_REF] Habel | Relabelling in graph transformation[END_REF] ensuring the existence of natural pushouts. Also, note that the resulting rule of Figure 33 would still produce the inconsistent result of Figure 32(c) as extended parts' nodes are not relabeled.

Embedding propagation

The final step of rule scheme instantiation consists in propagating node labels of the extended rule. For example, for the extended rule of Figure 33(b), node labels have to be propagated in order to obtain the final of rule Figure 32(d). This step is a direct application of the quotient representation. For all graphs of the extended rule, each node is relabeled with the label of its images in the quotient graph. For example, in Figure 34 Let G = (V, E, s, t, π, α) be a graph embedded on π : o → τ such that G satisfies the embedding consistency constraint and q : G → G /π the quotient morphism with

G /π = (V /π , E /π , s /π , t /π , π /π , α /π ). The π-embedding propagation of G is the π-embedded graph G π = (V, E, s, t, π , α) such for each node v ∈ V, π (v) = π /π (q V (v)).
For r : L ← K →R an n-topological π-embedded rule, we denote r π the rule

L π ← K π →R π .
Note that as the quotient existence depends on the satisfaction of the embedding consistency constraint, the embedding propagation only applies to rules for which all parts satisfy the constraint. The extended patterns must contain only one label value per embedding orbit in order for their quotient representation to preserve these unique labels. Let us consider the counterexample of Figure 35. The rule scheme defines the edge removal without consistently relabeling the face colors and therefore the face can be labeled by two different colors in the right-hand side of the extended evaluated rule. As this prevents the quotient existence, the embedding propagation cannot be applied.

Moreover, the satisfaction of the embedding consistency constraint by all parts of a rule scheme does not entail the same property on its extended rule, because of the overlap phenomenon that will be detailed in Section . Regardless of consistency preservation, the application of a rule scheme r to an object defined as embedded G-map G along a kernel match morphism m consists in the three instantiation steps of Figure 36(a): 1. the evaluation r m V of the rule scheme r along m V to substitute node variables by nodes of G; 2. the topological extension (r m V ) ⊕m along m of the evaluated rule r m V ; 3. the embedding propagation ((r m V ) ⊕m ) π ) along the extended rule (r m V ) ⊕m ; followed by the the application of the final rule ((r m V ) ⊕m ) π ) on the targeted object G by the DPO transformation of Figure 36(a). Note that as the embedding propagation existence depends on the satisfaction of the embedding consistency constraint by all parts of the extended rule. This will be ensured by conditions on rule schemes provided in Section 8 to preserve G-map consistency. Therefore, rule schemes satisfying those conditions can always be instantiated for any kernel match morphism.

Definition 12 (Instantiation and application of rule scheme). Let r : L ← K → R be a rule scheme on a user signature Ω π , and m : L α → G a kernel match morphism on a π-embedded G-map G.

Let r m

V = L m V ← K m V → R m V
be the evaluation of r along m (Definition 9). Let (r m V ) ⊕m be the topological extension of r m V along 14 m (Definition 10). 14 Thanks to Definition 9 of graph scheme evaluations, L m V α = Lα. Thus the rule can be directly extended along m.

If all parts of (r m V ) ⊕m satisfy the embedding consistency constraint, let ((r m V ) ⊕m ) π be the πembedding propagation of (r m V ) ⊕m (Definition 11).

The instantiation of r along m is ((

r m V ) ⊕m ) π denoted r m : L m ← K m → R m .
If there exists a morphism m * : L m → G extending m, the application of r to G along m denoted by G ⇒ r,m H is defined by the direct transformation G ⇒ r m , m * H.

Finally, note that similarly to the approach of [START_REF] Hoffmann | Graph transformation with variables[END_REF] recalled in Subsection 3.3, the substitution given by the kernel match morphism can not always result in an extended full match of the instantiated rule. Let us take an example with the operation of edge removal of Figure 37. This time, the rule scheme of Figure 37(a) removes an edge between two faces of the same color e.col. The instantiation of the rule scheme along the identity morphism on the object G of Figure 36 results in the rule of Figure 37(b) where the term e.col has been evaluated to yellow. As the extension process rests on the kernel match, the rule can always be extended regardless of the label of the matched object. However, the resulting rule can obviously not be applied to the object as an application match morphism can not be induced because nodes g, h, i and j of the object are blue.

Consistency preservation

This section establishes and proves the conditions on rule schemes that ensure the preservation of G-map constraints. Subsection 8.1 adresses the topological consistency while Subsections 8.2 and 8.3 focus on the embedding consistency. More precisely, we show that rule schemes that satisfy some given conditions can always be instantiated and that the instantiated rules satisfy the original conditions of embedding consistency preservation of Definition 2.

Topological consistency preservation

As the topological extension is the only part of the instantiation that transforms the rule topological structure, let us show that it preserves the conditions of topological consistency preservation of Theorem 1.

Lemma 1 (Topological consistency preservation of topological extension). Let r : L← K →R be a rule embedded on π : o → τ and m : L α → G a kernel match morphism on a π-embedded G-map G.

If r satisfies the conditions of topological consistency preservation of Theorem 1, then the topological extended rule r ⊕m also satisfies these conditions.

Proof. Let us show the three conditions of topological consistency preservation.

Symmetry

Because an n-G-map and its o -orbits are symmetric graphs, the part added by the topological extension is also symmetric. And because L, K and R are symmetric graphs, then L ⊕m , K ⊕m and R ⊕m are also symmetric graphs. Consequently, r ⊕m satisfies the symmetry condition.

Adjacent arcs

As K ⊕m and R ⊕m are computed by application of r on L ⊕m , all new nodes added by the topological extension step are preserved nodes of K ⊕m . Consequently, those nodes are the sources of the same arcs with the same labels on both sides L ⊕m and R ⊕m . Thus all nodes added by the topological extension satisfy the adjacent arc condition. And because r satisfies the adjacent arc condition, r ⊕m also does.

Cycle condition

As already mentioned, all nodes added by the topological extension are preserved nodes of K ⊕m and are the source of the same arcs with the same labels in L ⊕m and R ⊕m . Thus, we have multiple cases to consider depending on what portion of a cycle belong to the extended part. Let us prove the three points of the cycle condition of Theorem 1 for all couple (i, j) such 0 ≤ i ≤ i + 2 ≤ j ≤ n:

• By definition of the topological extension, any added node v of R ⊕m \K ⊕m comes from R\K. And as the rule r satisfies the cycle condition, v is the source of an ijij-cycle in R and also in R ⊕m \K ⊕m .

• If v is a preserved node of K ⊕m and is the source of an ijij-cycle in L ⊕m , then either:

-If v is source of a ijij-cycle in L, because the rule r satisfies the cycle condition, v is the source of an ijij-cycle in R, and so in R ⊕m .

-If some of the four arcs come from L and some others have been added by the topological extension step. Then, due to the cycle condition on r, the old arcs of L are preserved in R, and thus also in L ⊕m and R ⊕m . And, due to topological extension, new arcs are also preserved in L ⊕m , K ⊕m and R ⊕m . Thus, in this case, the preserved node v of K ⊕m is the source of an ijij-cycle in L ⊕m , and is also the source of an ijij-cycle in R ⊕m .

-If the four arcs are added by the topological extension step. Then, as previously, these new arcs are preserved in L ⊕m , K ⊕m and R ⊕m . And thus the preserved node v of K ⊕m is the source of an ijij-cycle in L ⊕m , and is also the source of an ijij-cycle in R ⊕m .

• Finally, if v is a preserved node of K ⊕m and is not the source of an ijij-cycle in L ⊕m , then, as previously, the i-arc and the j-arc of source v can be either old arcs from r, or new arcs added during topological extension step. In both cases, these arcs are preserved in R ⊕m , respectively due to cycle condition of r and topological extension. Consequently, the i-arc and the j-arc of source v are preserved in R ⊕m .

Thus, r ⊕m satisfies the cycle condition.

Consequently, r ⊕m satisfies the conditions of topological consistency preservation of Theorem 1.

This result can directly be extended to the whole rule instantiation.

Theorem 3 (Topological consistency preservation of instantiation). Let r : L ← K → R be a rule scheme on a user signature Ω π , and m : L α → G a kernel match morphism on a π-embedded G-map G.

If r satisfies the conditions of topological consistency preservation of theorem 1, then the instantiated rule r m = ((r m V ) ⊕m ) π , if it exists, also satisfies these conditions.

Proof. As r m V has the same topological structure as r, r m V satisfies the conditions of topological consistency preservation. Then, according to Lemma 1, (r m V ) ⊕m also does. Finally, as the embedding propagation preserves the topological structure, ((r m V ) ⊕m ) π satisfies these conditions.

Case of overlap

Before we study the embedding consistency preservation, we mention a risk occurring with topological extension : the overlap of embedding orbits. By allowing a minimal match of the transformed embeddings that relies on the automatic completion of transformed embedding orbits, we are exposed to unexpected merges of different embedding orbits. Let us consider the face stretching defined by the rule scheme of Figure 38. However, when the rule is applied to the triangle face, the extended rule of Figure 40 is inconsistent as the top vertex ends up embedded in R with two different values A = A -v and A = A + v. This is a clear case of misapplication as we wanted to match and translate four vertices but only match three. We call an overlap such a situation where different embedding orbits manipulated in the rule end up merged in the extended rule and we define a condition on the kernel morphism that prevent it. This condition can be seen as an extension of the injective condition on the match morphism to the embedding orbits. We say that the topological extension of r along m produces an overlap if for v and w two nodes of L

r p q o j i g h e f A A B C r p q o j i g h e f r p q o j i g h e f A' A' ' B' C' (L) (K) (R) r p q o A A B C r p q o r p q o A' B' A' ' C' (L ⊕m ) (K ⊕m ) (R ⊕m ) (a) Inconsistent extended rule A B C D E A' B' C' D E A'' (b) Intuition
(resp. K, R) such that v ≡ L o w (resp. v ≡ K o w , v ≡ R o w ) then v ≡ L ⊕m o w (resp. v ≡ K ⊕m o w, v ≡ R ⊕m o w).
The topological extension of r along m does not produce overlap if m satisfies the following condition of non-overlap: for two nodes v and w of L such as v ≡ L o w, m(v) ≡ G o m(w).

Proof. Let us show that L ⊕m does not contain overlap. Let us suppose that there exist v and w two nodes of L such that v ≡ L o w and v ≡ L ⊕m o w. Then, the overlap comes from the topological extension, i.e the node images m(v) and m(w) belong to the same orbit in G, m(v) ≡ G o m(w). This is contrary to the condition of non-overlap. The proof is similar for K ⊕m and R ⊕m .

Embedding consistency preservation

We now study how the non-overlap condition combined with the conditions of embedding consistency preservations on evaluated rule schemes ensure that the instantiated rules satisfy the conditions of embedding consistency preservation on rules given in Theorem 2. In particular, we will release the condition of full match of transformed embeddings as it was the goal of the automatic orbit completion of transformed embeddings.

We start with the topological extension step. Note that as the nodes added by the topological extension are not labeled, the extended rule is only expected to satisfy a weak version of the full match of transformed embeddings of Theorem 2 that does not require a total labelling of the orbit.

Lemma 3 (Embedding consistency preservation of topological extension). Let r : L← K →R be a rule embedded on π : o → τ and m : L α → G a kernel match morphism on a π-embedded G-map G.

If r satisfies the conditions of topological consistency preservation of Theorem 1, the conditions of embedding consistency and of labeling of extended embedding orbits of Theorem 2, and if m satisfies the condition of non-overlap of Lemma 2, then the topological extended rule r ⊕m : L ⊕m ← K ⊕m →R ⊕m satisfies the following conditions:

• Embedding consistency of Theorem 2: L, K and R satisfy the embedding consistency constraint of Definition 5.

• Weak full match of transformed embeddings: if a preserved node v has a transformed embedding, then

R ⊕m o (v) is a full orbit; i.e. if v is a node of K ⊕m such that π L ⊕m (v) = π R ⊕m (v), then every node of R ⊕m o (v)
is the source of exactly one i-arc for each i of o .

• Labeling of extended embedding orbits of Theorem 2: if v is a node of K and there exits a node w

in R o (v) such that w is not in L o (v), then there exist v in K with v ≡ L o v and v ≡ R o v such that π L (v ) = ⊥.
Proof. Let us show that the three conditions of the Lemma 3 hold.

Embedding consistency Let v and w be two nodes of L ⊕m such that v ≡ L ⊕m o w, π L ⊕m (v) = ⊥ and π L ⊕m (w) = ⊥. Because of the condition of non-overlap, v and w are two nodes of L such v ≡ L o w.

As L satisfies the embedding consistency constraint, π L (v) = π L (w) and therefore π L ⊕m (v) = π L ⊕m (w). The proof is the same for K and R. r ⊕m satisfies the embedding consistency condition.

Weak full match of transformed embedding.

Let v be a node of R ⊕m . If v is a preserved node of K ⊕m or an added node of R ⊕m , thanks to topological extension step, R ⊕m o (v) is a complete orbit. Thus v is the source of exactly one i-arc for each i of o . Then r ⊕m satisfies the weak full match of transformed embedding.

Labeling of extended embedding orbits. Let v be a node of K ⊕m and w a node R ⊕m o (v) such that w is not in L ⊕m o (v). Because the topological extension definition, w is a node of r. As r satisfies the labeling of extended embedding orbits, there exist v in K with v ≡ L o v and v ≡ R o v such that π L (v ) = ⊥. Moreover, because of the topological extension definition, v ≡ L ⊕m o v, v ≡ R ⊕m o v, and π L ⊕m (v ) = ⊥. Therefore, r ⊕m satisfies the labeling of extended embedding orbits.

Let us now show that the embedding propagation step restores the original strong embedding consistency conditions. Lemma 4 (Embedding consistency preservation of the embedding propagation). Let r : L ← K → R be a rule embedded on π : o → τ and m : L α → G a kernel match morphism on a π-embedded G-map G.

If r satisfies the conditions of topological consistency preservation of Theorem 1 and the conditions of Lemma 3, then the embedding propagated rule r π satisfies the conditions of topological consistency preservation of Theorem 1 and the conditions of embedding consistency preservation of Theorem 2.

Proof. As previously said, the embedding propagation step does not modify the topological structure, thus this last step preserves the topological consistency conditions of Theorem 1.

In the same way, the conditions of embedding consistency preservation and of labeling of extended embedding orbits are preserved.

Moreover, the π-embedding propagation step propagates each embedding label along the full o -orbit, the weak condition of full match of transformed embed becomes total as all nodes are become labeled.

Finally, we can extend this result to the whole rule instantiation and show that it always exists if the following conditions of embedding consistency preservation are satisfied.. Theorem 4 (Embedding consistency preservation of instantiation). Let r : L ← K → R be a rule scheme on a user signature Ω π and m : L α → G be a kernel match morphism on a π-embedded G-map G.

The instantiated rule ((r m V ) ⊕m ) π exists and satisfies the conditions of embedding consistency preservation of Theorem 2 if the following conditions are satisfied:

• r satisfies the condition of embedding consistency of Theorem 2;

• r satisfies the condition of labeling of extended embedding orbits of Theorem 2;

• m satisfies the condition of non-overlap of Lemma 2.

Proof. As equal terms are evaluated by equal values, if r satisfies the previous conditions, so does the evaluated rule r m V . Then, the extended rule (r m V ) ⊕m satisfies the condition of Lemma 3, including embedding consistency. Therefore, the propagation ((r m V ) ⊕m ) π exists. Finally, according to Lemma 4, the instanciated rule ((r m V ) ⊕m ) π satisfies the conditions of embedding consistency preservation.

Let us note that the properties of Theorem 4 are sufficient but not necessary to ensure the embedding consistency preservation. In practice, it may be useful to relax the embedding consistency condition if several terms can have the same evaluation. For example, algebraic properties of user-defined functions on embeddings could be taken into account.

Applications

As presented in the introduction, the manipulation of geometric information is at the heart of geometric modelers. Rule schemes with embedding terms allow a major part of geometric operations to be defined, as this section will illustrate. After some basic rule scheme examples, a physical simulation application will be presented with its implementation in a dedicated software tool set. Many usual geometric operations can be specified by rule schemes, using embedding expressions and node variables. The most basic ones are simple modifications of one embedding (see Figure 41). Thanks to the topological extension (see section 7.2), matching one node is enough as the instantiation ensures that all nodes of the embedded orbit are relabeled. For example, Figure 41 But these embedding modifications can also be combined with topological transformations of a fixed pattern. For example, the rule scheme of Figure 42 allows one to sew two faces along free edges and to position the merged edge in the middle of the two previous edge positions. More generally, the introduced rule schemes can therefore address any modeling operation as long as this operation concerns the transformations of a fixed topological pattern. For example, we can easily define usual operations on regular mesh processing. The enlargement of a triangle in mesh can be defined by the rule scheme of Figure 43. This enlargement is carried out by translating every vertex position of the triangle by the vector computed with the vec user-operator between the two following positions: the triangle barycenter (bary(pos 0 1 (a)), see Subsection 6.2) and the vertex position itself (e.g. a.pos). Therefore, all vertex positions are translated in a way that put them farther from the triangle center.

We shall now take another example of triangular mesh processing, with the triangular flip-flap operation [START_REF] Paulus | Virtual Cutting of Deformable Objects based on Efficient Topological Operations[END_REF] in Figure 44. This operation is useful to transform two flat triangles into more equilateral ones, in order to increase the mesh shape regularity and therefore the quality of simulations. It should be noted that the rule scheme does not modify the vertex positions. However, as the vertex orbits incident to nodes a and k are extended with nodes m, n, o and p, the corresponding positions must be redefined at least once per extended vertex orbit (see the condition of labeling of extended embedding orbits of Theorem 4). A more elaborate example of mesh processing is the loop subdivision of Figure 45 [START_REF] Loop | Smooth subdivision surfaces based on triangles[END_REF]. As this subdivision consists in splitting the three edges of the triangle, the rule scheme has to match both the triangle and its three adjacent edges in order to preserve the topological coherence. On the embedding aspect, the positions of the new vertices are defined as the center of the split edges, while none of the three positions of the original face are modified. While this rule scheme allows the first triangle to be subdivided, it cannot be used to subdivide the neighbor face, as this face would then have four vertices as a result of the first subdivision. Consequently, a new rule scheme is necessary to subdivide this second face. However, to be correctly applied, this second rule scheme would require additional information (i.e. an additional embedding) to distinguish the three original vertices from the added one.

An application to physical simulation

In [START_REF] Ben Salah | A general physical-topological framework using rule-based language for physical simulation[END_REF], we proposed a physical simulator based on the mass/spring systems of [START_REF] Provot | Deformation constraints in a mass-spring model to describe rigid cloth behaviour[END_REF] in which all operations are defined with the introduced rule language. Figure 46( As any realistic modeling application, this simulator requires multiples embeddings. Each node must therefore carry the particle properties (its position pos, its mass m, and its cumulated force F ) and the stretching spring properties (its stiffness k and its rest-length l 0 ). In [START_REF] Bellet | Rule-based transformations for geometric modeling[END_REF], we addressed the case of multiple embeddings by introducing a category of partially I-labeled graphs that handle multiple node labels as an extension of the category defined in [START_REF] Habel | Relabelling in graph transformation[END_REF]. In this category, each type of embedding (node label) is defined by its own node labeling function, which is defined on its own orbit type. We extended graph transformations in this category so rules could simultaneously transform multiple embeddings. For example, the rule scheme of Figure 46(b) computes the forces corresponding to a given stretching spring (edge), by using a user-defined operator sprF on the two corresponding particle data (pos and m) and the spring properties (k and l 0 ). The final cumulated forces of particles are obtained when this rule scheme has been applied to all springs (all edges). To preserve the shape of faces, shear springs, as represented in Figure 47, are generally added. In case of initially rectangular faces (when diagonals have equal length) with an isotropic material, the two shear springs are equal and we can save only one set of parameters for the two springs associated to the face. Therefore, in the rule scheme of Figure 47(b), the computation of the forces corresponding to a pair of shear springs directly matches a whole face. In the other case (when the initial face is not regular), or when the material is anisotropic, two set of parameters are required and are associated with the two face corners (orbit 1 ). Consequently, in the rule scheme of Figure 47(c), the computing of a shear spring only matches half a face (i.e. two opposite corners at a time). Finally, linear bending springs can also be added to control bending. As represented in Figure 48(a), they connect second-neighbor vertices in order to control the angle between two edges, and therefore the corresponding rule scheme of Figure 48(b) matches three vertices. In this case, the chosen orbit to carry the string data are the orbits 2 as their number matches with the number of linear bending springs.

Jerboa and related applications

The presented language and the associated syntactic conditions are at the heart of Jerboa [START_REF] Bellet | Designing a topological modeler kernel: a rule-based approach[END_REF][START_REF] Belhaouari | JERBOA: A graph transformation library for topology-based geometric modeling[END_REF][START_REF] Jerboa | a rule-based topological modeler generator[END_REF], a tool set for designing and generating a safe geometric modeler kernel. As Jerboa aims at allowing the generation of any modeler, it addresses a large class of modeling operations.

Creating a modeler with Jerboa can basically be achieved in two steps:

• The first one consists in specifying the manipulated object by providing its topological dimension and embedding (which data type will be attached to which orbits). Note that the modeler designer has to provide any external library required to handle the embedding data types (e.g. 3D coordinate, RGB color) and their associated computational functions (e.g. barycenter of a set of points, mix of two colors).

• The second step is the design of rule schemes defining the modeling operations. The syntactic analyzer included in the graphic rule editor automatically checks the conditions given in this article and guides the user through modeling operations design by indicating which parts of the rule are inconsistent. Once designed, a modeler can be generated and used right away thanks to a default generic viewer provided by Jerboa. But this modeler kernel can also be integrated into larger tools. Most importantly, end-users are not required to understand the rule language: indeed, they will only use modeling operations by interactively applying them on the object under construction. Jerboa has been used to develop several geometric modelers, such as one geology modeling tool [START_REF] Gauthier | A topological approach for automated unstructured meshing of complex reservoir[END_REF], and the simulation using mass/spring model presented in section 9.2. The previously described rule schemes have been implemented in 2D (see Figure 49) and adapted in 3D (see Figure 50). They have been applied on several objects: with rectangular cells in Figure 49

Conclusion

In this article, we introduced a new kind of graph transformation variables, called node variables and inspired from the attribute variables of [START_REF] Hoffmann | Graph transformation with variables[END_REF], and dedicated to embedding computations in the context of topology-based geometric modeling. Benefiting from the regularity of G-map topological structures, these node variables are provided with operators that allow both to access the existing embedding (node labels in the transformed object), therefore avoiding any additional identifier naming for variable. Operators are also allow provided to traverse the topological structure (neighboring nodes in the transformed object) without having to match the precise configuration below the matched pattern (e.g. in the face triangulation case, a mix with the neighboring face colors can be defined wether these faces exist or not). A rule instantiation mechanism is also provided to propagate the embedding modifications to the concern orbits of the object. This mechanism allows to modify the labels of nodes located beyond the rule pattern without having to explicitly match all of them (e.g. in the edge removal case, the merged face color can be defined without having to match the whole structure, therefore allowing a generic definition of the operation limited to the edge). The resulting language is generic enough to define any usual embedding transformation, and it is fitted with syntactic conditions that allow an operation implemented as a rule to be statically checked. A single rule application engine may thus be programmed to handle any operation.

Our further work will consist in enhancing the language with new possibilities, while still providing a safe theoretical ground. In particular, we still have to show under which syntactic conditions node variables can be simultaneously used with the orbit variables dedicated to topological transformations in order to define operations independently from both embedding value and topological shape (e.g. the triangulation of any sized face of any color). Furthermore, we wish to provide rule scripts in order to compute complex modeling operations, as the boolean operators allowing to combine objects together by intersection, difference or union. Such operations require to search the object and selectively apply rules, following a given strategy. A script language would allow to define these strategies by providing operators such as iterators, loops or conditionals.

Figure 1 :

 1 Figure 1: An example of graph transformation expressiveness

Figure 2 :

 2 Figure 2: Two modeling operations

Figure 3 :

 3 Figure 3: Fractals in nature

Figure 4 :

 4 Figure 4: Plants modeling based on L-Systems

Figure 5 :

 5 Figure 5: Urban modeling based on L-Systems

Figure 6 :

 6 Figure 6: Our first study case: the Golgi apparatus

Figure 7 :

 7 Figure 7: DPO graph transformation

Figure 8 :

 8 Figure 8: A relabeling rule

Figure 9 :

 9 Figure 9: A diagram and a direct derivation

Figure 10 :

 10 Figure 10: A rule scheme with attribute variables

Figure 11 :

 11 Figure 11: Object inconsistencies

Figure 12 :

 12 Figure 12: Topological decomposition of a geometric 2D object

  o} and whose s , t , l V and α are restrictions of corresponding fonctions in G to the sets V or E .

  Figure 14: Completions Let us take two examples to illustrate the notion of completion. The topological graph of Figure 14(a) is the 1 2 -completion of 0 2 (e), i.e the vertex completion of the edge adjacent to node e. Symmetrically, the Figure 14(b) presents the 0 2 -completion of the vertex 1 2 (e).

Figure 15 :

 15 Figure 15: Non-respect of adjacent arcs condition

Figure 16 :

 16 Figure 16: Non-respect of cycle condition

Figure 17 :

 17 Figure 17: Two embedding operations

Figure 18 :

 18 Figure 18: Quotients of the embedded 2-G-maps given in Figure 17

Figure 19 :

 19 Figure 19: Two operations on the position embedding

Figure 20 :

 20 Figure 20: Incoherent translation

Figure 21 :

 21 Figure 21: Coherent translation

  ). (b) Both v and w have two antecedents v and w in R. Because of the adjacent arcs condition of Theorem 1, R has no i-arc neither with source v nor w . And thus R o (v ) and R o (w ) are not full orbits. Because of the condition of full match of transformed embeddings, v and w are preserved nodes with preserved π-labels, i.e. π L (v ) = π R (v ) and π L (w ) = π R (w ). Thus v and w have the same defined π-label in G and H, i.e. π G (v) = π H (v) and π G (w) = π H (w).

  (a) Both v and w have defined π-labels in R, i.e. π R (v ) = ⊥ and π R (w ) = ⊥. Thanks to the embedding consistency condition, v and w have the same defined π-label, π R (v ) = π R (w ) and therefore π H (v) = π H (w). (b) Both v and w have undefined π-labels in R, i.e. π R (v ) = ⊥ and π R (w ) = ⊥. Thanks to the rule definition (see Definition 1), v and w are nodes of K and thus of L, with π L (v ) = ⊥ and π L (w ) = ⊥. Then v and w also come from G, but not necessarily from the same o -orbit. i. v and w do not come from the same o -orbit, i.e. v ≡ L o w . Thanks to the condition of labeling of extended embedding orbits, there exists x ∈ K with x ≡ L o v and x ≡ R o v such that π L (x ) = ⊥ and therefore π R (x ) = ⊥. Symmetrically, there exists y ∈ K with y ≡ L o v and y ≡ R o v such that π L (y ) = ⊥ and therefore π R (y ) = ⊥. Moreover, as x ≡ R o y , the embedding consistency condition ensures that π R (x ) = π R (y ). Thanks to the condition of full match of transformed embeddings, x and y have their π-label preserved by the rule as their o -orbit in R is not totally labeled, and therefore π L (x ) = π L (y ) (both defined). As v ≡ L o x and w ≡ L o y , we have v ≡ G o x and v ≡ G o y with x and y the respective images of x and y in G. Then because G is a π-embedded G-map, π G (v) = π G (x) and π G (w) = π G (y) and therefore π H (v) = π H (w). ii. v and w come from the same o -orbits, i.e. v ≡ L o w . Then v ≡ G o w and because G is a π-embedded G-map, π G (v) = π G (w) and then π H (v) = π H (w).

Figure 22 :

 22 Figure 22: Two non-consistent rules that break conditions of Theorem 2

Figure 23 :

 23 Figure 23: Application of the edge folding

Figure 24 :

 24 Figure 24: Rule schemes of the operations of Figure 19

  (b), i.pos and k.pos are the two positions associated to the matched edge and center(i.pos, k.pos) defines the corresponding center.

Figure 25 :

 25 Figure 25: Face triangulations on the color embedding

Figure 26 :

 26 Figure 26: Face triangulations of Figure 25 on a col-embedded G-map

Figure 27 :

 27 Figure 27: Face triangulation on a pos-embedded G-map

Figure 28 :

 28 Figure 28: Evaluation of the multiset of the face positions

Figure 29 :

 29 Figure 29: Two evaluations of the rule scheme Figure 26

Figure 30 :

 30 Figure 30: Expected rule scheme of the translation

Figure 31 :

 31 Figure 31: Edge removal on the color embedding

Figure 33 :

 33 Figure 33: Construction of the topological extension

Figure 34 :

 34 Figure 34: Quotients for the embedding propagation

Figure 35 :

 35 Figure 35: Inconsistent edge removal

Figure 36 :

 36 Figure 36: Rule scheme application

Figure 37 :

 37 Figure 37: Edge removal between two faces of same color

Figure 38 :Figure 39 :

 3839 Figure 38: Face stretching rule scheme

Figure 40 :

 40 Figure 40: Inconsistent face streching

Figure 41 :

 41 Figure 41: To modify one embedding

Figure 42 :

 42 Figure 42: Edge sewing

2 sFigure 43 :

 243 Figure 43: Triangle enlargement

Figure 44 :

 44 Figure 44: Triangular flip-flap

  s = center(a. pos, c. pos) t = center(b. pos, d. pos) u = center(e. pos, f. pos)

Figure 45 :

 45 Figure 45: Loop subdivison

  a) presents a first intuitive representation of this model: vertices represent particles and stretching springs are associated to edges.

Figure 46 :

 46 Figure 46: Stretch springs

  . F+ sprF(a.pos,a.m,e.pos,e.m,a.k,a.l 0 ) x = c. F + sprF(c.pos,c.m,g.pos,g.m,a.k,a.l 0 ) y = e. F + sprF(e.pos,e.m,a.pos,a.m,a.k,a.l 0 ) z = g. F + sprF(g.pos,g.m,c.pos,c.m,a.k,a.l 0 ) . F+ sprF(a.pos,a.m,d.pos,d.m,b.k,b.l 0 ) v = d. F + sprF(d.pos,d.m,a.pos,a.m,b.k,b.l 0 )

Figure 47 :

 47 Figure 47: Shear springs

  s = a. F t = f. F u = a. F+ sprF(a.pos,a.m,f.pos,f.m,c.k,c.l 0 ) v = d. F + sprF(f.pos,f.m,a.pos,a.m,c.k,c.l 0 )

Figure 48 :

 48 Figure 48: Bending springs

Figure 49 :

 49 Figure 49: Mass/spring simulation in 2D.

  (a), with triangular cells in Figure 49(b), with mixed ones in Figure 49(c), on cuboids with 64 elements in Figure 50(a), and on a liver model with 597 elements in Figure 50(b). Simulation of more complex objects is possible and the degree of accuracy of the results is equivalent to other approaches.

Figure 50 :

 50 Figure 50: Mass/spring simulation in 3D.

http://www.speedtree.com/

One can generally consider standard graph morphisms instead of only considering inclusions.

Labels of nodes or arcs are either variables of X or expressions built over variables of X.

Undirected graphs, also called symmetric graphs, are such that for each arc of source n and of target n , there exists a symmetric arc, of source n and of target n.

To be in agreement with the community of geometric modeling, we chose the term "embedded" rather than the term "attributed", most commonly used in the graph transformation community.

Let X be a set and ≡ an equivalent relation on X, the equivalence class [x] of any element x ∈ X is defined as [x] = {y ∈ X | x ≡ y}, and the quotient set X /≡ is the set {[x] | x ∈ X}.

Cases are hierarchically numbered to ease proof commentary.

Note that terms are detailed on top of the rules for readability purposes.

In accordance with Definition 1, rule nodes must be labeled in L in order to relabel them.

We write π (v ) | v ∈ V the multiset of type τ • such that for all x : τ , the multiplicity of x is equal to the number of node of V labeled by x.