matrix - 计算变换椭圆的 AABB

Question

我希望计算应用了变换矩阵(旋转、缩放、平移等)的 2D 椭圆的轴对齐边界框 (AABB)

类似于此解决方案的内容:Calculating an AABB for a transformed sphere

到目前为止，它似乎不适用于 2D 椭圆。

这是我得到的(伪代码):

Matrix M; // Transformation matrix (already existing)
Matrix C = new Matrix( // Conic matrix
    radiusX, 0,         0,
    0,       radiusY,   0,
    0,       0,         -1
);

Matrix MT = M.transpose();
Matrix CI = C.inverse();

Matrix R = M*CI*MT;

int minX = (R13 + sqrt(R13^2 - (R11 * R33))) / R33;
int minY = (R23 + sqrt(R23^2 - (R22 * R33))) / R33;

// maxX etc...
// Build AABB Rectangle out of min & max...

当前行为的简单演示

radiusX = 2    
radiusY = 2                              // To keep it simple, M is identity
                                         // (no transformation on the ellipse)
M = /1 0 0\                              // /M11 M21 M31\ 
    |0 1 0|                              // |M12 M22 M32| Transform matrix format
    \0 0 1/                              // \0   0   1  /

C = /2 0  0\                             // C as conic
    |0 2  0|
    \0 0 -1/

CI =/0.5 0   0\                          // CI as dual conic
    |0   0.5 0|
    \0   0  -1/

R = /1 0 0\ * /0.5 0   0\ * /1 0 0\      // R = M*CI*MT
    |0 1 0|   |0   0.5 0|   |0 1 0|
    \0 0 1/   \0   0  -1/   \0 0 1/

  = /0.5 0   0\                          // /R11 R12 R13\
    |0   0.5 0|                          // |R12 R22 R23| (R is symmetric)
    \0   0  -1/                          // \R13 R23 R33/

minX = (0 + sqrt(0^2 - (0.5 * -1))) / -1

     = -0.7071                           // Should be -2

                                         // Also, using R = MIT*C*MI
                                         // leads to -1.4142

解决方案(使用双圆锥矩阵)

Matrix M;
Matrix C = new Matrix(
    1/radiusX^2, 0,           0,
    0,           1/radiusY^2, 0,
    0,           0,           -1
);
Matrix MT = M.transpose();
Matrix CI = C.inverse();
Matrix R = M*CI*MT;

int minX = (R13 + sqrt(R13^2 - (R11 * R33))) / R33;
int minY = (R23 + sqrt(R23^2 - (R22 * R33))) / R33;

最终解决方案(不直接使用圆锥矩阵)

这是一个简化版本。

Matrix M;

int xOffset = sqrt((M11^2 * radiusX^2) + (M21^2 * radiusY^2));
int yOffset = sqrt((M12^2 * radiusX^2) + (M22^2 * radiusY^2));

int centerX = (M11 * ellipse.x + M21 * ellipse.y) + M31; // Transform center of 
int centerY = (M12 * ellipse.x + M22 * ellipse.y) + M32; // ellipse using M
                                                         // Most probably, ellipse.x = 0 for you, but my implementation has an actual (x,y) AND a translation
int xMin = centerX - xOffset;
int xMax = centerX + xOffset;

int yMin = centerY - yOffset;
int yMax = centerY + yOffset;

Answer 1

从双圆锥

所以你说 M是变换矩阵。但是它转换了什么，是点还是线？我假设点。您如何将点表示为行向量(点在左侧，矩阵在右侧)，或作为列向量(矩阵在左侧，点在乘法右侧)？我将假设列向量。所以转换将是 p' = M*p有一点p .

接下来是 C .你写的方式，这是一个椭圆，但不是你正在使用的半径。如果满足 (x/radiusX)^2 + (y/radiusY)^2 = 1，则点位于椭圆上所以主对角线上的值必须是 (1/radiusX^2, 1/radiusY^2, -1) .在我的答案的先前修订中，我一再错过了这个错误。

接下来你将这些东西结合起来。假设 CP是原始圆锥曲线，即圆锥曲线作为一组点。然后你可以通过做 MT.inverse()*CP*M.inverse() 获得转换后的版本.原因是因为你申请了M.inverse()到每个点，然后检查它是否位于原始圆锥上。但是您没有使用 M.inverse() , 您正在使用 M .这表明您尝试变换双圆锥曲线。如 M转换点，然后 MT.inverse()变换线条，所以 M*CD*MT如果 CD 是正确的转换是双圆锥曲线。

如果 R是双圆锥曲线，那么你的公式是正确的。所以也许你的代码的主要问题是你忘记在矩阵中使用反半径 C .

从原始圆锥

当我第一次阅读您的帖子时，我认为 R将描述一组点，即一个点 (x,y)如果 (x,y,1)*R*(x,y,1).transpose()=0 位于那个椭圆上.基于此，我确实想出了 AABB 的公式，而不使用双圆锥曲线。我并不是说这更简单，尤其是当您将矩阵求逆作为构建块时更是如此。但我还是把它留在这里以供引用。请记住，R本段中的内容与您的代码示例中使用的内容不同。

对于我的方法，请考虑 R*(1,0,0) (这只是 R 的第一列)是一些向量 (a,b,c)您可以将其解释为线的定义 ax+by+c=0 . Intersect that line with the conic然后你得到切线水平的点，它们是 y 中的极值方向。对 R*(0,1,0) 执行相同操作(即第二列)在 x 中找到极值方向。

这里的关键思想是 R*p计算某个点的极线 p ，因此我们正在为 x 中的无穷远点构建极线。分别y方向。该极线将在切线通过 p 的点处与圆锥相交。触摸圆锥，在这种情况下，圆锥是水平的。垂直切线，因为平行线在无穷远处相交。

如果我象征性地进行上述计算，我会得到以下公式:

xmin, xmax = (R13*R22^2 - R12*R22*R23 ± sqrt(R13^2*R22^4 - 2*R12*R13*R22^3*R23 + R11*R22^3*R23^2 + (R12^2*R22^3 - R11*R22^4)*R33))/(R12^2*R22 - R11*R22^2)
ymin, ymax = (R11*R12*R13 - R11^2*R23 ± sqrt(R11^3*R13^2*R22 - 2*R11^3*R12*R13*R23 + R11^4*R23^2 + (R11^3*R12^2 - R11^4*R22)*R33))/(R11^2*R22 - R11*R12^2)

这些表达式当然可以简化，但它应该让你开始。如果您将其重新表述为更简单或更易阅读的内容，请随意编辑这篇文章。