{
"playfield_bounds": [0, 0, -100, 1280, 500, 100],
- "maximum_bounds": [-165, -5, -197, 1445, 517, 229],
+ "maximum_bounds": [-160, 0, -192, 1440, 512, 224],
"instructions":
[
Moof/OpenGL.hh \
Moof/Plane.cc \
Moof/Plane.hh \
- Moof/Profiler.hh \
Moof/Random.cc \
Moof/Random.hh \
Moof/Resource.cc \
Moof/Tilemap.hh \
Moof/Timer.cc \
Moof/Timer.hh \
- Moof/Tree.hh \
Moof/Video.cc \
Moof/Video.hh \
Moof/fastevents.c \
yoink_LDADD = libmoof.la
-EXTRA_DIST = Moof/cml
+EXTRA_DIST = Moof/cml Moof/stlplus
YOINK_ENVIRONMENT = YOINK_DATADIR="$(top_srcdir)/data"
#include <boost/shared_ptr.hpp>
+#include <stlplus/ntree.hpp>
+
#include <Moof/Aabb.hh>
#include <Moof/Drawable.hh>
#include <Moof/Entity.hh>
#include <Moof/Math.hh>
#include <Moof/Sphere.hh>
-#include <Moof/Tree.hh>
namespace Mf {
class Octree;
typedef boost::shared_ptr<Octree> OctreePtr;
-class Octree : public Tree<OctreeNode>
+class Octree
{
- Octree() {}
-
- explicit Octree(const OctreeNode& initNode) :
- Tree<OctreeNode>(initNode) {}
+ stlplus::ntree<OctreeNode> root_;
public:
- inline static OctreePtr createNewNode(const OctreeNode& item)
+ explicit Octree(const OctreeNode& rootNode)
{
- OctreePtr newNode = OctreePtr(new Octree(item));
- init(newNode);
- return newNode;
+ root_.insert(rootNode);
}
+ void insert(EntityPtr entity)
+ {
+ insert(root_.root(), entity);
+ }
- static Tree<OctreeNode>::WeakPtr add(Ptr node, EntityPtr entity)
+ void insert(stlplus::ntree<OctreeNode>::iterator node, EntityPtr entity)
{
Plane::Halfspace halfspace;
int octantNum = -1;
- Plane xy = node->node.getAabb().getPlaneXY();
+ if (!node.valid())
+ {
+ std::cerr << "cannot insert into invalid node" << std::endl;
+ return;
+ }
+
+ Plane xy = node->getAabb().getPlaneXY();
halfspace = xy.intersectsSphere(entity->getSphere());
if (halfspace == Plane::POSITIVE)
{
- Plane xz = node->node.getAabb().getPlaneXZ();
+ Plane xz = node->getAabb().getPlaneXZ();
halfspace = xz.intersectsSphere(entity->getSphere());
if (halfspace == Plane::POSITIVE)
{
- Plane yz = node->node.getAabb().getPlaneYZ();
+ Plane yz = node->getAabb().getPlaneYZ();
halfspace = yz.intersectsSphere(entity->getSphere());
if (halfspace == Plane::POSITIVE)
}
else if (halfspace == Plane::NEGATIVE)
{
- Plane yz = node->node.getAabb().getPlaneYZ();
+ Plane yz = node->getAabb().getPlaneYZ();
halfspace = yz.intersectsSphere(entity->getSphere());
if (halfspace == Plane::POSITIVE)
}
else if (halfspace == Plane::NEGATIVE)
{
- Plane xz = node->node.getAabb().getPlaneXZ();
+ Plane xz = node->getAabb().getPlaneXZ();
halfspace = xz.intersectsSphere(entity->getSphere());
if (halfspace == Plane::POSITIVE)
{
- Plane yz = node->node.getAabb().getPlaneYZ();
+ Plane yz = node->getAabb().getPlaneYZ();
halfspace = yz.intersectsSphere(entity->getSphere());
if (halfspace == Plane::POSITIVE)
}
else if (halfspace == Plane::NEGATIVE)
{
- Plane yz = node->node.getAabb().getPlaneYZ();
+ Plane yz = node->getAabb().getPlaneYZ();
halfspace = yz.intersectsSphere(entity->getSphere());
if (halfspace == Plane::POSITIVE)
if (octantNum == -1)
{
- node->node.objects.push_front(entity);
- return node;
+ node->objects.push_front(entity);
+ //return node;
}
else
{
- if (node->isLeaf())
+ if (root_.children(node) == 0)
{
addChildren(node);
}
- Ptr child = node->getChild(octantNum);
- if (child)
+ stlplus::ntree<OctreeNode>::iterator child = root_.child(node, octantNum);
+
+ if (child.valid())
{
- return add(child, entity);
+ return insert(child, entity);
}
else
{
- std::cerr << "no child at index " << octantNum << std::endl;
- return Ptr();
+ std::cerr << "expected but found no child at index " << octantNum << std::endl;
+ //return stlplus::ntree<OctreeNode>::iterator();
}
//return WeakPtr();
}
}
- static void addChildren(Ptr node)
+ void addChildren(stlplus::ntree<OctreeNode>::iterator node)
{
Aabb octant;
+ if (!node.valid())
+ {
+ std::cerr << "cannot add children to invalid node" << std::endl;
+ return;
+ }
+
for (int i = 0; i < 8; ++i)
{
- node->node.getAabb().getOctant(octant, i);
+ node->getAabb().getOctant(octant, i);
//OctreeNode octantNode(octant);
- Ptr newChild = createNewNode(octant);
- node->addChild(newChild);
+ root_.append(node, octant);
}
}
- void draw(Ptr node, Scalar alpha)
+ void draw(stlplus::ntree<OctreeNode>::iterator node, Scalar alpha)
{
- if (!node)
+ if (!node.valid())
{
- std::cerr << "null child :-(" << std::endl;
+ std::cerr << "cannot draw null child node :-(" << std::endl;
return;
}
- node->node.draw(alpha);
+ node->draw(alpha);
- if (!node->isLeaf())
+ for (unsigned i = 0; i < root_.children(node); ++i)
{
- Ptr firstChild = node->getFirstChild();
- Ptr temp = firstChild;
+ stlplus::ntree<OctreeNode>::iterator child = root_.child(node, i);
- if (!firstChild)
+ if (child.valid())
{
- std::cerr << "node is not a leaf, but has no first child :-(" << std::endl;
- return;
+ draw(child, alpha);
}
-
- do
+ else
{
- draw(temp, alpha);
- temp = temp->getNextSibling();
+ std::cerr << "node is not a leaf, but has an invalid child" << std::endl;
}
- while (temp && temp != firstChild);
+
}
}
- void drawIfVisible(Ptr node, Scalar alpha, const Camera& cam)
+ void drawIfVisible(stlplus::ntree<OctreeNode>::iterator node,
+ Scalar alpha, const Camera& cam)
{
//node.drawIfVisible(alpha, cam);
- if (!node)
+ if (!node.valid())
{
- std::cerr << "null child :-(" << std::endl;
+ std::cerr << "invalid child while drawing :-(" << std::endl;
return;
}
Frustum::Collision collision =
- cam.getFrustum().containsSphere(node->node.getSphere());
+ cam.getFrustum().containsSphere(node->getSphere());
if (collision == Frustum::OUTSIDE) return;
- collision = cam.getFrustum().containsAabb(node->node.getAabb());
+ collision = cam.getFrustum().containsAabb(node->getAabb());
if (collision == Frustum::OUTSIDE) return;
if (collision == Frustum::INSIDE)
{
- node->node.draw(alpha);
+ node->draw(alpha);
}
else // collision == Frustum::INTERSECT
{
- node->node.drawIfVisible(alpha, cam);
+ node->drawIfVisible(alpha, cam);
}
- if (!node->isLeaf())
+ if (root_.children(node) > 0)
{
- Ptr firstChild = node->getFirstChild();
- Ptr temp = firstChild;
-
- if (!firstChild)
- {
- std::cerr << "node is not a leaf, but has no first child :-(" << std::endl;
- return;
- }
-
if (collision == Frustum::INSIDE)
{
- do
+ for (unsigned i = 0; i < root_.children(node); ++i)
{
- draw(temp, alpha);
- temp = temp->getNextSibling();
+ stlplus::ntree<OctreeNode>::iterator child = root_.child(node, i);
+
+ if (child.valid())
+ {
+ draw(child, alpha);
+ }
+ else
+ {
+ std::cerr << "node is not a leaf, but has an invalid child" << std::endl;
+ }
+
}
- while (temp && temp != firstChild);
}
else // collision == Frustum::INTERSECT
{
- do
+ for (unsigned i = 0; i < root_.children(node); ++i)
{
- drawIfVisible(temp, alpha, cam);
- temp = temp->getNextSibling();
+ stlplus::ntree<OctreeNode>::iterator child = root_.child(node, i);
+
+ if (child.valid())
+ {
+ drawIfVisible(child, alpha, cam);
+ }
+ else
+ {
+ std::cerr << "node is not a leaf, but has an invalid child" << std::endl;
+ }
}
- while (temp && temp != firstChild);
}
}
}
void drawIfVisible(Scalar alpha, const Camera& cam)
{
- drawIfVisible(getThis(), alpha, cam);
+ drawIfVisible(root_.root(), alpha, cam);
}
};
boost::shared_ptr<Quad> quadPtr(quad);
//objects.push_back(quadPtr);
- Octree::add(octree, quadPtr);
+ octree->insert(quadPtr);
}
}
}
boost::shared_ptr<Quad> quadPtr(quad);
//objects.push_back(quad_Ptr);
- Octree::add(octree, quadPtr);
+ octree->insert(quadPtr);
}
}
}
//OctreeNode rootNode(maximumBounds);
- octree = Octree::createNewNode(maximumBounds);
+ octree = OctreePtr(new Octree(maximumBounds));
if ((it = rootObj.find("instructions")) != rootObj.end())
{
+++ /dev/null
-
-/*******************************************************************************
-
- Copyright (c) 2009, Charles McGarvey
- All rights reserved.
-
- Redistribution and use in source and binary forms, with or without
- modification, are permitted provided that the following conditions are met:
-
- * Redistributions of source code must retain the above copyright notice,
- this list of conditions and the following disclaimer.
- * Redistributions in binary form must reproduce the above copyright notice,
- this list of conditions and the following disclaimer in the documentation
- and/or other materials provided with the distribution.
-
- THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS"
- AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
- IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE
- DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT HOLDER OR CONTRIBUTORS BE LIABLE
- FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
- DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR
- SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER
- CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY,
- OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
- OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
-
-*******************************************************************************/
-
-#ifndef _MOOF_TREE_HH_
-#define _MOOF_TREE_HH_
-
-#include <boost/shared_ptr.hpp>
-#include <boost/weak_ptr.hpp>
-
-
-namespace Mf {
-
-
-template <typename T>
-class Tree
-{
-public:
- typedef boost::shared_ptr<Tree> Ptr;
- typedef boost::weak_ptr<Tree> WeakPtr;
-
- T node;
-
-protected:
- WeakPtr parent_;
- WeakPtr prevSibling_;
- Ptr next_;
- WeakPtr lastDescendant_;
-
- inline static void init(Ptr itself)
- {
- itself->prevSibling_ = itself;
- itself->lastDescendant_ = itself;
- }
-
- Tree() {}
-
- explicit Tree(const T& item) :
- node(item) {}
-
-public:
-
- inline void print() const
- {
- std::cout << "==================" << std::endl;
- std::cout << " Node: " << getThis() << std::endl;
- std::cout << " Parent: " << parent_.lock() << std::endl;
- std::cout << " PrevSib: " << prevSibling_.lock() << std::endl;
- std::cout << " Next: " << next_ << std::endl;
- std::cout << "LastDesc: " << lastDescendant_.lock() << std::endl;
- //std::cout << " Value: " << node << std::endl;
- std::cout << "==================" << std::endl;
- }
-
- inline static Ptr createNewNode()
- {
- Ptr newNode = Ptr(new Tree<T>());
- }
-
- inline static Ptr createNewNode(const T& item)
- {
- Ptr newNode = Ptr(new Tree<T>(item));
- init(newNode);
- return newNode;
- }
-
- inline Ptr getNext() const
- {
- return next_;
- }
-
- inline Ptr getPrevious() const
- {
- Ptr parent = getParent();
-
- if (parent)
- {
- if (parent->getNext().get() == this)
- {
- return parent;
- }
- else
- {
- return prevSibling_.lock()->getLastDescendant();
- }
- }
-
- return Ptr();
- }
-
- inline Ptr getFirstChild() const
- {
- if (next_ && next_->getParent().get() == this)
- {
- return next_;
- }
-
- return Ptr();
- }
-
- inline Ptr getLastChild() const
- {
- Ptr child = getFirstChild();
-
- if (child)
- {
- child = child->prevSibling_.lock();
- }
-
- return child;
- }
-
- inline Ptr getChild(int index) const
- {
- Ptr child = getFirstChild();
-
- for (int i = 0; child && i < index; ++i)
- {
- child = child->getNextSibling();
- }
-
- return child;
- }
-
- inline Ptr getNextSibling() const
- {
- Ptr sibling = getLastDescendant()->getNext();
-
- if (sibling && sibling->getParent() != getParent())
- {
- return Ptr();
- }
-
- return sibling;
- }
-
- inline Ptr getPreviousSibling() const
- {
- Ptr parent = getParent();
-
- if (parent && parent->getNext().get() != this)
- {
- return prevSibling_.lock();
- }
-
- return Ptr();
- }
-
- inline Ptr getParent() const
- {
- return parent_.lock();
- }
-
- inline Ptr getLastDescendant() const
- {
- return lastDescendant_.lock();
- }
-
- inline Ptr getThis() const
- {
- if (next_)
- {
- return next_->getPrevious();
- }
-
- return getLastDescendant();
- }
-
- inline bool isRoot() const
- {
- return getParent().get() == 0;
- }
-
- inline bool isLeaf() const
- {
- return getLastDescendant().get() == this;
- }
-
- inline bool isDescendantOf(Ptr ancestor) const
- {
- Ptr temp = getParent();
-
- while (temp)
- {
- if (temp.get() == this) return true;
-
- temp = temp->getParent();
- }
-
- return false;
- }
-
-
- class Iterator
- {
- Ptr current;
-
- public:
-
- };
-
-
- void addChild(Ptr subtree)
- {
- //WeakPtr parent_;
- //WeakPtr prevSibling_;
- //Ptr next_;
- //WeakPtr lastDescendant_;
-
- subtree->remove();
-
- Ptr firstChild = getFirstChild();
- Ptr lastChild = getLastChild();
- Ptr nextSibling = getNextSibling();
- Ptr lastDescendant = getLastDescendant();
- Ptr newLastDescendant = subtree->getLastDescendant();
- Ptr parent = getThis();
-
- // 1. If parent is leaf, set parent.next to subtree.
-
- if (isLeaf())
- {
- next_ = subtree;
- }
-
- // 2. Set parent.last_descendant to subtree.last_descendant.
-
- Ptr temp = parent;
- while (temp && temp->getLastDescendant() == lastDescendant)
- {
- temp->lastDescendant_ = newLastDescendant;
- temp = temp->getParent();
- }
-
- // 3. Set subtree.parent to parent.
-
- subtree->parent_ = parent;
-
- // 4. Set parent.first_child.prev_sibling to subtree.
-
- if (firstChild)
- {
- firstChild->prevSibling_ = subtree;
- }
-
- // 5. Set subtree.prev_sibling to parent.last_child.
- // 6. Set parent.last_child.last_descendant.next to subtree.
-
- if (lastChild)
- {
- subtree->prevSibling_ = lastChild;
- lastChild->getLastDescendant()->next_ = subtree;
- }
- else
- {
- subtree->prevSibling_ = subtree;
- }
-
- // 7. Set subtree.last_descendant.next to parent.next_sibling.
-
- if (nextSibling)
- {
- subtree->getLastDescendant()->next_ = nextSibling;
- }
- }
-
- void remove()
- {
- Ptr parent = getParent();
- Ptr prevSibling = getPreviousSibling();
- Ptr nextSibling = getNextSibling();
- Ptr lastDescendant = getLastDescendant();
- Ptr previous = getPrevious();
-
- Ptr newLastDescendant;
-
- // 1. Fix last descendant of each direct ancestor.
-
- if (prevSibling) newLastDescendant = prevSibling->getLastDescendant();
- else newLastDescendant = parent;
-
- Ptr temp = parent;
- while (temp && temp->getLastDescendant() == lastDescendant)
- {
- temp->lastDescendant_ = newLastDescendant;
- temp = temp->getParent();
- }
-
- // 2. Fix next of previous.
-
- if (previous)
- {
- previous->next_ = nextSibling;
- }
-
- // 3. Fix the previous sibling of next sibling.
-
- if (nextSibling)
- {
- nextSibling->prevSibling_ = prevSibling;
- }
-
- // 4. Once detached, the subtree root has no parent or siblings.
-
- parent_.reset();
- prevSibling_ = getThis();
- }
-
-};
-
-
-} // namespace Mf
-
-#endif // _MOOF_TREE_HH_
-
-/** vim: set ts=4 sw=4 tw=80: *************************************************/
-
}
-#include <Moof/Tree.hh>
-
int main(int argc, char* argv[])
{
int status = 0;
- //Mf::Tree<int>::Ptr rootNode;
- //Mf::Tree<int>::Ptr temp, temp2, temp3;
-
- //rootNode = Mf::Tree<int>::Ptr(Mf::Tree<int>::createNewNode(1));
-
- //temp = Mf::Tree<int>::Ptr(Mf::Tree<int>::createNewNode(2));
- //temp3 = temp;
- //rootNode->addChild(temp);
-
- //temp = Mf::Tree<int>::Ptr(Mf::Tree<int>::createNewNode(3));
- //temp2 = temp;
- //rootNode->addChild(temp);
-
- //temp = Mf::Tree<int>::Ptr(Mf::Tree<int>::createNewNode(4));
- //rootNode->addChild(temp);
-
- //temp = Mf::Tree<int>::Ptr(Mf::Tree<int>::createNewNode(5));
- //temp2->addChild(temp);
-
- //temp = Mf::Tree<int>::Ptr(Mf::Tree<int>::createNewNode(6));
- //temp2->addChild(temp);
-
- //temp = Mf::Tree<int>::Ptr(Mf::Tree<int>::createNewNode(7));
- //temp3->addChild(temp);
-
- //temp = rootNode;
- //while (temp)
- //{
- //temp->print();
- //temp = temp->getNext();
- //}
- //return 0;
-
try
{
YoinkApp app(argc, argv);
return status;
}
+
/** vim: set ts=4 sw=4 tw=80: *************************************************/
projects / chaz / yoink / commitdiff
