The Wall
Introduction
Hello everyone, Derek Dittmer here.For this project, I again wanted to document my thought process, the problems I encountered, and how I overcame these problems, while creating it. My goals for this project: make a wall of bricks, be able to shoot them down with a projectile, have all the physics, collision detection and response made by me, and do it all in OpenGL.
I knew this wasn't going to be easy; while at school I learned a bit about OpenGL and it was tough. Most of my projects up to this point used some sort of engine (usually Unity), and I feel that this project is important if I want to know out how things really work under the hood.
Update 1
Alright, at this point I have objects being loaded in by a model loader, rendering for those objects, a camera controlled my keyboard/mouse input, and ambient/diffuse/specular lighting. Let's take a look at how I got these things up and running.
Before I actually started coding anything, I did some research on how collision detection might work, because I knew this would be the toughest thing for me. I found that there is no magic way to do it: every objects needs to check itself against every other object to see if they are colliding. Depending one how many objects you have, it doesn't take long for that number of calculations to get huge: for just 1000 objects you need half a million calculations for a collision check. Now, I don't see my simple brick wall getting over 100 objects, but these huge calculations bothered me. Luckily I stumbled upon some ways to get that number down. Using an Octree was one of them. I found some tutorials, but didn't look too much into it; I had a lot to do before I got there anyway. It was good to know that there was a way to do it though.
Source: http://en.wikipedia.org/wiki/Octree
I quickly found that collisions are easier to deal with when the colliders are axis aligned (no rotations). Since this is my first shot at collisions, I decided to have no rotations on my bricks, which will make detecting (and responding to) collisions much easier. It won't look realistic at all, but at least I have a chance at getting this thing working.
After that bit of research, I felt that I might be able to get this thing working, so I started working on getting the basic camera and input stuff in first, before I started worrying about collisions again.
The first thing that I did was look for some OpenGL tutorials. I quickly found NeHe and was going through some of their tutorials, but I felt they were out of date compared to what I had done while at school. So, I continued looking, and found OpenGL tutorials.org. That website showed me just about everything. I also found that the OpenGL that I did while at school was basically an exact copy of this website (now I know where my teacher learned OpenGL).
So, I had these tutorials to help me, and I also had my work from school. The way I saw it, the tutorials helped me get things working, and my school work helped my figure out ways to organize everything. I used these two sources a lot, though I never copy pasted anything from them. I wanted to make sure I knew exactly how things worked before I even typed them up – or at least have a good understanding of it.
After some simple tutorials to get some hardcoded rendering, I decided to work on getting input. We were learning about macros at school at the time, and we used macros to make each input button. Most of what I did for input was taken from what I did at school, though I did add some things; it didn't have events for the frame the key was pressed or released, and it didn't allow mouse buttons. Other than that, it is about the same: a singleton that objects can ask if a key was pressed (pretty similar to how it is in Unity). It keeps track of keyboard/mouse buttons, and mouse positions.
The next thing that I made was the camera. This is the one thing that I don't understand 100%. I understand model space and world space very well, and I also understand view space, but I don't think I get how things get to and from view space. It is embarrassing and I plan on doing a bit of researching on the subject after writing this. The camera is basically the same as what I did in school, though I did cut some functionality. We had different kinds of cameras, because one of our assignments required an orbiting camera, but I didn't need that here and left that stuff out. I didn't test out this new camera very much, and went straight into loading models, which caused some problems later on.
Alright, model loading. Again, I made this just about the same way I did it at school (which was about the same way it is done in the OpenGL Tutorials). Simply take the .obj file, and make the model with all the vertices, uv coordinates, and vertex normals. I also added the texture loader. This was super simple since GLFW can do it for you, though only for .tga files. While typing these loaders up, I made a lot of off by one errors (2 or 3 of them), and my cube ended up looking very strange: it looked like a single plane from the bottom front corners to the back top corners, and the texture was just all over the place.
I thought I had tested my .obj loader and it was working, but actually I didn't. I should have written some comments somewhere that I said what I tested, so I wouldn't have had this problem. So, because I didn't test my camera very much, I thought it might be the problem, since I thought the .obj loader was working. I went through the camera code for hours, but nothing fixed my cube. Then, I knew it had to be my .obj loader. I went through the code and found I had defined my uvs (which are vec2s, u and v) as vec3s, which caused all the weird texture problems. I also found that when I was separating the vertices (example 1.0 -1.0 0.5) I had the pointer off by one for where the number started. So, when I tried to convert " 1.0" into a float, it saw that space and just returned 0. After I fixed that and another place where I defined the uvs as vec3s, everything was working and I could again sleep peacefully.
Then I organized my renderable objects a bit better. Again, the way we did it at school worked fine, so I borrowed from that. I felt like the organizing took things out of the Main file and into their own separate files, which was a lot easier to manage. Nothing fancy with this, just putting things like texture data/vertices/normals/uvs into the object instead of somewhere in main.
I didn't want to do anything crazy with the lights/shaders, but since my .obj loader takes in normals, I figured I should use them. So, I used OpenGL Tutorials to get ambient/diffuse/specular lighting. It is pretty much the same as the websites'. It mostly makes sense, though I think I need to do a bit more researching on the whole shader process, especially how things get into and out of the shader.
Alright, I have a nice model and a texture loaded into my program and rendered on screen. I can use my mouse and keyboard to fly the camera around to check out these objects. And that's about it for now. It seems like a lot of work for not much to show. Now I want to take a closer look at collision detection and octrees, and if all goes well, we will see about collision response. It is equally exciting and terrifying.
Update 2
Alright, I'm at the point where I am about to start coding the collision. First I have done some researching though.
The first thing I need is collision detection. I decided to have axis aligned bounding boxes. Finding out if two boxes are colliding is easy, just check their extents:
(a.max_x() >= b.min_x() and a.min_x() <= b.max_x())
&& (a.max_y() >= b.min_y() and a.min_y() <= b.max_y())
&& (a.max_z() >= b.min_z() and a.min_z() <= b.max_z())
If true, then they are colliding. But like I said before, testing each box against the other is a lot of computations. So, I looked further into the octree, and actually found a tutorial where a guy uses an octree for collision detection! http://www.videotutorialsrock.com/opengl_tutorial/collision_detection/text.php it's my lucky day! I've watched the video, and looked over his code a lot; it is just a matter of coding it.
There are some things I would like to change when doing my own octree though. First, instead of taking actual ball objects, I would like for my octree to only know only about colliders. Since I am only going to use box colliders for now, a collider will just have xyz mins and maxes, and probably some other data that I can't foresee at this point. The octree will just put the colliders into sets, and send that off to someone else (probably a collision manager) to handle the actual checks and responses.
Also, I want to be able to visually see the octree, so I want to be able to draw out the cut up regions of the octree like a wireframe. This way, debugging will be a lot easier. Also, to make debugging easier, I would like to make the objects turn red if they are colliding, just to make it easy to see. I think a #define for debugging would work very nicely here.
I don't yet understand exactly how the octree works, but it is only a matter of time before I get it. When I finish it, I definitely want to check how fast it is though. While at school, we made some cool timers to see how fast (or slow) a piece of code is, so I will compare the octree with each collider checking against the other.
One thing is bothering me though, especially since everyone online is warning about it: if your objects move too fast, they could move through each other. This didn't bother me at first, but then I remembered that I am shooting projectiles, which move quickly. I don't quite know the solution, or even if it will be a problem, but it is something that I set in the back of my mind.
Alright, I am pretty confident in my collision detection. Collision response is the real tough part though. I have done some research and using elastic collision seems to be pretty simple and looks cool. Basically, your objects have mass, and if they collide, the bigger the mass and velocity the more impact it has on the other object. It seems to be used a lot for billiard balls. I have found a lot of ways to calculate this response, and though most have been in 2d space, I feel that I shouldn't have too hard of a time converting it to 3d space.
Source: http://physics.ucsc.edu/~josh/6A/book/momentum/node31.html
Also, I need a way for my objects to stop. I am figuring that every frame I will take a small percentage of their velocity off due to friction/air resistance. Also, if they collide with another object, I will take some of that energy (velocity) away. I think this will make it so when they are colliding with something a lot, like the floor, it will slow them down nicely. It is a good idea, but I feel that it will likely change. Once I see how these objects actually collide, I will have a better idea of what needs to happen. If it looks unrealistic then I will try something else.
I have also taken a small peek at rigidbody collision detection and response, and it is crazy. It looks so amazing, but I don't know that I am quite ready for it. I think if my simple collisions system actually works out, then I may take a look at rigidbodies, but that is for another time.
Alright, I feel a lot better about moving forward with my collision system. First I will try to detect collisions, and then we will see how well the response is. I can tell it is going to be tough, but if I survive, I will come out with a lot of important knowledge.
Update 3
Sorry it took so long to get back; I was in an epic battle with physics and collision response! It seemed that I lost every battle, but now, I feel that ultimate victory shall be mine. Basically, I tried a lot and failed a lot, but now it's finally starting to look good. Now objects are affected by gravity, don't (usually) go through each other, bounce off the floors and walls nicely, and move away when shot with a projectile. Oh boy, I've got a lot of explaining to do.
First off, I haven't done a single thing with the octree. I don't know why I wanted to do that so early; it would have caused too many problems I am sure. Once I know that my physics and collisions are working, then I can go back and make it nice and pretty. Right now, I am just having every object check against every other object. Keep optimizations in mind for sure, but early optimizations can cause problems I feel; maybe not all the time, but in this case, yes.
All right, so I have a couple of important classes: a collider class, physics object class, and the all mighty collision manager.
The collider class is simple; it has two vec3s for the min and max points (bottom/left/front point and top/right/back point), some info for debug drawing the collider, and some getters and setters. It also has a bool for if it is enabled, that way I can turn colliders off if I want. And that's about it.
Next is the physics object. It inherits my textured object class, so I don't have to worry much about drawing. The physic object class holds onto a collider, and gives the collider the info it needs to get its mins and maxes. This class is also a friend to the collision manager. I figured the collision manager is going to need all of the physics objects info, and though I don't know for sure, I think that calling getter functions a ton of times per frame would be a bit slower. The only data that is has is its velocity, its mass, and some bools that I am playing with.
One is mIsKinematic. Anyone that has used Unity before should know what that does. Basically, if true, its position and movement will not be affected by the collision response. So, it is like the floor or a wall. When doing my collisions checks, if both objects are kinematic, then I can exit early to save some time.
Another is mUseGravity. I'm sure you can guess what that does; if true, gravity will be applied to it. Walls and floors and the like have this set to false.
The last one is mIsSleeping, and is something that I am still playing with. Again, I have seen it used in Unity, and have seen it a lot online. It is very cool, and I hope I get it working right. I found an awesome site that is helping me with this: http://www.xbdev.net/physics/RigidBodyImpulseCubes/ It doesn't give you much code, but it tells you very simply what should happen. Basically, if an object is colliding with another sleeping object or an object with infinite mass (0 is infinite for me; walls and floor have 0 mass), then it goes to "sleep". It must have been moving below a certain threshold for a certain amount of frames to be able to sleep. The only thing that will wake this object up is a collision with a bit of force. The cool part is, if the object is sleeping, you don't have to apply any gravity or physics to it, and if two objects are sleeping you can just take them out of the collision check. I've also read that it helps when getting stacks of objects working, which is exactly what I am having problems with right now. If I can get it working, the objects will stack nicely, and I will also be saving quite a bit of processing power. Win win!
That's basically it for the physics object. I also have overloaded my translate and scale functions to apply the same to the collider as well.
I also made a bullet class. Basically, when you left click, it moves this to the cameras position, and uses the cameras forward vector to move. When it hits something it stops rendering and turns the collider off. Right now, only one projectile can be active, and I am alright with that.
Alright, I saved the best for last: the collision manager. Right now it handles the physics and collisions, but once I get that octree working, I will have a collision manager check for collisions, and then pass the colliding objects to the physics object to calculate the response. Or I may not, but that is what I think I will do.
So, the last week was pretty much spent failing at this collision manager. I looked at how physics is usually done online, and it looked like stuff that I could never understand, so I just tried hacking my way through it, which didn't work very well. I used the elastic collision equation, and it worked pretty well, but objects were sinking through each other because of gravity. I made a function that moved the objects back about a frame, and that kind of worked. I had the problem of objects hitting the floor/ceiling would have their x and z reversed, hitting the left/right wall would have their y and z reversed, and hitting the front/back wall would have their y and x reversed. So I hard-coded a fix for that and that kind of worked.
Everything was just kind of thrown together, and it actually didn't look terrible with one brick, or a couple bricks on top of each other. But, man, when I made a wall of bricks and hit one from the side, craaaaazy stuff started to happen. It reminded me of that scene in the first Harry Potter movie where the bricks moved out of the way to let them into that wizard town. These bricks were pushing out, pushing in, getting stuck in each other, flying up in the air opposite of gravity, and just looked terrible. Everything up to that point didn't look too bad, but I knew I would have to try something different.
Earlier I had tried getting the sleeping to work, and after a whole day of trying, ended up deleting it all. I tried getting the penetration depth so I could push the objects out of each other that way, but that wasn't working. I also tried using something I read about: SAT the separating axis theorem, to help get the penetration depth working but couldn't quite understand it.
At this point, I was wondering if this was something that I could do. It was tough, but I kept on trying.
I figured it had to be something with my "move objects back when colliding" and tried to replace that. Everything online said to get the penetration depth to move the objects out of each other. So I gave it another go. I really tried to get it working, debugging and stepping through everything to understand it. And finally it started working… sometimes. I found out that was because my way of detecting what side was hit was just not right. Then I gave the separating axis theorem another go, and that started to work. Still bouncing off walls and floors was weird, but now that the SAT was working, I could just check if it collided with an object with infinite mass and do this: a.mVelocity - = 2.0f * normal * (normal * a.mVelocity); and now it worked great!
This was super exciting for me. The collision detection was working, and the physics didn't look too bad, and I also got rid off all of the hard-coded nonsense. Objects didn't slide through walls or get stuck in each other (as much). It started looking good!
Stacking the bricks is a little jittery, and that is why I am currently looking into getting my objects to sleep.
And that is the update! Sorry it was so long, but I hope you found at least some of it interesting. Whew, finally I can get back to getting these objects sleeping and waking up properly!
Update 4
Alright, I think I am done with my physics/collision stuff. My objects are now sleeping/waking properly, and I took a shot at the octree.
I had a lot of trouble getting the sleeping/waking working, but it looks pretty good now. The first problem I has was the velocities always being too crazy. On that xbdev site, and other places on the internet, it said to use your velocities to see if you should be sleeping. Basically, if your velocities are really low for a certain amount of frames, go to sleep. I tried doing that, and it worked well in some cases, but when objects are stacked on each other, it didn't work very well; the velocities were all over the place, even though the objects weren't moving anywhere.
So I decided to use positions instead. Basically, if your object doesn't move in a couple of frames, then it should go to sleep. And that worked pretty well it seems. It now looked like this:
float motion = glm::dot(GetPosition(), GetPosition());
float bias = 0.96f;
mRWAMotion = bias*mRWAMotion + (1-bias)*motion;
if (abs(mRWAMotion - motion) < GlobalProperties::SLEEP_EPSILON) // You are slow enough to be sleeping
Now, at that point, you can increment a counter to see if you have been in that state for a couple of frames, otherwise the counter will reset.
But there was once important piece to sleeping: in order to fall asleep, you need to be colliding with an object that is already sleeping, or an object with infinite mass. Not terribly difficult, so I made a mIsSleepable variable that got set to true if you are slow for the certain amount of fames. It will check if the object is sleepable and collided with a 0 mass or sleeping object in collisions and then it will go to sleep.
Everything should have been working at that point, but it wasn't. I looked over the code for about a day, and could not figure it out. Basically, I had two bricks. If one brick was on the other, the bottom would fall asleep, allowing the one on the top to sleep as well. But if I put the bottom brick on top of the top brick, the bottom brick would fall asleep and the top one would never fall asleep. Hmmm…
Long (embarrassing) story short, I had mIsSleepable inside a check that should have been mIsSleeping. I felt stupid and wasted a lot of time. Right after that I changed mIsSleepable to mAbleToSleep, because they looked too similar and that was why it took me such a long time to notice that it was wrong. mIsSleepable would come up first in Visual Studio's auto complete, and I'm sure I just accidentally used that one without knowing. That's the last time I use variable names that look exactly the same!
Everything was working pretty well at this point, though I found out that if you have the right angle, you can shoot out the bottom bricks and the top ones will still be sleeping in the air. I didn't know if I would be able to fix that, but it bothered me, so I tried. I really had no ideas on how to fix that, or even what to look for in Google, but I stumbled upon a site that gave me the answer. It was a strange place to find an answer, but it worked.
http://chipmunk-physics.net/release/ChipmunkLatest-Docs/ This site is just some documentation on a 2D physics engine. I looked at some of their sleeping functions and their wake up function (void cpBodyActivate(cpBody *body)) said that it will wake up body and any other bodies it was touching. Genius! When an object goes to sleep, let the object that it is sleeping on have a pointer to that object, so when it wakes up, it will wake the object that was sleeping on it also. Seemed pretty simple, but I ran into some problems. The first problem was that I could still knock out the bottom bricks and the top bricks would stay floating, though it was much harder. I found out this was because if I hit a brick on the side, while there were other bricks on top of it (so basically more than one object sleeping on it) it just didn't work. I was thinking of having multiple pointers in case that happens, but I just decided that if an object sleeps on an object, before setting the objects pointer, check if it is pointing to something; if it is, wake that object up. This worked a bit, no more floating objects, but some objects would never fall asleep now. Turns out I needed one more check. It now looks like this:
if (aOther.mObjectSleepingOn == 0)
aOther.mObjectSleepingOn = &aObjToCheck;
else if (aOther.mObjectSleepingOn != &aObjToCheck)
aOther.mObjectSleepingOn->WakeUp();
That else if check was the key, turns out that the object would go to sleep, and aOther.mObjectSleepingOn was not 0, because it was already pointing to aObjToCheck, so it would wake it up. And that would go on infinitely; the object would go to sleep, and immediately get woken up, so that else if check is very important.
NOW everything seems to be working good. The only other problem is that sometimes bricks will be slightly inside each other. I'm sure I'm getting the right penetration distance; it is how I resolve that isn't working. So when two bricks collide, I use the penetration distance and they both push out of each other. If one object is sleeping and wasn't woken up, or one object has infinite mass, the other object should push out all the way. I think my problem is when an object is on the floor and another object is on top of that, it tries to push both objects apart, but the object on the floor shouldn't be moved, because it is on the floor. It isn't a huge problem; once the objects go to sleep it seems to fix itself – though I feel like hiding some physics problems under a sleeping function is a bit shameful. I have tried checking if the object collided with a sleeping/infinite mass object that frame, any other collisions should bounce off it, but that didn't seem to work. I don't know if I will fix it, but I think I will give it another shot.
The next thing I tried was getting the octree up and running. I spent some time getting it to work, and implementing it, but ran into problems. First problem was that everything started to noticeably lag, which was the opposite of what should have happened. Also, the collisions looked weird. I spent some time trying to debug it, and I think the collisions look weird because the same two objects are checking each other for collisions twice, though I haven't figured it out. I put in a #define and just left the octree out. It would be cool to get up and running, but at this point, there is no reason for it. I decided most of the code is there, and if I eventually have hundreds of objects then maybe I will give it another go, but at this point it is not needed.
Alright, that's about it. I might try tweaking the collision a bit, but other than that, I want to just add some extra polish stuff. Maybe see how hard it is to play sounds, or get some sort of UI; stuff like that. Thanks for reading – I think one more post and this project will be finished!
Update 5
Alright, I think it is finished! I tweaked the collision system a bit, changed the way models/textures function, and added some extra cool stuff. Let's take a look at how all this came about.
The first thing that I fixed with the collision systems was sleeping. For the most part, sleeping and waking worked perfectly. I thought I fixed it with that pointer to the object that it was sleeping on; so if that object wakes up, it will wake any object sleeping on it up as well. The only problem was when I hit the wall of bricks from the side, sometimes multiple objects would be sleeping on each other. I didn't really want to do it, but I just made a list of object pointers for all the objects sleeping on the object. Now every time an object falls asleep on an object, they add themselves to the list. When that object wakes up, it goes through the list, waking them up and removing them from the list. NOW it is working good.
The next thing that I changed was the way models and textures work. I used to have every object loading in their textures and models (verts/uvs/normals/indices), but that just seemed wrong. The data is the same, so why do I need to load it so many times? I figured that they could all use the same data, and I was right. I made a namespace that holds all the models' data and a namespace for the textures. Instead of passing in the path to the models/textures, you pass in a reference to one of these models' data and textures, and then they just use that. It works fine, and I'm sure it was better than what I was doing before. The only problem is how it is organized; I just feel like there could be a better way to load in all the models/textures. Every time I want to a put in new textures, I have to make a new TextureData class, and give it the texture path, and put it in an init and delete function. I'm sure there is a much better way to do it, though for now this works fine.
At this point, the project did exactly what I set out for it to do. But that doesn't mean it was finished; now it was time to have some fun! The first thing that I really wanted to do was have some 2D text that told you the controls. I really wanted to do this after I found a tutorial for it on OpenGL Tutorials. While I was working on my Doom2 UDK map (you can check it out in my projects), I tried very hard to get the old Doom font into the game, but couldn't. This time around (with the help of OpenGL Tutorials), I got it to work though. It uses a texture that has all the letters on it. So, I copied every letter into Photoshop and lined them all up perfectly to get it to work (that was fun). It doesn't look perfect; the edges look a bit strange, and all the letters take up the same amount of space, but it works. I was very happy about this working without too much trouble. At first, I thought the tutorial was broken, since the texture that they were using was just all white. After I learned a bit more about how it works, I checked out the alpha layer, and that was where/how it worked.
So now I have Doom textures, and fonts. What else could I possibly need? Sounds of course! I have used Fmod before to get sounds working, and that worked perfectly, but since I was doing everything myself until this point, I didn't want to use it here. I looked around for a way to play sounds without another library, and found the windows.h has some very simple sound functions. After digging a bit, I found that it only allows one sound to play at a time, but that was fine – I only had two sounds anyway. It would have been cool to have the Doom pistol shot sound in there, but I feel the background music is much more important. Well, about the first 20 seconds of the background music. Windows.h only plays .wav files, and by cutting that music down, I am saving about 18 meg, which is pretty huge for my small program.
Alright, now the last and coolest thing that I added: rewind! The idea actually came to me when I was working on my Please Be Kind rewind project (check it out in my projects) – how cool would it be to be able to break stuff, and then watch it rebuild itself the opposite of how you broke it? That's what I was going for, and I think it looks great. I did things a bit differently than in my Please Be Kind project; since there are going to be more rewindable objects here, I figured I would go for a set amount of rewind time, so that way it doesn't just keep eating away at the memory. I didn't know how big the objects were going to be until I got everything working, but I ended up with 2 minutes of rewind time. To make my life a whole lot easier, I just had every object save every 6 frames, that way getting the rewind speed working was very easy.
One thing I did differently was to have a rewind manager class, which had all the rewindables. Since everything had the same timestamps of when they were saved, this manager would go through all the objects to tell them what to do and when to do it. It was very simple.
Since I only had their positions every 6 frames, I needed to interpolate between them on the in-between frames. This caused a lot of issues when I was doing my Please Be Kind project, and I figured it would do the same thing here. I looked online to see example lerp code, and found that lerping made a lot more sense when I saw the code. I was able to get the lerping working without too much hassle.
When everything was finished, I started playing around with my program, seeing where it doesn't work so well. I found that when I have a lot of stacked objects (doubled digits) they sink into each other a lot more, and jitter. It really is just a problem of how my collision works. I've read that how I resolved penetration works well, but not too well for stacked objects. Some say that when you resolve the penetration, you can (and will) cause more collisions, so you must check for collisions more than once. I checked other ways people fought this, but most of them just checked for collisions 2-3 times. Since I didn't get the Octree working, I just stuck to having 1 collision check and not stacking too many objects.
I also found that when my frame rate drops, the collisions don't work very well. I had a game running in the background while running my program and it didn't perform nearly as well. I didn't really know what to do about this problem. I read this cool article that gave me some ideas on how I could combat the frame rate issue http://www.koonsolo.com/news/dewitters-gameloop/, but I didn't put much effort into fixing it. As long as you aren't playing another game in the background, it should be fine!
At this point, I told myself it was done; if I hadn't I could have worked on this project for much longer. I am very happy with what I accomplished; it does what I expected a bit more. Hope you learned something or found it interesting. Thanks for reading!