| |
| |
| |
| |
| |
| |
| |
| |
| |
| |
| |
| |
| |
| |
| |
| |
| |
| |
| |
| |
| #include <cassert> |
| |
| #include "polyspan.h" |
| |
| |
| using namespace std; |
| |
| |
| Polyspan::Polyspan(): |
| open_index(0), |
| cur_x(0.0), |
| cur_y(0.0), |
| close_x(0.0), |
| close_y(0.0), |
| flags(NotSorted) |
| { } |
| |
| void Polyspan::clear() { |
| covers.clear(); |
| cur_x = cur_y = close_x = close_y = 0; |
| open_index = 0; |
| current.set(0, 0, 0, 0); |
| flags = NotSorted; |
| } |
| |
| |
| void Polyspan::addcurrent() { |
| if (current.cover || current.area) { |
| if (covers.size() == covers.capacity()) |
| covers.reserve(covers.size() + 1024*1024); |
| covers.push_back(current); |
| } |
| } |
| |
| |
| void Polyspan::move_pen(int x, int y) { |
| if (y != current.y || x != current.x) { |
| addcurrent(); |
| current.set(x, y, 0, 0); |
| } |
| } |
| |
| |
| void Polyspan::close() { |
| if (flags & NotClosed) { |
| if (cur_x != close_x || cur_y != close_y) { |
| line_to(close_x, close_y); |
| addcurrent(); |
| current.setcover(0,0); |
| } |
| flags &= ~NotClosed; |
| } |
| } |
| |
| |
| void Polyspan::merge_all() { |
| sort(covers.begin(), covers.end()); |
| open_index = 0; |
| } |
| |
| |
| void Polyspan::sort_marks() { |
| if (flags & NotSorted) { |
| |
| addcurrent(); |
| current.setcover(0, 0); |
| |
| sort(covers.begin() + open_index, covers.end()); |
| |
| flags &= ~NotSorted; |
| } |
| } |
| |
| |
| void Polyspan::encapsulate_current() { |
| |
| sort_marks(); |
| open_index = covers.size(); |
| } |
| |
| |
| void Polyspan::move_to(Real x, Real y) { |
| close(); |
| if (isnan(x)) x=0; |
| if (isnan(y)) y=0; |
| move_pen((int)floor(x), (int)floor(y)); |
| close_y = cur_y = y; |
| close_x = cur_x = x; |
| } |
| |
| |
| void Polyspan::line_to(Real x, Real y) { |
| Real n[4] = {0, 0, 0, 0}; |
| bool afterx = false; |
| |
| const Real xin(x), yin(y); |
| |
| Real dx = x - cur_x; |
| Real dy = y - cur_y; |
| |
| |
| |
| if ( (cur_y >= window.maxy && y >= window.maxy) |
| || (cur_y < window.miny && y < window.miny) ) |
| { |
| cur_x = x; |
| cur_y = y; |
| } else { |
| if (dy > 0) { |
| |
| |
| |
| if (cur_y < window.miny) { |
| |
| n[2] = cur_x + (window.miny - cur_y)*dx/dy; |
| |
| cur_x = n[2]; |
| cur_y = window.miny; |
| move_pen((int)floor(cur_x), window.miny); |
| } |
| |
| |
| if (y > window.maxy) { |
| |
| n[2] = x + (window.maxy - y)*dx/dy; |
| |
| |
| x = n[2]; |
| y = window.maxy; |
| } |
| } else { |
| |
| if (cur_y > window.maxy) { |
| |
| n[2] = cur_x + (window.maxy - cur_y)*dx/dy; |
| |
| cur_x = n[2]; |
| cur_y = window.maxy; |
| move_pen((int)floor(cur_x), window.maxy); |
| } |
| |
| |
| if (y < window.miny) { |
| |
| n[2] = x + (window.miny - y)*dx/dy; |
| |
| |
| x = n[2]; |
| y = window.miny; |
| } |
| } |
| |
| |
| if ( (cur_x >= window.maxx && x >= window.maxx) |
| || (cur_x < window.minx && x < window.minx) ) |
| { |
| |
| cur_x = max(cur_x, (Real)window.minx); |
| cur_x = min(cur_x, (Real)window.maxx); |
| |
| |
| x = max(x, (Real)window.minx); |
| x = min(x, (Real)window.maxx); |
| |
| |
| move_pen((int)floor(cur_x), (int)floor(cur_y)); |
| |
| draw_line(cur_x,cur_y,x,y); |
| |
| cur_x = xin; |
| cur_y = yin; |
| } else { |
| |
| if (dx > 0) { |
| |
| if (cur_x < window.minx) { |
| |
| n[2] = cur_y + (window.minx - cur_x)*dy/dx; |
| |
| move_pen(window.minx, (int)floor(cur_y)); |
| draw_line(window.minx, cur_y, window.minx, n[2]); |
| |
| cur_x = window.minx; |
| cur_y = n[2]; |
| } |
| |
| |
| if (x > window.maxx) { |
| |
| n[2] = y + (window.maxx - x)*dy/dx; |
| |
| n[0] = window.maxx; |
| n[1] = y; |
| |
| |
| x = window.maxx; |
| y = n[2]; |
| afterx = true; |
| } |
| } else { |
| |
| if (cur_x > window.maxx) { |
| |
| n[2] = cur_y + (window.maxx - cur_x)*dy/dx; |
| |
| move_pen(window.maxx, (int)floor(cur_y)); |
| draw_line(window.maxx, cur_y, window.maxx, n[2]); |
| |
| cur_x = window.maxx; |
| cur_y = n[2]; |
| } |
| |
| |
| if (x < window.minx) { |
| |
| n[2] = y + (window.minx - x)*dy/dx; |
| |
| n[0] = window.minx; |
| n[1] = y; |
| |
| |
| x = window.minx; |
| y = n[2]; |
| afterx = true; |
| } |
| } |
| |
| move_pen((int)floor(cur_x), (int)floor(cur_y)); |
| |
| draw_line(cur_x, cur_y, x, y); |
| |
| if (afterx) |
| draw_line(x, y, n[0], n[1]); |
| |
| cur_x = xin; |
| cur_y = yin; |
| } |
| } |
| |
| flags |= NotClosed | NotSorted; |
| } |
| |
| bool Polyspan::clip_conic(const Vector *p, const ContextRect &r) { |
| const Real minx = min(min(p[0][0], p[1][0]), p[2][0]); |
| const Real miny = min(min(p[0][1], p[1][1]), p[2][1]); |
| const Real maxx = max(max(p[0][0], p[1][0]), p[2][0]); |
| const Real maxy = max(max(p[0][1], p[1][1]), p[2][1]); |
| |
| return (minx > r.maxx) || |
| (maxx < r.minx) || |
| (miny > r.maxy) || |
| (maxy < r.miny); |
| } |
| |
| Real Polyspan::max_edges_conic(const Vector *p) { |
| const Real x1 = p[1][0] - p[0][0]; |
| const Real y1 = p[1][1] - p[0][1]; |
| |
| const Real x2 = p[2][0] - p[1][0]; |
| const Real y2 = p[2][1] - p[1][1]; |
| |
| const Real d1 = x1*x1 + y1*y1; |
| const Real d2 = x2*x2 + y2*y2; |
| |
| return max(d1,d2); |
| } |
| |
| void Polyspan::subd_conic_stack(Vector *arc) { |
| |
| |
| |
| |
| |
| |
| |
| |
| |
| |
| |
| |
| |
| Real a, b; |
| |
| |
| arc[4][0] = arc[2][0]; |
| b = arc[1][0]; |
| |
| a = arc[1][0] = (arc[0][0] + b)/2; |
| b = arc[3][0] = (arc[4][0] + b)/2; |
| arc[2][0] = (a + b)/2; |
| |
| |
| arc[4][1] = arc[2][1]; |
| b = arc[1][1]; |
| |
| a = arc[1][1] = (arc[0][1] + b)/2; |
| |
| b = arc[3][1] = (arc[4][1] + b)/2; |
| arc[2][1] = (a + b)/2; |
| |
| |
| |
| |
| |
| |
| |
| |
| |
| |
| |
| } |
| |
| void Polyspan::conic_to(Real x1, Real y1, Real x, Real y) { |
| Vector *current = arc; |
| int level = 0; |
| int num = 0; |
| bool onsecond = false; |
| |
| arc[0] = Vector(x, y); |
| arc[1] = Vector(x1, y1); |
| arc[2] = Vector(cur_x, cur_y); |
| |
| |
| if (clip_conic(arc, window)) |
| { |
| line_to(x,y); |
| return; |
| } |
| |
| |
| while(current >= arc) { |
| assert(num < MAX_SUBDIVISION_SIZE); |
| |
| |
| if (clip_conic(current, window)) { |
| line_to(current[0][0],current[0][1]); |
| current -= 2; |
| if (onsecond) level--; |
| onsecond = true; |
| num--; |
| continue; |
| } else |
| |
| if (level < MIN_SUBDIVISION_DRAW_LEVELS) { |
| subd_conic_stack(current); |
| current += 2; |
| level ++; |
| num ++; |
| onsecond = false; |
| continue; |
| } else |
| |
| if (max_edges_conic(current) > 0.25) { |
| subd_conic_stack(current); |
| current += 2; |
| level ++; |
| num ++; |
| onsecond = false; |
| } else { |
| |
| line_to(current[1][0], current[1][1]); |
| line_to(current[0][0], current[0][1]); |
| |
| current -= 2; |
| if (onsecond) level--; |
| num--; |
| onsecond = true; |
| } |
| } |
| } |
| |
| bool Polyspan::clip_cubic(const Vector *p, const ContextRect &r) { |
| return ((p[0][0] > r.maxx) && (p[1][0] > r.maxx) && (p[2][0] > r.maxx) && (p[3][0] > r.maxx)) || |
| ((p[0][0] < r.minx) && (p[1][0] < r.minx) && (p[2][0] < r.minx) && (p[3][0] < r.minx)) || |
| ((p[0][1] > r.maxy) && (p[1][1] > r.maxy) && (p[2][1] > r.maxy) && (p[3][1] > r.maxy)) || |
| ((p[0][1] < r.miny) && (p[1][1] < r.miny) && (p[2][1] < r.miny) && (p[3][1] < r.miny)); |
| } |
| |
| Real Polyspan::max_edges_cubic(const Vector *p) { |
| const Real x1 = p[1][0] - p[0][0]; |
| const Real y1 = p[1][1] - p[0][1]; |
| |
| const Real x2 = p[2][0] - p[1][0]; |
| const Real y2 = p[2][1] - p[1][1]; |
| |
| const Real x3 = p[3][0] - p[2][0]; |
| const Real y3 = p[3][1] - p[2][1]; |
| |
| const Real d1 = x1*x1 + y1*y1; |
| const Real d2 = x2*x2 + y2*y2; |
| const Real d3 = x3*x3 + y3*y3; |
| |
| return max(max(d1, d2), d3); |
| } |
| |
| void Polyspan::subd_cubic_stack(Vector *arc) { |
| Real a, b, c; |
| |
| |
| |
| |
| |
| |
| |
| |
| |
| |
| |
| |
| |
| |
| |
| |
| arc[6][0] = arc[3][0]; |
| |
| b = arc[1][0]; |
| c = arc[2][0]; |
| |
| a = arc[1][0] = (arc[0][0] + b)/2; |
| b = (b + c)/2; |
| c = arc[5][0] = (arc[6][0] + c)/2; |
| |
| a = arc[2][0] = (a + b)/2; |
| b = arc[4][0] = (b + c)/2; |
| |
| arc[3][0] = (a + b)/2; |
| |
| |
| arc[6][1] = arc[3][1]; |
| |
| b = arc[1][1]; |
| c = arc[2][1]; |
| |
| a = arc[1][1] = (arc[0][1] + b)/2; |
| b = (b + c)/2; |
| c = arc[5][1] = (arc[6][1] + c)/2; |
| |
| a = arc[2][1] = (a + b)/2; |
| b = arc[4][1] = (b + c)/2; |
| |
| arc[3][1] = (a + b)/2; |
| } |
| |
| void Polyspan::cubic_to(Real x1, Real y1, Real x2, Real y2, Real x, Real y) { |
| Vector *current = arc; |
| int num = 0; |
| int level = 0; |
| bool onsecond = false; |
| |
| arc[0] = Vector(x, y); |
| arc[1] = Vector(x2, y2); |
| arc[2] = Vector(x1, y1); |
| arc[3] = Vector(cur_x, cur_y); |
| |
| |
| if (clip_cubic(arc, window)) { |
| line_to(x,y); |
| return; |
| } |
| |
| |
| while(current >= arc) { |
| assert(num < MAX_SUBDIVISION_SIZE); |
| |
| |
| if (level < MIN_SUBDIVISION_DRAW_LEVELS) { |
| subd_cubic_stack(current); |
| current += 3; |
| level ++; |
| num ++; |
| onsecond = false; |
| continue; |
| } else |
| |
| if (clip_cubic(current, window)) { |
| line_to(current[0][0], current[0][1]); |
| current -= 3; |
| if (onsecond) level--; |
| onsecond = true; |
| num --; |
| continue; |
| } else |
| |
| if (max_edges_cubic(current) > 0.25) { |
| subd_cubic_stack(current); |
| current += 3; |
| level ++; |
| num ++; |
| onsecond = false; |
| } else { |
| |
| line_to(current[2][0], current[2][1]); |
| line_to(current[1][0], current[1][1]); |
| line_to(current[0][0], current[0][1]); |
| |
| current -= 3; |
| if (onsecond) level--; |
| num --; |
| onsecond = true; |
| } |
| } |
| } |
| |
| void Polyspan::draw_scanline(int y, Real x1, Real y1, Real x2, Real y2) { |
| int ix1 = (int)floor(x1); |
| int ix2 = (int)floor(x2); |
| Real fx1 = x1 - ix1; |
| Real fx2 = x2 - ix2; |
| |
| Real dx,dy,dydx,mult; |
| |
| dx = x2 - x1; |
| dy = y2 - y1; |
| |
| |
| if (y1 == y2) { |
| move_pen(ix2, y); |
| return; |
| } |
| |
| |
| if (ix1 == ix2) { |
| current.addcover(dy, (fx1 + fx2)*dy/2); |
| return; |
| } |
| |
| if (dx > 0) { |
| |
| dydx = dy/dx; |
| |
| |
| |
| mult = (1 - fx1)*dydx; |
| |
| |
| current.addcover(mult, (1 + fx1)*mult/2); |
| |
| |
| y1 += mult; |
| ix1++; |
| |
| move_pen(ix1, y); |
| |
| |
| while(ix1 != ix2) { |
| |
| current.addcover(dydx,dydx/2); |
| |
| |
| ix1++; |
| y1 += dydx; |
| move_pen(ix1, y); |
| } |
| |
| |
| |
| mult = fx2 * dydx; |
| current.addcover(mult, (0 + fx2)*mult/2); |
| } else { |
| |
| |
| |
| dydx = -dy/dx; |
| |
| |
| |
| mult = fx1*dydx; |
| |
| |
| current.addcover(mult, fx1*mult/2); |
| |
| |
| y1 += mult; |
| ix1--; |
| |
| move_pen(ix1, y); |
| |
| |
| while(ix1 != ix2) { |
| |
| current.addcover(dydx, dydx/2); |
| |
| |
| y1 += dydx; |
| ix1--; |
| move_pen(ix1, y); |
| } |
| |
| |
| mult = y2 - y1; |
| |
| current.addcover(mult, (fx2+1)*mult/2); |
| } |
| } |
| |
| void Polyspan::draw_line(Real x1, Real y1, Real x2, Real y2) { |
| int iy1 = (int)floor(y1); |
| int iy2 = (int)floor(y2); |
| Real fy1 = y1 - iy1; |
| Real fy2 = y2 - iy2; |
| |
| assert(!isnan(fy1)); |
| assert(!isnan(fy2)); |
| |
| Real dx,dy,dxdy,mult,x_from,x_to; |
| |
| const Real SLOPE_EPSILON = 1e-10; |
| |
| |
| if (iy1 == iy2) { |
| draw_scanline(iy1, x1, y1, x2, y2); |
| return; |
| } |
| |
| |
| dy = y2 - y1; |
| dx = x2 - x1; |
| |
| |
| if (dx < SLOPE_EPSILON && dx > -SLOPE_EPSILON) { |
| |
| if (dy > 0) { |
| |
| Real sub; |
| |
| int ix1 = (int)floor(x1); |
| Real fx1 = x1 - ix1; |
| |
| |
| sub = 1 - fy1; |
| |
| current.addcover(sub, fx1*sub); |
| |
| |
| iy1++; |
| |
| |
| move_pen(ix1, iy1); |
| |
| while(iy1 != iy2) { |
| |
| current.addcover(1,fx1); |
| |
| |
| iy1++; |
| move_pen(ix1, iy1); |
| } |
| |
| |
| current.addcover(fy2, fy2*fx1); |
| } else { |
| Real sub; |
| |
| int ix1 = (int)floor(x1); |
| Real fx1 = x1 - ix1; |
| |
| |
| sub = 0 - fy1; |
| |
| current.addcover(sub, fx1*sub); |
| |
| |
| iy1--; |
| |
| move_pen(ix1, iy1); |
| |
| while(iy1 != iy2) { |
| |
| current.addcover(-1,-fx1); |
| |
| |
| iy1--; |
| move_pen(ix1,iy1); |
| } |
| |
| current.addcover(fy2-1,(fy2-1)*fx1); |
| } |
| return; |
| } |
| |
| |
| |
| |
| if (dy > 0) { |
| dxdy = dx/dy; |
| |
| mult = (1 - fy1)*dxdy; |
| |
| |
| x_from = x1 + mult; |
| draw_scanline(iy1, x1, fy1, x_from, 1); |
| |
| |
| iy1++; |
| |
| move_pen((int)floor(x_from), iy1); |
| |
| while(iy1 != iy2) { |
| |
| x_to = x_from + dxdy; |
| draw_scanline(iy1, x_from, 0, x_to, 1); |
| x_from = x_to; |
| |
| |
| iy1++; |
| move_pen((int)floor(x_from), iy1); |
| } |
| |
| |
| draw_scanline(iy2, x_from, 0, x2, fy2); |
| } else { |
| dxdy = -dx/dy; |
| |
| mult = fy1*dxdy; |
| |
| |
| x_from = x1 + mult; |
| draw_scanline(iy1,x1,fy1,x_from,0); |
| |
| |
| iy1--; |
| |
| move_pen((int)floor(x_from), iy1); |
| |
| while(iy1 != iy2) { |
| x_to = x_from + dxdy; |
| draw_scanline(iy1, x_from, 1, x_to, 0); |
| x_from = x_to; |
| |
| iy1--; |
| move_pen((int)floor(x_from), iy1); |
| } |
| |
| draw_scanline(iy2, x_from, 1, x2, fy2); |
| } |
| } |
| |
| Real Polyspan::extract_alpha(Real area, bool evenodd) const { |
| if (area < 0) |
| area = -area; |
| |
| if (evenodd) { |
| |
| while (area > 1) |
| area -= 2; |
| |
| |
| if (area < 0) |
| area = -area; |
| } else { |
| |
| if (area > 1) |
| return 1; |
| } |
| |
| return area; |
| } |
| |
| |