ViewVC Help
View File | Revision Log | Show Annotations | Download File | Root Listing
root/radiance/ray/src/common/octree.c
Revision: 2.8
Committed: Sun Nov 1 04:41:55 2009 UTC (14 years, 4 months ago) by greg
Content type: text/plain
Branch: MAIN
CVS Tags: rad5R4, rad5R2, rad4R2P2, rad5R0, rad5R1, rad4R2, rad4R1, rad4R0, rad4R2P1, rad5R3, HEAD
Changes since 2.7: +13 -23 lines
Log Message:
Deleted unused cucopy() routine

File Contents

# Content
1 #ifndef lint
2 static const char RCSid[] = "$Id: octree.c,v 2.7 2007/05/23 21:39:38 greg Exp $";
3 #endif
4 /*
5 * octree.c - routines dealing with octrees and cubes.
6 */
7
8 #include "copyright.h"
9
10 #include "standard.h"
11
12 #include "octree.h"
13
14 OCTREE *octblock[MAXOBLK]; /* our octree */
15 static OCTREE ofreelist = EMPTY; /* freed octree nodes */
16 static OCTREE treetop = 0; /* next free node */
17
18
19 OCTREE
20 octalloc() /* allocate an octree */
21 {
22 OCTREE freet;
23
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 if ((octblock[octbi(freet)] = (OCTREE *)malloc(
34 (unsigned)OCTBLKSIZ*8*sizeof(OCTREE))) == NULL)
35 return(EMPTY);
36 }
37 treetop++;
38 return(freet);
39 }
40
41
42 void
43 octfree(ot) /* free an octree */
44 OCTREE ot;
45 {
46 int i;
47
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 void
58 octdone() /* free EVERYTHING */
59 {
60 int i;
61
62 for (i = 0; i < MAXOBLK; i++) {
63 if (octblock[i] == NULL)
64 break;
65 free((void *)octblock[i]);
66 octblock[i] = NULL;
67 }
68 ofreelist = EMPTY;
69 treetop = 0;
70 }
71
72
73 OCTREE
74 combine(ot) /* recursively combine nodes */
75 OCTREE ot;
76 {
77 int i;
78 OCTREE ores;
79
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 if (!istree(ores)) { /* all were identical leaves */
87 octkid(ot, 0) = ofreelist;
88 ofreelist = ot;
89 }
90 return(ores);
91 }
92
93
94 void
95 culocate(cu, pt) /* locate point within cube */
96 CUBE *cu;
97 FVECT pt;
98 {
99 int i;
100 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 int
116 incube(cu, pt) /* determine if a point is inside a cube */
117 CUBE *cu;
118 FVECT pt;
119 {
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 }