Designing Hidden Surface Algorithms
Considerations for selecting or designing hidden surface algorithms. Following three considerations are taken:
- Sorting
- Coherence
- Machine
1. Sorting:
All surfaces are sorted in two classes, i.e., visible and invisible. Pixels are colored accordingly.
Several sorting algorithms are available i.e.
- Bubble sort
- Shell sort
- Quick sort
- Tree sort
- Radix sort
Different sorting algorithms are applied to different hidden surface algorithms. Sorting of objects is done using x and y, z co-ordinates. Mostly z coordinate is used for sorting. The efficiency of sorting algorithm affects the hidden surface removal algorithm. For sorting complex scenes or hundreds of polygons complex sorts are used, i.e., quick sort, tree sort, radix sort.
For simple objects selection, insertion, bubble sort is used.
2. Coherence
It is used to take advantage of the constant value of the surface of the scene. It is based on how much regularity exists in the scene. When we moved from one polygon of one object to another polygon of same object color and shearing will remain unchanged.
Types of Coherence
- Edge coherence
- Object coherence
- Face coherence
- Area coherence
- Depth coherence
- Scan line coherence
- Frame coherence
- Implied edge coherence
a. Edge coherence:
The visibility of edge changes when it crosses another edge or it also penetrates a visible edge.
b. Object coherence:
Each object is considered separate from others. In object, coherence comparison is done using an object instead of edge or vertex. If A object is farther from object B, then there is no need to compare edges and faces.
c. Face coherence:
In this faces or polygons which are generally small compared with the size of the image.
d. Area coherence:
It is used to group of pixels cover by same visible face.
e. Depth coherence:
Location of various polygons has separated a basis of depth. Depth of surface at one point is calculated, the depth of points on rest of the surface can often be determined by a simple difference equation.
f. Scan line coherence:
The object is scanned using one scan line then using the second scan line. The intercept of the first line.
g. Frame coherence:
It is used for animated objects. It is used when there is little change in image from one frame to another.
h. Implied edge coherence:
If a face penetrates in another, line of intersection can be determined from two points of intersection.
Algorithms used for hidden line surface detection
- Back Face Removal Algorithm
- Z-Buffer Algorithm