# Question
Title: Physics for a 2.5D platformer with a plane that curves
I'm creating a 2.5D platformer in XNA which uses 3D models that are constrained to travelling along a 2D plane (just like Trine).

To make things tricker, however, I want the 2D plane itself to be able to curve. Consider this replay of Klonoa (you only need to watch for 10 seconds): although the player was on a 2D plane, the plane itself could wrap around the side of a mountain, effectively allowing the player to travel through 3D space - all the while constrained to the regular 2D plane of a platformer.

**How should the physics be approached in a game like this?**

* Should I use a 2D physics engine or a 3D physics engine?
* Are there any physics engines actually designed with this situation in mind?
* For any that weren't designed for this: what hacks or tricks will be necessary to get the physics engine cooperating with me?

# Answer
A platformer like this is still, in its essence a 2D platformer. The 2.5D effect, even the curling around the mountain, is merely a visualisation of a world constrained in 2D. Your physics engine will probably only operate on this world and not on the visualisation of it, so a 2D physics engine will be sufficient.

That said, you might be interested in some 3D effects. In the game "Bionic Commando:Re-armed", defeated enemy characters will kinda 'roll' off the platform, making the ragdoll physics actually 3D. In addition, most 3D physics engines allow you constrain the movement along one or more axis (albeit with some tweaks like creating a joint between the road and moving characters).

Remember that not every 3D effect needs a full-blown physics engine. You could code your own 3D implementations for minor things like falling debris after an explosion, without having to resort to a complete 3D engine.

My recommendation is starting out with a 2D engine if you probably will not need physics calculations in the 3rd dimension. Otherwise pick a 3D engine and constrain the calculations in only two axis where relevant.
> 9 votes

# Answer
It depends if any of your physics can happen outside the flat player space.

As ghostonline said debris and ragdoll animations are a classic example of out-of-2D physics in an 2.5D game.

Another example is bullets: If there are any projectiles in your game, do they follow the curvature of your 2D space or do the travel straight ahead even if that means they will leave those bounds?

Also mapping a physical 2D space to a curved 3D visualization correctly is (correct me if I'm mistaken) .. not that easy. You will need an injective projection functions probably involving lots of splines or something similar.

While having curved 2D game spaces is a nice add-on, it requires quite some overhead for the code. That might be the reason why there is no such thing in Trine. But the game was fun anyway, wasn't it? I'd think twice about a feature like that.
> 2 votes

---
Tags: xna, 3d, physics, 2.5d
---


# Question
Title: How do I find the largest circle possible in a square of pixels using Unity?
As I am using Unity, I can easily grab a square of pixels of any length. However, I want to find the largest circle possible within that square of pixels.

So for instance, if I had a 40 x 40 square of pixels, how would I get an array of pixels that form a circle inside of the square?

# Answer
On a 40×40 square of pixels, you can draw a circle with approximately 40×sqrt(8) pixels.

If you are looking for a circle drawing algorithm to let you pick the pixels to put in your array, an easy way is to draw an eighth of the circle, for instance using the midpoint algorithm, then mirror it three times.
> 1 votes

---
Tags: mathematics, unity
---


# Question
Title: Changing player color without multiple player bitmaps
> **Possible Duplicate:**
> How to colorize certain parts of a model - like RTS games have those team colors?

Ok, so here is my current situation. I have a player model, fully UV mapped, and textured. At first I made multiple bitmaps for the character representing multiple colors for each team in the game. (red, blue, green, yellow, etc) Well, as my player count build up, space lowers. So I needed to make a new method of keeping the game effecient, clean, and fast. So I thought of the idea of having a color mask (alpha map covering the areas to be colored). I am using OpenGL, and I just have NO idea on where to begin!

So I ask you, are there any libraries? methods? anything that could help me do this?

# Answer
I recommend using the same idea that they use in movies - chroma key. Reserve one color that you don't otherwise use in your textures (e.g. green, blue, magenta). Let's call it the "reserved color." In the engine, make a matrix that rotates the "reserved color" onto the "player color" you wish to render at the moment.

Set this matrix as a pixel shader constant. In the pixel shader, compute the chroma of the pixel color and find its angle to the "reserved color's" chroma. Lerp the pixel color to the pixel color transformed by the matrix, according to how close the pixel's chroma is to the reserved color's chroma.

Why do this instead of using an alpha channel? Because when textures are DXT compressed, adding an alpha channel makes your texture 2x bigger. A matrix multiply and a little bit of trig in the pixel shader is a lot cheaper than reading 2x as much memory - and will become even cheaper as the years roll on.
> 4 votes

# Answer
you can make a model with some base color and replace that color with a shader.

```
color = texture_color(x,y);

if(color == base_color)
    color = team_color;

```
> 2 votes

---
Tags: opengl
---


# Question
Title: How to colorize certain parts of a model - like RTS games have those team colors?
I am in a need of implementing something we see in RTS games: team colors. Basically, I am looking for a way to colorize certain parts of a model. How would I achieve this? I have no idea where to even begin. Do I need to make some adjustments to the 3d model first?

# Answer
> 18 votes
The way I would do this is based on the texture maps you are applying to the units. For most stuff you would have some regions that need to be tinted and some that do not. So for example, you might have a normal tank but you want to just change the color of some flags.

If you paint the texture as if the colored regions are grayscale you can then use the alpha channel to designate which regions need to be colorized.

So in your shader you could go (for the most simple way):

```
float3 finalColor;
if (colorFromTex.a > 0)
 finalColor = colorFromTex.rgb;
else
 finalColor = colorFromTex.rgb*myTintColor.rgb;

```

That's not optimal though since you will a have a hard transition and have a branch in your shader. Instead it's better to go:

```
float3 finalColor = lerp(colorFromTex.rgb,
    colorFromTex.rgb*myTintColor.rgb, colorFromTex.a);

```

# Answer
> 3 votes
One technique is to have two sets of textures for each model - one red, the other blue. Then depending on which team the character is assigned to you apply that texture set.

Obviously this only works if you have just two teams. While you might get away with it for more than two it starts to get inefficient.

Another way is to blend two textures - the first being the base texture for the model, the second being a coloured overlay which you could generate at runtime.

A third way could be to change the colour of the base model and have no textures (or partially transparent textures) over those parts of the model that you want to show the team colours.

# Answer
> 2 votes
Devoting a texture alpha channel to team color makes DXT textures 2x bigger, so I would rather use chroma key to calculate team color. Designate one color (e.g. green, blue, magenta) as the "reserved color" in your textures.

When the engine boots up, make a matrix for each team color that rotates the "reserved color" onto the team color. Just before drawing a team object, set this matrix as a pixel shader constant.

In the pixel shader, transform the pixel color by the team color matrix. Lerp the untransformed pixel color with the transformed pixel color, by an amount proportional to the angle of the pixel's chroma to the "reserved color's" chroma.

This will cost you some ALU instructions and trig in the pixel shader, but that's a lot cheaper than bloating up your texture cache with textures 2x as big.

You also have the ability to have multiple chroma keys (e.g. magenta and cyan get mapped onto a primary and secondary team color) without devoting one texture channel to each color.

# Answer
> 1 votes
My technique would be: Having 2 textures: one main texture, one second texture overlaying the main but only the parts you want to be colored. Change the second texture's color as you want to.

---
Tags: xna, c#
---


title: XNA GameTime before first Update

text:
# Question
Title: XNA GameTime before first Update
Using XNA, is it possible to access the GameTime object *before* Update is called for the first time?

Can it be used in the game constructor, Initialize or LoadContent methods?

# Answer
I don't believe this is possible:

> The GameTime object received by Draw and Update isn't technically owned by anyone, but is instead re-created each Game.Tick and passed to Update and Draw from there.
>
> Internally, Tick fills the value of the Total/ElapsedRealTime properties based off of the current high performance counter value as reported by Stopwatch.GetTimestamp(). If the PC the program is running on does not have a high performance counter, then it returns DateTime.Now.Ticks.
>
> The Game Time properties (as opposed to real-time) also use the Stopwatch.GetTimestamp, however elapsed time since application launch and last frame are computed internally and then filled in before **GameTime is passed to Draw or Update - so there's no external way to compute those values directly.**

Source: http://forums.create.msdn.com/forums/t/10587.aspx, bold mine. Also included there are several work arounds, similar to what you've already outlined though.
> 5 votes

---
Tags: xna, game-loop
---


title: Blending 2d images to subtract alpha

text:
# Question
Title: Blending 2d images to subtract alpha
I'm looking into doing a 2d lighting system with a result similar to this: http://forums.tigsource.com/index.php?topic=15619.0 This thread I believe disregards color, as well as doesn't really list a clear final solution, which is something we could provide here.

What I'd like to do is start with a solid black texture, and render colored lights to it. When I render a colored light onto the texture, I'd like it to subtract the alpha away from the solid black texture but also add in the color of the light. In the end, my goal would be to have a texture that I can blend normally on top of my scene, using glBlendFunc( GL\_SRC\_ALPHA, GL\_ONE\_MINUS\_SRC\_ALPHA), which would let the background show through in the "lighted" areas in addition to adding some of that lights color to the area.

To start I fill the texture with black:

```
glColor4f( 0.0f, 0.0f, 0.0f, 1.0 )

```

Then I set the blend function to subtract and draw the lights:

```
glBlendEquation( GL_FUNC_SUBTRACT );
glBlendFunc( ??? , ??? ); // Not quite sure what to put here

// Draw a triangle fan for the circle of light.
glColor4f( 0.0f, 0.0f, 0.0f, 0.8f );
glBegin(GL_TRIANGLE_FAN);
glVertex2f(0, 0);
glColor4f( 0.0f, 0.0f, 0.0f, 0.0f );
for (float angle = 0; angle <= 6.28; angle+=0.1) {
    glVertex2f(sin(angle) * sizeOfLight, cos(angle) * sizeOfLight);
}
glVertex2f(sin(3.14159*2) * sizeOfLight, cos(3.14159*2) * sizeOfLight);
glEnd();

// Reset this back to normal
glBlendEquation(GL_FUNC_ADD);

```

The guts of my question is what type of blending would I need here, on the second line of this code block.

# Answer
What it sounds like you want to do is additively blend your lights together, and then multiply the results on top of your scene.
> 1 votes

# Answer
If I were you, I'd render two scenes: a light-only scene and an everything-else scene. First, clear the Z buffer to zNear and render the light-only scene with zCompare turned off and Z set to zFar. This will make it so unlit pixels = zNear and lit pixels = zFar.

To draw the lights, the simple way is to bound each light by a rectangle on screen and render a quad with a texture of a radial gradient and additive blend.

If you intend to have a very large amount of lights, eventually you will have to do it the fast way: divide the screen into tiles and for each tile, set pixel shader constants to say where each light in the tile is and what color it is, and in the pixel shader for each tile, render all the lights into pixel shader registers before finally returning only the total light with no additive blend.

Anyway, after you've rendered all the lights, copy off the light color buffer somewhere else as a texture, and start to render the main scene.

Since all unlit pixels were set to zNear in the light pass, you won't waste any GPU time rendering unlit pixels in the main scene, woot!

If the main scene is rendered with deferred rendering, then use the light texture you made in the beginning in a deferred lighting pass. If the main scene is forward-rendered, then in the pixel shader of each object in the main scene, read in the light texture and multiply the pixel's albedo by it before writing it out.
> 0 votes

---
Tags: 2d, opengl, lighting, blending
---


title: Collision Problems

text:
# Question
Title: Collision Problems
I'm having some troubles with a 2D platformer type game (there's more to it, but that's all that matters for this question). I had collision with the platforms working fine, but if the character hit the side of the platform, they would be automatically be placed on top of the platform. This is bad, for obvious reasons. I want the player to hit the side and fall, like one would expect. So what I'm trying to do is simply keep track of the previous position of the player, and if the player's bounding box overlaps the platform's bounding box, move the player back to their previous position. The problem is, when the player is on the platform, they cannot move left or right. They can jump, they can move while they're in the air, and their falls are stopped by the platforms. I just can't figure out why they won't move anymore. Here's some relevant code:

```
// previous position is stored
previousPos = new Vector2(playerPosition.x, playerPosition.y);

....
// game checks input and calculates next position and
// stores it in playerPosition. only changes the Vector2
// playerPosition, does not display the change via the sprite yet,
// so it doesn't look like it's stuttering to the player
....

if (!isJumping) {
    // loop through the platform list
    for (Platform platform : platformList) {
        // if the player is touching a platform, then they are on a platform
        // and they are not falling
        if (platform.getBoundingBox().contains(playerBoundingBox)) {
            playerPosition = new Vector2(previousPos.x, previousPos.y);
            boundingBoxPositionLower = new Vector3(playerPosition.x, playerPosition.y, 0);
            boundingBoxPositionUpper = new Vector3(playerPosition.x+playerSprite.getWidth(), playerPosition.y+playerSprite.getHeight(), 0);
            playerBoundingBox.set(boundingBoxPositionLower, boundingBoxPositionUpper);
            isOnPlatform = true;
            isFalling = false;
            playerDirection.y = 0;
            break;
        }
    }
}

```

I'm not sure where to go from here. Maybe ideas on how to debug? Or maybe it's just a simple problem I'm overlooking. If you need any other code snippets, let me know.

Thanks guys!

PS - Sorry I don't follow the 80 characters per line standard, it all fits on my 1080p monitor fine in my IDE :P .

# Answer
> 2 votes
A little late, but posted as an answer as requested.

They wont move any more because they 'hit' the platform, so you're moving them back to their previous position. You need to check their new position against the old position. If they moved down into the platform from the top (as with gravity), you just need to use their old Y position, not the X.

To solve the 'sticking to the side' issue, you'd do the same as the 'sticking to the top' solution, but just revert the X and leave the Y in tact.

In the case where you move the character too far back, you could just calculate the exact X or Y position using the width/height of the bounding boxes.

Eg. If you're using the centroid as your position, and the player is moving left-to-right and hits a wall:

```
player.X = wall.X - (wall.Width / 2) - (player.width / 2);

```

# Answer
> 4 votes
You really just got to do the inverse for side collisions, go back to the old X and let the Y go on to continue the fall. Beware of corners where you hit two different blocks, there you got to make the full stop.

And by the way, ideally you shouldn't move all the way back to the old position, but just far enough that you don't collide.

---
Tags: opengl, 2d, java, collision-detection, movement
---


# Question
Title: Megatexturing : Evolution from Quake Wars to Rage
I remember John Carmack talking about how they initially used Megatexturing for Quake Wars: Enemy Territory. The technology has since evolved quite a bit in Rage.

I was wondering if somebody here can give some technical details on the specifics on what and how it has evolved since then.

# Answer
> 6 votes
I don't know, if it's what you are looking for, but you can try this video and this paper from GDC 2011. It's about: Mega Meshes - Modelling, rendering and lighting a world made of 100 billion polygons. And there is a lot about texturing.

# Answer
> 3 votes
I would recommend to check "Virtual Texture Mapping 101" article on GPU Gems. It is basically dividing the original texture (which is usually huge) into smaller tiles and load them into GPU memory when needed. The same idea can be used to render huge and high detailed terrains.

# Answer
> 3 votes
For starters, Beyond3D has a nice little Writeup of some technical tidbits gathered throughout an interview with Splash Damage's Technical Director Arnout van Meer as well as Senior Graphics Programmer Mike Armstrong. This same article specifically cites some disadvantages about MegaTexturing in its then current iteration on page 5. It hints at John Carmack having already fixed some of them in a later revision as well as at ways to fix some others that were not viable at the time.

Notable examples are:

* Sniper Rifle zoom won't stream in higher quality mip maps for displayed tiles
* Not possible with arbitrary geometry

Also, in this interview John Carmack states that some of the shortcomings of the technology used in Quake Wars have already been fixed in internal builds - for instance applying MegaTextures to arbitrary geometry including characters and vehicles.

# Answer
> 2 votes
Sean Barret's GDC 2008 Sparse Virtual Texture presentation was his attempt to recreate what Carmack was doing at the time. There's source, too. There has been some correspondence between Carmack and Barrett since then.

(The presentation is a bit dense, but worth taking the time to understand -- I spent a few hour-long sessions with a whiteboard after watching it twice in the course of two days, and eventually got to the point where I think I understood it all. Much easier if you have a fragment shader background, which I didn't at the time. It's also really neat that the presentation *is* the demo.)

+1 to zacharmarz for mentioning the excellent GDC2011 Mega Meshes presentation by the Lionhead folks working on Milo and Kate. There are a lot of very practical solutions mentioned therein, for example: rendering every other frame at different locations (hotspots, 180 degree turns, zooms, further along a control spline, etc) to determine texture visibility and mip levels, and communicating the results to an "L2 Cache", to solve some of the texture streaming issues. Not necessarily simple, but nonetheless elegant in its directness.

---
Tags: textures
---


# Question
Title: What is a good method for coloring textures based on a palette in XNA?
I've been trying to work on a game with the look of an 8-bit game using XNA, specifically using the NES as a guide.

The NES has a very specific palette and each sprite can use up to 4 colors from that palette. How could I emulate this? The current way I accomplish this is I have a texture with defined values which act as indexes to an array of colors I pass to the GPU. I imagine there must be a better way than this, but maybe this is the best way?

I don't want to simply make sure I draw every sprite with the right colors because I want to be able to dynamically alter the palette. I'd also prefer not to alter the texture directly using the CPU.

# Answer
I think what you are doing is just fine.

If you had more than four colours I might suggest doing a dependent texture read: Instead of using the value of the texture to look up an array of colours (I assume you are passing these as shader parameters), you could use it to look up a colour in another 1D texture containing your palette.

But this has some performance implications - and I think it limits you to PS 2.0.

(There are some other sneaky optimisations possible if you're having to switch palettes every sprite and all the extra batches are killing performance. But I imagine in a NES-like game this is not the case.)

I think what might be useful in your situation is to use the XNA content pipeline to take an easily editable, colour version of the sprite, check it only uses four colours, convert it to a texture with your four levels of grayscale (usable by your shader), and perhaps also output the original colour palette along side the texture.

The Creators Club samples for the content pipeline might be a good place to start.
> 7 votes

# Answer
Would it be to slow to create a composite class that can contain up to 4 objects that are one of each color for the sprite and combine that into the sprite that gets drawn. So each sprite is a composite of up to 4 sprites combined and then drawn.

Then you could change 1 color via that class and the entire sprite would change.

(note, I haven't done XNA but this might spark some ideas with you.)
> 1 votes

# Answer
If you don't care at all about memory performance, you could store your sprites uncompressed such that pixels with color 0 are pure red, 1 are pure green, 2 are pure blue, and 3 are pure alpha.

When about to render a sprite, set a matrix pixel shader constant made of four vectors that correspond to colors 0, 1, 2, 3. In the pixel shader, execute the following code to recolor the sprite texel:

```
float4 unpaletted = tex2D( texture, uv );
float4 paletted = mul( unpaletted, paletteMatrix );

```

This works because when a pixel is color 0, it is pure red, and so it will end up as

```
1 * palette[0] + 0 * palette[1] + 0 * palette[2] + 0 * palette[3]

```

or

```
1 * palette[0]

```

and the same applies to colors 1, 2, and 3.

If you do care about memory performance, then by all means store your NES palette as a 256x1 RGB uncompressed texture, set texture filtering to nearest-neighbor, store your sprites as uncompressed 8 bit single-channel textures, and do shader code something like this:

```
float palette_index = tex2D( texture, uv );
float4 color = tex1D( palette, palette_index * 255 );

```
> 1 votes

---
Tags: xna, textures, palette
---


title: 2d Procedural universe generation

text:
# Question
Title: 2d Procedural universe generation
I want to create a flat universe, where at first the whole universe is blank.

That would be represented by a parallax scrolling nebula background image.

What I want to do is represent the planets as disc shaped objects in the universe. They can be of various sizes.

The inside of the discs will consist of a landmass, then outside that will be a body of water and after that air.

what would be the best way to go about creating those tiles procedurally as for example the air would consist of various gases and the land of various minerals and resources.

My first thought is to create texture images and then stamp out the circles out of those textures, but problem is that those textures would have to wrap horizontal and vertically. Is there a fully procedural way of doing this?

# Answer
Procedural textures, particularly noise-based ones, can be made to tile. See this thread at GDNet for some discussion, as well as this journal entry. There's also this link, which sounds interesting although I can't speak for its veracity.

As for procedurally generating the world, there's this article written by the guy developing Infinity. His system is 3D but you could probably adapt the techniques easily enough.

There's a whole wiki on procedural content generation, too.
> 14 votes

# Answer
It sounds to me like you want rectangular textures with air on top and dirt on the bottom. You can map rectangular textures to the circles by making the U texture coordinate represent angle around the circle, and V texture coordinate represent distance from the center of the circle. For larger planets, U can wrap around the planet several times.

To convert from regular 2D coordinates XY to the above UV coordinates, you can do math like so:

```
y -= planet_center.y;
x -= planet_center.x;
u = atan2( y, x );
v = sqrt( y*y + x*x );

```

Care should be taken to avoid calculating this too close to the center of the planets...
> 2 votes

---
Tags: procedural-generation, terrain
---


title: Configuration management in XNA

text:
# Question
Title: Configuration management in XNA
I come from a .net web background so I am accustomed to using xml .config files. What is the XNA equivalent? It seems to me that using the same practice of a xml config leaves your game open to easy modification (which can be good, I know). In my day-life web development the configs live on servers where users can't access. XNA games live purely on the client (most of the time).

Say I have some values I want in a config, can the config be obfuscated or is there a different configuration management system for XNA? Is the only solution to hardcode the values back in before release so they are not accessible?

# Answer
Your dev machine takes the XML & uses the content processor to convert it into a binary XNB file which is distributed to your customers. The XNA runtime on the customer device can understand and load it. The customer device does not need to ever have the raw XML on it.
> 5 votes

---
Tags: xna, c#, xna-4.0
---


# Question
Title: Designing for multiple screen resolutions and aspect ratios, target one resolution then scale to meet others or use normalized values?
I feel like what I'm currently doing is stupid but would just like reaffirmation it is. Basically I'm writing games which target a certain screen resolution (800x480), so all positions, widths and heights I set for sprites is for that resolution.

On the engine side I have special scalers which will change the width and height of what is being drawn to meet the current platforms res, so for example if the platforms screen res is 1200x720 I will stretch a sprite by a factor of:

```
1280 / 800.0f;
720 / 480.0f;

```

Positions are also offset and manipulated in a similar way.

I really feel I should move to a normalized system for widths and positions (i.e. 0 to 1) but at the same time feel this is more intuitive since the first platform I target is 800x480 and I already kind of have a good udnerstanding of dimensions and such for that.

So my question is, is it really that bad to target a specific ccreen res then in the engine side modify this res to meet different platforms?

# Answer
> 3 votes
> So my question is, is it really that bad to target a specific screen res then in the engine side modify this res to meet different platforms?

Generally speaking, no. Changing the scale of your number and then normalizing to 0..1 later just means it's easier to design the UI.

The one thing that'll bite you on this, though, are different aspect ratios. If you're authoring on a coordinate system that's, for example, 4:3, things are going to stretch pretty bad at 16:9.

There are a couple of solutions to this. One is to just accept the stretching. Another is to stretch to fill the screen area, and just not have any UI in the side areas if you are displaying on a screen that's wider.

A more robust solution, though, is to set up some kind of anchoring system. Generally speaking, you want certain elements near the edges of the screen. You set up your widgets such that the "quit" button is in the "upper left", offset by some amount. Then when your resolution changes, the button's absolute position shifts such that it makes sense.

# Answer
> 1 votes
You might want to consider only scaling some things, specifically the positions of the layouts. But then leave the actual size of the UI elements the same and allow the user to step it up in increments as they see fit. This should give you a layout that works between resolution and aspect ratios as well as increasing the options the user has in how predominant the UI is on their screen all while solving the issue you are addressing.

Hope this helps

# Answer
> 1 votes
If this is your first time out, then you're unlikely to get this right. *Something* will come and bite you in the arse, and it's unlikely anyone will be able to steer you away from that because what that thing is will depend on your design.

So my advice is pick a resolution for this project, and treat it as your "virtual" coordinate system and let it lie at that. As you've already mentioned, you're currently thinking in 800 * 480, so stick with that.

If you're working on your own 2D engine on 3D hardware, then you can use your vertex shader to compensate for the actual size of your back buffer. Otherwise, you'll need to factor in a scale somewhere in your pipeline between the fixed logical units and the variable screen dimensions.

Now, what to do about aspect ratio changes? The easiest plan is to just assume you'll letter box. That's not a terrible choice, and most devices are close enough in aspect ratio that it won't matter. In that case, all you'll have to do is calculate the largest square that fits inside the screen at your aspect ratio, calculate either a horizontal or vertical offset to center that box on screen, and then mask off the remaining space.

One step up from that, but heavily dependent on what kind of game you're making and how you're building it, is making sure you have some bleed in your backgrounds that can extend outside the play area into what would be the letter boxed area. This would give the user the impression that you're filling the screen, without shagging up your logic.

Imagine, for instance, Mario; you could easily see making it taller if you had to, just repeating sky and ground tiles above and below. Going the other way is a little dicier, in that you'd have to show more of the level to the left and right, which may break some of the design, but art wise appending a few extra columns to the far left and far right of the level would be trivial.

---
Tags: sprites, interface, aspect-ratio
---


title: AR app: Mapping 3D object to 2D plane?

text:
# Question
Title: AR app: Mapping 3D object to 2D plane?
I'm trying to create an Augmented Reality app. I'm using OpenCV to get 4 points from a checkerboard pattern that represent the four corners of the pattern. This should be used to create a plane in my app, but the points are in 2D.

Anyone here have an idea how one is to use these 4 points to create a plane and/or map a 3D object to the pattern

# Answer
Having found the corners in 2D, you assign them 3D coordinates yourself. (You might know the actual physical size of the board squares, or you might simply do everything relative to these sizes e.g. assign them a size of 1).

You then calibrate the camera giving the chessboard positions and your assigned 3D coordinates. OpenCV then computes a camera model. With this camera model, you can project 3D points.

There is a good example in ***Tutorial 10***. This also shows how to undistort the image.
> 1 votes

# Answer
There was a question on Stack Overflow that also has a link to the ARToolkit which describes the process they use a little bit.
> 0 votes

# Answer
So, haven't tried this before, but here is my guess at the approach.

You've got four points in screen space, in 2D. Let's refer to those as the UL,UR,LL,LR corner points (upper left, upper right, etc.).

Create a vector from the LL to the UL (so, along the left edge), and another vector from the LL to the LR (along the bottom edge). The cross product of these two vectors (with normalization applied where needed) give you the normal of the plane for the checkerboard.

You've still got to figure out the distance of the plane from the camera; to do this, you need to figure out how the edge distances compare with what you believe they should be, and so back out the perspective scaling that's been undergone. To get a feel for the scales, you'll probably need a calibration phase for your code where you place the checkerboard facing the camera straight on (perpendicular to the camera) and move it to different (measured and known!) distances, observing the detected lengths of the edges. From that information you can figure out the perspective transform of the camera.

That should be a good start, anyways.

---

**Update**

I made a mistake here and failed to address that the actual depth of the points/vectors would still need to be worked out. The cross-product as spec'd above would be useless, as it could only give you a vector perp. to the camera, which is useless.

I'm leaving this up in case it spurs any ideas, but the approach I quickly sketched is, at best, deeply flawed.
> 0 votes

---
Tags: 3d
---


# Question
Title: How can I insert and remove blocks quickly in a Minecraft-style world?
I currently have volume data for the world stored as an array of booleans. I then check each empty block and if it has non-empty neighbors the faces get drawn. This prevents me from sending a bunch of faces to the graphics card using OpenGL.

I'm now working on inserting and removing blocks but I'm not sure how to do this quickly. It is simple enough to change the volume data but I don't want to recompute all the vertices from the volume data each time someone inserts or removes a block. It occurred to me just to add the block to the vertex buffer at the end of the existing vertex data but then I don't have a good way of destroying it as I have no way to correlate between the volume and vertex buffer data.

Any thoughts on how I can fix the mess I'm in?

# Answer
> 8 votes
Notch says:

> Terrain is generated, saved and loaded, and (kind of) rendered in chunks of 16\*16\*128 blocks

Divide your world into small subsections of space. Within each of these sections, generate a VBO for the faces of the cubes (or place the faces into a big shared VBO). Each time you edit in a section, regenerate the VBO from scratch. This is unlikely to be a performance bottleneck.

---
Tags: opengl, performance, voxels
---


title: rendering rolling hills

text:
# Question
Title: rendering rolling hills
I want to render very pretty smooth undulating hills. There are objects snuggled between these hills, so I can't really use naive bump-mapping.

I am currently rendering using a very detailed mesh that I generate myself. Its a lot of very small triangles.

Are there other approaches? What is the current viability of displacement mapping, for example?

I would like to run on mainstream hardware, including integrated graphics, and possibly even one day across to tablets and such.

# Answer
> 4 votes
All the games I know of that display lots of terrain make heavy use of LODing to create the illusion of huge amounts of very detailed surfaces.

The CryEngine is king at this. And in World of Warcraft you can even see the LOD transitions when using low-performance settings.

The second post at http://www.gamedev.net/topic/439081-crysis-voxel-based-terrain-engine/ describes many different techniques to visualize huge terrains efficiently. Especially the HLOD article http://www.cs.unc.edu/~walk/hlod/ seems helpful.

I doubt that displacement mapping will get you anywhere near the performance obtained by simply reducing the number of triangles for far-away terrain. Especially for mobile devices lacking hardware support.

---
Tags: opengl, displacement-mapping
---


# Question
Title: How does "Cut the Rope" do such realistic animation?
*"Cut the Rope"* is so smooth and real life like, while some apps are very "bitmap" like. How does *"Cut the Rope"* do such realistic animation?

# Answer
vectors are used in cut the rope. and the other games may be using bitmaps instead... like old school zelda.

Vectors you can have curve lines and such, where bitmaps are all squares. Vectors vs bitmaps
> 6 votes

---
Tags: animation
---


title: Generating a town layout in a grid

text:
# Question
Title: Generating a town layout in a grid
I want to generate a town layout in a square grid (rendered isometrically, but that doesn't matter) using the following elements:

* 2x2 Houses
* Roads, 1 unit wide
* Canals, 1 unit wide

Sample layout:

* I always have a specific number of houses, and as many roads and canals as necessary to connect them all.
* The houses need to have two pieces of road in front of their front door (which is always pointing to the right)
* It would be nice to have fields of grass (emptiness) inbetween.

Is there a ready-made algorithm for this? If not, what direction should I be thinking of to implement this?

# Answer
There are many ways to go depending on exactly how you want it. Here is a rough outline of one way which I think will fit your description:

First generate the canals. Then start placing houses randomly, for each house you place, place the road in front of it and draw a road from that piece to the existing road network, if either is not possible or placing the road in front results in an ugly 2x2 block of road reposition the house. Detect some road points that are close to each other but far apart following the existing roads and try to make some shortcuts for those.

This kind of stuff most of all takes experimentation and experience. Often you'll get good results from making some detail in a random fashion, determine if it meets some criteria and undo and retry if it doesn't.

For this exact task you will certainly also need a good grasp of basic pathfinding, unless you are already an expert, go read on the topic. And remember, pathfinding doesn't have to be just about the shortest path, for the last part of my description you might want to give some weight to reusing paths that are already there.

This is not at all an easy task, if you get stuck come back and show us your code and some example output and explain in detail how you would like it to be different.
> 8 votes

---
Tags: procedural-generation, isometric, grid
---


title: Finding the point of collision

text:
# Question
Title: Finding the point of collision
I'm writing a 2D rigid body simulator. The objects being simulated are convex polygons. My question involves how to decide on the "point" of collision, so that when I apply a response force, I can also calculate torque.

In 2D, the popular method of narrowphase collision detection seems to be the Separating Axis Theorem. However, while this gives you the "are they colliding?" as well as "by how much?", it does NOT give you a reference point (that I'm aware of) at which to apply the response force (and thus calculate torque)\*.

The other method (which also interests me more, because it's what's used in 3D, which would be the logical next step) is to calculate the Minkowski difference of the two polygons, and decide that they're colliding if (0,0) is contained in the resulting polygon. But, how do you use this to decide the relative point at which to apply the response force? My hypothesis is that, since each face of this difference effectively corresponds to a face of one of the polygons, the separation distance is the shortest distance from (0,0) to the MD, and you apply this to the corresponding face on the polygon.

As a bonus, how does one do this in 3D?

\*As I'm writing this, I just realized that, when using SAT, I could just keep track of which points are overlapping, and apply the force at the "average" of those points. But I would have to decide on which of the several non-separating axes to perform this little trick...

# Answer
> 6 votes
The keywords you're looking for are *"support points"* and *"manifold"*.

Erin Catto has written an excellent 2D physics engine. He regularly presents at GDC. You should be able to find some of his slides where he explains collision manifolds. The first version of his physics engine only supported box shapes to simply calculating the support points. Which is where the engine got its name Box2D.

The answer is too complex to describe fully here but the overview is you need to pick a total of 2 points from the two shapes. Then apply the restitution force equally to each. You'll also have to deal with a corner case where it's better to only use one support point.

---
Tags: collision-detection, physics, physics-engine, simulations
---


# Question
Title: Using XML in XNA to display maths questions which are associated with objects
I've got a snake game with three objects: apple, pear & orange. I would like these to be associated with questions which I'm trying to create in XML. This is what I've done so far...

```
<?xml version="1.0" encoding="utf-8" ?>
<XnaContent>
<Asset Type="System.Collections.Generic.List[System.String]">

<MathsQuiz>

<Question Value ="What is 3 x 3? Orange = 9, Pear = 10, Apple = 12" Right ="orange">
    <answer Value ="orange"/>
    <answer Value ="pear"/>
    <answer Value ="apple"/>
  </Question>

</MathsQuiz>
</Asset>
</XnaContent>

```

I'm getting the error: "Error There was an error while deserializing intermediate XML. 'Element' is an invalid XmlNodeType. Line 7, position 6."

I'm guessing it's because of the line MathsQuiz but not sure.

Any help is much appreciated!

Thanks, Tom

# Answer
> 1 votes
Much like this question, **you cannot simply *make up* the XML format!**

You have to use a format which matches the objects you will be deserializing!

Just as in my answer to that question, you can simply create some of your objects, serialize them, and see what they *should* look like in XML such that they can be deserialized. For example:

```
var sb = new StringBuilder();
using(XmlWriter writer = XmlWriter.Create(sb))
{
    IntermediateSerializer.Serialize(writer, theRootObjectYouAreSerializing, null);
}
Console.Write(sb.ToString());

```

So in your case, if your question structure looks like this:

```
struct Question
{
    public string question;
    public string correct;
    public List<string> answers;
}

```

Then your XML will look something like this:

```
<?xml version="1.0" encoding="utf-8"?>
<XnaContent>
<Asset Type="MyNamespace.Question">
    <question>What is 3 x 3? Orange = 9, Pear = 10, Apple = 12</question>
    <correct>orange</correct>
    <answers>
        <Item>orange</Item>
        <Item>pear</Item>
        <Item>apple</Item>
    </answers>
</Asset>
</XnaContent>

```

---
Tags: xna, xml
---


# Question
Title: Text-based game using JavaScript and/or PHP
I'd like to make a simple text-based game using either JavaScript or PHP. Ideally I'd like to be able to render ASCII text in a kind of blackscreen "console" style (think console roguelikes such as Crawl or Nethack, or old Infocom text adventure games). The game would be simple, mostly text entry and menu choices.

Is this easily done using JS or PHP; if so, could you give me some pointers, and if not, what could I use to have this kind of game running from a browser rather than an executeable?

# Answer
You could build the entire game in JavaScript for sure. Be aware that the source-code will be visible to the user. So if you're concerned about cheating (probably a non-issue if it's just a single-player game), then you should have your game logic on the server.

JavaScript and PHP is definitely going to work.

If I were creating such a game, I would do the following:

* Use a robust JavaScript framework like jQuery or Mootools for the client.
* Write the game logic in PHP. This could be plain PHP, but a framework like Zend, Saphire or Symfony can speed up development of complex projects quite a bit.
* Try to have your game-quests and items in data-files or a database to facilitate updates to your game-world. Avoid having your data in your code.
* Start with simple page-requests for testing, then move to asynchronous requests (AJAX) for a nicer user-experience.
* Always start with the most simple input method possible. A form field and a *send* button should be sufficient to start sending some user-input to the server. You can implement more sophisticated methods in your client as soon as the basic communication works.
* Don't trust the user input! Always validate/sanitize data coming from the client.
> 10 votes

# Answer
On top of bummzack's answer, which is pretty well fleshed out, I would give you one bit of advice.

Before you get into animating, make sure your PHP is solid. One good way of testing is to have several buttons on the page for your various actions, and use them with a simple POST call.

If you can nail down your game processing logic, then animating it should be a simple step forward. But, debugging AJAX requests can certainly be a headache if you're not careful.
> 2 votes

# Answer
This is very much possible in javascript, you can also load your preferred console font from an `.ttf` or `.otf` file.
> 1 votes

# Answer
Yep, should be pretty easy to do in HTML/JavaScript. Take a pre block and style it as you see fit. For input you should probably ditch text input fields and just use the key events.
> 0 votes

---
Tags: javascript, php, text-based
---


# Question
Title: How to model irregular boundary of a 2D map in Game?
I am creating a map in a game, the map contains different countries, my question:

Q. How to model the irregular boundary of each countries? How to do quick country searching if I click on the map (given x,y values)?

# Answer
The simplest way I can think of to do this is make the map into a finite grid or into an image and assign each location an enumerated value (or color). Each country would be a separate value on the map. Then given any xy index or coordinate you could quickly find out the country's value and look up its name in a table.
> 3 votes

# Answer
The question is a bit vague, but, assuming you want to generate some irregular boundaried countries with a quick lookup function, here goes:

Take a very simple country lookup, I'm assuming you have some kind of capital city at the centre, assign the city a strength, then use an adjusted voronoi style map to produce the regular shaped country border map. that gets you something like this:

https://i.stack.imgur.com/0BUbU.jpg

now, for the irregular borders, look at how perlin noise is used to offset into a different texture:

Perlin Noise

this should provide you with a quick way to generate the clean coordinates from the world coordinates. That then should provide you with a rough edged country map.
> 1 votes

# Answer
This depends entirely on your input data.

If all you have is a bitmap, then you'll need some bitmap data. You could paint a parallel image to your game map, but with block colors where the countries are. You'd want the image painted palletized, with each color representing a country. At runtime, load it uncompressed and trivially look up which color, and thus which country is under any given pixel by mapping your pick ray onto the image. If you're just displaying in 2D, it should be easy to map the screen coordinates to the map coordinates. This is a nice fast array lookup, and should be easy to author side by side with the visual map.

If you want to save some memory, it's highly likely that you could quarter this image and still have enough fidelity to feel precise picking countries near borders.

If you're modeling geometry for your countries, say you're making a nice 3D map, then you could just feed each country into a collision library like http://bulletphysics.org/ and just build a pick ray from the camera and collide it with the resulting optimized shapes. Which shape gets picked tells you which country was hit. It's highly likely that this would be fast enough for you, and again it would be easy to author side by side with your visual data.
> 1 votes

# Answer
Without knowing any further constraints, I'd prefer using a BSP to find out which point of (2D) space belongs to which object. This works even with the country borders overlapping (simulating conflicts about the exact borders) or not filling out all the available space (simulating no-man's land and areas outside of the map's chosen projection).
> 0 votes

# Answer
### use anchor points

This can be done exactly with using the collision detection from a physics engine and triangulated country shapes. However, I think the results will require lots of work that will be ultimately unsatisfactory.

You're best bet is to hand tune some anchor points. The basic idea is you place anchor points on the map. On user click find the anchor point that is the closest. That is the country you just selected.

Tips:

* add some null anchor points for areas that don't make sense to click.
This avoids surprising the user when the accidentally click on an ocean and suddenly select a country hundreds of miles away.I think you best shot will be to hand tune.
* The anchor points don't need to be fair.
Luxemburg would be very difficult to select. Adding some luxemburg anchor points into its neighboring countries will result in a better user experience.
> 0 votes

---
Tags: algorithm, maps
---


# Question
Title: How do I replicate the warp effect from Geometry Wars?
I'm trying to achieve the warp effect that you see in games like *Geometry Wars*.

Can someone help explain what is going on here? I feel like the grid's z axis is manipulated in some way, any way, by the programmer, but is there maybe some known mathematical equation to really get the correct warping effect?

Edit: To be more specific, I mean the warping of the grid. How everything looks pulled towards the negative z axis and then bounces.

# Answer
> 11 votes
A 10-minute implementation of a simple spring system (or so he says on his blog ;) ). The system can handle multiple warps and other things distorting the grid.

Updated to add some minor addition detail:

A few other details. From an interview that used to be hosted on the Bizarre Creations website (that site has now disappeared due to the company closure) there was a question:

**Q: One of the most striking new graphical features in the game is the "gravity grid" play area. How did you make this look so cool; does every object in the game really have its own gravity?** The grid itself is made up of 60,000 points, each one exerting a small amount of force on its neighbour. The simulation itself sits on the edge of stability which is what causes it to swing about so much when one of the game objects gives it a small push! Only a few types of object affect the grid. As the grid system is rather expensive to calculate, it actually runs on the second core along with the audio system, (the first core being dedicated to gameplay and particles, the third is used to render the audio).

# Answer
> 1 votes
I don't know if there's a "correct" way to do it, but it's likely just an aesthetically pleasing linear transform applied with a falloff calculated from distance to a point.

So for any element you're working with, you'd:

* find the distance to the center of the warp (d)
* calculate 1 - d / the max distance of the effect you'd like (i for intensity)
* clamp that to \[0-1\]
* transform the element by lerp( identity, transform, i )

Iirc, Geometry wars applied that as a distorting warp to some elements, while other elements like particles were just affected by the "force", without being distorted. You could apply the distortion in a vertex shader, assuming you had enough vertices to smoothly sample the effect. Alternatively you could render everything that needs affecting to an offscreen buffer first, and then render the results onto a nicely tessellated quad that you apply the distortion to, before adding all the non distorted elements on top.

As for the transform, scaling will give you the sucking in look. If I remember correctly, there was also some twisting going on, which would just be a little rotation.

You can get fancier and fancier with your calculations of the intensity factor to get wackier looking effects. You could, for instance, calculate the angle (a) that an element is relative to the center, and factor that in. Take cos(a) and you can make radial waves in the effect. What you want to do is set yourself up with the necessary scaffolding code and then go to town experimenting with different combinations of factors.

---
Tags: graphics, graphic-effects
---


title: When should vector/list be used?

text:
# Question
Title: When should vector/list be used?
I can understand when to use lists, but I don't understand when it is better to use vectors than using lists in video games: when it is better to have fast random access ?

(And I understand why it's faster to insert/delete in lists because it just removes/adds pointers, but it still has to find the corresponding item...)

# Answer
My rule of thumb, and I'm sure there will be debate on this, is to *never* use lists (unless you need to very, very frequently remove things from the middle of large lists).

The speed you'll gain by having all your elements in your container in contiguous memory (and therefore more cache-friendly) is worth the offset of the additional costs of adding/removing/resizing the vector.

Edit: Just to clarify a bit more, of course it should go without saying that any kind of "which is faster" question should be tested on whatever platform with whatever data sets are pertinent to your particular needs. If I just need a collection of elements I just use vector (or deque, which is almost the same thing) unless there's a good reason *not* to.
> 29 votes

# Answer
Use a list when iterator invalidation caused by modifying the middle of your data structure is going to cause a problem, or you need to keep your elements sorted so the swap and pop trick for quick middle collection deletes won't work and you have a large number of mid collection deletes.

You may also want to consider using a Deque. It has similar performance characteristics to a vector but doesn't have vector's need for contiguous memory, and is a little more flexable.
> 8 votes

# Answer
Your choice should reflect your needs. All the elements of the vectors are continous in memory and lists has pointers to next / previous elements so they each have their advantage / disavantages :

Lists :

* Each elements takes 2 integers to point previous and next elements, so most commonly, that's 8 bytes more for each elements in your list
* Insert is linear in time : O(n)
* Remove is a constant operation : O(1)
* Access the x element is linear in time : O(n)

Vectors :

* Needs less memory (no pointers to other elements, it's a simple math algorithm)
* Remove is linear in time : O(n)
* Access the x element is constant : O(1) (That's because the elements are continious in memory so it's a simple math operation vectorPtr + ( x * bytesOfTheType ) )
* Insert can be in linear time, but most commonly, it's a constant operation : O(1) (That's because the vector in an array but always reserve 2 times it's capacity when the array is full so array copy is not frequent )

So list is better when you program needs to add and remove elements frequently, but never access (or rarely access) a particular element without the need of the others before. The vector should be used for better access time, but lacks effeciency when you need to remove or add elements.

Check this post on stackoverflow, it present a really nice graph with basic questions on your needs that drives you to a specific container depending on your answers :

https://stackoverflow.com/questions/366432/extending-stdlist
> 4 votes

# Answer
Usually lists are used for structures like queues where there are lots of append and remove operations. **Example:** An ever changing list of entities that should be updated. The list itself only contains entities on screen and therefore changes frequently.

Vectors (or arrays) are better suited for a collection that doesn't change that much and where you need fast access to individual items within the collection. **Example:** A tile-map where you have to lookup tiles at a given index.

Tetrads opinion might be true, but it depends on the programming language that is used. I see that you tagged your question `c++`, but I tried to give an answer that isn't language-specific.
> 2 votes

# Answer
In console games we never, ever use std::list because:

1. it does memory allocations whenever you add a new item. memory allocations are slow.
2. it's full of pointers. pointers are bad. a pointer is a cache miss. a cache miss is bad.

even std::vector is losing favor on consoles because:

1. you often care only about, for example, the positions of all the objects. like for example you want to collide the objects with each other, in which case you don't care what their color is. so you want all the positions to be contiguous in memory and you want the colors to be somewhere else far away, to avoid polluting the cache. but std::vector requires you to store everything for each object in a contiguous chunk of memory (e.g. position then color.) so if you do work that reads only the positions, you need to read all the colors into the cache too, even if you don't use them. this is wasteful.
> 0 votes

---
Tags: c++, algorithm, data-structure
---


# Question
Title: Determing an object's position along a curve over time
I have some objects in my game which are "thrown". At the moment I am trying to implement this by having these objects follow a parabolic curve. I know the start point, the end point, the vertex and the speed of the object.

1. How can I determine at any given time or frame what the x & y co-ordinates are?
2. Is a parabolic curve even the right curve to be using?

# Answer
What your looking for a parametric plot of the parabolic function. It's easiest to make the parametric function use a range of p ∈ \[0,1\].

The canonical form for a parametric parabola is

> k := some constant
> f\_x(p) = 2kp
> f\_y(p) = kp²

Using this formula and some basic algebra for function morphing and I got

> p ∈ \[0,1\] → x,y ∈ \[0,1\]
> or in other words keep p between 0 and 1 and x,y will be between 0 and 1 as well.
> x = p
> y = 4p - 4p²

So to get these functions will produce the numbers you're looking for.

```
float total_time = 2;
float x_min = 0;
float x_max = 480;
float y_min = 0;
float y_max = 320;

float f_x( float time )
{
   float p = time/total_time;
   return x_min + (x_max-x_min)*p;
}

float f_y( float time )
{
   float p = time/total_time;
   return y_min + (y_max-y_min)*(4*p-4*p*p);
}

```
> 4 votes

# Answer
Finding the equation of a curve that you want your object to move along is one way to accomplish what you want, but probably not the best.

Instead, one usually keeps track of local properties of an object (velocity, acceleration) and then uses these values to update the object's position every frame.

Since you mentioned a parabola I am assuming that you are throwing a ball in 2D and you want it to fall down along the y-axis. So, your object has constant acceleration in the y-direction (let's call that `g`) and no acceleration in the x-direction. When the object is thrown it is given some velocity, let's call that `vx` and `vy`.

Then, every frame of your application you would add the object's acceleration to its velocity, and then add it's velocity to it's position. Something like:

```
vy += g;
x += vx;
y += vy;

```

Do this every frame and your ball will start to move. There is a lot more to know about this, but it's a start.
> 4 votes

# Answer
Brandon's answer is pretty good, but if you're looking for something more advanced, you might want to check out linear interpolation: http://en.wikipedia.org/wiki/Linear\_interpolation

Also, if your curve is a function, you can know the x and y (and z) coords at a given time. This might help too: http://www.ucl.ac.uk/Mathematics/geomath/level2/fvec/fv8.html#l1
> 2 votes

# Answer
In console games we often use Bicubic Interpolation to solve this problem. First, sample an object's position at regular intervals of time t. For a projectile, add gravitational acceleration \[0,dy/dt/dt\] to its velocity \[dx/dt,dy/dt\] at each interval. Record all the \[x,y\] coordinates so generated in an array.

Later, to reconstruct the object's position \[x,y\] for a given t, read the four samples closest to that t from the buffer you recorded: \[t-1,t,t+1,t+2\]. Blend the four samples according to the coefficients in the linked wikipedia article to get smooth motion in space.

This is not as physically accurate as performing physics calculations on-the-fly but it permits artistic license and economy of scale to assist your simulation.
> 0 votes

---
Tags: physics, projectile-physics
---


title: Basic Box2D collision detection

text:
# Question
Title: Basic Box2D collision detection
I don't understand how to listen for collisions in Cocos2D/Box2D. Say I have two dynamic circle bodies. One is very small and the other is relatively large. When the small circle collides w/ the large circle I'd like to do something (play a sound for example). What's the best way to do this?

I'm currently experimenting w/ the TestPoint method. Something like:

```
if(largeCircleBody->GetFixtureList()->TestPoint(smallCirclePoint)){
    // collision happened...
    // play sound etc
}

```

# Answer
> 9 votes
You use b2ContactListener

http://www.box2d.org/manual.html#\_Toc258082975

http://www.emanueleferonato.com/2008/12/23/understanding-how-box2d-manages-collisions/

---
Tags: physics, box2d, cocos2d-iphone
---


# Question
Title: Adding a simple mix() destroys the framerate
I have a very simple shader and added linear fog via mix like this:

```
finalColor = mix(finalColor, vec3(0.5, 0.8, 0.95), vUVoutAndViewZ.z);

```

Note that the view Z distance is in the variable that also contains the UV coordinates, so the fog didn't even add a new interpolator.

Still, this one innocuous line brought the framerate on the OG Droid with the Power SGX chipset from 33fps to 22fps. Even the HTC Evo with the Adreno 200 GPU stays under 30fps. (The Adreno 205 is at a constant 60fps, but that thing is a beast).

The fragment shader itself is primitive (all values are hard-coded since it's a test shader):

```
precision mediump float;
varying mediump vec3 vUVoutAndViewZ;
varying lowp vec3 vNormalOut;

uniform lowp sampler2D diffuse;

void main() {
    lowp vec3 normal = vNormalOut;

    // Lighting
    lowp vec3 lightDir = vec3(0.5, 0.3, 0.5);
    lowp vec3 light = vec3(dot(normal, lightDir));

    lowp vec3 diffuse = texture2D(diffuse, vUVoutAndViewZ.xy).rgb;

    lowp vec3 finalColor = diffuse * light;

    // Fog
    finalColor = mix(finalColor, vec3(0.5, 0.8, 0.95), vUVoutAndViewZ.z);

    gl_FragColor = vec4(finalColor.xyz, 1.0);
}

```

I added the lowp/mediump declarations later (which added about 2fps), it works just as bad without them.

I refuse to believe that the PowerVR chipset is so weak that it can't handle a simple shader like this. There must be something stupid in this shader (like something implicitly swizzling a lowp register) that just completely messes up the unit.

**ANSWER and EDIT:**

Ellis has some fantastic information in the answer and the subsequent comments. In this particular case, it seems that mix() is flat-out broken. It brought the shader to 12 cycles (from 4) and 4 GPRs (from 2). I got back to 29fps by using this code instead:

```
lowp vec3 fogDiff = vec3(0.5, 0.8, 0.95) - finalColor;
fogDiff *= vUVoutAndViewZ.z;
finalColor += fogDiff;

```

# Answer
**Response from EboMike computed with PVRUniSCo Editor: mix() brings the shader from 4 cycles to 12 cycles** (PowerVR).

The PowerVR 530/535 is very slow. Andreno 200 and PowerVR 530/535 are first GPU generation (OpenGL ES 2.x) for hdpi resolution. You can't redraw a full screen at 60FPS with a simple texture.

I wrote GPUBench to test shaders performance and it is very bad on these GPU. The second generation (Andreno 205, Powervr 540) is far better.

Today, i try to minimize Fragment shader with one or two operations. You can try to optimize your shader because GLSL compilers are bad (on mobile platform).

Note: for powervr gpu, read this document. PVRUniSCo Editor can compute cycles used in shaders.

My toughts:

* The Droid GPU is slower than Andreno 200 because of fillrate
* 30 FPS for Andreno 200 is good
* 20 FPS for Droid is good
* You can render your scene in a smaller FBO and draw it on a screen (but FBO switch is costly)
* Fragment shaders must be very short.
> 6 votes

---
Tags: android, opengl-es, shaders, performance
---


# Question
Title: Looking for online resources to understand game camera properties
What are some good online resources to understand game camera properties, such as fov, aspect-ratio and more?

# Answer
it's not too complete and exaustive but maybe this could help: http://aoeu.snth.net/?p=43
> 2 votes

---
Tags: camera
---


title: Need an engine for MMO mockup

text:
# Question
Title: Need an engine for MMO mockup
What I *don't* need is an MMORPG engine, at the moment.

What I *do* need is a flexible easy-to-use engine that I can make a mock-up with. I don't need support for more than 10 players in an instance, so any multiplayer platform is probably fine.

I need an engine with which I can create the following core features:

* Waves of simple AI enemies that have specific objectives (move to point A, destroy target, move to point B). The units present can be between 50-200 in number.
* An over-the-shoulder view and the ability to control a team of 3 (like Mass Effect or the latest Dragon Age)
* Functioning inventory system

Right now, all I can really think of is Unreal or Source. Any other suggestions? Again, this is a proving mock-up, not an actual MMO.

I'm not terribly worried about the visual aspects as we just want to test mechanics.

*Note: Can write some scripts in Python, Ruby, or Lua, if necessary.*

# Answer
I know you said you don't want a full-fledged MMORPG, but I can't think of something that will fit your bill without being big...

Here is a modern MMORPG, open sourced, including assets: Ryzom. It should provide a good starting point for any open world multiplayer game.
> 6 votes

# Answer
Unity \- It will allow you quickly prototype what you're after. It has networking support, you can add flexible scripts to it to create your gameplay mechanics and it's got a lot of support and resources.
> 5 votes

# Answer
Your best bet is probably to mod an existing game. Some people are even modding Starcraft 2 to an MMO, but that looks like a lot more work than modding a game that already has some RPG features.

There's an active modding community for Diablo 2, so this might be a starting point?

I'm making this answer CW, because I'm not a modding expert and somebody might add some better suggestions for easy moddable RPGs or MMOs.
> 1 votes

# Answer
About the only thing that will be this high-level is a tool like RPGMaker. Honestly if you just want to test it, mock something out in a top-down view using blue and red boxes or something.
> 0 votes

---
Tags: mmo
---


# Question
Title: Fbx animation without bones or single skeleton
SkinnedModel sample nicely shows how to import single root bone skeleton and run in XNA.

My question are:

1. Is it possible to have animations played in XNA if there no bones are used in model (which can easily be done in 3dmax with auto key frames)?
2. Is it possible to have multiple independent bones laying around, connected to independent meshes and animated, all played in XNA?
3. Can SkinnedModelProcessor be downgraded to this level ?

# Answer
> 0 votes
Maybe you should look at XNAnimation, it extends on the original samples to provide a more comprehensive set of animation possibilities.

Beware though, it was discontinued at some point, although it's now looking active again. Somebody took it up to port it to the SunBurn rendering engine: sgMotion.

# Answer
> 1 votes
In Max, you can actually asign a mesh a single bone, that has rigidly asigned or linked a mesh or vertices, and animate bone's traslations/rotations (or use dummies). Using auto keyframe or not. The mesh will follow it, as is linked. I guess later on importing the skinned mesh into XNA will treat it like always, it would see no difference, but you actually handled them as if were moving just static meshes, in Max. If there can be two skinned meshes at a time in xna, then you should be able to do this, and with more than two.

---
Tags: xna, models
---


# Question
Title: Where can I find sales figures for PSN Minis?
I work for a small game studio that develops games for iOS and Android currently. The engine we are building will be portable and our upcoming game is quite ambitious. Therefore we are considering porting it to PSP also, making it available at the PSN as a mini. I have been searching for days now but I am having trouble finding any numbers of what an average PSN mini game can sell. What a hit or a bad game could sell is also really interesting. As we are trying to calculate if it is worth going into this market any clue would be helpful!

# Answer
If you're seriously considering this I'd speak to Sony directly. Sales numbers are usually considered commercially sensitive, not only between competing game developers/publishers but between different platform holders. As a developer Sony would probably be prepared to provide you with generalisations on some of the numbers for what you could reasonably expect.
> 4 votes

---
Tags: business, sales
---


# Question
Title: Does it require any license to use a real city landscape in a car racing game?
I'm now planning a casual car racing game that want to model some real cities sight into it. I doubt if there is copyright of the landscape or city planning of those real cities in the world. Can I model such as existing city or I can't?

Thanks a lot.

# Answer
You can use OpenStreetMap.org \- their license is clear and suitable:

> You are free to copy, distribute, transmit and adapt our maps and data, as long as you credit OpenStreetMap and its contributors.

osm2xp is for example using this data for the X-Plane game:
> 8 votes

# Answer
It depends on the level of detail you go into and how you generate your data. From Will's post, deriving your layout from OSM does seem to be a way of doing this to an extent, however if you derive anything from any other source you'll need to carefully check their licences very carefully.

There may be certain buildings or objects in real cities or locations that would require a specific licence to use (from past experience we've had to remove the odd distinct building that either didn't want to appear or had a ridiculously high licence fee), if you planned to try and actually use the real shops or corporate logo's of buildings you'd potentially have to obtain a licence for each one individually (this may vary depending on the country you're recreating).

As an example, take the Hollywood sign, if you wanted to put that in a game you'd need to specifically obtain a licence for it here.

As with all things legal, if in doubt, ask a lawyer who has some experience in this area.
> 10 votes

---
Tags: copyright, racing
---


# Question
Title: How can I get my meshes to work with Bullet Physics?
The problem is that I'm trying to use my meshes with Bullet Physics for the collision part of my game.

When I attempted doing this method with my GLM(model loading library by nate robins) model, I get a segmentation fault in the debug, so I figured that it doesnt like the coordinate variables of the model.

If i use blender to export my model as a collision file, what type of file should I use?

I have heard of a .bullet exporter, but i dont know hot to integrate this python script into my Blender 2.5 program.

# Answer
If it's segfaulting there's a bug in the library. Open a bug report and send them a reproducible test case.
> 1 votes

---
Tags: opengl, c++, blender, bullet-physics
---


# Question
Title: Facebook Game Development - Where can I save my data?
I'd like to develop a small Facebook game with some graphics involved (not that many). Within that game, the users will be able to buy/sell certain items and I wonder WHERE I can save those items/virtual money...? Does Facebook offer me a database I can use?

# Answer
> 4 votes
Depending on what sort of game you are trying to make, you will need some place to put the actual game.

A Facebook App points to external websites for the canvas part of the application. This is your own webserver/webhotel and what ever language your webserver uses ought to provide you with some database connectivity.

So if you eg. use PHP on the server, MySQL might be the datasstorage. If you have a IIS/ASP/ASP.net server available, SQL-Express could be your answer. But with most server-side languages you can also remotely connect through IP to another database server somewhere else.

You can also use API's to connect to webservices that allows you to put/get data from their storage. Some are SQL, some are Table and some are XML based, but if you have basic CRUDL functionality at them, you dont have to care about how they do it.

Amazon AWS has something called SimpleDB which is a XML kinda storage. It has a great API too, but again, it all depends on your needs, economics and technical skills for implementing this.

If you use Flash for a client, then you have the issue of how to communicate with a server to get the data in and out from the client. For this you also need the server-side "something" that can serve your data as needed and receive "POST" data from the Flash-client.

So once you have a server, you know where you can put your data.

To my knowledge, Facebook does currently NOT support native data-storage, but perhaps others can elaborate on this subject.

# Answer
> 3 votes
Google App Engine and AWS Simple Db would be a good starting point. They include some superb sample client code to get you going.

# Answer
> 2 votes
You need to provide your own server for hosting your database. Google App Engine is free to start using but kind of tricky because the database is Google's Big Table rather than SQL.

So the option I recommend is Kodingen: http://kodingen.com/

---
Tags: facebook
---


# Question
Title: AI controlled monster vs player controlled monster stats
Does anyone know if in a pokemon game does the wild pokemon have the same stats when you catch it as it did in that battle?

and to make this a more programming question ... In that type of game should the "wild" enemies have the same limits imposed on them as if they were player controlled or should the enemies be stronger that if you caught them.

This question assumes that the creature is the same level in both cases.

# Answer
For balancing there is only one true answer, experiment. I don't know exactly what the different Pokemon games do, it may be different from game to game, but it seems very likely that there is a difference, as it would otherwise be quite limited what tools one have for fine tuning the difficulty.
> 0 votes

---
Tags: game-design, balance, statistics
---


title: Design suggestions for my Entity module

text:
# Question
Title: Design suggestions for my Entity module
I need some advice on how to design the Entity module in my game, how to apply the MVC pattern and generally how the Entity should interact with its controller and its representation.

First some details about the game: it's a 2D action-platformer, it's data-driven (or rather, I'd like it to be data-driven — it isn't yet) and the Entities should be scriptable (I'll be using Python).

I'm still at the very beginning of the development and I have some general ideas about how the Entity module should work, but I get stuck on the details. Here's roughly what I have up until now:

```
class Entity
{
  private:
    // The representation holds the actual animation and sounds that
    // are used to render the entity. The representation can read the
    // Entity's state but it cannot alter it.
    EntityRepresentation* representation_;

    // The controller handles events and changes the Entity's state
    // based on these events.
    EntityController* controller_;

    // Here's some of Entity's attributes
    struct Vector{ float x, y; } position_;
    float directionRadians_;
    float speed_;

  public:
    void handleEvent(const Event& e) {
        controller_->handleEvent(e, this); // It's obvious what it does :)

        // The representation needs to handle events so it can change the
        // current animation, queue up a sound for playing, etc. In my
        // current setup it doesn't yet need to take 'this' as a parameter.
        representation_->handleEvent(e);
    }

    void update(unsigned long timePassed) {
        position_.x += speed_ * timePassed * std::cos(directionRadians_);
        position_.y += speed_ * timePassed * std::sin(directionRadians_);
        // .. And any other updates I might need to do...
    }

    void render(DrawingContext* context, unsigned long timePassed) {
        representation_->render(context, timePassed, position_.x, position_.y);
    }
};

```

There are a few things I think could be problematic in this setup. For one, if you look at the `Entity::handleEvent()` function you will see that the Entity forwards the event to the controller *as well as to the representation*. The controller uses the event to alter the state of the Entity; the representation however uses it to alter its own state (to use some other animation, to decide whether it should play a sound, etc.).

This means the representation has a state of its own which is characteristic to this Entity only. Do you think it's bad that each representation can only be used for one Entity? (Note: this does not mean that in case there are two entities using the same sprite, that sprite is loaded twice in memory: the sprite itself is a common resource.)

Another thing I'm having problems with the deciding how to organize the actual entity data on disk. Where should the bounding box info be read from: the animation or somewhere separate? should there be a single animation file for each character? should scripts be separate from the data or should everything related to one type of entity be stored in a single folder (scripts and animation and sounds)?

---

**tl;dr** Can you give some some general advice on how the Entity should interact with its controller and its representation (i.e. sprites and sounds). Also, do you have any advice on how the data itself should be organized on the hard-drive?

# Answer
(My tl;dr -\> Just make a friggin' game!)

For the MVC part of your question, have you read through this question?

I think keeping a 1-to-1 relationship between Entity and EntityRepresentation is the right choice. The things you'll want to share across multiple entities can be referred to in the Representation or Controller (like the Sprite loaded in memory as you discussed). This way, you are able to make per-instance changes to the Entity.

Say you added the option in EntityRepresentation to apply special effects, like a colored glow. If you shared one EntityRepresentation instance among multiple Entity instances, you wouldn't be able to choose one specific Entity instance to add the glow effect to.

Have you written your EntityRepresentation class? Something to think about is cases where you want image and sound vs image but no sound vs sound but no image.

My train of thought regarding that is:

* Okay, have different subclasses of EntityRepresentation to represent each.
* Except that's wasteful performance-wise, just give EntityRepresentation two pointers to an Audio and Visual representation respectvely Easier/faster to check NULL than to have another virtual call and making your inheritance chain deeper.
* But then that leads me to the conclusion, why even bother having EntityRepresentation? just have an AudioRepresentation and VisualRepresentation in the Entity class and do the null checking in Entity. It's just one additional handle\_event call.

As for file organization, I don't think it makes a significant difference so long as you keep it organized. I personally prefer to keep (for example) images and scripts in separate folders even if they are associated with the same type of entity. I do keep a similar subdirectory hierarchy in both the images and scripts folder though.

ie:

* `images/Enemies/Vogon/Vogon_idle.png` and `images/Enemies/Vogon/Vogon_walk.png`
* `scripts/Enemies/Vogon_config.py` and `scripts/Enemies/Vogon_AI.py`

There is a miniscule workflow benefit for having all `Vogon` related files in one folder in that you don't have to keep multiple file browser windows open. But this is a really trivial difference.

A lot of this stuff is really trivial. Just keep making the game and go with your gut instinct on organization and the Entity class structure. I like your current layout of the Entity class. Work with it and then make some decisions. You'll be better informed about your style of programming and about the game you want to make after you actually start trying to make this game. Starting with separating the representation as you are now will give you enough wiggle room to change things up later down the line.
> 3 votes

---
Tags: entity-system
---


# Question
Title: Information on seamless MMO server architecture
I'm looking for any material on seamless MMO servers! I do have a few articles in the "Massively Multiplayer Game Development" books and "Game Programming Gems 5." Has anyone experience on that topic or knows articles about that?

I'm interested in "high-level views" as well as implementations. This might become the topic of my master thesis and I would like to find out how hard it is to write such a system, before I actually start the thesis. Right now I haven't decided which language to use, I'm thinking about Java or Scala. Erlang could be a choice, but I've never worked with that.

Note: Basic requirement would be movement. Any other gamesystems are optional and give "bonus credit."

Now for what I mean with "seamless server": I want so set up a server cluster where every node controls some part of the game world, with static boundaries. Players can now move from one end of the world to the other without switching an instance or hitting some "teleporter". I think WoW does that. In my back-end however the player transitions from one server to the next.

# Answer
> I'm interested in "high-level views" as well as implementations.

Implementations are generally reasonably deeply involved and you probably won't see much talk of them here. The StackExchange software isn't well-suited to that kind of involved discussion, not to mention it would involve a significant investment of somebody's time.

> I would like to find out how hard it is to write such a system

No more or less hard than any other system: it will depend on your requirements and the features you intend to drive. You can write trivial implementations trivially, but non-trivial stuff will of course be much harder. One of the bigger problems is that you probably won't have enough real clients to tell if your system actually scales to the "massive" level that WoW and other games operate on.

MMOs are not magical. Most of their technology is nothing special when taken in isolation, it's simply that a number of smaller, simpler bits of technology are combined very intelligently to allow for larger scale, connected parallel simulations of some shared world state.

> I want so set up a server cluster where every node controls some part of the game world, with static boundaries. Players can now move from one end of the world to the other without switching an instance or hitting some "teleporter".

Essentially what you're talking about is simulation hand-off. This can be done quite simply and isn't necessarily an MMO-specific technology (peer-to-peer games tend to support all the same underlying mechanisms to implement host migration). The basic premise is to have each server understand the topology of the servers "around" it (specifically, a server for world node A must know about the servers for simulation-adjacent world nodes) as well as to define a buffer around which you consider a particular simulated entity "close" to an adjacent server.

When an entity enters the "close" buffer, you start reporting it to the adjacent server as well. Once the entity crosses the actual threshold, you send a message to the adjacent server with the full state of the entity and a message indicating that the adjacent server should take over the entity. Obviously you want this to be as reliable as possible.
> 5 votes

# Answer
The main complexity in managing such a system comes from just how seamless you need it to be. As Josh has said, solving the problem handing off an entity from one server to another is a key part of the package.

This is not the only problem though - if entities across multiple servers need to interact as part of one operation you now have a synchronisation problem where each system needs data from the other side in order to proceed, but by the time that data arrives it may already be invalid. You can attempt to solve this by breaking the operation down into multiple messages with rollback capability if one side backs out, but as you've seen from Chapter 3.1 in "Massively Multiplayer Game Development", this *significantly* complicates any game logic that you have to do this with. Scala and Erlang help you get the messaging system right - they do not help you with the decomposition of what used to be a 10 line function into the many different messages and states you now need to track.

Obviously, this problem is not entirely new, and relational databases support this sort of problem by storing all the data centrally and letting multiple clients query and alter it as they need to, rolling back transactions where necessary. This gives you most of your correctness requirements but unfortunately imposes impractical performance problems as well as making game logic implementation awkward (since much of your logic is now written in database stored procedures). A different kind of database might provide a good solution here, especially if you're willing to trade away the reliability requirements that most RDBMSes provide.

Most professional games get around this problem by not even attempting it, by keeping the shard size small enough to put all players on one server, by splitting the world into parts that don't really interact (see the WoW example in the comments above), or by distributing the game across servers based on function rather than geography (eg. all combat happens on one server, all chat on another) so that there are no 'seams' to contend with.
> 5 votes

---
Tags: architecture, networking, mmo, server
---


title: How to apply shaders on primitives

text:
# Question
Title: How to apply shaders on primitives
There are tutorials about applying shaders to 3D models, but I would like to know how to use shaders on primitives. I have a world with a lot of vertices and I would like to apply a shader to it without adding any texture to it or loading any model. I'm working with XNA and HSLS.

# Answer
> 1 votes
All of the primitive stuff I've seen so far for XNA was actually building the object out of verts during run time and passing them in as a Triangle list of Vertexes (or VertexNormals if you want to do lighting stuff) You may wish to consider getting some basic shape models for traditional primitives.

That being said, the terrain in the current game I'm working on is all generated run-time with no models (though we do apply textures), and if you already have your verts set up and want to get them to draw into a shader, all you have to do is set up a VertexBuffer and an IndexBuffer, then set the Indicies and Vertices on your GraphicsDevice to each of them. After that, you use the GraphicsDevice's DrawIndexedPrimitives to draw the data you've buffered. Start an effect before you do so just like with a model and voila.

http://www.riemers.net/eng/Tutorials/XNA/Csharp/series1.php Has a good starting point for this as the terrain is generated from a heightmap instead of a model, and the lighting/coloring is done with normal/height data in hlsl.

*Warning: all of this is in regards to XNA 3.1*, I would imagine most of it would carry over to XNA 4.0 or be easily translatable, but there may be a better way in the current version.

Anyway, hope this helps!

---
Tags: xna
---


title: Math topics for 3D graphics programming

text:
# Question
Title: Math topics for 3D graphics programming
I understand that the following math topics are required for 3D graphics programming. I have started doing some of them in my math course. Can someone point me in the direction of a resource that explains **how** they apply? What graphics/game problems are they used to solve?

* vector math
* matrix math
* quaternions
* linear algebra

As far as I can see these are all linear algebra/matrix topics. Are there any other topics required?

# Answer
> 10 votes
Linear Algebra is the foremost discipline for 3d graphics programming simply *because* it's the mathematical language for describing spatial geometry. Your other three topics are really just subsets of linear algebra:

* Vectors are a way of thinking about points in space
* Matrices are ways of thinking about transformations of space and objects: translating objects, scaling them, etc.
* Quaternions are a natural representation for a specific subgroup of those transformations, the rotations
* etc, etc.

As far as other relevant pieces of mathematics for 3d graphics programming, the one I'd recommend that doesn't get nearly enough love is computational geometry. A lot of natural problems boil down to topics in computational geometry:

* One of the most natural ways of defining a volume from a set of points (for instance, to define an audio volume where a specific background noise will play, or a fog volume, or the like) is to find the *Convex Hull* of the points; there are good algorithms for doing that in 2 and 3 dimensions, but even the 2d algorithms aren't immediately obvious.
* The problem of being able to determine what objects are near a given point or are near each other (for instance, to reduce the number of objects that have to be checked for possible collisions, or to figure out which enemies will notice the players at a given point) gets into the field of *Geometric query* problems and to spatial partitioning schemes (and thus into structures like BSP trees and octrees). The same general ideas are also used to answer 'line tracing' queries (for instance, 'what does this laser beam hit?')

After that, I'd encourage looking into basic calculus and particularly numerical methods for differential equations; these are less relevant to 3d graphics per se than they are to 3d physics, but in general the two topics are pretty tightly coupled (even for simple problems of kinematics - for instance, for character animations and the like) and some knowledge of both will substantially enhance your knowledge of either; it's difficult if not impossible to work the relevant physics without the same core linear algebra knowledge as graphics uses, but at the same time having the physics knowledge provides another point of reference for understanding the topics in graphics.

# Answer
> 4 votes
Here's a great intro http://blog.wolfire.com/2009/07/linear-algebra-for-game-developers-part-2/

# Answer
> 3 votes
http://www.dickbaldwin.com/KjellTutorial/KjellVectorTutorialIndex.htm is a pretty good and straightforward tutorial about 2D/3D vector math AND it's applications on graphics programming.

# Answer
> 1 votes
If you are familiar with Cartesian coordinates, then the application of the above topics to computer graphics should be pretty clear. There are tutorials such as these for OpenGL that will help to clarify the application of math to solving basic display problems, e.g. how to make a wire-frame model appear to rotate. The Wikipedia article on perspective drawing might help with a bit of historical background.

Beyond that there are many display topics that benefit from mathematical formulation. For example, 3D solids are usually represented by triangulations of their surface. How do we show only that part of the surface that an observer "should" see (hidden surface/line algorithms)? If an object is to be illuminated from a particular source/direction, how does this interact with perspective to give a convincing surface rendering?

Beyond that there are all sorts of interesting modelling topics, such as animation of a mist or a flame. But the transformation of coordinates, as your list of topics seems to center on, is a staple of all later advances.

# Answer
> 1 votes
Practical Linear Algebra and Fundamentals of Computer Graphics are two very good books that will cover the topics you mention (and their use within computer graphics), if you're in to books and such.

# Answer
> 1 votes
They are not all required. Vector maths are all over 3D graphics, you might be able to set up the geometry without knowing the finer points of vector maths, but stuff like bump maps are going to get really hard, and you'll fall through on physics.

Quaternions simply offer a different description for some of the maths, it may be nice to have, but it's certainly not needed as more conventional mathematics suffice for describing any calculation you can do with quaternions.

Matrix maths and linear algebra are very closely related, most of all it describe linear operations on sets of numbers. But again, it's just another way of describing some things that could be described with vectors and algebra.

I don't know if you consider it to be just a part of basic maths, but trigonometry certainly needs to make the list as well.

---
Tags: 3d, mathematics, matrix, linear-algebra, quaternion
---