SkLineParameters.h 5.3 KB

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