1ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov/***************************************************************************/ 2ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov/* */ 3ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov/* ftbbox.c */ 4ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov/* */ 5ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov/* FreeType bbox computation (body). */ 6ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov/* */ 7ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov/* Copyright 1996-2002, 2004, 2006, 2010, 2013 by */ 8ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov/* David Turner, Robert Wilhelm, and Werner Lemberg. */ 9ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov/* */ 10ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov/* This file is part of the FreeType project, and may only be used */ 11ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov/* modified and distributed under the terms of the FreeType project */ 12ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov/* license, LICENSE.TXT. By continuing to use, modify, or distribute */ 13ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov/* this file you indicate that you have read the license and */ 14ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov/* understand and accept it fully. */ 15ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov/* */ 16ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov/***************************************************************************/ 17ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov 18ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov 19ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov /*************************************************************************/ 20ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov /* */ 21ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov /* This component has a _single_ role: to compute exact outline bounding */ 22ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov /* boxes. */ 23ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov /* */ 24ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov /*************************************************************************/ 25ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov 26ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov 27ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov#include "../../include/ft2build.h" 28ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov#include "../../include/freetype/internal/ftdebug.h" 29ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov 30ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov#include "../../include/freetype/ftbbox.h" 31ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov#include "../../include/freetype/ftimage.h" 32ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov#include "../../include/freetype/ftoutln.h" 33ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov#include "../../include/freetype/internal/ftcalc.h" 34ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov#include "../../include/freetype/internal/ftobjs.h" 35ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov 36ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov 37ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov typedef struct TBBox_Rec_ 38ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov { 39ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov FT_Vector last; 40ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov FT_BBox bbox; 41ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov 42ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov } TBBox_Rec; 43ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov 44ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov 45ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov /*************************************************************************/ 46ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov /* */ 47ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov /* <Function> */ 48ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov /* BBox_Move_To */ 49ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov /* */ 50ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov /* <Description> */ 51ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov /* This function is used as a `move_to' and `line_to' emitter during */ 52ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov /* FT_Outline_Decompose(). It simply records the destination point */ 53ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov /* in `user->last'; no further computations are necessary since we */ 54ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov /* use the cbox as the starting bbox which must be refined. */ 55ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov /* */ 56ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov /* <Input> */ 57ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov /* to :: A pointer to the destination vector. */ 58ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov /* */ 59ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov /* <InOut> */ 60ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov /* user :: A pointer to the current walk context. */ 61ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov /* */ 62ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov /* <Return> */ 63ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov /* Always 0. Needed for the interface only. */ 64ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov /* */ 65ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov static int 66ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov BBox_Move_To( FT_Vector* to, 67ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov TBBox_Rec* user ) 68ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov { 69ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov user->last = *to; 70ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov 71ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov return 0; 72ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov } 73ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov 74ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov 75ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov#define CHECK_X( p, bbox ) \ 76ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov ( p->x < bbox.xMin || p->x > bbox.xMax ) 77ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov 78ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov#define CHECK_Y( p, bbox ) \ 79ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov ( p->y < bbox.yMin || p->y > bbox.yMax ) 80ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov 81ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov 82ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov /*************************************************************************/ 83ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov /* */ 84ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov /* <Function> */ 85ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov /* BBox_Conic_Check */ 86ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov /* */ 87ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov /* <Description> */ 88ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov /* Finds the extrema of a 1-dimensional conic Bezier curve and update */ 89ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov /* a bounding range. This version uses direct computation, as it */ 90ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov /* doesn't need square roots. */ 91ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov /* */ 92ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov /* <Input> */ 93ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov /* y1 :: The start coordinate. */ 94ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov /* */ 95ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov /* y2 :: The coordinate of the control point. */ 96ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov /* */ 97ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov /* y3 :: The end coordinate. */ 98ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov /* */ 99ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov /* <InOut> */ 100ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov /* min :: The address of the current minimum. */ 101ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov /* */ 102ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov /* max :: The address of the current maximum. */ 103ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov /* */ 104ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov static void 105ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov BBox_Conic_Check( FT_Pos y1, 106ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov FT_Pos y2, 107ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov FT_Pos y3, 108ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov FT_Pos* min, 109ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov FT_Pos* max ) 110ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov { 111ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov if ( y1 <= y3 && y2 == y1 ) /* flat arc */ 112ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov goto Suite; 113ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov 114ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov if ( y1 < y3 ) 115ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov { 116ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov if ( y2 >= y1 && y2 <= y3 ) /* ascending arc */ 117ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov goto Suite; 118ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov } 119ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov else 120ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov { 121ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov if ( y2 >= y3 && y2 <= y1 ) /* descending arc */ 122ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov { 123ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov y2 = y1; 124ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov y1 = y3; 125ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov y3 = y2; 126ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov goto Suite; 127ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov } 128ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov } 129ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov 130ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov y1 = y3 = y1 - FT_MulDiv( y2 - y1, y2 - y1, y1 - 2*y2 + y3 ); 131ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov 132ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov Suite: 133ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov if ( y1 < *min ) *min = y1; 134ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov if ( y3 > *max ) *max = y3; 135ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov } 136ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov 137ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov 138ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov /*************************************************************************/ 139ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov /* */ 140ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov /* <Function> */ 141ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov /* BBox_Conic_To */ 142ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov /* */ 143ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov /* <Description> */ 144ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov /* This function is used as a `conic_to' emitter during */ 145ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov /* FT_Outline_Decompose(). It checks a conic Bezier curve with the */ 146ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov /* current bounding box, and computes its extrema if necessary to */ 147ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov /* update it. */ 148ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov /* */ 149ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov /* <Input> */ 150ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov /* control :: A pointer to a control point. */ 151ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov /* */ 152ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov /* to :: A pointer to the destination vector. */ 153ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov /* */ 154ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov /* <InOut> */ 155ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov /* user :: The address of the current walk context. */ 156ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov /* */ 157ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov /* <Return> */ 158ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov /* Always 0. Needed for the interface only. */ 159ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov /* */ 160ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov /* <Note> */ 161ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov /* In the case of a non-monotonous arc, we compute directly the */ 162ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov /* extremum coordinates, as it is sufficiently fast. */ 163ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov /* */ 164ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov static int 165ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov BBox_Conic_To( FT_Vector* control, 166ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov FT_Vector* to, 167ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov TBBox_Rec* user ) 168ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov { 169ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov /* we don't need to check `to' since it is always an `on' point, thus */ 170ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov /* within the bbox */ 171ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov 172ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov if ( CHECK_X( control, user->bbox ) ) 173ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov BBox_Conic_Check( user->last.x, 174ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov control->x, 175ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov to->x, 176ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov &user->bbox.xMin, 177ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov &user->bbox.xMax ); 178ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov 179ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov if ( CHECK_Y( control, user->bbox ) ) 180ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov BBox_Conic_Check( user->last.y, 181ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov control->y, 182ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov to->y, 183ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov &user->bbox.yMin, 184ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov &user->bbox.yMax ); 185ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov 186ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov user->last = *to; 187ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov 188ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov return 0; 189ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov } 190ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov 191ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov 192ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov /*************************************************************************/ 193ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov /* */ 194ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov /* <Function> */ 195ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov /* BBox_Cubic_Check */ 196ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov /* */ 197ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov /* <Description> */ 198ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov /* Finds the extrema of a 1-dimensional cubic Bezier curve and */ 199ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov /* updates a bounding range. This version uses splitting because we */ 200ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov /* don't want to use square roots and extra accuracy. */ 201ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov /* */ 202ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov /* <Input> */ 203ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov /* p1 :: The start coordinate. */ 204ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov /* */ 205ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov /* p2 :: The coordinate of the first control point. */ 206ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov /* */ 207ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov /* p3 :: The coordinate of the second control point. */ 208ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov /* */ 209ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov /* p4 :: The end coordinate. */ 210ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov /* */ 211ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov /* <InOut> */ 212ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov /* min :: The address of the current minimum. */ 213ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov /* */ 214ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov /* max :: The address of the current maximum. */ 215ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov /* */ 216ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov 217ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov#if 0 218ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov 219ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov static void 220ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov BBox_Cubic_Check( FT_Pos p1, 221ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov FT_Pos p2, 222ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov FT_Pos p3, 223ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov FT_Pos p4, 224ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov FT_Pos* min, 225ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov FT_Pos* max ) 226ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov { 227ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov FT_Pos q1, q2, q3, q4; 228ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov 229ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov 230ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov q1 = p1; 231ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov q2 = p2; 232ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov q3 = p3; 233ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov q4 = p4; 234ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov 235ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov /* for a conic segment to possibly reach new maximum */ 236ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov /* one of its off-points must be above the current value */ 237ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov while ( q2 > *max || q3 > *max ) 238ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov { 239ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov /* determine which half contains the maximum and split */ 240ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov if ( q1 + q2 > q3 + q4 ) /* first half */ 241ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov { 242ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov q4 = q4 + q3; 243ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov q3 = q3 + q2; 244ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov q2 = q2 + q1; 245ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov q4 = q4 + q3; 246ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov q3 = q3 + q2; 247ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov q4 = ( q4 + q3 ) / 8; 248ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov q3 = q3 / 4; 249ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov q2 = q2 / 2; 250ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov } 251ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov else /* second half */ 252ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov { 253ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov q1 = q1 + q2; 254ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov q2 = q2 + q3; 255ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov q3 = q3 + q4; 256ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov q1 = q1 + q2; 257ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov q2 = q2 + q3; 258ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov q1 = ( q1 + q2 ) / 8; 259ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov q2 = q2 / 4; 260ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov q3 = q3 / 2; 261ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov } 262ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov 263ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov /* check if either end reached the maximum */ 264ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov if ( q1 == q2 && q1 >= q3 ) 265ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov { 266ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov *max = q1; 267ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov break; 268ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov } 269ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov if ( q3 == q4 && q2 <= q4 ) 270ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov { 271ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov *max = q4; 272ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov break; 273ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov } 274ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov } 275ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov 276ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov q1 = p1; 277ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov q2 = p2; 278ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov q3 = p3; 279ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov q4 = p4; 280ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov 281ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov /* for a conic segment to possibly reach new minimum */ 282ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov /* one of its off-points must be below the current value */ 283ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov while ( q2 < *min || q3 < *min ) 284ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov { 285ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov /* determine which half contains the minimum and split */ 286ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov if ( q1 + q2 < q3 + q4 ) /* first half */ 287ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov { 288ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov q4 = q4 + q3; 289ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov q3 = q3 + q2; 290ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov q2 = q2 + q1; 291ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov q4 = q4 + q3; 292ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov q3 = q3 + q2; 293ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov q4 = ( q4 + q3 ) / 8; 294ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov q3 = q3 / 4; 295ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov q2 = q2 / 2; 296ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov } 297ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov else /* second half */ 298ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov { 299ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov q1 = q1 + q2; 300ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov q2 = q2 + q3; 301ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov q3 = q3 + q4; 302ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov q1 = q1 + q2; 303ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov q2 = q2 + q3; 304ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov q1 = ( q1 + q2 ) / 8; 305ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov q2 = q2 / 4; 306ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov q3 = q3 / 2; 307ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov } 308ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov 309ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov /* check if either end reached the minimum */ 310ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov if ( q1 == q2 && q1 <= q3 ) 311ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov { 312ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov *min = q1; 313ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov break; 314ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov } 315ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov if ( q3 == q4 && q2 >= q4 ) 316ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov { 317ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov *min = q4; 318ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov break; 319ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov } 320ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov } 321ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov } 322ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov 323ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov#else 324ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov 325ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov static void 326ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov test_cubic_extrema( FT_Pos y1, 327ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov FT_Pos y2, 328ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov FT_Pos y3, 329ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov FT_Pos y4, 330ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov FT_Fixed u, 331ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov FT_Pos* min, 332ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov FT_Pos* max ) 333ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov { 334ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov /* FT_Pos a = y4 - 3*y3 + 3*y2 - y1; */ 335ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov FT_Pos b = y3 - 2*y2 + y1; 336ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov FT_Pos c = y2 - y1; 337ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov FT_Pos d = y1; 338ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov FT_Pos y; 339ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov FT_Fixed uu; 340ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov 341ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov FT_UNUSED ( y4 ); 342ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov 343ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov 344ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov /* The polynomial is */ 345ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov /* */ 346ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov /* P(x) = a*x^3 + 3b*x^2 + 3c*x + d , */ 347ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov /* */ 348ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov /* dP/dx = 3a*x^2 + 6b*x + 3c . */ 349ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov /* */ 350ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov /* However, we also have */ 351ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov /* */ 352ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov /* dP/dx(u) = 0 , */ 353ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov /* */ 354ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov /* which implies by subtraction that */ 355ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov /* */ 356ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov /* P(u) = b*u^2 + 2c*u + d . */ 357ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov 358ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov if ( u > 0 && u < 0x10000L ) 359ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov { 360ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov uu = FT_MulFix( u, u ); 361ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov y = d + FT_MulFix( c, 2*u ) + FT_MulFix( b, uu ); 362ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov 363ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov if ( y < *min ) *min = y; 364ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov if ( y > *max ) *max = y; 365ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov } 366ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov } 367ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov 368ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov 369ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov static void 370ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov BBox_Cubic_Check( FT_Pos y1, 371ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov FT_Pos y2, 372ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov FT_Pos y3, 373ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov FT_Pos y4, 374ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov FT_Pos* min, 375ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov FT_Pos* max ) 376ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov { 377ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov /* always compare first and last points */ 378ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov if ( y1 < *min ) *min = y1; 379ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov else if ( y1 > *max ) *max = y1; 380ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov 381ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov if ( y4 < *min ) *min = y4; 382ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov else if ( y4 > *max ) *max = y4; 383ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov 384ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov /* now, try to see if there are split points here */ 385ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov if ( y1 <= y4 ) 386ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov { 387ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov /* flat or ascending arc test */ 388ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov if ( y1 <= y2 && y2 <= y4 && y1 <= y3 && y3 <= y4 ) 389ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov return; 390ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov } 391ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov else /* y1 > y4 */ 392ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov { 393ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov /* descending arc test */ 394ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov if ( y1 >= y2 && y2 >= y4 && y1 >= y3 && y3 >= y4 ) 395ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov return; 396ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov } 397ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov 398ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov /* There are some split points. Find them. */ 399ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov /* We already made sure that a, b, and c below cannot be all zero. */ 400ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov { 401ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov FT_Pos a = y4 - 3*y3 + 3*y2 - y1; 402ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov FT_Pos b = y3 - 2*y2 + y1; 403ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov FT_Pos c = y2 - y1; 404ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov FT_Pos d; 405ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov FT_Fixed t; 406ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov FT_Int shift; 407ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov 408ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov 409ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov /* We need to solve `ax^2+2bx+c' here, without floating points! */ 410ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov /* The trick is to normalize to a different representation in order */ 411ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov /* to use our 16.16 fixed-point routines. */ 412ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov /* */ 413ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov /* We compute FT_MulFix(b,b) and FT_MulFix(a,c) after normalization. */ 414ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov /* These values must fit into a single 16.16 value. */ 415ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov /* */ 416ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov /* We normalize a, b, and c to `8.16' fixed-point values to ensure */ 417ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov /* that their product is held in a `16.16' value including the sign. */ 418ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov /* Necessarily, we need to shift `a', `b', and `c' so that the most */ 419ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov /* significant bit of their absolute values is at position 22. */ 420ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov /* */ 421ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov /* This also means that we are using 23 bits of precision to compute */ 422ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov /* the zeros, independently of the range of the original polynomial */ 423ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov /* coefficients. */ 424ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov /* */ 425ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov /* This algorithm should ensure reasonably accurate values for the */ 426ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov /* zeros. Note that they are only expressed with 16 bits when */ 427ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov /* computing the extrema (the zeros need to be in 0..1 exclusive */ 428ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov /* to be considered part of the arc). */ 429ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov 430ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov shift = FT_MSB( FT_ABS( a ) | FT_ABS( b ) | FT_ABS( c ) ); 431ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov 432ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov if ( shift > 22 ) 433ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov { 434ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov shift -= 22; 435ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov 436ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov /* this loses some bits of precision, but we use 23 of them */ 437ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov /* for the computation anyway */ 438ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov a >>= shift; 439ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov b >>= shift; 440ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov c >>= shift; 441ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov } 442ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov else 443ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov { 444ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov shift = 22 - shift; 445ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov 446ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov a <<= shift; 447ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov b <<= shift; 448ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov c <<= shift; 449ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov } 450ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov 451ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov /* handle a == 0 */ 452ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov if ( a == 0 ) 453ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov { 454ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov if ( b != 0 ) 455ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov { 456ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov t = - FT_DivFix( c, b ) / 2; 457ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov test_cubic_extrema( y1, y2, y3, y4, t, min, max ); 458ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov } 459ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov } 460ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov else 461ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov { 462ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov /* solve the equation now */ 463ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov d = FT_MulFix( b, b ) - FT_MulFix( a, c ); 464ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov if ( d < 0 ) 465ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov return; 466ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov 467ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov if ( d == 0 ) 468ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov { 469ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov /* there is a single split point at -b/a */ 470ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov t = - FT_DivFix( b, a ); 471ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov test_cubic_extrema( y1, y2, y3, y4, t, min, max ); 472ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov } 473ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov else 474ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov { 475ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov /* there are two solutions; we need to filter them */ 476ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov d = FT_SqrtFixed( (FT_Int32)d ); 477ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov t = - FT_DivFix( b - d, a ); 478ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov test_cubic_extrema( y1, y2, y3, y4, t, min, max ); 479ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov 480ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov t = - FT_DivFix( b + d, a ); 481ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov test_cubic_extrema( y1, y2, y3, y4, t, min, max ); 482ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov } 483ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov } 484ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov } 485ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov } 486ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov 487ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov#endif 488ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov 489ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov 490ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov /*************************************************************************/ 491ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov /* */ 492ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov /* <Function> */ 493ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov /* BBox_Cubic_To */ 494ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov /* */ 495ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov /* <Description> */ 496ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov /* This function is used as a `cubic_to' emitter during */ 497ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov /* FT_Outline_Decompose(). It checks a cubic Bezier curve with the */ 498ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov /* current bounding box, and computes its extrema if necessary to */ 499ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov /* update it. */ 500ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov /* */ 501ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov /* <Input> */ 502ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov /* control1 :: A pointer to the first control point. */ 503ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov /* */ 504ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov /* control2 :: A pointer to the second control point. */ 505ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov /* */ 506ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov /* to :: A pointer to the destination vector. */ 507ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov /* */ 508ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov /* <InOut> */ 509ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov /* user :: The address of the current walk context. */ 510ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov /* */ 511ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov /* <Return> */ 512ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov /* Always 0. Needed for the interface only. */ 513ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov /* */ 514ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov /* <Note> */ 515ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov /* In the case of a non-monotonous arc, we don't compute directly */ 516ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov /* extremum coordinates, we subdivide instead. */ 517ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov /* */ 518ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov static int 519ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov BBox_Cubic_To( FT_Vector* control1, 520ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov FT_Vector* control2, 521ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov FT_Vector* to, 522ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov TBBox_Rec* user ) 523ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov { 524ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov /* we don't need to check `to' since it is always an `on' point, thus */ 525ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov /* within the bbox */ 526ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov 527ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov if ( CHECK_X( control1, user->bbox ) || 528ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov CHECK_X( control2, user->bbox ) ) 529ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov BBox_Cubic_Check( user->last.x, 530ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov control1->x, 531ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov control2->x, 532ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov to->x, 533ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov &user->bbox.xMin, 534ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov &user->bbox.xMax ); 535ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov 536ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov if ( CHECK_Y( control1, user->bbox ) || 537ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov CHECK_Y( control2, user->bbox ) ) 538ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov BBox_Cubic_Check( user->last.y, 539ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov control1->y, 540ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov control2->y, 541ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov to->y, 542ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov &user->bbox.yMin, 543ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov &user->bbox.yMax ); 544ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov 545ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov user->last = *to; 546ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov 547ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov return 0; 548ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov } 549ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov 550ee451cb395940862dad63c85adfe8f2fd55e864cSvet GanovFT_DEFINE_OUTLINE_FUNCS(bbox_interface, 551ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov (FT_Outline_MoveTo_Func) BBox_Move_To, 552ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov (FT_Outline_LineTo_Func) BBox_Move_To, 553ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov (FT_Outline_ConicTo_Func)BBox_Conic_To, 554ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov (FT_Outline_CubicTo_Func)BBox_Cubic_To, 555ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov 0, 0 556ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov ) 557ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov 558ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov /* documentation is in ftbbox.h */ 559ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov 560ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov FT_EXPORT_DEF( FT_Error ) 561ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov FT_Outline_Get_BBox( FT_Outline* outline, 562ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov FT_BBox *abbox ) 563ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov { 564ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov FT_BBox cbox; 565ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov FT_BBox bbox; 566ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov FT_Vector* vec; 567ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov FT_UShort n; 568ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov 569ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov 570ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov if ( !abbox ) 571ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov return FT_THROW( Invalid_Argument ); 572ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov 573ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov if ( !outline ) 574ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov return FT_THROW( Invalid_Outline ); 575ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov 576ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov /* if outline is empty, return (0,0,0,0) */ 577ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov if ( outline->n_points == 0 || outline->n_contours <= 0 ) 578ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov { 579ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov abbox->xMin = abbox->xMax = 0; 580ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov abbox->yMin = abbox->yMax = 0; 581ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov return 0; 582ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov } 583ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov 584ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov /* We compute the control box as well as the bounding box of */ 585ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov /* all `on' points in the outline. Then, if the two boxes */ 586ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov /* coincide, we exit immediately. */ 587ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov 588ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov vec = outline->points; 589ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov bbox.xMin = bbox.xMax = cbox.xMin = cbox.xMax = vec->x; 590ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov bbox.yMin = bbox.yMax = cbox.yMin = cbox.yMax = vec->y; 591ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov vec++; 592ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov 593ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov for ( n = 1; n < outline->n_points; n++ ) 594ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov { 595ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov FT_Pos x = vec->x; 596ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov FT_Pos y = vec->y; 597ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov 598ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov 599ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov /* update control box */ 600ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov if ( x < cbox.xMin ) cbox.xMin = x; 601ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov if ( x > cbox.xMax ) cbox.xMax = x; 602ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov 603ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov if ( y < cbox.yMin ) cbox.yMin = y; 604ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov if ( y > cbox.yMax ) cbox.yMax = y; 605ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov 606ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov if ( FT_CURVE_TAG( outline->tags[n] ) == FT_CURVE_TAG_ON ) 607ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov { 608ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov /* update bbox for `on' points only */ 609ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov if ( x < bbox.xMin ) bbox.xMin = x; 610ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov if ( x > bbox.xMax ) bbox.xMax = x; 611ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov 612ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov if ( y < bbox.yMin ) bbox.yMin = y; 613ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov if ( y > bbox.yMax ) bbox.yMax = y; 614ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov } 615ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov 616ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov vec++; 617ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov } 618ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov 619ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov /* test two boxes for equality */ 620ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov if ( cbox.xMin < bbox.xMin || cbox.xMax > bbox.xMax || 621ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov cbox.yMin < bbox.yMin || cbox.yMax > bbox.yMax ) 622ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov { 623ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov /* the two boxes are different, now walk over the outline to */ 624ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov /* get the Bezier arc extrema. */ 625ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov 626ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov FT_Error error; 627ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov TBBox_Rec user; 628ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov 629ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov#ifdef FT_CONFIG_OPTION_PIC 630ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov FT_Outline_Funcs bbox_interface; 631ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov Init_Class_bbox_interface(&bbox_interface); 632ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov#endif 633ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov 634ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov user.bbox = bbox; 635ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov 636ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov error = FT_Outline_Decompose( outline, &bbox_interface, &user ); 637ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov if ( error ) 638ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov return error; 639ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov 640ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov *abbox = user.bbox; 641ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov } 642ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov else 643ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov *abbox = bbox; 644ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov 645ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov return FT_Err_Ok; 646ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov } 647ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov 648ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov 649ee451cb395940862dad63c85adfe8f2fd55e864cSvet Ganov/* END */ 650