Hello and welcome to lecture number 24 in the course Computer Graphics. We are in the process of learning about the 3D graphics pipeline, which has five stages.
What are those stages, let us recap. Object representation, modeling transformation, lighting, viewing pipeline, and scan conversion. So we are currently in this fourth stage of discussion that is the viewing pipeline.
There we covered three transformations that are sub stages of the fourth stage namely, view transformation, projection transformation, viewport transformation.
Then there are two more operations. These are also sub stages of this fourth stage, clipping and hidden surface removal.
Among them, we have already discussed clipping and we started our discussion on HSR or hidden surface removal. So we will continue our discussion on HSR and conclude that discussion today.
So in the last lecture, we talked about two hidden surface removal method namely, back face elimination and depth buffer algorithm. Today, we are going to talk about few more hidden surface removal methods. We will start our discussion with another method that is called depth sorting algorithm.
Now, this depth sorting algorithm is also known as the painter’s algorithm, another popular name and it works at both image and object space. So it works both at the pixel level as well as the surface level. And why it is called painter’s algorithm? Because it tries to simulate the way painter draws a scene.
Now this algorithm consists of two basic steps.
What is the first step? In the first step, it sorts the surfaces based on their depth with respect to the view position. To do that, we need to determine the max and min depth of each surface. That means the maximum and minimum depth of each surface and then we create a sorted surface list based on the maximum depth.
So we can denote this list in terms of notation si, and we can arrange them in ascending order of depth. So in this notation, depth of si is less than depth of si+1 that is the first stage of the algorithm.
In the next stage, we render the surface on the screen one at a time, starting with surface having maximum depth that is the nth surface in the list to surface with the least depth or the lowest depth.
Now, during rendering, during the second stage, we perform some comparisons. So when we are rendering a surface si, we compare it with all other surfaces in the list S to check for depth overlap. That means the minimum depth of one surface is greater than maximum depth of another surface as the situation is illustrated here. Because that these two surfaces here, there is no depth overlap because the minimum is greater than maximum. However, here the minimum is not greater than maximum, so there is a depth overlap.
If there is no overlap then render the surface and remove it from the list S.
In case there is overlap, we perform more checks. First check is bounding rectangles of the two surfaces do not overlap, we check for it. Then we check whether surface si is completely behind the overlapping surface relative to the viewing position. That is the second check, this is the first check. In the third check, overlapping surface completely in front of si relative to the viewing position that is the third check.
And finally, the boundary edge projections of the two surfaces on to the view plane do not overlap, this is the fourth check. So there are series of checks that we perform in case there is depth overlap.
Let us try to understand these checks. First check is bounding rectangles; do not overlap. Now, how do we check for it? So the rectangles do not overlap if there is no overlap in the x and y coordinate extents of the two surfaces.
Consider the situation here. This is one surface, this is another surface. So here, Xmin is less than Xmax, so there is overlap. If there is no overlap then Xmin would be higher than Xmax of the other surface. So if either of these coordinates overlap then the condition fails that means bounding rectangles overlap. So we check for X and Y coordinate extents and then decide whether bounding rectangles overlap or not.
Next check is surface si completely behind overlapping surface relative to the viewing position. Now how do we determine it? We determine the plane equation of the overlapping surface where the normal point towards the viewer.
Next we check all vertices of si with the plane equation of that overlapping surface. If for all vertices of si the plane equation of the overlapping surface returns value less than 0, then si is behind the overlapping surface, otherwise, it is not behind and this condition fails. Situation is depicted in this diagram.
The third condition that we check is whether the overlapping surface is completely in front of the surface of interest si, again relative to the viewing position. Now, this we can check similarly with the plane equations that we have done earlier.
Now, this time we use the plane equation of si rather than this overlapping surface and we use the vertices of the overlapping surface. So we use those vertices in the plane equation and for all vertices, if the equation returns positive value then it is completely in front, otherwise, the condition fails. Situation is shown in this figure.
And finally, the boundary edge projections of the two surfaces onto the view plane do not the overlap, this is the final check. Now, in order to check for these we need set of projected pixels for each surface and then check if there are any common pixels in the two sets. The idea is illustrated here. If there are common pixels in the two sets then definitely, there is an overlap, otherwise, there is no overlap.
Now, as you can see here that this algorithm incorporates elements of both object space and image space methods. The first and the last checks were performed at the pixel level so that is image space, whereas the other two, second and third, were have performed at the object level. So here, the element of object space method is present.
Now, when we perform the tests, we perform the tests following this ascending order maintained in s and also, the order of the checks that we have mentioned. Now, as soon as any one of the checks is true, we move to the check for overlap with the next surface of the list.
So essentially, what we are doing? Initially, we are checking for Z overlap for one surface, with all other surfaces, if it succeeds then we simply render the surface, otherwise, we perform the checks in that particular order, and during the checks if any check is true then we move to the next step rather than continuing with the other checks.
Now if all the test fail, what happens in that case? We swap the order of the surfaces in the list. This is called reordering and then we stop. Then we restart the whole process again from the beginning. So if all checks fail, then we need to reorder the surface list and then we start from the beginning.
Now, sometimes there are issues. Sometimes we may get surfaces that intersect with each other. For example, see this surfaces. This is one surface, this is another surface, and they intersect each other. So in this example, one part of surface 1 is at a depth which is larger than surface 2, whereas the other part is at a depth which is lesser than surface 2, as you can see in this figure.
Now, in such situations we may face problem, we may initially keep surface 1 and surface 2 in a particular way that is surface 1 after surface 2 in the sorted list.
However, if you perform the algorithm you will see that for these surfaces, all conditions will fail so we have to reorder. But that will not solve our purpose. Even if we reorder, the conditions will fail again and we have to reorder again.
So initially, we have S1 followed by S2, next we will have S2 followed by S1. Then we will have to reorder again S1 followed by S2 and this will go on, and we may end up in an indefinite loop because the surfaces intersect and the relative distance between the two are difficult to determine.
In order to avoid such situations what we can do is we can use an extra flag, a Boolean flag for each surface. If a surface is reordered then the corresponding flag will be set ON, which indicates that the surface is already reordered once.
Now, if the surface needs to be reordered again next time we shall do the following. We divide the surface along the intersection line and then add two new surfaces in the sorted list at appropriate positions. So when the surface needs to reordered again, we know that there is intersection. Then we divide the surface along the intersection lines and then add two new surfaces instead of one in the list in a sorted order.
Of course, these two steps are very easy to do and requires lots of computations, however, we will not go into the details we just give you some idea rather than the details of how to do that. So that is the basic idea of painter’s algorithm.
We will discuss one more algorithm Warnock’s algorithm.
This is actually part of a group of methods for hidden surface removal, which are collectively known as area subdivision methods and they work on same general idea. And what is that idea?
So we first consider an area of the projected image.
Then if we can determine which polygonal surfaces are visible in the area then we assign those surface colors to the area. Of course, if we can determine then our problem is solved. So that determination is the key issue here.
Now if we cannot determine, we recursively subdivide area into smaller regions and apply the same decision logic on the sub regions. So it is a recursive process.
Warnock’s algorithm is one of the earliest subdivision method developed.
In this algorithm, we subdivide a screen area into four equal squares. As you can see this is the region which we divide into four equal squares P1, P2, P3 and P4 then we perform recursion.
We check for visibility in each square to determine pixel colors in the square region. So we process each square at a time.
And in this processing, there are three cases to check. Case 1, is current square region being checked does not contain any surface. In that case, we do not sub divide the region any further because it does not have any surface so there is no point in further checking and we simply assign background color to the pixels contained in this sub region.
In case 2, the nearest surface completely overlaps the region under consideration. That means it is completely overlapped by the surface that is closest to the viewer. In this case also, we do not further sub divide the square, instead we simply assign the surface color to the region because it is completely covered by the surface. So note that here we need to determine the nearest surface and then determine the extent of this surface after projection so that we can check whether it completely cover that sub region.
And there is case 3, where none of case 1 and 2 holds. In this case, we perform recursion. We recursively divide the region into four sub regions and then repeat the checks. Recursion
stops if either of the cases is met or the region size becomes equal to pixel size. For example, here, as you can see, we subdivided into four more sub regions P31, 32, 33, and 34. Then 31 we performed another recursion, again divided into sub regions, four sub regions.
And we continue till either of the conditions 1 or 2 is met or the sub region size becomes equal to pixel size that is the smallest size possible. So this is the idea of the algorithm, where we assume that we are having projected image and then, we divide it into four sub regions at a time and perform recursive steps.
So with that, we have come to the conclusion of our discussion on hidden surface removal.
Now, before we conclude, few things to be noted here. The hidden surface removal is an important operation in the fourth stage, but it involves lots of complex operations and we exploit the coherence principles to reduce such complexities. These are the things that we should remember.
Also, we should remember that there are many methods for hidden surface removal and broadly, they are of two types, object space method and image space method.
Among these methods, we covered four such methods that is back face elimination, which is an object space method; Z-buffer algorithm, an image space method; painter’s algorithm, a mix of image and object based method; and Warnock’s algorithm, which is image space method. There are other approaches of course.
One popular approach, which is an object space method is an Octree method, which we will not discuss in details, you may refer to the learning material. So we covered fourth stage and all its sub stages namely, the three transformations view transformation, projection transformation, viewport transformation, and also the two operations namely, clipping and hidden surface removal.
Whatever we have discussed so far can be found in this book. You may refer to chapter 8, sections 8.6 and 8.7. Also, if you are interested to learn more about another object space method that is the Octree method you may check section 8.8 as well.
So that is all for today. In the next lecture, we will start our discussion on the next stage of the pipeline that is scan conversion. Till then, thank you and good bye.
Log in to save your progress and obtain a certificate in Alison’s free Advanced Diploma in Computer Graphics online course
Sign up to save your progress and obtain a certificate in Alison’s free Advanced Diploma in Computer Graphics online course
Please enter you email address and we will mail you a link to reset your password.