Developer Diary, April week 3

I must have missed a week somewhere because it’s nearly May already.

I had some problems with false positives/false negatives with my collision detecting algorithm. It works fine when the shapes involved are roughly the same size, but when the shapes have significantly different sizes, the midpoint-trick doesn’t work.

The problem specifically breaks down if the midpoint of the shapes falls inside the bounds of one of the shapes, which is often the case for a very large shape coming closer to a comparatively smaller shape. As I am using very large triangles for my scenes, and comparatively small ones for my bounding boxes, this is a major issue.

I’ll be looking at solutions to this problem this week, as well as alternate implementations to consider. Now the math revision is basically complete I hope to knock this problem off on Tuesday.

I notice I still haven’t done any more Unity tutorials. I became addicted to the sweet feeling of pushing my own engine further and further to a deploy state. I still want to do these tutorials so I’ll need to properly factor them in to my project plan and not just say “Do them on Thursday” because I discovered that I would shunt all my necessary outside-world tasks (shopping/housework/laundry/etc) on to those days so that I could spend more days programming.

Tuesday Midday: I couldn’t find a reasonable algorithm so I’m just going to brute force it. I’ll make it cute later if I need to.

So I’m going to take the triangle in question and see if it intersects the bounding box.
To do this, I’m first going to assess if the plane that the triangle is on intersects the box – I can simply see if all the points of the box are on one side, or the other. If they are, no intersection, early exit.

If there’s a split, then there could be an intersection.

I then need to take any two points of the triangle and make a plane out of it, that is parallel to the surface normal of the triangle, and then repeat the ‘all-or-none’ test with the points above/below this new plane.

If all the points are on the ‘outside’ of the plane/triangle, there’s no intersection – exit.

As soon as I find some points on either side of the plane/triangle, there’s an intersection – resolve and exit.

If all the points are on the ‘inside’ of the plane/triangle, then I need to take another two points and make another plane, and repeat the same set of checks.

If I still haven’t got an exit, then I need to check the third plane, only this time if all the points are on ‘inside’ then we have got an intersection.

Tuesday afternoon:
I’ve got the code for the ‘if the hitbox intersects the plane’ working.
Now, I need to generate a plane from two points of a triangle.
I can generate a third point by multiplying one of these two points by the existing surface normal.
I can then work out a surface normal for this plane using the cross product of the edge I had just made, and the original edge.
This will then give me the surface normal.
I can then perform the ‘if the hitbox intersects the plane’ test on this new plane.

I must do this for all three edges of the triangle. This will allow me to pick up all triangle/box interactions I can think of.

Tuesday night:
The code is basically done (to my understanding) but I’m still getting many false positives/false negatives.
I wrote a lot of unfamiliar code so I’ll need to desk check it to make sure it’s doing what it’s supposed to.

My eyes have kind of glazed over from coding all day so I think I’ll leave it here and have a fresh look in the morning.

Wednesday morning:
Where I left it last night;
There’s four checks in total that I need to make to work out if a triangle is intersecting the box, or not.
1 – The first check is the “Is the triangle’s plane intersecting the box”.
If yes, then the second check is:
2 – Are all the points ‘on one side’ of the triangle?
If yes, and that side happens to be the ‘outside’, then there’s no intersection.
Otherwise, if SOME points are on either side of the triangle, there’s an intersection.
If ALL the points are on the ‘inside’ of the triangle, then I need to repeat test 2 for each of the other sides of the triangle, until either I resolve there’s an intersection somewhere, or I get ‘inside’ for all three tests – which means the box is entirely enclosed by the triangle; and there’s an intersection.

The second test is fundamentally more complex, and that’s what I’m working on now.

However, today my wife is at home so I’m not sure how much work I’ll get done.

Test 2 appears to be working. I found that I had not been converting the vertexes in the test triangles to the same coordinate space as the hitbox. I’ve temporarily fixed this by converting in the physics section, I’ll later consider if it’s worth converting the scene coordinates to world coordinates at compile time, for scenes that don’t move (e.g rooms) this is acceptable. For scenes that do move (e.g an elevator, or space ships flying around) this won’t work.

Wednesday evening:
It appears that the algorithm doesn’t work for triangles that aren’t aligned with an x, y, or z axis.
I will have to redo it using the boxes sides instead of the triangles sides.

Here’s the current test scene. The blue block is my actor. It’s currently flagging a collision, but if I angle it around the middle left/right or forwards/backwards, collisions fail, even though it’s clearly embedded in the wall.

Thursday morning:
I think the correct way to do this is to use the ‘separating axis test’. I’d seen this a couple of times but I mistakenly thought it was flawed like the ‘midpoint-plane’ test, I had started with.
This test is described in detail here and there is even some code I can review. This website is the support website for the book I’m using, “3D Math Primer for Graphics and Game Development”, Fletcher Dunn & Ian Parberry. This is also the book that taught me the finer details of 3D camera math, so they have proved themselves so far.

The main problem is that I do not intuitively understand what’s going on here. I understand the concept of ‘If you can draw a line that separate the points, you win’ but I’m not sure how to pick this line. I’ll have to look in to it.

Before then, I need to reduce the actors hit box into a 2D shape that lies along the same plane as the triangle. This will require performing a ‘point that ray intersects plane’ test, and compiling the results into whatever shape that results (could be a triangle, quadrilateral, pentagon or heptagon).

So that’s what I’ll do.

Developer Diary, April week 2

This week I want to at least get the code up to the point where I’m testing for collision detection, but ideally, actually have the collision detection working to the point that I can identify when an actor is inside a scene/outside a scene, and have it interact with gravity.

This week I’ll also be contacting various gaming companies in Adelaide. I’m hoping I can get some insight in to what kinds of things they are looking for in potential future employees. I’ve been checking out different websites and the main thing that I’ve seen in common is ‘actually working on a game’; I feel like my engine isn’t far enough progressed yet to call it ‘working on a game’ although we’re not far off. If I can roll out a prototype by the end of April I’ll consider it mission accomplished.

Monday: I was working at my regular job today so I didn’t get a chance to do any coding.

Tuesday midday: I’ve implemented a simple cube hitbox for all of my scene objects. I’m now working on very basic collision checking (identify if the actor hitbox is at least some way interacting with the room it is in). I’ve made two rooms so that I can test which room the actor is currently in.

Tuesday evening: Today was cut short when my wife came home early, so we had a relaxing afternoon walking around town a bit. I managed to get the basic box collision detection working including having an actor (a purple box) move around on screen. I’ll put a video up shortly to demonstrate this.

The next objective will be to further refine this collision detection so that the box is only triggering a collision when it crosses an object in the scene, rather than when it enters the scene itself.

Wednesday midday: Collisions are now being triggered while the object is in the scene. I’m now testing for collisions against specific triangles inside the scene.

Thursday night: I reached the limits of ‘hackjob collision detection’ code Wednesday afternoon. From then I was reading up on the problem and looking at the math. I’ll even put some diagrams in here when I get the chance.

Essentially, I want to work out if any given triangle in a scene/prop is overlapping an actor’s hit box. There are a number of tricks to make this particular search more efficient. It’s fairly easy to determine if an actor is in a specific area, and that allows me to narrow down the number of triangles to search through.

To work out if a given triangle is intersecting an actors hitbox, we have some assumptions:
1 – The hitbox is an axis-aligned-bounding-box, meaning that all the corners are 90 degrees, although it is not necessarily a square.
2 – We have the vertex addresses of the triangle we wish to check.
3 – We have the vertex addresses of the hitbox we wish to check.
4 – The hitbox and triangle are in the same coordinate space.

We can then draw a line from the midpoint of the triangle to the midpoint of the hitbox.
At the midpoint of this line, we create a plane that is perpendicular to the midpoint.
We then test the triangle vertexes and see which side of the plane they are on.
If all the vertexes are on one side, then there is no collision.
If some of the vertexes are on either side, then there is a collision.

I can use the dot product of the vector from the midpoint-to-the-hitbox against the vector from the midpoint-to-the-triangle-vertex being tested to work out what side of the plane the vertex is on.

I also have some work to do with rotation/translation of the points to put both of them in the same coordinate space. At the moment, I’m using translation only. I will likely need to use quaternions to correctly rotate vertexes in 3D space. I might therefore rotate the hitbox into the triangle coordinate space because this only needs to be done once per scene.

Guess I’ll be back here Friday morning to implement this o/

Friday night:
Nope. I brushed up my resume, wrote a cover letter, and applied for a job. I spent some time more time reading up on the maths. Now I’m gonna sit down and work on the code.
This weekend is super busy so I probably won’t have time to get much done. I’ll do my best.

Developer Diary April week 1

Last week was a mess. I finally got to check out the new Himeji castle with a friend, so that was very nice. I also spent a few days looking for work. It’s very sparse in Adelaide, moving to Sydney/Melbourne is looking increasingly necessary.

I started trying to make the basics of a first-person view for the game. I have implemented mouse look to a degree I’d call it done, plus you can change the camera view from joystick to mouse easily (quaternion versus cardinal axis). This seems like a minor thing but it’s the difference between a first person view and a space simulator.

I made some more progress to texture unwrapping and binding on models.

I also attempted to make a start on the game. I started by modifying the testearth model into a simple quad and wrapping a tile texture on to it, I then built a thousand of them and experienced shocking and unacceptable lag – down to 1 frame per second.

I’m hoping that this is just because I’m making the draw calls in nested for loops. More experimentation is required.

I was able to draw 100 fighter01-s on screen, about 600 polygons without real issue. 1000 tiles should have only been 2000 polygons, which is not much more than 600. This is a serious constraint.

In terms of my goals for the last month:

Major objectives
Resolved gimbal lock issue (complete)
Implemented mouse look (complete)
Implemented joystick look (complete)
Implemented different camera modes (complete)
Implement importing from Blender to C++ (Partial)
-> Vertex/normal/material complete. Still to complete textures.

My overall goal is now putting out prototype games, with ideally one completed per month. I have two capabilities I still want to work on, but for the most part I’m now mainly focused on developing games.
The capabilities are texturing on models, and sound/music media.

I’ll spend some time working out best practices for vertex buffering. I’ve been reading about ‘instancing’ for displaying multiple objects of the same type which may be appropriate for tiling. Games like World of Warcraft are able to display many thousands of vertexes, with hundreds of models on screen at a time, running at 60fps without much issue on my current hardware. I don’t need to reach this goal but I’m wondering if there’s a better way to do things than I currently am.

***

This week has mostly been theoretical. When I was unable to freely draw tiles as I had hoped I became concerned that I would be unable to make an interesting game. So this threatened my creativity and I didn’t like it.

I have generally identified the bottleneck. It’s ‘somewhere’ in my shader update code. I tried using a bare bones shader that didn’t make any real changes to the fragments and confirmed that it was unrelated to what’s going on in the fragment shader.

At a guess, I would pin it on the calculation for the normal matrix, which requires an inverse transpose of the modelview matrix. The normal matrix is required for models that will need to undergo a scaling process to ensure a consistent scaling procedure. In other words, it allows me to make models bigger/smaller.

Since I don’t need this feature at present, I can use the more computationally efficient version of vector normal * modelview matrix for these models, and use the less efficient version for any model that needs to scale at a later date. Alternatively, I can also program size changes as an animation and interpolate the vertexes to their new position. I’ll test that when I get to it.

The second take away from this is that it’s the update-part of the code that’s causing the bottleneck, and this is worse when I sent lots of models to be drawn. 100 identical 4 vertex models ran at 250 frames per second. If I merged this into a single 400 vertex model, It’s possible that it will run more efficiently.

Actually, since I’ve got three testEarth’s and a skybox in the scene, and each one of them has roughly 700 vertexes, I think I already know the answer. That’s already 2800 vertexes with no concern.

Lets test it out.

High vertex count/low model count + simple calculation = 800 – 900 fps.
Low vertex count/high model count + simple calculation = 400 – 425 fps.
High vertex count/low model count + hard calculation = 700 – 900 fps
Low vertex count/high model count + hard calculation = 250 – 270 fps.

I observed that when the testearth was in the camera, the lower fps score appeared, probably indicating the additional work that these spheres put on the fragment shader. When the flat tiles were in the shot, the score would be somewhere in the middle. When the camera was pointing off into space, the highest score was reached.

So in conclusion:
More complex models with a lower model count is always better than a lot of small models.
The simpler calculation appears to be twice as fast as the complex calculation.
I should use the simple calculation wherever possible.

Using the simplified calculation:
1000 4 vertex models ran at 55-60 fps (acceptable, we are never going to have 1000 models on screen)
10000 4 vertex models ran at 5 fps (If I’m never going to use 1000 models, 10000 is even more unlikely).

So that’s great. I haven’t really solved the bottleneck, but I’m able to side step it so it has no effect, and in the world of computer programming, that’s usually all that’s needed.

Tuesday:
I spent today working on the quad tile-builder that I intend to use to lay out some basic levels for the game. I was able to use parts of the testsphere code to make this process easier. In the process I learned a bit more about how vertexes interact with a texture and a shader to get a more desired result.
At the moment I can only build square tiles, however it shouldn’t be too difficult to be able to make tiles that are irregular or even sheared.

With this I plan to lay out a basic level, maybe four rooms, so that I can try out different textures and start looking at game physics. For example, at the moment, the camera flies through space like a ship. For a first-person-view, I need the camera to be constrained near the ground, to simulate a person walking around. Also, if you get too close to an object, you can see through it and even pass inside of it. I’ll want to add basic collision detection to prevent walking through walls.

Finally I’ll want to build some simple models to represent the robots and code some AI for them, as well as start working out the game mechanics.

By then I should have all the tools I need, and it’s just a case of using them to make something.

Wednesday: I forgot to mention that Monday I was back at work again so I couldn’t code.
Today I’m going to lay out a basic level and start making it look and feel like a first person view.
I spent a little bit of time laying out an algorithm for making tiles in 3D space, as well as irregular tiles, but I decided that since I’m ultimately intending to use Blender to make my models, there’s little point in continuing progress on the tile factory.

The level will consist of four ‘rooms’ with walls and no roof. There will be door spaces between the rooms. This should be enough to start testing basic collisions avoidance and start dropping in some robot models to play with.

Wednesday evening

Making even a single wall with a gap in it was quite fiddly, having to mess around with manual rotation/location setting. When I realised I would have to make quads for the top/sides as well as the insides of the door frame, I was ugh. That’s a lot of objects.

I’m going to build the scene in Blender using materials. Tomorrow I’m going to look at UV wrapping. I feel like I can advance so much faster if I’m using a proper modelling tool.

I’ll have a look at collision detection when that’s done.

Thursday night: Using Blender to make the same room didn’t take long at all. Now working on collision detection. I’m going to use simple, box collision detection (as opposed to spherical or cylindrical) for the purposes of the demo. I may later want to add stairs/ramps and other types will be needed.

Sunday night: I spent Friday laying out new classes and working out how I’m going to do efficient collision detection. Originally I mentioned an ‘actors’ class. Now there’s a scene and a prop class.

Collision detection basically works like this: Go through my list of actors (an actor is something like a spaceship, or a rocket, or even a player controlled character) and check it against the geometry of everything else in the game to see if there’s some kind of overlap. If so, do an appropriate interaction.

However, this means the larger the game sets get, the more complex these checks become, and the game gets bogged down working out physics instead of updating the screen.

I can get around this by breaking up the game world into different lists that become active only when an actor attempts to enter them/until an actor leaves. I can also maintain a list of what actors are currently present in any given scene, so that I don’t have to check an actor with another actor in a different room.

I’ll spend this week getting this up and running.

I also spent a good chunk of this week getting my resume up to date. The only downside of living in Japan for so long, is that I’m worried what employers will say when they look at my resume.
“So what did you do for the last two and a half years?”
“I, uh, taught English to kindergarden children.”
“We are sorry, we were looking for software engineers.”
“But I AM a software engineer. Stop laughing ; ~; ”

Or something like that. That’s the reason I’ve been coding all this time, I knew if I didn’t keep up my skills or learn something new, I could never break in to the IT industry.

Yesterday, we bought our tickets. We’ll be back in Adelaide early August 2015.