1.1 --- /dev/null Thu Jan 01 00:00:00 1970 +0000
1.2 +++ b/gfx/skia/trunk/src/pathops/SkLineParameters.h Wed Dec 31 06:09:35 2014 +0100
1.3 @@ -0,0 +1,171 @@
1.4 +/*
1.5 + * Copyright 2012 Google Inc.
1.6 + *
1.7 + * Use of this source code is governed by a BSD-style license that can be
1.8 + * found in the LICENSE file.
1.9 + */
1.10 +#include "SkPathOpsCubic.h"
1.11 +#include "SkPathOpsLine.h"
1.12 +#include "SkPathOpsQuad.h"
1.13 +
1.14 +// Sources
1.15 +// computer-aided design - volume 22 number 9 november 1990 pp 538 - 549
1.16 +// online at http://cagd.cs.byu.edu/~tom/papers/bezclip.pdf
1.17 +
1.18 +// This turns a line segment into a parameterized line, of the form
1.19 +// ax + by + c = 0
1.20 +// When a^2 + b^2 == 1, the line is normalized.
1.21 +// The distance to the line for (x, y) is d(x,y) = ax + by + c
1.22 +//
1.23 +// Note that the distances below are not necessarily normalized. To get the true
1.24 +// distance, it's necessary to either call normalize() after xxxEndPoints(), or
1.25 +// divide the result of xxxDistance() by sqrt(normalSquared())
1.26 +
1.27 +class SkLineParameters {
1.28 +public:
1.29 +
1.30 + void cubicEndPoints(const SkDCubic& pts) {
1.31 + int endIndex = 1;
1.32 + cubicEndPoints(pts, 0, endIndex);
1.33 + if (dy() != 0) {
1.34 + return;
1.35 + }
1.36 + if (dx() == 0) {
1.37 + cubicEndPoints(pts, 0, ++endIndex);
1.38 + SkASSERT(endIndex == 2);
1.39 + if (dy() != 0) {
1.40 + return;
1.41 + }
1.42 + if (dx() == 0) {
1.43 + cubicEndPoints(pts, 0, ++endIndex); // line
1.44 + SkASSERT(endIndex == 3);
1.45 + return;
1.46 + }
1.47 + }
1.48 + if (dx() < 0) { // only worry about y bias when breaking cw/ccw tie
1.49 + return;
1.50 + }
1.51 + // if cubic tangent is on x axis, look at next control point to break tie
1.52 + // control point may be approximate, so it must move significantly to account for error
1.53 + if (NotAlmostEqualUlps(pts[0].fY, pts[++endIndex].fY)) {
1.54 + if (pts[0].fY > pts[endIndex].fY) {
1.55 + a = DBL_EPSILON; // push it from 0 to slightly negative (y() returns -a)
1.56 + }
1.57 + return;
1.58 + }
1.59 + if (endIndex == 3) {
1.60 + return;
1.61 + }
1.62 + SkASSERT(endIndex == 2);
1.63 + if (pts[0].fY > pts[3].fY) {
1.64 + a = DBL_EPSILON; // push it from 0 to slightly negative (y() returns -a)
1.65 + }
1.66 + }
1.67 +
1.68 + void cubicEndPoints(const SkDCubic& pts, int s, int e) {
1.69 + a = pts[s].fY - pts[e].fY;
1.70 + b = pts[e].fX - pts[s].fX;
1.71 + c = pts[s].fX * pts[e].fY - pts[e].fX * pts[s].fY;
1.72 + }
1.73 +
1.74 + double cubicPart(const SkDCubic& part) {
1.75 + cubicEndPoints(part);
1.76 + if (part[0] == part[1] || ((const SkDLine& ) part[0]).nearRay(part[2])) {
1.77 + return pointDistance(part[3]);
1.78 + }
1.79 + return pointDistance(part[2]);
1.80 + }
1.81 +
1.82 + void lineEndPoints(const SkDLine& pts) {
1.83 + a = pts[0].fY - pts[1].fY;
1.84 + b = pts[1].fX - pts[0].fX;
1.85 + c = pts[0].fX * pts[1].fY - pts[1].fX * pts[0].fY;
1.86 + }
1.87 +
1.88 + void quadEndPoints(const SkDQuad& pts) {
1.89 + quadEndPoints(pts, 0, 1);
1.90 + if (dy() != 0) {
1.91 + return;
1.92 + }
1.93 + if (dx() == 0) {
1.94 + quadEndPoints(pts, 0, 2);
1.95 + return;
1.96 + }
1.97 + if (dx() < 0) { // only worry about y bias when breaking cw/ccw tie
1.98 + return;
1.99 + }
1.100 + if (pts[0].fY > pts[2].fY) {
1.101 + a = DBL_EPSILON;
1.102 + }
1.103 + }
1.104 +
1.105 + void quadEndPoints(const SkDQuad& pts, int s, int e) {
1.106 + a = pts[s].fY - pts[e].fY;
1.107 + b = pts[e].fX - pts[s].fX;
1.108 + c = pts[s].fX * pts[e].fY - pts[e].fX * pts[s].fY;
1.109 + }
1.110 +
1.111 + double quadPart(const SkDQuad& part) {
1.112 + quadEndPoints(part);
1.113 + return pointDistance(part[2]);
1.114 + }
1.115 +
1.116 + double normalSquared() const {
1.117 + return a * a + b * b;
1.118 + }
1.119 +
1.120 + bool normalize() {
1.121 + double normal = sqrt(normalSquared());
1.122 + if (approximately_zero(normal)) {
1.123 + a = b = c = 0;
1.124 + return false;
1.125 + }
1.126 + double reciprocal = 1 / normal;
1.127 + a *= reciprocal;
1.128 + b *= reciprocal;
1.129 + c *= reciprocal;
1.130 + return true;
1.131 + }
1.132 +
1.133 + void cubicDistanceY(const SkDCubic& pts, SkDCubic& distance) const {
1.134 + double oneThird = 1 / 3.0;
1.135 + for (int index = 0; index < 4; ++index) {
1.136 + distance[index].fX = index * oneThird;
1.137 + distance[index].fY = a * pts[index].fX + b * pts[index].fY + c;
1.138 + }
1.139 + }
1.140 +
1.141 + void quadDistanceY(const SkDQuad& pts, SkDQuad& distance) const {
1.142 + double oneHalf = 1 / 2.0;
1.143 + for (int index = 0; index < 3; ++index) {
1.144 + distance[index].fX = index * oneHalf;
1.145 + distance[index].fY = a * pts[index].fX + b * pts[index].fY + c;
1.146 + }
1.147 + }
1.148 +
1.149 + double controlPtDistance(const SkDCubic& pts, int index) const {
1.150 + SkASSERT(index == 1 || index == 2);
1.151 + return a * pts[index].fX + b * pts[index].fY + c;
1.152 + }
1.153 +
1.154 + double controlPtDistance(const SkDQuad& pts) const {
1.155 + return a * pts[1].fX + b * pts[1].fY + c;
1.156 + }
1.157 +
1.158 + double pointDistance(const SkDPoint& pt) const {
1.159 + return a * pt.fX + b * pt.fY + c;
1.160 + }
1.161 +
1.162 + double dx() const {
1.163 + return b;
1.164 + }
1.165 +
1.166 + double dy() const {
1.167 + return -a;
1.168 + }
1.169 +
1.170 +private:
1.171 + double a;
1.172 + double b;
1.173 + double c;
1.174 +};
