ref: a8f8de1cdeec7f9bee287c137b576e0249e8df82
dir: /sys/src/libmemdraw/ellipse.c/
#include <u.h>
#include <libc.h>
#include <draw.h>
#include <memdraw.h>
#include <memlayer.h>
/*
* ellipse(dst, c, a, b, t, src, sp)
* draws an ellipse centered at c with semiaxes a,b>=0
* and semithickness t>=0, or filled if t<0. point sp
* in src maps to c in dst
*
* very thick skinny ellipses are brushed with circles (slow)
* others are approximated by filling between 2 ellipses
* criterion for very thick when b<a: t/b > 0.5*x/(1-x)
* where x = b/a
*/
typedef struct Param Param;
typedef struct State State;
static void bellipse(int, State*, Param*);
static void erect(int, int, int, int, Param*);
static void eline(int, int, int, int, Param*);
struct Param {
Memimage *dst;
Memimage *src;
Point c;
int t;
Point sp;
Memimage *disc;
int op;
};
/*
* denote residual error by e(x,y) = b^2*x^2 + a^2*y^2 - a^2*b^2
* e(x,y) = 0 on ellipse, e(x,y) < 0 inside, e(x,y) > 0 outside
*/
struct State {
int a;
int x;
vlong a2; /* a^2 */
vlong b2; /* b^2 */
vlong b2x; /* b^2 * x */
vlong a2y; /* a^2 * y */
vlong c1;
vlong c2; /* test criteria */
vlong ee; /* ee = e(x+1/2,y-1/2) - (a^2+b^2)/4 */
vlong dxe;
vlong dye;
vlong d2xe;
vlong d2ye;
};
static
State*
newstate(State *s, int a, int b)
{
s->x = 0;
s->a = a;
s->a2 = (vlong)(a*a);
s->b2 = (vlong)(b*b);
s->b2x = (vlong)0;
s->a2y = s->a2*(vlong)b;
s->c1 = -((s->a2>>2) + (vlong)(a&1) + s->b2);
s->c2 = -((s->b2>>2) + (vlong)(b&1));
s->ee = -s->a2y;
s->dxe = (vlong)0;
s->dye = s->ee<<1;
s->d2xe = s->b2<<1;
s->d2ye = s->a2<<1;
return s;
}
/*
* return x coord of rightmost pixel on next scan line
*/
static
int
step(State *s)
{
while(s->x < s->a) {
if(s->ee+s->b2x <= s->c1 || /* e(x+1,y-1/2) <= 0 */
s->ee+s->a2y <= s->c2) { /* e(x+1/2,y) <= 0 (rare) */
s->dxe += s->d2xe;
s->ee += s->dxe;
s->b2x += s->b2;
s->x++;
continue;
}
s->dye += s->d2ye;
s->ee += s->dye;
s->a2y -= s->a2;
if(s->ee-s->a2y <= s->c2) { /* e(x+1/2,y-1) <= 0 */
s->dxe += s->d2xe;
s->ee += s->dxe;
s->b2x += s->b2;
return s->x++;
}
break;
}
return s->x;
}
void
memellipse(Memimage *dst, Point c, int a, int b, int t, Memimage *src, Point sp, int op)
{
State in, out;
int y, inb, inx, outx, u;
Param p;
if(a < 0)
a = -a;
if(b < 0)
b = -b;
p.dst = dst;
p.src = src;
p.c = c;
p.t = t;
p.sp = subpt(sp, c);
p.disc = nil;
p.op = op;
u = (t<<1)*(a-b);
if(b<a && u>b*b || a<b && -u>a*a) {
/* if(b<a&&(t<<1)>b*b/a || a<b&&(t<<1)>a*a/b) # very thick */
bellipse(b, newstate(&in, a, b), &p);
return;
}
if(t < 0) {
inb = -1;
newstate(&out, a, y = b);
} else {
inb = b - t;
newstate(&out, a+t, y = b+t);
}
if(t > 0)
newstate(&in, a-t, inb);
inx = 0;
for( ; y>=0; y--) {
outx = step(&out);
if(y > inb) {
erect(-outx, y, outx, y, &p);
if(y != 0)
erect(-outx, -y, outx, -y, &p);
continue;
}
if(t > 0) {
inx = step(&in);
if(y == inb)
inx = 0;
} else if(inx > outx)
inx = outx;
erect(inx, y, outx, y, &p);
if(y != 0)
erect(inx, -y, outx, -y, &p);
erect(-outx, y, -inx, y, &p);
if(y != 0)
erect(-outx, -y, -inx, -y, &p);
inx = outx + 1;
}
}
static Point p00 = {0, 0};
/*
* a brushed ellipse
*/
static
void
bellipse(int y, State *s, Param *p)
{
int t, ox, oy, x, nx;
t = p->t;
p->disc = allocmemimage(Rect(-t,-t,t+1,t+1), GREY1);
if(p->disc == nil)
return;
memfillcolor(p->disc, DTransparent);
memellipse(p->disc, p00, t, t, -1, memopaque, p00, p->op);
oy = y;
ox = 0;
nx = x = step(s);
do {
while(nx==x && y-->0)
nx = step(s);
y++;
eline(-x,-oy,-ox, -y, p);
eline(ox,-oy, x, -y, p);
eline(-x, y,-ox, oy, p);
eline(ox, y, x, oy, p);
ox = x+1;
x = nx;
y--;
oy = y;
} while(oy > 0);
}
/*
* a rectangle with closed (not half-open) coordinates expressed
* relative to the center of the ellipse
*/
static
void
erect(int x0, int y0, int x1, int y1, Param *p)
{
Rectangle r;
/* print("R %d,%d %d,%d\n", x0, y0, x1, y1); /**/
r = Rect(p->c.x+x0, p->c.y+y0, p->c.x+x1+1, p->c.y+y1+1);
memdraw(p->dst, r, p->src, addpt(p->sp, r.min), memopaque, p00, p->op);
}
/*
* a brushed point similarly specified
*/
static
void
epoint(int x, int y, Param *p)
{
Point p0;
Rectangle r;
/* print("P%d %d,%d\n", p->t, x, y); /**/
p0 = Pt(p->c.x+x, p->c.y+y);
r = Rpt(addpt(p0, p->disc->r.min), addpt(p0, p->disc->r.max));
memdraw(p->dst, r, p->src, addpt(p->sp, r.min), p->disc, p->disc->r.min, p->op);
}
/*
* a brushed horizontal or vertical line similarly specified
*/
static
void
eline(int x0, int y0, int x1, int y1, Param *p)
{
/* print("L%d %d,%d %d,%d\n", p->t, x0, y0, x1, y1); /**/
if(x1 > x0+1)
erect(x0+1, y0-p->t, x1-1, y1+p->t, p);
else if(y1 > y0+1)
erect(x0-p->t, y0+1, x1+p->t, y1-1, p);
epoint(x0, y0, p);
if(x1-x0 || y1-y0)
epoint(x1, y1, p);
}