- Main Page
- Namespaces
- Classes
- Files
- Directories

- File List
- File Members

# VobSubImage.cpp

    00001 /*
    00002  *      Copyright (C) 2003-2005 Gabest
    00003  *      http://www.gabest.org
    00004  *
    00005  *  This Program is free software; you can redistribute it and/or modify
    00006  *  it under the terms of the GNU General Public License as published by
    00007  *  the Free Software Foundation; either version 2, or (at your option)
    00008  *  any later version.
    00009  *
    00010  *  This Program is distributed in the hope that it will be useful,
    00011  *  but WITHOUT ANY WARRANTY; without even the implied warranty of
    00012  *  MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
    00013  *  GNU General Public License for more details.
    00014  *
    00015  *  You should have received a copy of the GNU General Public License
    00016  *  along with GNU Make; see the file COPYING.  If not, write to
    00017  *  the Free Software Foundation, 675 Mass Ave, Cambridge, MA 02139, USA.
    00018  *  http://www.gnu.org/copyleft/gpl.html
    00019  *
    00020  */
    00021
    00022 #include "stdafx.h"
    00023 #include "VobSubImage.h"
    00024
    00025 CVobSubImage::CVobSubImage()
    00026 {
    00027         iLang = iIdx = -1;
    00028         fForced = false;
    00029         start = delay = 0;
    00030         rect = CRect(0,0,0,0);
    00031         lpPixels = lpTemp1 = lpTemp2 = NULL;
    00032         org = CSize(0,0);
    00033 }
    00034
    00035 CVobSubImage::~CVobSubImage()
    00036 {
    00037         Free();
    00038 }
    00039
    00040 bool CVobSubImage::Alloc(int w, int h)
    00041 {
    00042         // if there is nothing to crop TrimSubImage might even add a 1 pixel
    00043         // wide border around the text, that's why we need a bit more memory
    00044         // to be allocated.
    00045
    00046         if(lpTemp1 == NULL || w*h > org.cx*org.cy)
    00047         {
    00048                 Free();
    00049
    00050                 lpTemp1 = new RGBQUAD[w*h];
    00051                 if(!lpTemp1) return(false);
    00052
    00053                 lpTemp2 = new RGBQUAD[(w+2)*(h+2)];
    00054                 if(!lpTemp2) {delete [] lpTemp1; lpTemp1 = NULL; return(false);}
    00055
    00056                 org.cx = w;
    00057                 org.cy = h;
    00058         }
    00059
    00060         lpPixels = lpTemp1;
    00061
    00062         return(true);
    00063 }
    00064
    00065 void CVobSubImage::Free()
    00066 {
    00067         if(lpTemp1) delete [] lpTemp1;
    00068         lpTemp1 = NULL;
    00069
    00070         if(lpTemp2) delete [] lpTemp2;
    00071         lpTemp2 = NULL;
    00072
    00073         lpPixels = NULL;
    00074 }
    00075
    00076 bool CVobSubImage::Decode(BYTE* lpData, int packetsize, int datasize,
    00077                                                   bool fCustomPal,
    00078                                                   int tridx,
    00079                                                   RGBQUAD* orgpal /*[16]*/, RGBQUAD* cuspal /*[4]*/,
    00080                                                   bool fTrim)
    00081 {
    00082         GetPacketInfo(lpData, packetsize, datasize);
    00083
    00084         if(!Alloc(rect.Width(), rect.Height())) return(false);
    00085
    00086         lpPixels = lpTemp1;
    00087
    00088         nPlane = 0;
    00089         fAligned = 1;
    00090
    00091         this->fCustomPal = fCustomPal;
    00092         this->orgpal = orgpal;
    00093         this->tridx = tridx;
    00094         this->cuspal = cuspal;
    00095
    00096         CPoint p(rect.left, rect.top);
    00097
    00098         int end0 = nOffset[1];
    00099         int end1 = datasize;
    00100
    00101         while((nPlane == 0 && nOffset[0] < end0) || (nPlane == 1 && nOffset[1] < end1))
    00102         {
    00103                 DWORD code;
    00104
    00105                 if((code = GetNibble(lpData)) >= 0x4
    00106                 || (code = (code << 4) | GetNibble(lpData)) >= 0x10
    00107                 || (code = (code << 4) | GetNibble(lpData)) >= 0x40
    00108                 || (code = (code << 4) | GetNibble(lpData)) >= 0x100)
    00109                 {
    00110                         DrawPixels(p, code >> 2, code & 3);
    00111                         if((p.x += code >> 2) < rect.right) continue;
    00112                 }
    00113
    00114                 DrawPixels(p, rect.right - p.x, code & 3);
    00115
    00116                 if(!fAligned) GetNibble(lpData); // align to byte
    00117
    00118                 p.x = rect.left;
    00119                 p.y++;
    00120                 nPlane = 1 - nPlane;
    00121         }
    00122
    00123         rect.bottom = min(p.y, rect.bottom);
    00124
    00125         if(fTrim) TrimSubImage();
    00126
    00127         return(true);
    00128 }
    00129
    00130 void CVobSubImage::GetPacketInfo(BYTE* lpData, int packetsize, int datasize)
    00131 {
    00132 //      delay = 0;
    00133
    00134         int i, nextctrlblk = datasize;
    00135         WORD pal, tr;
    00136
    00137         do
    00138         {
    00139                 i = nextctrlblk;
    00140
    00141                 int t = (lpData[i] << 8) | lpData[i+1]; i += 2;
    00142                 nextctrlblk = (lpData[i] << 8) | lpData[i+1]; i += 2;
    00143
    00144                 if(nextctrlblk > packetsize || nextctrlblk < datasize)
    00145                 {
    00146                         ASSERT(0);
    00147                         return;
    00148                 }
    00149
    00150                 bool fBreak = false;
    00151
    00152                 while(!fBreak)
    00153                 {
    00154                         int len = 0;
    00155
    00156                         switch(lpData[i])
    00157                         {
    00158                                 case 0x00: len = 0; break;
    00159                                 case 0x01: len = 0; break;
    00160                                 case 0x02: len = 0; break;
    00161                                 case 0x03: len = 2; break;
    00162                                 case 0x04: len = 2; break;
    00163                                 case 0x05: len = 6; break;
    00164                                 case 0x06: len = 4; break;
    00165                                 default: len = 0; break;
    00166                         }
    00167
    00168                         if(i+len >= packetsize)
    00169                         {
    00170                                 TRACE(_T("Warning: Wrong subpicture parameter block ending\n"));
    00171                                 break;
    00172                         }
    00173
    00174                         switch(lpData[i++])
    00175                         {
    00176                                 case 0x00: // forced start displaying
    00177                                         fForced = true;
    00178                                         break;
    00179                                 case 0x01: // start displaying
    00180                                         fForced = false;
    00181                                         break;
    00182                                 case 0x02: // stop displaying
    00183                                         delay = 1024 * t / 90;
    00184                                         break;
    00185                                 case 0x03:
    00186                                         pal = (lpData[i] << 8) | lpData[i+1]; i += 2;
    00187                                         break;
    00188                                 case 0x04:
    00189                                         tr = (lpData[i] << 8) | lpData[i+1]; i += 2;
    00190 //tr &= 0x00f0;
    00191                                         break;
    00192                                 case 0x05:
    00193                                         rect = CRect((lpData[i] << 4) + (lpData[i+1] >> 4),
    00194                                                 (lpData[i+3] << 4) + (lpData[i+4] >> 4),
    00195                                                 ((lpData[i+1] & 0x0f) << 8) + lpData[i+2] + 1,
    00196                                                 ((lpData[i+4] & 0x0f) << 8) + lpData[i+5] + 1);
    00197                                         i += 6;
    00198                                         break;
    00199                                 case 0x06:
    00200                                         nOffset[0] = (lpData[i] << 8) + lpData[i+1]; i += 2;
    00201                                         nOffset[1] = (lpData[i] << 8) + lpData[i+1]; i += 2;
    00202                                         break;
    00203                                 case 0xff: // end of ctrlblk
    00204                                         fBreak = true;
    00205                                         continue;
    00206                                 default: // skip this ctrlblk
    00207                                         fBreak = true;
    00208                                         break;
    00209                         }
    00210                 }
    00211         }
    00212         while(i <= nextctrlblk && i < packetsize);
    00213
    00214         for(i = 0; i < 4; i++)
    00215         {
    00216                 this->pal[i].pal = (pal >> (i << 2)) & 0xf;
    00217                 this->pal[i].tr = (tr >> (i << 2)) & 0xf;
    00218         }
    00219 }
    00220
    00221 BYTE CVobSubImage::GetNibble(BYTE* lpData)
    00222 {
    00223         WORD& off = nOffset[nPlane];
    00224         BYTE ret = (lpData[off] >> (fAligned << 2)) & 0x0f;
    00225         fAligned = !fAligned;
    00226         off += fAligned;
    00227         return(ret);
    00228 }
    00229
    00230 void CVobSubImage::DrawPixels(CPoint p, int length, int colorid)
    00231 {
    00232         if(length <= 0
    00233         || p.x + length < rect.left
    00234         || p.x >= rect.right
    00235         || p.y < rect.top
    00236         || p.y >= rect.bottom)
    00237         {
    00238                 return;
    00239         }
    00240
    00241         if(p.x < rect.left) p.x = rect.left;
    00242         if(p.x + length >= rect.right) length = rect.right - p.x;
    00243
    00244         RGBQUAD* ptr = &lpPixels[rect.Width() * (p.y - rect.top) + (p.x - rect.left)];
    00245
    00246         RGBQUAD c;
    00247
    00248         if(!fCustomPal)
    00249         {
    00250                 c = orgpal[pal[colorid].pal];
    00251                 c.rgbReserved = (pal[colorid].tr<<4)|pal[colorid].tr;
    00252         }
    00253         else
    00254         {
    00255                 c = cuspal[colorid];
    00256         }
    00257
    00258         while(length-- > 0) *ptr++ = c;
    00259 }
    00260
    00261 void CVobSubImage::TrimSubImage()
    00262 {
    00263         CRect r;
    00264         r.left = rect.Width();
    00265         r.top = rect.Height();
    00266         r.right = 0;
    00267         r.bottom = 0;
    00268
    00269         RGBQUAD* ptr = lpTemp1;
    00270
    00271         for(int j = 0, y = rect.Height(); j < y; j++)
    00272         {
    00273                 for(int i = 0, x = rect.Width(); i < x; i++, ptr++)
    00274                 {
    00275                         if(ptr->rgbReserved)
    00276                         {
    00277                                 if(r.top > j) r.top = j;
    00278                                 if(r.bottom < j) r.bottom = j;
    00279                                 if(r.left > i) r.left = i;
    00280                                 if(r.right < i) r.right = i;
    00281                         }
    00282                 }
    00283         }
    00284
    00285         if(r.left > r.right || r.top > r.bottom) return;
    00286
    00287         r += CRect(0, 0, 1, 1);
    00288
    00289         r &= CRect(CPoint(0,0), rect.Size());
    00290
    00291         int w = r.Width(), h = r.Height();
    00292
    00293         DWORD offset = r.top*rect.Width() + r.left;
    00294
    00295         r += CRect(1, 1, 1, 1);
    00296
    00297         DWORD* src = (DWORD*)&lpTemp1[offset];
    00298         DWORD* dst = (DWORD*)&lpTemp2[1 + w + 1];
    00299
    00300         memset(lpTemp2, 0, (1 + w + 1)*sizeof(RGBQUAD));
    00301
    00302         for(int height = h; height; height--, src += rect.Width())
    00303         {
    00304                 *dst++ = 0;
    00305                 memcpy(dst, src, w*sizeof(RGBQUAD)); dst += w;
    00306                 *dst++ = 0;
    00307         }
    00308
    00309         memset(dst, 0, (1 + w + 1)*sizeof(RGBQUAD));
    00310
    00311         lpPixels = lpTemp2;
    00312
    00313         rect = r + rect.TopLeft();
    00314 }
    00315
    00317
    00318 #include "RTS.h"
    00319 #include <math.h>
    00320
    00321 #define GP(xx, yy) (((xx) < 0 || (yy) < 0 || (xx) >= w || (yy) >= h) ? 0 : p[(yy)*w+(xx)])
    00322
    00323 COutlineList* CVobSubImage::GetOutlineList(CPoint& topleft)
    00324 {
    00325         int w = rect.Width(), h = rect.Height(), len = w*h;
    00326         if(len <= 0) return NULL;
    00327
    00328         CAutoVectorPtr<BYTE> p;
    00329         if(!p.Allocate(len)) return NULL;
    00330
    00331         COutlineList* ol = new COutlineList();
    00332         if(!ol) return NULL;
    00333
    00334         BYTE* cp = p;
    00335         RGBQUAD* rgbp = (RGBQUAD*)lpPixels;
    00336
    00337         for(int i = 0; i < len; i++, cp++, rgbp++)
    00338                 *cp = !!rgbp->rgbReserved;
    00339
    00340         enum {UP, RIGHT, DOWN, LEFT};
    00341
    00342         topleft.x = topleft.y = INT_MAX;
    00343
    00344         while(1)
    00345         {
    00346                 cp = p;
    00347
    00348                 int x, y;
    00349
    00350                 for(y = 0; y < h; y++)
    00351                 {
    00352                         for(x = 0; x < w-1; x++, cp++)
    00353                         {
    00354                                 if(cp[0] == 0 && cp[1] == 1) break;
    00355                         }
    00356
    00357                         if(x < w-1) break;
    00358
    00359                         cp++;
    00360                 }
    00361
    00362                 if(y == h) break;
    00363
    00364                 int prevdir, dir = UP;
    00365
    00366                 int ox = x, oy = y, odir = dir;
    00367
    00368                 CAutoPtr<COutline> o(new COutline);
    00369                 if(!o) break;
    00370
    00371                 do
    00372                 {
    00373                         CPoint pp;
    00374                         BYTE fl, fr, br;
    00375
    00376                         prevdir = dir;
    00377
    00378                         switch(prevdir)
    00379                         {
    00380                         case UP:
    00381                                 pp = CPoint(x+1, y);
    00382                                 fl = GP(x, y-1);
    00383                                 fr = GP(x+1, y-1);
    00384                                 br = GP(x+1, y);
    00385                                 break;
    00386                         case RIGHT:
    00387                                 pp = CPoint(x+1, y+1);
    00388                                 fl = GP(x+1, y);
    00389                                 fr = GP(x+1, y+1);
    00390                                 br = GP(x, y+1);
    00391                                 break;
    00392                         case DOWN:
    00393                                 pp = CPoint(x, y+1);
    00394                                 fl = GP(x, y+1);
    00395                                 fr = GP(x-1, y+1);
    00396                                 br = GP(x-1, y);
    00397                                 break;
    00398                         case LEFT:
    00399                                 pp = CPoint(x, y);
    00400                                 fl = GP(x-1, y);
    00401                                 fr = GP(x-1, y-1);
    00402                                 br = GP(x, y-1);
    00403                                 break;
    00404                         }
    00405
    00406                         // turning left if:
    00407                         // o . | o .
    00408                         // ^ o | < o
    00409                         // turning right if:
    00410                         // x x | x >
    00411                         // ^ o | x o
    00412                         //
    00413                         // o set, x empty, . can be anything
    00414
    00415                         if(fl==1) dir = (dir-1+4)&3;
    00416                         else if(fl!=1 && fr!=1 && br==1) dir = (dir+1)&3;
    00417                         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)
    00418
    00419                         p[y*w+x] = (p[y*w+x]<<1) | 2; // increase turn count (== log2(highordbit(*p)))
    00420
    00421                         switch(dir)
    00422                         {
    00423                         case UP:
    00424                                 if(prevdir == LEFT) {x--; y--;}
    00425                                 if(prevdir == UP) y--;
    00426                                 break;
    00427                         case RIGHT:
    00428                                 if(prevdir == UP) {x++; y--;}
    00429                                 if(prevdir == RIGHT) x++;
    00430                                 break;
    00431                         case DOWN:
    00432                                 if(prevdir == RIGHT) {x++; y++;}
    00433                                 if(prevdir == DOWN) y++;
    00434                                 break;
    00435                         case LEFT:
    00436                                 if(prevdir == DOWN) {x--; y++;}
    00437                                 if(prevdir == LEFT) x--;
    00438                                 break;
    00439                         }
    00440
    00441                         int d = dir - prevdir;
    00442                         o->Add(pp, d == 3 ? -1 : d == -3 ? 1 : d);
    00443
    00444                         if(topleft.x > pp.x) topleft.x = pp.x;
    00445                         if(topleft.y > pp.y) topleft.y = pp.y;
    00446                 }
    00447                 while(!(x == ox && y == oy && dir == odir));
    00448
    00449                 if(o->pa.GetSize() > 0 && (x == ox && y == oy && dir == odir))
    00450                 {
    00451                         ol->AddTail(o);
    00452                 }
    00453                 else
    00454                 {
    00455                         ASSERT(0);
    00456                 }
    00457         }
    00458
    00459         return(ol);
    00460 }
    00461
    00462 static bool FitLine(COutline& o, int& start, int& end)
    00463 {
    00464         int len = o.pa.GetSize();
    00465         if(len < 7) return(false); // small segments should be handled with beziers...
    00466
    00467         for(start = 0; start < len && !o.da[start]; start++);
    00468         for(end = len-1; end > start && !o.da[end]; end--);
    00469
    00470         if(end-start < 8 || end-start < (len-end)+(start-0)) return(false);
    00471
    00472         CUIntArray la, ra;
    00473
    00474         int i, j, k;
    00475
    00476         for(i = start+1, j = end, k = start; i <= j; i++)
    00477         {
    00478                 if(!o.da[i]) continue;
    00479                 if(o.da[i] == o.da[k]) return(false);
    00480                 if(o.da[i] == -1) la.Add(i-k);
    00481                 else ra.Add(i-k);
    00482                 k = i;
    00483         }
    00484
    00485         bool fl = true, fr = true;
    00486
    00487         // these tests are completly heuristic and might be redundant a bit...
    00488
    00489         for(i = 0, j = la.GetSize(); i < j && fl; i++) {if(la[i] != 1) fl = false;}
    00490         for(i = 0, j = ra.GetSize(); i < j && fr; i++) {if(ra[i] != 1) fr = false;}
    00491
    00492         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)
    00493         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
    00494         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)
    00495         if(!fr && ra.GetSize() > 0 && ra.GetSize() <= 4 && (ra[0] == 1 && ra[ra.GetSize()-1] == 1)) return(false); // -''-
    00496
    00497         CUIntArray& a = !fl ? la : ra;
    00498
    00499         len = a.GetSize();
    00500
    00501         int sum = 0;
    00502
    00503         for(i = 0, j = INT_MAX, k = 0; i < len; i++)
    00504         {
    00505                 if(j > a[i]) j = a[i];
    00506                 if(k < a[i]) k = a[i];
    00507                 sum += a[i];
    00508         }
    00509
    00510         if(k - j > 2 && 1.0*sum/len < 2) return(false);
    00511         if(k - j > 2 && 1.0*sum/len >= 2 && len < 4) return(false);
    00512
    00513         if((la.GetSize()/2+ra.GetSize()/2)/2 <= 2)
    00514         {
    00515                 if((k+j)/2 < 2 && k*j!=1) return(false);
    00516         }
    00517
    00518         double err = 0;
    00519
    00520         CPoint sp = o.pa[start], ep = o.pa[end];
    00521
    00522         double minerr = 0, maxerr = 0;
    00523
    00524         double vx = ep.x - sp.x, vy = ep.y - sp.y, l = sqrt(vx*vx+vy*vy);
    00525         vx /= l; vy /= l;
    00526
    00527         for(i = start+1, j = end-1; i <= j; i++)
    00528         {
    00529                 CPoint p = o.pa[i], dp = p - sp;
    00530                 double t = vx*dp.x+vy*dp.y, dx = vx*t + sp.x - p.x, dy = vy*t + sp.y - p.y;
    00531                 t = dx*dx+dy*dy;
    00532                 err += t;
    00533                 t = sqrt(t);
    00534                 if(vy*dx-dy*vx < 0) {if(minerr > -t) minerr = -t;}
    00535                 else {if(maxerr < t) maxerr = t;}
    00536         }
    00537
    00538         return((maxerr-minerr)/l < 0.1  || err/l < 1.5 || (fabs(maxerr) < 8 && fabs(minerr) < 8));
    00539 }
    00540
    00541 static int CalcPossibleCurveDegree(COutline& o)
    00542 {
    00543         int len2 = o.da.GetSize();
    00544
    00545         CUIntArray la;
    00546
    00547         for(int i = 0, j = 0; j < len2; j++)
    00548         {
    00549                 if(j == len2-1 || o.da[j])
    00550                 {
    00551                         la.Add(j-i);
    00552                         i = j;
    00553                 }
    00554         }
    00555
    00556         int len = la.GetSize();
    00557
    00558         int ret = 0;
    00559
    00560         // check if we can find a reason to add a penalty degree, or two :P
    00561         // it is mainly about looking for distant corners
    00562         {
    00563                 int penalty = 0;
    00564
    00565                 int ma[2] = {0, 0};
    00566                 for(int i = 0; i < len; i++) ma[i&1] += la[i];
    00567
    00568                 int ca[2] = {ma[0], ma[1]};
    00569                 for(int i = 0; i < len; i++)
    00570                 {
    00571                         ca[i&1] -= la[i];
    00572
    00573                         double c1 = 1.0*ca[0]/ma[0], c2 = 1.0*ca[1]/ma[1], c3 = 1.0*la[i]/ma[i&1];
    00574
    00575                         if(len2 > 16 && (fabs(c1-c2) > 0.7 || (c3 > 0.6 && la[i] > 5)))
    00576                                 {penalty = 2; break;}
    00577
    00578                         if(fabs(c1-c2) > 0.6 || (c3 > 0.4 && la[i] > 5))
    00579                                 {penalty = 1;}
    00580                 }
    00581
    00582                 ret += penalty;
    00583         }
    00584
    00585         la[0] <<= 1;
    00586         la[len-1] <<= 1;
    00587
    00588         for(int i = 0; i < len; i+=2)
    00589         {
    00590                 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
    00591         }
    00592
    00593         return(ret);
    00594 }
    00595
    00596 inline double vectlen(CPoint p)
    00597 {
    00598         return(sqrt((double)(p.x*p.x+p.y*p.y)));
    00599 }
    00600
    00601 inline double vectlen(CPoint p1, CPoint p2)
    00602 {
    00603         return(vectlen(p2 - p1));
    00604 }
    00605
    00606 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
    00607 {
    00608         CPointArray& pa = o.pa;
    00609
    00610         int len = (int)pa.GetSize();
    00611         if(len < 6) return(false);
    00612
    00613         mincf = 1;
    00614         maxcf = -1;
    00615
    00616         CPoint p = pa[len-1] - pa[0];
    00617         double l = vectlen(p);
    00618
    00619         for(int i = 2; i < len-2; i++) // skip the endpoints, they aren't accurate
    00620         {
    00621                 CPoint p1 = pa[0] - pa[i], p2 = pa[len-1] - pa[i];
    00622                 double l1 = vectlen(p1), l2 = vectlen(p2);
    00623                 int sign = p1.x*p.y-p1.y*p.x >= 0 ? 1 : -1;
    00624
    00625                 double c = (1.0*len/2 - fabs(i - 1.0*len/2)) / len * 2; // c: 0 -> 1 -> 0
    00626
    00627                 double cosfi = (1+(p1.x*p2.x+p1.y*p2.y)/(l1*l2)) * sign * c;
    00628                 if(mincf > cosfi) mincf = cosfi;
    00629                 if(maxcf < cosfi) maxcf = cosfi;
    00630         }
    00631
    00632         return(true);
    00633 }
    00634
    00635 static bool FitBezierVH(COutline& o, CPoint& p1, CPoint& p2)
    00636 {
    00637         int i;
    00638
    00639         CPointArray& pa = o.pa;
    00640
    00641         int len = (int)pa.GetSize();
    00642
    00643         if(len <= 1)
    00644         {
    00645                 return(false);
    00646         }
    00647         else if(len == 2)
    00648         {
    00649                 CPoint mid = pa[0]+pa[1];
    00650                 mid.x >>= 1;
    00651                 mid.y >>= 1;
    00652                 p1 = p2 = mid;
    00653                 return(true);
    00654         }
    00655
    00656         CPoint dir1 = pa[1] - pa[0], dir2 = pa[len-2] - pa[len-1];
    00657         if((dir1.x&&dir1.y)||(dir2.x&&dir2.y))
    00658                 return(false); // we are only fitting beziers with hor./ver. endings
    00659
    00660         if(CalcPossibleCurveDegree(o) > 3)
    00661                 return(false);
    00662
    00663         double mincf, maxcf;
    00664         if(MinMaxCosfi(o, mincf, maxcf))
    00665         {
    00666                 if(maxcf-mincf > 0.8
    00667                 || maxcf-mincf > 0.6 && (maxcf >= 0.4 || mincf <= -0.4))
    00668                         return(false);
    00669         }
    00670
    00671         CPoint p0 = p1 = pa[0];
    00672         CPoint p3 = p2 = pa[len-1];
    00673
    00674         CArray<double,double&> pl;
    00675         pl.SetSize(len);
    00676
    00677         double c10 = 0, c11 = 0, c12 = 0, c13 = 0, c1x = 0, c1y = 0;
    00678         double c20 = 0, c21 = 0, c22 = 0, c23 = 0, c2x = 0, c2y = 0;
    00679         double length = 0;
    00680
    00681         for(pl[0] = 0, i = 1; i < len; i++)
    00682         {
    00683                 CPoint diff = (pa[i] - pa[i-1]);
    00684                 pl[i] = (length += sqrt((double)(diff.x*diff.x+diff.y*diff.y)));
    00685         }
    00686
    00687         for(i = 0; i < len; i++)
    00688         {
    00689                 double t1 = pl[i] / length;
    00690                 double t2 = t1*t1;
    00691                 double t3 = t2*t1;
    00692                 double it1 = 1 - t1;
    00693                 double it2 = it1*it1;
    00694                 double it3 = it2*it1;
    00695
    00696                 double dc1 = 3.0*it2*t1;
    00697                 double dc2 = 3.0*it1*t2;
    00698
    00699                 c10 += it3*dc1;
    00700                 c11 += dc1*dc1;
    00701                 c12 += dc2*dc1;
    00702                 c13 += t3*dc1;
    00703                 c1x += pa[i].x*dc1;
    00704                 c1y += pa[i].y*dc1;
    00705
    00706                 c20 += it3*dc2;
    00707                 c21 += dc1*dc2;
    00708                 c22 += dc2*dc2;
    00709                 c23 += t3*dc2;
    00710                 c2x += pa[i].x*dc2;
    00711                 c2y += pa[i].y*dc2;
    00712         }
    00713
    00714         if(dir1.y == 0 && dir2.x == 0)
    00715         {
    00716                 p1.x = (int)((c1x - c10*p0.x - c12*p3.x - c13*p3.x) / c11 + 0.5);
    00717                 p2.y = (int)((c2y - c20*p0.y - c21*p0.y - c23*p3.y) / c22 + 0.5);
    00718         }
    00719         else if(dir1.x == 0 && dir2.y == 0)
    00720         {
    00721                 p2.x = (int)((c2x - c20*p0.x - c21*p0.x - c23*p3.x) / c22 + 0.5);
    00722                 p1.y = (int)((c1y - c10*p0.y - c12*p3.y - c13*p3.y) / c11 + 0.5);
    00723         }
    00724         else if(dir1.y == 0 && dir2.y == 0)
    00725         {
    00726                 // cramer's rule
    00727                 double D = c11*c22 - c12*c21;
    00728                 p1.x = (int)(((c1x-c10*p0.x-c13*p3.x)*c22 - c12*(c2x-c20*p0.x-c23*p3.x)) / D + 0.5);
    00729                 p2.x = (int)((c11*(c2x-c20*p0.x-c23*p3.x) - (c1x-c10*p0.x-c13*p3.x)*c21) / D + 0.5);
    00730         }
    00731         else if(dir1.x == 0 && dir2.x == 0)
    00732         {
    00733                 // cramer's rule
    00734                 double D = c11*c22 - c12*c21;
    00735                 p1.y = (int)(((c1y-c10*p0.y-c13*p3.y)*c22 - c12*(c2y-c20*p0.y-c23*p3.y)) / D + 0.5);
    00736                 p2.y = (int)((c11*(c2y-c20*p0.y-c23*p3.y) - (c1y-c10*p0.y-c13*p3.y)*c21) / D + 0.5);
    00737         }
    00738         else // must not happen
    00739         {
    00740                 ASSERT(0);
    00741                 return(false);
    00742         }
    00743
    00744         // check for "inside-out" beziers
    00745         CPoint dir3 = p1 - p0, dir4 = p2 - p3;
    00746         if((dir1.x*dir3.x+dir1.y*dir3.y) <= 0 || (dir2.x*dir4.x+dir2.y*dir4.y) <= 0)
    00747                 return(false);
    00748
    00749         return(true);
    00750 }
    00751
    00752 int CVobSubImage::GrabSegment(int start, COutline& o, COutline& ret)
    00753 {
    00754         ret.RemoveAll();
    00755
    00756         int len = o.pa.GetSize();
    00757
    00758         int cur = (start)%len, first = -1, last = -1;
    00759         int curDir = 0, lastDir = 0;
    00760
    00761         for(int i = 0; i < len; i++)
    00762         {
    00763                 cur = (cur+1)%len;
    00764
    00765                 if(o.da[cur] == 0) continue;
    00766
    00767                 if(first == -1) first = cur;
    00768
    00769                 if(lastDir == o.da[cur])
    00770                 {
    00771                         CPoint startp = o.pa[first]+o.pa[start]; startp.x >>= 1; startp.y >>= 1;
    00772                         CPoint endp = o.pa[last]+o.pa[cur]; endp.x >>= 1; endp.y >>= 1;
    00773
    00774                         if(first < start) first += len;
    00775                         start = ((start+first)>>1)+1;
    00776                         if(start >= len) start -= len;
    00777                         if(cur < last) cur += len;
    00778                         cur = ((last+cur+1)>>1);
    00779                         if(cur >= len) cur -= len;
    00780
    00781                         ret.Add(startp, 0);
    00782
    00783                         while(start != cur)
    00784                         {
    00785                                 ret.Add(o.pa[start], o.da[start]);
    00786
    00787                                 start++;
    00788                                 if(start >= len) start -= len;
    00789                         }
    00790
    00791                         ret.Add(endp, 0);
    00792
    00793                         return(last);
    00794                 }
    00795
    00796                 lastDir = o.da[cur];
    00797                 last = cur;
    00798         }
    00799
    00800         ASSERT(0);
    00801
    00802         return(start);
    00803 }
    00804
    00805 void CVobSubImage::SplitOutline(COutline& o, COutline& o1, COutline& o2)
    00806 {
    00807         int len = o.pa.GetSize();
    00808         if(len < 4) return;
    00809
    00810         CUIntArray la, sa, ea;
    00811
    00812         int i, j, k;
    00813
    00814         for(i = 0, j = 0; j < len; j++)
    00815         {
    00816                 if(j == len-1 || o.da[j])
    00817                 {
    00818                         la.Add(j-i);
    00819                         sa.Add(i);
    00820                         ea.Add(j);
    00821                         i = j;
    00822                 }
    00823         }
    00824
    00825         int maxlen = 0, maxidx = -1;
    00826         int maxlen2 = 0, maxidx2 = -1;
    00827
    00828         for(i = 0; i < la.GetSize(); i++)
    00829         {
    00830                 if(maxlen < la[i])
    00831                 {
    00832                         maxlen = la[i];
    00833                         maxidx = i;
    00834                 }
    00835
    00836                 if(maxlen2 < la[i] && i > 0 && i < la.GetSize()-1)
    00837                 {
    00838                         maxlen2 = la[i];
    00839                         maxidx2 = i;
    00840                 }
    00841         }
    00842
    00843         if(maxlen == maxlen2) maxidx = maxidx2; // if equal choose the inner section
    00844
    00845         j = (sa[maxidx] + ea[maxidx]) >> 1, k = (sa[maxidx] + ea[maxidx] + 1) >> 1;
    00846
    00847         o1.RemoveAll();
    00848         o2.RemoveAll();
    00849
    00850         for(i = 0; i <= j; i++)
    00851                 o1.Add(o.pa[i], o.da[i]);
    00852
    00853         if(j != k)
    00854         {
    00855                 CPoint mid = o.pa[j]+o.pa[k]; mid.x >>= 1; mid.y >>= 1;
    00856                 o1.Add(mid, 0);
    00857                 o2.Add(mid, 0);
    00858         }
    00859
    00860         for(i = k; i < len; i++)
    00861                 o2.Add(o.pa[i], o.da[i]);
    00862 }
    00863
    00864 void CVobSubImage::AddSegment(COutline& o, CByteArray& pathTypes, CPointArray& pathPoints)
    00865 {
    00866         int i, len = o.pa.GetSize();
    00867         if(len < 3) return;
    00868
    00869         int nLeftTurns = 0, nRightTurns = 0;
    00870
    00871         for(i = 0; i < len; i++)
    00872         {
    00873                 if(o.da[i] == -1) nLeftTurns++;
    00874                 else if(o.da[i] == 1) nRightTurns++;
    00875         }
    00876
    00877         if(nLeftTurns == 0 && nRightTurns == 0) // line
    00878         {
    00879                 pathTypes.Add(PT_LINETO);
    00880                 pathPoints.Add(o.pa[len-1]);
    00881
    00882                 return;
    00883         }
    00884
    00885         if(nLeftTurns == 0 || nRightTurns == 0) // b-spline
    00886         {
    00887                 pathTypes.Add(PT_MOVETONC);
    00888                 pathPoints.Add(o.pa[0]+(o.pa[0]-o.pa[1]));
    00889
    00890                 for(i = 0; i < 3; i++)
    00891                 {
    00892                         pathTypes.Add(PT_BSPLINETO);
    00893                         pathPoints.Add(o.pa[i]);
    00894                 }
    00895
    00896                 for(; i < len; i++)
    00897                 {
    00898                         pathTypes.Add(PT_BSPLINEPATCHTO);
    00899                         pathPoints.Add(o.pa[i]);
    00900                 }
    00901
    00902                 pathTypes.Add(PT_BSPLINEPATCHTO);
    00903                 pathPoints.Add(o.pa[len-1]+(o.pa[len-1]-o.pa[len-2]));
    00904
    00905                 pathTypes.Add(PT_MOVETONC);
    00906                 pathPoints.Add(o.pa[len-1]);
    00907
    00908                 return;
    00909         }
    00910
    00911         int start, end;
    00912         if(FitLine(o, start, end)) // b-spline, line, b-spline
    00913         {
    00914                 pathTypes.Add(PT_MOVETONC);
    00915                 pathPoints.Add(o.pa[0]+(o.pa[0]-o.pa[1]));
    00916
    00917                 pathTypes.Add(PT_BSPLINETO);
    00918                 pathPoints.Add(o.pa[0]);
    00919
    00920                 pathTypes.Add(PT_BSPLINETO);
    00921                 pathPoints.Add(o.pa[1]);
    00922
    00923                 CPoint p[4], pp, d = o.pa[end] - o.pa[start];
    00924                 double l = sqrt((double)(d.x*d.x+d.y*d.y)), dx = 1.0 * d.x / l, dy = 1.0 * d.y / l;
    00925
    00926                 pp = o.pa[start]-o.pa[start-1];
    00927                 double l1 = abs(pp.x)+abs(pp.y);
    00928                 pp = o.pa[end]-o.pa[end+1];
    00929                 double l2 = abs(pp.x)+abs(pp.y);
    00930                 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));
    00931                 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));
    00932                 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));
    00933                 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));
    00934
    00935                 if(start == 1)
    00936                 {
    00937                         pathTypes.Add(PT_BSPLINETO);
    00938                         pathPoints.Add(p[0]);
    00939                 }
    00940                 else
    00941                 {
    00942                         pathTypes.Add(PT_BSPLINETO);
    00943                         pathPoints.Add(o.pa[2]);
    00944
    00945                         for(int i = 3; i <= start; i++)
    00946                         {
    00947                                 pathTypes.Add(PT_BSPLINEPATCHTO);
    00948                                 pathPoints.Add(o.pa[i]);
    00949                         }
    00950
    00951                         pathTypes.Add(PT_BSPLINEPATCHTO);
    00952                         pathPoints.Add(p[0]);
    00953                 }
    00954
    00955                 pathTypes.Add(PT_BSPLINEPATCHTO);
    00956                 pathPoints.Add(p[1]);
    00957
    00958                 pathTypes.Add(PT_MOVETONC);
    00959                 pathPoints.Add(p[0]);
    00960
    00961                 pathTypes.Add(PT_LINETO);
    00962                 pathPoints.Add(p[3]);
    00963
    00964                 pathTypes.Add(PT_MOVETONC);
    00965                 pathPoints.Add(p[2]);
    00966
    00967                 pathTypes.Add(PT_BSPLINEPATCHTO);
    00968                 pathPoints.Add(p[3]);
    00969
    00970                 for(i = end; i < len; i++)
    00971                 {
    00972                         pathTypes.Add(PT_BSPLINEPATCHTO);
    00973                         pathPoints.Add(o.pa[i]);
    00974                 }
    00975
    00976                 pathTypes.Add(PT_BSPLINEPATCHTO);
    00977                 pathPoints.Add(o.pa[len-1]+(o.pa[len-1]-o.pa[len-2]));
    00978
    00979                 pathTypes.Add(PT_MOVETONC);
    00980                 pathPoints.Add(o.pa[len-1]);
    00981
    00982                 return;
    00983         }
    00984
    00985         CPoint p1, p2;
    00986         if(FitBezierVH(o, p1, p2)) // bezier
    00987         {
    00988                 pathTypes.Add(PT_BEZIERTO);
    00989                 pathPoints.Add(p1);
    00990                 pathTypes.Add(PT_BEZIERTO);
    00991                 pathPoints.Add(p2);
    00992                 pathTypes.Add(PT_BEZIERTO);
    00993                 pathPoints.Add(o.pa[o.pa.GetSize()-1]);
    00994
    00995                 return;
    00996         }
    00997
    00998         COutline o1, o2;
    00999         SplitOutline(o, o1, o2);
    01000         AddSegment(o1, pathTypes, pathPoints);
    01001         AddSegment(o2, pathTypes, pathPoints);
    01002 }
    01003
    01004 bool CVobSubImage::Polygonize(CByteArray& pathTypes, CPointArray& pathPoints, bool fSmooth, int scale)
    01005 {
    01006         CPoint topleft;
    01007         CAutoPtr<COutlineList> ol(GetOutlineList(topleft));
    01008         if(!ol) return(false);
    01009
    01010         POSITION pos;
    01011
    01012         pos = ol->GetHeadPosition();
    01013         while(pos)
    01014         {
    01015                 CPointArray& pa = ol->GetNext(pos)->pa;
    01016                 for(int i = 0; i < pa.GetSize(); i++)
    01017                 {
    01018                         pa[i].x = (pa[i].x-topleft.x)<<scale;
    01019                         pa[i].y = (pa[i].y-topleft.y)<<scale;
    01020                 }
    01021         }
    01022
    01023         pos = ol->GetHeadPosition();
    01024         while(pos)
    01025         {
    01026                 COutline& o = *ol->GetNext(pos), o2;
    01027
    01028                 if(fSmooth)
    01029                 {
    01030                         int i = 0, iFirst = -1;
    01031
    01032                         while(1)
    01033                         {
    01034                                 i = GrabSegment(i, o, o2);
    01035
    01036                                 if(i == iFirst) break;
    01037
    01038                                 if(iFirst < 0)
    01039                                 {
    01040                                         iFirst = i;
    01041                                         pathTypes.Add(PT_MOVETO);
    01042                                         pathPoints.Add(o2.pa[0]);
    01043                                 }
    01044
    01045                                 AddSegment(o2, pathTypes, pathPoints);
    01046                         }
    01047                 }
    01048                 else
    01049                 {
    01050 /*
    01051                         for(int i = 1, len = o.pa.GetSize(); i < len; i++)
    01052                         {
    01053                 if(int dir = o.da[i-1])
    01054                                 {
    01055                                         CPoint dir2 = o.pa[i] - o.pa[i-1];
    01056                                         dir2.x /= 2; dir2.y /= 2;
    01057                                         CPoint dir1 = dir > 0 ? CPoint(dir2.y, -dir2.x) : CPoint(-dir2.y, dir2.x);
    01058                                         i = i;
    01059                                         o.pa[i-1] -= dir1;
    01060                                         o.pa.InsertAt(i, o.pa[i-1] + dir2);
    01061                                         o.da.InsertAt(i, -dir);
    01062                                         o.pa.InsertAt(i+1, o.pa[i] + dir1);
    01063                                         o.da.InsertAt(i+1, dir);
    01064                                         i += 2;
    01065                                         len += 2;
    01066                                 }
    01067                         }
    01068 */
    01069                         pathTypes.Add(PT_MOVETO);
    01070                         pathPoints.Add(o.pa[0]);
    01071                         for(int i = 1, len = o.pa.GetSize(); i < len; i++)
    01072                         {
    01073                                 pathTypes.Add(PT_LINETO);
    01074                                 pathPoints.Add(o.pa[i]);
    01075                         }
    01076                 }
    01077         }
    01078
    01079         return(pathTypes.GetSize() > 0);
    01080 }
    01081
    01082 bool CVobSubImage::Polygonize(CStringW& assstr, bool fSmooth, int scale)
    01083 {
    01084         CByteArray pathTypes;
    01085         CPointArray pathPoints;
    01086
    01087         if(!Polygonize(pathTypes, pathPoints, fSmooth, scale))
    01088                 return(false);
    01089
    01090         assstr.Format(L"{\\an7\\pos(%d,%d)\\p%d}", rect.left, rect.top, 1+scale);
    01091 //      assstr.Format(L"{\\p%d}", 1+scale);
    01092
    01093         BYTE lastType = 0;
    01094
    01095         int nPoints = pathTypes.GetSize();
    01096
    01097         for(int i = 0; i < nPoints; i++)
    01098         {
    01099                 CStringW s;
    01100
    01101                 switch(pathTypes[i])
    01102                 {
    01103                 case PT_MOVETO:
    01104                         if(lastType != PT_MOVETO) assstr += L"m ";
    01105                         s.Format(L"%d %d ", pathPoints[i].x, pathPoints[i].y);
    01106                         break;
    01107                 case PT_MOVETONC:
    01108                         if(lastType != PT_MOVETONC) assstr += L"n ";
    01109                         s.Format(L"%d %d ", pathPoints[i].x, pathPoints[i].y);
    01110                         break;
    01111                 case PT_LINETO:
    01112                         if(lastType != PT_LINETO) assstr += L"l ";
    01113                         s.Format(L"%d %d ", pathPoints[i].x, pathPoints[i].y);
    01114                         break;
    01115                 case PT_BEZIERTO:
    01116                         if(i < nPoints-2)
    01117                         {
    01118                                 if(lastType != PT_BEZIERTO) assstr += L"b ";
    01119                                 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);
    01120                                 i+=2;
    01121                         }
    01122                         break;
    01123                 case PT_BSPLINETO:
    01124                         if(i < nPoints-2)
    01125                         {
    01126                                 if(lastType != PT_BSPLINETO) assstr += L"s ";
    01127                                 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);
    01128                                 i+=2;
    01129                         }
    01130                         break;
    01131                 case PT_BSPLINEPATCHTO:
    01132                         if(lastType != PT_BSPLINEPATCHTO) assstr += L"p ";
    01133                         s.Format(L"%d %d ", pathPoints[i].x, pathPoints[i].y);
    01134                         break;
    01135                 }
    01136
    01137                 lastType = pathTypes[i];
    01138
    01139                 assstr += s;
    01140         }
    01141
    01142         assstr += L"{\\p0}";
    01143
    01144         return(nPoints > 0);
    01145 }
    01146
    01147 void CVobSubImage::Scale2x()
    01148 {
    01149         int w = rect.Width(), h = rect.Height();
    01150
    01151         DWORD* src = (DWORD*)lpPixels;
    01152         DWORD* dst = new DWORD[w*h];
    01153
    01154         for(int y = 0; y < h; y++)
    01155         {
    01156                 for(int x = 0; x < w; x++, src++, dst++)
    01157                 {
    01158                         DWORD E = *src;
    01159
    01160                         DWORD A = x > 0 && y > 0 ? src[-w-1] : E;
    01161                         DWORD B = y > 0 ? src[-w] : E;
    01162                         DWORD C = x < w-1 && y > 0 ? src[-w+1] : E;
    01163
    01164                         DWORD D = x > 0 ? src[-1] : E;;
    01165                         DWORD F = x < w-1 ? src[+1] : E;;
    01166
    01167                         DWORD G = x > 0 && y < h-1 ? src[+w-1] : E;
    01168                         DWORD H = y < h-1 ? src[+w] : E;
    01169                         DWORD I = x < w-1 && y < h-1 ? src[+w+1] : E;
    01170
    01171                         DWORD E0 = D == B && B != F && D != H ? D : E;
    01172                         DWORD E1 = B == F && B != D && F != H ? F : E;
    01173                         DWORD E2 = D == H && D != B && H != F ? D : E;
    01174                         DWORD E3 = H == F && D != H && B != F ? F : E;
    01175
    01176                         *dst = ((((E0&0x00ff00ff)+(E1&0x00ff00ff)+(E2&0x00ff00ff)+(E3&0x00ff00ff)+2)>>2)&0x00ff00ff)
    01177                                 | (((((E0>>8)&0x00ff00ff)+((E1>>8)&0x00ff00ff)+((E2>>8)&0x00ff00ff)+((E3>>8)&0x00ff00ff)+2)<<6)&0xff00ff00);
    01178                 }
    01179         }
    01180
    01181         src -= w*h;
    01182         dst -= w*h;
    01183
    01184         memcpy(src, dst, w*h*4);
    01185
    01186         delete [] dst;
    01187 }