CODEWITHSUNDEEP
algorithmunity-game-engine3dtrigonometry
Beppi's
Beppi's

Reputation: 2129

Algorithm to find the smallest box containing a set of 3D objects

This is a problem that I meet on Unity3D, but it's actually a request for help for a general graphical algorithm. I have a set of 3D objects/meshes that form a map. To generalize let's say that they are arrays of 6 numbers: position and size.

I need to create a box that contains all these objects. The box must have the minimum possible volume. To generalize, we can say that also the box will end to be an array of 9 numbers: position, size and rotation.

So at the end I'm talking about a function that takes a set of array[6] and returns an array[9].

The box can be obviously rotated in 3 directions as needed, so it's not just "take the smallest and the biggest x, y and z values".

Probably this question can some how easily resolved with a few trigonometrical functions, but i don't have any idea of how to do it! I only could create something that does that iteratively, but that's not what I want.

A particular case of this problem could be to find the minimum box containing a set of points. Probably this question is easier and some how can be extended to the main problem. Anyway... I can't solve neither this one! :)

Thanks for the help.

Upvotes: 1

Views: 1810

Answers (2)

Dhruv Kumar
Dhruv Kumar

Reputation: 11

You can find the 3d convex hull of all the vertex. Using the points of the convex hull you can form the faces of the convex hull. Then incline one by one all the faces parallel to x-axis. Then find the min x/y/z and max x/y/z along each face rotation.Calculate the volume using min x/y/z and max x/y/z. Find the index corresponding to the minimum volume. Rotate back this volume using the rotation you used for the corresponding face. This problem is similar to the 2d problem of minimum area rectangle. For minimum area rectangle the reference is https://gis.stackexchange.com/questions/22895/how-to-find-the-minimum-area-rectangle-for-given-points

Upvotes: 1

maraaaaaaaa
maraaaaaaaa

Reputation: 8193

Quick easy way to get the bottom left rear corner of your new box, and the top right forward corner.

Either:

List<GameObjects> gameObjects; // <-- your game objects here
List<Bounds> objectsBounds = gameObjects.Select(item => item.GetComponent<MeshRenderer>().bounds);

Vector3 min = objectsBounds.Min(item => item.min);
Vector3 max = objectsBounds.Max(item => item.max);

Or:

List<GameObjects> gameObjects; // <-- your game objects here
List<Bounds> objectsBounds = gameObjects.Select(item => item.GetComponent<MeshRenderer>().bounds);

Vector3 min = Vector3.one * Single.MaxValue;
Vector3 max = Vector3.one * Single.MinValue;
foreach(Bounds bounds in objectsBounds)
    if(bounds.min < min) min = bounds.min;
foreach(Bounds bounds in objectsBounds)
    if(bounds.max > max) max = bounds.max;

Upvotes: 0

Related Questions