search

gkjohnson / three-mesh-bvh

A BVH implementation to speed up raycasting and enable spatial queries against three.js meshes.
https://gkjohnson.github.io/three-mesh-bvh/example/bundle/raycast.html
MIT License
2.5k stars 261 forks source link

Parallel Worker Construction #627

Closed gkjohnson closed 8 months ago

gkjohnson commented 8 months ago

Related to #296

2-4x faster construction times

Notes

TODO

Upcoming

gkjohnson commented 8 months ago

Performance notes:

gkjohnson commented 8 months ago

Make some progressive buildTree changes to the main branch to avoid all the added complexities

BVH General before after delta increase
Desrialize
*  median 0.10262 ms 0.10646 ms 0.00383 ms 3.73594 %
BVH Casts before after delta increase
Raycast First Hit Shapecast
*  mean 0.00566 ms 0.00811 ms 0.00245 ms 43.33364 %
BVH Misc before after delta increase
Compute Bounds w/o
*  mean 1.01377 ms 1.04972 ms 0.03595 ms 3.54570 %
*  median 1.00585 ms 1.05067 ms 0.04481 ms 4.45517 %
Indirect BVH Casts before after delta increase
Raycast First Hit
*  mean 0.00392 ms 0.00439 ms 0.00047 ms 12.11259 %
IntersectsSphere
*  median 0.00108 ms 0.00133 ms 0.00025 ms 22.96019 %
Indirect BVH Misc before after delta increase
Compute Bounds
*  mean 0.00017 ms 0.00019 ms 0.00001 ms 7.77323 %
*  median 0.00013 ms 0.00017 ms 0.00004 ms 33.33333 %
Math Functions before after delta increase
IntersectTri w/o Target
*  mean 0.00024 ms 0.00027 ms 0.00003 ms 12.11392 %
IntersectTri w/ Target
*  mean 0.00049 ms 0.00052 ms 0.00003 ms 5.58734 %
*  median 0.00046 ms 0.00050 ms 0.00004 ms 9.16189 %
IntersectTri w/ Update
*  mean 0.00058 ms 0.00063 ms 0.00005 ms 8.92690 %
*  median 0.00058 ms 0.00062 ms 0.00004 ms 7.19836 %
Tower Case Geometry before after delta increase
AVERAGE raycast
*  mean 0.00170 ms 0.00218 ms 0.00048 ms 28.29104 %
Full Benchmark **BVH General** | | before | after | delta | increase | |---|---|---|---|---| | Serialize | | | | | |    mean | 0.85835 ms | 0.64992 ms | -0.20844 ms | -24.28317 % | |    median | 0.66940 ms | 0.57679 ms | -0.09260 ms | -13.83406 % | | Desrialize | | | | | |    mean | 0.10469 ms | 0.10769 ms | 0.00301 ms | 2.87325 % | | *  median | 0.10262 ms | 0.10646 ms | 0.00383 ms | 3.73594 % | **BVH Casts** | | before | after | delta | increase | |---|---|---|---|---| | Compute BVH | | | | | |    mean | 117.01649 ms | 113.31586 ms | -3.70063 ms | -3.16249 % | |    median | 117.14846 ms | 113.11729 ms | -4.03117 ms | -3.44107 % | | Compute BVH w/ groups | | | | | |    mean | 124.02749 ms | 106.93533 ms | -17.09216 ms | -13.78095 % | |    median | 122.95490 ms | 106.64929 ms | -16.30560 ms | -13.26145 % | | Raycast | | | | | |    mean | 0.05610 ms | 0.05538 ms | -0.00072 ms | -1.28089 % | |    median | 0.05233 ms | 0.05150 ms | -0.00083 ms | -1.59180 % | | Raycast Shapecast | | | | | |    mean | 0.08306 ms | 0.08294 ms | -0.00012 ms | -0.14140 % | |    median | 0.07875 ms | 0.07863 ms | -0.00013 ms | -0.15879 % | | Raycast First Hit | | | | | |    mean | 0.00498 ms | 0.00453 ms | -0.00044 ms | -8.88366 % | |    median | 0.00492 ms | 0.00483 ms | -0.00008 ms | -1.66836 % | | Raycast First Hit Shapecast | | | | | | *  mean | 0.00566 ms | 0.00811 ms | 0.00245 ms | 43.33364 % | |    median | 0.00587 ms | 0.00583 ms | -0.00004 ms | -0.69802 % | | Sphere Shapecast | | | | | |    mean | 0.00188 ms | 0.00190 ms | 0.00002 ms | 1.05748 % | |    median | 0.00183 ms | 0.00187 ms | 0.00004 ms | 2.23609 % | | IntersectsSphere | | | | | |    mean | 0.00182 ms | 0.00188 ms | 0.00005 ms | 2.92940 % | |    median | 0.00192 ms | 0.00192 ms | -0.00000 ms | -0.03731 % | | IntersectsBox | | | | | |    mean | 0.00674 ms | 0.00564 ms | -0.00110 ms | -16.32497 % | |    median | 0.00462 ms | 0.00460 ms | -0.00002 ms | -0.45108 % | | DistanceToGeometry w/ BVH | | | | | |    mean | 82.46630 ms | 82.53429 ms | 0.06799 ms | 0.08245 % | |    median | 82.42754 ms | 82.46969 ms | 0.04215 ms | 0.05113 % | | DistanceToPoint | | | | | |    mean | 0.07498 ms | 0.07419 ms | -0.00079 ms | -1.05487 % | |    median | 0.07250 ms | 0.07242 ms | -0.00008 ms | -0.11444 % | | IntersectsGeometry w/ BVH | | | | | |    mean | 2.12904 ms | 2.15385 ms | 0.02481 ms | 1.16547 % | |    median | 2.11329 ms | 2.13583 ms | 0.02254 ms | 1.06670 % | | IntersectsGeometry w/o BVH | | | | | |    mean | 32.69535 ms | 33.03721 ms | 0.34186 ms | 1.04560 % | |    median | 32.58929 ms | 32.93871 ms | 0.34942 ms | 1.07218 % | | BVHCast | | | | | |    mean | 52.87328 ms | 53.55730 ms | 0.68401 ms | 1.29369 % | |    median | 52.72752 ms | 53.37208 ms | 0.64456 ms | 1.22244 % | **BVH Misc** | | before | after | delta | increase | |---|---|---|---|---| | Refit | | | | | |    mean | 11.37539 ms | 11.34165 ms | -0.03375 ms | -0.29667 % | |    median | 11.34383 ms | 11.31933 ms | -0.02450 ms | -0.21598 % | | Refit with Hints | | | | | |    mean | 0.37976 ms | 0.38946 ms | 0.00969 ms | 2.55250 % | |    median | 0.37917 ms | 0.38879 ms | 0.00963 ms | 2.53864 % | | Compute Bounds | | | | | |    mean | 0.00019 ms | 0.00017 ms | -0.00003 ms | -13.37474 % | |    median | 0.00017 ms | 0.00017 ms | 0.00000 ms | 0.00000 % | | Compute Bounds w/o | | | | | | *  mean | 1.01377 ms | 1.04972 ms | 0.03595 ms | 3.54570 % | | *  median | 1.00585 ms | 1.05067 ms | 0.04481 ms | 4.45517 % | **Indirect BVH Casts** | | before | after | delta | increase | |---|---|---|---|---| | Compute BVH | | | | | |    mean | 110.89948 ms | 106.84445 ms | -4.05502 ms | -3.65649 % | |    median | 111.46663 ms | 106.62667 ms | -4.83996 ms | -4.34207 % | | Compute BVH w/ groups | | | | | |    mean | 128.60765 ms | 121.38177 ms | -7.22588 ms | -5.61854 % | |    median | 127.45162 ms | 121.05188 ms | -6.39975 ms | -5.02132 % | | Raycast | | | | | |    mean | 0.05996 ms | 0.06057 ms | 0.00061 ms | 1.01652 % | |    median | 0.05842 ms | 0.05863 ms | 0.00021 ms | 0.35794 % | | Raycast Shapecast | | | | | |    mean | 0.07882 ms | 0.08096 ms | 0.00214 ms | 2.71794 % | |    median | 0.07550 ms | 0.07575 ms | 0.00025 ms | 0.33094 % | | Raycast First Hit | | | | | | *  mean | 0.00392 ms | 0.00439 ms | 0.00047 ms | 12.11259 % | |    median | 0.00404 ms | 0.00413 ms | 0.00008 ms | 2.08272 % | | Raycast First Hit Shapecast | | | | | |    mean | 0.00354 ms | 0.00354 ms | 0.00001 ms | 0.18657 % | |    median | 0.00329 ms | 0.00329 ms | -0.00000 ms | -0.00724 % | | Sphere Shapecast | | | | | |    mean | 0.00150 ms | 0.00150 ms | 0.00001 ms | 0.51138 % | |    median | 0.00163 ms | 0.00163 ms | 0.00000 ms | 0.00000 % | | IntersectsSphere | | | | | |    mean | 0.00132 ms | 0.00132 ms | -0.00000 ms | -0.02295 % | | *  median | 0.00108 ms | 0.00133 ms | 0.00025 ms | 22.96019 % | | IntersectsBox | | | | | |    mean | 0.00162 ms | 0.00164 ms | 0.00002 ms | 1.41505 % | |    median | 0.00158 ms | 0.00158 ms | 0.00000 ms | 0.00000 % | | DistanceToGeometry w/ BVH | | | | | |    mean | 82.48547 ms | 82.70101 ms | 0.21554 ms | 0.26131 % | |    median | 82.40660 ms | 82.66546 ms | 0.25885 ms | 0.31412 % | | DistanceToPoint | | | | | |    mean | 0.07980 ms | 0.07981 ms | 0.00001 ms | 0.01118 % | |    median | 0.07788 ms | 0.07733 ms | -0.00054 ms | -0.69620 % | | IntersectsGeometry w/ BVH | | | | | |    mean | 2.25026 ms | 2.24816 ms | -0.00210 ms | -0.09345 % | |    median | 2.22865 ms | 2.23373 ms | 0.00508 ms | 0.22813 % | | IntersectsGeometry w/o BVH | | | | | |    mean | 33.38231 ms | 33.65025 ms | 0.26795 ms | 0.80266 % | |    median | 33.29504 ms | 33.49475 ms | 0.19971 ms | 0.59982 % | | BVHCast | | | | | |    mean | 53.53602 ms | 54.25790 ms | 0.72188 ms | 1.34840 % | |    median | 53.30383 ms | 53.89179 ms | 0.58796 ms | 1.10303 % | **Indirect BVH Misc** | | before | after | delta | increase | |---|---|---|---|---| | Refit | | | | | |    mean | 12.80377 ms | 12.83093 ms | 0.02716 ms | 0.21214 % | |    median | 12.75117 ms | 12.78317 ms | 0.03200 ms | 0.25096 % | | Refit with Hints | | | | | |    mean | 0.43600 ms | 0.43510 ms | -0.00090 ms | -0.20666 % | |    median | 0.43548 ms | 0.43433 ms | -0.00115 ms | -0.26318 % | | Compute Bounds | | | | | | *  mean | 0.00017 ms | 0.00019 ms | 0.00001 ms | 7.77323 % | | *  median | 0.00013 ms | 0.00017 ms | 0.00004 ms | 33.33333 % | | Compute Bounds w/o | | | | | |    mean | 1.01831 ms | 1.03612 ms | 0.01781 ms | 1.74933 % | |    median | 1.01183 ms | 1.04042 ms | 0.02858 ms | 2.82488 % | **Math Functions** | | before | after | delta | increase | |---|---|---|---|---| | IntersectTri w/o Target | | | | | | *  mean | 0.00024 ms | 0.00027 ms | 0.00003 ms | 12.11392 % | |    median | 0.00025 ms | 0.00025 ms | 0.00000 ms | 0.09542 % | | IntersectTri w/ Target | | | | | | *  mean | 0.00049 ms | 0.00052 ms | 0.00003 ms | 5.58734 % | | *  median | 0.00046 ms | 0.00050 ms | 0.00004 ms | 9.16189 % | | IntersectTri w/ Update | | | | | | *  mean | 0.00058 ms | 0.00063 ms | 0.00005 ms | 8.92690 % | | *  median | 0.00058 ms | 0.00062 ms | 0.00004 ms | 7.19836 % | **Tower Case Geometry** | | before | after | delta | increase | |---|---|---|---|---| | CENTER raycast | | | | | |    mean | 0.00405 ms | 0.00402 ms | -0.00003 ms | -0.74337 % | |    median | 0.00421 ms | 0.00417 ms | -0.00004 ms | -0.98306 % | | AVERAGE raycast | | | | | | *  mean | 0.00170 ms | 0.00218 ms | 0.00048 ms | 28.29104 % | |    median | 0.00158 ms | 0.00163 ms | 0.00004 ms | 2.65060 % | | SAH raycast | | | | | |    mean | 0.00655 ms | 0.00483 ms | -0.00172 ms | -26.28950 % | |    median | 0.00433 ms | 0.00433 ms | 0.00000 ms | 0.00000 % |