Take a look at the new version of this page: [ beta version ]. Tell us what you think.

ABSTRACT

Visibility determination is one of the oldest problems in computer graphics. The visibility, in terms of back-to-front polygon visibility ordering, can be determined by updating a priority list as the viewpoint moves. A new list-priority algorithm, utilizing a property of Voronoi diagrams, is proposed in this paper. In the preprocessing phase, the 3D space is divided into Voronoi cells in order to cluster polygons that can be assigned a fixed set of priority orders within the cluster. and during the post-processing phase, the clusters and contained polygons are depth-sorted correctly. The most time-consuming work is undertaken during the pre-processing phase that only has to be executed once for the scene. All the polygons in a cluster are pre-computed to obtain the view independent priority order within the cluster. Thus, a relatively simple task is left in the post-processing phase, which is only to sort the clusters repeatedly when the viewpoint is changed. One reason to explore list-priority algorithm is because they offer flexibility that hardware configuration (such as Z-buffer approach) do not possess. One example is that of rendering with the correct treatment of the translucency effects. Translucency is an important graphics effect that can be used to increase the realism of the rendered scene or to enable more effective visual inspection in visualization.

REFERENCES

• 1: Pankaj K. Agarwal , T. M. Murali , Jeffrey Scott Vitter, Practical techniques for constructing binary space partitions for orthogonal rectangles, Proceedings of the thirteenth annual symposium on Computational geometry, p.382-384, June 04-06, 1997, Nice, France [doi>10.1145/262839.263011]
• 2: Han-Ming Chen , Wen-Teng Wang, The feudal priority algorithm on hidden-surface removal, Proceedings of the 23rd annual conference on Computer graphics and interactive techniques, p.55-64, August 1996 [doi>10.1145/237170.237204]
• 3: Dur, A., and Leimgruber, S. 2003. A practical list-priority algorithm for 3d polygons. Journal of Graphics Tools 8, 25--36.
• 4: James D. Foley , Andries van Dam , Steven K. Feiner , John F. Hughes, Computer graphics: principles and practice (2nd ed.), Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1990
• 5: Henry Fuchs , Zvi M. Kedem , Bruce Naylor, Predetermining visibility priority in 3-D scenes (Preliminary Report), Proceedings of the 6th annual conference on Computer graphics and interactive techniques, p.175-181, August 08-10, 1979, Chicago, Illinois, United States
• 6: Henry Fuchs , Zvi M. Kedem , Bruce F. Naylor, On visible surface generation by a priori tree structures, Proceedings of the 7th annual conference on Computer graphics and interactive techniques, p.124-133, July 14-18, 1980, Seattle, Washington, United States
• 7: Henry Fuchs , Gregory D. Abram , Eric D. Grant, Near real-time shaded display of rigid objects, ACM SIGGRAPH Computer Graphics, v.17 n.3, p.65-72, July 1983
• 8: James, A., and Day, A. M. 1998. The priority face determination tree for hidden surface removal. Computer Graphics Forum 17, 55--71.
• 9: Morer, P., Garcia-Alonso, A. M., and Flaquer, J. 1995. Optimization of a priority list algorithm for 3-d rendering of buildings. Computer Graphics Forum 14, 217--227.
• 10: Bruce Fountain Naylor, A priori based techniques for determining visibility priority for 3-d scenes, 1981
• 11: Schumacker, R. A., Brand, B., Gilliland, M. G., and Sharp, W. H. 1969. Study for applying computer-generated images to visual simulation. Technical Report AFHRL-TR-69-14, Air Force Human Resources Lab.
• 12: Sutherland, I. E., Sproull, R. F., and Schumacker, R. A. 1973. Sorting and the hidden-surface problem. In Proceedings of the National Computer Conference, 685--693.
• 13: Ivan E. Sutherland , Robert F. Sproull , Robert A. Schumacker, A Characterization of Ten Hidden-Surface Algorithms, ACM Computing Surveys (CSUR), v.6 n.1, p.1-55, March 1974 [doi>10.1145/356625.356626]
• 14: Yao, F. F. 1980. On the priority approach to hidden-surface algorithms. In Proceedings of the IEEE Symposium on the Foundations of Computer Science, 21st Annual, 301--307.

INDEX TERMS

Primary Classification:
  I. Computing Methodologies
  I.3 COMPUTER GRAPHICS
      I.3.6 Methodology and Techniques
          Subjects: Graphics data structures and data types

Additional Classification:
  I. Computing Methodologies
  I.3 COMPUTER GRAPHICS
      I.3.7 Three-Dimensional Graphics and Realism

Keywords:
Voronoi diagram, depth sorting, transparency rendering, visibility determination