|
Published Articles >> Table of Contents >> Abstract
March/April 2004 - (Vol. 10, No. 2)
pp. 130-141
Isosurface Construction in Any Dimension Using Convex Hulls
Praveen Bhaniramka
Rephael Wenger
Roger Crawfis, IEEE Computer Society
Full Article Text:
   
DOI Bookmark: http://doi.ieeecomputersociety.org/10.1109/TVCG.2004.1260765
Send link to a friend
| Abstract |
|
We present an algorithm for constructing isosurfaces in any dimension. The input to the algorithm is a set of scalar values in a d-dimensional regular grid of (topological) hypercubes. The output is a set of (d-1)-dimensional simplices forming a piecewise linear approximation to the isosurface. The algorithm constructs the isosurface piecewise within each hypercube in the grid using the convex hull of an appropriate set of points. We prove that our algorithm correctly produces a triangulation of a (d-1)-manifold with boundary. In dimensions three and four, lookup tables with 2^8 and 2^{16} entries, respectively, can be used to speed the algorithm's running time. In three dimensions, this gives the popular Marching Cubes algorithm. We discuss applications of four-dimensional isosurface construction to time varying isosurfaces, interval volumes, and morphing.
|
 References
|
[1] P. Bhaniramka, R. Wenger, and R. Crawfis, Isosurfacing in Higher Dimensions Proc. Visualization 2000, T. Ertl, B. Hamann, and A. Varshney, eds., pp. 267-273, 2000.
[2] K.L. Clarkson, K. Mehlhorn, and R. Seidel, Four Results on Randomized Incremental Constructions Computational Geometric Theory Applications, vol. 3, pp. 185-212, 1993.
[3] M.J. Dürst, Additional Reference to Marching Cubes Computer Graphics, vol. 22, pp. 72-73, 1988.
[4] I. Fujishiro, Y. Maeda, H. Sato, and Y. Takeshima, Volumetric Data Exploration Using Interval Volume IEEE Trans. Visualization and Computer Graphics, vol. 2, no. 2, June 1996.
[5] W.E. Lorensen and H.E. Cline, Marching Cubes: A High Resolution 3D Surface Construction Algorithm Computer Graphics (Proc. SIGGRAPH '87), M.C. Stone, ed., pp. 163-169, July 1987.
[6] N. Max, Consistent Subdivision of Convex Polyhedra into Tetrahedra J. Graphics Tools, vol. 6, no. 3, pp. 29-36, 2002.
[7] N. Max, P. Hanrahan, and R. Crawfis, Area and Volume Coherence for Efficient Visualization of 3D Scalar Functions Computer Graphics (San Diego Workshop Volume Visualization), pp. 27-33, Nov. 1990.
[8] C. Montani, R. Scateni, and R. Scopigno, A Modified Look-Up Table for Implicit Disambiguation of Marching Cubes Visual Computer, vol. 10, pp. 353-355, 1994.
[9] G.M. Nielson and B. Hamann, The Asymptotic Decider: Removing the Ambiguity in Marching Cubes Proc. Visualization '91, pp. 83-91, 1991.
[10] G.M. Nielson and J. Sung, Interval Volume Tetrahedrization Proc. IEEE Visualization '97, R. Yagel and H. Hagen, eds., pp. 221-228, Nov. 1997.
[11] H.-W. Shen, Isosurface Extraction in Time-Varying Fields Using a Temporal Hierarchical Index Tree Proc. IEEE Visualization '98, D. Ebert, H. Hagen, and H. Rushmeier, eds., pp. 159-166, Oct. 1998.
[12] P. Shirley and A. Tuchman, A Polygonal Approximation to Direct Scalar Volume Rendering Proc. Volume Visualization Workshop, pp. 63-70, 1990.
[13] P.M. Sutton and C.D. Hansen, Isosurface Extraction in Time-Varying Fields Using a Temporal Branch-on-Need Tree (T-BON) Proc. IEEE Visualization '99, D. Ebert, M. Gross, and B. Hamann, eds., pp. 147-154, Oct. 1999.
[14] C. Weigle and D.C. Banks, Complex-Valued Contour Meshing Proc. IEEE Visualization '96, R. Yagel and G.M. Nielson, eds., pp. 173-180, Oct. 1996.
[15] C. Weigle and D.C. Banks, Extracting Iso-Valued Features in 4-Dimensional Scalar Fields Proc. 1998 Volume Visualization Symp., pp. 103-110, Oct. 1998.
[16] J. Wilhelms and A.V. Gelder, Multi-Dimensional Trees for Controlled Volume Rendering and Compression Proc. 1994 Symp. Volume Visualization, A. Kaugman and W. Krueger, eds., pp. 27-34, Oct. 1994.
[17] J. Wilhelms and A.V. Gelder, Octrees for Faster Isosurface Generation ACM Trans. Graphics, vol. 11, pp. 201-227, July 1992.
|
 Additional Information
|
Index Terms- Scientific visualization, multidimensional visualization, isosurface, contour, interval volumes, morphing, time varying data.
Citation:
Praveen Bhaniramka, Rephael Wenger, Roger Crawfis,
"Isosurface Construction in Any Dimension Using Convex Hulls,"
IEEE Transactions on Visualization and Computer Graphics,
vol. 10,
no. 2,
pp. 130-141,
Mar/Apr,
2004
|
|
RSS Feed