← Back to branch summary

~ubuntu-branches/ubuntu/gutsy/blender/gutsy-security

« back to all changes in this revision

Viewing changes to source/gameengine/SceneGraph/SG_Tree.h

  • Committer: Bazaar Package Importer
  • Author(s): Florian Ernst
  • Date: 2005-11-06 12:40:03 UTC
  • mfrom: (1.1.2 upstream)
  • Revision ID: james.westby@ubuntu.com-20051106124003-3pgs7tcg5rox96xg
Tags: 2.37a-1.1
http://bugs.debian.org/333958
* Non-maintainer upload.
* Split out parts of 01_SConstruct_debian.dpatch again: root_build_dir
  really needs to get adjusted before the clean target runs - closes: #333958,
  see #288882 for reference

Show diffs side-by-side

added added

removed removed

Lines of Context:
source/gameengine/SceneGraph/SG_Tree.h
 
1
/**
 
2
 * $Id: SG_Tree.h,v 1.2 2004/05/21 09:21:15 kester Exp $
 
3
 *
 
4
 * ***** BEGIN GPL/BL DUAL LICENSE BLOCK *****
 
5
 *
 
6
 * This program is free software; you can redistribute it and/or
 
7
 * modify it under the terms of the GNU General Public License
 
8
 * as published by the Free Software Foundation; either version 2
 
9
 * of the License, or (at your option) any later version. The Blender
 
10
 * Foundation also sells licenses for use in proprietary software under
 
11
 * the Blender License.  See http://www.blender.org/BL/ for information
 
12
 * about this.
 
13
 *
 
14
 * This program is distributed in the hope that it will be useful,
 
15
 * but WITHOUT ANY WARRANTY; without even the implied warranty of
 
16
 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
 
17
 * GNU General Public License for more details.
 
18
 *
 
19
 * You should have received a copy of the GNU General Public License
 
20
 * along with this program; if not, write to the Free Software Foundation,
 
21
 * Inc., 59 Temple Place - Suite 330, Boston, MA  02111-1307, USA.
 
22
 *
 
23
 * The Original Code is Copyright (C) 2001-2002 by NaN Holding BV.
 
24
 * All rights reserved.
 
25
 *
 
26
 * The Original Code is: all of this file.
 
27
 *
 
28
 * Contributor(s): none yet.
 
29
 *
 
30
 * ***** END GPL/BL DUAL LICENSE BLOCK *****
 
31
 * Bounding Box
 
32
 */
 
33
 
 
34
#ifndef __SG_TREE_H__
 
35
#define __SG_TREE_H__
 
36
 
 
37
#include "MT_Point3.h"
 
38
#include "SG_BBox.h"
 
39
 
 
40
#include <set> 
 
41
 
 
42
class SG_Node;
 
43
 
 
44
 
 
45
/**
 
46
 * SG_Tree.
 
47
 * Holds a binary tree of SG_Nodes.
 
48
 */
 
49
class SG_Tree 
 
50
{
 
51
        SG_Tree* m_left;
 
52
        SG_Tree* m_right;
 
53
        SG_Tree* m_parent;
 
54
        SG_BBox  m_bbox;
 
55
        MT_Point3 m_centre;
 
56
        MT_Scalar m_radius;
 
57
        SG_Node* m_client_object;
 
58
public:
 
59
        SG_Tree();
 
60
        SG_Tree(SG_Tree* left, SG_Tree* right);
 
61
        
 
62
        SG_Tree(SG_Node* client);
 
63
        ~SG_Tree();
 
64
        
 
65
        /**
 
66
         * Computes the volume of the bounding box.
 
67
         */
 
68
        MT_Scalar volume() const;
 
69
        
 
70
        /**
 
71
         * Prints the tree (for debugging.)
 
72
         */
 
73
        void dump() const;
 
74
        
 
75
        /**
 
76
         * Returns the left node.
 
77
         */
 
78
        SG_Tree *Left() const;
 
79
        SG_Tree *Right() const;
 
80
        SG_Node *Client() const;
 
81
        
 
82
        SG_Tree* Find(SG_Node *node);
 
83
        /**
 
84
         * Gets the eight corners of this treenode's bounding box,
 
85
         * in world coordinates.
 
86
         * @param box: an array of 8 MT_Point3
 
87
         * @example MT_Point3 box[8];
 
88
         *          treenode->get(box);
 
89
         */
 
90
        void get(MT_Point3 *box) const;
 
91
        /**
 
92
         * Get the tree node's bounding box.
 
93
         */
 
94
        const SG_BBox& BBox() const;
 
95
        
 
96
        /**
 
97
         * Test if the given bounding box is inside this bounding box.
 
98
         */
 
99
        bool inside(const MT_Point3 &point) const;
 
100
        
 
101
        void SetLeft(SG_Tree *left);
 
102
        void SetRight(SG_Tree *right);
 
103
 
 
104
        MT_Point3 Centre() const { return m_centre; }
 
105
        MT_Scalar Radius() { return m_radius; }
 
106
        
 
107
        //friend class SG_TreeFactory;
 
108
        
 
109
        struct greater
 
110
        {
 
111
                bool operator()(const SG_Tree *a, const SG_Tree *b)
 
112
                {
 
113
                        return a->volume() > b->volume();
 
114
                }
 
115
        };
 
116
        
 
117
};
 
118
 
 
119
 
 
120
/**
 
121
 *  SG_TreeFactory generates an SG_Tree from a list of SG_Nodes.
 
122
 *  It joins pairs of SG_Nodes to minimise the size of the resultant
 
123
 *  bounding box.
 
124
 *  cf building an optimised Huffman tree.
 
125
 *  @warning O(n^3)!!!
 
126
 */
 
127
class SG_TreeFactory 
 
128
{
 
129
        typedef std::multiset<SG_Tree*, SG_Tree::greater> TreeSet;
 
130
        TreeSet m_objects;
 
131
public:
 
132
        SG_TreeFactory();
 
133
        ~SG_TreeFactory();
 
134
        
 
135
        /**
 
136
         *  Add a node to be added to the tree.
 
137
         */
 
138
        void Add(SG_Node* client);
 
139
        void Add(SG_Tree* tree);
 
140
 
 
141
        /**
 
142
         *  Build the tree from the set of nodes added by
 
143
         *  the Add method.
 
144
         */
 
145
        SG_Tree* MakeTreeUp();
 
146
        
 
147
        /**
 
148
         *  Build the tree from the set of nodes top down.
 
149
         */
 
150
        SG_Tree* MakeTreeDown(SG_BBox &bbox);
 
151
        
 
152
        SG_Tree* MakeTree();
 
153
        
 
154
};
 
155
 
 
156
#endif /* __SG_BBOX_H__ */