猫史档案馆

为什么现有的3D引擎都那么慢？

要回答这个问题，我们得先搞清楚现有的3D引擎的运转原理：

每一次渲染前都会重载一遍数据

遍历列表渲染

上面标红的字就是问题的关键

假设我们有n个立方体要渲染

要加载8n个顶点

使用插入排序来排序数据

由于我们已经知道了插入排序的时间复杂度是o(n^2)

而在添加时就要添加到对应位置

因此我们可以大体推导一下

t=n^2(插入排序)

R=t1+t2+t3+t4+...+tn

=>

R=[n  i = 1] ti

=>

R=[n i = 1] i^2

=>O([n i = 1] i^2)=O(N(N+1)(N+2)/3)

这种3D引擎的架构正是造成这样慢的时间复杂度

而这种架构叫做：重载数据架构

它的优点是：

简单，易于编写

缺点就是慢

当然，还有另一种架构

叫做：顶点缓存架构

时间复杂度是：O(N^2 (以内部排序算法为准))