We still use the region codes do find line segments that are trivally accepted or rejected. When a line crosses the boundary, the midpoint is computed as follows:
Xmid = (X1+X2)/2
Ymid = (Y1+Y2)/2
Essentially we have two scenerios that can exist and they look like the following:
This algorithm wants to find the visible point of the line segment(P0P1) that is farthest from P0.
Midpoint subdivision algorithm:
Step#1: Is P1 visible? If it is, then P1 is the farthest point from P0 and the process is complete; otherwise, it is invisible, continue.
Step#2: Is segment(P0P1) entirely invisible? If it is, then clip entire line; otherwise, continue.
Step#3: We will take a guess at the farthest point from P0 which is Pm (midpoint of the segment(P0P1)). If segment(PmP1) can be trivally rejected, then go to Step#2 using segment(P0Pm); otherwise, go to Step#2 using segment(PmP1).
What are the terminating conditions of the midpoint subdivision algorithm?
Remember that while the process is going on for segment(P0P1) and a similar process is going on for segment(P1P0).
Problem: Given set_window(10,50,10,50) and segment(P0P1) such that P0=(20,15) and P1=(20,8), show how the midpoint subdivision algorithm would proceed and clip the line segment(P0,P1) to the window.
How would the midpoint subdivision algorithm handle the following case?
Sutherland-Hodgman Clipping Algorithm
Clipping a polygon can produce a polygon with fewer vertices or a polygon with more vertices. Give an example of each.
Remember that a polygon consists of an ordered set of vertices or an ordered set of edges. The polygon is drawn by connecting the vertices in order or more specifically by connecting successive pairs of consecutive vertices with straight lines which produces the edges. So how does the clipping algorithm work?
We can call the clipping algorithm once for each vertex of the original polygon. For each vertex, the algorithm will either return:
1) no vertex at all
2) the original vertex
3) one or more new vertices
Essentially, we use a divide and conquer algorithm such that we solve a series of smaller, simpler problems which combine to solve the larger problem. What is a simpler problem than clipping a polygon to four regions? Clipping a polygon to one region.
We can note that successive clips against four clip boundaries, where each boundary is defined by the window, will clip the polygon.The following is a good example:
Before hitting the specifics of the Sutherland-Hodgman algorith, we will discuss some generalities:
1) The algorithm accepts a series of vertices: V1,V2,...Vn.
2) In general, the polygon edges are from Vi to Vi+1 and from Vn to V1.
3) The algorithm will clip against an edge and then output another series of vertices that define the clipped polygon to that edge. Remember, we must clip againt all four boundaries.
Consider the point A=(2,2) in a rectangular coordinate system. The point A is a certain distance and a certain direction from (0,0). The distance and direction are characterized by the length and direction of segment(OA). OA is called a position vector and indicated by means of an arrow as follows:
Go through vector notation and simple vector properties in class!!
Problem: Determine whether points P3 and P4 are inside or outside the clip boundary, given the following:
