Hidden Line Removal: Unveiling the Invisible: Secrets of Computer Vision

By Fouad Sabry

What is Hidden Line Removal

Solid objects are typically modeled as polyhedra in the field of three-dimensional computer graphics. Within a polyhedron, a face is a planar polygon that is surrounded by straight line segments that are referred to as edges. When attempting to imitate curved surfaces, a polygon mesh is typically used. It is necessary for computer programs that are used to create line drawings of opaque objects to have the capability of determining whether edges or sections of the edges are hidden by the object itself or by other objects. This allows for the edges to be clipped during the rendering process. The difficulty in question is referred to as hidden-line removal.

How you will benefit

(I) Insights, and validations about the following topics:

Chapter 1: Hidden-line removal

Chapter 2: Painter's algorithm

Chapter 3: Computational geometry

Chapter 4: Ray casting

Chapter 5: Hidden-surface determination

Chapter 6: Point location

Chapter 7: Euclidean minimum spanning tree

Chapter 8: Art gallery problem

Chapter 9: High-dynamic-range rendering

Chapter 10: Straight skeleton

(II) Answering the public top questions about hidden line removal.

(III) Real world examples for the usage of hidden line removal in many fields.

Who this book is for

Professionals, undergraduate and graduate students, enthusiasts, hobbyists, and those who want to go beyond basic knowledge or information for any kind of Hidden Line Removal.

• Language: English
• Publisher: One Billion Knowledgeable
• Release date: May 5, 2024

Book preview

Chapter 1: Hidden-line removal

In 3D computer graphics, polyhedra are typically used to model solid things. A face of a polyhedron is a planar polygon bounded by edges, which are straight line segments. Typically, a polygon mesh is used to represent curved surfaces. In order to clip edges during rendering, computer programs for line drawings of opaque objects must be able to determine which edges or portions of edges are obscured by an item or by other objects. This issue is referred to as hidden-line removal.

Roberts developed the first known solution to the hidden-line problem. Ivan E. Sutherland highlighted ten unresolved issues in computer graphics in 1966.

In computer-aided design, for instance, models can have thousands or millions of edges. Therefore, it is essential to use a computational complexity method that expresses resource requirements (such as time and memory) as a function of issue sizes. Particularly crucial are time constraints for interactive systems.

The problem sizes for hidden-line removal are the number n of the model's edges and the number v of the edges' visible segments.

At the crossing places of the pictures of the edges, visibility can shift.

Let k be the total number of sites where the images of the edges intersect.

Both k = Θ(n²) and v = Θ(n²) in the worst case, but typically v k.

Prior to 1984, hidden-line algorithms published by Ottmann and, Widmayer and Wood proposed O((n + k) log² n)-time hidden-line algorithms.

Then Nurmi improved the running time to O((n + k) log n).

These algorithms take Θ(n² log² n), respectively Θ(n² log n) time in the worst case, if k is less than quadratic nevertheless, can be quicker in actuality.

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² log n) worst-case time, Consequently, Nurmi's algorithm is the best.

However, the log n factor was eliminated by Devai, that Devai and McKenna's methods are milestones in visibility algorithms, breaking a theoretical barrier from O(n² log n) to O(n²) for processing a scene of n edges.

The other outstanding issue, presented by Devai, of whether there exists an O(n log n + v)-time hidden-line algorithm, where v, as already said, is the number of segment visible, remained unanswered at the time of writing.

In 1988 Devai proposed an O(log n)-time parallel algorithm using n² processors for the hidden-line problem under the concurrent read, Model of computing using exclusive write (CREW) parallel random-access machine (PRAM).

As the product of the processor number and the running time is asymptotically greater than Θ(n²), the problem's sequential complication, The algorithm is inefficient, However, it proves that the hidden-line problem belongs to the NC class of difficulty, i.e, It can be solved using a polynomial number of processors in polylogarithmic time.

Hidden-surface algorithms can be used to eliminate hidden lines, however, not the reverse.

Reif and Sen proposed an O(log⁴ 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 amount of output.

In 2011 Devai published an O(log n)-time hidden-surface, and an easier, also O(log n)-time, concealed-line algorithm.

The concealed-surface algorithm, using n²/log n CREW PRAM processors, is best in terms of efficiency.

The hidden-line algorithm uses n² exclusive read, EREW (exclusive write) PRAM processors.

EREW is the PRAM type most similar to actual machines.

The hidden-line algorithm does O(n² log n) work, What is the upper bound for the most effective sequential algorithms in use?.

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.

{End Chapter 1}

Chapter 2: Painter's algorithm

The painter’s algorithm (also depth-sort algorithm and priority fill) 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, by the row, or on a region-by-region basis using additional Hidden-Surface Removal techniques.

In 1972, while all three were employed at CADCentre, Martin Newell, Richard Newell, and Tom Sancha first presented the painter's algorithm as a basic solution to the Hidden-surface determination problem.

The Painter's Algorithm conceptually operates as follows::

Sort each polygon according to depth

Place every polygon from the most distant to the nearest.

sort polygons by depth

for each polygon p:

for each pixel that p covers:

paint p.color on pixel

The time complexity of the painter's algorithm is highly reliant on the sorting mechanism used to arrange the polygons. Assuming the most efficient sorting technique, the worst-case complexity of the painter's approach is O(n log n + m*n), where n is the number of polygons and m is the number of pixels to be filled.

The worst-case space complexity of the painter's algorithm is O(n+m), where n is the number of polygons and m is the number of to-be-filled pixels.

There are two primary technical requisites that favor the use of the painter’s algorithm.

The painter's