7 #define IMTRUNC(x) ((int)((x)*16))
9 #define coarse(x) ((x)/16)
10 #define fine(x) ((x)%16)
12 /*#define DEBUG_POLY*/
20 typedef i_img_dim pcord;
33 int updown; /* -1 means down, 0 vertical, 1 up */
42 int *line; /* temporary buffer for scanline */
43 i_img_dim linelen; /* length of scanline */
48 p_compy(const p_point *p1, const p_point *p2) {
49 if (p1->y > p2->y) return 1;
50 if (p1->y < p2->y) return -1;
56 p_compx(const p_slice *p1, const p_slice *p2) {
57 if (p1->x > p2->x) return 1;
58 if (p1->x < p2->x) return -1;
62 /* Change this to int? and round right goddamn it! */
66 p_eval_aty(p_line *l, pcord y) {
69 if (t) return ( (y-l->y1)*l->x2 + (l->y2-y)*l->x1 )/t;
70 return (l->x1+l->x2)/2.0;
75 p_eval_atx(p_line *l, pcord x) {
78 if (t) return ( (x-l->x1)*l->y2 + (l->x2-x)*l->y1 )/t;
79 return (l->y1+l->y2)/2.0;
84 line_set_new(const double *x, const double *y, int l) {
86 p_line *lset = mymalloc(sizeof(p_line) * l);
90 lset[i].x1 = IMTRUNC(x[i]);
91 lset[i].y1 = IMTRUNC(y[i]);
92 lset[i].x2 = IMTRUNC(x[(i+1)%l]);
93 lset[i].y2 = IMTRUNC(y[(i+1)%l]);
94 lset[i].miny=i_min(lset[i].y1,lset[i].y2);
95 lset[i].maxy=i_max(lset[i].y1,lset[i].y2);
96 lset[i].minx=i_min(lset[i].x1,lset[i].x2);
97 lset[i].maxx=i_max(lset[i].x1,lset[i].x2);
104 point_set_new(const double *x, const double *y, int l) {
106 p_point *pset = mymalloc(sizeof(p_point) * l);
110 pset[i].x=IMTRUNC(x[i]);
111 pset[i].y=IMTRUNC(y[i]);
118 ss_scanline_reset(ss_scanline *ss) {
119 memset(ss->line, 0, sizeof(int) * ss->linelen);
124 ss_scanline_init(ss_scanline *ss, i_img_dim linelen, int linepairs) {
125 ss->line = mymalloc( sizeof(int) * linelen );
126 ss->linelen = linelen;
127 ss_scanline_reset(ss);
132 ss_scanline_exorcise(ss_scanline *ss) {
139 /* returns the number of matches */
143 lines_in_interval(p_line *lset, int l, p_slice *tllist, pcord minc, pcord maxc) {
147 if (lset[k].maxy > minc && lset[k].miny < maxc) {
148 if (lset[k].miny == lset[k].maxy) {
149 POLY_DEB( printf(" HORIZONTAL - skipped\n") );
151 tllist[count].x=p_eval_aty(&lset[k],(minc+maxc)/2.0 );
160 /* marks the up variable for all lines in a slice */
164 mark_updown_slices(p_line *lset, p_slice *tllist, int count) {
167 for(k=0; k<count; k+=2) {
168 l = lset + tllist[k].n;
170 if (l->y1 == l->y2) {
171 mm_log((1, "mark_updown_slices: horizontal line being marked: internal error!\n"));
175 l->updown = (l->x1 == l->x2) ?
179 (l->y1 > l->y2) ? -1 : 1
181 (l->y1 > l->y2) ? 1 : -1;
183 POLY_DEB( printf("marking left line %d as %s(%d)\n", l->n,
184 l->updown ? l->updown == 1 ? "up" : "down" : "vert", l->updown, l->updown)
188 mm_log((1, "Invalid polygon spec, odd number of line crossings.\n"));
192 r = lset + tllist[k+1].n;
193 if (r->y1 == r->y2) {
194 mm_log((1, "mark_updown_slices: horizontal line being marked: internal error!\n"));
198 r->updown = (r->x1 == r->x2) ?
202 (r->y1 > r->y2) ? -1 : 1
204 (r->y1 > r->y2) ? 1 : -1;
206 POLY_DEB( printf("marking right line %d as %s(%d)\n", r->n,
207 r->updown ? r->updown == 1 ? "up" : "down" : "vert", r->updown, r->updown)
217 if (in>255) { return 255; }
218 else if (in>0) return in;
222 typedef void (*scanline_flusher)(i_img *im, ss_scanline *ss, int y, void *ctx);
224 /* This function must be modified later to do proper blending */
227 scanline_flush(i_img *im, ss_scanline *ss, int y, void *ctx) {
230 i_color *val = (i_color *)ctx;
231 POLY_DEB( printf("Flushing line %d\n", y) );
232 for(x=0; x<im->xsize; x++) {
233 tv = saturate(ss->line[x]);
234 i_gpix(im, x, y, &t);
235 for(ch=0; ch<im->channels; ch++)
236 t.channel[ch] = tv/255.0 * val->channel[ch] + (1.0-tv/255.0) * t.channel[ch];
237 i_ppix(im, x, y, &t);
245 trap_square(pcord xlen, pcord ylen, double xl, double yl) {
246 POLY_DEB( printf("trap_square: %d %d %.2f %.2f\n", xlen, ylen, xl, yl) );
247 return xlen*ylen-(xl*yl)/2.0;
252 pixel_coverage calculates the 'left side' pixel coverage of a pixel that is
253 within the min/max ranges. The shape always corresponds to a square with some
254 sort of a triangle cut from it (which can also yield a triangle).
260 pixel_coverage(p_line *line, pcord minx, pcord maxx, pcord miny, pcord maxy) {
261 double lycross, rycross;
266 printf(" pixel_coverage(..., minx %g, maxx%g, miny %g, maxy %g)\n",
267 minx/16.0, maxx/16.0, miny/16.0, maxy/16.0)
273 lycross = p_eval_atx(line, minx);
274 rycross = p_eval_atx(line, maxx);
275 l = lycross <= maxy && lycross >= miny; /* true if it enters through left side */
276 r = rycross <= maxy && rycross >= miny; /* true if it enters through left side */
279 printf(" %4s(%+d): ", line->updown ? line->updown == 1 ? "up" : "down" : "vert", line->updown);
280 printf(" (%2d,%2d) [%3d-%3d, %3d-%3d] lycross=%.2f rycross=%.2f", coarse(minx), coarse(miny), minx, maxx, miny, maxy, lycross, rycross);
281 printf(" l=%d r=%d\n", l, r)
285 return line->updown == 1 ?
286 (double)(maxx-minx) * (2.0*maxy-lycross-rycross)/2.0 /* up case */
288 (double)(maxx-minx) * (lycross+rycross-2*miny)/2.0; /* down case */
290 if (!l && !r) return (maxy-miny)*(maxx*2-p_eval_aty(line, miny)-p_eval_aty(line, maxy))/2.0;
293 return line->updown == 1 ?
294 trap_square(maxx-minx, maxy-miny, p_eval_aty(line, miny)-minx, p_eval_atx(line, minx)-miny) :
295 trap_square(maxx-minx, maxy-miny, p_eval_aty(line, maxy)-minx, maxy-p_eval_atx(line, minx));
299 int r = line->updown == 1 ?
300 (maxx-p_eval_aty(line, maxy))*(maxy-p_eval_atx(line, maxx))/2.0 :
301 (maxx-p_eval_aty(line, miny))*(p_eval_atx(line, maxx)-miny)/2.0;
305 return 0; /* silence compiler warning */
313 handle the scanline slice in three steps
315 1. Where only the left edge is inside a pixel
316 2a. Where both left and right edge are inside a pixel
317 2b. Where neither left or right edge are inside a pixel
318 3. Where only the right edge is inside a pixel
323 render_slice_scanline(ss_scanline *ss, int y, p_line *l, p_line *r, pcord miny, pcord maxy) {
325 pcord lminx, lmaxx; /* left line min/max within y bounds in fine coords */
326 pcord rminx, rmaxx; /* right line min/max within y bounds in fine coords */
327 i_img_dim cpix; /* x-coordinate of current pixel */
328 int thin; /* boolean for thin/thick segment */
329 i_img_dim startpix; /* temporary variable for "start of this interval" */
330 i_img_dim stoppix; /* temporary variable for "end of this interval" */
332 /* Find the y bounds of scanline_slice */
336 printf("render_slice_scanline(..., y=%d)\n");
337 printf(" left n=%d p1(%.2g, %.2g) p2(%.2g,%.2g) min(%.2g, %.2g) max(%.2g,%.2g) updown(%d)\n",
338 l->n, l->x1/16.0, l->y1/16.0, l->x2/16.0, l->y2/16.0,
339 l->minx/16.0, l->miny/16.0, l->maxx/16.0, l->maxy/16.0,
341 printf(" right n=%d p1(%.2g, %.2g) p2(%.2g,%.2g) min(%.2g, %.2g) max(%.2g,%.2g) updown(%d)\n",
342 r->n, r->x1/16.0, r->y1/16.0, r->x2/16.0, r->y2/16.0,
343 r->minx/16.0, r->miny/16.0, r->maxx/16.0, r->maxy/16.0,
347 lminx = i_min( p_eval_aty(l, maxy), p_eval_aty(l, miny) );
348 lmaxx = i_max( p_eval_aty(l, maxy), p_eval_aty(l, miny) );
350 rminx = i_min( p_eval_aty(r, maxy), p_eval_aty(r, miny) );
351 rmaxx = i_max( p_eval_aty(r, maxy), p_eval_aty(r, miny) );
353 thin = coarse(lmaxx) >= coarse(rminx);
355 startpix = i_max( coarse(lminx), 0 );
356 stoppix = i_min( coarse(rmaxx-1), ss->linelen-1 );
358 POLY_DEB( printf(" miny=%g maxy=%g\n", miny/16.0, maxy/16.0) );
360 for(cpix=startpix; cpix<=stoppix; cpix++) {
361 int lt = coarse(lmaxx-1) >= cpix;
362 int rt = coarse(rminx) <= cpix;
366 POLY_DEB( printf(" (%d,%d) lt=%d rt=%d\n", cpix, y, lt, rt) );
368 A = lt ? pixel_coverage(l, cpix*16, cpix*16+16, miny, maxy) : 0;
369 B = lt ? 0 : 16*(maxy-miny);
370 C = rt ? pixel_coverage(r, cpix*16, cpix*16+16, miny, maxy) : 0;
372 POLY_DEB( printf(" A=%d B=%d C=%d\n", A, B, C) );
374 ss->line[cpix] += A+B-C;
377 POLY_DEB( printf("end render_slice_scanline()\n") );
380 /* Antialiasing polygon algorithm
382 1. only nice polygons - no crossovers
383 2. 1/16 pixel resolution
384 3. full antialiasing ( complete spectrum of blends )
385 4. uses hardly any memory
386 5. no subsampling phase
390 1. Split into vertical intervals.
391 2. handle each interval
393 For each interval we must:
394 1. find which lines are in it
395 2. order the lines from in increasing x order.
396 since we are assuming no crossovers it is sufficent
397 to check a single point on each line.
403 1. Interval: A vertical segment in which no lines cross nor end.
404 2. Scanline: A physical line, contains 16 subpixels in the horizontal direction
405 3. Slice: A start stop line pair.
411 i_poly_aa_low(i_img *im, int l, const double *x, const double *y, void *ctx, scanline_flusher flusher) {
412 int i ,k; /* Index variables */
413 i_img_dim clc; /* Lines inside current interval */
414 /* initialize to avoid compiler warnings */
416 i_img_dim cscl = 0; /* Current scanline */
418 ss_scanline templine; /* scanline accumulator */
419 p_point *pset; /* List of points in polygon */
420 p_line *lset; /* List of lines in polygon */
421 p_slice *tllist; /* List of slices */
423 mm_log((1, "i_poly_aa(im %p, l %d, x %p, y %p, ctx %p, flusher %p)\n", im, l, x, y, ctx, flusher));
426 mm_log((2, "(%.2f, %.2f)\n", x[i], y[i]));
432 setbuf(stdout, NULL);
435 tllist = mymalloc(sizeof(p_slice)*l);
437 ss_scanline_init(&templine, im->xsize, l);
439 pset = point_set_new(x, y, l);
440 lset = line_set_new(x, y, l);
443 qsort(pset, l, sizeof(p_point), (int(*)(const void *,const void *))p_compy);
447 printf("%d [ %d ] (%d , %d) -> (%d , %d) yspan ( %d , %d )\n",
448 i, lset[i].n, lset[i].x1, lset[i].y1, lset[i].x2, lset[i].y2, lset[i].miny, lset[i].maxy);
450 printf("MAIN LOOP\n\n");
454 /* loop on intervals */
455 for(i=0; i<l-1; i++) {
456 i_img_dim startscan = i_max( coarse(pset[i].y), 0);
457 i_img_dim stopscan = i_min( coarse(pset[i+1].y+15), im->ysize);
458 pcord miny, maxy; /* y bounds in fine coordinates */
460 POLY_DEB( pcord cc = (pset[i].y + pset[i+1].y)/2 );
463 printf("current slice is %d: %d to %d ( cpoint %d ) scanlines %d to %d\n",
464 i, pset[i].y, pset[i+1].y, cc, startscan, stopscan)
467 if (pset[i].y == pset[i+1].y) {
468 POLY_DEB( printf("current slice thickness = 0 => skipping\n") );
472 clc = lines_in_interval(lset, l, tllist, pset[i].y, pset[i+1].y);
473 qsort(tllist, clc, sizeof(p_slice), (int(*)(const void *,const void *))p_compx);
475 mark_updown_slices(lset, tllist, clc);
479 printf("Interval contains %d lines\n", clc);
480 for(k=0; k<clc; k++) {
481 int lno = tllist[k].n;
482 p_line *ln = lset+lno;
483 printf("%d: line #%2d: (%2d, %2d)->(%2d, %2d) (%2d/%2d, %2d/%2d) -> (%2d/%2d, %2d/%2d) alignment=%s\n",
484 k, lno, ln->x1, ln->y1, ln->x2, ln->y2,
485 coarse(ln->x1), fine(ln->x1),
486 coarse(ln->y1), fine(ln->y1),
487 coarse(ln->x2), fine(ln->x2),
488 coarse(ln->y2), fine(ln->y2),
489 ln->updown == 0 ? "vert" : ln->updown == 1 ? "up" : "down");
493 maxy = im->ysize * 16;
495 for (k = 0; k < clc; ++k) {
496 p_line const * line = lset + tllist[k].n;
497 if (line->miny > miny)
499 if (line->maxy < maxy)
501 POLY_DEB( printf(" line miny %g maxy %g\n", line->miny/16.0, line->maxy/16.0) );
503 POLY_DEB( printf("miny %g maxy %g\n", miny/16.0, maxy/16.0) );
505 for(cscl=startscan; cscl<stopscan; cscl++) {
506 pcord scan_miny = i_max(miny, cscl * 16);
507 pcord scan_maxy = i_min(maxy, (cscl + 1 ) * 16);
509 tempy = i_min(cscl*16+16, pset[i+1].y);
510 POLY_DEB( printf("evaluating scan line %d \n", cscl) );
511 for(k=0; k<clc-1; k+=2) {
512 POLY_DEB( printf("evaluating slice %d\n", k) );
513 render_slice_scanline(&templine, cscl, lset+tllist[k].n, lset+tllist[k+1].n, scan_miny, scan_maxy);
515 if (16*coarse(tempy) == tempy) {
516 POLY_DEB( printf("flushing scan line %d\n", cscl) );
517 flusher(im, &templine, cscl, ctx);
518 ss_scanline_reset(&templine);
522 scanline_flush(im, &templine, cscl, val);
523 ss_scanline_reset(&templine);
529 if (16*coarse(tempy) != tempy)
530 flusher(im, &templine, cscl-1, ctx);
532 ss_scanline_exorcise(&templine);
540 i_poly_aa(i_img *im, int l, const double *x, const double *y, const i_color *val) {
542 i_poly_aa_low(im, l, x, y, &c, scanline_flush);
546 struct poly_render_state {
549 unsigned char *cover;
553 scanline_flush_render(i_img *im, ss_scanline *ss, int y, void *ctx) {
555 i_img_dim left, right;
556 struct poly_render_state *state = (struct poly_render_state *)ctx;
559 while (left < im->xsize && ss->line[left] <= 0)
561 if (left < im->xsize) {
563 /* since going from the left found something, moving from the
565 while (/* right > left && */ ss->line[right-1] <= 0)
568 /* convert to the format the render interface wants */
569 for (x = left; x < right; ++x) {
570 state->cover[x-left] = saturate(ss->line[x]);
572 i_render_fill(&state->render, left, y, right-left, state->cover,
578 i_poly_aa_cfill(i_img *im, int l, const double *x, const double *y,
580 struct poly_render_state ctx;
582 i_render_init(&ctx.render, im, im->xsize);
584 ctx.cover = mymalloc(im->xsize);
585 i_poly_aa_low(im, l, x, y, &ctx, scanline_flush_render);
587 i_render_done(&ctx.render);