Home | History | Annotate | Download | only in core 
      1 #include "SkLineClipper.h"
      2 
      3 // return X coordinate of intersection with horizontal line at Y
      4 static SkScalar sect_with_horizontal(const SkPoint src[2], SkScalar Y) {
      5     SkScalar dy = src[1].fY - src[0].fY;
      6     if (SkScalarNearlyZero(dy)) {
      7         return SkScalarAve(src[0].fX, src[1].fX);
      8     } else {
      9         return src[0].fX + SkScalarMulDiv(Y - src[0].fY, src[1].fX - src[0].fX,
     10                                           dy);
     11     }
     12 }
     13 
     14 // return Y coordinate of intersection with vertical line at X
     15 static SkScalar sect_with_vertical(const SkPoint src[2], SkScalar X) {
     16     SkScalar dx = src[1].fX - src[0].fX;
     17     if (SkScalarNearlyZero(dx)) {
     18         return SkScalarAve(src[0].fY, src[1].fY);
     19     } else {
     20         return src[0].fY + SkScalarMulDiv(X - src[0].fX, src[1].fY - src[0].fY,
     21                                           dx);
     22     }
     23 }
     24 
     25 ///////////////////////////////////////////////////////////////////////////////
     26 
     27 static inline bool nestedLT(SkScalar a, SkScalar b, SkScalar dim) {
     28     return a <= b && (a < b || dim > 0);
     29 }
     30 
     31 // returns true if outer contains inner, even if inner is empty.
     32 // note: outer.contains(inner) always returns false if inner is empty.
     33 static inline bool containsNoEmptyCheck(const SkRect& outer,
     34                                         const SkRect& inner) {
     35     return  outer.fLeft <= inner.fLeft && outer.fTop <= inner.fTop &&
     36             outer.fRight >= inner.fRight && outer.fBottom >= inner.fBottom;
     37 }
     38 
     39 bool SkLineClipper::IntersectLine(const SkPoint src[2], const SkRect& clip,
     40                                   SkPoint dst[2]) {
     41     SkRect bounds;
     42 
     43     bounds.set(src, 2);
     44     if (containsNoEmptyCheck(clip, bounds)) {
     45         if (src != dst) {
     46             memcpy(dst, src, 2 * sizeof(SkPoint));
     47         }
     48         return true;
     49     }
     50     // check for no overlap, and only permit coincident edges if the line
     51     // and the edge are colinear
     52     if (nestedLT(bounds.fRight, clip.fLeft, bounds.width()) ||
     53         nestedLT(clip.fRight, bounds.fLeft, bounds.width()) ||
     54         nestedLT(bounds.fBottom, clip.fTop, bounds.height()) ||
     55         nestedLT(clip.fBottom, bounds.fTop, bounds.height())) {
     56         return false;
     57     }
     58 
     59     int index0, index1;
     60 
     61     if (src[0].fY < src[1].fY) {
     62         index0 = 0;
     63         index1 = 1;
     64     } else {
     65         index0 = 1;
     66         index1 = 0;
     67     }
     68 
     69     SkPoint tmp[2];
     70     memcpy(tmp, src, sizeof(tmp));
     71 
     72     // now compute Y intersections
     73     if (tmp[index0].fY < clip.fTop) {
     74         tmp[index0].set(sect_with_horizontal(src, clip.fTop), clip.fTop);
     75     }
     76     if (tmp[index1].fY > clip.fBottom) {
     77         tmp[index1].set(sect_with_horizontal(src, clip.fBottom), clip.fBottom);
     78     }
     79 
     80     if (tmp[0].fX < tmp[1].fX) {
     81         index0 = 0;
     82         index1 = 1;
     83     } else {
     84         index0 = 1;
     85         index1 = 0;
     86     }
     87 
     88     // check for quick-reject in X again, now that we may have been chopped
     89     if ((tmp[index1].fX <= clip.fLeft || tmp[index0].fX >= clip.fRight) &&
     90         tmp[index0].fX < tmp[index1].fX) {
     91         // only reject if we have a non-zero width
     92         return false;
     93     }
     94 
     95     if (tmp[index0].fX < clip.fLeft) {
     96         tmp[index0].set(clip.fLeft, sect_with_vertical(src, clip.fLeft));
     97     }
     98     if (tmp[index1].fX > clip.fRight) {
     99         tmp[index1].set(clip.fRight, sect_with_vertical(src, clip.fRight));
    100     }
    101 #ifdef SK_DEBUG
    102     bounds.set(tmp, 2);
    103     SkASSERT(containsNoEmptyCheck(clip, bounds));
    104 #endif
    105     memcpy(dst, tmp, sizeof(tmp));
    106     return true;
    107 }
    108 
    109 int SkLineClipper::ClipLine(const SkPoint pts[], const SkRect& clip,
    110                             SkPoint lines[]) {
    111     int index0, index1;
    112 
    113     if (pts[0].fY < pts[1].fY) {
    114         index0 = 0;
    115         index1 = 1;
    116     } else {
    117         index0 = 1;
    118         index1 = 0;
    119     }
    120 
    121     // Check if we're completely clipped out in Y (above or below
    122 
    123     if (pts[index1].fY <= clip.fTop) {  // we're above the clip
    124         return 0;
    125     }
    126     if (pts[index0].fY >= clip.fBottom) {  // we're below the clip
    127         return 0;
    128     }
    129 
    130     // Chop in Y to produce a single segment, stored in tmp[0..1]
    131 
    132     SkPoint tmp[2];
    133     memcpy(tmp, pts, sizeof(tmp));
    134 
    135     // now compute intersections
    136     if (pts[index0].fY < clip.fTop) {
    137         tmp[index0].set(sect_with_horizontal(pts, clip.fTop), clip.fTop);
    138     }
    139     if (tmp[index1].fY > clip.fBottom) {
    140         tmp[index1].set(sect_with_horizontal(pts, clip.fBottom), clip.fBottom);
    141     }
    142 
    143     // Chop it into 1..3 segments that are wholly within the clip in X.
    144 
    145     // temp storage for up to 3 segments
    146     SkPoint resultStorage[kMaxPoints];
    147     SkPoint* result;    // points to our results, either tmp or resultStorage
    148     int lineCount = 1;
    149     bool reverse;
    150 
    151     if (pts[0].fX < pts[1].fX) {
    152         index0 = 0;
    153         index1 = 1;
    154         reverse = false;
    155     } else {
    156         index0 = 1;
    157         index1 = 0;
    158         reverse = true;
    159     }
    160 
    161     if (tmp[index1].fX <= clip.fLeft) {  // wholly to the left
    162         tmp[0].fX = tmp[1].fX = clip.fLeft;
    163         result = tmp;
    164         reverse = false;
    165     } else if (tmp[index0].fX >= clip.fRight) {    // wholly to the right
    166         tmp[0].fX = tmp[1].fX = clip.fRight;
    167         result = tmp;
    168         reverse = false;
    169     } else {
    170         result = resultStorage;
    171         SkPoint* r = result;
    172 
    173         if (tmp[index0].fX < clip.fLeft) {
    174             r->set(clip.fLeft, tmp[index0].fY);
    175             r += 1;
    176             r->set(clip.fLeft, sect_with_vertical(pts, clip.fLeft));
    177         } else {
    178             *r = tmp[index0];
    179         }
    180         r += 1;
    181 
    182         if (tmp[index1].fX > clip.fRight) {
    183             r->set(clip.fRight, sect_with_vertical(pts, clip.fRight));
    184             r += 1;
    185             r->set(clip.fRight, tmp[index1].fY);
    186         } else {
    187             *r = tmp[index1];
    188         }
    189 
    190         lineCount = r - result;
    191     }
    192 
    193     // Now copy the results into the caller's lines[] parameter
    194     if (reverse) {
    195         // copy the pts in reverse order to maintain winding order
    196         for (int i = 0; i <= lineCount; i++) {
    197             lines[lineCount - i] = result[i];
    198         }
    199     } else {
    200         memcpy(lines, result, (lineCount + 1) * sizeof(SkPoint));
    201     }
    202     return lineCount;
    203 }
    204 
    205