我正在寻找计算应用了转换矩阵的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...
Simple demo of the current behavior
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;
1 回答
来自双锥形
所以你说
M
是一个转换矩阵 . 但它改变了什么,是点还是线?我假设积分 . 如何将点表示为行向量,使得点位于左侧,矩阵位于右侧,或者作为列向量,以便矩阵位于左侧,而右侧的点位于乘法的位置?我假设列向量 . 因此,对于某些点p
,转换将是p' = M*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()
转换线,如果CD
是双锥形,则M*CD*MT
是正确的转换 .如果
R
是双锥形,那么你的公式是正确的 . 因此,您的代码可能存在的主要问题是您忘记在矩阵中使用反半径C
.来自原始圆锥曲线
当我第一次阅读你的帖子时,我假设
R
会描述一组点,即如果(x,y,1)*R*(x,y,1).transpose()=0
,点(x,y)
就位于该椭圆上 . 基于此,我确实为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)
(即seond列)执行相同操作以查找x
方向的极值 .这里的关键思想是
R*p
计算某点p
的极线,所以我们在x
resp中构建无穷远点的极线 .y
方向 . 切线通过p
触及圆锥的那些点将与圆锥相交,在这种情况下,圆锥将是水平的 . 垂直切线,因为平行线在无穷远处相交 .如果我象征性地进行上述计算,我得到以下公式:
这些表达式当然可以简化,但它应该让你开始 . 如果您将此重新编写为更简单,更易于阅读或其他任何内容,请随意编辑此帖子 .