You are not Logged In! -- Please consider creating an account. (It's free!)
This is the BETA version of the Articles Library -- Expect occasional bugs -- Report them to Daemon_Lotos => [Here]
[ Articles Home | Newest Articles | Submit an Article ]
[ Random Article | Search Articles ]

WeaveMaker Automatic Weave Generator Program
Article © MAIL User: Inventor

WeaveMaker web link: http://www.freedomodds.com/WeaveMaker.html

POV-Ray web link: http://www.povray.org/


Image: weavemaker1.jpg

A Gift
I have a little gift for you. It's a software gift, the kind of gift that you create yourself sometime in a frenzy of creativity and then give to the world in the hope that you did a good thing and made life just a little bit better. Call it a holiday gift since 'tis the season at the time of this writing.

With this software you can make movies of maille that are kind of like slide shows plus you can create your own new maille weaves. Most folks, however will be content to just look at the pictures and skim over the words and feel content knowing that someone somewhere is doing stuff like this, which is fine. This article gets kind of technical so if your eyes blur, just skim over the details.

About the Program
So you say it makes chainmaile weaves, eh, well how does it do that? It does it with randomness, a genetic optimization algorithm, and some tests that evaluate whether a weave is physically possible or not. Using these features, WeaveMaker creates arrangements of rings and tests them each, getting better at guessing over time until a solution weave is found. We'll get into all that later in the article.

I had been thinking on occasion of writing such a program and perhaps letting it percolate in my mind. Then one day I didn't have much to do so I decided to give it a try. Pretty soon I was generating random segments of rings all fused together in a blob. Not much but it was a start. I named the program WeaveMaker, to be descriptive of its purpose. Then I gradually shaped the code like a clay sculpture, adding new chunks of code and smoothing the whole thing out over and over again until it reached a good stopping point, which is now.

WeaveMaker is freeware, protected by the GNU General Public License. You are free to do anything you want with WeaveMaker, including make a profit, as long as you keep my name in the credits of the software and mention that you used WeaveMaker when you do your weave submissions. Naturally, if you used WeaveMaker as part of your creative process you would want to mention it in the weave submission anyway, I suppose.

I track WeaveMaker versions by adding a number, like this: WeaveMaker30.pov, for the 30th revision. I also keep a file WeaveMaker.pov with the latest version on my web space. I currently keep the file here:

http://www.freedomodds.com/WeaveMaker.html

So that's the file to get for the latest version at any given time. I encourage you to copy the file and put it on your webspace if you like so that the program does not get lost someday. WeaveMaker runs on POV-Ray which is freeware and cross-platform. The program is a 1,000 line text file that you load into POV-Ray, then you can scroll through it for just a moment and admire it's deeply nested loops and xyz indexing, "wow what well written code" you say to yourself! What shall we do with it?

Running WeaveMaker
Why, let's make some weaves! In particular we will make some spiral weaves. To do that, all you have to do is run WeaveMaker because it's all set up to make spirals in the released version. Start up POV-Ray, go to file/open and open up the WeaveMaker.pov file. Then pull-down the Render menu and select Render to render the image. The user interface varies slightly on different operating systems, but you'll figure it out. After some computation time, you will be treated to a spiral image like the one below.

Image: weavemaker2.jpg

WeaveMaker will always make that same weave on the first screen. To get more weaves you need to make a movie. On a Mac you do that by first selecting the source code window then going to the Edit menu and pulling down to the last entry which says WeaveMaker.pov Settings... You can then set up the animation and the animation file type on the tabbed window that pops up. I do not know how to do this on a PC. Some users have set this up with an ini file, but I think you can do it with the pulldown menus because my nephew and I did that once a long time ago. But anyway, make it do an animation and you will get however many weaves as frames in the animation. I like to set it up for a custom frame rate of one frame per second to make the movie into a slideshow.


Selecting the Weave Type
At the very top of the WeaveMaker.pov file is a section of optimization selection switches. You need to have at least one of these set to 1 and the others set to 0. We just did a spiral optimization, so let's try something a bit more challenging. Select the half-persian optimization and run WeaveMaker again. After a much longer wait you'll get some weaves like this one:

Image: weavemaker3.jpg

which is half-persian 3 in 1, and you'll also get some trivial weaves. Sometimes a less than useful weave meets the acceptance criteria and out pops a trivial weave. One of the reasons for this is that WeaveMaker is not yet able to distinguish between a linked ring and a ring that touches into the disk of another ring's interior without being linked. So sometimes rings stacked like coins or at sharp angles look like linked rings to WeaveMaker. When that happens, a trivial weave can get into the population of solution weaves or become an accepted solution weave and get drawn. I need to fix that, but if I hadn't drawn the line somewhere I'd never have gotten this article done for the holidays.

At any rate, it's cool that WeaveMaker can discover the half-persian 3 in 1 weave as an indicator that it actually works. It has found HP 4 in 1 this way also.


Randomness
To create a new proposed weave, WeaveMaker uses a pseudo-random number generator. Once seeded with a seed value, this generator cranks out numbers that determine the selection of ring size, ring position and rotation, as well as spin and distance. That's enough to fully characterize a given weave. At first all that WeaveMaker did was random generation, but it was very computationally intensive to just shotgun it like that, so I added an optimization algorithm which is described in the next section.


Optimization
WeaveMaker has a Genetic Optimization Algorithm, which means that it maintains a population of solutions and evolves them like a species in nature. There are lots of ways to code genetic algorithms, and any particular implementation will have its own unique characteristics. The main idea, though is to treat each proposed solution to the problem as a member of a society of some species and to evolve the species toward better problem solutions. The optimizer works like this:

The numbers that describe each candidate solution weave form the gene code and the program also remembers how good the solution weave is and what it's age is. There is one birth every cycle and a probability-based death function to model birth and death in the population. Also mating is modeled, with the generation of new solutions being a cross operator that randomly selects gene codes from either parent. A mutation function adds variety to the birth process, helping to prevent population stagnation at times.

Once the optimization parameters are set in the control parameters code section, the optimizer has all the information it needs to search the space of possible solutions essentialy endlessly until one is found. It begins with a certain population size and starts counting time, generating random population members to fill in the population, then the optimizer kicks in and starts generating the new solutions with the cross and mutation operators. A temperature variable decays as an exponential with a time constant.

The mutation probability and the mutation size are a function of temperature, changing dramatically at first and then not so much later. This establishes an annealing of the solution population over time. This annealing process means that initial guesses vary wildly throughout the solution space, the better ones get remembered in the population, and at the end of the cycle fine tuning of the solution weaves occurs.

If the optimization algorithm's temperature falls below the min_temperature threshold, then it will restart the optimization with twice the population size and twice the time constant. So each try it takes more time and works with a bigger population, both of which improve the solution searching ability at the cost of more computation time. This increase goes on indefinitely if a solution is never found, so let it crunch away and it will do it's best!

If a lot of the above sounds like technical gibberish, just know that it describes the particular way in which the program models a genetically evolving species. It's not really all that complicated once you get used to all the terms and how they work together.


Sheet and Volume Weaves
I planned ahead when coding WeaveMaker to do things in such a way that sheet and volume weaves would be possible. It turned out to be fairly simple, just one day's work to expand the program from one dimensional chain weaves to 2 and 3 dimensions. Naturally, however, the computation time went up dramatically in response. To tell WeaveMaker to generate a sheet or volume weave, simply adjust the num_segments and num_seg_checks vectors accordingly. Leave a 1 representing only one segment in any undesired dimension, and change the values in a desired dimension to greater than one.

Set num_segments to 3 or greater in each desired dimension. For num_seg_checks I recommend a value of 3 in each dimension unless you have spiral enabled in which case num_seg_checks should be equal to num_segments. For example, here is what you might do for a 7x5 horizontal sheet weave without spiral enabled:

#declare num_segments = <7, 1, 5>; // number of segments
#declare num_seg_checks = <3, 1, 3>; // number of segments to check

This would produce a weave that is 7 units wide, 5 deep, and 1 tall, with the first 3x3 box being checked. In fact, let's select just such a weave exploration now by going to the top of the file and enabling european_optimization. Let WeaveMaker chew on that for a while and you will be rewarded with weaves like the one shown below.

Image: weavemaker4.jpg


The Hyperbox
When I studied optimization algorithms in school, I learned about this thing called the hyperbox. It is a way of describing the box in which a solution space is confined. They use the hyper- prefix because the box can be any number of dimensions. In WeaveMaker the hyperbox is defined by ring selection, ring position, ring rotation, spiral and segment distance. Also the number of dimensions and number of rings are part of the hyperbox.

I'm telling you about the hyperbox because the way you get WeaveMaker to look for a meaningful weave in a reasonable amount of computation time is by constraining the hyperbox. Imagine you have a shoe box and you must search through all the styrofoam peanuts in the shoe box until you find a blue one. That's what optimization is like, and if you can make the shoebox smaller then the search gets a whole lot easier, especially when you're dealing with a large number of dimensions which we are.

In the following few sections I describe how to set up the various hyperbox parameters. Feel free to skim or skip over them if you have no interest in actually running the program.


The Hyperbox: Number of Rings per Segment
This is where you tell WeaveMaker how many rings to put in each segment, as follows.

#declare rings_per_segment_min = 1; // the smallest number of rings that a segment can have
#declare rings_per_segment_max = 1; // the largest number of rings that a segment can have (these can be equal)

There is a minimum and a maximum value so you can set it for a range of rings, but usually you will just set them equal. They are set to one for doing spiral weaves.


The Hyperbox: Number of Links
The number of links describes how many rings must be linked into each central ring to accept a solution weave, like this:

#declare min_num_links = 2.0; // sets threshold of how many links there must be to accept a weave

For example, if you are trying to generate half-persian 3 in 1, then you set this to 3.


The Hyperbox: Ring Positions
The rings get randomly generated within a 3D box, or more accurately with their centers bound by a 3D box. This is specified as follows.

#declare len = <0.0, 0.0, 0.0>; // ring segment size

In this example the box is just a zero-sized point because the example is for spiral weaves, but normally you would have numbers that ranged from 0.0 to 1.0 or more. The unit is ring ID (inside diameter), so if you set len = <1.0, 1.0, 1.0> then the ring centers will be bound to within one inside diameter of themselves. For cases where there are multiple ring sizes, the largest ID is used.

The Hyperbox: Ring Rotations
Phi is the angle of the rings, specified as rotation around the x, y, and z axes like this:

#declare phi_min = <0, 0, 0>; // minimum angle of rotation of each ring
#declare phi_max = <0, 0, 0>; // maximum angle of rotation of each ring

Actually I believe that the y axis does nothing because rings are created lying flat in the x-z plane so they are symmetrical about the y axis. Therefore y rotations do nothing.


The Hyperbox: Spiral Angles
Spiral is a pair of vectors that describe the range of spiral values to use in each dimension. They are set up with the following code.

#declare spiral_min = <-180, 0, 0>; // minimum angle of rotation of each segment
#declare spiral_max = <180, 0, 0>; // maximum angle of rotation of each segment

You can make spiral weaves along the x dimension which is typical for a chain weave, and it was just a matter of expanding spiral into a vector to accommodate spirals in all three dimensions. Who knows, maybe a 3D spiral weave is possible.


The Hyperbox: Segment Distances
This describes how far apart the segments get spaced, specified as shown below.

#declare dist_min = <0.0, 0.0, 0.0>; // minimum segment spacing
#declare dist_max = <1.0, 0.5, 0.5>; // maximum segment spacing

In this way you can control the density of the weave in all three dimensions.


The Hyperbox: Number of Dimensions
Described earlier, the number of dimensions is set as follows.

#declare num_segments = <7, 1, 1>; // number of segments
#declare num_seg_checks = <7, 1, 1>; // number of segments to check

Since the example is a spiral weave, num_seg_checks is equal to num_segments, otherwise it would be set to 3 to save on compute time. We do this more thorough testing for spiral weaves because spirals, especially with more than one ring per segment or with ring rotations, tend to create fuses on down the chain that we must check for. If not, we might get fused rings in the solution weaves and not know it!


Discovering New Weaves
So far in it's three weeks of existence, WeaveMaker has not found any new weaves that are attractive. If you set it up for two or three rings per segment and run it on spiral, you'll get some unusual chaotic weaves, but these are more like variants of shaggy loops than actual weaves. I do feel that WeaveMaker is capable of producing new weaves, but it needs a lot of creativity and compute time to do so. For now it was useful enough to rediscover some existing weaves because that shows that WeaveMaker *can* discover weaves. Also it is worth noting that the best efforts of some very creative minds have been applied to the subject and the search space of possible weaves may be largely discovered... only time will tell.


Speed Considerations
Searching out the space of possible new weaves with WeaveMaker gets computationally intensive very easily. Just increase the number of rings per segment to four or do a sheet or volume weave and you'll bring any modern personal computer to its knees for a while. Fortunately POV-Ray is well behaved and it will only use as much CPU as you have to spare, so you can do stuff while it runs.

To get the most speed out of WeaveMaker, you must reduce the size of the solution space. This means setting the len and phi parameters to the smallest range possible. Also you want the spiral and spacing parameters to be tight. Running with theta_overkill set to 1.0 makes the fastest weave function evaluations. Setting your num_seg_checks wisely helps too.

If you have a multiprocessing computer, then you might want to get version 3.7 or later of POV-Ray which has multiprocessing capability for the renders only. Unfortunately most of the time is spent on WeaveMaker's code which POV-Ray does not multiprocess. But at least your renders will go faster.

You can also play around with the optimization parameters to try to make WeaveMaker run smarter for your particular search space. I suggest turning debug_mode on and watching the population information that scrolls by to monitor your adjustments. Look for a well-filled, diverse population that converges to one or a few solutions as the temperature decreases and you'll know its working properly.

Aside from that, use the fastest computer you have, let it hog the processor, and let it run, run, and run some more. You might just find a new weave if you try hard enough (or smart enough)!


The Future of Computer Weavemaking
This program is a nice start, and probably there have been other attempts at computer weave generation, but what is really cool is what may be in store for us in the future. Imagine a user interface where you use the mouse or a 3d pointer to move rings around. This could occur simultaneously with an optimization algorithm running beneath it, and rings morphing into each other as you move them around.

Or programs like WeaveMaker could get smarter. It is possible that given a proper description of a fuse or set of fuses, one could calculate the correct ring moving and twisting to break the fuse or fuses in one single motion. This would dramatically speed up WeaveMaker. Or perhaps smarter forms of optimization like Artificial Intelligence will get applied to the problem of searching for weaves.

Another frontier is physics, simulating the effect of spring tension or gravity on the weave. One mailler has volunteered to do some SolidWorks modeling of WeaveMaker's output and we will see what happens with that effort.


Conclusion
WeaveMaker is my gift to the chainmaille community, a holiday present to close out the 2008 year and "ring" in the new 2009 year. By following the instructions in this article you can run WeaveMaker in predefined modes that create slide show movies of maille weaves, and you can also use WeaveMaker to explore the space of possible new chainmaille weaves. WeaveMaker is the first or one of the first efforts in computer generated maille weaves, a tradition that is likely to continue and expand as the years roll by.

I enjoyed coding WeaveMaker and I hope you enjoy it too. Happy Holidays and everydays.
Original URL: http://www.mailleartisans.org/articles/articledisplay.php?key=511