Category: Tutorials

  • ASCII terminal mandelbrot fractal renderer in Go

    ASCII terminal mandelbrot fractal renderer in Go

    After the previous post about the mandelbrot renderer written in Go, this article will be related to the same topic, only this time i’ll talk about a terminal based Julia set generator written again in Go language. In fact i’ve done this experiment prior to write the mandelbrot renderer. About the implementation I’ve discussed in the last article.

    The whole idea came from the motivation to create something which resembles the feeling which only a terminal based application can create (something which is close enough to the pixelart technique), but at the same time it has enough visually appealing characteristics and above all it’s dynamic.

    Into the terminal fractals

    (In preview the ASCII Mandelbrot generator running in terminal)

    Because in the last few months i was pretty much delved into the fractals, i’ve started to create some small experiments, one of them being the code snippet below:

    https://gist.github.com/esimov/970a3816dda12e4059e3.js

    Which produce the following terminal output:

    mandelbrot

    This was nice but i wanted to be dynamic, and not something simply put in the terminal window. So i’ve started to search for methods to refresh the terminal window periodically, ideally to refresh on each mandelbrot iteration. For this reason i’ve created some utility methods to get the terminal window width and height. And another method to flush the screen buffer periodically.

    
    // Get console width
    func Width() int {
    	ws, err := getWinsize()
    
    	if err != nil {
    		return -1
    	}
    
    	return int(ws.Row)
    }
    
    // Get console height
    func Height() int {
    	ws, err := getWinsize()
    	if err != nil {
    		return -1
    	}
    	return int(ws.Col)
    }
    
    // Flush buffer and ensure that it will not overflow screen
    func Flush() {
    	for idx, str := range strings.Split(Screen.String(), "\n") {
    		if idx > Height() {
    			return
    		}
    
    		output.WriteString(str + "\n")
    	}
    
    	output.Flush()
    	Screen.Reset()
    }
    

    It was missing another ingredient: in terminal based application we need somehow to specify the cursor position where to output the desired character, some kind of pointer to a position specified by width and height coordinate. For this i’ve created another method which move the cursor to the desired place, defined by x and y:

    // Move cursor to given position
    func MoveCursor(x int, y int) {
    	fmt.Fprintf(Screen, "\033[%d;%dH", x, y)
    }

    Then we can clear the screen buffer periodically. In linux based systems to move the cursor to a specific place in terminal window we can use ANSI escape codes, like: \033[%d;%dH, where %d;%d we can replace with values obtained from the mandelbrot renderer. In the example provided in the project github repo i’m moving the terminal window cursor to the mandelbrot x and y position, after which i’m clearing the screen.

    To make it more attractive i used a cheap trick to zoom in and out into the fractal and to smoothly displace the fractal position by applying sine and cosine function on x and y coordinate.

    for {
    	n += 0.045
    	zoom += 0.04 * math.Sin(n)
    	asciibrot.DrawFractal(zoom, math.Cos(n), math.Sin(n)/zoom*0.02, math.Sin(n), MAX_IT, true, isColor) //where math.Cos(n) and math.Sin(n) are x and y coordinates	
    }

    But there is another issue. We need to handle differently the code responsible to obtain the terminal window size in different operating systems. In linux and darwin based operating systems here is how we can get the terminal size:

    func getWinsize() (*winsize, error) {
    	ws := new(winsize)
    
    	var _TIOCGWINSZ int64
    
    	switch runtime.GOOS {
    	case "linux":
    		_TIOCGWINSZ = 0x5413
    	case "darwin":
    		_TIOCGWINSZ = 1074295912
    	}
    
    	r1, _, errno := syscall.Syscall(syscall.SYS_IOCTL,
    		uintptr(syscall.Stdin),
    		uintptr(_TIOCGWINSZ),
    		uintptr(unsafe.Pointer(ws)),
    	)
    
    	if int(r1) == -1 {
    		fmt.Println("Error:", os.NewSyscallError("GetWinsize", errno))
    		return nil, os.NewSyscallError("GetWinsize", errno)
    	}
    	return ws, nil
    }
    

    In Windows operating system to obtain the terminal dimension is a little bit different:

    
    type (
    	coord struct {
    		x int16
    		y int16
    	}
    
    	consoleScreenBufferInfo struct {
    		size              coord
    		cursorPosition    coord
    		maximumWindowSize coord
    	}
    )
    // ...
    func getWinSize() (width, height int, err error) {
    	var info consoleScreenBufferInfo
    	r0, _, e1 := syscall.Syscall(procGetConsoleScreenBufferInfo.Addr(), 2, uintptr(out), uintptr(unsafe.Pointer(&info)), 0)
    	if int(r0) == 0 {
    		if e1 != 0 {
    			err = error(e1)
    		} else {
    			err = syscall.EINVAL
    		}
    	}
    	return int(info.size.x), int(info.size.y), nil
    }
    

    One last step remained: to clear the screen buffer on CTRL-C signal, in another words to clear the screen on control break. For this i’ve created a channel and when the CTRL-C was pressed i signaled this event and on a separate goroutine i was listening for this event, meaning i could break the operation.

    
    // On CTRL+C restore default terminal foreground and background color
    go func() {
    	<-c
    	fmt.Fprint(asciibrot.Screen, "%s%s", "\x1b[49m", "\x1b[39m")
    	fmt.Fprint(asciibrot.Screen, "\033[2J")
    	asciibrot.Flush()
    	os.Exit(1)
    }()
    

    Usage

    In big that’s all. You can grab the code by running the following command:


    go get github.com/esimov/asciibrot

    To run it type:


    go run julia.go --help

    You can run the example in monochrome or color version. For the color version use --color or -c. For monochrome version use --mono or -m.

    You can build the binary version with: go build github.com/esimov/asciibrot.

    I’ve created a github repo for this experiment, which you can get it here: https://github.com/esimov/asciibrot

  • Mandelbrot renderer in Go

    Mandelbrot renderer in Go

    Lately i’ve been playing around a lot with the Go language, and wanted to put it something together which is somehow related to the graphics part of the language. Mandelbrot image set generator was a well suited candidate for this task, because of the calculation complexity and the iteration count used to generate the fractal image, Go being a language capable to communicate and share different pools of resources via channels and goroutines.

    The goroutine is used when i’m iterating over the two dimensional array, defined as a 2d system coordinate and applying the mathematical calculation prior to generate the mandelbrot set. The mandelbrot set is generated by applying a mathematical function to each complex number projected in the complex plane and determining for each whether they are bounded or escapes towards infinity.

    The mandelbrot is defined by the following formula: z_{n+1} = z_n^2 + c.. For example, letting c = 1 gives the sequence 0, 1, 2, 5, 26,…, which tends to infinity. As this sequence is unbounded, 1 is not an element of the Mandelbrot set. On the other hand, c = -1 gives the sequence 0, -1, 0, -1, 0,…, which is bounded, and so -1 belongs to the Mandelbrot set.

    
    for iy := 0; iy < height; iy++ {
    	waitGroup.Add(1)
    	go func(iy int) {
    		defer waitGroup.Done()
    
    		for ix := 0; ix < width; ix++ {
    			var x float64 = xmin + (xmax-xmin)*float64(ix)/float64(width-1)
    			var y float64 = ymin + (ymax-ymin)*float64(iy)/float64(height-1)
    			norm, it := mandelIteration(x, y, maxIteration)
    			iteration := float64(maxIteration-it) + math.Log(norm)
    			
    			if (int(math.Abs(iteration)) < len(colors)-1) {
    				color1 := colors[int(math.Abs(iteration))]
    				color2 := colors[int(math.Abs(iteration))+1]
    				color := linearInterpolation(RGBAToUint(color1), RGBAToUint(color2), uint32(iteration))
    
    				image.Set(ix, iy, Uint32ToRGBA(color))
    			}
    		}
    	}(iy)
    }
    
    

    After applying the mathematical function to the same point projected in the complex plane infinite number of times we can check if its bounded or escapes towards infinity. If it’s bounded the iteration is restarted again.

    The mandelbrot function translated into Go code is looking like this:

    
    func mandelIteration(cx, cy float64, maxIter int) (float64, int) {
    	var x, y, xx, yy float64 = 0.0, 0.0, 0.0, 0.0
    
    	for i := 0; i < maxIter; i++ { xy := x * y xx = x * x yy = y * y if xx+yy > 4 {
    			return xx + yy, i
    		}
    		x = xx - yy + cx
    		y = 2*xy + cy
    	}
    
    	log_zn := (x*x + y*y) / 2
    	return log_zn, maxIter
    }
    

    Treating the real and imaginary parts of each number as image coordinates, pixels are colored according to how rapidly the sequence diverges, if at all. For smooth color interpolation i’ve used Paul Burke’s cosine interpolation algorithm:

    
    func cosineInterpolation(c1, c2, mu float64) float64 {
    	mu2 := (1 - math.Cos(mu*math.Pi)) / 2.0
    	return c1*(1-mu2) + c2*mu2
    }
    

    The larger and scattered the color palette used the more intense and vivid the generated mandelbrot image is. By combining the following flag values: -step, -palette and -iteration you can obtain differently colorized mandelbrot sets, like in the screenshot below:

    mandelbrot_sample

    Because the rendering process could take some time, depending on the image resolution, the image smoothness and the iteration count, i thought that it would be a good idea to visualize the background process in terminal. For this purpose a good option was to use a different channel and signaling a tick on specified intervals. time.Tick is at rescue! On another channel i’m processing the image and when the rendering has been finished i’m sending a done signal to main goroutine, telling that the rendering process has been finished, which means i could stop the background indicator process.

    
    done := make(chan struct{})
    ticker := time.NewTicker(time.Millisecond * 100)
    
    go func() {
    	for {
    		select {
    		case <-ticker.C:
    			fmt.Print(".")
    		case <-done:
    			ticker.Stop()
    			fmt.Print("Done!")
    			fmt.Printf("\n\nMandelbrot set rendered into `%s`\n", outputFile)
    		}
    	}
    }()
    

    Install

    go get github.com/esimov/gobrot

    Before to run the code you need to include the project into the GOPATH environment variable. See the documentation: https://golang.org/doc/code.html#GOPATH

    Run

    go run mandelbrot.go –help

    Will give all the options supported by the renderer at the moment.

    Here are some options you can try out. (The attached images are generated using the below commands.)

    – go run mandelbrot.go -palette “Hippi” -xpos -0.0091275 -ypos 0.7899912 -radius .01401245 -file “test1.png”

    – go run mandelbrot.go -palette “Plan9” -xpos -0.0091275 -ypos 0.7899912 -radius .01401245 -file “test2.png” -iteration 600 -step 600

    – go run mandelbrot.go -palette “Hippi” -xpos -0.00275 -ypos 0.78912 -radius .1256789 -file “test3.png” -iteration 800 -step 6000 -smoothness 10 -width 1920 -height 1080

    TODO

  • Nice to meet you Go lang

    Nice to meet you Go lang

    Nice to meet You, GO!

    Recently i started to study Go language, the shiny new programming language developed by Google. The general opinion about the language among developers was quite positive so i thought to give it a try.

    As a web developer i’m working mainly with dynamic languages like PHP, Ruby, Javascript etc., so for me it was fresh new start to switch back to a language which has a standard AOT (Ahead of Time) compilator, contrary to JIT (Just in Time) compilers, which translate the human readable (high level) code to machine or byte code prior to execution, the compilation time being one of the strong feature of the Go language. Until now this was regarded as one of the great benefits of dynamic languages because the long compile/link step of C++ could be skipped, but with Go this is no longer an issue! Compilation times are negligible, so with Go we have the same productivity as in the development cycle of a scripting or dynamic language. On the other hand, the execution speed of the native code should be comparable to C/C++.

    Above the fast compilation time, another main characteristic of Go is that it combines the efficacy, speed and safety of a strongly and statically compiled language with the ease of programming of a dynamic language. Above these, Go is designed for fast parallelization, thread concurrency which are the basic desirables for network programming, Go definitely being designed for highly scalable and lightning fast web servers.This is certainly the great stronghold of Go, given the growing importance of multicore and multiprocessor computers, and the lack of support for that in existing programming languages.

    Because it is a statically typed language it’s a safe language, giving 100% percent trust for the programmer for incidental and not desired errors to not happen, assigning different types of values to the same variable (redeclaring) being impossible without an error notification. Go is strongly typed: implicit type conversions (also called castings or coercions) are not allowed; the principle is: keep things explicit!

    Text editors and IDE extensions for Go

    Having these basic ingredients at our disposal, combined with a powerful editor like IntelliJ IDEA extended with a very versatile Golang Idea Plugin specially developed to support all the syntactical sugar, auto completion, refactoring etc. desired for every IDE, programming in Go is pure fun. I can fully recommend this strong partnership.

    I’ve tried Sublime Text 2 editor with GoSublime plugin, but even if i’m a huge fan of Sublime i think the first option is a better choice. There is a dedicated page at the project site for the current existing editors supporting the language including Eclipse, but considering that till now i was very satisfied with InteliJ editors i sticked with IntelliJ IDEA.

    Installation

    The installation of Go is quite straightforward. You only need to follow the directions set on main site: http://golang.org/doc/install, paying special attention to setting up the environment variables. I won’t go into details how to do this (you can read this article if you need assistance), i will focus only on two special aspects of the installation process:

    1.) The first one is that if you are using Windows environment (i haven’t tested on other environments) and want to use Go with IntelliJ IDEA be careful to download the binary code, extract it and copy into the root folder of Go installation, otherwise it’s not possible to associate the project to the Go SDK. If everything went well, you should see something like this:

    Go SDK

    …otherwise if you install with MSI installer, the IDE won’t be able to locate and setup the SDK.

    2.) Another special attention which you have to pay is to set up the Go environment variables correctly. This means either you specify the GOROOT, GOOS, GOBIN variables per project or you set up permanently by including into the Windows default environment variables either by using the SET command line or simply by editing the existing environment variables on Control Panel -> System and Security -> System -> Advanced System Settings -> Advanced.

    Windows EV

    However on each project you need to setup the GOPATH variable (which need to be associated to the root of the project folder!!) by running the SET GOPATH="root\to\the\project\folder" command. This is necessary if you wish to run the build or install go commands in order to create executable files or to build the source packages.

    Quasi torture test

    After setting up the necessary prerequisites I've started to play with different type of function invocations Go can handle, one of the most referred in every torture test being the recursive function. I came up with three different methods to calculate the factorial of the first 40 numbers and measured the execution time for each one separately.

    As you can see from examples below the calculation/execution times are really impressive. The first method is the traditional one. It's execution time is the worst between the three. The second method is a demonstration how Go can handle closure functions and how can solve the same problem more elegantly. The last one is the best one using the memoization technique. What i really liked is how elegantly Go handle the closure function, being possible to define even a function as a return statement. So below are the methods, you can test it yourself by following the steps defined above.

    Conclusion

    This is the first post from - hopefully - a series of Go related entries, so along the way tinkering with the language, i'm aiming to publish more views and thoughts. In the current phase i wanted only to share my first impression and steps necessary to install Go with a IntelliJ IDEA on Windows environment.

    package main
     
    import (
    	"fmt"
    	"time"
    )
     
    const LIM = 41
    var facts [LIM]uint64
     
    func main() {
    	fmt.Println("==================FACTORIAL==================")
    	start := time.Now()
    	for i:=uint64(0); i < LIM; i++ {
    		fmt.Printf("Factorial for %d is : %d \n", i, Factorial(uint64(i)))
    	}
    	end := time.Now()
    	fmt.Printf("Calculation finished in %s \n", end.Sub(start)) //Calculation finished in 2.0002ms 
     
    	fmt.Println("==================FACTORIAL CLOSURE==================")
    	start = time.Now()
    	fact := FactorialClosure()
    	for i:=uint64(0); i < LIM; i++ {
    		fmt.Printf("Factorial closure for %d is : %d \n", uint64(i), fact(uint64(i)))
    	}
    	end = time.Now()
    	fmt.Printf("Calculation finished in %s \n", end.Sub(start)) //Calculation finished in 1ms 
     
    	fmt.Println("==================FACTORIAL MEMOIZATION==================")
    	start = time.Now()
    	var result uint64 = 0
    	for i:=uint64(0); i < LIM; i++ {
    		result = FactorialMemoization(uint64(i))
    		fmt.Printf("The factorial value for %d is %d\n", uint64(i), uint64(result))
    	}
     
    	end = time.Now()
    	fmt.Printf("Calculation finished in %s\n", end.Sub(start)) // Calculation finished in 0ms
    }
     
    func Factorial(n uint64)(result uint64) {
    	if (n > 0) {
    		result = n * Factorial(n-1)
    		return result
    	}
    	return 1
    }
     
    func FactorialClosure() func(n uint64)(uint64) {
    	var a,b uint64 = 1, 1
    	return func(n uint64)(uint64) {
    		if (n > 1) {
    			a, b = b, uint64(n) * uint64(b)
    		} else {
    			return 1
    		}
     
    		return b
    	}
    }
     
    func FactorialMemoization(n uint64)(res uint64) {
    	if (facts[n] != 0) {
    		res = facts[n]
    		return res
    	}
     
    	if (n > 0) {
    		res = n * FactorialMemoization(n-1)
    		return res
    	}
     
    	return 1
    }

    And here is the gist: Download gist

  • First impressions about Typescript, the new authoring tool from Microsoft

    First impressions about Typescript, the new authoring tool from Microsoft

    In this blog post i want to share my first impression about Typescript, the new programming language from Microsoft.

    The background

    Coming from Flash/Actionscript, and having done almost all my experiments in AS3, facing the loose typing nature of JavaScript was a bit daunting for me. Over the time I got familiarized myself with all the mystical parts of JavaScript, with it’s prototyping nature, with the strange fact that JS hasn’t a type interface, and you can declare a variable without declaring the type of that variable. In fact all the declared variables can take any type of value, and assigning a different type of value to the variable wont make the compiler to trow an exception (only if we force to do so). This proved to be the weakness of JavaScript and the most acclaimed factor which stand in front of developing highly scalable applications.

    wo

    The first question that may arise is what is Typescript? The answer is: Typescript is a superset of JavaScript which compiles to JavaScript at runtime, all while maintaining your existing code and using the existing libraries. And why Typescript? The short answer: because Typescript is awesome. The long answer will follow.

    One of the main benefits using typescript is code validation at compile time and compilation to native Javascript file at the runtime.

    This differentiate Typescript from other competitors, nominating mainly two contenders: DART ( which is a very heavy assault initiative from Google meant to eliminate all the weakness and flawless of JavaScript, introducing a completely new language, having as target not less than being the web native language), and Coffescript which is a syntactic sugar of Javascript, which compile to Javascript. Typescript somehow break in the middle of the two, because DART is a fundamentally and completely different language than Javascript, with strong typing, traditional class  structures, modules etc. On the other hand Coffescript embraced the new ECMA-6 (Harmony) features like classes,  import modules (only when required) etc, but it’s weakness is the same as of Javascript: the absence of type annotation and a very limited or almost completely absent feedback response and lack of debugging tools. This got managed by TypeScript.

    Getting started

    I won’t go into much details how to get started with Typescript. You can download the source from the official page of the language: http://www.typescriptlang.org/, then if you are a Windows 8 or at least Windows 7 user and preferably (not my case) .NET developer you’ll have a very easy time to get started with coding. There is a plugin for Microsoft Visual Studio 2012 downloadable from the same source. I’ve tried installing on Vista, after too many trials and errors finally got working, unfortunately without code highlighting and code completion. So in the end decided to write a plugin for Sublime Text 2 editor (my editor of choice). Here is the Stackoverflow thread explaining the process to automate the code transcription from TS to JS. The only weakness is – at the time of this writing –  there isn’t a code completion and live time error checking plugin implemented. A good news is that Webstorm 6.0 is already offering support for Typescript. This article summarize in a few words the capabilities of Typescript in Webstorm perspective: http://joeriks.com/2012/11/20/a-first-look-at-the-typescript-support-in-webstorm-6-eap/.

    There is a live playground available for online experimentation with a few samples at disposal: http://www.typescriptlang.org/Playground/

    Things I liked in Typescript

    Static value declaration

    As i said earlier declaring a variable in JS is simply assigning a value to it, the rest of internal operations are up to the JIT compiler. This is the root of many unwanted errors which happens when we unconsciously  messing up different types of values with the originally declared variable. Typescript helps to resolve this issue by allowing to statically declare the variable type. If no type has been specified the type any is inferred.

    var num: number = 20;

    which compiles to JS as:

    var num = 20;

    The only chance in JS to get feedback about the errors is to use test cases by covering all the possible errors you might expect:

    if typeof num !== "number" {
       throw new Error(num, " is not a number");
    }

    On the other hand TS informs instantly about the errors as you type.

    Arrow function expression

    Another great feature is the addition of the so called arrow function expression. These are useful on situations when we need to preserve the scope of the outer execution context. A common practice widespread among JS developers is to bind this to a variable self which we place outside the inner function.
    A function expression using the function keyword introduces a new dynamically bound this, whereas an arrow function expression preserves the this of its enclosing context. These are particularly useful in situation when we need to write callbacks like in the following example.

    function sayHello(message:string, callback:()=>any) {
    	alert(message);
    	setTimeout(callback, 2000);
    }
    
    sayHello("Welcome visitor", function() {
    	alert("thank you");	
    });

    Classes, modules, interfaces

    Probably the greatest addition of Typescript is the possibility to work with classes, modules and interfaces.

    Interfaces

    Let’s start with interfaces. In Typescript interfaces have only a contextual scope, they haven’t any runtime representations of the compiled code. Their role is only to create a syntactic structure, a shell which is particular useful for object properties validation, in other words for documenting and validating the required shape of properties, objects passed as parameters, and objects returned from functions. In TS, interfaces are actually object types. While in Actionscript you have to have a class to implement the interface, in TS a simple object can implement it. Here is how you declare interfaces in TS:

    interface Person {
    	name: string;
    	age?: number;
    }
    
    function print(person: Person) {
    	if (person.age) {
    		alert("Welcome " + person.name + " you are " + person.age + " age");	
    	} else {
    		alert("Welcome " + person.name);
    	}
    	
    }
    
    print({name: "George", age:22});

    Furthermore interfaces have function overloading features which means that you can pass two identical functions on the same interface and let the user decide at the implementation phase which function wants to implement:

    interface Overload {
    	foo(s:string): string;
    	foo(n:number): number;
    }
    
    function process(o:Overload) {
    	o.foo("string");
    	o.foo(23);
    }

    Another very interesting particularity of Typescript is that above the support offered for overloading functions, this is applicable for constructors too. This way we can redefine multiple constructor only by changing the way we implement it.

    var canvas = document.createElement("canvas");
    document.body.appendChild(canvas);
    var ctx = canvas.getContext('2d');
    
    interface ICircle {
    	x: number;
    	y: number;
    	radius: number;
    	color?: string;
    }
    
    class Circle {
    	public x: number;
    	public y: number;
    	public radius: number;
    	public color: string = "#000";
    	
    	constructor () {}		
    	
    	constructor () { 
    		this.x = Math.random() * canvas.width;
    		this.y = Math.random() * canvas.height;
    		this.radius = 40;
    	}		 		
    	
    	constructor (circle: ICircle = {x:Math.random() * canvas.width, y:Math.random() * canvas.height, radius:20}) {
    		this.x = circle.x;
    		this.y = circle.y;
    		this.radius = circle.radius;
    	}
    }
    
    var c = new Circle();
    ctx.fillStyle = c.color;
    ctx.beginPath();
    ctx.arc(c.x, c.y, c.radius, 0, Math.PI * 2, true);
    ctx.closePath();
    ctx.fill();

    Classes

    The most advanced feature of Typescript (from my point of view) is the addition of the more traditional class structure with all the hotness like inheritance, polymorphism, constructor functions etc. In Typescript we are declaring the class in the following way:

    class Point {
    	x: number;
    	y: number;
    	
    	constructor(x: number, y: number) {
    		this.x = x;
    		this.y = y;
    	}
    	
    	sqrt() {
    
    		return Math.sqrt(this.x * this.x + this.y * this.y) 
    	}
    	
    	print(callback?) {		 
    		setTimeout(callback, 3000);
    		
    	}
    }
    
    class Point3D extends Point {	
    	z : number;
    	
    	constructor ( x:number,  y: number, z: number) {
    		super(x, y);
    	}
    	
    	sqrt() {
    		var d = super.sqrt();
    		return Math.sqrt(d * d + this.z * this.z);
    	}
    }
    
    var p = new Point(20, 20);
    p.print(() => { alert (p.sqrt()); });

    … which in Javascript compiles to:

    var __extends = this.__extends || function (d, b) {
        function __() { this.constructor = d; }
        __.prototype = b.prototype;
        d.prototype = new __();
    };
    var Point = (function () {
        function Point(x, y) {
            this.x = x;
            this.y = y;
        }
        Point.prototype.sqrt = function () {
            return Math.sqrt(this.x * this.x + this.y * this.y);
        };
        Point.prototype.print = function (callback) {
            setTimeout(callback, 3000);
        };
        return Point;
    })();
    var Point3D = (function (_super) {
        __extends(Point3D, _super);
        function Point3D(x, y, z) {
            _super.call(this, x, y);
        }
        Point3D.prototype.sqrt = function () {
            var d = _super.prototype.sqrt.call(this);
            return Math.sqrt(d * d + this.z * this.z);
        };
        return Point3D;
    })(Point);
    var p = new Point(20, 20);
    p.print(function () {
        alert(p.sqrt());
    });

    Analyzing the code we observe that it share almost the same principle like any other static type language. We declare the class, it’s variables and functions, which can be static, private and public. By default the declared functions and variables are public, but we can make them private or static, by placing the private or static keyword in front of them. TS supports the constructor functions, which we declare in the following format:

    var1:type;
    var2:type;
    constructor (var1:type, var2:type...varn:type) {
           this.var1 = var1;
           this.var2 = var2;
           .
           .
           .
           this.varn = varn;
    }

    It’s possible to declare the constructor arguments type as public and then we can eliminate to assign the constructor function parameters to constructor’s variables.

    Typescript facilitates the working with classes by introducing another two great features commonly used in OOP, namely the inheritance and class extension. I rewrite the above code sample to show with a few simple changes we can extend the existing code to embrace some advanced polymorphism methods:

    class Point {
    	x: number;
    	y: number;
    	
    	constructor(x: number, y: number) {
    		this.x = x;
    		this.y = y;
    	}
    	
    	sqrt(x:number, y:number):number {		
    		return Math.sqrt(x * x + y * y); 
    	}
    	
    	dist(p:Point):number {
    		var dx: number = this.x - p.x;
    		var dy: number = this.y - p.y;
    		
    		return this.sqrt(dx, dy);
    	}
    	
    	print(callback?) {		 
    		setTimeout(callback, 3000);
    		
    	}
    }
    
    class Point3D extends Point {	
    	z : number;
    	
    	constructor ( x:number,  y: number, z: number) {
    		super(x, y);
    	}
    	
    	sqrt3(z:number) {
    		var s = super.sqrt(this.x, this.y);
    		return Math.sqrt(s * s + this.z * this.z);		
    	}	
    		
    	dist(p:Point3D):number {
    		var d = super.dist(p);		
    		var dz: number = this.z - p.z;										
    		return this.sqrt3(dz);
    	}
    }
    
    var p = new Point3D(19, 20, 20);
    p.print(() => { alert (p.dist(new Point3D(2,2,20))); });

    Modules

    The last topic i want to discuss is about modules. Typescript module implementation is closely aligned with ECMAScript 6 proposal and supports code generation, targeting AMD and CommonJS modules. There are two types of source files Typescript is supporting: implementation source files and declaration source files. The difference between the two is that the first one contains statements and declarations, on the other hand the second contains only declarations. These can be used to declare static type information associated with existing javascript code. By default, a JavaScript output file is generated for each implementation source file in a compilation, but no output is generated from declaration source files.

    The scope of modules is to maintain a clean structure in our code and to prevent the global namespace pollution. If suppose i have to create a global function Main the way i do in Javascript without to override the function at a later stage is to assure that the Main function get initialized only once. This is a common technique widespread among JS developers. In TS we do in the following way:

    module net.esimov.core {
    	export class Main {
    		public name: string;
    		public interest: string;
    		
    		constructor() {
    			this.name = "esimov";
    			this.interest = "web technology";
    		}
    		
    		puts() {
    			console.log(this.name, " like", this.interest);
    		}
    	}
    }

    Importing the declaration files is simple as placing the following statement on the top of our code: /// <reference path="...";/>. Then with a simple import statement we’ll import the modules needed at one specific moment.

    import Core = net.esimov.core;
    var c = new Core.Main();

    Final thoughts

    Typescript is a language that is definitely worth to try it. Unfortunately it has one main disadvantage, namely to benefit from it’s strong typing features we need to declare and construct declaration files for libraries we want to include in our projects. There are predefined declaration files for jQuery, node.js and d3.js, just to mention a few, but hopefully as the community will grow this list will get bigger and bigger.

    Another weak point is the lack of support from IDE’s other than MS Visual Studio, but fortunately Webstorm 6 has in perspective to include full type support for Typescript too.

    What’s next?

    With this introduction done, my intention is to put into real usage all the information and learning accumulated and trying to create some canvas experiments but this time using Typescript. So check out soon.

    Other resources to check

  • Worley noise cellular texturing

    Worley noise cellular texturing

    There are some quite well known procedural content generation algorithms out there: Voronoi, Perlin noise, simplex noise, L-systems, reaction-diffusion systems like Turing pattern, which I’ve presented in my earlier blog post.The specifics of these algorithms are that either generates a large amount of content for a small investment of input data, or one that adds structure to random noise.

    Generally speaking they are categorized by what they generate (map vs sequence generation) and also by the mindset behind their use. This time we’ll discuss the Worley noise pattern, which can be included into the generative map creation category. This means we need a grid system for the representation and visualization of points scattered randomly in 3D or 2D space.

    In it’s visual appearance is almost like a Voronoi diagram, only it’s not as famous like it’s counterpart. Even Wikipedia discuss it very briefly. Worley noise in it’s essence is a noise generation pattern, which means by multiplication/addition of different octaves of the same noise pattern we can produce a variety and completely different outputs. This is the fun part of working with generative patterns.

    Now, after we gain a little theoretical introduction let’s get started with the basics, and try to dissect how can we reproduce those organic shapes and textures found in every living being in nature. (In parentheses being said, in many graphic simulations and parametric applications dealing with textural visualizations this shapes can be found). As a last side note before we go into the technical details, my intention was to implement the algorithm in Javascript mainly because i wished to be accessible by as many users as possible, and at the same time i was curious how far can i stress the limit of the modern web browsers. This is an experiment based 100% on CPU, so WebGL was out of scope, only because i was not playing with this technology until now, but i considering to implement on GPU in a shorter or longer future.

    Feature points

    The basic idea is to spread randomly varying number in space and calculate the distance to these point from every possible location of space. As a complement, Worley suggest to assign to each feature point an unique ID number. This number can be used to generate surface with colored areas or crocodile like textures, cityblock diagrams etc. depending on the algorithm, or coloring function implemented.

    The noise function simply computes a single value for every location in space. We can then use that value in literally thousands of interesting ways, such as perturbing an existing pattern spatially, mapping directly to a density or color or adding multiple scale of noise to make a fractal combination. While there are infinite number of possible functions which provide an infinite number of outputs, noise’s random behavior gives a much more interesting appearance  then simple gradients for example.

    By spreading  feature points randomly through the 3D space we build a scalar function based on the distribution of the points near the sample location. Because an image worth a thousand of words the picture below describes a space with feature points scattered across the plane.

    For a position on the plane (marked with x in the picture above) there is always a closest feature point, a second closest, a third and so on. The algorithm is searching for such feature points, return  their relative distance to the target point, their position and their unique ID number.

    Another key component of the algorithm is the demarcation line which is supposed to be integer in every plane. Each squares (cubes in 3D) are positioned so that their identification numbers can be expressed with some integer values. Let’s suppose we want to obtain the distance to the two feature point closest to the (3.6, 5.7) we start by looking at the integer squares (3, 5) and compare it’s feature points to each other.  It’s obvius that the two feature points in that square aren’t the two closest. One of them is, but the second closest belongs to the integer square (3, 6).

    It’s possible that some feature points are not inside the square where the target point is placed, in this case we extend our analysis to the adjacent squares. We could just test all 26 immediate neighboring cubes, but by checking the closest distance we’ve computed so far (our tentative n-th closest feature distance) we can throw out whole rows of cubes at once by deciding when no point in the neighbor cube could possibly contribute to our list. We don’t know yet what points are in the adjacent cubes marked by “?,” but if we examine a circle of radius F1, we can see that it’s possible that the cubes labeled A, B, and C might contribute a closer feature point, so we have to check them. As resulted from the image below, it’s mostly possible to check 6 facing neighbors of center cube (these are the closest and most likely to have a close feature point), 12 edge cube and 8 corner cubes in 3D. We could start testing more distant cubes, but it’s much more convenient to just use a high enough density to ensure that the central 27 are sufficient.

    The code implementation in Javascript

    For the code implementation i used html5 canvas. I’ve commented the source code, so won’t be too hard to follow for anyone. Because (as i mentioned in the beginning) my WebGL knowledge is quite minimal, for this reason i tried to optimize every single bit of code. For this reason my single option was to use web workers by separating the main core from the computationally heavy and intense pixel manipulation logic. There is a well described article on html5rocks.com about the basic principles of web workers, followed by some very neat examples regarding the implementation of them.

    The main advantage of using web workers is that we can eliminate the bottlenecks caused by computational heavy threads running in the background, separating the implementation interface from the computational logic. This way we can reduce the hangouts caused by intensive calculations which may block the UI or script to handle the user interaction.

    Creating a web worker is quite simple. We define the variables we want to pass to workers, and by calling an event listener using postMessage function we transfer the main tread instructions to the worker (which is running in a separate thread). Because web workers run in isolated threads, the code that they execute needs to be contained in a separate file. But before we do that, the first thing we have to do is create a new Worker object in our main page. The constructor takes the name of the worker script:

    In  a separate script we’ll define wich are the variables we want to listen for. This part is responsible for the heavy weight operations. After the pixel calculations has been done, we pass over the results through the postMessage method to the main thread. This part of code looks like the following:

    As a last option i’ve included the DAT.GUI lightweight graphical interface for a user interaction, where we can select different methods, colors etc. and lastly to offer the possibility for rendering with or without web workers.

    Hopefully you find interesting this experiment, and if you have some remarks, comments, then please use the comments field below, or share through twitter.

  • Organic Turing Pattern

    Organic Turing Pattern

    In this post i will present an experiment which i did a few months earlier, but because lately i was pretty occupied with various job related activities and with setting up this new blog (transferring the old content to the new host – plus a lot of other stuff), i have no time to publish this new experiment. More about below, but until then a few words about the background, inspiration and some of the key challenge i have faced during this process.

    This is an experiment inspired by a thoroughly explained article about the concept behind what is generally known as Turing Pattern. The Turing Patterns has become a key attraction in fact thanks to Jonathan McCabe popular paper Cyclic Symmetric Mutli-Scale Turing Patterns in which he explains the process behind the image generation algorithm like that one below, about what Frederik Vanhoutte know as W:blut wrote on his post:

    Quote leftIf you’ve seen any real­ity zoo/wild-life pro­gram you’ll rec­og­nize this. Five min­utes into the show you’re con­fronted with a wounded, mag­nif­i­cent ani­mal, held in cap­tiv­ity so its care­tak­ers can nur­ture and feed it. And inevitably, after three com­mer­cial breaks, they release it, teary-eyed, back into the wild. It’s a piv­otal moment that turns their leop­ard into anyone’s/no one’s leop­ard.Quote right

    That’s the feeling which emanates when you first see the organic like, somehow obscure (some may go even further and say: macabre or creepy) thing which is known as a Turing pattern. At first moment when you are confronted with it, some kind of emotion (be that fear or amazement or just a sight) is resurfaced. Definitely won’t let you neutral.

    This is the emotion which pushed me to try to implement it in Actionscript. (In parentheses be said this is not the best platform for computation intensive experiments.) Felix Woitzel did an amazing remake adaptation of the original pattern in WebGL. The performance with a good GPU is quite impressive. Maybe in the future i will try to port in WebGL. Anyway, there is another nice article by Jason Rampe, where he explains the algorithm of the Turing Pattern.

    So let’s face directly and dissect the core components of the algorithm.

    The basic concept

    The process is based on a series of different “turing” scales. Each scale has different values for activator, inhibitor, radius, amount and levels. We use a two dimensional grid which will be the basic container for activator, inhibitor and variations, all of them going to be of typed arrays (in our case Vectors.<>). At the first phase we will initialize the grid with random points between -1 and 1. In the next step we have to determine the shape of the pattern. For this case w’ll use a formula defined by the following method:

    for (var i:int = 0; i < levels; i++)
    {
    	var radius:int = int(Math.pow(base, i));
    	_radii[i] = radius;
    	_stepSizes[i] = Math.log(radius) * stepScale + stepOffset;
    }

    During each step of simulation we have to execute the following methods:

    1. Populate the grid with pixels at random locations. I’m gonna use a linked list to store the pixels properties: positions and colors. We will loop through all the pixels, the number of pixels will be defined by the grid with x height dimension.
    2. Average each grid cell location over a circular radius specified by activator, then store the results in the activator array, multiplied by the weight.
    3. Average each grid cell location over a circular radius specified by inhibitor, then store the results in the activator array, multiplied by the weight.
    4. In the next step we need to calculate the absolute difference between the activator and inhibitor using the the following formula: variations = variations + abs(activator[x,y] - inhibitor[x,y])

    Once we have all the activator, inhibitor and variations values calculated for each grid cells we proceed with updating the grids as follows:

    1. Find which grid cell has the lowest variation value
    2. Once we found the lowest variation value we update the grid by the following formula:
    for (var l:Number = 0; l < levels - 1; l++)
    {
    	var radius:int = int(_radii[l]);
    	fastBlur(activator, inhibitor, _blurBuffer, WIDTH, HEIGHT, radius);
    
    	//calculates the absolute difference between activator and inhibitor
    
    	for (var i:int = 0; i < n; i++)
    	{
    		_variations[i] = activator[i] - inhibitor[i];
    		if (_variations[i] < 0)
    		{
    			_variations[i] = -_variations[i];
    		}
    	}
    
    	//if first level then set some initial values for bestLevel and bestVariation 
    	if (l == 0)
    	{
    		for (i = 0; i < n; i++)
    		{
    			_bestVariation[i] = _variations[i];
    			_bestLevel[i] = l;
    			_directions[i] = activator[i] > inhibitor[i];
    		}
    		activator = _diffRight;
    		inhibitor = _diffLeft;
    	}
    	else
    	{
    		for (i = 0; i < n; i++)
    		{
    			if (_variations[i] < _bestVariation[i])
    			{
    				_bestVariation[i] = _variations[i];
    				_bestLevel[i] = l;
    				_directions[i] = activator[i] > inhibitor[i];
    
    			}
    		}
    		var swap:Vector. = activator;
    		activator = inhibitor;
    		inhibitor = swap;
    	}
    }

    As a last step we should average the gap between the levels by performing a blur technique for a nicer transition. We blur the image sequentially in two steps: first we blur the image vertically then horizontally.

    The challenge

    The most challenging part was related to the unknown factor about how well gonna handle the AVM2 the intensive CPU calculation. Well as you may have guessed not too well, especially with very large bitmap dimension and a lot of pixels needed to be manipulated, plus the extra performance loss “gained” after the bluring operation.

    For some kind of compensation benefits (in terms of performance) i decided to populate the BitmapData with a chained loop using single linked list, plus typed arrays as generally known the Vector.<> arrays are much faster compared to the traditional array stacks. After a not too impressive performance, i wondered how can i even more optimize the code for a better overcome. I decided to give it a try to Alchemy, and Joa Ebert’s TDSI, a Java based Actionscript compiler, as by that time was commonly known a better choice over AVM. Unfortunately i didn’t get too many support and helpful articles about the implementation and as a consequence my attempt was a failure, which resulted in a quite buggy and ugly output. After too many attempts without the wishful result, i gave up.

    That’s all in big steps. You can grab the source code from here. Feel free to post your remarks.

    ps: Be prepared this experiment will burn your CPU. 🙂