Are bounding box and circle collisions just not cutting it? Well, now we're going to dive right down into pixel precision!

Before we start, I'd like to say that this is an advanced SDL tutorial. You should have experience with creating SDL applications and some basic knowledge of getting a program with it's libraries up and running.

First, we'll start off with a very simple Game class to build the foundation of our demo project.

Game.h
#ifndef GAME_H
#define GAME_H

#include "SDL.h"

class Game
{
    public:
        Game();
        ~Game();

        void OnExecute();

        void OnThink();
        void OnUpdate();
        void OnRender();

    private:
        int ScreenWidth;
        int ScreenHeight;
        int ScreenBPP;
        Uint32 ScreenFlags;
        
        bool done;

        double thisTime;
        double lastTime;
        double deltaTime;

        SDL_Surface* screen;
        SDL_Event event;
};

#endif
Game.cpp
#include "Game.h"

Game::Game()
{
    ScreenWidth = 800;
    ScreenHeight = 600;
    ScreenBPP = 32;
     ScreenFlags = SDL_HWSURFACE | SDL_DOUBLEBUF;

    thisTime = 0.0;
    lastTime = 0.0;
    deltaTime = 0.0;

    done = false;

    SDL_Init(SDL_INIT_EVERYTHING);

    SDL_WM_SetCaption("SDL Per Pixel Collision", NULL);
    SDL_ShowCursor(0);

    screen = SDL_SetVideoMode(ScreenWidth, ScreenHeight, ScreenBPP, ScreenFlags);
}

Game::~Game()
{
    SDL_Quit();
}

void Game::OnExecute()
{
    while(!done)
    {
        OnThink();
        OnUpdate();
        OnRender();
    }
}

void Game::OnThink()
{
    while(SDL_PollEvent(&event))
    {
        if(event.type == SDL_QUIT)
            done = true;
            
        if(event.type == SDL_KEYDOWN)
            if(event.key.keysym.sym == SDLK_ESCAPE)
                done = true;
    }
}

void Game::OnUpdate()
{
    lastTime = thisTime;
    thisTime = SDL_GetTicks();
    deltaTime = (thisTime - lastTime) / 1000.0;
}

void Game::OnRender()
{
    SDL_FillRect(screen, NULL, 0);

    SDL_Flip(screen);
}

int main(int argc, char* args[])
{
    Game game;
    game.OnExecute();

    return 0;
}
You should be able to compile and run at this point. Now we have a nice 800x600 window prepared for our bidding! The three double variables are used at keep track of elapsed time each tick. You can simply substitute in your favorite Timer class if you wish. I also turn off cursor visibility since we'll be controlling an object with the mouse and we don't want it to obscure our view.

Now we'll need some sort of objects that we can collide together!

Entity.h
#ifndef ENTITY_H
#define ENTITY_H

#include "SDL.h"
#include "SDL_image.h"

struct Vector
{
    float X;
    float Y;

    Vector()
    {
        X = 0.0f;
        Y = 0.0f;
    }
};

class Entity
{
    public:
        Entity(char* filename, int tilesX, int tilesY, double frameRate);
        ~Entity();

    public:
        Vector position;
        Vector origin;

    public:
        SDL_Surface* surface;

        int tilesX;
        int tilesY;
        int tileWidth;
        int tileHeight;
        
        int frame;
        int frameCount;
        
        double frameInterval;
        double frameTimeRemaining;

    public:        
        void Update(double deltaTime);
        void Render(SDL_Surface* screen);
};

#endif
Simple enough, I hope. For each Entity we create, we'll take in a filename for the for the image we'll be loading. If you didn't notice, SDL_image is included, as I'll be working with PNG files with alpha transparency. Next, we take in the tiles across and tiles down in the spritesheet we'll be using. Finally, a frame rate to determine how fast the sprite will animate.

Next, the member variables. I've created a simple Vector struct to hold position and origin information. Position is where the Entity will sit on the screen and origin is the center of the tile currently being drawn. This will make things simpler when we want to draw a sprite centered on it's position. Of course, an SDL_Surface pointer to hold the image data we'll be using. And last, variables to hold information about the spritesheet we'll be using and handling animation.

Finally, two methods to update and render the given Entity. Now let's implement these!

Entity.cpp
#include "Entity.h"

Entity::Entity(char* filename, int tilesX, int tilesY, double frameRate)
{
    this->surface = IMG_Load(filename);

    this->tilesX = tilesX;
    this->tilesY = tilesY;
    this->tileWidth = surface->w / tilesX;
    this->tileHeight = surface->h / tilesY;
    this->frame = 0;
    this->frameCount = tilesX * tilesY;
    this->frameInterval = 1 / frameRate;
    this->frameTimeRemaining = frameInterval;

    this->origin.X = tileWidth / 2.0f;
    this->origin.Y = tileHeight / 2.0f;
}

Entity::~Entity()
{
    SDL_FreeSurface(surface);
}

void Entity::Update(double deltaTime)
{
    frameTimeRemaining -= deltaTime;
    if(frameTimeRemaining < 0)
    {
        frame++;
        frame %= frameCount;
        frameTimeRemaining = frameInterval;
    }
}

void Entity::Render(SDL_Surface* screen)
{
    SDL_Rect location = GetBounds();    
    SDL_Rect clip = GetFrameBounds();
    
    SDL_BlitSurface(surface, &clip, screen, &location);
}
The constructor loads in our image using IMG_Load() and stores all our data about the sprite sheet. The destructor ensures we have no memory leaks by freeing our SDL_Surface. Update chips away at our frameTimeRemaining with a given deltaTime. Once we hit or are under zero, we increase the frame, wrap around to the beginning if need be, and reset our frameTimeRemaining with our given frameInterval. Render finds our location and clip rectangles and then blits the surface to the screen. But wait, we haven't added GetBounds or GetFrameBounds() yet. I'm sure those will be useful to have! Let's get to that!

Add these method definitions in:

Entity.h
    public:
        SDL_Rect GetBounds();
        SDL_Rect GetFrameBounds();
And now we'll implement them:

Entity.cpp
SDL_Rect Entity::GetBounds()
{
    SDL_Rect bounds;
    bounds.x = (Sint16)(position.X - origin.X);
    bounds.y = (Sint16)(position.Y - origin.Y);
    bounds.w = (Sint16)(tileWidth);
    bounds.h = (Sint16)(tileHeight);

    return bounds;
}

SDL_Rect Entity::GetFrameBounds()
{
    SDL_Rect frameBounds;
    frameBounds.x = (Sint16)(frame % tilesX * tileWidth);
    frameBounds.y = (Sint16)(frame / tilesX * tileHeight);
    frameBounds.w = (Sint16)(tileWidth);
    frameBounds.h = (Sint16)(tileHeight);
    
    return frameBounds;
}
GetBounds() takes our position and shifts it over by our origin. This places the position at the center of the sprite, rather than the top left. GetFramesBound() checks what frame we're on and finds the matching coordinates. Very important for animation!

Now lets slap a couple of these suckers into our demo!

Game.h
#include "Entity.h"

class Game
{
    ...

    private:
        Entity* ship;
        Entity* asteroid;
};
Make sure you include Entity.h so we can actually use the class and we'll add two Entity pointers to our Game class.

Game.cpp
Game::Game()
{
    ...

    ship = new Entity("images/ship.png", 4, 3, 10);
    asteroid = new Entity("images/asteroid.png", 5, 6, 30);

    asteroid->position.X = (float)(ScreenWidth / 2);
    asteroid->position.Y = (float)(ScreenHeight / 2);
}

Game::~Game()
{
    delete ship;
    delete asteroid;

    ...
}
Image: Ship
Image: Asteroid
(Special thanks to 3DBuzz for these images.)

We'll now dynamically allocate memory for our two new Entity objects. I have my images sitting in an "images" folder, but you may do whatever you want! I then position the asteroid at the center of the screen. And because we're mindful programmers, we'll delete the allocated memory once we're all done.

Game.cpp
void Game::OnThink()
{
    while(SDL_PollEvent(&event))
    {
        if(event.type == SDL_QUIT)
            done = true;
            
        if(event.type == SDL_KEYDOWN)
            if(event.key.keysym.sym == SDLK_ESCAPE)
                done = true;
            
        if(event.type == SDL_MOUSEMOTION)
        {
            ship->position.X = event.motion.x;
            ship->position.Y = event.motion.y;
        }
    }
}

void Game::OnUpdate()
{
    lastTime = thisTime;
    thisTime = SDL_GetTicks();
    deltaTime = (thisTime - lastTime) / 1000.0;

    ship->Update(deltaTime);
    asteroid->Update(deltaTime);
}

void Game::OnRender()
{
    SDL_FillRect(screen, NULL, 0);

    ship->Render(screen);
    asteroid->Render(screen);

    SDL_Flip(screen);
}
In OnThink, we'll mouse movement to our ship by looking for an SDL_MOUSEMOTION event while polling for events. In OnUpdate, we'll simply call each Entity's Update method with the deltaTime we found. Lastly, in OnRender, we'll just call the Render method by passing our screen.

Compile, run, and give it a whirl! Weeee! We now have two animated sprites, one centered in the screen and one controlled by our mouse. But where's the collision? Oh yeah, we haven't implemented it yet!

We'll need a bit more functionally in our Entity class, so let's work on that. This one's a doozy, so hold on tight! But don't worry, we'll take it one step at a time...

Entity.h
class Entity
{
    ...

    public:
        SDL_Rect NormalizeBounds(const SDL_Rect& rect);

        static SDL_Rect Intersection(const SDL_Rect& boundsA, const SDL_Rect& boundsB);
        static bool CheckCollision(Entity* entityA, Entity* entityB);
        static bool GetAlphaXY(Entity* entity, int x, int y);
};
Entity.cpp
SDL_Rect Entity::NormalizeBounds(const SDL_Rect& rect)
{
    SDL_Rect normalized;
    normalized.x = rect.x - (Sint16)position.X + (Sint16)origin.X + GetFrameBounds().x;
    normalized.y = rect.y - (Sint16)position.Y + (Sint16)origin.Y + GetFrameBounds().y;
    normalized.w = rect.w;
    normalized.h = rect.h;
    
    return normalized;
}
Given the SDL_Rect of a collision rectangle, we want to find what pixels on the sprite sheet correlate to it. A little messy, but it gets the job done.

Entity.cpp
SDL_Rect Entity::Intersection(const SDL_Rect& boundsA, const SDL_Rect& boundsB)
{
    int x1 = Maximum(boundsA.x, boundsB.x);
    int y1 = Maximum(boundsA.y, boundsB.y);
    int x2 = Minimum(boundsA.x + boundsA.w, boundsB.x + boundsB.w);
    int y2 = Minimum(boundsA.y + boundsA.h, boundsB.y + boundsB.h);
    
    int width = x2 - x1;
    int height = y2 - y1;
    
    if(width > 0 && height > 0)
    {
        SDL_Rect intersect = {x1, y1, width, height};
        return intersect;
    }
    else
    {
        SDL_Rect intersect = {0, 0, 0, 0};
        return intersect;
    }
}
Given the two bounds of two entities, we want to find how much they intersect, if at all. If they do, we're given their intersection rectangle, if not, we're given an empty rectangle. For Max and Min, you can either include "cmath" or use a couple macros such as this:
#define Maximum(a, b) ((a > b) ? a : b)
#define Minimum(a, b) ((a < b) ? a : b)
Entity.cpp
bool Entity::CheckCollision(Entity* entityA, Entity* entityB)
{
    SDL_Rect collisionRect = Intersection(entityA->GetBounds(), entityB->GetBounds());

    if(collisionRect.w == 0 && collisionRect.h == 0)
        return false;

    SDL_Rect normalA = entityA->NormalizeBounds(collisionRect);
    SDL_Rect normalB = entityB->NormalizeBounds(collisionRect);

    for(int y = 0; y < collisionRect.h; y++)
        for(int x = 0; x < collisionRect.w; x++)
            if(GetAlphaXY(entityA, normalA.x + x, normalA.y + y) && GetAlphaXY(entityB, normalB.x + x, normalB.y + y))
                return true;

    return false;
}
This is where bulk of our per pixel collision check happens. First, we ensure there's even a bounding box collision. No use going through all the trouble when we know nothing will happen. Then we normalize the bounds of each entity with the found collision rectangle. This will give us the region of pixels we'll be comparing against each other. You'll notice this GetAlphaXY() function. This is where we'll get down into the pixels and determine if they're solid enough for collision. You'll see that it's called twice in one if-statement. This is because we're searching for a solid enough pixel in each surface at the same position. Once that is found, we'll confirm a hit!

Entity.cpp
bool Entity::GetAlphaXY(Entity* entity, int x, int y)
{
    int bpp = entity->surface->format->BytesPerPixel;
    Uint8* p = (Uint8*)entity->surface->pixels + y * entity->surface->pitch + x * bpp;
    Uint32 pixelColor;
    
    switch(bpp)
    {
        case(1):
            pixelColor = *p;
            break;
        case(2):
            pixelColor = *(Uint16*)p;
            break;
        case(3):
            if(SDL_BYTEORDER == SDL_BIG_ENDIAN)
                pixelColor = p[0] << 16 | p[1] << 8 | p[2];
            else
                pixelColor = p[0] | p[1] << 8 | p[2] << 16;
            break;
        case(4):
            pixelColor = *(Uint32*)p;
            break;
    }
    
    Uint8 red, green, blue, alpha;
    SDL_GetRGBA(pixelColor, entity->surface->format, &red, &green, &blue, &alpha);

    return alpha > 200;
}
Oh my, some crazy looking stuff here! It's not that bad. Let me explain a few things here.

We're passing in a pointer to an Entity and an (x,y) coordinate. All we're doing in this function is finding the pixel at that coordinate and determining what colors its composed of. The first two lines give us a pointer to the pixel in question. The funky looking switch-statement is finding the color composition depending on the image's bytes-per-pixel format, either 8-bit, 16-bit, 24-bit, or 32-bit. In our case, it will always land on case(4), but this should give you an idea on how to expand to other formats.

Finally, we're grabbing the RGBA components of the pixel using SDL_GetRGBA. All we care about is alpha, but you can experiment with collision where hits will only happen when a pixel is red or blue enough. Alpha will range between 0 and 255. I wanted collision to happen with not just pixels that were completely opaque, but not too transparent. I found 200 to be a nice number, but you're free to tweak as you please.

Well that's it! Our Entity class has the functionally to test for per pixel collision... so lets show it off!

Game.cpp
void Game::OnRender()
{
    SDL_FillRect(screen, NULL, 0);

    SDL_Rect collisionRect = Entity::Intersection(ship->GetBounds(), asteroid->GetBounds());

    if(collisionRect.w != 0 && collisionRect.h != 0)
        if(Entity::CheckCollision(ship, asteroid))
            SDL_FillRect(screen, &collisionRect, SDL_MapRGB(screen->format, 255, 0, 0));
        else
            SDL_FillRect(screen, &collisionRect, SDL_MapRGB(screen->format, 0, 255, 0));

    ship->Render(screen);
    asteroid->Render(screen);

    SDL_Flip(screen);
}
Adding this checks for collision between our ship and asteroid. When bounding box collision happens, a green box will be drawn behind them. When per pixel collision happens, the box will turn red!

Well, that's about it. Run, compile, and enjoy! You now have per pixel collision checks between your two Entity objects! Feel free to tweak numbers, use different images, or control them in different ways! I've given you the foundation, now go out there and create some interesting implementations!

Here's the final code in case you may have some errors and need to check against my own.

Game.h
#ifndef GAME_H
#define GAME_H

#include "Entity.h"

class Game
{
    public:
        Game();
        ~Game();

        void OnExecute();

        void OnThink();
        void OnUpdate();
        void OnRender();

    private:
        int ScreenWidth;
        int ScreenHeight;
        int ScreenBPP;
        Uint32 ScreenFlags;
        
        bool done;

        double thisTime;
        double lastTime;
        double deltaTime;

        SDL_Surface* screen;
        SDL_Event event;

        Entity* ship;
        Entity* asteroid;
};

#endif
Game.cpp
#include "Game.h"

Game::Game()
{
    ScreenWidth = 800;
    ScreenHeight = 600;
    ScreenBPP = 32;
    ScreenFlags = SDL_HWSURFACE | SDL_DOUBLEBUF;

    done = false;

    thisTime = 0.0;
    lastTime = 0.0;
    deltaTime = 0.0;

    SDL_Init(SDL_INIT_EVERYTHING);

    SDL_WM_SetCaption("SDL Per Pixel Collision", NULL);
    SDL_ShowCursor(0);

    screen = SDL_SetVideoMode(ScreenWidth, ScreenHeight, ScreenBPP, ScreenFlags);

    ship = new Entity("images/ship.png", 4, 3, 10);
    asteroid = new Entity("images/asteroid.png", 5, 6, 30);

    asteroid->position.X = (float)(ScreenWidth / 2);
    asteroid->position.Y = (float)(ScreenHeight / 2);
}

Game::~Game()
{
    delete ship;
    delete asteroid;

    SDL_Quit();
}

void Game::OnExecute()
{
    while(!done)
    {
        OnThink();
        OnUpdate();
        OnRender();
    }
}

void Game::OnThink()
{
    while(SDL_PollEvent(&event))
    {
        if(event.type == SDL_QUIT)
            done = true;
            
        if(event.type == SDL_KEYDOWN)
            if(event.key.keysym.sym == SDLK_ESCAPE)
                done = true;
            
        if(event.type == SDL_MOUSEMOTION)
        {
            ship->position.X = event.motion.x;
            ship->position.Y = event.motion.y;
        }
    }
}

void Game::OnUpdate()
{
    lastTime = thisTime;
    thisTime = SDL_GetTicks();
    deltaTime = (thisTime - lastTime) / 1000.0;

    ship->Update(deltaTime);
    asteroid->Update(deltaTime);
}

void Game::OnRender()
{
    SDL_FillRect(screen, NULL, 0);

    if(collisionRect.w != 0 && collisionRect.h != 0)
        if(Entity::CheckCollision(ship, asteroid))
            SDL_FillRect(screen, &collisionRect, SDL_MapRGB(screen->format, 255, 0, 0));
        else
            SDL_FillRect(screen, &collisionRect, SDL_MapRGB(screen->format, 0, 255, 0));

    ship->Render(screen);
    asteroid->Render(screen);

    SDL_Flip(screen);
}

int main(int argc, char* args[])
{
    Game game;
    game.OnExecute();

    return 0;
}

Entity.h
#ifndef ENTITY_H
#define ENTITY_H

#include "SDL.h"
#include "SDL_image.h"

struct Vector
{
    float X;
    float Y;

    Vector()
    {
        X = 0.0f;
        Y = 0.0f;
    }
};

class Entity
{
    public:
        Entity(char* filename, int tilesX, int tilesY, double frameRate);
        ~Entity();

    public:
        Vector position;
        Vector origin;

    public:
        SDL_Surface* surface;

        int tilesX;
        int tilesY;
        int tileWidth;
        int tileHeight;
        
        int frame;
        int frameCount;
        
        double frameInterval;
        double frameTimeRemaining;

    public:        
        void Update(double deltaTime);
        void Render(SDL_Surface* screen);

    public:    
        SDL_Rect GetBounds();
        SDL_Rect GetFrameBounds();
        SDL_Rect NormalizeBounds(const SDL_Rect& rect);

        static SDL_Rect Intersection(const SDL_Rect& boundsA, const SDL_Rect& boundsB);
        static bool CheckCollision(Entity* entityA, Entity* entityB);
        static bool GetAlphaXY(Entity* entity, int x, int y);
};

#endif
Entity.cpp
#include "Entity.h"

#define Maximum(a, b) ((a > b) ? a : b)
#define Minimum(a, b) ((a < b) ? a : b)

Entity::Entity(char* filename, int tilesX, int tilesY, double frameRate)
{
    this->surface = IMG_Load(filename);

    this->tilesX = tilesX;
    this->tilesY = tilesY;
    this->tileWidth = surface->w / tilesX;
    this->tileHeight = surface->h / tilesY;
    this->frame = 0;
    this->frameCount = tilesX * tilesY;
    this->frameInterval = 1 / frameRate;
    this->frameTimeRemaining = frameInterval;

    this->origin.X = tileWidth / 2.0f;
    this->origin.Y = tileHeight / 2.0f;
}

Entity::~Entity()
{
    SDL_FreeSurface(surface);
}

void Entity::Update(double deltaTime)
{
    frameTimeRemaining -= deltaTime;
    if(frameTimeRemaining < 0)
    {
        frame++;
        frame %= frameCount;
        frameTimeRemaining = frameInterval;
    }
}

void Entity::Render(SDL_Surface* screen)
{
    SDL_Rect location = GetBounds();    
    SDL_Rect clip = GetFrameBounds();
    
    SDL_BlitSurface(surface, &clip, screen, &location);
}

SDL_Rect Entity::GetBounds()
{
    SDL_Rect bounds;
    bounds.x = (Sint16)(position.X - origin.X);
    bounds.y = (Sint16)(position.Y - origin.Y);
    bounds.w = (Sint16)(tileWidth);
    bounds.h = (Sint16)(tileHeight);

    return bounds;
}

SDL_Rect Entity::GetFrameBounds()
{
    SDL_Rect frameBounds;
    frameBounds.x = (Sint16)(frame % tilesX * tileWidth);
    frameBounds.y = (Sint16)(frame / tilesX * tileHeight);
    frameBounds.w = (Sint16)(tileWidth);
    frameBounds.h = (Sint16)(tileHeight);
    
    return frameBounds;
}

SDL_Rect Entity::NormalizeBounds(const SDL_Rect& rect)
{
    SDL_Rect normalized;
    normalized.x = rect.x - (Sint16)position.X + (Sint16)origin.X + GetFrameBounds().x;
    normalized.y = rect.y - (Sint16)position.Y + (Sint16)origin.Y + GetFrameBounds().y;
    normalized.w = rect.w;
    normalized.h = rect.h;
    
    return normalized;
}

SDL_Rect Entity::Intersection(const SDL_Rect& boundsA, const SDL_Rect& boundsB)
{
    int x1 = Maximum(boundsA.x, boundsB.x);
    int y1 = Maximum(boundsA.y, boundsB.y);
    int x2 = Minimum(boundsA.x + boundsA.w, boundsB.x + boundsB.w);
    int y2 = Minimum(boundsA.y + boundsA.h, boundsB.y + boundsB.h);
    
    int width = x2 - x1;
    int height = y2 - y1;
    
    if(width > 0 && height > 0)
    {
        SDL_Rect intersect = {x1, y1, width, height};
        return intersect;
    }
    else
    {
        SDL_Rect intersect = {0, 0, 0, 0};
        return intersect;
    }
}

bool Entity::CheckCollision(Entity* entityA, Entity* entityB)
{
    SDL_Rect collisionRect = Intersection(entityA->GetBounds(), entityB->GetBounds());

    if(collisionRect.w == 0 && collisionRect.h == 0)
        return false;

    SDL_Rect normalA = entityA->NormalizeBounds(collisionRect);
    SDL_Rect normalB = entityB->NormalizeBounds(collisionRect);

    for(int y = 0; y < collisionRect.h; y++)
        for(int x = 0; x < collisionRect.w; x++)
            if(GetAlphaXY(entityA, normalA.x + x, normalA.y + y) && GetAlphaXY(entityB, normalB.x + x, normalB.y + y))
                return true;

    return false;
}

bool Entity::GetAlphaXY(Entity* entity, int x, int y)
{
    int bpp = entity->surface->format->BytesPerPixel;
    Uint8* p = (Uint8*)entity->surface->pixels + y * entity->surface->pitch + x * bpp;
    Uint32 pixelColor;
    
    switch(bpp)
    {
        case(1):
            pixelColor = *p;
            break;
        case(2):
            pixelColor = *(Uint16*)p;
            break;
        case(3):
            if(SDL_BYTEORDER == SDL_BIG_ENDIAN)
                pixelColor = p[0] << 16 | p[1] << 8 | p[2];
            else
                pixelColor = p[0] | p[1] << 8 | p[2] << 16;
            break;
        case(4):
            pixelColor = *(Uint32*)p;
            break;
    }
    
    Uint8 red, green, blue, alpha;
    SDL_GetRGBA(pixelColor, entity->surface->format, &red, &green, &blue, &alpha);

    return alpha > 200;
}
I hope you enjoyed my first tutorial for SDLTutorials.com and learned a lot! I plan to do more in the future!