vleue / polyanya

Pathfinding using Polyanya
Apache License 2.0
280 stars 20 forks source link

use a bvh for baking #13

Closed mockersf closed 2 years ago

mockersf commented 2 years ago

For an increase in baking, an improvement in finding a point in the mesh

group                                             bvh                         main
-----                                             ---                         ----
baking                                            1.34      6.0±0.09ms        1.00       4.5±0.05ms
get path Vec2(0.0, 0.0)-Vec2(0.0, 0.0)            1.00    193.9±3.98ns        68.77     13.3±0.14µs
get path Vec2(0.0, 0.0)-Vec2(575.0, 410.0)        1.00    192.8±2.37ns        68.98     13.3±0.18µs
get path Vec2(233.0, 323.0)                       1.00  1433.2±13.58µs        1.01   1444.3±19.30µs
get path Vec2(297.0, 438.0)-Vec2(575.0, 410.0)    1.00    503.6±4.31ns        114.02    57.4±0.63µs
get path Vec2(356.0, 166.0)                       1.00  1468.9±14.06µs        1.00   1475.0±24.24µs
get path Vec2(458.0, 47.0)-Vec2(575.0, 410.0)     1.00     14.6±0.13µs        1.50      21.9±0.22µs
get path Vec2(468.0, 584.0)                       1.00  1057.9±15.76µs        1.00   1059.4±25.57µs
get path Vec2(512.0, 170.0)                       1.00  1322.0±18.64µs        1.00   1327.2±11.61µs
get path Vec2(575.0, 410.0)-Vec2(0.0, 0.0)        1.00    375.9±5.92ns        45.22     17.0±0.20µs
get path Vec2(575.0, 410.0)-Vec2(458.0, 47.0)     1.00     10.8±0.09ms        1.01      10.8±0.10ms
get path Vec2(611.0, 658.0)                       1.00  1483.1±17.37µs        1.01   1497.4±23.48µs
get path Vec2(827.0, 678.0)                       1.00  1533.2±14.68µs        1.01   1542.3±23.38µs
get path Vec2(993.0, 290.0)                       1.00      2.8±0.02ms        1.00       2.9±0.02ms
is in mesh Vec2(131.0, 669.0)                     1.00    182.4±1.49ns        16.85      3.1±0.03µs
is in mesh Vec2(135.0, 360.0)                     1.00    156.3±1.25ns        4.84     757.1±6.08ns
is in mesh Vec2(22.0, 432.0)                      1.00    172.5±1.91ns        9.19   1584.3±15.51ns
is in mesh Vec2(308.0, 147.0)                     1.00    346.7±3.57ns        6.77       2.3±0.02µs
is in mesh Vec2(575.0, 410.0)                     1.00    188.3±2.01ns        17.95      3.4±0.03µs
is in mesh Vec2(728.0, 148.0)                     1.00    262.7±2.76ns        9.65       2.5±0.02µs
is not in mesh Vec2(0.0, 0.0)                     1.00    183.8±4.19ns        73.35     13.5±0.15µs
is not in mesh Vec2(297.0, 438.0)                 1.00    504.3±5.42ns        115.50    58.2±0.54µs
is not in mesh Vec2(521.0, 90.0)                  1.00   883.2±11.62ns        62.51     55.2±0.67µs
is not in mesh Vec2(726.0, 470.0)                 1.00    517.2±5.26ns        108.48    56.1±0.58µs
is not in mesh Vec2(969.0, 726.0)                 1.00    335.0±3.99ns        112.53    37.7±0.35µs