Back to index

radiance  4R0+20100331
rhd_odraw.c
Go to the documentation of this file.
00001 #ifndef lint
00002 static const char    RCSid[] = "$Id: rhd_odraw.c,v 3.17 2005/01/07 20:33:02 greg Exp $";
00003 #endif
00004 /*
00005  * Routines for drawing samples using depth buffer checks.
00006  */
00007 
00008 #include "standard.h"
00009 
00010 #include <GL/glx.h>
00011 #include <GL/glu.h>
00012 
00013 #include "rhd_odraw.h"
00014 
00015 #ifndef DEPTHEPS
00016 #define DEPTHEPS     0.02          /* depth epsilon */
00017 #endif
00018 #ifndef SAMPSPERBLOCK
00019 #define SAMPSPERBLOCK       1024          /* target samples per image block */
00020 #endif
00021 #ifndef SFREEFRAC
00022 #define SFREEFRAC    0.2           /* fraction to free at a time */
00023 #endif
00024 #ifndef REDRAWTHRESH
00025 #define REDRAWTHRESH 10240         /* number of samples for dissolve */
00026 #endif
00027 #ifndef MAXFAN
00028 #define MAXFAN              32            /* maximum arms in a triangle fan */
00029 #endif
00030 #ifndef MINFAN
00031 #define MINFAN              4             /* minimum arms in a triangle fan */
00032 #endif
00033 #ifndef FANSIZE
00034 #define FANSIZE             3.5           /* fan sizing factor */
00035 #endif
00036 
00037 #define NEWMAP              01            /* need to recompute mapping */
00038 #define NEWRGB              02            /* need to remap RGB values */
00039 #define NEWHIST             04            /* clear histogram as well */
00040 
00041 struct ODview *odView;      /* our view list */
00042 int    odNViews;            /* number of views in our list */
00043 
00044 struct ODsamp odS;          /* sample values */
00045 
00046 static int    needmapping;  /* what needs doing with tone map */
00047 
00048 
00049 #define SAMP32       (32*(2*sizeof(short)+sizeof(union ODfunion)+sizeof(TMbright)+\
00050                      6*sizeof(BYTE))+sizeof(int32))
00051 
00052 static int sampcmp(const void *s0, const void *s1);
00053 static int odAllocBlockSamp(int vn, int hh, int vh, double prox);
00054 static int make_arms(GLshort ar[MAXFAN][3], short cp[2], struct ODview *vp,
00055               double sz);
00056 static int depthchange(struct ODview *vp, int x0, int y0, int x1, int y1);
00057 static void clip_edge(GLshort p[3], short o[2], struct ODview *vp);
00058 static int getblock(struct ODview *vp, int h, int v);
00059 static int blockedge(struct ODview *vp, int bi0, int bi1);
00060 static void odDrawSamp(int vn, int id);
00061 
00062 
00063 extern int
00064 odInit(                            /* initialize drawing routines */
00065        int    n
00066 )
00067 {
00068        int    nbytes, i, j, k, nextsamp, count, blockdiv;
00069        int    res[2];
00070 
00071        if (odNViews > 0) {         /* deallocate view structures */
00072               for (i = odNViews; i--; ) {
00073                      free((void *)odView[i].bmap);
00074                      free((void *)odView[i].pmap);
00075                      if (odView[i].emap != NULL)
00076                             free((void *)odView[i].emap);
00077               }
00078               free((void *)odView);
00079               odView = NULL;
00080               odNViews = 0;
00081        }
00082        if (n && n != odS.nsamp) {
00083                             /* round space up to nearest power of 2 */
00084               nbytes = (n+31)/32 * SAMP32;
00085               for (i = 1024; nbytes > i-8; i <<= 1)
00086                      ;
00087               n = (i-8)/SAMP32 * 32;
00088               needmapping = NEWHIST;
00089        }
00090        if (n != odS.nsamp) {       /* (re)allocate sample array */
00091               if (odS.nsamp)
00092                      free(odS.base);
00093               odS.nsamp = 0;
00094               if (!n)
00095                      return(0);
00096               nbytes = (n+31)/32 * SAMP32;
00097               odS.base = (char *)malloc(nbytes);
00098               if (odS.base == NULL)
00099                      return(0);
00100                             /* assign larger alignment types earlier */
00101               odS.f = (union ODfunion *)odS.base;
00102               odS.redraw = (int32 *)(odS.f + n);
00103               odS.ip = (short (*)[2])(odS.redraw + n/32);
00104               odS.brt = (TMbright *)(odS.ip + n);
00105               odS.chr = (BYTE (*)[3])(odS.brt + n);
00106               odS.rgb = (BYTE (*)[3])(odS.chr + n);
00107               odS.nsamp = n;
00108        }
00109        if (!n)
00110               return(0);
00111                             /* allocate view information */
00112        count = 0;                  /* count pixels */
00113        for (i = 0; dev_auxview(i, res) != NULL; i++)
00114               count += res[0]*res[1];
00115        odView = (struct ODview *)malloc(i*sizeof(struct ODview));
00116        if (odView == NULL)
00117               return(0);
00118        odNViews = i;
00119        blockdiv = sqrt(count/(n/SAMPSPERBLOCK)) + 0.5;
00120        if (blockdiv < 8) blockdiv = 8;
00121        nextsamp = 0; count /= blockdiv*blockdiv; /* # blocks */
00122        while (i--) {               /* initialize each view */
00123               dev_auxview(i, res);
00124               odView[i].hhi = res[0];
00125               odView[i].hlow = (res[0] + blockdiv/2) / blockdiv;
00126               if (odView[i].hlow < 1) odView[i].hlow = 1;
00127               odView[i].vhi = res[1];
00128               odView[i].vlow = (res[1] + blockdiv/2) / blockdiv;
00129               if (odView[i].vlow < 1) odView[i].vlow = 1;
00130               odView[i].emap = NULL;
00131               odView[i].dmap = NULL;
00132               odView[i].pmap = (int32 *)calloc(FL4NELS(res[0]*res[1]),
00133                             sizeof(int32));
00134               if (odView[i].pmap == NULL)
00135                      return(0);
00136               j = odView[i].hlow*odView[i].vlow;
00137               odView[i].bmap = (struct ODblock *)malloc(
00138                             j * sizeof(struct ODblock));
00139               if (odView[i].bmap == NULL)
00140                      return(0);
00141               DCHECK(count<=0 | nextsamp>=n,
00142                             CONSISTENCY, "counter botch in odInit");
00143               if (!i) count = j;
00144               odView[i].sfirst = nextsamp;
00145               while (j--) {        /* initialize blocks & free lists */
00146                      odView[i].bmap[j].pthresh = FHUGE;
00147                      odView[i].bmap[j].first = k = nextsamp;
00148                      nextsamp += odView[i].bmap[j].nsamp = 
00149                             (n - nextsamp)/count--;
00150                      odView[i].bmap[j].free = k;
00151                      while (++k < nextsamp)
00152                             odS.nextfree(k-1) = k;
00153                      odS.nextfree(k-1) = ENDFREE;
00154                      odView[i].bmap[j].nused = 0;
00155               }
00156               odView[i].snext = nextsamp;
00157               odView[i].n2redraw = 0;
00158        }
00159        CLR4ALL(odS.redraw, odS.nsamp);           /* clear redraw flags */
00160        for (i = odS.nsamp; i--; ) {              /* clear values */
00161               odS.ip[i][0] = odS.ip[i][1] = -1;
00162               odS.brt[i] = TM_NOBRT;
00163        }
00164        needmapping |= NEWMAP;                    /* compute new map on update */
00165        return(odS.nsamp);                 /* return number of samples */
00166 }
00167 
00168 #undef SAMP32
00169 
00170 
00171 int
00172 sampcmp(                    /* sample order, descending proximity */
00173        const void    *s0,
00174        const void    *s1
00175 )
00176 {
00177        register double      diff = odS.closeness(*(int*)s1) - odS.closeness(*(int*)s0);
00178 
00179        return (diff > FTINY ? 1 : diff < -FTINY ? -1 : 0);
00180 }
00181 
00182 
00183 int
00184 odAllocBlockSamp(    /* allocate sample from block */
00185        int    vn,
00186        int    hh,
00187        int    vh,
00188        double prox
00189 )
00190 {
00191        int    si[SAMPSPERBLOCK+SAMPSPERBLOCK/4];
00192        int    hl, vl;
00193        VIEW   *vw;
00194        int    res[2];
00195        register struct ODblock     *bp;
00196        register int  i, j;
00197                                    /* get block */
00198        hl = hh*odView[vn].hlow/odView[vn].hhi;
00199        vl = vh*odView[vn].vlow/odView[vn].vhi;
00200        bp = odView[vn].bmap + vl*odView[vn].hlow + hl;
00201        if (prox > bp->pthresh)
00202               return(-1);          /* worse than free list occupants */
00203                                    /* check for duplicate pixel */
00204        if (CHK4(odView[vn].pmap, vh*odView[vn].hhi + hh))
00205               i = bp->first + bp->nsamp;
00206        else
00207               i = 0;
00208        while (i-- > bp->first)
00209               if (hh == odS.ip[i][0] && vh == odS.ip[i][1]) {  /* found it! */
00210                                           /* search free list for it */
00211                      if (i == bp->free)
00212                             break;        /* special case */
00213                      if (bp->free != ENDFREE)
00214                             for (j = bp->free; odS.nextfree(j) != ENDFREE;
00215                                           j = odS.nextfree(j))
00216                                    if (odS.nextfree(j) == i) {
00217                                           odS.nextfree(j) =
00218                                                  odS.nextfree(i);
00219                                           bp->nused++;
00220                                           goto gotit;
00221                                    }
00222                      if (prox >= 0.99*odS.closeness(i))
00223                             return(-1);   /* previous sample is fine */
00224                      goto gotit;
00225               }
00226        if (bp->free != ENDFREE) {  /* allocate from free list */
00227               i = bp->free;
00228               if ((odS.ip[i][0] >= 0) & (odS.ip[i][1] >= 0))
00229                      CLR4(odView[vn].pmap, odS.ip[i][1]*odView[vn].hhi +
00230                                                  odS.ip[i][0]);
00231               bp->free = odS.nextfree(i);
00232               bp->nused++;
00233               goto gotit;
00234        }
00235        DCHECK(bp->nsamp<=0, CONSISTENCY,
00236                      "no available samples in odAllocBlockSamp");
00237        DCHECK(bp->nsamp > sizeof(si)/sizeof(si[0]), CONSISTENCY,
00238                      "too many samples in odAllocBlockSamp");
00239                                    /* free some samples */
00240        if ((vw = dev_auxview(vn, res)) == NULL)
00241               error(CONSISTENCY, "bad view number in odAllocBlockSamp");
00242        for (i = bp->nsamp; i--; )  /* figure out which are worse */
00243               si[i] = bp->first + i;
00244        qsort((char *)si, bp->nsamp, sizeof(int), sampcmp);
00245        i = bp->nsamp*SFREEFRAC + .5;      /* put them into free list */
00246        if (i >= bp->nsamp) i = bp->nsamp-1;      /* paranoia */
00247        bp->pthresh = odS.closeness(si[i]);       /* new proximity threshold */
00248        while (--i > 0) {
00249               odS.nextfree(si[i]) = bp->free;
00250               bp->free = si[i];
00251               bp->nused--;
00252        }
00253        i = si[0];                  /* use worst sample */
00254        CLR4(odView[vn].pmap, odS.ip[i][1]*odView[vn].hhi + odS.ip[i][0]);
00255 gotit:
00256        odS.ip[i][0] = hh;
00257        odS.ip[i][1] = vh;
00258        odS.closeness(i) = prox;
00259        SET4(odView[vn].pmap, vh*odView[vn].hhi + hh);
00260        return(i);
00261 }
00262 
00263 
00264 extern void
00265 odSample(                   /* add a sample value */
00266        COLR   c,
00267        FVECT  d,
00268        FVECT  p
00269 )
00270 {
00271        FVECT  disp;
00272        double d0, d1, h, v, prox;
00273        register VIEW *vw;
00274        int    hh, vh;
00275        int    res[2];
00276        register int  i, id;
00277 
00278        DCHECK(odS.nsamp<=0, CONSISTENCY, "no samples allocated in odSample");
00279                                           /* add value to each view */
00280        for (i = 0; (vw = dev_auxview(i, res)) != NULL; i++) {
00281               DCHECK(i>=odNViews, CONSISTENCY, "too many views in odSample");
00282               CHECK(vw->type!=VT_PER, INTERNAL,
00283                             "cannot handle non-perspective views");
00284               if (p != NULL) {            /* compute view position */
00285                      VSUB(disp, p, vw->vp);
00286                      d0 = DOT(disp, vw->vdir);
00287                      if (d0 <= vw->vfore+FTINY)
00288                             continue;            /* too close */
00289               } else {
00290                      VCOPY(disp, d);
00291                      d0 = DOT(disp, vw->vdir);
00292                      if (d0 <= FTINY)            /* behind view */
00293                             continue;
00294               }
00295               h = DOT(disp,vw->hvec)/(d0*vw->hn2) + 0.5 - vw->hoff;
00296               if (h < 0. || h >= 1.)
00297                      continue;                   /* left or right */
00298               v = DOT(disp,vw->vvec)/(d0*vw->vn2) + 0.5 - vw->voff;
00299               if (v < 0. || v >= 1.)
00300                      continue;                   /* above or below */
00301               hh = h * res[0];
00302               vh = v * res[1];
00303               if (odView[i].dmap != NULL) {             /* check depth */
00304                      d1 = odView[i].dmap[vh*res[0] + hh];
00305                      if (d1 < 0.99*FHUGE && (d0 > (1.+DEPTHEPS)*d1 ||
00306                                           (1.+DEPTHEPS)*d0 < d1))
00307                      continue;                   /* occlusion error */
00308               }
00309               if (p != NULL) {            /* compute closeness (sin^2) */
00310                      d1 = DOT(disp, d);
00311                      prox = 1. - d1*d1/DOT(disp,disp);
00312               } else
00313                      prox = 0.;
00314                                           /* allocate sample */
00315               id = odAllocBlockSamp(i, hh, vh, prox);
00316               if (id < 0)
00317                      continue;            /* not good enough */
00318                                                  /* convert color */
00319               tmCvColrs(tmGlobal, &odS.brt[id], odS.chr[id], (COLR *)c, 1);
00320               if (imm_mode | needmapping)        /* if immediate mode */
00321                      needmapping |= NEWRGB;             /* map it later */
00322               else                               /* else map it now */
00323                      tmMapPixels(tmGlobal, odS.rgb[id], &odS.brt[id],
00324                                    odS.chr[id], 1);
00325               SET4(odS.redraw, id);                     /* mark for redraw */
00326               odView[i].n2redraw++;
00327        }
00328 }
00329 
00330 
00331 extern void
00332 odRemap(                    /* recompute tone mapping */
00333        int    newhist
00334 )
00335 {
00336        needmapping |= NEWMAP|NEWRGB;
00337        if (newhist)
00338               needmapping |= NEWHIST;
00339 }
00340 
00341 
00342 extern void
00343 odRedrawAll(void)                         /* mark all samples for redraw */
00344 {
00345        register int  i;
00346 
00347        if ((needmapping&(NEWMAP|NEWRGB)) == (NEWMAP|NEWRGB))
00348               return;                     /* will be called later, anyway */
00349        for (i = odS.nsamp; i--; )
00350               if (odS.ip[i][0] >= 0)
00351                      SET4(odS.redraw, i);
00352                                    /* not right, but not important */
00353        for (i = 0; i < odNViews; i++)
00354               odView[i].n2redraw = odView[i].snext - odView[i].sfirst;
00355 }
00356 
00357 
00358 extern void
00359 odRedraw(     /* redraw view region */
00360        int    vn,
00361        int    hmin,
00362        int    vmin,
00363        int    hmax,
00364        int    vmax
00365 )
00366 {
00367        int    i, j;
00368        register struct ODblock     *bp;
00369        register int  k;
00370 
00371        if ((vn<0) | (vn>=odNViews))
00372               return;
00373                             /* check view limits */
00374        if (hmin < 0) hmin = 0;
00375        if (hmax >= odView[vn].hhi) hmax = odView[vn].hhi-1;
00376        if (vmin < 0) vmin = 0;
00377        if (vmax >= odView[vn].vhi) vmax = odView[vn].vhi-1;
00378        if ((hmax <= hmin) | (vmax <= vmin))
00379               return;
00380                             /* convert to low resolution */
00381        hmin = hmin * odView[vn].hlow / odView[vn].hhi;
00382        hmax = hmax * odView[vn].hlow / odView[vn].hhi;
00383        vmin = vmin * odView[vn].vlow / odView[vn].vhi;
00384        vmax = vmax * odView[vn].vlow / odView[vn].vhi;
00385                             /* mark block samples for redraw, inclusive */
00386        for (i = hmin; i <= hmax; i++)
00387               for (j = vmin; j <= vmax; j++) {
00388                      bp = odView[vn].bmap + j*odView[vn].hlow + i;
00389                      for (k = bp->nsamp; k--; )
00390                             if (odS.ip[bp->first+k][0] >= 0) {
00391                                    SET4(odS.redraw, bp->first+k);
00392                                    odView[vn].n2redraw++;
00393                             }
00394               }
00395 }
00396 
00397 
00398 extern void
00399 odDepthMap(                 /* assign depth map for view */
00400        int    vn,
00401        GLfloat       *dm
00402 )
00403 {
00404        double d0, d1;
00405        int    i, j, hmin, hmax, vmin, vmax;
00406        register int  k, l;
00407 
00408        if (dm == NULL) {                  /* free edge map */
00409               if ((vn<0) | (vn>=odNViews))
00410                      return;                     /* too late -- they're gone! */
00411               if (odView[vn].emap != NULL)
00412                      free((void *)odView[vn].emap);
00413               odView[vn].emap = NULL;
00414               odView[vn].dmap = NULL;
00415               return;
00416        }
00417        DCHECK(vn<0 | vn>=odNViews, CONSISTENCY,
00418                      "bad view number in odDepthMap");
00419        odView[vn].dmap = dm;                     /* initialize edge map */
00420        if (odView[vn].emap == NULL) {
00421               odView[vn].emap = (int32 *)malloc(
00422                      FL4NELS(odView[vn].hlow*odView[vn].vlow)*sizeof(int32));
00423               if (odView[vn].emap == NULL)
00424                      error(SYSTEM, "out of memory in odDepthMap");
00425        }
00426        CLR4ALL(odView[vn].emap, odView[vn].hlow*odView[vn].vlow);
00427                                           /* compute edge map */
00428        vmin = odView[vn].vhi;                    /* enter loopsville */
00429        for (j = odView[vn].vlow; j--; ) {
00430               vmax = vmin;
00431               vmin = j*odView[vn].vhi/odView[vn].vlow;
00432               hmin = odView[vn].hhi;
00433               for (i = odView[vn].hlow; i--; ) {
00434                      hmax = hmin;
00435                      hmin = i*odView[vn].hhi/odView[vn].hlow;
00436                      for (l = vmin; l < vmax; l++) {    /* vertical edges */
00437                             d1 = dm[l*odView[vn].hhi+hmin];
00438                             for (k = hmin+1; k < hmax; k++) {
00439                                    d0 = d1;
00440                                    d1 = dm[l*odView[vn].hhi+k];
00441                                    if (d0 > (1.+DEPTHEPS)*d1 ||
00442                                           (1.+DEPTHEPS)*d0 < d1) {
00443                                           SET4(odView[vn].emap,
00444                                                  j*odView[vn].hlow + i);
00445                                           break;
00446                                    }
00447                             }
00448                             if (k < hmax)
00449                                    break;
00450                      }
00451                      if (l < vmax)
00452                             continue;
00453                      for (k = hmin; k < hmax; k++) {    /* horizontal edges */
00454                             d1 = dm[vmin*odView[vn].hhi+k];
00455                             for (l = vmin+1; l < vmax; l++) {
00456                                    d0 = d1;
00457                                    d1 = dm[l*odView[vn].hhi+k];
00458                                    if (d0 > (1.+DEPTHEPS)*d1 ||
00459                                           (1.+DEPTHEPS)*d0 < d1) {
00460                                           SET4(odView[vn].emap,
00461                                                  j*odView[vn].hlow + i);
00462                                           break;
00463                                    }
00464                             }
00465                             if (l < vmax)
00466                                    break;
00467                      }
00468               }
00469        }
00470 }
00471 
00472 
00473 extern void
00474 odUpdate(                          /* update this view */
00475        int    vn
00476 )
00477 {
00478        static short  primes[] = {9431,6803,4177,2659,1609,887,587,251,47,1};
00479        int    myprime;
00480        register int  i, n;
00481 
00482        DCHECK(vn<0 | vn>=odNViews, CONSISTENCY,
00483                      "bad view number in odUpdate");
00484                                    /* need to do some tone mapping? */
00485        if (needmapping & NEWRGB) {
00486               if (needmapping & NEWMAP) {
00487                      if (needmapping & NEWHIST)
00488                             tmClearHisto(tmGlobal);
00489                      needmapping &= ~NEWHIST;
00490                      if (tmAddHisto(tmGlobal, odS.brt,odS.nsamp,1) != TM_E_OK)
00491                             return;
00492                      if (tmComputeMapping(tmGlobal, 0.,0.,0.) != TM_E_OK)
00493                             return;
00494                      needmapping &= ~NEWMAP;
00495                      odRedrawAll();                     /* redraw everything */
00496               }
00497               if (tmMapPixels(tmGlobal, (BYTE *)(odS.rgb), odS.brt,
00498                             (BYTE *)(odS.chr), odS.nsamp) != TM_E_OK)
00499                      return;
00500               needmapping &= ~NEWRGB;
00501        }
00502        if (odView[vn].n2redraw <= 0)
00503               return;
00504 #if REDRAWTHRESH
00505        if (odView[vn].n2redraw < REDRAWTHRESH)
00506               goto quickdraw;
00507                                    /* pick a good prime step size */
00508        n = odView[vn].snext - odView[vn].sfirst;
00509        for (i = 0; primes[i]<<5 >= n; i++)
00510               ;
00511        while ((myprime = primes[i++]) > 1)
00512               if (n % myprime)
00513                      break;
00514                                    /* dissolve in new samples */
00515        for (i = odView[vn].sfirst; n-- > 0; i += myprime) {
00516               if (i >= odView[vn].snext)
00517                      i -= odView[vn].snext - odView[vn].sfirst;
00518               if (CHK4(odS.redraw, i)) {
00519                      odDrawSamp(vn, i);
00520                      CLR4(odS.redraw, i);
00521               }
00522        }
00523        odView[vn].n2redraw = 0;
00524        return;
00525 quickdraw:                         /* quicker sparse flag checking */
00526 #endif
00527                                    /* redraw samples at end */
00528        for (i = odView[vn].snext-31; i < odView[vn].snext; i++)
00529               if (CHK4(odS.redraw, i)) {
00530                      odDrawSamp(vn, i);
00531                      CLR4(odS.redraw, i);
00532               }
00533                                    /* faster flag checks in middle */
00534        for (n = odView[vn].snext>>5; n-- > (odView[vn].sfirst+0x1f)>>5; )
00535               for (i = 0; odS.redraw[n]; i++)           /* skips faster */
00536                      if (odS.redraw[n] & 1L<<i) {
00537                             odDrawSamp(vn, (n<<5)+i);
00538                             odS.redraw[n] &= ~(1L<<i);
00539                      }
00540                                    /* redraw samples at beginning */
00541        for (i = odView[vn].sfirst; i < odView[vn].sfirst+31; i++)
00542               if (CHK4(odS.redraw, i)) {
00543                      odDrawSamp(vn, i);
00544                      CLR4(odS.redraw, i);
00545               }
00546        odView[vn].n2redraw = 0;
00547 }
00548 
00549 
00550                                    /* this turned out to be unnecessary */
00551 #if 0
00552 static
00553 clip_end(p, o, vp)                 /* clip line segment to view */
00554 GLshort       p[3];
00555 short  o[2];
00556 register struct ODview      *vp;
00557 {
00558        if (p[0] < 0) {
00559               p[1] = -o[0]*(p[1]-o[1])/(p[0]-o[0]) + o[1];
00560               p[2] = -o[0]*p[2]/(p[0]-o[0]);
00561               p[0] = 0;
00562        } else if (p[0] >= vp->hhi) {
00563               p[1] = (vp->hhi-1-o[0])*(p[1]-o[1])/(p[0]-o[0]) + o[1];
00564               p[2] = (vp->hhi-1-o[0])*p[2]/(p[0]-o[0]);
00565               p[0] = vp->hhi-1;
00566        }
00567        if (p[1] < 0) {
00568               p[0] = -o[1]*(p[0]-o[0])/(p[1]-o[1]) + o[0];
00569               p[2] = -o[1]*p[2]/(p[1]-o[1]);
00570               p[1] = 0;
00571        } else if (p[1] >= vp->vhi) {
00572               p[0] = (vp->vhi-1-o[1])*(p[0]-o[0])/(p[1]-o[1]) + o[0];
00573               p[2] = (vp->vhi-1-o[1])*p[2]/(p[1]-o[1]);
00574               p[1] = vp->vhi-1;
00575        }
00576 }
00577 #endif
00578 
00579 
00580 static int
00581 make_arms(           /* make arms for triangle fan */
00582        GLshort       ar[MAXFAN][3],
00583        short  cp[2],
00584        register struct ODview      *vp,
00585        double sz
00586 )
00587 {
00588        int    na, dv;
00589        double hrad, vrad, phi;
00590        register int  i;
00591 
00592        DCHECK(sz > 1, CONSISTENCY, "super-unary size in make_arms");
00593        na = MAXFAN*sz + 0.5;                     /* keep arc length constant */
00594        if (na < MINFAN) na = MINFAN;
00595        hrad = FANSIZE*sz*vp->hhi/vp->hlow;
00596        vrad = FANSIZE*sz*vp->vhi/vp->vlow;
00597        if (hrad*vrad < 2.25)
00598               hrad = vrad = 1.5;
00599        dv = OMAXDEPTH*sz + 0.5;
00600        for (i = 0; i < na; i++) {
00601               phi = (2.*PI)*i/na;
00602               ar[i][0] = cp[0] + tcos(phi)*hrad + 0.5;
00603               ar[i][1] = cp[1] + tsin(phi)*vrad + 0.5;
00604               ar[i][2] = dv;
00605               /* clip_end(ar[i], cp, vp); */
00606        }
00607        return(na);
00608 }
00609 
00610 
00611 static int
00612 depthchange(         /* check depth discontinuity */
00613        register struct ODview      *vp,
00614        int    x0,
00615        int    y0,
00616        int    x1,
00617        int    y1
00618 )
00619 {
00620        register double      d0, d1;
00621 
00622        DCHECK(x0<0 | x0>=vp->hhi | y0<0 | y0>=vp->vhi,
00623                      CONSISTENCY, "coordinates off view in depthchange");
00624 
00625        if ((x1<0) | (x1>=vp->hhi) | (y1<0) | (y1>=vp->vhi))
00626               return(1);
00627 
00628        d0 = vp->dmap[y0*vp->hhi + x0];
00629        d1 = vp->dmap[y1*vp->hhi + x1];
00630 
00631        return((1.+DEPTHEPS)*d0 < d1 || d0 > (1.+DEPTHEPS)*d1);
00632 }
00633 
00634 
00635 static void
00636 clip_edge(                  /* clip line segment to depth edge */
00637        GLshort       p[3],
00638        short  o[2],
00639        register struct ODview      *vp
00640 )
00641 {
00642        int    x, y, xstep, ystep, rise, rise2, run, run2, n;
00643 
00644        DCHECK(vp->dmap==NULL, CONSISTENCY,
00645                      "clip_edge called with no depth map");
00646        x = o[0]; y = o[1];
00647        run = p[0] - x;
00648        xstep = run > 0 ? 1 : -1;
00649        run *= xstep;
00650        rise = p[1] - y;
00651        ystep = rise > 0 ? 1 : -1;
00652        rise *= ystep;
00653        rise2 = run2 = 0;
00654        if (rise > run) rise2 = 1;
00655        else run2 = 1;
00656        n = rise + run;
00657        while (n--)                 /* run out arm, checking depth */
00658               if (run2 > rise2) {
00659                      x += xstep;
00660                      rise2 += rise;
00661                      if (depthchange(vp, x-xstep, y, x, y))
00662                             break;
00663               } else {
00664                      y += ystep;
00665                      run2 += run;
00666                      if (depthchange(vp, x, y-ystep, x, y))
00667                             break;
00668               }
00669        if (n < 0)                  /* found something? */
00670               return;
00671        if (run > rise)
00672               p[2] = (x - o[0])*p[2]/(p[0] - o[0]);
00673        else
00674               p[2] = (y - o[1])*p[2]/(p[1] - o[1]);
00675        p[0] = x;
00676        p[1] = y;
00677 }
00678 
00679 
00680 static int
00681 getblock(                   /* get block index */
00682        register struct ODview      *vp,
00683        register int  h,
00684        register int  v
00685 )
00686 {
00687        if ((h<0) | (h>=vp->hhi) | (v<0) | (v>=vp->vhi))
00688               return(-1);
00689        return(h*vp->hlow/vp->hhi + v*vp->vlow/vp->vhi*vp->hlow);
00690 }
00691 
00692 
00693 static int
00694 blockedge(                  /* check for edge between blocks? */
00695        register struct ODview      *vp,
00696        register int  bi0,
00697        register int  bi1
00698 )
00699 {
00700        if (bi1 == bi0)
00701               return(0);           /* same block */
00702        if (bi1 < 0)
00703               return(1);           /* end off view */
00704        if (CHK4(vp->emap, bi1))
00705               return(1);           /* end block has edges */
00706        if (bi1 == bi0+1 || bi1 == bi0-1 ||
00707                      bi1 == bi0+vp->hlow || bi1 == bi0-vp->hlow)
00708               return(0);           /* end in adjacent block -- no edges */
00709        return(1);                  /* conservative for rarer case */
00710 }
00711 
00712 
00713 static void
00714 odDrawSamp(                 /* draw view sample */
00715        int    vn,
00716        register int  id
00717 )
00718 {
00719        GLshort       arm[MAXFAN][3];
00720        int    narms, blockindex;
00721        register struct ODview      *vp;
00722        double size;
00723        int    home_edges;
00724        register int  i;
00725 
00726        vp = odView + vn;
00727        blockindex = getblock(vp, odS.ip[id][0], odS.ip[id][1]);
00728        DCHECK(blockindex<0, CONSISTENCY, "bad sample handed to odDrawSamp");
00729        DCHECK(vp->bmap[blockindex].nused <= 0,
00730                      CONSISTENCY, "bad in-use count in odDrawSamp");
00731                                    /* create triangle fan */
00732        size = 1./sqrt((double)vp->bmap[blockindex].nused);
00733        narms = make_arms(arm, odS.ip[id], vp, size);
00734        if (vp->emap != NULL) {            /* check for edge collisions */
00735               home_edges = CHK4(vp->emap, blockindex);
00736               for (i = 0; i < narms; i++)
00737                      if (home_edges || blockedge(vp, blockindex,
00738                                    getblock(vp, arm[i][0], arm[i][1])))
00739                             clip_edge(arm[i], odS.ip[id], vp);
00740        }
00741                                    /* draw triangle fan */
00742        glColor3ub(odS.rgb[id][0], odS.rgb[id][1], odS.rgb[id][2]);
00743        glBegin(GL_TRIANGLE_FAN);
00744        glVertex3s((GLshort)odS.ip[id][0], (GLshort)odS.ip[id][1], (GLshort)0);
00745        for (i = 0; i < narms; i++)
00746               glVertex3sv(arm[i]);
00747        glVertex3sv(arm[0]);        /* connect last to first */
00748        glEnd();
00749 }