Comments: Fast, Constant Time Sphere Indexing, Part 2

[dwilliamson]

http://donw.io/post/sphere-indexing-2/

[makc]

that seems pretty useful, but limited to particular geometry 😢 if I use different sphere mesh, I`m back to square 1.

[dwilliamson]

What do you mean by "use different sphere mesh" ?

[makc]

Just what it says - same object (sphere), different mesh (not octahedron-based, for example)

[dwilliamson]

Yeah, you've still lost me. See, this is a post about indexing the sphere into some arbitrary data set. My spheres are tessellated using Marching Cubes and so vary hugely from this post. However, I still use the technique in this post to index the same sphere to lookup light probes to blend between.

[Touhma]

How would you do the same kind of indexing but having the indexmap stored in an array ?

Like .. given a point on the sphere you get an index that get you a vertex point that is on the underlaying mesh ?

My take on that would be to iterate on all the vertices of the sphere & generate the index map but that give me an array with a lot of holes.

So let's say a sphere with 164k vertices. & you want to make an index map with like half the resolution. and when you hover on the sphere you snap on the vertices of the index map.

Hopefully it's clear. ^^" English is not my first language sorry.

[dwilliamson]

I do this for light probe lookup on a planet and it's pretty fast.

This should be your shader input:

struct Triangle
{
    // Vertex indices
    uint i0;
    uint i1;
    uint i2;
};

StructuredBuffer<Triangle> g_Triangles;

And then when you get the triangle index, you can find the specific vertex indices that make up that triangle:

uint tri_index = GetTriangleIndex(position);
Triangle probe_tri = g_Triangles[tri_index];

You then do a square-distance check to those 3 vertices to see which one is nearest. You can actually accelerate this step by precalculating some barycentric parameters and storing them in Triangle, reducing that distance check to 2 dots, 4 scalar muls and a few subtractions. But this is only useful if you're going to use those barycentrics for some other purpose at the same time, as the cost of bringing in more data will exceed the cost of a few more ALU instructions: I use those barycentrics for weighted interpolation of the probes at each vertex.

[Touhma]

Fuck me , I have not seen you answer, github don't notify me.

Thanks for the answer.

[Touhma]

Alright after a more in depth testing I think something is definitely wrong.

here is the thing :

https://imgur.com/a/ZLnqOPT

https://catlikecoding.com/unity/tutorials/procedural-meshes/octasphere/ --> Started from this with a multistream setup & the octasphere generator ( use the provided project & just use a unity shader doing the same as yours .( screen 2 ) )

That result in a perfect match between the mesh triangles & the shader color triangles seperation. ( screen 3 ) Resulting in 320k triangles for 161604 vertices

BUT ( screen 1 ) If i'm taking the centroids of the triangles it's giving me 320k differents indexes ( good ) but with a maximum value exceeding 320k ( screen 1 - red outline ) If i'm taking the vertices values i'm expecting it to give me 320k differents indexes but it's giving me instead less than that. ( orange outline )

To ensure that it's actually differents calculated indexes I did a 3rd test where i combine the 2 hashset & it's giving me past 320k indexes. ( screen 4, orange outline )

Conclusion : either I have a problem on my side or there is a problem in the way the indexes are calculated, not giving me indexes values from 0 to 320k to ensure any points are actually in each triangles.

( Screen 4 ) : the index seems to hit something each time but that don't explain why there are so much empty slots in the array & why it's not possible to get it to work without holes in the array ...

Can you confirm ? Am i doing something wrong ? Missing a step ?

[dwilliamson]

There's always going to be holes in the LUT as the per-octant indexing is just a 2D lookup into a square array that matches the longest side. The LUT can be compressed further but it makes the lookup much more complicated.

These numbers all sound quite overwhelming. Have you tried reducing the subdivision to see if this problem kicks in at a certain level, or is a problem at all subdivisions where it's easier to debug?

[Touhma]

Figured out what was the problem.

Now everything is working well.

"The LUT can be compressed further but it makes the lookup much more complicated."

How Complicated ? Can you give me an idea on that ?

Because at scales like that it's x4 impact on the memory instead of the cpu. I would rather hit the cpu than the memory for this kind of indexing.

[dwilliamson]

There's some text in the first article about packing entries closer together. I haven't researched further than that. If I was to go recursive and fine detail where needed I'd probably look at a hash.

[michaelsakharov]

@Touhma How did you fix the issue where the index returned was outside the range of triangles?

[Touhma]

Sorry mate , I did not see that comment. I don't remember what was the issue ^^' sorry ...