如何生成无相交的随机Cuboid数组？寻求非暴力校验方案

需求背景 #

在3D空间中生成一组无相交的随机长方体（Cuboid），已知约束条件：

• 长方体的最小/最大宽、高、深尺寸
• 长方体中心位置范围为(0,1)区间内

当前已实现暴力生成逻辑：生成随机长方体后，与已有长方体逐一校验相交性，无相交则加入数组。但该方案依赖大量随机尝试，效率较低，需寻求更优实现方式。

已实现的相交校验及暴力生成代码 #

相交校验代码 #

bool cuboid::point_intersects(Vec3 a, Cuboid b) {
  Vec3 dimensions = {b.width, b.height, b.depth};
  for (unsigned int i = 0; i < 3; i++) { // x,y,z
    if (!(a[i] <= b.center[i] + dimensions[i] &&
          a[i] >= b.center[i] - dimensions[i])) {
      return false;
    }
  }
  return true;
}

bool cuboid::intersects(Cuboid a, Cuboid b) {
  Vec3 a_points[8];
  Vec3 b_points[8];
  cuboid::assign_vertices(a, a_points);
  cuboid::assign_vertices(b, b_points);
  for (unsigned int i = 0; i < 8; i++) {
    if (cuboid::point_intersects(a_points[i], b)) {
      return true;
    }
    if (cuboid::point_intersects(b_points[i], a)) {
      return true;
    }
  }
  return false;
}

bool cuboid::intersects_with_vector(std::vector<Cuboid> cuboids, Cuboid a) {
  for (Cuboid c : cuboids) {
    if (cuboid::intersects(a, c))
      return true;
  }
  return false;
}

暴力生成逻辑示例 #

#include "cuboid.h"
#include "vector3.h"

#include <ctime>
#include <iostream>
#include <random>
#include <vector>

#define MIN_WIDTH 0.01
#define MAX_WIDTH 0.2

#define MIN_HEIGHT 0.01
#define MAX_HEIGHT 0.2

#define MIN_DEPTH 0.01
#define MAX_DEPTH 0.2

#define NUM_ROOMS 12

int main() {
  std::mt19937 mt(time(nullptr));
  std::vector<Cuboid> rooms = {};
  rooms.push_back(cuboid::random_cuboid(MIN_WIDTH, MAX_WIDTH, MIN_HEIGHT,
                                        MAX_HEIGHT, MIN_DEPTH, MAX_DEPTH, &mt));
  for (unsigned int i = 0; i < NUM_ROOMS - 1; i++) {
    Cuboid c = cuboid::random_cuboid(MIN_WIDTH, MAX_WIDTH, MIN_HEIGHT,
                                     MAX_HEIGHT, MIN_DEPTH, MAX_DEPTH, &mt);
    while (cuboid::intersects_with_vector(rooms, c)) {
      c = cuboid::random_cuboid(MIN_WIDTH, MAX_WIDTH, MIN_HEIGHT, MAX_HEIGHT,
                                MIN_DEPTH, MAX_DEPTH, &mt);
    }
    rooms.push_back(c);
  }
  for (Cuboid c : rooms) {
    std::cout << c << std::endl;
  }
  return 0;
}

优化实现方案 #

1. 空间划分加速校验（减少碰撞检测次数） #

暴力方案中每次生成新长方体都要遍历所有已有几何体，可通过空间划分数据结构优化：

• 八叉树（Octree）：将整个(0,1)³空间递归划分为8个子区域，每个区域存储其中的长方体。生成新长方体时，仅需检查其所在区域及相邻区域内的已有长方体，大幅减少碰撞检测的次数。
• 网格划分：将空间划分为固定大小的3D网格，每个网格单元记录包含的长方体。生成新长方体时，仅检查其覆盖的网格单元内的几何体。

2. 基于间隙的生成法（直接在合法区域生成） #

不再随机生成后校验，而是直接在已有长方体之间的空隙中生成新的长方体：

1. 维护当前空间中所有未被占用的“空闲区域”（可用轴对齐的长方体表示）。
2. 每次生成新长方体时，从空闲区域中随机选择一个，在该区域内随机生成符合尺寸约束的长方体。
3. 将生成的长方体占用的区域从空闲区域中移除，并将剩余的空隙拆分为新的空闲区域（例如，一个空闲区域被新长方体分割为最多6个新的空闲子区域）。

这种方法完全避免了碰撞检测的循环重试，效率更高，且能确保生成的几何体必然不相交。

3. 约束式随机生成 #

在生成长方体的中心和尺寸时，直接加入不相交约束：

• 生成中心位置时，确保该位置与所有已有长方体的中心距离满足：distance_x >= (当前宽度/2 + 已有宽度/2)，同理y、z轴方向都满足该条件。
• 可结合空间划分数据结构快速查询附近的已有几何体，计算合法的中心位置范围，再在该范围内随机生成中心和尺寸。

额外优化：优化相交检测逻辑 #

当前的相交检测通过检查8个顶点是否在对方内部实现，可替换为更高效的轴对齐包围盒（AABB）相交算法：

bool cuboid::intersects(Cuboid a, Cuboid b) {
    // 计算每个轴上的区间是否重叠
    bool x_overlap = (a.center.x - a.width/2 <= b.center.x + b.width/2) && 
                     (a.center.x + a.width/2 >= b.center.x - b.width/2);
    bool y_overlap = (a.center.y - a.height/2 <= b.center.y + b.height/2) && 
                     (a.center.y + a.height/2 >= b.center.y - b.height/2);
    bool z_overlap = (a.center.z - a.depth/2 <= b.center.z + b.depth/2) && 
                     (a.center.z + a.depth/2 >= b.center.z - b.depth/2);
    return x_overlap && y_overlap && z_overlap;
}

该算法仅需6次比较即可判断两个轴对齐长方体是否相交，比顶点检测效率更高。

内容的提问来源于stack exchange，提问作者Lnio Yarschov