1// Copyright 2013 The Flutter Authors. All rights reserved. 2// Use of this source code is governed by a BSD-style license that can be 3// found in the LICENSE file. 4 5part of engine; 6 7/// Converts conic curve to a list of quadratic curves for rendering on 8/// canvas or conversion to svg. 9/// 10/// See "High order approximation of conic sections by quadratic splines" 11/// by Michael Floater, 1993. 12/// Skia implementation reference: 13/// https://github.com/google/skia/blob/master/src/core/SkGeometry.cpp 14class Conic { 15 double p0x, p0y, p1x, p1y, p2x, p2y; 16 final double fW; 17 static const int _maxSubdivisionCount = 5; 18 19 Conic(this.p0x, this.p0y, this.p1x, this.p1y, this.p2x, this.p2y, this.fW); 20 21 /// Returns array of points for the approximation of the conic as quad(s). 22 /// 23 /// First offset is start Point. Each pair of offsets after are quadratic 24 /// control and end points. 25 List<ui.Offset> toQuads() { 26 final List<ui.Offset> pointList = <ui.Offset>[]; 27 // This value specifies error bound. 28 const double conicTolerance = 1.0 / 4.0; 29 30 // Based on error bound, compute how many times we should subdivide 31 final int subdivideCount = _computeSubdivisionCount(conicTolerance); 32 33 // Split conic into quads, writes quad coordinates into [_pointList] and 34 // returns number of quads. 35 assert(subdivideCount > 0); 36 int quadCount = 1 << subdivideCount; 37 bool skipSubdivide = false; 38 pointList.add(ui.Offset(p0x, p0y)); 39 if (subdivideCount == _maxSubdivisionCount) { 40 // We have an extreme number of quads, chop this conic and check if 41 // it generates a pair of lines, in which case we should not subdivide. 42 final List<Conic> dst = List<Conic>(2); 43 _chop(dst); 44 final Conic conic0 = dst[0]; 45 final Conic conic1 = dst[1]; 46 // If this chop generates pair of lines no need to subdivide. 47 if (conic0.p1x == conic0.p2x && 48 conic0.p1y == conic0.p2y && 49 conic1.p0x == conic1.p1x && 50 conic1.p0y == conic1.p1y) { 51 final ui.Offset controlPointOffset = ui.Offset(conic0.p1x, conic0.p1y); 52 pointList.add(controlPointOffset); 53 pointList.add(controlPointOffset); 54 pointList.add(controlPointOffset); 55 pointList.add(ui.Offset(conic1.p2x, conic1.p2y)); 56 quadCount = 2; 57 skipSubdivide = true; 58 } 59 } 60 if (!skipSubdivide) { 61 _subdivide(this, subdivideCount, pointList); 62 } 63 64 // If there are any non-finite generated points, pin to middle of hull. 65 final int pointCount = 2 * quadCount + 1; 66 bool hasNonFinitePoints = false; 67 for (int p = 0; p < pointCount; ++p) { 68 if (pointList[p].dx.isNaN || pointList[p].dy.isNaN) { 69 hasNonFinitePoints = true; 70 break; 71 } 72 } 73 if (hasNonFinitePoints) { 74 for (int p = 1; p < pointCount - 1; ++p) { 75 pointList[p] = ui.Offset(p1x, p1y); 76 } 77 } 78 return pointList; 79 } 80 81 static bool _between(double a, double b, double c) { 82 return (a - b) * (c - b) <= 0; 83 } 84 85 // Subdivides a conic and writes to points list. 86 static void _subdivide(Conic src, int level, List<ui.Offset> pointList) { 87 assert(level >= 0); 88 if (0 == level) { 89 // At lowest subdivision point, copy control point and end point to 90 // target. 91 pointList.add(ui.Offset(src.p1x, src.p1y)); 92 pointList.add(ui.Offset(src.p2x, src.p2y)); 93 return; 94 } 95 final List<Conic> dst = List<Conic>(2); 96 src._chop(dst); 97 final Conic conic0 = dst[0]; 98 final Conic conic1 = dst[1]; 99 final double startY = src.p0y; 100 final double endY = src.p2y; 101 final double cpY = src.p1y; 102 if (_between(startY, cpY, endY)) { 103 // Ensure that chopped conics maintain their y-order. 104 final double midY = conic0.p2y; 105 if (!_between(startY, midY, endY)) { 106 // The computed midpoint is outside end points, move it to 107 // closer one. 108 final double closerY = 109 (midY - startY).abs() < (midY - endY).abs() ? startY : endY; 110 conic0.p2y = conic1.p0y = closerY; 111 } 112 if (!_between(startY, conic0.p1y, conic0.p2y)) { 113 // First control point not between start and end points, move it 114 // to start. 115 conic0.p1y = startY; 116 } 117 if (!_between(conic1.p0y, conic1.p1y, endY)) { 118 // Second control point not between start and end points, move it 119 // to end. 120 conic1.p1y = endY; 121 } 122 // Verify that conics points are ordered. 123 assert(_between(startY, conic0.p1y, conic0.p2y)); 124 assert(_between(conic0.p1y, conic0.p2y, conic1.p1y)); 125 assert(_between(conic0.p2y, conic1.p1y, endY)); 126 } 127 --level; 128 _subdivide(conic0, level, pointList); 129 _subdivide(conic1, level, pointList); 130 } 131 132 static double _subdivideWeightValue(double w) { 133 return math.sqrt(0.5 + w * 0.5); 134 } 135 136 // Splits conic into 2 parts based on weight. 137 void _chop(List<Conic> dst) { 138 final double scale = 1.0 / (1.0 + fW); 139 final double newW = _subdivideWeightValue(fW); 140 final ui.Offset wp1 = ui.Offset(fW * p1x, fW * p1y); 141 ui.Offset m = ui.Offset((p0x + (2 * wp1.dx) + p2x) * scale * 0.5, 142 (p0y + 2 * wp1.dy + p2y) * scale * 0.5); 143 if (m.dx.isNaN || m.dy.isNaN) { 144 final double w2 = fW * 2; 145 final double scaleHalf = 1.0 / (1 + fW) * 0.5; 146 m = ui.Offset((p0x + (w2 * p1x) + p2x) * scaleHalf, 147 (p0y + (w2 * p1y) + p2y) * scaleHalf); 148 } 149 dst[0] = Conic(p0x, p0y, (p0x + wp1.dx) * scale, (p0y + wp1.dy) * scale, 150 m.dx, m.dy, newW); 151 dst[1] = Conic(m.dx, m.dy, (p2x + wp1.dx) * scale, (p2y + wp1.dy) * scale, 152 p2x, p2y, newW); 153 } 154 155 /// Computes number of binary subdivisions of the curve given 156 /// the tolerance. 157 /// 158 /// The number of subdivisions never exceed [_maxSubdivisionCount]. 159 int _computeSubdivisionCount(double tolerance) { 160 assert(tolerance.isFinite); 161 // Expecting finite coordinates. 162 assert(p0x.isFinite && 163 p1x.isFinite && 164 p2x.isFinite && 165 p0y.isFinite && 166 p1y.isFinite && 167 p2y.isFinite); 168 if (tolerance < 0) { 169 return 0; 170 } 171 // See "High order approximation of conic sections by quadratic splines" 172 // by Michael Floater, 1993. 173 // Error bound e0 = |a| |p0 - 2p1 + p2| / 4(2 + a). 174 final double a = fW - 1; 175 final double k = a / (4.0 * (2.0 + a)); 176 final double x = k * (p0x - 2 * p1x + p2x); 177 final double y = k * (p0y - 2 * p1y + p2y); 178 179 double error = math.sqrt(x * x + y * y); 180 int pow2 = 0; 181 for (; pow2 < _maxSubdivisionCount; ++pow2) { 182 if (error <= tolerance) { 183 break; 184 } 185 error *= 0.25; 186 } 187 return pow2; 188 } 189} 190