1 /*
2 * FTGL - OpenGL font library
3 *
4 * Copyright (c) 2001-2004 Henry Maddocks <ftgl@opengl.geek.nz>
5 * Copyright (c) 2008 Sam Hocevar <sam@zoy.org>
6 * Copyright (c) 2008 Éric Beets <ericbeets@free.fr>
7 *
8 * Permission is hereby granted, free of charge, to any person obtaining
9 * a copy of this software and associated documentation files (the
10 * "Software"), to deal in the Software without restriction, including
11 * without limitation the rights to use, copy, modify, merge, publish,
12 * distribute, sublicense, and/or sell copies of the Software, and to
13 * permit persons to whom the Software is furnished to do so, subject to
14 * the following conditions:
15 *
16 * The above copyright notice and this permission notice shall be
17 * included in all copies or substantial portions of the Software.
18 *
19 * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
20 * EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF
21 * MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT.
22 * IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY
23 * CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION OF CONTRACT,
24 * TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION WITH THE
25 * SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
26 */
27
28 #include "config.h"
29
30 #include "FTContour.h"
31
32 #include <math.h>
33
34 static const unsigned int BEZIER_STEPS = 5;
35
36
AddPoint(FTPoint point)37 void FTContour::AddPoint(FTPoint point)
38 {
39 if(pointList.empty() || (point != pointList[pointList.size() - 1]
40 && point != pointList[0]))
41 {
42 pointList.push_back(point);
43 }
44 }
45
46
AddOutsetPoint(FTPoint point)47 void FTContour::AddOutsetPoint(FTPoint point)
48 {
49 outsetPointList.push_back(point);
50 }
51
52
AddFrontPoint(FTPoint point)53 void FTContour::AddFrontPoint(FTPoint point)
54 {
55 frontPointList.push_back(point);
56 }
57
58
AddBackPoint(FTPoint point)59 void FTContour::AddBackPoint(FTPoint point)
60 {
61 backPointList.push_back(point);
62 }
63
64
evaluateQuadraticCurve(FTPoint A,FTPoint B,FTPoint C)65 void FTContour::evaluateQuadraticCurve(FTPoint A, FTPoint B, FTPoint C)
66 {
67 for(unsigned int i = 1; i < BEZIER_STEPS; i++)
68 {
69 float t = static_cast<float>(i) / BEZIER_STEPS;
70
71 FTPoint U = (1.0f - t) * A + t * B;
72 FTPoint V = (1.0f - t) * B + t * C;
73
74 AddPoint((1.0f - t) * U + t * V);
75 }
76 }
77
78
evaluateCubicCurve(FTPoint A,FTPoint B,FTPoint C,FTPoint D)79 void FTContour::evaluateCubicCurve(FTPoint A, FTPoint B, FTPoint C, FTPoint D)
80 {
81 for(unsigned int i = 0; i < BEZIER_STEPS; i++)
82 {
83 float t = static_cast<float>(i) / BEZIER_STEPS;
84
85 FTPoint U = (1.0f - t) * A + t * B;
86 FTPoint V = (1.0f - t) * B + t * C;
87 FTPoint W = (1.0f - t) * C + t * D;
88
89 FTPoint M = (1.0f - t) * U + t * V;
90 FTPoint N = (1.0f - t) * V + t * W;
91
92 AddPoint((1.0f - t) * M + t * N);
93 }
94 }
95
96
97 // This function is a bit tricky. Given a path ABC, it returns the
98 // coordinates of the outset point facing B on the left at a distance
99 // of 64.0.
100 // M
101 // - - - - - - X
102 // ^ / '
103 // | 64.0 / '
104 // X---->-----X ==> X--v-------X '
105 // A B \ A B \ .>'
106 // \ \<' 64.0
107 // \ \ .
108 // \ \ .
109 // C X C X
110 //
ComputeOutsetPoint(FTPoint A,FTPoint B,FTPoint C)111 FTPoint FTContour::ComputeOutsetPoint(FTPoint A, FTPoint B, FTPoint C)
112 {
113 /* Build the rotation matrix from 'ba' vector */
114 FTPoint ba = (A - B).Normalise();
115 FTPoint bc = C - B;
116
117 /* Rotate bc to the left */
118 FTPoint tmp(bc.X() * -ba.X() + bc.Y() * -ba.Y(),
119 bc.X() * ba.Y() + bc.Y() * -ba.X());
120
121 /* Compute the vector bisecting 'abc' */
122 FTGL_DOUBLE norm = sqrt(tmp.X() * tmp.X() + tmp.Y() * tmp.Y());
123 FTGL_DOUBLE dist = 64.0 * sqrt((norm - tmp.X()) / (norm + tmp.X()));
124 tmp.X(tmp.Y() < 0.0 ? dist : -dist);
125 tmp.Y(64.0);
126
127 /* Rotate the new bc to the right */
128 return FTPoint(tmp.X() * -ba.X() + tmp.Y() * ba.Y(),
129 tmp.X() * -ba.Y() + tmp.Y() * -ba.X());
130 }
131
132
SetParity(int parity)133 void FTContour::SetParity(int parity)
134 {
135 size_t size = PointCount();
136 FTPoint vOutset;
137
138 if(((parity & 1) && clockwise) || (!(parity & 1) && !clockwise))
139 {
140 // Contour orientation is wrong! We must reverse all points.
141 // FIXME: could it be worth writing FTVector::reverse() for this?
142 for(size_t i = 0; i < size / 2; i++)
143 {
144 FTPoint tmp = pointList[i];
145 pointList[i] = pointList[size - 1 - i];
146 pointList[size - 1 -i] = tmp;
147 }
148
149 clockwise = !clockwise;
150 }
151
152 for(size_t i = 0; i < size; i++)
153 {
154 size_t prev, cur, next;
155
156 prev = (i + size - 1) % size;
157 cur = i;
158 next = (i + size + 1) % size;
159
160 vOutset = ComputeOutsetPoint(Point(prev), Point(cur), Point(next));
161 AddOutsetPoint(vOutset);
162 }
163 }
164
165
FTContour(FT_Vector * contour,char * tags,unsigned int n)166 FTContour::FTContour(FT_Vector* contour, char* tags, unsigned int n)
167 {
168 FTPoint prev, cur(contour[(n - 1) % n]), next(contour[0]);
169 FTPoint a, b = next - cur;
170 double olddir, dir = atan2((next - cur).Y(), (next - cur).X());
171 double angle = 0.0;
172
173 // See http://freetype.sourceforge.net/freetype2/docs/glyphs/glyphs-6.html
174 // for a full description of FreeType tags.
175 for(unsigned int i = 0; i < n; i++)
176 {
177 prev = cur;
178 cur = next;
179 next = FTPoint(contour[(i + 1) % n]);
180 olddir = dir;
181 dir = atan2((next - cur).Y(), (next - cur).X());
182
183 // Compute our path's new direction.
184 double t = dir - olddir;
185 if(t < -M_PI) t += 2 * M_PI;
186 if(t > M_PI) t -= 2 * M_PI;
187 angle += t;
188
189 // Only process point tags we know.
190 if(n < 2 || FT_CURVE_TAG(tags[i]) == FT_Curve_Tag_On)
191 {
192 AddPoint(cur);
193 }
194 else if(FT_CURVE_TAG(tags[i]) == FT_Curve_Tag_Conic)
195 {
196 FTPoint prev2 = prev, next2 = next;
197
198 // Previous point is either the real previous point (an "on"
199 // point), or the midpoint between the current one and the
200 // previous "conic off" point.
201 if(FT_CURVE_TAG(tags[(i - 1 + n) % n]) == FT_Curve_Tag_Conic)
202 {
203 prev2 = (cur + prev) * 0.5;
204 AddPoint(prev2);
205 }
206
207 // Next point is either the real next point or the midpoint.
208 if(FT_CURVE_TAG(tags[(i + 1) % n]) == FT_Curve_Tag_Conic)
209 {
210 next2 = (cur + next) * 0.5;
211 }
212
213 evaluateQuadraticCurve(prev2, cur, next2);
214 }
215 else if(FT_CURVE_TAG(tags[i]) == FT_Curve_Tag_Cubic
216 && FT_CURVE_TAG(tags[(i + 1) % n]) == FT_Curve_Tag_Cubic)
217 {
218 evaluateCubicCurve(prev, cur, next,
219 FTPoint(contour[(i + 2) % n]));
220 }
221 }
222
223 // If final angle is positive (+2PI), it's an anti-clockwise contour,
224 // otherwise (-2PI) it's clockwise.
225 clockwise = (angle < 0.0);
226 }
227
228
buildFrontOutset(float outset)229 void FTContour::buildFrontOutset(float outset)
230 {
231 for(size_t i = 0; i < PointCount(); ++i)
232 {
233 AddFrontPoint(Point(i) + Outset(i) * outset);
234 }
235 }
236
237
buildBackOutset(float outset)238 void FTContour::buildBackOutset(float outset)
239 {
240 for(size_t i = 0; i < PointCount(); ++i)
241 {
242 AddBackPoint(Point(i) + Outset(i) * outset);
243 }
244 }
245
246