Pastebin launched a little side project called VERYVIRAL.com, check it out ;-) Want more features on Pastebin? Sign Up, it's FREE!
Guest

TextureFromPoints3

By: NPSF3000 on Jul 20th, 2012  |  syntax: C#  |  size: 9.12 KB  |  views: 93  |  expires: Never
download  |  raw  |  embed  |  report abuse  |  print
Text below is selected. Please press Ctrl+C to copy to your clipboard. (⌘+C on Mac)
  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. using System;
  10. using System.Collections.Generic;
  11. using System.Diagnostics;
  12. using System.Drawing;
  13. using System.Drawing.Imaging;
  14. using System.Linq;
  15.  
  16. namespace TextureFromPoints3
  17. {
  18.     class Program
  19.     {
  20.         const int numSensors = 70000;
  21.         const int textureSize = 1024;
  22.         const int intervals = 0;
  23.  
  24.         static Random rnd = new Random();
  25.  
  26.         static void Main(string[] args)
  27.         {
  28.             while (true)
  29.             {
  30.                 Console.WriteLine("Starting");
  31.                 Console.WriteLine();
  32.  
  33.                 var swTotalTime = Stopwatch.StartNew();
  34.  
  35.                 //Step one: get the raw data:
  36.                 var sensors = GetData();
  37.  
  38.                 //Step two: put sensors into a searchable collection.
  39.                 //I built my own to keep things simple.
  40.                 //Of course, it's not well tested.
  41.                 var spacialhash = new SimpleSpacialCollection(textureSize, 1);
  42.                 foreach (var sensor in sensors) spacialhash.AddSensor(sensor);
  43.  
  44.                 //Now let's map each 'pixel' to a sensor;
  45.                 //This basic mapping takes about 0.5 seconds.
  46.                 Sensor[,] sensorTexture = new Sensor[textureSize, textureSize];
  47.                 var sw = Stopwatch.StartNew();
  48.                 for (int x = 0; x < textureSize; x++)
  49.                     for (int y = 0; y < textureSize; y++)
  50.                         sensorTexture[x, y] = spacialhash.GetNearest(x, y);
  51.                 sw.Stop();
  52.                 Console.WriteLine("Mapped {0} sensors to {1}x{1} pixels in {2}ms", numSensors, textureSize, sw.ElapsedMilliseconds);
  53.  
  54.                 //Now let's generate each texture
  55.                 //We use System.Drawing for this - though U3D's Texture2D class should have similar features.
  56.                 //This takes about 0.85s an image.
  57.                 var textures = new Bitmap[intervals];
  58.                 for (int i = 0; i < intervals; i++)
  59.                 {
  60.                     var sw1 = Stopwatch.StartNew();
  61.                     var bmp = new Bitmap(textureSize, textureSize);
  62.                     for (int x = 0; x < textureSize; x++)
  63.                         for (int y = 0; y < textureSize; y++)
  64.                         {
  65.                             var sensor = sensorTexture[x, y];
  66.                             bmp.SetPixel(x, y, Color.FromArgb((int)(255 * sensor.data[i]), (int)(255 * sensor.data[i]), (int)(255 * sensor.data[i])));
  67.                         }
  68.                     textures[i] = bmp;
  69.                     sw1.Stop();
  70.                     Console.WriteLine("Created Texture {0} in {1}ms", i, sw1.ElapsedMilliseconds);
  71.                 }
  72.  
  73.                 //Now let us save each image.
  74.                 //This takes around 0.02s - though I am on a SSD.
  75.                 for (int i = 0; i < intervals; i++)
  76.                 {
  77.                     var sw1 = Stopwatch.StartNew();
  78.                     new Bitmap(textures[i]).Save("C:\\" + i + ".png", ImageFormat.Png);
  79.                     Console.WriteLine("Saved Texture {0} in {1}ms", i, sw1.ElapsedMilliseconds);
  80.                 }
  81.  
  82.                 swTotalTime.Stop();
  83.  
  84.                 Console.WriteLine();
  85.                 Console.WriteLine("All finished in {0}ms", swTotalTime.ElapsedMilliseconds);
  86.                 Console.ReadLine();
  87.  
  88.                 //And that's everything IIRC?
  89.                 //Unless theres a major change, I've taken your '30 hours' for 200 textures and
  90.                 //Changed it into:
  91.                 //0.5 + (0.8+0.08)*n = 0.5 + (0.85+0.08)*200 = 186.5s
  92.                 //Tested and I completed in 188.7ms - and that includes gererating the test data and spacial hash! :P
  93.  
  94.                 //It's late so I'll leave multithreading for tomorrow.
  95.                 //It's pretty trvial in .Net, but the libraries I use aren't available in U3D IIRC.
  96.  
  97.                 //Thanks for all the fish.
  98.             }
  99.         }
  100.  
  101.         private static Sensor[] GetData()
  102.         {
  103.             //  I don't care how you manage it, but I figure you need a sensor
  104.             //  that has a 2d position [corrisponding with the texture co-ords]
  105.             //  and has a array of values that shows teh sensor's value every interval.
  106.             //  So I faked itL
  107.             var sensors = new Sensor[numSensors];
  108.  
  109.             for (int i = 0; i < numSensors; i++)
  110.             {
  111.                 var sensor = new Sensor();
  112.                 sensor.position = new Vector2(textureSize);
  113.                 sensor.data = Enumerable.Range(0, intervals).Select(_ => (float)rnd.NextDouble()).ToArray();
  114.                 sensors[i] = sensor;
  115.             }
  116.             return sensors;
  117.         }
  118.  
  119.         /* private static bool CheckResults(Vector2[,] lhs, Vector2[,] rhs)
  120.          {
  121.              for (int x = 0; x < textureSize; x++)
  122.                  for (int y = 0; y < textureSize; y++)
  123.                      if (!lhs[x, y].Equals(rhs[x, y]))
  124.                          return false;
  125.              return true;
  126.          }*/
  127.  
  128.         public struct Sensor
  129.         {
  130.             public Vector2 position;
  131.             public float[] data;
  132.         }
  133.  
  134.         public struct Vector2
  135.         {
  136.             public float x;
  137.             public float y;
  138.  
  139.             public Vector2(float x, float y)
  140.             {
  141.                 this.x = x;
  142.                 this.y = y;
  143.             }
  144.  
  145.             public Vector2(float randomDistance)
  146.             {
  147.                 this.x = (float)rnd.NextDouble() * randomDistance;
  148.                 this.y = (float)rnd.NextDouble() * randomDistance;
  149.             }
  150.  
  151.             public static Vector2 operator -(Vector2 a, Vector2 b)
  152.             {
  153.                 return new Vector2(a.x - b.x, a.y - b.y);
  154.             }
  155.  
  156.             public float sqrMagnitude()
  157.             {
  158.                 return x * x + y * y;
  159.             }
  160.  
  161.             public float sqrDistanceToPoint(Vector2 point)
  162.             {
  163.                 var x = this.x - point.x;
  164.                 var y = this.y - point.y;
  165.                 return x * x + y * y;
  166.             }
  167.         }
  168.  
  169.         public class SimpleSpacialCollection
  170.         {
  171.             List<Sensor>[,] buckets;
  172.             int bounds;
  173.             int hash;
  174.  
  175.             public SimpleSpacialCollection(int bounds, int hash)
  176.             {
  177.                 this.bounds = bounds;
  178.                 this.hash = hash;
  179.                 buckets = new List<Sensor>[bounds / hash + 1, bounds / hash + 1];
  180.             }
  181.  
  182.             public void AddSensor(Sensor sensor)
  183.             {
  184.                 GetBucket(sensor.position).Add(sensor);
  185.             }
  186.  
  187.             List<Sensor> GetBucket(Vector2 v2)
  188.             {
  189.                 return GetBucket((int)v2.x, (int)v2.y);
  190.             }
  191.  
  192.             List<Sensor> GetBucket(int x, int y)
  193.             {
  194.                 var bucket = buckets[x / hash, y / hash];
  195.                 if (bucket == null)
  196.                 {
  197.                     bucket = new List<Sensor>();
  198.                     buckets[x / hash, y / hash] = bucket;
  199.                 }
  200.                 return bucket;
  201.             }
  202.  
  203.             public Sensor GetNearest(int pointX, int pointY)
  204.             {
  205.                 var candidates = new List<Sensor>();
  206.  
  207.                 int maxX, minX, maxY, minY;
  208.  
  209.                 maxX = minX = pointX / hash;
  210.                 maxY = minY = pointY / hash;
  211.  
  212.                 do
  213.                 {
  214.                     maxX++; maxY++; minX--; minY--;
  215.  
  216.                     if (minX < 0) minX = 0;
  217.                     if (minY < 0) minY = 0;
  218.                     if (maxX > buckets.GetLength(0)) maxX = buckets.GetLength(0);
  219.                     if (maxY > buckets.GetLength(1)) maxY = buckets.GetLength(1);
  220.  
  221.                     for (int x = minX; x < maxX; x++)
  222.                         for (int y = minY; y < maxY; y++)
  223.                         {
  224.                             var bucket = buckets[x, y];
  225.                             if (bucket != null) candidates.AddRange(bucket);
  226.                         }
  227.                 } while (candidates.Count == 0);  //Potential Infinite Loop.
  228.  
  229.                 var point = new Vector2(pointX, pointY);
  230.  
  231.                 Sensor nearest = candidates[0];
  232.                 float nearestDistance = nearest.position.sqrDistanceToPoint(point);
  233.  
  234.                 for (int i = 1; i < candidates.Count; i++)
  235.                 {
  236.                     var candidate = candidates[i];
  237.                     if (candidate.position.sqrDistanceToPoint(point) < nearestDistance)
  238.                     {
  239.                         nearest = candidate;
  240.                         nearestDistance = candidate.position.sqrDistanceToPoint(point);
  241.                     }
  242.                 }
  243.                 return nearest;
  244.             }
  245.         }
  246.     }
  247. }