Don't let the title deceive you, this is not a simple rotation case. This is the subject that I've spent more time on than any other in my tank game so far, even more than the rest of the game combined. If I had found a solution, this dev journal entry would probably be named "Orientation of Objects Substantially Larger Than Heightmap Resolution". After a week[sup]1[/sup] of working on it, I thought I would end up writing a tutorial on this, due to being unable to find reference material for this particular problem (aside from one page that I have been unable to find again and isn't in the browser history when I got to looking for it). After a month[sup]1[/sup] plus of working on this, I decided it was time to move on as my motivation was getting sapped. I may come back to this problem later, but for now, I want to get the rest of the game working.
This problem is determining the pitch and roll of the tanks based on the terrain they are over. Positioning an object on a heightmap using a single point is a fairly simple task and I could find an abundance of reference material on it. When using a single point, the orientation of the object can be determined by looking at the normal of the heightmap cell it is in or the face it is on. However, my tanks are substantially larger than the resolution of my heightmap. The tanks roughly have a footprint of 9.5 meters by 3.5 meters, and the heightmap is a regular 2d grid in xz with indices being 1 meter apart. I could increase distance between points on the heightmap, but thought that there must be a better solution.
While looking for the better solution, I spun off test programs so that I could debug different techniques and their parts separately from the whole game and not have to revert the changes in order to get the game back. This showed one of the strengths of XNA, how quickly a new program can get up and running so you can concentrate on what you are trying to do. Window creation, gathering input, model loading, basic rendering are all there once the project is created. The only thing missing is a basic camera class or struct, which of course I brought over from the game. While I'm not sold on XNA for large projects, for test programs the quick setup is very nice.
[heading]First Test Program[/heading]
The first test program was to debug part of an algorithm that didn't pan out. My first attempt was to gather all the entries in the heightmap that are within the bounding box of the object/tank, and from there try to determine the pitch and roll. For this and the next attempt, the real trick is going from heightmap values to pitch and roll, which I will discuss in the next section. This way of gathering heightmap values has a flaw in that it could cause the object to clip through an incline if the bounds didn't end on an integer value (due to the heightmap having a resolution of 1 meter and its alignment).
The part of first attempt that the first test program dealt with is determining which entries in the heightmap are within the object's bounding box. There are 4 pieces of information needed for this search, the bounding box, object's position, the object's rotation (just yaw since determining pitch and roll is the ultimate goal), and the heightmap. The axis-aligned bounding box, which XNA's BoundingBox struct represents, is determined by the model. After doing a model processor for skeletal animation, writing one to determine the bounding box was trivial. The object's position and rotation are variables that could be adjusted by the user and are passed to the function that does the search. The heightmap is the class I put the search function in, and for the sake of this test it is just an 11 by 11 grid with all heights set to 0. The search has an additional twist of in the design doc I specified that the origin of the model is to be the center of mass[sup]2[/sup], which is not necessarily the geometric center. This is easy to deal with, but worth mentioning. As with ray-sphere intersection on scaled, rotated, and translated spheres discussed in my previous dev journal entry, I created a matrix but this one is to convert the entries of the heightmap, which are in world space, into the object space of the bounds. This matrix is:
Matrix.CreateTranslation(-box.Center()) * rot * Matrix.CreateTranslation(pos)Where box.Center() is an extension method to get the center of the BoundingBox, rot is the object's rotation matrix for yaw, and pos is the position of the object in world space. As with the ray conversion, I multiplied each heightmap entry against by the inverse of the matrix. The result of the conversions are run against BoundingBox's Contains method, and so long as it does not return ContainmentType.Disjoint, the position is in bounds.
In order to verify this part of the algorithm worked and debug earlier iterations of the code, I drew a series of squares to represent the heightmap locations which are colored white if not a match and green if they are within the bounds. The squares were centered at the heightmap position and scaled down slightly to not overlap. An outline box was also drawn as reference for where the bounds are. The model for the outline box was also the model used for creating the bounding box for this test program rather than tank model from the game. A screen shot is below (note: white squares that partially overlap with the outline box are outside the bounds because it is the center of the square that is the entry in the heightmap and the center is outside the outline box).
[heading]Second Test Program[/heading]
The purpose of the second test program was to convert the heightmap values into pitch and roll, the hard part of this problem. A variant of the outline box model was used for this program, with the change being adding some height to the model. Since I didn't bother making the outline box anything more than a series of faces in either tester, in this tester I set the cull mode to none so that both front and back faces would be drawn. In addition to that model, several terrain test patches were created to cover all the basic scenarios and some more complicated ones. So that the object's position was fixed for the tests against the different terrain, instead of moving the object, I switched the terrain and ran the algorithm on the switch. Doing it this way was nice so that breakpoints were not being hit on every update cycle, just when there was an actual change.
From taking the final code from the first test program and integrating it into the second, I quickly realized that this was not going work. It's been quite awhile since this part, so I don't remember all the problems. But from what I remember, the two main problems were:
1. The y value for the object was an unknown, and wouldn't be known until the pitch and roll were known.
2. By taking all of the heightmap entries within the bounds, I could compute the pitch and roll between any number of them, and how many there were would depend on the footprint of the object.
To handle problem 2, I tried to split the heightmap entries into quadrants within the bounds, trying to keep track of the entry that would cause the greatest pitch and/or roll. This is what made problem 1 an issue since to calculate the pitch and roll of a point relative to the center, both points needed to be known and the center was not yet known.
Those problems and that reference page I couldn't re-find, caused me to switch to a completely different method. I would use control points[sup]3[/sup] at defined positions on the bounding box of the object and deal with pitch and roll between the control points. In order to avoid clipping through the crest of a hill, I went with 8 control points, 4 at the corners and the other 4 along the perimeter aligned with the center of mass. The numbers in the image below are the indices I used into the array that stored the points.
For each control point, the heightmap would be queried for the height at that point. After that, the points could be combined to compute various pitches and rolls. Since I had decided in the design doc that models should be facing the +x direction, pitch is rotation around the z axis and roll around the x axis. Based on XNA's description of the arguments in Matrix.CreateFromYawPitchRoll, it seems more typical to have the facing direction be along +z. In my next game, I will change the facing direction, but will keep my current one for this game and test programs. In the image below, the numbers are the indices in the arrays of floats for keeping track of the individual pitches and rolls between the control points. In case it's not clear, the 4 and 5 indices are between the corner control points and the rest are between a particular corner and a center of mass aligned control point.
After computing the various pitches and rolls between the control points, the remaining questions were:
1. Which of those values should be used for pitch and roll?
2. What is the y value for the object's position?
I'll answer the second question first as it was consistent across any method I used to try to answer the first question. For each control point, I took the xz vector from subtracting the highest control point from the current one one and applied the pitch and roll from the answer to the first question to that vector, then added the resulting vector to the highest control point. Since code is probably more clear (note: going through only the first 4 indices is because those are the corner control points and the only ones needed for the next part):
for (int i = 0; i < 4; ++i)
{
if (i != max_index)
{
Vector3 xz = new Vector3(
control_points_object.X - control_points_object[max_index].X,
0,
control_points_object.Z - control_points_object[max_index].Z);
control_points_object =
Vector3.Transform(xz,pitch_roll) + control_points_object[max_index];
}
}After that, performing bilinear interpolation on the corner control points would result in the y value for the object's position.
The answer to the first question is where I got stuck. After trying a variety of methods, I asked on the forums in case someone else had solved this problem before. Apparently, this isn't a common problem as there were no responses, which had me hoping I could find a solution and post a tutorial on it in a dev journal. The methods I had tried before posting the question were doing the min, max, min magnitude, and max magnitude per side and combining the sides with the same variety of functions. Resorting to these combinations was well after thinking about the problem and trying/debugging the one that seemed reasonable. Some would give reasonable results in default orientation, but break when I tested with other yaws (my test cases were yaws, in radians, of 0, pi/4, pi/2, 3*pi/4,pi,-pi/4). I then tried to do a series of if/else cases for equalities and inequalities, which again worked in default orientation and broke in several of the other terrain/yaw test cases.
Also, in the course of these initial attempts, it was clear that when both pitch and roll were non-zero each needed to be scaled back. Rotating by both at their full values caused over-rotation and the object to clip through the terrain. The scaling factor I used after realizing its necessity was:
public float Scale
{
get
{
return Math.Abs(Pitch) / (Math.Abs(Pitch) + Math.Abs(Roll) + .000001f);
}
}With the "+ .000001f" simply to handle the case were pitch and roll are both 0. For applying the scaling factor, it is simply Scale * Pitch, and (1 - Scale) * Roll.
The next time I worked on this after posting the question on the forums, I tried a brute force approach. Go through all combinations of pitches and rolls between the control points, assign a score to each combination, and pick the one with the best score. So that I could debug the scoring method, I made the test program keep all the combinations and flip to the next best combination with a button press. My goal with this brute force method was to find the right answer in all the test cases and analyze the results to find out what is the right combination method.
After debugging the scoring mechanism and code, I went with a two part scoring mechanism. The first part is that combinations whose control points all remain at or above their heightmap values are better than those that have any that dip below. After that, it is which combination has the smallest total increase for each control point's y value over their heightmap values. What I was shooting for with this scoring mechanism is finding the result that matched the terrain the closest without going below it.
From analyzing the results of that scoring mechanism, the min/max approaches didn't fit the results at all. So, I adjusted my if/else method of computing the final result to be very close to the brute force method. It wasn't an exact match because the analysis showed a contradiction. Looking at one of the test cases for the inequality results would require a particular index to be used, but a different test case with the same inequality result, would need a different index. After adjusting the if/else method, I re-enabled that code and disabled the scoring mechanism and ran through the test cases. While most of the results looked good, the contradiction case looked terrible.
[heading]Game Integration[/heading]
Since the scoring mechanism produced good results and at this point I wanted to get on with the game and not stay on this problem indefinitely (I might come back to it eventually), I tried plugging the scoring method into the game. Given what the game currently does and what I expect it to do, it should be able to handle the added performance cost of running through the combinations without a noticeable degradation to performance. Performance wasn't the problem. While the scoring results looked good in a static scene, when applied to a moving object the difference frame-to-frame was too severe. The camera is at a fixed following distance from the tank, so the tank's movement affects the camera which made the jitter very apparent. The jitter was due to only looking at the tank's current position on the terrain, so the best fit pitch and roll on that frame had no relation to the pitch and roll on the previous.
At this point, I've decided it's time to move on with my game as there are plenty of other aspects that need to be implemented. At the time of working on this problem, there wasn't a hud, object-object collision detection, or any AI yet. The first two of those have since been added and the third is the next topic to start looking at[sup]4[/sup]. While I'm not sure if there is a way to combine the various pitches and rolls between the control points to get a satisfying result, I think this problem might be solvable by using physics to tell the tank when the ground level has increased or when center of mass has crested a hill or cliff and can start tilting down. But, physics simulation is a subject well beyond the scope of this particular game. So for now, my game is just going with level terrain. Since the goals of the game are to:
1. Get experience with XNA
2. Create a full game
3. Be a small game that can be developed quickly
I'm willing to sacrifice the detail of cresting hills and crossing short trenches, since that detail combined with how much is left to do has made the "quickly" part of goal #3 to have passed.
[heading]Foot Notes[/heading]
[sup]1[/sup] Just to be clear, these are calendar times and has been spare time work, definitely no where close to 40+ hour work weeks.
[sup]2[/sup] The reason for models having their origin be the center of mass instead of their geometric center is because when I was doing the initial planning, I was thinking of integrating some physics into it. I have since decided that physics is outside the scope of this game due to the amount of complexity it brings and this was supposed to be a quick to develop game.
[sup]3[/sup] "Control points" might not be the conventional term and could be why I can't re-find that reference page.
[sup]4[/sup] I read "Programming Game AI by Example" by Mat Buckland a couple months ago and look forward to applying some of that.
