Replace cgmath and collision with nalgebra

[nnmm]

• nalgebra has an Isometry3 that can replace our hand-rolled Isometry3
• nalgebra does not provide an AABB type or something like cgmath::Perspective, so we add those ourselves.
• While we're at it, consistently use the Point3 type for point coordinates – this matches the intended semantics and gets rid of a bunch of conversions.

Criterion output against master (the octree queries will improve when we move to using Relation as opposed to a bool for intersection tests in an upcoming PR):

all_query_octree        time:   [25.687 ms 26.782 ms 28.270 ms]
                        change: [-3.5701% +1.8095% +7.7862%] (p = 0.53 > 0.05)
                        No change in performance detected.
Found 4 outliers among 100 measurements (4.00%)
  4 (4.00%) high severe

all_query_s2            time:   [19.869 ms 20.372 ms 20.974 ms]
                        change: [-1.0242% +2.5209% +6.2368%] (p = 0.17 > 0.05)
                        No change in performance detected.

box_query_octree        time:   [28.085 ms 28.390 ms 28.760 ms]
                        change: [-1.6742% +0.0614% +1.7783%] (p = 0.94 > 0.05)
                        No change in performance detected.

box_query_s2            time:   [20.913 ms 21.431 ms 22.051 ms]
                        change: [-0.3591% +3.5221% +7.3647%] (p = 0.07 > 0.05)
                        No change in performance detected.

frustum_query_octree    time:   [8.9604 ms 9.1048 ms 9.2342 ms]
                        change: [+1.9397% +4.2781% +6.7289%] (p = 0.00 < 0.05)
                        Performance has regressed.
Found 7 outliers among 100 measurements (7.00%)
  3 (3.00%) low mild
  3 (3.00%) high mild
  1 (1.00%) high severe

frustum_query_s2        time:   [1.9423 ms 2.2494 ms 2.6056 ms]
                        change: [+6.5215% +16.341% +26.731%] (p = 0.00 < 0.05)
                        Performance has regressed.
Found 13 outliers among 100 measurements (13.00%)
  5 (5.00%) low mild
  4 (4.00%) high mild
  4 (4.00%) high severe

obb_query_octree        time:   [18.768 ms 19.075 ms 19.410 ms]
                        change: [-5.5102% -3.4219% -1.4232%] (p = 0.00 < 0.05)
                        Performance has improved.
Found 1 outliers among 100 measurements (1.00%)
  1 (1.00%) high severe

obb_query_s2            time:   [10.984 ms 11.296 ms 11.594 ms]
                        change: [-2.8831% +0.3239% +3.7390%] (p = 0.86 > 0.05)
                        No change in performance detected.
Found 13 outliers among 100 measurements (13.00%)
  3 (3.00%) low severe
  4 (4.00%) low mild
  1 (1.00%) high mild
  5 (5.00%) high severe

cell_union_query_octree time:   [12.990 ms 13.454 ms 13.929 ms]
                        change: [-13.005% -9.8551% -7.0474%] (p = 0.00 < 0.05)
                        Performance has improved.

cell_union_query_s2     time:   [295.79 us 298.04 us 299.97 us]
                        change: [-26.297% -22.423% -19.211%] (p = 0.00 < 0.05)
                        Performance has improved.
Found 1 outliers among 100 measurements (1.00%)
  1 (1.00%) high severe

[krzesi-mir]

• nalgebra does not provide an AABB type or something like cgmath::Perspective, so we add those ourselves.

ncollide, which is part of the same suite as nalgebra, provides AABB type https://docs.rs/ncollide/0.14.1/ncollide/bounding_volume/struct.AABB.html

[nnmm]

True, I used that before, but ncollide is a very heavy dependency, if we're only going to use that, I don't think it's worth it. The Aabb struct is trivial.

[krzesi-mir]

True, I used that before, but ncollide is a very heavy dependency, if we're only going to use that, I don't think it's worth it. The Aabb struct is trivial.

Makes sense

[nnmm]

@feuerste Sorry, I indeed made merge errors. Git is dumber than I thought. I will double-check that after the next commit, this PR has all your changes.

[nnmm]

ptal @krzesi-mir @feuerste

[nnmm]

Just added some benchmarks to the description, performance improves a lot with this! Edit: That was measurement error, sorry. Performance is about the same overall.

[feuerste]

Do you know, why the frustum performance got worse?

[nnmm]

@feuerste re: Frustum performance, collision used an AABB intersection test based on intersection testing the box with all six faces. While this is maybe a bit faster, it's also inaccurate. I'd rather have a correct intersection test than the fastest one, and we can reduce the number of intersection tests anyway by returning the full Relation instead of a bool.

[nnmm]

I checked the number of points returned for all queries in point_cloud_test, they are the same before and after this change. Btw, check_box_query_equality returns all of the 1000000 points, so it's not a very good test.

[nnmm]

I built an octree from the same ply on master and this branch and compared the output.

• The number of files are the same
• The file names and their sizes are the same according to diff <(ls -1s octree | sort -k 2) <(ls -1s octree_nalgebra | sort -k 2)
• The metas are not the same

I'll look further into it.

[feuerste]

• The metas are not the same

One reason for this can be that the orders of items in the proto repeated fields are rarely the same.

[nnmm]

One reason for this can be that the orders of items in the proto repeated fields are rarely the same.

Yep, I'll check that next.

[nnmm]

So, they really are just permuted. And besides this, I also tested sdl_viewer, which works exactly like before (even feels a tad smoother).

I'll merge soon after I resolve the merge conflicts unless I'm hearing concerns.

[krzesi-mir]

🎉

[nnmm]

I tested xrays as well, found a small bug that is fixed with the latest commit.