1049d6fea481044fcc000e7782e5bc7046fc70844The Android Open Source Project/***************************************************************************/ 2049d6fea481044fcc000e7782e5bc7046fc70844The Android Open Source Project/* */ 3049d6fea481044fcc000e7782e5bc7046fc70844The Android Open Source Project/* ftbbox.c */ 4049d6fea481044fcc000e7782e5bc7046fc70844The Android Open Source Project/* */ 5049d6fea481044fcc000e7782e5bc7046fc70844The Android Open Source Project/* FreeType bbox computation (body). */ 6049d6fea481044fcc000e7782e5bc7046fc70844The Android Open Source Project/* */ 7a2b9955b49034a51dfbc8bf9f4e9d312149cecacXianzhu Wang/* Copyright 1996-2002, 2004, 2006, 2010, 2013 by */ 8049d6fea481044fcc000e7782e5bc7046fc70844The Android Open Source Project/* David Turner, Robert Wilhelm, and Werner Lemberg. */ 9049d6fea481044fcc000e7782e5bc7046fc70844The Android Open Source Project/* */ 10049d6fea481044fcc000e7782e5bc7046fc70844The Android Open Source Project/* This file is part of the FreeType project, and may only be used */ 11049d6fea481044fcc000e7782e5bc7046fc70844The Android Open Source Project/* modified and distributed under the terms of the FreeType project */ 12049d6fea481044fcc000e7782e5bc7046fc70844The Android Open Source Project/* license, LICENSE.TXT. By continuing to use, modify, or distribute */ 13049d6fea481044fcc000e7782e5bc7046fc70844The Android Open Source Project/* this file you indicate that you have read the license and */ 14049d6fea481044fcc000e7782e5bc7046fc70844The Android Open Source Project/* understand and accept it fully. */ 15049d6fea481044fcc000e7782e5bc7046fc70844The Android Open Source Project/* */ 16049d6fea481044fcc000e7782e5bc7046fc70844The Android Open Source Project/***************************************************************************/ 17049d6fea481044fcc000e7782e5bc7046fc70844The Android Open Source Project 18049d6fea481044fcc000e7782e5bc7046fc70844The Android Open Source Project 19049d6fea481044fcc000e7782e5bc7046fc70844The Android Open Source Project /*************************************************************************/ 20049d6fea481044fcc000e7782e5bc7046fc70844The Android Open Source Project /* */ 21049d6fea481044fcc000e7782e5bc7046fc70844The Android Open Source Project /* This component has a _single_ role: to compute exact outline bounding */ 22049d6fea481044fcc000e7782e5bc7046fc70844The Android Open Source Project /* boxes. */ 23049d6fea481044fcc000e7782e5bc7046fc70844The Android Open Source Project /* */ 24049d6fea481044fcc000e7782e5bc7046fc70844The Android Open Source Project /*************************************************************************/ 25049d6fea481044fcc000e7782e5bc7046fc70844The Android Open Source Project 26049d6fea481044fcc000e7782e5bc7046fc70844The Android Open Source Project 27049d6fea481044fcc000e7782e5bc7046fc70844The Android Open Source Project#include <ft2build.h> 28a2b9955b49034a51dfbc8bf9f4e9d312149cecacXianzhu Wang#include FT_INTERNAL_DEBUG_H 29a2b9955b49034a51dfbc8bf9f4e9d312149cecacXianzhu Wang 30049d6fea481044fcc000e7782e5bc7046fc70844The Android Open Source Project#include FT_BBOX_H 31049d6fea481044fcc000e7782e5bc7046fc70844The Android Open Source Project#include FT_IMAGE_H 32049d6fea481044fcc000e7782e5bc7046fc70844The Android Open Source Project#include FT_OUTLINE_H 33049d6fea481044fcc000e7782e5bc7046fc70844The Android Open Source Project#include FT_INTERNAL_CALC_H 34295ffce55e0198e7a9f7d46b33f5c2b4147bf821David 'Digit' Turner#include FT_INTERNAL_OBJECTS_H 35049d6fea481044fcc000e7782e5bc7046fc70844The Android Open Source Project 36049d6fea481044fcc000e7782e5bc7046fc70844The Android Open Source Project 37049d6fea481044fcc000e7782e5bc7046fc70844The Android Open Source Project typedef struct TBBox_Rec_ 38049d6fea481044fcc000e7782e5bc7046fc70844The Android Open Source Project { 39049d6fea481044fcc000e7782e5bc7046fc70844The Android Open Source Project FT_Vector last; 40049d6fea481044fcc000e7782e5bc7046fc70844The Android Open Source Project FT_BBox bbox; 41049d6fea481044fcc000e7782e5bc7046fc70844The Android Open Source Project 42049d6fea481044fcc000e7782e5bc7046fc70844The Android Open Source Project } TBBox_Rec; 43049d6fea481044fcc000e7782e5bc7046fc70844The Android Open Source Project 44049d6fea481044fcc000e7782e5bc7046fc70844The Android Open Source Project 45049d6fea481044fcc000e7782e5bc7046fc70844The Android Open Source Project /*************************************************************************/ 46049d6fea481044fcc000e7782e5bc7046fc70844The Android Open Source Project /* */ 47049d6fea481044fcc000e7782e5bc7046fc70844The Android Open Source Project /* <Function> */ 48049d6fea481044fcc000e7782e5bc7046fc70844The Android Open Source Project /* BBox_Move_To */ 49049d6fea481044fcc000e7782e5bc7046fc70844The Android Open Source Project /* */ 50049d6fea481044fcc000e7782e5bc7046fc70844The Android Open Source Project /* <Description> */ 51049d6fea481044fcc000e7782e5bc7046fc70844The Android Open Source Project /* This function is used as a `move_to' and `line_to' emitter during */ 52049d6fea481044fcc000e7782e5bc7046fc70844The Android Open Source Project /* FT_Outline_Decompose(). It simply records the destination point */ 53049d6fea481044fcc000e7782e5bc7046fc70844The Android Open Source Project /* in `user->last'; no further computations are necessary since we */ 54049d6fea481044fcc000e7782e5bc7046fc70844The Android Open Source Project /* use the cbox as the starting bbox which must be refined. */ 55049d6fea481044fcc000e7782e5bc7046fc70844The Android Open Source Project /* */ 56049d6fea481044fcc000e7782e5bc7046fc70844The Android Open Source Project /* <Input> */ 57049d6fea481044fcc000e7782e5bc7046fc70844The Android Open Source Project /* to :: A pointer to the destination vector. */ 58049d6fea481044fcc000e7782e5bc7046fc70844The Android Open Source Project /* */ 59049d6fea481044fcc000e7782e5bc7046fc70844The Android Open Source Project /* <InOut> */ 60049d6fea481044fcc000e7782e5bc7046fc70844The Android Open Source Project /* user :: A pointer to the current walk context. */ 61049d6fea481044fcc000e7782e5bc7046fc70844The Android Open Source Project /* */ 62049d6fea481044fcc000e7782e5bc7046fc70844The Android Open Source Project /* <Return> */ 63049d6fea481044fcc000e7782e5bc7046fc70844The Android Open Source Project /* Always 0. Needed for the interface only. */ 64049d6fea481044fcc000e7782e5bc7046fc70844The Android Open Source Project /* */ 65049d6fea481044fcc000e7782e5bc7046fc70844The Android Open Source Project static int 66049d6fea481044fcc000e7782e5bc7046fc70844The Android Open Source Project BBox_Move_To( FT_Vector* to, 67049d6fea481044fcc000e7782e5bc7046fc70844The Android Open Source Project TBBox_Rec* user ) 68049d6fea481044fcc000e7782e5bc7046fc70844The Android Open Source Project { 69049d6fea481044fcc000e7782e5bc7046fc70844The Android Open Source Project user->last = *to; 70049d6fea481044fcc000e7782e5bc7046fc70844The Android Open Source Project 71049d6fea481044fcc000e7782e5bc7046fc70844The Android Open Source Project return 0; 72049d6fea481044fcc000e7782e5bc7046fc70844The Android Open Source Project } 73049d6fea481044fcc000e7782e5bc7046fc70844The Android Open Source Project 74049d6fea481044fcc000e7782e5bc7046fc70844The Android Open Source Project 75049d6fea481044fcc000e7782e5bc7046fc70844The Android Open Source Project#define CHECK_X( p, bbox ) \ 76049d6fea481044fcc000e7782e5bc7046fc70844The Android Open Source Project ( p->x < bbox.xMin || p->x > bbox.xMax ) 77049d6fea481044fcc000e7782e5bc7046fc70844The Android Open Source Project 78049d6fea481044fcc000e7782e5bc7046fc70844The Android Open Source Project#define CHECK_Y( p, bbox ) \ 79049d6fea481044fcc000e7782e5bc7046fc70844The Android Open Source Project ( p->y < bbox.yMin || p->y > bbox.yMax ) 80049d6fea481044fcc000e7782e5bc7046fc70844The Android Open Source Project 81049d6fea481044fcc000e7782e5bc7046fc70844The Android Open Source Project 82049d6fea481044fcc000e7782e5bc7046fc70844The Android Open Source Project /*************************************************************************/ 83049d6fea481044fcc000e7782e5bc7046fc70844The Android Open Source Project /* */ 84049d6fea481044fcc000e7782e5bc7046fc70844The Android Open Source Project /* <Function> */ 85049d6fea481044fcc000e7782e5bc7046fc70844The Android Open Source Project /* BBox_Conic_Check */ 86049d6fea481044fcc000e7782e5bc7046fc70844The Android Open Source Project /* */ 87049d6fea481044fcc000e7782e5bc7046fc70844The Android Open Source Project /* <Description> */ 88049d6fea481044fcc000e7782e5bc7046fc70844The Android Open Source Project /* Finds the extrema of a 1-dimensional conic Bezier curve and update */ 89049d6fea481044fcc000e7782e5bc7046fc70844The Android Open Source Project /* a bounding range. This version uses direct computation, as it */ 90049d6fea481044fcc000e7782e5bc7046fc70844The Android Open Source Project /* doesn't need square roots. */ 91049d6fea481044fcc000e7782e5bc7046fc70844The Android Open Source Project /* */ 92049d6fea481044fcc000e7782e5bc7046fc70844The Android Open Source Project /* <Input> */ 93049d6fea481044fcc000e7782e5bc7046fc70844The Android Open Source Project /* y1 :: The start coordinate. */ 94049d6fea481044fcc000e7782e5bc7046fc70844The Android Open Source Project /* */ 95049d6fea481044fcc000e7782e5bc7046fc70844The Android Open Source Project /* y2 :: The coordinate of the control point. */ 96049d6fea481044fcc000e7782e5bc7046fc70844The Android Open Source Project /* */ 97049d6fea481044fcc000e7782e5bc7046fc70844The Android Open Source Project /* y3 :: The end coordinate. */ 98049d6fea481044fcc000e7782e5bc7046fc70844The Android Open Source Project /* */ 99049d6fea481044fcc000e7782e5bc7046fc70844The Android Open Source Project /* <InOut> */ 100049d6fea481044fcc000e7782e5bc7046fc70844The Android Open Source Project /* min :: The address of the current minimum. */ 101049d6fea481044fcc000e7782e5bc7046fc70844The Android Open Source Project /* */ 102049d6fea481044fcc000e7782e5bc7046fc70844The Android Open Source Project /* max :: The address of the current maximum. */ 103049d6fea481044fcc000e7782e5bc7046fc70844The Android Open Source Project /* */ 104049d6fea481044fcc000e7782e5bc7046fc70844The Android Open Source Project static void 105049d6fea481044fcc000e7782e5bc7046fc70844The Android Open Source Project BBox_Conic_Check( FT_Pos y1, 106049d6fea481044fcc000e7782e5bc7046fc70844The Android Open Source Project FT_Pos y2, 107049d6fea481044fcc000e7782e5bc7046fc70844The Android Open Source Project FT_Pos y3, 108049d6fea481044fcc000e7782e5bc7046fc70844The Android Open Source Project FT_Pos* min, 109049d6fea481044fcc000e7782e5bc7046fc70844The Android Open Source Project FT_Pos* max ) 110049d6fea481044fcc000e7782e5bc7046fc70844The Android Open Source Project { 111049d6fea481044fcc000e7782e5bc7046fc70844The Android Open Source Project if ( y1 <= y3 && y2 == y1 ) /* flat arc */ 112049d6fea481044fcc000e7782e5bc7046fc70844The Android Open Source Project goto Suite; 113049d6fea481044fcc000e7782e5bc7046fc70844The Android Open Source Project 114049d6fea481044fcc000e7782e5bc7046fc70844The Android Open Source Project if ( y1 < y3 ) 115049d6fea481044fcc000e7782e5bc7046fc70844The Android Open Source Project { 116049d6fea481044fcc000e7782e5bc7046fc70844The Android Open Source Project if ( y2 >= y1 && y2 <= y3 ) /* ascending arc */ 117049d6fea481044fcc000e7782e5bc7046fc70844The Android Open Source Project goto Suite; 118049d6fea481044fcc000e7782e5bc7046fc70844The Android Open Source Project } 119049d6fea481044fcc000e7782e5bc7046fc70844The Android Open Source Project else 120049d6fea481044fcc000e7782e5bc7046fc70844The Android Open Source Project { 121049d6fea481044fcc000e7782e5bc7046fc70844The Android Open Source Project if ( y2 >= y3 && y2 <= y1 ) /* descending arc */ 122049d6fea481044fcc000e7782e5bc7046fc70844The Android Open Source Project { 123049d6fea481044fcc000e7782e5bc7046fc70844The Android Open Source Project y2 = y1; 124049d6fea481044fcc000e7782e5bc7046fc70844The Android Open Source Project y1 = y3; 125049d6fea481044fcc000e7782e5bc7046fc70844The Android Open Source Project y3 = y2; 126049d6fea481044fcc000e7782e5bc7046fc70844The Android Open Source Project goto Suite; 127049d6fea481044fcc000e7782e5bc7046fc70844The Android Open Source Project } 128049d6fea481044fcc000e7782e5bc7046fc70844The Android Open Source Project } 129049d6fea481044fcc000e7782e5bc7046fc70844The Android Open Source Project 130049d6fea481044fcc000e7782e5bc7046fc70844The Android Open Source Project y1 = y3 = y1 - FT_MulDiv( y2 - y1, y2 - y1, y1 - 2*y2 + y3 ); 131049d6fea481044fcc000e7782e5bc7046fc70844The Android Open Source Project 132049d6fea481044fcc000e7782e5bc7046fc70844The Android Open Source Project Suite: 133049d6fea481044fcc000e7782e5bc7046fc70844The Android Open Source Project if ( y1 < *min ) *min = y1; 134049d6fea481044fcc000e7782e5bc7046fc70844The Android Open Source Project if ( y3 > *max ) *max = y3; 135049d6fea481044fcc000e7782e5bc7046fc70844The Android Open Source Project } 136049d6fea481044fcc000e7782e5bc7046fc70844The Android Open Source Project 137049d6fea481044fcc000e7782e5bc7046fc70844The Android Open Source Project 138049d6fea481044fcc000e7782e5bc7046fc70844The Android Open Source Project /*************************************************************************/ 139049d6fea481044fcc000e7782e5bc7046fc70844The Android Open Source Project /* */ 140049d6fea481044fcc000e7782e5bc7046fc70844The Android Open Source Project /* <Function> */ 141049d6fea481044fcc000e7782e5bc7046fc70844The Android Open Source Project /* BBox_Conic_To */ 142049d6fea481044fcc000e7782e5bc7046fc70844The Android Open Source Project /* */ 143049d6fea481044fcc000e7782e5bc7046fc70844The Android Open Source Project /* <Description> */ 144049d6fea481044fcc000e7782e5bc7046fc70844The Android Open Source Project /* This function is used as a `conic_to' emitter during */ 145295ffce55e0198e7a9f7d46b33f5c2b4147bf821David 'Digit' Turner /* FT_Outline_Decompose(). It checks a conic Bezier curve with the */ 146049d6fea481044fcc000e7782e5bc7046fc70844The Android Open Source Project /* current bounding box, and computes its extrema if necessary to */ 147049d6fea481044fcc000e7782e5bc7046fc70844The Android Open Source Project /* update it. */ 148049d6fea481044fcc000e7782e5bc7046fc70844The Android Open Source Project /* */ 149049d6fea481044fcc000e7782e5bc7046fc70844The Android Open Source Project /* <Input> */ 150049d6fea481044fcc000e7782e5bc7046fc70844The Android Open Source Project /* control :: A pointer to a control point. */ 151049d6fea481044fcc000e7782e5bc7046fc70844The Android Open Source Project /* */ 152049d6fea481044fcc000e7782e5bc7046fc70844The Android Open Source Project /* to :: A pointer to the destination vector. */ 153049d6fea481044fcc000e7782e5bc7046fc70844The Android Open Source Project /* */ 154049d6fea481044fcc000e7782e5bc7046fc70844The Android Open Source Project /* <InOut> */ 155049d6fea481044fcc000e7782e5bc7046fc70844The Android Open Source Project /* user :: The address of the current walk context. */ 156049d6fea481044fcc000e7782e5bc7046fc70844The Android Open Source Project /* */ 157049d6fea481044fcc000e7782e5bc7046fc70844The Android Open Source Project /* <Return> */ 158049d6fea481044fcc000e7782e5bc7046fc70844The Android Open Source Project /* Always 0. Needed for the interface only. */ 159049d6fea481044fcc000e7782e5bc7046fc70844The Android Open Source Project /* */ 160049d6fea481044fcc000e7782e5bc7046fc70844The Android Open Source Project /* <Note> */ 161049d6fea481044fcc000e7782e5bc7046fc70844The Android Open Source Project /* In the case of a non-monotonous arc, we compute directly the */ 162049d6fea481044fcc000e7782e5bc7046fc70844The Android Open Source Project /* extremum coordinates, as it is sufficiently fast. */ 163049d6fea481044fcc000e7782e5bc7046fc70844The Android Open Source Project /* */ 164049d6fea481044fcc000e7782e5bc7046fc70844The Android Open Source Project static int 165049d6fea481044fcc000e7782e5bc7046fc70844The Android Open Source Project BBox_Conic_To( FT_Vector* control, 166049d6fea481044fcc000e7782e5bc7046fc70844The Android Open Source Project FT_Vector* to, 167049d6fea481044fcc000e7782e5bc7046fc70844The Android Open Source Project TBBox_Rec* user ) 168049d6fea481044fcc000e7782e5bc7046fc70844The Android Open Source Project { 169049d6fea481044fcc000e7782e5bc7046fc70844The Android Open Source Project /* we don't need to check `to' since it is always an `on' point, thus */ 170049d6fea481044fcc000e7782e5bc7046fc70844The Android Open Source Project /* within the bbox */ 171049d6fea481044fcc000e7782e5bc7046fc70844The Android Open Source Project 172049d6fea481044fcc000e7782e5bc7046fc70844The Android Open Source Project if ( CHECK_X( control, user->bbox ) ) 173049d6fea481044fcc000e7782e5bc7046fc70844The Android Open Source Project BBox_Conic_Check( user->last.x, 174049d6fea481044fcc000e7782e5bc7046fc70844The Android Open Source Project control->x, 175049d6fea481044fcc000e7782e5bc7046fc70844The Android Open Source Project to->x, 176049d6fea481044fcc000e7782e5bc7046fc70844The Android Open Source Project &user->bbox.xMin, 177049d6fea481044fcc000e7782e5bc7046fc70844The Android Open Source Project &user->bbox.xMax ); 178049d6fea481044fcc000e7782e5bc7046fc70844The Android Open Source Project 179049d6fea481044fcc000e7782e5bc7046fc70844The Android Open Source Project if ( CHECK_Y( control, user->bbox ) ) 180049d6fea481044fcc000e7782e5bc7046fc70844The Android Open Source Project BBox_Conic_Check( user->last.y, 181049d6fea481044fcc000e7782e5bc7046fc70844The Android Open Source Project control->y, 182049d6fea481044fcc000e7782e5bc7046fc70844The Android Open Source Project to->y, 183049d6fea481044fcc000e7782e5bc7046fc70844The Android Open Source Project &user->bbox.yMin, 184049d6fea481044fcc000e7782e5bc7046fc70844The Android Open Source Project &user->bbox.yMax ); 185049d6fea481044fcc000e7782e5bc7046fc70844The Android Open Source Project 186049d6fea481044fcc000e7782e5bc7046fc70844The Android Open Source Project user->last = *to; 187049d6fea481044fcc000e7782e5bc7046fc70844The Android Open Source Project 188049d6fea481044fcc000e7782e5bc7046fc70844The Android Open Source Project return 0; 189049d6fea481044fcc000e7782e5bc7046fc70844The Android Open Source Project } 190049d6fea481044fcc000e7782e5bc7046fc70844The Android Open Source Project 191049d6fea481044fcc000e7782e5bc7046fc70844The Android Open Source Project 192049d6fea481044fcc000e7782e5bc7046fc70844The Android Open Source Project /*************************************************************************/ 193049d6fea481044fcc000e7782e5bc7046fc70844The Android Open Source Project /* */ 194049d6fea481044fcc000e7782e5bc7046fc70844The Android Open Source Project /* <Function> */ 195049d6fea481044fcc000e7782e5bc7046fc70844The Android Open Source Project /* BBox_Cubic_Check */ 196049d6fea481044fcc000e7782e5bc7046fc70844The Android Open Source Project /* */ 197049d6fea481044fcc000e7782e5bc7046fc70844The Android Open Source Project /* <Description> */ 198049d6fea481044fcc000e7782e5bc7046fc70844The Android Open Source Project /* Finds the extrema of a 1-dimensional cubic Bezier curve and */ 199049d6fea481044fcc000e7782e5bc7046fc70844The Android Open Source Project /* updates a bounding range. This version uses splitting because we */ 200049d6fea481044fcc000e7782e5bc7046fc70844The Android Open Source Project /* don't want to use square roots and extra accuracy. */ 201049d6fea481044fcc000e7782e5bc7046fc70844The Android Open Source Project /* */ 202049d6fea481044fcc000e7782e5bc7046fc70844The Android Open Source Project /* <Input> */ 203049d6fea481044fcc000e7782e5bc7046fc70844The Android Open Source Project /* p1 :: The start coordinate. */ 204049d6fea481044fcc000e7782e5bc7046fc70844The Android Open Source Project /* */ 205049d6fea481044fcc000e7782e5bc7046fc70844The Android Open Source Project /* p2 :: The coordinate of the first control point. */ 206049d6fea481044fcc000e7782e5bc7046fc70844The Android Open Source Project /* */ 207049d6fea481044fcc000e7782e5bc7046fc70844The Android Open Source Project /* p3 :: The coordinate of the second control point. */ 208049d6fea481044fcc000e7782e5bc7046fc70844The Android Open Source Project /* */ 209049d6fea481044fcc000e7782e5bc7046fc70844The Android Open Source Project /* p4 :: The end coordinate. */ 210049d6fea481044fcc000e7782e5bc7046fc70844The Android Open Source Project /* */ 211049d6fea481044fcc000e7782e5bc7046fc70844The Android Open Source Project /* <InOut> */ 212049d6fea481044fcc000e7782e5bc7046fc70844The Android Open Source Project /* min :: The address of the current minimum. */ 213049d6fea481044fcc000e7782e5bc7046fc70844The Android Open Source Project /* */ 214049d6fea481044fcc000e7782e5bc7046fc70844The Android Open Source Project /* max :: The address of the current maximum. */ 215049d6fea481044fcc000e7782e5bc7046fc70844The Android Open Source Project /* */ 216049d6fea481044fcc000e7782e5bc7046fc70844The Android Open Source Project 217049d6fea481044fcc000e7782e5bc7046fc70844The Android Open Source Project#if 0 218049d6fea481044fcc000e7782e5bc7046fc70844The Android Open Source Project 219049d6fea481044fcc000e7782e5bc7046fc70844The Android Open Source Project static void 220049d6fea481044fcc000e7782e5bc7046fc70844The Android Open Source Project BBox_Cubic_Check( FT_Pos p1, 221049d6fea481044fcc000e7782e5bc7046fc70844The Android Open Source Project FT_Pos p2, 222049d6fea481044fcc000e7782e5bc7046fc70844The Android Open Source Project FT_Pos p3, 223049d6fea481044fcc000e7782e5bc7046fc70844The Android Open Source Project FT_Pos p4, 224049d6fea481044fcc000e7782e5bc7046fc70844The Android Open Source Project FT_Pos* min, 225049d6fea481044fcc000e7782e5bc7046fc70844The Android Open Source Project FT_Pos* max ) 226049d6fea481044fcc000e7782e5bc7046fc70844The Android Open Source Project { 227a2b9955b49034a51dfbc8bf9f4e9d312149cecacXianzhu Wang FT_Pos q1, q2, q3, q4; 228049d6fea481044fcc000e7782e5bc7046fc70844The Android Open Source Project 229049d6fea481044fcc000e7782e5bc7046fc70844The Android Open Source Project 230a2b9955b49034a51dfbc8bf9f4e9d312149cecacXianzhu Wang q1 = p1; 231a2b9955b49034a51dfbc8bf9f4e9d312149cecacXianzhu Wang q2 = p2; 232a2b9955b49034a51dfbc8bf9f4e9d312149cecacXianzhu Wang q3 = p3; 233a2b9955b49034a51dfbc8bf9f4e9d312149cecacXianzhu Wang q4 = p4; 234049d6fea481044fcc000e7782e5bc7046fc70844The Android Open Source Project 235a2b9955b49034a51dfbc8bf9f4e9d312149cecacXianzhu Wang /* for a conic segment to possibly reach new maximum */ 236a2b9955b49034a51dfbc8bf9f4e9d312149cecacXianzhu Wang /* one of its off-points must be above the current value */ 237a2b9955b49034a51dfbc8bf9f4e9d312149cecacXianzhu Wang while ( q2 > *max || q3 > *max ) 238049d6fea481044fcc000e7782e5bc7046fc70844The Android Open Source Project { 239a2b9955b49034a51dfbc8bf9f4e9d312149cecacXianzhu Wang /* determine which half contains the maximum and split */ 240a2b9955b49034a51dfbc8bf9f4e9d312149cecacXianzhu Wang if ( q1 + q2 > q3 + q4 ) /* first half */ 241049d6fea481044fcc000e7782e5bc7046fc70844The Android Open Source Project { 242a2b9955b49034a51dfbc8bf9f4e9d312149cecacXianzhu Wang q4 = q4 + q3; 243a2b9955b49034a51dfbc8bf9f4e9d312149cecacXianzhu Wang q3 = q3 + q2; 244a2b9955b49034a51dfbc8bf9f4e9d312149cecacXianzhu Wang q2 = q2 + q1; 245a2b9955b49034a51dfbc8bf9f4e9d312149cecacXianzhu Wang q4 = q4 + q3; 246a2b9955b49034a51dfbc8bf9f4e9d312149cecacXianzhu Wang q3 = q3 + q2; 247a2b9955b49034a51dfbc8bf9f4e9d312149cecacXianzhu Wang q4 = ( q4 + q3 ) / 8; 248a2b9955b49034a51dfbc8bf9f4e9d312149cecacXianzhu Wang q3 = q3 / 4; 249a2b9955b49034a51dfbc8bf9f4e9d312149cecacXianzhu Wang q2 = q2 / 2; 250049d6fea481044fcc000e7782e5bc7046fc70844The Android Open Source Project } 251a2b9955b49034a51dfbc8bf9f4e9d312149cecacXianzhu Wang else /* second half */ 252049d6fea481044fcc000e7782e5bc7046fc70844The Android Open Source Project { 253a2b9955b49034a51dfbc8bf9f4e9d312149cecacXianzhu Wang q1 = q1 + q2; 254a2b9955b49034a51dfbc8bf9f4e9d312149cecacXianzhu Wang q2 = q2 + q3; 255a2b9955b49034a51dfbc8bf9f4e9d312149cecacXianzhu Wang q3 = q3 + q4; 256a2b9955b49034a51dfbc8bf9f4e9d312149cecacXianzhu Wang q1 = q1 + q2; 257a2b9955b49034a51dfbc8bf9f4e9d312149cecacXianzhu Wang q2 = q2 + q3; 258a2b9955b49034a51dfbc8bf9f4e9d312149cecacXianzhu Wang q1 = ( q1 + q2 ) / 8; 259a2b9955b49034a51dfbc8bf9f4e9d312149cecacXianzhu Wang q2 = q2 / 4; 260a2b9955b49034a51dfbc8bf9f4e9d312149cecacXianzhu Wang q3 = q3 / 2; 261049d6fea481044fcc000e7782e5bc7046fc70844The Android Open Source Project } 262a2b9955b49034a51dfbc8bf9f4e9d312149cecacXianzhu Wang 263a2b9955b49034a51dfbc8bf9f4e9d312149cecacXianzhu Wang /* check if either end reached the maximum */ 264a2b9955b49034a51dfbc8bf9f4e9d312149cecacXianzhu Wang if ( q1 == q2 && q1 >= q3 ) 265049d6fea481044fcc000e7782e5bc7046fc70844The Android Open Source Project { 266a2b9955b49034a51dfbc8bf9f4e9d312149cecacXianzhu Wang *max = q1; 267a2b9955b49034a51dfbc8bf9f4e9d312149cecacXianzhu Wang break; 268049d6fea481044fcc000e7782e5bc7046fc70844The Android Open Source Project } 269a2b9955b49034a51dfbc8bf9f4e9d312149cecacXianzhu Wang if ( q3 == q4 && q2 <= q4 ) 270a2b9955b49034a51dfbc8bf9f4e9d312149cecacXianzhu Wang { 271a2b9955b49034a51dfbc8bf9f4e9d312149cecacXianzhu Wang *max = q4; 272a2b9955b49034a51dfbc8bf9f4e9d312149cecacXianzhu Wang break; 273a2b9955b49034a51dfbc8bf9f4e9d312149cecacXianzhu Wang } 274a2b9955b49034a51dfbc8bf9f4e9d312149cecacXianzhu Wang } 275049d6fea481044fcc000e7782e5bc7046fc70844The Android Open Source Project 276a2b9955b49034a51dfbc8bf9f4e9d312149cecacXianzhu Wang q1 = p1; 277a2b9955b49034a51dfbc8bf9f4e9d312149cecacXianzhu Wang q2 = p2; 278a2b9955b49034a51dfbc8bf9f4e9d312149cecacXianzhu Wang q3 = p3; 279a2b9955b49034a51dfbc8bf9f4e9d312149cecacXianzhu Wang q4 = p4; 280049d6fea481044fcc000e7782e5bc7046fc70844The Android Open Source Project 281a2b9955b49034a51dfbc8bf9f4e9d312149cecacXianzhu Wang /* for a conic segment to possibly reach new minimum */ 282a2b9955b49034a51dfbc8bf9f4e9d312149cecacXianzhu Wang /* one of its off-points must be below the current value */ 283a2b9955b49034a51dfbc8bf9f4e9d312149cecacXianzhu Wang while ( q2 < *min || q3 < *min ) 284a2b9955b49034a51dfbc8bf9f4e9d312149cecacXianzhu Wang { 285a2b9955b49034a51dfbc8bf9f4e9d312149cecacXianzhu Wang /* determine which half contains the minimum and split */ 286a2b9955b49034a51dfbc8bf9f4e9d312149cecacXianzhu Wang if ( q1 + q2 < q3 + q4 ) /* first half */ 287a2b9955b49034a51dfbc8bf9f4e9d312149cecacXianzhu Wang { 288a2b9955b49034a51dfbc8bf9f4e9d312149cecacXianzhu Wang q4 = q4 + q3; 289a2b9955b49034a51dfbc8bf9f4e9d312149cecacXianzhu Wang q3 = q3 + q2; 290a2b9955b49034a51dfbc8bf9f4e9d312149cecacXianzhu Wang q2 = q2 + q1; 291a2b9955b49034a51dfbc8bf9f4e9d312149cecacXianzhu Wang q4 = q4 + q3; 292a2b9955b49034a51dfbc8bf9f4e9d312149cecacXianzhu Wang q3 = q3 + q2; 293a2b9955b49034a51dfbc8bf9f4e9d312149cecacXianzhu Wang q4 = ( q4 + q3 ) / 8; 294a2b9955b49034a51dfbc8bf9f4e9d312149cecacXianzhu Wang q3 = q3 / 4; 295a2b9955b49034a51dfbc8bf9f4e9d312149cecacXianzhu Wang q2 = q2 / 2; 296a2b9955b49034a51dfbc8bf9f4e9d312149cecacXianzhu Wang } 297a2b9955b49034a51dfbc8bf9f4e9d312149cecacXianzhu Wang else /* second half */ 298a2b9955b49034a51dfbc8bf9f4e9d312149cecacXianzhu Wang { 299a2b9955b49034a51dfbc8bf9f4e9d312149cecacXianzhu Wang q1 = q1 + q2; 300a2b9955b49034a51dfbc8bf9f4e9d312149cecacXianzhu Wang q2 = q2 + q3; 301a2b9955b49034a51dfbc8bf9f4e9d312149cecacXianzhu Wang q3 = q3 + q4; 302a2b9955b49034a51dfbc8bf9f4e9d312149cecacXianzhu Wang q1 = q1 + q2; 303a2b9955b49034a51dfbc8bf9f4e9d312149cecacXianzhu Wang q2 = q2 + q3; 304a2b9955b49034a51dfbc8bf9f4e9d312149cecacXianzhu Wang q1 = ( q1 + q2 ) / 8; 305a2b9955b49034a51dfbc8bf9f4e9d312149cecacXianzhu Wang q2 = q2 / 4; 306a2b9955b49034a51dfbc8bf9f4e9d312149cecacXianzhu Wang q3 = q3 / 2; 307a2b9955b49034a51dfbc8bf9f4e9d312149cecacXianzhu Wang } 308049d6fea481044fcc000e7782e5bc7046fc70844The Android Open Source Project 309a2b9955b49034a51dfbc8bf9f4e9d312149cecacXianzhu Wang /* check if either end reached the minimum */ 310a2b9955b49034a51dfbc8bf9f4e9d312149cecacXianzhu Wang if ( q1 == q2 && q1 <= q3 ) 311a2b9955b49034a51dfbc8bf9f4e9d312149cecacXianzhu Wang { 312a2b9955b49034a51dfbc8bf9f4e9d312149cecacXianzhu Wang *min = q1; 313a2b9955b49034a51dfbc8bf9f4e9d312149cecacXianzhu Wang break; 314a2b9955b49034a51dfbc8bf9f4e9d312149cecacXianzhu Wang } 315a2b9955b49034a51dfbc8bf9f4e9d312149cecacXianzhu Wang if ( q3 == q4 && q2 >= q4 ) 316a2b9955b49034a51dfbc8bf9f4e9d312149cecacXianzhu Wang { 317a2b9955b49034a51dfbc8bf9f4e9d312149cecacXianzhu Wang *min = q4; 318a2b9955b49034a51dfbc8bf9f4e9d312149cecacXianzhu Wang break; 319a2b9955b49034a51dfbc8bf9f4e9d312149cecacXianzhu Wang } 320a2b9955b49034a51dfbc8bf9f4e9d312149cecacXianzhu Wang } 321049d6fea481044fcc000e7782e5bc7046fc70844The Android Open Source Project } 322049d6fea481044fcc000e7782e5bc7046fc70844The Android Open Source Project 323049d6fea481044fcc000e7782e5bc7046fc70844The Android Open Source Project#else 324049d6fea481044fcc000e7782e5bc7046fc70844The Android Open Source Project 325049d6fea481044fcc000e7782e5bc7046fc70844The Android Open Source Project static void 326049d6fea481044fcc000e7782e5bc7046fc70844The Android Open Source Project test_cubic_extrema( FT_Pos y1, 327049d6fea481044fcc000e7782e5bc7046fc70844The Android Open Source Project FT_Pos y2, 328049d6fea481044fcc000e7782e5bc7046fc70844The Android Open Source Project FT_Pos y3, 329049d6fea481044fcc000e7782e5bc7046fc70844The Android Open Source Project FT_Pos y4, 330049d6fea481044fcc000e7782e5bc7046fc70844The Android Open Source Project FT_Fixed u, 331049d6fea481044fcc000e7782e5bc7046fc70844The Android Open Source Project FT_Pos* min, 332049d6fea481044fcc000e7782e5bc7046fc70844The Android Open Source Project FT_Pos* max ) 333049d6fea481044fcc000e7782e5bc7046fc70844The Android Open Source Project { 334049d6fea481044fcc000e7782e5bc7046fc70844The Android Open Source Project /* FT_Pos a = y4 - 3*y3 + 3*y2 - y1; */ 335049d6fea481044fcc000e7782e5bc7046fc70844The Android Open Source Project FT_Pos b = y3 - 2*y2 + y1; 336049d6fea481044fcc000e7782e5bc7046fc70844The Android Open Source Project FT_Pos c = y2 - y1; 337049d6fea481044fcc000e7782e5bc7046fc70844The Android Open Source Project FT_Pos d = y1; 338049d6fea481044fcc000e7782e5bc7046fc70844The Android Open Source Project FT_Pos y; 339049d6fea481044fcc000e7782e5bc7046fc70844The Android Open Source Project FT_Fixed uu; 340049d6fea481044fcc000e7782e5bc7046fc70844The Android Open Source Project 341049d6fea481044fcc000e7782e5bc7046fc70844The Android Open Source Project FT_UNUSED ( y4 ); 342049d6fea481044fcc000e7782e5bc7046fc70844The Android Open Source Project 343049d6fea481044fcc000e7782e5bc7046fc70844The Android Open Source Project 344049d6fea481044fcc000e7782e5bc7046fc70844The Android Open Source Project /* The polynomial is */ 345049d6fea481044fcc000e7782e5bc7046fc70844The Android Open Source Project /* */ 346049d6fea481044fcc000e7782e5bc7046fc70844The Android Open Source Project /* P(x) = a*x^3 + 3b*x^2 + 3c*x + d , */ 347049d6fea481044fcc000e7782e5bc7046fc70844The Android Open Source Project /* */ 348049d6fea481044fcc000e7782e5bc7046fc70844The Android Open Source Project /* dP/dx = 3a*x^2 + 6b*x + 3c . */ 349049d6fea481044fcc000e7782e5bc7046fc70844The Android Open Source Project /* */ 350049d6fea481044fcc000e7782e5bc7046fc70844The Android Open Source Project /* However, we also have */ 351049d6fea481044fcc000e7782e5bc7046fc70844The Android Open Source Project /* */ 352049d6fea481044fcc000e7782e5bc7046fc70844The Android Open Source Project /* dP/dx(u) = 0 , */ 353049d6fea481044fcc000e7782e5bc7046fc70844The Android Open Source Project /* */ 354049d6fea481044fcc000e7782e5bc7046fc70844The Android Open Source Project /* which implies by subtraction that */ 355049d6fea481044fcc000e7782e5bc7046fc70844The Android Open Source Project /* */ 356049d6fea481044fcc000e7782e5bc7046fc70844The Android Open Source Project /* P(u) = b*u^2 + 2c*u + d . */ 357049d6fea481044fcc000e7782e5bc7046fc70844The Android Open Source Project 358049d6fea481044fcc000e7782e5bc7046fc70844The Android Open Source Project if ( u > 0 && u < 0x10000L ) 359049d6fea481044fcc000e7782e5bc7046fc70844The Android Open Source Project { 360049d6fea481044fcc000e7782e5bc7046fc70844The Android Open Source Project uu = FT_MulFix( u, u ); 361049d6fea481044fcc000e7782e5bc7046fc70844The Android Open Source Project y = d + FT_MulFix( c, 2*u ) + FT_MulFix( b, uu ); 362049d6fea481044fcc000e7782e5bc7046fc70844The Android Open Source Project 363049d6fea481044fcc000e7782e5bc7046fc70844The Android Open Source Project if ( y < *min ) *min = y; 364049d6fea481044fcc000e7782e5bc7046fc70844The Android Open Source Project if ( y > *max ) *max = y; 365049d6fea481044fcc000e7782e5bc7046fc70844The Android Open Source Project } 366049d6fea481044fcc000e7782e5bc7046fc70844The Android Open Source Project } 367049d6fea481044fcc000e7782e5bc7046fc70844The Android Open Source Project 368049d6fea481044fcc000e7782e5bc7046fc70844The Android Open Source Project 369049d6fea481044fcc000e7782e5bc7046fc70844The Android Open Source Project static void 370049d6fea481044fcc000e7782e5bc7046fc70844The Android Open Source Project BBox_Cubic_Check( FT_Pos y1, 371049d6fea481044fcc000e7782e5bc7046fc70844The Android Open Source Project FT_Pos y2, 372049d6fea481044fcc000e7782e5bc7046fc70844The Android Open Source Project FT_Pos y3, 373049d6fea481044fcc000e7782e5bc7046fc70844The Android Open Source Project FT_Pos y4, 374049d6fea481044fcc000e7782e5bc7046fc70844The Android Open Source Project FT_Pos* min, 375049d6fea481044fcc000e7782e5bc7046fc70844The Android Open Source Project FT_Pos* max ) 376049d6fea481044fcc000e7782e5bc7046fc70844The Android Open Source Project { 377049d6fea481044fcc000e7782e5bc7046fc70844The Android Open Source Project /* always compare first and last points */ 378049d6fea481044fcc000e7782e5bc7046fc70844The Android Open Source Project if ( y1 < *min ) *min = y1; 379049d6fea481044fcc000e7782e5bc7046fc70844The Android Open Source Project else if ( y1 > *max ) *max = y1; 380049d6fea481044fcc000e7782e5bc7046fc70844The Android Open Source Project 381049d6fea481044fcc000e7782e5bc7046fc70844The Android Open Source Project if ( y4 < *min ) *min = y4; 382049d6fea481044fcc000e7782e5bc7046fc70844The Android Open Source Project else if ( y4 > *max ) *max = y4; 383049d6fea481044fcc000e7782e5bc7046fc70844The Android Open Source Project 384049d6fea481044fcc000e7782e5bc7046fc70844The Android Open Source Project /* now, try to see if there are split points here */ 385049d6fea481044fcc000e7782e5bc7046fc70844The Android Open Source Project if ( y1 <= y4 ) 386049d6fea481044fcc000e7782e5bc7046fc70844The Android Open Source Project { 387049d6fea481044fcc000e7782e5bc7046fc70844The Android Open Source Project /* flat or ascending arc test */ 388049d6fea481044fcc000e7782e5bc7046fc70844The Android Open Source Project if ( y1 <= y2 && y2 <= y4 && y1 <= y3 && y3 <= y4 ) 389049d6fea481044fcc000e7782e5bc7046fc70844The Android Open Source Project return; 390049d6fea481044fcc000e7782e5bc7046fc70844The Android Open Source Project } 391049d6fea481044fcc000e7782e5bc7046fc70844The Android Open Source Project else /* y1 > y4 */ 392049d6fea481044fcc000e7782e5bc7046fc70844The Android Open Source Project { 393049d6fea481044fcc000e7782e5bc7046fc70844The Android Open Source Project /* descending arc test */ 394049d6fea481044fcc000e7782e5bc7046fc70844The Android Open Source Project if ( y1 >= y2 && y2 >= y4 && y1 >= y3 && y3 >= y4 ) 395049d6fea481044fcc000e7782e5bc7046fc70844The Android Open Source Project return; 396049d6fea481044fcc000e7782e5bc7046fc70844The Android Open Source Project } 397049d6fea481044fcc000e7782e5bc7046fc70844The Android Open Source Project 398a2b9955b49034a51dfbc8bf9f4e9d312149cecacXianzhu Wang /* There are some split points. Find them. */ 399a2b9955b49034a51dfbc8bf9f4e9d312149cecacXianzhu Wang /* We already made sure that a, b, and c below cannot be all zero. */ 400049d6fea481044fcc000e7782e5bc7046fc70844The Android Open Source Project { 401049d6fea481044fcc000e7782e5bc7046fc70844The Android Open Source Project FT_Pos a = y4 - 3*y3 + 3*y2 - y1; 402049d6fea481044fcc000e7782e5bc7046fc70844The Android Open Source Project FT_Pos b = y3 - 2*y2 + y1; 403049d6fea481044fcc000e7782e5bc7046fc70844The Android Open Source Project FT_Pos c = y2 - y1; 404049d6fea481044fcc000e7782e5bc7046fc70844The Android Open Source Project FT_Pos d; 405049d6fea481044fcc000e7782e5bc7046fc70844The Android Open Source Project FT_Fixed t; 406a2b9955b49034a51dfbc8bf9f4e9d312149cecacXianzhu Wang FT_Int shift; 407049d6fea481044fcc000e7782e5bc7046fc70844The Android Open Source Project 408049d6fea481044fcc000e7782e5bc7046fc70844The Android Open Source Project 409049d6fea481044fcc000e7782e5bc7046fc70844The Android Open Source Project /* We need to solve `ax^2+2bx+c' here, without floating points! */ 410049d6fea481044fcc000e7782e5bc7046fc70844The Android Open Source Project /* The trick is to normalize to a different representation in order */ 411a2b9955b49034a51dfbc8bf9f4e9d312149cecacXianzhu Wang /* to use our 16.16 fixed-point routines. */ 412049d6fea481044fcc000e7782e5bc7046fc70844The Android Open Source Project /* */ 413049d6fea481044fcc000e7782e5bc7046fc70844The Android Open Source Project /* We compute FT_MulFix(b,b) and FT_MulFix(a,c) after normalization. */ 414049d6fea481044fcc000e7782e5bc7046fc70844The Android Open Source Project /* These values must fit into a single 16.16 value. */ 415049d6fea481044fcc000e7782e5bc7046fc70844The Android Open Source Project /* */ 416a2b9955b49034a51dfbc8bf9f4e9d312149cecacXianzhu Wang /* We normalize a, b, and c to `8.16' fixed-point values to ensure */ 417a2b9955b49034a51dfbc8bf9f4e9d312149cecacXianzhu Wang /* that their product is held in a `16.16' value including the sign. */ 418a2b9955b49034a51dfbc8bf9f4e9d312149cecacXianzhu Wang /* Necessarily, we need to shift `a', `b', and `c' so that the most */ 419a2b9955b49034a51dfbc8bf9f4e9d312149cecacXianzhu Wang /* significant bit of their absolute values is at position 22. */ 420a2b9955b49034a51dfbc8bf9f4e9d312149cecacXianzhu Wang /* */ 421a2b9955b49034a51dfbc8bf9f4e9d312149cecacXianzhu Wang /* This also means that we are using 23 bits of precision to compute */ 422a2b9955b49034a51dfbc8bf9f4e9d312149cecacXianzhu Wang /* the zeros, independently of the range of the original polynomial */ 423a2b9955b49034a51dfbc8bf9f4e9d312149cecacXianzhu Wang /* coefficients. */ 424a2b9955b49034a51dfbc8bf9f4e9d312149cecacXianzhu Wang /* */ 425a2b9955b49034a51dfbc8bf9f4e9d312149cecacXianzhu Wang /* This algorithm should ensure reasonably accurate values for the */ 426a2b9955b49034a51dfbc8bf9f4e9d312149cecacXianzhu Wang /* zeros. Note that they are only expressed with 16 bits when */ 427a2b9955b49034a51dfbc8bf9f4e9d312149cecacXianzhu Wang /* computing the extrema (the zeros need to be in 0..1 exclusive */ 428a2b9955b49034a51dfbc8bf9f4e9d312149cecacXianzhu Wang /* to be considered part of the arc). */ 429049d6fea481044fcc000e7782e5bc7046fc70844The Android Open Source Project 430a2b9955b49034a51dfbc8bf9f4e9d312149cecacXianzhu Wang shift = FT_MSB( FT_ABS( a ) | FT_ABS( b ) | FT_ABS( c ) ); 431049d6fea481044fcc000e7782e5bc7046fc70844The Android Open Source Project 432a2b9955b49034a51dfbc8bf9f4e9d312149cecacXianzhu Wang if ( shift > 22 ) 433a2b9955b49034a51dfbc8bf9f4e9d312149cecacXianzhu Wang { 434a2b9955b49034a51dfbc8bf9f4e9d312149cecacXianzhu Wang shift -= 22; 435049d6fea481044fcc000e7782e5bc7046fc70844The Android Open Source Project 436a2b9955b49034a51dfbc8bf9f4e9d312149cecacXianzhu Wang /* this loses some bits of precision, but we use 23 of them */ 437a2b9955b49034a51dfbc8bf9f4e9d312149cecacXianzhu Wang /* for the computation anyway */ 438a2b9955b49034a51dfbc8bf9f4e9d312149cecacXianzhu Wang a >>= shift; 439a2b9955b49034a51dfbc8bf9f4e9d312149cecacXianzhu Wang b >>= shift; 440a2b9955b49034a51dfbc8bf9f4e9d312149cecacXianzhu Wang c >>= shift; 441a2b9955b49034a51dfbc8bf9f4e9d312149cecacXianzhu Wang } 442a2b9955b49034a51dfbc8bf9f4e9d312149cecacXianzhu Wang else 443a2b9955b49034a51dfbc8bf9f4e9d312149cecacXianzhu Wang { 444a2b9955b49034a51dfbc8bf9f4e9d312149cecacXianzhu Wang shift = 22 - shift; 445049d6fea481044fcc000e7782e5bc7046fc70844The Android Open Source Project 446a2b9955b49034a51dfbc8bf9f4e9d312149cecacXianzhu Wang a <<= shift; 447a2b9955b49034a51dfbc8bf9f4e9d312149cecacXianzhu Wang b <<= shift; 448a2b9955b49034a51dfbc8bf9f4e9d312149cecacXianzhu Wang c <<= shift; 449049d6fea481044fcc000e7782e5bc7046fc70844The Android Open Source Project } 450049d6fea481044fcc000e7782e5bc7046fc70844The Android Open Source Project 451049d6fea481044fcc000e7782e5bc7046fc70844The Android Open Source Project /* handle a == 0 */ 452049d6fea481044fcc000e7782e5bc7046fc70844The Android Open Source Project if ( a == 0 ) 453049d6fea481044fcc000e7782e5bc7046fc70844The Android Open Source Project { 454049d6fea481044fcc000e7782e5bc7046fc70844The Android Open Source Project if ( b != 0 ) 455049d6fea481044fcc000e7782e5bc7046fc70844The Android Open Source Project { 456049d6fea481044fcc000e7782e5bc7046fc70844The Android Open Source Project t = - FT_DivFix( c, b ) / 2; 457049d6fea481044fcc000e7782e5bc7046fc70844The Android Open Source Project test_cubic_extrema( y1, y2, y3, y4, t, min, max ); 458049d6fea481044fcc000e7782e5bc7046fc70844The Android Open Source Project } 459049d6fea481044fcc000e7782e5bc7046fc70844The Android Open Source Project } 460049d6fea481044fcc000e7782e5bc7046fc70844The Android Open Source Project else 461049d6fea481044fcc000e7782e5bc7046fc70844The Android Open Source Project { 462049d6fea481044fcc000e7782e5bc7046fc70844The Android Open Source Project /* solve the equation now */ 463049d6fea481044fcc000e7782e5bc7046fc70844The Android Open Source Project d = FT_MulFix( b, b ) - FT_MulFix( a, c ); 464049d6fea481044fcc000e7782e5bc7046fc70844The Android Open Source Project if ( d < 0 ) 465049d6fea481044fcc000e7782e5bc7046fc70844The Android Open Source Project return; 466049d6fea481044fcc000e7782e5bc7046fc70844The Android Open Source Project 467049d6fea481044fcc000e7782e5bc7046fc70844The Android Open Source Project if ( d == 0 ) 468049d6fea481044fcc000e7782e5bc7046fc70844The Android Open Source Project { 469049d6fea481044fcc000e7782e5bc7046fc70844The Android Open Source Project /* there is a single split point at -b/a */ 470049d6fea481044fcc000e7782e5bc7046fc70844The Android Open Source Project t = - FT_DivFix( b, a ); 471049d6fea481044fcc000e7782e5bc7046fc70844The Android Open Source Project test_cubic_extrema( y1, y2, y3, y4, t, min, max ); 472049d6fea481044fcc000e7782e5bc7046fc70844The Android Open Source Project } 473049d6fea481044fcc000e7782e5bc7046fc70844The Android Open Source Project else 474049d6fea481044fcc000e7782e5bc7046fc70844The Android Open Source Project { 475049d6fea481044fcc000e7782e5bc7046fc70844The Android Open Source Project /* there are two solutions; we need to filter them */ 476049d6fea481044fcc000e7782e5bc7046fc70844The Android Open Source Project d = FT_SqrtFixed( (FT_Int32)d ); 477049d6fea481044fcc000e7782e5bc7046fc70844The Android Open Source Project t = - FT_DivFix( b - d, a ); 478049d6fea481044fcc000e7782e5bc7046fc70844The Android Open Source Project test_cubic_extrema( y1, y2, y3, y4, t, min, max ); 479049d6fea481044fcc000e7782e5bc7046fc70844The Android Open Source Project 480049d6fea481044fcc000e7782e5bc7046fc70844The Android Open Source Project t = - FT_DivFix( b + d, a ); 481049d6fea481044fcc000e7782e5bc7046fc70844The Android Open Source Project test_cubic_extrema( y1, y2, y3, y4, t, min, max ); 482049d6fea481044fcc000e7782e5bc7046fc70844The Android Open Source Project } 483049d6fea481044fcc000e7782e5bc7046fc70844The Android Open Source Project } 484049d6fea481044fcc000e7782e5bc7046fc70844The Android Open Source Project } 485049d6fea481044fcc000e7782e5bc7046fc70844The Android Open Source Project } 486049d6fea481044fcc000e7782e5bc7046fc70844The Android Open Source Project 487049d6fea481044fcc000e7782e5bc7046fc70844The Android Open Source Project#endif 488049d6fea481044fcc000e7782e5bc7046fc70844The Android Open Source Project 489049d6fea481044fcc000e7782e5bc7046fc70844The Android Open Source Project 490049d6fea481044fcc000e7782e5bc7046fc70844The Android Open Source Project /*************************************************************************/ 491049d6fea481044fcc000e7782e5bc7046fc70844The Android Open Source Project /* */ 492049d6fea481044fcc000e7782e5bc7046fc70844The Android Open Source Project /* <Function> */ 493049d6fea481044fcc000e7782e5bc7046fc70844The Android Open Source Project /* BBox_Cubic_To */ 494049d6fea481044fcc000e7782e5bc7046fc70844The Android Open Source Project /* */ 495049d6fea481044fcc000e7782e5bc7046fc70844The Android Open Source Project /* <Description> */ 496049d6fea481044fcc000e7782e5bc7046fc70844The Android Open Source Project /* This function is used as a `cubic_to' emitter during */ 497295ffce55e0198e7a9f7d46b33f5c2b4147bf821David 'Digit' Turner /* FT_Outline_Decompose(). It checks a cubic Bezier curve with the */ 498049d6fea481044fcc000e7782e5bc7046fc70844The Android Open Source Project /* current bounding box, and computes its extrema if necessary to */ 499049d6fea481044fcc000e7782e5bc7046fc70844The Android Open Source Project /* update it. */ 500049d6fea481044fcc000e7782e5bc7046fc70844The Android Open Source Project /* */ 501049d6fea481044fcc000e7782e5bc7046fc70844The Android Open Source Project /* <Input> */ 502049d6fea481044fcc000e7782e5bc7046fc70844The Android Open Source Project /* control1 :: A pointer to the first control point. */ 503049d6fea481044fcc000e7782e5bc7046fc70844The Android Open Source Project /* */ 504049d6fea481044fcc000e7782e5bc7046fc70844The Android Open Source Project /* control2 :: A pointer to the second control point. */ 505049d6fea481044fcc000e7782e5bc7046fc70844The Android Open Source Project /* */ 506049d6fea481044fcc000e7782e5bc7046fc70844The Android Open Source Project /* to :: A pointer to the destination vector. */ 507049d6fea481044fcc000e7782e5bc7046fc70844The Android Open Source Project /* */ 508049d6fea481044fcc000e7782e5bc7046fc70844The Android Open Source Project /* <InOut> */ 509049d6fea481044fcc000e7782e5bc7046fc70844The Android Open Source Project /* user :: The address of the current walk context. */ 510049d6fea481044fcc000e7782e5bc7046fc70844The Android Open Source Project /* */ 511049d6fea481044fcc000e7782e5bc7046fc70844The Android Open Source Project /* <Return> */ 512049d6fea481044fcc000e7782e5bc7046fc70844The Android Open Source Project /* Always 0. Needed for the interface only. */ 513049d6fea481044fcc000e7782e5bc7046fc70844The Android Open Source Project /* */ 514049d6fea481044fcc000e7782e5bc7046fc70844The Android Open Source Project /* <Note> */ 515049d6fea481044fcc000e7782e5bc7046fc70844The Android Open Source Project /* In the case of a non-monotonous arc, we don't compute directly */ 516049d6fea481044fcc000e7782e5bc7046fc70844The Android Open Source Project /* extremum coordinates, we subdivide instead. */ 517049d6fea481044fcc000e7782e5bc7046fc70844The Android Open Source Project /* */ 518049d6fea481044fcc000e7782e5bc7046fc70844The Android Open Source Project static int 519049d6fea481044fcc000e7782e5bc7046fc70844The Android Open Source Project BBox_Cubic_To( FT_Vector* control1, 520049d6fea481044fcc000e7782e5bc7046fc70844The Android Open Source Project FT_Vector* control2, 521049d6fea481044fcc000e7782e5bc7046fc70844The Android Open Source Project FT_Vector* to, 522049d6fea481044fcc000e7782e5bc7046fc70844The Android Open Source Project TBBox_Rec* user ) 523049d6fea481044fcc000e7782e5bc7046fc70844The Android Open Source Project { 524049d6fea481044fcc000e7782e5bc7046fc70844The Android Open Source Project /* we don't need to check `to' since it is always an `on' point, thus */ 525049d6fea481044fcc000e7782e5bc7046fc70844The Android Open Source Project /* within the bbox */ 526049d6fea481044fcc000e7782e5bc7046fc70844The Android Open Source Project 527049d6fea481044fcc000e7782e5bc7046fc70844The Android Open Source Project if ( CHECK_X( control1, user->bbox ) || 528049d6fea481044fcc000e7782e5bc7046fc70844The Android Open Source Project CHECK_X( control2, user->bbox ) ) 529049d6fea481044fcc000e7782e5bc7046fc70844The Android Open Source Project BBox_Cubic_Check( user->last.x, 530049d6fea481044fcc000e7782e5bc7046fc70844The Android Open Source Project control1->x, 531049d6fea481044fcc000e7782e5bc7046fc70844The Android Open Source Project control2->x, 532049d6fea481044fcc000e7782e5bc7046fc70844The Android Open Source Project to->x, 533049d6fea481044fcc000e7782e5bc7046fc70844The Android Open Source Project &user->bbox.xMin, 534049d6fea481044fcc000e7782e5bc7046fc70844The Android Open Source Project &user->bbox.xMax ); 535049d6fea481044fcc000e7782e5bc7046fc70844The Android Open Source Project 536049d6fea481044fcc000e7782e5bc7046fc70844The Android Open Source Project if ( CHECK_Y( control1, user->bbox ) || 537049d6fea481044fcc000e7782e5bc7046fc70844The Android Open Source Project CHECK_Y( control2, user->bbox ) ) 538049d6fea481044fcc000e7782e5bc7046fc70844The Android Open Source Project BBox_Cubic_Check( user->last.y, 539049d6fea481044fcc000e7782e5bc7046fc70844The Android Open Source Project control1->y, 540049d6fea481044fcc000e7782e5bc7046fc70844The Android Open Source Project control2->y, 541049d6fea481044fcc000e7782e5bc7046fc70844The Android Open Source Project to->y, 542049d6fea481044fcc000e7782e5bc7046fc70844The Android Open Source Project &user->bbox.yMin, 543049d6fea481044fcc000e7782e5bc7046fc70844The Android Open Source Project &user->bbox.yMax ); 544049d6fea481044fcc000e7782e5bc7046fc70844The Android Open Source Project 545049d6fea481044fcc000e7782e5bc7046fc70844The Android Open Source Project user->last = *to; 546049d6fea481044fcc000e7782e5bc7046fc70844The Android Open Source Project 547049d6fea481044fcc000e7782e5bc7046fc70844The Android Open Source Project return 0; 548049d6fea481044fcc000e7782e5bc7046fc70844The Android Open Source Project } 549049d6fea481044fcc000e7782e5bc7046fc70844The Android Open Source Project 550295ffce55e0198e7a9f7d46b33f5c2b4147bf821David 'Digit' TurnerFT_DEFINE_OUTLINE_FUNCS(bbox_interface, 551aacb8e1368a883fcbc9fe64fd0e460cef9c9b20cNick Kralevich (FT_Outline_MoveTo_Func) BBox_Move_To, 552aacb8e1368a883fcbc9fe64fd0e460cef9c9b20cNick Kralevich (FT_Outline_LineTo_Func) BBox_Move_To, 553aacb8e1368a883fcbc9fe64fd0e460cef9c9b20cNick Kralevich (FT_Outline_ConicTo_Func)BBox_Conic_To, 554aacb8e1368a883fcbc9fe64fd0e460cef9c9b20cNick Kralevich (FT_Outline_CubicTo_Func)BBox_Cubic_To, 555aacb8e1368a883fcbc9fe64fd0e460cef9c9b20cNick Kralevich 0, 0 556295ffce55e0198e7a9f7d46b33f5c2b4147bf821David 'Digit' Turner ) 557049d6fea481044fcc000e7782e5bc7046fc70844The Android Open Source Project 558049d6fea481044fcc000e7782e5bc7046fc70844The Android Open Source Project /* documentation is in ftbbox.h */ 559049d6fea481044fcc000e7782e5bc7046fc70844The Android Open Source Project 560049d6fea481044fcc000e7782e5bc7046fc70844The Android Open Source Project FT_EXPORT_DEF( FT_Error ) 561049d6fea481044fcc000e7782e5bc7046fc70844The Android Open Source Project FT_Outline_Get_BBox( FT_Outline* outline, 562049d6fea481044fcc000e7782e5bc7046fc70844The Android Open Source Project FT_BBox *abbox ) 563049d6fea481044fcc000e7782e5bc7046fc70844The Android Open Source Project { 564049d6fea481044fcc000e7782e5bc7046fc70844The Android Open Source Project FT_BBox cbox; 565049d6fea481044fcc000e7782e5bc7046fc70844The Android Open Source Project FT_BBox bbox; 566049d6fea481044fcc000e7782e5bc7046fc70844The Android Open Source Project FT_Vector* vec; 567049d6fea481044fcc000e7782e5bc7046fc70844The Android Open Source Project FT_UShort n; 568049d6fea481044fcc000e7782e5bc7046fc70844The Android Open Source Project 569049d6fea481044fcc000e7782e5bc7046fc70844The Android Open Source Project 570049d6fea481044fcc000e7782e5bc7046fc70844The Android Open Source Project if ( !abbox ) 571a2b9955b49034a51dfbc8bf9f4e9d312149cecacXianzhu Wang return FT_THROW( Invalid_Argument ); 572049d6fea481044fcc000e7782e5bc7046fc70844The Android Open Source Project 573049d6fea481044fcc000e7782e5bc7046fc70844The Android Open Source Project if ( !outline ) 574a2b9955b49034a51dfbc8bf9f4e9d312149cecacXianzhu Wang return FT_THROW( Invalid_Outline ); 575049d6fea481044fcc000e7782e5bc7046fc70844The Android Open Source Project 576049d6fea481044fcc000e7782e5bc7046fc70844The Android Open Source Project /* if outline is empty, return (0,0,0,0) */ 577049d6fea481044fcc000e7782e5bc7046fc70844The Android Open Source Project if ( outline->n_points == 0 || outline->n_contours <= 0 ) 578049d6fea481044fcc000e7782e5bc7046fc70844The Android Open Source Project { 579049d6fea481044fcc000e7782e5bc7046fc70844The Android Open Source Project abbox->xMin = abbox->xMax = 0; 580049d6fea481044fcc000e7782e5bc7046fc70844The Android Open Source Project abbox->yMin = abbox->yMax = 0; 581049d6fea481044fcc000e7782e5bc7046fc70844The Android Open Source Project return 0; 582049d6fea481044fcc000e7782e5bc7046fc70844The Android Open Source Project } 583049d6fea481044fcc000e7782e5bc7046fc70844The Android Open Source Project 584049d6fea481044fcc000e7782e5bc7046fc70844The Android Open Source Project /* We compute the control box as well as the bounding box of */ 585049d6fea481044fcc000e7782e5bc7046fc70844The Android Open Source Project /* all `on' points in the outline. Then, if the two boxes */ 586049d6fea481044fcc000e7782e5bc7046fc70844The Android Open Source Project /* coincide, we exit immediately. */ 587049d6fea481044fcc000e7782e5bc7046fc70844The Android Open Source Project 588049d6fea481044fcc000e7782e5bc7046fc70844The Android Open Source Project vec = outline->points; 589049d6fea481044fcc000e7782e5bc7046fc70844The Android Open Source Project bbox.xMin = bbox.xMax = cbox.xMin = cbox.xMax = vec->x; 590049d6fea481044fcc000e7782e5bc7046fc70844The Android Open Source Project bbox.yMin = bbox.yMax = cbox.yMin = cbox.yMax = vec->y; 591049d6fea481044fcc000e7782e5bc7046fc70844The Android Open Source Project vec++; 592049d6fea481044fcc000e7782e5bc7046fc70844The Android Open Source Project 593049d6fea481044fcc000e7782e5bc7046fc70844The Android Open Source Project for ( n = 1; n < outline->n_points; n++ ) 594049d6fea481044fcc000e7782e5bc7046fc70844The Android Open Source Project { 595049d6fea481044fcc000e7782e5bc7046fc70844The Android Open Source Project FT_Pos x = vec->x; 596049d6fea481044fcc000e7782e5bc7046fc70844The Android Open Source Project FT_Pos y = vec->y; 597049d6fea481044fcc000e7782e5bc7046fc70844The Android Open Source Project 598049d6fea481044fcc000e7782e5bc7046fc70844The Android Open Source Project 599049d6fea481044fcc000e7782e5bc7046fc70844The Android Open Source Project /* update control box */ 600049d6fea481044fcc000e7782e5bc7046fc70844The Android Open Source Project if ( x < cbox.xMin ) cbox.xMin = x; 601049d6fea481044fcc000e7782e5bc7046fc70844The Android Open Source Project if ( x > cbox.xMax ) cbox.xMax = x; 602049d6fea481044fcc000e7782e5bc7046fc70844The Android Open Source Project 603049d6fea481044fcc000e7782e5bc7046fc70844The Android Open Source Project if ( y < cbox.yMin ) cbox.yMin = y; 604049d6fea481044fcc000e7782e5bc7046fc70844The Android Open Source Project if ( y > cbox.yMax ) cbox.yMax = y; 605049d6fea481044fcc000e7782e5bc7046fc70844The Android Open Source Project 606049d6fea481044fcc000e7782e5bc7046fc70844The Android Open Source Project if ( FT_CURVE_TAG( outline->tags[n] ) == FT_CURVE_TAG_ON ) 607049d6fea481044fcc000e7782e5bc7046fc70844The Android Open Source Project { 608049d6fea481044fcc000e7782e5bc7046fc70844The Android Open Source Project /* update bbox for `on' points only */ 609049d6fea481044fcc000e7782e5bc7046fc70844The Android Open Source Project if ( x < bbox.xMin ) bbox.xMin = x; 610049d6fea481044fcc000e7782e5bc7046fc70844The Android Open Source Project if ( x > bbox.xMax ) bbox.xMax = x; 611049d6fea481044fcc000e7782e5bc7046fc70844The Android Open Source Project 612049d6fea481044fcc000e7782e5bc7046fc70844The Android Open Source Project if ( y < bbox.yMin ) bbox.yMin = y; 613049d6fea481044fcc000e7782e5bc7046fc70844The Android Open Source Project if ( y > bbox.yMax ) bbox.yMax = y; 614049d6fea481044fcc000e7782e5bc7046fc70844The Android Open Source Project } 615049d6fea481044fcc000e7782e5bc7046fc70844The Android Open Source Project 616049d6fea481044fcc000e7782e5bc7046fc70844The Android Open Source Project vec++; 617049d6fea481044fcc000e7782e5bc7046fc70844The Android Open Source Project } 618049d6fea481044fcc000e7782e5bc7046fc70844The Android Open Source Project 619049d6fea481044fcc000e7782e5bc7046fc70844The Android Open Source Project /* test two boxes for equality */ 620049d6fea481044fcc000e7782e5bc7046fc70844The Android Open Source Project if ( cbox.xMin < bbox.xMin || cbox.xMax > bbox.xMax || 621049d6fea481044fcc000e7782e5bc7046fc70844The Android Open Source Project cbox.yMin < bbox.yMin || cbox.yMax > bbox.yMax ) 622049d6fea481044fcc000e7782e5bc7046fc70844The Android Open Source Project { 623049d6fea481044fcc000e7782e5bc7046fc70844The Android Open Source Project /* the two boxes are different, now walk over the outline to */ 624049d6fea481044fcc000e7782e5bc7046fc70844The Android Open Source Project /* get the Bezier arc extrema. */ 625049d6fea481044fcc000e7782e5bc7046fc70844The Android Open Source Project 626049d6fea481044fcc000e7782e5bc7046fc70844The Android Open Source Project FT_Error error; 627049d6fea481044fcc000e7782e5bc7046fc70844The Android Open Source Project TBBox_Rec user; 628049d6fea481044fcc000e7782e5bc7046fc70844The Android Open Source Project 629295ffce55e0198e7a9f7d46b33f5c2b4147bf821David 'Digit' Turner#ifdef FT_CONFIG_OPTION_PIC 630295ffce55e0198e7a9f7d46b33f5c2b4147bf821David 'Digit' Turner FT_Outline_Funcs bbox_interface; 631295ffce55e0198e7a9f7d46b33f5c2b4147bf821David 'Digit' Turner Init_Class_bbox_interface(&bbox_interface); 632295ffce55e0198e7a9f7d46b33f5c2b4147bf821David 'Digit' Turner#endif 633049d6fea481044fcc000e7782e5bc7046fc70844The Android Open Source Project 634049d6fea481044fcc000e7782e5bc7046fc70844The Android Open Source Project user.bbox = bbox; 635049d6fea481044fcc000e7782e5bc7046fc70844The Android Open Source Project 636049d6fea481044fcc000e7782e5bc7046fc70844The Android Open Source Project error = FT_Outline_Decompose( outline, &bbox_interface, &user ); 637049d6fea481044fcc000e7782e5bc7046fc70844The Android Open Source Project if ( error ) 638049d6fea481044fcc000e7782e5bc7046fc70844The Android Open Source Project return error; 639049d6fea481044fcc000e7782e5bc7046fc70844The Android Open Source Project 640049d6fea481044fcc000e7782e5bc7046fc70844The Android Open Source Project *abbox = user.bbox; 641049d6fea481044fcc000e7782e5bc7046fc70844The Android Open Source Project } 642049d6fea481044fcc000e7782e5bc7046fc70844The Android Open Source Project else 643049d6fea481044fcc000e7782e5bc7046fc70844The Android Open Source Project *abbox = bbox; 644049d6fea481044fcc000e7782e5bc7046fc70844The Android Open Source Project 645049d6fea481044fcc000e7782e5bc7046fc70844The Android Open Source Project return FT_Err_Ok; 646049d6fea481044fcc000e7782e5bc7046fc70844The Android Open Source Project } 647049d6fea481044fcc000e7782e5bc7046fc70844The Android Open Source Project 648049d6fea481044fcc000e7782e5bc7046fc70844The Android Open Source Project 649049d6fea481044fcc000e7782e5bc7046fc70844The Android Open Source Project/* END */ 650