midpoint subdivision algorithm [page-93(104)]works on basis of dividing line smaller segments , tests each segment find whether within visible boundary of clipping region or not.
in binary search algorithm, find middle element , either choose right hand side or left hand side.
but, here, following image shows, after first segmentation, find both of subsections disputed. so, both of them candidates further subdivisions. so, can not proceed binary search.
i using iterative method. but, following code doesn't work:
line2d getclippedline() { line2d clippingcandidate = this->line; std::vector<line2d> lines = clippingcandidate.getmidpointsublines(); while(lines[0] != lines[1]) { lines = clippingcandidate.getmidpointsublines(); line2d 1 = lines[0]; line2d 2 = lines[1]; if(one.isclippingcandidate(rectangle)) { clippingcandidate = one; } if(two.isclippingcandidate(rectangle)) { clippingcandidate = two; } if(one.isvisible(rectangle)) { coordinates2d::draw(one, yellow); } if(two.isvisible(rectangle)) { coordinates2d::draw(two, yellow); } clippingcandidate.show(); //std::cout<<"++"; //two.show(); std::cout<<"\n"; } return clippingcandidate; }
you're right ask. explanations of midpoint subdivision have arisen sloppy or wrong. looks code based on 1 of these bad sources.
m-s useful finding intersections when know segment straddles clipping boundary (one end point on each side), , it's implemented integers. used subroutine in variation of complete clipping algorithm of cohen , sutherland.
see the wikipedia article if you're not familiar c-s. "out codes" guide successive clipping against infinite lines containing viewport boundaries. in pseudocode there, you'd replace floating point math m-s.
say clipping against left boundary @ x=c, , line segment straddles p0(x0,y0)---p1(x1,y1). x0<c<=x1, p0 known outside boundary. m-s algorithm is:
tx1 = x1; // don't modify p1; it's inside boundary ty1 = y1; while (x0 < c) { xm = (x0 + tx1 + 1) >> 1; ym = (y0 + ty1 + 1) >> 1; if (xm <= c) { // midpoint on or outside boundary x0 = xm; // move p0 y0 = ym; } else { // midpoint strictly inside tx1 = xm; // move p1 ty1 = ym; } } // clipped segment (x0,x1)--(y0,y1). you need 3 other minor variations of other 3 boundaries.
termination conditions tricky. + 1s necessary avoid looping forever in case x0 = c-1 , tx1 = c: (c + c - 1 + 1) >> 1 == c, next iteration terminate.
having said that, midpoint subdivision pretty obsolete. useful processors had integer arithmetic (often case until @ least mid 90's; implemented in 8088 assembly language in 1984). finding midpoint requires division 2, integer right shift, possible clip no more ceiling(log_2 n) fast iterations coordinates of max size n. these days floating point units operating @ gigaflop rates, it's faster , easier clip floating point.
addition fun, implemented in c:
#include <stdio.h> #include <stdlib.h> typedef unsigned outcode; typedef int coord; typedef int bool; #define true 1 #define false 0 #define xmin 0 #define ymin 0 #define xmax 5000 #define ymax 3000 // not strictly portable, fine. #define sign_bit (~(~0u >> 1)) #define left sign_bit #define top (left >> 1) #define right (top >> 1) #define bottom (right >> 1) #define (left | bottom | right | top) // mask sign bit. #define m(x) ((x) & sign_bit) // shift previous value , mask in new sign bit. #define sm(prev, new) (((outcode)(prev) >> 1) | m(new)) __inline outcode outcode(coord x, coord y) { return sm(sm(sm(m(ymax - y), xmax - x), y - ymin), x - xmin); } // in s-t coordinate system, po outside boundary c , moved // boundary while pi doesn't move. termination correction. #define move_to_boundary(so, to, si, ti, c, i, is_outside) { \ coord tsi = si, tti = ti; \ while (so is_outside c) { \ coord sm = (tsi + + i) >> 1; \ coord tm = (tti + + i) >> 1; \ if (sm is_outside ## = c) { \ = sm; \ = tm; \ } else { \ tsi = sm; \ tti = tm; \ } \ } \ } while (0) bool clip(coord *x0p, coord *y0p, coord *x1p, coord *y1p) { coord x0 = *x0p, y0 = *y0p, x1 = *x1p, y1 = *y1p; outcode code0 = outcode(x0, y0); outcode code1 = outcode(x1, y1); (;;) { if ((code0 | code1) == 0) { *x0p = x0; *y0p = y0; *x1p = x1; *y1p = y1; return true; } else if (code0 & code1) { return false; } else if (code0) { if (code0 & bottom) move_to_boundary(y0, x0, y1, x1, ymax, 0, >); else if (code0 & right) move_to_boundary(x0, y0, x1, y1, xmax, 0, >); else if (code0 & top) move_to_boundary(y0, x0, y1, x1, ymin, 1, <); else /* left */ move_to_boundary(x0, y0, x1, y1, xmin, 1, <); code0 = outcode(x0, y0); } else { if (code1 & bottom) move_to_boundary(y1, x1, y0, x0, ymax, 0, >); else if (code1 & right) move_to_boundary(x1, y1, x0, y0, xmax, 0, >); else if (code1 & top) move_to_boundary(y1, x1, y0, x0, ymin, 1, <); else /* left */ move_to_boundary(x1, y1, x0, y0, xmin, 1, <); code1 = outcode(x1, y1); } } } int main(void) { int n = 0, margin = 2000; (;;) { // generate random points around viewport. int x0 = rand() % (2 * margin + xmax - xmin) - margin; int y0 = rand() % (2 * margin + ymax - ymin) - margin; int x1 = rand() % (2 * margin + xmax - xmin) - margin; int y1 = rand() % (2 * margin + ymax - ymin) - margin; printf("a(%d, %d)--(%d, %d) %x--%x\n", x0, y0, x1, y1, outcode(x0,y0) >> 28, outcode(x1,y1) >> 28); bool r = clip(&x0, &y0, &x1, &y1); printf("a(%d, %d)--(%d, %d): %d\n", x0, y0, x1, y1, r); } return 0; } on macbook clips billion segments in 90 seconds. interesting see how compares floating point c-s.
Comments
Post a Comment