HOME

TheInfoList



OR:

In
3D computer graphics 3D computer graphics, or “3D graphics,” sometimes called CGI, 3D-CGI or three-dimensional computer graphics are graphics that use a three-dimensional representation of geometric data (often Cartesian) that is stored in the computer for th ...
, solid objects are usually modeled by
polyhedra In geometry, a polyhedron (plural polyhedra or polyhedrons; ) is a three-dimensional shape with flat polygonal faces, straight edges and sharp corners or vertices. A convex polyhedron is the convex hull of finitely many points, not all on t ...
. A face of a polyhedron is a planar
polygon In geometry, a polygon () is a plane figure that is described by a finite number of straight line segments connected to form a closed ''polygonal chain'' (or ''polygonal circuit''). The bounded plane region, the bounding circuit, or the two toge ...
bounded by straight line segments, called edges. Curved surfaces are usually approximated by a
polygon mesh In 3D computer graphics and solid modeling, a polygon mesh is a collection of , s and s that defines the shape of a polyhedral object. The faces usually consist of triangles (triangle mesh), quadrilaterals (quads), or other simple convex polyg ...
. Computer programs for
line drawings Line most often refers to: * Line (geometry), object with zero thickness and curvature that stretches to infinity * Telephone line, a single-user circuit on a telephone communication system Line, lines, The Line, or LINE may also refer to: Arts ...
of opaque objects must be able to decide which edges or which parts of the edges are hidden by an object itself or by other objects, so that those edges can be clipped during rendering. This problem is known as hidden-line removal. The first known solution to the hidden-line problem was devised by L. G. Roberts in 1963. However, it severely restricts the model: it requires that all objects be
convex Convex or convexity may refer to: Science and technology * Convex lens, in optics Mathematics * Convex set, containing the whole line segment that joins points ** Convex polygon, a polygon which encloses a convex set of points ** Convex polytope ...
. Ruth A. Weiss of Bell Labs documented her 1964 solution to this problem in a 1965 paper. In 1966
Ivan E. Sutherland Ivan Edward Sutherland (born May 16, 1938) is an American computer scientist and Internet pioneer, widely regarded as a pioneer of computer graphics. His early work in computer graphics as well as his teaching with David C. Evans in that subje ...
listed 10 unsolved problems in computer graphics. Problem number seven was ''"hidden-line removal"''. In terms of
computational complexity In computer science, the computational complexity or simply complexity of an algorithm is the amount of resources required to run it. Particular focus is given to computation time (generally measured by the number of needed elementary operations) ...
, this problem was solved by Devai in 1986.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. Models, e.g. in
computer-aided design Computer-aided design (CAD) is the use of computers (or ) to aid in the creation, modification, analysis, or optimization of a design. This software is used to increase the productivity of the designer, improve the quality of design, improve c ...
, 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 of the edges of the model and the total number of the visible segments of the edges. Visibility can change at the intersection points of the images of the edges. Let denote the total number of the intersection points of the images of the edges. Both and in the worst case, but usually .


Algorithms

Hidden-line algorithms published before 1984A. Appel
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.
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''2) line segments against Θ(''n'') faces takes Θ(''n''3) time in the worst case. Appel's algorithm is also unstable, because an error in visibility will be propagated to subsequent segment endpoints. Ottmann and WidmayerTh. Ottmann and P. Widmayer
Solving visibility problems by using skeleton structures
In ''Proc. Mathematical Foundations of Computer Science 1984'', pp. 459–470, London, UK, 1984. Springer-Verlag.
and Ottmann, Widmayer and
Wood Wood is a porous and fibrous structural tissue found in the stems and roots of trees and other woody plants. It is an organic materiala natural composite of cellulose fibers that are strong in tension and embedded in a matrix of lignin th ...
Th. Ottmann, P. Widmayer, and D. Wood
A worst-case efficient algorithm for hidden-line elimination
''Internat. J. Computer Mathematics'', 18(2):93–119, 1985.
proposed ''O''((''n'' + ''k'') log2 ''n'')-time hidden-line algorithms. Then Nurmi improvedO. Nurmi
A fast line-sweep algorithm for hidden line elimination
''BIT'', 25:466–472, September 1985.
the running time to ''O''((''n'' + ''k'') log ''n''). These algorithms take Θ(''n''2 log2 ''n''), respectively Θ(''n''2 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, it appears that the best one can hope to achieve is Θ(''n''2 log ''n'') worst-case time, and hence Nurmi's algorithm is optimal. However, the log ''n'' factor was eliminated by Devai, who raised the open problem whether the same optimal ''O''(''n''2) upper bound existed for hidden-surface removal. This problem was solved by McKenna in 1987. The intersection-sensitive algorithms are mainly known in the computational-geometry literature. The quadratic upper bounds are also appreciated by the computer-graphics literature: Ghali notes that the algorithms by Devai and McKenna ''"represent milestones in visibility algorithms"'', breaking a theoretical barrier from ''O''(''n''2 log ''n'') to ''O''(''n''2) for processing a scene of ''n'' edges. The other open problem, raised by Devai, 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 an ''O''(log ''n'')-time parallel algorithm using ''n''2 processors for the hidden-line problem under the
concurrent read, exclusive write In computer science, a parallel random-access machine (parallel RAM or PRAM) is a shared-memory abstract machine. As its name indicates, the PRAM is intended as the parallel-computing analogy to the random-access machine (RAM) (not to be confused ...
(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''2), the sequential complexity of the problem, the algorithm is not work-optimal, but it demonstrates that the hidden-line problem is in the 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 proposed an ''O''(log4 ''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 publishedF. Devai
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.
an ''O''(log ''n'')-time hidden-surface, and a simpler, also ''O''(log ''n'')-time, hidden-line algorithm. The hidden-surface algorithm, using ''n''2/log ''n'' CREW PRAM processors, is work-optimal. The hidden-line algorithm uses ''n''2 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''2 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.S. Cook, C. Dwork, and R. Reischuk
Upper and lower time bounds for parallel random access machines without simultaneous writes
''SIAM J. Comput''., 15:87–97, February 1986.
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.


See also

*
Back-face culling In computer graphics, back-face culling determines whether a polygon of a graphical object is drawn. It is a step in the graphical pipeline that tests whether the points in the polygon appear in clockwise or counter-clockwise order when projected ...


References


External links


Patrick-Gilles Maillot's thesis
an extension of the 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.
Vector Hidden Line Removal
an article by Walter Heger with a further description (of the pathological cases) and more citations. 3D rendering Computer graphics algorithms