//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;
}
}
}
}