Image-Space Decomposition Algorithms for Sort-First Parallel Volume Rendering of Unstructured Grids
Tóm tắt
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.
Tài liệu tham khảo
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.
S.H. Bokhari. On the mapping problem. IEEE Trans. Computers, 3:207–214, 1981.
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.
J. Challinger. Scalable Parallel Direct Volume Rendering for Nonrectilinear Computational Grids. Ph.D. thesis, University of California, 1993.
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.
F.C. Crow. Summed-area tables for texture mapping. Computer Graphics, 18(3):207–212, 1984.
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.
M.P. Garrity. Raytracing irregular volume data. Computer Graphics, 24(5):35–40, 1990.
M. Grigni and F. Manne. On the complexity of the generalized block distribution. Lecture Notes in Computer Science, 1117:319–326, 1996.
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.
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.
Tahsin M. Kurç. Parallel rendering on multicomputers. Ph.D. thesis, Bilkent University, Computer Engineering Department, 1997.
H. Kutluca. Image-space decomposition algorithms for sort-first parallel volume rendering of unstructured grids. MS thesis, Bilkent University, Computer Engineering Department, 1997.
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.
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.
F. Manne and T. Sørevik. Optimal partitioning of sequences. J. Algorithms, 19:235–249, 1995.
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.
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.
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.
C. Mueller. The sort-first rendering architecture for high-performance graphics. In Proceedings of 1995 Symposium on Interactive 3D Graphics, pp. 75–84, 1995.
D.M. Nicol. Rectilinear partitioning of irregular data parallel computations. Journal of Parallel and Disributed Computing, 23:119–134, 1994.
Embedded Parix (EPX) ver. 1.9.2 User's Guide and Programmers Reference Manual. Parsytec GmbH, Germany, 1996.
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.
F.P. Preparata and M.I. Shamos. Computational Geometry: An Introduction. Springer-Verlag, 1985.
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.
P. Shirley and A. Tuchman. A polygonal approximation to direct scalar volume rendering. Computer Graphics, 24(5):63–70, 1990.
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.
S. Whitman. Multiprocessor Methods for Computer Graphics Rendering. Jones and Bartlett Publishers, 1992.
P. L. Williams. em Interactive direct volume rendering of curvilinear and unstructured data. Ph.D. thesis, University of Illinois at Urbana-Champaign, 1992.
P.L. Williams. Visibility ordering meshed polyhedra. ACM Transactions on Graphics, 11(2):103–126, 1992.
R. Yagel and R. Machiraju. Data-parallel volume rendering algorithms. Visual Computer, 11:319–338, 1995.