SPBG: Symposium on Point Based Graphics
Permanent URI for this community
Browse
Browsing SPBG: Symposium on Point Based Graphics by Title
Now showing 1 - 20 of 89
Results Per Page
Sort Options
Item Accelerating Volume Raycasting using Occlusion Frustums(The Eurographics Association, 2008) Mensmann, Jörg; Ropinski, Timo; Hinrichs, Klaus; Hans-Christian Hege and David Laidlaw and Renato Pajarola and Oliver StaadtGPU-based volume raycasting allows to produce high quality renderings on current graphics hardware. The use of such raycasters is on the rise due to their inherent flexibility as well as the advances in hardware performance and functionality. Although recent raycasting systems achieve interactive frame rates on high-end graphics hardware, further improved performance would enable more complex rendering techniques, e. g., advanced illumination models. In this paper we introduce a novel approach to empty space leaping in order to reduce the number of costly volume texture fetches during ray traversal. We generate an optimized proxy geometry for raycasting which is based on occlusion frustums obtained from previous frames. Our technique does not rely on any preprocessing, introduces no image artifacts, and in contrast to previous point-based methods works also for non-continuous view changes. Besides the technical realization and the performance results, we also discuss the potential problems of ray coherence in relation to our approach and restrictions in current GPU architectures. The presented technique has been implemented using fragment and geometry shaders and can be integrated easily into existing raycasting systems.Item Adaptive Sampling and Rendering of Fluids on the GPU(The Eurographics Association, 2008) Zhang, Yanci; Solenthaler, Barbara; Pajarola, Renato; Hans-Christian Hege and David Laidlaw and Renato Pajarola and Oliver StaadtIn this paper, we propose a novel GPU-friendly algorithm for the Smoothed Particle Hydrodynamics (SPH) simulation for weakly compressible fluids. The major goal of our algorithm is to implement a GPU-based SPH simulation that can simulate and render a large number of particles at interactive speed. Additionally, our algorithm exhibits the following three features. Firstly, our algorithm supports adaptive sampling of the fluids. Particles can be split into several sub-particles in geometrically complex regions to provide a more accurate simulation. At the same time, nearby particles deep inside the fluids are merged to a single particle to reduce the number of particles. Secondly, the fluids are visualized by directly computing the intersection between ray and an isosurface defined by the surface particles. A dynamic particle grouping algorithm and equation solver are employed to quickly find the ray-isosurface intersection. Thirdly, based on the observation that the SPH simulation is a naturally parallel algorithm, the whole SPH simulation, including the adaptive sampling of the fluids as well as surface particle rendering, is executed on the GPU to fully utilize the computational power and parallelism of modern graphics hardware. Our experimental data shows that we can simulate about 50K adaptively sampled particles, or up to 120K particles in the fixed sampling case at a rate of approximately 20 time steps per second.Item Approximate Star-Shaped Decomposition of Point Set Data(The Eurographics Association, 2007) Lien, Jyh-Ming; M. Botsch and R. Pajarola and B. Chen and M. ZwickerSimplification or decomposition is a common strategy to handle large geometric models, which otherwise require excessive computation to process. Star-shaped decomposition partitions a model into a set of star-shaped components. A model is star shaped if and only if there exists at least one point which can see all the points of the model. Due to this interesting property, decomposing a model into star-shaped components can be used for computing camera locations to guard a given environment (the art-gallery problem), skeleton extraction, point data compression, as well as motion planning. In this paper, we propose a simple method to partition (or cluster) point set data (PSD) into 'approximately star-shaped' components. Our method can be applied to both 2D and 3D PSD and can be naturally extended to higher dimensional spaces. Our method does not require or compute any connectivity information of the input points. The proposed method only requires the position and the outward normals of points. Our experimental results show that the size of the final decomposition is close to optimal.Item Approximating Geodesics on Point Set Surfaces(The Eurographics Association, 2006) Ruggeri, Mauro R.; Darom, Tal; Saupe, Dietmar; Kiryati, Nahum; Mario Botsch and Baoquan Chen and Mark Pauly and Matthias ZwickerWe present a technique for computing piecewise linear approximations of geodesics on point set surfaces by minimizing an energy function defined for piecewise linear path. The function considers path length, closeness to the surface for the nodes of the piecewise linear path and for the intermediate line segments. Our method is robust with respect to noise and outliers. In order to avoid local minima, a good initial piecewise linear approximation of a geodesic is provided by Dijkstra s algorithm that is applied to a proximity graph constructed over the point set. As the proximity graph we use a sphere-of-influence weighted graph extended for surfel sets. The convergence of our method has been studied and compared to results of other methods by running experiments on surfaces whose geodesics can be computed analytically. Our method is presented and optimized for surfel-based representations but it has been implemented also for MLS surfaces. Moreover, it can also be applied to other surface representations, e.g., triangle meshes, radial-basis functions, etc.Item A Barcode Shape Descriptor for Curve Point Cloud Data(The Eurographics Association, 2004) Collins, Anne; Zomorodian, Afra; Carlsson, Gunnar; Guibas, Leonidas; Markus Gross and Hanspeter Pfister and Marc Alexa and Szymon RusinkiewiczIn this paper, we present a complete computational pipeline for extracting a compact shape descriptor for curve point cloud data. Our shape descriptor, called a barcode, is based on a blend of techniques from differential geometry and algebraic topology.We also provide a metric over the space of barcodes, enabling fast comparison of PCDs for shape recognition and clustering. To demonstrate the feasibility of our approach, we have implemented it and provide experimental evidence in shape classification and parametrization.Item Boolean Operations on Surfel-Bounded Solids Using Programmable Graphics Hardware(The Eurographics Association, 2004) Adams, Bart; Dutré, Philip; Markus Gross and Hanspeter Pfister and Marc Alexa and Szymon RusinkiewiczIn this paper we present an algorithm to compute boolean operations on free-form solids bounded by surfels using programmable graphics hardware. The intersection, union and difference of two or more solids, is calculated on the GPU using vertex and fragment programs. First, we construct an inside-outside partitioning using 3-color grids and signed distance fields. Next, we use this partitioning to classify the surfels of both solids as inside or outside the other solid. For surfels close to the boundary of the other solid, we use the distance field and its gradient to define a clipping plane, which can be used to resample or clip the surfel. Our algorithm runs at interactive rates on consumer-level graphics hardware.Item Bounds on the k-Neighborhood for Locally Uniformly Sampled Surfaces(The Eurographics Association, 2004) Andersson, Mattias; Giesen, Joachim; Pauly, Mark; Speckmann, Bettina; Markus Gross and Hanspeter Pfister and Marc Alexa and Szymon RusinkiewiczGiven a locally uniform sample set P of a smooth surface S. We derive upper and lower bounds on the number k of nearest neighbors of a sample point p that have to be chosen from P such that this neighborhood contains all restricted Delaunay neighbors of p. In contrast to the trivial lower bound, the upper bound indicates that a sampling condition that is used in many computational geometry proofs is quite reasonable from a practical point of view.Item Compression of Point-Based 3D Models by Shape-Adaptive Wavelet Coding of Multi-Height Fields(The Eurographics Association, 2004) Ochotta, Tilo; Saupe, Dietmar; Markus Gross and Hanspeter Pfister and Marc Alexa and Szymon RusinkiewiczIn order to efficiently archive and transmit large 3D models, lossy and lossless compression methods are needed. We propose a compression scheme for coordinate data of point-based 3D models of surfaces. A point-based model is processed for compression in a pipeline of three subsequent operations, partitioning, parameterization, and coding. First the point set is partitioned yielding a suitable number of point clusters. Each cluster corresponds to a surface patch, that can be parameterized as a height field and resampled on a regular grid. The domains of the height fields have irregular shapes that are encoded losslessly. The height fields themselves are encoded using a shape-adaptive wavelet coder, producing a progressive bitstream for each patch. A rate-distortion optimization provides for an optimal bit allocation for the individual patch codes. With this algorithm design compact codes are produced that are scalable with respect to rate, quality, and resolution. In our encodings of complex 3D models competitive rate-distortion performances were achieved with excellent reconstruction quality at under 3 bits per point (bpp).Item Computing Variation Modes for Point Set Surfaces(The Eurographics Association, 2005) Miao, Lanfang; Huang, Jin; Liu, Xinguo; Bao, Hujun; Peng, Qunsheng; Guo, Baining; Marc Alexa and Szymon Rusinkiewicz and Mark Pauly and Matthias ZwickerPoint sets have become a popular shape representation. In this paper, we present a novel approach to computing variation modes for point set surfaces, and represent the point set surface as a linear combination of the variation modes, called a generative representation for the point set surface. Given a point set, our approach consists of two steps: The first is to produce a set of new samples with increasing smoothness and less detailed features. We use a modified smoothing method based on moving least squares (MLS) surface to produce the samples. The second is to arrange the shape vectors of the new samples together with the original point set into a matrix, and then compute the singular value decomposition of the matrix, producing a set of variation modes (the eigen vectors). Using the variation modes and the generative representation, we can easily synthesize new shapes. Typical applications are low/high/band pass filtering as well as denoising and detail enhancement in multiple scales.Item Conformal Alpha Shapes(The Eurographics Association, 2005) Cazals, Frederic; Giesen, Joachim; Pauly, Mark; Zomorodian, Afra; Marc Alexa and Szymon Rusinkiewicz and Mark Pauly and Matthias ZwickerWe define a new filtration of the Delaunay triangulation of a finite set of points in Rd, similar to the alpha shape filtration. The new filtration is parameterized by a local scale parameter instead of the global scale parameter in alpha shapes. Since our approach shares many properties with the alpha shape filtration and the local scale parameter conforms to the local geometry we call it conformal alpha shape filtration. The local scale parameter is motivated from applications and previous algorithms in surface reconstruction. We show how conformal alpha shapes can be used for surface reconstruction of non-uniformly sampled surfaces, which is not possible with alpha shapes.Item Conversion of Point-Sampled Models to Textured Meshes(The Eurographics Association, 2005) Wicke, Martin; Olibet, Sandro; Gross, Markus; Marc Alexa and Szymon Rusinkiewicz and Mark Pauly and Matthias ZwickerWe present an algorithm to convert point-sampled objects to textured meshes. The output mesh carries the geometric information present in the input model, while information about color and other surface attributes is separated and stored in textures. The point cloud is triangulated and decimated so it adequately represents the object geometry. Using EWA splatting, we compute textures patches for all triangles in the mesh. In an iterative process, the size of the texture patches is chosen adaptively such that texture information is preserved during the conversion. The texture filtering capabilities of EWA splatting ensure that no texture aliasing occurs. Finally, the texture patches are compiled into a texture atlas. Aside from colors, other surface attributes can be treated similarly. Normal maps can be computed to allow for further simplification of the output mesh while maintaining high visual quality.Item Decomposition and Visualization of Fourth-Order Elastic-Plastic Tensors(The Eurographics Association, 2008) Neeman, Alisa G.; Brannon, Rebecca; Jeremic, Boris; Gelder, Allen Van; Pang, Alex; Hans-Christian Hege and David Laidlaw and Renato Pajarola and Oliver StaadtVisualization of fourth-order tensors from solid mechanics has not been explored in depth previously. Challenges include the large number of components (3x3x3x3 for 3D), loss of major symmetry and loss of positive definiteness (with possibly zero or negative eigenvalues). This paper presents a decomposition of fourth-order tensors that facilitates their visualization and understanding. Fourth-order tensors are used to represent a solid's stiffness. The stiffness tensor represents the relationship between increments of stress and increments of strain. Visualizing stiffness is important to understand the changing state of solids during plastification and failure. In this work, we present a method to reduce the number of stiffness components to second-order 3x3 tensors for visualization. The reduction is based on polar decomposition, followed by eigen-decomposition on the polar "stretch". If any resulting eigenvalue is significantly lower than the others, the material has softened in that eigen-direction. The associated second-order eigentensor represents the mode of stress (such as compression, tension, shear, or some combination of these) to which the material becomes vulnerable. Thus we can visualize the physical meaning of plastification with techniques for visualizing second-order symmetric tensors.Item Direct Computing of Surface Curvatures for Point-Set Surfaces(The Eurographics Association, 2007) Yang, Pinghai; Qian, Xiaoping; M. Botsch and R. Pajarola and B. Chen and M. ZwickerAccurate computing of the curvatures of a surface from its discrete form is of fundamental importance for many graphics and engineering applications. The moving least-squares (MLS) surface from Levin [Lev2003] and its variants have been successfully used to define point-set surfaces in a variety of point cloud data based modeling and rendering applications. This paper presents a set of analytical equations for direct computing of surface curvatures from pointset surfaces based on the explicit definition from [AK04a, AK04b]. Besides the Gaussian parameter involved in the MLS definition, these analytical equations allow us to conduct direct and exact differential geometric analysis on the point-set surfaces without specifying any subjective parameters. Our experimental validation on both synthetic and real point cloud data demonstrates that such direct computing from analytical equations provides a viable approach for surface curvature evaluation for unorganized point cloud data.Item The Domain of a Point Set Surface(The Eurographics Association, 2004) Amenta, Nina; Kil, Yong J.; Markus Gross and Hanspeter Pfister and Marc Alexa and Szymon RusinkiewiczIt is useful to be able to define a two-dimensional point-set surface determined by a point cloud. One popular definition is Levin's MLS surface. This surface is defined on a domain which is a three-dimensional subset of R3, a narrow region around the input point cloud. If we were to extend the definition outside the domain, we would produce components of the surface which are far from the point cloud. This is important in practice, since when moving points onto the MLS surface, we need to begin with an initial guess which is within the domain. We visualize the domain in two dimensions, and explain why it is so narrow. We also consider two MLS variants which can be defined on a wider domain without producing spurious surface components. One is efficient and works well except near sharp corners. The other is computationally expensive but seems to work well everywhere.Item DUODECIM - A Structure for Point Scan Compression and Rendering(The Eurographics Association, 2005) Krüger, Jens; Schneider, Jens; Westermann, Rüdiger; Marc Alexa and Szymon Rusinkiewicz and Mark Pauly and Matthias ZwickerIn this paper we present a compression scheme for large point scans including per-point normals. For the encoding of such scans we introduce a particular type of closest sphere packing grids, the hexagonal close packing (HCP). HCP grids provide a structure for an optimal packing of 3D space, and for a given sampling error they result in a minimal number of cells if geometry is sampled into these grids. To compress the data, we extract linear sequences (runs) of filled cells in HCP grids. The problem of determining optimal runs is turned into a graph theoretical one. Point positions and normals in these runs are incrementally encoded. At a grid spacing close to the point sampling distance, the compression scheme only requires slightly more than 3 bits per point position. Incrementally encoded per-point normals are quantized at high fidelity using only 5 bits per normal (see Figure 1). The compressed data stream can be decoded in the graphics processing unit (GPU). Decoded point positions are saved in graphics memory, and they are then used on the GPU again to render point primitives. In this way we render gigantic point scans from their compressed representation in local GPU memory at interactive frame rates (see Figure 2).Item A Dynamic Surface Reconstruction Framework for Large Unstructured Point Sets(The Eurographics Association, 2006) Allègre, Rémi; Chaine, Raphaëlle; Akkouche, Samir; Mario Botsch and Baoquan Chen and Mark Pauly and Matthias ZwickerWe present a method to reconstruct simplified mesh surfaces from large unstructured point sets, extending recent work on dynamic surface reconstruction. The method consists of two core components: an efficient selective reconstruction algorithm, based on geometric convection, that simplifies the input point set while reconstructing a surface, and a local update algorithm that dynamically refines or coarsens the reconstructed surface according to specific local sampling constraints. We introduce a new data-structure that significantly accelerates the original selective reconstruction algorithm and makes it possible to handle point set models with millions of sample points. Our data-structure mixes a kd-tree with the Delaunay triangulation of the selected points enriched with a sparse subset of landmark sample points. This design efficiently responds to the specific spatial location issues of the geometric convection algorithm. We also develop an out-of-core implementation of the method, that permits to seamlessly reconstruct and interactively update simplified mesh surfaces from point sets that do not fit into main memory.Item Efficient and Prioritized Point Subsampling for CSRBF Compression(The Eurographics Association, 2006) Kitago, Masaki; Gopi, M.; Mario Botsch and Baoquan Chen and Mark Pauly and Matthias ZwickerWe present a novel cost function to prioritize points and subsample a point set based on the dominant geometric features and local sampling density of the model. This cost function is easy to compute and at the same time provides rich feedback in the form of redundancy and non-uniformity in the sampling. We use this cost function to simplify the given point set and thus reduce the CSRBF (Compactly Supported Radial Basis Function) coefficients of the surface fit over this point set. Further compression of CSRBF data set is effected by employing lossy encoding techniques on the geometry of the simplified model, namely the positions and normal vectors, and lossless encoding on the CSRBF coefficients. Results on the quality of subsampling and our compression algorithms are provided. The major advantages of our method include highly efficient subsampling using carefully designed, effective, and easy compute cost function, in addition to a very high PSNR (Peak Signal to Noise Ratio) of our compression technique relative to other known point set subsampling techniques.Item Efficient Bounds for Point-Based Animations(The Eurographics Association, 2007) Steinemann, Denis; Otaduy, Miguel A.; Gross, Markus; M. Botsch and R. Pajarola and B. Chen and M. ZwickerWe introduce a new and efficient approach for collision detection in point-based animations, based on the fast computation of tight surface bounds. Our approach is able to tightly bound a high-resolution surface with a cost linear in the number of simulation nodes, which is typically small. We extend concepts about bounds of convex sets to the point-based deformation setting, and we introduce an efficient algorithm for finding extrema of these convex sets. We can compute surface bounds orders of magnitude faster and/or tighter than with previous methods.Item Efficient Point-Based Rendering Using Image Reconstruction(The Eurographics Association, 2007) Marroquim, Ricardo; Kraus, Martin; Cavalcanti, Paulo Roma; M. Botsch and R. Pajarola and B. Chen and M. ZwickerImage-space reconstruction of continuous surfaces from scattered one-pixel projections of points is known to potentially offer an advantageous time complexity compared to surface splatting techniques. We propose a new algorithm for hardware-accelerated image-space reconstruction using pull-push interpolation and present an efficient GPU implementation. Compared to published image-space reconstruction approaches employing the pull-push interpolation, our method offers a significantly improved image quality because of the integration of elliptic boxfilters and support for deferred Phong shading. For large point-based models, our GPU implementation is capable of rendering more than 50M points per second including image-space reconstruction and deferred shading.Item Efficient Refinement of Dynamic Point Data(The Eurographics Association, 2007) Solenthaler, Barbara; Zhang, Yanci; Pajarola, Renato; M. Botsch and R. Pajarola and B. Chen and M. ZwickerParticle simulations as well as geometric modeling techniques have demonstrated their ability to process and render points interactively. However, real-time particle-based fluid simulations suffer from poor rendering quality due to low surface particle resolutions. Surfaces appear blobby, surface details are lost, and features like edges are degraded due to smoothing effects. This paper presents a novel point refinement method for irregularly sampled, dynamic points coming from a particle-based fluid simulation. Our interpolation algorithm can handle complex geometries including splashes, and at the same time preserves features like edges. Point collisions are avoided resulting in a nearly uniform sampling facilitating surface reconstruction techniques. No point preprocessing is necessary, and point neighborhoods are dynamically updated reducing computation and memory costs. We show that our algorithm can efficiently detect and refine the surface points of a fluid and we demonstrate the improvement of rendering quality and applicability to real-time simulations.