Herb Voelcker and his research team laid the foundations of Solid Modelling, on which Computer-Aided Design is based. He founded the ambitious Production Automation Project, that included Constructive Solid Geometry (CSG) as the basic 3D geometric representation. CSG trees were compact and robust, saving a memory space that was scarce in those times. But the main computational problem was Boundary Evaluation: the process of converting CSG trees to Boundary Representations (BReps) with explicit faces, edges and vertices for manufacturing and visualization purposes. This paper presents some glimpses of the history and evolution of some ideas that started with Herb Voelcker. We briefly describe the path from “localization and boundary evaluation” to “localization and printing”, with many intermediate steps driven by hardware, software and new mathematical tools: voxel and volume representations, triangle meshes, and many others, observing also that in some applications, voxel models no longer require Boundary Evaluation. In this last case, we consider the current research challenges and discuss several avenues for further research.

Remote exploration of medical volume models is nowadays a challenging problem. Interactive visualization algorithms must be able to send and render in real-time the volume model at the maximum possible visual quality, while adapting to network bandwidth limitations and to hardware constraints in the client device. In this paper we present a transfer function-aware scheme for the remote interactive inspection of volume models in client-server architectures with the objectives of supporting multi-resolution, avoiding gradient computations in the client device and sending a very limited amount of information through the network. Gradient Octrees can be progressively transmitted to the clients in a strongly compact way while achieving a minimum loss of visual quality as compared to state of the art ray-casting renderings. Visual volume understanding can be complemented by showing 2D sections of the original volume data on demand.

Abstract Medical illustrations have been used for a long time for teaching and communicating information for diagnosis or surgery planning. Illustrative visualization systems create methods and tools that adapt traditional illustration techniques to enhance the result of renderings. Clipping the volume is a popular operation in volume rendering for inspecting the inner parts, though it may remove some information of the context that is worth preserving. In this paper we present a new editing technique based on the use of clipping planes, direct structure extrusion, and illustrative methods, which preserves the context by adapting the extruded region to the structures of interest of the volumetric model. We will show that users may interactively modify the clipping plane and edit the structures to highlight, in order to easily create the desired result. Our approach works with segmented volume models and non‐segmented ones. In the last case, a local segmentation is performed on‐the‐fly. We will demonstrate the efficiency and utility of our method.

Abstract In this paper, we present an efficient approach for the interactive rendering of large‐scale urban models, which can be integrated seamlessly with virtual globe applications. Our scheme fills the gap between standard approaches for distant views of digital terrains and the polygonal models required for close‐up views. Our work is oriented towards city models with real photographic textures of the building facades. At the heart of our approach is a multi‐resolution tree of the scene defining multi‐level relief impostors. Key ingredients of our approach include the pre‐computation of a small set of zenithal and oblique relief maps that capture the geometry and appearance of the buildings inside each node, a rendering algorithm combining relief mapping with projective texture mapping which uses only a small subset of the pre‐computed relief maps, and the use of wavelet compression to simulate two additional levels of the tree. Our scheme runs considerably faster than polygonal‐based approaches while producing images with higher quality than competing relief‐mapping techniques. We show both analytically and empirically that multi‐level relief impostors are suitable for interactive navigation through large urban models.

In Volume Rendering, it is difficult to simultaneously visualize interior and exterior structures. Several approaches have been developed to solve this problem, such as cut-away or exploded views. Nevertheless, in most cases, those algorithms usually require either a preprocess of the data, or an accurate determination of the region of interest, previous to data inspection.

Abstract We explore the automatic recovery of solids from their binary volumetric discretizations. In particular, we propose an approach, called Pressing, for smoothing isosurfaces extracted from binary volumes while recovering their large planar regions (flats). Pressing yields a surface that is guaranteed to contain the samples of the volume classified as interior and exclude those classified as exterior. It uses global optimization to identify flats and constrained bilaplacian smoothing to eliminate sharp features and high frequencies from the rest of the isosurface. It recovers sharp edges between flat regions and between flat and smooth regions. Hence, the resulting isosurface is usually a very accurate approximation of the original solid. Furthermore, the segmentation of the isosurface into flat and curved faces and the sharp/smooth labelling of their edges may be valuable for shape recognition, simplification, compression and various reverse engineering and manufacturing applications.

Abstract Relief impostors have been proposed as a compact and high‐quality representation for high‐frequency detail in 3D models. In this paper we propose an algorithm to represent a complex object through the combination of a reduced set of relief maps. These relief maps can be rendered with very few artifacts and no apparent deformation from any view direction. We present an efficient algorithm to optimize the set of viewing planes supporting the relief maps, and an image‐space metric to select a sufficient subset of relief maps for each view direction. Selected maps (typically three) are rendered based on the well‐known ray‐height‐field intersection algorithm implemented on the GPU. We discuss several strategies to merge overlapping relief maps while minimizing sampling artifacts and to reduce extra texture requirements. We show that our representation can maintain the geometry and the silhouette of a large class of complex shapes with no limit in the viewing direction. Since the rendering cost is output sensitive, our representation can be used to build a hierarchical model of a 3D scene.

Abstract Given a tetrahedral mesh immersed in a voxel model, we present a method to refine the mesh to reduce the discrepancy between interpolated values based on either scheme at arbitrary locations. An advantage of the method presented is that it requires few subdivisions and all decisions are made locally at each tetrahedron. We discuss the algorithm's performance and applications.

Abstract The computation of the largest planar region approximating a 3D object is an important problem with wide applications in modeling and rendering. Given a voxelization of the 3D object, we propose an efficient algorithm to solve a discrete version of this problem. The input of the algorithm is the set of grid edges connecting the interior and the exterior of the object (called sticks). Using a voting‐based approach, we compute the plane that slices the largest number of sticks and is orientation‐compatible with these sticks. The robustness and efficiency of our approach rests on the use of two different parameterizations of the planes with suitable properties. The first of these is exact and is used to retrieve precomputed local solutions of the problem. The second one is discrete and is used in a hierarchical voting scheme to compute the global maximum. This problem has diverse applications that range from finding object signatures to generating simplified models. Here we demonstrate the merits of the algorithm for efficiently computing an optimized set of textured impostors for a given polygonal model. Categories and Subject Descriptors (according to ACM CCS): I.3.5 [Computer Graphics]: Computational Geometry and Object Modeling

Abstract We present a novel Cell‐To‐Cell Visibility (C2CV) algorithm, which given two polyhedra, AandBand a connectedand oriented manifold triangle mesh, S offers a simple, fast and conservative test for detecting when A and B areoccluded from each other by S. Previously disclosed C2CV algorithms either relied on costly occlusion fusion orwere restricted to convex or “apparently convex” occluders, which makes them inappropriate for scenes wherepotential occluders are arbitrary triangulated surfaces, such as the body of a car or a portion of a terrain. Thesimplicity of our C2CV algorithm, named ShieldTester, stems from a new Occlusion Theorem, introduced herewhich permits to establish occlusion by computing the intersection of S with a single ray from a vertex ofAtoa vertex ofB. ShieldTester may be used to establish that pairs of cells in a subdivision of space are hidden fromeach other by a relatively large surface occluder, so that when the viewer is in one cell, the objects in the othercell need not be displayed. Categories and Subject Descriptors (according to ACM CCS): I.3.3 [Computer Graphics]: Computational Geometryand Object Modeling: Occlussion Culling, Visibility Test, Triangle Meshes

Most visibility culling algorithms require convexity of occluders. Occluder synthesis algorithms attempt to construct large convex occluders inside bulky non-convex sets. Occluder fusion algorithms generate convex occluders that are contained in the umbra cast by a group of objects given an area light. In this paper we prove that convexity requirements can be shifted from the occluders to their umbra with no loss of efficiency, and use this property to show how some special non-planar, non-convex closed polylines that we call “hoops” can be used to compute occlusion efficiently for objects that have no large interior convex sets and were thus rejected by previous approaches.

The 3D reconstruction of the cerebral vascular anatomy can greatly improve the diagnosis of vascular pathologies, such as embolisms and haemorrhages. This paper presents a new method for the automatic extraction of the blood vessels surface and the labelling of its features, specifically branching, aneurysms and stenoses. The method works with segmented magnetic resonance angiography images. It extracts a discrete medial axis transform from the stacked images and vectorizes it. During the vectorization process, the features are detected and labelled automatically. The final output is a labelled continuous medial axis transform representation of the vascular tree suitable for interactive visualizations and navigations, along with 3D geometrical and topological queries.

Medical imaging is constantly advancing due to technological improvements in both data gathering devices and data processing of their output. In this progress the heart presents special demands because of its incessant and brisk movement, and intrinsic characteristics. In this paper we briefly survey techniques that can be used to construct a three-dimensional model of a heart, and discuss our approach within an ongoing effort to produce accurate models of a patient's beating heart for both diagnosis and medical training.

Occlusion culling and level‐of‐detail rendering have become two powerful tools for accelerating the handling of very large models in real‐time visualization applications. We present a framework that combines both techniques to improve rendering times. Classical occlusion culling algorithms compute potentially visible sets (PVS), which are supersets of the sets of visible polygons. The novelty of our approach is to estimate the degree of visibility of each object of the PVS using synthesized coarse occluders. This allows to arrange the objects of each PVS into several Hardly‐Visible Sets (HVS) with similar occlusion degree. According to image accuracy and frame rate requirements, HVS provide a way to avoid sending to the graphics pipeline those objects whose pixel contribution is low due to partial occlusion. The image error can be bounded by the user at navigation time. On the other hand, as HVS offer a tighter estimation of the pixel contribution for each scene object, it can be used for a more convenient selection of the level‐of‐detail at which objects are rendered. In this paper, we describe the new framework technique, provide details of its implementation using a visibility octree as the chosen occlusion culling data structure and show some experimental results on the image quality.

An interactive cerebral blood vessel exploration system is described. It has been designed on the basis of neurosurgeons' requirements in order to assist them in the diagnosis of vascular pathologies. The system is based on the construction of a symbolic model of the vascular tree, with automatic identification and labelling of vessel bifurcations, aneurysms and stenoses. It provides several types of visualization: individual MRA (magnetic resonance angiography) slices, MIP (maximum intensity projection), shaded rendering, symbolic schemes and surface reconstruction.

Besides the most widely used models in the Geometric Modeling Systems, Constructive Solid Geometry (CSG) and Boundary Representations (BR), Octtrees have appeared as an alternative representation scheme which is particularly well suited for the solid boolean operation algorithms. Extended Octtrees, which incorporates three additional node types containing part of the surface of the object, are much more compact and allow the exact representation of plane faced objects, while supporting also low complexity algorithms for boolean operations. Due to the limitations of the two main models, CSG and Boundary Representation , a number of Hybrid Systems have appeared, which support both schemes and perform every operation in the most suitable model. However, algorithms for the boundary evaluation of CSG trees are complex, and at the moment little is known on algorithms for the inverse conversion, from BR to CSG. In the present paper, the use of the Extended Octtree model as an intermediate tool in the conversions between. CSG trees and BR is studied. In the case of CSG trees build from primitives with plane faces, an algorithm for the conversion from the CSG model to the Extended Octtree representation is presented. Its complexity is linear with respect to the numbe of nodes in the Octtree. The use of this algorithm in model-to-model conversions is discussed, together with the BR to Extended Octtree and Extended Octtree to BR conversion algorithms, that present also linear complexity with respect to the total number of nodes.

Abstract Geometric Modellers based on a Boundary Representation scheme are well suited for display operations, but boolean operations require algorithms with quadratic complexity. Using a class of extended octtrees which is presented here, boolean operations become linear, while exact recomputation of the boundary model in the case of polyhedral objects is possible, and memory requirements are less than in classical octtree encodings. Some bounds on the memory savings are given and discussed. The DMI system, a Geometric Modeller based on a hybrid model Boundary ‐ Extended Octtrees, is presented, discussing the main operations and the interface between both models. Some modelling examples are shown. Finally, a generalization of the extended octtree encoding which allows the exact representation of objects limited by sculptured surfaces is presented.

In the last few years, octrees have been proposed for the representation of solids in Geometric Modelling systems. Using them, boolean operations are simple; however, they use a great amount of memory and it is very difficult to obtain smooth graphical outputs from them or to recompute the boundary model. In the present paper, a new class of Octtrees is introduced, which allows face, edge and vertex nodes as well as the classical white, black and grey nodes. The required amount of storage is less than in the case of classical Octtrees, and boolean operations are also simple. Futhermore, there exists an algorithm for the exact recomputation of the boundary model.

Quadtree representation of two-dimensional objects is performed with a tree that describes the recursive subdivision of the more complex parts of a picture until the desired resolution is reached. At the end, all the leaves of the tree are square cells that lie completely inside or outside the object. There are two great disadvantages in the use of quadtrees as a representation scheme for objects in geometric modeling system: The amount of memory required for polygonal objects is too great, and it is difficult to recompute the boundary representation of the object after some Boolean operations have been performed. In the present paper a new class of quadtrees, in which nodes may contain zero or one edge, is introduced. By using these quadtrees, storage requirements are reduced and it is possible to obtain the exact backward conversion to boundary representation. Algorithms for the generation of the quadtree, Boolean operations, and recomputation of the boundary representation are presented, and their complexities in time and space are discussed. Three-dimensional algorithms working on octrees are also presented. Their use in the geometric modeling of three-dimensional polyhedral objects is discussed.