Volume 22 (2003)

Permanent URI for this community

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

Browse

Now showing 1 - 20 of 90

Progressive Hulls for Intersection Applications
(Blackwell Publishers, Inc and the Eurographics Association, 2003) Platis, Nikos; Theoharis, Theoharis
Progressive meshes are an established tool for triangle mesh simplification. By suitably adapting the simplification process, progressive hulls can be generated which enclose the original mesh in gradually simpler, nested meshes. We couple progressive hulls with a selective refinement framework and use them in applications involving intersection queries on the mesh. We demonstrate that selectively refinable progressive hulls considerably speed up intersection queries by efficiently locating intersection points on the mesh. Concerning the progressive hull construction, we propose a new formula for assigning edge collapse priorities that significantly accelerates the simplification process, and enhance the existing algorithm with several conditions aimed at producing higher quality hulls. Using progressive hulls has the added advantage that they can be used instead of the enclosed object when a lower resolution of display can be tolerated, thus speeding up the rendering process.ACM CSS: I.3.3 Computer Graphics-Picture/Image Generation, I.3.5 Computer Graphics-Computational Geometry and Object Modeling, I.3.7 Computer Graphics-Three-Dimensional Graphics and Realism
Ray Differentials and Multiresolution Geometry Caching for Distribution Ray Tracing in Complex Scenes
(Blackwell Publishers, Inc and the Eurographics Association, 2003) Christensen, Per H.; Laur, David M.; Fong, Julian; Wooten, Wayne L.; Batali, Dana
When rendering only directly visible objects, ray tracing a few levels of specular reflection from large, low-curvaturesurfaces, and ray tracing shadows from point-like light sources, the accessed geometry is coherentand a geometry cache performs well. But in many other cases, the accessed geometry is incoherent and a standardgeometry cache performs poorly: ray tracing of specular reflection from highly curved surfaces, tracing rays thatare many reflection levels deep, and distribution ray tracing for wide glossy reflection, global illumination, widesoft shadows, and ambient occlusion. Fortunately, less geometric accuracy is necessary in the incoherent cases.This observation can be formalized by looking at the ray differentials for different types of scattering: coherentrays have small differentials, while incoherent rays have large differentials. We utilize this observation to obtainefficient multiresolution caching of geometry and textures (including displacement maps) for classic and distributionray tracing in complex scenes. We use an existing multiresolution caching scheme (originally developed forscanline rendering) for textures and displacement maps, and introduce a multiresolution geometry caching schemefor tessellated surfaces. The multiresolution geometry caching scheme makes it possible to efficiently render scenesthat, if fully tessellated, would use 100 times more memory than the geometry cache size.
A Fast Rendering Method for Refractive and Reflective Caustics Due to Water Surfaces
(Blackwell Publishers, Inc and the Eurographics Association, 2003) Iwasaki, Kei; Dobashi, Yoshinori; Nishita, Tomoyuki
In order to synthesize realistic images of scenes that include water surfaces, the rendering of optical effectscaused by waves on the water surface, such as caustics and reflection, is necessary. However, rendering causticsis quite complex and time-consuming. In recent years, the performance of graphics hardware has made significantprogress. This fact encourages researchers to study the acceleration of realistic image synthesis. We present herea method for the fast rendering of refractive and reflective caustics due to water surfaces. In the proposed method,an object is expressed by a set of texture mapped slices. We calculate the intensities of the caustics on the objectby using the slices and store the intensities as textures. This makes it possible to render caustics at interactive rateby using graphics hardware. Moreover, we render objects that are reflected and refracted due to the water surfaceby using reflection/refraction mapping of these slices.Categories and Subject Descriptors (according to ACM CCS): I.3.1 [Computer Graphics]: Hardware Architecture I.3.7 [Computer Graphics]: Three-Dimensional Graphics and Realism
Siggraph 2003
(Blackwell Publishing, Inc and Eurographics Association, 2003) Laycock, S. D.; Laycock, R. G.
Adaptive Ray Tracing of Subdivision Surfaces
(Blackwell Publishers, Inc and the Eurographics Association, 2003) Müller, Kerstin; Techmann, Torsten; Fellner, Dieter W.
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
State of the Art in Global Illumination for Interactive Applications and High-quality Animations
(Blackwell Publishers, Inc and the Eurographics Association, 2003) Damez, Cyrille; Dmitriev, Kirill; Myszkowski, Karol
Global illumination algorithms are regarded as computationally intensive. This cost is a practical problem when producing animations or when interactions with complex models are required. Several algorithms have been proposed to address this issue. Roughly, two families of methods can be distinguished. The first one aims at providing interactive feedback for lighting design applications. The second one gives higher priority to the quality of results, and therefore relies on offline computations. Recently, impressive advances have been made in both categories. In this report, we present a survey and classification of the most up-to-date of these methods.ACM CSS: I.3.7 Computer Graphics-Three-Dimensional Graphics and Realism
Volumetric cell-and-portal generation
(Blackwell Publishers, Inc and the Eurographics Association, 2003) Haumont, D.; Debeir, O.; Sillion, F.
We present an algorithm to generate a cell-and-portal decomposition of general indoor scenes. The method is an adaptation of the 3D watershed transform, computed on a distance-to-geometry sampled field. The watershed is processed using a flooding analogy in the distance field space. Flooding originates from local minima, each minimum producing a region. Portals are built as needed to avoid the merging of regions during their growth. As a result, the cell-and-portal decomposition is closely linked to the structure of the models. In a building, the algorithm finds all the rooms, doors and windows. To restrict the memory load, a hierarchical implementation of the algorithm is presented. We also explain how to handle possible model degeneracies -such as cracks, holes and interpenetrating geometries- using a pre-voxelisation step. The hierarchical algorithm, preceded when necessary by the pre-voxelisation, was tested on a large range of models. We show that it is able to deal with classical architectural models, as well as cave-like environments and large mixed indoor/outdoor scenes. Thanks to the intermediate distance field representation, the algorithm can be used regardless of the way the model is represented: it deals with parametric curves, implicit surfaces, volumetric data and polygon soups in a unified way.
A Survey of Real-time Soft Shadows Algorithms
(Blackwell Publishing, Inc and Eurographics Association, 2003) Hasenfratz, J. -M.; Lapierre, M.; Holzschuch, N.; Sillion, F.; Artis GRAVIR/IMAG-INRIA
Recent advances in GPU technology have produced a shift in focus for real-time rendering applications, whereby improvements in image quality are sought in addition to raw polygon display performance. Rendering effects such as antialiasing, motion blur and shadow casting are becoming commonplace and will likely be considered indispensable in the near future. The last complete and famous survey on shadow algorithms — by Woo et al. [52] in 1990 — has to be updated in particular in view of recent improvements in graphics hardware, which make new algorithms possible. This paper covers all current methods for real-time shadow rendering, without venturing into slower, high quality techniques based on ray casting or radiosity. Shadows are useful for a variety of reasons: first, they help understand relative object placement in a 3D scene by providing visual cues. Second, they dramatically improve image realism and allow the creation of complex lighting ambiances. Depending on the application, the emphasis is placed on a guaranteed framerate, or on the visual quality of the shadows including penumbra effects or “soft shadows”. Obviously no single method can render physically correct soft shadows in real time for any dynamic scene! However our survey aims at providing an exhaustive study allowing a programmer to choose the best compromise for his/her needs. In particular we discuss the advantages, limitations, rendering quality and cost of each algorithm. Recommendations are included based on simple characteristics of the application such as static/moving lights, single or multiple light sources, static/dynamic geometry, geometric complexity, directed or omnidirectional lights, etc. Finally we indicate which methods can efficiently exploit the most recent graphics hardware facilities.
Two-dimensional Potential Fields for Advanced Implicit Modeling Operators
(Blackwell Publishers, Inc and the Eurographics Association, 2003) Barthe, L.; Dodgson, N. A.; Sabin, M. A.; Wyvill, B.; Gaildrat, V.
Current methods for building models using implicit volume techniques present problems defining accurate and controllable blend shapes between implicit primitives. We present new methods to extend the freedom and controllability of implicit volume modeling. The main idea is to use a free-form curve to define the profile of the blend region between implicit primitives.The use of a free-form implicit curve, controlled point-by-point in the Euclidean user space, allows us to group boolean composition operators with sharp transitions or smooth free-form transitions in a single modeling metaphor. This idea is generalized for the creation, sculpting and manipulation of volume objects, while providing the user with simplicity, controllability and freedom in implicit modeling.ACM CSS: I.3.5 Computational Gemoetry and Object Modeling-Curve, surface, solid, and object representations
Planning Collision-Free Reaching Motions for Interactive Object Manipulation and Grasping
(Blackwell Publishers, Inc and the Eurographics Association, 2003) Kallmann, Marcelo; Aubel, Amaury; Abaci, Tolga; Thalmann, Daniel
We present new techniques that use motion planning algorithms based on probabilistic roadmaps to control 22 degrees of freedom (DOFs) of human-like characters in interactive applications. Our main purpose is the automatic synthesis of collision-free reaching motions for both arms, with automatic column control and leg flexion. Generated motions are collision-free, in equilibrium, and respect articulation range limits. In order to deal with the high (22) dimension of our configuration space, we bias the random distribution of configurations to favor postures most useful for reaching and grasping. In addition, extensions are presented in order to interactively generate object manipulation sequences: a probabilistic inverse kinematics solver for proposing goal postures matching pre-designed grasps; dynamic update of roadmaps when obstacles change position; online planning of object location transfer; and an automatic stepping control to enlarge the character's reachable space. This is, to our knowledge, the first time probabilistic planning techniques are used to automatically generate collision-free reaching motions involving the entire body of a human-like character at interactive frame rates.Categories and Subject Descriptors (according to ACM CCS): I.3.7 [Computer Graphics]: Three-Dimensional Graphics and Realism
Volumetric Filtering, Modeling and Visualization for Nano-Medicine
(Blackwell Publishers, Inc and the Eurographics Association, 2003) Bajaj, Chandrajit
The 3D structures of individual proteins or small complexes, such as most of the Protein Data Bank entries, are still unable to yield the 'full picture' of a functional biological complex. The study of large macromolecular complexes, such as viruses, ion channels, the ribosome and other macromolecular machines of various types, offer more complete structural and functional description of the nano-machinery of life.In addition to x-ray crystallography. NMR spectroscopy, electron cryomicroscopy (cryoEM) imaging of single particles, and in-vivo molecular tomographic imaging has become indispensable at revealing the structures of large macromolecular complexes at subnanometer resolutions.In this talk, I shall describe some of the recent computational advances in filtering, modeling, analysis and visualization, that have propelled structure determination by cryoEM and tomographic imaging, to steadily increasing accuracy.
Progressive Simplification of Tetrahedral Meshes Preserving All Isosurface Topologies
(Blackwell Publishers, Inc and the Eurographics Association, 2003) Chiang, Yi-Jen; Lu, Xiang
In this paper, we propose a novel technique for constructing multiple levels of a tetrahedral volume dataset whilepreserving the topologies of all isosurfaces embedded in the data. Our simplification technique has two majorphases. In the segmentation phase, we segment the volume data into topological-equivalence regions, that is, thesub-volumes within each of which all isosurfaces have the same topology. In the simplification phase, we simplifyeach topological-equivalence region independently, one by one, by collapsing edges from the smallest to the largesterrors (within the user-specified error tolerance, for a given error metrics), and ensure that we do not collapseedges that may cause an isosurface-topology change. We also avoid creating a tetrahedral cell of negative volume(i.e., avoid the fold-over problem). In this way, we guarantee to preserve all isosurface topologies in the entiresimplification process, with a controlled geometric error bound. Our method also involves several additionalnovel ideas, including using the Morse theory and the implicit fully augmented contour tree, identifying typesof edges that are not allowed to be collapsed, and developing efficient techniques to avoid many unnecessary orexpensive checkings, all in an integrated manner. The experiments show that all the resulting isosurfaces preservethe topologies, and have good accuracies in their geometric shapes. Moreover, we obtain nice data-reductionrates, with competitively fast running times.
Automatic Hybrid Hierarchy Creation: a Cost-model Based Approach
(Blackwell Publishers, Inc and the Eurographics Association, 2003) Masso, J. P. Molina; Lopez, P. Gonzalez
While using hierarchical search structures has been proved as one of the most efficient acceleration techniques when rendering complex scenes, automatic creation of appropriate hierarchies is not solved yet. Well-known algorithms for automatic creation of bounding volume hierarchies are not enough. Higher performance is achieved by introducing spatial uniform subdivision, although algorithms proposed up to now are not truly automatic, as they need some parameters to be adjusted. In this paper we present a full-automatic hierarchy creation scheme that structures the scene in a hybrid way, combining bounding volumes and voxel grids in the same tree, selecting the search structure that best fits to each scene region. It uses no parameters at all. This efficient proposal relies on a new cost model that estimates the goodness of a hybrid hierarchy if used for rendering the scene.ACM CSS: I.3.7 Computer Graphics-Three-Dimensional Graphics and Realism
The Stringed Haptic Workbench: a New Haptic Workbench Solution
(Blackwell Publishers, Inc and the Eurographics Association, 2003) Tarrin, N.; Coquillart, S.; Hasegawa, S.; Bouguila, L.; Sato, M.
The workbench is an interesting semi-immersive configuration for interactive tasks. However, haptic feedback, i.e.force and tactile feedback, is one important cue which is missing. To the authors' knowledge, the sole proposedsolution consists in installing an arm force feedback device on one-screen workbenches. This solution, however,has several drawbacks. The arm can perturb the stereoscopic display, cross virtual objects or hide parts of thevisualization space. Furthermore, the interaction space is limited by the size of the arm, which may also damagethe screen or perturb the electromagnetic tracking system. Some of these difficulties may even be worth with a two-screenworkbench. This paper discusses an alternative solution, which consists in integrating a stringed hapticdevice on a workbench. This approach is less invasive, more flexible and well-suited to a two-screen workbench.
Announcement
(Blackwell Publishers, Inc and the Eurographics Association, 2003)
Interpolating an Unlimited Number of Curves Meeting at Extraordinary Points on Subdivision Surfaces*
(Blackwell Publishers, Inc and the Eurographics Association, 2003) Nasri, Ahmed H.
Interpolating curves by subdivision surfaces is one of the major constraints that is partially addressed in the literature. So far, no more than two intersecting curves can be interpolated by a subdivision surface such as Doo-Sabin or Catmull-Clark surfaces. One approach that has been used in both of theses surfaces is the polygonal complex approach where a curve can be defined by a control mesh rather than a control polygon. Such a definition allows a curve to carry with it cross derivative information which can be naturally embodied in the mesh of a subdivision surface. This paper extends the use of this approach to interpolate an unlimited number of curves meeting at an extraordinary point on a subdivision surface. At that point, the curves can all meet with eitherC0orC1continuity, yet still have common tangent plane. A straight forward application is the generation of subdivision surfaces through 3-regular meshes of curves for which an easy interface can be used.
Local Exact Particle Tracing on Unstructured Grids
(Blackwell Publishers, Inc and the Eurographics Association, 2003) Kipfer, Peter; Reck, Frank; Greiner, Gunther
For analyzing and interpreting results of flow simulations, particle tracing is a well established visualization method. In addition, it is a preliminary step for more advanced techniques such as line integral convolution. For interactive exploration of large data sets, a very efficient and reliable particle tracing method is needed. For wind channel experiments or flight simulations, large unstructured computational grids have become common practice. Traditional approachs, based on numerical integration methods of ordinary differential equations however fail to deliver sufficiently accurate path calculation at the speed required for interactive use. In this paper we extend the local exact approach of Nielson and Jung in such a way that it can be used for interactive particle tracing in large data sets of steady flow simulation experiments. This will be achieved by sophisticated preprocessing using additional memory. For further visual enhancement of the streamline we construct an implicitly defined smooth Bezier curve that is used for ray tracing. This allows us to visualize additional scalar values of the simulation as attributes to the trajectory and enables the display of high-quality smooth curves without creating any visualization geometry and providing a good impression of the spatial situation at the same time.ACM CSS: I.3.3 Computer Graphics-Line and curve generation; I .3.7 Computer Graphics-Raytracing; G.1.2 Numerical Analysis-Spline and piecewise polynomial approximation
Approximating Parametric Curves With Strip Trees Using Affine Arithmetic
(Blackwell Publishers, Inc and the Eurographics Association, 2003) Henrique de Figueiredo, Luiz; Stolfi, Jorge; Velho, Luiz
We show how to use affine arithmetic to represent a parametric curve with a strip tree. The required bounding rectangles for pieces of the curve are computed by exploiting the linear correlation information given by affine arithmetic. As an application, we show how to compute approximate distance fields for parametric curves.ACM CSS: I.3.3 Computer Graphics-Curve, surface, solid, and object representations, G.1.2 Numerical Analysis-Approximation of surfaces and contours, G.1.0 Numerical Analysis-Interval arithmetic
ShieldTester: Cell-to-Cell Visibility Test for Surface Occluders
(Blackwell Publishers, Inc and the Eurographics Association, 2003) Navazo, I.; Rossignac, J.; Jou, J.; Shariff, R.
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
Freeform Shape Representations for Efficient Geometry Processing
(Blackwell Publishers, Inc and the Eurographics Association, 2003) Kobbelt, Leif
The most important concepts for the handling and storage of freeform shapes in geometry processing applications are parametric representations and volumetric representations. Both have their specific advantages and drawbacks. While the algebraic complexity of volumetric representations is independent from the shape complexity, the domain of a parametric representation usually has to have the same structure as the surface itself (which sometimes makes it necessary to update the domain when the surface is modified).On the other hand, the topology of a parametrically defined surface can be controlled explicitly while in a volumetric representation, the surface topology can change accidentally during deformation. A volumetric representation reduces distance queries or inside/outside tests to mere function evaluations but the geodesic neighborhood relation between surface points is difficult to resolve. As a consequence, it seems promising to combine parametric and volumetric representations to effectively exploit both advantages.In this talk, a number of projects are presented and discussed in which such a combination leads to efficient and numerically stable algorithms for the solution of various geometry processing tasks. Applications include global error control for mesh decimation and smoothing, topology control for level-set surfaces, and shape modeling with unstructured point clouds.

Browse

Browsing Volume 22 (2003) by Issue Date

Results Per Page

Sort Options