# Given a deformed cube, find the closest undeformed cube

Given a deformed cube, how can I find the closest matching undeformed cube?

More precisely, given a deformed cube defined by its eight vertices $$\langle p_1,p_2,p_3,p_4,p_5,p_6,p_7,p_8 \rangle$$ and its radius $$r$$, how can I find the vertices of the nearest undeformed cube of the same radius such that the distance between the matching vertices of the deformed and undeformed cube is minimized?

To accomplish this, the following equation must be minimized:

$$E=\sum_{n=1}^8 \Vert p_n-u_n\Vert$$ where $$p_n$$ are the points of the deformed cube and $$u_n$$ are the points of the undeformed cube. But the equation must also be subject to the constraint that the points $$u_{1,2,3...8}$$ form a perfect cube of radius $$r$$. We can assume that the given cube is only slightly deformed, so that it is easy to tell which vertex matches with its undeformed counterpart.

I imagine this will involve some sort of numerical iterative procedure. Minimal computational cost is also desirable. Any ideas?

EDIT:

It's probably okay to assume that the center of the undeformed cube is the average of the deformed cube's vertices. Under this assumption, we only need to determine the rotation of the cube. Hopefully this simplifies the problem.

EDIT 2:

It looks like this is very similar to Wahba's problem.

• The solution may be not unique (+1, nevertheless) – ajotatxe Nov 23 '19 at 7:04
• How do you define the "radius" of a cube, deformed or otherwise? Is it something like the radius of the smallest enclosing sphere? – John Omielan Nov 23 '19 at 7:24
• @JohnOmielan The radius of a cube is typically half its edge length. It doesn't really matter in this question though, as long as the size of the undeformed cube is constrained by some means. – Daniel Williams Nov 23 '19 at 7:33
• Why not take avarage distance between vertices as side length – Ch.Siva Ram Kishore Nov 23 '19 at 7:51
• This is a standard Procrustes problem and can be solved without an iterative procedure. – user856 Nov 24 '19 at 5:40

OP: "If we assume that the center of the undeformed cube is the average of the points in the deformed cube"

Then there are only two variables—3D orientation—determining the eight $$u_n$$ coordinates of the cube. I did not have difficulty minimizing the sum of the Euclidean distances of the eight vertex distances, using Mathematica's FindMinimum[] function. A typical run is shown below.

Left: Deformed cube (light), unit cube (green) fixed on origin.
Right: Unit cube rotated (red vector) to minimize error.

I did not explore the entire landscape of orientations to verify that the min returned by Mathematica's function is truly the global min.

• Could you post some of your Mathematica code? – Daniel Williams Nov 24 '19 at 3:13
• Is there a way to determine how many iterations FindMinimum[] typically takes? – Daniel Williams Nov 24 '19 at 3:32
• @DanielWilliams: My code is nothing but FindMinimum[] with your error function, and variables $x,y$ to determine the tilt vector $(x,y,1)$. The number of iterations can be controlled, e.g., MaxIterations -> 100. – Joseph O'Rourke Nov 26 '19 at 16:39

Hint:

The problem has two-stages :
a) to "put in shape" the eight deformed points, that is to relabel them in such way that they individuate a cuboid (avoiding extreme torsion or tilting of the faces);
b) to separate the rigid-body motion from deformation, which is the object of the mechanics of deformable bodies in analyzing the strain.

I would approach part a) by
- finding four of the eight points which lie "almost" on the same face, i.e. which minimize $$det(x_k , y_k , z_k ,1)$$;
- fix one point as $$O'$$, and find the two edges with minimum dot product to get $$X', Y'$$;
- take the cross product of the two edges above as $$O'Z'$$, verify that the four points on the other face have a positive dot product otherwise exchange $$X',Y'$$;
- take the point on the other face closest to $$O'Z'$$ as $$Z'$$ and complete the appropriate labelling of the cuboid.

Then you can pass to stage b) and apply the tools of strain analysis, taking into account that lowest deformation energy means lowest total square deviation of the vertices.