Main Page | Namespace List | Class Hierarchy | Class List | Directories | File List | Namespace Members | Class Members | File Members | Search for 

TraceRegion Class Reference

#include <tracergn.h>

Inheritance diagram for TraceRegion:

CCObject SimpleCCObject List of all members.

Public Member Functions

 TraceRegion ()
 Sets intial values up.
 ~TraceRegion ()
 Destructs object.
BOOL UseBitmap (KernelBitmap *pBitmap)
 Points the TraceRegion at a particular bitmap and claims the relevant size buffers.
BOOL UsePath (Path *pPath)
 Specifies we should use a particular path. The path is initialised, cleared etc.
BOOL Trace (INT32 InitialX, INT32 InitialY, BfxPixelOp *thepBfxPixelOp)
 Does a single boundary trace.
BOOL SetParams (double *pPixelError=NULL)
 Sets the tracing parameters.
BOOL GetParams (double *pPixelError=NULL)
 Sets the tracing parameters.

Static Public Member Functions

static void Test (UndoableOperation *Op)
 Internal test routine.

Protected Member Functions

BOOL TraceBoundary (DocCoord Origin, DocCoord Point1, DocCoord Point2)
 Does a single boundary trace.
BOOL FillBoundaryBuffer (BOOL *End)
 Fills up the boundary buffer.
BOOL ProcessBoundaryBuffer (BOOL Done=FALSE)
 Empties the boundary buffer.
BOOL FindInitialPoint (BOOL *End)
 Finds an initial point to start at.
void FitCubic (INT32 FirstPoint, INT32 LastPoint, TraceBoundaryPoint Tangent1, TraceBoundaryPoint Tangent2, BOOL IsStartCusp, BOOL IsEndCusp)
 This function is recursive. It tries to fit a cubic function to the coordinates in the path between FirstPoint and LastPoint. It then compares this function with the actual coordinates to determine how good a fit it has found. If the fit is good it is added to the path object. If the fit is bad then it is split at the point where the fit is at its worst and FitCubic is called again for the left and right halves. Scope: private.
void GenerateBezier (INT32 FirstPoint, INT32 LastPoint, TraceBoundaryPoint Tangent1, TraceBoundaryPoint Tangent2, TraceBoundaryPoint *Bezier)
 This function supplies the maths to try and fit a cubic function to a set of points. It spends its time trying to come up with good lengths for the two tangents passed in to maximise the closeness of the fit. If it fails to come up with realistic results it simply sets the tangent lengths to be 1/3 of the distance between the start point and the end point. Scope: private.
TraceBoundaryPoint BezierPoint (TraceBoundaryPoint *Bez, double u)
 This function simply evaluates the bezier function for a given position and is used to help when determining how good a fit we have obtained Scope: private.
BOOL CalcMaxError (INT32 LeftPoint, INT32 RightPoint, TraceBoundaryPoint *Bezier, INT32 *SplitPoint, double *MaxDist, INT32 Level)
 Finds out how good a fit the bezier curve we have created is when compared with the data points Scope: private.
void Parameterize (INT32 FirstPoint, INT32 LastPoint)
 This function determines the TPoints which will be fitted (i.e. the trace boundary points we use) and the TValues which will be assigned to them (i.e. the t values along the chord length to which the points correspond). Scope: private.
TraceBoundaryPoint LeftTangent (INT32 Start, INT32 Points)
 Finds the Left tangent at the given point in the path Scope: private.
TraceBoundaryPoint RightTangent (INT32 End, INT32 Points)
 Finds the Right tangent at the given point in the path Scope: private.
TraceBoundaryPoint CentreTangent (INT32 Centre, INT32 Points)
 Finds the tangent at the centre of the path Scope: private.
void InsertBezier (TraceBoundaryPoint *Bezier, BOOL IsStartCusp, BOOL IsEndCusp)
 Adds the bezier curve to the path. If it is that last curve in the fitting (ie Depth is 0) then the rotate flag will not be set Scope: private.
void InsertLine (const DocCoord &Start, const DocCoord &End, BOOL IsStartCusp, BOOL IsEndCusp)
 Inserts a straight curve into the path. It keeps it as a curve so that the path will continue to look smooth after it is edited. If this is the last Path element in the fit, (ie Depth is zero) then the rotate flag will not be set. Scope: private.
void InsertStraightLine (const DocCoord &End)
 Inserts a straight Line into the path. This is used in cases where the Line segment must be kept as a straight line (ie by using Straight Line Mode of the FreeHand tool) Scope: private.
double Bezier0 (double u)
double Bezier1 (double u)
double Bezier2 (double u)
double Bezier3 (double u)
BOOL IsCuspDirectionChange (INT32 dir1, INT32 dir2)

Protected Attributes

TraceBoundaryPoint * BoundaryBuffer
BfxPixelOp * pBfxPixelOp
KernelBitmap * Bitmap
INT32 xsize
INT32 ysize
TraceBoundaryPoint InitialPoint
TraceBoundaryPoint HeadPoint
INT32 InitialDirection
INT32 TailDirection
INT32 HeadDirection
TraceBoundaryPoint FirstBufferPoint
INT32 BoundaryTail
INT32 BoundaryHead
INT32 BoundaryRingMask
INT32 BoundaryRingSize
double Error
double PixelError
BOOL VirginBuffer
BOOL VirginPath
BOOL AtCusp
BOOL TailCusp
Path * ThePath
TraceBoundaryPoint Directions [(0x7)+1]
TraceBoundaryPoint DirectionPoint [(0x7)+1][(0x7)+1][4]
double TValues [10+1]
INT32 TPoints [10+1]
TraceBoundaryPoint Q1 [3]
TraceBoundaryPoint Q2 [2]
INT32 NumTPoints

Private Member Functions

 CC_DECLARE_DYNCREATE (TraceRegion)

Detailed Description

Definition at line 318 of file tracergn.h.

Constructor & Destructor Documentation

TraceRegion::TraceRegion (   ) 
 

Sets intial values up.

Author:
Alex_Bligh (Xara Group Ltd) <camelotdev@xara.com>
Date:
21/11/94
Parameters:
none [INPUTS]
(constructs object) [OUTPUTS]
Returns:
none

Errors: None Scope: Public

See also:
-

Definition at line 165 of file tracergn.cpp.

00166 {
00167     pBfxPixelOp = NULL;
00168     BoundaryBuffer = NULL;
00169     BoundaryRingSize = 0;
00170     BoundaryRingMask =0;
00171     Bitmap = NULL;
00172     xsize = 1;
00173     ysize = 1;
00174     VirginBuffer = TRUE;
00175     AtCusp = FALSE;
00176     TailCusp = FALSE;
00177     TailDirection = -1;
00178     ThePath = NULL;
00179 
00180     double TheError = 1.00;
00181     SetParams(&TheError);
00182 
00183 /*
00184     In each direction of travel we always leave with a particular corner of the pixel set. In some directinos
00185     of travel, we have to set 2 edges. Here goes:
00186 
00187      ->1-X
00188     |    |  This is how an east going trace is represented. The top edge is the one we need to fill in.
00189     |    |
00190      ----
00191 
00192      ->1- 
00193     |    V  This is how a SE going trace is represented. We have 2 edges to fill in this time.
00194     |    2
00195      ----
00196     
00197     When there is a change in direction, things become more complex. Let us assume that the current
00198     direction is east, then note (for the following new directions) how will fill be buffer in:
00199 
00200     Current direction East                                   Current direction south east:           
00201                                                                                                      
00202      ->1-X                                                    ->1-X                                 
00203     |    |  E                                                |    |  E                               
00204     |    |                                                   |    |                                  
00205      ----                                                     ----                                   
00206                                                                                                      
00207      ->1-                                                     ->1-                                   
00208     |    V  SE                                               |    V  SE                              
00209     |    2                                                   |    2                                  
00210      ----X                                                    ----X                                  
00211                                                                                                      
00212      ->1-C                                                    ->1-                                   
00213     |    V  S                                                |    V  S                               
00214     |    2                                                   |    2                                  
00215      ----X                                                    ----X                                  
00216                                                                                                      
00217      ->1-C                                                    ->1-                                   
00218     |    V  SW                                               |    V  SW                              
00219     |    2                                                   |    2                                  
00220     X-<3-                                                    X-<3-C                                  
00221                                                                                                      
00222      ->1-C                                                    ->1-                                   
00223     |    V  W                                                |    V  W                               
00224     |    2                                                   |    2                                  
00225     X-<3-(C)                                                 X-<3-C                                   
00226                                                                                                      
00227     X----                                                     ->1-                                   
00228     |    |  NW  (theoretically impossible - no edges)        4    V  NW                              
00229     |    |                                                   ^    2                                  
00230      ----                                                     -<3-C                                   
00231                                                                                                      
00232     C----                                                    X----                                   
00233     |    |  N   (no edges (correct place))                   |    |  N   (theoretically impossible)  
00234     |    |                                                   |    |                                  
00235      ----                                                     ----                                   
00236                                                                                                      
00237      ->1-                                                     ->1-X                                  
00238     |    |  NE                                               |    |  NE                              
00239     |    |                                                   |    |                                  
00240      ----                                                     ----                                   
00241 
00242 
00243  Note how strikingly similar these are! We use the RH column one as that's generic for both sides.
00244 
00245 */
00246     
00247 
00248 
00249 
00250     // Grrr... This should be static but lovely C++ wont let me compile it. Thanks a lot C++
00251     // Heh what's 128 bytes when you have a bitmap to trace
00252     Directions[0].Init( (1<<8), (0<<8));    // East
00253     Directions[1].Init( (1<<8),-(1<<8));    // South East
00254     Directions[2].Init( (0<<8),-(1<<8));    // South
00255     Directions[3].Init(-(1<<8),-(1<<8));    // South West
00256     Directions[4].Init(-(1<<8), (0<<8));    // West
00257     Directions[5].Init(-(1<<8), (1<<8));    // North West
00258     Directions[6].Init( (0<<8), (1<<8));    // North
00259     Directions[7].Init( (1<<8), (1<<8));    // North East
00260 
00261     // First sort out the non-diagonal table
00262     DirectionPoint[0][0][0].Init( (1<<7), (1<<7));              // East to East
00263     DirectionPoint[0][0][1].Init( -1, -1);                      // No point 2
00264     DirectionPoint[0][0][2].Init( -1, -1);                      // No point 3
00265     DirectionPoint[0][0][3].Init( -1, -1);                      // No point 4
00266 
00267     DirectionPoint[0][1][0].Init( (1<<7), (1<<7));              // East to SE
00268     DirectionPoint[0][1][1].Init( (1<<7),-(1<<7));              // point 2
00269     DirectionPoint[0][1][2].Init( -1, -1);                      // No point 3
00270     DirectionPoint[0][1][3].Init( -1, -1);                      // No point 4
00271     
00272     DirectionPoint[0][2][0].Init( (1<<7), (1<<7));              // East to S
00273     DirectionPoint[0][2][1].Init( -1, 2);                       // No point 2, go south
00274     DirectionPoint[0][2][2].Init( -1, -1);                      // No point 3
00275     DirectionPoint[0][2][3].Init( -1, -1);                      // No point 4
00276     
00277     DirectionPoint[0][3][0].Init( (1<<7), (1<<7));              // East to SW
00278     DirectionPoint[0][3][1].Init( -1, 3);                       // No point 2, go SW
00279     DirectionPoint[0][3][2].Init( -1, -1);                      // point 3
00280     DirectionPoint[0][3][3].Init( -1, -1);                      // No point 4
00281 
00282     DirectionPoint[0][4][0].Init( (1<<7), (1<<7));              // East to W
00283     DirectionPoint[0][4][1].Init( -1, 2);                       // No point 2, go S
00284     DirectionPoint[0][4][2].Init( -1, -1);                      // point 3
00285     DirectionPoint[0][4][3].Init( -1, -1);                      // No point 4
00286 
00287     DirectionPoint[0][5][0].Init( (1<<7), (1<<7));              // South East to NW
00288     DirectionPoint[0][5][1].Init( (1<<7),-(1<<7));              // point 2
00289     DirectionPoint[0][5][2].Init( -1, 5);                       // No point 3, go NW
00290     DirectionPoint[0][5][3].Init( -1, -1);                      // No point 4
00291 
00292     DirectionPoint[0][6][0].Init( -1, 6);                       // No point 1, go N
00293     DirectionPoint[0][6][1].Init( -1, -1);                      // No point 2
00294     DirectionPoint[0][6][2].Init( -1, -1);                      // No point 3
00295     DirectionPoint[0][6][3].Init( -1, -1);                      // No point 4
00296 
00297     DirectionPoint[0][7][0].Init( (1<<7), (1<<7));              // East to NE
00298     DirectionPoint[0][7][1].Init( -1, -1);                      // No point 2
00299     DirectionPoint[0][7][2].Init( -1, -1);                      // No point 3
00300     DirectionPoint[0][7][3].Init( -1, -1);                      // No point 4
00301 
00302 
00303 
00304     DirectionPoint[1][0][0].Init( (1<<7), (1<<7));              // South East to East
00305     DirectionPoint[1][0][1].Init( -1, -1);                      // No point 2
00306     DirectionPoint[1][0][2].Init( -1, -1);                      // No point 3
00307     DirectionPoint[1][0][3].Init( -1, -1);                      // No point 4
00308 
00309     DirectionPoint[1][1][0].Init( (1<<7), (1<<7));              // South East to SE
00310     DirectionPoint[1][1][1].Init( (1<<7),-(1<<7));              // point 2
00311     DirectionPoint[1][1][2].Init( -1, -1);                      // No point 3
00312     DirectionPoint[1][1][3].Init( -1, -1);                      // No point 4
00313     
00314     DirectionPoint[1][2][0].Init( (1<<7), (1<<7));              // South East to S
00315     DirectionPoint[1][2][1].Init( (1<<7),-(1<<7));              // point 2
00316     DirectionPoint[1][2][2].Init( -1, -1);                      // No point 3
00317     DirectionPoint[1][2][3].Init( -1, -1);                      // No point 4
00318                     
00319     DirectionPoint[1][3][0].Init( (1<<7), (1<<7));              // South East to SW
00320     DirectionPoint[1][3][1].Init( (1<<7), (0<<7));              // point 3
00321     DirectionPoint[1][3][2].Init( -1, 3);                       // No point 4, go SW
00322     DirectionPoint[1][3][3].Init( -1, -1);                      // No point 4
00323 
00324     DirectionPoint[1][4][0].Init( (1<<7), (1<<7));              // South East to W
00325     DirectionPoint[1][4][1].Init( (1<<7),-(1<<7));              // point 2
00326     DirectionPoint[1][4][2].Init( -1, 4);                       // No point 3, go W
00327     DirectionPoint[1][4][3].Init( -1, -1);                      // No point 4
00328     
00329     DirectionPoint[1][5][0].Init( (1<<7), (1<<7));              // South East to NW
00330     DirectionPoint[1][5][1].Init( (1<<7),-(1<<7));              // point 2
00331     DirectionPoint[1][5][2].Init( -1, 5);                       // No point 3, go NW
00332     DirectionPoint[1][5][3].Init( -1, -1);                      // No point 4
00333 
00334     DirectionPoint[1][6][0].Init( -1, 6);                       // No point 1, go N
00335     DirectionPoint[1][6][1].Init( -1, -1);                      // No point 2
00336     DirectionPoint[1][6][2].Init( -1, -1);                      // No point 3
00337     DirectionPoint[1][6][3].Init( -1, -1);                      // No point 4
00338                 
00339     DirectionPoint[1][7][0].Init( (0<<7), (1<<7));              // South East to NE
00340     DirectionPoint[1][7][1].Init( -1, 7);                       // No point 2, go NE
00341     DirectionPoint[1][7][2].Init( -1, -1);                      // No point 3
00342     DirectionPoint[1][7][3].Init( -1, -1);                      // No point 4
00343     
00344     INT32 i;
00345     INT32 j;
00346     INT32 k;
00347     for (i=2; i<=7; i+=1) for (j=0; j<=7; j++) for (k=0; k<=3; k++)
00348     {
00349         // Go from direction i to direction j, i even
00350         INT32 j2 = (j-(i & 0x6)) & TR_NUMDIRECTIONMASK;
00351         DirectionPoint[i][j][k]=DirectionPoint[i & 0x1][j2][k];
00352         
00353         if (DirectionPoint[i][j][k].x != -1)
00354         {
00355             DirectionPoint[i][j][k].RotateDirection(Directions[(i & 0x6)]);
00356         }
00357         else
00358         {
00359             if (DirectionPoint[i][j][k].y != -1)
00360                 DirectionPoint[i][j][k].y = (((INT32)(DirectionPoint[(i & 0x1)][j2][k].y) + (i & 0x6)) & TR_NUMDIRECTIONMASK);
00361         }
00362     }
00363     
00364     TraceBoundaryPoint Centre;
00365     Centre.Init((1<<7),(1<<7));
00366     for (i=0; i<=7; i+=1) for (j=0; j<=7; j++) for (k=0; k<=3; k++)
00367     {
00368         if (DirectionPoint[i][j][k].x != -1)
00369         {
00370             DirectionPoint[i][j][k].translate(Centre);
00371         }
00372     }
00373     
00374 }

TraceRegion::~TraceRegion (   ) 
 

Destructs object.

Author:
Alex_Bligh (Xara Group Ltd) <camelotdev@xara.com>
Date:
21/11/94
Parameters:
none [INPUTS]
(destructs object) [OUTPUTS]
Returns:
none

Errors: None Scope: Public

See also:
-
This frees the boundary buffer it is is present.

Definition at line 505 of file tracergn.cpp.

00506 {
00507     if (BoundaryBuffer) CCFree(BoundaryBuffer);
00508     // Clear some hanging pointers
00509     BoundaryBuffer = NULL;
00510     Bitmap = NULL;
00511     ThePath = NULL;
00512 }

Member Function Documentation

double TraceRegion::Bezier0 (  double  u  )  [inline, protected]
 

Definition at line 373 of file tracergn.h.

00373 { double t=1.0-u; return (t*t*t); }

double TraceRegion::Bezier1 (  double  u  )  [inline, protected]
 

Definition at line 374 of file tracergn.h.

00374 { double t=1.0-u; return (3*u*t*t); }

double TraceRegion::Bezier2 (  double  u  )  [inline, protected]
 

Definition at line 375 of file tracergn.h.

00375 { double t=1.0-u; return (3*u*u*t); }

double TraceRegion::Bezier3 (  double  u  )  [inline, protected]
 

Definition at line 376 of file tracergn.h.

00376 { return (u*u*u); }

TraceBoundaryPoint TraceRegion::BezierPoint (  TraceBoundaryPoint *  Bez,
double  u
)  [protected]
 

This function simply evaluates the bezier function for a given position and is used to help when determining how good a fit we have obtained Scope: private.

Author:
Rik_Heywood (Xara Group Ltd) <camelotdev@xara.com> & Alex
Date:
7/3/94
Parameters:
Bez - The control points of a bezier curve [INPUTS] u - the normalised distance along the bezier that we are interested in
Returns:
The coord of the point that is a distance u into the bezier. for example, if u = 0.5 then the coord of the point half way along the bezier will be returned
See also:
TraceRegion::CalcMaxError

Definition at line 1383 of file tracergn.cpp.

01384 {
01385     double OneMinus = 1.0-u;
01386     double uSquared = u*u;
01387     double OneMinusSquared = OneMinus*OneMinus;
01388 
01389     TraceBoundaryPoint Coord;
01390     Coord = Bez[0]*(OneMinusSquared*OneMinus);
01391     Coord = Coord + Bez[1]*(3.0*u*OneMinusSquared);
01392     Coord = Coord + Bez[2]*(3.0*uSquared*OneMinus);
01393     Coord = Coord + Bez[3]*(uSquared*u);
01394 
01395     return Coord;
01396 }

BOOL TraceRegion::CalcMaxError (  INT32  LeftPoint,
INT32  RightPoint,
TraceBoundaryPoint *  Bezier,
INT32 *  SplitPoint,
double *  MaxDist,
INT32  Level
)  [protected]
 

Finds out how good a fit the bezier curve we have created is when compared with the data points Scope: private.

Author:
Alex_Bligh (Xara Group Ltd) <camelotdev@xara.com>
Date:
12/12/94
Parameters:
LeftPoint,RightPoint - the index of the start and send of the section - note these are indexes [INPUTS] into the T Array Bezier - the control points of the bezier we have fitted to the points Level - a recursion level counter
SplitPoint - the point to split the curve at if the error is too great [OUTPUTS] MaxDist - The biggest distance
Returns:
TRUE if the bezier should be split
This is done by recursive splitting of the line (as the largest error terms are likely to be in the middle we are extremely likely to only do one split). However, in order to find the maximum error point we force 3 levels of recursion.

Cunningly we move the TValues about if we think they are salvageable.

Definition at line 1426 of file tracergn.cpp.

01428 {
01429     TraceBoundaryPoint Q_t, Q1_t, Q2_t; // t evaluated at Q, Q' & Q''
01430     INT32 MidPoint = (LeftPoint + RightPoint+1)/2;  // where we are going to evaluate it
01431     double Distance;
01432     
01433     if (!((MidPoint == LeftPoint) || (MidPoint==RightPoint)))
01434     {
01435     
01436         for (INT32 iterations=1; iterations<=3; iterations++)
01437         {       
01438             double t = TValues[MidPoint];
01439             TraceBoundaryPoint pt = BoundaryBuffer[TPoints[MidPoint]];
01440 
01441             // Calculate where the curve actually is and find the distance from where we want it
01442             Distance = (BezierPoint(Bezier, t) - pt).SquaredLength();
01443 
01444             if ((Distance > *MaxDist) && (Distance < Error * 2.0))
01445             // If this is would be the new winner, and it's salvageable (less than twice as far away as we
01446             // we want), recalculate a better TValue
01447             {
01448 
01449                 // Evaluate Q, Q' & Q''
01450                 double OneMinus = 1.0-t;
01451                 double tSquared = t*t;
01452                 double OneMinusSquared = OneMinus*OneMinus;
01453 
01454                 Q_t = Bezier[0] *(OneMinusSquared*OneMinus) + Bezier[1]*(3.0*t*OneMinusSquared)
01455                      +Bezier[2] *(3.0*tSquared*OneMinus) + Bezier[3]*(tSquared*t);
01456                 Q1_t = Q1[0]*(OneMinusSquared) + Q1[1]*(2.0*t*OneMinus) + Q1[2]*(tSquared);
01457                 Q2_t = Q2[0]*(OneMinus) + Q2[1]*(t);
01458 
01459                 // Now Newton Raphson tprime = t - f(t)/f'(t)
01460                 TraceBoundaryPoint QtMinuspt = Q_t - pt;
01461 
01462 //  changed by Ed Cornes 31/10/95 in an attempt to remove an itermittent floating point exception in the tracer
01463 //              t = t - (  (QtMinuspt.x)*(Q1_t.x) + (QtMinuspt.y) * (Q1_t.y) ) /
01464 //                      (  Q1_t.SquaredLength() + ((QtMinuspt.x) * (Q2_t.x) + (QtMinuspt.y) * (Q2_t.y)) );
01465                 double denom = Q1_t.SquaredLength() + ((QtMinuspt.x) * (Q2_t.x) + (QtMinuspt.y) * (Q2_t.y));
01466                 if (fabs(denom)<1e-50)
01467                     denom = (denom<0) ? -1e-50 : 1e-50;
01468 
01469                 t = t - (  (QtMinuspt.x)*(Q1_t.x) + (QtMinuspt.y) * (Q1_t.y) ) / denom;
01470                 if (t<0) t=0;
01471                 if (t>1) t=1;
01472                 //TRACEUSER( "Alex", _T("Point %f moves to %f\n"),TValues[MidPoint],t);
01473                 TValues[MidPoint] = t;
01474             }
01475             else break; // Leave 'for' loop - point OK or point not salvageable
01476         }
01477 
01478         if ( Distance >= *MaxDist)
01479         {
01480             *MaxDist = Distance;
01481             *SplitPoint = MidPoint;
01482         }
01483 
01484         // If we haven't got a point to split at yet, or if we're in the 4 first points,
01485         // recurse down. This ensures we do 8 points.
01486         if ((*MaxDist<=Error) || (Level<3)) CalcMaxError(LeftPoint, MidPoint,
01487                                                          Bezier, SplitPoint, MaxDist, Level+1); 
01488         if ((*MaxDist<=Error) || (Level<3)) CalcMaxError(MidPoint, RightPoint,
01489                                                          Bezier, SplitPoint, MaxDist, Level+1); 
01490         
01491     }   
01492     return(*MaxDist>Error);
01493 }

TraceRegion::CC_DECLARE_DYNCREATE (  TraceRegion   )  [private]
 

TraceBoundaryPoint TraceRegion::CentreTangent (  INT32  Centre,
INT32  Points
)  [protected]
 

Finds the tangent at the centre of the path Scope: private.

Author:
Rik_Heywood (Xara Group Ltd) <camelotdev@xara.com> & Alex
Date:
7/3/94
Parameters:
Centre - the index of the split point in the path [INPUTS] Points - the max number of points that can be scanned
Returns:
The tangent at the point Centre

Definition at line 1595 of file tracergn.cpp.

01596 {
01597     TraceBoundaryPoint Left, Right;
01598     TraceBoundaryPoint Tangent(0,0);
01599 
01600     Points = 1+MIN (Points/2,MAXTANGENTPOINTS);
01601     if (Points<2) Points=2;
01602 
01603     // Make sure that is not of zero length
01604     while ((Tangent.x==0) && (Tangent.y==0))
01605     {
01606         if ((--Points)>0)
01607         {
01608             // Calc right tangent
01609             Left.x = BoundaryBuffer[Centre-Points].x - BoundaryBuffer[Centre].x;
01610             Left.y = BoundaryBuffer[Centre-Points].y - BoundaryBuffer[Centre].y;
01611 
01612             // Calc left tangent
01613             Right.x = BoundaryBuffer[Centre].x - BoundaryBuffer[Centre+Points].x;
01614             Right.y = BoundaryBuffer[Centre].y - BoundaryBuffer[Centre+Points].y;
01615 
01616             // Average to get the centre tangent
01617             Tangent.x = (Left.x + Right.x) / 2;
01618             Tangent.y = (Left.y + Right.y) / 2;
01619 
01620         }
01621         else
01622         {
01623             ERROR3("Tangent was a zero length vector in the curve fitter (Centre)");
01624             Tangent.x = -1;
01625         }
01626     }
01627 
01628     return Tangent;
01629 }

BOOL TraceRegion::FillBoundaryBuffer (  BOOL *  End  )  [protected]
 

Fills up the boundary buffer.

Author:
Alex_Bligh (Xara Group Ltd) <camelotdev@xara.com>
Date:
21/11/94
Parameters:
End ptr to BOOL to return in [INPUTS]
End set TRUE if last point else set FALSE [OUTPUTS]
Returns:
TRUE if worked, FALSE & error set if failed

Errors: Error2 & Error3 (various) Scope: Protected

See also:
TraceRegion::ProcessBoundaryBuffer
This routine fills the boundary buffer up with some more points. It stops if the buffer becomes nearly full.

It also stops if it meets a cusp, or the intial point in the initial direction.

Definition at line 824 of file tracergn.cpp.

00825 {
00826     INT32 NewDirection;
00827     INT32 Turns;
00828 
00829     ERROR2IF((!Bitmap),FALSE,"TraceRegion incorrectly initialised");
00830 
00831     *End=FALSE; 
00832     while (BoundaryHead<BoundaryRingSize - 6)   // there is enough room in buffer
00833     {
00834         // Calculate the new direction. We start looking at direction-2 but as we add one before we start
00835         // we have -3. If we're at a cusp we know the NewDirection set to HeadDirection is the correct place,
00836         // i.e. we want +0, but because we add one before we start, we want -1.
00837         NewDirection = (HeadDirection-(AtCusp?1:3)) & TR_NUMDIRECTIONMASK;
00838         //NewDirection = (HeadDirection-3) & TR_NUMDIRECTIONMASK;
00839         Turns=0;
00840         TraceBoundaryPoint NewPoint=HeadPoint; // Initialisation unnecessary but quiets the compiler
00841         
00842         
00843         do
00844         {
00845             // This should only return(TRUE) if asked to trace a
00846             // one pixel shape - else we must have got to this pixel some how.
00847             if ((Turns++)==8)
00848             {
00849                 *End=TRUE;
00850                 // We want to force it to be the 4 corner case
00851                 NewDirection=((HeadDirection & 0x6) + 6) & TR_NUMDIRECTIONMASK;
00852                 ERROR3("One pixel regions NYI");
00853                 // The above won't work properly because it's not properly entered. I think we need a horrible
00854                 // goto here.
00855                 break;
00856             }
00857             // Find next direction
00858             NewDirection = (NewDirection + 1) & TR_NUMDIRECTIONMASK;            
00859             NewPoint = HeadPoint;       // Calculate the new point
00860             NewPoint.translate(Directions[NewDirection]);
00861         } while (!pBfxPixelOp->IsInRegion(((INT32)(NewPoint.x))>>8, ((INT32)(NewPoint.y))>>8)); 
00862 
00863         if (VirginBuffer) InitialDirection = TailDirection = NewDirection;
00864 
00865 
00866         // stick point in ring buffer
00867         // Limit is such that we know we can fit the maximum of 4 points in
00868         INT32 HintPoint=0;
00869         if (!VirginBuffer)
00870         {
00871             if (AtCusp)
00872             {
00873                 // Only put the last point in if at a cusp
00874                 while ((DirectionPoint[HeadDirection][NewDirection][HintPoint].x != -1) // sufficient check
00875                       && (HintPoint<4)) {HintPoint++;}  // Don't inc at final point
00876                 BoundaryBuffer[BoundaryHead] = HeadPoint;
00877                 BoundaryBuffer[BoundaryHead++].translate(DirectionPoint[HeadDirection][NewDirection][HintPoint-1]);
00878                 // HintPoint still points at terminator
00879             }
00880             else
00881             {
00882                 // Put all points in
00883                 while ((DirectionPoint[HeadDirection][NewDirection][HintPoint].x != -1) // sufficient check
00884                       && (HintPoint<4))
00885                 {
00886                     BoundaryBuffer[BoundaryHead] = HeadPoint;
00887                     BoundaryBuffer[BoundaryHead++].translate(DirectionPoint[HeadDirection][NewDirection][HintPoint++]);
00888                 }
00889             }
00890         } else while ((DirectionPoint[HeadDirection][NewDirection][HintPoint].x != -1) // sufficient check
00891                       && (HintPoint<4)) {HintPoint++;}  // Don't inc at final point
00892 
00893 
00894         if (DirectionPoint[HeadDirection][NewDirection][HintPoint].y !=-1)
00895         {
00896             HeadDirection = (INT32)(DirectionPoint[HeadDirection][NewDirection][HintPoint].y);
00897 //          HeadPoint = NewPoint;
00898             AtCusp = TRUE;
00899             if (TailDirection == -1) TailDirection = HeadDirection;
00900 //          VirginBuffer = FALSE;
00901             return (TRUE);
00902         }
00903 
00904         // check for cusp a with dirty unsigned arithmetic and return NOW if we are there.
00905         // AtCusp =  ( ( ((unsigned)(Turns-2)) >=3) && (!AtCusp));
00906         AtCusp = FALSE;
00907 
00908         //if (AtCusp) return (TRUE); // cusp return 
00909     
00910 
00911         if ( (HeadPoint == InitialPoint) && (NewDirection == InitialDirection) && !VirginBuffer )
00912         {
00913             *End = TRUE;
00914             VirginBuffer = FALSE;
00915             return (TRUE);
00916         }
00917 
00918         VirginBuffer = FALSE;
00919  
00920         if (TailDirection == -1) TailDirection = NewDirection;
00921 
00922         // Set up member vars
00923         HeadPoint = NewPoint;
00924         HeadDirection = NewDirection;
00925 
00926     }
00927 
00928     return(TRUE); // Out of buffer space, go process some & come back
00929 }

BOOL TraceRegion::FindInitialPoint (  BOOL *  End  )  [protected]
 

Finds an initial point to start at.

Author:
Alex_Bligh (Xara Group Ltd) <camelotdev@xara.com>
Date:
21/11/94
Parameters:
None [INPUTS]
End set if no points [OUTPUTS]
Returns:
TRUE if succeeded else FALSE and error set

Errors: Various Scope: Protected

See also:
-
This routine is currently a horrible bodge creature.

The boundary buffer is cleared. An initial point will be found if possible and End cleared. If one is not found, End will be set.

Definition at line 650 of file tracergn.cpp.

00651 {
00652     INT32 x;
00653     INT32 y;
00654 
00655     ERROR2IF((!Bitmap),FALSE,"How about giving us a bitmap first then?");
00656 
00657     InitialDirection = 0; // East
00658     VirginBuffer = TRUE;
00659     BoundaryHead =0;
00660     BoundaryTail =0;
00661     TailDirection = -1;
00662     HeadDirection = 0;
00663     AtCusp=FALSE;
00664     TailCusp = FALSE;
00665     *End = FALSE;
00666 
00667     for (y = ysize-1; y>=0; y--) for (x = 0; x < xsize; x++) if (pBfxPixelOp->IsInRegion(x,y))
00668     {
00669         InitialPoint.x = x<<8;
00670         InitialPoint.y = y<<8;
00671         HeadPoint = InitialPoint;
00672         return (TRUE);
00673     }
00674 
00675     *End = TRUE;    // Oh dear, no initial point
00676         
00677     return(TRUE);
00678 }

void TraceRegion::FitCubic (  INT32  FirstPoint,
INT32  LastPoint,
TraceBoundaryPoint  Tangent1,
TraceBoundaryPoint  Tangent2,
BOOL  IsStartCusp,
BOOL  IsEndCusp
)  [protected]
 

This function is recursive. It tries to fit a cubic function to the coordinates in the path between FirstPoint and LastPoint. It then compares this function with the actual coordinates to determine how good a fit it has found. If the fit is good it is added to the path object. If the fit is bad then it is split at the point where the fit is at its worst and FitCubic is called again for the left and right halves. Scope: private.

Author:
Rik_Heywood (Xara Group Ltd) <camelotdev@xara.com> & Alex
Date:
7/3/94
Parameters:
FirstPoint - the index of the coordinate in the path to start fitting from [INPUTS] LastPoint - the index of the coordinate in the path to stop fitting at Tangent1 - The tangent of the curve at the first point Tangent2 - the tangent of the curve at the last point IsStartCusp - TRUE if FirstPoint is next to a cusp IsEndCusp - TRUE of EndPoint is next to a cusp
See also:
TraceRegion::GenerateBezier; TraceRegion::CalcMaxError

Definition at line 1029 of file tracergn.cpp.

01031 {
01032     // Will need space for a Bezier curve
01033     TraceBoundaryPoint Bezier[4];
01034     TraceBoundaryPoint CentTangent;
01035     INT32 NumPoints = LastPoint - FirstPoint + 1;
01036     INT32 SplitPoint, Split;
01037 
01038 
01039     // If we have the flexibility, recalculate the tangents to the left and right
01040     if (IsStartCusp) Tangent1 = LeftTangent(FirstPoint, NumPoints);
01041     if (IsEndCusp) Tangent2 = RightTangent(LastPoint, NumPoints);
01042 
01043 // The following is actually legal if we start on a cusp
01044 //  ERROR3IF(NumPoints<2,"Too few points to fit a cubic");
01045     if (NumPoints<2) return;
01046 #if 0
01047     // if this segment only has 2 points in it then do the special case
01048     if ( NumPoints == 2 )
01049     {
01050         InsertLine( DocCoord((INT32)(BoundaryBuffer[FirstPoint].x), (INT32)(BoundaryBuffer[FirstPoint].y)),
01051                     DocCoord((INT32)(BoundaryBuffer[LastPoint].x), (INT32)(BoundaryBuffer[FirstPoint].y)),
01052                     IsStartCusp, IsEndCusp);
01053         return;
01054     }
01055 #endif
01056     /* Due to a bug in the algorithm we also have to consider 3 points a special case.
01057 
01058     Here's what Mathematica reckons is the formula for a bezier A B C D that passes through a point Q
01059     with tangents tx & ty
01060 
01061                   4 t1x (Ay t2x + Dy t2x - 2 Qy t2x - Ax t2y - Dx t2y + 2 Qx t2y)
01062      {{Bx -> Ax - ---------------------------------------------------------------, 
01063                                        3 (t1y t2x - t1x t2y)
01064                   4 t1y (Ay t2x + Dy t2x - 2 Qy t2x - Ax t2y - Dx t2y + 2 Qx t2y)
01065        By -> Ay - ---------------------------------------------------------------, 
01066                                        3 (t1y t2x - t1x t2y)
01067                   (12 (Ay + Dy - 2 Qy) t1x - 12 (Ax + Dx - 2 Qx) t1y) t2x
01068        Cx -> Dx - -------------------------------------------------------, 
01069                                  9 (-(t1y t2x) + t1x t2y)
01070                   4 (Ay t1x + Dy t1x - 2 Qy t1x - Ax t1y - Dx t1y + 2 Qx t1y) t2y
01071        Cy -> Dy + ---------------------------------------------------------------, 
01072                                        3 (t1y t2x - t1x t2y)
01073 
01074     I reckon I can rewrite this better:
01075 
01076 
01077        F  -> (4/3) (A + D - 2 Q) / (t2x t1y - t2y t1x)
01078 
01079        B  -> Fy t2x - Fx t2y
01080          
01081        C  -> Fx t1y - Fy t1x
01082               
01083        Bx -> Ax - B t1x
01084    
01085        By -> Ay - B t1y
01086 
01087        Cx -> Dx - C t2x
01088               
01089        Cy -> Dy - C t2y
01090 
01091     This is all very well and good, but when does it occur? Here's an example:
01092 
01093 
01094     A     B
01095      ....
01096          ....
01097              ...T1
01098 
01099     T2....C
01100 
01101   
01102     Here A is is the FistPoint with tangent T1, and C is the last point with tangent T2. The only bezier that
01103     fits through B as well with tangents specified is a loop that goes left from C, back under it and up through T1.
01104     Though all the maths is fine, and we can even detect this case, it's just not worth it. We just miss out point B.
01105 
01106     Oh well, so much for the beaury of mathematics. (PS - the real soln is to introduce 1 or more extra points. But that's
01107     getting silly).
01108 
01109     */
01110     
01111     #if 0
01112     // Never appears to run to completion anyway :-(
01113     if (NumPoints == 3)
01114     {
01115         INT32 MidPoint = FirstPoint+1;
01116         double Bottom = 0.75 * (Tangent2.x * Tangent1.y - Tangent2.y * Tangent1.x);
01117         if (Abs(Bottom)>0.001) // Else ignore middle point - this happens if the tangents are nearly parallel
01118         {
01119             TraceBoundaryPoint F = (BoundaryBuffer[FirstPoint]+BoundaryBuffer[LastPoint]-BoundaryBuffer[MidPoint]*2.0)/Bottom;
01120             double B = F.y * Tangent2.x - F.x * Tangent2.y;
01121             double C = F.x * Tangent1.y - F.y * Tangent1.x;
01122             if ((B<0.0) && (C<0.0)) // Not generating a loop
01123             {
01124                 Tangent1 = -(Tangent1 * B);
01125                 Tangent2 = -(Tangent2 * C); // Don't worry - we just need their directions for the fallback case
01126                 // Max distance is ((1<<8)/2)^2 = (1<<14)
01127                 if ((Tangent1.SquaredLength()<(1<<14)) && (Tangent2.SquaredLength()<(1<<14)))
01128                 {
01129                     Bezier[0] = BoundaryBuffer[FirstPoint];
01130                     Bezier[3] = BoundaryBuffer[LastPoint];
01131                     Bezier[1] = BoundaryBuffer[FirstPoint] + Tangent1;
01132                     Bezier[2] = BoundaryBuffer[LastPoint] + Tangent2;
01133                     InsertBezier(Bezier, IsStartCusp, IsEndCusp);
01134                     return;
01135                 }
01136             }
01137         }   
01138     }
01139     #endif
01140 
01141     // We must consider 2 points (or unhandled 3 point cases) as a special case
01142     if ( NumPoints <=2)
01143     {
01144         // With 3 points the distance is always 2.
01145         INT32 Distance = (1<<8)*2/3;
01146         
01147         // store the end points
01148         Bezier[0] = BoundaryBuffer[FirstPoint];
01149         Bezier[3] = BoundaryBuffer[LastPoint];
01150         
01151         // calc the control points
01152         Bezier[1] = Bezier[0] + Tangent1.SetLength(Distance);
01153         Bezier[2] = Bezier[3] + Tangent2.SetLength(Distance);
01154 
01155         // add it to the path
01156         InsertBezier(Bezier, IsStartCusp, IsEndCusp);
01157         return;
01158     }
01159 
01160     
01161     if (NumPoints ==3)
01162     {
01163         Split = FirstPoint + 1; // Midpoint 
01164     }
01165     else
01166     {
01167         // Create a Bezier curve from the segemnt and see if it is a good fit
01168         Parameterize(FirstPoint, LastPoint);
01169 
01170         GenerateBezier(FirstPoint, LastPoint, Tangent1, Tangent2, Bezier);
01171     
01172         SplitPoint=NumTPoints-1;
01173         double MaxError = 0;    
01174         if (!CalcMaxError(0, NumTPoints, Bezier, &SplitPoint, &MaxError, 0))
01175         {
01176             // The mapping was good, so output the curve segment
01177             //TRACEUSER( "Alex", _T("  OK FP=%d, LP=%d, ME=%f\n"),FirstPoint,LastPoint,MaxError);
01178             InsertBezier(Bezier, IsStartCusp, IsEndCusp);
01179             return;
01180         }
01181 
01182         Split = TPoints[SplitPoint];
01183     }   
01184     
01185     //TRACEUSER( "Alex", _T("Split FP=%d, SP=%d, LP=%d\n"),FirstPoint,Split,LastPoint);
01186     // fitting failed -- split at max error point and fit recursively
01187     CentTangent = CentreTangent(Split, MIN(Split-FirstPoint+1,LastPoint-Split+1));
01188     //Tangent1=LeftTangent(FirstPoint,SplitPoint-FirstPoint+1);
01189     FitCubic(FirstPoint, Split, Tangent1, CentTangent, IsStartCusp, FALSE);
01190 
01191     CentTangent = -CentTangent;
01192     //Tangent2=RightTangent(LastPoint,LastPoint-SplitPoint+1);
01193     FitCubic(Split, LastPoint, CentTangent, Tangent2, FALSE, IsEndCusp);
01194     
01195 }

void TraceRegion::GenerateBezier (  INT32  FirstPoint,
INT32  LastPoint,
TraceBoundaryPoint  Tangent1,
TraceBoundaryPoint  Tangent2,
TraceBoundaryPoint *  Bezier
)  [protected]
 

This function supplies the maths to try and fit a cubic function to a set of points. It spends its time trying to come up with good lengths for the two tangents passed in to maximise the closeness of the fit. If it fails to come up with realistic results it simply sets the tangent lengths to be 1/3 of the distance between the start point and the end point. Scope: private.

Author:
Rik_Heywood (Xara Group Ltd) <camelotdev@xara.com> & Alex
Date:
7/3/94
Parameters:
FirstPoint - the index of the coordinate in the path to start fitting from [INPUTS] LastPoint - the index of the coordinate in the path to stop fitting at Tangent1