1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
|
/* $Xorg: curves.c,v 1.3 2000/08/17 19:46:29 cpqbld Exp $ */
/* Copyright International Business Machines,Corp. 1991 */
/* All Rights Reserved */
/* License to use, copy, modify, and distribute this software */
/* and its documentation for any purpose and without fee is */
/* hereby granted, provided that licensee provides a license to */
/* IBM, Corp. to use, copy, modify, and distribute derivative */
/* works and their documentation for any purpose and without */
/* fee, that the above copyright notice appear in all copies */
/* and that both that copyright notice and this permission */
/* notice appear in supporting documentation, and that the name */
/* of IBM not be used in advertising or publicity pertaining to */
/* distribution of the software without specific, written prior */
/* permission. */
/* IBM PROVIDES THIS SOFTWARE "AS IS", WITHOUT ANY WARRANTIES */
/* OF ANY KIND, EITHER EXPRESS OR IMPLIED, INCLUDING, BUT NOT */
/* LIMITED TO ANY IMPLIED WARRANTIES OF MERCHANTABILITY, */
/* FITNESS FOR A PARTICULAR PURPOSE, AND NONINFRINGEMENT OF */
/* THIRD PARTY RIGHTS. THE ENTIRE RISK AS TO THE QUALITY AND */
/* PERFORMANCE OF THE SOFTWARE, INCLUDING ANY DUTY TO SUPPORT */
/* OR MAINTAIN, BELONGS TO THE LICENSEE. SHOULD ANY PORTION OF */
/* THE SOFTWARE PROVE DEFECTIVE, THE LICENSEE (NOT IBM) ASSUMES */
/* THE ENTIRE COST OF ALL SERVICING, REPAIR AND CORRECTION. IN */
/* NO EVENT SHALL IBM BE LIABLE FOR ANY SPECIAL, INDIRECT OR */
/* CONSEQUENTIAL DAMAGES OR ANY DAMAGES WHATSOEVER RESULTING */
/* FROM LOSS OF USE, DATA OR PROFITS, WHETHER IN AN ACTION OF */
/* CONTRACT, NEGLIGENCE OR OTHER TORTIOUS ACTION, ARISING OUT */
/* OF OR IN CONNECTION WITH THE USE OR PERFORMANCE OF THIS */
/* SOFTWARE. */
/* $XFree86: xc/lib/font/Type1/curves.c,v 1.7 2001/08/27 19:49:52 dawes Exp $ */
/*
:h1.CURVES Module - Stepping Beziers
This module is responsible for "rasterizing"
third order curves. That is, it changes the high level curve
specification into a list of pels that that curve travels
through.
:h3.Include Files
Include files needed:
*/
#include "os.h"
#include "objects.h"
#include "spaces.h"
#include "paths.h"
#include "regions.h"
#include "curves.h"
#include "lines.h"
#include "arith.h"
/*
:h3.Functions Provided to Other Modules
External entry points:
*/
/*SHARED LINE(S) ORIGINATED HERE*/
/*
Note that "stepping" and "flattening" are so similiar that they use the
same routine. When the "region" parameter is NULL, that is a flag that
we are flattening instead of stepping.
*/
/*
:h2.Bezier Third Order Curves
*/
/*
:h3.The "bezierinfo" Structure
This structure is used to store information used when we subdivide
Bezier curves.
*/
struct bezierinfo {
struct region *region; /* the region being built or NULL */
struct fractpoint last; /* not used yet; maybe could save some work */
struct fractpoint origin; /* the origin of the bezier */
} ;
/*
Checking for termination of the subdivision process:
This is the stupidest test in the world, just check if the coordinatewise
distance from an end control point to the next control point is less than
one half pel. If so, we must be done.
This returns 1 if the subdivision is terminated and 0 if you still need
to subdivide.
*/
static int
BezierTerminationTest(fractpel xa, fractpel ya,
fractpel xb, fractpel yb,
fractpel xc, fractpel yc,
fractpel xd, fractpel yd)
{
fractpel dmax;
dmax = ABS(xa - xb);
dmax = MAX(dmax,ABS(ya - yb));
dmax = MAX(dmax,ABS(xd - xc));
dmax = MAX(dmax,ABS(yd - yc));
if(dmax > FPHALF)
return(0); /* not done yet */
else
return(1); /* done */
}
/*
:h3.StepBezierRecurse() - The Recursive Logic in StepBezier()
The recursion involves dividing the control polygon into two smaller
control polygons by finding the midpoints of the lines. This idea is
described in any graphics text book and its simplicity is what caused
Bezier to define his curves as he did. If the input region 'R' is NULL,
the result is a path that is the 'flattened' curve; otherwise StepBezier
returns nothing special.
*/
static struct segment *
StepBezierRecurse(struct bezierinfo *I, /* Region under construction or NULL */
fractpel xA, fractpel yA, /* A control point */
fractpel xB, fractpel yB, /* B control point */
fractpel xC, fractpel yC, /* C control point */
fractpel xD, fractpel yD) /* D control point */
{
if (BezierTerminationTest(xA,yA,xB,yB,xC,yC,xD,yD))
{
if (I->region == NULL)
return(PathSegment(LINETYPE, xD - xA, yD - yA));
else
StepLine(I->region, I->origin.x + xA, I->origin.y + yA,
I->origin.x + xD, I->origin.y + yD);
}
else
{
fractpel xAB,yAB;
fractpel xBC,yBC;
fractpel xCD,yCD;
fractpel xABC,yABC;
fractpel xBCD,yBCD;
fractpel xABCD,yABCD;
xAB = xA + xB; yAB = yA + yB;
xBC = xB + xC; yBC = yB + yC;
xCD = xC + xD; yCD = yC + yD;
xABC = xAB + xBC; yABC = yAB + yBC;
xBCD = xBC + xCD; yBCD = yBC + yCD;
xABCD = xABC + xBCD; yABCD = yABC + yBCD;
xAB >>= 1; yAB >>= 1;
xBC >>= 1; yBC >>= 1;
xCD >>= 1; yCD >>= 1;
xABC >>= 2; yABC >>= 2;
xBCD >>= 2; yBCD >>= 2;
xABCD >>= 3; yABCD >>= 3;
if (I->region == NULL)
{
return( Join(
StepBezierRecurse(I, xA, yA, xAB, yAB, xABC, yABC, xABCD, yABCD),
StepBezierRecurse(I, xABCD, yABCD, xBCD, yBCD, xCD, yCD, xD, yD)
)
);
}
else
{
StepBezierRecurse(I, xA, yA, xAB, yAB, xABC, yABC, xABCD, yABCD);
StepBezierRecurse(I, xABCD, yABCD, xBCD, yBCD, xCD, yCD, xD, yD);
}
}
return NULL;
/*NOTREACHED*/
}
/*
:h3.TOOBIG() - Macro to Test if a Coordinate is Too Big to Bezier SubDivide Normally
Intermediate values in the Bezier subdivision are 8 times bigger than
the starting values. If this overflows, a 'long', we are in trouble:
*/
#undef BITS
#define BITS (sizeof(long)*8)
#define HIGHTEST(p) (((p)>>(BITS-4)) != 0) /* includes sign bit */
#define TOOBIG(xy) ((xy < 0) ? HIGHTEST(-xy) : HIGHTEST(xy))
/*
:h3.StepBezier() - Produce Run Ends for a Bezier Curve
This is the entry point called from outside the module.
*/
struct segment *
StepBezier(struct region *R, /* Region under construction or NULL */
fractpel xA, fractpel yA, /* A control point */
fractpel xB, fractpel yB, /* B control point */
fractpel xC, fractpel yC, /* C control point */
fractpel xD, fractpel yD) /* D control point */
{
struct bezierinfo Info;
Info.region = R;
Info.origin.x = xA;
Info.origin.y = yA;
xB -= xA;
xC -= xA;
xD -= xA;
yB -= yA;
yC -= yA;
yD -= yA;
if ( TOOBIG(xB) || TOOBIG(yB) || TOOBIG(xC) || TOOBIG(yC)
|| TOOBIG(xD) || TOOBIG(yD) )
Abort("Beziers this big not yet supported");
return(StepBezierRecurse(&Info,
(fractpel) 0, (fractpel) 0, xB, yB, xC, yC, xD, yD));
}
|
