src/subtitles/VobSubImage.cpp

   1 /*
   2  *      Copyright (C) 2003-2006 Gabest
   3  *      http://www.gabest.org
   4  *
   5  *  This Program is free software; you can redistribute it and/or modify
   6  *  it under the terms of the GNU General Public License as published by
   7  *  the Free Software Foundation; either version 2, or (at your option)
   8  *  any later version.
   9  *
  10  *  This Program is distributed in the hope that it will be useful,
  11  *  but WITHOUT ANY WARRANTY; without even the implied warranty of
  12  *  MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
  13  *  GNU General Public License for more details.
  14  *
  15  *  You should have received a copy of the GNU General Public License
  16  *  along with GNU Make; see the file COPYING.  If not, write to
  17  *  the Free Software Foundation, 675 Mass Ave, Cambridge, MA 02139, USA.
  18  *  http://www.gnu.org/copyleft/gpl.html
  19  *
  20  */
  21
  22 #include "stdafx.h"
  23 #include "VobSubImage.h"
  24
  25 CVobSubImage::CVobSubImage()
  26 {
  27         iLang = iIdx = -1;
  28         fForced = false;
  29         start = delay = 0;
  30         rect = CRect(0,0,0,0);
  31         lpPixels = lpTemp1 = lpTemp2 = NULL;
  32         org = CSize(0,0);
  33 }
  34
  35 CVobSubImage::~CVobSubImage()
  36 {
  37         Free();
  38 }
  39
  40 bool CVobSubImage::Alloc(int w, int h)
  41 {
  42         // if there is nothing to crop TrimSubImage might even add a 1 pixel
  43         // wide border around the text, that's why we need a bit more memory
  44         // to be allocated.
  45
  46         if(lpTemp1 == NULL || w*h > org.cx*org.cy || (w+2)*(h+2) > (org.cx+2)*(org.cy+2))
  47         {
  48                 Free();
  49
  50                 lpTemp1 = new RGBQUAD[w*h];
  51                 if(!lpTemp1) return(false);
  52
  53                 lpTemp2 = new RGBQUAD[(w+2)*(h+2)];
  54                 if(!lpTemp2) {delete [] lpTemp1; lpTemp1 = NULL; return(false);}
  55
  56                 org.cx = w;
  57                 org.cy = h;
  58         }
  59
  60         lpPixels = lpTemp1;
  61
  62         return(true);
  63 }
  64
  65 void CVobSubImage::Free()
  66 {
  67         if(lpTemp1) delete [] lpTemp1;
  68         lpTemp1 = NULL;
  69
  70         if(lpTemp2) delete [] lpTemp2;
  71         lpTemp2 = NULL;
  72
  73         lpPixels = NULL;
  74 }
  75
  76 bool CVobSubImage::Decode(BYTE* lpData, int packetsize, int datasize,
  77                                                   bool fCustomPal,
  78                                                   int tridx,
  79                                                   RGBQUAD* orgpal /*[16]*/, RGBQUAD* cuspal /*[4]*/,
  80                                                   bool fTrim)
  81 {
  82         GetPacketInfo(lpData, packetsize, datasize);
  83
  84         if(!Alloc(rect.Width(), rect.Height())) return(false);
  85
  86         lpPixels = lpTemp1;
  87
  88         nPlane = 0;
  89         fAligned = 1;
  90
  91         this->fCustomPal = fCustomPal;
  92         this->orgpal = orgpal;
  93         this->tridx = tridx;
  94         this->cuspal = cuspal;
  95
  96         CPoint p(rect.left, rect.top);
  97
  98         int end0 = nOffset[1];
  99         int end1 = datasize;
 100
 101         while((nPlane == 0 && nOffset[0] < end0) || (nPlane == 1 && nOffset[1] < end1))
 102         {
 103                 DWORD code;
 104
 105                 if((code = GetNibble(lpData)) >= 0x4
 106                 || (code = (code << 4) | GetNibble(lpData)) >= 0x10
 107                 || (code = (code << 4) | GetNibble(lpData)) >= 0x40
 108                 || (code = (code << 4) | GetNibble(lpData)) >= 0x100)
 109                 {
 110                         DrawPixels(p, code >> 2, code & 3);
 111                         if((p.x += code >> 2) < rect.right) continue;
 112                 }
 113
 114                 DrawPixels(p, rect.right - p.x, code & 3);
 115
 116                 if(!fAligned) GetNibble(lpData); // align to byte
 117
 118                 p.x = rect.left;
 119                 p.y++;
 120                 nPlane = 1 - nPlane;
 121         }
 122
 123         rect.bottom = min(p.y, rect.bottom);
 124
 125         if(fTrim) TrimSubImage();
 126
 127         return(true);
 128 }
 129
 130 void CVobSubImage::GetPacketInfo(BYTE* lpData, int packetsize, int datasize)
 131 {
 132 //      delay = 0;
 133
 134         int i, nextctrlblk = datasize;
 135         WORD pal = 0, tr = 0;
 136
 137         do
 138         {
 139                 i = nextctrlblk;
 140
 141                 int t = (lpData[i] << 8) | lpData[i+1]; i += 2;
 142                 nextctrlblk = (lpData[i] << 8) | lpData[i+1]; i += 2;
 143
 144                 if(nextctrlblk > packetsize || nextctrlblk < datasize)
 145                 {
 146                         ASSERT(0);
 147                         return;
 148                 }
 149
 150                 bool fBreak = false;
 151
 152                 while(!fBreak)
 153                 {
 154                         int len = 0;
 155
 156                         switch(lpData[i])
 157                         {
 158                                 case 0x00: len = 0; break;
 159                                 case 0x01: len = 0; break;
 160                                 case 0x02: len = 0; break;
 161                                 case 0x03: len = 2; break;
 162                                 case 0x04: len = 2; break;
 163                                 case 0x05: len = 6; break;
 164                                 case 0x06: len = 4; break;
 165                                 default: len = 0; break;
 166                         }
 167
 168                         if(i+len >= packetsize)
 169                         {
 170                                 TRACE(_T("Warning: Wrong subpicture parameter block ending\n"));
 171                                 break;
 172                         }
 173
 174                         switch(lpData[i++])
 175                         {
 176                                 case 0x00: // forced start displaying
 177                                         fForced = true;
 178                                         break;
 179                                 case 0x01: // start displaying
 180                                         fForced = false;
 181                                         break;
 182                                 case 0x02: // stop displaying
 183                                         delay = 1024 * t / 90;
 184                                         break;
 185                                 case 0x03:
 186                                         pal = (lpData[i] << 8) | lpData[i+1]; i += 2;
 187                                         break;
 188                                 case 0x04:
 189                                         tr = (lpData[i] << 8) | lpData[i+1]; i += 2;
 190 //tr &= 0x00f0;
 191                                         break;
 192                                 case 0x05:
 193                                         rect = CRect((lpData[i] << 4) + (lpData[i+1] >> 4),
 194                                                 (lpData[i+3] << 4) + (lpData[i+4] >> 4),
 195                                                 ((lpData[i+1] & 0x0f) << 8) + lpData[i+2] + 1,
 196                                                 ((lpData[i+4] & 0x0f) << 8) + lpData[i+5] + 1);
 197                                         i += 6;
 198                                         break;
 199                                 case 0x06:
 200                                         nOffset[0] = (lpData[i] << 8) + lpData[i+1]; i += 2;
 201                                         nOffset[1] = (lpData[i] << 8) + lpData[i+1]; i += 2;
 202                                         break;
 203                                 case 0xff: // end of ctrlblk
 204                                         fBreak = true;
 205                                         continue;
 206                                 default: // skip this ctrlblk
 207                                         fBreak = true;
 208                                         break;
 209                         }
 210                 }
 211         }
 212         while(i <= nextctrlblk && i < packetsize);
 213
 214         for(i = 0; i < 4; i++)
 215         {
 216                 this->pal[i].pal = (pal >> (i << 2)) & 0xf;
 217                 this->pal[i].tr = (tr >> (i << 2)) & 0xf;
 218         }
 219 }
 220
 221 BYTE CVobSubImage::GetNibble(BYTE* lpData)
 222 {
 223         WORD& off = nOffset[nPlane];
 224         BYTE ret = (lpData[off] >> (fAligned << 2)) & 0x0f;
 225         fAligned = !fAligned;
 226         off += fAligned;
 227         return(ret);
 228 }
 229
 230 void CVobSubImage::DrawPixels(CPoint p, int length, int colorid)
 231 {
 232         if(length <= 0
 233         || p.x + length < rect.left
 234         || p.x >= rect.right
 235         || p.y < rect.top
 236         || p.y >= rect.bottom)
 237         {
 238                 return;
 239         }
 240
 241         if(p.x < rect.left) p.x = rect.left;
 242         if(p.x + length >= rect.right) length = rect.right - p.x;
 243
 244         RGBQUAD* ptr = &lpPixels[rect.Width() * (p.y - rect.top) + (p.x - rect.left)];
 245
 246         RGBQUAD c;
 247
 248         if(!fCustomPal)
 249         {
 250                 c = orgpal[pal[colorid].pal];
 251                 c.rgbReserved = (pal[colorid].tr<<4)|pal[colorid].tr;
 252         }
 253         else
 254         {
 255                 c = cuspal[colorid];
 256         }
 257
 258         while(length-- > 0) *ptr++ = c;
 259 }
 260
 261 void CVobSubImage::TrimSubImage()
 262 {
 263         CRect r;
 264         r.left = rect.Width();
 265         r.top = rect.Height();
 266         r.right = 0;
 267         r.bottom = 0;
 268
 269         RGBQUAD* ptr = lpTemp1;
 270
 271         for(int j = 0, y = rect.Height(); j < y; j++)
 272         {
 273                 for(int i = 0, x = rect.Width(); i < x; i++, ptr++)
 274                 {
 275                         if(ptr->rgbReserved)
 276                         {
 277                                 if(r.top > j) r.top = j;
 278                                 if(r.bottom < j) r.bottom = j;
 279                                 if(r.left > i) r.left = i;
 280                                 if(r.right < i) r.right = i;
 281                         }
 282                 }
 283         }
 284
 285         if(r.left > r.right || r.top > r.bottom) return;
 286
 287         r += CRect(0, 0, 1, 1);
 288
 289         r &= CRect(CPoint(0,0), rect.Size());
 290
 291         int w = r.Width(), h = r.Height();
 292
 293         DWORD offset = r.top*rect.Width() + r.left;
 294
 295         r += CRect(1, 1, 1, 1);
 296
 297         DWORD* src = (DWORD*)&lpTemp1[offset];
 298         DWORD* dst = (DWORD*)&lpTemp2[1 + w + 1];
 299
 300         memset(lpTemp2, 0, (1 + w + 1)*sizeof(RGBQUAD));
 301
 302         for(int height = h; height; height--, src += rect.Width())
 303         {
 304                 *dst++ = 0;
 305                 memcpy(dst, src, w*sizeof(RGBQUAD)); dst += w;
 306                 *dst++ = 0;
 307         }
 308
 309         memset(dst, 0, (1 + w + 1)*sizeof(RGBQUAD));
 310
 311         lpPixels = lpTemp2;
 312
 313         rect = r + rect.TopLeft();
 314 }
 315
 316 ////////////////////////////////
 317
 318 #include "RTS.h"
 319 #include <math.h>
 320
 321 #define GP(xx, yy) (((xx) < 0 || (yy) < 0 || (xx) >= w || (yy) >= h) ? 0 : p[(yy)*w+(xx)])
 322
 323 CAutoPtrList<COutline>* CVobSubImage::GetOutlineList(CPoint& topleft)
 324 {
 325         int w = rect.Width(), h = rect.Height(), len = w*h;
 326         if(len <= 0) return NULL;
 327
 328         CAutoVectorPtr<BYTE> p;
 329         if(!p.Allocate(len)) return NULL;
 330
 331         CAutoPtrList<COutline>* ol = new CAutoPtrList<COutline>();
 332         if(!ol) return NULL;
 333
 334         BYTE* cp = p;
 335         RGBQUAD* rgbp = (RGBQUAD*)lpPixels;
 336
 337         for(int i = 0; i < len; i++, cp++, rgbp++)
 338                 *cp = !!rgbp->rgbReserved;
 339
 340         enum {UP, RIGHT, DOWN, LEFT};
 341
 342         topleft.x = topleft.y = INT_MAX;
 343
 344         while(1)
 345         {
 346                 cp = p;
 347
 348                 int x, y;
 349
 350                 for(y = 0; y < h; y++)
 351                 {
 352                         for(x = 0; x < w-1; x++, cp++)
 353                         {
 354                                 if(cp[0] == 0 && cp[1] == 1) break;
 355                         }
 356
 357                         if(x < w-1) break;
 358
 359                         cp++;
 360                 }
 361
 362                 if(y == h) break;
 363
 364                 int prevdir, dir = UP;
 365
 366                 int ox = x, oy = y, odir = dir;
 367
 368                 CAutoPtr<COutline> o(new COutline);
 369                 if(!o) break;
 370
 371                 do
 372                 {
 373                         CPoint pp;
 374                         BYTE fl, fr, br;
 375
 376                         prevdir = dir;
 377
 378                         switch(prevdir)
 379                         {
 380                         case UP:
 381                                 pp = CPoint(x+1, y);
 382                                 fl = GP(x, y-1);
 383                                 fr = GP(x+1, y-1);
 384                                 br = GP(x+1, y);
 385                                 break;
 386                         case RIGHT:
 387                                 pp = CPoint(x+1, y+1);
 388                                 fl = GP(x+1, y);
 389                                 fr = GP(x+1, y+1);
 390                                 br = GP(x, y+1);
 391                                 break;
 392                         case DOWN:
 393                                 pp = CPoint(x, y+1);
 394                                 fl = GP(x, y+1);
 395                                 fr = GP(x-1, y+1);
 396                                 br = GP(x-1, y);
 397                                 break;
 398                         case LEFT:
 399                                 pp = CPoint(x, y);
 400                                 fl = GP(x-1, y);
 401                                 fr = GP(x-1, y-1);
 402                                 br = GP(x, y-1);
 403                                 break;
 404                         }
 405
 406                         // turning left if:
 407                         // o . | o .
 408                         // ^ o | < o
 409                         // turning right if:
 410                         // x x | x >
 411                         // ^ o | x o
 412                         //
 413                         // o set, x empty, . can be anything
 414
 415                         if(fl==1) dir = (dir-1+4)&3;
 416                         else if(fl!=1 && fr!=1 && br==1) dir = (dir+1)&3;
 417                         else if(p[y*w+x]&16) {ASSERT(0); break;} // we are going around in one place (this must not happen if the starting conditions were correct)
 418
 419                         p[y*w+x] = (p[y*w+x]<<1) | 2; // increase turn count (== log2(highordbit(*p)))
 420
 421                         switch(dir)
 422                         {
 423                         case UP:
 424                                 if(prevdir == LEFT) {x--; y--;}
 425                                 if(prevdir == UP) y--;
 426                                 break;
 427                         case RIGHT:
 428                                 if(prevdir == UP) {x++; y--;}
 429                                 if(prevdir == RIGHT) x++;
 430                                 break;
 431                         case DOWN:
 432                                 if(prevdir == RIGHT) {x++; y++;}
 433                                 if(prevdir == DOWN) y++;
 434                                 break;
 435                         case LEFT:
 436                                 if(prevdir == DOWN) {x--; y++;}
 437                                 if(prevdir == LEFT) x--;
 438                                 break;
 439                         }
 440
 441                         int d = dir - prevdir;
 442                         o->Add(pp, d == 3 ? -1 : d == -3 ? 1 : d);
 443
 444                         if(topleft.x > pp.x) topleft.x = pp.x;
 445                         if(topleft.y > pp.y) topleft.y = pp.y;
 446                 }
 447                 while(!(x == ox && y == oy && dir == odir));
 448
 449                 if(o->pa.GetCount() > 0 && (x == ox && y == oy && dir == odir))
 450                 {
 451                         ol->AddTail(o);
 452                 }
 453                 else
 454                 {
 455                         ASSERT(0);
 456                 }
 457         }
 458
 459         return(ol);
 460 }
 461
 462 static bool FitLine(COutline& o, int& start, int& end)
 463 {
 464         int len = o.pa.GetCount();
 465         if(len < 7) return(false); // small segments should be handled with beziers...
 466
 467         for(start = 0; start < len && !o.da[start]; start++);
 468         for(end = len-1; end > start && !o.da[end]; end--);
 469
 470         if(end-start < 8 || end-start < (len-end)+(start-0)) return(false);
 471
 472         CUIntArray la, ra;
 473
 474         int i, j, k;
 475
 476         for(i = start+1, j = end, k = start; i <= j; i++)
 477         {
 478                 if(!o.da[i]) continue;
 479                 if(o.da[i] == o.da[k]) return(false);
 480                 if(o.da[i] == -1) la.Add(i-k);
 481                 else ra.Add(i-k);
 482                 k = i;
 483         }
 484
 485         bool fl = true, fr = true;
 486
 487         // these tests are completly heuristic and might be redundant a bit...
 488
 489         for(i = 0, j = la.GetSize(); i < j && fl; i++) {if(la[i] != 1) fl = false;}
 490         for(i = 0, j = ra.GetSize(); i < j && fr; i++) {if(ra[i] != 1) fr = false;}
 491
 492         if(!fl && !fr) return(false); // can't be a line if there are bigger steps than one in both directions (lines are usually drawn by stepping one either horizontally or vertically)
 493         if(fl && fr && 1.0*(end-start)/((len-end)*2+(start-0)*2) > 0.4) return(false); // if this section is relatively too small it may only be a rounded corner
 494         if(!fl && la.GetSize() > 0 && la.GetSize() <= 4 && (la[0] == 1 && la[la.GetSize()-1] == 1)) return(false); // one step at both ends, doesn't sound good for a line (may be it was skewed, so only eliminate smaller sections where beziers going to look just as good)
 495         if(!fr && ra.GetSize() > 0 && ra.GetSize() <= 4 && (ra[0] == 1 && ra[ra.GetSize()-1] == 1)) return(false); // -''-
 496
 497         CUIntArray& a = !fl ? la : ra;
 498
 499         len = a.GetSize();
 500
 501         int sum = 0;
 502
 503         for(i = 0, j = INT_MAX, k = 0; i < len; i++)
 504         {
 505                 if(j > a[i]) j = a[i];
 506                 if(k < a[i]) k = a[i];
 507                 sum += a[i];
 508         }
 509
 510         if(k - j > 2 && 1.0*sum/len < 2) return(false);
 511         if(k - j > 2 && 1.0*sum/len >= 2 && len < 4) return(false);
 512
 513         if((la.GetSize()/2+ra.GetSize()/2)/2 <= 2)
 514         {
 515                 if((k+j)/2 < 2 && k*j!=1) return(false);
 516         }
 517
 518         double err = 0;
 519
 520         CPoint sp = o.pa[start], ep = o.pa[end];
 521
 522         double minerr = 0, maxerr = 0;
 523
 524         double vx = ep.x - sp.x, vy = ep.y - sp.y, l = sqrt(vx*vx+vy*vy);
 525         vx /= l; vy /= l;
 526
 527         for(i = start+1, j = end-1; i <= j; i++)
 528         {
 529                 CPoint p = o.pa[i], dp = p - sp;
 530                 double t = vx*dp.x+vy*dp.y, dx = vx*t + sp.x - p.x, dy = vy*t + sp.y - p.y;
 531                 t = dx*dx+dy*dy;
 532                 err += t;
 533                 t = sqrt(t);
 534                 if(vy*dx-dy*vx < 0) {if(minerr > -t) minerr = -t;}
 535                 else {if(maxerr < t) maxerr = t;}
 536         }
 537
 538         return((maxerr-minerr)/l < 0.1  || err/l < 1.5 || (fabs(maxerr) < 8 && fabs(minerr) < 8));
 539 }
 540
 541 static int CalcPossibleCurveDegree(COutline& o)
 542 {
 543         int len2 = o.da.GetCount();
 544
 545         CUIntArray la;
 546
 547         for(int i = 0, j = 0; j < len2; j++)
 548         {
 549                 if(j == len2-1 || o.da[j])
 550                 {
 551                         la.Add(j-i);
 552                         i = j;
 553                 }
 554         }
 555
 556         int len = la.GetCount();
 557
 558         int ret = 0;
 559
 560         // check if we can find a reason to add a penalty degree, or two :P
 561         // it is mainly about looking for distant corners
 562         {
 563                 int penalty = 0;
 564
 565                 int ma[2] = {0, 0};
 566                 for(int i = 0; i < len; i++) ma[i&1] += la[i];
 567
 568                 int ca[2] = {ma[0], ma[1]};
 569                 for(int i = 0; i < len; i++)
 570                 {
 571                         ca[i&1] -= la[i];
 572
 573                         double c1 = 1.0*ca[0]/ma[0], c2 = 1.0*ca[1]/ma[1], c3 = 1.0*la[i]/ma[i&1];
 574
 575                         if(len2 > 16 && (fabs(c1-c2) > 0.7 || (c3 > 0.6 && la[i] > 5)))
 576                                 {penalty = 2; break;}
 577
 578                         if(fabs(c1-c2) > 0.6 || (c3 > 0.4 && la[i] > 5))
 579                                 {penalty = 1;}
 580                 }
 581
 582                 ret += penalty;
 583         }
 584
 585         la[0] <<= 1;
 586         la[len-1] <<= 1;
 587
 588         for(int i = 0; i < len; i+=2)
 589         {
 590                 if(la[i] > 1) {ret++; i--;} // prependicular to the last chosen section and bigger then 1 -> add a degree and continue with the other dir
 591         }
 592
 593         return(ret);
 594 }
 595
 596 inline double vectlen(CPoint p)
 597 {
 598         return(sqrt((double)(p.x*p.x+p.y*p.y)));
 599 }
 600
 601 inline double vectlen(CPoint p1, CPoint p2)
 602 {
 603         return(vectlen(p2 - p1));
 604 }
 605
 606 static bool MinMaxCosfi(COutline& o, double& mincf, double& maxcf) // not really cosfi, it is weighted by the distance from the segment endpoints, and since it would be always between -1 and 0, the applied sign marks side
 607 {
 608         CAtlArray<CPoint>& pa = o.pa;
 609
 610         int len = (int)pa.GetCount();
 611         if(len < 6) return(false);
 612
 613         mincf = 1;
 614         maxcf = -1;
 615
 616         CPoint p = pa[len-1] - pa[0];
 617         double l = vectlen(p);
 618
 619         for(int i = 2; i < len-2; i++) // skip the endpoints, they aren't accurate
 620         {
 621                 CPoint p1 = pa[0] - pa[i], p2 = pa[len-1] - pa[i];
 622                 double l1 = vectlen(p1), l2 = vectlen(p2);
 623                 int sign = p1.x*p.y-p1.y*p.x >= 0 ? 1 : -1;
 624
 625                 double c = (1.0*len/2 - fabs(i - 1.0*len/2)) / len * 2; // c: 0 -> 1 -> 0
 626
 627                 double cosfi = (1+(p1.x*p2.x+p1.y*p2.y)/(l1*l2)) * sign * c;
 628                 if(mincf > cosfi) mincf = cosfi;
 629                 if(maxcf < cosfi) maxcf = cosfi;
 630         }
 631
 632         return(true);
 633 }
 634
 635 static bool FitBezierVH(COutline& o, CPoint& p1, CPoint& p2)
 636 {
 637         int i;
 638
 639         CAtlArray<CPoint>& pa = o.pa;
 640
 641         int len = (int)pa.GetCount();
 642
 643         if(len <= 1)
 644         {
 645                 return(false);
 646         }
 647         else if(len == 2)
 648         {
 649                 CPoint mid = pa[0]+pa[1];
 650                 mid.x >>= 1;
 651                 mid.y >>= 1;
 652                 p1 = p2 = mid;
 653                 return(true);
 654         }
 655
 656         CPoint dir1 = pa[1] - pa[0], dir2 = pa[len-2] - pa[len-1];
 657         if((dir1.x&&dir1.y)||(dir2.x&&dir2.y))
 658                 return(false); // we are only fitting beziers with hor./ver. endings
 659
 660         if(CalcPossibleCurveDegree(o) > 3)
 661                 return(false);
 662
 663         double mincf, maxcf;
 664         if(MinMaxCosfi(o, mincf, maxcf))
 665         {
 666                 if(maxcf-mincf > 0.8
 667                 || maxcf-mincf > 0.6 && (maxcf >= 0.4 || mincf <= -0.4))
 668                         return(false);
 669         }
 670
 671         CPoint p0 = p1 = pa[0];
 672         CPoint p3 = p2 = pa[len-1];
 673
 674         CAtlArray<double> pl;
 675         pl.SetCount(len);
 676
 677         double c10 = 0, c11 = 0, c12 = 0, c13 = 0, c1x = 0, c1y = 0;
 678         double c20 = 0, c21 = 0, c22 = 0, c23 = 0, c2x = 0, c2y = 0;
 679         double length = 0;
 680
 681         for(pl[0] = 0, i = 1; i < len; i++)
 682         {
 683                 CPoint diff = (pa[i] - pa[i-1]);
 684                 pl[i] = (length += sqrt((double)(diff.x*diff.x+diff.y*diff.y)));
 685         }
 686
 687         for(i = 0; i < len; i++)
 688         {
 689                 double t1 = pl[i] / length;
 690                 double t2 = t1*t1;
 691                 double t3 = t2*t1;
 692                 double it1 = 1 - t1;
 693                 double it2 = it1*it1;
 694                 double it3 = it2*it1;
 695
 696                 double dc1 = 3.0*it2*t1;
 697                 double dc2 = 3.0*it1*t2;
 698
 699                 c10 += it3*dc1;
 700                 c11 += dc1*dc1;
 701                 c12 += dc2*dc1;
 702                 c13 += t3*dc1;
 703                 c1x += pa[i].x*dc1;
 704                 c1y += pa[i].y*dc1;
 705
 706                 c20 += it3*dc2;
 707                 c21 += dc1*dc2;
 708                 c22 += dc2*dc2;
 709                 c23 += t3*dc2;
 710                 c2x += pa[i].x*dc2;
 711                 c2y += pa[i].y*dc2;
 712         }
 713
 714         if(dir1.y == 0 && dir2.x == 0)
 715         {
 716                 p1.x = (int)((c1x - c10*p0.x - c12*p3.x - c13*p3.x) / c11 + 0.5);
 717                 p2.y = (int)((c2y - c20*p0.y - c21*p0.y - c23*p3.y) / c22 + 0.5);
 718         }
 719         else if(dir1.x == 0 && dir2.y == 0)
 720         {
 721                 p2.x = (int)((c2x - c20*p0.x - c21*p0.x - c23*p3.x) / c22 + 0.5);
 722                 p1.y = (int)((c1y - c10*p0.y - c12*p3.y - c13*p3.y) / c11 + 0.5);
 723         }
 724         else if(dir1.y == 0 && dir2.y == 0)
 725         {
 726                 // cramer's rule
 727                 double D = c11*c22 - c12*c21;
 728                 p1.x = (int)(((c1x-c10*p0.x-c13*p3.x)*c22 - c12*(c2x-c20*p0.x-c23*p3.x)) / D + 0.5);
 729                 p2.x = (int)((c11*(c2x-c20*p0.x-c23*p3.x) - (c1x-c10*p0.x-c13*p3.x)*c21) / D + 0.5);
 730         }
 731         else if(dir1.x == 0 && dir2.x == 0)
 732         {
 733                 // cramer's rule
 734                 double D = c11*c22 - c12*c21;
 735                 p1.y = (int)(((c1y-c10*p0.y-c13*p3.y)*c22 - c12*(c2y-c20*p0.y-c23*p3.y)) / D + 0.5);
 736                 p2.y = (int)((c11*(c2y-c20*p0.y-c23*p3.y) - (c1y-c10*p0.y-c13*p3.y)*c21) / D + 0.5);
 737         }
 738         else // must not happen
 739         {
 740                 ASSERT(0);
 741                 return(false);
 742         }
 743
 744         // check for "inside-out" beziers
 745         CPoint dir3 = p1 - p0, dir4 = p2 - p3;
 746         if((dir1.x*dir3.x+dir1.y*dir3.y) <= 0 || (dir2.x*dir4.x+dir2.y*dir4.y) <= 0)
 747                 return(false);
 748
 749         return(true);
 750 }
 751
 752 int CVobSubImage::GrabSegment(int start, COutline& o, COutline& ret)
 753 {
 754         ret.RemoveAll();
 755
 756         int len = o.pa.GetCount();
 757
 758         int cur = (start)%len, first = -1, last = -1;
 759         int curDir = 0, lastDir = 0;
 760
 761         for(int i = 0; i < len; i++)
 762         {
 763                 cur = (cur+1)%len;
 764
 765                 if(o.da[cur] == 0) continue;
 766
 767                 if(first == -1) first = cur;
 768
 769                 if(lastDir == o.da[cur])
 770                 {
 771                         CPoint startp = o.pa[first]+o.pa[start]; startp.x >>= 1; startp.y >>= 1;
 772                         CPoint endp = o.pa[last]+o.pa[cur]; endp.x >>= 1; endp.y >>= 1;
 773
 774                         if(first < start) first += len;
 775                         start = ((start+first)>>1)+1;
 776                         if(start >= len) start -= len;
 777                         if(cur < last) cur += len;
 778                         cur = ((last+cur+1)>>1);
 779                         if(cur >= len) cur -= len;
 780
 781                         ret.Add(startp, 0);
 782
 783                         while(start != cur)
 784                         {
 785                                 ret.Add(o.pa[start], o.da[start]);
 786
 787                                 start++;
 788                                 if(start >= len) start -= len;
 789                         }
 790
 791                         ret.Add(endp, 0);
 792
 793                         return(last);
 794                 }
 795
 796                 lastDir = o.da[cur];
 797                 last = cur;
 798         }
 799
 800         ASSERT(0);
 801
 802         return(start);
 803 }
 804
 805 void CVobSubImage::SplitOutline(COutline& o, COutline& o1, COutline& o2)
 806 {
 807         int len = o.pa.GetCount();
 808         if(len < 4) return;
 809
 810         CAtlArray<UINT> la, sa, ea;
 811
 812         int i, j, k;
 813
 814         for(i = 0, j = 0; j < len; j++)
 815         {
 816                 if(j == len-1 || o.da[j])
 817                 {
 818                         la.Add(j-i);
 819                         sa.Add(i);
 820                         ea.Add(j);
 821                         i = j;
 822                 }
 823         }
 824
 825         int maxlen = 0, maxidx = -1;
 826         int maxlen2 = 0, maxidx2 = -1;
 827
 828         for(i = 0; i < la.GetCount(); i++)
 829         {
 830                 if(maxlen < la[i])
 831                 {
 832                         maxlen = la[i];
 833                         maxidx = i;
 834                 }
 835
 836                 if(maxlen2 < la[i] && i > 0 && i < la.GetCount()-1)
 837                 {
 838                         maxlen2 = la[i];
 839                         maxidx2 = i;
 840                 }
 841         }
 842
 843         if(maxlen == maxlen2) maxidx = maxidx2; // if equal choose the inner section
 844
 845         j = (sa[maxidx] + ea[maxidx]) >> 1, k = (sa[maxidx] + ea[maxidx] + 1) >> 1;
 846
 847         o1.RemoveAll();
 848         o2.RemoveAll();
 849
 850         for(i = 0; i <= j; i++)
 851                 o1.Add(o.pa[i], o.da[i]);
 852
 853         if(j != k)
 854         {
 855                 CPoint mid = o.pa[j]+o.pa[k]; mid.x >>= 1; mid.y >>= 1;
 856                 o1.Add(mid, 0);
 857                 o2.Add(mid, 0);
 858         }
 859
 860         for(i = k; i < len; i++)
 861                 o2.Add(o.pa[i], o.da[i]);
 862 }
 863
 864 void CVobSubImage::AddSegment(COutline& o, CAtlArray<BYTE>& pathTypes, CAtlArray<CPoint>& pathPoints)
 865 {
 866         int i, len = o.pa.GetCount();
 867         if(len < 3) return;
 868
 869         int nLeftTurns = 0, nRightTurns = 0;
 870
 871         for(i = 0; i < len; i++)
 872         {
 873                 if(o.da[i] == -1) nLeftTurns++;
 874                 else if(o.da[i] == 1) nRightTurns++;
 875         }
 876
 877         if(nLeftTurns == 0 && nRightTurns == 0) // line
 878         {
 879                 pathTypes.Add(PT_LINETO);
 880                 pathPoints.Add(o.pa[len-1]);
 881
 882                 return;
 883         }
 884
 885         if(nLeftTurns == 0 || nRightTurns == 0) // b-spline
 886         {
 887                 pathTypes.Add(PT_MOVETONC);
 888                 pathPoints.Add(o.pa[0]+(o.pa[0]-o.pa[1]));
 889
 890                 for(i = 0; i < 3; i++)
 891                 {
 892                         pathTypes.Add(PT_BSPLINETO);
 893                         pathPoints.Add(o.pa[i]);
 894                 }
 895
 896                 for(; i < len; i++)
 897                 {
 898                         pathTypes.Add(PT_BSPLINEPATCHTO);
 899                         pathPoints.Add(o.pa[i]);
 900                 }
 901
 902                 pathTypes.Add(PT_BSPLINEPATCHTO);
 903                 pathPoints.Add(o.pa[len-1]+(o.pa[len-1]-o.pa[len-2]));
 904
 905                 pathTypes.Add(PT_MOVETONC);
 906                 pathPoints.Add(o.pa[len-1]);
 907
 908                 return;
 909         }
 910
 911         int start, end;
 912         if(FitLine(o, start, end)) // b-spline, line, b-spline
 913         {
 914                 pathTypes.Add(PT_MOVETONC);
 915                 pathPoints.Add(o.pa[0]+(o.pa[0]-o.pa[1]));
 916
 917                 pathTypes.Add(PT_BSPLINETO);
 918                 pathPoints.Add(o.pa[0]);
 919
 920                 pathTypes.Add(PT_BSPLINETO);
 921                 pathPoints.Add(o.pa[1]);
 922
 923                 CPoint p[4], pp, d = o.pa[end] - o.pa[start];
 924                 double l = sqrt((double)(d.x*d.x+d.y*d.y)), dx = 1.0 * d.x / l, dy = 1.0 * d.y / l;
 925
 926                 pp = o.pa[start]-o.pa[start-1];
 927                 double l1 = abs(pp.x)+abs(pp.y);
 928                 pp = o.pa[end]-o.pa[end+1];
 929                 double l2 = abs(pp.x)+abs(pp.y);
 930                 p[0] = CPoint((int)(1.0 * o.pa[start].x + dx*l1 + 0.5), (int)(1.0 * o.pa[start].y + dy*l1 + 0.5));
 931                 p[1] = CPoint((int)(1.0 * o.pa[start].x + dx*l1*2 + 0.5), (int)(1.0 * o.pa[start].y + dy*l1*2 + 0.5));
 932                 p[2] = CPoint((int)(1.0 * o.pa[end].x - dx*l2*2 + 0.5), (int)(1.0 * o.pa[end].y - dy*l2*2 + 0.5));
 933                 p[3] = CPoint((int)(1.0 * o.pa[end].x - dx*l2 + 0.5), (int)(1.0 * o.pa[end].y - dy*l2 + 0.5));
 934
 935                 if(start == 1)
 936                 {
 937                         pathTypes.Add(PT_BSPLINETO);
 938                         pathPoints.Add(p[0]);
 939                 }
 940                 else
 941                 {
 942                         pathTypes.Add(PT_BSPLINETO);
 943                         pathPoints.Add(o.pa[2]);
 944
 945                         for(int i = 3; i <= start; i++)
 946                         {
 947                                 pathTypes.Add(PT_BSPLINEPATCHTO);
 948                                 pathPoints.Add(o.pa[i]);
 949                         }
 950
 951                         pathTypes.Add(PT_BSPLINEPATCHTO);
 952                         pathPoints.Add(p[0]);
 953                 }
 954
 955                 pathTypes.Add(PT_BSPLINEPATCHTO);
 956                 pathPoints.Add(p[1]);
 957
 958                 pathTypes.Add(PT_MOVETONC);
 959                 pathPoints.Add(p[0]);
 960
 961                 pathTypes.Add(PT_LINETO);
 962                 pathPoints.Add(p[3]);
 963
 964                 pathTypes.Add(PT_MOVETONC);
 965                 pathPoints.Add(p[2]);
 966
 967                 pathTypes.Add(PT_BSPLINEPATCHTO);
 968                 pathPoints.Add(p[3]);
 969
 970                 for(i = end; i < len; i++)
 971                 {
 972                         pathTypes.Add(PT_BSPLINEPATCHTO);
 973                         pathPoints.Add(o.pa[i]);
 974                 }
 975
 976                 pathTypes.Add(PT_BSPLINEPATCHTO);
 977                 pathPoints.Add(o.pa[len-1]+(o.pa[len-1]-o.pa[len-2]));
 978
 979                 pathTypes.Add(PT_MOVETONC);
 980                 pathPoints.Add(o.pa[len-1]);
 981
 982                 return;
 983         }
 984
 985         CPoint p1, p2;
 986         if(FitBezierVH(o, p1, p2)) // bezier
 987         {
 988                 pathTypes.Add(PT_BEZIERTO);
 989                 pathPoints.Add(p1);
 990                 pathTypes.Add(PT_BEZIERTO);
 991                 pathPoints.Add(p2);
 992                 pathTypes.Add(PT_BEZIERTO);
 993                 pathPoints.Add(o.pa[o.pa.GetCount()-1]);
 994
 995                 return;
 996         }
 997
 998         COutline o1, o2;
 999         SplitOutline(o, o1, o2);
1000         AddSegment(o1, pathTypes, pathPoints);
1001         AddSegment(o2, pathTypes, pathPoints);
1002 }
1003
1004 bool CVobSubImage::Polygonize(CAtlArray<BYTE>& pathTypes, CAtlArray<CPoint>& pathPoints, bool fSmooth, int scale)
1005 {
1006         CPoint topleft;
1007         CAutoPtr<CAutoPtrList<COutline> > ol(GetOutlineList(topleft));
1008         if(!ol) return(false);
1009
1010         POSITION pos;
1011
1012         pos = ol->GetHeadPosition();
1013         while(pos)
1014         {
1015                 CAtlArray<CPoint>& pa = ol->GetNext(pos)->pa;
1016                 for(size_t i = 0; i < pa.GetCount(); i++)
1017                 {
1018                         pa[i].x = (pa[i].x-topleft.x)<<scale;
1019                         pa[i].y = (pa[i].y-topleft.y)<<scale;
1020                 }
1021         }
1022
1023         pos = ol->GetHeadPosition();
1024         while(pos)
1025         {
1026                 COutline& o = *ol->GetNext(pos), o2;
1027
1028                 if(fSmooth)
1029                 {
1030                         int i = 0, iFirst = -1;
1031
1032                         while(1)
1033                         {
1034                                 i = GrabSegment(i, o, o2);
1035
1036                                 if(i == iFirst) break;
1037
1038                                 if(iFirst < 0)
1039                                 {
1040                                         iFirst = i;
1041                                         pathTypes.Add(PT_MOVETO);
1042                                         pathPoints.Add(o2.pa[0]);
1043                                 }
1044
1045                                 AddSegment(o2, pathTypes, pathPoints);
1046                         }
1047                 }
1048                 else
1049                 {
1050 /*
1051                         for(int i = 1, len = o.pa.GetSize(); i < len; i++)
1052                         {
1053                 if(int dir = o.da[i-1])
1054                                 {
1055                                         CPoint dir2 = o.pa[i] - o.pa[i-1];
1056                                         dir2.x /= 2; dir2.y /= 2;
1057                                         CPoint dir1 = dir > 0 ? CPoint(dir2.y, -dir2.x) : CPoint(-dir2.y, dir2.x);
1058                                         i = i;
1059                                         o.pa[i-1] -= dir1;
1060                                         o.pa.InsertAt(i, o.pa[i-1] + dir2);
1061                                         o.da.InsertAt(i, -dir);
1062                                         o.pa.InsertAt(i+1, o.pa[i] + dir1);
1063                                         o.da.InsertAt(i+1, dir);
1064                                         i += 2;
1065                                         len += 2;
1066                                 }
1067                         }
1068 */
1069                         pathTypes.Add(PT_MOVETO);
1070                         pathPoints.Add(o.pa[0]);
1071
1072                         for(int i = 1, len = o.pa.GetCount(); i < len; i++)
1073                         {
1074                                 pathTypes.Add(PT_LINETO);
1075                                 pathPoints.Add(o.pa[i]);
1076                         }
1077                 }
1078         }
1079
1080         return !pathTypes.IsEmpty();
1081 }
1082
1083 bool CVobSubImage::Polygonize(CStringW& assstr, bool fSmooth, int scale)
1084 {
1085         CAtlArray<BYTE> pathTypes;
1086         CAtlArray<CPoint> pathPoints;
1087
1088         if(!Polygonize(pathTypes, pathPoints, fSmooth, scale))
1089                 return(false);
1090
1091         assstr.Format(L"{\\an7\\pos(%d,%d)\\p%d}", rect.left, rect.top, 1+scale);
1092 //      assstr.Format(L"{\\p%d}", 1+scale);
1093
1094         BYTE lastType = 0;
1095
1096         int nPoints = pathTypes.GetCount();
1097
1098         for(int i = 0; i < nPoints; i++)
1099         {
1100                 CStringW s;
1101
1102                 switch(pathTypes[i])
1103                 {
1104                 case PT_MOVETO:
1105                         if(lastType != PT_MOVETO) assstr += L"m ";
1106                         s.Format(L"%d %d ", pathPoints[i].x, pathPoints[i].y);
1107                         break;
1108                 case PT_MOVETONC:
1109                         if(lastType != PT_MOVETONC) assstr += L"n ";
1110                         s.Format(L"%d %d ", pathPoints[i].x, pathPoints[i].y);
1111                         break;
1112                 case PT_LINETO:
1113                         if(lastType != PT_LINETO) assstr += L"l ";
1114                         s.Format(L"%d %d ", pathPoints[i].x, pathPoints[i].y);
1115                         break;
1116                 case PT_BEZIERTO:
1117                         if(i < nPoints-2)
1118                         {
1119                                 if(lastType != PT_BEZIERTO) assstr += L"b ";
1120                                 s.Format(L"%d %d %d %d %d %d ", pathPoints[i].x, pathPoints[i].y, pathPoints[i+1].x, pathPoints[i+1].y, pathPoints[i+2].x, pathPoints[i+2].y);
1121                                 i+=2;
1122                         }
1123                         break;
1124                 case PT_BSPLINETO:
1125                         if(i < nPoints-2)
1126                         {
1127                                 if(lastType != PT_BSPLINETO) assstr += L"s ";
1128                                 s.Format(L"%d %d %d %d %d %d ", pathPoints[i].x, pathPoints[i].y, pathPoints[i+1].x, pathPoints[i+1].y, pathPoints[i+2].x, pathPoints[i+2].y);
1129                                 i+=2;
1130                         }
1131                         break;
1132                 case PT_BSPLINEPATCHTO:
1133                         if(lastType != PT_BSPLINEPATCHTO) assstr += L"p ";
1134                         s.Format(L"%d %d ", pathPoints[i].x, pathPoints[i].y);
1135                         break;
1136                 }
1137
1138                 lastType = pathTypes[i];
1139
1140                 assstr += s;
1141         }
1142
1143         assstr += L"{\\p0}";
1144
1145         return nPoints > 0;
1146 }
1147
1148 void CVobSubImage::Scale2x()
1149 {
1150         int w = rect.Width(), h = rect.Height();
1151
1152         DWORD* src = (DWORD*)lpPixels;
1153         DWORD* dst = new DWORD[w*h];
1154
1155         for(int y = 0; y < h; y++)
1156         {
1157                 for(int x = 0; x < w; x++, src++, dst++)
1158                 {
1159                         DWORD E = *src;
1160
1161                         DWORD A = x > 0 && y > 0 ? src[-w-1] : E;
1162                         DWORD B = y > 0 ? src[-w] : E;
1163                         DWORD C = x < w-1 && y > 0 ? src[-w+1] : E;
1164
1165                         DWORD D = x > 0 ? src[-1] : E;;
1166                         DWORD F = x < w-1 ? src[+1] : E;;
1167
1168                         DWORD G = x > 0 && y < h-1 ? src[+w-1] : E;
1169                         DWORD H = y < h-1 ? src[+w] : E;
1170                         DWORD I = x < w-1 && y < h-1 ? src[+w+1] : E;
1171
1172                         DWORD E0 = D == B && B != F && D != H ? D : E;
1173                         DWORD E1 = B == F && B != D && F != H ? F : E;
1174                         DWORD E2 = D == H && D != B && H != F ? D : E;
1175                         DWORD E3 = H == F && D != H && B != F ? F : E;
1176
1177                         *dst = ((((E0&0x00ff00ff)+(E1&0x00ff00ff)+(E2&0x00ff00ff)+(E3&0x00ff00ff)+2)>>2)&0x00ff00ff)
1178                                 | (((((E0>>8)&0x00ff00ff)+((E1>>8)&0x00ff00ff)+((E2>>8)&0x00ff00ff)+((E3>>8)&0x00ff00ff)+2)<<6)&0xff00ff00);
1179                 }
1180         }
1181
1182         src -= w*h;
1183         dst -= w*h;
1184
1185         memcpy(src, dst, w*h*4);
1186
1187         delete [] dst;
1188 }