src/common/octree.c

#ifndef lint
static const char       RCSid[] = "$Id: octree.c,v 2.7 2007/05/23 21:39:38 greg Exp $";
#endif
/*
 *  octree.c - routines dealing with octrees and cubes.
 */

#include "copyright.h"

#include  "standard.h"

#include  "octree.h"

OCTREE  *octblock[MAXOBLK];             /* our octree */
static OCTREE  ofreelist = EMPTY;       /* freed octree nodes */
static OCTREE  treetop = 0;             /* next free node */


OCTREE
octalloc()                      /* allocate an octree */
{
        OCTREE  freet;

        if ((freet = ofreelist) != EMPTY) {
                ofreelist = octkid(freet, 0);
                return(freet);
        }
        freet = treetop;
        if (octti(freet) == 0) {
                errno = 0;
                if (octbi(freet) >= MAXOBLK)
                        return(EMPTY);
                if ((octblock[octbi(freet)] = (OCTREE *)malloc(
                                (unsigned)OCTBLKSIZ*8*sizeof(OCTREE))) == NULL)
                        return(EMPTY);
        }
        treetop++;
        return(freet);
}


void
octfree(ot)                     /* free an octree */
OCTREE  ot;
{
        int  i;

        if (!istree(ot))
                return;
        for (i = 0; i < 8; i++)
                octfree(octkid(ot, i));
        octkid(ot, 0) = ofreelist;
        ofreelist = ot;
}


void
octdone()                       /* free EVERYTHING */
{
        int     i;

        for (i = 0; i < MAXOBLK; i++) {
                if (octblock[i] == NULL)
                        break;
                free((void *)octblock[i]);
                octblock[i] = NULL;
        }
        ofreelist = EMPTY;
        treetop = 0;
}


OCTREE
combine(ot)                     /* recursively combine nodes */
OCTREE  ot;
{
        int  i;
        OCTREE  ores;

        if (!istree(ot))        /* not a tree */
                return(ot);
        ores = octkid(ot, 0) = combine(octkid(ot, 0));
        for (i = 1; i < 8; i++)
                if ((octkid(ot, i) = combine(octkid(ot, i))) != ores)
                        ores = ot;
        if (!istree(ores)) {    /* all were identical leaves */
                octkid(ot, 0) = ofreelist;
                ofreelist = ot;
        }
        return(ores);
}


void
culocate(cu, pt)                /* locate point within cube */
CUBE  *cu;
FVECT  pt;
{
        int  i;
        int  branch;

        while (istree(cu->cutree)) {
                cu->cusize *= 0.5;
                branch = 0;
                for (i = 0; i < 3; i++)
                        if (cu->cuorg[i] + cu->cusize <= pt[i]) {
                                cu->cuorg[i] += cu->cusize;
                                branch |= 1 << i;
                        }
                cu->cutree = octkid(cu->cutree, branch);
        }
}


int
incube(cu, pt)                  /* determine if a point is inside a cube */
CUBE  *cu;
FVECT  pt;
{
        if (cu->cuorg[0] > pt[0] || pt[0] >= cu->cuorg[0] + cu->cusize)
                return(0);
        if (cu->cuorg[1] > pt[1] || pt[1] >= cu->cuorg[1] + cu->cusize)
                return(0);
        if (cu->cuorg[2] > pt[2] || pt[2] >= cu->cuorg[2] + cu->cusize)
                return(0);
        return(1);
}
Revision:	2.8
Committed:	Sun Nov 1 04:41:55 2009 UTC (16 years ago) by greg
Content type:	text/plain
Branch:	MAIN
CVS Tags:	rad5R4, rad5R2, rad5R3, rad5R0, rad5R1, rad4R2, rad6R0, rad4R1, rad4R0, rad4R2P1, rad4R2P2, HEAD
Changes since 2.7:	+13 -23 lines
Log Message:	Deleted unused cucopy() routine
#	User	Rev	Content
1	greg	1.1	#ifndef lint
2	greg	2.8	static const char RCSid[] = "$Id: octree.c,v 2.7 2007/05/23 21:39:38 greg Exp $";
3	greg	1.1	#endif
4			/*
5			* octree.c - routines dealing with octrees and cubes.
6	greg	2.5	*/
7
8	greg	2.6	#include "copyright.h"
9	greg	1.1
10			#include "standard.h"
11
12			#include "octree.h"
13
14			OCTREE octblock[MAXOBLK]; / our octree */
15	greg	1.2	static OCTREE ofreelist = EMPTY; /* freed octree nodes */
16	greg	1.1	static OCTREE treetop = 0; /* next free node */
17
18
19			OCTREE
20			octalloc() /* allocate an octree */
21			{
22	greg	2.8	OCTREE freet;
23	greg	1.1
24			if ((freet = ofreelist) != EMPTY) {
25			ofreelist = octkid(freet, 0);
26			return(freet);
27			}
28			freet = treetop;
29			if (octti(freet) == 0) {
30			errno = 0;
31			if (octbi(freet) >= MAXOBLK)
32			return(EMPTY);
33	greg	2.5	if ((octblock[octbi(freet)] = (OCTREE *)malloc(
34	gwlarson	2.4	(unsigned)OCTBLKSIZ8sizeof(OCTREE))) == NULL)
35	greg	1.1	return(EMPTY);
36			}
37	greg	2.7	treetop++;
38	greg	1.1	return(freet);
39			}
40
41
42	greg	2.5	void
43	greg	1.1	octfree(ot) /* free an octree */
44	greg	2.8	OCTREE ot;
45	greg	1.1	{
46	greg	2.8	int i;
47	greg	1.1
48			if (!istree(ot))
49			return;
50			for (i = 0; i < 8; i++)
51			octfree(octkid(ot, i));
52			octkid(ot, 0) = ofreelist;
53			ofreelist = ot;
54			}
55
56
57	greg	2.5	void
58	greg	2.2	octdone() /* free EVERYTHING */
59			{
60	greg	2.8	int i;
61	greg	2.2
62			for (i = 0; i < MAXOBLK; i++) {
63	gwlarson	2.3	if (octblock[i] == NULL)
64			break;
65	greg	2.5	free((void *)octblock[i]);
66	greg	2.2	octblock[i] = NULL;
67			}
68			ofreelist = EMPTY;
69			treetop = 0;
70			}
71
72
73	greg	1.1	OCTREE
74			combine(ot) /* recursively combine nodes */
75	greg	2.8	OCTREE ot;
76	greg	1.1	{
77	greg	2.8	int i;
78			OCTREE ores;
79	greg	1.1
80			if (!istree(ot)) /* not a tree */
81			return(ot);
82			ores = octkid(ot, 0) = combine(octkid(ot, 0));
83			for (i = 1; i < 8; i++)
84			if ((octkid(ot, i) = combine(octkid(ot, i))) != ores)
85			ores = ot;
86	greg	1.2	if (!istree(ores)) { /* all were identical leaves */
87			octkid(ot, 0) = ofreelist;
88			ofreelist = ot;
89			}
90	greg	1.1	return(ores);
91			}
92
93
94	greg	2.5	void
95	greg	1.1	culocate(cu, pt) /* locate point within cube */
96	greg	2.8	CUBE *cu;
97			FVECT pt;
98	greg	1.1	{
99	greg	2.8	int i;
100	greg	1.1	int branch;
101
102			while (istree(cu->cutree)) {
103			cu->cusize *= 0.5;
104			branch = 0;
105			for (i = 0; i < 3; i++)
106			if (cu->cuorg[i] + cu->cusize <= pt[i]) {
107			cu->cuorg[i] += cu->cusize;
108			branch \|= 1 << i;
109			}
110			cu->cutree = octkid(cu->cutree, branch);
111			}
112			}
113
114
115	greg	2.5	int
116	greg	1.1	incube(cu, pt) /* determine if a point is inside a cube */
117	greg	2.8	CUBE *cu;
118			FVECT pt;
119	greg	1.1	{
120			if (cu->cuorg[0] > pt[0] \|\| pt[0] >= cu->cuorg[0] + cu->cusize)
121			return(0);
122			if (cu->cuorg[1] > pt[1] \|\| pt[1] >= cu->cuorg[1] + cu->cusize)
123			return(0);
124			if (cu->cuorg[2] > pt[2] \|\| pt[2] >= cu->cuorg[2] + cu->cusize)
125			return(0);
126			return(1);
127			}