Page 171 - DCAP504_Computer Graphics

Computer Graphics

Use of Tree for Color Quantization
If there is a need for color quantization, we would require extending our node-structure by a reference
counter and three color markers. Now, there is no need for the data pointer anymore as all the
information has been stored directly into the Octree node structure. The structure would look like:
struct octreeroot
{
unsigned long references;
unsigned long red;
unsigned long green;
unsigned long blue;
struct octreeroot childnodes[8];
};
Now, we will insert these colors into the tree. Whenever a leaf is encountered while moving up in the
tree, we would have to increment the reference count and add the color value to the red, green, and
blue counters respectively. This can help us in identifying the colors that are most important. After
inserting all the colors we should start reducing them. Since, we know that only leaves can have a
reference so we will count all the nodes that have a reference greater than zero. Now, we will move into
the following code-fragment:
WHILE (numb of leaves>256)

search the node, where the sum of the child references is minimum and then reduce it.
ENDWHILE
The range 0 – 256 represents the range of colors from white to black, where 0 represents white and 256
represents black. Thus, we get the desired color composition at the end.
11.7 Removal

Surface of objects closer to the camera obscure the more far-off ones. Now, we are left to decide upon
which surfaces are visible and which are not and remove them accordingly. This process of removing
hidden surfaces is termed as removal.
Scan Line
This is another approach of image space method. This algorithm deals with more than one surface.
When each scan line is processed, the polygon surfaces intersecting that line are examined to determine
which are visible. The depth calculation is then done to find which polygon is nearest to the view plane.
Finally, it takes the intensity value of the nearest polygon at that position into the frame buffer.

Scan line algorithm maintains the edge list in the Edge Table (ET). The Active Edge Table (AET)
contains edges which cross the current scan line. These are sorted in order of increasing value of x. The
scan line algorithm also stores a flag for each surface. This flag is set on or off to indicate whether a
position along a scan line is inside or outside of the surface. The processing of scan lines is done from
left to right. The surface flag is turned ON at the leftmost boundary of a surface and it is turned off at
the rightmost boundary.

164 LOVELY PROFESSIONAL UNIVERSITY