1*e1fe3e4aSElliott Hughes# Copyright 2016 Google Inc. All Rights Reserved. 2*e1fe3e4aSElliott Hughes# 3*e1fe3e4aSElliott Hughes# Licensed under the Apache License, Version 2.0 (the "License"); 4*e1fe3e4aSElliott Hughes# you may not use this file except in compliance with the License. 5*e1fe3e4aSElliott Hughes# You may obtain a copy of the License at 6*e1fe3e4aSElliott Hughes# 7*e1fe3e4aSElliott Hughes# http://www.apache.org/licenses/LICENSE-2.0 8*e1fe3e4aSElliott Hughes# 9*e1fe3e4aSElliott Hughes# Unless required by applicable law or agreed to in writing, software 10*e1fe3e4aSElliott Hughes# distributed under the License is distributed on an "AS IS" BASIS, 11*e1fe3e4aSElliott Hughes# WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. 12*e1fe3e4aSElliott Hughes# See the License for the specific language governing permissions and 13*e1fe3e4aSElliott Hughes# limitations under the License. 14*e1fe3e4aSElliott Hughes 15*e1fe3e4aSElliott Hughesimport collections 16*e1fe3e4aSElliott Hughesimport math 17*e1fe3e4aSElliott Hughesimport unittest 18*e1fe3e4aSElliott Hughesimport os 19*e1fe3e4aSElliott Hughesimport json 20*e1fe3e4aSElliott Hughes 21*e1fe3e4aSElliott Hughesfrom fontTools.cu2qu import curve_to_quadratic, curves_to_quadratic 22*e1fe3e4aSElliott Hughes 23*e1fe3e4aSElliott Hughes 24*e1fe3e4aSElliott HughesDATADIR = os.path.join(os.path.dirname(__file__), "data") 25*e1fe3e4aSElliott Hughes 26*e1fe3e4aSElliott HughesMAX_ERR = 5 27*e1fe3e4aSElliott Hughes 28*e1fe3e4aSElliott Hughes 29*e1fe3e4aSElliott Hughesclass CurveToQuadraticTest(unittest.TestCase): 30*e1fe3e4aSElliott Hughes @classmethod 31*e1fe3e4aSElliott Hughes def setUpClass(cls): 32*e1fe3e4aSElliott Hughes """Do the curve conversion ahead of time, and run tests on results.""" 33*e1fe3e4aSElliott Hughes with open(os.path.join(DATADIR, "curves.json"), "r") as fp: 34*e1fe3e4aSElliott Hughes curves = json.load(fp) 35*e1fe3e4aSElliott Hughes 36*e1fe3e4aSElliott Hughes cls.single_splines = [curve_to_quadratic(c, MAX_ERR) for c in curves] 37*e1fe3e4aSElliott Hughes cls.single_errors = [ 38*e1fe3e4aSElliott Hughes cls.curve_spline_dist(c, s) for c, s in zip(curves, cls.single_splines) 39*e1fe3e4aSElliott Hughes ] 40*e1fe3e4aSElliott Hughes 41*e1fe3e4aSElliott Hughes curve_groups = [curves[i : i + 3] for i in range(0, 300, 3)] 42*e1fe3e4aSElliott Hughes cls.compat_splines = [ 43*e1fe3e4aSElliott Hughes curves_to_quadratic(c, [MAX_ERR] * 3) for c in curve_groups 44*e1fe3e4aSElliott Hughes ] 45*e1fe3e4aSElliott Hughes cls.compat_errors = [ 46*e1fe3e4aSElliott Hughes [cls.curve_spline_dist(c, s) for c, s in zip(curve_group, splines)] 47*e1fe3e4aSElliott Hughes for curve_group, splines in zip(curve_groups, cls.compat_splines) 48*e1fe3e4aSElliott Hughes ] 49*e1fe3e4aSElliott Hughes 50*e1fe3e4aSElliott Hughes cls.results = [] 51*e1fe3e4aSElliott Hughes 52*e1fe3e4aSElliott Hughes @classmethod 53*e1fe3e4aSElliott Hughes def tearDownClass(cls): 54*e1fe3e4aSElliott Hughes """Print stats from conversion, as determined during tests.""" 55*e1fe3e4aSElliott Hughes 56*e1fe3e4aSElliott Hughes for tag, results in cls.results: 57*e1fe3e4aSElliott Hughes print( 58*e1fe3e4aSElliott Hughes "\n%s\n%s" 59*e1fe3e4aSElliott Hughes % ( 60*e1fe3e4aSElliott Hughes tag, 61*e1fe3e4aSElliott Hughes "\n".join( 62*e1fe3e4aSElliott Hughes "%s: %s (%d)" % (k, "#" * (v // 10 + 1), v) 63*e1fe3e4aSElliott Hughes for k, v in sorted(results.items()) 64*e1fe3e4aSElliott Hughes ), 65*e1fe3e4aSElliott Hughes ) 66*e1fe3e4aSElliott Hughes ) 67*e1fe3e4aSElliott Hughes 68*e1fe3e4aSElliott Hughes def test_results_unchanged(self): 69*e1fe3e4aSElliott Hughes """Tests that the results of conversion haven't changed since the time 70*e1fe3e4aSElliott Hughes of this test's writing. Useful as a quick check whenever one modifies 71*e1fe3e4aSElliott Hughes the conversion algorithm. 72*e1fe3e4aSElliott Hughes """ 73*e1fe3e4aSElliott Hughes 74*e1fe3e4aSElliott Hughes expected = {2: 6, 3: 26, 4: 82, 5: 232, 6: 360, 7: 266, 8: 28} 75*e1fe3e4aSElliott Hughes 76*e1fe3e4aSElliott Hughes results = collections.defaultdict(int) 77*e1fe3e4aSElliott Hughes for spline in self.single_splines: 78*e1fe3e4aSElliott Hughes n = len(spline) - 2 79*e1fe3e4aSElliott Hughes results[n] += 1 80*e1fe3e4aSElliott Hughes self.assertEqual(results, expected) 81*e1fe3e4aSElliott Hughes self.results.append(("single spline lengths", results)) 82*e1fe3e4aSElliott Hughes 83*e1fe3e4aSElliott Hughes def test_results_unchanged_multiple(self): 84*e1fe3e4aSElliott Hughes """Test that conversion results are unchanged for multiple curves.""" 85*e1fe3e4aSElliott Hughes 86*e1fe3e4aSElliott Hughes expected = {5: 11, 6: 35, 7: 49, 8: 5} 87*e1fe3e4aSElliott Hughes 88*e1fe3e4aSElliott Hughes results = collections.defaultdict(int) 89*e1fe3e4aSElliott Hughes for splines in self.compat_splines: 90*e1fe3e4aSElliott Hughes n = len(splines[0]) - 2 91*e1fe3e4aSElliott Hughes for spline in splines[1:]: 92*e1fe3e4aSElliott Hughes self.assertEqual( 93*e1fe3e4aSElliott Hughes len(spline) - 2, n, "Got incompatible conversion results" 94*e1fe3e4aSElliott Hughes ) 95*e1fe3e4aSElliott Hughes results[n] += 1 96*e1fe3e4aSElliott Hughes self.assertEqual(results, expected) 97*e1fe3e4aSElliott Hughes self.results.append(("compatible spline lengths", results)) 98*e1fe3e4aSElliott Hughes 99*e1fe3e4aSElliott Hughes def test_does_not_exceed_tolerance(self): 100*e1fe3e4aSElliott Hughes """Test that conversion results do not exceed given error tolerance.""" 101*e1fe3e4aSElliott Hughes 102*e1fe3e4aSElliott Hughes results = collections.defaultdict(int) 103*e1fe3e4aSElliott Hughes for error in self.single_errors: 104*e1fe3e4aSElliott Hughes results[round(error, 1)] += 1 105*e1fe3e4aSElliott Hughes self.assertLessEqual(error, MAX_ERR) 106*e1fe3e4aSElliott Hughes self.results.append(("single errors", results)) 107*e1fe3e4aSElliott Hughes 108*e1fe3e4aSElliott Hughes def test_does_not_exceed_tolerance_multiple(self): 109*e1fe3e4aSElliott Hughes """Test that error tolerance isn't exceeded for multiple curves.""" 110*e1fe3e4aSElliott Hughes 111*e1fe3e4aSElliott Hughes results = collections.defaultdict(int) 112*e1fe3e4aSElliott Hughes for errors in self.compat_errors: 113*e1fe3e4aSElliott Hughes for error in errors: 114*e1fe3e4aSElliott Hughes results[round(error, 1)] += 1 115*e1fe3e4aSElliott Hughes self.assertLessEqual(error, MAX_ERR) 116*e1fe3e4aSElliott Hughes self.results.append(("compatible errors", results)) 117*e1fe3e4aSElliott Hughes 118*e1fe3e4aSElliott Hughes @classmethod 119*e1fe3e4aSElliott Hughes def curve_spline_dist(cls, bezier, spline, total_steps=20): 120*e1fe3e4aSElliott Hughes """Max distance between a bezier and quadratic spline at sampled points.""" 121*e1fe3e4aSElliott Hughes 122*e1fe3e4aSElliott Hughes error = 0 123*e1fe3e4aSElliott Hughes n = len(spline) - 2 124*e1fe3e4aSElliott Hughes steps = total_steps // n 125*e1fe3e4aSElliott Hughes for i in range(0, n - 1): 126*e1fe3e4aSElliott Hughes p1 = spline[0] if i == 0 else p3 127*e1fe3e4aSElliott Hughes p2 = spline[i + 1] 128*e1fe3e4aSElliott Hughes if i < n - 1: 129*e1fe3e4aSElliott Hughes p3 = cls.lerp(spline[i + 1], spline[i + 2], 0.5) 130*e1fe3e4aSElliott Hughes else: 131*e1fe3e4aSElliott Hughes p3 = spline[n + 2] 132*e1fe3e4aSElliott Hughes segment = p1, p2, p3 133*e1fe3e4aSElliott Hughes for j in range(steps): 134*e1fe3e4aSElliott Hughes error = max( 135*e1fe3e4aSElliott Hughes error, 136*e1fe3e4aSElliott Hughes cls.dist( 137*e1fe3e4aSElliott Hughes cls.cubic_bezier_at(bezier, (j / steps + i) / n), 138*e1fe3e4aSElliott Hughes cls.quadratic_bezier_at(segment, j / steps), 139*e1fe3e4aSElliott Hughes ), 140*e1fe3e4aSElliott Hughes ) 141*e1fe3e4aSElliott Hughes return error 142*e1fe3e4aSElliott Hughes 143*e1fe3e4aSElliott Hughes @classmethod 144*e1fe3e4aSElliott Hughes def lerp(cls, p1, p2, t): 145*e1fe3e4aSElliott Hughes (x1, y1), (x2, y2) = p1, p2 146*e1fe3e4aSElliott Hughes return x1 + (x2 - x1) * t, y1 + (y2 - y1) * t 147*e1fe3e4aSElliott Hughes 148*e1fe3e4aSElliott Hughes @classmethod 149*e1fe3e4aSElliott Hughes def dist(cls, p1, p2): 150*e1fe3e4aSElliott Hughes (x1, y1), (x2, y2) = p1, p2 151*e1fe3e4aSElliott Hughes return math.hypot(x1 - x2, y1 - y2) 152*e1fe3e4aSElliott Hughes 153*e1fe3e4aSElliott Hughes @classmethod 154*e1fe3e4aSElliott Hughes def quadratic_bezier_at(cls, b, t): 155*e1fe3e4aSElliott Hughes (x1, y1), (x2, y2), (x3, y3) = b 156*e1fe3e4aSElliott Hughes _t = 1 - t 157*e1fe3e4aSElliott Hughes t2 = t * t 158*e1fe3e4aSElliott Hughes _t2 = _t * _t 159*e1fe3e4aSElliott Hughes _2_t_t = 2 * t * _t 160*e1fe3e4aSElliott Hughes return (_t2 * x1 + _2_t_t * x2 + t2 * x3, _t2 * y1 + _2_t_t * y2 + t2 * y3) 161*e1fe3e4aSElliott Hughes 162*e1fe3e4aSElliott Hughes @classmethod 163*e1fe3e4aSElliott Hughes def cubic_bezier_at(cls, b, t): 164*e1fe3e4aSElliott Hughes (x1, y1), (x2, y2), (x3, y3), (x4, y4) = b 165*e1fe3e4aSElliott Hughes _t = 1 - t 166*e1fe3e4aSElliott Hughes t2 = t * t 167*e1fe3e4aSElliott Hughes _t2 = _t * _t 168*e1fe3e4aSElliott Hughes t3 = t * t2 169*e1fe3e4aSElliott Hughes _t3 = _t * _t2 170*e1fe3e4aSElliott Hughes _3_t2_t = 3 * t2 * _t 171*e1fe3e4aSElliott Hughes _3_t_t2 = 3 * t * _t2 172*e1fe3e4aSElliott Hughes return ( 173*e1fe3e4aSElliott Hughes _t3 * x1 + _3_t_t2 * x2 + _3_t2_t * x3 + t3 * x4, 174*e1fe3e4aSElliott Hughes _t3 * y1 + _3_t_t2 * y2 + _3_t2_t * y3 + t3 * y4, 175*e1fe3e4aSElliott Hughes ) 176*e1fe3e4aSElliott Hughes 177*e1fe3e4aSElliott Hughes 178*e1fe3e4aSElliott Hughesclass AllQuadraticFalseTest(unittest.TestCase): 179*e1fe3e4aSElliott Hughes def test_cubic(self): 180*e1fe3e4aSElliott Hughes cubic = [(0, 0), (0, 1), (2, 1), (2, 0)] 181*e1fe3e4aSElliott Hughes result = curve_to_quadratic(cubic, 0.1, all_quadratic=False) 182*e1fe3e4aSElliott Hughes assert result == cubic 183*e1fe3e4aSElliott Hughes 184*e1fe3e4aSElliott Hughes def test_quadratic(self): 185*e1fe3e4aSElliott Hughes cubic = [(0, 0), (2, 2), (4, 2), (6, 0)] 186*e1fe3e4aSElliott Hughes result = curve_to_quadratic(cubic, 0.1, all_quadratic=False) 187*e1fe3e4aSElliott Hughes quadratic = [(0, 0), (3, 3), (6, 0)] 188*e1fe3e4aSElliott Hughes assert result == quadratic 189*e1fe3e4aSElliott Hughes 190*e1fe3e4aSElliott Hughes 191*e1fe3e4aSElliott Hughesif __name__ == "__main__": 192*e1fe3e4aSElliott Hughes unittest.main() 193