algorithm - 碰撞检测复杂度

转载 作者：塔克拉玛干 更新时间：2023-11-03 03:45:06 32 4

我有大量的物体(首先是球)在空间中逐步移动，一次一个，并且不应重叠。目前，对于每一个 Action ，我都会检查是否与其他所有对象发生碰撞。 Several other questions here然而，处理这个问题时，我想到了一个看似简单的解决方案，但在这种情况下似乎并没有出现，我想知道为什么。

为什么不简单地保留所有对象的 2 个集合(对于 2D，或 3 个在三维中)，分别按 x 和 y(和 z)坐标排序，并在每次移动时查找给定距离内的所有其他对象(这里的球直径)在每个维度上，只对两个(或所有 3 个)结果集中的对象进行实际碰撞检查？

我意识到这只适用于大小相同的对象，但也可以使用两倍数量的集合，按每个对象每个维度的 (1) 最高 (2) 最低坐标排序。与从 O(n)“成对检查”到“grid method”或“四叉树/八叉树”相比，为什么这不起作用，或者提供的改进少得多？我在这里看到这些排序集合的更新是昂贵的操作，但是使用例如一个 TreeSet(我的实现将在 Java 中)它应该仍然明显小于 O(n)，对吗？

最佳答案

检查两个结果集中有哪些对象涉及查看平面两 strip 中的所有对象。这是一个更大的区域，因此涉及更多的对象，而不是四叉树让您立即缩小范围的封闭正方形。更多的对象意味着它更慢。

关于algorithm - 碰撞检测复杂度 <O(n²) : Simpler approach than grid, 四叉树，BSP？，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/6139011/

32 4 0

• c++ - BSP 树是否适用于单个透明对象？

  我一直在尝试实现三维 BSP 树来呈现透明的单个对象(立方体、带有圆柱体的盒子等)。据我所知，这应该有效，但事实并非如此，我也不知道为什么。我读过的所有内容都涉及在二维或多个对象上使用的 BSP 树，

• c++ - 从预建的 BSP 树渲染？

  大家好。我正在将预建的 BSP 树加载到内存中，但我很困惑。它被用于第一人称探索程序。你如何推荐我使用已经制作好的 BSP 树。我知道我遍历了这棵树，但我要寻找什么？ 对不起我的英语。 最佳答案 您的

• c - STM32CubeF7 BSP LCD尝试

  我正在尝试使用来自 STM32CubeF7 的 BSP 库在 stm32f769i-disco 的 LED 上显示一个字符串。但是，没有任何反应。这是代码: #include "stm32f7xx_h

• algorithm - 如何测试给定的 BSP 树是否最优？

  我有一个三角形的多边形汤，我想为其构建一个 BSP 树。我当前的程序只是通过一次从模型中插入一个随机三角形来构建 BSP 树，直到消耗完所有三角形，然后它检查树的深度和广度并记住它获得的最佳分数(最低

• c++ - 我是否错误地渲染了 BSP 树？

  我有一个 BSP 树加载到内存中。我首先找出我所在的叶子。接下来，我解码 PVS。然后，我遍历该 PVS 中的每个区域，看看它是否位于我的截锥体内。 有人告诉我这是不正确的渲染方式，我实际上应该通过遍

• java - Hama BSP 中此作业的运行时分区失败

  开始运行 hama BSP 作业时遇到以下问题。当 hama 在实际运行我自己的代码之前尝试加载和分区输入数据时，会发生此异常。这是一些网站中讨论的已知问题，但不幸的是没有已知原因(例如，参见 her

• c++ - 从原始数据生成 BSP 树

  我知道如何使用带有旧 3d 关卡(如 Quake 等)的预建 BSP 树，甚至还编写了一个关卡渲染器。现在，我将进入下一步，实际上是自己构建 BSP 树。我知道它背后的过程，但我想知道是否有人有任何建

• c++ - 需要帮助组织 BSP 几何渲染的类型差异

  我目前正在尝试将另一种格式转换为 Quake 3 BSP 格式。 Quake 格式包括顶点、面、索引和纹理。 根据我必须处理的信息: 我有顶点，它们是 x、y 和 z 位置的 3 个浮点结构。 我有可

• three.js - 有没有人有 BSP 的例子？

  有没有人有在 ThreeJS 中使用 BSP 树的例子，他们可以分享或了解？我正在考虑创建地形 splatting 示例，并希望使用 BSP(或者八叉树...？)来帮助加快渲染速度。 非常感谢 最佳答

• linux-device-driver - BSP 与设备驱动程序

  虽然单独理解每一个(或者可能不理解)，但看起来我远未理解两者之间的实际差异。 根据我的理解，BSP 是一个驱动程序和配置设置包，它允许内核镜像启动板(并且是板的一部分)。 单个设备驱动程序在特定组件

• embedded - Yocto 中的 BSP 和分布层有什么区别

  您能否简单解释一下什么是 BSP 和分发层以及它们之间的区别是什么？ 实际上，我并不是在寻找 Yocto 项目手册引用，但很高兴得到您理解的解释，用您的话来说。 最佳答案 好吧，不管你有什么要求，手册

• c++ - BSP 和 MPI 有什么区别？

  BSP 和 MPI 有什么区别？ 我知道Pregel's图计算框架基于BSP。为什么他们不直接使用MPI或者基于MPI开发一个框架？ 最佳答案 Bulk Synchronous Parallel (B

• python - 在 Python 中运行批量同步并行模型 (BSP)

  BSP 并行编程模型有几个好处 - 程序员无需明确关心同步，死锁变得不可能，速度推理比传统方法更容易。 SciPy 中有一个 BSPlib 的 Python 接口(interface): import

• CSS3 在 SAP BSP 中不起作用

  我正在尝试在我的 bsp 应用程序中使用 css3 样式(如 border-radius、box-shadow)。但是这些新样式在 BSP 中没有应用。我也尝试过替换 BSP 标签。但是现有的元素(如

• linux - 找不到 yocto-bsp 命令

  我目前正在玩 yocto，想为树莓派创建一个特定的 BSP(学习练习，所以不想使用提供的 meta-rpi 层)。 手册告诉我输入命令“yocto-bsp help”，但我的系统说找不到该命令。 我已

• ios - BSP Dungeon Generator 出现无法修复的错误

  我正在翻译 this ActionScript tutorial将二进制空间划分为 Swift，这样我就可以在我的 rogue-like 游戏中使用它。我遇到了一个障碍。 在文章中，作者这样初始化他的

• java - 哈马 BSP 的异常(exception)情况

  在实际运行我的 BSP 作业之前，我的 hama 在输入数据分区阶段抛出以下异常。我可以知道此异常的可能根本原因是什么吗？任何有关如何找出根本原因的建议都将受到赞赏。谢谢! 13/11/06 03:5

• c - RAM_HIGH_ADRS 在 VxWorks BSP 中的真正含义是什么？

  RAM_HIGH_ADRS 是在 config.h 和 makefile 中定义的参数。据我了解，它定义了程序的数据+文本+bss段将写入RAM的地址。 这意味着，例如，如果 cpu 有 64 Mb

• c - Sieve Of Eratosthenes BSP C 实现没有找到所有素数

  我有一个 C 语言的 BSP 实现，用于 Erastothenes 筛法，请参见下面的代码。 当使用 ./bspsieve 2 100 执行时，它会给出以下输出: “2 次中的 0 次触发花费了 0.

• linux - 英特尔伽利略 BSP Quark_EDKII 错误 4063

  构建 EDKII 固件 ./buildallconfigs.sh GCC44 QuarkPlatform 我得到下面列出的错误 在遇到障碍并且不知道去哪里之后有人有什么想法吗？ 正在运行 python