GE5 - nester

This is where the magic happens. The class Nester is our engine where we encode our list of instructions to nest or pack our furnitures into a given room.

Basic class Nester’s structure

The Nester class’s main ingredients to produce a layout are the following:


Where,

the TypeHint for the newly created class that we are feeding to the Nester component will be of type ghdoc Object ⚠️!

The basic python code for the class is the followin:

import Rhino.Geometry as rg
import Rhino as r
from Grasshopper.Kernel import GH_RuntimeMessageLevel as RML
import Grasshopper as gh

TOLERANCE = r.RhinoDoc.ActiveDoc.ModelAbsoluteTolerance

class Nester:
    def __init__(self,
                 room,
                 furniture_list,
                 step=100.  # mm
                 ):
        # All the custom objects need to be duplicated to avoid to modify the previous objects in
        # the grasshopper flow.
        self.room = room.Duplicate()
        self.furniture_list = [f.Duplicate() for f in furniture_list]
        
        # This parameter represent the step for nesting, or how much you divide the room contours.
        # Implicitly this define the definition of the nesting operation.
        # we limit the division by 100 and the step indicates the unit length in millemeters.
        self.step = max(100, step)
        
        # This parameter is the outcome of the the nesting operation: the transformed furniture objects.
        self._furniture_nested_list = []


The structure is simple, besides the fact that we created an internal property self._furniture_nested_list to store output our new furnitures. But why do we immediately duplicate the input list of furnitures? If we don’t we would apply the transformations to the same object and we would modify the original object, remember: when you apply transformation to geometries, in GHPython, everything needs to be copied 🐇🐇.

Furniture class’s methods

Concerning the methods, we will have one main method that we will expose to be called: the compute(self) method. This is where the nesting take place! For better readability and organization is often convinient to split a bigger function such this one in muliple smaller ones wraped in the compute(self) method. But before going into that let’s take a moment to design our nesting mechanism.

The compute(self) method 🪑

Here we need to design and implement our own nesting algorithm, yes we used that word and you can too. An algorithm is a set of pre-defined operations involving calculations to solve a problem, in our case: placing authomatically a list of furnitures. So without further due, let’s list our operations in order to nest the furniture. Our algorithm can be divided in 3 big chunks:

These 3 steps define exactly our 3 sub-methods wraped by compute(self):


def compute(self):
    # (a) get furniture placement planes on the room walls by the given step size
    pool_planes = self._compute_planes_pool(room_sides, step)
    
    # (b) iterate through the input list of furnitures and check collision between
    self._nest_furnitures(furnitures, pool_planes)
    
    # (c) check if all the furnitures are placed
    self._check_sanity_nesting()


Before going into coding it’s always good to try to define as much each intermediary steps. The more information you will add at this point to your design the easier will be to code it out.

(a) get furniture placement planes on the room walls by the given step size
(b) iterate through the input list of furnitures
    (b.0) iterate through planes
    (b.1) orient furniture
    (b.2) check collision between furniture bounding rectangle and ...
        (b.2.1) room contour
        (b.2.2) room obstacles (closed curve)
            (b.2.2.1) we need to check if the furniture is inside the obstacle
            (b.2.2.2) check if the obstacle is inside the furniture
            (b.2.2.3) we check for the furniture-obstacle intersection
        (b.2.3) add currently place furniture to the furniture list
    (b.3) break the loop when the correct placement is found and collect nested furniture
(c) check if all the furnitures are placed


It’s also useful to sketch a small dataflow which resume our design:


Enough planning, let’s dive into coding. We are going to see in details each of the 3 functions that compose our method compute(self).

(a) _compute_planes_pool(self, room_sides, step)

As said this function allows us to obtain all the possible planes out of the Room’s contour to place furnitures.


def _compute_planes_pool(self, room_sides, step):
        pool_planes = []
        for s_polyl in room_sides:
            s_crv = s_polyl.ToNurbsCurve()
            s_crv_params = s_crv.DivideByLength(step, True)
            s_crv_params = s_crv_params[:-1]
            
            axis_x = s_polyl.Direction
            axis_y = rg.Vector3d.CrossProduct(axis_x, rg.Vector3d.ZAxis)
            
            for s_crv_p in s_crv_params:
                plane = rg.Plane(s_crv.PointAt(s_crv_p), axis_x, axis_y)
                pool_planes.append(plane)
        return pool_planes


The implementation is rather simple. We iterate through the room’s sides and we divide each one of by the step length. Next, for each point on the curve we create a plane defined by:

Finally we return the list of planes.

(b) _nest_furnitures(self, furnitures, pool_planes)

Here’s the core of our nesting method:

def _nest_furnitures(self, furnitures, pool_planes):
        for idx, geo_t in enumerate(furnitures):
            
            # (b.0) iterate through planes
            for apln in pool_planes:
                
                # (b.1) orient furniture
                geo = geo_t.Duplicate()
                xform = rg.Transform.PlaneToPlane(geo_t.plane, apln)
                geo.Transform(xform)
                
                # (b.2) check collision between furniture bounding rectangle and ...
                obr = geo.access_area
                is_intersected_obs = False
                
                # (b.2.1) room contour
                ## check the furniture intersection with the room
                obs_intersect = rg.Intersect.Intersection.CurveCurve(obr,                                           # first curve
                                                                     self.room.get_offset_contour().ToNurbsCurve(), # second curve (casted polyline)
                                                                     TOLERANCE,                                     # interection tolerance
                                                                     TOLERANCE                                      # overlap tolerance
                                                                     )
                ## if there is intersection continue
                if obs_intersect.Count > 0:
                    continue
                
                for obs in self.room.obstacles:
                    
                    # (b.2.2) room obstacles (closed curve)
                    ## (b.2.2.1) we need to check if the furniture is inside the obstacle
                    if ( rg.PointContainment.Inside == obs.Contains(obr.PointAt(0),rg.Plane.WorldXY,TOLERANCE) ):
                        is_intersected_obs = True
                        break
                    
                    # (b.2.2.2) check if the obstacle is inside the furniture
                    if ( rg.PointContainment.Inside == obr.Contains(obs.PointAtStart,rg.Plane.WorldXY,TOLERANCE) ):
                        is_intersected_obs = True
                        break
                    
                    ## (b.2.2.3) we check for the furniture-obstacle intersection
                    obs_intersect = rg.Intersect.Intersection.CurveCurve(obr,       # first curve
                                                                         obs,       # second curve
                                                                         TOLERANCE, # interection tolerance
                                                                         TOLERANCE  # overlap tolerance
                                                                         )
                    if obs_intersect.Count > 0:
                        is_intersected_obs = True
                        break
                    
                # (b.2.3) add currently placed furniture to the furniture list
                if not is_intersected_obs:
                    self._furniture_nested_list.append(geo)
                    self.room.add_obstacle(obr)
                    break


Although it might look complex the whole function is based on collision detection thanks to the Rhino method rg.Intersect.Intersection.CurveCurve(). In fact, by simply checking bounding box collisions we are able to detect if the furniture can be placed or not, both for the room’s contours and obstacles. ⚠️ Note that if the furniture, it’s added to the list of collisions, this allows our system to be aware of the placed furnitures during each loop ⚠️. Remeber: for and while loops together with break conditions are ones of your most valuable friends in GHPython.

(c) _check_sanity_nesting(self)

This is our little safety check at the end that all furnitures are placed. If not a warning flag is raised for the component. This is just an example but you could add many other types of sanity checks at the end.

def _check_sanity_nesting(self):
        if (len(self.furniture_list) != len(self._furniture_nested_list)):
            ghenv.Component.AddRuntimeMessage(RML.Warning, "Not all the furniture could be placed")

The final code

And to resume everything contained in the GHPython for the Nester class:

import Rhino.Geometry as rg
import Rhino as r
from Grasshopper.Kernel import GH_RuntimeMessageLevel as RML
import Grasshopper as gh

TOLERANCE = r.RhinoDoc.ActiveDoc.ModelAbsoluteTolerance

class Nester:
    def __init__(self,
                 room,
                 furniture_list,
                 step=100.  # mm
                 ):
        """
            __init__() is the constructor for the Nester class.
            
            :param room: (Room) The object of the room
            :param furniture_list: (List(Furniture)) The list of the furnitures
            :param step: (float) The length of the step to which the room is divided.
            It indicates the resolution/precision of the nesting operation.
            
            :return: the Nester object
        """
        # All the custom objects need to be duplicated to avoid to modify the previous objects in
        # the grasshopper flow.
        self.room = room.Duplicate()
        self.furniture_list = [f.Duplicate() for f in furniture_list]
        
        # This parameter represent the step for nesting, or how much you divide the room contours.
        # Implicitly this define the definition of the nesting operation.
        # we limit the division by 100 and the step indicates the unit length in millemeters.
        self.step = max(100, step)
        
        # This parameter is the outcome of the the nesting operation: the transformed furniture objects.
        self._furniture_nested_list = []
    
    
    def _compute_planes_pool(self, room_sides, step):
        """
            This function compute all the possible placement planes on the room contour
            
            :param room_sides: the sides of the room as Crv datatype
            :param step: the dividing step for the segments
            
            :return: (List(Planes)) a list of all the planes of the room's contour where furniture can be placed 
        """
        pool_planes = []
        for s_polyl in room_sides:
            s_crv = s_polyl.ToNurbsCurve()
            s_crv_params = s_crv.DivideByLength(step, True)
            s_crv_params = s_crv_params[:-1]
            
            axis_x = s_polyl.Direction
            axis_y = rg.Vector3d.CrossProduct(axis_x, rg.Vector3d.ZAxis)
            
            for s_crv_p in s_crv_params:
                plane = rg.Plane(s_crv.PointAt(s_crv_p), axis_x, axis_y)
                pool_planes.append(plane)
        return pool_planes
    
    
    def _nest_furnitures(self, furnitures, pool_planes):
        """
            This function compute all the possible placement planes on the room contour
            Here's the subset for this step:
                (b.0) iterate through planes
                (b.1) orient furniture
                (b.2) check collision between furniture bounding rectangle and ...
                (b.2.1) room contour
                (b.2.2) room obstacles (closed curve)
                (b.2.2.1) we need to check if the furniture is inside the obstacle
                (b.2.2.2) check if the obstacle is inside the furniture
                (b.2.2.3) we check for the furniture-obstacle intersection
                (b.2.3) add currently place furniture to the furniture list
                (b.3) break the loop when the correct placement is found and collect nested furniture
            
            :param room_sides: the list of furnitures to be placed
            :param pool_planes:  a list of all the planes of the room's contour where furniture can be placed
        """
        
        for idx, geo_t in enumerate(furnitures):
            
            # (b.0) iterate through planes
            for apln in pool_planes:
                
                # (b.1) orient furniture
                geo = geo_t.Duplicate()
                xform = rg.Transform.PlaneToPlane(geo_t.plane, apln)
                geo.Transform(xform)
                
                # (b.2) check collision between furniture bounding rectangle and ...
                obr = geo.access_area
                is_intersected_obs = False
                
                # (b.2.1) room contour
                ## check the furniture intersection with the room
                obs_intersect = rg.Intersect.Intersection.CurveCurve(obr,                                           # first curve
                                                                     self.room.get_offset_contour().ToNurbsCurve(), # second curve (casted polyline)
                                                                     TOLERANCE,                                     # interection tolerance
                                                                     TOLERANCE                                      # overlap tolerance
                                                                     )
                ## if there is intersection continue
                if obs_intersect.Count > 0:
                    continue
                
                for obs in self.room.obstacles:
                    
                    # (b.2.2) room obstacles (closed curve)
                    ## (b.2.2.1) we need to check if the furniture is inside the obstacle
                    if ( rg.PointContainment.Inside == obs.Contains(obr.PointAt(0),rg.Plane.WorldXY,TOLERANCE) ):
                        is_intersected_obs = True
                        break
                    
                    # (b.2.2.2) check if the obstacle is inside the furniture
                    if ( rg.PointContainment.Inside == obr.Contains(obs.PointAtStart,rg.Plane.WorldXY,TOLERANCE) ):
                        is_intersected_obs = True
                        break
                    
                    ## (b.2.2.3) we check for the furniture-obstacle intersection
                    obs_intersect = rg.Intersect.Intersection.CurveCurve(obr,       # first curve
                                                                         obs,       # second curve
                                                                         TOLERANCE, # interection tolerance
                                                                         TOLERANCE  # overlap tolerance
                                                                         )
                    if obs_intersect.Count > 0:
                        is_intersected_obs = True
                        break
                    
                # (b.2.3) add currently placed furniture to the furniture list
                if not is_intersected_obs:
                    self._furniture_nested_list.append(geo)
                    self.room.add_obstacle(obr)
                    break
        
    
    
    def _check_sanity_nesting(self):
        """
            This function checks if all the furnitures could be placed. If not it raise a warning message
        """
        if (len(self.furniture_list) != len(self._furniture_nested_list)):
            ghenv.Component.AddRuntimeMessage(RML.Warning, "Not all the furniture could be placed")
    
    def compute(self):
        """
            The definition is in charge of nesting the furniture. It's where the magic happens!
            This is how it works in order:
                (a) get furniture placement planes on the room walls by the given step size
                (b) iterate through the input list of furnitures
                (c) check if all the furnitures are placed
            
            :return: (List(Furniture)) The list of the nested furnitures
        """
        
        # (a) get furniture placement planes on the room walls by the given step size
        pool_planes = self._compute_planes_pool(self.room.contour.GetSegments(), self.step)
        
        # (b) iterate through the input list of furnitures and check collision between
        self._nest_furnitures(self.furniture_list, pool_planes)
        
        # (c) check if all the furnitures are placed
        self._check_sanity_nesting()


if __name__ == "__main__":
    # >>>> your code runs only here <<<<
    
    # instantiate the Nester class and run the compute function
    nester = Nester(room=i_room,
                    furniture_list=i_furniture_list,
                    step=i_step)
    nester.compute()
    
    # (optional) convert list of lists of furniture display curves to a datatree, because list of lists are not readable by grasshopper 
    datatree = gh.DataTree[rg.Curve]()
    for idx, g in enumerate(nester._furniture_nested_list):
        datatree.AddRange(g.geo4display, gh.Kernel.Data.GH_Path(idx))
    
    # output
    a  = datatree


* The extra mile

🎉🎉🎉 That’s it! 🎉🎉🎉

Note that this is just a very basic implementation of what a furniture plan nester could be. Let’s not even talk about ML-based nesters.

If you are interested in this topic have a look at what exist already on the market such as PlanFinder or Finch.