C++

Forum

 
SAT Collision Issue

Jacob16682 (9)
Ok, I am kinda new here so hi guys!. I am having a bit of an issue with a collision detection system I am trying to get working that uses the Separating Axis Theorem to work. (info here: http://gamedevelopment.tutsplus.com/tutorials/collision-detection-using-the-separating-axis-theorem--gamedev-169 )

So when the one corner of the one square is rotated to touch the other square it doesn't work! (picture for reference: http://imgur.com/Bl4tyf9 )

Here is the code for the different functions I use. I can't find much wrong (I hope you can help) http://pastebin.com/JT21y1fL

Thank you so much. If you want I can upload the full code for the application as well as the library code I used to make it. Or I can upload the application itself if need be. I really need this to work, but I can't find the problem. Thanks again!
helios (17575)
http://www.cplusplus.com/articles/jLzyhbRD/

When asking about code Don't ask others to debug your broken code without giving a hint what sort of problem they should be searching for. Posting a few hundred lines of code, saying "it doesn't work", will get you ignored. Posting a dozen lines of code, saying "after line 7 I was expecting to see <x>, but <y> occurred instead" is much more likely to get you a response.
Hippogriff (727)
As well as that you seem to be making it more complicated than it needs to be.

-Create a vector from each edge. (x2-x1, y2-y1).
(-y,x) is the normal of that vector. Normalize all vectors.
-Use dot product on every point to each axis vector, store min/max.
-Compare them all.

No division needed, you shouldn't need the slopeUndefined checks.
Here is dot product + where I first learnt it from.

http://freespace.virgin.net/hugo.elias/routines/r_dot.htm
http://rocketmandevelopment.com/blog/separation-of-axis-theorem-for-collision-detection/

Too much code to see if code itself is the problem, just advice here.
Jacob16682 (9)
Ok I tried what James2250 said and cleaned up the code quite a bit:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
 
float projectedPoint(glm::vec2 point, glm::vec2 slope)
{
	return (point.x * slope.x) + (point.y * slope.y);
}


float rotatedvalueY(float x, float y, float centerX, float centerY, float angle)
{
	angle = angle * (M_PI / 180.0f);
	return centerY - (x - centerX)* sin(angle) + (centerY - y) * cos(angle);
}

float rotatedvalueX(float x, float y, float centerX, float centerY, float angle)
{
	angle = angle * (M_PI / 180.0f);
	return centerX + (x - centerX)* cos(angle) + (centerY - y) * sin(angle);
}

glm::vec2 slope(glm::vec2 P1, glm::vec2 P2)
{
	return glm::vec2((P2.x - P1.x) , (P2.y - P1.y));
}

bool SATcollision(glm::vec2 A_Topleft, glm::vec2 A_Topright, glm::vec2 A_Bottomright, glm::vec2 A_Bottomleft, glm::vec2 B_Topleft, glm::vec2 B_Topright, glm::vec2 B_Bottomright, glm::vec2 B_Bottomleft)
{
	glm::vec2 box1_point[]{A_Topleft, A_Topright, A_Bottomright, A_Bottomleft};
	glm::vec2 box2_point[]{B_Topleft, B_Topright, B_Bottomright, B_Bottomleft};

	float box1_min = 0;
	float box1_max = 0;
	float box2_min = 0;
	float box2_max = 0;


	bool box1_min_undefined = true;
	bool box2_min_undefined = true;
	glm::vec2 normal;
	glm::vec2 lineSlope;

	for (int i = 0; i < 8; i++)
	{
		box1_min = 0;
		box1_max = 0;
		box2_min = 0;
		box2_max = 0;

		box1_min_undefined = true;
		box2_min_undefined = true;
		

		if (i < 4)
		{
			int q = i + 1;
			if (q >= 4)
				q = 0;

			lineSlope = slope(box1_point[i], box1_point[q]);

			normal = glm::vec2(-lineSlope.y, lineSlope.x);
		}
		else
		{
			int q = i - 4 + 1;
			if (q >= 4)
				q = 0;
			lineSlope = slope(box2_point[i - 4], box2_point[q]);

			normal = glm::vec2(-lineSlope.y, lineSlope.x);
		}


		for (int p = 0; p < 8; p++)
		{
			if (p < 4)
			{
				if (projectedPoint(box1_point[p], normal) > box1_max)
					box1_max = projectedPoint(box1_point[p], normal);

				else if (projectedPoint(box1_point[p], normal) < box1_min || box1_min_undefined == true)
				{
					box1_min = projectedPoint(box1_point[p], normal);
					box1_min_undefined = false;
				}
			}

			else
			{
				if (projectedPoint(box2_point[p - 4], normal) > box2_max)
					box2_max = projectedPoint(box2_point[p - 4], normal);

				else if (projectedPoint(box2_point[p - 4], normal) < box2_min || box2_min_undefined == true)
				{
					box2_min = projectedPoint(box2_point[p - 4], normal);
					box2_min_undefined = false;
				}
			}
		}

		

		if (box2_min > box1_max || box1_min > box2_max) // || vectorComparison(box2_min, box1_max) == "equal" || vectorComparison(box1_min, box2_max) == "equal")
			return false;

	}
	return true;
}



Now, this still doesn't work and I believe that it is from a different problem. I think it's from how I find the rotated value of the points in the rotatedvalueY and rotatedvalueX functions. Since I am using OpenGL with this it is confusing by the fact that the y-axis is flipped (going up means decreasing a point's y-value and going down means increasing it). Now I thought I took into account this fact in those functions, but I could be wrong. The functions are at lines: 7 and 13. I'll try messing around with them to see if that's it because the only time this collision function doesn't work is when the box is rotated. Oh! Here is also how I define the Topleft, Topright, etc. points:
1
2
3
4
5
6
7
 
float centerX = x + (width / 2);
	float centerY = y - (height / 2);

	topLeft = glm::vec2(rotatedvalueX(x, y - height, centerX, centerY, angle), rotatedvalueY(x, y - height, centerX, centerY, angle));
	bottomLeft = glm::vec2(rotatedvalueX(x, y, centerX, centerY, angle), rotatedvalueY(x, y, centerX, centerY, angle));
	bottomRight = glm::vec2(rotatedvalueX(x + width, y, centerX, centerY, angle), rotatedvalueY(x + width, y, centerX, centerY, angle));
	topRight = glm::vec2(rotatedvalueX(x + width, y - height, centerX, centerY, angle), rotatedvalueY(x + width, y - height, centerX, centerY, angle));


I am very appreciative of all the help so far and understand better how SAT works. Thank you all so much!
Jacob16682 (9)
UPDATE:
I fixed the rotatedY function so that it actually outputs the correct value (I knew something was wrong there). The updated function is:

1
2
3
4
5
 
float rotatedvalueY(float x, float y, float centerX, float centerY, float angle)
{
	angle = angle * (M_PI / 180.0f);
	return centerY + (x - centerX)* sin(angle) + (y - centerY) * cos(angle);
}


This presents a whole new slew of problems though!

https://www.dropbox.com/s/0184sva184z5697/Screenshot%202015-06-29%2012.44.16.png?dl=0

I managed to output some information that might help:

-45.7 (angle of box)
box 0 top left (275.749, 353.553)
box 0 top right (320.447, 307.749)
box 0 bottom right (366.251, 352.447)
box 0 bottom left (321.553, 398.251)
box 1 top left (288, 384)
box 1 top right (352, 384)
box 1 bottom right (352, 448)
box 1 bottom left (288, 448)


I also outputted how many times the collision looped through until it returned false. It was 2 times, so it was checking the slope of the first box's top right coordinate and bottom right coordinate. Using this info I hope to be able to follow through the program with those variables to find where I went wrong. I welcome you guys to do the same in order to help me solve this head scratcher! Thanks for putting up with my annoying problem thus far!
Hippogriff (727)
To make it easier to might want to directly type in 8 points and see if it works (rules out any rotated value problems).

Does it work when neither box is rotated?

If you want to upload the entire source somewhere, assuming it isn't huge I can try and take a look.
Jacob16682 (9)
So I typed in 8 points and it worked. Yes it works with no rotation. I also checked the math on paper with those 8 coordinates I outputted and it worked on paper. Maybe I am getting the min and max values wrong. (lines 72-97)
Jacob16682 (9)
As requested here is the full source code:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
 
//WORLD.H
#pragma once

#ifndef WORLD_H
#define WORLD_H

#include <iostream>
#include <windows.h>
#include "GLee.h"
#include <gl/gl.h>
#include <gl/glu.h>
#include <string>
#include <fstream>
#include <SDL.h>
#include "SDL_opengl.h"
#include "SDL_image.h"
#include "SDL_mixer.h"
#include <stdio.h>
#include <math.h>
#include <sstream>

#include "shaders.h"
#include "framebuffer.h"
#include "MoveAndRender.h"
#include "pipeline.h"
#include "sound.h"
#include "camera.h"
#include "Particles.h"

#include <vector>

using namespace std;

SDL_Event event;
RenderPipeline pipeline;
shader* mainshader;
Framebuffer screenfbo;
Camera camera;

MoveRender entity[2];

unsigned int texture;

bool running = true;

int r = 1;

#endif



//MAIN.CPP
#include "world.h"




int main(int argc, char* args[])
{
	pipeline.setup("SATCollision", 640, 480, false, MODEL_MATRIX);

	cout << glGetString(GL_VERSION) << endl;

	mainshader = new shader("vertex.txt", "fragment.txt");
	screenfbo.setup(640, 640);

	texture = entity[0].loadtexture("texture.png");
	
	for (int i = 0; i < 2; i++)
	{
		entity[i].readdata("entity.txt");
		entity[i].init();
		entity[i].setlocation((640/2)-32, (640/2)+128);
	}

	bool pause = false;
	

	while(running)
	{
		pipeline.setdelta();
		while (SDL_PollEvent(&event))
		{
			switch (event.type)
			{
				case SDL_QUIT:
					running = false;

				case SDL_MOUSEMOTION:
				{
					if (!pause)
					{
						entity[0].x = event.motion.x - (entity[0].width / 2);
						entity[0].y = event.motion.y + 168 + (entity[0].height / 2);
					}
					break;
				}

				case SDL_MOUSEWHEEL:
				{
					if (!pause)
					{
						if (event.wheel.y > 0)
							entity[0].angle += 100 * pipeline.delta;
						else
							entity[0].angle -= 100 * pipeline.delta;
					}
					break;
				}

				case SDL_KEYDOWN:
				{
					if (event.key.keysym.sym == SDLK_SPACE)
					{
						pause = !pause;
						cout << SATcollision(glm::vec2(274.759, 362.106), glm::vec2(318.894, 315.759), glm::vec2(365.241, 359.894), glm::vec2(321.106, 406.241), glm::vec2(288, 384), glm::vec2(352, 384), glm::vec2(252, 448), glm::vec2(322, 488)) << endl; // the function will return true here
						for (int i = 0; i < 2; i++)
						{
							cout << "box " << i << " top left (" << entity[i].topLeft.x << ", " << entity[i].topLeft.y << ")" << endl;
							cout << "box " << i << " top right (" << entity[i].topRight.x << ", " << entity[i].topRight.y << ")" << endl;
							cout << "box " << i << " bottom right (" << entity[i].bottomRight.x << ", " << entity[i].bottomRight.y << ")" << endl;
							cout << "box " << i << " bottom left (" << entity[i].bottomLeft.x << ", " << entity[i].bottomLeft.y << ")" << endl;
						}
					}
				}
			}
		}

		if (!pause)
		{
			cout << SATcollision(entity[0].topLeft, entity[0].topRight, entity[0].bottomRight, entity[0].bottomLeft, entity[1].topLeft, entity[1].topRight, entity[1].bottomRight, entity[1].bottomLeft) << endl;
			if (SATcollision(entity[0].topLeft, entity[0].topRight, entity[0].bottomRight, entity[0].bottomLeft, entity[1].topLeft, entity[1].topRight, entity[1].bottomRight, entity[1].bottomLeft))
				r = 0;
			else
				r = 1;
		}
		//rendering
		glClearColor(GLclampf(0), GLclampf(0), GLclampf(0), GLclampf(1));
		mainshader->useShader();

		glBindFramebuffer(GL_FRAMEBUFFER, screenfbo.FBO);
		glClear(GL_COLOR_BUFFER_BIT);

		for (int i = 0; i < 2; i++)
		{
			pipeline.pushMatrix();
			pipeline.ortho(0, 640, 640, 0, -1, 1);

			pipeline.translate(camera.calcx(), camera.calcy(), 0);

			pipeline.translate(entity[i].x + (entity[i].width / 2), entity[i].y - (entity[i].height / 2), 0);
			pipeline.rotate(entity[i].angle, 0, 0, 1);
			pipeline.rotate(entity[i].yangle, 0, 1, 0);
			pipeline.translate(-(entity[i].x + (entity[i].width / 2)), -(entity[i].y - (entity[i].height / 2)), 0);

			pipeline.updateMatrices(mainshader->getProgramID());

			entity[i].render(mainshader->getProgramID(), texture, r); // render function where I render quad and find rotated values of points

			pipeline.popMatrix();
		}
		glBindFramebuffer(GL_FRAMEBUFFER, 0);

		
		//render screen fbo
		pipeline.pushMatrix();
		pipeline.ortho(0, 640, 640, 0, -1, 1);
		pipeline.translate(((float)640 / 2), ((float)640 / 2), 0);
		pipeline.rotate(camera.scamr, 0, 0, 1);
		pipeline.translate(-(((float)640 / 2)), -(((float)640 / 2)), 0);
		pipeline.updateMatrices(mainshader->getProgramID());

		screenfbo.render(mainshader->getProgramID());

		pipeline.popMatrix();

		mainshader->delShader();


		pipeline.swapBuffers();
	}

	return 0;
	pipeline.deletepipeline();
	screenfbo.~Framebuffer();
	SDL_Quit();
}


Some of these functions are from a library I created. The big one you need to know is the render function, where I render the quad and also find out the rotated points. (As shown earlier in the thread.)

I found that when I manually type in the values that I outputted into the collision function it will return true. I don't understand why though.
Last edited on
Jacob16682 (9)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
 
bool SATcollision(glm::vec2 A_Topleft, glm::vec2 A_Topright, glm::vec2 A_Bottomright, glm::vec2 A_Bottomleft, glm::vec2 B_Topleft, glm::vec2 B_Topright, glm::vec2 B_Bottomright, glm::vec2 B_Bottomleft)
{
	glm::vec2 box1_point[]{A_Topleft, A_Topright, A_Bottomright, A_Bottomleft};
	glm::vec2 box2_point[]{B_Topleft, B_Topright, B_Bottomright, B_Bottomleft};

	float box1_min = 0;
	float box1_max = 0;
	float box2_min = 0;
	float box2_max = 0;


	glm::vec2 normal;
	glm::vec2 lineSlope;

	for (int i = 0; i < 8; i++)
	{
		box1_min = 0;
		box1_max = 0;
		box2_min = 0;
		box2_max = 0;



		if (i < 4)
		{
			int q = i + 1;
			if (q >= 4)
				q = 0;

			lineSlope = slope(box1_point[i], box1_point[q]);

			normal = glm::vec2(-lineSlope.y, lineSlope.x);
		}
		else
		{
			int q = i - 4 + 1;
			if (q >= 4)
				q = 0;
			lineSlope = slope(box2_point[i - 4], box2_point[q]);

			normal = glm::vec2(-lineSlope.y, lineSlope.x);
		}


		box1_max = projectedPoint(box1_point[0], normal);
		box1_min = projectedPoint(box1_point[0], normal);

		box2_max = projectedPoint(box2_point[0], normal);
		box2_min = projectedPoint(box2_point[0], normal);

		for (int p = 0; p < 8; p++)
		{
			if (p < 4)
			{
				if (projectedPoint(box1_point[p], normal) > box1_max)
					box1_max = projectedPoint(box1_point[p], normal);
				
				else if (projectedPoint(box1_point[p], normal) < box1_min)
					box1_min = projectedPoint(box1_point[p], normal);
			}

			else
			{
				if (projectedPoint(box2_point[p - 4], normal) > box2_max)
					box2_max = projectedPoint(box2_point[p - 4], normal);
				
				else if (projectedPoint(box2_point[p - 4], normal) < box2_min)
					box2_min = projectedPoint(box2_point[p - 4], normal);
			}

			
		}

		if (box2_min > box1_max || box1_min > box2_max)
		{
		
			return false;
		}

	}
	return true;
}


Hallelujah! It works now! It was a min and max error. The min_undefined bools were messing it up. This code works though, thank you all so much!
Hippogriff (727)
Good job figuring it out.
Time to start on an awesome game now the collision is all set up?~
Jacob16682 (9)
Time to apply it to my awesome game now that I got it working.
Topic archived. No new replies allowed.