Log in

No account? Create an account
entries friends calendar profile It's Me Previous Previous Next Next
The Autobiography of Russell
Life from a different perspective
Wild Ideas: Automatic Box Connection (spaceship design)
Late last night I got a wild idea and decided to follow through with it. I wanted to see if I could take various rectangular shapes and connect them in some coherent manner, then increase the shape of the components and connection to create a body around all of it. I did all of this is JavaScript with Canvas. While I was creating it I stepped the function by time, making it look animated, which I thought looked pretty cool. I then took each frame and compiled it into one animation file.

As you watch the animation (it loops) you'll see two things. First a bunch of unconnected rectangular and square shapes have lines drawn between only the closest ones until finally all of them are one connected whole. After that the border is enhanced with an fading outline, giving the entire thing a fuller body. The ultimate idea was to automate the creation of spaceship designs from completely arbitrary components. The smallest boxes were added just to influence the final shape of the connections.

Animation of connecting close shapes and adding border

Performance-wise the most expensive operation is the feathering. That alone has six iterations, one for each pixel expanded layer, and takes ~240ms (40ms per pixel increase!) versus only 14ms for the entire area draw and connection finding and drawing algorithm. Minus that feathering, this is something that could even be done on-the-fly as boxes are moved around or added.

The next step in this will be to add a user interface to add boxes and move them around in a grid. At some point I'll post the full source code so that, if anyone desires, they can review it, provide critique and perhaps better ways of doing some of the things, etc.

Tags: , , , ,
Current Mood: accomplished accomplished

3 comments or Leave a comment
unspeakablevorn From: unspeakablevorn Date: March 7th, 2012 07:36 pm (UTC) (Link)
Feathering shouldn't take that long - your actual goal here should be to use the typical round-join line work to build the edges and then gradient-fill, with a modified line drawing algorithm, perhaps.

It will still take longer than the other steps.
zimzat From: zimzat Date: March 7th, 2012 08:51 pm (UTC) (Link)
This is my first "major" foray into any sort of graphics processing so I've probably done some things The Wrong Way™. Like, for instance, the original estimate of how long just the area drawing and connection finding/drawing took was off because that included re-parsing the entire JS file each time; I was doing some AJAX to immediately re-run the code in the background every time the file was updated rather than refresh the page, manually or automatically. The real find/draw time is averaging around 5ms.

The way it's feathering currently is iterating over all 800x600 pixels (rgba channels), checking if the current one isn't already visible, and checking if the four adjacent pixels are visible or not. It then adds them to a list of pixels to adjust once it's done, so it doesn't feed itself feathered data. It then does this 6 times slightly adjusting the color each time. It's not very smooth, though, and leaves some hard edges around corners.

I tried to find an algorithm to take an arbitrary shape and feather it, but I couldn't seem to find any. I need to do more research into what existing Canvas frameworks there are out there. I have the coordinates of the rectangles, and the coordinates of the lines, but haven't figured out how to take that and get a padded line around it. If you have any suggestions of what I should search for or anything else to read up on I'd be very appreciative.

I found some quick and dirty code to handle the mouse movement of rectangles so now I'm going to see about cleaning it and my code up some more and put it up somewhere. Well, later anyway; I have some paid work to take care of first.
unspeakablevorn From: unspeakablevorn Date: March 8th, 2012 01:51 am (UTC) (Link)
Look into Marching Squares - this gives you edge detection, and feathering, without the crying. You'll have to do some work to make it get all the inner holes.

Alternatively: do your drawing in several steps, drawing thicker lines and larger boxes, and gradually making them smaller and darker until you get to the actual desired width and size. No pixel detection there.
3 comments or Leave a comment