gwinding.cpp

Go to the documentation of this file.
00001 // $Id: gwinding.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 path winding code
00099 
00100 /*
00101 */
00102 
00103 #include "camtypes.h"
00104 
00106 //
00107 // GWinding.cpp
00108 //
00110 
00111 #include <math.h>
00112 #include "gwinding.h"
00113 
00116 
00117 INT32 GWSgnMulSubMul( INT32 A, INT32 B, INT32 C, INT32 D )
00118 {
00119 #if defined(__WXMSW__)
00120     UINT32 temp ;
00121     __asm {
00122         mov     eax,A
00123         imul    B
00124         mov     ebx,eax
00125         mov     ecx,edx
00126         mov     eax,C
00127         imul    D
00128         sub     ebx,eax
00129         sbb     ecx,edx
00130         jne     returnecx
00131         or      ecx,ebx
00132         jns     returnecx
00133             not     ecx
00134 returnecx:
00135         mov     temp,ecx
00136     }
00137     return temp;
00138 #else
00139     XLONG X = (XLONG)A*B-(XLONG)C*D;
00140     return X>0 ? 1 : X<0 ? -1 : 0 ;
00141 #endif
00142 }
00143 
00145 
00146 PPOINT Points ;
00147 PPOINT StartPoint ;
00148 
00149 POINT BottomLeft ;
00150 POINT PrevPoint ;
00151 POINT LastPoint ;
00152 POINT OldPoint ;
00153 
00154 POINT Prev_Point ;
00155 POINT Next_Point ;
00156 
00157 INT32 Flags ;
00158 
00159 UINT32 Flatness ;
00160 UINT32 BottomLeftOffset ;
00161 
00163 
00164 void DoLine( POINT P )
00165 {
00166     if ( (Flags & 04) && ( OldPoint.x!=LastPoint.x || OldPoint.y!=LastPoint.y ) )
00167     {
00168         PrevPoint = LastPoint ;
00169         Flags &= ~04 ;
00170     }
00171     if (  P.x+P.y >  BottomLeft.x+BottomLeft.y ||
00172          (P.x+P.y == BottomLeft.x+BottomLeft.y &&
00173               P.y >=              BottomLeft.y) )
00174     {
00175         if ( (Flags & 02) && ( P.x!=BottomLeft.x ||
00176                                P.y!=BottomLeft.y ) )
00177         {
00178             Next_Point = P ;
00179             Flags &= ~02 ;
00180         }
00181         Flags |= 04 ;
00182     }
00183     else
00184     {
00185         Prev_Point = PrevPoint ;
00186         BottomLeft = P ;
00187         BottomLeftOffset = Points-StartPoint ; /* Save curve offset */
00188         Flags = 02 ;
00189         PrevPoint = P ;
00190     }
00191     OldPoint = LastPoint ;
00192     LastPoint = P ;
00193 }
00194 
00196 
00197 void FlattenSplit( POINT P0, POINT P1, POINT P2, POINT P3 ) ;
00198 
00199 void FlattenCurve( POINT P0, POINT P1, POINT P2, POINT P3 )
00200 {
00201     UINT32 dx,dy ;
00202     dx = abs(P1.x*3 - P0.x*2 - P3.x) ;
00203     dy = abs(P1.y*3 - P0.y*2 - P3.y) ;
00204     if ( (dx>=dy ? 3*dx+dy : dx+3*dy) > Flatness )
00205         FlattenSplit(P0,P1,P2,P3) ;
00206     else
00207     {
00208         dx = abs(P2.x*3 - P0.x - P3.x*2) ;
00209         dy = abs(P2.y*3 - P0.y - P3.y*2) ;
00210         if ( (dx>=dy ? 3*dx+dy : dx+3*dy) > Flatness )
00211             FlattenSplit(P0,P1,P2,P3) ;
00212         else
00213             DoLine(P3) ;
00214     }
00215 }
00216 
00217 
00218 void FlattenSplit( POINT P0, POINT P1, POINT P2, POINT P3 )
00219 {
00220     POINT L1, L2, M, R1, R2 ;
00221     L1.x = (P0.x + P1.x)/2;
00222     L1.y = (P0.y + P1.y)/2;
00223     L2.x = (P0.x + 2*P1.x + P2.x)/4;
00224     L2.y = (P0.y + 2*P1.y + P2.y)/4;
00225      M.x = (P0.x + 3*P1.x + 3*P2.x + P3.x)/8;
00226      M.y = (P0.y + 3*P1.y + 3*P2.y + P3.y)/8;
00227     R1.x = (P1.x + 2*P2.x + P3.x)/4;
00228     R1.y = (P1.y + 2*P2.y + P3.y)/4;
00229     R2.x = (P2.x + P3.x)/2;
00230     R2.y = (P2.y + P3.y)/2;
00231     FlattenCurve(P0, L1, L2, M) ;
00232     FlattenCurve(M, R1, R2, P3) ;
00233 }
00234 
00236 
00237 BOOL GWinding(
00238         PPOINT  pPoints,
00239         PBYTE   Types,
00240         INT32   Length,
00241         UINT32  pFlatness,
00242         UINT32  &pBottomLeftOffset,
00243         POINT   &pBottomLeft
00244     )
00245 {
00246     Flatness = pFlatness*27/2 ;
00247     StartPoint = Points = pPoints ;
00248     BottomLeft = PrevPoint = LastPoint = *Points++ ; Types++ ; --Length ;
00249     BottomLeftOffset = 0 ;
00250     Flags = 03 ;
00251     while ( Length>0 )
00252     {
00253         if ( (*Types & PT_MOVETO)==PT_LINETO )
00254         {
00255             DoLine( Points[0] ) ;
00256             Points++ ; Types++ ; --Length ;
00257         }
00258         else /* Curve */
00259         {
00260             FlattenCurve( Points[-1],Points[0],Points[1],Points[2] ) ;
00261             Points+=3 ; Types+=3 ; Length-=3 ;
00262         }
00263     }
00264     if ( BottomLeft.x!=LastPoint.x || BottomLeft.y!=LastPoint.y )
00265         PrevPoint = LastPoint ;
00266     if ( Flags & 01 )
00267         Prev_Point = PrevPoint ;
00268     else if ( Flags & 02 )
00269         Next_Point = *StartPoint ;
00270     pBottomLeftOffset = BottomLeftOffset ;
00271     pBottomLeft = BottomLeft ;
00272     INT32 Sgn = GWSgnMulSubMul( Next_Point.x-BottomLeft.x, Prev_Point.y-BottomLeft.y,
00273                              Prev_Point.x-BottomLeft.x, Next_Point.y-BottomLeft.y ) ;
00274     if ( Sgn )
00275         return Sgn<0 ;
00276     Sgn = Next_Point.x-Prev_Point.x ;
00277     if ( Sgn )
00278         return Sgn<0 ;
00279     Sgn = Prev_Point.y-Next_Point.y ;
00280     return Sgn<0 ;
00281 }
00282 

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