Update contrib.
1 // Copyright (c) 1997-2009 Nokia Corporation and/or its subsidiary(-ies).
2 // All rights reserved.
3 // This component and the accompanying materials are made available
4 // under the terms of "Eclipse Public License v1.0"
5 // which accompanies this distribution, and is available
6 // at the URL "http://www.eclipse.org/legal/epl-v10.html".
8 // Initial Contributors:
9 // Nokia Corporation - initial contribution.
19 // TCompareEdgesUpperY
21 NONSHARABLE_CLASS(TCompareEdgesUpperY) : public TKey
24 TCompareEdgesUpperY(const CPolygonFiller::SFastData& aFastData);
26 virtual TInt Compare(TInt aLeft,TInt aRight) const;
28 const CPolygonFiller::SFastData& iFastData;
31 TCompareEdgesUpperY::TCompareEdgesUpperY(const CPolygonFiller::SFastData& aFastData):
36 TInt TCompareEdgesUpperY::Compare(TInt aLeft,TInt aRight) const
38 const TInt leftUpperY=iFastData.vertexList[iFastData.edgeList[aLeft].upperVertex].iY;
39 const TInt rightUpperY=iFastData.vertexList[iFastData.edgeList[aRight].upperVertex].iY;
40 if (leftUpperY<rightUpperY)
42 if (leftUpperY>rightUpperY)
49 NONSHARABLE_CLASS(TSwapEdges) : public TSwap
52 TSwapEdges(CPolygonFiller::SFastData& aFastData);
54 virtual void Swap(TInt aLeft,TInt aRight) const;
56 CPolygonFiller::SFastData& iFastData;
59 TSwapEdges::TSwapEdges(CPolygonFiller::SFastData& aFastData):
64 void TSwapEdges::Swap(TInt aLeft,TInt aRight) const
66 CPolygonFiller::SFastEdge& leftEdge=iFastData.edgeList[aLeft];
67 CPolygonFiller::SFastEdge& rightEdge=iFastData.edgeList[aRight];
69 const CPolygonFiller::SFastEdge temp(leftEdge);
74 // TCompareActiveEdgesFirstVertex
76 NONSHARABLE_CLASS(TCompareActiveEdgesFirstVertex) : public TKey
79 TCompareActiveEdgesFirstVertex(const CPolygonFiller::SFastData& aFastData);
81 virtual TInt Compare(TInt aLeft,TInt aRight) const;
83 const CPolygonFiller::SFastData& iFastData;
86 TCompareActiveEdgesFirstVertex::TCompareActiveEdgesFirstVertex(const CPolygonFiller::SFastData& aFastData):
91 TInt TCompareActiveEdgesFirstVertex::Compare(TInt aLeft,TInt aRight) const
93 const TInt leftFirstVertex=iFastData.activeEdgeList[aLeft].edgePtr->firstVertex;
94 const TInt rightFirstVertex=iFastData.activeEdgeList[aRight].edgePtr->firstVertex;
95 if (leftFirstVertex<rightFirstVertex)
97 if (leftFirstVertex>rightFirstVertex)
104 NONSHARABLE_CLASS(TSwapActiveEdges) : public TSwap
107 TSwapActiveEdges(CPolygonFiller::SFastData& aFastData);
109 virtual void Swap(TInt aLeft,TInt aRight) const;
111 CPolygonFiller::SFastData& iFastData;
114 TSwapActiveEdges::TSwapActiveEdges(CPolygonFiller::SFastData& aFastData):
119 void TSwapActiveEdges::Swap(TInt aLeft,TInt aRight) const
121 CPolygonFiller::SFastActiveEdge& leftActiveEdge=iFastData.activeEdgeList[aLeft];
122 CPolygonFiller::SFastActiveEdge& rightActiveEdge=iFastData.activeEdgeList[aRight];
124 const CPolygonFiller::SFastActiveEdge temp(leftActiveEdge);
125 leftActiveEdge=rightActiveEdge;
126 rightActiveEdge=temp;
128 if (leftActiveEdge.scanLineIntersectionPtr!=NULL)
129 leftActiveEdge.scanLineIntersectionPtr->activeEdgePtr=&leftActiveEdge;
130 if (rightActiveEdge.scanLineIntersectionPtr!=NULL)
131 rightActiveEdge.scanLineIntersectionPtr->activeEdgePtr=&rightActiveEdge;
134 // TCompareScanLineIntersectionsFirstPixel
136 NONSHARABLE_CLASS(TCompareScanLineIntersectionsFirstPixel) : public TKey
139 TCompareScanLineIntersectionsFirstPixel(const CPolygonFiller::SFastData& aFastData);
141 virtual TInt Compare(TInt aLeft,TInt aRight) const;
143 const CPolygonFiller::SFastData& iFastData;
146 TCompareScanLineIntersectionsFirstPixel::TCompareScanLineIntersectionsFirstPixel(const CPolygonFiller::SFastData& aFastData):
151 TInt TCompareScanLineIntersectionsFirstPixel::Compare(TInt aLeft,TInt aRight) const
153 const TInt leftFirstPixel=iFastData.scanLineIntersectionList[aLeft].firstPixel;
154 const TInt rightFirstPixel=iFastData.scanLineIntersectionList[aRight].firstPixel;
155 if (leftFirstPixel<rightFirstPixel)
157 if (leftFirstPixel>rightFirstPixel)
162 // TSwapScanLineIntersections
164 NONSHARABLE_CLASS(TSwapScanLineIntersections) : public TSwap
167 TSwapScanLineIntersections(CPolygonFiller::SFastData& aFastData);
169 virtual void Swap(TInt aLeft,TInt aRight) const;
171 CPolygonFiller::SFastData& iFastData;
174 TSwapScanLineIntersections::TSwapScanLineIntersections(CPolygonFiller::SFastData& aFastData):
179 void TSwapScanLineIntersections::Swap(TInt aLeft,TInt aRight) const
181 CPolygonFiller::SFastScanLineIntersection& leftScanLineIntersection=iFastData.scanLineIntersectionList[aLeft];
182 CPolygonFiller::SFastScanLineIntersection& rightScanLineIntersection=iFastData.scanLineIntersectionList[aRight];
184 const CPolygonFiller::SFastScanLineIntersection temp(leftScanLineIntersection);
185 leftScanLineIntersection=rightScanLineIntersection;
186 rightScanLineIntersection=temp;
188 leftScanLineIntersection.activeEdgePtr->scanLineIntersectionPtr=&leftScanLineIntersection;
189 rightScanLineIntersection.activeEdgePtr->scanLineIntersectionPtr=&rightScanLineIntersection;
192 // the sorting function
194 LOCAL_C void Sort(TInt aCount,const TKey& aKey,const TSwap& aSwap)
197 const TInt error=User::QuickSort(aCount,aKey,aSwap);
198 BG_ASSERT_ALWAYS_INVARIANT(error==KErrNone);
199 #elif 0 // bubble sort
200 for (TInt i=1; i<aCount; ++i)
202 for (TInt j=i; j>0; --j)
204 if (aKey.Compare(j-1,j)>0)
211 TInt startOfSortedPortion=aCount;
212 if (startOfSortedPortion>1)
214 TInt startOfHeap=startOfSortedPortion>>1;
217 BG_ASSERT_DEBUG_INVARIANT(startOfHeap>=0);
224 --startOfSortedPortion;
225 aSwap.Swap(startOfSortedPortion,0);
226 BG_ASSERT_DEBUG_INVARIANT(startOfSortedPortion>=1);
227 if (startOfSortedPortion==1)
232 // put aArray[startOfHeap] into the correct place in the heap
237 if ((j>=startOfSortedPortion) || (aKey.Compare(j-1,j)>0))
241 if ((j>=startOfSortedPortion) || (aKey.Compare(i,j)>=0))
253 for (TInt i=1; i<aCount; ++i)
255 BG_ASSERT_DEBUG_INVARIANT(aKey.Compare(i-1,i)<=0);
266 Constructor which initializes all member data to zero, EFalse or null for
267 TInt, TBool pointers respectively.
269 EXPORT_C CPolygonFiller::CPolygonFiller():
273 iFillRule(CGraphicsContext::EAlternate),
274 iUseFastAlgorithm(EFalse),
278 iScanLineIntersection(0),
279 iRightMostPixelOnScanLine(0),
281 iPolygonIsAllHorizontal(EFalse),
286 iFastData.vertexList=NULL;
287 iFastData.edgeList=NULL;
288 iFastData.activeEdgeList=NULL;
289 iFastData.scanLineIntersectionList=NULL;
290 iFastData.numActiveEdges=0;
291 iFastData.numScanLineIntersections=0;
292 iFastData.nextEdgeToActivate=0;
293 iSlowData.numIntersectionsWithSameFirstPixelPreviouslyMet=0;
294 iSlowData.numIntersectionsWithSameFirstPixelMetThisTime=0;
295 iSlowData.numScanLineIntersections=0;
296 iSlowData.scanLineComplete=EFalse;
297 iSlowData.firstPixelOfLastIntersectionInPrevBuffer=0;
301 Destructor calls reset on the polygon.
303 EXPORT_C CPolygonFiller::~CPolygonFiller()
309 Takes a list of points to be the points for the new polygon and sets the number of points in the shape.
310 After this has been done it transfers the task to <code>Construct(aFillRule,aUsage)</code>. This should not fail.
311 @param aPointList A list of points for the polygon.
312 @param aNumPoints The number of points in the list.
313 @param aFillRule How filling should be achieved, as described by a CGraphicsContext::TFillRule object.
314 @param aUsage How the polygon should be used, see TUsage enumeration.
316 EXPORT_C void CPolygonFiller::Construct(const TPoint* aPointList,TInt aNumPoints,
317 CGraphicsContext::TFillRule aFillRule, TUsage aUsage)
319 BG_ASSERT_ALWAYS(aPointList!=NULL,EBitgdiPanicPolygonFiller);
320 iPointList=aPointList;
321 iNumVertexes=aNumPoints;
322 Construct(aFillRule,aUsage);
326 An overloaded version of Construct which allows the list of points to be passed in as a point array.
327 Exactly the same behaviour and structure as above. This should not fail. This method does not require the
328 number of nodes to be given as a parameter.
329 @param PointArray A pointer to point array, as opposed to a pointer to a point list.
330 @param aFillRule How filling should be achieved, as described by a CGraphicsContext::TFillRule object.
331 @param aUsage How the polygon should be used.
333 EXPORT_C void CPolygonFiller::Construct(const CArrayFix<TPoint>* aPointArray,
334 CGraphicsContext::TFillRule aFillRule, TUsage aUsage)
336 BG_ASSERT_ALWAYS(aPointArray!=NULL,EBitgdiPanicPolygonFiller);
337 iPointArray=aPointArray;
338 iNumVertexes=iPointArray->Count();
339 Construct(aFillRule,aUsage);
342 void CPolygonFiller::Construct(CGraphicsContext::TFillRule aFillRule, TUsage aUsage)
344 BG_ASSERT_ALWAYS((aFillRule==CGraphicsContext::EAlternate) || (aFillRule==CGraphicsContext::EWinding),
345 EBitgdiPanicPolygonFiller);
346 BG_ASSERT_ALWAYS((aUsage==EGetAllPixelRunsSequentially) || (aUsage==EGetPixelRunsSequentiallyForSpecifiedScanLines),
347 EBitgdiPanicPolygonFiller);
350 iUseFastAlgorithm=(aUsage==EGetAllPixelRunsSequentially);
353 iScanLineIntersection=0;
354 iRightMostPixelOnScanLine=KMinTInt;
355 // find the first vertex and see if the polygon is all horizontal
356 iFirstVertex=0; // dummy default value
357 iPolygonIsAllHorizontal=ETrue;
362 for (i=0; i<iNumVertexes; ++i)
363 if (Point(i).iY!=Point((i+1)%iNumVertexes).iY)
365 // i is now set to the vertex before the first non-horizontal edge
367 // set j%iNumVertexes to the vertex before the next non-horizontal edge
368 for (j=i+1; Point(j%iNumVertexes).iY==Point((j+1)%iNumVertexes).iY; ++j)
371 TInt first=Point(i).iY;
372 TInt middle=Point(j).iY;
373 TInt last=Point((j+1)%iNumVertexes).iY;
375 // if vertex j is a max or min point, set the first-vertex to be j
376 if ((middle<first)==(middle<last))
379 iPolygonIsAllHorizontal=EFalse;
384 if (iUseFastAlgorithm)
386 iFastData.vertexList=(TPoint*)User::Alloc(sizeof(TPoint)*iNumVertexes);
387 iFastData.edgeList=(SFastEdge*)User::Alloc(sizeof(SFastEdge)*iNumVertexes);
388 iFastData.activeEdgeList=(SFastActiveEdge*)User::Alloc(sizeof(SFastActiveEdge)*iNumVertexes);
389 iFastData.scanLineIntersectionList=(SFastScanLineIntersection*)User::Alloc(sizeof(SFastScanLineIntersection)*iNumVertexes);
390 if ((iFastData.vertexList==NULL) ||
391 (iFastData.edgeList==NULL) ||
392 (iFastData.activeEdgeList==NULL) ||
393 (iFastData.scanLineIntersectionList==NULL))
395 Reset(); // sets iUseFastAlgorithm to EFalse among other things
399 if (iUseFastAlgorithm)
401 for(TInt vertexcount=0;vertexcount<iNumVertexes;vertexcount++)
402 new(&iFastData.activeEdgeList[vertexcount]) SFastActiveEdge;
403 iFastData.numActiveEdges=0;
404 iFastData.numScanLineIntersections=0;
405 iFastData.nextEdgeToActivate=0;
407 // put the points into the vertex-list
408 // N.B. this array is uesd for speed since CArrayXxxs are slower for indexing into than built-in arrays
409 for (i=0; i<iNumVertexes; ++i)
410 iFastData.vertexList[i]=Point((i+iFirstVertex)%iNumVertexes);
413 for (i=0; i<iNumVertexes; ++i)
415 if (iFastData.vertexList[i].iY<iFastData.vertexList[(i+1)%iNumVertexes].iY)
417 iFastData.edgeList[i].upperVertex=i;
418 iFastData.edgeList[i].lowerVertex=(i+1)%iNumVertexes;
422 iFastData.edgeList[i].upperVertex=(i+1)%iNumVertexes;
423 iFastData.edgeList[i].lowerVertex=i;
425 iFastData.edgeList[i].firstVertex=i;
428 // sort edge-list into order of increasing upper y-position
429 Sort(iNumVertexes,TCompareEdgesUpperY(iFastData),TSwapEdges(iFastData));
431 // find the first scan-line
432 iFirstScanLine=iFastData.vertexList[iFastData.edgeList[0].upperVertex].iY;
434 // find the last scan-line
435 iLastScanLine=iFirstScanLine;
436 for (i=0; i<iNumVertexes; ++i)
437 if (iLastScanLine<iFastData.vertexList[i].iY)
438 iLastScanLine=iFastData.vertexList[i].iY;
442 iSlowData.numIntersectionsWithSameFirstPixelPreviouslyMet=0;
443 iSlowData.scanLineComplete=EFalse;
444 iSlowData.firstPixelOfLastIntersectionInPrevBuffer=KMinTInt;
446 // find the first and last scan-lines
447 iFirstScanLine=KMaxTInt;
448 iLastScanLine=KMinTInt;
449 for (i=0; i<iNumVertexes; ++i)
452 if (iFirstScanLine>y)
459 iCurrentScanLine=iFirstScanLine;
463 Frees any data held in the polygons lists of all edges, vertexs and scan lines and sets these values to NULL.
464 It also has the feature of setting iUseFastAlgorithm = EFalse.
466 EXPORT_C void CPolygonFiller::Reset()
468 if(iUseFastAlgorithm)
470 if(iFastData.vertexList)
472 User::Free(iFastData.vertexList);
473 iFastData.vertexList=NULL;
475 if(iFastData.edgeList)
477 User::Free(iFastData.edgeList);
478 iFastData.edgeList=NULL;
480 if(iFastData.activeEdgeList)
482 User::Free(iFastData.activeEdgeList);
483 iFastData.activeEdgeList=NULL;
485 if(iFastData.scanLineIntersectionList)
487 User::Free(iFastData.scanLineIntersectionList);
488 iFastData.scanLineIntersectionList=NULL;
490 iUseFastAlgorithm=EFalse;
495 Method is used to calculate the locations of vertex interactions between the polygon and scan lines.
496 An initial scan line is required. It calculates the start and end positions on the line. The method
497 can use either the fast or slow polygon algorithm depending upon the state of aUsage. Polygon filling
498 is also addressed by this method.
499 @param aExists Will be set to false if a polygon with no vertexes is passed in, otherwise ETrue on return.
500 @param aScanline On return will contain iScanline at the beginning of the operation.
501 @param aStart The position on the scan line to start the run, on returned.
502 @param aEnd The position on the scan line to end the run, returned.
504 EXPORT_C void CPolygonFiller::GetNextPixelRun(TBool& aExists, TInt& aScanLine, TInt& aStart,
507 if (iNumVertexes==0 || iCurrentScanLine>iLastScanLine)
514 aScanLine=iCurrentScanLine;
516 if (iPolygonIsAllHorizontal)
518 // set the start after the end
525 if (iUseFastAlgorithm)
529 if (iScanLineIntersection==0)
531 // add any new edges to the active-edge-list
532 for (; (iFastData.nextEdgeToActivate<iNumVertexes) &&
533 (iFastData.vertexList[iFastData.edgeList[iFastData.nextEdgeToActivate].upperVertex].iY==iCurrentScanLine);
534 ++iFastData.numActiveEdges, ++iFastData.nextEdgeToActivate)
536 iFastData.activeEdgeList[iFastData.numActiveEdges].edgePtr=&iFastData.edgeList[iFastData.nextEdgeToActivate];
537 iFastData.activeEdgeList[iFastData.numActiveEdges].lineGenerator.Construct(
538 iFastData.vertexList[iFastData.edgeList[iFastData.nextEdgeToActivate].upperVertex],
539 iFastData.vertexList[iFastData.edgeList[iFastData.nextEdgeToActivate].lowerVertex]);
540 iFastData.activeEdgeList[iFastData.numActiveEdges].scanLineIntersectionPtr=NULL;
543 // sort the active-edge-list into order of adjacent edges (if possible)
544 Sort(iFastData.numActiveEdges,TCompareActiveEdgesFirstVertex(iFastData),TSwapActiveEdges(iFastData));
546 // find the intersection of each active-edge with the current scan-line
547 // for max/min vertex-runs (e.g. \/, \_/, \__/, etc.) add 2 intersections for each run
548 // for other vertex-runs (e.g. /----/) add 1 intersection for each run
549 for (i=0; i<iFastData.numActiveEdges; ++i)
551 // check that active-edge i is not horizontal
552 BG_ASSERT_DEBUG(iFastData.vertexList[iFastData.activeEdgeList[i].edgePtr->upperVertex].iY!=
553 iFastData.vertexList[iFastData.activeEdgeList[i].edgePtr->lowerVertex].iY, EBitgdiPanicPolygonFiller);
555 if (iFastData.vertexList[iFastData.activeEdgeList[i].edgePtr->upperVertex].iY==iCurrentScanLine)
556 // the scan-line is intersecting active-edge i at its upper-vertex
557 FastHandleVertexIntersection(i, EFalse);
558 else if (iFastData.vertexList[iFastData.activeEdgeList[i].edgePtr->lowerVertex].iY==iCurrentScanLine)
559 // the scan-line is intersecting active-edge i at its lower-vertex
560 FastHandleVertexIntersection(i, ETrue);
562 // the scan-line is intersecting active-edge i at neither of its vertices
563 SetFastIntersection(iFastData.activeEdgeList[i],*iFastData.activeEdgeList[i].scanLineIntersectionPtr);
566 // N.B. iFastData.numScanLineIntersections is less than or equal to iFastData.numActiveEdges
568 // sort the intersection-list into increasing order of first-pixel
569 Sort(iFastData.numScanLineIntersections,TCompareScanLineIntersectionsFirstPixel(iFastData),TSwapScanLineIntersections(iFastData));
571 BG_ASSERT_DEBUG(iFastData.numScanLineIntersections>=2, EBitgdiPanicPolygonFiller);
574 // depending on the rule used, find the pixel-run
575 TBool doFill=EFalse; // dummy initialization to prevent compiler warning
576 if (iScanLineIntersection<iFastData.numScanLineIntersections-1)
580 case CGraphicsContext::EAlternate:
584 case CGraphicsContext::EWinding:
585 BG_ASSERT_DEBUG(iFastData.vertexList[iFastData.scanLineIntersectionList[iScanLineIntersection].activeEdgePtr->edgePtr->lowerVertex].iY!=
586 iFastData.vertexList[iFastData.scanLineIntersectionList[iScanLineIntersection].activeEdgePtr->edgePtr->upperVertex].iY,
587 EBitgdiPanicPolygonFiller);
589 if (iFastData.scanLineIntersectionList[iScanLineIntersection].activeEdgePtr->edgePtr->lowerVertex==
590 (iFastData.scanLineIntersectionList[iScanLineIntersection].activeEdgePtr->edgePtr->upperVertex+1)%iNumVertexes)
595 doFill=(iNestingLevel!=0);
601 aStart=Max(iRightMostPixelOnScanLine, iFastData.scanLineIntersectionList[iScanLineIntersection].lastPixel)+1;
602 aEnd=iFastData.scanLineIntersectionList[iScanLineIntersection+1].firstPixel-1;
606 // set the start after the end
611 if (iRightMostPixelOnScanLine<iFastData.scanLineIntersectionList[iScanLineIntersection].lastPixel)
612 iRightMostPixelOnScanLine=iFastData.scanLineIntersectionList[iScanLineIntersection].lastPixel;
613 ++iScanLineIntersection;
616 if (iScanLineIntersection==iFastData.numScanLineIntersections-1)
618 BG_ASSERT_DEBUG(iFastData.vertexList[iFastData.scanLineIntersectionList[iScanLineIntersection].activeEdgePtr->edgePtr->lowerVertex].iY!=
619 iFastData.vertexList[iFastData.scanLineIntersectionList[iScanLineIntersection].activeEdgePtr->edgePtr->upperVertex].iY,
620 EBitgdiPanicPolygonFiller);
624 case CGraphicsContext::EAlternate:
626 BG_ASSERT_DEBUG(iToggler==0, EBitgdiPanicPolygonFiller);
628 case CGraphicsContext::EWinding:
629 if (iFastData.scanLineIntersectionList[iScanLineIntersection].activeEdgePtr->edgePtr->lowerVertex==
630 (iFastData.scanLineIntersectionList[iScanLineIntersection].activeEdgePtr->edgePtr->upperVertex+1)%iNumVertexes)
634 BG_ASSERT_DEBUG((iNumVertexes==2) || (iNestingLevel==0), EBitgdiPanicPolygonFiller);
638 // remove any scan-line-intersections associated with old active-edges
639 for (i=0; i<iFastData.numScanLineIntersections; )
640 if (iFastData.vertexList[iFastData.scanLineIntersectionList[i].activeEdgePtr->edgePtr->lowerVertex].iY==iCurrentScanLine)
642 iFastData.scanLineIntersectionList[i].activeEdgePtr->scanLineIntersectionPtr=NULL;
644 // ripple all the entries in the scan-line-intersection-list after this one back one place
645 for (j=i+1; j<iFastData.numScanLineIntersections; ++j)
647 iFastData.scanLineIntersectionList[j-1]=iFastData.scanLineIntersectionList[j];
648 iFastData.scanLineIntersectionList[j-1].activeEdgePtr->scanLineIntersectionPtr=&iFastData.scanLineIntersectionList[j-1];
651 iFastData.scanLineIntersectionList[j-1].activeEdgePtr=NULL;
652 --iFastData.numScanLineIntersections;
657 // remove any old edges from the active-edge-list
658 for (i=0; i<iFastData.numActiveEdges; )
659 if (iFastData.vertexList[iFastData.activeEdgeList[i].edgePtr->lowerVertex].iY==iCurrentScanLine)
661 BG_ASSERT_DEBUG(iFastData.activeEdgeList[i].scanLineIntersectionPtr==NULL, EBitgdiPanicPolygonFiller);
663 // ripple all the entries in the active-edge-list after this one back one place
664 for (j=i+1; j<iFastData.numActiveEdges; ++j)
666 iFastData.activeEdgeList[j-1]=iFastData.activeEdgeList[j];
667 if (iFastData.activeEdgeList[j-1].scanLineIntersectionPtr)
668 iFastData.activeEdgeList[j-1].scanLineIntersectionPtr->activeEdgePtr=&iFastData.activeEdgeList[j-1];
671 iFastData.activeEdgeList[j-1].scanLineIntersectionPtr=NULL;
672 --iFastData.numActiveEdges;
678 for (i=0; i<iFastData.numActiveEdges; ++i)
680 BG_ASSERT_DEBUG(iFastData.activeEdgeList[i].scanLineIntersectionPtr->activeEdgePtr==
681 &iFastData.activeEdgeList[i], EBitgdiPanicPolygonFiller);
684 for (i=0; i<iFastData.numScanLineIntersections; ++i)
686 BG_ASSERT_DEBUG(iFastData.scanLineIntersectionList[i].activeEdgePtr->scanLineIntersectionPtr==
687 &iFastData.scanLineIntersectionList[i], EBitgdiPanicPolygonFiller);
691 iScanLineIntersection=0;
693 iRightMostPixelOnScanLine=KMinTInt;
698 GetNextPixelRunOnSpecifiedScanLine(aExists, iCurrentScanLine, aStart, aEnd);
700 GetNextPixelRunOnSpecifiedScanLine(aExists, ++iCurrentScanLine, aStart, aEnd);
705 Similar to GetNextPixelRun(aExists, aScanLine, aStart, aEnd) this method is used to draw the relevant
706 vertex intersections for a polygon but only for an individual specified scan line. The method
707 can use either the fast or slow polygon algorithm depending upon the state of aUsage.
708 @param aExists Will be set to false if the line does not pass through the polygon or if
709 a polygon with no vertices is specified, otherwise ETrue on return.
710 @param aScanline The scan line to be drawn on. Used to set iScanline
711 @param aStart The position on the scan line to start the run, on returned.
712 @param aEnd The position on the scan line to end the run, returned.
714 EXPORT_C void CPolygonFiller::GetNextPixelRunOnSpecifiedScanLine(TBool& aExists,
721 BG_ASSERT_DEBUG(!iUseFastAlgorithm, EBitgdiPanicPolygonFiller);
723 if (iNumVertexes==0 || aScanLine<iCurrentScanLine || aScanLine>iLastScanLine)
730 iCurrentScanLine=aScanLine;
732 if (iPolygonIsAllHorizontal)
734 // set the start after the end
741 if (iScanLineIntersection==0)
743 iSlowData.numIntersectionsWithSameFirstPixelMetThisTime=0;
744 iSlowData.numScanLineIntersections=0;
745 iSlowData.scanLineComplete=ETrue;
747 // find the left-most iSlowData::EStoreSize number (or less) of intersections with this scan-line
748 for (i=iFirstVertex; i<iNumVertexes+iFirstVertex; ++i)
750 TPoint upper=Point(i%iNumVertexes);
751 TPoint lower=Point((i+1)%iNumVertexes);
752 if (upper.iY>lower.iY)
759 if ((iCurrentScanLine>=upper.iY) && (iCurrentScanLine<=lower.iY))
761 // check that the edge starting at vertex i%iNumVertexes is not horizontal
762 BG_ASSERT_DEBUG(upper.iY!=lower.iY, EBitgdiPanicPolygonFiller);
764 // step through the line-generator until the current scan-line is reached
765 TPoint startPos, endPos;
766 JumpToCurrentScanLine(iSlowData.lineGenerator, upper, lower, startPos, endPos);
768 // find the intersection start and end pixels
769 SSlowScanLineIntersection scanLineIntersection;
770 scanLineIntersection.firstPixel=Min(startPos.iX, endPos.iX);
771 scanLineIntersection.lastPixel=Max(startPos.iX, endPos.iX);
772 scanLineIntersection.firstVertexOfEdge=i%iNumVertexes;
774 // handle horizontal runs and minima/maxima
775 if (upper.iY==iCurrentScanLine)
776 SlowHandleVertexIntersection(scanLineIntersection, i, EFalse);
777 else if (lower.iY==iCurrentScanLine)
778 SlowHandleVertexIntersection(scanLineIntersection, i, ETrue);
780 // see if there have been other intersections with the same first-pixel
781 if (scanLineIntersection.firstPixel==iSlowData.firstPixelOfLastIntersectionInPrevBuffer)
782 ++iSlowData.numIntersectionsWithSameFirstPixelMetThisTime;
784 // if the intersection has not already been included in a previous buffer-load
785 if ((scanLineIntersection.firstPixel>iSlowData.firstPixelOfLastIntersectionInPrevBuffer) ||
786 ((scanLineIntersection.firstPixel==iSlowData.firstPixelOfLastIntersectionInPrevBuffer) &&
787 (iSlowData.numIntersectionsWithSameFirstPixelMetThisTime>=
788 iSlowData.numIntersectionsWithSameFirstPixelPreviouslyMet)))
790 // put the intersection in the right place in the intersection list (if there is room)
791 for (j=0; j<iSlowData.numScanLineIntersections; ++j)
792 if (scanLineIntersection.firstPixel<iSlowData.scanLineIntersectionList[j].firstPixel)
794 if (iSlowData.numScanLineIntersections<SSlowData::EStoreSize)
795 ++iSlowData.numScanLineIntersections;
797 iSlowData.scanLineComplete=EFalse;
799 for (k=iSlowData.numScanLineIntersections-1; k>j; --k)
800 iSlowData.scanLineIntersectionList[k]=iSlowData.scanLineIntersectionList[k-1];
801 iSlowData.scanLineIntersectionList[j]=scanLineIntersection;
804 if (j==iSlowData.numScanLineIntersections)
806 if (iSlowData.numScanLineIntersections<SSlowData::EStoreSize)
807 iSlowData.scanLineIntersectionList[iSlowData.numScanLineIntersections++]=scanLineIntersection;
809 iSlowData.scanLineComplete=EFalse;
815 if (!iSlowData.scanLineComplete)
817 BG_ASSERT_DEBUG(iSlowData.numScanLineIntersections==SSlowData::EStoreSize, EBitgdiPanicPolygonFiller);
819 if (iSlowData.firstPixelOfLastIntersectionInPrevBuffer==iSlowData.scanLineIntersectionList[SSlowData::EStoreSize-1].firstPixel)
820 iSlowData.numIntersectionsWithSameFirstPixelPreviouslyMet+=SSlowData::EStoreSize-1;
823 iSlowData.firstPixelOfLastIntersectionInPrevBuffer=iSlowData.scanLineIntersectionList[SSlowData::EStoreSize-1].firstPixel;
824 iSlowData.numIntersectionsWithSameFirstPixelPreviouslyMet=1;
825 for (i=SSlowData::EStoreSize-1; (i>0) && (iSlowData.firstPixelOfLastIntersectionInPrevBuffer==
826 iSlowData.scanLineIntersectionList[i-1].firstPixel); --i)
827 ++iSlowData.numIntersectionsWithSameFirstPixelPreviouslyMet;
832 // depending on the rule used, find the pixel-run
833 TBool doFill=EFalse; // dummy initialization to prevent compiler warning
834 if (iScanLineIntersection<iSlowData.numScanLineIntersections-1)
838 case CGraphicsContext::EAlternate:
842 case CGraphicsContext::EWinding:
843 BG_ASSERT_DEBUG(Point(iSlowData.scanLineIntersectionList[iScanLineIntersection].firstVertexOfEdge).iY!=
844 Point((iSlowData.scanLineIntersectionList[iScanLineIntersection].firstVertexOfEdge+1)%iNumVertexes).iY,
845 EBitgdiPanicPolygonFiller);
847 if (Point(iSlowData.scanLineIntersectionList[iScanLineIntersection].firstVertexOfEdge).iY>
848 Point((iSlowData.scanLineIntersectionList[iScanLineIntersection].firstVertexOfEdge+1)%iNumVertexes).iY)
853 doFill=(iNestingLevel!=0);
859 aStart=Max(iRightMostPixelOnScanLine, iSlowData.scanLineIntersectionList[iScanLineIntersection].lastPixel)+1;
860 aEnd=iSlowData.scanLineIntersectionList[iScanLineIntersection+1].firstPixel-1;
864 // set the start after the end
869 if (iRightMostPixelOnScanLine<iSlowData.scanLineIntersectionList[iScanLineIntersection].lastPixel)
870 iRightMostPixelOnScanLine=iSlowData.scanLineIntersectionList[iScanLineIntersection].lastPixel;
871 ++iScanLineIntersection;
874 if (iScanLineIntersection==iSlowData.numScanLineIntersections-1)
876 if (iSlowData.scanLineComplete)
878 BG_ASSERT_DEBUG(Point(iSlowData.scanLineIntersectionList[iScanLineIntersection].firstVertexOfEdge).iY!=
879 Point((iSlowData.scanLineIntersectionList[iScanLineIntersection].firstVertexOfEdge+1)%iNumVertexes).iY,
880 EBitgdiPanicPolygonFiller);
884 case CGraphicsContext::EAlternate:
886 BG_ASSERT_DEBUG(iToggler==0, EBitgdiPanicPolygonFiller);
888 case CGraphicsContext::EWinding:
889 if (Point(iSlowData.scanLineIntersectionList[iScanLineIntersection].firstVertexOfEdge).iY>
890 Point((iSlowData.scanLineIntersectionList[iScanLineIntersection].firstVertexOfEdge+1)%iNumVertexes).iY)
895 BG_ASSERT_DEBUG((!iSlowData.scanLineComplete) || (iNumVertexes==2) || (iNestingLevel==0), EBitgdiPanicPolygonFiller);
900 iScanLineIntersection=0;
901 if (iSlowData.scanLineComplete)
904 iRightMostPixelOnScanLine=KMinTInt;
905 iSlowData.numIntersectionsWithSameFirstPixelPreviouslyMet=0;
906 iSlowData.scanLineComplete=EFalse;
907 iSlowData.firstPixelOfLastIntersectionInPrevBuffer=KMinTInt;
912 void CPolygonFiller::FastHandleVertexIntersection(TInt& aCurrentActiveEdge,
913 TBool aIsLowerVertex)
915 BG_ASSERT_DEBUG(iUseFastAlgorithm, EBitgdiPanicPolygonFiller);
917 if (iFastData.vertexList[(iFastData.activeEdgeList[aCurrentActiveEdge].edgePtr->firstVertex+1)%iNumVertexes].iY==iCurrentScanLine)
918 // it is the second vertex of active-edge aCurrentActiveEdge that coincides with the current scan-line
920 TInt origActiveEdge=aCurrentActiveEdge;
921 SFastScanLineIntersection scanLineIntersection;
922 scanLineIntersection.activeEdgePtr=NULL;
923 SetFastIntersection(iFastData.activeEdgeList[origActiveEdge], scanLineIntersection);
925 // walk through subsequent adjacent horizontal active-edges
928 // exit the loop if the vertex-run *is* a maximum or a minimum
929 const SFastEdge* tempEdgePtr=iFastData.activeEdgeList[(aCurrentActiveEdge+1)%iFastData.numActiveEdges].edgePtr;
930 TBool isMaxOrMin = EFalse;
932 switch(aIsLowerVertex)
935 isMaxOrMin = (iFastData.vertexList[tempEdgePtr->lowerVertex].iY > iCurrentScanLine);
939 isMaxOrMin = (iFastData.vertexList[tempEdgePtr->upperVertex].iY < iCurrentScanLine);
944 // the vertex-run is a maximum or a minimum
948 *iFastData.activeEdgeList[origActiveEdge].scanLineIntersectionPtr=scanLineIntersection;
949 iFastData.activeEdgeList[origActiveEdge].scanLineIntersectionPtr->activeEdgePtr=&iFastData.activeEdgeList[origActiveEdge];
953 // add an intersection
954 iFastData.scanLineIntersectionList[iFastData.numScanLineIntersections]=scanLineIntersection;
955 iFastData.scanLineIntersectionList[iFastData.numScanLineIntersections].activeEdgePtr=&iFastData.activeEdgeList[origActiveEdge];
956 iFastData.activeEdgeList[origActiveEdge].scanLineIntersectionPtr=&iFastData.scanLineIntersectionList[iFastData.numScanLineIntersections];
957 ++iFastData.numScanLineIntersections;
962 // the active-edge is horizontal, or the vertex-run is not a maximum or a minimum
964 ++aCurrentActiveEdge;
965 BG_ASSERT_DEBUG(aCurrentActiveEdge<iFastData.numActiveEdges, EBitgdiPanicPolygonFiller);
967 // update scanLineIntersection
968 TPoint startPos, endPos;
970 iFastData.activeEdgeList[aCurrentActiveEdge].lineGenerator.SingleScanline(startPos, endPos);
971 minX=Min(startPos.iX, endPos.iX);
972 maxX=Max(startPos.iX, endPos.iX);
973 if (scanLineIntersection.firstPixel>minX)
974 scanLineIntersection.firstPixel=minX;
975 if (scanLineIntersection.lastPixel<maxX)
976 scanLineIntersection.lastPixel=maxX;
978 tempEdgePtr=iFastData.activeEdgeList[aCurrentActiveEdge].edgePtr;
979 TBool isNeitherMaxOrMin = EFalse;
981 switch(aIsLowerVertex)
984 isNeitherMaxOrMin = (iFastData.vertexList[tempEdgePtr->upperVertex].iY < iCurrentScanLine);
988 isNeitherMaxOrMin = (iFastData.vertexList[tempEdgePtr->lowerVertex].iY > iCurrentScanLine);
992 // exit the loop if the vertex-run is *not* a maximum or a minimum
993 if (isNeitherMaxOrMin)
999 newActiveEdge=aCurrentActiveEdge;
1000 oldActiveEdge=origActiveEdge;
1004 newActiveEdge=origActiveEdge;
1005 oldActiveEdge=aCurrentActiveEdge;
1007 iFastData.activeEdgeList[newActiveEdge].scanLineIntersectionPtr=iFastData.activeEdgeList[oldActiveEdge].scanLineIntersectionPtr;
1008 iFastData.activeEdgeList[oldActiveEdge].scanLineIntersectionPtr=NULL;
1009 *iFastData.activeEdgeList[newActiveEdge].scanLineIntersectionPtr=scanLineIntersection;
1010 iFastData.activeEdgeList[newActiveEdge].scanLineIntersectionPtr->activeEdgePtr=&iFastData.activeEdgeList[newActiveEdge];
1016 // it is the first vertex of active-edge aCurrentActiveEdge that coincides with the current scan-line
1019 // check that the vertex we are at is a maximum or a minimum
1020 TInt previousNotLevelVertex;
1021 TInt SFastEdge::*vertex=(aIsLowerVertex)? &SFastEdge::lowerVertex: &SFastEdge::upperVertex;
1022 for (previousNotLevelVertex=iFastData.activeEdgeList[aCurrentActiveEdge].edgePtr->*vertex;
1023 iFastData.vertexList[iFastData.activeEdgeList[aCurrentActiveEdge].edgePtr->*vertex].iY==iFastData.vertexList[previousNotLevelVertex].iY;
1024 previousNotLevelVertex=(previousNotLevelVertex+iNumVertexes-1)%iNumVertexes)
1026 TInt nextNotLevelVertex=(iFastData.activeEdgeList[aCurrentActiveEdge].edgePtr->*vertex+1)%iNumVertexes;
1027 BG_ASSERT_DEBUG((iFastData.vertexList[iFastData.activeEdgeList[aCurrentActiveEdge].edgePtr->*vertex].iY>iFastData.vertexList[previousNotLevelVertex].iY)==
1028 (iFastData.vertexList[iFastData.activeEdgeList[aCurrentActiveEdge].edgePtr->*vertex].iY>iFastData.vertexList[nextNotLevelVertex].iY),
1029 EBitgdiPanicPolygonFiller);
1033 SetFastIntersection(iFastData.activeEdgeList[aCurrentActiveEdge],*iFastData.activeEdgeList[aCurrentActiveEdge].scanLineIntersectionPtr);
1036 // add an intersection
1037 SetFastIntersection(iFastData.activeEdgeList[aCurrentActiveEdge], iFastData.scanLineIntersectionList[iFastData.numScanLineIntersections]);
1038 iFastData.scanLineIntersectionList[iFastData.numScanLineIntersections].activeEdgePtr=&iFastData.activeEdgeList[aCurrentActiveEdge];
1039 iFastData.activeEdgeList[aCurrentActiveEdge].scanLineIntersectionPtr=&iFastData.scanLineIntersectionList[iFastData.numScanLineIntersections];
1040 ++iFastData.numScanLineIntersections;
1045 void CPolygonFiller::SetFastIntersection(SFastActiveEdge& aActiveEdge, SFastScanLineIntersection& aScanLineIntersection)
1047 BG_ASSERT_DEBUG(iUseFastAlgorithm, EBitgdiPanicPolygonFiller);
1049 TPoint startPos, endPos;
1051 aActiveEdge.lineGenerator.SingleScanline(startPos, endPos);
1052 aScanLineIntersection.firstPixel=Min(startPos.iX, endPos.iX);
1053 aScanLineIntersection.lastPixel=Max(startPos.iX, endPos.iX);
1056 void CPolygonFiller::SlowHandleVertexIntersection(SSlowScanLineIntersection& aScanLineIntersection,
1057 TInt& aVertexStartingCurrentEdge,
1058 TBool aIsLowerVertex)
1060 if (Point((aVertexStartingCurrentEdge+1)%iNumVertexes).iY==iCurrentScanLine)
1061 // it is the second vertex of the edge starting at vertex aVertexStartingCurrentEdge%iNumVertexes
1062 // that coincides with the current scan-line
1064 // walk through subsequent adjacent horizontal active-edges
1067 TPoint nextVertexButOne=Point((aVertexStartingCurrentEdge+2)%iNumVertexes);
1068 TBool isMaxOrMin = EFalse;
1070 switch(aIsLowerVertex)
1073 isMaxOrMin = (nextVertexButOne.iY > iCurrentScanLine);
1077 isMaxOrMin = (nextVertexButOne.iY < iCurrentScanLine);
1081 // exit the loop if the vertex-run *is* a maximum or a minimum
1087 // the edge starting at vertex aVertexStartingCurrentEdge%iNumVertexes is horizontal, or the vertex-run is not a
1088 // maximum or a minimum
1090 ++aVertexStartingCurrentEdge;
1091 BG_ASSERT_DEBUG(aVertexStartingCurrentEdge%iNumVertexes!=iFirstVertex, EBitgdiPanicPolygonFiller);
1093 // step through the line-generator until the current scan-line is reached
1094 TPoint upper=Point(aVertexStartingCurrentEdge%iNumVertexes);
1095 TPoint lower=nextVertexButOne;
1096 if (upper.iY>lower.iY)
1103 TPoint startPos, endPos;
1104 if (upper.iY!=lower.iY)
1105 JumpToCurrentScanLine(iSlowData.lineGenerator, upper, lower, startPos, endPos);
1108 // N.B. which is set to which doesn't matter, as long as startPos is set to either upper or lower, and endPos is set to the other
1113 // expand the intersection, if necessary
1114 TInt minX=Min(startPos.iX, endPos.iX);
1115 TInt maxX=Max(startPos.iX, endPos.iX);
1116 if (aScanLineIntersection.firstPixel>minX)
1117 aScanLineIntersection.firstPixel=minX;
1118 if (aScanLineIntersection.lastPixel<maxX)
1119 aScanLineIntersection.lastPixel=maxX;
1121 TBool isNeitherMaxOrMin = EFalse;
1123 switch(aIsLowerVertex)
1126 isNeitherMaxOrMin = (nextVertexButOne.iY < iCurrentScanLine);
1130 isNeitherMaxOrMin = (nextVertexButOne.iY > iCurrentScanLine);
1134 // exit the loop if the vertex-run is *not* a maximum or a minimum
1135 if (isNeitherMaxOrMin)
1139 aScanLineIntersection.firstVertexOfEdge=aVertexStartingCurrentEdge%iNumVertexes;
1146 // it is the first vertex of the edge starting at vertex aVertexStartingCurrentEdge%iNumVertexes
1147 // that coincides with the current scan-line
1150 // check that the vertex we are at is a maximum or a minimum
1151 TInt previousNotLevelVertex;
1152 for (previousNotLevelVertex=aVertexStartingCurrentEdge%iNumVertexes;
1153 Point(aVertexStartingCurrentEdge%iNumVertexes).iY==
1154 Point(previousNotLevelVertex).iY;
1155 previousNotLevelVertex=(previousNotLevelVertex+iNumVertexes-1)%iNumVertexes)
1157 TInt nextNotLevelVertex=(aVertexStartingCurrentEdge+1)%iNumVertexes;
1158 TInt previousY=Point(previousNotLevelVertex).iY;
1159 TInt currentY=Point(aVertexStartingCurrentEdge%iNumVertexes).iY;
1160 TInt nextY=Point(nextNotLevelVertex).iY;
1161 BG_ASSERT_DEBUG((currentY>previousY) == (currentY>nextY), EBitgdiPanicPolygonFiller);
1166 void CPolygonFiller::JumpToCurrentScanLine(TLinearDDA& aLineGenerator,
1167 const TPoint& aUpper,
1168 const TPoint& aLower,
1170 TPoint& aEndPos) const
1172 BG_ASSERT_DEBUG(aUpper.iY<=aLower.iY, EBitgdiPanicPolygonFiller);
1173 aLineGenerator.Construct(aUpper, aLower);
1174 if (aUpper.iY<iCurrentScanLine)
1177 aLineGenerator.JumpToYCoord(notUsed, iCurrentScanLine-2);
1180 aLineGenerator.SingleScanline(aStartPos, aEndPos);
1181 while (aStartPos.iY!=iCurrentScanLine);
1182 BG_ASSERT_DEBUG(aStartPos.iY==iCurrentScanLine, EBitgdiPanicPolygonFiller);
1183 BG_ASSERT_DEBUG(aEndPos.iY==iCurrentScanLine, EBitgdiPanicPolygonFiller);
1186 const TPoint& CPolygonFiller::Point(TInt aIndex)
1188 if(iPointList) return(iPointList[aIndex]);
1189 BG_ASSERT_DEBUG(iPointArray,EBitgdiPanicPolygonFiller);
1190 return((*iPointArray)[aIndex]);