caryclark@google.com | 9e49fb6 | 2012-08-27 14:11:33 +0000 | [diff] [blame] | 1 | /* |
| 2 | * Copyright 2012 Google Inc. |
| 3 | * |
| 4 | * Use of this source code is governed by a BSD-style license that can be |
| 5 | * found in the LICENSE file. |
| 6 | */ |
caryclark@google.com | 639df89 | 2012-01-10 21:46:10 +0000 | [diff] [blame] | 7 | #include "DataTypes.h" |
| 8 | |
| 9 | // Sources |
| 10 | // computer-aided design - volume 22 number 9 november 1990 pp 538 - 549 |
| 11 | // online at http://cagd.cs.byu.edu/~tom/papers/bezclip.pdf |
| 12 | |
caryclark@google.com | b45a1b4 | 2012-05-18 20:50:33 +0000 | [diff] [blame] | 13 | // This turns a line segment into a parameterized line, of the form |
| 14 | // ax + by + c = 0 |
| 15 | // When a^2 + b^2 == 1, the line is normalized. |
| 16 | // The distance to the line for (x, y) is d(x,y) = ax + by + c |
| 17 | // |
| 18 | // Note that the distances below are not necessarily normalized. To get the true |
| 19 | // distance, it's necessary to either call normalize() after xxxEndPoints(), or |
| 20 | // divide the result of xxxDistance() by sqrt(normalSquared()) |
| 21 | |
caryclark@google.com | 639df89 | 2012-01-10 21:46:10 +0000 | [diff] [blame] | 22 | class LineParameters { |
| 23 | public: |
| 24 | void cubicEndPoints(const Cubic& pts) { |
caryclark@google.com | 32546db | 2012-08-31 20:55:07 +0000 | [diff] [blame] | 25 | cubicEndPoints(pts, 0, 3); |
caryclark@google.com | 639df89 | 2012-01-10 21:46:10 +0000 | [diff] [blame] | 26 | } |
rmistry@google.com | d6176b0 | 2012-08-23 18:14:13 +0000 | [diff] [blame] | 27 | |
caryclark@google.com | 639df89 | 2012-01-10 21:46:10 +0000 | [diff] [blame] | 28 | void cubicEndPoints(const Cubic& pts, int s, int e) { |
caryclark@google.com | 32546db | 2012-08-31 20:55:07 +0000 | [diff] [blame] | 29 | a = approximately_pin(pts[s].y - pts[e].y); |
| 30 | b = approximately_pin(pts[e].x - pts[s].x); |
caryclark@google.com | 639df89 | 2012-01-10 21:46:10 +0000 | [diff] [blame] | 31 | c = pts[s].x * pts[e].y - pts[e].x * pts[s].y; |
| 32 | } |
rmistry@google.com | d6176b0 | 2012-08-23 18:14:13 +0000 | [diff] [blame] | 33 | |
caryclark@google.com | 639df89 | 2012-01-10 21:46:10 +0000 | [diff] [blame] | 34 | void lineEndPoints(const _Line& pts) { |
caryclark@google.com | 32546db | 2012-08-31 20:55:07 +0000 | [diff] [blame] | 35 | a = approximately_pin(pts[0].y - pts[1].y); |
| 36 | b = approximately_pin(pts[1].x - pts[0].x); |
caryclark@google.com | 639df89 | 2012-01-10 21:46:10 +0000 | [diff] [blame] | 37 | c = pts[0].x * pts[1].y - pts[1].x * pts[0].y; |
| 38 | } |
rmistry@google.com | d6176b0 | 2012-08-23 18:14:13 +0000 | [diff] [blame] | 39 | |
caryclark@google.com | 639df89 | 2012-01-10 21:46:10 +0000 | [diff] [blame] | 40 | void quadEndPoints(const Quadratic& pts) { |
caryclark@google.com | 32546db | 2012-08-31 20:55:07 +0000 | [diff] [blame] | 41 | quadEndPoints(pts, 0, 2); |
caryclark@google.com | 639df89 | 2012-01-10 21:46:10 +0000 | [diff] [blame] | 42 | } |
| 43 | |
| 44 | void quadEndPoints(const Quadratic& pts, int s, int e) { |
caryclark@google.com | 32546db | 2012-08-31 20:55:07 +0000 | [diff] [blame] | 45 | a = approximately_pin(pts[s].y - pts[e].y); |
| 46 | b = approximately_pin(pts[e].x - pts[s].x); |
caryclark@google.com | 639df89 | 2012-01-10 21:46:10 +0000 | [diff] [blame] | 47 | c = pts[s].x * pts[e].y - pts[e].x * pts[s].y; |
| 48 | } |
| 49 | |
caryclark@google.com | 32546db | 2012-08-31 20:55:07 +0000 | [diff] [blame] | 50 | double normalSquared() const { |
caryclark@google.com | 639df89 | 2012-01-10 21:46:10 +0000 | [diff] [blame] | 51 | return a * a + b * b; |
| 52 | } |
| 53 | |
| 54 | bool normalize() { |
| 55 | double normal = sqrt(normalSquared()); |
caryclark@google.com | d168874 | 2012-09-18 20:08:37 +0000 | [diff] [blame] | 56 | if (approximately_zero(normal)) { |
caryclark@google.com | 639df89 | 2012-01-10 21:46:10 +0000 | [diff] [blame] | 57 | a = b = c = 0; |
| 58 | return false; |
| 59 | } |
| 60 | double reciprocal = 1 / normal; |
| 61 | a *= reciprocal; |
| 62 | b *= reciprocal; |
| 63 | c *= reciprocal; |
| 64 | return true; |
| 65 | } |
rmistry@google.com | d6176b0 | 2012-08-23 18:14:13 +0000 | [diff] [blame] | 66 | |
caryclark@google.com | 32546db | 2012-08-31 20:55:07 +0000 | [diff] [blame] | 67 | void cubicDistanceY(const Cubic& pts, Cubic& distance) const { |
caryclark@google.com | 639df89 | 2012-01-10 21:46:10 +0000 | [diff] [blame] | 68 | double oneThird = 1 / 3.0; |
| 69 | for (int index = 0; index < 4; ++index) { |
| 70 | distance[index].x = index * oneThird; |
| 71 | distance[index].y = a * pts[index].x + b * pts[index].y + c; |
| 72 | } |
| 73 | } |
| 74 | |
caryclark@google.com | 32546db | 2012-08-31 20:55:07 +0000 | [diff] [blame] | 75 | void quadDistanceY(const Quadratic& pts, Quadratic& distance) const { |
caryclark@google.com | 639df89 | 2012-01-10 21:46:10 +0000 | [diff] [blame] | 76 | double oneHalf = 1 / 2.0; |
| 77 | for (int index = 0; index < 3; ++index) { |
| 78 | distance[index].x = index * oneHalf; |
| 79 | distance[index].y = a * pts[index].x + b * pts[index].y + c; |
| 80 | } |
| 81 | } |
| 82 | |
caryclark@google.com | 73ca624 | 2013-01-17 21:02:47 +0000 | [diff] [blame] | 83 | double controlPtDistance(const Cubic& pts, int index) const { |
caryclark@google.com | aa35831 | 2013-01-29 20:28:49 +0000 | [diff] [blame] | 84 | SkASSERT(index == 1 || index == 2); |
caryclark@google.com | 73ca624 | 2013-01-17 21:02:47 +0000 | [diff] [blame] | 85 | return a * pts[index].x + b * pts[index].y + c; |
caryclark@google.com | 639df89 | 2012-01-10 21:46:10 +0000 | [diff] [blame] | 86 | } |
rmistry@google.com | d6176b0 | 2012-08-23 18:14:13 +0000 | [diff] [blame] | 87 | |
caryclark@google.com | 32546db | 2012-08-31 20:55:07 +0000 | [diff] [blame] | 88 | double controlPtDistance(const Quadratic& pts) const { |
caryclark@google.com | 639df89 | 2012-01-10 21:46:10 +0000 | [diff] [blame] | 89 | return a * pts[1].x + b * pts[1].y + c; |
| 90 | } |
rmistry@google.com | d6176b0 | 2012-08-23 18:14:13 +0000 | [diff] [blame] | 91 | |
caryclark@google.com | 32546db | 2012-08-31 20:55:07 +0000 | [diff] [blame] | 92 | double pointDistance(const _Point& pt) const { |
caryclark@google.com | 639df89 | 2012-01-10 21:46:10 +0000 | [diff] [blame] | 93 | return a * pt.x + b * pt.y + c; |
| 94 | } |
caryclark@google.com | b45a1b4 | 2012-05-18 20:50:33 +0000 | [diff] [blame] | 95 | |
caryclark@google.com | 32546db | 2012-08-31 20:55:07 +0000 | [diff] [blame] | 96 | double dx() const { |
| 97 | return b; |
| 98 | } |
| 99 | |
| 100 | double dy() const { |
| 101 | return -a; |
| 102 | } |
| 103 | |
caryclark@google.com | 639df89 | 2012-01-10 21:46:10 +0000 | [diff] [blame] | 104 | private: |
| 105 | double a; |
| 106 | double b; |
| 107 | double c; |
| 108 | }; |