src/subtitles/xy_widen_region.cpp

   1 #include "stdafx.h"
   2 #include "xy_widen_regoin.h"
   3 #include "Rasterizer.h"
   4 #include <vector>
   5 #include "xy_circular_array_queue.h"
   6 #include <math.h>
   7
   8 //terminology
   9 //  @left arc : left part of an ellipse
  10 //  @right arc: right part of an ellipse
  11 //  @link arc : curve composed by all left most points of a series of left arc , or all right most points of a series of right arc
  12 //  @cross_line of arc a and b (a.y < b.y):
  13 //    if both a and b are left arc, @cross_line is the max line that satisfied:
  14 //      a(line)< b(line) on line<@cross_line,
  15 //    and
  16 //      a(line)>=b(line) on line>=@cross_line
  17 //    if both a and b are right arc, @cross_line is the max line that satisfied:
  18 //      a(line)> b(line) on line<@cross_line,
  19 //    and
  20 //      a(line)<=b(line) on line>=@cross_line
  21
  22 static const int MIN_CROSS_LINE = (-2147483647 - 1);
  23 static const int MAX_CROSS_LINE = 0x7fffffff;
  24 static const int MAX_X = 0x7fffffff;
  25
  26 typedef unsigned __int64 XY_POINT;
  27 #define  XY_POINT_X(point)               ((point)&0xffffffff)
  28 #define  XY_POINT_Y(point)               ((point)>>32)
  29 #define  XY_POINT_SET(point,x,y)         ((point)=(((long long)(y)<<32)|(x)))
  30
  31 struct LinkArcItem
  32 {
  33     LinkArcItem():dead_line(0),arc_center(0){}
  34
  35     XY_POINT arc_center;
  36     int dead_line;
  37 };
  38
  39 typedef XYCircularArrayQueue<LinkArcItem> LinkArc;
  40
  41 struct LinkSpan
  42 {
  43     LinkArc left;
  44     LinkArc right;
  45 };
  46
  47 typedef CAtlList<LinkSpan> LinkSpanList;
  48
  49 typedef tSpan Span;
  50 typedef tSpanBuffer SpanBuffer;
  51 #define SPAN_LEFT(span)       ((span).first)
  52 #define SPAN_RIGHT(span)      ((span).second)
  53 #define SPAN_PTR_LEFT(span)   ((span)->first)
  54 #define SPAN_PTR_RIGHT(span)  ((span)->second)
  55
  56 struct XyEllipse
  57 {
  58 public:
  59     XyEllipse();
  60     ~XyEllipse();
  61
  62     /***
  63      * ry must >0 and rx must >=0
  64      **/
  65     int init(int rx, int ry);
  66
  67     inline int get_left_arc_x(int y) const;
  68     inline int get_left_arc_x(XY_POINT center, int y) const;
  69
  70     inline int get_right_arc_x(int y) const;
  71     inline int get_right_arc_x(XY_POINT center, int y) const;
  72
  73     int cross_left(XY_POINT c1, XY_POINT base) const;
  74     int cross_right(XY_POINT c1, XY_POINT base) const;
  75
  76     int init_cross_point();
  77
  78     int m_rx, m_ry;
  79     int *m_left_arc;
  80     int *m_left_arc_base;
  81
  82     int *m_cross_matrix;
  83     int *m_cross_matrix_base;
  84 private:
  85     XyEllipse(const XyEllipse&);
  86     void operator=(const XyEllipse&);
  87 };
  88
  89 class WidenRegionCreaterImpl
  90 {
  91 public:
  92     WidenRegionCreaterImpl();
  93     ~WidenRegionCreaterImpl();
  94
  95     void xy_overlap_region(SpanBuffer* dst, const SpanBuffer& src, int rx, int ry);
  96 private:
  97     int cross_left(const LinkArc& arc, XY_POINT center);//return <0 if arc(o)<inner_pl, MAX if arc(0)>inner_pl, else return cross_line
  98
  99     void add_left(LinkArc* arc, XY_POINT center);
 100     void add_right(LinkArc* arc, XY_POINT center);
 101     void add_span(LinkSpan* spans, const Span& span);
 102     void add_line(SpanBuffer* dst, LinkSpanList& spans, int cur_line, int dead_line);//add all line<dead_line to dst
 103
 104 private:
 105     XyEllipse *m_ellipse;
 106 };
 107
 108 //
 109 // WidenRegionCreater
 110 //
 111
 112 WidenRegionCreater* WidenRegionCreater::GetDefaultWidenRegionCreater()
 113 {
 114     static WidenRegionCreater result;
 115     static WidenRegionCreaterImpl impl;
 116     result.m_impl = &impl;
 117     return &result;
 118 }
 119
 120 WidenRegionCreater::WidenRegionCreater():m_impl(NULL)
 121 {
 122
 123 }
 124
 125 WidenRegionCreater::~WidenRegionCreater()
 126 {
 127
 128 }
 129
 130 void WidenRegionCreater::xy_overlap_region( SpanBuffer* dst, const SpanBuffer& src, int rx, int ry )
 131 {
 132     m_impl->xy_overlap_region(dst, src, rx, ry);
 133 }
 134
 135 //
 136 // WidenRegionCreaterImpl
 137 //
 138
 139 WidenRegionCreaterImpl::WidenRegionCreaterImpl(): m_ellipse(NULL)
 140 {
 141 }
 142
 143 WidenRegionCreaterImpl::~WidenRegionCreaterImpl()
 144 {
 145     delete m_ellipse;
 146 }
 147
 148 void WidenRegionCreaterImpl::xy_overlap_region(SpanBuffer* dst, const SpanBuffer& src, int rx, int ry)
 149 {
 150     if (m_ellipse!=NULL && (m_ellipse->m_rx!=rx || m_ellipse->m_ry!=ry))
 151     {
 152         delete m_ellipse;
 153         m_ellipse = NULL;
 154     }
 155     if (m_ellipse==NULL)
 156     {
 157         m_ellipse = new XyEllipse();
 158         if (m_ellipse==NULL)
 159         {
 160             ASSERT(0);
 161             return;
 162         }
 163         int rv = m_ellipse->init(rx, ry);
 164         if (rv<0)
 165         {
 166             ASSERT(0);
 167             return;
 168         }
 169     }
 170
 171     LinkSpanList link_span_list;
 172     POSITION pos=NULL;
 173     int dst_line = 0;
 174
 175     SpanBuffer::const_iterator it_src = src.begin();
 176     SpanBuffer::const_iterator it_src_end = src.end();
 177
 178     LinkSpan &sentinel = link_span_list.GetAt(link_span_list.AddTail());
 179     sentinel.left.init(2*ry+2);
 180     sentinel.right.init(2*ry+2);
 181     LinkArcItem& item = sentinel.left.inc_1_at_tail();
 182     XY_POINT_SET(item.arc_center, MAX_X, 0);
 183     item.dead_line = MAX_CROSS_LINE;
 184
 185     for ( ;it_src!=it_src_end; it_src++)
 186     {
 187         const XY_POINT &left = SPAN_PTR_LEFT(it_src);
 188         const XY_POINT &right = SPAN_PTR_RIGHT(it_src);
 189         int line = XY_POINT_Y(left); //fix me
 190         if (line-ry>dst_line)
 191         {
 192             add_line(dst, link_span_list, dst_line, line - ry);
 193             dst_line = line - ry;
 194             ASSERT(!link_span_list.IsEmpty() && !link_span_list.GetTail().left.empty());
 195             ASSERT(XY_POINT_X(link_span_list.GetTail().left.get_at(0).arc_center)==MAX_X);
 196             XY_POINT_SET(link_span_list.GetTail().left.get_at(0).arc_center, MAX_X, line-1);//update sentinel
 197             pos = link_span_list.GetHeadPosition();
 198         }
 199         while(true)
 200         {
 201             LinkSpan &spans = link_span_list.GetAt(pos);
 202             LinkArc &arc = spans.left;
 203             int y = cross_left(arc, left);
 204             if (y>ry)//fix me
 205             {
 206                 link_span_list.GetNext(pos);
 207                 continue;
 208             }
 209             else if ( y>=-ry )//fix me
 210             {
 211                 add_span(&spans, *it_src);
 212                 link_span_list.GetNext(pos);
 213                 break;
 214             }
 215             else
 216             {
 217                 LinkSpan &new_span = link_span_list.GetAt(link_span_list.InsertBefore(pos, LinkSpan()));
 218                 new_span.left.init(2*ry+2);
 219                 LinkArcItem& item = new_span.left.inc_1_at_tail();
 220
 221                 item.arc_center = SPAN_PTR_LEFT(it_src);
 222                 item.dead_line = line+ry+1;
 223
 224                 new_span.right.init(2*ry+2);
 225                 LinkArcItem& item2 = new_span.right.inc_1_at_tail();
 226                 item2.arc_center = SPAN_PTR_RIGHT(it_src);
 227                 item2.dead_line = line+ry+1;
 228                 break;
 229             }
 230         }
 231     }
 232     add_line(dst, link_span_list, dst_line, MAX_CROSS_LINE);
 233 }
 234
 235 int WidenRegionCreaterImpl::cross_left(const LinkArc& arc, XY_POINT center)
 236 {
 237     ASSERT(!arc.empty());
 238     int y = m_ellipse->cross_left(arc.back().arc_center, center);
 239     if (y>=MAX_CROSS_LINE)
 240     {
 241         return MAX_CROSS_LINE;
 242     }
 243     else
 244     {
 245         y = m_ellipse->cross_left(arc.get_at(0).arc_center, center);
 246         if (y<=MIN_CROSS_LINE)
 247         {
 248             return MIN_CROSS_LINE;
 249         }
 250     }
 251     return 0;
 252 }
 253
 254 void WidenRegionCreaterImpl::add_span(LinkSpan* spans, const Span& span )
 255 {
 256     ASSERT(spans);
 257     add_left(&spans->left, SPAN_LEFT(span));
 258     add_right(&spans->right, SPAN_RIGHT(span));
 259 }
 260
 261 void WidenRegionCreaterImpl::add_left( LinkArc* arc, XY_POINT center )
 262 {
 263     int rx = m_ellipse->m_rx;
 264     int ry = m_ellipse->m_ry;
 265     ASSERT(arc);
 266     ASSERT(!arc->empty()&& m_ellipse->cross_left(arc->get_at(0).arc_center, center)>=-ry );
 267     int y = 0;
 268     int i = 0;
 269     int line = XY_POINT_Y(center);
 270     for (i=arc->size()-1;i>=1;i--)
 271     {
 272         y = m_ellipse->cross_left( arc->get_at(i).arc_center, center );
 273         if( y>ry )//not cross
 274         {
 275             break;
 276         }
 277         else if  ( y+line>arc->get_at(i-1).dead_line )
 278         {
 279             arc->get_at(i).dead_line = y+line;
 280             break;
 281         }
 282         else
 283         {
 284             arc->pop_back();
 285         }
 286     }
 287     if (i==0)
 288     {
 289         y = m_ellipse->cross_left( arc->get_at(0).arc_center, center );
 290         ASSERT(y>=-ry && y+line<=arc->get_at(0).dead_line);
 291         arc->get_at(0).dead_line = y + line;
 292     }
 293     LinkArcItem& item = arc->inc_1_at_tail();
 294     item.arc_center = center;
 295     item.dead_line = line + ry + 1;
 296 }
 297
 298 void WidenRegionCreaterImpl::add_right( LinkArc* arc, XY_POINT center )
 299 {
 300     int rx = m_ellipse->m_rx;
 301     int ry = m_ellipse->m_ry;
 302     ASSERT(arc);
 303     ASSERT(!arc->empty());
 304     int y = 0;
 305     int i = 0;
 306     int line = XY_POINT_Y(center);
 307     for (i=arc->size()-1;i>=1;i--)
 308     {
 309         y = m_ellipse->cross_right( arc->get_at(i).arc_center, center );
 310         if( y>ry )//not cross
 311         {
 312             break;
 313         }
 314         else if ( y+line>arc->get_at(i-1).dead_line )
 315         {
 316             arc->get_at(i).dead_line = y+line;
 317             break;
 318         }
 319         else
 320         {
 321             arc->pop_back();
 322         }
 323     }
 324     if (i==0)
 325     {
 326         y = m_ellipse->cross_right( arc->get_at(0).arc_center, center );
 327         if (y<-ry)
 328         {
 329             arc->pop_back();
 330         }
 331         else if (y<MAX_CROSS_LINE)
 332         {
 333             ASSERT(y+line<=arc->get_at(0).dead_line);
 334             arc->get_at(0).dead_line = y + line;
 335         }
 336     }
 337     LinkArcItem& item = arc->inc_1_at_tail();
 338     item.arc_center = center;
 339     item.dead_line = line + ry + 1;
 340 }
 341
 342 void WidenRegionCreaterImpl::add_line( SpanBuffer* dst, LinkSpanList& spans, int cur_dst_line, int dead_line )
 343 {
 344     ASSERT(dst);
 345
 346     Span dst_span(0,0);
 347
 348     for( ;cur_dst_line<dead_line;cur_dst_line++)
 349     {
 350         POSITION pos_cur = spans.GetHeadPosition();
 351         POSITION pos_next = pos_cur;
 352         ASSERT(pos_next!=NULL);
 353         LinkSpan *span = &spans.GetNext(pos_next);
 354         if (pos_next==NULL)
 355         {
 356             break;
 357         }
 358
 359         while(pos_next!=NULL)
 360         {
 361             ASSERT(!span->left.empty());
 362             const LinkArcItem &left_top = span->left.get_at(0);
 363
 364             ASSERT(!span->right.empty());
 365             const LinkArcItem &right_top = span->right.get_at(0);
 366
 367             ASSERT(cur_dst_line < left_top.dead_line);
 368             ASSERT(cur_dst_line < right_top.dead_line);
 369
 370             XY_POINT left, right;
 371             int x = m_ellipse->get_left_arc_x(left_top.arc_center, cur_dst_line);
 372             XY_POINT_SET(left, x, cur_dst_line);
 373             x = m_ellipse->get_right_arc_x(right_top.arc_center, cur_dst_line);
 374             XY_POINT_SET(right, x, cur_dst_line);
 375             ASSERT(SPAN_LEFT(dst_span)<=left);
 376             if ( SPAN_RIGHT(dst_span) >= left )
 377             {
 378                 if ( SPAN_RIGHT(dst_span)<right )
 379                     SPAN_RIGHT(dst_span) = right;
 380             }
 381             else if ( SPAN_RIGHT(dst_span)>SPAN_LEFT(dst_span) )
 382             {
 383                 dst->push_back(dst_span);
 384                 SPAN_LEFT(dst_span) = left;
 385                 SPAN_RIGHT(dst_span) = right;
 386             }
 387             else
 388             {
 389                 SPAN_LEFT(dst_span) = left;
 390                 SPAN_RIGHT(dst_span) = right;
 391             }
 392
 393             if (cur_dst_line+1==left_top.dead_line)
 394             {
 395                 span->left.pop_front();
 396             }
 397             if (cur_dst_line+1==right_top.dead_line)
 398             {
 399                 span->right.pop_front();
 400             }
 401             if (span->left.empty())
 402             {
 403                 ASSERT(span->right.empty());
 404                 spans.RemoveAt(pos_cur);
 405                 pos_cur = pos_next;
 406                 span = &spans.GetNext(pos_next);
 407             }
 408             else
 409             {
 410                 pos_cur = pos_next;
 411                 span = &spans.GetNext(pos_next);
 412             }
 413         }
 414     }
 415     if ( SPAN_RIGHT(dst_span)>SPAN_LEFT(dst_span) )
 416     {
 417         dst->push_back(dst_span);
 418     }
 419 }
 420
 421 //
 422 // ref: A Fast Bresenham Type Algorithm For Drawing Ellipses by John Kennedy
 423 // http://homepage.smc.edu/kennedy_john/belipse.pdf
 424 //
 425 int gen_left_arc(int left_arc[], int rx, int ry)
 426 {
 427     if (left_arc==NULL)
 428         return 0;
 429
 430     int *left_arc2 = left_arc + ry;
 431     if (rx==0)
 432     {
 433         for (int y=-ry;y<=ry;y++)
 434         {
 435             left_arc2[y] = 0;
 436         }
 437         return 0;
 438     }
 439     else if (ry==0)
 440     {
 441         left_arc2[0] = rx;
 442         return 0;
 443     }
 444
 445     rx = abs(rx);
 446     ry = abs(ry);
 447     int a = rx;
 448     int b = ry;
 449     int a2 = 2* a * a;
 450     int b2 = 2* b * b;
 451     int x = a;
 452     int y = 0;
 453     __int64 dx = b*b*(1-2*a);
 454     __int64 dy = a*a;
 455     __int64 err = 0;
 456     __int64 stopx = b2 * a;
 457     __int64 stopy = 0;
 458     while (stopx >= stopy)
 459     {
 460         left_arc2[y] = -x;
 461         left_arc2[-y] = -x;
 462
 463         y++;
 464         stopy += a2;
 465         err += dy;
 466         dy += a2;
 467         if ( 2*err + dx > 0 )
 468         {
 469             x--;
 470             stopx -= b2;
 471             err += dx;
 472             dx += b2;
 473         }
 474     }
 475     int last_y_stop = y;
 476
 477     x = 0;
 478     y = b;
 479     dx = b*b;
 480     dy = a*a*(1-2*b);
 481     err = 0;
 482     stopx = 0;
 483     stopy = a2*b;
 484     while (stopx <= stopy)
 485     {
 486         left_arc2[y] = -x;
 487         left_arc2[-y] = -x;
 488
 489         x++;
 490         stopx += b2;
 491         err += dx;
 492         dx += b2;
 493         if (2*err+dy > 0)
 494         {
 495             y--;
 496             stopy -= a2;
 497             err += dy;
 498             dy += a2;
 499
 500             left_arc2[y] = -x;
 501             left_arc2[-y] = -x;
 502         }
 503     }
 504     while(y>last_y_stop)
 505     {
 506         y--;
 507         left_arc2[y] = left_arc2[y+1];
 508         left_arc2[-y] = left_arc2[y+1];
 509         if (y<=last_y_stop)
 510         {
 511             break;
 512         }
 513         left_arc2[last_y_stop] = left_arc[last_y_stop-1];
 514         left_arc2[-last_y_stop] = left_arc[last_y_stop-1];
 515         last_y_stop++;
 516     }
 517     //ASSERT(y<last_y_stop);
 518     return 0;
 519 }
 520
 521 //
 522 // XyEllipse
 523 //
 524
 525 XyEllipse::XyEllipse()
 526     : m_left_arc(NULL)
 527     , m_left_arc_base(NULL)
 528     , m_cross_matrix(NULL)
 529     , m_cross_matrix_base(NULL)
 530     , m_rx(0), m_ry(0)
 531 {
 532
 533 }
 534
 535 XyEllipse::~XyEllipse()
 536 {
 537     delete[]m_left_arc_base;
 538     delete[]m_cross_matrix_base;
 539 }
 540
 541 /***
 542  * ry must >0 and rx must >=0
 543  ***/
 544 int XyEllipse::init( int rx, int ry )
 545 {
 546     if (rx<0 || ry<=0)
 547     {
 548         return -1;
 549     }
 550     m_left_arc_base = new int[2*ry+2];
 551     if (!m_left_arc_base)
 552     {
 553         return -1;
 554     }
 555     gen_left_arc(m_left_arc_base, rx, ry);
 556     m_left_arc = m_left_arc_base + ry;
 557     m_rx = rx;
 558     m_ry = ry;
 559     init_cross_point();
 560     return 0;
 561 }
 562
 563 int XyEllipse::get_left_arc_x( int y ) const
 564 {
 565     return m_left_arc[y];
 566 }
 567
 568 int XyEllipse::get_left_arc_x( XY_POINT center, int y ) const
 569 {
 570     return XY_POINT_X(center) + m_left_arc[y-XY_POINT_Y(center)];
 571 }
 572
 573 int XyEllipse::get_right_arc_x( int y ) const
 574 {
 575     return -m_left_arc[y];
 576 }
 577
 578 int XyEllipse::get_right_arc_x( XY_POINT center, int y ) const
 579 {
 580     return XY_POINT_X(center) - m_left_arc[y-XY_POINT_Y(center)];
 581 }
 582
 583 int XyEllipse::init_cross_point()
 584 {
 585     if (m_rx<0 || m_ry<=0 )
 586     {
 587         return 0;
 588     }
 589     m_cross_matrix_base = new int[ (2*m_ry+1)*(2*m_rx+1) ];
 590     if (!m_cross_matrix_base)
 591     {
 592         return -1;
 593     }
 594
 595     m_cross_matrix = m_cross_matrix_base + (2*m_ry)*(2*m_rx+1) + m_rx;
 596
 597
 598     float f_rx = m_rx;
 599     float f_ry = m_ry;
 600     ASSERT(f_ry>0);
 601     float rx_devide_ry = f_rx/f_ry;
 602     float ry_2 = m_ry * m_ry;
 603
 604     std::vector<int> cross_x_base(2*m_ry+1+1);
 605     int *cross_x = &cross_x_base[0] + m_ry + 1;
 606     cross_x[-m_ry-1] = m_rx;
 607     for (int dy=-2*m_ry;dy<=-1;dy++)
 608     {
 609         int y=-m_ry;
 610         for ( ;y-dy<=m_ry;y++)
 611         {
 612             float f_cross_x = rx_devide_ry * ( sqrt(ry_2 - (y - dy)*(y - dy)) - sqrt(ry_2 - y*y) );
 613             cross_x[y] = ceil(f_cross_x);
 614             ASSERT(cross_x[y]<=cross_x[y-1] && abs(cross_x[y])<=m_rx);
 615         }
 616
 617         int *cross_matrix = m_cross_matrix + dy*(2*m_rx+1);
 618
 619         y--;
 620         //[ -m_rx, cross_x[y] )
 621         for (int j=-m_rx;j<cross_x[y];j++)
 622         {
 623             cross_matrix[j] = MAX_CROSS_LINE;
 624         }
 625         for ( ;y>-m_ry;y-- )
 626         {
 627             //[ cross_x[y], cross_x[y-1] )
 628             for (int j=cross_x[y];j<cross_x[y-1];j++)
 629             {
 630                 cross_matrix[j] = y;
 631             }
 632         }
 633         cross_matrix[cross_x[y]] = y;
 634         //[ cross_x[y], m_rx ]
 635         for (int j=cross_x[y];j<=m_rx;j++)
 636         {
 637             cross_matrix[j] = MIN_CROSS_LINE;
 638         }
 639     }
 640     return 0;
 641 }
 642
 643 int XyEllipse::cross_left( XY_POINT c1, XY_POINT base ) const
 644 {
 645     int dx = XY_POINT_X(c1) - XY_POINT_X(base);
 646     int dy = XY_POINT_Y(c1) - XY_POINT_Y(base);
 647     ASSERT(dy<0 && dy>=-2*m_ry);
 648     if (dx < -m_rx)
 649     {
 650         return MAX_CROSS_LINE;
 651     }
 652     else if (dx > m_rx)
 653     {
 654         return MIN_CROSS_LINE;
 655     }
 656     else // [-m_rx, m_rx]
 657     {
 658         ASSERT( abs( *(m_cross_matrix + dy*(2*m_rx+1) + dx) )<=m_ry ||
 659             *(m_cross_matrix + dy*(2*m_rx+1) + dx) == MIN_CROSS_LINE ||
 660             *(m_cross_matrix + dy*(2*m_rx+1) + dx) == MAX_CROSS_LINE );
 661         return *(m_cross_matrix + dy*(2*m_rx+1) + dx);
 662     }
 663 }
 664
 665 int XyEllipse::cross_right( XY_POINT c1, XY_POINT base ) const
 666 {
 667     int dx = XY_POINT_X(base) - XY_POINT_X(c1);
 668     int dy = XY_POINT_Y(c1) - XY_POINT_Y(base);
 669     ASSERT(dy<0 && dy>=-2*m_ry);
 670     if (dx < -m_rx)
 671     {
 672         return MAX_CROSS_LINE;
 673     }
 674     else if (dx > m_rx)
 675     {
 676         return MIN_CROSS_LINE;
 677     }
 678     else // [-m_rx, m_rx]
 679     {
 680         ASSERT( abs( *(m_cross_matrix + dy*(2*m_rx+1) + dx) )<=m_ry ||
 681             *(m_cross_matrix + dy*(2*m_rx+1) + dx) == MIN_CROSS_LINE ||
 682             *(m_cross_matrix + dy*(2*m_rx+1) + dx) == MAX_CROSS_LINE );
 683         return *(m_cross_matrix + dy*(2*m_rx+1) + dx);
 684     }
 685 }