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; }