Celestin Apprentice 7

home *** CD-ROM | disk | FTP | other *** search

/ Celestin Apprentice 7 / Apprentice-Release7.iso / Source Code / Libraries / 3DGPL 1.0 / TEXT / 4.TXT < prev

Wrap

Text File | 1995-06-22 | 28.0 KB | 741 lines | [TEXT/ttxt]

2-D clipping. --------------- "Don't discount flying pigs before you have good air defense." -- jvh@clinet.fi Screen boundaries clipping. --------------------------- Throughout the last chapter we've assumed that primitives we were rendering are completely within the screen boundaries. This is something we can't really guarantee. The worst thing- if we would try using those functions to render an element outside the screen, they won't much complain and would most likely try accessing memory outside the colourmap's allocated space. And I guess: segmentation fault, core dumped is hardly most graceful way to exit a program. So we don't have another choice but to guarantee rendering algorithms that the element passed is indeed inside the screen. A dot. ------ Clipping looks trivial in case of a dot, we just have to add few comparisons checking if the coordinates are in the screen range and proceed only if that is the case: void G_dot(int x,int y,unsigned char colour) { if( (x>=0)&&(x<HW_SCREEN_X_SIZE) && (y>=0)&&(y<HW_SCREEN_Y_SIZE) ) { G_buffer[y*HW_SCREEN_X_SIZE+x]=colour; } } And of course there if we are always clipping to a rectangular with a diagonal (0,0-something_x,something_y) we can do it with just 2 comparisons instead of 4, just by making sure x and y passed are considered by unsigned comparisons, (negative numbers after all would be thought of as just very big positive). A line. ------- We can extend above method for line and check every time before plotting a dot whether it is within the boundaries. Unfortunately by doing that we push up the complexity of the code within the loop. And moreover our optimized line routine work with addresses of points within the colourmap rather then with the coordinates. What we would have to construct is a function that would take in arbitrary coordinates of some line and return back the coordinates of a line's part which is within the screen boundaries. This process is called clipping. The clipping routine must basically find coordinates of an intersection point between the line and some of the screen edges. * A \\ \ \ \ \I1 \ +-o---------------- Y=0 \| \ I2o \ |\ * B | *C | X=0 pic 4.1 The problem is that we are not sure on what edge the intersection point lies, for example in the picture above line A-B intersects screen at the edge Y==0, whereas line A-C intersects it at the edge X==0. Generally we can avoid thinking where the intersection is located by consecutive clipping a line against first, say, vertical boundaries limits and then horizontal: * A | \ | \oI1 |\ ------+--o--------------- Y=0 * G | I2 \ \ | \ \ | * B *E *H C*---o--*D \ | *F | X=0 pic 4.2 In the example above after first call to clipping routine line A-B would become I1-B, after the second it would assume the final acceptable form I2-B. It can be seen also that some lines going through this clipping method won't actually be clipped at all (E-F) some would be clipped just once (C-D), some twice (A-B) and finally some would be completely clipped, that is, would be totally outside the screen area (G-H). Now, how to find an intersection point? obviously it is not a very complicated case of solving similar triangles: | (x1,y1) * | | \ | | * (xm,ym) | | \ +---|---* (x2,y2) | pic 4.3 y2-ym y2-y1 (y2-y1)*(x2-xm) ------- = ------- => ym = y2 - ----------------- x2-xm x2-x1 x2-x1 but this method involves multiplications and divisions, so beholding to our tradition let's try to avoid it. The alternative method is using binary search: A(-3,1) * | \ | (-1,3)* | o I(0,?) | \ | * B(1,5) | X=0 pic 4.4 Let's see how it works on a simple example: suppose we have to clip a line A(-3,1)-B(1,5) by an edge X=0 , we have to find Y of the intersection point. let's find midpoint of the line A-B: Ax+Bx Ay+By midx=------- midy=------- 2 2 midx=(-3+1)/2=-1 midy=(1+5)/2=3 Now, let's see where the boundary lies with respect to the midpoint? It is still to the right of it, so of two lines A-MidPoint MidPoint-B, edge intersects MidPoint-B. Let's rename MidPoint into A and start the midpoint search over again: midx=(-1+1)/2=0 midy=(3+5)/2=4 Here, the intersection came precisely onto the edge. So midy is the Y coordinate of Intersection point we were looking for. It appears that this method involve a lot of calculations, but they are all very cheap, just an addition and division by two (which is actually a 1 bit right shift). Practice shows binary search works indeed faster then calculation resulting from solving similar triangles. When dealing with divisions performed by shits however, one has to be aware of truncation problems that might arise. Since -1>>1=-1 that means that if we would try to use algorithm described above to clipp (-1,y1)-(0,y2) line by X==0 boundary chances are we would loop forever, at each iteration finding that -1>>1 is still -1. (and O(for ever) is hardly, the time complexity contributing towards high frame-rate). As in the code below this situation should be thought of. Let's create a function which would perform clipping against two vertical screen edges: that is C_X_CLIPPING_MIN and C_X_CLIPPING_MAX. int C_line_x_clipping(int **vertex1,int **vertex2,int dimension) { register int i; register int whereto; register int *l,*r,*m,*t; /* left right and midle and tmp */ static int g_store0[C_MAX_DIMENSIONS]; /* static stores for clipped vxes */ static int g_store1[C_MAX_DIMENSIONS]; static int g_store2[C_MAX_DIMENSIONS]; static int g_store3[C_MAX_DIMENSIONS]; static int g_store4[C_MAX_DIMENSIONS]; static int g_store5[C_MAX_DIMENSIONS]; int **vmn,**vmx; /* so that *vmn[0] < *vmx[0] */ int swap; /* we coordinates swaped? */ C_2D_clipping=0; /* default no clipping yet */ if((*vertex1)[0]<(*vertex2)[0]) { swap=0; vmn=vertex1; vmx=vertex2; } /* so that *vmn[0] < *vmx[0] */ else { swap=1; vmn=vertex2; vmx=vertex1; } if(((*vmn)[0]>C_X_CLIPPING_MAX)||((*vmx)[0]<C_X_CLIPPING_MIN)) return(0); else { if((*vmn)[0]<=C_X_CLIPPING_MIN) /* clipping */ { HW_copy_int(*vmn,l=g_store0,dimension); /* copying old vertixes */ HW_copy_int(*vmx,m=g_store1,dimension); r=g_store2; /* let middle be there */ whereto=0; while(m[0]!=C_X_CLIPPING_MIN) { if(whereto==1) { t=l; l=m; m=t; } else { t=r; r=m; m=t; } for(i=0;i<dimension;i++) m[i]=(l[i]+r[i])>>1; whereto=m[0]<C_X_CLIPPING_MIN; } *vmn=m; /* that is why m[] is static */ C_2D_clipping=swap^1; } if((*vmx)[0]>=C_X_CLIPPING_MAX) /* clipping */ { HW_copy_int(*vmn,l=g_store3,dimension); /* copying old vertixes */ HW_copy_int(*vmx,m=g_store4,dimension); r=g_store5; /* let middle be here */ whereto=0; while(m[0]!=C_X_CLIPPING_MAX) { if(whereto==1) { t=l; l=m; m=t; } else { t=r; r=m; m=t; } for(i=0;i<dimension;i++) m[i]=(l[i]+r[i])>>1; whereto=m[0]<C_X_CLIPPING_MAX; } *vmx=m; /* that is why m[] is static */ C_2D_clipping|=swap&1; } } return(1); /* partialy or not clipped */ } The return value of this function is zero if line is completely clipped otherwise it is 1. The purpose of global C_2D_clipping variable would become clear when we would be talking about polygon clipping. As to the Y clipping we can either modify the above code to do both functions or just duplicate most of the code changing few things, like constants names ( C_Y_CLIP... instead of C_X_CLIPP...) and indexes of clipped variable ( 1 instead of 0). As you can see this code is generic enough to allow clipping of N-dimensional lines ( so that to allow for X Y Z Colour Intensity etc. to be processed at the same time). To do it effectively static arrays are being set to keep temporary left (l) middle (m) and right (r) N-tuples. Whenever making decision which segment to take for the next iteration we can just swap pointers, so that array keeping coordinate of segment being discarded could be set to accept middle point at the next iteration. <----------- m l -----------> r | | | v v v +---------+ +---------+ +---------+ |x,y,z... | |x,y,z... | |x,y,z... | +---------+ +---------+ +---------+ pic 4.5 This is being done so that at every iteration only pointers to actual data are moved not the data itself. (The point I am trying to make: (and I am sure everybody knows that, just a bit of reinforcement) it's ok to physically copy small amounts of data, but when we have a lot of it, it is better to move pointers instead) Let's insert calls to clipping function into the G_line routine: ... ... v1=vertex1; v2=vertex2; if(C_line_x_clipping(&v1,&v2,2)) /* horizontal clipping */ { if(C_line_y_clipping(&v1,&v2,2)) /* vertical clipping */ { dx=v2[0]-v1[0]; dy=v2[1]-v1[1]; /* ranges */ ... ... So, whenever line is completely clipped we wouldn't go any further in the rasterization function. A polygon. ---------- Now, remembering that we render polygon by scanning it's edges using rasterization function pretty much like the one above, we may think that adding clipping calls into GI_scan would solve our problem with polygon clipping, unfortunately, it is only half true (literary half true). Lets consider pictures pic 4.6 and 4.7: B * B | *==== I/ |/==== -----*------ I*====== /====== /|?????? /======== / |????? /======== A* |?????? A*========== pic 4.6 pic 4.7 In the cases above edge A-B contribute to the left side of the polygon, clipping present no problem for case on pic 4.7. Clipped part I-B of the edge can be discarded since there's nothing to form outside the screen. On the other hand in the case on pic 4.6 we can't simply discard clipped part A-I since we would loose left boundary of all horizontal lines marked "???". The observation we can make is that polygon, being scanned edge at a time, may not be clipped against horizontal boundaries but must be clipped against vertical, this way the code within GI_scan would look like: ... ... v1=edges; edges+=skip; v2=edges; /* length ints in each */ if(C_line_y_clipping(&v1,&v2,dimension)) /* vertical clipping */ { dx=*v2++; dy=*v2++; /* extracting 2-D coordinates */ x=*v1++; y=*v1++; /* v2/v1 point remaining dim-2 */ ... ... Creating a vertically clipped polygon on the other hand is a bit more complicated. The problem is that the clipped polygon may have different from the original one number of edges. let's consider the situation on the pic 4.8: /* 3 | | / | |5' |/ | 5*-*-----*6 * | / | \ /|2''| 4* | *1 2 * | | \ | / \| | 3*-*-----*2 *\ | |3' |2'\* 1 pic 4.8 pic 4.9 It can be seen that original polygon has 6 edges which becomes 5 after clipping. Some other polygon pic 4.9 can have 1 more edge after clipping. It is obvious that we would have to create a temporary structure to hold the clipped polygon. Now, we know how to clip a single edge, let's try to find pattern how clipped edges compose clipped polygon. Let's be considering clipping against a single boundary, say X==0. it is obvious that if an edge is completely outside it's vertexes won't be present in the new polygon. On the other hand if an edge is within the boundary both points would be present. Any point on the intersection line would be present too. One more consideration is that each point in the polygon belong to two edges, so when the edge is not clipped we may put into the new structure just the second point assuming that the first one is already taken care of when we were processing previous edge. Let's list the patterns: (1) If edge is not clipped or the second point is clipped put into new structure just the second point; (2) When first point is changed or both are changed put both; (3) When both are outside put none. Surprisingly enough this algorithm doesn't have to be changed when we consider simultaneous clipping against two parallel boundaries: | *-----*1| |/5 \| 4'* *2' /| |\ 4* | | \ | | | \ *-*---------*---*2 3 |3' |2'' | | pic 4.10 edge 1-2 Second point clipped - pattern (1) putting in 2' edge 2-3 Both points changed - pattern (2) putting in 2'' and 3' edge 3-4 Both points outside - pattern (3) ignoring edge 4-5 First point clipped - pattern (2) putting in 4' and 5 edge 5-1 No clipping - pattern (1) putting in 1 The result is: 2'-2''-3'-4'-5-1 just looking at the picture assures us that what we got is indeed right. Now finally the purpose of C_2D_clipping variable being set in C_line_x_clipping must be clear. It would be set to 1 whenever first or both points were changed, and would be 0 if none or just second one were changed. Knowing this all let's write some code: int C_polygon_x_clipping(register int *from,register int *to, int dimension,int length ) { register int i; int *v1,*v2,new_lng=0; int *first_vrtx=to; /* begining of the source */ for(i=0;i<length;i++) /* for all edges */ { v1=from; from+=dimension; v2=from; /* taking two vertexes */ if(C_line_x_clipping(&v1,&v2,dimension)) /* clipping */ { if(C_2D_clipping) /* depends which one was clipped */ { HW_copy_int(v1,to,dimension); to+=dimension; HW_copy_int(v2,to,dimension); to+=dimension; new_lng+=2; /* first point clipped */ } else { HW_copy_int(v2,to,dimension); to+=dimension; new_lng++; /* second point clipped */ } } } HW_copy_int(first_vrtx,to,dimension); /* looping the polygon vertexes */ return(new_lng); } Again the way we represent the polygon the very first point has to be the last too since every point belong to two edges, and we can have a pointer to a new edge by just advancing it by "dimension" of a single vertex in the list of polygon vertices. View plane clipping. -------------------- As discussed before if we want to do perspective transformation we have to make sure we are actually applying it to something that we know produces a valid result, hence there should be no points with negative or zero Z coordinates. Zero would produce divide errors, Negative once would appear flipped over. There is another good reason to clip out vertices with negative Z, we just can't see things which are behind us (at least majority of us can't). The technique we would be using is just an expansion of 2-D clipping that was used to make sure 2-D primitives fit physical screen before rendering. As before, we can find the intersection point from solving similar triangles, or using binary-search techniques. The single clipping plane would be specified to be somewhere in front of Z==0. (And no, not quite as far as "focus" distance used in perspective transformation, viewing plane is not necessarily a clipping plane). The function to clip polygons would be almost identical too. (By the way, we can indeed try writing generic line and polygon clipping functions performing it for both 2D screen boundaries and view plane). Volume clipping. ---------------- First of all what view volume is? This is the set of all points in the "world" space which can appear on screen under certain projection method. For example if we are using just the parallel projection (let's forget for a second about perspective) we may see that only points from depicted below rectangular area would appear on the screen. | | | | | | * B | * C | Screen | | | boundaries | v | -----I--------*-------I----- Viewing plane. * A pic 4.11 Point A can't appear on screen as it is behind the viewing plane - it would be clipped by the algorithm described above in this chapter. point B on the other hand is in front of the viewing plane, so it would pass the first test but since it's projection onto the viewing plane won't fit the screen it would be clipped by 2-D screen boundaries clipping routines. Point C is lucky to be inside the view volume. The conclusion here is that by doing first viewing plane clipping and then screen boundaries clipping we actually performed volume clipping, that is we selected from space the set of all points that can be projected and then did actual projection (Yes, by passing to the rendering routines just X and Y of points and discarding Z we basically did parallel projection). Should this be changed somehow to accommodate perspective projection? after all by clipping against view plane we guarantee that there would be no points with Z==0. However the problem is that even having points close to the viewing plane is not very good. pic 4.12 *---> *-------------> *--------------------------> A*- - -> -----I-----I----- pic 4.12 By applying perspective transformation we increase the absolute values of coordinate components depending on inverse of it's distance to the viewer, so if Z==0 transforms into infinity numbers close to that transform into something bitsize of numbers stored in computers might not be able to handle, and no, we can't quite solve it by moving the clipping plane slightly forward, since there are still those nasty points which are slightly in front of the viewing plane but already have big absolute value of X or Y. (pic 4.12, point A). The overflow problem that may result from perspectively transforming this point is this: positive values may become negative, and if it would happen to just one point of two off-screen points representing a line we may actually see this line all across the screen instead of not seeing it at all. The conclusion when using perspective transformation, it is better to apply it to the points we know would produce a valid result. And since what we ultimately want is to project to the screen we are coming back to the view volumes since those are exactly sets of points that would be projected inside the screen. Hence we do need to consider actual viewing volume for perspective projection. What the view volume for perspective projection would look like? The way we modeled this transformation - rays of all visible points converge in viewer's eye. If we would cast back into space lines connecting the eye and the screen boundaries, we would obtain the pyramid marking points from space that would project onto screen edges. what's inside the pyramid would project inside the screen what's outside - outside the screen. adding the clipping plane somewhere in front of the viewer we are obtaining the view-volume for perspective projection, pic 4.13. \ / \ / \ / \ / \ / -----I\---/I----- \ / * pic 4.13 The only problem - we now have to clip against planes which are directed almost arbitrary in space (the exact geometry of this view volume depends on the "focus" parameter - the distance between the viewer and the viewing plane (again, not quite the same as clipping plane). Although conceptually easy to achieve clipping against arbitrary directed plane would have higher complexity. There is number of solutions one can consider: obvious one: indeed implement real volume clipping, although expansive we would be able to completely get rid of 2-D clipping routines which overall might be quite descent. Second: implement volume clipping with special kind of perspective view volume, the one having 90' angle. The reason can be seen from the pic 4.14: \ / \ / x=-z \ / x=z \ / ----I\-----/I----- \ / * pic 4.14 Planes composing this perspective view volume have pretty simple equations: x==z , y==z, x==-z and y==-z clipping against those is way easier then against arbitrary directed planes. The method however we would discuss is a bit different, that is, we would not do clipping at all, to be more exact we would only throw away polygons which are for sure outside the view volume and leave those even partially inside to be further clipped against screen boundaries after being projected. ( Clipping against viewing plane, is a sacred matter that one can hardly get rid of ) One should understand that this method works on assumption that there is no terribly big polygons around, since a one part of a really big polygon can be within the view volume whereas another can be both close to viewing plane and have really big absolute value of X or Y, just something we are trying to exclude from being perspectively projected. How can one figure out whether a point is outside the pyramid with 90' angle? From the pic 4.14 we can see that parts of the space separated by Z==X and Z==-X planes have obvious relationships among X and Z of every point, if Z<X or Z<-X point is for sure outside this area. it should be realized we can't quite extend this scheme onto polygons by saying if all points of a polygon are outside it is outside also, example is a polygon AB on the pic 4.15, it is clear that although both points composing it are outside there supposed to be some part of this polygon inside the view volume. ^ Z | \ | / \ Z>-X | Z>X / \ | / A *---------------------* B \ | / Z<-X \ / Z<X --------------*-----------------> X pic 4.15 We would make decisions, on the other hand, using notion of polygon's extends. pic 4.16 Extend is a cube completely enclosing within itself certain polygon. So coordinates of extend planes are that of maximum and minimum among the polygon vertices along all axes. xmin xmax -------------- ymin |\\ | | \ \ | | \ \ | | \ /| | \/ | |------------ ymax pic 4.16 This way by considering for example (xmin,zmax) point of the extend box we can make a decision whether polygon's extend is outside the x=z plane. ^ Z | \ | / \ | / (xmax,zmax) \ | / (xmin,zmax) ----+ \ | / +----+ | \ | / | --+ \ / +--- --------------*-----------------> X +-------+ (zmax) | | pic 4.17 Let's list all the other cases: xmin > zmax ymin > zmax -xmax > zmax -ymax > zmax On the same stage we can check if the polygon is completely behind the view plane as well. int C_volume_clipping(register int *vxes,int number) { int xmin,ymin,zmin,xmax,ymax,zmax; int i; ymin=xmin=zmin=INT_MAX; ymax=xmax=zmax=INT_MIN; /* initializing searching */ for(i=0;i<number;i++) { if(*vxes>xmax) xmax=*vxes; if(*vxes<xmin) xmin=*vxes; vxes++; if(*vxes>ymax) ymax=*vxes; if(*vxes<ymin) ymin=*vxes; vxes++; if(*vxes>zmax) zmax=*vxes; if(*vxes<zmin) zmin=*vxes; /* searching max/min */ vxes++; } if((zmax<xmin)||(zmax<ymin)||(zmax<-xmax)|| (zmax<-ymax)||(zmax<C_plane)) return(0); else if(zmin<C_plane) return(-1); /* behind clipping plane */ else return(1); } It should be realized that, extend testing is approximate, there might be polygons outside the view volume whose extends are partly inside, but since we are doing clipping to screen boundaries afterwards they would eventually be taken care of. Besides, clipping view volume is a pyramid with 90' angle, real view volume on the other hand depends on the perspective transformation formula, and would likely have angle less then 90'. And again, there should be no very big polygons, since we are doing "full element" volume clipping. * * *