search

mattrdowney / planetaria

A Unity framework for Euclidean 2-sphere games (e.g. 2D virtual reality games) [quasi-MIT license]
Other
10 stars 2 forks source link

PlanetariaGrid #88

Open mattrdowney opened 6 years ago

mattrdowney commented 6 years ago

Takes a planetarium mesh (a group of normalized points) and finds the closest point for vertex snapping. Rendering the grid draws lines between adjacent vertices (drawing all edges).

mattrdowney commented 5 years ago

A good implementation for clustering arbitrary points for grid snapping would be bounding volume hierarchies - ensuring O(log2(n)) retrieval.

You would still need an index/pointer into the Mesh data structure so you can do edge snapping.

mattrdowney commented 5 years ago

Actually, wouldn't there be issues if a poor bisecting plane were chosen? I don't think there are guarantees a good bisecting plane exists either.

mattrdowney commented 5 years ago

You could do bounding volume hierarchy to graph search using the nearest point on convex mesh algorithm (which is probably O(~V^(1/2)))

mattrdowney commented 5 years ago

Partially a repeat of #101.

The grid structure also entails rendering.

mattrdowney commented 5 years ago

Bounding volume hierarchy construction is more interesting.

You would basically need to do binary search on [-1, +1] range (which is an abstraction because you need to check along an axis e.g. x/y/z/composite). An easy implementation would bisect along x/y/z in turn, since continually bisecting the x axis would not work as well.

Additionally, you only need to bisect from [min, max] not [-1, +1] if you wanted to optimize further.