From 639df891487e40925a4f8d9a34fd3dc0c18b40a7 Mon Sep 17 00:00:00 2001 From: "caryclark@google.com" Date: Tue, 10 Jan 2012 21:46:10 +0000 Subject: work in progress for shape operations A experimental/Intersection A experimental/Intersection/Intersections.h A experimental/Intersection/DataTypes.cpp A experimental/Intersection/QuadraticReduceOrder.cpp A experimental/Intersection/IntersectionUtilities.cpp A experimental/Intersection/CubicIntersection_Tests.h A experimental/Intersection/LineParameteters_Test.cpp A experimental/Intersection/ReduceOrder.cpp A experimental/Intersection/QuadraticIntersection.cpp A experimental/Intersection/Extrema.h A experimental/Intersection/CubicIntersection_TestData.h A experimental/Intersection/QuadraticParameterization_Test.cpp A experimental/Intersection/TestUtilities.cpp A experimental/Intersection/CubicRoots.cpp A experimental/Intersection/QuadraticParameterization.cpp A experimental/Intersection/QuadraticSubDivide.cpp A experimental/Intersection/LineIntersection_Test.cpp A experimental/Intersection/LineIntersection.cpp A experimental/Intersection/CubicParameterizationCode.cpp A experimental/Intersection/LineParameters.h A experimental/Intersection/CubicIntersection.h A experimental/Intersection/CubeRoot.cpp A experimental/Intersection/SkAntiEdge.h A experimental/Intersection/ConvexHull_Test.cpp A experimental/Intersection/CubicBezierClip_Test.cpp A experimental/Intersection/CubicIntersection_Tests.cpp A experimental/Intersection/CubicBezierClip.cpp A experimental/Intersection/CubicIntersectionT.cpp A experimental/Intersection/Inline_Tests.cpp A experimental/Intersection/ReduceOrder_Test.cpp A experimental/Intersection/QuadraticIntersection_TestData.h A experimental/Intersection/DataTypes.h A experimental/Intersection/Extrema.cpp A experimental/Intersection/EdgeApp.cpp A experimental/Intersection/CubicIntersection_TestData.cpp A experimental/Intersection/IntersectionUtilities.h A experimental/Intersection/CubicReduceOrder.cpp A experimental/Intersection/CubicCoincidence.cpp A experimental/Intersection/CubicIntersection_Test.cpp A experimental/Intersection/CubicIntersection.cpp A experimental/Intersection/QuadraticUtilities.h A experimental/Intersection/SkAntiEdge.cpp A experimental/Intersection/TestUtilities.h A experimental/Intersection/CubicParameterization_Test.cpp A experimental/Intersection/LineIntersection.h A experimental/Intersection/CubicSubDivide.cpp A experimental/Intersection/CubicParameterization.cpp A experimental/Intersection/QuadraticBezierClip_Test.cpp A experimental/Intersection/QuadraticBezierClip.cpp A experimental/Intersection/BezierClip_Test.cpp A experimental/Intersection/ConvexHull.cpp A experimental/Intersection/BezierClip.cpp A experimental/Intersection/QuadraticIntersection_TestData.cpp git-svn-id: http://skia.googlecode.com/svn/trunk@3005 2bbb7eff-a529-9590-31e7-b0007b416f81 --- experimental/Intersection/CubicBezierClip.cpp | 83 +++++++++++++++++++++++++++ 1 file changed, 83 insertions(+) create mode 100644 experimental/Intersection/CubicBezierClip.cpp (limited to 'experimental/Intersection/CubicBezierClip.cpp') diff --git a/experimental/Intersection/CubicBezierClip.cpp b/experimental/Intersection/CubicBezierClip.cpp new file mode 100644 index 0000000000..1b5c60c182 --- /dev/null +++ b/experimental/Intersection/CubicBezierClip.cpp @@ -0,0 +1,83 @@ +#include "CubicIntersection.h" +#include "LineParameters.h" +#include // used for std::swap + +// return false if unable to clip (e.g., unable to create implicit line) +// caller should subdivide, or create degenerate if the values are too small +bool bezier_clip(const Cubic& cubic1, const Cubic& cubic2, double& minT, double& maxT) { + minT = 1; + maxT = 0; + // determine normalized implicit line equation for pt[0] to pt[3] + // of the form ax + by + c = 0, where a*a + b*b == 1 + + // find the implicit line equation parameters + LineParameters endLine; + endLine.cubicEndPoints(cubic1); + if (!endLine.normalize()) { + printf("line cannot be normalized: need more code here\n"); + return false; + } + + double distance[2]; + endLine.controlPtDistance(cubic1, distance); + + // find fat line + double top = distance[0]; + double bottom = distance[1]; + if (top > bottom) { + std::swap(top, bottom); + } + if (top * bottom >= 0) { + const double scale = 3/4.0; // http://cagd.cs.byu.edu/~tom/papers/bezclip.pdf (13) + if (top < 0) { + top *= scale; + bottom = 0; + } else { + top = 0; + bottom *= scale; + } + } else { + const double scale = 4/9.0; // http://cagd.cs.byu.edu/~tom/papers/bezclip.pdf (15) + top *= scale; + bottom *= scale; + } + + // compute intersecting candidate distance + Cubic distance2y; // points with X of (0, 1/3, 2/3, 1) + endLine.cubicDistanceY(cubic2, distance2y); + + int flags = 0; + if (approximately_lesser(distance2y[0].y, top)) { + flags |= kFindTopMin; + } else if (approximately_greater(distance2y[0].y, bottom)) { + flags |= kFindBottomMin; + } else { + minT = 0; + } + + if (approximately_lesser(distance2y[3].y, top)) { + flags |= kFindTopMax; + } else if (approximately_greater(distance2y[3].y, bottom)) { + flags |= kFindBottomMax; + } else { + maxT = 1; + } + // Find the intersection of distance convex hull and fat line. + char to_0[2]; + char to_3[2]; + bool do_1_2_edge = convex_x_hull(distance2y, to_0, to_3); + x_at(distance2y[0], distance2y[to_0[0]], top, bottom, flags, minT, maxT); + if (to_0[0] != to_0[1]) { + x_at(distance2y[0], distance2y[to_0[1]], top, bottom, flags, minT, maxT); + } + x_at(distance2y[to_3[0]], distance2y[3], top, bottom, flags, minT, maxT); + if (to_3[0] != to_3[1]) { + x_at(distance2y[to_3[1]], distance2y[3], top, bottom, flags, minT, maxT); + } + if (do_1_2_edge) { + x_at(distance2y[1], distance2y[2], top, bottom, flags, minT, maxT); + } + + return minT < maxT; // returns false if distance shows no intersection +} + -- cgit v1.2.3