Camelot: TrapEdgeList Class Reference

00137 {
00138     ERROR3IF(pParent == NULL, "Illegal NULL param");
00139 
00140     Used            = 0;
00141     CurrentSize     = 0;
00142     pEdges          = NULL;
00143     PathLength      = 1.0;
00144     pParentList     = pParent;
00145 }

00161 {
00162     if (pEdges != NULL)
00163         CCFree(pEdges);
00164 }

00275 {
00276     // --- Make sure we have room to add the new point to our array
00277     DocCoord Temp;                  // Temporary safe storage for the point
00278     if (Used >= CurrentSize)
00279     {
00280         // I pass in a pointer to the coord for efficiency, to save copying points until
00281         // absolutely necessary. This is safe under normal circumstances, except when
00282         // we realloc the array and the input pointer points INTO that array! Most of
00283         // the time, it works fine, but every now and then NT maps out the memory page
00284         // and we get a nasty access violation! Rather than copying the Coord every
00285         // time, I prefer therefore to copy it into a temporary point on those few
00286         // occasions where we actually have to realloc the array.
00287         Temp = *pPoint;             // Copy the point into safe, temporary storage
00288         pPoint = &Temp;             // And point the input value pointer at the safe copy
00289 
00290         if (!ExpandArray())         // Try to allocate more
00291             return FALSE;                   // And return if we failed
00292     }
00293 
00294     // --- Find the new entry and allocate it
00295     TrapEdge *pEdge = &pEdges[Used];
00296 
00297     // --- Record the point & join type
00298     pEdge->Centre = *pPoint;
00299     pEdge->PrevTrapJoin = JoinType;
00300 
00301     // --- Calculate position, and check for repeating strokes
00302     if (Used > 0)
00303     {
00304         TrapEdge *pPrevEdge = &pEdges[Used-1];
00305         const double dx = (double) (pPrevEdge->Centre.x - pPoint->x);
00306         const double dy = (double) (pPrevEdge->Centre.y - pPoint->y);
00307         double Travel = sqrt(dx*dx + dy*dy);
00308         if (Travel < 1.0)       // Make sure all positions increment slightly to keep everyone happy
00309             Travel = 1.0;
00310         pEdge->Position = pPrevEdge->Position + Travel;
00311 
00312         // Now check for (and handle) repeating strokes
00313         const INT32 RepeatLength = (pParentList == NULL) ? 0 : pParentList->GetRepeatLength();
00314         if (RepeatLength > 0 && JoinType == TrapJoin_None)
00315         {
00316             // If it's a repeating stroke, and we're not in the middle of a join, then
00317             // we compare the current path travel to the repeat distance to see if we've gone
00318             // past the end of this repeat. If we have, then we calculate the point where the
00319             // (first) repeat in this trapezoid should happen, and break this trapezoid there,
00320             // ending the current TrapEdgeList, and starting a new TrapEdgeList.
00321             // Note: We recursively call AddEdge on each new TrapEdgeList so that if the
00322             // trapezoid contains many repeats, we will subdivide it further.
00323 
00324             if (pEdge->Position >= (double)RepeatLength)
00325             {
00326                 // We've gone too far. Time to subdivide.
00327                 ERROR3IF(pEdge->Position - pPrevEdge->Position <= 0.0, "Position calculation is screwed up!");
00328 
00329                 const double Split = (((double)RepeatLength) - pPrevEdge->Position) / (pEdge->Position - pPrevEdge->Position);
00330 
00331                 // Calculate the split point & position value into our last Edge
00332                 pEdge->Centre.x = (INT32) (((1.0 - Split) * (double)pPrevEdge->Centre.x) + (Split * (double)pPoint->x));
00333                 pEdge->Centre.y = (INT32) (((1.0 - Split) * (double)pPrevEdge->Centre.y) + (Split * (double)pPoint->y));
00334                 pEdge->Position = (double) RepeatLength;
00335 
00336                 // And create a new TrapEdgelist, and initialise it to go from the split point to the
00337                 // edge which we were orignally passed - NOTE that this may RECURSE.
00338                 TrapEdgeList *pNewEdgeList = pParentList->AddEdgeList();
00339                 if (pNewEdgeList != NULL)
00340                 {
00341                     pNewEdgeList->AddEdge(&pEdge->Centre, TrapJoin_None);   // Add intersection point
00342                     pNewEdgeList->AddEdge(pPoint, TrapJoin_None);           // then add the original end Edge
00343                 }
00344             }
00345         }
00346     }
00347     else
00348         pEdge->Position = 0.0;
00349 
00350     // Finally, increment Used to move on to the next TrapEdge entry in our array
00351     Used++;
00352 
00353     return TRUE;
00354 }

00381 {
00382     // Work out how many entries to allocate. Note that I use a fairly large number
00383     // so that we don't have to reallocate the array very often. Each structure is
00384     // small, so the memory usage is fairly low, although it must be noted that
00385     // a dashed line could potentially generate quite a pile of these lists!
00386     INT32 AllocSize = CurrentSize + 512;
00387     if (pParentList != NULL && pParentList->GetRepeatLength() > 0)
00388     {
00389         // If it's a repeating stroke, then we must be far more careful about memory usage!
00390         // (i.e. if there are 1000 repeats along a stroke, each taking 15kB, we'll eat 15MB!)
00391         // We assume that repeats are small and hence will not need very many entries, and
00392         // then if (and only if) we find we have to realloc to make the array bigger, we jump
00393         // in bigger steps.
00394         if (CurrentSize == 0)
00395             AllocSize = CurrentSize + 4;
00396         else
00397             AllocSize = CurrentSize + 16;
00398     }
00399 
00400     if (pEdges == NULL)
00401     {
00402         // We have no array yet, so allocate one
00403         pEdges = (TrapEdge *) CCMalloc(AllocSize * sizeof(TrapEdge));
00404         if (pEdges == NULL)
00405             return(FALSE);
00406     }
00407     else
00408     {
00409         // We have an array - we must make it larger
00410         TrapEdge *pNewBuf = (TrapEdge *) CCRealloc(pEdges, AllocSize * sizeof(TrapEdge));
00411         if (pNewBuf == NULL)
00412             return(FALSE);
00413 
00414         pEdges = pNewBuf;
00415     }
00416 
00417     // Success. Update the current size value
00418     CurrentSize = AllocSize;
00419     return(TRUE);
00420 }

00196 {
00197     if (Used < 2)
00198         return(0);
00199 
00200     // Special cases - if the point is outside the array bounds, then return the end immediately.
00201     // These boost speed greatly when clipping part of a vector stroke off the end, etc
00202     if (Position <= pEdges[0].Position)
00203         return(0);
00204 
00205     if (Position >= pEdges[Used-1].Position)
00206         return(Used-1);
00207 
00208     // Make sure HiIndex is greater than LoIndex - if not, set it to the last array entry
00209     if (HiIndex < LoIndex)
00210         HiIndex = Used-1;
00211 
00212     ERROR3IF(LoIndex >= Used || HiIndex >= Used || LoIndex > HiIndex, "Illegal start index(es)");
00213 
00214     // --- Check if the position is out of the original search bounds, or if it
00215     // is silly, and expand the bounds as necessary to make sure we will search all
00216     // relevant TrapEdges
00217     if (LoIndex >= HiIndex || LoIndex >= Used || Position <= pEdges[LoIndex].Position)
00218         LoIndex = 0;
00219 
00220     if (HiIndex <= LoIndex || HiIndex >= Used || Position >= pEdges[HiIndex].Position)
00221         HiIndex = Used-1;
00222 
00223     // --- Search the TrapEdges. This is done using a binary chop - we find the
00224     // midpoint between LoIndex & HiIndex, and move either Lo or Hi to that point,
00225     // so that the range reduces toward a single edge. This is far more efficient
00226     // than a linear search, especially on the large lists we typically deal with.
00227     while (HiIndex > LoIndex+1)
00228     {
00229         const UINT32 MidIndex = (LoIndex + HiIndex) / 2;
00230         if (pEdges[MidIndex].Position > Position)
00231             HiIndex = MidIndex;
00232         else
00233             LoIndex = MidIndex;
00234     }
00235 
00236     ERROR3IF(pEdges[LoIndex].Position > Position || pEdges[HiIndex].Position < Position,
00237                 "I think the binary chop has screwed up");
00238 
00239     return(LoIndex);
00240 }

00321 { return((Used == 0) ? NULL : &pEdges[Used-1]); };

00315 { return(Used); };

00336 { return PathLength; };

00318 { ERROR3IF(index >= Used, "Out of range"); return(&pEdges[index]); };

00448 {
00449     if (Used < 2)                           // Sanity check
00450     {
00451         ERROR3("Not enough coordinates in trapezoid list!");
00452         return(FALSE);
00453     }
00454 
00455     TrapEdge *pPrevEdge = NULL;
00456     TrapEdge *pEdge     = NULL;
00457     NormCoord PrevNormal(1.0, 0.0);
00458     BOOL CompletingAMitre = FALSE;
00459 
00460     // --- First, scan the trapezoid list, and calculate the normal of each edge
00461     for (UINT32 Index = 0; Index < Used; Index++)
00462     {
00463         // Start by finding a pointer to the edge record and previous record (if any)
00464         pPrevEdge = pEdge;
00465         pEdge = &(pEdges[Index]);
00466 
00467         // Calculate the path normal for this trapezoid edge.
00468         if (pPrevEdge == NULL)
00469         {
00470             // It's the very first point. The normal is just the normal to the first segment
00471             TrapEdge *pNextEdge = &(pEdges[Index+1]);
00472             pEdge->Normal.SetNormalToLine(pEdge->Centre, pNextEdge->Centre);
00473 
00474             PrevNormal = pEdge->Normal;     // Remember this edge's normal for the next pass
00475         }
00476         else if (pEdge->Centre == pPrevEdge->Centre)
00477         {
00478             // Two points are coincident. That means a joint (or a degenerate source path element).
00479             //
00480             // The following cases can apply:
00481             //  if (the next point is ALSO coincident)
00482             //      * We have a mitred join. The normal is the average of the previous and next normals
00483             //        with some jiggery-pokery to make the normal also have a length which will get the
00484             //        outline out to the mitre intersection point (rather than being normalised)
00485             //  else
00486             //      * We have the last 2 points of the 3-point mitred join, or
00487             //      * We have a simple bevelled or rounded join
00488             //          (both of which are treated in the same manner)
00489 
00490             // Find the "next" edge. Care must be taken for the last join to make sure
00491             // that the first edge is treated as "next". Note that we don't use point 0
00492             // in this case, as that is coincident! We use point 1 which is the point
00493             // at the end of that first line.
00494             TrapEdge *pNextEdge = &pEdges[1];
00495             if (Index < Used-1)
00496                 pNextEdge = &pEdges[Index+1];
00497 
00498             if (pNextEdge->Centre == pEdge->Centre)
00499             {
00500                 // We have found 3 coincident points, so we've hit a mitred join.
00501                 // The middle Edge of the mitred join has a normal which is in the direction
00502                 // of the average of the preceeding/next edge normals (i.e. points towards the
00503                 // mitre intersection), but it has a non-unit-length, so as to stretch the
00504                 // outline out to the mitre point.
00505 
00506                 // In this case, we don't bother to do anything yet, as we'll calculate
00507                 // the next normal on the next pass, so we just flag the case and let
00508                 // the next pass come back and fix up our normal once it has all the facts.
00509                 CompletingAMitre = TRUE;
00510 
00511                 // NOTE that we leave PrevNormal containing the previous normal - we'll need it
00512                 // on the next pass.
00513             }
00514             else
00515             {
00516                 // The completing trap of any join simply uses the normal of the "next" edge,
00517                 // so we simply calculate this for all cases.
00518                 if (Index >= Used-1)
00519                 {
00520                     // At the end of the curve - we can just copy the normal from the first point
00521                     pEdge->Normal = pEdges[0].Normal;
00522                 }
00523                 else
00524                 {
00525                     // Inside the path - just use the next edge to generate a normal
00526                     pEdge->Normal.SetNormalToLine(pEdge->Centre, pNextEdge->Centre);
00527                 }
00528 
00529                 // However, now we must check if we've just completed a mitred join, in
00530                 // which case we have to go back to fill in the previous edge normal
00531                 if (CompletingAMitre)
00532                 {
00533                     // Find the vector pointing towards the mitre point
00534                     pPrevEdge->Normal.Average(PrevNormal, pEdge->Normal);
00535 
00536                     // We now know the direction the mitre intersection (pointy bit) lies in.
00537                     // Now, we will "stretch" that normal by the ratio of the distance to
00538                     // the intersection over the stroke width. 
00539                     // We pass in the point before the join, the join centre, and the point
00540                     // after the join. (Note that the join centre point occupies 3 edge entries)
00541                     double MitreChordRatio = 1.0;
00542                     pProcessor->CalculateMitreIntersection( &pEdges[Index-3].Centre,
00543                                                             &pEdge->Centre,
00544                                                             &pNextEdge->Centre,
00545                                                     /*TO*/  &MitreChordRatio);
00546 
00547                     pPrevEdge->Normal.x *= MitreChordRatio;
00548                     pPrevEdge->Normal.y *= MitreChordRatio;
00549                 }
00550 
00551                 CompletingAMitre = FALSE;       // Clear the mitre flag
00552                 PrevNormal = pEdge->Normal;     // Remember this edge's normal for the next pass
00553             }
00554         }
00555         else
00556         {
00557             // This isn't the first point. It also is not "inside" a joint (although it could be
00558             // the last edge preceeding a join)
00559             if (Index >= Used-1)
00560             {
00561                 // Last point - the normal is merely at right-angles to last line, so = (lineY,-lineX)
00562                 // NOTE that this is not true if this is a closed path, but we will fix that after
00563                 // the loop if it needs fixing
00564                 pEdge->Normal = PrevNormal;
00565             }
00566             else
00567             {
00568                 // Find normal to next line
00569                 NormCoord NextNormal(pEdge->Centre.y - pEdges[Index+1].Centre.y, -(pEdge->Centre.x - pEdges[Index+1].Centre.x));
00570 
00571                 if (NextNormal.x == 0.0 && NextNormal.y == 0.0)
00572                 {
00573                     // This point and the next point are coincident, so we must have hit a cusp join
00574                     // (or rampant discontinuity) The normal is simply perpendicular to the last line
00575                     pEdge->Normal = PrevNormal;
00576                 }
00577                 else
00578                 {
00579                     // This point lies between 2 flattened source path segments, so we simply average
00580                     // their normals to get the path normal at the point.
00581                     NextNormal.Normalise();
00582                     pEdge->Normal.Average(PrevNormal, NextNormal);
00583 
00584                     PrevNormal = NextNormal;        // Remember this normal for the next pass
00585                 }
00586             }
00587         }
00588     }
00589 
00590     return(TRUE);
00591 }

00625 {
00626     // We don't need to do anything unless the user wants parametric positions
00627     if (TravelType != TrapTravel_Parametric || Used < 1)
00628         return(TRUE);
00629 
00630     // --- Record the maximum position value as the millipoint length of the path
00631     // Note: When repeating, we record the length of the repeat rather than the
00632     // actual path length, as this makes the final repeat partial rather than squashed
00633     // when it doesn't all fit in.
00634     if (pParentList != NULL && pParentList->GetRepeatLength() > 0)
00635         PathLength = (double) pParentList->GetRepeatLength();
00636     else
00637         PathLength = pEdges[Used-1].Position;
00638     ERROR2IF(PathLength <= 0.0, FALSE, "No 'travel' in Stroke");
00639 
00640     // --- Normalise the Travel values to generate Position values in range 0.0 to 1.0
00641     // This is done by simply dividing them all by the position of the final edge
00642     if (PathLength > 0.0)
00643     {
00644         double R = 1.0/PathLength;
00645         for (UINT32 Index = 0; Index < Used; Index++)
00646             pEdges[Index].Position *= R;
00647     }
00648 
00649     return(TRUE);
00650 }


Public Member Functions
	TrapEdgeList (TrapsList *pParent=NULL)
	Constructor.
	~TrapEdgeList ()
	Destructor.
UINT32	GetNumEdges (void)
TrapEdge *	GetTrapEdge (UINT32 index)
TrapEdge *	GetLastTrapEdge (void)
UINT32	FindTrapEdge (double Position, UINT32 LoIndex=0, UINT32 HiIndex=0)
	Searches the trapedge list for the trapezoid "containing" the given position value. It starts its search from the given index and searches upwards until it finds the last edge which has a position less than or equal to the given position.
BOOL	AddEdge (DocCoord *pPoint, TrapJoinType JoinType=TrapJoin_None)
	Add a new TrapEdge structure to the list.
BOOL	ProcessEdgeNormals (ProcessPathToTrapezoids *pProcessor)
	Scans the recorded list of edges (added by AddEdge) and fills in the edge Normal information.
BOOL	ProcessEdgePositions (TrapTravelType TravelType)
	Scans the recorded list of edges (added by AddEdge) and fills in the position information according to TravelType. If you don't need Position values, then don't call this function (which will leave Postions totally uninitialised).
double	GetPathLength (void)
Protected Member Functions
BOOL	ExpandArray (void)
	(Internal method) Expands the storage structure of the list to allow more entries to be used. Called automatically by AddEdge if it needs more edges.
Protected Attributes
UINT32	Used
UINT32	CurrentSize
TrapEdge *	pEdges
double	PathLength
TrapsList *	pParentList
Private Member Functions
	CC_DECLARE_DYNCREATE (TrapEdgeList)

TrapEdgeList Class Reference

Public Member Functions

Protected Member Functions

Protected Attributes

Private Member Functions

Detailed Description

Constructor & Destructor Documentation

Member Function Documentation

Member Data Documentation