Isosurface Extraction and Spatial Filtering using Persistent Octree (POT)
|
We propose a novel Persistent OcTree (POT) indexing structure for accelerating isosurface extraction and spatial filtering from volumetric data. This data structure efficiently handles a wide range of visualization problems such as the generation of view-dependent isosurfaces, ray tracing, and isocontour slicing for high dimensional data. POT can be viewed as a hybrid data structure between the interval tree and the Branch-On-Need Octree (BONO) in the sense that it achieves the asymptotic bound of the interval tree for identifying the active cells corresponding to an isosurface and is more efficient than BONO for handling spatial queries. We encode a compact octree for each isovalue. Each such octree contains only the corresponding active cells, in such a way that the combined structure has linear space. The inherent hierarchical structure associated with the active cells enables very fast filtering of the active cells based on spatial constraints. We demonstrate the effectiveness of our approach by performing view-dependent isosurfacing on a wide variety of volumetric data sets and 4D isocontour slicing on the time-varying Richtmyer-Meshkov instability dataset.
[1] 1283 U. Bordoloi and H.-W. Shen, Space efficient fast isosurface extraction for large datasets. In IEEE Visualization '03, pages 201–208, 2003.
[2] A. Boroujerdi and B. Moret, Persistency in computational geometry. In Proc. 7th Canadian Conf. Comp. Geometry (CCCG 95), pages 241–246, Québec, Canada, 1995.
[3] Y.-J. Chiang, C. T. Silva, and W. J. Schroeder, Interactive out-of-core isosurface extraction. In IEEE Visualization '98, pages 167–174, 1998.
[4] P. Cignoni, P. Marino, C. Montani, E. Puppo, and R. Scopigno, Speeding up isosurface extraction using interval trees. IEEE Transactions on Visualization and Computer Graphics, 3 (2): 158–170, 1997.
[5] J. Driscoll, N. Sarnak, D. Sleator, and R. Tarjan, Making data structures persistent. Journal of Computer and System Sciences, 38: 86–124, 1989.
[6] H. Edelsbrunner, J. Harer, A. Mascarenhas, and V. Pascucci, Time-varying reeb graphs for continuous space-time data. In SCG'04: Proceedings of the twentieth annual symposium on computational geometry, pages 366–372, New York, NY, USA, 2004.
[7] R. S. Gallagher, Span filtering: an optimization scheme for volume visualization of large finite element models. In VIS '91: Proceedings of the 2nd conference on Visualization '91, pages 68–75, 1991.
[8] N. Greene, Hierarchical polygon tiling with coverage masks. In SIGGRAPH '96: Proceedings of the 23rd annual conference on Computer graphics and interactive techniques, pages 65–74, New York, NY, USA, 1996.
[9] B. Gregorski, M. Duchaineau, P. Lindstrom, V. Pascucci, and K. I. Joy, Interactive view-dependent rendering of large isosurfaces. In IEEE Visualization '02, pages 475–484, 2002.
[10] P. Gupta, R. Janardan, and M. Smid, Further results on generalized intersection searching problems: counting, reporting, and dynamization. Journal of Algorithms, 19: 282–317, 1995.
[11] Y. Livnat and C. Hansen, View dependent isosurface extraction. In IEEE Visualization '98, pages 175–180, 1998.
[12] Y. Livnat and C. Hansen, Dynamic view dependent isosurface extraction. Technical Report UUSCI-2003-004, Scientific Computating and Imaging Institute, University of Utah, Salt Lake City, UT 84112, USA, 2002.
[13] Y. Livnat, H.-W. Shen, and C. R. Johnson, A near optimal isosurface extraction algorithm using the span space. IEEE Transactions on Visualization and Computer Graphics, 2 (1): 73–84, 1996.
[14] Y. Livnat and X. Tricoche, Interactive point-based isosurface extraction. In IEEE Visualization '04, pages 457–464, 2004.
[15] W. E. Lorensen and H. E. Cline, Marching Cubes: A high resolution 3D surface construction algorithm. ACM SIGGRAPH Computer Graphics, 21 (4): 163–169, 1987.
[16] A. Mascarenhas, M. Isenburg, V. Pascucci, and J. Snoeyink, Encoding volumetric grids for streaming isosurface extraction. In 2nd International Symposium on 3D Data Processing, Visualization and Transmission (3DPVT 2004), pages 665–672, 2004.
[17] A. A. Mirin, D. H. Porter, P. R. Woodward, L. J. Shieh, S. W. White, R. H. Cohen, B. C. Curtis, W. P. Dannevik, A. M. Dimits, M. A. Duchaineau, D. E. Eliason, D. R. Schikore, and S. E. Anderson, Very high resolution simulation of compressible turbulence on the IBM-SP system. In Proceedings of the 1999 ACM/IEEE Conference on Supercomputing (CDROM), 1999.
[18] S. Parker, P. Shirley, Y. Livnat, C. Hansen, and P.-P. Sloan, Interactive ray tracing for isosurface rendering. In IEEE Visualization '98, pages 233–238, 1998.
[19] S. Pesco, P. Lindstrom, V. Pascucci, and C. T. Silva, Implicit occluders. In Proceedigns of the IEEE Symposium on Volume Visualization and Graphics, pages 47–54, Austin, Texas, 2004.
[20] N. Sarnak and R. E. Tarjan, Planar point location using persistent search trees. Communications of the ACM, 29 (7): 669–679, 1986.
[21] H.-W. Shen, Isosurface extraction in time-varying fields using a temporal hierarchical index tree. In IEEE Visualization '98, pages 159–166, 1998.
[22] H.-W. Shen, L.-J. Chiang, and K.-L. Ma, A fast volume rendering algorithm for time-varying fields using a time-space partition (TSP) tree. In IEEE Visualization '99, pages 371–377, 1999.
[23] H.-W. Shen, C. D. Hansen, Y. Livnat, and C. R. Johnson, Isosurfacing in span space with utmost efficiency (ISSUE). In IEEE Visualization '96, pages 287–294, 1996.
[24] Q. Shi and J. JaJa, Optimal and near-optimal algorithms for generalized intersection reporting on pointer machines. Information Processing Letters, 95: 382–388, 2005.
[25] Q. Shi and J. JaJa, Efficient isosurface extraction for large scale time-varying data using the persistent hyperoctree (phot). Technical Report CS-TR-4776, Institute of Advanced Computer Studies (UMIACS), University of Maryland, 2006.
[26] P. Sutton, C. Hansen, H.-W. Shen, and D. Schikore, A case study of isosurface extraction algorithm performance. In 2nd Joint Eurographics-IEEE TCCG Symposium on Visualization, pages 259–268, 2000.
[27] P. Sutton and C. D. Hansen, Isosurface extraction in time-varying fields using a Temporal Branch-on-Need Tree (T-BON). In IEEE Visualization '99, pages 147–153, 1999.
[28] K. W. Waters, C. S. Co, and K. I. Joy, Isosurface extraction using fixed-sized buckets. In EUROGRAPHICS - IEEE VGTC Symposium on Visualization, pages 207–214, 2005.
[29] C. Weigle and D. C. Banks, Extracting iso-valued features in 4-dimensional scalar fields. In Proceedings of the 1998 IEEE Symposium on Volume Visualization, pages 103–110, 1998.
[30] J. Wilhelms and A. van Gelder, Octrees for faster isosurface generation. ACM Transactions on Graphics, 11 (3): 201–227, 1992.
Index Terms:
scientific visualization, isosurface extraction, indexing.
Citation:
Qingmin Shi, Joseph JaJa, "Isosurface Extraction and Spatial Filtering using Persistent Octree (POT)," IEEE Transactions on Visualization and Computer Graphics, vol. 12, no. 5, pp. 1283-1290, Sept. 2006, doi:10.1109/TVCG.2006.157
PURCHASE ARTICLE: $19
IEEE Xplore Subscribers
Digg
Furl
Spurl
Blink
Simpy
Google
Del.icio.us
Y!MyWeb