c++ - 对我的绘图项目的建议

Question

我正在开发一个每 (.1) 秒更新一次对象列表的程序。程序完成更新列表后，程序将知道是否有任何对象在任何其他对象的特定距离内。每个对象在图形上都有一个 X、Y 位置。每个对象都有一个称为“范围”的值。每个刻度 (.1s) 程序将使用距离公式来计算是否有任何其他对象小于或等于正在处理的对象的范围。

例如，如果点 A 的范围为 4 且位于 (1,1)，而点 B 位于 (1,2)，则距离公式将返回 ~1，这意味着点 B 在点 A 的范围内. 计算结果类似于:

objects = { A = {X = 1,Y = 1,Range = 4}, B = {X = 1,Y = 2,Range = 3}, C = {X = 4,Y = 7,Range = 9} }

while(true) do
 for i,v in pairs(objects) do
   v:CheckDistance()
 end
wait()
end

-- Point:CheckDistance() calculates the distance of all other points from Point "self".
-- Returns true if a point is within range of the Point "self", otherwise false.
--

问题: 该图可能包含 200 多个点，每个点都会对存在的每个其他点应用数学。这将每 .1 秒发生一次。我想这可能会减慢我正在使用的 3D 环境或造成延迟。

问题: 这听起来像是执行此操作的最佳方法吗？ 对于如何更有效/更快地完成这项工作，您有什么想法？

Answer 1

作为Alex Feinamn说:看起来你正在制作自己的碰撞检测器，尽管是一个原始的。

不过，我不确定您是否在 2D 或 3D 平面上有点。您说每个对象“在图表上都有一个 X、Y 位置”，并进一步谈论“我正在使用的 3D 环境中的滞后”。

好吧，2D 和 3D 物理以及 Lua 都是发达的领域，因此不乏优化。

空间树

A quadtree (或 3D 的 octree)是一种数据结构，将您的整个 2 世界表示为一个分为四个正方形的正方形，每个正方形又分为四个正方形，依此类推。

您可以在 this handy site 上亲自体验交互式示例.

空间树通常可以非常快速地访问局部点。

圆圈表示特定粒子的相互作用半径。如您所见，很容易准确地找到需要遍历哪些分支。

在处理点云时，您需要确保两个点不共享同一位置，或者您的树有最大划分深度；否则，它将尝试无限地划分分支。

我不知道 Lua 中有任何八叉树的实现，但是制作一个很容易。如果您需要示例，请寻找 Python 或 C 实现；不要不要在 C++ 中寻找一个，除非你能处理模板疯狂。或者，您可以通过 Lua API 绑定(bind)或 FFI 库使用 C 或 C++ 实现(推荐，请参阅绑定(bind)部分)。

LuaJIT

LuaJIT是一个定制的 Lua 5.1 解释器和即时编译器，提供显着的速度和存储优化，以及一个 FFI 库，允许轻松高效地使用 C 函数和类型，例如整数。

使用 C 类型来表示您的点和空间树将显着提高性能。

local ffi = require"ffi"
ffi.cdef[[
    // gp = graphing project
    struct gp_point_s {
        double x, y;
        double range;
    };
    
    struct gp_quadtree_root_s {
        // This would be extensive
    };
    struct gp_quadtree_node_s {
        // 
    };
]]

gp_point_mt = {
    __add = function(a, b)
        return gp_point(a.x+b.x, a.y+b.y)
    end,
    __tostring = function(self)
        return self.x..", "..self.y
    end
    __index = {
        -- I couldn't think of anything you might need here!
        something = function(self) return self.range^27 end,
    },
}
gp_point = ffi.metatype("struct gp_point_s", gp_point_mt)

-- Now use gp_point at will

local p = gp_point(22.5, 5.4, 6)
print(p)
print(p+gp_point(1, 1, 0))
print(p:something())

LuaJIT 会将 gp_point 的任何运行时使用编译为 native 程序集，这意味着在某些情况下速度类似于 C。

Lua API 与 FFI

这是一个棘手的...

无法正确优化通过 Lua API 的调用，因为它们对 Lua 状态具有权威。而通过 LuaJIT 的 FFI 对 C 函数的原始调用可以得到完全优化。

由您决定您的代码应该如何互操作:

• 直接在脚本中(Lua，限制因素:动态语言只能在一定程度上优化)
• 脚本 -> 应用程序绑定(bind)(Lua -> C/C++，限制因素:Lua API)
• 脚本 -> 外部库(Lua -> C，限制因素:无，FFI 调用是 JIT 编译的)

增量时间

不是真正的优化，但它很重要。

如果您正在制作专为用户交互设计的应用程序，那么您不应该 fix your time step ;也就是说，您不能假设每次迭代都恰好需要 0.1 秒。相反，您必须将所有与时间相关的操作乘以时间。

pos = pos+vel*delta
vel = vel+accel*delta
accel = accel+jerk*delta
-- and so on!

但是，这是一个物理模拟；正如 Glenn Fiedler 所讨论的，物理学的固定时间步长和可变时间步长都存在明显的问题:

Fix your timestep or explode

... If you have a series of really stiff spring constraints for shock absorbers in a car simulation then tiny changes in dt can actually make the simulation explode. ...

如果您使用固定的时间步长，那么理论上每次都应该运行相同的模拟。如果你使用可变时间步长，它会非常平滑但不可预测。我建议问问你的教授。 (这是一个大学项目，对吧？)