Towards the Three-dimensional Arrangement of Quadrics: an Exact Parametric Approach

This book presents a complete, exact and efficient algorithm to compute the adjacency graph of an arrangement of quadrics, i.e., surfaces of algebraic degree 2. Extending an approach for an exact parameterization of the intersection curves of two quadrics, the approach computes the exact parameter value for intersection points and from that the adjacency graph of the arrangement. The presented implementation is complete in the sense that it can handle all kinds of inputs. It is exact in that it always computes the mathematically correct result. It is efficient measured in running times, i.e. it compares favorably to the only previously implemented approach. The approach was realized in the context of the EXACUS project whose central goal is the development of a demonstrator of a reliable and efficient CAD geometry kernel spending great effort on completeness, exactness, efficiency, documentation and reusability. Due to its specific requirements, the work on quadrics had particular impact on the generic number type support and the modular methods used within EXACUS, which is by now successfully integrated into CGAL, the computational geometry algorithms library.