“The feudal priority algorithm on hidden-surface removal” by Wang and Chen

Development of a real-time shaded rendering approach for a frequently changing viewpoint or view vector is very important in the simulation of 3-D objects in Computer-Aided Design. A new approach is proposed in this paper to meet this demand in a very efficient manner. A pre-processing phase, in which a feudal priority tree is established for all polygons of an object, and a post-processing phase, in which a rendering priority list is searched for from the feudal priority tree for a new viewpoint or view vector, are included in our approach. The most time-consuming work is finished in the pre-processing phase which only has to be executed once for an object, and the relatively simple task is left to the post-processing phase, which is repeated when the viewpoint or view vector is changed. For the pre-processing phase, a static version and a dynamic version are proposed in this paper. The one-way priority relations of all polygons are computed in the former part of the dynamic pre-processing in a more efficient way than that in the static pre-processing, but the latter part of the dynamic pre-processing is still based on the static pre-processing. A new concept of “absolute priority” is introduced to systematically reduce the polygons in which a separating plane is to be searched for so the probability of finding the separating plane is much increased. This is the basis to implement another important concept of “separating before splitting” by which the polygon splittings are much reduced. Hence the efficiency in the pre-processing and the post-processing phases is highly increased.

1. CHEN, HAN-MING. A Real-Time Rendering System for 3-D Objects in Computer-Aided Design and Manufacturing, Ph.D. Dissertation, University of California at Berkeley, May 1991.
2. CHEN, HAN-MING, and ADIGA, S. An Ingenious Algorithm for Hidden-Surface Removal. The Proceedings of The Second International Conference on CAD & CG. September 1991, Hangzhou, China, pp. 159-164.
3. CHEN, HAN-MING, and JIANG, L. S. Partitioning A Concave Polygon into Simply-Connected Polygons. The Proceedings of The Twenty-third Midwestern Mechanics Conference, October 1993, Lincoln, U.S.A., pp.75-77.
4. FOLEY, J. D., VAN DAM, A., FEINER, S. K., and HUGHES, J. F. Computer Graphics: Principles and Practice, second ed. Addison-Wesley, Reading, MA, 1990.
5. FUCHS, H., KEDEM, Z. M., and NAYLOR, B. F. On Visible Surface Generation by A Priori Tree Structures. Computer Graphics, Vo1.14(3), July 1980, pp.124-133.
6. FUCHS, H., ABRAM, G. D., and GRANT, E. D. Near Real-Time Shaded Display of Rigid Objects. Computer Graphics, Vo1.17(3), July 1983, pp.65-72.
7. NAYLOR, B. F. A Priori Based Techniques for Determining Visibility Priority for 3-D Scenes, Ph.D. Dissertation, University of Texas at Dallas, May 1981.
8. NEwEI~I~, M. E., NEwEI~I~, R. G., and S ANCHA, T. L. A Solution to the Hidden Surface Problem. The Proceedings of the ACM National Conference, 1972, pp.443-450.
9. PREPARATA, F. P., and SHAMOS, M. I. Computational Geometry: An Introduction, Springer-Verlag, New York, 1985.
10. SCHUMACKER, e. A., BRAND, B., GILLILAND, M. G., and SHARP, W. H. Study for Applying Computer-Generated Images to Visual Simulation. Technical Report AFHRL-TR- 69-14, NTIS AD700375fR, U.S. Air Force Human Resources Lab., Air Force Systems Command, Brooks AFB, TX, September 1969.
11. SUTHERLAND, I. E., SPROULL, R. F., and SCHUMACKER R. A. Sorting and the Hidden-Surface Problem. The Proceedings of the National Computer Conference, 1973, pp.685-693.
12. SUTHEaLAND, I. E., SPaOUI~L, R. F., and SCHUMACKER, U. A. A Characterization of Ten Hidden-Surface Algorithms. ACM Computing Surveys, Vol.6(1), March 1974, pp.l-55.
13. SUTHEaLAND, I. E., and HODGMAN, a. W. Reentrant Polygon Clipping. Communications of the ACM, Vol.17(1), January 1974, pp.32-42.
14. THIBAULT, W. C., and NAYLOR, B. F. Set Operations on Polyhedra Using Binary Space Partitioning Trees. Computer Graphics, Vol.21(4), July 1987, pp.153-162.
15. YAO, F. F. On the Priority Approach to Hidden-Surface Algorithms. The Proceedings of the IEEE Symposium on the Foundations of Computer Science, 21st Annual, 1980, pp.301-307.