The paper presents a set of combined techniques to enhance the real-time visualization of simple or complex molecules (up to order of 106 atoms) space fill mode. The proposed approach includes an innovative technique for efficient computation and storage of ambient occlusion terms, a small set of GPU accelerated procedural impostors for space-fill and ball-and-stick rendering, and novel edge-cueing techniques. As a result, the user's understanding of the three-dimensional structure under inspection is strongly increased (even for still images), while the rendering still occurs in real time.

Range map registration is still the most time consuming phase in the processing of 3D scanning data. This is because real scanning sets are composed of hundreds of range maps and their registration is still partially manual. We propose a new method to manage complex scan sets acquired by following a regular scanner pose pattern. Our goal is to define an initial adjacency graph by coarsely aligning couples of range maps that we know are partially overlapping thanks to the adopted scanning strategy. For a pair of partially overlapping range maps, our iterative solution locates pairs of correspondent vertices through the computation of a regular n×n kernel which takes into account vertex normals and is defined in the 2D space of the range map (represented in implicit 2D format rather than as a triangle mesh in 3D space). The shape-characterization kernel and the metrics defined give a sufficiently accurate shape matching, which has been proven to fit well the requirements of automatic registration. This initial set of adjacency arcs can then be augmented by the automatic identification of the other significant arcs, by adopting a criterion based on approximate range map overlap computation. With respect to the solutions present in literature, the simplifications and assumptions adopted make our solution specifically oriented to complex 3D scanning campaigns (hundreds of range maps). The proposed method can coarsely register range maps in parallel with the acquisition activity and this is a valuable help in assessing on site the completeness of the sampling of large objects.

Standard texture mapping of real-world meshes suffers from the presence of seams that need to be introduced in order to avoid excessive distortions and to make the topology of the mesh compatible to the one of the texture domain. In contrast, cube maps provide a mechanism that could be used for seamless texture mapping with low distortion, but only if the object roughly resembles a cube. We extend this concept to arbitrary meshes by using as texture domain the surface of a polycube whose shape is similar to that of the given mesh. Our approach leads to a seamless texture mapping method that is simple enough to be implemented in currently available graphics hardware.

Very large triangle meshes, i.e., meshes composed of millions of faces, are becoming common in many applications. Obviously, processing, rendering, transmission, and archiving of these meshes are not simple tasks. Mesh simplification and LOD management are a rather mature technology that, in many cases, can efficiently manage complex data. But, only a few available systems can manage meshes characterized by a huge size: RAM size is often a severe bottleneck. In this paper, we present a data structure called Octree-based External Memory Mesh (OEMM). It supports external memory management of complex meshes, loading dynamically in main memory only the selected sections and preserving data consistency during local updates. The functionalities implemented on this data structure (simplification, detail preservation, mesh editing, visualization, and inspection) can be applied to huge triangles meshes on low-cost PC platforms. The time overhead due to the external memory management is affordable. Results of the test of our system on complex meshes are presented.

The paper presents a simple and efficient algorithm for the removal of small topological inconsistencies and high frequency details from surface models. The method, called marching intersections (MI), adopts a volumetric approach and acts as a resampling filter. All the intersection points between the input model and the lines of a user selected 3D reference grid are located and then, beginning from these intersections, an output surface is reconstructed. MI, which presents good characteristics in terms of efficiency, compactness, and quality of the output models, can be also used: for the conversion between different representation schemes; to perform logical operations on geometric models; for the topological simplification of surfaces; and for the simplification of huge meshes, i.e. meshes too large to be allocated in main memory during the simplification process. All these aspects are discussed in the paper and timing and graphic results are presented.

Multi-resolution representations are widely used in many data visualization contexts and applications. The adoption of a multi-resolution approach provides the optimal management of a data representation, using at each instant of time a level of detail that is more adequate for the given action or task to be performed. Recently, multi-resolution has also been introduced into the interactive physically-based simulation of deformable objects (e.g. in virtual surgery applications). In these applications, the processing resources available are often insufficient and pose a critical constraint. The adoption of multi-resolution allows one to improve the accuracy of the simulation in the proximity of the action focus while maintaining computations under a given bound. In this particular context, the user should be able to perform cuts in the object. The problem is that most multi-resolution models need a pre-processing phase in which the data structure is constructed. Such a construction strictly depends on the topology of the object, which is supposed to be invariable. We propose a new approach for the dynamic topological modification of a multi-resolution model, which allows easy updating of the multi-resolution data structure (based on the multi-resolution triangulation framework), and efficient decomposition of the cells intersected by the cut. With respect to previous methods, our solution supports a much lower degree of fragmentation of the decomposition and very short processing times, due to the design of a lookup table (LUT) based splitting solution.

The techniques for reducing the size of a volume dataset by preserving both the geometrical/topological shape and the information encoded in an attached scalar field are attracting growing interest. Given the framework of incremental 3D mesh simplification based on edge collapse, we propose an approach for the integrated evaluation of the error introduced by both the modification of the domain and the approximation of the field of the original volume dataset. We present and compare various techniques to evaluate the approximation error or to produce a sound prediction. A flexible simplification tool has been implemented, which provides a different degree of accuracy and computational efficiency for the selection of the edge to be collapsed. Techniques for preventing a geometric or topological degeneration of the mesh are also presented.

Performing a really interactive and physically‐based simulation of complex soft objects is still an open problem in computer animation/simulation. Given the application domain of virtual surgery training, a complete model should be quite realistic, interactive and should enable the user to modify the topology of the objects. Recent papers propose the adoption of multiresolution techniques to optimize time performance by representing at high resolution only the object parts considered more important or critical. The speed up obtainable at simulation time are counterbalanced by the need of a preprocessing phase strongly dependent on the topology of the object, with the drawback that performing dynamic topology modification becomes a prohibitive issue. In this paper we present an approach that couples multiresolution and topological modifications, based on the adoption of a particle systems approach to the physical simulation. Our approach is based on a tetrahedral decomposition of the space, chosen both for its suitability to support a particle system and for the ready availability of many techniques recently proposed for the simplification and multiresolution management of 3D simplicial decompositions. The multiresolution simulation system is designed to ensure the required speedup and to support dynamic changes of the topology, e.g. due to cuts or lacerations of the represented tissue.

The paper addresses the problem of the representation of three-dimensional works of art (e.g. sculptures, architectural elements, vases, etc.) in a web-based environment. Specifically, we propose a system for the visual presentation of the 3D results of a standard SQL query to distributed archives. The system solves the general problem of the remote visualization of dynamic result sets on the Internet using standard and low cost processing architectures. It provides the user with an innovative visual metaphor for the analysis and investigation of the objects presented. Moreover, the system has been designed to provide capabilities which go beyond visualization (e.g. manipulation), and further extensions are possible. We describe the methodologies used for the acquisition, storing, and manipulation of 3D artistic objects together with details on the system's implementation in a web environment, using the VRML2.0 specification language.

Many sophisticated solutions have been proposed to reduce the geometric complexity of 3D meshes. A problem studied less often is how to preserve on a simplified mesh the detail (e.g., color, high frequency shape detail, scalar fields, etc.) which is encoded in the original mesh. We present a general approach for preserving detail on simplified meshes. The detail (or high frequency information) lost after simplification is encoded through texture or bump maps. The original contribution is that preservation is performed after simplification, by building set of triangular texture patches that are then packed in a single texture map. Each simplified mesh face is sampled to build the associated triangular texture patch; a new method for storing this set of texture patches into a standard rectangular texture is presented and discussed. Our detail preserving approach makes no assumptions about the simplification process adopted to reduce mesh complexity and allows highly efficient rendering. The solution is very general, allowing preservation of any attribute value defined on the high resolution mesh. We also describe an alternative application: the conversion of 3D models with 3D static procedural textures into standard 3D models with 2D textures.

The interval tree is an optimally efficient search structure proposed by Edelsbrunner (1980) to retrieve intervals on the real line that contain a given query value. We propose the application of such a data structure to the fast location of cells intersected by an isosurface in a volume dataset. The resulting search method can be applied to both structured and unstructured volume datasets, and it can be applied incrementally to exploit coherence between isosurfaces. We also address issues of storage requirements, and operations other than the location of cells, whose impact is relevant in the whole isosurface extraction task. In the case of unstructured grids, the overhead, due to the search structure, is compatible with the storage cost of the dataset, and local coherence in the computation of isosurface patches is exploited through a hash table. In the case of a structured dataset, a new conceptual organization is adopted, called the chess-board approach, which exploits the regular structure of the dataset to reduce memory usage and to exploit local coherence. In both cases, efficiency in the computation of surface normals on the isosurface is obtained by a precomputation of the gradients at the vertices of the mesh. Experiments on different kinds of input show that the practical performance of the method reflects its theoretical optimality.

A system to represent and visualize scalar volume data at multiple resolution is presented. The system is built on a multiresolution model based on tetrahedral meshes with scattered vertices that can be obtained from any initial dataset. The model is built off-line through data simplification techniques, and stored in a compact data structure that supports fast on-line access. The system supports interactive visualization of a representation at an arbitrary level of resolution through isosurface and projective methods. The user can interactively adapt the quality of visualization to requirements of a specific application task and to the performance of a specific hardware platform. Representations at different resolutions can be used together to further enhance interaction and performance through progressive and multiresolution rendering.

Abstract The paper deals with the parallelization of Delaunay triangulation, a widely used space partitioning technique. Two parallel implementations of a three‐dimensional incremental construction algorithm are presented. The first is based on the decomposition of the spatial domain, while the second relies on the master‐slaves approach. Both parallelization strategies are evaluated, stressing practical issues rather than theoretical complexity. We report on the exploitation of two different parallel environments: a tightly coupled distributed memory MIMD architecture and a network of workstations co‐operating under the Linda environment Then, a third hybrid solution is proposed, specifically addressed to the exploitation of higher parallelism. It combines the other two solutions by grouping the processing nodes of the multicomputer into clusters and by exploiting parallelism at two different levels.

Since the introduction of standard techniques for isosurface extraction from volumetric datasets, one of the hardest problems has been to reduce the number of triangles (or polygons) generated. The paper presents an algorithm that considerably reduces the number of polygons generated by a Marching Cubes-like scheme (W. Lorensen and H. Cline, 1987) without excessively increasing the overall computational complexity. The algorithm assumes discretization of the dataset space and replaces cell edge interpolation by midpoint selection. Under these assumptions, the extracted surfaces are composed of polygons lying within a finite number of incidences, thus allowing simple merging of the output facets into large coplanar polygons. An experimental evaluation of the proposed approach on datasets related to biomedical imaging and chemical modelling is reported.>

Abstract How to render very complex datasets, and yet maintain interactive response times, is a hot topic in computer graphics. The MagicSphere idea originated as a solution to this problem, but its potential goes much further than this original scope. In fact, it has been designed as a very generical 3D widget: it defines a spherical volume of interest in the dataset modeling space. Then, several filters can be associated with the Magicsphere, which apply different visualization modalities to the data contained in the volume of interest. The visualization of multi‐resolution datasets is selected here as a case study and an ad hoc filter has been designed, the MultiRes filter. Some results of a prototipal implementation are presented and discussed.

In this paper we address the problem of computing visibility information on digital terrain models in parallel. We propose a parallel algorithm for computing the visible region of an observation point located on the terrain. The algorithm is based on a sequential triangle-sorting visibility approach proposed by De Floriani et al. (1989). Static and dynamic parallelization strategies, both in terms of partitioning criteria and scheduling policies, are discussed. The different parallelization strategies are implemented on an MIMD multicomputer and evaluated through experimental results.

Abstract The paper deals with the parallelization of Delaunay triangulation algorithms, giving more emphasis to pratical issues and implementation than to theoretical complexity. Two parallel implementations are presented. The first one is built on De Wall, an Ed triangulator based on an original interpretation of the divide & conquer paradigm. The second is based on an incremental construction algorithm. The parallelization strategies are presented and evaluated. The target parallel machine is a distributed computing environment, composed of coarse grain processing nodes. Results of first implementations are reported and compared with the performance of the serial versions running on a Unix workstation.

Abstract A solution is proposed to the problem of interactive visualization and rendering of volume data. Designed for parallel distributed memory MIMD architectures, the volume rendering system is based on the ray tracing (RT) visualization technique, the Sticks representation scheme (a data structure exploiting data coherence for the compression of classified data sets), the use of a slice‐partitioning technique for the distribution of the data between the processing nodes and the consequent ray‐data‐flow parallelizing strategy. The system has been implemented on two different architectures: an inmos Transputer network and a hypercube nCUBE 6400 architecture. The high number of processors of this latter machine has allowed us to exploit a second level of parallelism (parallelism on image space, or parallelism on pixels) in order to arrive at a higher degree of scalability. In both proposals, the similarities between the chosen data‐partitioning strategy, the communications pattern of the visualization processes and the topology of the physical system architecture represent the key points and provide improved software design and efficiency. Moreover, the partitioning strategy used and the network interconnection topology reduce the communications overhead and allow for an efficient implementation of a static load‐balancing technique based on the prerendering of a low resolution image. Details of the practical issues involved in the parallelization process of volumetric RT, commonly encountered problems (i.e. termination and deadlock prevention) and the sw migration process between different architectures are discussed.

Recently, methods have been defined and investigated for the encoding of quadtrees. Although these methods save storage space, they are normally less efficient. In this short note an artifice is suggested to encode quadtrees. It allows the preservation of the quadtree logical structure, permitting a memory saving higher than 75% without losing efficiency. The main characteristics of the new coding technique are compared with those of previous methods.