Thursday, 17 January 2013

Variable density circle packing to approximate bone cross section - WIP 1

Currently looking into generating infill patterns for 3D printing that have variable density and an internal structure similar to bone. Been pondering this one for over a year, but finally got round to writing some code.

First stage in this process is to develop a robust sphere packing algorithm, the spheres will later be "sliced" in some way to generate the infill. Not sure what I'll try first, but perhaps a veronoi tessellation followed by printing each face of the resulting tessellation. Short cut may be to merge the spheres back into an existing model (via OpenSCAD, or directly modifying the STL) and then slicing as per normal... along the lines of Gary's experiment: thoughts-on-fill-algorithms/

For now, the short video below shows the WIP algorithm operating in 2D (as it's easier to debug before moving into 3D).

High level algorithm models the cells as soft-bodies, with a repelling force acting between close neighbours. The repelling force is non-linear, with a sharp drop-off at the cells "boundary". Cells start small and attempt to grow to a target radius based on their distance from the boundary of the object. Cells undergo mitosis (split into two) under certain conditions: 1) they have no close neighbours 2) there is a sufficient gap (3 units in the demo video) between the cell and all of it's neighbours.

For each iteration of the algorithm:
1) inter-cell forces are calculated
2) cell locations are updated, taking into account collisions with other cells (soft collision) and the object boundary (nullifies velocity component orthogonal to the boundary)
3) mitosis conditions are evaluated, cell splits if appropriate
4) cell updates it's radius based on distance to neighbours (e.g. only grows if there's room)

Video is showing every iteration of the algorithm - it runs much faster in real time, but performance judgements are not really relevant yet, as it's far from optimised and only in 2D. Key challenge is a robust way of judging the end of the convergence...

1 comment:

  1. Nice work, but have you optimised the surface strength to density ration but not the global strength of the object? Does it also need some bones?

    Try setting the circle size by using the following gradient as a guide.

    Rasterize the shape,

    Trace the boundary, masked by the shape's boundary and then apply a blur with a large radius (some proportion of the object scale), equalise the result if required.

    On a new layer apply a skeleton filter (see G'MIC) referencing the blurred image in the layer below.

    Blur the skeleton image and then combine with the other layer to form a new layer that is a composite of the two.

    Use this composite layer to bias the size of the circles. The result should give you a distribution of voids that result in a greater density of material both near the surfaces and along lines that form a near optimal bracing network or skeleton in the interior of the object.

    Then work out how to do this in 3D. :-)

    Rasterizing the entire object to voxels at a resolution that matches the maximum precision of the printer may offer a paradigm that is better suited to solving these sorts of problems, even if the voxel file is just used to influence the probability of a G-code path position in the final file sent to the printer.

    There is also some interesting ideas in the paper titled "Trabecular bone adaptation with an orthotropic material model"