PDA

View Full Version : subdividing octree

ugluk
01-25-2010, 06:23 AM
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&amp; aabb,
std::vector<AABB<U1, U2> >&amp; 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
01-25-2010, 07:50 AM
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));

Ilian Dinev
01-25-2010, 08:45 AM
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.