Abstract Image-based 3D reconstruction is a powerful method for accurately reconstructing an object’s geometry and texture from images. A crucial factor for the accuracy and completeness of the resulting reconstructed model is the choice of poses for capturing images, which is called view planning. One possible view planning strategy uses an iterative feedback loop that switches between planning poses and an incremental reconstruction to autonomously digitize an object without prior knowledge. However, this approach requires identifying which parts of an object are “poorly reconstructed” and thus would benefit from being part of additional images. This work explores the use of point cloud quality metrics to provide this feedback by comprehensively comparing a set of existing and newly introduced metrics in terms of their time-dependent behavior, similarity, and their applicability to view planning. Among the newly proposed metrics this work introduces the Reconstruction Quality Feedback (RQF), which shows a significantly improved performance in simulations when being used for view planning. The effectiveness of RQF is also demonstrated for real objects on an autonomous robotic 3D digitization system.

Abstract Interactive deformation via control handles is essential in computer graphics for the modeling of 3D geometry. Deformation control structures include lattices for free‐form deformation and skeletons for character articulation, but this report focuses on cage‐based deformation. Cages for deformation control are coarse polygonal meshes that encase the to‐be‐deformed geometry, enabling high‐resolution deformation. Cage‐based deformation enables users to quickly manipulate 3D geometry by deforming the cage. Due to their utility, cage‐based deformation techniques increasingly appear in many geometry modeling applications. For this reason, the computer graphics community has invested a great deal of effort in the past decade and beyond into improving automatic cage generation and cage‐based deformation. Recent advances have significantly extended the practical capabilities of cage‐based deformation methods. As a result, there is a large body of research on cage‐based deformation. In this report, we provide a comprehensive overview of the current state of the art in cage‐based deformation of 3D geometry. We discuss current methods in terms of deformation quality, practicality, and precomputation demands. In addition, we highlight potential future research directions that overcome current issues and extend the set of practical applications. In conjunction with this survey, we publish an application to unify the most relevant deformation methods. Our report is intended for computer graphics researchers, developers of interactive geometry modeling applications, and 3D modeling and character animation artists.

Abstract Neural radiance fields (NeRFs) have revolutionized novel view synthesis, leading to an unprecedented level of realism in rendered images. However, the reconstruction quality of NeRFs suffers significantly from out-of-focus regions in the input images. We propose NeRF-FF, a plug-in strategy that estimates image masks based on Focus Frustums (FFs), i.e., the visible volume in the scene space that is in-focus. NeRF-FF enables a subsequently trained NeRF model to omit out-of-focus image regions during the training process. Existing methods to mitigate the effects of defocus blurred input images often leverage dynamic ray generation. This makes them incompatible with the static ray assumptions employed by runtime-performance-optimized NeRF variants, such as Instant-NGP, leading to high training times. Our experiments show that NeRF-FF outperforms state-of-the-art approaches regarding training time by two orders of magnitude—reducing it to under 1 min on end-consumer hardware—while maintaining comparable visual quality.

Abstract Neural Radiance Fields have revolutionized Novel View Synthesis by providing impressive levels of realism. However, in most in‐the‐wild scenes they suffer from floater artifacts that occur due to sparse input images or strong view‐dependent effects. We propose an approach that uses neighborhood based clustering and a consistency metric on NeRF models trained on different scene scales to identify regions that contain floater artifacts based on Instant‐NGPs multiscale occupancy grids. These occupancy grids contain the position of relevant optical densities in the scene. By pruning the regions that we identified as containing floater artifacts, they are omitted during the rendering process, leading to higher quality resulting images. Our approach has no negative runtime implications for the rendering process and does not require retraining of the underlying Multi Layer Perceptron. We show on a qualitative base, that our approach is suited to remove floater artifacts while preserving most of the scenes relevant geometry. Furthermore, we conduct a comparison to state‐of‐the‐art techniques on the Nerfbusters dataset, that was created with measuring the implications of floater artifacts in mind. This comparison shows, that our method outperforms currently available techniques. Our approach does not require additional user input, but can be be used in an interactive manner. In general, the presented approach is applicable to every architecture that uses an explicit representation of a scene's occupancy distribution to accelerate the rendering process.

Structure from Motion (SfM) plays a crucial role in unstructured capturing. While images are usually taken by perspective cameras, orthographic camera projections do not suffer from the foreshortening effect, that leads to varying capturing quality in image regions. Most contributions to orthographic image SfM assume a perspective setup with nearly infinite focal length. These assumptions lead to potentially sub-optimal camera pose estimation. Therefore, we propose a SfM pipeline that is optimized for orthographically projected images. For this, we estimate initial camera poses using the factorization method by Tomasi and Kanade. These poses are further refined by a specialized bundle adjustment implementation for orthographic projections. The proposed pipeline surpasses the precision of state-of-the-art work by an order of magnitude, while consuming considerably less computational resources.

Abstract Memory performance is a crucial bottleneck in many GPGPU applications, making optimizations for hardware and software mandatory. While hardware vendors already use highly efficient caching architectures, software engineers usually have to organize their data accordingly in order to efficiently make use of these, requiring deep knowledge of the actual hardware. In this paper we present a novel technique for fine‐grained memory profiling that simulates the whole pipeline of memory flow and finally accumulates profiling values in a way that the user retains information about the potential region in the GPU program by showing these values separately for each allocation. Our memory simulator turns out to outperform state‐of‐the‐art memory models of NVIDIA architectures by a magnitude of 2.4 for the L1 cache and 1.3 for the L2 cache, in terms of accuracy. Additionally, we find our technique of fine grained memory profiling a useful tool for memory optimizations, which we successfully show in case of ray tracing and machine learning applications.

Abstract Mesh optimization is essential to enable sufficient element quality for numerical methods such as the finite element method (FEM). Depending on the required accuracy and geometric detail, a mesh with many elements is necessary to resolve small-scale details. Sequential optimization of large meshes often imposes long run times. This is especially an issue for Delaunay-based methods. Recently, the notion of harmonic triangulations [1] was evaluated for tetrahedral meshes, revealing significantly faster run times than competing Delaunay-based methods. A crucial aspect for efficiency and high element quality is boundary treatment. We investigate directional derivatives for boundary treatment and massively parallel GPUs for mesh optimization. Parallel flipping achieves compelling speedups by up to $$318\times $$ 318 × . We accelerate harmonic mesh optimization by $$119\times $$ 119 × for boundary preservation and $$78\times $$ 78 × for moving every boundary vertex, while producing superior mesh quality.

S.271-277

Abstract Large sparse matrices with compound entries, i.e. complex and quaternionic matrices as well as matrices with dense blocks, are a core component of many algorithms in geometry processing, physically based animation and other areas of computer graphics. We generalize several matrix layouts and apply joint schedule and layout autotuning to improve the performance of the sparse matrix‐vector product on massively parallel graphics processing units. Compared to schedule tuning without layout tuning, we achieve speedups of up to 5.5 × . In comparison to cuSPARSE, we achieve speedups of up to 4.7 × .

Abstract We present a novel bounding volume hierarchy for GPU-accelerated direct volume rendering (DVR) as well as volumetric mesh slicing and inside-outside intersection testing. Our novel octree-based data structure is laid out linearly in memory using space filling Morton curves. As our new data structure results in tightly fitting bounding volumes, boundary markers can be associated with nodes in the hierarchy. These markers can be used to speed up all three use cases that we examine. In addition, our data structure is memory-efficient, reducing memory consumption by up to 75%. Tree depth and memory consumption can be controlled using a parameterized heuristic during construction. This allows for significantly shorter construction times compared to the state of the art. For GPU-accelerated DVR, we achieve performance gain of 8.4 $$\times $$ × –13 $$\times $$ × . For 3D printing, we present an efficient conservative slicing method that results in a 3 $$\times $$ × –25 $$\times $$ × speedup when using our data structure. Furthermore, we improve volumetric mesh intersection testing speed by 5 $$\times $$ × –52 $$\times $$ × .

We show how to overcome the single weakness of an existing fully automatic system for acquisition of spatially varying optical material behavior of real object surfaces. While the expression of spatially varying material behavior with spherical dependence on incoming light as a 4D texture (an ABTF material model) allows flexible mapping onto arbitrary 3D geometry, with photo-realistic rendering and interaction in real time, this very method of texture-like representation exposes it to common problems of texturing, striking in two disadvantages. Firstly, non-seamless textures create visible artifacts at boundaries. Secondly, even a perfectly seamless texture causes repetition artifacts due to their organised placement in large numbers over a 3D surface. We have solved both problems through our novel texture synthesis method that generates a set of seamless texture variations randomly distributed over the surface at shading time. When compared to regular 2D textures, the inter-dimensional coherence of the 4D ABTF material model poses entirely new challenges to texture synthesis, which includes maintaining the consistency of material behavior throughout the 4D space spanned by the spatial image domain and the angular illumination hemisphere. In addition, we tackle the increased memory consumption caused by the numerous variations through a fitting scheme specifically designed to reconstruct the most prominent effects captured in the material model.

The need to analyze and visualize distances between objects arises in many use cases. Although the problem to calculate the distance between two polygonal objects may sound simple, real-world scenarios with large models will always be challenging, but optimization techniques - such as space partitioning - can reduce the complexity of the average case significantly. Our contribution to this problem is a publicly available benchmark to compare distance calculation algorithms. Furthermore, we evaluated the two most important techniques (hierarchical tree structures versus grid-based approaches).

We developed a new concept to improve the efficiency of visual analysis through visual recommendations. It uses a novel eye-gaze based recommendation model that aids users in identifying interesting time-series patterns. Our model combines time-series features and eye-gaze interests, captured via an eye-tracker. Mouse selections are also considered. The system provides an overlay visualization with recommended patterns, and an eye-history graph, that supports the users in the data exploration process. We conducted an experiment with 5 tasks where 30 participants explored sensor data of a wind turbine. This work presents results on pre-attentive features, and discusses the precision/recall of our model in comparison to final selections made by users. Our model helps users to efficiently identify interesting time-series patterns.

Labeling data instances is an important task in machine learning and visual analytics. Both fields provide a broad set of labeling strategies, whereby machine learning (and in particular active learning) follows a rather model-centered approach and visual analytics employs rather user-centered approaches (visual-interactive labeling). Both approaches have individual strengths and weaknesses. In this work, we conduct an experiment with three parts to assess and compare the performance of these different labeling strategies. In our study, we (1) identify different visual labeling strategies for user-centered labeling, (2) investigate strengths and weaknesses of labeling strategies for different labeling tasks and task complexities, and (3) shed light on the effect of using different visual encodings to guide the visual-interactive labeling process. We further compare labeling of single versus multiple instances at a time, and quantify the impact on efficiency. We systematically compare the performance of visual interactive labeling with that of active learning. Our main findings are that visual-interactive labeling can outperform active learning, given the condition that dimension reduction separates well the class distributions. Moreover, using dimension reduction in combination with additional visual encodings that expose the internal state of the learning model turns out to improve the performance of visual-interactive labeling.

In 3D object retrieval, additional knowledge like user input, classification information or database dependent configured parameters are rarely available in real scenarios. For example, meta data about 3D objects is seldom if the objects are not within a well-known evaluation database.

In the application of 3D object retrieval we search for 3D objects similar to a given query object. When a user searches for a certain class of objects like 'planes' the results can be unsatisfying: Many object variations are possible for a single class and not all of them are covered with one or a few example objects. We propose a meta model representation which corresponds to a procedural model with meta-parameters. Changing the meta-parameters leads to different variations of a 3D object. For the meta model generation a single object is constructed with a modeling tool. We automatically extract a procedural representation of the object. By inserting meta-parameters we generate our meta model. The meta model defines a whole object class. The user can choose a meta model and search for all objects similar to any instance of the meta model to retrieve all objects of a certain class from a 3D object database. We show that the retrieval precision is significantly improved using the meta model as retrieval query.

When creating immersive interactive virtual worlds, it is important to not only provide plausible visuals, but also to allow the user to interact with the virtual scene in a natural way. While rigid-body physics simulations are widely used to provide basic interaction, realistic soft-body deformations of virtual objects are challenging and therefore typically not offered.We present a client-server architecture for interactive physics-based deformation, which makes it possible to add physically accurate response to interaction to any virtual environment. The architecture is highly flexible, can be used from any web enabled client, and facilitates synchronization of computed deformations across multiple users and devices.

In this paper, we present a novel approach for a tighter integration of 3D modeling and physically-based simulation. Instead of modeling 3D objects as surface models, we use a volumetric subdivision representation. Volumetric modeling operations allow designing 3D objects in similar ways as with surface-based modeling tools, while automatic checks and modifications of inner control points ensure consistency during the design process. Encoding the volumetric information already in the design mesh drastically simplifies and speeds up the mesh generation process for simulation. The transition between design, simulation and back to design is consistent and computationally cheap. Since the subdivision and mesh generation can be expressed as a precomputable matrix-vector multiplication, iteration times can be greatly reduced compared to common modeling and simulation setups. Therefore, this approach is especially well suited for early-stage modeling or optimization use cases, where many geometric changes are made in a short time and their physical effect on the model has to be evaluated frequently. To test our approach, we created, simulated and adapted several 3D models. We measured and evaluated the timings for generating and applying the matrices for different subdivision levels. Additionally, we computed several characteristic factors for mesh quality and mesh consistency. For comparison, we analyzed the tetrahedral meshing functionality offered by CGAL for similar numbers of elements. For changing topology, our implicit meshing approach proves to be up to 70 times faster than creating the tetrahedral mesh only based on the outer surface. Without changing the topology and by precomputing the matrices, we achieve a speed-up of up to 2800, as all the required information is already available.

The rising quantity and complexity of data creates a need to design and optimize data processing pipelines-the set of data processing steps, parameters and algorithms that perform operations on the data. Visualization can support this process but, although there are many examples of systems for visual parameter analysis, there remains a need to systematically assess users' requirements and match those requirements to exemplar visualization methods. This article presents a new characterization of the requirements for pipeline design and optimization. This characterization is based on both a review of the literature and first-hand assessment of eight application case studies. We also match these requirements with exemplar functionality provided by existing visualization tools. Thus, we provide end-users and visualization developers with a way of identifying functionality that addresses data processing problems in an application. We also identify seven future challenges for visualization research that are not met by the capabilities of today's systems.

Naturalness of the mid-air interaction interface for virtual assembly and shape modeling is important. In order to design an interface perceived as "natural" by most people, common behaviors and mental patterns for mid-air interaction of people have to be recognized, which is an area merely explored yet. This paper serves this purpose of understanding the users' mental interaction models, in order to provide standards and recommendation for devising a natural virtual interaction interface. We tested three kinds of tasks --- manipulating tasks, deforming tasks and tool-based operating tasks on 16 participants. We have found that: 1) different features of mental models were observed for different types of tasks. Interaction techniques should be designed to match these features; 2) virtual hand self-avatar helps estimate size of virtual objects, as well as helps plan and visualize the complex process and procedures of a task, which is especially helpful for tool-based tasks; 3) bimanual interaction is witnessed as a dominant interaction mode preferred by the majority; 4) natural gestures for deforming tasks always reflect forces exerted. These suggestions are useful for designing a midair interaction interface matching users' mental models.

Creation of procedural 3D building models can significantly lessen the costs of modeling, since it allows generating a variety of similar shapes from one procedural description. The common field of application for procedural modeling is modeling of straight building facades, which are very well suited for shape grammars – a special kind of procedural modeling system. In order to generate round building geometry, we present a way to setup different coordinate systems in shape grammars. Besides Cartesian, these are primarily cylindrical and spherical coordinate systems for generation of structures like towers or domes, that can procedurally adapt to different dimensions and parameters. The users can apply common splitting idioms from shape grammars in their familiar way, for creating round instead of straight geometry.

Abstract We present a novel multigrid scheme based on a cut‐cell formulation on regular staggered grids which generates compatible systems of linear equations on all levels of the multigrid hierarchy. This geometrically motivated formulation is derived from a finite volume approach and exhibits an improved rate of convergence compared to previous methods. Existing fluid solvers with voxelized domains can directly benefit from this approach by only modifying the representation of the non‐fluid domain. The necessary building blocks are fully parallelizable and can therefore benefit from multi‐ and many‐core architectures.

While the growing demand for new building models contained in virtual worlds, games, and movies, makes the easy and fast creation of modifiable models more and more important, 3D modeling of buildings can be a tedious task due to their sometimes complex geometry. For historic buildings, especially the roofs can be challenging. We present a new method of combining simple building solids to form more complex buildings, and give an emphasis on the blending of roof faces. This can be integrated in common pipelines for procedural modeling of buildings and will bring more expressiveness than existing methods.

With the current state of video games growing in scale, manual content creation may no longer be feasible in the future. Split grammars are a promising technology for large scale procedural generation of urban structures, which are very common in video games. Buildings with curved parts, however, can currently only be approximated by static pre-modeled assets, and rules apply only to planar surface parts. We present an extension to current split grammar systems that allows the generation of curved architecture through free-form deformations that can be introduced at any level in a grammar. Further subdivision rules can then adapt to these deformations to maintain length constraints, and repetitions can adjust to more or less space.

A procedural model is a script, which generates a geometric object. The script's input parameters offer a simple way to specify and modify the scripting output. Due to its algorithmic character, a procedural model is perfectly suited to describe geometric shapes with well-organized structures and repetitive forms. In this paper, we interpret a generative script as a function, which is nested into an objective function. Thus, the script's parameters can be optimized according to an objective. We demonstrate this approach using architectural examples: each generative script creates a building with several free parameters. The objective function is an energy-efficiency-simulation that approximates a building's annual energy consumption. Consequently, the nested objective function reads a set of building parameters and returns the energy needs for the corresponding building. This nested function is passed to a minimization and optimization process. Outcome is the best building (within the family of buildings described by its script) concerning energy-efficiency. Our contribution is a new way of modeling. The generative approach separates design and engineering: the complete design is encoded in a script and the script ensures that all parameter combinations (within a fixed range) generate a valid design. Then the design can be optimized numerically.

Using Head-up-Displays (HUD) for Augmented Reality requires to have an accurate internal model of the image generation process, so that 3D content can be visualized perspectively correct from the viewpoint of the user. We present a generic and cost-effective camera-based calibration for an automotive HUD which uses the windshield as a combiner. Our proposed calibration model encompasses the view-independent spatial geometry, i.e. the exact location, orientation and scaling of the virtual plane, and a view-dependent image warping transformation for correcting the distortions caused by the optics and the irregularly curved windshield. View-dependency is achieved by extending the classical polynomial distortion model for cameras and projectors to a generic five-variate mapping with the head position of the viewer as additional input. The calibration involves the capturing of an image sequence from varying viewpoints, while displaying a known target pattern on the HUD. The accurate registration of the camera path is retrieved with state-of-the-art vision-based tracking. As all necessary data is acquired directly from the images, no external tracking equipment needs to be installed. After calibration, the HUD can be used together with a head-tracker to form a head-coupled display which ensures a perspectively correct rendering of any 3D object in vehicle coordinates from a large range of possible viewpoints. We evaluate the accuracy of our model quantitatively and qualitatively.

Abstract We present graphics processing unit (GPU) data structures and algorithms to efficiently solve sparse linear systems that are typically required in simulations of multi‐body systems and deformable bodies. Thereby, we introduce an efficient sparse matrix data structure that can handle arbitrary sparsity patterns and outperforms current state‐of‐the‐art implementations for sparse matrix vector multiplication. Moreover, an efficient method to construct global matrices on the GPU is presented where hundreds of thousands of individual element contributions are assembled in a few milliseconds. A finite‐element‐based method for the simulation of deformable solids as well as an impulse‐based method for rigid bodies are introduced in order to demonstrate the advantages of the novel data structures and algorithms. These applications share the characteristic that a major computational effort consists of building and solving systems of linear equations in every time step. Our solving method results in a speed‐up factor of up to 13 in comparison to other GPU methods.

In this paper, we describe a multimodal brain-computer interface (BCI) experiment, situated in a highly immersive CAVE. A subject sitting in the virtual environment controls the main character of a virtual reality game: a penguin that slides down a snowy mountain slope. While the subject can trigger a jump action via the BCI, additional steering with a game controller as a secondary task was tested. Our experiment profits from the game as an attractive task where the subject is motivated to get a higher score with a better BCI performance. A BCI based on the so-called brain switch was applied, which allows discrete asynchronous actions. Fourteen subjects participated, of which 50% achieved the required performance to test the penguin game. Comparing the BCI performance during the training and the game showed that a transfer of skills is possible, in spite of the changes in visual complexity and task demand. Finally and most importantly, our results showed that the use of a secondary motor task, in our case the joystick control, did not deteriorate the BCI performance during the game. Through these findings, we conclude that our chosen approach is a suitable multimodal or hybrid BCI implementation, in which the user can even perform other tasks in parallel.

High-quality urban reconstruction requires more than multi-view reconstruction and local optimization. The structure of facades depends on the general layout, which has to be optimized globally. Shape grammars are an established method to express hierarchical spatial relationships, and are therefore suited as representing constraints for semantic facade interpretation. Usually inference uses numerical approximations, or hard-coded grammar schemes. Existing methods inspired by classical grammar parsing are not applicable on real-world images due to their prohibitively high complexity. This work provides feasible generic facade reconstruction by combining low-level classifiers with mid-level object detectors to infer an irregular lattice. The irregular lattice preserves the logical structure of the facade while reducing the search space to a manageable size. We introduce a novel method for handling symmetry and repetition within the generic grammar. We show competitive results on two datasets, namely the Paris 2010 and the Graz 50. The former includes only Hausmannian, while the latter includes Classicism, Biedermeier, Historicism, Art Nouveau and post-modern architectural styles.

A personal computer can be considered as a one-node heterogeneous cluster that simultaneously processes several application tasks. It can be composed by, for example, asymmetric CPU and GPUs. This way, a high-performance heterogeneous platform is built on a desktop for data intensive engineering calculations. In our perspective, a workload distribution over the Processing Units (PUs) plays a key role in such systems. This issue presents challenges since the cost of a task at a PU is non-deterministic and can be affected by parameters not known a priori. This paper presents a context-aware runtime and tuning system based on a compromise between reducing the execution time of engineering applications - due to appropriate dynamic scheduling - and the cost of computing such scheduling applied on a platform composed of CPU and GPUs. Results obtained in experimental case studies are encouraging and a performance gain of 21.77% was achieved in comparison to the static assignment of all tasks to the GPU.

Abstract The analysis of large graphs plays a prominent role in various fields of research and is relevant in many important application areas. Effective visual analysis of graphs requires appropriate visual presentations in combination with respective user interaction facilities and algorithmic graph analysis methods. How to design appropriate graph analysis systems depends on many factors, including the type of graph describing the data, the analytical task at hand and the applicability of graph analysis methods. The most recent surveys of graph visualization and navigation techniques cover techniques that had been introduced until 2000 or concentrate only on graph layouts published until 2002. Recently, new techniques have been developed covering a broader range of graph types, such as time‐varying graphs. Also, in accordance with ever growing amounts of graph‐structured data becoming available, the inclusion of algorithmic graph analysis and interaction techniques becomes increasingly important. In this State‐of‐the‐Art Report, we survey available techniques for the visual analysis of large graphs. Our review first considers graph visualization techniques according to the type of graphs supported. The visualization techniques form the basis for the presentation of interaction approaches suitable for visual graph exploration. As an important component of visual graph analysis, we discuss various graph algorithmic aspects useful for the different stages of the visual graph analysis process. We also present main open research challenges in this field.

GPUs (Graphics Processing Units) have become one of the main co-processors that contributed to desktops towards high performance computing. Together with multi-core CPUs, a powerful heterogeneous execution platform is built for massive calculations. To improve application performance and explore this heterogeneity, a distribution of workload in a balanced way over the PUs (Processing Units) plays an important role for the system. However, this problem faces challenges since the cost of a task at a PU is non-deterministic and can be influenced by several parameters not known a priori, like the problem size domain. We present a comparison of iterative SLE (Systems of Linear Equations) solvers, used in many scientific and engineering applications, over a heterogeneous CPU-GPUs platform and characterize scenarios where the solvers obtain better performances. A new technique to improve memory access on matrix-vector multiplication used by SLEs on GPUs is described and compared to standard implementations for CPU and GPUs. Such timing profiling is analyzed and break-even points based on the problem sizes are identified for this implementation, pointing whether our technique is faster to use GPU instead of CPU. Preliminary results show the importance of this study applied to a real-time CFD (Computational Fluid Dynamics) application with geometry modification.

For many tasks like markerless model-based camera tracking it is essential that the 3D model of a scene accurately represents the real geometry of the scene. It is therefore very important to detect deviations between a 3D model and a scene. We present an innovative approach which is based on the insight that camera tracking can not only be used for Augmented Reality visualization but also to solve the correspondence problem between 3D measurements of a real scene and their corresponding positions in the 3D model. We combine a time-of-flight camera (which acquires depth images in real time) with a custom 2D camera (used for the camera tracking) and developed an analysis-by-synthesis approach to detect deviations between a scene and a 3D model of the scene.

An extended subdivision surface (ESub) is a generalization of Catmull Clark and NURBS surfaces. Depending on the knot intervals and valences of the vertices and faces, Catmull Clark as well as NURBS patches can be generated using the extended subdivision rules. Moreover, an arbitrary choice of the knot intervals and the topology is possible. Special features like sharp edges and corners are consistently supported by setting selected knot intervals to zero or by applying special rules. Compared to the prior nonuniform rational subdivision surfaces (NURSS), the ESubs offer limit-point rules which are indispensable in many applications, for example, for computer-aided design or in adaptive visualization. The refinement and limit-point rules for our nonuniform, nonstationary scheme are obtained via a new method using local Bézier control points. With our new surface, it is possible to start with existing Catmull Clark as well as NURBS models and to continue the modeling process using the extended subdivision options.

This paper presents a protein visualization system called BioBrowser, which provides high quality images at interactive frame rates for molecules of extreme size and complexity. This is achieved by a shift in the tessellation approach: triangle meshes are not produced a priori on a 'just-in-case' basis. Instead, tessellation happens 'justin- time' given a certain camera position, image size and interaction demand. Thus, our approach is based on multiresolution meshes and on new extensions of graphics hardware. The paper shows how to reduce geometric data by using subdivision surfaces for ribbon structures and molecular surfaces and by using billboards instead of spheres consisting of triangles. It also shows how to use fragment shaders to create a three dimensional appearance and realistic sphere intersections. The combination of these approaches leads to an image quality not yet seen in interactive visualization environments for molecules of that size/complexity. All the above methods are combined to gain a high performance configurable visualization system on standard hardware.

(Semi)immersive displays like back projection walls have become widely used in various visual domains. Despite the superior image quality of 'through-the-windows VR' users are still not satisfied with the interaction capabilities - mostly due to the extra wiring for the interaction devices. This paper represents a hand gesture interaction system for a back-projection wall environment, supporting object manipulation (translation, rotation, and uniform scale) and selection tasks through the vision-tracking technique. We propose to use thimble-shaped fingertip markers made of white printing paper with a 'black light' source. Gesture parameters are calculated by 3D positions of the marked fingertips and their pinching states.

The increasing size of protein data available in Internet databases demands new fast methods of visualization. This paper introduces a novel visualization technique for molecular ribbon structures. The method is based on Combined BReps - a mesh structure defining a combination of polygonal faces and Catmull/Clark surfaces. Our technique provides high frame rates when interactively moving through structures of highest complexity as well as high quality images when the viewpoint remains static.

Gothic architecture, and especially window tracery, exhibits quite complex geometric shape configurations by combining only a few basic geometric patterns, namely circles and straight lines. They are combined using only a limited set of operations, such as intersection, offsetting, and extrusions. The reason lies in the process how these objects have been physically realized, i.e., through construction with compass and ruler. Consequently, Gothic architecture is a great, although challenging, domain for parametric modeling. We present some principles of this long-standing domain, together with some delicate details, and show how the constructions of some prototypic Gothic windows can be formalized using our Generative Modeling Language (GML). The emphasis of this procedural approach is on modularization, so that complex configurations can be obtained from combining elementary constructions. Different combinations of specific parametric features can be grouped together, which leads to the concept of styles. They permit to differentiate between the basic shape and its appearance, i.e., a particular ornamental decoration. This leads to an extremely compact representation for a whole class of shapes, which can nevertheless be quickly evaluated to obtain a connected manifold mesh of a particular window instance. The resulting mesh may also contain free-form surface parts, represented as subdivision surfaces.

The economic production and the interactive rendering of complete reconstructions of populated urban environments are technically difficult tasks. Specialized modelling tools, which exploit knowledge of the types of object being modelled by working in the application domain, can be used to create appealing virtual reconstructions quickly. At the same time, the structural information from the modeller gives valuable hints to the renderer to determine efficient interactive display strategies through the use of level-of-detail and culling techniques. Thus a modeller that knows the operator is creating houses can use this information to simplify the user interaction, guide the operator, and to create models that build in optimisations when attempting real-time rendering. In this paper we discuss the way in which polygonal and multi-resolution surface techniques can complement one another in the modelling of urban environments. We also draw more general conclusions which apply to other software systems that share the same objective.

Abstract Subdivision Surfaces as well as (interactive) ray tracing have become an important issue in computer graphics.But ray tracing of subdivision surfaces has received only little attention. We present a new approach for raytracing of subdivision surfaces. The algorithm uses a projection of the ray onto the surface and works mainly intwo dimensions along this projection. While proceeding from patch to patch, we examine the bounding volume oftheir borders: the lower the distance between ray and subdivision surface, the more refinement steps are adaptivelyapplied to the surface but only along the projection of the ray. The adaptive refinement of a patch is controlled bycurvature, size, its membership to the silhouette, and its potential contribution to the light transport. The algorithmis simple and mainly consists of elementary geometric computations. Hence it is fast and easy to implementwithout the need for elaborate preprocessing. The algorithm is robust in the sense that it deals with all features ofsubdivision surfaces like creases and corners. Categories and Subject Descripters (according to ACM CCS): I.3.7 [Computer Graphics]: Raytracing

Using object clusters for hierarchical radiosity greatly improves the efficiency and thus usability of radiosity computations. By eliminating the quadratic starting phase very large scenes containing about 100k polygons can be handled efficiently. Although the main algorithm extends rather easily to using object clusters, the creation of ‘good’ object hierarchies is a difficult task both in terms of construction time and in the way how surfaces or objects are grouped to clusters. The quality of an object hierarchy for clustering depends on its ability to accurately simulate the hierarchy of the energy flow in a given scene. Additionally it should support visibility computations by providing efficient ray acceleration techniques. In this paper we will present a new approach of building hierarchies of object clusters. Our hybrid structuring algorithm provides accuracy and speed by combining a highly optimized bounding volume hierarchy together with uniform spatial subdivisions for nodes with regular object densities. The algorithm works without user intervention and is well suited for a wide variety of scenes. First results of using these hierarchies in a radiosity clustering environment are very promising and will be presented here. The combination of very deep hierarchies (we use a binary tree) together with an efficient ray acceleration structure shifts the computational effort away from form factor and visibility calculation towards accurately propagating the energy through the hierarchy. We will show how an efficient single pass gathering can be used to minimize traversal costs.

Image quantization and digital halftoning, two fundamental image processing problems, are generally performed sequentially and, in most cases, independent of each other. Color reduction with a pixel-wise defined distortion measure and the halftoning process with its local averaging neighborhood typically optimize different quality criteria or, frequently, follow a heuristic approach without reference to any quantitative quality measure. In this paper, we propose a new model to simultaneously quantize and halftone color images. The method is based on a rigorous cost-function approach which optimizes a quality criterion derived from a simplified model of human perception. It incorporates spatial and contextual information into the quantization and thus overcomes the artificial separation of quantization and halftoning. Optimization is performed by an efficient multiscale procedure which substantially alleviates the computational burden. The quality criterion and the optimization algorithms are evaluated on a representative set of artificial and real-world images showing a significant image quality improvement compared to standard color reduction approaches. Applying the developed cost function, we also suggest a new distortion measure for evaluating the overall quality of color reduction schemes.

Using object clusters for hierarchical radiosity greatly improves the efficiency and thus usability of radiosity computations. By eliminating the quadratic starting phase very large scenes containing about 100 K polygons can be handled efficiently. Although the main algorithm extends rather easily to using object clusters, the creation of "good" object hierarchies is a difficult task both in terms of construction time and in the way how surfaces or objects are grouped to clusters. The quality of an object hierarchy for clustering depends on its ability to accurately simulate the hierarchy of the energy flow in a given scene. Additionally it should support visibility computations by providing efficient ray acceleration techniques. In this paper we present a new approach of building hierarchies of object clusters. Our hybrid structuring algorithm provides accuracy and speed by combining a highly optimized bounding volume hierarchy together with uniform spatial subdivisions for nodes with regular object densities. The algorithm works without user intervention and is well suited for a wide variety of scenes. First results of using these hierarchies in a radiosity clustering environment are very promising and will be presented here. The combination of very deep hierarchies (we use a binary tree) together with an efficient ray acceleration structure shifts the computational effort away from form factor and visibility calculation towards accurately propagating the energy through the hierarchy. We show how an efficient single pass gathering can be used to minimize traversal costs.

Image quantization and digital halftoning are fundamental problems in computer graphics, which arise when displaying high‐color images on non‐truecolor devices. Both steps are generally performed sequentially and, in most cases, independent of each other. Color quantization with a pixel‐wise defined distortion measure and the dithering process with its local neighborhood optimize different quality criteria or, frequently, follow a heuristic without reference to any quality measure. In this paper we propose a new method to simultaneously quantize and dither color images. The method is based on a rigorous cost‐function approach which optimizes a quality criterion derived from a generic model of human perception. A highly efficient algorithm for optimization based on a multiscale method is developed for the dithered color quantization cost function. The quality criterion and the optimization algorithms are evaluated on a representative set of artificial and real‐world images as well as on a collection of icons. A significant image quality improvement is observed compared to standard color reduction approaches.

Based on the method of Maxwell and Baker [7], an all-integer algorithm is developed for the rendering of elliptical curves.It is immune to problems of degeneracy and best suited for hardware implementation.At each point the algorithm provides the tangent vector and an estimate of the quantization error, all the data needed for rendering high precision elliptical arcs and generating antialiased curves, (categories and

Even though GKS did not include circles and, in a more general form, ellipses and elliptical arcs in the list of elementary graphics primitives, CGM settled this omission with its standardization in 1987. According to CGM as well as to CGI, ellipses and elliptical arcs are defined in a very general way via endpoints of conjugate diameter pairs (CDP). Based on the algorithm of Maxwell & Baker [5] this paper presents a new algorithm for the rendering of general ellipses (i.e. not aligned to the coordinate axes) and elliptical arcs which is not only fast and very well suited for implementation in hardware but also deals with all degenerate cases of ellipses at no extra cost. Furthermore, the algorithm provides all the information which is necessary for the generation of anti-aliased elliptical curves.

Systems allowing the creation and manipulation of graphical information (so-called Graphic Editors) have become essential in various fields of applications. At the same time the typical user of such a system has changed. Not computer experts, but designers, secretaries, technicians, teachers etc. are today's typical users of computer graphics, mostly on microcomputers. Obviously it would be desirable to have a common concept of graphics editing covering many applications. The purpose of this paper is a brief survey of the EDEN project started at the IIGb in 1987: the motivation for the project, the major steps, results, current status and future work is presented here. EDEN (short for EDitor ENvironnient) is a generic concept for object-oriented graphics editing, providing device independence at the workstation and graphics output level as well as an application independent file-format for the storage and exchange between different graphics applications.

Brushing commonly refers to the drawing of curves with various line widths in hit-mapped graphics systems. It is best done with circles of suitable diameter so that a constant line width, independent of the curve's slope, is obtained. Allowing all possible integer diameters corresponding to all possible integer line widths results in every second width having an odd value. Thus, the underlying circle algorithm must be able to handle both integer and half-integer radii. Our circle-brush algorithm handles both situations and produces a “best approximation”: All grid points produced simultaneously minimize (1) the residual, (2) the Euclidean distance to the circle, and (3) the displacement along the grid line from the intersection with the circle. Our circle-brush algorithm was developed in careful consideration of its implementation in VLSI.