A generic and flexible framework for the geometrical and topological analysis of (algebraic) surfaces

We present a generic framework on a set of surfaces $\calS$ in $\R^3$ that provides their geometric and topological analysis in order to support various algorithms and applications in computational geometry. Our implementation follows the generic programming paradigm, i.e., to support a certain family of surfaces, we require a small set of types and some basic operations on them, all collected in a model of the newly presented {\sc SurfaceTraits\_3} concept. The framework obtains geometric and topological information on a non-empty set of surfaces in two steps. First, important $0$- and $1$-dimensional features are projected onto the $xy$-plane, obtaining an arrangement $\calA_\calS$ with certain properties. Second, for each of its components, a sample point is lifted back to $\R^3$ while detecting intersections with the given surfaces. This idea is similar to Collins' cylindrical algebraic decomposition (cad). In contrast, we reduce the number of liftings using \cgal's Arrangement\_2 package as a basic tool. Properly instantiated, the framework provides main functionality required to support the computation of a Piano Mover's instance. On the other hand, the complexity of the output is high, and thus, we particularly regard the framework as key ingredient for querying information on and constructing geometric objects from a small set of surfaces. Examples are meshing of single surfaces, the computation of space-curves defined by two surfaces, to compute lower envelopes of surfaces, or as a basic step to compute an efficient representation of a three-dimensional arrangement. We also inspirit the framework in two steps. First, we show that the well-known family of algebraic surfaces fulfils the framework's requirements. As robust implementations on these surfaces are lacking these days, we consider the framework to be an important step to fill this gap. Second, we instantiate the framework by a fully-fledged model for special algebraic surfaces, namely quadrics. This instantiation already supports main tasks demanded from rotational robot motion planning~\cite{Latom1993}. How to provide a model for algebraic surfaces of arbitrary degree, is partly discussed in~\cite{bks-exact-08}