Author Archives: Randy Gaul

Transformations: Change of Basis Matrix

When dealing with tensors and having to transform them from one basis to another the formula to do so isn’t all that intuitive, especially when 3D programmers are used to transformation concatenations.

I’m sure any reader familiar with 3D would understand that two transformation matrices can be combined to make a new one with the same effect as the first two. This can look like so:

\begin{equation}
A * B = C
\label{eq1}
\end{equation}

In the above equation the transformations present (A B and C) would be used to transform a single vector. It should noted that this article refers to vectors as points (or more clearly vectors translating the origin). In column major format this would mean that the a given transformation would transform the column of a single vector. Given a matrix A and a vector V, to transform V into V’ the following equation would be used:

\begin{equation}
A * V = V’
\label{eq2}
\end{equation}

Similarly, if V needs to be transformed into the frame of A (which is different than being transformed by the frame of A), the following equation can be used:

\begin{equation}
A^{-1} * V = V’
\label{eq3}
\end{equation}

Say a programmer needs to take a transformation matrix and see what this would look like within another coordinate frame. An example of this would be the need to rotate a rotation matrix, or perhaps transform an intertia tensor from local to world frame. In order to apply a change of basis upon a matrix the following equation must be used, where B is called the change of basis matrix:

\begin{equation}
A’ = B * A * B^{-1}
\label{eq4}
\end{equation}

A Euclidean vector can be thought of as a linear combination of the Euclidean basis. Given a vector v:

\begin{equation}
V = \begin{bmatrix} x \\ y \\ z \end{bmatrix}
\label{eq5}
\end{equation}

And Euclidean basis as a formation of three principal vector axes scaled by scaling factors i, j and k:

\begin{equation}
E^{3} = i\begin{bmatrix} 1 \\ 0 \\ 0 \end{bmatrix}, j\begin{bmatrix} 0 \\ 1 \\ 0 \end{bmatrix}, k\begin{bmatrix} 0 \\ 0 \\ 1 \end{bmatrix}
\label{eq6}
\end{equation}

The vector V can be written as a linear combination of E^3 by replacing the i, j and k components with V’s x, y and z components:

\begin{equation}
V = x\begin{bmatrix} 1 \\ 0 \\ 0 \end{bmatrix}, y\begin{bmatrix} 0 \\ 1 \\ 0 \end{bmatrix}, z\begin{bmatrix} 0 \\ 0 \\ 1 \end{bmatrix}
\label{eq7}
\end{equation}

Following this line of thinking, a 3×3 matrix for some arbitrary rotational transformation actually contains an orthonormal basis of three principal axes. The first column represents the x axis, the second column represents the y axis, and the third column represents the z axis of a given reference frame. Any vector in E^3 can be described by a different combination of i, j and k values in any new basis. Wikipedia actually has a beautiful picture to visualize a vector within two different bases simultaneously:

Here is a simple example of showing V as a combination of the columns of some arbitrary basis matrix:

\begin{equation}
V = x\begin{bmatrix} a \\ b \\ c \end{bmatrix}, y\begin{bmatrix} d \\ e \\ f \end{bmatrix}, z\begin{bmatrix} g \\ h \\ i \end{bmatrix}
\label{eq8}
\end{equation}

Now back to equation \eqref{eq4}, in order to rotate a rotation it might be good to clearly define what this means. This means: given a rotation A it is desired to apply this rotation within the reference frame of B.

Say we have a rotation A that rotates about the x axis by θ. We would like to tilt A slightly, which would tilt the x axis slightly, and apply a rotation of θ about the new slightly tilted axis. The tilt rotation itself is given by B.

Just multiplying A by B, or B by A does not solve this problem. Multiplying A by B would translate to “rotate around the x axis, and then tilt a little bit”. Multiplying B by A would translate to: “Tilt a little bit, then spin around the x axis”. Neither of these are properly translating to “Rotating around the tilted x axis”. Here’s the translation of equation \eqref{eq4}: “Tilt the tilted axis so that it lays upon the x axis, then rotate about the x axis, and tilt once again”. This translation can also be stated in a slightly more formal manner: “Tilt A by inverse B (which aligns A’s x axis into the frame of B), rotate around B’s x axis, and tilt A back into it’s original frame”.

All that equation \eqref{eq4} is doing is transforming basis vectors of A into B’s frame, applying A, and transforming A back into A’s original reference frame. This matches the original clarified problem of “Given a rotation A it is desired to apply this rotation within the reference frame of B”. In more loose terms, this also means to rotate the rotation A by B.

Reference: GDC 2014 Slides – Math for Game Programmers – Understanding 3D Rotations by Stan Melax

Geometric Duality Transformation

cubedual

One topic I’ve found to be extremely interesting is the idea of dual space in terms of a polyhedron. After recently being introduced to Fourier transforms (thanks Professor Morhmann!) and image processing I’ve been thinking about dual space in the same sort of light: as a mathematical transformation. I’d like to take a moment to thank Dirk Gregorius for first introducing me to the idea of Dual space, and sharing some of his thoughts on the subject.

Transformations that map from domain to range are generally used to simplify problems. In computational geometry many problems are numerically challenging to solve in standard Euclidean space. Edge cases and code complexity rise in order to handle numerical and geometric robustness issues.

By taking a polyhedron into Dual Space a new perspective is gained and some problems may become much simpler to solve. Hopefully this short article can be of use to someone by describing a particular type of dual transformation. For this article Euclidean space is denoted by E, and dual space is denoted by D. Given a 3D point P in E, the transformation to dual space is:

\begin{equation}
P = \left\{\begin{matrix}a&b&c\end{matrix}\right\}\in E \\
D( P ) = ax + by + cz = 1
\label{eq1}
\end{equation}

In this way a point in E becomes a plane in D. In this way the Dual plane of point P becomes farther from the origin in D the closer P is to the origin in E. The units in Dual Space are of inverse units in Euclidean space.

Similarly a plane L in E transformed to a point in D is denoted by the following:

\begin{equation}
L = ax + by + cz \in E \\
D( L ) = \left\{\begin{matrix}\frac{a}{d}&\frac{b}{d}&\frac{c}{d}\end{matrix}\right\} = 1
\label{eq2}
\end{equation}

In this way a point in E maps to a plain in D, and the farther away from the origin the point is the closer to the origin the plane is.

This Dual transformation is interesting due to the isomorphism present. The Dual of E is indeed D, and the Dual of D returns back the original E. This allows data to be transformed to Dual space and back again, allowing algorithms to be performed within the intermediary Dual space.

This particular transformation can be see in Ericson’s Real-Time Collision Detection, as well as a white paper on the topic of CD-Dual.

One popular example of utilizing a type of dual transformation (not necessarily this exact transformation) is the open source project HACD by Khaled Mamou. In his project half-edge collapse operations are performed upon the Dual of a mesh, all the while minimizing a tunable cost function. There are more applications that may benefit from the perspective of Dual space, and I hope this article can bring this idea some more awareness.

If anyone reading this article knows of any other interesting applications of the geometric dual, please to do comment!

Preview image from: http://www.math.rutgers.edu/~erowland/polyhedra-project.html

thatgamecompany Internship!

ThatGameCompany_Logo

Recently inspired by my colleague Allen’s interesting blog post about his hiring experience I’ve decided to follow suit and share my own experience on acquiring an internship the year before graduation!

I’m sure most anyone reading my blog knows of a company called thatgamecompany. I have recently been offered a summer internship! The company is an amazing one and I personally feel that I belong at such a place. I’ll see how good of a fit we make in the coming months, though I remain extremely optimistic about the whole thing.

Smaller game companies seem to work like a mini-Valve in that the team structure is flat. When speaking with thatgamecompany’s lead engineer John and researching the company I was drawn towards the way that John detailed about the internals of company working. One thing that stuck out to me most was that John had mentioned that often times a developer will get an idea, experiment and try it out and see how things go. If a good idea is placed into the game other employees will recognize this and “hop on the bandwagon” to work together to get to the next iteration. John had mentioned that he feels a good fit for a team structure like this are individuals with a lot of initiative. I myself strive for an environment that embraces initiative, experimentation and professional growth.

They even sent me one of their AWESOME T-Shirts! Special thanks to a particular someone’s mom :)

2014-03-10 18.13.19

So I’ve been struttin round with my snazzy shirt for weeks ever since I was made an offer. I think it would be fun to describe how I actually met John Edwards, one of the founders, in an effort to perhaps inspire others to do similar.

In my early studies at DigiPen I was hungry to find all resources that exist on the C++ topic of code reflection. thatgamecompany’s lead engineer John Edwards had made some sample material available to students at my university a few years earlier, and at the end of his material he left his email in case anyone wanted to contact him.

Happy to have found the exact reference material I needed I implemented all that was presented, and then added a whole lot more atop. After feeling great about the results I emailed John thanking him for his contribution of knowledge and linked him to one of my portfolio videos. I do this with most people that give out GDC lectures or other types of online-material, as I know from experience that seeing others’ work benefit from your own material grants a very rewarding feeling -like a sense altruism satiated.

John ended up liking my video and asked me to shoot him an email next year if I was interested in interning at thatgamecompany. At first (as a Sophomore) my mind wasn’t on internships or hiring in any way, and I was really just lucky I sent him an email at all.

The interview process was actually super long spanning a couple months. Albeit Christmas did strike through the middle of the process, it was still long. The usual is programming tests, phone interviews followed by some form of in-person meetup and additional interviews; interviewing with thatgamecompany mostly followed this format. In general (not specific to thatgamecompany) knowing 3D math to point where it feels like a language in and of itself, and proficiency in C++ seem to be pretty much the only requirements to make oneself appealing as a potential hire (as for as tech skill goes for engineers). If anyone wants tips on how to practice for interviewing my advice would be to make sure you’re proficient in your area of study. Beyond this I find that practicing writing code on a white-board helps for formal coding interviews, practicing with a mock-interviewer. For me personally the biggest practice was just repetition of mock coding interviews to keep me from being nervous. When I’m nervous my mind can go pretty blank.

Another thing thatgamecompany was very interested in learning about was how I handle myself in team situations. I actually appreciated the care they took to find out who I am and how I work with other people. So if I did have any advice that might be of help to anyone, it would be to not underestimate the value of working on a larger project with other people in order to ship a product. I feel that I’m quite lucky to have a few small school/team projects finished and released, and would advise others seeking entry level positions to do the same if possible.

Hopefully my luck will last out a little longer as I proceed towards graduation!

In this I would say the moral of the story is: people that write or put forth educational content always do so with an interest to teach others. If one is genuinely interested in the content and contacts the original authors with a thank you, they will inevitably be interested, especially if intelligent followup questions are asked. I would suppose that seeing others benefit and take interest in your efforts to help is just irresistible. It’s a great way to thank wonderful people and educate yourself at the same time. I’ve done this with dozens of various authors of all sorts of content, and every single one of them has always responded very generously; I’m very thankful to them all for their willingness to help.

Buoyancy, Rigid Bodies and Water Surface

Picture1

I’ve spent the last couple weeks researching eigenvalue decomposition and solving cubic polynomials in order to simulate a liquid surface and polyhedral buoyancy! I gave a lecture about this topic at my university and hope the slides can be of interest or help to someone. I’ve attached a couple demo GIFs to the bottom of this post.

Download (PDF, Unknown)

WavesFinal

Waves

Code Sample: Gaussian Elimination

In my current portfolio project I came across the need for an implementation of Gaussian Elimination to solve a system of equations in C++. I’ve decided to open source the code and use it for a code sample as a portfolio piece. Here is an entire working program:

And here is the current output of the program:

 

Dynamically Slicing Shapes

Just this morning I finished up a small open source project, along with a huge article at gamedev.tutsplus. The open source project is an implementation of Sutherland-Hodgman clipping which can be used in many advanced shape and mesh manipulation techniques.

PolygonSplitting

Gif of the open source project in action. Slicing a quad interactively.

 

Simple and Efficient Singleton Pattern

For game engines the singleton pattern is pretty commonly used for various global accesses, like for the core engine or for specific systems. Often times things like texture managers, the graphics implementation or a physical simulator are represented as singular entity that can be accessed globally.

A singleton pattern can be used to help facilitate and assert the existence of only one of these systems at any given time. This is important for a lot of code that is created under the assumption that only one given instance will be alive at once.

Advantages of Singletons

The biggest reason singletons are used is for code clarity. Any programmer that realizes something is a singleton is instantly informed of how it should be used. Beyond conceptual aids a singleton can also be an efficient means of allowing global access of an object. Often times in games everything is owned by something, otherwise referred to as the “Ownership Pattern”.

If a game consists purely of things owning other things (except for the core Game or Engine object), retrieving different systems from global access might be hard. This is because the Engine would be the only global thing. Code like this:

is long and annoying and also inefficient; there are many unnecessary levels of indirection. Instead a singleton can be used to solve such a problem.

A Traditional Approach

The traditional approach to creating a singleton is to utilize some code like so:

This approach does in fact ensure that only a single instance of a given class is alive at any given time, and can be especially effective if the constructor and destructor are declared in the private section.

Drawbacks

There is a pretty big drawback to this traditional style: construction and destruction order. C++ makes no guarantee about the construction and destruction order of objects on global (file) scope. This means that the code run for each destructor of every singleton instance (despite construction time) can run in any order.

This poses a huge problem for systems that depend on one another. What if the TextureManager class contained a pointer to the Graphics class? What if the destructor of the TextureManager tries to access the Graphics pointer and the Graphics singleton has already destructed?

Such an issue does have workaround solutions, but it might be best to have some form of singleton that controls construction and destruction explicitly.

A Better Singleton

Here’s a simple way to implement a singleton and allow explicit construction and destruction:

This singleton is actually quite safe due to the simple assertion in the constructor. The nice thing about this assertion is that it can be compiled away during release builds. This might be considered an advantage against the traditional approach, as the traditional approach will often times have a boolean flag to test for previous construction (in the assembly of the compiled C++).

Since it is a slight inconvenience to add the instance handling to every class you wish to be a single the use of a template mixin can help. Making such a utility can be tricky due to multiple inheritance. I will leave solving the multiple inheritance issue as an exercise for the reader.

I myself use this sort of singleton (I don’t even have a utility) and enjoy it. I actually don’t even use a Get function but just have a global extern’d pointer in my header.

I’ve also seen this exact implementation in a few areas, one of which is in an article by Scott Bilas in the first Game Programming Gems book (he covers the multiple inheritance issue),

Setting up wxWidgets

wxWidgets is a nice cross-platform GUI library for C++. I know quite a few colleagues that used it for creation of various editors and applications. One of them is Sean Reilly, who wrote a really useful series of steps to follow in order to setup your wxWidgets project. Here are his steps:

Hopefully this is helpful to someone!