| | This Article | |
| |
| |
| | Share | |
| |
| |
| | Bibliographic References | |
| |
| |
| | Add to: | |
| |
 Digg
 Furl
 Spurl
 Blink
 Simpy
 Google
 Del.icio.us
 Y!MyWeb
| |
| | Search | |
| |
| |
| | |
Smooth Surface Extraction from Unstructured Point-based Volume Data Using PDEs
November/December 2008 (vol. 14 no. 6)
pp. 1531-1546
Smooth surface extraction using PDEs is a well-known and widely used technique for visualizing volume data. Existing approaches operate on gridded data and mainly on regular structured grids. When considering unstructured point-based volume data where sample points do not form regular patterns nor are they connected in any form, one would typically resample the data over a grid prior to applying the known PDE-based methods. As resampling inserts interpolation inaccuracies, data providers would rather have segmentation methods operate on the actual unstructured data. We propose an approach that directly extracts smooth surfaces from unstructured point-based volume data without prior resampling or mesh generation.When operating on unstructured data one needs to quickly derive neighborhood informations. The respective information is retrieved by partitioning the 3D domain into cells using a kd-tree and operating on its cells. We exploit neighborhood information to estimate gradients and mean curvature at every sample point using a four-dimensional least-squares fitting approach. Gradients and mean curvature are required for applying the chosen PDE-based method that combines hyperbolic advection to an isovalue of a given scalar field and mean curvature flow. Since we are using an explicit time-integration scheme, time steps are bounded by the Courant-Friedrichs-Lewy condition. To avoid small global time steps, we use asynchronous local integration. We extract the surface by successively fitting a smooth function to the data set. This function is initialized with a signed distance function. For each sample and for every time step we compute the respective gradient, the mean curvature, and a stable time step. With these informations the function is manipulated using an explicit Euler time integration. The process continues with the next sample point in time. If the norm of the function gradient in a sample exceeds a given threshold at some time the function is reinitialized to a signed distance function. The resulting smooth surface is obtained by extracting the zero isosurface from the function using isosurface extraction from unstructured data and rendering the surface using point-based methods.
[1] R. Bracewell, The Fourier Transform and Its Applications. McGraw-Hill Science Engineering, 3 edition, 1999.
[2] D. Breen, R. Whitaker, K. Museth, and L. Zhukov, Level set segmentation of biological volume data sets. In Handbook of Medical Image Analysis, Volume I: Segmentation Part A, pages 415–478, New York, 2005. Kluwer.
[3] R. Courant, K. Friedrichs, and H. Lewy, On partial difference equations of mathematical physics. IBM J., 11: 215–222, 1967.
[4] H. Dym and H. McKean, Fourier Series and Integrals. Academic Press Inc., 1972.
[5] D. Enright, F. Losasso, and R. Fedkiw, A fast and accurate semilagrangian particle level set method. Computers and Structures, 83 (6–7): 479–490, 2004.
[6] J. Escher and G. Simonett, The volume preserving mean curvature flow near spheres. In Proceedings of the American Mathematical Society, volume 126, pages 2789–2796, 1998.
[7] L. C. Evans and J. Spruck, Motion of level sets by mean curvature I. J. Diff. Geometry, 33: 635–681, 1991.
[8] L. C. Evans and J. Spruck, Motion of level sets by mean curvature II. Trans. American Math. Soc., 330 (1), 1992.
[9] L. C. Evans and J. Spruck, Motion of level sets by mean curvature III. J. Geometric Analysis, 2 (2), 1992.
[10] R. Franke and G. M. Nielson, Geometric Modeling: Methods and Applications, chapter Scattered Data Interpolation: A Tutorial and Survey, pages 131–160. Springer Verlag, New York, 1991.
[11] J. H. Friedman, J. L. Bentley, and R. A. Finkel, An algorithm for finding best matches in logarithmic expected time. ACM Trans. Math. Softw., 3 (3): 209–226, 1977.
[12] S. Gottlieb, C.-W. Shu, and E. Tadmor, Strong stability-preserving high-order time discretization methods. SIAM Rev., 43 (1): 89–112, 2001.
[13] S. E. Hieber and P. Koumoutsakos, A lagrangian particle level set method. J. Comput. Phys., 210 (1): 342–367, 2005.
[14] S. Larsson and V. Thome, Partial differential equations with numerical methods. Springer, 2005.
[15] A. E. Lefohn, J. M. Kniss, C. D. Hansen, and R. T. Whitaker, Interactive deformation and visualization of level set surfaces using graphics hardware. In VIS '03: Proceedings of the 14th IEEE Visualization 2003 (VIS'03), page 11, Washington, DC, USA, 2003. IEEE Computer Society.
[16] L. Linsen, K. Müller, and P. Rosenthal, Splat-based ray tracing of point clouds. Journal of WSCG, 15 (1–3), 2007.
[17] J. McNames, A fast nearest-neighbor algorithm based on a principal axis search tree. IEEE Transactions on Pattern Analysis and Machine Intelligence, 23 (9): 964–976, 2001.
[18] R. B. Milne, An Adaptive Level-Set Method. PhD thesis, University of California, Berkeley, 1995.
[19] B. S. Morse, W. Liu, T. S. Yoo, and K. Subramanian, Active contours using a constraint-based implicit representation. In CVPR '05: Proceedings of the 2005 IEEE Computer Society Conference on Computer Vision and Pattern Recognition (CVPR'05) - Volume 1, pages 285–292, Washington, DC, USA, 2005. IEEE Computer Society.
[20] K. Museth, D. E. Breen, L. Zhukov, and R. T. Whitaker, Level set segmentation from multiple non-uniform volume datasets. In VIS '02: Proceedings of the conference on Visualization '02, pages 179–186, Washington, DC, USA, 2002. IEEE Computer Society.
[21] Y. A. Omelchenko and H. Karimabadi, Self-adaptive time integration of flux-conservative equations with sources. J. Comput. Phys., 216 (1): 179–194, 2006.
[22] S. Osher and R. Fedkiw, Level set methods and dynamic implicit surfaces. Springer, 2003.
[23] S. Osher and J. A. Sethian, Fronts propagating with curvature-dependent speed: Algorithms based on hamilton-jacobi formualtions. Journal of Computational Physics, (79): 12–49, 1988.
[24] N. F. Otani, Computer modeling in cardiac electrophysiology. J. Comput. Phys., 161 (1): 21–34, 2000.
[25] S. Park, L. Linsen, O. Kreylos, J. D. Owens, and B. Hamann, A framework for real-time volume visualization of streaming scattered data. In M. Stamminger and J. Hornegger, editors, Proceedings of Tenth International Fall Workshop on Vision, Modeling, and Visualization 2005, pages 225–232,507. DFG Collaborative Research Center, 2005.
[26] S. W. Park, L. Linsen, O. Kreylos, J. D. Owens, and B. Hamann, Discrete Sibson interpolation. IEEE Transactions on Visualization and Computer Graphics, 12 (2): 243–253, 2006.
[27] M. Pauly, R. Keiser, L. P. Kobbelt, and M. Gross, Shape modeling with point-sampled geometry. ACM Trans. Graph., 22 (3): 641–650, 2003.
[28] D. Peng, B. Merriman, S. Osher, H. Zhao, and M. Kang, A pde-based fast local level set method. J. Comput. Phys., 155 (2): 410–438, 1999.
[29] P. Rosenthal and L. Linsen, Direct isosurface extraction from scattered volume data. In Proceedings of Eurographics/IEEE-VGTC Symposium on Visualization, pages 99–106, 2006.
[30] J. A. Sethian, Level Set Methods and Fast Marching Methods. Cambridge University Press, Cambridge, UK, second edition edition, 1999.
[31] J. Strain, Tree methods for moving interfaces. J. Comput. Phys., 151 (2): 616–648, 1999.
[32] J. C. Strikwerda, Finite difference schemes and partial differential equations. Wadsworth Publ. Co., Belmont, CA, USA, 1989.
[33] M. Sussman, A. S. Almgren, J. B. Bell, P. Colella, L. H. Howell, and M. L. Welcome, An adaptive level set approach for incompressible two-phase flows. J. Comput. Phys., 148: 81–124, 1999.
[34] J. W. Thomas, Numerical Partial Differential Equations. Springer, 1998.
Index Terms:
Index Terms—PDEs, surface extraction, level sets, point-based visualization
Citation:
Paul Rosenthal, Lars Linsen, "Smooth Surface Extraction from Unstructured Point-based Volume Data Using PDEs," IEEE Transactions on Visualization and Computer Graphics, vol. 14, no. 6, pp. 1531-1546, Nov./Dec. 2008, doi:10.1109/TVCG.2008.164
