# finding vertex in sphere with a vector.

This topic is 5410 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

## Recommended Posts

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

##### Share on other sites
You can convert each vertex into polar coordinates, and do the sorting like that. it will be two float per vertex, that you can try to sort in a quad-tree, top speed up the search, or something.

void ToPolar(Vector V, float& phi, float& theta, float& r)
{
r = V.Magnitude();
Vector W = V / r;
phi = Asine(W.y); // elevation angle
theta = atan2(W.x, W.z); // roattion angle
}

Frankly, I would not do it that way though. If it's recursively tessalated, you can use the LODs you get from the recursion to pin down the closest points.

If you want to do ripples like water, I've got a wee demo of a sphere rippling. It was used for a shield effect in a game, a long time ago. It's quite basic though.

##### Share on other sites
I know about polar coordinates. But I don't like to give every vertex a polarcoordinate with it because of the memory it costs. I'd rather like the vertexes to be in a logical order (spiraling down for example). There should be a magic formula to be able to convert the indexes of a tesselated sphere to indexes spiraling down the sphere. I just can't figure it out
:( ...

I'm not going to do any dynamic LOD, because i'm going for the brute force approach. I've only got one sphere anyways.

Thanx,
Marty

##### Share on other sites
mmmm ok....

say you use polar coordinates (bear with me :))

so, elevation angle (latitude) goes from -90 to +90.

rotation angle (longitude) goes from 0 to 360.

so in theory, you can create a hash value for each vertex, like so

HashVal(Vertex) = Latitude(Vertex) * 360 + Longitude(Vertex);

so each vertex will be ordered in a spiral. Theoretically, you need 180 * 360 values, given that you allow a minimum of 1 degree separation between the vertices. that fits into a u_short.

##### Share on other sites
btw, if the sphere is built from polar coords (like the most basic usual way), the vertices will be ordered in a spiral anyway.

##### Share on other sites
k thanx, i might use that, but i still see a problems.

Since i've got 33000 vertexes and i want none of them having the same hash value i'll need more precision. The precision to choose is how many vertexes are at the equator. With 6 itterations it would be.... He, just thingking it's less than 360! Ok, next problem...

There will be missing hash values because there are more vertexes around the equator than over the longtitudes at the poles.
Then again, with this precision I could choose the closest hash value to the hash value of the direction vector i'm using.

Thanx! This'll work!

##### Share on other sites
I've got another approach now. I've got a 360*180 array if integers that represent the vertex indexes. For all my vertexes i calculate their place in the array and put them there. On the top of the sphere (near the poles) the array won't be completely filled, since there are less then 360 vertexes on that lattitude. The unfilled places in the array need to be filled with the closed vertexes. This'll take time when filling the array, but spare a lot of time when finding them, since i can just call array[259][23] to find the vertex at these angles. The problem is that for a nice shockwave all verts should go up and down. This way some will be missing since they're not in the array. I could use a larger array resolution, like 720*180 and calculate by half a degree, but i think this solution is not very elegant. I could also give every vertex the hash-number you were talking about and sort them by hash number (to make 'm spiraling down), but then it would still take a smart algorith to find the proper angle fast. Now i'll just have to run through all verts to find the hashnumber i'm looking for.

Hmmm. should be a nicer, more elegant, faster solution.

• 13
• 18
• 29
• 11