Keith,
My calculations were all correct. I had just typed "p1" where I meant
to type "p2" in one spot.
Here's a new poly.5c with my area calculations using line-pixel
intersections. It seems to be handling the four interesting slope
cases correctly, (haven't tested vertical and horizontal yet).
I think my C implementation will not be much longer in being finished
now.
-Carl
/*
* $XFree86$
*
* Copyright � 2002 Keith Packard, member of The XFree86 Project, Inc.
*
* Permission to use, copy, modify, distribute, and sell this software and its
* documentation for any purpose is hereby granted without fee, provided that
* the above copyright notice appear in all copies and that both that
* copyright notice and this permission notice appear in supporting
* documentation, and that the name of Keith Packard not be used in
* advertising or publicity pertaining to distribution of the software without
* specific, written prior permission. Keith Packard makes no
* representations about the suitability of this software for any purpose. It
* is provided "as is" without express or implied warranty.
*
* KEITH PACKARD DISCLAIMS ALL WARRANTIES WITH REGARD TO THIS SOFTWARE,
* INCLUDING ALL IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS, IN NO
* EVENT SHALL KEITH PACKARD BE LIABLE FOR ANY SPECIAL, INDIRECT OR
* CONSEQUENTIAL DAMAGES OR ANY DAMAGES WHATSOEVER RESULTING FROM LOSS OF USE,
* DATA OR PROFITS, WHETHER IN AN ACTION OF CONTRACT, NEGLIGENCE OR OTHER
* TORTIOUS ACTION, ARISING OUT OF OR IN CONNECTION WITH THE USE OR
* PERFORMANCE OF THIS SOFTWARE.
*/
/*
* polygon rendering code
*/
typedef rational coord;
typedef int alpha;
namespace Point {
public typedef struct {
coord x;
coord y;
} point;
public point function new (coord x, coord y)
{
return (point) { x = x, y = y };
}
}
namespace IPoint {
public typedef struct {
int x;
int y;
} ipoint;
public ipoint function new (int x, int y)
{
return (ipoint) { x = x, y = y };
}
}
namespace Alpha {
public alpha function cover (coord amount, alpha max)
{
return floor (amount * max);
}
}
namespace Line {
import Point;
public typedef struct {
point top;
point bottom;
} line;
public exception horizontal (line l);
public exception vertical (line l);
public exception parallel (line l1, line l2);
/*
* Note that the line equation is "backwards" from convention,
* horizontal lines are not legal so we use x = my + b instead
* of y = mx + b
*/
public line function new (point top, point bottom)
{
return (line) { top = top, bottom = bottom };
}
coord function dx (line l)
{
return l.bottom.x - l.top.x;
}
coord function dy (line l)
{
return l.bottom.y - l.top.y;
}
public coord function slope (line l)
{
return dx(l) / dy(l);
}
public coord function intercept (line l)
{
return (l.top.x * l.bottom.y - l.top.y * l.bottom.x) / dy(l);
}
/*
* Return y coordinate for location 'x' on line
*/
public coord function y (line l, coord x)
{
if (dx(l) == 0)
raise horizontal (l);
if (dy(l) == 0)
raise vertical (l);
return (x - intercept (l)) / slope (l);
}
public coord function x (line l, coord y)
{
if (l.bottom.x == l.top.x)
raise horizontal (l);
if (l.bottom.y == l.top.y)
raise vertical (l);
return slope (l) * y + intercept (l);
}
public point function interesect (line l1, line l2)
{
coord y = ((intercept (l1) - intercept (l2)) /
(slope (l2) - slope (l1)));
return Point::new (x(l1, y), y);
}
}
namespace Rect {
import IPoint;
public typedef struct {
ipoint upper_left;
ipoint lower_right;
} rect;
public rect function new (ipoint ul, ipoint lr)
{
return (rect) { upper_left = ul, lower_right = lr };
}
public coord function width (rect r)
{
return r.lower_right.x - r.upper_left.x;
}
public coord function height (rect r)
{
return r.lower_right.y - r.upper_left.y;
}
}
namespace Trap {
import Point;
import Line;
import Rect;
public typedef struct {
coord top;
coord bottom;
line left;
line right;
} trap;
public trap function new (coord top, coord bottom, line left, line right)
{
return (trap) {
top = top,
bottom = bottom,
left = left,
right = right
};
}
/*
* Alpha coverage between 'bound' and 'y'
*/
alpha function scan_bound (coord bound, coord y, alpha max)
{
coord part = bound - y;
coord cover;
if (part <= 0)
part = 0;
if (part >= 1)
part = 1;
return Alpha::cover (part, max);
}
/*
* Alpha coverage of a particular scan line given the vertical
* limits of the trapezoid
*/
public alpha function scan_cover (trap t, coord y, alpha max)
{
y = floor (y);
return scan_bound (t.bottom, y, max) - scan_bound (t.top, y, max);
}
/* Compute sub-pixel vertical bounds of coverage */
coord function scan_top_y (trap t, coord y)
{
if (t.top < y)
return y;
else
return t.top;
}
coord function scan_bottom_y (trap t, coord y)
{
if (t.bottom > y + 1)
return y + 1;
else
return t.bottom;
}
point function scan_top (trap t, line l, coord y)
{
coord scan_y = scan_top_y (t, y);
return Point::new (Line::x(l, scan_y), scan_y);
}
point function scan_bottom (trap t, line l, coord y)
{
coord scan_y = scan_bottom_y (t, y);
return Point::new (Line::x(l, scan_y), scan_y);
}
public coord function pixel_line_cover_area (coord top_y,
coord bottom_y,
line l,
coord x)
{
coord slope = Line::slope (l);
coord area;
/* rectangle case */
if (slope == 0)
{
area = l.top.x - x;
if (area < 0)
area = 0;
else if (area > 1)
area = 1;
area *= (bottom_y - top_y);
return area;
}
else
{
coord yx = Line::y(l, x);
coord yx1 = Line::y(l, x+1);
coord xt = Line::x (l, top_y);
coord xb = Line::x (l, bottom_y);
coord dy, tri;
point p1, p2;
/* First, an ugly little bit to find the first and second
intersection of the line with the pixel*/
if (xt >= x && xt < x+1) {
p1.x = xt;
p1.y = top_y;
} else if (yx < yx1 && (yx >= top_y && yx < bottom_y)) {
p1.x = x;
p1.y = yx;
} else if (yx1 >= top_y && yx1 < bottom_y) {
p1.x = x+1;
p1.y = yx1;
} else {
/* Special case if line does not intersect pixel */
if ((yx < top_y && slope > 0)
|| (yx > bottom_y && slope < 0)) {
area = bottom_y - top_y;
} else {
area = 0;
}
return area;
}
if (xb >= x && xb < x + 1) {
p2.x = xb;
p2.y = bottom_y;
} else if (yx > yx1 && (yx >= top_y && yx1 < bottom_y)) {
p2.x = x;
p2.y = yx;
} else {
p2.x = x+1;
p2.y = yx1;
}
/* Now, the real area calculation */
/* First, form a rectangle by clipping the pixel with top
and bottom. Then intersect the line with that
rectangle. Name the topmost intersection point p1 and the
bottom p2. There are now seven cases to deal with
determined by whether p1 is on the left, top, or right of
the rectangle and whether p2 is on the left, bottom, or
right. The combinations of left-left and right-right are
of course illegal.
For each case, the area calculation involves at most two
multiplications, (one for a rectangle and one for a
triangle).
The equations for area are:
dx = x2 - x1
dy = y2 - y2
tri = 1/2 * dx * dy
Rp = bottom-top
R1 = (x1-left) * dy
R2 = (bottom-y1) * dx
top->left: area = -tri
top->bottom: area = R1 + tri
top->right: area = Rp - tri
right->left: area = Rp + R2 - tri
right->bottom: area = Rp + tri
left->bottom: area = tri
left->right: area = R2 - tri
*/
dy = p2.y - p1.y;
tri = 1/2 * (p2.x - p1.x) * dy;
if (p2.y == bottom_y) {
area = tri;
if (p1.y == top_y) {
area += (p1.x - x) * dy;
} else if (slope < 0) {
area += bottom_y - top_y;
}
} else {
area = -tri;
if (p1.y == top_y) {
if (slope > 0) {
area += bottom_y - top_y;
}
} else {
area += (bottom_y - p1.y) * (p2.x - p1.x);
if (slope < 0) {
area += bottom_y - top_y;
}
}
}
/* These are here because the outer loop isn't restricting
pixels to the bounds tightly, so we can end up here
with bottom_y < top_y. Otherwise, this wouldn't be
necessary. */
if (area < 0) {
area = 0;
}
else if (area > 1) {
area = 1;
}
/*
printf("\ntop = %f, bottom = %f, x = %f, x+1 = %f", top_y, bottom_y, x,
x+1);
printf("\nxt = %f, xb = %f, yx = %f, yx1 = %f", xt, xb, yx, yx1);
printf("\np1 = (%f, %f) p2 = (%f, %f)\n", p1.x, p1.y, p2.x, p2.y);
printf("\narea = %f\n", area);
*/
return area;
}
}
public alpha function pixel_line_cover (coord top_y,
coord bottom_y,
line l,
coord x,
alpha max)
{
coord area;
area = pixel_line_cover_area(top_y, bottom_y, l, x);
return Alpha::cover (area, max);
}
public alpha function pixel_cover (trap t, point p, alpha max)
{
coord top_y = scan_top_y (t, p.y);
coord bottom_y = scan_bottom_y (t, p.y);
alpha total = scan_cover (t, p.y, max);
alpha left_cover = pixel_line_cover (top_y,
bottom_y,
t.left,
p.x,
total);
alpha right_cover = pixel_line_cover (top_y,
bottom_y,
t.right,
p.x,
total);
return right_cover - left_cover;
}
coord function min (coord a, coord b)
{
return a < b ? a : b;
}
coord function max (coord a, coord b)
{
return a > b ? a : b;
}
public rect function bounds (trap t)
{
return Rect::new (Point::new (floor (min (Line::x (t.left, t.top),
Line::x (t.left, t.bottom))),
floor (t.top)),
Point::new (ceil (max (Line::x (t.right, t.top),
Line::x (t.right, t.bottom))),
ceil (t.bottom)));
}
public void function draw (file f, trap t)
{
rect b = bounds (t);
int x, y;
File::fprintf (f, "%d %d\n", b.lower_right.x + 1, b.lower_right.y + 1);
for (y = 0; y <= b.lower_right.y; y++)
{
for (x = 0; x <= b.lower_right.x; x++)
File::fprintf (f, "%d ", pixel_cover (t, Point::new (x, y), 255));
File::fprintf (f, "\n");
}
File::flush (f);
}
}
namespace Draw {
file f;
int f_set = 0;
import Trap;
public void function init ()
{
if (f_set)
File::close (f);
f = File::pipe ("draw", (string[1]) { "draw" }, "w");
f_set = 1;
}
public void function draw (trap t)
{
if (!f_set)
init ();
Trap::draw (f, t);
}
public void function done ()
{
File::close (f);
f_set = 0;
}
}
Trap::trap t1 = Trap::new (1.5, 25.5,
Line::new (Point::new (6, 1),
Point::new (1, 31)),
Line::new (Point::new (8, 1),
Point::new (13, 31)));
Trap::trap t2 = Trap::new (3.5, 100,
Line::new (Point::new (20, 3.5),
Point::new (150, 203.5)),
Line::new (Point::new (20.9, 3.5),
Point::new (150.9, 203.5)));
Trap::trap t3 = Trap::new (1.5, 15.5,
Line::new (Point::new (10, 1),
Point::new (60, 31)),
Line::new (Point::new (80, 1),
Point::new (30, 31)));
--
Carl Worth
USC Information Sciences Institute [EMAIL PROTECTED]
3811 N. Fairfax Dr. #200, Arlington VA 22203 703-812-3725
