The topological model of generalized maps

Jerboa uses the topological model of generalized maps (or G-maps) [10] because its mathematical definition can be easily encoded within a formal framework. In G-maps, the topological structure is handled by both the graph structure with the arc labels, while the embedding is defined by the node labels.

G-map decomposition


G-maps intuitively come from object decomposition into topological cells. The 2D object of Fig. 1 is first decomposed into faces in Fig. 2 connected along their common edge with a 2-relation and provided with 2-loops on border edges. Similarly, faces are split into edges connected with the 1-relation of Fig. 3. At last, edges are split into vertices by the 0-relation to obtain the 2-G-map of Fig. 4. Nodes obtained at the end of the process are the G-map darts and the different i-relations are labeled arcs: for an n-dimensional G-map, i belongs to [0, n]. At last, the multiple embedding informations such as vertex points and face colors are encoded by multiple node labels [4] in Fig. 5.



Topological cells of G-maps are defined by subgraphs called orbits and built from an originating node v and a set of labels o. The orbit ⟨o⟩(v) (of type ⟨o⟩ adjacent to v) is the subgraph which contains v, the nodes reachable from node v using arcs labeled on o, and the arcs themselves. For example, the vertex adjacent to e is the orbit ⟨1 2⟩(e) of Fig. 6, the ajacent edge is the orbit ⟨0 2⟩(e) of Fig. 7, and the ajacent face is the orbit ⟨0 1⟩(e) of Fig. 8. Note that by construction, embedding informations (points or colors) are shared by all nodes belonging to orbits associated to the considered embedding. For example, all nodes of the vertex of Fig. 6 are labeled with the point B, and all nodes of the face of Fig. 8 are labeled with the blue color. Note that orbits are not limited to cells and any subset [0,n] can define a valid orbit of a n-G-map. For instance, the orbit ⟨0⟩(e) of Fig. 9 defines the half-edge ajacent to e.


Formal rule languages have already been used for twenty years in the context of geometric modeling. In particular, L-systems [13] introduced by the biologist Aristid Lindenmayer to model plant growth have been developed for many procedural applications. In particular, they have already been used with G-maps to model leaf growth [14], flowers [15], or the internal structure of fruits [16]. But L-systems and similar grammars are defined by a limited set of high level operations which make them difficult to adapt.

Conversely, graph transformation approach offers a very natural way to describe complex transformations at low level [12]. Moreover, to meet the various application needs for abstraction, they 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. Variable types have various purposes [11]. For example, attribute variables allow label computations or labeling constraints, while graph variables and hyperedge variables allow structural transformations.

Taking inspiration from attribute and graph variables [11], Jerboa rules use two types of dedicated variables. First, the expressions in ⟨⟩ labeling nodes abstract topological rewritings of a matched orbit. For exemple, in the triangulation rule, a face orbit ⟨0 1⟩ is matched in the left-hand side (node n0). In the right hand-side, two copies of that orbit are made (n1 and n2) and all nodes are topologicaly rewritten differently to achieve the triangulation. For example, n0 is rewritten by ⟨0 _⟩ to delete the 1-arcs between the original face arcs. Similarly, n2 is rewritten by ⟨1 2⟩ (i.e. 0-arcs are relabeled into 1-arcs and 1-arcs are relabeled into 2-arcs) to create the dual vertex of the face. Secondly, the embedding terms labelling the bottom of nodes abstract the new embedding computations. For example, in the triangulation rule, two terms (that are not fully developped in the figure) respectivelly compute the new point (the face center) and the new colors (the mix with neighboring face colors).

Therefore, the Jerboa rule for face triangulation abstracts both rule instances, depending on whether a triangle or a square are matched.


Our publications

[1] Constraint-preserving labeled graph transformation for topology-based geometric modeling. T. Bellet, A. Arnould, P. Le Gall. Under submission, 2016.Pdf

[2] A Topological Approach for Automated Unstructured Meshing of Complex Reservoir. V. Gauthier, A. Arnould, H. Belhaouari, S. Horna, M. Perrin, M. Poudret, J.F. Rainaud. European Conference on the Mathematics of Oil Recovery (ECMOR), 2016.Pdf

[3] Jerboa: A Graph Transformation Library for Topology-Based Geometric Modeling. H. Belhaouari, A. Arnould, P. Le Gall, T. Bellet. International Conference on Graph Transformation (ICGT), 2014.Pdf

[4] Rule-based transformations for geometric modelling. T. Bellet, A. Arnould, P. Le Gall. TERMGRAPH, 2011.Pdf

[5] Designing a topological modeler kernel: a rule-based approach. T. Bellet, M. Poudret, A. Arnould, L. Fuchs, P. Le Gall. Shape Modeling International Conference (SMI), 2010.Pdf

[6] Graph transformation for topology modelling. M Poudret, A Arnould, JP Comet, P Le Gall. International Conference on Graph Transformation (ICGT), 2008.Pdf

[7] Topology-based Geometric Modelling for Biological Cellular Processes. M Poudret, JP Comet, P Le Gall, A. Arnould, P. Meseure. International Conference on Language and Automata Theory and Applications (LATA), 2007.Pdf

[8] Modélisation et Animation à base de règles pour la simulation physique. Ben Salah, F., Belhaouari, Arnould, A., Meseure, P. Groupe de Travail en Modélisation Géométrique (GTMG), 2015.Pdf

[9] Évaluation de la modélisation à base de transformation de graphes avec Jerboa. Gauthier, V., Belhaouari, H., Arnould, A. Journées de l'Association Française d'Informatique Graphique (AFIG), 2015.Pdf

Other publications

[10] N-dimensional generalized combinatorial maps and cellular quasi-manifolds. P. Lienhardt. International Journal of Computational Geometry & Applications, 1994.

[11] Graph Transformation with Variables. B. Hoffmann. Formal Methods in Software and Systems Modeling, 2005.

[12] Fundamentals of Algebraic Graph Transformation. H. Ehrig, K. Ehrig, U. Prange, G. Taentzer. Monographs in Theoretical Computer Science, 2006.

[13] The algorithmic beauty of plants. P. Prusinkiewicz, A. Lindenmayer. The Virtual Laboratory, 1991.

[14] Generating vast varieties of realistic leaves with parametric 2-G-map L-systems. A. Peyrat, O. Terraz, S. Merillou, E. Galin. The visual Computer, 2004.

[15] Flower modelling using natural interface and 3-G-map L-systems. O. Petrenko, R. J. G. Hernandez, M. Sbert, O. Terraz, D. Ghazanfarpour. International Conference on Virtual Reality Continuum and Its Applications in Industry (VRCAI), 2013.

[16] Modeling fruits and their internal structure using parametric 3-G-map L-systems. E. Bohl, O. Terraz, D. Ghazanfarpour. The Visual Computer, 2015.

[17] Procedural modeling of buildings. P. Müller, P. Wonka, S. Haegler, A. Ulmer, L. Van Gool. SIGGRAPH, 2006.