← Back to branch summary

~gimaker/peekabot/coord-sys-default

« back to all changes in this revision

Viewing changes to src/renderer/OctreeNode.cc

  • Committer: Staffan Gimåker
  • Date: 2009-06-29 10:09:26 UTC
  • mfrom: (665.1.39 renderer-redux)
  • Revision ID: staffan@gimaker.se-20090629100926-ju5kx8jwzy422rwu
Merged the renderer-redux branch.

This represents a major overhaul to the rendering engine, with a less contrived
design and better performance. Both memory and CPU utilization should be 
better in general.

Show diffs side-by-side

added added

removed removed

Lines of Context:
src/renderer/OctreeNode.cc
1
 
/*
2
 
 * This file is part of peekabot.
3
 
 *
4
 
 * peekabot is free software; you can redistribute it and/or modify
5
 
 * it under the terms of the GNU General Public License as published by
6
 
 * the Free Software Foundation; either version 2 of the License, or
7
 
 * (at your option) any later version.
8
 
 *
9
 
 * peekabot is distributed in the hope that it will be useful,
10
 
 * but WITHOUT ANY WARRANTY; without even the implied warranty of
11
 
 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
12
 
 * GNU General Public License for more details.
13
 
 *
14
 
 * You should have received a copy of the GNU General Public License
15
 
 * along with this program.  If not, see <http://www.gnu.org/licenses/>.
16
 
 */
17
 
 
18
 
 
19
 
/**
20
 
 * \brief \c OctreeNode class implementation.
21
 
 *
22
 
 * \todo Could benefit from clearer separation from \c Octree, i.e. by
23
 
 * adding dedicated methods for add/remove child nodes.
24
 
 */
25
 
 
26
 
#include <GL/glew.h>
27
 
#include <iostream>
28
 
#include <stack>
29
 
#include <cassert>
30
 
#include "Octree.hh"
31
 
#include "Cullable.hh"
32
 
#include "primitives/Camera.hh"
33
 
#include "OctreeTraverser.hh"
34
 
#include "Frustum.hh"
35
 
 
36
 
 
37
 
using namespace peekabot;
38
 
using namespace peekabot::renderer;
39
 
 
40
 
 
41
 
 
42
 
Octree::OctreeNode::OctreeNode(OctreeNode *parent,
43
 
                               real32 half_size,
44
 
                               const Vector3r &pos, 
45
 
                               const real32 &min_node_size) :
46
 
    m_half_size(half_size),
47
 
    m_pos(pos), 
48
 
    m_parent(parent), 
49
 
    m_enclosed(0),
50
 
    m_min_node_size(min_node_size),
51
 
    m_child_count(0)
52
 
{
53
 
    for( int i = 0; i < 8; i++ )
54
 
        m_children[i] = 0;
55
 
}
56
 
 
57
 
Octree::OctreeNode::~OctreeNode()
58
 
{
59
 
    for( int i = 0; i < 8; i++ )
60
 
        if( m_children[i] != 0 )
61
 
            delete m_children[i];
62
 
}
63
 
 
64
 
 
65
 
 
66
 
 
67
 
Octree::OctreeNode *Octree::OctreeNode::add_object(Cullable *obj) throw()
68
 
{
69
 
    // 1. It is enclosed by a child node and the minimum node size has not
70
 
    //    been reached.
71
 
    //    1.1. That child exists, do a recurisve add.
72
 
    //    1.2. It doesn't exist, create it and do a recursive add.
73
 
    // 2. Not enclosed by a child, add to this node.
74
 
 
75
 
    //assert(encloses(obj));
76
 
 
77
 
    ++m_enclosed;
78
 
 
79
 
    // Test for 2)
80
 
    if( obj->get_bounding_sphere().get_radius() <= m_half_size/2 &&
81
 
        m_half_size/2 > m_min_node_size )
82
 
    {
83
 
        // Add to child node
84
 
        for( int i = 0; i < 8; i++ )
85
 
        {      
86
 
            if( enclosed_in_octant(obj, i) )
87
 
            {
88
 
                if( m_children[i] == 0 )
89
 
                {
90
 
                    // invariant: m_half_size/2 > m_min_node_size
91
 
 
92
 
                    m_children[i] = new OctreeNode(
93
 
                        this, 
94
 
                        m_half_size / 2,
95
 
                        m_pos + octant_offset(i), 
96
 
                        m_min_node_size);
97
 
 
98
 
                    ++m_child_count;
99
 
                }
100
 
 
101
 
                return m_children[i]->add_object(obj);
102
 
            }
103
 
        }
104
 
 
105
 
        TheMessageHub::instance().publish(
106
 
            ERROR_MESSAGE,
107
 
            "Pending assertion failure! Object not enclosed in a child node, "
108
 
            "even though it should meet the requirements to do so. "
109
 
            "bounding sphere: pos=(%f, %f, %f), r=%f", 
110
 
            obj->get_bounding_sphere().get_pos()(0),
111
 
            obj->get_bounding_sphere().get_pos()(1),
112
 
            obj->get_bounding_sphere().get_pos()(2),
113
 
            obj->get_bounding_sphere().get_radius());
114
 
        
115
 
        assert(false); // Should never happend
116
 
    }
117
 
    else
118
 
    {
119
 
        m_contained_objects.insert(obj);
120
 
 
121
 
        return this;
122
 
    }
123
 
}
124
 
            
125
 
 
126
 
void Octree::OctreeNode::remove_object(Cullable *obj,
127
 
                                       bool update_enclosed_count) throw()
128
 
{
129
 
    assert(contains(obj));
130
 
 
131
 
    m_contained_objects.erase(obj);
132
 
    --m_enclosed;
133
 
 
134
 
    if( update_enclosed_count )
135
 
    {
136
 
        // Decrease enclosed count for ancestor nodes
137
 
        OctreeNode *parent = m_parent;
138
 
        while( parent != 0 )
139
 
        {
140
 
            --parent->m_enclosed;
141
 
 
142
 
            parent = parent->m_parent;
143
 
        }
144
 
    }
145
 
}
146
 
 
147
 
 
148
 
bool Octree::OctreeNode::encloses(Cullable *obj) const throw()
149
 
{
150
 
    if( obj->get_bounding_sphere().get_radius() > m_half_size )
151
 
        return false;
152
 
 
153
 
    real32 x = obj->get_bounding_sphere().get_pos()(0);
154
 
    real32 y = obj->get_bounding_sphere().get_pos()(1);
155
 
    real32 z = obj->get_bounding_sphere().get_pos()(2);
156
 
 
157
 
    if( x >= m_pos(0) - m_half_size/2 && x < m_pos(0) + m_half_size/2 &&
158
 
        y >= m_pos(1) - m_half_size/2 && y < m_pos(1) + m_half_size/2 &&
159
 
        z >= m_pos(2) - m_half_size/2 && z < m_pos(2) + m_half_size/2 )
160
 
    {
161
 
        return true;
162
 
    }
163
 
    else
164
 
        return false;
165
 
}
166
 
 
167
 
 
168
 
bool Octree::OctreeNode::enclosed_in_octant(Cullable *obj, 
169
 
                                            int octant) const throw()
170
 
{
171
 
    if( obj->get_bounding_sphere().get_radius() > m_half_size/2 )
172
 
        return false;
173
 
 
174
 
    real32 x = obj->get_bounding_sphere().get_pos()(0);
175
 
    real32 y = obj->get_bounding_sphere().get_pos()(1);
176
 
    real32 z = obj->get_bounding_sphere().get_pos()(2);
177
 
 
178
 
    return ( ( octant&1 ? x >= m_pos(0) : x < m_pos(0) ) && 
179
 
             ( octant&2 ? y >= m_pos(1) : y < m_pos(1) ) && 
180
 
             ( octant&4 ? z >= m_pos(2) : z < m_pos(2) ) );
181
 
}
182
 
 
183
 
 
184
 
bool Octree::OctreeNode::contains(const Cullable *obj) const throw()
185
 
{
186
 
    return m_contained_objects.find(const_cast<Cullable *>(obj)) 
187
 
        != m_contained_objects.end();
188
 
}
189
 
 
190
 
 
191
 
 
192
 
/*bool Octree::OctreeNode::is_empty() const throw()
193
 
{
194
 
    //assert(m_enclosed >= 0);
195
 
    
196
 
    return m_enclosed == 0;
197
 
}*/
198
 
 
199
 
 
200
 
 
201
 
Vector3r Octree::OctreeNode::octant_offset(int octant) const throw()
202
 
{
203
 
    real32 hs = m_half_size/4;
204
 
 
205
 
    return Vector3r( hs*(2*(octant&1)-1),
206
 
                     hs*((octant&2)-1),
207
 
                     hs*(((octant&4)>>1)-1) );
208
 
}
209
 
 
210
 
 
211
 
Octree::OctreeNode *Octree::OctreeNode::get_parent() throw()
212
 
{
213
 
    return m_parent;
214
 
}
215
 
 
216
 
 
217
 
const Octree::OctreeNode *Octree::OctreeNode::get_parent() const throw()
218
 
{
219
 
    return m_parent;
220
 
}
221
 
 
222
 
 
223
 
int Octree::OctreeNode::get_child_count() const throw()
224
 
{
225
 
    return m_child_count;
226
 
}
227
 
 
228
 
 
229
 
void Octree::OctreeNode::eval_recursive(
230
 
    OctreeTraverser *traverser,
231
 
    const int order[]) const throw()
232
 
{
233
 
    for( ContainedSet::const_iterator it = m_contained_objects.begin();
234
 
         it != m_contained_objects.end(); ++it )
235
 
    {
236
 
        traverser->traverse(*it);
237
 
    }
238
 
 
239
 
    // Execute fn on recursively on all non-empty child nodes
240
 
    for( int i = 0; i < 8; i++ )
241
 
    {
242
 
        OctreeNode *child = m_children[order[i]];
243
 
        if( child && !child->is_empty() )
244
 
            child->eval_recursive(traverser, order);
245
 
    }
246
 
}
247
 
 
248
 
 
249
 
 
250
 
void Octree::OctreeNode::traverse_pvs(primitives::Camera *camera, 
251
 
                                      OctreeTraverser *traverser,
252
 
                                      const int order[],
253
 
                                      int plane_mask) const throw()
254
 
{
255
 
    if( is_empty() )
256
 
        return;
257
 
 
258
 
    const boost::shared_ptr<Frustum> frustum(camera->get_frustum());
259
 
 
260
 
    BoundingSphere bsphere = BoundingSphere(m_pos, m_half_size*M_SQRT2);
261
 
 
262
 
    // Cull the node?
263
 
    IntersectionTestResult culltest = bsphere.contained_in(
264
 
        frustum->get_bounding_sphere());
265
 
 
266
 
    //if( culltest != DISJOINT )
267
 
    //    culltest = bsphere.contained_in(camera->get_frustum_bounding_cone());
268
 
 
269
 
    if( culltest != DISJOINT )
270
 
        culltest = frustum->is_in_frustum(bsphere, plane_mask);
271
 
 
272
 
    if( culltest == DISJOINT )
273
 
    {
274
 
        // Cull all child nodes!
275
 
        return;
276
 
    }
277
 
    else if( culltest == INSIDE )
278
 
    {
279
 
        eval_recursive(traverser, order);
280
 
    }
281
 
    else // culltest == INTERSECT
282
 
    {
283
 
        // If partial intersection:
284
 
        // 1. Do object level tests for contained objects
285
 
        // 2. traverse child nodes
286
 
 
287
 
        for( std::set<Cullable *>::iterator it = m_contained_objects.begin();
288
 
             it != m_contained_objects.end(); ++it )
289
 
        {
290
 
            object_level_cull(*it, camera, traverser, plane_mask);
291
 
        }
292
 
 
293
 
 
294
 
        // Cull subnodes
295
 
        for( int i = 0; i < 8; i++ )
296
 
        {
297
 
            OctreeNode *child = m_children[order[i]];
298
 
 
299
 
            if( child ) //&& !child->is_empty() )
300
 
            {
301
 
                child->traverse_pvs(camera,
302
 
                                    traverser,
303
 
                                    order,
304
 
                                    plane_mask);
305
 
            }
306
 
        }
307
 
    }
308
 
}
309
 
 
310
 
 
311
 
 
312
 
 
313
 
// Performs sphere-sphere and sphere-frustum tests
314
 
void Octree::OctreeNode::object_level_cull(
315
 
    Cullable *node, 
316
 
    primitives::Camera *camera,
317
 
    OctreeTraverser *traverser,
318
 
    int plane_mask) throw()
319
 
{
320
 
    const boost::shared_ptr<Frustum> frustum(camera->get_frustum());
321
 
 
322
 
    // Cull the node?
323
 
    IntersectionTestResult culltest = node->get_bounding_sphere().contained_in(
324
 
        frustum->get_bounding_sphere());
325
 
 
326
 
    if( culltest != DISJOINT )
327
 
        culltest = frustum->is_in_frustum(
328
 
            node->get_bounding_sphere(), plane_mask);
329
 
 
330
 
    if( culltest != DISJOINT )
331
 
        traverser->traverse(node);
332
 
 
333
 
    return;
334
 
}
335
 
 
336
 
 
337
 
Octree::OctreeNode *Octree::OctreeNode::get_octant(int i) throw()
338
 
{
339
 
    return m_children[i];
340
 
}
341
 
 
342
 
 
343
 
const Octree::OctreeNode *Octree::OctreeNode::get_octant(int i) const throw()
344
 
{
345
 
    return m_children[i];
346
 
}
347
 
 
348