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 QTNODESIZ(ne)   ((ne) + QTELEMBLK - ((ne) % QTELEMBLK))

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;
        int     nalc;

        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;
        }
        nalc = QTNODESIZ(*oset);
        if ((qtsettab[osi] = (OBJECT *)malloc(nalc*sizeof(OBJECT))) == 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, no quest. */
QUADTREE  qt;
OBJECT  id;
{
        register QUADTREE  lf;
        int  oalc, nalc;

#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);
        }                                       /* else delete element */
        oalc = QTNODESIZ(qtsettab[lf][0]);
        nalc = QTNODESIZ(qtsettab[lf][0] - 1);
        deletelem(qtsettab[lf], id);
        if (nalc != oalc)
                qtsettab[lf] = (OBJECT *)realloc((char *)qtsettab[lf],
                                nalc*sizeof(OBJECT));
        return(qt);
}


QUADTREE
qtaddelem(qt, id)               /* add element to leaf node, no quest. */
QUADTREE  qt;
OBJECT  id;
{
        OBJECT  newset[2];
        register QUADTREE  lf;
        int  oalc, nalc;

#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
        oalc = QTNODESIZ(qtsettab[lf][0]);
        nalc = QTNODESIZ(qtsettab[lf][0] + 1);
        if (nalc != oalc) {
                qtsettab[lf] = (OBJECT *)realloc((char *)qtsettab[lf],
                                nalc*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.2
Committed:	Fri Sep 11 11:52:27 1998 UTC (25 years, 7 months ago) by gwlarson
Content type:	text/plain
Branch:	MAIN
Changes since 3.1:	+55 -37 lines
Log Message:	fixed triangle insertion using edge tracing
#	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
19			#define QTNODESIZ(ne) ((ne) + QTELEMBLK - ((ne) % QTELEMBLK))
20
21	gwlarson	3.2	OBJECT *qtsettab= NULL; / quadtree leaf node table */
22			QUADTREE qtnumsets; /* number of used set indices */
23	gwlarson	3.1	static int qtfreesets = EMPTY; /* free set index list */
24
25
26			QUADTREE
27			qtnewleaf(oset) /* return new leaf node for object set */
28			OBJECT *oset;
29			{
30			register QUADTREE osi;
31			int nalc;
32
33			if (*oset <= 0)
34			return(EMPTY); /* should be error? */
35			if (qtfreesets != EMPTY) {
36			osi = qtfreesets;
37			qtfreesets = (int)qtsettab[osi];
38			} else if ((osi = qtnumsets++) % QTSETIBLK == 0) {
39			qtsettab = (OBJECT *)realloc((char )qtsettab,
40			(unsigned)(osi+QTSETIBLK)sizeof(OBJECT ));
41			if (qtsettab == NULL)
42			goto memerr;
43			}
44			nalc = QTNODESIZ(*oset);
45			if ((qtsettab[osi] = (OBJECT )malloc(nalcsizeof(OBJECT))) == NULL)
46			goto memerr;
47			setcopy(qtsettab[osi], oset);
48			return(QT_INDEX(osi));
49			memerr:
50			error(SYSTEM, "out of memory in qtnewleaf");
51			}
52
53
54			QUADTREE
55			qtdelelem(qt, id) /* delete element from leaf node, no quest. */
56			QUADTREE qt;
57			OBJECT id;
58			{
59			register QUADTREE lf;
60			int oalc, nalc;
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			} /* else delete element */
78			oalc = QTNODESIZ(qtsettab[lf][0]);
79			nalc = QTNODESIZ(qtsettab[lf][0] - 1);
80			deletelem(qtsettab[lf], id);
81			if (nalc != oalc)
82			qtsettab[lf] = (OBJECT )realloc((char )qtsettab[lf],
83			nalc*sizeof(OBJECT));
84			return(qt);
85			}
86
87
88			QUADTREE
89			qtaddelem(qt, id) /* add element to leaf node, no quest. */
90			QUADTREE qt;
91			OBJECT id;
92			{
93			OBJECT newset[2];
94			register QUADTREE lf;
95			int oalc, nalc;
96
97	gwlarson	3.2	#ifdef DEBUG
98			if(id < 0)
99			eputs("qtaddelem():Invalid triangle id\n");
100			#endif
101	gwlarson	3.1	if (QT_IS_EMPTY(qt)) { /* create new leaf */
102			newset[0] = 1; newset[1] = id;
103			return(qtnewleaf(newset));
104			} /* else add element */
105	gwlarson	3.2	#ifdef DEBUG
106			if (!QT_IS_LEAF(qt) \|\| (lf = QT_SET_INDEX(qt)) >= qtnumsets)
107			error(CONSISTENCY, "bad node in qtaddelem");
108			if (inset(qtsettab[lf], id))
109			error(CONSISTENCY, "id already in leaf in qtaddelem");
110			#else
111	gwlarson	3.1	lf = QT_SET_INDEX(qt);
112	gwlarson	3.2	#endif
113	gwlarson	3.1	oalc = QTNODESIZ(qtsettab[lf][0]);
114			nalc = QTNODESIZ(qtsettab[lf][0] + 1);
115			if (nalc != oalc) {
116			qtsettab[lf] = (OBJECT )realloc((char )qtsettab[lf],
117			nalc*sizeof(OBJECT));
118			if (qtsettab[lf] == NULL)
119			error(SYSTEM, "out of memory in qtaddelem");
120			}
121			insertelem(qtsettab[lf], id);
122			return(qt);
123			}
124
125
126	gwlarson	3.2	#ifdef DEBUG
127			OBJECT *
128			qtqueryset(qt) /* return object set for leaf node */
129	gwlarson	3.1	QUADTREE qt;
130			{
131	gwlarson	3.2	register QUADTREE lf;
132	gwlarson	3.1
133	gwlarson	3.2	if (!QT_IS_LEAF(qt) \|\| (lf = QT_SET_INDEX(qt)) >= qtnumsets)
134			error(CONSISTENCY, "bad node in qtqueryset");
135			return(qtsettab[lf]);
136	gwlarson	3.1	}
137	gwlarson	3.2	#endif
138	gwlarson	3.1
139
140			qtfreeleaf(qt) /* free set and leaf node */
141			QUADTREE qt;
142			{
143			register QUADTREE osi;
144
145			if (!QT_IS_LEAF(qt))
146			return;
147			osi = QT_SET_INDEX(qt);
148			if (osi >= qtnumsets)
149	gwlarson	3.2	return;
150	gwlarson	3.1	free((char *)qtsettab[osi]);
151			qtsettab[osi] = (OBJECT *)qtfreesets;
152			qtfreesets = osi;
153			}
154
155
156	gwlarson	3.2
157			qtfreeleaves() /* free ALL sets and leaf nodes */
158			{
159			register int i;
160
161			while ((i = qtfreesets) != EMPTY) {
162			qtfreesets = (int)qtsettab[i];
163			qtsettab[i] = NULL;
164			}
165			for (i = qtnumsets; i--; )
166			if (qtsettab[i] != NULL)
167			free((char *)qtsettab[i]);
168			free((char *)qtsettab);
169			qtsettab = NULL;
170			qtnumsets = 0;
171			}
172
173
174	gwlarson	3.1	check_set(os, cs) /* modify checked set and set to check */
175			register OBJECT os; / os' = os - cs */
176			register OBJECT cs; / cs' = cs + os */
177			{
178	gwlarson	3.2	OBJECT cset[QT_MAXCSET+QT_MAXSET+1];
179	gwlarson	3.1	register int i, j;
180			int k;
181			/* copy os in place, cset <- cs */
182			cset[0] = 0;
183			k = 0;
184			for (i = j = 1; i <= os[0]; i++) {
185			while (j <= cs[0] && cs[j] < os[i])
186			cset[++cset[0]] = cs[j++];
187			if (j > cs[0] \|\| os[i] != cs[j]) { /* object to check */
188			os[++k] = os[i];
189			cset[++cset[0]] = os[i];
190			}
191			}
192			if (!(os[0] = k)) /* new "to check" set size */
193			return; /* special case */
194			while (j <= cs[0]) /* get the rest of cs */
195			cset[++cset[0]] = cs[j++];
196	gwlarson	3.2	if (cset[0] > QT_MAXCSET) /* truncate "checked" set if nec. */
197			cset[0] = QT_MAXCSET;
198	gwlarson	3.1	/* setcopy(cs, cset); / / copy cset back to cs */
199			os = cset;
200			for (i = os[0]; i-- >= 0; )
201			cs++ = os++;
202			}
203	gwlarson	3.2