Tuesday, June 28, 2011

Back to the SHMUP?

Well, I am finally through the prereqs section of the graph theory book.  Although I didn't do the final problem set, I should have a good enough grasp on the subjects to make use of them.

I am currently considering using kinematics for animation in the SHMUP rather than dynamics, which would allow me to temporarily skip most of this math.  Kinematics is basically hard-coded movement, where dynamics is more physics-based.  Gamers know these as arcade games and simulation games respectively.

We are also redesigning the SHMUP so that it will be easier to create.  This means that I shouldn't have to make many test projects, and I can jump right back in to coding the "real" game.

Friday, June 17, 2011

Mathematical functions

A function is similar to a relation.  It is a set of ordered pairs (a, b) where a is an element of some set A and b is an element of some set B.  For each element in A, there is exactly one ordered pair with that element in the first position.  Given such a function f, we say that it is a function from A to B, which is written f:A->B.  We could also say that f:A->B is a mapping from A to B, in which case we would say that f maps from A into B.  This is written b = f(a), similar to how a relation is written aRba is mapped into b by f, and we say that b is the image of a under f.

Something worth noting is that because there is exactly one ordered pair per element in A, there is exactly one image of each element in A under f.  In other words, an element of A has exactly one image, no more, no less.  However, multiple elements of A can share the same image.  If each image is the image of only a single element of A, we say that f is one-to-one.  If all the elements of B are images of elements in A under f, we say that the function f maps from A onto B, rather than "into".

A composition of two functions f:A->B and g:B->C is the function fog:A->C which maps from A into C.  Such a function is written c = g(f(a)) where a is an element of A and c is an element of C.  This works exactly how you think it would: First b = f(a) is calculated, and the resulting element b is fed into g.

And lastly we have something called a "permutation".  A permutation is a function f:A->A where A is not the empty set and f is both one-to-one and maps from A onto A.  What you end up with is a function which rearranges the elements in A.

Thursday, June 16, 2011

Equivalence relations

Today I learned about equivalence relations, equivalence classes, partitions, divides, and congruent to modulo n.

An equivalence relation is a relation that is reflexive, symmetric, and transitive.  Pretty straight forward.

An equivalence class (also known as an equivalence set) is denoted [a] = {x | x is an element of A, x R a}.  In other words, it is the set [a] consisting of all the elements of the set A which are related to a by the equivalence relation R.  To look at it in a slightly different way, [a] is the set of all elements in A which are related to a.  For example, if the relation is "has the same PvP score as" and A is the set of all the people in your gaming community and a is someone in that community (lets say it is you), then [a] would be the set of everyone in your gaming community who has the same PvP score as you do.

A partition is a set of sets.  So for example, S = {A1, A2, ..., An} where Ai is some set for 1 <= i <= n.  A partition has a few requirements for that set of sets though.  Each Ai is a subset of a single set A.  Also, every pair of distinct subsets (I will get to what "distinct" means shortly) is disjoint, meaning their intersection is the empty set (there are no overlapping elements between subsets).  And finally, the union of all Ai must be the set A.  This is kind of like partitioning a harddrive or separating the screen in a Tetris-like game into chunks for the various shapes and the empty space.

There is another noteworthy "set of sets": the equivalence classes.  You can actually make a set out of all the possible equivalence classes for a particular (nonempty) set and equivalence relation: S = {[a] | a is an element of A}  This is noteworthy because it turns out that the set of equivalence classes S is a partition of the set A.  However, if you are like me this can get confusing when you realize that two or more of the equivalence classes in the set can be equal.  For example, if A={1, 2, 3, 4} and the relation is setup so that [1] = {1, 3} and [3] = {1, 3}.  But isn't one of the requirements for a partition that all pairs of sets be disjoint?  How are {1, 3} and {1, 3} disjoint?  Well, the key bit of information I was missing is this: Only distinct sets count.  Two sets are distinct if they are not equal.  This makes sense, since you can have a set A = {a, b, a, c} but all of the a's are treated as the same element.

Lets define the set Z to be the set of all integers.  Given two variables d and m which are both elements of Z (they are both integers) and where d does not equal 0, if there is a variable q which is also an element of Z such that m = dq then you could say that d divides m, or in more "mathy" terms: d|m.  Note that q must be an element of Z, so in other words an integer.  If the division has a remainder, then q doesn't exist in Z and d does not divide m.

Lets look at d|m again, but this time using three variables instead of two: n, a, and b which are all elements of Z.  If you arrange these so that it reads "n divides the difference between a and b", in other words n|(a - b), you can also say that "a is congruent to b modulo n".  I don't have access to the exact symbols, but the mathematical way to write it is something like this: a congruent b(mod n).

Using congruent modulo n you get an interesting set called "integers modulo n", written Zn or Z/(n).  It is the set of distinct equivalence classes from the relation "is congruent modulo n" on the set of integers Z where n >= 2.  I stopped studying today about half-way through a problem which was designed to show uses for this set, so I'm not really sure how you could put it to use.  Based on the name however (and after seeing what a few of the equivalence classes are for a couple values of n), I'm going to guess that it can be used in division, possibly as a lookup table or for something related to remainders.  I'm sure I'll find out later!

Wednesday, June 15, 2011

GDC Vault and Relations

Apparently you can get a lot of the GDC presentations for free at the GDC Vault website.  It doesn't have everything unfortunately (I couldn't find Erin Catto's 2006 presentation), but there are some cool things in there.  I didn't have much time to browse around, but the Halo: Reach networking presentation caught my eye; it's rather good, and I recommend it to anyone who is writing networking code.

Today I learned about relations and Cartesian products.  The Cartesian product of two sets A and B is the set consisting of all the ordered pairs (a, b) where a is an element of A and b is an element of B.

A relation of a set V is any subset of the Cartesian product of V with itself.  Given an ordered pair (a, b) of a relation R, a is said to related to b by R.

Relations can have several properties: reflexive, irreflexive, symmetric, asymmetric, and transitive.  A relation R on V is reflexive if for every x in V there is an element (x, x) in R; it is irreflexive if for every x in V there is no element (x, x) in R.  A relation R is symmetric if for every element (a, b), there is another element (b, a); it is asymmetric if for every element (a, b) where b is not a, there is no element (b, a).  And finally, a relation R is transitive if for every element (a, b) there is an element (b, c) and (a, c).

I also learned that the cardinality of a set is the number of elements in that set.

Tuesday, June 14, 2011

De Morgan's Laws

I spent most of the morning creating a forum post asking for people's  opinions of Chris Hecker's physics references list.  I posted it on four  forums: The Bullet Physics Simulation Forum, GameDev.net, TIGSource, and Physics Forums.   It's been interesting to see how active the various forums are.  Bullet  and Physics Forums are about equal at 32 views and 33 views with 0  replies.  GameDev.net appears to be the least active at 0 views and 0  replies, although I suspect that this may have something to do with  differences in the counting systems used.  TIGSource is definitely the  most active at 181 views and 12 replies.

When I had time to study math, I finished off the section on sets.  I  learned what a universal set is (the set which all the currently  discussed sets are subsets of), as well as what the complement of a set  is (it is the set of all elements in the universal set except the  elements belonging to the set being operated on). I also learned about  De Morgan's laws in relation to set theory, including how to prove  them.  The first law states that the complement of the union of two sets  A and B is equal to the intersection of the complements of the two sets  A and B.  The second law states that the complement of the intersection  of two sets A and B is equal to the union of the complements of the two  sets A and B.  One of the problems in the problem set was proving De  Morgan's second law.  It took me about an hour to figure out, but I  eventually proved it by doing a lot of substitution and logic.

Monday, June 13, 2011

Starting graph theory

Today I started reading Introductory Graph Theory by Gary Chartrand.  It's starting off teaching about modeling.  Modeling in this case is turning something into math, such as the area of a square being A=W^2.

I reached the part in the book where it talks about actual graphs, but it was using terms from set theory which I'm not familiar with.  Fortunately the book has a section in the back which teaches you the basics, so I started going through that as well.  It's mostly been review so far (I picked up some bits of set theory here and there while studying other things), introducing you to the symbols/operations such as "element of set", "subset", "equal set", etc.

This made me curious about whether there is a good book devoted to set theory.  After some searching I found this thread which contains an abundance of recommendations.  Naive Set Theory by P. R. Halmos and Theory of Sets by E. Kamke look interesting, the first covering more area in less time and the second covering a few topics in more depth.

Friday, June 10, 2011

Well, apparently it's not a prereq

Today I decided to learn about the Laplace Transform and eigenvectors/values.

From what I gather, the Laplace Transform transforms a function f(t) into a function f(s).  I'm not entirely sure what "s" is supposed to be though...  I suspect it is used as a temporary placeholder for going inbetween different Laplace transforms or something, but the videos weren't very clear.

An eigenvector is a vector which can either be transformed by a certain matrix or multiplied by a certain scalar and result in the same vector in both cases.  The scalar is called the eigenvalue.

I also found out that the class I started going through was apparently not a prereq for the Convex Optimization classes.  I seem to have misread the prereqs, effectively "putting the comma in the wrong spot".  I'm not going to complain about having less on my plate though!

Speaking of having less on my plate; I seem to have spoken too soon.  Earlier today I remembered that Chris Hecker has a page listing resources for learning how to simulate physics, located here: http://chrishecker.com/Physics_References  Now that I have a bit more experience, I decided to give it another look.  I think it might be good idea to go through the steps he describes, so I will be looking into getting the first book in a month or so.  In the meantime, I ordered some books on graph theory, abstract algebra, and topology.  These should keep me busy for at least a month, and they cover topics I have been curious about for a while.

Thursday, June 9, 2011

Going back into study mode

Yesterday I made it so that you could control the pitch, heading, and roll of your ship using the mouse and cursor keys.  Pitch and heading adjustment works fine, but roll is dependent on the direction that your ship is facing; I actually suspect that the other two have similar problems as well, just not as pronounced.  This led me to start reading through physics articles to try and find a solution.

While reading the articles I was reminded that I still don't know much about mathematical programming (linear, quadratic...), which seems to pop up a lot in physics and makes an appearance in collision detection.  I figure this is as good a time as any to correct that, so I have started going through the free classes on the Stanford website located here: http://www.stanford.edu/~boyd/  Class EE263 is a prerequisite for the convex optimization classes, so I'm starting there.  If this starts taking too long, I may decide to postpone further study in this area, but hopefully I won't have to.

Writing blog entries will be a bit challenging for a variety of reasons, but the plan is to continue updating at least five times per week.  The last thing I want to do is just repeat what's said in the lectures, so I may draw from multiple sources when I discuss what I have learned.

Wednesday, June 8, 2011


A skybox is used to add a background to a 3D scene.  Things which are so far in the distance that they can be drawn into a 2D texture, such as the sun, distant mountains, and unmoving clouds, are part of the background.  It is literally a box with the camera at its center.  As the camera moves, the skybox follows it.  Because the background doesn't move as you move, it appears to be very far away.  The skybox doesn't rotate with the camera though.  Picture a cardboard box ontop of your character's head and you have about the right idea.

Using a skybox is pretty easy.  Making the texture for it is a bit difficult, but fortunately us programmers can leave that to the artists.  To use a skybox, you first need a cube which has the sky texture applied to its inside.  You could create this in the game, or get the artist to create it as a model and load it in along with the other models.

There are two ways you can render a skybox.  The first is to render it last, which requires a skybox large enough to enclose all of the visible geometry.  The second is to render it first and then render the rest of the scene ontop of it.  This method allows you to use a smaller skybox (just big enough to fully enclose the camera should be fine) but can be slower since there is more overdraw.  When rendering the skybox first, you need to disable writing to the z-buffer so that the rest of the scene can be drawn ontop of it.  For either method, make sure to disable lighting before rendering the skybox, otherwise the edges will be much more visible.

Tuesday, June 7, 2011

First screenshot of new project, mouse look

You can now look around the cockpit using the mouse.

In order to get the mouse's relative movement, I used raw input.  After I have the relative movement vector, I multiply it by the mouse sensitivity and multiply that by the rotation speed.  This gives the final angular velocity vector which I use to integrate the orientation.

Here is a screenshot of what the game looks like so far.  I plan on removing the "blast shield" tomorrow and put in a star filled background.  Before I can make it so you can fly around, I need to make it so that you can tell you are moving!

Monday, June 6, 2011

Direct3D9 FFP Lighting

Today I finally managed to get the cockpit model into the game.  I've decided to use the fixed function pipeline this time rather than shaders; it's probably a good idea to be experienced with both.

To use FFP (fixed function pipeline) lighting, you first need to fill in a D3DLIGHT9 structure.  The elements are pretty straight-forward.  I've found that you need values much greater than 1.0 for the light's color though; somewhere around 300 in R, G, and B for white lights is working well for the moment.  After you have the structure filled out, pass it to IDirect3DDevice9::SetLight().  After setting the light information, you need to enable to light as well using IDirect3DDevice9::LightEnable().

To take full advantage of the lighting system, I recommend setting a material as well.  To do this, fill out a D3DMATERIAL9 structure.  The material describes what components of the incoming light are reflected, and by how much.  It also describes how shiny a surface is with the Power element, and how much light the surface is emitting with the Emissive element.  Note that the emissive element does not actually act as a D3D light; it only makes it seem like the material is glowing.  After the material structure has been filled, pass it to IDirect3DDevice9::SetMaterial(). Now that the actual material is setup, we need to tell Direct3D that the diffuse and specular information is coming from the material and not the vertex buffer.  To do this, set the D3DRS_DIFFUSEMATERIALSOURCE and D3DRS_SPECULARMATERIALSOURCE render states to D3DMCS_MATERIAL.

Friday, June 3, 2011

Researching Direct3D9 Lighting

While doing some further research into the relation between a graphics API and the graphics driver, I came across this article: Mode Switching.  I recommend reading it if you are interested in the things I discussed in the previous blog post.

I spent most of the day in research, mainly into the way lighting is performed in Direct3D9.  Apparently you can set a material to specify ambient, diffuse, specular, and emissive colors, as well as the specular power.  I originally thought that you had to pass this information in a vertex buffer.  The layout of the MS3D file format makes a lot more sense now, since all of the colors are stored together rather than per vertex.

Another interesting thing I found out is that material colors specify how much of the incoming light affects the resulting color.  Having a diffuse material color of (r:0.5 g:0.0 b:0.0) for example means that 50% of the red component of the light's diffuse color is used, and the green and blue components aren't used at all.

Thursday, June 2, 2011

The relation between graphics APIs and graphics drivers, also CRT security enhancements

While working on the model loading code, the compiler complained about fopen() being deprecated.  These warnings aren't new, but I've been wondering for a while what exactly caused the functions to become deprecated.  So after a Google search I found myself at the MSDN reading "Security Enhancements in the CRT", which led me to partially read "Repel Attacks on Your Code with the Visual Studio 2005 Safe C and C++ Libraries".  Basically the functions are deprecated because new ones were written which check for buffer overruns and various misc. checks such as making sure that pointers are not NULL.  The part which I'm the most interested in however are the changes they made to error handling.  More functions return error codes now, which makes my job a little easier since I don't have to guess at why the function returned a NULL pointer.

I also did a little research into the relation between Direct3D/OpenGL and the graphics driver.  I've wondered for a while how you could make your own graphics API, and I think I have an answer: You can't unless you write your own drivers or can convince driver developers to adopt your API.  This might be a bit vague, so I'll try to explain my understanding of how things work.

A graphics API is just an interface to the graphics driver.  You are effectively communicating "directly" with the graphics driver when you use Direct3D/OpenGL (I'll get to why that is in quotes shortly).  If you aren't familiar with the term in relation to programming, an "interface" is a set of functions which act as the only way of communicating with a "black box".  A "black box" in this case is a chunk of code which you do not have access to, and you do not know how it works exactly.  Direct3D/OpenGL is pretty much just a design which the driver developers use.  Because all of the driver developers will be working with the same design, you end up with a common "face" to the driver, allowing your program to easily communicate without trying to figure out which driver it is talking to.

This brings us to why I used quotes earlier.  There is actually another layer in between your application and the graphics driver when you use Direct3D.  Rather than plugging your application directly into the driver, you are attached to the Direct3D layer (I am assuming this is d3d*.dll).  The Direct3D layer performs some additional work (again, I am assuming here) and handles communication with the actual graphics driver.

In the case of OpenGL, I think you are plugged directly into the graphics driver...  I don't know very much about OpenGL though.

Wednesday, June 1, 2011

Systems layer makes a comeback

The first thing I did today was the removal of the initialization game state, replacing it with the systems layer.  The "systems layer" is a collection of objects/systems common to all game states.  Examples of these are the main window, Direct3D device, and timing system.  Currently the systems layer is a collection of scope pointers in the application layer's Run() function.

Something I realized while working on the systems layer is that I no longer need the window manager.  The purpose for the window manager was to have a constant place for the window procedure to exist.  Now that ownership of the main window isn't being transferred between game states repeatedly, I can put the window procedure in the application class.

With the systems layer in place, I was able to easily give the main window code a pointer to the current state safe pointer.  When the main window receives the WM_CLOSE message, it calls the IGameState::WindowClose() method on the pointer.  The actual code looks a bit ugly due to the whole pointer-to-a-safe-pointer thing, but at least it works: m_state.Get()->WindowClose();

I also put the basic rendering code in place.  This gave me the chance to try out the COM wrapper idea I mentioned in a previous blog post, and it's working great!  Using a generic wrapper is a lot easier than creating a wrapper for each interface.

While writing the timing system for the fixed timestep, I decided to take a closer look at the conversion from int64 to double which is required when using QueryPerformanceCounter/Frequency().  My main concern was losing precision.  I looked into doing integer-only math for the timer, but I quickly remembered that not using floating-point math for timing in a fixed timestep had caused problems in the past.  I eventually decided to just cast to double like usual, and fix the problem when it is actually a problem.