Sign in to follow this  

Find the minimum translation to fit one box inside another

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?
 
Yh4dhQCl.png
 
(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.
 
OWH0E9dl.jpg
 
(in this image crack patching is not finished yet:)
mbPSfS2l.png
 
(apparently, clipmaps were first used for rendering planets in "Alien" [1979]:)
paxdfWel.jpg
 
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 this post


Link to post
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 this post


Link to post
Share on other sites
Posted (edited)

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 this post


Link to post
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).

 

Thanks for the answers, anyway.

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 this post


Link to post
Share on other sites
Posted (edited)

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 this post


Link to post
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.

Share this post


Link to post
Share on other sites

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now

Sign in to follow this