1 Image Analysis and Computer Graphics, Department of Informatics and Mathematical Modeling, Technical University of Denmark2 Department of Informatics and Mathematical Modeling, Technical University of Denmark3 Department of Applied Mathematics and Computer Science, Technical University of Denmark
The topic of this thesis is volume graphics, and in particular techniques which are applicable to volume sculpting. A volume sculpting system is an interactive computer program for shape modelling where the shape is represented volumetrically in a 3D lattice of so-called voxels. It is argued that it is reasonable to classify the tools in a sculpting system according to whether the tools tend to deform the sculpted object or work according to the paradigm of Constructive Solid Geometry (CSG). Existing volume sculpting systems are surveyed, and it is found that almost all systems provide sculpting tools belonging exclusively to either or both categories. It is also found that existing systems have a number of important deficiencies. For instance, none of the systems provide a generic methodology for deformation. Rather they provide specific solutions for concrete deformation tasks, e.g. smoothing or the creation of small protrusions or dents. Moreover, most of the existing systems are based on a volume representation where the value of a voxel is construed as a pseudo-density with no precise meaning. More precisely, we can tell from a voxel whether it is on the inside or the outside of a represented solid, but nothing more. In this thesis it is argued, that it is useful to be able to give a voxel a more precise meaning. This leads to a cleaner volume representation, and if we choose (as the precise meaning of a voxel) the shortest distance from the voxel position to the closest surface point, we reap additional benefits: It becomes trivial to find surface points, and it becomes much easier to find offset surfaces and to compute various geometric properties such as curvature. Generic techniques for constructive (CSG based) and deformative tools have been implemented. Both sets of tools maintain a volume representation where the meaning of a voxel is shortest distance. The deformative tools are based on a specialization of the Level Set Method. The main advantage of using the Level Set Method is that it is a very generic technique as opposed to methods previously proposed. The main task here has been to restrict the effect of the Level Set Method to a local region of in uence and to ensure a smooth transition between the affected region and the unaffected. The theoretical problem of what shapes that are suitable for volume representation has been considered. I reach the conclusion that a shape is suitable if we can roll a ball on either side of the surface in such a way that no point on (either side of) the surface is untouched. Here, the size of the ball depends on the scale of the voxel lattice. The intuitive quality that the ball can roll on either side of the surface of the solid has been formulated more precisely using concepts from mathematical morphology. Essentially, if the solid is unchanged by a morphological opening using the ball as structuring element, then the ball rolls on the interior side. Likewise, invariance with respect to closing implies that the ball can roll on the exterior. These results are, of course, of theoretical interest, but not exclusively: A technique for constructive manipulation which maintains the properties of openness and closedness has been developed. A technique for fast volume visualization is an essential part of a sculpting system. Two techniques for interactive visualization have been implemented: A novel technique based on point rendering and the well-known Marching Cubes Method. The point rendering technique is compared to marching cubes and to texture based visualization. A ray casting method has also been implemented for the generation of high quality images. The most important disadvantage of the volume representation is its lack of support for features at different scales. By choosing a volume representation, we implicitly choose a scale, and features that are very small with respect to that scale are essentially un-representable. As a solution, I propose an adaptive framework, where voxels are no longer stored in a regular grid but in adaptive grid. This allows for higher concentrations of voxels in some parts of the volume than others, and this, in turn, allows for features at vastly differing scales.