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

Nice one!
I had a chance to compare both versions: mine and yours. For some reason my script works a bit quicker against yours (set with 10 iterations). Here is a comparison test file: minbb-py-comparison-Ilja.gh (610.4 KB)
Both outputs (volume values, orientations of BB) are quite similar.



For my purposes, computational time is very critical so I even think to rewrite mine Python version with C# component to make it even more faster. But I just started to learn C# language…

2 Likes

If you use a fixed size array for the “new_vol_x” (and the other two), namely the size of the range count, then you can run ALL those rotations in a simple parallel.For-loop and assign the result into the array index of your current index, like so: “new_vol_x[i] = int(volume(new_bb))

That should probably be significantly faster. In C# that would look something like

    var new_vol_x = new int[180];
    System.Threading.Tasks.Parallel.For(0, 180, i => 
    {
        ...
        ...
        new_vol_x[i] = int(volume(new_bb));
    });
    // Aso.

By only assigning indexed slots ([i]) in the array, each thread in the parallel loop will handle each case (i) without conflating it with any other index (i) in another thread, and so it will not cause any data races or other spooky things.

// Rolf

2 Likes

Hi @ilmar_ik,

I tried to understand the code I have baisc c# understanding but dont know python.
You rotate it degrewise 180 degrees, rot_x is the degree with the smallest bBox?
I dont understand what in line 30 happens:

rot_x = new_vol_x.index(min(new_vol_x))+1 #degrees

Thanks

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

@RIL Thank you

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

1 Like

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

1 Like

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

2 Likes

I wish you the best of luck! :+1:

1 Like

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! :wink:

2 Likes

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

1 Like

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

// Rolf

1 Like

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 :smiley:
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.

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

3 Likes

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

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

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.
bild

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

7 Likes

What does that mean?

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

1 Like

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

3 Likes