Imposters are a must for any game or demo with large draw distances. Even if you have an excellent LOD system, drawing tens to hundreds of polys with complex shaders for an object that occupies a tiny portion of the screen is wasteful. The classic argument against imposters is that the user can easily tell when they 'pop' into view, but a well implemented imposter system should be nearly undetectable even by those aware of it. This tutorial will give a bare-bones look at how to create an imposter in OpenGL.

Note: The code in this tutorial should be taken as pseudo-code. It hasn't been compiled or tested. It is meant only to demonstrate the technique.

For purposes of clarity, we'll treat our Imposter class like a struct and pass it into functions that do the updating and drawing. We'll be using the RenderTexture class developed in the Frame Buffer Object tutorial to store and update our imposter texture. Having one fbo/texture per imposter is incredibly wasteful, but easier to begin with. At the end, I'll discuss a few improvements that could be made.

Here is our simple Imposter class. The purpose of each variable will become more clear as the tutorial progresses.

class Imposter {
	public:
	RenderTexture renderTexture;  //  the texture that will store our imposter
	Vector verts[4];  //  the world-space billboard vertices we'll be using to draw the imposter
	Vector center;  //  the center of the billboard
	Vector cameraVec;  //  a unit vector pointing from the center towards the camera

	Imposter() : renderTexture(GL_RGBA, 256, 256) {}
};

The first step is to calculate an axis-aligned bounding box for the object you want to imposter. Here is a simple function that will calculate the AABB for a jumble of world-space vertices:

//  a little demonstration bounding box class
class BoundsAABB {
	public:
		Vector mins;
		Vector maxs;
		//  this function just lets us iterate over the vertices of the bounding box easily
		Vector operator[] (int i) {
			case 0: return mins;
			case 1: return Vector(maxs.x,mins.y,mins.z);
			case 2: return Vector(mins.x,maxs.y,mins.z);
			case 3: return Vector(mins.x,mins.y,maxs.z);
			case 4: return Vector(maxs.x,maxs.y,mins.z);
			case 5: return Vector(maxs.x,mins.y,maxs.z);
			case 6: return Vector(mins.x,maxs.y,maxs.z);
			case 7: return maxs;
			default: return mins;
			
		}		
};

BoundsAABB calculateAABB( const Vector[] vertices, int totalVertices ) {
	BoundsAABB b;
	b.mins = vertices[0];
	b.maxs = vertices[0];
	for(int i=1; i<totalVertices; ++i) {
		b.mins.x = min(vertices[i].x, b.mins.x);
		b.mins.y = min(vertices[i].y, b.mins.y);
		b.mins.z = min(vertices[i].z, b.mins.z);
		b.maxs.x = max(vertices[i].x, b.mins.x);
		b.maxs.y = max(vertices[i].y, b.mins.y);
		b.maxs.z = max(vertices[i].z, b.mins.z);
	}
	return b;
}

Now let's write a function to update our imposter. This function assumes the projection and modelview matrices are set up just as they would be for rendering an actual frame.

Our first goal is to calculate the vertices of the billboard we will use to draw the imposter. To do this takes three steps.

1. Project the world-space coordinates of our object's AABB into screen-space.

	double modelview[16];
	double projection[16];
	GLint viewport[4];
	
	glGetDoublev(GL_MODELVIEW_MATRIX, modelview);
	glGetDoublev(GL_PROJECTION_MATRIX, projection);
	glGetIntegerv(GL_VIEWPORT,viewport);

	//  project world-space object AABB vertices into screen-space
	Vector screenVerts[8];
	for(int i=0; i<8; ++i) {
		double x,y,z;
		gluProject(bounds[i].x,bounds[i].y,bounds[i].z,modelview,projection,viewport,&x,&y,&z);
		screenVerts[i] = Vector(x,y,z);
	}

2. Now we determine a tight bounding box around these screen-space vertices using the calculateAABB function defined above.

	BoundsAABB billboardBounds = calculateAABB( screenVerts, 8 );
	Vector screenQuadVerts[4];
	//  we create the four billboard quad vertices by extracting all of the billboard bounds with minimum z
	screenQuadVerts[0] = Vector(billboardBounds.mins.x, billboardBounds.mins.y, billboardBounds.mins.z);
	screenQuadVerts[1] = Vector(billboardBounds.maxs.x, billboardBounds.mins.y, billboardBounds.mins.z);
	screenQuadVerts[2] = Vector(billboardBounds.maxs.x, billboardBounds.maxs.y, billboardBounds.mins.z);
	screenQuadVerts[3] = Vector(billboardBounds.mins.x, billboardBounds.maxs.y, billboardBounds.mins.z);

3. Finally, we unproject these screen-space billboard vertices back into world-space. These world-space vertices form the quad that we will use to draw our imposter.

	for(int i=0; i<4; ++i) {
		double x,y,z;
		gluUnProject(screenQuadVerts[i].x,screenQuadVerts[i].y,screenQuadVerts[i].z,modelview,projection,viewport,&x,&y,&z);
		//  store our unprojected world-space vertices in the imposter for later use
		imposter.verts[i] = Vector(x,y,z);
	}

A handy value to have around is the center of our imposter billboard. This can be calculated just by averaging the vertices.

	imposter.center = Vector(0,0,0);
	for(int i=0; i<4; ++i) {
		imposter.center += imposter.verts[i];
	}
	imposter.center *= 0.25;

Another handy value is a vector pointing from the camera to the imposter. We can use this later as a metric for deciding when to update the imposter.

	imposter.cameraVec = cameraPos - imposter.center;
	imposter.cameraVec.normalize();

Now that we've calculated the billboard vertices and center, let's render the texture for our imposter. We set up the projection matrix with the near plane right on the imposter, and the far plane just far enough to cover the whole object. This way we get maximum use out of the depth buffer. The modelview matrix is set up so the camera is facing the center of the imposter from its current position.

	float nearPlane = (imposter.center - cameraPos).length();
	float farPlane = nearPlane + (bounds.maxs-bounds.mins).length();
	
	glMatrixMode(GL_PROJECTION);
	glPushMatrix();
	glLoadIdentity();
	
	//  calculate the width and height of our imposter's vertices
	float w = (imposter.verts[1] - imposter.verts[0]).length();
	float h = (imposter.verts[3] - imposter.verts[0]).length();

	//  setup a projection matrix with near plane points exactly covering the object
	glFrustum(-w/2,w/2,-h/2,h/2,nearPlane,farPlane);

	glMatrixMode(GL_MODELVIEW);
	glPushMatrix();
	glLoadIdentity();
	//  face the camera towards the imposter
	gluLookAt(cameraPos.x,cameraPos.y,cameraPos.z,imposter.center.x,imposter.center.y,imposter.center.z,0,1,0);
	
	imposter.renderTexture.startRender();
	//  clear the render texture to 0(be sure to set the alpha to 0 too!)
	glClearColor( 0.0f, 0.0f, 0.0f, 0.0f );
	glClear(GL_COLOR_BUFFER_BIT | GL_DEPTH_BUFFER_BIT);
	glColor4f(1,1,1,1);
}

That concludes the startUpdateImposter function. At this point you'll want to draw your object just as you would for a regular pass. When you are done, call the next function, finishUpdateImposter.

void finishUpdateImposter( Imposter &imposter ) {
	imposter.renderTexture.finishRender();

	glMatrixMode(GL_PROJECTION);
	glPopMatrix();
	glMatrixMode(GL_MODELVIEW);
	glPopMatrix();
}

We have now rendered the object into the imposter's texture. Now we can actually draw the imposter billboard.

void drawImposter( Imposter &imposter ) {
	imposter.renderTexture.bind();

	glBegin(GL_QUADS);
		glTexCoord2f(0,0);
		glVertex3fv(imposter.verts[0].v);
		glTexCoord2f(1,0);
		glVertex3fv(imposter.verts[1].v);
		glTexCoord2f(1,1);
		glVertex3fv(imposter.verts[2].v);
		glTexCoord2f(0,1);
		glVertex3fv(imposter.verts[3].v);
	glEnd();
}

The question arises: just how often do we need to update the imposter? That is a subject that has received considerable research. My brother's thesis is a good place to start. For a bare-bones implementation, a brain-dead function like this will work suprisingly well:

bool doesImposterNeedUpdate(const Imposter &imposter, Vector cameraPos) {
	Vector newCameraVec = cameraPos - imposter.center;
	newCameraVec.normalize();
	if(dotProduct(newCameraVec,imposter.cameraVec)<0.99999) return true;
	else return false;
}

Now let's discuss a few improvements that are needed in order to make the imposter system efficient.

1. Multiple imposters need to share a single texture. If you are drawing a lot of small imposters, the cost of switching textures each time can be significant. In my Prayer engine, I have an ImposterManager class that manages multiple ImposterCollection objects. Each ImposterCollection object has a large RenderTexture. Each new Imposter requests some space from the ImposterManager, which searches for an appropriately sized free area in the existing ImposterCollection objects, or allocates a new ImposterCollection if required. This way all of the imposters can batched into groups that share a texture at draw time.

2. As an object gets further away, it requires a lower resolution imposter texture. It is silly to use a 256x256 imposter texture on an object that occupies a handful of pixels on the screen. Using the screen-space coordinates calculated in the startUpdateImposter function, you can determine the required width and height of the imposter texture. If you are using a single texture per imposter, you can just round up to the nearest power of two. Otherwise, you can allocate more precise custom texture sizes in your common imposter texture if you so desire.

3. All of the imposters that share a texture should be batched together into one call to glBegin(GL_QUADS). Even better, you can stuff them into a vertex buffer object and use glBufferSubData to update only the billboard vertices that have changed.

4. In the unlikely case that a bunch of imposters have to be updated in a single frame, it might be a good idea to set a limit as to how any imposters can be updated per frame and queue the rest. I haven't had to do this in Prayer yet, but when we have large towns in the distance it could become a problem. If a lot of buildings are clustered around the same point, they will likely all need to be updated around the same time.