1 // frametree.cpp
2 //
3 // Reference frame tree
4 //
5 // Copyright (C) 2008, the Celestia Development Team
6 // Initial version by Chris Laurel, claurel@gmail.com
7 //
8 // This program is free software; you can redistribute it and/or
9 // modify it under the terms of the GNU General Public License
10 // as published by the Free Software Foundation; either version 2
11 // of the License, or (at your option) any later version.
12
13 #include <algorithm>
14 #include <cassert>
15 #include "celengine/frametree.h"
16 #include "celengine/timeline.h"
17 #include "celengine/timelinephase.h"
18 #include "celengine/frame.h"
19
20
21 /* A FrameTree is hierarchy of solar system bodies organized according to
22 * the relationship of their reference frames. An object will appear in as
23 * a child in the tree of whatever object is the center of its orbit frame.
24 * Since an object may have several orbit frames in its timeline, the
25 * structure is a bit more complicated than a straightforward tree
26 * of Body objects. A Body has exactly a single parent in the frame tree
27 * at a given time, but may have many over it's lifespan. An object's
28 * timeline contains a list of timeline phases; each phase can point to
29 * a different parent. Thus, the timeline can be thought of as a list of
30 * parents.
31 *
32 * The FrameTree hiearchy is designed for fast visibility culling. There are
33 * two values stored in each node for this purpose: the bounding sphere
34 * radius, and the maximum child object radius. The bounding sphere is large
35 * enough to contain the orbits of all child objects, as well as the child
36 * objects themselves. Change tracking is performed whenever the frame tree
37 * is modified: adding a node, removing a node, or changing the radius of an
38 * object will all cause the tree to be marked as changed.
39 */
40
41 /*! Create a frame tree associated with a star.
42 */
FrameTree(Star * star)43 FrameTree::FrameTree(Star* star) :
44 starParent(star),
45 bodyParent(NULL),
46 defaultFrame(NULL)
47 {
48 // Default frame for a star is J2000 ecliptical, centered
49 // on the star.
50 defaultFrame = new J2000EclipticFrame(Selection(star));
51 defaultFrame->addRef();
52 }
53
54
55 /*! Create a frame tree associated with a planet or other solar system body.
56 */
FrameTree(Body * body)57 FrameTree::FrameTree(Body* body) :
58 starParent(NULL),
59 bodyParent(body),
60 defaultFrame(NULL)
61 {
62 // Default frame for a solar system body is the mean equatorial frame of the body.
63 defaultFrame = new BodyMeanEquatorFrame(Selection(body), Selection(body));
64 defaultFrame->addRef();
65 }
66
67
~FrameTree()68 FrameTree::~FrameTree()
69 {
70 defaultFrame->release();
71 }
72
73
74 /*! Return the default reference frame for the object a frame tree is associated
75 * with.
76 */
77 ReferenceFrame*
getDefaultReferenceFrame() const78 FrameTree::getDefaultReferenceFrame() const
79 {
80 return defaultFrame;
81 }
82
83
84 /*! Mark this node of the frame hierarchy as changed. The changed flag
85 * is propagated up toward the root of the tree.
86 */
87 void
markChanged()88 FrameTree::markChanged()
89 {
90 if (!m_changed)
91 {
92 m_changed = true;
93 if (bodyParent != NULL)
94 bodyParent->markChanged();
95 }
96 }
97
98
99 /*! Mark this node of the frame hierarchy as updated. The changed flag
100 * is marked false in this node and in all child nodes that
101 * were marked changed.
102 */
103 void
markUpdated()104 FrameTree::markUpdated()
105 {
106 if (m_changed)
107 {
108 m_changed = false;
109 for (vector<TimelinePhase*>::iterator iter = children.begin();
110 iter != children.end(); iter++)
111 {
112 (*iter)->body()->markUpdated();
113 }
114 }
115 }
116
117
118 /*! Recompute the bounding sphere for this tree and all subtrees marked
119 * as having changed. The bounding sphere is large enough to accommodate
120 * the orbits (and radii) of all child bodies. This method also recomputes
121 * the maximum child radius, secondary illuminator status, and child
122 * class mask.
123 */
124 void
recomputeBoundingSphere()125 FrameTree::recomputeBoundingSphere()
126 {
127 if (m_changed)
128 {
129 m_boundingSphereRadius = 0.0;
130 m_maxChildRadius = 0.0;
131 m_containsSecondaryIlluminators = false;
132 m_childClassMask = 0;
133
134 for (vector<TimelinePhase*>::iterator iter = children.begin();
135 iter != children.end(); iter++)
136 {
137 TimelinePhase* phase = *iter;
138 double bodyRadius = phase->body()->getRadius();
139 double r = phase->body()->getCullingRadius() + phase->orbit()->getBoundingRadius();
140 m_maxChildRadius = max(m_maxChildRadius, bodyRadius);
141 m_containsSecondaryIlluminators = m_containsSecondaryIlluminators || phase->body()->isSecondaryIlluminator();
142 m_childClassMask |= phase->body()->getClassification();
143
144 FrameTree* tree = phase->body()->getFrameTree();
145 if (tree != NULL)
146 {
147 tree->recomputeBoundingSphere();
148 r += tree->m_boundingSphereRadius;
149 m_maxChildRadius = max(m_maxChildRadius, tree->m_maxChildRadius);
150 m_containsSecondaryIlluminators = m_containsSecondaryIlluminators || tree->containsSecondaryIlluminators();
151 m_childClassMask |= tree->childClassMask();
152 }
153
154 m_boundingSphereRadius = max(m_boundingSphereRadius, r);
155 }
156 }
157 }
158
159
160 /*! Add a new phase to this tree.
161 */
162 void
addChild(TimelinePhase * phase)163 FrameTree::addChild(TimelinePhase* phase)
164 {
165 phase->addRef();
166 children.push_back(phase);
167 markChanged();
168 }
169
170
171 /*! Remove a phase from the tree. This method does nothing if the specified
172 * phase doesn't exist in the tree.
173 */
174 void
removeChild(TimelinePhase * phase)175 FrameTree::removeChild(TimelinePhase* phase)
176 {
177 vector<TimelinePhase*>::iterator iter = find(children.begin(), children.end(), phase);
178 if (iter != children.end())
179 {
180 (*iter)->release();
181 children.erase(iter);
182 markChanged();
183 }
184 }
185
186
187 /*! Return the child at the specified index. */
188 TimelinePhase*
getChild(unsigned int n) const189 FrameTree::getChild(unsigned int n) const
190 {
191 return children[n];
192 }
193
194
195 /*! Get the number of immediate children of this tree. */
196 unsigned int
childCount() const197 FrameTree::childCount() const
198 {
199 return children.size();
200 }
201