Speeding up an L-System renderer in C#/WPF

Question

lsys is a blazing fast L-System renderer written in CoffeeScript.

Below is a simple renderer in C# and WPF. It is hardcoded to render this example. The result when run looks as follows:

A mouse-click in the window will adjust the angleGrowth variable. The re-calculation of the GeometryGroup as well as building the Canvas usually take much less than a tenth of a second. However, the actual screen update seems to take much longer.

Any suggestions for how to make this faster or more efficient? It's currently way slower than the CoffeeScript/JavaScript version... :-)

using System;
using System.Collections.Generic;
using System.Text;
using System.Windows;
using System.Windows.Controls;
using System.Windows.Media;
using System.Diagnostics;

namespace WpfLsysRender
{
    class DrawingVisualElement : FrameworkElement
    {
        public DrawingVisual visual;

        public DrawingVisualElement() { visual = new DrawingVisual(); }

        protected override int VisualChildrenCount { get { return 1; } }

        protected override Visual GetVisualChild(int index) { return visual; }
    }

    class State
    {
        public double size;

        public double angle;

        public double x;

        public double y;

        public double dir;

        public State Clone() { return (State) this.MemberwiseClone(); }
    }

    public partial class MainWindow : Window
    {
        static string Rewrite(Dictionary<char, string> tbl, string str)
        {
            var sb = new StringBuilder();

            foreach (var elt in str)
            {
                if (tbl.ContainsKey(elt))
                    sb.Append(tbl[elt]);
                else
                    sb.Append(elt);
            }

            return sb.ToString();
        }

        public MainWindow()
        {
            InitializeComponent();

            Width = 800;
            Height = 800;

            var states = new Stack<State>();

            var str = "L";

            {
                var tbl = new Dictionary<char, string>();

                tbl.Add('L', "|-S!L!Y");
                tbl.Add('S', "[F[FF-YS]F)G]+");
                tbl.Add('Y', "--[F-)<F-FG]-");
                tbl.Add('G', "FGF[Y+>F]+Y");

                for (var i = 0; i < 12; i++) str = Rewrite(tbl, str);
            }

            var canvas = new Canvas();

            Content = canvas;

            var sizeGrowth = -1.359672;
            var angleGrowth = -0.138235;

            State state;

            var pen = new Pen(new SolidColorBrush(Colors.Black), 0.25);

            var geometryGroup = new GeometryGroup();

            Action buildGeometry = () => 
            {
                state = new State()
                {
                    x = 0,
                    y = 0,
                    dir = 0,
                    size = 14.11,
                    angle = -3963.7485
                };

                geometryGroup = new GeometryGroup();

                foreach (var elt in str)
                {
                    if (elt == 'F')
                    {
                        var new_x = state.x + state.size * Math.Cos(state.dir * Math.PI / 180.0);
                        var new_y = state.y + state.size * Math.Sin(state.dir * Math.PI / 180.0);

                        geometryGroup.Children.Add(
                            new LineGeometry(
                                new Point(state.x, state.y),
                                new Point(new_x, new_y)));

                        state.x = new_x;
                        state.y = new_y;
                    }
                    else if (elt == '+') state.dir += state.angle;

                    else if (elt == '-') state.dir -= state.angle;

                    else if (elt == '>') state.size *= (1.0 - sizeGrowth);

                    else if (elt == '<') state.size *= (1.0 + sizeGrowth);

                    else if (elt == ')') state.angle *= (1 + angleGrowth);

                    else if (elt == '(') state.angle *= (1 - angleGrowth);

                    else if (elt == '[') states.Push(state.Clone());

                    else if (elt == ']') state = states.Pop();

                    else if (elt == '!') state.angle *= -1.0;

                    else if (elt == '|') state.dir += 180.0;
                }
            };

            Action populateCanvas = () =>
            {
                var drawingVisualElement = new DrawingVisualElement();

                Console.WriteLine(".");

                canvas.Children.Clear();

                canvas.RenderTransform = new TranslateTransform(400.0, 400.0);

                using (var dc = drawingVisualElement.visual.RenderOpen())
                    dc.DrawGeometry(null, pen, geometryGroup);

                canvas.Children.Add(drawingVisualElement);
            };

            MouseDown += (s, e) =>
                {
                    angleGrowth += 0.001;
                    Console.WriteLine("angleGrowth: {0}", angleGrowth);

                    var sw = Stopwatch.StartNew();

                    buildGeometry();
                    populateCanvas();

                    sw.Stop();

                    Console.WriteLine(sw.Elapsed);
                };

            buildGeometry();

            populateCanvas();
        }
    }
}

Answer 1

WPF's geometry rendering is just slow. If you want fast, render using another technology, and host the result in WPF. For example, you could render using Direct3D and host your render target inside a D3DImage. Here's an example using Direct2D instead. Or you could draw by manually setting byte values in a RGB buffer and copy that inside a WriteableBitmap.

EDIT: as the OP found out, there's also a free library to help out with drawing inside a WriteableBitmap called WriteableBitmapEx.

Answer 2

Below is a version that uses WritableBitmap as Asik suggested. I used the WriteableBitmapEx extension methods library for the DrawLine method.

It is ridiculously fast now. Thanks Asik!

using System;
using System.Collections.Generic;
using System.Text;
using System.Windows;
using System.Windows.Controls;
using System.Windows.Media;
using System.Windows.Media.Imaging;
using System.Diagnostics;

namespace WpfLsysRender
{
    class DrawingVisualElement : FrameworkElement
    {
        public DrawingVisual visual;

        public DrawingVisualElement() { visual = new DrawingVisual(); }

        protected override int VisualChildrenCount { get { return 1; } }

        protected override Visual GetVisualChild(int index) { return visual; }
    }

    class State
    {
        public double size;

        public double angle;

        public double x;

        public double y;

        public double dir;

        public State Clone() { return (State) this.MemberwiseClone(); }
    }

    public partial class MainWindow : Window
    {
        static string Rewrite(Dictionary<char, string> tbl, string str)
        {
            var sb = new StringBuilder();

            foreach (var elt in str)
            {
                if (tbl.ContainsKey(elt))
                    sb.Append(tbl[elt]);
                else
                    sb.Append(elt);
            }

            return sb.ToString();
        }

        public MainWindow()
        {
            InitializeComponent();

            Width = 800;
            Height = 800;

            var bitmap = BitmapFactory.New(800, 800);

            Content = new Image() { Source = bitmap };

            var states = new Stack<State>();

            var str = "L";

            {
                var tbl = new Dictionary<char, string>();

                tbl.Add('L', "|-S!L!Y");
                tbl.Add('S', "[F[FF-YS]F)G]+");
                tbl.Add('Y', "--[F-)<F-FG]-");
                tbl.Add('G', "FGF[Y+>F]+Y");

                for (var i = 0; i < 12; i++) str = Rewrite(tbl, str);
            }

            var sizeGrowth = -1.359672;
            var angleGrowth = -0.138235;

            State state;

            var lines = new List<Point>();

            var pen = new Pen(new SolidColorBrush(Colors.Black), 0.25);

            var geometryGroup = new GeometryGroup();

            Action buildLines = () =>
                {
                    lines.Clear();

                    state = new State()
                    {
                        x = 400,
                        y = 400,
                        dir = 0,
                        size = 14.11,
                        angle = -3963.7485
                    };

                    foreach (var elt in str)
                    {
                        if (elt == 'F')
                        {
                            var new_x = state.x + state.size * Math.Cos(state.dir * Math.PI / 180.0);
                            var new_y = state.y + state.size * Math.Sin(state.dir * Math.PI / 180.0);

                            lines.Add(new Point(state.x, state.y));
                            lines.Add(new Point(new_x, new_y));

                            state.x = new_x;
                            state.y = new_y;
                        }
                        else if (elt == '+') state.dir += state.angle;

                        else if (elt == '-') state.dir -= state.angle;

                        else if (elt == '>') state.size *= (1.0 - sizeGrowth);

                        else if (elt == '<') state.size *= (1.0 + sizeGrowth);

                        else if (elt == ')') state.angle *= (1 + angleGrowth);

                        else if (elt == '(') state.angle *= (1 - angleGrowth);

                        else if (elt == '[') states.Push(state.Clone());

                        else if (elt == ']') state = states.Pop();

                        else if (elt == '!') state.angle *= -1.0;

                        else if (elt == '|') state.dir += 180.0;
                    }
                };

            Action updateBitmap = () =>
                {
                    using (bitmap.GetBitmapContext())
                    {
                        bitmap.Clear();

                        for (var i = 0; i < lines.Count; i += 2)
                        {
                            var a = lines[i];
                            var b = lines[i+1];

                            bitmap.DrawLine(
                                (int) a.X, (int) a.Y, (int) b.X, (int) b.Y, 
                                Colors.Black);
                        }
                    }
                };

            MouseDown += (s, e) =>
                {
                    angleGrowth += 0.001;
                    Console.WriteLine("angleGrowth: {0}", angleGrowth);

                    var sw = Stopwatch.StartNew();

                    buildLines();
                    updateBitmap();

                    sw.Stop();

                    Console.WriteLine(sw.Elapsed);
                };

            buildLines();

            updateBitmap();
        }
    }
}

Answer 3

I have not tested the WriteableBitmapEx version, so I don't know how this compares, but I was able to substantially speed up the WPF native version by using StreamGeometry and Freeze(), which is a way to optimize when there is no animation. (Though it still doesn't feel as fast as the javascript version)

• The posted version timing is ~0.15s
• The StreamGeometry version timing is ~0.029s

I don't think the timer includes the actual rendering time, just the time to populate the rendering commands. However, it also feels much more speedy. This WPF performance test demonstrates a way to get actual rendering times.

I also removed the Canvas and FrameworkElement, but it was switching to StreamGeometry that did the speedup.

using System;
using System.Collections.Generic;
using System.Text;
using System.Windows;
using System.Windows.Controls;
using System.Windows.Media;
using System.Diagnostics;

using System.Windows.Media.Imaging;

// https://stackoverflow.com/q/22599806/519568

namespace WpfLsysRender
{

    class UpdatableUIElement : UIElement {        
        DrawingGroup backingStore = new DrawingGroup();
        public UpdatableUIElement() {

        }

        protected override void OnRender(DrawingContext drawingContext) {
            base.OnRender(drawingContext);                    
            drawingContext.DrawDrawing(backingStore);            
        }
        public void Redraw(Action<DrawingContext> fn) {
            var vis = backingStore.Open();            
            fn(vis);
            vis.Close();
        }
    }    

    class State
    {
        public double size;

        public double angle;

        public double x;

        public double y;

        public double dir;

        public State Clone() { return (State)this.MemberwiseClone(); }
    }

    public partial class MainWindow : Window
    {
        static string Rewrite(Dictionary<char, string> tbl, string str) {
            var sb = new StringBuilder();

            foreach (var elt in str) {
                if (tbl.ContainsKey(elt))
                    sb.Append(tbl[elt]);
                else
                    sb.Append(elt);
            }

            return sb.ToString();
        }

        public MainWindow() {
            // InitializeComponent();

            Width = 800;
            Height = 800;

            var states = new Stack<State>();

            var str = "L";

            {
                var tbl = new Dictionary<char, string>();

                tbl.Add('L', "|-S!L!Y");
                tbl.Add('S', "[F[FF-YS]F)G]+");
                tbl.Add('Y', "--[F-)<F-FG]-");
                tbl.Add('G', "FGF[Y+>F]+Y");

                for (var i = 0; i < 12; i++) str = Rewrite(tbl, str);
            }

            var lsystem_view = new UpdatableUIElement();
            Content = lsystem_view;


            var sizeGrowth = -1.359672;
            var angleGrowth = -0.138235;

            State state;

            var pen = new Pen(new SolidColorBrush(Colors.Black), 0.25);

            var geometry = new StreamGeometry();

            Action buildGeometry = () => {
                state = new State() {
                    x = 0,
                    y = 0,
                    dir = 0,
                    size = 14.11,
                    angle = -3963.7485
                };

                geometry = new StreamGeometry();
                var gc = geometry.Open();

                foreach (var elt in str) {
                    if (elt == 'F') {
                        var new_x = state.x + state.size * Math.Cos(state.dir * Math.PI / 180.0);
                        var new_y = state.y + state.size * Math.Sin(state.dir * Math.PI / 180.0);
                        var p1 = new Point(state.x, state.y);
                        var p2 = new Point(new_x, new_y); 
                        gc.BeginFigure(p1,false,false);
                        gc.LineTo(p2,true,true);


                        state.x = new_x;
                        state.y = new_y;
                    }
                    else if (elt == '+') state.dir += state.angle;

                    else if (elt == '-') state.dir -= state.angle;

                    else if (elt == '>') state.size *= (1.0 - sizeGrowth);

                    else if (elt == '<') state.size *= (1.0 + sizeGrowth);

                    else if (elt == ')') state.angle *= (1 + angleGrowth);

                    else if (elt == '(') state.angle *= (1 - angleGrowth);

                    else if (elt == '[') states.Push(state.Clone());

                    else if (elt == ']') state = states.Pop();

                    else if (elt == '!') state.angle *= -1.0;

                    else if (elt == '|') state.dir += 180.0;
                }
                gc.Close();
                geometry.Freeze();
            };

            Action populateCanvas = () => {
                Console.WriteLine(".");

                lsystem_view.RenderTransform = new TranslateTransform(400,400);

                lsystem_view.Redraw((dc) => {
                    dc.DrawGeometry(null, pen, geometry);
                });
            };

            MouseDown += (s, e) => {
                angleGrowth += 0.001;
                Console.WriteLine("angleGrowth: {0}", angleGrowth);

                var sw = Stopwatch.StartNew();

                buildGeometry();
                populateCanvas();

                sw.Stop();

                Console.WriteLine(sw.Elapsed);
            };

            buildGeometry();

            populateCanvas();
        }
    }
}

Answer 4

Here is a DirectX version using SlimDX.