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