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!
- using System;
- using System.Collections.Generic;
- using System.Diagnostics;
- using System.Drawing;
- using System.Drawing.Imaging;
- using System.Linq;
- namespace TextureFromPoints3
- {
- class Program
- {
- const int numSensors = 70000;
- const int textureSize = 1024;
- const int intervals = 0;
- 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 two: put sensors into a searchable collection.
- //I built my own to keep things simple.
- //Of course, it's not well tested.
- var spacialhash = new SimpleSpacialCollection(textureSize, 1);
- foreach (var sensor in sensors) spacialhash.AddSensor(sensor);
- //Now let's map each 'pixel' to a sensor;
- //This basic mapping takes about 0.5 seconds.
- Sensor[,] sensorTexture = new Sensor[textureSize, textureSize];
- var sw = Stopwatch.StartNew();
- for (int x = 0; x < textureSize; x++)
- for (int y = 0; y < textureSize; y++)
- sensorTexture[x, y] = spacialhash.GetNearest(x, y);
- sw.Stop();
- Console.WriteLine("Mapped {0} sensors to {1}x{1} pixels in {2}ms", numSensors, textureSize, sw.ElapsedMilliseconds);
- //Now let's generate each texture
- //We use System.Drawing for this - though U3D's Texture2D class should have similar features.
- //This takes about 0.85s an image.
- var textures = new Bitmap[intervals];
- for (int i = 0; i < 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);
- }
- //Now let us save each image.
- //This takes around 0.02s - though I am on a SSD.
- for (int i = 0; i < intervals; i++)
- {
- var sw1 = Stopwatch.StartNew();
- new Bitmap(textures[i]).Save("C:\\" + i + ".png", ImageFormat.Png);
- Console.WriteLine("Saved Texture {0} in {1}ms", i, sw1.ElapsedMilliseconds);
- }
- swTotalTime.Stop();
- Console.WriteLine();
- Console.WriteLine("All finished in {0}ms", swTotalTime.ElapsedMilliseconds);
- Console.ReadLine();
- //And that's everything IIRC?
- //Unless theres a major change, I've taken your '30 hours' for 200 textures and
- //Changed it into:
- //0.5 + (0.8+0.08)*n = 0.5 + (0.85+0.08)*200 = 186.5s
- //Tested and I completed in 188.7ms - and that includes gererating the test data and spacial hash! :P
- //It's late so I'll leave multithreading for tomorrow.
- //It's pretty trvial in .Net, but the libraries I use aren't available in U3D IIRC.
- //Thanks for all the fish.
- }
- }
- 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