三角形随机均匀点采样算法

引理及证明

定理1 对于在集合$S \subset \mathbb{R}^n$上具有概率密度函数$f$的$n$维连续随机变量$X$，若在集合$T \subset \mathbb{R}^m$上存在连续随机变量$Y$满足单调函数$Y=\phi (X)$，则其分布函数为$F_Y(y)=F_X(\phi^{-1}(y))$（单调递增）或$F_Y(y)=1-F_X(\phi^{-1}(y))$（单调递减），其分布密度函数为$f_y(y)=f\left( \phi^{-1}(y) \right)|{\frac{d}{dy}\phi^{-1}}(y)|$.

证明：

$$\begin{gather*} \begin{split} F_Y(y) &= P(Y \le y)\\ &= P(\phi(x) \in (-\inf,y])\\ &= P(X \in \phi^{-1}(-\inf,y]) \end{split} \end{gather*}$$

当$\phi(X)$单调递增时：

$$\begin{gather*} \begin{split} F_Y(y) &= P\left(X \in \phi^{-1}(-\inf,y]\right)\\ &= P\left(X \le \phi^{-1}(y)\right)\\ &= F_X\left(\phi^{-1}(y)\right) \end{split} \end{gather*}$$

当$\phi(X)$单调递减时：

$$\begin{gather*} \begin{split} F_Y(y) &= P\left(X \in \phi^{-1}(-\inf,y]\right)\\ &= P\left(X \ge \phi^{-1}(y)\right)\\ &= 1 - F_X\left( \phi^{-1}(y) \right) \end{split} \end{gather*}$$

当$\phi(X)$单调递增时，$\frac{\mathrm{d}}{\mathrm{d}y}\phi^{-1}(y) \ge 0$：

$$\begin{gather*} \begin{split} f_Y(y) &= \frac{\mathrm{d}}{\mathrm{d}y}F_Y(y)\\ &= \frac{\mathrm{d}\phi^{-1}(y)}{\mathrm{d}y}\left( \frac{\mathrm{d}}{\mathrm{d}\phi^{-1}(y)}F_X\left(\phi^{-1}(y)\right) \right)\\ &= f_X\left( \phi^{-1}(y) \right){\frac{\mathrm{d}}{\mathrm{d}y}\phi^{-1}}(y)\\ &= f_X\left( \phi^{-1}(y) \right)|\frac{\mathrm{d}}{\mathrm{d}y}\phi^{-1}(y)| \end{split} \end{gather*}$$

当$\phi(X)$单调递减时，$\frac{\mathrm{d}}{\mathrm{d}y}\phi^{-1}(y) \le 0$：

$$\begin{gather*} \begin{split} f_Y(y) &= \frac{\mathrm{d}}{\mathrm{d}y}F_Y(y)\\ &= \frac{\mathrm{d}\phi^{-1}(y)}{\mathrm{d}y}\left( \frac{\mathrm{d}}{\mathrm{d}\phi^{-1}(y)}\left( 1-F_X\left(\phi^{-1}(y)\right) \right) \right)\\ &= -f_X\left( \phi^{-1}(y) \right){\frac{\mathrm{d}}{\mathrm{d}y}\phi^{-1}}(y)\\ &= f_X\left( \phi^{-1}(y) \right)|\frac{\mathrm{d}}{\mathrm{d}y}\phi^{-1}(y)| \end{split} \end{gather*}$$

综上所述，当$\phi(X)$单调时，均有：

$$f_Y(y)=f_X\left( \phi^{-1}(y) \right)|\frac{\mathrm{d}}{\mathrm{d}y}\phi^{-1}(y)|$$

定理2 对于在集合$S \subset \mathbb{R}^n$上服从均匀分布的$n$维连续随机变量$X$，若在集合$T \subset \mathbb{R}^n$上存在连续随机变量$Y$与$X$满足线性变换$Y=AX + b$，矩阵$A$满秩，则$Y$也服从均匀分布。

证明：
显然线性变换$Y=AX + b$是单调且连续的，因此利用定理1，有

$$\begin{gather*} \begin{split} f_Y(y) &= f\left( \phi^{-1}(y) \right)|\frac{\mathrm{d}}{\mathrm{d}y}\phi^{-1}(y)|\\ &= f_X\left(A^{-1}(y-b)\right)|\frac{\mathrm{d}}{\mathrm{d}y}A^{-1}(y-b)|\\ &= f_X\left(A^{-1}(y-b)\right)\frac{1}{\left|\det(A)\right|} \end{split} \end{gather*}$$

由于$X$服从均匀分布，因此$f_X\left(A^{-1}(y-b)\right)$为常数$C$，故$f_Y(y)=\frac{C}{\left|\det(A)\right|}$也为常数，因而$Y$也服从均匀分布，证明完毕。

三角形重心坐标系（barycentric coordinate system）

三角形$ABC$内的点$P$可以使用重心坐标表示：

$$\begin{aligned} P=\lambda_1 A + \lambda_2 B + \lambda_3 C \nonumber\\ \left\{ \begin{aligned} \lambda_1 + \lambda_2 + \lambda_3 = 1 \nonumber\\ \lambda_1, \lambda_2, \lambda_3 > 0 \nonumber \end{aligned} \right. \end{aligned}$$

利用重心坐标系的三角形随机点采样

三角形重心坐标形式简单，但并不适合直接使用，我们可以将其写成向量形式：

$$\begin{gather*} \begin{split} P &= A + \overrightarrow{AP} \\ &=A+\overrightarrow{AC}+\overrightarrow{CP} \\ &=A+\overrightarrow{AC}+v\overrightarrow{CQ} \\ &=A+\overrightarrow{AC}+v(\overrightarrow{AQ}-\overrightarrow{AC}) \\ &=A+uv\overrightarrow{AB}+(1 - v)\overrightarrow{AC} \\ &=A+u(B - A)+v(1 - u)(C - A) \\ &=v(1-u)A+uvB+(1-v)C \end{split} \end{gather*}$$

式中，$u,v \in (0, 1)$，我们可以在区间$(0, 1)$上随机生成2个随机数得到$u, v$，带入公式即可得到一个三角形$ABC$内的采样点$P$，示意图如下：

模拟采样结果如下，可见，样本分布并不均匀，在$C$点附近采样点分布明显更加密集。

我们来简单证明一下这种方法得到的分布在$XY$空间中不是均匀分布：
首先由定理2，均匀分布的线性变换一定是均匀分布，那么只要我们证明在任意一个三角形上，这种采样方法得到的不是均匀分布，即可证明在所有三角形上，这种采样方法在$XY$空间中都不服从均匀分布，为了简化运算，我们分别给定三角形的三个点坐标为：$A(0, 0), B(1, 0), C(0, 1)$，在三角形中任取点$P$，点$P$坐标满足：

$$P=\left(\begin{array}{1}x \\y\end{array}\right) = \left(\begin{array}{1}uv \\1 - v\end{array}\right)$$

在$XY$空间中，分布函数为:

$$\begin{gather*} \begin{split} F(x, y) &= P(X \le x, Y \le y) \\ &= P(UV \le x, 1 - V \le y) \\ &= \int_0^1{P(uV \le x, 1 - V \le y)}f_U(u)\mathrm{d}u \\ &= \int_0^1{P(V \le \frac{x}{u}, V \ge 1 - y)}f_U(u)\mathrm{d}u \end{split} \end{gather*}$$

由于$U$服从在$(0, 1)$上服从均匀分布，因此$f_U(u) = 1$，当$x > 0,y > 0,x \le 1 - y$，即$(x, y)$在三角形$ABC$内时，有：

$$\begin{gather*} \begin{split} F(x, y) &= \int_0^1{P(V \le \frac{x}{u}, V \ge 1 - y)}\mathrm{d}u \\ &= \int_0^x{P(V \ge 1 - y)}\mathrm{d}u + \int_x^{\frac{x}{1-y}}P(1 - y \le V \le \frac{x}{u})\mathrm{d}u \\ &= -x\ln (1-y) \end{split} \end{gather*}$$

因此分布密度函数

$$\begin{gather*} \begin{split} f(x,y) &= \frac{\delta^2}{\delta x \delta y}F(x, y) \\ &= \frac{1}{1-y} \end{split} \end{gather*}$$

明显不是常数，概率密度随着$y$增大而变大，与采样模拟图密度分布结果相符，因此这个分布不是均匀分布，再利用定理2，可以推出——对于所有三角形，这种采样方法都不能在三角形内均匀采点。

利用重心坐标系的三角形随机均匀点采样

定理3 假设$u$和$v$为分别在$(0, 1)$区间上随机均匀生成的随机数，三角形$ABC$内的一个随机均匀采样点可以表示为

$$P=\sqrt{v}(1-u)A+u\sqrt{v}B+(1-\sqrt{v})C$$

证明：
和上文证明之前的采样方法不能得到均匀分布类似，我们只要证明当在特定三角形$A(0, 0), B(1, 0), C(0, 1)$上这种采样能得到均匀分布，那么利用定理2，我们就能证明对于所有三角形，这种采样方法得到的点都服从均匀分布。

$$\begin{gather*} \begin{split} F(x, y) &= P(X \le x, y \le y) \\ &= \int_0^1{P(u\sqrt{V} \le x, 1 - \sqrt{V} \le y)}f_U(u)\mathrm{d}u \\ &= \int_0^1{P(V \le \frac{x^2}{u^2}, V \ge (1 - y)^2)}f_U(u)\mathrm{d}u \\ &= \int_0^x{P(V \ge (1 - y)^2)}\mathrm{d}u + \int_x^{\frac{x}{1-y}}P((1 - y)^2 \le V \le \frac{x^2}{u^2})\mathrm{d}u \\ &= 2xy \end{split} \end{gather*}$$

因此分布密度函数

$$\begin{gather*} \begin{split} f(x,y) &= \frac{\delta^2}{\delta x \delta y}F(x, y) \\ &= 2 \end{split} \end{gather*}$$

显然是常数，符合均匀分布条件，证明完毕。
算法过程如下：

Algorithm samplePointInTriangle($x_a$, $y_a$, $x_b$, $y_b$, $x_c$, $y_c$):

  $u$ ← sample in uniform distribution $[0,1]$.

  $v$ ← sample in uniform distribution $[0,1]$.

  $x$ ← $\sqrt{v}(1-u)x_a+u\sqrt{v}x_b+(1-\sqrt{v})x_c$

  $y$ ← $\sqrt{v}(1-u)y_a+u\sqrt{v}y_b+(1-\sqrt{v})y_c$

  $P$ ← $(x, y)$

return $P$

拒绝采样法

在三角形的bbox上均匀采样，拒绝三角形外的点即可，算法：

Algorithm samplePointInTriangle($x_a$, $y_a$, $x_b$, $y_b$, $x_c$, $y_c$):

  $x_{min}$ ← $\min(x_a, x_b, x_c)$

  $x_{max}$ ← $\max(x_a, x_b, x_c)$

  $y_{min}$ ← $\min(y_a, y_b, y_c)$

  $y_{max}$ ← $\max(y_a, y_b, y_c)$

  do
    $u$ ← sample in uniform distribution $[0,1]$.

    $v$ ← sample in uniform distribution $[0,1]$.

    $P$ ← $(x_{min}+u(x_{max}-x_{min}),y_{min}+v(y_{max}-y_{min}))$

  until $P$ in triangle $ABC$

return $P$

示意图如下（只保留绿色区域的采样点）：

d