数字图形生成与绘制技术解析

### 数字图形生成与绘制技术解析 #### 生成完整球面表面 在三维整数空间中生成完整的球面表面时，会涉及到球面缺失体的相关问题。首先明确一些定义，半径为 r 的完整（空心）球面可表示为 \(SZ(r) = SZ ∪(r) ∪ AZ3(r)\) ，其中 \(AZ3(r)\) 中的点数是 \(HZ ∪(r)\) 中缺失体数量的两倍。 在计算和修复旋转表面中的缺失体时，需要用到一些之前的研究成果： - **定理 1**：位于 \(DZ ∪(r)\) 中的圆盘缺失体总数为 \(|AZ2(r)| = 8 \sum_{k = 0}^{mr - 1} |AZ2_k(r)|\) ，其中 \(|AZ2_k(r)| = \lfloor(2k + 1)r - k(k + 1)\rfloor - \lfloor 2k + 1 + \frac{1}{2} \sqrt{(8k^2 + 4k + 1)}\rfloor\) ，且 \(mr = r - \lfloor r / \sqrt{2} \rfloor + 1\) 。 - **定理 2**：\(|AZ2(r)| = Θ(r^2)\) 。 数字旋转半球和数字旋转球面存在缺失体体素，这些缺失体体素可根据它们与 \(DZ ∪(r)\) 中缺失像素的唯一对应关系来表征。考虑对应于 \(HZ ∪(r)\) 的生成曲线 \(CZ_{1,2}(r)\) 的两个连续像素 \(p_i(x_i, y_i)\) 和 \(p_{i + 1}(x_{i + 1}, y_{i + 1})\) ，有以下三种可能情况： 1. \((x_{i + 1}, y_{i + 1}) = (x_i + 1, y_i)\) （第一卦限） 2. \((x_{i + 1}, y_{i + 1}) = (x_i + 1, y_i - 1)\) （第一卦限或第二卦限） 3. \((x_{i + 1}, y_{i + 1}) = (x_i, y_i - 1)\) （第二卦限） 对于情况 1，会得到两个半径相差 1 且位于同一平面的同心圆，对应 \(p_i\) 和 \(p_{i + 1}\) 的圆半径分别为 \(x_i\) 和 \(x_i + 1\) ，此时两个连续圆之间的缺失体体素与 \(CZ(o, x_i)\) 和 \(CZ(o, x_{i + 1})\) 之间的缺失像素相对应。对于情况 2，\(p_{i + 1}\) 生成的圆半径为 \(x_{i + 1} = x_i + 1\) ，其平面与 \(p_i\) 生成的圆平面相距一个体素。若将这两个圆投影到 zx 平面，投影圆之间的缺失像素与原始圆之间的缺失体体素相对应。对于情况 3，由于 \(p_i\) 和 \(p_{i + 1}\) 生成的圆半径相同（\(x_i = x_{i + 1}\) ），所以不存在缺失体。 由此可知，\(HZ ∪(r)\) 中缺失体体素的数量与 \(DZ ∪(r)\) 中缺失像素的数量相同。并且，\(HZ ∪(r)\) 中存在的体素数量会大于 \(DZ ∪(r)\) 中存在的像素数量，因为对于 \(DZ ∪(r)\) 中特定半径 \(s \in \{0, 1, 2, \ldots, r\}\) 的每个数字圆，在 \(HZ ∪(r)\) 中会有一个或多个半径为 \(s\) 的数字圆依次排列。 以下是相关的引理和定理： - **引理 1**：若 \(p(i, j, k)\) 是 \(HZ ∪(r)\) 中的缺失体体素，则将 \(p\) 投影到 xz 平面得到的像素 \((i, k)\) 是 \(DZ ∪(r)\) 中的缺失像素。 - **定理 3**：\(HZ ∪(r)\) 中缺失体体素的总数为 \(|AZ2(r)| = Θ(r^2)\) 。 - **定理 4**：位于 \(SZ(r)\) 上的缺失体体素总数为 \(|AZ3(r)| = 2|AZ2(r)| = 16 \sum_{k = 0}^{mr - 1} |AZ2_k(r)| = Θ(r^2)\) 。 判断一个给定体素是否为缺失体的必要和充分条件如下： - **引理 2**：\(CZ_1(r)\) 中纵坐标为 \(j\) 的像素的横坐标的平方位于区间 \(I(r)_{r - j} := [u(r)_{r - j}, v(r)_{r - j}]\) ，其中 \(u(r)_{r - j} = r^2 - j^2 - j\) ，\(v(r)_{r - j} = r^2 - j^2 + j\) 。 - **引理 3**：像素 \((i, j)\) 是缺失体当且仅当 \(i^2\) 位于整数区间 \(J(r)_{r - j} := [v(r)_{r - j}, u(r + 1)_{r + 1 - j}]\) 中，对于某些 \(r \in Z^+\) 。 - **定理 5**：体素 \(p(i, j, k)\) 是缺失体当且仅当对于某些 \(r' \in Z^+\) ，\(i^2 \in J(r')_{r' - k}\) 且 \(r'^2 \in I(r)_{r - j}\) 。 例如，在半径 \(r = 50\) 的旋转半球中，体素 \((2, 50, 4)\) 是缺失体，因为当 \(k = 4\) 时，\(r' = 4\) ，\(v(r')_{r' - k} = r'^2 - k^2 + k = 16 - 16 + 4 = 4\) ，\(u(r' + 1)_{r' + 1 - k} = (r' + 1)^2 - k^2 - k = 25 - 16 - 4 = 5\) ，所以 \(J(4)_0 = [4, 5) = [4, 4]\) ，其中包含 \(4 = i^2\) ；同时 \(u(r)_{r - j} = r^2 - j^2 - j = 50^2 - 50^2 - 50 = -50\) ，\(v(r)_{r - j} = r^2 - j^2 + j = 50^2 - 50^2 + 50 = 50\) ，所以 \(I(50)_0 = [-50, 50)\) ，包含 \(16 = r'^2\) 。而体素 \((3, 50, 4)\) 不是缺失体，因为当 \(k = 4\) 时，不存在这样的 \(r'\) 使得 \(J(r')_{r' - 4}\) 包含 \(3^2\) 。 修复缺失体体素的算法如下： ```plaintext Algorithm 1. (AVH) Fixing absentee voxels in the hemisphere Input: Generating circular arc, CZ_{1,2}(r) := {p1, p2, ... , pnr} Output: Absentee voxels in HZ ∪(r) 1 AZ3(r) ← ∅ 2 for t = 1, 2, ... , nr - 1 do 3 if it+1 > it then 4 AZ3(r) ← AZ3(r) ∪ ACC(CZ_{1,2}(r), t) 5 return AZ3(r) Procedure ACC(CZ_{1,2}(r), t) 1 A ← ∅, r ← it 2 int i ← 0, k ← r, s ← 0, w ← r - 1 3 int l ← 2w 4 while k ≥ i do 5 repeat 6 s ← s + 2i + 1 7 i ← i + 1 8 until s ≤ w 9 if i^2 ∈ J(r)_{r - k} and k ≥ i then 10 A ← A ∪ {(i', jt, k') : {|i'|} ∪ {|k'|} = {i, k}} 11 w ← w + l, l ← l - 2, k ← k - 1 12 return A ``` 该算法的输入是生成圆弧 \(CZ_{1,2}(r)\) ，它是一个有序的点序列 \(\{p_t(i_t, j_t, 0) \in Z^3 : t = 1, 2, \ldots, n_r\}\) ，第一个点是 \(p_1(0, r, 0)\) ，最后一个点是 \(p_{n_r}(r, 0, 0)\) 。点 \(p_{t + 1}\) 的 \(i_{t + 1}\) 可以与前一个点 \(p_t\) 的 \(i_t\) 相同，或者比 \(i_t\) 大 1 。对于前者情况，\(p_t\) 和 \(p_{t + 1}\) 生成的两个圆之间没有缺失体；对于后者情况，通过调用过程 \(ACC\) 计算缺失体。 过程 \(ACC\) 用于查找半径为 \(i\) 和 \(i + 1\)