This relies on the useful property that, if the input faces are IID (independently and identically distributed), then the expected number of visible edge pieces is linear in the number of input edges, and I can find them all in expected linear time.

This is remarkable since the total number of intersections of the projected input edges might be superlinear if the edges' lengths do not shrink fast enough. However, in that case, most of those intersections are hidden, and I can delete them in groups w/o spending even constant time per one. (1978)

  1. Parallel Object-Space Hidden Surface Removal. Wm Randolph Franklin and Mohan Kankanhalli. In Proceedings of SIGGRAPH'90, pages 87-94, aug 1990. (BIB)
    Paper.
  2. A linear time exact hidden surface algorithm. Wm Randolph Franklin. In Tutorial: Computer Graphics: Image Synthesis, pages 218-224., 1988. (BIB)
    Paper.
  3. "Adaptive Grid for polyhedral visibility in object space. Wm Randolph Franklin and Varol Akman. Computer Journal, 31(1):56-60, feb 1988. (BIB)
    Paper.
  4. A simple and efficient haloed line algorithm for hidden line elimination. Wm Randolph Franklin and Varol Akman. Computer Graphics Forum, 6(2):103-109, may 1987. (BIB)
    Paper.
  5. An exact hidden sphere algorithm that operates in linear time. Wm Randolph Franklin. Comput. Graph. Image Process., 15:364-379, 1981. (BIB)
  6. A linear time exact hidden surface algorithm. Wm Randolph Franklin. Comput. Graph., 14(3):117-123, 1980. (BIB)
  7. Combinatorics of hidden surface algorithms. Wm Randolph Franklin. PhD thesis, Center for Research in Computing Technology, Harvard Univ., Jun 1978. (BIB)
    Scanned in 4 parts:
    1. Start to chapter 3,
    2. Chapters 4 to 7,
    3. Appendix A,
    4. Appendix B to end.


<< Connected Components Test Results Random | Research Page List | Nearpt3 >>

nn