src/hd/sm_ogl.c

/* Copyright (c) 1998 Silicon Graphics, Inc. */

#ifndef lint
static char SCCSid[] = "$SunId$ SGI";
#endif

/*
 * sm_ogl.c
*/
#include "standard.h"

#include <GL/gl.h>

#ifdef TEST_DRIVER
#include <gl/device.h>
#include <GL/glu.h>
#include <glut.h>
#endif
#include "sm_flag.h"
#include "sm_list.h"
#include "sm_geom.h"
#include "sm_qtree.h"
#include "sm_stree.h"
#include "sm.h"

#ifdef TEST_DRIVER
#include "sm_draw.h"
/*static char smClean_notify = TRUE; 
MAKE STATIC LATER: ui.c using for now;
 */
char smClean_notify = TRUE; 
#else
static int smClean_notify = TRUE; 
#endif

typedef struct {
        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 */

static QT_LUENT *qt_htbl = NULL;        /* quadtree cache */
static int      qt_hsiz = 0;            /* quadtree cache size */


 /*
  * 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;
}

int
qtCache_init(nel)               /* initialize for at least nel elements */
int     nel;
{
        static int  hsiztab[] = {
                8191, 16381, 32749, 65521, 131071, 262139, 524287, 1048573, 0
        };
        register int  i;

        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);
}

QT_LUENT *
qtCache_find(qt)                /* find a quadtree table entry */
QUADTREE qt;
{
        int     i, n;
        register int    ndx;
        register QT_LUENT       *le;

        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! */
}

stCount_level_leaves(lcnt, qt)  /* count quadtree leaf nodes at each level */
int lcnt[];
register QUADTREE qt;
{
  if (QT_IS_EMPTY(qt))
    return;
  if (QT_IS_TREE(qt)) {
    if (!QT_IS_FLAG(qt))        /* not in our frustum */
      return;
    stCount_level_leaves(lcnt+1, QT_NTH_CHILD(qt,0));
    stCount_level_leaves(lcnt+1, QT_NTH_CHILD(qt,1));
    stCount_level_leaves(lcnt+1, QT_NTH_CHILD(qt,2));
    stCount_level_leaves(lcnt+1, QT_NTH_CHILD(qt,3));
  }
  else
    if(QT_LEAF_IS_FLAG(qt))
      lcnt[0]++;
}


QTRAVG *
qtRender_level(qt,v0,v1,v2,sm,lvl)
QUADTREE qt;
FVECT v0,v1,v2;
SM *sm;
int lvl;
{
  FVECT a,b,c;
  register QT_LUENT *le;
  QTRAVG *rc[4];
  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 = 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);
    rc[1] = qtRender_level(QT_NTH_CHILD(qt,1),a,v1,b,sm,lvl-1);
    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 (QT_IS_EMPTY(le->qt))
  {                                     /* let's make some data! */
    int rgbs[3];
    double distsum;
    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 (rc[i] != NULL)
        {
          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;
      int s0, s1, s2;

      os = qtqueryset(qt);
      for (n = os[0]; n; n--)
      {
        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
                                : sqrt(dist2(b,SM_VIEW_CENTER(sm)));
        distsum += SM_BG_SAMPLE(sm,s2) ? dev_zmax
                                : sqrt(dist2(c,SM_VIEW_CENTER(sm)));
        rgbs[0] += SM_NTH_RGB(sm,s0)[0] + SM_NTH_RGB(sm,s1)[0]
                  + SM_NTH_RGB(sm,s2)[0];
        rgbs[1] += SM_NTH_RGB(sm,s0)[1] + SM_NTH_RGB(sm,s1)[1]
                  + SM_NTH_RGB(sm,s2)[1];
        rgbs[2] += SM_NTH_RGB(sm,s0)[2] + SM_NTH_RGB(sm,s1)[2]
                  + SM_NTH_RGB(sm,s2)[2];
      }
      n = 3*os[0];
    }
    if (!n)
      return(NULL);
    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,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(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(&le->av);
}


smRender_stree_level(sm,lvl)
SM *sm;
int lvl;
{
  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 < ST_NUM_ROOT_NODES; i++)
  {
    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();
}


smRender_stree(sm, qual)        /* render some quadtree triangles */
SM *sm;
int qual;
{
  int i, ntarget;
  int lvlcnt[QT_MAX_LEVELS];
  STREE *st;

  if (qual <= 0)
    return;
                                /* compute rendering target */
  ntarget = 0;
  SM_FOR_ALL_ACTIVE_TRIS(sm,i)
    ntarget++;
  ntarget = ntarget*qual/100;
  if (!ntarget)
    return;
  for (i = QT_MAX_LEVELS; i--; )
    lvlcnt[i] = 0;
  
  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;
                                /* compute and render target level */
  smRender_stree_level(sm,i);
}


smRender_tri(sm,i,vp,clr)
SM *sm;
int i;
FVECT vp;
int clr;
{
  TRI *tri;
  double ptr[3];
  int j;

  tri = SM_NTH_TRI(sm,i);
  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)))
      eputs("SmRenderTri(): shouldnt have bg samples\n");
#endif
    glColor3ub(SM_NTH_RGB(sm,T_NTH_V(tri,j))[0],
               SM_NTH_RGB(sm,T_NTH_V(tri,j))[1],
               SM_NTH_RGB(sm,T_NTH_V(tri,j))[2]);
    VCOPY(ptr,SM_T_NTH_WV(sm,tri,j));
    glVertex3d(ptr[0],ptr[1],ptr[2]);
  }
}

smRender_mixed_tri(sm,i,vp,clr)
SM *sm;
int i;
FVECT vp;
int clr;
{
  TRI *tri;
  double p[3],d;
  int j,ids[3],cnt;
  int rgb[3];

  tri = SM_NTH_TRI(sm,i);
  if (clr) SM_CLR_NTH_T_NEW(sm,i);

  /* NOTE:Triangles are defined clockwise:historical relative to spherical
     tris: could change
     */
  cnt = 0;
  d = 0.0;
  rgb[0] = rgb[1] = rgb[2] = 0;
  for(j=0;j < 3;j++)
  {
      ids[j] = T_NTH_V(tri,j);
      if(!SM_BG_SAMPLE(sm,ids[j]))
      {
          rgb[0] += SM_NTH_RGB(sm,ids[j])[0];
          rgb[1] += SM_NTH_RGB(sm,ids[j])[1];
          rgb[2] += SM_NTH_RGB(sm,ids[j])[2];
          cnt++;
          d += DIST(vp,SM_NTH_WV(sm,ids[j]));
      }
  }
  if(cnt > 1)
  {
    rgb[0]/=cnt; rgb[1]/=cnt; rgb[2]/=cnt;
    d /= (double)cnt;
  } 
  for(j=0; j <= 2; j++)
  {
    if(SM_BG_SAMPLE(sm,ids[j]))
    {
        glColor3ub(rgb[0],rgb[1],rgb[2]);
        VSUB(p,SM_NTH_WV(sm,ids[j]),SM_VIEW_CENTER(sm));
        p[0] *= d;
        p[1] *= d;
        p[2] *= d;
        VADD(p,p,SM_VIEW_CENTER(sm));
    }
    else
    {
        glColor3ub(SM_NTH_RGB(sm,ids[j])[0],SM_NTH_RGB(sm,ids[j])[1],
                   SM_NTH_RGB(sm,ids[j])[2]);
        VCOPY(p,SM_NTH_WV(sm,ids[j]));
    }
    glVertex3d(p[0],p[1],p[2]);
   }
}

smRender_bg_tri(sm,i,vp,d,clr)
SM *sm;
int i;
FVECT vp;
double d;
int clr;
{
  double p[3];
  int j,id;
  TRI *tri;
  
  tri = SM_NTH_TRI(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=0; j <= 2; j++)
  {
      id = T_NTH_V(tri,j);
      glColor3ub(SM_NTH_RGB(sm,id)[0],SM_NTH_RGB(sm,id)[1],
                 SM_NTH_RGB(sm,id)[2]);
      VSUB(p,SM_NTH_WV(sm,id),SM_VIEW_CENTER(sm));
      if(dev_zmin >= 0.99)
       {
           p[0] *= d;
           p[1] *= d;
           p[2] *= d;
       }
      VADD(p,p,vp);
      glVertex3d(p[0],p[1],p[2]);
  }
}

smRender_mesh(sm,vp,clr)
SM *sm;
FVECT vp;
int clr;
{
  int i;
  TRI *tri;
  double ptr[3],d;
  int j;

  d = (dev_zmin+dev_zmax)/2.0;
  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
        smRender_mixed_tri(sm,i,vp,clr);
  }
  glEnd();

  glPopAttrib();
}

smRender_tri_edges(sm,i)
SM *sm;
int i;
{
  TRI *tri;
  int j;
  double ptr[3];


  tri = SM_NTH_TRI(sm,i);

  for(j=0; j <= 2; j++)
  {
    VCOPY(ptr,SM_NTH_WV(sm,T_NTH_V(tri,j)));
    glVertex3d(ptr[0],ptr[1],ptr[2]);
    VCOPY(ptr,SM_NTH_WV(sm,T_NTH_V(tri,(j+1)%3)));
    glVertex3d(ptr[0],ptr[1],ptr[2]);
  }
}

int
compare_tri_depths(T_DEPTH *td1,T_DEPTH *td2)
{
  double d;

  d = td2->depth-td1->depth;
  
  if(d > 0.0)
    return(1);
  if(d < 0.0)
    return(-1);
  
  return(0);
}

LIST
*smDepth_sort_tris(sm,vp,td)
SM *sm;
FVECT vp;
T_DEPTH *td;
{
  int i,j,t_id,v;
  TRI *tri;
  double d,min_d;
  LIST *tlist=NULL;

  i = 0;
  SM_FOR_ALL_NEW_TRIS(sm,t_id)
  {
    if(SM_BG_TRI(sm,t_id))
    {
        tlist = push_data(tlist,t_id);
        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++)
    {
        v = T_NTH_V(tri,j);
        if(!SM_BG_SAMPLE(sm,v))
        {
            d = DIST(vp,SM_NTH_WV(sm,v));
            if(min_d == -1 || d < min_d)
               min_d = d;
        }
    }
    td[i].depth = min_d;
    i++;
  }
  td[i].tri = -1;
  if(i)
     qsort((void *)td,i,sizeof(T_DEPTH),compare_tri_depths);
  return(tlist);
}


smUpdate_Rendered_mesh(sm,vp,clr)
SM *sm;
FVECT vp;
int clr;
{
  static T_DEPTH *td= NULL;
  static int tsize = 0;
  int i;
  GLint depth_test;
  double d;
  LIST *bglist;
  /* For all of the NEW triangles (since last update): assume
     ACTIVE. Go through and sort on depth value (from vp). Turn
     Depth Buffer test off and render back-front
     */
  /* NOTE: could malloc each time or hard code */
  if(smNew_tri_cnt > tsize)
  {
    if(td)
      free((char *)td);
    td = (T_DEPTH *)malloc(smNew_tri_cnt*sizeof(T_DEPTH));
    tsize = smNew_tri_cnt;
  }
  if(!td)
  {
    error(SYSTEM,"smUpdate_Rendered_mesh:Cannot allocate memory\n");
  }
  bglist = smDepth_sort_tris(sm,vp,td);

  /* Turn Depth Test off -- using Painter's algorithm */
  glPushAttrib(GL_DEPTH_BUFFER_BIT);
  glDepthFunc(GL_ALWAYS);
  d = (dev_zmin+dev_zmax)/2.0;
  /* Now render back-to front */
  /* First render bg triangles */
  glBegin(GL_TRIANGLES);
  while(bglist)
     smRender_bg_tri(sm,pop_list(&bglist),vp,d,clr);
  glEnd();


  glBegin(GL_TRIANGLES);
  i=0;
  while(td[i].tri != -1)
     if(!SM_MIXED_TRI(sm,td[i].tri))
        smRender_tri(sm,td[i++].tri,vp,clr);
     else
        smRender_mixed_tri(sm,td[i++].tri,vp,clr);
  glEnd();

  /* Restore Depth Test */
  glPopAttrib();
}

/*
 * smUpdate(view, qua)  : update OpenGL output geometry for view vp
 * VIEW *view;          : desired view
 * int  qual;           : quality level (percentage on linear time scale)
 *
 * Draw new geometric representation using OpenGL calls.  Assume that the
 * view has already been set up and the correct frame buffer has been
 * selected for drawing.  The quality level is on a linear scale, where 100%
 * is full (final) quality.  It is not necessary to redraw geometry that has
 * been output since the last call to smClean().  (The last view drawn will
 * be view==&odev.v each time.)
 */
smUpdate(view,qual)
   VIEW *view;
   int qual;
{
  double d;
  int last_update;
  int t;

  /* If view has moved beyond epsilon from canonical: must rebuild -
     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  
      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_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))
    {
       tmClearHisto();
       tmAddHisto(SM_BRT(smMesh),SM_NUM_SAMP(smMesh),1);
       tmComputeMapping(0.,0.,0.);
       tmMapPixels(SM_RGB(smMesh),SM_BRT(smMesh),SM_CHR(smMesh),
                   SM_NUM_SAMP(smMesh));
    }
#endif
    mark_tris_in_frustum(view);
    if (qual <= 75)
        smRender_stree(smMesh,qual);
    else
        smRender_mesh(smMesh,view->vp,last_update);
#ifdef TEST_DRIVER
    glFlush();
    glutSwapBuffers();
#endif
  }
  /* Do an incremental update instead */
  else
  {
      if(!smNew_tri_cnt)
      return;
#ifdef TEST_DRIVER
    glDrawBuffer(GL_FRONT);
#else
    t = SM_TONE_MAP(smMesh);
    if(t == 0)
    {
        tmClearHisto();
        tmAddHisto(SM_BRT(smMesh),SM_NUM_SAMP(smMesh),1);
        if(tmComputeMapping(0.,0.,0.) != 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);
    
#ifdef TEST_DRIVER
    glDrawBuffer(GL_BACK);
#endif
  }

  SM_TONE_MAP(smMesh) = SM_NUM_SAMP(smMesh);

  if (last_update)
  {
    smClean_notify = FALSE;
    smNew_tri_cnt = 0;
    smClear_flags(smMesh,T_NEW_FLAG);
    qtCache_init(0);
  }

}
Revision:	3.10
Committed:	Mon Dec 28 18:07:35 1998 UTC (26 years, 10 months ago) by gwlarson
Content type:	text/plain
Branch:	MAIN
Changes since 3.9:	+28 -202 lines
Log Message:	New insertion routine New Culling routine based on insertion algorithm Adapted old insertion code: now used by picking Point location code returns on-vertex,on-edge, or in-triangle Added on_edge case for subdivision Implemented unordered sets Removed deletion from quadtree- added set compression to replace functionality
#	User	Rev	Content
1	gwlarson	3.1	/* Copyright (c) 1998 Silicon Graphics, Inc. */
2
3			#ifndef lint
4			static char SCCSid[] = "$SunId$ SGI";
5			#endif
6
7			/*
8			* sm_ogl.c
9			*/
10			#include "standard.h"
11
12			#include <GL/gl.h>
13
14			#ifdef TEST_DRIVER
15			#include <gl/device.h>
16			#include <GL/glu.h>
17			#include <glut.h>
18			#endif
19	gwlarson	3.8	#include "sm_flag.h"
20	gwlarson	3.3	#include "sm_list.h"
21	gwlarson	3.1	#include "sm_geom.h"
22	gwlarson	3.8	#include "sm_qtree.h"
23			#include "sm_stree.h"
24	gwlarson	3.1	#include "sm.h"
25
26			#ifdef TEST_DRIVER
27			#include "sm_draw.h"
28			/*static char smClean_notify = TRUE;
29			MAKE STATIC LATER: ui.c using for now;
30			*/
31			char smClean_notify = TRUE;
32			#else
33	gwlarson	3.4	static int smClean_notify = TRUE;
34	gwlarson	3.1	#endif
35
36	gwlarson	3.3	typedef struct {
37	gwlarson	3.4	float dist; /* average distance */
38	gwlarson	3.3	BYTE rgb[3]; /* average color */
39			} QTRAVG; /* average quadtree value */
40
41	gwlarson	3.4	typedef struct {
42			QUADTREE qt; /* quadtree node (key & hash value) */
43			QTRAVG av; /* node average */
44			} QT_LUENT; /* lookup table entry */
45	gwlarson	3.3
46	gwlarson	3.5	static QT_LUENT qt_htbl = NULL; / quadtree cache */
47			static int qt_hsiz = 0; /* quadtree cache size */
48	gwlarson	3.3
49
50	gwlarson	3.10	/*
51			* smClean() : display has been wiped clean
52			*
53			* Called after display has been effectively cleared, meaning that all
54			* geometry must be resent down the pipeline in the next call to smUpdate().
55			*/
56	gwlarson	3.1	smClean()
57			{
58			smClean_notify = TRUE;
59			}
60
61	gwlarson	3.4	int
62	gwlarson	3.5	qtCache_init(nel) /* initialize for at least nel elements */
63	gwlarson	3.4	int nel;
64			{
65			static int hsiztab[] = {
66			8191, 16381, 32749, 65521, 131071, 262139, 524287, 1048573, 0
67			};
68			register int i;
69	gwlarson	3.1
70	gwlarson	3.4	if (nel <= 0) { /* call to free table */
71			if (qt_hsiz) {
72			free((char *)qt_htbl);
73			qt_htbl = NULL;
74			qt_hsiz = 0;
75			}
76			return(0);
77			}
78			nel += nel>>1; /* 66% occupancy */
79			for (i = 0; hsiztab[i]; i++)
80			if (hsiztab[i] > nel)
81			break;
82			if (!(qt_hsiz = hsiztab[i]))
83			qt_hsiz = nel2 + 1; / not always prime */
84			qt_htbl = (QT_LUENT *)calloc(qt_hsiz, sizeof(QT_LUENT));
85			if (qt_htbl == NULL)
86			qt_hsiz = 0;
87			for (i = qt_hsiz; i--; )
88			qt_htbl[i].qt = EMPTY;
89			return(qt_hsiz);
90			}
91
92			QT_LUENT *
93	gwlarson	3.5	qtCache_find(qt) /* find a quadtree table entry */
94	gwlarson	3.4	QUADTREE qt;
95			{
96			int i, n;
97			register int ndx;
98			register QT_LUENT *le;
99
100	gwlarson	3.5	if (qt_hsiz == 0 && !qtCache_init(1))
101			return(NULL);
102	gwlarson	3.4	tryagain: /* hash table lookup */
103			ndx = (unsigned long)qt % qt_hsiz;
104			for (i = 0, n = 1; i < qt_hsiz; i++, n += 2) {
105			le = &qt_htbl[ndx];
106			if (QT_IS_EMPTY(le->qt) \|\| le->qt == qt)
107			return(le);
108			if ((ndx += n) >= qt_hsiz) /* this happens rarely */
109			ndx = ndx % qt_hsiz;
110			}
111			/* table is full, reallocate */
112			le = qt_htbl;
113			ndx = qt_hsiz;
114	gwlarson	3.5	if (!qtCache_init(ndx+1)) { /* no more memory! */
115	gwlarson	3.4	qt_htbl = le;
116			qt_hsiz = ndx;
117			return(NULL);
118			}
119	gwlarson	3.5	/* copy old table to new and free */
120	gwlarson	3.4	while (ndx--)
121			if (!QT_IS_EMPTY(le[ndx].qt))
122	gwlarson	3.5	copystruct(qtCache_find(le[ndx].qt), &le[ndx]);
123	gwlarson	3.4	free((char *)le);
124			goto tryagain; /* should happen only once! */
125			}
126
127	gwlarson	3.3	stCount_level_leaves(lcnt, qt) /* count quadtree leaf nodes at each level */
128			int lcnt[];
129			register QUADTREE qt;
130			{
131			if (QT_IS_EMPTY(qt))
132			return;
133			if (QT_IS_TREE(qt)) {
134			if (!QT_IS_FLAG(qt)) /* not in our frustum */
135			return;
136			stCount_level_leaves(lcnt+1, QT_NTH_CHILD(qt,0));
137			stCount_level_leaves(lcnt+1, QT_NTH_CHILD(qt,1));
138			stCount_level_leaves(lcnt+1, QT_NTH_CHILD(qt,2));
139			stCount_level_leaves(lcnt+1, QT_NTH_CHILD(qt,3));
140			}
141			else
142	gwlarson	3.10	if(QT_LEAF_IS_FLAG(qt))
143			lcnt[0]++;
144	gwlarson	3.3	}
145
146
147			QTRAVG *
148			qtRender_level(qt,v0,v1,v2,sm,lvl)
149			QUADTREE qt;
150			FVECT v0,v1,v2;
151	gwlarson	3.1	SM *sm;
152	gwlarson	3.3	int lvl;
153			{
154			FVECT a,b,c;
155	gwlarson	3.4	register QT_LUENT *le;
156	gwlarson	3.3	QTRAVG *rc[4];
157	gwlarson	3.7	TRI *tri;
158	gwlarson	3.3
159			if (QT_IS_EMPTY(qt)) /* empty leaf node */
160			return(NULL);
161			if (QT_IS_TREE(qt) && !QT_IS_FLAG(qt)) /* not in our frustum */
162			return(NULL);
163	gwlarson	3.10	if(QT_IS_LEAF(qt) && !QT_LEAF_IS_FLAG(qt)) /* not in our frustum */
164			return(NULL);
165	gwlarson	3.3	/* else look up node */
166	gwlarson	3.5	if ((le = qtCache_find(qt)) == NULL)
167	gwlarson	3.4	error(SYSTEM, "out of memory in qtRender_level");
168			if (QT_IS_TREE(qt) && (QT_IS_EMPTY(le->qt) \|\| lvl > 0))
169	gwlarson	3.3	{ /* compute children */
170			qtSubdivide_tri(v0,v1,v2,a,b,c);
171			rc[0] = qtRender_level(QT_NTH_CHILD(qt,0),v0,a,c,sm,lvl-1);
172			rc[1] = qtRender_level(QT_NTH_CHILD(qt,1),a,v1,b,sm,lvl-1);
173			rc[2] = qtRender_level(QT_NTH_CHILD(qt,2),c,b,v2,sm,lvl-1);
174			rc[3] = qtRender_level(QT_NTH_CHILD(qt,3),b,c,a,sm,lvl-1);
175			}
176	gwlarson	3.4	if (QT_IS_EMPTY(le->qt))
177	gwlarson	3.3	{ /* let's make some data! */
178			int rgbs[3];
179			double distsum;
180	gwlarson	3.4	register int i, n;
181	gwlarson	3.3	/* average our triangle vertices */
182			rgbs[0] = rgbs[1] = rgbs[2] = 0;
183			distsum = 0.; n = 0;
184			if(QT_IS_TREE(qt))
185			{ /* from subtree */
186			for (i = 4; i--; )
187	gwlarson	3.4	if (rc[i] != NULL)
188	gwlarson	3.3	{
189	gwlarson	3.4	rgbs[0] += rc[i]->rgb[0]; rgbs[1] += rc[i]->rgb[1];
190			rgbs[2] += rc[i]->rgb[2]; distsum += rc[i]->dist; n++;
191	gwlarson	3.3	}
192			}
193			else
194			{ /* from triangle set */
195	gwlarson	3.5	OBJECT *os;
196	gwlarson	3.3	int s0, s1, s2;
197
198	gwlarson	3.5	os = qtqueryset(qt);
199	gwlarson	3.3	for (n = os[0]; n; n--)
200			{
201	gwlarson	3.9	if(SM_IS_NTH_T_BASE(sm,os[n]))
202			continue;
203	gwlarson	3.7	tri = SM_NTH_TRI(sm,os[n]);
204	gwlarson	3.8	if(!T_IS_VALID(tri))
205			continue;
206	gwlarson	3.9
207	gwlarson	3.7	s0 = T_NTH_V(tri,0);
208			s1 = T_NTH_V(tri,1);
209			s2 = T_NTH_V(tri,2);
210			VCOPY(a,SM_NTH_WV(sm,s0));
211			VCOPY(b,SM_NTH_WV(sm,s1));
212			VCOPY(c,SM_NTH_WV(sm,s2));
213	gwlarson	3.3	distsum += SM_BG_SAMPLE(sm,s0) ? dev_zmax
214			: sqrt(dist2(a,SM_VIEW_CENTER(sm)));
215			distsum += SM_BG_SAMPLE(sm,s1) ? dev_zmax
216			: sqrt(dist2(b,SM_VIEW_CENTER(sm)));
217			distsum += SM_BG_SAMPLE(sm,s2) ? dev_zmax
218			: sqrt(dist2(c,SM_VIEW_CENTER(sm)));
219			rgbs[0] += SM_NTH_RGB(sm,s0)[0] + SM_NTH_RGB(sm,s1)[0]
220			+ SM_NTH_RGB(sm,s2)[0];
221			rgbs[1] += SM_NTH_RGB(sm,s0)[1] + SM_NTH_RGB(sm,s1)[1]
222			+ SM_NTH_RGB(sm,s2)[1];
223			rgbs[2] += SM_NTH_RGB(sm,s0)[2] + SM_NTH_RGB(sm,s1)[2]
224			+ SM_NTH_RGB(sm,s2)[2];
225			}
226			n = 3*os[0];
227			}
228			if (!n)
229			return(NULL);
230	gwlarson	3.4	le->qt = qt;
231			le->av.rgb[0] = rgbs[0]/n; le->av.rgb[1] = rgbs[1]/n;
232			le->av.rgb[2] = rgbs[2]/n; le->av.dist = distsum/(double)n;
233	gwlarson	3.3	}
234			if (lvl == 0 \|\| (lvl > 0 && QT_IS_LEAF(qt)))
235			{ /* render this node */
236			/* compute pseudo vertices */
237			VCOPY(a,v0); VCOPY(b,v1); VCOPY(c,v2);
238			normalize(a); normalize(b); normalize(c);
239	gwlarson	3.4	VSUM(a,SM_VIEW_CENTER(sm),a,le->av.dist);
240			VSUM(b,SM_VIEW_CENTER(sm),b,le->av.dist);
241			VSUM(c,SM_VIEW_CENTER(sm),c,le->av.dist);
242	gwlarson	3.3	/* draw triangle */
243	gwlarson	3.4	glColor3ub(le->av.rgb[0],le->av.rgb[1],le->av.rgb[2]);
244	gwlarson	3.9	glVertex3d(a[0],a[1],a[2]);
245			glVertex3d(b[0],b[1],b[2]);
246	gwlarson	3.3	glVertex3d(c[0],c[1],c[2]);
247	gwlarson	3.9
248	gwlarson	3.3	}
249	gwlarson	3.4	return(&le->av);
250	gwlarson	3.3	}
251
252
253			smRender_stree_level(sm,lvl)
254			SM *sm;
255			int lvl;
256			{
257	gwlarson	3.10	QUADTREE qt;
258	gwlarson	3.3	int i;
259			FVECT t0,t1,t2;
260	gwlarson	3.8	STREE *st;
261	gwlarson	3.3
262	gwlarson	3.8
263	gwlarson	3.3	if (lvl < 1)
264			return;
265	gwlarson	3.8	st = SM_LOCATOR(sm);
266	gwlarson	3.3	glPushAttrib(GL_LIGHTING_BIT);
267			glShadeModel(GL_FLAT);
268			glBegin(GL_TRIANGLES);
269	gwlarson	3.8	for(i=0; i < ST_NUM_ROOT_NODES; i++)
270	gwlarson	3.3	{
271	gwlarson	3.10	qt = ST_ROOT_QT(st,i);
272			qtRender_level(qt,ST_NTH_V(st,i,0),ST_NTH_V(st,i,1),ST_NTH_V(st,i,2),
273	gwlarson	3.8	sm,lvl-1);
274	gwlarson	3.3	}
275			glEnd();
276			glPopAttrib();
277			}
278
279
280			smRender_stree(sm, qual) /* render some quadtree triangles */
281			SM *sm;
282			int qual;
283			{
284			int i, ntarget;
285			int lvlcnt[QT_MAX_LEVELS];
286	gwlarson	3.10	STREE *st;
287	gwlarson	3.3
288			if (qual <= 0)
289			return;
290			/* compute rendering target */
291			ntarget = 0;
292			SM_FOR_ALL_ACTIVE_TRIS(sm,i)
293			ntarget++;
294			ntarget = ntarget*qual/100;
295			if (!ntarget)
296			return;
297			for (i = QT_MAX_LEVELS; i--; )
298			lvlcnt[i] = 0;
299	gwlarson	3.10
300			st = SM_LOCATOR(sm);
301			for(i=0; i < ST_NUM_ROOT_NODES;i++)
302			stCount_level_leaves(lvlcnt, ST_ROOT_QT(st,i));
303
304	gwlarson	3.3	for (ntarget -= lvlcnt[i=0]; i < QT_MAX_LEVELS-1; ntarget -= lvlcnt[++i])
305			if (ntarget < lvlcnt[i+1])
306			break;
307			/* compute and render target level */
308			smRender_stree_level(sm,i);
309			}
310
311
312			smRender_tri(sm,i,vp,clr)
313			SM *sm;
314	gwlarson	3.1	int i;
315			FVECT vp;
316	gwlarson	3.3	int clr;
317	gwlarson	3.1	{
318			TRI *tri;
319			double ptr[3];
320			int j;
321
322			tri = SM_NTH_TRI(sm,i);
323	gwlarson	3.8	if (clr) SM_CLR_NTH_T_NEW(sm,i);
324	gwlarson	3.9	for(j=0; j <= 2; j++)
325	gwlarson	3.1	{
326	gwlarson	3.2	#ifdef DEBUG
327			if(SM_BG_SAMPLE(sm,T_NTH_V(tri,j)))
328			eputs("SmRenderTri(): shouldnt have bg samples\n");
329			#endif
330	gwlarson	3.1	glColor3ub(SM_NTH_RGB(sm,T_NTH_V(tri,j))[0],
331			SM_NTH_RGB(sm,T_NTH_V(tri,j))[1],
332			SM_NTH_RGB(sm,T_NTH_V(tri,j))[2]);
333			VCOPY(ptr,SM_T_NTH_WV(sm,tri,j));
334			glVertex3d(ptr[0],ptr[1],ptr[2]);
335			}
336			}
337
338	gwlarson	3.3	smRender_mixed_tri(sm,i,vp,clr)
339	gwlarson	3.1	SM *sm;
340			int i;
341			FVECT vp;
342	gwlarson	3.3	int clr;
343	gwlarson	3.1	{
344			TRI *tri;
345	gwlarson	3.3	double p[3],d;
346	gwlarson	3.1	int j,ids[3],cnt;
347	gwlarson	3.2	int rgb[3];
348	gwlarson	3.1
349	gwlarson	3.3	tri = SM_NTH_TRI(sm,i);
350	gwlarson	3.8	if (clr) SM_CLR_NTH_T_NEW(sm,i);
351	gwlarson	3.2
352	gwlarson	3.1	/* NOTE:Triangles are defined clockwise:historical relative to spherical
353			tris: could change
354			*/
355			cnt = 0;
356	gwlarson	3.3	d = 0.0;
357	gwlarson	3.1	rgb[0] = rgb[1] = rgb[2] = 0;
358	gwlarson	3.3	for(j=0;j < 3;j++)
359	gwlarson	3.1	{
360	gwlarson	3.3	ids[j] = T_NTH_V(tri,j);
361			if(!SM_BG_SAMPLE(sm,ids[j]))
362			{
363			rgb[0] += SM_NTH_RGB(sm,ids[j])[0];
364			rgb[1] += SM_NTH_RGB(sm,ids[j])[1];
365			rgb[2] += SM_NTH_RGB(sm,ids[j])[2];
366			cnt++;
367			d += DIST(vp,SM_NTH_WV(sm,ids[j]));
368			}
369	gwlarson	3.1	}
370	gwlarson	3.3	if(cnt > 1)
371	gwlarson	3.1	{
372			rgb[0]/=cnt; rgb[1]/=cnt; rgb[2]/=cnt;
373	gwlarson	3.3	d /= (double)cnt;
374	gwlarson	3.1	}
375	gwlarson	3.9	for(j=0; j <= 2; j++)
376	gwlarson	3.1	{
377			if(SM_BG_SAMPLE(sm,ids[j]))
378	gwlarson	3.3	{
379			glColor3ub(rgb[0],rgb[1],rgb[2]);
380			VSUB(p,SM_NTH_WV(sm,ids[j]),SM_VIEW_CENTER(sm));
381			p[0] *= d;
382			p[1] *= d;
383			p[2] *= d;
384			VADD(p,p,SM_VIEW_CENTER(sm));
385			}
386	gwlarson	3.1	else
387	gwlarson	3.2	{
388	gwlarson	3.3	glColor3ub(SM_NTH_RGB(sm,ids[j])[0],SM_NTH_RGB(sm,ids[j])[1],
389			SM_NTH_RGB(sm,ids[j])[2]);
390			VCOPY(p,SM_NTH_WV(sm,ids[j]));
391	gwlarson	3.2	}
392	gwlarson	3.1	glVertex3d(p[0],p[1],p[2]);
393	gwlarson	3.3	}
394			}
395
396			smRender_bg_tri(sm,i,vp,d,clr)
397			SM *sm;
398			int i;
399			FVECT vp;
400			double d;
401			int clr;
402			{
403			double p[3];
404			int j,id;
405			TRI *tri;
406
407			tri = SM_NTH_TRI(sm,i);
408	gwlarson	3.8	if (clr) SM_CLR_NTH_T_NEW(sm,i);
409	gwlarson	3.3
410			/* NOTE:Triangles are defined clockwise:historical relative to spherical
411			tris: could change
412			*/
413	gwlarson	3.9	for(j=0; j <= 2; j++)
414	gwlarson	3.3	{
415			id = T_NTH_V(tri,j);
416			glColor3ub(SM_NTH_RGB(sm,id)[0],SM_NTH_RGB(sm,id)[1],
417			SM_NTH_RGB(sm,id)[2]);
418			VSUB(p,SM_NTH_WV(sm,id),SM_VIEW_CENTER(sm));
419			if(dev_zmin >= 0.99)
420			{
421			p[0] *= d;
422			p[1] *= d;
423			p[2] *= d;
424			}
425			VADD(p,p,vp);
426			glVertex3d(p[0],p[1],p[2]);
427	gwlarson	3.1	}
428			}
429
430	gwlarson	3.3	smRender_mesh(sm,vp,clr)
431	gwlarson	3.1	SM *sm;
432			FVECT vp;
433	gwlarson	3.3	int clr;
434	gwlarson	3.1	{
435			int i;
436			TRI *tri;
437	gwlarson	3.2	double ptr[3],d;
438	gwlarson	3.1	int j;
439
440	gwlarson	3.2	d = (dev_zmin+dev_zmax)/2.0;
441	gwlarson	3.1	glPushAttrib(GL_DEPTH_BUFFER_BIT);
442
443			/* First draw background polygons */
444			glDisable(GL_DEPTH_TEST);
445			glBegin(GL_TRIANGLES);
446			SM_FOR_ALL_ACTIVE_BG_TRIS(sm,i)
447	gwlarson	3.3	smRender_bg_tri(sm,i,vp,d,clr);
448	gwlarson	3.1	glEnd();
449			glEnable(GL_DEPTH_TEST);
450			glBegin(GL_TRIANGLES);
451			SM_FOR_ALL_ACTIVE_FG_TRIS(sm,i)
452	gwlarson	3.3	{
453			if(!SM_MIXED_TRI(sm,i))
454			smRender_tri(sm,i,vp,clr);
455	gwlarson	3.8	else
456	gwlarson	3.3	smRender_mixed_tri(sm,i,vp,clr);
457			}
458	gwlarson	3.1	glEnd();
459
460			glPopAttrib();
461			}
462	gwlarson	3.3
463	gwlarson	3.1	smRender_tri_edges(sm,i)
464			SM *sm;
465			int i;
466			{
467			TRI *tri;
468			int j;
469			double ptr[3];
470
471
472			tri = SM_NTH_TRI(sm,i);
473
474	gwlarson	3.9	for(j=0; j <= 2; j++)
475	gwlarson	3.1	{
476			VCOPY(ptr,SM_NTH_WV(sm,T_NTH_V(tri,j)));
477			glVertex3d(ptr[0],ptr[1],ptr[2]);
478			VCOPY(ptr,SM_NTH_WV(sm,T_NTH_V(tri,(j+1)%3)));
479			glVertex3d(ptr[0],ptr[1],ptr[2]);
480			}
481			}
482
483			int
484			compare_tri_depths(T_DEPTH td1,T_DEPTH td2)
485			{
486			double d;
487
488			d = td2->depth-td1->depth;
489
490			if(d > 0.0)
491			return(1);
492			if(d < 0.0)
493			return(-1);
494
495			return(0);
496			}
497
498	gwlarson	3.3	LIST
499			*smDepth_sort_tris(sm,vp,td)
500	gwlarson	3.1	SM *sm;
501	gwlarson	3.3	FVECT vp;
502	gwlarson	3.1	T_DEPTH *td;
503			{
504	gwlarson	3.3	int i,j,t_id,v;
505	gwlarson	3.1	TRI *tri;
506	gwlarson	3.3	double d,min_d;
507			LIST *tlist=NULL;
508	gwlarson	3.1
509			i = 0;
510			SM_FOR_ALL_NEW_TRIS(sm,t_id)
511			{
512	gwlarson	3.3	if(SM_BG_TRI(sm,t_id))
513	gwlarson	3.1	{
514	gwlarson	3.3	tlist = push_data(tlist,t_id);
515			continue;
516	gwlarson	3.1	}
517			tri = SM_NTH_TRI(sm,t_id);
518	gwlarson	3.6	#ifdef DEBUG
519			if(i >= smNew_tri_cnt)
520			{
521			eputs("smDepth_sort_tris():More tris than reported by smNew_tri_cnt\n");
522			break;
523			}
524			#endif
525	gwlarson	3.1	td[i].tri = t_id;
526	gwlarson	3.3	min_d = -1;
527	gwlarson	3.1	for(j=0;j < 3;j++)
528	gwlarson	3.3	{
529			v = T_NTH_V(tri,j);
530			if(!SM_BG_SAMPLE(sm,v))
531			{
532			d = DIST(vp,SM_NTH_WV(sm,v));
533			if(min_d == -1 \|\| d < min_d)
534			min_d = d;
535			}
536			}
537			td[i].depth = min_d;
538	gwlarson	3.1	i++;
539			}
540	gwlarson	3.3	td[i].tri = -1;
541			if(i)
542			qsort((void *)td,i,sizeof(T_DEPTH),compare_tri_depths);
543			return(tlist);
544	gwlarson	3.1	}
545
546
547	gwlarson	3.3	smUpdate_Rendered_mesh(sm,vp,clr)
548	gwlarson	3.1	SM *sm;
549	gwlarson	3.3	FVECT vp;
550			int clr;
551	gwlarson	3.1	{
552			static T_DEPTH *td= NULL;
553			static int tsize = 0;
554			int i;
555			GLint depth_test;
556	gwlarson	3.2	double d;
557	gwlarson	3.3	LIST *bglist;
558	gwlarson	3.1	/* For all of the NEW triangles (since last update): assume
559			ACTIVE. Go through and sort on depth value (from vp). Turn
560			Depth Buffer test off and render back-front
561			*/
562			/* NOTE: could malloc each time or hard code */
563			if(smNew_tri_cnt > tsize)
564			{
565			if(td)
566	gwlarson	3.3	free((char *)td);
567	gwlarson	3.1	td = (T_DEPTH )malloc(smNew_tri_cntsizeof(T_DEPTH));
568			tsize = smNew_tri_cnt;
569			}
570			if(!td)
571			{
572			error(SYSTEM,"smUpdate_Rendered_mesh:Cannot allocate memory\n");
573			}
574	gwlarson	3.3	bglist = smDepth_sort_tris(sm,vp,td);
575	gwlarson	3.1
576	gwlarson	3.3	/* Turn Depth Test off -- using Painter's algorithm */
577	gwlarson	3.1	glPushAttrib(GL_DEPTH_BUFFER_BIT);
578	gwlarson	3.9	glDepthFunc(GL_ALWAYS);
579	gwlarson	3.2	d = (dev_zmin+dev_zmax)/2.0;
580	gwlarson	3.1	/* Now render back-to front */
581			/* First render bg triangles */
582			glBegin(GL_TRIANGLES);
583	gwlarson	3.3	while(bglist)
584			smRender_bg_tri(sm,pop_list(&bglist),vp,d,clr);
585	gwlarson	3.1	glEnd();
586
587	gwlarson	3.6
588	gwlarson	3.1	glBegin(GL_TRIANGLES);
589	gwlarson	3.3	i=0;
590			while(td[i].tri != -1)
591			if(!SM_MIXED_TRI(sm,td[i].tri))
592			smRender_tri(sm,td[i++].tri,vp,clr);
593			else
594			smRender_mixed_tri(sm,td[i++].tri,vp,clr);
595	gwlarson	3.1	glEnd();
596
597			/* Restore Depth Test */
598			glPopAttrib();
599			}
600
601			/*
602	gwlarson	3.3	* smUpdate(view, qua) : update OpenGL output geometry for view vp
603			* VIEW *view; : desired view
604	gwlarson	3.1	* int qual; : quality level (percentage on linear time scale)
605			*
606			* Draw new geometric representation using OpenGL calls. Assume that the
607			* view has already been set up and the correct frame buffer has been
608			* selected for drawing. The quality level is on a linear scale, where 100%
609			* is full (final) quality. It is not necessary to redraw geometry that has
610	gwlarson	3.3	* been output since the last call to smClean(). (The last view drawn will
611			* be view==&odev.v each time.)
612	gwlarson	3.1	*/
613	gwlarson	3.3	smUpdate(view,qual)
614			VIEW *view;
615	gwlarson	3.1	int qual;
616			{
617			double d;
618	gwlarson	3.3	int last_update;
619	gwlarson	3.1	int t;
620	gwlarson	3.3
621	gwlarson	3.1	/* If view has moved beyond epsilon from canonical: must rebuild -
622			epsilon is calculated as running avg of distance of sample points
623	gwlarson	3.3	from canonical view: m = 1/(AVG(1/r)): some fraction of this
624	gwlarson	3.1	*/
625	gwlarson	3.8
626			if(!smMesh)
627			return;
628	gwlarson	3.10
629
630
631	gwlarson	3.3	d = DIST(view->vp,SM_VIEW_CENTER(smMesh));
632	gwlarson	3.1	if(qual >= 100 && d > SM_ALLOWED_VIEW_CHANGE(smMesh))
633			{
634			/* Re-build the mesh */
635	gwlarson	3.3	#ifdef TEST_DRIVER
636			odev.v = *view;
637	gwlarson	3.8	#endif
638			mark_tris_in_frustum(view);
639			smRebuild_mesh(smMesh,view);
640	gwlarson	3.1	}
641	gwlarson	3.3	/* This is our final update iff qual==100 and view==&odev.v */
642			last_update = qual>=100 && view==&(odev.v);
643			/* Check if we should draw ALL triangles in current frustum */
644	gwlarson	3.8	if(smClean_notify \|\| smNew_tri_cnt > SM_SAMPLE_TRIS(smMesh)*SM_INC_PERCENT)
645	gwlarson	3.1	{
646			#ifdef TEST_DRIVER
647			glClear(GL_COLOR_BUFFER_BIT \| GL_DEPTH_BUFFER_BIT);
648			#else
649	gwlarson	3.8	if ( SM_TONE_MAP(smMesh) < SM_NUM_SAMP(smMesh))
650	gwlarson	3.3	{
651			tmClearHisto();
652			tmAddHisto(SM_BRT(smMesh),SM_NUM_SAMP(smMesh),1);
653	gwlarson	3.10	tmComputeMapping(0.,0.,0.);
654			tmMapPixels(SM_RGB(smMesh),SM_BRT(smMesh),SM_CHR(smMesh),
655			SM_NUM_SAMP(smMesh));
656	gwlarson	3.3	}
657	gwlarson	3.1	#endif
658	gwlarson	3.3	mark_tris_in_frustum(view);
659			if (qual <= 75)
660			smRender_stree(smMesh,qual);
661			else
662			smRender_mesh(smMesh,view->vp,last_update);
663	gwlarson	3.1	#ifdef TEST_DRIVER
664			glFlush();
665			glutSwapBuffers();
666			#endif
667			}
668			/* Do an incremental update instead */
669			else
670	gwlarson	3.8	{
671			if(!smNew_tri_cnt)
672	gwlarson	3.1	return;
673			#ifdef TEST_DRIVER
674			glDrawBuffer(GL_FRONT);
675			#else
676			t = SM_TONE_MAP(smMesh);
677			if(t == 0)
678			{
679			tmClearHisto();
680			tmAddHisto(SM_BRT(smMesh),SM_NUM_SAMP(smMesh),1);
681			if(tmComputeMapping(0.,0.,0.) != TM_E_OK)
682			return;
683			}
684	gwlarson	3.10	tmMapPixels(SM_NTH_RGB(smMesh,t),&SM_NTH_BRT(smMesh,t),
685			SM_NTH_CHR(smMesh,t), SM_NUM_SAMP(smMesh)-t);
686
687	gwlarson	3.1	#endif
688	gwlarson	3.3	smUpdate_Rendered_mesh(smMesh,view->vp,last_update);
689	gwlarson	3.1
690			#ifdef TEST_DRIVER
691			glDrawBuffer(GL_BACK);
692			#endif
693			}
694	gwlarson	3.9
695	gwlarson	3.1	SM_TONE_MAP(smMesh) = SM_NUM_SAMP(smMesh);
696	gwlarson	3.9
697	gwlarson	3.3	if (last_update)
698			{
699			smClean_notify = FALSE;
700			smNew_tri_cnt = 0;
701	gwlarson	3.6	smClear_flags(smMesh,T_NEW_FLAG);
702	gwlarson	3.5	qtCache_init(0);
703	gwlarson	3.3	}
704
705	gwlarson	3.1	}