--- ray/src/hd/rhd_odraw.c 1998/12/20 20:37:53 3.2 +++ ray/src/hd/rhd_odraw.c 2005/01/07 20:33:02 3.17 @@ -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.17 2005/01/07 20:33:02 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 @@ -49,22 +47,35 @@ static int needmapping; /* what needs doing with tone #define SAMP32 (32*(2*sizeof(short)+sizeof(union ODfunion)+sizeof(TMbright)+\ - 6*sizeof(BYTE))+sizeof(int4)) + 6*sizeof(BYTE))+sizeof(int32)) -int -odInit(n) /* initialize drawing routines */ -int n; +static int sampcmp(const void *s0, const void *s1); +static int odAllocBlockSamp(int vn, int hh, int vh, double prox); +static int make_arms(GLshort ar[MAXFAN][3], short cp[2], struct ODview *vp, + double sz); +static int depthchange(struct ODview *vp, int x0, int y0, int x1, int y1); +static void clip_edge(GLshort p[3], short o[2], struct ODview *vp); +static int getblock(struct ODview *vp, int h, int v); +static int blockedge(struct ODview *vp, int bi0, int bi1); +static void odDrawSamp(int vn, int id); + + +extern int +odInit( /* initialize drawing routines */ + 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; } @@ -88,7 +99,7 @@ int n; return(0); /* assign larger alignment types earlier */ odS.f = (union ODfunion *)odS.base; - odS.redraw = (int4 *)(odS.f + n); + odS.redraw = (int32 *)(odS.f + n); odS.ip = (short (*)[2])(odS.redraw + n/32); odS.brt = (TMbright *)(odS.ip + n); odS.chr = (BYTE (*)[3])(odS.brt + n); @@ -109,8 +120,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; @@ -118,6 +127,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 = (int32 *)calloc(FL4NELS(res[0]*res[1]), + sizeof(int32)); + if (odView[i].pmap == NULL) + return(0); j = odView[i].hlow*odView[i].vlow; odView[i].bmap = (struct ODblock *)malloc( j * sizeof(struct ODblock)); @@ -126,6 +141,7 @@ int n; DCHECK(count<=0 | nextsamp>=n, CONSISTENCY, "counter botch in odInit"); if (!i) count = j; + odView[i].sfirst = nextsamp; while (j--) { /* initialize blocks & free lists */ odView[i].bmap[j].pthresh = FHUGE; odView[i].bmap[j].first = k = nextsamp; @@ -137,6 +153,8 @@ 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 */ @@ -151,24 +169,28 @@ int n; int -sampcmp(s0, s1) /* sample order, descending proximity */ -int *s0, *s1; +sampcmp( /* sample order, descending proximity */ + const void *s0, + const void *s1 +) { - register double diff = odS.closeness(*s1) - odS.closeness(*s0); + register double diff = odS.closeness(*(int*)s1) - odS.closeness(*(int*)s0); return (diff > FTINY ? 1 : diff < -FTINY ? -1 : 0); } int -odAllocBlockSamp(vn, hh, vh, prox) /* allocate sample from block */ -int vn, hh, vh; -double prox; +odAllocBlockSamp( /* allocate sample from block */ + int vn, + int hh, + int 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, j; @@ -179,7 +201,11 @@ double prox; if (prox > bp->pthresh) return(-1); /* worse than free list occupants */ /* check for duplicate pixel */ - for (i = bp->first+bp->nsamp; i-- > bp->first; ) + 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) @@ -193,12 +219,15 @@ double prox; bp->nused++; goto gotit; } - if (prox >= 0.999*odS.closeness(i)) + 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++; goto gotit; @@ -222,17 +251,22 @@ double prox; bp->nused--; } 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); } -odSample(c, d, p) /* add a sample value */ -COLR c; -FVECT d, p; +extern void +odSample( /* add a sample value */ + COLR c, + FVECT d, + FVECT p +) { FVECT disp; double d0, d1, h, v, prox; @@ -282,18 +316,22 @@ FVECT d, p; if (id < 0) continue; /* not good enough */ /* convert color */ - tmCvColrs(&odS.brt[id], odS.chr[id], c, 1); + tmCvColrs(tmGlobal, &odS.brt[id], odS.chr[id], (COLR *)c, 1); if (imm_mode | needmapping) /* if immediate mode */ needmapping |= NEWRGB; /* map it later */ else /* else map it now */ - tmMapPixels(odS.rgb[id], &odS.brt[id], odS.chr[id], 1); + tmMapPixels(tmGlobal, odS.rgb[id], &odS.brt[id], + odS.chr[id], 1); SET4(odS.redraw, id); /* mark for redraw */ + odView[i].n2redraw++; } } -odRemap(newhist) /* recompute tone mapping */ -int newhist; +extern void +odRemap( /* recompute tone mapping */ + int newhist +) { needmapping |= NEWMAP|NEWRGB; if (newhist) @@ -301,21 +339,43 @@ int newhist; } -odRedraw(vn, hmin, vmin, hmax, vmax) /* redraw view region */ -int vn, hmin, vmin, hmax, vmax; +extern void +odRedrawAll(void) /* 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; +} + + +extern void +odRedraw( /* redraw view region */ + int vn, + int hmin, + int vmin, + int hmax, + int vmax +) +{ int i, j; register struct ODblock *bp; register int k; - if (vn<0 | vn>=odNViews) + if ((vn<0) | (vn>=odNViews)) return; /* check view limits */ if (hmin < 0) hmin = 0; if (hmax >= odView[vn].hhi) hmax = odView[vn].hhi-1; if (vmin < 0) vmin = 0; if (vmax >= odView[vn].vhi) vmax = odView[vn].vhi-1; - if (hmax <= hmin | vmax <= vmin) + if ((hmax <= hmin) | (vmax <= vmin)) return; /* convert to low resolution */ hmin = hmin * odView[vn].hlow / odView[vn].hhi; @@ -327,25 +387,29 @@ 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++; + } } } -odDepthMap(vn, dm) /* assign depth map for view */ -int vn; -GLfloat *dm; +extern void +odDepthMap( /* assign depth map for view */ + int vn, + GLfloat *dm +) { double d0, d1; int i, j, hmin, hmax, vmin, vmax; register int k, l; if (dm == NULL) { /* free edge map */ - if (vn<0 | vn>=odNViews) + 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; @@ -354,8 +418,8 @@ GLfloat *dm; "bad view number in odDepthMap"); odView[vn].dmap = dm; /* initialize edge map */ if (odView[vn].emap == NULL) { - odView[vn].emap = (int4 *)malloc( - FL4NELS(odView[vn].hlow*odView[vn].vlow)*sizeof(int4)); + odView[vn].emap = (int32 *)malloc( + FL4NELS(odView[vn].hlow*odView[vn].vlow)*sizeof(int32)); if (odView[vn].emap == NULL) error(SYSTEM, "out of memory in odDepthMap"); } @@ -406,12 +470,14 @@ GLfloat *dm; } -odUpdate(vn) /* update this view */ -int vn; +extern void +odUpdate( /* 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"); @@ -419,40 +485,69 @@ int vn; if (needmapping & NEWRGB) { if (needmapping & NEWMAP) { if (needmapping & NEWHIST) - tmClearHisto(); - if (tmAddHisto(odS.brt,odS.nsamp,1) != TM_E_OK) + tmClearHisto(tmGlobal); + needmapping &= ~NEWHIST; + if (tmAddHisto(tmGlobal, odS.brt,odS.nsamp,1) != TM_E_OK) return; - if (tmComputeMapping(0.,0.,0.) != TM_E_OK) + if (tmComputeMapping(tmGlobal, 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) + if (tmMapPixels(tmGlobal, (BYTE *)(odS.rgb), odS.brt, + (BYTE *)(odS.chr), odS.nsamp) != TM_E_OK) return; - needmapping = 0; /* reset flag */ + needmapping &= ~NEWRGB; } - /* draw each block in view */ - for (j = odView[vn].vlow; j--; ) - for (i = 0; i < odView[vn].hlow; i++) { - /* 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; @@ -514,16 +609,20 @@ double sz; static int -depthchange(vp, x0, y0, x1, y1) /* check depth discontinuity */ -register struct ODview *vp; -int x0, y0, x1, y1; +depthchange( /* check depth discontinuity */ + register struct ODview *vp, + int x0, + int y0, + int x1, + int y1 +) { register double d0, d1; DCHECK(x0<0 | x0>=vp->hhi | y0<0 | y0>=vp->vhi, CONSISTENCY, "coordinates off view in depthchange"); - if (x1<0 | x1>=vp->hhi | y1<0 | y1>=vp->vhi) + if ((x1<0) | (x1>=vp->hhi) | (y1<0) | (y1>=vp->vhi)) return(1); d0 = vp->dmap[y0*vp->hhi + x0]; @@ -533,11 +632,12 @@ int x0, y0, x1, y1; } -static -clip_edge(p, o, vp) /* clip line segment to depth edge */ -GLshort p[3]; -short o[2]; -register struct ODview *vp; +static void +clip_edge( /* clip line segment to depth edge */ + GLshort p[3], + short o[2], + register struct ODview *vp +) { int x, y, xstep, ystep, rise, rise2, run, run2, n; @@ -556,15 +656,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; @@ -578,46 +678,64 @@ register struct ODview *vp; static int -getblock(vp, h, v) /* get block index */ -register struct ODview *vp; -register int h, v; +getblock( /* get block index */ + register struct ODview *vp, + register int h, + register int v +) { - if (h<0 | h>=vp->hhi | v<0 | v>=vp->vhi) + if ((h<0) | (h>=vp->hhi) | (v<0) | (v>=vp->vhi)) return(-1); return(h*vp->hlow/vp->hhi + v*vp->vlow/vp->vhi*vp->hlow); } -odDrawBlockSamp(vn, h, v, id) /* draw sample in view block */ -int vn, h, v; -register int id; +static int +blockedge( /* check for edge between blocks? */ + register struct ODview *vp, + register int bi0, + register int 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 */ +} + + +static void +odDrawSamp( /* 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 */