10

我有一个截锥体（截断的金字塔），我需要为这个截锥体计算一个尽可能小的边界球。我可以选择中心正好在截锥体的中心，半径是到“远”角之一的距离，但这通常会在截锥体的窄端留下很多松弛

这似乎是简单的几何图形，但我似乎无法弄清楚。有任何想法吗？

4

8 回答 8

5

这可能不是您要寻找的答案，但您可以计算截锥体的所有顶点并将它们插入到通用最小边界球算法中，例如miniball 实现。

于 2010-02-03T19:43:26.547 回答
5

嗯，当然有http://www.cgafaq.info/wiki/Minimal_enclosing_sphere（通过 Google）。

我认为有两种可能。一个（如果平截头体非常平）将是底部的相对点成为球体上的相对点。另一个（如果平截头体非常高）是平截头体的相对点将在球体上，你会从这四个点中找出球体（一个点在底座上，一个与底座上的第一个点相对，一个在较高方格上与第一个相对，另一个在较高方格上与第一个相邻）。

找出第一个球体。如果截头锥适合它，那就是你的答案。否则，第二个领域将是您的答案。

于 2010-02-03T20:02:28.943 回答
4

有几种算法和实现可以解决这个问题（另见这篇文章）。

  • 对于 2D 和 3D，Gärtner 的实现可能是最快的。

  • 对于更高的维度（比如高达 10,000），请查看https://github.com/hbf/miniball，这是 Gärtner、Kutz 和 Fischer 的算法实现（注意：我是其中的一员） -作者）。

  • 对于非常非常高的维度，核心集（近似）算法会更快。

在您的特定应用程序中，您可能想尝试前两种算法中的任何一种。两者都O(n)以非常小的常数运行并且在数值上是稳定的。

于 2013-02-20T12:04:07.387 回答
2

做到这一点的方法是在你的平截头体上找到一个适合 4 个点的球体。如果这是一个适当的平截头体（截断的金字塔 - 我的错我假设一个圆柱形的平截头体），那么你从顶部四边形的对角得到两个点，从底部四边形得到另外两个点，与顶部两个不同相. 然后用它来获得你的球体。

于 2010-02-03T19:45:08.730 回答
1

好吧，让我们用数学来解决。

使用右手 Y 向上坐标系（向前是 -Z 轴），对于视口宽度 w、高度 h、近平面 n、远平面 f、X 轴视场角 fov 的截锥体，则最小边界球为

k = sqrt(1+(h/w)^2) * tan⁡(fov/2)

if( k^2 >= (f-n)/(f+n) )
{
    C = (0, 0, -f)
    R = f*k
}
else
{
    C = (0, 0, -0.5 * (f+n) * (1+k^2))
    R = 0.5 * sqrt( (f-n)^2 + 2*(f^2+n^2)*k^2 + (f+n)^2*k^4 )
}

C 是球体的中心，在视图空间中，R 是半径。

如果您有兴趣，我会将详细信息放在我的博客中： https ://lxjk.github.io/2017/04/15/Calculate-Minimal-Bounding-Sphere-of-Frustum.html

于 2017-04-16T01:48:05.890 回答
0

任何四个非共面点的集合都定义了一个球体。假设您使用四棱锥作为平截头体，则有 70 组可能的四个点。尝试所有 70 个球体，看看哪个是最小的。

鉴于您的平截头体可能有一些对称性，您可能可以选择对角的四个点并使用 plinth 的解决方案。

于 2010-02-03T19:46:24.247 回答
0

严格来说（根据this），截锥体的底部可以是任何多边形，而且严格来说，该多边形甚至不必是凸的。也就是说，要获得问题的一般解决方案，我认为您可能需要（几乎）使用上面建议的所有顶点。但是，可能存在特殊情况，其解决方案可能（如上所述）只需要比较几个球体。我喜欢上面 Anthony 的链接：Megiddo 提供了一个转换，他声称在 O(n) (!) 时间内产生了一个解决方案。不错 ！

于 2010-02-03T22:50:47.550 回答
0

您需要在截锥体中心下方的“垂直”线上找到一个点，该点到截锥体底部和顶部边缘的距离（假设它是对称的）是相同的。

求解使得底部的点是 Xb、Yb、Zb，顶部的点是 Xt、Yt、Zt，直线是点 Xp、Yp、Zp 加上向量 Ax、By、Cz。

所以解方程

sqrt( (Xb - (Xp + VAx) )^2 + (Yb - (Yp + VBy))^2 + (Zb - (Zp + VCy))^2) = 
sqrt( (Xt - (Xp + VAx) )^2 + (Yt - (Yp + VBy))^2 + (Zt - (Zp + VCy))^2).

唯一的变量是标量 V。

于 2010-02-03T19:56:26.490 回答