Mesh-based Shape Approximation with Guaranteed Progress Toward Global Optima

3IA Côte d'Azur; France; Sur place; EUR 20 000 - 40 000; Plein temps

Résumé du poste

Une opportunité de doctorat à 3IA Côte d'Azur se concentre sur l'optimisation des algorithmes pour l'approximation de formes 3D. Le candidat explorera des méthodes innovantes, y compris l'apprentissage automatique, pour résoudre des problèmes complexes dans le traitement géométrique.

Qualifications

• Connaissance des algorithmes d'optimisation et de traitement géométrique.
• Compétences en apprentissage automatique et en méthodes basées sur les données.
• Capacité à travailler sur des problèmes complexes et ill-posed.

Responsabilités

• Explorer de nouveaux algorithmes d'optimisation pour l'approximation de formes 3D.
• Développer des méthodes garantissant la progression vers l'optimum global.
• Utiliser l'apprentissage par renforcement pour prédire les bénéfices des opérateurs.

Formation

Doctorat en informatique ou domaine connexe

Description du poste

Context.

The initial great promise of 3D geometric modeling and processing was to achieve for shapes what had been done in digital signal processing for sound and images. Over the last twenty years, it has matured into an established research community seeking automatic, computerized processing of 3D geometric data obtained through measurements or designs.

The following developments have shaped this Ph.D. topic proposal:

• The optimal approximation of 3D shapes using meshes is known to be a NP-hard problem. This means that finding the best possible mesh representation for a given shape, while minimizing error and maximizing efficiency, is computationally challenging—no known polynomial-time algorithm exists to solve it optimally in all cases. Because of this complexity, researchers typically rely on heuristics, approximation algorithms, and optimization techniques to generate practical
solutions that only reach local minima. Some common approaches include: (1) Iterative refinement methods that improve the approximation over time, (2) Energy-based optimization that balances accuracy and mesh complexity, or (3) Graph-based techniques that seek near-optimal connectivity structures for mesh representation.

• Recent advances in machine learning and data-intensive approaches facilitate the search for better or even global minima via evolutionary computations or reinforcement learning.

Objectives.

The main scientific objective of this thesis is to explore novel optimization algorithms for mesh-based approximation of 3D shapes. A specific challenge is to devise algorithms that are guaranteed to always progress toward the global optimum. In this
context, optimum translates into either the minimal mesh complexity for a given error tolerance, or its dual problem, that is finding the minimum approximation error for a given mesh complexity. Most greedy algorithms utilize local operators [2, 1], or
variational approaches [5] or different stages (topology, then geometry) [6], or a larger repertoire of operators [9]. More specifically, most algorithms (meshing, remeshing or mesh processing) rely upon operators that range from local (eg, edge flip, edge collapse, vertex insertion [6] or vertex relocation) to global (eg relocation of all vertices) through semi-local (eg, sequence of edge flips or vertex relocation on a stencil). Each operator is associated to both a cost (compute or energy) and a benefit in terms of the main objective function (eg, approximation error). A key question is to devise an algorithm that organizes the operators into a sequence, such that the best operators (low cost and high benefits) are performed first so as to obtain (1) the best tradeoff between time or energy and objective function, and (2) guarantees that the algorithm can always progress toward the global optimum. One difficulty lies into the fact that estimating the benefit of one operator is almost as costly as applying it.

One possible direction to explore is the use of reinforcement learning or advanced machine learning to predict benefits of operators and to organize the operators into an optimal sequence.

The same principle can apply to ill-posed problems that abound in geometric modeling and processing, where the objective function is replaced by multiple objectives or by satisfactory balance between different criteria.

References

[1] J. A. Bærentzen, J. Gravesen, F. Anton, and H. Aanæs, Guide to Computational Geometry Processing. 2012.

[2] M. Botsch, L. Kobbelt, M. Pauly, P. Alliez, and B. Lévy, Polygon Mesh Processing. 2010.

[3] L. Feng, P. Alliez, L. Busé, H. Delingette, and M. Desbrun, “Curved optimal delaunay triangulation,” ACM Trans. Graph., vol. 37, no. 4, 2018, doi: 10.1145/3197517.3201358.

[4] D. Cohen-Steiner, P. Alliez, and M. Desbrun, “Variational shape approximation,” in ACM Transactions on Graphics, 2004, vol. 23, no. 3, doi: 10.1145/1015706.1015817.

[5] M. Mandad, D. Cohen-Steiner, and P. Alliez, “Isotopic approximation within a tolerance volume,” ACM Trans. Graph., vol. 34, no. 4, 2015, doi: 10.1145/2766950.

[6] C. Jamin, P. Alliez, M. Yvinec, and J.-D. Boissonnat, “CGALmesh: A generic framework for delaunay mesh generation,” ACM Trans. Math. Softw., vol. 41, no. 4, 2015, doi: 10.1145/2699463.

[7] B. M. Klingner and J. R. Shewchuk, “Aggressive tetrahedral mesh improvement,” 2008, doi: 10.1007/978-3-540-75103-8_1.