Context and overall objectives of the project

Digital geometry processing is an important research field which has been extensively developed for more than forty years. It deals with the definition and implementations of models and operations for describing and handling geometrical objects. The results of this field of research are used as basic tools for many applications in different domains. Indeed, computers have become increasingly powerful and are now capable of handling detailed representations of complex objects. In addition, powerful tools have recently been developed that are able to scan real objects in order to reconstruct the corresponding electronic descriptions. For these reasons, real objects can now be described in computers with a very high level of precision, and we can use these precise descriptions to perform analysis and processing tasks on the corresponding objects. These algorithms can be used to improve the works of experts, either by replacing very long manual processes, or by giving more precise results.

For all of these reasons, digital object representations are used in many different domains of application, such as for example in medical imaging, surgery planning, computer aided design, architecture, geology, biology, material analysis, animation, simulation, geographic information systems.

One main challenge for digital geometry processing is the elaboration of geometrical models to describe digital objects and to propose algorithms that use these models to compute information and to handle the objects represented.

Useful abstractions of human anatomies, geological structures, man-made electromechanical parts, architectural models, etc. include a partition of space into full-dimensional chunks, surfaces that may separate such as chunks or define cracks, membranes, or sheets, wires, etc. and isolated points. Hence, we must develop representations that are well suited to capturing these arrangements and to querying and traversing them efficiently. Moreover, the constantly increasing complexity of the arrangements requires the representations to be highly compact, so as to minimize memory thrashing.

Furthermore, due to the considerable diversity of all the different domains of application, the needs are very varied as each application has its own specificity:

specific dimension: 2D models are of course mainly used in image analysis/processing. 3D models are used in medical imagery, CAD, geology, etc. However, recently new works have been published on higher dimension: 4D for example to describe a 3D animated object, the additional dimension being time, or higher dimensional objects by adding some feature spaces, for example in geographic information systems;
specific objects to represent: regular when all the cells have the same type (for example only triangles or only hexahedra) versus non-regular (different type of cells); manifold (when each point has a neighborhood equivalent to a ball) versus non-manifold (different types of neighborhood);
specific relations between objects: two objects can touch several times (multi-incidence) or not; two objects can be adjacent only along one of their faces (quasi-manifold) or along any cell in their boundary.

In this framework, our overall research goal in this project is to design the next generation technologies for modeling the full complexity of living and designed structures. In order to do this, we plan to define a generic purpose representation for geometric structures of arbitrary topology and different high level powerful operations capable of building and modifying this representation. In addition, we want to develop libraries and software implementing our solutions to serve as a basis for future software development in computer graphics.

The representation must be:

efficient: compact in memory space, fast of access and modification, easily modifiable;
powerful: capable of representing complex and inhomogeneous structures;
scalable: support multi-resolution processing and streaming, usable to represent complex geometric structures.

The operations must allow handling of the objects described by our representation. As examples, we can cite basic creations of atomic elements (polygons, polyhedra, grids, etc.); traversal of cells; cell modifications such as identification, split, merge; remeshing; simplification, etc. These operations are the classical ones that serve as a basis, for example in CAD software or in mesh processing algorithms, but generalized here in any dimension and acting on our specific new representation. Our goal in this project, which is also the main originality and innovative aspects of our project, is to propose a solution that fulfills all the requirements (efficient, powerful and scalable) allowing powerful operations to build and modify the described objects.

Main results achieved

During the first year of the project, Guillaume Damiand and Jarek Rossignac worked together on the definition of a new model allowing to describe 2D planar objects in a compact and a streamable way. By reading the most advanced and recent state of the art work, we were really interested by models based on pixels and voxels representation. Indeed such solutions have as main advantages to provide a natural spatial indexing of objects to describe; and it is often simple to define streamed operations. However their main drawback is to provide only an approximated representation of the initial object connectivity leading to complex and sometimes ill-formed traversal of the boundaries of the object.

Many previously proposed representations of planar face graphs either store the connectivity using integer references (a solution that has a high storage cost) or re-sample the graph at intersections with grid lines and discard the topology information about what happens inside a pixel.

To solve these problems, we devised a rasterized representation for planar face graphs, called rPFC. Our solution unifies the previous approaches and provides a compact, per pixel representation. It provides a spatial decomposition of the connectivity of the graph into local (per pixel) descriptors that can be stored using a small number of bits per pixel and streamed as needed. This solution stores the topology of the original complex and is capable of representing sub-pixel connectivity.

We defined operators on our rPFC that allow to navigate through the graph connectivity by using only the local information stored in the pixels. Moreover, we proposed four different data structures to encode an rPFC that provide different compromise between memory space and complexity of traversal operators. We implemented our solution in a software that is able to build an rPFC from a 2D planar graph. This software allowed us to conduct our experiments in order to study the memory space required by our different data structures. We also used it to validate our implementation on several data sets: one synthetic generated from 2D Voronoi diagram of random points and geographic information system data of different countries.

Publications

International Journals

Rasterized Planar Face Complex Damiand G., Rossignac J. Computer-Aided Design (CAD), Volume 90, pages 146-156, September 2017 Abstract: We consider a Planar Face Complex (PFC). It is defined by the immersion of a planar and connected graph G, which comprises a set of vertices joined by curved edges. G decomposes the plane into faces that need not be manifold or open-regularized and may be bounded by a single loop edge. The PFC may, for example, be used to represent the complex street network of a city, the decomposition of a continent into countries, or the inhomogeneous structure made of a large set of regions of different materials possibly with internal cracks. The rasterized Planar Face Complex (rPFC) proposed here provides a compact representation of an approximation of a PFC, where the precise location of each vertex is quantized to the pixel that contains it and where the precise geometry of each curved edge is approximated by the ordered list (with possible repetitions) of the pixels traversed by (a chosen polygonal approximation of) the edge. We claim three key contributions: (1) The geometric error between a PFC and its rPFC is bounded by the pixel half-diagonal. (2) In spite of such a drastic discretization of the geometry, the rPFC captures the exact topology of the original PFC (provided that no street lies entirely inside a single pixel) and supports standard graph traversal operators that permit to walk the loop of sidewalks along the streets that bound a face, to cross a street to the opposite sidewalk, or to cross streets in order while walking around their common junction. (3) The local connectivity and order information needed to provide the above functionality is stored at each pixel using only about 4 bits per crossing. We discuss the details of this representation, our implementation of its exact construction, four possible embodiments that offer different space/time efficiency compromises, experimental results, relations between rPFC and prior solutions.
Hierarchical Representation for Rasterized Planar Face Complexes Damiand G., Gonzalez-Lorenzo A., Rossignac J., Dupont F. Computers & Graphics (C&G), Volume 74, pages 161-170, August 2018 Abstract: A useful example of a Planar Face Complex (PFC) is a connected network of streets, each modeled by a zero-thickness curve. The union of these decomposes the plane into faces that may be topologically complex. The previously proposed rasterized representation of the PFC (abbreviated rPFC) (1) uses a fixed resolution pixel grid, (2) quantizes the geometry of the vertices and edges to pixel-resolution, (3) assumes that no street is contained in a single pixel, and (4) encodes the graph connectivity using a small and fixed number of bits per pixel by decomposing the exact topology into per-pixel descriptors. The hierarchical (irregular) version of the rPFC (abbreviated hPFC) proposed here improved on rPFC in several ways: (1) It uses an adaptively constructed tree to eliminate the “no street in a pixel” constraint of the rPFC, hence making it possible to represent exactly any PFC topology and (2) for PFCs of the models tested, and more generally for models with relatively large empty regions, it reduces the storage cost significantly.
Distributed Combinatorial Maps for Parallel Mesh Processing Damiand G., Gonzalez-Lorenzo A., Zara F., Dupont F. Algorithms, Volume 11, Number 7, August 2018 Abstract: We propose a new strategy for the parallelization of mesh processing algorithms. Our main contribution is the definition of distributed combinatorial maps (called n-dmaps), which allow us to represent the topology of big meshes by splitting them into independent parts. Our mathematical definition ensures the global consistency of the meshes at their interfaces. Thus, an n-dmap can be used to represent a mesh, to traverse it, or to modify it by using different mesh processing algorithms. Moreover, an nD mesh with a huge number of elements can be considered, which is not possible with a sequential approach and a regular data structure. We illustrate the interest of our solution by presenting a parallel adaptive subdivision method of a 3D hexahedral mesh, implemented in a distributed version. We report space and time performance results that show the interest of our approach for parallel processing of huge meshes.

NGTMod

Next generation technologies for modeling the full complexity of living and designed structures

Context and overall objectives of the project

Main results achieved

Publications

Members

Greetings