Open xiaoiver opened 4 years ago
力导布局算法中会用到 quadtree。例如 G6 中使用了 d3-force,在其中碰撞力和多体力中都有用到这个空间索引数据结构。
d3-force
但是当我们尝试移植该布局算法到 Shader 中,会发现 Shader 中是没法使用对象的。我们必须找到一种更高效、扁平化的 quadtree 存储方式。
早在 1982 年,「An Effective Way to Represent Quadtrees」 https://www.csee.usf.edu/~tuy/Literature/QTree-Represent-CACM82.pdf
后续有很多基于此算法做的应用,例如:
问题背景
力导布局算法中会用到 quadtree。例如 G6 中使用了
d3-force
,在其中碰撞力和多体力中都有用到这个空间索引数据结构。但是当我们尝试移植该布局算法到 Shader 中,会发现 Shader 中是没法使用对象的。我们必须找到一种更高效、扁平化的 quadtree 存储方式。
Linear Quadtree
早在 1982 年,「An Effective Way to Represent Quadtrees」 https://www.csee.usf.edu/~tuy/Literature/QTree-Represent-CACM82.pdf
后续有很多基于此算法做的应用,例如: