- Main Page
- Namespaces
- Classes
- Files
- Directories

- File List
- File Members

# Rasterizer.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 <string.h>
    00024 #include <math.h>
    00025 #include <vector>
    00026 #include <algorithm>
    00027 #include "Rasterizer.h"
    00028
    00029 Rasterizer::Rasterizer() : mpPathTypes(NULL), mpPathPoints(NULL), mPathPoints(0), mpOverlayBuffer(NULL)
    00030 {
    00031         mOverlayWidth = mOverlayHeight = 0;
    00032         mPathOffsetX = mPathOffsetY = 0;
    00033         mOffsetX = mOffsetY = 0;
    00034 }
    00035
    00036 Rasterizer::~Rasterizer()
    00037 {
    00038         _TrashPath();
    00039         _TrashOverlay();
    00040 }
    00041
    00042 void Rasterizer::_TrashPath()
    00043 {
    00044         delete [] mpPathTypes;
    00045         delete [] mpPathPoints;
    00046         mpPathTypes = NULL;
    00047         mpPathPoints = NULL;
    00048         mPathPoints = 0;
    00049 }
    00050
    00051 void Rasterizer::_TrashOverlay()
    00052 {
    00053         delete [] mpOverlayBuffer;
    00054         mpOverlayBuffer = NULL;
    00055 }
    00056
    00057 void Rasterizer::_ReallocEdgeBuffer(int edges)
    00058 {
    00059         mEdgeHeapSize = edges;
    00060         mpEdgeBuffer = (Edge*)realloc(mpEdgeBuffer, sizeof(Edge)*edges);
    00061 }
    00062
    00063 void Rasterizer::_EvaluateBezier(int ptbase, bool fBSpline)
    00064 {
    00065         const POINT* pt0 = mpPathPoints + ptbase;
    00066         const POINT* pt1 = mpPathPoints + ptbase + 1;
    00067         const POINT* pt2 = mpPathPoints + ptbase + 2;
    00068         const POINT* pt3 = mpPathPoints + ptbase + 3;
    00069
    00070         double x0 = pt0->x;
    00071         double x1 = pt1->x;
    00072         double x2 = pt2->x;
    00073         double x3 = pt3->x;
    00074         double y0 = pt0->y;
    00075         double y1 = pt1->y;
    00076         double y2 = pt2->y;
    00077         double y3 = pt3->y;
    00078
    00079         double cx3, cx2, cx1, cx0, cy3, cy2, cy1, cy0;
    00080
    00081         if(fBSpline)
    00082         {
    00083                 // 1   [-1 +3 -3 +1]
    00084                 // - * [+3 -6 +3  0]
    00085                 // 6   [-3  0 +3  0]
    00086                 //         [+1 +4 +1  0]
    00087
    00088                 double _1div6 = 1.0/6.0;
    00089
    00090                 cx3 = _1div6*(-  x0+3*x1-3*x2+x3);
    00091                 cx2 = _1div6*( 3*x0-6*x1+3*x2);
    00092                 cx1 = _1div6*(-3*x0        +3*x2);
    00093                 cx0 = _1div6*(   x0+4*x1+1*x2);
    00094
    00095                 cy3 = _1div6*(-  y0+3*y1-3*y2+y3);
    00096                 cy2 = _1div6*( 3*y0-6*y1+3*y2);
    00097                 cy1 = _1div6*(-3*y0     +3*y2);
    00098                 cy0 = _1div6*(   y0+4*y1+1*y2);
    00099         }
    00100         else // bezier
    00101         {
    00102                 // [-1 +3 -3 +1]
    00103                 // [+3 -6 +3  0]
    00104                 // [-3 +3  0  0]
    00105                 // [+1  0  0  0]
    00106
    00107                 cx3 = -  x0+3*x1-3*x2+x3;
    00108                 cx2 =  3*x0-6*x1+3*x2;
    00109                 cx1 = -3*x0+3*x1;
    00110                 cx0 =    x0;
    00111
    00112                 cy3 = -  y0+3*y1-3*y2+y3;
    00113                 cy2 =  3*y0-6*y1+3*y2;
    00114                 cy1 = -3*y0+3*y1;
    00115                 cy0 =    y0;
    00116         }
    00117
    00118         //
    00119         // This equation is from Graphics Gems I.
    00120         //
    00121         // The idea is that since we're approximating a cubic curve with lines,
    00122         // any error we incur is due to the curvature of the line, which we can
    00123         // estimate by calculating the maximum acceleration of the curve.  For
    00124         // a cubic, the acceleration (second derivative) is a line, meaning that
    00125         // the absolute maximum acceleration must occur at either the beginning
    00126         // (|c2|) or the end (|c2+c3|).  Our bounds here are a little more
    00127         // conservative than that, but that's okay.
    00128         //
    00129         // If the acceleration of the parametric formula is zero (c2 = c3 = 0),
    00130         // that component of the curve is linear and does not incur any error.
    00131         // If a=0 for both X and Y, the curve is a line segment and we can
    00132         // use a step size of 1.
    00133
    00134         double maxaccel1 = fabs(2*cy2) + fabs(6*cy3);
    00135         double maxaccel2 = fabs(2*cx2) + fabs(6*cx3);
    00136
    00137         double maxaccel = maxaccel1 > maxaccel2 ? maxaccel1 : maxaccel2;
    00138         double h = 1.0;
    00139
    00140         if(maxaccel > 8.0) h = sqrt(8.0 / maxaccel);
    00141
    00142         if(!fFirstSet) {firstp.x = (LONG)cx0; firstp.y = (LONG)cy0; lastp = firstp; fFirstSet = true;}
    00143
    00144         for(double t = 0; t < 1.0; t += h)
    00145         {
    00146                 double x = cx0 + t*(cx1 + t*(cx2 + t*cx3));
    00147                 double y = cy0 + t*(cy1 + t*(cy2 + t*cy3));
    00148                 _EvaluateLine(lastp.x, lastp.y, (int)x, (int)y);
    00149         }
    00150
    00151         double x = cx0 + cx1 + cx2 + cx3;
    00152         double y = cy0 + cy1 + cy2 + cy3;
    00153         _EvaluateLine(lastp.x, lastp.y, (int)x, (int)y);
    00154 }
    00155
    00156 void Rasterizer::_EvaluateLine(int pt1idx, int pt2idx)
    00157 {
    00158         const POINT* pt1 = mpPathPoints + pt1idx;
    00159         const POINT* pt2 = mpPathPoints + pt2idx;
    00160
    00161         _EvaluateLine(pt1->x, pt1->y, pt2->x, pt2->y);
    00162 }
    00163
    00164 void Rasterizer::_EvaluateLine(int x0, int y0, int x1, int y1)
    00165 {
    00166         if(lastp.x != x0 || lastp.y != y0)
    00167         {
    00168                 _EvaluateLine(lastp.x, lastp.y, x0, y0);
    00169         }
    00170
    00171         if(!fFirstSet) {firstp.x = x0; firstp.y = y0; fFirstSet = true;}
    00172         lastp.x = x1; lastp.y = y1;
    00173
    00174         if(y1 > y0)     // down
    00175         {
    00176                 __int64 xacc = (__int64)x0 << 13;
    00177
    00178                 // prestep y0 down
    00179
    00180                 int dy = y1 - y0;
    00181                 int y = ((y0 + 3)&~7) + 4;
    00182                 int iy = y >> 3;
    00183
    00184                 y1 = (y1 - 5) >> 3;
    00185
    00186                 if(iy <= y1)
    00187                 {
    00188                         __int64 invslope = (__int64(x1 - x0) << 16) / dy;
    00189
    00190                         while(mEdgeNext + y1 + 1 - iy > mEdgeHeapSize)
    00191                                 _ReallocEdgeBuffer(mEdgeHeapSize*2);
    00192
    00193                         xacc += (invslope * (y - y0)) >> 3;
    00194
    00195                         while(iy <= y1)
    00196                         {
    00197                                 int ix = (int)((xacc + 32768) >> 16);
    00198
    00199                                 mpEdgeBuffer[mEdgeNext].next = mpScanBuffer[iy];
    00200                                 mpEdgeBuffer[mEdgeNext].posandflag = ix*2 + 1;
    00201
    00202                                 mpScanBuffer[iy] = mEdgeNext++;
    00203
    00204                                 ++iy;
    00205                                 xacc += invslope;
    00206                         }
    00207                 }
    00208         }
    00209         else if(y1 < y0) // up
    00210         {
    00211                 __int64 xacc = (__int64)x1 << 13;
    00212
    00213                 // prestep y1 down
    00214
    00215                 int dy = y0 - y1;
    00216                 int y = ((y1 + 3)&~7) + 4;
    00217                 int iy = y >> 3;
    00218
    00219                 y0 = (y0 - 5) >> 3;
    00220
    00221                 if(iy <= y0)
    00222                 {
    00223                         __int64 invslope = (__int64(x0 - x1) << 16) / dy;
    00224
    00225                         while(mEdgeNext + y0 + 1 - iy > mEdgeHeapSize)
    00226                                 _ReallocEdgeBuffer(mEdgeHeapSize*2);
    00227
    00228                         xacc += (invslope * (y - y1)) >> 3;
    00229
    00230                         while(iy <= y0)
    00231                         {
    00232                                 int ix = (int)((xacc + 32768) >> 16);
    00233
    00234                                 mpEdgeBuffer[mEdgeNext].next = mpScanBuffer[iy];
    00235                                 mpEdgeBuffer[mEdgeNext].posandflag = ix*2;
    00236
    00237                                 mpScanBuffer[iy] = mEdgeNext++;
    00238
    00239                                 ++iy;
    00240                                 xacc += invslope;
    00241                         }
    00242                 }
    00243         }
    00244 }
    00245
    00246 bool Rasterizer::BeginPath(HDC hdc)
    00247 {
    00248         _TrashPath();
    00249
    00250         return !!::BeginPath(hdc);
    00251 }
    00252
    00253 bool Rasterizer::EndPath(HDC hdc)
    00254 {
    00255         ::CloseFigure(hdc);
    00256
    00257         if(::EndPath(hdc))
    00258         {
    00259                 mPathPoints = GetPath(hdc, NULL, NULL, 0);
    00260
    00261                 if(!mPathPoints)
    00262                         return true;
    00263
    00264                 mpPathTypes = (BYTE*)malloc(sizeof(BYTE) * mPathPoints);
    00265                 mpPathPoints = (POINT*)malloc(sizeof(POINT) * mPathPoints);
    00266
    00267                 if(mPathPoints == GetPath(hdc, mpPathPoints, mpPathTypes, mPathPoints))
    00268                         return true;
    00269         }
    00270
    00271         ::AbortPath(hdc);
    00272
    00273         return false;
    00274 }
    00275
    00276 bool Rasterizer::PartialBeginPath(HDC hdc, bool bClearPath)
    00277 {
    00278         if(bClearPath)
    00279                 _TrashPath();
    00280
    00281         return !!::BeginPath(hdc);
    00282 }
    00283
    00284 bool Rasterizer::PartialEndPath(HDC hdc, long dx, long dy)
    00285 {
    00286         ::CloseFigure(hdc);
    00287
    00288         if(::EndPath(hdc))
    00289         {
    00290                 int nPoints;
    00291                 BYTE* pNewTypes;
    00292                 POINT* pNewPoints;
    00293
    00294                 nPoints = GetPath(hdc, NULL, NULL, 0);
    00295
    00296                 if(!nPoints)
    00297                         return true;
    00298
    00299                 pNewTypes = (BYTE*)realloc(mpPathTypes, (mPathPoints + nPoints) * sizeof(BYTE));
    00300                 pNewPoints = (POINT*)realloc(mpPathPoints, (mPathPoints + nPoints) * sizeof(POINT));
    00301
    00302                 if(pNewTypes)
    00303                         mpPathTypes = pNewTypes;
    00304
    00305                 if(pNewPoints)
    00306                         mpPathPoints = pNewPoints;
    00307
    00308                 BYTE* pTypes = new BYTE[nPoints];
    00309                 POINT* pPoints = new POINT[nPoints];
    00310
    00311                 if(pNewTypes && pNewPoints && nPoints == GetPath(hdc, pPoints, pTypes, nPoints))
    00312                 {
    00313                         for(int i = 0; i < nPoints; ++i)
    00314                         {
    00315                                 mpPathPoints[mPathPoints + i].x = pPoints[i].x + dx;
    00316                                 mpPathPoints[mPathPoints + i].y = pPoints[i].y + dy;
    00317                                 mpPathTypes[mPathPoints + i] = pTypes[i];
    00318                         }
    00319
    00320                         mPathPoints += nPoints;
    00321
    00322                         delete[] pTypes;
    00323                         delete[] pPoints;
    00324                         return true;
    00325                 }
    00326                 else
    00327                         DebugBreak();
    00328
    00329                 delete[] pTypes;
    00330                 delete[] pPoints;
    00331         }
    00332
    00333         ::AbortPath(hdc);
    00334
    00335         return false;
    00336 }
    00337
    00338 bool Rasterizer::ScanConvert()
    00339 {
    00340         int lastmoveto = -1;
    00341         int i;
    00342
    00343         // Drop any outlines we may have.
    00344
    00345         mOutline.clear();
    00346         mWideOutline.clear();
    00347
    00348         // Determine bounding box
    00349
    00350         if(!mPathPoints)
    00351         {
    00352                 mPathOffsetX = mPathOffsetY = 0;
    00353                 mWidth = mHeight = 0;
    00354                 return 0;
    00355         }
    00356
    00357         int minx = INT_MAX;
    00358         int miny = INT_MAX;
    00359         int maxx = INT_MIN;
    00360         int maxy = INT_MIN;
    00361
    00362         for(i=0; i<mPathPoints; ++i)
    00363         {
    00364                 int ix = mpPathPoints[i].x;
    00365                 int iy = mpPathPoints[i].y;
    00366
    00367                 if(ix < minx) minx = ix;
    00368                 if(ix > maxx) maxx = ix;
    00369                 if(iy < miny) miny = iy;
    00370                 if(iy > maxy) maxy = iy;
    00371         }
    00372
    00373         minx = (minx >> 3) & ~7;
    00374         miny = (miny >> 3) & ~7;
    00375         maxx = (maxx + 7) >> 3;
    00376         maxy = (maxy + 7) >> 3;
    00377
    00378         for(i=0; i<mPathPoints; ++i)
    00379         {
    00380                 mpPathPoints[i].x -= minx*8;
    00381                 mpPathPoints[i].y -= miny*8;
    00382         }
    00383
    00384         if(minx > maxx || miny > maxy)
    00385         {
    00386                 mWidth = mHeight = 0;
    00387                 mPathOffsetX = mPathOffsetY = 0;
    00388                 _TrashPath();
    00389                 return true;
    00390         }
    00391
    00392         mWidth = maxx + 1 - minx;
    00393         mHeight = maxy + 1 - miny;
    00394
    00395         mPathOffsetX = minx;
    00396         mPathOffsetY = miny;
    00397
    00398         // Initialize edge buffer.  We use edge 0 as a sentinel.
    00399
    00400         mEdgeNext = 1;
    00401         mEdgeHeapSize = 2048;
    00402         mpEdgeBuffer = (Edge*)malloc(sizeof(Edge)*mEdgeHeapSize);
    00403
    00404         // Initialize scanline list.
    00405
    00406         mpScanBuffer = new unsigned int[mHeight];
    00407         memset(mpScanBuffer, 0, mHeight*sizeof(unsigned int));
    00408
    00409         // Scan convert the outline.  Yuck, Bezier curves....
    00410
    00411         // Unfortunately, Windows 95/98 GDI has a bad habit of giving us text
    00412         // paths with all but the first figure left open, so we can't rely
    00413         // on the PT_CLOSEFIGURE flag being used appropriately.
    00414
    00415         fFirstSet = false;
    00416         firstp.x = firstp.y = 0;
    00417         lastp.x = lastp.y = 0;
    00418
    00419         for(i=0; i<mPathPoints; ++i)
    00420         {
    00421                 BYTE t = mpPathTypes[i] & ~PT_CLOSEFIGURE;
    00422
    00423                 switch(t)
    00424                 {
    00425                 case PT_MOVETO:
    00426                         if(lastmoveto >= 0 && firstp != lastp)
    00427                                 _EvaluateLine(lastp.x, lastp.y, firstp.x, firstp.y);
    00428                         lastmoveto = i;
    00429                         fFirstSet = false;
    00430                         lastp = mpPathPoints[i];
    00431                         break;
    00432                 case PT_MOVETONC:
    00433                         break;
    00434                 case PT_LINETO:
    00435                         if(mPathPoints - (i-1) >= 2) _EvaluateLine(i-1, i);
    00436                         break;
    00437                 case PT_BEZIERTO:
    00438                         if(mPathPoints - (i-1) >= 4) _EvaluateBezier(i-1, false);
    00439                         i += 2;
    00440                         break;
    00441                 case PT_BSPLINETO:
    00442                         if(mPathPoints - (i-1) >= 4) _EvaluateBezier(i-1, true);
    00443                         i += 2;
    00444                         break;
    00445                 case PT_BSPLINEPATCHTO:
    00446                         if(mPathPoints - (i-3) >= 4) _EvaluateBezier(i-3, true);
    00447                         break;
    00448                 }
    00449         }
    00450
    00451         if(lastmoveto >= 0 && firstp != lastp)
    00452                 _EvaluateLine(lastp.x, lastp.y, firstp.x, firstp.y);
    00453
    00454         // Free the path since we don't need it anymore.
    00455
    00456         _TrashPath();
    00457
    00458         // Convert the edges to spans.  We couldn't do this before because some of
    00459         // the regions may have winding numbers >+1 and it would have been a pain
    00460         // to try to adjust the spans on the fly.  We use one heap to detangle
    00461         // a scanline's worth of edges from the singly-linked lists, and another
    00462         // to collect the actual scans.
    00463
    00464         std::vector<int> heap;
    00465
    00466         mOutline.reserve(mEdgeNext / 2);
    00467
    00468         __int64 y = 0;
    00469
    00470         for(y=0; y<mHeight; ++y)
    00471         {
    00472                 int count = 0;
    00473
    00474                 // Detangle scanline into edge heap.
    00475
    00476                 for(unsigned ptr = (unsigned)(mpScanBuffer[y]&0xffffffff); ptr; ptr = mpEdgeBuffer[ptr].next)
    00477                 {
    00478                         heap.push_back(mpEdgeBuffer[ptr].posandflag);
    00479                 }
    00480
    00481                 // Sort edge heap.  Note that we conveniently made the opening edges
    00482                 // one more than closing edges at the same spot, so we won't have any
    00483                 // problems with abutting spans.
    00484
    00485                 std::sort(heap.begin(), heap.end()/*begin() + heap.size()*/);
    00486
    00487                 // Process edges and add spans.  Since we only check for a non-zero
    00488                 // winding number, it doesn't matter which way the outlines go!
    00489
    00490                 std::vector<int>::iterator itX1 = heap.begin();
    00491                 std::vector<int>::iterator itX2 = heap.end(); // begin() + heap.size();
    00492
    00493                 int x1, x2;
    00494
    00495                 for(; itX1 != itX2; ++itX1)
    00496                 {
    00497                         int x = *itX1;
    00498
    00499                         if(!count)
    00500                                 x1 = (x>>1);
    00501
    00502                         if(x&1)
    00503                                 ++count;
    00504                         else
    00505                                 --count;
    00506
    00507                         if(!count)
    00508                         {
    00509                                 x2 = (x>>1);
    00510
    00511                                 if(x2>x1)
    00512                                         mOutline.push_back(std::pair<__int64,__int64>((y<<32)+x1+0x4000000040000000i64, (y<<32)+x2+0x4000000040000000i64)); // G: damn Avery, this is evil! :)
    00513                         }
    00514                 }
    00515
    00516                 heap.clear();
    00517         }
    00518
    00519         // Dump the edge and scan buffers, since we no longer need them.
    00520
    00521         free(mpEdgeBuffer);
    00522         delete [] mpScanBuffer;
    00523
    00524         // All done!
    00525
    00526         return true;
    00527 }
    00528
    00529 using namespace std;
    00530
    00531 void Rasterizer::_OverlapRegion(tSpanBuffer& dst, tSpanBuffer& src, int dx, int dy)
    00532 {
    00533         tSpanBuffer temp;
    00534
    00535         temp.reserve(dst.size() + src.size());
    00536
    00537         dst.swap(temp);
    00538
    00539         tSpanBuffer::iterator itA = temp.begin();
    00540         tSpanBuffer::iterator itAE = temp.end();
    00541         tSpanBuffer::iterator itB = src.begin();
    00542         tSpanBuffer::iterator itBE = src.end();
    00543
    00544         // Don't worry -- even if dy<0 this will still work! // G: hehe, the evil twin :)
    00545
    00546         unsigned __int64 offset1 = (((__int64)dy)<<32) - dx;
    00547         unsigned __int64 offset2 = (((__int64)dy)<<32) + dx;
    00548
    00549         while(itA != itAE && itB != itBE)
    00550         {
    00551                 if((*itB).first + offset1 < (*itA).first)
    00552                 {
    00553                         // B span is earlier.  Use it.
    00554
    00555                         unsigned __int64 x1 = (*itB).first + offset1;
    00556                         unsigned __int64 x2 = (*itB).second + offset2;
    00557
    00558                         ++itB;
    00559
    00560                         // B spans don't overlap, so begin merge loop with A first.
    00561
    00562                         for(;;)
    00563                         {
    00564                                 // If we run out of A spans or the A span doesn't overlap,
    00565                                 // then the next B span can't either (because B spans don't
    00566                                 // overlap) and we exit.
    00567
    00568                                 if(itA == itAE || (*itA).first > x2)
    00569                                         break;
    00570
    00571                                 do {x2 = _MAX(x2, (*itA++).second);}
    00572                                 while(itA != itAE && (*itA).first <= x2);
    00573
    00574                                 // If we run out of B spans or the B span doesn't overlap,
    00575                                 // then the next A span can't either (because A spans don't
    00576                                 // overlap) and we exit.
    00577
    00578                                 if(itB == itBE || (*itB).first + offset1 > x2)
    00579                                         break;
    00580
    00581                                 do {x2 = _MAX(x2, (*itB++).second + offset2);}
    00582                                 while(itB != itBE && (*itB).first + offset1 <= x2);
    00583                         }
    00584
    00585                         // Flush span.
    00586
    00587                         dst.push_back(tSpan(x1, x2));
    00588                 }
    00589                 else
    00590                 {
    00591                         // A span is earlier.  Use it.
    00592
    00593                         unsigned __int64 x1 = (*itA).first;
    00594                         unsigned __int64 x2 = (*itA).second;
    00595
    00596                         ++itA;
    00597
    00598                         // A spans don't overlap, so begin merge loop with B first.
    00599
    00600                         for(;;)
    00601                         {
    00602                                 // If we run out of B spans or the B span doesn't overlap,
    00603                                 // then the next A span can't either (because A spans don't
    00604                                 // overlap) and we exit.
    00605
    00606                                 if(itB == itBE || (*itB).first + offset1 > x2)
    00607                                         break;
    00608
    00609                                 do {x2 = _MAX(x2, (*itB++).second + offset2);}
    00610                                 while(itB != itBE && (*itB).first + offset1 <= x2);
    00611
    00612                                 // If we run out of A spans or the A span doesn't overlap,
    00613                                 // then the next B span can't either (because B spans don't
    00614                                 // overlap) and we exit.
    00615
    00616                                 if(itA == itAE || (*itA).first > x2)
    00617                                         break;
    00618
    00619                                 do {x2 = _MAX(x2, (*itA++).second);}
    00620                                 while(itA != itAE && (*itA).first <= x2);
    00621                         }
    00622
    00623                         // Flush span.
    00624
    00625                         dst.push_back(tSpan(x1, x2));
    00626                 }
    00627         }
    00628
    00629         // Copy over leftover spans.
    00630
    00631         while(itA != itAE)
    00632                 dst.push_back(*itA++);
    00633
    00634         while(itB != itBE)
    00635         {
    00636                 dst.push_back(tSpan((*itB).first + offset1, (*itB).second + offset2));
    00637                 ++itB;
    00638         }
    00639 }
    00640
    00641 bool Rasterizer::CreateWidenedRegion(int r)
    00642 {
    00643         if(r < 0) r = 0;
    00644
    00645         for(int y = -r; y <= r; ++y)
    00646         {
    00647                 int x = (int)(0.5 + sqrt(float(r*r - y*y)));
    00648
    00649                 _OverlapRegion(mWideOutline, mOutline, x, y);
    00650         }
    00651
    00652         mWideBorder = r;
    00653
    00654         return true;
    00655 }
    00656
    00657 void Rasterizer::DeleteOutlines()
    00658 {
    00659         mWideOutline.clear();
    00660         mOutline.clear();
    00661 }
    00662
    00663 bool Rasterizer::Rasterize(int xsub, int ysub, bool fBlur)
    00664 {
    00665         _TrashOverlay();
    00666
    00667         if(!mWidth || !mHeight)
    00668         {
    00669                 mOverlayWidth = mOverlayHeight = 0;
    00670                 return true;
    00671         }
    00672
    00673         xsub &= 7;
    00674         ysub &= 7;
    00675
    00676         int width = mWidth + xsub;
    00677         int height = mHeight + ysub;
    00678
    00679         mOffsetX = mPathOffsetX - xsub;
    00680         mOffsetY = mPathOffsetY - ysub;
    00681
    00682         mWideBorder = (mWideBorder+7)&~7;
    00683
    00684         if(!mWideOutline.empty())
    00685         {
    00686                 width += 2*mWideBorder;
    00687                 height += 2*mWideBorder;
    00688
    00689                 xsub += mWideBorder;
    00690                 ysub += mWideBorder;
    00691
    00692                 mOffsetX -= mWideBorder;
    00693                 mOffsetY -= mWideBorder;
    00694         }
    00695
    00696         mOverlayWidth = ((width+7)>>3) + 1;
    00697         mOverlayHeight = ((height+7)>>3) + 1;
    00698
    00699         mpOverlayBuffer = new byte[2 * mOverlayWidth * mOverlayHeight];
    00700         memset(mpOverlayBuffer, 0, 2 * mOverlayWidth * mOverlayHeight);
    00701
    00702         // Are we doing a border?
    00703
    00704         tSpanBuffer* pOutline[2] = {&mOutline, &mWideOutline};
    00705
    00706         for(int i = countof(pOutline)-1; i >= 0; i--)
    00707         {
    00708                 tSpanBuffer::iterator it = pOutline[i]->begin();
    00709                 tSpanBuffer::iterator itEnd = pOutline[i]->end();
    00710
    00711                 for(; it!=itEnd; ++it)
    00712                 {
    00713                         int y = (int)(((*it).first >> 32) - 0x40000000 + ysub);
    00714                         int x1 = (int)(((*it).first & 0xffffffff) - 0x40000000 + xsub);
    00715                         int x2 = (int)(((*it).second & 0xffffffff) - 0x40000000 + xsub);
    00716
    00717                         if(x2 > x1)
    00718                         {
    00719                                 int first = x1>>3;
    00720                                 int last = (x2-1)>>3;
    00721                                 byte* dst = mpOverlayBuffer + 2*(mOverlayWidth*(y>>3) + first) + i;
    00722
    00723                                 if(first == last)
    00724                                         *dst += x2-x1;
    00725                                 else
    00726                                 {
    00727                                         *dst += ((first+1)<<3) - x1;
    00728                                         dst += 2;
    00729
    00730                                         while(++first < last)
    00731                                         {
    00732                                                 *dst += 0x08;
    00733                                                 dst += 2;
    00734                                         }
    00735
    00736                                         *dst += x2 - (last<<3);
    00737                                 }
    00738                         }
    00739                 }
    00740         }
    00741
    00742         if(fBlur && mOverlayWidth >= 3 && mOverlayHeight >= 3)
    00743         {
    00744                 int pitch = mOverlayWidth*2;
    00745
    00746                 byte* tmp = new byte[pitch*mOverlayHeight];
    00747                 if(!tmp) return(false);
    00748
    00749                 memcpy(tmp, mpOverlayBuffer, pitch*mOverlayHeight);
    00750
    00751                 int border = !mWideOutline.empty() ? 1 : 0;
    00752
    00753                 for(int j = 1; j < mOverlayHeight-1; j++)
    00754                 {
    00755                         byte* src = tmp + pitch*j + 2 + border;
    00756                         byte* dst = mpOverlayBuffer + pitch*j + 2 + border;
    00757
    00758                         for(int i = 1; i < mOverlayWidth-1; i++, src+=2, dst+=2)
    00759                         {
    00760                                 *dst = (src[-2-pitch] + (src[-pitch]<<1) + src[+2-pitch]
    00761                                         + (src[-2]<<1) + (src[0]<<2) + (src[+2]<<1)
    00762                                         + src[-2+pitch] + (src[+pitch]<<1) + src[+2+pitch]) >> 4;
    00763                         }
    00764                 }
    00765
    00766                 delete [] tmp;
    00767         }
    00768
    00769         return true;
    00770 }
    00771
    00773
    00774 #define pixmix(s) {                                                                                                                              \
    00775         int a = (((s)*(color>>24))>>6)&0xff;                                                                             \
    00776         int ia = 256-a;                                                                                                                          \
    00777                                                                                                                                                                  \
    00778         dst[wt] = ((((dst[wt]&0x00ff00ff)*ia + (color&0x00ff00ff)*a)&0xff00ff00)>>8) \
    00779                         | ((((dst[wt]&0x0000ff00)*ia + (color&0x0000ff00)*a)&0x00ff0000)>>8) \
    00780                         | ((((dst[wt]>>8)&0x00ff0000)*ia)&0xff000000);                                           \
    00781         } \
    00782
    00783 #include <xmmintrin.h>
    00784 #include <emmintrin.h>
    00785
    00786 __forceinline void pixmix_sse2(DWORD* dst, DWORD color, DWORD alpha)
    00787 {
    00788         alpha = ((alpha * (color>>24)) >> 6) & 0xff;
    00789         color &= 0xffffff;
    00790
    00791         __m128i zero = _mm_setzero_si128();
    00792         __m128i a = _mm_set1_epi32((alpha << 16) | (0x100 - alpha));
    00793         __m128i d = _mm_unpacklo_epi8(_mm_cvtsi32_si128(*dst), zero);
    00794         __m128i s = _mm_unpacklo_epi8(_mm_cvtsi32_si128(color), zero);
    00795         __m128i r = _mm_unpacklo_epi16(d, s);
    00796
    00797         r = _mm_madd_epi16(r, a);
    00798         r = _mm_srli_epi32(r, 8);
    00799         r = _mm_packs_epi32(r, r);
    00800         r = _mm_packus_epi16(r, r);
    00801
    00802         *dst = (DWORD)_mm_cvtsi128_si32(r);
    00803 }
    00804
    00805 #include "../dsutil/vd.h"
    00806
    00807 CRect Rasterizer::Draw(SubPicDesc& spd, CRect& clipRect, byte* pAlphaMask, int xsub, int ysub, const long* switchpts, bool fBody, bool fBorder)
    00808 {
    00809         CRect bbox(0, 0, 0, 0);
    00810
    00811         if(!switchpts || !fBody && !fBorder) return(bbox);
    00812
    00813         // clip
    00814
    00815         CRect r(0, 0, spd.w, spd.h);
    00816         r &= clipRect;
    00817
    00818         int x = (xsub + mOffsetX + 4)>>3;
    00819         int y = (ysub + mOffsetY + 4)>>3;
    00820         int w = mOverlayWidth;
    00821         int h = mOverlayHeight;
    00822         int xo = 0, yo = 0;
    00823
    00824         if(x < r.left) {xo = r.left-x; w -= r.left-x; x = r.left;}
    00825         if(y < r.top) {yo = r.top-y; h -= r.top-y; y = r.top;}
    00826         if(x+w > r.right) w = r.right-x;
    00827         if(y+h > r.bottom) h = r.bottom-y;
    00828
    00829         if(w <= 0 || h <= 0) return(bbox);
    00830
    00831         bbox.SetRect(x, y, x+w, y+h);
    00832         bbox &= CRect(0, 0, spd.w, spd.h);
    00833
    00834         // draw
    00835
    00836         const byte* src = mpOverlayBuffer + 2*(mOverlayWidth * yo + xo);
    00837         const byte* s = fBorder ? (src+1) : src;
    00838         const byte* am = pAlphaMask + spd.w * y + x;
    00839         unsigned long* dst = (unsigned long *)((char *)spd.bits + spd.pitch * y) + x;
    00840
    00841         unsigned long color = switchpts[0];
    00842
    00843         bool fSSE2 = !!(g_cpuid.m_flags & CCpuID::sse2);
    00844
    00845         while(h--)
    00846         {
    00847                 if(!pAlphaMask)
    00848                 {
    00849                         if(switchpts[1] == 0xffffffff)
    00850                         {
    00851                                 if(fBody)
    00852                                 {
    00853                                         if(fSSE2) for(int wt=0; wt<w; ++wt) pixmix_sse2(&dst[wt], color, s[wt*2]);
    00854                                         else for(int wt=0; wt<w; ++wt) pixmix(s[wt*2]);
    00855                                 }
    00856                                 else
    00857                                 {
    00858                                         if(fSSE2) for(int wt=0; wt<w; ++wt) pixmix_sse2(&dst[wt], color, src[wt*2+1] - src[wt*2]);
    00859                                         else for(int wt=0; wt<w; ++wt) pixmix(src[wt*2+1] - src[wt*2]);
    00860                                 }
    00861                         }
    00862                         else
    00863                         {
    00864                                 const long *sw = switchpts;
    00865
    00866                                 if(fBody)
    00867                                 {
    00868                                         if(fSSE2)
    00869                                         for(int wt=0; wt<w; ++wt)
    00870                                         {
    00871                                                 if(wt+xo >= sw[1]) {while(wt+xo >= sw[1]) sw += 2; color = sw[-2];}
    00872                                                 pixmix_sse2(&dst[wt], color, s[wt*2]);
    00873                                         }
    00874                                         else
    00875                                         for(int wt=0; wt<w; ++wt)
    00876                                         {
    00877                                                 if(wt+xo >= sw[1]) {while(wt+xo >= sw[1]) sw += 2; color = sw[-2];}
    00878                                                 pixmix(s[wt*2]);
    00879                                         }
    00880                                 }
    00881                                 else
    00882                                 {
    00883                                         if(fSSE2)
    00884                                         for(int wt=0; wt<w; ++wt)
    00885                                         {
    00886                                                 if(wt+xo >= sw[1]) {while(wt+xo >= sw[1]) sw += 2; color = sw[-2];}
    00887                                                 pixmix_sse2(&dst[wt], color, src[wt*2+1] - src[wt*2]);
    00888                                         }
    00889                                         else
    00890                                         for(int wt=0; wt<w; ++wt)
    00891                                         {
    00892                                                 if(wt+xo >= sw[1]) {while(wt+xo >= sw[1]) sw += 2; color = sw[-2];}
    00893                                                 pixmix(src[wt*2+1] - src[wt*2]);
    00894                                         }
    00895                                 }
    00896                         }
    00897                 }
    00898                 else
    00899                 {
    00900                         if(switchpts[1] == 0xffffffff)
    00901                         {
    00902                                 if(fBody)
    00903                                 {
    00904                                         if(fSSE2) for(int wt=0; wt<w; ++wt) pixmix_sse2(&dst[wt], color, s[wt*2] * am[wt]);
    00905                                         else for(int wt=0; wt<w; ++wt) pixmix(s[wt*2] * am[wt]);
    00906                                 }
    00907                                 else
    00908                                 {
    00909                                         if(fSSE2) for(int wt=0; wt<w; ++wt) pixmix_sse2(&dst[wt], color, (src[wt*2+1] - src[wt*2]) * am[wt]);
    00910                                         else for(int wt=0; wt<w; ++wt) pixmix((src[wt*2+1] - src[wt*2]) * am[wt]);
    00911                                 }
    00912                         }
    00913                         else
    00914                         {
    00915                                 const long *sw = switchpts;
    00916
    00917                                 if(fBody)
    00918                                 {
    00919                                         if(fSSE2)
    00920                                         for(int wt=0; wt<w; ++wt)
    00921                                         {
    00922                                                 if(wt+xo >= sw[1]) {while(wt+xo >= sw[1]) sw += 2; color = sw[-2];}
    00923                                                 pixmix_sse2(&dst[wt], color, s[wt*2] * am[wt]);
    00924                                         }
    00925                                         else
    00926                                         for(int wt=0; wt<w; ++wt)
    00927                                         {
    00928                                                 if(wt+xo >= sw[1]) {while(wt+xo >= sw[1]) sw += 2; color = sw[-2];}
    00929                                                 pixmix(s[wt*2] * am[wt]);
    00930                                         }
    00931                                 }
    00932                                 else
    00933                                 {
    00934                                         if(fSSE2)
    00935                                         for(int wt=0; wt<w; ++wt)
    00936                                         {
    00937                                                 if(wt+xo >= sw[1]) {while(wt+xo >= sw[1]) sw += 2; color = sw[-2];}
    00938                                                 pixmix_sse2(&dst[wt], color, (src[wt*2+1] - src[wt*2]) * am[wt]);
    00939                                         }
    00940                                         else
    00941                                         for(int wt=0; wt<w; ++wt)
    00942                                         {
    00943                                                 if(wt+xo >= sw[1]) {while(wt+xo >= sw[1]) sw += 2; color = sw[-2];}
    00944                                                 pixmix((src[wt*2+1] - src[wt*2]) * am[wt]);
    00945                                         }
    00946                                 }
    00947                         }
    00948                 }
    00949
    00950                 src += 2*mOverlayWidth;
    00951                 s += 2*mOverlayWidth;
    00952                 am += spd.w;
    00953                 dst = (unsigned long *)((char *)dst + spd.pitch);
    00954         }
    00955
    00956         return bbox;
    00957 }