三维显示器

Pittow · 2020-11-02 13:38:29 · 个人记录

文章的标题之所以用三维，是因为上次秋游去看了一场5D电影，非常震撼，出来的时候脸上和衣服都是湿的。为避免引起歧义，标题特使用汉字三维。但由于种种原因，以下用3D代替三维。

开门见山

再看这个

后看这个本文中所有3D示例均使用该查看器查看。

3D显示器显然可以显示出3D的图像，就是将3D的数据建模，然后投影到屏幕上去。

道理很简单：首先，你要有一个屏幕，然后，你要有一个观察点，最后，你要有一个物体。于是你就可以开始观察了。

也可以使用这个，看的更清楚->v

21 36
500 500 1500 500 500 1600 500 600 1500 500 600 1600
600 500 1500 600 500 1600 600 600 1500 600 600 1600
300 300 1200 300 600 1200 600 300 1200 600 600 1200
462.5 462.5 1200 460 460 1200 462.5 487.5 1200 460 480 1200
487.5 462.5 1200 480 460 1200 487.5 487.5 1200 480 480 1200
450 450 1100
1 2 3 4 5 6 7 8 1 3 2 4 5 7 6 8 1 5 2 6 3 7 4 8
9 10 9 11 10 12 11 12
13 14 15 16 17 18 19 20 13 15 14 16 17 19 18 20
13 17 14 18 15 19 16 20
1 21 2 21 3 21 4 21 5 21 6 21 7 21 8 21
将此数据输入查看器即可查看。

点坐标

相似三角形

连接目标点和观察点，线段与显示屏的交点的坐标就是它在你的电脑屏幕上的坐标。

从显示屏的纵横两个方向分别来看，都能得到这样一个模型：显然\frac{TC}{CO}=\frac{AH}{HO}

也就是说AH=\frac{HO* TC}{CO}

其中，TC=X_T-X_O \quad CO=Y_T-Y_O，HO则是一个常数，代表显示屏与观测点的距离，这个值在一开始就应该设置好，而且除非打开倍镜，否则这个值不应该改变。

最后这个模型会得到A点在显示屏上一个维度的坐标，而将这个模型在与显示屏垂直的两个方向上分别计算一次，就能得到A点在显示屏上的完整坐标。若镜头朝向Z轴正方向，以显示屏中心为坐标(0,0)，CO=Z_T-Z_O，则A(\frac{HO* (X_T-X_O)}{CO},\frac{HO* (Y_T-Y_O)}{CO})

29 32
0 0 500 -300 -300 1000 -300 300 1000 300 -300 1000
300 300 1000 300 300 2000 0 0 2000 0 300 2000
300 0 2000 0 100 1000 100 0 1000 0 0 1000 95 95 1000
95 105 1000 105 95 1000 105 105 1000 100 100 1000
290 290 2000 290 310 2000 310 290 2000 310 310 2000
290 300 1990 290 300 2010 310 300 1990 310 300 2010
300 290 1990 300 290 2010 300 310 1990 300 310 2010
1 7 1 6 1 8 1 9
2 3 3 5 4 5 2 4
6 8 6 9 7 8 7 9
10 17 11 17 10 12 11 12
13 14 13 15 14 16 15 16
18 19 18 20 19 21 20 21
22 23 22 24 23 25 24 25
26 27 26 28 27 29 28 29

十分简单对不对，甚至只用到了相似三角形的基本知识。

三角函数与旋转

然而，如果只是使用相似三角形，当然只能处理视线正对坐标轴的情况。如果视线旋转之后还要得到正确的答案，就需要这个：设O(0,0)，A(x,0)，AO=BO，\angle AOB=\alpha，则B点的坐标显然为(x\cos\alpha,x\sin\alpha)。对于坐标为(0,y)的点，它同样逆时针旋转后的坐标是(-y\sin\alpha,y\cos\alpha)。这两个坐标可以简单相加，于是可以求出对于任意的A(x,y)，它逆时针旋转\alpha度角后的坐标是(x\cos\alpha-y\sin\alpha,x\sin\alpha+y\cos\alpha)（这也是三角恒等变换的基础）。

拖欠图片一张，数据一组

同样的，对于三维空间坐标(x,y,z)，当Z轴正方向指向前方，Y轴正方向指向上方，X轴正方向指向右方时，将它向左旋转\alpha度，然后向上旋转\beta度后，它的坐标就是

(x\cos\alpha-z\sin\alpha,x\sin\alpha\sin\beta+y\cos\beta+z\cos\alpha\sin\beta,x\sin\alpha\cos\beta-y\sin\beta+z\cos\alpha\cos\beta)

公式很恶心对不对，然而你根本就不需要看懂它，因为它就不是给人看的。因为它只要得出结论：对于站在(0,0,0)的观察者，当他将视线向右偏移\alpha度，然后向下偏移\beta度后，这个点在显示屏上的坐标是(\frac{dx\cos\alpha-dz\sin\alpha}{x\sin\alpha\cos\beta-y\sin\beta+z\cos\alpha\cos\beta},\frac{dx\sin\alpha\sin\beta+dy\cos\beta+dz\cos\alpha\sin\beta}{x\sin\alpha\cos\beta-y\sin\beta+z\cos\alpha\cos\beta})，其中d代表观察者与显示屏的距离。

顺便赠送三角函数机一个->v

#define Pi 3.1415926535898
#define TINY (1e-13)
//输入单位为 度
double sin(double x){
    x=x*Pi/180;
    double n=x,sum=0;
    for(int i=1;(n<0?-n:n)>=TINY;++i){
        sum+=n;
        n=-n*x*x/(2*i)/(2*i+1);
    }return sum;
}
#define cos(x) sin(90-x)
#define tan(x) (sin(x)/cos(x))

以及投影机一个->v

struct x2d{
    double x,y;
};
struct x3d{
    double x,y,z;
};
long dis,sx,sy;//分别代表观察点离显示屏的距离，窗口宽度，高度。
double rx,ry,nx,ny,cx,cy;
nx=sin(rx);//rx,ry分别代表视线在水平，竖直方向上的旋转角度。
ny=sin(ry);
cx=cos(rx);
cy=cos(ry);//同一帧内，角度不改变，所以预处理加速
double getzpos(x3d ps){
    return -nx*cy*ps.x-ny*ps.y+cx*cy*ps.z;
}x2d getpos(x3d ps){
    x2d ret;
    double z=getzpos(ps);
    ret.x=dis*(cx*ps.x+nx*ps.z)/z;
    ret.y=dis*(-nx*ny*ps.x+cy*ps.y+ny*cx*ps.z)/z;
    ret.x+=sx>>1;//实际绘图时，坐标位于屏幕左上角而不是中心
    ret.y+=sy>>1;
    return ret;
}

连线

一次函数

易证：三维空间中的线段投影到平面上依然是线段。

因此只要给出线段两个端点的坐标，可以使用一次函数进行轻松绘制。欢迎残缺代码->v

struct x2d{
    double x,y;
};
void drawline(x2d f,x2d t){//连接一条从f到t的线
    if(f.x<0&&t.x<0)return;
    if(f.x>=sx&&t.x>=sx)return;
    if(f.y<0&&t.y<0)return;
    if(f.y>=sy&&t.y>=sy)return;
    double dx=t.x-f.x,dy=t.y-f.y,a;
    long i;
    if(dx==0&&dy==0){
        drawpoint(f.x,f.y,color[1]);//color是颜色值
        return;
    }if(abs(dx)<abs(dy)){
        a=f.x-f.y*dx/dy;
        if(f.y>t.y)swap(f,t);
        if(f.y<0)f.y=0;
        if(t.y>=sy)t.y=sy-1;
        for(i=f.y;i<=t.y;++i)if(i*dx/dy+a>=0&&i*dx/dy+a<sx)drawpoint(i*dx/dy+a,i,color[1]);
    }else{
        a=f.y-f.x*dy/dx;
        if(f.x>t.x)swap(f,t);
        if(f.x<0)f.x=0;
        if(t.x>=sx)t.x=sx-1;
        for(i=f.x;i<=t.x;++i)if(i*dy/dx+a>=0&&i*dy/dx+a<sy)drawpoint(i,i*dy/dx+a,color[1]);
    }
}

然而存在一种更贱的情况：

出界与射线

当线段AB分列于观察者O的前后两侧时，根据上述方法计算，它在显示屏上的成像将会是CD。然而根据一眼法得出的结论，它的成像应该是DE。当机器与眼睛冲突的时候，当然是相信自己的眼睛。

于是就需要修改。首先判断目标点在观察点的前方还是后方。这个可以直接用旋转后的Z轴坐标来判断。若x\sin\alpha\cos\beta-y\sin\beta+z\cos\alpha\cos\beta>0，则目标在前方，否则在后方。当两个点都在前方时，可以直接绘制；当两个点都在后方时，无需绘制；而当其一前一后时，就需要特殊处理了。

处理方法多姿多彩，我使用的方法是连接AB，与OF相交于F，取AF中点G，此时可以保证G点一定在O点前方。对A点和G点进行计算，得到C点和H点，射线CH就是AB的投影。

公式也十分好推，当视线正对Z轴正方向时，有O(0,0,0)\quad A(u,v,w)\quad B(x,y,z)，其中z<0<w。显然，F点坐标为()

拖欠公式一个^

拖欠图片一张，数据一组

实现画射线的功能很简单，在drawline函数中添加以下部分即可->v

void drawline(x2d f,x2d t,bool b/*新增部分*/)
//b为1时画射线，为0时画线段

a=f.x-f.y*dx/dy;
if(b){                  //新
    if(f.y<t.y)t.y=sy-1;//增
    else t.y=0;         //部
}                       //分
if(f.y>t.y)swap(f,t);

a=f.y-f.x*dy/dx;
if(b){                  //新
    if(f.x<t.x)t.x=sx-1;//增
    else t.x=0;         //部
}                       //分
if(f.x>t.x)swap(f,t);

旋转与移动

玩家终归是要移动的，所以看这个：(x\cos\alpha-z\sin\alpha,x\sin\alpha\sin\beta+y\cos\beta+z\cos\alpha\sin\beta,x\sin\alpha\cos\beta-y\sin\beta+z\cos\alpha\cos\beta)

大意是说：当一个点坐标为(x,y,z)时，将坐标轴水平顺时针旋转\alpha度，然后向下旋转\beta度后，它的坐标就是上面那一位。

也就是说：如果观察点在(0,0,0)，将视线如此偏转后，然后向右行走x，向上行走y，向前行走z，那么你的坐标就是(x\cos\alpha-z\sin\alpha,x\sin\alpha\sin\beta+y\cos\beta+z\cos\alpha\sin\beta,x\sin\alpha\cos\beta-y\sin\beta+z\cos\alpha\cos\beta)。

将矩阵翻转，代码呼之欲出：

add=114514;//常数，根据具体的比例和移动速度决定
if(GetAsyncKeyState('A')){
    m.x-=add*cx;
    m.z-=add*nx;
}if(GetAsyncKeyState('D')){
    m.x+=add*cx;
    m.z+=add*nx;
}if(GetAsyncKeyState('E')){
    m.x+=add*nx*ny;
    m.y-=add*cy;
    m.z-=add*cx*ny;
}if(GetAsyncKeyState('Q')){
    m.x-=add*nx*ny;
    m.y+=add*cy;
    m.z+=add*cx*ny;
}if(GetAsyncKeyState('S')){
    m.x+=add*nx*cy;
    m.y+=add*ny;
    m.z-=add*cx*cy;
}if(GetAsyncKeyState('W')){
    m.x-=add*nx*cy;
    m.y-=add*ny;
    m.z+=add*cx*cy;
}

甚至压行：

x3d f;
f.x=f.y=f.z=0;
if(GetAsyncKeyState('A'))f.x-=add;//GetAsyncKeyState函数返回按键情况
if(GetAsyncKeyState('D'))f.x+=add;//按键按下返回非0，抬起返回0
if(GetAsyncKeyState('E'))f.y-=add;//询问字母键时应使用大写字母
if(GetAsyncKeyState('Q'))f.y+=add;//其他控制键的宏定义在winuser.h的190行至350行
if(GetAsyncKeyState('S'))f.z-=add;
if(GetAsyncKeyState('W'))f.z+=add;
m.x+=cx*f.x-nx*ny*f.y-nx*cy*f.z;
m.y+=cy*f.y-ny*f.z;
m.z+=nx*f.x+cx*ny*f.y+cx*cy*f.z;

还有各种稀奇古怪的移动方式，如重力模式，星舰模式等，根据上述公式均可实现，不一一赘述。

于是你就通晓了《开门见山》中的全部道理，然而还有一个问题，你可以透过一个方块看见另一个方块，这就使得对于某些图片，你并不知道它是凹是凸，孰上孰下甚至可以隔板猜物，这非常不好，于是就要有请：

消隐算法

[以旧换新]()

消隐算法顾名思义，是指找到屏幕上被其他面遮挡的物体，并将其消去的算法。如今市面上流行的消隐算法主要是：八叉树v

八叉树

顾名思义是一棵树，其中每个节点最多有8个儿子。这是一个基于思想的经典算法。

结构与建树

八叉树从一个包含所有顶点的大正方体开始，将三维空间中的每一维都进行二分处理，得到八个形状完全相同，且与父节点相似的正方体，重复这一过程，直到每个节点中只有一个顶点。

拖欠图片一张，数据一组

建树道理显然，先选取一个足够大的大正方体，将所有点放入这个大正方体内，然后搜索建树。对于每个节点，如果点数

>1，为它申请8个儿子节点，枚举点的坐标，将点放入范围内的儿子节点。

==1，将该节点设置为叶子节点，结束。

==0，删除该节点，因为它无意义，即使它包含数个面的一部分，也仍然无意义。

这样一来，就可以保证每个叶子节点都只包含一个点。

拖欠代码一段

//今后有时间再更