Polygon Rendering Performance Optimization

I need help achieving a possible 25x speedup.

  • (2 Pages)
  • +
  • 1
  • 2

17 Replies - 7153 Views - Last Post: 09 May 2009 - 12:05 PM Rate Topic: ***-- 2 Votes

#1 StarBP   User is offline

  • New D.I.C Head

Reputation: 1
  • View blog
  • Posts: 42
  • Joined: 06-May 09

Polygon Rendering Performance Optimization

Post icon  Posted 06 May 2009 - 05:20 PM

On his blog, Roger Alsing describes a very interesting program. I wonder how it can be improved....?

Attached you can find a .zip file with the source code with Dan Bystromís improvements [to the EvoLisa program], plus an additional improvement that I added (using uints instead of doubles when the fitness drops below 3/4 of uint.MaxValue). I also added a feature which could be implemented. It allows an interlaced subset of the pixels to be tested for fitness instead of the full set (the subset would change every time the fitness improves with the current set, similar to how a TV's interlaced resolutions work). I also included an open-source C program I found on the Internet that generates fast random numbers, but that would not help improve the program much speed-wise due to other bottlenecks in the system, so I did not implement it. Right now the renderer seems to be the major bottleneck in the code. You may want to try using System.Windows.Shapes.Polygon instead of System.Graphics for the polygons, since then each polygon could be rerendered at will individually. Right now, rendering is the major bottleneck in the code after the updates are applied (Around 350 renders occur per second on my computer, whereas 3,500 mutates or 1,750 fitness evaluations can occur in the same time period [I tested that by commenting out code temporarily and counting to ten while the algorithm was running. The margin of error was around 10%, which is negligible in this case]). By the way, I think that using uints instead of doubles was the 60% improvement that Dan was talking about, although the improvement would be more along the lines of 3X if the Renderer was faster.

The question is, how can I implement this? (I am a high-school student who has recently begun programming, and I consider myself to be a novice-intermediate programmer). Could anyone optimize that code with all of this in mind? The key is to use System.Windows.Shapes.Polygon so only one polygon would usually need to be rendered per generation (maybe two or three, but certainly not all of them as is required now). I do not even know where to start on this, although I know that using Clone() is very inefficient compared to storing a change and doing it twice around 10% of the time (The mutations are good around 1/10 of the time). Also, any other improvements you could give me that make the code faster would be appreciated. Before you ask, NO, THIS IS NOT A HOMEWORK ASSIGNMENT!!! (Also, it isn't a science fair project).

Just for an example of the source code (download the attachment for the full code), here is the Renderer class, which is called AFTER EVERY GENERATION (There are usually around 50 polygons, whereas only 1 or 2 of them are usually changed):

using System.Collections.Generic;
using System.Drawing;
using System.Drawing.Imaging;
using GenArt.AST;

namespace GenArt.Classes
{
	public static class Renderer
	{
		//Render a Drawing
		public static void Render(DnaDrawing drawing,Graphics g,int scale)
		{
			g.Clear(Color.Black);

			foreach (DnaPolygon polygon in drawing.Polygons)
				Render(polygon, g, scale);
		}

		//Render a polygon
		private static void Render(DnaPolygon polygon, Graphics g, int scale)
		{
			using (Brush brush = GetGdiBrush(polygon.Brush))
			{
				Point[] points = GetGdiPoints(polygon.Points, scale);
				g.FillPolygon(brush, points);
			}
		}

		//Convert a list of DnaPoint to a list of System.Drawing.Point's
		private static Point[] GetGdiPoints(IList<DnaPoint> points,int scale)
		{
			Point[] pts = new Point[points.Count];
			int i = 0;
			foreach (DnaPoint pt in points)
			{
				pts[i++] = new Point(pt.X * scale, pt.Y * scale);
			}
			return pts;
		}

		//Convert a DnaBrush to a System.Drawing.Brush
		private static Brush GetGdiBrush(DnaBrush b)
		{
			return new SolidBrush(Color.FromArgb(b.Alpha, b.Red, b.Green, b.Blue));
		}

		
	}
}

Attached File(s)


This post has been edited by StarBP: 07 May 2009 - 09:50 AM


Is This A Good Question/Topic? 0
  • +

Replies To: Polygon Rendering Performance Optimization

#2 StarBP   User is offline

  • New D.I.C Head

Reputation: 1
  • View blog
  • Posts: 42
  • Joined: 06-May 09

Re: Polygon Rendering Performance Optimization

Posted 07 May 2009 - 09:48 AM

Could someone please help me with this, or at least ask for any specific additional information that is needed?
Was This Post Helpful? 0
  • +
  • -

#3 SixOfEleven   User is offline

  • Planeswalker
  • member icon

Reputation: 1055
  • View blog
  • Posts: 6,643
  • Joined: 18-October 08

Re: Polygon Rendering Performance Optimization

Posted 07 May 2009 - 10:03 AM

        public static void Render(DnaDrawing drawing,Graphics g,int scale)
        {
            g.Clear(Color.Black);

            foreach (DnaPolygon polygon in drawing.Polygons)
                Render(polygon, g, scale);
        }



I have one question about the above code. Are you able to modify the DnaPolygon class? If you can can an add a variable and a property to the class:

bool polygonchanged;

public bool Polygonchanged
{
    get { return polygonchanged; }
}



Then, when you run your foreach loop you could do this:

        public static void Render(DnaDrawing drawing,Graphics g,int scale)
        {
            g.Clear(Color.Black);

            foreach (DnaPolygon polygon in drawing.Polygons)
            {
                if (polygon.Polygonchanged)
                    Render(polygon, g, scale);
             }
        }



That way you would only be drawing the changed polygons.

This post has been edited by SixOfEleven: 07 May 2009 - 10:04 AM

Was This Post Helpful? 0
  • +
  • -

#4 StarBP   User is offline

  • New D.I.C Head

Reputation: 1
  • View blog
  • Posts: 42
  • Joined: 06-May 09

Re: Polygon Rendering Performance Optimization

Posted 07 May 2009 - 10:17 AM

View PostSixOfEleven, on 7 May, 2009 - 09:03 AM, said:

        public static void Render(DnaDrawing drawing,Graphics g,int scale)
        {
            g.Clear(Color.Black);

            foreach (DnaPolygon polygon in drawing.Polygons)
                Render(polygon, g, scale);
        }



I have one question about the above code. Are you able to modify the DnaPolygon class? If you can can an add a variable and a property to the class:

bool polygonchanged;

public bool Polygonchanged
{
    get { return polygonchanged; }
}



Then, when you run your foreach loop you could do this:

        public static void Render(DnaDrawing drawing,Graphics g,int scale)
        {
            g.Clear(Color.Black);

            foreach (DnaPolygon polygon in drawing.Polygons)
            {
                if (polygon.Polygonchanged)
                    Render(polygon, g, scale);
             }
        }



That way you would only be drawing the changed polygons.


Yes, I can modify it. Download the attachment to see the full source of EvoLisa. Also, I tried something similar to that, but I can't seem to get a polygon to change. If I use a static method with your code, I ONLY get the changed polygons, but with an instance method, the polys NEVER get removed. That's why I recommend using System.Windows.Shapes.Polygon instead of Systen.Graphics, since Polygon allows you to change attributes of individual polygons. Again, any help with any speed improvement in any way would be appreciated, but I'm especially wanting to improve the renderer, preferrably by using Polygon, which I think is the fastest way.
Was This Post Helpful? 0
  • +
  • -

#5 SixOfEleven   User is offline

  • Planeswalker
  • member icon

Reputation: 1055
  • View blog
  • Posts: 6,643
  • Joined: 18-October 08

Re: Polygon Rendering Performance Optimization

Posted 07 May 2009 - 10:21 AM

I have to leave right now but I will take a look at the program a little later.
Was This Post Helpful? 0
  • +
  • -

#6 StarBP   User is offline

  • New D.I.C Head

Reputation: 1
  • View blog
  • Posts: 42
  • Joined: 06-May 09

Re: Polygon Rendering Performance Optimization

Posted 07 May 2009 - 10:23 AM

View PostSixOfEleven, on 7 May, 2009 - 09:21 AM, said:

I have to leave right now but I will take a look at the program a little later.


OK, thanks. Remember, if you find any other performance enhancements that can be done, you can tell me what they are, too (However, no other performance enhancement will really make a difference unless the Renderer is improved).
Was This Post Helpful? 0
  • +
  • -

#7 SixOfEleven   User is offline

  • Planeswalker
  • member icon

Reputation: 1055
  • View blog
  • Posts: 6,643
  • Joined: 18-October 08

Re: Polygon Rendering Performance Optimization

Posted 07 May 2009 - 01:02 PM

View PostStarBP, on 7 May, 2009 - 09:23 AM, said:

View PostSixOfEleven, on 7 May, 2009 - 09:21 AM, said:

I have to leave right now but I will take a look at the program a little later.


OK, thanks. Remember, if you find any other performance enhancements that can be done, you can tell me what they are, too (However, no other performance enhancement will really make a difference unless the Renderer is improved).


I've been looking at the code. Maybe you could help me a little. Can you paste a link to the entry in the blog that describes the program? I need to better understand the process that is being used.
Was This Post Helpful? 0
  • +
  • -

#8 StarBP   User is offline

  • New D.I.C Head

Reputation: 1
  • View blog
  • Posts: 42
  • Joined: 06-May 09

Re: Polygon Rendering Performance Optimization

Posted 07 May 2009 - 01:12 PM

View PostSixOfEleven, on 7 May, 2009 - 12:02 PM, said:

View PostStarBP, on 7 May, 2009 - 09:23 AM, said:

View PostSixOfEleven, on 7 May, 2009 - 09:21 AM, said:

I have to leave right now but I will take a look at the program a little later.


OK, thanks. Remember, if you find any other performance enhancements that can be done, you can tell me what they are, too (However, no other performance enhancement will really make a difference unless the Renderer is improved).


I've been looking at the code. Maybe you could help me a little. Can you paste a link to the entry in the blog that describes the program? I need to better understand the process that is being used.


Here are the posts about EvoLisa:

http://rogeralsing.c...n-of-mona-lisa/
http://rogeralsing.c...-mona-lisa-faq/

http://rogeralsing.c...e-and-binaries/
http://rogeralsing.c...enetic-gallery/
http://rogeralsing.c...misconceptions/
http://rogeralsing.c...proved-quality/
http://rogeralsing.c...res-in-evolisa/
http://rogeralsing.c...ng-gp-ga-ep-es/
http://rogeralsing.c...-have-lift-off/
http://rogeralsing.c...volution-1-1-4/

And the improvements:

http://danbystrom.se...serwisser-blog/
http://danbystrom.se...ng-performance/

http://danbystrom.se...ptimizing-away/
http://danbystrom.se...mizing-away-ii/
http://danbystrom.se...izing-away-ii3/

I have bolded the most relevant posts. Note: The source code at Roger's website uses an outdated fitness function which is over 25x slower. Use my source code instead (although feel free to look at his for a good laugh).

EDIT: I forgot to add one link on EvoLisa. Here it is:
http://rogeralsing.c...ry-compression/

This post has been edited by StarBP: 07 May 2009 - 02:26 PM

Was This Post Helpful? 0
  • +
  • -

#9 StarBP   User is offline

  • New D.I.C Head

Reputation: 1
  • View blog
  • Posts: 42
  • Joined: 06-May 09

Re: Polygon Rendering Performance Optimization

Posted 08 May 2009 - 01:03 PM

Anyone able to help me?
Was This Post Helpful? 0
  • +
  • -

#10 SixOfEleven   User is offline

  • Planeswalker
  • member icon

Reputation: 1055
  • View blog
  • Posts: 6,643
  • Joined: 18-October 08

Re: Polygon Rendering Performance Optimization

Posted 08 May 2009 - 01:30 PM

It's a very interesting program, I'm looking at it but so far don't really know what to do to optimize it. :(
Was This Post Helpful? 0
  • +
  • -

#11 StarBP   User is offline

  • New D.I.C Head

Reputation: 1
  • View blog
  • Posts: 42
  • Joined: 06-May 09

Re: Polygon Rendering Performance Optimization

Posted 08 May 2009 - 02:59 PM

View PostSixOfEleven, on 8 May, 2009 - 12:30 PM, said:

It's a very interesting program, I'm looking at it but so far don't really know what to do to optimize it. :(


This is from my first post:

"The key is to use System.Windows.Shapes.Polygon so only one polygon would usually need to be rendered per generation (maybe two or three, but certainly not all of them as is required now). I do not even know where to start on this, although I know that using Clone() is very inefficient compared to storing a change and doing it twice around 10% of the time (The mutations make the picture better around 1/10 of the time)."

This post has been edited by StarBP: 08 May 2009 - 03:14 PM

Was This Post Helpful? 0
  • +
  • -

#12 SixOfEleven   User is offline

  • Planeswalker
  • member icon

Reputation: 1055
  • View blog
  • Posts: 6,643
  • Joined: 18-October 08

Re: Polygon Rendering Performance Optimization

Posted 08 May 2009 - 03:43 PM

I can't seem to find the System.Windows.Shapes.Polygon name space? It does not come up in my intelli-sense when I enter it in the using statement and it is not listed in the .NET framework documentation either.
Was This Post Helpful? 0
  • +
  • -

#13 StarBP   User is offline

  • New D.I.C Head

Reputation: 1
  • View blog
  • Posts: 42
  • Joined: 06-May 09

Re: Polygon Rendering Performance Optimization

Posted 08 May 2009 - 06:58 PM

View PostSixOfEleven, on 8 May, 2009 - 02:43 PM, said:

I can't seem to find the System.Windows.Shapes.Polygon name space? It does not come up in my intelli-sense when I enter it in the using statement and it is not listed in the .NET framework documentation either.


It's a CLASS, not a namespace!!! Also, a correction on my part: When I said System.Graphics, I meant System.Drawing.Graphics. Now can you help me?
Was This Post Helpful? 0
  • +
  • -

#14 SixOfEleven   User is offline

  • Planeswalker
  • member icon

Reputation: 1055
  • View blog
  • Posts: 6,643
  • Joined: 18-October 08

Re: Polygon Rendering Performance Optimization

Posted 08 May 2009 - 08:08 PM

View PostStarBP, on 8 May, 2009 - 07:58 PM, said:

View PostSixOfEleven, on 8 May, 2009 - 02:43 PM, said:

I can't seem to find the System.Windows.Shapes.Polygon name space? It does not come up in my intelli-sense when I enter it in the using statement and it is not listed in the .NET framework documentation either.


It's a CLASS, not a namespace!!! Also, a correction on my part: When I said System.Graphics, I meant System.Drawing.Graphics. Now can you help me?


I will try.
Was This Post Helpful? 0
  • +
  • -

#15 SixOfEleven   User is offline

  • Planeswalker
  • member icon

Reputation: 1055
  • View blog
  • Posts: 6,643
  • Joined: 18-October 08

Re: Polygon Rendering Performance Optimization

Posted 08 May 2009 - 09:19 PM

I have done a search on System.Windows.Shapes. Unfortunately this is part of WPF, not WinForms. I do have an idea on how to use this but it will take a while for me to implement it. I will try and get back to you soon.
Was This Post Helpful? 0
  • +
  • -

  • (2 Pages)
  • +
  • 1
  • 2