src/hd/sm_sets.c

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

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

/*
 * Quadtree-specific set operations.
 */

#include "standard.h"

#include "sm_qtree.h"


#define QTSETIBLK       2048            /* set index allocation block size */
#define QTELEMBLK       8               /* set element allocation block */
#define QTELEMMOD(ne)   ((ne)&7)        /* (ne) % QTELEMBLK */

#define QTONTHRESH(ne)  (!QTELEMMOD((ne)+1))
#define QTNODESIZ(ne)   ((ne) + QTELEMBLK - QTELEMMOD(ne))

OBJECT  **qtsettab= NULL;               /* quadtree leaf node table */
QUADTREE  qtnumsets;                    /* number of used set indices */
static int  qtfreesets = EMPTY;         /* free set index list */


QUADTREE
qtnewleaf(oset)                 /* return new leaf node for object set */
OBJECT  *oset;
{
  register QUADTREE  osi;

  if (*oset <= 0)
    return(EMPTY);              /* should be error? */
  if (qtfreesets != EMPTY) {
    osi = qtfreesets;
    qtfreesets = (int)qtsettab[osi];
  } else if ((osi = qtnumsets++) % QTSETIBLK == 0) {
    qtsettab = (OBJECT **)realloc((char *)qtsettab,
                                  (unsigned)(osi+QTSETIBLK)*sizeof(OBJECT *));
    if (qtsettab == NULL)
      goto memerr;
  }
  qtsettab[osi] = (OBJECT *)malloc(QTNODESIZ(*oset)*sizeof(OBJECT));
  if (qtsettab[osi] == NULL)
    goto memerr;
  setcopy(qtsettab[osi], oset);
  return(QT_INDEX(osi));
memerr:
  error(SYSTEM, "out of memory in qtnewleaf");
}


QUADTREE
qtdelelem(qt, id)               /* delete element from leaf node */
QUADTREE  qt;
OBJECT  id;
{
        register QUADTREE  lf;

#ifdef DEBUG
        if(id < 0)
                eputs("qtdelelem():Invalid triangle id\n");
        if (!QT_IS_LEAF(qt) || (lf = QT_SET_INDEX(qt)) >= qtnumsets)
                error(CONSISTENCY, "empty/bad node in qtdelelem");
        if (!inset(qtsettab[lf], id))
                error(CONSISTENCY, "id not in leaf in qtdelelem");
#else
        lf = QT_SET_INDEX(qt);
#endif
        if (qtsettab[lf][0] <= 1) {             /* blow leaf away */
                free((char *)qtsettab[lf]);
                qtsettab[lf] = (OBJECT *)qtfreesets;
                qtfreesets = lf;
                return(EMPTY);
        }
        deletelem(qtsettab[lf], id);
        if (QTONTHRESH(qtsettab[lf][0]))
                qtsettab[lf] = (OBJECT *)realloc((char *)qtsettab[lf],
                                QTNODESIZ(qtsettab[lf][0])*sizeof(OBJECT));
        return(qt);
}


QUADTREE
qtaddelem(qt, id)               /* add element to leaf node */
QUADTREE  qt;
OBJECT  id;
{
        OBJECT  newset[2];
        register QUADTREE  lf;

#ifdef DEBUG
        if(id < 0)
                eputs("qtaddelem():Invalid triangle id\n");
#endif
        if (QT_IS_EMPTY(qt)) {          /* create new leaf */
                newset[0] = 1; newset[1] = id;
                return(qtnewleaf(newset));
        }                               /* else add element */
#ifdef DEBUG
        if (!QT_IS_LEAF(qt) || (lf = QT_SET_INDEX(qt)) >= qtnumsets)
                error(CONSISTENCY, "bad node in qtaddelem");
        if (inset(qtsettab[lf], id))
                error(CONSISTENCY, "id already in leaf in qtaddelem");
#else
        lf = QT_SET_INDEX(qt);
#endif
        if (QTONTHRESH(qtsettab[lf][0])) {
                qtsettab[lf] = (OBJECT *)realloc((char *)qtsettab[lf],
                                QTNODESIZ(qtsettab[lf][0]+1)*sizeof(OBJECT));
                if (qtsettab[lf] == NULL)
                        error(SYSTEM, "out of memory in qtaddelem");
        }
        insertelem(qtsettab[lf], id);
        return(qt);
}


#ifdef DEBUG
OBJECT *
qtqueryset(qt)                  /* return object set for leaf node */
QUADTREE  qt;
{
        register QUADTREE  lf;

        if (!QT_IS_LEAF(qt) || (lf = QT_SET_INDEX(qt)) >= qtnumsets)
                error(CONSISTENCY, "bad node in qtqueryset");
        return(qtsettab[lf]);
}
#endif


qtfreeleaf(qt)                  /* free set and leaf node */
QUADTREE  qt;
{
        register QUADTREE       osi;

        if (!QT_IS_LEAF(qt))
                return;
        osi = QT_SET_INDEX(qt);
        if (osi >= qtnumsets)
                return;
        free((char *)qtsettab[osi]);
        qtsettab[osi] = (OBJECT *)qtfreesets;
        qtfreesets = osi;
}


qtfreeleaves()                  /* free ALL sets and leaf nodes */
{
        register int    i;

        while ((i = qtfreesets) != EMPTY) {
                qtfreesets = (int)qtsettab[i];
                qtsettab[i] = NULL;
        }
        for (i = qtnumsets; i--; )
                if (qtsettab[i] != NULL)
                        free((char *)qtsettab[i]);
        free((char *)qtsettab);
        qtsettab = NULL;
        qtnumsets = 0;
}


check_set(os, cs)                /* modify checked set and set to check */
register OBJECT  *os;                   /* os' = os - cs */
register OBJECT  *cs;                   /* cs' = cs + os */
{
    OBJECT  cset[QT_MAXCSET+QT_MAXSET+1];
    register int  i, j;
    int  k;
                                        /* copy os in place, cset <- cs */
    cset[0] = 0;
    k = 0;
    for (i = j = 1; i <= os[0]; i++) {
        while (j <= cs[0] && cs[j] < os[i])
           cset[++cset[0]] = cs[j++];
        if (j > cs[0] || os[i] != cs[j]) {      /* object to check */
            os[++k] = os[i];
            cset[++cset[0]] = os[i];
        }
    }
    if (!(os[0] = k))               /* new "to check" set size */
       return;                 /* special case */
    while (j <= cs[0])              /* get the rest of cs */
       cset[++cset[0]] = cs[j++];
    if (cset[0] > QT_MAXCSET)          /* truncate "checked" set if nec. */
       cset[0] = QT_MAXCSET;
    /* setcopy(cs, cset); */        /* copy cset back to cs */
    os = cset;
    for (i = os[0]; i-- >= 0; )
       *cs++ = *os++;
}


Revision:	3.4
Committed:	Wed Nov 11 12:05:41 1998 UTC (25 years, 5 months ago) by gwlarson
Content type:	text/plain
Branch:	MAIN
Changes since 3.3:	+26 -18 lines
Log Message:	new triangulation code changed triangle vertex order to CCW changed numbering of triangle neighbors to match quadtree fixed tone-mapping bug removed errant printf() statements redid logic for adding and testing samples with new epsilon
#	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			* Quadtree-specific set operations.
9			*/
10
11			#include "standard.h"
12
13			#include "sm_qtree.h"
14
15	gwlarson	3.2
16			#define QTSETIBLK 2048 /* set index allocation block size */
17	gwlarson	3.1	#define QTELEMBLK 8 /* set element allocation block */
18	gwlarson	3.3	#define QTELEMMOD(ne) ((ne)&7) /* (ne) % QTELEMBLK */
19	gwlarson	3.1
20	gwlarson	3.3	#define QTONTHRESH(ne) (!QTELEMMOD((ne)+1))
21			#define QTNODESIZ(ne) ((ne) + QTELEMBLK - QTELEMMOD(ne))
22	gwlarson	3.1
23	gwlarson	3.3	OBJECT *qtsettab= NULL; / quadtree leaf node table */
24	gwlarson	3.2	QUADTREE qtnumsets; /* number of used set indices */
25	gwlarson	3.1	static int qtfreesets = EMPTY; /* free set index list */
26
27
28			QUADTREE
29			qtnewleaf(oset) /* return new leaf node for object set */
30			OBJECT *oset;
31			{
32	gwlarson	3.4	register QUADTREE osi;
33	gwlarson	3.1
34	gwlarson	3.4	if (*oset <= 0)
35			return(EMPTY); /* should be error? */
36			if (qtfreesets != EMPTY) {
37			osi = qtfreesets;
38			qtfreesets = (int)qtsettab[osi];
39			} else if ((osi = qtnumsets++) % QTSETIBLK == 0) {
40			qtsettab = (OBJECT *)realloc((char )qtsettab,
41			(unsigned)(osi+QTSETIBLK)sizeof(OBJECT ));
42			if (qtsettab == NULL)
43			goto memerr;
44			}
45			qtsettab[osi] = (OBJECT )malloc(QTNODESIZ(oset)*sizeof(OBJECT));
46			if (qtsettab[osi] == NULL)
47			goto memerr;
48			setcopy(qtsettab[osi], oset);
49			return(QT_INDEX(osi));
50	gwlarson	3.1	memerr:
51	gwlarson	3.4	error(SYSTEM, "out of memory in qtnewleaf");
52	gwlarson	3.1	}
53
54
55			QUADTREE
56	gwlarson	3.3	qtdelelem(qt, id) /* delete element from leaf node */
57	gwlarson	3.1	QUADTREE qt;
58			OBJECT id;
59			{
60			register QUADTREE lf;
61
62	gwlarson	3.2	#ifdef DEBUG
63			if(id < 0)
64			eputs("qtdelelem():Invalid triangle id\n");
65			if (!QT_IS_LEAF(qt) \|\| (lf = QT_SET_INDEX(qt)) >= qtnumsets)
66			error(CONSISTENCY, "empty/bad node in qtdelelem");
67			if (!inset(qtsettab[lf], id))
68			error(CONSISTENCY, "id not in leaf in qtdelelem");
69			#else
70	gwlarson	3.1	lf = QT_SET_INDEX(qt);
71	gwlarson	3.2	#endif
72	gwlarson	3.1	if (qtsettab[lf][0] <= 1) { /* blow leaf away */
73			free((char *)qtsettab[lf]);
74			qtsettab[lf] = (OBJECT *)qtfreesets;
75			qtfreesets = lf;
76			return(EMPTY);
77	gwlarson	3.3	}
78	gwlarson	3.1	deletelem(qtsettab[lf], id);
79	gwlarson	3.3	if (QTONTHRESH(qtsettab[lf][0]))
80	gwlarson	3.1	qtsettab[lf] = (OBJECT )realloc((char )qtsettab[lf],
81	gwlarson	3.3	QTNODESIZ(qtsettab[lf][0])*sizeof(OBJECT));
82	gwlarson	3.1	return(qt);
83			}
84
85
86			QUADTREE
87	gwlarson	3.3	qtaddelem(qt, id) /* add element to leaf node */
88	gwlarson	3.1	QUADTREE qt;
89			OBJECT id;
90			{
91			OBJECT newset[2];
92			register QUADTREE lf;
93
94	gwlarson	3.2	#ifdef DEBUG
95			if(id < 0)
96			eputs("qtaddelem():Invalid triangle id\n");
97			#endif
98	gwlarson	3.1	if (QT_IS_EMPTY(qt)) { /* create new leaf */
99			newset[0] = 1; newset[1] = id;
100			return(qtnewleaf(newset));
101			} /* else add element */
102	gwlarson	3.2	#ifdef DEBUG
103			if (!QT_IS_LEAF(qt) \|\| (lf = QT_SET_INDEX(qt)) >= qtnumsets)
104			error(CONSISTENCY, "bad node in qtaddelem");
105			if (inset(qtsettab[lf], id))
106			error(CONSISTENCY, "id already in leaf in qtaddelem");
107			#else
108	gwlarson	3.1	lf = QT_SET_INDEX(qt);
109	gwlarson	3.2	#endif
110	gwlarson	3.3	if (QTONTHRESH(qtsettab[lf][0])) {
111	gwlarson	3.1	qtsettab[lf] = (OBJECT )realloc((char )qtsettab[lf],
112	gwlarson	3.3	QTNODESIZ(qtsettab[lf][0]+1)*sizeof(OBJECT));
113	gwlarson	3.1	if (qtsettab[lf] == NULL)
114			error(SYSTEM, "out of memory in qtaddelem");
115			}
116			insertelem(qtsettab[lf], id);
117			return(qt);
118			}
119
120
121	gwlarson	3.2	#ifdef DEBUG
122			OBJECT *
123			qtqueryset(qt) /* return object set for leaf node */
124	gwlarson	3.1	QUADTREE qt;
125			{
126	gwlarson	3.2	register QUADTREE lf;
127	gwlarson	3.1
128	gwlarson	3.2	if (!QT_IS_LEAF(qt) \|\| (lf = QT_SET_INDEX(qt)) >= qtnumsets)
129			error(CONSISTENCY, "bad node in qtqueryset");
130			return(qtsettab[lf]);
131	gwlarson	3.1	}
132	gwlarson	3.2	#endif
133	gwlarson	3.1
134
135			qtfreeleaf(qt) /* free set and leaf node */
136			QUADTREE qt;
137			{
138			register QUADTREE osi;
139
140			if (!QT_IS_LEAF(qt))
141			return;
142			osi = QT_SET_INDEX(qt);
143			if (osi >= qtnumsets)
144	gwlarson	3.2	return;
145	gwlarson	3.1	free((char *)qtsettab[osi]);
146			qtsettab[osi] = (OBJECT *)qtfreesets;
147			qtfreesets = osi;
148			}
149
150
151	gwlarson	3.2
152			qtfreeleaves() /* free ALL sets and leaf nodes */
153			{
154			register int i;
155
156			while ((i = qtfreesets) != EMPTY) {
157			qtfreesets = (int)qtsettab[i];
158			qtsettab[i] = NULL;
159			}
160			for (i = qtnumsets; i--; )
161			if (qtsettab[i] != NULL)
162			free((char *)qtsettab[i]);
163			free((char *)qtsettab);
164			qtsettab = NULL;
165			qtnumsets = 0;
166			}
167
168
169	gwlarson	3.1	check_set(os, cs) /* modify checked set and set to check */
170			register OBJECT os; / os' = os - cs */
171			register OBJECT cs; / cs' = cs + os */
172			{
173	gwlarson	3.2	OBJECT cset[QT_MAXCSET+QT_MAXSET+1];
174	gwlarson	3.1	register int i, j;
175			int k;
176			/* copy os in place, cset <- cs */
177			cset[0] = 0;
178			k = 0;
179			for (i = j = 1; i <= os[0]; i++) {
180			while (j <= cs[0] && cs[j] < os[i])
181			cset[++cset[0]] = cs[j++];
182			if (j > cs[0] \|\| os[i] != cs[j]) { /* object to check */
183			os[++k] = os[i];
184			cset[++cset[0]] = os[i];
185			}
186			}
187			if (!(os[0] = k)) /* new "to check" set size */
188			return; /* special case */
189			while (j <= cs[0]) /* get the rest of cs */
190			cset[++cset[0]] = cs[j++];
191	gwlarson	3.2	if (cset[0] > QT_MAXCSET) /* truncate "checked" set if nec. */
192			cset[0] = QT_MAXCSET;
193	gwlarson	3.1	/* setcopy(cs, cset); / / copy cset back to cs */
194			os = cset;
195			for (i = os[0]; i-- >= 0; )
196			cs++ = os++;
197			}
198	gwlarson	3.4
199
200
201
202
203
204
205
206	gwlarson	3.2