]>
Dogcows Code - chaz/yoink/blob - src/Moof/Octree.cc
2 /*******************************************************************************
4 Copyright (c) 2009, Charles McGarvey
7 Redistribution and use in source and binary forms, with or without
8 modification, are permitted provided that the following conditions are met:
10 * Redistributions of source code must retain the above copyright notice,
11 this list of conditions and the following disclaimer.
12 * Redistributions in binary form must reproduce the above copyright notice,
13 this list of conditions and the following disclaimer in the documentation
14 and/or other materials provided with the distribution.
16 THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS"
17 AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
18 IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE
19 DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT HOLDER OR CONTRIBUTORS BE LIABLE
20 FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
21 DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR
22 SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER
23 CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY,
24 OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
25 OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
27 *******************************************************************************/
38 stlplus::ntree
<OctreeNode
>::prefix_iterator it
;
40 for (it
= tree_
.prefix_begin(); it
!= tree_
.prefix_end(); ++it
)
47 stlplus::ntree
<OctreeNode
>::iterator
Octree::insert(stlplus::ntree
<OctreeNode
>::iterator node
,
50 Plane::Halfspace halfspace
;
55 std::cerr
<< "cannot insert into invalid node" << std::endl
;
56 return stlplus::ntree
<OctreeNode
>::iterator();
59 Plane xy
= node
->getAabb().getPlaneXY();
60 halfspace
= xy
.intersectsSphere(entity
->getSphere());
61 if (halfspace
== Plane::INTERSECT
)
63 halfspace
= xy
.intersectsAabb(entity
->getAabb());
66 if (halfspace
== Plane::POSITIVE
)
68 Plane xz
= node
->getAabb().getPlaneXZ();
69 halfspace
= xz
.intersectsSphere(entity
->getSphere());
70 if (halfspace
== Plane::INTERSECT
)
72 halfspace
= xz
.intersectsAabb(entity
->getAabb());
75 if (halfspace
== Plane::POSITIVE
)
77 Plane yz
= node
->getAabb().getPlaneYZ();
78 halfspace
= yz
.intersectsSphere(entity
->getSphere());
79 if (halfspace
== Plane::INTERSECT
)
81 halfspace
= yz
.intersectsAabb(entity
->getAabb());
84 if (halfspace
== Plane::POSITIVE
)
88 else if (halfspace
== Plane::NEGATIVE
)
93 else if (halfspace
== Plane::NEGATIVE
)
95 Plane yz
= node
->getAabb().getPlaneYZ();
96 halfspace
= yz
.intersectsSphere(entity
->getSphere());
97 if (halfspace
== Plane::INTERSECT
)
99 halfspace
= yz
.intersectsAabb(entity
->getAabb());
102 if (halfspace
== Plane::POSITIVE
)
106 else if (halfspace
== Plane::NEGATIVE
)
112 else if (halfspace
== Plane::NEGATIVE
)
114 Plane xz
= node
->getAabb().getPlaneXZ();
115 halfspace
= xz
.intersectsSphere(entity
->getSphere());
116 if (halfspace
== Plane::INTERSECT
)
118 halfspace
= xz
.intersectsAabb(entity
->getAabb());
121 if (halfspace
== Plane::POSITIVE
)
123 Plane yz
= node
->getAabb().getPlaneYZ();
124 halfspace
= yz
.intersectsSphere(entity
->getSphere());
125 if (halfspace
== Plane::INTERSECT
)
127 halfspace
= yz
.intersectsAabb(entity
->getAabb());
130 if (halfspace
== Plane::POSITIVE
)
134 else if (halfspace
== Plane::NEGATIVE
)
139 else if (halfspace
== Plane::NEGATIVE
)
141 Plane yz
= node
->getAabb().getPlaneYZ();
142 halfspace
= yz
.intersectsSphere(entity
->getSphere());
143 if (halfspace
== Plane::INTERSECT
)
145 halfspace
= yz
.intersectsAabb(entity
->getAabb());
148 if (halfspace
== Plane::POSITIVE
)
152 else if (halfspace
== Plane::NEGATIVE
)
161 node
->objects
.push_front(entity
);
166 if ((int)tree_
.children(node
) <= octantNum
)
168 addChild(node
, octantNum
);
171 stlplus::ntree
<OctreeNode
>::iterator child
= tree_
.child(node
, octantNum
);
175 return insert(child
, entity
);
179 std::cerr
<< "expected but found no child at index " << octantNum
<< std::endl
;
180 return stlplus::ntree
<OctreeNode
>::iterator();
185 stlplus::ntree
<OctreeNode
>::iterator
Octree::reinsert(EntityPtr entity
,
186 stlplus::ntree
<OctreeNode
>::iterator node
)
190 std::cerr
<< "cannot move entity from invalid node" << std::endl
;
191 return stlplus::ntree
<OctreeNode
>::iterator();
194 std::list
<EntityPtr
>::iterator it
;
195 it
= std::find(node
->objects
.begin(), node
->objects
.end(), entity
);
197 if (it
!= node
->objects
.end())
199 node
->objects
.erase(it
);
202 return insert(entity
);
206 void Octree::addChild(stlplus::ntree
<OctreeNode
>::iterator node
, int index
)
212 std::cerr
<< "cannot add children to invalid node" << std::endl
;
216 for (int i
= tree_
.children(node
); i
<= index
; ++i
)
218 node
->getAabb().getOctant(octant
, i
);
219 tree_
.append(node
, octant
);
224 void Octree::draw(stlplus::ntree
<OctreeNode
>::iterator node
, Scalar alpha
)
228 std::cerr
<< "cannot draw null child node :-(" << std::endl
;
234 for (unsigned i
= 0; i
< tree_
.children(node
); ++i
)
236 stlplus::ntree
<OctreeNode
>::iterator child
= tree_
.child(node
, i
);
244 std::cerr
<< "node is not a leaf, but has an invalid child" << std::endl
;
250 void Octree::drawIfVisible(stlplus::ntree
<OctreeNode
>::iterator node
,
251 Scalar alpha
, const Camera
& cam
)
253 //node.drawIfVisible(alpha, cam);
257 std::cerr
<< "invalid child while drawing :-(" << std::endl
;
261 Frustum::Collision collision
=
262 cam
.getFrustum().containsSphere(node
->getSphere());
263 if (collision
== Frustum::OUTSIDE
) return;
265 collision
= cam
.getFrustum().containsAabb(node
->getAabb());
266 if (collision
== Frustum::OUTSIDE
) return;
269 if (collision
== Frustum::INSIDE
)
273 else // collision == Frustum::INTERSECT
275 node
->drawIfVisible(alpha
, cam
);
278 if (tree_
.children(node
) > 0)
280 if (collision
== Frustum::INSIDE
)
282 for (unsigned i
= 0; i
< tree_
.children(node
); ++i
)
284 stlplus::ntree
<OctreeNode
>::iterator child
= tree_
.child(node
, i
);
292 std::cerr
<< "node is not a leaf, but has an invalid child" << std::endl
;
297 else // collision == Frustum::INTERSECT
299 for (unsigned i
= 0; i
< tree_
.children(node
); ++i
)
301 stlplus::ntree
<OctreeNode
>::iterator child
= tree_
.child(node
, i
);
305 drawIfVisible(child
, alpha
, cam
);
309 std::cerr
<< "node is not a leaf, but has an invalid child" << std::endl
;
319 /** vim: set ts=4 sw=4 tw=80: *************************************************/
This page took 0.048618 seconds and 5 git commands to generate.