Symposium on Point Based Graphics 04
Permanent URI for this collection
Multi-Resolution Sound Rendering
Wand, M.
;
Straßer, W.
Interactive Silhouette Rendering for Point-Based Models
[meta data] [files:
Xu, Hui
;
Nguyen, Minh X.
;
Yuan, Xiaoru
;
Chen, Baoquan
Boolean Operations on Surfel-Bounded Solids Using Programmable Graphics Hardware
[meta data] [files:
Adams, Bart
;
Dutré, Philip
Interactive Point-Based Modeling from Dense Color and Sparse Depth
Popescu, Voicu
;
Sacks, Elisha
;
Bahmutov, Gleb
Interactive 3D Painting on Point-Sampled Objects
[meta data] [files:
Adams, Bart
;
Wicke, Martin
;
Dutré, Philip
;
Gross, Markus
;
Pauly, Mark
;
Teschner, Matthias
Uncertainty and Variability in Point Cloud Surface Data
[meta data] [files:
Pauly, Mark
;
Mitra, Niloy J.
;
Guibas, Leonidas J.
Post-processing of Scanned 3D Surface Data
[meta data] [files:
Weyrich, T.
;
Pauly, M.
;
Keiser, R.
;
Heinzle, S.
;
Scandella, S.
;
Gross, M.
Progressive Compression of Point-Sampled Models
[meta data] [files:
Waschbüsch, M.
;
Gross, M.
;
Eberhard, F.
;
Lamboray, E.
;
Würmlin, S.
Compression of Point-Based 3D Models by Shape-Adaptive Wavelet Coding of Multi-Height Fields
[meta data] [files:
Ochotta, Tilo
;
Saupe, Dietmar
Points Reloaded: Point-Based Rendering Revisited
[meta data] [files:
Sainz, Miguel
;
Pajarola, Renato
;
Lario, Roberto
Proximity Graphs for Defining Surfaces over Point Clouds
[meta data] [files:
Klein, Jan
;
Zachmann, Gabriel
Bounds on the k-Neighborhood for Locally Uniformly Sampled Surfaces
[meta data] [files:
Andersson, Mattias
;
Giesen, Joachim
;
Pauly, Mark
;
Speckmann, Bettina
On Normals and Projection Operators for Surfaces Defined by Point Sets
[meta data] [files:
Alexa, Marc
;
Adamson, Anders
Topological estimation using witness complexes
[meta data] [files:
Silva, Vin de
;
Carlsson, Gunnar
Meshing Point Clouds Using Spherical Parameterization
[meta data] [files:
Zwicker, M.
;
Gotsman, C.
Shape Segmentation and Matching from Noisy Point Clouds
[meta data] [files:
Dey, Tamal K.
;
Giesen, Joachim
;
Goswami, Samrat
A Barcode Shape Descriptor for Curve Point Cloud Data
[meta data] [files:
Collins, Anne
;
Zomorodian, Afra
;
Carlsson, Gunnar
;
Guibas, Leonidas
Browse
Recent Submissions
Item Multi-Resolution Sound Rendering(The Eurographics Association, 2004) Wand, M.; Straßer, W.; Markus Gross and Hanspeter Pfister and Marc Alexa and Szymon RusinkiewiczPoint-based multi-resolution representations have been used successfully for rendering highly complex three dimensional scenes in real-time. In this paper, we apply this paradigm to sound rendering: A hierarchy of stochastic sample sound sources is used to approximate complex sound environments (containing a large number of sound sources, such as a football stadium), allowing for interactive real-time walkthroughs. Additionally, the proposed technique can be used for observer-dependent auralizations of simple approximations of global sound propagation. Typical applications of the technique are in virtual reality and computer games, especially to complement established output-sensitive algorithms for rendering visual content.Item Interactive Silhouette Rendering for Point-Based Models(The Eurographics Association, 2004) Xu, Hui; Nguyen, Minh X.; Yuan, Xiaoru; Chen, Baoquan; Markus Gross and Hanspeter Pfister and Marc Alexa and Szymon RusinkiewiczWe present a new method for rendering silhouettes of point-based models. Due to the lack of connectivity information, most existing polygon-based silhouette generation algorithms cannot be applied to point-based models. Our method not only bypasses this connectivity requirement, but also accommodates point-based models with sparse non-uniform sampling and inaccurate/no normal information. Like conventional point-based rendering, we render a model in two passes. The points are rendered as enlarged opaque disks in the first pass to obtain a visibility mask, while being rendered as regular size splats/disks in the second pass. In this way, edges are automatically depicted at depth discontinuities, usually at the silhouette boundaries. The silhouette color is the disk color used in the first pass rendering. The silhouette thickness can be controlled by changing the disk size difference between two passes. We demonstrate our method on different types of point-based models from various sources. The simplicity of our method allows it to be easily integrated with other rendering techniques to cater to many applications. Our method is capable of rendering large scenes of millions of points at interactive rates using modern graphics hardware.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 Point-based Surface Rendering with Motion Blur(The Eurographics Association, 2004) Guan, Xin; Mueller, Klaus; Markus Gross and Hanspeter Pfister and Marc Alexa and Szymon RusinkiewiczIn this paper we show how to extend point-based surface rendering to illustrate object motion. We do this by first extruding the circular points into ellipsoids, which fill the space traced out by the points in motion. Using ellipsoids instead of cylinders achieves a low-passing effect of the motion trail. We then find the screen-space projection of each ellipsoid, which is an ellipse. These can be rendered conveniently using hardware acceleration. Our technique thus facilitates the rendering of complex objects with real-time motion blur. It gives the viewer a sharply rendered object together with the hint of the direction of motion. The construction of the motion blur trails can be based on different rendering primitives, as is also discussed in the paper. Various trail textures are presented to achieve artistic rendering results.Item Phong Splatting(The Eurographics Association, 2004) Botsch, Mario; Spernat, Michael; Kobbelt, Leif; Markus Gross and Hanspeter Pfister and Marc Alexa and Szymon RusinkiewiczSurface splatting has developed into a valuable alternative to triangle meshes when it comes to rendering of highly detailed massive datasets. However, even highly accurate splat approximations of the given geometry may sometimes not provide a sufficient rendering quality since surface lighting mostly depends on normal vectors whose deviation is not bounded by the Hausdorff approximation error. Moreover, current point-based rendering systems usually associate a constant normal vector with each splat, leading to rendering results which are comparable to flat or Gouraud shading for polygon meshes. In contrast, we propose to base the lighting of a splat on a linearly varying normal field associated with it, and we show that the resulting Phong Splats provide a visual quality which is far superior to existing approaches. We present a simple and effective way to construct a Phong splat representation for a given set of input samples. Our surface splatting system is implemented completely based on vertex and pixel shaders of current GPUs and achieves a splat rate of up to 4M Phong shaded, filtered, and blended splats per second. In contrast to previous work, our scan conversion is projectively correct per pixel, leading to more accurate visualization and clipping at sharp features.Item Real-Time Point Cloud Refinement(The Eurographics Association, 2004) Guennebaud, G.; Barthe, L.; Paulin, M.; Markus Gross and Hanspeter Pfister and Marc Alexa and Szymon RusinkiewiczSplatting-based rendering techniques are currently the best choice for efficient high quality rendering of pointbased geometries. However, such techniques are not suitable for large magnification, especially when the object is under-sampled. This paper improves the rendering quality of pure splatting techniques using a fast dynamic up-sampling algorithm for point-based geometry. Our algorithm is inspired by interpolatory subdivision surfaces where the geometry is refined iteratively. At each step the refined geometry is that from the previous step enriched by a new set of points. The point insertion procedure uses three operators: a local neighborhood selection operator, a refinement operator (adding new points) and a smoothing operator. Even though our insertion procedure makes the analysis of the limit surface complicated and it does not guarantee its G1 continuity, it remains very efficient for high quality real-time point rendering. Indeed, while providing an increased rendering quality, especially for large magnification, our algorithm needs no other preprocessing nor any additional information beyond that used by any splatting technique.Item Stratified Point Sampling of 3D Models(The Eurographics Association, 2004) Nehab, Diego; Shilane, Philip; Markus Gross and Hanspeter Pfister and Marc Alexa and Szymon RusinkiewiczPoint sampling is an important intermediate step for a variety of computer graphics applications, and specialized sampling strategies have been developed to satisfy the requirements of each problem. In this article, we present a technique to generate a stratified sampling of 3D models that is applicable across many domains. The algorithm voxelizes the model and selects one sample per voxel, restricted to the original model s surface. Parameters allow control of the uniformity of the sample placement and the minimum distance between samples. We demonstrate the effectiveness of this technique in selecting stroke locations for painterly rendering models and for producing sampled geometry used as input to shape descriptors.Item Interactive Point-Based Modeling from Dense Color and Sparse Depth(The Eurographics Association, 2004) Popescu, Voicu; Sacks, Elisha; Bahmutov, Gleb; Markus Gross and Hanspeter Pfister and Marc Alexa and Szymon RusinkiewiczWe are developing a system for interactive modeling of real world scenes. The acquisition device consists of a video camera enhanced with an attached laser system. As the operator sweeps the scene, the device acquires dense color and sparse depth frames that are registered and merged into a point-based model. The evolving model is rendered continually to provide immediate operator feedback. This paper discusses interactive modeling of structured scenes, which consist of large smooth surfaces. We have built an acquisition device that captures 7x7 evenly spaced depth samples per frame. The samples are grouped into patches that are approximated with polynomial surfaces. Consecutive frames are registered by computing a motion that aligns their depth and color samples. The scene is modeled as a collection of depth images created on demand during scanning. Resampling errors are avoided by using offsets to record accurately the positions of the acquired samples. The interactive modeling pipeline runs at five frames per second.Item Interactive 3D Painting on Point-Sampled Objects(The Eurographics Association, 2004) Adams, Bart; Wicke, Martin; Dutré, Philip; Gross, Markus; Pauly, Mark; Teschner, Matthias; Markus Gross and Hanspeter Pfister and Marc Alexa and Szymon RusinkiewiczWe present a novel painting system for 3D objects. In order to overcome parameterization problems of existing applications, we propose a unified sample-based approach to represent geometry and appearance of the 3D object as well as the brush surface. The generalization of 2D pixel-based paint models to point samples allows us to elegantly simulate paint transfer for 3D objects. In contrast to mesh-based painting systems, an efficient dynamic resampling scheme permits arbitrary levels of painted detail. Our system provides intuitive user interaction with a six degree-of-freedom (DOF) input device. As opposed to other 3D painting systems, real brushes are simulated including their dynamics and collision handling.Item Uncertainty and Variability in Point Cloud Surface Data(The Eurographics Association, 2004) Pauly, Mark; Mitra, Niloy J.; Guibas, Leonidas J.; Markus Gross and Hanspeter Pfister and Marc Alexa and Szymon RusinkiewiczWe present a framework for analyzing shape uncertainty and variability in point-sampled geometry. Our representation is mainly targeted towards discrete surface data stemming from 3D acquisition devices, where a finite number of possibly noisy samples provides only incomplete information about the underlying surface. We capture this uncertainty by introducing a statistical representation that quantifies for each point in space the likelihood that a surface fitting the data passes through that point. This likelihood map is constructed by aggregating local linear extrapolators computed from weighted least squares fits. The quality of fit of these extrapolators is combined into a corresponding confidence map that measures the quality of local tangent estimates. We present an analysis of the effect of noise on these maps, show how to efficiently compute them, and extend the basic definition to a scale-space formulation. Various applications of our framework are discussed, including an adaptive re-sampling method, an algorithm for reconstructing surfaces in the presence of noise, and a technique for robustly merging a set of scans into a single point-based representation.Item Post-processing of Scanned 3D Surface Data(The Eurographics Association, 2004) Weyrich, T.; Pauly, M.; Keiser, R.; Heinzle, S.; Scandella, S.; Gross, M.; Markus Gross and Hanspeter Pfister and Marc Alexa and Szymon Rusinkiewicz3D shape acquisition has become a major tool for creating digital 3D surface data in a variety of application elds. Despite the steady increase in accuracy, most available scanning techniques cause severe scanning artifacts such as noise, outliers, holes, or ghost geometry. To apply sophisticated modeling operations on these data sets, substantial post-processing is usually required. In this paper, we address a variety of scanning artifacts that are created by common optical scanners and provide a comprehensive set of user-guided tools to process corrupted data sets. These include an eraser tool, low-pass lter s for noise removal, a set of outlier detection methods, and various up-sampling and hole- lling tools. These techniques can be applied early in the content creation pipeline. Therefore, all our tools are implemented to operate directly on the acquired point cloud. We also emphasize the need for extensive user control and an ef cient visual feedback loop. The effectiveness of our scan cleaning tools is demonstrated on various models acquired with commercial laser-range scanners and low-cost structured light scanners.Item Progressive Compression of Point-Sampled Models(The Eurographics Association, 2004) Waschbüsch, M.; Gross, M.; Eberhard, F.; Lamboray, E.; Würmlin, S.; Markus Gross and Hanspeter Pfister and Marc Alexa and Szymon Rusinkiewiczdecomposition of the point set and thus easily allows for progressive decoding. Our method is generic in the sense that it can handle arbitrary point attributes using attribute-specific coding operations. Furthermore, no resampling of the model is needed and thus we do not introduce additional smoothing artifacts. We provide coding operators for the point position, normal and color. Particularly, by transforming the point positions into a local reference frame, we exploit the fact that all point samples are living on a surface. Our framework enables for compressing both geometry and appearance of the model in a unified manner. We show the performance of our framework on a diversity of point-based models.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 Layered Point Clouds(The Eurographics Association, 2004) Gobbetti, Enrico; Marton, Fabio; Markus Gross and Hanspeter Pfister and Marc Alexa and Szymon RusinkiewiczWe present a simple point-based multiresolution structure for interactive visualization of very large point sampled models on consumer graphics platforms. The structure is based on a hierarchy of precomputed object-space point clouds. At rendering time, the clouds are combined coarse-to-fine with a top-down structure traversal to locally adapt sample densities according to the projected size in the image. Since each cloud is made of a few thousands of samples, the multiresolution extraction cost is amortized over many graphics primitives, and host-to-graphics communication effectively exploits on-board caching and object based rendering APIs. The progressive block based refinement nature of the rendering traversal is well suited to hiding out-of-core data access latency, and lends itself well to incorporate backface, view frustum, and occlusion culling, as well as compression and viewdependent progressive transmission. The resulting system allows rendering of complex models at high frame rates (over 60M splat/second), supports network streaming, and is fundamentally simple to implement.Item Points Reloaded: Point-Based Rendering Revisited(The Eurographics Association, 2004) Sainz, Miguel; Pajarola, Renato; Lario, Roberto; Markus Gross and Hanspeter Pfister and Marc Alexa and Szymon RusinkiewiczThe increasing popularity of points as rendering primitives has led to a variety of different rendering algorithms, and in particular the different implementations compare like apples to oranges. In this paper we revisit a number of recently developed point-based rendering implementations. We briefly summarize a few proposed hierarchical multiresolution point data structures and their advantages. Based on a common multiresolution framework we then describe and examine different hardware accelerated point rendering algorithms. Experimental results are given with respect to performance timing and rendering quality for the different approaches.Item Proximity Graphs for Defining Surfaces over Point Clouds(The Eurographics Association, 2004) Klein, Jan; Zachmann, Gabriel; Markus Gross and Hanspeter Pfister and Marc Alexa and Szymon RusinkiewiczWe present a new definition of an implicit surface over a noisy point cloud. It can be evaluated very fast, but, unlike other definitions based on the moving least squares approach, it does not suffer from artifacts. In order to achieve robustness, we propose to use a different kernel function that approximates geodesic distances on the surface by utilizing a geometric proximity graph. The starting point in the graph is determined by approximate nearest neighbor search. From a variety of possibilities, we have examined the Delaunay graph and the sphere-of-influence graph (SIG). For both, we propose to use modifications, the r-SIG and the pruned Delaunay graph. We have implemented our new surface definition as well as a test environment which allows to visualize and to evaluate the quality of the surfaces. We have evaluated the different surfaces induced by different proximity graphs. The results show that artifacts and the root mean square error are significantly reduced.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 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 On Normals and Projection Operators for Surfaces Defined by Point Sets(The Eurographics Association, 2004) Alexa, Marc; Adamson, Anders; Markus Gross and Hanspeter Pfister and Marc Alexa and Szymon RusinkiewiczLevin s MLS projection operator allows defining a surface from a set of points and represents a versatile procedure to generate points on this surface. Practical problems of MLS surfaces are a complicated non-linear optimization to compute a tangent frame and the (commonly overlooked) fact that the normal to this tangent frame is not the surface normal. An alternative definition of Point Set Surfaces, inspired by the MLS projection, is the implicit surface version of Adamson & Alexa.We use this surface definition to show how to compute exact surface normals and present simple, efficient projection operators. The exact normal computation also allows computing orthogonal projections.Item Topological estimation using witness complexes(The Eurographics Association, 2004) Silva, Vin de; Carlsson, Gunnar; Markus Gross and Hanspeter Pfister and Marc Alexa and Szymon RusinkiewiczThis paper tackles the problem of computing topological invariants of geometric objects in a robust manner, using only point cloud data sampled from the object. It is now widely recognised that this kind of topological analysis can give qualitative information about data sets which is not readily available by other means. In particular, it can be an aid to visualisation of high dimensional data. Standard simplicial complexes for approximating the topological type of the underlying space (such as Cech, Rips, or a-shape) produce simplicial complexes whose vertex set has the same size as the underlying set of point cloud data. Such constructions are sometimes still tractable, but are wasteful (of computing resources) since the homotopy types of the underlying objects are generally realisable on much smaller vertex sets. We obtain smaller complexes by choosing a set of landmark points from our data set, and then constructing a "witness complex" on this set using ideas motivated by the usual Delaunay complex in Euclidean space. The key idea is that the remaining (non-landmark) data points are used as witnesses to the existence of edges or simplices spanned by combinations of landmark points. Our construction generalises the topology-preserving graphs of Martinetz and Schulten [MS94] in two directions. First, it produces a simplicial complex rather than a graph. Secondly it actually produces a nested family of simplicial complexes, which represent the data at different feature scales, suitable for calculating persistent homology [ELZ00, ZC04]. We find that in addition to the complexes being smaller, they also provide (in a precise sense) a better picture of the homology, with less noise, than the full scale constructions using all the data points. We illustrate the use of these complexes in qualitatively analyzing a data set of 3x3 pixel patches studied by David Mumford et al [LPM03].Item Meshing Point Clouds Using Spherical Parameterization(The Eurographics Association, 2004) Zwicker, M.; Gotsman, C.; Markus Gross and Hanspeter Pfister and Marc Alexa and Szymon RusinkiewiczWe present a simple method for meshing a 3D point cloud to a manifold genus-0 mesh. Our approach is based on recent methods for spherical embedding of planar graphs, where we use instead a k-nearest neighborhood graph of the point cloud. Our approach proceeds in two steps: We first embed the neighborhood graph on a sphere using an iterative procedure, minimizing the tangential Laplacian. Then we triangulate the embedded points and apply the resulting mesh connectivity to the input points. Besides meshing, spherical embedding of point clouds may also be used for other applications such as texture mapping or morphing.Item Finite Elements on Point Based Surfaces(The Eurographics Association, 2004) Clarenz, U.; Rumpf, M.; Telea, A.; Markus Gross and Hanspeter Pfister and Marc Alexa and Szymon Rusinkiewiczframework efficiently and effectively brings well-known PDE-based processing techniques to the field of point-based surfaces. Our method is based on the construction of local tangent planes and a local Delaunay triangulation of adjacent points projected onto this plane. The definition of tangent spaces relies on moment-based computation with proven scaling and stability properties. Once local couplings are obtained, we are able to easily assemble PDE-specific mass and stiffness matrices and solve corresponding linear systems by standard iterative solvers. We demonstrate our framework by different classes of PDE-based surface processing applications, such as texture synthesis and processing, geometric fairing, and segmentation.Item Shape Segmentation and Matching from Noisy Point Clouds(The Eurographics Association, 2004) Dey, Tamal K.; Giesen, Joachim; Goswami, Samrat; Markus Gross and Hanspeter Pfister and Marc Alexa and Szymon RusinkiewiczWe present the implementation results of a shape segmentation technique and an associated shape matching method whose input is a point sample from the shape. The sample is allowed to be noisy in the sense that they may scatter around the boundary of the shape instead of lying exactly on it. The algorithm is simple and mostly combinatorial in that it builds a single data structure, the Delaunay triangulation of the point set, and groups the tetrahedra to form the segments. A small set of weighted points are derived from the segments which are used as signatures to match shapes. Experimental results establish the effectiveness of the method in practice.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.