Arrondi de maillages en 3D

Supervisor: Sylvain Lazard (https://members.loria.fr/Sylvain.Lazard/)

Hosting team: GAMBLE ( hhttps://gamble.loria.fr/ )

Grant type : Competing for a doctoral contract of the University of Lorraine

Application deadline: 21/05/2020

Context

Rounding 3D polygonal structures is a fundamental problem in computational geometry. Indeed, many implementations dealing with 3D polygonal objects, in academia and industry, require as input pairwise-disjoint polygons whose vertices have coordinates given with fixed-precision representations (usually with 32 or 64 bits). On the other hand, many algorithms and implementations dealing with 3D polygonal objects in computational geometry output polygons whose vertices have coordinates that have arbitrary- precision representations. For instance, when computing boolean operations on polyhedra, some new ver- tices are defined as the intersection of three faces and their exact coordinates are rational numbers whose numerators and denominators are defined with roughly seven times the number of bits used for representing each input coordinate. The same issue appears when removing self-intersections in meshes, which happen to be very common in some contexts: e.g., 45% of the 10 thousands meshes in the Thingi10K data base self-intersect [18]. Similarly, when applying a rotation to a polyhedron, the new vertices have coordinates that involve trigonometric functions and, when sampling algebraic surfaces, the vertices are obtained as solutions of algebraic systems.

This discrepancy between the precision of the input and output of many geometric algorithms is an issue, both in academia (see e.g. [18] and references therein) and in industry [3,15], because it often prevents the output of one algorithm from being directly used as the input to a subsequent algorithm. The problem of rounding the coordinates of 3D polygonal objects without creating self-intersections between the faces and without changing the geometry too much (the faces can however be subdivided) is thus an important problem.

Practical state-of-the-art solutions are to naively round the vertices, compute the induced self-intersections and, if any, recurse for some time [15,18]. Such heuristics are shown to not always work in practice [15,18], which calls for some proven solutions.

The problem is well understood in 2D [1,6–12,14] but, despite its relevance, the literature is extremely scarce in 3D: Two schemes were presented in 1990 and 1997 for rounding polyhedral subdivisions [13] and segments [6], but they were both incorrect [5]. Fortune, first suggested a high-level scheme which does not generalize to polygonal objects defined by their vertices [4] and then presented in 1999 a solution [5] that was seminal but which does not solve the actual problem as it uses a grid precision that depends on the number n of input faces (the vertices coordinates are rounded to integer multiples of about 1 /n).

After a gap of about two decades, we recently presented the first theoretical solution [2] that solves the problem of rounding, on a uniform grid independent of the input, the vertices of a set of interior- disjoint polygons without creating self-intersections (preserving the topology in some sense) and preserving the geometry (bounding the Hausdorff distance between the faces and their bounded images). Despite this breakthrough, the proposed solution is purely theoretical as its worst-case space and time complexity are in O(n^13) and O(n^15). Still, this solutions opens many new alleys of research, which we will address in this PhD.

More recently, in the Spring of 2019, Leo Valque in his Master (M2) internship started to investigate some of these directions. In particular, he presented some evidences that the algorithm in [2] was actually not (entirely) implementable in a reasonable way and that its practical complexity is likely closer to O(n sqrt{n}) than O(n^15) but that it is still too large (considering the constants) to be practical.

Objectives

In a nutshel, the goal of this PhD is to propose a certified and practically efficient algorithm and an implementation for rounding meshes in 3D. More precisely, the approach is multifaceted. First it is necessary to develop an algorithm in the spirit of the recent theoretical solution [2] but which can be implemented in a reasonable way. Furthermore, such algorithm will need to be reasonably efficient in practice, ideally with an observed complexity on real data close to O(n sqrt{n}). Ideas have been raised for this problem in Valque Master thesis [17] but they still need to be explored.

Second, the candidate will have to develop an algorithm that can round efficiently the vertices everywhere it does not cause topological conflicts. This problem is quite clearly tractable although it is more subtle than it seems at first sight.

Furthermore, the two above algorithms will have to be compatible and intertwined. Ideally we aim at a solution that would round naively everywhere it does not cause troubles and that would use the heavy- hammer approach in hopefully small boxes where rounding is difficult. This goal might be out of reach but a weaker goal, still hopefully efficient, is to apply the heavy-hammer scheme in hopefully reasonably small slabs (instead of boxes).

The goal is also to implement these algorithms in CGAL [16], the reference library for geometric al- gorithms. This is especially interesting because Geometry Factory (the start-up that distributes CGAL) has requests from companies for such software and this would be a good way for distributing it widely and swiftly.

Another facet of the work will be to study the complexity of these algorithms under some reasonable probabilistic model. Indeed, on one hand, the worst-case bound of O(n^15) in [2] seems difficult to substantially improve and on the other hand, there are some evidences that a practical complexity in (O(n sqrt{n})) makes sense. The gap is thus very large. One goal is to study the complexity considering some reasonable distributions of vertices on surfaces. A first step has been considered in this direction in [2] showing a complexity of O(n^5) under some set of hypotheses but the gap still remains large.

The thesis will include both theoretical work and programming in the well-recognized C++ CGAL library, which will open up many opportunities for the PhD student in both academia and industry.

 

Prerequisites

Master in Computer Science. Expertise in Computer science, Mathematics, C++ required. CGAL knowledge would be a plus.

References

[1] Mark de Berg, Dan Halperin, and Mark Overmars. An intersection-sensitive algorithm for snap rounding. Computational Geometry, 36(3):159–165, 2007. doi:10.1016/j.comgeo.2006.03.002.
[2] Olivier Devillers, Sylvain Lazard, and William J. Lenhart. 3D Snap Rounding. In Bettina Speckmann and Csaba D. To ́th, editors, 34th International Symposium on Computational Geometry (SoCG 2018), volume 99 of Leibniz International Proceedings in Informatics (LIPIcs), pages 30:1–30:14, Dagstuhl, Germany, 2018. Schloss Dagstuhl–Leibniz-Zentrum fuer Informatik. URL: http://drops.dagstuhl.de/opus/volltexte/2018/8743, doi:10.4230/LIPIcs.SoCG.2018.30.
[3] Sébastien Loriot (Geometry factory CGAL). Private communication, 2019.
[4] Steven Fortune. Polyhedral modelling with multiprecision integer arithmetic. Computer-Aided Design, 29(2):123
– 133, 1997. Solid Modelling. doi:doi.org/10.1016/S0010-4485(96)00041-3.
[5] Steven Fortune. Vertex-rounding a three-dimensional polyhedral subdivision. Discrete & Computational Geom- etry, 22(4):593–618, 1999. doi:10.1007/PL00009480.
[6] Michael T. Goodrich, Leonidas J. Guibas, John Hershberger, and Paul J. Tanenbaum. Snap rounding line segments efficiently in two and three dimensions. In Proceedings of the thirteenth annual symposium on Compu- tational geometry, pages 284–293. ACM, 1997. doi:10.1145/262839.262985.
[7] Daniel H. Greene and F. Frances Yao. Finite-resolution computational geometry. In 27th Annual Symposium on Foundations of Computer Science, 1986, pages 143–152. IEEE, 1986. doi:10.1109/SFCS.1986.19.
[8] Leonidas J. Guibas and David H. Marimont. Rounding arrangements dynamically. International Journal of Computational Geometry & Applications, 8(02):157–178, 1998. doi:10.1142/S0218195998000096.
[9] Dan Halperin and Eli Packer. Iterated snap rounding. Computational Geometry, 23(2):209–225, 2002. doi: 10.1016/S0925-7721(01)00064-5.
[10] John Hershberger. Improved output-sensitive snap rounding. Discrete & Computational Geometry, 39(1):298– 318, Mar 2008. doi:10.1007/s00454-007-9015-0.
[11] John Hershberger. Stable snap rounding. Computational Geometry, 46(4):403–416, 2013. doi:10.1016/j. comgeo.2012.02.011.
[12] John D. Hobby. Practical segment intersection with finite precision output. Computational Geometry, 13(4):199– 214, 1999. doi:10.1016/S0925-7721(99)00021-8.
[13] Victor Milenkovic. Rounding face lattices in d dimensions. In Proceedings of the 2nd Canadian Conference on Computational geometry, pages 40–45, 1990.
[14] Eli Packer. Iterated snap rounding with bounded drift. Computational Geometry, 40(3):231 – 251, 2008. doi: doi.org/10.1016/j.comgeo.2007.09.002.
[15] Andr ́e Lieutier (Dassault syst`emes). Private communication, 2006.
[16] The CGAL Project. CGAL User and Reference Manual. CGAL Editorial Board, 4.14.1 edition, 2019. URL:
https://doc.cgal.org/4.14.1/Manual/packages.html.
[17] Leo Valque. 3D Snap Rounding. Master’s thesis, ENS Lyon, 2019.
[18] Qingnan Zhou, Eitan Grinspun, Denis Zorin, and Alec Jacobson. Mesh arrangements for solid geometry. ACM Trans. Graph., 35(4):39:1–39:15, July 2016. URL: http://doi.acm.org/10.1145/2897824.2925901, doi:10. 1145/2897824.2925901.

Logo d'Inria