SkReduceOrder.cpp revision 277c3f87656c44e0a651ed0dd56efa16c0ab07b4 
1/*
2 * Copyright 2012 Google Inc.
3 *
4 * Use of this source code is governed by a BSD-style license that can be
5 * found in the LICENSE file.
6 */
7#include "SkReduceOrder.h"
8
9int SkReduceOrder::reduce(const SkDLine& line) {
10    fLine[0] = line[0];
11    int different = line[0] != line[1];
12    fLine[1] = line[different];
13    return 1 + different;
14}
15
16static double interp_quad_coords(double a, double b, double c, double t) {
17    double ab = SkDInterp(a, b, t);
18    double bc = SkDInterp(b, c, t);
19    return SkDInterp(ab, bc, t);
20}
21
22static int coincident_line(const SkDQuad& quad, SkDQuad& reduction) {
23    reduction[0] = reduction[1] = quad[0];
24    return 1;
25}
26
27static int reductionLineCount(const SkDQuad& reduction) {
28    return 1 + !reduction[0].approximatelyEqual(reduction[1]);
29}
30
31static int vertical_line(const SkDQuad& quad, SkReduceOrder::Style reduceStyle,
32        SkDQuad& reduction) {
33    double tValue;
34    reduction[0] = quad[0];
35    reduction[1] = quad[2];
36    if (reduceStyle == SkReduceOrder::kFill_Style) {
37        return reductionLineCount(reduction);
38    }
39    int smaller = reduction[1].fY > reduction[0].fY;
40    int larger = smaller ^ 1;
41    if (SkDQuad::FindExtrema(quad[0].fY, quad[1].fY, quad[2].fY, &tValue)) {
42        double yExtrema = interp_quad_coords(quad[0].fY, quad[1].fY, quad[2].fY, tValue);
43        if (reduction[smaller].fY > yExtrema) {
44            reduction[smaller].fY = yExtrema;
45        } else if (reduction[larger].fY < yExtrema) {
46            reduction[larger].fY = yExtrema;
47        }
48    }
49    return reductionLineCount(reduction);
50}
51
52static int horizontal_line(const SkDQuad& quad, SkReduceOrder::Style reduceStyle,
53        SkDQuad& reduction) {
54    double tValue;
55    reduction[0] = quad[0];
56    reduction[1] = quad[2];
57    if (reduceStyle == SkReduceOrder::kFill_Style) {
58        return reductionLineCount(reduction);
59    }
60    int smaller = reduction[1].fX > reduction[0].fX;
61    int larger = smaller ^ 1;
62    if (SkDQuad::FindExtrema(quad[0].fX, quad[1].fX, quad[2].fX, &tValue)) {
63        double xExtrema = interp_quad_coords(quad[0].fX, quad[1].fX, quad[2].fX, tValue);
64        if (reduction[smaller].fX > xExtrema) {
65            reduction[smaller].fX = xExtrema;
66        }  else if (reduction[larger].fX < xExtrema) {
67            reduction[larger].fX = xExtrema;
68        }
69    }
70    return reductionLineCount(reduction);
71}
72
73static int check_linear(const SkDQuad& quad, SkReduceOrder::Style reduceStyle,
74        int minX, int maxX, int minY, int maxY, SkDQuad& reduction) {
75    int startIndex = 0;
76    int endIndex = 2;
77    while (quad[startIndex].approximatelyEqual(quad[endIndex])) {
78        --endIndex;
79        if (endIndex == 0) {
80            SkDebugf("%s shouldn't get here if all four points are about equal", __FUNCTION__);
81            SkASSERT(0);
82        }
83    }
84    if (!quad.isLinear(startIndex, endIndex)) {
85        return 0;
86    }
87    // four are colinear: return line formed by outside
88    reduction[0] = quad[0];
89    reduction[1] = quad[2];
90    if (reduceStyle == SkReduceOrder::kFill_Style) {
91        return reductionLineCount(reduction);
92    }
93    int sameSide;
94    bool useX = quad[maxX].fX - quad[minX].fX >= quad[maxY].fY - quad[minY].fY;
95    if (useX) {
96        sameSide = SkDSign(quad[0].fX - quad[1].fX) + SkDSign(quad[2].fX - quad[1].fX);
97    } else {
98        sameSide = SkDSign(quad[0].fY - quad[1].fY) + SkDSign(quad[2].fY - quad[1].fY);
99    }
100    if ((sameSide & 3) != 2) {
101        return reductionLineCount(reduction);
102    }
103    double tValue;
104    int root;
105    if (useX) {
106        root = SkDQuad::FindExtrema(quad[0].fX, quad[1].fX, quad[2].fX, &tValue);
107    } else {
108        root = SkDQuad::FindExtrema(quad[0].fY, quad[1].fY, quad[2].fY, &tValue);
109    }
110    if (root) {
111        SkDPoint extrema;
112        extrema.fX = interp_quad_coords(quad[0].fX, quad[1].fX, quad[2].fX, tValue);
113        extrema.fY = interp_quad_coords(quad[0].fY, quad[1].fY, quad[2].fY, tValue);
114        // sameSide > 0 means mid is smaller than either [0] or [2], so replace smaller
115        int replace;
116        if (useX) {
117            if ((extrema.fX < quad[0].fX) ^ (extrema.fX < quad[2].fX)) {
118                return reductionLineCount(reduction);
119            }
120            replace = ((extrema.fX < quad[0].fX) | (extrema.fX < quad[2].fX))
121                    ^ (quad[0].fX < quad[2].fX);
122        } else {
123            if ((extrema.fY < quad[0].fY) ^ (extrema.fY < quad[2].fY)) {
124                return reductionLineCount(reduction);
125            }
126            replace = ((extrema.fY < quad[0].fY) | (extrema.fY < quad[2].fY))
127                    ^ (quad[0].fY < quad[2].fY);
128        }
129        reduction[replace] = extrema;
130    }
131    return reductionLineCount(reduction);
132}
133
134// reduce to a quadratic or smaller
135// look for identical points
136// look for all four points in a line
137    // note that three points in a line doesn't simplify a cubic
138// look for approximation with single quadratic
139    // save approximation with multiple quadratics for later
140int SkReduceOrder::reduce(const SkDQuad& quad, Style reduceStyle) {
141    int index, minX, maxX, minY, maxY;
142    int minXSet, minYSet;
143    minX = maxX = minY = maxY = 0;
144    minXSet = minYSet = 0;
145    for (index = 1; index < 3; ++index) {
146        if (quad[minX].fX > quad[index].fX) {
147            minX = index;
148        }
149        if (quad[minY].fY > quad[index].fY) {
150            minY = index;
151        }
152        if (quad[maxX].fX < quad[index].fX) {
153            maxX = index;
154        }
155        if (quad[maxY].fY < quad[index].fY) {
156            maxY = index;
157        }
158    }
159    for (index = 0; index < 3; ++index) {
160        if (AlmostEqualUlps(quad[index].fX, quad[minX].fX)) {
161            minXSet |= 1 << index;
162        }
163        if (AlmostEqualUlps(quad[index].fY, quad[minY].fY)) {
164            minYSet |= 1 << index;
165        }
166    }
167    if (minXSet == 0x7) {  // test for vertical line
168        if (minYSet == 0x7) {  // return 1 if all four are coincident
169            return coincident_line(quad, fQuad);
170        }
171        return vertical_line(quad, reduceStyle, fQuad);
172    }
173    if (minYSet == 0xF) {  // test for horizontal line
174        return horizontal_line(quad, reduceStyle, fQuad);
175    }
176    int result = check_linear(quad, reduceStyle, minX, maxX, minY, maxY, fQuad);
177    if (result) {
178        return result;
179    }
180    fQuad = quad;
181    return 3;
182}
183
184////////////////////////////////////////////////////////////////////////////////////
185
186static double interp_cubic_coords(const double* src, double t) {
187    double ab = SkDInterp(src[0], src[2], t);
188    double bc = SkDInterp(src[2], src[4], t);
189    double cd = SkDInterp(src[4], src[6], t);
190    double abc = SkDInterp(ab, bc, t);
191    double bcd = SkDInterp(bc, cd, t);
192    return SkDInterp(abc, bcd, t);
193}
194
195static int coincident_line(const SkDCubic& cubic, SkDCubic& reduction) {
196    reduction[0] = reduction[1] = cubic[0];
197    return 1;
198}
199
200static int reductionLineCount(const SkDCubic& reduction) {
201    return 1 + !reduction[0].approximatelyEqual(reduction[1]);
202}
203
204static int vertical_line(const SkDCubic& cubic, SkReduceOrder::Style reduceStyle,
205                         SkDCubic& reduction) {
206    double tValues[2];
207    reduction[0] = cubic[0];
208    reduction[1] = cubic[3];
209    if (reduceStyle == SkReduceOrder::kFill_Style) {
210        return reductionLineCount(reduction);
211    }
212    int smaller = reduction[1].fY > reduction[0].fY;
213    int larger = smaller ^ 1;
214    int roots = SkDCubic::FindExtrema(cubic[0].fY, cubic[1].fY, cubic[2].fY, cubic[3].fY, tValues);
215    for (int index = 0; index < roots; ++index) {
216        double yExtrema = interp_cubic_coords(&cubic[0].fY, tValues[index]);
217        if (reduction[smaller].fY > yExtrema) {
218            reduction[smaller].fY = yExtrema;
219            continue;
220        }
221        if (reduction[larger].fY < yExtrema) {
222            reduction[larger].fY = yExtrema;
223        }
224    }
225    return reductionLineCount(reduction);
226}
227
228static int horizontal_line(const SkDCubic& cubic, SkReduceOrder::Style reduceStyle,
229                           SkDCubic& reduction) {
230    double tValues[2];
231    reduction[0] = cubic[0];
232    reduction[1] = cubic[3];
233    if (reduceStyle == SkReduceOrder::kFill_Style) {
234        return reductionLineCount(reduction);
235    }
236    int smaller = reduction[1].fX > reduction[0].fX;
237    int larger = smaller ^ 1;
238    int roots = SkDCubic::FindExtrema(cubic[0].fX, cubic[1].fX, cubic[2].fX, cubic[3].fX, tValues);
239    for (int index = 0; index < roots; ++index) {
240        double xExtrema = interp_cubic_coords(&cubic[0].fX, tValues[index]);
241        if (reduction[smaller].fX > xExtrema) {
242            reduction[smaller].fX = xExtrema;
243            continue;
244        }
245        if (reduction[larger].fX < xExtrema) {
246            reduction[larger].fX = xExtrema;
247        }
248    }
249    return reductionLineCount(reduction);
250}
251
252// check to see if it is a quadratic or a line
253static int check_quadratic(const SkDCubic& cubic, SkDCubic& reduction) {
254    double dx10 = cubic[1].fX - cubic[0].fX;
255    double dx23 = cubic[2].fX - cubic[3].fX;
256    double midX = cubic[0].fX + dx10 * 3 / 2;
257    double sideAx = midX - cubic[3].fX;
258    double sideBx = dx23 * 3 / 2;
259    if (approximately_zero(sideAx) ? !approximately_equal(sideAx, sideBx)
260            : !AlmostEqualUlps(sideAx, sideBx)) {
261        return 0;
262    }
263    double dy10 = cubic[1].fY - cubic[0].fY;
264    double dy23 = cubic[2].fY - cubic[3].fY;
265    double midY = cubic[0].fY + dy10 * 3 / 2;
266    double sideAy = midY - cubic[3].fY;
267    double sideBy = dy23 * 3 / 2;
268    if (approximately_zero(sideAy) ? !approximately_equal(sideAy, sideBy)
269            : !AlmostEqualUlps(sideAy, sideBy)) {
270        return 0;
271    }
272    reduction[0] = cubic[0];
273    reduction[1].fX = midX;
274    reduction[1].fY = midY;
275    reduction[2] = cubic[3];
276    return 3;
277}
278
279static int check_linear(const SkDCubic& cubic, SkReduceOrder::Style reduceStyle,
280        int minX, int maxX, int minY, int maxY, SkDCubic& reduction) {
281    int startIndex = 0;
282    int endIndex = 3;
283    while (cubic[startIndex].approximatelyEqual(cubic[endIndex])) {
284        --endIndex;
285        if (endIndex == 0) {
286            SkDebugf("%s shouldn't get here if all four points are about equal\n", __FUNCTION__);
287            SkASSERT(0);
288        }
289    }
290    if (!cubic.isLinear(startIndex, endIndex)) {
291        return 0;
292    }
293    // four are colinear: return line formed by outside
294    reduction[0] = cubic[0];
295    reduction[1] = cubic[3];
296    if (reduceStyle == SkReduceOrder::kFill_Style) {
297        return reductionLineCount(reduction);
298    }
299    int sameSide1;
300    int sameSide2;
301    bool useX = cubic[maxX].fX - cubic[minX].fX >= cubic[maxY].fY - cubic[minY].fY;
302    if (useX) {
303        sameSide1 = SkDSign(cubic[0].fX - cubic[1].fX) + SkDSign(cubic[3].fX - cubic[1].fX);
304        sameSide2 = SkDSign(cubic[0].fX - cubic[2].fX) + SkDSign(cubic[3].fX - cubic[2].fX);
305    } else {
306        sameSide1 = SkDSign(cubic[0].fY - cubic[1].fY) + SkDSign(cubic[3].fY - cubic[1].fY);
307        sameSide2 = SkDSign(cubic[0].fY - cubic[2].fY) + SkDSign(cubic[3].fY - cubic[2].fY);
308    }
309    if (sameSide1 == sameSide2 && (sameSide1 & 3) != 2) {
310        return reductionLineCount(reduction);
311    }
312    double tValues[2];
313    int roots;
314    if (useX) {
315        roots = SkDCubic::FindExtrema(cubic[0].fX, cubic[1].fX, cubic[2].fX, cubic[3].fX, tValues);
316    } else {
317        roots = SkDCubic::FindExtrema(cubic[0].fY, cubic[1].fY, cubic[2].fY, cubic[3].fY, tValues);
318    }
319    for (int index = 0; index < roots; ++index) {
320        SkDPoint extrema;
321        extrema.fX = interp_cubic_coords(&cubic[0].fX, tValues[index]);
322        extrema.fY = interp_cubic_coords(&cubic[0].fY, tValues[index]);
323        // sameSide > 0 means mid is smaller than either [0] or [3], so replace smaller
324        int replace;
325        if (useX) {
326            if ((extrema.fX < cubic[0].fX) ^ (extrema.fX < cubic[3].fX)) {
327                continue;
328            }
329            replace = ((extrema.fX < cubic[0].fX) | (extrema.fX < cubic[3].fX))
330                    ^ (cubic[0].fX < cubic[3].fX);
331        } else {
332            if ((extrema.fY < cubic[0].fY) ^ (extrema.fY < cubic[3].fY)) {
333                continue;
334            }
335            replace = ((extrema.fY < cubic[0].fY) | (extrema.fY < cubic[3].fY))
336                    ^ (cubic[0].fY < cubic[3].fY);
337        }
338        reduction[replace] = extrema;
339    }
340    return reductionLineCount(reduction);
341}
342
343/* food for thought:
344http://objectmix.com/graphics/132906-fast-precision-driven-cubic-quadratic-piecewise-degree-reduction-algos-2-a.html
345
346Given points c1, c2, c3 and c4 of a cubic Bezier, the points of the
347corresponding quadratic Bezier are (given in convex combinations of
348points):
349
350q1 = (11/13)c1 + (3/13)c2 -(3/13)c3 + (2/13)c4
351q2 = -c1 + (3/2)c2 + (3/2)c3 - c4
352q3 = (2/13)c1 - (3/13)c2 + (3/13)c3 + (11/13)c4
353
354Of course, this curve does not interpolate the end-points, but it would
355be interesting to see the behaviour of such a curve in an applet.
356
357--
358Kalle Rutanen
359http://kaba.hilvi.org
360
361*/
362
363// reduce to a quadratic or smaller
364// look for identical points
365// look for all four points in a line
366    // note that three points in a line doesn't simplify a cubic
367// look for approximation with single quadratic
368    // save approximation with multiple quadratics for later
369int SkReduceOrder::reduce(const SkDCubic& cubic, Quadratics allowQuadratics,
370        Style reduceStyle) {
371    int index, minX, maxX, minY, maxY;
372    int minXSet, minYSet;
373    minX = maxX = minY = maxY = 0;
374    minXSet = minYSet = 0;
375    for (index = 1; index < 4; ++index) {
376        if (cubic[minX].fX > cubic[index].fX) {
377            minX = index;
378        }
379        if (cubic[minY].fY > cubic[index].fY) {
380            minY = index;
381        }
382        if (cubic[maxX].fX < cubic[index].fX) {
383            maxX = index;
384        }
385        if (cubic[maxY].fY < cubic[index].fY) {
386            maxY = index;
387        }
388    }
389    for (index = 0; index < 4; ++index) {
390        double cx = cubic[index].fX;
391        double cy = cubic[index].fY;
392        double denom = SkTMax(fabs(cx), SkTMax(fabs(cy),
393                SkTMax(fabs(cubic[minX].fX), fabs(cubic[minY].fY))));
394        if (denom == 0) {
395            minXSet |= 1 << index;
396            minYSet |= 1 << index;
397            continue;
398        }
399        double inv = 1 / denom;
400        if (approximately_equal_half(cx * inv, cubic[minX].fX * inv)) {
401            minXSet |= 1 << index;
402        }
403        if (approximately_equal_half(cy * inv, cubic[minY].fY * inv)) {
404            minYSet |= 1 << index;
405        }
406    }
407    if (minXSet == 0xF) {  // test for vertical line
408        if (minYSet == 0xF) {  // return 1 if all four are coincident
409            return coincident_line(cubic, fCubic);
410        }
411        return vertical_line(cubic, reduceStyle, fCubic);
412    }
413    if (minYSet == 0xF) {  // test for horizontal line
414        return horizontal_line(cubic, reduceStyle, fCubic);
415    }
416    int result = check_linear(cubic, reduceStyle, minX, maxX, minY, maxY, fCubic);
417    if (result) {
418        return result;
419    }
420    if (allowQuadratics == SkReduceOrder::kAllow_Quadratics
421            && (result = check_quadratic(cubic, fCubic))) {
422        return result;
423    }
424    fCubic = cubic;
425    return 4;
426}
427
428SkPath::Verb SkReduceOrder::Quad(const SkPoint a[3], SkTDArray<SkPoint>* reducePts) {
429    SkDQuad quad;
430    quad.set(a);
431    SkReduceOrder reducer;
432    int order = reducer.reduce(quad, kFill_Style);
433    if (order == 2) {  // quad became line
434        for (int index = 0; index < order; ++index) {
435            SkPoint* pt = reducePts->append();
436            pt->fX = SkDoubleToScalar(reducer.fLine[index].fX);
437            pt->fY = SkDoubleToScalar(reducer.fLine[index].fY);
438        }
439    }
440    return SkPathOpsPointsToVerb(order - 1);
441}
442
443SkPath::Verb SkReduceOrder::Cubic(const SkPoint a[4], SkTDArray<SkPoint>* reducePts) {
444    SkDCubic cubic;
445    cubic.set(a);
446    SkReduceOrder reducer;
447    int order = reducer.reduce(cubic, kAllow_Quadratics, kFill_Style);
448    if (order == 2 || order == 3) {  // cubic became line or quad
449        for (int index = 0; index < order; ++index) {
450            SkPoint* pt = reducePts->append();
451            pt->fX = SkDoubleToScalar(reducer.fQuad[index].fX);
452            pt->fY = SkDoubleToScalar(reducer.fQuad[index].fY);
453        }
454    }
455    return SkPathOpsPointsToVerb(order - 1);
456}
457