octree.cpp

Go to the documentation of this file.

/*
    toxic - A Global Illumination Renderer
    Copyright (C) 2003-2004 Francois Beaune
    Contact: http://toxicengine.sourceforge.net/

    This file is part of toxic.

    toxic 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.

    toxic 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 toxic; if not, write to the Free Software
    Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA  02111-1307  USA
*/

#include "octree.h" // include first
#include "common/math/real.h"
#include "common/math/vector3.h"
#include "common/math/vector4.h"
#include "context.h"
#include "ray.h"

#include <cassert>
#include <limits>

using namespace sheep;
using namespace std;
using namespace toxic;

toxic::Octree::Octree(const Matrix4 &m,
                      int pop_threshold /*= DEFAULT_OCTREE_POP_THRESHOLD*/,
                      int max_subdiv /*= DEFAULT_OCTREE_MAX_SUBDIV*/,
                      IntersectionMask intersection_mask /*= INTERSECT_ALL_RAYS*/) :
    IBoundedObject(m, 0, intersection_mask),
    m_object_count(0),
    m_pop_threshold(pop_threshold),
    m_max_subdiv(max_subdiv),
    m_octree(0)
{
}

toxic::Octree::~Octree() {
    for(object_vector_const_it i = m_objects.begin(), e = m_objects.end(); i != e; ++i) {
        delete *i;
    }

    delete m_octree;
}

void toxic::Octree::Insert(IBoundedObject *object) {
    assert(object);
    m_objects.push_back(object);
}

void toxic::Octree::Finalize(const Context &context) {
    m_object_count = 0;

    for(object_vector_const_it i = m_objects.begin(), e = m_objects.end(); i != e; ++i) {
        IObject *child = *i;

        child->Finalize(context);

        m_object_count += child->GetObjectCount();
    }

    // Minimum number of objects to use an octree.
    const int OBJECTS_THRESHOLD = 8;

    if(m_objects.size() >= OBJECTS_THRESHOLD) {
        m_octree = new octree();

        for(object_vector_const_it i = m_objects.begin(), e = m_objects.end(); i != e; ++i) {
            m_octree->Insert(*i, (*i)->GetAABB());
        }

        object_voxel_intersector ovi;
        m_octree->Subdivide(m_pop_threshold, m_max_subdiv, ovi);

        //!\todo This is probably incorrect...
        m_aabb = m_octree->GetAABB().Transform(m_m);
    } else {
        assert(m_octree == 0);

        // Compute AABB from objects.
        m_aabb.Invalidate();
        for(object_vector_const_it i = m_objects.begin(), e = m_objects.end(); i != e; ++i) {
            m_aabb.Include((*i)->GetAABB());
        }
    }

    // It is not necessary to widen the box of an octree.
}

Real toxic::Octree::ComputeSurfaceArea() const {
    //!\todo Implement.
    assert(!"Not implemented yet.");
    return 0.0;
}

void toxic::Octree::EvaluateSurface(const Point2 &input,
                                    Point3 *point,
                                    Vector3 *geometric_normal) const
{
    assert(point);
    assert(geometric_normal);

    //!\todo Implement.
    assert(!"Not implemented yet.");
}

bool toxic::Octree::Intersect(const Context &context,
                              const Ray &ray,   //!< 'ray' is expressed in world space.
                              Hit *hit /*= 0*/) const
{
    // Test whether this object intersects with this type of ray.
    if(!(m_intersection_mask & ray.GetType()))
        return false;

    //!\todo Handle octree transformation.

    if(m_octree) {
        if(hit) {
            octree_full_visitor visitor(context, ray);

            assert(m_octree);
            m_octree->Trace(ray.m_origin, ray.m_direction, visitor);

            if(visitor.m_nearest.m_abscissa < std::numeric_limits<Real>::max()) {
                *hit = visitor.m_nearest;
                return true;
            } else return false;
        } else {
            octree_test_visitor visitor(context, ray);

            assert(m_octree);
            m_octree->Trace(ray.m_origin, ray.m_direction, visitor);

            return visitor.m_found;
        }
    } else {
        if(hit) {
            Hit nearest;

            nearest.m_abscissa = std::numeric_limits<Real>::max();

            for(object_vector_const_it i = m_objects.begin(), e = m_objects.end(); i != e; ++i) {
                const IBoundedObject *object = *i;
                Hit h;

                if(object->Intersect(context, ray, &h)) {
                    if(h.m_abscissa < nearest.m_abscissa)
                        nearest = h;
                }
            }

            if(nearest.m_abscissa < std::numeric_limits<Real>::max()) {
                *hit = nearest;
                return true;
            } else return false;
        } else {
            for(object_vector_const_it i = m_objects.begin(), e = m_objects.end(); i != e; ++i) {
                const IBoundedObject *object = *i;

                if(object->Intersect(context, ray))
                    return true;
            }

            return false;
        }
    }
}

void toxic::Octree::Annotate(const Context &context,
                             const ICamera *camera,
                             Framebuffer *framebuffer) const
{
    for(object_vector_const_it i = m_objects.begin(), e = m_objects.end(); i != e; ++i) {
        (*i)->Annotate(context, camera, framebuffer);
    }
}

inline
bool toxic::Octree::object_voxel_intersector::Intersect(const IBoundedObject *object,
                                                        const AABB3 &voxel) const
{
    assert(object);
    return object->GetAABB().Overlaps(voxel);
}

inline
toxic::Octree::octree_test_visitor::octree_test_visitor(const Context &context,
                                                        const Ray &ray) :
    m_context(context),
    m_ray(ray),
    m_found(false)
{
}

bool toxic::Octree::octree_test_visitor::Trace(const octree_node *node,
                                               Real /*t0*/, Real /*t1*/)
{
    assert(node);

    for(octree_node::ItemVectorConstIt i = node->m_items.begin(), e = node->m_items.end(); i != e; ++i) {
        if((*i)->Intersect(m_context, m_ray)) {
            m_found = true;
            return true;    // terminate octree traversal
        }
    }

    return false;   // continue octree traversal
}

inline
toxic::Octree::octree_full_visitor::octree_full_visitor(const Context &context,
                                                        const Ray &ray) :
    m_context(context),
    m_ray(ray)
{
    m_nearest.m_abscissa = std::numeric_limits<Real>::max();
}

bool toxic::Octree::octree_full_visitor::Trace(const octree_node *node,
                                               Real t0, Real t1)
{
    assert(node);

    for(octree_node::ItemVectorConstIt i = node->m_items.begin(), e = node->m_items.end(); i != e; ++i) {
        const IBoundedObject *object = *i;

#ifdef USE_MAILBOXES
        if(object->m_mailbox_ray_id != m_ray.GetId()) {
#endif  // USE_MAILBOXES
            Hit h;

            if(object->Intersect(m_context, m_ray, &h)) {
                if(h.m_abscissa < m_nearest.m_abscissa)
                    m_nearest = h;
            }

#ifdef USE_MAILBOXES
            object->m_mailbox_ray_id = m_ray.GetId();
        }
#endif  // USE_MAILBOXES
    }

    //!\todo Make sure the <= and >= are correct.
    if(m_nearest.m_abscissa >= t0 && m_nearest.m_abscissa <= t1)
        return true;    // terminate octree traversal
    else return false;  // continue octree traversal
}

---