4

我正在寻找在其上应用变换矩阵（旋转、缩放、平移等）的 2D 椭圆的轴对齐边界框（AABB）

类似于此解决方案的内容：Calculating an AABB for a transform 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;
4

1 回答 1

2

从双圆锥

所以你说这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)，您可以将其解释为 line 的定义ax+by+c=0。将该线与圆锥相交，您会得到切线水平的点，这是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)

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

于 2014-07-14T23:08:49.937 回答