/* * Copyright (c) 1993 Silicon Graphics, Inc. * * Permission to use, copy, modify, distribute, and sell this software * and its documentation for any purpose is hereby granted without * fee, provided that (i) the above copyright notices and this * permission notice appear in all copies of the software and related * documentation, and (ii) the name of Silicon Graphics may not be * used in any advertising or publicity relating to the software * without the specific, prior written permission of Silicon Graphics. * * THE SOFTWARE IS PROVIDED "AS-IS" AND WITHOUT WARRANTY OF ANY KIND, * EXPRESS, IMPLIED OR OTHERWISE, INCLUDING WITHOUT LIMITATION, ANY * WARRANTY OF MERCHANTABILITY OR FITNESS FOR A PARTICULAR PURPOSE. * * IN NO EVENT SHALL SILICON GRAPHICS BE LIABLE FOR ANY SPECIAL, * INCIDENTAL, INDIRECT OR CONSEQUENTIAL DAMAGES OF ANY KIND, OR ANY * DAMAGES WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR PROFITS, * WHETHER OR NOT ADVISED OF THE POSSIBILITY OF DAMAGE, AND ON ANY * THEORY OF LIABILITY, ARISING OUT OF OR IN CONNECTION WITH THE USE * OR PERFORMANCE OF THIS SOFTWARE. * */ /* * pfobj.c: $Revision: 1.45 $ $Date: 1994/11/16 03:24:21 $ */ #include #include #include #include #include #include "pfsgi.h" #include "pfutil.h" pfNode *pfuSpatialize(pfList *gsets, float geodeSize, long geodeChild); pfGroup *pfuRespatialize(pfGroup *grp, long branch); /* length of longest input line in ".obj" file (including continuations) */ #define BUFFER_SIZE 20000 /* maximum number of vertices in a single polygon */ #define FACE_SIZE 4096 /* initial allocation size for growable arrays */ #define CHUNK 20000 /* how many different material library files */ #define MTL_LIBS 128 /* case insensitive string equality test */ #define SAME(_a, _b) (strcasecmp(_a,_b) == 0) /* list of textures defined by Wavefront material files */ typedef struct TEX { char *name; pfTexture *texture; float su; /* u-axis texture scale factor */ float sv; /* v-axis texture scale factor */ } TEX; #define NUMTEX 512 static TEX TexList[NUMTEX]; static long TexCount = 0; /* list of materials defined by Wavefront material files */ typedef struct MTL { char *name; pfGeoState *gstate; pfMaterial *material; pfTexture *texture; long refl_mapped; } MTL; #define NUMMTL 512 static MTL MtlList[NUMMTL]; static long MtlCount = 0; /* current material -- latest one selected or defined (or NULL) */ static MTL *CurMtl = NULL; static pfGeoState *DefaultGState = NULL; static pfMaterial *DefaultMtl = NULL; static void *sharedArena = NULL; /* number of input lines skipped (recognized but not processed) or unknown */ static long numSkip = 0; static long numOther = 0; /* function type and argument declarations */ static void loadMtl(char *fileName); static FILE *openFile(char *fileName); extern long pfuPreDrawReflMap(pfTraverser *trav, void *data); extern long pfuPostDrawReflMap(pfTraverser *trav, void *data); static pfGeoState *defaultGeoState(void); static pfMaterial *defaultMaterial(void); #define GROW(_v, _t) \ if (_v == NULL) \ { \ _v ## Available = CHUNK; \ _v = (_t *)pfMalloc(sizeof(_t)*_v ## Available, NULL); \ } \ else \ if (_v ## Count >= _v ## Available) \ { \ _v ## Available *= 2; \ _v = (_t *)pfRealloc(_v, sizeof(_t)*_v ## Available); \ } /* * LoadObj -- load Wavefront ".obj" files into IRIS Performer */ extern pfNode* LoadObj (char *fileName, pfGeoState *gs) { FILE *objFile; pfuPoly polygon; pfuBuilder *builder; pfGroup *group; char buffer[BUFFER_SIZE]; char token[BUFFER_SIZE]; char *next = NULL; char *backslash = NULL; int width = 0; long numTris = 0; long numGroups = 0; /* growable vertex coordinate list (X, Y, Z) */ pfVec3 *v = NULL; uint vCount = 0; uint vAvailable = 0; /* growable vertex normal list (Nx, Ny, Nz) */ pfVec3 *n = NULL; uint nCount = 0; uint nAvailable = 0; /* growable texture coordinate list (S, T )*/ pfVec2 *t = NULL; uint tCount = 0; uint tAvailable = 0; /* tmp count vars */ int i, j; pfList *gsetList; pfList *reflGSetList; double startTime = pfGetTime(); double elapsedTime = 0.0f; /* get pointer to IRIS Performer shared memory arena */ if (sharedArena == NULL) sharedArena = pfGetSharedArena(); /* open Wavefront ".obj" file file */ if ((objFile = openFile(fileName)) == NULL) return NULL; /* start with caller's geostate */ DefaultGState = gs; /* initialize utility library triangle/geoset builder */ builder = pfuNewBuilder(); reflGSetList = pfNewList(sizeof(pfGeoSet*), 10, NULL); gsetList = pfNewList(sizeof(pfGeoSet*), 10, NULL); /* read Wavefront ".obj" file */ while (fgets(buffer, BUFFER_SIZE, objFile) != NULL) { /* concatenate continuation lines */ while ((backslash = strchr(buffer, '\\')) != NULL) if (fgets(backslash, BUFFER_SIZE - strlen(buffer), objFile) == NULL) break; /* find first non-"space" character in line */ for (next = buffer; *next != '\0' && isspace(*next); next++) /* EMPTY */ {}; /* skip blank lines and comments ('$' is comment in "cow.obj") */ if (*next == '\0' || *next == '#' || *next == '!' || *next == '$') continue; /* extract token */ sscanf(next, "%s%n", token, &width); next += width; /* identify token */ if (SAME(token, "v")) { /* enlarge vertex coordinate list */ GROW(v, pfVec3); /* set default values for vertex coordinate */ v[vCount][0] = v[vCount][1] = v[vCount][2] = 0.0f; /* read vertex coordinate into list */ sscanf(next, "%f %f %f", &v[vCount][PF_X], &v[vCount][PF_Y], &v[vCount][PF_Z]); /* advance vertex count */ ++vCount; } else if (SAME(token, "vn")) { /* enlarge vertex normal list */ GROW(n, pfVec3); /* set default values for vertex normal */ n[nCount][0] = n[nCount][1] = n[nCount][2] = 0.0f; /* read vertex normal into list */ sscanf(next, "%f %f %f", &n[nCount][PF_X], &n[nCount][PF_Y], &n[nCount][PF_Z]); /* advance normal count */ ++nCount; } else if (SAME(token, "vt")) { /* enlarge texture coordinate list */ GROW(t, pfVec2); /* set default values for vertex normal */ t[tCount][0] = t[tCount][1] = 0.0f; /* read texture coordinate into list */ sscanf(next, "%f %f", &t[tCount][0], &t[tCount][1]); /* advance texture coordinate count */ ++tCount; } else if (SAME(token, "g")) { ++numGroups; } else if (SAME(token, "f") || SAME(token, "fo")) { long count; int textureValid = 1; int normalsValid = 1; int vi[FACE_SIZE]; int ti[FACE_SIZE]; int ni[FACE_SIZE]; char *slash; char vertexData[256]; /* parse vertex data from input buffer */ for (count = 0; count < FACE_SIZE; count++) { /* read the next vertices' data packet */ if (sscanf(next, "%s%n", vertexData, &width) != 1) break; /* advance next pointer past data packet ("n/n/n") */ next += width; /* get vertex coordinate index */ vi[count] = (int)strtol(vertexData, NULL, 10); /* get texture coordinate index */ ti[count] = 0; if ((slash = strchr(vertexData, '/')) == NULL || (ti[count] = (int)strtol(slash+1, NULL, 10)) == 0) textureValid = 0; /* get vertex normal index */ ni[count] = 0; if (slash == NULL || (slash = strchr(slash+1, '/')) == NULL || (ni[count] = (int)strtol(slash+1, NULL, 10)) == 0) normalsValid = 0; /* * form cannonical indices: * convert ".obj" 1-based indices to 0-based (subtract 1) * convert negative indices to positive (count from 0) */ if (vi[count] >= 0) vi[count] -= 1; else vi[count] = vCount - vi[count]; if (ti[count] >= 0) ti[count] -= 1; else ti[count] = tCount - ti[count]; if (ni[count] >= 0) ni[count] -= 1; else ni[count] = nCount - ni[count]; } polygon.numVerts = count; if (CurMtl && CurMtl->refl_mapped) polygon.tbind = PFGS_PER_PRIM; else if (textureValid) polygon.tbind = PFGS_PER_VERTEX; else polygon.tbind = PFGS_OFF; if (normalsValid) polygon.nbind = PFGS_PER_VERTEX; else polygon.nbind = PFGS_OFF; polygon.cbind = PFGS_OFF; for (i = 0; i < count; i++) { pfCopyVec3(polygon.coords[i], v[vi[i]]); if (polygon.tbind == PFGS_PER_VERTEX) pfCopyVec2(polygon.texCoords[i], t[ti[i]]); if (polygon.nbind == PFGS_PER_VERTEX) pfCopyVec3(polygon.norms[i], n[ni[i]]); } pfuAddPoly(builder, &polygon); numTris += count-2; /* drain the builder before it gets too huge */ if (pfuGetNumTris(builder) > 500) { pfList *newGSets = pfuMakeGSets(builder); for (j=0; jgstate); else { if (!DefaultGState) DefaultGState = defaultGeoState(); pfGSetGState(gset, DefaultGState); } } if (CurMtl && CurMtl->refl_mapped) pfCombineLists(reflGSetList, reflGSetList, newGSets); else pfCombineLists(gsetList, gsetList, newGSets); } } else if (SAME(token, "usemtl")) { char mtlName[PF_MAXSTRING]; sscanf(next, "%s", mtlName); for (i = 0; i < MtlCount; i++) if (!strcmp(mtlName, MtlList[i].name)) break; if (i == MtlCount) { pfNotify(PFNFY_WARN, PFNFY_RESOURCE, "Could not find material %s", mtlName); CurMtl = NULL; } else { pfList *newGSets = pfuMakeGSets(builder); for (j=0; jgstate); else { if (!DefaultGState) DefaultGState = defaultGeoState(); pfGSetGState(gset, DefaultGState); } } if (CurMtl && CurMtl->refl_mapped) pfCombineLists(reflGSetList, reflGSetList, newGSets); else pfCombineLists(gsetList, gsetList, newGSets); CurMtl = &MtlList[i]; /* new material */ } } else if (SAME(token, "mtllib")) { char fName[PF_MAXSTRING]; static char *mtlList[MTL_LIBS]; static int mtlCount = 0; sscanf(next, "%s", fName); /* have we seen this library before ? */ for (i = 0; i < mtlCount; i++) if (strcmp(fName, mtlList[i]) == 0) break; if (i >= mtlCount) { mtlList[mtlCount++] = strdup(fName); loadMtl(fName); } else { printf("Note: material library %s already loaded\n", fName); } } else if (SAME(token, "bevel") || SAME(token, "bmat") || SAME(token, "bsp") || SAME(token, "bzp") || SAME(token, "c_interp") || SAME(token, "cdc") || SAME(token, "con") || SAME(token, "cstype") || SAME(token, "ctech") || SAME(token, "curv") || SAME(token, "curv2") || SAME(token, "d_interp") || SAME(token, "deg") || SAME(token, "end") || SAME(token, "hole") || SAME(token, "l") || SAME(token, "lod") || SAME(token, "maplib") || SAME(token, "mg") || SAME(token, "o") || SAME(token, "p") || SAME(token, "param") || SAME(token, "res") || SAME(token, "s") || SAME(token, "scrv") || SAME(token, "shadow_obj") || SAME(token, "sp") || SAME(token, "stech") || SAME(token, "step") || SAME(token, "surf") || SAME(token, "trace_obj") || SAME(token, "trim") || SAME(token, "usemap") || SAME(token, "vp")) ++numSkip; else { printf(" unrecognized: %s", buffer); ++numOther; } } /* close Wavefront ".obj" file */ fclose(objFile); /* release dynamically allocated vertex, normal, and texture data */ if (v != NULL) pfFree(v); if (n != NULL) pfFree(n); if (t != NULL) pfFree(t); /* convert current face list into one or more geosets */ { pfList *newGSets = pfuMakeGSets(builder); for (j=0; jgstate); else { if (!DefaultGState) DefaultGState = defaultGeoState(); pfGSetGState(gset, DefaultGState); } } if (CurMtl && CurMtl->refl_mapped) pfCombineLists(reflGSetList, reflGSetList, newGSets); else pfCombineLists(gsetList, gsetList, newGSets); } { pfNode *child; group = pfNewGroup(); if (pfGetNum(gsetList) > 0) { child = pfuSpatialize(gsetList, 0.0f, 8); pfAddChild(group, child); } if (pfGetNum(reflGSetList) > 0) { child = pfuSpatialize(reflGSetList, 0.0f, 8); pfAddChild(group, child); pfNodeTravFuncs(child, PFTRAV_DRAW, pfuPreDrawReflMap, pfuPostDrawReflMap); } pfDelete(gsetList); pfDelete(reflGSetList); pfuDelBuilder(builder); } /* print statistics */ if(pfGetNotifyLevel() >= PFNFY_INFO) { elapsedTime = pfGetTime() - startTime; fprintf(stderr, "LoadObj:\n"); fprintf(stderr, " file name = %s\n", fileName); fprintf(stderr, " skipped tokens = %ld\n", numSkip); fprintf(stderr, " unrecognized tokens = %ld\n", numOther); fprintf(stderr, " groups processed = %ld\n", numGroups); fprintf(stderr, " vertex coordinates = %ld\n", vCount); fprintf(stderr, " vertex normals = %ld\n", nCount); fprintf(stderr, " texture coordinates = %ld\n", tCount); fprintf(stderr, " triangular faces = %ld\n", numTris); if (elapsedTime > 0.0f) { fprintf(stderr, " loading time = %12.3f sec\n", elapsedTime); fprintf(stderr, " loading rate = %12.3f tri/sec\n", numTris/elapsedTime); } } /* return address of hierarchy to caller */ return (pfNode*)group; } /* * Make a reasonable default geostate */ static pfGeoState * defaultGeoState (void) { static pfGeoState *geostate = NULL; /* allocate and initialize geostate only on first call */ if (geostate == NULL) { geostate = pfNewGState(pfGetSharedArena()); pfGStateAttr(geostate, PFSTATE_FRONTMTL, defaultMaterial()); } /* return pointer to default geostate */ return geostate; } /* * Make a reasonable default material */ static pfMaterial * defaultMaterial (void) { static pfMaterial *material = NULL; if (material == NULL) { material = pfNewMtl(pfGetSharedArena()); pfMtlColor(material, PFMTL_AMBIENT, 0.1f, 0.1f, 0.1f); pfMtlColor(material, PFMTL_SPECULAR, 0.8f, 0.8f, 0.8f); pfMtlShininess(material, 10.0f); if (pfuGetMesherMode(PFUMESH_SHOW_TSTRIPS)) pfMtlColorMode(material, PFMTL_FRONT, LMC_AD); else pfMtlColorMode(material, PFMTL_FRONT, LMC_COLOR); } /* return pointer to default material */ return material; } /* * Read and remember wavefront-format (".mtl") file */ static void loadMtl (char *fileName) { FILE *mtlFile; char buffer[BUFFER_SIZE]; char token[BUFFER_SIZE]; char *next; char *backslash; int width = 0; /* open file */ if ((mtlFile = openFile(fileName)) == NULL) return; /* Generate Default Material */ if (DefaultMtl == NULL) { CurMtl = &MtlList[MtlCount++]; CurMtl->material = DefaultMtl = defaultMaterial(); CurMtl->name = strdup("default"); CurMtl->refl_mapped = 0; CurMtl->gstate = pfNewGState(sharedArena); pfGStateAttr(CurMtl->gstate, PFSTATE_FRONTMTL, CurMtl->material); } /* read Wavefront ".mtl" file */ while (fgets(buffer, BUFFER_SIZE, mtlFile) != NULL) { /* concatenate continuation lines */ while ((backslash = strchr(buffer, '\\')) != NULL) if (fgets(backslash, BUFFER_SIZE - strlen(buffer), mtlFile) == NULL) break; /* find first non-"space" character in line */ for (next = buffer; *next != '\0' && isspace(*next); next++) /* EMPTY */ {}; /* skip blank lines and comments ('$' is comment in "cow.obj") */ if (*next == '\0' || *next == '#' || *next == '!' || *next == '$') continue; /* extract token */ sscanf(next, "%s%n", token, &width); next += width; /* identify token */ if (SAME(token, "newmtl")) { if (MtlCount >= NUMMTL) { pfNotify(PFNFY_WARN, PFNFY_RESOURCE, "LoadObj() Too many materials."); } else { char mtlname[PF_MAXSTRING]; sscanf(next, "%s", mtlname); CurMtl = &MtlList[MtlCount++]; CurMtl->material = pfNewMtl(sharedArena); if(pfuGetMesherMode(PFUMESH_SHOW_TSTRIPS)) pfMtlColorMode(CurMtl->material, PFMTL_FRONT, LMC_AD); else pfMtlColorMode(CurMtl->material, PFMTL_FRONT, LMC_COLOR); CurMtl->name = strdup(mtlname); CurMtl->refl_mapped = 0; CurMtl->gstate = pfNewGState(sharedArena); pfGStateAttr(CurMtl->gstate, PFSTATE_FRONTMTL, CurMtl->material); pfGStateMode(CurMtl->gstate, PFSTATE_ENTEXTURE, 0); } } else if (SAME(token, "Ka")) { float r = 0.0f, g = 0.0f, b = 0.0f; sscanf(next, "%f %f %f", &r, &g, &b); pfMtlColor(CurMtl->material, PFMTL_AMBIENT, r, g, b); } else if (SAME(token, "Kd")) { float r = 0.0f, g = 0.0f, b = 0.0f; sscanf(next, "%f %f %f", &r, &g, &b); pfMtlColor(CurMtl->material, PFMTL_DIFFUSE, r, g, b); } else if (SAME(token, "Ks")) { float r = 0.0f, g = 0.0f, b = 0.0f; sscanf(next, "%f %f %f", &r, &g, &b); pfMtlColor(CurMtl->material, PFMTL_SPECULAR, r, g, b); } else if (SAME(token, "Ns")) { float shininess = 0.0f; sscanf(next, "%f", &shininess); pfMtlShininess(CurMtl->material, shininess); } else if (SAME(token, "map_Kd")) { char texName[PF_MAXSTRING]; char texPath[PF_MAXSTRING]; static char texSuffix[5][8] = {".rgb", ".rgba", ".int", ".inta", ".bw"}; char *suffix; pfTexture *tex = NULL; long i, j, texFound = 0, comp, foo; ulong *image; float su = 1.0f; float sv = 1.0f; sscanf(next, "%s", texName); /* if "-s" was seen then parse: "map_Kd -s su sv sw name" */ if (strcmp(texName, "-s") == 0) sscanf(next, "-s %f %f %*f %s", &su, &sv, texName); for (j=0; j<5; j++) { /* Convert texture name from blah.tex to blah.rgb etc */ if ((suffix = strrchr(texName, (int)'.')) != NULL) *suffix = '\0'; strcat(texName, texSuffix[j]); /* Locate texture in list of textures */ for (i = 0; i < TexCount; i++) { if (!strcmp(texName, TexList[i].name)) { texFound = 1; break; } } if (texFound) break; } /* Texture is not on list, try to find texture file */ if (!texFound) { for (j=0; j<5; j++) { /* Convert texture name from blah.tex to blah.rgb etc */ if ((suffix = strrchr(texName, (int)'.')) != NULL) *suffix = '\0'; strcat(texName, texSuffix[j]); if (pfFindFile(texName, texPath, R_OK)) { if (TexCount >= NUMTEX) { pfNotify(PFNFY_WARN, PFNFY_RESOURCE, "LoadObj() Too many textures"); tex = NULL; } else { tex = pfNewTex(sharedArena); pfLoadTexFile(tex, texPath); TexList[TexCount].name = strdup(texName); TexList[TexCount].texture = tex; TexList[TexCount].su = su; TexList[TexCount].sv = sv; TexCount++; } texFound = 1; break; } } if (!texFound) { if ((suffix = strrchr(texName, (int)'.')) != NULL) *suffix = '\0'; pfNotify(PFNFY_WARN, PFNFY_RESOURCE, "Could not find texture file %s", texName); tex = NULL; } } else tex = TexList[i].texture; CurMtl->texture = tex; pfGStateAttr(CurMtl->gstate, PFSTATE_TEXTURE, tex); /* * Inherit texture enable so texturing can be machine-dependent, * e.g. - enable texturing on RealityEngine, not Indy. */ pfGStateInherit(CurMtl->gstate, PFSTATE_ENTEXTURE); if (tex) { pfGetTexImage(CurMtl->texture, &image, &comp, &foo, &foo, &foo); if (comp == 2 || comp == 4) { pfGStateMode(CurMtl->gstate, PFSTATE_ALPHAFUNC, PFAF_GREATER); pfGStateMode(CurMtl->gstate, PFSTATE_ALPHAREF, 4); pfGStateMode(CurMtl->gstate, PFSTATE_TRANSPARENCY, PFTR_ON); } } } else if (SAME(token, "refl")) { if (CurMtl) CurMtl->refl_mapped = 1; } else if (SAME(token, "map_Ka") || SAME(token, "map_Ks")|| SAME(token, "map_d") || SAME(token, "sharpness") || SAME(token, "illum") || SAME(token, "d") || SAME(token, "vp")) numSkip++; else { printf(" unrecognized: %s", buffer); numOther++; } } /* close Wavefront ".mtl" file */ fclose(mtlFile); } /* * locate and open named file in IRIS Performer search path */ static FILE * openFile (char *fileName) { FILE *file = NULL; char filePath[BUFFER_SIZE]; /* check argument */ if (fileName == NULL || *fileName == '\0') return NULL; /* find file in IRIS Performer directory-search path */ if (!pfFindFile(fileName, filePath, R_OK)) { pfNotify(PFNFY_WARN, PFNFY_RESOURCE, "openFile: Could not find file \"%s\"", fileName); return NULL; } /* open file */ if ((file = fopen(filePath, "r")) == NULL) { pfNotify(PFNFY_WARN, PFNFY_RESOURCE, "openFile: Could not open file \"%s\"", filePath); return NULL; } return file; } pfNode* pfuSpatialize(pfList *gsets, float geodeSize, long geodeChild) { long i, j; long active; pfList *lists[8]; long ngset; pfBox bigbox; pfVec3 center; float size2; pfPlane planes[3]; pfGroup *grp; pfBox gsbbox; ngset = pfGetNum(gsets); pfMakeEmptyBox(&bigbox); /* * compute center */ for (i = 0 ; i < ngset ; i++) { pfGeoSet *gset; gset = (pfGeoSet *)pfGet(gsets, i); pfGetGSetBBox(gset, &gsbbox); pfBoxExtendBox(&bigbox, &gsbbox); } pfCombineVec3(center, 0.5f, bigbox.min, 0.5f, bigbox.max); size2 = PFSQR_DISTANCE_PT3(bigbox.min, bigbox.max); /* * if fewer than 4 children or smaller than specified * geode dimension, return a single geode */ if (ngset <= geodeChild || size2 < geodeSize*geodeSize) { pfGeode *geode = pfNewGeode(); for (i = 0 ; i < ngset ; i++) { pfGeoSet *gset; gset = (pfGeoSet *)pfGet(gsets, i); pfAddGSet(geode, gset); } return (pfNode*)geode; } for (i = 0 ; i < 8 ; i++) lists[i] = pfNewList(sizeof(pfGeoSet*), 10, pfGetSharedArena()); { pfVec3 norms[3] = { {1.0f, 0.0f, 0.0f}, {0.0f, 1.0f, 0.0f}, {0.0f, 0.0f, 1.0f}}; for (j = 0 ; j < 3 ; j++) pfMakeNormPtPlane(&planes[j], norms[j], center); } /* * place geosets on one of eight lists based on center */ for (i = 0 ; i < ngset ; i++) { pfBox bbox; pfVec3 gscenter; pfGeoSet *gset; long which = 0; gset = (pfGeoSet *)pfGet(gsets, i); pfGetGSetBBox(gset, &bbox); pfCombineVec3(gscenter, 0.5f, bbox.min, 0.5f, bbox.max); for (j = 0 ; j < 3 ; j++) { if (pfPtInHalfSpace(gscenter, &planes[j])) which |= (1< 0) active++; } /* * if only one octant active, arbitrarily subdivide */ grp = pfNewGroup(); if (active < 2) { long nper = PF_MAX2(ngset/4, 3); long which = 0; for (i = 0 ; i < 8 ; i++) pfResetList(lists[i]); for (i = 0 ; i < ngset ; i++) { pfGeoSet *gset = (pfGeoSet *)pfGet(gsets, i); if (i > (which+1)*nper) which++; pfAdd(lists[which], gset); } } /* * add recursion result to current group & cleanup */ for (i = 0 ; i < 8 ; i++) { if (pfGetNum(lists[i]) > 0) { pfNode *child = pfuSpatialize(lists[i], geodeSize, geodeChild); pfAddChild(grp, child); } pfDelete(lists[i]); } return (pfNode *)grp; } /************************************************************************ * Traversal and callback for computing a bounding box around pfGeoSets ***********************************************************************/ typedef struct { long depth; pfList *gsets; } pfuGSetter; static long cbPreGSet(pfuTraverser *trav) { long nType = pfGetType(trav->node); pfuGSetter *gsetter = trav->data; long ngsets, i; switch (nType) { case PFTYPE_GEODE: if (gsetter->depth == 0) { ngsets = pfGetNumGSets(trav->node); for (i = 0 ; i < ngsets ; i++) { pfGeoSet *gset = pfGetGSet(trav->node, i); pfAdd(gsetter->gsets, gset); } for (i = ngsets-1 ; i >= 0 ; i--) { pfGeoSet *gset = pfGetGSet(trav->node, i); pfRemoveGSet(trav->node, gset); } } return PFTRAV_CONT; case PFTYPE_SCS: case PFTYPE_DCS: gsetter->depth++; return PFTRAV_CONT; case PFTYPE_GROUP: return PFTRAV_CONT; default: return PFTRAV_PRUNE; } } static long cbPostGSet(pfuTraverser *trav) { long nType = pfGetType(trav->node); long nChild; pfuGSetter *gsetter = trav->data; long i; if (nType == PFTYPE_SCS || nType == PFTYPE_DCS) { gsetter->depth--; return PFTRAV_CONT; } else if (nType & PFCLASS_GROUP) { nChild = pfGetNumChildren(trav->node); for (i = nChild -1 ; i >= 0 ; i--) { pfNode *child = pfGetChild(trav->node, i); long childType = pfGetType(child); long numGrandKids = -1; switch (childType) { case PFTYPE_GEODE: numGrandKids = 0; /* pfGetNumGSets((pfGeode *)child); */ break; case PFTYPE_GROUP: numGrandKids = pfGetNumChildren(child); break; } if (numGrandKids == 0) { pfRemoveChild((pfGroup*)trav->node, child); pfDelete(child); } } } return PFTRAV_CONT; } pfList * pfuTravGetGSets(pfNode *node) { pfuTraverser trav; pfuGSetter gsetter; gsetter.gsets = pfNewList(sizeof(pfGeoSet*), 100, pfGetSharedArena()); gsetter.depth = 0; pfuInitTraverser(&trav); trav.data = &gsetter; trav.mode = PFUTRAV_LOD_NONE|PFUTRAV_SW_NONE|PFUTRAV_SEQ_NONE; trav.preFunc = cbPreGSet; trav.postFunc = cbPostGSet; trav.mstack = pfNewMStack(32, pfGetSharedArena()); pfuTraverse(node, &trav); pfDelete(trav.mstack); return gsetter.gsets; } pfGroup * pfuRespatialize(pfGroup *grp, long branch) { pfList *gsets; pfNode *newTree; pfGroup *newGrp; gsets = pfuTravGetGSets((pfNode *)grp); printf("%d geosets found\n", pfGetNum(gsets)); newTree = pfuSpatialize(gsets, 0.0f, branch); newGrp = pfNewGroup(); pfAddChild(newGrp, newTree); pfDelete(gsets); return newGrp; }