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 891 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;
}

References _level, _nodeCount, beginInnerNode, InsertNode, kMaxOctreeDepth, and State.

Referenced by beginInnerNode, and BuildSubOctree().

Here is the call graph for this function:

Here is the caller graph for this function:

buildOctreeWithRadius:

- (Octree *) buildOctreeWithRadius:

(GLfloat)

radius

Definition at line 856 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];
}

References _capacity, _level, _nodeCount, _octree, and State.

Referenced by OOMeshToOctreeConverter::findOctreeToDepth:.

Here is the call graph for this function:

Here is the caller graph for this function:

dealloc

- (void) dealloc

implementation

Definition at line 848 of file Octree.m.

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

References _octree, and dealloc.

Referenced by dealloc.

Here is the call graph for this function:

Here is the caller graph for this function:

endInnerNode

- (void) endInnerNode

Definition at line 915 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;
}

References _level, _nodeCount, _octree, endInnerNode, and State.

Referenced by BuildSubOctree(), and endInnerNode.

Here is the call graph for this function:

Here is the caller graph for this function:

init

- (id) init

implementation

Definition at line 825 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;
}

References _capacity, _nodeCount, _octree, init, kMinimumBuilderCapacity, nil, and State.

Referenced by init.

Here is the call graph for this function:

Here is the caller graph for this function:

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);
}

References OOINLINE, SetNode, and State.

Referenced by beginInnerNode, writeEmpty, and writeSolid.

Here is the call graph for this function:

Here is the caller graph for this function:

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);
    }
}

References _capacity, OOINLINE, and SetNode_slow.

Referenced by InsertNode.

Here is the call graph for this function:

Here is the caller graph for this function:

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, self, and SetNode_slow.

Referenced by SetNode, and SetNode_slow.

Here is the call graph for this function:

Here is the caller graph for this function:

State

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

implementation

Definition at line 794 of file Octree.m.

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

References _level, and OOINLINE.

Referenced by beginInnerNode, buildOctreeWithRadius:, endInnerNode, init, and InsertNode.

Here is the caller graph for this function:

suppressClangStuff

- (BOOL) suppressClangStuff

implementation

Definition at line 967 of file Octree.m.

{
    return &_stateStack && 0;
}

References _stateStack, and suppressClangStuff.

Referenced by suppressClangStuff.

Here is the call graph for this function:

Here is the caller graph for this function:

writeEmpty

- (void) writeEmpty

Definition at line 885 of file Octree.m.

{
    InsertNode(self, 0);
}

References InsertNode, and writeEmpty.

Referenced by BuildSubOctree(), and writeEmpty.

Here is the call graph for this function:

Here is the caller graph for this function:

writeSolid

- (void) writeSolid

Definition at line 879 of file Octree.m.

{
    InsertNode(self, -1);
}

References InsertNode, and writeSolid.

Referenced by BuildSubOctree(), and writeSolid.

Here is the call graph for this function:

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.

Referenced by buildOctreeWithRadius:, init, and SetNode.

_level

- (uint_fast8_t) _level

private

Definition at line 102 of file Octree.h.

Referenced by beginInnerNode, buildOctreeWithRadius:, endInnerNode, and State.

_nodeCount

- (uint_fast32_t) _nodeCount

private

Definition at line 96 of file Octree.h.

Referenced by beginInnerNode, buildOctreeWithRadius:, endInnerNode, and init.

_octree

- (int*) _octree

private

Definition at line 95 of file Octree.h.

Referenced by buildOctreeWithRadius:, dealloc, endInnerNode, and init.

_stateStack

- (struct OOOctreeBuildState) OOOctreeBuilder:

private

Referenced by suppressClangStuff.

---

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

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