本文转载自MIT News，由ChatGPT翻译，图片来源于网络

在2024QS世界大学排名中，麻省理工学院荣获第1位

       1611年，以行星运动定律著称的约翰内斯·开普勒提出了一个解决方案，解决了如何以最密集的方式排列相等大小的球体的问题。

       当被问及如何堆放炮弹以占用最少的空间时，这位著名的天文学家研究了这个问题。

       开普勒得出的结论是一种所谓的面心立方格子结构，这种方法通常用于杂货店展示橙子：每个炮弹应该停留在由直接在其下方排列成紧密的2x2正方形的四个炮弹留下的空腔中。

       然而，这只是一个猜测，直到近400年后才被密歇根大学的一位数学家证明。

（训练师，你也不希望它们挤在箱子里吧）

       虽然这解决了关于均匀球体堆积的问题，但关于如何最优地放置大小和形状各异的3D物体的更普遍问题仍未解决。

       然而，有一些重大进展，不是以数学证明的形式，而是通过一种新的计算方法，使这个先前难以处理的任务更易处理。

       由麻省理工学院和位于马萨诸塞州梅德福德的研究人员组成的团队将这种技术称为“密集的、无嵌套且可扩展的光谱堆积”（SSP），团队将于2023年8月在世界上最大的计算机图形和交互技术会议SIGGRAPH 2023上展示该研究成果。

       SSP的第一步是确定用于填充固定容器的实体3D物体的顺序。例如，一种可能的方法是以最大的物体开始，以最小的结束。下一步是将每个物体放入容器中。

       为了促进这个过程，容器被“像素化”，这意味着它由微小的立方体或像素组成的3D网格表示，每个像素可能只有1毫米的立方体大小。该网格显示哪些部分的容器已经被填充，哪些是空的。

（对，它可以帮你塞得更满）

       要打包的物体也被像素化，再次由与容器中的像素大小相同的立方体组成。为了确定该物体的可用空间，算法然后在每个像素处计算一个称为碰撞度量的量。

       它通过将物体的中心放置在容器的每个像素处，然后计算物体与之重叠或“碰撞”的占用像素的数量。该物体只能放置在重叠为零——即没有“碰撞”的位置。

（很多游戏中的伤害判定也是“碰撞”）

       SSP算法的关键优势在于，它可以轻松地适用于不同大小和形状的物体，以及不同形状和大小的容器。

       此外，该算法可以通过添加更多的物体和容器来扩展，因此它是可扩展的。最后，该算法可以在合理的时间内执行，因为它采用了高度并行化的方法和快速近似计算的技术。

       这种新的计算方法为许多应用程序提供了方便，例如在制造业中进行3D打印和装载运输容器。

       此外，SSP算法还可以用于游戏开发、虚拟现实、建筑设计和城市规划等领域，以帮助设计师和工程师优化空间使用，同时保证物体的最佳布局。

（为什么不问问万能的神奇妈妈呢？）