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

Binary Tree PlanetariaCollider #136

Open mattrdowney opened 5 years ago

mattrdowney commented 5 years ago

The main idea is you create a bounding sphere for each arc, and then recursively combine them (in a preprocessing stage, usually in editor-time) two sets at a time.

It is bounding volume hierarchies with some minor changes.

When trying to find the closest collision, you can discard certain bounding spheres (unfortunately I don't think this is O(log2(n)) in the best case, just some typical cases).

This would probably be stored in NativeArrays in the new Entity-Component System (because using Entities would involve 1) a lot of objects (sort of like creating an object per each triangle), 2) difficulty in dealing with the base case versus the recursive case, and 3) a lot of cache incoherence

mattrdowney commented 5 years ago

I just learned about optimal binary search trees, and I think the concept should be integrated at some point (although I'll have to decide how the probability distribution works -- most likely via the length of the arc).

The first version should definitely use a simple bounding volume/sphere hierarchy, and later I can focus on optimizations like this (through refactoring).