Editing Hidden-line removal

{{Short description|Problem of finding obscured edges in a wire-frame 3D model}}
[[File:Obj lineremoval.png|thumb|200px|A wire-frame image using hidden-line removal]]

In [[3D computer graphics]], [[Solid geometry|solid objects]] are usually modeled by [[polyhedra]]. A face of a polyhedron is a planar [[polygon]] bounded by straight line segments, called [[Edge (geometry)|edges]]. Curved surfaces are [[Computer representation of surfaces|usually approximated]] by a [[polygon mesh]].  Computer programs for [[Wire-frame model|line drawings]] of opaque objects must be able to decide which edges or which parts of the edges are [[Hidden line|hidden]] by an object itself or by other objects, so that those edges can be [[Clipping (computer graphics)|clipped]] during [[Rendering (computer graphics)|rendering]]. This problem is known as '''hidden-line removal'''.

The first known solution to the hidden-line problem was devised by L. G. Roberts<ref>L. G. Roberts. ''[https://dspace.mit.edu/bitstream/handle/1721.1/11589/33959125-MIT.pdf?sequence=2 Machine perception of three-dimensional solids]''. PhD thesis, Massachusetts Institute of Technology, 1963.</ref> in 1963. However, it severely restricts the model: it requires that all objects be [[Convex set|convex]]. [[Ruth A. Weiss]] of Bell Labs documented her 1964 solution to this problem in a 1965 paper.<ref>Ruth A. Weiss ''[https://ohiostate.pressbooks.pub/app/uploads/sites/45/2017/09/bevision-weiss.pdf BE VISION, A Package of IBM 7090 FORTRAN Programs to Draw Orthographic Views of Combinations of Plane and Quadric Surfaces ]''</ref>
In 1966 [[Ivan E. Sutherland]] listed 10 unsolved problems in computer graphics.<ref>I. E. Sutherland. Ten unsolved problems in computer graphics. ''Datamation'', 12(5):22–27, 1966.</ref>  Problem number seven was ''"hidden-line removal"''.  In terms of [[computational complexity]], this problem was solved by Frank Devai in 1986.<ref name=Devai86>F. Devai. Quadratic bounds for hidden line elimination. In ''Proc. 2nd Annual Symp. on Computational Geometry'', SCG ’86, pp. 269–275, New York, NY, USA, 1986.</ref>

Models, e.g. in [[computer-aided design]], can have thousands or millions of edges. Therefore, a computational-complexity approach expressing resource requirements (such as time and memory) as the function of problem sizes is crucial. Time requirements are particularly important in interactive systems.

Problem sizes for hidden-line removal are the total number {{mvar|n}} of the edges of the model and the total number {{mvar|v}} of the visible segments of the edges.  Visibility can change at the intersection points of the images of the edges.  Let {{mvar|k}} denote the total number of the intersection points of the images of the edges. Both {{math|1=''k'' = Θ(''n''<sup>2</sup>)}} and {{math|1=''v'' = Θ(''n''<sup>2</sup>)}} in the worst case,<ref name=Devai86 /> but usually {{math|''v'' < ''k''}}.

== 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.

== Parallel algorithms ==
In 1988 Devai proposed<ref>F. Devai. An ''O''(log ''N'') parallel time exact hidden-line algorithm. ''Advances in Computer Graphics Hardware II'', pp. 65–73, 1988.</ref> an ''O''(log ''n'')-time parallel algorithm using ''n''<sup>2</sup> processors for the hidden-line problem under the [[concurrent read, exclusive write]] (CREW) parallel random-access machine (PRAM) model of computation.  As the product of the processor number and the running time is asymptotically greater than Θ(''n''<sup>2</sup>), the sequential complexity of the problem, the algorithm is not work-optimal, but it demonstrates that the hidden-line problem is in the [[NC (complexity)|complexity class NC]], i.e., it can be solved in polylogarithmic time by using a polynomial number of processors.

Hidden-surface algorithms can be used for hidden-line removal, but not the other way around. Reif and Sen <ref>J. H. Reif and S. Sen. [http://repository.ias.ac.in/90070/1/4-Pub.pdf An efficient output-sensitive hidden surface removal algorithm and its parallelization]. In ''Proc. 4th Annual Symp. on Computational Geometry'', SCG ’88, pp. 193–200, New York, NY, USA, 1988.</ref> proposed an ''O''(log<sup>4</sup> ''n'')-time algorithm for the hidden-surface problem, using ''O''((''n'' + ''v'')/log ''n'') CREW PRAM processors for a restricted model of polyhedral terrains, where ''v'' is the output size.

In 2011 Devai published<ref name=Devai11>F. Devai. [https://www.researchgate.net/profile/Frank_Devai2/publication/225694183_An_Optimal_Hidden-Surface_Algorithm_and_Its_Parallelization/links/5595457608ae99aa62c6869c.pdf An optimal hidden-surface algorithm and its parallelization]. In ''Computational Science and Its Applications'', ICCSA 2011, volume 6784 of ''Lecture Notes in Computer Science'', pp 17–29. Springer Berlin/Heidelberg, 2011.</ref> an ''O''(log ''n'')-time hidden-surface, and a simpler, also ''O''(log ''n'')-time, hidden-line algorithm. The hidden-surface algorithm, using ''n''<sup>2</sup>/log ''n'' CREW PRAM processors, is work-optimal.

The hidden-line algorithm uses ''n''<sup>2</sup> exclusive read, exclusive write (EREW) PRAM processors.  The EREW model is the PRAM variant closest to real machines.  The hidden-line algorithm does ''O''(''n''<sup>2</sup> log ''n'') work, which is the upper bound for the best sequential algorithms used in practice.

Cook, Dwork and Reischuk gave an Ω(log ''n'') lower bound for finding the maximum of ''n'' integers allowing infinitely many processors of any PRAM without simultaneous writes.<ref>S. Cook, C. Dwork, and R. Reischuk. [https://epubs.siam.org/doi/abs/10.1137/0215006 Upper and lower time bounds for parallel random access machines without simultaneous writes]. ''SIAM J. Comput''., 15:87–97, February 1986.</ref>  Finding the maximum of ''n'' integers is constant-time reducible to the hidden-line problem by using ''n'' processors.  Therefore, the hidden-line algorithm is time optimal.<ref name=Devai11 />
== See also ==
* [[Back-face culling]]
== References ==

{{reflist}}

== External links ==
* [https://sites.google.com/site/patrickmaillot/english Patrick-Gilles Maillot's thesis], an extension of the [[Bresenham's line algorithm|Bresenham line-drawing algorithm]] to perform 3D hidden-lines removal; also published in MICAD '87 proceedings on CAD/CAM and Computer Graphics, page 591, {{ISBN|2-86601-084-1}}.
* [http://wheger.tripod.com/vhl/vhl.htm Vector Hidden Line Removal], an article by Walter Heger with a further description (of the pathological cases) and more citations.

[[Category:3D rendering]]
[[Category:Computer graphics algorithms]]