Source: Simple Collision Detection for SFML 2

ahnonay edited this page Jul 28, 2013 · 4 revisions
Clone this wiki locally

Simple Collision Detection

Overview

This is an adaptation of the Simple Collision Detection code that was written for SFML 1. Now it works with SFML 2. Changes include:

  • The alpha values of a texture are now stored in a bitmask, since SFML no longer uses sf::Images for rendering. Creating this bitmask for an already existing texture takes time (because of a call to sf::Texture::copyToImage) so use Collision::CreateTextureAndBitmask to load an image file into a texture and create the bitmask at the same time.
  • The helper functions of the original version are omitted. sf::Sprite::getGlobalBounds now does what Collision::GetAABB did before.
  • sf::Sprite now longer returns its size so a couple of extra calculations are needed to take scaling into account.
  • The BoundingBoxTest was rewritten completely. It now uses the Seperating Axis Theorem.

Code

To use this code save the following two files and include them into your current SFML project

Collision.h

/* 
 * File:   collision.h
 * Authors: Nick Koirala (original version), ahnonay (SFML2 compatibility)
 *
 * Collision Detection and handling class
 * For SFML2.

Notice from the original version:

(c) 2009 - LittleMonkey Ltd

This software is provided 'as-is', without any express or
implied warranty. In no event will the authors be held
liable for any damages arising from the use of this software.

Permission is granted to anyone to use this software for any purpose,
including commercial applications, and to alter it and redistribute
it freely, subject to the following restrictions:

1. The origin of this software must not be misrepresented;
   you must not claim that you wrote the original software.
   If you use this software in a product, an acknowledgment
   in the product documentation would be appreciated but
   is not required.

2. Altered source versions must be plainly marked as such,
   and must not be misrepresented as being the original software.

3. This notice may not be removed or altered from any
   source distribution.

 *
 * Created on 30 January 2009, 11:02
 */

#ifndef COLLISION_H
#define COLLISION_H

namespace Collision {
    //////
    /// Test for a collision between two sprites by comparing the alpha values of overlapping pixels
    /// Supports scaling and rotation
    /// AlphaLimit: The threshold at which a pixel becomes "solid". If AlphaLimit is 127, a pixel with
    /// alpha value 128 will cause a collision and a pixel with alpha value 126 will not.
    /// 
    /// This functions creates bitmasks of the textures of the two sprites by
    /// downloading the textures from the graphics card to memory -> SLOW!
    /// You can avoid this by using the "CreateTextureAndBitmask" function
    //////
    bool PixelPerfectTest(const sf::Sprite& Object1 ,const sf::Sprite& Object2, sf::Uint8 AlphaLimit = 0);

    //////
    /// Replaces Texture::loadFromFile
    /// Load an imagefile into the given texture and create a bitmask for it
    /// This is much faster than creating the bitmask for a texture on the first run of "PixelPerfectTest"
    /// 
    /// The function returns false if the file could not be opened for some reason
    //////
    bool CreateTextureAndBitmask(sf::Texture &LoadInto, const std::string& Filename);

    //////
    /// Test for collision using circle collision dection
    /// Radius is averaged from the dimensions of the sprite so
    /// roughly circular objects will be much more accurate
    //////
    bool CircleTest(const sf::Sprite& Object1, const sf::Sprite& Object2);

    //////
    /// Test for bounding box collision using the Seperating Axis Theorem
    /// Supports scaling and rotation
    //////
    bool BoundingBoxTest(const sf::Sprite& Object1, const sf::Sprite& Object2);
}

#endif  /* COLLISION_H */

Collision.cpp

/* 
 * File:   collision.cpp
 * Author: Nick (original version), ahnonay (SFML2 compatibility)
 */
#include <SFML\Graphics.hpp>
#include <map>
#include "Collision.h"

namespace Collision
{
    class BitmaskManager
    {
    public:
        ~BitmaskManager() {
            std::map<const sf::Texture*, sf::Uint8*>::const_iterator end = Bitmasks.end();
            for (std::map<const sf::Texture*, sf::Uint8*>::const_iterator iter = Bitmasks.begin(); iter!=end; iter++)
                delete [] iter->second;
        }

        sf::Uint8 GetPixel (const sf::Uint8* mask, const sf::Texture* tex, unsigned int x, unsigned int y) {
            if (x>tex->getSize().x||y>tex->getSize().y)
                return 0;

            return mask[x+y*tex->getSize().x];
        }

        sf::Uint8* GetMask (const sf::Texture* tex) {
            sf::Uint8* mask;
            std::map<const sf::Texture*, sf::Uint8*>::iterator pair = Bitmasks.find(tex);
            if (pair==Bitmasks.end())
            {
                sf::Image img = tex->copyToImage();
                mask = CreateMask (tex, img);
            }
            else
                mask = pair->second;

            return mask;
        }

        sf::Uint8* CreateMask (const sf::Texture* tex, const sf::Image& img) {
            sf::Uint8* mask = new sf::Uint8[tex->getSize().y*tex->getSize().x];

            for (unsigned int y = 0; y<tex->getSize().y; y++)
            {
                for (unsigned int x = 0; x<tex->getSize().x; x++)
                    mask[x+y*tex->getSize().x] = img.getPixel(x,y).a;
            }

            Bitmasks.insert(std::pair<const sf::Texture*, sf::Uint8*>(tex,mask));

            return mask;
        }
    private:
        std::map<const sf::Texture*, sf::Uint8*> Bitmasks;
    };

    BitmaskManager Bitmasks;

    bool PixelPerfectTest(const sf::Sprite& Object1, const sf::Sprite& Object2, sf::Uint8 AlphaLimit) {
        sf::FloatRect Intersection; 
        if (Object1.getGlobalBounds().intersects(Object2.getGlobalBounds(), Intersection)) {
            sf::IntRect O1SubRect = Object1.getTextureRect();
            sf::IntRect O2SubRect = Object2.getTextureRect();

            sf::Uint8* mask1 = Bitmasks.GetMask(Object1.getTexture());
            sf::Uint8* mask2 = Bitmasks.GetMask(Object2.getTexture());

            // Loop through our pixels
            for (int i = Intersection.left; i < Intersection.left+Intersection.width; i++) {
                for (int j = Intersection.top; j < Intersection.top+Intersection.height; j++) {

                    sf::Vector2f o1v = Object1.getInverseTransform().transformPoint(i, j);
                    sf::Vector2f o2v = Object2.getInverseTransform().transformPoint(i, j);

                    // Make sure pixels fall within the sprite's subrect
                    if (o1v.x > 0 && o1v.y > 0 && o2v.x > 0 && o2v.y > 0 &&
                        o1v.x < O1SubRect.width && o1v.y < O1SubRect.height &&
                        o2v.x < O2SubRect.width && o2v.y < O2SubRect.height) {

                            if (Bitmasks.GetPixel(mask1, Object1.getTexture(), (int)(o1v.x)+O1SubRect.left, (int)(o1v.y)+O1SubRect.top) > AlphaLimit &&
                                Bitmasks.GetPixel(mask2, Object2.getTexture(), (int)(o2v.x)+O2SubRect.left, (int)(o2v.y)+O2SubRect.top) > AlphaLimit)
                                return true;

                    }
                }
            }
        }
        return false;
    }

    bool CreateTextureAndBitmask(sf::Texture &LoadInto, const std::string& Filename)
    {
        sf::Image img;
        if (!img.loadFromFile(Filename))
            return false;
        if (!LoadInto.loadFromImage(img))
            return false;

        Bitmasks.CreateMask(&LoadInto, img);
        return true;
    }

    sf::Vector2f GetSpriteCenter (const sf::Sprite& Object)
    {
        sf::FloatRect AABB = Object.getGlobalBounds();
        return sf::Vector2f (AABB.left+AABB.width/2.f, AABB.top+AABB.height/2.f);
    }

    sf::Vector2f GetSpriteSize (const sf::Sprite& Object)
    {
        sf::IntRect OriginalSize = Object.getTextureRect();
        sf::Vector2f Scale = Object.getScale();
        return sf::Vector2f (OriginalSize.width*Scale.x, OriginalSize.height*Scale.y);
    }

    bool CircleTest(const sf::Sprite& Object1, const sf::Sprite& Object2) {
        sf::Vector2f Obj1Size = GetSpriteSize(Object1);
        sf::Vector2f Obj2Size = GetSpriteSize(Object2);
        float Radius1 = (Obj1Size.x + Obj1Size.y) / 4;
        float Radius2 = (Obj2Size.x + Obj2Size.y) / 4;

        sf::Vector2f Distance = GetSpriteCenter(Object1)-GetSpriteCenter(Object2);

        return (Distance.x * Distance.x + Distance.y * Distance.y <= (Radius1 + Radius2) * (Radius1 + Radius2));
    }

    class OrientedBoundingBox // Used in the BoundingBoxTest
    {
    public:
        OrientedBoundingBox (const sf::Sprite& Object) // Calculate the four points of the OBB from a transformed (scaled, rotated...) sprite
        {
            sf::Transform trans = Object.getTransform();
            sf::IntRect local = Object.getTextureRect();
            Points[0] = trans.transformPoint(0.f, 0.f);
            Points[1] = trans.transformPoint(local.width, 0.f);
            Points[2] = trans.transformPoint(local.width, local.height);
            Points[3] = trans.transformPoint(0.f, local.height);
        }

        sf::Vector2f Points[4];

        void ProjectOntoAxis (const sf::Vector2f& Axis, float& Min, float& Max) // Project all four points of the OBB onto the given axis and return the dotproducts of the two outermost points
        {
            Min = (Points[0].x*Axis.x+Points[0].y*Axis.y);
            Max = Min;
            for (int j = 1; j<4; j++)
            {
                float Projection = (Points[j].x*Axis.x+Points[j].y*Axis.y);

                if (Projection<Min)
                    Min=Projection;
                if (Projection>Max)
                    Max=Projection;
            }
        }
    };

    bool BoundingBoxTest(const sf::Sprite& Object1, const sf::Sprite& Object2) {
        OrientedBoundingBox OBB1 (Object1);
        OrientedBoundingBox OBB2 (Object2);

        // Create the four distinct axes that are perpendicular to the edges of the two rectangles
        sf::Vector2f Axes[4] = {
            sf::Vector2f (OBB1.Points[1].x-OBB1.Points[0].x,
            OBB1.Points[1].y-OBB1.Points[0].y),
            sf::Vector2f (OBB1.Points[1].x-OBB1.Points[2].x,
            OBB1.Points[1].y-OBB1.Points[2].y),
            sf::Vector2f (OBB2.Points[0].x-OBB2.Points[3].x,
            OBB2.Points[0].y-OBB2.Points[3].y),
            sf::Vector2f (OBB2.Points[0].x-OBB2.Points[1].x,
            OBB2.Points[0].y-OBB2.Points[1].y)
        };

        for (int i = 0; i<4; i++) // For each axis...
        {
            float MinOBB1, MaxOBB1, MinOBB2, MaxOBB2;

            // ... project the points of both OBBs onto the axis ...
            OBB1.ProjectOntoAxis(Axes[i], MinOBB1, MaxOBB1);
            OBB2.ProjectOntoAxis(Axes[i], MinOBB2, MaxOBB2);

            // ... and check whether the outermost projected points of both OBBs overlap.
            // If this is not the case, the Seperating Axis Theorem states that there can be no collision between the rectangles
            if (!((MinOBB2<=MaxOBB1)&&(MaxOBB2>=MinOBB1)))
                return false;
        }
        return true;
    }
}