Find the minimum translation to fit one box inside another

This topic is 708 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

Recommended Posts

There are two cubes (AABBs), A and B, A is always bigger than B.
When B is not fully inside A, how to calculate the minimum-length translation vector for A
so that A, when translated, fully covers B?

(Whence this problem came:
I'm implementing a clipmap (aka 'nested clip-boxes') which is a LOD-scheme allowing for ludicrously large volumetric terrains (e.g. planets in space).
The space around the viewer is partitioned into a set of nested boxes of the same resolution, but different sizes.

(in this image crack patching is not finished yet:)

(apparently, clipmaps were first used for rendering planets in "Alien" [1979]:)

Usually, the boxes remain nested and roughly centered around the viewer,
but if the camera moves too fast, the inner boxes can intersect their 'parent' (the box, representing a coarser LoD) or even jump ouside of it.
So, I need to update the positions of all boxes starting from the innermost one (immediately surrounding the viewer).
I've written some crappy code to update LOD levels (if A doesn't fully contain B, then offset A by smallest absolute magnitude of mins/maxs A-B differences along each axis),
but there surely is a simple and elegant solution.)

Share on other sites

Seems like you're going down the rabbit hole of over engineering, instead of taking a step back and re-evaluating your entire approach altogether.

To my mind, the trick is doing the outer lower-res first, and then progressively refining closer to the camera. If you're handling 'boxes' then something is wrong.

Share on other sites

If b should go th bottom right of a, take the difference from top left of b to the center of a. You get t - it's magic.

Ooops, i was assuming a as always exactly double the size of b, but you say it's just larger.

Let's take an even simpler solution covering any case:

If b should be bottom right aligned with a, take the difference between the bottom right corners of both to get t :)

Edit:

Seriously, does that really answer your question? I mean, it's really simple in comparision to the work you've already done.

Edited by JoeJ

Share on other sites

If b should go th bottom right of a, take the difference from top left of b to the center of a. You get t - it's magic.

Ooops, i was assuming a as always exactly double the size of b, but you say it's just larger.

Let's take an even simpler solution covering any case:

If b should be bottom right aligned with a, take the difference between the bottom right corners of both to get t :)

Edit:

Seriously, does that really answer your question? I mean, it's really simple in comparision to the work you've already done.

Not really.

B could be anywhere, e.g. to the bottom left, or top left, or top right of A.

I need to align A (e.g. move it to the bottom left, or top left, or top right) so that it fully contains B.

Yes, each LoD box is double the size of the previous (contained) box,

but they cannot touch (to ensure proper 2:1 LoD transitions),

so B is slightly larger (border size == 1 cell of A).

I just wanted to know if there's a nicer approach. Btw, here's my (fully working) ugly code:

Int3 CalcMinCorner( const AABBi& _bigger, const AABBi& _smaller )
{
ASSERT(Int3::GreaterOrEqual( _bigger.FullSize(), _smaller.FullSize() ) );
Int3 result( _bigger.mins );
if( !_bigger.Contains( _smaller ) )
{
// Find the minimum translational distance to move the current clip-box
// so that it fully encompasses the inner clip-box (including the margin of one-cell-at-this-LOD width).
for( int axis = 0; axis < 3; axis++ )
{
const int deltaMins = Abs( _bigger.mins[ axis ] - _smaller.mins[ axis ] );
const int deltaMaxs = Abs( _bigger.maxs[ axis ] - _smaller.maxs[ axis ] );
if( deltaMins < deltaMaxs )
{
if( _smaller.mins[ axis ] < _bigger.mins[ axis ] ) {
result[ axis ] = _bigger.mins[ axis ] - deltaMins;
}
}
else
{
if( _smaller.maxs[ axis ] > _bigger.maxs[ axis ] ) {
result[ axis ] = _bigger.mins[ axis ] + deltaMaxs;
}
}
}
}
return result;
}


Share on other sites

For each dimension, with box A ranging from Amin to Amax, and B from Bmin to Bmax, then it should be sufficient to calculate:

d = 0
if Amax < Bmax then d = Bmax - Amax // shifting A by a positive value to align with B's max edge
if Amin > Bmin then d = Bmin - Amin // shifting A by a negative value to align with B's min edge


(w/o having tested its correctness)

Edited by haegarr

Share on other sites

Oh ok, now i get what you mean, sorry.

But like deftware said, what you usually want is to snap each box as close to the camera as possible, or let's call it 'focus point' in case you pick the point on the planet which us closest to camera.

If you do this, you don't need to worry about containment - it will happen automatically. (Downside is that in the worst case you have to update all LOD levels at once, so you may still use the containment test to distribute work equally over frames when possible).

The only catch is that you move the clipmaps in units of (1<<lodLevel), so you don't sample between vertices seen in the previous frame.

Some pseudo code using integer bitmath:

for (int lod = 0; lod < 4; lod++)
for (int dim = 0; dim < 3; dim++)
{
int poi = (int) (myPointOfInterest[dim] + 0.5f);
if (lod) poi += 1<<(lod-1); // just for proper rounding
int clipMapCenter = ((poi>>lod)<<lod); // clear rightmost bits to ensure proper snapping per lod level
clipMap.center[dim] = (float) clipMapCenter;
}


Maybe that's the elegant solution you look for.

1. 1
2. 2
3. 3
Rutin
15
4. 4
5. 5

• 10
• 9
• 9
• 11
• 11
• Forum Statistics

• Total Topics
633680
• Total Posts
3013304
×