gblend.cpp

Go to the documentation of this file.
00001 // $Id: gblend.cpp 751 2006-03-31 15:43:49Z alex $
00002 /* @@tag:xara-cn@@ DO NOT MODIFY THIS LINE
00003 ================================XARAHEADERSTART===========================
00004  
00005                Xara LX, a vector drawing and manipulation program.
00006                     Copyright (C) 1993-2006 Xara Group Ltd.
00007        Copyright on certain contributions may be held in joint with their
00008               respective authors. See AUTHORS file for details.
00009 
00010 LICENSE TO USE AND MODIFY SOFTWARE
00011 ----------------------------------
00012 
00013 This file is part of Xara LX.
00014 
00015 Xara LX is free software; you can redistribute it and/or modify it
00016 under the terms of the GNU General Public License version 2 as published
00017 by the Free Software Foundation.
00018 
00019 Xara LX and its component source files are distributed in the hope
00020 that it will be useful, but WITHOUT ANY WARRANTY; without even the
00021 implied warranty of MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.
00022 See the GNU General Public License for more details.
00023 
00024 You should have received a copy of the GNU General Public License along
00025 with Xara LX (see the file GPL in the root directory of the
00026 distribution); if not, write to the Free Software Foundation, Inc., 51
00027 Franklin St, Fifth Floor, Boston, MA  02110-1301 USA
00028 
00029 
00030 ADDITIONAL RIGHTS
00031 -----------------
00032 
00033 Conditional upon your continuing compliance with the GNU General Public
00034 License described above, Xara Group Ltd grants to you certain additional
00035 rights. 
00036 
00037 The additional rights are to use, modify, and distribute the software
00038 together with the wxWidgets library, the wxXtra library, and the "CDraw"
00039 library and any other such library that any version of Xara LX relased
00040 by Xara Group Ltd requires in order to compile and execute, including
00041 the static linking of that library to XaraLX. In the case of the
00042 "CDraw" library, you may satisfy obligation under the GNU General Public
00043 License to provide source code by providing a binary copy of the library
00044 concerned and a copy of the license accompanying it.
00045 
00046 Nothing in this section restricts any of the rights you have under
00047 the GNU General Public License.
00048 
00049 
00050 SCOPE OF LICENSE
00051 ----------------
00052 
00053 This license applies to this program (XaraLX) and its constituent source
00054 files only, and does not necessarily apply to other Xara products which may
00055 in part share the same code base, and are subject to their own licensing
00056 terms.
00057 
00058 This license does not apply to files in the wxXtra directory, which
00059 are built into a separate library, and are subject to the wxWindows
00060 license contained within that directory in the file "WXXTRA-LICENSE".
00061 
00062 This license does not apply to the binary libraries (if any) within
00063 the "libs" directory, which are subject to a separate license contained
00064 within that directory in the file "LIBS-LICENSE".
00065 
00066 
00067 ARRANGEMENTS FOR CONTRIBUTION OF MODIFICATIONS
00068 ----------------------------------------------
00069 
00070 Subject to the terms of the GNU Public License (see above), you are
00071 free to do whatever you like with your modifications. However, you may
00072 (at your option) wish contribute them to Xara's source tree. You can
00073 find details of how to do this at:
00074   http://www.xaraxtreme.org/developers/
00075 
00076 Prior to contributing your modifications, you will need to complete our
00077 contributor agreement. This can be found at:
00078   http://www.xaraxtreme.org/developers/contribute/
00079 
00080 Please note that Xara will not accept modifications which modify any of
00081 the text between the start and end of this header (marked
00082 XARAHEADERSTART and XARAHEADEREND).
00083 
00084 
00085 MARKS
00086 -----
00087 
00088 Xara, Xara LX, Xara X, Xara X/Xtreme, Xara Xtreme, the Xtreme and Xara
00089 designs are registered or unregistered trademarks, design-marks, and/or
00090 service marks of Xara Group Ltd. All rights in these marks are reserved.
00091 
00092 
00093       Xara Group Ltd, Gaddesden Place, Hemel Hempstead, HP2 6EX, UK.
00094                         http://www.xara.com/
00095 
00096 =================================XARAHEADEREND============================
00097  */
00098 // Gavin's blend code
00099 
00100 /*
00101 */
00102 
00103 #include "camtypes.h"
00104 
00106 //
00107 // GBlend.cpp
00108 //
00110 
00111 #include <math.h>
00112 #include "gblend.h"
00113 
00116 
00117 CONST BYTE PT_END = 0 ;
00118 
00119 inline BOOL IsntEnd( BYTE Type )
00120 {
00121     return Type!=PT_END ;
00122 }
00123 
00124 inline BOOL IsntMove( BYTE Type )
00125 {
00126     return (Type & PT_MOVETO)!=PT_MOVETO ;
00127 }
00128 
00129 inline BOOL IsLine( BYTE Type )
00130 {
00131     return (Type & PT_MOVETO)==PT_LINETO ;
00132 }
00133 
00134 inline BOOL IsCurve( BYTE Type )
00135 {
00136     return (Type & PT_MOVETO)==PT_BEZIERTO ;
00137 }
00138 
00139 inline BOOL IsntCurve( BYTE Type )
00140 {
00141     return (Type & PT_MOVETO)!=PT_BEZIERTO ;
00142 }
00143 
00145 
00146 inline UINT32 ScaledDiv( UINT32 N, UINT32 D )
00147 {
00148     if (D == 0)
00149         return 1;
00150 #if defined(__WXMSW__)
00151     UINT32 temp ;
00152     __asm {
00153         mov     eax,N
00154         xor     edx,edx
00155         shld    edx,eax,28
00156         shl     eax,28
00157         div     D
00158         mov     temp,eax
00159     }
00160     return temp ;
00161 #else
00162     return UINT32((UINT64(N)<<28)/D);
00163 #endif
00164 }
00165 
00166 inline INT32 ScaledMul( INT32 X, INT32 N )
00167 {
00168 //  return X*N/0x10000000 ;
00169 #if defined(__WXMSW__)
00170     UINT32 temp ;
00171     __asm {
00172         mov     eax,X
00173         imul    N
00174         shrd    eax,edx,28
00175         mov     temp,eax
00176     }
00177     return temp ;
00178 #else
00179     return INT32(INT64(X)*N>>28);
00180 #endif
00181 }
00182 
00183 inline UINT32 length( POINT P0, POINT P1 )
00184 {
00185 #if defined(__WXMSW__)
00186     union {
00187         struct {
00188             DWORD lo ;
00189             DWORD hi ;
00190         } itemp ;
00191         double ftemp ;
00192     } val ;
00193     __asm {
00194         mov     eax,P1.x
00195         sub     eax,P0.x
00196         imul    eax
00197         mov     ebx,eax
00198         mov     ecx,edx
00199         mov     eax,P1.y
00200         sub     eax,P0.y
00201         imul    eax
00202         add     eax,ebx
00203         adc     edx,ecx
00204         mov     val.itemp.lo,eax
00205         mov     val.itemp.hi,edx
00206         fild    val.ftemp
00207         fsqrt
00208         fistp   val.itemp.lo
00209     }
00210     return val.itemp.lo ;
00211 #else
00212     return (UINT32)sqrt( double(P1.x-P0.x)*(P1.x-P0.x)+double(P1.y-P0.y)*(P1.y-P0.y) ) ;
00213 #endif
00214 }
00215 
00218 
00219 void GBlend::Define(
00220         PPOINT  Src0Points,
00221         PBYTE   Src0Types,
00222         UINT32  Src0Length,
00223         PPOINT  Src1Points,
00224         PBYTE   Src1Types,
00225         UINT32  Src1Length,
00226         BOOL    Flag,
00227         UINT32  pFlatness,
00228         PUINT32 Buffer,
00229         UINT32  BufferLength
00230     )
00231 {
00232     S0Points    = Src0Points ;
00233     S0Types     = Src0Types ;
00234     S0Length    = Src0Length ;
00235     S1Points    = Src1Points ;
00236     S1Types     = Src1Types ;
00237     S1Length    = Src1Length ;
00238     Is1to1      = Flag ;
00239     Flatness    = pFlatness*27/2 ;
00240     CalcPathLengths(
00241         S0Points, S0Types, S0Length,
00242         LengthPtr0 = Buffer,
00243         BufferLength,
00244         EndLengthPtr0
00245     ) ;
00246     CalcPathLengths(
00247         S1Points, S1Types, S1Length,
00248         LengthPtr1 = EndLengthPtr0,
00249         BufferLength-(EndLengthPtr0-LengthPtr0),
00250         EndLengthPtr1
00251     ) ;
00252     Is1to1 = Is1to1 && (EndLengthPtr0-LengthPtr0)==(EndLengthPtr1-LengthPtr1) ;
00253 }
00254 
00255 UINT32 GBlend::Blend( double pRatio, PPOINT DPoints, PBYTE DTypes, INT32 DLength )
00256 {
00257     Ratio       = (INT32) (pRatio*0x10000000) ;
00258     OPoints     = DPoints ;
00259     OTypes      = DTypes ;
00260     OLength     = DLength ;
00261     IPoints0    = S0Points ;
00262     ITypes0     = S0Types ;
00263     ILength0    = S0Length ;
00264     IPoints1    = S1Points ;
00265     ITypes1     = S1Types ;
00266     ILength1    = S1Length ;
00267     LPtr0       = LengthPtr0 ;
00268     LPtr1       = LengthPtr1 ;
00269     P00 = *IPoints0++ ; Type0 = *ITypes0++ ; ILength0-- ;
00270     P10 = *IPoints1++ ; Type1 = *ITypes1++ ; ILength1-- ;
00271     if ( !BlendPoint( PT_MOVETO, P00, P10 ) )
00272         return FALSE ;
00273     Length0 = 0 ; ReadPathStart0() ;
00274     Length1 = 0 ; ReadPathStart1() ;
00275     if ( Is1to1 )
00276     {
00277         if ( !BlendNtoN() )
00278             return 0 ;
00279     }
00280     else
00281     {
00282         if ( !BlendMtoN() )
00283             return 0 ;
00284     }
00285     return OTypes-DTypes ;
00286 }
00287 
00289 
00290 BOOL GBlend::CalcPathLengths(
00291         PPOINT  Points,
00292         PBYTE   Types,
00293         UINT32  Length,
00294         PUINT32 Buffer,
00295         UINT32  BufferLength,
00296         PUINT32 &BufferEnd
00297     )
00298 {
00299     UINT32 TotalLength = 0 ;
00300     BufferEnd = Buffer ;
00301     UINT32 i = 1 ;
00302     while ( i<Length )
00303     {
00304         if ( IsLine(Types[i]) )
00305         {
00306             *BufferEnd = length( Points[i-1],Points[i] ) ;
00307             i++ ;
00308         }
00309         else /* Curve */
00310         {
00311             *BufferEnd = BezierLength( Points[i-1],Points[i],Points[i+1],Points[i+2] ) ;
00312             i+=3 ;
00313         }
00314         TotalLength += *BufferEnd++ ;
00315     }
00316     PUINT32 P = Buffer ;
00317     UINT32 Total = 0 ;
00318     while ( P<BufferEnd )
00319     {
00320         *P = ScaledDiv( *P, TotalLength ) ;
00321         Total += *P++ ;
00322     }
00323     if ( Total != 0x10000000 )
00324     {
00325         while ( *(--P)+0x10000000 <= Total )
00326         { }
00327         *P -= Total-0x10000000 ;
00328     }
00329     return TRUE ;
00330 }
00331 
00333 
00334 BOOL GBlend::BlendNtoN()
00335 {
00336     while ( IsntEnd(Type0) || IsntEnd(Type1) )
00337         if ( !Blend1to1() )
00338             return FALSE ;
00339     return TRUE ;
00340 }
00341 
00342 BOOL GBlend::BlendMtoN()
00343 {
00344     UINT32 t ;
00345     while ( IsntEnd(Type0) || IsntEnd(Type1) )
00346     {
00347         if ( LPtr1==EndLengthPtr1-1 )
00348             MatchLast( LPtr0, EndLengthPtr0, *LPtr1+Length1-Length0, Match0, Total0 ) ;
00349         else
00350             Match    ( LPtr0, EndLengthPtr0, *LPtr1+Length1-Length0, Match0, Total0 ) ;
00351         if ( LPtr0==EndLengthPtr0-1 )
00352             MatchLast( LPtr1, EndLengthPtr1, *LPtr0+Length0-Length1, Match1, Total1 ) ;
00353         else
00354             Match    ( LPtr1, EndLengthPtr1, *LPtr0+Length0-Length1, Match1, Total1 ) ;
00355         if ( abs(Match0)<abs(Match1) )
00356         {
00357             if ( Total0!=1 )
00358             {
00359                 Match0 += *LPtr1+Length1-Length0 ;
00360                 if ( IsntCurve(Type1) )
00361                 {
00362                     P11.x = (2*P10.x+P13.x)/3 ; P12.x = (P10.x+2*P13.x)/3 ;
00363                     P11.y = (2*P10.y+P13.y)/3 ; P12.y = (P10.y+2*P13.y)/3 ;
00364                 }
00365                 for ( t=2 ; t<=Total0 ; t++ )
00366                 {
00367                     if ( IsCurve(Type0) || IsCurve(Type1) )
00368                     {
00369                         if ( IsntCurve(Type0) )
00370                         {
00371                             P01.x = (2*P00.x+P03.x)/3 ; P02.x = (P00.x+2*P03.x)/3 ;
00372                             P01.y = (2*P00.y+P03.y)/3 ; P02.y = (P00.y+2*P03.y)/3 ;
00373                         }
00374                         Split( P10,P11,P12,P13, *LPtr0,Match0 ) ;
00375                         if ( !BlendCurve( P01,P02,P03, L1,L2,M ) )
00376                             return FALSE ;
00377                         P10 = M ;
00378                         P11 = R1 ;
00379                         P12 = R2 ;
00380                     }
00381                     else
00382                     {
00383                         P10.x += MulDiv(P13.x-P10.x,*LPtr0,Match0) ;
00384                         P10.y += MulDiv(P13.y-P10.y,*LPtr0,Match0) ;
00385                         if ( !BlendPoint( PT_LINETO, P03, P10 ) )
00386                             return FALSE ;
00387                     }
00388                     P00 = P03 ;
00389                     Match0 -= *LPtr0 ;
00390                     ReadPath0() ;
00391                 }
00392             }
00393         }
00394         else
00395         {
00396             if ( Total1!=1 )
00397             {
00398                 Match1 += *LPtr0+Length0-Length1 ;
00399                 if ( IsntCurve(Type0) )
00400                 {
00401                     P01.x = (2*P00.x+P03.x)/3 ; P02.x = (P00.x+2*P03.x)/3 ;
00402                     P01.y = (2*P00.y+P03.y)/3 ; P02.y = (P00.y+2*P03.y)/3 ;
00403                 }
00404                 for ( t=2 ; t<=Total1 ; t++ )
00405                 {
00406                     if ( IsCurve(Type0) || IsCurve(Type1) )
00407                     {
00408                         if ( IsntCurve(Type1) )
00409                         {
00410                             P11.x = (2*P10.x+P13.x)/3 ; P12.x = (P10.x+2*P13.x)/3 ;
00411                             P11.y = (2*P10.y+P13.y)/3 ; P12.y = (P10.y+2*P13.y)/3 ;
00412                         }
00413                         Split( P00,P01,P02,P03, *LPtr1,Match1 ) ;
00414                         if ( !BlendCurve( L1,L2,M, P11,P12,P13 ) )
00415                             return FALSE ;
00416                         P00 = M ;
00417                         P01 = R1 ;
00418                         P02 = R2 ;
00419                     }
00420                     else
00421                     {
00422                         P00.x += MulDiv(P03.x-P00.x,*LPtr1,Match1) ;
00423                         P00.y += MulDiv(P03.y-P00.y,*LPtr1,Match1) ;
00424                         if ( !BlendPoint( PT_LINETO, P00, P13 ) )
00425                             return FALSE ;
00426                     }
00427                     P10 = P13 ;
00428                     Match1 -= *LPtr1 ;
00429                     ReadPath1() ;
00430                 }
00431             }
00432         }
00433         if ( !Blend1to1() )
00434             return FALSE ;
00435     } /* while */
00436     return TRUE ;
00437 }
00438 
00439 BOOL GBlend::Blend1to1()
00440 {
00441     if ( IsCurve(Type0) || IsCurve(Type1) )
00442     {
00443         if ( IsntCurve(Type0) )
00444         {
00445             P01.x = (2*P00.x+P03.x)/3 ; P02.x = (P00.x+2*P03.x)/3 ;
00446             P01.y = (2*P00.y+P03.y)/3 ; P02.y = (P00.y+2*P03.y)/3 ;
00447         }
00448         if ( IsntCurve(Type1) )
00449         {
00450             P11.x = (2*P10.x+P13.x)/3 ; P12.x = (P10.x+2*P13.x)/3 ;
00451             P11.y = (2*P10.y+P13.y)/3 ; P12.y = (P10.y+2*P13.y)/3 ;
00452         }
00453         if ( !BlendCurve( P01,P02,P03, P11,P12,P13 ) )
00454             return FALSE ;
00455     }
00456     else
00457         if ( !BlendPoint( PT_LINETO, P03, P13 ) )
00458             return FALSE ;
00459     P00 = P03 ; ReadPath0() ;
00460     P10 = P13 ; ReadPath1() ;
00461     return TRUE ;
00462 }
00463 
00464 BOOL GBlend::BlendPoint( BYTE Type, POINT P0, POINT P1 )
00465 {
00466     if ( --OLength<0 )
00467         return FALSE ;
00468     *OTypes++ = Type ;
00469     OPoints->x = P0.x+ScaledMul(Ratio,P1.x-P0.x) ;
00470     OPoints->y = P0.y+ScaledMul(Ratio,P1.y-P0.y) ;
00471     OPoints++ ;
00472     return TRUE ;
00473 }
00474 
00475 BOOL GBlend::BlendCurve( POINT P01,POINT P02,POINT P03, POINT P11,POINT P12,POINT P13 )
00476 {
00477     return BlendPoint( PT_BEZIERTO, P01, P11 ) &&
00478            BlendPoint( PT_BEZIERTO, P02, P12 ) &&
00479            BlendPoint( PT_BEZIERTO, P03, P13 ) ;
00480 }
00481 
00482 void GBlend::Match( PUINT32 Ptr, PUINT32 EndPtr, UINT32 Length, INT32 &Match, UINT32 &Total )
00483 {
00484     Match = -(INT32)Length ;
00485     Total = 0 ;
00486     if ( Ptr<EndPtr )
00487     {
00488         Match += *Ptr++ ;
00489         Total++ ;
00490         while ( Ptr<EndPtr-1 && abs((INT32)Match)>abs((INT32)(*Ptr+Match)) )
00491         {
00492             Match += *Ptr++ ;
00493             Total++ ;
00494         }
00495     }
00496 }
00497 
00498 void GBlend::MatchLast( PUINT32 Ptr, PUINT32 EndPtr, UINT32 Length, INT32 &Match, UINT32 &Total )
00499 {
00500     Match = -(INT32)Length ;
00501     Total = 0 ;
00502     while ( Ptr<EndPtr )
00503     {
00504         Match += *Ptr++ ;
00505         Total++ ;
00506     }
00507 }
00508 
00509 void GBlend::Split( POINT P0,POINT P1,POINT P2,POINT P3, INT32 N,UINT32 D )
00510 {
00511     L1.x = P0.x+MulDiv(P1.x-P0.x,N,D) ; L1.y = P0.y+MulDiv(P1.y-P0.y,N,D) ;
00512      M.x = P1.x+MulDiv(P2.x-P1.x,N,D) ;  M.y = P1.y+MulDiv(P2.y-P1.y,N,D) ;
00513     R2.x = P2.x+MulDiv(P3.x-P2.x,N,D) ; R2.y = P2.y+MulDiv(P3.y-P2.y,N,D) ;
00514     L2.x = L1.x+MulDiv( M.x-L1.x,N,D) ; L2.y = L1.y+MulDiv( M.y-L1.y,N,D) ;
00515     R1.x =  M.x+MulDiv(R2.x- M.x,N,D) ; R1.y =  M.y+MulDiv(R2.y- M.y,N,D) ;
00516      M.x = L2.x+MulDiv(R1.x-L2.x,N,D) ;  M.y = L2.y+MulDiv(R1.y-L2.y,N,D) ;
00517 }
00518 
00520 
00521 void GBlend::ReadPath0()
00522 {
00523     Length0 += *LPtr0++ ;
00524     ReadPathStart0() ;
00525 }
00526 
00527 void GBlend::ReadPathStart0()
00528 {
00529     if ( ILength0==0 )
00530         Type0 = PT_END ;
00531     else if ( IsLine(Type0=*ITypes0) )
00532     {
00533         ITypes0++ ;
00534         P03 = *IPoints0++ ;
00535         ILength0-- ;
00536     }
00537     else /* Curve */
00538     {
00539         ITypes0+=3 ;
00540         P01 = *IPoints0++ ;
00541         P02 = *IPoints0++ ;
00542         P03 = *IPoints0++ ;
00543         ILength0-=3 ;
00544     }
00545 }
00546 
00547 void GBlend::ReadPath1()
00548 {
00549     Length1 += *LPtr1++ ;
00550     ReadPathStart1() ;
00551 }
00552 
00553 void GBlend::ReadPathStart1()
00554 {
00555     if ( ILength1==0 )
00556         Type1 = PT_END ;
00557     else if ( IsLine(Type1=*ITypes1) )
00558     {
00559         ITypes1++ ;
00560         P13 = *IPoints1++ ;
00561         ILength1-- ;
00562     }
00563     else /* Curve */
00564     {
00565         ITypes1+=3 ;
00566         P11 = *IPoints1++ ;
00567         P12 = *IPoints1++ ;
00568         P13 = *IPoints1++ ;
00569         ILength1-=3 ;
00570     }
00571 }
00572 
00574 
00575 INT32 GBlend::BezierLength( POINT P0, POINT P1, POINT P2, POINT P3 )
00576 {
00577     UINT32 dx,dy ;
00578     dx = abs(P1.x*3 - P0.x*2 - P3.x) ;
00579     dy = abs(P1.y*3 - P0.y*2 - P3.y) ;
00580     if ( (dx>=dy ? 3*dx+dy : dx+3*dy) > Flatness )
00581         return FlattenSplit(P0,P1,P2,P3) ;
00582     dx = abs(P2.x*3 - P0.x - P3.x*2) ;
00583     dy = abs(P2.y*3 - P0.y - P3.y*2) ;
00584     if ( (dx>=dy ? 3*dx+dy : dx+3*dy) > Flatness )
00585         return FlattenSplit(P0,P1,P2,P3) ;
00586     return length(P0,P3) ;
00587 }
00588 
00589 
00590 INT32 GBlend::FlattenSplit( POINT P0, POINT P1, POINT P2, POINT P3 )
00591 {
00592     POINT L1, L2, M, R1, R2 ;
00593     L1.x = (P0.x + P1.x)/2;
00594     L1.y = (P0.y + P1.y)/2;
00595     L2.x = (P0.x + 2*P1.x + P2.x)/4;
00596     L2.y = (P0.y + 2*P1.y + P2.y)/4;
00597      M.x = (P0.x + 3*P1.x + 3*P2.x + P3.x)/8;
00598      M.y = (P0.y + 3*P1.y + 3*P2.y + P3.y)/8;
00599     R1.x = (P1.x + 2*P2.x + P3.x)/4;
00600     R1.y = (P1.y + 2*P2.y + P3.y)/4;
00601     R2.x = (P2.x + P3.x)/2;
00602     R2.y = (P2.y + P3.y)/2;
00603     return BezierLength(P0, L1, L2, M) + BezierLength(M, R1, R2, P3) ;
00604 }
00605 

Generated on Sat Nov 10 03:45:25 2007 for Camelot by  doxygen 1.4.4