1.1 --- /dev/null Thu Jan 01 00:00:00 1970 +0000
1.2 +++ b/gfx/skia/trunk/src/core/SkLineClipper.cpp Wed Dec 31 06:09:35 2014 +0100
1.3 @@ -0,0 +1,283 @@
1.4 +
1.5 +/*
1.6 + * Copyright 2011 Google Inc.
1.7 + *
1.8 + * Use of this source code is governed by a BSD-style license that can be
1.9 + * found in the LICENSE file.
1.10 + */
1.11 +#include "SkLineClipper.h"
1.12 +
1.13 +template <typename T> T pin_unsorted(T value, T limit0, T limit1) {
1.14 + if (limit1 < limit0) {
1.15 + SkTSwap(limit0, limit1);
1.16 + }
1.17 + // now the limits are sorted
1.18 + SkASSERT(limit0 <= limit1);
1.19 +
1.20 + if (value < limit0) {
1.21 + value = limit0;
1.22 + } else if (value > limit1) {
1.23 + value = limit1;
1.24 + }
1.25 + return value;
1.26 +}
1.27 +
1.28 +// return X coordinate of intersection with horizontal line at Y
1.29 +static SkScalar sect_with_horizontal(const SkPoint src[2], SkScalar Y) {
1.30 + SkScalar dy = src[1].fY - src[0].fY;
1.31 + if (SkScalarNearlyZero(dy)) {
1.32 + return SkScalarAve(src[0].fX, src[1].fX);
1.33 + } else {
1.34 + // need the extra precision so we don't compute a value that exceeds
1.35 + // our original limits
1.36 + double X0 = src[0].fX;
1.37 + double Y0 = src[0].fY;
1.38 + double X1 = src[1].fX;
1.39 + double Y1 = src[1].fY;
1.40 + double result = X0 + ((double)Y - Y0) * (X1 - X0) / (Y1 - Y0);
1.41 +
1.42 + // The computed X value might still exceed [X0..X1] due to quantum flux
1.43 + // when the doubles were added and subtracted, so we have to pin the
1.44 + // answer :(
1.45 + return (float)pin_unsorted(result, X0, X1);
1.46 + }
1.47 +}
1.48 +
1.49 +// return Y coordinate of intersection with vertical line at X
1.50 +static SkScalar sect_with_vertical(const SkPoint src[2], SkScalar X) {
1.51 + SkScalar dx = src[1].fX - src[0].fX;
1.52 + if (SkScalarNearlyZero(dx)) {
1.53 + return SkScalarAve(src[0].fY, src[1].fY);
1.54 + } else {
1.55 + // need the extra precision so we don't compute a value that exceeds
1.56 + // our original limits
1.57 + double X0 = src[0].fX;
1.58 + double Y0 = src[0].fY;
1.59 + double X1 = src[1].fX;
1.60 + double Y1 = src[1].fY;
1.61 + double result = Y0 + ((double)X - X0) * (Y1 - Y0) / (X1 - X0);
1.62 + return (float)result;
1.63 + }
1.64 +}
1.65 +
1.66 +///////////////////////////////////////////////////////////////////////////////
1.67 +
1.68 +static inline bool nestedLT(SkScalar a, SkScalar b, SkScalar dim) {
1.69 + return a <= b && (a < b || dim > 0);
1.70 +}
1.71 +
1.72 +// returns true if outer contains inner, even if inner is empty.
1.73 +// note: outer.contains(inner) always returns false if inner is empty.
1.74 +static inline bool containsNoEmptyCheck(const SkRect& outer,
1.75 + const SkRect& inner) {
1.76 + return outer.fLeft <= inner.fLeft && outer.fTop <= inner.fTop &&
1.77 + outer.fRight >= inner.fRight && outer.fBottom >= inner.fBottom;
1.78 +}
1.79 +
1.80 +bool SkLineClipper::IntersectLine(const SkPoint src[2], const SkRect& clip,
1.81 + SkPoint dst[2]) {
1.82 + SkRect bounds;
1.83 +
1.84 + bounds.set(src, 2);
1.85 + if (containsNoEmptyCheck(clip, bounds)) {
1.86 + if (src != dst) {
1.87 + memcpy(dst, src, 2 * sizeof(SkPoint));
1.88 + }
1.89 + return true;
1.90 + }
1.91 + // check for no overlap, and only permit coincident edges if the line
1.92 + // and the edge are colinear
1.93 + if (nestedLT(bounds.fRight, clip.fLeft, bounds.width()) ||
1.94 + nestedLT(clip.fRight, bounds.fLeft, bounds.width()) ||
1.95 + nestedLT(bounds.fBottom, clip.fTop, bounds.height()) ||
1.96 + nestedLT(clip.fBottom, bounds.fTop, bounds.height())) {
1.97 + return false;
1.98 + }
1.99 +
1.100 + int index0, index1;
1.101 +
1.102 + if (src[0].fY < src[1].fY) {
1.103 + index0 = 0;
1.104 + index1 = 1;
1.105 + } else {
1.106 + index0 = 1;
1.107 + index1 = 0;
1.108 + }
1.109 +
1.110 + SkPoint tmp[2];
1.111 + memcpy(tmp, src, sizeof(tmp));
1.112 +
1.113 + // now compute Y intersections
1.114 + if (tmp[index0].fY < clip.fTop) {
1.115 + tmp[index0].set(sect_with_horizontal(src, clip.fTop), clip.fTop);
1.116 + }
1.117 + if (tmp[index1].fY > clip.fBottom) {
1.118 + tmp[index1].set(sect_with_horizontal(src, clip.fBottom), clip.fBottom);
1.119 + }
1.120 +
1.121 + if (tmp[0].fX < tmp[1].fX) {
1.122 + index0 = 0;
1.123 + index1 = 1;
1.124 + } else {
1.125 + index0 = 1;
1.126 + index1 = 0;
1.127 + }
1.128 +
1.129 + // check for quick-reject in X again, now that we may have been chopped
1.130 + if ((tmp[index1].fX <= clip.fLeft || tmp[index0].fX >= clip.fRight) &&
1.131 + tmp[index0].fX < tmp[index1].fX) {
1.132 + // only reject if we have a non-zero width
1.133 + return false;
1.134 + }
1.135 +
1.136 + if (tmp[index0].fX < clip.fLeft) {
1.137 + tmp[index0].set(clip.fLeft, sect_with_vertical(src, clip.fLeft));
1.138 + }
1.139 + if (tmp[index1].fX > clip.fRight) {
1.140 + tmp[index1].set(clip.fRight, sect_with_vertical(src, clip.fRight));
1.141 + }
1.142 +#ifdef SK_DEBUG
1.143 + bounds.set(tmp, 2);
1.144 + SkASSERT(containsNoEmptyCheck(clip, bounds));
1.145 +#endif
1.146 + memcpy(dst, tmp, sizeof(tmp));
1.147 + return true;
1.148 +}
1.149 +
1.150 +#ifdef SK_DEBUG
1.151 +// return value between the two limits, where the limits are either ascending
1.152 +// or descending.
1.153 +static bool is_between_unsorted(SkScalar value,
1.154 + SkScalar limit0, SkScalar limit1) {
1.155 + if (limit0 < limit1) {
1.156 + return limit0 <= value && value <= limit1;
1.157 + } else {
1.158 + return limit1 <= value && value <= limit0;
1.159 + }
1.160 +}
1.161 +#endif
1.162 +
1.163 +#ifdef SK_DEBUG
1.164 +// This is an example of why we need to pin the result computed in
1.165 +// sect_with_horizontal. If we didn't explicitly pin, is_between_unsorted would
1.166 +// fail.
1.167 +//
1.168 +static void sect_with_horizontal_test_for_pin_results() {
1.169 + const SkPoint pts[] = {
1.170 + { -540000, -720000 },
1.171 + { -9.10000017e-05f, 9.99999996e-13f }
1.172 + };
1.173 + float x = sect_with_horizontal(pts, 0);
1.174 + SkASSERT(is_between_unsorted(x, pts[0].fX, pts[1].fX));
1.175 +}
1.176 +#endif
1.177 +
1.178 +int SkLineClipper::ClipLine(const SkPoint pts[], const SkRect& clip,
1.179 + SkPoint lines[]) {
1.180 +#ifdef SK_DEBUG
1.181 + {
1.182 + static bool gOnce;
1.183 + if (!gOnce) {
1.184 + sect_with_horizontal_test_for_pin_results();
1.185 + gOnce = true;
1.186 + }
1.187 + }
1.188 +#endif
1.189 +
1.190 + int index0, index1;
1.191 +
1.192 + if (pts[0].fY < pts[1].fY) {
1.193 + index0 = 0;
1.194 + index1 = 1;
1.195 + } else {
1.196 + index0 = 1;
1.197 + index1 = 0;
1.198 + }
1.199 +
1.200 + // Check if we're completely clipped out in Y (above or below
1.201 +
1.202 + if (pts[index1].fY <= clip.fTop) { // we're above the clip
1.203 + return 0;
1.204 + }
1.205 + if (pts[index0].fY >= clip.fBottom) { // we're below the clip
1.206 + return 0;
1.207 + }
1.208 +
1.209 + // Chop in Y to produce a single segment, stored in tmp[0..1]
1.210 +
1.211 + SkPoint tmp[2];
1.212 + memcpy(tmp, pts, sizeof(tmp));
1.213 +
1.214 + // now compute intersections
1.215 + if (pts[index0].fY < clip.fTop) {
1.216 + tmp[index0].set(sect_with_horizontal(pts, clip.fTop), clip.fTop);
1.217 + SkASSERT(is_between_unsorted(tmp[index0].fX, pts[0].fX, pts[1].fX));
1.218 + }
1.219 + if (tmp[index1].fY > clip.fBottom) {
1.220 + tmp[index1].set(sect_with_horizontal(pts, clip.fBottom), clip.fBottom);
1.221 + SkASSERT(is_between_unsorted(tmp[index1].fX, pts[0].fX, pts[1].fX));
1.222 + }
1.223 +
1.224 + // Chop it into 1..3 segments that are wholly within the clip in X.
1.225 +
1.226 + // temp storage for up to 3 segments
1.227 + SkPoint resultStorage[kMaxPoints];
1.228 + SkPoint* result; // points to our results, either tmp or resultStorage
1.229 + int lineCount = 1;
1.230 + bool reverse;
1.231 +
1.232 + if (pts[0].fX < pts[1].fX) {
1.233 + index0 = 0;
1.234 + index1 = 1;
1.235 + reverse = false;
1.236 + } else {
1.237 + index0 = 1;
1.238 + index1 = 0;
1.239 + reverse = true;
1.240 + }
1.241 +
1.242 + if (tmp[index1].fX <= clip.fLeft) { // wholly to the left
1.243 + tmp[0].fX = tmp[1].fX = clip.fLeft;
1.244 + result = tmp;
1.245 + reverse = false;
1.246 + } else if (tmp[index0].fX >= clip.fRight) { // wholly to the right
1.247 + tmp[0].fX = tmp[1].fX = clip.fRight;
1.248 + result = tmp;
1.249 + reverse = false;
1.250 + } else {
1.251 + result = resultStorage;
1.252 + SkPoint* r = result;
1.253 +
1.254 + if (tmp[index0].fX < clip.fLeft) {
1.255 + r->set(clip.fLeft, tmp[index0].fY);
1.256 + r += 1;
1.257 + r->set(clip.fLeft, sect_with_vertical(tmp, clip.fLeft));
1.258 + SkASSERT(is_between_unsorted(r->fY, tmp[0].fY, tmp[1].fY));
1.259 + } else {
1.260 + *r = tmp[index0];
1.261 + }
1.262 + r += 1;
1.263 +
1.264 + if (tmp[index1].fX > clip.fRight) {
1.265 + r->set(clip.fRight, sect_with_vertical(tmp, clip.fRight));
1.266 + SkASSERT(is_between_unsorted(r->fY, tmp[0].fY, tmp[1].fY));
1.267 + r += 1;
1.268 + r->set(clip.fRight, tmp[index1].fY);
1.269 + } else {
1.270 + *r = tmp[index1];
1.271 + }
1.272 +
1.273 + lineCount = SkToInt(r - result);
1.274 + }
1.275 +
1.276 + // Now copy the results into the caller's lines[] parameter
1.277 + if (reverse) {
1.278 + // copy the pts in reverse order to maintain winding order
1.279 + for (int i = 0; i <= lineCount; i++) {
1.280 + lines[lineCount - i] = result[i];
1.281 + }
1.282 + } else {
1.283 + memcpy(lines, result, (lineCount + 1) * sizeof(SkPoint));
1.284 + }
1.285 + return lineCount;
1.286 +}
