engine_zero_08

While I implemented frustum culling a little while ago, I never actually coded a proper bounding volume. For the  bounding test I was using a sphere, but I just set the radius to some hard-coded value. This was fine when I just had a bunch of similar sized cubes on screen, however it broke apart once I started getting varied models imported. This week I decided to do something about it.

After a quick Google search for bounding spheres, I ended up on Wikipedia. There was some good information there regarding minimal bounding spheres (also known as smallest enclosing ball or minimal enclosing ball), and I was given a few options for different algorithms. After reading the whole page I become very interested in the “bouncing bubble” algorithm, especially due to the spiffy gif animation showing it in action. The brief explanation seemed easy to follow compared to the other methods, and the error percentage was only around 1-2% which is much lower than Ritter’s algorithm (which can be as high as 20%). So far so good.

Unfortunately I found next to nothing on the internet describing the method. What I did find is a post from last year on StackOverflow by someone in the same situation as me. This lead me to the original paper describing the method, which was for sale for $18 on Grin.com. Honestly I don’t mind paying the money for quality information if it’s going to help improve my engine. The article was fairly easy to follow, and provided just enough information to base the implementation on. At first I was disappointed that no source-code was given, but I managed to pull it together using the pseudo-code. All in all I think I spent about 4 hours on it (including research) so I’m happy to have got it working so quickly.

Below is my bouncing bubble implementation. Keep in mind I have not profiled this code, it’s possible it’s not fully optimized. However, I’m only doing the calculation when a 3D model is loaded, so it shouldn’t effect performance at all really.

BoundSphere RenderCore::calculateBoundSphere(vector vertices){
	Vector3D center = vertices[0].position;
	float radius = 0.0001f;
	Vector3D pos, diff;
	float len, alpha, alphaSq;
	vector::iterator it;

	for (int i = 0; i < 3; i++){
		for (it = vertices.begin(); it != vertices.end(); it++){
			pos = it->position;
			diff = pos - center;
			len = diff.length();
			if (len > radius){
				if (i < 2){
					alpha = len / radius;
					alphaSq = alpha * alpha;
					radius = 0.5f * (alpha + 1 / alpha) * radius;
					center = 0.5f * ((1 + 1 / alphaSq) * center + (1 - 1 / alphaSq) * pos);
				} else {
					radius = (radius + len) / 2.0f;
					center = center + ((len - radius) / len * diff);
				}
			}
		}
	}
	
	return BoundSphere(center, radius);
}

Also, I should remind myself to do benchmarks more often. After I added all the normal mapping and shadow stuff performance has taken a big it. Before I was getting likely over 2400fps, now I’m only getting around 1600fps. Still acceptable, but maybe could be better with such a simple scene. The culling definitely helps, but I may have to look into other optimizations like batching and instancing if I want to get the speeds I need for my project. I’ll probably get started with the physics engine aspect soon and then optimize later if I can’t meet my 120fps target. Cheers.

 

After struggling for a bit with the shadow mapping implementation, I finally have something presentable. I followed a tutorial from Microsoft and thought I understood what was happening. However, it required a lot of changes in the rendering code and it took a little while to get things working. Even once it was somewhat functional, I still had some issues with what they call shadow acne. It seemed really bad on the self-shadowing side of objects. I tried tweaking all the values I could (i.e. the bias in the shader), but I was not able to get it to look right. Finally I just set it so that there wouldn’t be self-shadowing of a single polygon. This happens to look fine, since the lighting equations make the polygon shaded anyhow. I’m not sure if this will work for every single instance, but with the simple models I’m testing with it’s fine.

I’m at the point where I really want to get the physics engine up and running. Still have some more research to do, so I bet it will take some time before I have something more to show. But it’s coming along.

 

PhysicsGameDevs

I can say I had a pretty good time with Physics for Game Developers: Science, math, and code for realistic effects by David M Bourg & Bryan Bywalec. It is a very approachable text, and makes a somewhat complex topic more manageable with concrete examples. It’s definitely a book about 3D physics, but many of the samples are done in 2D for clarity. I did not find this to be an issue, and most of the equations and code were digestible. I did see some heat on the reviews, saying that there were errors in some of the code. I could not verify this, but just from reading the book the authors seemed knowledgeable.

At the beginning, each chapter covers a fundamental aspects of physics. Later they go into examples that could be used in a game. Some of the topics covered include: Newton’s laws of motion, kinematics, force, kinetics, collisions, projectiles, particles, rigid-bodies, springs, aircraft, boats, cars, guns, sports. In the last section it goes over some emerging technology and how they work, like touch screens, motion-sensors, 3D displays, and the physics of sound. I very much enjoyed the whole book, and liked that there were practical examples to go along with every topic.

Many technical books can get lost in the math equations, but I found this text to have a good amount of explanation and not too many long proofs. This could be a pro or a con. On one hand it makes reading it a little more straight-forward, but on the other-hand, it may leave out some important details when it comes time to create your own implementation. I’m not sure I would want to base a physics engine solely on this book. It’s not that it was bad, but it was more of a general concept thing than giving you all the code. That said, there is a good amount of code in the book, it just may not be as complete as some other sources.

Overall I was satisfied with Physics for Game Developers. It may not be my favorite physics book (I found Game Physics Engine Development to be a lot better for my purposes), it still seemed worth reading. Now I am beginning to realize the creating a physics engine will not be easy, but the more I read the more I feel capable of this task. I think the book has helped.