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 "src/core/SkGeometry.h"
8#include "src/pathops/SkIntersections.h"
9#include "tests/PathOpsTestCommon.h"
10#include "tests/Test.h"
11
12/*
13manually 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
19static const ConicPts 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
45const int testSetCount = (int) SK_ARRAY_COUNT(testSet);
46
47static 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 "include/core/SkBitmap.h"
64#include "include/core/SkCanvas.h"
65#include "include/core/SkImageEncoder.h"
66#include "include/core/SkPaint.h"
67#include "include/core/SkString.h"
68#include "src/pathops/SkPathOpsRect.h"
69
70#define DEBUG_VISUALIZE_CONICS 0
71
72#if DEBUG_VISUALIZE_CONICS
73static 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    ToolUtils::EncodeImageToFile(filename.c_str(), bitmap, SkEncodedImageFormat::kPNG, 100);
114}
115
116static void writeDPng(const SkDConic& dC, const char* name) {
117    const int scale = 5;
118    SkDConic dConic = {{{ {dC.fPts[0].fX * scale, dC.fPts[0].fY * scale },
119        {dC.fPts[1].fX * scale, dC.fPts[1].fY * scale },
120        {dC.fPts[2].fX * scale, dC.fPts[2].fY * scale }}}, dC.fWeight };
121    SkBitmap bitmap;
122    SkDRect bounds;
123    bounds.setBounds(dConic);
124    bounds.fLeft -= 10;
125    bounds.fTop -= 10;
126    bounds.fRight += 10;
127    bounds.fBottom += 10;
128    bitmap.tryAllocPixels(SkImageInfo::MakeN32Premul(
129          SkScalarRoundToInt(SkDoubleToScalar(bounds.width())),
130          SkScalarRoundToInt(SkDoubleToScalar(bounds.height()))));
131    SkCanvas canvas(bitmap);
132    SkPaint paint;
133    paint.setAntiAlias(true);
134    paint.setStyle(SkPaint::kStroke_Style);
135    canvas.translate(SkDoubleToScalar(-bounds.fLeft), SkDoubleToScalar(-bounds.fTop));
136    canvas.drawColor(SK_ColorWHITE);
137    SkPath path;
138    path.moveTo(dConic.fPts[0].asSkPoint());
139    path.conicTo(dConic.fPts[1].asSkPoint(), dConic.fPts[2].asSkPoint(), dConic.fWeight);
140    paint.setARGB(0x80, 0xFF, 0, 0);
141    canvas.drawPath(path, paint);
142    path.reset();
143    const int chops = 2;
144    for (int tIndex = 0; tIndex < chops; ++tIndex) {
145        SkDConic chopped = dConic.subDivide(tIndex / (double) chops,
146                (tIndex + 1) / (double) chops);
147        path.moveTo(chopped.fPts[0].asSkPoint());
148        path.conicTo(chopped.fPts[1].asSkPoint(), chopped.fPts[2].asSkPoint(), chopped.fWeight);
149    }
150    paint.setARGB(0x80, 0, 0, 0xFF);
151    canvas.drawPath(path, paint);
152    SkString filename("c:\\Users\\caryclark\\Documents\\");
153    filename.appendf("%s.png", name);
154    ToolUtils::EncodeImageToFile(filename.c_str(), bitmap, SkEncodedImageFormat::kPNG, 100);
155}
156#endif
157
158static void chopBothWays(const SkDConic& dConic, double t, const char* name) {
159    SkConic conic;
160    for (int index = 0; index < 3; ++index) {
161        conic.fPts[index] = dConic.fPts[index].asSkPoint();
162    }
163    conic.fW = dConic.fWeight;
164    SkConic chopped[2];
165    SkDConic dChopped[2];
166    if (!conic.chopAt(SkDoubleToScalar(t), chopped)) {
167        return;
168    }
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
181const 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
186const 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
193const 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
200const 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
207const 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
214const 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
221const 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
228const SkDConic* frames[] = {
229    frame0, frame1, frame2, frame3, frame4, frame5, frame6
230};
231
232const 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
238static 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        ToolUtils::EncodeImageToFile(filename.c_str(), bitmap, SkEncodedImageFormat::kPNG, 100);
292    }
293}
294#endif
295
296static void oneOff(skiatest::Reporter* reporter, const ConicPts& conic1, const ConicPts& conic2,
297        bool coin) {
298#if DEBUG_VISUALIZE_CONICS
299    writeFrames();
300#endif
301    SkDConic c1, c2;
302    c1.debugSet(conic1.fPts.fPts, conic1.fWeight);
303    c2.debugSet(conic2.fPts.fPts, conic2.fWeight);
304    chopBothWays(c1, 0.5, "c1");
305    chopBothWays(c2, 0.5, "c2");
306#if DEBUG_VISUALIZE_CONICS
307    writeDPng(c1, "d1");
308    writeDPng(c2, "d2");
309#endif
310    SkASSERT(ValidConic(c1));
311    SkASSERT(ValidConic(c2));
312    SkIntersections intersections;
313    intersections.intersect(c1, c2);
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
330static void oneOff(skiatest::Reporter* reporter, int outer, int inner) {
331    const ConicPts& c1 = testSet[outer];
332    const ConicPts& c2 = testSet[inner];
333    oneOff(reporter, c1, c2, false);
334}
335
336static 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
344DEF_TEST(PathOpsConicIntersectionOneOff, reporter) {
345    oneOff(reporter, 0, 1);
346}
347
348DEF_TEST(PathOpsConicIntersection, reporter) {
349    oneOffTests(reporter);
350}
351