Page Menu
Home
c4science
Search
Configure Global Search
Log In
Files
F85140745
oocbuild.c
No One
Temporary
Actions
Download File
Edit File
Delete File
View Transforms
Subscribe
Mute Notifications
Award Token
Subscribers
None
File Metadata
Details
File Info
Storage
Attached
Created
Fri, Sep 27, 01:35
Size
12 KB
Mime Type
text/x-c
Expires
Sun, Sep 29, 01:35 (2 d)
Engine
blob
Format
Raw Data
Handle
21129486
Attached To
R10977 RADIANCE Photon Map
oocbuild.c
View Options
#ifndef lint
static
const
char
RCSid
[]
=
"$Id: oocbuild.c,v 2.4 2017/08/14 21:12:10 rschregle Exp $"
;
#endif
/*
=======================================================================
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) Lucerne University of Applied Sciences and Arts,
supported by the Swiss National Science Foundation (SNSF, #147053)
=======================================================================
$Id: oocbuild.c,v 2.4 2017/08/14 21:12:10 rschregle Exp $
*/
#if !defined(_WIN32) && !defined(_WIN64) || defined(PMAP_OOC)
/* No Windoze support for now */
#include "oococt.h"
#include "oocsort.h"
#include <stdlib.h>
#include <string.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)->cap * (q)->recSize)
/* Input queue for bottom-up octree construction */
typedef
struct
{
void
*
data
;
unsigned
head
,
len
,
cap
,
recSize
;
/* Queue head, length (from head),
capacity and record size */
FILE
*
in
;
/* Input file for data records */
}
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; return new queue length or -1 on failure */
{
if
(
!
q
||
!
rec
||
QueueFull
(
q
))
return
-
1
;
++
q
->
len
;
memcpy
(
QueueTail
(
q
),
rec
,
q
->
recSize
);
return
q
->
len
;
}
static
int
QueuePop
(
OOC_BuildQueue
*
q
,
void
*
rec
)
/* Remove record from queue head and return in rec if not NULL; return new
* queue length or -1 on failure */
{
if
(
!
q
||
QueueEmpty
(
q
))
return
-
1
;
/* Return head if rec != NULL */
if
(
rec
)
memcpy
(
rec
,
QueueHead
(
q
),
q
->
recSize
);
q
->
head
=
(
q
->
head
+
1
)
%
q
->
cap
;
return
--
q
->
len
;
}
static
int
QueueFill
(
OOC_BuildQueue
*
q
)
/* Read records from q -> in until the queue is full; return queue
* length or -1 on failure */
{
static
void
*
rec
=
NULL
;
if
(
!
rec
&&
!
(
rec
=
malloc
(
q
->
recSize
)))
return
-
1
;
while
(
!
QueueFull
(
q
)
&&
!
feof
(
q
->
in
)
&&
fread
(
rec
,
q
->
recSize
,
1
,
q
->
in
))
QueuePush
(
q
,
rec
);
return
q
->
len
;
}
static
OOC_DataIdx
OOC_BuildRecurse
(
OOC_Octree
*
oct
,
OOC_Node
*
node
,
FVECT
org
,
RREAL
size
,
unsigned
depth
,
OOC_BuildQueue
*
queue
)
/* Recursive part of OOC_Build(); insert records from input queue into
* octree node and subdivide into kids if necessary. Returns number of
* records in subtree or OOC_DATAIDX_ERR if failed. */
{
int
k
;
const
RREAL
kidSize
=
size
*
0.5
;
if
(
!
oct
||
!
node
)
return
OOC_DATAIDX_ERR
;
if
(
QueueEmpty
(
queue
)
||
!
OOC_InBBox
(
oct
,
org
,
size
,
oct
->
key
(
QueueHead
(
queue
))))
/* Input exhausted or queue head outside node */
return
0
;
if
(
QueueFull
(
queue
)
&&
depth
<
oct
->
maxDepth
&&
OOC_InBBox
(
oct
,
org
,
size
,
oct
->
key
(
QueueTail
(
queue
))))
{
/*************************** SUBDIVIDE NODE *************************
* At least leafMax + 1 records (since the queue is full) lie inside
* the current node's bounding box, and maxDepth has not been reached
* ==> subdivide this node.
* (Note it suffices to only test the queue tail against the bounding
* box, as the records are in Z-order)
********************************************************************/
OOC_Node
kid
[
8
];
OOC_DataIdx
dataCnt
;
FVECT
kidOrg
;
#ifdef DEBUG_OOC_BUILD
FVECT
key
;
unsigned
k2
=
0
;
#endif
/* We recurse on the nonempty kids first, then finalise their nodes so
* they are ordered consecutively, since the parent only indexes the 1st kid */
for
(
k
=
0
;
k
<
8
;
k
++
)
{
/* Clear kid node and get its octant origin */
OOC_CLEARNODE
(
kid
+
k
);
VCOPY
(
kidOrg
,
org
);
OOC_OCTORIGIN
(
kidOrg
,
k
,
kidSize
);
/* Recurse on kid and check for early bailout */
if
(
OOC_BuildRecurse
(
oct
,
kid
+
k
,
kidOrg
,
kidSize
,
depth
+
1
,
queue
)
==
OOC_DATAIDX_ERR
)
return
OOC_DATAIDX_ERR
;
#ifdef DEBUG_OOC_BUILD
if
(
!
QueueEmpty
(
queue
))
{
VCOPY
(
key
,
oct
->
key
(
QueueHead
(
queue
)));
k2
=
OOC_Branch
(
oct
,
org
,
kidSize
,
key
,
NULL
);
if
(
OOC_InBBox
(
oct
,
org
,
size
,
key
)
&&
k2
<
k
)
{
fprintf
(
stderr
,
"OOC_BuildRecurse, node subdiv: unsorted key [%f, %f, %f] "
"with octant %d (last %d with bbox [%f-%f, %f-%f, %f-%f])
\n
"
,
key
[
0
],
key
[
1
],
key
[
2
],
k2
,
k
,
kidOrg
[
0
],
kidOrg
[
0
]
+
kidSize
,
kidOrg
[
1
],
kidOrg
[
1
]
+
kidSize
,
kidOrg
[
2
],
kidOrg
[
2
]
+
kidSize
);
}
}
#endif
}
/* Now finalise consecutive kid nodes, skipping empty ones */
for
(
k
=
0
;
k
<
8
;
k
++
)
if
((
dataCnt
=
OOC_DATACNT
(
kid
+
k
)))
{
/* Nonzero kid ==> allocate and set node */
if
(
!
NewNode
(
oct
))
{
fputs
(
"OOC_BuildRecurse: failed to allocate new node
\n
"
,
stderr
);
return
OOC_DATAIDX_ERR
;
}
OOC_SETROOT
(
oct
,
kid
+
k
);
/* Sum kid's data count to parent's and check for overflow */
if
((
dataCnt
+=
node
->
node
.
num
)
<=
OOC_DATAIDX_MAX
)
node
->
node
.
num
=
dataCnt
;
else
{
fputs
(
"OOC_BuildRecurse: data count overflow in node
\n
"
,
stderr
);
return
OOC_DATAIDX_ERR
;
}
/* Set kid index in parent (if first kid) and corresponding
* branch bit. The kid is the most recent node and thus at the
* end of the node array, which coincides with the current
* subtree root */
if
(
!
node
->
node
.
branch
)
node
->
node
.
kid
=
OOC_ROOTIDX
(
oct
);
OOC_SETBRANCH
(
node
,
k
);
}
}
else
{
/****************************** MAKE LEAF ****************************
* Queue contains no more than leafMax records, queue tail lies
* outside node's bounding box, or maxDepth reached
* ==> make this node a leaf.
*********************************************************************/
RREAL
*
key
;
#ifdef DEBUG_OOC_BUILD
MortonIdx
zIdx
,
lastzIdx
=
0
;
FVECT
/* key, */
lastKey
,
kidOrg
;
unsigned
lastk
=
0
;
#endif
/* Mark as leaf (note it's been cleared by the parent call) */
OOC_SETLEAF
(
node
);
while
(
!
QueueEmpty
(
queue
)
&&
OOC_InBBox
(
oct
,
org
,
size
,
(
key
=
oct
->
key
(
QueueHead
(
queue
)))))
{
/* Record lies inside leaf; increment data counter for octant
* containing record. */
if
((
k
=
OOC_Branch
(
oct
,
org
,
kidSize
,
key
,
NULL
))
<
0
)
{
/* Shouldn't happen, as key tested within bbox above */
fprintf
(
stderr
,
"OOC_BuildRecurse: buggered Morton code, "
"disruption in space-time continuum?
\n
"
);
return
OOC_DATAIDX_ERR
;
}
if
(
node
->
leaf
.
num
[
k
]
==
OOC_OCTCNT_MAX
)
{
/* Currently we're buggered here; merge records instead? */
fprintf
(
stderr
,
"OOC_BuildRecurse: data count overflow in "
"leaf: depth = %d, count = %d
\n
"
,
depth
,
node
->
leaf
.
num
[
k
]);
return
OOC_DATAIDX_ERR
;
}
++
node
->
leaf
.
num
[
k
];
#ifdef DEBUG_OOC_BUILD
/* VCOPY(key, oct -> key(QueueHead(queue))); */
if
((
zIdx
=
OOC_KEY2MORTON
(
key
,
oct
))
<
lastzIdx
)
{
fprintf
(
stderr
,
"OOC_BuildRecurse, make leaf: unsorted zIdx %020ld for "
"key [%f, %f, %f] (previous zIdx %020ld for "
"key [%f, %f, %f]
\n
"
,
zIdx
,
key
[
0
],
key
[
1
],
key
[
2
],
lastzIdx
,
lastKey
[
0
],
lastKey
[
1
],
lastKey
[
2
]
);
}
VCOPY
(
kidOrg
,
org
);
OOC_OCTORIGIN
(
kidOrg
,
k
,
kidSize
);
if
(
k
<
lastk
||
zIdx
<
lastzIdx
)
{
fprintf
(
stderr
,
"OOC_BuildRecurse, make leaf: unsorted octant %d (last %d) "
"with bbox [%f-%f, %f-%f, %f-%f] for key [%f, %f, %f] with "
"zIdx %020ld (last [%f, %f, %f], zIdx %020ld)
\n
"
,
k
,
lastk
,
kidOrg
[
0
],
kidOrg
[
0
]
+
kidSize
,
kidOrg
[
1
],
kidOrg
[
1
]
+
kidSize
,
kidOrg
[
2
],
kidOrg
[
2
]
+
kidSize
,
key
[
0
],
key
[
1
],
key
[
2
],
zIdx
,
lastKey
[
0
],
lastKey
[
1
],
lastKey
[
2
],
lastzIdx
);
}
lastk
=
k
;
lastzIdx
=
zIdx
;
VCOPY
(
lastKey
,
key
);
#endif
/* Remove record from queue */
QueuePop
(
queue
,
NULL
);
}
/* Refill queue for next node(s) */
if
(
QueueFill
(
queue
)
<
0
)
{
fputs
(
"OOC_Build: failed input queue fill
\n
"
,
stderr
);
return
OOC_DATAIDX_ERR
;
}
}
return
OOC_DATACNT
(
node
);
}
OOC_Octree
*
OOC_Build
(
OOC_Octree
*
oct
,
unsigned
leafMax
,
unsigned
maxDepth
)
/* Bottom-up construction of out-of-core octree in postorder traversal. The
* octree oct is assumed to be initialised with its origin (oct -> org),
* size (oct -> size), key callback (oct -> key), and its associated leaf
* file (oct -> leafFile).
* Records are read from the leafFile and assumed to be sorted in Z-order,
* which defines an octree leaf ordering. Leaves (terminal nodes) are
* constructed such that they contain <= leafMax records and have a maximum
* depth of maxDepth.
* Note that the following limits apply:
* leafMax <= OOC_OCTCNT_MAX (see oococt.h)
* maxDepth <= OOC_MORTON_BITS (see oocsort.h)
* The maxDepth limit arises from the fact that the Z-ordering has a limited
* resolution and will map node coordinates beyond a depth of
* OOC_MORTON_BITS to the same Z-index, causing nodes to be potentially read
* out of sequence and winding up in the wrong octree nodes.
* On success, the octree pointer oct is returned, with the constructed
* nodes in oct -> nodes, and the node count in oct -> numNodes. On
* failure, NULL is returned. */
{
OOC_BuildQueue
queue
;
OOC_Node
root
;
if
(
!
oct
||
!
oct
->
size
)
{
fputs
(
"OOC_Build: octree not initialised"
,
stderr
);
return
NULL
;
}
if
(
!
oct
->
leafFile
)
{
fputs
(
"OOC_Build: empty leaf file"
,
stderr
);
return
NULL
;
}
oct
->
leafMax
=
leafMax
;
oct
->
maxDepth
=
maxDepth
;
queue
.
in
=
oct
->
leafFile
;
rewind
(
queue
.
in
);
/* Init queue and fill from leaf file */
if
(
!
QueueInit
(
&
queue
,
oct
->
recSize
,
leafMax
+
1
)
||
QueueFill
(
&
queue
)
<
0
)
{
fputs
(
"OOC_Build: failed input queue init
\n
"
,
stderr
);
return
NULL
;
}
/* Clear octree root and recurse */
OOC_CLEARNODE
(
&
root
);
if
(
OOC_BuildRecurse
(
oct
,
&
root
,
oct
->
org
,
oct
->
size
,
0
,
&
queue
)
==
OOC_DATAIDX_ERR
)
return
NULL
;
/* Finalise octree root */
if
(
!
NewNode
(
oct
))
{
fputs
(
"OOC_Build: failed to allocate octree root
\n
"
,
stderr
);
return
NULL
;
}
OOC_SETROOT
(
oct
,
&
root
);
/* Passing OOC_ROOT(oct) avoids annoying compiler warnings about (&root)
* always evaluating to true when calling OOC_DATAIDX() */
oct
->
numData
=
OOC_DATACNT
(
OOC_ROOT
(
oct
));
return
oct
;
}
#endif
/* NIX / PMAP_OOC */
Event Timeline
Log In to Comment