ViewVC Help
View File | Revision Log | Show Annotations | Download File | Root Listing
root/radiance/ray/src/common/octree.c
Revision: 2.3
Committed: Mon Aug 24 15:30:11 1998 UTC (25 years, 8 months ago) by gwlarson
Content type: text/plain
Branch: MAIN
Changes since 2.2: +2 -0 lines
Log Message: 
fixed potential bug in octdone()

File Contents

# User Rev Content
1 greg 1.1 /* Copyright (c) 1986 Regents of the University of California */
2    
3     #ifndef lint
4     static char SCCSid[] = "$SunId$ LBL";
5     #endif
6    
7     /*
8     * octree.c - routines dealing with octrees and cubes.
9     *
10     * 7/28/85
11     */
12    
13     #include "standard.h"
14    
15     #include "octree.h"
16    
17     OCTREE *octblock[MAXOBLK]; /* our octree */
18 greg 1.2 static OCTREE ofreelist = EMPTY; /* freed octree nodes */
19 greg 1.1 static OCTREE treetop = 0; /* next free node */
20    
21    
22     OCTREE
23     octalloc() /* allocate an octree */
24     {
25     register OCTREE freet;
26    
27     if ((freet = ofreelist) != EMPTY) {
28     ofreelist = octkid(freet, 0);
29     return(freet);
30     }
31     freet = treetop;
32     if (octti(freet) == 0) {
33     errno = 0;
34     if (octbi(freet) >= MAXOBLK)
35     return(EMPTY);
36 greg 1.3 if ((octblock[octbi(freet)] = (OCTREE *)bmalloc(
37 greg 1.1 (unsigned)256*8*sizeof(OCTREE))) == NULL)
38     return(EMPTY);
39     }
40     treetop += 8;
41     return(freet);
42     }
43    
44    
45     octfree(ot) /* free an octree */
46     register OCTREE ot;
47     {
48     register int i;
49    
50     if (!istree(ot))
51     return;
52     for (i = 0; i < 8; i++)
53     octfree(octkid(ot, i));
54     octkid(ot, 0) = ofreelist;
55     ofreelist = ot;
56     }
57    
58    
59 greg 2.2 octdone() /* free EVERYTHING */
60     {
61     register int i;
62    
63     for (i = 0; i < MAXOBLK; i++) {
64 gwlarson 2.3 if (octblock[i] == NULL)
65     break;
66 greg 2.2 bfree((char *)octblock[i], (unsigned)256*8*sizeof(OCTREE));
67     octblock[i] = NULL;
68     }
69     ofreelist = EMPTY;
70     treetop = 0;
71     }
72    
73    
74 greg 1.1 OCTREE
75     combine(ot) /* recursively combine nodes */
76     register OCTREE ot;
77     {
78     register int i;
79     register OCTREE ores;
80    
81     if (!istree(ot)) /* not a tree */
82     return(ot);
83     ores = octkid(ot, 0) = combine(octkid(ot, 0));
84     for (i = 1; i < 8; i++)
85     if ((octkid(ot, i) = combine(octkid(ot, i))) != ores)
86     ores = ot;
87 greg 1.2 if (!istree(ores)) { /* all were identical leaves */
88     octkid(ot, 0) = ofreelist;
89     ofreelist = ot;
90     }
91 greg 1.1 return(ores);
92     }
93    
94    
95     culocate(cu, pt) /* locate point within cube */
96     register CUBE *cu;
97     register FVECT pt;
98     {
99     register 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     cucopy(cu1, cu2) /* copy cu2 into cu1 */
116     register CUBE *cu1, *cu2;
117     {
118     cu1->cutree = cu2->cutree;
119     cu1->cusize = cu2->cusize;
120     VCOPY(cu1->cuorg, cu2->cuorg);
121     }
122    
123    
124     incube(cu, pt) /* determine if a point is inside a cube */
125     register CUBE *cu;
126     register FVECT pt;
127     {
128     if (cu->cuorg[0] > pt[0] || pt[0] >= cu->cuorg[0] + cu->cusize)
129     return(0);
130     if (cu->cuorg[1] > pt[1] || pt[1] >= cu->cuorg[1] + cu->cusize)
131     return(0);
132     if (cu->cuorg[2] > pt[2] || pt[2] >= cu->cuorg[2] + cu->cusize)
133     return(0);
134     return(1);
135     }