107393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com/* 207393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com * Copyright 2012 Google Inc. 307393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com * 407393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com * Use of this source code is governed by a BSD-style license that can be 507393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com * found in the LICENSE file. 607393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com */ 79eb182ac4bcdc38f71a603ba958ff889fbbf5d77george 89eb182ac4bcdc38f71a603ba958ff889fbbf5d77george#ifndef SkLineParameters_DEFINED 99eb182ac4bcdc38f71a603ba958ff889fbbf5d77george#define SkLineParameters_DEFINED 109eb182ac4bcdc38f71a603ba958ff889fbbf5d77george 1107393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com#include "SkPathOpsCubic.h" 1207393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com#include "SkPathOpsLine.h" 1307393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com#include "SkPathOpsQuad.h" 1407393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com 1507393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com// Sources 1607393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com// computer-aided design - volume 22 number 9 november 1990 pp 538 - 549 1707393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com// online at http://cagd.cs.byu.edu/~tom/papers/bezclip.pdf 1807393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com 1907393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com// This turns a line segment into a parameterized line, of the form 2007393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com// ax + by + c = 0 2107393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com// When a^2 + b^2 == 1, the line is normalized. 2207393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com// The distance to the line for (x, y) is d(x,y) = ax + by + c 2307393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com// 2407393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com// Note that the distances below are not necessarily normalized. To get the true 2507393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com// distance, it's necessary to either call normalize() after xxxEndPoints(), or 2607393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com// divide the result of xxxDistance() by sqrt(normalSquared()) 2707393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com 2807393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.comclass SkLineParameters { 2907393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.compublic: 30866f4e34a943c115ac372c22123a1520aa5f9b06commit-bot@chromium.org 314431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org bool cubicEndPoints(const SkDCubic& pts) { 32866f4e34a943c115ac372c22123a1520aa5f9b06commit-bot@chromium.org int endIndex = 1; 33866f4e34a943c115ac372c22123a1520aa5f9b06commit-bot@chromium.org cubicEndPoints(pts, 0, endIndex); 34866f4e34a943c115ac372c22123a1520aa5f9b06commit-bot@chromium.org if (dy() != 0) { 354431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org return true; 36866f4e34a943c115ac372c22123a1520aa5f9b06commit-bot@chromium.org } 37866f4e34a943c115ac372c22123a1520aa5f9b06commit-bot@chromium.org if (dx() == 0) { 38866f4e34a943c115ac372c22123a1520aa5f9b06commit-bot@chromium.org cubicEndPoints(pts, 0, ++endIndex); 39866f4e34a943c115ac372c22123a1520aa5f9b06commit-bot@chromium.org SkASSERT(endIndex == 2); 40866f4e34a943c115ac372c22123a1520aa5f9b06commit-bot@chromium.org if (dy() != 0) { 414431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org return true; 42866f4e34a943c115ac372c22123a1520aa5f9b06commit-bot@chromium.org } 43866f4e34a943c115ac372c22123a1520aa5f9b06commit-bot@chromium.org if (dx() == 0) { 44866f4e34a943c115ac372c22123a1520aa5f9b06commit-bot@chromium.org cubicEndPoints(pts, 0, ++endIndex); // line 45866f4e34a943c115ac372c22123a1520aa5f9b06commit-bot@chromium.org SkASSERT(endIndex == 3); 464431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org return false; 47866f4e34a943c115ac372c22123a1520aa5f9b06commit-bot@chromium.org } 48866f4e34a943c115ac372c22123a1520aa5f9b06commit-bot@chromium.org } 494431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org // FIXME: after switching to round sort, remove bumping fA 50866f4e34a943c115ac372c22123a1520aa5f9b06commit-bot@chromium.org if (dx() < 0) { // only worry about y bias when breaking cw/ccw tie 514431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org return true; 52866f4e34a943c115ac372c22123a1520aa5f9b06commit-bot@chromium.org } 53866f4e34a943c115ac372c22123a1520aa5f9b06commit-bot@chromium.org // if cubic tangent is on x axis, look at next control point to break tie 54866f4e34a943c115ac372c22123a1520aa5f9b06commit-bot@chromium.org // control point may be approximate, so it must move significantly to account for error 55866f4e34a943c115ac372c22123a1520aa5f9b06commit-bot@chromium.org if (NotAlmostEqualUlps(pts[0].fY, pts[++endIndex].fY)) { 56866f4e34a943c115ac372c22123a1520aa5f9b06commit-bot@chromium.org if (pts[0].fY > pts[endIndex].fY) { 574431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org fA = DBL_EPSILON; // push it from 0 to slightly negative (y() returns -a) 58cffbcc3b9665f2c928544b6fc6b8a0e22a4210fbcaryclark@google.com } 594431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org return true; 60866f4e34a943c115ac372c22123a1520aa5f9b06commit-bot@chromium.org } 61866f4e34a943c115ac372c22123a1520aa5f9b06commit-bot@chromium.org if (endIndex == 3) { 624431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org return true; 63866f4e34a943c115ac372c22123a1520aa5f9b06commit-bot@chromium.org } 64866f4e34a943c115ac372c22123a1520aa5f9b06commit-bot@chromium.org SkASSERT(endIndex == 2); 65866f4e34a943c115ac372c22123a1520aa5f9b06commit-bot@chromium.org if (pts[0].fY > pts[3].fY) { 664431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org fA = DBL_EPSILON; // push it from 0 to slightly negative (y() returns -a) 67cffbcc3b9665f2c928544b6fc6b8a0e22a4210fbcaryclark@google.com } 684431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org return true; 6907393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com } 7007393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com 7107393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com void cubicEndPoints(const SkDCubic& pts, int s, int e) { 724431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org fA = pts[s].fY - pts[e].fY; 734431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org fB = pts[e].fX - pts[s].fX; 744431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org fC = pts[s].fX * pts[e].fY - pts[e].fX * pts[s].fY; 7507393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com } 7607393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com 77570863f2e22b8ea7d7c504bd15e4f766af097df2caryclark@google.com double cubicPart(const SkDCubic& part) { 78570863f2e22b8ea7d7c504bd15e4f766af097df2caryclark@google.com cubicEndPoints(part); 79570863f2e22b8ea7d7c504bd15e4f766af097df2caryclark@google.com if (part[0] == part[1] || ((const SkDLine& ) part[0]).nearRay(part[2])) { 80570863f2e22b8ea7d7c504bd15e4f766af097df2caryclark@google.com return pointDistance(part[3]); 81570863f2e22b8ea7d7c504bd15e4f766af097df2caryclark@google.com } 82570863f2e22b8ea7d7c504bd15e4f766af097df2caryclark@google.com return pointDistance(part[2]); 83570863f2e22b8ea7d7c504bd15e4f766af097df2caryclark@google.com } 84570863f2e22b8ea7d7c504bd15e4f766af097df2caryclark@google.com 8507393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com void lineEndPoints(const SkDLine& pts) { 864431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org fA = pts[0].fY - pts[1].fY; 874431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org fB = pts[1].fX - pts[0].fX; 884431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org fC = pts[0].fX * pts[1].fY - pts[1].fX * pts[0].fY; 8907393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com } 9007393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com 914431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org bool quadEndPoints(const SkDQuad& pts) { 92cffbcc3b9665f2c928544b6fc6b8a0e22a4210fbcaryclark@google.com quadEndPoints(pts, 0, 1); 93866f4e34a943c115ac372c22123a1520aa5f9b06commit-bot@chromium.org if (dy() != 0) { 944431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org return true; 95866f4e34a943c115ac372c22123a1520aa5f9b06commit-bot@chromium.org } 96866f4e34a943c115ac372c22123a1520aa5f9b06commit-bot@chromium.org if (dx() == 0) { 97cffbcc3b9665f2c928544b6fc6b8a0e22a4210fbcaryclark@google.com quadEndPoints(pts, 0, 2); 984431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org return false; 99866f4e34a943c115ac372c22123a1520aa5f9b06commit-bot@chromium.org } 100866f4e34a943c115ac372c22123a1520aa5f9b06commit-bot@chromium.org if (dx() < 0) { // only worry about y bias when breaking cw/ccw tie 1014431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org return true; 102866f4e34a943c115ac372c22123a1520aa5f9b06commit-bot@chromium.org } 1034431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org // FIXME: after switching to round sort, remove this 104866f4e34a943c115ac372c22123a1520aa5f9b06commit-bot@chromium.org if (pts[0].fY > pts[2].fY) { 1054431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org fA = DBL_EPSILON; 106cffbcc3b9665f2c928544b6fc6b8a0e22a4210fbcaryclark@google.com } 1074431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org return true; 10807393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com } 10907393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com 11007393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com void quadEndPoints(const SkDQuad& pts, int s, int e) { 1114431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org fA = pts[s].fY - pts[e].fY; 1124431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org fB = pts[e].fX - pts[s].fX; 1134431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org fC = pts[s].fX * pts[e].fY - pts[e].fX * pts[s].fY; 11407393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com } 11507393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com 116570863f2e22b8ea7d7c504bd15e4f766af097df2caryclark@google.com double quadPart(const SkDQuad& part) { 117570863f2e22b8ea7d7c504bd15e4f766af097df2caryclark@google.com quadEndPoints(part); 118570863f2e22b8ea7d7c504bd15e4f766af097df2caryclark@google.com return pointDistance(part[2]); 119570863f2e22b8ea7d7c504bd15e4f766af097df2caryclark@google.com } 120570863f2e22b8ea7d7c504bd15e4f766af097df2caryclark@google.com 12107393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com double normalSquared() const { 1224431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org return fA * fA + fB * fB; 12307393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com } 12407393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com 12507393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com bool normalize() { 12607393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com double normal = sqrt(normalSquared()); 12707393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com if (approximately_zero(normal)) { 1284431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org fA = fB = fC = 0; 12907393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com return false; 13007393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com } 13107393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com double reciprocal = 1 / normal; 1324431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org fA *= reciprocal; 1334431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org fB *= reciprocal; 1344431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org fC *= reciprocal; 13507393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com return true; 13607393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com } 13707393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com 13807393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com void cubicDistanceY(const SkDCubic& pts, SkDCubic& distance) const { 13907393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com double oneThird = 1 / 3.0; 14007393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com for (int index = 0; index < 4; ++index) { 14107393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com distance[index].fX = index * oneThird; 1424431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org distance[index].fY = fA * pts[index].fX + fB * pts[index].fY + fC; 14307393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com } 14407393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com } 14507393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com 14607393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com void quadDistanceY(const SkDQuad& pts, SkDQuad& distance) const { 14707393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com double oneHalf = 1 / 2.0; 14807393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com for (int index = 0; index < 3; ++index) { 14907393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com distance[index].fX = index * oneHalf; 1504431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org distance[index].fY = fA * pts[index].fX + fB * pts[index].fY + fC; 15107393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com } 15207393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com } 15307393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com 15407393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com double controlPtDistance(const SkDCubic& pts, int index) const { 15507393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com SkASSERT(index == 1 || index == 2); 1564431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org return fA * pts[index].fX + fB * pts[index].fY + fC; 15707393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com } 15807393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com 15907393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com double controlPtDistance(const SkDQuad& pts) const { 1604431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org return fA * pts[1].fX + fB * pts[1].fY + fC; 16107393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com } 16207393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com 16307393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com double pointDistance(const SkDPoint& pt) const { 1644431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org return fA * pt.fX + fB * pt.fY + fC; 16507393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com } 16607393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com 16707393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com double dx() const { 1684431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org return fB; 16907393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com } 17007393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com 17107393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com double dy() const { 1724431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org return -fA; 17307393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com } 17407393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com 17507393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.comprivate: 1764431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org double fA; 1774431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org double fB; 1784431e7757cfcb8cfa99535eed0e9f156dabf95c2commit-bot@chromium.org double fC; 17907393cab57ce74a4aae89a31fae9aaa9780fc19dcaryclark@google.com}; 1809eb182ac4bcdc38f71a603ba958ff889fbbf5d77george 1819eb182ac4bcdc38f71a603ba958ff889fbbf5d77george#endif 182