计算机图形学II--基础填充几何变换
昨天没写完，今天补上后半部分。现在回想起来计算机图形学是我本科时期上的最有意思的一门课程，其他解方程如果没有联系到实际问题，实在是太枯燥了。为啥我们的本科数学教科书不能改改，从更加应用的方向讲起呢。
扫描线算法
扫描线算法(Scanline rendering, Scanline alghorithm)主要用途是填充在屏幕上显示的几何图形。这个方法就是一个点一个点、一条线一条线，像扫描一样，把一个多边形的内部填满。 要想填充多边形内部的所有像素，需要找到一种合适的规则，能够沿着一个方向，一个像素不漏地把多边形内部填满，同时不污染多边形外部。于是上世纪六十年代，人们发明了一条水平方向的扫描线，它从\(y=0\)开始，判断与多边形的交点，这些交点把扫描线分成了若干段，之后判断哪些“段”在多边形内部，哪些“段”在多边形外部，然后把内部的部分着色，完成后，令\(y=y+1\)，即扫描线上移一格，重复之前的操作，直到扫描线不再与多边形的任何部分相交。
我的这个程序里用Bresenham’s line 的方法画多边形的边，然后用扫描线算法判断哪些像素是在多边形内部。
function scanline(x,y)
%测试数据：
% x=[10 50 30]./2;y=[30 20 70]./2;
% x=[10 30 50 20]./2;y=[20 10 50 70]./2;
% x=[20 50 110 110 50 20]./5;y=[20 10 30 80 50 70]./5;
% x=[20 25 210 110 80 20 50]./5;y=[20 5 60 80 50 70 35]./5;
% x=[20 25 100 210 110 80 20 50]./5;y=[20 5 40 30 80 50 70 35]./5;
n=length(x);
kk=1;
A=[0,0];
x=[x,x(1)];
y=[y,y(1)];
for i=1:n
[a,k]=Bresenhamline(x(i),y(i),x(i+1),y(i+1));%画边
kk=kk+k;
A=[A;a];
end
A=A(2:kk,:);
m=kk-1;
y0=min(A(:,2));
y1=max(A(:,2));
yy=y0;
datayy=[inf inf];
while yy<y1
k=0;
for i=1:m
if A(i,2)==yy
k=k+1;
D(yy,k)=A(i,1);
end
end
d0=min(D(yy,1:k));
d1=max(D(yy,1:k));
for j=d0:d1-1
% pause(0.001);
% plot(j,yy,'ro');
datayy=[datayy;j yy];
end
yy=yy+1;
end
x0=min(A(:,1));
x1=max(A(:,1));
xx=x0;
dataxx=[inf inf];
while xx<x1
k=0;
for i=1:m
if A(i,1)==xx
k=k+1;
D(xx,k)=A(i,2);
end
end
d0=min(D(xx,1:k));
d1=max(D(xx,1:k));
for j=d0:d1-1
% pause(0.001);
% plot(xx,j,'ro');
dataxx=[dataxx;xx j];
end
xx=xx+1;
end
if size(dataxx(:,1))>size(dataxx(:,1))
for i=2:size(dataxx(:,1))
for j=2:size(datayy(:,1))
if dataxx(i,1)==datayy(j,1) && dataxx(i,2)==datayy(j,2)
plot(dataxx(i,1),dataxx(i,2),'ro');
pause(0.001);
end
end
end
else
for i=2:size(datayy(:,1))
for j=2:size(dataxx(:,1))
if datayy(i,1)==dataxx(j,1) && datayy(i,2)==dataxx(j,2)
plot(datayy(i,1),datayy(i,2),'ro');
pause(0.001);
end
end
end
end
end
其他图形变换
最终我为了展示自己所有的画图方法，搞了个大demo程序，把所有画线和几何图形的变换都囊括在一张图里。程序里可能还有些bug。 这其中包括：旋转变化，平移变换，比例变换，对称变换（关于x轴），错切变换，相对(2,2)点的旋转变换。
错切变换（transvection）是啥？就是把矩形变成平行四边形的变换。
function demo
figure
subplot(4,2,1)
[Dx Dy]=DDALine(4,6,8,10)%DDALine(x(1),y(1),x(2),y(2))
[X2]=Bresenhamline(1,2,6,7)%Bresenhamline(x(1),y(1),x(2),y(2))
Bx=X2(:,1);
By=X2(:,2);
%----------------------------------------------
%二维几何变换
s=45;
T=[cos(s) sin(s) 0;
-sin(s) cos(s) 0;
0 0 1];
title('旋转变换(逆时针)');
xlabel('x');
ylabel('y');
for i=1:size(Dx(:))
z=[double(Dx(i)) double(Dy(i)) 1];
z=z*T;
XX(i)=z(1);
YY(i)=z(2);
plot(XX,YY,'*- k')
end
for i=1:size(Bx(:))
z=[double(Bx(i)) double(By(i)) 1];
z=z*T;
XXX(i)=z(1);
YYX(i)=z(2);
plot(XXX,YYX,'*- y')
end
%----------------------------------------------
subplot(4,2,2)
T=[1 0 0;
0 1 0;
4 5 1];
for i=1:size(Bx(:))
z=[double(Bx(i)) double(By(i)) 1];
z=z*T;
XXX(i)=z(1);
YYX(i)=z(2);
plot(XXX,YYX,'*- g')
title('平移变换');
xlabel('x');
ylabel('y');
end
hold on
plot(Bx,By,'* b');
%----------------------------------------------
subplot(4,2,3)
T=[2 0 0;
0 2 0;
0 0 1];
for i=1:size(Bx(:))
z=[double(Bx(i)) double(By(i)) 1];
z=z*T;
XXX(i)=z(1);
YYX(i)=z(2);
plot(XXX,YYX,'*- g')
title('比例变换');
xlabel('x');
ylabel('y');
end
hold on
plot(Bx,By,'* b');
%----------------------------------------------
subplot(4,2,4)
T=[1 0 0;
0 -1 0;
0 0 1];
for i=1:size(Bx(:))
z=[double(Bx(i)) double(By(i)) 1];
z=z*T;
XXX(i)=z(1);
YYX(i)=z(2);
plot(XXX,YYX,'*- g')
title('对称变换(关于x轴)');
xlabel('x');
ylabel('y');
end
hold on
plot(Bx,By,'* b');
%----------------------------------------------
subplot(4,2,5)
T=[0 -1 0;
-1 0 0;
0 0 1];
for i=1:size(Bx(:))
z=[double(Bx(i)) double(By(i)) 1];
z=z*T;
XXX(i)=z(1);
YYX(i)=z(2);
plot(XXX,YYX,'*- g')
title('对称变换(关于y=-x轴)');
xlabel('x');
ylabel('y');
end
hold on
plot(Bx,By,'* b');
%----------------------------------------------
subplot(4,2,6)
T=[1 -1 0;
2 1 0;
0 0 1];
zx=[1 5 3 1];
zy=[3 4 0 3];
clear XXX
clear YYX
for i=1:size(zx(:))
z=[double(zx(i)) double(zy(i)) 1];
z=z*T;
XXX(i)=z(1);
YYX(i)=z(2);
plot(XXX,YYX,'*- g')
title('错切变换');
xlabel('x');
ylabel('y');
end
hold on
plot(zx,zy,'*- b');
%----------------------------------------------
subplot(4,2,7)
T1=[1 0 0;
0 1 0;
-2 -2 1];
T=[cos(s) sin(s) 0;
-sin(s) cos(s) 0;
0 0 1];
clear XXX
clear YYX
for i=1:size(Bx(:))
z=[double(Bx(i)) double(By(i)) 1];
z=z*T1*T*(-1*T1);
XXX(i)=z(1);
YYX(i)=z(2);
plot(XXX,YYX,'*- g')
title('相对(2,2)点的旋转变换');
xlabel('x');
ylabel('y');
end
hold on
plot(Bx,By,'* b');
end
树根和回文串
还是那个code文件夹里的东西，现在写代码的习惯里必须再增加一条，写明这个程序的作用。我整理了不少图形图像和online judge的程序，每次回想程序的用途都是一件非常麻烦的事情，有的时候根本就想不起来。
树根
这个问题非常的经典，具体的介绍可以参照知乎中leetcode.wang的介绍
对于给定的数字，将其每一位上的数字相加得到新的数字，一直重复这个过程，直到这个数小于10，将这个数输出。
原数是n，树根就可以表示成(n-1) mod 9 + 1。 主要的用途是计算模运算的同余，对于非常大的数字的情况下可以节省很多时间。数字根可作为一种检验计算正确性的方法。例如，两数字的和的数根等于两数字分别的数根的和。
当时做这道题的时候，想到了树根的问题，但是没有求出其表达式，因而采用了一个比较苯的办法来做计算，即排除数字9,在一个多位数字中，排除9和0的其他数字之和不影响最终的树根结果。那么我就在计算的时候默认排除了9和0的加法运算。
写了一大长串程序，其中的char - '0' 是ASCII运算，将字符转换成其对应的数字，这个程序也是本篇文章中唯一可以正常运行的程序。
#include <stdio.h>
int main()
{
unsigned long a=0,b=0;
int flag=2;
char c;
while(1)
{
a=0;b=0;flag=2;
c=getchar();
if(c=='0') break;
else
{ a=a+(c-'0');
while((c=getchar())!='\n')
{
if(((c-'0')!=9)&&((c-'0')!=0))
{
a=a+(c-'0');
}
}
// c='0';
while(flag>1)
{ if(a>9)
{
while(a!=0)
{ b=b+a%10;
a=a/10;
}
if(b>9)
{
flag=2;
a=b;
b=0;
}
else{
flag=0;
a=b;
b=0;
break;
}
}
else
{
break;
}
}
printf("%d\n",a);
}
}
}
谁知道其实答案如此简单(⊙ˍ⊙)。
public int addDigits(int num) {
return (num - 1) % 9 + 1;
}
回文串
这程序里有bug，目前无法自动停止。输入一串数字，判断这窜数字是否有回文结构。这个题目主要靠算法思想，但是我没什么思想，只会最简单的按位比较.
例如：输入123321，返回YES；输入123231,返回NO。
#include <cstring>
#include<iostream>
using namespace std;
int isPalindrome(char str[])
{
int len=strlen(str);
int i,j;
i=0;
j=len-1;
while(i<j)
{
if(str[i++]!=str[j--]) return 0;
}
return 1;
}
int main(){
char str[10001];
int n,i=0;
cin>>n;
while(i<=n-1)
{ i=i+1;
cin>>str;
int a=0;
a=isPalindrome(str);
if(a==1) cout<<"YES"<<endl;
else cout<<"NO"<<endl;
}
return 0;
}
其他
我忘记了这个程序是做什么的，程序名称是MaxArray，估计是个找最大array相关的程序。从这个例子中深刻的体会到，写代码注释的重要性。
#include <stdio.h>
//#include <stdlib.h>
#define MAX 130
int maxSum(int b[], int n)
{
int max = b[0];
int sum = 0;
for(int i = 0; i < n; ++i)
{
if(sum < 0) sum = b[i];
else sum += b[i];
if(sum > max) max = sum;
}
return max;
}
int solve(int a[][MAX], int n)
{
int b[MAX];int i,j,k,sum,tmp;
sum = a[0][0];
for(i = 0; i < n; ++i)
{
for(k = 0; k < n; ++k) b[k] = 0;
for(j = i; j < n; ++j)
{
for(k =0; k < n; ++k) b[k] += a[j][k];
if(sum < (tmp = maxSum(b,n)) ) sum = tmp;
}
}
return sum;
}
int main()
{
int arr[MAX][MAX];
int i,j,n;
while(scanf("%d",&n)!=EOF)
{
for(i = 0; i < n; ++i)
for(j = 0; j < n; ++j)
scanf("%d",&arr[i][j]);
printf("%d",solve(arr,n));
break;
}
// system("pause");
return 0;
}
老古董Fortran
依旧是整理code文件夹里的东西，Fortran语言基本上被我当作化石了，除了在久远的“遗产代码”中你会看到这门语言，当今，应该没有人将它用作主要的编程语言。
我在学习Fortran的时候还是用的 g77，但是现在发现，在我的系统里只能使用gfortran来编译了。
下面是写过的唯一一个代码，其中C开头的是注释，编译方法是 gfortran helloworld.f -o helloworld。
传统的 Fortran 程序只能用大写字符书写，而且每行前六个字符为特定用途所保留。第一列为字符 C 所保留，用来表征整行都是注释。第二列到第六列是为标号预留的。代码从第七列开始。下面是示例程序采用的是传统的 Fortran 格式。
C helloworld.f
C
PROGRAM HELLOWORLD
WRITE(*,10)
10 FORMAT('hello, world')
END PROGRAM HELLOWORLD
C http://wiki.ubuntu.org.cn/Compiling_Fortran77
c g77 helloworld.f -o helloworld
希望这些老古董能尽早退役吧。
计算机图形学I--基础画线
为什么我今天这么闲，可以更水这么多篇博客，那是因为昨天在家办公感觉比在办公室还累，所以索性不干了。(* ￣︿￣)
本篇内容所有程序都是MATLAB/GNU Octave上运行的。
注意：有没有最后的end可能是上面两个编译环境的区别，但是我没有安装MATLAB，所以没法测试MATLAB现在的函数组成中是否仍旧不带最后一个end。
数值微分法画线
众所周知，在屏幕上连续的点组成了线条。那么如何在计算机中模拟这些由“点”生成的线呢，这就是计算机图形学要研究的内容，其中最简单的一个问题就是画直线。
数值微分法（ Digital Differential Analyzer，DDA）是一种处理此种问题的经典算法。
算法思想：
- 给定一条线段的起点\((x_1, y_1)\)和终点\((x_2, y_2)\)，分别计算在两轴上的差值 \(\Delta y = y_{2} - y_{1}\) 和 \(\Delta x = x_{1} - x_{2}\)。
- 比较\(\Delta y\)和\(\Delta x\)二者谁比较大，大的那一个就作为遍历的总步数。\(steps = max(\Delta x, \Delta y)\)。我的程序中简化了这个部分，直接把x作为主序方向。
- 计算在x和y方向上单步的步距。 \(d_x = \frac{\Delta x}{steps}\)，\(d_y = \frac{\Delta y}{steps}\)。我的程序里只计算了y方向的单步距离，x方向一直是“进1”。
- 我的程序中根据\(x_0\)和\(x_1\)的大小决定划线的方向，y增长的部分是根据斜率和目前点的位置来计算的。这个过程涉及大量的浮点运算，效率上是比较低的。
function [Xdata Ydata]=DDALine(x0,y0,x1,y1)
% DDALine(8,9,2,6)
% DDALine(2,6,8,9)
% DDALine(1,9,6,5)
% DDALine(6,5,1,9)
deltaX=x1-x0;
deltaY=y1-y0;
if deltaX~=0&&deltaY~=0
Slope=double(deltaY)/double(deltaX);
CurrentY=double(y0);
j=1;
if x0<x1
for CurrentX=int8(x0):int8(x1)
plot(CurrentX,int8(CurrentY-0.5),'* r');
Xdata(j)=CurrentX;
Ydata(j)=int8(CurrentY-0.5);
hold on;
CurrentY=Slope+CurrentY;
j=j+1;
end
end
if x0>x1
for CurrentX=int8(x0):-1:int8(x1)
plot(CurrentX,int8(CurrentY-0.5),'* r');
Xdata(j)=CurrentX;
Ydata(j)=int8(CurrentY-0.5);
hold on;
CurrentY=-Slope+CurrentY;
j=j+1;
end
end
title('DDAline');
xlabel('x');
ylabel('y');
hold on
end
if deltaX==0&&deltaY~=0
plot(x1,min(y0,y1):max(y0,y1),'* r');
end
if deltaX~=0&&deltaY==0
plot(min(x0,x1):max(x0,x1),y0,'* r');
end
grid on;
end
Bresenham’s line algorithm
Bresenham line’s algorithm 是DDA的一种改进算法。它与DDA相比有质量和效率的两点改进：
- 以y方向为例，Bresenham line 根据斜率的方向，决定每一个点是离\(y_1\)还是\(y_2\)近，从而给出下一个点的位置究竟是y+1还是y-1。
- 由于上述原因，该方法避免了大量的浮点小数计算。
function [a,k]=Bresenhamline(x0,y0,x1,y1)
% Bresenhamline(8,9,2,6)
% Bresenhamline(2,6,8,9)
% Bresenhamline(1,9,6,5)
% Bresenhamline(6,5,1,9)
dx=x1-x0;
dy=y1-y0;
d1=abs(2*dx);
d2=abs(2*dy);
x=x0;y=y0;
plot(x,y,'*');
a=[x y];
k=1;
if(abs(dx)>=abs(dy))
e=-abs(dx);
while abs(x)~=abs(x1)
if(dx>=0) x=x+1;end
if(dx<0) x=x-1;end
e=e+d2;
if e>0
if(dy>=0)y=y+1;end
if(dy<0)y=y-1;end
e=e-d1;
end
hold on;
a=[a;x y];k=k+1;
hold on;
plot(x,y,'*');
end
end
if(abs(dx)<abs(dy))
e=-abs(dy);
while abs(y)~=abs(y1)
if(dy>=0) y=y+1;end
if(dy<0) y=y-1;end
e=e+d1;
if e>0
if(dx>=0) x=x+1;end
if(dx<0) x=x-1;end
e=e-d2;
end
hold on;
a=[a;x y];k=k+1;
hold on;
plot(x,y,'*');
end
end
hold on;
grid on;
end
不要让媒体定义你看待事物的方式
这因该是最近关于新冠最后的一篇博文了，由于我也在做相关的边缘辅助工作，工作量大，负能量也大，但是不能因为这些问题而让生活变得更糟。
由于美国政府对疫情应对不利，特朗普为了保护他的选举基本盘，已经丧心病狂的直呼新冠病毒是China/Chinese病毒，特朗普上台以后就一直在挑起种族歧视，称中国留学生是间谍，很多华裔学者/对华人有好的学者在美遭受无端调查和指控。
澳大利亚一直是美国的坚定支持者和追随者，反华政策这些年间也接连不断，疫情初期停止中国人入境的国家就属美国和澳大利亚最快。国内的普通人自然会对这两国有着强烈的不满。国内的媒体也会引导舆论，揭露这两国的政客对中国的无端指控和造谣。但是今天新闻出了一个消息“澳总理称美国是澳感染病例最大来源”，这一时间，让很多人认为澳大利亚站在了我们这边，开始谴责美国。结果很多人都在调侃，澳大利亚的立场要偏向中国了，因为他们想要医护物品援助。不管怎样解读，媒体都很好的带起了节奏 —— 即，更多的国家意识到美国是传播疫情的国家。（究竟是不是，我也不知道，但下结论必须有科学严谨的分析，目前的全球状况，我们还是多关注怎么控制传播，治疗疾病，早日结束疫情吧。） 殊不知，莫里森后面就说了新冠疫情起源于中国，传播到了全世界。
如果仔细听这期电台广播，你可以知道莫里森没有对任何国家进行谴责、辩护或者讨好，他只是在陈述他认为的事实情况：由于美澳交往密切，所以澳洲的病例大多源自美国，但是新冠疫情最初爆发在中国，传遍了整个世界。目前为止，没有证据表明任何国家，包括中国，在故意做任何事情。
这并不能说明澳大利亚看待疫情的立场出现了变化，并且开始偏向中国，指责美国。他们想不想借此要中国防护物资单说。
这让我想到n年前，我的同事为了介绍媒体的作用，用到的一幅图《不要让媒体定义你看待事物的方式》
媒体可以让人们了解真相，也可以做到颠倒黑白。
如果要看国外消息，最好找原始出处，就像国内的新闻会有“反转”一样，被别有用心剪辑的新闻，能让你对某些事物产生错误的看法。有条件就不要看剪辑后的内容，因为，它很有可能为了突出某种观点而掩盖内容的完整性。
对于中国的攻击会因为疫情而不断持续，并且在美国会变得是一件政治正确的事情，这会煽动很多人的反华情绪，海外华侨华人多保重吧。
