searchborder.hh

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

	{
		for (itActive = m_setBorderRegions.Begin();
			 itActive != m_setBorderRegions.End();
			 itActive = itNextActive)
		{
			// Get the next item, since we may remove the current item.
			itNextActive = itActive;
			++itNextActive;
	
			// If this region reference came from the last-border, get
			// rid of it.
			if ((*itActive).m_tnLine == m_tnY - 1)
				m_setBorderRegions.Erase (itActive);
		}
	}

	// The old last-border is gone, and we have a new current-border.
	// So move all our startpoint/endpoint iterators back one, and
	// create a new one for the new current-border.
	for (i = 1; i <= m_tnPGH; ++i)
	{
		m_paitBorderStartpoints[i-1] = m_paitBorderStartpoints[i];
		m_paitBorderEndpoints[i-1] = m_paitBorderEndpoints[i];
	}
	m_paitBorderStartpoints[m_tnPGH] = m_setBorderStartpoints.End();
	m_paitBorderEndpoints[m_tnPGH] = m_setBorderEndpoints.End();

	// Any region with (if m_tnX == 0) a last-border startpoint at
	// m_tnPGW or (if m_tnX == m_tnWidth - m_tnPGW) a last-border
	// endpoint of m_tnX will no longer be contiguous with the current
	// pixel-group, but they will be the next time the search border
	// moves left/right.
	// (But not if we're past the bottom line.  This happens when we're
	// called by FinishFrame().)
	if (m_tnY < m_tnHeight - m_tnPGH)
	{
		typename IntersectingRegionsSet::Iterator itRemove;
			// An item being removed from the possibly-intersecting set.

		if (m_tnX == 0)
		{
			// Get the iterator we'll be using.
			typename BorderExtentBoundarySet::ConstIterator &ritBorder
				= m_paitBorderStartpoints[0];
	
#ifndef NDEBUG
			// Make sure it's right where we want to be.
			{
				typename BorderExtentBoundarySet::ConstIterator itPrev
					= ritBorder;
				--itPrev;
				assert (ritBorder == m_setBorderStartpoints.End()
				|| (*ritBorder).m_tnLine > m_tnY
				|| ((*ritBorder).m_tnLine == m_tnY
					&& ((*ritBorder).m_tnIndex > m_tnPGW
						&& (itPrev == m_setBorderStartpoints.End()
							|| (*itPrev).m_tnLine < m_tnY
							|| ((*itPrev).m_tnLine == m_tnY
								&& (*itPrev).m_tnIndex <= m_tnPGW)))));
			}
#endif // NDEBUG

			// Remove all active regions that have startpoints at this
			// index.
			while ((--ritBorder) != m_setBorderStartpoints.End()
			&& (*ritBorder).m_tnLine == m_tnY
			&& (*ritBorder).m_tnIndex == m_tnPGW)
			{
#ifdef PRINT_SEARCHBORDER
				if (frame == 61)
				fprintf (stderr, "Moving down a line, remove "
						"active-border region (%d,%d), "
						"motion vector (%d,%d)\n",
					(*ritBorder).m_tnIndex, (*ritBorder).m_tnLine,
					(*ritBorder).m_tnMotionX, (*ritBorder).m_tnMotionY);
#endif
		
				itRemove = m_setBorderRegions.Find (*ritBorder);
	
#ifdef PRINT_SEARCHBORDER
				if (frame == 61 && itRemove == m_setBorderRegions.End())
				{
					fprintf (stderr, "NOT FOUND!\n"
						"Here's what was found:\n");
					for (itRemove = m_setBorderRegions.Begin();
						 itRemove != m_setBorderRegions.End();
						 ++itRemove)
					{
						fprintf (stderr, "\t(%d,%d), "
								"motion vector (%d,%d)\n",
							(*itRemove).m_tnIndex, (*itRemove).m_tnLine,
							(*itRemove).m_tnMotionX,
							(*itRemove).m_tnMotionY);
					}
				}
#endif
		
				assert (itRemove != m_setBorderRegions.End());
				m_setBorderRegions.Erase (itRemove);
			}
			++ritBorder;
		}
		else
		{
			assert (m_tnX == m_tnWidth - m_tnPGW);

			// Get the iterator we'll be using.
			typename BorderExtentBoundarySet::ConstIterator &ritBorder
				= m_paitBorderEndpoints[0];
	
#ifndef NDEBUG
			// Make sure it's right where we expect it to be.
			{
				typename BorderExtentBoundarySet::ConstIterator itPrev
					= ritBorder;
				--itPrev;
				assert (ritBorder == m_setBorderEndpoints.End()
					|| (*ritBorder).m_tnLine > m_tnY
					|| ((*ritBorder).m_tnLine == m_tnY
						&& (*ritBorder).m_tnIndex >= m_tnX
						&& (itPrev == m_setBorderEndpoints.End()
							|| (*itPrev).m_tnLine < m_tnY
							|| ((*itPrev).m_tnLine == m_tnY
								&& (*itPrev).m_tnIndex < m_tnX))));
			}
#endif // NDEBUG
	
			// Remove all active regions that have endpoints at this
			// index.
			while (ritBorder != m_setBorderEndpoints.End()
			&& (*ritBorder).m_tnLine == m_tnY
			&& (*ritBorder).m_tnIndex == m_tnX)
			{
				// Move to the corresponding startpoint.
				const BorderExtentBoundary &rHere
					= *((*ritBorder).m_pCounterpart);

#ifdef PRINT_SEARCHBORDER
				if (frame == 61)
				fprintf (stderr, "Moving down a line, remove "
						"active-border region (%d,%d), "
						"motion vector (%d,%d)\n",
					rHere.m_tnIndex, rHere.m_tnLine,
					rHere.m_tnMotionX, rHere.m_tnMotionY);
#endif
		
				itRemove = m_setBorderRegions.Find (rHere);
	
#ifdef PRINT_SEARCHBORDER
				if (frame == 61 && itRemove == m_setBorderRegions.End())
				{
					fprintf (stderr, "NOT FOUND!\n"
						"Here's what was found:\n");
					for (itRemove = m_setBorderRegions.Begin();
						 itRemove != m_setBorderRegions.End();
						 ++itRemove)
					{
						fprintf (stderr, "\t(%d,%d), "
								"motion vector (%d,%d)\n",
							(*itRemove).m_tnIndex, (*itRemove).m_tnLine,
							(*itRemove).m_tnMotionX,
							(*itRemove).m_tnMotionY);
					}
				}
#endif
		
				assert (itRemove != m_setBorderRegions.End());
				m_setBorderRegions.Erase (itRemove);

				++ritBorder;
			}
		}

		// Finally, move one step down, and prepare to move the other
		// direction across the window.  (But not if we're past the
		// bottom line, i.e. being called by FinishFrame().)
		++m_tnY;
		m_tnStepX = -m_tnStepX;
	}
}



// Return the number of regions that would intersect with the
// current pixel-group.
template <class PIXELINDEX, class FRAMESIZE>
inline FRAMESIZE
SearchBorder<PIXELINDEX,FRAMESIZE>::NumberOfActiveRegions (void) const
{
	// Easy enough.
	return m_setBorderRegions.Size();
}



// Accept a new match for a pixel-group, with the given motion-vector.
template <class PIXELINDEX, class FRAMESIZE>
FRAMESIZE
SearchBorder<PIXELINDEX,FRAMESIZE>::AddNewMatch (Status_t &a_reStatus,
	PIXELINDEX a_tnMotionX, PIXELINDEX a_tnMotionY)
{
	PIXELINDEX tnI, tnJ;
		// Used to loop through things.
	typename IntersectingRegionsSet::Iterator itHere;
		// The range of regions that are contiguous with the newly-added
		// pixel-group.
	bool bLastBorderExtentFound;
		// true if the current pixel-group merged with a region that
		// had an extent on the last-boundary.
	MovedRegion *pRegionMergedTo;
	RegionUnderConstruction *pRegionUnderConstructionMergedTo;
		// The region that receives the new pixel-group, as well as any
		// other region that's now contiguous with it.
		// May be a brand-new region.
	BorderExtentBoundary *aStart, *aEnd;
		// Used to search for the range of regions contiguous with the
		// new pixel-group, as well as to set up the new startpoints and
		// endpoints for the current-border and last-border.
	typename BorderExtentBoundarySet::Iterator *aitCurrentStarts,
			*aitCurrentEnds;
		// Where the startpoints/endpoints gets hooked into the
		// current-boundary/last-boundary.
	typename IntersectingRegionsSet::Iterator *aitCurrentRegions;
		// Where the new/merged region gets hooked into the
		// possibly-intersecting list of regions.
	
	// Allocate memory for our temporary arrays.
	aStart = (BorderExtentBoundary *) alloca
		(ARRAYSIZE (BorderExtentBoundary, m_tnPGH + 1));
	aEnd = (BorderExtentBoundary *) alloca
		(ARRAYSIZE (BorderExtentBoundary, m_tnPGH + 1));
	aitCurrentStarts = (typename BorderExtentBoundarySet::Iterator *)
		alloca (ARRAYSIZE (typename BorderExtentBoundarySet::Iterator,
		m_tnPGH + 1));
	aitCurrentEnds = (typename BorderExtentBoundarySet::Iterator *)
		alloca (ARRAYSIZE (typename BorderExtentBoundarySet::Iterator,
		m_tnPGH + 1));
	aitCurrentRegions = (typename IntersectingRegionsSet::Iterator *)
		alloca (ARRAYSIZE (typename IntersectingRegionsSet::Iterator,
		m_tnPGH + 1));

#if 0
	// (Why isn't this working???  It's not strictly necessary, but I
	// like to be clean.)
	// Construct the objects in our temporary arrays.
	for (tnI = 0; tnI < m_tnPGH + 1; ++tnI)
	{
		typedef typename BorderExtentBoundarySet::Iterator
			BorderExtentBoundarySetIterator;
		typedef typename IntersectingRegionsSet::Iterator
			IntersectingRegionsSetIterator;

		aStart[tnI].BorderExtentBoundary();
		aEnd[tnI].BorderExtentBoundary();
		aitCurrentStarts[tnI].BorderExtentBoundarySetIterator();
		aitCurrentEnds[tnI].BorderExtentBoundarySetIterator();
		aitCurrentRegions[tnI].IntersectingRegionsSetIterator();
	}
#endif

	// m_setBorderRegions contains all the regions that would intersect
	// with a pixel-group match at the current location, so we just
	// search for the subset with the same motion-vector.
	aStart[0].m_tnMotionX = a_tnMotionX;
	aStart[0].m_tnMotionY = a_tnMotionY;
	aStart[0].m_bIsEnding = false;
	itHere = m_setBorderRegions.LowerBound (aStart[0]);

	// Create the initial startpoint/endpoint for the current-border
	// and last-border.  If we find any regions that intersect with the
	// new pixel-group, these will get adjusted.
	for (tnI = 0; tnI <= m_tnPGH; ++tnI)
	{
		aStart[tnI].m_tnMotionX = aEnd[tnI].m_tnMotionX = a_tnMotionX;
		aStart[tnI].m_tnMotionY = aEnd[tnI].m_tnMotionY = a_tnMotionY;
		aStart[tnI].m_bIsEnding = false;
		aEnd[tnI].m_bIsEnding = true;
		aStart[tnI].m_tnIndex = m_tnX;
		aEnd[tnI].m_tnIndex = m_tnX + m_tnPGW;
		aStart[tnI].m_tnLine = aEnd[tnI].m_tnLine = m_tnY + tnI
			- PIXELINDEX (1);
	}

	// We only add a last-border extent if the current pixel-group
	// got merged with a region that had a last-border extent (since the
	// current pixel-group doesn't have a last-border extent itself).
	// Set up to detect that.
	bLastBorderExtentFound = false;
	aStart[0].m_tnIndex = Limits<PIXELINDEX>::Max;
	aEnd[0].m_tnIndex = Limits<PIXELINDEX>::Min;

	// Do any existing regions intersect with the new pixel-group?
	if (itHere == m_setBorderRegions.End()
	|| (*itHere).m_tnMotionX != aStart[0].m_tnMotionX
	|| (*itHere).m_tnMotionY != aStart[0].m_tnMotionY)
	{
#ifdef PRINT_SEARCHBORDER
		if (frame == 61)
		fprintf (stderr, "Create a new region for the match.\n");
#endif

		// No.  Create a new region.
		pRegionMergedTo = new MovedRegion (a_reStatus);
		if (pRegionMergedTo == NULL)
			goto cleanup0;
		if (a_reStatus != g_kNoError)
			goto cleanup1;

		// Set its motion vector.
		pRegionMergedTo->SetMotionVector (a_tnMotionX, a_tnMotionY);

		// Create something to manage the region as it's being
		// constructed.
		pRegionUnderConstructionMergedTo = new RegionUnderConstruction;
		if (pRegionUnderConstructionMergedTo == NULL)
			goto cleanup1;
		pRegionUnderConstructionMergedTo->m_pRegion = pRegionMergedTo;

		// Regions under construction form a circular list with all
		// other under-construction regions that it gets merged with.
		// So start the circular list.
		pRegionUnderConstructionMergedTo->m_pForward
			= pRegionUnderConstructionMergedTo->m_pBackward
			= pRegionUnderConstructionMergedTo;
	}

	// Some existing regions intersect with the current pixel-group.
	else
	{
#ifdef PRINT_SEARCHBORDER
		if (frame == 61)
		fprintf (stderr, "This match is contiguous with an existing "
			"region!\n");
#endif

		// Get the first region that's contiguous with the new
		// pixel-group.
		pRegionUnderConstructionMergedTo = (*itHere).m_pRegion;
		pRegionMergedTo = pRegionUnderConstructionMergedTo->m_pRegion;

#ifdef PRINT_SEARCHBORDER
		if (frame == 61)
		{
		fprintf (stderr, "Region to merge to:\n");
		PrintRegion (*pRegionMergedTo);
		fprintf (stderr, "\n");
		}
#endif

		// Now loop through all the regions that'll get merged with the
		// current pixel-group (including the first one that we already
		// looked at).  Incorporate the startpoint/endpoint associated
		// with that region into our new startpoint/endpoint.  Then, if
		// it's a different region than the first one we looked at,
		// merge it into that first one.  Finally, remove the found
		// startpoints/endpoints -- they'll be superseded by the
		// merged-region's startpoints/endpoints.
		while (itHere != m_setBorderRegions.End()
		&& (*itHere).m_tnMotionX == aStart[0].m_tnMotionX
		&& (*itHere).m_tnMotionY == aStart[0].m_tnMotionY)
		{
			typename IntersectingRegionsSet::Iterator itNext;
				// The next item in the possibly-intersecting-region
				// set.  Needed because we remove the current item.
			PIXELINDEX tnBorderIndex;
				// Which current-border it's on.  Ranges from 0 (the
				// last-border) to 1 (the first current-border) to
				// m_tnPGH (the last current-border).
			MovedRegion *pRegionMergedFrom;
			RegionUnderConstruction *pRegionUnderConstructionMergedFrom;
				// The latest region that's contiguous with the new
				// pixel-group.
			typename BorderExtentBoundarySet::Iterator itStart, itEnd;
				// The location of the startpoint/endpoint of the latest
				// region that's contiguous with the new pixel-group.
				// (And they all lived in the house that Jack built, so
				// NYAAAH!)

			// Before we have a chance to remove the current item,
			// remember the next item, so that we can move to it later.
			itNext = itHere;
			++itNext;

			// Figure out which border this new region is on.
			tnBorderIndex = (*itHere).m_tnLine - m_tnY + 1;
			// (Sanity check: there should be no last-border regions
			// if there is no last-border.)
			assert (tnBorderIndex > 0 || m_tnY > 0);

#ifdef PRINT_SEARCHBORDER
			if (frame == 61)
			fprintf (stderr, "Search for startpoint (%d,%d)\n",
				(*itHere).m_tnIndex, (*itHere).m_tnLine);
#endif

			// Find the startpoint/endpoint.
			itStart = m_setBorderStartpoints.Find (*itHere);
			assert (itStart != m_setBorderStartpoints.End());
			assert (*itStart == *itHere);
			itEnd = m_setBorderEndpoints.Find
				(*((*itStart).m_pCounterpart));
			assert (itEnd != m_setBorderEndpoints.End());
			// (Sanity check: make sure the endpoint knows it's paired
			// with this startpoint.)
			assert ((*itEnd).m_pCounterpart == &(*itStart));
			// (Sanity check: make sure they refer to the same region
			// under construction.)
			assert ((*itStart).m_pRegion == (*itEnd).m_pRegion);

			// Remove the merged-from region from the list of
			// possibly-intersecting regions.
			assert (m_setBorderRegions.LowerBound (*itHere)	// sanity
				== itHere);
			m_setBorderRegions.Erase (itHere);

			// Extend our new startpoint/endpoint by this region's
			// startpoint/endpoint.
			aStart[tnBorderIndex].m_tnIndex
				= Min (aStart[tnBorderIndex].m_tnIndex,
					(*itStart).m_tnIndex);
			aEnd[tnBorderIndex].m_tnIndex
				= Max (aEnd[tnBorderIndex].m_tnIndex,
					(*itEnd).m_tnIndex);
			// (If that was on the last-border, remember that.)