Combinatorial maps: transformations and application to geometric modeling

Abstract : In the first part of the talk, I will present generalized maps that represent quasi-manifolds through their subdivision into topological cells (vertices,edges, faces, volumes). We defined generalized maps as constrained labeled graphs. Arc labels encode topological relations of the subparts of the modeled object, while node labels describe the geometric data used to represent the object. Modeling operations are designed regardless of the object’s underlying topology. Therefore, we generalize DPO rules with a functorial approach to encode semi-global relabeling with a product operation. Rules and their extensions (called rule schemes) are considered valid if any application to a well-formed graph results in an equally well-formed graph. We provide set-theoric conditions on rules and rule schemes to ensure the preservation of the model consistency. In the second part of the talk, I will present how this approach allows the design of geometric modelers (software used to create and edit geometric objects) in Jerboa. The set-theoric conditions can be checked via graph traversal in Jerboa’s rule editor to ensure that the code derived from the rule will never break the model. The generated code can be used as an add-on in other software or Jerboa’s generic viewer.

Tool presentation by Hakim Belhaouari (Laboratoire XLIM UMR CNRS 7252, Université de Poitiers).

Romain Pascual
Romain Pascual

My research interests include applications of graph rewriting to computer graphics, and more generally formal methods from theory to applications.