ok as i dynamically create triangles, I want to add the vertices to an ordered array, to do this i ideally need a unique key so i can order by this. other wise i would be ordering by X, then Y, then Z, which would be 3 times the overhead. I hope you understand what i mean. Any suggestions? I did try using magnitudes but got lots of the same magnitudes back. thank you Tom

Simplest thing I can think of would be to use the values of the three vertices in ascending order:

Triangle: 0.7, -3.2, 1.6 -> -3.2 0.7 1.6Triangle: 1.6, 0.7, -3.2 -> -3.2 0.7 1.6

This does ignore winding however. If you need winding as well then just use the lowest value first, but maintain order:

Triangle: 0.7, -3.2, 1.6 -> -3.2 1.6 0.7Triangle: 1.6, 0.7, -3.2 -> -3.2 1.6 0.7Triangle: 1.6, -3.2, 0.7 -> -3.2 0.7 1.6 (reversed winding)

That said, are you sure this is really the best way to do what you're wanting?

Enigma

hmm that would still be ordering by X,Y and Z though and would require checking XY&Z upon finding within the ordered array. I was wondering if there was a single value way of indexing them.


hmm im really not making this clear am i?

You are trying to map a 3d space onto a 1d space, where each point in the 3d space has a unique match in the 1d space. If the positions in the 3d space are discrete (like integers) then this is possible even if the space is infinite. In the 2d to 1d case this could be done by mapping a 1d path as a spiral out from the origin that visits every point in the space. This would give you (x,y) = f(t) where t is the distance along the path and 0 <= t <= infinity.

The 3d to 1d case could be done with expanding spherical shells. Each shell is a 2d surface on which every point could be visited in order by a spiral path. If we visit each shell in order of increasing radius (remember space is discrete but infinite so there are an infinite number of shells, but not uncountably many), then we can arrive at (x,y,z) = f(r,t). Both r (radius of current shell) and t (distance along the path on that shell) can be calculated from a single variable function since the number of points on each shell is finite.

However if we have a continuous 3d space I believe there are uncountably many points in that space, which will prevent us from mapping it to a 1d space using the above technique. Of course we are using a digital representation of that space, which means that it can not be actually continuous. For example, if you used a fixed point decimal representation of the points in your 3d space you could use the above scheme directly. This should work with floating point numbers too, at the very least you could map to a fixed point space with a higher resolution than the floating point space and the floating point nubmers would only be able to represent some points in the space.

Even better, our actual 3d space isn't infinite. This means we don't have to visit points in a spiral pattern. We can just start in one corner of the space and procede in an orderly fashion to the far corner. (This was the method suggested by Enigma above.)

Now then I'm not sure any of this is of any practical value. You probably want to look into spatial partitioning systems such as oct-trees, BSP, ABT, etc.

Also it's been quite a while since I took a theory of computation class so it's quite possible I made mistakes in the math above. It was fun to try and remember all that though. :)

So called 'plane filling curves' can fill the plane (obviously) and give a 2D->1D mapping in continuous spaces. Same for space filling curves. (see this for an intro).

This doesn't help much the OP though. You could treat the 3 floats as a 12 byte vector and sort by that, although this won't buy you all that much in terms of performance. Maybe if you give a clue as to *why* you need them sorted it would be easier to give an answer.

Im creating a polygon housing class, which holds unique vertices and idices to these for triangles. Within this class i can reverse vertices, calc vertex normals etc.

I wanted them sorted so i could quickly add a vertex to the ordered list. This way i can tell if they are unique vertices easily. And if they are i just use the vertice that is in the list to indice to, instead of adding a duplicate.

This old thread of mine might help
Determing duplicate vertices

It was a discussion I had last year concerning the most optimal method for determing duplicate vertices in a large dataset.

The solution provided (and worked far better than I expected) was to use a hash table. The thread addresses a number of issues with hash tables (such as collisions) and discusess a optimum (or at least good enough for the job) method to geenerate the hash key, whilst keeping memory requirements low.

Actually looking again it appears for completeness i added my final code to the last message in the thread. So if this method is appropraite it shouldn't take long to implement it

Cheers