Hostname: page-component-5c6d5d7d68-pkt8n Total loading time: 0 Render date: 2024-08-22T20:50:08.504Z Has data issue: false hasContentIssue false
  • English
  • Français

Preserving consistency in geometric modeling with graph transformations

Published online by Cambridge University Press:  18 October 2022

Agnès Arnould ,
Hakim Belhaouari ,
Thomas Bellet ,
Pascale Le Gall  and
Romain Pascual Open the ORCID record for Romain Pascual [Opens in a new window]
Agnès Arnould
Affiliation:
Laboratory XLIM UMR CNRS 7252, Poitiers University, Poitiers, France
Hakim Belhaouari
Affiliation:
Laboratory XLIM UMR CNRS 7252, Poitiers University, Poitiers, France
Thomas Bellet
Affiliation:
Laboratory MICS, CentraleSupélec, Paris-Saclay University, Gif-sur-Yvette, France
Pascale Le Gall
Affiliation:
Laboratory MICS, CentraleSupélec, Paris-Saclay University, Gif-sur-Yvette, France
Romain Pascual*
Affiliation:
Laboratory MICS, CentraleSupélec, Paris-Saclay University, Gif-sur-Yvette, France
*
*Corresponding author. Email: [email protected]
Get access Rights & Permissions [Opens in a new window]

Abstract

Labeled graphs are particularly well adapted to represent objects in the context of topology-based geometric modeling. Thus, graph transformation theory is used to implement modeling operations and check their consistency. This article defines a class of graph transformation rules dedicated to embedding computations. Objects are here defined as a particular subclass of labeled graphs in which arc labels encode their topological structure (i.e., cell subdivision: vertex, edge, face) and node labels encode their embedding (i.e., relevant data: vertex positions, face colors, volume density). Object consistency is defined by labeling constraints which must be preserved by modeling operations that modify topology and/or embedding. Dedicated graph transformation variables allow us to access the existing embedding from the underlying topological structure (e.g., collecting all the points of a face) in order to compute the new embedding using user-provided functions (e.g., compute the barycenter of several points). To ensure the safety of the defined operations, we provide syntactic conditions on rules that preserve the object consistency constraints.

Keywords

DPO graph transformationtopology-based geometric modelinggraph transformation with variablesgeneralized mapsconsistency preservationstatic analysis
Type
Paper
Information
Mathematical Structures in Computer Science , Volume 32 , Issue 3 , March 2022 , pp. 300 - 347
Check for updates
Copyright
© The Author(s), 2022. Published by Cambridge University Press

Access options

Get access to the full version of this content by using one of the access options below. (Log in options will check for institutional or personal access. Content may require purchase if you do not have access.)

References

Arnould, A., Belhaouari, H., Bellet, T., Le Gall, P. and Poudret, M. (2019). Jerboa. http://xlim-sic.labo.univ-poitiers.fr/jerboa/.Google Scholar
Baader, F. and Nipkow, T. (1999). Equational unification. In: Term Rewriting and All that, chapter 10, Cambridge University Press, 223–234.Google Scholar
Baresi, L. and Heckel, R. (2004). Tutorial introduction to graph transformation: A software engineering perspective. In: Ehrig, H., Engels, G., Parisi-Presicce, F. and Rozenberg, G. (eds.) Graph Transformations (ICGT 2004), Lecture Notes in Computer Science, vol. 3256, Berlin, Heidelberg, Springer, 431–433.CrossRefGoogle Scholar
Belhaouari, H., Arnould, A., Le Gall, P. and Bellet, T. (2014). Jerboa: A graph transformation library for topology-based geometric modeling. In: Giese, H. and König, B. (eds.) Graph Transformation (ICGT 2014), Lecture Notes in Computer Science, vol. 8571, Cham, Springer International Publishing, 269–284.Google Scholar
Belhaouari, H. and Horna, S. (2019). Reconstruction of volumes from soup of faces with a formal topological approach. Computer-Aided Design and Applications 16 (5) 6.Google Scholar
Bellet, T., Arnould, A., Belhaouari, H. and Le Gall, P. (2017). Geometric modeling: Consistency preservation using two-layered variable substitutions. In: de Lara, J. and Plump, D. (eds.) Graph Transformation (ICGT 2017), Lecture Notes in Computer Science, vol. 10373, Cham, Springer, 36–53.Google Scholar
Bellet, T., Arnould, A. and Le Gall, P. (2011). Rule-based transformations for geometric modeling. In: 6th International Workshop on Computing with Terms and Graphs (TERMGRAPH 2011), Part of ETAPS 2011, vol. 48, Saarbrücken, Germany, 20–37.Google Scholar
Bellet, T., Poudret, M., Arnould, A., Fuchs, L. and Le Gall, P. (2010). Designing a topological modeler kernel: A rule-based approach. In: Shape Modeling International Conference (SMI), IEEE, 100–112.CrossRefGoogle Scholar
Ben Salah, F., Belhaouari, H., Arnould, A. and Meseure, P. (2017). A general physical-topological framework using rule-based language for physical simulation. In: Proceedings of the 12th International Conference on Computer Graphics Theory and Application (VISIGRAPP/GRAPP 2017), VISIGRAPP 2017 Proceedings, vol. GRAPP, Porto, Portugal, SciTePress, 220–227.Google Scholar
Bohl, E., Terraz, O. and Ghazanfarpour, D. (2015). Modeling fruits and their internal structure using parametric 3Gmap L-systems. Visual Computer 31 (6–8) 819–829.CrossRefGoogle Scholar
Bunke, H. 1982. Attributed programmed graph grammars and their application to schematic diagram interpretation. IEEE Transactions on Pattern Analysis and Machine Intelligence 4 (6) 574–582.CrossRefGoogle ScholarPubMed
Cardot, A., Marcheix, D., Skapin, X., Arnould, A. and Belhaouari, H. (2019). Persistent naming based on graph transformation rules to reevaluate parametric specification. Computer-Aided Design and Applications 16 (5) 985–1002.CrossRefGoogle Scholar
Corradini, A., Montanari, U., Rossi, F., Ehrig, H., Heckel, R. and Löwe, M. 1997. Algebraic approaches to graph transformation, part I: Basic concepts and double pushout approach. In: Rozenberg, G. (ed.), Handbook of Graph Grammars and Computing by Graph Transformation, World Scientific, 163–245.Google Scholar
Damiand, G. and Lienhardt, P. (2014). Combinatorial Maps: Efficient Data Structures for Computer Graphics and Image Processing, New York, A. K. Peters, Ltd./CRC Press.CrossRefGoogle Scholar
Dijkstra, E. W. (1976). A Discipline of Programming, Englewood Cliffs, New Jersey, Prentice-Hall.Google Scholar
Drewes, F., Hoffmann, B., Janssens, D. and Minas, M. (2010). Adaptive star grammars and their languages. Theoretical Computer Science 411 (34–36) 3090–3109.CrossRefGoogle Scholar
Drewes, F., Kreowski, H.-J. and Habel, A. (1997). Hyperedge replacement graph grammars. In: Rozenberg, G. (ed.), Handbook Of Graph Grammars And Computing By Graph Transformation: Volume 1: Foundations, World Scientific, 95–162.Google Scholar
Ebert, J. and Horn, T. (2014). GReTL: An extensible, operational, graph-based transformation language. Software and Systems Modeling 13 (1) 301–321.Google Scholar
Ehrig, H., Ehrig, K., Prange, U. and Taentzer, G. (2006). Fundamentals of Algebraic Graph Transformation, Monographs in Theoretical Computer Science. An EATCS Series, Berlin Heidelberg, Springer-Verlag.Google Scholar
Ehrig, H., Kreowski, H.-J., Montanari, U. and Rozenberg, G. (1999). Handbook of Graph Grammars and Computing by Graph Transformation: Concurrency, Parallelism, and Distribution, Concurrency, Parallelism, and Distribution, vol. 3, Singapore, World Scientific.Google Scholar
Engelfriet, J. and Rozenberg, G. (1997). Node replacement graph grammars. In: Rozenberg, G. (ed.), Handbook Of Graph Grammars And Computing By Graph Transformation: Volume 1: Foundations, World Scientific, 1–94.Google Scholar
Gauthier, V., Arnould, A., Belhaouari, H., Horna, S., Perrin, M., Poudret, M. and Rainaud, J.-F. (2016). A topological approach for automated unstructured meshing of complex reservoir. In: ECMOR XV-15th European Conference on the Mathematics of Oil Recovery, European Association of Geoscientists & Engineers, cp–494.Google Scholar
Geiß, R., Batz, G. V., Grund, D., Hack, S. and Szalkowski, A. (2006). GrGen: A fast SPO-based graph rewriting tool. In: Corradini, A., Ehrig, H., Montanari, U., Ribeiro, L. and Rozenberg, G. (eds.) Graph Transformations (ICGT 2006), Lecture Notes in Computer Science, vol. 4178, Berlin, Heidelberg, Springer, 383–397.Google Scholar
Gyssens, M., Paredaens, J., van den Bussche, J. and van Gucht, D. (1994). A graph-oriented object database model. IEEE Transactions on Knowledge and Data Engineering 6 (4) 572–586.CrossRefGoogle Scholar
Habel, A. (1992). Hyperedge Replacement: Grammars and Languages , Lecture Notes in Computer Science, vol. 643, Berlin, Heidelberg, Springer.Google Scholar
Habel, A. and Pennemann, K.-H. (2009). Correctness of high-level transformation systems relative to nested conditions. Mathematical Structures in Computer Science 19 (2) 245–296.Google Scholar
Habel, A. and Plump, D. (2001). Computational completeness of programming languages based on graph transformation. In: Honsell, F. and Miculan, M. (eds.) Foundations of Software Science and Computation Structures, Lecture Notes in Computer Science, Berlin, Heidelberg, Springer, 230–245.Google Scholar
Habel, A. and Plump, D. (2002). Relabelling in graph transformation. In: Corradini, A., Ehrig, H., Kreowski, H.-J. and Rozenberg, G. (eds.) Graph Transformation (ICGT 2002), Lecture Notes in Computer Science, vol. 2505, Berlin, Heidelberg, Springer, 135–147.Google Scholar
Haeusler, M., Trojer, T., Kessler, J., Farwick, M., Nowakowski, E. and Breu, R. (2019). ChronoSphere: A graph-based EMF model repository for IT landscape models. Software and Systems Modeling 18 (6) 3487–3526.CrossRefGoogle ScholarPubMed
Han, F. and Zhu, S.-C. (2005). Bottom-up/top-down image parsing by attribute graph grammar. In: Tenth IEEE International Conference on Computer Vision (ICCV’05) Volume 1, vol. 2, IEEE, 1778–1785.Google Scholar
Heckel, R. and Taentzer, G. (2020). Graph Transformation for Software Engineers: With Applications to Model-Based Development and Domain-Specific Language Engineering, Cham, Springer International Publishing.CrossRefGoogle Scholar
Hoare, C. A. R. (1969). An axiomatic basis for computer programming. Communications of the ACM 12 (10) 576–580, 583.CrossRefGoogle Scholar
Hoffmann, B. (2005). Graph transformation with variables. In: Kreowski, H.-J., Montanari, U., Orejas, F., Rozenberg, G. and Taentzer, G. (eds.) Formal Methods in Software and Systems Modeling: Essays Dedicated to Hartmut Ehrig on the Occasion of His 60th Birthday, Lecture Notes in Computer Science, Berlin, Heidelberg, Springer, 101–115.Google Scholar
Ikehata, S., Yang, H. and Furukawa, Y. (2015). Structured indoor modeling. In: Proceedings of the IEEE International Conference on Computer Vision (ICCV), USA, IEEE Computer Society, 1323–1331.CrossRefGoogle Scholar
Lang, V. and Lienhardt, P. (1996). Simplicial sets and triangular patches. In: Proceedings of the 1996 Conference on Computer Graphics International. IEEE, 154–163.CrossRefGoogle Scholar
Ledoux, F., Arnould, A., Le Gall, P. and Bertrand, Y. 2002. Geometric modelling with CASL. In: Cerioli, M. and Reggio, G. (eds.) Recent Trends in Algebraic Development Techniques, Lecture Notes in Computer Science, vol. 2267, Berlin, Heidelberg, Springer, 176–201.Google Scholar
Li, W., Agrawala, M., Curless, B. and Salesin, D. (2008). Automated generation of interactive 3D exploded view diagrams. ACM Transactions on Graphics 27 (3) 1–7.CrossRefGoogle Scholar
Lienhardt, P. (1994). N-dimensional generalized combinatorial maps and cellular quasi-manifolds. International Journal of Computational Geometry & Applications 04 (03) 275–324. Publisher: World Scientific Publishing Co.CrossRefGoogle Scholar
Mäntylä, M. (1988). Introduction to Solid Modeling, USA, W. H. Freeman & Co.Google Scholar
Minas, M. and Viehstaedt, G. (1995). DiaGen: A generator for diagram editors providing direct manipulation and execution of diagrams. In: Proceedings of Symposium on Visual Languages, IEEE, 203–210.Google Scholar
Mohammad, R. and Kroll, E. (1993). Automatic generation of exploded view by graph transformation. In: Proceedings of 9th IEEE Conference on Artificial Intelligence for Applications, 368–374.Google Scholar
Müller, P., Wonka, P., Haegler, S., Ulmer, A. and Van Gool, L. (2006). Procedural modeling of buildings. In: ACM SIGGRAPH 2006 Papers, SIGGRAPH’06, New York, NY, USA, Association for Computing Machinery, 614–623.CrossRefGoogle Scholar
Nickel, U., Niere, J. and Zündorf, A. (2000). The FUJABA environment. In: Proceedings of the 22nd International Conference on Software Engineering, ICSE’00, New York, NY, USA, Association for Computing Machinery, 742–745.Google Scholar
Ong, Y. and Kurth, W. (2012). A graph model and grammar for multi-scale modelling using XL. In: 2012 IEEE International Conference on Bioinformatics and Biomedicine Workshops, IEEE, 1–8.CrossRefGoogle Scholar
Parish, Y. I. H. and Müller, P. (2001). Procedural modeling of cities. In: Proceedings of the 28th Annual Conference on Computer Graphics and Interactive techniques, SIGGRAPH’01, New York, NY, USA, Association for Computing Machinery, 301–308.Google Scholar
Pascual, R., Le Gall, P., Arnould, A. and Belhaouari, H. (2022). Topological consistency preservation with graph transformation schemes. Science of Computer Programming 214 102728.CrossRefGoogle Scholar
Plump, D. (2009). The graph programming language GP. In: Bozapalidis, S. and Rahonis, G. (eds.) Algebraic Informatics, Lecture Notes in Computer Science, vol. 5725, Springer, 99–122.Google Scholar
Plump, D. and Steinert, S. (2004). Towards graph programs for graph algorithms. In: Ehrig, H., Engels, G., Parisi-Presicce, F. and Rozenberg, G. (eds.) Graph Transformations (ICGT 2004), Lecture Notes in Computer Science, vol. 3256, Berlin, Heidelberg, Springer, 128–143.Google Scholar
Poskitt, C. M. and Plump, D. (2012). Hoare-style verification of graph programs. Fundamenta Informaticae 118 (1–2) 135–175.Google Scholar
Poudret, M., Arnould, A., Comet, J.-P. and Le Gall, P. (2008). Graph transformation for topology modelling. In: Ehrig, H., Heckel, R., Rozenberg, G. and Taentzer, G. (eds.) Graph Transformations (ICGT 2008), Lecture Notes in Computer Science, vol. 5214, Berlin, Heidelberg, Springer, 147–161.Google Scholar
Prusinkiewicz, P., Lindenmayer, A. and Hanan, J. (1988). Development models of herbaceous plants for computer imagery purposes. In: Proceedings of the 15th Annual Conference on Computer graphics and Interactive Techniques, SIGGRAPH’88, vol. 22, New York, NY, USA, Association for Computing Machinery, 141–150.CrossRefGoogle Scholar
Puitg, F. and Dufourd, J.-F. (1998). Formal specification and theorem proving breakthroughs in geometric modeling. In: Grundy, J. and Newey, M. (eds.) Theorem Proving in Higher Order Logics, Lecture Notes in Computer Science, Berlin, Heidelberg, Springer, 401–422.Google Scholar
Rensink, A. (2004). The GROOVE simulator: A tool for state space generation. In: Pfaltz, J. L., Nagl, M. and Böhlen, B. (eds.) Applications of Graph Transformations with Industrial Relevance, Lecture Notes in Computer Science, Berlin, Heidelberg, Springer, 479–485.Google Scholar
Rodriguez, M. A. (2015). The Gremlin graph traversal machine and language (invited talk). In: Proceedings of the 15th Symposium on Database Programming Languages, DBPL 2015, New York, NY, USA, Association for Computing Machinery, 1–10.CrossRefGoogle Scholar
Schürr, A., Winter, A. J. and Zündorf, A. (1995). Graph grammar engineering with PROGRES. In: Schäfer, W. and Botella, P. (eds.) Software Engineering – ESEC’95, Lecture Notes in Computer Science, Berlin, Heidelberg, Springer, 219–234.Google Scholar
Smelik, R. M., De Kraker, K. J., Tutenel, T., Bidarra, R. and Groenewegen, S. A. (2009). A survey of procedural methods for terrain modelling. In: Proceedings of the CASA Workshop on 3D Advanced Media In Gaming And Simulation (3AMIGAS), 25–34.Google Scholar
Smith, C., Prusinkiewicz, P. and Samavati, F. (2004). Local specification of surface subdivision algorithms. In: Pfaltz, J. L., Nagl, M. and Böhlen, B. (eds.) Applications of Graph Transformations with Industrial Relevance (AGTIVE 2003), Lecture Notes in Computer Science, vol. 3062, Berlin, Heidelberg, Springer, 313–327.Google Scholar
Spicher, A., Michel, O. and Giavitto, J.-L. (2010). Declarative mesh subdivision using topological rewriting in MGS. In: Ehrig, H., Rensink, A., Rozenberg, G. and Schürr, A. (eds.) Graph Transformations, Lecture Notes in Computer Science, Berlin, Heidelberg, Springer, 298–313.Google Scholar
Taentzer, G. (2004). AGG: A graph transformation environment for modeling and validation of software. In: Pfaltz, J. L., Nagl, M. and Böhlen, B. (eds.) Applications of Graph Transformations with Industrial Relevance, Lecture Notes in Computer Science, vol. 3062, Berlin, Heidelberg, Springer, 446–453.Google Scholar
Tsai, W.-H. and Fu, K.-S. (1980). Attributed grammar-A tool for combining syntactic and statistical approaches to pattern recognition. IEEE Transactions on Systems, Man, and Cybernetics 10 (12) 873–885.CrossRefGoogle Scholar
Vilgertshofer, S. and Borrmann, A. (2017). Using graph rewriting methods for the semi-automatic generation of parametric infrastructure models. Advanced Engineering Informatics 33 502–515.CrossRefGoogle Scholar
Weiler, K. (1988). The radial-edge structure: A topological representation for non-manifold geometric boundary representations. In: Geometric Modeling for CAD Applications: Selected Papers from IFIP WG 5.2, 3–36.Google Scholar
You, K. C. and Fu, K.-S. (1979). A syntactic approach to shape recognition using attributed grammars. IEEE Transactions on Systems, Man, and Cybernetics 9 (6) 334–345.CrossRefGoogle Scholar