src/bedbugs.c

   1 /*
   2  * Relevant bits of original copyright notice from
   3  * http://bjh21.me.uk/bedstead/  bedstead.c  #137:
   4  *
   5  * [...] the file is covered by the following:
   6  *
   7  * Copyright (c) 2009 Ben Harris.
   8  *
   9  * Permission is hereby granted, free of charge, to any person
  10  * obtaining a copy of this software and associated documentation files
  11  * (the "Software"), to deal in the Software without restriction,
  12  * including without limitation the rights to use, copy, modify, merge,
  13  * publish, distribute, sublicense, and/or sell copies of the Software,
  14  * and to permit persons to whom the Software is furnished to do so,
  15  * subject to the following conditions:
  16  *
  17  * The above copyright notice and this permission notice shall be
  18  * included in all copies or substantial portions of the Software.
  19  *
  20  * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
  21  * EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF
  22  * MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND
  23  * NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS
  24  * BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN
  25  * ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN
  26  * CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE
  27  * SOFTWARE.
  28  */
  29 /*
  30  * This is a program to construct an outline font from a bitmap.  It's
  31  * based on the character-rounding algorithm of the Mullard SAA5050
  32  * series of Teletext character generators, and thus works best on
  33  * character shapes in the same style of those of the SAA5050.  This
  34  * file includes all of the glyphs from the SAA5050, SAA5051, SAA5052,
  35  * SAA5053, SAA5054, SAA5055, SAA5056, and SAA5057.  The output is a
  36  * Spline Font Database file suitable for feeding to Fontforge.
  37  *
  38  * The character-smoothing algorithm of the SAA5050 and friends is
  39  * a fairly simple means of expanding a 5x9 pixel character to 10x18
  40  * pixels for use on an interlaced display.  All it does is to detect
  41  * 2x2 clumps of pixels containing a diagonal line and add a couple of
  42  * subpixels to it, like this:
  43  *
  44  * . #  -> . . # # -> . . # # or # . -> # # . . -> # # . .
  45  * # .     . . # #    . # # #    . #    # # . .    # # # .
  46  *         # # . .    # # # .           . . # #    . # # #
  47  *         # # . .    # # . .           . . # #    . . # #
  48  *
  49  * This is applied to every occurrence of these patterns, even when
  50  * they overlap, and the result is that thin diagonal lines are
  51  * smoothed out while other features mostly remain the same.
  52  *
  53  * One way of extending this towards continuity would be to repeatedly
  54  * double the resolution and add more pixels to diagonals each time,
  55  * but this ends up with the diagonals being much too heavy.  Instead,
  56  * in places where the SAA5050 would add pixels, this program adds a
  57  * largeish triangle to each unfilled pixel, and removes a small
  58  * triangle from each filled one, something like this:
  59  *
  60  * . #  -> . . # # -> . . / # or # . -> # # . . -> # \ . .
  61  * # .     . . # #    . / # /    . #    # # . .    \ # \ .
  62  *         # # . .    / # / .           . . # #    . \ # \
  63  *         # # . .    # / . .           . . # #    . . \ #
  64  *
  65  * The position of the lines is such that on a long diagonal line, the
  66  * amount of filled space is the same as in the rounded bitmap.  There
  67  * are a few additional complications, in that the trimming of filled
  68  * pixels can leave odd gaps where a diagonal stem joins another one,
  69  * so the code detects this and doesn't trim in these cases:
  70  *
  71  * . # # -> . . # # # # -> . . / # # # -> . . / # # #
  72  * # . .    . . # # # #    . / # / # #    . / # # # #
  73  *          # # . . . .    / # / . . .    / # / . . .
  74  *          # # . . . .    # / . . . .    # / . . . .
  75  *
  76  * That is the interesting part of the program, and is in the dochar()
  77  * function.  Most of the rest is just dull geometry to join all the
  78  * bits together into a sensible outline.  Much of the code is wildly
  79  * inefficient -- O(n^2) algorithms aren't much of a problem when you
  80  * have at most a few thousand points to deal with.
  81  *
  82  * A rather nice feature of the outlines produced by this program is
  83  * that when rasterised at precisely 10 or 20 pixels high, they
  84  * produce the input and output respectively of the character-rounding
  85  * process.  While there are obious additional smoothings that could
  86  * be applied, doing so would probably lose this nice property.
  87  *
  88  * [...]
  89  */
  90
  91 #include <stdbool.h>
  92 #include <stdio.h>
  93 #include <stdlib.h>
  94 #include <string.h>
  95
  96 static bool *
  97 blank(int size)
  98 {
  99     return calloc(size*size, sizeof(bool));
 100 }
 101
 102 static void output(bool *r, int size) {
 103     int x, y;
 104     for (y=0; y<size; y++) {
 105         putchar('\"');
 106         for (x=0; x<size; x++) {
 107             putchar(r[x+y*size] ? 'A' : '.');
 108         }
 109         putchar('\"');
 110         putchar('\n');
 111     }
 112 }
 113
 114 static bool *
 115 triangle(bool *r, int size, int startpos, bool top, bool left)
 116 {
 117     int x, y;
 118     for (y = 0; y < startpos; y++) {
 119         for (x = 0; x < startpos-y; x++) {
 120             int rx, ry;
 121             if (top) {
 122                 ry = y;
 123             } else {
 124                 ry = size-1 - y;
 125             }
 126             if (left) {
 127                 rx = x;
 128             } else {
 129                 rx = size-1 - x;
 130             }
 131             r[rx+ry*size]=true;
 132         }
 133     }
 134     return r;
 135 }
 136
 137 static void
 138 triangles(bool *r, int size, int startpos, int bl, int br, int tr, int tl)
 139 {
 140     if (!bl) {
 141         triangle(r, size, startpos, false, true);
 142     }
 143     if (!br) {
 144         triangle(r, size, startpos, false, false);
 145     }
 146     if (!tr) {
 147         triangle(r, size, startpos, true, false);
 148     }
 149     if (!tl) {
 150         triangle(r, size, startpos, true, true);
 151     }
 152 }
 153
 154 static void
 155 whitepixel(bool *r, int size, int bl, int br, int tr, int tl)
 156 {
 157     /* wrt blackpixel(): -1 for adjacency, -1 for gridlines */
 158     const int startpos = size-size/4-2;
 159     triangles(r, size, startpos, bl, br, tr, tl);
 160 }
 161
 162 static void
 163 blackpixel(bool *r, int size, int bl, int br, int tr, int tl)
 164 {
 165     const int startpos = size/4;
 166     int i;
 167     triangles(r, size, startpos, bl, br, tr, tl);
 168     for (i=0; i<size*size; i++) {
 169         r[i] = !r[i];
 170     }
 171 }
 172
 173 int main(int argc, char *argv[])
 174 {
 175 #define GETPIX(x,y) (!!(iter & 1u<<((y)*3+(x))))
 176 #define L GETPIX(x-1, y)
 177 #define R GETPIX(x+1, y)
 178 #define U GETPIX(x, y-1)
 179 #define D GETPIX(x, y+1)
 180 #define UL GETPIX(x-1, y-1)
 181 #define UR GETPIX(x+1, y-1)
 182 #define DL GETPIX(x-1, y+1)
 183 #define DR GETPIX(x+1, y+1)
 184
 185         int iter;
 186         for (iter = 0; iter < 1u<<9; iter++) {
 187                         int state, x = 1, y = 1;
 188                         if (GETPIX(x, y)) {
 189                                 bool tl, tr, bl, br;
 190
 191                                 /* Assume filled in */
 192                                 tl = tr = bl = br = true;
 193                                 /* Check for diagonals */
 194                                 if ((UL && !U && !L) || (DR && !D && !R))
 195                                         tr = bl = false;
 196                                 if ((UR && !U && !R) || (DL && !D && !L))
 197                                         tl = br = false;
 198                                 /* Avoid odd gaps */
 199                                 if (L || UL || U) tl = true;
 200                                 if (R || UR || U) tr = true;
 201                                 if (L || DL || D) bl = true;
 202                                 if (R || DR || D) br = true;
 203                                 state = 2 + 16 + (bl | br<<1 | tr<<2 | tl<<3);
 204                         } else {
 205                                 bool tl, tr, bl, br;
 206
 207                                 /* Assume clear */
 208                                 tl = tr = bl = br = false;
 209                                 /* white pixel -- just diagonals */
 210                                 if (L && U && !UL) tl = true;
 211                                 if (R && U && !UR) tr = true;
 212                                 if (L && D && !DL) bl = true;
 213                                 if (R && D && !DR) br = true;
 214                                 state = 2 + (bl | br<<1 | tr<<2 | tl<<3);
 215                         }
 216                         printf("%d,%d,%d,%d,%d,%d,%d,%d,%d,%d\n",
 217                                GETPIX(x,y),U,UR,R,DR,D,DL,L,UL,state);
 218         }
 219         {
 220             const int sizes[] = {7, 15, 31};
 221             int size_index;
 222             for (size_index = 0;
 223                  size_index < sizeof(sizes)/sizeof(sizes[0]);
 224                  size_index++) {
 225                 int size = sizes[size_index], state;
 226                 printf("XPM\n/* width height num_colors chars_per_pixel */\n");
 227                 printf("\"%d %d 2 1\"\n", size, size*33);
 228                 printf("/* colors */\n\". c #000000\"\n\"A c #FFFFFF\"\n");
 229                 /* icons never used for state 0 */
 230                 for (state = 1; state < 34; state++) {
 231                     bool *r = blank(size);
 232                     if (state == 0) {
 233                         ; /* nothing */
 234                     } else if (state == 1) {
 235                         /* everything */
 236                         memset(r, 1, size*size*sizeof(*r));
 237                     } else if (state < 16+2) {
 238                         int bits = ~(state-2);
 239                         whitepixel(r, size, bits&1, bits&2, bits&4, bits&8);
 240                     } else {
 241                         int bits = state-16-2;
 242                         blackpixel(r, size, bits&1, bits&2, bits&4, bits&8);
 243                     }
 244                     printf("/* icon for state %d */\n", state);
 245                     output(r, size);
 246                     free(r);
 247                 }
 248             }
 249         }
 250         return 0;
 251 }