How would I have to imagine pixel-based rendering in Haskell?

Question

Imagine an imperative rendering engine that blits sprites to a bitmap that later gets displayed. This heavily relies on the ability to efficiently mutate individual pixels in said bitmap. How would I do such a thing an a language without side effects? I guess a completely different data structure is called for?

Answer 1

You can convert any algorithm that uses mutable state into an algorithm that "strings" the state along with it. Haskell provides a way of doing this such that it still feels like imperative programming with the state Monad.

Although, it seems to me that the basic blit operation could be done in a more functional style. You are basically combining two bitmaps to produce a new bitmap via pixel by pixel operation. That sounds very functional to me.

High quality imperative code is often faster than good functional code, but if you are willing to give up a little speed you can normally create very nice architectures in a pure functional style

Answer 2

Haskell has side effects, and you should use them whenever they're appropriate. A high-speed blit routine that's going to be in your inner loop (and therefore is performance-critical) is certainly one place that mutation is appropriate, so use it! You have a couple of options:

• Roll your own in Haskell, using ST(U)Array or IO(U)Array. Not recommended.
• Roll your own in C, and call it with the FFI. Not recommended.
• Use one of the many graphics toolkits that offers this kind of operation already, and has hundreds of programmer hours spent on making a good interface with high performance, such as Gtk or OpenGL. Highly recommended.

Enjoy!

Answer 3

A natural functional way of representing an image is by using the index function:

Image :: (Int,Int) -> Color

With this representation, blitting an area from one image to another would be achieved with

blit area a b = \(x,y) -> if (x,y) `isInsideOf` area then a (x,y) else b (x,y)  

If translation or another transformation is required, it can be directly applied to the coordinates:

translate (dx,dy) image = \(x,y) ->  b (x+dx,y+dy)  

This representation gives you natural way of working with image points. You can, for example, easily work with non-rectangular areas, and do tricks like making image interpolation as separate function instead of being part of your usual image scaling algorithms:

quadraticInterpolation :: ((Int,Int) -> Color) -> ((Double,Double) -> Color)

The performance might suffer in some cases, such as when you blit multiple images into one and then do calculations with the result. This results in a chain of tests for each pixel for each successive calculation. However, by applying memoization, we can temporarily render the functional representation into an array and transform that back to it's index function, thus eliminating the performance hit for the successive operations.

Note that the memoization can also be used to introduce parallelism to the process.