Finding a vertex index in a sphere.
Author
Hi all. I'm busy on a classic artillery game on a 3D globe.
Since i want to be able to do craters and shockwaves through the globe i'd like to look up the heights of my sphere.
And since the sphere is a tesselated octahedron the vertexes are not in a very usable order.
I'd like to rearrange them to be able to give a direction vector and get my vertex index (closest to the vector). To do this i would normalize the vertexes (or just use the normals, since they corresponding indexes) Then order them by x, then by y and then by z.
When searching the index i would have to go through the list for x, then for y and then for z to compare with the direction vector. That's a lot of searching to do for just one index. Has anyone got any suggestions on finding this vertex index? Any would be very welcome.
Thanx,
Marty
Say your vertices have coordinates (0,0,1), (0,0,-1), (0,1,0), (0,-1,0), (1,0,0) and (-1,0,0). Take any point in the sphere, check which coordinate has the maximum absolute value and see if the value was positive or negative. That should tell you very quickly which vertex is closest.
The numbering of the vertices is kind of irrelevant, I think.
The numbering of the vertices is kind of irrelevant, I think.
Author
I don't get what u mean exactly. I've got a sphere with about 33000 vertexes. And a vector from the origin. I need to find the vertex whose direction is closest to the vector.
I'd need to run through all 33000... There must be a better way.
Thanx,
Marty
I'd need to run through all 33000... There must be a better way.
Thanx,
Marty
You could try BSPing your sphere. Basically, just divide it by a plane recursively until you have an acceptably sized set to check per BSP node. It would probably work well if you used axis-aligned planes. Your testing algorithm would just be a simple walk of the BSP tree, checking which side of the BSP plane your vector is.
You could reduce your set of vertices to check down to about 128 verts if your BSP has only 8 levels.
Another thing to note: you could add your vertex-indices to the BSP tree and duplicate those that lie within an acceptable bias within adjacent BSP nodes. ie. those vertices that lie close to the BSP splitting planes.
You could reduce your set of vertices to check down to about 128 verts if your BSP has only 8 levels.
Another thing to note: you could add your vertex-indices to the BSP tree and duplicate those that lie within an acceptable bias within adjacent BSP nodes. ie. those vertices that lie close to the BSP splitting planes.
The BSP idea is a good one, but requires additional memory for the BSP tree.
Another one would be like this:
Since you have information of the vertex positions and how they are connected (assuming you are drawing triangles), you can start with any vertex and check if one of its neigbours is closer to the direction vector. If there is no neighbour being closer, the current vertex is closest. If at least one neighbour is closer, test again for this one.
This will take more time than the BSP idea, but you can reduce memory usage.
Another one would be like this:
Since you have information of the vertex positions and how they are connected (assuming you are drawing triangles), you can start with any vertex and check if one of its neigbours is closer to the direction vector. If there is no neighbour being closer, the current vertex is closest. If at least one neighbour is closer, test again for this one.
This will take more time than the BSP idea, but you can reduce memory usage.
There is a simple solution for this without any BSP trees.
It all depends on how the sphere is defined.
You say your sphere is built from an octahedron (8 faces). So you've probably taken the following steps:
1) Define six vertices to be the corner nodes of the octahedron, e.g. the ones alvaro mentioned.
2) From the six vertices, build the 8 octahedron faces (triangles).
3) Subdivide each face *regularly* to obtain a regular mesh.
4) Project each mesh back to the sphere by normalizing it's vertices.
Now if you have an arbitrary direction vector, you just have to
1) Find the octahedron face in this direction. This comes down to computing an intersection of a line and a plane. (Maybe it's even simpler with some tricks)
2) Since the sphere mesh is regular (like a heightmap) on each octahedron face, you just have to compute the closest mesh index of the point where the direction vector hits the face. This is like solving a small linear system of equations.
That's an O(1) operation and doesn't depend on mesh size.
It all depends on how the sphere is defined.
You say your sphere is built from an octahedron (8 faces). So you've probably taken the following steps:
1) Define six vertices to be the corner nodes of the octahedron, e.g. the ones alvaro mentioned.
2) From the six vertices, build the 8 octahedron faces (triangles).
3) Subdivide each face *regularly* to obtain a regular mesh.
4) Project each mesh back to the sphere by normalizing it's vertices.
Now if you have an arbitrary direction vector, you just have to
1) Find the octahedron face in this direction. This comes down to computing an intersection of a line and a plane. (Maybe it's even simpler with some tricks)
2) Since the sphere mesh is regular (like a heightmap) on each octahedron face, you just have to compute the closest mesh index of the point where the direction vector hits the face. This is like solving a small linear system of equations.
That's an O(1) operation and doesn't depend on mesh size.
The Anonymous Poster gave the right O(1) answer. I suppose the octahedron has a square (ccw) {{1,0},{0,1},{-1,0},(0,-1)} section at the equator. There is an obvious implicit space partition in 8 sub spaces, corresponding to the eight faces. You can index the faces by a 3bit octant.
bit 0 = signbit(x) = (x>0) ? 0 : 1;
bit 1 = signbit(y) = (y>0) ? 0 : 1;
bit 2 = signbit(z) = (z>0) ? 0 : 1;
Thus :
Face 0 (X+,Y+,Z+)
Face 1 (X-,Y+,Z+)
Face 2 (X+,Y-,Z+)
etc ...
1) This partition is conserved by the octahedron to unit sphere transfo. So getting the face index is immediate with the signbits of your input 3D vector.
Next finding the nearest sub-vertex or sub-face is also trivial but can be accelerated by the choice of your subdivision scheme (tesselation). First take the absolute values of the point coords. So every face is treated just like face 0.
Now the inverse sphere to face transfo is done, I suppose it's obvious how to see how to do it. We're left with the 'texture coords' or 'triangle coords' on the face 0 <= (x=s) <=1, 0<= (y=t) <= 1 and 0<=x+y<=1.
I suppose each face is a mesh, and owns its vertices. (You can cope with shared vertices later if you want but this makes it a bit more tricky). I suppose tesselation is done this way (you can recurse) :
So the vertex index can be easilly found this way :
Scale by the number of edge subdivisions. Discretize, x and y by rounding to the nearest. (Example x integer in [0,2], y integer in [0,2]).
n = (x+y) (index of the diagonal)
i = n*(n+1)/2 + y (index of the vertex)
EDIT :
BTW this last trick is a useful scheme to remember.
In math it can be used to prove that the cardinal (the 'size' if you want) of |N (the infinite integers set) is equal to |Nx|N (the set of the integer doubles), nd thus to the cardinal of any power of |N.
You can use it for quick 'ray casting' (collision detection oriented) in many triangle subdivision schemes if you have an explicit inverse transformation from 3D point (near or on surface) to 'triangle coords'. It was the case here.
[Edited by - Charles B on September 29, 2004 5:26:56 AM]
bit 0 = signbit(x) = (x>0) ? 0 : 1;
bit 1 = signbit(y) = (y>0) ? 0 : 1;
bit 2 = signbit(z) = (z>0) ? 0 : 1;
Thus :
Face 0 (X+,Y+,Z+)
Face 1 (X-,Y+,Z+)
Face 2 (X+,Y-,Z+)
etc ...
1) This partition is conserved by the octahedron to unit sphere transfo. So getting the face index is immediate with the signbits of your input 3D vector.
Next finding the nearest sub-vertex or sub-face is also trivial but can be accelerated by the choice of your subdivision scheme (tesselation). First take the absolute values of the point coords. So every face is treated just like face 0.
Now the inverse sphere to face transfo is done, I suppose it's obvious how to see how to do it. We're left with the 'texture coords' or 'triangle coords' on the face 0 <= (x=s) <=1, 0<= (y=t) <= 1 and 0<=x+y<=1.
I suppose each face is a mesh, and owns its vertices. (You can cope with shared vertices later if you want but this makes it a bit more tricky). I suppose tesselation is done this way (you can recurse) :
Up view of Face 0 (X+, Y+, Z+). Y+ ^ | 5 | . 2--4 | .| . 0--1--3---> X+So the vertex index can be easilly found this way :
Scale by the number of edge subdivisions. Discretize, x and y by rounding to the nearest. (Example x integer in [0,2], y integer in [0,2]).
n = (x+y) (index of the diagonal)
i = n*(n+1)/2 + y (index of the vertex)
EDIT :
BTW this last trick is a useful scheme to remember.
In math it can be used to prove that the cardinal (the 'size' if you want) of |N (the infinite integers set) is equal to |Nx|N (the set of the integer doubles), nd thus to the cardinal of any power of |N.
You can use it for quick 'ray casting' (collision detection oriented) in many triangle subdivision schemes if you have an explicit inverse transformation from 3D point (near or on surface) to 'triangle coords'. It was the case here.
[Edited by - Charles B on September 29, 2004 5:26:56 AM]
I dared to copy a private mail here, since this problem is very generic for anyone interested in planet rendering).
No. When I mentionned a STATIC subdivision implicit to your mesh arrangement. I never meant using some kind of graph structure (parent child nodes), any kind of recursion. It's O(1), that is immediate.
I suppose you have a static subdivision. For instance 8*16 = 128 faces. Whatever as long as you have half grids (cf later). You can also use plain grids by connecting top and bottom faces two by two.
Please tell me which point you don't follow :
1) You see the 3 canonical planes : x=0, y=0 and z=0. OK ?
2) They subdivide the space in 8 sub spaces :
(X+,Y+,Z+), (X-,Y+,Z+), etc ... I hope you see them ! OK ?
3) Each of the 8 faces of your octahedron fits entirely in one of these sub spaces, since I took these 4 vertices at equator {{1,0},{0,1},{-1,0},(0,-1).
4) When you deform each octahedron triangle into a eighth of sphere at infinity, or when you subdivide it to build one eighth of your mesh, you stay in the same sub-space.
5) When you take any ray, reading the sign bits gives you directly the index of the subspace concerned, thus the original octahedron face index, thus the quarter of the mesh concerned.
6) Now you take a vector, a ray. Read the sign bits. Find the subspace index.
7) Make a central projection on the original triangle. (I can detail this part if you don't see how). Remove the coord signs (fabs).
8) Multiply x and y (discard z) by n, the rows/columns of you 'half grid '.
9) Discretize the coordinates.
10) Apply the formula of my previous post and find the index of the nearest vertex.
In the end you will see it's 4 lines of C code and a very fast and simple computation. Just have a clear picture in mind.
Quote:
Hi.
I think I get what you're saying, but might be mistaken. He're are my two interpretations:
1 Treat the 8 octahedron faces as a flat surface containing the children triangles on it's surface (when subdivided) check where my vector (i'll call it ray from now) hits the face and find which of the 4 subdivision triangles it hit. Then do it for that triangle, etc. untill I hit a face with no more subdivisions/children. The ray hit that face... right?
2 Treat the 8 octahedron faces as a flat surface containing the children, grandchildren, etc. on it's surface. Do something I don't get to find the last generation child (smallest subdivision trianfle) on this triangle.
Option 2 would be faster, but I get 1... If it's 2 (or maybe something else) Please explain the thing I don't get some more, if you want to and have the time, ofcourse.
Thanx a lot for the help!
Marty
No. When I mentionned a STATIC subdivision implicit to your mesh arrangement. I never meant using some kind of graph structure (parent child nodes), any kind of recursion. It's O(1), that is immediate.
I suppose you have a static subdivision. For instance 8*16 = 128 faces. Whatever as long as you have half grids (cf later). You can also use plain grids by connecting top and bottom faces two by two.
Please tell me which point you don't follow :
1) You see the 3 canonical planes : x=0, y=0 and z=0. OK ?
2) They subdivide the space in 8 sub spaces :
(X+,Y+,Z+), (X-,Y+,Z+), etc ... I hope you see them ! OK ?
3) Each of the 8 faces of your octahedron fits entirely in one of these sub spaces, since I took these 4 vertices at equator {{1,0},{0,1},{-1,0},(0,-1).
Top view,4 top faces (f0, f1, f2, f3)4 top subspaces (S0, S1, S2, S3)5 vertices visible. Y ^ | x S01=001b. | . 0=000b : X+,Y+,Z+ .f1 |f0 .--x-----x-----x---> X .f3 |f2 .3=011b. | . 2=010 : X+, Y-, Z+ x S2 |4) When you deform each octahedron triangle into a eighth of sphere at infinity, or when you subdivide it to build one eighth of your mesh, you stay in the same sub-space.
5) When you take any ray, reading the sign bits gives you directly the index of the subspace concerned, thus the original octahedron face index, thus the quarter of the mesh concerned.
6) Now you take a vector, a ray. Read the sign bits. Find the subspace index.
7) Make a central projection on the original triangle. (I can detail this part if you don't see how). Remove the coord signs (fabs).
8) Multiply x and y (discard z) by n, the rows/columns of you 'half grid '.
Quote:
Example :
Half grid of 4 rows => Original triangle split into 16.
*
* *
* * *
* * * *
* * * * *
9) Discretize the coordinates.
10) Apply the formula of my previous post and find the index of the nearest vertex.
In the end you will see it's 4 lines of C code and a very fast and simple computation. Just have a clear picture in mind.
Author
EDIT:
I wrote this post yesterday. I deleted the lot, because I think differently now.
I get what you're saying, although I disagree on point 4.
The subspaces are different when I divide my triangle more then once before normalizing then they would be if i divide, normalize, divide children, normalize, divide grandchildren, normalize, etc.
EXAMPLE:
This is why I use recursive tesselation. The vertices will not be in a usable order this way, since the vertices will be in the order i create them.
The solution can be this: Not tesselating recursively, using
the vertice order you proposed for the raycasting, but creating
and normalize the vertices in the right order.
EXAMPLE:
So when the grandchildren are made their parents are allready normalized. Now I still need a formula which gives me all the parents before their children before their grandchildren, etc. But for the order of verts you proposed (the one above).
This formula should work when i tesselate once, but also when i tesselate 10 times... Since the code should be flexible and my sphere class should be able to return spheres of different tesselation levels.
I'm back at my first problem... a magic formula to sort the vertices, only not for spiraling down, now for the ray casting...
Thanx a lot for all the help so far!
Marty
[Edited by - Marty666 on October 2, 2004 9:54:39 AM]
I wrote this post yesterday. I deleted the lot, because I think differently now.
I get what you're saying, although I disagree on point 4.
The subspaces are different when I divide my triangle more then once before normalizing then they would be if i divide, normalize, divide children, normalize, divide grandchildren, normalize, etc.
EXAMPLE:
0 = vertex ...... = (r=1)------ = original face .....0..... ...... | ...... ..... | ..... ....0 | 0.... ... \ | / ... .. \ | / .. 0-----------1/4-----------1/2-----------3/4------------0ABOVE: the original face is split, then both halfs are splitand after that they're all normalized.Take a piece of paper, because this is far easyer explainingthan in ascii. Draw the above... Then in your drawing drawanother situation in this order:1) Split the original face. 2) Normalize the new vertex. 3) Draw the new faces.4) Split both new faces (remember the new faces are not in the original face anymore).5) draw lines from the origin to the new vertexes that came from the second split. These lines will NOT intersect at 1/4 and 3/4 of the originalface, thus SUBSPACES ARE DIFFERENT for the two situations.The second situation (split, normalize, split, normalize, etc)returns a uniformly distributed sphere.This is why I use recursive tesselation. The vertices will not be in a usable order this way, since the vertices will be in the order i create them.
I use: vector<cVec3> Verts;then: Vers.push_back(somevert);. 2 2 .. /\ /\ .. / \ 13/__\12 .. / \ /\ /\ .. 5/______\4 5/__14__\4 .. /\ /\ ... /\ /\ /\ ...etc. / \ / \ 8/__7/__11__\10 .. / \ / \ /\ /\ /\ /\ .. /______\/______\ /__\/__\/__\/__\ .. 0 3 1 0 6 3 9 1 .The solution can be this: Not tesselating recursively, using
the vertice order you proposed for the raycasting, but creating
and normalize the vertices in the right order.
EXAMPLE:
(since 3, 12 and 5 are parents of the rest)1 make vert 3, normalize...2 make vert 12, normalize...3 make vert 5, normalize...4 make rest.. 14 .. /\ .. 9 /__\13 .. /\ /\ .. 5/__8/__\12 .. /\ /\ /\ .. 2/__4/__7/__\11 .. /\ /\ /\ /\ .. /__\/__\/__\/__\ .. 0 1 3 6 10 .So when the grandchildren are made their parents are allready normalized. Now I still need a formula which gives me all the parents before their children before their grandchildren, etc. But for the order of verts you proposed (the one above).
This formula should work when i tesselate once, but also when i tesselate 10 times... Since the code should be flexible and my sphere class should be able to return spheres of different tesselation levels.
I'm back at my first problem... a magic formula to sort the vertices, only not for spiraling down, now for the ray casting...
Thanx a lot for all the help so far!
Marty
[Edited by - Marty666 on October 2, 2004 9:54:39 AM]
(Please try to reedit what's between the code tags, scrolling to read is no fun)
It's not a question of subspace, it's a question of inverse mapping if I understood your algo well enough :
Subspace :
I wonder if you are :
- either confused by the term subspace (infinite convex volume here). Then Google search.
- or you don't get the 3D picture well mentally.
- or I missed something in your explanations, but I doubt since the problem is well defined whatever the particularities of your algorithm.
The triangle in subspace 0 : X+,Y+,Z+, will have 3 edges split, 3 verts created still in S0, normalize still in S0, subdivide again still in S0, etc.. for any level of recursion. Else explain me how a child of the original triangle could ever have a negative x, y or z coordinate.
Thus the ray to subspace function is certain to work. This gives you which sub-mesh (eighth of the whole) you have to deal with.
Next there is still the ray to face index or ray to vertex index stuff. I understand you are concerned by your subdivision scheme. Your method is fine for the uniform subdivision side. But this prevents an obvious inverse mapping from (x,y,z) to grid indices (i, j) thus to index.
Still for any given level of subdivision, with your tesselation algo, there is obviously an inversible mapping. I am rather confident a simple formula exists.
A few considerations guide my intuition. Your algo is based on edge subdivision plus normalization, that is scaling from the center at 0. Thus the children of an edge always stay in the same plane given by the origin and the original edge. Such consecutive planes act like the coordinates you need, a bit like the classical longitude and latitude coords.
I think I could push it further and find the solution in the end. But please tell me more of the context where you need such an algo. If speed does not matter, then following your original idea of using the recursive structure may be enough.
[Edited by - Charles B on October 1, 2004 6:53:34 PM]
It's not a question of subspace, it's a question of inverse mapping if I understood your algo well enough :
Subspace :
I wonder if you are :
- either confused by the term subspace (infinite convex volume here). Then Google search.
- or you don't get the 3D picture well mentally.
- or I missed something in your explanations, but I doubt since the problem is well defined whatever the particularities of your algorithm.
The triangle in subspace 0 : X+,Y+,Z+, will have 3 edges split, 3 verts created still in S0, normalize still in S0, subdivide again still in S0, etc.. for any level of recursion. Else explain me how a child of the original triangle could ever have a negative x, y or z coordinate.
Thus the ray to subspace function is certain to work. This gives you which sub-mesh (eighth of the whole) you have to deal with.
Next there is still the ray to face index or ray to vertex index stuff. I understand you are concerned by your subdivision scheme. Your method is fine for the uniform subdivision side. But this prevents an obvious inverse mapping from (x,y,z) to grid indices (i, j) thus to index.
Still for any given level of subdivision, with your tesselation algo, there is obviously an inversible mapping. I am rather confident a simple formula exists.
A few considerations guide my intuition. Your algo is based on edge subdivision plus normalization, that is scaling from the center at 0. Thus the children of an edge always stay in the same plane given by the origin and the original edge. Such consecutive planes act like the coordinates you need, a bit like the classical longitude and latitude coords.
I think I could push it further and find the solution in the end. But please tell me more of the context where you need such an algo. If speed does not matter, then following your original idea of using the recursive structure may be enough.
[Edited by - Charles B on October 1, 2004 6:53:34 PM]
This topic is closed to new replies.
Advertisement
Popular Topics
Advertisement
