sadyx
0.27D
V2EX  ›  问与答

求助,为什么我的 kd 树实际使用起来比暴力遍历还要慢(js)

  •  1
     
  •   sadyx · Sep 30, 2024 · 797 views
    This topic created in 614 days ago, the information mentioned may be changed or developed.

    场景

    threejs 场景下,新建一个顶点数量为 2000 * 2000 即 4000000 个顶点的 plane geometry ,在 plane 上放一个运动的盒子,不断地获取距盒子距离为 n 的所有顶点并进行染色。

    提供了两种方法:kd-tree 和 直接遍历。

    结果

    实际测试下来,直接遍历的帧数约为 40 ,而 kd-tree 的帧数只有 15 左右。

    疑问

    一开始以为是 kd-tree 实现的问题(实现算法也是自己写的),换了其他人写好的现成的库也是一样的结果。

    现在不太清楚到底是 kd-tree 算法的问题还是我实现的 kd-tree 代码出错

    代码

    预览(加载比较慢,因为创建 kd-tree 比较费时)

    threejs 代码

    kd 树代码

    No Comments Yet
    About   ·   Help   ·   Advertise   ·   Blog   ·   API   ·   FAQ   ·   Solana   ·   909 Online   Highest 6679   ·     Select Language
    创意工作者们的社区
    World is powered by solitude
    VERSION: 3.9.8.5 · 30ms · UTC 22:15 · PVG 06:15 · LAX 15:15 · JFK 18:15
    ♥ Do have faith in what you're doing.