Fast Culling

From X-Plane SDK

This code snippet can be used to determine if a sphere at a location in the current OpenGL coordinates is visible.

• Call setup_cull_info once per drawing callback...this queries OpenGL to get the visibility info from OpenGL's state. Between callbacks the camera may have moved.
• Call sphere_is_visible once for each visibility check you want to make - r = radius of the sphere in meters; if the sphere whose center is XYZ and radius is r is completely off screen, the function returns false, otherwise is returns true.
• Be careful about tuning cull checks vs. drawing; you only want to cull large chunks of geometry, so that the fps boost from not drawing justifies the CPU time spent culling.
• You don't need to cull individual OBJs drawn with the XPLMDrawObject API - this API culls for you. But you might want to cull many objects at once, by culling a sphere that contains a whole set of objects.
• This code works in all projection matrices, ortho and frustum, including oblique frustums.

struct cull_info_t {					// This struct has everything we need to cull fast!
	float	model_view[16];				// The model view matrix, to get from local OpenGL to eye coordinates.
	float	nea_clip[4];				// Four clip planes in the form of Ax + By + Cz + D = 0 (ABCD are in the array.)
	float	far_clip[4];				// They are oriented so the positive side of the clip plane is INSIDE the view volume.
	float	lft_clip[4];
	float	rgt_clip[4];
	float	bot_clip[4];
	float	top_clip[4];
};

static void setup_cull_info(cull_info_t * i)
{
	float m[16];
	
	// First, just read out the current OpenGL matrices...do this once at setup because it's not the fastest thing to do.
	glGetFloatv(GL_MODELVIEW_MATRIX ,i->model_view);
	glGetFloatv(GL_PROJECTION_MATRIX,m);
	
	// Now...what the heck is this?  Here's the deal: the clip planes have values in "clip" coordinates of: Left = (1,0,0,1)
	// Right = (-1,0,0,1), Bottom = (0,1,0,1), etc.  (Clip coordinates are coordinates from -1 to 1 in XYZ that the driver
	// uses.  The projection matrix converts from eye to clip coordinates.)
	//
	// How do we convert a plane backward from clip to eye coordinates?  Well, we need the transpose of the inverse of the
	// inverse of the projection matrix.  (Transpose of the inverse is needed to transform a plane, and the inverse of the
	// projection is the matrix that goes clip -> eye.)  Well, that cancels out to the transpose of the projection matrix,
	// which is nice because it means we don't need a matrix inversion in this bit of sample code.
	
	// So this nightmare down here is simply:
	// clip plane * transpose (proj_matrix)
	// worked out for all six clip planes.  If you squint you can see the patterns:
	// L:  1  0 0 1
	// R: -1  0 0 1
	// B:  0  1 0 1
	// T:  0 -1 0 1
	// etc.
	
	i->lft_clip[0] = m[0]+m[3];	i->lft_clip[1] = m[4]+m[7];	i->lft_clip[2] = m[8]+m[11];	i->lft_clip[3] = m[12]+m[15];
	i->rgt_clip[0] =-m[0]+m[3];	i->rgt_clip[1] =-m[4]+m[7];	i->rgt_clip[2] =-m[8]+m[11];	i->rgt_clip[3] =-m[12]+m[15];
	
	i->bot_clip[0] = m[1]+m[3];	i->bot_clip[1] = m[5]+m[7];	i->bot_clip[2] = m[9]+m[11];	i->bot_clip[3] = m[13]+m[15];
	i->top_clip[0] =-m[1]+m[3];	i->top_clip[1] =-m[5]+m[7];	i->top_clip[2] =-m[9]+m[11];	i->top_clip[3] =-m[13]+m[15];

	i->nea_clip[0] = m[2]+m[3];	i->nea_clip[1] = m[6]+m[7];	i->nea_clip[2] = m[10]+m[11];	i->nea_clip[3] = m[14]+m[15];
	i->far_clip[0] =-m[2]+m[3];	i->far_clip[1] =-m[6]+m[7];	i->far_clip[2] =-m[10]+m[11];	i->far_clip[3] =-m[14]+m[15];
}

static int sphere_is_visible(const cull_info_t * i, float x, float y, float z, float r)
{
	// First: we transform our coordinate into eye coordinates from model-view.
	float xp = x * i->model_view[0] + y * i->model_view[4] + z * i->model_view[ 8] + i->model_view[12];
	float yp = x * i->model_view[1] + y * i->model_view[5] + z * i->model_view[ 9] + i->model_view[13];
	float zp = x * i->model_view[2] + y * i->model_view[6] + z * i->model_view[10] + i->model_view[14];

	// Now - we apply the "plane equation" of each clip plane to see how far from the clip plane our point is.  
	// The clip planes are directed: positive number distances mean we are INSIDE our viewing area by some distance;
	// negative means outside.  So ... if we are outside by less than -r, the ENTIRE sphere is out of bounds.
	// We are not visible!  We do the near clip plane, then sides, then far, in an attempt to try the planes
	// that will eliminate the most geometry first...half the world is behind the near clip plane, but not much is
	// behind the far clip plane on sunny day.
	if ((xp * i->nea_clip[0] + yp * i->nea_clip[1] + zp * i->nea_clip[2] + i->nea_clip[3] + r) < 0)	return false;
	if ((xp * i->bot_clip[0] + yp * i->bot_clip[1] + zp * i->bot_clip[2] + i->bot_clip[3] + r) < 0)	return false;
	if ((xp * i->top_clip[0] + yp * i->top_clip[1] + zp * i->top_clip[2] + i->top_clip[3] + r) < 0)	return false;
	if ((xp * i->lft_clip[0] + yp * i->lft_clip[1] + zp * i->lft_clip[2] + i->lft_clip[3] + r) < 0)	return false;
	if ((xp * i->rgt_clip[0] + yp * i->rgt_clip[1] + zp * i->rgt_clip[2] + i->rgt_clip[3] + r) < 0)	return false;
	if ((xp * i->far_clip[0] + yp * i->far_clip[1] + zp * i->far_clip[2] + i->far_clip[3] + r) < 0)	return false;
	return true;
	
}