1fe17456d5e528078ce69b5f15cf7adf1fab963fandroid-build-team Robot/* 2fe17456d5e528078ce69b5f15cf7adf1fab963fandroid-build-team Robot * Copyright 2012 Google Inc. 3fe17456d5e528078ce69b5f15cf7adf1fab963fandroid-build-team Robot * 4fe17456d5e528078ce69b5f15cf7adf1fab963fandroid-build-team Robot * Use of this source code is governed by a BSD-style license that can be 5fe17456d5e528078ce69b5f15cf7adf1fab963fandroid-build-team Robot * found in the LICENSE file. 6fe17456d5e528078ce69b5f15cf7adf1fab963fandroid-build-team Robot */ 7fe17456d5e528078ce69b5f15cf7adf1fab963fandroid-build-team Robot 8fe17456d5e528078ce69b5f15cf7adf1fab963fandroid-build-team Robot#ifndef SkLineParameters_DEFINED 9fe17456d5e528078ce69b5f15cf7adf1fab963fandroid-build-team Robot#define SkLineParameters_DEFINED 10fe17456d5e528078ce69b5f15cf7adf1fab963fandroid-build-team Robot 11fe17456d5e528078ce69b5f15cf7adf1fab963fandroid-build-team Robot#include "SkPathOpsCubic.h" 12fe17456d5e528078ce69b5f15cf7adf1fab963fandroid-build-team Robot#include "SkPathOpsLine.h" 13fe17456d5e528078ce69b5f15cf7adf1fab963fandroid-build-team Robot#include "SkPathOpsQuad.h" 14fe17456d5e528078ce69b5f15cf7adf1fab963fandroid-build-team Robot 15fe17456d5e528078ce69b5f15cf7adf1fab963fandroid-build-team Robot// Sources 16fe17456d5e528078ce69b5f15cf7adf1fab963fandroid-build-team Robot// computer-aided design - volume 22 number 9 november 1990 pp 538 - 549 17fe17456d5e528078ce69b5f15cf7adf1fab963fandroid-build-team Robot// online at http://cagd.cs.byu.edu/~tom/papers/bezclip.pdf 18fe17456d5e528078ce69b5f15cf7adf1fab963fandroid-build-team Robot 19fe17456d5e528078ce69b5f15cf7adf1fab963fandroid-build-team Robot// This turns a line segment into a parameterized line, of the form 20fe17456d5e528078ce69b5f15cf7adf1fab963fandroid-build-team Robot// ax + by + c = 0 21fe17456d5e528078ce69b5f15cf7adf1fab963fandroid-build-team Robot// When a^2 + b^2 == 1, the line is normalized. 22fe17456d5e528078ce69b5f15cf7adf1fab963fandroid-build-team Robot// The distance to the line for (x, y) is d(x,y) = ax + by + c 23fe17456d5e528078ce69b5f15cf7adf1fab963fandroid-build-team Robot// 24fe17456d5e528078ce69b5f15cf7adf1fab963fandroid-build-team Robot// Note that the distances below are not necessarily normalized. To get the true 25fe17456d5e528078ce69b5f15cf7adf1fab963fandroid-build-team Robot// distance, it's necessary to either call normalize() after xxxEndPoints(), or 26fe17456d5e528078ce69b5f15cf7adf1fab963fandroid-build-team Robot// divide the result of xxxDistance() by sqrt(normalSquared()) 27fe17456d5e528078ce69b5f15cf7adf1fab963fandroid-build-team Robot 28fe17456d5e528078ce69b5f15cf7adf1fab963fandroid-build-team Robotclass SkLineParameters { 29fe17456d5e528078ce69b5f15cf7adf1fab963fandroid-build-team Robotpublic: 30fe17456d5e528078ce69b5f15cf7adf1fab963fandroid-build-team Robot 31fe17456d5e528078ce69b5f15cf7adf1fab963fandroid-build-team Robot bool cubicEndPoints(const SkDCubic& pts) { 32fe17456d5e528078ce69b5f15cf7adf1fab963fandroid-build-team Robot int endIndex = 1; 33fe17456d5e528078ce69b5f15cf7adf1fab963fandroid-build-team Robot cubicEndPoints(pts, 0, endIndex); 34fe17456d5e528078ce69b5f15cf7adf1fab963fandroid-build-team Robot if (dy() != 0) { 35fe17456d5e528078ce69b5f15cf7adf1fab963fandroid-build-team Robot return true; 36fe17456d5e528078ce69b5f15cf7adf1fab963fandroid-build-team Robot } 37fe17456d5e528078ce69b5f15cf7adf1fab963fandroid-build-team Robot if (dx() == 0) { 38fe17456d5e528078ce69b5f15cf7adf1fab963fandroid-build-team Robot cubicEndPoints(pts, 0, ++endIndex); 39fe17456d5e528078ce69b5f15cf7adf1fab963fandroid-build-team Robot SkASSERT(endIndex == 2); 40fe17456d5e528078ce69b5f15cf7adf1fab963fandroid-build-team Robot if (dy() != 0) { 41fe17456d5e528078ce69b5f15cf7adf1fab963fandroid-build-team Robot return true; 42fe17456d5e528078ce69b5f15cf7adf1fab963fandroid-build-team Robot } 43fe17456d5e528078ce69b5f15cf7adf1fab963fandroid-build-team Robot if (dx() == 0) { 44fe17456d5e528078ce69b5f15cf7adf1fab963fandroid-build-team Robot cubicEndPoints(pts, 0, ++endIndex); // line 45fe17456d5e528078ce69b5f15cf7adf1fab963fandroid-build-team Robot SkASSERT(endIndex == 3); 46fe17456d5e528078ce69b5f15cf7adf1fab963fandroid-build-team Robot return false; 47fe17456d5e528078ce69b5f15cf7adf1fab963fandroid-build-team Robot } 48fe17456d5e528078ce69b5f15cf7adf1fab963fandroid-build-team Robot } 49fe17456d5e528078ce69b5f15cf7adf1fab963fandroid-build-team Robot // FIXME: after switching to round sort, remove bumping fA 50fe17456d5e528078ce69b5f15cf7adf1fab963fandroid-build-team Robot if (dx() < 0) { // only worry about y bias when breaking cw/ccw tie 51fe17456d5e528078ce69b5f15cf7adf1fab963fandroid-build-team Robot return true; 52fe17456d5e528078ce69b5f15cf7adf1fab963fandroid-build-team Robot } 53fe17456d5e528078ce69b5f15cf7adf1fab963fandroid-build-team Robot // if cubic tangent is on x axis, look at next control point to break tie 54fe17456d5e528078ce69b5f15cf7adf1fab963fandroid-build-team Robot // control point may be approximate, so it must move significantly to account for error 55fe17456d5e528078ce69b5f15cf7adf1fab963fandroid-build-team Robot if (NotAlmostEqualUlps(pts[0].fY, pts[++endIndex].fY)) { 56fe17456d5e528078ce69b5f15cf7adf1fab963fandroid-build-team Robot if (pts[0].fY > pts[endIndex].fY) { 57fe17456d5e528078ce69b5f15cf7adf1fab963fandroid-build-team Robot fA = DBL_EPSILON; // push it from 0 to slightly negative (y() returns -a) 58fe17456d5e528078ce69b5f15cf7adf1fab963fandroid-build-team Robot } 59fe17456d5e528078ce69b5f15cf7adf1fab963fandroid-build-team Robot return true; 60fe17456d5e528078ce69b5f15cf7adf1fab963fandroid-build-team Robot } 61fe17456d5e528078ce69b5f15cf7adf1fab963fandroid-build-team Robot if (endIndex == 3) { 62fe17456d5e528078ce69b5f15cf7adf1fab963fandroid-build-team Robot return true; 63fe17456d5e528078ce69b5f15cf7adf1fab963fandroid-build-team Robot } 64fe17456d5e528078ce69b5f15cf7adf1fab963fandroid-build-team Robot SkASSERT(endIndex == 2); 65fe17456d5e528078ce69b5f15cf7adf1fab963fandroid-build-team Robot if (pts[0].fY > pts[3].fY) { 66fe17456d5e528078ce69b5f15cf7adf1fab963fandroid-build-team Robot fA = DBL_EPSILON; // push it from 0 to slightly negative (y() returns -a) 67fe17456d5e528078ce69b5f15cf7adf1fab963fandroid-build-team Robot } 68fe17456d5e528078ce69b5f15cf7adf1fab963fandroid-build-team Robot return true; 69fe17456d5e528078ce69b5f15cf7adf1fab963fandroid-build-team Robot } 70fe17456d5e528078ce69b5f15cf7adf1fab963fandroid-build-team Robot 71fe17456d5e528078ce69b5f15cf7adf1fab963fandroid-build-team Robot void cubicEndPoints(const SkDCubic& pts, int s, int e) { 72fe17456d5e528078ce69b5f15cf7adf1fab963fandroid-build-team Robot fA = pts[s].fY - pts[e].fY; 73fe17456d5e528078ce69b5f15cf7adf1fab963fandroid-build-team Robot fB = pts[e].fX - pts[s].fX; 74fe17456d5e528078ce69b5f15cf7adf1fab963fandroid-build-team Robot fC = pts[s].fX * pts[e].fY - pts[e].fX * pts[s].fY; 75fe17456d5e528078ce69b5f15cf7adf1fab963fandroid-build-team Robot } 76fe17456d5e528078ce69b5f15cf7adf1fab963fandroid-build-team Robot 77fe17456d5e528078ce69b5f15cf7adf1fab963fandroid-build-team Robot double cubicPart(const SkDCubic& part) { 78fe17456d5e528078ce69b5f15cf7adf1fab963fandroid-build-team Robot cubicEndPoints(part); 79fe17456d5e528078ce69b5f15cf7adf1fab963fandroid-build-team Robot if (part[0] == part[1] || ((const SkDLine& ) part[0]).nearRay(part[2])) { 80fe17456d5e528078ce69b5f15cf7adf1fab963fandroid-build-team Robot return pointDistance(part[3]); 81fe17456d5e528078ce69b5f15cf7adf1fab963fandroid-build-team Robot } 82fe17456d5e528078ce69b5f15cf7adf1fab963fandroid-build-team Robot return pointDistance(part[2]); 83fe17456d5e528078ce69b5f15cf7adf1fab963fandroid-build-team Robot } 84fe17456d5e528078ce69b5f15cf7adf1fab963fandroid-build-team Robot 85fe17456d5e528078ce69b5f15cf7adf1fab963fandroid-build-team Robot void lineEndPoints(const SkDLine& pts) { 86fe17456d5e528078ce69b5f15cf7adf1fab963fandroid-build-team Robot fA = pts[0].fY - pts[1].fY; 87fe17456d5e528078ce69b5f15cf7adf1fab963fandroid-build-team Robot fB = pts[1].fX - pts[0].fX; 88fe17456d5e528078ce69b5f15cf7adf1fab963fandroid-build-team Robot fC = pts[0].fX * pts[1].fY - pts[1].fX * pts[0].fY; 89fe17456d5e528078ce69b5f15cf7adf1fab963fandroid-build-team Robot } 90fe17456d5e528078ce69b5f15cf7adf1fab963fandroid-build-team Robot 91fe17456d5e528078ce69b5f15cf7adf1fab963fandroid-build-team Robot bool quadEndPoints(const SkDQuad& pts) { 92fe17456d5e528078ce69b5f15cf7adf1fab963fandroid-build-team Robot quadEndPoints(pts, 0, 1); 93fe17456d5e528078ce69b5f15cf7adf1fab963fandroid-build-team Robot if (dy() != 0) { 94fe17456d5e528078ce69b5f15cf7adf1fab963fandroid-build-team Robot return true; 95fe17456d5e528078ce69b5f15cf7adf1fab963fandroid-build-team Robot } 96fe17456d5e528078ce69b5f15cf7adf1fab963fandroid-build-team Robot if (dx() == 0) { 97fe17456d5e528078ce69b5f15cf7adf1fab963fandroid-build-team Robot quadEndPoints(pts, 0, 2); 98fe17456d5e528078ce69b5f15cf7adf1fab963fandroid-build-team Robot return false; 99fe17456d5e528078ce69b5f15cf7adf1fab963fandroid-build-team Robot } 100fe17456d5e528078ce69b5f15cf7adf1fab963fandroid-build-team Robot if (dx() < 0) { // only worry about y bias when breaking cw/ccw tie 101fe17456d5e528078ce69b5f15cf7adf1fab963fandroid-build-team Robot return true; 102fe17456d5e528078ce69b5f15cf7adf1fab963fandroid-build-team Robot } 103fe17456d5e528078ce69b5f15cf7adf1fab963fandroid-build-team Robot // FIXME: after switching to round sort, remove this 104fe17456d5e528078ce69b5f15cf7adf1fab963fandroid-build-team Robot if (pts[0].fY > pts[2].fY) { 105fe17456d5e528078ce69b5f15cf7adf1fab963fandroid-build-team Robot fA = DBL_EPSILON; 106fe17456d5e528078ce69b5f15cf7adf1fab963fandroid-build-team Robot } 107fe17456d5e528078ce69b5f15cf7adf1fab963fandroid-build-team Robot return true; 108fe17456d5e528078ce69b5f15cf7adf1fab963fandroid-build-team Robot } 109fe17456d5e528078ce69b5f15cf7adf1fab963fandroid-build-team Robot 110fe17456d5e528078ce69b5f15cf7adf1fab963fandroid-build-team Robot void quadEndPoints(const SkDQuad& pts, int s, int e) { 111fe17456d5e528078ce69b5f15cf7adf1fab963fandroid-build-team Robot fA = pts[s].fY - pts[e].fY; 112fe17456d5e528078ce69b5f15cf7adf1fab963fandroid-build-team Robot fB = pts[e].fX - pts[s].fX; 113fe17456d5e528078ce69b5f15cf7adf1fab963fandroid-build-team Robot fC = pts[s].fX * pts[e].fY - pts[e].fX * pts[s].fY; 114fe17456d5e528078ce69b5f15cf7adf1fab963fandroid-build-team Robot } 115fe17456d5e528078ce69b5f15cf7adf1fab963fandroid-build-team Robot 116fe17456d5e528078ce69b5f15cf7adf1fab963fandroid-build-team Robot double quadPart(const SkDQuad& part) { 117fe17456d5e528078ce69b5f15cf7adf1fab963fandroid-build-team Robot quadEndPoints(part); 118fe17456d5e528078ce69b5f15cf7adf1fab963fandroid-build-team Robot return pointDistance(part[2]); 119fe17456d5e528078ce69b5f15cf7adf1fab963fandroid-build-team Robot } 120fe17456d5e528078ce69b5f15cf7adf1fab963fandroid-build-team Robot 121fe17456d5e528078ce69b5f15cf7adf1fab963fandroid-build-team Robot double normalSquared() const { 122fe17456d5e528078ce69b5f15cf7adf1fab963fandroid-build-team Robot return fA * fA + fB * fB; 123fe17456d5e528078ce69b5f15cf7adf1fab963fandroid-build-team Robot } 124fe17456d5e528078ce69b5f15cf7adf1fab963fandroid-build-team Robot 125fe17456d5e528078ce69b5f15cf7adf1fab963fandroid-build-team Robot bool normalize() { 126fe17456d5e528078ce69b5f15cf7adf1fab963fandroid-build-team Robot double normal = sqrt(normalSquared()); 127fe17456d5e528078ce69b5f15cf7adf1fab963fandroid-build-team Robot if (approximately_zero(normal)) { 128fe17456d5e528078ce69b5f15cf7adf1fab963fandroid-build-team Robot fA = fB = fC = 0; 129fe17456d5e528078ce69b5f15cf7adf1fab963fandroid-build-team Robot return false; 130fe17456d5e528078ce69b5f15cf7adf1fab963fandroid-build-team Robot } 131fe17456d5e528078ce69b5f15cf7adf1fab963fandroid-build-team Robot double reciprocal = 1 / normal; 132fe17456d5e528078ce69b5f15cf7adf1fab963fandroid-build-team Robot fA *= reciprocal; 133fe17456d5e528078ce69b5f15cf7adf1fab963fandroid-build-team Robot fB *= reciprocal; 134fe17456d5e528078ce69b5f15cf7adf1fab963fandroid-build-team Robot fC *= reciprocal; 135fe17456d5e528078ce69b5f15cf7adf1fab963fandroid-build-team Robot return true; 136fe17456d5e528078ce69b5f15cf7adf1fab963fandroid-build-team Robot } 137fe17456d5e528078ce69b5f15cf7adf1fab963fandroid-build-team Robot 138fe17456d5e528078ce69b5f15cf7adf1fab963fandroid-build-team Robot void cubicDistanceY(const SkDCubic& pts, SkDCubic& distance) const { 139fe17456d5e528078ce69b5f15cf7adf1fab963fandroid-build-team Robot double oneThird = 1 / 3.0; 140fe17456d5e528078ce69b5f15cf7adf1fab963fandroid-build-team Robot for (int index = 0; index < 4; ++index) { 141fe17456d5e528078ce69b5f15cf7adf1fab963fandroid-build-team Robot distance[index].fX = index * oneThird; 142fe17456d5e528078ce69b5f15cf7adf1fab963fandroid-build-team Robot distance[index].fY = fA * pts[index].fX + fB * pts[index].fY + fC; 143fe17456d5e528078ce69b5f15cf7adf1fab963fandroid-build-team Robot } 144fe17456d5e528078ce69b5f15cf7adf1fab963fandroid-build-team Robot } 145fe17456d5e528078ce69b5f15cf7adf1fab963fandroid-build-team Robot 146fe17456d5e528078ce69b5f15cf7adf1fab963fandroid-build-team Robot void quadDistanceY(const SkDQuad& pts, SkDQuad& distance) const { 147fe17456d5e528078ce69b5f15cf7adf1fab963fandroid-build-team Robot double oneHalf = 1 / 2.0; 148fe17456d5e528078ce69b5f15cf7adf1fab963fandroid-build-team Robot for (int index = 0; index < 3; ++index) { 149fe17456d5e528078ce69b5f15cf7adf1fab963fandroid-build-team Robot distance[index].fX = index * oneHalf; 150fe17456d5e528078ce69b5f15cf7adf1fab963fandroid-build-team Robot distance[index].fY = fA * pts[index].fX + fB * pts[index].fY + fC; 151fe17456d5e528078ce69b5f15cf7adf1fab963fandroid-build-team Robot } 152fe17456d5e528078ce69b5f15cf7adf1fab963fandroid-build-team Robot } 153fe17456d5e528078ce69b5f15cf7adf1fab963fandroid-build-team Robot 154fe17456d5e528078ce69b5f15cf7adf1fab963fandroid-build-team Robot double controlPtDistance(const SkDCubic& pts, int index) const { 155fe17456d5e528078ce69b5f15cf7adf1fab963fandroid-build-team Robot SkASSERT(index == 1 || index == 2); 156fe17456d5e528078ce69b5f15cf7adf1fab963fandroid-build-team Robot return fA * pts[index].fX + fB * pts[index].fY + fC; 157fe17456d5e528078ce69b5f15cf7adf1fab963fandroid-build-team Robot } 158fe17456d5e528078ce69b5f15cf7adf1fab963fandroid-build-team Robot 159fe17456d5e528078ce69b5f15cf7adf1fab963fandroid-build-team Robot double controlPtDistance(const SkDQuad& pts) const { 160fe17456d5e528078ce69b5f15cf7adf1fab963fandroid-build-team Robot return fA * pts[1].fX + fB * pts[1].fY + fC; 161fe17456d5e528078ce69b5f15cf7adf1fab963fandroid-build-team Robot } 162fe17456d5e528078ce69b5f15cf7adf1fab963fandroid-build-team Robot 163fe17456d5e528078ce69b5f15cf7adf1fab963fandroid-build-team Robot double pointDistance(const SkDPoint& pt) const { 164fe17456d5e528078ce69b5f15cf7adf1fab963fandroid-build-team Robot return fA * pt.fX + fB * pt.fY + fC; 165fe17456d5e528078ce69b5f15cf7adf1fab963fandroid-build-team Robot } 166fe17456d5e528078ce69b5f15cf7adf1fab963fandroid-build-team Robot 167fe17456d5e528078ce69b5f15cf7adf1fab963fandroid-build-team Robot double dx() const { 168fe17456d5e528078ce69b5f15cf7adf1fab963fandroid-build-team Robot return fB; 169fe17456d5e528078ce69b5f15cf7adf1fab963fandroid-build-team Robot } 170fe17456d5e528078ce69b5f15cf7adf1fab963fandroid-build-team Robot 171fe17456d5e528078ce69b5f15cf7adf1fab963fandroid-build-team Robot double dy() const { 172fe17456d5e528078ce69b5f15cf7adf1fab963fandroid-build-team Robot return -fA; 173fe17456d5e528078ce69b5f15cf7adf1fab963fandroid-build-team Robot } 174fe17456d5e528078ce69b5f15cf7adf1fab963fandroid-build-team Robot 175fe17456d5e528078ce69b5f15cf7adf1fab963fandroid-build-team Robotprivate: 176fe17456d5e528078ce69b5f15cf7adf1fab963fandroid-build-team Robot double fA; 177fe17456d5e528078ce69b5f15cf7adf1fab963fandroid-build-team Robot double fB; 178fe17456d5e528078ce69b5f15cf7adf1fab963fandroid-build-team Robot double fC; 179fe17456d5e528078ce69b5f15cf7adf1fab963fandroid-build-team Robot}; 180fe17456d5e528078ce69b5f15cf7adf1fab963fandroid-build-team Robot 181fe17456d5e528078ce69b5f15cf7adf1fab963fandroid-build-team Robot#endif 182