Scribd Logo
Upload

Welcome to Scribd!

  • 86 views

    Octree Representation Source Code

    Uploaded by

    prasadreddy87
    The document describes an octree representation used to store 3D data in a tree structure. It includes code for a C++ implementation of an octree with classes for nodes, data arrays, and the overall octree. The code reads in random 3D data, builds an octree from that data by recursively dividing it into octants, and performs a depth-first traversal to print out the node values.

    Copyright:

    Attribution Non-Commercial (BY-NC)
    Download as DOCX, PDF, TXT or read online from Scribd

    Octree Representation Source Code

    Uploaded by

    prasadreddy87
    86 views5 pages
    The document describes an octree representation used to store 3D data in a tree structure. It includes code for a C++ implementation of an octree with classes for nodes, data arrays, and the overall octree. The code reads in random 3D data, builds an octree from that data by recursively dividing it into octants, and performs a depth-first traversal to print out the node values.

    Original Title

    Octree Representation

    Copyright

    © Attribution Non-Commercial (BY-NC)

    Available Formats

    DOCX, PDF, TXT or read online from Scribd

    Did you find this document useful?

    Is this content inappropriate?

    The document describes an octree representation used to store 3D data in a tree structure. It includes code for a C++ implementation of an octree with classes for nodes, data arrays, and the overall octree. The code reads in random 3D data, builds an octree from that data by recursively dividing it into octants, and performs a depth-first traversal to print out the node values.

    Copyright:

    Attribution Non-Commercial (BY-NC)
    Download as DOCX, PDF, TXT or read online from Scribd
    Download as docx, pdf, or txt
    86 views5 pages

    Octree Representation Source Code

    Uploaded by

    prasadreddy87
    The document describes an octree representation used to store 3D data in a tree structure. It includes code for a C++ implementation of an octree with classes for nodes, data arrays, and the overall octree. The code reads in random 3D data, builds an octree from that data by recursively dividing it into octants, and performs a depth-first traversal to print out the node values.

    Copyright:

    Attribution Non-Commercial (BY-NC)
    Download as DOCX, PDF, TXT or read online from Scribd
    Download as docx, pdf, or txt
    of 5

    Octree Representation

    Source Code:
    /******************************** octree.cpp
    ********************************/
    #include <stdio.h>
    #include <stdlib.h>
    #include <string.h>
    #include <conio.h>
    typedef unsigned char uchar;
    typedef unsigned short ushort;
    #define XVAL 4 /* x value */
    #define YVAL 4 /* y value */
    #define ZVAL 4 /* z value */
    #define LEAF 128 /* leaf node */
    #define INTL 256 /* internal node */
    /*
    * 1---5
    * /| /|
    * 0---4 |
    * | 3-|-7
    * |/ |/
    * 2---6
    */
    enum ot_parts
    {
    TFL, /* TOP FRONT LEFT */
    TFR, /* TOP FRONT RIGHT */
    TBL, /* TOP BACK LEFT */
    TBR, /* TOP BACK RIGHT */
    BFL, /* BOTTOM FRONT LEFT */
    BFR, /* BOTTOM FRONT RIGHT */
    BBL, /* BOTTOM BACK LEFT */
    BBR /* BOTTOM BACK RIGHT */
    };
    class ot_node_class
    {
    public:
    ushort index;
    uchar value;
    ot_node_class **child;
    ot_node_class(int ntype)
    {
    index = 0;
    value = 0;
    if (ntype == LEAF) /* node type */
    {
    child = NULL;
    }
    else
    {
    child = new ot_node_class*[8];
    child[TFL] = NULL; child[ =
    child[TFR] = NULL; BBL] NUL
    child[TBL] = NULL; = L;
    child[TBR] = NULL; NULL; }
    child[BFL] = NULL; child[ }
    child[BFR] = NULL; BBR]
    ~ot_node_class()
    {
    if (child)
    {
    delete child[TFL];
    delete child[TFR];
    delete child[TBL];
    delete child[TBR];
    delete child[BFL];
    delete child[BFR];
    delete child[BBL];
    delete child[BBR];
    }
    }
    void ot_print()
    {
    printf(" %2d\t", value);
    }
    uchar avg_child(); /* average child */
    };
    uchar ot_node_class::avg_child() /* average child */
    {
    if (child)
    {
    ushort tmp = 0;
    for (int i = 0; i < 8; i++)
    {
    tmp += (ushort)child[i];
    }
    return (uchar)(tmp /= 8);
    }
    return 0;
    }
    class data_array_class
    {
    public:
    uchar data[XVAL][YVAL][ZVAL];
    data_array_class() { }
    ~data_array_class() { }
    void read_data();
    ot_node_class *buildtree(int xpt = 0, };
    int ypt = 0,
    int zpt = 0,
    int len = XVAL);
    void data_array_class::read_data()
    {
    for (int i = 0; i < ZVAL; i++)
    {
    for (int j = 0; j < YVAL; j++)
    {
    for (int k = 0; k < XVAL; k++)
    {
    data[k][j][i] = rand() % 100;
    printf(" [%d-%d-%d]:%2d\t", k, j, i, data[k][j][i]);
    }
    }
    }
    putchar('\n');
    }
    ot_node_class* data_array_class::buildtree(int xpt, int ypt, int
    zpt, int len)
    {
    ot_node_class *parent;
    if (len == 1)
    {
    parent = new ot_node_class(LEAF);
    parent->value = data[xpt][ypt][zpt];
    return parent;
    }
    parent = new ot_node_class(INTL);
    parent->child[TFL] = buildtree(xpt, ypt, zpt, len/2);
    parent->child[TFR] = buildtree(xpt, ypt, zpt+len/2, len/2);
    parent->child[TBL] = buildtree(xpt, ypt+len/2, zpt, len/2);
    parent->child[TBR] = buildtree(xpt, ypt+len/2, zpt+len/2,
    len/2);
    parent->child[BFL] = buildtree(xpt+len/2, ypt, zpt, len/2);
    parent->child[BFR] = buildtree(xpt+len/2, ypt, zpt+len/2,
    len/2);
    parent->child[BBL] = buildtree(xpt+len/2, ypt+len/2, zpt,
    len/2);
    parent->child[BBR] = buildtree(xpt+len/2, ypt+len/2,
    zpt+len/2, len/2);
    parent->value = parent->avg_child();
    return parent;
    }
    class octree_class
    {
    public:
    ot_node_class *root;
    octree_class(ot_node_class *otree)
    {
    root = otree;
    }
    ~octree_class()
    {
    delete root;
    }
    void depth_traversal(ot_node_class *recur_root =
    NULL,
    char *octnode_fun = "ot_print");
    };
    void octree_class::depth_traversal(ot_node_class
    *recur_root,
    char *octnode_fun)
    {
    if (recur_root == NULL)
    {
    return;
    }
    if (!(recur_root->child))
    {
    if(!(strcmp(octnode_fun, "ot_print")))
    {
    recur_root->ot_print();
    }
    return;
    }
    for (int i = 0; i < 8; i++) }
    {
    depth_traversal(recur_root->child[i], octnode_fun); }
    int main()
    {
    data_array_class dataobj;
    clrscr();
    printf("\n Implementing Octree \n");
    printf("\n Reading three dimensional random data... \n");
    dataobj.read_data();
    printf("\n Building Octree using three dimensional random data... \n");
    octree_class otobj(dataobj.buildtree());
    printf("\n Depth Traversing Octree... \n");
    printf(" Octree nodes are : \n");
    otobj.depth_traversal(otobj.root, "ot_print");
    putchar('\n');
    getch();
    return 0;
    }
    Output: Implementing Octree
    Reading three dimensional random data...
    [0-0-0]:46 [1-0-0]:30 [2-0-0]:82 [3-0-0]:90 [0-1-0]:56
    [1-1-0]:17 [2-1-0]:95 [3-1-0]:15 [0-2-0]:48 [1-2-0]:26
    [2-2-0]: 4 [3-2-0]:58 [0-3-0]:71 [1-3-0]:79 [2-3-0]:92
    [3-3-0]:60 [0-0-1]:12 [1-0-1]:21 [2-0-1]:63 [3-0-1]:47
    [0-1-1]:19 [1-1-1]:41 [2-1-1]:90 [3-1-1]:85 [0-2-1]:14
    [1-2-1]: 9 [2-2-1]:52 [3-2-1]:71 [0-3-1]:79 [1-3-1]:16
    [2-3-1]:81 [3-3-1]:51 [0-0-2]:95 [1-0-2]:93 [2-0-2]:34
    [3-0-2]:10 [0-1-2]:79 [1-1-2]:95 [2-1-2]:61 [3-1-2]:92
    [0-2-2]:89 [1-2-2]:88 [2-2-2]:66 [3-2-2]:64 [0-3-2]:92
    [1-3-2]:63 [2-3-2]:66 [3-3-2]:64 [0-0-3]:39 [1-0-3]:51
    [2-0-3]:27 [3-0-3]: 0 [0-1-3]:95 [1-1-3]:12 [2-1-3]: 8
    [3-1-3]:66 [0-2-3]:47 [1-2-3]:42 [2-2-3]:74 [3-2-3]:69
    [0-3-3]:89 [1-3-3]:83 [2-3-3]:66 [3-3-3]:41
    Building Octree using three dimensional random data...
    Depth Traversing Octree...
    Octree nodes are :
    46 12 56 19 30 21 17 41 95 39
    79 95 93 51 95 12 48 14 71 79
    26 9 79 16 89 47 92 89 88 42
    63 83 82 63 95 90 90 47 15 85
    34 27 61 8 10 0 92 66 4 52
    92 81 58 71 60 51 66 74 66 66
    64 69 64 41

    You might also like