Editing Hidden-line removal (section)

== Algorithms ==
Hidden-line algorithms published before 1984<ref name=Appel67>A. Appel. [http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.94.6457&rep=rep1&type=pdf The notion of quantitative invisibility and the machine rendering of solids]. In ''Proc. 22nd National Conference'', ACM ’67, pp. 387–393, New York, NY, USA, 1967.</ref><ref>R. Galimberti and U. Montanari. [https://dl.acm.org/citation.cfm?id=362921 An algorithm for hidden line elimination]. ''Commun. ACM'', 12(4):206–211, April 1969.</ref><ref>Ch. Hornung. [https://www.sciencedirect.com/science/article/pii/009784938290005X An approach to a calculation-minimized hidden line algorithm]. ''Computers & Graphics'', 6(3):121–126, 1982.</ref><ref>P. P. Loutrel. [https://ieeexplore.ieee.org/abstract/document/1671491/ A solution to the hidden-line problem for computer-drawn polyhedra]. ''IEEE Trans. Comput''., 19(3):205–213, March 1970.</ref> divide edges into line segments by the intersection points of their images, and then test each segment for visibility against each face of the model.  Assuming a model of a collection of polyhedra with the boundary of each topologically equivalent to a sphere and with faces topologically equivalent to disks, according to Euler's formula, there are Θ(''n'') faces.  Testing Θ(''n''<sup>2</sup>) line segments against Θ(''n'') faces takes Θ(''n''<sup>3</sup>) time in the worst case.<ref name=Devai86 />  Appel's algorithm<ref name=Appel67 /> is also unstable, because an error in visibility will be propagated to subsequent segment endpoints.<ref>J. F. Blinn. Fractional invisibility. ''IEEE Comput. Graph. Appl''., 8(6):77–84, November 1988.</ref>

Ottmann and Widmayer<ref name=Ottmann1>Th. Ottmann and P. Widmayer. [https://link.springer.com/chapter/10.1007/BFb0030329 Solving visibility problems by using skeleton structures]. In ''Proc. Mathematical Foundations of Computer Science 1984'', pp. 459–470, London, UK, 1984. Springer-Verlag.</ref> 
and Ottmann, Widmayer and [[Derick Wood|Wood]]<ref name=Ottmann2>Th. Ottmann, P. Widmayer, and [[Derick Wood|D. Wood]]. [https://www.tandfonline.com/doi/abs/10.1080/00207168508803482 A worst-case efficient algorithm for hidden-line elimination]. ''Internat. J. Computer Mathematics'', 18(2):93–119, 1985.</ref>
proposed ''O''((''n'' + ''k'') log<sup>2</sup> ''n'')-time hidden-line algorithms.  Then Nurmi improved<ref name=Nurmi>O. Nurmi. [https://link.springer.com/article/10.1007/BF01935366 A fast line-sweep algorithm for hidden line elimination]. ''BIT'', 25:466–472, September 1985.</ref> the running time to ''O''((''n'' + ''k'') log ''n'').  These algorithms take Θ(''n''<sup>2</sup> log<sup>2</sup> ''n''), respectively Θ(''n''<sup>2</sup> log ''n'') time in the worst case, but if ''k'' is less than quadratic, can be faster in practice.

Any hidden-line algorithm has to determine the union of Θ(''n'') hidden intervals on ''n'' edges in the worst case.  As Ω(''n'' log ''n'') is a lower bound for determining the union of ''n'' intervals,<ref>M. L. Fredman and B. Weide. On the complexity of computing the measure of U[a<sub>i</sub>, b<sub>i</sub>]. ''Commun. ACM'', 21:540–544, July 1978.</ref>
it appears that the best one can hope to achieve is Θ(''n''<sup>2</sup> log ''n'') worst-case time, and hence Nurmi's algorithm is optimal.

However, the log ''n'' factor was eliminated by Devai,<ref name=Devai86 /> who raised the open problem whether the same optimal ''O''(''n''<sup>2</sup>) upper bound existed for hidden-surface removal.  This problem was solved by McKenna in 1987.<ref>M. McKenna. Worst-case optimal hidden-surface removal. ''ACM Trans. Graph.'', 6:19–28, January 1987.</ref>

The intersection-sensitive algorithms<ref name=Ottmann1 /><ref name=Ottmann2 /><ref name=Nurmi /> are mainly known in the computational-geometry literature.  The quadratic upper bounds are also appreciated by the computer-graphics literature: Ghali notes<ref>Sh. Ghali. [http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.81.7877&rep=rep1&type=pdf A survey of practical object space visibility algorithms]. SIGGRAPH Tutorial Notes, 1(2), 2001.</ref> that the algorithms by Devai and McKenna ''"represent milestones in visibility algorithms"'', breaking a theoretical barrier from ''O''(''n''<sup>2</sup> log ''n'') to ''O''(''n''<sup>2</sup>) for processing a scene of ''n'' edges.

The other open problem, raised by Devai,<ref name=Devai86 /> of whether there exists an ''O''(''n'' log ''n'' + ''v'')-time hidden-line algorithm, where ''v'', as noted above, is the number of visible segments, is still unsolved at the time of writing.