git.maemo.org Git - opencv/blob - cxcore/src/cxdrawing.cpp

   1 /*M///////////////////////////////////////////////////////////////////////////////////////
   2 //
   3 //  IMPORTANT: READ BEFORE DOWNLOADING, COPYING, INSTALLING OR USING.
   4 //
   5 //  By downloading, copying, installing or using the software you agree to this license.
   6 //  If you do not agree to this license, do not download, install,
   7 //  copy or use the software.
   8 //
   9 //
  10 //                        Intel License Agreement
  11 //                For Open Source Computer Vision Library
  12 //
  13 // Copyright (C) 2000, Intel Corporation, all rights reserved.
  14 // Third party copyrights are property of their respective owners.
  15 //
  16 // Redistribution and use in source and binary forms, with or without modification,
  17 // are permitted provided that the following conditions are met:
  18 //
  19 //   * Redistribution's of source code must retain the above copyright notice,
  20 //     this list of conditions and the following disclaimer.
  21 //
  22 //   * Redistribution's in binary form must reproduce the above copyright notice,
  23 //     this list of conditions and the following disclaimer in the documentation
  24 //     and/or other materials provided with the distribution.
  25 //
  26 //   * The name of Intel Corporation may not be used to endorse or promote products
  27 //     derived from this software without specific prior written permission.
  28 //
  29 // This software is provided by the copyright holders and contributors "as is" and
  30 // any express or implied warranties, including, but not limited to, the implied
  31 // warranties of merchantability and fitness for a particular purpose are disclaimed.
  32 // In no event shall the Intel Corporation or contributors be liable for any direct,
  33 // indirect, incidental, special, exemplary, or consequential damages
  34 // (including, but not limited to, procurement of substitute goods or services;
  35 // loss of use, data, or profits; or business interruption) however caused
  36 // and on any theory of liability, whether in contract, strict liability,
  37 // or tort (including negligence or otherwise) arising in any way out of
  38 // the use of this software, even if advised of the possibility of such damage.
  39 //
  40 //M*/
  41 #include "_cxcore.h"
  42
  43 #define  XY_SHIFT  16
  44 #define  XY_ONE    (1 << XY_SHIFT)
  45
  46 #define CV_DRAWING_STORAGE_BLOCK ((1 << 12) - 256)
  47
  48 typedef struct CvPolyEdge
  49 {
  50     int x, dx;
  51     union
  52     {
  53         struct CvPolyEdge *next;
  54         int y0;
  55     };
  56     int y1;
  57 }
  58 CvPolyEdge;
  59
  60 static void
  61 icvCollectPolyEdges( CvMat* img, CvSeq* v, CvContour* edges,
  62                      const void* color, int line_type,
  63                      int shift, CvPoint offset=cvPoint(0,0) );
  64
  65 static void
  66 icvFillEdgeCollection( CvMat* img, CvContour* edges, const void* color );
  67
  68 static void
  69 icvPolyLine( CvMat* img, CvPoint *v, int count, int closed,
  70              const void* color, int thickness, int line_type, int shift );
  71
  72 static void
  73 icvFillConvexPoly( CvMat* img, CvPoint* v, int npts,
  74                    const void* color, int line_type, int shift );
  75
  76 /****************************************************************************************\
  77 *                                   Lines                                                *
  78 \****************************************************************************************/
  79
  80 CV_IMPL int
  81 cvClipLine( CvSize img_size, CvPoint* pt1, CvPoint* pt2 )
  82 {
  83     int result = 0;
  84
  85     CV_FUNCNAME( "cvClipLine" );
  86
  87     __BEGIN__;
  88
  89     int x1, y1, x2, y2;
  90     int c1, c2;
  91     int right = img_size.width-1, bottom = img_size.height-1;
  92
  93     if( !pt1 || !pt2 )
  94         CV_ERROR( CV_StsNullPtr, "One of point pointers is NULL" );
  95
  96     if( right < 0 || bottom < 0 )
  97         CV_ERROR( CV_StsOutOfRange, "Image width or height are negative" );
  98
  99     x1 = pt1->x; y1 = pt1->y; x2 = pt2->x; y2 = pt2->y;
 100     c1 = (x1 < 0) + (x1 > right) * 2 + (y1 < 0) * 4 + (y1 > bottom) * 8;
 101     c2 = (x2 < 0) + (x2 > right) * 2 + (y2 < 0) * 4 + (y2 > bottom) * 8;
 102
 103     if( (c1 & c2) == 0 && (c1 | c2) != 0 )
 104     {
 105         int a;
 106
 107         if( c1 & 12 )
 108         {
 109             a = c1 < 8 ? 0 : bottom;
 110             x1 += (int) (((int64) (a - y1)) * (x2 - x1) / (y2 - y1));
 111             y1 = a;
 112             c1 = (x1 < 0) + (x1 > right) * 2;
 113         }
 114         if( c2 & 12 )
 115         {
 116             a = c2 < 8 ? 0 : bottom;
 117             x2 += (int) (((int64) (a - y2)) * (x2 - x1) / (y2 - y1));
 118             y2 = a;
 119             c2 = (x2 < 0) + (x2 > right) * 2;
 120         }
 121         if( (c1 & c2) == 0 && (c1 | c2) != 0 )
 122         {
 123             if( c1 )
 124             {
 125                 a = c1 == 1 ? 0 : right;
 126                 y1 += (int) (((int64) (a - x1)) * (y2 - y1) / (x2 - x1));
 127                 x1 = a;
 128                 c1 = 0;
 129             }
 130             if( c2 )
 131             {
 132                 a = c2 == 1 ? 0 : right;
 133                 y2 += (int) (((int64) (a - x2)) * (y2 - y1) / (x2 - x1));
 134                 x2 = a;
 135                 c2 = 0;
 136             }
 137         }
 138
 139         assert( (c1 & c2) != 0 || (x1 | y1 | x2 | y2) >= 0 );
 140
 141         pt1->x = x1;
 142         pt1->y = y1;
 143         pt2->x = x2;
 144         pt2->y = y2;
 145     }
 146
 147     result = ( c1 | c2 ) == 0;
 148
 149     __END__;
 150
 151     return result;
 152 }
 153
 154
 155 /*
 156    Initializes line iterator.
 157    Returns number of points on the line or negative number if error.
 158 */
 159 CV_IMPL int
 160 cvInitLineIterator( const CvArr* img, CvPoint pt1, CvPoint pt2,
 161                     CvLineIterator* iterator, int connectivity,
 162                     int left_to_right )
 163 {
 164     int count = -1;
 165
 166     CV_FUNCNAME( "cvInitLineIterator" );
 167
 168     __BEGIN__;
 169
 170     CvMat stub, *mat = (CvMat*)img;
 171     int dx, dy, s;
 172     int bt_pix, bt_pix0, step;
 173
 174     if( !CV_IS_MAT(mat) )
 175         CV_CALL( mat = cvGetMat( mat, &stub ));
 176
 177     if( !iterator )
 178         CV_ERROR( CV_StsNullPtr, "Pointer to the iterator state is NULL" );
 179
 180     if( connectivity != 8 && connectivity != 4 )
 181         CV_ERROR( CV_StsBadArg, "Connectivity must be 8 or 4" );
 182
 183     if( (unsigned)pt1.x >= (unsigned)(mat->width) ||
 184         (unsigned)pt2.x >= (unsigned)(mat->width) ||
 185         (unsigned)pt1.y >= (unsigned)(mat->height) ||
 186         (unsigned)pt2.y >= (unsigned)(mat->height) )
 187         CV_ERROR( CV_StsBadPoint,
 188             "One of the ending points is outside of the image, use cvClipLine" );
 189
 190     bt_pix0 = bt_pix = CV_ELEM_SIZE(mat->type);
 191     step = mat->step;
 192
 193     dx = pt2.x - pt1.x;
 194     dy = pt2.y - pt1.y;
 195     s = dx < 0 ? -1 : 0;
 196
 197     if( left_to_right )
 198     {
 199         dx = (dx ^ s) - s;
 200         dy = (dy ^ s) - s;
 201         pt1.x ^= (pt1.x ^ pt2.x) & s;
 202         pt1.y ^= (pt1.y ^ pt2.y) & s;
 203     }
 204     else
 205     {
 206         dx = (dx ^ s) - s;
 207         bt_pix = (bt_pix ^ s) - s;
 208     }
 209
 210     iterator->ptr = (uchar*)(mat->data.ptr + pt1.y * step + pt1.x * bt_pix0);
 211
 212     s = dy < 0 ? -1 : 0;
 213     dy = (dy ^ s) - s;
 214     step = (step ^ s) - s;
 215
 216     s = dy > dx ? -1 : 0;
 217
 218     /* conditional swaps */
 219     dx ^= dy & s;
 220     dy ^= dx & s;
 221     dx ^= dy & s;
 222
 223     bt_pix ^= step & s;
 224     step ^= bt_pix & s;
 225     bt_pix ^= step & s;
 226
 227     if( connectivity == 8 )
 228     {
 229         assert( dx >= 0 && dy >= 0 );
 230
 231         iterator->err = dx - (dy + dy);
 232         iterator->plus_delta = dx + dx;
 233         iterator->minus_delta = -(dy + dy);
 234         iterator->plus_step = step;
 235         iterator->minus_step = bt_pix;
 236         count = dx + 1;
 237     }
 238     else /* connectivity == 4 */
 239     {
 240         assert( dx >= 0 && dy >= 0 );
 241
 242         iterator->err = 0;
 243         iterator->plus_delta = (dx + dx) + (dy + dy);
 244         iterator->minus_delta = -(dy + dy);
 245         iterator->plus_step = step - bt_pix;
 246         iterator->minus_step = bt_pix;
 247         count = dx + dy + 1;
 248     }
 249
 250     __END__;
 251
 252     return count;
 253 }
 254
 255 static void
 256 icvLine( CvMat* mat, CvPoint pt1, CvPoint pt2,
 257          const void* color, int connectivity = 8 )
 258 {
 259     if( cvClipLine( cvGetMatSize(mat), &pt1, &pt2 ))
 260     {
 261         CvLineIterator iterator;
 262         int pix_size = CV_ELEM_SIZE(mat->type);
 263         int i, count;
 264
 265         if( connectivity == 0 )
 266             connectivity = 8;
 267         if( connectivity == 1 )
 268             connectivity = 4;
 269
 270         count = cvInitLineIterator( mat, pt1, pt2, &iterator, connectivity, 1 );
 271
 272         for( i = 0; i < count; i++ )
 273         {
 274             CV_MEMCPY_AUTO( iterator.ptr, color, pix_size );
 275             CV_NEXT_LINE_POINT( iterator );
 276         }
 277     }
 278 }
 279
 280
 281 /* Correction table depent on the slope */
 282 static const uchar icvSlopeCorrTable[] = {
 283     181, 181, 181, 182, 182, 183, 184, 185, 187, 188, 190, 192, 194, 196, 198, 201,
 284     203, 206, 209, 211, 214, 218, 221, 224, 227, 231, 235, 238, 242, 246, 250, 254
 285 };
 286
 287 /* Gaussian for antialiasing filter */
 288 static const int icvFilterTable[] = {
 289     168, 177, 185, 194, 202, 210, 218, 224, 231, 236, 241, 246, 249, 252, 254, 254,
 290     254, 254, 252, 249, 246, 241, 236, 231, 224, 218, 210, 202, 194, 185, 177, 168,
 291     158, 149, 140, 131, 122, 114, 105, 97, 89, 82, 75, 68, 62, 56, 50, 45,
 292     40, 36, 32, 28, 25, 22, 19, 16, 14, 12, 11, 9, 8, 7, 5, 5
 293 };
 294
 295 static void
 296 icvLineAA( CvMat* img, CvPoint pt1, CvPoint pt2,
 297            const void* color )
 298 {
 299     int dx, dy;
 300     int ecount, scount = 0;
 301     int slope;
 302     int ax, ay;
 303     int x_step, y_step;
 304     int i, j;
 305     int ep_table[9];
 306     int cb = ((uchar*)color)[0], cg = ((uchar*)color)[1], cr = ((uchar*)color)[2];
 307     int _cb, _cg, _cr;
 308     int nch = CV_MAT_CN( img->type );
 309     uchar* ptr = (uchar*)(img->data.ptr);
 310     int step = img->step;
 311     CvSize size = cvGetMatSize( img );
 312
 313     assert( img && (nch == 1 || nch == 3) && CV_MAT_DEPTH(img->type) == CV_8U );
 314
 315     pt1.x -= XY_ONE*2;
 316     pt1.y -= XY_ONE*2;
 317     pt2.x -= XY_ONE*2;
 318     pt2.y -= XY_ONE*2;
 319     ptr += img->step*2 + 2*nch;
 320
 321     size.width = ((size.width - 5) << XY_SHIFT) + 1;
 322     size.height = ((size.height - 5) << XY_SHIFT) + 1;
 323
 324     if( !cvClipLine( size, &pt1, &pt2 ))
 325         return;
 326
 327     dx = pt2.x - pt1.x;
 328     dy = pt2.y - pt1.y;
 329
 330     j = dx < 0 ? -1 : 0;
 331     ax = (dx ^ j) - j;
 332     i = dy < 0 ? -1 : 0;
 333     ay = (dy ^ i) - i;
 334
 335     if( ax > ay )
 336     {
 337         dx = ax;
 338         dy = (dy ^ j) - j;
 339         pt1.x ^= pt2.x & j;
 340         pt2.x ^= pt1.x & j;
 341         pt1.x ^= pt2.x & j;
 342         pt1.y ^= pt2.y & j;
 343         pt2.y ^= pt1.y & j;
 344         pt1.y ^= pt2.y & j;
 345
 346         x_step = XY_ONE;
 347         y_step = (int) (((int64) dy << XY_SHIFT) / (ax | 1));
 348         pt2.x += XY_ONE;
 349         ecount = (pt2.x >> XY_SHIFT) - (pt1.x >> XY_SHIFT);
 350         j = -(pt1.x & (XY_ONE - 1));
 351         pt1.y += (int) ((((int64) y_step) * j) >> XY_SHIFT) + (XY_ONE >> 1);
 352         slope = (y_step >> (XY_SHIFT - 5)) & 0x3f;
 353         slope ^= (y_step < 0 ? 0x3f : 0);
 354
 355         /* Get 4-bit fractions for end-point adjustments */
 356         i = (pt1.x >> (XY_SHIFT - 7)) & 0x78;
 357         j = (pt2.x >> (XY_SHIFT - 7)) & 0x78;
 358     }
 359     else
 360     {
 361         dy = ay;
 362         dx = (dx ^ i) - i;
 363         pt1.x ^= pt2.x & i;
 364         pt2.x ^= pt1.x & i;
 365         pt1.x ^= pt2.x & i;
 366         pt1.y ^= pt2.y & i;
 367         pt2.y ^= pt1.y & i;
 368         pt1.y ^= pt2.y & i;
 369
 370         x_step = (int) (((int64) dx << XY_SHIFT) / (ay | 1));
 371         y_step = XY_ONE;
 372         pt2.y += XY_ONE;
 373         ecount = (pt2.y >> XY_SHIFT) - (pt1.y >> XY_SHIFT);
 374         j = -(pt1.y & (XY_ONE - 1));
 375         pt1.x += (int) ((((int64) x_step) * j) >> XY_SHIFT) + (XY_ONE >> 1);
 376         slope = (x_step >> (XY_SHIFT - 5)) & 0x3f;
 377         slope ^= (x_step < 0 ? 0x3f : 0);
 378
 379         /* Get 4-bit fractions for end-point adjustments */
 380         i = (pt1.y >> (XY_SHIFT - 7)) & 0x78;
 381         j = (pt2.y >> (XY_SHIFT - 7)) & 0x78;
 382     }
 383
 384     slope = (slope & 0x20) ? 0x100 : icvSlopeCorrTable[slope];
 385
 386     /* Calc end point correction table */
 387     {
 388         int t0 = slope << 7;
 389         int t1 = ((0x78 - i) | 4) * slope;
 390         int t2 = (j | 4) * slope;
 391
 392         ep_table[0] = 0;
 393         ep_table[8] = slope;
 394         ep_table[1] = ep_table[3] = ((((j - i) & 0x78) | 4) * slope >> 8) & 0x1ff;
 395         ep_table[2] = (t1 >> 8) & 0x1ff;
 396         ep_table[4] = ((((j - i) + 0x80) | 4) * slope >> 8) & 0x1ff;
 397         ep_table[5] = ((t1 + t0) >> 8) & 0x1ff;
 398         ep_table[6] = (t2 >> 8) & 0x1ff;
 399         ep_table[7] = ((t2 + t0) >> 8) & 0x1ff;
 400     }
 401
 402     if( nch == 3 )
 403     {
 404         #define  ICV_PUT_POINT()            \
 405         {                                   \
 406             _cb = tptr[0];                  \
 407             _cb += ((cb - _cb)*a + 127)>> 8;\
 408             _cg = tptr[1];                  \
 409             _cg += ((cg - _cg)*a + 127)>> 8;\
 410             _cr = tptr[2];                  \
 411             _cr += ((cr - _cr)*a + 127)>> 8;\
 412             tptr[0] = (uchar)_cb;           \
 413             tptr[1] = (uchar)_cg;           \
 414             tptr[2] = (uchar)_cr;           \
 415         }
 416         if( ax > ay )
 417         {
 418             ptr += (pt1.x >> XY_SHIFT) * 3;
 419
 420             while( ecount >= 0 )
 421             {
 422                 uchar *tptr = ptr + ((pt1.y >> XY_SHIFT) - 1) * step;
 423
 424                 int ep_corr = ep_table[(((scount >= 2) + 1) & (scount | 2)) * 3 +
 425                                        (((ecount >= 2) + 1) & (ecount | 2))];
 426                 int a, dist = (pt1.y >> (XY_SHIFT - 5)) & 31;
 427
 428                 a = (ep_corr * icvFilterTable[dist + 32] >> 8) & 0xff;
 429                 ICV_PUT_POINT();
 430                 ICV_PUT_POINT();
 431
 432                 tptr += step;
 433                 a = (ep_corr * icvFilterTable[dist] >> 8) & 0xff;
 434                 ICV_PUT_POINT();
 435                 ICV_PUT_POINT();
 436
 437                 tptr += step;
 438                 a = (ep_corr * icvFilterTable[63 - dist] >> 8) & 0xff;
 439                 ICV_PUT_POINT();
 440                 ICV_PUT_POINT();
 441
 442                 pt1.y += y_step;
 443                 ptr += 3;
 444                 scount++;
 445                 ecount--;
 446             }
 447         }
 448         else
 449         {
 450             ptr += (pt1.y >> XY_SHIFT) * step;
 451
 452             while( ecount >= 0 )
 453             {
 454                 uchar *tptr = ptr + ((pt1.x >> XY_SHIFT) - 1) * 3;
 455
 456                 int ep_corr = ep_table[(((scount >= 2) + 1) & (scount | 2)) * 3 +
 457                                        (((ecount >= 2) + 1) & (ecount | 2))];
 458                 int a, dist = (pt1.x >> (XY_SHIFT - 5)) & 31;
 459
 460                 a = (ep_corr * icvFilterTable[dist + 32] >> 8) & 0xff;
 461                 ICV_PUT_POINT();
 462                 ICV_PUT_POINT();
 463
 464                 tptr += 3;
 465                 a = (ep_corr * icvFilterTable[dist] >> 8) & 0xff;
 466                 ICV_PUT_POINT();
 467                 ICV_PUT_POINT();
 468
 469                 tptr += 3;
 470                 a = (ep_corr * icvFilterTable[63 - dist] >> 8) & 0xff;
 471                 ICV_PUT_POINT();
 472                 ICV_PUT_POINT();
 473
 474                 pt1.x += x_step;
 475                 ptr += step;
 476                 scount++;
 477                 ecount--;
 478             }
 479         }
 480         #undef ICV_PUT_POINT
 481     }
 482     else
 483     {
 484         #define  ICV_PUT_POINT()            \
 485         {                                   \
 486             _cb = tptr[0];                  \
 487             _cb += ((cb - _cb)*a + 127)>> 8;\
 488             tptr[0] = (uchar)_cb;           \
 489         }
 490
 491         if( ax > ay )
 492         {
 493             ptr += (pt1.x >> XY_SHIFT);
 494
 495             while( ecount >= 0 )
 496             {
 497                 uchar *tptr = ptr + ((pt1.y >> XY_SHIFT) - 1) * step;
 498
 499                 int ep_corr = ep_table[(((scount >= 2) + 1) & (scount | 2)) * 3 +
 500                                        (((ecount >= 2) + 1) & (ecount | 2))];
 501                 int a, dist = (pt1.y >> (XY_SHIFT - 5)) & 31;
 502
 503                 a = (ep_corr * icvFilterTable[dist + 32] >> 8) & 0xff;
 504                 ICV_PUT_POINT();
 505                 ICV_PUT_POINT();
 506
 507                 tptr += step;
 508                 a = (ep_corr * icvFilterTable[dist] >> 8) & 0xff;
 509                 ICV_PUT_POINT();
 510                 ICV_PUT_POINT();
 511
 512                 tptr += step;
 513                 a = (ep_corr * icvFilterTable[63 - dist] >> 8) & 0xff;
 514                 ICV_PUT_POINT();
 515                 ICV_PUT_POINT();
 516
 517                 pt1.y += y_step;
 518                 ptr++;
 519                 scount++;
 520                 ecount--;
 521             }
 522         }
 523         else
 524         {
 525             ptr += (pt1.y >> XY_SHIFT) * step;
 526
 527             while( ecount >= 0 )
 528             {
 529                 uchar *tptr = ptr + ((pt1.x >> XY_SHIFT) - 1);
 530
 531                 int ep_corr = ep_table[(((scount >= 2) + 1) & (scount | 2)) * 3 +
 532                                        (((ecount >= 2) + 1) & (ecount | 2))];
 533                 int a, dist = (pt1.x >> (XY_SHIFT - 5)) & 31;
 534
 535                 a = (ep_corr * icvFilterTable[dist + 32] >> 8) & 0xff;
 536                 ICV_PUT_POINT();
 537                 ICV_PUT_POINT();
 538
 539                 tptr++;
 540                 a = (ep_corr * icvFilterTable[dist] >> 8) & 0xff;
 541                 ICV_PUT_POINT();
 542                 ICV_PUT_POINT();
 543
 544                 tptr++;
 545                 a = (ep_corr * icvFilterTable[63 - dist] >> 8) & 0xff;
 546                 ICV_PUT_POINT();
 547                 ICV_PUT_POINT();
 548
 549                 pt1.x += x_step;
 550                 ptr += step;
 551                 scount++;
 552                 ecount--;
 553             }
 554         }
 555         #undef ICV_PUT_POINT
 556     }
 557 }
 558
 559
 560 static void
 561 icvLine2( CvMat* img, CvPoint pt1, CvPoint pt2, const void* color )
 562 {
 563     int dx, dy;
 564     int ecount;
 565     int ax, ay;
 566     int i, j;
 567     int x_step, y_step;
 568     int cb = ((uchar*)color)[0];
 569     int cg = ((uchar*)color)[1];
 570     int cr = ((uchar*)color)[2];
 571     int pix_size = CV_ELEM_SIZE( img->type );
 572     uchar *ptr = (uchar*)(img->data.ptr), *tptr;
 573     int step = img->step;
 574     CvSize size = cvGetMatSize( img );
 575
 576     //assert( img && (nch == 1 || nch == 3) && CV_MAT_DEPTH(img->type) == CV_8U );
 577
 578     pt1.x -= XY_ONE*2;
 579     pt1.y -= XY_ONE*2;
 580     pt2.x -= XY_ONE*2;
 581     pt2.y -= XY_ONE*2;
 582     ptr += img->step*2 + 2*pix_size;
 583
 584     size.width = ((size.width - 5) << XY_SHIFT) + 1;
 585     size.height = ((size.height - 5) << XY_SHIFT) + 1;
 586
 587     if( !cvClipLine( size, &pt1, &pt2 ))
 588         return;
 589
 590     dx = pt2.x - pt1.x;
 591     dy = pt2.y - pt1.y;
 592
 593     j = dx < 0 ? -1 : 0;
 594     ax = (dx ^ j) - j;
 595     i = dy < 0 ? -1 : 0;
 596     ay = (dy ^ i) - i;
 597
 598     if( ax > ay )
 599     {
 600         dx = ax;
 601         dy = (dy ^ j) - j;
 602         pt1.x ^= pt2.x & j;
 603         pt2.x ^= pt1.x & j;
 604         pt1.x ^= pt2.x & j;
 605         pt1.y ^= pt2.y & j;
 606         pt2.y ^= pt1.y & j;
 607         pt1.y ^= pt2.y & j;
 608
 609         x_step = XY_ONE;
 610         y_step = (int) (((int64) dy << XY_SHIFT) / (ax | 1));
 611         ecount = (pt2.x - pt1.x) >> XY_SHIFT;
 612     }
 613     else
 614     {
 615         dy = ay;
 616         dx = (dx ^ i) - i;
 617         pt1.x ^= pt2.x & i;
 618         pt2.x ^= pt1.x & i;
 619         pt1.x ^= pt2.x & i;
 620         pt1.y ^= pt2.y & i;
 621         pt2.y ^= pt1.y & i;
 622         pt1.y ^= pt2.y & i;
 623
 624         x_step = (int) (((int64) dx << XY_SHIFT) / (ay | 1));
 625         y_step = XY_ONE;
 626         ecount = (pt2.y - pt1.y) >> XY_SHIFT;
 627     }
 628
 629     pt1.x += (XY_ONE >> 1);
 630     pt1.y += (XY_ONE >> 1);
 631
 632     if( pix_size == 3 )
 633     {
 634         #define  ICV_PUT_POINT()    \
 635         {                           \
 636             tptr[0] = (uchar)cb;    \
 637             tptr[1] = (uchar)cg;    \
 638             tptr[2] = (uchar)cr;    \
 639         }
 640
 641         tptr = ptr + ((pt2.x + (XY_ONE >> 1))>> XY_SHIFT)*3 +
 642             ((pt2.y + (XY_ONE >> 1)) >> XY_SHIFT)*step;
 643         ICV_PUT_POINT();
 644
 645         if( ax > ay )
 646         {
 647             ptr += (pt1.x >> XY_SHIFT) * 3;
 648
 649             while( ecount >= 0 )
 650             {
 651                 tptr = ptr + (pt1.y >> XY_SHIFT) * step;
 652                 ICV_PUT_POINT();
 653                 pt1.y += y_step;
 654                 ptr += 3;
 655                 ecount--;
 656             }
 657         }
 658         else
 659         {
 660             ptr += (pt1.y >> XY_SHIFT) * step;
 661
 662             while( ecount >= 0 )
 663             {
 664                 tptr = ptr + (pt1.x >> XY_SHIFT) * 3;
 665                 ICV_PUT_POINT();
 666                 pt1.x += x_step;
 667                 ptr += step;
 668                 ecount--;
 669             }
 670         }
 671
 672         #undef ICV_PUT_POINT
 673     }
 674     else if( pix_size == 1 )
 675     {
 676         #define  ICV_PUT_POINT()            \
 677         {                                   \
 678             tptr[0] = (uchar)cb;            \
 679         }
 680
 681         tptr = ptr + ((pt2.x + (XY_ONE >> 1))>> XY_SHIFT) +
 682             ((pt2.y + (XY_ONE >> 1)) >> XY_SHIFT)*step;
 683         ICV_PUT_POINT();
 684
 685         if( ax > ay )
 686         {
 687             ptr += (pt1.x >> XY_SHIFT);
 688
 689             while( ecount >= 0 )
 690             {
 691                 tptr = ptr + (pt1.y >> XY_SHIFT) * step;
 692                 ICV_PUT_POINT();
 693                 pt1.y += y_step;
 694                 ptr++;
 695                 ecount--;
 696             }
 697         }
 698         else
 699         {
 700             ptr += (pt1.y >> XY_SHIFT) * step;
 701
 702             while( ecount >= 0 )
 703             {
 704                 tptr = ptr + (pt1.x >> XY_SHIFT);
 705                 ICV_PUT_POINT();
 706                 pt1.x += x_step;
 707                 ptr += step;
 708                 ecount--;
 709             }
 710         }
 711         #undef ICV_PUT_POINT
 712     }
 713     else
 714     {
 715         #define  ICV_PUT_POINT()                \
 716             for( j = 0; j < pix_size; j++ )     \
 717                 tptr[j] = ((uchar*)color)[j];
 718
 719         tptr = ptr + ((pt2.x + (XY_ONE >> 1))>> XY_SHIFT)*pix_size +
 720             ((pt2.y + (XY_ONE >> 1)) >> XY_SHIFT)*step;
 721         ICV_PUT_POINT();
 722
 723         if( ax > ay )
 724         {
 725             ptr += (pt1.x >> XY_SHIFT) * pix_size;
 726
 727             while( ecount >= 0 )
 728             {
 729                 tptr = ptr + (pt1.y >> XY_SHIFT) * step;
 730                 ICV_PUT_POINT();
 731                 pt1.y += y_step;
 732                 ptr += pix_size;
 733                 ecount--;
 734             }
 735         }
 736         else
 737         {
 738             ptr += (pt1.y >> XY_SHIFT) * step;
 739
 740             while( ecount >= 0 )
 741             {
 742                 tptr = ptr + (pt1.x >> XY_SHIFT) * pix_size;
 743                 ICV_PUT_POINT();
 744                 pt1.x += x_step;
 745                 ptr += step;
 746                 ecount--;
 747             }
 748         }
 749
 750         #undef ICV_PUT_POINT
 751     }
 752 }
 753
 754
 755 /****************************************************************************************\
 756 *                   Antialiazed Elliptic Arcs via Antialiazed Lines                      *
 757 \****************************************************************************************/
 758
 759 static const float icvSinTable[] =
 760     { 0.0000000f, 0.0174524f, 0.0348995f, 0.0523360f, 0.0697565f, 0.0871557f,
 761     0.1045285f, 0.1218693f, 0.1391731f, 0.1564345f, 0.1736482f, 0.1908090f,
 762     0.2079117f, 0.2249511f, 0.2419219f, 0.2588190f, 0.2756374f, 0.2923717f,
 763     0.3090170f, 0.3255682f, 0.3420201f, 0.3583679f, 0.3746066f, 0.3907311f,
 764     0.4067366f, 0.4226183f, 0.4383711f, 0.4539905f, 0.4694716f, 0.4848096f,
 765     0.5000000f, 0.5150381f, 0.5299193f, 0.5446390f, 0.5591929f, 0.5735764f,
 766     0.5877853f, 0.6018150f, 0.6156615f, 0.6293204f, 0.6427876f, 0.6560590f,
 767     0.6691306f, 0.6819984f, 0.6946584f, 0.7071068f, 0.7193398f, 0.7313537f,
 768     0.7431448f, 0.7547096f, 0.7660444f, 0.7771460f, 0.7880108f, 0.7986355f,
 769     0.8090170f, 0.8191520f, 0.8290376f, 0.8386706f, 0.8480481f, 0.8571673f,
 770     0.8660254f, 0.8746197f, 0.8829476f, 0.8910065f, 0.8987940f, 0.9063078f,
 771     0.9135455f, 0.9205049f, 0.9271839f, 0.9335804f, 0.9396926f, 0.9455186f,
 772     0.9510565f, 0.9563048f, 0.9612617f, 0.9659258f, 0.9702957f, 0.9743701f,
 773     0.9781476f, 0.9816272f, 0.9848078f, 0.9876883f, 0.9902681f, 0.9925462f,
 774     0.9945219f, 0.9961947f, 0.9975641f, 0.9986295f, 0.9993908f, 0.9998477f,
 775     1.0000000f, 0.9998477f, 0.9993908f, 0.9986295f, 0.9975641f, 0.9961947f,
 776     0.9945219f, 0.9925462f, 0.9902681f, 0.9876883f, 0.9848078f, 0.9816272f,
 777     0.9781476f, 0.9743701f, 0.9702957f, 0.9659258f, 0.9612617f, 0.9563048f,
 778     0.9510565f, 0.9455186f, 0.9396926f, 0.9335804f, 0.9271839f, 0.9205049f,
 779     0.9135455f, 0.9063078f, 0.8987940f, 0.8910065f, 0.8829476f, 0.8746197f,
 780     0.8660254f, 0.8571673f, 0.8480481f, 0.8386706f, 0.8290376f, 0.8191520f,
 781     0.8090170f, 0.7986355f, 0.7880108f, 0.7771460f, 0.7660444f, 0.7547096f,
 782     0.7431448f, 0.7313537f, 0.7193398f, 0.7071068f, 0.6946584f, 0.6819984f,
 783     0.6691306f, 0.6560590f, 0.6427876f, 0.6293204f, 0.6156615f, 0.6018150f,
 784     0.5877853f, 0.5735764f, 0.5591929f, 0.5446390f, 0.5299193f, 0.5150381f,
 785     0.5000000f, 0.4848096f, 0.4694716f, 0.4539905f, 0.4383711f, 0.4226183f,
 786     0.4067366f, 0.3907311f, 0.3746066f, 0.3583679f, 0.3420201f, 0.3255682f,
 787     0.3090170f, 0.2923717f, 0.2756374f, 0.2588190f, 0.2419219f, 0.2249511f,
 788     0.2079117f, 0.1908090f, 0.1736482f, 0.1564345f, 0.1391731f, 0.1218693f,
 789     0.1045285f, 0.0871557f, 0.0697565f, 0.0523360f, 0.0348995f, 0.0174524f,
 790     0.0000000f, -0.0174524f, -0.0348995f, -0.0523360f, -0.0697565f, -0.0871557f,
 791     -0.1045285f, -0.1218693f, -0.1391731f, -0.1564345f, -0.1736482f, -0.1908090f,
 792     -0.2079117f, -0.2249511f, -0.2419219f, -0.2588190f, -0.2756374f, -0.2923717f,
 793     -0.3090170f, -0.3255682f, -0.3420201f, -0.3583679f, -0.3746066f, -0.3907311f,
 794     -0.4067366f, -0.4226183f, -0.4383711f, -0.4539905f, -0.4694716f, -0.4848096f,
 795     -0.5000000f, -0.5150381f, -0.5299193f, -0.5446390f, -0.5591929f, -0.5735764f,
 796     -0.5877853f, -0.6018150f, -0.6156615f, -0.6293204f, -0.6427876f, -0.6560590f,
 797     -0.6691306f, -0.6819984f, -0.6946584f, -0.7071068f, -0.7193398f, -0.7313537f,
 798     -0.7431448f, -0.7547096f, -0.7660444f, -0.7771460f, -0.7880108f, -0.7986355f,
 799     -0.8090170f, -0.8191520f, -0.8290376f, -0.8386706f, -0.8480481f, -0.8571673f,
 800     -0.8660254f, -0.8746197f, -0.8829476f, -0.8910065f, -0.8987940f, -0.9063078f,
 801     -0.9135455f, -0.9205049f, -0.9271839f, -0.9335804f, -0.9396926f, -0.9455186f,
 802     -0.9510565f, -0.9563048f, -0.9612617f, -0.9659258f, -0.9702957f, -0.9743701f,
 803     -0.9781476f, -0.9816272f, -0.9848078f, -0.9876883f, -0.9902681f, -0.9925462f,
 804     -0.9945219f, -0.9961947f, -0.9975641f, -0.9986295f, -0.9993908f, -0.9998477f,
 805     -1.0000000f, -0.9998477f, -0.9993908f, -0.9986295f, -0.9975641f, -0.9961947f,
 806     -0.9945219f, -0.9925462f, -0.9902681f, -0.9876883f, -0.9848078f, -0.9816272f,
 807     -0.9781476f, -0.9743701f, -0.9702957f, -0.9659258f, -0.9612617f, -0.9563048f,
 808     -0.9510565f, -0.9455186f, -0.9396926f, -0.9335804f, -0.9271839f, -0.9205049f,
 809     -0.9135455f, -0.9063078f, -0.8987940f, -0.8910065f, -0.8829476f, -0.8746197f,
 810     -0.8660254f, -0.8571673f, -0.8480481f, -0.8386706f, -0.8290376f, -0.8191520f,
 811     -0.8090170f, -0.7986355f, -0.7880108f, -0.7771460f, -0.7660444f, -0.7547096f,
 812     -0.7431448f, -0.7313537f, -0.7193398f, -0.7071068f, -0.6946584f, -0.6819984f,
 813     -0.6691306f, -0.6560590f, -0.6427876f, -0.6293204f, -0.6156615f, -0.6018150f,
 814     -0.5877853f, -0.5735764f, -0.5591929f, -0.5446390f, -0.5299193f, -0.5150381f,
 815     -0.5000000f, -0.4848096f, -0.4694716f, -0.4539905f, -0.4383711f, -0.4226183f,
 816     -0.4067366f, -0.3907311f, -0.3746066f, -0.3583679f, -0.3420201f, -0.3255682f,
 817     -0.3090170f, -0.2923717f, -0.2756374f, -0.2588190f, -0.2419219f, -0.2249511f,
 818     -0.2079117f, -0.1908090f, -0.1736482f, -0.1564345f, -0.1391731f, -0.1218693f,
 819     -0.1045285f, -0.0871557f, -0.0697565f, -0.0523360f, -0.0348995f, -0.0174524f,
 820     -0.0000000f, 0.0174524f, 0.0348995f, 0.0523360f, 0.0697565f, 0.0871557f,
 821     0.1045285f, 0.1218693f, 0.1391731f, 0.1564345f, 0.1736482f, 0.1908090f,
 822     0.2079117f, 0.2249511f, 0.2419219f, 0.2588190f, 0.2756374f, 0.2923717f,
 823     0.3090170f, 0.3255682f, 0.3420201f, 0.3583679f, 0.3746066f, 0.3907311f,
 824     0.4067366f, 0.4226183f, 0.4383711f, 0.4539905f, 0.4694716f, 0.4848096f,
 825     0.5000000f, 0.5150381f, 0.5299193f, 0.5446390f, 0.5591929f, 0.5735764f,
 826     0.5877853f, 0.6018150f, 0.6156615f, 0.6293204f, 0.6427876f, 0.6560590f,
 827     0.6691306f, 0.6819984f, 0.6946584f, 0.7071068f, 0.7193398f, 0.7313537f,
 828     0.7431448f, 0.7547096f, 0.7660444f, 0.7771460f, 0.7880108f, 0.7986355f,
 829     0.8090170f, 0.8191520f, 0.8290376f, 0.8386706f, 0.8480481f, 0.8571673f,
 830     0.8660254f, 0.8746197f, 0.8829476f, 0.8910065f, 0.8987940f, 0.9063078f,
 831     0.9135455f, 0.9205049f, 0.9271839f, 0.9335804f, 0.9396926f, 0.9455186f,
 832     0.9510565f, 0.9563048f, 0.9612617f, 0.9659258f, 0.9702957f, 0.9743701f,
 833     0.9781476f, 0.9816272f, 0.9848078f, 0.9876883f, 0.9902681f, 0.9925462f,
 834     0.9945219f, 0.9961947f, 0.9975641f, 0.9986295f, 0.9993908f, 0.9998477f,
 835     1.0000000f
 836 };
 837
 838
 839 static void
 840 icvSinCos( int angle, float *cosval, float *sinval )
 841 {
 842     angle += (angle < 0 ? 360 : 0);
 843     *sinval = icvSinTable[angle];
 844     *cosval = icvSinTable[450 - angle];
 845 }
 846
 847 /*
 848    constructs polygon that represents elliptic arc.
 849 */
 850 CV_IMPL int
 851 cvEllipse2Poly( CvPoint center, CvSize axes, int angle,
 852                 int arc_start, int arc_end, CvPoint* pts, int delta )
 853 {
 854     float alpha, beta;
 855     double size_a = axes.width, size_b = axes.height;
 856     double cx = center.x, cy = center.y;
 857     CvPoint *pts_origin = pts;
 858     int i;
 859
 860     while( angle < 0 )
 861         angle += 360;
 862     while( angle > 360 )
 863         angle -= 360;
 864
 865     if( arc_start > arc_end )
 866     {
 867         i = arc_start;
 868         arc_start = arc_end;
 869         arc_end = i;
 870     }
 871     while( arc_start < 0 )
 872     {
 873         arc_start += 360;
 874         arc_end += 360;
 875     }
 876     while( arc_end > 360 )
 877     {
 878         arc_end -= 360;
 879         arc_start -= 360;
 880     }
 881     if( arc_end - arc_start > 360 )
 882     {
 883         arc_start = 0;
 884         arc_end = 360;
 885     }
 886     icvSinCos( angle, &alpha, &beta );
 887
 888     for( i = arc_start; i < arc_end + delta; i += delta )
 889     {
 890         double x, y;
 891         angle = i;
 892         if( angle > arc_end )
 893             angle = arc_end;
 894         if( angle < 0 )
 895             angle += 360;
 896
 897         x = size_a * icvSinTable[450-angle];
 898         y = size_b * icvSinTable[angle];
 899         pts->x = cvRound( cx + x * alpha - y * beta );
 900         pts->y = cvRound( cy - x * beta - y * alpha );
 901         pts += i == arc_start || pts->x != pts[-1].x || pts->y != pts[-1].y;
 902     }
 903
 904     i = (int)(pts - pts_origin);
 905     for( ; i < 2; i++ )
 906         pts_origin[i] = pts_origin[i-1];
 907     return i;
 908 }
 909
 910
 911 static void
 912 icvEllipseEx( CvMat* img, CvPoint center, CvSize axes,
 913               int angle, int arc_start, int arc_end,
 914               const void* color, int thickness, int line_type )
 915 {
 916     CvMemStorage* st = 0;
 917
 918     CV_FUNCNAME( "icvEllipseEx" );
 919
 920     __BEGIN__;
 921
 922     CvPoint v[1 << 8];
 923     int count, delta;
 924
 925     if( axes.width < 0 || axes.height < 0 )
 926         CV_ERROR( CV_StsBadSize, "" );
 927
 928     delta = (MAX(axes.width,axes.height)+(XY_ONE>>1))>>XY_SHIFT;
 929     delta = delta < 3 ? 90 : delta < 10 ? 30 : delta < 15 ? 18 : 5;
 930
 931     count = cvEllipse2Poly( center, axes, angle, arc_start, arc_end, v, delta );
 932
 933     if( thickness >= 0 )
 934     {
 935         icvPolyLine( img, v, count, 0, color, thickness, line_type, XY_SHIFT );
 936     }
 937     else if( arc_end - arc_start >= 360 )
 938     {
 939         icvFillConvexPoly( img, v, count, color, line_type, XY_SHIFT );
 940     }
 941     else
 942     {
 943         CvContour* edges;
 944         CvSeq vtx;
 945         CvSeqBlock block;
 946
 947         CV_CALL( st = cvCreateMemStorage( CV_DRAWING_STORAGE_BLOCK ));
 948         CV_CALL( edges = (CvContour*)cvCreateSeq( 0, sizeof(CvContour), sizeof(CvPolyEdge), st ));
 949         v[count++] = center;
 950
 951         CV_CALL( cvMakeSeqHeaderForArray( CV_32SC2, sizeof(CvSeq), sizeof(CvPoint),
 952                                           v, count, &vtx, &block ));
 953
 954         CV_CALL( icvCollectPolyEdges( img, &vtx, edges, color, line_type, XY_SHIFT ));
 955         CV_CALL( icvFillEdgeCollection( img, edges, color ));
 956     }
 957
 958     __END__;
 959
 960     if( st )
 961         cvReleaseMemStorage( &st );
 962 }
 963
 964
 965 /****************************************************************************************\
 966 *                                Polygons filling                                        *
 967 \****************************************************************************************/
 968
 969 /* helper macros: filling horizontal row */
 970 #define ICV_HLINE( ptr, xl, xr, color, pix_size )            \
 971 {                                                            \
 972     uchar* hline_ptr = (uchar*)(ptr) + (xl)*(pix_size);      \
 973     uchar* hline_max_ptr = (uchar*)(ptr) + (xr)*(pix_size);  \
 974                                                              \
 975     for( ; hline_ptr <= hline_max_ptr; hline_ptr += (pix_size))\
 976     {                                                        \
 977         int hline_j;                                         \
 978         for( hline_j = 0; hline_j < (pix_size); hline_j++ )  \
 979         {                                                    \
 980             hline_ptr[hline_j] = ((uchar*)color)[hline_j];   \
 981         }                                                    \
 982     }                                                        \
 983 }
 984
 985
 986 /* filling convex polygon. v - array of vertices, ntps - number of points */
 987 static void
 988 icvFillConvexPoly( CvMat* img, CvPoint *v, int npts, const void* color, int line_type, int shift )
 989 {
 990     struct
 991     {
 992         int idx, di;
 993         int x, dx, ye;
 994     }
 995     edge[2];
 996
 997     int delta = shift ? 1 << (shift - 1) : 0;
 998     int i, y, imin = 0, left = 0, right = 1, x1, x2;
 999     int edges = npts;
1000     int xmin, xmax, ymin, ymax;
1001     uchar* ptr = img->data.ptr;
1002     CvSize size = cvGetMatSize( img );
1003     int pix_size = CV_ELEM_SIZE(img->type);
1004     CvPoint p0;
1005     int delta1, delta2;
1006
1007     if( line_type < CV_AA )
1008         delta1 = delta2 = XY_ONE >> 1;
1009         //delta1 = 0, delta2 = XY_ONE - 1;
1010     else
1011         delta1 = XY_ONE - 1, delta2 = 0;
1012
1013     p0 = v[npts - 1];
1014     p0.x <<= XY_SHIFT - shift;
1015     p0.y <<= XY_SHIFT - shift;
1016
1017     assert( 0 <= shift && shift <= XY_SHIFT );
1018     xmin = xmax = v[0].x;
1019     ymin = ymax = v[0].y;
1020
1021     for( i = 0; i < npts; i++ )
1022     {
1023         CvPoint p = v[i];
1024         if( p.y < ymin )
1025         {
1026             ymin = p.y;
1027             imin = i;
1028         }
1029
1030         ymax = MAX( ymax, p.y );
1031         xmax = MAX( xmax, p.x );
1032         xmin = MIN( xmin, p.x );
1033
1034         p.x <<= XY_SHIFT - shift;
1035         p.y <<= XY_SHIFT - shift;
1036
1037         if( line_type <= 8 )
1038         {
1039             if( shift == 0 )
1040             {
1041                 CvPoint pt0, pt1;
1042                 pt0.x = p0.x >> XY_SHIFT;
1043                 pt0.y = p0.y >> XY_SHIFT;
1044                 pt1.x = p.x >> XY_SHIFT;
1045                 pt1.y = p.y >> XY_SHIFT;
1046                 icvLine( img, pt0, pt1, color, line_type );
1047             }
1048             else
1049                 icvLine2( img, p0, p, color );
1050         }
1051         else
1052             icvLineAA( img, p0, p, color );
1053         p0 = p;
1054     }
1055
1056     xmin = (xmin + delta) >> shift;
1057     xmax = (xmax + delta) >> shift;
1058     ymin = (ymin + delta) >> shift;
1059     ymax = (ymax + delta) >> shift;
1060
1061     if( npts < 3 || xmax < 0 || ymax < 0 || xmin >= size.width || ymin >= size.height )
1062         return;
1063
1064     ymax = MIN( ymax, size.height - 1 );
1065     edge[0].idx = edge[1].idx = imin;
1066
1067     edge[0].ye = edge[1].ye = y = ymin;
1068     edge[0].di = 1;
1069     edge[1].di = npts - 1;
1070
1071     ptr += img->step*y;
1072
1073     do
1074     {
1075         if( line_type < CV_AA || y < ymax || y == ymin )
1076         {
1077             for( i = 0; i < 2; i++ )
1078             {
1079                 if( y >= edge[i].ye )
1080                 {
1081                     int idx = edge[i].idx, di = edge[i].di;
1082                     int xs = 0, xe, ye, ty = 0;
1083
1084                     for(;;)
1085                     {
1086                         ty = (v[idx].y + delta) >> shift;
1087                         if( ty > y || edges == 0 )
1088                             break;
1089                         xs = v[idx].x;
1090                         idx += di;
1091                         idx -= ((idx < npts) - 1) & npts;   /* idx -= idx >= npts ? npts : 0 */
1092                         edges--;
1093                     }
1094
1095                     ye = ty;
1096                     xs <<= XY_SHIFT - shift;
1097                     xe = v[idx].x << (XY_SHIFT - shift);
1098
1099                     /* no more edges */
1100                     if( y >= ye )
1101                         return;
1102
1103                     edge[i].ye = ye;
1104                     edge[i].dx = ((xe - xs)*2 + (ye - y)) / (2 * (ye - y));
1105                     edge[i].x = xs;
1106                     edge[i].idx = idx;
1107                 }
1108             }
1109         }
1110
1111         if( edge[left].x > edge[right].x )
1112         {
1113             left ^= 1;
1114             right ^= 1;
1115         }
1116
1117         x1 = edge[left].x;
1118         x2 = edge[right].x;
1119
1120         if( y >= 0 )
1121         {
1122             int xx1 = (x1 + delta1) >> XY_SHIFT;
1123             int xx2 = (x2 + delta2) >> XY_SHIFT;
1124
1125             if( xx2 >= 0 && xx1 < size.width )
1126             {
1127                 if( xx1 < 0 )
1128                     xx1 = 0;
1129                 if( xx2 >= size.width )
1130                     xx2 = size.width - 1;
1131                 ICV_HLINE( ptr, xx1, xx2, color, pix_size );
1132             }
1133         }
1134
1135         x1 += edge[left].dx;
1136         x2 += edge[right].dx;
1137
1138         edge[left].x = x1;
1139         edge[right].x = x2;
1140         ptr += img->step;
1141     }
1142     while( ++y <= ymax );
1143 }
1144
1145
1146 /******** Arbitrary polygon **********/
1147
1148 static void
1149 icvCollectPolyEdges( CvMat* img, CvSeq* v, CvContour* edges,
1150                      const void* color, int line_type, int shift,
1151                      CvPoint offset )
1152 {
1153     int  i, count = v->total;
1154     CvRect bounds = edges->rect;
1155     int delta = offset.y + (shift ? 1 << (shift - 1) : 0);
1156     int elem_type = CV_MAT_TYPE(v->flags);
1157
1158     CvSeqReader reader;
1159     CvSeqWriter writer;
1160
1161     cvStartReadSeq( v, &reader );
1162     cvStartAppendToSeq( (CvSeq*)edges, &writer );
1163
1164     for( i = 0; i < count; i++ )
1165     {
1166         CvPoint pt0, pt1, t0, t1;
1167         CvPolyEdge edge;
1168         CV_READ_EDGE( pt0, pt1, reader );
1169
1170         if( elem_type == CV_32SC2 )
1171         {
1172             pt0.x = (pt0.x + offset.x) << (XY_SHIFT - shift);
1173             pt0.y = (pt0.y + delta) >> shift;
1174             pt1.x = (pt1.x + offset.x) << (XY_SHIFT - shift);
1175             pt1.y = (pt1.y + delta) >> shift;
1176         }
1177         else
1178         {
1179             Cv32suf x, y;
1180             assert( shift == 0 );
1181
1182             x.i = pt0.x; y.i = pt0.y;
1183             pt0.x = cvRound((x.f + offset.x) * XY_ONE);
1184             pt0.y = cvRound(y.f + offset.y);
1185             x.i = pt1.x; y.i = pt1.y;
1186             pt1.x = cvRound((x.f + offset.x) * XY_ONE);
1187             pt1.y = cvRound(y.f + offset.y);
1188         }
1189
1190         if( line_type < CV_AA )
1191         {
1192             t0.y = pt0.y; t1.y = pt1.y;
1193             t0.x = (pt0.x + (XY_ONE >> 1)) >> XY_SHIFT;
1194             t1.x = (pt1.x + (XY_ONE >> 1)) >> XY_SHIFT;
1195             icvLine( img, t0, t1, color, line_type );
1196         }
1197         else
1198         {
1199             t0.x = pt0.x; t1.x = pt1.x;
1200             t0.y = pt0.y << XY_SHIFT;
1201             t1.y = pt1.y << XY_SHIFT;
1202             icvLineAA( img, t0, t1, color );
1203         }
1204
1205         if( pt0.y == pt1.y )
1206             continue;
1207
1208         if( pt0.y > pt1.y )
1209             CV_SWAP( pt0, pt1, t0 );
1210
1211         bounds.y = MIN( bounds.y, pt0.y );
1212         bounds.height = MAX( bounds.height, pt1.y );
1213
1214         if( pt0.x < pt1.x )
1215         {
1216             bounds.x = MIN( bounds.x, pt0.x );
1217             bounds.width = MAX( bounds.width, pt1.x );
1218         }
1219         else
1220         {
1221             bounds.x = MIN( bounds.x, pt1.x );
1222             bounds.width = MAX( bounds.width, pt0.x );
1223         }
1224
1225         edge.y0 = pt0.y;
1226         edge.y1 = pt1.y;
1227         edge.x = pt0.x;
1228         edge.dx = (pt1.x - pt0.x) / (pt1.y - pt0.y);
1229         assert( edge.y0 < edge.y1 );
1230
1231         CV_WRITE_SEQ_ELEM( edge, writer );
1232     }
1233
1234     edges->rect = bounds;
1235     cvEndWriteSeq( &writer );
1236 }
1237
1238 static int
1239 icvCmpEdges( const void* _e1, const void* _e2, void* /*userdata*/ )
1240 {
1241     CvPolyEdge *e1 = (CvPolyEdge*)_e1, *e2 = (CvPolyEdge*)_e2;
1242     return e1->y0 - e2->y0 ? e1->y0 - e2->y0 :
1243            e1->x - e2->x ? e1->x - e2->x : e1->dx - e2->dx;
1244 }
1245
1246 /**************** helper macros and functions for sequence/contour processing ***********/
1247
1248 static void
1249 icvFillEdgeCollection( CvMat* img, CvContour* edges, const void* color )
1250 {
1251     CvPolyEdge tmp;
1252     int i, y, total = edges->total;
1253     CvSeqReader reader;
1254     CvSize size = cvGetMatSize(img);
1255     CvPolyEdge* e;
1256     int y_max = INT_MIN;
1257     int pix_size = CV_ELEM_SIZE(img->type);
1258
1259     __BEGIN__;
1260
1261     memset( &tmp, 0, sizeof(tmp));
1262
1263     /* check parameters */
1264     if( edges->total < 2 || edges->rect.height < 0 || edges->rect.y >= size.height ||
1265         edges->rect.width < 0 || edges->rect.x >= size.width )
1266         EXIT;
1267
1268     cvSeqSort( (CvSeq*)edges, icvCmpEdges, 0 );
1269     cvStartReadSeq( (CvSeq*)edges, &reader );
1270
1271 #ifdef _DEBUG
1272     e = &tmp;
1273     tmp.y0 = INT_MIN;
1274 #endif
1275
1276     for( i = 0; i < total; i++ )
1277     {
1278         CvPolyEdge* e1 = (CvPolyEdge*)(reader.ptr);
1279
1280 #ifdef _DEBUG
1281         assert( e1->y0 < e1->y1 && (i == 0 || icvCmpEdges( e, e1, 0 ) <= 0) );
1282         e = e1;
1283 #endif
1284         y_max = MAX( y_max, e1->y1 );
1285
1286         CV_NEXT_SEQ_ELEM( sizeof(CvPolyEdge), reader );
1287     }
1288
1289     /* start drawing */
1290     tmp.y0 = INT_MAX;
1291     cvSeqPush( (CvSeq*)edges, &tmp );
1292
1293     i = 0;
1294     tmp.next = 0;
1295     cvStartReadSeq( (CvSeq*)edges, &reader );
1296     e = (CvPolyEdge*)(reader.ptr);
1297     y_max = MIN( y_max, size.height );
1298
1299     for( y = e->y0; y < y_max; y++ )
1300     {
1301         CvPolyEdge *last, *prelast, *keep_prelast;
1302         int sort_flag = 0;
1303         int draw = 0;
1304         int clipline = y < 0;
1305
1306         prelast = &tmp;
1307         last = tmp.next;
1308         while( last || e->y0 == y )
1309         {
1310             if( last && last->y1 == y )
1311             {
1312                 /* exlude edge if y reachs its lower point */
1313                 prelast->next = last->next;
1314                 last = last->next;
1315                 continue;
1316             }
1317             keep_prelast = prelast;
1318             if( last && (e->y0 > y || last->x < e->x) )
1319             {
1320                 /* go to the next edge in active list */
1321                 prelast = last;
1322                 last = last->next;
1323             }
1324             else if( i < total )
1325             {
1326                 /* insert new edge into active list if y reachs its upper point */
1327                 prelast->next = e;
1328                 e->next = last;
1329                 prelast = e;
1330                 CV_NEXT_SEQ_ELEM( edges->elem_size, reader );
1331                 e = (CvPolyEdge*)(reader.ptr);
1332                 i++;
1333             }
1334             else
1335                 break;
1336
1337             if( draw )
1338             {
1339                 if( !clipline )
1340                 {
1341                     /* convert x's from fixed-point to image coordinates */
1342                     uchar *timg = (uchar*)(img->data.ptr) + y * img->step;
1343                     int x1 = keep_prelast->x;
1344                     int x2 = prelast->x;
1345
1346                     if( x1 > x2 )
1347                     {
1348                         int t = x1;
1349
1350                         x1 = x2;
1351                         x2 = t;
1352                     }
1353
1354                     x1 = (x1 + XY_ONE - 1) >> XY_SHIFT;
1355                     x2 = x2 >> XY_SHIFT;
1356
1357                     /* clip and draw the line */
1358                     if( x1 < size.width && x2 >= 0 )
1359                     {
1360                         if( x1 < 0 )
1361                             x1 = 0;
1362                         if( x2 >= size.width )
1363                             x2 = size.width - 1;
1364                         ICV_HLINE( timg, x1, x2, color, pix_size );
1365                     }
1366                 }
1367                 keep_prelast->x += keep_prelast->dx;
1368                 prelast->x += prelast->dx;
1369             }
1370             draw ^= 1;
1371         }
1372
1373         /* sort edges (bubble sort on list) */
1374         keep_prelast = 0;
1375
1376         do
1377         {
1378             prelast = &tmp;
1379             last = tmp.next;
1380
1381             while( last != keep_prelast && last->next != 0 )
1382             {
1383                 CvPolyEdge *te = last->next;
1384
1385                 /* swap edges */
1386                 if( last->x > te->x )
1387                 {
1388                     prelast->next = te;
1389                     last->next = te->next;
1390                     te->next = last;
1391                     prelast = te;
1392                     sort_flag = 1;
1393                 }
1394                 else
1395                 {
1396                     prelast = last;
1397                     last = te;
1398                 }
1399             }
1400             keep_prelast = prelast;
1401         }
1402         while( sort_flag && keep_prelast != tmp.next && keep_prelast != &tmp );
1403     }
1404
1405     __END__;
1406 }
1407
1408
1409 /* draws simple or filled circle */
1410 static void
1411 icvCircle( CvMat* img, CvPoint center, int radius, const void* color, int fill )
1412 {
1413     CvSize size = cvGetMatSize( img );
1414     int step = img->step;
1415     int pix_size = CV_ELEM_SIZE(img->type);
1416     uchar* ptr = (uchar*)(img->data.ptr);
1417     int err = 0, dx = radius, dy = 0, plus = 1, minus = (radius << 1) - 1;
1418     int inside = center.x >= radius && center.x < size.width - radius &&
1419         center.y >= radius && center.y < size.height - radius;
1420
1421     #define ICV_PUT_POINT( ptr, x )     \
1422         CV_MEMCPY_CHAR( ptr + (x)*pix_size, color, pix_size );
1423
1424     while( dx >= dy )
1425     {
1426         int mask;
1427         int y11 = center.y - dy, y12 = center.y + dy, y21 = center.y - dx, y22 = center.y + dx;
1428         int x11 = center.x - dx, x12 = center.x + dx, x21 = center.x - dy, x22 = center.x + dy;
1429
1430         if( inside )
1431         {
1432             uchar *tptr0 = ptr + y11 * step;
1433             uchar *tptr1 = ptr + y12 * step;
1434
1435             if( !fill )
1436             {
1437                 ICV_PUT_POINT( tptr0, x11 );
1438                 ICV_PUT_POINT( tptr1, x11 );
1439                 ICV_PUT_POINT( tptr0, x12 );
1440                 ICV_PUT_POINT( tptr1, x12 );
1441             }
1442             else
1443             {
1444                 ICV_HLINE( tptr0, x11, x12, color, pix_size );
1445                 ICV_HLINE( tptr1, x11, x12, color, pix_size );
1446             }
1447
1448             tptr0 = ptr + y21 * step;
1449             tptr1 = ptr + y22 * step;
1450
1451             if( !fill )
1452             {
1453                 ICV_PUT_POINT( tptr0, x21 );
1454                 ICV_PUT_POINT( tptr1, x21 );
1455                 ICV_PUT_POINT( tptr0, x22 );
1456                 ICV_PUT_POINT( tptr1, x22 );
1457             }
1458             else
1459             {
1460                 ICV_HLINE( tptr0, x21, x22, color, pix_size );
1461                 ICV_HLINE( tptr1, x21, x22, color, pix_size );
1462             }
1463         }
1464         else if( x11 < size.width && x12 >= 0 && y21 < size.height && y22 >= 0 )
1465         {
1466             if( fill )
1467             {
1468                 x11 = MAX( x11, 0 );
1469                 x12 = MIN( x12, size.width - 1 );
1470             }
1471
1472             if( (unsigned)y11 < (unsigned)size.height )
1473             {
1474                 uchar *tptr = ptr + y11 * step;
1475
1476                 if( !fill )
1477                 {
1478                     if( x11 >= 0 )
1479                         ICV_PUT_POINT( tptr, x11 );
1480                     if( x12 < size.width )
1481                         ICV_PUT_POINT( tptr, x12 );
1482                 }
1483                 else
1484                     ICV_HLINE( tptr, x11, x12, color, pix_size );
1485             }
1486
1487             if( (unsigned)y12 < (unsigned)size.height )
1488             {
1489                 uchar *tptr = ptr + y12 * step;
1490
1491                 if( !fill )
1492                 {
1493                     if( x11 >= 0 )
1494                         ICV_PUT_POINT( tptr, x11 );
1495                     if( x12 < size.width )
1496                         ICV_PUT_POINT( tptr, x12 );
1497                 }
1498                 else
1499                     ICV_HLINE( tptr, x11, x12, color, pix_size );
1500             }
1501
1502             if( x21 < size.width && x22 >= 0 )
1503             {
1504                 if( fill )
1505                 {
1506                     x21 = MAX( x21, 0 );
1507                     x22 = MIN( x22, size.width - 1 );
1508                 }
1509
1510                 if( (unsigned)y21 < (unsigned)size.height )
1511                 {
1512                     uchar *tptr = ptr + y21 * step;
1513
1514                     if( !fill )
1515                     {
1516                         if( x21 >= 0 )
1517                             ICV_PUT_POINT( tptr, x21 );
1518                         if( x22 < size.width )
1519                             ICV_PUT_POINT( tptr, x22 );
1520                     }
1521                     else
1522                         ICV_HLINE( tptr, x21, x22, color, pix_size );
1523                 }
1524
1525                 if( (unsigned)y22 < (unsigned)size.height )
1526                 {
1527                     uchar *tptr = ptr + y22 * step;
1528
1529                     if( !fill )
1530                     {
1531                         if( x21 >= 0 )
1532                             ICV_PUT_POINT( tptr, x21 );
1533                         if( x22 < size.width )
1534                             ICV_PUT_POINT( tptr, x22 );
1535                     }
1536                     else
1537                         ICV_HLINE( tptr, x21, x22, color, pix_size );
1538                 }
1539             }
1540         }
1541         dy++;
1542         err += plus;
1543         plus += 2;
1544
1545         mask = (err <= 0) - 1;
1546
1547         err -= minus & mask;
1548         dx += mask;
1549         minus -= mask & 2;
1550     }
1551
1552     #undef  ICV_PUT_POINT
1553 }
1554
1555
1556 static void
1557 icvThickLine( CvMat* img, CvPoint p0, CvPoint p1, const void* color,
1558               int thickness, int line_type, int flags, int shift )
1559 {
1560     static const double INV_XY_ONE = 1./XY_ONE;
1561
1562     p0.x <<= XY_SHIFT - shift;
1563     p0.y <<= XY_SHIFT - shift;
1564     p1.x <<= XY_SHIFT - shift;
1565     p1.y <<= XY_SHIFT - shift;
1566
1567     if( thickness <= 1 )
1568     {
1569         if( line_type < CV_AA )
1570         {
1571             if( line_type == 1 || line_type == 4 || shift == 0 )
1572             {
1573                 p0.x = (p0.x + (XY_ONE>>1)) >> XY_SHIFT;
1574                 p0.y = (p0.y + (XY_ONE>>1)) >> XY_SHIFT;
1575                 p1.x = (p1.x + (XY_ONE>>1)) >> XY_SHIFT;
1576                 p1.y = (p1.y + (XY_ONE>>1)) >> XY_SHIFT;
1577                 icvLine( img, p0, p1, color, line_type );
1578             }
1579             else
1580                 icvLine2( img, p0, p1, color );
1581         }
1582         else
1583             icvLineAA( img, p0, p1, color );
1584     }
1585     else
1586     {
1587         CvPoint pt[4], dp = {0,0};
1588         double dx = (p0.x - p1.x)*INV_XY_ONE, dy = (p1.y - p0.y)*INV_XY_ONE;
1589         double r = dx * dx + dy * dy;
1590         int i;
1591         thickness <<= XY_SHIFT - 1;
1592
1593         if( fabs(r) > DBL_EPSILON )
1594         {
1595             r = thickness * cvInvSqrt( (float) r );
1596             dp.x = cvRound( dy * r );
1597             dp.y = cvRound( dx * r );
1598         }
1599
1600         pt[0].x = p0.x + dp.x;
1601         pt[0].y = p0.y + dp.y;
1602         pt[1].x = p0.x - dp.x;
1603         pt[1].y = p0.y - dp.y;
1604         pt[2].x = p1.x - dp.x;
1605         pt[2].y = p1.y - dp.y;
1606         pt[3].x = p1.x + dp.x;
1607         pt[3].y = p1.y + dp.y;
1608
1609         icvFillConvexPoly( img, pt, 4, color, line_type, XY_SHIFT );
1610
1611         for( i = 0; i < 2; i++ )
1612         {
1613             if( flags & (i+1) )
1614             {
1615                 if( line_type < CV_AA )
1616                 {
1617                     CvPoint center;
1618                     center.x = (p0.x + (XY_ONE>>1)) >> XY_SHIFT;
1619                     center.y = (p0.y + (XY_ONE>>1)) >> XY_SHIFT;
1620                     icvCircle( img, center, thickness >> XY_SHIFT, color, 1 );
1621                 }
1622                 else
1623                 {
1624                     icvEllipseEx( img, p0, cvSize(thickness, thickness),
1625                                   0, 0, 360, color, -1, line_type );
1626                 }
1627             }
1628             p0 = p1;
1629         }
1630     }
1631 }
1632
1633
1634 static void
1635 icvPolyLine( CvMat* img, CvPoint *v, int count, int is_closed,
1636              const void* color, int thickness,
1637              int line_type, int shift )
1638 {
1639     CV_FUNCNAME("icvPolyLine");
1640
1641     __BEGIN__;
1642
1643     if( count > 0 )
1644     {
1645         int i = is_closed ? count - 1 : 0;
1646         int flags = 2 + !is_closed;
1647         CvPoint p0;
1648         assert( 0 <= shift && shift <= XY_SHIFT );
1649         assert( img && thickness >= 0 );
1650         assert( v && count >= 0 );
1651
1652         if( !v )
1653             CV_ERROR( CV_StsNullPtr, "" );
1654
1655         p0 = v[i];
1656         for( i = !is_closed; i < count; i++ )
1657         {
1658             CvPoint p = v[i];
1659             icvThickLine( img, p0, p, color, thickness, line_type, flags, shift );
1660             p0 = p;
1661             flags = 2;
1662         }
1663     }
1664
1665     __END__;
1666 }
1667
1668 /****************************************************************************************\
1669 *                              External functions                                        *
1670 \****************************************************************************************/
1671
1672 CV_IMPL CvScalar cvColorToScalar( double packed_color, int type )
1673 {
1674     CvScalar scalar;
1675
1676     if( CV_MAT_DEPTH( type ) == CV_8U )
1677     {
1678         int icolor = cvRound( packed_color );
1679         if( CV_MAT_CN( type ) > 1 )
1680         {
1681             scalar.val[0] = icolor & 255;
1682             scalar.val[1] = (icolor >> 8) & 255;
1683             scalar.val[2] = (icolor >> 16) & 255;
1684             scalar.val[3] = (icolor >> 24) & 255;
1685         }
1686         else
1687         {
1688             scalar.val[0] = CV_CAST_8U( icolor );
1689             scalar.val[1] = scalar.val[2] = scalar.val[3] = 0;
1690         }
1691     }
1692     else if( CV_MAT_DEPTH( type ) == CV_8S )
1693     {
1694         int icolor = cvRound( packed_color );
1695         if( CV_MAT_CN( type ) > 1 )
1696         {
1697             scalar.val[0] = (char)icolor;
1698             scalar.val[1] = (char)(icolor >> 8);
1699             scalar.val[2] = (char)(icolor >> 16);
1700             scalar.val[3] = (char)(icolor >> 24);
1701         }
1702         else
1703         {
1704             scalar.val[0] = CV_CAST_8S( icolor );
1705             scalar.val[1] = scalar.val[2] = scalar.val[3] = 0;
1706         }
1707     }
1708     else
1709     {
1710         int cn = CV_MAT_CN( type );
1711         switch( cn )
1712         {
1713         case 1:
1714             scalar.val[0] = packed_color;
1715             scalar.val[1] = scalar.val[2] = scalar.val[3] = 0;
1716             break;
1717         case 2:
1718             scalar.val[0] = scalar.val[1] = packed_color;
1719             scalar.val[2] = scalar.val[3] = 0;
1720             break;
1721         case 3:
1722             scalar.val[0] = scalar.val[1] = scalar.val[2] = packed_color;
1723             scalar.val[3] = 0;
1724             break;
1725         default:
1726             scalar.val[0] = scalar.val[1] =
1727                 scalar.val[2] = scalar.val[3] = packed_color;
1728             break;
1729         }
1730     }
1731
1732     return scalar;
1733 }
1734
1735
1736 CV_IMPL void
1737 cvLine( void* img, CvPoint pt1, CvPoint pt2, CvScalar color,
1738         int thickness, int line_type, int shift )
1739 {
1740     CV_FUNCNAME( "cvLine" );
1741
1742     __BEGIN__;
1743
1744     int coi = 0;
1745     CvMat stub, *mat = (CvMat*)img;
1746     double buf[4];
1747
1748     CV_CALL( mat = cvGetMat( img, &stub, &coi ));
1749
1750     if( line_type == CV_AA && CV_MAT_DEPTH(mat->type) != CV_8U )
1751         line_type = 8;
1752
1753     if( coi != 0 )
1754         CV_ERROR( CV_BadCOI, cvUnsupportedFormat );
1755
1756     if( (unsigned)thickness > 255  )
1757         CV_ERROR( CV_StsOutOfRange, "" );
1758
1759     if( shift < 0 || XY_SHIFT < shift )
1760         CV_ERROR( CV_StsOutOfRange, "shift must be between 0 and 16" );
1761
1762     CV_CALL( cvScalarToRawData( &color, buf, mat->type, 0 ));
1763     icvThickLine( mat, pt1, pt2, buf, thickness, line_type, 3, shift );
1764
1765     __END__;
1766 }
1767
1768
1769 CV_IMPL void
1770 cvRectangle( void* img, CvPoint pt1, CvPoint pt2,
1771              CvScalar color, int thickness,
1772              int line_type, int shift )
1773 {
1774     CvPoint pt[4];
1775
1776     CV_FUNCNAME("cvRectangle");
1777
1778     __BEGIN__;
1779
1780     int coi = 0;
1781     CvMat stub, *mat = (CvMat*)img;
1782     double buf[4];
1783
1784     if( thickness > 255 )
1785         CV_ERROR( CV_StsOutOfRange, "" );
1786
1787     CV_CALL( mat = cvGetMat( img, &stub, &coi ));
1788
1789     if( line_type == CV_AA && CV_MAT_DEPTH(mat->type) != CV_8U )
1790         line_type = 8;
1791
1792     if( coi != 0 )
1793         CV_ERROR( CV_BadCOI, cvUnsupportedFormat );
1794
1795     if( shift < 0 || XY_SHIFT < shift )
1796         CV_ERROR( CV_StsOutOfRange, "shift must be between 0 and 16" );
1797
1798     CV_CALL( cvScalarToRawData( &color, buf, mat->type, 0 ));
1799
1800     pt[0] = pt1;
1801     pt[1].x = pt2.x;
1802     pt[1].y = pt1.y;
1803     pt[2] = pt2;
1804     pt[3].x = pt1.x;
1805     pt[3].y = pt2.y;
1806
1807     if( thickness >= 0 )
1808         icvPolyLine( mat, pt, 4, 1, buf, thickness, line_type, shift );
1809     else
1810         icvFillConvexPoly( mat, pt, 4, buf, line_type, shift );
1811
1812     __END__;
1813 }
1814
1815
1816 CV_IMPL void
1817 cvCircle( void *img, CvPoint center, int radius,
1818           CvScalar color, int thickness, int line_type, int shift )
1819 {
1820     CV_FUNCNAME( "cvCircle" );
1821
1822     __BEGIN__;
1823
1824     int coi = 0;
1825     CvMat stub, *mat = (CvMat*)img;
1826     double buf[4];
1827
1828     CV_CALL( mat = cvGetMat( mat, &stub, &coi ));
1829
1830     if( line_type == CV_AA && CV_MAT_DEPTH(mat->type) != CV_8U )
1831         line_type = 8;
1832
1833     if( coi != 0 )
1834         CV_ERROR( CV_BadCOI, cvUnsupportedFormat );
1835
1836     if( radius < 0 )
1837         CV_ERROR( CV_StsOutOfRange, "" );
1838
1839     if( thickness > 255 )
1840         CV_ERROR( CV_StsOutOfRange, "" );
1841
1842     if( shift < 0 || XY_SHIFT < shift )
1843         CV_ERROR( CV_StsOutOfRange, "shift must be between 0 and 16" );
1844
1845     CV_CALL( cvScalarToRawData( &color, buf, mat->type, 0 ));
1846
1847     if( thickness > 1 || line_type >= CV_AA )
1848     {
1849         center.x <<= XY_SHIFT - shift;
1850         center.y <<= XY_SHIFT - shift;
1851         radius <<= XY_SHIFT - shift;
1852         icvEllipseEx( mat, center, cvSize( radius, radius ),
1853                       0, 0, 360, buf, thickness, line_type );
1854     }
1855     else
1856     {
1857         icvCircle( mat, center, radius, buf, thickness < 0 );
1858     }
1859
1860     __END__;
1861 }
1862
1863
1864 CV_IMPL void
1865 cvEllipse( void *img, CvPoint center, CvSize axes,
1866            double angle, double start_angle, double end_angle,
1867            CvScalar color, int thickness, int line_type, int shift )
1868 {
1869     CV_FUNCNAME( "cvEllipse" );
1870
1871     __BEGIN__;
1872
1873     int coi = 0;
1874     CvMat stub, *mat = (CvMat*)img;
1875     double buf[4];
1876
1877     CV_CALL( mat = cvGetMat( mat, &stub, &coi ));
1878
1879     if( line_type == CV_AA && CV_MAT_DEPTH(mat->type) != CV_8U )
1880         line_type = 8;
1881
1882     if( coi != 0 )
1883         CV_ERROR( CV_BadCOI, cvUnsupportedFormat );
1884
1885     if( axes.width < 0 || axes.height < 0 )
1886         CV_ERROR( CV_StsOutOfRange, "" );
1887
1888     if( thickness > 255 )
1889         CV_ERROR( CV_StsOutOfRange, "" );
1890
1891     if( shift < 0 || XY_SHIFT < shift )
1892         CV_ERROR( CV_StsOutOfRange, "shift must be between 0 and 16" );
1893
1894     CV_CALL( cvScalarToRawData( &color, buf, mat->type, 0 ));
1895
1896     {
1897         int _angle = cvRound(angle);
1898         int _start_angle = cvRound(start_angle);
1899         int _end_angle = cvRound(end_angle);
1900         center.x <<= XY_SHIFT - shift;
1901         center.y <<= XY_SHIFT - shift;
1902         axes.width <<= XY_SHIFT - shift;
1903         axes.height <<= XY_SHIFT - shift;
1904
1905         CV_CALL( icvEllipseEx( mat, center, axes, _angle, _start_angle,
1906                                _end_angle, buf, thickness, line_type ));
1907     }
1908
1909     __END__;
1910 }
1911
1912
1913 CV_IMPL void
1914 cvFillConvexPoly( void *img, CvPoint *pts, int npts, CvScalar color, int line_type, int shift )
1915 {
1916     CV_FUNCNAME( "cvFillConvexPoly" );
1917
1918     __BEGIN__;
1919
1920     int coi = 0;
1921     CvMat stub, *mat = (CvMat*)img;
1922     double buf[4];
1923
1924     CV_CALL( mat = cvGetMat( mat, &stub, &coi ));
1925
1926     if( line_type == CV_AA && CV_MAT_DEPTH(mat->type) != CV_8U )
1927         line_type = 8;
1928
1929     if( coi != 0 )
1930         CV_ERROR( CV_BadCOI, cvUnsupportedFormat );
1931
1932     if( !pts )
1933         CV_ERROR( CV_StsNullPtr, "" );
1934
1935     if( npts <= 0 )
1936         CV_ERROR( CV_StsOutOfRange, "" );
1937
1938     if( shift < 0 || XY_SHIFT < shift )
1939         CV_ERROR( CV_StsOutOfRange, "shift must be between 0 and 16" );
1940
1941     CV_CALL( cvScalarToRawData( &color, buf, mat->type, 0 ));
1942     icvFillConvexPoly( mat, pts, npts, buf, line_type, shift );
1943
1944     __END__;
1945 }
1946
1947
1948 CV_IMPL void
1949 cvFillPoly( void *img, CvPoint **pts, int *npts, int contours,
1950             CvScalar color, int line_type, int shift )
1951 {
1952     CvMemStorage* st = 0;
1953
1954     CV_FUNCNAME( "cvFillPoly" );
1955
1956     __BEGIN__;
1957
1958     int coi = 0;
1959     CvMat stub, *mat = (CvMat*)img;
1960     double buf[4];
1961
1962     CV_CALL( mat = cvGetMat( mat, &stub, &coi ));
1963
1964     if( line_type == CV_AA && CV_MAT_DEPTH(mat->type) != CV_8U )
1965         line_type = 8;
1966
1967     if( coi != 0 )
1968         CV_ERROR( CV_BadCOI, cvUnsupportedFormat );
1969
1970     if( contours <= 0 )
1971         CV_ERROR( CV_StsBadArg, "" );
1972
1973     if( !pts )
1974         CV_ERROR( CV_StsNullPtr, "" );
1975
1976     if( npts <= 0 )
1977         CV_ERROR( CV_StsNullPtr, "" );
1978
1979     if( shift < 0 || XY_SHIFT < shift )
1980         CV_ERROR( CV_StsOutOfRange, "shift must be between 0 and 16" );
1981
1982     CV_CALL( cvScalarToRawData( &color, buf, mat->type, 0 ));
1983
1984     {
1985         CvContour* edges = 0;
1986         CvSeq vtx;
1987         CvSeqBlock block;
1988
1989         CV_CALL( st = cvCreateMemStorage( CV_DRAWING_STORAGE_BLOCK ));
1990         CV_CALL( edges = (CvContour*)cvCreateSeq( 0, sizeof(CvContour),
1991                                                   sizeof(CvPolyEdge), st ));
1992
1993         for( int i = 0; i < contours; i++ )
1994         {
1995             if( !pts[i] )
1996                 CV_ERROR( CV_StsNullPtr, "" );
1997
1998             if( npts[i] < 0 )
1999                 CV_ERROR( CV_StsOutOfRange, "" );
2000
2001             cvMakeSeqHeaderForArray( CV_32SC2, sizeof(CvSeq), sizeof(CvPoint),
2002                                      pts[i], npts[i], &vtx, &block );
2003
2004             CV_CALL( icvCollectPolyEdges( mat, &vtx, edges, buf, line_type, shift ));
2005         }
2006
2007         CV_CALL( icvFillEdgeCollection( mat, edges, buf ));
2008     }
2009
2010     __END__;
2011
2012     cvReleaseMemStorage( &st );
2013 }
2014
2015
2016
2017 CV_IMPL void
2018 cvPolyLine( void *img, CvPoint **pts, int *npts,
2019             int contours, int closed, CvScalar color,
2020             int thickness, int line_type, int shift )
2021 {
2022     CV_FUNCNAME( "cvPolyLine" );
2023
2024     __BEGIN__;
2025
2026     int coi = 0, i;
2027     CvMat stub, *mat = (CvMat*)img;
2028     double buf[4];
2029
2030     CV_CALL( mat = cvGetMat( mat, &stub, &coi ));
2031
2032     if( line_type == CV_AA && CV_MAT_DEPTH(mat->type) != CV_8U )
2033         line_type = 8;
2034
2035     if( coi != 0 )
2036         CV_ERROR( CV_BadCOI, cvUnsupportedFormat );
2037
2038     if( contours <= 0 )
2039         CV_ERROR( CV_StsBadArg, "" );
2040
2041     if( thickness < -1 || thickness > 255 )
2042         CV_ERROR( CV_StsBadArg, "" );
2043
2044     if( !pts )
2045         CV_ERROR( CV_StsNullPtr, "" );
2046
2047     if( npts <= 0 )
2048         CV_ERROR( CV_StsNullPtr, "" );
2049
2050     if( shift < 0 || XY_SHIFT < shift )
2051         CV_ERROR( CV_StsOutOfRange, "shift must be between 0 and 16" );
2052
2053     CV_CALL( cvScalarToRawData( &color, buf, mat->type, 0 ));
2054
2055     for( i = 0; i < contours; i++ )
2056         icvPolyLine( mat, pts[i], npts[i], closed, buf, thickness, line_type, shift );
2057
2058     __END__;
2059 }
2060
2061
2062 #define CV_FONT_SIZE_SHIFT     8
2063 #define CV_FONT_ITALIC_ALPHA   (1 << 8)
2064 #define CV_FONT_ITALIC_DIGIT   (2 << 8)
2065 #define CV_FONT_ITALIC_PUNCT   (4 << 8)
2066 #define CV_FONT_ITALIC_BRACES  (8 << 8)
2067 #define CV_FONT_HAVE_GREEK     (16 << 8)
2068 #define CV_FONT_HAVE_CYRILLIC  (32 << 8)
2069
2070 static const int icvHersheyPlain[] = {
2071 (5 + 4*16) + CV_FONT_HAVE_GREEK,
2072 199, 214, 217, 233, 219, 197, 234, 216, 221, 222, 228, 225, 211, 224, 210, 220,
2073 200, 201, 202, 203, 204, 205, 206, 207, 208, 209, 212, 213, 191, 226, 192,
2074 215, 190, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13,
2075 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 193, 84,
2076 194, 85, 86, 87, 101, 102, 103, 104, 105, 106, 107, 108, 109, 110, 111,
2077 112, 113, 114, 115, 116, 117, 118, 119, 120, 121, 122, 123, 124, 125, 126,
2078 195, 223, 196, 88 };
2079
2080 static const int icvHersheyPlainItalic[] = {
2081 (5 + 4*16) + CV_FONT_ITALIC_ALPHA + CV_FONT_HAVE_GREEK,
2082 199, 214, 217, 233, 219, 197, 234, 216, 221, 222, 228, 225, 211, 224, 210, 220,
2083 200, 201, 202, 203, 204, 205, 206, 207, 208, 209, 212, 213, 191, 226, 192,
2084 215, 190, 51, 52, 53, 54, 55, 56, 57, 58, 59, 60, 61, 62, 63,
2085 64, 65, 66, 67, 68, 69, 70, 71, 72, 73, 74, 75, 76, 193, 84,
2086 194, 85, 86, 87, 151, 152, 153, 154, 155, 156, 157, 158, 159, 160, 161,
2087 162, 163, 164, 165, 166, 167, 168, 169, 170, 171, 172, 173, 174, 175, 176,
2088 195, 223, 196, 88 };
2089
2090 static const int icvHersheyComplexSmall[] = {
2091 (6 + 7*16) + CV_FONT_HAVE_GREEK,
2092 1199, 1214, 1217, 1275, 1274, 1271, 1272, 1216, 1221, 1222, 1219, 1232, 1211, 1231, 1210, 1220,
2093 1200, 1201, 1202, 1203, 1204, 1205, 1206, 1207, 1208, 1209, 1212, 2213, 1241, 1238, 1242,
2094 1215, 1273, 1001, 1002, 1003, 1004, 1005, 1006, 1007, 1008, 1009, 1010, 1011, 1012, 1013,
2095 1014, 1015, 1016, 1017, 1018, 1019, 1020, 1021, 1022, 1023, 1024, 1025, 1026, 1223, 1084,
2096 1224, 1247, 586, 1249, 1101, 1102, 1103, 1104, 1105, 1106, 1107, 1108, 1109, 1110, 1111,
2097 1112, 1113, 1114, 1115, 1116, 1117, 1118, 1119, 1120, 1121, 1122, 1123, 1124, 1125, 1126,
2098 1225, 1229, 1226, 1246 };
2099
2100 static const int icvHersheyComplexSmallItalic[] = {
2101 (6 + 7*16) + CV_FONT_ITALIC_ALPHA + CV_FONT_HAVE_GREEK,
2102 1199, 1214, 1217, 1275, 1274, 1271, 1272, 1216, 1221, 1222, 1219, 1232, 1211, 1231, 1210, 1220,
2103 1200, 1201, 1202, 1203, 1204, 1205, 1206, 1207, 1208, 1209, 1212, 1213, 1241, 1238, 1242,
2104 1215, 1273, 1051, 1052, 1053, 1054, 1055, 1056, 1057, 1058, 1059, 1060, 1061, 1062, 1063,
2105 1064, 1065, 1066, 1067, 1068, 1069, 1070, 1071, 1072, 1073, 1074, 1075, 1076, 1223, 1084,
2106 1224, 1247, 586, 1249, 1151, 1152, 1153, 1154, 1155, 1156, 1157, 1158, 1159, 1160, 1161,
2107 1162, 1163, 1164, 1165, 1166, 1167, 1168, 1169, 1170, 1171, 1172, 1173, 1174, 1175, 1176,
2108 1225, 1229, 1226, 1246 };
2109
2110 static const int icvHersheySimplex[] = {
2111 (9 + 12*16) + CV_FONT_HAVE_GREEK,
2112 2199, 714, 717, 733, 719, 697, 734, 716, 721, 722, 728, 725, 711, 724, 710, 720,
2113 700, 701, 702, 703, 704, 705, 706, 707, 708, 709, 712, 713, 691, 726, 692,
2114 715, 690, 501, 502, 503, 504, 505, 506, 507, 508, 509, 510, 511, 512, 513,
2115 514, 515, 516, 517, 518, 519, 520, 521, 522, 523, 524, 525, 526, 693, 584,
2116 694, 2247, 586, 2249, 601, 602, 603, 604, 605, 606, 607, 608, 609, 610, 611,
2117 612, 613, 614, 615, 616, 617, 618, 619, 620, 621, 622, 623, 624, 625, 626,
2118 695, 723, 696, 2246 };
2119
2120 static const int icvHersheyDuplex[] = {
2121 (9 + 12*16) + CV_FONT_HAVE_GREEK,
2122 2199, 2714, 2728, 2732, 2719, 2733, 2718, 2727, 2721, 2722, 2723, 2725, 2711, 2724, 2710, 2720,
2123 2700, 2701, 2702, 2703, 2704, 2705, 2706, 2707, 2708, 2709, 2712, 2713, 2730, 2726, 2731,
2124 2715, 2734, 2501, 2502, 2503, 2504, 2505, 2506, 2507, 2508, 2509, 2510, 2511, 2512, 2513,
2125 2514, 2515, 2516, 2517, 2518, 2519, 2520, 2521, 2522, 2523, 2524, 2525, 2526, 2223, 2084,
2126 2224, 2247, 587, 2249, 2601, 2602, 2603, 2604, 2605, 2606, 2607, 2608, 2609, 2610, 2611,
2127 2612, 2613, 2614, 2615, 2616, 2617, 2618, 2619, 2620, 2621, 2622, 2623, 2624, 2625, 2626,
2128 2225, 2229, 2226, 2246 };
2129
2130 static const int icvHersheyComplex[] = {
2131 (9 + 12*16) + CV_FONT_HAVE_GREEK + CV_FONT_HAVE_CYRILLIC,
2132 2199, 2214, 2217, 2275, 2274, 2271, 2272, 2216, 2221, 2222, 2219, 2232, 2211, 2231, 2210, 2220,
2133 2200, 2201, 2202, 2203, 2204, 2205, 2206, 2207, 2208, 2209, 2212, 2213, 2241, 2238, 2242,
2134 2215, 2273, 2001, 2002, 2003, 2004, 2005, 2006, 2007, 2008, 2009, 2010, 2011, 2012, 2013,
2135 2014, 2015, 2016, 2017, 2018, 2019, 2020, 2021, 2022, 2023, 2024, 2025, 2026, 2223, 2084,
2136 2224, 2247, 587, 2249, 2101, 2102, 2103, 2104, 2105, 2106, 2107, 2108, 2109, 2110, 2111,
2137 2112, 2113, 2114, 2115, 2116, 2117, 2118, 2119, 2120, 2121, 2122, 2123, 2124, 2125, 2126,
2138 2225, 2229, 2226, 2246 };
2139
2140 static const int icvHersheyComplexItalic[] = {
2141 (9 + 12*16) + CV_FONT_ITALIC_ALPHA + CV_FONT_ITALIC_DIGIT + CV_FONT_ITALIC_PUNCT +
2142 CV_FONT_HAVE_GREEK + CV_FONT_HAVE_CYRILLIC,
2143 2199, 2764, 2778, 2782, 2769, 2783, 2768, 2777, 2771, 2772, 2219, 2232, 2211, 2231, 2210, 2220,
2144 2750, 2751, 2752, 2753, 2754, 2755, 2756, 2757, 2758, 2759, 2212, 2213, 2241, 2238, 2242,
2145 2765, 2273, 2051, 2052, 2053, 2054, 2055, 2056, 2057, 2058, 2059, 2060, 2061, 2062, 2063,
2146 2064, 2065, 2066, 2067, 2068, 2069, 2070, 2071, 2072, 2073, 2074, 2075, 2076, 2223, 2084,
2147 2224, 2247, 587, 2249, 2151, 2152, 2153, 2154, 2155, 2156, 2157, 2158, 2159, 2160, 2161,
2148 2162, 2163, 2164, 2165, 2166, 2167, 2168, 2169, 2170, 2171, 2172, 2173, 2174, 2175, 2176,
2149 2225, 2229, 2226, 2246 };
2150
2151 static const int icvHersheyTriplex[] = {
2152 (9 + 12*16) + CV_FONT_HAVE_GREEK,
2153 2199, 3214, 3228, 3232, 3219, 3233, 3218, 3227, 3221, 3222, 3223, 3225, 3211, 3224, 3210, 3220,
2154 3200, 3201, 3202, 3203, 3204, 3205, 3206, 3207, 3208, 3209, 3212, 3213, 3230, 3226, 3231,
2155 3215, 3234, 3001, 3002, 3003, 3004, 3005, 3006, 3007, 3008, 3009, 3010, 3011, 3012, 3013,
2156 2014, 3015, 3016, 3017, 3018, 3019, 3020, 3021, 3022, 3023, 3024, 3025, 3026, 2223, 2084,
2157 2224, 2247, 587, 2249, 3101, 3102, 3103, 3104, 3105, 3106, 3107, 3108, 3109, 3110, 3111,
2158 3112, 3113, 3114, 3115, 3116, 3117, 3118, 3119, 3120, 3121, 3122, 3123, 3124, 3125, 3126,
2159 2225, 2229, 2226, 2246 };
2160
2161 static const int icvHersheyTriplexItalic[] = {
2162 (9 + 12*16) + CV_FONT_ITALIC_ALPHA + CV_FONT_ITALIC_DIGIT +
2163 CV_FONT_ITALIC_PUNCT + CV_FONT_HAVE_GREEK,
2164 2199, 3264, 3278, 3282, 3269, 3233, 3268, 3277, 3271, 3272, 3223, 3225, 3261, 3224, 3260, 3270,
2165 3250, 3251, 3252, 3253, 3254, 3255, 3256, 3257, 3258, 3259, 3262, 3263, 3230, 3226, 3231,
2166 3265, 3234, 3051, 3052, 3053, 3054, 3055, 3056, 3057, 3058, 3059, 3060, 3061, 3062, 3063,
2167 2064, 3065, 3066, 3067, 3068, 3069, 3070, 3071, 3072, 3073, 3074, 3075, 3076, 2223, 2084,
2168 2224, 2247, 587, 2249, 3151, 3152, 3153, 3154, 3155, 3156, 3157, 3158, 3159, 3160, 3161,
2169 3162, 3163, 3164, 3165, 3166, 3167, 3168, 3169, 3170, 3171, 3172, 3173, 3174, 3175, 3176,
2170 2225, 2229, 2226, 2246 };
2171
2172 static const int icvHersheyScriptSimplex[] = {
2173 (9 + 12*16) + CV_FONT_ITALIC_ALPHA + CV_FONT_HAVE_GREEK,
2174 2199, 714, 717, 733, 719, 697, 734, 716, 721, 722, 728, 725, 711, 724, 710, 720,
2175 700, 701, 702, 703, 704, 705, 706, 707, 708, 709, 712, 713, 691, 726, 692,
2176 715, 690, 551, 552, 553, 554, 555, 556, 557, 558, 559, 560, 561, 562, 563,
2177 564, 565, 566, 567, 568, 569, 570, 571, 572, 573, 574, 575, 576, 693, 584,
2178 694, 2247, 586, 2249, 651, 652, 653, 654, 655, 656, 657, 658, 659, 660, 661,
2179 662, 663, 664, 665, 666, 667, 668, 669, 670, 671, 672, 673, 674, 675, 676,
2180 695, 723, 696, 2246 };
2181
2182 static const int icvHersheyScriptComplex[] = {
2183 (9 + 12*16) + CV_FONT_ITALIC_ALPHA + CV_FONT_ITALIC_DIGIT + CV_FONT_ITALIC_PUNCT + CV_FONT_HAVE_GREEK,
2184 2199, 2764, 2778, 2782, 2769, 2783, 2768, 2777, 2771, 2772, 2219, 2232, 2211, 2231, 2210, 2220,
2185 2750, 2751, 2752, 2753, 2754, 2755, 2756, 2757, 2758, 2759, 2212, 2213, 2241, 2238, 2242,
2186 2215, 2273, 2551, 2552, 2553, 2554, 2555, 2556, 2557, 2558, 2559, 2560, 2561, 2562, 2563,
2187 2564, 2565, 2566, 2567, 2568, 2569, 2570, 2571, 2572, 2573, 2574, 2575, 2576, 2223, 2084,
2188 2224, 2247, 586, 2249, 2651, 2652, 2653, 2654, 2655, 2656, 2657, 2658, 2659, 2660, 2661,
2189 2662, 2663, 2664, 2665, 2666, 2667, 2668, 2669, 2670, 2671, 2672, 2673, 2674, 2675, 2676,
2190 2225, 2229, 2226, 2246 };
2191
2192
2193 CV_IMPL void
2194 cvPutText( void *img, const char *text, CvPoint org, const CvFont *font, CvScalar color )
2195 {
2196     CV_FUNCNAME( "cvPutText" );
2197
2198     __BEGIN__;
2199
2200     int view_x, view_y;
2201     int coi = 0;
2202     int top_bottom = 0, base_line;
2203     int hscale, vscale, default_shear, italic_shear;
2204     int thickness, line_type;
2205     CvMat stub, *mat = (CvMat*)img;
2206     double buf[4];
2207     CvPoint pt[1 << 10];
2208     int count;
2209
2210     int i;
2211     const char **faces = icvHersheyGlyphs;
2212
2213     CV_CALL( mat = cvGetMat( mat, &stub, &coi ));
2214
2215     if( coi != 0 )
2216         CV_ERROR( CV_BadCOI, cvUnsupportedFormat );
2217
2218     if( CV_IS_IMAGE_HDR(img) && ((IplImage*)img)->origin )
2219         top_bottom = 1;
2220
2221     if( !text || !font || !font->ascii )
2222         CV_ERROR( CV_StsNullPtr, "" );
2223
2224     CV_CALL( cvScalarToRawData( &color, buf, mat->type, 0 ));
2225     base_line = -(font->ascii[0] & 15);
2226     hscale = cvRound(font->hscale*XY_ONE);
2227     vscale = cvRound(font->vscale*XY_ONE);
2228     default_shear = cvRound(font->shear*font->vscale*XY_ONE);
2229     italic_shear = !(font->font_face & CV_FONT_ITALIC) ? 0 : cvRound(font->vscale*.25*XY_ONE);
2230     thickness = font->thickness;
2231     line_type = font->line_type;
2232
2233     if( line_type == CV_AA && CV_MAT_DEPTH(mat->type) != CV_8U )
2234         line_type = 8;
2235
2236     if( top_bottom )
2237         vscale = -vscale;
2238
2239     view_x = org.x << XY_SHIFT;
2240     view_y = (org.y << XY_SHIFT) + base_line*vscale;
2241
2242     for( i = 0; text[i] != '\0'; i++ )
2243     {
2244         int c = (uchar)text[i];
2245         int dx, shear = default_shear;
2246         const char* ptr;
2247         CvPoint p;
2248
2249         if( c > 128 || c < ' ' )
2250             c = '?';
2251
2252         if( italic_shear )
2253         {
2254             if( ('a' <= c && c <= 'z') || ('A' <= c && c <= 'Z'))
2255             {
2256                 if( !(font->ascii[0] & CV_FONT_ITALIC_ALPHA) )
2257                     shear += italic_shear;
2258             }
2259             else if( '0' <= c && c <= '9' )
2260             {
2261                 if( !(font->ascii[0] & CV_FONT_ITALIC_DIGIT) )
2262                     shear += italic_shear;
2263             }
2264             else if( c < 'A' )
2265             {
2266                 if( !(font->ascii[0] & CV_FONT_ITALIC_PUNCT) )
2267                     shear += italic_shear;
2268             }
2269             else
2270             {
2271                 shear += italic_shear;
2272             }
2273         }
2274
2275         ptr = faces[font->ascii[(c-' ')+1]];
2276         p.x = (unsigned char)ptr[0] - 'R';
2277         p.y = (unsigned char)ptr[1] - 'R';
2278         dx = p.y*hscale;
2279         view_x -= p.x*hscale;
2280         count = 0;
2281
2282         for( ptr += 2;; )
2283         {
2284             if( *ptr == ' ' || !*ptr )
2285             {
2286                 if( count > 1 )
2287                     icvPolyLine( mat, pt, count, 0, buf, thickness, line_type, XY_SHIFT );
2288                 if( !*ptr++ )
2289                     break;
2290                 count = 0;
2291             }
2292             else
2293             {
2294                 p.x = (unsigned char)ptr[0] - 'R';
2295                 p.y = (unsigned char)ptr[1] - 'R';
2296                 ptr += 2;
2297                 pt[count].x = p.x*hscale - p.y*shear + view_x;
2298                 pt[count++].y = p.y*vscale + view_y;
2299             }
2300         }
2301         view_x += dx;
2302     }
2303
2304     __END__;
2305 }
2306
2307 CV_IMPL void
2308 cvInitFont( CvFont *font, int font_face, double hscale, double vscale,
2309             double shear, int thickness, int line_type )
2310 {
2311     CV_FUNCNAME( "cvInitFont" );
2312
2313     __BEGIN__;
2314
2315     int is_italic = font_face & CV_FONT_ITALIC;
2316
2317     if( !font )
2318         CV_ERROR( CV_StsNullPtr, "" );
2319
2320     if( hscale <= 0 || vscale <= 0 || thickness < 0 )
2321         CV_ERROR( CV_StsOutOfRange, "" );
2322
2323     switch( (font_face & 7) )
2324     {
2325     case CV_FONT_HERSHEY_SIMPLEX:
2326         font->ascii = icvHersheySimplex;
2327         break;
2328     case CV_FONT_HERSHEY_PLAIN:
2329         font->ascii = !is_italic ? icvHersheyPlain : icvHersheyPlainItalic;
2330         break;
2331     case CV_FONT_HERSHEY_DUPLEX:
2332         font->ascii = icvHersheyDuplex;
2333         break;
2334     case CV_FONT_HERSHEY_COMPLEX:
2335         font->ascii = !is_italic ? icvHersheyComplex : icvHersheyComplexItalic;
2336         break;
2337     case CV_FONT_HERSHEY_TRIPLEX:
2338         font->ascii = !is_italic ? icvHersheyTriplex : icvHersheyTriplexItalic;
2339         break;
2340     case CV_FONT_HERSHEY_COMPLEX_SMALL:
2341         font->ascii = !is_italic ? icvHersheyComplexSmall : icvHersheyComplexSmallItalic;
2342         break;
2343     case CV_FONT_HERSHEY_SCRIPT_SIMPLEX:
2344         font->ascii = icvHersheyScriptSimplex;
2345         break;
2346     case CV_FONT_HERSHEY_SCRIPT_COMPLEX:
2347         font->ascii = icvHersheyScriptComplex;
2348         break;
2349     default:
2350         CV_ERROR( CV_StsOutOfRange, "Unknown font type" );
2351     }
2352
2353     font->font_face = font_face;
2354     font->hscale = (float)hscale;
2355     font->vscale = (float)vscale;
2356     font->thickness = thickness;
2357     font->shear = (float)shear;
2358     font->greek = font->cyrillic = 0;
2359     font->line_type = line_type;
2360
2361     __END__;
2362 }
2363
2364
2365 CV_IMPL void
2366 cvGetTextSize( const char *text, const CvFont *font, CvSize *size, int *_base_line )
2367 {
2368     CV_FUNCNAME( "cvGetTextSize" );
2369
2370     __BEGIN__;
2371
2372     float view_x = 0;
2373     int base_line, cap_line;
2374
2375     int i;
2376     const char **faces = icvHersheyGlyphs;
2377
2378     if( !text || !font || !font->ascii || !size )
2379         CV_ERROR( CV_StsNullPtr, "" );
2380
2381     base_line = (font->ascii[0] & 15);
2382     cap_line = (font->ascii[0] >> 4) & 15;
2383     if( _base_line )
2384         *_base_line = cvRound(base_line*font->vscale);
2385     size->height = cvRound((cap_line + base_line)*font->vscale + font->thickness);
2386
2387     for( i = 0; text[i] != '\0'; i++ )
2388     {
2389         int c = (uchar)text[i];
2390         const char* ptr;
2391         CvPoint p;
2392
2393         if( c > 128 || c < ' ' )
2394             c = '?';
2395
2396         ptr = faces[font->ascii[(c-' ')+1]];
2397         p.x = (unsigned char)ptr[0] - 'R';
2398         p.y = (unsigned char)ptr[1] - 'R';
2399         view_x += (p.y - p.x)*font->hscale;
2400     }
2401
2402     size->width = cvRound(view_x + font->thickness);
2403
2404     __END__;
2405 }
2406
2407
2408 static const CvPoint icvCodeDeltas[8] =
2409 { {1, 0}, {1, -1}, {0, -1}, {-1, -1}, {-1, 0}, {-1, 1}, {0, 1}, {1, 1} };
2410
2411 #define CV_ADJUST_EDGE_COUNT( count, seq )  \
2412     ((count) -= ((count) == (seq)->total && !CV_IS_SEQ_CLOSED(seq)))
2413
2414 CV_IMPL void
2415 cvDrawContours( void*  img,  CvSeq*  contour,
2416                 CvScalar externalColor, CvScalar holeColor,
2417                 int  maxLevel, int thickness,
2418                 int line_type, CvPoint offset )
2419 {
2420     CvSeq *contour0 = contour, *h_next = 0;
2421     CvMemStorage* st = 0;
2422     CvSeq* tseq = 0;
2423     CvContour* edges = 0;
2424     CvSeqWriter writer;
2425     CvTreeNodeIterator iterator;
2426
2427     CV_FUNCNAME( "cvDrawContours" );
2428
2429     __BEGIN__;
2430
2431     int coi = 0;
2432     CvMat stub, *mat = (CvMat*)img;
2433     double ext_buf[4], hole_buf[4];
2434
2435     CV_CALL( mat = cvGetMat( mat, &stub, &coi ));
2436
2437     if( line_type == CV_AA && CV_MAT_DEPTH(mat->type) != CV_8U )
2438         line_type = 8;
2439
2440     if( !contour )
2441         EXIT;
2442
2443     if( coi != 0 )
2444         CV_ERROR( CV_BadCOI, cvUnsupportedFormat );
2445
2446     if( thickness < -1 || thickness > 255 )
2447         CV_ERROR( CV_StsOutOfRange, "" );
2448
2449     CV_CALL( cvScalarToRawData( &externalColor, ext_buf, mat->type, 0 ));
2450     CV_CALL( cvScalarToRawData( &holeColor, hole_buf, mat->type, 0 ));
2451
2452     if( maxLevel < 0 )
2453     {
2454         h_next = contour->h_next;
2455         contour->h_next = 0;
2456         maxLevel = -maxLevel+1;
2457     }
2458
2459     if( thickness < 0 )
2460     {
2461         if( contour->storage )
2462             st = cvCreateChildMemStorage( contour->storage );
2463         else
2464             st = cvCreateMemStorage( CV_DRAWING_STORAGE_BLOCK );
2465         tseq = cvCreateSeq( 0, sizeof(CvContour), sizeof(CvPoint), st );
2466         edges = (CvContour*)cvCreateSeq( 0, sizeof(CvContour), sizeof(CvPolyEdge), st );
2467     }
2468
2469     memset( &writer, 0, sizeof(writer));
2470
2471     cvInitTreeNodeIterator( &iterator, contour, maxLevel );
2472
2473     while( (contour = (CvSeq*)cvNextTreeNode( &iterator )) != 0 )
2474     {
2475         CvSeqReader reader;
2476         int i, count = contour->total;
2477         int elem_type = CV_MAT_TYPE(contour->flags);
2478         void* clr = (contour->flags & CV_SEQ_FLAG_HOLE) == 0 ? ext_buf : hole_buf;
2479
2480         cvStartReadSeq( contour, &reader, 0 );
2481
2482         if( CV_IS_SEQ_CHAIN_CONTOUR( contour ))
2483         {
2484             CvPoint pt = ((CvChain*)contour)->origin;
2485             CvPoint prev_pt = pt;
2486             char prev_code = reader.ptr ? reader.ptr[0] : '\0';
2487
2488             if( thickness < 0 )
2489             {
2490                 cvClearSeq( tseq );
2491                 cvStartAppendToSeq( tseq, &writer );
2492                 CV_WRITE_SEQ_ELEM( pt, writer );
2493             }
2494
2495             prev_pt.x += offset.x;
2496             prev_pt.y += offset.y;
2497
2498             for( i = 0; i < count; i++ )
2499             {
2500                 char code;
2501                 CV_READ_SEQ_ELEM( code, reader );
2502
2503                 assert( (code & ~7) == 0 );
2504
2505                 if( code != prev_code )
2506                 {
2507                     prev_code = code;
2508                     if( thickness >= 0 )
2509                     {
2510                         icvThickLine( mat, prev_pt, pt, clr, thickness, line_type, 2, 0 );
2511                     }
2512                     else
2513                     {
2514                         CV_WRITE_SEQ_ELEM( pt, writer );
2515                     }
2516                     prev_pt = pt;
2517                 }
2518
2519                 pt.x += icvCodeDeltas[(int)code].x;
2520                 pt.y += icvCodeDeltas[(int)code].y;
2521             }
2522
2523             if( thickness >= 0 )
2524             {
2525                 icvThickLine( mat, prev_pt, ((CvChain*)contour)->origin,
2526                               clr, thickness, line_type, 2, 0 );
2527             }
2528             else
2529             {
2530                 CV_WRITE_SEQ_ELEM( pt, writer );
2531                 cvEndWriteSeq( &writer );
2532                 CV_CALL( icvCollectPolyEdges( mat, tseq, edges, ext_buf, line_type, 0 ));
2533             }
2534         }
2535         else if( CV_IS_SEQ_POLYLINE( contour ))
2536         {
2537             if( thickness >= 0 )
2538             {
2539                 CvPoint pt1, pt2;
2540                 int shift = 0;
2541
2542                 count -= !CV_IS_SEQ_CLOSED(contour);
2543                 if( elem_type == CV_32SC2 )
2544                 {
2545                     CV_READ_SEQ_ELEM( pt1, reader );
2546                     pt1.x += offset.x;
2547                     pt1.y += offset.y;
2548                 }
2549                 else
2550                 {
2551                     CvPoint2D32f pt1f;
2552                     CV_READ_SEQ_ELEM( pt1f, reader );
2553                     pt1.x = cvRound( (pt1f.x + offset.x) * XY_ONE );
2554                     pt1.y = cvRound( (pt1f.y + offset.y) * XY_ONE );
2555                     shift = XY_SHIFT;
2556                 }
2557
2558                 for( i = 0; i < count; i++ )
2559                 {
2560                     if( elem_type == CV_32SC2 )
2561                     {
2562                         CV_READ_SEQ_ELEM( pt2, reader );
2563                         pt2.x += offset.x;
2564                         pt2.y += offset.y;
2565                     }
2566                     else
2567                     {
2568                         CvPoint2D32f pt2f;
2569                         CV_READ_SEQ_ELEM( pt2f, reader );
2570                         pt2.x = cvRound( pt2f.x * XY_ONE );
2571                         pt2.y = cvRound( pt2f.y * XY_ONE );
2572                     }
2573                     icvThickLine( mat, pt1, pt2, clr, thickness, line_type, 2, shift );
2574                     pt1 = pt2;
2575                 }
2576             }
2577             else
2578             {
2579                 CV_CALL( icvCollectPolyEdges( mat, contour, edges, ext_buf, line_type, 0, offset ));
2580             }
2581         }
2582     }
2583
2584     if( thickness < 0 )
2585     {
2586         CV_CALL( icvFillEdgeCollection( mat, edges, ext_buf ));
2587     }
2588
2589     __END__;
2590
2591     if( h_next && contour0 )
2592         contour0->h_next = h_next;
2593
2594     cvReleaseMemStorage( &st );
2595 }
2596
2597 /* End of file. */