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