CODEWITHSUNDEEP
arraysalgorithmsorting
Kinru
Kinru

Reputation: 399

Keeping track of indices after sorting

So I have several arrays of positions, velocities, etc in 3D-space (vec3(x,y,z)) and another array which holds indices that are used to look-up in the vec3 arrays. This is all for a particle-system representing cloth (in case anyone was wondering).

The second array is far larger than the position array because for each particle, the second array represents a type of "spring" relationship with another particle. So for example, any given particle might have a "spring" attached to 3 different particles. So the first bunch of indices in the second array might look like this: [0, 1, 0, 2, 0, 3, 0, 4, ...]

The problem here is that the position array is sorted based on a hash function used for finding neighbors in a uniform grid. This means that the indices held in the 2nd array will no longer be valid. I'm trying to figure out a way to sort the positions and then still use the 2nd array to index properly.

One thought that I've had would be to have a 3rd array which stores the new indices based on the sorting function, but I am not sure how I could actually go about doing this.

Also, the reason the data is separated rather than being put into an object is that this is being run in CUDA and it is an optimization for speed/memory.

Is there a simple way of going about this? Thanks for any help.

Upvotes: 1

Views: 170

Answers (1)

Claudiu
Claudiu

Reputation: 229361

Would something like this work?

Transfer your array of vec3(x, y, z)s into an array of pair(index, vec3(x, y, z)). Sort this new array by taking the hash function of the second element. The result will be a sorted array of pair(index, vec3(x, y, z)), where index is the vector's initial position in the array. Then, use this to construct a third "lookup" array of integers whose indices are the initial indices and whose values are the new values. Now to get a vector from your second array you do something like vector_pairs[lookup[spring[4]]].second.

Python-ish pseudocode:

vecs = ...
spring = ...
pair_vecs = [(index, vec) for index, vec in enumerate(vecs)]
pair_vecs.sort(key=lambda index, vec: hash(vec))
lookup = [0] * len(pair_vecs)
for new_index, (initial_index, vec) in enumerate(pair_vecs):
    lookup[initial_index] = new_index

Upvotes: 2

Related Questions