map-kdtree.h

Go to the documentation of this file.
00001 /*
00002  * map-kdtree.h
00003  *
00004  * Copyright (C) 2010  Thomas A. Vaughan
00005  * All rights reserved.
00006  *
00007  *
00008  * Redistribution and use in source and binary forms, with or without
00009  * modification, are permitted provided that the following conditions are met:
00010  *     * Redistributions of source code must retain the above copyright
00011  *       notice, this list of conditions and the following disclaimer.
00012  *     * Redistributions in binary form must reproduce the above copyright
00013  *       notice, this list of conditions and the following disclaimer in the
00014  *       documentation and/or other materials provided with the distribution.
00015  *     * Neither the name of the <organization> nor the
00016  *       names of its contributors may be used to endorse or promote products
00017  *       derived from this software without specific prior written permission.
00018  *
00019  * THIS SOFTWARE IS PROVIDED BY THOMAS A. VAUGHAN ''AS IS'' AND ANY
00020  * EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED
00021  * WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE
00022  * DISCLAIMED. IN NO EVENT SHALL THOMAS A. VAUGHAN BE LIABLE FOR ANY
00023  * DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES
00024  * (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES;
00025  * LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND
00026  * ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
00027  * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS
00028  * SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
00029  *
00030  */
00031 
00032 #ifndef AESOP_MAP_KDTREE_H__
00033 #define AESOP_MAP_KDTREE_H__
00034 
00035 
00036 // includes --------------------------------------------------------------------
00037 #include "glut/renderable.h"
00038 #include "map-dynamics/map-dynamics.h"
00039 #include "kdtree/kdtree.h"
00040 
00041 
00042 namespace aesop {
00043 
00044 
00045 ////////////////////////////////////////////////////////////////////////////////
00046 ///
00047 /// \ingroup aesop_map_mgmt
00048 /// \defgroup map_kdtree Map kd-Tree Library
00049 ///
00050 /// The MapKdTree class is used to help manage drawing aesop Maps and Zones (see
00051 /// aesop::Map and aesop::Zone).
00052 ///
00053 /// Internally, the MapKdTree maintains a kd-tree which provides efficient
00054 /// front-to-back traversal of all objects near the viewer within the view
00055 /// frustum.  The MapKdTree is also aware of zone visibility flags and will
00056 /// use that to optimize tree walking.  Furthermore, the MapKdTree is aware of
00057 /// virtual zones and will make objects in virtual leaf zones available for
00058 /// rendering if they should be visible.
00059 ///
00060 /// In general, when walking a large 3D scee for rendering, you should:
00061 ///  - walk from objects nearest the viewer to farthest (front-to-back)
00062 ///  - render each object in turn.
00063 ///  - push any transparent textures onto the glut::RequestQueue
00064 ///  - at the end of traversal, pop all transparent textures from the queue
00065 ///     so they render in back-to-front order.
00066 ///
00067 /// In addition, the MapKdTree class knows how to update dynamic objects it
00068 /// contains.  It will remove them and re-insert them at updated positions
00069 /// whenever you call MapKdTree::update().
00070 ///
00071 /// The goal is to make things easy for the client: when you have a MapDynamics
00072 /// object, create a MapKdTree object for it, and then you can use the MapKdTree
00073 /// to efficiently render everything in the map.  As a client, just call
00074 /// MapKdTree::walkFrontToBack() and you'll be given objects to render in the
00075 /// proper order (and these will only be objects within the view frustum and
00076 /// in zones visible to the viewer).
00077 ///
00078 ////////////////////////////////////////////////////////////////////////////////
00079 /*@{*/
00080 
00081 
00082 struct map_draw_stats_t {
00083         // constructor, manipulators
00084         map_draw_stats_t(void) throw() { this->clear(); }
00085         void clear(void) throw() {
00086                         nObjects = 0;
00087                 }
00088 
00089         // data fields
00090         int             nObjects;       ///< number of objects drawn
00091 };
00092 
00093 
00094 
00095 struct kd_node_t {
00096         rect3d_t        rect;
00097         int             depth;  ///< root-->depth=0, then increases
00098 };
00099 
00100 
00101 typedef void (*kdtree_callback_fn)(IN const kd_node_t& node,
00102                                 IN void * context);
00103 
00104 typedef void (*kdtree_object_fn)(IN glut::Renderable * model,
00105                                 IN const glut::render_context_t& rc,
00106                                 IN glut::RenderQueue * rq,
00107                                 IN void * context);
00108 
00109 
00110 /// top-level object that manages the full kd-tree
00111 class MapKdTree {
00112 public:
00113         // virtual destructor --------------------------------------------------
00114         virtual ~MapKdTree(void) throw();
00115 
00116         // aesop::MapKdTree class interface methods ----------------------------
00117 
00118         /// get the underlying MapDynamics object
00119         virtual MapDynamics * getMapDynamics(void) throw() = 0;
00120 
00121         /// visit all nodes in the tree in arbitrary order
00122         virtual void walkNodes(IN kdtree_callback_fn callback,
00123                                 IN void * context) = 0;
00124 
00125         /// visit all objects in the tree, walking front to back
00126         virtual void walkFrontToBack(IN const glut::render_context_t& rc,
00127                                         IN glut::RenderQueue * rq,
00128                                         IN kdtree_object_fn callback,
00129                                         IN void * context) = 0;
00130 
00131         // public static methods (factory methods) -----------------------------
00132         static smart_ptr<MapKdTree> create(IN smart_ptr<MapDynamics>& map);
00133 };
00134 
00135 
00136 
00137 /// helper method to draw a KdTree map.  Caller must provide an (empty)
00138 ///   glut::RenderQueue object, which this routine uses to render transparent
00139 ///   polygons.
00140 void drawMap(IN MapKdTree * mapKdTree,
00141                         IN const glut::render_context_t& rc,
00142                         IN glut::RenderQueue * rq,
00143                         OUT map_draw_stats_t& stats);
00144 
00145 
00146 
00147 };      // aesop namespace
00148 
00149 #endif  // AESOP_MAP_KDTREE_H__
00150