Does anyone know of any code laying around the net that distributes points on a mesh in a blue noise distribution?
A student intern i work with is looking for this. It's tempting to write it, but im also kinda swamped :X
@demofox a lot of renderers are already doing this.
render the mesh, sample blue noise texture, project passing samples to world space using depth buffer the usual way.
added step: use inverse model matrix to project to local space, throw result into a uav with interlocked add.
@lritter well i can choose a triangle uniform randomly based on size, and can uniformly generate a point in a triangle.
That'd give you candidates for MBC.
But now you have to calculate distance between points :/
@breakin@lritter you still need distance between points on mesh for lloyd relaxation. im more a fan of MBC, but they both have the requirement of needing to be able to calculate distance between points on a mesh, which makes it a longer task hehe
@demofox@lritter Maybe distance can be done in 3d if you are going for high point density but still not easy. Maybe generate many points using white noise and then just remove close ones is easiest.
@breakin@lritter if dense enough, yeah, i bet you could just deal with points within a triangle and the immediate neighbors. I think this is all solvable but not ~1 hour of work haha. sigh...
@demofox@lritter nope! Lots of code! If you have tooling do uv-unwrap, spread points blue in uv space and profit? Like project them back. Not perfect but maybe doable.
@breakin oh yeah, that's true. not good enough for me. sorry for posing an unsolvable problem. Was just hoping some code existed somewhere hehe. TinyOBJ + mitchell's best candidate.
approximate geodesic distances over the entire mesh, then get the parameterization from an eigenvalue problem (only first two largest), it's close to isometric but not conformal
@mmby@breakin eesh, i wish this problem was simpler hehe.
finding the distance between 2 points on a mesh doesn't SOUND that hard. but then you think of the details and urgh...
@demofox@mmby I'm thinking that if you only need to figure out if a point should be removed, then you "only" need to find distance with all triangles that are inside a sphere. If you have connectivity making some shortest-path algorithm shouldn't be that hard. But yeah yuck.
@breakin@mmby the hardest problem i can see with the "shortest path between points on mesh" is: what is the straight line as you move between triangles that go concave, convex etc. am i overthinking that? it sounds hard.
The "which triangles should i take to go the shortest path" maze solving seems easier at least.
@breakin it specifically mentions being able to make a voronoi diagram and using Lloyd relaxation to optimize the point sets, which is an algorithm for making blue noise point sets.
I think this is the winner.
Thanks a lot! https://github.com/BrunoLevy/geogram/wiki/Delaunay2D
Mitchell's best candidate would work well here, and would give a sequence instead of a set (use the first N of M total points, for any N), but what makes it more than a 1 hour task is the mesh connectivity, and multiple paths through triangles to the same points that you need to calculate distance between.
@demofox haven't tried in practice, so might be suboptimal, but I am pretty sure it would be "correct": I would probably do 3D Mitchel's best candidate on some conservative voxel grid around the mesh, then take only points closer to a surface than some epsilon and project them onto surface (can be done as gather, not scatter). But it depends if you want the blue noise with geodesic distance (surface connectivity) or 3D. For most meshes (convex or locally almost convex), should be ~similar.
Add comment