Jump to content


Best way for perfect pixel collision detection?


5 replies to this topic

#1 hellhound_01

    New Member

  • Members
  • PipPip
  • 58 posts

Posted 31 October 2012 - 11:00 AM

Actually I try to implement a pixel perfect collision (PPC) detection for 2D sprites. For "normal" sprites anything is working perfectly. But how should I handle scaled and rotated sprites?

PPC is expensive, so I try to find an optimized solution to perform PPC. What is the best way I should go? Should I read the actual pixel data from pixel buffer and compare those or should I approximate the scaled values against the origin image data?

Actually I use this approximation attempt to check point based collisions,
but this works not realy good with scaled sprites:

bool brSprite::intersect(float x, float y)
{
	// first check if bounding rect collides with point positions
	bool collision = this->contains(x, y);
  
	// perform pixel perfect collision if required
	if(collision && m_usePPC)
	{
      /* Substract actual rectangle position from point position value to
	   reduce intersection point to image dimensions in range: [0,width]
	   and [0,height].
	  
	   Please take note that we also have to regard the region x,y
	   position values to determine correct image position in atlas
	   textures and a scaling of the sprite.
		*/
		int pos_x = (int)((x - m_x)+m_region.getX()/m_scale.m_fX);
		int pos_y = (int)((y - m_y)+m_region.getY()/m_scale.m_fY);
	
		if(pos_x<m_width && pos_y<m_height){

			// define alpha compareable
			int alpha = 0;
			if(m_ppcTolerance>0){
				alpha = (255 * m_ppcTolerance)/100;
			}

			// perform pixel perfect collision check
			brColor color = m_region.getImage()->getPixelColor(pos_x,pos_y);
			if(color.getAlpha()>alpha){
				collision = true;
			}
	  else{
		collision = false;
	  }
		}	
	}  
	return collision;
}

Any Ideas?
"There is only one god and his name is death. And there is only one thing we have to say to Death: Not today!" -- Syrio Forel (from Game of Thrones)

#2 Stainless

    Member

  • Members
  • PipPipPipPip
  • 581 posts
  • LocationSouthampton

Posted 31 October 2012 - 12:15 PM

An alternative to pixel perfect collision detection is using collision polygons.

In your editor, you create a polygon that closely fits the image.

It's not perfect, but it's a lot less complex and a lot quicker.

#3 hellhound_01

    New Member

  • Members
  • PipPip
  • 58 posts

Posted 31 October 2012 - 12:21 PM

Stainless you are right, this is an option. But I've to use PPC ...
"There is only one god and his name is death. And there is only one thing we have to say to Death: Not today!" -- Syrio Forel (from Game of Thrones)

#4 TheNut

    Senior Member

  • Moderators
  • 1699 posts
  • LocationThornhill, ON

Posted 31 October 2012 - 01:40 PM

In my UI system, I just compute the inverse transformation on the point and check against the image buffer. These checks are being performed every time the cursor position updates, so it's quite frequent and I find the performance impact negligible. Tested on my netbook, it's like a percentage or two of CPU usage with several dozen UI elements on the screen. The benefits of using matrix multiplication is that it covers all grounds (translation, rotation, scale, sheer), and simplifies my code to just an arithmetic operation on the point and inverse transformation matrix. With a UI, demands are much greater because you have to test all objects in front, which can require deep traversals and many tests. With game objects, I would take advantage of spatial partioning to reduce the number of tests. In my particular case, I'm not sure there would be benefits for doing two types of tests. A high level box check and then a low-level pixel check. In both cases, I need to transform the input point, so the hard work has already been done. Performing a point in box check is redundant in my case because my image object already performs boundary checks on accessors. So, naturally I would just request the alpha value at that particular (x,y), do the test, and move on.
http://www.nutty.ca - Being a nut has its advantages.

#5 hellhound_01

    New Member

  • Members
  • PipPip
  • 58 posts

Posted 01 November 2012 - 06:09 AM

Hmm, sounds good. Nice idea using object transformation matrix operations.
I've to check this out.
"There is only one god and his name is death. And there is only one thing we have to say to Death: Not today!" -- Syrio Forel (from Game of Thrones)

#6 alphadog

    DevMaster Staff

  • Moderators
  • 1716 posts

Posted 07 November 2012 - 04:51 PM

Why must you use PPC?

Between PPC and bounding boxes, as Stainless says, you can use more complex geometric shapes. I like techniques that use convex hulls.
Hyperbole is, like, the absolute best, most wonderful thing ever! However, you'd be an idiot to not think dogmatism is always bad.





1 user(s) are reading this topic

0 members, 1 guests, 0 anonymous users