Blame c++/contourgl/polyspan.cpp

93cbac
/*
93cbac
	polyspan.cpp
93cbac
	Polyspan
93cbac
93cbac
	Copyright (c) 2002-2005 Robert B. Quattlebaum Jr., Adrian Bentley
93cbac
	Copyright (c) 2007, 2008 Chris Moore
93cbac
	Copyright (c) 2012-2013 Carlos Lรณpez
93cbac
	......... ... 2015 Ivan Mahonin
93cbac
93cbac
	This package is free software; you can redistribute it and/or
93cbac
	modify it under the terms of the GNU General Public License as
93cbac
	published by the Free Software Foundation; either version 2 of
93cbac
	the License, or (at your option) any later version.
93cbac
93cbac
	This package is distributed in the hope that it will be useful,
93cbac
	but WITHOUT ANY WARRANTY; without even the implied warranty of
93cbac
	MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
93cbac
	General Public License for more details.
93cbac
*/
93cbac
93cbac
#include <cassert></cassert>
93cbac
93cbac
#include "polyspan.h"
93cbac
93cbac
6e407d
using namespace std;
6e407d
6e407d
93cbac
Polyspan::Polyspan():
93cbac
	open_index(0),
93cbac
	cur_x(0.0),
93cbac
	cur_y(0.0),
93cbac
	close_x(0.0),
93cbac
	close_y(0.0),
93cbac
	flags(NotSorted)
93cbac
{ }
93cbac
93cbac
void Polyspan::clear() {
93cbac
	covers.clear();
93cbac
	cur_x = cur_y = close_x = close_y = 0;
93cbac
	open_index = 0;
93cbac
	current.set(0, 0, 0, 0);
93cbac
	flags = NotSorted;
93cbac
}
93cbac
93cbac
// add the current cell, but only if there is information to add
93cbac
void Polyspan::addcurrent() {
93cbac
	if (current.cover || current.area) {
93cbac
		if (covers.size() == covers.capacity())
93cbac
			covers.reserve(covers.size() + 1024*1024);
93cbac
		covers.push_back(current);
93cbac
	}
93cbac
}
93cbac
93cbac
// move to the next cell (cover values 0 initially), keeping the current if necessary
93cbac
void Polyspan::move_pen(int x, int y) {
93cbac
	if (y != current.y || x != current.x) {
93cbac
		addcurrent();
93cbac
		current.set(x, y, 0, 0);
93cbac
	}
93cbac
}
93cbac
93cbac
// close the primitives with a line (or rendering will not work as expected)
93cbac
void Polyspan::close() {
93cbac
	if (flags & NotClosed) {
93cbac
		if (cur_x != close_x || cur_y != close_y) {
93cbac
			line_to(close_x, close_y);
93cbac
			addcurrent();
93cbac
			current.setcover(0,0);
93cbac
		}
93cbac
		flags &= ~NotClosed;
93cbac
	}
93cbac
}
93cbac
93cbac
// Not recommended - destroys any separation of spans currently held
93cbac
void Polyspan::merge_all() {
93cbac
	sort(covers.begin(), covers.end());
93cbac
	open_index = 0;
93cbac
}
93cbac
93cbac
// will sort the marks if they are not sorted
93cbac
void Polyspan::sort_marks() {
93cbac
	if (flags & NotSorted) {
7c6b57
		// only sort the open index
93cbac
		addcurrent();
93cbac
		current.setcover(0, 0);
93cbac
93cbac
		sort(covers.begin() + open_index, covers.end());
6e407d
93cbac
		flags &= ~NotSorted;
93cbac
	}
93cbac
}
93cbac
93cbac
// encapsulate the current sublist of marks (used for drawing)
93cbac
void Polyspan::encapsulate_current() {
93cbac
	// sort the current list then reposition the open list section
93cbac
	sort_marks();
93cbac
	open_index = covers.size();
93cbac
}
93cbac
93cbac
// move to start a new primitive list (enclose the last primitive if need be)
93cbac
void Polyspan::move_to(Real x, Real y) {
93cbac
	close();
93cbac
	if (isnan(x)) x=0;
93cbac
	if (isnan(y)) y=0;
93cbac
	move_pen((int)floor(x), (int)floor(y));
93cbac
	close_y = cur_y = y;
93cbac
	close_x = cur_x = x;
93cbac
}
93cbac
93cbac
// primitive_to functions
93cbac
void Polyspan::line_to(Real x, Real y) {
93cbac
	Real n[4] = {0, 0, 0, 0};
93cbac
	bool afterx = false;
93cbac
93cbac
	const Real xin(x), yin(y);
93cbac
93cbac
	Real dx = x - cur_x;
93cbac
	Real dy = y - cur_y;
93cbac
93cbac
	// CLIP IT!!!!
93cbac
	// outside y - ignore entirely
93cbac
	if ( (cur_y >= window.maxy && y >= window.maxy)
93cbac
	  || (cur_y <  window.miny && y <  window.miny) )
93cbac
	{
93cbac
		cur_x = x;
93cbac
		cur_y = y;
93cbac
	} else { // not degenerate - more complicated
93cbac
		if (dy > 0) { //be sure it's not tooooo small
93cbac
			// cur_y ... window.miny ... window.maxy ... y
93cbac
93cbac
			// initial degenerate - initial clip
93cbac
			if (cur_y < window.miny) {
93cbac
				// new clipped start point (must also move pen)
93cbac
				n[2] = cur_x + (window.miny - cur_y)*dx/dy;
93cbac
93cbac
				cur_x = n[2];
93cbac
				cur_y = window.miny;
93cbac
				move_pen((int)floor(cur_x), window.miny);
93cbac
			}
93cbac
93cbac
			// generate data for the ending clipped info
93cbac
			if (y > window.maxy) {
93cbac
				// initial line to intersection (and degenerate)
93cbac
				n[2] = x + (window.maxy - y)*dx/dy;
93cbac
93cbac
				//intersect coords
93cbac
				x = n[2];
93cbac
				y = window.maxy;
93cbac
			}
93cbac
		} else {
93cbac
			// initial degenerate - initial clip
93cbac
			if (cur_y > window.maxy) {
93cbac
				// new clipped start point (must also move pen)
93cbac
				n[2] = cur_x + (window.maxy - cur_y)*dx/dy;
93cbac
93cbac
				cur_x = n[2];
93cbac
				cur_y = window.maxy;
93cbac
				move_pen((int)floor(cur_x), window.maxy);
93cbac
			}
93cbac
93cbac
			// generate data for the ending clipped info
93cbac
			if (y < window.miny) {
93cbac
				// initial line to intersection (and degenerate)
93cbac
				n[2] = x + (window.miny - y)*dx/dy;
93cbac
93cbac
				// intersect coords
93cbac
				x = n[2];
93cbac
				y = window.miny;
93cbac
			}
93cbac
		}
93cbac
93cbac
		// all degenerate - but require bounded clipped values
93cbac
		if ( (cur_x >= window.maxx && x >= window.maxx)
93cbac
		  || (cur_x <  window.minx && x <  window.minx) )
93cbac
		{
93cbac
			//clip both vertices - but only needed in the x direction
6e407d
			cur_x = max(cur_x,	(Real)window.minx);
6e407d
			cur_x = min(cur_x,	(Real)window.maxx);
93cbac
93cbac
			//clip the dest values - y is already clipped
6e407d
			x = max(x, (Real)window.minx);
6e407d
			x = min(x, (Real)window.maxx);
93cbac
93cbac
			//must start at new point...
93cbac
			move_pen((int)floor(cur_x), (int)floor(cur_y));
93cbac
93cbac
			draw_line(cur_x,cur_y,x,y);
93cbac
93cbac
			cur_x = xin;
93cbac
			cur_y = yin;
93cbac
		} else {
93cbac
			// clip x
93cbac
			if (dx > 0) {
93cbac
				// initial degenerate - initial clip
93cbac
				if (cur_x < window.minx) {
93cbac
					// need to draw an initial segment from clippedx,cur_y to clippedx,intersecty
93cbac
					n[2] = cur_y + (window.minx - cur_x)*dy/dx;
93cbac
93cbac
					move_pen(window.minx, (int)floor(cur_y));
93cbac
					draw_line(window.minx, cur_y, window.minx, n[2]);
93cbac
93cbac
					cur_x = window.minx;
93cbac
					cur_y = n[2];
93cbac
				}
93cbac
93cbac
				// generate data for the ending clipped info
93cbac
				if (x > window.maxx) {
93cbac
					// initial line to intersection (and degenerate)
93cbac
					n[2] = y + (window.maxx - x)*dy/dx;
93cbac
93cbac
					n[0] = window.maxx;
93cbac
					n[1] = y;
93cbac
93cbac
					// intersect coords
93cbac
					x = window.maxx;
93cbac
					y = n[2];
93cbac
					afterx = true;
93cbac
				}
93cbac
			} else {
93cbac
				// initial degenerate - initial clip
93cbac
				if (cur_x > window.maxx) {
93cbac
					// need to draw an initial segment from clippedx,cur_y to clippedx,intersecty
93cbac
					n[2] = cur_y + (window.maxx - cur_x)*dy/dx;
93cbac
93cbac
					move_pen(window.maxx, (int)floor(cur_y));
93cbac
					draw_line(window.maxx, cur_y, window.maxx, n[2]);
93cbac
93cbac
					cur_x = window.maxx;
93cbac
					cur_y = n[2];
93cbac
				}
93cbac
93cbac
				// generate data for the ending clipped info
93cbac
				if (x < window.minx) {
93cbac
					//initial line to intersection (and degenerate)
93cbac
					n[2] = y + (window.minx - x)*dy/dx;
93cbac
93cbac
					n[0] = window.minx;
93cbac
					n[1] = y;
93cbac
93cbac
					//intersect coords
93cbac
					x = window.minx;
93cbac
					y = n[2];
93cbac
					afterx = true;
93cbac
				}
93cbac
			}
93cbac
93cbac
			move_pen((int)floor(cur_x), (int)floor(cur_y));
93cbac
			// draw the relevant line (clipped)
93cbac
			draw_line(cur_x, cur_y, x, y);
93cbac
93cbac
			if (afterx)
93cbac
				draw_line(x, y, n[0], n[1]);
93cbac
93cbac
			cur_x = xin;
93cbac
			cur_y = yin;
93cbac
		}
93cbac
	}
93cbac
93cbac
	flags |= NotClosed | NotSorted;
93cbac
}
93cbac
a7f97a
bool Polyspan::clip_conic(const Vector *p, const ContextRect &r) {
6e407d
	const Real minx = min(min(p[0][0], p[1][0]), p[2][0]);
6e407d
	const Real miny = min(min(p[0][1], p[1][1]), p[2][1]);
6e407d
	const Real maxx = max(max(p[0][0], p[1][0]), p[2][0]);
6e407d
	const Real maxy = max(max(p[0][1], p[1][1]), p[2][1]);
93cbac
93cbac
	return 	(minx > r.maxx) ||
93cbac
			(maxx < r.minx) ||
93cbac
			(miny > r.maxy) ||
93cbac
			(maxy < r.miny);
93cbac
}
93cbac
a7f97a
Real Polyspan::max_edges_conic(const Vector *p) {
93cbac
	const Real x1 = p[1][0] - p[0][0];
93cbac
	const Real y1 = p[1][1] - p[0][1];
93cbac
93cbac
	const Real x2 = p[2][0] - p[1][0];
93cbac
	const Real y2 = p[2][1] - p[1][1];
93cbac
93cbac
	const Real d1 = x1*x1 + y1*y1;
93cbac
	const Real d2 = x2*x2 + y2*y2;
93cbac
6e407d
	return max(d1,d2);
93cbac
}
93cbac
93cbac
void Polyspan::subd_conic_stack(Vector *arc) {
93cbac
	/*
93cbac
93cbac
	b0
93cbac
	*		0+1 a
93cbac
	b1 b	*		1+2*1+2 a
93cbac
	*		1+2	b	*
93cbac
	b2 		*
93cbac
	*
93cbac
93cbac
	0.1.2 ->	0.1 2 3.4
93cbac
93cbac
	*/
93cbac
93cbac
	Real a, b;
93cbac
93cbac
93cbac
	arc[4][0] = arc[2][0];
93cbac
	b = arc[1][0];
93cbac
93cbac
	a = arc[1][0] = (arc[0][0] + b)/2;
93cbac
	b = arc[3][0] = (arc[4][0] + b)/2;
93cbac
	arc[2][0] = (a + b)/2;
93cbac
93cbac
93cbac
	arc[4][1] = arc[2][1];
93cbac
	b = arc[1][1];
93cbac
93cbac
	a = arc[1][1] = (arc[0][1] + b)/2;
93cbac
93cbac
	b = arc[3][1] = (arc[4][1] + b)/2;
93cbac
	arc[2][1] = (a + b)/2;
93cbac
93cbac
	/* //USING SIMD
93cbac
93cbac
	arc[4] = arc[2];
93cbac
93cbac
	arc[3] = (arc[2] + arc[1])/2;
93cbac
	arc[1] = (arc[0] + arc[1])/2;
93cbac
93cbac
	arc[2] = (arc[1] + arc[3])/2;
93cbac
93cbac
	*/
93cbac
}
93cbac
93cbac
void Polyspan::conic_to(Real x1, Real y1, Real x, Real y) {
93cbac
	Vector *current = arc;
93cbac
	int		level = 0;
93cbac
	int 	num = 0;
93cbac
	bool	onsecond = false;
93cbac
93cbac
	arc[0] = Vector(x, y);
93cbac
	arc[1] = Vector(x1, y1);
93cbac
	arc[2] = Vector(cur_x, cur_y);
93cbac
93cbac
	// just draw the line if it's outside
93cbac
	if (clip_conic(arc, window))
93cbac
	{
93cbac
		line_to(x,y);
93cbac
		return;
93cbac
	}
93cbac
93cbac
	// Ok so it's not super degenerate, subdivide and draw (run through minimum subdivision levels first)
93cbac
	while(current >= arc) {
93cbac
		assert(num < MAX_SUBDIVISION_SIZE);
93cbac
93cbac
		// if the curve is clipping then draw degenerate
93cbac
		if (clip_conic(current, window)) {
93cbac
			line_to(current[0][0],current[0][1]); //backwards so front is destination
93cbac
			current -= 2;
93cbac
			if (onsecond) level--;
93cbac
			onsecond = true;
93cbac
			num--;
93cbac
			continue;
93cbac
		} else
93cbac
		// if we are not at the level minimum
93cbac
		if (level < MIN_SUBDIVISION_DRAW_LEVELS) {
93cbac
			subd_conic_stack(current);
93cbac
			current += 2; 		// cursor on second curve
93cbac
			level ++;
93cbac
			num ++;
93cbac
			onsecond = false;
93cbac
			continue;
93cbac
		} else
93cbac
		// split it again, if it's too big
93cbac
		if (max_edges_conic(current) > 0.25) { // distance of .5 (cover no more than half the pixel)
93cbac
			subd_conic_stack(current);
93cbac
			current += 2; 		// cursor on second curve
93cbac
			level ++;
93cbac
			num ++;
93cbac
			onsecond = false;
93cbac
		} else { // NOT TOO BIG? RENDER!!!
93cbac
			// cur_x, cur_y = current[2], so we need to go 1,0
93cbac
			line_to(current[1][0], current[1][1]);
93cbac
			line_to(current[0][0], current[0][1]);
93cbac
93cbac
			current -= 2;
93cbac
			if (onsecond) level--;
93cbac
			num--;
93cbac
			onsecond = true;
93cbac
		}
93cbac
	}
93cbac
}
93cbac
a7f97a
bool Polyspan::clip_cubic(const Vector *p, const ContextRect &r) {
93cbac
	return 	((p[0][0] > r.maxx) && (p[1][0] > r.maxx) && (p[2][0] > r.maxx) && (p[3][0] > r.maxx)) ||
93cbac
			((p[0][0] < r.minx) && (p[1][0] < r.minx) && (p[2][0] < r.minx) && (p[3][0] < r.minx)) ||
93cbac
			((p[0][1] > r.maxy) && (p[1][1] > r.maxy) && (p[2][1] > r.maxy) && (p[3][1] > r.maxy)) ||
93cbac
			((p[0][1] < r.miny) && (p[1][1] < r.miny) && (p[2][1] < r.miny) && (p[3][1] < r.miny));
93cbac
}
93cbac
a7f97a
Real Polyspan::max_edges_cubic(const Vector *p) {
93cbac
	const Real x1 = p[1][0] - p[0][0];
93cbac
	const Real y1 = p[1][1] - p[0][1];
93cbac
93cbac
	const Real x2 = p[2][0] - p[1][0];
93cbac
	const Real y2 = p[2][1] - p[1][1];
93cbac
93cbac
	const Real x3 = p[3][0] - p[2][0];
93cbac
	const Real y3 = p[3][1] - p[2][1];
93cbac
93cbac
	const Real d1 = x1*x1 + y1*y1;
93cbac
	const Real d2 = x2*x2 + y2*y2;
93cbac
	const Real d3 = x3*x3 + y3*y3;
93cbac
6e407d
	return max(max(d1, d2), d3);
93cbac
}
93cbac
93cbac
void Polyspan::subd_cubic_stack(Vector *arc) {
93cbac
	Real a, b, c;
93cbac
93cbac
	/*
93cbac
93cbac
	b0
93cbac
	*		0+1 a
93cbac
	b1 b	*		1+2*1+2 a
93cbac
	*		1+2	b	*			0+3*1+3*2+3
93cbac
	b2 c	*		1+2*2+2	b	*
93cbac
	*		2+3	c	*
93cbac
	b3 		*
93cbac
	*
93cbac
93cbac
	0.1 2.3 ->	0.1 2 3 4 5.6
93cbac
93cbac
	*/
93cbac
93cbac
	arc[6][0] = arc[3][0];
93cbac
93cbac
	b = arc[1][0];
93cbac
	c = arc[2][0];
93cbac
93cbac
	a = arc[1][0] = (arc[0][0] + b)/2;
93cbac
	b = (b + c)/2;
93cbac
	c = arc[5][0] = (arc[6][0] + c)/2;
93cbac
93cbac
	a = arc[2][0] = (a + b)/2;
93cbac
	b = arc[4][0] = (b + c)/2;
93cbac
93cbac
	arc[3][0] = (a + b)/2;
93cbac
93cbac
93cbac
	arc[6][1] = arc[3][1];
93cbac
93cbac
	b = arc[1][1];
93cbac
	c = arc[2][1];
93cbac
93cbac
	a = arc[1][1] = (arc[0][1] + b)/2;
93cbac
	b = (b + c)/2;
93cbac
	c = arc[5][1] = (arc[6][1] + c)/2;
93cbac
93cbac
	a = arc[2][1] = (a + b)/2;
93cbac
	b = arc[4][1] = (b + c)/2;
93cbac
93cbac
	arc[3][1] = (a + b)/2;
93cbac
}
93cbac
93cbac
void Polyspan::cubic_to(Real x1, Real y1, Real x2, Real y2, Real x, Real y) {
93cbac
	Vector *current = arc;
93cbac
	int		num = 0;
93cbac
	int		level = 0;
93cbac
	bool	onsecond = false;
93cbac
93cbac
	arc[0] = Vector(x, y);
93cbac
	arc[1] = Vector(x2, y2);
93cbac
	arc[2] = Vector(x1, y1);
93cbac
	arc[3] = Vector(cur_x, cur_y);
93cbac
93cbac
	// just draw the line if it's outside
93cbac
	if (clip_cubic(arc, window)) {
93cbac
		line_to(x,y);
93cbac
		return;
93cbac
	}
93cbac
93cbac
	// Ok so it's not super degenerate, subdivide and draw (run through minimum subdivision levels first)
93cbac
	while(current >= arc) { // once current goes below arc, there are no more curves left
93cbac
		assert(num < MAX_SUBDIVISION_SIZE);
93cbac
93cbac
		// if we are not at the level minimum
93cbac
		if (level < MIN_SUBDIVISION_DRAW_LEVELS) {
93cbac
			subd_cubic_stack(current);
93cbac
			current += 3; 		// cursor on second curve
93cbac
			level ++;
93cbac
			num ++;
93cbac
			onsecond = false;
93cbac
			continue;
93cbac
		} else
93cbac
		// if the curve is clipping then draw degenerate
93cbac
		if (clip_cubic(current, window)) {
93cbac
			line_to(current[0][0], current[0][1]); // backwards so front is destination
93cbac
			current -= 3;
93cbac
			if (onsecond) level--;
93cbac
			onsecond = true;
93cbac
			num --;
93cbac
			continue;
93cbac
		} else
93cbac
		// split it again, if it's too big
93cbac
		if (max_edges_cubic(current) > 0.25) { //could use max_edges<3>
93cbac
			subd_cubic_stack(current);
93cbac
			current += 3; 		// cursor on second curve
93cbac
			level ++;
93cbac
			num ++;
93cbac
			onsecond = false;
93cbac
		} else { // NOT TOO BIG? RENDER!!!
93cbac
			// cur_x, cur_y = current[3], so we need to go 2,1,0
93cbac
			line_to(current[2][0], current[2][1]);
93cbac
			line_to(current[1][0], current[1][1]);
93cbac
			line_to(current[0][0], current[0][1]);
93cbac
93cbac
			current -= 3;
93cbac
			if (onsecond) level--;
93cbac
			num --;
93cbac
			onsecond = true;
93cbac
		}
93cbac
	}
93cbac
}
93cbac
93cbac
void Polyspan::draw_scanline(int y, Real x1, Real y1, Real x2, Real y2) {
93cbac
	int	ix1 = (int)floor(x1);
93cbac
	int	ix2 = (int)floor(x2);
93cbac
	Real fx1 = x1 - ix1;
93cbac
	Real fx2 = x2 - ix2;
93cbac
93cbac
	Real dx,dy,dydx,mult;
93cbac
93cbac
	dx = x2 - x1;
93cbac
	dy = y2 - y1;
93cbac
93cbac
	// case horizontal line
93cbac
	if (y1 == y2) {
93cbac
		move_pen(ix2, y); // pen needs to be at the last coord
93cbac
		return;
93cbac
	}
93cbac
93cbac
	// case all in same pixel
93cbac
	if (ix1 == ix2) { // impossible for degenerate case (covered by the previous cases)
93cbac
		current.addcover(dy, (fx1 + fx2)*dy/2); // horizontal trapezoid area
93cbac
		return;
93cbac
	}
93cbac
93cbac
	if (dx > 0) {
93cbac
		// ---->	fx1...1  0...1  ...  0...1  0...fx2
93cbac
		dydx = dy/dx;
93cbac
93cbac
		// set initial values
93cbac
		// Iterate through the covered pixels
93cbac
		mult = (1 - fx1)*dydx;	// next y intersection diff value (at 1)
93cbac
93cbac
		// first pixel
93cbac
		current.addcover(mult, (1 + fx1)*mult/2);	// fx1, fy1, 1, fy@1 - starting trapezoidal area
93cbac
93cbac
		// move to the next pixel
93cbac
		y1 += mult;
93cbac
		ix1++;
93cbac
93cbac
		move_pen(ix1, y);
93cbac
93cbac
		// set up for whole ones
93cbac
		while(ix1 != ix2) {
93cbac
			// trapezoid(0, y1, 1, y1 + dydx);
93cbac
			current.addcover(dydx,dydx/2); // accumulated area 1/2 the cover
93cbac
93cbac
			// move to next pixel (+1)
93cbac
			ix1++;
93cbac
			y1 += dydx;
93cbac
			move_pen(ix1, y);
93cbac
		}
93cbac
93cbac
		// last pixel
93cbac
		// final y-pos - last intersect pos
93cbac
		mult = fx2 * dydx;
93cbac
		current.addcover(mult, (0 + fx2)*mult/2);
93cbac
	} else {
93cbac
		// fx2...1  0...1  ...  0...1  0...fx1   <----
93cbac
		// mult = (0 - fx1) * dy / dx;
93cbac
		// neg sign sucked into dydx
93cbac
		dydx = -dy/dx;
93cbac
93cbac
		// set initial values
93cbac
		// Iterate through the covered pixels
93cbac
		mult = fx1*dydx; // next y intersection diff value
93cbac
93cbac
		// first pixel
93cbac
		current.addcover(mult, fx1*mult/2); // fx1, fy1, 0, fy@0 - starting trapezoidal area
93cbac
93cbac
		// move to next pixel
93cbac
		y1 += mult;
93cbac
		ix1--;
93cbac
93cbac
		move_pen(ix1, y);
93cbac
93cbac
		// set up for whole ones
93cbac
		while(ix1 != ix2) {
93cbac
			// trapezoid(0, y1, 1, y1+dydx);
93cbac
			current.addcover(dydx, dydx/2); // accumulated area 1/2 the cover
93cbac
93cbac
			// move to next pixel (-1)
93cbac
			y1 += dydx;
93cbac
			ix1--;
93cbac
			move_pen(ix1, y);
93cbac
		}
93cbac
93cbac
		// last pixel
93cbac
		mult = y2 - y1; // final y-pos - last intersect pos
93cbac
93cbac
		current.addcover(mult, (fx2+1)*mult/2);
93cbac
	}
93cbac
}
93cbac
93cbac
void Polyspan::draw_line(Real x1, Real y1, Real x2, Real y2) {
93cbac
	int iy1 = (int)floor(y1);
93cbac
	int iy2 = (int)floor(y2);
93cbac
	Real fy1 = y1 - iy1;
93cbac
	Real fy2 = y2 - iy2;
93cbac
93cbac
	assert(!isnan(fy1));
93cbac
	assert(!isnan(fy2));
93cbac
93cbac
	Real dx,dy,dxdy,mult,x_from,x_to;
93cbac
93cbac
	const Real SLOPE_EPSILON = 1e-10;
93cbac
93cbac
	// case all one scanline
93cbac
	if (iy1 == iy2) {
93cbac
		draw_scanline(iy1, x1, y1, x2, y2);
93cbac
		return;
93cbac
	}
93cbac
93cbac
	// difference values
93cbac
	dy = y2 - y1;
93cbac
	dx = x2 - x1;
93cbac
93cbac
	// case vertical line
93cbac
	if (dx < SLOPE_EPSILON && dx > -SLOPE_EPSILON) {
93cbac
		// calc area and cover on vertical line
93cbac
		if (dy > 0) {
93cbac
			// ---->	fx1...1  0...1  ...  0...1  0...fx2
93cbac
			Real sub;
93cbac
93cbac
			int ix1 = (int)floor(x1);
93cbac
			Real fx1 = x1 - ix1;
93cbac
93cbac
			// current pixel
93cbac
			sub = 1 - fy1;
93cbac
93cbac
			current.addcover(sub, fx1*sub);
93cbac
93cbac
			// next pixel
93cbac
			iy1++;
93cbac
93cbac
			// move pen to next pixel
93cbac
			move_pen(ix1, iy1);
93cbac
93cbac
			while(iy1 != iy2) {
93cbac
				// accumulate cover
93cbac
				current.addcover(1,fx1);
93cbac
93cbac
				// next pixel
93cbac
				iy1++;
93cbac
				move_pen(ix1, iy1);
93cbac
			}
93cbac
93cbac
			// last pixel
93cbac
			current.addcover(fy2, fy2*fx1);
93cbac
		} else {
93cbac
			Real sub;
93cbac
93cbac
			int	ix1 = (int)floor(x1);
93cbac
			Real fx1 = x1 - ix1;
93cbac
93cbac
			// current pixel
93cbac
			sub = 0 - fy1;
93cbac
93cbac
			current.addcover(sub, fx1*sub);
93cbac
93cbac
			// next pixel
93cbac
			iy1--;
93cbac
93cbac
			move_pen(ix1, iy1);
93cbac
93cbac
			while(iy1 != iy2) {
93cbac
				// accumulate in current pixel
93cbac
				current.addcover(-1,-fx1);
93cbac
93cbac
				// move to next
93cbac
				iy1--;
93cbac
				move_pen(ix1,iy1);
93cbac
			}
93cbac
93cbac
			current.addcover(fy2-1,(fy2-1)*fx1);
93cbac
		}
93cbac
		return;
93cbac
	}
93cbac
93cbac
	// case normal line - guaranteed dx != 0 && dy != 0
93cbac
93cbac
	// calculate the initial intersection with "next" scanline
93cbac
	if (dy > 0) {
93cbac
		dxdy = dx/dy;
93cbac
93cbac
		mult = (1 - fy1)*dxdy;
93cbac
93cbac
		// x intersect scanline
93cbac
		x_from = x1 + mult;
93cbac
		draw_scanline(iy1, x1, fy1, x_from, 1);
93cbac
93cbac
		// move to next line
93cbac
		iy1++;
93cbac
93cbac
		move_pen((int)floor(x_from), iy1);
93cbac
93cbac
		while(iy1 != iy2) {
93cbac
			// keep up on the x axis, and render the current scanline
93cbac
			x_to = x_from + dxdy;
93cbac
			draw_scanline(iy1, x_from, 0, x_to, 1);
93cbac
			x_from = x_to;
93cbac
93cbac
			// move to next pixel
93cbac
			iy1++;
93cbac
			move_pen((int)floor(x_from), iy1);
93cbac
		}
93cbac
93cbac
		//draw the last one, fractional
93cbac
		draw_scanline(iy2, x_from, 0, x2, fy2);
93cbac
	} else {
93cbac
		dxdy = -dx/dy;
93cbac
93cbac
		mult = fy1*dxdy;
93cbac
93cbac
		// x intersect scanline
93cbac
		x_from = x1 + mult;
93cbac
		draw_scanline(iy1,x1,fy1,x_from,0);
93cbac
93cbac
		// each line after
93cbac
		iy1--;
93cbac
93cbac
		move_pen((int)floor(x_from), iy1);
93cbac
93cbac
		while(iy1 != iy2) {
93cbac
			x_to = x_from + dxdy;
93cbac
			draw_scanline(iy1, x_from, 1, x_to, 0);
93cbac
			x_from = x_to;
93cbac
93cbac
			iy1--;
93cbac
			move_pen((int)floor(x_from), iy1);
93cbac
		}
93cbac
		// draw the last one, fractional
93cbac
		draw_scanline(iy2, x_from, 1, x2, fy2);
93cbac
	}
93cbac
}
93cbac
93cbac
Real Polyspan::extract_alpha(Real area, bool evenodd) const {
93cbac
	if (area < 0)
93cbac
		area = -area;
93cbac
93cbac
	if (evenodd) {
93cbac
		// even-odd winding style
93cbac
		while (area > 1)
93cbac
			area -= 2;
93cbac
93cbac
		// want pyramid like thing
93cbac
		if (area < 0)
93cbac
			area = -area;
93cbac
	} else {
93cbac
		// non-zero winding style
93cbac
		if (area > 1)
93cbac
			return 1;
93cbac
	}
93cbac
93cbac
	return area;
93cbac
}
93cbac
93cbac
/* === E N T R Y P O I N T ================================================= */