The Computational Geometry Algorithms Library Cgal currently provides packages to compute triangulations in ℝ2 and ℝ3. In this paper we describe a new design for the 3D triangulation package that permits to easily add functionality to compute triangulations in other spaces. These design changes have been implemented, and validated on the case of the periodic space T3. We give a detailed description of the realized changes together with their motivation. Finally, we show benchmarks to prove that the new design does not affect the efficiency.

We construct a class of envelope surfaces in Rd, more precisely envelopes of balls. An envelope surface is a closed C1 (tangent continuous) manifold wrapping tightly around the union of a set of balls. Such a manifold is useful in modeling since the union of a finite set of balls can approximate any closed smooth manifold arbitrarily close.The theory of envelope surfaces generalizes the theoretical framework of skin surfaces [5] developed by Edelsbrunner for molecular modeling. However, envelope surfaces are more flexible: where a skin surface is controlled by a single parameter, envelope surfaces can be adapted locally.We show that a special subset of envelope surfaces is piecewise quadratic and derive conditions under which the envelope surface is C1. These conditions can be verified automatically. We give examples of envelope surfaces to demonstrate their flexibility in surface design.

Skin surfaces are used for the modeling and visualization of molecules. They form a class of tangent continuous surfaces defined in terms of a set of balls (the atoms of the molecule) and a shrink factor. More recently, skin surfaces have been used to approximate arbitrary surfaces. We present an algorithm that approximates a skin surface with a topologically correct mesh. The complexity of the mesh is linear in the size of the Delaunay triangulation of the balls, which is worst case optimal. We also adapt two existing refinement algorithms to improve the quality of the mesh and show that the same algorithm can be used for meshing a union of balls.