Efficient Fitting and Rendering of Large Scattered Data Sets Using Subdivision Surfaces
Eurographics 2002
Abstract
We present a method to efficiently construct and render a smooth surface for approximation of large functional scattered data. Using a subdivision surface framework and techniques from terrain rendering, the resulting surface can be explored from any viewpoint while maintaining high surface fairness and interactive frame rates. We show the approximation error to be sufficiently small for several large data sets. Our system allows for adaptive simplification and provides continuous levels of detail, taking into account the local variation and distribution of the data.
Paper and Presentation
- EG2002-scheib.pdf (2 MB)
- presentation.ppt (2 MB)
Images
| Dense 0.7 million points |
Fractal 1.0 million points |
|
| Data point distribution |  |
 |
| Tessellation (without subdivision) |  |
 |
| Tessellation (with subdivision) |  |
 |
The Dense data set was purchased for use from real world sampled data. The Fractal terrain was created from a 4000x4000 height field; created in Bryce and Photoshop, sampled randomly with bilinear interpolation in Matlab.
Videos
These videos were taken on the the following system:
- Processor: Dual ~1495 MHz Intel Family 15 Model 0 Stepping 10 GenuineIntel
- RAM: 2 GB
- Graphics Card: GeForce3, 64 MB
- OS: Microsoft Windows 2000 Professional
The paper shows timings for several platforms, including ones with higher performance.
The videos are all MPEG-1, and are divided into three categories:
Flythrough
The largest data sets are explored with our new algorithm.
dense: real world data
fractal: generated data
Technical
Split screen, one half with lighting only (no texture). This demonstrates the that the curvature of the surface is maintained. The right half displays highlighted edges so that subdivision can be seen from the first person.
A third person point of view camera observes the adaptive tessellation of the mesh based on viewpoint. Notice the different subdivision schemes. The subdivision surface tessellation looks like spider webs. This is the camera path exploring the fractal data set.
Comparison
We compare our implementation with the Bézier patches of Haber et al. from VIS 2001. Both implementations were run on the same machine and were tuned for best performance.
Our new method makes use of a pixel error metric while the other implementation does not. For every video on this disk a one pixel error maximum is used. Settings for the other implementation were selected to equal visual quality.
Note the situations where the Bézier patches, without adaptive tessellation, are under the most strain: when the horizon is visible and the viewpoint is near the mesh.
dense: real world data
fractal: generated data