#include #include #include enum{A, B, C, D}; /* plane equation coefficients */ enum{X, Y, Z}; /* for finding coordinates */ enum{Red, Green, Blue, Alpha}; /* for color components */ #define NULL 0 /* For Santa Clara's loader */ #define BRAINDAMAGED_LOADER #ifdef BRAINDAMAGED_LOADER #define cosf(x) (float)cos((float)(x)) #define sinf(x) (float)sin((float)(x)) #endif /* define a polygon */ typedef struct Polygon { int n; /* number of vertices */ GLfloat color[3]; /* color for polygon */ GLfloat *verts; /* ordered list of vertex coordinates V0 -> Vn-1*/ struct Polygon *next; /* to make a list of pgons */ } Poly; typedef struct BSPNode { Poly *pgon; /* polygon to draw */ GLfloat plane[4]; /* plane equation coefficients A, B, C, D*/ struct BSPNode *front; /* nodes in front of this one */ struct BSPNode *back; /* nodes behind this one */ } Node; /* node in bsp tree */ Poly *object = NULL; /* object to draw */ Node *bspTree = NULL; /* bsp tree */ /* a cube; on corner on origin */ GLfloat cube[] = {1.f, 1.f, 1.f, /* white */ 0.f, 0.f, 0.f, /* face in XY plane */ 1.f, 0.f, 0.f, 1.f, 1.f, 0.f, 0.f, 1.f, 0.f, 1.f, 0.f, 0.f, /* red */ 1.f, 0.f, 0.f, /* face in X = 1 plane */ 1.f, 0.f,-1.f, 1.f, 1.f,-1.f, 1.f, 1.f, 0.f, 0.f, 1.f, 0.f, /* green */ 1.f, 0.f,-1.f, /* face in Z = -1 plane */ 0.f, 0.f,-1.f, 0.f, 1.f,-1.f, 1.f, 1.f,-1.f, 0.f, 0.f, 1.f, /* blue */ 0.f, 0.f, 0.f, /* face in YZ plane */ 0.f, 1.f, 0.f, 0.f, 1.f,-1.f, 0.f, 0.f,-1.f, 0.f, 1.f, 1.f, /* cyan */ 0.f, 0.f, 0.f, /* face in XZ plane */ 0.f, 0.f,-1.f, 1.f, 0.f,-1.f, 1.f, 0.f, 0.f, 1.f, 0.f, 1.f, /* magenta */ 0.f, 1.f, 0.f, /* face in Y = 1 plane */ 1.f, 1.f, 0.f, 1.f, 1.f,-1.f, 0.f, 1.f,-1.f}; /* assume 3 float x,y,z format */ Poly * makePoly(GLfloat *color, GLfloat *verts, int n) { int i; Poly *pgon; pgon = (Poly *)malloc(sizeof(Poly)); if(color) { pgon->color[Red] = color[Red]; pgon->color[Green] = color[Green]; pgon->color[Blue] = color[Blue]; } pgon->verts = (GLfloat *)malloc(sizeof(GLfloat) * n * 3); for(i = 0; i < n * 3; i++) pgon->verts[i] = verts[i]; pgon->n = n; pgon->next = NULL; return pgon; } void drawPoly(Poly *pgon) { int i; glBegin(GL_POLYGON); glColor3fv(pgon->color); for(i = 0; i < pgon->n; i++) glVertex3fv(&pgon->verts[i * 3]); glEnd(); } void subVec(GLfloat vert[3], GLfloat minus[3], GLfloat result[4]) { result[X] = vert[X] - minus[X]; result[Y] = vert[Y] - minus[Y]; result[Z] = vert[Z] - minus[Z]; } void cross(GLfloat A[3], GLfloat B[3], GLfloat cross[3]) { cross[X] = A[Y] * B[Z] - A[Z] * B[Y]; cross[Y] = -(A[X] * B[Z] - A[Z] * B[X]); cross[Z] = A[X] * B[Y] - A[Y] * B[X]; } /* find D component of plane equation */ void findD(GLfloat coeff[3], GLfloat point[3], GLfloat *d) { *d = - (coeff[A] * point[X] + coeff[B] * point[Y] + coeff[C] * point[Z]); } void findPlane(Poly *pgon, GLfloat plane[4]) { GLfloat *vert0, *vert1, *vert2; GLfloat vecA[3], vecB[3]; GLfloat normal[3]; vert0 = pgon->verts; vert1 = &pgon->verts[3]; vert2 = &pgon->verts[3 * (pgon->n - 1)]; subVec(vert1, vert0, vecA); subVec(vert2, vert0, vecB); cross(vecA, vecB, plane); findD(plane, vert0, &plane[3]); } /* is the polygon in front of plane? nonzero = TRUE */ int frontPlane(GLfloat plane[4], Poly *pgon) { int i; GLfloat eq; for(i = 0; i < pgon->n; i++) { eq = plane[A] * pgon->verts[i * 3] + plane[B] * pgon->verts[i * 3 + 1] + plane[C] * pgon->verts[i * 3 + 2] + plane[D]; if(eq < 0.f) return 0; } return 1; } /* wrapper function */ int inFront(Node *node, Poly *pgon) { return (frontPlane(node->plane, pgon)); } /* is viewpoint in front of plane? */ int viewFront(Node *node, GLfloat view[3]) { if(node->plane[A] * view[X] + node->plane[B] * view[Y] + node->plane[C] * view[Z] + node->plane[D] < 0.f) return 0; else return 1; } /* create a new bsp node */ Node * newNode(Poly *pgon) { Node *node; int i; node = (Node *)malloc(sizeof(Node)); node->pgon = pgon; findPlane(pgon, node->plane); node->back = NULL; node->front = NULL; return node; } /* create a bsp subtree and return the pointer */ Node * createBSP(Poly *objlist) { Poly *obj, *flist = NULL, *blist = NULL; Node *node; /* node to return */ if(!objlist) /* no more objects */ return NULL; /* make a node from the top of the list */ node = newNode(objlist); objlist = objlist->next; while(objlist) { obj = objlist; objlist = objlist->next; if(inFront(node, obj)) { obj->next = flist; flist = obj; } else { obj->next = blist; blist = obj; } } node->front = createBSP(flist); node->back = createBSP(blist); return node; } void traverseBSP(Node *tree, GLfloat *viewpt) { if(!tree) return; if(viewFront(tree, viewpt)) { traverseBSP(tree->back, viewpt); drawPoly(tree->pgon); traverseBSP(tree->front, viewpt); } else { traverseBSP(tree->front, viewpt); drawPoly(tree->pgon); traverseBSP(tree->back, viewpt); } } /* convert polygon list to array of Poly objects */ Poly * makeCube(GLfloat *data) { int face; Poly *prev, *plist = NULL; for(face = 0; face < 6; face++) { prev = plist; plist = makePoly(data, &data[3], 4); plist->next = prev; data += 15; } return plist; } /* eye position */ GLfloat eye[3] = {0.f, 5.f, 0.f}; void redraw(void) { glClear(GL_COLOR_BUFFER_BIT); glPushMatrix(); gluLookAt(eye[X], eye[Y], eye[Z], 0.5f, 0.5f, 0.5f, 0.f, 1.f, 0.f); traverseBSP(bspTree, eye); glPopMatrix(); glutSwapBuffers(); } void key(unsigned char key, int x, int y) { switch(key) { case '\033': exit(0); } } void motion(void) { static float angle = 0.f; angle += .01f; eye[X] = 10.f * cosf(angle); eye[Z] = 10.f * sinf(angle); glutPostRedisplay(); } main(int argc, char **argv) { glutInit(&argc, argv); glutInitWindowSize(512, 512); glutInitDisplayMode(GLUT_RGBA|GLUT_DOUBLE); (void)glutCreateWindow("bsp tree"); glutDisplayFunc(redraw); glutIdleFunc(motion); glutKeyboardFunc(key); object = makeCube(cube); bspTree = createBSP(object); glMatrixMode(GL_PROJECTION); glFrustum(-2., 2., -2., 2., 9., 20.); glMatrixMode(GL_MODELVIEW); glutMainLoop(); }