Flythrough Demo Source
// **************************************************************************
// 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.