blob: 7f011590fc84f4dd4e5c69782a0b3fe451075e07 [file] [log] [blame]
/*
* Copyright 2020 Google Inc.
*
* Use of this source code is governed by a BSD-style license that can be
* found in the LICENSE file.
*/
#include "include/core/SkPoint.h"
#include "include/core/SkScalar.h"
#include "include/core/SkTypes.h"
#include "src/core/SkGeometry.h"
#include "src/gpu/tessellate/Tessellation.h"
#include "tests/Test.h"
#include <cmath>
#include <cstdint>
#include <cstring>
namespace skgpu::tess {
static bool is_linear(SkPoint p0, SkPoint p1, SkPoint p2) {
return SkScalarNearlyZero((p0 - p1).cross(p2 - p1));
}
static bool is_linear(const SkPoint p[4]) {
return is_linear(p[0],p[1],p[2]) && is_linear(p[0],p[2],p[3]) && is_linear(p[1],p[2],p[3]);
}
static void check_cubic_convex_180(skiatest::Reporter* r, const SkPoint p[4]) {
bool areCusps = false;
float inflectT[2], convex180T[2];
if (int inflectN = SkFindCubicInflections(p, inflectT)) {
// The curve has inflections. FindCubicConvex180Chops should return the inflection
// points.
int convex180N = FindCubicConvex180Chops(p, convex180T, &areCusps);
REPORTER_ASSERT(r, inflectN == convex180N);
if (!areCusps) {
REPORTER_ASSERT(r, inflectN == 1 ||
fabsf(inflectT[0] - inflectT[1]) >= SK_ScalarNearlyZero);
}
for (int i = 0; i < convex180N; ++i) {
REPORTER_ASSERT(r, SkScalarNearlyEqual(inflectT[i], convex180T[i]));
}
} else {
float totalRotation = SkMeasureNonInflectCubicRotation(p);
int convex180N = FindCubicConvex180Chops(p, convex180T, &areCusps);
SkPoint chops[10];
SkChopCubicAt(p, chops, convex180T, convex180N);
float radsSum = 0;
for (int i = 0; i <= convex180N; ++i) {
float rads = SkMeasureNonInflectCubicRotation(chops + i*3);
SkASSERT(rads < SK_ScalarPI + SK_ScalarNearlyZero);
radsSum += rads;
}
if (totalRotation < SK_ScalarPI - SK_ScalarNearlyZero) {
// The curve should never chop if rotation is <180 degrees.
REPORTER_ASSERT(r, convex180N == 0);
} else if (!is_linear(p)) {
REPORTER_ASSERT(r, SkScalarNearlyEqual(radsSum, totalRotation));
if (totalRotation > SK_ScalarPI + SK_ScalarNearlyZero) {
REPORTER_ASSERT(r, convex180N == 1);
// This works because cusps take the "inflection" path above, so we don't get
// non-lilnear curves that lose rotation when chopped.
REPORTER_ASSERT(r, SkScalarNearlyEqual(
SkMeasureNonInflectCubicRotation(chops), SK_ScalarPI));
REPORTER_ASSERT(r, SkScalarNearlyEqual(
SkMeasureNonInflectCubicRotation(chops + 3), totalRotation - SK_ScalarPI));
}
REPORTER_ASSERT(r, !areCusps);
} else {
REPORTER_ASSERT(r, areCusps);
}
}
}
DEF_TEST(FindCubicConvex180Chops, r) {
// Test all combinations of corners from the square [0,0,1,1]. This covers every cubic type as
// well as a wide variety of special cases for cusps, lines, loops, and inflections.
for (int i = 0; i < (1 << 8); ++i) {
SkPoint p[4] = {SkPoint::Make((i>>0)&1, (i>>1)&1),
SkPoint::Make((i>>2)&1, (i>>3)&1),
SkPoint::Make((i>>4)&1, (i>>5)&1),
SkPoint::Make((i>>6)&1, (i>>7)&1)};
check_cubic_convex_180(r, p);
}
{
// This cubic has a convex-180 chop at T=1-"epsilon"
static const uint32_t hexPts[] = {0x3ee0ac74, 0x3f1e061a, 0x3e0fc408, 0x3f457230,
0x3f42ac7c, 0x3f70d76c, 0x3f4e6520, 0x3f6acafa};
SkPoint p[4];
memcpy(p, hexPts, sizeof(p));
check_cubic_convex_180(r, p);
}
// Now test an exact quadratic.
SkPoint quad[4] = {{0,0}, {2,2}, {4,2}, {6,0}};
float T[2];
bool areCusps;
REPORTER_ASSERT(r, FindCubicConvex180Chops(quad, T, &areCusps) == 0);
// Now test that cusps and near-cusps get flagged as cusps.
SkPoint cusp[4] = {{0,0}, {1,1}, {1,0}, {0,1}};
REPORTER_ASSERT(r, FindCubicConvex180Chops(cusp, T, &areCusps) == 1);
REPORTER_ASSERT(r, areCusps == true);
// Find the height of the right side of "cusp" at which the distance between its inflection
// points is kEpsilon (in parametric space).
constexpr static double kEpsilon = 1.0 / (1 << 11);
constexpr static double kEpsilonSquared = kEpsilon * kEpsilon;
double h = (1 - kEpsilonSquared) / (3 * kEpsilonSquared + 1);
double dy = (1 - h) / 2;
cusp[1].fY = (float)(1 - dy);
cusp[2].fY = (float)(0 + dy);
REPORTER_ASSERT(r, SkFindCubicInflections(cusp, T) == 2);
REPORTER_ASSERT(r, SkScalarNearlyEqual(T[1] - T[0], (float)kEpsilon, (float)kEpsilonSquared));
// Ensure two inflection points barely more than kEpsilon apart do not get flagged as cusps.
cusp[1].fY = (float)(1 - 1.1 * dy);
cusp[2].fY = (float)(0 + 1.1 * dy);
REPORTER_ASSERT(r, FindCubicConvex180Chops(cusp, T, &areCusps) == 2);
REPORTER_ASSERT(r, areCusps == false);
// Ensure two inflection points barely less than kEpsilon apart do get flagged as cusps.
cusp[1].fY = (float)(1 - .9 * dy);
cusp[2].fY = (float)(0 + .9 * dy);
REPORTER_ASSERT(r, FindCubicConvex180Chops(cusp, T, &areCusps) == 1);
REPORTER_ASSERT(r, areCusps == true);
}
} // namespace skgpu::tess