3 * COPYRIGHT: Written by John Cunningham Bowler, 2015.
4 * To the extent possible under law, the author has waived all copyright and
5 * related or neighboring rights to this work. This work is published from:
8 * Generate a PNG with an alpha channel, correctly.
10 * This is a test case generator; the resultant PNG files are only of interest
11 * to those of us who care about whether the edges of circles are green, red,
14 * The program generates an RGB+Alpha PNG of a given size containing the given
15 * shapes on a transparent background:
17 * genpng width height { shape }
18 * shape ::= color width shape x1 y1 x2 y2
22 * black white red green yellow blue brown purple pink orange gray cyan
24 * The point is to have colors that are linguistically meaningful plus that old
25 * bugbear of the department store dress murders, Cyan, the only color we argue
32 * line: a straight line
34 * Each shape is followed by four numbers, these are two points in the output
35 * coordinate space (as real numbers) which describe the circle, square, or
36 * line. The shape is filled if it is preceded by 'filled' (not valid for
37 * 'line') or is drawn with a line, in which case the width of the line must
40 * The whole set of information can be repeated as many times as desired:
42 * shape ::= color width shape x1 y1 x2 y2
44 * color ::= black|white|red|green|yellow|blue
45 * color ::= brown|purple|pink|orange|gray|cyan
48 * shape ::= circle|square|line
54 * The output PNG is generated by down-sampling a 4x supersampled image using
55 * a bi-cubic filter. The bi-cubic has a 2 (output) pixel width, so an 8x8
56 * array of super-sampled points contribute to each output pixel. The value of
57 * a super-sampled point is found using an unfiltered, aliased, infinite
58 * precision image: Each shape from the last to the first is checked to see if
59 * the point is in the drawn area and, if it is, the color of the point is the
60 * color of the shape and the alpha is 1, if not the previous shape is checked.
62 * This is an aliased algorithm because no filtering is done; a point is either
63 * inside or outside each shape and 'close' points do not contribute to the
64 * sample. The down-sampling is relied on to correct the error of not using
67 * The line end-caps are 'flat'; they go through the points. The square line
68 * joins are mitres; the outside of the lines are continued to the point of
77 /* Normally use <png.h> here to get the installed libpng, but this is done to
78 * ensure the code picks up the local libpng implementation:
80 #include "../../png.h"
82 #if defined(PNG_SIMPLIFIED_WRITE_SUPPORTED) && defined(PNG_STDIO_SUPPORTED)
84 static const struct color
91 /* color ::= black|white|red|green|yellow|blue
92 * color ::= brown|purple|pink|orange|gray|cyan
99 { "yellow", 1, 1, 0 },
101 { "brown", .5, .125, 0 },
102 { "purple", 1, 0, 1 },
103 { "pink", 1, .5, .5 },
104 { "orange", 1, .5, 0 },
105 { "gray", 0, .5, .5 },
108 #define color_count ((sizeof colors)/(sizeof colors[0]))
110 static const struct color
*
111 color_of(const char *arg
)
113 int icolor
= color_count
;
115 while (--icolor
>= 0)
117 if (strcmp(colors
[icolor
].name
, arg
) == 0)
118 return colors
+icolor
;
121 fprintf(stderr
, "genpng: invalid color %s\n", arg
);
126 width_of(const char *arg
)
128 if (strcmp(arg
, "filled") == 0)
134 double w
= strtod(arg
, &ep
);
136 if (ep
!= NULL
&& *ep
== 0 && w
> 0)
140 fprintf(stderr
, "genpng: invalid line width %s\n", arg
);
145 coordinate_of(const char *arg
)
148 double w
= strtod(arg
, &ep
);
150 if (ep
!= NULL
&& *ep
== 0)
153 fprintf(stderr
, "genpng: invalid coordinate value %s\n", arg
);
157 struct arg
; /* forward declaration */
159 typedef int (*shape_fn_ptr
)(const struct arg
*arg
, double x
, double y
);
160 /* A function to determine if (x,y) is inside the shape.
162 * There are two implementations:
164 * inside_fn: returns true if the point is inside
166 * -1: the point is outside the shape by more than the filter width (2)
167 * 0: the point may be inside the shape
168 * +1: the point is inside the shape by more than the filter width
175 const struct color
*color
;
176 shape_fn_ptr inside_fn
;
177 shape_fn_ptr check_fn
;
178 double width
; /* line width, 0 for 'filled' */
179 double x1
, y1
, x2
, y2
;
182 /* IMPLEMENTATION NOTE:
184 * We want the contribution of each shape to the sample corresponding to each
185 * pixel. This could be obtained by super sampling the image to infinite
186 * dimensions, finding each point within the shape and assigning that a value
187 * '1' while leaving every point outside the shape with value '0' then
188 * downsampling to the image size with sinc; computationally very expensive.
190 * Approximations are as follows:
192 * 1) If the pixel coordinate is within the shape assume the sample has the
193 * shape color and is opaque, else assume there is no contribution from
196 * This is the equivalent of aliased rendering or resampling an image with
197 * a block filter. The maximum error in the calculated alpha (which will
198 * always be 0 or 1) is 0.5.
200 * 2) If the shape is within a square of size 1x1 centered on the pixel assume
201 * that the shape obscures an amount of the pixel equal to its area within
204 * This is the equivalent of 'pixel coverage' alpha calculation or resampling
205 * an image with a bi-linear filter. The maximum error is over 0.2, but the
206 * results are often acceptable.
208 * This can be approximated by applying (1) to a super-sampled image then
209 * downsampling with a bi-linear filter. The error in the super-sampled
210 * image is 0.5 per sample, but the resampling reduces this.
212 * 3) Use a better filter with a super-sampled image; in the limit this is the
215 * 4) Do the geometric calculation; a bivariate definite integral across the
216 * shape, unfortunately this means evaluating Si(x), the integral of sinc(x),
217 * which is still a lot of math.
219 * This code uses approach (3) with a bi-cubic filter and 8x super-sampling
220 * and method (1) for the super-samples. This means that the sample is either
221 * 0 or 1, depending on whether the sub-pixel is within or outside the shape.
222 * The bi-cubic weights are also fixed and the 16 required weights are
223 * pre-computed here (note that the 'scale' setting will need to be changed if
224 * 'super' is increased).
226 * The code also calculates a sum to the edge of the filter. This is not
227 * currently used by could be used to optimize the calculation.
233 if (x
<= 1) return (1.5*x
- 2.5)*x
*x
+ 1;
234 if (x
< 2) return (((2.5 - 0.5*x
)*x
- 4)*x
+ 2);
240 while (x
< 2*super
) {
241 s
= s
+ bicubic(x
/super
);
248 b
= bicubic(x
/super
);
251 print
" /*", x
, "*/ { ", b
, ", ", s
, " }";
257 if (x
< 2*super
) print
","
263 #define BICUBIC1(x) /* |x| <= 1 */ ((1.5*(x)* - 2.5)*(x)*(x) + 1)
264 #define BICUBIC2(x) /* 1 < |x| < 2 */ (((2.5 - 0.5*(x))*(x) - 4)*(x) + 2)
265 #define FILTER_WEIGHT 9 /* Twice the first sum below */
266 #define FILTER_WIDTH 2 /* Actually half the width; -2..+2 */
267 #define FILTER_STEPS 8 /* steps per filter unit */
271 /* These numbers are exact; the weight for the filter is 1/9, but this
272 * would make the numbers inexact, so it is not included here.
275 /* 0*/ { 1.0000000000, 4.5000000000 },
276 /* 1*/ { .9638671875, 3.5000000000 },
277 /* 2*/ { .8671875000, 2.5361328125 },
278 /* 3*/ { .7275390625, 1.6689453125 },
279 /* 4*/ { .5625000000, .9414062500 },
280 /* 5*/ { .3896484375, .3789062500 },
281 /* 6*/ { .2265625000, -.0107421875 },
282 /* 7*/ { .0908203125, -.2373046875 },
283 /* 8*/ { 0, -.3281250000 },
284 /* 9*/ { -.0478515625, -.3281250000 },
285 /*10*/ { -.0703125000, -.2802734375 },
286 /*11*/ { -.0732421875, -.2099609375 },
287 /*12*/ { -.0625000000, -.1367187500 },
288 /*13*/ { -.0439453125, -.0742187500 },
289 /*14*/ { -.0234375000, -.0302734375 },
290 /*15*/ { -.0068359375, -.0068359375 }
294 alpha_calc(const struct arg
*arg
, double x
, double y
)
296 /* For [x-2..x+2],[y-2,y+2] calculate the weighted bicubic given a function
297 * which tells us whether a point is inside or outside the shape. First
298 * check if we need to do this at all:
300 switch (arg
->check_fn(arg
, x
, y
))
303 return 0; /* all samples outside the shape */
306 return 1; /* all samples inside the shape */
313 # define FILTER_D (FILTER_WIDTH*FILTER_STEPS-1)
314 for (dy
=-FILTER_D
; dy
<=FILTER_D
; ++dy
)
316 double wy
= bicubic
[abs(dy
)][0];
323 for (dx
=-FILTER_D
; dx
<=FILTER_D
; ++dx
)
325 double wx
= bicubic
[abs(dx
)][0];
327 if (wx
!= 0 && arg
->inside_fn(arg
, x
+dx
/16, y
+dy
/16))
331 alpha
+= wy
* alphay
;
335 /* This needs to be weighted for each dimension: */
336 return alpha
/ (FILTER_WEIGHT
*FILTER_WEIGHT
);
341 /* These are the shape functions. */
343 * { inside_square_filled, check_square_filled },
344 * { inside_square, check_square }
347 square_check(double x
, double y
, double x1
, double y1
, double x2
, double y2
)
348 /* Is x,y inside the square (x1,y1)..(x2,y2)? */
350 /* Do a modified Cohen-Sutherland on one point, bit patterns that indicate
353 * x<x1 | x<y1 | x<x2 | x<y2
354 * 0 x 0 x To the right
355 * 1 x 1 x To the left
359 * So 'inside' is (x<x1) != (x<x2) && (y<y1) != (y<y2);
361 return ((x
<x1
) ^ (x
<x2
)) & ((y
<y1
) ^ (y
<y2
));
365 inside_square_filled(const struct arg
*arg
, double x
, double y
)
367 return square_check(x
, y
, arg
->x1
, arg
->y1
, arg
->x2
, arg
->y2
);
371 square_check_line(const struct arg
*arg
, double x
, double y
, double w
)
372 /* Check for a point being inside the boundaries implied by the given arg
373 * and assuming a width 2*w each side of the boundaries. This returns the
374 * 'check' INSIDE/OUTSIDE/0 result but note the semantics:
382 * And '0' means within the line boundaries.
385 double cx
= (arg
->x1
+arg
->x2
)/2;
386 double wx
= fabs(arg
->x1
-arg
->x2
)/2;
387 double cy
= (arg
->y1
+arg
->y2
)/2;
388 double wy
= fabs(arg
->y1
-arg
->y2
)/2;
390 if (square_check(x
, y
, cx
-wx
-w
, cy
-wy
-w
, cx
+wx
+w
, cy
+wy
+w
))
392 /* Inside, but maybe too far; check for the redundant case where
397 if (wx
> 0 && wy
> 0 && square_check(x
, y
, cx
-wx
, cy
-wy
, cx
+wx
, cy
+wy
))
398 return INSIDE
; /* between (inside) the boundary lines. */
400 return 0; /* inside the lines themselves. */
403 return OUTSIDE
; /* outside the boundary lines. */
407 check_square_filled(const struct arg
*arg
, double x
, double y
)
409 /* The filter extends +/-FILTER_WIDTH each side of each output point, so
410 * the check has to expand and contract the square by that amount; '0'
411 * means close enough to the edge of the square that the bicubic filter has
412 * to be run, OUTSIDE means alpha==0, INSIDE means alpha==1.
414 return square_check_line(arg
, x
, y
, FILTER_WIDTH
);
418 inside_square(const struct arg
*arg
, double x
, double y
)
420 /* Return true if within the drawn lines, else false, no need to distinguish
421 * INSIDE vs OUTSIDE here:
423 return square_check_line(arg
, x
, y
, arg
->width
/2) == 0;
427 check_square(const struct arg
*arg
, double x
, double y
)
429 /* So for this function a result of 'INSIDE' means inside the actual lines.
431 double w
= arg
->width
/2;
433 if (square_check_line(arg
, x
, y
, w
+FILTER_WIDTH
) == 0)
435 /* Somewhere close to the boundary lines. If far enough inside one of
436 * them then we can return INSIDE:
440 if (w
> 0 && square_check_line(arg
, x
, y
, w
) == 0)
443 /* Point is somewhere in the filter region: */
447 else /* Inside or outside the square by more than w+FILTER_WIDTH. */
452 * { inside_circle_filled, check_circle_filled },
453 * { inside_circle, check_circle }
455 * The functions here are analoguous to the square ones; however, they check
456 * the corresponding ellipse as opposed to the rectangle.
459 circle_check(double x
, double y
, double x1
, double y1
, double x2
, double y2
)
461 if (square_check(x
, y
, x1
, y1
, x2
, y2
))
463 /* Inside the square, so maybe inside the circle too: */
464 const double cx
= (x1
+ x2
)/2;
465 const double cy
= (y1
+ y2
)/2;
466 const double dx
= x1
- x2
;
467 const double dy
= y1
- y2
;
472 /* It is outside if the distance from the center is more than half the
475 return x
*x
+y
*y
< .25;
478 return 0; /* outside */
482 inside_circle_filled(const struct arg
*arg
, double x
, double y
)
484 return circle_check(x
, y
, arg
->x1
, arg
->y1
, arg
->x2
, arg
->y2
);
488 circle_check_line(const struct arg
*arg
, double x
, double y
, double w
)
489 /* Check for a point being inside the boundaries implied by the given arg
490 * and assuming a width 2*w each side of the boundaries. This function has
491 * the same semantic as square_check_line but tests the circle.
494 double cx
= (arg
->x1
+arg
->x2
)/2;
495 double wx
= fabs(arg
->x1
-arg
->x2
)/2;
496 double cy
= (arg
->y1
+arg
->y2
)/2;
497 double wy
= fabs(arg
->y1
-arg
->y2
)/2;
499 if (circle_check(x
, y
, cx
-wx
-w
, cy
-wy
-w
, cx
+wx
+w
, cy
+wy
+w
))
501 /* Inside, but maybe too far; check for the redundant case where
506 if (wx
> 0 && wy
> 0 && circle_check(x
, y
, cx
-wx
, cy
-wy
, cx
+wx
, cy
+wy
))
507 return INSIDE
; /* between (inside) the boundary lines. */
509 return 0; /* inside the lines themselves. */
512 return OUTSIDE
; /* outside the boundary lines. */
516 check_circle_filled(const struct arg
*arg
, double x
, double y
)
518 return circle_check_line(arg
, x
, y
, FILTER_WIDTH
);
522 inside_circle(const struct arg
*arg
, double x
, double y
)
524 return circle_check_line(arg
, x
, y
, arg
->width
/2) == 0;
528 check_circle(const struct arg
*arg
, double x
, double y
)
530 /* Exactly as the 'square' code. */
531 double w
= arg
->width
/2;
533 if (circle_check_line(arg
, x
, y
, w
+FILTER_WIDTH
) == 0)
537 if (w
> 0 && circle_check_line(arg
, x
, y
, w
) == 0)
540 /* Point is somewhere in the filter region: */
544 else /* Inside or outside the square by more than w+FILTER_WIDTH. */
549 * { NULL, NULL }, There is no 'filled' line.
550 * { inside_line, check_line }
553 line_check(double x
, double y
, double x1
, double y1
, double x2
, double y2
,
554 double w
, double expand
)
556 /* Shift all the points to (arg->x1, arg->y1) */
559 double len2
= lx
*lx
+ ly
*ly
;
565 /* The dot product is the distance down the line, the cross product is
566 * the distance away from the line:
568 * distance = |cross| / sqrt(len2)
570 cross
= x
* ly
- y
* lx
;
572 /* If 'distance' is more than w the point is definitely outside the line:
575 * |cross| >= w * sqrt(len2)
576 * cross^2 >= w^2 * len2:
578 if (cross
*cross
>= (w
+expand
)*(w
+expand
)*len2
)
579 return 0; /* outside */
581 /* Now find the distance *along* the line; this comes from the dot product
582 * lx.x+ly.y. The actual distance (in pixels) is:
584 * distance = dot / sqrt(len2)
586 dot
= lx
* x
+ ly
* y
;
588 /* The test for 'outside' is:
590 * distance < 0 || distance > sqrt(len2)
591 * -> dot / sqrt(len2) > sqrt(len2)
594 * But 'expand' is used for the filter width and needs to be handled too:
596 return dot
> -expand
&& dot
< len2
+expand
;
600 inside_line(const struct arg
*arg
, double x
, double y
)
602 return line_check(x
, y
, arg
->x1
, arg
->y1
, arg
->x2
, arg
->y2
, arg
->width
/2, 0);
606 check_line(const struct arg
*arg
, double x
, double y
)
608 /* The end caps of the line must be checked too; it's not enough just to
609 * widen the line by FILTER_WIDTH; 'expand' exists for this purpose:
611 if (line_check(x
, y
, arg
->x1
, arg
->y1
, arg
->x2
, arg
->y2
, arg
->width
/2,
614 /* Inside the line+filter; far enough inside that the filter isn't
617 if (arg
->width
> 2*FILTER_WIDTH
&&
618 line_check(x
, y
, arg
->x1
, arg
->y1
, arg
->x2
, arg
->y2
, arg
->width
/2,
631 shape_fn_ptr function
[2/*fill,line*/][2];
637 { { inside_square_filled
, check_square_filled
},
638 { inside_square
, check_square
} }
641 { { inside_circle_filled
, check_circle_filled
},
642 { inside_circle
, check_circle
} }
646 { inside_line
, check_line
} }
650 #define shape_count ((sizeof shape_defs)/(sizeof shape_defs[0]))
653 shape_of(const char *arg
, double width
, int f
)
657 for (i
=0; i
<shape_count
; ++i
) if (strcmp(shape_defs
[i
].name
, arg
) == 0)
659 shape_fn_ptr fn
= shape_defs
[i
].function
[width
!= 0][f
];
664 fprintf(stderr
, "genpng: %s %s not supported\n",
665 width
== 0 ? "filled" : "unfilled", arg
);
669 fprintf(stderr
, "genpng: %s: not a valid shape name\n", arg
);
674 parse_arg(struct arg
*arg
, const char **argv
/*7 arguments*/)
676 /* shape ::= color width shape x1 y1 x2 y2 */
677 arg
->color
= color_of(argv
[0]);
678 arg
->width
= width_of(argv
[1]);
679 arg
->inside_fn
= shape_of(argv
[2], arg
->width
, FN_INSIDE
);
680 arg
->check_fn
= shape_of(argv
[2], arg
->width
, FN_CHECK
);
681 arg
->x1
= coordinate_of(argv
[3]);
682 arg
->y1
= coordinate_of(argv
[4]);
683 arg
->x2
= coordinate_of(argv
[5]);
684 arg
->y2
= coordinate_of(argv
[6]);
688 read_wh(const char *name
, const char *str
)
689 /* read a PNG width or height */
692 unsigned long ul
= strtoul(str
, &ep
, 10);
694 if (ep
!= NULL
&& *ep
== 0 && ul
> 0 && ul
<= 0x7fffffff)
695 return (png_uint_32
)/*SAFE*/ul
;
697 fprintf(stderr
, "genpng: %s: invalid number %s\n", name
, str
);
702 pixel(png_uint_16p p
, struct arg
*args
, int nargs
, double x
, double y
)
704 /* Fill in the pixel by checking each shape (args[nargs]) for effects on
705 * the corresponding sample:
707 double r
=0, g
=0, b
=0, a
=0;
709 while (--nargs
>= 0 && a
!= 1)
711 /* NOTE: alpha_calc can return a value outside the range 0..1 with the
714 const double alpha
= alpha_calc(args
+nargs
, x
, y
) * (1-a
);
716 r
+= alpha
* args
[nargs
].color
->red
;
717 g
+= alpha
* args
[nargs
].color
->green
;
718 b
+= alpha
* args
[nargs
].color
->blue
;
722 /* 'a' may be negative or greater than 1; if it is, negative clamp the
723 * pixel to 0 if >1 clamp r/g/b:
735 /* And fill in the pixel: */
736 p
[0] = (png_uint_16
)/*SAFE*/round(r
* 65535);
737 p
[1] = (png_uint_16
)/*SAFE*/round(g
* 65535);
738 p
[2] = (png_uint_16
)/*SAFE*/round(b
* 65535);
739 p
[3] = (png_uint_16
)/*SAFE*/round(a
* 65535);
743 p
[3] = p
[2] = p
[1] = p
[0] = 0;
747 main(int argc
, const char **argv
)
749 int convert_to_8bit
= 0;
751 /* There is one option: --8bit: */
752 if (argc
> 1 && strcmp(argv
[1], "--8bit") == 0)
753 --argc
, ++argv
, convert_to_8bit
= 1;
760 # define max_shapes 256
761 struct arg arg_list
[max_shapes
];
763 /* The libpng Simplified API write code requires a fully initialized
766 memset(&image
, 0, sizeof image
);
767 image
.version
= PNG_IMAGE_VERSION
;
769 image
.width
= read_wh("width", argv
[1]);
770 image
.height
= read_wh("height", argv
[2]);
771 image
.format
= PNG_FORMAT_LINEAR_RGB_ALPHA
;
773 image
.colormap_entries
= 0;
775 /* Check the remainder of the arguments */
776 for (nshapes
=0; 3+7*(nshapes
+1) <= argc
&& nshapes
< max_shapes
;
778 parse_arg(arg_list
+nshapes
, argv
+3+7*nshapes
);
780 if (3+7*nshapes
!= argc
)
782 fprintf(stderr
, "genpng: %s: too many arguments\n", argv
[3+7*nshapes
]);
786 /* Create the buffer: */
787 buffer
= malloc(PNG_IMAGE_SIZE(image
));
793 /* Write each row... */
794 for (y
=0; y
<image
.height
; ++y
)
798 /* Each pixel in each row: */
799 for (x
=0; x
<image
.width
; ++x
)
800 pixel(buffer
+ 4*(x
+ y
*image
.width
), arg_list
, nshapes
, x
, y
);
803 /* Write the result (to stdout) */
804 if (png_image_write_to_stdio(&image
, stdout
, convert_to_8bit
,
805 buffer
, 0/*row_stride*/, NULL
/*colormap*/))
808 return 0; /* success */
812 fprintf(stderr
, "genpng: write stdout: %s\n", image
.message
);
818 fprintf(stderr
, "genpng: out of memory: %lu bytes\n",
819 (unsigned long)PNG_IMAGE_SIZE(image
));
824 /* Wrong number of arguments */
825 fprintf(stderr
, "genpng: usage: genpng [--8bit] width height {shape}\n"
826 " Generate a transparent PNG in RGBA (truecolor+alpha) format\n"
827 " containing the given shape or shapes. Shapes are defined:\n"
829 " shape ::= color width shape x1 y1 x2 y2\n"
830 " color ::= black|white|red|green|yellow|blue\n"
831 " color ::= brown|purple|pink|orange|gray|cyan\n"
832 " width ::= filled|<number>\n"
833 " shape ::= circle|square|line\n"
834 " x1,x2 ::= <number>\n"
835 " y1,y2 ::= <number>\n"
837 " Numbers are floating point numbers describing points relative to\n"
838 " the top left of the output PNG as pixel coordinates. The 'width'\n"
839 " parameter is either the width of the line (in output pixels) used\n"
840 " to draw the shape or 'filled' to indicate that the shape should\n"
841 " be filled with the color.\n"
843 " Colors are interpreted loosely to give access to the eight full\n"
844 " intensity RGB values:\n"
846 " black, red, green, blue, yellow, cyan, purple, white,\n"
848 " Cyan is full intensity blue+green; RGB(0,1,1), plus the following\n"
849 " lower intensity values:\n"
851 " brown: red+orange: RGB(0.5, 0.125, 0) (dark red+orange)\n"
852 " pink: red+white: RGB(1.0, 0.5, 0.5)\n"
853 " orange: red+yellow: RGB(1.0, 0.5, 0)\n"
854 " gray: black+white: RGB(0.5, 0.5, 0.5)\n"
856 " The RGB values are selected to make detection of aliasing errors\n"
857 " easy. The names are selected to make the description of errors\n"
860 " The PNG is written to stdout, if --8bit is given a 32bpp RGBA sRGB\n"
861 " file is produced, otherwise a 64bpp RGBA linear encoded file is\n"
867 #endif /* SIMPLIFIED_WRITE && STDIO */