Abstract Annotation support in interactive systems is often considered a simple task by the CG community, since it entails the apparently easy selection of a region and its connection with some information. The reality appears more complex. The scope of this paper is two‐fold: first, to review the status of this domain, discussing and characterizing several approaches proposed in literature to manage annotations over geometric models; second, to present in detail an innovative solution proposed and assessed in the framework of Cultural Heritage (CH) applications, called ClippingVolumes. At the annotation definition stage ClippingVolumes uses 3D data to characterize the annotation region; subsequently, annotations are visualized by adopting a two‐pass rendering solution which uses stencil buffers, thus without introducing new geometric elements, changing the topology or duplicating geometry elements. It solves most of the issues that afflict the current state of the art, such as fragmentation, annotation transfer to multiple representations and multi‐resolution data encoding. The latter is a mandatory requirement to produce efficient web‐based systems. We implemented and we fully tested this approach in the framework of a complex system that supports the documentation of CH restoration projects.

We present a novel approach to automatically recover, from a small set of partially overlapping spherical images, an indoor structure representation in terms of a 3D floor plan registered with a set of 3D environment maps. We introduce several improvements over previous approaches based on color and spatial reasoning exploiting Manhattan world priors. In particular, we introduce a new method for geometric context extraction based on a 3D facet representation, which combines color distribution analysis of individual images with sparse multi-view clues. We also introduce an efficient method to combine the facets from different viewpoints in a single consistent model, taking into the reliability of the facet information. The resulting capture and reconstruction pipeline automatically generates 3D multi-room environments in cases where most previous approaches fail, e.g., in the presence of hidden corners and large clutter, without the need for additional dense 3D data or tools. We demonstrate the effectiveness and performance of our approach on different real-world indoor scenes. Our test data is available to allow further studies and comparisons.

We describe an automated pipeline for digitization of catalog drawings of pottery types. This work is aimed at extracting a structured description of the main geometric features and a 3D representation of each class. The pipeline includes methods for understanding a 2D drawing and using it for constructing a 3D model of the pottery. These will be used to populate a reference database for classification of potsherds. Furthermore, we extend the pipeline with methods for breaking the 3D model to obtain synthetic sherds and methods for capturing images of these sherds in a way that matches the imaging methodology of archaeologists. These will serve to build a massive set of synthetic sherd images that will help train and test future automated classification systems.

Abstract Digital fabrication devices exploit basic technologies in order to create tangible reproductions of 3D digital models. Although current 3D printing pipelines still suffer from several restrictions, accuracy in reproduction has reached an excellent level. The manufacturing industry has been the main domain of 3D printing applications over the last decade. Digital fabrication techniques have also been demonstrated to be effective in many other contexts, including the consumer domain. The Cultural Heritage is one of the new application contexts and is an ideal domain to test the flexibility and quality of this new technology. This survey overviews the various fabrication technologies, discussing their strengths, limitations and costs. Various successful uses of 3D printing in the Cultural Heritage are analysed, which should also be useful for other application contexts. We review works that have attempted to extend fabrication technologies in order to deal with the specific issues in the use of digital fabrication in the Cultural Heritage. Finally, we also propose areas for future research.

Using synthetic videos to present a 3D scene is a common requirement for architects, designers, engineers or Cultural Heritage professionals however it is usually time consuming and, in order to obtain high quality results, the support of a film maker/computer animation expert is necessary. We introduce an alternative approach that takes the 3D scene of interest and an example video as input, and automatically produces a video of the input scene that resembles the given video example. In other words, our algorithm allows the user to "replicate" an existing video, on a different 3D scene. We build on the intuition that a video sequence of a static environment is strongly characterized by its optical flow, or, in other words, that two videos are similar if their optical flows are similar. We therefore recast the problem as producing a video of the input scene whose optical flow is similar to the optical flow of the input video. Our intuition is supported by a user-study specifically designed to verify this statement. We have successfully tested our approach on several scenes and input videos, some of which are reported in the accompanying material of this paper.

Abstract Detecting geometric changes between two 3D captures of the same location performed at different moments is a critical operation for all systems requiring a precise segmentation between change and no‐change regions. Such application scenarios include 3D surface reconstruction, environment monitoring, natural events management and forensic science. Unfortunately, typical 3D scanning setups cannot provide any one‐to‐one mapping between measured samples in static regions: in particular, both extrinsic and intrinsic sensor parameters may vary over time while sensor noise and outliers additionally corrupt the data. In this paper, we adopt a multi‐scale approach to robustly tackle these issues. Starting from two point clouds, we first remove outliers using a probabilistic operator. Then, we detect the actual change using the implicit surface defined by the point clouds under a Growing Least Square reconstruction that, compared to the classical proximity measure, offers a more robust change/no‐change characterization near the temporal intersection of the scans and in the areas exhibiting different sampling density and direction. The resulting classification is enhanced with a spatial reasoning step to solve critical geometric configurations that are common in man‐made environments. We validate our approach on a synthetic test case and on a collection of real data sets acquired using commodity hardware. Finally, we show how 3D reconstruction benefits from the resulting precise change/no‐change segmentation.

The advent of low cost scanning devices and the improvement of multi-view stereo techniques have made the acquisition of 3D geometry ubiquitous. Data gathered from different devices, however, result in large variations in detail, scale, and coverage. Registration of such data is essential before visualizing, comparing and archiving them. However, state-of-the-art methods for geometry registration cannot be directly applied due to intrinsic differences between the models, e.g., sampling, scale, noise. In this paper we present a method for the automatic registration of multi-modal geometric data, i.e., acquired by devices with different properties (e.g., resolution, noise, data scaling). The method uses a descriptor based on Growing Least Squares, and is robust to noise, variation in sampling density, details, and enables scale-invariant matching. It allows not only the measurement of the similarity between the geometry surrounding two points, but also the estimation of their relative scale. As it is computed locally, it can be used to analyze large point clouds composed of millions of points. We implemented our approach in two registration procedures (assisted and automatic) and applied them successfully on a number of synthetic and real cases. We show that using our method, multi-modal models can be automatically registered, regardless of their differences in noise, detail, scale, and unknown relative coverage.

Abstract We introduce a framework for the generation of polygonal gridshell architectural structures, whose topology is designed in order to excel in static performances. We start from the analysis of stress on the input surface and we use the resulting tensor field to induce an anisotropic nonEuclidean metric over it. This metric is derived by studying the relation between the stress tensor over a continuous shell and the optimal shape of polygons in a corresponding gridshell. Polygonal meshes with uniform density and isotropic cells under this metric exhibit variable density and anisotropy in Euclidean space, thus achieving a better distribution of the strain energy over their elements. Meshes are further optimized taking into account symmetry and regularity of cells to improve aesthetics. We experiment with quad meshes and hexdominant meshes, demonstrating that our gridshells achieve better static performances than stateoftheart gridshells.

Current digital painting tools are primarily targeted at professionals and are often overwhelmingly complex for use by novices. At the same time, simpler tools may not invoke the user creatively, or are limited to plain styles that lack visual sophistication. There are many people who are not art professionals, yet would like to partake in digital creative expression. Challenges and rewards for novices differ greatly from those for professionals. In this paper, we leverage existing works in Creativity and Creativity Support Tools (CST) to formulate design goals specifically for digital art creation tools for novices. We implemented these goals within a digital painting system, called Painting with Bob. We evaluate the efficacy of the design and our prototype with a user study, and we find that users are highly satisfied with the user experience, as well as the paintings created with our system.

Abstract We introduce a novel efficient technique for automatically transforming a generic renderable 3D scene into a simple graph representation named ExploreMaps, where nodes are nicely placed point of views, called probes, and arcs are smooth paths between neighboring probes. Each probe is associated with a panoramic image enriched with preferred viewing orientations, and each path with a panoramic video. Our GPU‐accelerated unattended construction pipeline distributes probes so as to guarantee coverage of the scene while accounting for perceptual criteria before finding smooth, good looking paths between neighboring probes. Images and videos are precomputed at construction time with off‐line photorealistic rendering engines, providing a convincing 3D visualization beyond the limits of current real‐time graphics techniques. At run‐time, the graph is exploited both for creating automatic scene indexes and movie previews of complex scenes and for supporting interactive exploration through a low‐DOF assisted navigation interface and the visual indexing of the scene provided by the selected viewpoints. Due to negligible CPU overhead and very limited use of GPU functionality, real‐time performance is achieved on emerging web‐based environments based on WebGL even on low‐powered mobile devices.

Mesh joinery is an innovative method to produce illustrative shape approximations suitable for fabrication. Mesh joinery is capable of producing complex fabricable structures in an efficient and visually pleasing manner. We represent an input geometry as a set of planar pieces arranged to compose a rigid structure, by exploiting an efficient slit mechanism. Since slices are planar, to fabricate them a standard 2D cutting system is enough. We automatically arrange slices according to a smooth cross-field defined over the surface. Cross-fields allow representing global features that characterize the appearance of the shape. Slice placement conforms to specific manufacturing constraints.

Multiview stereo reconstruction methods can provide impressive results in a number of applications. Nevertheless, when trying to apply the state-of-the-art methods in the case of a more structured 3D acquisition, the lack of feedback on the quality of the reconstruction during the photo shooting can be problematic. In this paper we present a framework for the assisted reconstruction from images of real objects. The framework is able to provide, in quasi-real time, a sparse reconstruction of the scene, so that the user is able to spot the missing or problematic parts. Moreover, the framework is able to separate the object of interest from the background and suggests missing points of view to the user, without any previous knowledge of the shape of the scene and the acquisition path. This is obtained by analyzing the sparse reconstruction and the connection between the reconstructed points and the input images. The framework has been tested on a variety of practical cases, and it has proved to be effective not only to obtain more complete reconstructions, but also to reduce the number of images needed and the processing time for dense reconstruction.

Abstract In this paper, we present EnvyDepth, an interface for recovering local illumination from a single HDR environment map. In EnvyDepth, the user quickly indicates strokes to mark regions of the environment map that should be grouped together in a single geometric primitive. From these annotated strokes, EnvyDepth uses edit propagation to create a detailed collection of virtual point lights that reproduce both the local and the distant lighting effects in the original scene. When compared to the sole use of the distant illumination, the added spatial information better reproduces a variety of local effects such as shadows, highlights and caustics. Without the effort needed to create precise scene reconstructions, EnvyDepth annotations take only tens of seconds to produce a plausible lighting without visible artifacts. This is easy to obtain even in the case of complex scenes, both indoors and outdoors. The generated lighting environments work well in a production pipeline since they are efficient to use and able to produce accurate renderings.

Abstract In this work we present a new algorithm for accelerating the colour bilateral filter based on a subsampling strategy working in the spatial domain. The base idea is to use a suitable subset of samples of the entire kernel in order to obtain a good estimation of the exact filter values. The main advantages of the proposed approach are that it has an excellent trade‐off between visual quality and speed‐up, a very low memory overhead is required and it is straightforward to implement on the GPU allowing real‐time filtering. We show different applications of the proposed filter, in particular efficient cross‐bilateral filtering, real‐time edge‐aware image editing and fast video denoising. We compare our method against the state of the art in terms of image quality, time performance and memory usage.

Abstract We present a statistical method for the estimation of the Spatially Varying Bidirectional Reflectance Distribution Function (SVBRDF) of an object with complex geometry, starting from video sequences acquired with fixed but general lighting conditions. The aim of this work is to define a method that simplifies the acquisition phase of the object surface appearance and allows to reconstruct an approximated SVBRDF. The final output is suitable to be used with a 3D model of the object to obtain accurate and photo‐realistic renderings. The method is composed by three steps: the approximation of the environment map of the acquisition scene, using the same object as a probe; the estimation of the diffuse color of the object; the estimation of the specular components of the main materials of the object, by using a Phong model. All the steps are based on statistical analysis of the color samples projected by the video sequences on the surface of the object. Although the method presents some limitations, the trade‐off between the easiness of acquisition and the obtained results makes it useful for practical applications.

This paper deals with the problem of taking random samples over the surface of a 3D mesh describing and evaluating efficient algorithms for generating different distributions. We discuss first the problem of generating a Monte Carlo distribution in an efficient and practical way avoiding common pitfalls. Then, we propose Constrained Poisson-disk sampling, a new Poisson-disk sampling scheme for polygonal meshes which can be easily tweaked in order to generate customized set of points such as importance sampling or distributions with generic geometric constraints. In particular, two algorithms based on this approach are presented. An in-depth analysis of the frequency characterization and performance of the proposed algorithms are also presented and discussed.

The projection of a photographic data set on a 3D model is a robust and widely applicable way to acquire appearance information of an object. The first step of this procedure is the alignment of the images on the 3D model. While any reconstruction pipeline aims at avoiding misregistration by improving camera calibrations and geometry, in practice a perfect alignment cannot always be reached. Depending on the way multiple camera images are fused on the object surface, remaining misregistrations show up either as ghosting or as discontinuities at transitions from one camera view to another. In this paper we propose a method, based on the computation of Optical Flow between overlapping images, to correct the local misalignment by determining the necessary displacement. The goal is to correct the symptoms of misregistration, instead of searching for a globally consistent mapping, which might not exist. The method scales up well with the size of the data set (both photographic and geometric) and is quite independent of the characteristics of the 3D model (topology cleanliness, parametrization, density). The method is robust and can handle real world cases that have different characteristics: low level geometric details and images that lack enough features for global optimization or manual methods. It can be applied to different mapping strategies, such as texture or per-vertex attribute encoding.

Analyzing either high-frequency shape detail or any other 2D fields (scalar or vector) embedded over a 3D geometry is a complex task, since detaching the detail from the overall shape can be tricky. An alternative approach is to move to the 2D space, resolving shape reasoning to easier image processing techniques. In this paper we propose a novel framework for the analysis of 2D information distributed over 3D geometry, based on a locally smooth parametrization technique that allows us to treat local 3D data in terms of image content. The proposed approach has been implemented as a sketch-based system that allows to design with a few gestures a set of (possibly overlapping) parameterizations of rectangular portions of the surface. We demonstrate that, due to the locality of the parametrization, the distortion is under an acceptable threshold, while discontinuities can be avoided since the parametrized geometry is always homeomorphic to a disk. We show the effectiveness of the proposed technique to solve specific Cultural Heritage (CH) tasks: the analysis of chisel marks over the surface of a unfinished sculpture and the local comparison of multiple photographs mapped over the surface of an artwork. For this very difficult task, we believe that our framework and the corresponding tool are the first steps toward a computer-based shape reasoning system, able to support CH scholars with a medium they are more used to.

Computer Graphics Forum is the leading journal for in-depth technical articles on computer graphics. The rapid publication of articles allows readers to keep up to date with new debates and topics of research. The journal features a lively mix of original research, computer graphics applications, conference reports, state-of-the-art surveys and workshops.

Abstract This work concerns a novel study in the field of image‐to‐geometry registration. Our approach takes inspiration from medical imaging, in particular from multi‐modal image registration. Most of the algorithms developed in this domain, where the images to register come from different sensors (CT, X‐ray, PET), are based on Mutual Information, a statistical measure of non‐linear correlation between two data sources. The main idea is to use mutual information as a similarity measure between the image to be registered and renderings of the model geometry, in order to drive the registration in an iterative optimization framework. We demonstrate that some illumination‐related geometric properties, such as surface normals, ambient occlusion and reflection directions can be used for this purpose. After a comprehensive analysis of such properties we propose a way to combine these sources of information in order to improve the performance of our automatic registration algorithm. The proposed approach can robustly cover a wide range of real cases and can be easily extended.

Abstract The support of advanced information technology (IT) to preservation, restoration and documentation of Cultural Heritage (CH) is becoming a very important goal for the research community. Michelangelo's David was one of the first applications of 3D scanning technology on a highly popular work of art. The subsequent restoration campaign, started in 2002 and concluded in 2004, was also a milestone for the adoption of modern scientific analysis procedures and IT tools in the framework of a restoration process. One of the focuses in this restoration was also methodological, i.e. to plan and adopt innovative ways to document the restoration process. In this paper, we present the results of an integration of different restoration data (2D and 3D datasets) which has been concluded recently. The recent evolution of HW and SW graphics technologies gave us the possibility to interactively visualize an extremely dense 3D model which incorporates the colour information provided by two professional photographic campaigns, made before and after the restoration. Moreover, we present the results concerning the mapping, in this case on the 2D media, of the reliefs produced by restorers to assess and document the status of the marble surface before the restoration took place. This result could lead to new and fascinating applications of computer graphics for preservation, restoration and documentation of CH.

Abstract Visual fidelity and interactivity are the main goals in Computer Graphics research, but recently also audio is assuming an important role. Binaural rendering can provide extremely pleasing and realistic three‐dimensional sound, but to achieve best results it's necessary either to measure or to estimate individual Head Related Transfer Function (HRTF). This function is strictly related to the peculiar features of ears and face of the listener. Recent sound scattering simulation techniques can calculate HRTF starting from an accurate 3D model of a human head. Hence, the use of binaural rendering on large scale (i.e. video games, entertainment) could depend on the possibility to produce a sufficiently accurate 3D model of a human head, starting from the smallest possible input. In this paper we present a completely automatic system, which produces a 3D model of a head starting from simple input data (five photos and some key‐points indicated by user). The geometry is generated by extracting information from images and accordingly deforming a 3D dummy to reproduce user head features. The system proves to be fast, automatic, robust and reliable: geometric validation and preliminary assessments show that it can be accurate enough for HRTF calculation.

Abstract We introduce a GPU‐friendly technique that efficiently exploits the highly structured nature of urban environments to ensure rendering quality and interactive performance of city exploration tasks. Central to our approach is a novel discrete representation, called BlockMap, for the efficient encoding and rendering of a small set of textured buildings far from the viewer. A BlockMap compactly represents a set of textured vertical prisms with a bounded on‐screen footprint. BlockMaps are stored into small fixed size texture chunks and efficiently rendered through GPU raycasting. Blockmaps can be seamlessly integrated into hierarchical data structures for interactive rendering of large textured urban models. We illustrate an efficient output‐sensitive framework in which a visibility‐aware traversal of the hierarchy renders components close to the viewer with textured polygons and employs BlockMaps for far away geometry. Our approach provides a bounded size far distance representation of cities, naturally scales with the improving shader technology, and outperforms current state of the art approaches. Its efficiency and generality is demonstrated with the interactive exploration of a large textured model of the city of Paris on a commodity graphics platform.

The multi triangulation framework (MT) is a very general approach for managing adaptive resolution in triangle meshes. The key idea is arranging mesh fragments at different resolution in a directed acyclic graph (DAG) which encodes the dependencies between fragments, thereby encompassing a wide class of multiresolution approaches that use hierarchies or DAGs with predefined topology. On current architectures, the classic MT is however unfit for real-time rendering, since DAG traversal costs vastly dominate raw rendering costs. In this paper, we redesign the MT framework in a GPU friendly fashion, moving its granularity from triangles to precomputed optimized triangle patches. The patches can be conveniently tri-stripped and stored in secondary memory to be loaded on demand, ready to be sent to the GPU using preferential paths. In this manner, central memory only contains the DAG structure and CPU workload becomes negligible. The major contributions of this work are: a new out-of-core multiresolution framework, that, just like the MT, encompasses a wide class of multiresolution structures; a robust and elegant way to build a well conditioned MT DAG by introducing the concept of V-partitions, that can encompass various state of the art multiresolution algorithms; an efficient multithreaded rendering engine and a general subsystem for the external memory processing and simplification of huge meshes.

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.

Data coming from complex simulation models reach easily dimensions much greater than available computational resources. Visualization of such data still represents the most intuitive and effective tool for scientific inspection of simulated phenomena. To ease this process several techniques have been adopted mainly concerning the use of hierarchical multi-resolution representations. In this paper we present the implementation of a hierarchical indexing schema for multiresolution data tailored to overwork the computational power of distributed environments.

Although in recent years the 3D-scanning field has reached a good level of maturity, it is still far from being perceived by common users as a 3D-photography approach, as simple as standard photography is. The main reason for that is that obtaining good 3D models without human intervention is still very hard. In particular, two problems remain open: automatic registration of single shots and planning of the acquisition session. In this paper we address the second issue and propose a solution to improve the coverage of automatically acquired objects. Rather than searching for the next-best-view in order to minimise the number of acquisitions, we propose a simple and easy-to-implement algorithm limiting our scope to closing gaps (i.e. filling unsampled regions) in roughly acquired models. The idea is very simple: detect holes in the current model and cluster their estimated normals in order to determine new views. Some results are shown to support our approach.

We describe an efficient technique for out-of-core construction and accurate view-dependent visualization of very large surface models. The method uses a regular conformal hierarchy of tetrahedra to spatially partition the model. Each tetrahedral cell contains a precomputed simplified version of the original model, represented using cache coherent indexed strips for fast rendering. The representation is constructed during a fine-to-coarse simplification of the surface contained in diamonds (sets of tetrahedral cells sharing their longest edge). The construction preprocess operates out-of-core and parallelizes nicely. Appropriate boundary constraints are introduced in the simplification to ensure that all conforming selective subdivisions of the tetrahedron hierarchy lead to correctly matching surface patches. For each frame at runtime, the hierarchy is traversed coarse-to-fine to select diamonds of the appropriate resolution given the view parameters. The resulting system can interatively render high quality views of out-of-core models of hundreds of millions of triangles at over 40Hz (or 70M triangles/s) on current commodity graphics platforms.

Valuable 3D graphical models, such as high-resolution digital scans of cultural heritage objects, may require protection to prevent piracy or misuse, while still allowing for interactive display and manipulation by a widespread audience. We have investigated techniques for protecting 3D graphics content, and we have developed a remote rendering system suitable for sharing archives of 3D models while protecting the 3D geometry from unauthorized extraction. The system consists of a 3D viewer client that includes low-resolution versions of the 3D models, and a rendering server that renders and returns images of high-resolution models according to client requests. The server implements a number of defenses to guard against 3D reconstruction attacks, such as monitoring and limiting request streams, and slightly perturbing and distorting the rendered images. We consider several possible types of reconstruction attacks on such a rendering server, and we examine how these attacks can be defended against without excessively compromising the interactive experience for non-malicious users.

In this paper, we address the problem of the efficient visualization of large irregular volume data sets by exploiting a multiresolution model based on tetrahedral meshes. Multiresolution models, also called Level-Of-Detail (LOD) models, allow encoding the whole data set at a virtually continuous range of different resolutions. We have identified a set of queries for extracting meshes at variable resolution from a multiresolution model, based on field values, domain location, or opacity of the transfer function. Such queries allow trading off between resolution and speed in visualization. We define a new compact data structure for encoding a multiresolution tetrahedral mesh built through edge collapses to support selective refinement efficiently and show that such a structure has a storage cost from 3 to 5.5 times lower than standard data structures used for tetrahedral meshes. The data structures and variable resolution queries have been implemented together with state-of-the art visualization techniques in a system for the interactive visualization of three-dimensional scalar fields defined on tetrahedral meshes. Experimental results show that selective refinement queries can support interactive visualization of large data sets.

We describe an efficient technique for out-of-core management and interactive rendering of planet sized textured terrain surfaces. The technique, called planet-sized batched dynamic adaptive meshes (P-BDAM), extends the BDAM approach by using as basic primitive a general triangulation of points on a displaced triangle. The proposed framework introduces several advances with respect to the state of the art: thanks to a batched host-to-graphics communication model, we outperform current adaptive tessellation solutions in terms of rendering speed; we guarantee overall geometric continuity, exploiting programmable graphics hardware to cope with the accuracy issues introduced by single precision floating points; we exploit a compressed out of core representation and speculative prefetching for hiding disk latency during rendering of out-of-core data; we efficiently construct high quality simplified representations with a novel distributed out of core simplification algorithm working on a standard PC network.

In this paper we propose a new method for the creation of normal maps for recovering the detail on simplified meshes and a set of objective techniques to metrically evaluate the quality of different recovering techniques. The proposed techniques, that automatically produces a normal-map texture for a simple 3D model that "imitates" the high frequency detail originally present in a second, much higher resolution one, is based on the computation of per-texel visibility and self-occlusion information. This information is used to define a point-to-point correspondence between simplified and hires meshes. Moreover, we introduce a number of criteria for measuring the quality (visual or otherwise) of a given mapping method, and provide efficient algorithms to implement them. Lastly, we apply them to rate different mapping methods, including the widely used ones and the new one proposed here.

Abstract This paper describes an efficient technique for out‐of‐core rendering and management of large textured terrainsurfaces. The technique, called Batched Dynamic Adaptive Meshes (BDAM), is based on a paired tree structure:a tiled quadtree for texture data and a pair of bintrees of small triangular patches for the geometry. These smallpatches are TINs and are constructed and optimized off‐line with high quality simplification and tristrippingalgorithms. Hierarchical view frustum culling and view‐dependent texture and geometry refinement is performedat each frame through a stateless traversal algorithm. Thanks to the batched CPU/GPU communication model,the proposed technique is not processor intensive and fully harnesses the power of current graphics hardware.Both preprocessing and rendering exploit out‐of‐core techniques to be fully scalable and to manage large terraindatasets. Categories and Subject Descriptors (according to ACM CCS): I.3.3 [Computer Graphics]: Picture and Image Generation;I.3.7 [Computer Graphics]: Three‐Dimensional Graphics and Realism.

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 recent evolution of graphics technology makes it possible to manage very complex models on inexpensive platforms. These impressive rendering capabilities should be paired with detailed and accurate digital models. The construction of high quality 3D models is made easier by the increasing diffusion of automatic 3D measuring devices (often called 3D scanners). These allow to build highly accurate models of real 3D objects in a cost- and time-effective manner. The talk will present the capabilities of this technology focusing mainly on a particular application context: the acquisition of Cultural Heritage artifacts. The peculiar requirements of this domain (high accuracy in the acquisition of both shape and surface appearance, expected low cost and easiness of use of the tools) make it a perfect application example. This talk aims also at presenting and discussing the main issues in the acquisition of accurate 3D models, together with some limitations of current hardware and software tools. Some examples of the results of current projects will be shown.

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.

We present a new technique to render in real time objects which have part of their high frequency geometric detail encoded in bump maps. It is based on the quantization of normal‐maps, and achieves excellent result both in rendering time and rendering quality, with respect to other alternative methods. The method proposed also allows to add many interesting visual effects, even for object with large bumb maps, including non‐s rendering, chrome effects, shading under multiple lights, rendering of different materials within a single object, specular reflections and others. Moreover, the implementation of the method is not complex and can be eased by software reuse.

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.

This paper presents a new tool, Metro, designed to compensate for a deficiency in many simplification methods proposed in literature. Metro allows one to compare the difference between a pair of surfaces (e.g. a triangulated mesh and its simplified representation) by adopting a surface sampling approach. It has been designed as a highly general tool, and it does no assumption on the particular approach used to build the simplified representation. It returns both numerical results (meshes areas and volumes, maximum and mean error, etc.) and visual results, by coloring the input surface according to the approximation error.

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.

Abstract In this paper the design of a visual program editor and its specification using formal grammars are discussed. We consider an environment to specify, analyse and execute visual programs for a Geographical Information System (GIS). The lack of sophisticated user interfaces is one of the major drawbacks to Geographical Information Systems, particularly for people without a sound background in computer science. The use of a visual language approach is useful in order to hide the plethora of basic GIS functions, while providing ready‐ to‐use tools to solve users' tasks. The visual environment provides users with higher level interfaces; it is based on the module concept, which is conceived as a software building block that implements a solution to a general basic task and is presented to the user through an interactive frame. Complex GIS queries can be carried out by interconnecting modules into flow networks, using a direct manipulation approach.

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.

Abstract In designing graphical workstations for high‐level performance presentations of graphical models, the main goal nowadays is to perform some effective real‐time traversal and rendering of data. In this paper we present a reference model of parallel processing for graphics, taking into account the main aspects of colour rendering of solid hierarchical shapes; i.e., traversal of structures, hidden surfaces removal, shadow identification and light models. In particular, a parallel design of the main graphical algorithms is presented. Three abstract machines are proposed, designed respectively for data structure traversing, for depth ordering and shadows computation and finally for shape merging and screen processing. Such abstract machines, internally parallel, may be combined in various ways to define different physical architectures. CR Categories and Subject Descriptors : C.1.2 [Multiple Data Stream Architectures] MIMD Processors, Parallel Processors; 1.3.2 [Computer Graphics] Graphics Systems; 1.3.3 [Computer Graphics] Picture Generation ‐Display Algorithms, Viewing Algorithms; 1.3.7 [Computer Graphics] Three Dimensional Graphics and Realism ‐ Colour, Shading, Shadowing, Visible Line/Surface I Algorithms.