菜缤的世界 CairBin's Blog - 计算机图形学
type: channel
link: https://blog.cairbin.top/index.php/category/CG/
items: 二维变换
items: 扫描转换椭圆与圆的绘制
items: 数值微分DDA算法与Bresenham算法画直线

二维变换
type: item
date: 2023-10-27T07:05:12+00:00
description: 二维变换概念应用于对象几何描述并改变其位置、方向或者大小的变换叫做几何变换，有时候也被叫做建模变换。而本文仅讨论平面中的几何变换，即二维变换。矩阵表示和齐次坐标对于普通的2x2矩阵，我们总是要将平移项与其它变换对应的矩阵写成不同规格，为了统一形式且方便运算，我们需要将2x2的矩阵扩展到3x3。此时，二为坐标必须用三元向量来表示。标准实现技术是将二维坐标$(x,y)$扩充到三维$(x_h,y_h,h)$，这称为齐次坐标，这个过程就被叫做齐次化。对于每一个维度有$$ x = \frac{x_h}{h},y=\frac{y_h}{h} $$其中非零值$h$被称为齐次参数。显然对于齐次参数，可以有无数个非零值，同样也意味着有无数个等价的齐次表达式。既然如此，为了方便计算，不妨令$h=1$。平移变换对于平移变换，我们可有参数方程$$ \begin{cases} x^{'}=x+\delta x \\ y^{'} = y+\delta y \end{cases} $$我们将方程组转换为矩阵的形式$$ \begin{bmatrix} x'& y'& 1 \end{bmatrix} = \begin{bmatrix} x& y& 1 \end{bmatrix} \cdot \begin{bmatrix} 1& 0& 0\\ 0& 1& 0\\ \delta x& \delta y & 1 \end{bmatrix} $$旋转变换对于一个复杂的图形的旋转，我们可以看做是多个点在同时旋转。因此只需要研究出一个点的旋转变换方法就可以了。我们不妨令点为平面任意一点，其绕原点进行旋转变换，该点的运动轨迹一定是一个以该点到原点连线为半径的圆弧。那么问题就简单了，对于旋转任意角度，我们只需要用圆的参数方程就能搞定，$$ \begin{cases} x = \cos{\theta} \\ y = \sin{\theta} \end{cases} $$对于我们假设旋转了$\alpha$的弧度（逆时针为正方向），则有$$ \begin{cases} x' = \cos{(\theta+\alpha)}=\cos{\theta}\cos{\alpha}-\sin{\theta}\sin{\alpha}=x\cos{\alpha}-y\sin{\alpha} \\ y' = \sin{(\theta+\alpha)}=\sin{\theta}\cos{\alpha}+\cos{\theta}\sin{\alpha}=x\sin{\alpha}+y\cos{\alpha} \end{cases} $$很显然对应矩阵形式为$$ \begin{bmatrix} x'&y'&1 \end{bmatrix} = \begin{bmatrix} x& y& 1 \end{bmatrix} \cdot \begin{bmatrix} \cos{\alpha}& \sin{\alpha}& 0 \\ -\sin{\alpha}& \cos{\alpha}& 0 \\ 0& 0& 1 \end{bmatrix} $$那么问题来了，如果所绕的旋转点不是原点怎么办呢？前面已经讲过平移变换了，只需要平移坐标系原点至该点（移轴），再进行旋转，最后平移回去就行了。不妨令被围绕点坐标为$P(x_1,y_1)$，则该流程的矩阵运算如下：$$ \begin{bmatrix} x'& y'& 1 \end{bmatrix} = \begin{bmatrix} x& y& 1 \end{bmatrix} \cdot \begin{bmatrix} 1& 0& 0\\ 0& 1& 0\\ -x_1& -y_1 & 1 \end{bmatrix} \cdot \begin{bmatrix} \cos{\alpha}& \sin{\alpha}& 0 \\ -\sin{\alpha}& \cos{\alpha}& 0 \\ 0& 0& 1 \end{bmatrix} \cdot \begin{bmatrix} 1& 0& 0\\ 0& 1& 0\\ x_1& y_1 & 1 \end{bmatrix} $$如果你对平移坐标系难以理解，不妨将坐标轴与平面想象成两个分离的东西。以坐标轴往右移动为例，则对于平面上的点来讲，就相当于坐标轴不动点向左平移。（平移坐标系只是移动的轴，不带平面上其他点，否则你会得到相反的结果！）缩放变换首先给出参数方程$$ \begin{cases} x' = s_xx \\ y' = s_yy \end{cases} $$对应矩阵运算为$$ \begin{bmatrix} x'&y'&1 \end{bmatrix} = \begin{bmatrix} x& y& 1 \end{bmatr…

扫描转换椭圆与圆的绘制
type: item
date: 2023-10-01T16:03:00+00:00
description: 扫描转换椭圆与圆的绘制前提我们先来设计一种数据类型class Point{ public: double x,y; Point(){this->x = 0; this->y = 0;} Point(double x, double y){this->x=x;this->y=y;} };注意此处的类型为double这一点很重要，因为在某些迭代过程中设置为int会导致坐标数值不变，然后进入死循环或者绘制不出来。如果需要int类型，那么无需担心，double到int之间会有一个隐式转换，直接将Point类型中属性值赋给对应的变量即可。（如果你想知道哪些情况下使用int会无法绘制请参考椭圆部分的DDA算法）圆基础知识在直角坐标系中，圆心在原点上的圆有如下方程：$$ x^2+y^2 = R^2 $$其中R为圆的半径。若圆心不在原点上，则有更一般形式的方程。假设圆心为(a,b)则圆的方程为：$$ (x-a)^2+(y-b)^2 = R^2 $$同样的，对于圆心在原点上的圆我们有参数方程：$$ \begin{cases} x=R\cos \theta \\ y = R\sin \theta \end{cases} $$对于圆心不在原点上的圆有参数方程：$$ \begin{cases} x=a+R\cos \theta \\ y = b+R\sin \theta \end{cases} $$将$\theta$离散化可得$$ \theta = 2\pi \frac{i}{n},i\in[0,n] $$然而我们在计算的时候并不喜欢圆心不在原点上的圆，所以在进行扫描转换之前，我们先平移坐标系原点至圆心，当扫描转换完成后再平移回去。故而在接下来的讨论中，我们只使用圆心在原点上的方程。此外，圆还有如下几种对称性质：关于 $y=\pm x$ 对称关于x轴对称关于y轴对称这几条对称轴将圆分割成了八等份，也就是说，给出圆周上任意一个点，就能通过数学计算得到其余的7个点。这对于圆的绘制就简单了许多，我们只需要计算出八分之一的圆弧，就能得到整个圆。在开始之前我们不妨约定这样一个函数（C++风格伪代码，实际代码根据你自己的API来调用相应的函数）/* 以原点为圆心，通过八分之一圆上的一点绘制其余七个对称点 * p为绘制的点 * center为圆心 * color为绘制颜色 */ void draw_circle_point(const Point& p, const Point& center, Color color){ int x = p.x; int y = p.y; int ox = center.x, oy = center.y; setPixel(x+ox,y+oy,color); //绘制像素 setPixel(y+ox,x+oy,color); setPixel(-y+ox,x+oy,color); setPixel(-x+ox,y+oy,color); setPixel(-x+ox,-y+oy,color); setPixel(-y+ox,-x+oy,color); setPixel(y+ox,-x+oy,color); setPixel(x+ox,-y+oy,color); }此外在接下来的计算中可能会用到三角函数的和差公式，请牢记这一点：$$ \sin{(\alpha \pm \beta)}=\sin{\alpha}\cos{\beta}\pm \cos{\alpha}\sin{\beta} \\ \cos{(\alpha \pm \beta)} = \cos{\alpha}\cos{\beta} \mp \sin{\alpha}\sin{\beta} $$直接计算法直接生成有两种方式，一种是根据直角坐标系下笛卡尔方程来计算，另一种根据参数方程。笛卡尔方程直接计算我们扫描这样圆弧上的点。根据方程 $x^2+y^2=R$ 可以得到：$$ \begin{cases} x_{i+1} = x_i+1,x\in [0,\frac{R}{\sqrt{2}}] \\ \\ y_{i+1} = round(\sqrt{R^2-x_{i+1}^2}) & \end{cases} $$故有C++风格伪代码const double SQRT_2 = sqrt(2); /* * 利用笛卡尔方程直接绘制圆 * circle_center为圆心 * R为圆半径 * color为绘制的颜色 */ void draw_circle_common(const Point& circle_center, double R, Color color){ double xr = R/SQRT_2; Point p; for(p.x=0;p.x<=xr;p.x++){ p.y=sq…

数值微分DDA算法与Bresenham算法画直线
type: item
date: 2023-09-24T02:56:00+00:00
description: 数值微分DDA算法与Bresenham算法画直线前提最近在学计算机图形学画线算法，主要学了两种数值微分算法(Digital Differential Analyzer, DDA)中点Bresenham算法直线我们既然要画线就必然要研究一些直线的基本性质。在中学就学过直线的斜截式方程为（我们先不考虑斜率不存在的情况，对与这种情况我们非常容易处理，只需单独拿出来判断下就行）$$ y=kx+b $$其中k为直线斜率，b为直线截距。在计算机中，我们如果要画一条线段，只需要取直线上的部分的点即可。我们不妨考虑线段的起始点和终点，其中起点坐标为：$$ (x_0,y_0) $$终点坐标为：$$ (x_{end},y_{end}) $$我们很轻松能得到斜率和截距与两点的关系式：$$ k = \frac{y_{end}-y_{0}}{x_{end}-x_{0s}} $$$$ b = y_0 - kx_0 $$不妨分别给定x方向和y方向的增量$\Delta{x}$和$\Delta{y}$$$ \Delta{y}=k\Delta{x} $$变形可得$$ k= \frac{\Delta{y}}{\Delta{x}} $$在光栅算法中，我们规定x和y方向上变化步长（变化量的绝对值）大的那一方向为最大位移方向。（沿正还是负根据实际情况判断）DDA算法原理取无穷小量$\varepsilon >0$，由于直线的一阶导数是连续的，而且对于$\Delta{x}$和$\Delta{y}$是成比例的，因此可通过在当前位置$(x_i,y_i)$，分别加上$\varepsilon x$和$\varepsilon y$来求出下一点的坐标$(x_{i+1},y_{i+1})$，即有方程$$ \begin{cases} x_{i+1} = x_{i}+\varepsilon \Delta x \\ y_{i+1} = y_{i}+\varepsilon \Delta y \\ \end{cases} $$对于计算机来讲这些点都是离散的，也就是说我们不可能取真正意义上的无穷小量。对于屏幕来讲，最小的单位就是一个像素，也就是说对于x和y方向上我们只能移动正整数个像素或者不位移，而最小的正整数为1，我们要绘制下一个点的坐标必然要在某个方向上移动1。通俗一点来讲，我们取x、y其中一个方向移动一个像素，以x为例：我们在x轴上移动一个像素大小，那么根据直线方程$x_i+1$代入得到的y值很可能是个小数，我们需要通过向上取整或者向下取整来找一个与这个小数近似的整数来作为近似的y坐标。接下来就很简单了，我们仅需要计算一下恰好比这个小数大的整数和恰好比这个小数小的整数离该小数的距离即可（四舍五入，哪个整数离得近就选哪个整数）。那么问题来了，我们究竟是选择x方向移动1，还是y方向移动1？回到我们的实际问题上来：我们仅想要一些近似于实际直线上的点，越近似越好！如果x变化比y快，也就是说x为最大位移方向，当我们选择移动y一个单位，x变化就可能非常大，带来的误差就可能大。y为最大位移方向，选择移动x同理。那么结论就有了：为降低误差，选最大位移方向为移动方向，移动1个单位的问题就转变成了找最大位移方向问题。当x为最大位移方向的时候$$ max(|\Delta x|,|\Delta y|) = |\Delta x| $$也就是说$$ 0 \le |k|\le 1 \\ \varepsilon |\Delta x| = 1 $$我们可以得出$$ \varepsilon |\Delta y| =\frac{|\Delta y|}{|\Delta x|} $$那么代入方程组可得$$ \begin{cases} x_{i+1} = x_{i}+\varepsilon |\Delta x| = x_{i}+\frac{\Delta x}{|\Delta x|}=x_i \pm 1\\ y_{i+1} = y_{i} + \varepsilon |\Delta y| = y_{i}+\frac{\Delta y}{|\Delta x|} = y_{i} \pm k \end{cases} $$同理我们得出y为最大方向的时候方程组如下$$ \begin{cases} x_{i+1} = x_{i} \pm \frac{1}{k} \\ y_{i+1} = y_{i} \pm 1 \end{cases} $$对得到的$(x_{i+1},y_{i+1})$的坐标四舍五入即为我们要绘制的近似点的坐标。上述两个方程组正负号处取正号还是负号与$\Delta x$和$\Delta y$有关系，例如对于初始点x坐标比终点x坐标小，斜率在$(0,1]$上的直线，最大位移方向为x方向，从起点到终点绘制x是不断增大的，所以$x_i \pm…