/* See LICENSE file for copyright and license details. */
#include "common.h"
#ifndef TEST
/*
* The implementation in this fill is not supposed to be fast,
* it is supposed to be absolutely correct. The implementation
* shall be as clear and obvious as possible. It is important
* that everything written to cells is as precise as possible
* and that the function behavious correctly when outside the
* raster. This implementation shall be usable to generate an
* as perfect as possible rasterisation and shall be usable to
* test the correctness and accuracy of the fast implementation.
*/
void
draw_linear_bezier_reference(RASTER *restrict raster, double x1, double y1, double x2, double y2)
{
double dx = x2 - x1;
double dy = y2 - y1;
int xdir = SIGNUM(dx);
int ydir = SIGNUM(dy);
double kx = dx / dy;
double ky = dy / dx;
double prevX, prevY, x, y, cx, cy, h2x, h2y;
double xfloor, yfloor;
ssize_t cellX, cellY;
size_t cell;
prevX = x1;
prevY = y1;
for (; prevX != x2 || prevY != y2; prevX = x, prevY = y) {
/* Find next vertical and next hozitonal grid line */
x = xdir < 0 ? floor(prevX) : xdir > 0 ? ceil(prevX) : prevX;
y = ydir < 0 ? floor(prevY) : ydir > 0 ? ceil(prevY) : prevY;
x = x == prevX ? x + xdir : x;
y = y == prevY ? y + ydir : y;
/* Limit to the extend of the drawn line segment */
if ((xdir < 0 && x < x2) || (xdir > 0 && x > x2))
x = x2;
if ((ydir < 0 && y < y2) || (ydir > 0 && y > y2))
y = y2;
/* Find next cell edge */
if (xdir && ydir) {
cy = y1 + (x - x1) * ky;
cx = x1 + (y - y1) * kx;
h2x = (cy - prevY) * (cy - prevY) + (x - prevX) * (x - prevX);
h2y = (cx - prevX) * (cx - prevX) + (y - prevY) * (y - prevY);
if (h2x < h2y)
y = cy;
else
x = cx;
/* Make sure loop will exit when we reach the end */
if ((xdir < 0 && x <= x2) || (xdir > 0 && x >= x2) ||
(ydir < 0 && y <= y2) || (ydir > 0 && y >= y2)) {
x = x2;
y = y2;
}
}
/* Select cell to draw in */
xfloor = xdir >= 0 ? floor(prevX) : floor(x);
yfloor = ydir >= 0 ? floor(prevY) : floor(y);
cellX = (ssize_t)xfloor;
cellY = (ssize_t)yfloor;
/* Do not draw if above or below the raster*/
if (cellY < 0 || (size_t)cellY >= raster->height)
continue;
if (cellX < 0) {
/* Draw on first column in raster of outside of raster on the left side,
* with full horizontal coverage, `.opposite_coverage` one the actual
* cell (outside of the raster) will contribute to the first column's
* `.cell_coverage` */
cell = (size_t)cellY * raster->width;
raster->cells[cell].opposite_coverage += y - prevY;
raster->cells[cell].cell_coverage += y - prevY;
} else if ((size_t)cellX >= raster->width) {
/* If outside of the raster, on the right side, add to the last
* columns contributions to the next column, so that the ink level
* balances out to zero */
cell = (size_t)cellY * raster->width + (raster->width - 1);
raster->cells[cell].opposite_coverage += y - prevY;
} else {
/* If inside the raster, just draw the line */
cell = (size_t)cellY * raster->width + (size_t)cellX;
raster->cells[cell].opposite_coverage += y - prevY;
raster->cells[cell].cell_coverage += (y - prevY) * fabs(xfloor + 1.0 - (x + prevX) / 2.0);
}
}
}
#else
#define CHECK_ZEROED()\
do {\
size_t i__;\
for (i__ = 0; i__ < 100; i__++) {\
ASSERT(!raster->cells[i__].cell_coverage);\
ASSERT(!raster->cells[i__].opposite_coverage);\
}\
} while (0)
#define CHECK_CELL(X, Y, AREA, SHADOW)\
do {\
size_t i__ = (Y) * raster->width + (X);\
ASSERT(raster->cells[i__].cell_coverage == (AREA));\
ASSERT(raster->cells[i__].opposite_coverage == (SHADOW));\
raster->cells[i__].cell_coverage = 0;\
raster->cells[i__].opposite_coverage = 0;\
} while (0)
#define SUB_CELL(X, Y, AREA, SHADOW)\
do {\
size_t i__ = (Y) * raster->width + (X);\
raster->cells[i__].cell_coverage -= (AREA);\
raster->cells[i__].opposite_coverage -= (SHADOW);\
} while (0)
static RASTER *raster;
#if 0
static void
print_raster(void)
{
size_t y, x;
printf("\nOutline (area)\n");
for (y = 0; y < raster->height; y++) {
for (x = 0; x < raster->width; x++)
printf(raster->cells[y * raster->width + x].cell_coverage ? "%+.4lf " : " 0 ",
raster->cells[y * raster->width + x].cell_coverage);
printf("\n");
}
printf("\nOutline (shadow)\n");
for (y = 0; y < raster->height; y++) {
for (x = 0; x < raster->width; x++)
printf(raster->cells[y * raster->width + x].opposite_coverage ? "%+.4lf " : " 0 ",
raster->cells[y * raster->width + x].opposite_coverage);
printf("\n");
}
}
#endif
static void
draw(double x1, double y1, double x2, double y2)
{
alarm(5);
draw_linear_bezier_reference(raster, x1, y1, x2, y2);
alarm(0);
}
#undef draw_linear_bezier_reference
#define draw_linear_bezier_reference "use draw(double, double, double, double) instead"
static void
check_horizontal(void)
{
ssize_t y, x1, x2;
for (y = -2; y < 12; y++) {
for (x1 = -2; x1 < 12; x1++) {
for (x2 = -2; x2 < 12; x2++) {
draw(x1, y, x2, y);
CHECK_ZEROED();
draw(x1 + 0.25, y, x2 + 0.25, y);
CHECK_ZEROED();
draw(x1, y + 0.25, x2, y + 0.25);
CHECK_ZEROED();
draw(x1 + 0.25, y + 0.25, x2 + 0.25, y + 0.25);
CHECK_ZEROED();
}
}
}
}
static void
check_vertical(void)
{
ssize_t x, y1, y2, i, ydir;
double yhit;
for (x = -2; x < 12; x++) {
for (y1 = -2; y1 < 12; y1++) {
for (y2 = -2; y2 < 12; y2++) {
ydir = SIGNUM(y2 - y1);
draw(x, y1, x, y2);
for (i = 0; i < 10; i++) {
if (i < y1 && i < y2)
continue;
if (i >= y1 && i >= y2)
continue;
CHECK_CELL(x < 0 ? 0 : x < 10 ? x : 9,
i,
x < 0 ? (double)ydir : x < 10 ? (double)ydir : 0,
(double)ydir);
}
CHECK_ZEROED();
draw(x + 0.25, y1, x + 0.25, y2);
for (i = 0; i < 10; i++) {
if (i < y1 && i < y2)
continue;
if (i >= y1 && i >= y2)
continue;
CHECK_CELL(x < 0 ? 0 : x < 10 ? x : 9,
i,
x < 0 ? (double)ydir : x < 10 ? (double)ydir * 0.75 : 0,
(double)ydir);
}
CHECK_ZEROED();
draw(x, y1 + 0.25, x, y2 + 0.25);
for (i = 0; i < 10; i++) {
if (i < y1 + (y1 > y2) && i < y2 + (y2 > y1))
continue;
if (i >= y1 + (y1 > y2) && i >= y2 + (y2 > y1))
continue;
yhit = i == (y1 < y2 ? y1 : y2) ? 0.75 : i == (y2 > y1 ? y2 : y1) ? 0.25 : 1.0;
CHECK_CELL(x < 0 ? 0 : x < 10 ? x : 9,
i,
(x < 0 ? (double)ydir : x < 10 ? (double)ydir : 0) * yhit,
(double)ydir * yhit);
}
CHECK_ZEROED();
draw(x + 0.25, y1 + 0.25, x + 0.25, y2 + 0.25);
for (i = 0; i < 10; i++) {
if (i < y1 + (y1 > y2) && i < y2 + (y2 > y1))
continue;
if (i >= y1 + (y1 > y2) && i >= y2 + (y2 > y1))
continue;
yhit = i == (y1 < y2 ? y1 : y2) ? 0.75 : i == (y2 > y1 ? y2 : y1) ? 0.25 : 1.0;
CHECK_CELL(x < 0 ? 0 : x < 10 ? x : 9,
i,
(x < 0 ? (double)ydir : x < 10 ? (double)ydir * 0.75 : 0) * yhit,
(double)ydir * yhit);
}
CHECK_ZEROED();
}
}
}
}
static void
check_11_diagonal(ssize_t xshift, ssize_t yshift)
{
ssize_t i1, i2, i, imin, imax, idir, x, y;
for (i1 = -2; i1 < 12; i1++) {
for (i2 = -2; i2 < 12; i2++) {
imin = i1 < i2 ? i1 : i2;
imax = i1 > i2 ? i1 : i2;
idir = SIGNUM(i2 - i1);
draw(i1 + xshift, i1 + yshift, i2 + xshift, i2 + yshift);
for (i = imin; i < imax; i++) {
x = i + xshift;
y = i + yshift;
if (y < 0 || y >= 10)
continue;
if (x >= 10)
CHECK_CELL(9, y, 0, idir);
else if (x >= 0)
CHECK_CELL(x, y, 0.5 * idir, idir);
else
CHECK_CELL(0, y, idir, idir);
}
CHECK_ZEROED();
draw(i1 + xshift, i1 + yshift + 0.25, i2 + xshift, i2 + yshift + 0.25);
for (i = imin; i < imax; i++) {
x = i + xshift;
y = i + yshift;
if (0 <= y && y < 10) {
if (x >= 10)
SUB_CELL(9, y, 0, idir * 0.75);
else if (x >= 0)
SUB_CELL(x, y, idir * (0.75 - 0.75 * 0.75 / 2), idir * 0.75);
else
SUB_CELL(0, y, idir * 0.75, idir * 0.75);
}
x = i + xshift;
y = i + yshift + 1;
if (0 <= y && y < 10) {
if (x >= 10)
SUB_CELL(9, y, 0, idir * 0.25);
else if (x >= 0)
SUB_CELL(x, y, idir * 0.25 * 0.25 / 2, idir * 0.25);
else
SUB_CELL(0, y, idir * 0.25, idir * 0.25);
}
}
CHECK_ZEROED();
draw(i1 + xshift + 0.25, i1 + yshift, i2 + xshift + 0.25, i2 + yshift);
for (i = imin; i < imax; i++) {
x = i + xshift;
y = i + yshift;
if (0 <= y && y < 10) {
if (x >= 10)
SUB_CELL(9, y, 0, idir * 0.75);
else if (x >= 0)
SUB_CELL(x, y, idir * 0.75 * 0.75 / 2, idir * 0.75);
else
SUB_CELL(0, y, idir * 0.75, idir * 0.75);
}
x = i + xshift + 1;
y = i + yshift;
if (0 <= y && y < 10) {
if (x >= 10)
SUB_CELL(9, y, 0, idir * 0.25);
else if (x >= 0)
SUB_CELL(x, y, idir * (0.25 - 0.25 * 0.25 / 2), idir * 0.25);
else
SUB_CELL(0, y, idir * 0.25, idir * 0.25);
}
}
CHECK_ZEROED();
draw(i1 + xshift + 0.25, i1 + yshift + 0.25, i2 + xshift + 0.25, i2 + yshift + 0.25);
for (i = imin; i < imax; i++) {
x = i + xshift;
y = i + yshift;
if (0 <= y && y < 10) {
if (x >= 10)
SUB_CELL(9, y, 0, idir * 0.75);
else if (x >= 0)
SUB_CELL(x, y, idir * 0.75 * 0.75 / 2, idir * 0.75);
else
SUB_CELL(0, y, idir * 0.75, idir * 0.75);
}
x = i + xshift + 1;
y = i + yshift + 1;
if (0 <= y && y < 10) {
if (x >= 10)
SUB_CELL(9, y, 0, idir * 0.25);
else if (x >= 0)
SUB_CELL(x, y, idir * (0.25 - 0.25 * 0.25 / 2), idir * 0.25);
else
SUB_CELL(0, y, idir * 0.25, idir * 0.25);
}
}
CHECK_ZEROED();
}
}
}
static void
check_11_antidiagonal(ssize_t xshift, ssize_t yshift)
{
ssize_t i1, i2, i, imin, imax, ydir, x, y;
for (i1 = -2; i1 < 12; i1++) {
for (i2 = -2; i2 < 12; i2++) {
imin = i1 < i2 ? i1 : i2;
imax = i1 > i2 ? i1 : i2;
ydir = -SIGNUM(i2 - i1);
draw(i1 + xshift, i2 + yshift, i2 + xshift, i1 + yshift);
for (i = imin; i < imax; i++) {
x = i + xshift;
y = imax - i + imin + yshift - 1;
if (y < 0 || y >= 10)
continue;
if (x >= 10)
CHECK_CELL(9, y, 0, ydir);
else if (x >= 0)
CHECK_CELL(x, y, 0.5 * ydir, ydir);
else
CHECK_CELL(0, y, ydir, ydir);
}
CHECK_ZEROED();
draw(i1 + xshift, i2 + yshift + 0.25, i2 + xshift, i1 + yshift + 0.25);
for (i = imin; i < imax; i++) {
x = i + xshift;
y = imax - i + imin + yshift - 1;
if (0 <= y && y < 10) {
if (x >= 10)
SUB_CELL(9, y, 0, ydir * 0.75);
else if (x >= 0)
SUB_CELL(x, y, ydir * 0.75 * 0.75 / 2, ydir * 0.75);
else
SUB_CELL(0, y, ydir * 0.75, ydir * 0.75);
}
x = i + xshift;
y = imax - i + imin + yshift - 1 + 1;
if (0 <= y && y < 10) {
if (x >= 10)
SUB_CELL(9, y, 0, ydir * 0.25);
else if (x >= 0)
SUB_CELL(x, y, ydir * (0.25 - 0.25 * 0.25 / 2), ydir * 0.25);
else
SUB_CELL(0, y, ydir * 0.25, ydir * 0.25);
}
}
CHECK_ZEROED();
draw(i1 + xshift + 0.25, i2 + yshift, i2 + xshift + 0.25, i1 + yshift);
for (i = imin; i < imax; i++) {
x = i + xshift;
y = imax - i + imin + yshift - 1;
if (0 <= y && y < 10) {
if (x >= 10)
SUB_CELL(9, y, 0, ydir * 0.75);
else if (x >= 0)
SUB_CELL(x, y, ydir * 0.75 * 0.75 / 2, ydir * 0.75);
else
SUB_CELL(0, y, ydir * 0.75, ydir * 0.75);
}
x = i + xshift + 1;
y = imax - i + imin + yshift - 1;
if (0 <= y && y < 10) {
if (x >= 10)
SUB_CELL(9, y, 0, ydir * 0.25);
else if (x >= 0)
SUB_CELL(x, y, ydir * (0.25 - 0.25 * 0.25 / 2), ydir * 0.25);
else
SUB_CELL(0, y, ydir * 0.25, ydir * 0.25);
}
}
CHECK_ZEROED();
draw(i1 + xshift + 0.25, i2 + yshift + 0.25, i2 + xshift + 0.25, i1 + yshift + 0.25);
for (i = imin; i < imax; i++) {
x = i + xshift;
y = imax - i + imin + yshift - 1;
if (0 <= y && y < 10) {
if (x >= 10)
SUB_CELL(9, y, 0, ydir * 0.5);
else if (x >= 0)
SUB_CELL(x, y, ydir / 8.0, ydir * 0.5);
else
SUB_CELL(0, y, ydir * 0.5, ydir * 0.5);
}
x = i + xshift;
y = imax - i + imin + yshift - 1 + 1;
if (0 <= y && y < 10) {
if (x >= 10)
SUB_CELL(9, y, 0, ydir * 0.25);
else if (x >= 0)
SUB_CELL(x, y, ydir * (2.5 / 16.0), ydir * 0.25);
else
SUB_CELL(0, y, ydir * 0.25, ydir * 0.25);
}
x = i + xshift + 1;
y = imax - i + imin + yshift - 1;
if (0 <= y && y < 10) {
if (x >= 10)
SUB_CELL(9, y, 0, ydir * 0.25);
else if (x >= 0)
SUB_CELL(x, y, ydir * (3.5 / 16.0), ydir * 0.25);
else
SUB_CELL(0, y, ydir * 0.25, ydir * 0.25);
}
}
CHECK_ZEROED();
}
}
}
static void
try_random_line(void)
{
double x1 = (double)rand() / (double)RAND_MAX;
double y1 = (double)rand() / (double)RAND_MAX;
double x2 = (double)rand() / (double)RAND_MAX;
double y2 = (double)rand() / (double)RAND_MAX;
draw(x1, y1, x2, y2);
}
int
main(void)
{
size_t i;
raster = rtgrpblib_create_raster(10, 10);
ASSERT(raster);
srand((unsigned)(uintptr_t)raster);
check_horizontal();
check_vertical();
check_11_diagonal(0, 0);
check_11_diagonal(0, 2);
check_11_diagonal(0, -2);
check_11_diagonal(2, 0);
check_11_diagonal(2, 2);
check_11_diagonal(2, -2);
check_11_diagonal(-2, 0);
check_11_diagonal(-2, 2);
check_11_diagonal(-2, -2);
check_11_antidiagonal(0, 0);
check_11_antidiagonal(0, 2);
check_11_antidiagonal(0, -2);
check_11_antidiagonal(2, 0);
check_11_antidiagonal(2, 2);
check_11_antidiagonal(2, -2);
check_11_antidiagonal(-2, 0);
check_11_antidiagonal(-2, 2);
check_11_antidiagonal(-2, -2);
for (i = 0; i < 100000UL; i++)
try_random_line();
rtgrpblib_reset_raster(raster, 10, 10);
free(raster);
return 0;
}
#endif
