Skip to main content
SpringerLink
Log in

Image-Space Decomposition Algorithms for Sort-First Parallel Volume Rendering of Unstructured Grids

  • Published:
The Journal of Supercomputing Aims and scope Submit manuscript

Abstract

Twelve adaptive image-space decomposition algorithms are presented for sort-first parallel direct volume rendering (DVR) of unstructured grids on distributed-memory architectures. The algorithms are presented under a novel taxonomy based on the dimension of the screen decomposition, the dimension of the workload arrays used in the decomposition, and the scheme used for workload-array creation and querying the workload of a region. For the 2D decomposition schemes using 2D workload arrays, a novel scheme is proposed to query the exact number of screen-space bounding boxes of the primitives in a screen region in constant time. A probe-based chains-on-chains partitioning algorithm is exploited for load balancing in optimal 1D decomposition and iterative 2D rectilinear decomposition (RD). A new probe-based optimal 2D jagged decomposition (OJD) is proposed which is much faster than the dynamic-programming based OJD scheme proposed in the literature. The summed-area table is successfully exploited to query the workload of a rectangular region in constant time in both OJD and RD schemes for the subdivision of general 2D workload arrays. Two orthogonal recursive bisection (ORB) variants are adapted to relax the straight-line division restriction in conventional ORB through using the medians-of-medians approach on regular mesh and quadtree superimposed on the screen. Two approaches based on the Hilbert space-filling curve and graph-partitioning are also proposed. An efficient primitive classification scheme is proposed for redistribution in 1D, and 2D rectilinear and jagged decompositions. The performance comparison of the decomposition algorithms is modeled by establishing appropriate quality measures for load-balancing, amount of primitive replication and parallel execution time. The experimental results on a Parsytec CC system using a set of benchmark volumetric datasets verify the validity of the proposed performance models. The performance evaluation of the decomposition algorithms is also carried out through the sort-first parallelization of an efficient DVR algorithm.

This is a preview of subscription content, log in via an institution to check access.

Access this article

Log in via an institution

Price excludes VAT (USA)
Tax calculation will be finalised during checkout.

Instant access to the full article PDF.

Institutional subscriptions

Similar content being viewed by others

References

  1. C. Aykanat, V. İşler, and B. Özgüç. Efficient parallel spatial subdivision algorithm for object-based parallel ray tracing. Computer-Aided Design, 26(12):883–890, 1994.

    Google Scholar 

  2. S.H. Bokhari. On the mapping problem. IEEE Trans. Computers, 3:207–214, 1981.

    Google Scholar 

  3. J. Challinger. Parallel volume rendering for curvilinear volumes. In Proceedings of the Scalable High Performance Computing Conference, pp. 14–21. IEEE Computer Society Press, April 1992.

  4. J. Challinger. Scalable Parallel Direct Volume Rendering for Nonrectilinear Computational Grids. Ph.D. thesis, University of California, 1993.

  5. J. Challinger. Scalable parallel volume raycasting for nonrectilinear computational grids. In Proceedings of the 1993 Parallel Rendering Symposium, pp. 81–88. IEEE Computer Society Press, October 1993.

  6. F.C. Crow. Summed-area tables for texture mapping. Computer Graphics, 18(3):207–212, 1984.

    Google Scholar 

  7. D. Ellsworth. A multicomputer polygon rendering algorithm for interactive applications. In Proceedings of the 1993 Parallel Rendering Symposium, pp. 43–48. IEEE Computer Society Press, October 1993.

  8. M.P. Garrity. Raytracing irregular volume data. Computer Graphics, 24(5):35–40, 1990.

    Google Scholar 

  9. M. Grigni and F. Manne. On the complexity of the generalized block distribution. Lecture Notes in Computer Science, 1117:319–326, 1996.

    Google Scholar 

  10. G. Karypis and V. Kumar. MeTiS: a software package for partitioning unstructured graphs, partitioning meshes, and computing fill-reducing prderings for sparse matrices version 3.0. University of Minnesota, Department of Computer Science, Army HPC Research Center, Minneapolis, 1998.

    Google Scholar 

  11. T.M. Kurç, H. Kutluca, C. Aykanat, and B. Özgüç. A comparison of spatial subdivision algorithms for sort-first rendering. Lecture Notes in Computer Science, 1225:137–146, 1997.

    Google Scholar 

  12. Tahsin M. Kurç. Parallel rendering on multicomputers. Ph.D. thesis, Bilkent University, Computer Engineering Department, 1997.

  13. H. Kutluca. Image-space decomposition algorithms for sort-first parallel volume rendering of unstructured grids. MS thesis, Bilkent University, Computer Engineering Department, 1997.

  14. H. Kutluca, T.M. Kurç, and C. Aykanat. Experimenting with the communication performance of Parsytec CC system. Technical report BU-CEIS-9811. Computer Engineering Department, Bilkent University, 1998.

  15. K. Ma. Parallel volume ray-casting for unstructured-grid data on distributed-memory multicomputers. In Proceedings of 1995 Parallel Rendering Symposium, pp. 23–30, October 1995.

  16. F. Manne and T. Sørevik. Optimal partitioning of sequences. J. Algorithms, 19:235–249, 1995.

    Google Scholar 

  17. F. Manne and T. Sørevik. Partitioning an array onto a mesh of processors. In Procedings of the 3rd International Workshop on Applied Parallel Computing (PARA'96), pp. 467–476, 1996.

  18. S. Molnar, M. Cox, D. Ellsworth, and H. Fuchs. A sorting classification of parallel rendering. IEEE Computer Graphics and Applications, 14(4):23–32, July 1994.

    Google Scholar 

  19. B. Moon, H.V. Jagadish, C. Faloutsos, and J.H. Saltz. Analysis of the clustering properties of Hilbert space-filling curve. Technical report UMCP-CSD:CS-TR-3611. UMIACS, University of Maryland at College Park, 1996.

  20. C. Mueller. The sort-first rendering architecture for high-performance graphics. In Proceedings of 1995 Symposium on Interactive 3D Graphics, pp. 75–84, 1995.

  21. D.M. Nicol. Rectilinear partitioning of irregular data parallel computations. Journal of Parallel and Disributed Computing, 23:119–134, 1994.

    Google Scholar 

  22. Embedded Parix (EPX) ver. 1.9.2 User's Guide and Programmers Reference Manual. Parsytec GmbH, Germany, 1996.

  23. J.R. Pilkington and S.B. Baden. Dynamic partitioning of non-uniform structured workloads with space-filling curves. IEEE Transactions on Parallel and Distributed Systems, 7(3):288–299, 1996.

    Google Scholar 

  24. F.P. Preparata and M.I. Shamos. Computational Geometry: An Introduction. Springer-Verlag, 1985.

  25. D.R. Roble. A load balanced parallel scanline z-buffer algorithm for the ipsc hypercube. In Proceedings of Pixim'88, pp. 177–192, Paris, France, October 1988.

  26. P. Shirley and A. Tuchman. A polygonal approximation to direct scalar volume rendering. Computer Graphics, 24(5):63–70, 1990.

    Google Scholar 

  27. J.P. Singh, C. Holt, J.L. Hennessy, and A. Gupta. A parallel adaptive fast multipole method. In Proceedings of Supercomputing 93, pp. 54–65, 1993.

  28. S. Whitman. Multiprocessor Methods for Computer Graphics Rendering. Jones and Bartlett Publishers, 1992.

  29. P. L. Williams. em Interactive direct volume rendering of curvilinear and unstructured data. Ph.D. thesis, University of Illinois at Urbana-Champaign, 1992.

  30. P.L. Williams. Visibility ordering meshed polyhedra. ACM Transactions on Graphics, 11(2):103–126, 1992.

    Google Scholar 

  31. R. Yagel and R. Machiraju. Data-parallel volume rendering algorithms. Visual Computer, 11:319–338, 1995.

    Google Scholar 

Download references

Author information

Authors and Affiliations

  1. Computer Engineering Department, Bilkent University, TR-06533, Ankara, Turkey

    Hüuseyin Kutluca & Cevdet Aykanat

  2. Computer Science Department, University of Maryland, College Park, MD, 20742

    Tah¨sin M. Kurç

Authors
  1. Hüuseyin Kutluca
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Tah¨sin M. Kurç
    View author publications

    You can also search for this author in PubMed Google Scholar

  3. Cevdet Aykanat
    View author publications

    You can also search for this author in PubMed Google Scholar

Rights and permissions

Reprints and permissions

About this article

Cite this article

Kutluca, H., Kurç, T.M. & Aykanat, C. Image-Space Decomposition Algorithms for Sort-First Parallel Volume Rendering of Unstructured Grids. The Journal of Supercomputing 15, 51–93 (2000). https://doi.org/10.1023/A:1008169609963

Download citation

  • Issue Date:

  • DOI: https://doi.org/10.1023/A:1008169609963

Search

Navigation