Minimum oriented bounding box. Implementation in Grasshopper + Python script node

[ilmar_ik]

Hi @Baris,
Okay, I’ll try to explain.

1. I am rotating an initial plane around world X axis 180 times incrementally (starting from 0, 1, 2, … 180)
2. Then I am estimating volume values of generated bounding boxes (BB) after every rotation. Values are stored in a list [new_vol_x] which is outside for loop
3. with the list.index(min()) function I am extracting an index which refers to an angle of rotation which generated the minimum volume of BB.
   Here is some additional info: https://stackoverflow.com/questions/2474015/getting-the-index-of-the-returned-max-or-min-item-using-max-min-on-a-list

[ilmar_ik]

@RIL Thank you

[RIL (Rolf)]

Let us know if you gain better speed with a C# solution. It should be possible to get much better speed with only that little parallel-for enhancement, even with the rest of the code remaining pretty much the same.

If I had known Python better (I can only listen to it fluently…) I would have tried to convert your script into some really nasty C# version, but I’m not that Python guy.

// Rolf

[Baris]

thanks a lot @ilmar_ik,
I was wondering, cause I couldnt see you are sorting the array.

[Baris]

Actually I am trying to convert it in to a really nasty c# version, jeje.

[RIL (Rolf)]

I wish you the best of luck!

[ilmar_ik]

I found C# editor a bit confusing in comparison with Python editor in GH. Autocomplete in C# confuses me a lot. No additional help as we have in Python Node. But indeed, C# works way faster.
@Baris - good luck buddy!

[ivelin.peychev]

@ilmar_ik

Autocomplete in C# confuses me a lot.

And this is why I don’t use it The pre-filled code inside is also quite confusing

[RIL (Rolf)]

@ivelin.peychev

Autocomplete

If Autocomplete would be what is executing the final code, I’d also use Python/Autocomplete to run my stuff.

// Rolf

[ivelin.peychev]

Well, no, but it is a helpful thing when you don’t know the api by heart. In the case of csharp scripting component inside GH. That autocomplete is kind of useless since you have so much unclear text inside
Last time I decided to use it. I clicked one button several times. Then I clicked another button several times and my code suddenly got two times bigger.

There’s no way I’m using this thing, ever again.

[RIL (Rolf)]

I couldn’t resist trying to convert to C#. This is what I arrived at: 64ms instead of 516ms on my machine (an ol’ i7 3930, 3.2GHz, 6/12 threads, 32Gb):

The resulting minimal BoundingBoxes were not identical (mine were consistenly a little smaller):

The C# Parallel version, nearly 10x speed improvement (Edit: Replaced with R2)
minimalboundingbox-py2csharp_R2.gh (614.4 KB)

// Rolf

[RIL (Rolf)]

In the above example I used the original 180 degree rotations, but if using 90 degrees (see below) it’s faster (43 ms) and perhaps it also produces slightly better results(?). At least the mesh to the right looks sigificantly tighter (the volume indicator confirms the right mesh being smaller). In both cases it seems the MinBB’s are better aligned.

// Rolf

[Baris]

sorry, I was too lame
Now I can start studying the paralell solution.

[RIL (Rolf)]

BUGFIX
I had introduced a bug in the code, here a fixed version (R2). I also replaced the file in the previous post. (I had swapped a plane and an axis, now fixed). The fixed version really produces better alignment as well as good minimal volumes. I also added the option to adjust the angle increments. Default is 90 (degrees):

Very good alignments in my opinion.

minimalboundingbox-py2csharp_R2.gh (614.4 KB)

Edit: New version (R3) with commented and heavily refactored code (easier to follow the logic):
minimalboundingbox-py2csharp_R3.gh (614.2 KB)

// Rolf

[ivelin.peychev]

@RIL

refactored code

What does that mean?

[RIL (Rolf)]

Refactoring means like “Re-arranged” without modifying any logic. A bit like algebra in math, but with code instead. For example, all the for-loops was extracted into a separate method, and variables were renamed, etc. Any tidy-up work could be said to be “refactoring”.

See also the classic refactoring bible by Martin Fowler; https://martinfowler.com/books/refactoring.html

BTW, when converting Python to C# I tried to preserve the original logic as well as I could (except for the parallel loop), and so also after refactoring but, there seems to be something basically flawed with the code. Because the Rotate-method takes a “degree” (the variable i) which is not in Radians, which the method expects. Changing it to Radians ( Rotate(i * (Math.Pi/180) ) makes the whole thing go bananas.

In R4 I also added an Input for a more meaningful “initial Plane” (meaningful only for the meshes though) created from PlaneFit (from points), which gives better results.

But I don’t understand how this works at all when the Rotation espects Radians, not Degrees as it is now.

minimalboundingbox-py2csharp_R4.gh (614.5 KB)

< scratching head >

// Rolf

[RIL (Rolf)]

R5 (proper use of Radians)
Oh, now I know what the problem with the “failing” Radians was; The function returning the resulting degree didn’t also convert the returned value to Radians, but now it does (so this R5 will be the final version which works correctly):

  /// <summary>
  /// Returns the rotation (in radians) of the smallest volume. The parallel loop
  /// performs m_rotations rotations of 1º each (90 rotations is default)
  /// </summary>

 private double GetRotationAtMinimumVolume(GeometryBase geo, Plane start_plane, Vector3d rotation_axis)
  {
    var rotated_volumes = new double[m_rotations];
    // Let the .NET platform take care of spreading out the for-loop iterations on  different threads. 
    // To avoid data races we use local block variables inside the for-loop, and results are put into 
    // array slots, each result into its own index in the array, which prevents "collisions" (meaning,
    //  different threads overwriting each others values).
    System.Threading.Tasks.Parallel.For(0, m_rotations, i =>
    {
      // make new rotation of the original plane on each try
      var new_plane = start_plane; 
      new_plane.Rotate(i * TO_RADIANS, rotation_axis);
      // Since each thread works with different indexes (i), and when done, assigning
      // each result value into "its own array index", then no conflict can occur be-
      // tween threads so that any one thread would overwrite the result produced by
      // another thread, and therefore no data-races will occur. This is a red-neck
      // approach which ALWAYS works if the size of the array can be known in advance
      rotated_volumes[i] = geo.GetBoundingBox(new_plane).Volume;
    });    
    // now find that index (degree of rotation) at which we had the smallest BoundingBox
    var rotation = IndexOfMinimumVolume(ref rotated_volumes);
    return rotation  * TO_RADIANS; // Edit: Conversion should be placed here. Angle in Radians
  }

  /// <summary> Returns the index of the smallest volume recorded in the 
  /// array </summary>
  /// <param name="recorded_volumes"></param>
  /// <returns>Returns the index of the smalles volume, which also is
  /// equal to the degree at which this volume was achieved.</returns>
  private double IndexOfMinimumVolume(ref double[] recorded_volumes)
  {
    var min_index = -1;
    var min_value = Double.MaxValue;
    for (var i = 0; i < recorded_volumes.Length; i++)
    {
      if (recorded_volumes[i] < min_value)
      {
        min_index = i;
        min_value = recorded_volumes[i];
      }
    }
    return min_index; // Index is the same as the degree
  }

minimalboundingbox-py2csharp_R5.gh (614.6 KB)

// Rolf

[Philippe_HAMON]

Thank you all for this very helpful explanations and script! Nice work! I will use it to prepare rough wood blocks for wreathed handrails, for CNC cutting.

[RIL (Rolf)]

BEST PICK
I think it is important to point out that Mitch’ script (py) gives very good minimal volume results although it’s not the fastest, so depending on requirement (speed or accuracy) you should try out which one of the components gives what you need or want.

For a comparison i made a silly handrail, and converted it into a mesh (for the PlaneFit component, but in this case it didn’t help better the result) and tried all three components.

R6 Enhanced
I also enhanced the parallel version by allowing it to make smaller rotation attempts than whole degrees (1º) by increasing the steps (D) to greater than 180 steps. All rotations over 180 steps reduces the rotation with a factor (180 / rotations) while still covering a full 180º rotation series.
Out of curiosity I also added an input I (Iterations) which causes the internal algorithm to repeat itself I times by starting over with the resulting plane from the previous full round of rotation attempts as the initial starting plane.

Interestingly enough no improvment is gained by performing more iterations though, probably because any repeated rotations will only be identical to the previous ones. Modifying the rotation angle based on the interation value perhaps would make it effective, but I haven’t tried.

What works though is to increase the rotations (D) to a value over 180 (degrees), which will reduce the rotation degree to less than 1º whole degree. The important point is that by manually increasing this value - and carefully watch the resulting min volume - was the only way I could come close to the results produced by Mitch’ MinBB component (and even beat it in some cases). But I bet there are cases where your prio is smallest volume and you wouldn’t want to manually drag the slider until you find the smallest volume. And then Mitch’ component seems to be the best choice.

Anyway, here’s a very fast version (R6) which can compete with Mitch component, but only if you manually drag the D slider (which I did for the below screenshots) until you come close to, or perhaps even beat Mitch:

Fig 1. I have indicated the fact that incerasing iterations doesn’t improve the final result as “useless”.

The silly handrail in this test with almost identical results for the Parallel version (magneta) and Mitch (cyan):

The point being that sometimes an initial workpiece really needs to be as small as possible, to the extent that millimeters matters.

R6 with the more fine grained rotation steps (< 1º):
minimalboundingbox-py2csharp_R6.gh (703.5 KB)

Next (R7) I may try (if/when I have the time) to automate the gradual adjustment of the rotation degree which was done manually in the example above. Automating this seems to be the only way to beat Mitch in finding the smallest volume. - Applaud to @Helvetosaur (Mitch), everyone!

// Rolf

Edit: Fixed documentation in image and in the component code

[Philippe_HAMON]

Wow! Bravo! In case of wood pieces, the minimum volume is great, but the best goal is to have the minimum thickness, to avoid to avoid unsightly glue joints: