Linear-Time Object-Space Hidden Surface Algorithm

Research archive · original page Research.LinearObjectSpaceHiddenSurfaces · last recorded update 2009-11-15

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)

Wm Randolph Franklin and Mohan Kankanhalli. Parallel object-space hidden surface removal. In Proceedings of SIGGRAPH'90, volume 24, 87–94. August 1990.

Paper / file · Download BibTeX

BibTeX

@inproceedings{fk-poshs-90-in-geom,
    author = "Franklin, Wm Randolph and Kankanhalli, Mohan",
    title = "Parallel Object-Space Hidden Surface Removal",
    booktitle = "Proceedings of SIGGRAPH'90",
    journal = "Comput. Graph.",
    comments = "Dallas, Texas",
    volume = "24",
    month = "August",
    year = "1990",
    pages = "87--94",
    fulltext = "https://wrfranklin.org/p/62-siggraph90-parallel.pdf",
    href = "\bibhref{62-siggraph90-parallel}",
    mykey = "vis3dobj kankanhalli",
    keywords = "computer graphics, parallel computation, hidden line/surface elimination, grids"
}

Wm Randolph Franklin. A linear time exact hidden surface algorithm. In Kenneth I. Joy and others, editors, Tutorial: Computer Graphics: Image Synthesis, pages 218–224. 1988.

Download BibTeX

BibTeX

@incollection{f-ltehs-88,
    author = "Franklin, Wm Randolph",
    editor = "Joy, Kenneth I. and others",
    title = "A linear time exact hidden surface algorithm",
    booktitle = "Tutorial: Computer Graphics: Image Synthesis",
    year = "1988",
    pages = "218--224",
    succeeds = "f-ltehs-80",
    precedes = "f-ehsao-81",
    mykey = "vis3dobj",
    keywords = "computer graphics, hidden line/surface elimination"
}

Paper.

Wm Randolph Franklin and Varol Akman. Adaptive grid for polyhedral visibility in object space, an implementation. Computer Journal, 31(1):56–60, February 1988.

Paper / file · Download BibTeX

BibTeX

@article{fa-agpvo-88-in-geom,
    author = "Franklin, Wm Randolph and Akman, Varol",
    title = "Adaptive Grid for polyhedral visibility in object space, an implementation",
    journal = "Computer Journal",
    volume = "31",
    number = "1",
    pages = "56-60",
    month = "February",
    year = "1988",
    fulltext = "https://wrfranklin.org/p/43-cj88-polyvis.pdf",
    href = "\bibhref{43-cj88-polyvis}",
    mykey = "akman vis3dobj",
    keywords = "computer graphics, hidden line/surface elimination"
}

Wm Randolph Franklin and Varol Akman. A simple and efficient haloed line algorithm for hidden line elimination. Computer Graphics Forum, 6(2):103–109, May 1987.

Paper / file · Download BibTeX

BibTeX

@article{fa-sehla-87,
    author = "Franklin, Wm Randolph and Akman, Varol",
    title = "A simple and efficient haloed line algorithm for hidden line elimination",
    journal = "Computer Graphics Forum",
    volume = "6",
    number = "2",
    pages = "103-109",
    month = "May",
    year = "1987",
    fulltext = "https://wrfranklin.org/p/42-cgf87-haloed.pdf",
    href = "\bibhref{42-cgf87-haloed}",
    mykey = "akman vis3dobj",
    keywords = "computer graphics, hidden line/surface elimination"
}

Wm Randolph Franklin. An exact hidden sphere algorithm that operates in linear time. Comput. Graph. Image Process., 15:364–379, 1981.

Paper / file · Download BibTeX

BibTeX

@article{f-ehsao-81,
    author = "Franklin, Wm Randolph",
    title = "An exact hidden sphere algorithm that operates in linear time",
    journal = "Comput. Graph. Image Process.",
    volume = "15",
    year = "1981",
    pages = "364--379",
    oldlabel = "geom-224",
    fulltext = "https://wrfranklin.org/p/8-cgip81-hsa.pdf",
    href = "\bibhref{8-cgip81-hsa}",
    succeeds = "f-ltehs-80",
    mykey = "vis3dobj",
    keywords = "computer graphics, hidden line/surface elimination"
}

Wm Randolph Franklin. A linear time exact hidden surface algorithm. Comput. Graph., 14(3):117–123, 1980.

Paper / file · Download BibTeX

BibTeX

@article{f-ltehs-80-in-geom,
    author = "Franklin, Wm Randolph",
    title = "A linear time exact hidden surface algorithm",
    booktitle = "Proc. SIGGRAPH '80",
    journal = "Comput. Graph.",
    volume = "14",
    number = "3",
    year = "1980",
    pages = "117--123",
    oldlabel = "geom-223",
    precedes = "f-ltehs-88",
    fulltext = "https://wrfranklin.org/p/7-siggraph80-linear-hsa.pdf",
    href = "\bibhref{7-siggraph80-linear-hsa}",
    keywords = "computer graphics, hidden line/surface elimination",
    mykey = "vis3dobj",
    portal = "\url{http://portal.acm.org/citation.cfm?id= 807480\&dl= GUIDE\&coll= GUIDE\&CFID= 52002891\&CFTOKEN= 56467748}"
}

Wm Randolph Franklin. Combinatorics of hidden surface algorithms. Technical Report, Center for Research in Computing Technology, Harvard Univ., Cambridge, MA, June 1978.

Paper / file · Download BibTeX

BibTeX

@PhdThesis{f-chsa-78,
    author = "Franklin, Wm Randolph",
    title = "Combinatorics of hidden surface algorithms",
    type = "Technical {Report}",
    number = "TR-12-78",
    school = "Center for Research in Computing Technology, Harvard Univ.",
    address = "Cambridge, MA",
    year = "1978",
    month = "June",
    oldlabel = "geom-221",
    href = "\bibhrefthesis{0-harvard78-thesis}",
    fulltext = "https://wrfranklin.org/p/0-harvard78-thesis.pdf",
    comments = "Thesis w/o appendices available as a TR from CRCT. Complete thesis available only on microfilm from Harvard, since Harvard did not then subscribe to UMI.",
    mykey = "vis3dobj",
    keywords = "computer graphics, hidden line/surface elimination"
}