1 /*
2 * Copyright 2015 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 "include/core/SkPoint.h"
8 #include "include/core/SkScalar.h"
9 #include "include/core/SkTypes.h"
10 #include "src/core/SkGeometry.h"
11 #include "src/pathops/SkIntersections.h"
12 #include "src/pathops/SkPathOpsConic.h"
13 #include "src/pathops/SkPathOpsPoint.h"
14 #include "src/pathops/SkPathOpsQuad.h"
15 #include "src/pathops/SkPathOpsTypes.h"
16 #include "tests/PathOpsTestCommon.h"
17 #include "tests/Test.h"
18
19 #include <array>
20
21 /*
22 manually compute the intersection of a pair of circles and see if the conic intersection matches
23 given two circles
24 construct a line connecting their centers
25
26 */
27
28 static const ConicPts testSet[] = {
29 {{{{306.588013,-227.983994}, {212.464996,-262.242004}, {95.5512009,58.9763985}}}, 0.707107008f},
30 {{{{377.218994,-141.981003}, {40.578701,-201.339996}, {23.1854992,-102.697998}}}, 0.707107008f},
31
32 {{{{5.1114602088928223, 628.77813720703125},
33 {10.834027290344238, 988.964111328125},
34 {163.40835571289062, 988.964111328125}}}, 0.72944212f},
35 {{{{163.40835571289062, 988.964111328125},
36 {5, 988.964111328125},
37 {5, 614.7423095703125}}}, 0.707106769f},
38
39 {{{{11.17222976684570312, -8.103978157043457031},
40 {22.91432571411132812, -10.37866020202636719},
41 {23.7764129638671875, -7.725424289703369141}}}, 1.00862849f},
42 {{{{-1.545085430145263672, -4.755282402038574219},
43 {22.23132705688476562, -12.48070907592773438},
44 {23.7764129638671875, -7.725427150726318359}}}, 0.707106769f},
45
46 {{{{-4,1}, {-4,5}, {0,5}}}, 0.707106769f},
47 {{{{-3,4}, {-3,1}, {0,1}}}, 0.707106769f},
48
49 {{{{0, 0}, {0, 1}, {1, 1}}}, 0.5f},
50 {{{{1, 0}, {0, 0}, {0, 1}}}, 0.5f},
51
52 };
53
54 const int testSetCount = (int) std::size(testSet);
55
chopCompare(const SkConic chopped[2],const SkDConic dChopped[2])56 static void chopCompare(const SkConic chopped[2], const SkDConic dChopped[2]) {
57 SkASSERT(roughly_equal(chopped[0].fW, dChopped[0].fWeight));
58 SkASSERT(roughly_equal(chopped[1].fW, dChopped[1].fWeight));
59 for (int cIndex = 0; cIndex < 2; ++cIndex) {
60 for (int pIndex = 0; pIndex < 3; ++pIndex) {
61 SkDPoint up;
62 up.set(chopped[cIndex].fPts[pIndex]);
63 SkASSERT(dChopped[cIndex].fPts[pIndex].approximatelyEqual(up));
64 }
65 }
66 #if DEBUG_VISUALIZE_CONICS
67 dChopped[0].dump();
68 dChopped[1].dump();
69 #endif
70 }
71
72 #define DEBUG_VISUALIZE_CONICS 0
73
74 #if DEBUG_VISUALIZE_CONICS
75 #include "include/core/SkBitmap.h"
76 #include "include/core/SkCanvas.h"
77 #include "include/core/SkPaint.h"
78 #include "include/core/SkString.h"
79 #include "src/pathops/SkPathOpsRect.h"
80
writePng(const SkConic & c,const SkConic ch[2],const char * name)81 static void writePng(const SkConic& c, const SkConic ch[2], const char* name) {
82 const int scale = 10;
83 SkConic conic, chopped[2];
84 for (int index = 0; index < 3; ++index) {
85 conic.fPts[index].fX = c.fPts[index].fX * scale;
86 conic.fPts[index].fY = c.fPts[index].fY * scale;
87 for (int chIndex = 0; chIndex < 2; ++chIndex) {
88 chopped[chIndex].fPts[index].fX = ch[chIndex].fPts[index].fX * scale;
89 chopped[chIndex].fPts[index].fY = ch[chIndex].fPts[index].fY * scale;
90 }
91 }
92 conic.fW = c.fW;
93 chopped[0].fW = ch[0].fW;
94 chopped[1].fW = ch[1].fW;
95 SkBitmap bitmap;
96 SkRect bounds;
97 conic.computeTightBounds(&bounds);
98 bounds.outset(10, 10);
99 bitmap.tryAllocPixels(SkImageInfo::MakeN32Premul(
100 SkScalarRoundToInt(bounds.width()), SkScalarRoundToInt(bounds.height())));
101 SkCanvas canvas(bitmap);
102 SkPaint paint;
103 paint.setAntiAlias(true);
104 paint.setStyle(SkPaint::kStroke_Style);
105 canvas.translate(-bounds.fLeft, -bounds.fTop);
106 canvas.drawColor(SK_ColorWHITE);
107 SkPath path;
108 path.moveTo(conic.fPts[0]);
109 path.conicTo(conic.fPts[1], conic.fPts[2], conic.fW);
110 paint.setARGB(0x80, 0xFF, 0, 0);
111 canvas.drawPath(path, paint);
112 path.reset();
113 path.moveTo(chopped[0].fPts[0]);
114 path.conicTo(chopped[0].fPts[1], chopped[0].fPts[2], chopped[0].fW);
115 path.moveTo(chopped[1].fPts[0]);
116 path.conicTo(chopped[1].fPts[1], chopped[1].fPts[2], chopped[1].fW);
117 paint.setARGB(0x80, 0, 0, 0xFF);
118 canvas.drawPath(path, paint);
119 SkString filename("c:\\Users\\caryclark\\Documents\\");
120 filename.appendf("%s.png", name);
121 ToolUtils::EncodeImageToPngFile(filename.c_str(), bitmap);
122 }
123
writeDPng(const SkDConic & dC,const char * name)124 static void writeDPng(const SkDConic& dC, const char* name) {
125 const int scale = 5;
126 SkDConic dConic = {{{ {dC.fPts[0].fX * scale, dC.fPts[0].fY * scale },
127 {dC.fPts[1].fX * scale, dC.fPts[1].fY * scale },
128 {dC.fPts[2].fX * scale, dC.fPts[2].fY * scale }}}, dC.fWeight };
129 SkBitmap bitmap;
130 SkDRect bounds;
131 bounds.setBounds(dConic);
132 bounds.fLeft -= 10;
133 bounds.fTop -= 10;
134 bounds.fRight += 10;
135 bounds.fBottom += 10;
136 bitmap.tryAllocPixels(SkImageInfo::MakeN32Premul(
137 SkScalarRoundToInt(SkDoubleToScalar(bounds.width())),
138 SkScalarRoundToInt(SkDoubleToScalar(bounds.height()))));
139 SkCanvas canvas(bitmap);
140 SkPaint paint;
141 paint.setAntiAlias(true);
142 paint.setStyle(SkPaint::kStroke_Style);
143 canvas.translate(SkDoubleToScalar(-bounds.fLeft), SkDoubleToScalar(-bounds.fTop));
144 canvas.drawColor(SK_ColorWHITE);
145 SkPath path;
146 path.moveTo(dConic.fPts[0].asSkPoint());
147 path.conicTo(dConic.fPts[1].asSkPoint(), dConic.fPts[2].asSkPoint(), dConic.fWeight);
148 paint.setARGB(0x80, 0xFF, 0, 0);
149 canvas.drawPath(path, paint);
150 path.reset();
151 const int chops = 2;
152 for (int tIndex = 0; tIndex < chops; ++tIndex) {
153 SkDConic chopped = dConic.subDivide(tIndex / (double) chops,
154 (tIndex + 1) / (double) chops);
155 path.moveTo(chopped.fPts[0].asSkPoint());
156 path.conicTo(chopped.fPts[1].asSkPoint(), chopped.fPts[2].asSkPoint(), chopped.fWeight);
157 }
158 paint.setARGB(0x80, 0, 0, 0xFF);
159 canvas.drawPath(path, paint);
160 SkString filename("c:\\Users\\caryclark\\Documents\\");
161 filename.appendf("%s.png", name);
162 ToolUtils::EncodeImageToPngFile(filename.c_str(), bitmap);
163 }
164 #endif
165
chopBothWays(const SkDConic & dConic,double t,const char * name)166 static void chopBothWays(const SkDConic& dConic, double t, const char* name) {
167 SkConic conic;
168 for (int index = 0; index < 3; ++index) {
169 conic.fPts[index] = dConic.fPts[index].asSkPoint();
170 }
171 conic.fW = dConic.fWeight;
172 SkConic chopped[2];
173 SkDConic dChopped[2];
174 if (!conic.chopAt(SkDoubleToScalar(t), chopped)) {
175 return;
176 }
177 dChopped[0] = dConic.subDivide(0, t);
178 dChopped[1] = dConic.subDivide(t, 1);
179 #if DEBUG_VISUALIZE_CONICS
180 dConic.dump();
181 #endif
182 chopCompare(chopped, dChopped);
183 #if DEBUG_VISUALIZE_CONICS
184 writePng(conic, chopped, name);
185 #endif
186 }
187
188 #if DEBUG_VISUALIZE_CONICS
189 const SkDConic frame0[] = {
190 {{{{306.588013,-227.983994}, {212.464996,-262.242004}, {95.5512009,58.9763985}}}, 0.707107008f},
191 {{{{377.218994,-141.981003}, {40.578701,-201.339996}, {23.1854992,-102.697998}}}, 0.707107008f},
192 };
193
194 const SkDConic frame1[] = {
195 {{{{377.218994,-141.981003}, {40.578701,-201.339996}, {23.1854992,-102.697998}}}, 0.707107008f},
196 {{{{306.58801299999999, -227.983994}, {212.46499600000001, -262.24200400000001}, {95.551200899999998, 58.976398500000002}}}, 0.707107008f},
197 {{{{377.21899400000001, -141.98100299999999}, {237.77799285476553, -166.56830755921084}, {134.08399674208422, -155.06258330544892}}}, 0.788580656f},
198 {{{{134.08399674208422, -155.06258330544892}, {30.390000629402859, -143.55685905168704}, {23.185499199999999, -102.697998}}}, 0.923879623f},
199 };
200
201 const SkDConic frame2[] = {
202 {{{{306.588013,-227.983994}, {212.464996,-262.242004}, {95.5512009,58.9763985}}}, 0.707107008f},
203 {{{{377.218994,-141.981003}, {40.578701,-201.339996}, {23.1854992,-102.697998}}}, 0.707107008f},
204 {{{{205.78973252799028, -158.12538713371103}, {143.97848953841861, -74.076645245042371}, {95.551200899999998, 58.976398500000002}}}, 0.923879623f},
205 {{{{377.21899400000001, -141.98100299999999}, {237.77799285476553, -166.56830755921084}, {134.08399674208422, -155.06258330544892}}}, 0.788580656f},
206 };
207
208 const SkDConic frame3[] = {
209 {{{{306.588013,-227.983994}, {212.464996,-262.242004}, {95.5512009,58.9763985}}}, 0.707107008f},
210 {{{{377.218994,-141.981003}, {40.578701,-201.339996}, {23.1854992,-102.697998}}}, 0.707107008f},
211 {{{{205.78973252799028, -158.12538713371103}, {143.97848953841861, -74.076645245042371}, {95.551200899999998, 58.976398500000002}}}, 0.923879623f},
212 {{{{252.08225670812539, -156.90491625851064}, {185.93099479842493, -160.81544543232982}, {134.08399674208422, -155.06258330544892}}}, 0.835816324f},
213 };
214
215 const SkDConic frame4[] = {
216 {{{{306.588013,-227.983994}, {212.464996,-262.242004}, {95.5512009,58.9763985}}}, 0.707107008f},
217 {{{{377.218994,-141.981003}, {40.578701,-201.339996}, {23.1854992,-102.697998}}}, 0.707107008f},
218 {{{{205.78973252799028, -158.12538713371103}, {174.88411103320448, -116.10101618937664}, {145.19509369736275, -56.857102571363754}}}, 0.871667147f},
219 {{{{252.08225670812539, -156.90491625851064}, {185.93099479842493, -160.81544543232982}, {134.08399674208422, -155.06258330544892}}}, 0.835816324f},
220 };
221
222 const SkDConic frame5[] = {
223 {{{{306.588013,-227.983994}, {212.464996,-262.242004}, {95.5512009,58.9763985}}}, 0.707107008f},
224 {{{{377.218994,-141.981003}, {40.578701,-201.339996}, {23.1854992,-102.697998}}}, 0.707107008f},
225 {{{{205.78973252799028, -158.12538713371103}, {174.88411103320448, -116.10101618937664}, {145.19509369736275, -56.857102571363754}}}, 0.871667147f},
226 {{{{252.08225670812539, -156.90491625851064}, {219.70109133058406, -158.81912754088933}, {190.17095392508796, -158.38373974664466}}}, 0.858306944f},
227 };
228
229 const SkDConic frame6[] = {
230 {{{{306.588013,-227.983994}, {212.464996,-262.242004}, {95.5512009,58.9763985}}}, 0.707107008f},
231 {{{{377.218994,-141.981003}, {40.578701,-201.339996}, {23.1854992,-102.697998}}}, 0.707107008f},
232 {{{{205.78973252799028, -158.12538713371103}, {190.33692178059735, -137.11320166154385}, {174.87004877564593, -111.2132534799228}}}, 0.858117759f},
233 {{{{252.08225670812539, -156.90491625851064}, {219.70109133058406, -158.81912754088933}, {190.17095392508796, -158.38373974664466}}}, 0.858306944f},
234 };
235
236 const SkDConic* frames[] = {
237 frame0, frame1, frame2, frame3, frame4, frame5, frame6
238 };
239
240 const int frameSizes[] = { (int) std::size(frame0), (int) std::size(frame1),
241 (int) std::size(frame2), (int) std::size(frame3),
242 (int) std::size(frame4), (int) std::size(frame5),
243 (int) std::size(frame6),
244 };
245
writeFrames()246 static void writeFrames() {
247 const int scale = 5;
248
249 for (int index = 0; index < (int) std::size(frameSizes); ++index) {
250 SkDRect bounds;
251 bool boundsSet = false;
252 int frameSize = frameSizes[index];
253 for (int fIndex = 0; fIndex < frameSize; ++fIndex) {
254 const SkDConic& dC = frames[index][fIndex];
255 SkDConic dConic = {{{ {dC.fPts[0].fX * scale, dC.fPts[0].fY * scale },
256 {dC.fPts[1].fX * scale, dC.fPts[1].fY * scale },
257 {dC.fPts[2].fX * scale, dC.fPts[2].fY * scale }}}, dC.fWeight };
258 SkDRect dBounds;
259 dBounds.setBounds(dConic);
260 if (!boundsSet) {
261 bounds = dBounds;
262 boundsSet = true;
263 } else {
264 bounds.add((SkDPoint&) dBounds.fLeft);
265 bounds.add((SkDPoint&) dBounds.fRight);
266 }
267 }
268 bounds.fLeft -= 10;
269 bounds.fTop -= 10;
270 bounds.fRight += 10;
271 bounds.fBottom += 10;
272 SkBitmap bitmap;
273 bitmap.tryAllocPixels(SkImageInfo::MakeN32Premul(
274 SkScalarRoundToInt(SkDoubleToScalar(bounds.width())),
275 SkScalarRoundToInt(SkDoubleToScalar(bounds.height()))));
276 SkCanvas canvas(bitmap);
277 SkPaint paint;
278 paint.setAntiAlias(true);
279 paint.setStyle(SkPaint::kStroke_Style);
280 canvas.translate(SkDoubleToScalar(-bounds.fLeft), SkDoubleToScalar(-bounds.fTop));
281 canvas.drawColor(SK_ColorWHITE);
282 for (int fIndex = 0; fIndex < frameSize; ++fIndex) {
283 const SkDConic& dC = frames[index][fIndex];
284 SkDConic dConic = {{{ {dC.fPts[0].fX * scale, dC.fPts[0].fY * scale },
285 {dC.fPts[1].fX * scale, dC.fPts[1].fY * scale },
286 {dC.fPts[2].fX * scale, dC.fPts[2].fY * scale }}}, dC.fWeight };
287 SkPath path;
288 path.moveTo(dConic.fPts[0].asSkPoint());
289 path.conicTo(dConic.fPts[1].asSkPoint(), dConic.fPts[2].asSkPoint(), dConic.fWeight);
290 if (fIndex < 2) {
291 paint.setARGB(0x80, 0xFF, 0, 0);
292 } else {
293 paint.setARGB(0x80, 0, 0, 0xFF);
294 }
295 canvas.drawPath(path, paint);
296 }
297 SkString filename("c:\\Users\\caryclark\\Documents\\");
298 filename.appendf("f%d.png", index);
299 ToolUtils::EncodeImageToPngFile(filename.c_str(), bitmap);
300 }
301 }
302 #endif
303
oneOff(skiatest::Reporter * reporter,const ConicPts & conic1,const ConicPts & conic2,bool coin)304 static void oneOff(skiatest::Reporter* reporter, const ConicPts& conic1, const ConicPts& conic2,
305 bool coin) {
306 #if DEBUG_VISUALIZE_CONICS
307 writeFrames();
308 #endif
309 SkDConic c1, c2;
310 c1.debugSet(conic1.fPts.fPts, conic1.fWeight);
311 c2.debugSet(conic2.fPts.fPts, conic2.fWeight);
312 chopBothWays(c1, 0.5, "c1");
313 chopBothWays(c2, 0.5, "c2");
314 #if DEBUG_VISUALIZE_CONICS
315 writeDPng(c1, "d1");
316 writeDPng(c2, "d2");
317 #endif
318 SkASSERT(ValidConic(c1));
319 SkASSERT(ValidConic(c2));
320 SkIntersections intersections;
321 intersections.intersect(c1, c2);
322 REPORTER_ASSERT(reporter, !coin || intersections.used() == 2);
323 double tt1, tt2;
324 SkDPoint xy1, xy2;
325 for (int pt3 = 0; pt3 < intersections.used(); ++pt3) {
326 tt1 = intersections[0][pt3];
327 xy1 = c1.ptAtT(tt1);
328 tt2 = intersections[1][pt3];
329 xy2 = c2.ptAtT(tt2);
330 const SkDPoint& iPt = intersections.pt(pt3);
331 REPORTER_ASSERT(reporter, xy1.approximatelyEqual(iPt));
332 REPORTER_ASSERT(reporter, xy2.approximatelyEqual(iPt));
333 REPORTER_ASSERT(reporter, xy1.approximatelyEqual(xy2));
334 }
335 reporter->bumpTestCount();
336 }
337
oneOff(skiatest::Reporter * reporter,int outer,int inner)338 static void oneOff(skiatest::Reporter* reporter, int outer, int inner) {
339 const ConicPts& c1 = testSet[outer];
340 const ConicPts& c2 = testSet[inner];
341 oneOff(reporter, c1, c2, false);
342 }
343
oneOffTests(skiatest::Reporter * reporter)344 static void oneOffTests(skiatest::Reporter* reporter) {
345 for (int outer = 0; outer < testSetCount - 1; ++outer) {
346 for (int inner = outer + 1; inner < testSetCount; ++inner) {
347 oneOff(reporter, outer, inner);
348 }
349 }
350 }
351
DEF_TEST(PathOpsConicIntersectionOneOff,reporter)352 DEF_TEST(PathOpsConicIntersectionOneOff, reporter) {
353 oneOff(reporter, 0, 1);
354 }
355
DEF_TEST(PathOpsConicIntersection,reporter)356 DEF_TEST(PathOpsConicIntersection, reporter) {
357 oneOffTests(reporter);
358 }
359