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 | c682590 | 2012-02-03 22:07:47 +0000 | [diff] [blame] | 7 | #include "CurveIntersection.h" |
caryclark@google.com | 8dcf114 | 2012-07-02 20:27:02 +0000 | [diff] [blame] | 8 | #include "CurveUtilities.h" |
caryclark@google.com | 639df89 | 2012-01-10 21:46:10 +0000 | [diff] [blame] | 9 | #include "LineParameters.h" |
caryclark@google.com | 639df89 | 2012-01-10 21:46:10 +0000 | [diff] [blame] | 10 | |
caryclark@google.com | 235f56a | 2012-09-14 14:19:30 +0000 | [diff] [blame] | 11 | #define DEBUG_BEZIER_CLIP 1 |
| 12 | |
caryclark@google.com | 639df89 | 2012-01-10 21:46:10 +0000 | [diff] [blame] | 13 | // return false if unable to clip (e.g., unable to create implicit line) |
| 14 | // caller should subdivide, or create degenerate if the values are too small |
| 15 | bool bezier_clip(const Quadratic& q1, const Quadratic& q2, double& minT, double& maxT) { |
| 16 | minT = 1; |
| 17 | maxT = 0; |
| 18 | // determine normalized implicit line equation for pt[0] to pt[3] |
| 19 | // of the form ax + by + c = 0, where a*a + b*b == 1 |
rmistry@google.com | d6176b0 | 2012-08-23 18:14:13 +0000 | [diff] [blame] | 20 | |
caryclark@google.com | 639df89 | 2012-01-10 21:46:10 +0000 | [diff] [blame] | 21 | // find the implicit line equation parameters |
| 22 | LineParameters endLine; |
| 23 | endLine.quadEndPoints(q1); |
| 24 | if (!endLine.normalize()) { |
| 25 | printf("line cannot be normalized: need more code here\n"); |
caryclark@google.com | aa35831 | 2013-01-29 20:28:49 +0000 | [diff] [blame] | 26 | SkASSERT(0); |
caryclark@google.com | 639df89 | 2012-01-10 21:46:10 +0000 | [diff] [blame] | 27 | return false; |
| 28 | } |
| 29 | |
| 30 | double distance = endLine.controlPtDistance(q1); |
rmistry@google.com | d6176b0 | 2012-08-23 18:14:13 +0000 | [diff] [blame] | 31 | |
caryclark@google.com | 639df89 | 2012-01-10 21:46:10 +0000 | [diff] [blame] | 32 | // find fat line |
| 33 | double top = 0; |
| 34 | double bottom = distance / 2; // http://students.cs.byu.edu/~tom/557/text/cic.pdf (7.6) |
| 35 | if (top > bottom) { |
caryclark@google.com | aa35831 | 2013-01-29 20:28:49 +0000 | [diff] [blame] | 36 | SkTSwap(top, bottom); |
caryclark@google.com | 639df89 | 2012-01-10 21:46:10 +0000 | [diff] [blame] | 37 | } |
rmistry@google.com | d6176b0 | 2012-08-23 18:14:13 +0000 | [diff] [blame] | 38 | |
caryclark@google.com | 639df89 | 2012-01-10 21:46:10 +0000 | [diff] [blame] | 39 | // compute intersecting candidate distance |
| 40 | Quadratic distance2y; // points with X of (0, 1/2, 1) |
| 41 | endLine.quadDistanceY(q2, distance2y); |
rmistry@google.com | d6176b0 | 2012-08-23 18:14:13 +0000 | [diff] [blame] | 42 | |
caryclark@google.com | 639df89 | 2012-01-10 21:46:10 +0000 | [diff] [blame] | 43 | int flags = 0; |
caryclark@google.com | 5e0500f | 2013-02-20 12:51:37 +0000 | [diff] [blame] | 44 | if (approximately_lesser_or_equal(distance2y[0].y, top)) { |
caryclark@google.com | 639df89 | 2012-01-10 21:46:10 +0000 | [diff] [blame] | 45 | flags |= kFindTopMin; |
caryclark@google.com | 5e0500f | 2013-02-20 12:51:37 +0000 | [diff] [blame] | 46 | } else if (approximately_greater_or_equal(distance2y[0].y, bottom)) { |
caryclark@google.com | 639df89 | 2012-01-10 21:46:10 +0000 | [diff] [blame] | 47 | flags |= kFindBottomMin; |
| 48 | } else { |
| 49 | minT = 0; |
| 50 | } |
| 51 | |
caryclark@google.com | 5e0500f | 2013-02-20 12:51:37 +0000 | [diff] [blame] | 52 | if (approximately_lesser_or_equal(distance2y[2].y, top)) { |
caryclark@google.com | 639df89 | 2012-01-10 21:46:10 +0000 | [diff] [blame] | 53 | flags |= kFindTopMax; |
caryclark@google.com | 5e0500f | 2013-02-20 12:51:37 +0000 | [diff] [blame] | 54 | } else if (approximately_greater_or_equal(distance2y[2].y, bottom)) { |
caryclark@google.com | 639df89 | 2012-01-10 21:46:10 +0000 | [diff] [blame] | 55 | flags |= kFindBottomMax; |
| 56 | } else { |
| 57 | maxT = 1; |
| 58 | } |
| 59 | // Find the intersection of distance convex hull and fat line. |
caryclark@google.com | 27accef | 2012-01-25 18:57:23 +0000 | [diff] [blame] | 60 | int idx = 0; |
| 61 | do { |
| 62 | int next = idx + 1; |
| 63 | if (next == 3) { |
| 64 | next = 0; |
| 65 | } |
| 66 | x_at(distance2y[idx], distance2y[next], top, bottom, flags, minT, maxT); |
| 67 | idx = next; |
rmistry@google.com | d6176b0 | 2012-08-23 18:14:13 +0000 | [diff] [blame] | 68 | } while (idx); |
caryclark@google.com | 235f56a | 2012-09-14 14:19:30 +0000 | [diff] [blame] | 69 | #if DEBUG_BEZIER_CLIP |
| 70 | _Rect r1, r2; |
| 71 | r1.setBounds(q1); |
| 72 | r2.setBounds(q2); |
| 73 | _Point testPt = {0.487, 0.337}; |
| 74 | if (r1.contains(testPt) && r2.contains(testPt)) { |
| 75 | printf("%s q1=(%1.9g,%1.9g %1.9g,%1.9g %1.9g,%1.9g)" |
| 76 | " q2=(%1.9g,%1.9g %1.9g,%1.9g %1.9g,%1.9g) minT=%1.9g maxT=%1.9g\n", |
| 77 | __FUNCTION__, q1[0].x, q1[0].y, q1[1].x, q1[1].y, q1[2].x, q1[2].y, |
| 78 | q2[0].x, q2[0].y, q2[1].x, q2[1].y, q2[2].x, q2[2].y, minT, maxT); |
| 79 | } |
| 80 | #endif |
caryclark@google.com | 639df89 | 2012-01-10 21:46:10 +0000 | [diff] [blame] | 81 | return minT < maxT; // returns false if distance shows no intersection |
| 82 | } |