19e49fb63d355446b91d20ff78ad78b297e89a50dcaryclark@google.com/* 29e49fb63d355446b91d20ff78ad78b297e89a50dcaryclark@google.com * Copyright 2012 Google Inc. 39e49fb63d355446b91d20ff78ad78b297e89a50dcaryclark@google.com * 49e49fb63d355446b91d20ff78ad78b297e89a50dcaryclark@google.com * Use of this source code is governed by a BSD-style license that can be 59e49fb63d355446b91d20ff78ad78b297e89a50dcaryclark@google.com * found in the LICENSE file. 69e49fb63d355446b91d20ff78ad78b297e89a50dcaryclark@google.com */ 7d88e0894d0156f4d427b812fec69bfba3eec7a8dcaryclark@google.com#ifndef CurveIntersection_DEFINE 8d88e0894d0156f4d427b812fec69bfba3eec7a8dcaryclark@google.com#define CurveIntersection_DEFINE 9d88e0894d0156f4d427b812fec69bfba3eec7a8dcaryclark@google.com 10c682590538a27d73489bc91c098e000fdfb07ccfcaryclark@google.com#include "DataTypes.h" 11c682590538a27d73489bc91c098e000fdfb07ccfcaryclark@google.com 12c682590538a27d73489bc91c098e000fdfb07ccfcaryclark@google.comclass Intersections; 13c682590538a27d73489bc91c098e000fdfb07ccfcaryclark@google.com 14c682590538a27d73489bc91c098e000fdfb07ccfcaryclark@google.com// unit-testable utilities 15fa0588ff672564af1c235a63589573829035a60bcaryclark@google.comdouble axialIntersect(const Quadratic& q1, const _Point& p, bool vert); 16c682590538a27d73489bc91c098e000fdfb07ccfcaryclark@google.combool bezier_clip(const Cubic& cubic1, const Cubic& cubic2, double& minT, double& maxT); 17c682590538a27d73489bc91c098e000fdfb07ccfcaryclark@google.combool bezier_clip(const Quadratic& q1, const Quadratic& q2, double& minT, double& maxT); 18c682590538a27d73489bc91c098e000fdfb07ccfcaryclark@google.comint convex_hull(const Cubic& cubic, char order[4]); 19c682590538a27d73489bc91c098e000fdfb07ccfcaryclark@google.combool convex_x_hull(const Cubic& cubic, char connectTo0[2], char connectTo3[2]); 20c682590538a27d73489bc91c098e000fdfb07ccfcaryclark@google.combool implicit_matches(const Cubic& cubic1, const Cubic& cubic2); 21c682590538a27d73489bc91c098e000fdfb07ccfcaryclark@google.combool implicit_matches(const _Line& line1, const _Line& line2); 2278e17130f396d8b2157116c2504e357192f87ed1caryclark@google.combool implicit_matches_ulps(const _Line& one, const _Line& two, int ulps); 23c682590538a27d73489bc91c098e000fdfb07ccfcaryclark@google.combool implicit_matches(const Quadratic& quad1, const Quadratic& quad2); 24c682590538a27d73489bc91c098e000fdfb07ccfcaryclark@google.comvoid tangent(const Cubic& cubic, double t, _Point& result); 25c682590538a27d73489bc91c098e000fdfb07ccfcaryclark@google.comvoid tangent(const _Line& line, _Point& result); 26c682590538a27d73489bc91c098e000fdfb07ccfcaryclark@google.comvoid tangent(const Quadratic& quad, double t, _Point& result); 27c682590538a27d73489bc91c098e000fdfb07ccfcaryclark@google.com 28c682590538a27d73489bc91c098e000fdfb07ccfcaryclark@google.com// main functions 2947d73daa7a971e7eee5822def7922f7d43b2dc47caryclark@google.comenum ReduceOrder_Quadratics { 30c682590538a27d73489bc91c098e000fdfb07ccfcaryclark@google.com kReduceOrder_NoQuadraticsAllowed, 31c682590538a27d73489bc91c098e000fdfb07ccfcaryclark@google.com kReduceOrder_QuadraticsAllowed 32c682590538a27d73489bc91c098e000fdfb07ccfcaryclark@google.com}; 3347d73daa7a971e7eee5822def7922f7d43b2dc47caryclark@google.comenum ReduceOrder_Styles { 3447d73daa7a971e7eee5822def7922f7d43b2dc47caryclark@google.com kReduceOrder_TreatAsStroke, 3547d73daa7a971e7eee5822def7922f7d43b2dc47caryclark@google.com kReduceOrder_TreatAsFill 3647d73daa7a971e7eee5822def7922f7d43b2dc47caryclark@google.com}; 3747d73daa7a971e7eee5822def7922f7d43b2dc47caryclark@google.comint reduceOrder(const Cubic& cubic, Cubic& reduction, ReduceOrder_Quadratics , 3847d73daa7a971e7eee5822def7922f7d43b2dc47caryclark@google.com ReduceOrder_Styles ); 39c682590538a27d73489bc91c098e000fdfb07ccfcaryclark@google.comint reduceOrder(const _Line& line, _Line& reduction); 4047d73daa7a971e7eee5822def7922f7d43b2dc47caryclark@google.comint reduceOrder(const Quadratic& quad, Quadratic& reduction, ReduceOrder_Styles ); 41c682590538a27d73489bc91c098e000fdfb07ccfcaryclark@google.comint horizontalIntersect(const Cubic& cubic, double y, double tRange[3]); 42198e054b33051a6cd5f606ccbc8d539cefc5631fcaryclark@google.comint horizontalIntersect(const Cubic& cubic, double left, double right, double y, 43198e054b33051a6cd5f606ccbc8d539cefc5631fcaryclark@google.com double tRange[3]); 44fa0588ff672564af1c235a63589573829035a60bcaryclark@google.comint horizontalIntersect(const Cubic& cubic, double left, double right, double y, 45fa0588ff672564af1c235a63589573829035a60bcaryclark@google.com bool flipped, Intersections&); 46fa0588ff672564af1c235a63589573829035a60bcaryclark@google.comint horizontalIntersect(const _Line& line, double left, double right, 47fa0588ff672564af1c235a63589573829035a60bcaryclark@google.com double y, bool flipped, Intersections& ); 48198e054b33051a6cd5f606ccbc8d539cefc5631fcaryclark@google.comint horizontalIntersect(const Quadratic& quad, double left, double right, 49198e054b33051a6cd5f606ccbc8d539cefc5631fcaryclark@google.com double y, double tRange[2]); 50fa0588ff672564af1c235a63589573829035a60bcaryclark@google.comint horizontalIntersect(const Quadratic& quad, double left, double right, 51fa0588ff672564af1c235a63589573829035a60bcaryclark@google.com double y, bool flipped, Intersections& ); 52c682590538a27d73489bc91c098e000fdfb07ccfcaryclark@google.combool intersect(const Cubic& cubic1, const Cubic& cubic2, Intersections& ); 5373ca6243b31e225e9fd5b75a96cbc82d62557de6caryclark@google.com// the following flavor uses quadratic approximation instead of convex hulls 544aaaaeace7e617ddc473645756fb7c20790bc270caryclark@google.com//bool intersect2(const Cubic& cubic1, const Cubic& cubic2, Intersections& ); 5545a8fc6a8b00451f807783f2a6ec640e9bcc7256caryclark@google.com// like '2', but iterates on centers instead of possible edges 5645a8fc6a8b00451f807783f2a6ec640e9bcc7256caryclark@google.combool intersect3(const Cubic& cubic1, const Cubic& cubic2, Intersections& ); 57c83c70e911a38aea03db4af8dd9841d0d77bd129caryclark@google.comint intersect(const Cubic& cubic, Intersections& i); // return true if cubic self-intersects 5873ca6243b31e225e9fd5b75a96cbc82d62557de6caryclark@google.comint intersect(const Cubic& cubic, const Quadratic& quad, Intersections& ); 5973ca6243b31e225e9fd5b75a96cbc82d62557de6caryclark@google.comint intersect(const Cubic& cubic, const _Line& line, Intersections& ); 60f9502d7dfad5b361a3cdaa42eb75b593c95f79d8caryclark@google.comint intersectRay(const Cubic& quad, const _Line& line, Intersections& i); 61c682590538a27d73489bc91c098e000fdfb07ccfcaryclark@google.combool intersect(const Quadratic& q1, const Quadratic& q2, Intersections& ); 623350c3c68ab75cd08721da3a938b8d2b10096d70caryclark@google.comint intersect(const Quadratic& quad, const _Line& line, Intersections& ); 63235f56a92f6eb6accbb243e11b3c45e3798f38f2caryclark@google.com// the following flavor uses the implicit form instead of convex hulls 64235f56a92f6eb6accbb243e11b3c45e3798f38f2caryclark@google.combool intersect2(const Quadratic& q1, const Quadratic& q2, Intersections& i); 65235f56a92f6eb6accbb243e11b3c45e3798f38f2caryclark@google.comint intersectRay(const Quadratic& quad, const _Line& line, Intersections& i); 66235f56a92f6eb6accbb243e11b3c45e3798f38f2caryclark@google.com 67235f56a92f6eb6accbb243e11b3c45e3798f38f2caryclark@google.com 6815fa138f2276a77679530fb608463ff5b4133f7bcaryclark@google.combool isLinear(const Quadratic& quad, int startIndex, int endIndex); 6915fa138f2276a77679530fb608463ff5b4133f7bcaryclark@google.combool isLinear(const Cubic& cubic, int startIndex, int endIndex); 70fa0588ff672564af1c235a63589573829035a60bcaryclark@google.comdouble leftMostT(const Cubic& , double startT, double endT); 71fa0588ff672564af1c235a63589573829035a60bcaryclark@google.comdouble leftMostT(const _Line& , double startT, double endT); 72fa0588ff672564af1c235a63589573829035a60bcaryclark@google.comdouble leftMostT(const Quadratic& , double startT, double endT); 73fa0588ff672564af1c235a63589573829035a60bcaryclark@google.comint verticalIntersect(const Cubic& cubic, double top, double bottom, double x, 74fa0588ff672564af1c235a63589573829035a60bcaryclark@google.com bool flipped, Intersections& ); 75fa0588ff672564af1c235a63589573829035a60bcaryclark@google.comint verticalIntersect(const _Line& line, double top, double bottom, double x, 76fa0588ff672564af1c235a63589573829035a60bcaryclark@google.com bool flipped, Intersections& ); 77fa0588ff672564af1c235a63589573829035a60bcaryclark@google.comint verticalIntersect(const Quadratic& quad, double top, double bottom, 78fa0588ff672564af1c235a63589573829035a60bcaryclark@google.com double x, bool flipped, Intersections& ); 79d88e0894d0156f4d427b812fec69bfba3eec7a8dcaryclark@google.com 80d88e0894d0156f4d427b812fec69bfba3eec7a8dcaryclark@google.com#endif 81