123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181 |
- /*
- * Copyright 2012 Google Inc.
- *
- * Use of this source code is governed by a BSD-style license that can be
- * found in the LICENSE file.
- */
- #ifndef SkLineParameters_DEFINED
- #define SkLineParameters_DEFINED
- #include "src/pathops/SkPathOpsCubic.h"
- #include "src/pathops/SkPathOpsLine.h"
- #include "src/pathops/SkPathOpsQuad.h"
- // Sources
- // computer-aided design - volume 22 number 9 november 1990 pp 538 - 549
- // online at http://cagd.cs.byu.edu/~tom/papers/bezclip.pdf
- // This turns a line segment into a parameterized line, of the form
- // ax + by + c = 0
- // When a^2 + b^2 == 1, the line is normalized.
- // The distance to the line for (x, y) is d(x,y) = ax + by + c
- //
- // Note that the distances below are not necessarily normalized. To get the true
- // distance, it's necessary to either call normalize() after xxxEndPoints(), or
- // divide the result of xxxDistance() by sqrt(normalSquared())
- class SkLineParameters {
- public:
- bool cubicEndPoints(const SkDCubic& pts) {
- int endIndex = 1;
- cubicEndPoints(pts, 0, endIndex);
- if (dy() != 0) {
- return true;
- }
- if (dx() == 0) {
- cubicEndPoints(pts, 0, ++endIndex);
- SkASSERT(endIndex == 2);
- if (dy() != 0) {
- return true;
- }
- if (dx() == 0) {
- cubicEndPoints(pts, 0, ++endIndex); // line
- SkASSERT(endIndex == 3);
- return false;
- }
- }
- // FIXME: after switching to round sort, remove bumping fA
- if (dx() < 0) { // only worry about y bias when breaking cw/ccw tie
- return true;
- }
- // if cubic tangent is on x axis, look at next control point to break tie
- // control point may be approximate, so it must move significantly to account for error
- if (NotAlmostEqualUlps(pts[0].fY, pts[++endIndex].fY)) {
- if (pts[0].fY > pts[endIndex].fY) {
- fA = DBL_EPSILON; // push it from 0 to slightly negative (y() returns -a)
- }
- return true;
- }
- if (endIndex == 3) {
- return true;
- }
- SkASSERT(endIndex == 2);
- if (pts[0].fY > pts[3].fY) {
- fA = DBL_EPSILON; // push it from 0 to slightly negative (y() returns -a)
- }
- return true;
- }
- void cubicEndPoints(const SkDCubic& pts, int s, int e) {
- fA = pts[s].fY - pts[e].fY;
- fB = pts[e].fX - pts[s].fX;
- fC = pts[s].fX * pts[e].fY - pts[e].fX * pts[s].fY;
- }
- double cubicPart(const SkDCubic& part) {
- cubicEndPoints(part);
- if (part[0] == part[1] || ((const SkDLine& ) part[0]).nearRay(part[2])) {
- return pointDistance(part[3]);
- }
- return pointDistance(part[2]);
- }
- void lineEndPoints(const SkDLine& pts) {
- fA = pts[0].fY - pts[1].fY;
- fB = pts[1].fX - pts[0].fX;
- fC = pts[0].fX * pts[1].fY - pts[1].fX * pts[0].fY;
- }
- bool quadEndPoints(const SkDQuad& pts) {
- quadEndPoints(pts, 0, 1);
- if (dy() != 0) {
- return true;
- }
- if (dx() == 0) {
- quadEndPoints(pts, 0, 2);
- return false;
- }
- if (dx() < 0) { // only worry about y bias when breaking cw/ccw tie
- return true;
- }
- // FIXME: after switching to round sort, remove this
- if (pts[0].fY > pts[2].fY) {
- fA = DBL_EPSILON;
- }
- return true;
- }
- void quadEndPoints(const SkDQuad& pts, int s, int e) {
- fA = pts[s].fY - pts[e].fY;
- fB = pts[e].fX - pts[s].fX;
- fC = pts[s].fX * pts[e].fY - pts[e].fX * pts[s].fY;
- }
- double quadPart(const SkDQuad& part) {
- quadEndPoints(part);
- return pointDistance(part[2]);
- }
- double normalSquared() const {
- return fA * fA + fB * fB;
- }
- bool normalize() {
- double normal = sqrt(normalSquared());
- if (approximately_zero(normal)) {
- fA = fB = fC = 0;
- return false;
- }
- double reciprocal = 1 / normal;
- fA *= reciprocal;
- fB *= reciprocal;
- fC *= reciprocal;
- return true;
- }
- void cubicDistanceY(const SkDCubic& pts, SkDCubic& distance) const {
- double oneThird = 1 / 3.0;
- for (int index = 0; index < 4; ++index) {
- distance[index].fX = index * oneThird;
- distance[index].fY = fA * pts[index].fX + fB * pts[index].fY + fC;
- }
- }
- void quadDistanceY(const SkDQuad& pts, SkDQuad& distance) const {
- double oneHalf = 1 / 2.0;
- for (int index = 0; index < 3; ++index) {
- distance[index].fX = index * oneHalf;
- distance[index].fY = fA * pts[index].fX + fB * pts[index].fY + fC;
- }
- }
- double controlPtDistance(const SkDCubic& pts, int index) const {
- SkASSERT(index == 1 || index == 2);
- return fA * pts[index].fX + fB * pts[index].fY + fC;
- }
- double controlPtDistance(const SkDQuad& pts) const {
- return fA * pts[1].fX + fB * pts[1].fY + fC;
- }
- double pointDistance(const SkDPoint& pt) const {
- return fA * pt.fX + fB * pt.fY + fC;
- }
- double dx() const {
- return fB;
- }
- double dy() const {
- return -fA;
- }
- private:
- double fA;
- double fB;
- double fC;
- };
- #endif
|