octree.h

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
*/

#ifndef TOXIC_RENDERER_OCTREE_H
#define TOXIC_RENDERER_OCTREE_H

#include "common/math/aabb3.h"
#include "common/math/matrix4.h"
#include "common/math/octree.h"
#include "common/math/point2.h"
#include "common/math/point3.h"
#include "common/math/vector3.h"
#include "common/math/real.h"
#include "common/misc/minmax.h"
#include "globals.h"
#include "hit.h"
#include "iboundedobject.h"

#include <vector>

namespace toxic {

    class Context;
    class Framebuffer;
    class ICamera;
    class Ray;
    class Scene;

    const int DEFAULT_OCTREE_POP_THRESHOLD = 8;
    const int DEFAULT_OCTREE_MAX_SUBDIV = 6;    // at most 8^6 = 262,144 cells

    class Octree : public IBoundedObject {
    public:
        //! m is the object space to world space transformation matrix.
        Octree(
            const sheep::Matrix4 &m,
            int pop_threshold = DEFAULT_OCTREE_POP_THRESHOLD,
            int max_subdiv = DEFAULT_OCTREE_MAX_SUBDIV,
            IntersectionMask intersection_mask = INTERSECT_ALL_RAYS);

        //! An octree deletes its children when it is destructed.
        virtual ~Octree();

        void Insert(IBoundedObject *object);

        //! This method must be called only once, after the object is completely
        //! configured, and before it is used for the first time.
        virtual void Finalize(const Context &context);

        //! This method returns the number of objects contained into this object.
        //! For primitives, it returns 1. For composite objects (like the Collection
        //! object), it returns the number of child objects.
        virtual int GetObjectCount() const;

        //! Returns the Axis Aligned Bounding Box of this object. The AABB is
        //! expressed in world space.
        virtual const sheep::AABB3 &GetAABB() const;

        //! Computes the surface area of this object.
        virtual sheep::Real ComputeSurfaceArea() const;

        //! Given a point in the unit square (the set of points in [0..1]^2),
        //! this method computes the corresponding surface point and normal
        //! (both are expressed in world space).
        virtual void EvaluateSurface(
            const sheep::Point2 &input,
            sheep::Point3 *point,
            sheep::Vector3 *geometric_normal
        ) const;

        //! This method returns true if the ray intersect the object, or false otherwise.
        //! If 'hit' is not null, intersection data are reported through the 'hit' parameter
        //! (only if an intersection has been found; if no intersection has been found, the
        //! 'hit' parameter is left unchanged). The ray is expressed in world space.
        virtual bool Intersect(
            const Context &context,
            const Ray &ray,
            Hit *hit = 0
        ) const;

        virtual void Annotate(
            const Context &context,
            const ICamera *camera,
            Framebuffer *framebuffer
        ) const;

    private:
        typedef std::vector<IBoundedObject *> object_vector;
        typedef object_vector::const_iterator object_vector_const_it;

        typedef sheep::OctreeNode<const IBoundedObject *> octree_node;
        typedef sheep::Octree<const IBoundedObject *> octree;

        struct object_voxel_intersector {
            bool Intersect(const IBoundedObject *object, const sheep::AABB3 &voxel) const;
        };

        //! This visitor is invoked by the Octree::Intersect() method when the hit
        //! parameter is 0 (null). It is aimed at testing whether the ray touches
        //! an object in the octree or not. It does not search for the nearest
        //! object and it does not compute the intersection distance.
        struct octree_test_visitor {
            const Context &m_context;
            const Ray &m_ray;
            bool m_found;

            octree_test_visitor(const Context &context, const Ray &ray);

            bool Trace(const octree_node *node, sheep::Real t0, sheep::Real t1);
        };

        //! This visitor is invoked by the Octree::Intersect() method when the hit
        //! parameter is not null. It does search for the nearest intersected
        //! object and it does report the intersection distance.
        struct octree_full_visitor {
            const Context &m_context;
            const Ray &m_ray;
            Hit m_nearest;

            octree_full_visitor(const Context &context, const Ray &ray);

            bool Trace(const octree_node *node, sheep::Real t0, sheep::Real t1);
        };

        object_vector m_objects;
        int m_object_count; //!< Number of child objects. Computed by the Finalize() method.

        //! Octree parameters.
        int m_pop_threshold;
        int m_max_subdiv;

        octree *m_octree;       //!< Used only if the octree contains enough objects.

        sheep::AABB3 m_aabb;    //!< Bounding box of the object, expressed in world space.
    };

#include "octree.inl"

}

#endif  // !TOXIC_RENDERER_OCTREE_H

---