Hidden-line removal

Last updated
A wire-frame image using hidden-line removal Obj lineremoval.png
A wire-frame image using hidden-line removal

Solid objects are usually modeled by polyhedra in a computer representation. A face of a polyhedron is a planar polygon bounded by straight line segments, called edges. Curved surfaces are usually approximated by a polygon mesh. Computer programs for line drawings 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. This problem is known as hidden-line removal.

Contents

The first known solution to the hidden-line problem was devised by L. G. Roberts [1] in 1963. However, it severely restricts the model: it requires that all objects be convex. Ruth A. Weiss of Bell Labs documented her 1964 solution to this problem in a 1965 paper. [2] In 1966 Ivan E. Sutherland listed 10 unsolved problems in computer graphics. [3] Problem number seven was "hidden-line removal". In terms of computational complexity, this problem was solved by Devai in 1986. [4]

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 n of the edges of the model and the total number v of the visible segments of the edges. Visibility can change at the intersection points of the images of the edges. Let k denote the total number of the intersection points of the images of the edges. Both k = Θ(n2) and v = Θ(n2) in the worst case, [4] but usually v < k.

Algorithms

Hidden-line algorithms published before 1984 [5] [6] [7] [8] 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 Θ(n2) line segments against Θ(n) faces takes Θ(n3) time in the worst case. [4] Appel's algorithm [5] is also unstable, because an error in visibility will be propagated to subsequent segment endpoints. [9]

Ottmann and Widmayer [10] and Ottmann, Widmayer and Wood [11] proposed O((n + k) log2 n)-time hidden-line algorithms. Then Nurmi improved [12] the running time to O((n + k) log n). These algorithms take Θ(n2 log2 n), respectively Θ(n2 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, [13] it appears that the best one can hope to achieve is Θ(n2 log n) worst-case time, and hence Nurmi's algorithm is optimal.

However, the log n factor was eliminated by Devai, [4] who raised the open problem whether the same optimal O(n2) upper bound existed for hidden-surface removal. This problem was solved by McKenna in 1987. [14]

The intersection-sensitive algorithms [10] [11] [12] are mainly known in the computational-geometry literature. The quadratic upper bounds are also appreciated by the computer-graphics literature: Ghali notes [15] that the algorithms by Devai and McKenna "represent milestones in visibility algorithms", breaking a theoretical barrier from O(n2 log n) to O(n2) for processing a scene of n edges.

The other open problem, raised by Devai, [4] 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 [16] an O(log n)-time parallel algorithm using n2 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 Θ(n2), 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 [17] 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 published [18] an O(log n)-time hidden-surface, and a simpler, also O(log n)-time, hidden-line algorithm. The hidden-surface algorithm, using n2/log n CREW PRAM processors, is work-optimal.

The hidden-line algorithm uses n2 exclusive read, exclusive write (EREW) PRAM processors. The EREW model is the PRAM variant closest to real machines. The hidden-line algorithm does O(n2 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. [19] 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. [18]

Related Research Articles

The painter’s algorithm is an algorithm for visible surface determination in 3D computer graphics that works on a polygon-by-polygon basis rather than a pixel-by-pixel, row by row, or area by area basis of other Hidden Surface Removal algorithms. The painter’s algorithm creates images by sorting the polygons within the image by their depth and placing each polygon in order from the farthest to the closest object.

Computational geometry is a branch of computer science devoted to the study of algorithms which can be stated in terms of geometry. Some purely geometrical problems arise out of the study of computational geometric algorithms, and such problems are also considered to be part of computational geometry. While modern computational geometry is a recent development, it is one of the oldest fields of computing with a history stretching back to antiquity.

Self-balancing binary search tree Any node-based binary search tree that automatically keeps its height small

In computer science, a self-balancingbinary search tree is any node-based binary search tree that automatically keeps its height small in the face of arbitrary item insertions and deletions.

Ray casting

Ray casting is the methodological basis for 3-D CAD/CAM solid modeling and image rendering. It is essentially the same as ray tracing for computer graphics where virtual light rays are "cast" or "traced" on their path from the focal point of a camera through each pixel in the camera sensor to determine what is visible along the ray in the 3-D scene. The term "Ray Casting" was introduced by Scott Roth while at the General Motors Research Labs from 1978-1980. His paper, "Ray Casting for Modeling Solids", describes modeled solid objects by combining primitive solids, such as blocks and cylinders, using the set operators union (+), intersection (&), and difference (-). The general idea of using these binary operators for solid modeling is largely due to Voelcker and Requicha's geometric modelling group at the University of Rochester. See Solid modeling for a broad overview of solid modeling methods. This figure on the right shows a U-Joint modeled from cylinders and blocks in a binary tree using Roth's ray casting system, circa 1979.

Hidden-surface determination Visibility in 3D computer graphics

In 3D computer graphics, hidden-surface determination is the process of identifying what surfaces and parts of surfaces can be seen from a particular viewing angle. A hidden-surface determination algorithm is a solution to the visibility problem, which was one of the first major problems in the field of 3D computer graphics. The process of hidden-surface determination is sometimes called hiding, and such an algorithm is sometimes called a hider. When referring to line rendering it is known as hidden-line removal. Hidden-surface determination is necessary to render a scene correctly, so that one may not view features hidden behind the model itself, allowing only the naturally viewable portion of the graphic to be visible.

The point location problem is a fundamental topic of computational geometry. It finds applications in areas that deal with processing geometrical data: computer graphics, geographic information systems (GIS), motion planning, and computer aided design (CAD).

Euclidean minimum spanning tree

The Euclidean minimum spanning tree or EMST is a minimum spanning tree of a set of n points in the plane, where the weight of the edge between each pair of points is the Euclidean distance between those two points. In simpler terms, an EMST connects a set of dots using lines such that the total length of all the lines is minimized and any dot can be reached from any other by following the lines.

The art gallery problem or museum problem is a well-studied visibility problem in computational geometry. It originates from a real-world problem of guarding an art gallery with the minimum number of guards who together can observe the whole gallery. In the geometric version of the problem, the layout of the art gallery is represented by a simple polygon and each guard is represented by a point in the polygon. A set of points is said to guard a polygon if, for every point in the polygon, there is some such that the line segment between and does not leave the polygon.

Sweep line algorithm

In computational geometry, a sweep line algorithm or plane sweep algorithm is an algorithmic paradigm that uses a conceptual sweep line or sweep surface to solve various problems in Euclidean space. It is one of the key techniques in computational geometry.

Visibility in geometry is a mathematical abstraction of the real-life notion of visibility.

Boolean operations on polygons

Boolean operations on polygons are a set of Boolean operations operating on one or more sets of polygons in computer graphics. These sets of operations are widely used in computer graphics, CAD, and in EDA.

Algorithms that construct convex hulls of various objects have a broad range of applications in mathematics and computer science.

Visibility polygon

In computational geometry, the visibility polygon or visibility region for a point p in the plane among obstacles is the possibly unbounded polygonal region of all points of the plane visible from p. The visibility polygon can also be defined for visibility from a segment, or a polygon. Visibility polygons are useful in robotics, video games, and in determining positions to locate facilities, such as the best placement of security guards in an art gallery.

Polygonal chain

In geometry, a polygonal chain is a connected series of line segments. More formally, a polygonal chain P is a curve specified by a sequence of points called its vertices. The curve itself consists of the line segments connecting the consecutive vertices.

In computer science, an output-sensitive algorithm is an algorithm whose running time depends on the size of the output, instead of, or in addition to, the size of the input. For certain problems where the output size varies widely, for example from linear in the size of the input to quadratic in the size of the input, analyses that take the output size explicitly into account can produce better runtime bounds that differentiate algorithms that would otherwise have identical asymptotic complexity.

In computational complexity theory, asymptotic computational complexity is the usage of asymptotic analysis for the estimation of computational complexity of algorithms and computational problems, commonly associated with the usage of the big O notation.

In computational geometry, the Bentley–Ottmann algorithm is a sweep line algorithm for listing all crossings in a set of line segments, i.e. it finds the intersection points of line segments. It extends the Shamos–Hoey algorithm, a similar previous algorithm for testing whether or not a set of line segments has any crossings. For an input consisting of line segments with crossings, the Bentley–Ottmann algorithm takes time . In cases where , this is an improvement on a naïve algorithm that tests every pair of segments, which takes .

John E. Hershberger is an American computer scientist and software professional, a principal engineer at Mentor Graphics Corporation since 1993. He is known for his research in computational geometry and algorithm engineering.

A partition of a polygon is a set of primitive units, which do not overlap and whose union equals the polygon. A polygon partition problem is a problem of finding a partition which is minimal in some sense, for example a partition with a smallest number of units or with units of smallest total side-length.

References

  1. ↑ L. G. Roberts. Machine perception of three-dimensional solids . PhD thesis, Massachusetts Institute of Technology, 1963.
  2. ↑ 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 ]
  3. ↑ I. E. Sutherland. Ten unsolved problems in computer graphics. Datamation, 12(5):22–27, 1966.
  4. 1 2 3 4 5 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.
  5. 1 2 A. 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.
  6. ↑ R. Galimberti and U. Montanari. An algorithm for hidden line elimination. Commun. ACM, 12(4):206–211, April 1969.
  7. ↑ Ch. Hornung. An approach to a calculation-minimized hidden line algorithm. Computers & Graphics, 6(3):121–126, 1982.
  8. ↑ P. P. Loutrel. A solution to the hidden-line problem for computer-drawn polyhedra. IEEE Trans. Comput., 19(3):205–213, March 1970.
  9. ↑ J. F. Blinn. Fractional invisibility. IEEE Comput. Graph. Appl., 8(6):77–84, November 1988.
  10. 1 2 Th. 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.
  11. 1 2 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.
  12. 1 2 O. Nurmi. A fast line-sweep algorithm for hidden line elimination. BIT, 25:466–472, September 1985.
  13. ↑ M. L. Fredman and B. Weide. On the complexity of computing the measure of U[ai, bi]. Commun. ACM, 21:540–544, July 1978.
  14. ↑ M. McKenna. Worst-case optimal hidden-surface removal. ACM Trans. Graph., 6:19–28, January 1987.
  15. ↑ Sh. Ghali. A survey of practical object space visibility algorithms. SIGGRAPH Tutorial Notes, 1(2), 2001.
  16. ↑ F. Devai. An O(log N) parallel time exact hidden-line algorithm. Advances in Computer Graphics Hardware II, pp. 65–73, 1988.
  17. ↑ J. H. Reif and S. Sen. 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.
  18. 1 2 F. 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.
  19. ↑ 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.
This page is based on this Wikipedia article
Text is available under the CC BY-SA 4.0 license; additional terms may apply.
Images, videos and audio are available under their respective licenses.