Thread: Priority queue not processed in expected order

Hello,

I am trying to implement a priority queue in an OpenGL program and am getting unexpected results.

I have an original image. The user colors different parts of this image one of three colors, with each color representing a different value of rigidity for that portion of the image. Then, when the user clicks and drags a point in the image, that image stretches depending on the rigidity of its parts. I want the connected, rigid parts of the image to move together, so I have implemented a priority queue to determine where each pixel of the image ends up after deformation, with the most rigid portions processed first.

The problem is that currently, the priority processes most of the rigid points together, but not all of them. I have output the order the points are being processed to confirm this, and it is not an OpenGL issue. Because of this issue, those rigid portions of the image don't stay together when they move. Does anyone have any suggestions?

I define my priority queue thusly:

Code:

std::priority_queue<DeformationCandidate> _deformationQueue;

A simplified version of the relevant code segment is below. It begins after the image has been colored and the user starts the stretching of the image.

Code:

        //Move the pixel nearest to the mouse click and drag

        //Add the first pixel's neighbors to the deformation queue

        //Process the neighbors queue
	while (!_deformationQueue.empty())
	{
		//Grab the candidate pixel for deformation from the neighbors queue
		DeformationCandidate candidatePoint = _deformationQueue.top();
		_deformationQueue.pop();

		
		//If the point has not already been processed, do so using the deformation of its sponsor point
		if (!deformed)
		{
			//Calculate how much the point moved

			//If the point was moved, we add its neighbors to the queue
			//xShift and yShift are the x and y displacements of the point
			if ((fabs(xShift) > 0.0) && (fabs(yShift) > 0.0))
			{
				//Add that point's neighbors to the queue to be processed
				_addNeighbors(candidatePoint.row, candidatePoint.column);
			}
		}

		//Flag the point as deformed so we don't keep processing already deformed points
		deformed = true;
	}

DeformationCandidate.h is:

Code:

#ifndef DEFORMATION_CANDIDATE
#define DEFORMATION_CANDIDATE

class DeformationCandidate
{
private:
public:
	DeformationCandidate();
	~DeformationCandidate(){};

	//The row and column number of the candidate point
	int row, column;

	//The row and column number for the sponsor point.
	//The sponsor point is the point whose movent caused our candidate point to deform
	int sponsorRow, sponsorColumn;

	//The tissue dentisty of the candidate point
	int rigidity;

	int get_rigidity()
	{
		return rigidity;
	}
	
	//Overloaded operators to appropriately order priority queue
	bool operator==(const DeformationCandidate& rhs) const;

	bool operator<(const DeformationCandidate& rhs) const;

	bool operator>(const DeformationCandidate& rhs) const;
};
#endif

and DeformationCandidate.cpp is:

Code:

# include "DeformationCandidate.h"

DeformationCandidate::DeformationCandidate()
{
	//Initialize variable values
	row = -1;
	column = -1;
	rigidity = -1;
	sponsorRow = -1;
	sponsorColumn = -1;

}

bool DeformationCandidate::operator==(const DeformationCandidate& rhs) const
{
	return (*this).rigidity == rhs.rigidity;
}

bool DeformationCandidate::operator<(const DeformationCandidate& rhs) const
{
	return (*this).rigidity < rhs.rigidity;
}

bool DeformationCandidate::operator>(const DeformationCandidate& rhs) const
{
	return (*this).rigidity > rhs.rigidity;
}

Thanks,
JackR

iMalc,

Thank you for your reply.

Deformed is a property of each pixel in the original image. I tried to show the section of the code where I thought the problem may have been, and I apologize for the error.

It should have been:

Code:

        
	//First, set the deformed variable for all points to false (not deformed)
	for (int rowNum = 0; rowNum < image.rows; rowNum++)
	{
		for (int columnNum = 0; columnNum < image.columns; columnNum++)
		{
                        image.deformed[rowNum][columnNum] = true;
		}
	}

        //Move the pixel nearest to the mouse click and drag

        //Add the first pixel's neighbors to the deformation queue

        //Process the neighbors queue
	while (!_deformationQueue.empty())
	{
		//Grab the candidate pixel for deformation from the neighbors queue
		DeformationCandidate candidatePoint = _deformationQueue.top();
		_deformationQueue.pop();

		
		//If the point has not already been processed, do so using the deformation of its sponsor point
		if (!image.deformed[candidatePoint.row][candidatePoint.column])
		{
			//Calculate how much the point moved

			//If the point was moved, we add its neighbors to the queue
			//xShift and yShift are the x and y displacements of the point
			if ((fabs(xShift) > 0.0) && (fabs(yShift) > 0.0))
			{
				//Add that point's neighbors to the queue to be processed
				_addNeighbors(candidatePoint.row, candidatePoint.column);
			}
		}

		//Flag the point on the original image as deformed so we don't keep processing already deformed points
		image.deformed[candidatePoint.row][candidatePoint.column] = true;
	}

I am still not sure what my issue is.