bitmapregion2d.hh

来自「Motion JPEG编解码器源代码」· HH 代码 · 共 1,442 行 · 第 1/3 页

		&& m_tnHeight == a_rOther.m_tnHeight);

	// Copy the other region's bitmap.
	memcpy (m_pnPoints, a_rOther.m_pnPoints,
		m_tnBitmapInts * sizeof (unsigned int));
}



// Destructor.
template <class INDEX, class SIZE>
BitmapRegion2D<INDEX,SIZE>::~BitmapRegion2D()
{
	// Free up the bitmap.
	delete[] m_pnPoints;

#ifndef NDEBUG
	// One less instance.
	--sm_ulInstances;
#endif // NDEBUG
}



// Return the total number of points contained by the region.
template <class INDEX, class SIZE>
SIZE
BitmapRegion2D<INDEX,SIZE>::NumberOfPoints (void) const
{
	// To make this fast, we precalculate a table, indexed by byte
	// value, that contains the number of set bits in that byte.
	if (!m_bSetBitsPerByte)
	{
		for (int i = 0; i < 256; ++i)
		{
			int8_t nBits = 0;
			uint8_t nVal = uint8_t (i);
			for (int j = 0; j < 8; ++j)
			{
				if (nVal & 1)
					++nBits;
				nVal >>= 1;
			}
			m_anSetBitsPerByte[i] = nBits;
		}

		// We only have to do this once.
		m_bSetBitsPerByte = true;
	}

	SIZE tnI, tnLimit;
		// Used to loop through the bitmap's bytes.
	SIZE tnPoints;
		// The number of points we tally.

	// Loop through the bitmap's bytes, look up how many set bits
	// there are in each byte, count them up.
	uint8_t *pnPoints = (uint8_t *) m_pnPoints;
	tnLimit = m_tnBitmapInts
		* (sizeof (unsigned int) / sizeof (uint8_t));
	tnPoints = 0;
	for (tnI = 0; tnI < tnLimit; ++tnI)
		tnPoints += m_anSetBitsPerByte[pnPoints[tnI]];

	// Return the number of points we counted.
	return tnPoints;
}



// Clear the region, emptying it of all extents.
template <class INDEX, class SIZE>
void
BitmapRegion2D<INDEX,SIZE>::Clear (void)
{
	// Easy enough.
	memset (m_pnPoints, 0, ARRAYSIZE (unsigned int, m_tnBitmapInts));
}



// Add the given horizontal extent to the region.
template <class INDEX, class SIZE>
void
BitmapRegion2D<INDEX,SIZE>::Union (INDEX a_tnY, INDEX a_tnXStart,
	INDEX a_tnXEnd)
{
	SIZE tnI;
		// The index of the bitmap integer to modify.
	INDEX tnX;
		// Used to loop through points.

	// Make sure they gave us a non-empty extent.
	assert (a_tnXStart < a_tnXEnd);

	// If this extent is completely outside the region, skip it.
	if (a_tnY < 0 || a_tnY >= m_tnHeight
	|| a_tnXStart >= m_tnWidth || a_tnXEnd <= 0)
		return;

	// If this extent is partially outside the region, clip it.
	if (a_tnXStart < 0)
		a_tnXStart = 0;
	if (a_tnXEnd > m_tnWidth)
		a_tnXEnd = m_tnWidth;
	if (a_tnXStart < 0)
		a_tnXStart = 0;
	if (a_tnXEnd > m_tnWidth)
		a_tnXEnd = m_tnWidth;

	// Loop through all the points, set them.
	for (tnX = a_tnXStart; tnX < a_tnXEnd; ++tnX)
	{
		tnI = a_tnY * m_tnWidth + tnX;
		m_pnPoints[tnI / (g_knBitsPerByte
				* sizeof (unsigned int))]
			|= (1U << (tnI % (g_knBitsPerByte
				* sizeof (unsigned int))));
	}
}



// Add the given horizontal extent to the region.
template <class INDEX, class SIZE>
void
BitmapRegion2D<INDEX,SIZE>::Union (Status_t &a_reStatus, INDEX a_tnY,
	INDEX a_tnXStart, INDEX a_tnXEnd)
{
	// Make sure they didn't start us off with an error.
	assert (a_reStatus == g_kNoError);

	// Call the non-failing version.
	Union (a_tnY, a_tnXStart, a_tnXEnd);
}



// Make the current region represent the union between itself
// and the other given region.
template <class INDEX, class SIZE>
void
BitmapRegion2D<INDEX,SIZE>::Union (Status_t &a_reStatus,
	const BitmapRegion2D<INDEX,SIZE> &a_rOther)
{
	// Make sure they didn't start us off with an error.
	assert (a_reStatus == g_kNoError);

	// Make sure the region is the exact same size.
	assert (m_tnWidth == a_rOther.m_tnWidth
		&& m_tnHeight == a_rOther.m_tnHeight);

	// Unify with the other region's bitmap.
	for (SIZE i = 0; i < m_tnBitmapInts; ++i)
		m_pnPoints[i] |= a_rOther.m_pnPoints[i];
}



// Merge this extent into the current region.
// The new extent can't intersect the region in any way.
template <class INDEX, class SIZE>
void
BitmapRegion2D<INDEX,SIZE>::Merge (Status_t &a_reStatus, INDEX a_tnY,
	INDEX a_tnXStart, INDEX a_tnXEnd)
{
	// For a bitmap, Union() is the same thing.
	Union (a_reStatus, a_tnY, a_tnXStart, a_tnXEnd);
}



// Merge the other region into ourselves, emptying the other region.
template <class INDEX, class SIZE>
void
BitmapRegion2D<INDEX,SIZE>::Merge (BitmapRegion2D<INDEX,SIZE> &a_rOther)
{
	// Make sure the region is the exact same size.
	assert (m_tnWidth == a_rOther.m_tnWidth
		&& m_tnHeight == a_rOther.m_tnHeight);

	// For a bitmap, this is easy.
	Status_t eStatus = g_kNoError;
	Union (eStatus, a_rOther);
	assert (eStatus == g_kNoError);
	a_rOther.Clear();
}



// Move the contents of the other region into the current region.
template <class INDEX, class SIZE>
void
BitmapRegion2D<INDEX,SIZE>::Move (BitmapRegion2D<INDEX,SIZE> &a_rOther)
{
	// Make sure we're allowed to do this.
	assert (CanMove (a_rOther));

	// Empty the current region.
	Clear();
	
	// Swap the contained bitmaps.
	unsigned int *pnPoints = m_pnPoints;
	m_pnPoints = a_rOther.m_pnPoints;
	a_rOther.m_pnPoints = pnPoints;
}



// Returns true if the other region's contents can be moved
// into the current region.
template <class INDEX, class SIZE>
bool
BitmapRegion2D<INDEX,SIZE>::CanMove
	(const BitmapRegion2D<INDEX,SIZE> &a_rOther) const
{
	// We can do this if the regions are the same size.
	return (m_tnWidth == a_rOther.m_tnWidth
		&& m_tnHeight == a_rOther.m_tnHeight);
}



// Make the current region represent the intersection between
// itself and the other given region.
template <class INDEX, class SIZE>
void
BitmapRegion2D<INDEX,SIZE>::Intersection (Status_t &a_reStatus,
	const BitmapRegion2D<INDEX,SIZE> &a_rOther)
{
	// Make sure they didn't start us off with an error.
	assert (a_reStatus == g_kNoError);

	// Make sure the region is the exact same size.
	assert (m_tnWidth == a_rOther.m_tnWidth
		&& m_tnHeight == a_rOther.m_tnHeight);

	// Intersect with the other region's bitmap.
	for (SIZE i = 0; i < m_tnBitmapInts; ++i)
		m_pnPoints[i] &= a_rOther.m_pnPoints[i];
}



// Subtract the given horizontal extent from the region.
template <class INDEX, class SIZE>
void
BitmapRegion2D<INDEX,SIZE>::Subtract (Status_t &a_reStatus, INDEX a_tnY,
	INDEX a_tnXStart, INDEX a_tnXEnd)
{
	SIZE tnI;
		// The index of the bitmap integer to modify.
	INDEX tnX;
		// Used to loop through points.

	// Make sure they didn't start us off with an error.
	assert (a_reStatus == g_kNoError);

	// Make sure they gave us a non-empty extent.
	assert (a_tnXStart < a_tnXEnd);

	// If this extent is completely outside the region, skip it.
	if (a_tnY < 0 || a_tnY >= m_tnHeight
	|| a_tnXStart >= m_tnWidth || a_tnXEnd <= 0)
		return;

	// If this extent is partially outside the region, clip it.
	if (a_tnXStart < 0)
		a_tnXStart = 0;
	if (a_tnXEnd > m_tnWidth)
		a_tnXEnd = m_tnWidth;
	if (a_tnXStart < 0)
		a_tnXStart = 0;
	if (a_tnXEnd > m_tnWidth)
		a_tnXEnd = m_tnWidth;

	// Loop through all the points, clear them.
	for (tnX = a_tnXStart; tnX < a_tnXEnd; ++tnX)
	{
		tnI = a_tnY * m_tnWidth + tnX;
		m_pnPoints[tnI / (g_knBitsPerByte
				* sizeof (unsigned int))]
			&= (~(1U << (tnI % (g_knBitsPerByte
				* sizeof (unsigned int)))));
	}
}



// Subtract the other region from the current region, i.e.
// remove from the current region any areas that exist in the
// other region.
template <class INDEX, class SIZE>
template <class OTHER>
void
BitmapRegion2D<INDEX,SIZE>::Subtract (Status_t &a_reStatus,
	const OTHER &a_rOther)
{
	typename OTHER::ConstIterator itExtent;
		// Used to loop through the other region's extents.

	// Make sure they didn't start us off with an error.
	assert (a_reStatus == g_kNoError);

	// Loop through the other region's extents, subtract each one.
	for (itExtent = a_rOther.Begin();
		 itExtent != a_rOther.End();
		 ++itExtent)
	{
		Subtract (a_reStatus, (*itExtent).m_tnY, (*itExtent).m_tnXStart,
			(*itExtent).m_tnXEnd);
		assert (a_reStatus == g_kNoError); 	// (should always succeed.)
		if (a_reStatus != g_kNoError)
			return;
	}
}



// Subtract the other region from the current region, i.e.
// remove from the current region any areas that exist in the
// other region.
template <class INDEX, class SIZE>
void
BitmapRegion2D<INDEX,SIZE>::Subtract (Status_t &a_reStatus,
	const BitmapRegion2D<INDEX,SIZE> &a_rOther)
{
	// Make sure they didn't start us off with an error.
	assert (a_reStatus == g_kNoError);

	// Make sure the region is the exact same size.
	assert (m_tnWidth == a_rOther.m_tnWidth
		&& m_tnHeight == a_rOther.m_tnHeight);

	// Subtract the other region's bitmap.
	for (SIZE i = 0; i < m_tnBitmapInts; ++i)
		m_pnPoints[i] &= (~(a_rOther.m_pnPoints[i]));
}



// Returns true if the region contains the given point.
template <class INDEX, class SIZE>
bool
BitmapRegion2D<INDEX,SIZE>::DoesContainPoint
	(INDEX a_tnY, INDEX a_tnX) const
{
	// Make sure the indices are within our extent.
	assert (a_tnY >= 0 && a_tnY < m_tnHeight);
	assert (a_tnX >= 0 && a_tnX < m_tnWidth);

	// Find the bit & return if it's set.
	SIZE tnI = a_tnY * m_tnWidth + a_tnX;
	return (m_pnPoints[tnI / (g_knBitsPerByte * sizeof (unsigned int))]
		& (1U << (tnI % (g_knBitsPerByte * sizeof (unsigned int)))));
}



// Flood-fill the current region.
template <class INDEX, class SIZE>
template <class CONTROL>
void
BitmapRegion2D<INDEX,SIZE>::FloodFill (Status_t &a_reStatus,
	CONTROL &a_rControl, bool a_bVerify)
{
	typename CONTROL::ConstIterator itExtent;
		// An extent we're examining.
	Extent oFoundExtent;
		// An extent we found to be part of the region.

	// Make sure they didn't start us off with an error.
	assert (a_reStatus == g_kNoError);

	// How we set up depends on whether we're to verify all existing
	// region extents.
	if (a_bVerify)
	{
		// The to-do-list becomes the current region, and we empty
		// out the current region too.
		a_rControl.m_oAlreadyDone.Clear();
		if (a_rControl.m_oToDo.CanMove (*this))
		{
			// Grab the extents right out of the current region.
			a_rControl.m_oToDo.Clear();
			a_rControl.m_oToDo.Move (*this);
		}
		else
		{
			// Copy the extents from the current region, then empty it.
			a_rControl.m_oToDo.Assign (a_reStatus, *this);
			if (a_reStatus != g_kNoError)
				return;
			Clear();
		}
	}
	else
	{
		// The already-done list starts with the region, i.e. every
		// extent already known to be in the region can avoid getting
		// tested.
		a_rControl.m_oAlreadyDone.Assign (a_reStatus, *this);
		if (a_reStatus != g_kNoError)
			return;
	
		// Start the to-do list with a border around all the extents in
		// the region.
		a_rControl.m_oToDo.MakeBorder (a_reStatus, *this);
		if (a_reStatus != g_kNoError)
			return;
	}

	// Now pull each extent out of the to-do list.  Determine which
	// sub-extents are part of the region.  Add those found extents
	// to the region.  Then add all extent surrounding the found extents
	// to the to-do-next list.
	itExtent = a_rControl.m_oToDo.Begin();
	while (itExtent != a_rControl.m_oToDo.End())
	{
		bool bStartedExtent;
			// true if we've started finding an extent.
		INDEX tnX;
			// Where we're looking for extents.

		// Get the extent, converting the type if necessary.
		typename CONTROL::Extent oExtent;
		oExtent.m_tnY = (*itExtent).m_tnY;
		oExtent.m_tnXStart = (*itExtent).m_tnXStart;
		oExtent.m_tnXEnd = (*itExtent).m_tnXEnd;

		// We're about to check this extent.  Put it in the
		// already-checked list now.
		a_rControl.m_oAlreadyDone.Union (a_reStatus, oExtent.m_tnY,
			oExtent.m_tnXStart, oExtent.m_tnXEnd);
		if (a_reStatus != g_kNoError)
			return;
	
		// If this extent shouldn't be considered, skip it.
		if (!a_rControl.ShouldUseExtent (oExtent))
			goto nextExtent;

		// Make sure our client left us with a valid extent.
		assert (oExtent.m_tnXStart < oExtent.m_tnXEnd);
		
		// Run through the pixels described by this extent, see if
		// they can be added to the region, and remember where to
		// search next.
		oFoundExtent.m_tnY = oExtent.m_tnY;
		bStartedExtent = false;
		for (tnX = oExtent.m_tnXStart; tnX <= oExtent.m_tnXEnd; ++tnX)
		{
			// Is this point in the region?
			if (tnX < oExtent.m_tnXEnd
			&& a_rControl.IsPointInRegion (tnX, oExtent.m_tnY))
			{
				// This point is in the region.  Start a new extent
				// if we didn't have one already, and add the point
				// to it.
				if (!bStartedExtent)
				{
					oFoundExtent.m_tnXStart = tnX;
					bStartedExtent = true;
				}
				oFoundExtent.m_tnXEnd = tnX + 1;
			}

			// This point is not in the region.  Any extent we're
			// building is done.
			else if (bStartedExtent)
			{
				// Add this extent to the region.
				Union (a_reStatus, oFoundExtent.m_tnY,
					oFoundExtent.m_tnXStart, oFoundExtent.m_tnXEnd);
				if (a_reStatus != g_kNoError)
					return;

				// Now add all surrounding extents to the to-do-next
				// list.
				a_rControl.m_oNextToDo.UnionSurroundingExtents
					(a_reStatus, oFoundExtent.m_tnY,
						oFoundExtent.m_tnXStart, oFoundExtent.m_tnXEnd);