TO BE WRITTEN

# Category Archives: Uncategorized

# Object Management and Factories

Recently I presented a lecture on the topic of Object Management and Factories. The slides include details about object lookup, great for Component Based Architecture and the ever hyped Entity Component Systems. Here are the slides, enjoy!

# Custom Physics Engine – Part 2: Manifold Generation

# Introduction

During the previous article in this Custom Physics Engine series we talked about impulse resolution. Though understanding the mathematics and physics presented there are important, not much could be put into practice without both collision detection and manifold generation.

Collision detection is a pretty widely documented area, and so I won’t go into too much detail on how to achieve collision detection in this article series. Instead I’ll focus on manifold generation, which is in my opinion much more difficult and less-documented compared to collision detection.

In general collision detection is useful for retrieving a boolean result of “are these two things colliding”. The usefulness of such a result ends when this collision needs to be resolved. This is where manifold generation comes in.

# Manifold Generation – Summary

A manifold, in context of physics engines, is a small structure that contains data about the details of a collision between two objects. The two bodies are commonly referred to as A and B. Whenever referring to a “collision” as a system, A is usually the reference object, as in the problem is viewed from A’s orthonormal basis.

I am not actually sure why this structure is called “the manifold”, and I do not know anyone that actually knows. So don’t ask! Either way this structure should be passed around by reference or pointer to avoid unnecessary copies. I also pool all my manifolds, and intrusively link them in order to keep a list of active manifolds during a scene’s step (the term scene is defined in the previous article).

Manifold generation involves gathering three pieces of information:

- Points of contact
- Penetration depth
- Vector of resolution, or collision normal

The points of contact are 2D points (or 3D for a 3D engine) that mark where one shape overlaps another. Usually these contact points are placed onto the vertex of one shape that resides within another.

The penetration depth is the depth of which the two shapes are intersecting. This is found using the Separating Axis Test (SAT). There are lots of resources around that talk about SAT, so I suggest googling for them. The penetration depth is defined as the axis of least penetration. In this case (assuming blue’s frame of reference and vertical as y axis) the y axis is the axis of least penetration.

The collision normal is used to describe in which direction to press both objects away from one another. The collision normal will be a face normal, and in this case it would be a normal pointing towards the brown box, where the normal corresponds to the blue box’s top face.

Generating these three pieces of information can be quite a challenge. Now lets view what a possible setup of the manifold structure might look like:

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 |
// Represents a single point of contact during a collision struct Contact { Vec position; Vec normal; float penetration; }; struct Manifold { Contact contacts[2]; unsigned contactCount; Body *A; Body *B; } |

Note that there can be a variable amount of contact points. I suggest having a contactCount of zero signify “no collision”. I also suggest having only two possible points of contact for a 2D simulation, and to start just use a single possible point of contact. More than one point of contact isn’t necessary until advanced constraint resolution is used (a future article).

It is important to just keep an array of contacts within this data structure as to keep strong cache coherency. There’s no reason to dynamically allocate the array of contacts.

# Circle to Circle

I’ll be covering how to gather manifold information for specialized cases of couple different types of shapes. Lets first go over circle to circle first. Here is what the definition of a circle would look like:

1 2 3 4 5 |
struct Circle { float r; Vec position; }; |

The first thing to do is to see if they are colliding or not. Again, throughout this article I’m going to mostly blaze through the collision detection and focus just on gathering important manifold information. Feel free to google or ask specific questions in the comments about collision detection.

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 |
Manifold m; // translation vector between two shapes Vec t = B->pos - A->pos // Cumulative radius float radius = A->r + B->r // Early out condition if(t.LengthSquared( ) > radius * radius) return non-intersecting // Perform sqrt with pythagorean theorem float d = t.Length( ) Contact *c = m.contact1 // Right on top of each other if(d == 0.0f) { // Choose random (but consistent) values c->penetration = A->r; c->normal = Vec( 1, 0 ) c->position = A->pos m.contactCount = 1 } else { c->penetration = radius - d // Utilize our d since we performed sqrt on it already c->normal = t / d // Take A's position and move it along the contact normal // the distance of A's radius c->position = c->normal * A->r + a->pos m.contactCount = 1 } return m |

The above code is really quite simple. The important thing to note is that our contact normal will always be a vector from A to B. In order to create a vector from one point to another you take your endpoint minus your starting pointer. In this case B’s position subtracted by A’s position. This results in a vector from A to B. This vector normalized will be the collision normal, or in other words the direction in which to resolve the collision.

It is important to note that no square root functions are called before the early out condition is checked. Most of the time your shapes are probably not colliding, and so there’s no reason to use a square rooted value.

The last tricky thing is to check if the two shapes are right on top of each other. Though this is unlikely in a dynamic environment, sometimes shapes can be placed directly upon one another through an editor. It is important to, in all collision detection functions, to handle all special cases, even if the handling is bad. Whatever you do just make sure you are consistent. I just chose a random vector to resolve in the direction of.

The nice thing about cirlce to circle collision is that only one collision point is really needed. Just be sure to be consistent in how you choose your collision point in order to reduce simulation jitter.

# AABB to AABB

Collision detection between two AABBs is a bit more complicated than two circles but still quite simple. The idea is to make use of min and max. Lets assume we’re storing our AABBs in a structure like so:

1 2 3 4 5 |
struct AABB { Vec min; // lower x and y coordinate position Vec max; // higher x and y coordinate position }; |

This allows a very simple algorithm to find points of contact. For convex polygons that are not axis aligned often times Sutherland-Hodgman clipping will need to be performed. In our case we can implicitly deduce our contact area due to the nature of AABBs.

First determine if the two AABBs are overlaping at all. When an axis of least penetration is found the collision area can then be deduced.

The idea is to perform the SAT while storing each overlap value. The least overlap is your axis of separation. To get the contact area and two points of intersection you can min your maxes and max your mins (I’m talking about the extents of each AABB).

1 2 3 4 5 |
float a_extent = (abox.max.x - abox.min.x) / 2 float b_extent = (bbox.max.x - bbox.min.x) / 2 // Calculate overlap on x axis (t is translation vector from A to B) float x_overlap = a_extent + b_extent - abs( t.x ) |

This sounds silly, but that’s how you do it. I suggest drawing it out. Here’s how to find your collision area given by two points (intersection points of the AABBs):

1 2 3 4 |
c1.position.x = max( abox.min.x, bbox.min.x ) c1.position.y = max( abox.min.y, bbox.min.y ) c2.position.x = min( abox.max.x, bbox.max.x ) c2.position.y = min( abox.max.y, bbox.max.y ) |

The last bit of info required would be to record the penetration and contact normal. Penetration is your axis of least overlap, so after you’ve found your axis of least overlap you can just assign a vector value as your contact normal. If you have found the axis of least penetration to be on the x axis, you want to point towards object B along the x axis. If the y axis is the axis of least penetration, you want to point towards object B along the y axis.

1 2 3 4 5 6 7 8 9 10 11 12 |
if(x_overlap > y_overlap) { // Point towards B knowing that t points from A to B c->normal = t.x < 0 ? Vec( 1, 0 ) : Vec( -1, 0 ) c->penetration = x_overlap; } else { // Point toward B knowing that t points from A to B c->normal = t.y < 0 ? Vec( 0, 1 ) : Vec( 0, -1 ); c->penetration = y_overlap; } |

That’s all there is to the AABB to AABB intersection. Be sure to properly record the number of contacts found (if any), and if neither axis x or y are actually overlapping, then that means there is no intersection.

# AABB to Circle

I will leave AABB to Circle collision an exercise for the reader, though I will quickly provide an explanation paragraph behind the idea. What needs to be done is to first determine if the shapes are overlapping at all. I have a previous post on my blog that explains the Circle to AABB intersection, and more information about such an intersection check can be found around the internet.

Lets assume A is the AABB and Circle is B and we have a collision. The collision normal will again be the vector from A to B, except slightly modified. The early out condition involves finding the closest point on the AABB to the Circle. The collision normal is the translation vector from A to B subtracted by a vector to the closest point on the AABB. This will represent a vector from the circle’s center to the closest point.

The contact point will be residing on the circle’s radius in the direction of the contact normal. This should be easy to perform if you understood the Circle vs Circle collision detailed above. The penetration depth will be the length of the collision normal before it is normalized.

There is one special case that must be properly handled: if the center of the circle is within the AABB. This is quite simple to handle; clamp the center of the circle to the edge of the AABB along the edge closest to the circle’s center. Then flip the collision normal (so it points away from the AABB instead of to the center) and normalize it.

# OBBs and Orientation

Now lets start talking about adding in some manifold generation for some more complex oriented shapes! The first thing that must be learned is how to properly change from one orthonomormal basis to another (that is shift from one frame of reference to another). This will vastly simplify collision detection involving OBB shapes.

Changing a basis involves taking the orientation and translation of an OBB and applying the inverse of these two it to another shape. In this way you can then treat the OBB as an AABB as long as you are still referring to your transformed object. Lets go over this in some more detail with some pictures.

Here is what an OBB is like in the OBB’s frame of reference (left), and the OBB in model space (right).

The important thing to realize is that in order to place an object into an OBB’s frame of reference it must have inverse translation and rotation of the OBB’s translation and rotation applied to it. This takes the OBB’s position to the origin, and the OBB can then be treated as an AABB.

If the inverse rotation of the OBB, in this case -45 degrees, is applied to both the OBB and an object near it, this is what happens:

As you can visually see, once the circle has been inversely transformed into the OBB’s frame of reference the OBB can be viewed as a simple AABB centered at the origin. The extents of the OBB can be used to mimic an AABB, and the OBB to Circle intersection and manifold generation can be treated identically to the AABB to Circle intersection, if a proper inverse transformation is performed. Again, this inverse transformation is called a “change of basis”. It means you transform the Circle into the OBB’s frame of reference.

# Mat2 Rotation Matrices

Lets go over rotations in 2D extremely quickly. I won’t go over derivation here for brevity’s sake (as you will see, brevity is a close friend of mine in these Physics Engine articles haha). Instead I will just show you how to create your own 2 by 2 matrix and use it as apart of whatever math library you currently have (which you should hand-code yourself!). Really the only useful thing about having a 2 by 2 matrix is to do rotation operations.

For those using C++ you’re in luck for I know how to use unions.

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 |
class Mat2 { public: // Contiguous memory in various access formats union { struct { float m00, m01; float m10, m11; }; float m[2][2]; float v[4]; }; // ... }; |

The above is a proper usage of the unnamed union trick. The elements of the 2 by 2 array can be accessed as if they are a two dimensional array, single dimensional array, or separate floating point values. Additionally you can stick two vectors into your union for column or row access, if you so wish.

I want to briefly hit all the important methods without writing an entire book, so get ready for code snippets to be thrown at you.

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 |
Mat2::Mat2( ) { } Mat2::Mat2( real radians ) { real c = std::cos( radians ); real s = std::sin( radians ); m00 = c; m01 = -s; m10 = s; m11 = c; } Mat2::Mat2( real a, real b, real c, real d ) : m00( a ), m01( b ) , m10( c ), m11( d ) { } void Mat2::Set( real a, real b, real c, real d ) { m00 = a; m01 = b; m10 = c; m11 = d; } // Imagine there's assignment operators, SetIdentity, Zero, Transpose, // Inversion (which I won't cover here), Abs (absolute values all elements) // Scalar multiplication/division/addition/subtraction, determinant // negative operator, etc. Don't forget vector/matrix multiplication void Mat2::SetRotation( real radians ) { real c( std::cos( radians ) ); real s( std::sin( radians ) ); m00 = c; m01 = -s; m10 = s; m11 = c; } |

The first thing you should realize is that the default constructor does nothing. This is important. Often times you will create a matrix only to briefly thereafter assign some value to it. Do not default construct your matrix to zero values as an optimization. Force the user to use the Set function like so: mat.Set( 0, 0, 0, 0 ).

The interesting functions here are the rotation constructor and SetRotation functions. Each one computes cosine and sine from a given radian value and caches the result. Caching the results prevents unneeded additional calls to cosine and sine. Note the format in which sine and cosine are stored. It is also important to realize that m00 and m10 represent a transformation of the x axis, and m01 and m11 represent a transformation of the y axis. Each of these two are columns, both columns can be viewed as unit vectors.

Multiplying a Mat2 with a vector will rotate the vector’s x and y components around the origin. It is important to realize where your origin is before you apply a rotation. If you want to jump into an OBB’s frame of reference you must do an inverse translation to set the OBB as the origin. This allows you to then apply the OBB’s inverse rotation (perhaps with the inverse operator of your Mat2, see Box2D if you don’t know how to inverse a Mat2) and rotate about the origin (which is about the OBB).

# OBB Representation

Every oriented shape will need to store its orientation somehow. I suggest the following:

1 2 3 4 5 6 |
struct OBB { float radians; Mat2 u; // anything else needed here } |

The OBB should store its current orientation in both a single floating point value along with a matrix to represent that radian value as a rotation matrix. When you need to rotate the OBB during integration, you can just add or subtract a little bit to the radians value, and then call u.SetRotate( radians ) to update the rotation matrix. This makes use of a simple and organized way to cache results from sine and cosine calls, and minimizes the amount of calls to these functions that you require.

# OBB to OBB

Now lets talk about the *big one*. How in the world can you see if two OBBs intersect? Both boxes are oriented, so the problem would involve a lot of complex calculations involving trigonometric computations.

Lets make things easier: transform one OBB into the other OBB’s frame of reference, and treat the transformed object as an AABB. Now the problem becomes much simpler.

First perform a separating axis check and find the axis of least penetration. In order to perform the SAT you must find a projected radius onto the axis you are currently testing.

If the sums of the projected radii from both OBBs are larger than the distance between the center of each OBB (along your respective axis), then they are intersecting on that axis. This method works for all convex polygons in 2D.

The way I perform this check is by taking the translation vector from A to B, lets call it T. Then I rotate T into A’s frame of reference and subtract A’s extent vector, and subtract that entire result by B’s extent vector rotated into A’s frame of reference. This results in a vector holding the overlap along the x and y axis for object A. Due to symmetry only two axes need to be tested. The same operation can be done for object B to find B’s separating axis. If no separating axis is found the shapes are intersecting.

This is where things start to get difficult. Since we just performed an early out test, now we need to find the axis of least separation. However you cannot just blindly perform floating point comparisons due to floating point error during rotation of the translation vector from A to B. You must bias your comparisons to favor one axis over another in a consistent manner. This is important for stability!

In the above picture, which set of contact points/normal is the “correct” one? Each axis of separation is very close to the same distance, so floating point error could account for which axis is chosen. If your simulation flops between the two you’ll end up with strange jitter and your simulation will be less believable. The solution is to just favor one axis over another using an error EPSILON value.

1 2 3 4 5 6 7 8 9 10 11 |
// Compares two floats to see if a is greater than b by a slight margin of error. Small // samples from both a and b are used in the comparison to bias the result in one direction // in order to stray away from mixed results due to floating point error. inline bool BiasGreaterThan( real a, real b ) { const real k_biasRelative = 0.95f; const real k_biasAbsolute = 0.01f; // >= instead of > for NaN comparison safety return a >= b * k_biasRelative + a * k_biasAbsolute; } |

Here’s a function (you’re lucky I just gave it to you!) that will check which value is greater than the other. Each value is modified slightly, and a small bias is fed into the comparison based off of how large each value passed in is. This can be used to favor one axis of separation over another, until a threshold larger than floating point error is breached.

Carefully record which direction your normal goes (from A to B) depending on what axis is separating. This is a similar operation to the one found in AABB to AABB as seen above.

Once an axis is found two line segments must be identified: the reference face and incident face. The reference face corresponds to your normal you recorded. So the reference face is the face that corresponds to your axis of least penetration. If your axis of least penetration is on A, then your reference face is on A. The incident face is the one with the information we need to generate our manifold.

The incident face it the face on the other object that the reference face has hit. We must compute it. All that needs be done is find out which face is most facing the normal (has the most negative dot product). Looping through all faces performing dot products is the simplest way to achieve this. A more optimized algorithm is the follow the sign of the flipped normal. Your normal will have an x and y component (and z in 3D), and each component will be positive or negative. This gives you a total of four combinations of positive or negative.

First check to see if the normal is point more towards the x axis or y axis (after you transform it into the incident face’s frame of reference). Then check the sign of the y axis. You know know to which face your normal is most pointing.

Think of it this way: if the normal is pointing more towards the x axis (absolute value of n.x is greater than absolute value of n.y), then you are going to be pointing more towards either the left or right face on your OBB (in the OBB’s frame of reference). All that you need to know from there, is if you’re pointing left or right on the x axis, which is denoted by the sign of the normal.

Your incident face segment endpoints are the extents of the x axis of the OBB, which are aligned with the x axis in the OBB’s frame of reference. You can then take the OBB x half-extent and use the positive and negative version of it to form two points: (-x, 0) and (x, 0) where x is the half-extent of the OBB on its x axis. Rotate these points with the OBB’s rotation matrix, and then translate them into world space with the OBB’s position vector, and you now have your endpoints for your incident face in world space.

All that is left is the clip the incident face to the reference face side planes using Sutherland-Hodgman clipping. Here’s a diagram showing this:

This is a fairly difficult thing to do unless you know your math fairly well. Each side plane can be simply computed once you know your reference normal. Here’s the process for getting two side planes:

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 |
// Line representation in 2D is ax + by + c = 0 // a and b form the normal of the line, and c is the distance to the origin struct Line { // Must be normalized Vec n; // Vec( a, b ) real c; // Distance from origin to line }; // Create our reference face line Line referenceFace; Line posPlane, negPlane; // two side planes for reference face // Assuming our axis of least penetration was on B's Y axis // normal is the collision normal // dot product is to compute c (ax + by) referenceFace.Set( -normal, Vec2::DotProduct( b_pos, -normal ) + b_ext.x ); Vec planeNormal = bu.AxisY( ); // grab second column from Mat2 real c = Vec2::DotProduct( b_pos, planeNormal ); // ax + by posPlane.Set( planeNormal, c + b_ext.y ); negPlane.Set( -planeNormal, -c + b_ext.y ); |

The above code was hand-derived by myself, but you’ll find something very similar within Box2D Lite (where I originally learned the math from). If this is confusing to you I suggest reading up on the various types of representations of lines in 2D.

Here’s another diagram I just found in my own source files:

1 2 3 4 5 6 7 8 9 10 11 12 |
// y // ^ ->n ^ // +---+ ------posPlane-- // x < | i |\ // +---+ c-----negPlane-- // \ v // r // // r : reference face // i : incident box // c : clipped point // n : incident normal |

You might have noticed I’m storing the c value. This is important as the c value stored within the Line structure can be used to find the distance of a point to the line like so:

1 2 3 4 5 6 |
// Assuming n is normalized simplifies the equation that is // found here: http://mathworld.wolfram.com/Point-LineDistance2-Dimensional.html real Line::DistanceToLine( const Vec2& point ) const { return Vec2::DotProduct( point, n ) - c; } |

I’ll be nice and provide you my clipping notes I created for Sutherland-Hodgman clipping :)

1 2 3 4 5 6 7 8 9 10 11 |
// Sutherland-Hodgman clipping algorithm // out in out in out in out in // s | | s s | | s // \ | | / \ | | / // \ | |/ \| | / // \ | i i | / // \ | /| |\ | / // \ | / | | \ | / // e | e | | e | e // // none push i push i push e push e |

However since we are clipping a line to a single plane the algorithm will need to be slightly modified. In some cases you need to push extra points, since Sutherland-Hodgman assumes to be clipping two polygons in a loop. See Box2D Lite for a good implementation of the incident to line clipping. I however use my own hand-derived algorithm that works in a very similar way. I’ll share some pseudo code for clipping a segment to a Line, assuming the Line is in the format of offset c and a normal n:

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 |
Segment::Clip( Line line ) { // Retrieve distances from each endpoint to the line d1 = line.DistanceToLine( v1 ) d2 = line.DistanceToLine( v2 ) // If negative (behind plane) clip the point // Add in points in front of plane to output array if(d1 <= 0) outVecArray += v1 if(d2 <= 0) outVecArray += v2 // If the points are on different sides of the plane if(d1 * d2 < 0) // less than to ignore -0.0f { // Push interesection point with simple interpolation alpha = d1 / (d1 - d2) outVecArray += v1 + alpha * (v2 - v1) } } |

After clipping to the side planes floating point error must be accounted for. If our clipping process went as expected we must have two resulting points. If we end up with less than two output points that means floating point error has screwed us over, and we must treat the entire process as if the two OBBs are non-intersecting.

Assuming we have two points output from our clipping we then need to only consider points that are behind the reference face. Use the DistanceToLine function I provided above to check this. Record each point behind the reference face as a contact point!

# OBB to AABB

If you’ve been reading along diligently and deriving your own understanding, you should be able to figure out how to perform such a check. This test is the exact same as OBB to OBB, except with less rotating from one basis to another. You can recall that the OBB to OBB test rotated one OBB into the frame of the other completely, turning the test into an AABB to OBB test. The same thing can be done here without the preliminary change of basis, and perhaps some other small optimizations. I will leave the section out as a challenge for the reader.

# Conclusion

I hope you have a solid understanding of various types of hand-crafted intersection tests! Feel free to email me or comment here with questions or comments. I refer you to Box2D Lite’s source code as a reference to the material in this article, along with all of Erin Catto’s GDC slides, especially the one from 2007. The next article in this series is likely to talk about creating a simple O(N^2) broadphase, and how to cull out duplicate contact pairs. Until then this article along with the previous one is more than enough to create a simple physics engine. Be aware that with impulse resolution only one point of contact should be necessary. This article goes over grabbing multiple contact points, and this is because more advanced collision resolution techniques can make use of more contact points.

# C++ Reflection Part 4: Variant

This time around I’d like to talk about the idea of a Variant data type in C++. A Variant in C++ would be a small class that would act as a container to a variable. Since we’ve been discussing in the previous few chapters how to construct reflection for basic plain old data types, it’s possible to build off of what we already know and make something a little more interesting.

A Variant in C++ not only contains some sort of data, but it can hold any sort of data in which we register with out MetaData system. The best part about the Variant is that it isn’t a templated class, which allows us to create arrays of them (since the size of a Variant would be known at compile time). The only drawback to the Variant is that it allocates data on the heap. This can actually be avoided entirely by creating a RefVariant (more on this near the end). We’ll be able to write code like so with our Variant class:

1 2 3 4 5 6 7 8 9 10 11 12 |
Variant v; v = 1; v = 5.0; SomeStruct struct; v = struct; const char *c = "Look, I'm a string!\n" v = c; |

As you might be imagining at this point, a Variant data type would can be pretty handy in writing generic code! And indeed this would be correct. The Variant data type is integral for many interesting applications of our MetaData system that I’ll be writing about in the future.

To get started lets look at a skeleton of what what the Variant’s core will be looking like:

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 |
class Variant { public: template <typename T> Variant( const T& value ); template <typename T> T& GetValue( void ); template <typename T> const T& GetValue( void ) const; template <typename TYPE> Variant& operator=( const TYPE& rhs ); private: const MetaData *meta; void *data; }; |

This should make a fair amount of sense if you’ve been reading along in the previous articles on reflection so far. All we really need in order to contain some sort of data is a void pointer to that data, and a MetaData instance that describes the data within the void pointer. All is well!

So now all that’s needed is a generic way of constructing objects we have registered within our MetaData system. In this article we’ll be only covering plain old data types, although it’s really easy to add support for arbitrary types with constructors (which I may cover in a future article).

Since our Variant is storing a void pointer it only makes sense to manipulate the void pointer when constructing some data to store within it. memcpy, along with array new and delete will be our friends! Using byte arrays of characters we can very easily create and store character arrays of arbitrary length and data type. Here’s a couple small functions we’ll be using shortly…

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 |
void MetaData::Copy( void *dest, const void *src ) const { memcpy( dest, src, size ); } void MetaData::Delete( void *data ) const { delete[] reinterpret_cast<char *>(data); data = NULL; } void *MetaData::NewCopy( const void *src ) const { void *data = new char[size]; memcpy( data, src, size ); return data; } void *MetaData::New( void ) const { return new char[size]; } |

Since our MetaData instances know about the size of data they represent it’s pretty trivial to use memcpy to allocate and manipulate byte arrays. These should go inside of the MetaData class definition so that we can write code like the following:

1 2 3 4 5 |
// Copy an integer into allocated heap space META_TYPE( int )->NewCopy( &someInt ); // Or a generic representation: META_TYPE( TYPE )->NewCopy( &someVariable ); |

And that’s that! Surprisingly easy. These functions are very useful to use as helper functions for writing the Variant class definition. Before talking about the constructor and assignment operator of the Variant, I’d like to discuss very quickly the GetValue method. The GetValue method is templated so that the user can request the actual value from within the Variant, and do with it what they please. Here’s an example of how it’s intended to be used:

1 2 3 4 5 |
Variant v; v = 17; // The value inside of v is now 23 v.GetValue<int>( ) = 23; |

As you can see, the type passed in as the template parameter is being used somehow to interpret our void pointer as a concrete type. Since C and C++ like pointer typecasting much more than typecasting of actual memory references, we can use pointer typecasting to implement GetValue as a nice wrapper around reinterpret cast, and return a reference from our cast so our GetValue function really returns the value of our data, and not its address:

1 2 3 4 5 6 7 8 9 10 11 |
template <typename T> T& Variant::GetValue( void ) { return *reinterpret_cast<T *>(data); } template <typename T> const T& Variant::GetValue( void ) const { return *reinterpret_cast<T *>(data); } |

Pretty simple as well! Actually, everything about making the Variant is pretty straightforward since the heavy lifting of creating the MetaData instances has already been accomplished.

Last but not least is to tackle the constructor and assignment operator. Lets do the constructor first since it’s only one line of code:

1 2 3 4 5 |
template <typename T> Variant::Variant( const T& value ) : meta( META_TYPE( T ) ), data( NULL ) { data = meta->NewCopy( value ); } |

There’s not much to explain here. We use our nifty META_TYPE macro and NewCopy helper function to all of the work. META_TYPE grabs the MetaData instance that corresponds to our templated type T (which is retrieved from the type of value being passed to the constructor).

The assignment operator is a little more tricky, and this is because you have to check and see if your current MetaData matches with the type you’re assigning to or not, in order to possibly avoid reallocating a new buffer for no reason.

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 |
template <typename TYPE> Variant& Variant::operator=( const TYPE& rhs ) { // We require a new copy if meta does not match! if(meta != META_TYPE( TYPE )) { assert( META_TYPE( TYPE ) ); // Cannot create instance of NULL meta! meta->Delete( data ); meta = META_TYPE( TYPE ); data = meta->NewCopy( &rhs ); } else { meta->Copy( data, &rhs ); } return *this; } |

As a possible optimization one could actually avoid creating a new buffer if the size of the incoming type is less than the size currently held by the Variant.

And this concludes all the explanations for how to create a Variant class I have! One last thing is to talk about the idea of a RefVariant. A RefVariant would act just like a Variant, except it would only store and handle a pointer to some data, rather than containing a char buffer allocated on the heap. This is especially useful, as now references to memory can be represented by the MetaData system, without having to actually allocate any memory on the heap. RefVariants in a sense are the “shallow copy” form of a Variant.

Some more useful methods to implement would include assignment to another Variant (or RefVariant), and a copy constructor.

Here’s a link to a working example showing my RefVariant example in action.

# Batch Files: Tips and Tricks

I spent a lot of time one weekend creating a utility I call AutoGCC. GCC is a compiler that comes with Cygwin for Windows. When running this compiler and finishing assignments there are a whole lot of very annoying commands and actions to complete, that are highly repetitive. Perfect situation for constructing a utility! Here is a link to the program, which I update as I find bugs or think of additional features: http://www.mediafire.com/?v3q5f4ntvceq4wa

There are a few tips and tricks I learned about batch programming that I’d like to share, and to document for my own future reference.

You can use parentheses to link multiple lines so they are treated as a single line. This allows you to make nicely formatted if statements, like so:

`if not exist %CD%\error_files\ (`

mkdir %CD%\error_files\

)

The next trick that took me forever to understand the syntax of, is string manipulation. Take the variable %PATH% for example. It is a string. However what if I want to modify a portion of this string to my own liking? Look at the following: %PATH:;c:\AutoGCC=%

`%PATH:;c:\folder=%`

That code actually searches for a matching sequence of characters of the sequence “;c:\folder“, and will set that portion of the string %PATH% to nothing. This is basically deleting an element from the %PATH% variable. You could also have done:

`%PATH:;c:\folder=;c:\LOL%`

Which would change the element ;c:\folder to ;c:\LOL.

There is also a nice way to edit the path (or any registry key) of a user’s machine by editing the registry key for the system path! This will however require a restart to take effect. Here is the syntax I used in AutoGCC to modify my system’s path (type reg add /? for information on the reg add command):

`reg add "HKLM\SYSTEM\CurrentControlSet\Control\Session Manager\Environment" /v Path /t REG_EXPAND_SZ /d "%PATH:;c:\AutoGCC=%" /f`

You can also use the CALL command to launch a specific portion of your code as if it were its own batch file. This is really useful for making functions within your batch file. Take a look at the following code:

`if exist %file% (`

` if %var% NEQ 2 (`

` call FUNCTION_1`

` )`

`)`

`:FUNCTION_1`

` do stuff...`

` ...`

…

goto EOF

The above code will go to the line labeled with FUNCTION_1 if %file% exists, and then return just below the goto FUNCTION_1 statement once the line goto EOF is reached. goto EOF sends the control to the end of the file, though since FUNCTION_1 was called by a call command, it is as if it is an emulated batch script of its own, and the emulation will close, not the original environment that called it.

These few things are extremely useful for me when working on my batch scripts, and hopefully will be for you as well!

# TL Secret

First person to quote this sentence (back on TL at the Lessons thread), and the one directly after it, will win a free one hour lesson! Additionally whoever is the 100th poster in this thread (cmon, we can get that many posts!) will win a free one hour lesson as well!

Edit: This contest is long over :P

# Linear Algebra: Rotation Matrices

A day or so ago I looked up the topic of using rotation matrices to modify the angle of a vector by an arbitrary amount. I visited none other than the WikiPedia page for rotation matrices.

The idea behind rotation matrices is to solve for the x and y coordinates after the rotation by using two separate equations. Here is a rotation matrix for 2 dimensions:

That matrix will rotate the 2D plane counterclockwise by angle *θ*. Using this knowledge, the new x and y coordinates for a point on a rotated vector would be solved for using these two equations:

Very simple! So here is an example problem: Say you have vector __AB__. * AB *= (2, 3).

*To solve for a rotated counterclockwise version of this vector you input your desired angle of rotation in for θ, 2 for x and 3 for y. This rotation matrix rotates a 2D plane clockwise:*

*Rotation in 3 dimensions is basically the same process. All that is different is the z coordinate and modified rotation matrices. You simply solve for each individual coordinate with the rotation matrices for the z, x, and y axis. These three rotation matrices and more are found at the WikiPedia page for rotation matrices.*

# Linear Algebra: Basics

Today with my math teacher I went over some of the basics of linear algebra. The two topics I went over included solving for the intersection of two lines in 3D space, and finding the angle between two vectors. The rest of the mathematical topics I’ll try to cover in the near future include: finding a vector orthogonal to two other vectors in 3D space; finding the time T during the intersection of ray between a circle of sphere; using a matrix to rotate a vector by an arbitrary angle. I found these topics, as well as an entire survival guide for DigiPen students, at this site here. Hopefully by explaining the math I went over today I can solidify my own understanding.

First off: solving for the intersection of two lines in 3D space. I know how to do this in matrix form, as it is easiest and simplest in matrix form. Here is a matrix of the x y and z coordinates for a point in 3D space: [x, y, z]. An equation for a vector in 3D space consists of a point on a line, and the direction vector of a line multiplied by a magnitude. This magnitude represents the length of the line, whereas the timestep, or t, represents a constant.

Here is an equation for a line in 3D space: L1 = [2, 4, -1] + t[-1, 2, 3]. I just chose these numbers at random because they really don’t matter. The first matrix is a point on the line. The second matrix is the rise, run, and the z equivalent to rise or run (just like two dimensional lines). You need a point on the line, otherwise the direction vector (rise//run//zrun) could sit anywhere in space. Without the direction vector for your line, you line could be facing in any direction as long as it sits on your point. The t is the magnitude of the direction vector, and these could be used as something to define the distance something traveled over time of t. t is just a constant.

In order to solve for the intersection of two lines, I’ll quickly show the process with some variables. Here are the two lines: L1 = [a, b, c] + t[d, e, f]; L2 = [g, h, i] + r[j, k, l]. Now since these two equations each represent a line, the point of intersection is going to be a point that can be used to satisfy either of the equations. You just set both of the equations equal to each other, one variable at a time (x, y and z) and solve for each one. To solve for the x coordinate of the intersection you would use a + td = g + rj. You do this for variable a through c corresponding to d through f. Then using substitution, if need be, you can solve for t and then solve for the rest of the variables, thus getting a final matrix of [x, y, z].

The second thing I learned today was finding the angle between two vectors. Luckily, you only need the direction vectors of the line equations. This makes sense because no matter where the lines are in space, they will have the same angle of intersection as long as the direction of the lines face in stays constant. To do this, you use the equation of:

Theta, the zero thingy on the left, is the angle you are solving for. a and b both represent matrices that represent direction vectors, like the direction vectors in the line equations earlier in this post. Arccos is cos^-1. The a and b on the top half of the right side of the equation is pronounced as a dot b. The dot is the operator for the dot product. The dot product is used to find the scalar projection of a onto b, and vise versa. I honestly don’t fully understand what exactly the dot product does yet (read last paragraph, I understand it now), but for now I just need it for equations like this one, and it returns a scalar value. To use the dot product on two 1×3 matrices, you would do this: [a, b, c] dot [d, e, f] = ((a x d) + (b x e) + (c x f). The |a| represents the magnitude of a, which is the length of a. If the direction vector of a line is representing velocity vectors, then the magnitude of a would be the speed of the direction vector. To find the magnitude of a 1×3 matrix you do this: |M| = |[a, b, c]| = sqrt(a^(2) + b^(2) + c^(2)). Does that look familiar? It should; it’s basically the Pythagorean Theorem in 3D. It takes the rise, run, and zrun and converts the three into a length value, just like the Pythagorean Theorem does with two lines, except this is with three.

Now once you find a dot b, and magnitude of a times magnitude of b, you then divide a dot by magnitude of a times magnitude of b, then arccos that value which results in your angle!

Dot product explained: Okay! I so I did a bit of research and asked a couple people some questions and now I understand what the value returned by the dot product does. It projects a vector onto another vector and returns the length. A dot B also equals B dot A, which makes sense because multiplication itself is commutative, and the formula for the dot product is just multiplication of three values. Here is a picture to help visualize this:

The blue line would be the dot product of A and B. This is very useful for collision in programming, and transforming vectors from one grid space to another. Here is a good example of using the dot product for 2D collision detection of convex polygons:

The red and blue are both one dimensional projections of the objects onto a line. The dotted line is perpendicular one side length of one of the objects. In the diagram is looks like it is perpendicular to both, which is fine, but it is important to understand that the dotted line is normal to one of the sides of one of the polygons. Once you find a dotted line that is perpendicular to a side of one of the shapes, you use the dot product on a two dimensional matrix and project both of the shapes onto the normal to the dotted line. You can then compare the two projections to see if they overlap. If the two projections overlap, you then try the entire process over for a different side of one of the polygons. Once you try this algorithm over each of the sides of each object and no collision vector was detected (a collision vector would be the length of overlap formed by overlapping projections) in at least one of the iterations, then the two objects are not colliding with one another.

Sources:

http://www.mvps.org/directx/articles/math/dot/index.htm

http://en.wikipedia.org/wiki/Dot_product

http://www.gamedev.net/reference/programming/features/verletPhys/page2.asp

# Decided to keep a blog.

A friend of mine mentioned to me today that I should keep a blog of my journeys on becoming a video game programmer; I have been accepted to my top choice college: DigiPen! I’m ridiculously excited to start school there next August! I’ll be starting in a Bachelor’s Degree of CS in Real Time Interactive Simulation (RTIS). Here is a link to DigiPen’s site: https://www.digipen.edu/

**Classes(1)**. I’ve learned to use variables, constants, basic input/output via cin and cout, control structures (like for and while loops, if and else statements) , arrays, pointers, dynamic memory, and data structures.

```
```

```
```

#include

using namespace std;
int subtraction (int a)

{

int r;

r = a*5;

return (r);

}

int main ()

{

int x, y, z;

y = 5;

loop:

cout << "Enter a number into the secret equation." << '\n';

cin >> x;

cout << "Now I will modify the number you entered; it is now:" << '\n';

cin.get();

cout << subtraction (x) << " - Press enter to continue" << '\n';

cin.get();

cout << "Can you guess by what number I multiplied yours by?" << '\n';

cin >> z;

while (z != 5)

{

cout << "You guessed the wrong number!" << '\n';

goto loop;

}

return 0;

}

```
```

```
```

```
```

#include

#include

#include

using namespace std;
struct animals_t {

string danger;

string size;

}dog, mouse, alligator;

void printdetails (animals_t details)

{

cout << details.danger << '\n';

cout << "And this large: ";

cout << details.size;

}

int main ()

{

string input;

cout << "How large is a dog!? ";

getline (cin,dog.size);

cout << "How dangerous is a dog!? ";

getline (cin,dog.danger);

cout << "How large is a mouse!? ";

getline (cin,mouse.size);

cout << "How dangerous is a mouse!? ";

getline (cin,mouse.danger);

cout << "How large is an alligator!? ";

getline (cin,alligator.size);

cout << "How dangerous is an alligator!? ";

getline (cin,alligator.danger);

cout << '\n';

cout << "A dog is this dangerous: ";

printdetails (dog);

cout << '\n' << '\n';

cout << "A mouse is this dangerous: ";

printdetails (mouse);

cout << '\n' << '\n';

cout << "An alligator is this dangerous: ";

printdetails (alligator);

cout << '\n' << '\n';

cin.get();

return 0;

}

```
```