Iterating large datasets

Unity Engine
1

Hey guys,

so using vectrosity I’ve been building a drawing application. I have been implementing an eraser tool that works by iterating every point in every line that currently exists on the canvas, and comparing that square magnitude to the current mouse position.

This works okay for erasing, but the amount of data becomes large quickly as someone is drawing and the eraser slows down very fast when iterating hundreds of thousands of points each frame, as makes sense this is a lot of iteration to do even frame.

Are there any patterns for dealing with problem like this?

I’ve tried to speed it up by keeping track of which lines are empty and then removing those from the list of iterated lines.

2

At the expense of using even more memory, try implementing a spatial hash.

3

You need a spatial index of some sort. Spatial hashing is one approach, indeed. You could also use something like octrees or BSP trees. The trick is being able to quickly retrieve a subset of all the points which is roughly in the right place, and then to sort through that subset by hand like you’re presently doing.

4

so I found this blog post and a few articles on spatial hashes and it makes sense to me, but what exactly is going on in this section of the code?

   private ArrayList Keys(Vector3 v)  {
        int o = cellSize / 2;
        ArrayList keys = new ArrayList();
        keys.Add(Key(new Vector3(v.x-o, v.y-0, v.z-o)));
        keys.Add(Key(new Vector3(v.x-o, v.y-0, v.z-0)));
        keys.Add(Key(new Vector3(v.x-o, v.y-0, v.z+o)));
        keys.Add(Key(new Vector3(v.x-0, v.y-0, v.z-o)));
        keys.Add(Key(new Vector3(v.x-0, v.y-0, v.z-0)));
        keys.Add(Key(new Vector3(v.x-0, v.y-0, v.z+o)));
        keys.Add(Key(new Vector3(v.x+o, v.y-0, v.z-o)));
        keys.Add(Key(new Vector3(v.x+o, v.y-0, v.z-o)));
        keys.Add(Key(new Vector3(v.x+o, v.y-0, v.z-0)));
        keys.Add(Key(new Vector3(v.x-o, v.y-o, v.z-o)));
        keys.Add(Key(new Vector3(v.x-o, v.y-o, v.z-0)));
        keys.Add(Key(new Vector3(v.x-o, v.y-o, v.z+o)));
        keys.Add(Key(new Vector3(v.x-0, v.y-o, v.z-o)));
        keys.Add(Key(new Vector3(v.x-0, v.y-o, v.z-0)));
        keys.Add(Key(new Vector3(v.x-0, v.y-o, v.z+o)));
        keys.Add(Key(new Vector3(v.x+o, v.y-o, v.z-o)));
        keys.Add(Key(new Vector3(v.x+o, v.y-o, v.z-o)));
        keys.Add(Key(new Vector3(v.x+o, v.y-o, v.z-0)));
        keys.Add(Key(new Vector3(v.x-o, v.y+o, v.z-o)));
        keys.Add(Key(new Vector3(v.x-o, v.y+o, v.z-0)));
        keys.Add(Key(new Vector3(v.x-o, v.y+o, v.z+o)));
        keys.Add(Key(new Vector3(v.x-0, v.y+o, v.z-o)));
        keys.Add(Key(new Vector3(v.x-0, v.y+o, v.z-0)));
        keys.Add(Key(new Vector3(v.x-0, v.y+o, v.z+o)));
        keys.Add(Key(new Vector3(v.x+o, v.y+o, v.z-o)));
        keys.Add(Key(new Vector3(v.x+o, v.y+o, v.z-o)));
        keys.Add(Key(new Vector3(v.x+o, v.y+o, v.z-0)));
        return keys;
    }
5

isnt this just a texture, would not GetPixels and SetPixels work just as good without going through every pixel.

You already know the height and width of your block. So if its 10x10, just get a 10x10 block and set it back when you are done.

Concept: Create mesh colliders for a tank that are similar in shape to the tank shell. UV them so that they match the tanks UV coordinates. Now, every time it is hit, just get the UV coordinates and convert them to texture coordinates +/- half the width of a bullet texture. Get the pixels. User the alpha and texture maps to blend the bullet hold to the tank. Set the pixels back and viola… instant smooth bullet hold that stays on the tank and doesnt cost any more memory or game objects to produce.

6

I’m not really understanding the tank concept relating here, but to your first point the canvas is not a texture, the lines are drawn with vectrosity so they are actually meshes containing arrays of points.

7

Sorry about that, I should have said spatial index; it just happened that the last time I had to implement a quick one I used a hash.

Spatial hashing breaks objects up into cells or buckets based on their positions in space. Querying a point in space means you querying all the cells that could possible satisfy your query; if the query is near the edge of a cell, you also need to query the adjacent cell in case what you need to check has flowed over. What this function does is it gives you the keys for all the cells in a 3x3x3 area around your query point, just in case you’re near an edge/corner.

8

thanks for all the help,

I got this working in universe with a sphere just based on its position, but I’d like to do it with arbitrary lines that the user draws, which could overlap any number of cells, even all of them at once, I was reading a good method is to use the bounding box of the object.

Any pseudo code example would help me out, also which bounds is the correct one to use? mesh.bounds, or renderer.bounds?

9

woohoo,

got it working with render.bounds.

it’s coded in universe, if anyone is interested once I get the graph cleaned up I’ll post it a link to the universe forum with the package.