src/common/mesh.c

#ifndef lint
static const char RCSid[] = "$Id$";
#endif
/*
 * Mesh support routines
 */

#include "standard.h"
#include "octree.h"
#include "object.h"
#include "otypes.h"
#include "mesh.h"

/* An encoded mesh vertex */
typedef struct {
        int             fl;
        uint4           xyz[3];
        int4            norm;
        uint4           uv[2];
} MCVERT;

#define  MPATCHBLKSIZ   128             /* patch allocation block size */

#define  IO_LEGAL       (IO_BOUNDS|IO_TREE|IO_SCENE)

static MESH     *mlist = NULL;          /* list of loaded meshes */


static unsigned long
cvhash(cvp)                             /* hash an encoded vertex */
MCVERT  *cvp;
{
        unsigned long   hval;
        
        if (!(cvp->fl & MT_V))
                return(0);
        hval = cvp->xyz[0] ^ cvp->xyz[1] << 11 ^ cvp->xyz[2] << 22;
        if (cvp->fl & MT_N)
                hval ^= cvp->norm;
        if (cvp->fl & MT_UV)
                hval ^= cvp->uv[0] ^ cvp->uv[1] << 16;
        return(hval);
}


static int
cvcmp(v1, v2)                           /* compare encoded vertices */
register MCVERT *v1, *v2;
{
        if (v1->fl != v2->fl)
                return(1);
        if (v1->xyz[0] != v2->xyz[0])
                return(1);
        if (v1->xyz[1] != v2->xyz[1])
                return(1);
        if (v1->xyz[2] != v2->xyz[2])
                return(1);
        if (v1->fl & MT_N && v1->norm != v2->norm)
                return(1);
        if (v1->fl & MT_UV) {
                if (v1->uv[0] != v2->uv[0])
                        return(1);
                if (v1->uv[1] != v2->uv[1])
                        return(1);
        }
        return(0);
}


MESH *
getmesh(mname, flags)                   /* get mesh data */
char    *mname;
int     flags;
{
        char  *pathname;
        register MESH  *ms;

        flags &= IO_LEGAL;
        for (ms = mlist; ms != NULL; ms = ms->next)
                if (!strcmp(mname, ms->name)) {
                        if ((ms->ldflags & flags) == flags) {
                                ms->nref++;
                                return(ms);             /* loaded */
                        }
                        break;                  /* load the rest */
                }
        if (ms == NULL) {
                ms = (MESH *)calloc(1, sizeof(MESH));
                if (ms == NULL)
                        error(SYSTEM, "out of memory in getmesh");
                ms->name = savestr(mname);
                ms->nref = 1;
                ms->mcube.cutree = EMPTY;
                ms->next = mlist;
                mlist = ms;
        }
        if ((pathname = getpath(mname, getlibpath(), R_OK)) == NULL) {
                sprintf(errmsg, "cannot find mesh file \"%s\"", mname);
                error(USER, errmsg);
        }
        flags &= ~ms->ldflags;
        if (flags)
                readmesh(ms, pathname, flags);
        return(ms);
}


MESHINST *
getmeshinst(o, flags)                   /* create mesh instance */
OBJREC  *o;
int     flags;
{
        register MESHINST  *ins;

        flags &= IO_LEGAL;
        if ((ins = (MESHINST *)o->os) == NULL) {
                if ((ins = (MESHINST *)malloc(sizeof(MESHINST))) == NULL)
                        error(SYSTEM, "out of memory in getmeshinst");
                if (o->oargs.nsargs < 1)
                        objerror(o, USER, "bad # of arguments");
                if (fullxf(&ins->x, o->oargs.nsargs-1,
                                o->oargs.sarg+1) != o->oargs.nsargs-1)
                        objerror(o, USER, "bad transform");
                if (ins->x.f.sca < 0.0) {
                        ins->x.f.sca = -ins->x.f.sca;
                        ins->x.b.sca = -ins->x.b.sca;
                }
                ins->msh = NULL;
                o->os = (char *)ins;
        }
        if (ins->msh == NULL || (ins->msh->ldflags & flags) != flags)
                ins->msh = getmesh(o->oargs.sarg[0], flags);
        return(ins);
}


int
getmeshtrivid(tvid, mo, mp, ti)         /* get triangle vertex ID's */
int4    tvid[3];
OBJECT  *mo;
MESH    *mp;
OBJECT  ti;
{
        int             pn = ti >> 10;
        MESHPATCH       *pp;

        if (pn >= mp->npatches)
                return(0);
        pp = &mp->patch[pn];
        ti &= 0x3ff;
        if (!(ti & 0x200)) {            /* local triangle */
                struct PTri     *tp;
                if (ti >= pp->ntris)
                        return(0);
                tp = &pp->tri[ti];
                tvid[0] = tvid[1] = tvid[2] = pn << 8;
                tvid[0] |= tp->v1;
                tvid[1] |= tp->v2;
                tvid[2] |= tp->v3;
                if (pp->trimat != NULL)
                        *mo = pp->trimat[ti];
                else
                        *mo = pp->solemat;
                if (*mo != OVOID)
                        *mo += mp->mat0;
                return(1);
        }
        ti &= ~0x200;
        if (!(ti & 0x100)) {            /* single link vertex */
                struct PJoin1   *tp1;
                if (ti >= pp->nj1tris)
                        return(0);
                tp1 = &pp->j1tri[ti];
                tvid[0] = tp1->v1j;
                tvid[1] = tvid[2] = pn << 8;
                tvid[1] |= tp1->v2;
                tvid[2] |= tp1->v3;
                if ((*mo = tp1->mat) != OVOID)
                        *mo += mp->mat0;
                return(1);
        }
        ti &= ~0x100;
        {                               /* double link vertex */
                struct PJoin2   *tp2;
                if (ti >= pp->nj2tris)
                        return(0);
                tp2 = &pp->j2tri[ti];
                tvid[0] = tp2->v1j;
                tvid[1] = tp2->v2j;
                tvid[2] = pn << 8 | tp2->v3;
                if ((*mo = tp2->mat) != OVOID)
                        *mo += mp->mat0;
        }
        return(1);
}


int
getmeshvert(vp, mp, vid, what)  /* get triangle vertex from ID */
MESHVERT        *vp;
MESH            *mp;
int4            vid;
int             what;
{
        int             pn = vid >> 8;
        MESHPATCH       *pp;
        double          vres;
        register int    i;
        
        vp->fl = 0;
        if (pn >= mp->npatches)
                return(0);
        pp = &mp->patch[pn];
        vid &= 0xff;
        if (vid >= pp->nverts)
                return(0);
                                        /* get location */
        if (what & MT_V) {
                vres = (1./4294967296.)*mp->mcube.cusize;
                for (i = 0; i < 3; i++)
                        vp->v[i] = mp->mcube.cuorg[i] +
                                        (pp->xyz[vid][i] + .5)*vres;
                vp->fl |= MT_V;
        }
                                        /* get normal */
        if (what & MT_N && pp->norm != NULL && pp->norm[vid]) {
                decodedir(vp->n, pp->norm[vid]);
                vp->fl |= MT_N;
        }
                                        /* get (u,v) */
        if (what & MT_UV && pp->uv != NULL && pp->uv[vid][0]) {
                for (i = 0; i < 2; i++)
                        vp->uv[i] = mp->uvlim[0][i] +
                                (mp->uvlim[1][i] - mp->uvlim[0][i])*
                                (pp->uv[vid][i] + .5)*(1./4294967296.);
                vp->fl |= MT_UV;
        }
        return(vp->fl);
}


OBJREC *
getmeshpseudo(mp, mo)           /* get mesh pseudo object for material */
MESH    *mp;
OBJECT  mo;
{
        if (mo < mp->mat0 || mo >= mp->mat0 + mp->nmats)
                error(INTERNAL, "modifier out of range in getmeshpseudo");
        if (mp->pseudo == NULL) {
                register int    i;
                mp->pseudo = (OBJREC *)calloc(mp->nmats, sizeof(OBJREC));
                if (mp->pseudo == NULL)
                        error(SYSTEM, "out of memory in getmeshpseudo");
                for (i = mp->nmats; i--; ) {
                        mp->pseudo[i].omod = mp->mat0 + i;
                        mp->pseudo[i].otype = OBJ_FACE;
                        mp->pseudo[i].oname = "M-Tri";
                }
        }
        return(&mp->pseudo[mo - mp->mat0]);
}


int
getmeshtri(tv, mo, mp, ti, wha) /* get triangle vertices */
MESHVERT        tv[3];
OBJECT          *mo;
MESH            *mp;
OBJECT          ti;
int             wha;
{
        int4    tvid[3];

        if (!getmeshtrivid(tvid, mo, mp, ti))
                return(0);

        getmeshvert(&tv[0], mp, tvid[0], wha);
        getmeshvert(&tv[1], mp, tvid[1], wha);
        getmeshvert(&tv[2], mp, tvid[2], wha);

        return(tv[0].fl & tv[1].fl & tv[2].fl);
}


int4
addmeshvert(mp, vp)             /* find/add a mesh vertex */
register MESH   *mp;
MESHVERT        *vp;
{
        LUENT           *lvp;
        MCVERT          cv;
        register int    i;

        if (!(vp->fl & MT_V))
                return(-1);
                                        /* encode vertex */
        for (i = 0; i < 3; i++) {
                if (vp->v[i] < mp->mcube.cuorg[i])
                        return(-1);
                if (vp->v[i] >= mp->mcube.cuorg[i] + mp->mcube.cusize)
                        return(-1);
                cv.xyz[i] = (uint4)(4294967296. *
                                (vp->v[i] - mp->mcube.cuorg[i]) /
                                mp->mcube.cusize);
        }
        if (vp->fl & MT_N)
                cv.norm = encodedir(vp->n);
        if (vp->fl & MT_UV)
                for (i = 0; i < 2; i++) {
                        if (vp->uv[i] <= mp->uvlim[0][i])
                                return(-1);
                        if (vp->uv[i] >= mp->uvlim[1][i])
                                return(-1);
                        cv.uv[i] = (uint4)(4294967296. *
                                        (vp->uv[i] - mp->uvlim[0][i]) /
                                        (mp->uvlim[1][i] - mp->uvlim[0][i]));
                }
        cv.fl = vp->fl;
        if (mp->lut.tsiz == 0) {
                mp->lut.hashf = cvhash;
                mp->lut.keycmp = cvcmp;
                mp->lut.freek = free;
                if (!lu_init(&mp->lut, 50000))
                        goto nomem;
        }
                                        /* find entry */
        lvp = lu_find(&mp->lut, (char *)&cv);
        if (lvp == NULL)
                goto nomem;
        if (lvp->key == NULL) {
                lvp->key = (char *)malloc(sizeof(MCVERT)+sizeof(int4));
                bcopy((void *)&cv, (void *)lvp->key, sizeof(MCVERT));
        }
        if (lvp->data == NULL) {        /* new vertex */
                register MESHPATCH      *pp;
                if (mp->npatches <= 0) {
                        mp->patch = (MESHPATCH *)calloc(MPATCHBLKSIZ,
                                        sizeof(MESHPATCH));
                        if (mp->patch == NULL)
                                goto nomem;
                        mp->npatches = 1;
                } else if (mp->patch[mp->npatches-1].nverts >= 256) {
                        if (mp->npatches % MPATCHBLKSIZ == 0) {
                                mp->patch = (MESHPATCH *)realloc(
                                                (void *)mp->patch,
                                        (mp->npatches + MPATCHBLKSIZ)*
                                                sizeof(MESHPATCH));
                                bzero((void *)(mp->patch + mp->npatches),
                                        MPATCHBLKSIZ*sizeof(MESHPATCH));
                        }
                        if (mp->npatches++ >= 1L<<22)
                                error(INTERNAL, "too many mesh patches");
                }
                pp = &mp->patch[mp->npatches-1];
                if (pp->xyz == NULL) {
                        pp->xyz = (uint4 (*)[3])calloc(256, 3*sizeof(int4));
                        if (pp->xyz == NULL)
                                goto nomem;
                }
                for (i = 0; i < 3; i++)
                        pp->xyz[pp->nverts][i] = cv.xyz[i];
                if (cv.fl & MT_N) {
                        if (pp->norm == NULL) {
                                pp->norm = (int4 *)calloc(256, sizeof(int4));
                                if (pp->norm == NULL)
                                        goto nomem;
                        }
                        pp->norm[pp->nverts] = cv.norm;
                }
                if (cv.fl & MT_UV) {
                        if (pp->uv == NULL) {
                                pp->uv = (uint4 (*)[2])calloc(256,
                                                2*sizeof(uint4));
                                if (pp->uv == NULL)
                                        goto nomem;
                        }
                        for (i = 0; i < 2; i++)
                                pp->uv[pp->nverts][i] = cv.uv[i];
                }
                pp->nverts++;
                lvp->data = lvp->key + sizeof(MCVERT);
                *(int4 *)lvp->data = (mp->npatches-1) << 8 | (pp->nverts-1);
        }
        return(*(int4 *)lvp->data);
nomem:
        error(SYSTEM, "out of memory in addmeshvert");
        return(-1);
}


OBJECT
addmeshtri(mp, tv, mo)          /* add a new mesh triangle */
MESH            *mp;
MESHVERT        tv[3];
OBJECT          mo;
{
        int4                    vid[3], t;
        int                     pn[3], i;
        register MESHPATCH      *pp;

        if (!(tv[0].fl & tv[1].fl & tv[2].fl & MT_V))
                return(OVOID);
                                /* find/allocate patch vertices */
        for (i = 0; i < 3; i++) {
                if ((vid[i] = addmeshvert(mp, &tv[i])) < 0)
                        return(OVOID);
                pn[i] = vid[i] >> 8;
        }
                                /* normalize material index */
        if (mo != OVOID)
                if ((mo -= mp->mat0) >= mp->nmats)
                        mp->nmats = mo+1;
                else if (mo < 0)
                        error(INTERNAL, "modifier range error in addmeshtri");
                                /* assign triangle */
        if (pn[0] == pn[1] && pn[1] == pn[2]) { /* local case */
                pp = &mp->patch[pn[0]];
                if (pp->tri == NULL) {
                        pp->tri = (struct PTri *)malloc(
                                        512*sizeof(struct PTri));
                        if (pp->tri == NULL)
                                goto nomem;
                }
                if (pp->ntris < 512) {
                        pp->tri[pp->ntris].v1 = vid[0] & 0xff;
                        pp->tri[pp->ntris].v2 = vid[1] & 0xff;
                        pp->tri[pp->ntris].v3 = vid[2] & 0xff;
                        if (pp->ntris == 0)
                                pp->solemat = mo;
                        else if (pp->trimat == NULL && mo != pp->solemat) {
                                pp->trimat = (int2 *)malloc(
                                                512*sizeof(int2));
                                if (pp->trimat == NULL)
                                        goto nomem;
                                for (i = pp->ntris; i--; )
                                        pp->trimat[i] = pp->solemat;
                        }
                        if (pp->trimat != NULL)
                                pp->trimat[pp->ntris] = mo;
                        return(pn[0] << 10 | pp->ntris++);
                }
        }
        if (pn[0] == pn[1]) {
                t = vid[2]; vid[2] = vid[1]; vid[1] = vid[0]; vid[0] = t;
                i = pn[2]; pn[2] = pn[1]; pn[1] = pn[0]; pn[0] = i;
        } else if (pn[0] == pn[2]) {
                t = vid[0]; vid[0] = vid[1]; vid[1] = vid[2]; vid[2] = t;
                i = pn[0]; pn[0] = pn[1]; pn[1] = pn[2]; pn[2] = i;
        }
        if (pn[1] == pn[2]) {                   /* single link */
                pp = &mp->patch[pn[1]];
                if (pp->j1tri == NULL) {
                        pp->j1tri = (struct PJoin1 *)malloc(
                                        256*sizeof(struct PJoin1));
                        if (pp->j1tri == NULL)
                                goto nomem;
                }
                if (pp->nj1tris < 256) {
                        pp->j1tri[pp->nj1tris].v1j = vid[0];
                        pp->j1tri[pp->nj1tris].v2 = vid[1] & 0xff;
                        pp->j1tri[pp->nj1tris].v3 = vid[2] & 0xff;
                        pp->j1tri[pp->nj1tris].mat = mo;
                        return(pn[1] << 10 | 0x200 | pp->nj1tris++);
                }
        }
                                                /* double link */
        pp = &mp->patch[pn[2]];
        if (pp->j2tri == NULL) {
                pp->j2tri = (struct PJoin2 *)malloc(
                                        256*sizeof(struct PJoin2));
                if (pp->j2tri == NULL)
                        goto nomem;
        }
        if (pp->nj2tris >= 256)
                error(INTERNAL, "too many patch triangles in addmeshtri");
        pp->j2tri[pp->nj2tris].v1j = vid[0];
        pp->j2tri[pp->nj2tris].v2j = vid[1];
        pp->j2tri[pp->nj2tris].v3 = vid[2] & 0xff;
        pp->j2tri[pp->nj2tris].mat = mo;
        return(pn[2] << 10 | 0x300 | pp->nj2tris++);
nomem:
        error(SYSTEM, "out of memory in addmeshtri");
        return(OVOID);
}


char *
checkmesh(mp)                           /* validate mesh data */
register MESH   *mp;
{
        static char     embuf[128];
        int             nouvbounds = 1;
        register int    i;
                                        /* basic checks */
        if (mp == NULL)
                return("NULL mesh pointer");
        if (!mp->ldflags)
                return("unassigned mesh");
        if (mp->name == NULL)
                return("missing mesh name");
        if (mp->nref <= 0)
                return("unreferenced mesh");
                                        /* check boundaries */
        if (mp->ldflags & IO_BOUNDS) {
                if (mp->mcube.cusize <= FTINY)
                        return("illegal octree bounds in mesh");
                nouvbounds = (mp->uvlim[1][0] - mp->uvlim[0][0] <= FTINY ||
                                mp->uvlim[1][1] - mp->uvlim[0][1] <= FTINY);
        }
                                        /* check octree */
        if (mp->ldflags & IO_TREE) {
                if (isempty(mp->mcube.cutree))
                        error(WARNING, "empty mesh octree");
        }
                                        /* check scene data */
        if (mp->ldflags & IO_SCENE) {
                if (!(mp->ldflags & IO_BOUNDS))
                        return("unbounded scene in mesh");
                if (mp->mat0 < 0 || mp->mat0+mp->nmats > nobjects)
                        return("bad mesh modifier range");
                for (i = mp->mat0+mp->nmats; i-- > mp->mat0; ) {
                        int     otyp = objptr(i)->otype;
                        if (!ismodifier(otyp)) {
                                sprintf(embuf,
                                        "non-modifier in mesh (%s \"%s\")",
                                        ofun[otyp].funame, objptr(i)->oname);
                                return(embuf);
                        }
                }
                if (mp->npatches <= 0)
                        error(WARNING, "no patches in mesh");
                for (i = 0; i < mp->npatches; i++) {
                        register MESHPATCH      *pp = &mp->patch[i];
                        if (pp->nverts <= 0)
                                error(WARNING, "no vertices in patch");
                        else {
                                if (pp->xyz == NULL)
                                        return("missing patch vertex list");
                                if (nouvbounds && pp->uv != NULL)
                                        return("unreferenced uv coordinates");
                        }
                        if (pp->ntris + pp->nj1tris + pp->nj2tris <= 0)
                                error(WARNING, "no triangles in patch");
                        if (pp->ntris > 0 && pp->tri == NULL)
                                return("missing patch triangle list");
                        if (pp->nj1tris > 0 && pp->j1tri == NULL)
                                return("missing patch joiner triangle list");
                        if (pp->nj2tris > 0 && pp->j2tri == NULL)
                                return("missing patch double-joiner list");
                }
        }
        return(NULL);                   /* seems OK */
}


static void
tallyoctree(ot, ecp, lcp, ocp)  /* tally octree size */
OCTREE  ot;
int     *ecp, *lcp, *ocp;
{
        int     i;

        if (isempty(ot)) {
                (*ecp)++;
                return;
        }
        if (isfull(ot)) {
                OBJECT  oset[MAXSET+1];
                (*lcp)++;
                objset(oset, ot);
                *ocp += oset[0];
                return;
        }
        for (i = 0; i < 8; i++)
                tallyoctree(octkid(ot, i), ecp, lcp, ocp);
}


void
printmeshstats(ms, fp)          /* print out mesh statistics */
MESH    *ms;
FILE    *fp;
{
        int     lfcnt=0, lecnt=0, locnt=0;
        int     vcnt=0, ncnt=0, uvcnt=0;
        int     nscnt=0, uvscnt=0;
        int     tcnt=0, t1cnt=0, t2cnt=0;
        int     i, j;
        
        tallyoctree(ms->mcube.cutree, &lecnt, &lfcnt, &locnt);
        for (i = 0; i < ms->npatches; i++) {
                register MESHPATCH      *pp = &ms->patch[i];
                vcnt += pp->nverts;
                if (pp->norm != NULL) {
                        for (j = pp->nverts; j--; )
                                if (pp->norm[j])
                                        ncnt++;
                        nscnt += pp->nverts;
                }
                if (pp->uv != NULL) {
                        for (j = pp->nverts; j--; )
                                if (pp->uv[j][0])
                                        uvcnt++;
                        uvscnt += pp->nverts;
                }
                tcnt += pp->ntris;
                t1cnt += pp->nj1tris;
                t2cnt += pp->nj2tris;
        }
        fprintf(fp, "Mesh statistics:\n");
        fprintf(fp, "\t%d materials\n", ms->nmats);
        fprintf(fp, "\t%d patches (%.2f MBytes)\n", ms->npatches,
                        (ms->npatches*sizeof(MESHPATCH) +
                        vcnt*3*sizeof(uint4) +
                        nscnt*sizeof(int4) +
                        uvscnt*2*sizeof(uint4) +
                        tcnt*sizeof(struct PTri) +
                        t1cnt*sizeof(struct PJoin1) +
                        t2cnt*sizeof(struct PJoin2))/(1024.*1024.));
        fprintf(fp, "\t%d vertices (%.1f%% w/ normals, %.1f%% w/ uv)\n",
                        vcnt, 100.*ncnt/vcnt, 100.*uvcnt/vcnt);
        fprintf(fp, "\t%d triangles (%.1f%% local, %.1f%% joiner)\n",
                        tcnt+t1cnt+t2cnt,
                        100.*tcnt/(tcnt+t1cnt+t2cnt),
                        100.*t1cnt/(tcnt+t1cnt+t2cnt));
        fprintf(fp,
        "\t%d leaves in octree (%.1f%% empty, %.2f avg. set size)\n",
                        lfcnt+lecnt, 100.*lecnt/(lfcnt+lecnt),
                        (double)locnt/lfcnt);
}


void
freemesh(ms)                    /* free mesh data */
register MESH   *ms;
{
        MESH    mhead;
        MESH    *msp;
        
        if (ms == NULL)
                return;
        if (ms->nref <= 0)
                error(CONSISTENCY, "unreferenced mesh in freemesh");
        ms->nref--;
        if (ms->nref)           /* still in use */
                return;
                                /* else remove from list */
        mhead.next = mlist;
        for (msp = &mhead; msp->next != NULL; msp = msp->next)
                if (msp->next == ms) {
                        msp->next = ms->next;
                        ms->next = NULL;
                        break;
                }
        if (ms->next != NULL)   /* can't be in list anymore */
                error(CONSISTENCY, "unlisted mesh in freemesh");
        mlist = mhead.next;
                                /* free mesh data */
        freestr(ms->name);
        octfree(ms->mcube.cutree);
        lu_done(&ms->lut);
        if (ms->npatches > 0) {
                register MESHPATCH      *pp = ms->patch + ms->npatches;
                while (pp-- > ms->patch) {
                        if (pp->j2tri != NULL)
                                free((void *)pp->j2tri);
                        if (pp->j1tri != NULL)
                                free((void *)pp->j1tri);
                        if (pp->tri != NULL)
                                free((void *)pp->tri);
                        if (pp->uv != NULL)
                                free((void *)pp->uv);
                        if (pp->norm != NULL)
                                free((void *)pp->norm);
                        if (pp->xyz != NULL)
                                free((void *)pp->xyz);
                }
                free((void *)ms->patch);
        }
        if (ms->pseudo != NULL)
                free((void *)ms->pseudo);
        free((void *)ms);
}


void
freemeshinst(o)                 /* free mesh instance */
OBJREC  *o;
{
        if (o->os == NULL)
                return;
        freemesh((*(MESHINST *)o->os).msh);
        free((void *)o->os);
        o->os = NULL;
}
Revision:	2.6
Committed:	Wed Apr 23 00:52:33 2003 UTC (21 years ago) by greg
Content type:	text/plain
Branch:	MAIN
Changes since 2.5:	+4 -4 lines
Log Message:	Added (void *) cast to realloc calls
#	User	Rev	Content
1	greg	2.1	#ifndef lint
2			static const char RCSid[] = "$Id$";
3			#endif
4			/*
5			* Mesh support routines
6			*/
7
8			#include "standard.h"
9			#include "octree.h"
10			#include "object.h"
11	greg	2.4	#include "otypes.h"
12	greg	2.1	#include "mesh.h"
13
14			/* An encoded mesh vertex */
15			typedef struct {
16			int fl;
17			uint4 xyz[3];
18			int4 norm;
19	greg	2.2	uint4 uv[2];
20	greg	2.1	} MCVERT;
21
22			#define MPATCHBLKSIZ 128 /* patch allocation block size */
23
24			#define IO_LEGAL (IO_BOUNDS\|IO_TREE\|IO_SCENE)
25
26			static MESH mlist = NULL; / list of loaded meshes */
27
28
29			static unsigned long
30			cvhash(cvp) /* hash an encoded vertex */
31			MCVERT *cvp;
32			{
33			unsigned long hval;
34
35			if (!(cvp->fl & MT_V))
36			return(0);
37			hval = cvp->xyz[0] ^ cvp->xyz[1] << 11 ^ cvp->xyz[2] << 22;
38			if (cvp->fl & MT_N)
39			hval ^= cvp->norm;
40			if (cvp->fl & MT_UV)
41			hval ^= cvp->uv[0] ^ cvp->uv[1] << 16;
42			return(hval);
43			}
44
45
46			static int
47			cvcmp(v1, v2) /* compare encoded vertices */
48			register MCVERT v1, v2;
49			{
50			if (v1->fl != v2->fl)
51			return(1);
52			if (v1->xyz[0] != v2->xyz[0])
53			return(1);
54			if (v1->xyz[1] != v2->xyz[1])
55			return(1);
56			if (v1->xyz[2] != v2->xyz[2])
57			return(1);
58			if (v1->fl & MT_N && v1->norm != v2->norm)
59			return(1);
60			if (v1->fl & MT_UV) {
61			if (v1->uv[0] != v2->uv[0])
62			return(1);
63			if (v1->uv[1] != v2->uv[1])
64			return(1);
65			}
66			return(0);
67			}
68
69
70			MESH *
71			getmesh(mname, flags) /* get mesh data */
72			char *mname;
73			int flags;
74			{
75			char *pathname;
76			register MESH *ms;
77
78			flags &= IO_LEGAL;
79			for (ms = mlist; ms != NULL; ms = ms->next)
80			if (!strcmp(mname, ms->name)) {
81			if ((ms->ldflags & flags) == flags) {
82			ms->nref++;
83			return(ms); /* loaded */
84			}
85			break; /* load the rest */
86			}
87			if (ms == NULL) {
88			ms = (MESH *)calloc(1, sizeof(MESH));
89			if (ms == NULL)
90			error(SYSTEM, "out of memory in getmesh");
91			ms->name = savestr(mname);
92			ms->nref = 1;
93			ms->mcube.cutree = EMPTY;
94			ms->next = mlist;
95			mlist = ms;
96			}
97			if ((pathname = getpath(mname, getlibpath(), R_OK)) == NULL) {
98			sprintf(errmsg, "cannot find mesh file \"%s\"", mname);
99			error(USER, errmsg);
100			}
101			flags &= ~ms->ldflags;
102			if (flags)
103			readmesh(ms, pathname, flags);
104			return(ms);
105			}
106
107
108			MESHINST *
109			getmeshinst(o, flags) /* create mesh instance */
110			OBJREC *o;
111			int flags;
112			{
113			register MESHINST *ins;
114
115			flags &= IO_LEGAL;
116			if ((ins = (MESHINST *)o->os) == NULL) {
117			if ((ins = (MESHINST *)malloc(sizeof(MESHINST))) == NULL)
118			error(SYSTEM, "out of memory in getmeshinst");
119			if (o->oargs.nsargs < 1)
120			objerror(o, USER, "bad # of arguments");
121			if (fullxf(&ins->x, o->oargs.nsargs-1,
122			o->oargs.sarg+1) != o->oargs.nsargs-1)
123			objerror(o, USER, "bad transform");
124			if (ins->x.f.sca < 0.0) {
125			ins->x.f.sca = -ins->x.f.sca;
126			ins->x.b.sca = -ins->x.b.sca;
127			}
128			ins->msh = NULL;
129			o->os = (char *)ins;
130			}
131			if (ins->msh == NULL \|\| (ins->msh->ldflags & flags) != flags)
132			ins->msh = getmesh(o->oargs.sarg[0], flags);
133			return(ins);
134			}
135
136
137			int
138	greg	2.4	getmeshtrivid(tvid, mo, mp, ti) /* get triangle vertex ID's */
139			int4 tvid[3];
140			OBJECT *mo;
141			MESH *mp;
142			OBJECT ti;
143	greg	2.1	{
144			int pn = ti >> 10;
145	greg	2.4	MESHPATCH *pp;
146	greg	2.1
147			if (pn >= mp->npatches)
148			return(0);
149	greg	2.4	pp = &mp->patch[pn];
150	greg	2.1	ti &= 0x3ff;
151			if (!(ti & 0x200)) { /* local triangle */
152			struct PTri *tp;
153	greg	2.4	if (ti >= pp->ntris)
154	greg	2.1	return(0);
155	greg	2.4	tp = &pp->tri[ti];
156	greg	2.1	tvid[0] = tvid[1] = tvid[2] = pn << 8;
157			tvid[0] \|= tp->v1;
158			tvid[1] \|= tp->v2;
159			tvid[2] \|= tp->v3;
160	greg	2.4	if (pp->trimat != NULL)
161			*mo = pp->trimat[ti];
162			else
163			*mo = pp->solemat;
164			if (*mo != OVOID)
165			*mo += mp->mat0;
166	greg	2.1	return(1);
167			}
168			ti &= ~0x200;
169			if (!(ti & 0x100)) { /* single link vertex */
170			struct PJoin1 *tp1;
171	greg	2.4	if (ti >= pp->nj1tris)
172	greg	2.1	return(0);
173	greg	2.4	tp1 = &pp->j1tri[ti];
174	greg	2.1	tvid[0] = tp1->v1j;
175			tvid[1] = tvid[2] = pn << 8;
176			tvid[1] \|= tp1->v2;
177			tvid[2] \|= tp1->v3;
178	greg	2.4	if ((*mo = tp1->mat) != OVOID)
179			*mo += mp->mat0;
180	greg	2.1	return(1);
181			}
182			ti &= ~0x100;
183			{ /* double link vertex */
184			struct PJoin2 *tp2;
185	greg	2.4	if (ti >= pp->nj2tris)
186	greg	2.1	return(0);
187	greg	2.4	tp2 = &pp->j2tri[ti];
188	greg	2.1	tvid[0] = tp2->v1j;
189			tvid[1] = tp2->v2j;
190			tvid[2] = pn << 8 \| tp2->v3;
191	greg	2.4	if ((*mo = tp2->mat) != OVOID)
192			*mo += mp->mat0;
193	greg	2.1	}
194			return(1);
195			}
196
197
198			int
199			getmeshvert(vp, mp, vid, what) /* get triangle vertex from ID */
200	greg	2.6	MESHVERT *vp;
201			MESH *mp;
202			int4 vid;
203			int what;
204	greg	2.1	{
205			int pn = vid >> 8;
206			MESHPATCH *pp;
207			double vres;
208			register int i;
209
210			vp->fl = 0;
211			if (pn >= mp->npatches)
212			return(0);
213			pp = &mp->patch[pn];
214			vid &= 0xff;
215			if (vid >= pp->nverts)
216			return(0);
217			/* get location */
218			if (what & MT_V) {
219			vres = (1./4294967296.)*mp->mcube.cusize;
220			for (i = 0; i < 3; i++)
221			vp->v[i] = mp->mcube.cuorg[i] +
222			(pp->xyz[vid][i] + .5)*vres;
223			vp->fl \|= MT_V;
224			}
225			/* get normal */
226			if (what & MT_N && pp->norm != NULL && pp->norm[vid]) {
227			decodedir(vp->n, pp->norm[vid]);
228			vp->fl \|= MT_N;
229			}
230			/* get (u,v) */
231			if (what & MT_UV && pp->uv != NULL && pp->uv[vid][0]) {
232			for (i = 0; i < 2; i++)
233	greg	2.2	vp->uv[i] = mp->uvlim[0][i] +
234			(mp->uvlim[1][i] - mp->uvlim[0][i])*
235	greg	2.1	(pp->uv[vid][i] + .5)*(1./4294967296.);
236			vp->fl \|= MT_UV;
237			}
238			return(vp->fl);
239			}
240
241
242	greg	2.4	OBJREC *
243			getmeshpseudo(mp, mo) /* get mesh pseudo object for material */
244			MESH *mp;
245			OBJECT mo;
246			{
247			if (mo < mp->mat0 \|\| mo >= mp->mat0 + mp->nmats)
248			error(INTERNAL, "modifier out of range in getmeshpseudo");
249			if (mp->pseudo == NULL) {
250			register int i;
251			mp->pseudo = (OBJREC *)calloc(mp->nmats, sizeof(OBJREC));
252			if (mp->pseudo == NULL)
253			error(SYSTEM, "out of memory in getmeshpseudo");
254			for (i = mp->nmats; i--; ) {
255			mp->pseudo[i].omod = mp->mat0 + i;
256			mp->pseudo[i].otype = OBJ_FACE;
257			mp->pseudo[i].oname = "M-Tri";
258			}
259			}
260			return(&mp->pseudo[mo - mp->mat0]);
261			}
262
263
264	greg	2.1	int
265	greg	2.4	getmeshtri(tv, mo, mp, ti, wha) /* get triangle vertices */
266	greg	2.1	MESHVERT tv[3];
267	greg	2.4	OBJECT *mo;
268	greg	2.1	MESH *mp;
269			OBJECT ti;
270	greg	2.4	int wha;
271	greg	2.1	{
272			int4 tvid[3];
273
274	greg	2.4	if (!getmeshtrivid(tvid, mo, mp, ti))
275	greg	2.1	return(0);
276
277	greg	2.4	getmeshvert(&tv[0], mp, tvid[0], wha);
278			getmeshvert(&tv[1], mp, tvid[1], wha);
279			getmeshvert(&tv[2], mp, tvid[2], wha);
280	greg	2.1
281			return(tv[0].fl & tv[1].fl & tv[2].fl);
282			}
283
284
285			int4
286			addmeshvert(mp, vp) /* find/add a mesh vertex */
287			register MESH *mp;
288			MESHVERT *vp;
289			{
290			LUENT *lvp;
291			MCVERT cv;
292			register int i;
293
294			if (!(vp->fl & MT_V))
295			return(-1);
296			/* encode vertex */
297			for (i = 0; i < 3; i++) {
298			if (vp->v[i] < mp->mcube.cuorg[i])
299			return(-1);
300			if (vp->v[i] >= mp->mcube.cuorg[i] + mp->mcube.cusize)
301			return(-1);
302			cv.xyz[i] = (uint4)(4294967296. *
303			(vp->v[i] - mp->mcube.cuorg[i]) /
304			mp->mcube.cusize);
305			}
306			if (vp->fl & MT_N)
307			cv.norm = encodedir(vp->n);
308			if (vp->fl & MT_UV)
309			for (i = 0; i < 2; i++) {
310	greg	2.2	if (vp->uv[i] <= mp->uvlim[0][i])
311	greg	2.1	return(-1);
312	greg	2.2	if (vp->uv[i] >= mp->uvlim[1][i])
313	greg	2.1	return(-1);
314			cv.uv[i] = (uint4)(4294967296. *
315	greg	2.2	(vp->uv[i] - mp->uvlim[0][i]) /
316			(mp->uvlim[1][i] - mp->uvlim[0][i]));
317	greg	2.1	}
318			cv.fl = vp->fl;
319	greg	2.4	if (mp->lut.tsiz == 0) {
320			mp->lut.hashf = cvhash;
321			mp->lut.keycmp = cvcmp;
322			mp->lut.freek = free;
323			if (!lu_init(&mp->lut, 50000))
324	greg	2.1	goto nomem;
325			}
326			/* find entry */
327	greg	2.4	lvp = lu_find(&mp->lut, (char *)&cv);
328	greg	2.1	if (lvp == NULL)
329			goto nomem;
330			if (lvp->key == NULL) {
331			lvp->key = (char *)malloc(sizeof(MCVERT)+sizeof(int4));
332			bcopy((void )&cv, (void )lvp->key, sizeof(MCVERT));
333			}
334			if (lvp->data == NULL) { /* new vertex */
335			register MESHPATCH *pp;
336			if (mp->npatches <= 0) {
337			mp->patch = (MESHPATCH *)calloc(MPATCHBLKSIZ,
338			sizeof(MESHPATCH));
339			if (mp->patch == NULL)
340			goto nomem;
341			mp->npatches = 1;
342			} else if (mp->patch[mp->npatches-1].nverts >= 256) {
343			if (mp->npatches % MPATCHBLKSIZ == 0) {
344			mp->patch = (MESHPATCH *)realloc(
345			(void *)mp->patch,
346			(mp->npatches + MPATCHBLKSIZ)*
347			sizeof(MESHPATCH));
348			bzero((void *)(mp->patch + mp->npatches),
349			MPATCHBLKSIZ*sizeof(MESHPATCH));
350			}
351	greg	2.2	if (mp->npatches++ >= 1L<<22)
352	greg	2.1	error(INTERNAL, "too many mesh patches");
353			}
354			pp = &mp->patch[mp->npatches-1];
355			if (pp->xyz == NULL) {
356			pp->xyz = (uint4 ()[3])calloc(256, 3sizeof(int4));
357			if (pp->xyz == NULL)
358			goto nomem;
359			}
360			for (i = 0; i < 3; i++)
361			pp->xyz[pp->nverts][i] = cv.xyz[i];
362			if (cv.fl & MT_N) {
363			if (pp->norm == NULL) {
364			pp->norm = (int4 *)calloc(256, sizeof(int4));
365			if (pp->norm == NULL)
366			goto nomem;
367			}
368			pp->norm[pp->nverts] = cv.norm;
369			}
370			if (cv.fl & MT_UV) {
371			if (pp->uv == NULL) {
372			pp->uv = (uint4 (*)[2])calloc(256,
373			2*sizeof(uint4));
374			if (pp->uv == NULL)
375			goto nomem;
376			}
377			for (i = 0; i < 2; i++)
378			pp->uv[pp->nverts][i] = cv.uv[i];
379			}
380			pp->nverts++;
381			lvp->data = lvp->key + sizeof(MCVERT);
382			(int4 )lvp->data = (mp->npatches-1) << 8 \| (pp->nverts-1);
383			}
384			return((int4 )lvp->data);
385			nomem:
386			error(SYSTEM, "out of memory in addmeshvert");
387			return(-1);
388			}
389
390
391			OBJECT
392	greg	2.4	addmeshtri(mp, tv, mo) /* add a new mesh triangle */
393	greg	2.1	MESH *mp;
394			MESHVERT tv[3];
395	greg	2.4	OBJECT mo;
396	greg	2.1	{
397			int4 vid[3], t;
398			int pn[3], i;
399			register MESHPATCH *pp;
400
401			if (!(tv[0].fl & tv[1].fl & tv[2].fl & MT_V))
402			return(OVOID);
403			/* find/allocate patch vertices */
404			for (i = 0; i < 3; i++) {
405			if ((vid[i] = addmeshvert(mp, &tv[i])) < 0)
406			return(OVOID);
407			pn[i] = vid[i] >> 8;
408			}
409	greg	2.4	/* normalize material index */
410			if (mo != OVOID)
411			if ((mo -= mp->mat0) >= mp->nmats)
412			mp->nmats = mo+1;
413			else if (mo < 0)
414			error(INTERNAL, "modifier range error in addmeshtri");
415	greg	2.1	/* assign triangle */
416			if (pn[0] == pn[1] && pn[1] == pn[2]) { /* local case */
417			pp = &mp->patch[pn[0]];
418			if (pp->tri == NULL) {
419			pp->tri = (struct PTri *)malloc(
420			512*sizeof(struct PTri));
421			if (pp->tri == NULL)
422			goto nomem;
423			}
424	greg	2.2	if (pp->ntris < 512) {
425			pp->tri[pp->ntris].v1 = vid[0] & 0xff;
426			pp->tri[pp->ntris].v2 = vid[1] & 0xff;
427			pp->tri[pp->ntris].v3 = vid[2] & 0xff;
428	greg	2.4	if (pp->ntris == 0)
429			pp->solemat = mo;
430			else if (pp->trimat == NULL && mo != pp->solemat) {
431			pp->trimat = (int2 *)malloc(
432			512*sizeof(int2));
433			if (pp->trimat == NULL)
434			goto nomem;
435			for (i = pp->ntris; i--; )
436			pp->trimat[i] = pp->solemat;
437			}
438			if (pp->trimat != NULL)
439			pp->trimat[pp->ntris] = mo;
440	greg	2.2	return(pn[0] << 10 \| pp->ntris++);
441			}
442	greg	2.1	}
443			if (pn[0] == pn[1]) {
444	greg	2.2	t = vid[2]; vid[2] = vid[1]; vid[1] = vid[0]; vid[0] = t;
445			i = pn[2]; pn[2] = pn[1]; pn[1] = pn[0]; pn[0] = i;
446	greg	2.1	} else if (pn[0] == pn[2]) {
447	greg	2.2	t = vid[0]; vid[0] = vid[1]; vid[1] = vid[2]; vid[2] = t;
448			i = pn[0]; pn[0] = pn[1]; pn[1] = pn[2]; pn[2] = i;
449	greg	2.1	}
450			if (pn[1] == pn[2]) { /* single link */
451			pp = &mp->patch[pn[1]];
452			if (pp->j1tri == NULL) {
453			pp->j1tri = (struct PJoin1 *)malloc(
454			256*sizeof(struct PJoin1));
455			if (pp->j1tri == NULL)
456			goto nomem;
457			}
458	greg	2.2	if (pp->nj1tris < 256) {
459			pp->j1tri[pp->nj1tris].v1j = vid[0];
460			pp->j1tri[pp->nj1tris].v2 = vid[1] & 0xff;
461			pp->j1tri[pp->nj1tris].v3 = vid[2] & 0xff;
462	greg	2.4	pp->j1tri[pp->nj1tris].mat = mo;
463	greg	2.2	return(pn[1] << 10 \| 0x200 \| pp->nj1tris++);
464			}
465	greg	2.1	}
466			/* double link */
467			pp = &mp->patch[pn[2]];
468			if (pp->j2tri == NULL) {
469			pp->j2tri = (struct PJoin2 *)malloc(
470			256*sizeof(struct PJoin2));
471			if (pp->j2tri == NULL)
472			goto nomem;
473			}
474			if (pp->nj2tris >= 256)
475	greg	2.2	error(INTERNAL, "too many patch triangles in addmeshtri");
476			pp->j2tri[pp->nj2tris].v1j = vid[0];
477			pp->j2tri[pp->nj2tris].v2j = vid[1];
478	greg	2.1	pp->j2tri[pp->nj2tris].v3 = vid[2] & 0xff;
479	greg	2.4	pp->j2tri[pp->nj2tris].mat = mo;
480	greg	2.1	return(pn[2] << 10 \| 0x300 \| pp->nj2tris++);
481			nomem:
482			error(SYSTEM, "out of memory in addmeshtri");
483			return(OVOID);
484			}
485
486
487	greg	2.4	char *
488			checkmesh(mp) /* validate mesh data */
489			register MESH *mp;
490			{
491			static char embuf[128];
492			int nouvbounds = 1;
493			register int i;
494			/* basic checks */
495			if (mp == NULL)
496			return("NULL mesh pointer");
497			if (!mp->ldflags)
498			return("unassigned mesh");
499			if (mp->name == NULL)
500			return("missing mesh name");
501			if (mp->nref <= 0)
502			return("unreferenced mesh");
503			/* check boundaries */
504			if (mp->ldflags & IO_BOUNDS) {
505			if (mp->mcube.cusize <= FTINY)
506			return("illegal octree bounds in mesh");
507	greg	2.5	nouvbounds = (mp->uvlim[1][0] - mp->uvlim[0][0] <= FTINY \|\|
508			mp->uvlim[1][1] - mp->uvlim[0][1] <= FTINY);
509	greg	2.4	}
510			/* check octree */
511			if (mp->ldflags & IO_TREE) {
512			if (isempty(mp->mcube.cutree))
513			error(WARNING, "empty mesh octree");
514			}
515			/* check scene data */
516			if (mp->ldflags & IO_SCENE) {
517			if (!(mp->ldflags & IO_BOUNDS))
518			return("unbounded scene in mesh");
519			if (mp->mat0 < 0 \|\| mp->mat0+mp->nmats > nobjects)
520			return("bad mesh modifier range");
521			for (i = mp->mat0+mp->nmats; i-- > mp->mat0; ) {
522			int otyp = objptr(i)->otype;
523			if (!ismodifier(otyp)) {
524			sprintf(embuf,
525			"non-modifier in mesh (%s \"%s\")",
526			ofun[otyp].funame, objptr(i)->oname);
527			return(embuf);
528			}
529			}
530			if (mp->npatches <= 0)
531			error(WARNING, "no patches in mesh");
532			for (i = 0; i < mp->npatches; i++) {
533			register MESHPATCH *pp = &mp->patch[i];
534			if (pp->nverts <= 0)
535			error(WARNING, "no vertices in patch");
536			else {
537			if (pp->xyz == NULL)
538			return("missing patch vertex list");
539			if (nouvbounds && pp->uv != NULL)
540			return("unreferenced uv coordinates");
541			}
542			if (pp->ntris + pp->nj1tris + pp->nj2tris <= 0)
543			error(WARNING, "no triangles in patch");
544			if (pp->ntris > 0 && pp->tri == NULL)
545			return("missing patch triangle list");
546			if (pp->nj1tris > 0 && pp->j1tri == NULL)
547			return("missing patch joiner triangle list");
548			if (pp->nj2tris > 0 && pp->j2tri == NULL)
549			return("missing patch double-joiner list");
550			}
551			}
552			return(NULL); /* seems OK */
553			}
554
555
556	greg	2.1	static void
557			tallyoctree(ot, ecp, lcp, ocp) /* tally octree size */
558			OCTREE ot;
559			int ecp, lcp, *ocp;
560			{
561			int i;
562
563			if (isempty(ot)) {
564			(*ecp)++;
565			return;
566			}
567			if (isfull(ot)) {
568			OBJECT oset[MAXSET+1];
569			(*lcp)++;
570			objset(oset, ot);
571			*ocp += oset[0];
572			return;
573			}
574			for (i = 0; i < 8; i++)
575			tallyoctree(octkid(ot, i), ecp, lcp, ocp);
576			}
577
578
579			void
580			printmeshstats(ms, fp) /* print out mesh statistics */
581			MESH *ms;
582			FILE *fp;
583			{
584			int lfcnt=0, lecnt=0, locnt=0;
585			int vcnt=0, ncnt=0, uvcnt=0;
586			int nscnt=0, uvscnt=0;
587			int tcnt=0, t1cnt=0, t2cnt=0;
588			int i, j;
589
590			tallyoctree(ms->mcube.cutree, &lecnt, &lfcnt, &locnt);
591			for (i = 0; i < ms->npatches; i++) {
592			register MESHPATCH *pp = &ms->patch[i];
593			vcnt += pp->nverts;
594			if (pp->norm != NULL) {
595			for (j = pp->nverts; j--; )
596			if (pp->norm[j])
597			ncnt++;
598			nscnt += pp->nverts;
599			}
600			if (pp->uv != NULL) {
601			for (j = pp->nverts; j--; )
602			if (pp->uv[j][0])
603			uvcnt++;
604			uvscnt += pp->nverts;
605			}
606			tcnt += pp->ntris;
607			t1cnt += pp->nj1tris;
608			t2cnt += pp->nj2tris;
609			}
610			fprintf(fp, "Mesh statistics:\n");
611	greg	2.4	fprintf(fp, "\t%d materials\n", ms->nmats);
612	greg	2.1	fprintf(fp, "\t%d patches (%.2f MBytes)\n", ms->npatches,
613			(ms->npatches*sizeof(MESHPATCH) +
614			vcnt3sizeof(uint4) +
615			nscnt*sizeof(int4) +
616			uvscnt2sizeof(uint4) +
617			tcnt*sizeof(struct PTri) +
618			t1cnt*sizeof(struct PJoin1) +
619			t2cntsizeof(struct PJoin2))/(1024.1024.));
620			fprintf(fp, "\t%d vertices (%.1f%% w/ normals, %.1f%% w/ uv)\n",
621			vcnt, 100.ncnt/vcnt, 100.uvcnt/vcnt);
622			fprintf(fp, "\t%d triangles (%.1f%% local, %.1f%% joiner)\n",
623			tcnt+t1cnt+t2cnt,
624			100.*tcnt/(tcnt+t1cnt+t2cnt),
625			100.*t1cnt/(tcnt+t1cnt+t2cnt));
626			fprintf(fp,
627			"\t%d leaves in octree (%.1f%% empty, %.2f avg. set size)\n",
628			lfcnt+lecnt, 100.*lecnt/(lfcnt+lecnt),
629			(double)locnt/lfcnt);
630			}
631
632
633			void
634			freemesh(ms) /* free mesh data */
635	greg	2.4	register MESH *ms;
636	greg	2.1	{
637			MESH mhead;
638			MESH *msp;
639
640			if (ms == NULL)
641			return;
642			if (ms->nref <= 0)
643			error(CONSISTENCY, "unreferenced mesh in freemesh");
644			ms->nref--;
645			if (ms->nref) /* still in use */
646			return;
647			/* else remove from list */
648			mhead.next = mlist;
649			for (msp = &mhead; msp->next != NULL; msp = msp->next)
650			if (msp->next == ms) {
651			msp->next = ms->next;
652			ms->next = NULL;
653			break;
654			}
655			if (ms->next != NULL) /* can't be in list anymore */
656			error(CONSISTENCY, "unlisted mesh in freemesh");
657			mlist = mhead.next;
658			/* free mesh data */
659			freestr(ms->name);
660			octfree(ms->mcube.cutree);
661	greg	2.4	lu_done(&ms->lut);
662	greg	2.1	if (ms->npatches > 0) {
663			register MESHPATCH *pp = ms->patch + ms->npatches;
664			while (pp-- > ms->patch) {
665			if (pp->j2tri != NULL)
666			free((void *)pp->j2tri);
667			if (pp->j1tri != NULL)
668			free((void *)pp->j1tri);
669			if (pp->tri != NULL)
670			free((void *)pp->tri);
671			if (pp->uv != NULL)
672			free((void *)pp->uv);
673			if (pp->norm != NULL)
674			free((void *)pp->norm);
675			if (pp->xyz != NULL)
676			free((void *)pp->xyz);
677			}
678			free((void *)ms->patch);
679			}
680	greg	2.4	if (ms->pseudo != NULL)
681			free((void *)ms->pseudo);
682	greg	2.1	free((void *)ms);
683			}
684
685
686			void
687			freemeshinst(o) /* free mesh instance */
688			OBJREC *o;
689			{
690			if (o->os == NULL)
691			return;
692			freemesh(((MESHINST )o->os).msh);
693			free((void *)o->os);
694			o->os = NULL;
695			}