#include <Octree.h>

Inheritance diagram for Octree:

Collaboration diagram for Octree:

Instance Methods
(id)	- initWithDictionary:

(Octree *)	- octreeScaledBy:

(void)	- drawOctree

(void)	- drawOctreeCollisions

(GLfloat)	- isHitByLine:v0:

(BOOL)	- isHitByOctree:withOrigin:andIJK:

(BOOL)	- isHitByOctree:withOrigin:andIJK:andScales:s1:

(NSDictionary *)	- dictionaryRepresentation

(GLfloat)	- volume

(Vector)	- randomPoint

(size_t)	- totalSize

(id)	- init `[implementation]`

(id)	- initWithData:radius: `[implementation]`

(void)	- dealloc `[implementation]`

(BOOL)	- hasCollision `[implementation]`

(void)	- setHasCollision: `[implementation]`

(Octree_details)	- octreeDetails `[implementation]`

(void)	- drawOctreeFromLocation:loc:scale: `[implementation]`

(void)	- drawOctreeCollisionFromLocation:loc:scale: `[implementation]`

Class Methods
(static Vector)	+ offsetForOctant `[implementation]`

(static BOOL)	+ isHitByLineSub `[implementation]`

(static BOOL)	+ isHitByLine `[implementation]`

(static BOOL)	+ isHitByOctree `[implementation]`

(static GLfloat)	+ volumeOfOctree `[implementation]`

(static Vector)	+ randomFullNodeFrom `[implementation]`

Private Attributes
GLfloat	_radius

uint32_t	_nodeCount

const int *	_octree

BOOL	_hasCollision

unsigned char *	_collisionOctree

NSData *	_data

Detailed Description

Definition at line 39 of file Octree.h.

Method Documentation

◆ dealloc

- (void) dealloc

implementation

Definition at line 47 of file Octree.m.

{
    DESTROY(_data);
    free(_collisionOctree);
    
    [super dealloc];
}

◆ dictionaryRepresentation

- (NSDictionary *) dictionaryRepresentation

Definition at line 497 of file Octree.m.

{
    return [NSDictionary dictionaryWithObjectsAndKeys:
        _data, @"octree",
        [NSNumber numberWithFloat:_radius], @"radius",
        nil];
}

References change_oct, isHitByOctree(), Octree_details::octree, Octree_details::octree_collision, OctreeDebugLog, and Octree_details::radius.

Here is the call graph for this function:

◆ drawOctree

- (void) drawOctree

Definition at line 170 of file Octree.m.

{
    OODebugWFState state = OODebugBeginWireframe(NO);
    
    OO_ENTER_OPENGL();
    OOGL(glEnable(GL_BLEND));
    OOGLBEGIN(GL_LINES);
    glColor4f(0.4f, 0.4f, 0.4f, 0.5f);
    
    // it's a series of cubes
    [self drawOctreeFromLocation:0 :_radius : kZeroVector];
    
    OOGLEND();
    
    OODebugEndWireframe(state);
    OOCheckOpenGLErrors(@"Octree after drawing %@", self);
}

◆ drawOctreeCollisionFromLocation:loc:scale:

- (void) drawOctreeCollisionFromLocation:	(uint32_t)
loc:	(GLfloat)
scale:	(Vector)	offset

implementation

Provided by category Octree(Private).

Definition at line 270 of file Octree.m.

                                        :(uint32_t)loc :(GLfloat)scale :(Vector)offset
{
    if (_octree[loc] == 0)
    {
        return;
    }
    
    if ((_octree[loc] != 0)&&(_collisionOctree[loc] != (unsigned char)0))   // full - draw
    {
        OO_ENTER_OPENGL();
        
        GLfloat red = (GLfloat)(_collisionOctree[loc])/255.0;
        glColor4f(1.0, 0.0, 0.0, red);  // 50% translucent
        
        drawTestForCollisions = YES;
        _collisionOctree[loc]--;
        
        // draw a cube
        OOGL(glDisable(GL_CULL_FACE));      // face culling
        
        OOGL(glDisable(GL_TEXTURE_2D));
 
        OOGLBEGIN(GL_LINE_STRIP);
            glVertex3f(-scale + offset.x, -scale + offset.y, -scale + offset.z);
            glVertex3f(-scale + offset.x, scale + offset.y, -scale + offset.z);
            glVertex3f(scale + offset.x, scale + offset.y, -scale + offset.z);
            glVertex3f(scale + offset.x, -scale + offset.y, -scale + offset.z);
            glVertex3f(-scale + offset.x, -scale + offset.y, -scale + offset.z);
        OOGLEND();
        
        OOGLBEGIN(GL_LINE_STRIP);
            glVertex3f(-scale + offset.x, -scale + offset.y, scale + offset.z);
            glVertex3f(-scale + offset.x, scale + offset.y, scale + offset.z);
            glVertex3f(scale + offset.x, scale + offset.y, scale + offset.z);
            glVertex3f(scale + offset.x, -scale + offset.y, scale + offset.z);
            glVertex3f(-scale + offset.x, -scale + offset.y, scale + offset.z);
        OOGLEND();
            
        OOGLBEGIN(GL_LINES);
            glVertex3f(-scale + offset.x, -scale + offset.y, -scale + offset.z);
            glVertex3f(-scale + offset.x, -scale + offset.y, scale + offset.z);
            
            glVertex3f(-scale + offset.x, scale + offset.y, -scale + offset.z);
            glVertex3f(-scale + offset.x, scale + offset.y, scale + offset.z);
            
            glVertex3f(scale + offset.x, scale + offset.y, -scale + offset.z);
            glVertex3f(scale + offset.x, scale + offset.y, scale + offset.z);
            
            glVertex3f(scale + offset.x, -scale + offset.y, -scale + offset.z);
            glVertex3f(scale + offset.x, -scale + offset.y, scale + offset.z);
        OOGLEND();
            
        OOGL(glEnable(GL_CULL_FACE));       // face culling
    }
    if (_octree[loc] > 0)
    {
        GLfloat sc = 0.5f * scale;
        [self drawOctreeCollisionFromLocation:loc + _octree[loc] + 0 :sc :make_vector(offset.x - sc, offset.y - sc, offset.z - sc)];
        [self drawOctreeCollisionFromLocation:loc + _octree[loc] + 1 :sc :make_vector(offset.x - sc, offset.y - sc, offset.z + sc)];
        [self drawOctreeCollisionFromLocation:loc + _octree[loc] + 2 :sc :make_vector(offset.x - sc, offset.y + sc, offset.z - sc)];
        [self drawOctreeCollisionFromLocation:loc + _octree[loc] + 3 :sc :make_vector(offset.x - sc, offset.y + sc, offset.z + sc)];
        [self drawOctreeCollisionFromLocation:loc + _octree[loc] + 4 :sc :make_vector(offset.x + sc, offset.y - sc, offset.z - sc)];
        [self drawOctreeCollisionFromLocation:loc + _octree[loc] + 5 :sc :make_vector(offset.x + sc, offset.y - sc, offset.z + sc)];
        [self drawOctreeCollisionFromLocation:loc + _octree[loc] + 6 :sc :make_vector(offset.x + sc, offset.y + sc, offset.z - sc)];
        [self drawOctreeCollisionFromLocation:loc + _octree[loc] + 7 :sc :make_vector(offset.x + sc, offset.y + sc, offset.z + sc)];
    }
}

References drawTestForCollisions, OOCheckOpenGLErrors(), OODebugBeginWireframe(), and OODebugEndWireframe().

Here is the call graph for this function:

◆ drawOctreeCollisions

- (void) drawOctreeCollisions

Definition at line 270 of file Octree.m.

{
    OODebugWFState state = OODebugBeginWireframe(NO);
    
    // it's a series of cubes
    drawTestForCollisions = NO;
    if (_hasCollision)
    {
        [self drawOctreeCollisionFromLocation:0 :_radius :kZeroVector];
    }
    _hasCollision = drawTestForCollisions;
    
    OODebugEndWireframe(state);
    OOCheckOpenGLErrors(@"Octree after drawing collisions for %@", self);
}

◆ drawOctreeFromLocation:loc:scale:

- (void) drawOctreeFromLocation:	(uint32_t)
loc:	(GLfloat)
scale:	(Vector)	offset

implementation

Provided by category Octree(Private).

Definition at line 170 of file Octree.m.

                               :(uint32_t)loc :(GLfloat)scale :(Vector)offset
{
    if (_octree[loc] == 0)
    {
        return;
    }
    
    OO_ENTER_OPENGL();
    
    if (_octree[loc] == -1) // full
    {
        // draw a cube
        glVertex3f(-scale + offset.x, -scale + offset.y, -scale + offset.z);
        glVertex3f(-scale + offset.x, scale + offset.y, -scale + offset.z);
        glVertex3f(-scale + offset.x, scale + offset.y, -scale + offset.z);
        glVertex3f(scale + offset.x, scale + offset.y, -scale + offset.z);
        glVertex3f(scale + offset.x, scale + offset.y, -scale + offset.z);
        glVertex3f(scale + offset.x, -scale + offset.y, -scale + offset.z);
        glVertex3f(scale + offset.x, -scale + offset.y, -scale + offset.z);
        glVertex3f(-scale + offset.x, -scale + offset.y, -scale + offset.z);
        
            
        glVertex3f(-scale + offset.x, -scale + offset.y, scale + offset.z);
        glVertex3f(-scale + offset.x, scale + offset.y, scale + offset.z);
        glVertex3f(-scale + offset.x, scale + offset.y, scale + offset.z);
        glVertex3f(scale + offset.x, scale + offset.y, scale + offset.z);
        glVertex3f(scale + offset.x, scale + offset.y, scale + offset.z);
        glVertex3f(scale + offset.x, -scale + offset.y, scale + offset.z);
        glVertex3f(scale + offset.x, -scale + offset.y, scale + offset.z);
        glVertex3f(-scale + offset.x, -scale + offset.y, scale + offset.z);
            
        glVertex3f(-scale + offset.x, -scale + offset.y, -scale + offset.z);
        glVertex3f(-scale + offset.x, -scale + offset.y, scale + offset.z);
        
        glVertex3f(-scale + offset.x, scale + offset.y, -scale + offset.z);
        glVertex3f(-scale + offset.x, scale + offset.y, scale + offset.z);
        
        glVertex3f(scale + offset.x, scale + offset.y, -scale + offset.z);
        glVertex3f(scale + offset.x, scale + offset.y, scale + offset.z);
        
        glVertex3f(scale + offset.x, -scale + offset.y, -scale + offset.z);
        glVertex3f(scale + offset.x, -scale + offset.y, scale + offset.z);
    }
    else if (_octree[loc] > 0)
    {
        GLfloat sc = 0.5f * scale;
        OCTREE_COLOR(0.4f, 0.4f, 0.4f, 0.5f);
        [self drawOctreeFromLocation:loc + _octree[loc] + 0 :sc :make_vector(offset.x - sc, offset.y - sc, offset.z - sc)];
        OCTREE_COLOR(0.0f, 0.0f, 1.0f, 0.5f);
        [self drawOctreeFromLocation:loc + _octree[loc] + 1 :sc :make_vector(offset.x - sc, offset.y - sc, offset.z + sc)];
        OCTREE_COLOR(0.0f, 1.0f, 0.0f, 0.5f);
        [self drawOctreeFromLocation:loc + _octree[loc] + 2 :sc :make_vector(offset.x - sc, offset.y + sc, offset.z - sc)];
        OCTREE_COLOR(0.0f, 1.0f, 1.0f, 0.5f);
        [self drawOctreeFromLocation:loc + _octree[loc] + 3 :sc :make_vector(offset.x - sc, offset.y + sc, offset.z + sc)];
        OCTREE_COLOR(1.0f, 0.0f, 0.0f, 0.5f);
        [self drawOctreeFromLocation:loc + _octree[loc] + 4 :sc :make_vector(offset.x + sc, offset.y - sc, offset.z - sc)];
        OCTREE_COLOR(1.0f, 0.0f, 1.0f, 0.5f);
        [self drawOctreeFromLocation:loc + _octree[loc] + 5 :sc :make_vector(offset.x + sc, offset.y - sc, offset.z + sc)];
        OCTREE_COLOR(1.0f, 1.0f, 0.0f, 0.5f);
        [self drawOctreeFromLocation:loc + _octree[loc] + 6 :sc :make_vector(offset.x + sc, offset.y + sc, offset.z - sc)];
        OCTREE_COLOR(1.0f, 1.0f, 1.0f, 0.5f);
        [self drawOctreeFromLocation:loc + _octree[loc] + 7 :sc :make_vector(offset.x + sc, offset.y + sc, offset.z + sc)];
    }
}

◆ hasCollision

- (BOOL) hasCollision

implementation

Provided by category Octree(Private).

Definition at line 47 of file Octree.m.

{
    return _hasCollision;
}

◆ init

- (id) init

implementation

Definition at line 47 of file Octree.m.

{
    // -init makes no sense, since octrees are immutable.
    [self release];
    [NSException raise:NSInternalInconsistencyException format:@"Call of invalid initializer %s", __FUNCTION__];
    return nil;
}

◆ initWithData:radius:

- (id) initWithData:		(NSData *)	data
radius:		(GLfloat)	radius

implementation

Definition at line 47 of file Octree.m.

                   :(NSData *)data
             radius:(GLfloat)radius
{
    if ((self = [super init]))
    {
        _data = [data copy];
        _radius = radius;
        
        NSUInteger nodeCount = [_data length] / sizeof *_octree;
        NSParameterAssert(nodeCount < UINT32_MAX);
        _nodeCount = (uint32_t)nodeCount;
        
        _octree = [_data bytes];
        
        _collisionOctree = calloc(1, _nodeCount);
        if (_octree == NULL || _collisionOctree == NULL)
        {
            [self release];
            return nil;
        }
    }
    
    return self;
}

◆ initWithDictionary:

- (id) initWithDictionary: (NSDictionary *) dictionary

Definition at line 47 of file Octree.m.

                         :(NSDictionary *)dict
{
    NSData *data = [dict objectForKey:@"octree"];
    if (![data isKindOfClass:[NSData class]] || ([data length] % sizeof (int)) != 0)
    {
        // Invalid representation.
        [self release];
        return nil;
    }
    
    return [self initWithData:data radius:[dict oo_floatForKey:@"radius"]];
}

◆ isHitByLine

+ (static BOOL) isHitByLine	(const int *)	octbuffer
	(unsigned char *)	collbuffer
	(int)	level
	(GLfloat)	rad
	(Vector)	v0
	(Vector)	v1
	(Vector)	off
	(int)	face_hit

implementation

Definition at line 372 of file Octree.m.

{
    // displace the line by the offset
    Vector u0 = make_vector(v0.x + off.x, v0.y + off.y, v0.z + off.z);
    Vector u1 = make_vector(v1.x + off.x, v1.y + off.y, v1.z + off.z);
    
    OctreeDebugLog(@"DEBUG octant: [%d] radius: %.2f vs. line: (%.2f, %.2f, %.2f) - (%.2f, %.2f, %.2f)",
        level, rad, u0.x, u0.y, u0.z, u1.x, u1.y, u1.z);
 
    if (octbuffer[level] == 0)
    {
        OctreeDebugLog(@"DEBUG Hit an empty octant: [%d]", level);
        return NO;
    }
    
    if (octbuffer[level] == -1)
    {
        OctreeDebugLog(@"DEBUG Hit a solid octant: [%d]", level);
        collbuffer[level] = 2;  // green
        hit_dist = sqrt(u0.x * u0.x + u0.y * u0.y + u0.z * u0.z);
        return YES;
    }
    
    int faces = face_hit;
    if (faces == 0)
        faces = lineCubeIntersection(u0, u1, rad);
 
    if (faces == 0)
    {
        OctreeDebugLog(@"----> Line misses octant: [%d].", level);
        return NO;
    }
    
    int octantIntersected = 0;
    
    if (faces > 0)
    {
        Vector vi = lineIntersectionWithFace(u0, u1, faces, rad);
        
        if (CUBE_FACE_FRONT & faces)
            octantIntersected = ((vi.x < 0.0)? 1: 5) + ((vi.y < 0.0)? 0: 2);
        if (CUBE_FACE_BACK & faces)
            octantIntersected = ((vi.x < 0.0)? 0: 4) + ((vi.y < 0.0)? 0: 2);
        
        if (CUBE_FACE_RIGHT & faces)
            octantIntersected = ((vi.y < 0.0)? 4: 6) + ((vi.z < 0.0)? 0: 1);
        if (CUBE_FACE_LEFT & faces)
            octantIntersected = ((vi.y < 0.0)? 0: 2) + ((vi.z < 0.0)? 0: 1);
 
        if (CUBE_FACE_TOP & faces)
            octantIntersected = ((vi.x < 0.0)? 2: 6) + ((vi.z < 0.0)? 0: 1);
        if (CUBE_FACE_BOTTOM & faces)
            octantIntersected = ((vi.x < 0.0)? 0: 4) + ((vi.z < 0.0)? 0: 1);
 
        OctreeDebugLog(@"----> found intersection with face 0x%2x of cube of radius %.2f at (%.2f, %.2f, %.2f) octant:%d",
                faces, rad, vi.x, vi.y, vi.z, octantIntersected);
    }
    else
    {   
        OctreeDebugLog(@"----> inside cube of radius %.2f octant:%d", rad, octantIntersected);
    }
    
    hasCollided = YES;
    
    collbuffer[level] = 1;  // red
    
    OctreeDebugLog(@"%@", @"----> testing octants...");
    
    int nextLevel = level + octbuffer[level];
        
    GLfloat rd2 = 0.5f * rad;
    
    // first test the intersected octant, then the three adjacent, then the next three adjacent, the finally the diagonal octant
    int oct0, oct1, oct2, oct3; // test oct0 then oct1, oct2, oct3 then (7 - oct1), (7 - oct2), (7 - oct3) then (7 - oct0)
    oct0 = octantIntersected;
    oct1 = oct0 ^ 0x01; // adjacent x
    oct2 = oct0 ^ 0x02; // adjacent y
    oct3 = oct0 ^ 0x04; // adjacent z
    
    OctreeDebugLog(@"----> testing first octant hit [+%d]", oct0);
    if (isHitByLineSub(octbuffer, collbuffer, nextLevel, rad, rd2, u0, u1, oct0))  return YES;  // first octant
        
    // test the three adjacent octants
 
    OctreeDebugLog(@"----> testing next three octants [+%d] [+%d] [+%d]", oct1, oct2, oct3);
    if (isHitByLineSub(octbuffer, collbuffer, nextLevel, rad, rd2, u0, u1, oct1))  return YES;  // second octant
    if (isHitByLineSub(octbuffer, collbuffer, nextLevel, rad, rd2, u0, u1, oct2))  return YES;  // third octant
    if (isHitByLineSub(octbuffer, collbuffer, nextLevel, rad, rd2, u0, u1, oct3))  return YES;  // fourth octant
    
    // go to the next four octants
    
    oct0 ^= 0x07;   oct1 ^= 0x07;   oct2 ^= 0x07;   oct3 ^= 0x07;
    
    OctreeDebugLog(@"----> testing back three octants [+%d] [+%d] [+%d]", oct1, oct2, oct3);
    if (isHitByLineSub(octbuffer, collbuffer, nextLevel, rad, rd2, u0, u1, oct1))  return YES;  // fifth octant
    if (isHitByLineSub(octbuffer, collbuffer, nextLevel, rad, rd2, u0, u1, oct2))  return YES;  // sixth octant
    if (isHitByLineSub(octbuffer, collbuffer, nextLevel, rad, rd2, u0, u1, oct3))  return YES;  // seventh octant
    
    // and check the last octant
    OctreeDebugLog(@"----> testing final octant [+%d]", oct0);
    if (isHitByLineSub(octbuffer, collbuffer, nextLevel, rad, rd2, u0, u1, oct0))  return YES;  // last octant
    
    return NO;
}

References hasCollided, hit_dist, lineCubeIntersection(), lineIntersectionWithFace(), and OctreeDebugLog.

Here is the call graph for this function:

◆ isHitByLine:v0:

- (GLfloat) isHitByLine:		(Vector)
v0:		(Vector)	v1

Definition at line 372 of file Octree.m.

                       :(Vector)v0 :(Vector)v1
{
    memset(_collisionOctree, 0, _nodeCount * sizeof *_collisionOctree);
    hasCollided = NO;
    
    if (isHitByLine(_octree, _collisionOctree, 0, _radius, v0, v1, kZeroVector, 0))
    {
        OctreeDebugLog(@"DEBUG Hit at distance %.2f", hit_dist);
        _hasCollision = hasCollided;
        return hit_dist;
    }
    else
    {
        OctreeDebugLog(@"%@", @"DEBUG Missed!");
        _hasCollision = hasCollided;
        return 0.0f;
    }
}

◆ isHitByLineSub

+ (static BOOL) isHitByLineSub	(const int *)	octbuffer
	(unsigned char *)	collbuffer
	(int)	nextLevel
	(GLfloat)	rad
	(GLfloat)	rd2
	(Vector)	v0
	(Vector)	v1
	(int)	octantMask

implementation

Definition at line 359 of file Octree.m.

{
    if (octbuffer[nextLevel + octantMask])
    {
        Vector moveLine = offsetForOctant(octantMask, rad);
        return isHitByLine(octbuffer, collbuffer, nextLevel + octantMask, rd2, v0, v1, moveLine, 0);
    }
    else  return NO;
}

References isHitByLine().

Here is the call graph for this function:

◆ isHitByOctree

+ (static BOOL) isHitByOctree	(Octree_details)	axialDetails
	(Octree_details)	otherDetails
	(Vector)	otherPosition
	(Triangle)	other_ijk

implementation

Definition at line 497 of file Octree.m.

{
    const int *axialBuffer = axialDetails.octree;
    const int *otherBuffer = otherDetails.octree;
 
    if (axialBuffer[0] == 0)
    {
        OctreeDebugLog(@"%@", @"DEBUG Axial octree is empty.");
        return NO;
    }
    
    if (!otherBuffer)
    {
        OctreeDebugLog(@"%@", @"DEBUG Other octree is undefined.");
        return NO;
    }
    
    if (otherBuffer[0] == 0)
    {
        OctreeDebugLog(@"%@", @"DEBUG Other octree is empty.");
        return NO;
    }
    
    GLfloat axialRadius = axialDetails.radius;
    GLfloat otherRadius = otherDetails.radius;
    
    if (otherRadius < axialRadius) // test axial cube against other sphere
    {
        // 'crude and simple' - test sphere against cube...
        if ((otherPosition.x + otherRadius < -axialRadius)||(otherPosition.x - otherRadius > axialRadius)||
            (otherPosition.y + otherRadius < -axialRadius)||(otherPosition.y - otherRadius > axialRadius)||
            (otherPosition.z + otherRadius < -axialRadius)||(otherPosition.z - otherRadius > axialRadius))
        {
            OctreeDebugLog(@"%@", @"----> Other sphere does not intersect axial cube");
            return NO;
        }
    }
    else    // test axial sphere against other cube
    {
        Vector  d2 = vector_flip(otherPosition);
        Vector  axialPosition = resolveVectorInIJK(d2, other_ijk);
        if ((axialPosition.x + axialRadius < -otherRadius)||(axialPosition.x - axialRadius > otherRadius)||
            (axialPosition.y + axialRadius < -otherRadius)||(axialPosition.y - axialRadius > otherRadius)||
            (axialPosition.z + axialRadius < -otherRadius)||(axialPosition.z - axialRadius > otherRadius))
        {
            OctreeDebugLog(@"%@", @"----> Axial sphere does not intersect other cube");
            return NO;
        }
    }
    
    // from here on, this Octree and the other Octree are considered to be intersecting
    unsigned char   *axialCollisionBuffer = axialDetails.octree_collision;
    unsigned char   *otherCollisionBuffer = otherDetails.octree_collision;
    if (axialBuffer[0] == -1)
    {
        // we are SOLID - is the other octree?
        if (otherBuffer[0] == -1)
        {
            // YES so octrees collide
            axialCollisionBuffer[0] = (unsigned char)255;   // mark
            otherCollisionBuffer[0] = (unsigned char)255;   // mark
            
            OctreeDebugLog(@"%@", @"DEBUG Octrees collide!");
            return YES;
        }
        // the other octree must be decomposed
        // and each of its octants tested against the axial octree
        // if any of them collides with this octant
        // then we have a solid collision
        
        OctreeDebugLog(@"%@", @"----> testing other octants...");
        
        // work out the nearest octant to the axial octree
        int nearest_oct = ((otherPosition.x > 0.0)? 0:4)|((otherPosition.y > 0.0)? 0:2)|((otherPosition.z > 0.0)? 0:1);
        
        int             nextLevel = otherBuffer[0];
        const int       *nextBuffer = &otherBuffer[nextLevel];
        unsigned char   *nextCollisionBuffer = &otherCollisionBuffer[nextLevel];
        Octree_details  nextDetails;
        Vector          voff, nextPosition;
        unsigned        i, oct;
        
        nextDetails.radius = 0.5f * otherRadius;
        for (i = 0; i < 8; i++)
        {
            oct = nearest_oct ^ change_oct[i];  // work from nearest to furthest
            if (nextBuffer[oct])    // don't test empty octants
            {
                nextDetails.octree = &nextBuffer[oct];
                nextDetails.octree_collision = &nextCollisionBuffer[oct];
                
                voff = resolveVectorInIJK(offsetForOctant(oct, otherRadius), other_ijk);
                nextPosition = vector_subtract(otherPosition, voff);
                if (isHitByOctree(axialDetails, nextDetails, nextPosition, other_ijk))  // test octant
                    return YES;
            }
        }
        
        // otherwise
        return NO;
    }
    // we are not solid
    // we must test each of our octants against
    // the other octree, if any of them collide
    // we have a solid collision
    
    OctreeDebugLog(@"%@", @"----> testing axial octants...");
    
    // work out the nearest octant to the other octree
    int nearest_oct = ((otherPosition.x > 0.0)? 4:0)|((otherPosition.y > 0.0)? 2:0)|((otherPosition.z > 0.0)? 1:0);
    
    int             nextLevel = axialBuffer[0];
    const int       *nextBuffer = &axialBuffer[nextLevel];
    unsigned char   *nextCollisionBuffer = &axialCollisionBuffer[nextLevel];
    Vector          nextPosition;
    Octree_details  nextDetails;
    unsigned        i, oct;
    
    nextDetails.radius = 0.5f * axialRadius;
    for (i = 0; i < 8; i++)
    {
        oct = nearest_oct ^ change_oct[i];  // work from nearest to furthest
        if (nextBuffer[oct])    // don't test empty octants
        {
            nextDetails.octree = &nextBuffer[oct];
            nextDetails.octree_collision = &nextCollisionBuffer[oct];
            
            nextPosition = vector_add(otherPosition, offsetForOctant(oct, axialRadius));
            if (isHitByOctree(nextDetails, otherDetails, nextPosition, other_ijk))
            {
                return YES; // test octant
            }
        }
    }
    // otherwise we're done!
    return NO;
}

◆ isHitByOctree:withOrigin:andIJK:

- (BOOL) isHitByOctree:	(Octree *)	other
withOrigin:	(Vector)	origin
andIJK:	(Triangle)	ijk

Definition at line 497 of file Octree.m.

                      :(Octree *)other withOrigin:(Vector)v0 andIJK:(Triangle)ijk
{
    if (other == nil)  return NO;
    
    BOOL hit = isHitByOctree([self octreeDetails], [other octreeDetails], v0, ijk);
    
    _hasCollision = _hasCollision || hit;
    [other setHasCollision: [other hasCollision] || hit];
    
    return hit; 
}

◆ isHitByOctree:withOrigin:andIJK:andScales:s1:

- (BOOL) isHitByOctree:	(Octree *)	other
withOrigin:	(Vector)	origin
andIJK:	(Triangle)	ijk
andScales:	(GLfloat)
s1:	(GLfloat)	s2

Definition at line 497 of file Octree.m.

                      :(Octree *)other withOrigin:(Vector)v0 andIJK:(Triangle)ijk andScales:(GLfloat) s1 :(GLfloat)s2
{
    Octree_details details1 = [self octreeDetails];
    Octree_details details2 = [other octreeDetails];
    
    details1.radius *= s1;
    details2.radius *= s2;
    
    BOOL hit = isHitByOctree(details1, details2, v0, ijk);
    
    _hasCollision = _hasCollision || hit;
    [other setHasCollision: [other hasCollision] || hit];
    
    return hit; 
}

◆ octreeDetails

- (Octree_details) octreeDetails

implementation

Provided by category Octree(Private).

Definition at line 47 of file Octree.m.

{
    Octree_details details =
    {
        .octree = _octree,
        .radius = _radius,
        .octree_collision = _collisionOctree
    };
    return details;
}

◆ octreeScaledBy:

- (Octree *) octreeScaledBy: (GLfloat) factor

Definition at line 47 of file Octree.m.

                           :(GLfloat)factor
{
    // Since octree data is immutable, we can share.
    return [[[Octree alloc] initWithData:_data radius:_radius * factor] autorelease];
}

◆ offsetForOctant

+ (static Vector) offsetForOctant		(int)	oct
		(GLfloat)	r

implementation

Definition at line 170 of file Octree.m.

{
    return make_vector((0.5f - (GLfloat)((oct >> 2) & 1)) * r, (0.5f - (GLfloat)((oct >> 1) & 1)) * r, (0.5f - (GLfloat)(oct & 1)) * r);
}

◆ randomFullNodeFrom

+ (static Vector) randomFullNodeFrom		(Octree_details)	details
		(Vector)	offset

implementation

Definition at line 730 of file Octree.m.

{
    const int *octBuffer = details.octree;
    GLfloat octRadius = details.radius;
    
    if (octBuffer[0] == 0)  return offset;
    if (octBuffer[0] == -1)  return offset;
    
    // We are not empty or solid.
    // Pick a location from a random octant.
    Octree_details  nextDetails;
    int             nextLevel = octBuffer[0];
    const int       *nextBuffer = &octBuffer[nextLevel];
    unsigned        i, oct;
    
    nextDetails.radius = 0.5f * octRadius;
    nextDetails.octree_collision = NULL;
    oct = Ranrot() & 7;
    
    for (i = 0; i < 8; i++)
    {
        int octant = oct ^ i;
        if (nextBuffer[octant]) // don't test empty octants
        {
            nextDetails.octree = &nextBuffer[octant];
            Vector voff = vector_add(offset, offsetForOctant(octant, octRadius));
            return randomFullNodeFrom(nextDetails, voff);
        }
    }
    return offset;
}

References Octree_details::octree, Octree_details::octree_collision, Octree_details::radius, randomFullNodeFrom(), and Ranrot().

Here is the call graph for this function:

◆ randomPoint

- (Vector) randomPoint

Definition at line 730 of file Octree.m.

{
    return randomFullNodeFrom([self octreeDetails], kZeroVector);
}

◆ setHasCollision:

- (void) setHasCollision: (BOOL) value

implementation

Provided by category Octree(Private).

Definition at line 47 of file Octree.m.

                        :(BOOL)value
{
    _hasCollision = !!value;
}

◆ totalSize

- (size_t) totalSize

Definition at line 730 of file Octree.m.

{
    return [self oo_objectSize] + _nodeCount * [_data oo_objectSize] + [_data length] + _nodeCount * sizeof *_collisionOctree;
}

◆ volume

- (GLfloat) volume

Definition at line 676 of file Octree.m.

{
    /*  For backwards compatibility, limit octree iteration for volume
     calculation to five levels. Raising the limit means lower calculated
     volumes for large ships.
     
     EMMSTRAN: consider raising the limit but fudging mass lock calculations
     to compensate. See http://aegidian.org/bb/viewtopic.php?f=3&t=9176 .
     Then again, five levels of iteration might be fine.
     -- Ahruman 2011-03-10
     */
    return volumeOfOctree([self octreeDetails], 5);
}

References Octree_details::octree, Octree_details::octree_collision, Octree_details::radius, and volumeOfOctree().

Here is the call graph for this function:

◆ volumeOfOctree

+ (static GLfloat) volumeOfOctree		(Octree_details)	octree_details
		(unsigned)	depthLimit

implementation

Definition at line 676 of file Octree.m.

{
    const int *octBuffer = octree_details.octree;
    GLfloat octRadius = octree_details.radius;
    
    if (octBuffer[0] == 0)
    {
        return 0.0f;
    }
    
    if (octBuffer[0] == -1 || depthLimit == 0)
    {
        return octRadius * octRadius * octRadius;
    }
    depthLimit--;
    
    // We are not empty or solid.
    // We sum the volume of each of our octants.
    GLfloat         sumVolume = 0.0f;
    Octree_details  nextDetails;
    int             nextLevel = octBuffer[0];
    const int       *nextBuffer = &octBuffer[nextLevel];
    unsigned        i;
    
    nextDetails.radius = 0.5f * octRadius;
    nextDetails.octree_collision = NULL;    // Placate static analyzer
    
    for (i = 0; i < 8; i++)
    {
        if (nextBuffer[i])  // don't test empty octants
        {
            nextDetails.octree = &nextBuffer[i];
            sumVolume += volumeOfOctree(nextDetails, depthLimit);
        }
    }
    return sumVolume;
}

Member Data Documentation

◆ _collisionOctree

- (unsigned char*) _collisionOctree

private

Definition at line 47 of file Octree.h.

◆ _data

- (NSData*) _data

private

Definition at line 49 of file Octree.h.

◆ _hasCollision

- (BOOL) _hasCollision

private

Definition at line 45 of file Octree.h.

◆ _nodeCount

- (uint32_t) _nodeCount

private

Definition at line 43 of file Octree.h.

◆ _octree

- (const int*) _octree

private

Definition at line 44 of file Octree.h.

◆ _radius

- (GLfloat) _radius

private

Definition at line 42 of file Octree.h.

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

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

Instance Methods

Class Methods

Private Attributes

Detailed Description

Method Documentation

◆ dealloc

◆ dictionaryRepresentation

◆ drawOctree

◆ drawOctreeCollisionFromLocation:loc:scale:

◆ drawOctreeCollisions

◆ drawOctreeFromLocation:loc:scale:

◆ hasCollision

◆ init

◆ initWithData:radius:

◆ initWithDictionary:

◆ isHitByLine

◆ isHitByLine:v0:

◆ isHitByLineSub

◆ isHitByOctree

◆ isHitByOctree:withOrigin:andIJK:

◆ isHitByOctree:withOrigin:andIJK:andScales:s1:

◆ octreeDetails

◆ octreeScaledBy:

◆ offsetForOctant

◆ randomFullNodeFrom

◆ randomPoint

◆ setHasCollision:

◆ totalSize

◆ volume

◆ volumeOfOctree

Member Data Documentation

◆ _collisionOctree

◆ _data

◆ _hasCollision

◆ _nodeCount

◆ _octree

◆ _radius