# Collision Detection. SAT implementation issue. Randy Gaul

## Recommended Posts

I'm trying to implement OBB vs OBB SAT collision from Randy Gaul's article.

I have been playing with it for days, but I can't figure it out why it doesn't work.

I am storing all vertex positions of each box, and also each edge normal on two lists. Then I use them on the algorithm, I tried a lot of changes to make it work but no luck.

This is my C++ code:

QVector2D Entity::getSupport(QVector2D dir)
{
float bestProjection = -std::numeric_limits<float>::max();

QVector2D bestVertex;

for(quint32 i = 0; i < verticesList.count(); ++i)
{
QVector2D v = verticesList.at(i);

float projection = QVector2D::dotProduct(v,dir);

if(projection > bestProjection)
{
bestVertex = v;
bestProjection = projection;
}
}

return bestVertex;
}

qreal Collision::FindAxisLeastPenetration(Entity *A, Entity *B )
{
float bestDistance = -std::numeric_limits<float>::max();

for(quint32 k = 0; k < A->verticesList.count() ; ++k)
{
QVector2D n = A->normalList.at(k);
QVector2D s = B->getSupport(-n);
QVector2D v = A->verticesList.at(k);
QVector2D r = s-v;
qreal d = QVector2D::dotProduct(n,r);

if(d > bestDistance)
{
bestDistance = d;
}
}
return bestDistance;
}

if (coli->FindAxisLeastPenetration(player,player2) <0 && FindAxisLeastPenetration(player2,player) <0 )
{
qDebug() << "Collision detected ";
}

Edited by Franco Gentili

##### Share on other sites

I don't have time to look too carefully at your code, but since you want to do OBB against OBB there is a good implementation by Erin Catto here for 2D: http://box2d.org/files/GDC2006/Box2D_Lite.zip

Another great resource for this code is Dirk's 2013 GDC lecture. His lecture is where I really learned the most about implementing a separating axis test. This thread has some good links: http://bulletphysics.org/Bullet/phpBB3/viewtopic.php?f=4&t=9109

##### Share on other sites

I think you are missing the transforms. Speculating about what your code does it should more look like this.

qreal Collision::FindAxisLeastPenetration(Entity *A, Entity *B )
{
float bestDistance = -std::numeric_limits<float>::max();

for(quint32 k = 0; k < A->verticesList.count() ; ++k)
{
QVector2D n = A->transformVectorToWorld( A->normalList.at(k) );
QVector2D s = B->getSupport(-n);
QVector2D v = A->transformPointToWorld( A->verticesList.at(k) );
QVector2D r = s-v;
qreal d = QVector2D::dotProduct(n,r);

if(d > bestDistance)
{
bestDistance = d;
}
}
return bestDistance;
}

Same for the support function:

QVector2D Entity::getSupport(QVector2D worldDir)
{
QVector2D dir = transformVectorToLocal( worldDir );

float bestProjection = -std::numeric_limits<float>::max();
QVector2D bestVertex;

for(quint32 i = 0; i < verticesList.count(); ++i)
{
QVector2D v = verticesList.at(i);
float projection = QVector2D::dotProduct(v,dir);

if(projection > bestProjection)
{
bestVertex = v;
bestProjection = projection;
}
}

return transformPointToWorld(bestVertex);
}

The other thing to watch out for is that the vertex you grab is on the actual plane of the edge. I assume you have ordered your normals and vertices accordingly, but I would double check.

Edited by DonDickieD

## Create an account

Register a new account

• 10
• 17
• 9
• 14
• 41
• ### Similar Content

• I am developing a 2d game using unreal engine 4 in which the user drags and drops a sword. I want the sword to follow the position of my finger. At the moment, when I drag the sword, it moves at an offset from my finger. The game has been packaged to an ipad and I have set up the functionality using blueprints. Pseudo code On Drag  (){ finger position = sword position on screen
on drop = finger position on release from screen = position of sword
}
How do I make the sword follow the position of my finger as I drag it?

• I am having an issue with touch inputs on an iPad. I have a UI widget item on screen that I am trying to drag. When I test the game on a PC the widget item works correctly. When I try to drag the widget item on a touch screen (iPad) the position of the item is nowhere near my finger. So as I am dragging the item it doesn't follow my finger, however when I drag the item using a mouse on a PC the widget moves in the correct position. In project settings I have enabled the use mouse for touch option but the issue still persists. This has been set up in unreal engine 4 and I am trying to get the correct functionality for a tablet device. Any help would be much appreciated on how I would get the UI widget to follow my finger when I drag it.

• By Wraithe
I am wondering how many DirectSound buffers I should maintain to find a good balance between constant reading of sound files and hanging on to upwards of 30-50 sound effects at once?
I am making a small 2D game engine using OpenGL, DirectSound and Win32 APIs. I am thinking I would only need two buffers for music so that I can fade them in and out, maybe adding a third for those instances where there is competing music (think of a character walking past someone's radio).
As for sound, I originally thought I could allow myself to set the number of sound buffers at the audio classes' initialization, storing them in an array for faster access, and then keeping a queue of audio requests that take up the first free buffer. Then I worried about a string of the same sound playing and thought maybe I should keep two buffers for every currently loaded sound effect, and whenever that sound effect is called while it is already playing I could do an extremely fast fade between the two buffers set aside for that sound effect.
I am sure I am just over-thinking this. I would imagine having three streaming buffers for music and a sound effects queue with 8 buffers is more than enough, but I have never really dealt with low-level sound before. What would people who have worked with lower-level audio recommend?
• By vvvvv
oh boy howdy howdy
i know little to nothing about game design and programming but i am a seasoned artist and am a huge gamer always have been
i recently got a very small taste of the industry if you can even call it that from the last UE4 game jam i helped with voice acting concept art writing and vector art
i absolutely loved it and am already itching to learn and do more but??? i have no idea how to go about it
the person i was working with during the game jam is years ahead of me and is already looking into getting me into some contract work and teaching me 3d modeling/painting/sculpting but at the moment hes currently busy with making a game for RTX!
while hes busy i thought id delve into some forums and get my feet wet
any info or tips on how or where to get started would be amazing thanks!
• By kirito
hey guys i wanna know how much of everything it costs to make a game kind of aberoth
if u haven't heared about it take a fast look here:http://aberoth.com

• Hey There,
I am a developer and Im working on a blockchain based infinite runner type game. Right now, I am working on releasing the beta version with a couple other game developers, but would love to expand the team and have other talented and bright people contributing. The game portion of the project isnt very complicated, and wouldnt require anyone to pull thier hair out for it.
Thank you!

• I am trying to build a particle system for unity based on "Destiny particle architecture " released in Siggraph.
I encounter a problem in trying to understand how they iterated this:

Converted to spline function and the result is

i wanted to know how did they converted the function in the editor to represent the graph ??

• Overview
Welcome to the 2D UFO game guide using the Orx Portable Game Engine. My aim for this tutorial is to take you through all the steps to build a UFO game from scratch.
The aim of our game is to allow the player to control a UFO by applying physical forces to move it around. The player must collect pickups to increase their score to win.
I should openly acknowledge that this series is cheekily inspired by the 2D UFO tutorial written for Unity.
It makes an excellent comparison of the approaches between Orx and Unity. It is also a perfect way to highlight one of the major parts that makes Orx unique among other game engines, its Data Driven Configuration System.
You'll get very familiar with this system very soon. It's at the very heart of just about every game written using Orx.
If you are very new to game development, don't worry. We'll take it nice and slow and try to explain everything in very simple terms. The only knowledge you will need is some simple C++.
I'd like say a huge thank you to FullyBugged for providing the graphics for this series of articles.

What are we making?
Visit the video below to see the look and gameplay of the final game:
Getting Orx
The latest up to date version of Orx can be cloned from github and set up with:
git clone https://github.com/orx/orx.git Once cloning has completed, the setup script in the root of the files will start automatically for you. This script creates an $ORX environment variable for your system. The variable will point to the code subfolder where you cloned Orx. Why? I'll get to the in a moment, but it'll make your life easier. The setup script also creates several projects for various IDEs and operating system: Visual Studio, Codelite, Code::Blocks, and gmake. You can pick one of these projects to build the Orx library. Building the Orx Library While the Orx headers are provided, you need to compile the Orx library so that your own games can link to it. Because the setup script has already created a suitable a project for you (using premake), you can simply open one for your chosen OS/IDE and compile the Orx library yourself. There are three configurations to compile: Debug, Profile and Release. You will need to compile all three. For more details on compiling the Orx lbrary at: http://orx-project.org/wiki/en/tutorials/cloning_orx_from_github at the Orx learning wiki. The$ORX Environment Variable
I promised I would explain what this is for. Once you have compiled all three orx library files, you will find them in the code/lib/dynamic folder:
orx.dll orxd.dll orxp.dll Also, link libraries will be available in the same folder:
orx.lib orxd.lib orxp.lib When it comes time to create our own game project, we would normally be forced to copy these library files and includes into every project.
A better way is to have our projects point to the libraries and includes located at the folder that the $ORX environment variable points to (for example: C:\Dev\orx\code). This means that your projects will always know where to find the Orx library. And should you ever clone and re-compile a new version of Orx, your game projects can make immediate use of the newer version. Setting up a 2D UFO Project Now the you have the Orx libraries cloned and compiled, you will need a blank project for your game. Supported options are: Visual Studio, CodeLite, Code::Blocks, XCode or gmake, depending on your operating system. Once you have a game project, you can use it to work through the steps in this tutorial. Orx provides a very nice system for auto creating game projects for you. In the root of the Orx repo, you will find either the init.bat (for Windows) or init.sh (Mac/Linux) command. Create a project for our 2D game from the command line in the Orx folder and running: init c:\temp\ufo or init.sh ~/ufo Orx will create a project for each IDE supported by your OS at the specified location. You can copy this folder anywhere, and your project will always compile and link due to the$ORX environment variable. It knows where the libraries and includes are for Orx.
Open your project using your favourite IDE from within the ufo/build folder.
When the blank template loads, there are two main folders to note in your solution:
config src Firstly, the src folder contains a single source file, ufo.cpp. This is where we will add the c++ code for the game. The config folder contains configuration files for our game.
What is config?
Orx is a data driven 2D game engine. Many of the elements in your game, like objects, spawners, music etc, do not need to be defined in code. They can be defined (or configured) using config files.
You can make a range of complex multi-part objects with special behaviours and effects in Orx, and bring them into your game with a single line of code. You'll see this in the following chapters of this guide.
There are three ufo config files in the config folder but for this guide, only one will actually be used in our game. This is:
ufo.ini All our game configuration will be done there.
Over in the Orx library repo folder under orx/code/bin, there are two other config files:
CreationTemplate.ini SettingsTemplate.ini These are example configs and they list all the properties and values that are available to you. We will mainly concentrate on referring to the CreationTemplate.ini, which is for objects, sounds, etc. It's good idea to include these two files into your project for easy reference.
Alternatively you can view these online at https://github.com/orx/orx/blob/master/code/bin/CreationTemplate.ini and here: https://github.com/orx/orx/blob/master/code/bin/SettingsTemplate.ini

The code template
Now to take a look at the basic ufo.cpp and see what is contained there.
The first function is the Init() function.
This function will execute when the game starts up. Here you can create objects have been defined in the config, or perform other set up tasks like handlers. We'll do both of these soon.
The Run() function is executed every main clock cycle. This is a good place to continually perform a task. Though there are better alternatives for this, and we will cover those later. This is mainly used to check for the quit key.
The Exit() function is where memory is cleaned up when your game quits. Orx cleans up nicely after itself. We won't use this function as part of this guide.
The Bootstrap() function is an optional function to use. This is used to tell Orx where to find the first config file for use in our game (ufo.ini). There is another way to do this, but for now, we'll use this function to inform Orx of the config.
Then of course, the main() function. We do not need to use this function in this guide.
Now that we have everything we need to get start, you should be able to compile successfully. Run the program and an Orx logo will appear slowly rotating.

Great. So now you have everything you need to start building the UFO game.
If you experience an issue compiling, check the troubleshooting article for Orx projects    for help.

Setting up the game assets
Our game will have a background, a UFO which the player will control, and some pickups that the player can collect.
The UFO will be controlled by the player using the cursor keys.
First you'll need the assets to make the game. You can download the file  assets-for-orx-ufo-game.zip which contains:
The background file (background.png😞

The UFO and Pickup sprite images (ufo.png and pickup.png😞

And a pickup sound effect (pickup.ogg😞
pickup.ogg
Copy the .png files into your data/texture folder
Copy the .ogg file into your data/sound folder.
Now these files can be accessed by your project and included in the game.

Setting up the Playfield
We will start by setting up the background object. This is done using config.
Open the ufo.ini config file in your editor and add the following:

[BackgroundGraphic] Texture = background.png Pivot = center
The BackgroundGraphic defined here is called a Graphic Section. It has two properties defined. The first is Texture which has been set as background.png.
The Orx library knows where to find this image, due to the properties set in the Resource section:

[Resource] Texture = ../../data/texture
So any texture files that are required (just like in our BackgroundGraphic section) will be located in the ../../data/texture folder.
The second parameter is Pivot. A pivot is the handle (or sometimes “hotspot” in other frameworks). This is set to be center. The position is 0,0 by default, just like the camera. The effect is to ensure the background sits in the center of our game window.
There are other values available for Pivot. To see the list of values, open the CreationTemplate.ini file in your editor. Scroll to the GraphicTemplate section and find Pivot in the list. There you can see all the possible values that could be used.
top left is also a typical value.
We need to define an object that will make use of this graphic. This will be the actual entity that is used in the game:

[BackgroundObject] Graphic = BackgroundGraphic Position = (0, 0, 0)
The Graphic property is the section BackgroundGraphic that we defined earlier. Our object will use that graphic.
The second property is the Position. In our world, this object will be created at (0, 0, 0). In Orx, the coordinates are (x, y, z). It may seem strange that Orx, being a 2D game engine has a Z axis. Actually Orx is 2.5D. It respects the Z axis for objects, and can use this for layering above or below other objects in the game.
To make the object appear in our game, we will add a line of code in our source file to create it.
In the Init() function of ufo.cpp, remove the default line:
orxObject_CreateFromConfig("Object"); and replace it with:
orxObject_CreateFromConfig("BackgroundObject"); Compile and run.
The old spinning logo is now replaced with a nice tiled background object.

Next, the ufo object is required. This is what the player will control. This will be covered in Part 2.
• ### Forum Statistics

• Total Topics
631073
• Total Posts
2997754
×