1 /* bzflag
2 * Copyright (c) 1993-2021 Tim Riker
3 *
4 * This package is free software; you can redistribute it and/or
5 * modify it under the terms of the license found in the file
6 * named COPYING that should have accompanied this file.
7 *
8 * THIS PACKAGE IS PROVIDED ``AS IS'' AND WITHOUT ANY EXPRESS OR
9 * IMPLIED WARRANTIES, INCLUDING, WITHOUT LIMITATION, THE IMPLIED
10 * WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE.
11 */
12
13 #ifndef __OCTREE_H__
14 #define __OCTREE_H__
15
16 #include "SceneNode.h"
17 #include "Frustum.h"
18 #include "Extents.h"
19
20
21 class OctreeNode;
22
23
24 class Octree
25 {
26
27 public:
28
29 Octree();
30 ~Octree();
31
32 void clear ();
33
34 void addNodes (SceneNode** list, int listSize, int depth, int elements);
35
36 int getFrustumList (SceneNode** list, int listSize,
37 const Frustum* frustum) const;
38 int getShadowList (SceneNode** list, int listSize,
39 int planeCount, const float (*planes)[4]) const;
40 int getRadarList (SceneNode** list, int listSize,
41 const Frustum* frustum) const;
42
43 void setOccluderManager(int);
44
45 void draw () const;
46
47 const Extents* getVisualExtents() const;
48
49
50 private: // methods
51 void getExtents(SceneNode** list, int listSize);
52
53 private: // data
54 OctreeNode* root;
55 Extents extents;
56 Extents visualExtents;
57 };
58
59
60
61 class OctreeNode
62 {
63
64 public:
65
66 OctreeNode(unsigned char depth, const Extents& exts,
67 SceneNode** list, int listSize);
68 ~OctreeNode();
69
70 void getFrustumList () const;
71 void getShadowList () const;
72 void getRadarList () const;
73 void getFullyVisible () const;
74 void getFullyVisibleOcclude () const;
75 void getFullyShadow () const;
76 OctreeNode* getChild (int child);
77
78 int getCount() const; // number of nodes in this and subnodes
79 int getChildren() const; // number of children
80 int getListSize() const; // number of nodes in this node
81 SceneNode** getList() const; // list of nodes
82 const Extents& getExtents() const;
83
84 void tallyStats();
85 void draw ();
86
87 private:
88
89 void makeChildren ();
90 void resizeCell ();
91
92 enum CullLevel
93 {
94 NoCull,
95 PartialCull,
96 FullCull
97 };
98
99 unsigned char depth;
100 Extents extents;
101 unsigned char childCount;
102 OctreeNode* children[8];
103 OctreeNode* squeezed[8];
104 int count; // number of nodes in this and subnodes
105 int listSize;
106 SceneNode** list;
107
108 const OctreeNode* getNode(unsigned char x) const;
109 const OctreeNode* getFullNode(unsigned char x) const;
110 };
111
112
getCount()113 inline int OctreeNode::getCount() const
114 {
115 return count;
116 }
117
getList()118 inline SceneNode** OctreeNode::getList() const
119 {
120 return list;
121 }
122
getListSize()123 inline int OctreeNode::getListSize() const
124 {
125 return listSize;
126 }
127
getChildren()128 inline int OctreeNode::getChildren() const
129 {
130 return childCount;
131 }
132
getChild(int child)133 inline OctreeNode* OctreeNode::getChild (int child)
134 {
135 return children[child];
136 }
137
getVisualExtents()138 inline const Extents* Octree::getVisualExtents() const
139 {
140 return &visualExtents;
141 }
142
143
144 #endif // __OCTREE_H__
145
146 // Local Variables: ***
147 // mode: C++ ***
148 // tab-width: 4 ***
149 // c-basic-offset: 4 ***
150 // indent-tabs-mode: nil ***
151 // End: ***
152 // ex: shiftwidth=4 tabstop=4
153