Recent advances in 3D acquisition technologies have resulted in a large and growing body of 3D point datasets. Such datasets are typically dense, unstructured, lack connectivity, and are increasingly becoming very large with upwards of several million to billions of points. In this work we propose a scheme for representing details of a given unstructured point sample geometry using a hierarchical statistical analysis of the original dataset. Hierarchical statistical analysis allows us to trade off accuracy against determinism. Our motivation for this new representation lies in the twin observations: (1) there is a very high coherence in local point neighborhoods, and (2) the accuracy required to generate a visually realistic image from a point cloud model can be achieved using statistical methods on a sparse point representation.
We use Principal Component Analysis (PCA) as our tool of statistical analysis. Given a collection of points we do a PCA of their spatial attributes to derive their mean, variance, and principal components. Similarly, a separate PCA on the color attributes of the points gives us a mean, variance, and principal components of the color attributes. Normals can be seen as points on a sphere and we do a 2D PCA on the sphere using a spherical parameterization. We then approximate the original point cloud by generating points using a Gaussian sampling of the spatial PCA attributes. The color and normal information of the generated points can be derived by a Gaussian sampling of the color and normal PCA information respectively.
The approximation error of the PCA representation depends on the complexity of the surface. We do a multi-resolution PCA analysis of the points by first doing a spatial octree subdivision of the points. The PCA is done at each level of this hierarchy to give us a coarse-to-fine PCA analysis of the point cloud. The information in each node can be further reduced by quantization and classification by k-means clustering. In all we use 13 bytes for the spatial and normal information and four extra bytes for the color information. We visualize the encoded geometry with view-dependent randomized rendering. In our client-server architecture the server selects the tree cut to be used for rendering in a view dependent manner. The nodes of the cut are then transmitted to the client, which is either the graphics card or a remote machine. The client renders each node by generating points and their attributes from the nodes statistical information. This generation can be speeded by caching and reusing the generated data.
View dependent rendering of Lucy St. Matthews face at various distances View dependent rendering of David (2mm)
The compact representation of the hierarchical PCA analysis can be used to reduce network transmission and for good rendering quality with randomized rendering. We tested our work on the Stanfordís Davidís Head model, David (full) model, Lucy model, and the St. Matthews face model. The models took no more than about two hours of processing. The figure on the left illustrates the reduction in network transmission in comparison to Stanford's QSplat point rendering system.
We have demonstrated a novel way to represent geometry and its attributes hierarchically using statistical analysis. The application of this work can be realized in reducing network bandwidth and in high-quality interactive rendering. This representation also holds promise for reducing the bus bandwidth in future graphics card architectures.
- A. Kalaiah and A. Varshney, Statistical Point Geometry, Eurographics Symposium on Geometry Processing, June 2003, pages 113-122.
- A. Kalaiah and A. Varshney, Statistical Geometry Representation for Efficient Transmission and Rendering, ACM Transactions on Graphics , Vol 24, No 2, April 2005, pp 348 - 373.
We thank the Stanford Graphics Laboratory for providing us with the David's Head model, David Statue model, Lucy model, and the St. Matthews face model. Also, many thanks to Thomas Baby for his help with coding the k-means clustering.
This work is based upon the work supported by the National Science Foundation under grants ACR-98-12572 and IIS-00-81847. Any opinions, findings, and conclusions or recommendations expressed in this material are those of the author(s) and do not necessarily reflect the views of the National Science Foundation.