1 /* Copyright (C) 1989, 1992, 1998, 1999 Aladdin Enterprises. All rights reserved.
2
3 This software is provided AS-IS with no warranty, either express or
4 implied.
5
6 This software is distributed under license and may not be copied,
7 modified or distributed except as expressly authorized under the terms
8 of the license contained in the file LICENSE in this distribution.
9
10 For more information about licensing, please refer to
11 http://www.ghostscript.com/licensing/. For information on
12 commercial licensing, go to http://www.artifex.com/licensing/ or
13 contact Artifex Software, Inc., 101 Lucas Valley Road #110,
14 San Rafael, CA 94903, U.S.A., +1(415)492-9861.
15 */
16
17 /* $Id: gsimpath.c,v 1.5 2002/06/16 05:48:55 lpd Exp $ */
18 /* Image to outline conversion for Ghostscript library */
19 #include "gx.h"
20 #include "gserrors.h"
21 #include "gsmatrix.h"
22 #include "gspaint.h" /* for gs_imagepath prototype */
23 #include "gsstate.h"
24 #include "gspath.h"
25
26 /* Define the state of the conversion process. */
27 typedef struct {
28 /* The following are set at the beginning of the conversion. */
29 gs_state *pgs;
30 const byte *data; /* image data */
31 int width, height, raster;
32 /* The following are updated dynamically. */
33 int dx, dy; /* X/Y increment of current run */
34 int count; /* # of steps in current run */
35 } status;
36
37 /* Define the scaling for the path tracer. */
38 /* It must be even. */
39 #define outline_scale 4
40 /* Define the length of the short strokes for turning corners. */
41 #define step 1
42
43 /* Forward declarations */
44 private int get_pixel(const status *, int, int);
45 private int trace_from(status *, int, int, int);
46 private int add_dxdy(status *, int, int, int);
47
48 #define add_deltas(s, dx, dy, n)\
49 if ( (code = add_dxdy(s, dx, dy, n)) < 0 ) return code
50 /* Append an outline derived from an image to the current path. */
51 int
gs_imagepath(gs_state * pgs,int width,int height,const byte * data)52 gs_imagepath(gs_state * pgs, int width, int height, const byte * data)
53 {
54 status stat;
55 status *out = &stat;
56 int code, x, y;
57
58 /* Initialize the state. */
59 stat.pgs = pgs;
60 stat.data = data;
61 stat.width = width;
62 stat.height = height;
63 stat.raster = (width + 7) / 8;
64 /* Trace the cells to form an outline. The trace goes in clockwise */
65 /* order, always starting by going west along a bottom edge. */
66 for (y = height - 1; y >= 0; y--)
67 for (x = width - 1; x >= 0; x--) {
68 if (get_pixel(out, x, y) && !get_pixel(out, x, y - 1) &&
69 (!get_pixel(out, x + 1, y) || get_pixel(out, x + 1, y - 1)) &&
70 !trace_from(out, x, y, 1)
71 ) { /* Found a starting point */
72 stat.count = 0;
73 stat.dx = stat.dy = 0;
74 if ((code = trace_from(out, x, y, 0)) < 0)
75 return code;
76 add_deltas(out, 0, 0, 1); /* force out last segment */
77 if ((code = gs_closepath(pgs)) < 0)
78 return code;
79 }
80 }
81 return 0;
82 }
83
84 /* Get a pixel from the data. Return 0 if outside the image. */
85 private int
get_pixel(register const status * out,int x,int y)86 get_pixel(register const status * out, int x, int y)
87 {
88 if (x < 0 || x >= out->width || y < 0 || y >= out->height)
89 return 0;
90 return (out->data[y * out->raster + (x >> 3)] >> (~x & 7)) & 1;
91 }
92
93 /* Trace a path. If detect is true, don't draw, just return 1 if we ever */
94 /* encounter a starting point whose x,y follows that of the initial point */
95 /* in x-then-y scan order; if detect is false, actually draw the outline. */
96 private int
trace_from(register status * out,int x0,int y0,int detect)97 trace_from(register status * out, int x0, int y0, int detect)
98 {
99 int x = x0, y = y0;
100 int dx = -1, dy = 0; /* initially going west */
101 int part = 0; /* how far along edge we are; */
102
103 /* initialized only to pacify gcc */
104 int code;
105
106 if (!detect) {
107 part = (get_pixel(out, x + 1, y - 1) ?
108 outline_scale - step : step);
109 code = gs_moveto(out->pgs,
110 x + 1 - part / (float)outline_scale,
111 (float)y);
112 if (code < 0)
113 return code;
114 }
115 while (1) { /* Relative to the current direction, */
116 /* -dy,dx is at +90 degrees (counter-clockwise); */
117 /* tx,ty is at +45 degrees; */
118 /* ty,-tx is at -45 degrees (clockwise); */
119 /* dy,-dx is at -90 degrees. */
120 int tx = dx - dy, ty = dy + dx;
121
122 if (get_pixel(out, x + tx, y + ty)) { /* Cell at 45 degrees is full, */
123 /* go counter-clockwise. */
124 if (!detect) { /* If this is a 90 degree corner set at a */
125 /* 45 degree angle, avoid backtracking. */
126 if (out->dx == ty && out->dy == -tx) {
127 #define half_scale (outline_scale / 2 - step)
128 out->count -= half_scale;
129 add_deltas(out, tx, ty, outline_scale / 2);
130 #undef half_scale
131 } else {
132 add_deltas(out, dx, dy, step - part);
133 add_deltas(out, tx, ty, outline_scale - step);
134 }
135 part = outline_scale - step;
136 }
137 x += tx, y += ty;
138 dx = -dy, dy += tx;
139 } else if (!get_pixel(out, x + dx, y + dy)) { /* Cell straight ahead is empty, go clockwise. */
140 if (!detect) {
141 add_deltas(out, dx, dy, outline_scale - step - part);
142 add_deltas(out, ty, -tx, step);
143 part = step;
144 }
145 dx = dy, dy -= ty;
146 } else { /* Neither of the above, go in same direction. */
147 if (!detect) {
148 add_deltas(out, dx, dy, outline_scale);
149 }
150 x += dx, y += dy;
151 }
152 if (dx == -step && dy == 0 && !(tx == -step && ty == -step)) { /* We just turned a corner and are going west, */
153 /* so the previous pixel is a starting point pixel. */
154 if (x == x0 && y == y0)
155 return 0;
156 if (detect && (y > y0 || (y == y0 && x > x0)))
157 return 1;
158 }
159 }
160 }
161
162 /* Add a (dx, dy) pair to the path being formed. */
163 /* Accumulate successive segments in the same direction. */
164 private int
add_dxdy(register status * out,int dx,int dy,int count)165 add_dxdy(register status * out, int dx, int dy, int count)
166 {
167 if (count != 0) {
168 if (dx == out->dx && dy == out->dy)
169 out->count += count;
170 else {
171 if (out->count != 0) {
172 int code = gs_rlineto(out->pgs,
173 out->dx * out->count / (float)outline_scale,
174 out->dy * out->count / (float)outline_scale);
175
176 if (code < 0)
177 return code;
178 }
179 out->dx = dx, out->dy = dy;
180 out->count = count;
181 }
182 }
183 return 0;
184 }
185