Starbeamrainbowlabs

Stardust
Blog


Archive

Mailing List Articles Atom Feed Comments Atom Feed Twitter

Tag Cloud

3d account algorithms announcement archives arduino artificial intelligence assembly async audio bash batch blog bookmarklet booting c sharp c++ challenge chrome os code codepen coding conundrums coding conundrums evolved command line compiling css dailyprogrammer debugging demystification distributed computing downtime embedded systems encryption es6 features event experiment external first impressions future game github github gist graphics hardware meetup holiday html html5 html5 canvas interfaces internet io.js jabber javascript js bin labs learning library linux low level lua maintenance network networking node.js operating systems performance photos php pixelbot portable privacy programming problems project projects prolog protocol pseudo 3d python reddit reference release releases resource review rust secrets security series list server servers software sorting source code control svg technical terminal textures three thing game three.js tool tutorial twitter ubuntu university update upgrade version control visual web website windows windows 10 xmpp

Chaikin Curves in C#: An alternative curve generation algorithm

A chaikin curve, increasing in order each frame.

A little while ago I was curious to know if there were any other ways to generate a smooth curve other than with a Bezier Curve. Turns out the answer is yes, and it comes in the form of a Chaikin Curve, which was invented in 1974 by a lecturer in America by the name of George Chaikin. A few days (and a lot of debugging) later, I found myself with a Chaikin curve generator written in pure C♯ (I seem to have this fascination with implementing algorithms :P), so I thought I'd share it here.

Before I do though, I should briefly explain how Chaikin's algorithm actually works. It's actually quite simple. If you have a list of control points, and you were to draw a line through them all, you'd get this:

Some lines before the chaikin algorithm has been run.

The magic of the algorithm happens when you interpolate between your control points. If you build a new list of points that contains points that are ¼ and ¾ along each of the lines between the current control points and draw a line though them instead, then the line suddenly gets a lot smoother. This process can be repeated multiple times to further refine the curve, as is evidenced in the animation above.

This page is very helpful in understanding the algorithm if you're having trouble getting your head around it.

My implementation makes use of the PointF class in the System.Drawing namespace, and also has the ability to generate an SVG version of any generated curve, so that it can be inspected and debugged.

You can find my implementation here: Chaikin Generator - comments and improvements are welcome!

Instructions on how to use to use it are available in the README, and the class is fully documented with Intellisense comments, so it should feel fairly intuitive to use. I've tried to use patterns that are present in the rest of the .NET framework too, so you can probably even guess how to use it correctly.

Additionally, I 'm going to try put it up as a Nuget package, but currently I can't get Nuget to pack it currently on linux (when I do, you can expect a tutorial on here!)

Pocketblock: Simple encryption tutorials

The Pocketblock logo.

Recently I found a project that aims to explain cryptography and encryption in a simple fashion through this Ars Technica article. The repository is called Pocketblock and is being created by an insanely clever guy called Justin Troutman. Initially the repository didn't have anything in it (which was confusing to say the least), but now that the first guide of sorts has been released I'd like to take the time to recommend it here.

The first article explains an encryption algorithm called 'Pockenacci', an encryption algorithm that is from the same family as AES. It's a great start to what I hope will be an awesome series! If you're interested in encryption or interested in getting into encryption, you should certainly go and check it out.

Set and forget async tasks

Banner image. (Banner image from here by GDJ)

Recently I've been using asynchronous C# quite a bit, and I've run into the problem of 'setting and forgetting' an asynchronous task more than once. You might want to do this when handling requests in some sort of server, for example.

I looked into it and came up with a few snippets of code I thought someone else might find useful, so I'm posting them here.

Without further delay, here's the first snippet:

/// <summary>
/// Call this method to allow a given task to complete in the background.
/// Errors will be handled correctly.
/// Useful in fire-and-forget scenarios, like a TCP server for example.
/// From http://stackoverflow.com/a/22864616/1460422
/// Adapted by Starbeamrainbowlabs
/// </summary>
/// <param name="task">The task to forget about.</param>
/// <param name="acceptableExceptions">Acceptable exceptions. Exceptions specified here won't cause a crash.</param>
public static async void ForgetTask(Task task, params Type[] acceptableExceptions)
{
    try
    {
        await task.ConfigureAwait(false);
    }
    catch (Exception ex)
    {
        // TODO: consider whether derived types are also acceptable.
        if (!acceptableExceptions.Contains(ex.GetType()))
            throw;
    }
}

All asynchronous methods in C♯ return some form of Task - and these Task s can be reconfigured and manipulated to make them run in the background on the thread pool, as in the above. The above also handles exceptions correctly so that your asynchronous methods won't just silently fail.

Talking about exceptions, if you await an asynchronous method, it's highly likely that if they do throw an exception it'll be an AggregateException. This is not helpful. It doesn't tell us anything about the actual exception that was thrown in the first place! It gets annoying manually inspecting the innerExceptions property of the AggregateException very quickly. Thankfully, I've found a solution to that too:

try
{
    await DoAsyncWork();
}
catch(AggregateException agError)
{
    agError.Handle((error) => {
        ExceptionDispatchInfo.Capture(error).Throw();
        throw error;
    });
}
catch
{
    Console.Error.WriteLine("Something went very wrong O.o");
    throw;
}

I can't remember where I found the ExceptionDispatchInfo bit (if it was your idea, please let me know so I can give you appropriate credit!), but the rest I wrote myself. It essentially unwraps the AggregateException and rethrows each exception in turn, whilst preserving the original stack trace. That way you can track the issue that threw the exception in the first place down.

Random Number Generation: The what, why and how

Many computer scientists are absolutely crazy about random numbers. On first thought it sounds a little bit odd, but upon further inspection it's easy to see why. You can use them for generating random loot in a game, or making a monster walk around randomly. Or in cryptography. The possibilities are endless! In addition, sometimes it is desirable to repeat a particular sequence of numbers without storing them all, and sometimes the opposite is true. In this post I intend to explain what a pseudo-random number generator is, why you'd want one, and where you can get your own.

Unfortunately, although computers are really good at complicated calculations, they are totally rubbish at generating true random numbers (that's what random.org is for). All is not lost though - we can still generate long sequences of numbers using a pseudo-random number generator (PRNG).

There are many different algorithms in several different families, but they all rely on a few basic principles. All PRNGs start with a seed, do something to transform the seed, and produce an output. Some algorithms store a few of the previously generated numbers to feed them back into the algorithm too. All PRNGs also have a period, which is the number of random values they can produce before they start to repeat themselves. Usually this value is so high that it doesn't mattter.

The seed, in this case, is a value that is used to initialise the random number generator and give it something to work with. Because PRNGs aren't truly random, any given seed will always produce the same sequence of random numbers. This can be useful if you want to allow players of your game to share cool maps that they've found without having to store details of every single item.

PRNGs can also be measured in terms of the 'quality' of the random numbers they produce. This sounds like a difficult thing to measure, and it is. The easiest (but probably not the best - I don't know, I'm not an expert!) way to test the quality of a random number generator is to generate a whole bunch of random bytes, save them to a file, and try to compress it. A true sequence of random numbers should be uncompressible. Besides, nobody wants a poor-quality random number generator.

After all that, we can finally get around to the algorithms themselves. there are 3 categories that I know of:

Linear Congruential Generators (LCGs)

Your bog standard (poor quality) generator. Usually has relatively short period too. The only good thing about these is their speed.

Mersenne Twister

Slower, but have an insanely large period (2219937 − 1 to be exact). Output is of a high quality.

XOR bitshifters

A family of fast, high-quality generators. Variable period, depending on the algorithm you pick. Also very easy to implement. See below for more information.

There may be others, but these are the 3 that I've seen around (suggestions of algorithm families are welcome in the comments).

Since XOR bit shifters are the new up-and-coming thing, I'll elaborate on them a little bit. There are actually a bunch of different algorithms in this family:

  • xorshift
  • xorshift1024*
  • xorshift128+
  • xoroshiro128+
  • ....

Their history is a bit complicated, so I won't go into any detail, but basically it all started with the xorshift algorithm. The xorshift* family followed as an improvement afterwards, and the xorshift+ family is the result of another (but different) improvement made by tweaking the original algorithm slightly. Finally, the xoroshiro+ set are new and include yet another improvement based on xorshiro+. This article sums them up nicely, along with a suggestion as to when you should use each.

The number in the names of the above refer to the number of bits that each uses to store its state. Apparently each algorithm is available in 64, 128, 256, 1024, and probably even more flavours, but the above are the most popular.

Implementations

To end this post, I'm going to include some links to implementations of the algorithms mentioned in this post in various languages. This (certainly) isn't an exhaustive list, but should serve as a good starting point if you are on the hunt for a random number generator for your next project.

Sources

  1. The multiply-with-carry (aka MWC) algorithm apparently come under xor bitshifters, but I' haven't mentioned it to as to keep things (relatively) simple. More information can be found here.

Update 5th Jan 2017: Fixed a typo.

An introduction to L Systems

Recently I've been taking a look at L Systems. Apparently, they are used for procedural content generation. After playing around with them for a little while, I discovered that you can create some rather cool patterns with them, like this Sierpinski Triangle for instance.

A Sierpinski Triangle

Before we get into how I made the above triangle grow, it's important to understand how an L System works first. The best way to describe an L System is to show you one. Let's start with a single letter:

f

Not very interesting, is it? Let's run a few find and replace rules over it. Here are a few I found lying around:

h=f+h+f f=h-f-h

After running those, here's what we got back:

h-f-h

Hrm. Interesting. What happens if I do it again?

f+h+f-h-f-h-f+h+f

Ah. Now we're getting somewhere. Here are the next 2 runs for reference:

Run 3:

h-f-h+f+h+f+h-f-h-f+h+f-h-f-h-f+h+f-h-f-h+f+h+f+h-f-h

Run 4:

f+h+f-h-f-h-f+h+f+h-f-h+f+h+f+h-f-h+f+h+f-h-f-h-f+h+f-h-f-h+f+h+f+h-f-h-f+h+f-h-f-h-f+h+f-h-f-h+f+h+f+h-f-h-f+h+f-h-f-h-f+h+f+h-f-h+f+h+f+h-f-h+f+h+f-h-f-h-f+h+f

Now that we have run it a few times, it's started to really blow up in size. The proper term for the letter we started with is the axiom, and each consecutive run we did with the find and replace rules are really called generations. This is the underlying principle of an L System. While this is cool, I'm sure you're asking how I turned the long string above into the animation at the beginning of this post.

Enter the turtle

For this next part you are going to need a (virtual) pet turtle. My turtle isn't just any turtle - he's a super fast racing turtle that I've trained to follow simple instructions like "go forwards", or "turn right". Now suppose I attach a pen to my turtle so that he leaves a line everywhere he walks.

Now if I give my turtle the following rules and the output from one of the generations above, I'll get back a picture:

f means go forwards one pace

h also mean go forwards one pace

+ means turn right

means turn left

ignore any other characters

Sierpinski triangle generation #4

Writing some code

Now that I've introduced how L Systems work and how you can use them to draw pretty pictures, we can start writing some code. I decided to use C♯ to simulate the L System, along with Mono.Cairo to draw the output. Mono.Cairo is a wonderful graphics drawing library that comes bundled along with the Mono runtime as standard.

I decided to split my implementation into 2 classes: the L System and the Turtle. Here's the code for the L System:

using System;
using System.Collections.Generic;
using System.IO;
using System.Runtime.InteropServices;
using System.Security.Policy;

namespace LSystem
{
    public class Rule
    {
        public string Find;
        public string Replace;

        public Rule(string inFind, string inReplace)
        {
            Find = inFind;
            Replace = inReplace;
        }
    }

    /// <summary>
    /// Simulates an L-System.
    /// Implemented according to http://www.cs.unm.edu/~joel/PaperFoldingFractal/L-system-rules.html
    /// </summary>
    public class LSystem
    {
        public readonly string Root;
        private List<Rule> rules = new List<Rule>();

        public int GenerationCount { get; private set; }
        public string CurrentGeneration { get; private set; }

        public Dictionary<string, string> Definitions { get; private set; }

        public LSystem(string inRoot)
        {
            CurrentGeneration = Root = inRoot;
            Definitions = new Dictionary<string, string>();
        }

        public void AddRule(string find, string replace)
        {
            rules.Add(new Rule(find, replace));
        }

        public string Simulate()
        {
            List<KeyValuePair<int, Rule>> rulePositions = new List<KeyValuePair<int, Rule>>();
            // Find all the current positions
            foreach(Rule rule in rules)
            {
                List<int> positions = AllIndexesOf(CurrentGeneration, rule.Find);
                foreach (int pos in positions)
                    rulePositions.Add(new KeyValuePair<int, Rule>(pos, rule));
            }
            rulePositions.Sort(compareRulePairs);

            string nextGeneration = CurrentGeneration;
            int replaceOffset = 0;
            foreach(KeyValuePair<int, Rule> rulePos in rulePositions)
            {
                int nextPos = rulePos.Key + replaceOffset;
                nextGeneration = nextGeneration.Substring(0, nextPos) + rulePos.Value.Replace + nextGeneration.Substring(nextPos + rulePos.Value.Find.Length);
                replaceOffset += rulePos.Value.Replace.Length - rulePos.Value.Find.Length;
            }
            CurrentGeneration = nextGeneration;
            GenerationCount++;
            return CurrentGeneration;
        }

        private int compareRulePairs(KeyValuePair<int, Rule> a, KeyValuePair<int, Rule> b)
        {
            return a.Key - b.Key;
        }

        /// <summary>
        /// From http://stackoverflow.com/a/2641383/1460422
        /// </summary>
        /// <param name="str"></param>
        /// <param name="value"></param>
        /// <returns></returns>
        private List<int> AllIndexesOf(string str, string value) {
            if (String.IsNullOrEmpty(value))
                throw new ArgumentException("the string to find may not be empty", "value");
            List<int> indexes = new List<int>();
            for (int index = 0;; index += value.Length) {
                index = str.IndexOf(value, index);
                if (index == -1)
                    return indexes;
                indexes.Add(index);
            }
        }

        public static LSystem FromFile(string filename)
        {
            StreamReader source = new StreamReader(filename);
            LSystem resultSystem = new LSystem(source.ReadLine());

            string nextLine = string.Empty;
            while (true) {
                nextLine = source.ReadLine();
                if (nextLine == null)
                    break;
                if (!nextLine.Contains("=") || nextLine.StartsWith("#") || nextLine.Trim().Length == 0)
                    continue;
                string[] parts = nextLine.Split(new char[]{'='}, 2);

                if(parts[0].StartsWith("!"))
                {
                    // This is a definition
                    resultSystem.Definitions.Add(parts[0].Trim('!'), parts[1]);
                }
                else
                {
                    resultSystem.AddRule(parts[0].Trim(), parts[1].Trim());
                }
            }
            return resultSystem;
        }
    }
}

There's quite a lot of code here, so I'll break it down. The most important bit is highlighted on lines 46-69. This Simulate() function takes the current generation and runs all the find and replace rules in parallel. A regular find and replace wouldn't work here because subsequent rules would pick up on new characters are were added when the previous rules added in a single generation.

Other important bits include the Rule class at the top, which represents a single find and replace rule, and the static FromFile() method. The FromFile() method loads a ruleset from a text file like this one, which produces a Dragon Curve:

f
f=f-h
h=f+h

....or this one, which produces a Sierpinski triangle, like the one above:

f
!angle=1.0472
h=f+h+f
f=h-f-h

The line beginning with an exclamation mark is a definition or a directive, which gives the turtle an instruction on how it should do something. They are stored in the string-to-string dictionary Definitions. The turtle class (which I'll show you in a moment) picks up on these and configures itself accordingly.

The turtle class I wrote is not as neat as the above. In fact it's kind of hacky. Here's what I ended up with:


using System;
using Cairo;
using System.Text.RegularExpressions;
using System.Resources;
using System.Collections.Generic;

namespace SimpleTurtle
{
    public class Area
    {
        public double X;
        public double Y;
        public double Width;
        public double Height;

        public Area(double inX, double inY, double inWidth, double inHeight)
        {
            X = inX;
            Y = inY;
            Width = inWidth;
            Height = inHeight;
        }
    }
    public class Turtle
    {
        private bool strictMode = false;
        private string commandQueue;

        private PointD position;
        private Area bounds;
        private double heading;
        private double headingStep;
        public double HeadingStep
        {
            get { return headingStep; }
            set { headingStep = value; }
        }
        private double movementStep ;
        public double MovementStep
        {
            get { return movementStep; }
            set { movementStep = value; }
        }

        public Turtle ()
        {
            Reset();
        }

        public void ApplyDefinitions(Dictionary<string, string> definitions)
        {
            foreach(KeyValuePair<string, string> definition in definitions)
            {
                switch(definition.Key.ToLower())
                {
                    case "angle":
                        HeadingStep = double.Parse(definition.Value);
                        break;
                }
            }
        }

        public bool Commands(string commandText)
        {
            // Remove all whitespace
            commandText = Regex.Replace(commandText, @"\s+", "");
            commandText = commandText.Replace("h", "f");

            string okCommands = "f+-";

            foreach(char ch in commandText)
            {
                if(okCommands.Contains(ch.ToString()))
                {
                    switch(ch)
                    {
                        case 'f':
                            Forwards();
                            break;
                        case '+':
                            Turn(false);
                            break;
                        case '-':
                            Turn(true);
                            break;
                        default:
                            if (strictMode) {
                                Console.WriteLine("The unexpected character '{0}' slipped through the net!", ch);
                                return false;
                            }
                            break;
                    }
                }
                else if(strictMode)
                {
                    Console.Error.WriteLine("Error: unexpected character '{0}'", ch);
                    return false;
                }
            }
            commandQueue += commandText;
            return true;
        }

        public void Draw(string filename, bool reset = true)
        {
            ImageSurface canvas = new ImageSurface(Format.ARGB32, (int)Math.Ceiling(bounds.Width + 10), (int)Math.Ceiling(bounds.Height + 10));
            Context context = new Context(canvas);
            PointD position = new PointD(-bounds.X + 5, -bounds.Y + 5);
            double heading = 0;

            context.LineWidth = 3;
            context.MoveTo(position);
            foreach(char ch in commandQueue)
            {
                switch(ch)
                {
                    case 'f':
                        PointD newPosition = new PointD(
                            position.X + movementStep * Math.Sin(heading),
                            position.Y + movementStep * Math.Cos(heading)
                        );
                        context.LineTo(newPosition);
                        position = newPosition;
                        break;
                    case '+':
                        heading += headingStep;
                        break;
                    case '-':
                        heading -= headingStep;
                        break;
                }
            }

            context.Stroke();
            canvas.WriteToPng(string.Format(filename));
            context.Dispose();
            canvas.Dispose();
            if(reset)
                Reset();
        }

        public void Forwards()
        {
            PointD newPosition = new PointD(
                position.X + MovementStep * Math.Sin(heading),
                position.Y + MovementStep * Math.Cos(heading)
            );

            if (newPosition.X > bounds.X + bounds.Width)
                bounds.Width += newPosition.X - position.X;
            if (newPosition.Y > bounds.Y + bounds.Height)
                bounds.Height += newPosition.Y - position.Y;
            if (newPosition.X < bounds.X)
            {
                bounds.X = newPosition.X;
                bounds.Width += position.X - newPosition.X;
            }
            if (newPosition.Y < bounds.Y)
            {
                bounds.Y = newPosition.Y;
                bounds.Height += position.Y - newPosition.Y;
            }

            position = newPosition;
        }

        public void Turn(bool anticlockwise = false)
        {
            if (!anticlockwise)
                heading += HeadingStep;
            else
                heading -= HeadingStep;
        }

        public void Reset()
        {
            commandQueue = string.Empty;
            position = new PointD(0, 0);
            bounds = new Area(position.X, position.Y, 1, 1);
            heading = 0;
            headingStep = Math.PI / 2;
            movementStep = 25;
        }
    }
}

Basically, the problem I found myself with was that I had to tell Cairo how large the canvas should be ahead of time, before I'd actually finished following all the commands that had been given. In order to get around this, I implemented the commands twice (bad practice, I know!).

The first implementation are the public interface methods, like Commands() (which processes a bunch of commands all at once), and the Forwards() and Turn() methods. The Commands() method follows a bunch of commands, using the private member variables at the top of the Turtle class to keep track of it's position. Each command it understands is then added to a store of valid commands ready for processing by the Draw() function (highlighted, lines 104-140). Whilst processing all these commands, the bounds of the area that the turtle has visited are tracked in the private bounds member variable (highlighted, line 30), which is of type Area (see the class at the top of the file).

The Draw() function creates a new Cairo canvas (lines 106-107) to the size of the bounds calculated previously (plus a bit extra of a border), and replays all the processed commands back on top of it. The final image is then dumped to disk.

After all that, we are missing one last piece of the puzzle: A bridge to connect the two together and provide an interface through which we can interact with the program. This is what I used:

using System;
using System.Collections.Generic;
using System.IO;

class Program
{
    public static void Main(string[] args)
    {
        if(args.Length < 2)
        {
            Console.WriteLine("Usage: ");
            Console.WriteLine(@"    ./Simpleturtle.exe <filename> <generations> [<stepCount> [<startingGeneration>]]");
            return;
        }

        int generations = int.Parse(args[1]);
        string filename = args[0];
        int movementStep = 25;
        if (args.Length > 2)
            movementStep = int.Parse(args[2]);
        int startingGeneration = 0;
        if (args.Length > 3)
            startingGeneration = int.Parse(args[3]);

        LSystem lsystem = LSystem.FromFile(filename);
        foreach(KeyValuePair<string, string> kvp in lsystem.Definitions)
        {
            Console.WriteLine("Setting {0} to {1}.", kvp.Key, kvp.Value);
        }
        Turtle turtle = new Turtle();

        for(int i = startingGeneration; i < generations; i++)
        {
            turtle.ApplyDefinitions(lsystem.Definitions);
            turtle.MovementStep = movementStep;
            turtle.Commands(lsystem.CurrentGeneration);
            turtle.Draw(string.Format("lsystem_generation_{0}.png", i));
            lsystem.Simulate();
            File.WriteAllText(string.Format("lsystem_generation_{0}.txt", i), lsystem.CurrentGeneration);
            Console.WriteLine("Generation {0} completed.", i);
        }
    }
}

There's nothing too interesting here, just a help message and a parameter reading code. If you put all of this code together, though, you can generate pretty pictures like the ones I showed you above.

This is only the beginning of what you can do with L Systems though. You could extend it to work in 3D, or give your turtle teleporting powers (look half way down) and draw some trees. you could even edit a few characters randomly after completing the main simulation to make every result slightly different. The possibilities are endless!

Sources and Further Reading

Making Mathematical Art with C Sharp and PPM

The other day I wanted to (for some random reason) create some stripes. Having worked out a simple algorithm that would produce some rather nice stripes given an (x, y) pixel coordinate, I set out to write a small script that would generate some stripes for me.

I discovered that it wasn't as easy as I'd thought. Lockbits confused me, and I couldn't find a good enough example to learn from. Thankfully I caught wind of a ridiculously simple image format called PPM (Portable Pixel Map) that I could use to output a byte[] array of pixel data as a valid image.

Here's a diagram I made to illustrate the format:

The PPM Format.

The format basically consists of a ascii header, followed by a raw dump of a byte[] full of pixel data. The header contains several parts:

  1. The characters P6 (This is called the 'magic byte', and can be used to identify the type of content that a file contains)
  2. A single whitespace (I used \s in the diagram because that is the escape code for whitespace in a javascript regular expression)
  3. The width of the image, in ascii
  4. Another single whitespace
  5. The height of the image, in ascii
  6. Another single whitespace
  7. The maximum value that the red / green / blue pixels will go up to. This value will be considered 100% saturated. Normally, you'd want this to be 255.
  8. Another single whitespace - not shown on the diagram (oops); usually a new line (\n).
  9. The raw byte[] array of pixel data.

Once you've your pixel data as a PPM, you can then use something like imagemagick to convert it to a png with a command like mogrify -format png image.ppm or convert image.ppm image.png.

Some red stripes.

Using this method, you can generate almost anything using pure C#. Here's the code I used to generate the above stripes:

using System;
using System.IO;

public class EmptyClass
{
    #region Settings

    static string filename = "image.ppm";

    static int width = 1500;
    static int height = 400;

    static int stripeWidth = width / 30;
    static rgb stripeLowCol = new rgb(204, 0, 0);
    static rgb stripeHighCol = new rgb(255, 51, 51);

    static float multiplier = 1f;

    #endregion

    #region Image Generator

    public static void Main()
    {
        byte[] pixelData = new byte[width * height * 3];
        for(int x = 0; x < width; ++x)
        {
            for(int y = 0; y < height; ++y)
            {
                int currentPixel = ((y * width) + x) * 3;
                pixelData[currentPixel] = redPixel(x, y);
                pixelData[currentPixel + 1] = greenPixel(x, y);
                pixelData[currentPixel + 2] = bluePixel(x, y);
            }
        }

        StreamWriter destination = new StreamWriter(filename);
        destination.Write("P6\n{0} {1}\n{2}\n", width, height, 255);
        destination.Flush();
        destination.BaseStream.Write(pixelData, 0, pixelData.Length);
        destination.Close();
    }

    #endregion

    #region Pixel value functions - edit these

    public static byte redPixel(int x, int y)
    {
        return (byte)(((x + y) % stripeWidth < stripeWidth / 2 ? stripeLowCol.r : stripeHighCol.r) * multiplier);
    }
    public static byte greenPixel(int x, int y)
    {
        return (byte)(((x + y) % stripeWidth < stripeWidth / 2 ? stripeLowCol.g : stripeHighCol.g) * multiplier);
    }
    public static byte bluePixel(int x, int y)
    {
        return (byte)(((x + y) % stripeWidth < stripeWidth / 2 ? stripeLowCol.b : stripeHighCol.b) * multiplier);
    }

    #endregion
}

#region Utility Classes
class rgb
{
    public byte r, g, b;
    public rgb(byte inCol)
    {
        r = g = b = inCol;
    }
    public rgb(byte inR, byte inG, byte inB)
    {
        r = inR;
        g = inG;
        b = inB;
    }
}
#endregion

The settings at the top control the appearance of the output. filename is the filename to write the image to, width and height set the dimensions of the image, stripeWidth sets the width in pixels of each stripe, and stripeLowCol and stripeHighCol set the colour of the different stripes. The multiplier at the end isn't actually needed, but you can use it to brighten or dim the resulting image if you want.

Not content with stripes, I played around for a bit longer and came up with this:

Another mathematical picture.

Above: My second attempt at mathematical art. It looks better in my native image previewer...

The above actually consists of a 3 different functions - one for each channel. Here they are:

public static byte redPixel(int x, int y)
{
    return (byte)(Math.Sin(x / (width / (Math.PI * 10))) * 255 * Math.Sin(y / (height / (Math.PI*10))));
}
public static byte greenPixel(int x, int y)
{
    return (byte)(Math.Sin(x / (width / (Math.PI * 5))) * 128 * Math.Sin(y / (height / (Math.PI * 5))));
}
public static byte bluePixel(int x, int y)
{
    return (byte)((Math.Sin(x / (width / Math.PI)) * 52 * Math.Sin(y / (height / Math.PI))) + 25);
}

I don't actually know how it works (even though I wrote it strangely enough), but if you do know, please leave a comment down below!

Since it might be a bit difficult to see, here's an animated gif that shows each of the colour channels broken down:

Illusion Boxes Decoded

Lastly, I have rendered a larger copy of the above. You can view it here (Size: 4.8MB).

Have you made some interesting mathematical art? Post it in the comments below!

Easy Quadratic Ease In/Out Algorithm

Recently I wanted to add an ease in / out effect to an animation that I was writing. I searched the internet, but couldn't find anything particularly useful that actually explained how the algorithm worked, so I am writing this post.

The formula I ended up using works by taking an input between 0 and 1, and spitting out an adjusted output which is also between 0 and 1, but has the easing function applied. For easing both in and out, there are two formulae.

To ease in, for $y < 0.5$: $$ y = 2x^2 $$

To ease out, for $y >= 0.5$: $$ y = -1 + x(4 - 2x) $$

If you want to only ease in or ease out, go ahead and use just one of the above equations, and forget about the other one. Or, you can combine them to ease in and out at the same time.

Initially, I wrote my implementation in C♯ while I was testing the equations. Here's what I came up with:

using System;
using System.Threading;

namespace EasingTest
{
    class MainClass
    {
        static int width = 75;
        static int frameDelay;

        public static float QuadEaseInOut(float time)
        {
            return time < 0.5f ? 2.0f * time * time : -1.0f + (4.0f - 2.0f * time) * time;
            //return t<.5 ? 2*t*t : -1+(4-2*t)*t
        }

        public static void displayEase(float time)
        {
            float ease = QuadEaseInOut(time);

            int nextWidth = (int)(ease * width);
            Console.Write("{0}{2}{1}\r", new string(' ', nextWidth), new String(' ', width - nextWidth), 'o');
        }

        public static void Main(string[] args)
        {
            Console.Write("Enter the frame delay: ");
            frameDelay = int.Parse(Console.ReadLine());

            int count = 0;
            float step = 0.01f;
            bool dir = false; // false = right->left, true = left->right
            while(count < 10)
            {
                if(!dir)
                {
                    for(float t = step; t < 1; t += step)
                    {
                        displayEase(t);
                        Thread.Sleep(frameDelay);
                    }
                    dir = true;
                }
                else
                {
                    for(float t = 1; t > 0; t -= step)
                    {
                        displayEase(t);
                        Thread.Sleep(frameDelay);
                    }
                    dir = false;
                }

                count++;

            }
        }
    }
}

(Pastebin, Raw)

Here's an example run of the above code:

The important stuff happens in the QuadEaseInOut function on line #11. If you just want the easing function, here it is in multiple languages:

C Sharp

public static float QuadEaseInOut(float time)
{
    return time < 0.5f ? 2.0f * time * time : -1.0f + (4.0f - 2.0f * time) * time;
}

Javascript

function (t)
{
    return t<.5 ? 2*t*t : -1+(4-2*t)*t;
}

The above can easily be ported to other languages if you aren't using C♯ or Javascript.

Sources

I originally got this algorithm from gre's wonderful gist, which also contains a number of other easing functions that you might be interested in.

3D Worley Noise with noisebox

Worley Noise Recently, I've been writing a command line noise generation tool in C♯, and I've called it noisebox. Initially I found a few noise generation algorithms that other people had already implemented, so all I had to do was write an extensible interfacde on top of the code I'd found. When I came to Worley noise, I couldn't find an implementation that I could understand (I haven't taken a look at delegates properly yet), so I decided to write my own. It's still got some bugs in it, but I've decided to relase the Worley noise implementation on it's own first, and then I will tidy up a few loose ends and release the full code on GitHub (loko out for a blog post soon!).

Here's a link to a gist of the Worley noise generator: Worley.cs

The imbuilt documentation comments (what do you call them?) should give you enough information to use it, but if you get stuck post a comment below and I will try and help you out.

The code will be released under the Mozilla Public License 2.0).

This post's title include the word "3D" - but the image at the top is very much in 2D. To demonstrate the 3D-ness of the algorithm, I added the --frames and --offset options to noisebox and rendered 1000 frames of noise, and then stitched the together with ffmpeg. I've uploaded the result to youtube.

Converting Hashtags into Titles with PHP

Recently I have been working on a website for someone I know. Mythdael (the awesome artist who created a design for this website!) did the design for this one too, and I felt that I had to bring it to life. While I was writing it, I found that I needed to convert any given hashtag into a presentable title. Since hashtags are all one word (and usually lower case), it is more or less impossible to work out where one word starts and another ends. The solution: A wordlist (My choice was a modified enable1.txt).

Here is the solution I came up with:

/*
 * From https://terenceyim.wordpress.com/2011/02/01/all-purpose-binary-search-in-php/
 * Parameters: 
 *   $a - The sort array.
 *   $first - First index of the array to be searched (inclusive).
 *   $last - Last index of the array to be searched (exclusive).
 *   $key - The key to be searched for.
 *   $compare - A user defined function for comparison. Same definition as the one in usort
 *
 * Return:
 *   index of the search key if found, otherwise return (-insert_index - 1). 
 *   insert_index is the index of smallest element that is greater than $key or sizeof($a) if $key
 *   is larger than all elements in the array.
 */
function binary_search(array $a, $first, $last, $key, $compare) {
    $lo = $first; 
    $hi = $last - 1;

    while ($lo <= $hi) {
        $mid = (int)(($hi - $lo) / 2) + $lo;
        $cmp = call_user_func($compare, $a[$mid], $key);

        if ($cmp < 0) {
            $lo = $mid + 1;
        } elseif ($cmp > 0) {
            $hi = $mid - 1;
        } else {
            return $mid;
        }
    }
    return -($lo + 1);
}

class hashtag_parser
{
    public $wordlist_length = 0;
    public $wordlist = [];

    function __construct($wordlist_path) {
        global $settings;
        $this->wordlist = file($wordlist_path, FILE_IGNORE_NEW_LINES);
        $this->wordlist_length = count($this->wordlist);
    }

    public function in_wordlist($word)
    {
        $word = strtolower($word);

        $result = binary_search($this->wordlist, 0, $this->wordlist_length, $word, "strcmp");

        if($result > -1)
            return true;
        else
            return false;
        /*
        if(in_array($word, $this->wordlist))
            return true;
        else
            return false;
        */
    }

    public function extract_words($hashtag)
    {
        global $settings;

        // Remove the hash from the beginning if it is present
        if(substr($hashtag, 0, 1) == "#") $hashtag = substr($hashtag, 1);

        // Create an array to hold the words we find
        $words = [];

        $length = strlen($hashtag); // Cache the length of the hashtag
        $pos = 0;
        while($pos < $length)
        {
//          echo("pos: $pos\n");
            // aim: find the length of the longest substring that is a valid
            // word according to the wordlist
            $longest_word_length = 0;
            for($scan_pos = $pos + 1; $scan_pos < $length + 1; $scan_pos++)
            {
//              echo("scan_pos: $scan_pos substring: " . substr($hashtag, $pos, $scan_pos - $pos) . "\n");
                if($this->in_wordlist(substr($hashtag, $pos, $scan_pos - $pos)))
                {
                    $longest_word_length = $scan_pos - $pos;
//                  echo("found word\n");
                }
            }

            // Set the length of the longest word to the remainder of the
            // string if we don't find any valid words
            if($longest_word_length == 0) $longest_word_length = $length - $pos;

            $words[] = substr($hashtag, $pos, $longest_word_length);

            $pos += $longest_word_length;
        }

        return ucwords(implode(" ", $words));
    }
}

The code is a bit messy (perhaps I should tidy it up a bit lot), but it does the job I intended it to do. I used a class because I was concerned that reading in the wordlist every time would cause the code to take too long to complete - it is slow enough as it is. Thankfully a binary search algorithm written in PHP by terenceyim helped speed things up enormously. Anyway, it can be used like this:

$parser = new hashtag_parser("/path/to/wordlist.txt");
echo($parser->extract_words("sometext")); // Prints "Some Text"

The algorithm I used is quite simple:

  1. Loop over each character.
  2. Scan ahead of the current character and figure out the length of the longest word in the input via the wordlist.
  3. If no valid word can be found, assume that the rest of the input is all one word.
  4. Extract the longest word we can find and add it to an array.
  5. Add the length of the word we found to the character pointer.
  6. If we haven't reached the end of the given input, go to step 2.
  7. If we have reach the end of the output, return the words we found.

I am posting this here in the hopes that someone else will find this code useful :)

Voronoi Diagrams

This post was meant to come out on the 15th April... but I forgot to upload it to the server - I am posting now instead.

A Voronoi Diagram

Today I bring you another experiment with the HTML5 Canvas - Voronoi diagrams. A Voronoi diagram is an image where you scatter a bunch of points across an image, give each point a colour, and then colour each pixel according to which point is closest.

You can find my implementation here: Voronoi Diagram Generator

Initially I had trouble implementing this algorithm as I was trying to draw the outline of each of the cells first, but the explanation on it's Wikipedia article helped me to realise that there was a much easier way to do it :)

Next time I am trying to implement something that looks rather complicated and difficult I will definitely look for an alternative way of thinking about it.

For those of you who are interested, I used a technique called 32 bit canvas manipulation when writing this one. In a nutshell, this is a way of setting the red, green, blue, and alpha values of a pixel all at once, instead of in 4 separate operations - speeding up the whole rendering process.

Art by Mythdael