ViewVC Help
View File | Revision Log | Show Annotations | Download File | Root Listing
root/radiance/ray/src/rt/oococt.h
Revision: 2.1
Committed: Tue Feb 24 19:39:26 2015 UTC (9 years, 2 months ago) by greg
Content type: text/plain
Branch: MAIN
Log Message:
Initial check-in of photon map addition by Roland Schregle

File Contents

# User Rev Content
1 greg 2.1 #ifndef OOC_OCT_H
2     #define OOC_OCT_H
3    
4     /*
5     ==================================================================
6     Out-of-core octree data structure
7    
8     Roland Schregle (roland.schregle@{hslu.ch, gmail.com})
9     (c) Fraunhofer Institute for Solar Energy Systems,
10     Lucerne University of Applied Sciences & Arts
11     ==================================================================
12    
13     $Id$
14     */
15    
16    
17     #include "fvect.h"
18    
19    
20     /* Pointer to i-th record */
21     #define OOC_RECPTR(p,i) ((p) +
22    
23     /* Default data block size (8k) */
24     #define OOC_BLKBITS 13
25     #define OOC_BLKSIZE (1 << OOC_BLKBITS)
26    
27     /* Index to data block and index within the block */
28     #define OOC_IDXTOBLK(i) ((i) >> OOC_BLKBITS)
29     #define OOC_IDXINBLK(i) ((i) & (1 << OOC_BLKBITS) - 1)
30    
31     /* Check for block overflow when adding node
32     #define OOC_BLKFULL(n) ((!(n) * sizeof(OOC_Node) % OOC_BLKSIZE) */
33    
34     /* Check for internal node, empty node, interior leaf, or terminal node
35     (8 leaves) */
36     #define OOC_INTNODE(n) ((n).num > 0 && (n).kid > 0)
37     #define OOC_EMPTYNODE(n) (!(n).num)
38     #define OOC_INTLEAF(n) ((n).kid < 0)
39     #define OOC_TERMNODE(n) ((n).num < 0)
40    
41     /* Return record count and kid/leaf index for node */
42     #define OOC_NUMREC(n) abs((n).num)
43     #define OOC_KID(n) abs((n).kid)
44    
45     /* Check for loaded data block */
46     #define OOC_LOADED(b) ((b).dataBlk != NULL)
47    
48     /* (Mutually exclusive) operations on octree to be specified as flags */
49     #define OOC_INSERT 1
50     #define OOC_SEARCH 2
51    
52     /* Counter for records at leaves (2 bytes) */
53     typedef unsigned short OOC_Leaf;
54    
55     /* Node and record index type */
56     typedef int OOC_Idx;
57    
58     /* Octree node */
59     typedef struct {
60     /*
61     For interior nodes (num > 0):
62     num = num records stored in this (sub)tree,
63     kid = index to 1st child node (immediately followed by its
64     siblings) in octree array.
65    
66     For interior leaves (kid < 0):
67     num = num records stored in leaf,
68     abs(kid) = index to single leaf, no siblings.
69    
70     For terminal nodes (num < 0):
71     abs(num) = num records stored in leaves,
72     kid = index to 1st of 8 leaves (immediately followed by its
73     siblings) in leaf array.
74     */
75     OOC_Idx num, kid;
76     } OOC_Node;
77    
78    
79     /* Load map entry; points to start of data block of size OOC_BLKSIZE, or
80     * NULL if not loaded. LRU counter counts accesses for paging from disk */
81     typedef struct {
82     void *dataBlk;
83     unsigned long lruCnt;
84     } OOC_Load;
85    
86    
87     /* Top level octree container */
88     typedef struct {
89     FVECT org; /* Cube origin (min. XYZ) and size */
90     RREAL size;
91     OOC_Node *root; /* Pointer to node array */
92     OOC_Idx maxNodes, /* Num currently allocated nodes */
93     numNodes; /* Num used nodes (< maxNodes) */
94     OOC_Load *loadMap; /* Pointer to load map */
95     OOC_Leaf *leaves; /* Pointer to leaf array */
96     unsigned recSize, /* Size of data record in bytes */
97     leafMax, /* Max num records per leaf */
98     maxDepth; /* Max subdivision depth */
99     } OOC_Octree;
100    
101    
102     /* Initialise octree for records of size recSize, return -1 on failure */
103     int OOC_Init (OOC_Octree *oct, unsigned recSize, unsigned leafMax);
104    
105     /* Return index of kid containing key, update origin and size accordingly */
106     int OOC_Branch (FVECT key, FVECT org, RREAL *size);
107    
108     /* Return data index to leaf containing key, or -1 if not found */
109     OOC_Idx OOC_Find (OOC_Octree *oct, FVECT key);
110    
111     #if 0
112     /* Return pointer to terminal node containing key */
113     OOC_Node *FindNode (OOC_Octree *oct, FVECT key);
114    
115     /* Return index into data block for leaf containing key */
116     OOC_Idx FindLeaf (OOC_Leaf *leaf, FVECT key);
117     #endif
118    
119     #endif