查找场景旋转，以最大程度地减少所有网眼的边界框

发布于 2025-01-31 17:28:07 字数 161 浏览 4 评论 0原文

我有一个场景中每个网格的轴对齐边界框（场景中的多个网眼），我想通过旋转整个场景来最大程度地减少所有网格的AABB（这将在预先计算步骤中完成，以便用户永远都不会感觉这种算法）。

我如何找到将AABB最小化的旋转（我知道它不会是每个网格的绝对最小BB，但总体而言，它将是单个场景轴的最小AABB）？

原文

分享到QQ

分享到微博

如果你对这篇内容有疑问，欢迎到本站社区发帖提问参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。

发布评论

需要登录才能够评论，你可以免费注册一个本站的账号。

一绘本一梦想 2025-02-07 17:28:07

首先，您可以计算网格的凸壳，以大大减少计算点的数量。实际上，凸壳的最小边界框保证与目标网格相同。

有多种方法可以通过计算凸船体的点集的直径来计算1网格的最佳体积，但是Afaik不能轻易地将其转移到N网格中。旋转卡钳可以用于计算点集的直径（支撑的平行线对抗焦点对可用于形成边界框）。

解决此问题的一种简单方法是使用基本的优化方法（AFAIK没有确切的算法可以在线性时间或任何简单的精确算法中解决此问题）。

这是最小化（总体积）的度量函数的示例：

function metric(α, β, θ)
    R_α <- RotationMatrixX(α)
    R_β <- RotationMatrixY(β)
    R_θ <- RotationMatrixZ(θ)
    R <- R_α * R_β * R_θ
    sum <- 0
    for each mesh M:
        K <- Points(PrecomputedConvexHull(M)) * R
        B <- BoundingBox(K)
        sum <- sum + volume(B)
    return sum

α，β和θ是X，Y和Z轴的旋转角度，以优化以最小化总数。有许多优化方法可用于最大程度地减少此度量函数。例如，您可以使用 l-bfgs （应该相对较好，因为公制功能应“平滑”）。

First of all you can compute the convex hull of the meshes so to drastically reduce the number of computed points. Indeed, the minimal bounding box of the convex hull is guaranteed to be the same than the target mesh.

There are ways to compute the optimal volume for 1 mesh by computing the diameter of the point set of the convex hull but AFAIK this cannot be easily transposed to N meshes. The rotating calipers can be used to compute the diameter of a point set (the supporting parallel lines of the antipodal pair can be used to form the bounding box).

One simple way to address this problem is by using basic optimizations methods (AFAIK there is no exact algorithm to solve this in linear time nor any simple exact algorithm).

Here is an example of metric function to minimize (total volume):

function metric(α, β, θ)
    R_α <- RotationMatrixX(α)
    R_β <- RotationMatrixY(β)
    R_θ <- RotationMatrixZ(θ)
    R <- R_α * R_β * R_θ
    sum <- 0
    for each mesh M:
        K <- Points(PrecomputedConvexHull(M)) * R
        B <- BoundingBox(K)
        sum <- sum + volume(B)
    return sum

α, β and θ are the rotation angles of the X, Y and Z axis to optimize so to minimize the total volume. There are many optimization methods that can be used to minimize this metric function. For example, you can use the L-BFGS algorithm (it should be relatively good since the metric function should be "smooth").

回复收藏 0 原文

~没有更多了~