Sign in to follow this  
thames

How to store XYZ as a unique key?

Recommended Posts

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

Share this post


Link to post
Share on other sites
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.6
Triangle: 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.7
Triangle: 1.6, 0.7, -3.2 -> -3.2 1.6 0.7
Triangle: 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

Share this post


Link to post
Share on other sites
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?

Share this post


Link to post
Share on other sites
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. :)

Share this post


Link to post
Share on other sites
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.

Share this post


Link to post
Share on other sites
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.

Share this post


Link to post
Share on other sites
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

Share this post


Link to post
Share on other sites

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now

Sign in to follow this