---

r_octree.cpp

Go to the documentation of this file.

// OMICRON ENGINE HEADER FILE
//
// --------------------------------------------------------------------------
// Copyright (C) 2001-2002 by Bjoern Paetzel <kolrabi@gmx.de>
//
// This file is part of the Omicron Engine.
//
// The Omicron Engine is free software; you can redistribute it and/or modify
// it under the terms of the  GNU General Public License  as published by the
// Free Software Foundation;  either version  2  of the License,  or (at your
// option) any later version.
//
// The Omicron Engine  is distributed in the hope that it will be useful, but
// WITHOUT ANY WARRANTY; without even the implied warranty of MERCHANTABILITY
// or  FITNESS FOR A PARTICULAR PURPOSE.  See the  GNU General Public License
// for more details.
//
// You should have  received a copy of the  GNU General Public License  along
// with The Omicron Engine;  if not,  write to the  Free Software Foundation,
// Inc., 59 Temple Place, Suite 330, Boston, MA  02111-1307  USA 
//
// --------------------------------------------------------------------------
// Last modified:       $Date: 2002/12/07 19:02:04 $
// By           :       $Author: kolrabi $
// $Id: r_octree.cpp,v 1.1.1.1 2002/12/07 19:02:04 kolrabi Exp $ 

/*

  $Log: r_octree.cpp,v $
  Revision 1.1.1.1  2002/12/07 19:02:04  kolrabi
  initial release


*/

#include            "omicron/internal.h"
#include            "omicron/list.h"
#include            "omicron/octree.h"
#include            "omicron/input.h"
#include            "omicron/array.h"
#include            "omicron/render.h"

#define             BIGPOLY             100000

template <class T>
octree_c<T>::octree_c() 
{ 
    for (ulong i=0; i<8; i++)
        root.subnodes[i] = NULL;
    
    root.data = NULL;
} 

template <class T>
octree_c<T>::~octree_c() 
{
    AssertThis;
    
    for (ulong i=0; i<8; i++)
        removenode(root.subnodes[i]);
} 

template <class T>
octree_c<T>::node_t<T> *octree_c<T>::create_node(octree_c::node_t<T> *node, ulong num)
{
    AssertThisV;
    
    ulong i;
    if (!node->subnodes[num])
    {
        node->subnodes[num] = new octree_c::node_t<T>;
        
        vec3_t size;
        
        vector_subtract(node->max, node->min, size);
        vector_scale(size, 0.5, size);
        
        vector_copy(node->min, node->subnodes[num]->min);
        
        for (i=0; i<3; i++)
            if (num && (1<<i))
                node->subnodes[num]->min[i]+=size[i];
            
            for (i=0; i<8; i++)
                node->subnodes[num]->subnodes[i] = NULL;
            
            node->subnodes[num]->data = NULL;
            
            vector_add(node->subnodes[num]->min, size, node->subnodes[num]->max);
            
            for (i=0; i<8; i++)
            {
                node->subnodes[num]->pts[i][0] = 
                    (i&1)?node->subnodes[num]->max[0]:node->subnodes[num]->min[0];
                
                node->subnodes[num]->pts[i][1] = 
                    (i&2)?node->subnodes[num]->max[1]:node->subnodes[num]->min[1];
                
                node->subnodes[num]->pts[i][2] = 
                    (i&4)?node->subnodes[num]->max[2]:node->subnodes[num]->min[2];
            }
    }
    
    return node->subnodes[num];
}

template <class T>
slong octree_c<T>::get_subnode_num_vec(octree_c::node_t<T> *node, vec3_t p)
{
    AssertThisV;
    
    ulong  num = 0;
    vec3_t center;
    
    vector_add(node->max, node->min, center);
    vector_scale(center, 0.5, center);
    
    for (ulong i=0; i<3; i++)
    {
        if (p[i]>=center[i])
            num |= 1<<i;
    }
    
    return num;
}

template <class T>
slong octree_c<T>::get_subnode_num(octree_c::node_t<T> *node, vec3_t mn, vec3_t mx)
{
    AssertThisV;
    
    ulong    num, lnum, i;
    vec3_t   pts[8];
    
    for (i=0; i<8; i++)
    {
        pts[i][0] = (i&1)?mx[0]:mn[0];
        pts[i][1] = (i&2)?mx[1]:mn[1];
        pts[i][2] = (i&4)?mx[2]:mn[2];
    }
    
    lnum = num = getsubnodenumvec(node, pts[0]);
    
    for (i=1; i<8; i++)
    {
        num = getsubnodenumvec(node, pts[i]);
        if (lnum != num)
            return -1;
    }
    
    return num;
}

template <class T>
void octree_c<T>::add_to_subnode(octree_c::node_t<T> *node, T *d, vec3_t mn, vec3_t mx)
{
    AssertThis;
    
    ulong num;
    
    num = getsubnodenum(node, mn, mx);
    
    if (num == -1)
    {
        if (!node->data)
            node->data = new list_c<T>;
        
        node->data->add_first(d);
    }
    else
    {
        createnode(node, num);
        addtosubnode(node->subnodes[num], d, mn, mx);
    }
}

template <class T>
void octree_c<T>::add(T *d, vec3_t mn, vec3_t mx)
{
    AssertThis;
    
    add_to_subnode(&root, d, mn, mx);
}

template <class T>
void octree_c<T>::update_view()
{
    AssertThis;
    
    /*viewplanes[0].d = vector_dot(gv.viewPos, gv.viewDir);
    vector_copy(gv.viewDir, viewplanes[0].n);*/
    
    vec3_t     pts[5];
    vec3_t     f,r,u;
    ulong       i;
    float       rpf;
    
    for (i=0; i<5; i++)
        vector_copy(gv.renderer->get_viewpos(), pts[i]);
    
    rpf = ftan(gv.renderer->get_fov()/2)*2500;
    
    vector_scale(gv.renderer->get_viewdir(),   5000, f);
    vector_scale(gv.renderer->get_viewright(), rpf,  r);
    vector_scale(gv.renderer->get_viewup2(),   rpf,  u);
    
    for (i=1; i<5; i++)
        vector_add(pts[i], f, pts[i]);
    
    vector_ma(pts[1], -1, r, pts[1]);
    vector_ma(pts[1], -1, u, pts[1]);
    
    vector_ma(pts[2],  1, r, pts[2]);
    vector_ma(pts[2], -1, u, pts[2]);
    
    vector_ma(pts[3],  1, r, pts[3]);
    vector_ma(pts[3],  1, u, pts[3]);
    
    vector_ma(pts[4], -1, r, pts[4]);
    vector_ma(pts[4],  1, u, pts[4]);
    
    vector_set(viewmin,  BIGPOLY,  BIGPOLY,  BIGPOLY);
    vector_set(viewmax, -BIGPOLY, -BIGPOLY, -BIGPOLY);
    
    for (i=0; i<5; i++)
        for (ulong j=0; j<3; j++)
        {
            if (pts[i][j]>viewmax[j])
                viewmax[j] = pts[i][j];
            if (pts[i][j]<viewmin[j])
                viewmin[j] = pts[i][j];
        }
}

// 0 not
// 1 partially
// 2 complete
template <class T>
slong octree_c<T>::get_visibility(octree_c::node_t<T> *node)
{
    AssertThisV;
    
    ulong       visible;
    ulong       i, j, inside;
    
    if (node == &root)
        return 1;
    
    if ((gv.renderer->get_viewpos()[0]>node->min[0] && 
        gv.renderer->get_viewpos()[0]<node->max[0]) && 
        (gv.renderer->get_viewpos()[1]>node->min[1] && 
        gv.renderer->get_viewpos()[1]<node->max[1]) &&
        (gv.renderer->get_viewpos()[2]>node->min[2] && 
        gv.renderer->get_viewpos()[2]<node->max[2]))
    {
        return 1;
    }
    
    visible = 0;
    
    inside = 1;
    for (i=0; i<3; i++)
    {
        if (node->pts[0][i]>viewmax[i] && node->pts[0][i]<viewmin[i])
            inside = 0;
    }
    
    for (j=0; j<8; j++)
        for (i=0; i<3; i++)
        {
            if (node->pts[j][i]>viewmax[i] && node->pts[j][i]<viewmin[i])
            {
                if (inside)
                    return 1;
            }
            else
            {
                if (!inside)
                    return 1;
            }
        }
        
        if (inside)
            return 2;
        
        return 0;
}

template <class T>
void octree_c<T>::add_complete_node_to_array(octree_c::node_t<T> *node, array_c<T> &list)
{
    AssertThis;
    
    ulong i;
    
    if (!node)
        return;
    
    if (node->data)
    {
        ulong c = node->data->getcount();
        T *data = node->data->getfirst();
        
        while (data)
        {
            list.add(data);
            data = node->data->getnext();
        }
    }
    
    for (i=0; i<8; i++)
        addcompletenodetolist(node->subnodes[i], list);
}

template <class T>
void octree_c<T>::add_node_to_array(octree_c::node_t<T> *node, array_c<T> &list)
{
    AssertThis;
    
    if (!node)
        return;
    
    ulong vis = getvisibility(node);
    
    if (!vis)
        return;
    
    if (vis==1)
    {
        if (node->data)
        {
            T *data = node->data->getfirst();
            
            while (data)
            {
                list.add(data);
                data = node->data->getnext();
            }
        }
        
        for (ulong i=0; i<8; i++)
            addnodetolist(node->subnodes[i], list);
        
        return;
    }
    addcompletenodetolist(node, list);
}

template <class T>
void octree_c<T>::get_visible(array_c<T> &list)
{
    AssertThis;
    
    list.clear();
    addnodetolist(&root, list);
}

template <class T>
void octree_c<T>::remove_node(octree_c::node_t<T> *node)
{
    AssertThis;
    
    if (!node)
        return;
    
    for (ulong i=0; i<8; i++)
        removenode(node->subnodes[i]);
    
    SafeDelete(node->data);
    SafeDelete(node);
}

---