hcsg.cpp | hcsg_modeler.cpp | collision.cpp | camera.cpp | vector.cpp | main.cpp | ||||||
hcsg.h | hcsg_modeler.h | collision.h | camera.h | vector.h |
// ************************************************************************** // HCSG Demo // (c) Bernie Freidin, 1999-2000 // ************************************************************************** #include <stdio.h> #include <stdlib.h> #include <string.h> #include <math.h> #include <time.h> #include "hcsg.h" #ifdef __MAC__ #include <Windows.h> #endif static vert_t *CSG_VERT_POOL = NULL; static surf_t *CSG_SURF_POOL = NULL; static ccof_t *CSG_CCOF_POOL = NULL; static int CSG_VERT_COUNT = 0; static int CSG_SURF_COUNT = 0; static int CSG_CCOF_COUNT = 0; static ccof_t *CSG_CCOF[CSG_MAX_DEPTH+1]; static int CSG_POLYGONALIZATION_DEPTH = 1; static hull_t *CSG_WORLD = NULL; static int CSG_CODE_OUT; static int CSG_CODE_IN; static void *CSG_CURRENT_SHAPE; // Debugging stuff. NOTE: We can't put the function name stack // on the heap using our standard CSG_AllocMem command, since // this command itself uses the function name stack! #define CSG_MAX_FUNC_DEPTH 100 static FILE *CSG_LOGFILE = NULL; static int CSG_ERRORS = 0; static int CSG_FUNC_DEPTH = 0; static char CSG_FUNC_NAME_STACK[CSG_MAX_FUNC_DEPTH][61] = {""}; static int CSG_MEMORY_USED = 0; static int CSG_MEMORY_CHECK = 0; #define CSG_RESOLVE_KEEP_NEW 1 #define CSG_RESOLVE_KEEP_OLD 2 // ******************************************************************* // FIXME: For now, we are forced to use KEEP_OLD for RESOLVE_ADD_3D, // because otherwise CSG_BooleanSub(HULL) will be invoked, which // requires a different polygonalization function than CSG_BooleanAdd, // which we have not yet written.. // ******************************************************************* static int CSG_RESOLVE_ADD_2D = CSG_RESOLVE_KEEP_NEW; static int CSG_RESOLVE_ADD_3D = CSG_RESOLVE_KEEP_OLD; // ============================================================== // HCSG: Hierarchial Constructive Solid Geometry Data Structures: // // Vertices and surface planes are stored in global pools. // There are two basic building blocks that describe geometry, // the POLYGON and the HULL. Polygons contain lists of vertex // references and a surface reference, as well as a list of // surface references which indicate the cutting planes forming // the polygon. Hulls also contain a list of vertex references, // and a linked list of polygons (NEXT). // // In addition, both polygons and hulls have sub-lists (DOWN). // An entity in a sub-list is always contained entirely within // the parent entity. // ============================================================== void CSG_Initialize(void) { CSG_PUSHNAME("Initialize"); // ********************** // Initialize HCSG engine // ********************** CSG_VERT_POOL = (vert_t*)CSG_AllocMem(sizeof(vert_t), CSG_MAX_VERTS); CSG_SURF_POOL = (surf_t*)CSG_AllocMem(sizeof(surf_t), CSG_MAX_SURFS); CSG_CCOF_POOL = (ccof_t*)CSG_AllocMem(sizeof(ccof_t), CSG_MAX_CCOFS); CSG_VERT_COUNT = 0; CSG_SURF_COUNT = 0; CSG_CCOF_COUNT = 0; CSG_MEMORY_CHECK = 1; CSG_POPNAME_; } hull_t *CSG_World(void) { CSG_PUSHNAME("World"); if(CSG_WORLD) CSG_Free(CSG_WORLD); CSG_WORLD = CSG_SolidCube(-1000.0, -1000.0, -1000.0, +1000.0, +1000.0, +1000.0); CSG_WORLD->depth = 0; CSG_POPNAME(CSG_WORLD); } vert_t *CSG_GetVertPool(void) { return CSG_VERT_POOL; } surf_t *CSG_GetSurfPool(void) { return CSG_SURF_POOL; } int CSG_GetMemInUse_Modeler(void); // prototype int CSG_GetMemInUse(void *obj) { CSG_PUSHNAME("GetMemInUse"); // ************************************************** // Determines the amount of memory used by an object. // This works for POLY and HULL objects. If NULL is // specified, then the function returns the amount of // global memory used by the HCSG engine including // all pools, etc. If -1 is specified, the function // returns the amount of global memory used by the // pools (VERT, SURF, CCOF) only. // ************************************************** int mem; if(!obj) { mem = CSG_MEMORY_USED; } else if(obj == (void*)-1) { mem = CSG_GetMemInUse_Modeler(); mem += sizeof(vert_t) * CSG_MAX_VERTS; mem += sizeof(surf_t) * CSG_MAX_SURFS; mem += sizeof(ccof_t) * CSG_MAX_CCOFS; } else { mem = 0; if(*(int*)obj == CSG_TYPE_POLY) { poly_t *poly = (poly_t*)obj; for(poly_t *p = poly->down; p; p = p->next) { mem += CSG_GetMemInUse(p); } mem += sizeof(vref_t) * poly->vertcount; mem += sizeof(sref_t) * poly->vertcount; mem += sizeof(poly_t); } else if(*(int*)obj == CSG_TYPE_HULL) { hull_t *hull = (hull_t*)obj; for(poly_t *p = hull->face; p; p = p->next) { mem += CSG_GetMemInUse(p); } for(hull_t *h = hull->down; h; h = h->next) { mem += CSG_GetMemInUse(h); } mem += sizeof(vref_t) * hull->vertcount; mem += sizeof(hull_t); } } CSG_POPNAME(mem); } void CSG_CheckMem(void) { CSG_PUSHNAME("CheckMem"); // *********************** // Checks for memory leaks // *********************** if(!CSG_MEMORY_CHECK) { CSG_POPNAME_; } int mem1 = CSG_GetMemInUse(NULL); // as reported by Alloc/Free int mem2 = CSG_GetMemInUse((void*)-1); // pools int mem3 = CSG_GetMemInUse(CSG_WORLD); // world char msg[100]; sprintf(msg, "memory leak found: %i", mem1 - mem2 - mem3); CSG_ASSERT(mem1 == mem2 + mem3, msg); CSG_POPNAME_; } void CSG_Messg(char *msg) { // ************* // Log some text // ************* return; // no logging if(!CSG_LOGFILE) { CSG_LOGFILE = fopen("CSG_log.txt", "w"); } fprintf(CSG_LOGFILE, "-> %s\n", msg); fflush(CSG_LOGFILE); } void CSG_Error(char *msg) { // ******************** // Log an error message // ******************** if(!CSG_LOGFILE) { CSG_LOGFILE = fopen("CSG_log.txt", "w"); } if(CSG_FUNC_DEPTH > 0) { char *fn = CSG_FUNC_NAME_STACK[CSG_FUNC_DEPTH-1]; fprintf(CSG_LOGFILE, "-> ERROR: %s: %s\n", fn, msg); } else { fprintf(CSG_LOGFILE, "-> ERROR: >: %s\n", msg); } fflush(CSG_LOGFILE); #if 1 int div0 = 0; int x = 1 / div0; // cause DIVIDE-BY-ZERO and halt #endif CSG_ERRORS++; } void CSG_PushFunctionName(char *name) { // **************************************************** // Useful for debugging - every function should declare // its name so that an error message may report it. // **************************************************** CSG_ASSERT(CSG_FUNC_DEPTH < CSG_MAX_FUNC_DEPTH, "function stack overflow"); strncpy(CSG_FUNC_NAME_STACK[CSG_FUNC_DEPTH++], name, 60); } void CSG_PopFunctionName(void) { CSG_ASSERT(CSG_FUNC_DEPTH > 0, "function stack underflow"); CSG_FUNC_DEPTH--; } void CSG_Print(poly_t *poly) { CSG_PUSHNAME("Print[POLY]"); char s1[200] = "v= "; char s2[200]; for(int n = 0; n < poly->vertcount; n++) { vert_t v = CSG_VERT_POOL[poly->vref[n]]; sprintf(s2, "(%.2f,%.2f,%.2f)", v.x, v.y, v.z); strcat(s1, s2); } CSG_Messg("POLY:"); CSG_Messg(s1); CSG_Messg("END POLY"); CSG_POPNAME_; } void CSG_Print(hull_t *hull) { CSG_PUSHNAME("Print[HULL]"); CSG_Messg("HULL:"); for(poly_t *p = hull->face; p; p = p->next) { CSG_Print(p); } CSG_Messg("END HULL"); CSG_POPNAME_; } vref_t CSG_AddToVertPool(vert_t &vert) { CSG_PUSHNAME("AddToVertPool"); // ********************************************** // Add a vertex to the vertex pool. If the vertex // already exists, return its index. // ********************************************** int i; for(i = 0; i < CSG_VERT_COUNT; i++) { vec3 err = vert - CSG_VERT_POOL[i]; if(err*err <= CSG_MAXERR*CSG_MAXERR) { CSG_POPNAME((vref_t)i); } } CSG_ASSERT(CSG_VERT_COUNT < CSG_MAX_VERTS, "too many vertices"); CSG_VERT_POOL[i] = vert; CSG_VERT_COUNT++; CSG_POPNAME((vref_t)i); } sref_t CSG_AddToSurfPool(surf_t &surf) { CSG_PUSHNAME("AddToSurfPool"); // ************************************************* // Add a surface to the surface pool. If the surface // already exists, return its index. // ************************************************* int i; for(i = 0; i < CSG_SURF_COUNT; i++) { if(fabs(CSG_SURF_POOL[i].dist - surf.dist) <= CSG_MAXERR) { if(fabs(CSG_SURF_POOL[i].norm*surf.norm - 1.0) <= CSG_MAXERR2) { CSG_POPNAME((sref_t)i); } } if(fabs(CSG_SURF_POOL[i].dist + surf.dist) <= CSG_MAXERR) { if(fabs(CSG_SURF_POOL[i].norm*surf.norm + 1.0) <= CSG_MAXERR2) { CSG_POPNAME((sref_t)i | CSG_SIDE_MASK); } } } CSG_ASSERT(CSG_SURF_COUNT < CSG_MAX_SURFS, "too many surfaces"); CSG_SURF_COUNT++; CSG_SURF_POOL[i] = surf; // ************************************************** // Compute surface mask. This field controls active // bounding-box components during POLY-POLY and POLY- // HULL bounding box checks. // ************************************************** double nx = fabs(surf.norm.x); double ny = fabs(surf.norm.y); double nz = fabs(surf.norm.z); int mask; if(nx >= ny && nx >= nz) mask = 2+4; else if(ny >= nx && ny >= nz) mask = 1+4; else mask = 1+2; CSG_SURF_POOL[i].mask = mask; CSG_SURF_POOL[i].data = rand(); CSG_POPNAME((sref_t)i); } sref_t CSG_AddToSurfPool(vref_t vref[], int i1, int i2, int i3) { CSG_PUSHNAME("AddToSurfPool"); // *********************************************** // Add a surface to the surface pool, created from // three vertices. If the surface already exists, // return its index. // *********************************************** surf_t surf; vert_t v1 = CSG_VERT_POOL[vref[i1]]; vert_t v2 = CSG_VERT_POOL[vref[i2]]; vert_t v3 = CSG_VERT_POOL[vref[i3]]; vec3 norm = (v2-v1) ^ (v3-v1); double q = norm.len(); CSG_ASSERT(q != 0.0, "zero normal"); surf.norm.x = norm.x / q; surf.norm.y = norm.y / q; surf.norm.z = norm.z / q; surf.dist = -(norm*v1) / q; CSG_POPNAME(CSG_AddToSurfPool(surf)); } void CSG_AddToPoly(poly_t *poly, vref_t vert_id, sref_t surf_id) { CSG_PUSHNAME("AddToPoly"); // ************************************************ // Adds a vertex and surface reference to a polygon // ************************************************ poly->vref[poly->vertcount] = vert_id; poly->sref[poly->vertcount] = surf_id; #if CSG_DEBUG // ***************************** // This helps catch errors early // ***************************** int n2 = poly->vertcount - 1; double tt1 = CSG_Distance(vert_id, poly->surf_id); double tt2 = CSG_Distance(vert_id, surf_id); double tt3 = (n2 > -1) ? CSG_Distance(poly->vref[n2], surf_id):0.0; CSG_ASSERT(tt1 == 0.0, "vertex not on surface"); CSG_ASSERT(tt2 == 0.0, "vertex not on surface"); CSG_ASSERT(tt3 == 0.0, "vertex not on surface"); #endif poly->vertcount++; CSG_POPNAME_; } void CSG_Copy(poly_t *dst, poly_t *src) { CSG_PUSHNAME("Copy[POLY]"); // ********************************************** // Deallocate existing dst->VREF and dst->SREF if // needed, and copy src->VREF and src->SREF into // dst. Also copy VERTCOUNT. Leave other data // unchanged. // ********************************************** if(dst->vref) CSG_FreeMem(dst->vref); if(dst->sref) CSG_FreeMem(dst->sref); dst->vref = (vref_t*)CSG_AllocMem(sizeof(vref_t), src->vertcount); dst->sref = (sref_t*)CSG_AllocMem(sizeof(sref_t), src->vertcount); memcpy(dst->vref, src->vref, sizeof(vref_t) * src->vertcount); memcpy(dst->sref, src->sref, sizeof(sref_t) * src->vertcount); dst->vertcount = src->vertcount; CSG_POPNAME_; } void CSG_Copy(hull_t *dst, hull_t *src) { CSG_PUSHNAME("Copy[HULL]"); CSG_ASSERT(0, "not implemented!"); CSG_POPNAME_; } poly_t *CSG_Clone(void *parent, poly_t *src) { CSG_PUSHNAME("Clone[POLY]"); // ********************************************** // Clone polygon. Sub-polygons are not preserved. // ********************************************** poly_t *dst = CSG_Alloc(parent, src->vertcount, src->surf_id); memcpy(dst->vref, src->vref, sizeof(vref_t) * src->vertcount); memcpy(dst->sref, src->sref, sizeof(sref_t) * src->vertcount); dst->vertcount = src->vertcount; dst->bbox = src->bbox; dst->shape = src->shape; CSG_POPNAME(dst); } hull_t *CSG_Clone(void *parent, hull_t *src) { CSG_PUSHNAME("Clone[HULL]"); // ******************************************************* // Clone hull. Sub-hulls are not preserved, but faces are. // ******************************************************* hull_t *dst = CSG_Alloc(parent); dst->vref = (vref_t*)CSG_AllocMem(sizeof(vref_t), src->vertcount); memcpy(dst->vref, src->vref, sizeof(vref_t) * src->vertcount); dst->vertcount = src->vertcount; dst->bbox = src->bbox; dst->shape = src->shape; for(poly_t *p = src->face; p; p = p->next) { CSG_Clone(dst, p); } CSG_POPNAME(dst); } void *CSG_AllocMem(int size, int nelems) { CSG_PUSHNAME("AllocMem"); // ************************** // Allocate a block of memory // ************************** #if CSG_DEBUG CSG_MEMORY_USED += size * nelems; #endif #ifdef __MAC__ void *tmp = NewPtr(size * nelems); CSG_ASSERT(tmp, "out of memory"); memset(tmp, 0, size * nelems); #else void *tmp = calloc(size, nelems); CSG_ASSERT(tmp, "out of memory"); #endif CSG_POPNAME(tmp); } poly_t *CSG_Alloc(void *parent, int vertcount, sref_t surf_id) { CSG_PUSHNAME("Alloc[POLY]"); // *************************************** // Allocate new polygon and link to parent // *************************************** poly_t *poly = (poly_t*)CSG_AllocMem(sizeof(poly_t), 1); poly->flags = CSG_TYPE_POLY; poly->surf_id = surf_id; CSG_Link(parent, poly); if(vertcount > 0) { // ********************************************* // Allocate space for vertices if vertcount > 0, // otherwise leave as NULL. Note that vertcount // of polygon is left at 0 regardless. // ********************************************* poly->vref = (vref_t*)CSG_AllocMem(sizeof(vref_t), vertcount); poly->sref = (sref_t*)CSG_AllocMem(sizeof(sref_t), vertcount); } poly->q = (double)rand(); CSG_POPNAME(poly); } hull_t *CSG_Alloc(void *parent) { CSG_PUSHNAME("Alloc[HULL]"); // ************************************ // Allocate new hull and link to parent // ************************************ hull_t *hull = (hull_t*)CSG_AllocMem(sizeof(hull_t), 1); hull->flags = CSG_TYPE_HULL; CSG_Link(parent, hull); CSG_POPNAME(hull); } void CSG_FreeMem(void *dst) { CSG_PUSHNAME("FreeMem"); // ***************** // Free memory block // ***************** if(!dst) { CSG_POPNAME_; } #ifdef __MAC__ #if CSG_DEBUG CSG_MEMORY_USED -= GetPtrSize((char*)dst); #endif DisposePtr((char*)dst); #else #if CSG_DEBUG CSG_MEMORY_USED -= ((long*)dst)[-4]; // implementation-specific! #endif free(dst); #endif CSG_POPNAME_; } void CSG_Free(poly_t *poly) { CSG_PUSHNAME("Free[POLY]"); // *************************************************** // Recursively free poly and all associated structures // *************************************************** CSG_Unlink(poly); for(poly_t *pnext, *p = poly->down; p; p = pnext) { pnext = p->next; CSG_Free(p); } CSG_FreeMem(poly->vref); CSG_FreeMem(poly->sref); CSG_FreeMem(poly); CSG_POPNAME_; } void CSG_Free(hull_t *hull) { CSG_PUSHNAME("Free[HULL]"); // *************************************************** // Recursively free hull and all associated structures // *************************************************** CSG_Unlink(hull); for(poly_t *pnext, *p = hull->face; p; p = pnext) { pnext = p->next; CSG_Free(p); } for(hull_t *hnext, *h = hull->down; h; h = hnext) { hnext = h->next; CSG_Free(h); } CSG_FreeMem(hull->vref); CSG_FreeMem(hull); CSG_POPNAME_; } void CSG_Unlink(poly_t *poly) { CSG_PUSHNAME("Unlink[POLY]"); // ************************** // Unlink polygon from parent // ************************** if(poly->parent) { if(*(int*)poly->parent == CSG_TYPE_POLY) { poly_t *parent = (poly_t*)poly->parent; if(parent->down == poly) { parent->down = poly->next; } else { poly_t *p = parent->down; while(p && p->next && p->next != poly) p = p->next; CSG_ASSERT(p && p->next, "no reference from parent"); p->next = poly->next; } } else // is hull { hull_t *parent = (hull_t*)poly->parent; if(parent->face == poly) { parent->face = poly->next; } else { poly_t *p = parent->face; while(p && p->next && p->next != poly) p = p->next; CSG_ASSERT(p && p->next, "no reference from parent"); p->next = poly->next; } } poly->parent = NULL; poly->next = NULL; } poly->depth = 0; CSG_POPNAME_; } void CSG_Unlink(hull_t *hull) { CSG_PUSHNAME("Unlink[HULL]"); // *********************** // Unlink hull from parent // *********************** if(hull->parent) { hull_t *parent = (hull_t*)hull->parent; if(parent->down == hull) { parent->down = hull->next; } else { hull_t *h = parent->down; while(h && h->next && h->next != hull) h = h->next; CSG_ASSERT(h && h->next, "no reference from parent"); h->next = hull->next; } hull->parent = NULL; hull->next = NULL; } hull->depth = 0; CSG_POPNAME_; } void CSG_Link(void *parent, poly_t *poly) { CSG_PUSHNAME("Link[POLY]"); // ********************** // Link polygon to parent // ********************** poly->parent = parent; if(!parent) { poly->depth = 0; // this is a dangerous assumption..? CSG_POPNAME_; } switch(*(int*)parent) { case CSG_TYPE_POLY: { poly_t *dst = (poly_t*)parent; poly->depth = dst->depth + 1; poly->next = dst->down; dst->down = poly; break; } case CSG_TYPE_HULL: { hull_t *dst = (hull_t*)parent; poly->depth = 0; poly->next = dst->face; dst->face = poly; break; } } CSG_POPNAME_; } void CSG_Link(void *parent, hull_t *hull) { CSG_PUSHNAME("Link[HULL]"); // ******************* // Link hull to parent // ******************* hull->parent = parent; if(!parent) { hull->depth = -1; CSG_POPNAME_; } switch(*(int*)parent) { case CSG_TYPE_HULL: { hull_t *dst = (hull_t*)parent; hull->depth = dst->depth + 1; hull->next = dst->down; dst->down = hull; break; } } CSG_POPNAME_; } int CSG_Count(poly_t *poly) { CSG_PUSHNAME("Count[POLY]"); // ********************** // Count polygons in list // ********************** int count = 0; while(poly) { count++; poly = poly->next; } CSG_POPNAME(count); } int CSG_Count(hull_t *hull) { CSG_PUSHNAME("Count[HULL]"); // ******************* // Count hulls in list // ******************* int count = 0; while(hull) { count++; hull = hull->next; } CSG_POPNAME(count); } int CSG_Count(ccof_t *ccof) { CSG_PUSHNAME("Count[CCOF"); // ******************** // Count CCOF's in list // ******************** int count = 0; while(ccof) { count++; ccof = ccof->next; } CSG_POPNAME(count); } void CSG_SetPolygonalizationDepth(int depth) { CSG_PUSHNAME("SetPolygonalizationDepth"); // ***************************************************** // Sets the depth level (in the HCSG hierarchy) at which // polygonalization begins. Essentially, this causes all // hulls and faces at lesser depths to be ignored during // the polygonalization process. // ***************************************************** CSG_ASSERT(depth >= 0 && depth <= CSG_MAX_DEPTH, "out of range"); CSG_POLYGONALIZATION_DEPTH = depth; CSG_POPNAME_; } void CSG_GenCCOF(poly_t *face) { CSG_PUSHNAME("GenCCOF"); // ********************************************************** // Generate list of Coplanar-Coincident Opposite Faces (CCOF) // ********************************************************** hull_t *hull = (hull_t*)face->parent; int ascend = 1; // ****************** // First, reset lists // ****************** for(int i = 0; i <= CSG_MAX_DEPTH; i++) { CSG_CCOF[i] = NULL; } CSG_CCOF_COUNT = 0; // *************************************************** // Ascend hierarchy until face is strictly inside hull // *************************************************** while(ascend) { ascend = 0; for(poly_t *p = hull->face; p; p = p->next) { if(p->surf_id == face->surf_id) { hull = (hull_t*)hull->parent; if(!hull) { CSG_POPNAME_; // CCOF = {} } ascend = 1; break; } } } // ************************************************* // Descend hierarchy recursively and enumerate faces // ************************************************* CSG_GenCCOF(face, hull); CSG_POPNAME_; } void CSG_GenCCOF(poly_t *face, hull_t *hull) { CSG_PUSHNAME("GenCCOF"); // ********************************* // Internal recursive stuff for CCOF // ********************************* sref_t surf_id_opp = face->surf_id ^ CSG_SIDE_MASK; for(hull_t *h = hull->down; h; h = h->next) { for(poly_t *p = h->face; p; p = p->next) { if(p->surf_id != surf_id_opp) continue; if(CSG_Intersect(p, face)) continue; if(h->depth >= CSG_POLYGONALIZATION_DEPTH) { CSG_ASSERT(CSG_CCOF_COUNT < CSG_MAX_CCOFS, "too many CCOFs"); ccof_t *cc = &CSG_CCOF_POOL[CSG_CCOF_COUNT++]; cc->face = p; cc->next = CSG_CCOF[h->depth]; CSG_CCOF[h->depth] = cc; } CSG_GenCCOF(face, h); break; } } CSG_POPNAME_; } void CSG_Update(bbox_t *bbox, vref_t vref[], int vertcount) { CSG_PUSHNAME("Update[BBOX]"); // ******************* // Update bounding box // ******************* CSG_ASSERT(vertcount > 0, "zero vertcount"); bbox->minv = CSG_VERT_POOL[vref[0]]; bbox->maxv = CSG_VERT_POOL[vref[0]]; for(int i = 1; i < vertcount; i++) { vert_t v = CSG_VERT_POOL[vref[i]]; if(bbox->minv.x > v.x) bbox->minv.x = v.x; if(bbox->minv.y > v.y) bbox->minv.y = v.y; if(bbox->minv.z > v.z) bbox->minv.z = v.z; if(bbox->maxv.x < v.x) bbox->maxv.x = v.x; if(bbox->maxv.y < v.y) bbox->maxv.y = v.y; if(bbox->maxv.z < v.z) bbox->maxv.z = v.z; } CSG_POPNAME_; } void CSG_Update(poly_t *poly) { CSG_PUSHNAME("Update[POLY]"); // *************************** // Update polygon fields: BBOX // *************************** CSG_Update(&poly->bbox, poly->vref, poly->vertcount); CSG_CHECK(poly); CSG_POPNAME_; } void CSG_Update(hull_t *hull) { CSG_PUSHNAME("Update[HULL]"); // ***************************************** // Update hull fields: BBOX, VREF, VERTCOUNT // ***************************************** poly_t *p; int vertcount = 0; int edgecount = 0; int facecount = 0; for(p = hull->face; p; p = p->next) { edgecount += p->vertcount; facecount++; } edgecount /= 2; vertcount = edgecount - facecount + 2; // Euler formula: V=E-F+2 CSG_FreeMem(hull->vref); hull->vref = (vref_t*)CSG_AllocMem(sizeof(vref_t), vertcount); hull->vertcount = 0; for(p = hull->face; p; p = p->next) { for(int i, n = 0; n < p->vertcount; n++) { for(i = 0; i < hull->vertcount; i++) { if(p->vref[n] == hull->vref[i]) break; } if(i < hull->vertcount) continue; CSG_ASSERT(hull->vertcount != vertcount, "connectivity error"); hull->vref[hull->vertcount++] = p->vref[n]; } } CSG_Update(&hull->bbox, hull->vref, hull->vertcount); CSG_CHECK(hull); CSG_POPNAME_; } void CSG_Update(hull_t *hull, sref_t surf_id) { CSG_PUSHNAME("Update[HULL,SURF_ID]"); // *********************************************** // Given a hull which was formed by CSG_Split, // compute the missing face which lies in surf_id. // *********************************************** // ******************** // Enumerate free edges // ******************** vref_t edge[CSG_MAX_VERTS_PER_POLY*2]; sref_t sref[CSG_MAX_VERTS_PER_POLY]; int edgecount = 0; for(poly_t *p = hull->face; p; p = p->next) { for(int n = 0; n < p->vertcount; n++) { int n2 = (n > 0) ? n-1 : p->vertcount-1; vref_t vert_id1 = p->vref[n2]; vref_t vert_id2 = p->vref[n]; int edgerefs = 1; for(poly_t *q = hull->face; q; q = q->next) { if(q == p) continue; for(int m = 0; m < q->vertcount; m++) { int m2 = (m > 0) ? m-1 : q->vertcount-1; vref_t r1 = q->vref[m2]; vref_t r2 = q->vref[m]; if(r1 == vert_id2 && r2 == vert_id1) { edgerefs++; break; } } #if !CSG_DEBUG if(m < q->vertcount) break; // slight optimization #endif } if(edgerefs == 1) { // ********************* // Add edge to free list // ********************* edge[edgecount*2 + 0] = vert_id1; // left vertex edge[edgecount*2 + 1] = vert_id2; // right vertex sref[edgecount++] = p->surf_id; #if CSG_DEBUG double tt1 = CSG_Distance(vert_id1, surf_id); double tt2 = CSG_Distance(vert_id2, surf_id); CSG_ASSERT(tt1 == 0.0, "wrong surface"); CSG_ASSERT(tt2 == 0.0, "wrong surface"); } else CSG_ASSERT(edgerefs == 2, "edgerefs > 2"); #else } #endif } } // *************************************** // Attach free edges together to form face // *************************************** poly_t *poly = CSG_Alloc(hull, edgecount, surf_id); for(int i = 0, j = 0; i < edgecount; i++) { vref_t vert_id1 = edge[j*2]; CSG_AddToPoly(poly, vert_id1, sref[j]); while(edge[1 + j*2] != vert_id1) { // NOTE: possible crash site if(++j >= edgecount) j = 0; } } CSG_Update(poly); CSG_Update(hull); CSG_POPNAME_; } int CSG_In(vref_t vref[], int vertcount, sref_t surf_id) { CSG_PUSHNAME("In/Intersect"); // ************************************************ // Intersection utility function. Returns 1 iff all // vertices (from POLY or HULL) are on "inside" of // surface plane. WARNING: This function does NOT // modify CSG_CODE_IN or CSG_CODE_OUT. // ************************************************ for(int n = 0; n < vertcount; n++) { if(CSG_Distance(vref[n], surf_id) < 0.0) { CSG_POPNAME(0); } } CSG_POPNAME(1); } int CSG_Intersect(bbox_t *bbox1, bbox_t *bbox2, int mask) { CSG_PUSHNAME("Intersect[BBOX,BBOX]"); // *************************************** // Intersection between two bounding boxes // *************************************** // ************************************************** // General note regarding intersection functions: // // Intersection functions return 1 iff object1 is // entirely outside or touching object2, 0 otherwise. // Additionally, the static variable CSG_CODE_IN is // set to 1 iff object1 is entirely inside or // touching object2, 0 otherwise. The static variable // CSG_CODE_OUT mirrors the returned value (normally, // it is not queried). If object1 is contained in the // boundary of object2 (i.e., a ploygon coplanar with // one face of a polyhedron) it is treated as being // outside. The exception to this rule is when a // polygon or polyhedron is tested against a single // plane - in this case, the polygon or polyhedron // being entirely coplanar results in an error. // ************************************************** CSG_CODE_OUT = 1; CSG_CODE_IN = 0; if(mask & 1) { if(bbox1->maxv.x <= bbox2->minv.x + CSG_MAXERR || bbox1->minv.x >= bbox2->maxv.x - CSG_MAXERR ) { CSG_POPNAME(1); } } if(mask & 2) { if(bbox1->maxv.y <= bbox2->minv.y + CSG_MAXERR || bbox1->minv.y >= bbox2->maxv.y - CSG_MAXERR ) { CSG_POPNAME(1); } } if(mask & 4) { if(bbox1->maxv.z <= bbox2->minv.z + CSG_MAXERR || bbox1->minv.z >= bbox2->maxv.z - CSG_MAXERR ) { CSG_POPNAME(1); } } CSG_CODE_OUT = 0; if(bbox1->minv.x >= bbox2->minv.x - CSG_MAXERR && bbox1->maxv.x <= bbox2->maxv.x + CSG_MAXERR && bbox1->minv.y >= bbox2->minv.y - CSG_MAXERR && bbox1->maxv.y <= bbox2->maxv.y + CSG_MAXERR && bbox1->minv.z >= bbox2->minv.z - CSG_MAXERR && bbox1->maxv.z <= bbox2->maxv.z + CSG_MAXERR ) { CSG_CODE_IN = 1; } CSG_POPNAME(0); } int CSG_Intersect(poly_t *poly1, sref_t surf_id) { CSG_PUSHNAME("Intersect[POLY,SURF_ID]"); // **************************************** // Intersection between polygon and surface // **************************************** CSG_CODE_OUT = 1; CSG_CODE_IN = 1; for(int n = 0; n < poly1->vertcount; n++) { double t = CSG_Distance(poly1->vref[n], surf_id); if(t > 0.0) CSG_CODE_OUT = 0; else if(t < 0.0) CSG_CODE_IN = 0; } CSG_ASSERT(!CSG_CODE_OUT || !CSG_CODE_IN, "invalid code"); CSG_POPNAME(CSG_CODE_OUT); } int CSG_Intersect(hull_t *hull1, sref_t surf_id) { CSG_PUSHNAME("Intersect[HULL,SURF_ID]"); // ************************************* // Intersection between hull and surface // ************************************* CSG_CODE_OUT = 1; CSG_CODE_IN = 1; for(int n = 0; n < hull1->vertcount; n++) { double t = CSG_Distance(hull1->vref[n], surf_id); if(t > 0.0) CSG_CODE_OUT = 0; else if(t < 0.0) CSG_CODE_IN = 0; } CSG_ASSERT(!CSG_CODE_OUT || !CSG_CODE_IN, "invalid code"); CSG_POPNAME(CSG_CODE_OUT); } int CSG_Intersect(poly_t *poly1, poly_t *poly2) { CSG_PUSHNAME("Intersect[POLY,POLY]"); // ********************************* // Intersection between two polygons // ********************************* int n; sref_t surf_id1 = poly1->surf_id & CSG_SURF_MASK; sref_t surf_id2 = poly2->surf_id & CSG_SURF_MASK; CSG_ASSERT(surf_id1 == surf_id2, "not coplanar"); int mask = CSG_SURF_POOL[surf_id1].mask; if(CSG_Intersect(&poly1->bbox, &poly2->bbox, mask)) { CSG_POPNAME(1); } // *********** // Inside test // *********** if(CSG_CODE_IN) { for(n = 0; n < poly2->vertcount; n++) { sref_t surf_id = poly2->sref[n]; int in = CSG_In(poly1->vref, poly1->vertcount, surf_id); if(!in) break; } if(n == poly2->vertcount) { CSG_POPNAME(0); } CSG_CODE_IN = 0; } // ************ // Outside test // ************ for(n = 0; n < poly1->vertcount; n++) { sref_t surf_id = poly1->sref[n] ^ CSG_SIDE_MASK; if(CSG_In(poly2->vref, poly2->vertcount, surf_id)) { CSG_POPNAME(CSG_CODE_OUT = 1); } } for(n = 0; n < poly2->vertcount; n++) { sref_t surf_id = poly2->sref[n] ^ CSG_SIDE_MASK; if(CSG_In(poly1->vref, poly1->vertcount, surf_id)) { CSG_POPNAME(CSG_CODE_OUT = 1); } } CSG_POPNAME(0); } int CSG_Intersect(hull_t *hull1, hull_t *hull2) { CSG_PUSHNAME("Intersect[HULL,HULL]"); // ************************************************* // Intersection between two hulls. WARNING: The // algorithm used here can sometimes fail, returning // a false result of 0 when in fact CSG_CODE_OUT // should have been set to 1. This happens when the // two hulls may be seperated by a plane, but not by // any of the planes referenced by the hull faces. // In this case, the program must be prepared to // recover gracefully. // // Consider, for example, the two trianglular prisms // defined by the vertices: // Prism A: (-1,-1,-1)(-1,+1,-1)(0,0,-1) // (-1,-1,+1)(-1,+1,+1)(0,0,+1) // Prism B: (+1,+1,+1)(+1,+1,-1)(0,+1,0) // (+1,-1,+1)(+1,-1,-1)(0,-1,0) // Of course in this case the bounding boxes would // indicate rejection, but if the geometry were // rotated slightly then the error would occur. // ************************************************* poly_t *p; if(CSG_Intersect(&hull1->bbox, &hull2->bbox, 7)) { CSG_POPNAME(1); } // *********** // Inside test // *********** if(CSG_CODE_IN) { for(p = hull2->face; p; p = p->next) { sref_t surf_id = p->surf_id; if(!CSG_In(hull1->vref, hull1->vertcount, surf_id)) { break; } } if(!p) { CSG_POPNAME(0); } CSG_CODE_IN = 0; } // ************ // Outside test // ************ for(p = hull1->face; p; p = p->next) { sref_t surf_id = p->surf_id ^ CSG_SIDE_MASK; if(CSG_In(hull2->vref, hull2->vertcount, surf_id)) { CSG_POPNAME(CSG_CODE_OUT = 1); } } for(p = hull2->face; p; p = p->next) { sref_t surf_id = p->surf_id ^ CSG_SIDE_MASK; if(CSG_In(hull1->vref, hull1->vertcount, surf_id)) { CSG_POPNAME(CSG_CODE_OUT = 1); } } CSG_POPNAME(0); } int CSG_Intersect(poly_t *poly1, hull_t *hull2) { CSG_PUSHNAME("Intersect[POLY,HULL]"); // **************************************************** // This function uses the slow brute-force intersection // testing algorithm of actually clipping one object to // another and determining if anything is left. It is // important that this function never fail. // **************************************************** sref_t surf_id1 = poly1->surf_id & CSG_SURF_MASK; int mask = CSG_SURF_POOL[surf_id1].mask; if(CSG_Intersect(&poly1->bbox, &hull2->bbox, mask)) { CSG_POPNAME(1); } if(CSG_Intersect(hull2, poly1->surf_id)) { CSG_POPNAME(1); } if(CSG_CODE_IN) { CSG_CODE_OUT = 1; CSG_CODE_IN = 0; CSG_POPNAME(1); } poly_t *tmp = CSG_Clone(NULL, poly1); CSG_CODE_OUT = 1; for(poly_t *p = hull2->face; p; p = p->next) { sref_t surf_id2 = p->surf_id & CSG_SURF_MASK; if(surf_id1 == surf_id2) { CSG_Free(tmp); CSG_POPNAME(1); } if(CSG_Clip(tmp, p->surf_id)) { // "tmp" is already free CSG_POPNAME(1); } } CSG_Free(tmp); CSG_POPNAME(CSG_CODE_OUT = 0); } int CSG_Intersect(poly_t *poly1, int edge1, poly_t *poly2) { CSG_PUSHNAME("Intersect[EDGE,POLY]"); // ****************************************** // Intersection between an edge and a polygon // ****************************************** int edge2 = (edge1 > 0) ? edge1-1 : poly1->vertcount-1; vref_t vert_id1 = poly1->vref[edge1]; vref_t vert_id2 = poly1->vref[edge2]; sref_t surf_id1 = poly1->sref[edge1]; sref_t surf_id2; if(CSG_Intersect(poly2, poly1->sref[edge1])) { CSG_POPNAME(1); } CSG_CODE_IN = 0; CSG_CODE_OUT = 1; for(int n = 0; n < poly2->vertcount; n++) { surf_id2 = poly2->sref[n] & CSG_SURF_MASK; if(surf_id1 == surf_id2) { CSG_POPNAME(1); } double t1 = CSG_Distance(vert_id1, poly2->sref[n]); double t2 = CSG_Distance(vert_id2, poly2->sref[n]); if(t1 <= 0.0 && t2 <= 0.0) { CSG_POPNAME(1); } } CSG_POPNAME(CSG_CODE_OUT = 0); } double CSG_Distance(vert_t &vert, sref_t surf_id) { CSG_PUSHNAME("Distance"); // **************************************************** // Distance from vertex to surface plane. If vert is in // the "inside" halfspace, a positive value is returned. // If vert is in the "outside" halfspace, a negative // value is returned. If the distance is less than or // equal to CSG_MAXERR, zero is returned. // **************************************************** surf_t *surf = &CSG_SURF_POOL[surf_id & CSG_SURF_MASK]; double dist = vert*surf->norm + surf->dist; if(fabs(dist) <= CSG_MAXERR) { CSG_POPNAME(0.0); } if(surf_id & CSG_SIDE_MASK) { CSG_POPNAME(-dist); } CSG_POPNAME(dist); } double CSG_Distance(vref_t vert_id, sref_t surf_id) { return CSG_Distance(CSG_VERT_POOL[vert_id], surf_id); } int CSG_Clip(poly_t *poly, sref_t surf_id) { CSG_PUSHNAME("Clip[POLY,SURF_ID]"); poly_t *pnew = CSG_Split(poly->parent, poly, surf_id); if(pnew) CSG_Free(pnew); CSG_POPNAME(poly->flags?0:1); } int CSG_Clip(hull_t *hull, sref_t surf_id) { CSG_PUSHNAME("Clip[HULL,SURF_ID]"); hull_t *hnew = CSG_Split(hull->parent, hull, surf_id); if(hnew) CSG_Free(hnew); CSG_POPNAME(hull->flags?0:1); } int CSG_Clip(poly_t *poly, poly_t *clip) { CSG_PUSHNAME("Clip[POLY,POLY]"); // *************************************************** // Assuming polygon is not entirely inside or entirely // outside of clipping volume polygon, clip polygon to // each intersecting edge. Returns 1 iff polygon is // clipped to nothing. // *************************************************** for(int n = 0; n < clip->vertcount; n++) { if(CSG_Intersect(clip, n, poly)) continue; if(CSG_Clip(poly, clip->sref[n])) { CSG_Messg("Clip[POLY]: WARNING: Recovering from bad intersect..."); CSG_POPNAME(1); } } CSG_POPNAME(0); } int CSG_Clip(hull_t *hull, hull_t *clip) { CSG_PUSHNAME("Clip[HULL,HULL]"); // ************************************************ // Assuming hull is not entirely inside or entirely // outside of clipping volume hull, clip hull to // each intersecting face. Returns 1 iff hull is // clipped to nothing. // ************************************************ for(poly_t *p = clip->face; p; p = p->next) { if(CSG_Intersect(p, hull)) continue; if(CSG_Clip(hull, p->surf_id)) { CSG_Messg("Clip[HULL]: WARNING: Recovering from bad intersect..."); CSG_POPNAME(1); } } CSG_POPNAME(0); } poly_t *CSG_Split(void *parent, poly_t *poly, sref_t surf_id) { CSG_PUSHNAME("Split[POLY]"); // ******************************************** // Recursively split polygon and all associated // structures. Outside fragment is returned. // ******************************************** CSG_ASSERT((surf_id & CSG_SURF_MASK) != (poly->surf_id & CSG_SURF_MASK), "coincident polys"); if(CSG_Intersect(poly, surf_id)) { if(poly->parent != parent) { CSG_Unlink(poly); CSG_Link(parent, poly); } CSG_POPNAME(poly); } if(CSG_CODE_IN) { CSG_POPNAME(NULL); } poly_t *pnew = CSG_Alloc(parent, 0, poly->surf_id); pnew->shape = poly->shape; for(poly_t *pnext, *p = poly->down; p; p = pnext) { pnext = p->next; CSG_Split(pnew, p, surf_id); } vert_t v1, v2 = CSG_VERT_POOL[poly->vref[poly->vertcount - 1]]; double t1, t2 = CSG_Distance(v2, surf_id); // *********************** // Allocate for worst-case // *********************** poly_t *split1 = CSG_Alloc(NULL, poly->vertcount+1, poly->surf_id); poly_t *split2 = CSG_Alloc(NULL, poly->vertcount+1, poly->surf_id); // Inner Fragment: split1 // Outer Fragment: split2 for(int n = 0; n < poly->vertcount; n++) { v1 = v2, v2 = CSG_VERT_POOL[poly->vref[n]]; t1 = t2, t2 = CSG_Distance(v2, surf_id); if(t2 > 0.0) { if(t1 < 0.0) { // ***************************************** // NOTE: To avoid inaccurate clipping, we // must avoid calling the vec3 "/" operator! // ***************************************** vert_t clip = v1*t2 - v2*t1; vref_t vert_id; clip.x /= t2 - t1; clip.y /= t2 - t1; clip.z /= t2 - t1; vert_id = CSG_AddToVertPool(clip); #if CSG_DEBUG double tt1 = CSG_Distance(vert_id, surf_id); double tt2 = CSG_Distance(vert_id, poly->surf_id); double tt3 = CSG_Distance(vert_id, poly->sref[n]); CSG_ASSERT(tt1==0.0&&tt2==0.0&&tt3==0.0, "clipping error"); #endif CSG_AddToPoly(split1, vert_id, surf_id); CSG_AddToPoly(split2, vert_id, poly->sref[n]); } CSG_AddToPoly(split1, poly->vref[n], poly->sref[n]); } else if(t2 < 0.0) { if(t1 > 0.0) { // ***************************************** // NOTE: To avoid inaccurate clipping, we // must avoid calling the vec3 "/" operator! // ***************************************** vert_t clip = v1*t2 - v2*t1; vref_t vert_id; clip.x /= t2 - t1; clip.y /= t2 - t1; clip.z /= t2 - t1; vert_id = CSG_AddToVertPool(clip); #if CSG_DEBUG double tt1 = CSG_Distance(vert_id, surf_id); double tt2 = CSG_Distance(vert_id, poly->surf_id); double tt3 = CSG_Distance(vert_id, poly->sref[n]); CSG_ASSERT(tt1==0.0&&tt2==0.0&&tt3==0.0, "clipping error"); #endif CSG_AddToPoly(split1, vert_id, poly->sref[n]); CSG_AddToPoly(split2, vert_id, surf_id ^ CSG_SIDE_MASK); } CSG_AddToPoly(split2, poly->vref[n], poly->sref[n]); } else { if(t1 < 0.0) { CSG_AddToPoly(split1, poly->vref[n], surf_id); CSG_AddToPoly(split2, poly->vref[n], poly->sref[n]); } else if(t1 > 0.0) { CSG_AddToPoly(split1, poly->vref[n], poly->sref[n]); CSG_AddToPoly(split2, poly->vref[n], surf_id ^ CSG_SIDE_MASK); } else CSG_ASSERT(0, "coincident edges"); } } CSG_Copy(poly, split1); CSG_Copy(pnew, split2); CSG_Free(split1); CSG_Free(split2); CSG_Update(poly); CSG_Update(pnew); #if CSG_DEBUG CSG_Intersect(poly, surf_id); CSG_ASSERT(CSG_CODE_IN, "failed"); CSG_Intersect(pnew, surf_id); CSG_ASSERT(CSG_CODE_OUT, "failed"); #endif CSG_POPNAME(pnew); } hull_t *CSG_Split(void *parent, hull_t *hull, sref_t surf_id) { CSG_PUSHNAME("Split[HULL]"); // ***************************************** // Recursively split hull and all associated // structures. Outside fragment is returned. // ***************************************** if(CSG_Intersect(hull, surf_id)) { if(hull->parent != parent) { CSG_Unlink(hull); CSG_Link(parent, hull); } CSG_POPNAME(hull); } if(CSG_CODE_IN) { CSG_POPNAME(NULL); } hull_t *hnew = CSG_Alloc(parent); hnew->shape = hull->shape; for(poly_t *pnext, *p = hull->face; p; p = pnext) { pnext = p->next; CSG_Split(hnew, p, surf_id); } for(hull_t *hnext, *h = hull->down; h; h = hnext) { hnext = h->next; CSG_Split(hnew, h, surf_id); } CSG_Update(hull, surf_id); CSG_Update(hnew, surf_id ^ CSG_SIDE_MASK); CSG_POPNAME(hnew); } void CSG_BooleanOp(hull_t *dst, hull_t *src, int target_depth, int op, int clip) { CSG_PUSHNAME("BooleanOp"); CSG_ASSERT(target_depth > dst->depth, "incompatible depths"); CSG_ASSERT(op == CSG_ADD || op == CSG_SUB, "unknown op"); if(target_depth - dst->depth == 1) { if(op == CSG_ADD) { hull_t *clone = CSG_Clone(NULL, src); CSG_BooleanAdd(dst, clone, clip); } else if(op == CSG_SUB) CSG_BooleanSub(dst, src); } else { for(hull_t *h = dst->down; h; h = h->next) { if(CSG_Intersect(src, h)) continue; CSG_BooleanOp(h, src, target_depth, op, CSG_CODE_IN ? 0 : 1); } } CSG_POPNAME_; } void CSG_BooleanAdd(poly_t *dst, poly_t *src, int clip) { CSG_PUSHNAME("BooleanAdd[POLY]"); // *********************************************** // Two-dimensional CSG boolean addition. Note that // CSG_RESOLVE_ADD_2D controls whether existing or // new polygons are split. // *********************************************** if(clip) { if(CSG_Clip(src, dst)) { CSG_POPNAME_; } } if(CSG_RESOLVE_ADD_2D == CSG_RESOLVE_KEEP_NEW) { CSG_BooleanSub(dst, src); } else if(CSG_RESOLVE_ADD_2D == CSG_RESOLVE_KEEP_OLD) { for(poly_t *p = dst->down; p; p = p->next) { if(CSG_Intersect(src, p)) continue; if(CSG_CODE_IN == 0) { int split = 0; for(int n = 0; n < p->vertcount; n++) { if(CSG_Intersect(p, n, src)) continue; poly_t *pnew = CSG_Split(NULL, src, p->sref[n]); CSG_BooleanAdd(dst, pnew, 0); split = 1; } CSG_ASSERT(split == 1, "intersection failure"); if(!split) continue; // for symmetry } CSG_Free(src); CSG_POPNAME_; } } src->shape = CSG_CURRENT_SHAPE; CSG_Link(dst, src); CSG_POPNAME_; } void CSG_BooleanAdd(hull_t *dst, hull_t *src, int clip) { CSG_PUSHNAME("BooleanAdd[HULL]"); // ************************************************ // Adds volume represented by "src" hull to volume // represented by children of "dst" hull, splitting // and re-polygonalizing as necessary. Note that // CSG_RESOLVE_ADD_3D controls whether existing or // new volumes are split. // ************************************************ if(clip) { if(CSG_Clip(src, dst)) { CSG_POPNAME_; } } if(CSG_RESOLVE_ADD_3D == CSG_RESOLVE_KEEP_NEW) { // ******************************************* // FIXME: Inefficient! Polygonalization should // occur only after inclusion of new hull. // ******************************************* CSG_BooleanSub(dst, src); } else if(CSG_RESOLVE_ADD_3D == CSG_RESOLVE_KEEP_OLD) { for(hull_t *h = dst->down; h; h = h->next) { if(CSG_Intersect(src, h)) continue; if(CSG_CODE_IN == 0) { int split = 0; for(poly_t *p = h->face; p; p = p->next) { if(CSG_Intersect(p, src)) continue; hull_t *hnew = CSG_Split(NULL, src, p->surf_id); CSG_BooleanAdd(dst, hnew, 0); split = 1; } if(!split) continue; } CSG_Free(src); CSG_POPNAME_; } } src->shape = CSG_CURRENT_SHAPE; CSG_Link(dst, src); CSG_Polygonalize(src); CSG_POPNAME_; } void CSG_BooleanSub(poly_t *dst, poly_t *src) { CSG_PUSHNAME("BooleanSub[POLY]"); // **************************************************** // Subtracts polygon represented by "src" poly from all // polygons represented by children of "dst" poly, // splitting as necessary. // **************************************************** for(poly_t *pnext, *p = dst->down; p; p = pnext) { pnext = p->next; if(CSG_Intersect(p, src)) continue; if(CSG_CODE_IN == 0) { int split = 0; for(int n = 0; n < src->vertcount; n++) { if(CSG_Intersect(src, n, p)) continue; CSG_Split(dst, p, src->sref[n]); split = 1; } CSG_ASSERT(split == 1, "intersection failure"); if(!split) continue; // for symmetry } CSG_Free(p); } CSG_POPNAME_; } void CSG_BooleanSub(hull_t *dst, hull_t *src) { CSG_PUSHNAME("BooleanSub[HULL]"); // *************************************************** // Subtracts volume represented by "src" hull from all // volumes represented by children of "dst" hull, // splitting them and re-polygonalizing as necessary. // *************************************************** for(hull_t *hnext, *h = dst->down; h; h = hnext) { hnext = h->next; if(CSG_Intersect(h, src)) continue; if(CSG_CODE_IN == 0) { int split = 0; for(poly_t *p = src->face; p; p = p->next) { if(CSG_Intersect(p, h)) continue; CSG_Split(dst, h, p->surf_id); split = 1; } if(!split) continue; } CSG_Free(h); } // FIXME: We need to write the proper polygonalizer.. CSG_ASSERT(0, "polygonalization for boolean subtraction??"); CSG_Polygonalize(src); CSG_POPNAME_; } void CSG_PTrim(poly_t *face) { CSG_PUSHNAME("PTrim"); // ***************************************************** // Polygon trimming: used internally in CSG_Polygonalize // ***************************************************** if(!face->down) { CSG_POPNAME_; // nothing left } hull_t *hull = (hull_t*)face->parent; if(hull->depth >= CSG_POLYGONALIZATION_DEPTH+1) { poly_t *t = NULL; for(poly_t *p = ((hull_t*)hull->parent)->face; p; p = p->next) { if(p->surf_id == face->surf_id) { t = CSG_Clone(NULL, p); break; } } if(t) { CSG_Clone(t, t); for(ccof_t *cc = CSG_CCOF[hull->depth-1]; cc; cc = cc->next) { if(CSG_Intersect(t, cc->face)) continue; if(CSG_CODE_IN) { CSG_Free(t); t = NULL; break; } CSG_BooleanSub(t, cc->face); } if(t) { for(poly_t *p = t->down; p; p = p->next) { CSG_BooleanSub(face, p); } CSG_Free(t); } } } for(ccof_t *cc = CSG_CCOF[hull->depth]; cc; cc = cc->next) { if(!face->down) { CSG_POPNAME_; // nothing left } if(CSG_Intersect(face, cc->face)) continue; CSG_BooleanSub(face, cc->face); } CSG_POPNAME_; } void CSG_PFlip(poly_t *poly) { CSG_PUSHNAME("PFlip"); // ************************************ // Reverse the orientation of a polygon // ************************************ for(int n = 0; n < poly->vertcount/2; n++) { int vn = poly->vertcount - n - 1; int sn = n ? poly->vertcount - n : 0; vref_t vtmp = poly->vref[n]; sref_t stmp = poly->sref[n]; poly->vref[n] = poly->vref[vn], poly->vref[vn] = vtmp; poly->sref[n] = poly->sref[sn], poly->sref[sn] = stmp; } poly->surf_id ^= CSG_SIDE_MASK; CSG_POPNAME_; } void CSG_Polygonalize(hull_t *hull) { CSG_PUSHNAME("Polygonalize"); // ****************************************************** // This function is used after each CSG boolean operation // to update the current polygon mesh. // ****************************************************** for(poly_t *p = hull->face; p; p = p->next) { int i; CSG_GenCCOF(p); if(hull->depth >= CSG_POLYGONALIZATION_DEPTH+1) { hull_t *parent = (hull_t*)hull->parent; for(poly_t *q = parent->face; q; q = q->next) { if(q->surf_id != p->surf_id) continue; CSG_BooleanSub(q, p); } } if(hull->depth >= CSG_POLYGONALIZATION_DEPTH) { CSG_Clone(p, p); CSG_PTrim(p); } for(i = hull->depth; i <= CSG_MAX_DEPTH; i += 2) { for(ccof_t *cc = CSG_CCOF[i]; cc; cc = cc->next) { CSG_BooleanSub(cc->face, p); } } for(i = hull->depth+1; i <= CSG_MAX_DEPTH; i += 2) { for(ccof_t *cc = CSG_CCOF[i]; cc; cc = cc->next) { poly_t *a = CSG_Clone(NULL, p); CSG_PFlip(a); CSG_BooleanAdd(cc->face, a, 1); hull_t *parent = (hull_t*)cc->face->parent; for(hull_t *h = parent->down; h; h = h->next) { for(poly_t *q = h->face; q; q = q->next) { if(q->surf_id != cc->face->surf_id) continue; CSG_BooleanSub(cc->face, q); break; } } } } } CSG_POPNAME_; } void CSG_Check(poly_t *poly) { CSG_PUSHNAME("Check[POLY]"); if(poly->depth > 0) { poly_t *parent = (poly_t*)poly->parent; if(CSG_Intersect(poly, parent)) CSG_Error("Check[POLY]: child not contained"); if(CSG_CODE_IN == 0) CSG_Error("Check[POLY]: child not contained"); } if(poly->down) { for(poly_t *p1 = poly->down; p1; p1 = p1->next) for(poly_t *p2 = p1->next; p2; p2 = p2->next) { if(!CSG_Intersect(p1, p2)) CSG_Error("Check[POLY]: children not disjoint"); } } if(poly->next && !poly->parent) { CSG_Error("Check[POLY]: poly has siblings, but no parent"); } if(poly->vertcount < 3) { CSG_Error("Check[POLY]: too few vertices"); } if(poly->vertcount > CSG_MAX_VERTS_PER_POLY) { CSG_Error("Check[POLY]: too many vertices"); } sref_t surf_id = poly->surf_id & CSG_SURF_MASK; if(surf_id >= (vref_t)CSG_SURF_COUNT) { CSG_Error("Check[POLY]: incorrect surface reference"); } for(int n = 0; n < poly->vertcount; n++) { int n2 = (n < poly->vertcount-1) ? n+1 : 0; vref_t vert_id1 = poly->vref[n]; sref_t surf_id1 = poly->sref[n] & CSG_SURF_MASK; if(vert_id1 >= (vref_t)CSG_VERT_COUNT) { CSG_Error("Check[POLY]: incorrect vertex reference"); } if(surf_id1 >= (vref_t)CSG_SURF_COUNT) { CSG_Error("Check[POLY]: incorrect surface reference"); } if(surf_id1 == surf_id) { CSG_Error("Check[POLY]: duplicate surface reference"); } double tt1 = CSG_Distance(vert_id1, poly->surf_id); double tt2 = CSG_Distance(vert_id1, poly->sref[n2]); double tt3 = CSG_Distance(vert_id1, poly->sref[n]); if(tt1 != 0.0 || tt2 != 0.0 || tt3 != 0.0) { CSG_Error("Check[POLY]: vertex not on surface"); } for(int i = 0; i < poly->vertcount; i++) { if(i == n) continue; vref_t vert_id2 = poly->vref[i]; sref_t surf_id2 = poly->sref[i] & CSG_SURF_MASK; if(vert_id2 == vert_id1) { CSG_Error("Check[POLY]: duplicate vertex reference"); } if(surf_id2 == surf_id1) { CSG_Error("Check[POLY]: duplicate surface reference"); } if(i == n2) continue; tt1 = CSG_Distance(vert_id1, poly->sref[i]); if(tt1 < 0.0) { CSG_Error("Check[POLY]: polygon not convex"); } else if(tt1 == 0.0) { CSG_Messg("Check[POLY]: WARNING: polygon not strictly convex"); } } } CSG_POPNAME_; } void CSG_Check(hull_t *hull) { CSG_PUSHNAME("Check[HULL]"); if(hull->depth > 0) { hull_t *parent = (hull_t*)hull->parent; if(CSG_Intersect(hull, parent)) CSG_Error("Check[HULL]: child not contained"); if(CSG_CODE_IN == 0) CSG_Error("Check[HULL]: child not contained"); } if(hull->down) { for(hull_t *h1 = hull->down; h1; h1 = h1->next) for(hull_t *h2 = h1->next; h2; h2 = h2->next) { if(!CSG_Intersect(h1, h2)) CSG_Error("Check[HULL]: children not disjoint"); } } if(hull->next && !hull->parent) { CSG_Error("Check[HULL]: hull has siblings, but no parent"); } if(hull->vertcount < 4) { CSG_Error("Check[HULL]: too few vertices"); } if(hull->vertcount > CSG_MAX_VERTS_PER_HULL) { CSG_Error("Check[HULL]: too many vertices"); } int facecount = CSG_Count(hull->face); if(facecount < 4) { CSG_Error("Check[HULL]: too few faces"); } if(facecount > CSG_MAX_FACES_PER_HULL) { CSG_Error("Check[HULL]: too many faces"); } for(poly_t *p = hull->face; p; p = p->next) { sref_t surf_id1 = p->surf_id & CSG_SURF_MASK; for(poly_t *q = hull->face; q; q = q->next) { if(q == p) continue; sref_t surf_id2 = q->surf_id & CSG_SURF_MASK; if(surf_id1 == surf_id2) { CSG_Error("Check[HULL]: duplicate surface reference"); } } for(int n = 0; n < hull->vertcount; n++) { vref_t vert_id1 = hull->vref[n]; double tt1 = CSG_Distance(vert_id1, p->surf_id); if(tt1 < 0.0) { CSG_Error("Check[HULL]: polygon not convex"); } else if(tt1 == 0.0) { int i; for(i = 0; i < p->vertcount; i++) { if(p->vref[i] == vert_id1) break; } if(i == p->vertcount) { // *********************************************** // Vertex "vert_id1" does not exist in polygon "p" // *********************************************** CSG_Messg("Check[HULL]: WARNING: polygon not strictly convex"); } } } } CSG_POPNAME_; } hull_t *CSG_SolidCube(double x1, double y1, double z1, double x2, double y2, double z2) { CSG_PUSHNAME("SolidCube"); // ***************************************************** // This creates a solid cube from the coordinates given. // The vertex indices are as follows: // // 6---7 // 2-+-3 | // | | | | // | 4-+-5 // 0---1 // ***************************************************** static vref_t vtab[] = {0,1,3,2, 4,6,7,5, 0,2,6,4, 1,5,7,3, 0,4,5,1, 2,3,7,6}; static sref_t stab[] = {2,4,3,5, 4,2,5,3, 4,0,5,1, 0,4,1,5, 0,2,1,3, 2,0,3,1}; hull_t *hull = CSG_Alloc(NULL); sref_t surf_id[6]; vref_t vert_id[8]; int i; for(i = 0; i < 8; i++) { vert_t vert; vert.x = (i & 1) ? x2 : x1; vert.y = (i & 2) ? y2 : y1; vert.z = (i & 4) ? z2 : z1; vert_id[i] = CSG_AddToVertPool(vert); } for(i = 0; i < 6; i++) { int i1 = vtab[i*4+0]; int i2 = vtab[i*4+1]; int i3 = vtab[i*4+2]; surf_id[i] = CSG_AddToSurfPool(vert_id, i1, i2, i3); } for(i = 0; i < 6; i++) { poly_t *poly = CSG_Alloc(hull, 4, surf_id[i]); for(int n = 0; n < 4; n++) { vref_t vref = vert_id[vtab[n + i*4]]; sref_t sref = surf_id[stab[n + i*4]]; CSG_AddToPoly(poly, vref, sref); } CSG_Update(poly); } CSG_Update(hull); CSG_POPNAME(hull); }
This page © Bernie Freidin, 2000.