A simple texture algorithm – faster code and more results

header

Faster Code

A while back I wrote about a simple texture algorithm that I have been exploring. The Python implementation was very slow – so much, that I decided to implement it in C++ to see what performance gain I would get. Surprisingly, the C++ version is about 100 faster, if not more. I expected a decent increase, but what once took several hours can now be done in a minute!

Not all of the performance gain is because of using C++ instead of Python. The Python version uses a data structure (an “enhanced” grid) that provides a lot of fancy syntax for operating on a grid. For instance:

grid[0, …] First column (1D)
grid[…, 1] Second row (1D)
grid[0, ::2] Every second item of the first column (1D)
grid[1:3,::2] Every second item of the second and third column (2D)
grid[3, 4] The item at the fourth column and fifth row (0D)

The “enhanced” grid also provides several iterators that allow easy processing, for example:

  • a cell iterator, that iterates over all values in the grid;
  • an index iterator, that iterates over all possible tuples that can be used to index the grid; and
  • a window iterator, that iterates over all cells in a rectangular portion of the grid.

The speed problem is caused by the implementation that supports the above features – an implementation that I thought was rather elegant. I knew there was a performance penalty, but after seeing to what extent I realise that I must have a hard look at how these features are implemented.

I am a big fan of late optimisation, especially for experimental code. But this incident has made me re-evaluate my position. After I had the fast C++ version running, I could do hordes of experiments very quickly – which meant I got a much better intuition of how parameters influence the resulting texture.

It also made me realise how important it is to check the performance of supporting data structures, even if they are merely convenience structures in non-production code (as is the “enhanced” grid).

More results

One of the things that struck me about the textures that this algorithm typically produces is the shapes of blotches of similar colour. I have been trying to enhance (and take advantage) these shapes by applying various filters on the texture; below are the results.

original water brown
Original (generated from a random 5×5 matrix) Dilation Posterisation
sobel sobel_median edge
Sobel edge detection Median filter and Sobel edge detection Median filter, differential edge detection
emboss alien green
Emboss Alien (Gimp filter) Median filter.

The texture is also suitable for organic blend animations (compare with organic blending using Perlin noise).

t1 t2 t3 t4 t5 t6

t1

Download

C++ Implementation

cpp_texture.zip (1.78 MB) (Visual Studio Solution)

The example uses PNG Writer , libpng and zlib (library files included with the download).

  • http://www.BuschnicK.net BuschnicK

    Fancy syntax doesn’t necessarily have to be expensive (runtime wise). Check out Blitz++ or Boost uBlas for examples:

    http://www.oonumerics.org/blitz/

    http://www.boost.org/doc/libs/1_37_0/libs/numeric/ublas/doc/index.htm

    It does come with a cost: increased complexity and longer compile times. But runtime penalty for nice iterator/slice/index access is neglectible and performance overall may even improve once you start using more complex matrix expressions where the compile time expression tree optimizations shine.

    Nice blog – I throroughly enjoyed your random steering article.

    cheers,

    Sören

  • http://code-spot.co.za/ herman.tulleken

    Sören,

    Thanks for the links!

    Hopefully, a faster version of the enhanced grid is also on its way.

    ht