Team PacMan - Second Week

There are a lot of stuffs going on this week, and I didn't remember to write the blog till now.

So last week I spent half of the time putting the octree into the code for collision optimizing, which is not necessary because our 3D scene is not big enough to cause performance issues but I figured it would be a good practice to do so. The principle is simple enough and there are many resources on the internet to research on. The hard part is how to merge that structure into our current code structure:

The structure before I merge the octree

As you see, in order to put in the octree, I have to get rid of all the collision check from the UpdatePhysics() function and merge them as part of the octree function. And since all the different classes has different collision objects(some are bounding boxes, some are using bounding sphere, some are formed by triangles), I have to create a new data structure (in my case, an entity class) to store all this collision entities and pass it to the octree. And since the octree is using bounding box to check which child each entity stays in, I have to write two new functions to check the collision between bounding box and triangles, bounding box and bounding boxes, as all the previous collision checks are through the player and the player is using a bounding sphere. But that was not even the hardest part yet, after finishing most of the code, I started to face a major problem: whether to put the player entity into the octree or not?

Well obviously I got two options. The first one is to add the player as one entity of the octree, and for collision check, we go through at least a branch of the octree every frame and get the all the leaves the player entity resides in (the player entity may reside in multiple leaves because it may intersect with several child space). After that, check collision with all the other leaves with the same parent. It sounds good, but the problem is, the player is moving, you also have to update the player entity in the octree for every frame and even re-struct it after the player is moving from one child space to another, during which, you have to go through at least one branch of the octree, again. The second one is to treat the player entity as an outside object and load it into the octree every frame. Then you calculate which leaves the player entity is in and check collision with entities in those leaves. This also means to go through at least one branch of the octree for once each frame and also a few bounding box collision check because you have to check the boundary of the space to decide which child are you in, so the number of checks are actually depending on how deep your tree is. Both way doesn't seem efficient enough for me, but I have to make the choice as I can't think of a better way to do it. So instead of doing a octree go through one more time, I decided to do a few more collision checks because collision checks between bounding boxes are not that expensive.

Normally, you would assume that's the end of it. And the world went dark after I ran the program only to find out the player is falling through the ground (I add a gravity -- constant falling speed -- to the player so he will fall if there is no collision with the terrain). And so there started the endless painful circle of debugging, which actually took most of the time since the coding only took like a few hours. First I got rid of the gravity and found out some collision worked. That's when thought the problem might be the partition process, I started to change the codes that handling big triangles (the triangle of the ground is big since it is flat) and began to keep track of the ground triangle in the octree, but nothing worked. I got so frustrated and desperate that I started to draw the flows of the octree to find out what part did I miss:

Part of The Octree Flow

It's actually during this process did I realize maybe my collision check code for partitioning wasn't working. I didn't think about the fact that the triangle may be so big that it might encircle the bounding box, which was actually bypassing my box-triangle check. And yea, that's the problem.

The rest of that week is mostly adding new game mechanics, there are two small challenges. One is to move a mesh of the model without moving the model, which is really easy when you figure out how to get the name of the mesh; another one is the physics reaction of the player when he collided with some special terrain like ramps and quicksand, as sometimes the behavior of the player was really weird when he collide with more than one triangle. I ended up with filtering some of the triangles that the player collided and using some really simple math equations to give the player a constant speed, since the player's speed could be really slow after multiple projection on the plane. Here is some screenshots of the new features (all triggered by triggers) I added in:

Door Closing

Sinking in quicksand 

Spike-wall is coming!

 At the end of last week, our artist sent us the model of the throne hall, I tried to add them in and found out most of the normals of the triangles in the scene are inverted (this took me a lot of time to debug as I first thought the problem was the collision detection). Which was making me nuts since most of my physics collision reactions were based on the direction of the normals, as I mentioned on the last blog and this kind of destroys my collision system. I talked with a few person and tried to find out a more generic way to ignore the direction of the normals, but nothing worked well. I ended up with manually flipped all the normals in 3dsMax by myself (It needs to bedone anyway since most of the textures are also inside-out) and got this to work. I also added a rear view camera, which is really simple, just add a new camera facing the opposite direction and draw everything twice.

Throne hall with rear view camera

Moving next to shaders and I really should sleep at this point...