Chromium Code Reviews
chromiumcodereview-hr@appspot.gserviceaccount.com (chromiumcodereview-hr) | Please choose your nickname with Settings | Help | Chromium Project | Gerrit Changes | Sign out
(123)

Side by Side Diff: src/pathops/SkDCubicToQuads.cpp

Issue 14034014: path ops -- use standard SkTQSort (Closed) Base URL: http://skia.googlecode.com/svn/trunk/
Patch Set: Created 7 years, 8 months ago
Use n/p to move between diff chunks; N/P to move between comments. Draft comments are only viewable by you.
Jump to:
View unified diff | Download patch | Annotate | Revision Log
OLDNEW
1 /* 1 /*
2 http://stackoverflow.com/questions/2009160/how-do-i-convert-the-2-control-points -of-a-cubic-curve-to-the-single-control-poi 2 http://stackoverflow.com/questions/2009160/how-do-i-convert-the-2-control-points -of-a-cubic-curve-to-the-single-control-poi
3 */ 3 */
4 4
5 /* 5 /*
6 Let's call the control points of the cubic Q0..Q3 and the control points of the quadratic P0..P2. 6 Let's call the control points of the cubic Q0..Q3 and the control points of the quadratic P0..P2.
7 Then for degree elevation, the equations are: 7 Then for degree elevation, the equations are:
8 8
9 Q0 = P0 9 Q0 = P0
10 Q1 = 1/3 P0 + 2/3 P1 10 Q1 = 1/3 P0 + 2/3 P1
(...skipping 32 matching lines...) Expand 10 before | Expand all | Expand 10 after
43 // maybe in turn derived from http://www.cccg.ca/proceedings/2004/36.pdf 43 // maybe in turn derived from http://www.cccg.ca/proceedings/2004/36.pdf
44 // also stored at http://www.cis.usouthal.edu/~hain/general/Publications/Bezier/ bezier%20cccg04%20paper.pdf 44 // also stored at http://www.cis.usouthal.edu/~hain/general/Publications/Bezier/ bezier%20cccg04%20paper.pdf
45 45
46 */ 46 */
47 47
48 #include "SkPathOpsCubic.h" 48 #include "SkPathOpsCubic.h"
49 #include "SkPathOpsLine.h" 49 #include "SkPathOpsLine.h"
50 #include "SkPathOpsQuad.h" 50 #include "SkPathOpsQuad.h"
51 #include "SkReduceOrder.h" 51 #include "SkReduceOrder.h"
52 #include "SkTDArray.h" 52 #include "SkTDArray.h"
53 #include "TSearch.h" 53 #include "SkTSort.h"
54 54
55 #define USE_CUBIC_END_POINTS 1 55 #define USE_CUBIC_END_POINTS 1
56 56
57 static double calc_t_div(const SkDCubic& cubic, double precision, double start) { 57 static double calc_t_div(const SkDCubic& cubic, double precision, double start) {
58 const double adjust = sqrt(3.) / 36; 58 const double adjust = sqrt(3.) / 36;
59 SkDCubic sub; 59 SkDCubic sub;
60 const SkDCubic* cPtr; 60 const SkDCubic* cPtr;
61 if (start == 0) { 61 if (start == 0) {
62 cPtr = &cubic; 62 cPtr = &cubic;
63 } else { 63 } else {
(...skipping 58 matching lines...) Expand 10 before | Expand all | Expand 10 after
122 if (order < 3) { 122 if (order < 3) {
123 return; 123 return;
124 } 124 }
125 double inflectT[5]; 125 double inflectT[5];
126 int inflections = findInflections(inflectT); 126 int inflections = findInflections(inflectT);
127 SkASSERT(inflections <= 2); 127 SkASSERT(inflections <= 2);
128 if (!endsAreExtremaInXOrY()) { 128 if (!endsAreExtremaInXOrY()) {
129 inflections += findMaxCurvature(&inflectT[inflections]); 129 inflections += findMaxCurvature(&inflectT[inflections]);
130 SkASSERT(inflections <= 5); 130 SkASSERT(inflections <= 5);
131 } 131 }
132 QSort<double>(inflectT, &inflectT[inflections - 1]); 132 SkTQSort<double>(inflectT, &inflectT[inflections - 1]);
133 // OPTIMIZATION: is this filtering common enough that it needs to be pulled out into its 133 // OPTIMIZATION: is this filtering common enough that it needs to be pulled out into its
134 // own subroutine? 134 // own subroutine?
135 while (inflections && approximately_less_than_zero(inflectT[0])) { 135 while (inflections && approximately_less_than_zero(inflectT[0])) {
136 memmove(inflectT, &inflectT[1], sizeof(inflectT[0]) * --inflections); 136 memmove(inflectT, &inflectT[1], sizeof(inflectT[0]) * --inflections);
137 } 137 }
138 int start = 0; 138 int start = 0;
139 do { 139 do {
140 int next = start + 1; 140 int next = start + 1;
141 if (next >= inflections) { 141 if (next >= inflections) {
142 break; 142 break;
(...skipping 38 matching lines...) Expand 10 before | Expand all | Expand 10 after
181 for (int idx = 0; idx < last; ++idx) { 181 for (int idx = 0; idx < last; ++idx) {
182 part = subDivide(inflectT[idx], inflectT[idx + 1]); 182 part = subDivide(inflectT[idx], inflectT[idx + 1]);
183 addTs(part, precision, inflectT[idx], inflectT[idx + 1], ts); 183 addTs(part, precision, inflectT[idx], inflectT[idx + 1], ts);
184 } 184 }
185 part = subDivide(inflectT[last], 1); 185 part = subDivide(inflectT[last], 1);
186 addTs(part, precision, inflectT[last], 1, ts); 186 addTs(part, precision, inflectT[last], 1, ts);
187 return; 187 return;
188 } 188 }
189 addTs(*this, precision, 0, 1, ts); 189 addTs(*this, precision, 0, 1, ts);
190 } 190 }
OLDNEW

Powered by Google App Engine
This is Rietveld 408576698