23-Issue 3

Permanent URI for this collection

https://diglib.eg.org/handle/10.2312/10150

Browse

Now showing 1 - 20 of 47

Point Cloud Collision Detection
(The Eurographics Association and Blackwell Publishing, Inc, 2004) Klein, Jan; Zachmann, Gabriel
In the past few years, many efficient rendering and surface reconstruction algorithms for point clouds have been developed. However, collision detection of point clouds has not been considered until now, although this is a prerequisite to use them for interactive or animated 3D graphics.We present a novel approach for time-critical collision detection of point clouds. Based solely on the point representation, it can detect intersections of the underlying implicit surfaces. The surfaces do not need to be closed.We construct a point hierarchy where each node stores a sufficient sample of the points plus a sphere covering of a part of the surface. These are used to derive criteria that guide our hierarchy traversal so as to increase convergence. One of them can be used to prune pairs of nodes, the other one is used to prioritize still to be visited pairs of nodes. At the leaves we efficiently determine an intersection by estimating the smallest distance.We have tested our implementation for several large point cloud models. The results show that a very fast and precise answer to collision detection queries can always be given.Categories and Subject Descriptors (according to ACM CCS): G.1.2 [Numerical Analysis]: Approximation of surfaces and contours I.3.5 [Computer Graphics]: Computational Geometry and Object-Modeling[Geometric algorithms, languages and systems; object hierarchy; physically-based modeling] I.3.7 [Computer Graphics]: Three-Dimensional Graphics and Realism[Animation; virtual reality]
Dupin Cyclide Blends Between Quadric Surfaces for Shape Modeling
(The Eurographics Association and Blackwell Publishing, Inc, 2004) Foufou, Sebti; Garnier, Lionel
We introduce a novel method to define Dupin cyclide blends between quadric primitives. Dupin cyclides are non-spherical algebraic surfaces discovered by French mathematician Pierre-Charles Dupin at the beginning of the 19th century. As a Dupin cyclide can be fully characterized by its principal circles, we have focussed our study on how to determine principal circles tangent to both quadrics being blended. This ensures that the Dupin cyclide we are constructing constitutes aG1blend. We use the Rational Quadratic Bezier Curve (RQBC) representation of circular arcs to model the principal circles, so the construction of each circle is reduced to the determination of the three control points of the RQBC representing the circle.In this work, we regard the blending of two quadric primitives A and B as two complementary blending operations: primitive A-cylinder and cylinder-primitive B; two Dupin cyclides and a cylinder are then defined for each blending operation. In general the cylinder is not useful and may be reduced to a simple circle. A complete shape design example is presented to illustrate the modeling of Eurographics'04 Hugo using a limited number of quadrics combined using Dupin cyclide blends.Categories and Subject Descriptors (according to ACM CCS): I.3.5 [Computer Graphics]: Computational Geometry and Object Modeling
Image-based Relighting, and Computer Vision
(The Eurographics Association and Blackwell Publishing, Inc, 2004) Dutre, Philip
Image-based techniques have become very popular over the past couple of years. Ranging from modeling to rendering and lighting, the use of images as direct input for graphics algorithms has become as important as processing polygons or other forms of data.This talk will focus on some of the challenges posed by Image-based relighting. Starting from a set of photographs of an object under various illumination conditions, Image-based relighting computes novel renderings of the objects. Also, the inverse problem stated as 'What is the required lighting configuration to reach a desired illumination on the object?' will be discussed, as well as some thoughts on how results from computer vision can be used to accelerate the process.
A System for View-Dependent Animation
(The Eurographics Association and Blackwell Publishing, Inc, 2004) Chaudhuri, Parag; Kalra, Prem; Banerjee, Subhashis
In this paper, we present a novel system for facilitating the creation of stylized view-dependent 3D animation. Our system harnesses the skill and intuition of a traditionally trained animator by providing a convivial sketch based 2D to 3D interface. A base mesh model of the character can be modified to match closely to an input sketch, with minimal user interaction. To do this, we recover the best camera from the intended view direction in the sketch using robust computer vision techniques. This aligns the mesh model with the sketch. We then deform the 3D character in two stages - first we reconstruct the best matching skeletal pose from the sketch and then we deform the mesh geometry. We introduce techniques to incorporate deformations in the view-dependent setting. This allows us to set up view-dependent models for animation.Categories and Subject Descriptors (according to ACM CCS): I.3.7 [Computer Graphics]: Three-Dimensional Graphics and Realism - Animation 7Our system takes as input a sketch (a), and a base mesh model (b), then recovers a camera to orient the base mesh (c), then reconstructs the skeleton pose (d), and finally deforms the mesh to find the best possible match with the sketch (e).
DiFi: Fast 3D Distance Field Computation Using Graphics Hardware
(The Eurographics Association and Blackwell Publishing, Inc, 2004) Sud, Avneesh; Otaduy, Miguel A.; Manocha, Dinesh
We present an algorithm for fast computation of discretized 3D distance fields using graphics hardware. Given a set of primitives and a distance metric, our algorithm computes the distance field for each slice of a uniform spatial grid baly rasterizing the distance functions of the primitives. We compute bounds on the spatial extent of the Voronoi region of each primitive. These bounds are used to cull and clamp the distance functions rendered for each slice. Our algorithm is applicable to all geometric models and does not make any assumptions about connectivity or a manifold representation. We have used our algorithm to compute distance fields of large models composed of tens of thousands of primitives on high resolution grids. Moreover, we demonstrate its application to medial axis evaluation and proximity computations. As compared to earlier approaches, we are able to achieve an order of magnitude improvement in the running time.Categories and Subject Descriptors (according to ACM CCS): I.3.3 [Computer Graphics]: Distance fields, Voronoi regions, graphics hardware, proximity computations
Approximate Soft Shadows win an Image-Space Flood-Fill Algorithm
(The Eurographics Association and Blackwell Publishing, Inc, 2004) Arvo, Jukka; Hirvikorpi, Mika; Tyystjaervi, Joonas
Most former soft shadow algorithms have either suffered from restricted self-shadowing capabilities, been too slow for interactive applications, or could only be used with a limited types of geometry. In this paper, we propose an efficient image-based approach for computing soft shadows. Our method is based on shadow mapping and provides the associated benefits. We use pixel-based visibility computations for rendering penumbra regions directly into the screen-space. This is accomplished by using a modified flood-fill algorithm which enables us to implement the algorithm using programmable graphics hardware. Even though the resulting images are most often high quality, we do not claim that the proposed method is physically correct. The computation time and memory requirements for soft shadows depend on image resolution and the number of lights, not geometric scene complexity.Categories and Subject Descriptors (according to ACM CCS): I.3.3 [Computer Graphics]: Picture/Image Generation I.3.7 [Three-Dimensional Graphics and Realism]: Color, shading, shadowing, and texture
Real-time Rigid Body Simulation for Haptic Interactions Based on Contact Volume of Polygonal Objects
(The Eurographics Association and Blackwell Publishing, Inc, 2004) Hasegawa, S.; Sato, M.
This paper proposes a new method for real-time rigid body simulations for haptic interactions based on a penalty method regarding contact volume. Analytical methods for calculation of contact forces require too much time to maintain fast update rates for haptic controls. In addition, they prohibit direct connection of haptic interfaces.Penalty methods, which employ spring-damper models for calculation of contact forces, offer a very rapid rate of iterations. In addition, they permit direct connection of haptic interfaces. Penalty methods are good for haptic interactions. However, previous penalty methods do not regard distribution of contact forces over the contact area. For that reason, they can't calculate normal and friction forces on face-face contacts correctly.We propose a distributed spring-damper model on a contact area to solve these problems. We analyze three-dimensional geometries of the intersecting portion on the polyhedral objects. Then, we integrate forces and torques of distributed spring-damper models.We implement a proposed simulator and compare it with a point-based penalty method and constraint method. The comparison shows that the proposed simulator improves accuracy of the simulation of face-face contact and friction forces and the simulation speed. In addition, we attach a six degree-of-freedom (6-DOF) haptic interface to the simulator. Users can feel 6-DOF force feedback and input 6-DOF motions.Categories and Subject Descriptors (according to ACM CCS): I.6.5 [Model Development]: Modeling methodologies, H.5.2 [User Interfaces]: Haptic I/O, I.3.6 [Methodology and Techniques]: Interaction techniques
High Quality Hatching
(The Eurographics Association and Blackwell Publishing, Inc, 2004) Zander, Johannes; Isenberg, Tobias; Schlechtweg, Stefan; Strothotte, Thomas
Hatching lines are often used in line illustrations to convey tone and texture of a surface. In this paper we present methods to generate hatching lines from polygonal meshes and render them in high quality either at interactive rates for on-screen display or for reproduction in print. Our approach is based on local curvature information that is integrated to form streamlines on the surface of the mesh. We use a new algorithm that provides an even distribution of these lines. A special processing of these streamlines ensures high quality line rendering for both intended output media later on. While the streamlines are generated in a preprocessing stage, hatching lines are rendered either for vector-based printer output or on-screen display, the latter allowing for interaction in terms of changing the view parameters or manipulating the entire line shading model at run-time using a virtual machine.Categories and Subject Descriptors (according to ACM CCS): I.3.3 [Computer Graphics]: Picture/Image Generation-Display algorithms; I.3.3 [Computer Graphics]: Picture/Image Generation-Line and curve generation
Combined Correlated and Importance Sampling in Direct Light Source Computation and Environment Mapping
(The Eurographics Association and Blackwell Publishing, Inc, 2004) Szecsi, Laszlo; Sbert, Mateu; Szirmay-Kalos, Laszlo
This paper presents a general variance reduction method that is a quasi-optimal combination of correlated and importance sampling. The weights of the combination are selected automatically in order to keep the merits of both importance and correlated sampling. The proposed sampling method is used for efficient direct light source computation of large area sources and for the calculation of the reflected illumination of environment maps. Importance sampling would be good in these cases if the sources are hidden, while correlated sampling is efficient if the sources are fully visible. The proposed method automatically detects the particular case and provides results that inherit the advantages of both techniques.
Interference Detection for Subdivision Surfaces
(The Eurographics Association and Blackwell Publishing, Inc, 2004) Wu, Xiaobin; Peters, Joerg
Accurate and robust interference detection and ray-tracing of subdivision surfaces requires safe linear approximations. Approximation of the limit surface by the subdivided control polyhedron can be both inaccurate and, due to the exponential growth of the number of facets, costly.This paper shows how a standard intersection hierarchy, such as an OBB tree, can be made safe and efficient for subdivision surface interference detection. The key is to construct, on the fly, optimally placed facets, whose spherical offsets tightly enclose the limit surface. The spherically offset facets can be locally subdivided and they can be efficiently intersected based on standard triangle-triangle interference detection.Categories and Subject Descriptors (according to ACM CCS): I.3.5 [Computer Graphics]: Computational Geometry and Object Modeling
Hardware-Accelerated Rendering of Photo Hulls
(The Eurographics Association and Blackwell Publishing, Inc, 2004) Li, Ming; Magnor, Marcus; Seidel, Hans-Peter
This paper presents an efficient hardware-accelerated method for novel view synthesis from a set of images or videos. Our method is based on the photo hull representation, which is the maximal photo-consistent shape. We avoid the explicit reconstruction of photo hulls by adopting a view-dependent plane-sweeping strategy. From the target viewpoint slicing planes are rendered with reference views projected onto them. Graphics hardware is exploited to verify the photo-consistency of each rasterized fragment. Visibilities with respect to reference views are properly modeled, and only photo-consistent fragments are kept and colored in the target view. We present experiments with real images and animation sequences. Thanks to the more accurate shape of the photo hull representation, our method generates more realistic rendering results than methods based on visual hulls. Currently, we achieve rendering frame rates of 2-3 fps. Compared to a pure software implementation, the performance of our hardware-accelerated method is approximately 7 times faster.Categories and Subject Descriptors (according to ACM CCS): CR Categories: I.3.3 [Computer Graphics]: Picture/Image Generation; I.3.7 [Computer Graphics]: Three-Dimensional Graphics and Realism.
VOTS: VOlume doTS as a Point-Based Representation of Volumetric Data
(The Eurographics Association and Blackwell Publishing, Inc, 2004) Grimm, Soeren; Bruckner, Stefan; Kanitsar, Armin; Groeller, Eduard
We present Volume dots (Vots), a new primitive for volumetric data modelling, processing, and rendering. Vots are a point-based representation of volumetric data. An individual Vot is specified by the coefficients of a Taylor series expansion, i.e. the function value and higher order derivatives at a specific point. A Vot does not only represent a single sample point, it represents the underlying function within a region. With the Vots representation we have a more intuitive and high-level description of the volume data. This allows direct analytical examination and manipulation of volumetric datasets. Vots enable the representation of the underlying scalar function with specified precision. User-centric importance sampling is also possible, i.e., unimportant volume parts are still present but represented with just very few Vots. As proof of concept, we show Maximum Intensity Projection based on Vots.Categories and Subject Descriptors (according to ACM CCS): I.3.6 [Computer Graphics]: Graphics Data Structures and Data Types
A Progressive Rendering Algorithm Using an Adaptive Perceptually Based Image Metric
(The Eurographics Association and Blackwell Publishing, Inc, 2004) Farrugia, Jean-Philippe; Peroche, Bernard
In this paper, we propose to solve the global illumination problem through a progressive rendering method relying on an adaptive sampling of the image space. The refinement of this sample scheme is driven by an image metric based on a powerful vision model. A Delaunay triangulation of the sampled points is followed by a classification of these triangles into three classes. By interpolating each triangle according to the class it belongs to, we can obtain a high quality image by computing only a fraction of all the pixels and thus saving computation time.Categories and Subject Descriptors (according to ACM CCS): I.3.3 [Computer Graphics]: Perceptual Rendering, Global illumination
SMARTPAPER: An Interactive and User Friendly Sketching System
(The Eurographics Association and Blackwell Publishing, Inc, 2004) Shesh, Amit; Chen, Baoquan
This paper describes an interactive sketching system for 3D design/modeling that diverts from the conventional menu-and-button interfaces of CAD tools. The system, dubbed SMARTPAPER, offers a unified sketching environment that supports direct sketching as well as gestured sketching with more emphasis on the former to encourage natural sketching styles. SMARTPAPER also provides a unified 2D and 3D drawing domain by allowing the user to sketch directly on a 3D model in addition to the usual 2D sketching from scratch. A natural sketching experience is offered by supporting casual sketching consisting of wiggly, discontinuous, overlapping strokes. The system is empowered by an array of seamlessly integrated 2D and 3D features such as 2D sketch cleaning, 3D reconstruction from 2D sketch, 3D transformations, sketching on 3D, and conventional 3D CSG operations like cutting and joining. The key to the success of SMARTPAPER is efficient and robust 3D reconstruction from a single freehand 2D sketch with minimal hints. We have employed and improved Lipson's optimization method, originally designed for offline reconstruction of engineering drawings, in our interactive system by leveraging additional clues obtained by interaction during sketching.Categories and Subject Descriptors (according to ACM CCS): I.3.3 [Computer Graphics]: Interaction Techniques, Pen-based Interaction
GPU-Based Nonlinear Ray Tracing
(The Eurographics Association and Blackwell Publishing, Inc, 2004) Weiskopf, Daniel; Schafhitzel, Tobias; Ertl, Thomas
In this paper, we present a mapping of nonlinear ray tracing to the GPU which avoids any data transfer back to main memory. The rendering process consists of the following parts: ray setup according to the camera parameters, ray integration, ray-object intersection, and local illumination. Bent rays are approximated by polygonal lines that are represented by textures. Ray integration is based on an iterative numerical solution of ordinary differential equations whose initial values are determined during ray setup. To improve the rendering performance, we propose acceleration techniques such as early ray termination and adaptive ray integration. Finally, we discuss a variety of applications that range from the visualization of dynamical systems to the general relativistic visualization in astrophysics and the rendering of the continuous refraction in media with varying density.Categories and Subject Descriptors (according to ACM CCS): I.3.3 [Computer Graphics]: Picture/Image Generation I.3.7 [Computer Graphics]: Three-Dimensional Graphics and Realism
Anisotropic Filtering of Non-Linear Surface Features
(The Eurographics Association and Blackwell Publishing, Inc, 2004) Hildebrandt, Klaus; Polthier, Konrad
A new method for noise removal of arbitrary surfaces meshes is presented which focuses on the preservation and sharpening of non-linear geometric features such as curved surface regions and feature lines. Our method uses a prescribed mean curvature flow (PMC) for simplicial surfaces which is based on three new contributions: 1. the definition and efficient calculation of a discrete shape operator and principal curvature properties on simplicial surfaces that is fully consistent with the well-known discrete mean curvature formula, 2. an anisotropic discrete mean curvature vector that combines the advantages of the mean curvature normal with the special anisotropic behaviour along feature lines of a surface, and 3. an anisotropic prescribed mean curvature flow which converges to surfaces with an estimated mean curvature distribution and with preserved non-linear features. Additionally, the PMC flow prevents boundary shrinkage at constrained and free boundary segments.
Implicit Visualization and Inverse Modeling of Growing Trees
(The Eurographics Association and Blackwell Publishing, Inc, 2004) Galbraith, Callum; Muendermann, Lars; Wyvill, Brian
A method is proposed for photo-realistic modeling and visualization of a growing tree. Recent visualization methods have focused on producing smoothly blending branching structures, however, these methods fail to account for the inclusion of non-smooth features such as branch bark ridges and bud scale scars. These features constitute an important visual aspect of a living tree, and are also observed to vary over time. The proposed method incorporates these features by using an hierarchical implicit modeling system, which provides a variety of tools for combining surface components in both smooth and non smooth configurations. A procedural interface to this system supports the use of inverse modeling, which is a global-to-local methodology, where the local properties of plant organs are described in terms of their global position within the tree architecture. Inverse modeling is used to define both the tree structure at any time, and a continuous developmental sequence for the tree from a seedling. These techniques provide an intuitive paradigm for the definition of complex tree growth sequences and their subsequent visualization, based solely on observed phenomena. Thus, a key advantage is that they do not require any knowledge of, or simulation of, the underlying biological processes.Categories and Subject Descriptors (according to ACM CCS): I.3.5 [Computer Graphics]: Curve, surface, solid, and object representations I.3.7 [Computer Graphics]: Animation
Balancing Considered Harmful - Faster Photon Mapping using the Voxel Volume Heuristic -
(The Eurographics Association and Blackwell Publishing, Inc, 2004) Wald, Ingo; Guenther, Johannes; Slusallek, Philipp
Photon mapping is one of the most important algorithms for computing global illumination. Especially for efficiently producing convincing caustics, there are no real alternatives to photon mapping. On the other hand, photon mapping is also quite costly: Each radiance lookup requires to find the k nearest neighbors in a kd-tree, which can be more costly than shooting several rays. Therefore, the nearest-neighbor queries often dominate the rendering time of a photon map based renderer.In this paper, we present a method that reorganizes - i.e. un balances - the kd-tree for storing the photons in a way that allows for finding the k-nearest neighbors much more efficiently, thereby accelerating the radiance estimates by a factor of 1.2-3.4. Most importantly, our method still finds exactly the same k-nearest-neighbors as the original method, without introducing any approximations or loss of accuracy. The impact of our method is demonstrated with several practical examples.Categories and Subject Descriptors (according to ACM CCS): I.3.3 [Computer Graphics]: Global Illumination I.3.7 [Computer Graphics]: Raytracing
Scalable behaviors for crowd simulation
(The Eurographics Association and Blackwell Publishing, Inc, 2004) Sung, Mankyu; Gleicher, Michael; Chenney, Stephen
Crowd simulation for virtual environments offers many challenges centered on the trade-offs between rich behavior, control and computational cost. In this paper we present a new approach to controlling the behavior of agents in a crowd. Our method is scalable in the sense that increasingly complex crowd behaviors can be created without a corresponding increase in the complexity of the agents. Our approach is also more authorable; users can dynamically specify which crowd behaviors happen in various parts of an environment. Finally, the character motion produced by our system is visually convincing. We achieve our aims with a situation-based control structure. Basic agents have very limited behaviors. As they enter new situations, additional, situation-specific behaviors are composed on the fly to enable agents to respond appropriately. The composition is done using a probabilistic mechanism. We demonstrate our system with three environments including a city street and a theater.Categories and Subject Descriptors (according to ACM CCS): I.3.7 [Computer Graphics]: Animation
Synthesizing Sound from Turbulent Field using Sound Textures for Interactive Fluid Simulation
(The Eurographics Association and Blackwell Publishing, Inc, 2004) Dobashi, Yoshinori; Yamamoto, Tsuyoshi; Nishita, Tomoyuki
Sound is an indispensable element for the simulation of a realistic virtual environment. Therefore, there has been much recent research focused on the simulation of realistic sound effects. This paper proposes a method for creating sound for turbulent phenomena such as fire. In a turbulent field, the complex motion of vortices leads to the generation of sound. This type of sound is called a vortex sound. The proposed method simulates a vortex sound by computing vorticity distributions using computational fluid dynamics. Sound textures for the vortex sound are first created in a pre-process step. The sound is then created at interactive rates by using these sound textures. The usefulness of the proposed method is demonstrated by applying it to the simulation of the sound of fire and other turbulent phenomena.Categories and Subject Descriptors (according to ACM CCS): I.3.7 [Computer Graphics]: Three-Dimensional Graphics and Realism - Animation; I.6.8 [Simulation and Modeling]: Types of Simulation - Animation; I.3.7 [Computer Graphics]: Three-Dimensional Graphics and Realism; I.6.3 [Simulation and Modeling]: Applications; H.5.5 [Information Interfaces and Presentation]: Sound and Music Computing - Methodologies and techniques, Modeling.

Browse

Browsing 23-Issue 3 by Issue Date

Results Per Page

Sort Options