123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256257258259260261262263264265266267268269270271272273274275276 |
- /*
- * Copyright 2011 Google Inc.
- *
- * Use of this source code is governed by a BSD-style license that can be
- * found in the LICENSE file.
- */
- #include "include/private/SkTo.h"
- #include "src/core/SkLineClipper.h"
- #include <utility>
- template <typename T> T pin_unsorted(T value, T limit0, T limit1) {
- if (limit1 < limit0) {
- using std::swap;
- swap(limit0, limit1);
- }
- // now the limits are sorted
- SkASSERT(limit0 <= limit1);
- if (value < limit0) {
- value = limit0;
- } else if (value > limit1) {
- value = limit1;
- }
- return value;
- }
- // return X coordinate of intersection with horizontal line at Y
- static SkScalar sect_with_horizontal(const SkPoint src[2], SkScalar Y) {
- SkScalar dy = src[1].fY - src[0].fY;
- if (SkScalarNearlyZero(dy)) {
- return SkScalarAve(src[0].fX, src[1].fX);
- } else {
- // need the extra precision so we don't compute a value that exceeds
- // our original limits
- double X0 = src[0].fX;
- double Y0 = src[0].fY;
- double X1 = src[1].fX;
- double Y1 = src[1].fY;
- double result = X0 + ((double)Y - Y0) * (X1 - X0) / (Y1 - Y0);
- // The computed X value might still exceed [X0..X1] due to quantum flux
- // when the doubles were added and subtracted, so we have to pin the
- // answer :(
- return (float)pin_unsorted(result, X0, X1);
- }
- }
- // return Y coordinate of intersection with vertical line at X
- static SkScalar sect_with_vertical(const SkPoint src[2], SkScalar X) {
- SkScalar dx = src[1].fX - src[0].fX;
- if (SkScalarNearlyZero(dx)) {
- return SkScalarAve(src[0].fY, src[1].fY);
- } else {
- // need the extra precision so we don't compute a value that exceeds
- // our original limits
- double X0 = src[0].fX;
- double Y0 = src[0].fY;
- double X1 = src[1].fX;
- double Y1 = src[1].fY;
- double result = Y0 + ((double)X - X0) * (Y1 - Y0) / (X1 - X0);
- return (float)result;
- }
- }
- static SkScalar sect_clamp_with_vertical(const SkPoint src[2], SkScalar x) {
- SkScalar y = sect_with_vertical(src, x);
- // Our caller expects y to be between src[0].fY and src[1].fY (unsorted), but due to the
- // numerics of floats/doubles, we might have computed a value slightly outside of that,
- // so we have to manually clamp afterwards.
- // See skbug.com/7491
- return pin_unsorted(y, src[0].fY, src[1].fY);
- }
- ///////////////////////////////////////////////////////////////////////////////
- static inline bool nestedLT(SkScalar a, SkScalar b, SkScalar dim) {
- return a <= b && (a < b || dim > 0);
- }
- // returns true if outer contains inner, even if inner is empty.
- // note: outer.contains(inner) always returns false if inner is empty.
- static inline bool containsNoEmptyCheck(const SkRect& outer,
- const SkRect& inner) {
- return outer.fLeft <= inner.fLeft && outer.fTop <= inner.fTop &&
- outer.fRight >= inner.fRight && outer.fBottom >= inner.fBottom;
- }
- bool SkLineClipper::IntersectLine(const SkPoint src[2], const SkRect& clip,
- SkPoint dst[2]) {
- SkRect bounds;
- bounds.set(src[0], src[1]);
- if (containsNoEmptyCheck(clip, bounds)) {
- if (src != dst) {
- memcpy(dst, src, 2 * sizeof(SkPoint));
- }
- return true;
- }
- // check for no overlap, and only permit coincident edges if the line
- // and the edge are colinear
- if (nestedLT(bounds.fRight, clip.fLeft, bounds.width()) ||
- nestedLT(clip.fRight, bounds.fLeft, bounds.width()) ||
- nestedLT(bounds.fBottom, clip.fTop, bounds.height()) ||
- nestedLT(clip.fBottom, bounds.fTop, bounds.height())) {
- return false;
- }
- int index0, index1;
- if (src[0].fY < src[1].fY) {
- index0 = 0;
- index1 = 1;
- } else {
- index0 = 1;
- index1 = 0;
- }
- SkPoint tmp[2];
- memcpy(tmp, src, sizeof(tmp));
- // now compute Y intersections
- if (tmp[index0].fY < clip.fTop) {
- tmp[index0].set(sect_with_horizontal(src, clip.fTop), clip.fTop);
- }
- if (tmp[index1].fY > clip.fBottom) {
- tmp[index1].set(sect_with_horizontal(src, clip.fBottom), clip.fBottom);
- }
- if (tmp[0].fX < tmp[1].fX) {
- index0 = 0;
- index1 = 1;
- } else {
- index0 = 1;
- index1 = 0;
- }
- // check for quick-reject in X again, now that we may have been chopped
- if ((tmp[index1].fX <= clip.fLeft || tmp[index0].fX >= clip.fRight)) {
- // usually we will return false, but we don't if the line is vertical and coincident
- // with the clip.
- if (tmp[0].fX != tmp[1].fX || tmp[0].fX < clip.fLeft || tmp[0].fX > clip.fRight) {
- return false;
- }
- }
- if (tmp[index0].fX < clip.fLeft) {
- tmp[index0].set(clip.fLeft, sect_with_vertical(src, clip.fLeft));
- }
- if (tmp[index1].fX > clip.fRight) {
- tmp[index1].set(clip.fRight, sect_with_vertical(src, clip.fRight));
- }
- #ifdef SK_DEBUG
- bounds.set(tmp[0], tmp[1]);
- SkASSERT(containsNoEmptyCheck(clip, bounds));
- #endif
- memcpy(dst, tmp, sizeof(tmp));
- return true;
- }
- #ifdef SK_DEBUG
- // return value between the two limits, where the limits are either ascending
- // or descending.
- static bool is_between_unsorted(SkScalar value,
- SkScalar limit0, SkScalar limit1) {
- if (limit0 < limit1) {
- return limit0 <= value && value <= limit1;
- } else {
- return limit1 <= value && value <= limit0;
- }
- }
- #endif
- int SkLineClipper::ClipLine(const SkPoint pts[], const SkRect& clip, SkPoint lines[],
- bool canCullToTheRight) {
- int index0, index1;
- if (pts[0].fY < pts[1].fY) {
- index0 = 0;
- index1 = 1;
- } else {
- index0 = 1;
- index1 = 0;
- }
- // Check if we're completely clipped out in Y (above or below
- if (pts[index1].fY <= clip.fTop) { // we're above the clip
- return 0;
- }
- if (pts[index0].fY >= clip.fBottom) { // we're below the clip
- return 0;
- }
- // Chop in Y to produce a single segment, stored in tmp[0..1]
- SkPoint tmp[2];
- memcpy(tmp, pts, sizeof(tmp));
- // now compute intersections
- if (pts[index0].fY < clip.fTop) {
- tmp[index0].set(sect_with_horizontal(pts, clip.fTop), clip.fTop);
- SkASSERT(is_between_unsorted(tmp[index0].fX, pts[0].fX, pts[1].fX));
- }
- if (tmp[index1].fY > clip.fBottom) {
- tmp[index1].set(sect_with_horizontal(pts, clip.fBottom), clip.fBottom);
- SkASSERT(is_between_unsorted(tmp[index1].fX, pts[0].fX, pts[1].fX));
- }
- // Chop it into 1..3 segments that are wholly within the clip in X.
- // temp storage for up to 3 segments
- SkPoint resultStorage[kMaxPoints];
- SkPoint* result; // points to our results, either tmp or resultStorage
- int lineCount = 1;
- bool reverse;
- if (pts[0].fX < pts[1].fX) {
- index0 = 0;
- index1 = 1;
- reverse = false;
- } else {
- index0 = 1;
- index1 = 0;
- reverse = true;
- }
- if (tmp[index1].fX <= clip.fLeft) { // wholly to the left
- tmp[0].fX = tmp[1].fX = clip.fLeft;
- result = tmp;
- reverse = false;
- } else if (tmp[index0].fX >= clip.fRight) { // wholly to the right
- if (canCullToTheRight) {
- return 0;
- }
- tmp[0].fX = tmp[1].fX = clip.fRight;
- result = tmp;
- reverse = false;
- } else {
- result = resultStorage;
- SkPoint* r = result;
- if (tmp[index0].fX < clip.fLeft) {
- r->set(clip.fLeft, tmp[index0].fY);
- r += 1;
- r->set(clip.fLeft, sect_clamp_with_vertical(tmp, clip.fLeft));
- SkASSERT(is_between_unsorted(r->fY, tmp[0].fY, tmp[1].fY));
- } else {
- *r = tmp[index0];
- }
- r += 1;
- if (tmp[index1].fX > clip.fRight) {
- r->set(clip.fRight, sect_clamp_with_vertical(tmp, clip.fRight));
- SkASSERT(is_between_unsorted(r->fY, tmp[0].fY, tmp[1].fY));
- r += 1;
- r->set(clip.fRight, tmp[index1].fY);
- } else {
- *r = tmp[index1];
- }
- lineCount = SkToInt(r - result);
- }
- // Now copy the results into the caller's lines[] parameter
- if (reverse) {
- // copy the pts in reverse order to maintain winding order
- for (int i = 0; i <= lineCount; i++) {
- lines[lineCount - i] = result[i];
- }
- } else {
- memcpy(lines, result, (lineCount + 1) * sizeof(SkPoint));
- }
- return lineCount;
- }
|