seed1.c

nucleus 文件系统,内核和彩色图形系统,在小系统上非常好用

/*************************************************************************/
/*                                                                       */
/*         Copyright (c) 1997 - 1999 Accelerated Technology, Inc.        */
/*                                                                       */
/* PROPRIETARY RIGHTS of Accelerated Technology are involved in the      */
/* subject matter of this material.  All manufacturing, reproduction,    */
/* use, and sales rights pertaining to this subject matter are governed  */
/* by the license agreement.  The recipient of this software implicitly  */
/* accepts the terms of the license.                                     */
/*                                                                       */
/*************************************************************************/

/*************************************************************************/
/*                                                                       */
/* FILE NAME                                            VERSION          */
/*                                                                       */
/*      SEED1.c                                          1.9             */
/*                                                                       */
/* COMPONENT                                                             */
/*                                                                       */
/*      All                                                              */
/*                                                                       */
/* DESCRIPTION                                                           */
/*                                                                       */
/*      This file contains the FloodFill, BoundaryFill and several local */
/* functions.                                                            */
/*                                                                       */
/* AUTHOR                                                                */
/*                                                                       */
/*      Robert G. Burrill, Accelerated Technology, Inc.                  */
/*                                                                       */
/* DATA STRUCTURES                                                       */
/*                                                                       */
/*      None                                                             */
/*                                                                       */
/* FUNCTIONS                                                             */
/*                                                                       */
/*      None                                                             */
/*                                                                       */
/* DEPENDENCIES                                                          */
/*                                                                       */
/*      None                                                             */
/*                                                                       */
/* HISTORY                                                               */
/*                                                                       */
/*         NAME            DATE                    REMARKS               */
/*                                                                       */
/*         BobB          10/6/98     Corrected for max width and height  */
/*         BobB          10/22/99    Corrected the correction            */
/*         BobB          11/16/99    Got rid of ANSI compiler warnings   */
/*                                                                       */
/*************************************************************************/

#include "meta_wnd.h"
#include "metconst.h"    /* MetaWINDOW Constant & Stucture Definitions */
#include "metports.h"    /* MetaWINDOW Port & Bitmap Definitions */
#include "grafdata.h"
#include "metmacs3.h"


/* Module SEED1 is the seed fill (flood fill & boundary fill) code.

To speed up:

	1) When scanning to the end of a segment, could calculate max distance
	to the left or right limit edge and use that as a loop count, rather
	than performing a clip check after each pixel. */

#define MAX_RECTS	4
/* This is how many segments can be drawn with a single call to the filler.
Making this larger may improve performance a tad, but will steal space from
the segment list. Making it smaller will hurt performance a little. This is
just a compromise value, which I figure gets rid of up to 75% of the filler
overhead while using just 24 extra bytes from the memory pool. */

#define STACK_BUFFER_SIZE	0x0800

/* Structure for storing one scan line segment in a linked list.	*/
typedef struct _SBlock{
	struct _SBlock *NextBlock;	/* pointer to next block in list	*/
	long sXmin;					/* left end of segment				*/
	long sXmax;					/* right end of segment plus 1		*/
} SBlock;

/* common variables */
SBlock *FreeBlocks;	/* pointer to start of list of free blocks in the
					memory pool. 0 if no more blocks */
int (*Qualify)(void);	/* routine to call to determine if a pixel qualifies
					as fillable */
int SeedColor;		/* color to flood over */
int boundaryColor;	/* boundary color */
rect *LimitPtr;		/* pointer to limit rect */
int SeedX;			/* seed point X in global coordinates */
int ScanLine;		/* scan line currently being filled, in global
					coordinates */
int sDirection;		/* 1 or -1, to move down or up */
int ForwardLimit;	/* scan line at which to stop when  reached in current
					scanning direction (1 past last line to do) */
int BackwardLimit;	/* scan line at which to stop if current scanning
					direction is reversed (1 past last line to do) (becomes
					ForwardLimit if direction is reversed) */
SBlock *FLimitPtr;	/* pointer to segment list for filling that's already
					occurred on line before ForwardLimit, used to add any
					new segments when limit hit */
SBlock *BLimitPtr;	/* becomes FLimitPtr if direction is reversed */
int WorkingScanLine;	/* scan line currently being scanned */
int qualifyX;		/* X of point to qualify */
SBlock *TempListHead;	/* working pointer to SBlock that's head of segment
					list */
SBlock *CurrentSegmentList;	/* offset of sentinel for current segment list */
long (*GetPixelPrimitive)();	/* vector to GetPixel primitive for the
					destination bitmap */
void (*FillPrimitive)();	/* vector to Fill primitive for the destination
					bitmap */
rect lmtR;			/* fill limit rect (X-style) */
SBlock *StateStackPtr;	/* offset of state stack top */
rect *sRectPtr;		/* offset of current blitList entry to fill */
SBlock *pShadow;	/* pointer to current shadow segment list */
SBlock *Unallocated;	/* pointer to start of as-yet unallocated portion of
					memory pool */
SBlock *UnallocatedEnd;	/* pointer to last byte from which SBlocks can be
					allocated in memory pool */
blitRcd blitRecord;	/* working blit record */
byte *stkBufPtr;
long stkBufCtr;
short wXmin;
short localFeedX, localFeedY;
SBlock *blockPtr;
SBlock *blockPtrBE;
SBlock *blockPtrCE;
SBlock *blockPtrDN;
SBlock *blockPtrST;

/* local functions */
int Setup1(void);
int MatchSeedColor(void);
int NotMatchBoundaryColor(void);
void DoSeedFill(void);
int AllocBlock(void);
int ScanOutSegList(void);
int PushState(void);
int PopState(void);
void FreeList(void);

void FloodFill(int FSeedX, int FSeedY, rect *FLimit)
{

	LimitPtr = FLimit;	/* fill limit rectangle */

	/* set up limit rect, blitRcd, and primitive GetPixel and Fill vectors,
	convert the seed point to global coords, check that it's inside the limit
	rect, and return the seed point */
	localFeedX = FSeedX;
	localFeedY = FSeedY;
	if (Setup1() == 0) return; /* exit if seed point isn't within limit rect */

	/* get the seed pixel color */
	SeedColor = GetPixelPrimitive(localFeedX, localFeedY, blitRecord.blitDmap);

	/* reject if fill color is solid and matches seed color */
	if ((blitRecord.blitPat == 1) & (SeedColor == blitRecord.blitFore))
		return;
	if ((blitRecord.blitPat == 0) & (SeedColor == blitRecord.blitBack))
		return;

	Qualify = MatchSeedColor;	/* pixel is fillable if matches seed color */

	DoSeedFill();	/* same as boundary fill from now on */

	return;
}


void BoundaryFill(int BSeedX, int BSeedY, int BColor, rect *BLimit)
{
	int shfCnt;

	LimitPtr = BLimit;	/* fill limit rectangle */
	boundaryColor = BColor;	/* boundary color */

	/* set up limit rect, blitRcd, and primitive GetPixel and Fill vectors,
	convert the seed point to global coords, check that it's inside the limit
	rect, and return the seed point */
	localFeedX = BSeedX;
	localFeedY = BSeedY;
	if (Setup1() == 0) return; /* exit if seed point isn't within limit rect */

	/* no need to check for seed pixel fillability; that'll happen when we
	scan out the seed line */
	/* get modulus of boundary color and bitmap's max color index */
	if (blitRecord.blitDmap->pixPlanes == 1)
	{
		shfCnt = blitRecord.blitDmap->pixBits;
	}
	else
	{
		shfCnt = blitRecord.blitDmap->pixPlanes;
	}

	boundaryColor = BColor & ((1 << shfCnt) - 1);

	Qualify = NotMatchBoundaryColor;	/* pixel is fillable if it doesn't
										match the boundary color */
	DoSeedFill();	/* same as flood fill from now on */

	return;
}


void DoSeedFill(void)
{
	int i;
	short scanLineP1;
	short tempEdge;
	short grafErrValue;
	byte stackBuffer[STACK_BUFFER_SIZE];	/* working storage */
	
	/* decide which buffer to use, stack or memory pool */
	stkBufPtr = mpWorkSpace;	/* assume using general memory pool */
	stkBufCtr = (long) (mpWorkEnd - stkBufPtr);
	if (stkBufCtr <= STACK_BUFFER_SIZE)	/* is the memory pool smaller than */
	{									/*  the stack buffer? */
		stkBufCtr = STACK_BUFFER_SIZE;	/* set up to use the stack buffer */
		stkBufPtr = &stackBuffer[0];
	}

	blitRecord.blitList = (long) stkBufPtr;	/* point blitRcd to blitList area */
	sRectPtr = (rect *) ((long) stkBufPtr);	/* first rect goes right at the
							start now split up the pool; MAX_RECTS rects for
							blitList rects, the rest for SBlocks */
	Unallocated = (SBlock *) ((long)(sRectPtr + MAX_RECTS));
	UnallocatedEnd = (SBlock *) ((long)(Unallocated - 1) + stkBufCtr
		- MAX_RECTS * sizeof(rect));
	FreeBlocks = NULL;	/* empty the free block list to start */

	/* set up to jump into filling as if we've just scanned up from the
	line below the seed point */
	StateStackPtr = NULL;	/* mark that the state stack is empty */
	sDirection = -1;	/* initial move direction is up */
	ForwardLimit = lmtR.Ymin - 1;	/* stop proceeeding upward when we reach
								this line */
	BackwardLimit = lmtR.Ymax;	/* stop proceeeding downward when we reach
							this line */
	FLimitPtr = 0;	/* NULL pointer, because these lists never get added to */
	BLimitPtr = 0;

	/* get a sentinel and a single additional block for the fake 1-point
	shadow we're about to use as a basis for scanning out the seed line */
	AllocBlock();
	blockPtr->sXmin = 0x7FFF;	/* make it a sentinel */
	blockPtr->sXmax = 0x7FFF;
	blockPtrDN = blockPtr;	/* remember where head is */
	AllocBlock();	/* get a block for the seed point */
	blockPtrDN->NextBlock = blockPtr;
	blockPtr->NextBlock = blockPtrDN;	/* make it a circular list */
	pShadow = blockPtrDN;	/* this will become the shadow for scanning
								out the seed line */
	
	/* we'll scan from the seed point (yes, this does mean that we read the
	seed point a second time for flood fills; that's life)*/
	blockPtr->sXmin = SeedX;
	blockPtr->sXmax = SeedX + 1;

	/*scan left and right from the seed point to make the initial current
	fill list, consisting of exactly one segment (the seed point has
	already been checked to be fillable) */

	/* generate the one segment from the seed point */
	if (ScanOutSegList() == 0)
	{	/* not enough memory */
		grafErrValue = c_SeedFill +  c_OutofMem;
		nuGrafErr(grafErrValue);
		return;
	}
	
	if (blockPtr->NextBlock == blockPtr) return;	/* empty segment list
							(Seed point not fillable; can't happen with
							flood fill, but can with boundary fill) */

	/* make the shadow list empty, so we can have an unobstructed backshadow
	from the seed line */
	blockPtrBE = pShadow->NextBlock;	/* link the sentinel to itself to
										make the shadow list empty */
	pShadow->NextBlock = pShadow;
	blockPtrBE->NextBlock = FreeBlocks;	/* link it to the free list */
	FreeBlocks = blockPtrBE;			/* and link the free list to it */

	/* Draw the segment list (build blitList, flushing when full).
	Assumes non-empty segment list. */