OOOctreeBuilder Class Reference

#include <Octree.h>

Inheritance diagram for OOOctreeBuilder:

Collaboration diagram for OOOctreeBuilder:

Classes
struct	OOOctreeBuildState

Instance Methods
(Octree *)	- buildOctreeWithRadius:
(void)	- writeSolid
(void)	- writeEmpty
(void)	- beginInnerNode
(void)	- endInnerNode
(OOINLINE struct OOOctreeBuildState *)	- State [implementation]
(OOINLINE void)	- SetNode [implementation]
(OOINLINE void)	- InsertNode [implementation]
(id)	- init [implementation]
(void)	- dealloc [implementation]
(BOOL)	- suppressClangStuff [implementation]

Class Methods
(static void)	+ SetNode_slow [implementation]

Private Attributes
int *	_octree
uint_fast32_t	_nodeCount
uint_fast32_t	_capacity
struct OOOctreeBuilder::OOOctreeBuildState	_stateStack [kMaxOctreeDepth+1]
uint_fast8_t	_level

Detailed Description

Definition at line 92 of file Octree.h.

Method Documentation

beginInnerNode

- (void) beginInnerNode

Definition at line 816 of file Octree.m.

{
    NSAssert(_level < kMaxOctreeDepth, @"Attempt to build octree exceeding maximum depth.");
    
    // Insert relative offset to next free space.
    uint32_t newInsertionPoint = _nodeCount;
    InsertNode(self, (int)_nodeCount - State(self)->insertionPoint);
    
    /*
        Leave space for eight nodes.
        
        NOTE: this may leave memory uninitialized or leave _nodeCount pointing
        past the end of the buffer. A valid sequence of eight child insertions
        will fix both these problems by writing to all of the new slots.
    */
    _nodeCount += 8;
    
    // Push state and set up new "stack frame".
    _level++;
    State(self)->insertionPoint = newInsertionPoint;
    State(self)->remaining = 8;
}

Referenced by BuildSubOctree().

Here is the caller graph for this function:

buildOctreeWithRadius:

- (Octree *) buildOctreeWithRadius:

(GLfloat)

radius

Definition at line 816 of file Octree.m.

                                  :(GLfloat)radius
{
    NSAssert(State(self)->remaining == 0 && _level == 0, @"Attempt to produce octree from an octree builder in an incomplete state.");
    
    size_t dataSize = _nodeCount * sizeof *_octree;
    int *resized = realloc(_octree, dataSize);
    if (resized == NULL)  resized = _octree;
    
    /*  Hand over the bytes to the data object, which will be used directly by
        the Octree.
    */
    NSData *data = [NSData dataWithBytesNoCopy:resized
                                        length:dataSize
                                  freeWhenDone:YES];
    
    _octree = NULL;
    _nodeCount = 0;
    _capacity = 0;
    
    return [[[Octree alloc] initWithData:data radius:radius] autorelease];
}

dealloc

- (void) dealloc

implementation

Definition at line 816 of file Octree.m.

{
    free(_octree);
    
    [super dealloc];
}

endInnerNode

- (void) endInnerNode

Definition at line 816 of file Octree.m.

{
    NSAssert(State(self)->remaining == 0, @"Attempt to end an inner octree node with fewer than eight children.");
    NSAssert1(_level > 0, @"Unbalanced call to %s", __FUNCTION__);
    
    _level--;
    
    /*
        Check if the last eight nodes are solid. If so, we just inserted an
        entirely solid subtree and can fold it into a single solid node. An
        entirely solid subtree will always use the last eight nodes (any solid
        subtrees within a child node will have been folded already), so this
        simple approach to folding will produce an optimal result.
        
        We could do the same for empty nodes, but OOMeshToOctreeConverter will
        never recurse into an empty subtree.
    */
    
    NSAssert(_nodeCount > 8, @"After ending an inner node, there must be at least eight nodes in buffer.");
    for (uint_fast32_t node = _nodeCount - 8; node < _nodeCount; node++)
    {
        if (_octree[node] != -1)  return;
    }
    
    // If we got here, subtree is solid; fold it into a solid node.
    _octree[State(self)->insertionPoint - 1] = -1;
    _nodeCount -= 8;
}

Referenced by BuildSubOctree().

Here is the caller graph for this function:

init

- (id) init

implementation

Definition at line 816 of file Octree.m.

{
    if ((self = [super init]))
    {
        _capacity = kMinimumBuilderCapacity;
        _octree = malloc(_capacity * sizeof *_octree);
        if (_octree == NULL)
        {
            [self release];
            return nil;
        }
        
        /*
            We're initially inserting into the root slot, which must exist and
            takes a single node.
        */
        _nodeCount = 1;
        State(self)->remaining = 1;
    }
    return self;
}

InsertNode

- (OOINLINE void) InsertNode (OOOctreeBuilder *) self (int) value

implementation

Definition at line 816 of file Octree.m.

{
    NSCAssert(State(self)->remaining > 0, @"Attempt to add node to a full parent in octree builder.");
    State(self)->remaining--;
    
    SetNode(self, State(self)->insertionPoint++, value);
}

SetNode

- (OOINLINE void) SetNode (OOOctreeBuilder *) self (uint32_t) index (int) value

implementation

Definition at line 802 of file Octree.m.

{
    if (index < self->_capacity)
    {
        self->_octree[index] = value;
    }
    else
    {
        SetNode_slow(self, index, value);
    }
}

SetNode_slow

+ (static void) SetNode_slow (OOOctreeBuilder *) self (uint32_t) index (int) value

implementation

Definition at line 946 of file Octree.m.

{
    uint32_t newCapacity = MAX(self->_capacity * 2, (uint32_t)kMinimumBuilderCapacity);
    newCapacity = MAX(newCapacity, index + 1);
    
    int *newBuffer = realloc(self->_octree, newCapacity * sizeof *newBuffer);
    if (EXPECT_NOT(newBuffer == NULL))
    {
        [NSException raise:NSMallocException format:@"Failed to allocate memory for octree."];
    }
    
    self->_octree = newBuffer;
    self->_capacity = newCapacity;
    self->_octree[index] = value;
}

References EXPECT_NOT, kMinimumBuilderCapacity, MAX, and self.

State

- (OOINLINE struct OOOctreeBuildState *) State (OOOctreeBuilder *) self

implementation

Definition at line 794 of file Octree.m.

{
    return &self->_stateStack[self->_level];
}

References _level.

suppressClangStuff

- (BOOL) suppressClangStuff

implementation

Definition at line 946 of file Octree.m.

{
    return &_stateStack && 0;
}

writeEmpty

- (void) writeEmpty

Definition at line 816 of file Octree.m.

{
    InsertNode(self, 0);
}

Referenced by BuildSubOctree().

Here is the caller graph for this function:

writeSolid

- (void) writeSolid

Definition at line 816 of file Octree.m.

{
    InsertNode(self, -1);
}

Referenced by BuildSubOctree().

Here is the caller graph for this function:

Member Data Documentation

_capacity

- (uint_fast32_t) _capacity

private

Definition at line 96 of file Octree.h.

_level

- (uint_fast8_t) _level

private

Definition at line 102 of file Octree.h.

Referenced by State.

_nodeCount

- (uint_fast32_t) _nodeCount

private

Definition at line 96 of file Octree.h.

_octree

- (int*) _octree

private

Definition at line 95 of file Octree.h.

_stateStack

- (struct OOOctreeBuildState) OOOctreeBuilder:

private

---

The documentation for this class was generated from the following files:

• src/Core/Octree.h
• src/Core/Octree.m