Engineer - Block-structured quadrilateral meshing using medial axis
Contract type : Fixed-term contract
Level of qualifications required : Graduate degree or equivalent
Fonction : Temporary scientific engineer
Context
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).
Assignment
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.
Main activities
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?
Skills
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.
Benefits package
- 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
Remuneration
From €2692 gross/month depending on experience and qualifications
General Information
- Theme/Domain : Interaction and visualization
- Town/city : Villers lès Nancy
- Inria Center : Centre Inria de l'Université de Lorraine
- Starting date : 2025-07-01
- Duration of contract : 6 months
- Deadline to apply : 2025-04-26
Warning : you must enter your e-mail address in order to save your application to Inria. Applications must be submitted online on the Inria website. Processing of applications sent from other channels is not guaranteed.
Instruction to apply
Defence Security :
This position is likely to be situated in a restricted area (ZRR), as defined in Decree No. 2011-1425 relating to the protection of national scientific and technical potential (PPST).Authorisation to enter an area is granted by the director of the unit, following a favourable Ministerial decision, as defined in the decree of 3 July 2012 relating to the PPST. An unfavourable Ministerial decision in respect of a position situated in a ZRR would result in the cancellation of the appointment.
Recruitment Policy :
As part of its diversity policy, all Inria positions are accessible to people with disabilities.
Contacts
- Inria Team : PIXEL
-
Recruiter :
Corman Etienne / etienne.corman@loria.fr
About Inria
Inria is the French national research institute dedicated to digital science and technology. It employs 2,600 people. Its 200 agile project teams, generally run jointly with academic partners, include more than 3,500 scientists and engineers working to meet the challenges of digital technology, often at the interface with other disciplines. The Institute also employs numerous talents in over forty different professions. 900 research support staff contribute to the preparation and development of scientific and entrepreneurial projects that have a worldwide impact.