Explain the scan-line algorithm, Data Structure & Algorithms

Assignment Help:

Explain the Scan-Line Algorithm

This image-space method for removing hidden surfaces is an extension of the scan-line algorithm for filling polygon interiors. Instead of filling just one surface, we now deal with multiple surfaces. As each scan line is processed, all polygon surfaces intersecting that line are examined to determine which are visible. Across each scan line, depth calculations are made for each overlapping surface to determine which is nearest to the view plane. When the visible surface has been determined, the intensity value for that position is entered into the refresh buffer.

We assume that tables are set up for the various surfaces, which include both an edge table and a polygon table. The edge table contains coordinate end points for each line in the scene, the inverse slope of each line, and pointers into the polygon table to identify the surfaces bounded by each line. The polygon table contains coefficients of the plane equation for each surface, intensity information for the surfaces, and possibly pointers into the edge table. To facilitate the search for surfaces crossing a given scan line, we can set up an active list of edges from information in the edge table. This active list will contain only edges that cross the current scan line, sorted in order of increasing x. In addition, we define a flag for each surface that is set on or off to indicate whether a position along a scan line is inside or outside of the surface. Scan lines are processed from left to right. At the leftmost boundary of a surface, the surface flag is turned on; and at the rightmost boundary, it is turned off.  Figure 3.6 illustrates the scan-line method for locating visible portions of surface for pixel positions along the line. The active list for scan line 1 contains information from the edge table for edges AB and BC, only the flag for surface S1 is on. Therefore, no depth calculations are necessary, and intensity information for surface S1 is entered from the polygon table into the refresh buffer. Similarly, between edges EH and FG, only the flag for surface S2 is on. No other positions along scan line 1 intersect surfaces, so the intensity values in the other areas are set to the background intensity. The background \intensity can be loaded throughout the buffer in an initialization routine. 

For scan lines 2 and 3 in Figure, the active edge list contains edges AD, EH, BC, and FG. Along scan line 2 from edge AD to edge EH, only the flag for surface S1 is on. But between edges EH and BC, the flags for both surfaces are on. In this interval, depth calculations must be made using the plane coefficients for the two surfaces. For this example, the depth of surface S1 is assumed to be less than that of S2, so intensities for surface S1 are loaded into the refresh buffer until boundary BC is encountered. Then the flag for surface S1 goes off, and intensities for surface S2, so intensities for surface S1 are loaded into the refresh buffer until boundary BC is encountered. Then the flag for surface S1 goes off, and intensities for surface S2 are stored until edge FG is passed. 

We can take advantage of coherence along the scan lines as we pass from one scan line to the next. In Figure 3.6, scan line 3 has the same active list of edges as scan line 2. Since no changes have occurred in line intersections, it is unnecessary again to make depth calculations between edges EH and BC. The two surfaces must be in the same orientation as determined on scan line 2, so the intensities for surface S1 can be entered without further calculations.

 

688_data structure.png


Related Discussions:- Explain the scan-line algorithm

Insertion of an element in a linear array, To delete an element in the list...

To delete an element in the list at the end, we can delete it without any difficult. But, assume if we desire to delete the element at the straining or middle of the list, then, we

Sorting, explain quick sort algorithm

explain quick sort algorithm

Applications of linear and binary search, The searching method are applicab...

The searching method are applicable to a number of places in current's world, may it be Internet, search engines, text pattern matching, on line enquiry, finding a record from data

Accept a file and form a binary tree - huffman encoding, Huffman Encoding i...

Huffman Encoding is one of the very simple algorithms to compress data. Even though it is very old and simple , it is still widely used (eg : in few stages of JPEG, MPEG etc). In t

Explain np-complete decision problem, a. Determine the result of inserting ...

a. Determine the result of inserting the keys 4,19, 17, 11, 3, 12, 8, 20, 22, 23, 13, 18, 14, 16, 1, 2, 24, 25, 26, 5 in order to an empty B-Tree of degree 3. Only draw the configu

Define graph, A graph is a mathematical structure giving of a set of vertex...

A graph is a mathematical structure giving of a set of vertexes (v1, v2, v3) and a group of edges (e1, e2, e3). An edge is a set of vertexes. The two vertexes are named the edge en

Green computing, In the present scenario of global warming, the computer ha...

In the present scenario of global warming, the computer hard ware and software are also contributing for the increase in the temperature in the environment and contributing for the

Non-recursive implementation of preorder traversal, For preorder traversal,...

For preorder traversal, in the worst case, the stack will rise to size n/2, where n refer to number of nodes in the tree. Another method of traversing binary tree non-recursively t

Structural Induction, Let a be a well-formed formula. Let c be the number o...

Let a be a well-formed formula. Let c be the number of binary logical operators in a. (Recall that ?, ?, ?, and ? are the binary logical operators). Let s be the number of proposit

Write Your Message!

Captcha
Free Assignment Quote

Assured A++ Grade

Get guaranteed satisfaction & time on delivery in every assignment order you paid with us! We ensure premium quality solution document along with free turntin report!

All rights reserved! Copyrights ©2019-2020 ExpertsMind IT Educational Pvt Ltd