ugluk
January 25, 2010, 6:23am
1
I am currently using this function to subdivide an AABB in an octree. I am dissatisfied with it, as it uses 3 loops and std::pow(), maybe there’s some trick to simplify this? Please show me some C++ power. The AABBs are all center-radius AABBs.
template <class U1, class U2>
void subdivide_aabb(AABB<U1, U2> const& aabb,
std::vector<AABB<U1, U2> >& aabbs)
{
BOOST_ASSERT(aabbs.empty());
AABB<U1, U2> naabb;
naabb.b = 0.5 * aabb.b;
for (unsigned char i(0); i != 2; ++i)
{
for (unsigned char j(0); j != 2; ++j)
{
for (unsigned char k(0); k != 2; ++k)
{
naabb.a = aabb.a;
naabb.a += U1(std::pow(-1, i) * naabb.b(0),
std::pow(-1, j) * naabb.b(1),
std::pow(-1, k) * naabb.b(2));
aabbs.push_back(naabb);
}
}
}
BOOST_ASSERT(8 == aabbs.size());
}
ugluk
January 25, 2010, 7:50am
2
I got this idea:
naabb.a += U1((2 * i - 1) * naabb.b(0),
(2 * j - 1) * naabb.b(1),
(2 * k - 1) * naabb.b(2));
I prefer to keep things simple and coherent, for things that don’t need optimization.
Index with bit 1 set: positive x, index with bit 2 set: positive y, bit 3: z
for(int i=0;i<8;i++){
AABB aabb;
aabb.minBB.z = minBB.z;
aabb.maxBB.z = avgBB.z;
aabb.minBB.y = minBB.y;
aabb.maxBB.y = avgBB.y;
aabb.minBB.x = minBB.x;
aabb.maxBB.x = avgBB.x;
if(i & 4){ // greater z
aabb.minBB.z = avgBB.z;
aabb.maxBB.z = maxBB.z;
}
if(i & 2){ // greater y
aabb.minBB.y = avgBB.y;
aabb.maxBB.y = maxBB.y;
}
if(i & 1){ // greater x
aabb.minBB.x = avgBB.x;
aabb.maxBB.x = maxBB.x;
}
child = new OCTREE;
parent->nodes[i]=child;
child->parent = parent;
child->aabb = aabb;
}
If speed is an issue, I’d use CMOVxx and SSE intrinsics, inline asm or external asm; and of course get around the allocalization.