CODEWITHSUNDEEP
algorithmvoxel
RobotRock
RobotRock

Reputation: 4459

Algorithm to encapsulate voxels/data in box

I have a cube with 8 variable corners. I also have a voxel data set which has all dimensions of same set size.

Does anyone know of an algorithm, to find the smallest possible area (and with that all 8 corner positions) for the cube while the cube still encapsulates all the voxels?

Preferably a not too heavy algorithm.

Upvotes: 1

Views: 683

Answers (2)

DrV
DrV

Reputation: 23540

j_random_hacker already gave a good answer with cuboids aligned with axes, cubes aligned with axes, and spheres. However, if you really want to find the optimal cuboid, the algorithm becomes much more complicated.

I will assume you have a set of voxels in a grid. If your voxels represent a solid or form a dense cloud, you may want to create a set of voxels which represents the outer shell of the shape. The inner voxels are not important when creating a convex hull (whether it is a sphere or any convex polyhedron).

One possible method for this is:

  • for each line along X-axis find the elements with smallest and largest X coordinate, and remove all elements between them
  • repeat the same for lines along Y axis and lines along Z axis

If this sounds odd, think of the geometry. If you try to draw a plane outside the solid (or), the plane can never reach to any of the middle positions along a line, so no points which are on a line segment between two other points can help to create a tighter fit. (This is not an optimal algorithm in the sense that it would not leave unnecessary points to the set, but it is easy and fast.)

If you want to create a polyhedron containing all points, you create it from a set of planes (6 in the case of a cuboid). A plane is quite simple in the sense that for any optimal limiting planes the following holds true:

  • all points are at a non-negative distance from the plane (i.e. on the same side)
  • there is at least one point on the plane (zero distance)

The distance from a point to a plane is a very simple calculation (ax+by+cx+d for each point). Finding the limiting plane at each direction is thus a relatively fast and easy O(n) operation (where n is the number of voxels remaining).

Worse news is that picking the correct directions for the planes is not easy. I do not know if there is an optimal algorithm for this, but I can only think of clumsy or slow algorithms with either a lot of brute force calculation (plane distances at many directions) or iterative guessing.

Even these may be useful, but really the question remains: why? There might be better ways than trying to make a small cuboid.

Upvotes: 0

j_random_hacker
j_random_hacker

Reputation: 51316

If you mean a cuboid -- a 3D shape with 6 rectangular faces -- and if these faces must be aligned with the axes of your voxel data, then this is just the (3D) bounding box. All you need to do is calculate the minimum and maximum values of the x, y and z co-ordinates of every voxel in your dataset. Taking all 8 combinations of {minimum, maximum} for these 3 dimensions will give you the co-ordinates of the 8 corners, although you would normally record just the two points (min_x, min_y, min_z) and (max_x, max_y, max_z), which completely describe the shape.

If the shape must be a cube (i.e. all dimensions equal) then you will have to increase the size of the 2 smaller dimensions to the size of the largest.

If you're looking for shapes to bound volumes with that you can use for efficient intersection testing (with points, lines, planes or other bounding volumes) then another good choice is a sphere. The intersection test between two spheres is particularly simple: all you need to do is check whether the distance between their centres exceeds the sum of their radii.

Upvotes: 1

Related Questions