--- ray/src/hd/sm_ogl.c 1998/09/03 08:14:29 3.3 +++ ray/src/hd/sm_ogl.c 1998/12/28 18:07:35 3.10 @@ -16,11 +16,12 @@ static char SCCSid[] = "$SunId$ SGI"; #include #include #endif -#include "object.h" +#include "sm_flag.h" #include "sm_list.h" #include "sm_geom.h" +#include "sm_qtree.h" +#include "sm_stree.h" #include "sm.h" -#include "lookup.h" #ifdef TEST_DRIVER #include "sm_draw.h" @@ -29,133 +30,100 @@ MAKE STATIC LATER: ui.c using for now; */ char smClean_notify = TRUE; #else -static char smClean_notify = TRUE; +static int smClean_notify = TRUE; #endif -extern unsigned long qthash(); -extern int qtcmp(); -extern int free(); - -static LUTAB qtr_tab = {qthash,qtcmp,NULL,(void (*)())free,0,NULL,0}; - typedef struct { - BYTE rgb[3]; /* average color */ float dist; /* average distance */ + BYTE rgb[3]; /* average color */ } QTRAVG; /* average quadtree value */ +typedef struct { + QUADTREE qt; /* quadtree node (key & hash value) */ + QTRAVG av; /* node average */ +} QT_LUENT; /* lookup table entry */ -unsigned long -qthash(qtc) /* hash a quadtree node value */ -char *qtc; -{ - register unsigned long qt = qtc; +static QT_LUENT *qt_htbl = NULL; /* quadtree cache */ +static int qt_hsiz = 0; /* quadtree cache size */ - return(qt>>10 ^ qt<<5); -} -int -qtcmp(qt1, qt2) -char *qt1, *qt2; + /* + * smClean() : display has been wiped clean + * + * Called after display has been effectively cleared, meaning that all + * geometry must be resent down the pipeline in the next call to smUpdate(). + */ +smClean() { - return(qt1 - qt2); + smClean_notify = TRUE; } - int -mark_active_tris(qtptr,arg) -QUADTREE *qtptr; -char *arg; +qtCache_init(nel) /* initialize for at least nel elements */ +int nel; { - QUADTREE qt = *qtptr; - OBJECT os[QT_MAX_SET+1],*optr; - register int i,t_id; + static int hsiztab[] = { + 8191, 16381, 32749, 65521, 131071, 262139, 524287, 1048573, 0 + }; + register int i; - if (!QT_IS_LEAF(qt)) - return(TRUE); - /* For each triangle in the set, set the which flag*/ - qtgetset(os,qt); - - for (i = QT_SET_CNT(os), optr = QT_SET_PTR(os); i > 0; i--) - { - t_id = QT_SET_NEXT_ELEM(optr); - /* Set the render flag */ - if(SM_IS_NTH_T_BASE(smMesh,t_id)) - continue; - SM_SET_NTH_T_ACTIVE(smMesh,t_id); - /* FOR NOW:Also set the LRU clock bit: MAY WANT TO CHANGE: */ - SM_SET_NTH_T_LRU(smMesh,t_id); - } - return(TRUE); + if (nel <= 0) { /* call to free table */ + if (qt_hsiz) { + free((char *)qt_htbl); + qt_htbl = NULL; + qt_hsiz = 0; + } + return(0); + } + nel += nel>>1; /* 66% occupancy */ + for (i = 0; hsiztab[i]; i++) + if (hsiztab[i] > nel) + break; + if (!(qt_hsiz = hsiztab[i])) + qt_hsiz = nel*2 + 1; /* not always prime */ + qt_htbl = (QT_LUENT *)calloc(qt_hsiz, sizeof(QT_LUENT)); + if (qt_htbl == NULL) + qt_hsiz = 0; + for (i = qt_hsiz; i--; ) + qt_htbl[i].qt = EMPTY; + return(qt_hsiz); } -mark_tris_in_frustum(view) -VIEW *view; +QT_LUENT * +qtCache_find(qt) /* find a quadtree table entry */ +QUADTREE qt; { - FVECT nr[4],far[4]; + int i, n; + register int ndx; + register QT_LUENT *le; - /* Mark triangles in approx. view frustum as being active:set - LRU counter: for use in discarding samples when out - of space - Radiance often has no far clipping plane: but driver will set - dev_zmin,dev_zmax to satisfy OGL - */ - - /* First clear all the quadtree node and triangle active flags */ - qtClearAllFlags(); - smClear_flags(smMesh,T_ACTIVE_FLAG); - - /* calculate the world space coordinates of the view frustum */ - calculate_view_frustum(view->vp,view->hvec,view->vvec,view->horiz, - view->vert, dev_zmin,dev_zmax,nr,far); - - /* Project the view frustum onto the spherical quadtree */ - /* For every cell intersected by the projection of the faces - of the frustum: mark all triangles in the cell as ACTIVE- - Also set the triangles LRU clock counter - */ - /* Near face triangles */ - smLocator_apply_func(smMesh,nr[0],nr[2],nr[3],mark_active_tris,NULL); - smLocator_apply_func(smMesh,nr[2],nr[0],nr[1],mark_active_tris,NULL); - /* Right face triangles */ - smLocator_apply_func(smMesh,nr[0],far[3],far[0],mark_active_tris,NULL); - smLocator_apply_func(smMesh,far[3],nr[0],nr[3],mark_active_tris,NULL); - /* Left face triangles */ - smLocator_apply_func(smMesh,nr[1],far[2],nr[2],mark_active_tris,NULL); - smLocator_apply_func(smMesh,far[2],nr[1],far[1],mark_active_tris,NULL); - /* Top face triangles */ - smLocator_apply_func(smMesh,nr[0],far[0],nr[1],mark_active_tris,NULL); - smLocator_apply_func(smMesh,nr[1],far[0],far[1],mark_active_tris,NULL); - /* Bottom face triangles */ - smLocator_apply_func(smMesh,nr[3],nr[2],far[3],mark_active_tris,NULL); - smLocator_apply_func(smMesh,nr[2],far[2],far[3],mark_active_tris,NULL); - /* Far face triangles */ - smLocator_apply_func(smMesh,far[0],far[2],far[1],mark_active_tris,NULL); - smLocator_apply_func(smMesh,far[2],far[0],far[3],mark_active_tris,NULL); - -#ifdef TEST_DRIVER - VCOPY(FrustumFar[0],far[0]); - VCOPY(FrustumFar[1],far[1]); - VCOPY(FrustumFar[2],far[2]); - VCOPY(FrustumFar[3],far[3]); - VCOPY(FrustumNear[0],nr[0]); - VCOPY(FrustumNear[1],nr[1]); - VCOPY(FrustumNear[2],nr[2]); - VCOPY(FrustumNear[3],nr[3]); -#endif + if (qt_hsiz == 0 && !qtCache_init(1)) + return(NULL); +tryagain: /* hash table lookup */ + ndx = (unsigned long)qt % qt_hsiz; + for (i = 0, n = 1; i < qt_hsiz; i++, n += 2) { + le = &qt_htbl[ndx]; + if (QT_IS_EMPTY(le->qt) || le->qt == qt) + return(le); + if ((ndx += n) >= qt_hsiz) /* this happens rarely */ + ndx = ndx % qt_hsiz; + } + /* table is full, reallocate */ + le = qt_htbl; + ndx = qt_hsiz; + if (!qtCache_init(ndx+1)) { /* no more memory! */ + qt_htbl = le; + qt_hsiz = ndx; + return(NULL); + } + /* copy old table to new and free */ + while (ndx--) + if (!QT_IS_EMPTY(le[ndx].qt)) + copystruct(qtCache_find(le[ndx].qt), &le[ndx]); + free((char *)le); + goto tryagain; /* should happen only once! */ } -/* - * smClean() : display has been wiped clean - * - * Called after display has been effectively cleared, meaning that all - * geometry must be resent down the pipeline in the next call to smUpdate(). - */ -smClean() -{ - smClean_notify = TRUE; -} - - stCount_level_leaves(lcnt, qt) /* count quadtree leaf nodes at each level */ int lcnt[]; register QUADTREE qt; @@ -171,7 +139,8 @@ register QUADTREE qt; stCount_level_leaves(lcnt+1, QT_NTH_CHILD(qt,3)); } else - lcnt[0]++; + if(QT_LEAF_IS_FLAG(qt)) + lcnt[0]++; } @@ -183,19 +152,20 @@ SM *sm; int lvl; { FVECT a,b,c; - LUENT *le; + register QT_LUENT *le; QTRAVG *rc[4]; - register QTRAVG *ra; + TRI *tri; if (QT_IS_EMPTY(qt)) /* empty leaf node */ return(NULL); if (QT_IS_TREE(qt) && !QT_IS_FLAG(qt)) /* not in our frustum */ return(NULL); + if(QT_IS_LEAF(qt) && !QT_LEAF_IS_FLAG(qt)) /* not in our frustum */ + return(NULL); /* else look up node */ - if ((le = lu_find(&qtr_tab,(char *)qt)) == NULL) - goto nomemory; - ra = (QTRAVG *)le->data; - if (QT_IS_TREE(qt) && (ra == NULL || lvl > 0)) + if ((le = qtCache_find(qt)) == NULL) + error(SYSTEM, "out of memory in qtRender_level"); + if (QT_IS_TREE(qt) && (QT_IS_EMPTY(le->qt) || lvl > 0)) { /* compute children */ qtSubdivide_tri(v0,v1,v2,a,b,c); rc[0] = qtRender_level(QT_NTH_CHILD(qt,0),v0,a,c,sm,lvl-1); @@ -203,33 +173,43 @@ int lvl; rc[2] = qtRender_level(QT_NTH_CHILD(qt,2),c,b,v2,sm,lvl-1); rc[3] = qtRender_level(QT_NTH_CHILD(qt,3),b,c,a,sm,lvl-1); } - if (ra == NULL) + if (QT_IS_EMPTY(le->qt)) { /* let's make some data! */ int rgbs[3]; double distsum; - int i; - register int n; + register int i, n; /* average our triangle vertices */ rgbs[0] = rgbs[1] = rgbs[2] = 0; distsum = 0.; n = 0; if(QT_IS_TREE(qt)) { /* from subtree */ for (i = 4; i--; ) - if ((ra = rc[i]) != NULL) + if (rc[i] != NULL) { - rgbs[0] += ra->rgb[0]; rgbs[1] += ra->rgb[1]; rgbs[2] += ra->rgb[2]; - distsum += ra->dist; n++; + rgbs[0] += rc[i]->rgb[0]; rgbs[1] += rc[i]->rgb[1]; + rgbs[2] += rc[i]->rgb[2]; distsum += rc[i]->dist; n++; } } else { /* from triangle set */ - OBJECT os[QT_MAX_SET+1]; + OBJECT *os; int s0, s1, s2; - qtgetset(os,qt); + os = qtqueryset(qt); for (n = os[0]; n; n--) { - qtTri_from_id(os[n],a,b,c,NULL,NULL,NULL,&s0,&s1,&s2); + if(SM_IS_NTH_T_BASE(sm,os[n])) + continue; + tri = SM_NTH_TRI(sm,os[n]); + if(!T_IS_VALID(tri)) + continue; + + s0 = T_NTH_V(tri,0); + s1 = T_NTH_V(tri,1); + s2 = T_NTH_V(tri,2); + VCOPY(a,SM_NTH_WV(sm,s0)); + VCOPY(b,SM_NTH_WV(sm,s1)); + VCOPY(c,SM_NTH_WV(sm,s2)); distsum += SM_BG_SAMPLE(sm,s0) ? dev_zmax : sqrt(dist2(a,SM_VIEW_CENTER(sm))); distsum += SM_BG_SAMPLE(sm,s1) ? dev_zmax @@ -247,31 +227,26 @@ int lvl; } if (!n) return(NULL); - if ((ra = (QTRAVG *)malloc(sizeof(QTRAVG))) == NULL) - goto nomemory; - ra->rgb[0] = rgbs[0]/n; ra->rgb[1] = rgbs[1]/n; ra->rgb[2] = rgbs[2]/n; - ra->dist = distsum/(double)n; - le->key = (char *)qt; - le->data = (char *)ra; + le->qt = qt; + le->av.rgb[0] = rgbs[0]/n; le->av.rgb[1] = rgbs[1]/n; + le->av.rgb[2] = rgbs[2]/n; le->av.dist = distsum/(double)n; } if (lvl == 0 || (lvl > 0 && QT_IS_LEAF(qt))) { /* render this node */ /* compute pseudo vertices */ VCOPY(a,v0); VCOPY(b,v1); VCOPY(c,v2); normalize(a); normalize(b); normalize(c); - VSUM(a,SM_VIEW_CENTER(sm),a,ra->dist); - VSUM(b,SM_VIEW_CENTER(sm),b,ra->dist); - VSUM(c,SM_VIEW_CENTER(sm),c,ra->dist); + VSUM(a,SM_VIEW_CENTER(sm),a,le->av.dist); + VSUM(b,SM_VIEW_CENTER(sm),b,le->av.dist); + VSUM(c,SM_VIEW_CENTER(sm),c,le->av.dist); /* draw triangle */ - glColor3ub(ra->rgb[0],ra->rgb[1],ra->rgb[2]); - /* NOTE: Triangle vertex order may change */ - glVertex3d(c[0],c[1],c[2]); - glVertex3d(b[0],b[1],b[2]); + glColor3ub(le->av.rgb[0],le->av.rgb[1],le->av.rgb[2]); glVertex3d(a[0],a[1],a[2]); + glVertex3d(b[0],b[1],b[2]); + glVertex3d(c[0],c[1],c[2]); + } - return(ra); -nomemory: - error(SYSTEM, "out of memory in qtRender_level"); + return(&le->av); } @@ -279,20 +254,23 @@ smRender_stree_level(sm,lvl) SM *sm; int lvl; { - QUADTREE root; + QUADTREE qt; int i; FVECT t0,t1,t2; + STREE *st; + if (lvl < 1) return; + st = SM_LOCATOR(sm); glPushAttrib(GL_LIGHTING_BIT); glShadeModel(GL_FLAT); glBegin(GL_TRIANGLES); - for(i=0; i < 4; i++) + for(i=0; i < ST_NUM_ROOT_NODES; i++) { - root = ST_NTH_ROOT(SM_LOCATOR(sm),i); - stNth_base_verts(SM_LOCATOR(sm),i,t0,t1,t2); - qtRender_level(root,t0,t1,t2,sm,lvl-1); + qt = ST_ROOT_QT(st,i); + qtRender_level(qt,ST_NTH_V(st,i,0),ST_NTH_V(st,i,1),ST_NTH_V(st,i,2), + sm,lvl-1); } glEnd(); glPopAttrib(); @@ -305,6 +283,7 @@ int qual; { int i, ntarget; int lvlcnt[QT_MAX_LEVELS]; + STREE *st; if (qual <= 0) return; @@ -317,7 +296,11 @@ int qual; return; for (i = QT_MAX_LEVELS; i--; ) lvlcnt[i] = 0; - stCount_level_leaves(lvlcnt, SM_LOCATOR(sm)->root); + + st = SM_LOCATOR(sm); + for(i=0; i < ST_NUM_ROOT_NODES;i++) + stCount_level_leaves(lvlcnt, ST_ROOT_QT(st,i)); + for (ntarget -= lvlcnt[i=0]; i < QT_MAX_LEVELS-1; ntarget -= lvlcnt[++i]) if (ntarget < lvlcnt[i+1]) break; @@ -337,12 +320,8 @@ int clr; int j; tri = SM_NTH_TRI(sm,i); - if (clr) SM_CLEAR_NTH_T_NEW(sm,i); - - /* NOTE:Triangles are defined clockwise:historical relative to spherical - tris: could change - */ - for(j=2; j>= 0; j--) + if (clr) SM_CLR_NTH_T_NEW(sm,i); + for(j=0; j <= 2; j++) { #ifdef DEBUG if(SM_BG_SAMPLE(sm,T_NTH_V(tri,j))) @@ -368,7 +347,7 @@ int clr; int rgb[3]; tri = SM_NTH_TRI(sm,i); - if (clr) SM_CLEAR_NTH_T_NEW(sm,i); + if (clr) SM_CLR_NTH_T_NEW(sm,i); /* NOTE:Triangles are defined clockwise:historical relative to spherical tris: could change @@ -393,7 +372,7 @@ int clr; rgb[0]/=cnt; rgb[1]/=cnt; rgb[2]/=cnt; d /= (double)cnt; } - for(j=2; j>= 0; j--) + for(j=0; j <= 2; j++) { if(SM_BG_SAMPLE(sm,ids[j])) { @@ -426,12 +405,12 @@ int clr; TRI *tri; tri = SM_NTH_TRI(sm,i); - if (clr) SM_CLEAR_NTH_T_NEW(sm,i); + if (clr) SM_CLR_NTH_T_NEW(sm,i); /* NOTE:Triangles are defined clockwise:historical relative to spherical tris: could change */ - for(j=2; j>= 0; j--) + for(j=0; j <= 2; j++) { id = T_NTH_V(tri,j); glColor3ub(SM_NTH_RGB(sm,id)[0],SM_NTH_RGB(sm,id)[1], @@ -462,20 +441,18 @@ int clr; glPushAttrib(GL_DEPTH_BUFFER_BIT); /* First draw background polygons */ - glDisable(GL_DEPTH_TEST); glBegin(GL_TRIANGLES); SM_FOR_ALL_ACTIVE_BG_TRIS(sm,i) smRender_bg_tri(sm,i,vp,d,clr); glEnd(); - glEnable(GL_DEPTH_TEST); glBegin(GL_TRIANGLES); SM_FOR_ALL_ACTIVE_FG_TRIS(sm,i) { if(!SM_MIXED_TRI(sm,i)) smRender_tri(sm,i,vp,clr); - else + else smRender_mixed_tri(sm,i,vp,clr); } glEnd(); @@ -494,10 +471,7 @@ int i; tri = SM_NTH_TRI(sm,i); - /* Triangles are defined clockwise:historical relative to spherical - tris: could change - */ - for(j=2; j >=0; j--) + for(j=0; j <= 2; j++) { VCOPY(ptr,SM_NTH_WV(sm,T_NTH_V(tri,j))); glVertex3d(ptr[0],ptr[1],ptr[2]); @@ -541,6 +515,13 @@ T_DEPTH *td; continue; } tri = SM_NTH_TRI(sm,t_id); +#ifdef DEBUG + if(i >= smNew_tri_cnt) + { + eputs("smDepth_sort_tris():More tris than reported by smNew_tri_cnt\n"); + break; + } +#endif td[i].tri = t_id; min_d = -1; for(j=0;j < 3;j++) @@ -594,7 +575,7 @@ int clr; /* Turn Depth Test off -- using Painter's algorithm */ glPushAttrib(GL_DEPTH_BUFFER_BIT); - glDisable(GL_DEPTH_TEST); + glDepthFunc(GL_ALWAYS); d = (dev_zmin+dev_zmax)/2.0; /* Now render back-to front */ /* First render bg triangles */ @@ -603,7 +584,7 @@ int clr; smRender_bg_tri(sm,pop_list(&bglist),vp,d,clr); glEnd(); - glEnable(GL_DEPTH_TEST); + glBegin(GL_TRIANGLES); i=0; while(td[i].tri != -1) @@ -641,31 +622,37 @@ smUpdate(view,qual) epsilon is calculated as running avg of distance of sample points from canonical view: m = 1/(AVG(1/r)): some fraction of this */ + + if(!smMesh) + return; + + + d = DIST(view->vp,SM_VIEW_CENTER(smMesh)); if(qual >= 100 && d > SM_ALLOWED_VIEW_CHANGE(smMesh)) { /* Re-build the mesh */ #ifdef TEST_DRIVER odev.v = *view; -#endif - smRebuild_mesh(smMesh,view->vp); +#endif + mark_tris_in_frustum(view); + smRebuild_mesh(smMesh,view); } /* This is our final update iff qual==100 and view==&odev.v */ last_update = qual>=100 && view==&(odev.v); /* Check if we should draw ALL triangles in current frustum */ - if(smClean_notify || smNew_tri_cnt > SM_NUM_TRIS(smMesh)*SM_INC_PERCENT) + if(smClean_notify || smNew_tri_cnt > SM_SAMPLE_TRIS(smMesh)*SM_INC_PERCENT) { #ifdef TEST_DRIVER glClear(GL_COLOR_BUFFER_BIT | GL_DEPTH_BUFFER_BIT); #else - if (SM_TONE_MAP(smMesh) < SM_NUM_SAMP(smMesh)) + if ( SM_TONE_MAP(smMesh) < SM_NUM_SAMP(smMesh)) { tmClearHisto(); tmAddHisto(SM_BRT(smMesh),SM_NUM_SAMP(smMesh),1); - if(tmComputeMapping(0.,0.,0.) != TM_E_OK || - tmMapPixels(SM_RGB(smMesh),SM_BRT(smMesh),SM_CHR(smMesh), - SM_NUM_SAMP(smMesh)) != TM_E_OK) - return; + tmComputeMapping(0.,0.,0.); + tmMapPixels(SM_RGB(smMesh),SM_BRT(smMesh),SM_CHR(smMesh), + SM_NUM_SAMP(smMesh)); } #endif mark_tris_in_frustum(view); @@ -680,8 +667,8 @@ smUpdate(view,qual) } /* Do an incremental update instead */ else - { - if(!smNew_tri_cnt) + { + if(!smNew_tri_cnt) return; #ifdef TEST_DRIVER glDrawBuffer(GL_FRONT); @@ -694,9 +681,9 @@ smUpdate(view,qual) if(tmComputeMapping(0.,0.,0.) != TM_E_OK) return; } - if(tmMapPixels(SM_NTH_RGB(smMesh,t),&SM_NTH_BRT(smMesh,t), - SM_NTH_CHR(smMesh,t), SM_NUM_SAMP(smMesh)-t) != TM_E_OK) - return; + tmMapPixels(SM_NTH_RGB(smMesh,t),&SM_NTH_BRT(smMesh,t), + SM_NTH_CHR(smMesh,t), SM_NUM_SAMP(smMesh)-t); + #endif smUpdate_Rendered_mesh(smMesh,view->vp,last_update); @@ -704,12 +691,15 @@ smUpdate(view,qual) glDrawBuffer(GL_BACK); #endif } + SM_TONE_MAP(smMesh) = SM_NUM_SAMP(smMesh); + if (last_update) { smClean_notify = FALSE; smNew_tri_cnt = 0; - lu_done(&qtr_tab); + smClear_flags(smMesh,T_NEW_FLAG); + qtCache_init(0); } }