Shaun's Space

前言

　　最近由于项目部署需要，简单学习了 docker 的使用和回顾下 CentOS 中的常用操作。

前言

　　最近由于项目部署需要，简单学习了 docker 的使用和回顾下 CentOS 中的常用操作。

Docker 篇

　　由于 Shaun 此次需要安装的环境有点偏门，没找到有完全符合要求的镜像，同时也趁着这次机会学一下 docker，所以就还是直接从最开始的装起了。

　　首先使用 docker pull centos:7 拉取 CentOS7 的系统镜像，使用 docker images 查看已有的本地镜像信息，使用 docker ps -a 查看当前已有的容器信息，去掉参数 a ，即显示正运行的容器，docker stop [container id | name] 可关闭指定容器，docker start [container id | name] 可打开指定容器，docker rm [container id | name] 可删除指定容器，docker rmi [image id | name] 可删除指定镜像，再删除镜像之前需要先删除依赖该镜像的所有容器。

　　使用 docker run -dit -p 80:80 -p 8080:8080 --name CentOS7 centos:7 bash 开启一个新的容器，其中参数的意义为： -i: 交互式操作；-t: 终端；-d: 后台启动；-p: 设置主机的端口映射到容器内的端口；-name: 指定容器名称；最后的 bash 代表使用 bash 终端。在 windows 中直接使用 docker run 运行镜像时会出现 the input device is not a TTY. If you are using mintty, try prefixing the command with 'winpty' 的错误，前面加上 winpty 即可，即 winpty docker run ...。当没有参数 d 时，则直接进入容器，而当存在参数 d 时，由于容器实在后台启动，进入容器时需要执行 docker exec -it [container id | name] bash 才能进入容器，而退出容器可以输入 exit 命令。

　　而为了在容器中可以开启后台服务，需要在开启容器时就进行提权，在 Windows 中提权命令为 docker run -dit --privileged=true --name CentOS7 centos:7 init；而在 Linux 中提权命令为 docker run -dit --privileged=true --name CentOS7 centos:7 /usr/sbin/init。

　　在新开启的容器中添加数据和相应的环境之后，即可使用 docker commit CentOS7 new_image:tag 生成一个新的镜像（生成镜像之前最好关闭容器），该镜像包含已经安装的环境和数据，再使用 docker save -o centos7.tar new_image:tag，可将生成的镜像导出成 tar 包，在其他机器中使用 docker load -i centos7.tar 即可导入该 tar 包，并生成相应的镜像，从而简单便捷的完成环境和数据迁移部署任务。

　　容器有时需要和主机之间传输文件，有两种方案，一种是直接采用共享文件夹的方式，设置某个目录为两系统的共享目录，从而实现文件传输；另一种是使用 docker cp 命令，使用 docker cp src_path container:dst_path 将主机的文件拷贝到容器中；使用 docker cp container:src_path dst_path 将容器的文件拷贝到主机中。

CentOS 篇

安装PostgreSQL12

CentOS安装PostgreSQL

# Install the repository RPM:
yum install -y https://download.postgresql.org/pub/repos/yum/reporpms/EL-7-x86_64/pgdg-redhat-repo-latest.noarch.rpm

# Install PostgreSQL:
yum install -y postgresql12-server

# Optionally initialize the database and enable automatic start:
/usr/pgsql-12/bin/postgresql-12-setup initdb
systemctl enable postgresql-12
systemctl start postgresql-12

#开启远程访问
修改/var/lib/pgsql/10/data/postgresql.conf文件，
取消 listen_addresses 的注释，将参数值改为“*”

修改/var/lib/pgsql/10/data/pg_hba.conf文件，增加下
# IPv4 local connections:
host all all 127.0.0.1/32 md5
host all all 0.0.0.0/0 md5

# 给数据库postgres用户分配密码 1
psql -U postgres
alter user postgres with encrypted password '1';

# 重启服务
systemctl restart postgresql-12

由于需要切换账户，所以最好在第一步安装完之后就使用 passwd [username] XXXXXX 设置 root 和 postgres 两个账户的密码。

安装postgis

（https://yum.postgresql.org/12/redhat/rhel-7-x86_64/repoview/）

# 解决依赖
yum install epel-release 

yum install -y https://yum.postgresql.org/12/redhat/rhel-7-x86_64/postgis30_12-3.0.2-2.rhel7.x86_64.rpm

# 安装pgrouting 
yum install -y https://yum.postgresql.org/12/redhat/rhel-7-x86_64/pgrouting_12-3.0.2-1.rhel7.x86_64.rpm

# 安装ogr_fdw 
yum search ogr_fdw # 查询
yum install ogr_fdw # 安装

postgres 移除扩展 drop extension postgis cascade;。

安装Java

（https://www.cnblogs.com/bcomll/p/12142747.html）

# 搜素java
yum search java | grep -i --color JDK

#安装
yum install java-11-openjdk

# 配置环境变量
vi /etc/profile
# 加入内容
export JAVA_HOME=/usr/lib/jvm/java-11-openjdk-11.0.8.10-0.el7_8.x86_64
export CLASSPATH=.:$JAVA_HOME/jre/lib/rt.jar:$JAVA_HOME/jre/lib/dt.jar:$JAVA_HOME/lib/tool.jar
export PATH=$PATH:$JAVA_HOME/bin

# 重启环境
source /etc/profile

安装GeoServer

（https://blog.csdn.net/weixin_34205076/article/details/88734828）

mv /tmp/geoserver-2.13.2 /usr/share/geoserver

### 添加环境变量
vi /etc/profile
# 追加
export GEOSERVER_HOME=/usr/share/geoserver
# 重新加载/etc/profile文件
source /etc/profile

# 授权
chown -R root:root /usr/share/geoserver

#### 改造启动脚本
vim /usr/share/geoserver/bin/startup.sh
     
# 在最上面引入环境变量
source /etc/profile
     
# 最后执行改为nohup，并将日志输入到 var/log/geoserver.log
nohup "$_RUNJAVA" $JAVA_OPTS $MARLIN_ENABLER -DGEOSERVER_DATA_DIR="$GEOSERVER_DATA_DIR" -Djava.awt.headless=true -DSTOP.PORT=8079 -DSTOP.KEY=geoserver -jar start.jar 1>/dev/null 2>/var/log/geoserver.log &

#### 修改停止脚本
vim /usr/share/geoserver/bin/shutdown.sh
# 在最上面引入环境变量
source /etc/profile

#### 创建服务
vim /lib/systemd/system/geoserver.service  
     
[Unit]
Description=geoserver service
After=network.target
     
[Service]
Type=forking
LimitNOFILE=65536
ExecStart=/usr/share/geoserver/bin/startup.sh
ExecReload=
ExecStop=/usr/share/geoserver/bin/shutdown.sh
Restart=on-abort
     
[Install]
WantedBy=multi-user.target


## 开机自启
systemctl enable geoserver
## 开启服务
systemctl start geoserver

安装 nginx

yum install nginx # 下载并安装nginx

systemctl start nginx # 启动nginx服务

　　在 /etc/nginx 下可修改 nginx.config 文件，监听端口默认是 80，直接输入本地地址可能并打不开网页，因为直接这样安装的 nginx 的可能“有毒”，在 /usr/share/nginx/html 目录中 index.html 可能并不是一个 html 文件，而只是快捷方式，需要从别的地方拷贝一个真正的 index.html 文件替换该文件才可正常打开网页。

安装 nodejs

（https://github.com/nodesource/distributions）

curl -sL https://rpm.nodesource.com/setup_10.x | bash -

yum install -y nodejs

VSCode 远程篇

　　需要安装 VSCode 远程开发插件 https://marketplace.visualstudio.com/items?itemName=ms-vscode-remote.vscode-remote-extensionpack，包括（Remote - WSL，Remote - Containers，Remote - SSH）。

在远程资源资源管理器中切换到 SSH Targes 标签，点击设置设置，在 C:/Users/用户名/.ssh/config 中输入

Host [随便写]
  HostName remote-ip 或 域名
  User 远程服务器用户名

　　配置SSH，通过命令 ssh-keygen -t rsa -b 4096 生成密钥对（在 C:/Users/用户名/.ssh/ 目录中），将公钥内容拷贝到远程服务器/root/.ssh/authorized_keys 中，修改配置文件 /etc/ssh/sshd_config，取消 #PubkeyAuthentication yes 注释，允许使用基于密钥认证的方式登录。重启 sshd 服务 systemctl restart sshd。通过 VSCode ssh 远程连接在结束之后最好将终端全部删除，尤其是最开始的那个 install server 终端。

　　设置好SSH之后，通过在 VSCode 中设置 "docker.host":"ssh://your-remote-user@your-remote-machine-fqdn-or-ip-here"，可以直接连接在远程服务器上的 docker。该设置最好用于工作区设置，而不是用户设置。

　　VSCode 远程连接 SSH 有时可能会出现无法连接，一直尝试连接的现象，这时需要粗暴的删除 ~/.vscode-server 目录，重新进行连接，不行的话就只能参考: https://stackoverflow.com/questions/56718453/using-remote-ssh-in-vscode-on-a-target-machine-that-only-allows-inbound-ssh-co，先关闭远程服务器上已存在的所有 vscode-server 进程，通过 https://update.code.visualstudio.com/commit:$COMMIT_ID/server-linux-x64/stable 下载 tar 包，使用 tar -xvzf vscode-server-linux-x64.tar.gz --strip-components 1 后再重新连接。

后记

　　据查 docker 依然存在很多缺点，尤其是守护进程，Shaun 这两天在 Windows 中使用 Docker 也时不时的出现 docker 卡死的问题，需要重启 docker 服务，以后有机会还是使用 Podman 吧。RedHat 系的 yum 也快退休了，以后再需要安装软件可能就直接上毒奶粉（bushi）dnf 了。VSCode 远程开发是真的舒服，文件无缝传输，任意修改，可以尽情享受现代编辑器的方便。

2020-10-18

空间中三角形与三角形相交

Image&Graphic

algorithm geometry

前言

　　一种快速判断空间中三角形与三角形相交的方法，出自论文：Tomas Moller. A Fast Triangle-Triangle Intersection Test. Journal of Graphics Tools, 1997, 2(2):25-30. ，与「快速判断三角形与长方体相交」中那篇论文的作者是同一个人。

前言

相交篇

　　该论文的理论基础部分来自分离轴理论，论文中三角形与三角形的相交测试主要可分为 3 类：1、沿三角形所在平面法线方向的相交测试；2、沿三角形所在两平面交线方向的相交测试；3、共面时的相交测试。下面来逐步分析这些相交测试。

沿法线方向相交

　　沿法线相交很简单，直接使用分离轴理论分别判断两三角形在对应两条法线上的投影是否相交，若存在一条法线使投影不相交，则可直接判定两三角形不相交，若投影都相交，则存在两种情况，一种是两三角形共面，一种是两三角形相互跨立，判断这两种情况的依据为计算两段投影之间的距离，具体计算方法为：计算三角形 B 上三个点到三角形 A 所在平面的距离，距离计算的方法可参考「计算几何基础—点到平面的距离」，此距离同时需要保留方向，若三个点的距离都为 0，则两三角形共面；若三个距离都同号，则说明投影不相交，即两三角形不相交；若三个距离存在异号现象，则 B 跨立 A。

沿交线方向相交

　　若两三角形相互跨立，则需要判断两三角形是否在两三角形所在平面交线上存在相交。由于两三角形相互跨立，则两三角形必然都与交线相交，则需要分别计算两三角形与交线的交点，根据交点判断两交线段是否相交，若相交，则可直接判定两三角形相交，若不相交，则同样可直接判定两三角形不相交。

　　问题的关键现在在于求取两交线段，比较粗暴的方式为：先求出两平面的交线，交线的方向向量为两三角形所在平面法向量的的叉积，交线上的一点通过联立两平面方程进行求取，由于是两个方程求 3 个未知数（x，y，z），所以理论上有无数个解，令交线方向向量绝对值最大的分量对应的未知数为 0，消除一个未知数，还剩两个，可得唯一解，即可求出交线上一点，亦可得到直线参数方程，求两交线段相当于求四个交点，根据直线与线段相交可得到交点，进而得到交线段。

论文中的方法为：求出交线的方向向量 D 后，设 O 为交线上任意一点（不需要求），则交线方程为 $L= O+tD$，此时求交线段只需要求出 4 个 t。先求交线与三角形 A 的交线段，设三角形 A（V0，V1，V2）三个顶点到三角形 B 所在平面的距离分别为 $d_0,d_1,d_2$，设 $d_1$ 与其它两个距离异号，则交线分别与 V0V1 和 V2V1 相交，先求与 V0V1 相交时的 t1，设三角形 B 所在的平面为平面 B，V0 和 V1 在平面 B 上的投影分别为为 K0 和 K1，V0 和 V1 在交线上的投影分别为为 P0 和 P1，交线与 V0V1 的交点为 C1，设 $P0=O+p_0D,P1=O+p_1D,C1=O+t_1D$，则 $p_0=(V0-O)·D,p_1=(V1-O)·D$，由论文中图二可知，有两组三角形相似，分别为 V0C1K0和V1C1K1 相似，以及 V0C1P0和V1C1P1 相似，所以 \[ \frac{V0K0}{V1K1} = \frac{V0C1}{V1C1} = \frac{C1P0}{C1P1} \Rightarrow \frac{d_0}{d_1} = \frac{p_0-t_1}{p1-t_1} \Rightarrow t_1 = \frac{d_0p_1-d_1p_0}{d_0-d_1} \] 若点 O 为原点在交线上的投影，则 $(V0-O)·D=V0·D=p_0, 　p_1=V1·D$，若将交线投影到交线方向向量绝对值最大的分量对应的坐标轴上，在该投影交线上进行相交测试与在原交线上进行相交测试是等效的，所以此时 $p_0,p_1$ 即为 V0 和 V1 上对应坐标轴的分量。同理可求出 t2，t3 ，t4，两交线段为 t1t2 和 t3t4。

共面相交

　　判断共面相交，相当于判断 2 维中两三角形是否相交，先将三角形投影到 XOY，XOZ，YOZ 平面中投影面积最大的平面（为避免计算面积，可直接令三角形顶点坐标中对应法向向量中绝对值最大的分量为 0，即若法向向量中绝对值最大的分量为 y，则将三角形投影到 XOZ 平面），判断投影后的两三角形是否相交即可，因为此时的两三角形相交，当且仅当其投影三角形相交。2 维中两三角形是否相交，论文中方法是先判断两三角形的边是否相交，即相当于判断 9 组线段是否相交，若存在一组相交，则两三角形相交，若都不相交，则需要判断其中一个三角形是否被另一个三角形包含，具体判断方式取三角形 A 中一顶点，若该顶点在三角形 B 内（判断 2 维中点在多边形内的方法同样可参考「计算几何基础」），则说明三角形 A 在 B 内，同样也需要判断 B 是否在 A 内，若都不在，则两三角形不相交，否则两三角形相交。当然，也可以直接通过分离轴理论来判断两三角形是否相交，毕竟，这就是在 2 维中，而且三角形算是天然的凸多边形。

后记

　　三角形是图形学中组成面的基本单元，图形学中面与面的碰撞检测都可以很粗暴的用三角形相交来实现，只不过直接一个个判断效率有点低就是了，所以一般会借助一些基于的树和包围盒空间加速结构，或者针对某种形状的特殊方法，这又是新的方法系列了。

前言

　　由于本篇主要是谈谈基础，所以一些快速运算方法一般不在本篇探讨范围之内，一些特殊的快速手法等后续专门独立开篇再谈。

前言

　　由于本篇主要是谈谈基础，所以一些快速运算方法一般不在本篇探讨范围之内，一些特殊的快速手法等后续专门独立开篇再谈。

基础篇

解线性方程组：令 $A$ 为 $n×n$ 的矩阵，$α$ 和 $β$ 为 n 维的列向量，设 $A = \begin{bmatrix} \alpha_1 & \alpha_2 & \alpha_3 & ... & \alpha_n \end{bmatrix}$，对于线性方程组 $Ax = β$，初等数学中最常规的就是消元法了，但在线性代数中，有两种解法，一种是等式两边同乘 $A$ 的逆阵，得到 $x = A^{-1}β$；另一种是克莱姆法则，可得 $x_i = |A_i| / |A|$，其中 $|A|$ 为矩阵 $A$ 对应的行列式， $|A_i|$ 为将矩阵 $A$ 中第 $i$ 列换成 $β$ 后对应的行列式，如 $x_3 = \left| \begin{array}{cccc} \alpha_1 & \alpha_2 & \beta & ... & \alpha_n \end{array} \right| / |A|$。

向量内积：又称向量点积，向量点乘。设 a，b 为空间中两个 n 维向量 $a=(x_1,x_2,x_3,...,x_n)$，$b=(y_1,y_2,y_3,...,y_n)$，则 $a·b=|a|*|b|*cos(α)=\sum\limits_{i=1}^{n}x_iy_i$，其中$|a|= \sqrt{(x_1)^2+(x_2)^2+(x_3)^2+...+(x_n)^2},\alpha$ 为两向量之间夹角。向量内积一般用来计算投影（令 $|b|=1$，则 $a \cdot b=|a|cos(α)$，即为向量 a 在 b 上的投影），和两向量之间角度。

向量外积：又称向量叉积，向量叉乘，$|a×b|=||a|*|b|*sin(\alpha)|$。向量外积一般只针对二维向量和三维向量，对于二维向量，$a×b=a.x*b.y-b.x*a.y$，可以认为是一个值（其实也是一个向量），对于三维向量 $a×b=(a.y*b.z-b.y*a.z, a.x*b.z-b.x*a.z, a.x*b.y-b.x*a.y)$，是一个向量，且该向量一定垂直于 a，b 两向量构成的平面，所以三维向量的外积一般可以用来计算平面的法向量。向量外积的几何意义为两向量构成平行四边形的面积，二维向量外积直接取绝对值即为面积，不取绝对值则可以用来判断两向量构成三角形的点是以顺时针排列（小于 0）的还是逆时针排列（大于 0）的，三维向量外积取所得向量的模即为面积。

向量混合积： 设 $a$，$b$，$c$ 为空间中三个向量，则其混合积 $(a,b,c)= (a×b)·c = -(c×b)·a = -(a×c)·b$，$(a,b,c) = (b,c,a) = (c,a,b)$。若 $a$，$b$，$c$ 都为 3 维的向量，矩阵 $A = [a, b, c]$，则 $|A| = (a, b, c)$ ，其中 $a,b,c$ 是列向量或行向量都可以，因为 $|A| = |A^T|$，该混合积的几何意义为这三个向量组成的平行六面体的体积。

直线参数方程：设 P 为直线上任意一点，若 P1 和 P2 为直线上已知两点，则 $P=P1 + (P2-P1)*t, t\in[-∞,+∞]$。当然直线的参数方程有很多种形式，之所以用两点式，是因为两点式除了能表示直线，同样能表示射线（$t\ge 0$），也能表示线段（$0\le t\le 1$）。

平面方程：设 P 为平面上任意一点，O 为平面上已知一点，n 为平面法向量，则平面方程为：$(P-O)·n=0$ 。

三角形内的点：设 P0，P1，P2 为三角形 3 个顶点，若 P 为三角形内一点，同时可认为 (P1-P0) 和 (P2-P0) 为一组基向量，则 P 满足 $P=P0+u*(P1-P0)+v*(P2-P0),u \in [0,1],v \in [0,1],u+v\le 1$。

距离篇

　　一般的距离计算都是向量计算，要么点乘，要么叉乘。

点到直线的距离

　　计算点到直线的距离通用的解法是使用向量叉乘，设 P 为直线外一点，Q1 和 Q2 为直线上两点，则可得到两向量 $a=P-Q1, b=Q2-Q1$，则 P 到直线的距离为 $d=|a×b|/|b|$，叉乘是面积，而面积又等于底乘高，$|b|$ 为底，$d$ 为高。当然点到直线的距离还有其他的一些方法，如利用公式，利用点积再使用勾股定理，直接利用点积计算直线法向量上的投影等，这些方法都有一定的局限性。

点到线段的距离

　　设 d 为点 P 到线段的距离，表示为点 P 到线段上最近点的距离，设 P1，P2 分别为线段两端点，计算 $a=(P-P1)·(P2-P1) / |P2-P1|$，若 $0≤a≤1$，则 d 为点 P 到线段所在直线的距离，若 $a<0$，则 d 为点 P 到点 P1 的距离，若 $a>1$，则 d 为点 P 到点 P2 的距离。

三维中点到三角形的距离

　　先计算点 P 到三角形所在平面的投影点 $P'$，若 $P'$ 在三角形内，则只需要求点 P 到三角形所在平面的距离，否则需要分别求点 P 到三角形三条边的距离（点到线段的距离），取三个距离中最小值即为点到三角形的距离。

点到平面的距离

　　直接利用点乘计算，平面外一点与平面内一点构成的向量到平面法向量上的投影，即为点到平面的距离。设 P 为平面外一点，O 为平面内一点，n 为平面法向量，则点 P 到平面的距离为 $d=(P-O) \cdot n$。

直线到直线的距离

　　设 P1 和 P2 为直线 1 上两点，Q1 和 Q2 为直线 2 上两点，则直线 1 与直线 2 之间的距离计算流程为：

先判断两直线是否平行，即 $(P2-P1) = k*(Q2-Q1), k \neq 0$ 有解。若平行，则相当于计算点到直线的距离；若不平行，则进行下一步。
再判断两直线是否共面，即 P1，P2，Q1，Q2 四点共面，先计算 $n=(P2-P1)×(Q2-Q1)$，再分别计算 $n·(Q1-P1), n·(Q2-P1), n·(Q1-P2), n·(Q2-P2)$，若这四个值都为 0 ，则两直线共面（之所以需要判断 4 个值，是为防出现 3 点共线情况，当然也可以先判断 3 点共线，再取不共线的一点构成向量与 n 做点积进行判断），若两直线共面，则两直线必然相交；若两直线不共面，则两直线间距离为 $d=(Q1-P1) \cdot n$。

直线到平面的距离

　　设 P1 和 P2 为直线上两点，n 为平面法向量，则直线与平面之间的距离计算流程为：

先判断直线与平面是否平行，即若 $(P2-P1) \cdot n = 0$ ，则直线与平面平行，则直线到平面的距离为点 P1 到平面的距离；
若直线与平面不平行，则直线与平面必相交。

相交篇

　　一般的相交求交点都是联立方程组，但有些只需要做相交测试的，可以利用一些特殊方法快速求出来。有些相交直接求很麻烦或很难，可以反向求不相交的情况，而在实际编程中，一般都有很多条件语句，以便快速返回提高效率。

直线与直线相交

　　设直线 1 方程为 $P=P1 + (P2-P1)*t$，直线 2 方程为 $P=Q1 + (Q2-Q1)*u$，联立两方程得 $P1 + (P2-P1)*t = Q1 + (Q2-Q1)*u$，即 $P1-Q1 = (Q2-Q1)*u - (P2-P1)*t$，设 $v_0=Q2-Q1,v_1=P1-P2,v_2=P1-Q1$，即 $v_0*u+v_1*t=v_2$，现在的问题就是解这个方程了，一种是直接把向量分解成单一维度，列方程组；一种是等式两边分别同时点乘 $v_0$ 和 $v_1$，可得 \[ \begin{cases} (v_0 \cdot v_0)*u+(v1 \cdot v_0)*t=v_2 \cdot v_0 , \\ (v_0 \cdot v_1)*u+(v1 \cdot v_1)*t=v_2 \cdot v_1 \end{cases} \] 解得： \[ \begin{cases} u=((v1·v1)(v2·v0)-(v1·v0)(v2·v1)) / ((v0·v0)(v1·v1) - (v0·v1)(v1·v0)) , \\ t = ((v0·v0)(v2·v1)-(v0·v1)(v2·v0)) / ((v0·v0)(v1·v1) - (v0·v1)(v1·v0)) \end{cases} \] 若方程有解，则两直线相交，由于两点式方程可以很简单的转换为线段和射线，所以该方法同样可以判断两线段相交，两射线相交，射线与直线与线段相交等。针对二维直线，还有一种解法是将原方程写成矩阵形式，利用克莱姆法则进行求解，不过总的来说，最终的解都是一种形式。

直线与平面相交

　　求直线与平面相交，直接联立直线方程和平面方程即可，得 $(P1-O+(P2-P1)*t)·n=0$ ，即 $t=(P1-O)·n/((P1-P2)·n)$。若 t 有解，则直线与平面相交。同样也可以用该方法判断线段或射线与平面相交。

直线与三角形相交

　　二维中判断直线和三角形相交相当于判断直线和线段相交，而在三维中则同样需要联立直线和三角形方程，设直线方程为 $P=P1+(P2-P1)*t$，三角形方程为 $P=Q1+(Q2-Q1)*u+(Q3-Q1)*v$，则联立后方程为 $P1-Q1=(P1-P2)*t+(Q2-Q1)*u+(Q3-Q1)*v$，令 $V_0=P1-Q1,V_1=P1-P2,V_2=Q2-Q1,V_3=Q3-Q1$，则 $V_0=V_1*t+V_2*u+V_3*v$，可以分解向量求解，也可以使用克莱姆法则得： \[ t = \frac{\begin{vmatrix} V_0 & V_2 & V_3 \end{vmatrix}}{\begin{vmatrix} V_1 & V_2 & V_3 \end{vmatrix}} \qquad u = \frac{\begin{vmatrix} V_1 & V_0 & V_3 \end{vmatrix}}{\begin{vmatrix} V_1 & V_2 & V_3 \end{vmatrix}} \qquad v = \frac{\begin{vmatrix} V_1 & V_2 & V_0 \end{vmatrix}}{\begin{vmatrix} V_1 & V_2 & V_3 \end{vmatrix}} \qquad \] 由于三阶行列式也可以用向量混合积来求值，所以 \[ t = \frac{-V_0 × V_3 · V_2 }{V_1 × V_2 · V_3} \qquad u = \frac{V_0 × V_3 · V_1 }{V_1 × V_2 · V_3} \qquad v = \frac{V_1 × V_2 · V_0 }{V_1 × V_2 · V_3} \qquad \] 若方程有解，且满足三角形条件，则相交。

二维中凸多边形与凸多边形相交

　　曾在「快速判断三角形与长方体相交」中写过判断两凸多边形是否相交直接使用分离轴理论（separating axis theorem， AST）即可，简而言之就是，取两多边形任意一条边，计算两多边形在该边法向量上的投影是否相交，若存在一条边，使投影不相交，则两凸多边形不相交。

二维中点在多边形内

　　判断点在多边形内有很多种方法，利用叉乘，面积等方法虽然思想简单粗暴但一般计算量较大，且有一定的局限性，仅限凸多边形，但有一种相对快速且能应对各种简单多边形的方法——射线法，射线法的本质是判断射线与线段相交，即从已知点处引一条沿 X 轴正向的射线，若射线与多边形边的相交条数为奇数，则该点在多边形内，该法的缺陷在于若点在边上则需要单独判断。判断该射线与多边形的边是否相交也比较简单，设射线起点为 P0，多边形边的两个端点分别为 P1 和 P2，则射线与边相交需满足的条件为：1、$min(P1.y, P2.y)<=P0.y<=max(P1.y, P2.y)$；2、$P0.x <= (P2.x-P1.x)*(P0.y-P1.y)/(P2.y-P1.y)+P1.x$。

圆与三角形相交

　　判断圆与三角形相交，即判断圆心到三角形各边的距离是否小于圆的半径，若存在一条边，使圆心到其的距离小于半径，则圆与三角形相交，该距离计算不是点到直线的距离，而是点到线段的距离。

直线与长方体相交

　　判断直线与长方体相交，首先需要将坐标原点平移至长方体中心，再计算过原点且垂直于直线的法向量 n ，随后计算原点到直线的距离 d，若满足 $|d| <= h_x|n_x| + h_y|n_y| + h_z|n_z|$ ，则直线与长方体相交。法向量 n 的求法为：设 P 为直线上一点，l 为直线方向向量，则 $n=-(P·l)*l+P$。

球与 AABB 相交

判断球与 AABB 相交，首先需要将坐标原点平移至球心，设平移后的 AABB 最小顶点为 V1，最大顶点为 V2，球半径为 r。最简单粗暴的当然是若原点不在 AABB 内，则直接求原点到 8 个面的距离，取最小值，若最小值比半径大，则不相交。另一种方法是将这个问题转化为求解不等式，若存在一点 $P(x, y, z)$，使 P 在球内，同时 P 在 AABB 中，即： \[ \begin{cases} x^2+y^2+z^2 ≤ r^2 , \\ V1.x ≤ x ≤ V2.x , \\ V1.y ≤ y ≤ V2.y , \\ V1.z ≤ z ≤ V2.z \end{cases} \] 若该不等式有解，则球与 AABB 相交，否则不相交。解该不等式也简单，由于是存在而不是任意，所以只需要求 $min(x^2+y^2+z^2)≤r^2 \Rightarrow min(x^2) + min(y^2)+ min(z^2)≤r^2$，则若 xyz 分量可以取 0，则对应分量取 0，否则取 $x = min(|V1.x|, |V2.x|), y = min(|V1.y|, |V2.y|),z = min(|V1.z|, |V2.z|)$，若满足不等式，则相交。

该方法同样可用来求 OBB 与球相交，只需要先利用坐标系变换将 OBB 转成 AABB。

反射篇

　　令入射向量为 $I$，法向量为 $N$，反射向量为 $R$，入射向量与反射向量构成的平面与镜面交线的方向向量为 $T$，这四个向量都为单位向量。首先以 $I$ 和 $R$ 组成一个菱形，则 $N$ 和 $T$ 则为该菱形对角线的方向向量，若已知 $I$ 和 $R$，则 $N = (R - I).normalize()$，$T = (I + R).normalize()$ ，$normalize()$ 指向量归一化；若已知 $I$ 和 $N$，则 $R = I + 2*|I \cdot N|*N$，$2*|I \cdot N|*N$ 为菱形 $N$ 方向的对角线向量。

　　镜面反射公式为 $(r',g',b') = (r,g,b) + (1-r,1-g,1-b)*t$，当 $t$ 越大则越接近白色，表现为越亮；漫反射公式为 $(r',g',b') = (r,g,b)*t$，当 $t$ 越小，则越接近黑色，表现为越暗。其中 $t\in[0,1]$，$t$ 为入射向量到平面法向量上的投影，即点积。

后记

　　该篇不出意外的话也会是一个长期支持篇，等以后有碰到其他的一些计算几何知识再持续更新吧。

2020-08-09

OpenDrive解析小结

note opendrive

前言

　　接触并使用高精地图和 OpenDRIVE 已有一年的时间，简要写写 Shaun 对 OpenDRIVE 的一些认知。

前言

　　接触并使用高精地图和 OpenDRIVE 已有一年的时间，简要写写 Shaun 对 OpenDRIVE 的一些认知。

基础篇

OpenDRIVE 目前最新的版本的 1.6，下面主要结合 1.4，1.5 和1.6 版本一起看。

　　在 OpenDRIVE 中主要有两种坐标系统，一种是常见的 X/Y/Z 空间坐标系统，另一种是 S/T/H 坐标系统。其中 X/Y/Z 坐标系统常与地理信息的各种坐标系统一起使用，S/T/H 坐标系统是针对 OpenDRIVE 中道路参考线设定的一种局部坐标系统，在 OpenDRIVE 中称前者为 “inertial co-ordinates”，后者为 “track co-ordinates”（1.6 中直接为 Reference Line System）。除此之外，还有个局部坐标系 U/V/Z，该坐标系统系统是相对于 S/T/H 坐标系统平移旋转而来的。

对于旋转，以逆时针为正，heading 是指绕 z/h 轴旋转，pitch 是指绕 y/t 轴旋转，roll 是指绕 x/s 轴旋转。

对于曲率，逆时针延申的曲线曲率为正，顺时针延申的曲线曲率为负。

在 OpenDRIVE 中对于道路和车道的描述，有以下几个重要的概念：

Reference Line。用来指示一条道路的骨架，是 S/T/H 坐标系统的依据，道路中各车道线需要参考这条线。
Lanes。用来描述各车道以及各车道所属 Lane Section。
Lane Offset。其意义在 OpenDRIVE 标准看起来很清除，但实际用起来非常模糊，offset 到底是只能偏移一个车道，或半个车道或多个车道，所属哪个 Lane Section，其意义不明，故下文解析篇将直接忽略该属性。
Lane Section。可以简单理解为子道路，一个 lane section 中包含多条车道，一条道路包含多个 lane section。一个 lane section 中车道数是一个常数，所以对于存在 m 变 n 车道的一条道路，至少要划分为两个 lane section。
Superelevation、Crossfall 和 Shape。用来表示路面倾斜程度。Superelevation 是整个路面侧向太高，即路面倾斜程度，Crossfall 在 1.6 中已被废弃，原因为 1.6 完善了 Shape，可以完全取代 CrossFall，甚至能做的更好，Shape 主要用来描述路面两侧车道的倾斜程度，通过三次曲线和线性插值可以精确到车道各点倾斜程度。
Road Linkage。道路之间的连接关系，通过前继（predecessor）和后继（successor）建立道路之间连接关系，若一条路存在多个前继或后继，则其对应前继或后继应该为 Junction ，即目前的标准中暂不支持道路多前后继，1.5 中只支持车道多前后继，道路多前后继依然不支持。
Junction。交汇处，通俗意义上的路口，主要包含 incomingRoad 和 connectingRoad。
Junction Group。可以简单理解为交通环岛。
Neighbors。相邻关系，和 Road Linkage 类似，一个是前后连接关系，一个侧面相邻关系。
Surface。车道或道路表面材质，有 OpenCRG 则优先使用，没有则由应用程序自定义字符串。
....... 等等。还有一些冷门的元素暂时没用到，就不介绍了。

下面就是真正的解析内容了。

解析篇

　　一些简单的就不介绍了，就介绍解析时需要注意的一些重点元素。

Road Geometry

　　geometry 信息可以说是 OpenDRIVE 中最重要的信息，没有之一。OpenDRIVE 中最重要的元素为 Road，而 Road 中最重要的是 Reference Line，而 geometry 正是用来描述 Reference Line 几何线条形状的信息。

　　首先 geometry 标签中共有 5 个属性，分别为 s （该段 geometry 沿参考线起始位置），x（该段 geometry 在 inertial system 下起始横坐标），y（该段 geometry 在 inertial system 下起始纵坐标），hdg（该段 geometry 在 inertial system 下起始弧度），length（该段 geometry 长度）。其次，geometry 共有 5 种线型，分别为 straight lines（直线），spirals（螺线），arcs（圆弧线），cubic polynomials（三次曲线），parametric cubic polynomials（参数化三次曲线），这 5 种线型分别由 geometry 下 5 种标签控制。解析 geometry 的要点在于：先不用管 geometry 标签中的属性，直接解析对应线型标签，需要满足两点：1、起始点坐标一定为 (0, 0)；2、起始点斜率，即导数也一定为 0。依据这两点正确解析完线型之后，再根据 hdg 旋转线型，根据 (x, y) 将线型平移到正确位置。下面就具体看看这 5 种线型：

line，直线。没有任何属性，直接根据 geometry 中 (x, y) 和 hdg 就可得到直线方程。
spiral，螺线。有两个属性 curvStart（起始曲率），curvEnd（结束曲率）。螺线解析的代码已经由 OpenDRIVE 官方直接给出了，里面涉及到的数值计算方法就不详解了，直接看官方提供 API 的输入输出，输入有两个：s（从原点开始，螺线延展的长度），cDot（螺线的曲率关于 s 的一阶导数）；输出有 3 个：x（横坐标），y（纵坐标），t（该点的切线弧度）。解析螺线最大的问题应该就是如何得到这两个输入参数，由螺线的性质可以得到，螺线的曲率一定随着螺线的长度均匀变化的，换句话说，对于一条已知螺线，cDot 一定是常数。则 $cDot = (curvEnd - curvStart) / length$，其中 length 为 geometry 中的长度属性，下一步需要求出 s，由于已知螺线在原点处的曲率一定为 0，则 (curv - 0) / (s - 0) = cDot，即 s = curv / cDot。由此可得到螺线的各点坐标和切向方向，但由于解析线型需要满足上面说的两点，所以需要将螺线坐标以起始点进行平移和旋转，以满足起始点为原点，起始点切线弧度为 0，最后再将完成平移和旋转后的点根据 geometry 的属性进行旋转和平移以得到真正的坐标点。
arc，圆弧线。只有一个属性 curvature（曲率），可根据曲率直接得到圆的半径，在根据曲率的正负可得到该曲线是以顺时针延申还是逆时针延申，再根据解析线型需要满足的两点和 geometry 的属性可得到真正的 inertial system 中的点。
poly3，三次曲线，在 1.6 中已被废弃。精度要求低一点可直接插值计算，要求高一点则需要利用 length ，数值计算和二分法直接求出最大的 u，然后插值。
paramPoly3，参数化三次曲线。最有名的两个参数化三次曲线就是 Bezier 曲线和 Hermite 曲线，为满足解析线型需要满足的两点，一定有 $a_u=0, a_v=0,b_v=0$，需要注意的是一般参数化曲线的参数取值范围为 $[0,1]$，即该标签最后一个属性 pRange="normalized"，若碰到特殊情况 pRange="arcLength"，则需要将 $a_u,b_u,\dots$ 等属性转化为参数取值范围为 $[0,1]$ 时对应的属性。

最重要的元素 Geometry 的解析就是这样了，下面谈谈 Shaun 对基于三次曲线的一些元素的理解。

　　比较重要的基于三次曲线的元素主要有 elevation（控制路面的高度），superelevation（道路侧面抬高弧度），crossfall（路面两侧弧度，已被废弃），shape（路面两侧形状，特殊，下文详细介绍），laneOffset（车道偏移量），border 和 width（特殊，下文详细介绍），这些元素所使用的三次曲线一般都基于道路参考线（特殊除外），即该三次曲线的横坐标一般为 s，纵坐标即三次曲线的值则为各元素的信息，这些三次曲线一般是分段描述的，即道路参考线上两个关键点的 s 之间必会生成对应的一段三次曲线，每一段三次曲线的横坐标取值范围都为 $[0,poly3Length]$，其中 ploy3Length 为该段三次曲线的长度。这些三次曲线段全部合起来则构成沿道路参考线的一条三次曲线，根据 s 计算三次曲线的取值得到对应的信息。

LaneOffset

　　laneOffset 用来指示的是所有车道沿参考线法线方向的偏移量，所有车道包括中心车道（centerLane），由于中心车道没有宽度，所以也可以叫道路中心线，这和道路参考线是两个概念，若 laneOffset 都为 0，则道路中心线和道路参考线重合。

Shape

　　路面两侧车道的高度，该元素虽然也是使用三次曲线进行描述的，但是该三次曲线的横坐标为 S/T/H 坐标中的 t，不是 s，不同的 t 得到不同的高度，该元素下可能存在多段三次曲线，这些三次曲线段是独立的，只是描述其属性 s 所在位置横截面的 shape，而没有完全指定 s 的横截面的 shape，则由两临近 s 的三次曲线计算相同的 t 对应的高度然后线型插值得到（1.6 标准中插值的公式 Shaun 觉得有问题）。

border 和 width

　　之所以把这个两个元素放在一起写，是因为这两个元素描述的本质上是一个东西，都是车道边界所在的位置。同时，Shaun 还是想吐槽一下，作为一个既定的标准，完全不应该把这两个元素同时放出来，只需要放出一个即可，既然为标准就应该做到完全统一，至于具体用哪个是应用程序的事，但是出来的东西必须得唯一。border 是指车道边界到道路中心线在道路参考线法线上的投影，有正负之分，一般左边车道为正，右边车道为负，而 width 是指车道的宽度，这两者完全可以相互转换。虽然描述这两者的三次曲线是基于道路参考线 s 的，但是这个 s 是相对于 laneSection 标签中 s 属性的，即其真正沿道路参考线的 s' 应该为 s' = s + laneSection.s。

　　至于Junction 的解析好像没什么需要注意的，就不写了，至于 1.5 中的 Virtual Junction，引入新的道路前后继描述方式，也新加了一个 virtual connection，解析时到也没有需要注意的，唯一需要注意是在应用程序中该如何利用这些信息。

　　对于 Signal 和 Object，Shaun 觉得标准中强制规定 s > 0 同样是一件非常不合理的事情，既然能超出道路长度，只准正向超出，不能反向超出，这有点不讲道理。 Signal 和 Object 同样需要注意在应用程序中的用法，至于解析方面，需要注意的应该就是 Object 中 outline 下面的 cornerRoad 和 cornerLocal。

cornerRoad 和 cornerLocal

　　这两个元素描述的本质上也是一个东西，都是面域对象多边形边界上的轮廓点，虽然 1.5 中引入了复杂多边形的概念，即有内轮廓和外轮廓，但 cornerRoad 和 cornerLocal 还是一样的解析。cornerRoad 是直接相对于道路参考线的坐标，即将 X/Y/Z 坐标直接转换为 S/T/H 坐标得到的，所以直接解析转换就可得到该点的真正坐标。而 cornerLocal 的解析则相对要麻烦些，首先根据 object 标签中 s 和 t 属性计算得到 Object 的位置，以道路参考线上 s 所在的位置建立 S/T/H 坐标系统，将该坐标系统平移到 Object 所在位置，即该 S/T/H 系统以Object 的位置为原点，将 cornerLocal 上 u,v,z 属性带入该坐标系统计算出真正的坐标。由于 Object 中的 roll,pitch,hdg 属性，所以还需要对坐标以 Object 的位置为中心进行相应旋转才能得到真正 X/Y/Z 坐标系统中坐标。

好了，以上就是 Shaun 觉得在解析 OpenDRIVE 时需要注意的一些地方了。

后记

　　整个地图行业本来就存在很强的壁垒，国内更是如此，而高精地图作为专为自动驾驶服务的地图，国内估计更是少有人接触过。

　　OpenDRIVE 虽作为一种高精地图标准，但离那种被广泛认可关注的标准还有很长一段距离，虽然它发展了十几年，但奈何整个行业才算是起步阶段，所以之前其一直发展的十分缓慢，之前用 OpenDRIVE 较多的应该是交通仿真领域，这个领域同样存在很强的壁垒，要在这种领域得到整个行业的认可是一件非常困难的事，因为其本来就存在一套自己的格式，而想要应用别人的标准，就势必需要逐渐抛弃自己的格式，这对企业来说需要下很大的决心。

　　就 Shaun 目前所知，行业内虽然有许多企业使用 OpenDRIVE 标准，但基本都是自己魔改后的标准，原因在于 OpenDRIVE 标准还没做到真正成为标准的地步，虽然其一些基本元素具备，但很有很多元素是完全缺失或不完善的，更重要的是，其可视化程序竟然不开源，在整个计算机领域内，还从没见过一种标准没有其开源实现的东西，没有相应的源码，只靠文字来理解难免会产生歧义，各大厂商自然就会选择实现自己的 OpenDRIVE，很难统一。历史上一些经典的论文和算法，都有其相应的开源实现，没有开源实现的论文和算法基本都淹没在了历史长河之中。所以没有开源实现，在计算机领域内很难真正推广开，就很难成为真正的标准。综上，OpenDRIVE 的发展任重而道远啊！希望现在在 ASAM 手中能发展的更快更完善些吧。

前言

　　前段时间做了一件很有意思的事，使用一张普通纹理图片做成了一个天空盒（SkyBox），其实是半个，因为最终形成的天空盒是上下对称的，看起来有天空之境的感觉。

前言

天空盒篇

　　常见的天空盒一般采用立方体包围盒做 geometry，再使用 CubeMap 将 6 张纹理图贴到立方体包围盒上，但是如果只用一张纹理图片，要映射到立方体包围盒上，无论怎么展 UV，都会造成部分棱和顶点 UV 聚集或突变，从而在这样的地方造成贴图扭曲或错位的不协调现象。

　　既然立方体包围盒不可行，就只有采用另一种 geometry —— 球了，但是直接用球作为 geometry 会造成两种问题：1、球的极点处会有扭曲现象，因为球极点处的 UV 是聚集的，同一个位置，V 都为 1 或 0，而 U 则为 [0, 1] 都有，即在该位置处一个 V 对应多个 U，自然会造成扭曲；2、由于球是一个圆周，所以 U 为 0 的位置和 U 为 1 的位置是同一个，对于一张普通纹理图，这就会造成错位，能看到非常明显的接缝线。所以需要重新展开球面的 UV，而常见的展 UV 方法主要有以下几种：

对于平面，uv 坐标自然通过线性归一化解决，取左下角坐标和右上角坐标，得到平面的宽度和长度，再用当前坐标减去左下角坐标，最后除以平面宽度和长度得到 uv 坐标。
对于球面，自然是取水平方位角 $θ, \theta \in [-\pi, \pi]$ 和垂直仰角 $φ, φ\in [0, \pi]$ 作为 uv 坐标。对于 threejs 而言，方位角在 XZ 平面上，可计算 $\theta = Math.atan2(z, x)$，仰角 $φ = Math.acos(-y)$，其中 $x,y,z$ 为当前坐标归一化后的值，则 $u = (θ +\pi)/(2*\pi)$，$v=φ/\pi$。
对于一般的曲面，可能会依据当前顶点的法线计算 uv 坐标。对法线向量 x,y,z 三个分量的值进行排序，取最小的两个作为 uv，或者将最小的两个除以最大的一个作为 uv（CubeMap 中通常用这种进行 6 个面的纹理映射，最大的那个决定映射 6 个面中的哪一面），或者取固定的两个分量作为 uv ，或者得到最小的两个分量索引取对应顶点坐标的分量值作为 uv 等等，若 uv 取值为 [-1,1]，则还需要做 $uv = uv *0.5+0.5$ 。根据法线计算 uv 一般需要根据不同的使用情况选择不同的 uv 计算策略。

　　Shaun 很快的解决了第二个问题，想要将一张普通纹理图片贴在整个球面上而不留下接缝线是不现实的，而铺在半个球面上，另一半球面做对称，这个是可行的，而且看起来的效果也不错，计算 uv 就很简单了，原始的 v 不需要改变，只需要将 u 从 [0, 0.5] 映射为 [0, 1]，从 [0.5, 1] 映射为 [1, 0]，即 \[ f(u)=\begin{cases} 2*u,　0 \le u \le 0.5 \\ 2*(1-u),　0.5 \le u \le 1 \end{cases} \] ，接缝线问题使用对称性巧妙的解决了，但第一个问题，极点扭曲现象，还是没法解决，接下来才是真正的难点 ╯︿╰。

　　为了解决极点扭曲问题，首先需要知道极点扭曲的根本原因是同一个位置对应了多个 uv，所以要么将这些 uv 给散开，要么抛弃一部分 uv，散开 uv 的方式 Shaun 没想出来，抛弃一部分 uv 倒是有一种简单的方式，不过抛弃 uv 也意味着会损失一部分纹理，就这个天空盒而言，抛弃一部分 uv 是能接受的，不然平面到球面必然有形变。具体抛弃方法为，将球面铺平，变为一个大圆面，即忽略球面顶点坐标的 z 值，求出球的 AABB，将 AABB 铺平，即为大圆的外接正方形，用计算平面 uv 的方式重新球上各顶点的 uv 坐标，这种方式的确能解决极点扭曲的问题，但又带来了一个更为严重的问题。

　　这个问题就是，球面上半部分显示很正常，但是越靠近底部大圆的部分，纹理拉伸的越厉害，造成天空盒四周都出现很严重的纹理拉伸现象。出现纹理拉伸现象的原因也很好理解，那就是越靠近底部大圆的顶点，uv 坐标之间的间隔越小，即同样的 uv 间隔，顶点之间的距离变大了，在进行纹理插值时，自然会导致纹理拉伸现象。知道问题出现的原因了，那怎么解决了？这又是一个新问题 😔。

　　导致纹理拉伸现象的原因是线性映射，那能不能对计算好的 uv 进行非线性映射，从而抵消 OpenGL 线性纹理插值的影响，非线性映射最重要的是找到合适的非线性函数，常见非线性函数一般有幂函数（伽马变换就是一种幂函数变换，幂 < 1 拉伸小值，幂 > 1 拉伸大值），对数函数，指数等，对于 Shaun 这里的情况，常规的非线性函数肯定是不行的，只能自己想一个函数。

　　注意到，这是在球面上，要取一个非线性映射函数，自然需要从圆的弧长入手，先计算圆的弧长。计算弧长的本质是勾股定理 $ds=\sqrt{(dx)^2 + (dy)^2} = \sqrt{1+(dy/dx)^2} * dx$，对于圆 $x^2 + y^2 = r^2,　y \ge 0$，即 $y=\sqrt{r^2-x^2}$，有 $dy/dx = -x/ \sqrt{r^2-x^2}$，则对于圆的弧长 $L=\int \sqrt{1+x^2/(r^2-x^2)}dx = r \int 1/ \sqrt{1-(x/r)^2}d(x/r) = r*arcsin(x/r)|$，即对于圆在第一象限的弧长可以为 $L=r*arcsin(x/r),　0\le x \le r$ 。

　　由于 v 是均匀的，所以只需要对 u 进行拉伸即可，离圆心越近的点，则越接近 0.5，离圆心越远的点则越偏离 0.5，非线性拉伸公式为 $ u = α * (u-0.5) + 0.5$，其中 $α = L / (\pi*r/2),　L中的x为点到圆心的距离$，使用这种拉伸后，天空盒四周的纹理拉伸现象确实不见了，但是又引入了新的问题，天空盒顶部出现了局部拉伸现象，出现微弱的纹理模糊，虽然区域不大，依靠一些手段可以让用户看不到这块区域，但是不能自欺欺人，这一块存在总让 Shaun 觉得很不舒服，于是，就有了下面的终极解决方案。

　　Shaun 最终想出解决方案是：既然单纯的拉伸不能完美解决问题，那还是只能从问题根源入手，完全重新计算 uv 坐标，这次计算 uv 坐标，还是需要借助上文的 $α$。具体计算 uv 坐标的方式如下：

先计算球面上顶点相对大圆圆心的角度，即 $angle = Math.atan2(y - center.y, x - center.x)$，其中 center 即为大圆圆心（0, 0）。
根据顶点到圆心的距离得到 $\alpha$，计算 $α_x = α * cos(angle)， α_y=α * sin(angle)$ 。
计算 uv：$u = α_x * 0.5 + 0.5， v=α_y*0.5+0.5$ 。

　　使用这个方式计算 uv，天空盒的全部问题都解决了，天空盒没有任何拉伸扭曲等令人看起来不协调的地方，至于对称也说的过去，Shaun 个人感觉挺漂亮的 (￣▽￣)"。自此天空盒的事就算是告一段落了。

后记

　　做这个天空盒，确实花费了 Shaun 了不少力气，在做的那两天，满脑子都是为什么会拉伸扭曲，以及如何解决拉伸扭曲，最终想出了这套方案，简单优雅，最后的效果也是完美达到了 Shaun 的预期。不过一般人应该也用不到 Shaun 这套方案，这只是 Shaun 自己想做做而已，搞不出来没关系，搞出来当然是好的。

2020-07-26

Windows Terminal 尝鲜小记

record

前言

　　Windows Terminal 正式版在两个月之前终于发布了，正好最近找了点时间尝尝鲜，感觉确实可以，Cmder 可以退休了。

前言

　　Windows Terminal 正式版在两个月之前终于发布了，正好最近找了点时间尝尝鲜，感觉确实可以，Cmder 可以退休了。

尝鲜篇

　　直接在 Microsoft Store 安装，顺便安装好 Powerline，执行以下三个命令：

Install-Module posh-git -Scope CurrentUser
Install-Module oh-my-posh -Scope CurrentUser
Install-Module -Name PSReadLine -Scope CurrentUser -Force -SkipPublisherCheck // 使用 powershell core 则必选

然后执行 notepad $PROFILE ，在弹出的记事本中添加：

Import-Module posh-git
Import-Module oh-my-posh
Set-Theme Paradox

重启 terminal，若出现 “无法加载文件 ***.ps1, 因为此系统上禁止运行脚本”，则需要执行 set-executionpolicy RemoteSigned，使powershell 能顺利执行该脚本。

　　由于目前 Windows Terminal 不会自动注册右键快捷菜单，所以需要手动修改注册表，执行 mkdir "%USERPROFILE%\AppData\Local\terminal" 后，在网上找一个终端图标，命名为 wt_32.ico，将该图标复制到 %USERPROFILE%\AppData\Local\terminal 目录中，新建 wt.reg 文件后直接双击执行，该注册表文件的内容如下：

Windows Registry Editor Version 5.00

[HKEY_CLASSES_ROOT\Directory\Background\shell\wt]
@="Windows terminal here"
"Icon"="%USERPROFILE%\\AppData\\Local\\terminal\\wt_32.ico"

[HKEY_CLASSES_ROOT\Directory\Background\shell\wt\command]
@="C:\\Users\\[user_name]\\AppData\\Local\\Microsoft\\WindowsApps\\wt.exe"

其中 [user_name] 是使用者电脑的用户名，wt_32.ico 可以是随便找的一张缩略图，也可以直接用 icons - yanglr 中的 wt_32.ico。

　　为了简单美化一下 Windows Terminal 界面，需要安装 Cascadia Code GitHub releases page 中 Cascadia Code PL 或 Cascadia Mono PL 字体，Shaun 因为只是尝鲜所以就简单配置了一下：

"theme": "dark",
"profiles":
{
    "defaults":
    {
        // Put settings here that you want to apply to all profiles.
    },
    "list":
    [
        {
            // Make changes here to the powershell.exe profile.
            "guid": "{61c54bbd-c2c6-5271-96e7-009a87ff44bf}",
            "name": "Windows PowerShell",
            "commandline": "powershell.exe",
            "hidden": false,
            "startingDirectory" : ".",
            "acrylicOpacity" : 0.00000001,
            "colorScheme" : "Campbell",
            "cursorColor" : "#00CCFF",
            "fontFace" : "Cascadia Mono PL",
            "useAcrylic" : true
        },
        {
            // Make changes here to the cmd.exe profile.
            "guid": "{0caa0dad-35be-5f56-a8ff-afceeeaa6101}",
            "name": "命令提示符",
            "commandline": "cmd.exe",
            "hidden": false
        },
        {
            "guid": "{b453ae62-4e3d-5e58-b989-0a998ec441b8}",
            "hidden": false,
            "name": "Azure Cloud Shell",
            "source": "Windows.Terminal.Azure"
        }
    ]
},

　　为了在 VSCode 中使用 Windows Terminal ，需要简单设置一下默认终端，首先将设置默认终端 "terminal.integrated.shell.windows" 注释掉或者直接不设置，添加设置：

"terminal.external.windowsExec": "C:\\Users\\[user_name]\\AppData\\Local\\Microsoft\\WindowsApps\\wt.exe",
"terminal.integrated.fontFamily": "Cascadia Mono PL",

如此可在 VSCode 中集成 Windows Terminal，并将其作为默认终端。

后记

　　在这两三天的使用过程中，发现 Windows Terminal 和 Cmder 之间还是存在差距的（如在输入命令过快的时候，tab 键补全跟不上等问题），暂时就两者先并行使用一段时间吧，等后续更新巨硬修复这些问题，相信 Windows Terminal 是能代替 Cmder 成为 Windows 首选终端的。

参考资料

[1] 【避坑】PowerShell：因为在此系统上禁止运行脚本附原因和解决办法

[2] 新发布的Windows Terminal如何添加到右键菜单？

[3] Setting Windows Terminal as Default External Terminal in Visual Studio Code

前言

　　一种快速判断空间中三角形与 box 相交的方法，出自论文：Tomas Akenine-Moller. Fast 3D triangle-box overlap testing. A. K. Peters, Ltd. 2002.

前言

　　一种快速判断空间中三角形与 box 相交的方法，出自论文：Tomas Akenine-Moller. Fast 3D triangle-box overlap testing. A. K. Peters, Ltd. 2002.

预备篇

　　该论文的理论基础来自分离轴理论（separating axis theorem， AST），AST 常用于检测两凸多边形是否相交。一句话描述 AST 即为：若两多边形能用一条直线分隔开，则两多边形不相交。如何判断该直线存在即为 AST 的关键。常用的判断方法为找出两多边形所有边向量（多边形相邻两点构成的向量，顺时针或逆时针都行）的法向量，使用向量点积分别计算两多边形在各法向量上的投影（一般以多边形上的点和原点构成一个向量与法向量做点积），从而得到两个投影集合，判断两集合是否相交（找出两个集合的最大值和最小值，若最小值大于最大值，则不相交），若不相交，则 AST 中的直线存在，即两多边形不相交，若相交，则继续判断在其它法向量上的投影，若所有法向量上的投影都相交，则两凸多边形相交。AST 常用于二维下判断两凸多边形的相交情况，三维下的情况比较复杂。

正文篇

　　该论文给定 13 个向量，若 box 的边和三角形的边在这 13 个向量中的投影均相交，则认为 box 与三角形相交。为简化运算，box 直接假定为轴向包围盒（axis-aligned bounding box， AABB），坐标轴原点为 box 中心，由于可以将普通 box 通过旋转平移等一系列变换，变成以原点为中心的 AABB，所以该假定是有效的。设三角形的顶点为 $v_0, v_1, v_2$ ，box 的一半长宽高为 $h_x, h_y, h_z$ ，则这 13 个向量分别为 $e_0(1, 0, 0), e_1(0, 1, 0), e_2(0, 0, 1)$ ，三角形的法向量 $n$ （通过三角形两边向量叉乘得到），剩下九个向量分别为 $a_{ij} = e_i \times f_j , i,j \in \{0, 1, 2\}$ ，其中 $f$ 为三角形的边向量 $f_0 = v_1 - v_0, f_1 = v_2 - v_1, f_2 = v_0 - v_2$ ， $\times$ 代表向量叉乘。若直接这样一个个的计算投影是否相交，虽然能达到目的，但快速就无法体现了，所以作者根据向量计算方法和一些策略将其中一些需要计算投影的地方极大的简化了，所以加快的计算速度。具体简化过程为：

首先来看最后九个向量，$a_{00} = e_0 \times f_0 = (0, -f_{0z}, f_{0y})$ ，三角形三个顶点在在该向量上的投影分别为：
$p_0 = a_{00} \cdot v_0 = (0, -f_{0z}, f_{0y}) \cdot v_0 = v_{0z}v_{1y} - v_{0y}v_{1z}$
$p_1 = a_{00} \cdot v_1 = (0, -f_{0z}, f_{0y}) \cdot v_1 = v_{0z}v_{1y} - v_{0y}v_{1z} = p_0$
$p_2 = a_{00} v_2 = (0, -f_{0z}, f_{0y}) v_2 = (v_{1y} - v_{0y})v_{2z} - (v_{1z} - v_{0z})v_{2y} $
由于 $p_0 == p_1$，所以在求最大最小值时只需要做一次比较，接着求 box 在该向量上的投影，box 中心在原点，所以投影半径 $r$ 可以以一种简单的方式求出：
$r = h_x|a_{00x}| + h_y|a_{00y}| + h_z|a_{00z}| = h_y|a_{00y}| + h_z|a_{00z}|$
计算投影是否重合也很简单：
$if(min(p_0, p_2) > r \ || \ max(p_0, p_2) < -r) \quad return \ false$ 否则两者投影相交，继续计算其它向量。
三个轴向单位向量 e 中的投影是否重合就更好判断了，完全不需要计算投影，只需要计算三角形的最小 AABB，判断两个 AABB 是否相交即可（取两个 AABB 最小的顶点和最大的顶点，从三维上判断最小是否的大于最大的即可，若任意一个维度上最小的比最大的大，则两者不相交），
至于判断最后一个向量——三角形的法向量上的投影是否重合，相当于判断三角形所在平面是否与 box 相交。判断 box 与平面相交有一种简单快速的方式，即通过公式 $|d| <= a_1 |n \cdot A^1| + a_2|n \cdot A^2| + a_3 |n \cdot A^3|$ ，其中 $d$ 为 box 中心到平面的距离（中心点到平面上一点构成的向量与平面法向量做点积），$n$ 为平面法向量，$A^1$ 为 box 侧面法向量，对于 AABB 可为 $(1, 0, 0)$，$a_1$ 为 box 中心到侧面的距离，对于 AABB 可为 $h_x$，同理 $A^2$ 为 box 顶面法向量，对于 AABB 可为 $(0, 1, 0)$，$a_2$ 为 box 中心到顶面距离，对于 AABB 可为 $h_y$，$A^3$ 为 box 正面法向量，对于 AABB 可为 $(0, 0, 1)$，$a_3$ 为 box 中心到正面距离，对于 AABB 可为 $h_z$，即在 AABB 中，该公式可简化为 $|d| <= h_x|n_x| + h_y|n_y| + h_z|n_z|$ ，满足该公式，即可判定平面与 AABB 相交。

　　如此 13 个向量全部判断完毕，如全都相交，则可认定三角形与长方体相交，若其中一个不相交，则三角形与长方体不相交。三维的都能判断，二维的三角形与矩形相交判断就更简单了，分成两类法向量后，利用向量运算先简化运算量，再计算投影是否相交即可。

附录

　　还有一种根据距离判断两个 AABB 是否相交的办法，即先取两个 AABB 的中心 $(x_1, y_1, z_1)$ 和 $(x_2, y_2, z_2)$，然后计算两个中心点之间的三个维度的距离，将 x 维度的距离与两个AABB 的 $h_x$ 之和比较，若中心点 x 维度的距离较大，则不相交。即：$if (|x_1 - x_2| > h_{x1} + h_{x2}) \quad return \ false$ ，否则比较 y 维度， z 维度，若所有都小，则两 AABB 相交。这种方式是 Shaun 在一次面试中被问到没答出后在网上找到的答案，其实感觉和比较最小最大顶点也差不多，都是从不相交出发，因为直接判断相交基本不可能，而不相交很容易判断，把所有的不相交情况判断完，那就只剩相交了，可惜面试官只想要这种方案 ╮(╯▽╰)╭。

参考资料

[1] Code by Tomas Akenine-Möller

[2] Simple Intersection Tests For Games

2019-10-28

网页菜单纯 css 实现

Study

css

前言

　　最近搞了些前端的工作，本来做菜单栏的时候想直接用 bootstrap 的，但是感觉 bootstrap 太大了，而且依赖有点多，在 webpack 中也不是很好打包（虽然可以绕过去），所以就索性自己在网上找了一些实现方式，改改感觉也还可以。这次主要实现了两种菜单栏，具体如下。

前言

鼠标悬停下拉菜单

　　鼠标悬停下拉菜单应该是最常见的一种菜单栏了，当鼠标悬停在菜单栏上时，子菜单缓缓下拉，看起来就很舒服，用 flex 布局结合列表也很好实现（不用像以前那种 float 了，舒服）。具体实现方式如下：

<style>
    .flex-body {
        display: flex;
        flex-direction: column;
    }

    header {
        z-index: 1;
    }

    ul,
    ul li {
        list-style: none;
        margin: 0;
        padding: 0;
    }

    .menu {
        display: flex;
        justify-content: start;
    }

    ul li {
        width: 100px;
        height: 50px;
        line-height: 50px;
    }

    .menu li .submenu {
        /* display: none; */
        background-color: aqua;
    }

    .submenu li {
        height: 0;
        line-height: 0;
        opacity: 0;
        visibility: hidden;
    }

    .menu li:hover .submenu li {
        /* display: block; */
        height: 50px;
        line-height: 50px;
        opacity: 1;
        visibility: visible;
        transition: all 1s;
    }
</style>
<div class="flex-body">
    <header>
        <ul class="menu">
            <li>
                <a>menu1</a>
                <ul class="submenu">
                    <li><a>submenu1</a></li>
                    <li><a>submenu1</a></li>
                    <li><a>submenu1</a></li>
                </ul>
            </li>
            <li>
                <a>menu2</a>
                <ul class="submenu">
                    <li><a>submenu1</a></li>
                    <li><a>submenu1</a></li>
                    <li><a>submenu1</a></li>
                </ul>
            </li>
            <li>
                <a>menu3</a>
                <ul class="submenu">
                    <li><a>submenu1</a></li>
                    <li><a>submenu1</a></li>
                    <li><a>submenu1</a></li>
                </ul>
            </li>
        </ul>
    </header>
    <main>mainmainmainmainmainmainmainmainmainmain</main>
</div>

　　※注： 实现该菜单栏有两个需要注意的点：1、不能用 display: none 和 block 来使子菜单消失或出现，因为这样会造成缓缓下拉的动画失效，transition 并不支持 display，所以只能用 visibility 和 height 来共同实现，以达到下拉动画效果；2、因为使用了 flex 布局，所以 z-index 只对同级 flex-item 有效，所以为防止菜单栏下面的内容出现在子菜单之上，即将子菜单栏位于最上层，需要将整个页面的布局都设置为 flex，并使 header 的 z-index 最大，如此才能保证子菜单的菜单覆盖 main 中的内容，不然就会有重叠干扰现象。

鼠标点击手风琴菜单

　　手风琴特效也算是非常常见的了，一般的手风琴是鼠标悬停展开，这种比较好实现，难的是如何保持这种展开状态，focus 可以短暂保持展开状态，但是不能点击其他地方，局限性太大。所以需要引入其它的东西来记录这种展开状态，可以用 checkbox 或 radio 的 checked 来记录这种状态，从而只用 css 即可实现该菜单，具体实现如下：

<style>
    input[data-prop="menu-recorder"] {
        display: none;
    }

    .menu-title {
        display: block;
        width: 500px;
        height: 50px;
        line-height: 50px;
        border: 1px solid black;
    }

    .menu-content {
        width: 500px;
        max-height: 100px;
        overflow-y: auto;
    }

    .menu-content>li {
        height: 0;
        line-height: 20px;
        overflow: auto;
        opacity: 0;
        visibility: hidden;
        transition: all 1s;
    }

    input[data-prop="menu-recorder"]:checked+.menu-content>li {
        height: 20px;
        line-height: 20px;
        opacity: 1;
        visibility: visible;
        transition: all 1s;
    }
</style>
<div class="accordion-menu">
    <section class="menu-item">
        <label class="menu-title" for="menu1">menu1</label>
        <input id="menu1" type="checkbox" data-prop="menu-recorder">
        <div class="menu-content">
            <li>test<br></li>
            <li>test<br></li>
            <li>test<br></li>
            <li>test<br></li>
            <li>test<br></li>
            <li>test<br></li>
            <li>test<br></li>
        </div>
    </section>
    <section class="menu-item">
        <label class="menu-title" for="menu2">menu2</label>
        <input id="menu2" type="checkbox" data-prop="menu-recorder">
        <div class="menu-content">
            <li>test<br></li>
            <li>test<br></li>
            <li>test<br></li>
        </div>
    </section>
    <section class="menu-item">
        <label class="menu-title" for="menu3">menu3</label>
        <input id="menu3" type="checkbox" data-prop="menu-recorder">
        <div class="menu-content">
            <li>test<br></li>
            <li>test<br></li>
            <li>test<br></li>
            <li>test<br></li>
        </div>
    </section>
    <section class="menu-item">
        <label class="menu-title" for="menu4">menu4</label>
        <input id="menu4" type="checkbox" data-prop="menu-recorder">
        <div class="menu-content">
            <li>test<br></li>
            <li>test<br></li>
            <li>test<br></li>
            <li>test<br></li>
            <li>test<br></li>
        </div>
    </section>
</div>

　　这里需要注意一点的就是 height 从 0 到 100% 并不会触发 transition 渐变动画，而是需要确切的高度值变化才能触发，所以上文这里添加了个 <li> 标签，直接在该标签上添加动画，还有一种就是在 .menu-content 上设定确定的 max-height，也能触发动画，但是有个缺点就是前后 max-height 的差距太大时，动画效果就很不理想了，这时可能只能依靠 js 了。上文中 checkbox 也可用 radio 替换，效果略有差异，一个是能全部展开或收起，而另一个则是能且仅能展开一个。

Tab 标签页切换菜单

　　这个菜单和上面那个菜单的实现非常相似，先上代码：

<style>
    .tab-menu {
        display: flex;
        position: relative;
        width: 500px;
        height: 300px;
    }

    input[data-prop="menu-recorder"] {
        display: none;
    }

    .menu-title {
        display: block;
        width: 100px;
        line-height: 50px;
        text-align: center;
        border: 1px solid black;
        border-right: 0;
        box-sizing: border-box;
        transition: all 1s;
    }

    .tab-menu .menu-item:last-child .menu-title {
        border-right: 1px solid black;
    }

    .menu-content {
        position: absolute;
        left: 0;
        top: 51px;
        height: calc(100% - 50px);
        overflow-y: auto;
        width: 100%;
        border: 1px solid #000;
        box-sizing: border-box;
        font-size: 24px;
        text-align: center;
        opacity: 0;
        visibility: hidden;
        transition: all 1s;

    }

    input[data-prop="menu-recorder"]:checked+.menu-content {
        opacity: 1;
        visibility: visible;
        transition: all 1s;
    }
</style>
<div class="tab-menu">
    <section class="menu-item">
        <label class="menu-title" for="menu1">menu1</label>
        <input id="menu1" type="radio" name="tab-control" data-prop="menu-recorder">
        <div class="menu-content">
            <li>test<br></li>
            <li>test<br></li>
            <li>test<br></li>
            <li>test<br></li>
            <li>test<br></li>
            <li>test<br></li>
            <li>test<br></li>
        </div>
    </section>
    <section class="menu-item">
        <label class="menu-title" for="menu2">menu2</label>
        <input id="menu2" type="radio" name="tab-control" data-prop="menu-recorder">
        <div class="menu-content">
            <li>test<br></li>
            <li>test<br></li>
            <li>test<br></li>
        </div>
    </section>
    <section class="menu-item">
        <label class="menu-title" for="menu3">menu3</label>
        <input id="menu3" type="radio" name="tab-control" data-prop="menu-recorder">
        <div class="menu-content">
            <li>test<br></li>
            <li>test<br></li>
            <li>test<br></li>
            <li>test<br></li>
        </div>
    </section>
    <section class="menu-item">
        <label class="menu-title" for="menu4">menu4</label>
        <input id="menu4" type="radio" name="tab-control" data-prop="menu-recorder">
        <div class="menu-content">
            <li>test<br></li>
            <li>test<br></li>
            <li>test<br></li>
            <li>test<br></li>
            <li>test<br></li>
        </div>
    </section>
</div>

　　从代码上看关键点就是 .menu-content 的定位方式了，采用了绝对定位，并将整个菜单栏设置为相对定位，以保证所有 tab 标签页内容位置和大小保持一致。当然 tab 标签页肯定是唯一的，所以只能用 radio 记录显示标签页了。其中为了保证 .menu-title 和 .menu-content 的边框不重叠，所以在 .menu-title 中只设置 line-height，而 .menu-content 的 top 比其多一个像素。