1ec3ed6a5ebf6f2c406d7bcf94b6bc34fcaeb976eepoger@google.com 2ec3ed6a5ebf6f2c406d7bcf94b6bc34fcaeb976eepoger@google.com/* 3ec3ed6a5ebf6f2c406d7bcf94b6bc34fcaeb976eepoger@google.com * Copyright 2006 The Android Open Source Project 4ec3ed6a5ebf6f2c406d7bcf94b6bc34fcaeb976eepoger@google.com * 5ec3ed6a5ebf6f2c406d7bcf94b6bc34fcaeb976eepoger@google.com * Use of this source code is governed by a BSD-style license that can be 6ec3ed6a5ebf6f2c406d7bcf94b6bc34fcaeb976eepoger@google.com * found in the LICENSE file. 7ec3ed6a5ebf6f2c406d7bcf94b6bc34fcaeb976eepoger@google.com */ 8ec3ed6a5ebf6f2c406d7bcf94b6bc34fcaeb976eepoger@google.com 98a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com 108a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com#ifndef SkGeometry_DEFINED 118a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com#define SkGeometry_DEFINED 128a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com 138a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com#include "SkMatrix.h" 148a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com 15945a139553a9c9da03766213661d7f5fd6ed3042reed@android.com/** An XRay is a half-line that runs from the specific point/origin to 16945a139553a9c9da03766213661d7f5fd6ed3042reed@android.com +infinity in the X direction. e.g. XRay(3,5) is the half-line 17945a139553a9c9da03766213661d7f5fd6ed3042reed@android.com (3,5)....(infinity, 5) 18945a139553a9c9da03766213661d7f5fd6ed3042reed@android.com */ 19945a139553a9c9da03766213661d7f5fd6ed3042reed@android.comtypedef SkPoint SkXRay; 20945a139553a9c9da03766213661d7f5fd6ed3042reed@android.com 212e086190e55a01dc2f7b74df6f2828e8cac2b9abkbr@chromium.org/** Given a line segment from pts[0] to pts[1], and an xray, return true if 222e086190e55a01dc2f7b74df6f2828e8cac2b9abkbr@chromium.org they intersect. Optional outgoing "ambiguous" argument indicates 232e086190e55a01dc2f7b74df6f2828e8cac2b9abkbr@chromium.org whether the answer is ambiguous because the query occurred exactly at 242e086190e55a01dc2f7b74df6f2828e8cac2b9abkbr@chromium.org one of the endpoints' y coordinates, indicating that another query y 252e086190e55a01dc2f7b74df6f2828e8cac2b9abkbr@chromium.org coordinate is preferred for robustness. 26945a139553a9c9da03766213661d7f5fd6ed3042reed@android.com*/ 27ad91799832b9ba2a3de30c0f57968148b4be17afreed@google.combool SkXRayCrossesLine(const SkXRay& pt, const SkPoint pts[2], 28ad91799832b9ba2a3de30c0f57968148b4be17afreed@google.com bool* ambiguous = NULL); 29945a139553a9c9da03766213661d7f5fd6ed3042reed@android.com 308a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com/** Given a quadratic equation Ax^2 + Bx + C = 0, return 0, 1, 2 roots for the 318a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com equation. 328a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com*/ 338a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.comint SkFindUnitQuadRoots(SkScalar A, SkScalar B, SkScalar C, SkScalar roots[2]); 348a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com 358a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com/////////////////////////////////////////////////////////////////////////////// 368a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com 378a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com/** Set pt to the point on the src quadratic specified by t. t must be 388a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com 0 <= t <= 1.0 398a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com*/ 40ad91799832b9ba2a3de30c0f57968148b4be17afreed@google.comvoid SkEvalQuadAt(const SkPoint src[3], SkScalar t, SkPoint* pt, 41ad91799832b9ba2a3de30c0f57968148b4be17afreed@google.com SkVector* tangent = NULL); 42ad91799832b9ba2a3de30c0f57968148b4be17afreed@google.comvoid SkEvalQuadAtHalf(const SkPoint src[3], SkPoint* pt, 43ad91799832b9ba2a3de30c0f57968148b4be17afreed@google.com SkVector* tangent = NULL); 448a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com 458a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com/** Given a src quadratic bezier, chop it at the specified t value, 468a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com where 0 < t < 1, and return the two new quadratics in dst: 478a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com dst[0..2] and dst[2..4] 488a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com*/ 498a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.comvoid SkChopQuadAt(const SkPoint src[3], SkPoint dst[5], SkScalar t); 508a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com 518a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com/** Given a src quadratic bezier, chop it at the specified t == 1/2, 528a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com The new quads are returned in dst[0..2] and dst[2..4] 538a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com*/ 548a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.comvoid SkChopQuadAtHalf(const SkPoint src[3], SkPoint dst[5]); 558a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com 568a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com/** Given the 3 coefficients for a quadratic bezier (either X or Y values), look 578a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com for extrema, and return the number of t-values that are found that represent 588a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com these extrema. If the quadratic has no extrema betwee (0..1) exclusive, the 598a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com function returns 0. 608a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com Returned count tValues[] 618a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com 0 ignored 628a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com 1 0 < tValues[0] < 1 638a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com*/ 648a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.comint SkFindQuadExtrema(SkScalar a, SkScalar b, SkScalar c, SkScalar tValues[1]); 658a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com 668a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com/** Given 3 points on a quadratic bezier, chop it into 1, 2 beziers such that 678a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com the resulting beziers are monotonic in Y. This is called by the scan converter. 688a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com Depending on what is returned, dst[] is treated as follows 69909994fbae0ffb532f42feac8859f8d86bbf64dereed@android.com 0 dst[0..2] is the original quad 70909994fbae0ffb532f42feac8859f8d86bbf64dereed@android.com 1 dst[0..2] and dst[2..4] are the two new quads 718a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com*/ 728a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.comint SkChopQuadAtYExtrema(const SkPoint src[3], SkPoint dst[5]); 7377f0ef726f1f8b6769ed2509171afce8bac00b23reed@android.comint SkChopQuadAtXExtrema(const SkPoint src[3], SkPoint dst[5]); 748a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com 755383a7525355dec72efa2083aeadffdd09a962b9egdaniel@google.com/** Given 3 points on a quadratic bezier, if the point of maximum 765383a7525355dec72efa2083aeadffdd09a962b9egdaniel@google.com curvature exists on the segment, returns the t value for this 775383a7525355dec72efa2083aeadffdd09a962b9egdaniel@google.com point along the curve. Otherwise it will return a value of 0. 785383a7525355dec72efa2083aeadffdd09a962b9egdaniel@google.com*/ 795383a7525355dec72efa2083aeadffdd09a962b9egdaniel@google.comfloat SkFindQuadMaxCurvature(const SkPoint src[3]); 805383a7525355dec72efa2083aeadffdd09a962b9egdaniel@google.com 818a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com/** Given 3 points on a quadratic bezier, divide it into 2 quadratics 828a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com if the point of maximum curvature exists on the quad segment. 838a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com Depending on what is returned, dst[] is treated as follows 848a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com 1 dst[0..2] is the original quad 858a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com 2 dst[0..2] and dst[2..4] are the two new quads 868a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com If dst == null, it is ignored and only the count is returned. 878a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com*/ 888a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.comint SkChopQuadAtMaxCurvature(const SkPoint src[3], SkPoint dst[5]); 898a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com 90945a139553a9c9da03766213661d7f5fd6ed3042reed@android.com/** Given 3 points on a quadratic bezier, use degree elevation to 91945a139553a9c9da03766213661d7f5fd6ed3042reed@android.com convert it into the cubic fitting the same curve. The new cubic 92945a139553a9c9da03766213661d7f5fd6ed3042reed@android.com curve is returned in dst[0..3]. 93945a139553a9c9da03766213661d7f5fd6ed3042reed@android.com*/ 947ffb1b21abcc7bbed5a0fc711f6dd7b9dbb4f577ctguil@chromium.orgSK_API void SkConvertQuadToCubic(const SkPoint src[3], SkPoint dst[4]); 95945a139553a9c9da03766213661d7f5fd6ed3042reed@android.com 96ad91799832b9ba2a3de30c0f57968148b4be17afreed@google.com/////////////////////////////////////////////////////////////////////////////// 978a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com 988a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com/** Convert from parametric from (pts) to polynomial coefficients 998a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com coeff[0]*T^3 + coeff[1]*T^2 + coeff[2]*T + coeff[3] 1008a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com*/ 1018a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.comvoid SkGetCubicCoeff(const SkPoint pts[4], SkScalar cx[4], SkScalar cy[4]); 1028a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com 1038a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com/** Set pt to the point on the src cubic specified by t. t must be 1048a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com 0 <= t <= 1.0 1058a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com*/ 106ad91799832b9ba2a3de30c0f57968148b4be17afreed@google.comvoid SkEvalCubicAt(const SkPoint src[4], SkScalar t, SkPoint* locOrNull, 107ad91799832b9ba2a3de30c0f57968148b4be17afreed@google.com SkVector* tangentOrNull, SkVector* curvatureOrNull); 1088a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com 1098a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com/** Given a src cubic bezier, chop it at the specified t value, 1108a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com where 0 < t < 1, and return the two new cubics in dst: 1118a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com dst[0..3] and dst[3..6] 1128a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com*/ 1138a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.comvoid SkChopCubicAt(const SkPoint src[4], SkPoint dst[7], SkScalar t); 114647a804c3dd53b6743091ec97dd12111f90efec3bsalomon@google.com/** Given a src cubic bezier, chop it at the specified t values, 115647a804c3dd53b6743091ec97dd12111f90efec3bsalomon@google.com where 0 < t < 1, and return the new cubics in dst: 116647a804c3dd53b6743091ec97dd12111f90efec3bsalomon@google.com dst[0..3],dst[3..6],...,dst[3*t_count..3*(t_count+1)] 117647a804c3dd53b6743091ec97dd12111f90efec3bsalomon@google.com*/ 118647a804c3dd53b6743091ec97dd12111f90efec3bsalomon@google.comvoid SkChopCubicAt(const SkPoint src[4], SkPoint dst[], const SkScalar t[], 119ad91799832b9ba2a3de30c0f57968148b4be17afreed@google.com int t_count); 1208a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com 1218a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com/** Given a src cubic bezier, chop it at the specified t == 1/2, 1228a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com The new cubics are returned in dst[0..3] and dst[3..6] 1238a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com*/ 1248a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.comvoid SkChopCubicAtHalf(const SkPoint src[4], SkPoint dst[7]); 1258a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com 1268a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com/** Given the 4 coefficients for a cubic bezier (either X or Y values), look 1278a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com for extrema, and return the number of t-values that are found that represent 1288a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com these extrema. If the cubic has no extrema betwee (0..1) exclusive, the 1298a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com function returns 0. 1308a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com Returned count tValues[] 1318a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com 0 ignored 1328a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com 1 0 < tValues[0] < 1 1338a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com 2 0 < tValues[0] < tValues[1] < 1 1348a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com*/ 135ad91799832b9ba2a3de30c0f57968148b4be17afreed@google.comint SkFindCubicExtrema(SkScalar a, SkScalar b, SkScalar c, SkScalar d, 136ad91799832b9ba2a3de30c0f57968148b4be17afreed@google.com SkScalar tValues[2]); 1378a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com 1388a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com/** Given 4 points on a cubic bezier, chop it into 1, 2, 3 beziers such that 1398a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com the resulting beziers are monotonic in Y. This is called by the scan converter. 1408a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com Depending on what is returned, dst[] is treated as follows 141909994fbae0ffb532f42feac8859f8d86bbf64dereed@android.com 0 dst[0..3] is the original cubic 142909994fbae0ffb532f42feac8859f8d86bbf64dereed@android.com 1 dst[0..3] and dst[3..6] are the two new cubics 143909994fbae0ffb532f42feac8859f8d86bbf64dereed@android.com 2 dst[0..3], dst[3..6], dst[6..9] are the three new cubics 1448a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com If dst == null, it is ignored and only the count is returned. 1458a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com*/ 1468a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.comint SkChopCubicAtYExtrema(const SkPoint src[4], SkPoint dst[10]); 147909994fbae0ffb532f42feac8859f8d86bbf64dereed@android.comint SkChopCubicAtXExtrema(const SkPoint src[4], SkPoint dst[10]); 1488a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com 1498a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com/** Given a cubic bezier, return 0, 1, or 2 t-values that represent the 1508a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com inflection points. 1518a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com*/ 1528a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.comint SkFindCubicInflections(const SkPoint src[4], SkScalar tValues[2]); 1538a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com 154647a804c3dd53b6743091ec97dd12111f90efec3bsalomon@google.com/** Return 1 for no chop, 2 for having chopped the cubic at a single 155647a804c3dd53b6743091ec97dd12111f90efec3bsalomon@google.com inflection point, 3 for having chopped at 2 inflection points. 156dbeeac33329f5fd7dbd3514cd7189ca6ed080476bsalomon@google.com dst will hold the resulting 1, 2, or 3 cubics. 1578a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com*/ 1588a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.comint SkChopCubicAtInflections(const SkPoint src[4], SkPoint dst[10]); 1598a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com 1608a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.comint SkFindCubicMaxCurvature(const SkPoint src[4], SkScalar tValues[3]); 161ad91799832b9ba2a3de30c0f57968148b4be17afreed@google.comint SkChopCubicAtMaxCurvature(const SkPoint src[4], SkPoint dst[13], 162ad91799832b9ba2a3de30c0f57968148b4be17afreed@google.com SkScalar tValues[3] = NULL); 1638a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com 164945a139553a9c9da03766213661d7f5fd6ed3042reed@android.com/** Given a monotonic cubic bezier, determine whether an xray intersects the 165945a139553a9c9da03766213661d7f5fd6ed3042reed@android.com cubic. 166945a139553a9c9da03766213661d7f5fd6ed3042reed@android.com By definition the cubic is open at the starting point; in other 167945a139553a9c9da03766213661d7f5fd6ed3042reed@android.com words, if pt.fY is equivalent to cubic[0].fY, and pt.fX is to the 168945a139553a9c9da03766213661d7f5fd6ed3042reed@android.com left of the curve, the line is not considered to cross the curve, 169945a139553a9c9da03766213661d7f5fd6ed3042reed@android.com but if it is equal to cubic[3].fY then it is considered to 170945a139553a9c9da03766213661d7f5fd6ed3042reed@android.com cross. 1712e086190e55a01dc2f7b74df6f2828e8cac2b9abkbr@chromium.org Optional outgoing "ambiguous" argument indicates whether the answer is 1722e086190e55a01dc2f7b74df6f2828e8cac2b9abkbr@chromium.org ambiguous because the query occurred exactly at one of the endpoints' y 1732e086190e55a01dc2f7b74df6f2828e8cac2b9abkbr@chromium.org coordinates, indicating that another query y coordinate is preferred 1742e086190e55a01dc2f7b74df6f2828e8cac2b9abkbr@chromium.org for robustness. 175945a139553a9c9da03766213661d7f5fd6ed3042reed@android.com */ 176ad91799832b9ba2a3de30c0f57968148b4be17afreed@google.combool SkXRayCrossesMonotonicCubic(const SkXRay& pt, const SkPoint cubic[4], 177ad91799832b9ba2a3de30c0f57968148b4be17afreed@google.com bool* ambiguous = NULL); 178945a139553a9c9da03766213661d7f5fd6ed3042reed@android.com 179945a139553a9c9da03766213661d7f5fd6ed3042reed@android.com/** Given an arbitrary cubic bezier, return the number of times an xray crosses 180945a139553a9c9da03766213661d7f5fd6ed3042reed@android.com the cubic. Valid return values are [0..3] 181945a139553a9c9da03766213661d7f5fd6ed3042reed@android.com By definition the cubic is open at the starting point; in other 182945a139553a9c9da03766213661d7f5fd6ed3042reed@android.com words, if pt.fY is equivalent to cubic[0].fY, and pt.fX is to the 183945a139553a9c9da03766213661d7f5fd6ed3042reed@android.com left of the curve, the line is not considered to cross the curve, 184945a139553a9c9da03766213661d7f5fd6ed3042reed@android.com but if it is equal to cubic[3].fY then it is considered to 185945a139553a9c9da03766213661d7f5fd6ed3042reed@android.com cross. 1862e086190e55a01dc2f7b74df6f2828e8cac2b9abkbr@chromium.org Optional outgoing "ambiguous" argument indicates whether the answer is 1872e086190e55a01dc2f7b74df6f2828e8cac2b9abkbr@chromium.org ambiguous because the query occurred exactly at one of the endpoints' y 1882e086190e55a01dc2f7b74df6f2828e8cac2b9abkbr@chromium.org coordinates or at a tangent point, indicating that another query y 1892e086190e55a01dc2f7b74df6f2828e8cac2b9abkbr@chromium.org coordinate is preferred for robustness. 190945a139553a9c9da03766213661d7f5fd6ed3042reed@android.com */ 191ad91799832b9ba2a3de30c0f57968148b4be17afreed@google.comint SkNumXRayCrossingsForCubic(const SkXRay& pt, const SkPoint cubic[4], 192ad91799832b9ba2a3de30c0f57968148b4be17afreed@google.com bool* ambiguous = NULL); 193945a139553a9c9da03766213661d7f5fd6ed3042reed@android.com 194ad91799832b9ba2a3de30c0f57968148b4be17afreed@google.com/////////////////////////////////////////////////////////////////////////////// 1958a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com 1968a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.comenum SkRotationDirection { 1978a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com kCW_SkRotationDirection, 1988a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com kCCW_SkRotationDirection 1998a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com}; 2008a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com 2018a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com/** Maximum number of points needed in the quadPoints[] parameter for 2028a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com SkBuildQuadArc() 2038a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com*/ 2048a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com#define kSkBuildQuadArcStorage 17 2058a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com 2068a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com/** Given 2 unit vectors and a rotation direction, fill out the specified 2078a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com array of points with quadratic segments. Return is the number of points 2088a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com written to, which will be { 0, 3, 5, 7, ... kSkBuildQuadArcStorage } 2098a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com 2108a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com matrix, if not null, is appled to the points before they are returned. 2118a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com*/ 212ad91799832b9ba2a3de30c0f57968148b4be17afreed@google.comint SkBuildQuadArc(const SkVector& unitStart, const SkVector& unitStop, 213ad91799832b9ba2a3de30c0f57968148b4be17afreed@google.com SkRotationDirection, const SkMatrix*, SkPoint quadPoints[]); 2148a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com 215c518710d9a99c4d0adf759a102f4a1cb582f5939reed@google.com// experimental 21628552e12a019bf5ae55c9e8602bbe216562d7a3emike@reedtribe.orgstruct SkConic { 217c518710d9a99c4d0adf759a102f4a1cb582f5939reed@google.com SkPoint fPts[3]; 218c518710d9a99c4d0adf759a102f4a1cb582f5939reed@google.com SkScalar fW; 219c518710d9a99c4d0adf759a102f4a1cb582f5939reed@google.com 220c518710d9a99c4d0adf759a102f4a1cb582f5939reed@google.com void set(const SkPoint pts[3], SkScalar w) { 221c518710d9a99c4d0adf759a102f4a1cb582f5939reed@google.com memcpy(fPts, pts, 3 * sizeof(SkPoint)); 222c518710d9a99c4d0adf759a102f4a1cb582f5939reed@google.com fW = w; 223c518710d9a99c4d0adf759a102f4a1cb582f5939reed@google.com } 224c518710d9a99c4d0adf759a102f4a1cb582f5939reed@google.com 22524bd210f2e2cf66f356b4e98f7801631089b8aa3reed@google.com /** 22624bd210f2e2cf66f356b4e98f7801631089b8aa3reed@google.com * Given a t-value [0...1] return its position and/or tangent. 22724bd210f2e2cf66f356b4e98f7801631089b8aa3reed@google.com * If pos is not null, return its position at the t-value. 22824bd210f2e2cf66f356b4e98f7801631089b8aa3reed@google.com * If tangent is not null, return its tangent at the t-value. NOTE the 22924bd210f2e2cf66f356b4e98f7801631089b8aa3reed@google.com * tangent value's length is arbitrary, and only its direction should 23024bd210f2e2cf66f356b4e98f7801631089b8aa3reed@google.com * be used. 23124bd210f2e2cf66f356b4e98f7801631089b8aa3reed@google.com */ 23224bd210f2e2cf66f356b4e98f7801631089b8aa3reed@google.com void evalAt(SkScalar t, SkPoint* pos, SkVector* tangent = NULL) const; 23328552e12a019bf5ae55c9e8602bbe216562d7a3emike@reedtribe.org void chopAt(SkScalar t, SkConic dst[2]) const; 23428552e12a019bf5ae55c9e8602bbe216562d7a3emike@reedtribe.org void chop(SkConic dst[2]) const; 2357841c63136e8aa2d3aadbeab8432405abcd73c32skia.committer@gmail.com 236af5c506cd6b63f43a0ebee2fb171ea55ba98e09fmike@reedtribe.org void computeAsQuadError(SkVector* err) const; 237af5c506cd6b63f43a0ebee2fb171ea55ba98e09fmike@reedtribe.org bool asQuadTol(SkScalar tol) const; 23897514f22e4cb85a0d79b089a1eecd54d4a952291mike@reedtribe.org 239277c3f87656c44e0a651ed0dd56efa16c0ab07b4reed@google.com /** 240277c3f87656c44e0a651ed0dd56efa16c0ab07b4reed@google.com * return the power-of-2 number of quads needed to approximate this conic 241277c3f87656c44e0a651ed0dd56efa16c0ab07b4reed@google.com * with a sequence of quads. Will be >= 0. 242277c3f87656c44e0a651ed0dd56efa16c0ab07b4reed@google.com */ 2433df87cb36e9f9d2e04d2f81ac64cf3d778c33847mike@reedtribe.org int computeQuadPOW2(SkScalar tol) const; 244277c3f87656c44e0a651ed0dd56efa16c0ab07b4reed@google.com 245277c3f87656c44e0a651ed0dd56efa16c0ab07b4reed@google.com /** 246277c3f87656c44e0a651ed0dd56efa16c0ab07b4reed@google.com * Chop this conic into N quads, stored continguously in pts[], where 247277c3f87656c44e0a651ed0dd56efa16c0ab07b4reed@google.com * N = 1 << pow2. The amount of storage needed is (1 + 2 * N) 248277c3f87656c44e0a651ed0dd56efa16c0ab07b4reed@google.com */ 2493df87cb36e9f9d2e04d2f81ac64cf3d778c33847mike@reedtribe.org int chopIntoQuadsPOW2(SkPoint pts[], int pow2) const; 2500c5c3867bdbde1005a7bbb9de9df93cc10e27782mike@reedtribe.org 2510c5c3867bdbde1005a7bbb9de9df93cc10e27782mike@reedtribe.org bool findXExtrema(SkScalar* t) const; 2520c5c3867bdbde1005a7bbb9de9df93cc10e27782mike@reedtribe.org bool findYExtrema(SkScalar* t) const; 25328552e12a019bf5ae55c9e8602bbe216562d7a3emike@reedtribe.org bool chopAtXExtrema(SkConic dst[2]) const; 25428552e12a019bf5ae55c9e8602bbe216562d7a3emike@reedtribe.org bool chopAtYExtrema(SkConic dst[2]) const; 25545fb8b60137c65106b7903285672d0f8a8041f97skia.committer@gmail.com 2565c082a14acbb70eec2fd6dc5a4c134799f3d8535mike@reedtribe.org void computeTightBounds(SkRect* bounds) const; 2575c082a14acbb70eec2fd6dc5a4c134799f3d8535mike@reedtribe.org void computeFastBounds(SkRect* bounds) const; 258def6468dd2daed36eced69098445aa99c90487d6commit-bot@chromium.org 259def6468dd2daed36eced69098445aa99c90487d6commit-bot@chromium.org /** Find the parameter value where the conic takes on its maximum curvature. 260def6468dd2daed36eced69098445aa99c90487d6commit-bot@chromium.org * 261def6468dd2daed36eced69098445aa99c90487d6commit-bot@chromium.org * @param t output scalar for max curvature. Will be unchanged if 262def6468dd2daed36eced69098445aa99c90487d6commit-bot@chromium.org * max curvature outside 0..1 range. 263def6468dd2daed36eced69098445aa99c90487d6commit-bot@chromium.org * 264def6468dd2daed36eced69098445aa99c90487d6commit-bot@chromium.org * @return true if max curvature found inside 0..1 range, false otherwise 265def6468dd2daed36eced69098445aa99c90487d6commit-bot@chromium.org */ 266def6468dd2daed36eced69098445aa99c90487d6commit-bot@chromium.org bool findMaxCurvature(SkScalar* t) const; 267c518710d9a99c4d0adf759a102f4a1cb582f5939reed@google.com}; 268c518710d9a99c4d0adf759a102f4a1cb582f5939reed@google.com 2694e05fd25c88bea64a988ededfc810770095ed97creed@google.com#include "SkTemplates.h" 2704e05fd25c88bea64a988ededfc810770095ed97creed@google.com 2714e05fd25c88bea64a988ededfc810770095ed97creed@google.com/** 2724e05fd25c88bea64a988ededfc810770095ed97creed@google.com * Help class to allocate storage for approximating a conic with N quads. 2734e05fd25c88bea64a988ededfc810770095ed97creed@google.com */ 2744e05fd25c88bea64a988ededfc810770095ed97creed@google.comclass SkAutoConicToQuads { 2754e05fd25c88bea64a988ededfc810770095ed97creed@google.compublic: 2764e05fd25c88bea64a988ededfc810770095ed97creed@google.com SkAutoConicToQuads() : fQuadCount(0) {} 2774e05fd25c88bea64a988ededfc810770095ed97creed@google.com 2784e05fd25c88bea64a988ededfc810770095ed97creed@google.com /** 2794e05fd25c88bea64a988ededfc810770095ed97creed@google.com * Given a conic and a tolerance, return the array of points for the 2804e05fd25c88bea64a988ededfc810770095ed97creed@google.com * approximating quad(s). Call countQuads() to know the number of quads 2814e05fd25c88bea64a988ededfc810770095ed97creed@google.com * represented in these points. 2824e05fd25c88bea64a988ededfc810770095ed97creed@google.com * 2834e05fd25c88bea64a988ededfc810770095ed97creed@google.com * The quads are allocated to share end-points. e.g. if there are 4 quads, 2844e05fd25c88bea64a988ededfc810770095ed97creed@google.com * there will be 9 points allocated as follows 2854e05fd25c88bea64a988ededfc810770095ed97creed@google.com * quad[0] == pts[0..2] 2864e05fd25c88bea64a988ededfc810770095ed97creed@google.com * quad[1] == pts[2..4] 2874e05fd25c88bea64a988ededfc810770095ed97creed@google.com * quad[2] == pts[4..6] 2884e05fd25c88bea64a988ededfc810770095ed97creed@google.com * quad[3] == pts[6..8] 2894e05fd25c88bea64a988ededfc810770095ed97creed@google.com */ 2904e05fd25c88bea64a988ededfc810770095ed97creed@google.com const SkPoint* computeQuads(const SkConic& conic, SkScalar tol) { 2914e05fd25c88bea64a988ededfc810770095ed97creed@google.com int pow2 = conic.computeQuadPOW2(tol); 2924e05fd25c88bea64a988ededfc810770095ed97creed@google.com fQuadCount = 1 << pow2; 2934e05fd25c88bea64a988ededfc810770095ed97creed@google.com SkPoint* pts = fStorage.reset(1 + 2 * fQuadCount); 2944e05fd25c88bea64a988ededfc810770095ed97creed@google.com conic.chopIntoQuadsPOW2(pts, pow2); 2954e05fd25c88bea64a988ededfc810770095ed97creed@google.com return pts; 2964e05fd25c88bea64a988ededfc810770095ed97creed@google.com } 2974e05fd25c88bea64a988ededfc810770095ed97creed@google.com 2984e05fd25c88bea64a988ededfc810770095ed97creed@google.com const SkPoint* computeQuads(const SkPoint pts[3], SkScalar weight, 2994e05fd25c88bea64a988ededfc810770095ed97creed@google.com SkScalar tol) { 3004e05fd25c88bea64a988ededfc810770095ed97creed@google.com SkConic conic; 3014e05fd25c88bea64a988ededfc810770095ed97creed@google.com conic.set(pts, weight); 3024e05fd25c88bea64a988ededfc810770095ed97creed@google.com return computeQuads(conic, tol); 3034e05fd25c88bea64a988ededfc810770095ed97creed@google.com } 3044e05fd25c88bea64a988ededfc810770095ed97creed@google.com 3054e05fd25c88bea64a988ededfc810770095ed97creed@google.com int countQuads() const { return fQuadCount; } 3064e05fd25c88bea64a988ededfc810770095ed97creed@google.com 3074e05fd25c88bea64a988ededfc810770095ed97creed@google.comprivate: 3084e05fd25c88bea64a988ededfc810770095ed97creed@google.com enum { 3094e05fd25c88bea64a988ededfc810770095ed97creed@google.com kQuadCount = 8, // should handle most conics 3104e05fd25c88bea64a988ededfc810770095ed97creed@google.com kPointCount = 1 + 2 * kQuadCount, 3114e05fd25c88bea64a988ededfc810770095ed97creed@google.com }; 3124e05fd25c88bea64a988ededfc810770095ed97creed@google.com SkAutoSTMalloc<kPointCount, SkPoint> fStorage; 3134e05fd25c88bea64a988ededfc810770095ed97creed@google.com int fQuadCount; // #quads for current usage 3144e05fd25c88bea64a988ededfc810770095ed97creed@google.com}; 3154e05fd25c88bea64a988ededfc810770095ed97creed@google.com 3168a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com#endif 317