www.pudn.com > Roamsteps20020818.zip > roamstep3.c, change:2002-08-18,size:12523b
/*
* roamstep3.c ROAM example 3: cached mesh, diamond data structure
* by Mark Duchaineau (free but copyrighted, see LibGen/COPYING)
*
*
* Here we introduce the backbone data structure for the more advanced
* features of ROAM. A diamond in ROAM is two right-isosceles (bintree)
* triangles joined on a common base edge. Diamonds will be used in
* several ways, replacing bintree triangles as the main data structure.
* Bintree triangles are still the atomic unit of drawing, but otherwise
* play no role in the frustum culling or mesh refinement/coarsening
* processes. See the file DIAMONDS.txt for more discussion.
*
*
* 2002-08-04: outlined this extension to example 2
* 2002-08-06: completed first version
* 2002-08-07: debugged and cleaned up code
* 2002-08-09: based on profiling, use parent/kid links rather than hash lookup
*
*/
#include "randtab.h" /* randomizer hashing tables */
#include "fly.h" /* wrapper of window/event support for flight apps */
#include "roam.h" /* our own defs */
#include "roamtypes.h" /* typedefs for internal use of roamstepN.c */
/*
* global values defining ROAM state (should eventually be stored in
* a global record referenced by the roam_create() return handle)
*/
int roam_lmax; /* maximum bintree refinement level */
float xcf,ycf,zcf; /* float copy of camera position in world space */
float frust_planes[6][4]; /* copy of frustum plane coefficients */
float level2dzsize[ROAM_LMAX+1]; /* max midpoint displacement per level */
roamdm dmstore; /* storage pool of diamond records */
int dmstoren; /* number of diamonds in store */
roamdm dm_free0,dm_free1; /* least and most recent unlocked diamonds */
roamdm dm_b0[3][3]; /* base diamonds level 0 */
roamdm dm_b1[4][4]; /* base diamonds level -1,-2... */
/* bintree recurse to draw */
static void drawsub(fly fl,roamdm dmp,int i,int cull);
/* get diamond from free list, returns null if out of mem */
/* does not set up the data structure in any way (see fetchkid) */
static roamdm dm_create();
/* fetch child i of diamond dm (locks it, creates as needed) */
static roamdm dm_fetchkid(roamdm c,int i);
/* increment reference count, lockcnt!=0 means not FREE to recycle */
static void dm_lock(roamdm dm);
/* decrement reference count, lockcnt==0 means FREE to recycle */
static void dm_unlock(roamdm dm);
roamhandle roam_create(fly fl)
{
printf("ROAM example library, step 3: simple split, cull and cache\n");
roam_lmax=ROAM_LMAX;
/* generate table of displacement sizes versus level */
{
int l;
for (l=0;l<=ROAM_LMAX;l++)
level2dzsize[l]=0.3f/sqrt((float)((roam_int64)1<q1=dm1; dm1->q0=dm0;
}
dm_free0=dmstore; dm_free1=dmstore+(dmstoren-1);
dm_free0->q0=(roamdm)0; dm_free1->q1=(roamdm)0;
/* set diamonds initially to be NEW and FREE */
for (i=0;ir_bound= -1; /* indicates NEW */
dm0->cull=0;
dm0->lockcnt=0;
}
}
/* allocate, position and hook up base-mesh diamonds */
/* --> see DIAMONDS.txt for detailed notes on how this works */
{
int i,j,k,di,dj,ix,jx;
roamdm dm;
/* allocate all base diamonds, setting everything but the links */
for (k=0;k<9+16;k++) {
if (k<9) {
j=k/3; i=k%3; dm_b0[j][i]=dm=dm_create();
dm->v[0]=2.0f*(float)(i-1);
dm->v[1]=2.0f*(float)(j-1);
}else{
j=(k-9)/4; i=(k-9)%4; dm_b1[j][i]=dm=dm_create();
dm->v[0]=2.0f*(float)i-3.0f;
dm->v[1]=2.0f*(float)j-3.0f;
}
dm->v[2]=0.0f;
dm->r_bound=5.0f;
dm->r_error=5.0f;
dm->p[0]=dm->p[1]=dm->a[0]=dm->a[1]=(roamdm)0;
dm->k[0]=dm->k[1]=dm->k[2]=dm->k[3]=(roamdm)0;
dm->l=(k<9?0:(((i^j)&1)?-1:-2));
dm->cull=0;
}
/* now that they all exist, set the links */
for (k=0;k<9;k++) {
j=k/3; i=k%3; dm=dm_b0[j][i];
di=(((i^j)&1)?1:-1); dj=1;
ix=(2*i+1-di)>>1; jx=(2*j+1-dj)>>1;
dm->p[0]=dm_b1[jx][ix];
ix=(2*i+1+di)>>1; jx=(2*j+1+dj)>>1;
dm->p[1]=dm_b1[jx][ix];
ix=(2*i+1-dj)>>1; jx=(2*j+1+di)>>1;
dm->a[0]=dm_b1[jx][ix];
ix=(2*i+1+dj)>>1; jx=(2*j+1-di)>>1;
dm->a[1]=dm_b1[jx][ix];
ix=(di<0?0:3); dm->p[0]->k[ix]=dm; dm->i[0]=ix;
ix=(di<0?2:1); dm->p[1]->k[ix]=dm; dm->i[1]=ix;
}
for (k=0;k<16;k++) {
j=k/4; i=k%4; dm=dm_b1[j][i];
if (j>0) dm->a[1]=dm_b1[j-1][i];
if (j<3) dm->a[0]=dm_b1[j+1][i];
if (i>0) dm->p[0]=dm_b1[j][i-1];
if (i<3) dm->p[1]=dm_b1[j][i+1];
}
/* fixup top-level z to agree with steps 1-2 */
dm_b0[1][1]->v[2]=0.19715245553463489614f;
}
return (roamhandle)0;
}
void roam_set_frustum(roamhandle rmh,fly fl)
{
int i,j;
xcf=fl->uvwxyz[9]; ycf=fl->uvwxyz[10]; zcf=fl->uvwxyz[11];
for (i=0;i<6;i++) {
for (j=0;j<4;j++) {
frust_planes[i][j]=fl->frust_planes[i][j];
}}
}
void roam_set_tricntmax(roamhandle rmh,int tricntmax)
{
/* meaningless for this version of the library */
}
void roam_set_lmax(roamhandle rmh,int lmax)
{
roam_lmax=lmax;
}
void roam_set_iqfine(roamhandle rmh,int iqfine)
{
/* not implemented yet for this version of the library */
}
void roam_draw(roamhandle rmh,fly fl)
{
/* turn on textured drawing (with the grid texture for now) */
glBindTexture(GL_TEXTURE_2D,fl->gridtex_id);
glEnable(GL_TEXTURE_2D);
/* draw a roam mesh */
{
/* recurse on the two base triangles */
drawsub(fl,dm_b1[2][1],2,0);
drawsub(fl,dm_b1[1][2],0,0);
}
/* stop texturing the draws */
glDisable(GL_TEXTURE_2D);
}
/*
* ========== internal routines ==========
*/
/*
* recursively draw a bintree triangle
*
* this version does frustum culling and caching but no crack fixups
* recursion terminates when triangle error projection is small or
* at level limit
*
* orientation of vertices:
*
* o-----------o
* |. .|
* | . . |
* | . . |
* | . . |
* | . . |
* | p |
* | /.\ |
* | / i \ |
* | / . \ |
* | / . \ |
* |/ . \|
* 1-----c-----0
* . . .
* . . .
* . . .
* . . .
* ...
* .
*/
static void drawsub(fly fl,roamdm dmp,int i,int cull)
{
roamdm dmc; /* center, split-edge diamond */
float *vc; /* center vertex */
float dx,dy,dz; /* vector from eyepoint to center vertex vc */
float rc; /* squared distance from eyepoint to vc */
/* get selected kid, create if not there, indicate recent use */
dmc=dm_fetchkid(dmp,i);
vc=dmc->v;
/* update cull flags, stop recursing if OUT */
if (cull!=CULL_ALLIN) {
int j,m;
float r;
for (j=0,m=1;j<6;j++,m<<=1) {
if (!(cull&m)) {
r=frust_planes[j][0]*vc[0]+frust_planes[j][1]*vc[1]+
frust_planes[j][2]*vc[2]+frust_planes[j][3];
if (r*r>dmc->r_bound) {
if (r>0.0f) { dm_unlock(dmc); return; } /* OUT */
cull|=m; /* IN */
} /* else still overlaps this frustum plane */
}
}
}
/* compute distance from split point to camera (squared) */
dx=vc[0]-xcf; dy=vc[1]-ycf; dz=vc[2]-zcf;
rc=dx*dx+dy*dy+dz*dz;
/* if not max level and error large on screen, recursively split */
/* otherwise draw tri */
if (dmc->lr_error>rc*0.00001f) {
if (dmc->p[0]==dmp) {
drawsub(fl,dmc,0,cull); drawsub(fl,dmc,1,cull);
}else{
drawsub(fl,dmc,2,cull); drawsub(fl,dmc,3,cull);
}
}else{
roamdm dm0,dm1; /* diamonds of other two triangle vertices */
/* determine all tri's verts */
if (dmc->p[0]==dmp) { dm0=dmc->a[0]; dm1=dmc->a[1]; }
else { dm0=dmc->a[1]; dm1=dmc->a[0]; }
/* draw the tri with simple per-tri texture the shows the grid */
glBegin(GL_TRIANGLE_STRIP);
glTexCoord2fv(fl->gridtex_t[0]); glVertex3fv(dm0->v);
glTexCoord2fv(fl->gridtex_t[1]); glVertex3fv(dmp->v);
glTexCoord2fv(fl->gridtex_t[2]); glVertex3fv(dm1->v);
glEnd();
}
/* undo locking from fetchkid() */
dm_unlock(dmc);
}
static roamdm dm_create()
{
roamdm dm;
/* recycle least recently used diamond from free list */
dm=dm_free0;
if (!dm) {
fprintf(stderr,"roam: out of diamond storage\n");
/* to do: get all calling code to deal with out-of-mem failure */
/* return (roamdm)0; */
exit(1);
}
/* if not NEW, unlink from parents */
if (dm->r_bound>=0.0f) {
dm->p[0]->k[dm->i[0]]=(roamdm)0; dm_unlock(dm->p[0]);
dm->p[1]->k[dm->i[1]]=(roamdm)0; dm_unlock(dm->p[1]);
}
/* lock and return it */
dm_lock(dm);
return dm;
}
static roamdm dm_fetchkid(roamdm c,int i)
{
int ix;
roamdm k,px,cx;
float *vc;
/* return right away if already there */
if ((k=c->k[i])) { dm_lock(k); return k; }
/* need to create kid */
/* lock center diamond early to avoid recycling it on kid create */
dm_lock(c);
/* allocate new kid */
k=dm_create(); /* locks new kid */
/* recursively create other parent to kid i */
if (i<2) { px=c->p[0]; ix=(c->i[0]+(i==0?1:-1))&3; }
else { px=c->p[1]; ix=(c->i[1]+(i==2?1:-1))&3; }
cx=dm_fetchkid(px,ix); /* locks other parent */
/* set all the links */
c->k[i]=k; ix=(i&1)^1; if (cx->p[1]==px) ix|=2; cx->k[ix]=k;
if (i&1) { k->p[0]=cx; k->i[0]=ix; k->p[1]=c; k->i[1]=i; }
else { k->p[0]=c; k->i[0]=i; k->p[1]=cx; k->i[1]=ix; }
k->a[0]=c->p[i>>1];
k->a[1]=c->a[((i+1)&2)>>1];
k->k[0]=k->k[1]=k->k[2]=k->k[3]=(roamdm)0;
/* compute kid level, vertex position */
k->l=c->l+1; vc=k->v;
{
float *v0,*v1,dz,ds;
v0=k->a[0]->v; v1=k->a[1]->v;
vc[0]=0.5f*(v0[0]+v1[0]);
vc[1]=0.5f*(v0[1]+v1[1]);
RANDHASHF((unsigned char *)vc,8,dz)
ds=level2dzsize[k->l];
vc[2]=0.5f*(v0[2]+v1[2])+dz*ds;
k->r_error=ds*ds;
}
/* compute radius of diamond bounding sphere (squared) */
{
float rd,rc,dx,dy,dz,*v;
v=k->p[0]->v; dx=v[0]-vc[0]; dy=v[1]-vc[1]; dz=v[2]-vc[2];
rd=dx*dx+dy*dy+dz*dz;
v=k->p[1]->v; dx=v[0]-vc[0]; dy=v[1]-vc[1]; dz=v[2]-vc[2];
rc=dx*dx+dy*dy+dz*dz; if (rc>rd) rd=rc;
v=k->a[0]->v; dx=v[0]-vc[0]; dy=v[1]-vc[1]; dz=v[2]-vc[2];
rc=dx*dx+dy*dy+dz*dz; if (rc>rd) rd=rc;
v=k->a[1]->v; dx=v[0]-vc[0]; dy=v[1]-vc[1]; dz=v[2]-vc[2];
rc=dx*dx+dy*dy+dz*dz; if (rc>rd) rd=rc;
k->r_bound=rd;
}
return k;
}
static void dm_lock(roamdm dm)
{
roamdm dm0,dm1;
/* remove from free list if first reference */
if (dm->lockcnt==0) {
dm0=dm->q0; dm1=dm->q1;
if (dm0) dm0->q1=dm1; else dm_free0=dm1;
if (dm1) dm1->q0=dm0; else dm_free1=dm0;
}
dm->lockcnt++;
}
static void dm_unlock(roamdm dm)
{
roamdm dm0;
dm->lockcnt--;
/* add to free list if no references left */
if (dm->lockcnt==0) {
dm0=dm_free1;
dm->q0=dm0; dm->q1=(roamdm)0;
if (dm0) dm0->q1=dm; else dm_free0=dm;
dm_free1=dm;
}
}