Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- // http://forum.unity3d.com/threads/144235-A-Fast-KD-Tree-or-Unity-Alternative
- // All rights reserved. Copyright NPSF3000 2012 Attribution Required.
- // I think I have enough data to give an example of how I'd tackle the problem.
- // This is written as a console application in VS because it has a few more features
- // and niceties to reduce my prototyping time. Feel free to use it as a console app,
- // or port it unity or even windows forms!
- // Tested on a i3 2120, windows 7 64, x86 build, plenty of ram and a SSD.
- // This version has had multithreading implemented.
- using System;
- using System.Collections.Generic;
- using System.Diagnostics;
- using System.Drawing;
- using System.Drawing.Imaging;
- using System.Linq;
- using System.Threading.Tasks;
- namespace TextureFromPoints3Threaded
- {
- class Program
- {
- const int numSensors = 700000;
- const int textureSize = 1024;
- const int intervals = 10;
- //Changing hash size can have dramatic effect on the my Spacial Collection's performance.
- //Ideal hash size relies upon the densisty of sensors:pixels -
- //For example the hash size of 2 will fill a 1024x1024 texture with 70,000 points in 0.5s.
- //However, if you reduce the number of points to 700 it will take 13 seconds.
- //Setting hash to less than 1 will use a simple formula to guess the correct size.
- //Otherwise the code will use whatever variable you choose.
- static int hash = -1;
- static Random rnd = new Random();
- static void Main(string[] args)
- {
- while (true)
- {
- Console.WriteLine("Starting");
- Console.WriteLine();
- var swTotalTime = Stopwatch.StartNew();
- //Step one: get the raw data:
- var sensors = GetData();
- //Step 2&3 - generate the sensor texture. We create a new spacial hash for every thread.
- //This decreases texture geration time from 700ms to about 500ms.
- //As such, at these settings the improvement is minimal - tough different workloads may vary.
- var sw = Stopwatch.StartNew();
- int threadCount = Environment.ProcessorCount / 2;
- Sensor[,] sensorTexture = new Sensor[textureSize, textureSize];
- if (hash < 1)
- {
- var magic = Math.Sqrt(textureSize * textureSize / numSensors) / 2; //Magic Formula
- hash = (int)Math.Pow(2, (int)(Math.Log(magic - 1, 2)) + 1); //Rounds up to nearest power of 2.
- if (hash < 1) hash = 1;
- Console.WriteLine("Rough Hash Generated: {0} [Magic Density : {1}]", hash, magic);
- }
- else
- Console.WriteLine("Using Harcoded Hash: {0}", hash);
- Parallel.For(0, threadCount, i =>
- {
- //Generate the spacial hash
- var spacialhash = new SimpleSpacialCollection(textureSize, hash);
- foreach (var sensor in sensors) spacialhash.AddSensor(sensor);
- //remember the offset
- int offsetSize = textureSize / threadCount;
- int offset = offsetSize * i;
- //Create the array to store the elements
- var result = new Sensor[offsetSize, textureSize];
- //Fill the result
- for (int x = 0; x < offsetSize; x++)
- for (int y = 0; y < textureSize; y++)
- result[x, y] = spacialhash.GetNearest(x + offset, y);
- //Copies the result to the sensorTexture.
- Array.Copy(result, 0, sensorTexture, offset * textureSize, result.Length);
- });
- sw.Stop();
- Console.WriteLine("Mapped {0} sensors to {1}x{1} pixels in {2}ms", numSensors, textureSize, sw.ElapsedMilliseconds);
- //Step 4&5 - Creating and saving textures.
- var sw5 = Stopwatch.StartNew();
- var textures = new Bitmap[intervals];
- Parallel.For(0, intervals, i =>
- {
- var sw1 = Stopwatch.StartNew();
- var bmp = new Bitmap(textureSize, textureSize);
- for (int x = 0; x < textureSize; x++)
- for (int y = 0; y < textureSize; y++)
- {
- var sensor = sensorTexture[x, y];
- bmp.SetPixel(x, y, Color.FromArgb((int)(255 * sensor.data[i]), (int)(255 * sensor.data[i]), (int)(255 * sensor.data[i])));
- }
- textures[i] = bmp;
- sw1.Stop();
- Console.WriteLine("Created Texture {0} in {1}ms", i, sw1.ElapsedMilliseconds);
- //It makes sence to combine IO and Compute bound tasks together - so IO isn't idling.
- sw1 = Stopwatch.StartNew();
- textures[i].Save("C:\\" + i + ".png", ImageFormat.Png);
- textures[i].Dispose(); //This is new - keeps memory consumption down!
- Console.WriteLine("Saved Texture {0} in {1}ms", i, sw1.ElapsedMilliseconds);
- });
- sw5.Stop();
- Console.WriteLine("Created & Saved {0} Textures in {1}ms", intervals, sw5.ElapsedMilliseconds);
- swTotalTime.Stop();
- Console.WriteLine();
- Console.WriteLine("All finished in {0}ms", swTotalTime.ElapsedMilliseconds);
- Console.ReadLine();
- //With Multithreading 200 images, 70k points, 1024 by 1024 takes 86s - faster than the single threaded version at 188.7s.
- //I removed the duplication of the bitmap for saving [apparent bug fix that's not needed and managed
- }
- }
- private static Sensor[] GetData()
- {
- // I don't care how you manage it, but I figure you need a sensor
- // that has a 2d position [corrisponding with the texture co-ords]
- // and has a array of values that shows teh sensor's value every interval.
- // So I faked itL
- var sensors = new Sensor[numSensors];
- for (int i = 0; i < numSensors; i++)
- {
- var sensor = new Sensor();
- sensor.position = new Vector2(textureSize);
- sensor.data = Enumerable.Range(0, intervals).Select(_ => (float)rnd.NextDouble()).ToArray();
- sensors[i] = sensor;
- }
- return sensors;
- }
- /* private static bool CheckResults(Vector2[,] lhs, Vector2[,] rhs)
- {
- for (int x = 0; x < textureSize; x++)
- for (int y = 0; y < textureSize; y++)
- if (!lhs[x, y].Equals(rhs[x, y]))
- return false;
- return true;
- }*/
- public struct Sensor
- {
- public Vector2 position;
- public float[] data;
- }
- public struct Vector2
- {
- public float x;
- public float y;
- public Vector2(float x, float y)
- {
- this.x = x;
- this.y = y;
- }
- public Vector2(float randomDistance)
- {
- this.x = (float)rnd.NextDouble() * randomDistance;
- this.y = (float)rnd.NextDouble() * randomDistance;
- }
- public static Vector2 operator -(Vector2 a, Vector2 b)
- {
- return new Vector2(a.x - b.x, a.y - b.y);
- }
- public float sqrMagnitude()
- {
- return x * x + y * y;
- }
- public float sqrDistanceToPoint(Vector2 point)
- {
- var x = this.x - point.x;
- var y = this.y - point.y;
- return x * x + y * y;
- }
- }
- public class SimpleSpacialCollection
- {
- List<Sensor>[,] buckets;
- int bounds;
- int hash;
- public SimpleSpacialCollection(int bounds, int hash)
- {
- this.bounds = bounds;
- this.hash = hash;
- buckets = new List<Sensor>[bounds / hash + 1, bounds / hash + 1];
- }
- public void AddSensor(Sensor sensor)
- {
- GetBucket(sensor.position).Add(sensor);
- }
- List<Sensor> GetBucket(Vector2 v2)
- {
- return GetBucket((int)v2.x, (int)v2.y);
- }
- List<Sensor> GetBucket(int x, int y)
- {
- var bucket = buckets[x / hash, y / hash];
- if (bucket == null)
- {
- bucket = new List<Sensor>();
- buckets[x / hash, y / hash] = bucket;
- }
- return bucket;
- }
- public Sensor GetNearest(int pointX, int pointY)
- {
- var candidates = new List<Sensor>();
- int maxX, minX, maxY, minY;
- maxX = minX = pointX / hash;
- maxY = minY = pointY / hash;
- do
- {
- maxX++; maxY++; minX--; minY--;
- if (minX < 0) minX = 0;
- if (minY < 0) minY = 0;
- if (maxX > buckets.GetLength(0)) maxX = buckets.GetLength(0);
- if (maxY > buckets.GetLength(1)) maxY = buckets.GetLength(1);
- for (int x = minX; x < maxX; x++)
- for (int y = minY; y < maxY; y++)
- {
- var bucket = buckets[x, y];
- if (bucket != null) candidates.AddRange(bucket);
- }
- } while (candidates.Count == 0); //Potential Infinite Loop.
- var point = new Vector2(pointX, pointY);
- Sensor nearest = candidates[0];
- float nearestDistance = nearest.position.sqrDistanceToPoint(point);
- for (int i = 1; i < candidates.Count; i++)
- {
- var candidate = candidates[i];
- if (candidate.position.sqrDistanceToPoint(point) < nearestDistance)
- {
- nearest = candidate;
- nearestDistance = candidate.position.sqrDistanceToPoint(point);
- }
- }
- return nearest;
- }
- }
- }
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement