Info

"A 512x512 image was isosurface.

generated using

a single view

of the bone

larger numbers of processors (> 64) can be explained by load imbalances and the time required to synchronize processors at the required frame rate. The efficiencies would be higher for a larger image.

Table 2 shows the improvements that were obtained through the data bricking and spatial hierarchy optimizations.

5 Example Applications

In this last section, we give examples of the NOISE, view-dependent, and real-time ray tracing algorithms given in the three previous sections. The examples we chose are from large medical imaging data sets, as well as from a large-scale geoscience imaging data set. Further examples of each of the algorithms along with detailed performance analyses can be found in our recent papers on isosurface extraction [16,25,29,35,36]. Figure 15 shows NOISE examples; Fig. 16 shows view-dependent examples, and Figs. 17 and 18 show examples of real-time ray tracing.

TABLE 2 Times in seconds for optimizations for ray tracing the visible humana

View

"A 512 x 512 image was generated on 16 processors using a single view of an isosurface.

FIGURE 15 Mantle convection modeling that was done on a Cray T3D at the Advanced Computing Laboratory at Los Alamos National Laboratory using more than 20 million elements. The left image shows a single, hot, isosurface, while the second adds a cold (blue) transparent isosurface. The third image shows a slice through the mantle with a single isosurface. See also Plate 133.

FIGURE 15 Mantle convection modeling that was done on a Cray T3D at the Advanced Computing Laboratory at Los Alamos National Laboratory using more than 20 million elements. The left image shows a single, hot, isosurface, while the second adds a cold (blue) transparent isosurface. The third image shows a slice through the mantle with a single isosurface. See also Plate 133.

Initial Bricking Hierarchy + bricking

FIGURE 16 Full vs view-dependent isosurface extraction. The isosurfaces were computed based on a user point of view that was above and behind the skull. These images illustrate the large portions of the isosurface that the view-dependent algorithm was able to avoid. See also Plate 134.

Siggraph Woman Muscle

FIGURE 17 Ray tracings of the bone and skin isosurfaces of the visible woman. See also Plate 135.

FIGURE 18 A ray tracing with and
without shadows. See also Plate 136.

Acknowledgments

This work was supported in part by awards from the Department of Energy and the National Science Foundation. The authors thank Peter Shirley, Chuck Hansen, Han-Wei Shen, and Peter-Pike Sloan for their significant contributors to the research presented in this chapter. The Visible Woman data set was obtained from the Visible Human Project of the National Library of Medicine.

References

1. B. Wyvill, G. Wyvill, C. McPheeters. Data structures for soft objects. The Visual Computer, 2:227-234, 1986.

2. William E. Lorensen and Harvey E. Cline. Marching cubes: A high resolution 3D surface construction algorithm. Computer Graphics, 21(4):163-169, July 1987. ACM Siggraph '87 Conference Proceedings.

3. J. Wilhelms and A. Van Gelder. Octrees for faster isosurface generation. Computer Graphics, 24(5):57-62, November 1990.

4. J. Wilhelms and A. Van Gelder. Octrees for faster isosurface generation. ACM Transactions on Graphics, 11(3):201-227, July 1992.

5. T. Itoh and K. Koyamada. Isosurface generation by using extrema graphs. In Visualization '94, pages 77-83. IEEE Computer Society Press, Los Alamitos, CA, 1994.

6. T. Itoh, Y. Yamaguchi, and K. Koyyamada. Volume thinning for automatic isosurface propagation. In Visualization '96 pages 303-310. IEEE Computer Society Press, Los Alamitos, CA, 1996.

7. R. S. Gallagher. Span filter: An optimization schemes for volume visualization of large finite element models. In Proceedings of Visualization '91, pages 68-75. IEEE Computer Soceity Press, Los Alamitos, CA, 1991.

8. M. Giles and R. Haimes. Advanced interactive visualization for CFD. Computer Systems in Engineering, 1(1):51-62, 1990.

9. H. Shen and C. R. Johnson. Sweeping simplicies: A fast isosurface extraction algorithm for unstructured grids. Proceedings of Visualization '95, pages 143-150. IEEE Computer Society Press, Los Alamitos, CA, 1995.

10. J. L. Bentley. Multidimentional binary search trees used for associative search. Communications of the ACM, 18(9):509-516, 1975.

11. M. Blum, R. W. Floyd, V. Pratt, R. L. Rivest, and R. E. Tarjan. Time bounds for selection. J Computer and System Science, 7:448-461, 1973.

12. Sedgewick R. Algorithms in C + +. Addison-Wesley, Reading, MA, 1992.

13. D. T. Lee and C. K. Wong. Worst-case analysis for region and partial region searches in multidimentional binary search trees and balanced quad trees. Acta Information, 9(23):23-29, 1977.

14. J. L. Bentley and Stanat D. F. Analysis of range searches in quad trees. Info. Proc. Lett., 3(6):170-173, 1975.

15. P. Cignoni, C. Montani, E. Puppo, and R. Scopigno. Optimal isosurface extraction from irregular volume data. In Proceedings of IEEE 1996 Symposium on Volume Visualization. ACM Press, 1996.

16. H. Shen, C. D. Hansen, Y. Livnat, and C. R. Johnson. Isosurfacing is span space with utmost efficiency (ISSUE). In Proceedings of Visualization '96, pages 287-294. IEEE Computer Society Press, Los Alamitos, CA, 1996.

17. Ned Greeene. Hierarchical polygon tiling with coverage masks. In Computer Graphics, Annual Conference Series, pages 65-74, August 1996.

18. H.E. Cline, Lorensen W.E., and Ludke S. Two algorithms for the three-dimensional reconstruction of tomograms. Medical Physics, 15(3):320-327, 1988.

19. Philippe Lacroute and Mark Levoy. Fast volume rendering using a shear-warp factorization of the viewing transformation. In Computer Graphics, Annual Conference Series, pages 451-458, ACM SIGGRAPH, 1994.

20. Philippe G. Lacroute. Fast volume rendering using shear-warp factorization of the viewing transformation. Technical Report, Stanford University, September 1995.

21. Chyi-Cheng Lin and Yu-Tai Ching. An efficient volume-rendering algorithm with an analytic approach. The Visual Computer, 12(10):515-526, 1996.

22. Stephen Marschner and Richard Lobb. An evaluationof reconstruction filters for volume rendering. In Proceedings of Visualization '94, pages 100-107, October 1994.

23. Milos Sramek. Fast surface rendering from raster data by voxel traversal using chessboard distance. In Proceedings of Visualization '94 pages 188-195, October 1994.

24. James T. Kajiya. An overview and comparison of rendering methods. A Consumer's and Developer's Guide to Images Synthesis, pages 259-263, 1988. ACM Siggraph '88 Course 12 Notes.

25. Y. Livnat and C.D. Hansen. View dependent isosurface extraction. In IEEE Visualization '98 pages 175-180. IEEE Computer Society, Oct. 1998.

26. Mark Levoy. Display of surfaces from volume data. IEEE Computer Graphics & Applications, 8(3):29-27, 1988.

27. Paolo Sabella. A rendering algorithm for visualizing 3D scalar fields. Computer Graphics, 22(4):51-58, July 1988. ACM Siggraph '88 Conference Proceedings.

28. Craig Upson and Micheal Keeler. V-buffer: Visible volume rendering. Computer Graphics, 22(4):59-64, July 1988. ACM Siggraph '88 Conference Proceedings.

29. Steven Parker, Peter Shirley, Yarden Livnat, Charles Hansen, and Peter-Pike Sloan. Interactive ray tracing for isosurface rendering. In Proceedings of Visualization '98 October 1998.

30. John Amanatides and Andrew Woo. A fast voxel traversal algorithm for ray tracing. In Eurographics '87 1987.

31. Michael B. Cox and David Ellsworth. Application-controlled demand paging for Out-of-Core visualization. In Proceedings of Visualization '97, pages 235-244, October 1997.

32. James Arvo and David Kirk. A survey of ray tracing acceleration techniques. In Andrew S. Glassner, editor, An Introduction to Ray Tracing, Academic Press, San Diego, CA, 1989.

33. Al Globus. Octree optimization. Technical Report RNR-90-011, NASA Ames Research Center, July 1990.

34. Scott Whitman. Multiprocessor Methods for Computer Graphics Rendering. Jones and Bartlett Publishers, Sudbury, MA, 1992.

35. Y Livnat, H. Shen, and C. R. Johnson. A near optimal isosurface extraction algorithm using the span space. IEEE Trans. Vis. Comp. Graphics, 2(1):73-84, 1996.

36. J. Painter, H.P. Bunge, and Y. Livnat. Case study: Mantle convection visualization on the Cray T3D. In Proceedings of IEEE Visualization '96, IEEE Press, Oct. 1996.

0 0

Post a comment