Search Unity

  1. Megacity Metro Demo now available. Download now.
    Dismiss Notice
  2. Unity support for visionOS is now available. Learn more in our blog post.
    Dismiss Notice

A Fast KD-Tree or Unity Alternative

Discussion in 'Scripting' started by karljj1, Jul 18, 2012.

  1. karljj1

    karljj1

    Joined:
    Feb 17, 2011
    Posts:
    440
    Hi,

    1)

    I have a large amount of data which is associated to real world positions. (70,000+ points).

    I currently put this data into a KD-Tree (Currently using this one: http://home.wlu.edu/~levys/software/kd/).
    I then have an editor script that goes through a texture and performs a lookup for each pixel using the KD-Tree, it then sets the texture based on the nearest value.

    Everything works however it takes about 30 hours to generate 200 1024x1024 textures, can anyone suggest either a better/faster method? I tried to multithread the process however it seems to go slower, I think my KD-Tree does not support multi threading? Does unity have any features that would help me?

    2)

    Can I multi thread creating textures in Unity? E.G split the task of creating 200 over 4 threads? Or does the Texture2D class not support multithreading?



    Thanks

    Karl
     
  2. Brian-Stone

    Brian-Stone

    Joined:
    Jun 9, 2012
    Posts:
    222
    You're sorting a set of real-world X,Y,Z map coordinates into a KD tree, and then you examine each pixel in a texture and use the R,G,B color (as an X,Y,Z coordinate?) to locate the nearest X,Y,Z coordinate stored in the KD tree (presumably)... and then you lost me. You need to explain what the problem is in greater detail. How are you generating these 200 textures? What is your application trying to accomplish?
     
    Last edited: Jul 19, 2012
  3. karljj1

    karljj1

    Joined:
    Feb 17, 2011
    Posts:
    440
    Hi,

    For each x,y,z position of the 70,000+ I have an array of 200 values. Each value holds flood data. Each of the 200 represents a single time step over a set period.

    I have a terrain mesh which I am showing this info on using shaders. The shader has 3 textures. Main tex and floodData0, floodData1. I lerp between the 2 flood data textures using a time(float) value. This wayIi can play out the flood data in a smooth way by simply swapping out the textures in the shader from time step 0 texture to 200.

    Now to generate these textures i first create a KD tree to store all the 70,000 points of data. I then create a texture using the terrain mesh textures UV's. I go through each pixel and work out what its real worl position is. I then perform a lookup to get the value for this pixel and this timestep. i can then stick the value into the pixel for my flood shade to use.

    The problem i have it the time it takes to do all this looking up. It should be possible to break it up into multiple tasks for many threads. The pixels have no dependency on each other so i was trying to break split it over several threads by giving them x rows to process each but it actually went much slower. I worked out it was my KD-Tree slowing things down, looks like it is not thread safe? So does unity have a way to lookup data based on x,y,z positions or is there a better solution to a KD-Tree that once generated can be accessed by multiple threads to do its lookups?

    Thanks

    Kar
     
  4. npsf3000

    npsf3000

    Joined:
    Sep 19, 2010
    Posts:
    3,830
    Interesting problem.

    If possible, I'd love to get a sample project so I can see if I can work any magic - this stuff interests me but I haven't had any real world challenges to work on.
     
    Last edited: Jul 19, 2012
  5. Marrrk

    Marrrk

    Joined:
    Mar 21, 2011
    Posts:
    1,032
    Retriving points from the KD-Tree should have no problems when using threads (what should be synchronized/locked? nothing at all!). Could you provide us with your code? 30 hours for some textures sounds very slow, and I can only see two reasons for the slowness:

    1. The KD-Tree access takes too much time, you said you verified this? Maybe there is a better/faster option than KD-Trees, like creating a 3 dimensional array of flood data (each array index represents a x, y or z value) spanning the min/max of your positions. And then accessing this array directly through the indexer.

    2. The way you fill your 2D textures, first no Texture2D should not be threadsafe (I may be wrong here, but most Unity API thingies are not). Maybe you first create the texture and then fill every pixel instead of all pixels.
     
  6. karljj1

    karljj1

    Joined:
    Feb 17, 2011
    Posts:
    440
    Hi Marrrk,

    2 Things seem to slow the whole process. The first stage involves me getting the data for each pixel using the KD-Tree which seems very slow. After examing the data closely i can see that it is basically a large 2d array of points where each point is seperated by the same amount, so it should be possible to do this quicker without a KD-Tree, plus I dont care about the z pos, just x,y. The next stage involves generating the 200+ textures from the collected data, this could probably be split up to allow a thread per texture using a ThreadPool, i have not tested the multithreaded texture creation yet. I will post my editor script tomorrow when I am back in the office.

    So far the actual visualising of the data is looking pretty sweet(I will post a screenshot tomorrow), I would just like to be able to generate the data quicker, ideally in real time...

    A small bug i have noticed is my generated data is slightly offset from the terrain, i think this is an issue with my UV to real world conversion, it will all become clear tomorrow when i post :)

    Thanks

    Karl
     
    Last edited: Jul 19, 2012
  7. Brian-Stone

    Brian-Stone

    Joined:
    Jun 9, 2012
    Posts:
    222
    Thanks for the explanation, the problem is much clearer. I still can't say I fully understand the problem, but I think I have enough to point you in some directions.

    - Make sure the tree is balanced.
    If the KD searches are taking that long, then possibly the tree isn't balanced. If the tree was balanced, then average case for the nearest neighbor search on 70000 points wouldn't be more than 6000 iterations, which is going to be pretty fast even though you're talking about performing 1 million searches per texturemap. It shouldn't take more than a few minutes (I should think). However, if the tree isn't balanced, then the search can easily take hundreds of times longer.

    - Are you performing the tree lookup 200 times per pixel, or just 1 time per pixel?
    If the terrain map doesn't change, then it seems to me that you don't need to perform these lookup's for every flood textuemap. It sounds like you can get away with performing the lookup for each pixel only once and save the (u,v)->point associations in a hash table for faster access. KD tree searches are fast, on average, but searching a hashtable can be O(1) if there are no key conflicts.

    - Do you really need the KD tree?
    If the data points represent terrain, then it seems to me that you can simply take an ad-hoc approach to mapping pixels to data points. Orthographically project and scale the data set onto the terrain texturemap's coordinate system (i.e. 0<=(u,v)<=1). If there is no overlapping data in the point cloud, then I'm not sure what the KD tree is really doing for you.

    Breaking up the work into multiple threads can boost performance, but only if those threads are being scheduled to run on different processors. Obviously if the engine is only using one processor, then you will lose some performance due to the overhead of context switching, thread management, etc. Multi-threading this algorithm doesn't change the fact that it's serial on a single processor, it only allows other processes to interrupt it more easily.
     
    Last edited: Jul 19, 2012
  8. holyjewsus

    holyjewsus

    Joined:
    Mar 7, 2011
    Posts:
    624
    Is this related to CPPN?
     
  9. npsf3000

    npsf3000

    Joined:
    Sep 19, 2010
    Posts:
    3,830
    @Brian Stone

    You're thinking along some similar lines as me, but there's one gigantic WTF!

    It sounds like you can get away with performing the lookup for each pixel only once and save the (u,v)->point associations in a hash table for faster access.

    Err... wouldn't it make a lot more sense to store 'em in an array? :p
     
  10. Brian-Stone

    Brian-Stone

    Joined:
    Jun 9, 2012
    Posts:
    222
    Sure. Scale the (u,v) coordinates to the texture's integer size; use the integer coordinates as the index into the array. Though, ostensibly, this really is no different from a general hash table where the hash keys are the array indices. I think I said that because I've just got hash-tables on the brain. I've been working with them recently.
     
  11. karljj1

    karljj1

    Joined:
    Feb 17, 2011
    Posts:
    440
    Hi,

    I am already storing the timestamps in an array for each value. I only have to do the look up once. This took 8 hours to do a lookup for a 2048 texture. It then took over 15 hours to generate 60 of the 261 textures, i cancelled it then. I will post the code in an hour or 2 so you have a better idea.

    I needed to be able to support different terrain meshes to the actual mesh used to generate the data which is why I use the KD-Tree, so I can just look up the nearest data for that pixel.

    Karl
     
    Last edited: Jul 20, 2012
  12. karljj1

    karljj1

    Joined:
    Feb 17, 2011
    Posts:
    440
    Whats CPPN?
     
  13. npsf3000

    npsf3000

    Joined:
    Sep 19, 2010
    Posts:
    3,830
  14. karljj1

    karljj1

    Joined:
    Feb 17, 2011
    Posts:
    440
    Hi,

    Ok here is the code. I have added extra comments to explain it. The only part you need to look at it the GenerateTextures function but i have posted the whole thing so you can test etc.

    Here is a link to the actual cs file:

    http://ubuntuone.com/3US4N0lzqL7dZxedj4isPb

    The function:

    Code (csharp):
    1.  
    2.     /// <summary>
    3.     /// Generates a range of times steps from start to end.
    4.     /// </summary>
    5.     /// <param name="startTS"></param>
    6.     /// <param name="endTS"></param>
    7.     void GenerateTextures( int startTS, int endTS )
    8.     {
    9.         System.DateTime startTime = System.DateTime.Now;
    10.  
    11.         // This is the data used to generate the textures
    12.         // a 2d array representing the pixels with an array of values for each time step.
    13.         data = new float[texX, texY][];
    14.        
    15.         // Work out how big a pixel is in real world coords.
    16.         float xStep = terrain.renderer.bounds.size.x / texX;
    17.         float zStep = terrain.renderer.bounds.size.z / texY;        
    18.  
    19.         // Now loop through all the pixels and perform a lookup
    20.         double[] point = new double[] { 0, zStep * 0.5f, 0 };
    21.         for( int z = 0; z < texY; z++ )
    22.         {
    23.             // Reset x point
    24.             point[0] = xStep * 0.5f;
    25.  
    26.             for( int x = 0; x < texX; x++ )
    27.             {
    28.                 point[0] += xStep;
    29.  
    30.                 // Get all timestep values for this pixel. This returns a float array. All float arrays are the same size.
    31.                 data[x,z] = floodData.GetScalars( point ); // This is the slow bit.
    32.             }
    33.  
    34.             // Increment z
    35.             point[1] += zStep;
    36.  
    37.             if( EditorUtility.DisplayCancelableProgressBar( "Working", string.Format( "{0} / {1}", z, texY ), ( float )( z / texY ) ) )
    38.             {
    39.                 EditorUtility.ClearProgressBar();
    40.                 return;
    41.             }
    42.         }  
    43.  
    44.         EditorUtility.ClearProgressBar();
    45.  
    46.         // Create textures
    47.         Debug.Log( "1 Total Time Taken: " + ( System.DateTime.Now - startTime ).ToString() );
    48.         startTime = System.DateTime.Now;
    49.  
    50.         // Now generate each texture
    51.         Texture2D tex = new Texture2D( texX, texY, TextureFormat.RGB24, false );
    52.  
    53.         for( int i = startTS; i < lastStep; ++i )
    54.         {
    55.             // Set each pixel. How much faster is SetPixels?
    56.             for( int z = 0; z < texY; z++ )
    57.             {
    58.                 if( EditorUtility.DisplayCancelableProgressBar( "Working - Texture " + i, "", ( float )( i / ( endTS - startTS ) ) ) )
    59.                 {
    60.                     EditorUtility.ClearProgressBar();
    61.                     return;
    62.                 }  
    63.  
    64.                 for( int x = 0; x < texX; x++ )
    65.                 {
    66.                     // Normalise value between 0 and max
    67.                    
    68.                     Color c = new Color( 0, 0, data[x,z][i] / floodData.MaxDepth );
    69.                     tex.SetPixel( x, z, c  );
    70.                 }
    71.  
    72.                 // Save texture out
    73.                 tex.Apply();
    74.                 tex.name = terrain.name + "_" + i;
    75.  
    76.                 // Save texture
    77.                 string file = Application.dataPath + "/" + tex.name + ".png";
    78.                 FileStream fs = new FileStream( file, FileMode.Create );
    79.                 BinaryWriter bw = new BinaryWriter( fs );
    80.                 bw.Write( tex.EncodeToPNG() );
    81.                 bw.Close();
    82.             }
    83.         }
    84.  
    85.         EditorUtility.ClearProgressBar();
    86.  
    87.         Debug.Log( "2 Total Time Taken: " + ( System.DateTime.Now - startTime ).ToString() );
    88.  
    89.         // Cleanup
    90.         DestroyImmediate( tex );        
    91.     }
    92.  
    I tested generation of 1024 textures and it took 02:05:08 for the KD-Tree lookup and 06:58:06 to generate the textures.

    I have access to a machine with 24 CPU cores and potentially one with 128 in the future so multi threading is something to consider.

    The full class
    Code (csharp):
    1.  
    2.  
    3. using UnityEngine;
    4. using UnityEditor;
    5. using System.Collections;
    6. using System.IO;
    7. using System.Threading;
    8. using System.ComponentModel;
    9.  
    10. public class GenerateFloodTextures : EditorWindow
    11. {
    12.     #region Properties
    13.    
    14.     // The terrain to generate the textures for
    15.     GameObject terrain;
    16.  
    17.     // The TUFLOW .2dm file
    18.     string meshFile = @"D:\Data\Projects\Unity\Flood 0.1\Results\USK_V01-A_Q1000_PLUVIAL.2dm";
    19.  
    20.     // The TUFLOW .dat file
    21.     string dataFile = @"D:\Data\Projects\Unity\Flood 0.1\Results\USK_V01-A_Q1000_PLUVIAL_d.dat";
    22.  
    23.     // Our loaded TUFLOW data
    24.     SMS.FloodData floodData;
    25.     float[,][] data; // Per pixel data extracted from floodData
    26.  
    27.     // GUI
    28.     int firstStep = 0, lastStep = 1;
    29.     int texX = 1024, texY = 1024;
    30.  
    31.     float maxDepth;
    32.        
    33.     #endregion
    34.  
    35.     /// <summary>
    36.     /// Create the editor window
    37.     /// </summary>
    38.     [MenuItem( "Flood/Generate Textures", false )]
    39.     static void OpenWindow()
    40.     {
    41.         GenerateFloodTextures window = EditorWindow.GetWindow<GenerateFloodTextures>( true, "Generate Flood Textures" );
    42.         window.maxSize = new Vector2( 500, 800 );
    43.     }
    44.  
    45.     /// <summary>
    46.     /// Draws the GUI
    47.     /// </summary>
    48.     void OnGUI()
    49.     {
    50.         int labelWidth = 150;
    51.  
    52.         EditorGUILayout.BeginVertical( GUI.skin.box );
    53.  
    54.         // Title
    55.         GUILayout.Label( "Input", EditorStyles.boldLabel );
    56.  
    57.         //
    58.         // Terrain
    59.         //
    60.         GUILayout.Space( 10 );
    61.         EditorGUILayout.BeginHorizontal();
    62.         GUILayout.Label( "Terrain: ", GUILayout.MaxWidth( labelWidth ) );
    63.         terrain = EditorGUILayout.ObjectField( terrain, typeof( GameObject ), GUILayout.MaxWidth( 150 ) ) as GameObject;        
    64.         EditorGUILayout.EndHorizontal();
    65.         if( terrain != null )
    66.         {
    67.             EditorGUILayout.BeginHorizontal();
    68.             GUILayout.Label( "Bounds: ", GUILayout.MaxWidth( labelWidth ) );
    69.             GUILayout.Label( terrain.renderer.bounds.size.ToString() );
    70.             EditorGUILayout.EndHorizontal();
    71.         }        
    72.         GUILayout.Space( 10 );
    73.  
    74.         //
    75.         // 2dm file        
    76.         //
    77.         EditorGUILayout.BeginHorizontal();
    78.         GUILayout.Label( "Mesh File(.2dm): ", GUILayout.MaxWidth( labelWidth ) );
    79.         meshFile = GUILayout.TextField( meshFile, GUILayout.MaxWidth( 200 ) );
    80.         if( GUILayout.Button( "...", GUILayout.MaxWidth( 30 ) ) )
    81.         {
    82.             meshFile = EditorUtility.OpenFilePanel( "Select Mesh File", Application.absoluteUrl, "2dm" );
    83.         }
    84.         EditorGUILayout.EndHorizontal();
    85.  
    86.         //
    87.         // dat file
    88.         //
    89.         EditorGUILayout.BeginHorizontal();
    90.         GUILayout.Label( "Data File(.dat): ", GUILayout.MaxWidth( labelWidth ) );
    91.         dataFile = GUILayout.TextField( dataFile, GUILayout.MaxWidth( 200 ) );
    92.         if( GUILayout.Button( "...", GUILayout.MaxWidth( 30 ) ) )
    93.         {
    94.             dataFile = EditorUtility.OpenFilePanel( "Select Data File", Application.absoluteUrl, "dat" );
    95.         }
    96.         EditorGUILayout.EndHorizontal();
    97.  
    98.         //
    99.         // Load data?        
    100.         //
    101.         if( ValidateFiles() )
    102.         {
    103.             GUILayout.Space( 10 );
    104.             if( GUILayout.Button( "Load TUFLOW Data" ) )
    105.             {                                                                      
    106.                 floodData = new SMS.FloodData();    
    107.                 floodData.LoadData( meshFile, dataFile );                
    108.                 lastStep = floodData.TimeSteps - 1;
    109.                                
    110.             }
    111.         }
    112.         EditorGUILayout.EndVertical();
    113.  
    114.         //
    115.         // TUFLOW data
    116.         //
    117.         if( floodData != null )
    118.         {
    119.             EditorGUILayout.BeginVertical( GUI.skin.box );
    120.  
    121.             // Label
    122.             GUILayout.Label( "TUFLOW Data", EditorStyles.boldLabel );
    123.  
    124.             // Time steps
    125.             EditorGUILayout.BeginHorizontal();
    126.             GUILayout.Label( "Time Steps:", GUILayout.MaxWidth( labelWidth ) );
    127.             GUILayout.Label( floodData.TimeSteps.ToString() );
    128.             EditorGUILayout.EndHorizontal();
    129.  
    130.             // Max depth            
    131.             EditorGUILayout.BeginHorizontal();
    132.             GUILayout.Label( "Max Depth:", GUILayout.MaxWidth( labelWidth ) );
    133.             GUILayout.Label( floodData.MaxDepth.ToString() );
    134.             EditorGUILayout.EndHorizontal();
    135.  
    136.             // Corner
    137.             EditorGUILayout.BeginHorizontal();
    138.             GUILayout.Label( "Corner:", GUILayout.MaxWidth( labelWidth ) );
    139.             GUILayout.Label( string.Format( "{0},{1}", floodData.Corner[0], floodData.Corner[1] ) );
    140.             EditorGUILayout.EndHorizontal();
    141.  
    142.             //
    143.             // Generate Time Steps
    144.             //
    145.             EditorGUILayout.BeginHorizontal();
    146.             GUILayout.Label( "Generate Range: " );
    147.             firstStep = Mathf.Clamp( EditorGUILayout.IntSlider( firstStep, 0, floodData.TimeSteps ), 0, lastStep - 1 );
    148.             lastStep = Mathf.Clamp( EditorGUILayout.IntSlider( lastStep, 0, floodData.TimeSteps ), firstStep + 1, floodData.TimeSteps );
    149.             EditorGUILayout.EndHorizontal();
    150.             EditorGUILayout.BeginHorizontal();
    151.             GUILayout.Label( "Texture Size: " );
    152.             texX = Mathf.Clamp( EditorGUILayout.IntField( texX ), 32, 4096 );
    153.             GUILayout.Label( "x" );
    154.             texY = Mathf.Clamp( EditorGUILayout.IntField( texY ), 32, 4096 );
    155.             EditorGUILayout.EndHorizontal();
    156.             EditorGUILayout.BeginHorizontal();
    157.             if( GUILayout.Button( "Generate" ) )
    158.             {
    159.                 GenerateTextures( firstStep, lastStep );
    160.             }
    161.             EditorGUILayout.EndHorizontal();
    162.             EditorGUILayout.EndVertical();
    163.         }      
    164.     }
    165.  
    166.     /// <summary>
    167.     /// Returns true if files are assigned and exist.
    168.     /// </summary>
    169.     /// <returns></returns>
    170.     bool ValidateFiles()
    171.     {
    172.         if( File.Exists( meshFile )  File.Exists( dataFile ) )
    173.         {
    174.             return true;
    175.         }
    176.         return false;
    177.     }
    178.  
    179.     /// <summary>
    180.     /// Generates a range of times steps from start to end.
    181.     /// </summary>
    182.     /// <param name="startTS"></param>
    183.     /// <param name="endTS"></param>
    184.     void GenerateTextures( int startTS, int endTS )
    185.     {
    186.         System.DateTime startTime = System.DateTime.Now;
    187.  
    188.         // This is the data used to generate the textures
    189.         // a 2d array representing the pixels with an array of values for each time step.
    190.         data = new float[texX, texY][];
    191.        
    192.         // Work out how big a pixel is in real world coords.
    193.         float xStep = terrain.renderer.bounds.size.x / texX;
    194.         float zStep = terrain.renderer.bounds.size.z / texY;        
    195.  
    196.         // Now loop through all the pixels and perform a lookup
    197.         double[] point = new double[] { 0, zStep * 0.5f, 0 };
    198.         for( int z = 0; z < texY; z++ )
    199.         {
    200.             // Reset x point
    201.             point[0] = xStep * 0.5f;
    202.  
    203.             for( int x = 0; x < texX; x++ )
    204.             {
    205.                 point[0] += xStep;
    206.  
    207.                 // Get all timestep values for this pixel. This returns a float array. All float arrays are the same size.
    208.                 data[x,z] = floodData.GetScalars( point ); // This is the slow bit.
    209.             }
    210.  
    211.             // Increment z
    212.             point[1] += zStep;
    213.  
    214.             if( EditorUtility.DisplayCancelableProgressBar( "Working", string.Format( "{0} / {1}", z, texY ), ( float )( z / texY ) ) )
    215.             {
    216.                 EditorUtility.ClearProgressBar();
    217.                 return;
    218.             }
    219.         }  
    220.  
    221.         EditorUtility.ClearProgressBar();
    222.  
    223.         // Create textures
    224.         Debug.Log( "1 Total Time Taken: " + ( System.DateTime.Now - startTime ).ToString() );
    225.         startTime = System.DateTime.Now;
    226.  
    227.         // Now generate each texture - this should be possible to multi thread.
    228.         Texture2D tex = new Texture2D( texX, texY, TextureFormat.RGB24, false );
    229.  
    230.         for( int i = startTS; i < lastStep; ++i )
    231.         {
    232.             // Set each pixel. How much faster is SetPixels?
    233.             for( int z = 0; z < texY; z++ )
    234.             {
    235.                 if( EditorUtility.DisplayCancelableProgressBar( "Working - Texture " + i, "", ( float )( i / ( endTS - startTS ) ) ) )
    236.                 {
    237.                     EditorUtility.ClearProgressBar();
    238.                     return;
    239.                 }  
    240.  
    241.                 for( int x = 0; x < texX; x++ )
    242.                 {
    243.                     // Normalise value between 0 and max
    244.                    
    245.                     Color c = new Color( 0, 0, data[x,z][i] / floodData.MaxDepth );
    246.                     tex.SetPixel( x, z, c  );
    247.                 }
    248.  
    249.                 // Save texture out
    250.                 tex.Apply();
    251.                 tex.name = terrain.name + "_" + i;
    252.  
    253.                 // Save texture
    254.                 string file = Application.dataPath + "/" + tex.name + ".png";
    255.                 FileStream fs = new FileStream( file, FileMode.Create );
    256.                 BinaryWriter bw = new BinaryWriter( fs );
    257.                 bw.Write( tex.EncodeToPNG() );
    258.                 bw.Close();
    259.             }
    260.         }
    261.  
    262.         EditorUtility.ClearProgressBar();
    263.  
    264.         Debug.Log( "2 Total Time Taken: " + ( System.DateTime.Now - startTime ).ToString() );
    265.  
    266.         // Cleanup
    267.         DestroyImmediate( tex );        
    268.     }
    269. }
    270.  
    A screenshot of what the end result is:

     
    Last edited: Jul 20, 2012
  15. superpig

    superpig

    Drink more water! Unity Technologies

    Joined:
    Jan 16, 2011
    Posts:
    4,649
    Unity's objects do not permit access from non-main threads - they may or may not be threadsafe but Unity errs on the side of safety and shoots down all accesses regardless. There are a couple of functions that can be called from non-main threads, like Debug.Log, but that's about it.

    However, this should not stop you: You can still use multiple threads, provided you don't touch Texture2D directly on other threads. So you can create and fill a Color/Color32 buffer across as many threads as you like, and then use Texture2D.SetPixels() from the main thread when they're done. I use this for a very similar task to you (generating lightmaps for LOD meshes based on the highest detail mesh) and it makes things much, much faster.

    So don't use SetPixel on a pixel-by-pixel basis - buffer everything and use SetPixels.

    Also, be aware that Display[Cancelable]ProgressBar is insanely slow (particularly on Windows) - it looks like your usage is OK but be careful about using it in tight loops in general.
     
  16. npsf3000

    npsf3000

    Joined:
    Sep 19, 2010
    Posts:
    3,830
    Okay, just to give you a bit of a heads up... the operation you are trying to do should take seconds, minutes at the worst case. So you can scale up all you want, but lets first look to making the code efficient?

    I'm still missing vital parts of the code - I need raw data and to know how you 'query' it to figure out which point belongs to which pixel. I GTG right now, will take a deeper look later.
     
  17. karljj1

    karljj1

    Joined:
    Feb 17, 2011
    Posts:
    440
    Hi,

    Afraid I can't share the flood data and terrain mesh, its not mine to share and also very large.

    The KD-Tree is an open source one from here:

    http://home.wlu.edu/~levys/software/kd/

    I don't think it is balanced?

    This loads my data and puts it into the tree:

    Code (csharp):
    1.  
    2.         /// <summary>
    3.         /// Load the generated flood data. generates a kd-tree for fast lookup.
    4.         /// </summary>
    5.         /// <exception cref="Exception"/>
    6.         /// <param name="meshFile">.2dm</param>
    7.         /// <param name="dataFile">.dat</param>
    8.         public void LoadData( string meshFile, string dataFile )
    9.         {
    10.             // Quick error check
    11.             if( File.Exists( meshFile ) == false )
    12.             {
    13.                 throw new Exception( "File not Found: " + meshFile );
    14.             }
    15.             if( File.Exists( dataFile ) == false )
    16.             {
    17.                 throw new Exception( "File not Found: " + dataFile );
    18.             }
    19.  
    20.             // Node Positions
    21.             Stream stream1 = new FileStream( meshFile, FileMode.Open, FileAccess.Read );
    22.             SMS.Mesh2D.File f1 = new SMS.Mesh2D.File();
    23.             f1.Read( stream1 );
    24.             List<SMS.Mesh2D.Cards.Card> nodes = f1.Cards[SMS.Mesh2D.Cards.CardType.ND];
    25.             MESH2D m = f1.Cards[SMS.Mesh2D.Cards.CardType.MESH2D][0] as MESH2D;
    26.             Corner = m.Corner;
    27.  
    28.             // Timestamps
    29.             Stream stream2 = new FileStream( dataFile, FileMode.Open, FileAccess.Read );
    30.             SMS.DataSet.File f2 = new SMS.DataSet.File();
    31.             f2.DeSerialise( stream2 );
    32.             List<SMS.DataSet.Cards.Card> timestamps = f2.Cards[SMS.DataSet.Cards.CardType.TS];
    33.  
    34.             Tree = new KDTree( 3 );
    35.  
    36.             // Set num ts
    37.             maxTS = timestamps.Count;
    38.  
    39.             maxDepth = 0;
    40.  
    41.             // Itterate through each node and attach the TS data.
    42.             for( int i = 0; i < nodes.Count; ++i )
    43.             {
    44.                 ND n = nodes[i] as ND;
    45.  
    46.                 // Extract all the timestamp values for this node                
    47.                 float[] tsData = new float[timestamps.Count];
    48.                 for( int j = 0; j < timestamps.Count; ++j )
    49.                 {
    50.                     TS t = timestamps[j] as TS;
    51.                     tsData[j] = t.ScalarValues[i];
    52.                    
    53.                     // Check max depth
    54.                     if( t.MaxValue > maxDepth ) maxDepth = t.MaxValue;
    55.                 }
    56.  
    57.                 // Insert into the kd-tree
    58.                 Tree.insert( new double[] { n.Pos[0] - m.Corner[0], n.Pos[1] - m.Corner[1], n.Pos[2] }, tsData );
    59.             }
    60.         }
    61.  
    This does the lookup using the tree

    Code (csharp):
    1.  
    2.         /// <summary>
    3.         /// Returns all time steps for a single point.
    4.         /// Returns null if none found.
    5.         /// </summary>
    6.         /// <param name="pos"></param>
    7.         /// <returns></returns>
    8.         public float[] GetScalars( double[] pos )
    9.         {
    10.             object[] o = Tree.nearest( pos, 1 );
    11.             if( o != null )
    12.             {
    13.                 return ( float[] )o[0];
    14.             }
    15.             return null;
    16.         }
    17.  
    I have realised i dont actually need the height position as the flood data will not be on top of each other so i can make it a 2d KD tree instead of 3d to help speed up searches.

    K
     
    Last edited: Jul 20, 2012
  18. npsf3000

    npsf3000

    Joined:
    Sep 19, 2010
    Posts:
    3,830
    Based on the data provided, I've created a 'proof of concept' - I think it covers most of the basics for you.

    After looking at the generated images, I realized that I've managed to create a Voronoi diagram - which was a nice suprise :)
     
  19. karljj1

    karljj1

    Joined:
    Feb 17, 2011
    Posts:
    440
    Thanks npsf3000,

    That looks very interesting. I will try to go through it next week and let you know how things go.

    Regards

    Karl
     
  20. npsf3000

    npsf3000

    Joined:
    Sep 19, 2010
    Posts:
    3,830
  21. karljj1

    karljj1

    Joined:
    Feb 17, 2011
    Posts:
    440
    Thanks that looks great :)
     
  22. npsf3000

    npsf3000

    Joined:
    Sep 19, 2010
    Posts:
    3,830
  23. ImogenPoot

    ImogenPoot

    Joined:
    Jul 2, 2012
    Posts:
    214
    This sounds like you are doing something utterly wrong. This is really a simple computation and should not take longer than say a few hundred seconds on CPU, with one core... On GPU this is something that could well be done in say a few seconds...
     
  24. npsf3000

    npsf3000

    Joined:
    Sep 19, 2010
    Posts:
    3,830
    On my test scenario, I've gotten the time down to about 4s on a dual core.
     
  25. karljj1

    karljj1

    Joined:
    Feb 17, 2011
    Posts:
    440
    Thanks i will try it out tomorrow.

    Having looked closer at the data I can see it is a grid with equal separation (ESRII ASCII), so it should be possible to use a simple 2d array. I would also like to do interpolation of the points to generate smoother data, I will put something together tomorrow. I also have an other piece of code unrelated to this that I could do with some help on if your interested :)
    Its a Page able LOD system that is part of a project I am presenting at UNITE this year :)

    I will send it to you tomorrow.

    Karl
     
  26. npsf3000

    npsf3000

    Joined:
    Sep 19, 2010
    Posts:
    3,830
    Had a look at the wiki article - that'll be a piece of cake to convert into a use-able data structure.

    Have fun with that :p

    I'd consider trying some simple image filters - blur, smooth that kind of stuff. Alternatively it'd be fairly trivial job to get SimpleSpacialCollection.GetNearest to return n items - which would give you the nearest sensors to work with.

    Sounds interesting :)


    ----

    Edit: Just realized there's a potential error with my GetNearest code that may return the wrong object in edge cases. I'll think about it some more and get a fix out soonish.
     
    Last edited: Jul 22, 2012
  27. karljj1

    karljj1

    Joined:
    Feb 17, 2011
    Posts:
    440
    Hi,

    So I have re-written without the KD-Tree and a simple grid in place. I am using the System.Drawing.Bitmap to do multi threaded saving however I have noticed some loss of data due to my conversion to int. I have got around it for the moment by reducing the max flood value to 10 instead of 17(the correct value). I was thinking of doing some form of outlier algorithm to remove the erroneous data(17 is wrong) but that's for one day in the future....

    Here is my Grid class:

    Code (csharp):
    1.  
    2. using System;
    3. using System.Collections.Generic;
    4. using System.Linq;
    5. using System.Text;
    6. using System.Threading;
    7.  
    8. namespace SMS
    9. {
    10.     /// <summary>
    11.     /// Provides fast lookup of flood scalar values based on position.
    12.     /// </summary>
    13.     public class DataGrid
    14.     {
    15.         #region Properties
    16.  
    17.         /// <summary>
    18.         /// The stored data
    19.         /// </summary>
    20.         public float[,][] Grid
    21.         {
    22.             get;
    23.             set;
    24.         }
    25.  
    26.         /// <summary>
    27.         /// Number of columns in the grid
    28.         /// </summary>
    29.         public int Cols
    30.         {
    31.             get;
    32.             set;
    33.         }
    34.  
    35.         /// <summary>
    36.         /// Number of rows in the grid
    37.         /// </summary>
    38.         public int Rows
    39.         {
    40.             get;
    41.             set;
    42.         }
    43.  
    44.         /// <summary>
    45.         /// Dont interpolate points within the threshold. Helps reduce memory footprint.
    46.         /// </summary>
    47.         public float InterpolationThreshold
    48.         {
    49.             get;
    50.             set;
    51.         }
    52.  
    53.         /// <summary>
    54.         /// Seperation between points.
    55.         /// </summary>
    56.         public float Seperation
    57.         {
    58.             get;
    59.             set;
    60.         }
    61.  
    62.         #endregion
    63.  
    64.         public DataGrid( int rows, int cols, float seperation )
    65.         {
    66.             Cols = rows + 1; // x,y swapped
    67.             Rows = cols + 1;
    68.             Grid = new float[Cols, Rows][];
    69.             Seperation = seperation;
    70.             InterpolationThreshold = 0.01f;
    71.         }
    72.  
    73.         /// <summary>
    74.         /// Adds a data point
    75.         /// </summary>
    76.         /// <param name="x"></param>
    77.         /// <param name="y"></param>
    78.         /// <param name="data"></param>
    79.         public void Add( float x, float y, float[] data )
    80.         {
    81.             int col = ( int )( x / Seperation );
    82.             int row = ( int )( y / Seperation );
    83.             Grid[col, row] = data;
    84.         }
    85.  
    86.         /// <summary>
    87.         /// Returns the nearest scalars or null if no data.
    88.         /// </summary>
    89.         /// <param name="x"></param>
    90.         /// <param name="y"></param>
    91.         /// <returns></returns>
    92.         public float[] GetNearestScalars( float x, float y )
    93.         {
    94.             // Round to nearest int
    95.             int col = ( int )Math.Round( x / Seperation, 0 );
    96.             int row = ( int )Math.Round( y / Seperation, 0 );            
    97.  
    98.             if( IsWithinGrid( col, row ) )
    99.             {
    100.                 return Grid[col, row];
    101.             }
    102.  
    103.             return null;
    104.         }
    105.        
    106.         /// <summary>
    107.         /// Returns new scalar values interpolated with neighbour values or null if no data.
    108.         /// </summary>
    109.         /// <param name="x"></param>
    110.         /// <param name="y"></param>
    111.         /// <returns></returns>
    112.         public float[] GetNearestScalarsInterpolated( float x, float y, int firstTS, int lastTS )
    113.         {
    114.             float colI = x / Seperation;
    115.             float rowI = y / Seperation;
    116.             int col = ( int )colI;
    117.             int row = ( int )rowI;            
    118.  
    119.             if( IsWithinGrid( col, row ) )
    120.             {
    121.                 rowI -= row;
    122.                 colI -= col;
    123.  
    124.                 // Do we need to actually do interpolation?
    125.                 // We can reduce memory footprint by increasing the threshold.
    126.                 if( ( rowI < InterpolationThreshold || 1.0f - rowI < InterpolationThreshold )
    127.                     ( colI < InterpolationThreshold || 1.0f - colI < InterpolationThreshold ) )
    128.                 {
    129.                     // Round to nearest int
    130.                     col = ( int )Math.Round( x / Seperation, 0 );
    131.                     row = ( int )Math.Round( y / Seperation, 0 );
    132.                     return Grid[col, row];
    133.                 }
    134.  
    135.                 // Get the 4 scalars for interpolation
    136.                 float[] bl = Grid[col, row],
    137.                         br = Grid[col + 1, row],
    138.                         tl = Grid[col, row + 1],
    139.                         tr = Grid[col + 1, row + 1];
    140.  
    141.                 // Create the new scalars, all have the same length.
    142.                 int numVals = lastTS - firstTS;
    143.                 float[] newScalars = new float[lastTS - firstTS];
    144.  
    145.                 // For each time step, interpolate
    146.                 int index = firstTS;
    147.  
    148.                 for( int i = 0; i < numVals; ++i, index++ )
    149.                 {
    150.                     float blVal = ( bl == null ) ? 0 : bl[index];
    151.                     float brVal = ( br == null ) ? 0 : br[index];
    152.                     float tlVal = ( tl == null ) ? 0 : tl[index];
    153.                     float trVal = ( tr == null ) ? 0 : tr[index];
    154.  
    155.                     // Lerp bottom and top rows, then lerp the results together.                    
    156.                     newScalars[i] = Lerp( Lerp( blVal, brVal, colI ), Lerp( tlVal, trVal, colI ), rowI );
    157.                 }
    158.  
    159.                 return newScalars;            
    160.             }
    161.  
    162.             return null;
    163.         }
    164.        
    165.  
    166.         /// <summary>
    167.         /// Returns an interpolated scalar value for a single timestep. Returns 0 if none found.
    168.         /// </summary>
    169.         /// <param name="x"></param>
    170.         /// <param name="y"></param>
    171.         /// <param name="timeStep"></param>        
    172.         /// <returns></returns>
    173.         public float GetNearestScalarInterpolated( float x, float y, int timeStep )
    174.         {
    175.             float colI = x / Seperation;
    176.             float rowI = y / Seperation;
    177.             int col = ( int )colI;
    178.             int row = ( int )rowI;
    179.  
    180.             if( IsWithinGrid( col, row ) )
    181.             {
    182.                 rowI -= row;
    183.                 colI -= col;
    184.  
    185.                 // Get the 4 scalars for interpolation
    186.                 float[] bl = Grid[col, row],
    187.                         br = Grid[col + 1, row],
    188.                         tl = Grid[col, row + 1],
    189.                         tr = Grid[col + 1, row + 1];
    190.  
    191.                 return Lerp( Lerp( bl[timeStep], br[timeStep], colI ), Lerp( tl[timeStep], tr[timeStep], colI ), rowI );
    192.             }
    193.  
    194.             return 0;
    195.         }
    196.  
    197.         /// <summary>
    198.         /// Tests if the point is within the grid.
    199.         /// </summary>
    200.         /// <param name="x"></param>
    201.         /// <param name="y"></param>
    202.         /// <returns></returns>
    203.         public bool IsWithinGrid( float x, float y )
    204.         {
    205.             int col = ( int )( x / Seperation );
    206.             int row = ( int )( y / Seperation );            
    207.             return IsWithinGrid( col, row );            
    208.         }
    209.  
    210.         /// <summary>
    211.         /// Test if the array indexes are within the Grid.
    212.         /// </summary>
    213.         /// <param name="x"></param>
    214.         /// <param name="y"></param>
    215.         /// <returns></returns>
    216.         public bool IsWithinGrid( int x, int y )
    217.         {
    218.             if( y > 0  y < Rows  x > 0  x < Cols ) return true;
    219.             return false;
    220.         }
    221.  
    222.         /// <summary>
    223.         /// Performs linear interpolation.
    224.         /// </summary>
    225.         /// <param name="valA"></param>
    226.         /// <param name="valB"></param>
    227.         /// <param name="amount"></param>
    228.         /// <returns></returns>
    229.         private float Lerp( float valA, float valB, float amount )
    230.         {
    231.             return valA + ( valB - valA ) * amount;
    232.         }
    233.     }
    234. }
    235.  
    236.  
    Using it:

    Code (csharp):
    1.  
    2. static void Main( string[] args )
    3.         {
    4.  
    5.             SMS.FloodData floodData = new SMS.FloodData();
    6.             floodData.LoadData( "D:/Data/Projects/Unity/Flood 0.2/Results/USK_V01-A_Q1000_PLUVIAL.2dm", "D:/Data/Projects/Unity/Flood 0.2/Results/USK_V01-A_Q1000_PLUVIAL_d.dat" );
    7.  
    8.             System.Diagnostics.Stopwatch generateDataTimer = System.Diagnostics.Stopwatch.StartNew();
    9.  
    10.             int texX = 1024, texY = 1024;
    11.             float[,][] data = new float[texX, texY][];
    12.  
    13.             float xStep = 6450.0f / texX;
    14.             float zStep = 4450.0f / texY;
    15.  
    16.             float xPos = 0, yPos = zStep * 0.5f;
    17.             for( int z = 0; z < texY; z++ )
    18.             {
    19.                 // Reset x point
    20.                 xPos = xStep * 0.5f;
    21.  
    22.                 for( int x = 0; x < texX; x++ )
    23.                 {
    24.                     xPos += xStep;
    25.  
    26.                     // Get all timestep values for this pixel                    
    27.                     data[x, z] = floodData.Data.GetNearestScalarsInterpolated( xPos, yPos, 0, 215 );
    28.                     //data[x, z] = floodData.Data.GetNearestScalars( xPos, yPos );
    29.                 }
    30.  
    31.                 // Increment z
    32.                 yPos += zStep;
    33.             }
    34.  
    35.             generateDataTimer.Stop();
    36.             Console.Write( string.Format( "Generated Data in {0}ms\n", generateDataTimer.ElapsedMilliseconds ) );
    37.  
    38.             // Generate Textures
    39.             System.Diagnostics.Stopwatch texGenTimer = System.Diagnostics.Stopwatch.StartNew();
    40.             System.Threading.Tasks.Parallel.For( 0, 100, i =>
    41.                 {
    42.                     System.Drawing.Bitmap img = new System.Drawing.Bitmap( texX, texY );                    
    43.  
    44.                     for( int y = 0; y < texY; ++y )
    45.                     {
    46.                         for( int x = 0; x < texX; ++x )
    47.                         {                                                                                    
    48.                             float scalar = ( data[x, y] != null ) ? data[x, y][i] : 0;                            
    49.                             img.SetPixel( x, texY - 1 - y, System.Drawing.Color.FromArgb( 0, 0, ( int )Math.Min( 255.0f, ( ( scalar / 10.0f ) * 255.0f ) ) ) );
    50.                         }
    51.                     }
    52.  
    53.                     // Save
    54.                     img.Save( string.Format( "Textures/FloodData_{0}.bmp", i ) );
    55.                 } );
    56.  
    57.  
    58.             texGenTimer.Stop();
    59.             Console.Write( string.Format( "Generated Textures in {0}ms\n", texGenTimer.ElapsedMilliseconds ) );
    60.         }
    61.  
    The interpolation feature works really well however it does cause a large memory footprint from all the extra data. I introduced the threshold to reduce this but its not perfect however you can reduce the risk by generating smaller batches at a time instead of all the data in one shot.


    a(left) - with interpolation
    b(right) - without interpolation

    It takes about a minute to generate all the data now :)

    Thanks for the help.
     
    Last edited: Jul 23, 2012
  28. npsf3000

    npsf3000

    Joined:
    Sep 19, 2010
    Posts:
    3,830
    My questions/notes are:

    1) Why does interpolation take more memory?

    You have a set of data of 'points'. You then ask for some very specific data [what is the value d for point x , y for each time 0..t] - and store that in an array as a cache to speed up image generation. Interpolation should only effect how much computation is done to generate that cache - not how much data is used. While you may technically use an extra few KB in the computation - this should be reused/garbage collected - and shouldn't be notable.

    2) You're 'Interpolation method' as far as I can see, ignores diagonals :p.

    3) Accuracy loss:

    I worked off of the following logic in my example: You should know the max and min numbers - e.g. your data is in the range of 0-10. Then you should force all your data to be a float [or double] in the range 0-1 and work off that for later calculations. The reason I do this is because:

    a) It's very easy to normalize data.
    b) Now you can do all your math without worrying about conversion issues.
    c) It makes your code cleaner, more flexible etc.

    For example:

    Code (csharp):
    1.  
    2. //Your Code:
    3. img.SetPixel( x, texY - 1 - y, System.Drawing.Color.FromArgb( 0, 0, ( int )Math.Min( 255.0f, ( ( scalar / 10.0f ) * 255.0f ) ) ) );
    4. //WTF is '( int )Math.Min( 255.0f, ( ( scalar / 10.0f ) * 255.0f ) ) '?
    5.  
    6. //My Code:
    7. bmp.SetPixel(x, y, Color.FromArgb((0, 0, (int)(255 * sensor.data[i])));
    8. //Much cleaner.
    9.  
    10. /*Furthermore, my method doesn't care about the nature of the incoming data - the original could be 0 to 42 or -10 to -4, have had the first 10 numbers culled or the last 10 numbers culled etc.  As long as the data's normalized it will print a pretty picture. */
    11.  
    TL;DR - Treat your steps like a pipeline - and normalize early on.

    Take a look at my GenerateBMPv2 - it should save lots of time and be fairly trivial to rewrite to your own specs.
     
    Last edited: Jul 24, 2012
  29. karljj1

    karljj1

    Joined:
    Feb 17, 2011
    Posts:
    440
    When a pixel does not lay on an exact value I generate a new interpolated value for it, I do this for each time step. So in my current case I return 216 new floats for that pixel. If I had to interpolate every value it would take 864MB ( 1024 * 1024 * 4 * 216 ). It seems that most of my data is not on an exact point so I had to generate a lot of new values.

    oops :)

    My values are actually between 0 and 17.242.
    The problem is that the majority of the values are very small. E.G 0.001.
    These values represent water levels in metres, 17 meters is incorrect, it seems to be an erroneous value.
    However since most data is very small it gets lost in the conversion.

    E.G

    0.001 / 17.242 * 255 = 0.0147

    By reducing the max value to 10 instead of 17 I have slightly more chance of keeping some of those values however I will now get normalised values over 1 for the values greater than 10. When they get converted they will be greater than 255 and Bitmap throws and exception if you put a value over 255, hence the Math.Min.

    When I used the Texture2D in unity I did not lose data as it takes straight floats, so is Unity doing some conversion in the background to fit it into the 255 range?

    Karl
     
  30. superpig

    superpig

    Drink more water! Unity Technologies

    Joined:
    Jan 16, 2011
    Posts:
    4,649
    Yes (assuming you've not managed to use some weird texture format).

    If you need more precision than that, you have to work in fixed-point and encode numbers across multiple channels.
     
  31. npsf3000

    npsf3000

    Joined:
    Sep 19, 2010
    Posts:
    3,830
    Yes, you may 'gather' 216 floats for a single pixel - but you're only storing 1 float - so this shouldn't affect memory.

    This is how my method work, with and without [hypothetical] interpolation.

    Code (csharp):
    1.  
    2. //Rough estimates 70K points, 1024x1024, 200 layers
    3.  
    4. //Normal -
    5. Points Array [56MB] -> Get Point [4B] ->  Cache [800MB]
    6.  
    7. //With Interpolation-
    8. Points Array [56MB] -> Get 216 Interpolation Points [864B] -> Interpolate [4B] ->  Cache [800MB]
    9.  
    Yes, you need a 800MB cache but that's nothing to do with interpolation. All the interpolation adds is 864B per emthod call - data that's either garbage collected [messy] or reused. The reason we have the cache is simply because it's faster to store 800MB than it is to regenerate this data on the fly 200 times when generating your images. You could of course rearrange the algorithm to have no cache, but to write to 200 images once for every pixel - but this makes like more complicated [particularly with threading].

    You're slightly confused.

    An pixel is consists of 4 bytes. One byte for red. One byte for green. One byte for blue. And, if applicable, one byte for alpha. And even this is not always the case - some file formats [e.g. the version in my GenerateV2] only store '255' values all together! Some screens only output 6 bit color etc.

    What we want to do, is normalize the data early on so that all the math beyond that point can be assured that it only has to deal with the values 0..1 - making life easy. Here's an example:


    Code (csharp):
    1.  
    2. static Random rnd = new Random();
    3.         static void Main(string[] args)
    4.         {
    5.             //Get Raw Data
    6.             var rawData = GenerateRawData();
    7.  
    8.             //Normalize Data
    9.             var normalizedData = new double[1024, 1024][];
    10.             for (int x = 0; x < 1024; x++)
    11.                 for (int y = 0; y < 1024; y++)
    12.                 {
    13.                     normalizedData[x, y] = new double[200];
    14.                     for (int t = 0; t < 200; t++)
    15.                         normalizedData[x, y][t] = Math.Min(rawData[x, y][t] / 10d, 1);
    16.                 }
    17.  
    18.             //Now query the points and generate your 'Cached Data'
    19.             //Now produce the images
    20.             //...
    21.  
    22.             //Now go on with your calcs - knowing that no matters what happens to the source data
    23.             //your math will still work.  0..1 is all we care about from here onwards!
    24.             //If you need to make any changes - there's one spot and only one spot!
    25.  
    26.             //  Complaint:  "However since most data is very small it gets lost in the conversion."
    27.             //  Answer - not as far as normailisation is concerned you don't.
    28.             //  The float type can store around 7 digits.
    29.             //  The double type can store around 15-16 digits.
    30.             //  And as you noted, the final output is only 0..255 - 3 digits.
    31.             //  So, normalize damnit!
    32.  
    33.             var d = 0.001 * 0.001 * 0.001;
    34.             Console.WriteLine(d.ToString("N9"));//prints 0.000000001 as expected
    35.  
    36.             Console.ReadLine();
    37.  
    38.         }
    39.  
    40.         private static float[,][] GenerateRawData()
    41.         {
    42.             var rawData = new float[1024, 1024][];
    43.             for (int x = 0; x < 1024; x++)
    44.                 for (int y = 0; y < 1024; y++)
    45.                 {
    46.                     rawData[x, y] = new float[200];
    47.                     for (int t = 0; t < 200; t++)
    48.                         rawData[x, y][t] = (float)rnd.NextDouble() * 17.242f;
    49.                 }
    50.             return rawData;
    51.         }
    52.  
    You bring up the fact that you're setting the max to '10' - not allowing '17'. This is great - but this should be done in the normalization step - not while your deciding what color to output!
     
  32. karljj1

    karljj1

    Joined:
    Feb 17, 2011
    Posts:
    440
    Hi,

    Before I introduced interpolation I was returning the nearest set of values for each pixel. So the memory started at 56MB and stayed at that as no new data needed to be created, I was just passing pointers(references?) to the existing arrays(I assume...). This is how I understand c# to work, like C++ pointers? When I introduce interpolation I now create new arrays for each pixel and so add an extra 800MB which sometimes causes Unity to crash(Heap error). I am also limited at texture size , what if I waned a 4096 texture(13.5GB), I would have to generate smaller batches...

    I understand your argument about doing normalisation earlier but this is really the only point where I need normalised data. It is something I may add later on, for now the results are the same whether I normalise earlier or not.

    My main issue is the loss of small values. I was thinking of splitting the bytes of my float into the RGBA channels and reassembling in the shader, do the shaders support bit shifting? This would solve all my problems :)

    Thanks for your help

    Karl

    Edit:

    Ok I caved in, I added this to my DataGrid class:

    Code (csharp):
    1.  
    2.         /// <summary>
    3.         /// Noramlise the data using maxValue
    4.         /// </summary>
    5.         /// <param name="maxValue"></param>
    6.         public void Normalise( float maxValue )
    7.         {
    8.             for( int x = 0; x < Cols; ++x )
    9.             {
    10.                 for( int y = 0; y < Rows; ++y )
    11.                 {
    12.                     for( int i = 0; i < Grid[x, y].Length; ++i )
    13.                     {
    14.                         Grid[x, y][i] = Math.Min( Grid[x, y][i] / maxValue, 1.0f );
    15.                     }
    16.                 }
    17.             }
    18.         }
    19.  
    :)

    I now do this

    Code (csharp):
    1.  
    2. System.Drawing.Color.FromArgb( 0, 0, ( int )Math.Round( scalarNormalised ) * 255
    3.  
     
    Last edited: Jul 24, 2012
  33. npsf3000

    npsf3000

    Joined:
    Sep 19, 2010
    Posts:
    3,830
    Ahh, I get you now, sorry for being slightly slow.

    You are talking about caching... the earlier system cached references - because lots of pixels shared the exact same 'data' [a pointer to a sensor in my version] - but now they all have their own array of values - that's probably unique.

    Okay then, the first thing to do is to cut our losses. Right now we are storing a float[,][] or similar. However as we noted, at least for now, we only need to store 0-255 - because we can't display more.

    So now the math is:

    1024x1024 - 1MB per image.
    4096x4096 - 16.8MB per image.

    The good news is that this helps out for most jobs. The bad news is that it doesn't fix the underlying problem - a 4k image * 200 time-stamps is ~3.4GB - i.e. crashing big time in unity. Now while I wouldn't build these images in unity [it's slow, only 32 bit, not a great fan of threading etc.] it's still a flaw in the algorithm.

    Now there's an obvious solution - split up the data. And this is the right solution :p Set yourself a limit - say 500MB. Break your job up into lots that are smaller than this - by reducing how many images you do at once. The logic would go like this:

    Code (csharp):
    1.  
    2. //We want to process 200 images.
    3. // Image Size/Max MB = Max Batch Size - say it's fifty.
    4. //for (var batch =0; batch<images to process; batch+= Math.Min(maxBatxhSize, remainingImages))
    5. //Cache the pixel data for 50 images.
    6. //Write 50 images.
    7. //End For
    8.  
    Good news is that it's simple to do, and shouldn't too badly stuff up your structure :)

    There's another way of doing it, that doesn't require any more ram, can handle potentially hundreds GB's of data on a consumer machine and *doesn't* involve splitting the data up! I'll give you 5 mins to think of it, then you can look at this monstrosity :p
    .
    Yes and no - normalizing now is easy [it's few LOC that you put in a method], it reduces the possibility of accidental errors [particularly with casting] and the chance of future code breaking before you fix. Either way it's not that important to me atm.

    Edit: Solved - see, wasn't that easy :p

    Why do you want/need more than 255 values for a pixel on your texture?
     
    Last edited: Jul 24, 2012
  34. karljj1

    karljj1

    Joined:
    Feb 17, 2011
    Posts:
    440
    Hi,

    As well as colouring the texture based on depth i am also using a vertex shader to create a mesh where each point is positioned using the float value. Ideally I want as much accuracy as possible:

    E.G

    Code (csharp):
    1.  
    2.         // Vertex stage
    3.         void vert( inout appdata_full v, out Input data )
    4.         {                      
    5.             #if !defined( SHADER_API_OPENGL )
    6.                        
    7.             v.vertex.z += lerp( tex2Dlod( _TimeStamp0, v.texcoord ).b, tex2Dlod( _TimeStamp1, v.texcoord ).b, _time ) * _maxDepth * _mult;             
    8.            
    9.             #endif
    10.  
    11.             float4 hpos = mul( UNITY_MATRIX_MVP, v.vertex );               
    12.         }
    13.  
    I am generating more time steps. Basically the time steps in-between points, this is in order to smooth the data.
    I could apply an image algorithm to smooth but my way is more accurate(for keeping data).
     
    Last edited: Jul 24, 2012
  35. npsf3000

    npsf3000

    Joined:
    Sep 19, 2010
    Posts:
    3,830
    LOL, I just spent an hour rewriting my last post because I didn't think this was an issue, and turns out it is! Luckily the solutions I gave will also work for this, albeit a little bit more work you're end stitching it together. I would ask if you need to do this at the data generation stage - or if you can simply do this as you're writing out the images - Image2[x,y] = Image1[x,y] + Image3[x,y] .

    You have 32 bits you can play with - Good luck :p
     
    Last edited: Jul 24, 2012
  36. karljj1

    karljj1

    Joined:
    Feb 17, 2011
    Posts:
    440
    Edit: Deleted rambling.

    Thanks for your help, everything is working now but in the future i would like be able to split my float into the RGBA bytes. Do you know if the shaders support bit shifting or can you suggest a way to combine the RGBA into a float?

    Karl
     
    Last edited: Jul 24, 2012
  37. karljj1

    karljj1

    Joined:
    Feb 17, 2011
    Posts:
    440
    I just found this
    Code (csharp):
    1.  
    2. highp float decode32(highp vec4 rgba) {
    3.     highp float Sign = 1.0 - step(128.0,rgba[0])*2.0;
    4.     highp float Exponent = 2.0 * mod(rgba[0],128.0) + step(128.0,rgba[1]) - 127.0;
    5.     highp float Mantissa = mod(rgba[1],128.0)*65536.0 + rgba[2]*256.0 +rgba[3] + float(0x800000);
    6.     highp float Result =  Sign * exp2(Exponent) * (Mantissa * exp2(-23.0 ));
    7.     return Result;
    8. }
    9.  
    Eeek :x
     
  38. npsf3000

    npsf3000

    Joined:
    Sep 19, 2010
    Posts:
    3,830
    LOL - do *not* do it! It's fun, and it does actually work [particularly as my modest SSD can push 200MB/s easily], however you're going to be much better off simply limiting how many 'timesteps' you do in a batch - and it's not a lot of code either. Less code, faster performance, less wear tear on IO!

    Then I'll leave that too you, I've tried to dabble in shader coding with no real success - I'll stick to generating images on my CPU :p

    Everything we've done is very flexible - saving 2, 3 or 4 bytes of 'depth' instead of one is quite doable - just need some minor tweaks here and there, and of course with the increased data size more focus on the batching to keep memory down.
     
  39. npsf3000

    npsf3000

    Joined:
    Sep 19, 2010
    Posts:
    3,830
    It's your funeral.
     
  40. karljj1

    karljj1

    Joined:
    Feb 17, 2011
    Posts:
    440
    Well thanks for your help, it was very useful!

    I sent you a private message the other day with a new challenge if your interested :)

    Will you be attending UNITE this year? I will buy you a beer :)

    Found a Unity shader function to convert RGBS to float - DecodeFloatRGBA :)

    Karl
     
    Last edited: Jul 24, 2012
  41. npsf3000

    npsf3000

    Joined:
    Sep 19, 2010
    Posts:
    3,830
    I't looks interesting... but no promises - I should be working :p


    Somewhat unlikely this year given the substantial distance and the cost of air-fare - but thanks :)
     
  42. npsf3000

    npsf3000

    Joined:
    Sep 19, 2010
    Posts:
    3,830
    Last edited: Jul 27, 2012
  43. karljj1

    karljj1

    Joined:
    Feb 17, 2011
    Posts:
    440
    Thanks that looks interesting. I will try to add the remove caching stage into my new code, I am now encoding the float into the RGBA channels and using DecodeFloatRGBA in the shader. This seems to have solved my precision problems, it also generates some pretty funky looking textures :)

    Karl
     
  44. chanfort

    chanfort

    Joined:
    Dec 15, 2013
    Posts:
    641
    Probably the thread is dead in 2 years, but maybe still worth to ask, as I am working on other similar problems, which involves nearest neighbour searches.
    1. How do you adopt this KDTree to Unity's C# ?
    2. I was using this version of kdtree, which seems to be working quite nicely. But I suspect that your version might be more optimised and it would be interesting to compare. Do you still have your kdtree scripts adopted to Unity?
     
  45. npsf3000

    npsf3000

    Joined:
    Sep 19, 2010
    Posts:
    3,830
    @chanfort if you read through the examples I linked to in pastebin, simply by using a hashgrid (and some other optimisations) we got far beyond the performance needed - from 20 hours to 4s IIRC.

    Take a look into it and feel free to ask any questions!
     
  46. chanfort

    chanfort

    Joined:
    Dec 15, 2013
    Posts:
    641
    I am using kdtrees not for textures, but for nearest neighbour (NNs) searches in RTS game. Is there possible to search NNs in your hashgrid? If no, I was wondering if some scripts remains from these days when kdtrees were used.
     
  47. karljj1

    karljj1

    Joined:
    Feb 17, 2011
    Posts:
    440
    Hi @chanfort,

    I am not sure what happened to my KD tree code however the implementation of one is quite simple.
    Here is an open source one I just found that may be helpful:
    https://code.google.com/p/kd-sharp/

    Alternatively is this something you could solve by using the unity path finding system/nav mesh grid?

    Karl
     
  48. chanfort

    chanfort

    Joined:
    Dec 15, 2013
    Posts:
    641
    Hey Karl, thanks for answer. NavMesh would be quite interesting, but I was unable to find something like neighbour searches there. Did you had something specific in mind?
     
  49. karljj1

    karljj1

    Joined:
    Feb 17, 2011
    Posts:
    440
    I was thinking if you know the locations you need to visit in your NN problem you could use the path finding system to calculate the shortest edge between the locations. I presume you are trying to solve some sort of travelling salesman problem?

    K
     
  50. chanfort

    chanfort

    Joined:
    Dec 15, 2013
    Posts:
    641
    well, no, it's actually not related with travelling salesman. In general I have two lists of warriors - attackers and targets. Each attacker needs to find what to attack. And I find out that assigning nearest neighbours directly from target list is very good and naturally looking solution. You can actually see it in one of my battle fronts simulation for 4000 or 12000 units (press "F" key to start battles when you are in the scene).

    The problem with this approach is that nearest neighbour searches are the heaviest part of these simulations and I can't get running battles larger than several thousand units at playable FPS just because NN searches are to heavy (other heaviest things in these simulations are about 5-10 times lighter than NN searches).

    As I used only one version of kdtree (which I posted above), I suspect that other implementations might be faster and more optimised than this one I am currently using.