Advertisement
NPSF3000

TextureFromPoints3Threaded

Jul 20th, 2012
382
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C# 10.76 KB | None | 0 0
  1. //  http://forum.unity3d.com/threads/144235-A-Fast-KD-Tree-or-Unity-Alternative
  2. //  All rights reserved. Copyright NPSF3000 2012  Attribution Required.
  3.  
  4. //  I think I have enough data to give an example of how I'd tackle the problem.
  5. //  This is written as a console application in VS because it has a few more features
  6. //  and niceties to reduce my prototyping time.  Feel free to use it as a console app,
  7. //  or port it unity or even windows forms!
  8.  
  9. //  Tested on a i3 2120, windows 7 64, x86 build, plenty of ram and a SSD.
  10.  
  11. //  This version has had multithreading implemented.
  12.  
  13. using System;
  14. using System.Collections.Generic;
  15. using System.Diagnostics;
  16. using System.Drawing;
  17. using System.Drawing.Imaging;
  18. using System.Linq;
  19. using System.Threading.Tasks;
  20.  
  21. namespace TextureFromPoints3Threaded
  22. {
  23.     class Program
  24.     {
  25.         const int numSensors = 700000;
  26.         const int textureSize = 1024;
  27.         const int intervals = 10;
  28.  
  29.         //Changing hash size can have dramatic effect on the my Spacial Collection's performance.
  30.         //Ideal hash size relies upon the densisty of sensors:pixels -
  31.         //For example the hash size of 2 will fill a 1024x1024 texture with 70,000 points in 0.5s.
  32.         //However, if you reduce the number of points to 700 it will take 13 seconds.
  33.         //Setting hash to less than 1 will use a simple formula to guess the correct size.
  34.         //Otherwise the code will use whatever variable you choose.
  35.         static int hash = -1;
  36.  
  37.         static Random rnd = new Random();
  38.  
  39.         static void Main(string[] args)
  40.         {
  41.  
  42.             while (true)
  43.             {
  44.                 Console.WriteLine("Starting");
  45.                 Console.WriteLine();
  46.  
  47.                 var swTotalTime = Stopwatch.StartNew();
  48.  
  49.                 //Step one: get the raw data:
  50.                 var sensors = GetData();
  51.  
  52.                 //Step 2&3 - generate the sensor texture.  We create a new spacial hash for every thread.
  53.                 //This decreases texture geration time from 700ms to about 500ms.
  54.                 //As such, at these settings the improvement is minimal - tough different workloads may vary.
  55.                 var sw = Stopwatch.StartNew();
  56.                 int threadCount = Environment.ProcessorCount / 2;
  57.  
  58.                 Sensor[,] sensorTexture = new Sensor[textureSize, textureSize];
  59.                 if (hash < 1)
  60.                 {
  61.                     var magic = Math.Sqrt(textureSize * textureSize / numSensors) / 2;  //Magic Formula
  62.                     hash = (int)Math.Pow(2, (int)(Math.Log(magic - 1, 2)) + 1);  //Rounds up to nearest power of 2.
  63.                     if (hash < 1) hash = 1;
  64.                     Console.WriteLine("Rough Hash Generated: {0}  [Magic Density : {1}]", hash, magic);
  65.                 }
  66.                 else
  67.                     Console.WriteLine("Using Harcoded Hash: {0}", hash);
  68.  
  69.                 Parallel.For(0, threadCount, i =>
  70.                 {
  71.                     //Generate the spacial hash
  72.                     var spacialhash = new SimpleSpacialCollection(textureSize, hash);
  73.  
  74.                     foreach (var sensor in sensors) spacialhash.AddSensor(sensor);
  75.  
  76.                     //remember the offset
  77.                     int offsetSize = textureSize / threadCount;
  78.                     int offset = offsetSize * i;
  79.                     //Create the array to store the elements
  80.                     var result = new Sensor[offsetSize, textureSize];
  81.  
  82.                     //Fill the result
  83.                     for (int x = 0; x < offsetSize; x++)
  84.                         for (int y = 0; y < textureSize; y++)
  85.                             result[x, y] = spacialhash.GetNearest(x + offset, y);
  86.  
  87.                     //Copies the result to the sensorTexture.
  88.                     Array.Copy(result, 0, sensorTexture, offset * textureSize, result.Length);
  89.                 });
  90.                 sw.Stop();
  91.  
  92.                 Console.WriteLine("Mapped {0} sensors to {1}x{1} pixels in {2}ms", numSensors, textureSize, sw.ElapsedMilliseconds);
  93.  
  94.                 //Step 4&5 - Creating and saving textures.
  95.                 var sw5 = Stopwatch.StartNew();
  96.                 var textures = new Bitmap[intervals];
  97.                 Parallel.For(0, intervals, i =>
  98.                 {
  99.                     var sw1 = Stopwatch.StartNew();
  100.                     var bmp = new Bitmap(textureSize, textureSize);
  101.                     for (int x = 0; x < textureSize; x++)
  102.                         for (int y = 0; y < textureSize; y++)
  103.                         {
  104.                             var sensor = sensorTexture[x, y];
  105.                             bmp.SetPixel(x, y, Color.FromArgb((int)(255 * sensor.data[i]), (int)(255 * sensor.data[i]), (int)(255 * sensor.data[i])));
  106.                         }
  107.                     textures[i] = bmp;
  108.                     sw1.Stop();
  109.                     Console.WriteLine("Created Texture {0} in {1}ms", i, sw1.ElapsedMilliseconds);
  110.  
  111.                     //It makes sence to combine IO and Compute bound tasks together - so IO isn't idling.
  112.                     sw1 = Stopwatch.StartNew();
  113.                     textures[i].Save("C:\\" + i + ".png", ImageFormat.Png);
  114.                     textures[i].Dispose();  //This is new - keeps memory consumption down!
  115.                     Console.WriteLine("Saved Texture {0} in {1}ms", i, sw1.ElapsedMilliseconds);
  116.                 });
  117.                 sw5.Stop();
  118.  
  119.                 Console.WriteLine("Created & Saved {0} Textures in {1}ms", intervals, sw5.ElapsedMilliseconds);
  120.  
  121.                 swTotalTime.Stop();
  122.  
  123.                 Console.WriteLine();
  124.                 Console.WriteLine("All finished in {0}ms", swTotalTime.ElapsedMilliseconds);
  125.                 Console.ReadLine();
  126.  
  127.  
  128.                 //With Multithreading 200 images, 70k points, 1024 by 1024 takes 86s - faster than the single threaded version at 188.7s.
  129.                 //I removed the duplication of the bitmap for saving [apparent bug fix that's not needed and managed
  130.             }
  131.         }
  132.  
  133.         private static Sensor[] GetData()
  134.         {
  135.             //  I don't care how you manage it, but I figure you need a sensor
  136.             //  that has a 2d position [corrisponding with the texture co-ords]
  137.             //  and has a array of values that shows teh sensor's value every interval.
  138.             //  So I faked itL
  139.             var sensors = new Sensor[numSensors];
  140.  
  141.             for (int i = 0; i < numSensors; i++)
  142.             {
  143.                 var sensor = new Sensor();
  144.                 sensor.position = new Vector2(textureSize);
  145.                 sensor.data = Enumerable.Range(0, intervals).Select(_ => (float)rnd.NextDouble()).ToArray();
  146.                 sensors[i] = sensor;
  147.             }
  148.             return sensors;
  149.         }
  150.  
  151.         /* private static bool CheckResults(Vector2[,] lhs, Vector2[,] rhs)
  152.          {
  153.              for (int x = 0; x < textureSize; x++)
  154.                  for (int y = 0; y < textureSize; y++)
  155.                      if (!lhs[x, y].Equals(rhs[x, y]))
  156.                          return false;
  157.              return true;
  158.          }*/
  159.  
  160.         public struct Sensor
  161.         {
  162.             public Vector2 position;
  163.             public float[] data;
  164.         }
  165.  
  166.         public struct Vector2
  167.         {
  168.             public float x;
  169.             public float y;
  170.  
  171.             public Vector2(float x, float y)
  172.             {
  173.                 this.x = x;
  174.                 this.y = y;
  175.             }
  176.  
  177.             public Vector2(float randomDistance)
  178.             {
  179.                 this.x = (float)rnd.NextDouble() * randomDistance;
  180.                 this.y = (float)rnd.NextDouble() * randomDistance;
  181.             }
  182.  
  183.             public static Vector2 operator -(Vector2 a, Vector2 b)
  184.             {
  185.                 return new Vector2(a.x - b.x, a.y - b.y);
  186.             }
  187.  
  188.             public float sqrMagnitude()
  189.             {
  190.                 return x * x + y * y;
  191.             }
  192.  
  193.             public float sqrDistanceToPoint(Vector2 point)
  194.             {
  195.                 var x = this.x - point.x;
  196.                 var y = this.y - point.y;
  197.                 return x * x + y * y;
  198.             }
  199.         }
  200.  
  201.         public class SimpleSpacialCollection
  202.         {
  203.             List<Sensor>[,] buckets;
  204.             int bounds;
  205.             int hash;
  206.  
  207.             public SimpleSpacialCollection(int bounds, int hash)
  208.             {
  209.                 this.bounds = bounds;
  210.                 this.hash = hash;
  211.                 buckets = new List<Sensor>[bounds / hash + 1, bounds / hash + 1];
  212.             }
  213.  
  214.             public void AddSensor(Sensor sensor)
  215.             {
  216.                 GetBucket(sensor.position).Add(sensor);
  217.             }
  218.  
  219.             List<Sensor> GetBucket(Vector2 v2)
  220.             {
  221.                 return GetBucket((int)v2.x, (int)v2.y);
  222.             }
  223.  
  224.             List<Sensor> GetBucket(int x, int y)
  225.             {
  226.                 var bucket = buckets[x / hash, y / hash];
  227.                 if (bucket == null)
  228.                 {
  229.                     bucket = new List<Sensor>();
  230.                     buckets[x / hash, y / hash] = bucket;
  231.                 }
  232.                 return bucket;
  233.             }
  234.  
  235.             public Sensor GetNearest(int pointX, int pointY)
  236.             {
  237.                 var candidates = new List<Sensor>();
  238.  
  239.                 int maxX, minX, maxY, minY;
  240.  
  241.                 maxX = minX = pointX / hash;
  242.                 maxY = minY = pointY / hash;
  243.  
  244.                 do
  245.                 {
  246.                     maxX++; maxY++; minX--; minY--;
  247.  
  248.                     if (minX < 0) minX = 0;
  249.                     if (minY < 0) minY = 0;
  250.                     if (maxX > buckets.GetLength(0)) maxX = buckets.GetLength(0);
  251.                     if (maxY > buckets.GetLength(1)) maxY = buckets.GetLength(1);
  252.  
  253.                     for (int x = minX; x < maxX; x++)
  254.                         for (int y = minY; y < maxY; y++)
  255.                         {
  256.                             var bucket = buckets[x, y];
  257.                             if (bucket != null) candidates.AddRange(bucket);
  258.                         }
  259.                 } while (candidates.Count == 0);  //Potential Infinite Loop.
  260.  
  261.                 var point = new Vector2(pointX, pointY);
  262.  
  263.                 Sensor nearest = candidates[0];
  264.                 float nearestDistance = nearest.position.sqrDistanceToPoint(point);
  265.  
  266.                 for (int i = 1; i < candidates.Count; i++)
  267.                 {
  268.                     var candidate = candidates[i];
  269.                     if (candidate.position.sqrDistanceToPoint(point) < nearestDistance)
  270.                     {
  271.                         nearest = candidate;
  272.                         nearestDistance = candidate.position.sqrDistanceToPoint(point);
  273.                     }
  274.                 }
  275.                 return nearest;
  276.             }
  277.         }
  278.     }
  279. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement