Maths

The 1D Radial Height Field

Posted on

It is common in games to use a generic, complex and powerful system to solve a small simple problem. There are many reasons for that:

  • developer is familiar with the system/tool – familiarity – we work faster with the tools we know how to use!
  • it’s available and needs no additional work – reuse – saving effort and money!
  • seems like the right “realistic” way to solve the problem – stay grounded
  • will solve the problem in all possible scenarios that would happen – be robust

All good reasons and I’m sure there are more. To illustrate this let’s take game physics and collision detection – often such a system in games. They can:

  • check for “line-of-sight”
  • use custom colliders (invisible walls) to solve game play problems
  • use it to ensure camera doesn’t get in a place where it won’t provide useful view to the player

These sound so common and natural. They are now standard uses of these systems in games and many people often wouldn’t think twice if they had to solve one of the above problems. I’m sure you can find other countless examples.

However…

… I want to talk about using a custom solution to solve a problem that would otherwise be solved by a generic system. In Mazer that would be the camera control and not letting it get in a place where random geometry would obscure the player’s view.

Using custom solution for camera control in Mazer. The line describes the area of safe camera movement.
Using custom solution for camera control in Mazer. The line describes the area of safe camera movement.

In Mazer the camera always looks at the top of the maze tower the player is constructing and is surrounded by other “leaderboard” towers. The camera position however is procedurally and programatically controlled to be “interesting” and “cool” with the music and gameplay. It can happen that the camera would intersect with surrounding towers obscuring the player’s view and rendering the game unplayable.

Simple brute-force solution to this problem would be to construct a camera frustum and check all surrounding towers for intersection. Easy enough to implement that solution has one major problem – it only provides us with the information that something bad has happened but not with the information needed to resolve the situation.

Next, more elaborate algorithms can be involved where we can have objects be physical entities (rigid-bodies) and just let them collide and slide against each other – never to intersect and get the player in trouble. That would solve the problem and perhaps look good too – one can never be sure before it’s implemented. However, it would be like using a massive hammer to hit a tiny nail.

The solution I use in Mazer uses a more simplistic yet robust approach. It is based on the knowledge that the camera is not completely free and there are various constraints that allow us to solve that problem in a different/targeted way.

Height Field (1D)

First a small detour into height fields. A height field is a scalar field of heights. Quite often you’d see that as a terrain representation where given 2D coordinates you can get the height of the terrain at that point.

hf_p1_1
Fig 1. Height field function using data control points.

A simpler form of this is a 1D height field. In essence that is just a function where given one coordinate “x” and evaluating the height field function h(x) you can get the height (or “y” coordinate).

This can be achieved with a polynomial of some fashion. For example f(x) = 2*x – x*x. That way we have a continuos solution and a known function that gives us a value at every (most) values of x.

However, if we have some data and we want our height function to match that data we can use an array of control points that specify the height at various values of “x” and an interpolation policy allowing the function to give a continuos result for any value of “x” (Figure 1). I find this to be a common scenario throughout development.

I’m using a linear interpolation here but a more complex methods of interpolation can provide a better (and higher order) continuity.

Height Field (1d) on a Circle 

Note: if anyone knows a better name for this method (there must be one), please let me know.

Now imagine we wrap the 1D height field over a circle. Now x is the angle in radians so any values outside the range of [0; 2*π] are equivalent to that range. So we need to define our h(x) just for that range.

If we have h(x) =0, our Circle Height Field will be just a dot. If we have h(x) = 1, our field will be a circle with radius 1.

Fig 2. Data points plotted on a circle.
Fig 2. Data points plotted on a circle. Note: in a proper implementation drawing the straight lines would be curved with the circle curvature as the 1D line is wrapped around the circle.

Figure 2 illustrates how our 1D data points height field above translates to this idea. It is the same field with the same data points but now plotted on a circle.

In code, I often need to plot the circle height field so I can visualise it and troubleshoot problems with my code. To do so we need to get a 2D point for every value of x. Here’s how we do this:

Vector2 GetCircleHeightFieldPoint(float x)
{
   //calculate the unit vector at X angle
   Vector2 unit = Vector2(fcos(x), fsin(x));

   //get the height at X angle
   float h = HeightFieldFunction(x);

   //combine them to get the point on our circle height field at that angle
   return unit*h;
}

By iterating a number of  values of “x” in the range of [0; 2*π] we can get a full representation of the radial height field. All images below (screens from Mazer) use this method to visualise the field.

Camera  Control

How is that relevant to camera control?

Mazer screen with a radial height field.
Mazer screen with a radial height field used for camera control.

I calculate the area the camera can go without getting the user in trouble. I start with and empty height field function h(x) and then I plot, in the height field, all the obstacles that can obscure the camera view. In my case each obstacle is a box. Once projected on a circle it becomes a curve segment that I have to draw (project) on my h(x). There is more information about this process below.

Once I complete that I have a h(x) that gives me the maximum distance (height) the camera can be in at every angle. If I keep the camera within that limit I know I won’t get any visual problems. Even more, if I find that the camera has strayed into an area that is “not good”, I can immediately take remedial action in the right direction or quickly evaluate many other potential points the camera can go very cheaply.

For now I’ll just show a simple method that limits the camera within that height-field – if it goes beyond it, it limits the camera to the maximum distance.

Vector2 LimitCameraPosition(Vector2 cameraPosition)
{
   //get the "height" the current camera position is at 
   float height = length(cameraPosition);

   //normalise to get the unit vector
   Vector2 unit = normalise(cameraPosition);

   //convert to angle representation
   float angle = UnitToAngle(unit);

   //look up the height function to get the max height at that angle
   float maxHeight = HeightFieldFunction(angle);

   //limit the distance to that max height
   if (height > maxHeight)
   {
      return unit*maxHeight;
   } 

   return cameraPosition; 
}

In the code above there is a function to convert from a unit vector to an angle scalar (in radians). While that’s trivial using an atan2 function from the standard library, you have to remember to wrap that around and keep the angle in the range of  [0; 2*π].

float UnitToAngle(const Vector2& unit)
{
   //get angle
   float ang =  atan2(unit.y, unit.x);
   
   //keep it in the range 
   if (ang < 0.0f)
        ang += PI*2.0f;
    
   return ang;
}

Obstacle Drawing: Preparing a Useful Height Field

Mazer screen illustrating the "safe" camera field. Note how each box/column makes a dent into what is otherwise a perfect circle.
Mazer screen illustrating the “safe” camera field. Note how each box/column makes a dent into what is otherwise a perfect circle.

Now that we have the basics of our radial height field for camera movement we need a method to insert useful data in it. The method I use is to initalise the field to some default maximum value – at that point it’s just a circle with radius of “maximum value”.

Then I “draw” various obstacles that in-turn would “dent” the circle and make the function non uniform. In the Mazer case the obstacles are the “score” boxes.

For each box I find the bonding circle of that box in 2D and then from the centre and radius of that bound sphere I find two points determining the extents (in the height field circle) of the arc that it would take. Then I step through the line segment those two points define intersecting a ray (starting at the origin and pointing towards the step point on the segment) with the box obstacle itself.

Then I check if the distance to the intersection point is less than the distance stored in the closest control point in the field function and write it in. In a way this acts as a 1D circular depth-buffer.

Finally I do a low pass filter on the data (field) so that all edges are smooth and provide a more gradual response when I use it for camera control.

Performance

I look up the constructed field multiple times a frame. However that would be only for certain values of “x”.

Most performance hit is taken when I’m constructing the field and rasterising the obstacles in it. Right now I do that every frame and it has a resolution of 128 control points for the whole range of  [0; 2*π]. That gives me a good resolution for quality camera control and I haven’t seen any visible performance impact.

Other Applications

I’m sure this method has it’s applications in game AI. I know I’ve seen this visualised before in games (or debug information in games) and that’s how I got to know about it. I can think of AI agents using it to plot a 360 degree of threat so the AI can reason about the best course of action for that agent. Or maybe representing the audio “hearing” of the AI agent so it can reason about where the sounds are coming from and how to react.

This approach also shares similar ground with the “context maps” described in this post by @tenpn http://andrewfray.wordpress.com/2013/03/26/context-behaviours-know-how-to-share/

That’s it for now. See you next time.

Advertisements

Tuturnions FTW!

Aside Posted on

Tuturnions

Ver. 1.0

Introduction

Quaternions have been around for some time now. Sometimes game programmers use them for rotations in graphics – after all they (quaternions) have lots of good properties. Programmers have good properties too. As it happens people use them without understanding them… but they work all the same – another good property of theirs. Quaternions too.

Anyway, we are not here to talk about quaternions as we already know about them and if you don’t, fear not, there is tons of info on the web and if you really care there are even books… now if you are hardcore enough you can go into some geometric algebra but that’s another story…

We are going to discuss Tuturnions. So what are they?

1. Tuturnions – they tuturn things

Let’s revisit the average quaternion definition (I mean, definition as the average programmer, me, defines it):

“Quaternions – they look like 4D vectors, you know, and they rotate things in 3D, and you can interpolate them, and they take less storage than 3×3 matrix, and they are easy to invert and so on”.

So couple of days ago I was doing some 2D stuff and thinking… well doing 2D stuff definitely, thinking – not so much, but anyway, it popped in my head – if we have these quaternions that can rotate stuff in 3D how come there aren’t any cool 2D rotating entities and I’m stuck with these 2×2 matrices[1]. So, without wasting my time with googling and internet and other spoilers like that, I put my wheel inventing hat on and there they were – Tuturnions.

Now, I’ve got to warn you, most of these things I’m going to talk about can actually be done with a 2×2 matrix (or are equivalent to it). But unless there is some secret society against ignoring 2×2 matrices when it comes to rotations we should be safe – come to think of it, I haven’t googled that either.

So, here’s the rules:

  • We want to be able to convert between our Tuturnions and 2×2 rotation matrices easily
  • Easy to keep the Tuturnion constrained so it can rotate stuff ( Quaternions need to be normalized to rotate stuff – right? )
  • Easy to perform operations on them – inversion, rotation concatenation, interpolation, etc

2. Tuturnions – the 2D quaternions

In 2D if we are given an angle, lets call it theta, we can rotate a vector using the following equations:

X’ = cos(theta)*X – sin(theta)*Y

Y’ = sin(theta)*X + cos(theta)*Y

And you can easily see how that translates to a 2×2 matrix. If you don’t, you either need glasses or you don’t understand how matrices work – another excellent reason to keep reading.

Looking at these equations we can see that really, there is only one quantity involved here when it comes to rotation – the angle theta. But obviously, everyone knows that sine and cosine are quite expensive operations[2] so we don’t really want to deal with just the angle. Also angle would be a bit tricky to interpolate continuously without some conditional statements.

But here is an idea: instead of using the angle we could use sin(theta) and cos(theta) instead – revolutionary isn’t it? So our Tuturionon will have two components called C and S. I’ll leave you guessing which one is which. Also, they do sound like they should have two components – two-turniouns.

Basically, in many respects, our Tuturion is a 2D vector. In order to represent a rotation though it needs to be normalized so if we have a Tu(c,s) following has to hold true:

C2 + S2 = 1

…and if you check your school math, like I did, you’ll remember that:

cos(theta)2 + sin(theta)2  = 1

You must admit our Tuturnions look more like 2D quaternions now. Though if we were to say they looked like unit 2D vectors[3] we would be a lot closer to the mark but quite boring to talk about them.

2.1 Interpolation

Interpolation of rotation entities is important, especially if you are doing animation system or you just want to have some fun.

2.1.1 Lerp

We can linearly interpolate a Tuturnion – it is a 2D vector after all. If you can’t interpolate a 2D vector I think you probably need to cover some more basic material first, though I admit, it might be challenging to find such material but if you got so far with this article it’s obvious that you like a challenge.

Anyway after we interpolate we need to re-normalise the Tuturnion, so it represents a rotation once again.

2.1.2 Slerp

We could also interpolate our Tuturnions using Slerp.

Yes, turns out Slerp is not really just for quaternions (Slurprised? Me too!) and we can apply it to everything in order to interpolate. Although it kind of beats me, if it wasn’t to do anything with 3D and quaternions, why on earth would someone call it spherical linear interpolation. After all the Slerp uses sine and cosine functions of the angle between the interpolated quantities and if anything should be called circular linear interpolation – Clerp.

Bottom line: you can use Clerp to interpolate tuturnions.

2.2 Conversion

This chapter seems to require a lot of 2×2 matrix visualization and my “word” skills are as advanced as my math skills. Short story long you have a sine and cosine (from your Tuturnion) and you already know how to make a 2×2 matrix from that, don’t you?

As for the 2×2 matrix to Tuturnion it should be clear by now, but if you want me to spell it for you: given a rotation matrix M you get equivalent tuturnion T(m11, m12)

2.3 Operations

Just like quaternions and rotation matrices you can perform numerous operations on a Tuturnion.

2.3.1 Rotate a 2D vector

In order to rotate a 2D vector V(x,y) by a Tuturnion denoted by T(c,s) you need to (replacing from the formula above):

x’ = c*x – s*y

y’ = c*y + s*x

Looks incredibly like these equations I showed you before and the reason for that is simple: “if it works – don’t fix it”.

2.3.2 Combine rotations

You need to simply multiply (transform) the two tuturnions. In essence the operation is the same as rotating a 2D vector but again our Tuturnion could be a 2D vector but that would be a wild guess.

In our example we have T1(c1,s1) and T2(c2,s2) we get the result T(cr, sr):

cr = c1*c2 – s1* s2

sr = c1*s1 + s2* c2

We could spend some time deriving that this is actually true but I’ve always found that part boring to read in articles and to be honest it looks boring to write as well. In fact I don’t see why people bother…

2.3.3 Inversion

When you work with rotations, it happens some times, you want to rotate stuff backwards. In order to do that you need to invert your rotation entity.

With Tuturnions this is quite easy – you just need to invert your tuturnion’s S part and there you are. It may come as a surprise to you (thought if it does you probably need to stop reading and consider going into politics instead), but if you look at your 2×2 rotation matrix and transpose it, because that’s how you invert it apparently, you can see how the sign changes place but then again that could be some weird coincidence.

We can go on and provide some proof by actually inverting the angle and checking what happens to the sine and cosine functions then. I’ll leave that an exercise to the reader, though believe me, going to the gym will be a far better exercise.

3 Applications and future work

If you are developing a 2D skeleton animation system you could find tuturnions useful. They will compress quite well, bearing in mind you can actually compress them pretty much in to a single entity.

3.1 Future work

Integrate a special quantity Q in the Tuturnion so they sound more complicated.

Conclusion

We have introduced new powerful rotation entities for 2D. They resemble quaternions in many ways (or at least one – they rotate things). They are easy to work with and they eliminate the need for 2×2 matrices when it comes to rotation – especially useful if you have “a thing” against matrices. They do have a cool name (that’s mainly what marketing is banking on) and they save a whooping 8 bytes if you use them instead of 2×2 matrix.

 

 

[1] That’s a long sentence, isn’t it?

[2] Well, you can approximate and some hardware supports them natively but where is the fun in that?

[3] It is important that when you are talking about Tuturnions you always use T(c,s) and not T(x,y).