Volume 23 (2004)
Permanent URI for this community
Browse
Browsing Volume 23 (2004) by Issue Date
Now showing 1 - 20 of 93
Results Per Page
Sort Options
Item Approximated Centroidal Voronoi Diagrams for Uniform Polygonal Mesh Coarsening(The Eurographics Association and Blackwell Publishing, Inc, 2004) Valette, Sebastien; Chassery, Jean-MarcWe present a novel clustering algorithm for polygonal meshes which approximates a Centroidal Voronoi Diagram construction. The clustering provides an efficient way to construct uniform tessellations, and therefore leads to uniform coarsening of polygonal meshes, when the output triangulation has many fewer elements than the input mesh. The mesh topology is also simplified by the clustering algorithm. Based on a mathematical framework, our algorithm is easy to implement, and has low memory requirements. We demonstrate the efficiency of the proposed scheme by processing several reference meshes having up to 1 million triangles and very high genus within a few minutes on a low- end computer.Item Dye Advection Without the Blur: A Level-Set Approach for Texture-Based Visualization of Unsteady Flow(The Eurographics Association and Blackwell Publishing, Inc, 2004) Weiskopf, D.Dye advection is an intuitive and versatile technique to visualize both steady and unsteady flow. Dye can be easily combined with noise-based dense vector field representations and is an important element in user-centric visual exploration processes. However, fast texture-based implementations of dye advection rely on linear interpolation operations that lead to severe diffusion artifacts. In this paper, a novel approach for dye advection is proposed to avoid this blurring and to achieve long and clearly defined streaklines or extended streak-like patterns. The interface between dye and background is modeled as a level-set within a signed distance field. The level-set evolution is governed by the underlying flow field and is computed by a semi-Lagrangian method. A reinitialization technique is used to counteract the distortions introduced by the level-set evolution and to maintain a level-set function that represents a local distance field. This approach works for 2D and 3D flow fields alike. It is demonstrated how the texture-based level-set representation lends itself to an efficient GPU implementation and therefore facilitates interactive visualization.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 RealismItem Deferred Splatting(The Eurographics Association and Blackwell Publishing, Inc, 2004) Guennebaud, Gael; Barthe, Loic; Paulin, MathiasIn recent years it has been shown that, above a certain complexity, points become the most efficient rendering primitives. Although the programmability of the lastest graphics hardware allows efficient implementation of high quality surface splatting algorithms, their performance remains below those obtained with simpler point based rendering algorithms when they are used for scenes of high complexity. In this paper, our goal is to apply high quality point based rendering algorithms on complex scenes. For this purpose, we show how to take advantage of temporal coherency in a very accurate hardware accelerated point selection algorithm allowing the expensive computations to be peformed only on visible points. Our algorithm is based on a multi-pass hardware accelerated EWA splatting. It is also suitable for any rendering application since no pre-process is needed and no assumption is made on the data structure. In addition, we briefly discuss the association of our method with other existing culling techniques and optimization for particular applications.Categories and Subject Descriptors (according to ACM CCS): I.3.3 [Computer Graphics]: Viewing algorithmsItem A Physically-Based Model for Rendering Realistic Scratches(The Eurographics Association and Blackwell Publishing, Inc, 2004) Bosch, Carles; Pueyo, Xavier; Merillou, Stephane; Ghazanfarpour, DjamchidIndividually visible scratches, also called isolated scratches, are very common in real world surfaces. Although their microgeometry is not visible, they are individually perceptible by the human eye, lying into a representation scale between BRDF and texture. In order to simulate this kind of scratches in synthetic images we need to know their position over the surface (texture scale), so we can determine where to use the specific scratch BRDF instead of the ordinary surface BRDF. Computing the BRDF of a scratch is difficult because it depends on the scratch's invisible microgeometry. In this paper, we propose a new physically based model to derive this microgeometry by simulating the formation process of scratches. We allow specifying intuitively the parameters involved in the process such as the scratching tool, the penetration forces, and the material properties of the object. From these parameters, we derive the microgeometries of the scratches by taking into account the real behaviour of the process. This behaviour has been determined by analysing existing models in the field of materials engineering and some 'scratch tests' that we performed on metals. Our method has the advantages of easily simulating scratches with a wide range of microgeometries and taking into account the variability of their microgeometry along the scratch path. Another contribution is related to the location of the scratches over the surface. Instead of using an image of the paths as in previous work, we present a new representation based on curves defining the paths. This offers an independence on the image resolution or the distance from the observer and accurately provides the scratch direction in order to compute scratch BRDFs.Categories and Subject Descriptors (according to ACM CCS): I.3.7 [Computer Graphics]: Color, shading, shadowing, and texture.Item REPORT OF THE STATUTORY AUDITORS TO THE GENERAL MEETING OF THE MEMBERS OF EUROGRAPHICS ASSOCIATION GENEVA(The Eurographics Association and Blackwell Publishing Ltd., 2004)Item SIMD Optimization of Linear Expressions for Programmable Graphics Hardware(The Eurographics Association and Blackwell Publishing Ltd., 2004) Chandrajit Bajaj; Insung Ihm; Jungki Min; Jinsang OhThe increased programmability of graphics hardware allows efficient graphical processing unit (GPU) implementations of a wide range of general computations on commodity PCs. An important factor in such implementations is how to fully exploit the SIMD computing capacities offered by modern graphics processors. Linear expressions in the form of , where A is a matrix, and and are vectors, constitute one of the most basic operations in many scientific computations. In this paper, we propose a SIMD code optimization technique that enables efficient shader codes to be generated for evaluating linear expressions. It is shown that performance can be improved considerably by efficiently packing arithmetic operations into four-wide SIMD instructions through reordering of the operations in linear expressions. We demonstrate that the presented technique can be used effectively for programming both vertex and pixel shaders for a variety of mathematical applications, including integrating differential equations and solving a sparse linear system of equations using iterative methods.Item ACM/EG Symposium on Computer Animation 2004(The Eurographics Association and Blackwell Publishing Ltd., 2004) Boulic, Ronan; Pai, Dinesh K.; Badler, Norman; Desbrun, Mathieu; Reveret, LionelItem Second Annual Symposium on Computer Animation (SCA 2003)(The Eurographics Association and Blackwell Publishing Ltd., 2004) SCA 2003 ChairsItem New Eurographics Fellows(The Eurographics Association and Blackwell Publishing Ltd., 2004)Item Fast Surface Modelling Using a 6th Order PDE(The Eurographics Association and Blackwell Publishing, Inc, 2004) Zhang, Jian. J.; You, L. H.Although the control-point based parametric approach is used most widely in free-form surface modelling, complementary techniques co-exist to meet various specialised requirements. The partial differential equation (PDE) based modelling approach is especially suitable for satisfying surface boundary constraints. They are also effective for the generation of families of free-form surfaces, which share a common base and differ in their secondary features. In this paper, we present a fast surface modelling method using a sixth order PDE. This PDE provides enough degrees of freedom not only to accommodate tangent, but also curvature boundary conditions and offers more shape control parameters to serve as user controls for the manipulation of surface shapes. In order to achieve real-time performance, we have constructed a surface function and developed a high-precision approximate solution to the 6th order PDE. Unlike some existing PDE-based techniques, this resolution method can satisfy the boundary conditions exactly, and is able to create free-form surfaces as fast and almost as accurately as the closed-form (analytical) solutions. Due to the fact that it has sufficient degrees of freedom to accommodate the continuity of 3-sided and 4-sided surface patches at their boundaries, this method is able to model complex surfaces consisting of multiple patches. Compared with existing PDE-based modelling methods, this method is both fast and can solve a larger class of surface modelling problems.Categories and Subject Descriptors (according to ACM CCS): I.3.5 [Computer Graphics]: Curves, surfaces, solid, and object representations; physically based modellingItem Measurement-Based Interactive Simulation of Viscoelastic Solids(The Eurographics Association and Blackwell Publishing, Inc, 2004) Schoner, Jeffrey L.; Lang, Jochen; Seidel, Hans-PeterAnimation of viscoelastic solids in entertainment and medical applications as well as scientific simulation can be improved through observations of real world objects. This paper presents a method for simulating viscoelastic solids in real-time for visual and haptic display along with a method for determining the parameters of the the underlying model from automated physical measurements of real world objects. The viscoelastic model is a novel extension of the discrete Green's function matrix for linear elasticity, which combines static behavior represented by Green's functions with dynamic behavior expressed by differential equations inspired by particle systems. We describe a novel estimation method of dynamic contact behavior for heterogeneous complex objects based on these measurements. For this estimation, our method relies only on measurement data previously used in the acquisition less realistic elastostatic models. In this way our method allows more physically accurate realism in animation of viscoelastic solids without large additional computational costs or any measurements besides those associated with related methods for elastostatic solids.Categories and Subject Descriptors (according to ACM CCS): I.3.5 [Computer Graphics]: Physically based modeling I.3.7 [Computer Graphics]: Virtual reality, animationItem Way-Finder: guided tours through complex walkthrough models(The Eurographics Association and Blackwell Publishing, Inc, 2004) Andujar, C.; Vazquez, P.; Fairen, M.The exploration of complex walkthrough models is often a difficult task due to the presence of densely occluded regions which pose a serious challenge to online navigation. In this paper we address the problem of algorithmic generation of exploration paths for complex walkthrough models. We present a characterization of suitable properties for camera paths and we discuss an efficient algorithm for computing them with little or no user intervention. Our approach is based on identifying the free-space structure of the scene (represented by a cell and portal graph) and an entropy-based measure of the relevance of a view-point. This metric is key for deciding which cells have to be visited and for computing critical way-points inside each cell. Several results on different model categories are presented and discussed.Item Applied Geometry:Discrete Differential Calculus for Graphics(The Eurographics Association and Blackwell Publishing, Inc, 2004) Desbrun, MathieuGeometry has been extensively studied for centuries, almost exclusively from a differential point of view. However, with the advent of the digital age, the interest directed to smooth surfaces has now partially shifted due to the growing importance of discrete geometry. From 3D surfaces in graphics to higher dimensional manifolds in mechanics, computational sciences must deal with sampled geometric data on a daily basis-hence our interest in Applied Geometry.In this talk we cover different aspects of Applied Geometry. First, we discuss the problem of Shape Approximation, where an initial surface is accurately discretized (i.e., remeshed) using anisotropic elements through error minimization. Second, once we have a discrete geometry to work with, we briefly show how to develop a full- blown discrete calculus on such discrete manifolds, allowing us to manipulate functions, vector fields, or even tensors while preserving the fundamental structures and invariants of the differential case. We will emphasize the applicability of our discrete variational approach to geometry by showing results on surface parameterization, smoothing, and remeshing, as well as virtual actors and thin-shell simulation.Joint work with: Pierre Alliez (INRIA) , David Cohen-Steiner (Duke U.), Eitan Grinspun (NYU), Anil Hirani (Caltech), Jerrold E. Marsden (Caltech), Mark Meyer (Pixar), Fred Pighin (USC), Peter Schroeder (Caltech), Yiying Tong (USC).Item Implicit Fitting Using Radial Basis Functions with Ellipsoid Constraint(The Eurographics Association and Blackwell Publishing Ltd., 2004) Li, Q.; Wills, D.; Phillips, R.; Viant, W. J.; Griffiths, J. G.; Ward, J.Implicit planar curve and surface fitting to a set of scattered points plays an important role in solving a wide variety of problems occurring in computer graphics modelling, computer graphics animation, and computer assisted surgery. The fitted implicit surfaces can be either algebraic or non-algebraic. The main problem with most algebraic surface fitting algorithms is that the surface fitted to a given data set is often unbounded, multiple sheeted, and disconnected when a high degree polynomial is used, whereas a low degree polynomial is too simple to represent general shapes. Recently, there has been increasing interest in non-algebraic implicit surface fitting. In these techniques, one popular way of representing an implicit surface has been the use of radial basis functions. This type of implicit surface can represent various shapes to a high level of accuracy. In this paper, we present an implicit surface fitting algorithm using radial basis functions with an ellipsoid constraint. This method does not need to build interior and exterior layers for the given data set or to use information on surface normal but still can fit the data accurately. Furthermore, the fitted shape can still capture the main features of the object when the data sets are extremely sparse. The algorithm involves solving a simple general eigen-system and a computation of the inverse or psedo-inverse of a matrix, which is straightforward to implement.Item An Integer One-Pass Algorithm for Voxel Traversal(The Eurographics Association and Blackwell Publishing Ltd., 2004) Liu, Y. K.; Zalik, B.; Yang, H.Voxel traversing along a line in a uniformly divided voxel space is frequently needed in different applications of computer graphics. The paper presents a new integer one-pass algorithm for this problem. In 2D, the proposed approach is based on a modification of the well-known Bresenham algorithm. The algorithm is then extended in 3D where a special case may occur. It is characterized by a simple discriminator. A derivation for this discriminator given in the paper confirms that all calculations can be realized using only integer arithmetic. In this way, the accumulation of rounding errors is completely eliminated, and a robust and compact implementation can be easily achieved. One of the main advantages of the proposed algorithm is that it visits 1-3 voxels during each iteration thus assuring its efficiency. The algorithm has been compared with other algorithms for voxel traversing by measuring spent CPU time. For comparison, Cleary and Wyvill's, Amanatides and Woo's, and Code-based algorithm have been used. The proposed algorithm is faster than the referenced algorithms.Item Real-time Light Animation(The Eurographics Association and Blackwell Publishing, Inc, 2004) Sbert, Mateu; Szecsi, Laszlo; Szirmay-Kalos, LaszloLight source animation is a particularly hard field of real-time global illumination algorithms since moving light sources result in drastic illumination changes and make coherence techniques less effective. However, the animation of small (point-like) light sources represents a special but practically very important case, for which the reuse of the results of other frames is possible. This paper presents a fast light source animation algorithm based on the virtual light sources illumination method. The speed up is close to the length of the animation, and is due to reusing paths in all frames and not only in the frame where they were obtained. The possible applications of this algorithm are the lighting design and systems to convey shape and features with relighting.Item GPU-Based Nonlinear Ray Tracing(The Eurographics Association and Blackwell Publishing, Inc, 2004) Weiskopf, Daniel; Schafhitzel, Tobias; Ertl, ThomasIn 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 RealismItem Balancing Considered Harmful - Faster Photon Mapping using the Voxel Volume Heuristic -(The Eurographics Association and Blackwell Publishing, Inc, 2004) Wald, Ingo; Guenther, Johannes; Slusallek, PhilippPhoton 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]: RaytracingItem Network Service(2004)Item Approximation of Optimal Voxel Size for Collision Detection in Maintainability Simulations within Massive Virtual Environments(The Eurographics Association and Blackwell Publishing Ltd., 2004) Borro, D.; Garcia-Alonso, A.; Matey, L.This paper describes a Collision Method for massive virtual environments composed of millions of triangles. It has been applied in the aeronautics industry for maintainability simulations using virtual aircraft engine mock-ups. The method performs well and has a good interactive frame rate even when it is used for computing force feedback with haptic devices. Space sorting problems chiefly related to voxel techniques, such as memory requirements and optimal voxel size, have been solved. We use advanced memory structures and hashing techniques. To find the optimal voxel size, several analytical solutions have been proposed and compared. These solutions are based on the performance cost function of the algorithm used. Experiments have been undertaken to verify these analytical solutions.