--- ray/src/hd/rhd_odraw.c 1998/12/18 11:55:19 3.1 +++ ray/src/hd/rhd_odraw.c 2003/02/22 02:07:24 3.13 @@ -1,20 +1,15 @@ -/* Copyright (c) 1998 Silicon Graphics, Inc. */ - #ifndef lint -static char SCCSid[] = "$SunId$ SGI"; +static const char RCSid[] = "$Id: rhd_odraw.c,v 3.13 2003/02/22 02:07:24 greg Exp $"; #endif - /* * Routines for drawing samples using depth buffer checks. */ #include "standard.h" -#include #include #include -#include "random.h" #include "rhd_odraw.h" #ifndef DEPTHEPS @@ -26,6 +21,9 @@ static char SCCSid[] = "$SunId$ SGI"; #ifndef SFREEFRAC #define SFREEFRAC 0.2 /* fraction to free at a time */ #endif +#ifndef REDRAWTHRESH +#define REDRAWTHRESH 10240 /* number of samples for dissolve */ +#endif #ifndef MAXFAN #define MAXFAN 32 /* maximum arms in a triangle fan */ #endif @@ -38,6 +36,7 @@ static char SCCSid[] = "$SunId$ SGI"; #define NEWMAP 01 /* need to recompute mapping */ #define NEWRGB 02 /* need to remap RGB values */ +#define NEWHIST 04 /* clear histogram as well */ struct ODview *odView; /* our view list */ int odNViews; /* number of views in our list */ @@ -57,13 +56,14 @@ int n; int nbytes, i, j, k, nextsamp, count, blockdiv; int res[2]; - if (odNViews) { /* deallocate view structures */ - for (i = 0; i < odNViews; i++) { - free((char *)odView[i].bmap); + if (odNViews > 0) { /* deallocate view structures */ + for (i = odNViews; i--; ) { + free((void *)odView[i].bmap); + free((void *)odView[i].pmap); if (odView[i].emap != NULL) - free((char *)odView[i].emap); + free((void *)odView[i].emap); } - free((char *)odView); + free((void *)odView); odView = NULL; odNViews = 0; } @@ -73,7 +73,7 @@ int n; for (i = 1024; nbytes > i-8; i <<= 1) ; n = (i-8)/SAMP32 * 32; - needmapping = NEWMAP; + needmapping = NEWHIST; } if (n != odS.nsamp) { /* (re)allocate sample array */ if (odS.nsamp) @@ -108,8 +108,6 @@ int n; if (blockdiv < 8) blockdiv = 8; nextsamp = 0; count /= blockdiv*blockdiv; /* # blocks */ while (i--) { /* initialize each view */ - odView[i].emap = NULL; - odView[i].dmap = NULL; dev_auxview(i, res); odView[i].hhi = res[0]; odView[i].hlow = (res[0] + blockdiv/2) / blockdiv; @@ -117,6 +115,12 @@ int n; odView[i].vhi = res[1]; odView[i].vlow = (res[1] + blockdiv/2) / blockdiv; if (odView[i].vlow < 1) odView[i].vlow = 1; + odView[i].emap = NULL; + odView[i].dmap = NULL; + odView[i].pmap = (int4 *)calloc(FL4NELS(res[0]*res[1]), + sizeof(int4)); + if (odView[i].pmap == NULL) + return(0); j = odView[i].hlow*odView[i].vlow; odView[i].bmap = (struct ODblock *)malloc( j * sizeof(struct ODblock)); @@ -125,7 +129,9 @@ int n; DCHECK(count<=0 | nextsamp>=n, CONSISTENCY, "counter botch in odInit"); if (!i) count = j; - while (j--) { + odView[i].sfirst = nextsamp; + while (j--) { /* initialize blocks & free lists */ + odView[i].bmap[j].pthresh = FHUGE; odView[i].bmap[j].first = k = nextsamp; nextsamp += odView[i].bmap[j].nsamp = (n - nextsamp)/count--; @@ -135,10 +141,15 @@ int n; odS.nextfree(k-1) = ENDFREE; odView[i].bmap[j].nused = 0; } + odView[i].snext = nextsamp; + odView[i].n2redraw = 0; } CLR4ALL(odS.redraw, odS.nsamp); /* clear redraw flags */ - for (i = odS.nsamp; i--; ) /* clear values */ + for (i = odS.nsamp; i--; ) { /* clear values */ odS.ip[i][0] = odS.ip[i][1] = -1; + odS.brt[i] = TM_NOBRT; + } + needmapping |= NEWMAP; /* compute new map on update */ return(odS.nsamp); /* return number of samples */ } @@ -156,22 +167,54 @@ int *s0, *s1; int -odAllocBlockSamp(vn, hl, vl) /* allocate sample from block */ -int vn, hl, vl; +odAllocBlockSamp(vn, hh, vh, prox) /* allocate sample from block */ +int vn, hh, vh; +double prox; { int si[SAMPSPERBLOCK+SAMPSPERBLOCK/4]; + int hl, vl; VIEW *vw; FVECT ro, rd; int res[2]; register struct ODblock *bp; - register int i; - + register int i, j; + /* get block */ + hl = hh*odView[vn].hlow/odView[vn].hhi; + vl = vh*odView[vn].vlow/odView[vn].vhi; bp = odView[vn].bmap + vl*odView[vn].hlow + hl; - if (bp->free != ENDFREE) { /* check free list first */ + if (prox > bp->pthresh) + return(-1); /* worse than free list occupants */ + /* check for duplicate pixel */ + if (CHK4(odView[vn].pmap, vh*odView[vn].hhi + hh)) + i = bp->first + bp->nsamp; + else + i = 0; + while (i-- > bp->first) + if (hh == odS.ip[i][0] && vh == odS.ip[i][1]) { /* found it! */ + /* search free list for it */ + if (i == bp->free) + break; /* special case */ + if (bp->free != ENDFREE) + for (j = bp->free; odS.nextfree(j) != ENDFREE; + j = odS.nextfree(j)) + if (odS.nextfree(j) == i) { + odS.nextfree(j) = + odS.nextfree(i); + bp->nused++; + goto gotit; + } + if (prox >= 0.99*odS.closeness(i)) + return(-1); /* previous sample is fine */ + goto gotit; + } + if (bp->free != ENDFREE) { /* allocate from free list */ i = bp->free; + if (odS.ip[i][0] >= 0 & odS.ip[i][1] >= 0) + CLR4(odView[vn].pmap, odS.ip[i][1]*odView[vn].hhi + + odS.ip[i][0]); bp->free = odS.nextfree(i); bp->nused++; - return(i); + goto gotit; } DCHECK(bp->nsamp<=0, CONSISTENCY, "no available samples in odAllocBlockSamp"); @@ -183,13 +226,22 @@ int vn, hl, vl; for (i = bp->nsamp; i--; ) /* figure out which are worse */ si[i] = bp->first + i; qsort((char *)si, bp->nsamp, sizeof(int), sampcmp); - i = bp->nsamp*SFREEFRAC + .5; /* put them in a list */ + i = bp->nsamp*SFREEFRAC + .5; /* put them into free list */ + if (i >= bp->nsamp) i = bp->nsamp-1; /* paranoia */ + bp->pthresh = odS.closeness(si[i]); /* new proximity threshold */ while (--i > 0) { odS.nextfree(si[i]) = bp->free; bp->free = si[i]; bp->nused--; } - return(si[0]); /* return first free sample */ + i = si[0]; /* use worst sample */ + CLR4(odView[vn].pmap, odS.ip[i][1]*odView[vn].hhi + odS.ip[i][0]); +gotit: + odS.ip[i][0] = hh; + odS.ip[i][1] = vh; + odS.closeness(i) = prox; + SET4(odView[vn].pmap, vh*odView[vn].hhi + hh); + return(i); } @@ -198,9 +250,9 @@ COLR c; FVECT d, p; { FVECT disp; - double d0, d1, h, v; + double d0, d1, h, v, prox; register VIEW *vw; - int hl, vl, hh, vh; + int hh, vh; int res[2]; register int i, id; @@ -235,17 +287,15 @@ FVECT d, p; (1.+DEPTHEPS)*d0 < d1)) continue; /* occlusion error */ } - hl = hh*odView[i].hlow/res[0]; - vl = vh*odView[i].vlow/res[1]; - /* may duplicate samples */ - id = odAllocBlockSamp(i, hl, vl); - odS.ip[id][0] = hh; - odS.ip[id][1] = vh; if (p != NULL) { /* compute closeness (sin^2) */ d1 = DOT(disp, d); - odS.closeness(id) = 1. - d1*d1/DOT(disp,disp); + prox = 1. - d1*d1/DOT(disp,disp); } else - odS.closeness(id) = 0.; + prox = 0.; + /* allocate sample */ + id = odAllocBlockSamp(i, hh, vh, prox); + if (id < 0) + continue; /* not good enough */ /* convert color */ tmCvColrs(&odS.brt[id], odS.chr[id], c, 1); if (imm_mode | needmapping) /* if immediate mode */ @@ -253,16 +303,35 @@ FVECT d, p; else /* else map it now */ tmMapPixels(odS.rgb[id], &odS.brt[id], odS.chr[id], 1); SET4(odS.redraw, id); /* mark for redraw */ + odView[i].n2redraw++; } } -odRemap() /* recompute tone mapping */ +odRemap(newhist) /* recompute tone mapping */ +int newhist; { needmapping |= NEWMAP|NEWRGB; + if (newhist) + needmapping |= NEWHIST; } +odRedrawAll() /* mark all samples for redraw */ +{ + register int i; + + if ((needmapping&(NEWMAP|NEWRGB)) == (NEWMAP|NEWRGB)) + return; /* will be called later, anyway */ + for (i = odS.nsamp; i--; ) + if (odS.ip[i][0] >= 0) + SET4(odS.redraw, i); + /* not right, but not important */ + for (i = 0; i < odNViews; i++) + odView[i].n2redraw = odView[i].snext - odView[i].sfirst; +} + + odRedraw(vn, hmin, vmin, hmax, vmax) /* redraw view region */ int vn, hmin, vmin, hmax, vmax; { @@ -289,8 +358,10 @@ int vn, hmin, vmin, hmax, vmax; for (j = vmin; j <= vmax; j++) { bp = odView[vn].bmap + j*odView[vn].hlow + i; for (k = bp->nsamp; k--; ) - if (odS.ip[bp->first+k][0] >= 0) + if (odS.ip[bp->first+k][0] >= 0) { SET4(odS.redraw, bp->first+k); + odView[vn].n2redraw++; + } } } @@ -303,15 +374,17 @@ GLfloat *dm; int i, j, hmin, hmax, vmin, vmax; register int k, l; - DCHECK(vn<0 | vn>=odNViews, CONSISTENCY, - "bad view number in odDepthMap"); if (dm == NULL) { /* free edge map */ + if (vn<0 | vn>=odNViews) + return; /* too late -- they're gone! */ if (odView[vn].emap != NULL) - free((char *)odView[vn].emap); + free((void *)odView[vn].emap); odView[vn].emap = NULL; odView[vn].dmap = NULL; return; } + DCHECK(vn<0 | vn>=odNViews, CONSISTENCY, + "bad view number in odDepthMap"); odView[vn].dmap = dm; /* initialize edge map */ if (odView[vn].emap == NULL) { odView[vn].emap = (int4 *)malloc( @@ -369,49 +442,78 @@ GLfloat *dm; odUpdate(vn) /* update this view */ int vn; { - int i, j; - register struct ODblock *bp; - register int k; + static short primes[] = {9431,6803,4177,2659,1609,887,587,251,47,1}; + int myprime; + register int i, n; DCHECK(vn<0 | vn>=odNViews, CONSISTENCY, "bad view number in odUpdate"); /* need to do some tone mapping? */ if (needmapping & NEWRGB) { if (needmapping & NEWMAP) { - tmClearHisto(); + if (needmapping & NEWHIST) + tmClearHisto(); + needmapping &= ~NEWHIST; if (tmAddHisto(odS.brt,odS.nsamp,1) != TM_E_OK) return; if (tmComputeMapping(0.,0.,0.) != TM_E_OK) return; - for (k = odS.nsamp; k--; ) /* redraw all */ - if (odS.ip[k][0] >= 0) - SET4(odS.redraw, k); + needmapping &= ~NEWMAP; + odRedrawAll(); /* redraw everything */ } if (tmMapPixels(odS.rgb,odS.brt,odS.chr,odS.nsamp) != TM_E_OK) return; - needmapping = 0; /* reset flag */ + needmapping &= ~NEWRGB; } - /* draw each block in view */ - for (i = odView[vn].hlow; i--; ) - for (j = odView[vn].vlow; j--; ) { - /* get block */ - bp = odView[vn].bmap + j*odView[vn].hlow + i; - /* do quick, conservative flag check */ - for (k = (bp->first+bp->nsamp+31)>>5; - k-- > bp->first>>5; ) - if (odS.redraw[k]) - break; /* non-zero flag */ - if (k < bp->first>>5) - continue; /* no flags set */ - for (k = bp->nsamp; k--; ) /* sample by sample */ - if (CHK4(odS.redraw, bp->first+k)) { - odDrawBlockSamp(vn, i, j, bp->first+k); - CLR4(odS.redraw, bp->first+k); - } + if (odView[vn].n2redraw <= 0) + return; +#if REDRAWTHRESH + if (odView[vn].n2redraw < REDRAWTHRESH) + goto quickdraw; + /* pick a good prime step size */ + n = odView[vn].snext - odView[vn].sfirst; + for (i = 0; primes[i]<<5 >= n; i++) + ; + while ((myprime = primes[i++]) > 1) + if (n % myprime) + break; + /* dissolve in new samples */ + for (i = odView[vn].sfirst; n-- > 0; i += myprime) { + if (i >= odView[vn].snext) + i -= odView[vn].snext - odView[vn].sfirst; + if (CHK4(odS.redraw, i)) { + odDrawSamp(vn, i); + CLR4(odS.redraw, i); } + } + odView[vn].n2redraw = 0; + return; +quickdraw: /* quicker sparse flag checking */ +#endif + /* redraw samples at end */ + for (i = odView[vn].snext-31; i < odView[vn].snext; i++) + if (CHK4(odS.redraw, i)) { + odDrawSamp(vn, i); + CLR4(odS.redraw, i); + } + /* faster flag checks in middle */ + for (n = odView[vn].snext>>5; n-- > (odView[vn].sfirst+0x1f)>>5; ) + for (i = 0; odS.redraw[n]; i++) /* skips faster */ + if (odS.redraw[n] & 1L< 1, CONSISTENCY, "super-unary size in make_arms"); - na = MAXFAN*sz*sz + 0.5; /* keep area constant */ + na = MAXFAN*sz + 0.5; /* keep arc length constant */ if (na < MINFAN) na = MINFAN; hrad = FANSIZE*sz*vp->hhi/vp->hlow; vrad = FANSIZE*sz*vp->vhi/vp->vlow; if (hrad*vrad < 2.25) hrad = vrad = 1.5; - phi0 = (2.*PI) * frandom(); dv = OMAXDEPTH*sz + 0.5; for (i = 0; i < na; i++) { - phi = phi0 + (2.*PI)*i/na; + phi = (2.*PI)*i/na; ar[i][0] = cp[0] + tcos(phi)*hrad + 0.5; ar[i][1] = cp[1] + tsin(phi)*vrad + 0.5; ar[i][2] = dv; @@ -515,15 +616,15 @@ register struct ODview *vp; n = rise + run; while (n--) /* run out arm, checking depth */ if (run2 > rise2) { - if (depthchange(vp, x, y, x+xstep, y)) - break; x += xstep; rise2 += rise; - } else { - if (depthchange(vp, x, y, x, y+ystep)) + if (depthchange(vp, x-xstep, y, x, y)) break; + } else { y += ystep; run2 += run; + if (depthchange(vp, x, y-ystep, x, y)) + break; } if (n < 0) /* found something? */ return; @@ -547,36 +648,48 @@ register int h, v; } -odDrawBlockSamp(vn, h, v, id) /* draw sample in view block */ -int vn, h, v; +static int +blockedge(vp, bi0, bi1) /* check for edge between blocks? */ +register struct ODview *vp; +register int bi0, bi1; +{ + if (bi1 == bi0) + return(0); /* same block */ + if (bi1 < 0) + return(1); /* end off view */ + if (CHK4(vp->emap, bi1)) + return(1); /* end block has edges */ + if (bi1 == bi0+1 || bi1 == bi0-1 || + bi1 == bi0+vp->hlow || bi1 == bi0-vp->hlow) + return(0); /* end in adjacent block -- no edges */ + return(1); /* conservative for rarer case */ +} + + +odDrawSamp(vn, id) /* draw view sample */ +int vn; register int id; { GLshort arm[MAXFAN][3]; - int narms, blockindex, bi1; + int narms, blockindex; register struct ODview *vp; double size; int home_edges; register int i; vp = odView + vn; - blockindex = v*vp->hlow + h; - DCHECK(odS.ip[id][0]*vp->hlow/vp->hhi != h | - odS.ip[id][1]*vp->vlow/vp->vhi != v, - CONSISTENCY, "bad sample position in odDrawBlockSamp"); + blockindex = getblock(vp, odS.ip[id][0], odS.ip[id][1]); + DCHECK(blockindex<0, CONSISTENCY, "bad sample handed to odDrawSamp"); DCHECK(vp->bmap[blockindex].nused <= 0, - CONSISTENCY, "bad in-use count in odDrawBlockSamp"); + CONSISTENCY, "bad in-use count in odDrawSamp"); /* create triangle fan */ size = 1./sqrt((double)vp->bmap[blockindex].nused); narms = make_arms(arm, odS.ip[id], vp, size); if (vp->emap != NULL) { /* check for edge collisions */ home_edges = CHK4(vp->emap, blockindex); for (i = 0; i < narms; i++) - /* the following test is flawed, because we could - * be passing through a block on a diagonal run */ - if (home_edges || - ( (bi1 = getblock(vp, arm[i][0], arm[i][1])) - != blockindex && - (bi1 < 0 || CHK4(vp->emap, bi1)) )) + if (home_edges || blockedge(vp, blockindex, + getblock(vp, arm[i][0], arm[i][1]))) clip_edge(arm[i], odS.ip[id], vp); } /* draw triangle fan */