src/rt/oocbuild.c

/* 
   =======================================================================
   Routines for building out-of-core octree data structure
   
   Adapted from:  Kontkanen J., Tabellion E. and Overbeck R.S.,
                  "Coherent Out-of-Core Point-Based Global Illumination",
                  EGSR 2011.   
   
   Roland Schregle (roland.schregle@{hslu.ch, gmail.com})
   (c) Fraunhofer Institute for Solar Energy Systems,
       Lucerne University of Applied Sciences & Arts   
   =======================================================================
   
   $Id$
*/


#include "oococt.h"
#include "oocsort.h"


/* Test for empty/full input queue, return pointer to head/tail */
#define QueueFull(q)    ((q) -> len == (q) -> cap)
#define QueueEmpty(q)   (!(q) -> len)
#define QueueHead(q)    ((q) -> data + (q) -> head * (q) -> recSize)
#define QueueTail(q)    ((q) -> data + \
                         (q) -> head + (q) -> len - 1) * (q) -> recSize)


/* Input queue from heap */
type struct {
   void *data = NULL;
   /* Queue head, length (from head), capacity and record size */
   unsigned head, len, cap, recSize;
} OOC_BuildQueue;


static OOC_BuildQueue *QueueInit (OOC_BuildQueue *q, unsigned recSize,
                                  unsigned capacity)
/* Initialise queue of #capacity records of size recSize each; returns queue
 * pointer or NULL if failed. */
{
   if (!(q && (q -> data = calloc(capacity, recSize))))
      return NULL;
   
   q -> cap = capacity;
   q -> recSize = recSize;
   q -> head = q -> len = 0;
   
   return q;
}
   
   
static int QueuePush (OOC_BuildQueue *q, const void *rec)
/* Append record to queue tail; returns new queue length or -1 on failure */
{
   int tail;
   
   if (!q || !rec)
      return -1;
      
   if (q -> len >= q -> cap)
      /* Queue full */
      return -1;
   
   tail = (q -> head + q-> len++) % q -> cap;
   memcpy(q -> data + tail * q -> recSize, rec, q -> recSize);
   
   return q -> len;
}


static int QueuePop (OOC_BuildQueue *q, void *rec)
/* Remove record from queue head; returns new queue length or -1 on failure */
{
   if (!q || !rec)
      return -1;
      
   if (!q -> len)
      /* Queue empty */
      return -1;
      
   memcpy(rev, q -> data + q -> head * q -> recSize, q -> recSize);
   q -> head = (q -> head + 1) % q -> cap;
   
   return --q -> len;
}   


static OOC_Idx *OOC_BuildRecurse (OOC_Octree *oct, OOC_Node *node, 
                                  FVECT org, RREAL size, unsigned depth,
                                  OOC_Queue *queue, FILE *heapFile, 
                                  FILE *nodeFile, FILE *leafFile)
/* Recursive part of OOC_Build(); insert records from input queue into
 * octree node and subdivide if necessary. Returns number of records in
 * subtree. */
{
   if (QueueEmpty(queue) || !InNode(QueueHead(queue)))
      /* Input exhausted or queue head outside node */
      return 0;
      
   if (InNode(QueueTail(queue)) && QueueFull(queue) && 
       depth < oct -> maxDepth) {
       
   }
   else {
   
   }      
}                                   
   
   
OOC_Octree *OOC_Build (OOC_Octree *oct, unsigned recSize, unsigned leafMax,
                       unsigned maxDepth, const char *heapFileName, 
                       const char *nodeFileName, const char *leafFileName)
/* Build out-of-core octree from unsorted records of size recSize in
 * heapFileName, such that leaves contain <= leafMax records, except those
 * at maxDepth. Nodes and leaves are output separately to nodeFileName and leafFileName,
 * respectively. Returns octree pointer on success, else NULL. */
{
   OOC_BuildQueue queue;
   void *rec = malloc(recSize);
   FILE *heapFile = fopen(heapFileName, "rb"), 
        *nodeFile = fopen(nodeFileName, "wb"), 
        *leafFile = fopen(leafFileName, "wb");
   
   if (OOC_Init(oct, recSize, leafMax, maxDepth) < 0) {
      perror("OOC_Build: failed octree init");
      return NULL;
   }
      
   if (!heapFile) {
      perror("OOC_Build: failed opening heap file");
      return NULL;
   }
   
   if (!nodeFile || !leafFile) {
      perror("OOC_Build: failed opening node/leaf output file");
      return NULL;
   }
   
   /* Init and fill queue from heap file */
   if (!rec || !QueueInit(&queue, recSize, leafMax + 1)) {
      perror("OOC_Build: failed input queue init");
      return NULL;
   }
   
   do {
      if (feof(heapFile) || !fread(rec, recSize, 1, heapFile)) {
         perror("OOC_Build: failed reading from heap file");
         
      QueuePush(&queue, rec);
   } while (!QueueFull(&queue));
   
   if (!OOC_BuildRecurse(oct, oct -> root, queue, 
                         heapFile, nodeFile, leafFile))
      return NULL;
      
   fclose(heapFile);
   fclose(nodeFile);
   fclose(leafFile);
   
   return oct;
}
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
#	User	Rev	Content
1	greg	2.1	/*
2			=======================================================================
3			Routines for building out-of-core octree data structure
4
5			Adapted from: Kontkanen J., Tabellion E. and Overbeck R.S.,
6			"Coherent Out-of-Core Point-Based Global Illumination",
7			EGSR 2011.
8
9			Roland Schregle (roland.schregle@{hslu.ch, gmail.com})
10			(c) Fraunhofer Institute for Solar Energy Systems,
11			Lucerne University of Applied Sciences & Arts
12			=======================================================================
13
14			$Id$
15			*/
16
17
18			#include "oococt.h"
19			#include "oocsort.h"
20
21
22			/* Test for empty/full input queue, return pointer to head/tail */
23			#define QueueFull(q) ((q) -> len == (q) -> cap)
24			#define QueueEmpty(q) (!(q) -> len)
25			#define QueueHead(q) ((q) -> data + (q) -> head * (q) -> recSize)
26			#define QueueTail(q) ((q) -> data + \
27			(q) -> head + (q) -> len - 1) * (q) -> recSize)
28
29
30			/* Input queue from heap */
31			type struct {
32			void *data = NULL;
33			/* Queue head, length (from head), capacity and record size */
34			unsigned head, len, cap, recSize;
35			} OOC_BuildQueue;
36
37
38			static OOC_BuildQueue QueueInit (OOC_BuildQueue q, unsigned recSize,
39			unsigned capacity)
40			/* Initialise queue of #capacity records of size recSize each; returns queue
41			* pointer or NULL if failed. */
42			{
43			if (!(q && (q -> data = calloc(capacity, recSize))))
44			return NULL;
45
46			q -> cap = capacity;
47			q -> recSize = recSize;
48			q -> head = q -> len = 0;
49
50			return q;
51			}
52
53
54			static int QueuePush (OOC_BuildQueue q, const void rec)
55			/* Append record to queue tail; returns new queue length or -1 on failure */
56			{
57			int tail;
58
59			if (!q \|\| !rec)
60			return -1;
61
62			if (q -> len >= q -> cap)
63			/* Queue full */
64			return -1;
65
66			tail = (q -> head + q-> len++) % q -> cap;
67			memcpy(q -> data + tail * q -> recSize, rec, q -> recSize);
68
69			return q -> len;
70			}
71
72
73			static int QueuePop (OOC_BuildQueue q, void rec)
74			/* Remove record from queue head; returns new queue length or -1 on failure */
75			{
76			if (!q \|\| !rec)
77			return -1;
78
79			if (!q -> len)
80			/* Queue empty */
81			return -1;
82
83			memcpy(rev, q -> data + q -> head * q -> recSize, q -> recSize);
84			q -> head = (q -> head + 1) % q -> cap;
85
86			return --q -> len;
87			}
88
89
90			static OOC_Idx OOC_BuildRecurse (OOC_Octree oct, OOC_Node *node,
91			FVECT org, RREAL size, unsigned depth,
92			OOC_Queue queue, FILE heapFile,
93			FILE nodeFile, FILE leafFile)
94			/* Recursive part of OOC_Build(); insert records from input queue into
95			* octree node and subdivide if necessary. Returns number of records in
96			* subtree. */
97			{
98			if (QueueEmpty(queue) \|\| !InNode(QueueHead(queue)))
99			/* Input exhausted or queue head outside node */
100			return 0;
101
102			if (InNode(QueueTail(queue)) && QueueFull(queue) &&
103			depth < oct -> maxDepth) {
104
105			}
106			else {
107
108			}
109			}
110
111
112			OOC_Octree OOC_Build (OOC_Octree oct, unsigned recSize, unsigned leafMax,
113			unsigned maxDepth, const char *heapFileName,
114			const char nodeFileName, const char leafFileName)
115			/* Build out-of-core octree from unsorted records of size recSize in
116			* heapFileName, such that leaves contain <= leafMax records, except those
117			* at maxDepth. Nodes and leaves are output separately to nodeFileName and leafFileName,
118			* respectively. Returns octree pointer on success, else NULL. */
119			{
120			OOC_BuildQueue queue;
121			void *rec = malloc(recSize);
122			FILE *heapFile = fopen(heapFileName, "rb"),
123			*nodeFile = fopen(nodeFileName, "wb"),
124			*leafFile = fopen(leafFileName, "wb");
125
126			if (OOC_Init(oct, recSize, leafMax, maxDepth) < 0) {
127			perror("OOC_Build: failed octree init");
128			return NULL;
129			}
130
131			if (!heapFile) {
132			perror("OOC_Build: failed opening heap file");
133			return NULL;
134			}
135
136			if (!nodeFile \|\| !leafFile) {
137			perror("OOC_Build: failed opening node/leaf output file");
138			return NULL;
139			}
140
141			/* Init and fill queue from heap file */
142			if (!rec \|\| !QueueInit(&queue, recSize, leafMax + 1)) {
143			perror("OOC_Build: failed input queue init");
144			return NULL;
145			}
146
147			do {
148			if (feof(heapFile) \|\| !fread(rec, recSize, 1, heapFile)) {
149			perror("OOC_Build: failed reading from heap file");
150
151			QueuePush(&queue, rec);
152			} while (!QueueFull(&queue));
153
154			if (!OOC_BuildRecurse(oct, oct -> root, queue,
155			heapFile, nodeFile, leafFile))
156			return NULL;
157
158			fclose(heapFile);
159			fclose(nodeFile);
160			fclose(leafFile);
161
162			return oct;
163			}