3
\$\begingroup\$

The fn_AABB struct represents an axis aligned bounding box, by a center(position) and half lengths(hwidth). They also contain a set of planes for use in collision but that is not important to the octree.

The fn_getAABBSTouch function returns any aabbs in the octree that are contained within the AABB passed as an argument.

An octree works by partitioning 3d space into 8 rectangular regions and then recursively subdividing those regions to improve performance in collision queries.

fn_octree.h

#pragma once
#include "fn_aabb.h"

struct fn_OctreeNode
{
  int* indices;
  int indiceCount;
  fn_AABB box;
  struct fn_OctreeNode* children[8]; //8 of them at max
  bool leaf;
};

typedef struct
{
  struct fn_OctreeNode* root;
  fn_AABB* aabbs;
  int aabbCount;
}fn_Octree;

fn_Octree fn_createOctree(fn_AABB* aabbs,int aabbcount);

fn_Octree fn_createOctreeParam(fn_AABB* aabbs,int aabbcount,int max_elm,int max_depth);

int* fn_getAABBSTouch(fn_AABB aabb,fn_Octree* otree,int* indiceCount);

void fn_getAABBSTouchv(fn_AABB aabb,fn_Octree* otree,int* indiceCount,int* ret);

void fn_exportOctree(fn_Octree* octree,char* demoName);

fn_Octree fn_importOctree(char* demoName,fn_AABB* aabbs,int aabbCount);

fn_octree.c

#include "fn_octree.h"
#include <stdlib.h>
#include <string.h>
#include "../fn_engine/fn_arrayutils.h"
#include <zlib.h>
#include <stdio.h>
static int MAX_ELEMENTS = 10;//5
static int MAX_DEPTH = 20;//20



static void getAABBPoints(fn_AABB aabb,fn_vec3* points)
{

  points[0] = fn_addVec3(aabb.position,fn_createVec3(aabb.hwidth.x,aabb.hwidth.y,aabb.hwidth.z)); // 1 1 1
  points[1] = fn_addVec3(aabb.position,fn_createVec3(-aabb.hwidth.x,-aabb.hwidth.y,-aabb.hwidth.z));// -1 -1 -1
  points[2] = fn_addVec3(aabb.position,fn_createVec3(-aabb.hwidth.x,aabb.hwidth.y,aabb.hwidth.z)); // -1 1 1
  points[3] = fn_addVec3(aabb.position,fn_createVec3(-aabb.hwidth.x,-aabb.hwidth.y,aabb.hwidth.z)); // -1 -1 1
  points[4] = fn_addVec3(aabb.position,fn_createVec3(-aabb.hwidth.x,aabb.hwidth.y,-aabb.hwidth.z)); // -1 1 -1
  points[5] = fn_addVec3(aabb.position,fn_createVec3(aabb.hwidth.x,aabb.hwidth.y,-aabb.hwidth.z)); // 1 1 -1
  points[6] = fn_addVec3(aabb.position,fn_createVec3(aabb.hwidth.x,-aabb.hwidth.y,aabb.hwidth.z)); // 1 -1 1
  points[7] = fn_addVec3(aabb.position,fn_createVec3(aabb.hwidth.x,-aabb.hwidth.y,-aabb.hwidth.z)); // 1 -1 -1
}

static fn_AABB makeAABBMinMax(fn_vec3 min,fn_vec3 max)
{
  fn_AABB box = defaultAABB;
  box.position = fn_multVec3s(fn_addVec3(max,min),0.5);

  box.hwidth = fn_abs(fn_subVec3(box.position,min));

  return box;
}

static void makeChildren(struct fn_OctreeNode* root)
{
  fn_vec3 points[8];
  getAABBPoints(root->box,points);
  int i;
  for (i = 0;i < 8;i++)
  {
    root->children[i] = (struct fn_OctreeNode*)malloc(sizeof(struct fn_OctreeNode));
    root->children[i]->box = makeAABBMinMax(points[i],root->box.position);

    root->children[i]->indices = NULL;
    root->children[i]->indiceCount = 0;
    root->children[i]->leaf = true;
    memset(root->children[i]->children, 0, 8*sizeof(int));
    // root->children[i]->aabbs = root->aabbs;
    // root->children[i]->aabbCount = root->aabbCount;
  }
}

static void createTree_r(struct fn_OctreeNode* root,int* flatCount,fn_AABB** aabbs,int* aabbcount,int depth)
{
  //printf("%i\n",depth );
  int i,j;

  makeChildren(root);
  root->leaf = false;


  *flatCount = *flatCount+8;





  for (i = *aabbcount-1;i >=0 ;i--)
  {

    // int usedIndices[*aabbcount];
   // #pragma omp parallel for private(j)
    for (j =0 ;j < 8; j++)
    {

      if (fn_aabbCheck((*aabbs)[i],root->children[j]->box))
      {

        if (root->children[j]->indiceCount < MAX_ELEMENTS || depth > MAX_DEPTH )
        {


          root->children[j]->indiceCount++;

          root->children[j]->indices = realloc(root->children[j]->indices,sizeof(int)*root->children[j]->indiceCount);

          root->children[j]->indices[root->children[j]->indiceCount-1] = i;


        }
        else
        {
          createTree_r(root->children[j],flatCount,aabbs,aabbcount,depth + 1);
        }
      }
    }
  }




}



fn_Octree fn_createOctree(fn_AABB* aabbs,int aabbcount)
{
  fn_Octree ret;

  int i,j;
  struct fn_OctreeNode* root = malloc(sizeof(struct fn_OctreeNode));

  //get size of root node
  fn_vec3 min = aabbs[0].position;
  fn_vec3 max = aabbs[0].position;
  //#pragma omp parallel for private(i)
  for (i = 0;i < aabbcount;i++)
  {
    fn_vec3 points[8];
    getAABBPoints(aabbs[i],points);

    for (j = 0;j < 8;j ++)
    {

      if (points[j].x < min.x)
      {
        min.x = points[j].x;
      }
      if (points[j].y < min.y)
      {
        min.y = points[j].y;
      }
      if (points[j].z < min.z)
      {
        min.z = points[j].z;
      }

      if (points[j].x > max.x)
      {
        max.x = points[j].x;
      }
      if (points[j].y > max.y)
      {
        max.y = points[j].y;
      }
      if (points[j].z > max.z)
      {
        max.z = points[j].z;
      }

    }
  }
  root->box.position = fn_multVec3s(fn_addVec3(max,min),0.5);
  root->box.hwidth = fn_abs(fn_subVec3(root->box.position,min));

  root->indices = NULL;
  root->indiceCount = 0;
  root->leaf = false;
  memset(root->children, 0, 8*sizeof(int));

  ret.root = root;
  ret.aabbs = aabbs;
  ret.aabbCount = aabbcount;
  int flatCount = 1;



  createTree_r(ret.root,&flatCount, &aabbs, &aabbcount,0);

  return ret;
}

fn_Octree fn_createOctreeParam(fn_AABB* aabbs,int aabbcount,int max_elm,int max_depth)
{
  int temp1 = MAX_DEPTH,temp2 = MAX_ELEMENTS;
  MAX_ELEMENTS = max_elm;
  MAX_DEPTH = max_depth;
    fn_Octree ret;

  int i,j;
  struct fn_OctreeNode* root = malloc(sizeof(struct fn_OctreeNode));

  //get size of root node
  fn_vec3 min = aabbs[0].position;
  fn_vec3 max = aabbs[0].position;
  //#pragma omp parallel for private(i)
  for (i = 0;i < aabbcount;i++)
  {
    fn_vec3 points[8];
    getAABBPoints(aabbs[i],points);

    for (j = 0;j < 8;j ++)
    {

      if (points[j].x < min.x)
      {
        min.x = points[j].x;
      }
      if (points[j].y < min.y)
      {
        min.y = points[j].y;
      }
      if (points[j].z < min.z)
      {
        min.z = points[j].z;
      }

      if (points[j].x > max.x)
      {
        max.x = points[j].x;
      }
      if (points[j].y > max.y)
      {
        max.y = points[j].y;
      }
      if (points[j].z > max.z)
      {
        max.z = points[j].z;
      }

    }
  }
  root->box.position = fn_multVec3s(fn_addVec3(max,min),0.5);
  root->box.hwidth = fn_abs(fn_subVec3(root->box.position,min));

  root->indices = NULL;
  root->indiceCount = 0;
  root->leaf = false;
  memset(root->children, 0, 8*sizeof(int));

  ret.root = root;
  ret.aabbs = aabbs;
  ret.aabbCount = aabbcount;
  int flatCount = 1;



  createTree_r(ret.root,&flatCount, &aabbs, &aabbcount,0);

  MAX_ELEMENTS = temp2;
  MAX_DEPTH = temp1;
  return ret;
}



static void getAABBTouch_r(fn_AABB aabb,struct fn_OctreeNode* node,int* indiceCount,int** ret,int* usedIndices)
{
  int i,j;

  for (i =0;i< 8;i++)
  {
    if(fn_aabbCheck(aabb,node->children[i]->box))
    {
      // if (node->children[i]->leaf)
      // {
      if (node->children[i]->indiceCount > 0)
      {
        //   memcpy(&((*ret)[*indiceCount]),&node->children[i]->indices[0],node->children[i]->indiceCount * sizeof(int));
        // *indiceCount = *indiceCount+node->children[i]->indiceCount;
        for (j = 0;j < node->children[i]->indiceCount;j++)
        {
          if (usedIndices[node->children[i]->indices[j]] == 0)
          {
            *indiceCount = *indiceCount+1;

            (*ret)[*indiceCount - 1] = node->children[i]->indices[j];
            usedIndices[node->children[i]->indices[j]] = 1;
          }

        }
      }

      if (!node->children[i]->leaf)
        getAABBTouch_r(aabb,node->children[i],indiceCount,ret,usedIndices);

    }
  }

}


int* fn_getAABBSTouch(fn_AABB aabb,fn_Octree* otree,int* indiceCount)
{
  int* usedIndices = malloc(otree->aabbCount*sizeof(int));
  int i;
  *indiceCount = 0;

  for (i = 0; i < otree->aabbCount;i++)
    usedIndices[i] = 0;

  int* ret = malloc(sizeof(int)*(otree->aabbCount));
  if (fn_aabbCheck(aabb,otree->root->box))
    getAABBTouch_r(aabb,otree->root,indiceCount,&ret,usedIndices);

  free(usedIndices);
//  ret = realloc(ret,sizeof(int)*(*indiceCount));
  return ret;
}

void fn_getAABBSTouchv(fn_AABB aabb,fn_Octree* otree,int* indiceCount,int* ret)
{
  int* usedIndices = NULL;

  *indiceCount = 0;
  usedIndices = calloc(otree->aabbCount,sizeof(int));

  if (fn_aabbCheck(aabb,otree->root->box))
    getAABBTouch_r(aabb,otree->root,indiceCount,&ret,usedIndices);

  free(usedIndices);

}


static void export_r(gzFile f,struct fn_OctreeNode* root)
{

  int i;
  gzwrite(f,&root->indiceCount,sizeof(int)*1);
  if (root->indiceCount != 0)
    gzwrite(f,root->indices,sizeof(int)*root->indiceCount);
  gzwrite(f,&root->box,sizeof(fn_AABB));
  gzwrite(f,&root->leaf,sizeof(bool));
  if (!root->leaf)
  {
    for (i =0;i < 8;i++)
    {
      export_r(f,root->children[i]);
    }
  }

}

void fn_exportOctree(fn_Octree* octree,char* demoName)
{
  char filename[512] = "fn1/octrees/";
  strcat(filename,demoName);
  gzFile f = gzopen(filename, "wb");
  export_r(f,octree->root);
  gzclose(f);
}

static void import_r(gzFile f,struct fn_OctreeNode* root)
{

  int i;
  gzread(f,&root->indiceCount,sizeof(int)*1);
  if (root->indiceCount != 0)
  {
    root->indices = malloc(sizeof(int)*root->indiceCount);
    gzread(f,root->indices,sizeof(int)*root->indiceCount);
  }
  gzread(f,&root->box,sizeof(fn_AABB));
  gzread(f,&root->leaf,sizeof(bool));
  if (!root->leaf)
  {
    for (i =0;i < 8;i++)
    {
      root->children[i] = (struct fn_OctreeNode*)malloc(sizeof(struct fn_OctreeNode));
      root->children[i]->indices = NULL;
      root->children[i]->indiceCount = 0;
      root->children[i]->leaf = true;
      memset(root->children[i]->children, 0, 8*sizeof(int));
      import_r(f,root->children[i]);
    }
  }

}

fn_Octree fn_importOctree(char* demoName,fn_AABB* aabbs,int aabbCount)
{
  fn_Octree ret;
  ret.aabbs = aabbs;
  ret.aabbCount = aabbCount;
  ret.root = malloc(sizeof(struct fn_OctreeNode));
  char filename[512] = "fn1/octrees/";
  strcat(filename,demoName);
  gzFile f = gzopen(filename, "rb");

  import_r(f,ret.root);

  gzclose(f);
  return ret;
}
\$\endgroup\$
4
\$\begingroup\$

There are two programming principles that might aid you in your future programming, they are the Don't Repeat Yourself Principle and the Single Responsibility Principle. Following these principles generally make is easier to create good code, reduce the amount of code written and reduce the complexity of the code.

Don't Repeat Yourself

In software engineering, don't repeat yourself (DRY) is a principle of software development aimed at reducing repetition of software patterns, replacing them with abstractions; and several copies of the same data, using data normalization to avoid redundancy.

Generally when there is repeating code in a software module it indicates that a function should be written to contain that code or a loop should be written to perform the repetition.

When code repeats in different functions it becomes a maintenance problem. Someone can fix the code in one location and miss it in another location. The solution to this is to write a function for the code that repeats.

Reduce Complexity, Follow SRP
The Single Responsibility Principle states that every module or class should have responsibility over a single part of the functionality provided by the software, and that responsibility should be entirely encapsulated by the class. All its services should be narrowly aligned with that responsibility.

Robert C. Martin expresses the principle as follows: A class should have only one reason to change.

While this is primarily targeted at classes in object oriented languages it applies to functions and subroutines well.

The more separate functions there are the easier it is to understand or read the code. This also makes it easier for any programmer to maintain or debug the code.

The functions fn_Octree fn_createOctree(fn_AABB* aabbs, int aabbcount) and fn_Octree fn_createOctreeParam(fn_AABB* aabbs, int aabbcount, int max_elm, int max_depth) would both benefit from being broken up into at multiple functions, they are almost duplicates of each other. One of these functions can almost be implemented by calling the other function.

The more separate functions there are the easier it is to understand or read the code. This also makes it easier for any programmer to maintain or debug the code.

One good candidate for a function is the following code:

    for (j = 0; j < 8; j++)
    {
        if (points[j].x < min.x)
        {
            min.x = points[j].x;
        }
        if (points[j].y < min.y)
        {
            min.y = points[j].y;
        }
        if (points[j].z < min.z)
        {
            min.z = points[j].z;
        }

        if (points[j].x > max.x)
        {
            max.x = points[j].x;
        }
        if (points[j].y > max.y)
        {
            max.y = points[j].y;
        }
        if (points[j].z > max.z)
        {
            max.z = points[j].z;
        }
    }

One goal in programming is to reduce the number of lines of code in a function so that the entire function can be viewed at one time. This makes it easier to write and debug.

Prefer Local Variables over Global Variables

When I first started reading the code I thought that it was declaring numeric constants in a strange way because of the following:

static int MAX_ELEMENTS = 10;
static int MAX_DEPTH = 20;

Then I found the code where these variables were changed. Generally all capitals is reserved for constants that don't change within the code. Variables names are written in lower case, camelCase or FirstLetterCapital.

At least these variables are static and therefore contained within the file so that they are not global to the program.

The general problem with global variables is that it is very hard to debug code that uses them. One may have to search through many files and thousands of lines of code to find where the bug is being introduced. Since these variables are staticly defined one only has to search through a little less than 400 lines to find where bugs may be introduced.

Lack of Error Checking
In the function fn_Octree fn_importOctree(char* demoName, fn_AABB* aabbs, int aabbCount) there is no test on whether gzopen() was actually able to open the file, and in static void import_r(gzFile f, struct fn_OctreeNode* root) there are no tests on gzread() to indicate if there are any read errors. Input from a file can be error prone, the filename may be mistyped, the file size may be zero, there may not be enough data for one of the reads. It's always best to add error handling for file input.

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.