121c2924b178f0d4c298d6631e568401473ed8d16caryclark@google.com/* 221c2924b178f0d4c298d6631e568401473ed8d16caryclark@google.com * Copyright 2012 Google Inc. 321c2924b178f0d4c298d6631e568401473ed8d16caryclark@google.com * 421c2924b178f0d4c298d6631e568401473ed8d16caryclark@google.com * Use of this source code is governed by a BSD-style license that can be 521c2924b178f0d4c298d6631e568401473ed8d16caryclark@google.com * found in the LICENSE file. 621c2924b178f0d4c298d6631e568401473ed8d16caryclark@google.com */ 721c2924b178f0d4c298d6631e568401473ed8d16caryclark@google.com#include "SkDQuadImplicit.h" 821c2924b178f0d4c298d6631e568401473ed8d16caryclark@google.com 921c2924b178f0d4c298d6631e568401473ed8d16caryclark@google.com/* from http://tom.cs.byu.edu/~tom/papers/cvgip84.pdf 4.1 1021c2924b178f0d4c298d6631e568401473ed8d16caryclark@google.com * 1121c2924b178f0d4c298d6631e568401473ed8d16caryclark@google.com * This paper proves that Syvester's method can compute the implicit form of 1221c2924b178f0d4c298d6631e568401473ed8d16caryclark@google.com * the quadratic from the parameterized form. 1321c2924b178f0d4c298d6631e568401473ed8d16caryclark@google.com * 1421c2924b178f0d4c298d6631e568401473ed8d16caryclark@google.com * Given x = a*t*t + b*t + c (the parameterized form) 1521c2924b178f0d4c298d6631e568401473ed8d16caryclark@google.com * y = d*t*t + e*t + f 1621c2924b178f0d4c298d6631e568401473ed8d16caryclark@google.com * 1721c2924b178f0d4c298d6631e568401473ed8d16caryclark@google.com * we want to find an equation of the implicit form: 1821c2924b178f0d4c298d6631e568401473ed8d16caryclark@google.com * 1921c2924b178f0d4c298d6631e568401473ed8d16caryclark@google.com * A*x*x + B*x*y + C*y*y + D*x + E*y + F = 0 2021c2924b178f0d4c298d6631e568401473ed8d16caryclark@google.com * 2121c2924b178f0d4c298d6631e568401473ed8d16caryclark@google.com * The implicit form can be expressed as a 4x4 determinant, as shown. 2221c2924b178f0d4c298d6631e568401473ed8d16caryclark@google.com * 2321c2924b178f0d4c298d6631e568401473ed8d16caryclark@google.com * The resultant obtained by Syvester's method is 2421c2924b178f0d4c298d6631e568401473ed8d16caryclark@google.com * 2521c2924b178f0d4c298d6631e568401473ed8d16caryclark@google.com * | a b (c - x) 0 | 2621c2924b178f0d4c298d6631e568401473ed8d16caryclark@google.com * | 0 a b (c - x) | 2721c2924b178f0d4c298d6631e568401473ed8d16caryclark@google.com * | d e (f - y) 0 | 2821c2924b178f0d4c298d6631e568401473ed8d16caryclark@google.com * | 0 d e (f - y) | 2921c2924b178f0d4c298d6631e568401473ed8d16caryclark@google.com * 3021c2924b178f0d4c298d6631e568401473ed8d16caryclark@google.com * which expands to 3121c2924b178f0d4c298d6631e568401473ed8d16caryclark@google.com * 3221c2924b178f0d4c298d6631e568401473ed8d16caryclark@google.com * d*d*x*x + -2*a*d*x*y + a*a*y*y 3321c2924b178f0d4c298d6631e568401473ed8d16caryclark@google.com * + (-2*c*d*d + b*e*d - a*e*e + 2*a*f*d)*x 3421c2924b178f0d4c298d6631e568401473ed8d16caryclark@google.com * + (-2*f*a*a + e*b*a - d*b*b + 2*d*c*a)*y 3521c2924b178f0d4c298d6631e568401473ed8d16caryclark@google.com * + 3621c2924b178f0d4c298d6631e568401473ed8d16caryclark@google.com * | a b c 0 | 3721c2924b178f0d4c298d6631e568401473ed8d16caryclark@google.com * | 0 a b c | == 0. 3821c2924b178f0d4c298d6631e568401473ed8d16caryclark@google.com * | d e f 0 | 3921c2924b178f0d4c298d6631e568401473ed8d16caryclark@google.com * | 0 d e f | 4021c2924b178f0d4c298d6631e568401473ed8d16caryclark@google.com * 4121c2924b178f0d4c298d6631e568401473ed8d16caryclark@google.com * Expanding the constant determinant results in 4221c2924b178f0d4c298d6631e568401473ed8d16caryclark@google.com * 4321c2924b178f0d4c298d6631e568401473ed8d16caryclark@google.com * | a b c | | b c 0 | 4421c2924b178f0d4c298d6631e568401473ed8d16caryclark@google.com * a*| e f 0 | + d*| a b c | == 4521c2924b178f0d4c298d6631e568401473ed8d16caryclark@google.com * | d e f | | d e f | 4621c2924b178f0d4c298d6631e568401473ed8d16caryclark@google.com * 4721c2924b178f0d4c298d6631e568401473ed8d16caryclark@google.com * a*(a*f*f + c*e*e - c*f*d - b*e*f) + d*(b*b*f + c*c*d - c*a*f - c*e*b) 4821c2924b178f0d4c298d6631e568401473ed8d16caryclark@google.com * 4921c2924b178f0d4c298d6631e568401473ed8d16caryclark@google.com */ 5021c2924b178f0d4c298d6631e568401473ed8d16caryclark@google.com 51289863b9e9abab20aec012de77343b61c7dc2566caryclark@google.com// use the tricky arithmetic path, but leave the original to compare just in case 52289863b9e9abab20aec012de77343b61c7dc2566caryclark@google.comstatic bool straight_forward = false; 5321c2924b178f0d4c298d6631e568401473ed8d16caryclark@google.com 5421c2924b178f0d4c298d6631e568401473ed8d16caryclark@google.comSkDQuadImplicit::SkDQuadImplicit(const SkDQuad& q) { 5521c2924b178f0d4c298d6631e568401473ed8d16caryclark@google.com double a, b, c; 5621c2924b178f0d4c298d6631e568401473ed8d16caryclark@google.com SkDQuad::SetABC(&q[0].fX, &a, &b, &c); 5721c2924b178f0d4c298d6631e568401473ed8d16caryclark@google.com double d, e, f; 5821c2924b178f0d4c298d6631e568401473ed8d16caryclark@google.com SkDQuad::SetABC(&q[0].fY, &d, &e, &f); 5921c2924b178f0d4c298d6631e568401473ed8d16caryclark@google.com // compute the implicit coefficients 6021c2924b178f0d4c298d6631e568401473ed8d16caryclark@google.com if (straight_forward) { // 42 muls, 13 adds 6121c2924b178f0d4c298d6631e568401473ed8d16caryclark@google.com fP[kXx_Coeff] = d * d; 6221c2924b178f0d4c298d6631e568401473ed8d16caryclark@google.com fP[kXy_Coeff] = -2 * a * d; 6321c2924b178f0d4c298d6631e568401473ed8d16caryclark@google.com fP[kYy_Coeff] = a * a; 6421c2924b178f0d4c298d6631e568401473ed8d16caryclark@google.com fP[kX_Coeff] = -2*c*d*d + b*e*d - a*e*e + 2*a*f*d; 6521c2924b178f0d4c298d6631e568401473ed8d16caryclark@google.com fP[kY_Coeff] = -2*f*a*a + e*b*a - d*b*b + 2*d*c*a; 6621c2924b178f0d4c298d6631e568401473ed8d16caryclark@google.com fP[kC_Coeff] = a*(a*f*f + c*e*e - c*f*d - b*e*f) 6721c2924b178f0d4c298d6631e568401473ed8d16caryclark@google.com + d*(b*b*f + c*c*d - c*a*f - c*e*b); 6821c2924b178f0d4c298d6631e568401473ed8d16caryclark@google.com } else { // 26 muls, 11 adds 6921c2924b178f0d4c298d6631e568401473ed8d16caryclark@google.com double aa = a * a; 7021c2924b178f0d4c298d6631e568401473ed8d16caryclark@google.com double ad = a * d; 7121c2924b178f0d4c298d6631e568401473ed8d16caryclark@google.com double dd = d * d; 7221c2924b178f0d4c298d6631e568401473ed8d16caryclark@google.com fP[kXx_Coeff] = dd; 7321c2924b178f0d4c298d6631e568401473ed8d16caryclark@google.com fP[kXy_Coeff] = -2 * ad; 7421c2924b178f0d4c298d6631e568401473ed8d16caryclark@google.com fP[kYy_Coeff] = aa; 7521c2924b178f0d4c298d6631e568401473ed8d16caryclark@google.com double be = b * e; 7621c2924b178f0d4c298d6631e568401473ed8d16caryclark@google.com double bde = be * d; 7721c2924b178f0d4c298d6631e568401473ed8d16caryclark@google.com double cdd = c * dd; 7821c2924b178f0d4c298d6631e568401473ed8d16caryclark@google.com double ee = e * e; 7921c2924b178f0d4c298d6631e568401473ed8d16caryclark@google.com fP[kX_Coeff] = -2*cdd + bde - a*ee + 2*ad*f; 8021c2924b178f0d4c298d6631e568401473ed8d16caryclark@google.com double aaf = aa * f; 8121c2924b178f0d4c298d6631e568401473ed8d16caryclark@google.com double abe = a * be; 8221c2924b178f0d4c298d6631e568401473ed8d16caryclark@google.com double ac = a * c; 8321c2924b178f0d4c298d6631e568401473ed8d16caryclark@google.com double bb_2ac = b*b - 2*ac; 8421c2924b178f0d4c298d6631e568401473ed8d16caryclark@google.com fP[kY_Coeff] = -2*aaf + abe - d*bb_2ac; 8521c2924b178f0d4c298d6631e568401473ed8d16caryclark@google.com fP[kC_Coeff] = aaf*f + ac*ee + d*f*bb_2ac - abe*f + c*cdd - c*bde; 8621c2924b178f0d4c298d6631e568401473ed8d16caryclark@google.com } 8721c2924b178f0d4c298d6631e568401473ed8d16caryclark@google.com} 8821c2924b178f0d4c298d6631e568401473ed8d16caryclark@google.com 8921c2924b178f0d4c298d6631e568401473ed8d16caryclark@google.com /* Given a pair of quadratics, determine their parametric coefficients. 9021c2924b178f0d4c298d6631e568401473ed8d16caryclark@google.com * If the scaled coefficients are nearly equal, then the part of the quadratics 9121c2924b178f0d4c298d6631e568401473ed8d16caryclark@google.com * may be coincident. 92289863b9e9abab20aec012de77343b61c7dc2566caryclark@google.com * OPTIMIZATION -- since comparison short-circuits on no match, 9321c2924b178f0d4c298d6631e568401473ed8d16caryclark@google.com * lazily compute the coefficients, comparing the easiest to compute first. 9421c2924b178f0d4c298d6631e568401473ed8d16caryclark@google.com * xx and yy first; then xy; and so on. 9521c2924b178f0d4c298d6631e568401473ed8d16caryclark@google.com */ 9621c2924b178f0d4c298d6631e568401473ed8d16caryclark@google.combool SkDQuadImplicit::match(const SkDQuadImplicit& p2) const { 9721c2924b178f0d4c298d6631e568401473ed8d16caryclark@google.com int first = 0; 9821c2924b178f0d4c298d6631e568401473ed8d16caryclark@google.com for (int index = 0; index <= kC_Coeff; ++index) { 9921c2924b178f0d4c298d6631e568401473ed8d16caryclark@google.com if (approximately_zero(fP[index]) && approximately_zero(p2.fP[index])) { 10021c2924b178f0d4c298d6631e568401473ed8d16caryclark@google.com first += first == index; 10121c2924b178f0d4c298d6631e568401473ed8d16caryclark@google.com continue; 10221c2924b178f0d4c298d6631e568401473ed8d16caryclark@google.com } 10321c2924b178f0d4c298d6631e568401473ed8d16caryclark@google.com if (first == index) { 10421c2924b178f0d4c298d6631e568401473ed8d16caryclark@google.com continue; 10521c2924b178f0d4c298d6631e568401473ed8d16caryclark@google.com } 10621c2924b178f0d4c298d6631e568401473ed8d16caryclark@google.com if (!AlmostEqualUlps(fP[index] * p2.fP[first], fP[first] * p2.fP[index])) { 10721c2924b178f0d4c298d6631e568401473ed8d16caryclark@google.com return false; 10821c2924b178f0d4c298d6631e568401473ed8d16caryclark@google.com } 10921c2924b178f0d4c298d6631e568401473ed8d16caryclark@google.com } 11021c2924b178f0d4c298d6631e568401473ed8d16caryclark@google.com return true; 11121c2924b178f0d4c298d6631e568401473ed8d16caryclark@google.com} 11221c2924b178f0d4c298d6631e568401473ed8d16caryclark@google.com 11321c2924b178f0d4c298d6631e568401473ed8d16caryclark@google.combool SkDQuadImplicit::Match(const SkDQuad& quad1, const SkDQuad& quad2) { 11421c2924b178f0d4c298d6631e568401473ed8d16caryclark@google.com SkDQuadImplicit i1(quad1); // a'xx , b'xy , c'yy , d'x , e'y , f 11521c2924b178f0d4c298d6631e568401473ed8d16caryclark@google.com SkDQuadImplicit i2(quad2); 11621c2924b178f0d4c298d6631e568401473ed8d16caryclark@google.com return i1.match(i2); 11721c2924b178f0d4c298d6631e568401473ed8d16caryclark@google.com} 118