Hello

I have many vertices drawn on my Unity3d C# application window (thousands). I am attempting to come up with a fast way to detect which vertex has been clicked.

My idea is to use a sorted list. The list will be ordered by a vector/vertices distance to (0,0,0):

List <KeyValuePair<double, GameObject>> vectorMap = new List <KeyValuePair<double, GameObject>>();

I use a binary search to order, search and add to the list.

Add/Insertion Method:

public void recordElementVertices(Element ele) { // Element is a Sub-Class of GameObject foreach (Vector3d v in ele.WorldVertices) { double distFromZero = Vector3d.Distance(Vector3d.zero, v); int index = -1; if (Algorithms.LowerBounds(vertexDistanceList, distFromZero, out index, DEF_PRECISION) != Algorithms.SearchResult.FOUND_TARGET) vertexDistanceList.Insert(index, new KeyValuePair<double, List<GameObject>>(distFromZero, new List<GameObject>())); vertexDistanceList[index].Value.Add (ele.gameObject); } }

Hit Test (Search) Method:

public List<GameObject> hits(Vector3d mousePos) { int index = -1; double distFromZero = Vector3d.Distance(Vector3d.zero, mousePos); // Binary search will search for an exact hit or find the closest vertex to the mouse pos if (Algorithms.BinarySearch(vertexDistanceList, distFromZero, out index, DEF_PRECISION) == Algorithms.SearchResult.FAIL || index < 0) return null; return vertexDistanceList[index].Value; // return all game objects that occupies that vector position }

This all works nicely and is fast but there is a major flaw. The algorithm doesn't take into account the vertices angle from (0,0,0). So 2 points that are the exact same distance from (0,0,0) but have different angles will be considered the same vertex when they are not.

For example; these 2 points lie 5 metres from (0,0,0) but have different angles. My algorithm will consider these 2 points as occupying the same place in space when they are in a completely different position.

Do you have any suggestions how I can hash a distance and angle to produce a unique result that describes that point in space? Some simple like doing **Distance ^ Angle** could produce a unique result but they would also produce huge numbers. A restriction is that my list sorting algorithm requires that two points close to each other should produce a hash that is similar in order to find points close to the mouse position. Hope that makes sense.

I've heard about Locatily Sensitve Hashing but it looks like implementing this algorithm would be very tricky.

Any advice would be greatly appreciated.