Saturday, February 11, 2017

Entry and Exit Points for Space Filling Paths on a Grid

I've been researching space filling curves recently and came across an interesting algorithm to generate curves for arbitrary areas. To be completely accurate, space filling curves cover the entire unit square in continuous space, whereas what I'm looking at is the discrete form that covers a grid. Below when a path or curve is mentioned, what is meant is a way to cover a rectangular area by moving one square at a time, either up, down, left, or right, without crossing over itself. The curve starts in one corner and ends in another.

Being almost completely new to this, I set about understanding the description of the algorithm. Although it was accompanied by code, details of the process were scant. The first part described rules for valid corner exit points given a starting point on grids with edges that are either odd or even. This is what I want to explore in this blog post.

A rectangular area can have an either odd or even width and an either odd or even height. There are 4 possible combinations of these edge dimensions and for each one, a set of directions were supplied. I didn't just want to take these at face value. Some sort of proof was needed.

Space Filling Curve Algorithm by Lutz Tautenhahn

The proof below doesn't say anything about the existence of a path/curve that starts at one corner and ends at another covering all squares. All it does is show if a path is possible or not. Although it's relatively easy to prove that a path can be found for all of the scenarios below, we'll leave that for another time.

So what are the results?  In grids with two even edges, a path can be found from a corner to either adjacent corner, but not to the diagonal corner.  In grids with an even and odd side a path can be found to the diagonal corner and the adjacent corner on the even side but not the odd side.  Finally in a grid with two odd sides a path can be found to any other corner except if one of the odd edges is equal to 1.  In that case the path is only diagonal or along the odd side that isn't one.  That last bit isn't in the proof but it's obvious.

Allow directions in a space filling grid

Proving the directions is straight forward. If you imagine that the corner start square of a grid is covered, and every time you move, another square is covered, it becomes obvious that there are (wh-1) moves until the entire space is covered. The total number of moves is also equal to the number of up, down, left, and right moves. If you want to move right side of the grid the number of right moves minus the number of left moves has to be equal to (w-1). If you want to stay on the left, the number of left moves is equal to the number of right moves.  Similarly if you want to move to the bottom of the grid, the number of down moves minus the number of up moves is equal to (h-1). If you want to stay at the top, the number of down and up moves mus t be equal. When these equations are combined the directions above can be found.

Grid movement proof

It was redundant to prove both the Odd-Even and Even-Odd case as they are a diagonal mirroring of the same scenario.  It's also sufficient to only show the paths starting at the top left corner as paths starting in other corners are vertical and or horizontal mirrors of paths in the top left corner.

Although I didn't end up using the curve filling path in the first image, it helped me understand some of the subtleties of curve generation.

Wednesday, February 1, 2017

Voronoi Stippling

I'm trying to write my own software to convert normal raster images to a corresponding stippled version.  If you're unfamiliar with the term, stippling is a style of artwork that that uses are large number of small dots to represent a scene.  Areas with a high density of dots appear darker, while areas without dots are white.  Normally I like to have reasonably good understanding of a subject before I do a blog post about it, but in this case I'll give a quick outline of what I'm trying to achieve and then fill in the details in a later post.

So, how do you get an image like this,
Stippled Image

From something like this.
Original Image

To start with I'm trying to replicate the process in a paper by Adrian Secord.

Weighted Voronoi Stippling
Adrian Secord
2nd International Symposium on Non-Photorealistic Animation and Rendering (NPAR 2002)

The first step is to generate a number of points equal to the desired number of stippling points in the final image.  They can be randomly distributed over the image, or ideally via a rough approximation, close to the locations of the stippling dots in the output image.  As the process I'm about to describe is iterative, the closer the initial approximation is the final output, the faster the algorithm will converge.

After the points have been created, their Voronoi diagram is generated.  A Voronoi diagram produces a region for each input point that identifies all the locations that are closest to that dot than any other.  There are some tricks to making sure that the regions around the boundary are properly created but in general it's a simple call to scipy.spatial.Voronoi

That's great, but the process so far hasn't taken the input image into account(unless you use it to generate the initial point locations).  Now that a number of points and their corresponding regions are created, the weighted centroid of the area is calculated.  The centroid then becomes the location of the new point.  This process of creating Voronoi diagrams and calculating centroids is repeated until some convergence criteria is met and is better known as Lloyd's Algorithm.

In the image below, the black dots are the initial points and the white dots are the centroids of the Voronoi regions after an iteration.
Voronoi Diagram
Voronoi Diagram with centroids
Overlaying this diagram on the original image helps to illustrate the process a little better.  Obviously the image below is sparsely stippled and the object isn't recognisable with only 64 points.

Voronoi Diagram
Voronoi Iteration

I've generated the next diagram with I think 256 points to explain a subtle point.  The Voronoi region for each point is a convex polygon.  Therefore its centroid will always be located within itself.  As the number of points increases the size of the regions decreases.  This means that the process will take a long time to converge as the points can only move a small amount during each iteration.   That's why you need to place the initial points as close to their final location as possible.  Or do you?

I only discovered this problem after programming my solution and needed a quick way to overcome it.  If a large number of points take a long time to converge then a small number should converge quickly.  So I started with only two points.  After a few iterations, each point splits, like a cell undergoing Mitosis.  Each point splits into two new points diametrically opposed on a unit circle centred on the old point.  The direction of the split is randomly chosen.  (I have a hunch that continually splitting in the same direction will cause artifacts that will delay convergence)  These new points are then iterated on for a while and then split again.  The key is to get the points close to where they need to be early and then converge and add the detail later.
Voronoi Diagram
Dense Voronoi diagram
I have some ideas I want to try to make the image better.  There are obviously some linearity problems with the output.  White parts aren't as light as they are should be.  My code is a mess too.  It needs a clean up.  I'm having fun though.

Tuesday, January 17, 2017

Arrange Rectangles with Python to Design a Carton

Recently I've been interested in cardboard boxes and how to design and model them.  In my last blog post I described how to create a box in Fusion 360.  It works but it's a cumbersome, frustrating, and time consuming process.  What was needed was a way to go from concept to template quickly.  After looking around and not finding a tool for the job, I designed one.  It's called rectangleBuilder.

Laying out a template isn't too hard once you get the hang of it.  Draw all the rectangles that make up the box you intend to build and then dimension them.  Then define relationships between all the rectangles.  An example of a relationship can be seen in the plan below.  The bottom middle of rectangle B is in the same location as the top middle of rectangle A.

Box Template Plan

This can be done by defining a Rectangle class in python,  It is initialized with its width and height and by default is placed with its bottom left corner at (0,0).  The Rectangle object is also aware of the position of all its corners and edge midpoints.  When called with a code for one of these points it returns the xy coordinates in list form.  For example, calling an object with the argument 'TM' will return the coordinates of the top middle.  All of this shorthand is explained in the code.

Python Code
Define rectangle sizes

This is the part that I think is really cool.  Positioning the rectangles by defining geometric relationships.  In the code below the bottom middle of rectangle A is positioned at the origin.  Rectangle B is then positioned so that it's bottom middle is in the same position as the top middle of rectangle A.  The last line demonstrates the offset feature.  It essentially says, place rectangle M so that its bottom left corner is in the same position as the bottom right of rectangle B then shift it in the y direction by an amount (t+b).  The few lines of code above and below completely describe the template for the box.

Python Code
Position rectangles

This data can then be used to generate an SVG template in python to see if everything is as expected.  The outline to cut is in black and the bend lines are marked in red.

Box Template
Box template

That's all well and good but how do we transfer that to cardboard?  I don't have a plotter or laser cutter so it has to be done by hand.  After some experimenting, the below instructions are the easiest way to describe the rectangle edges so that they can be easily drawn.  The y coordinate and the start and end x coordinates of the horizontal lines are listed in increasing y order.

Stats and Horizontal lines

The same process is repeated for the vertical lines as well.

Vertical lines

Take the piece of cardboard that you plan to use and draw a base line in the direction of the x axis.  At each end of this line draw perpendicular guides in the direction of the y axis.  Along each of these lines mark all the y coordinates from the horizontal line list using the base line as the zero point.  You can then draw the line segments in the following manner.  77.0 , (84.0 - 124.5) means place a ruler on the 77.0 marks you would have drawn in the last step with the 0 mark on the left guide.  Then draw a line from 84.0 to 124.5 on the ruler.  By working through the list the design will gradually appear.  The vertical list is supplied just to be complete and isn't really needed as the ends of the horizontal lines can be joined to form the rectangles.

Edge guides

The layout looks like the SVG file so everything worked out OK.

Box Plan
Box to cut out

The bend lines can be perforated with a tool like the one below that's used for transferring dressmaking patterns.

Perforated Cardboard
Perforated Bend Lines

Cut out the outlines with a scalpel.

Flattened box

When folded together everything works quite well.  You can see in the image below what my intention was.  The top extends over to cover the entire top and although not necessary is a fun little design challenge.

Cardboard Box
Top overlap

As it's a tight fit, the box needs to be taped together to stop it springing open.

Cardboard Box
Assembled Box

Everything seems to fit nicely.  A little tweaking could make things better, but I'm happy with it.  In the end the fit all comes down to how accurately the template is drawn and bent.  Folding across the corrugations is easy to get right, but folding in the same direction as the corrugations is hard and I need to come up with a better way to do it.  When folding with the corrugation it's not uncommon for the fold to follow the middle of the corrugation.  This could be a couple mm away from from the line.
Get The Code!


Thursday, January 5, 2017

Designing Homemade Cardboard Boxes in 3D CAD

I'm currently selling my old phone on eBay and I needed a sturdy box for shipping.  I could buy one, but why waste money on a box when I can get my hands on cardboard for free.  It was also important to make the package as small as possible to keep my postage fees low.  So the obvious choice was to make my own.

When I was young I used to make cardboard boxes for everything (That's right I was just as exciting then as I am now).  They were simplistic and held together with staples, but never anything too complicated.  So I thought that this would be a good opportunity to up my game and emulate how the professionals do it.

I don't know the name of the box I'm trying to make, but I'm certain you've seen one before.  Quarter circle shaped flaps on the lid slide into the sides, locking everything together.  Let's work backwards  and start with some photos of the final product.

Cardboard Box
Final Box
Cardboard Box
Quarter Circle Flaps
Cardboard Box
Side Slots
I'm quite happy with the result, but a few bits were cut off during assembly to make things fit.  I assume that this was due to the inaccurate way I transferred the pattern to the cardboard.  Tacking it onto the cardboard and scoring it with my wood marking knife was rough but worked..  My end goal was the template below that was transferred onto scrap cardboard and cut out to make the box.

2D Cardboard Box Template
To generate the template I used Fusion 360 from Autodesk.  Before starting, four parameters were specified, the thickness of the cardboard, the height, width, and depth of the box.  By using these parameters for dimensions, the design can be altered later.

The process is simple but frustrating.  Make 3D components for each part of the box and then define how they join together.  They don't have to be the right size, as long as they are close you can change them later.  Defining the joins is the hard part due to the software being uncooperative.  Once you have a 3D version of the template you can generate a 2D version to print.

3D Cardboard Box Template
The first thing you will need to think about is how to model bending cardboard.  To me, a good approximation was to assume that the midpoint of the material acts as a pivot point.  In the image below you can see the bend between the back (red) and top (yellow) of the box.  This means that when laid out flat they will meet in a butt joint and be easy to mark out.  You can then move forward by defining all joints between components using this assumption.  Your mileage may vary, but this seems to have worked for me.

Pivot Point Of The Faces
Now for the "fun" part.  Using the CAD package, assemble the box as you would in the real world by bending each joint one by one.  As you do this, make sure parts don't interfere with each other.  You may have to resize some.

Assemble a Box
Fold Up The Sides
Assemble a Box
Fold In The Internal Base Flaps
Assemble a Box
Fold Up The Side Flaps
Assemble a Box
Fold The Side Flaps Into the Box
Assemble a Box
Fold the Inner Side Flaps Into The Box Leaving Slots
Assemble a Box
Fold The Top Down
Assemble a Box
Fold In The Ears On The Sides
Assemble a Box
Insert The Ears Into The Slots

I think the results are pretty good.  If the cardboard I was using was flatter and I had transferred, cut, and bent the pattern with more care I think the results would be even better.  It would be great to get a pen plotter to draw the outline.  I kind of joke about going overboard and spending too much time on this but it was a conscious decision.  I got some more practice in 3D CAD and because the model is parametric it can be easily reused for other purposes.  At least the box from my computer case is being put to good use.

There was meant to be a nifty little animation of how assemble the box to go with this post but the motion study feature of Fusion 360 is a dumpster fire.  Que sera sera.

Saturday, December 24, 2016

LED Bunker Light Teardown

I recently picked up this LED bunker light for $33 and I thought it'd make an interesting tear down.

Bunker Light
AT5700 bunker light

When you remove the diffuser from the front the first thing you see is the PCB that holds the 32 LEDs.  Ideally you're meant to be able to loosen the screws and turn the PCB slightly and then lift it out, the only problem with that is that there isn't enough room to get your fingers down the side of the circuit board.  As it took me a couple of minutes to remove the PCB I'd suggest that in their next design iteration they route some indentations into the edge to allow you to hold onto the board.

Surface mount LEDs

The light is just a low power bunker light for non task illumination and is rated for outdoor and indoor use.

Box specifications

The LED driver is mounted to the back of the PCB and seems to be of the constant current type.  It's hard to tell but I think the voltage range of 12-25 volts indicates that it will regulate the output to 350mA and vary the voltage accordingly.  When measured the LEDs were drawing 350mA at 12V for a power of 4.2W.  The box indicates a power draw of 6 watts so the difference is likely to be what gets wasted in the driver.

LED Driver
LED driver specifications

The light was chosen because of its small size, almost too small in fact.  As we'll see later, the 70mm thickness doesn't leave much space for cabling.


The connector that supplies power to the board has a cover over its soldered terminals on the front side of the panel.  I assume that this is to prevent shorting occurring and not a safety thing as the voltages on the board are low and still accessible on the sides of the surface mount LEDs.  It's a good idea but I wish they'd put the same amount of thought into the installation process as it's quite hard.  Ripping a surface mount component off a board isn't that hard to do.

Insulator over connector solder points

The main problem I have is that the driver is mounted to the back of the LED PCB.  During installation you have to first connect the cabling to the terminal block.  This means that you need to leave about 8 inches of extra wire so you can get a screw driver in there before putting the board into the base and if you can't shove that extra cable into a wall or wherever the light is going, it has to be curled up inside the fitting and that's hard as there is only about 30mm of space behind the board.  I think a better solution would have been to mount the driver to the base of the fixture so that the driver can be wired in first and then connect the LED PCB via the header connector to the driver.  The connector on the PCB could be also moved to the front side to allow connection after mounting the LED board.  There is plenty of room, you just bring a small cable up the gap beside the PCB and connect it on the front side.

Rear of the PCB as it sits upside down in the base

Curious about how the LEDs were arranged I mapped out the layout of the board.  In the image below each different section of copper track has its own colour to clearly identify them.

Electrical layout of PCB

This shows that the 32 LEDs are arranged in 4 serially connected groups of 8 parallel lights.  I would usually have an issue with this because there isn't any form of load balancing, but I think the lights are under-driven enough that it isn't a concern.  I'll take a minute to explain that better.  If the LED driver is generating 12 volts with a constant current of 350 mA, you would assume that each component is getting 43.75mA at 3V, but due to manufacturing tolerances it's unlikely that the 350mA will get evenly split between the 8 LEDs in each group.  You then have a situation where one will be drawing more current than the others and if there isn't enough of a safety factor in the design it will eventually fail.  When this happens, the 350 mA will now be divided between the 7 remaining lights and another will fail this will continue until an entire group fails.  The reason that I'm not too concerned about this is that I think the packages are 2835 LEDs and they can usually handle more than the (0.04375 x 3) 131.25 mW per device.  The forward voltage of a white LED is usually considered to be above 3V.  This is what makes me think that to get the reliability they wanted, all they had to do was add extra LEDs to split the current and under drive each chip.  You would probably find that if there were only 7 LEDs in each group the higher current would cause the forward voltage to increase and instead of regulating at 12V, the driver may go to 13V.

LED schematic

It's not too bad for $33 but I think the design could be improved with only some minor adjustments.

Tuesday, December 20, 2016

Cron Based Discrete Event Simulator

In my last post I showed how to use the croniter package to find all the cron events that occur between two dates.  I wanted to see if it was suitable for integration into my discrete event simulator, and after a overhaul of the original simulator that's exactly what I've done.  To demonstrate the functionality it's helpful to have a real world scenario to model.


A programmer is addicted to energy drinks and every night at 8 pm they put all the empty cans on their desk in the bin.  Some days are more stressful than others so the number of cans taken out is a random number between 0 and 10 included.  The rubbish bin is emptied every Monday morning at 8 am.  The programmer only works from home January through April but the number of cans in the bin needs to be determined between December to May.  The amount of rubbish in the bin needs to be monitored every 30 minutes.

The first step is to define tasks that need to be performed.  They are simply functions that accept a variable describing the simulation environment.

Define Events

The parameters to initialise the simulator include a start time, an end time, and a default location.  The times are made up of a year, month, day of the month, hour, minute, second and an optional location that is a valid entry for the pytz package.  If no location is supplied for the times, the default location is used.  Other parameters specific to the state of the simulation are included as parameters.  Locations are needed as the underlying simulator uses unix timestamps as the timebase.  This prevents ambiguous time due to daylight saving and different time zones.  Essentially a time and date is useless information without a location.

Initialise the simulator

The tasks are scheduled to run via a cron string and a location for the event.  If a location isn't supplied the default simulation location is used.  You can also set a range for the cron events to run.  In the example below the log_data and the empty_rubbish tasks don't have start and end times so they run for the entire simulation.  The take_out_trash task runs for a shorter period of time and has defined start and end times.  The simulation is then run with the results logged to file.

Schedule Events

The results show that on one occasion there are at more than 50 cans in the bin.  This could be used to determine the size of a bin to buy if the current one is too small.  Let's say you have a bin that takes only 40 cans, it wouldn't be too much trouble to calculate the percentage of the time that there are more than 40 cans to be placed in it.  You may decide that it's acceptable for the bin to be overfull for a certain percentage of the time.  It's all about quantifying data from the simulation and using it to make informed decisions instead of just going by your gut.

Simulation Results

This is a work in progress and there are parts I want to improve, and although this scenario is simple I hope I've demonstrated the value of simulating a situation.
Get the Code!