1ec3ed6a5ebf6f2c406d7bcf94b6bc34fcaeb976eepoger@google.com/*
2ec3ed6a5ebf6f2c406d7bcf94b6bc34fcaeb976eepoger@google.com * Copyright 2006 The Android Open Source Project
3ec3ed6a5ebf6f2c406d7bcf94b6bc34fcaeb976eepoger@google.com *
4ec3ed6a5ebf6f2c406d7bcf94b6bc34fcaeb976eepoger@google.com * Use of this source code is governed by a BSD-style license that can be
5ec3ed6a5ebf6f2c406d7bcf94b6bc34fcaeb976eepoger@google.com * found in the LICENSE file.
6ec3ed6a5ebf6f2c406d7bcf94b6bc34fcaeb976eepoger@google.com */
7ec3ed6a5ebf6f2c406d7bcf94b6bc34fcaeb976eepoger@google.com
88a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com#ifndef SkGeometry_DEFINED
98a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com#define SkGeometry_DEFINED
108a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com
118a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com#include "SkMatrix.h"
126983f66d8b3a489133b751e2cef03e72a03bfeaereed#include "SkNx.h"
136983f66d8b3a489133b751e2cef03e72a03bfeaereed
146983f66d8b3a489133b751e2cef03e72a03bfeaereedstatic inline Sk2s from_point(const SkPoint& point) {
156983f66d8b3a489133b751e2cef03e72a03bfeaereed    return Sk2s::Load(&point.fX);
166983f66d8b3a489133b751e2cef03e72a03bfeaereed}
176983f66d8b3a489133b751e2cef03e72a03bfeaereed
186983f66d8b3a489133b751e2cef03e72a03bfeaereedstatic inline SkPoint to_point(const Sk2s& x) {
196983f66d8b3a489133b751e2cef03e72a03bfeaereed    SkPoint point;
206983f66d8b3a489133b751e2cef03e72a03bfeaereed    x.store(&point.fX);
216983f66d8b3a489133b751e2cef03e72a03bfeaereed    return point;
226983f66d8b3a489133b751e2cef03e72a03bfeaereed}
236983f66d8b3a489133b751e2cef03e72a03bfeaereed
246983f66d8b3a489133b751e2cef03e72a03bfeaereedstatic inline Sk2s sk2s_cubic_eval(const Sk2s& A, const Sk2s& B, const Sk2s& C, const Sk2s& D,
256983f66d8b3a489133b751e2cef03e72a03bfeaereed                                   const Sk2s& t) {
266983f66d8b3a489133b751e2cef03e72a03bfeaereed    return ((A * t + B) * t + C) * t + D;
276983f66d8b3a489133b751e2cef03e72a03bfeaereed}
288a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com
298a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com/** Given a quadratic equation Ax^2 + Bx + C = 0, return 0, 1, 2 roots for the
308a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com    equation.
318a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com*/
328a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.comint SkFindUnitQuadRoots(SkScalar A, SkScalar B, SkScalar C, SkScalar roots[2]);
338a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com
348a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com///////////////////////////////////////////////////////////////////////////////
358a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com
3640b7dd57ef1f4e91af72512d8ca57459b99d71bdreedSkPoint SkEvalQuadAt(const SkPoint src[3], SkScalar t);
3740b7dd57ef1f4e91af72512d8ca57459b99d71bdreedSkPoint SkEvalQuadTangentAt(const SkPoint src[3], SkScalar t);
3840b7dd57ef1f4e91af72512d8ca57459b99d71bdreed
398a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com/** Set pt to the point on the src quadratic specified by t. t must be
408a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com    0 <= t <= 1.0
418a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com*/
4265cb2cd2f7ad4146f055810b8bd77bff03a4e76ereedvoid SkEvalQuadAt(const SkPoint src[3], SkScalar t, SkPoint* pt, SkVector* tangent = NULL);
438a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com
446983f66d8b3a489133b751e2cef03e72a03bfeaereed/**
456983f66d8b3a489133b751e2cef03e72a03bfeaereed *  output is : eval(t) == coeff[0] * t^2 + coeff[1] * t + coeff[2]
466983f66d8b3a489133b751e2cef03e72a03bfeaereed */
476983f66d8b3a489133b751e2cef03e72a03bfeaereedvoid SkQuadToCoeff(const SkPoint pts[3], SkPoint coeff[3]);
486983f66d8b3a489133b751e2cef03e72a03bfeaereed
496983f66d8b3a489133b751e2cef03e72a03bfeaereed/**
506983f66d8b3a489133b751e2cef03e72a03bfeaereed *  output is : eval(t) == coeff[0] * t^3 + coeff[1] * t^2 + coeff[2] * t + coeff[3]
516983f66d8b3a489133b751e2cef03e72a03bfeaereed */
526983f66d8b3a489133b751e2cef03e72a03bfeaereedvoid SkCubicToCoeff(const SkPoint pts[4], SkPoint coeff[4]);
536983f66d8b3a489133b751e2cef03e72a03bfeaereed
548a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com/** Given a src quadratic bezier, chop it at the specified t value,
558a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com    where 0 < t < 1, and return the two new quadratics in dst:
568a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com    dst[0..2] and dst[2..4]
578a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com*/
588a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.comvoid SkChopQuadAt(const SkPoint src[3], SkPoint dst[5], SkScalar t);
598a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com
608a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com/** Given a src quadratic bezier, chop it at the specified t == 1/2,
618a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com    The new quads are returned in dst[0..2] and dst[2..4]
628a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com*/
638a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.comvoid SkChopQuadAtHalf(const SkPoint src[3], SkPoint dst[5]);
648a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com
658a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com/** Given the 3 coefficients for a quadratic bezier (either X or Y values), look
668a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com    for extrema, and return the number of t-values that are found that represent
678a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com    these extrema. If the quadratic has no extrema betwee (0..1) exclusive, the
688a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com    function returns 0.
698a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com    Returned count      tValues[]
708a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com    0                   ignored
718a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com    1                   0 < tValues[0] < 1
728a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com*/
738a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.comint SkFindQuadExtrema(SkScalar a, SkScalar b, SkScalar c, SkScalar tValues[1]);
748a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com
758a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com/** Given 3 points on a quadratic bezier, chop it into 1, 2 beziers such that
768a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com    the resulting beziers are monotonic in Y. This is called by the scan converter.
778a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com    Depending on what is returned, dst[] is treated as follows
78909994fbae0ffb532f42feac8859f8d86bbf64dereed@android.com    0   dst[0..2] is the original quad
79909994fbae0ffb532f42feac8859f8d86bbf64dereed@android.com    1   dst[0..2] and dst[2..4] are the two new quads
808a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com*/
818a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.comint SkChopQuadAtYExtrema(const SkPoint src[3], SkPoint dst[5]);
8277f0ef726f1f8b6769ed2509171afce8bac00b23reed@android.comint SkChopQuadAtXExtrema(const SkPoint src[3], SkPoint dst[5]);
838a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com
845383a7525355dec72efa2083aeadffdd09a962b9egdaniel@google.com/** Given 3 points on a quadratic bezier, if the point of maximum
855383a7525355dec72efa2083aeadffdd09a962b9egdaniel@google.com    curvature exists on the segment, returns the t value for this
865383a7525355dec72efa2083aeadffdd09a962b9egdaniel@google.com    point along the curve. Otherwise it will return a value of 0.
875383a7525355dec72efa2083aeadffdd09a962b9egdaniel@google.com*/
88891372c3b5b8229cf5c20b085f2d9448525f98e4reedSkScalar SkFindQuadMaxCurvature(const SkPoint src[3]);
895383a7525355dec72efa2083aeadffdd09a962b9egdaniel@google.com
908a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com/** Given 3 points on a quadratic bezier, divide it into 2 quadratics
918a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com    if the point of maximum curvature exists on the quad segment.
928a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com    Depending on what is returned, dst[] is treated as follows
938a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com    1   dst[0..2] is the original quad
948a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com    2   dst[0..2] and dst[2..4] are the two new quads
958a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com    If dst == null, it is ignored and only the count is returned.
968a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com*/
978a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.comint SkChopQuadAtMaxCurvature(const SkPoint src[3], SkPoint dst[5]);
988a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com
99945a139553a9c9da03766213661d7f5fd6ed3042reed@android.com/** Given 3 points on a quadratic bezier, use degree elevation to
100945a139553a9c9da03766213661d7f5fd6ed3042reed@android.com    convert it into the cubic fitting the same curve. The new cubic
101945a139553a9c9da03766213661d7f5fd6ed3042reed@android.com    curve is returned in dst[0..3].
102945a139553a9c9da03766213661d7f5fd6ed3042reed@android.com*/
1037ffb1b21abcc7bbed5a0fc711f6dd7b9dbb4f577ctguil@chromium.orgSK_API void SkConvertQuadToCubic(const SkPoint src[3], SkPoint dst[4]);
104945a139553a9c9da03766213661d7f5fd6ed3042reed@android.com
105ad91799832b9ba2a3de30c0f57968148b4be17afreed@google.com///////////////////////////////////////////////////////////////////////////////
1068a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com
1078a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com/** Set pt to the point on the src cubic specified by t. t must be
1088a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com    0 <= t <= 1.0
1098a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com*/
110ad91799832b9ba2a3de30c0f57968148b4be17afreed@google.comvoid SkEvalCubicAt(const SkPoint src[4], SkScalar t, SkPoint* locOrNull,
111ad91799832b9ba2a3de30c0f57968148b4be17afreed@google.com                   SkVector* tangentOrNull, SkVector* curvatureOrNull);
1128a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com
1138a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com/** Given a src cubic bezier, chop it at the specified t value,
1148a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com    where 0 < t < 1, and return the two new cubics in dst:
1158a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com    dst[0..3] and dst[3..6]
1168a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com*/
1178a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.comvoid SkChopCubicAt(const SkPoint src[4], SkPoint dst[7], SkScalar t);
1186b9ef90c029c7c783f156ffd6fb1ba047bec63e0reed
119647a804c3dd53b6743091ec97dd12111f90efec3bsalomon@google.com/** Given a src cubic bezier, chop it at the specified t values,
120647a804c3dd53b6743091ec97dd12111f90efec3bsalomon@google.com    where 0 < t < 1, and return the new cubics in dst:
121647a804c3dd53b6743091ec97dd12111f90efec3bsalomon@google.com    dst[0..3],dst[3..6],...,dst[3*t_count..3*(t_count+1)]
122647a804c3dd53b6743091ec97dd12111f90efec3bsalomon@google.com*/
123647a804c3dd53b6743091ec97dd12111f90efec3bsalomon@google.comvoid SkChopCubicAt(const SkPoint src[4], SkPoint dst[], const SkScalar t[],
124ad91799832b9ba2a3de30c0f57968148b4be17afreed@google.com                   int t_count);
1258a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com
1268a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com/** Given a src cubic bezier, chop it at the specified t == 1/2,
1278a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com    The new cubics are returned in dst[0..3] and dst[3..6]
1288a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com*/
1298a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.comvoid SkChopCubicAtHalf(const SkPoint src[4], SkPoint dst[7]);
1308a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com
1318a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com/** Given the 4 coefficients for a cubic bezier (either X or Y values), look
1328a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com    for extrema, and return the number of t-values that are found that represent
1338a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com    these extrema. If the cubic has no extrema betwee (0..1) exclusive, the
1348a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com    function returns 0.
1358a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com    Returned count      tValues[]
1368a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com    0                   ignored
1378a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com    1                   0 < tValues[0] < 1
1388a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com    2                   0 < tValues[0] < tValues[1] < 1
1398a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com*/
140ad91799832b9ba2a3de30c0f57968148b4be17afreed@google.comint SkFindCubicExtrema(SkScalar a, SkScalar b, SkScalar c, SkScalar d,
141ad91799832b9ba2a3de30c0f57968148b4be17afreed@google.com                       SkScalar tValues[2]);
1428a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com
1438a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com/** Given 4 points on a cubic bezier, chop it into 1, 2, 3 beziers such that
1448a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com    the resulting beziers are monotonic in Y. This is called by the scan converter.
1458a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com    Depending on what is returned, dst[] is treated as follows
146909994fbae0ffb532f42feac8859f8d86bbf64dereed@android.com    0   dst[0..3] is the original cubic
147909994fbae0ffb532f42feac8859f8d86bbf64dereed@android.com    1   dst[0..3] and dst[3..6] are the two new cubics
148909994fbae0ffb532f42feac8859f8d86bbf64dereed@android.com    2   dst[0..3], dst[3..6], dst[6..9] are the three new cubics
1498a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com    If dst == null, it is ignored and only the count is returned.
1508a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com*/
1518a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.comint SkChopCubicAtYExtrema(const SkPoint src[4], SkPoint dst[10]);
152909994fbae0ffb532f42feac8859f8d86bbf64dereed@android.comint SkChopCubicAtXExtrema(const SkPoint src[4], SkPoint dst[10]);
1538a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com
1548a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com/** Given a cubic bezier, return 0, 1, or 2 t-values that represent the
1558a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com    inflection points.
1568a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com*/
1578a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.comint SkFindCubicInflections(const SkPoint src[4], SkScalar tValues[2]);
1588a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com
159647a804c3dd53b6743091ec97dd12111f90efec3bsalomon@google.com/** Return 1 for no chop, 2 for having chopped the cubic at a single
160647a804c3dd53b6743091ec97dd12111f90efec3bsalomon@google.com    inflection point, 3 for having chopped at 2 inflection points.
161dbeeac33329f5fd7dbd3514cd7189ca6ed080476bsalomon@google.com    dst will hold the resulting 1, 2, or 3 cubics.
1628a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com*/
1638a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.comint SkChopCubicAtInflections(const SkPoint src[4], SkPoint dst[10]);
1648a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com
1658a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.comint SkFindCubicMaxCurvature(const SkPoint src[4], SkScalar tValues[3]);
166ad91799832b9ba2a3de30c0f57968148b4be17afreed@google.comint SkChopCubicAtMaxCurvature(const SkPoint src[4], SkPoint dst[13],
167ad91799832b9ba2a3de30c0f57968148b4be17afreed@google.com                              SkScalar tValues[3] = NULL);
1688a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com
169dc3088570f945ed0ede84f0af0016eedc267dda3reedbool SkChopMonoCubicAtX(SkPoint src[4], SkScalar y, SkPoint dst[7]);
170dc3088570f945ed0ede84f0af0016eedc267dda3reedbool SkChopMonoCubicAtY(SkPoint src[4], SkScalar x, SkPoint dst[7]);
171dc3088570f945ed0ede84f0af0016eedc267dda3reed
1728dd31cf69e24ff82865309781107dfab948b6a02caryclarkenum SkCubicType {
1738dd31cf69e24ff82865309781107dfab948b6a02caryclark    kSerpentine_SkCubicType,
1748dd31cf69e24ff82865309781107dfab948b6a02caryclark    kCusp_SkCubicType,
1758dd31cf69e24ff82865309781107dfab948b6a02caryclark    kLoop_SkCubicType,
1768dd31cf69e24ff82865309781107dfab948b6a02caryclark    kQuadratic_SkCubicType,
1778dd31cf69e24ff82865309781107dfab948b6a02caryclark    kLine_SkCubicType,
1788dd31cf69e24ff82865309781107dfab948b6a02caryclark    kPoint_SkCubicType
1798dd31cf69e24ff82865309781107dfab948b6a02caryclark};
1808dd31cf69e24ff82865309781107dfab948b6a02caryclark
1818dd31cf69e24ff82865309781107dfab948b6a02caryclark/** Returns the cubic classification. Pass scratch storage for computing inflection data,
1828dd31cf69e24ff82865309781107dfab948b6a02caryclark    which can be used with additional work to find the loop intersections and so on.
1838dd31cf69e24ff82865309781107dfab948b6a02caryclark*/
1848dd31cf69e24ff82865309781107dfab948b6a02caryclarkSkCubicType SkClassifyCubic(const SkPoint p[4], SkScalar inflection[3]);
1858dd31cf69e24ff82865309781107dfab948b6a02caryclark
186ad91799832b9ba2a3de30c0f57968148b4be17afreed@google.com///////////////////////////////////////////////////////////////////////////////
1878a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com
1888a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.comenum SkRotationDirection {
1898a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com    kCW_SkRotationDirection,
1908a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com    kCCW_SkRotationDirection
1918a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com};
1928a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com
1938a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com/** Maximum number of points needed in the quadPoints[] parameter for
1948a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com    SkBuildQuadArc()
1958a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com*/
1968a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com#define kSkBuildQuadArcStorage  17
1978a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com
1988a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com/** Given 2 unit vectors and a rotation direction, fill out the specified
1998a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com    array of points with quadratic segments. Return is the number of points
2008a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com    written to, which will be { 0, 3, 5, 7, ... kSkBuildQuadArcStorage }
2018a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com
2028a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com    matrix, if not null, is appled to the points before they are returned.
2038a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com*/
204ad91799832b9ba2a3de30c0f57968148b4be17afreed@google.comint SkBuildQuadArc(const SkVector& unitStart, const SkVector& unitStop,
205ad91799832b9ba2a3de30c0f57968148b4be17afreed@google.com                   SkRotationDirection, const SkMatrix*, SkPoint quadPoints[]);
2068a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com
20728552e12a019bf5ae55c9e8602bbe216562d7a3emike@reedtribe.orgstruct SkConic {
208220f926d9d4b38a9018c922c095847bbd261f583reed    SkConic() {}
209220f926d9d4b38a9018c922c095847bbd261f583reed    SkConic(const SkPoint& p0, const SkPoint& p1, const SkPoint& p2, SkScalar w) {
210220f926d9d4b38a9018c922c095847bbd261f583reed        fPts[0] = p0;
211220f926d9d4b38a9018c922c095847bbd261f583reed        fPts[1] = p1;
212220f926d9d4b38a9018c922c095847bbd261f583reed        fPts[2] = p2;
213220f926d9d4b38a9018c922c095847bbd261f583reed        fW = w;
214220f926d9d4b38a9018c922c095847bbd261f583reed    }
215220f926d9d4b38a9018c922c095847bbd261f583reed    SkConic(const SkPoint pts[3], SkScalar w) {
216220f926d9d4b38a9018c922c095847bbd261f583reed        memcpy(fPts, pts, sizeof(fPts));
217220f926d9d4b38a9018c922c095847bbd261f583reed        fW = w;
218220f926d9d4b38a9018c922c095847bbd261f583reed    }
219220f926d9d4b38a9018c922c095847bbd261f583reed
220c518710d9a99c4d0adf759a102f4a1cb582f5939reed@google.com    SkPoint  fPts[3];
221c518710d9a99c4d0adf759a102f4a1cb582f5939reed@google.com    SkScalar fW;
222c518710d9a99c4d0adf759a102f4a1cb582f5939reed@google.com
223c518710d9a99c4d0adf759a102f4a1cb582f5939reed@google.com    void set(const SkPoint pts[3], SkScalar w) {
224c518710d9a99c4d0adf759a102f4a1cb582f5939reed@google.com        memcpy(fPts, pts, 3 * sizeof(SkPoint));
225c518710d9a99c4d0adf759a102f4a1cb582f5939reed@google.com        fW = w;
226c518710d9a99c4d0adf759a102f4a1cb582f5939reed@google.com    }
227c518710d9a99c4d0adf759a102f4a1cb582f5939reed@google.com
228d5d27d9b146731b871b1bcc6d6de36fba2d5ea44reed    void set(const SkPoint& p0, const SkPoint& p1, const SkPoint& p2, SkScalar w) {
229d5d27d9b146731b871b1bcc6d6de36fba2d5ea44reed        fPts[0] = p0;
230d5d27d9b146731b871b1bcc6d6de36fba2d5ea44reed        fPts[1] = p1;
231d5d27d9b146731b871b1bcc6d6de36fba2d5ea44reed        fPts[2] = p2;
232d5d27d9b146731b871b1bcc6d6de36fba2d5ea44reed        fW = w;
233d5d27d9b146731b871b1bcc6d6de36fba2d5ea44reed    }
234d5d27d9b146731b871b1bcc6d6de36fba2d5ea44reed
23524bd210f2e2cf66f356b4e98f7801631089b8aa3reed@google.com    /**
23624bd210f2e2cf66f356b4e98f7801631089b8aa3reed@google.com     *  Given a t-value [0...1] return its position and/or tangent.
23724bd210f2e2cf66f356b4e98f7801631089b8aa3reed@google.com     *  If pos is not null, return its position at the t-value.
23824bd210f2e2cf66f356b4e98f7801631089b8aa3reed@google.com     *  If tangent is not null, return its tangent at the t-value. NOTE the
23924bd210f2e2cf66f356b4e98f7801631089b8aa3reed@google.com     *  tangent value's length is arbitrary, and only its direction should
24024bd210f2e2cf66f356b4e98f7801631089b8aa3reed@google.com     *  be used.
24124bd210f2e2cf66f356b4e98f7801631089b8aa3reed@google.com     */
24224bd210f2e2cf66f356b4e98f7801631089b8aa3reed@google.com    void evalAt(SkScalar t, SkPoint* pos, SkVector* tangent = NULL) const;
24328552e12a019bf5ae55c9e8602bbe216562d7a3emike@reedtribe.org    void chopAt(SkScalar t, SkConic dst[2]) const;
24428552e12a019bf5ae55c9e8602bbe216562d7a3emike@reedtribe.org    void chop(SkConic dst[2]) const;
2457841c63136e8aa2d3aadbeab8432405abcd73c32skia.committer@gmail.com
246b640203cd5733aaf110277e28e22007c5b541565reed    SkPoint evalAt(SkScalar t) const;
247b640203cd5733aaf110277e28e22007c5b541565reed    SkVector evalTangentAt(SkScalar t) const;
248b640203cd5733aaf110277e28e22007c5b541565reed
249af5c506cd6b63f43a0ebee2fb171ea55ba98e09fmike@reedtribe.org    void computeAsQuadError(SkVector* err) const;
250af5c506cd6b63f43a0ebee2fb171ea55ba98e09fmike@reedtribe.org    bool asQuadTol(SkScalar tol) const;
25197514f22e4cb85a0d79b089a1eecd54d4a952291mike@reedtribe.org
252277c3f87656c44e0a651ed0dd56efa16c0ab07b4reed@google.com    /**
253277c3f87656c44e0a651ed0dd56efa16c0ab07b4reed@google.com     *  return the power-of-2 number of quads needed to approximate this conic
254277c3f87656c44e0a651ed0dd56efa16c0ab07b4reed@google.com     *  with a sequence of quads. Will be >= 0.
255277c3f87656c44e0a651ed0dd56efa16c0ab07b4reed@google.com     */
2563df87cb36e9f9d2e04d2f81ac64cf3d778c33847mike@reedtribe.org    int computeQuadPOW2(SkScalar tol) const;
257277c3f87656c44e0a651ed0dd56efa16c0ab07b4reed@google.com
258277c3f87656c44e0a651ed0dd56efa16c0ab07b4reed@google.com    /**
259277c3f87656c44e0a651ed0dd56efa16c0ab07b4reed@google.com     *  Chop this conic into N quads, stored continguously in pts[], where
260277c3f87656c44e0a651ed0dd56efa16c0ab07b4reed@google.com     *  N = 1 << pow2. The amount of storage needed is (1 + 2 * N)
261277c3f87656c44e0a651ed0dd56efa16c0ab07b4reed@google.com     */
2623df87cb36e9f9d2e04d2f81ac64cf3d778c33847mike@reedtribe.org    int chopIntoQuadsPOW2(SkPoint pts[], int pow2) const;
2630c5c3867bdbde1005a7bbb9de9df93cc10e27782mike@reedtribe.org
2640c5c3867bdbde1005a7bbb9de9df93cc10e27782mike@reedtribe.org    bool findXExtrema(SkScalar* t) const;
2650c5c3867bdbde1005a7bbb9de9df93cc10e27782mike@reedtribe.org    bool findYExtrema(SkScalar* t) const;
26628552e12a019bf5ae55c9e8602bbe216562d7a3emike@reedtribe.org    bool chopAtXExtrema(SkConic dst[2]) const;
26728552e12a019bf5ae55c9e8602bbe216562d7a3emike@reedtribe.org    bool chopAtYExtrema(SkConic dst[2]) const;
26845fb8b60137c65106b7903285672d0f8a8041f97skia.committer@gmail.com
2695c082a14acbb70eec2fd6dc5a4c134799f3d8535mike@reedtribe.org    void computeTightBounds(SkRect* bounds) const;
2705c082a14acbb70eec2fd6dc5a4c134799f3d8535mike@reedtribe.org    void computeFastBounds(SkRect* bounds) const;
271def6468dd2daed36eced69098445aa99c90487d6commit-bot@chromium.org
272def6468dd2daed36eced69098445aa99c90487d6commit-bot@chromium.org    /** Find the parameter value where the conic takes on its maximum curvature.
273def6468dd2daed36eced69098445aa99c90487d6commit-bot@chromium.org     *
274def6468dd2daed36eced69098445aa99c90487d6commit-bot@chromium.org     *  @param t   output scalar for max curvature.  Will be unchanged if
275def6468dd2daed36eced69098445aa99c90487d6commit-bot@chromium.org     *             max curvature outside 0..1 range.
276def6468dd2daed36eced69098445aa99c90487d6commit-bot@chromium.org     *
277def6468dd2daed36eced69098445aa99c90487d6commit-bot@chromium.org     *  @return  true if max curvature found inside 0..1 range, false otherwise
278def6468dd2daed36eced69098445aa99c90487d6commit-bot@chromium.org     */
279def6468dd2daed36eced69098445aa99c90487d6commit-bot@chromium.org    bool findMaxCurvature(SkScalar* t) const;
280220f926d9d4b38a9018c922c095847bbd261f583reed
281220f926d9d4b38a9018c922c095847bbd261f583reed    static SkScalar TransformW(const SkPoint[3], SkScalar w, const SkMatrix&);
282d5d27d9b146731b871b1bcc6d6de36fba2d5ea44reed
283d5d27d9b146731b871b1bcc6d6de36fba2d5ea44reed    enum {
284d5d27d9b146731b871b1bcc6d6de36fba2d5ea44reed        kMaxConicsForArc = 5
285d5d27d9b146731b871b1bcc6d6de36fba2d5ea44reed    };
286d5d27d9b146731b871b1bcc6d6de36fba2d5ea44reed    static int BuildUnitArc(const SkVector& start, const SkVector& stop, SkRotationDirection,
287d5d27d9b146731b871b1bcc6d6de36fba2d5ea44reed                            const SkMatrix*, SkConic conics[kMaxConicsForArc]);
288c518710d9a99c4d0adf759a102f4a1cb582f5939reed@google.com};
289c518710d9a99c4d0adf759a102f4a1cb582f5939reed@google.com
2904e05fd25c88bea64a988ededfc810770095ed97creed@google.com#include "SkTemplates.h"
2914e05fd25c88bea64a988ededfc810770095ed97creed@google.com
2924e05fd25c88bea64a988ededfc810770095ed97creed@google.com/**
2934e05fd25c88bea64a988ededfc810770095ed97creed@google.com *  Help class to allocate storage for approximating a conic with N quads.
2944e05fd25c88bea64a988ededfc810770095ed97creed@google.com */
2954e05fd25c88bea64a988ededfc810770095ed97creed@google.comclass SkAutoConicToQuads {
2964e05fd25c88bea64a988ededfc810770095ed97creed@google.compublic:
2974e05fd25c88bea64a988ededfc810770095ed97creed@google.com    SkAutoConicToQuads() : fQuadCount(0) {}
2984e05fd25c88bea64a988ededfc810770095ed97creed@google.com
2994e05fd25c88bea64a988ededfc810770095ed97creed@google.com    /**
3004e05fd25c88bea64a988ededfc810770095ed97creed@google.com     *  Given a conic and a tolerance, return the array of points for the
3014e05fd25c88bea64a988ededfc810770095ed97creed@google.com     *  approximating quad(s). Call countQuads() to know the number of quads
3024e05fd25c88bea64a988ededfc810770095ed97creed@google.com     *  represented in these points.
3034e05fd25c88bea64a988ededfc810770095ed97creed@google.com     *
3044e05fd25c88bea64a988ededfc810770095ed97creed@google.com     *  The quads are allocated to share end-points. e.g. if there are 4 quads,
3054e05fd25c88bea64a988ededfc810770095ed97creed@google.com     *  there will be 9 points allocated as follows
3064e05fd25c88bea64a988ededfc810770095ed97creed@google.com     *      quad[0] == pts[0..2]
3074e05fd25c88bea64a988ededfc810770095ed97creed@google.com     *      quad[1] == pts[2..4]
3084e05fd25c88bea64a988ededfc810770095ed97creed@google.com     *      quad[2] == pts[4..6]
3094e05fd25c88bea64a988ededfc810770095ed97creed@google.com     *      quad[3] == pts[6..8]
3104e05fd25c88bea64a988ededfc810770095ed97creed@google.com     */
3114e05fd25c88bea64a988ededfc810770095ed97creed@google.com    const SkPoint* computeQuads(const SkConic& conic, SkScalar tol) {
3124e05fd25c88bea64a988ededfc810770095ed97creed@google.com        int pow2 = conic.computeQuadPOW2(tol);
3134e05fd25c88bea64a988ededfc810770095ed97creed@google.com        fQuadCount = 1 << pow2;
3144e05fd25c88bea64a988ededfc810770095ed97creed@google.com        SkPoint* pts = fStorage.reset(1 + 2 * fQuadCount);
3154e05fd25c88bea64a988ededfc810770095ed97creed@google.com        conic.chopIntoQuadsPOW2(pts, pow2);
3164e05fd25c88bea64a988ededfc810770095ed97creed@google.com        return pts;
3174e05fd25c88bea64a988ededfc810770095ed97creed@google.com    }
3184e05fd25c88bea64a988ededfc810770095ed97creed@google.com
3194e05fd25c88bea64a988ededfc810770095ed97creed@google.com    const SkPoint* computeQuads(const SkPoint pts[3], SkScalar weight,
3204e05fd25c88bea64a988ededfc810770095ed97creed@google.com                                SkScalar tol) {
3214e05fd25c88bea64a988ededfc810770095ed97creed@google.com        SkConic conic;
3224e05fd25c88bea64a988ededfc810770095ed97creed@google.com        conic.set(pts, weight);
3234e05fd25c88bea64a988ededfc810770095ed97creed@google.com        return computeQuads(conic, tol);
3244e05fd25c88bea64a988ededfc810770095ed97creed@google.com    }
3254e05fd25c88bea64a988ededfc810770095ed97creed@google.com
3264e05fd25c88bea64a988ededfc810770095ed97creed@google.com    int countQuads() const { return fQuadCount; }
3274e05fd25c88bea64a988ededfc810770095ed97creed@google.com
3284e05fd25c88bea64a988ededfc810770095ed97creed@google.comprivate:
3294e05fd25c88bea64a988ededfc810770095ed97creed@google.com    enum {
3304e05fd25c88bea64a988ededfc810770095ed97creed@google.com        kQuadCount = 8, // should handle most conics
3314e05fd25c88bea64a988ededfc810770095ed97creed@google.com        kPointCount = 1 + 2 * kQuadCount,
3324e05fd25c88bea64a988ededfc810770095ed97creed@google.com    };
3334e05fd25c88bea64a988ededfc810770095ed97creed@google.com    SkAutoSTMalloc<kPointCount, SkPoint> fStorage;
3344e05fd25c88bea64a988ededfc810770095ed97creed@google.com    int fQuadCount; // #quads for current usage
3354e05fd25c88bea64a988ededfc810770095ed97creed@google.com};
3364e05fd25c88bea64a988ededfc810770095ed97creed@google.com
3378a1c16ff38322f0210116fa7293eb8817c7e477ereed@android.com#endif
338