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/* */ 7ec62c527eb34ee4481a0153ceb42dfd35d7e1d26Makoto Onuki/* Copyright 1996-2015 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> 28727dee178a392d20eb050d0c446f2fcc29058fa1Victoria Lease#include FT_INTERNAL_DEBUG_H 29727dee178a392d20eb050d0c446f2fcc29058fa1Victoria Lease 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 45ec62c527eb34ee4481a0153ceb42dfd35d7e1d26Makoto Onuki#define FT_UPDATE_BBOX( p, bbox ) \ 46ec62c527eb34ee4481a0153ceb42dfd35d7e1d26Makoto Onuki FT_BEGIN_STMNT \ 47ec62c527eb34ee4481a0153ceb42dfd35d7e1d26Makoto Onuki if ( p->x < bbox.xMin ) \ 48ec62c527eb34ee4481a0153ceb42dfd35d7e1d26Makoto Onuki bbox.xMin = p->x; \ 49ec62c527eb34ee4481a0153ceb42dfd35d7e1d26Makoto Onuki if ( p->x > bbox.xMax ) \ 50ec62c527eb34ee4481a0153ceb42dfd35d7e1d26Makoto Onuki bbox.xMax = p->x; \ 51ec62c527eb34ee4481a0153ceb42dfd35d7e1d26Makoto Onuki if ( p->y < bbox.yMin ) \ 52ec62c527eb34ee4481a0153ceb42dfd35d7e1d26Makoto Onuki bbox.yMin = p->y; \ 53ec62c527eb34ee4481a0153ceb42dfd35d7e1d26Makoto Onuki if ( p->y > bbox.yMax ) \ 54ec62c527eb34ee4481a0153ceb42dfd35d7e1d26Makoto Onuki bbox.yMax = p->y; \ 55ec62c527eb34ee4481a0153ceb42dfd35d7e1d26Makoto Onuki FT_END_STMNT 56ec62c527eb34ee4481a0153ceb42dfd35d7e1d26Makoto Onuki 57ec62c527eb34ee4481a0153ceb42dfd35d7e1d26Makoto Onuki#define CHECK_X( p, bbox ) \ 58ec62c527eb34ee4481a0153ceb42dfd35d7e1d26Makoto Onuki ( p->x < bbox.xMin || p->x > bbox.xMax ) 59ec62c527eb34ee4481a0153ceb42dfd35d7e1d26Makoto Onuki 60ec62c527eb34ee4481a0153ceb42dfd35d7e1d26Makoto Onuki#define CHECK_Y( p, bbox ) \ 61ec62c527eb34ee4481a0153ceb42dfd35d7e1d26Makoto Onuki ( p->y < bbox.yMin || p->y > bbox.yMax ) 62ec62c527eb34ee4481a0153ceb42dfd35d7e1d26Makoto Onuki 63ec62c527eb34ee4481a0153ceb42dfd35d7e1d26Makoto Onuki 64049d6fea481044fcc000e7782e5bc7046fc70844The Android Open Source Project /*************************************************************************/ 65049d6fea481044fcc000e7782e5bc7046fc70844The Android Open Source Project /* */ 66049d6fea481044fcc000e7782e5bc7046fc70844The Android Open Source Project /* <Function> */ 67049d6fea481044fcc000e7782e5bc7046fc70844The Android Open Source Project /* BBox_Move_To */ 68049d6fea481044fcc000e7782e5bc7046fc70844The Android Open Source Project /* */ 69049d6fea481044fcc000e7782e5bc7046fc70844The Android Open Source Project /* <Description> */ 70ec62c527eb34ee4481a0153ceb42dfd35d7e1d26Makoto Onuki /* This function is used as a `move_to' emitter during */ 71049d6fea481044fcc000e7782e5bc7046fc70844The Android Open Source Project /* FT_Outline_Decompose(). It simply records the destination point */ 72ec62c527eb34ee4481a0153ceb42dfd35d7e1d26Makoto Onuki /* in `user->last'. We also update bbox in case contour starts with */ 73ec62c527eb34ee4481a0153ceb42dfd35d7e1d26Makoto Onuki /* an implicit `on' point. */ 74049d6fea481044fcc000e7782e5bc7046fc70844The Android Open Source Project /* */ 75049d6fea481044fcc000e7782e5bc7046fc70844The Android Open Source Project /* <Input> */ 76049d6fea481044fcc000e7782e5bc7046fc70844The Android Open Source Project /* to :: A pointer to the destination vector. */ 77049d6fea481044fcc000e7782e5bc7046fc70844The Android Open Source Project /* */ 78049d6fea481044fcc000e7782e5bc7046fc70844The Android Open Source Project /* <InOut> */ 79049d6fea481044fcc000e7782e5bc7046fc70844The Android Open Source Project /* user :: A pointer to the current walk context. */ 80049d6fea481044fcc000e7782e5bc7046fc70844The Android Open Source Project /* */ 81049d6fea481044fcc000e7782e5bc7046fc70844The Android Open Source Project /* <Return> */ 82049d6fea481044fcc000e7782e5bc7046fc70844The Android Open Source Project /* Always 0. Needed for the interface only. */ 83049d6fea481044fcc000e7782e5bc7046fc70844The Android Open Source Project /* */ 84049d6fea481044fcc000e7782e5bc7046fc70844The Android Open Source Project static int 85049d6fea481044fcc000e7782e5bc7046fc70844The Android Open Source Project BBox_Move_To( FT_Vector* to, 86049d6fea481044fcc000e7782e5bc7046fc70844The Android Open Source Project TBBox_Rec* user ) 87049d6fea481044fcc000e7782e5bc7046fc70844The Android Open Source Project { 88ec62c527eb34ee4481a0153ceb42dfd35d7e1d26Makoto Onuki FT_UPDATE_BBOX( to, user->bbox ); 89ec62c527eb34ee4481a0153ceb42dfd35d7e1d26Makoto Onuki 90049d6fea481044fcc000e7782e5bc7046fc70844The Android Open Source Project user->last = *to; 91049d6fea481044fcc000e7782e5bc7046fc70844The Android Open Source Project 92049d6fea481044fcc000e7782e5bc7046fc70844The Android Open Source Project return 0; 93049d6fea481044fcc000e7782e5bc7046fc70844The Android Open Source Project } 94049d6fea481044fcc000e7782e5bc7046fc70844The Android Open Source Project 95049d6fea481044fcc000e7782e5bc7046fc70844The Android Open Source Project 96ec62c527eb34ee4481a0153ceb42dfd35d7e1d26Makoto Onuki /*************************************************************************/ 97ec62c527eb34ee4481a0153ceb42dfd35d7e1d26Makoto Onuki /* */ 98ec62c527eb34ee4481a0153ceb42dfd35d7e1d26Makoto Onuki /* <Function> */ 99ec62c527eb34ee4481a0153ceb42dfd35d7e1d26Makoto Onuki /* BBox_Line_To */ 100ec62c527eb34ee4481a0153ceb42dfd35d7e1d26Makoto Onuki /* */ 101ec62c527eb34ee4481a0153ceb42dfd35d7e1d26Makoto Onuki /* <Description> */ 102ec62c527eb34ee4481a0153ceb42dfd35d7e1d26Makoto Onuki /* This function is used as a `line_to' emitter during */ 103ec62c527eb34ee4481a0153ceb42dfd35d7e1d26Makoto Onuki /* FT_Outline_Decompose(). It simply records the destination point */ 104ec62c527eb34ee4481a0153ceb42dfd35d7e1d26Makoto Onuki /* in `user->last'; no further computations are necessary because */ 105ec62c527eb34ee4481a0153ceb42dfd35d7e1d26Makoto Onuki /* bbox already contains both explicit ends of the line segment. */ 106ec62c527eb34ee4481a0153ceb42dfd35d7e1d26Makoto Onuki /* */ 107ec62c527eb34ee4481a0153ceb42dfd35d7e1d26Makoto Onuki /* <Input> */ 108ec62c527eb34ee4481a0153ceb42dfd35d7e1d26Makoto Onuki /* to :: A pointer to the destination vector. */ 109ec62c527eb34ee4481a0153ceb42dfd35d7e1d26Makoto Onuki /* */ 110ec62c527eb34ee4481a0153ceb42dfd35d7e1d26Makoto Onuki /* <InOut> */ 111ec62c527eb34ee4481a0153ceb42dfd35d7e1d26Makoto Onuki /* user :: A pointer to the current walk context. */ 112ec62c527eb34ee4481a0153ceb42dfd35d7e1d26Makoto Onuki /* */ 113ec62c527eb34ee4481a0153ceb42dfd35d7e1d26Makoto Onuki /* <Return> */ 114ec62c527eb34ee4481a0153ceb42dfd35d7e1d26Makoto Onuki /* Always 0. Needed for the interface only. */ 115ec62c527eb34ee4481a0153ceb42dfd35d7e1d26Makoto Onuki /* */ 116ec62c527eb34ee4481a0153ceb42dfd35d7e1d26Makoto Onuki static int 117ec62c527eb34ee4481a0153ceb42dfd35d7e1d26Makoto Onuki BBox_Line_To( FT_Vector* to, 118ec62c527eb34ee4481a0153ceb42dfd35d7e1d26Makoto Onuki TBBox_Rec* user ) 119ec62c527eb34ee4481a0153ceb42dfd35d7e1d26Makoto Onuki { 120ec62c527eb34ee4481a0153ceb42dfd35d7e1d26Makoto Onuki user->last = *to; 121049d6fea481044fcc000e7782e5bc7046fc70844The Android Open Source Project 122ec62c527eb34ee4481a0153ceb42dfd35d7e1d26Makoto Onuki return 0; 123ec62c527eb34ee4481a0153ceb42dfd35d7e1d26Makoto Onuki } 124049d6fea481044fcc000e7782e5bc7046fc70844The Android Open Source Project 125049d6fea481044fcc000e7782e5bc7046fc70844The Android Open Source Project 126049d6fea481044fcc000e7782e5bc7046fc70844The Android Open Source Project /*************************************************************************/ 127049d6fea481044fcc000e7782e5bc7046fc70844The Android Open Source Project /* */ 128049d6fea481044fcc000e7782e5bc7046fc70844The Android Open Source Project /* <Function> */ 129049d6fea481044fcc000e7782e5bc7046fc70844The Android Open Source Project /* BBox_Conic_Check */ 130049d6fea481044fcc000e7782e5bc7046fc70844The Android Open Source Project /* */ 131049d6fea481044fcc000e7782e5bc7046fc70844The Android Open Source Project /* <Description> */ 132ec0bab5697bb31ba980810145f62e3799946ec60Victoria Lease /* Find the extrema of a 1-dimensional conic Bezier curve and update */ 133049d6fea481044fcc000e7782e5bc7046fc70844The Android Open Source Project /* a bounding range. This version uses direct computation, as it */ 134049d6fea481044fcc000e7782e5bc7046fc70844The Android Open Source Project /* doesn't need square roots. */ 135049d6fea481044fcc000e7782e5bc7046fc70844The Android Open Source Project /* */ 136049d6fea481044fcc000e7782e5bc7046fc70844The Android Open Source Project /* <Input> */ 137049d6fea481044fcc000e7782e5bc7046fc70844The Android Open Source Project /* y1 :: The start coordinate. */ 138049d6fea481044fcc000e7782e5bc7046fc70844The Android Open Source Project /* */ 139049d6fea481044fcc000e7782e5bc7046fc70844The Android Open Source Project /* y2 :: The coordinate of the control point. */ 140049d6fea481044fcc000e7782e5bc7046fc70844The Android Open Source Project /* */ 141049d6fea481044fcc000e7782e5bc7046fc70844The Android Open Source Project /* y3 :: The end coordinate. */ 142049d6fea481044fcc000e7782e5bc7046fc70844The Android Open Source Project /* */ 143049d6fea481044fcc000e7782e5bc7046fc70844The Android Open Source Project /* <InOut> */ 144049d6fea481044fcc000e7782e5bc7046fc70844The Android Open Source Project /* min :: The address of the current minimum. */ 145049d6fea481044fcc000e7782e5bc7046fc70844The Android Open Source Project /* */ 146049d6fea481044fcc000e7782e5bc7046fc70844The Android Open Source Project /* max :: The address of the current maximum. */ 147049d6fea481044fcc000e7782e5bc7046fc70844The Android Open Source Project /* */ 148049d6fea481044fcc000e7782e5bc7046fc70844The Android Open Source Project static void 149049d6fea481044fcc000e7782e5bc7046fc70844The Android Open Source Project BBox_Conic_Check( FT_Pos y1, 150049d6fea481044fcc000e7782e5bc7046fc70844The Android Open Source Project FT_Pos y2, 151049d6fea481044fcc000e7782e5bc7046fc70844The Android Open Source Project FT_Pos y3, 152049d6fea481044fcc000e7782e5bc7046fc70844The Android Open Source Project FT_Pos* min, 153049d6fea481044fcc000e7782e5bc7046fc70844The Android Open Source Project FT_Pos* max ) 154049d6fea481044fcc000e7782e5bc7046fc70844The Android Open Source Project { 155ec0bab5697bb31ba980810145f62e3799946ec60Victoria Lease /* This function is only called when a control off-point is outside */ 156ec0bab5697bb31ba980810145f62e3799946ec60Victoria Lease /* the bbox that contains all on-points. It finds a local extremum */ 157ec0bab5697bb31ba980810145f62e3799946ec60Victoria Lease /* within the segment, equal to (y1*y3 - y2*y2)/(y1 - 2*y2 + y3). */ 158ec0bab5697bb31ba980810145f62e3799946ec60Victoria Lease /* Or, offsetting from y2, we get */ 159ec0bab5697bb31ba980810145f62e3799946ec60Victoria Lease 160ec0bab5697bb31ba980810145f62e3799946ec60Victoria Lease y1 -= y2; 161ec0bab5697bb31ba980810145f62e3799946ec60Victoria Lease y3 -= y2; 162ec0bab5697bb31ba980810145f62e3799946ec60Victoria Lease y2 += FT_MulDiv( y1, y3, y1 + y3 ); 163ec0bab5697bb31ba980810145f62e3799946ec60Victoria Lease 164ec0bab5697bb31ba980810145f62e3799946ec60Victoria Lease if ( y2 < *min ) 165ec0bab5697bb31ba980810145f62e3799946ec60Victoria Lease *min = y2; 166ec0bab5697bb31ba980810145f62e3799946ec60Victoria Lease if ( y2 > *max ) 167ec0bab5697bb31ba980810145f62e3799946ec60Victoria Lease *max = y2; 168049d6fea481044fcc000e7782e5bc7046fc70844The Android Open Source Project } 169049d6fea481044fcc000e7782e5bc7046fc70844The Android Open Source Project 170049d6fea481044fcc000e7782e5bc7046fc70844The Android Open Source Project 171049d6fea481044fcc000e7782e5bc7046fc70844The Android Open Source Project /*************************************************************************/ 172049d6fea481044fcc000e7782e5bc7046fc70844The Android Open Source Project /* */ 173049d6fea481044fcc000e7782e5bc7046fc70844The Android Open Source Project /* <Function> */ 174049d6fea481044fcc000e7782e5bc7046fc70844The Android Open Source Project /* BBox_Conic_To */ 175049d6fea481044fcc000e7782e5bc7046fc70844The Android Open Source Project /* */ 176049d6fea481044fcc000e7782e5bc7046fc70844The Android Open Source Project /* <Description> */ 177049d6fea481044fcc000e7782e5bc7046fc70844The Android Open Source Project /* This function is used as a `conic_to' emitter during */ 178295ffce55e0198e7a9f7d46b33f5c2b4147bf821David 'Digit' Turner /* FT_Outline_Decompose(). It checks a conic Bezier curve with the */ 179049d6fea481044fcc000e7782e5bc7046fc70844The Android Open Source Project /* current bounding box, and computes its extrema if necessary to */ 180049d6fea481044fcc000e7782e5bc7046fc70844The Android Open Source Project /* update it. */ 181049d6fea481044fcc000e7782e5bc7046fc70844The Android Open Source Project /* */ 182049d6fea481044fcc000e7782e5bc7046fc70844The Android Open Source Project /* <Input> */ 183049d6fea481044fcc000e7782e5bc7046fc70844The Android Open Source Project /* control :: A pointer to a control point. */ 184049d6fea481044fcc000e7782e5bc7046fc70844The Android Open Source Project /* */ 185049d6fea481044fcc000e7782e5bc7046fc70844The Android Open Source Project /* to :: A pointer to the destination vector. */ 186049d6fea481044fcc000e7782e5bc7046fc70844The Android Open Source Project /* */ 187049d6fea481044fcc000e7782e5bc7046fc70844The Android Open Source Project /* <InOut> */ 188049d6fea481044fcc000e7782e5bc7046fc70844The Android Open Source Project /* user :: The address of the current walk context. */ 189049d6fea481044fcc000e7782e5bc7046fc70844The Android Open Source Project /* */ 190049d6fea481044fcc000e7782e5bc7046fc70844The Android Open Source Project /* <Return> */ 191049d6fea481044fcc000e7782e5bc7046fc70844The Android Open Source Project /* Always 0. Needed for the interface only. */ 192049d6fea481044fcc000e7782e5bc7046fc70844The Android Open Source Project /* */ 193049d6fea481044fcc000e7782e5bc7046fc70844The Android Open Source Project /* <Note> */ 194049d6fea481044fcc000e7782e5bc7046fc70844The Android Open Source Project /* In the case of a non-monotonous arc, we compute directly the */ 195049d6fea481044fcc000e7782e5bc7046fc70844The Android Open Source Project /* extremum coordinates, as it is sufficiently fast. */ 196049d6fea481044fcc000e7782e5bc7046fc70844The Android Open Source Project /* */ 197049d6fea481044fcc000e7782e5bc7046fc70844The Android Open Source Project static int 198049d6fea481044fcc000e7782e5bc7046fc70844The Android Open Source Project BBox_Conic_To( FT_Vector* control, 199049d6fea481044fcc000e7782e5bc7046fc70844The Android Open Source Project FT_Vector* to, 200049d6fea481044fcc000e7782e5bc7046fc70844The Android Open Source Project TBBox_Rec* user ) 201049d6fea481044fcc000e7782e5bc7046fc70844The Android Open Source Project { 202ec62c527eb34ee4481a0153ceb42dfd35d7e1d26Makoto Onuki /* in case `to' is implicit and not included in bbox yet */ 203ec62c527eb34ee4481a0153ceb42dfd35d7e1d26Makoto Onuki FT_UPDATE_BBOX( to, user->bbox ); 204049d6fea481044fcc000e7782e5bc7046fc70844The Android Open Source Project 205049d6fea481044fcc000e7782e5bc7046fc70844The Android Open Source Project if ( CHECK_X( control, user->bbox ) ) 206049d6fea481044fcc000e7782e5bc7046fc70844The Android Open Source Project BBox_Conic_Check( user->last.x, 207049d6fea481044fcc000e7782e5bc7046fc70844The Android Open Source Project control->x, 208049d6fea481044fcc000e7782e5bc7046fc70844The Android Open Source Project to->x, 209049d6fea481044fcc000e7782e5bc7046fc70844The Android Open Source Project &user->bbox.xMin, 210049d6fea481044fcc000e7782e5bc7046fc70844The Android Open Source Project &user->bbox.xMax ); 211049d6fea481044fcc000e7782e5bc7046fc70844The Android Open Source Project 212049d6fea481044fcc000e7782e5bc7046fc70844The Android Open Source Project if ( CHECK_Y( control, user->bbox ) ) 213049d6fea481044fcc000e7782e5bc7046fc70844The Android Open Source Project BBox_Conic_Check( user->last.y, 214049d6fea481044fcc000e7782e5bc7046fc70844The Android Open Source Project control->y, 215049d6fea481044fcc000e7782e5bc7046fc70844The Android Open Source Project to->y, 216049d6fea481044fcc000e7782e5bc7046fc70844The Android Open Source Project &user->bbox.yMin, 217049d6fea481044fcc000e7782e5bc7046fc70844The Android Open Source Project &user->bbox.yMax ); 218049d6fea481044fcc000e7782e5bc7046fc70844The Android Open Source Project 219049d6fea481044fcc000e7782e5bc7046fc70844The Android Open Source Project user->last = *to; 220049d6fea481044fcc000e7782e5bc7046fc70844The Android Open Source Project 221049d6fea481044fcc000e7782e5bc7046fc70844The Android Open Source Project return 0; 222049d6fea481044fcc000e7782e5bc7046fc70844The Android Open Source Project } 223049d6fea481044fcc000e7782e5bc7046fc70844The Android Open Source Project 224049d6fea481044fcc000e7782e5bc7046fc70844The Android Open Source Project 225049d6fea481044fcc000e7782e5bc7046fc70844The Android Open Source Project /*************************************************************************/ 226049d6fea481044fcc000e7782e5bc7046fc70844The Android Open Source Project /* */ 227049d6fea481044fcc000e7782e5bc7046fc70844The Android Open Source Project /* <Function> */ 228049d6fea481044fcc000e7782e5bc7046fc70844The Android Open Source Project /* BBox_Cubic_Check */ 229049d6fea481044fcc000e7782e5bc7046fc70844The Android Open Source Project /* */ 230049d6fea481044fcc000e7782e5bc7046fc70844The Android Open Source Project /* <Description> */ 231ec0bab5697bb31ba980810145f62e3799946ec60Victoria Lease /* Find the extrema of a 1-dimensional cubic Bezier curve and */ 232ec0bab5697bb31ba980810145f62e3799946ec60Victoria Lease /* update a bounding range. This version uses iterative splitting */ 233ec0bab5697bb31ba980810145f62e3799946ec60Victoria Lease /* because it is faster than the exact solution with square roots. */ 234049d6fea481044fcc000e7782e5bc7046fc70844The Android Open Source Project /* */ 235049d6fea481044fcc000e7782e5bc7046fc70844The Android Open Source Project /* <Input> */ 236049d6fea481044fcc000e7782e5bc7046fc70844The Android Open Source Project /* p1 :: The start coordinate. */ 237049d6fea481044fcc000e7782e5bc7046fc70844The Android Open Source Project /* */ 238049d6fea481044fcc000e7782e5bc7046fc70844The Android Open Source Project /* p2 :: The coordinate of the first control point. */ 239049d6fea481044fcc000e7782e5bc7046fc70844The Android Open Source Project /* */ 240049d6fea481044fcc000e7782e5bc7046fc70844The Android Open Source Project /* p3 :: The coordinate of the second control point. */ 241049d6fea481044fcc000e7782e5bc7046fc70844The Android Open Source Project /* */ 242049d6fea481044fcc000e7782e5bc7046fc70844The Android Open Source Project /* p4 :: The end coordinate. */ 243049d6fea481044fcc000e7782e5bc7046fc70844The Android Open Source Project /* */ 244049d6fea481044fcc000e7782e5bc7046fc70844The Android Open Source Project /* <InOut> */ 245049d6fea481044fcc000e7782e5bc7046fc70844The Android Open Source Project /* min :: The address of the current minimum. */ 246049d6fea481044fcc000e7782e5bc7046fc70844The Android Open Source Project /* */ 247049d6fea481044fcc000e7782e5bc7046fc70844The Android Open Source Project /* max :: The address of the current maximum. */ 248049d6fea481044fcc000e7782e5bc7046fc70844The Android Open Source Project /* */ 249ec0bab5697bb31ba980810145f62e3799946ec60Victoria Lease static FT_Pos 250ec62c527eb34ee4481a0153ceb42dfd35d7e1d26Makoto Onuki cubic_peak( FT_Pos q1, 251ec62c527eb34ee4481a0153ceb42dfd35d7e1d26Makoto Onuki FT_Pos q2, 252ec62c527eb34ee4481a0153ceb42dfd35d7e1d26Makoto Onuki FT_Pos q3, 253ec62c527eb34ee4481a0153ceb42dfd35d7e1d26Makoto Onuki FT_Pos q4 ) 254049d6fea481044fcc000e7782e5bc7046fc70844The Android Open Source Project { 255ec62c527eb34ee4481a0153ceb42dfd35d7e1d26Makoto Onuki FT_Pos peak = 0; 256ec62c527eb34ee4481a0153ceb42dfd35d7e1d26Makoto Onuki FT_Int shift; 257ec62c527eb34ee4481a0153ceb42dfd35d7e1d26Makoto Onuki 258ec62c527eb34ee4481a0153ceb42dfd35d7e1d26Makoto Onuki 259ec62c527eb34ee4481a0153ceb42dfd35d7e1d26Makoto Onuki /* This function finds a peak of a cubic segment if it is above 0 */ 260ec62c527eb34ee4481a0153ceb42dfd35d7e1d26Makoto Onuki /* using iterative bisection of the segment, or returns 0. */ 261ec62c527eb34ee4481a0153ceb42dfd35d7e1d26Makoto Onuki /* The fixed-point arithmetic of bisection is inherently stable */ 262ec62c527eb34ee4481a0153ceb42dfd35d7e1d26Makoto Onuki /* but may loose accuracy in the two lowest bits. To compensate, */ 263ec62c527eb34ee4481a0153ceb42dfd35d7e1d26Makoto Onuki /* we upscale the segment if there is room. Large values may need */ 264ec62c527eb34ee4481a0153ceb42dfd35d7e1d26Makoto Onuki /* to be downscaled to avoid overflows during bisection. */ 265ec62c527eb34ee4481a0153ceb42dfd35d7e1d26Makoto Onuki /* It is called with either q2 or q3 positive, which is necessary */ 266ec62c527eb34ee4481a0153ceb42dfd35d7e1d26Makoto Onuki /* for the peak to exist and avoids undefined FT_MSB. */ 267ec62c527eb34ee4481a0153ceb42dfd35d7e1d26Makoto Onuki 268ec62c527eb34ee4481a0153ceb42dfd35d7e1d26Makoto Onuki shift = 27 - FT_MSB( (FT_UInt32)( FT_ABS( q1 ) | 269ec62c527eb34ee4481a0153ceb42dfd35d7e1d26Makoto Onuki FT_ABS( q2 ) | 270ec62c527eb34ee4481a0153ceb42dfd35d7e1d26Makoto Onuki FT_ABS( q3 ) | 271ec62c527eb34ee4481a0153ceb42dfd35d7e1d26Makoto Onuki FT_ABS( q4 ) ) ); 272ec62c527eb34ee4481a0153ceb42dfd35d7e1d26Makoto Onuki 273ec62c527eb34ee4481a0153ceb42dfd35d7e1d26Makoto Onuki if ( shift > 0 ) 274ec62c527eb34ee4481a0153ceb42dfd35d7e1d26Makoto Onuki { 275ec62c527eb34ee4481a0153ceb42dfd35d7e1d26Makoto Onuki /* upscaling too much just wastes time */ 276ec62c527eb34ee4481a0153ceb42dfd35d7e1d26Makoto Onuki if ( shift > 2 ) 277ec62c527eb34ee4481a0153ceb42dfd35d7e1d26Makoto Onuki shift = 2; 278ec62c527eb34ee4481a0153ceb42dfd35d7e1d26Makoto Onuki 279ec62c527eb34ee4481a0153ceb42dfd35d7e1d26Makoto Onuki q1 <<= shift; 280ec62c527eb34ee4481a0153ceb42dfd35d7e1d26Makoto Onuki q2 <<= shift; 281ec62c527eb34ee4481a0153ceb42dfd35d7e1d26Makoto Onuki q3 <<= shift; 282ec62c527eb34ee4481a0153ceb42dfd35d7e1d26Makoto Onuki q4 <<= shift; 283ec62c527eb34ee4481a0153ceb42dfd35d7e1d26Makoto Onuki } 284ec62c527eb34ee4481a0153ceb42dfd35d7e1d26Makoto Onuki else 285ec62c527eb34ee4481a0153ceb42dfd35d7e1d26Makoto Onuki { 286ec62c527eb34ee4481a0153ceb42dfd35d7e1d26Makoto Onuki q1 >>= -shift; 287ec62c527eb34ee4481a0153ceb42dfd35d7e1d26Makoto Onuki q2 >>= -shift; 288ec62c527eb34ee4481a0153ceb42dfd35d7e1d26Makoto Onuki q3 >>= -shift; 289ec62c527eb34ee4481a0153ceb42dfd35d7e1d26Makoto Onuki q4 >>= -shift; 290ec62c527eb34ee4481a0153ceb42dfd35d7e1d26Makoto Onuki } 291ec62c527eb34ee4481a0153ceb42dfd35d7e1d26Makoto Onuki 292ec62c527eb34ee4481a0153ceb42dfd35d7e1d26Makoto Onuki /* for a peak to exist above 0, the cubic segment must have */ 293ec62c527eb34ee4481a0153ceb42dfd35d7e1d26Makoto Onuki /* at least one of its control off-points above 0. */ 294ec62c527eb34ee4481a0153ceb42dfd35d7e1d26Makoto Onuki while ( q2 > 0 || q3 > 0 ) 295049d6fea481044fcc000e7782e5bc7046fc70844The Android Open Source Project { 296727dee178a392d20eb050d0c446f2fcc29058fa1Victoria Lease /* determine which half contains the maximum and split */ 297727dee178a392d20eb050d0c446f2fcc29058fa1Victoria Lease if ( q1 + q2 > q3 + q4 ) /* first half */ 298049d6fea481044fcc000e7782e5bc7046fc70844The Android Open Source Project { 299727dee178a392d20eb050d0c446f2fcc29058fa1Victoria Lease q4 = q4 + q3; 300727dee178a392d20eb050d0c446f2fcc29058fa1Victoria Lease q3 = q3 + q2; 301727dee178a392d20eb050d0c446f2fcc29058fa1Victoria Lease q2 = q2 + q1; 302727dee178a392d20eb050d0c446f2fcc29058fa1Victoria Lease q4 = q4 + q3; 303727dee178a392d20eb050d0c446f2fcc29058fa1Victoria Lease q3 = q3 + q2; 304727dee178a392d20eb050d0c446f2fcc29058fa1Victoria Lease q4 = ( q4 + q3 ) / 8; 305727dee178a392d20eb050d0c446f2fcc29058fa1Victoria Lease q3 = q3 / 4; 306727dee178a392d20eb050d0c446f2fcc29058fa1Victoria Lease q2 = q2 / 2; 307049d6fea481044fcc000e7782e5bc7046fc70844The Android Open Source Project } 308727dee178a392d20eb050d0c446f2fcc29058fa1Victoria Lease else /* second half */ 309049d6fea481044fcc000e7782e5bc7046fc70844The Android Open Source Project { 310727dee178a392d20eb050d0c446f2fcc29058fa1Victoria Lease q1 = q1 + q2; 311727dee178a392d20eb050d0c446f2fcc29058fa1Victoria Lease q2 = q2 + q3; 312727dee178a392d20eb050d0c446f2fcc29058fa1Victoria Lease q3 = q3 + q4; 313727dee178a392d20eb050d0c446f2fcc29058fa1Victoria Lease q1 = q1 + q2; 314727dee178a392d20eb050d0c446f2fcc29058fa1Victoria Lease q2 = q2 + q3; 315727dee178a392d20eb050d0c446f2fcc29058fa1Victoria Lease q1 = ( q1 + q2 ) / 8; 316727dee178a392d20eb050d0c446f2fcc29058fa1Victoria Lease q2 = q2 / 4; 317727dee178a392d20eb050d0c446f2fcc29058fa1Victoria Lease q3 = q3 / 2; 318049d6fea481044fcc000e7782e5bc7046fc70844The Android Open Source Project } 319727dee178a392d20eb050d0c446f2fcc29058fa1Victoria Lease 320ec0bab5697bb31ba980810145f62e3799946ec60Victoria Lease /* check whether either end reached the maximum */ 321727dee178a392d20eb050d0c446f2fcc29058fa1Victoria Lease if ( q1 == q2 && q1 >= q3 ) 322049d6fea481044fcc000e7782e5bc7046fc70844The Android Open Source Project { 323ec62c527eb34ee4481a0153ceb42dfd35d7e1d26Makoto Onuki peak = q1; 324727dee178a392d20eb050d0c446f2fcc29058fa1Victoria Lease break; 325049d6fea481044fcc000e7782e5bc7046fc70844The Android Open Source Project } 326727dee178a392d20eb050d0c446f2fcc29058fa1Victoria Lease if ( q3 == q4 && q2 <= q4 ) 327727dee178a392d20eb050d0c446f2fcc29058fa1Victoria Lease { 328ec62c527eb34ee4481a0153ceb42dfd35d7e1d26Makoto Onuki peak = q4; 329727dee178a392d20eb050d0c446f2fcc29058fa1Victoria Lease break; 330727dee178a392d20eb050d0c446f2fcc29058fa1Victoria Lease } 331727dee178a392d20eb050d0c446f2fcc29058fa1Victoria Lease } 332049d6fea481044fcc000e7782e5bc7046fc70844The Android Open Source Project 333ec62c527eb34ee4481a0153ceb42dfd35d7e1d26Makoto Onuki if ( shift > 0 ) 334ec62c527eb34ee4481a0153ceb42dfd35d7e1d26Makoto Onuki peak >>= shift; 335ec62c527eb34ee4481a0153ceb42dfd35d7e1d26Makoto Onuki else 336ec62c527eb34ee4481a0153ceb42dfd35d7e1d26Makoto Onuki peak <<= -shift; 337ec62c527eb34ee4481a0153ceb42dfd35d7e1d26Makoto Onuki 338ec62c527eb34ee4481a0153ceb42dfd35d7e1d26Makoto Onuki return peak; 339049d6fea481044fcc000e7782e5bc7046fc70844The Android Open Source Project } 340049d6fea481044fcc000e7782e5bc7046fc70844The Android Open Source Project 341049d6fea481044fcc000e7782e5bc7046fc70844The Android Open Source Project 342049d6fea481044fcc000e7782e5bc7046fc70844The Android Open Source Project static void 343ec0bab5697bb31ba980810145f62e3799946ec60Victoria Lease BBox_Cubic_Check( FT_Pos p1, 344ec0bab5697bb31ba980810145f62e3799946ec60Victoria Lease FT_Pos p2, 345ec0bab5697bb31ba980810145f62e3799946ec60Victoria Lease FT_Pos p3, 346ec0bab5697bb31ba980810145f62e3799946ec60Victoria Lease FT_Pos p4, 347049d6fea481044fcc000e7782e5bc7046fc70844The Android Open Source Project FT_Pos* min, 348049d6fea481044fcc000e7782e5bc7046fc70844The Android Open Source Project FT_Pos* max ) 349049d6fea481044fcc000e7782e5bc7046fc70844The Android Open Source Project { 350ec0bab5697bb31ba980810145f62e3799946ec60Victoria Lease /* This function is only called when a control off-point is outside */ 351ec62c527eb34ee4481a0153ceb42dfd35d7e1d26Makoto Onuki /* the bbox that contains all on-points. So at least one of the */ 352ec62c527eb34ee4481a0153ceb42dfd35d7e1d26Makoto Onuki /* conditions below holds and cubic_peak is called with at least one */ 353ec62c527eb34ee4481a0153ceb42dfd35d7e1d26Makoto Onuki /* non-zero argument. */ 354049d6fea481044fcc000e7782e5bc7046fc70844The Android Open Source Project 355ec62c527eb34ee4481a0153ceb42dfd35d7e1d26Makoto Onuki if ( p2 > *max || p3 > *max ) 356ec62c527eb34ee4481a0153ceb42dfd35d7e1d26Makoto Onuki *max += cubic_peak( p1 - *max, p2 - *max, p3 - *max, p4 - *max ); 357049d6fea481044fcc000e7782e5bc7046fc70844The Android Open Source Project 358ec0bab5697bb31ba980810145f62e3799946ec60Victoria Lease /* now flip the signs to update the minimum */ 359ec62c527eb34ee4481a0153ceb42dfd35d7e1d26Makoto Onuki if ( p2 < *min || p3 < *min ) 360ec62c527eb34ee4481a0153ceb42dfd35d7e1d26Makoto Onuki *min -= cubic_peak( *min - p1, *min - p2, *min - p3, *min - p4 ); 361ec0bab5697bb31ba980810145f62e3799946ec60Victoria Lease } 362049d6fea481044fcc000e7782e5bc7046fc70844The Android Open Source Project 363049d6fea481044fcc000e7782e5bc7046fc70844The Android Open Source Project 364049d6fea481044fcc000e7782e5bc7046fc70844The Android Open Source Project /*************************************************************************/ 365049d6fea481044fcc000e7782e5bc7046fc70844The Android Open Source Project /* */ 366049d6fea481044fcc000e7782e5bc7046fc70844The Android Open Source Project /* <Function> */ 367049d6fea481044fcc000e7782e5bc7046fc70844The Android Open Source Project /* BBox_Cubic_To */ 368049d6fea481044fcc000e7782e5bc7046fc70844The Android Open Source Project /* */ 369049d6fea481044fcc000e7782e5bc7046fc70844The Android Open Source Project /* <Description> */ 370049d6fea481044fcc000e7782e5bc7046fc70844The Android Open Source Project /* This function is used as a `cubic_to' emitter during */ 371295ffce55e0198e7a9f7d46b33f5c2b4147bf821David 'Digit' Turner /* FT_Outline_Decompose(). It checks a cubic Bezier curve with the */ 372049d6fea481044fcc000e7782e5bc7046fc70844The Android Open Source Project /* current bounding box, and computes its extrema if necessary to */ 373049d6fea481044fcc000e7782e5bc7046fc70844The Android Open Source Project /* update it. */ 374049d6fea481044fcc000e7782e5bc7046fc70844The Android Open Source Project /* */ 375049d6fea481044fcc000e7782e5bc7046fc70844The Android Open Source Project /* <Input> */ 376049d6fea481044fcc000e7782e5bc7046fc70844The Android Open Source Project /* control1 :: A pointer to the first control point. */ 377049d6fea481044fcc000e7782e5bc7046fc70844The Android Open Source Project /* */ 378049d6fea481044fcc000e7782e5bc7046fc70844The Android Open Source Project /* control2 :: A pointer to the second control point. */ 379049d6fea481044fcc000e7782e5bc7046fc70844The Android Open Source Project /* */ 380049d6fea481044fcc000e7782e5bc7046fc70844The Android Open Source Project /* to :: A pointer to the destination vector. */ 381049d6fea481044fcc000e7782e5bc7046fc70844The Android Open Source Project /* */ 382049d6fea481044fcc000e7782e5bc7046fc70844The Android Open Source Project /* <InOut> */ 383049d6fea481044fcc000e7782e5bc7046fc70844The Android Open Source Project /* user :: The address of the current walk context. */ 384049d6fea481044fcc000e7782e5bc7046fc70844The Android Open Source Project /* */ 385049d6fea481044fcc000e7782e5bc7046fc70844The Android Open Source Project /* <Return> */ 386049d6fea481044fcc000e7782e5bc7046fc70844The Android Open Source Project /* Always 0. Needed for the interface only. */ 387049d6fea481044fcc000e7782e5bc7046fc70844The Android Open Source Project /* */ 388049d6fea481044fcc000e7782e5bc7046fc70844The Android Open Source Project /* <Note> */ 389049d6fea481044fcc000e7782e5bc7046fc70844The Android Open Source Project /* In the case of a non-monotonous arc, we don't compute directly */ 390049d6fea481044fcc000e7782e5bc7046fc70844The Android Open Source Project /* extremum coordinates, we subdivide instead. */ 391049d6fea481044fcc000e7782e5bc7046fc70844The Android Open Source Project /* */ 392049d6fea481044fcc000e7782e5bc7046fc70844The Android Open Source Project static int 393049d6fea481044fcc000e7782e5bc7046fc70844The Android Open Source Project BBox_Cubic_To( FT_Vector* control1, 394049d6fea481044fcc000e7782e5bc7046fc70844The Android Open Source Project FT_Vector* control2, 395049d6fea481044fcc000e7782e5bc7046fc70844The Android Open Source Project FT_Vector* to, 396049d6fea481044fcc000e7782e5bc7046fc70844The Android Open Source Project TBBox_Rec* user ) 397049d6fea481044fcc000e7782e5bc7046fc70844The Android Open Source Project { 398ec0bab5697bb31ba980810145f62e3799946ec60Victoria Lease /* We don't need to check `to' since it is always an on-point, */ 399ec0bab5697bb31ba980810145f62e3799946ec60Victoria Lease /* thus within the bbox. Only segments with an off-point outside */ 400ec0bab5697bb31ba980810145f62e3799946ec60Victoria Lease /* the bbox can possibly reach new extreme values. */ 401049d6fea481044fcc000e7782e5bc7046fc70844The Android Open Source Project 402049d6fea481044fcc000e7782e5bc7046fc70844The Android Open Source Project if ( CHECK_X( control1, user->bbox ) || 403049d6fea481044fcc000e7782e5bc7046fc70844The Android Open Source Project CHECK_X( control2, user->bbox ) ) 404049d6fea481044fcc000e7782e5bc7046fc70844The Android Open Source Project BBox_Cubic_Check( user->last.x, 405049d6fea481044fcc000e7782e5bc7046fc70844The Android Open Source Project control1->x, 406049d6fea481044fcc000e7782e5bc7046fc70844The Android Open Source Project control2->x, 407049d6fea481044fcc000e7782e5bc7046fc70844The Android Open Source Project to->x, 408049d6fea481044fcc000e7782e5bc7046fc70844The Android Open Source Project &user->bbox.xMin, 409049d6fea481044fcc000e7782e5bc7046fc70844The Android Open Source Project &user->bbox.xMax ); 410049d6fea481044fcc000e7782e5bc7046fc70844The Android Open Source Project 411049d6fea481044fcc000e7782e5bc7046fc70844The Android Open Source Project if ( CHECK_Y( control1, user->bbox ) || 412049d6fea481044fcc000e7782e5bc7046fc70844The Android Open Source Project CHECK_Y( control2, user->bbox ) ) 413049d6fea481044fcc000e7782e5bc7046fc70844The Android Open Source Project BBox_Cubic_Check( user->last.y, 414049d6fea481044fcc000e7782e5bc7046fc70844The Android Open Source Project control1->y, 415049d6fea481044fcc000e7782e5bc7046fc70844The Android Open Source Project control2->y, 416049d6fea481044fcc000e7782e5bc7046fc70844The Android Open Source Project to->y, 417049d6fea481044fcc000e7782e5bc7046fc70844The Android Open Source Project &user->bbox.yMin, 418049d6fea481044fcc000e7782e5bc7046fc70844The Android Open Source Project &user->bbox.yMax ); 419049d6fea481044fcc000e7782e5bc7046fc70844The Android Open Source Project 420049d6fea481044fcc000e7782e5bc7046fc70844The Android Open Source Project user->last = *to; 421049d6fea481044fcc000e7782e5bc7046fc70844The Android Open Source Project 422049d6fea481044fcc000e7782e5bc7046fc70844The Android Open Source Project return 0; 423049d6fea481044fcc000e7782e5bc7046fc70844The Android Open Source Project } 424049d6fea481044fcc000e7782e5bc7046fc70844The Android Open Source Project 425ec62c527eb34ee4481a0153ceb42dfd35d7e1d26Makoto Onuki 426ec62c527eb34ee4481a0153ceb42dfd35d7e1d26Makoto Onuki FT_DEFINE_OUTLINE_FUNCS(bbox_interface, 427aacb8e1368a883fcbc9fe64fd0e460cef9c9b20cNick Kralevich (FT_Outline_MoveTo_Func) BBox_Move_To, 428ec62c527eb34ee4481a0153ceb42dfd35d7e1d26Makoto Onuki (FT_Outline_LineTo_Func) BBox_Line_To, 429aacb8e1368a883fcbc9fe64fd0e460cef9c9b20cNick Kralevich (FT_Outline_ConicTo_Func)BBox_Conic_To, 430aacb8e1368a883fcbc9fe64fd0e460cef9c9b20cNick Kralevich (FT_Outline_CubicTo_Func)BBox_Cubic_To, 431aacb8e1368a883fcbc9fe64fd0e460cef9c9b20cNick Kralevich 0, 0 432295ffce55e0198e7a9f7d46b33f5c2b4147bf821David 'Digit' Turner ) 433049d6fea481044fcc000e7782e5bc7046fc70844The Android Open Source Project 434ec62c527eb34ee4481a0153ceb42dfd35d7e1d26Makoto Onuki 435049d6fea481044fcc000e7782e5bc7046fc70844The Android Open Source Project /* documentation is in ftbbox.h */ 436049d6fea481044fcc000e7782e5bc7046fc70844The Android Open Source Project 437049d6fea481044fcc000e7782e5bc7046fc70844The Android Open Source Project FT_EXPORT_DEF( FT_Error ) 438049d6fea481044fcc000e7782e5bc7046fc70844The Android Open Source Project FT_Outline_Get_BBox( FT_Outline* outline, 439049d6fea481044fcc000e7782e5bc7046fc70844The Android Open Source Project FT_BBox *abbox ) 440049d6fea481044fcc000e7782e5bc7046fc70844The Android Open Source Project { 441ec62c527eb34ee4481a0153ceb42dfd35d7e1d26Makoto Onuki FT_BBox cbox = { 0x7FFFFFFFL, 0x7FFFFFFFL, 442ec62c527eb34ee4481a0153ceb42dfd35d7e1d26Makoto Onuki -0x7FFFFFFFL, -0x7FFFFFFFL }; 443ec62c527eb34ee4481a0153ceb42dfd35d7e1d26Makoto Onuki FT_BBox bbox = { 0x7FFFFFFFL, 0x7FFFFFFFL, 444ec62c527eb34ee4481a0153ceb42dfd35d7e1d26Makoto Onuki -0x7FFFFFFFL, -0x7FFFFFFFL }; 445049d6fea481044fcc000e7782e5bc7046fc70844The Android Open Source Project FT_Vector* vec; 446049d6fea481044fcc000e7782e5bc7046fc70844The Android Open Source Project FT_UShort n; 447049d6fea481044fcc000e7782e5bc7046fc70844The Android Open Source Project 448049d6fea481044fcc000e7782e5bc7046fc70844The Android Open Source Project 449049d6fea481044fcc000e7782e5bc7046fc70844The Android Open Source Project if ( !abbox ) 450727dee178a392d20eb050d0c446f2fcc29058fa1Victoria Lease return FT_THROW( Invalid_Argument ); 451049d6fea481044fcc000e7782e5bc7046fc70844The Android Open Source Project 452049d6fea481044fcc000e7782e5bc7046fc70844The Android Open Source Project if ( !outline ) 453727dee178a392d20eb050d0c446f2fcc29058fa1Victoria Lease return FT_THROW( Invalid_Outline ); 454049d6fea481044fcc000e7782e5bc7046fc70844The Android Open Source Project 455049d6fea481044fcc000e7782e5bc7046fc70844The Android Open Source Project /* if outline is empty, return (0,0,0,0) */ 456049d6fea481044fcc000e7782e5bc7046fc70844The Android Open Source Project if ( outline->n_points == 0 || outline->n_contours <= 0 ) 457049d6fea481044fcc000e7782e5bc7046fc70844The Android Open Source Project { 458049d6fea481044fcc000e7782e5bc7046fc70844The Android Open Source Project abbox->xMin = abbox->xMax = 0; 459049d6fea481044fcc000e7782e5bc7046fc70844The Android Open Source Project abbox->yMin = abbox->yMax = 0; 460049d6fea481044fcc000e7782e5bc7046fc70844The Android Open Source Project return 0; 461049d6fea481044fcc000e7782e5bc7046fc70844The Android Open Source Project } 462049d6fea481044fcc000e7782e5bc7046fc70844The Android Open Source Project 463049d6fea481044fcc000e7782e5bc7046fc70844The Android Open Source Project /* We compute the control box as well as the bounding box of */ 464049d6fea481044fcc000e7782e5bc7046fc70844The Android Open Source Project /* all `on' points in the outline. Then, if the two boxes */ 465049d6fea481044fcc000e7782e5bc7046fc70844The Android Open Source Project /* coincide, we exit immediately. */ 466049d6fea481044fcc000e7782e5bc7046fc70844The Android Open Source Project 467049d6fea481044fcc000e7782e5bc7046fc70844The Android Open Source Project vec = outline->points; 468049d6fea481044fcc000e7782e5bc7046fc70844The Android Open Source Project 469ec62c527eb34ee4481a0153ceb42dfd35d7e1d26Makoto Onuki for ( n = 0; n < outline->n_points; n++ ) 470049d6fea481044fcc000e7782e5bc7046fc70844The Android Open Source Project { 471ec62c527eb34ee4481a0153ceb42dfd35d7e1d26Makoto Onuki FT_UPDATE_BBOX( vec, cbox); 472049d6fea481044fcc000e7782e5bc7046fc70844The Android Open Source Project 473049d6fea481044fcc000e7782e5bc7046fc70844The Android Open Source Project if ( FT_CURVE_TAG( outline->tags[n] ) == FT_CURVE_TAG_ON ) 474ec62c527eb34ee4481a0153ceb42dfd35d7e1d26Makoto Onuki FT_UPDATE_BBOX( vec, bbox); 475049d6fea481044fcc000e7782e5bc7046fc70844The Android Open Source Project 476049d6fea481044fcc000e7782e5bc7046fc70844The Android Open Source Project vec++; 477049d6fea481044fcc000e7782e5bc7046fc70844The Android Open Source Project } 478049d6fea481044fcc000e7782e5bc7046fc70844The Android Open Source Project 479049d6fea481044fcc000e7782e5bc7046fc70844The Android Open Source Project /* test two boxes for equality */ 480049d6fea481044fcc000e7782e5bc7046fc70844The Android Open Source Project if ( cbox.xMin < bbox.xMin || cbox.xMax > bbox.xMax || 481049d6fea481044fcc000e7782e5bc7046fc70844The Android Open Source Project cbox.yMin < bbox.yMin || cbox.yMax > bbox.yMax ) 482049d6fea481044fcc000e7782e5bc7046fc70844The Android Open Source Project { 483049d6fea481044fcc000e7782e5bc7046fc70844The Android Open Source Project /* the two boxes are different, now walk over the outline to */ 484049d6fea481044fcc000e7782e5bc7046fc70844The Android Open Source Project /* get the Bezier arc extrema. */ 485049d6fea481044fcc000e7782e5bc7046fc70844The Android Open Source Project 486049d6fea481044fcc000e7782e5bc7046fc70844The Android Open Source Project FT_Error error; 487049d6fea481044fcc000e7782e5bc7046fc70844The Android Open Source Project TBBox_Rec user; 488049d6fea481044fcc000e7782e5bc7046fc70844The Android Open Source Project 489295ffce55e0198e7a9f7d46b33f5c2b4147bf821David 'Digit' Turner#ifdef FT_CONFIG_OPTION_PIC 490295ffce55e0198e7a9f7d46b33f5c2b4147bf821David 'Digit' Turner FT_Outline_Funcs bbox_interface; 491295ffce55e0198e7a9f7d46b33f5c2b4147bf821David 'Digit' Turner Init_Class_bbox_interface(&bbox_interface); 492295ffce55e0198e7a9f7d46b33f5c2b4147bf821David 'Digit' Turner#endif 493049d6fea481044fcc000e7782e5bc7046fc70844The Android Open Source Project 494049d6fea481044fcc000e7782e5bc7046fc70844The Android Open Source Project user.bbox = bbox; 495049d6fea481044fcc000e7782e5bc7046fc70844The Android Open Source Project 496049d6fea481044fcc000e7782e5bc7046fc70844The Android Open Source Project error = FT_Outline_Decompose( outline, &bbox_interface, &user ); 497049d6fea481044fcc000e7782e5bc7046fc70844The Android Open Source Project if ( error ) 498049d6fea481044fcc000e7782e5bc7046fc70844The Android Open Source Project return error; 499049d6fea481044fcc000e7782e5bc7046fc70844The Android Open Source Project 500049d6fea481044fcc000e7782e5bc7046fc70844The Android Open Source Project *abbox = user.bbox; 501049d6fea481044fcc000e7782e5bc7046fc70844The Android Open Source Project } 502049d6fea481044fcc000e7782e5bc7046fc70844The Android Open Source Project else 503049d6fea481044fcc000e7782e5bc7046fc70844The Android Open Source Project *abbox = bbox; 504049d6fea481044fcc000e7782e5bc7046fc70844The Android Open Source Project 505049d6fea481044fcc000e7782e5bc7046fc70844The Android Open Source Project return FT_Err_Ok; 506049d6fea481044fcc000e7782e5bc7046fc70844The Android Open Source Project } 507049d6fea481044fcc000e7782e5bc7046fc70844The Android Open Source Project 508049d6fea481044fcc000e7782e5bc7046fc70844The Android Open Source Project 509049d6fea481044fcc000e7782e5bc7046fc70844The Android Open Source Project/* END */ 510