1 // Copyright (c) 2007-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".

     7 //

     8 // Initial Contributors:

     9 // Nokia Corporation - initial contribution.

    10 //

    11 // Contributors:

    12 //

    13 // Description:

    14 //

    15 

    16 #include "swdirectgdipolygon.h"

    17 

    18 /**

    19 A utility class used to sort vertex lists based on y coordinates.

    20 @see CSwDirectGdiPolygonFiller

    21 @see TKey

    22 

    23 @internalComponent

    24 */

    25 NONSHARABLE_CLASS(TCompareEdgesUpperY) : public TKey

    26 	{

    27 public:

    28 	TCompareEdgesUpperY(const CSwDirectGdiPolygonFiller::SFastData& aFastData);

    29 private:

    30 	virtual TInt Compare(TInt aLeft,TInt aRight) const;

    31 private:

    32 	const CSwDirectGdiPolygonFiller::SFastData& iFastData;

    33 	};

    34 

    35 TCompareEdgesUpperY::TCompareEdgesUpperY(const CSwDirectGdiPolygonFiller::SFastData& aFastData):

    36 	iFastData(aFastData)

    37 	{

    38 	}

    39 

    40 /**

    41 Compare edges based on their upper Y coordinate.

    42 

    43 @param aLeft Index corresponding to the "left" side of the comparison. 

    44 @param aRight Index corresponding to the "right" side of the comparison.

    45 

    46 @return Zero, if the two keys are equal; negative, if the left key is less than the right key; positive, if the left key is greater than the right key.

    47 

    48 @see TKey::Compare

    49 */

    50 TInt TCompareEdgesUpperY::Compare(TInt aLeft,TInt aRight) const

    51 	{

    52 	const TInt leftUpperY=iFastData.vertexList[iFastData.edgeList[aLeft].upperVertex].iY;

    53 	const TInt rightUpperY=iFastData.vertexList[iFastData.edgeList[aRight].upperVertex].iY;

    54 	if (leftUpperY<rightUpperY)

    55 		return -1;

    56 	if (leftUpperY>rightUpperY)

    57 		return 1;

    58 	return 0;

    59 	}

    60 

    61 /**

    62 A utility class used to swap entries in edgeList arrays during sort operations.

    63 @see CSwDirectGdiPolygonFiller

    64 @see TSwap

    65 

    66 @internalComponent

    67 */

    68 NONSHARABLE_CLASS(TSwapEdges) : public TSwap

    69 	{

    70 public:

    71 	TSwapEdges(CSwDirectGdiPolygonFiller::SFastData& aFastData);

    72 private:

    73 	virtual void Swap(TInt aLeft,TInt aRight) const;

    74 private:

    75 	CSwDirectGdiPolygonFiller::SFastData& iFastData;

    76 	};

    77 

    78 TSwapEdges::TSwapEdges(CSwDirectGdiPolygonFiller::SFastData& aFastData):

    79 	iFastData(aFastData)

    80 	{

    81 	}

    82 

    83 /**

    84 Swaps two elements of an edgeList array. 

    85 

    86 @param aLeft The index of an array element participating in the swap. 

    87 @param aRight The index of an array element participating in the swap.

    88 

    89 @see TSwap::Swap

    90 */

    91 void TSwapEdges::Swap(TInt aLeft,TInt aRight) const

    92 	{

    93 	CSwDirectGdiPolygonFiller::SFastEdge& leftEdge=iFastData.edgeList[aLeft];

    94 	CSwDirectGdiPolygonFiller::SFastEdge& rightEdge=iFastData.edgeList[aRight];

    95 

    96 	const CSwDirectGdiPolygonFiller::SFastEdge temp(leftEdge);

    97 	leftEdge=rightEdge;

    98 	rightEdge=temp;

    99 	}

   100 

   101 /**

   102 A utility class used to sort active edge lists based on the order of their vertexes.

   103 @see CSwDirectGdiPolygonFiller

   104 @see TKey

   105 

   106 @internalComponent

   107 */

   108 NONSHARABLE_CLASS(TCompareActiveEdgesFirstVertex) : public TKey

   109 	{

   110 public:

   111 	TCompareActiveEdgesFirstVertex(const CSwDirectGdiPolygonFiller::SFastData& aFastData);

   112 private:

   113 	virtual TInt Compare(TInt aLeft,TInt aRight) const;

   114 private:

   115 	const CSwDirectGdiPolygonFiller::SFastData& iFastData;

   116 	};

   117 

   118 TCompareActiveEdgesFirstVertex::TCompareActiveEdgesFirstVertex(const CSwDirectGdiPolygonFiller::SFastData& aFastData):

   119 	iFastData(aFastData)

   120 	{

   121 	}

   122 

   123 /**

   124 Compare edges based on the order of their vertexes.

   125 

   126 @param aLeft Index corresponding to the "left" side of the comparison. 

   127 @param aRight Index corresponding to the "right" side of the comparison.

   128 

   129 @return Zero, if the two keys are equal; negative, if the left key is less than the right key; positive, if the left key is greater than the right key.

   130 

   131 @see TKey::Compare

   132 */

   133 TInt TCompareActiveEdgesFirstVertex::Compare(TInt aLeft,TInt aRight) const

   134 	{

   135 	const TInt leftFirstVertex=iFastData.activeEdgeList[aLeft].edgePtr->firstVertex;

   136 	const TInt rightFirstVertex=iFastData.activeEdgeList[aRight].edgePtr->firstVertex;

   137 	if (leftFirstVertex<rightFirstVertex)

   138 		return -1;

   139 	if (leftFirstVertex>rightFirstVertex)

   140 		return 1;

   141 	return 0;

   142 	}

   143 

   144 /**

   145 A utility class used to swap entries in activeEdgeList arrays during sort operations.

   146 @see CSwDirectGdiPolygonFiller

   147 @see TSwap

   148 

   149 @internalComponent

   150 */

   151 NONSHARABLE_CLASS(TSwapActiveEdges) : public TSwap

   152 	{

   153 public:

   154 	TSwapActiveEdges(CSwDirectGdiPolygonFiller::SFastData& aFastData);

   155 private:

   156 	virtual void Swap(TInt aLeft,TInt aRight) const;

   157 private:

   158 	CSwDirectGdiPolygonFiller::SFastData& iFastData;

   159 	};

   160 

   161 TSwapActiveEdges::TSwapActiveEdges(CSwDirectGdiPolygonFiller::SFastData& aFastData):

   162 	iFastData(aFastData)

   163 	{

   164 	}

   165 

   166 /**

   167 Swaps two elements of an activeEdgeList array. 

   168 @param aLeft The index of an array element participating in the swap. 

   169 @param aRight The index of an array element participating in the swap.

   170 @see TSwap::Swap

   171 */

   172 void TSwapActiveEdges::Swap(TInt aLeft,TInt aRight) const

   173 	{

   174 	CSwDirectGdiPolygonFiller::SFastActiveEdge& leftActiveEdge=iFastData.activeEdgeList[aLeft];

   175 	CSwDirectGdiPolygonFiller::SFastActiveEdge& rightActiveEdge=iFastData.activeEdgeList[aRight];

   176 

   177 	const CSwDirectGdiPolygonFiller::SFastActiveEdge temp(leftActiveEdge);

   178 	leftActiveEdge=rightActiveEdge;

   179 	rightActiveEdge=temp;

   180 

   181 	if (leftActiveEdge.scanLineIntersectionPtr!=NULL)

   182 		leftActiveEdge.scanLineIntersectionPtr->activeEdgePtr=&leftActiveEdge;

   183 	if (rightActiveEdge.scanLineIntersectionPtr!=NULL)

   184 		rightActiveEdge.scanLineIntersectionPtr->activeEdgePtr=&rightActiveEdge;

   185 	}

   186 

   187 /**

   188 A utility class used to sort intersection lists based on the position of their first pixel.

   189 @see CSwDirectGdiPolygonFiller

   190 @see TKey

   191 

   192 @internalComponent

   193 */

   194 NONSHARABLE_CLASS(TCompareScanLineIntersectionsFirstPixel) : public TKey

   195 	{

   196 public:

   197 	TCompareScanLineIntersectionsFirstPixel(const CSwDirectGdiPolygonFiller::SFastData& aFastData);

   198 private:

   199 	virtual TInt Compare(TInt aLeft,TInt aRight) const;

   200 private:

   201 	const CSwDirectGdiPolygonFiller::SFastData& iFastData;

   202 	};

   203 

   204 TCompareScanLineIntersectionsFirstPixel::TCompareScanLineIntersectionsFirstPixel(const CSwDirectGdiPolygonFiller::SFastData& aFastData):

   205 	iFastData(aFastData)

   206 	{

   207 	}

   208 

   209 /**

   210 Compare intersections based on the order of their first pixel.

   211 

   212 @param aLeft Index corresponding to the "left" side of the comparison. 

   213 @param aRight Index corresponding to the "right" side of the comparison.

   214 

   215 @return Zero, if the two keys are equal; negative, if the left key is less than the right key; positive, if the left key is greater than the right key.

   216 

   217 @see TKey::Compare

   218 */

   219 TInt TCompareScanLineIntersectionsFirstPixel::Compare(TInt aLeft,TInt aRight) const

   220 	{

   221 	const TInt leftFirstPixel=iFastData.scanLineIntersectionList[aLeft].firstPixel;

   222 	const TInt rightFirstPixel=iFastData.scanLineIntersectionList[aRight].firstPixel;

   223 	if (leftFirstPixel<rightFirstPixel)

   224 		return -1;

   225 	if (leftFirstPixel>rightFirstPixel)

   226 		return 1;

   227 	return 0;

   228 	}

   229 

   230 /**

   231 A utility class used to swap entries in intersection list arrays during sort operations.

   232 @see CSwDirectGdiPolygonFiller

   233 @see TSwap

   234 

   235 @internalComponent

   236 */

   237 NONSHARABLE_CLASS(TSwapScanLineIntersections) : public TSwap

   238 	{

   239 public:

   240 	TSwapScanLineIntersections(CSwDirectGdiPolygonFiller::SFastData& aFastData);

   241 private:

   242 	virtual void Swap(TInt aLeft,TInt aRight) const;

   243 private:

   244 	CSwDirectGdiPolygonFiller::SFastData& iFastData;

   245 	};

   246 

   247 TSwapScanLineIntersections::TSwapScanLineIntersections(CSwDirectGdiPolygonFiller::SFastData& aFastData):

   248 	iFastData(aFastData)

   249 	{

   250 	}

   251 

   252 /**

   253 Swaps two elements of a scanLineIntersectionList array. 

   254 @param aLeft The index of an array element participating in the swap. 

   255 @param aRight The index of an array element participating in the swap.

   256 @see TSwap::Swap

   257 */

   258 void TSwapScanLineIntersections::Swap(TInt aLeft,TInt aRight) const

   259 	{

   260 	CSwDirectGdiPolygonFiller::SFastScanLineIntersection& leftScanLineIntersection=iFastData.scanLineIntersectionList[aLeft];

   261 	CSwDirectGdiPolygonFiller::SFastScanLineIntersection& rightScanLineIntersection=iFastData.scanLineIntersectionList[aRight];

   262 

   263 	const CSwDirectGdiPolygonFiller::SFastScanLineIntersection temp(leftScanLineIntersection);

   264 	leftScanLineIntersection=rightScanLineIntersection;

   265 	rightScanLineIntersection=temp;

   266 

   267 	leftScanLineIntersection.activeEdgePtr->scanLineIntersectionPtr=&leftScanLineIntersection;

   268 	rightScanLineIntersection.activeEdgePtr->scanLineIntersectionPtr=&rightScanLineIntersection;

   269 	}

   270 

   271 /**

   272 Sorts array elements

   273 

   274 @param aCount The number of elements in the array.

   275 @param aKey A reference to a suitably initialised TKey derived object.

   276 @param aSwap A reference to a suitably initialised TSwap derived object.

   277 @panic DGDIAdapter 1015, if QuickSort failed.

   278 

   279 @internalComponent

   280 */

   281 LOCAL_C void Sort(TInt aCount,const TKey& aKey,const TSwap& aSwap)

   282 	{

   283 #if 1 // quick sort

   284 	const TInt error=User::QuickSort(aCount,aKey,aSwap);

   285 	GRAPHICS_ASSERT_ALWAYS(error==KErrNone, EDirectGdiPanicPolygonFiller);

   286 #elif 0 // bubble sort

   287 	for (TInt i=1; i<aCount; ++i)

   288 		{

   289 		for (TInt j=i; j>0; --j)

   290 			{

   291 			if (aKey.Compare(j-1,j)>0)

   292 				{

   293 				aSwap.Swap(j-1,j);

   294 				}

   295 			}

   296 		}

   297 #else // heap sort

   298 	TInt startOfSortedPortion=aCount;

   299 	if (startOfSortedPortion>1)

   300 		{

   301 		TInt startOfHeap=startOfSortedPortion>>1;

   302 		FOREVER

   303 			{

   304 			GRAPHICS_ASSERT_DEBUG(startOfHeap>=0, EDirectGdiPanicPolygonFiller);

   305 			if (startOfHeap!=0)

   306 				{

   307 				--startOfHeap;

   308 				}

   309 			else

   310 				{

   311 				--startOfSortedPortion;

   312 				aSwap.Swap(startOfSortedPortion,0);

   313 				GRAPHICS_ASSERT_DEBUG(startOfSortedPortion>=1, EDirectGdiPanicPolygonFiller);

   314 				if (startOfSortedPortion==1)

   315 					{

   316 					break;

   317 					}

   318 				}

   319 			// put aArray[startOfHeap] into the correct place in the heap

   320 			TInt i=startOfHeap;

   321 			FOREVER

   322 				{

   323 				TInt j=(i+1)<<1;

   324 				if ((j>=startOfSortedPortion) || (aKey.Compare(j-1,j)>0))

   325 					{

   326 					--j;

   327 					}

   328 				if ((j>=startOfSortedPortion) || (aKey.Compare(i,j)>=0))

   329 					{

   330 					break;

   331 					}

   332 				aSwap.Swap(i,j);

   333 				i=j;

   334 				}

   335 			}

   336 		}

   337 #endif

   338 #if defined(_DEBUG)

   339 	{

   340 	for (TInt i=1; i<aCount; ++i)

   341 		{

   342 		GRAPHICS_ASSERT_DEBUG(aKey.Compare(i-1,i)<=0, EDirectGdiPanicPolygonFiller);

   343 		}

   344 	}

   345 #endif

   346 	}

   347 

   348 /*

   349  CSwDirectGdiPolygonFiller

   350  */

   351  

   352 /**

   353  Constructor which initialises all member data to zero, EFalse or null for 

   354  TInt, TBool pointers respectively.

   355  */

   356 CSwDirectGdiPolygonFiller::CSwDirectGdiPolygonFiller():

   357 	CBase(),

   358 	iPointArray(NULL),

   359 	iFillRule(DirectGdi::EAlternate),

   360 	iUseFastAlgorithm(EFalse),

   361 	iNumVertexes(0),

   362 	iToggler(EFalse),

   363 	iNestingLevel(0),

   364 	iScanLineIntersection(0),

   365 	iRightMostPixelOnScanLine(0),

   366 	iFirstVertex(0),

   367 	iPolygonIsAllHorizontal(EFalse),

   368 	iFirstScanLine(0),

   369 	iLastScanLine(0),

   370 	iCurrentScanLine(0)

   371 	{

   372 	iFastData.vertexList=NULL;

   373 	iFastData.edgeList=NULL;

   374 	iFastData.activeEdgeList=NULL;

   375 	iFastData.scanLineIntersectionList=NULL;

   376 	iFastData.numActiveEdges=0;

   377 	iFastData.numScanLineIntersections=0;

   378 	iFastData.nextEdgeToActivate=0;

   379 	iSlowData.numIntersectionsWithSameFirstPixelPreviouslyMet=0;

   380 	iSlowData.numIntersectionsWithSameFirstPixelMetThisTime=0;

   381 	iSlowData.numScanLineIntersections=0;

   382 	iSlowData.scanLineComplete=EFalse;

   383 	iSlowData.firstPixelOfLastIntersectionInPrevBuffer=0;

   384 	}

   385 

   386 /**

   387 Destructor calls reset on the polygon.

   388 */

   389 CSwDirectGdiPolygonFiller::~CSwDirectGdiPolygonFiller()

   390 	{

   391 	Reset();

   392 	}

   393 

   394 /**

   395 An overloaded version of Construct which allows the list of points to be passed in as a point array.

   396 Exactly the same behaviour and structure as above. This should not fail. This method does not require the 

   397 number of nodes to be given as a parameter.

   398 

   399 @param aPointArray A pointer to point array, as opposed to a pointer to a point list.

   400 @param aFillRule How filling should be achieved, as described by a DirectGdi::TFillRule object.

   401 @param aUsage How the polygon should be used.

   402 @panic DGDIAdapter 1015, if aPointArray is NULL.

   403 */

   404 void CSwDirectGdiPolygonFiller::Construct(const TArray<TPoint>* aPointArray, 

   405 										DirectGdi::TFillRule aFillRule, TUsage aUsage)

   406 	{

   407 	GRAPHICS_ASSERT_ALWAYS(aPointArray!=NULL,EDirectGdiPanicPolygonFiller);

   408 	iPointArray=aPointArray;

   409 	iNumVertexes=iPointArray->Count();

   410 	Construct(aFillRule,aUsage);

   411 	}

   412 

   413 /**

   414 Builds up the internal meta-data needed to fill the polygon.

   415 

   416 @param aFillRule How filling should be achieved, as described by a DirectGdi::TFillRule object.

   417 @param aUsage How the polygon should be used, see TUsage enumeration.

   418 @panic DGDIAdapter 1015, if aFillRule is invalid, or aUsage is invalid. 

   419 */

   420 void CSwDirectGdiPolygonFiller::Construct(DirectGdi::TFillRule aFillRule, TUsage aUsage)

   421 	{

   422 	GRAPHICS_ASSERT_ALWAYS((aFillRule==DirectGdi::EAlternate) || (aFillRule==DirectGdi::EWinding),

   423 																					EDirectGdiPanicPolygonFiller);

   424 	GRAPHICS_ASSERT_ALWAYS((aUsage==EGetAllPixelRunsSequentially) || (aUsage==EGetPixelRunsSequentiallyForSpecifiedScanLines),

   425 																					EDirectGdiPanicPolygonFiller);

   426 	TInt i, j;

   427 	iFillRule=aFillRule;

   428 	iUseFastAlgorithm=(aUsage==EGetAllPixelRunsSequentially);

   429 	iToggler=EFalse;

   430 	iNestingLevel=0;

   431 	iScanLineIntersection=0;

   432 	iRightMostPixelOnScanLine=KMinTInt;

   433 	// find the first vertex and see if the polygon is all horizontal

   434 	iFirstVertex=0; // dummy default value

   435 	iPolygonIsAllHorizontal=ETrue;

   436 

   437 	for (i=0; i<iNumVertexes; ++i)

   438 		if (Point(i).iY!=Point((i+1)%iNumVertexes).iY)

   439 			{

   440 			// i is now set to the vertex before the first non-horizontal edge

   441 

   442 			// set j%iNumVertexes to the vertex before the next non-horizontal edge

   443 			for (j=i+1; Point(j%iNumVertexes).iY==Point((j+1)%iNumVertexes).iY; ++j)

   444 				;

   445 			j%=iNumVertexes;

   446 			TInt first=Point(i).iY;

   447 			TInt middle=Point(j).iY;

   448 			TInt last=Point((j+1)%iNumVertexes).iY;

   449 

   450 			// if vertex j is a max or min point, set the first-vertex to be j

   451 			if ((middle<first)==(middle<last))

   452 				{

   453 				iFirstVertex=j;

   454 				iPolygonIsAllHorizontal=EFalse;

   455 				break;

   456 				}

   457 			}

   458 

   459 	if (iUseFastAlgorithm)

   460 		{

   461 		iFastData.vertexList=(TPoint*)User::Alloc(sizeof(TPoint)*iNumVertexes);

   462 		iFastData.edgeList=(SFastEdge*)User::Alloc(sizeof(SFastEdge)*iNumVertexes);

   463 		iFastData.activeEdgeList=(SFastActiveEdge*)User::Alloc(sizeof(SFastActiveEdge)*iNumVertexes);

   464 		iFastData.scanLineIntersectionList=(SFastScanLineIntersection*)User::Alloc(sizeof(SFastScanLineIntersection)*iNumVertexes);

   465 		if ((iFastData.vertexList==NULL) ||

   466 			(iFastData.edgeList==NULL) ||

   467 			(iFastData.activeEdgeList==NULL) ||

   468 			(iFastData.scanLineIntersectionList==NULL))

   469 			{

   470 			Reset(); // sets iUseFastAlgorithm to EFalse among other things

   471 			}

   472 		}

   473 	

   474 	if (iUseFastAlgorithm)

   475 		{

   476 		for(TInt vertexcount=0;vertexcount<iNumVertexes;vertexcount++)

   477 			new(&iFastData.activeEdgeList[vertexcount]) SFastActiveEdge;

   478 		iFastData.numActiveEdges=0;

   479 		iFastData.numScanLineIntersections=0;

   480 		iFastData.nextEdgeToActivate=0;

   481 

   482 		// put the points into the vertex-list

   483 		// N.B. this array is used for speed since CArrayXxxs are slower for indexing into than built-in arrays

   484 		for (i=0; i<iNumVertexes; ++i)

   485 			{

   486 			// If iFastData.vertexList is NULL this will never be run. iFastData.vertexList is checked 

   487 			// above after which iUseFastAlgorithm is set to EFalse if it is NULL (in Reset())

   488 			// coverity[var_deref_op]

   489 			iFastData.vertexList[i]=Point((i+iFirstVertex)%iNumVertexes);

   490 			}

   491 

   492 		// create edge-list

   493 		for (i=0; i<iNumVertexes; ++i)

   494 			{

   495 			// See preceding coverity comment

   496 			// coverity[var_deref_op]

   497 			if (iFastData.vertexList[i].iY<iFastData.vertexList[(i+1)%iNumVertexes].iY)

   498 				{

   499 				iFastData.edgeList[i].upperVertex=i;

   500 				iFastData.edgeList[i].lowerVertex=(i+1)%iNumVertexes;

   501 				}

   502 			else

   503 				{

   504 				iFastData.edgeList[i].upperVertex=(i+1)%iNumVertexes;

   505 				iFastData.edgeList[i].lowerVertex=i;

   506 				}

   507 			iFastData.edgeList[i].firstVertex=i;

   508 			}

   509 

   510 		// sort edge-list into order of increasing upper y-position

   511 		Sort(iNumVertexes,TCompareEdgesUpperY(iFastData),TSwapEdges(iFastData));

   512 

   513 		// find the first scan-line

   514 		iFirstScanLine=iFastData.vertexList[iFastData.edgeList[0].upperVertex].iY;

   515 

   516 		// find the last scan-line

   517 		iLastScanLine=iFirstScanLine;

   518 		for (i=0; i<iNumVertexes; ++i)

   519 			if (iLastScanLine<iFastData.vertexList[i].iY)

   520 				iLastScanLine=iFastData.vertexList[i].iY;

   521 		}

   522 	else

   523 		{

   524 		iSlowData.numIntersectionsWithSameFirstPixelPreviouslyMet=0;

   525 		iSlowData.scanLineComplete=EFalse;

   526 		iSlowData.firstPixelOfLastIntersectionInPrevBuffer=KMinTInt;

   527 

   528 		// find the first and last scan-lines

   529 		iFirstScanLine=KMaxTInt;

   530 		iLastScanLine=KMinTInt;

   531 		for (i=0; i<iNumVertexes; ++i)

   532 			{

   533 			TInt y=Point(i).iY;

   534 			if (iFirstScanLine>y)

   535 				iFirstScanLine=y;

   536 			if (iLastScanLine<y)

   537 				iLastScanLine=y;

   538 			}

   539 		}

   540 

   541 	iCurrentScanLine=iFirstScanLine;

   542 	}

   543 

   544 /**

   545 Frees any data held in the polygon’s lists of edges, vertexes and scan lines, and sets these values to NULL.

   546 It also has the feature of setting iUseFastAlgorithm = EFalse.

   547 */

   548 void CSwDirectGdiPolygonFiller::Reset()

   549 	{

   550 	if(iUseFastAlgorithm)

   551 		{

   552 		if(iFastData.vertexList)

   553 			{

   554 			User::Free(iFastData.vertexList);

   555 			iFastData.vertexList=NULL;

   556 			}

   557 		if(iFastData.edgeList)

   558 			{

   559 			User::Free(iFastData.edgeList);

   560 			iFastData.edgeList=NULL;

   561 			}

   562 		if(iFastData.activeEdgeList)

   563 			{

   564 			User::Free(iFastData.activeEdgeList);

   565 			iFastData.activeEdgeList=NULL;

   566 			}

   567 		if(iFastData.scanLineIntersectionList)

   568 			{

   569 			User::Free(iFastData.scanLineIntersectionList);

   570 			iFastData.scanLineIntersectionList=NULL;

   571 			}

   572 		iUseFastAlgorithm=EFalse;

   573 		}

   574 	}

   575 

   576 /**

   577 Method is used to calculate the locations of vertex interactions between the polygon and scan lines. 

   578 An initial scan line is required. It calculates the start and end positions on the line. The method

   579 can use either the fast or slow polygon algorithm depending upon the state of aUsage. Polygon filling

   580 is also addressed by this method.

   581 

   582 @param aExists Will be set to EFalse if a polygon with no vertexes is passed in, otherwise ETrue on return.

   583 @param aScanLine On return will contain iScanline at the beginning of the operation.

   584 @param aStart On return, contains the position on the scan line to start the run.

   585 @param aEnd On return, contains the position on the scan line to end the run.

   586 @panic DGDIAdapter 1015 (debug only)

   587 */

   588 void CSwDirectGdiPolygonFiller::GetNextPixelRun(TBool& aExists, TInt& aScanLine, TInt& aStart, 

   589 											  TInt& aEnd)

   590 	{

   591 	if (iCurrentScanLine>iLastScanLine)

   592 		{

   593 		aExists=EFalse;

   594 		return;

   595 		}

   596 

   597 	aExists=ETrue;

   598 	aScanLine=iCurrentScanLine;

   599 

   600 	if (iPolygonIsAllHorizontal)

   601 		{

   602 		// set the start after the end

   603 		aStart=KMinTInt+1;

   604 		aEnd=KMinTInt;

   605 		++iCurrentScanLine;

   606 		return;

   607 		}

   608 

   609 	if (iUseFastAlgorithm)

   610 		{

   611 		TInt i, j;

   612 

   613 		if (iScanLineIntersection==0)

   614 			{

   615 			// add any new edges to the active-edge-list

   616 			for (; (iFastData.nextEdgeToActivate<iNumVertexes) &&

   617 					(iFastData.vertexList[iFastData.edgeList[iFastData.nextEdgeToActivate].upperVertex].iY==iCurrentScanLine);

   618 					++iFastData.numActiveEdges, ++iFastData.nextEdgeToActivate)

   619 				{

   620 				iFastData.activeEdgeList[iFastData.numActiveEdges].edgePtr=&iFastData.edgeList[iFastData.nextEdgeToActivate];

   621 				iFastData.activeEdgeList[iFastData.numActiveEdges].lineGenerator.Construct(

   622 														iFastData.vertexList[iFastData.edgeList[iFastData.nextEdgeToActivate].upperVertex],

   623 														iFastData.vertexList[iFastData.edgeList[iFastData.nextEdgeToActivate].lowerVertex]);

   624 				iFastData.activeEdgeList[iFastData.numActiveEdges].scanLineIntersectionPtr=NULL;

   625 				}

   626 

   627 			// sort the active-edge-list into order of adjacent edges (if possible)

   628 			Sort(iFastData.numActiveEdges,TCompareActiveEdgesFirstVertex(iFastData),TSwapActiveEdges(iFastData));

   629 

   630 			// find the intersection of each active-edge with the current scan-line

   631 			// for max/min vertex-runs (e.g. \/, \_/, \__/, etc.) add 2 intersections for each run

   632 			// for other vertex-runs (e.g. /----/) add 1 intersection for each run

   633 			for (i=0; i<iFastData.numActiveEdges; ++i)

   634 				{

   635 				// check that active-edge i is not horizontal

   636 				GRAPHICS_ASSERT_DEBUG(iFastData.vertexList[iFastData.activeEdgeList[i].edgePtr->upperVertex].iY!=

   637 							   iFastData.vertexList[iFastData.activeEdgeList[i].edgePtr->lowerVertex].iY, EDirectGdiPanicPolygonFiller);

   638 

   639 				if (iFastData.vertexList[iFastData.activeEdgeList[i].edgePtr->upperVertex].iY==iCurrentScanLine)

   640 					// the scan-line is intersecting active-edge i at its upper-vertex

   641 					FastHandleVertexIntersection(i, EFalse);

   642 				else if (iFastData.vertexList[iFastData.activeEdgeList[i].edgePtr->lowerVertex].iY==iCurrentScanLine)

   643 					// the scan-line is intersecting active-edge i at its lower-vertex

   644 					FastHandleVertexIntersection(i, ETrue);

   645 				else

   646 					// the scan-line is intersecting active-edge i at neither of its vertexes

   647 					SetFastIntersection(iFastData.activeEdgeList[i],*iFastData.activeEdgeList[i].scanLineIntersectionPtr);

   648 				}

   649 

   650 			// N.B. iFastData.numScanLineIntersections is less than or equal to iFastData.numActiveEdges

   651 

   652 			// sort the intersection-list into increasing order of first-pixel

   653 			Sort(iFastData.numScanLineIntersections,TCompareScanLineIntersectionsFirstPixel(iFastData),TSwapScanLineIntersections(iFastData));

   654 

   655 			GRAPHICS_ASSERT_DEBUG(iFastData.numScanLineIntersections>=2, EDirectGdiPanicPolygonFiller);

   656 			}

   657 

   658 		// depending on the rule used, find the pixel-run

   659 		TBool doFill=EFalse; // dummy initialization to prevent compiler warning

   660 		if (iScanLineIntersection<iFastData.numScanLineIntersections-1)

   661 			{

   662 			switch (iFillRule)

   663 				{

   664 			case DirectGdi::EAlternate:

   665 				iToggler=!iToggler;

   666 				doFill=iToggler;

   667 				break;

   668 			case DirectGdi::EWinding:

   669 					GRAPHICS_ASSERT_DEBUG(iFastData.vertexList[iFastData.scanLineIntersectionList[iScanLineIntersection].activeEdgePtr->edgePtr->lowerVertex].iY!=

   670 								   iFastData.vertexList[iFastData.scanLineIntersectionList[iScanLineIntersection].activeEdgePtr->edgePtr->upperVertex].iY,

   671 																										EDirectGdiPanicPolygonFiller);

   672 

   673 					if (iFastData.scanLineIntersectionList[iScanLineIntersection].activeEdgePtr->edgePtr->lowerVertex==

   674 						(iFastData.scanLineIntersectionList[iScanLineIntersection].activeEdgePtr->edgePtr->upperVertex+1)%iNumVertexes)

   675 						++iNestingLevel;

   676 					else

   677 						--iNestingLevel;

   678 

   679 				doFill=(iNestingLevel!=0);

   680 				break;

   681 				}

   682 

   683 			if (doFill)

   684 				{

   685 				aStart=Max(iRightMostPixelOnScanLine, iFastData.scanLineIntersectionList[iScanLineIntersection].lastPixel)+1;

   686 				aEnd=iFastData.scanLineIntersectionList[iScanLineIntersection+1].firstPixel-1;

   687 				}

   688 			else

   689 				{

   690 				// set the start after the end

   691 				aStart=KMinTInt+1;

   692 				aEnd=KMinTInt;

   693 				}

   694 

   695 			if (iRightMostPixelOnScanLine<iFastData.scanLineIntersectionList[iScanLineIntersection].lastPixel)

   696 				iRightMostPixelOnScanLine=iFastData.scanLineIntersectionList[iScanLineIntersection].lastPixel;

   697 			++iScanLineIntersection;

   698 			}

   699 

   700 		if (iScanLineIntersection==iFastData.numScanLineIntersections-1)

   701 			{

   702 			GRAPHICS_ASSERT_DEBUG(iFastData.vertexList[iFastData.scanLineIntersectionList[iScanLineIntersection].activeEdgePtr->edgePtr->lowerVertex].iY!=

   703 						   iFastData.vertexList[iFastData.scanLineIntersectionList[iScanLineIntersection].activeEdgePtr->edgePtr->upperVertex].iY,

   704 																											EDirectGdiPanicPolygonFiller);

   705 

   706 			switch (iFillRule)

   707 				{

   708 			case DirectGdi::EAlternate:

   709 				iToggler=!iToggler;

   710 				GRAPHICS_ASSERT_DEBUG(iToggler==0, EDirectGdiPanicPolygonFiller);

   711 				break;

   712 			case DirectGdi::EWinding:

   713 				if (iFastData.scanLineIntersectionList[iScanLineIntersection].activeEdgePtr->edgePtr->lowerVertex==

   714 					(iFastData.scanLineIntersectionList[iScanLineIntersection].activeEdgePtr->edgePtr->upperVertex+1)%iNumVertexes)

   715 					++iNestingLevel;

   716 				else

   717 					--iNestingLevel;

   718 				GRAPHICS_ASSERT_DEBUG((iNumVertexes==2) || (iNestingLevel==0), EDirectGdiPanicPolygonFiller);

   719 				break;

   720 				}

   721 

   722 			// remove any scan-line-intersections associated with old active-edges

   723 			for (i=0; i<iFastData.numScanLineIntersections; )

   724 				if (iFastData.vertexList[iFastData.scanLineIntersectionList[i].activeEdgePtr->edgePtr->lowerVertex].iY==iCurrentScanLine)

   725 					{

   726 					iFastData.scanLineIntersectionList[i].activeEdgePtr->scanLineIntersectionPtr=NULL;

   727 

   728 					// ripple all the entries in the scan-line-intersection-list after this one back one place

   729 					for (j=i+1; j<iFastData.numScanLineIntersections; ++j)

   730 						{

   731 						iFastData.scanLineIntersectionList[j-1]=iFastData.scanLineIntersectionList[j];

   732 						iFastData.scanLineIntersectionList[j-1].activeEdgePtr->scanLineIntersectionPtr=&iFastData.scanLineIntersectionList[j-1];

   733 						}

   734 

   735 					iFastData.scanLineIntersectionList[j-1].activeEdgePtr=NULL;

   736 					--iFastData.numScanLineIntersections;

   737 					}

   738 				else

   739 					++i;

   740 

   741 			// remove any old edges from the active-edge-list

   742 			for (i=0; i<iFastData.numActiveEdges; )

   743 				if (iFastData.vertexList[iFastData.activeEdgeList[i].edgePtr->lowerVertex].iY==iCurrentScanLine)

   744 					{

   745 					GRAPHICS_ASSERT_DEBUG(iFastData.activeEdgeList[i].scanLineIntersectionPtr==NULL, EDirectGdiPanicPolygonFiller);

   746 

   747 					// ripple all the entries in the active-edge-list after this one back one place

   748 					for (j=i+1; j<iFastData.numActiveEdges; ++j)

   749 						{

   750 						iFastData.activeEdgeList[j-1]=iFastData.activeEdgeList[j];

   751 						if (iFastData.activeEdgeList[j-1].scanLineIntersectionPtr)

   752 							iFastData.activeEdgeList[j-1].scanLineIntersectionPtr->activeEdgePtr=&iFastData.activeEdgeList[j-1];

   753 						}

   754 

   755 					iFastData.activeEdgeList[j-1].scanLineIntersectionPtr=NULL;

   756 					--iFastData.numActiveEdges;

   757 					}

   758 				else

   759 					++i;

   760 

   761 #if defined(_DEBUG)

   762 			for (i=0; i<iFastData.numActiveEdges; ++i)

   763 				{

   764 				GRAPHICS_ASSERT_DEBUG(iFastData.activeEdgeList[i].scanLineIntersectionPtr->activeEdgePtr==

   765 								&iFastData.activeEdgeList[i], EDirectGdiPanicPolygonFiller);

   766 				}

   767 

   768 			for (i=0; i<iFastData.numScanLineIntersections; ++i)

   769 				{

   770 				GRAPHICS_ASSERT_DEBUG(iFastData.scanLineIntersectionList[i].activeEdgePtr->scanLineIntersectionPtr==

   771 								&iFastData.scanLineIntersectionList[i], EDirectGdiPanicPolygonFiller);

   772 				}

   773 #endif

   774 

   775 			iScanLineIntersection=0;

   776 			++iCurrentScanLine;

   777 			iRightMostPixelOnScanLine=KMinTInt;

   778 			}

   779 		}

   780 	else

   781 		{

   782 		GetNextPixelRunOnSpecifiedScanLine(aExists, iCurrentScanLine, aStart, aEnd);

   783 		if (!aExists)

   784 			GetNextPixelRunOnSpecifiedScanLine(aExists, ++iCurrentScanLine, aStart, aEnd);

   785 		}

   786 	}

   787 

   788 /**

   789 Similar to GetNextPixelRun(aExists, aScanLine, aStart, aEnd) this method is used to draw the relevant 

   790 vertex intersections for a polygon but only for an individual specified scan line. The method

   791 can use either the fast or slow polygon algorithm depending upon the state of aUsage.

   792 

   793 @param aExists Will be set to false if the line does not pass through the polygon or if

   794 a polygon with no vertexes is specified, otherwise ETrue on return.

   795 @param aScanLine The scan line to be drawn on. Used to set iScanline

   796 @param aStart On return, contains the position on the scan line to start the run.

   797 @param aEnd The position on the scan line to end the run, returned.

   798 @panic DGDIAdapter 1015, if iUseFastAlgorithm is ETrue (debug only).

   799 */

   800 void CSwDirectGdiPolygonFiller::GetNextPixelRunOnSpecifiedScanLine(TBool& aExists, 

   801 																 TInt aScanLine, 

   802 																 TInt& aStart, 

   803 																 TInt& aEnd)

   804 	{

   805 	TInt i, j, k;

   806 

   807 	GRAPHICS_ASSERT_DEBUG(!iUseFastAlgorithm, EDirectGdiPanicPolygonFiller);

   808 

   809 	if (aScanLine<iCurrentScanLine || aScanLine>iLastScanLine)

   810 		{

   811 		aExists=EFalse;

   812 		return;

   813 		}

   814 

   815 	aExists=ETrue;

   816 	iCurrentScanLine=aScanLine;

   817 

   818 	if (iPolygonIsAllHorizontal)

   819 		{

   820 		// set the start after the end

   821 		aStart=KMinTInt+1;

   822 		aEnd=KMinTInt;

   823 		++iCurrentScanLine;

   824 		return;

   825 		}

   826 

   827 	if (iScanLineIntersection==0)

   828 		{

   829 		iSlowData.numIntersectionsWithSameFirstPixelMetThisTime=0;

   830 		iSlowData.numScanLineIntersections=0;

   831 		iSlowData.scanLineComplete=ETrue;

   832 

   833 		// find the left-most iSlowData::EStoreSize number (or less) of intersections with this scan-line

   834 		for (i=iFirstVertex; i<iNumVertexes+iFirstVertex; ++i)

   835 			{

   836 			TPoint upper=Point(i%iNumVertexes);

   837 			TPoint lower=Point((i+1)%iNumVertexes);

   838 			if (upper.iY>lower.iY)

   839 				{

   840 				TPoint temp=upper;

   841 				upper=lower;

   842 				lower=temp;

   843 				}

   844 

   845 			if ((iCurrentScanLine>=upper.iY) && (iCurrentScanLine<=lower.iY))

   846 				{

   847 				// check that the edge starting at vertex i%iNumVertexes is not horizontal

   848 				GRAPHICS_ASSERT_DEBUG(upper.iY!=lower.iY, EDirectGdiPanicPolygonFiller);

   849 

   850 				// step through the line-generator until the current scan-line is reached

   851 				TPoint startPos, endPos;

   852 				JumpToCurrentScanLine(iSlowData.lineGenerator, upper, lower, startPos, endPos);

   853 

   854 				// find the intersection start and end pixels

   855 				SSlowScanLineIntersection scanLineIntersection;

   856 				scanLineIntersection.firstPixel=Min(startPos.iX, endPos.iX);

   857 				scanLineIntersection.lastPixel=Max(startPos.iX, endPos.iX);

   858 				scanLineIntersection.firstVertexOfEdge=i%iNumVertexes;

   859 

   860 				// handle horizontal runs and minima/maxima

   861 				if (upper.iY==iCurrentScanLine)

   862 					SlowHandleVertexIntersection(scanLineIntersection, i, EFalse);

   863 				else if (lower.iY==iCurrentScanLine)

   864 					SlowHandleVertexIntersection(scanLineIntersection, i, ETrue);

   865 

   866 				// see if there have been other intersections with the same first-pixel

   867 				if (scanLineIntersection.firstPixel==iSlowData.firstPixelOfLastIntersectionInPrevBuffer)

   868 					++iSlowData.numIntersectionsWithSameFirstPixelMetThisTime;

   869 

   870 				// if the intersection has not already been included in a previous buffer-load

   871 				if ((scanLineIntersection.firstPixel>iSlowData.firstPixelOfLastIntersectionInPrevBuffer) ||

   872 					((scanLineIntersection.firstPixel==iSlowData.firstPixelOfLastIntersectionInPrevBuffer) &&

   873 													(iSlowData.numIntersectionsWithSameFirstPixelMetThisTime>=

   874 													iSlowData.numIntersectionsWithSameFirstPixelPreviouslyMet)))

   875 					{

   876 					// put the intersection in the right place in the intersection list (if there is room)

   877 					for (j=0; j<iSlowData.numScanLineIntersections; ++j)

   878 						if (scanLineIntersection.firstPixel<iSlowData.scanLineIntersectionList[j].firstPixel)

   879 							{

   880 							if (iSlowData.numScanLineIntersections<SSlowData::EStoreSize)

   881 								++iSlowData.numScanLineIntersections;

   882 							else

   883 								iSlowData.scanLineComplete=EFalse;

   884 

   885 							for (k=iSlowData.numScanLineIntersections-1; k>j; --k)

   886 								iSlowData.scanLineIntersectionList[k]=iSlowData.scanLineIntersectionList[k-1];

   887 							iSlowData.scanLineIntersectionList[j]=scanLineIntersection;

   888 							break;

   889 							}

   890 					if (j==iSlowData.numScanLineIntersections)

   891 						{

   892 						if (iSlowData.numScanLineIntersections<SSlowData::EStoreSize)

   893 							iSlowData.scanLineIntersectionList[iSlowData.numScanLineIntersections++]=scanLineIntersection;

   894 						else

   895 							iSlowData.scanLineComplete=EFalse;

   896 						}

   897 					}

   898 				}

   899 			}

   900 

   901 		if (!iSlowData.scanLineComplete)

   902 			{

   903 			GRAPHICS_ASSERT_DEBUG(iSlowData.numScanLineIntersections==SSlowData::EStoreSize, EDirectGdiPanicPolygonFiller);

   904 

   905 			if (iSlowData.firstPixelOfLastIntersectionInPrevBuffer==iSlowData.scanLineIntersectionList[SSlowData::EStoreSize-1].firstPixel)

   906 				iSlowData.numIntersectionsWithSameFirstPixelPreviouslyMet+=SSlowData::EStoreSize-1;

   907 			else

   908 				{

   909 				iSlowData.firstPixelOfLastIntersectionInPrevBuffer=iSlowData.scanLineIntersectionList[SSlowData::EStoreSize-1].firstPixel;

   910 				iSlowData.numIntersectionsWithSameFirstPixelPreviouslyMet=1;

   911 				for (i=SSlowData::EStoreSize-1; (i>0) && (iSlowData.firstPixelOfLastIntersectionInPrevBuffer==

   912 															iSlowData.scanLineIntersectionList[i-1].firstPixel); --i)

   913 					++iSlowData.numIntersectionsWithSameFirstPixelPreviouslyMet;

   914 				}

   915 			}

   916 		}

   917 

   918 	// depending on the rule used, find the pixel-run

   919 	TBool doFill=EFalse; // dummy initialization to prevent compiler warning

   920 	if (iScanLineIntersection<iSlowData.numScanLineIntersections-1)

   921 		{

   922 		switch (iFillRule)

   923 			{

   924 		case DirectGdi::EAlternate:

   925 			iToggler=!iToggler;

   926 			doFill=iToggler;

   927 			break;

   928 		case DirectGdi::EWinding:

   929 				GRAPHICS_ASSERT_DEBUG(Point(iSlowData.scanLineIntersectionList[iScanLineIntersection].firstVertexOfEdge).iY!=

   930 							   Point((iSlowData.scanLineIntersectionList[iScanLineIntersection].firstVertexOfEdge+1)%iNumVertexes).iY,

   931 																										EDirectGdiPanicPolygonFiller);

   932 

   933 				if (Point(iSlowData.scanLineIntersectionList[iScanLineIntersection].firstVertexOfEdge).iY>

   934 					Point((iSlowData.scanLineIntersectionList[iScanLineIntersection].firstVertexOfEdge+1)%iNumVertexes).iY)

   935 					++iNestingLevel;

   936 				else

   937 					--iNestingLevel;

   938 

   939 			doFill=(iNestingLevel!=0);

   940 			break;

   941 			}

   942 

   943 		if (doFill)

   944 			{

   945 			aStart=Max(iRightMostPixelOnScanLine, iSlowData.scanLineIntersectionList[iScanLineIntersection].lastPixel)+1;

   946 			aEnd=iSlowData.scanLineIntersectionList[iScanLineIntersection+1].firstPixel-1;

   947 			}

   948 		else

   949 			{

   950 			// set the start after the end

   951 			aStart=KMinTInt+1;

   952 			aEnd=KMinTInt;

   953 			}

   954 

   955 		if (iRightMostPixelOnScanLine<iSlowData.scanLineIntersectionList[iScanLineIntersection].lastPixel)

   956 			iRightMostPixelOnScanLine=iSlowData.scanLineIntersectionList[iScanLineIntersection].lastPixel;

   957 		++iScanLineIntersection;

   958 		}

   959 

   960 	if (iScanLineIntersection==iSlowData.numScanLineIntersections-1)

   961 		{

   962 		if (iSlowData.scanLineComplete)

   963 			{

   964 			GRAPHICS_ASSERT_DEBUG(Point(iSlowData.scanLineIntersectionList[iScanLineIntersection].firstVertexOfEdge).iY!=

   965 						   Point((iSlowData.scanLineIntersectionList[iScanLineIntersection].firstVertexOfEdge+1)%iNumVertexes).iY,

   966 																											EDirectGdiPanicPolygonFiller);

   967 

   968 			switch (iFillRule)

   969 				{

   970 			case DirectGdi::EAlternate:

   971 				iToggler=!iToggler;

   972 				GRAPHICS_ASSERT_DEBUG(iToggler==0, EDirectGdiPanicPolygonFiller);

   973 				break;

   974 			case DirectGdi::EWinding:

   975 				if (Point(iSlowData.scanLineIntersectionList[iScanLineIntersection].firstVertexOfEdge).iY>

   976 					Point((iSlowData.scanLineIntersectionList[iScanLineIntersection].firstVertexOfEdge+1)%iNumVertexes).iY)

   977 					++iNestingLevel;

   978 				else

   979 					--iNestingLevel;

   980 

   981 				GRAPHICS_ASSERT_DEBUG((!iSlowData.scanLineComplete) || (iNumVertexes==2) || (iNestingLevel==0), EDirectGdiPanicPolygonFiller);

   982 				break;

   983 				}

   984 			}

   985 

   986 		iScanLineIntersection=0;

   987 		if (iSlowData.scanLineComplete)

   988 			{

   989 			++iCurrentScanLine;

   990 			iRightMostPixelOnScanLine=KMinTInt;

   991 			iSlowData.numIntersectionsWithSameFirstPixelPreviouslyMet=0;

   992 			iSlowData.scanLineComplete=EFalse;

   993 			iSlowData.firstPixelOfLastIntersectionInPrevBuffer=KMinTInt;

   994 			}

   995 		}

   996 	}

   997 

   998 /**

   999 Builds up drawing meta-data in the case where a scanline intersects the active edge at a vertex using

  1000 fast algorithms. 

  1001 

  1002 @param aCurrentActiveEdge Index of the current active edge

  1003 @param aIsLowerVertex If the vertex is the lower vertex ETrue otherwise EFalse.

  1004 @panic DGDIAdapter 1015, if iUseFastAlgorithm is EFalse.

  1005 

  1006 @see GetNextPixelRun()

  1007 */

  1008 void CSwDirectGdiPolygonFiller::FastHandleVertexIntersection(TInt& aCurrentActiveEdge, 

  1009 												  TBool aIsLowerVertex)

  1010 	{

  1011 	GRAPHICS_ASSERT_DEBUG(iUseFastAlgorithm, EDirectGdiPanicPolygonFiller);

  1012 

  1013 	if (iFastData.vertexList[(iFastData.activeEdgeList[aCurrentActiveEdge].edgePtr->firstVertex+1)%iNumVertexes].iY==iCurrentScanLine)

  1014 		// it is the second vertex of active-edge aCurrentActiveEdge that coincides with the current scan-line

  1015 		{

  1016 		TInt origActiveEdge=aCurrentActiveEdge;

  1017 		SFastScanLineIntersection scanLineIntersection;

  1018 		scanLineIntersection.activeEdgePtr=NULL;

  1019 		SetFastIntersection(iFastData.activeEdgeList[origActiveEdge], scanLineIntersection);

  1020 

  1021 		// walk through subsequent adjacent horizontal active-edges

  1022 		FOREVER

  1023 			{

  1024 			// exit the loop if the vertex-run *is* a maximum or a minimum

  1025 			const SFastEdge* tempEdgePtr=iFastData.activeEdgeList[(aCurrentActiveEdge+1)%iFastData.numActiveEdges].edgePtr;

  1026 			TBool isMaxOrMin = EFalse;

  1027 

  1028 			switch(aIsLowerVertex)

  1029 				{

  1030 				case EFalse:

  1031 					isMaxOrMin = (iFastData.vertexList[tempEdgePtr->lowerVertex].iY > iCurrentScanLine);

  1032 					break;

  1033 

  1034 				case ETrue:

  1035 					isMaxOrMin = (iFastData.vertexList[tempEdgePtr->upperVertex].iY < iCurrentScanLine);

  1036 					break;

  1037 				}

  1038 

  1039 			if (isMaxOrMin)

  1040  				// the vertex-run is a maximum or a minimum

  1041 				{

  1042 				if (aIsLowerVertex)

  1043 					{

  1044 					*iFastData.activeEdgeList[origActiveEdge].scanLineIntersectionPtr=scanLineIntersection;

  1045 					iFastData.activeEdgeList[origActiveEdge].scanLineIntersectionPtr->activeEdgePtr=&iFastData.activeEdgeList[origActiveEdge];

  1046 					}

  1047 				else

  1048 					{

  1049 					// add an intersection

  1050 					iFastData.scanLineIntersectionList[iFastData.numScanLineIntersections]=scanLineIntersection;

  1051 					iFastData.scanLineIntersectionList[iFastData.numScanLineIntersections].activeEdgePtr=&iFastData.activeEdgeList[origActiveEdge];

  1052 					iFastData.activeEdgeList[origActiveEdge].scanLineIntersectionPtr=&iFastData.scanLineIntersectionList[iFastData.numScanLineIntersections];

  1053 					++iFastData.numScanLineIntersections;

  1054 					}

  1055 				break;

  1056 				}

  1057 

  1058 			// the active-edge is horizontal, or the vertex-run is not a maximum or a minimum

  1059 

  1060 			++aCurrentActiveEdge;

  1061 			GRAPHICS_ASSERT_DEBUG(aCurrentActiveEdge<iFastData.numActiveEdges, EDirectGdiPanicPolygonFiller);

  1062 

  1063 			// update scanLineIntersection

  1064 			TPoint startPos, endPos;

  1065 			TInt minX, maxX;

  1066 			iFastData.activeEdgeList[aCurrentActiveEdge].lineGenerator.SingleScanline(startPos, endPos);

  1067 			minX=Min(startPos.iX, endPos.iX);

  1068 			maxX=Max(startPos.iX, endPos.iX);

  1069 			if (scanLineIntersection.firstPixel>minX)

  1070 				scanLineIntersection.firstPixel=minX;

  1071 			if (scanLineIntersection.lastPixel<maxX)

  1072 				scanLineIntersection.lastPixel=maxX;

  1073 

  1074 			// exit the loop if the vertex-run is *not* a maximum or a minimum

  1075 			tempEdgePtr=iFastData.activeEdgeList[aCurrentActiveEdge].edgePtr;

  1076 			TBool isNeitherMaxOrMin = EFalse;

  1077 

  1078 			switch(aIsLowerVertex)

  1079 				{

  1080 				case EFalse:

  1081 					isNeitherMaxOrMin = (iFastData.vertexList[tempEdgePtr->upperVertex].iY < iCurrentScanLine);

  1082 					break;

  1083 

  1084 				case ETrue:

  1085 					isNeitherMaxOrMin = (iFastData.vertexList[tempEdgePtr->lowerVertex].iY > iCurrentScanLine);

  1086 					break;

  1087 				}

  1088 

  1089  			// exit the loop if the vertex-run is *not* a maximum or a minimum

  1090 			if (isNeitherMaxOrMin)

  1091 				{

  1092 				TInt newActiveEdge;

  1093 				TInt oldActiveEdge;

  1094 				if (aIsLowerVertex)

  1095 					{

  1096 					newActiveEdge=aCurrentActiveEdge;

  1097 					oldActiveEdge=origActiveEdge;

  1098 					}

  1099 				else

  1100 					{

  1101 					newActiveEdge=origActiveEdge;

  1102 					oldActiveEdge=aCurrentActiveEdge;

  1103 					}

  1104 				iFastData.activeEdgeList[newActiveEdge].scanLineIntersectionPtr=iFastData.activeEdgeList[oldActiveEdge].scanLineIntersectionPtr;

  1105 				iFastData.activeEdgeList[oldActiveEdge].scanLineIntersectionPtr=NULL;

  1106 				*iFastData.activeEdgeList[newActiveEdge].scanLineIntersectionPtr=scanLineIntersection;

  1107 				iFastData.activeEdgeList[newActiveEdge].scanLineIntersectionPtr->activeEdgePtr=&iFastData.activeEdgeList[newActiveEdge];

  1108 				break;

  1109 				}

  1110 			}

  1111 		}

  1112 	else

  1113 		// it is the first vertex of active-edge aCurrentActiveEdge that coincides with the current scan-line

  1114 		{

  1115 #if defined(_DEBUG)

  1116 		// check that the vertex we are at is a maximum or a minimum

  1117 		TInt previousNotLevelVertex;

  1118 		TInt SFastEdge::*vertex=(aIsLowerVertex)? &SFastEdge::lowerVertex: &SFastEdge::upperVertex;

  1119 		for (previousNotLevelVertex=iFastData.activeEdgeList[aCurrentActiveEdge].edgePtr->*vertex;

  1120 								iFastData.vertexList[iFastData.activeEdgeList[aCurrentActiveEdge].edgePtr->*vertex].iY==iFastData.vertexList[previousNotLevelVertex].iY;

  1121 								previousNotLevelVertex=(previousNotLevelVertex+iNumVertexes-1)%iNumVertexes)

  1122 			;

  1123 		TInt nextNotLevelVertex=(iFastData.activeEdgeList[aCurrentActiveEdge].edgePtr->*vertex+1)%iNumVertexes;

  1124 		GRAPHICS_ASSERT_DEBUG((iFastData.vertexList[iFastData.activeEdgeList[aCurrentActiveEdge].edgePtr->*vertex].iY>iFastData.vertexList[previousNotLevelVertex].iY)==

  1125 					   (iFastData.vertexList[iFastData.activeEdgeList[aCurrentActiveEdge].edgePtr->*vertex].iY>iFastData.vertexList[nextNotLevelVertex].iY),

  1126 																						EDirectGdiPanicPolygonFiller);

  1127 #endif

  1128 

  1129 		if (aIsLowerVertex)

  1130 			SetFastIntersection(iFastData.activeEdgeList[aCurrentActiveEdge],*iFastData.activeEdgeList[aCurrentActiveEdge].scanLineIntersectionPtr);

  1131 		else

  1132 			{

  1133 			// add an intersection

  1134 			SetFastIntersection(iFastData.activeEdgeList[aCurrentActiveEdge], iFastData.scanLineIntersectionList[iFastData.numScanLineIntersections]);

  1135 			iFastData.scanLineIntersectionList[iFastData.numScanLineIntersections].activeEdgePtr=&iFastData.activeEdgeList[aCurrentActiveEdge];