Engineer - Block-structured quadrilateral meshing using medial axis

PIXEL is a research team in digital geometry processing. More specifically, we are interested in parameterization techniques, meshing and reconstruction of objects from 3D point clouds.

We investigate mathematically correct, scalable and numerically stable solutions, by studying the properties of the objective function in order to develop efficient optimization algorithms.

Our methods have applications in both Computer Graphics and Scientific Computing which we develop in cooperation with researchers and industrial partners from various fields. These applications include oil exploration, plasma physics, bio-chemistry and computer-aided design.

The engineer will be advised by Etienne Corman (chargé de recherche CNRS).

In computer science, geometric objects are most often represented by meshes, in particular triangle meshes. However, numerical simulations sometimes require quadrilateral meshes for high-performance computation because of their efficient memory access, and domain partitioning for parallel processing. Generally speaking, a good quad mesh is made of large quadrilateral regions looking like a deformed grid. In other words, we would like to have all vertices incident exactly to 4 quads. Unfortunately, meshing methods either produce highly irregular meshes or are extremely complex and provide little guarantees on the output. 

In this offer we propose to study medial-axis-based algorithms for quadrilateral partitioning. Medial-axis-based algorithms have been considered as a promising approach for automatically decomposing a domain into quadrilateral blocks while ensuring minimal singular vertices. TopMaker [1] is a notable example, providing a robust decomposition strategy. This algorithm suffers from limitations such as the capture of curved block boundaries, poor geometric quality, and the presence of non-quadrilateral blocks. But the main limitations of this class of algorithms is that it can only be applied to planar domains. 

In a recent article (currently under review), we proposed an improved block decomposition method that enhances TopMaker by integrating integer optimization for subdivision selection and incorporating additional singular nodes to better approximate the domain geometry. Our approach assigns a mesh template to each point of the medial axis, greatly improving the block quality while ensuring a valid conform quadrilateral decomposition. 

The goal of this job is to overcome the limitation encounter by all algorithms using medial axes: it only applies to planar domains. The medial axis of a domain is the set of all points having more than one closest point on the object's boundary. This definition can be extended to curved surfaces by using a geodesic distance instead of a Euclidean distance. However, geodesic distances are notoriously challenging to compute. In order to obtain a stable computation of the medial axis several options can be considered:

• Approximating geodesics using heat diffusion schemes [2,3];
• Approximating circumcenters using intrinsic Delaunay triangulations [4];
• Going back to the planar case using a parametrization of the curved surface.

The third direction will always work but it provides an extremely poor approximation of the real medial axis.

References:

[1] RIGBY, David. Topmaker: A technique for automatic multi-block topology generation using the medial axis. In : Fluids engineering division summer meeting. 2003. p. 1991-1997.

[2] CRANE, Keenan, WEISCHEDEL, Clarisse, et WARDETZKY, Max. Geodesics in heat: A new approach to computing distance based on heat flow. ACM Transactions on Graphics (TOG), 2013, vol. 32, no 5, p. 1-11.

[3] SHARP, Nicholas, SOLIMAN, Yousuf, et CRANE, Keenan. The vector heat method. ACM Transactions on Graphics (TOG), 2019, vol. 38, no 3, p. 1-19.

[4] GILLESPIE, Mark, SHARP, Nicholas, et CRANE, Keenan. Integer coordinates for intrinsic geometry processing. ACM Transactions on Graphics (TOG), 2021, vol. 40, no 6, p. 1-13.

The successful applicant will be trusted with the following tasks:

• From our research code, reimplement a clean version of our algorithm generalizing TopMaker in C++;
• Compute the medial axes generalized to curved surfaces using the three methods presented earlier;
• Answer the question: does the guaranties of robustness provided by TopMaker still holds in the curved case? 

Required skills:

• Advance knowledge in C++
• Some knowledge of geometry processing algorithms and data structures (half-edges, Delaunay triangulations)

Soft skills:

• Ability to work in a team and collaborate with experts from other fields
• Thorough and detail-oriented

Fluency in English, or fluency in French with excellent level in English are mandatory to fill the position.

• Subsidized meals
• Partial reimbursement of public transport costs
• Leave: 7 weeks of annual leave + 10 extra days off due to RTT (statutory reduction in working hours) + possibility of exceptional leave (sick children, moving home, etc.)
• Possibility of teleworking (after 6 months of employment) and flexible organization of working hours
• Professional equipment available (videoconferencing, loan of computer equipment, etc.)
• Social, cultural and sports events and activities
• Access to vocational training
• Social security coverage

From €2692 gross/month depending on experience and qualifications