kdtree.h

Go to the documentation of this file.

/*
 * kdtree.h
 * 
 * Copyright (C) 2009  Thomas A. Vaughan
 * All rights reserved.
 *
 *
 * Redistribution and use in source and binary forms, with or without
 * modification, are permitted provided that the following conditions are met:
 *     * Redistributions of source code must retain the above copyright
 *       notice, this list of conditions and the following disclaimer.
 *     * Redistributions in binary form must reproduce the above copyright
 *       notice, this list of conditions and the following disclaimer in the
 *       documentation and/or other materials provided with the distribution.
 *     * Neither the name of the <organization> nor the
 *       names of its contributors may be used to endorse or promote products
 *       derived from this software without specific prior written permission.
 *
 * THIS SOFTWARE IS PROVIDED BY THOMAS A. VAUGHAN ''AS IS'' AND ANY
 * EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED
 * WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE
 * DISCLAIMED. IN NO EVENT SHALL THOMAS A. VAUGHAN BE LIABLE FOR ANY
 * DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES
 * (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES;
 * LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND
 * ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
 * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS
 * SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
 *
 *
 * Simple kd-tree library.h
 */

#ifndef WAVEPACKET_KDTREE_H__
#define WAVEPACKET_KDTREE_H__


// includes --------------------------------------------------------------------
#include "common/common.h"
#include "geometry/geometry_3d.h"
#include "threadsafe/smart_ptr.h"


/// \ingroup geometric
/*@{*/

////////////////////////////////////////////////////////////////////////////////
///
/// \defgroup kdtree kd-tree Library
///
/// \n
/// API for creating kd trees.  Only supports 3D for now.
/// See http://en.wikipedia.org/wiki/Kd-tree
///
/// \n
/// This library is optimized for use caess where a lot of objects are added
/// and only a few are removed.  In particular, the tree isn't rebalanced nor
/// are empty nodes removed.
///
/// \n
/// \b WARNING: This API is \e not threadsafe.
///
////////////////////////////////////////////////////////////////////////////////

/*@{*/


namespace kdtree {


// basic sorting (move this to geometry library?)
enum eSort {
        eSort_Left      = 1, ///< "left" of sort plane, negative distance
        eSort_Right     = 2, ///< "right" of sort plane, positive distance
        eSort_Straddle  = 3, ///< in sort plane, or spans both sides

        // keep this last!
        eSort_Invalid   = 0
};



enum eAxis {
        eAxis_X         = 1,
        eAxis_Y         = 2,
        eAxis_Z         = 3,

        // keep this last!
        eAxis_Invalid   = 0
};


/// a kdtree plane is always axis-aligned
struct plane_t {
        void clear(void) throw() {
                        axis = eAxis_Invalid;
                        value = 0.0;
                }
        bool isValid(void) const throw() { return (axis > 0 && axis < 4); }
        void dump(IN const char * title) const throw() {
                        DPRINTF("%s: axis[%d] value=%f", title, axis, value);
                }

        // data fields
        eAxis           axis;   ///< which axis is normal to this plane
        float           value;  ///< coordinate value along axis
};


/// say which side of a given sort plane the provided test point is on
eSort sortPoint(IN const plane_t& plane, IN const point3d_t& point) throw();


/// say how the given rectangle sorts against the given sorting plane
eSort sortRect(IN const plane_t& plane, IN const rect3d_t& rect) throw();


// forward declaration
class Node;


/// base class for kd-tree entries.  Clients can inherit from this.
class Entry {
public:
        // virtual destructor (main purpose of this class) ---------------------
        virtual ~Entry(void) throw();
};



enum eAction {
        eAction_Continue                = 0x001,        // keep iterating
        eAction_Halt                    = 0x002,        // stop iterating

        eAction_Remove                  = 0x010,        // remove this item

        eAction_Invalid                 = 0             // keep this last!
};


typedef eAction (*iteration_callback)(IN void * context,
                                IN Entry * entry,
                                IN const rect3d_t& entry_rect);


/// strategies used for space partitioning
enum eStrategy {
        eStrategy_Naive         =  1, ///< simple strategy based on bounding box
        eStrategy_Balance       =  2, ///< strategy that aims to balance nodes

        // keep this last!
        eStrategy_Invalid       =  0
};



/// root (and node!) of a kd-tree
/// This class is expected to be used as the core object for rendering and other
///     CPU-intensive tasks, so it therefore has no virtual methods.
class Node {
public:
        // public typedefs -----------------------------------------------------
        struct entry_rec_t {
                smart_ptr<Entry>        entry;
                rect3d_t                rect;
        };
        struct dynamic_entry_t {
                // data fields
                smart_ptr<Entry>        entry;
                rect3d_t                rect;
                smart_ptr<dynamic_entry_t> next;
        };

        typedef std::vector<entry_rec_t> vec_entries_t;

        // constructor, destructor ---------------------------------------------
        ~Node(void) throw();

        // kdtree::Node class interface methods --------------------------------

        /// static entries are expensive to add and remove--do so rarely (such
        ///     as when constructing the tree).
        void addStaticEntry(IN smart_ptr<Entry>& entry,
                                IN const rect3d_t& r);

        /// dynamic entries are fast to add and remove, but are not used for
        ///     partitioning and are not affected by subdividing.
        void addDynamicEntry(IN smart_ptr<dynamic_entry_t>& de);

        bool removeStaticEntry(IN Entry * entry) throw();
        smart_ptr<dynamic_entry_t> popDynamicEntry(void) throw();
        int getTreeDepth(void) const throw();
        int getNodeCount(void) const throw();
        int getStaticEntryCount(void) const throw();

        /// here you tell the kd-tree to subdivide (recursively), using the
        ///     given strategy.  The param use depends on the strategy.
        ///
        /// - For the naive strategy, the param is the max number of nodes per
        ///     entity.
        void subdivide(IN eStrategy strategy,
                                IN float param);

        /// client can iterate over all entries in the given rect
        eAction iterateStaticEntries(IN const rect3d_t& r,
                                IN iteration_callback callback,
                                IN void * context);

        // raw accessors for clients needing to walk directly
        const Node * getLeftChild(void) const throw() { return m_left; }
        const Node * getRightChild(void) const throw() { return m_right; }
        Node * getLeftChild(void) throw() { return m_left; }
        Node * getRightChild(void) throw() { return m_right; }

        const rect3d_t& getRect(void) const throw() { return m_bounds; }
        const plane_t& getSortPlane(void) const throw() { return m_sortPlane; }

        const vec_entries_t& getStaticEntries(void) const throw() { return m_entries; }
        vec_entries_t& getStaticEntries(void) throw() { return m_entries; }

        void setUserPointer(IN void * context) throw() { m_user = context; }
        void * getUserPointer(void) const throw() { return m_user; }

        // public static methods (factory methods) -----------------------------

        /// when you create a kd-tree node (especially the root!) you had better
        ///     know the overall boundaries.  Anything you add to the node must
        ///     be contained by these bounds.
        static smart_ptr<Node> create(IN const rect3d_t& bounds);

private:
        // require clients to use the public factory methods to create ---------
        Node(void) throw();

        // private helper methods ----------------------------------------------
        void initialize(IN const rect3d_t& bounds);
        void subdivideInternal(IN eStrategy strategy,
                                IN float param);

        // private member data -------------------------------------------------
        smart_ptr<Node> m_left; // left child (for some definition of "left")
        smart_ptr<Node> m_right;// right child
        plane_t         m_sortPlane;// left/right divide
        rect3d_t        m_bounds;// boundary
        vec_entries_t   m_entries; // unsorted or spanning entries
        smart_ptr<dynamic_entry_t> m_dynamic;   // dynamic entries
        void *          m_user; // user context
};



};      // kdtree namespace

#endif  // WAVEPACKET_KDTREE_H__