17839ce1af63bf12fe7b3caa866970bbbb3afb13dDerek Sollenberger/* 27839ce1af63bf12fe7b3caa866970bbbb3afb13dDerek Sollenberger * Copyright 2012 Google Inc. 37839ce1af63bf12fe7b3caa866970bbbb3afb13dDerek Sollenberger * 47839ce1af63bf12fe7b3caa866970bbbb3afb13dDerek Sollenberger * Use of this source code is governed by a BSD-style license that can be 57839ce1af63bf12fe7b3caa866970bbbb3afb13dDerek Sollenberger * found in the LICENSE file. 67839ce1af63bf12fe7b3caa866970bbbb3afb13dDerek Sollenberger */ 77839ce1af63bf12fe7b3caa866970bbbb3afb13dDerek Sollenberger#include "SkDQuadImplicit.h" 87839ce1af63bf12fe7b3caa866970bbbb3afb13dDerek Sollenberger 97839ce1af63bf12fe7b3caa866970bbbb3afb13dDerek Sollenberger/* from http://tom.cs.byu.edu/~tom/papers/cvgip84.pdf 4.1 107839ce1af63bf12fe7b3caa866970bbbb3afb13dDerek Sollenberger * 117839ce1af63bf12fe7b3caa866970bbbb3afb13dDerek Sollenberger * This paper proves that Syvester's method can compute the implicit form of 127839ce1af63bf12fe7b3caa866970bbbb3afb13dDerek Sollenberger * the quadratic from the parameterized form. 137839ce1af63bf12fe7b3caa866970bbbb3afb13dDerek Sollenberger * 147839ce1af63bf12fe7b3caa866970bbbb3afb13dDerek Sollenberger * Given x = a*t*t + b*t + c (the parameterized form) 157839ce1af63bf12fe7b3caa866970bbbb3afb13dDerek Sollenberger * y = d*t*t + e*t + f 167839ce1af63bf12fe7b3caa866970bbbb3afb13dDerek Sollenberger * 177839ce1af63bf12fe7b3caa866970bbbb3afb13dDerek Sollenberger * we want to find an equation of the implicit form: 187839ce1af63bf12fe7b3caa866970bbbb3afb13dDerek Sollenberger * 197839ce1af63bf12fe7b3caa866970bbbb3afb13dDerek Sollenberger * A*x*x + B*x*y + C*y*y + D*x + E*y + F = 0 207839ce1af63bf12fe7b3caa866970bbbb3afb13dDerek Sollenberger * 217839ce1af63bf12fe7b3caa866970bbbb3afb13dDerek Sollenberger * The implicit form can be expressed as a 4x4 determinant, as shown. 227839ce1af63bf12fe7b3caa866970bbbb3afb13dDerek Sollenberger * 237839ce1af63bf12fe7b3caa866970bbbb3afb13dDerek Sollenberger * The resultant obtained by Syvester's method is 247839ce1af63bf12fe7b3caa866970bbbb3afb13dDerek Sollenberger * 257839ce1af63bf12fe7b3caa866970bbbb3afb13dDerek Sollenberger * | a b (c - x) 0 | 267839ce1af63bf12fe7b3caa866970bbbb3afb13dDerek Sollenberger * | 0 a b (c - x) | 277839ce1af63bf12fe7b3caa866970bbbb3afb13dDerek Sollenberger * | d e (f - y) 0 | 287839ce1af63bf12fe7b3caa866970bbbb3afb13dDerek Sollenberger * | 0 d e (f - y) | 297839ce1af63bf12fe7b3caa866970bbbb3afb13dDerek Sollenberger * 307839ce1af63bf12fe7b3caa866970bbbb3afb13dDerek Sollenberger * which expands to 317839ce1af63bf12fe7b3caa866970bbbb3afb13dDerek Sollenberger * 327839ce1af63bf12fe7b3caa866970bbbb3afb13dDerek Sollenberger * d*d*x*x + -2*a*d*x*y + a*a*y*y 337839ce1af63bf12fe7b3caa866970bbbb3afb13dDerek Sollenberger * + (-2*c*d*d + b*e*d - a*e*e + 2*a*f*d)*x 347839ce1af63bf12fe7b3caa866970bbbb3afb13dDerek Sollenberger * + (-2*f*a*a + e*b*a - d*b*b + 2*d*c*a)*y 357839ce1af63bf12fe7b3caa866970bbbb3afb13dDerek Sollenberger * + 367839ce1af63bf12fe7b3caa866970bbbb3afb13dDerek Sollenberger * | a b c 0 | 377839ce1af63bf12fe7b3caa866970bbbb3afb13dDerek Sollenberger * | 0 a b c | == 0. 387839ce1af63bf12fe7b3caa866970bbbb3afb13dDerek Sollenberger * | d e f 0 | 397839ce1af63bf12fe7b3caa866970bbbb3afb13dDerek Sollenberger * | 0 d e f | 407839ce1af63bf12fe7b3caa866970bbbb3afb13dDerek Sollenberger * 417839ce1af63bf12fe7b3caa866970bbbb3afb13dDerek Sollenberger * Expanding the constant determinant results in 427839ce1af63bf12fe7b3caa866970bbbb3afb13dDerek Sollenberger * 437839ce1af63bf12fe7b3caa866970bbbb3afb13dDerek Sollenberger * | a b c | | b c 0 | 447839ce1af63bf12fe7b3caa866970bbbb3afb13dDerek Sollenberger * a*| e f 0 | + d*| a b c | == 457839ce1af63bf12fe7b3caa866970bbbb3afb13dDerek Sollenberger * | d e f | | d e f | 467839ce1af63bf12fe7b3caa866970bbbb3afb13dDerek Sollenberger * 477839ce1af63bf12fe7b3caa866970bbbb3afb13dDerek Sollenberger * 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) 487839ce1af63bf12fe7b3caa866970bbbb3afb13dDerek Sollenberger * 497839ce1af63bf12fe7b3caa866970bbbb3afb13dDerek Sollenberger */ 507839ce1af63bf12fe7b3caa866970bbbb3afb13dDerek Sollenberger 517839ce1af63bf12fe7b3caa866970bbbb3afb13dDerek Sollenberger// use the tricky arithmetic path, but leave the original to compare just in case 527839ce1af63bf12fe7b3caa866970bbbb3afb13dDerek Sollenbergerstatic bool straight_forward = false; 537839ce1af63bf12fe7b3caa866970bbbb3afb13dDerek Sollenberger 547839ce1af63bf12fe7b3caa866970bbbb3afb13dDerek SollenbergerSkDQuadImplicit::SkDQuadImplicit(const SkDQuad& q) { 557839ce1af63bf12fe7b3caa866970bbbb3afb13dDerek Sollenberger double a, b, c; 567839ce1af63bf12fe7b3caa866970bbbb3afb13dDerek Sollenberger SkDQuad::SetABC(&q[0].fX, &a, &b, &c); 577839ce1af63bf12fe7b3caa866970bbbb3afb13dDerek Sollenberger double d, e, f; 587839ce1af63bf12fe7b3caa866970bbbb3afb13dDerek Sollenberger SkDQuad::SetABC(&q[0].fY, &d, &e, &f); 597839ce1af63bf12fe7b3caa866970bbbb3afb13dDerek Sollenberger // compute the implicit coefficients 607839ce1af63bf12fe7b3caa866970bbbb3afb13dDerek Sollenberger if (straight_forward) { // 42 muls, 13 adds 617839ce1af63bf12fe7b3caa866970bbbb3afb13dDerek Sollenberger fP[kXx_Coeff] = d * d; 627839ce1af63bf12fe7b3caa866970bbbb3afb13dDerek Sollenberger fP[kXy_Coeff] = -2 * a * d; 637839ce1af63bf12fe7b3caa866970bbbb3afb13dDerek Sollenberger fP[kYy_Coeff] = a * a; 647839ce1af63bf12fe7b3caa866970bbbb3afb13dDerek Sollenberger fP[kX_Coeff] = -2*c*d*d + b*e*d - a*e*e + 2*a*f*d; 657839ce1af63bf12fe7b3caa866970bbbb3afb13dDerek Sollenberger fP[kY_Coeff] = -2*f*a*a + e*b*a - d*b*b + 2*d*c*a; 667839ce1af63bf12fe7b3caa866970bbbb3afb13dDerek Sollenberger fP[kC_Coeff] = a*(a*f*f + c*e*e - c*f*d - b*e*f) 677839ce1af63bf12fe7b3caa866970bbbb3afb13dDerek Sollenberger + d*(b*b*f + c*c*d - c*a*f - c*e*b); 687839ce1af63bf12fe7b3caa866970bbbb3afb13dDerek Sollenberger } else { // 26 muls, 11 adds 697839ce1af63bf12fe7b3caa866970bbbb3afb13dDerek Sollenberger double aa = a * a; 707839ce1af63bf12fe7b3caa866970bbbb3afb13dDerek Sollenberger double ad = a * d; 717839ce1af63bf12fe7b3caa866970bbbb3afb13dDerek Sollenberger double dd = d * d; 727839ce1af63bf12fe7b3caa866970bbbb3afb13dDerek Sollenberger fP[kXx_Coeff] = dd; 737839ce1af63bf12fe7b3caa866970bbbb3afb13dDerek Sollenberger fP[kXy_Coeff] = -2 * ad; 747839ce1af63bf12fe7b3caa866970bbbb3afb13dDerek Sollenberger fP[kYy_Coeff] = aa; 757839ce1af63bf12fe7b3caa866970bbbb3afb13dDerek Sollenberger double be = b * e; 767839ce1af63bf12fe7b3caa866970bbbb3afb13dDerek Sollenberger double bde = be * d; 777839ce1af63bf12fe7b3caa866970bbbb3afb13dDerek Sollenberger double cdd = c * dd; 787839ce1af63bf12fe7b3caa866970bbbb3afb13dDerek Sollenberger double ee = e * e; 797839ce1af63bf12fe7b3caa866970bbbb3afb13dDerek Sollenberger fP[kX_Coeff] = -2*cdd + bde - a*ee + 2*ad*f; 807839ce1af63bf12fe7b3caa866970bbbb3afb13dDerek Sollenberger double aaf = aa * f; 817839ce1af63bf12fe7b3caa866970bbbb3afb13dDerek Sollenberger double abe = a * be; 827839ce1af63bf12fe7b3caa866970bbbb3afb13dDerek Sollenberger double ac = a * c; 837839ce1af63bf12fe7b3caa866970bbbb3afb13dDerek Sollenberger double bb_2ac = b*b - 2*ac; 847839ce1af63bf12fe7b3caa866970bbbb3afb13dDerek Sollenberger fP[kY_Coeff] = -2*aaf + abe - d*bb_2ac; 857839ce1af63bf12fe7b3caa866970bbbb3afb13dDerek Sollenberger fP[kC_Coeff] = aaf*f + ac*ee + d*f*bb_2ac - abe*f + c*cdd - c*bde; 867839ce1af63bf12fe7b3caa866970bbbb3afb13dDerek Sollenberger } 877839ce1af63bf12fe7b3caa866970bbbb3afb13dDerek Sollenberger} 887839ce1af63bf12fe7b3caa866970bbbb3afb13dDerek Sollenberger 897839ce1af63bf12fe7b3caa866970bbbb3afb13dDerek Sollenberger /* Given a pair of quadratics, determine their parametric coefficients. 907839ce1af63bf12fe7b3caa866970bbbb3afb13dDerek Sollenberger * If the scaled coefficients are nearly equal, then the part of the quadratics 917839ce1af63bf12fe7b3caa866970bbbb3afb13dDerek Sollenberger * may be coincident. 927839ce1af63bf12fe7b3caa866970bbbb3afb13dDerek Sollenberger * OPTIMIZATION -- since comparison short-circuits on no match, 937839ce1af63bf12fe7b3caa866970bbbb3afb13dDerek Sollenberger * lazily compute the coefficients, comparing the easiest to compute first. 947839ce1af63bf12fe7b3caa866970bbbb3afb13dDerek Sollenberger * xx and yy first; then xy; and so on. 957839ce1af63bf12fe7b3caa866970bbbb3afb13dDerek Sollenberger */ 967839ce1af63bf12fe7b3caa866970bbbb3afb13dDerek Sollenbergerbool SkDQuadImplicit::match(const SkDQuadImplicit& p2) const { 977839ce1af63bf12fe7b3caa866970bbbb3afb13dDerek Sollenberger int first = 0; 987839ce1af63bf12fe7b3caa866970bbbb3afb13dDerek Sollenberger for (int index = 0; index <= kC_Coeff; ++index) { 997839ce1af63bf12fe7b3caa866970bbbb3afb13dDerek Sollenberger if (approximately_zero(fP[index]) && approximately_zero(p2.fP[index])) { 1007839ce1af63bf12fe7b3caa866970bbbb3afb13dDerek Sollenberger first += first == index; 1017839ce1af63bf12fe7b3caa866970bbbb3afb13dDerek Sollenberger continue; 1027839ce1af63bf12fe7b3caa866970bbbb3afb13dDerek Sollenberger } 1037839ce1af63bf12fe7b3caa866970bbbb3afb13dDerek Sollenberger if (first == index) { 1047839ce1af63bf12fe7b3caa866970bbbb3afb13dDerek Sollenberger continue; 1057839ce1af63bf12fe7b3caa866970bbbb3afb13dDerek Sollenberger } 1060a657bbc2c6fc9daf699942e023050536d5ec95fDerek Sollenberger if (!AlmostDequalUlps(fP[index] * p2.fP[first], fP[first] * p2.fP[index])) { 1077839ce1af63bf12fe7b3caa866970bbbb3afb13dDerek Sollenberger return false; 1087839ce1af63bf12fe7b3caa866970bbbb3afb13dDerek Sollenberger } 1097839ce1af63bf12fe7b3caa866970bbbb3afb13dDerek Sollenberger } 1107839ce1af63bf12fe7b3caa866970bbbb3afb13dDerek Sollenberger return true; 1117839ce1af63bf12fe7b3caa866970bbbb3afb13dDerek Sollenberger} 1127839ce1af63bf12fe7b3caa866970bbbb3afb13dDerek Sollenberger 1137839ce1af63bf12fe7b3caa866970bbbb3afb13dDerek Sollenbergerbool SkDQuadImplicit::Match(const SkDQuad& quad1, const SkDQuad& quad2) { 1147839ce1af63bf12fe7b3caa866970bbbb3afb13dDerek Sollenberger SkDQuadImplicit i1(quad1); // a'xx , b'xy , c'yy , d'x , e'y , f 1157839ce1af63bf12fe7b3caa866970bbbb3afb13dDerek Sollenberger SkDQuadImplicit i2(quad2); 1167839ce1af63bf12fe7b3caa866970bbbb3afb13dDerek Sollenberger return i1.match(i2); 1177839ce1af63bf12fe7b3caa866970bbbb3afb13dDerek Sollenberger} 118