source: trunk/src/lol/algorithm/aabb_tree.h @ 3809

Last change on this file since 3809 was 3809, checked in by sam, 7 years ago

misc: various C++11-related compilation fixes for Visual Studio.

  • Property svn:eol-style set to LF
File size: 12.6 KB
Line 
1//
2//  Lol Engine
3//
4//  Copyright © 2010—2015 Sam Hocevar <sam@hocevar.net>
5//            © 2013—2015 Benjamin "Touky" Huet <huet.benjamin@gmail.com>
6//
7//  This library is free software. It comes without any warranty, to
8//  the extent permitted by applicable law. You can redistribute it
9//  and/or modify it under the terms of the Do What the Fuck You Want
10//  to Public License, Version 2, as published by the WTFPL Task Force.
11//  See http://www.wtfpl.net/ for more details.
12//
13
14#pragma once
15
16#include <lol/base/array.h>
17#include <lol/debug/lines.h>
18#include <lol/image/color.h>
19
20namespace lol
21{
22
23//------ AABB TREE SYSTEM -----
24template <typename TE, typename TV, typename TB, size_t child_nb> class AABBTree;
25template <typename TE> class Quadtree;
26template <typename TE> class Octree;
27
28//--
29namespace Debug {
30//--
31
32template<typename TREE, typename TE, typename TBB>
33void DrawInner(TREE *tree, array<TBB, vec4> &boxes,
34               array<TE *, int, vec4> &elements,
35               array<int, TBB> &leaves, int children, vec4 color)
36{
37    boxes.Push(tree->GetAABB(), Color::white);
38    leaves.Push(0, boxes.Last().m1);
39    while (leaves.Count() > 0)
40    {
41        for (int j = 0; j < tree->GetTree()[leaves[0].m1].m_elements.Count(); j++)
42        {
43            bool done = false;
44            for (int k = 0; k < elements.Count(); k++)
45            {
46                if (elements[k].m1 == tree->GetElements()[tree->GetTree()[leaves[0].m1].m_elements[j]].m_element)
47                {
48                    elements[k].m2++;
49                    done = true;
50                    break;
51                }
52            }
53            if (!done)
54                elements.Push(tree->GetElements()[tree->GetTree()[leaves[0].m1].m_elements[j]].m_element, 1, Color::red);
55        }
56
57        for (int i = 0; i < children; i++)
58        {
59            if (tree->GetTree()[leaves[0].m1].m_children[i] != 0)
60            {
61                TBB bbox = tree->GetSubAABB(leaves[0].m2, i);
62                leaves.Push(tree->GetTree()[leaves[0].m1].m_children[i], bbox);
63                boxes.Push(bbox, color);
64            }
65        }
66        leaves.Remove(0);
67    }
68}
69
70//--
71template <typename TE, typename TV = void>
72void Draw(Quadtree<TE>* tree, vec4 color)
73{
74    array<box2, vec4> boxes;
75    array<TE*, int, vec4> elements;
76    array<int, box2> leaves;
77
78    DrawInner<Quadtree<TE>, TE, box2>(tree, boxes, elements, leaves, 4, color);
79
80    vec3 off = vec3(0.0f, 0.1f, 0.0f);
81    //vec3 add = vec3(0.0f, 0.1f, 0.0f);
82    while (boxes.Count() > 0)
83    {
84        Debug::DrawBox(vec3(boxes[0].m1.A.x, tree->m_debug_y_offset, boxes[0].m1.A.y),
85                       vec3(boxes[0].m1.B.x, tree->m_debug_y_offset, boxes[0].m1.B.y),
86                       boxes[0].m2);
87        boxes.Remove(0);
88    }
89    while (elements.Count() > 0)
90    {
91        while (elements[0].m2 > 0)
92        {
93            Debug::DrawBox(vec3(elements[0].m1->GetAABB().A.x, tree->m_debug_y_offset, elements[0].m1->GetAABB().A.y) + off * (float)elements[0].m2,
94                           vec3(elements[0].m1->GetAABB().B.x, tree->m_debug_y_offset, elements[0].m1->GetAABB().B.y) + off * (float)elements[0].m2,
95                           elements[0].m3);
96            elements[0].m2--;
97        }
98        elements.Remove(0);
99    }
100}
101//--
102template <typename TE, typename TV = void>
103void Draw(Octree<TE>* tree, vec4 color)
104{
105    array<box3, vec4> boxes;
106    array<TE*, int, vec4> elements;
107    array<int, box3> leaves;
108
109    DrawInner<Octree<TE>, TE, box3>(tree, boxes, elements, leaves, 8, color);
110
111    vec3 off = vec3(0.0f, 0.1f, 0.0f);
112    //vec3 add = vec3(0.0f, 0.1f, 0.0f);
113    while (boxes.Count() > 0)
114    {
115        //float size = boxes[0].m1.B.x - boxes[0].m1.A.x;
116        Debug::DrawBox(vec3(boxes[0].m1.A.x, boxes[0].m1.A.y, boxes[0].m1.A.z) /* + off * (m_size.x / size) */,
117                        vec3(boxes[0].m1.B.x, boxes[0].m1.B.y, boxes[0].m1.B.z) /* + off * (m_size.x / size) */,
118                        boxes[0].m2);
119        //off += add;
120        boxes.Remove(0);
121    }
122    while (elements.Count() > 0)
123    {
124        while (elements[0].m2 > 0)
125        {
126            Debug::DrawBox(vec3(elements[0].m1->GetAABB().A.x, elements[0].m1->GetAABB().A.y, elements[0].m1->GetAABB().A.z) + off * (float)elements[0].m2,
127                            vec3(elements[0].m1->GetAABB().B.x, elements[0].m1->GetAABB().B.y, elements[0].m1->GetAABB().B.z) + off * (float)elements[0].m2,
128                            elements[0].m3);
129            elements[0].m2--;
130        }
131        elements.Remove(0);
132    }
133}
134//--
135}
136
137//--
138template <typename TE, typename TV, typename TB, size_t child_nb>
139class AABBTree
140{
141    struct NodeLeaf
142    {
143        int             m_parent;
144        //Children pos in the list
145        int             m_children[child_nb];
146        //Element list
147        array<int>      m_elements;
148
149        NodeLeaf(int parent)
150        {
151            m_parent = parent;
152            for (int i = 0; i < child_nb; i++)
153                m_children[i] = 0;
154        }
155    };
156
157    struct TreeElement
158    {
159        TE*             m_element;
160        array<int>      m_leaves;
161
162        inline bool operator==(const TE*& element) { return m_element == element; }
163    };
164
165public:
166    AABBTree()
167    {
168        m_max_depth = 1;
169        m_max_element = 1;
170        AddLeaf(0);
171    }
172    ~AABBTree()
173    {
174        Clear();
175    }
176    void CopySetup(const AABBTree<TE, TV, TB, child_nb>* src)
177    {
178        CopySetup(*src);
179    }
180    void CopySetup(const AABBTree<TE, TV, TB, child_nb>& src)
181    {
182        m_size = src.m_size;
183        m_max_depth = src.m_max_depth;
184        m_max_element = src.m_max_element;
185    }
186
187private:
188    //--
189    bool                CleanupEmptyLeaves(int leaf=0)
190    {
191        int empty_children = 0;
192        for (int i = 0; i < child_nb; i++)
193        {
194            bool child_empty = false;
195            if (m_tree[leaf].m_children[i] != 0)
196                child_empty = CleanupEmptyLeaves(m_tree[leaf].m_children[i]);
197            empty_children += (int)(m_tree[leaf].m_children[i] == 0 || child_empty);
198        }
199        if (empty_children == 4 && leaf != 0)
200        {
201            for (int i = 0; i < child_nb; i++)
202            {
203                int old_leaf = m_tree[leaf].m_children[i];
204                if (old_leaf != 0)
205                    m_free_leaves << old_leaf;
206                m_tree[leaf].m_children[i] = 0;
207            }
208            return true;
209        }
210        return false;
211    }
212    //--
213    void                RemoveElement(TE* element)
214    {
215        int idx = INDEX_NONE;
216        for (int i = 0; i < m_elements.Count(); ++i)
217            if (m_elements[i].m_element == element)
218                idx = i;
219
220        if (idx == INDEX_NONE)
221            return;
222
223        //Remove item from tree leaves
224        for (int i = 0; i < m_elements[idx].m_leaves.Count(); i++)
225            m_tree[m_elements[idx].m_leaves[i]].m_elements.RemoveItem(idx);
226
227        //Try leaves cleanup
228        CleanupEmptyLeaves();
229    }
230    //--
231    int                 AddElement(TE* element)
232    {
233        for (int i = 0; i < m_elements.Count(); ++i)
234            if (m_elements[i].m_element == element)
235                return i;
236
237        TreeElement new_element;
238        new_element.m_element = element;
239        new_element.m_leaves = array<int>();
240        m_elements << new_element;
241        return m_elements.Count() - 1;
242    }
243    //--
244    int                 AddLeaf(int parent)
245    {
246        int idx = m_tree.Count();
247        if (m_free_leaves.Count())
248        {
249            idx = m_free_leaves.Pop();
250            m_tree[idx] = NodeLeaf(parent);
251        }
252        else
253            m_tree << NodeLeaf(parent);
254        return idx;
255    }
256
257    //--
258    bool                TestLeaf(int leaf, const TB& leaf_bb, const TB& test_bb, array<TE*>& elements)
259    {
260        bool result = false;
261        if (TestAABBVsAABB(leaf_bb, test_bb))
262        {
263            NodeLeaf& node = m_tree[leaf];
264            for (int i = 0; i < child_nb; i++)
265            {
266                if (node.m_children[i] != 0)
267                {
268                    TB sub_aabb = GetSubAABB(leaf_bb, i);
269                    result = result | TestLeaf(node.m_children[i], sub_aabb, test_bb, elements);
270                }
271                else
272                {
273                    for (int j = 0; j < node.m_elements.Count(); j++)
274                        elements.PushUnique(m_elements[node.m_elements[j]].m_element);
275                    result = true;
276                }
277            }
278        }
279        return result;
280    }
281    //--
282    bool                RegisterElement(TE* element, int leaf, TB leaf_bb, int depth)
283    {
284        if (TestAABBVsAABB(leaf_bb, element->GetAABB()))
285        {
286            bool found_child = false;
287            for (int i = 0; i < child_nb; i++)
288            {
289                TB child_bb = GetSubAABB(leaf_bb, i);
290                int child_leaf = m_tree[leaf].m_children[i];
291                //there is a child, go further down
292                if (child_leaf != 0)
293                    found_child = found_child | RegisterElement(element, child_leaf, child_bb, depth + 1);
294            }
295            if (found_child)
296                return true;
297
298            //Too much elements, we need to re-dispatch the elements
299            if (m_tree[leaf].m_elements.Count() + 1 > m_max_element &&
300                depth < m_max_depth)
301            {
302                //Extract elements
303                array<int> elements = m_tree[leaf].m_elements;
304                elements.PushUnique(AddElement(element));
305                m_tree[leaf].m_elements.Empty();
306                //Add children
307                for (int j = 0; j < child_nb; j++)
308                    m_tree[leaf].m_children[j] = AddLeaf(leaf);
309                //Re-run extracted elements
310                while (elements.Count())
311                {
312                    RegisterElement(m_elements[elements[0]].m_element, leaf, leaf_bb, depth);
313                    elements.Remove(0);
314                }
315            }
316            //else add to list.
317            else
318            {
319                int idx = AddElement(element);
320                m_elements[idx].m_leaves.PushUnique(leaf);
321                m_tree[leaf].m_elements.PushUnique(idx);
322            }
323            return true;
324        }
325        return false;
326    }
327
328public:
329    void                RegisterElement(TE* element)                        { RegisterElement(element, 0, GetAABB(), 0); }
330    void                UnregisterElement(TE* element)                      { RemoveElement(element); }
331    bool                FindElements(const TB& bbox, array<TE*>& elements)  { return TestLeaf(0, GetAABB(), bbox, elements); }
332    void                Clear()
333    {
334        m_tree.Empty();
335        m_elements.Empty();
336    }
337
338    //--
339    virtual TV          GetSubOffset(int sub) = 0;
340    virtual TB          GetAABB() { return TB(-m_size * .5f, m_size * .5f); }
341    virtual TB          GetSubAABB(const TB& bbox, int sub)
342    {
343        TV v(GetSubOffset(sub));
344        TV half_vec = (bbox.B - bbox.A) * .5f;
345        return TB(bbox.A + half_vec * v,
346                  bbox.A + half_vec * (v + TV(1.f)));
347    }
348
349    //--
350    TV                  GetSize()                       { return m_size; }
351    int                 GetMaxDepth()                   { return m_max_depth; }
352    int                 GetMaxElement()                 { return m_max_element; }
353    void                SetSize(TV size)                { m_size = size; }
354    void                SetMaxDepth(int max_depth)      { m_max_depth = max_depth; }
355    void                SetMaxElement(int max_element)  { m_max_element = max_element; }
356
357    array<NodeLeaf> const & GetTree() const
358    {
359        return m_tree;
360    }
361
362    array<TreeElement> const & GetElements() const
363    {
364        return m_elements;
365    }
366
367protected:
368    array<NodeLeaf>     m_tree;         //actual tree
369    array<TreeElement>  m_elements;     //elements to leaves
370    array<int>          m_free_leaves;  //leaves removed from tree
371    TV                  m_size;         //Main tree size
372    int                 m_max_depth;    //Maximum depth possible
373    int                 m_max_element;  //Maximum element per leaf
374};
375
376//--
377template <typename TE>
378class Quadtree : public AABBTree<TE, vec2, box2, 4>
379{
380    friend void Debug::Draw<TE,void>(Octree<TE>* tree, vec4 color);
381public:
382    Quadtree()          { m_debug_y_offset = 0.f; }
383    virtual ~Quadtree() { }
384    float               m_debug_y_offset;
385protected:
386    virtual vec2        GetSubOffset(int sub) { return vec2(ivec2(sub % 2, sub / 2)); }
387};
388
389//--
390template <typename TE>
391class Octree : public AABBTree<TE, vec3, box3, 8>
392{
393    friend void Debug::Draw<TE,void>(Octree<TE>* tree, vec4 color);
394public:
395    Octree()            { }
396    virtual ~Octree()   { }
397protected:
398    virtual vec3        GetSubOffset(int sub) { return vec3(ivec3(sub % 2, sub / 4, (sub % 4) / 2)); }
399};
400
401} /* namespace lol */
402
Note: See TracBrowser for help on using the repository browser.