拙訳「A topological approach to voxelization」

[Laine 2013Laine, S. 2013. A topological approach to voxelization. Computer Graphics Forum 32, 4, 77–86. 10.1111/cgf.12153. https://research.nvidia.com/sites/default/files/pubs/2013-06_A-Topological-Approach/laine2013egsr_paper.pdf.]

doi url

1. まえがき（Introduction）#

1.1. 基本定義（Basic definitions）#

我々の表記法は主に Cohen-Or and Kaufman [1995Cohen-Or, D. and Kaufman, A. 1995. Fundamentals of surface voxelization. Graph. Models Image Process. 57, 6, 453–461. 10.1006/gmip.1995.1039. https://www.math.tau.ac.il/~dcor/articles/older/fundamentals.pdf.] に従う。整数の座標を持つ3次元の点の集合を $\mathbb{Z}^3$ する。我々は点 $p(x, y, z) \in \mathbb{R}^3$ の集合とボクセル $V = (x, y, z) \in \mathbb{Z}^3$ を関連付ける。ここで、 $V_x \le p_x \le V_x + 1$ であり、 $y$ と $z$ に対しても同様である。 $\mathbb{R}^3$ に組み込まれた連続で単純で閉じた2次元多様体の表面 $S$ を考えるとすると、 $\mathbb{R}^3 - S$ は｜過不足なく《exactly》2つの連結成分《connected components》 $I$ および $O$ を持つ。

$I$ と $O$ の全体に含まれるボクセルの空でない集合をそれぞれ $I^d$ と $O^d$ とする表面 $S$ のボクセル化とは $I^d$ や $O^d$ と共通の要素を持たないボクセルの離散集合 $S^d$ である。ボクセルの $k$ 連結経路《k-connected path》 $\Pi_k = (V_0, \dots, V_n)$ が存在しないならば、 $S^d$ は $k$ 分離《k-separating》であると言われる。ここで、 $V_{i + 1} \in N_k(V_i)$ 、すなわち、 $V_0 \in I^d$ であり、 $V_n \in O^d$ であり、 $\Pi_k \cap S^d \ne \emptyset$ である。別の言い方をすれば、 $I^d$ と $O^d$ の間のすべての $\Pi_k$ が $S^d$ にあるボクセルを含むならば、 $S^d$ は $S$ の $k$ 分離ボクセル化である。 $N_k(V)$ はボクセル $V$ の $k$ 近傍の集合であり、 $\mathbb{Z}^3$ において、我々にとって関心のある近傍集合は以下である。

N_6(x, y, z) = (x \pm 1, y, z) \cup (x, y \pm 1, z) \cup (x, y, z \pm 1)

N_{26}(x, y, z) = \{x - 1, x, x + 1\} \times \{y - 1, y, y + 1\} \times \{z - 1, z, z + 1\} - (x, y, z)

ここで、 $\times$ は｜デカルト積《cartesian product》を表す。ゆえに、任意の $V$ に対して、 $N_6(V)$ は6個の要素を持ち、 $N_{26}(V)$ は26個の要素を持つ。したがって、6連結経路 $\Pi_6$ はボクセルの面を通って隣接するボクセルを｜たどる《walk into》ことのみが可能であるものであり、26連結経路 $\Pi_{26}$ では｜それに加えて《as well》｜対角線上をたどること《diagonal walks》が可能である。｜紙面の都合により《due to space constraints》、本論では18分離および18連結のボクセル化および経路を｜考慮しない《we shall not consider》。

2Dボクセル化においても状況は変わらず、この場合において、我々はそれらに対応する意味で $S \subset \mathbb{R}^2$ 、 $S^d \subset \mathbb{Z}^2$ 、 $V$ 、 $I$ 、 $O$ 、 $\Pi_k$ を用いる。その次元は文脈により明らかとなるだろう。2Dにおける近傍関係《neighborship relations》は以下である。

\begin{align} N_4(x, y) &= (x \pm 1, y) \cup (x, y \pm 1) \\ N_8(x, y) &= \{x - 1, x, x + 1\} \times \{y - 1, y, y + 1\} - (x, y) \end{align}

ここで、 $N_4$ は3Dにおける $N_6$ と類似し、 $N_8$ は $N_{26}$ と類似している。近傍集合の図は、例えば、[Huang et al. 1998Huang, J., Yagel, R., Filippov, V. and Kurzion, Y. 1998. An accurate method for voxelizing polygon meshes. Proceedings of the 1998 IEEE symposium on volume visualization 119–126. 10.1145/288126.288181. https://web.eecs.utk.edu/~huangj/papers/polygon.pdf.]に見ることができる。

我々は、その表面が依然として $\mathbb{R}^3$ において対応するボリュームを2つの連結成分に分けるようなボクセル空間 $\mathbb{Z}^3$ の部分集合を考慮することによって、閉じていない表面に分離可能性《separability》の概念を拡張できる。これについては図1を参照のこと。閉じている表面と閉じていない表面のどちらでも、対応する $I^d$ および $O^d$ が空でない場合に制限していることに注意したい。そうでない場合、 $\mathbb{Z}^3$ で分離する手段が存在しないので、分離可能性を論じる意味がなくなってしまう。

（図1：閉じていない表面への $k$ 分離可能性の概念の拡張。（a） $S$ が依然として $\mathbb{R}^3$ における対応するボリュームを2つの連結成分 $I$ および $O$ に分離するような部分集合 $\boldsymbol{z} \subset \mathbb{Z}^3$ が存在する閉じていない表面 $S$ を考える。そして、対応する $I^d$ および $O^d$ は空ではない。（b） $\boldsymbol{z}$ におけるボクセルに制限される $I^d$ と $O^d$ の間のすべての $\Pi_k$ が $S^d$ におけるボクセルを含むならば、 $S^d$ は $S$ の $k$ 分離ボクセル化であると言える。そして、これは部分集合 $\boldsymbol{z}$ の任意の有効な選択に対して｜成り立つ《holds for》。この2Dの例では、 $S^d$ は8分離ではなく4分離である。）

2. 関連研究（Previous work）#

Kaufman and Shimony [1987Kaufman, A. and Shimony, E. 1987. 3D scan-conversion algorithms for voxel-based graphics. Proceedings of the 1986 workshop on interactive 3D graphics 45–75. 10.1145/319120.319126.] は線分や多角形、曲面を含む様々なタイプのプリミティブをボクセル化するためのアルゴリズムを提示する。彼らはいくつかの｜生来の忠実性《natural fidelity》と接続性の要件を明示的に列挙しており、我々もこの論文に従うものとする。特に、接続性はボクセル化された1D物体の忠実度に対する定義的要件《defining requirement》である一方、2D物体は分離可能性と密接に関わる”｜トンネルの欠如《lack of tunnels》”要件を満たさなければならない。 Cohen-Or and Kaufman [1997Cohen-Or, D. and Kaufman, A. 1997. 3D line voxelization and connectivity control. IEEE Computer Graphics and Applications 17, 6, 80–87. 10.1109/38.626973.] は3D直線のボクセル化に対する特定の接続性要件の｜満たし方《fullfilling》を更に詳しく述べる。

Cohen-Or and Kaufman [1995Cohen-Or, D. and Kaufman, A. 1995. Fundamentals of surface voxelization. Graph. Models Image Process. 57, 6, 453–461. 10.1006/gmip.1995.1039. https://www.math.tau.ac.il/~dcor/articles/older/fundamentals.pdf.] は3Dにおける表面のボクセル化の精緻な取り扱いに対しての基礎を築く。彼らは、 $S$ のいわゆるsupercoverが $S$ に接するすべてのボクセルから成り、任意の $k \in \{6,18,26\}$ に対して $k$ 分離である、ということを示す。その証明の性質はsupercover以外のボクセル化に対してこの論文で使われるものと似ている。彼らは $S$ がボクセルの境界面か辺、頂点のみと接する所の退化のケースの適切な扱い方も詳細に議論する。我々はこの論文にあるような退化に対するより単純でより一般的な解を提示する。

上記の論文はtunnel-freeボクセル化の概念を導入したりもする。これは、 $S^d$ の外側で $\mathbb{R}^3$ にある、ある種の接続されたパスが入力表面 $S$ と交差しないことを保証する幾何的特性である。2Dおよび3Dにおける我々の4分離および6分離ボクセル化はtunnel-freeである。そして、我々は主に分離可能性に焦点を当てるが、他のtunnel-freeボクセル化を容易に得られるだろう。これは節5.2.2で議論しようと思う。

Wang and Kaufman [1993Wang, S.W. and Kaufman, A.E. 1993. Volume sampled voxelization of geometric primitives. Proceedings visualization '93 78–84. 10.1109/VISUAL.1993.398854.] はボリュームサンプリングのボクセル化を検討する。これは、ボクセルの状態が入力プリミティブと重み付き球状ボリュームとの交差によって決定され、本質的には3Dにおける入力を事前にフィルタリングしている。これは、例えば、ボクセル化したデータにおける正確《precise》な表面位置の推定を難しくするエイリアシングアーティファクトを｜除こうとする《combat》ことで行われる。ボリュームサンプリングの結果はより忠実度の高い表面の再構築を可能にする距離フィールドとして解釈できる。ボリュームサンプリングは我々の交差対象と接点を持つが、我々の目標は入力を事前フィルタリングしないことである。

Huang et al. [1998Huang, J., Yagel, R., Filippov, V. and Kurzion, Y. 1998. An accurate method for voxelizing polygon meshes. Proceedings of the 1998 IEEE symposium on volume visualization 119–126. 10.1145/288126.288181. https://web.eecs.utk.edu/~huangj/papers/polygon.pdf.] は最小限の6分離および26分離ボクセル化を生成することを目標としたポリゴンメッシュのボクセル化の正確さを議論する。彼らは2D直線と3D平面に対する最小性《minimality》を証明し、それらの結果を三角形で構成される3Dメッシュに拡張する。しかしながら、三角形の辺と頂点は保守的な｜やり方《fashion》で扱われることで、その手法が入力メッシュのテッセレーションに影響されやすかったり、最小性が損なわれたりする。これは26分離のケースに関して Schwarz and Seidel [2010Schwarz, M. and Seidel, H.-P. 2010. Fast parallel surface and solid voxelization on GPUs. ACM Trans. Graph. 29, 6. 10.1145/1882261.1866201. https://michael-schwarz.com/research/publ/files/vox-siga10.pdf.] によって指摘された。そして、図2に示される通り、辺と頂点の特別な扱いもまた6分離のケースで最小性を破壊する。 Widjaya et al. [2003Widjaya, H., Moller, T. and Entezari, A. 2003. Voxelization in common sampling lattices. 11th pacific conference onComputer graphics and applications, 2003. Proceedings. 497–501. 10.1109/PCCGA.2003.1238302. https://eprints.cs.univie.ac.at/5027/1/2003_-_voxelization.pdf.] は無限の直線および平面に対する分離可能性と最小性の証明を伴う一般的な2Dおよび3D格子への拡張を提示する。

（図2：三角形メッシュ（ここに図示される通り、2Dにおけるポリラインに対応）のボクセル化に関する Huang et al. [1998Huang, J., Yagel, R., Filippov, V. and Kurzion, Y. 1998. An accurate method for voxelizing polygon meshes. Proceedings of the 1998 IEEE symposium on volume visualization 119–126. 10.1145/288126.288181. https://web.eecs.utk.edu/~huangj/papers/polygon.pdf.] の手法は最小ではなく、テッセレーションに影響されやすい。(a)[Schwarz and Seidel 2010Schwarz, M. and Seidel, H.-P. 2010. Fast parallel surface and solid voxelization on GPUs. ACM Trans. Graph. 29, 6. 10.1145/1882261.1866201. https://michael-schwarz.com/research/publ/files/vox-siga10.pdf.]で指摘される通り、26分離ボクセル化（2Dにおける8分離に対応）において、 $R_c = (\sqrt{3} / 2)$ を持つ｜辺を覆う円筒《edge sylinders》や｜頂点を覆う球《vertex spheres》を用いると、平坦な表面の辺や頂点の近くに余計《extraneous》なボクセルがタグ付けされてしまうかもしれない。(b)加えて、6分離ボクセル化（2Dにおける4分離を参照）において、 $R_c = L / 2$ は、左図（[Huang et al. 1998Huang, J., Yagel, R., Filippov, V. and Kurzion, Y. 1998. An accurate method for voxelizing polygon meshes. Proceedings of the 1998 IEEE symposium on volume visualization 119–126. 10.1145/288126.288181. https://web.eecs.utk.edu/~huangj/papers/polygon.pdf.]における図13より抜粋《adapted》）に示されるように、分離を保証する最小半径であるが、右図に示される通り、これもまた、平坦な表面上に余計なボクセルを生成するかもしれない。）

Schwarz and Seidel [2010Schwarz, M. and Seidel, H.-P. 2010. Fast parallel surface and solid voxelization on GPUs. ACM Trans. Graph. 29, 6. 10.1145/1882261.1866201. https://michael-schwarz.com/research/publ/files/vox-siga10.pdf.] は入力の三角形の軸平行な2D投影に基づく三角形メッシュの効率的なGPUボクセル化を検討する。彼らは6分離および26分離ボクセル化の両方を検討しており、その後者は入力表面のcover、すなわち、 $S$ におけるすべての点が $S^d$ におけるボクセルによってカバーされるようなボクセルの集合である。彼らの6分離ボクセル化は2Dテストに起因する非自明な幾何的等価性という点で興味深くあり、それは我々のボクセル化スキームを八面体の交差対象に適用する際の保守的な近似として見なすことができる。さらなる詳細は図3を参照のこと。我々は節5.2.2においてこの手法の分離可能性と非最小性を示す。 Pantaleoni [2011Pantaleoni, J. 2011. VoxelPipe: a programmable pipeline for 3D voxelization. Proceedings of the ACM SIGGRAPH symposium on high performance graphics 99–106. 10.1145/2018323.2018339. https://research.nvidia.com/sites/default/files/pubs/2011-08_VoxelPipe-A-Programmable/voxel-pipe.pdf.] は三角形メッシュの6分離および26分離ボクセル化の両方に対するとりわけ効率的な多段《multi-stage》GPUアルゴリズムを提示する。これもまた、後者のケースへの解としてcoverを生成する。 Varadhan et al. [2003Varadhan, G., Krishnan, S., Kim, Y. J., Diggavi, S. and Manocha, D. 2003. Efficient max-norm distance computation and reliable voxelization. Eurographics symposium on geometry processing. 10.2312/SGP/SGP03/116-126. https://gamma.cs.unc.edu/RECONS/maxnorm.pdf.] はボクセル中心と入力ジオメトリの間のmax-norm距離を計算することでcoverを生成するものであり、交差が発生するかどうかを特定するのにこれを用いる。

（図3： Schwarz and Seidel [2010Schwarz, M. and Seidel, H.-P. 2010. Fast parallel surface and solid voxelization on GPUs. ACM Trans. Graph. 29, 6. 10.1145/1882261.1866201. https://michael-schwarz.com/research/publ/files/vox-siga10.pdf.] の6分離表面ボクセル化手法は3Dにおける｜かなり独特な《rather peculiar》一連の幾何テストと等価である。(a)彼らはまず平面テストを行う。これは、三角形の平面とボクセルに包含される八面体との交差に対応する。ボクセルがこのテストに合格する場合、三角形の軸平行な2D投影それぞれがピクセル辺の中点間にまたがる2Dダイアモンドに対してテストされる。(b)3Dにおける｜押し出された《extruded》2Dダイアモンドの交差は平面テストで用いられる八面体を完全に取り囲む菱形十二面体《rhombic dodecahedron》である。図示されているのは、三角形の平面が八面体と交差するものの、その三角形が菱形十二面体のみと交差するように、これらの多面体《polyhedra》の間をメッシュが通過する場合である。それ故に、その最終結果は八面体との近似的な交差としてみなすことができる。）

3. 交差対象を伴うボクセル化（Voxelizing with intersection targets）#

我々の手法では、入力ジオメトリが $V$ の中に含まれる 交差対象《intersection target》 と交差するかどうかのテストによって、ボクセル $V$ がボクセル化 $S^d$ に含まれるかどうかを選択する。すべての場合において、 $S$ のsupercover[Cohen-Or and Kaufman 1995Cohen-Or, D. and Kaufman, A. 1995. Fundamentals of surface voxelization. Graph. Models Image Process. 57, 6, 453–461. 10.1006/gmip.1995.1039. https://www.math.tau.ac.il/~dcor/articles/older/fundamentals.pdf.]に属するボクセルを考えるには、それとは別のボクセルにおける交差対象が明らかに入力ジオメトリと交差できないので、これで十分である。

本節の後半において、我々は、入力の実効次元がボクセル化戦略に与えるであろう影響度と退化した交差を扱う一般的な方法を考察する。節4では、2Dにおける曲線に対する交差対象を導出し、節5では、3Dにおける曲面および表面のボクセル化を検討する。最後に、節6では、交差対象がボクセルごとに異なっても良い変種《variants》を｜調査する《examine》。

3.1. 入力の実効次元（Effective dimension of input）#

交差対象は様々な次元のプリミティブから構成しても良い。これらの例については図4を参照のこと。交差対象の次元の適切な選択はその入力の 実効次元《effective dimension》 に依存する。これは入力プリミティブの次元と異なっても良い。例えば、ソリッドな円柱としてジオメトリ的に表現される1本の細い｜髪の毛《strand of hair》を考えよう。その物体がボリューメトリックな立体であるとしても、例えば、｜ボリューム内に点があるかどうか《point-in-volume》の単純なテストを用いてボクセル化するという発想はおそらくうまくいかない。これは我々の用語法においてボクセルの中心にある0次元の点である交差対象と対応するだろう。入力が実質的に1次元であり、交差対象が0次元であるので、交差は髪の毛の太さに依存する任意に小さな確率でのみ発生する。これは結果としてその入力を代表しないボクセル化となり、例えば、その連結性《connectivity》を維持することができない。

（図4：色々な種類の入力に適する、様々な次元のプリミティブから構成される交差対象の例）

この例の状況において、例えば、 $S^d$ に対する6または26連結性を｜立証したい《want to establish》場合、入力と交差対象との交差が｜確率で決まらない《not rely on chance》ようにするため、我々は少なくとも2次元の交差対象を用いなければならない。一方で、3次元の交差対象（例えば、ボクセル全体）は｜不必要に鈍く《unnecessarily blunt》、結果として冗長なボクセルが $S^d$ に含まれてしまう可能性があるだろう。髪の毛が3Dの立体、2Dの表面、1Dのポリライン《polyline》または曲線のいずれかから構成されるかに関わらず同じ論拠《argument》が適用される。すなわち、実効次元は入力プリミティブの次元よりも｜関連性がある《relevant》。

2Dボクセル化において、2Dプリミティブの列が実質的に1次元である物体を形成するとき、似た状況が発生する。そのような例のひとつは、パスレンダリング《path rendering》で一般的な状況である、ゼロでない小さな太さを持つ線分から構成される曲線である。通常の0次元の交差対象（ピクセルの中心）によってパスをラスタライズすることはその結果の連結性を保証できないが、各ピクセル内に適切な1D交差対象を配置することによって、4または8連結性のいずれかを容易に保証することができる。また、完全な2D交差対象はこれらの目的に対して過剰であるだろう。

関連研究《previous literature》で示される手法は入力プリミティブの次元性《dimensionality》に対して厳密に特殊化されるため、実効次元より（不必要に）高いプリミティブの次元が発生する入力には適用できない。例えば、その入力が実質的に1次元であると分かったとしても、線のボクセル化アルゴリズムは2Dの表面から構成される細い髪の毛に対して使用できない。我々の交差対象手法はこの問題に悩まされず、同じ枠組みの中で任意の次元のプリミティブから構成される入力を扱うことができる。

3.2. 退化した交差（Degenerate intersections）#

入力プリミティブと交差対象の境界は、ボクセル化において｜本来不要な穴《spurious holes》を生成するのを避けたり、不必要な「厚い」結果を避けたりするため、正確に扱われなければならない。交差において境界（ボリュームの表面、三角形のような表面要素の辺、線の端点、または、曲線の線分）を常に含めることは穴を形成することを防ぐだろうが、入力が複数の交差対象の境界に触れるとき、対応するボクセルのすべてが $S^d$ に含まれる。 Cohen-Or and Kaufman [1995Cohen-Or, D. and Kaufman, A. 1995. Fundamentals of surface voxelization. Graph. Models Image Process. 57, 6, 453–461. 10.1006/gmip.1995.1039. https://www.math.tau.ac.il/~dcor/articles/older/fundamentals.pdf.] は｜詳細に《at length》これらの問題を考察し、2Dピクセルまたは3Dボクセルの境界の慎重に選択された部分を除外した交差対象を用いることを提案する。

このような手法はより複雑な交差対象に拡張することが難しく、それ故に、我々は退化した交差の問題に対するより汎用的でより単純な解法を提案する。我々はまず、任意のそのような退化がどちらかの入力ジオメトリを --- また｜同様に《equivalently》、交差対象を --- 適切な方向に若干摂動させることによって解決できることを｜述べる《observe》。これは結果として、交差していないか、入力と交差対象が適切に交差しているかのどちらかとなる。ここでは境界が含まれているかどうかは問題とならない。

入力プリミティブと交差対象の間の任意の退化を取り除く微小摂動ベクトルを ｜演繹的に《a priori》 選択できるということが判明している。この摂動を入力全体に --- また同様に、すべての交差対象に --- 適用することは、入力に対する微小の修正《modifications》が可能であると仮定すると正しくなるボクセル化を生成する。そのような摂動ベクトルの例は $(\epsilon, \epsilon^2, \epsilon^3)$ である。実践において、退化した交差は、退化していない結果が得られるまで、まずは $+x$ へ、そして $+y$ へ、などというように、微小に入力（または、交差対象）をずらすことで退化していない状態になるかどうかをテストすることによって解決される。

ボクセル対三角形やピクセル対辺のテストでは、このアプローチは Cohen-Or and Kaufman [1995Cohen-Or, D. and Kaufman, A. 1995. Fundamentals of surface voxelization. Graph. Models Image Process. 57, 6, 453–461. 10.1006/gmip.1995.1039. https://www.math.tau.ac.il/~dcor/articles/older/fundamentals.pdf.] の”reduced-voxels”と等価であるが、ボクセル境界の面、辺、頂点について、どれが含まれ、どれが含まれないかを個別に選択する必要がない。標準の2Dラスタライゼーションで用いられる点対三角形のテストでは、一般的なグラフィックスAPIで使われるラスタライゼーション規則と等価である。これは、一貫した｜面の向き《facing》を持つ三角形の扇が各ピクセル中心を、それが辺や頂点の上にあったとしても、｜たった一度《exactly once》だけ｜含める《cover》ことを保証する。実践において、我々は微小摂動ベクトルのアプローチが通常では交差計算中に行われる不等式テストの中へ注意深く配置された方程式に｜煮詰まる《boil down》ことを期待する。例えば、3Dでのポリゴン対ポリゴンのような、ある種のテストでは、その実装は自明ではないかもしれない。

ほとんどの場合、稀に退化した交差が発生する場合では結果のボクセル化に少量の余分なボクセルを含むことは壊滅的《disastrous》というほどではないことは注目されるべきである。入力プリミティブと交差対象が互いに触れているだけでも交差を報告する｜保守的な《conservative》交差はボクセル化に追加することだけが可能であり、それ故に、その連結性や分離可能性の特性を一切破壊しない。薄さが｜損なわれる《compromised》かもしれないが、これが関心事であるかどうかはアプリケーションに依存する。摂動手法の｜主な価値《principal value》は潜在的な退化を考える必要性を取り除くことによって我々の解析を単純化することである。

4. 2Dにおける交差対象（Intersection targets in 2D）#

まずは2Dにおけるボクセル化、すなわち、ラスタライゼーションを考えるとしよう。一般的な命名法《nomenclature》に従うため、我々はボクセルをピクセルと呼び、そして、入力ジオメトリはプリミティブ次元と実効次元の両方において0、1、2次元として良い。我々は入力の実効次元が適切なボクセル化戦略を選択するために既知であると仮定する。我々は単純閉曲線の内側から外側に｜横切る《cross》任意の連続的なパスがこの曲線と少なくとも1点で交差しなければならないというジョルダン《Jordan》曲線定理《curve theorem》に強く依存する。また、上記のような退化した場合を扱うために、パスが複数の曲線と交差または｜接する《meet》点を横切る場合を個別に考慮することは、そのような状況がいずれも横切るパスの微小摂動によって解決されるので、必要ないことに注意する。

4.1. 1次元の入力（One-dimensional input）#

実質的に1次元である入力は実際に1次元の線分か曲線、または、｜薄い《slim》2次元プリミティブのいずれかから成るだろう。ピクセルグリッドにボクセル化するとき、我々はその結果を4連結または8連結のいずれかとする必要があるだろう。これらはそれぞれ8分離可能性および4分離可能性と等価である[Cohen-Or and Kaufman 1995Cohen-Or, D. and Kaufman, A. 1995. Fundamentals of surface voxelization. Graph. Models Image Process. 57, 6, 453–461. 10.1006/gmip.1995.1039. https://www.math.tau.ac.il/~dcor/articles/older/fundamentals.pdf.]。それ故に、4分離可能性および8分離可能性を｜強制する《enforce》ための自明な方法は入力のcoverを生成することであるが、我々の入力は1次元であるので、我々は1次元の交差対象で足りること、および、より少ないボクセルを生成することを期待するべきである。

4.1.1. 4連結、8分離のボクセル化（4-connected, 8-separating voxelization）#

すべてのピクセルに配置された図5aに示される交差対象を考えるとする。この構造の重要な特徴は連続的な曲線がピクセルの隣接するカドのすべてのペアを接続することである。ピクセル内でその対象と交差する連続的な入力ジオメトリは、これらの一部が当該ピクセルの周りで単純閉曲線を形成するので、このピクセルの4近傍の交差対象を最初に通過することによってのみ他のピクセルへ拡張できる（図5b）。それ故に、結果としての連続的な入力パスのボクセル化は4連結、すなわち、8分離である。代わりとなる方法は節5.2.1で後に行われるように8分離可能性を直接証明することである。そこから4連結性が導かれる。

（図5：2Dにおける1次元の入力の4連結、8分離のボクセル化に対する交差対象。（a）隣接するピクセルのカドが連続的な曲線によって接続される一般的な形状。（b）中心のボクセルにおいてその対象と交差する入力ジオメトリはその境界曲線を通る以外で灰色で｜塗られた《shaded》領域を脱出することができない。これは中心ピクセルの4近傍の交差対象の一部を成す。（c）｜カドで接続する《corner-connecting》曲線を中心で接するように伸長することで、実践的な｜斜め十字《cross-diagonal》の交差対象を得る。（d）もうひとつの選択肢は曲線をピクセルの境界に押し出すことである。）

図6は図5cの斜め十字の対象を用いた1次元の入力の4連結ボクセル化の例を示す。ここでは、その結果に2次元の｜ピクセル全体《full-pixel》の対象が生成するであろうより少ないボクセルを含む。図5dの四角形の対象は、単一のピクセルの内側に全体が｜入り込む《fall in》任意の入力を含んだ、ゼロの実効次元を持つ点のような入力を無視する能力のためにのみ興味深い。そうでなければ、ピクセル全体の対象と同じ結果を生成する。

（図6：斜め十字の交差対象による1次元の入力のボクセル化の例。点は入力の曲線と交差対象との交差を示す。4連結性および8分離可能性はcoverの部分集合によって達成される。）

4.1.2. 8連結、4分離のボクセル化（8-connected, 4-separating voxelization）#

以前の交差対象を修正することによって、1次元の入力の8連結、4分離のボクセル化を容易に生成できる。図7aは隣接する辺の中間点が連続的な曲線によって接続される一般的な交差対象を図示する。図7bに示される通り、我々は再び、その交差対象と入力が交差するピクセルの周りに単純閉曲線を得る。この曲線はピクセルの8近傍の交差対象の一部から成り、それ故に、連続的な入力ジオメトリはこれらの内の少なくとも1つと交差することなしに脱出することができなくなる。再度、我々は節5.2.1における証明を用いて4分離可能性を直接示すことができるだろう。それから8連結性が導かれる。

（図7：2Dにおける1次元の入力の8連結、4分離のボクセル化に対する交差対象。（a）隣接する辺の中心が連続的な曲線によって接続される一般的な形状。（b）中心のボクセルにおいてその対象と交差する入力ジオメトリは、灰色の領域の境界曲線がこれらの交差対象から成るので、ピクセルの8近傍にのみ拡張できる。（c）中心で曲線を接続すると、実践的な十字線《crosshair》の交差対象を生み出す。（d）真っ直ぐな線分で隣接する辺の中心を接続すると、ラインレンダリングに対して一般的なグラフィックスAPIで使われるダイアモンドパターンを生み出す。）

実践的な交差対象はピクセルの辺の中間点《midpoints》をピクセル中心に接続することによって得られる（図7c）。これは｜湾曲した《curved》入力プリミティブに対してすらも交差する非常に単純な対象である。OpenGLやDirectXといったグラフィックスAPIはラインレンダリングに対して”diamond exit”ルールを採用する。これは一般形状の特殊な場合として得られる図7dにおける交差対象に対応する。ダイアモンド型の対象は十字線の対象よりその結果にピクセルを｜含みやすい《eager to include》。すなわち、入力が1つの象限《quadrant》に留まりつつも、カドからピクセルへ｜突き出ている《protruding》と考える。これは8連結性に対して不必要なピクセルを生成するコストでより｜審美的に満足する《aesthetically pleasing》結果を生み出すだろう。

薄さ（Thinness）。8連結ボクセル化において、我々は、表面または曲面の法線ベクトルの主軸方向に1ボクセル分だけの厚さのレイヤを生成するとして｜おおまかに《loosely》定義される、いわゆる結果の ｜薄さ《thinness》 について更に考慮する必要があるかもしれない。パラメータ化された連続的かつ微分可能な入力曲線 $c = (f_x(t), f_y(t)), t \in [0, 1]$ を考えるとする。ここで、すべての $t$ に対して $|d f_y / d f_x| \ge 1$ である。 $c$ は常に $x$ 軸ではなく $y$ 軸の方を向いているので、我々は $S^d$ におけるすべての水平なレイヤに対して多くとも1つのボクセルを生成したい。

図7cの十字線の対象がこの目標を｜満たす《fulfill》ことを確認することは容易である。点 $(x_0, y_0)$ でボクセル $V$ にある水平な線分と交差する $c$ を考える。ここで、 $y_0 = Y + \frac{1}{2}$ であり、 $Y \in \mathbb{Z}$ である。この水平なピクセルレイヤ内では、 $y \in [y_0 - \frac{1}{2}, y_0 + \frac{1}{2}]$ であり、絶対値の微分の比に関する制限のために境界 $x \in [x_0 - \frac{1}{2}, x_0 + \frac{1}{2}]$ を持つ。従って、 $c$ と潜在的に交差するかもしれない交差対象の垂直な線分は $c$ がその水平な線分と交差する同じ十字線の対象に属さなければならない。これは $x,y$ 境界がそのような他の線分を含まないためである。明らかに、そのレイヤにおける他の水平な線分はいずれとも交差する可能性が存在しない。すなわち、同じレイヤにおける他のボクセルは $S^d$ の中に存在しないだろう。似た推論を用いて、図7dのダイアモンド型の対象が薄いボクセル化を生成することを確認できる。

図8は図7cの十字線の対象を用いた1次元の入力の8連結ボクセル化の例を示す。節5.2.2で後に示される通り、そのボクセル化は4-tunnel-free[Cohen-Or and Kaufman 1995Cohen-Or, D. and Kaufman, A. 1995. Fundamentals of surface voxelization. Graph. Models Image Process. 57, 6, 453–461. 10.1006/gmip.1995.1039. https://www.math.tau.ac.il/~dcor/articles/older/fundamentals.pdf.]である。

（図8：十字線の交差対象を持つ1次元の入力の8連結および4分離ボクセル化の例。）

5. 3Dにおける交差対象（Intersection targets in 3D）#

3Dでは、連結性と分離可能性の関係は2Dの場合よりも明瞭ではない。更に、1次元の入力を用いると、分離可能性の道理にかなう概念を与えることは一切できないが、それでも我々は結果のボクセル化に対する様々な連結性の特性を立証することに関心があるだろう。

節4において用いられる種類の推論は依然として1次元の入力に対する連結性の特性を立証するために適用するが、2次元の入力に対する分離可能性は異なる戦略を用いて示される必要がある。我々は再びジョルダン曲線定理 --- または、より適切に言うならば、3Dの類似品である｜ジョルダン・ブラウワー《Jordan-Brouwer》の分離定理《separation theorem》を採用する。このとき、単純閉領域は2次元の入力ジオメトリによって形成され、内側領域と外側領域の間のパスは交差対象の部分を共に｜区分化《piecing》することによって形成される。

5.1. 1次元の入力（One-dimensional input）#

3Dにおいて実質的に1次元の入力は1、2、または、3次元のプリミティブから成るだろう。そのような入力が3D空間において分離を生成できないにもかかわらず、例えば、｜流体シミュレーション《flow simulation》やボクセル化された曲面の内部での塗りつぶしを可能にしたり、可視化されたボクセル化の｜見た目《appearance》が｜欠けていない《is not missing pieces》ことを保証したりするために、入力のボクセル化が6連結または26連結である必要があるだろう。我々は以降で両方の連結性に対する交差対象を導出するだろう。

5.1.1. 6連結ボクセル化（6-connected voxelization）#

節4.1.1からの2Dの類似品に従って、図9aに図示される3D交差対象を考えるとする。ボクセルの面ごとに、曲線がボクセルの外側からボクセルに侵入し、この表面と交差せずに他のある面を通って脱出するのを防ぐ連続的な表面を構築する。2Dの場合とまったく同じ推論に従って、連続的な1次元の入力オブジェクトが間にボクセルの6連結パスを形成することなしに2つのボクセル間を拡張できないことを確認できる。

（図9：3Dにおける1次元の入力の6連結ボクセル化に対する交差対象。（a）一般形状において、各面はボクセル内の表面によって閉じている。明確にするためにここでは下の面に対する部分《piece》のみが示される。（b）取り得る実現方法《realization》のひとつは中心で接する角錐《pyramids》で各面を閉じることである。これは空間の八面体テッセレーションに対応する。ここでは、八面体の中心がボクセル面の中心に位置する。（c）もうひとつの選択肢はボクセルの境界に表面を押し出すことである。交差対象は依然として2次元であり、立方体の表面のみから成る。明らかに、これは空間の立方体テッセレーションに対応する。）

この一般形状の2つの実践的な実現方法は図9bおよびcに図示され、それぞれ空間の八面体および立方体テッセレーションに対応する。ボクセル化が3Dボクセル全体に対して入力を交差させることで生成されるcoverとほぼ同じだけのボクセルを含むので、｜これらの実用上の妥当性は疑わしい《the practical relevance of these is dubious》。いくつかの状況では、3Dボクセルより2Dシートから構成される交差対象に対して入力を交差させる方が容易であるかもしれないが、一般には、これらの交差対象は結果のボクセル数をできるだけ少なくしておく必要があるときにのみおそらく有用である。

5.1.2. 26連結ボクセル化（26-connected voxelization）#

実質的に1次元の入力の26連結ボクセル化のケースはさらに興味深い。このはるかに緩和された連結性の要件に対してcoverを生成することは、多くの不必要なボクセルを含むので、あきらかに｜やり過ぎ《overkill》であろう。既存のアルゴリズムは、例えば、線分やパラメータ化された曲線のような、1次元のプリミティブから形成される入力に制限される。対して、我々の手法は実質的に1次元だが2または3次元のプリミティブのみで構成される入力から26連結ボクセル化を構築することができる。

図10aはこの目的に対して適切な交差対象を示す。連結性は2Dにおける8連結ボクセル化に対して節4.1.2で用いられたものと似た論拠｜から得られる《follow from》。入力がボクセル $V$ 内で対象と交差すると仮定しよう。 $V$ の26近傍の交差対象の部分は単一のボクセルの倍の長さの辺《side》を持つボックスを形成する（図10b）。これは単純で閉じた表面であり、入力ジオメトリが $V$ から｜目の前の近傍《immediate neighbors》の外側のボクセルへの連続的なパスを含むならば、この｜取り囲む《enclosing》ボックスと交差しなければならず、それ故に、 $N_{26}(V)$ における対象と交差する。

（図10：3Dにおける1次元の入力の26連結ボクセル化に対する交差対象。（a）その対象は3つのすべての軸に沿ってボクセルを｜二分する《bisect》3つの四角形《quadrilaterals》から成る。これはボクセルのカドを中心とする立方体に空間を分割する。（b）中心のボクセル内で対象と交差する入力ジオメトリは26近傍の対象と交差することなしに脱出できない。これは、これらの部分が倍の長さの辺を持つボクセルの周りに閉じた立方体を形成するためである。）

その結果が十字線の対象による2Dの場合と同じ意味での薄い状態とならないことは注目されるべきである。従って、支配的な方向に曲線に沿って｜歩を進め《steps》、レイヤあたり厳密に1つのボクセルを出力するアルゴリズムはより少ないボクセルを伴う26連結ボクセル化を生成するだろう。我々の手法の主な利点《benfit》は1次元プリミティブ以外の入力に対して機能することである。

5.2. 2次元の入力（Two-dimensional input）#

｜ほぼ間違いなく《arguably》3Dボクセル化の最も｜適した《relevant》使い方は2次元の入力の離散化である。この場合、結果のボクセル化の分離可能性は主な関心事である。例えば、ボクセル化した表面に対してレイをキャストすることを考えると、我々はできるだけ少ないボクセルをテストするためにレイから26連結パスを形成することを選択するだろう。この場合、表面のボクセル化は離散化したレイが元々分離している表面を｜貫通しない《not penetrate》ことを保証するために26分離である必要がある。あるいは、レイマーチがボクセルの6連結パスをテストするならば、より疎な入力の6分離ボクセル化で十分である。 Cohen-Or and Kaufman [1997Cohen-Or, D. and Kaufman, A. 1997. 3D line voxelization and connectivity control. IEEE Computer Graphics and Applications 17, 6, 80–87. 10.1109/38.626973.] は詳細な解析を提供する。

5.2.1. 26分離ボクセル化（26-separating voxelization）#

cover、すなわち、交差対象として3Dボクセル全体を用いることは、 Cohen-Or and Kaufman [1995Cohen-Or, D. and Kaufman, A. 1995. Fundamentals of surface voxelization. Graph. Models Image Process. 57, 6, 453–461. 10.1006/gmip.1995.1039. https://www.math.tau.ac.il/~dcor/articles/older/fundamentals.pdf.] によって示される通り、26分離である。しかし、我々の入力は実質的に2次元であるので、1次元の区分から構成される交差対象は関連するボクセルを求めることを保証するのに足るはずである。

図11aにおける交差対象を考えるとしよう。我々は、26分離を保証するために必要な特性とは交差対象がボクセルのカドを互いに接続することのみである、と主張する。これは｜ひと目では分からない《not trivial to see》ので、ジョルダン曲線定理を用いて背理法《indirect proof》を定式化しようと思う。退化が節3.2における微小摂動の手法によって扱われるという点に留意することが重要であり、それ故に、表面が、例えば、ボクセルのカドを斜めに通過するような場合について心配する必要はない。別の言い方をすれば、摂動は、この場合でも、交差対象と表面の交差がボクセルの1つの内側で発生し、カドと辺と面では一切発生しないことを保証する。入力が3次元のボリューメトリックなプリミティブから構成されるが、依然として実質的に2次元の表面を形成するならば（例えば、ゼロでない厚さを持つ球殻《spherical shell》）、このボリューム内に含まれる適切な表面を｜考慮するだろう《shall consider》。

（図11：3Dにおける2次元の入力の26分離ボクセル化に対する交差対象。（a）最も一般的な場合では、交差対象が｜何らかの方法で《in one way or another》ボクセルのすべてのカドを互いに接続するだけで十分である。ここではボクセル内の共通の1点と接続しているが、これは必須ではない。（b）実践では、空間の対角線上の真っ直ぐな線分は単純で対称的な対象を生成する。（c）いくつかの状況では、個々の線分対表面の交差テストが近傍のボクセル間で共有され得るので、ボクセルの辺に沿ってカドを接続する対象を用いる方が便利であるかもしれない。）

仮定を｜示し直す《restating》ため、 $\mathbb{R}^3$ に組み込まれ、空でない2つの集合 $I$ および $O$ に分割するような、単純で閉じた2次元の入力の表面 $S$ があるとしよう。 $S^d$ が上記の一般的な交差対象を用いて生成される $S$ のボクセル化であり、加えて、それぞれ3Dボリューム全体が $I$ および $O$ に属するボクセルから成る空でない集合 $I^d$ および $O^d$ が存在すると仮定する。

$S^d$ が26分離であることを示すため、 $V_{i+1} \in N_{26}(V_i)$ 、 $V_0 \in I^d$ 、 $V_n \in O^d$ 、かつ、 $Pi \cap S^d = \emptyset$ であるパス $\Pi = (V_0, \dots, V_n)$ が存在しないことを示さなければならない。ジョルダン曲線定理に従い、 $I$ の点と $O$ の点の間のすべての連続的なパスは $S$ と交差しなければならない。連続的なパスが $\Pi$ におけるボクセル内に｜完全に《entirely》含まれるならば、交差はボクセルのひとつ $V_i$ の中で発生する。故に、これはそのような連続的なパスを構築するのに十分であり、 $V_i$ が $S^d$ に含まれなければならないことを示す。

そのような連続的なパス $C(\Pi)$ を構築するため、各 $V_i$ における交差対象の部分《pieces》を接続する。交差対象はすべてのボクセルのカドを接続するので、交差対象に沿って $N_{26}$ のいずれかへ移動可能となるため、実際に、 $\Pi$ に存在するボクセル内に位置するよう $C(\Pi)$ を｜含める《contain》ことができる。 $V_0 \in I^d$ であり、それ故に、 $V_0$ 内の任意の点が $I$ の中にあることから、我々は $V_0$ の交差対象における任意の点から $C(\Pi)$ を開始する。同様に、 $V_n$ にある $C(\Pi)$ の終点《endpoint》は自明なこととして $O$ の中にある。

$C(\Pi)$ は $I$ の点と $O$ の点の間の単純閉曲線であるので、ある点 $p \in \mathbb{R}^3$ で $S$ と交差しなければならない。 $C(\Pi)$ が $\Pi$ におけるボクセルに対応するボリューム内に完全に含まれるので、交差点 $p$ は $\Pi$ の一部であるこれらのボクセルの1つ $V_i$ にもなければならない。 $p$ が表面 $S$ と $V_i$ の交差対象の両方の上にあるので、これは我々の $\Pi$ の定義と｜矛盾する《contradict》。従って、 $V_i \in S^d$ であり、上で定義されるような26連結パス $\Pi$ は存在できず、 $S^d$ が26分離であることを暗に示す。

上記の推論は26連結の $\Pi$ におけるボクセルによってカバーされるボリューム内に含まれる連続的なパス $C(\Pi)$ を構築することを可能にする任意の交差対象に対して成り立つ。これは実践的な交差対象の定式化に多くの柔軟性を与える。図11bとcは2つの選択肢を示すが、特に対称性を気にしないならば、他の多くの選択肢が存在する。

5.2.2. 6分離ボクセル化（6-separating voxelization）#

6分離ボクセル化は26分離より少ないボクセルを持つかもしれず、故に、26分離可能性が必要ないアプリケーションでは一般に好まれる。図12aに図示される交差対象は互いにボクセル面の中心と接続し、6分離ボクセル化を生成することを確認できる。その論拠は、｜仮定の分離可能性に違反している《hypothetical separability-violating》ボクセルのパス $\Pi$ が6連結であることを除いて、以前の場合と厳密に同じである。それ故に、6近傍の意味での近傍ボクセルの間を、すなわち、面を通って移動できる限り長く、連続的な $C(\Pi)$ を形成することができる。これは、提案される交差対象で明らかに可能である。一般的な形状の最も実践的で対称的な実現方法はおそらく図12bの十字線の対象である。

（図12：3Dにおける2次元入力の6分離ボクセル化に対する交差対象。(a)一般的な交差対象は面の中心を互いに接続する。(b)まっすぐな線分は特に単純な十字線の形状を生み出す。(c)ダイヤモンドルールの3D一般化（例えば、[Schwarz and Seidel 2010Schwarz, M. and Seidel, H.-P. 2010. Fast parallel surface and solid voxelization on GPUs. ACM Trans. Graph. 29, 6. 10.1145/1882261.1866201. https://michael-schwarz.com/research/publ/files/vox-siga10.pdf.]）は、十字線の対象のスーパーセットに対応するので、6分離の結果を生成する。）

2Dで用いられるダイアモンドルールのいずれかの理に適う3D拡張が十字線の対象を包含するために6分離ボクセル化を生み出すということは即座に導かれる。例えば、 Schwarz and Seidel [2010Schwarz, M. and Seidel, H.-P. 2010. Fast parallel surface and solid voxelization on GPUs. ACM Trans. Graph. 29, 6. 10.1145/1882261.1866201. https://michael-schwarz.com/research/publ/files/vox-siga10.pdf.] の手法は入力の三角形がボクセルの面の中心の間に｜かかる《spanned》八面体と交差する任意のボクセルを常に含み（図12c）、それ故に、6分離である。しかし、不必要に大きな対象を用いることは6分離に対して必要のないボクセルを含み、彼らの手法を最小限にできないことを示す。

単純な解析は Forest et al. [2009Forest, V., Barthe, L. and Paulin, M. 2009. Real-Time Hierarchical Binary-Scene Voxelization. Journal of Graphics, GPU, and Game Tools 14, 3, 21–34. 10.1080/2151237X.2009.10129283. https://www.irit.fr/recherches/VORTEX/publications/rendu-geometrie/JGT2009_Forest_et_al.pdf.] や Crassin et al. [2011Crassin, C., Neyret, F., Sainz, M., Green, S. and Eisemann, E. 2011. Interactive indirect illumination using voxel-based cone tracing: an insight. ACM SIGGRAPH 2011 talks. 10.1145/2037826.2037853. https://research.nvidia.com/sites/default/files/publications/GIVoxels-pg2011-authors.pdf.] によって用いられるGPUベースのボクセル化手法が6分離であることも明らかにする。これらは入力に関して3パスを行い、各パスでは3つの軸並行な投影に沿ってプリミティブをラスタライズする。結果のピクセルごとに、プリミティブの深度がその中心で計算され、その中心が奥行きで最も近いボクセルが $S^d$ に含まれる。これが図12bの十字線の交差対象を用いることと等価であることを理解するのは容易である。ここでは、各ラスタライゼーションパスが投影軸の方を向いている十字線の線分と入力を交差させることに対応する。拡張よって、このラスタライゼーションベースの手法は湾曲したプリミティブに対してさえ6分離の結果を生成するだろうが、一方で、必要になるのは深度の点の計算だけである。この特性は上記のものを用いた技術なしに｜確認する《ascertain》ことが極めて困難であるかもしれないだろう。

薄さ（Thinness）。十字線の交差対象によって生成されるボクセル化は以下の意味において薄くもある。曲がっている可能性があり、連続的で、あらゆるところで微分可能な表面プリミティブを考える。ここでは、すべての点で、法線ベクトルの $z$ 成分は最も大きい絶対値を持つ。薄さのために、我々は1つより多いボクセルがボクセルの $z$ 方向《-oriented》の各列において生成されないことを必要とする。その表面が点 $(x_0, y_0, z_0)$ のボクセル $V$ の $z$ 方向の十字線の線分と交差するとしよう。ここで、 $x_0 = X + \frac{1}{2}$ 、 $y_0 = Y + \frac{1}{2}$ 、 $X, Y \in \mathbb{Z}$ である。この（ $z$ 方向の）ボクセルの列では、 $x \in [x_0 - \frac{1}{2}, x_0 + \frac{1}{2}]$ であり、 $y$ に対しても同様である。 $y = y_0$ の $xz$ 平面で表面をスライスすることを考える。すべての点で $z$ に向かって傾いている法線ベクトルにより、我々は $|dz / dx| \le 1$ を得る。それ故に、 $z$ もまた $y = y_0$ を維持するときにこの $x$ の範囲において境界 $z \in [z_0 - \frac{1}{2}, z_0 + \frac{1}{2}]$ を持ち、従って、表面はこの列の中の $V$ 以外のボクセルにおける $x$ 方向の十字線の線分に到達できない。 $y$ を向いた十字線の線分に対しても同様のことが成り立つ。一般に表面 $z$ はその列におけるもうひとつのボクセルの中間に達するだろうが、これは十字線の線分がある $xz$ および $yz$ 平面では起こり得ないことに注意する。その表面は明らかに同じ列における他のいずれかの $z$ 方向の十字線の線分と交差できない。それ故に、 $V$ を除いたこの列の他のボクセルは結果に含めることができない。これにより薄さが導かれる。

単一の2D投影を伴うボクセル化（Voxelization with a single 2D projection）。興味深い推論《corollary》が薄さの特性と十字線の対象を用いる3軸ラスタライゼーションの等価性[Forest et al. 2009Forest, V., Barthe, L. and Paulin, M. 2009. Real-Time Hierarchical Binary-Scene Voxelization. Journal of Graphics, GPU, and Game Tools 14, 3, 21–34. 10.1080/2151237X.2009.10129283. https://www.irit.fr/recherches/VORTEX/publications/rendu-geometrie/JGT2009_Forest_et_al.pdf.; Crassin et al. 2011Crassin, C., Neyret, F., Sainz, M., Green, S. and Eisemann, E. 2011. Interactive indirect illumination using voxel-based cone tracing: an insight. ACM SIGGRAPH 2011 talks. 10.1145/2037826.2037853. https://research.nvidia.com/sites/default/files/publications/GIVoxels-pg2011-authors.pdf.]から導かれる。平面の三角形がその幾何的な法線ベクトルの支配的な方向に沿って投影されるとき、投影された三角形の中にその中心があるすべてのピクセルは対応するボクセル列におけるユニークなボクセルを生成する。十字線の対象を伴うボクセル化は薄いので、他の投影方向はこれらの列において｜それ以上の《any more》ボクセルを生成しない。従って、そのようなすべてのピクセルに対して、支配的な軸に沿った投影を考えるだけで十分であり、更に考慮する必要があるのは辺のみである。これは以下のアルゴリズムを提案する。

法線の支配的な軸に沿って2Dに投影される三角形をラスタライズする。投影された三角形がピクセルの中心を含むピクセルに対して、以前の手法にあるように[Forest et al. 2009Forest, V., Barthe, L. and Paulin, M. 2009. Real-Time Hierarchical Binary-Scene Voxelization. Journal of Graphics, GPU, and Game Tools 14, 3, 21–34. 10.1080/2151237X.2009.10129283. https://www.irit.fr/recherches/VORTEX/publications/rendu-geometrie/JGT2009_Forest_et_al.pdf.; Crassin et al. 2011Crassin, C., Neyret, F., Sainz, M., Green, S. and Eisemann, E. 2011. Interactive indirect illumination using voxel-based cone tracing: an insight. ACM SIGGRAPH 2011 talks. 10.1145/2037826.2037853. https://research.nvidia.com/sites/default/files/publications/GIVoxels-pg2011-authors.pdf.]、中心の深度がピクセル中心で計算される三角形の深度に最も近いボクセルを出力する。三角形の辺を含むが、その三角形が中心と｜重なっていない《not overlap》ピクセルに対して、ピクセルを二分する水平な線上の三角形の範囲《extents》を求め、これらを水平なピクセルの範囲《extents》にクランプし、こらら2つの点で三角形の深度を計算する。その値がボクセルの中心の深度の｜別々の側《different sides》にあるならば、対応するボクセルを出力する。そうでなければ、垂直方向に対してテストを繰り返す。最初のテスト（三角形対ピクセル中心）は投影軸に平行な十字線の線分に対して三角形を交差させることに対応し、後者のテストは投影軸に垂直な2つの十字線の線分に対して三角形をテストすることに対応する。こうして、6分離ボクセル化はたった1つの2D投影に基づいて生成できる。

Tunnel-freeness。 Cohen-Or and Kaufman [1995Cohen-Or, D. and Kaufman, A. 1995. Fundamentals of surface voxelization. Graph. Models Image Process. 57, 6, 453–461. 10.1006/gmip.1995.1039. https://www.math.tau.ac.il/~dcor/articles/older/fundamentals.pdf.] の定義に従うと、6-tunnel-freeボクセル化は $S^d$ の外側の2つの6近傍ボクセルの中心を接続する任意の線分が $S$ と交差しないようなものである。図12bにおける十字線の対象を用いることがこの要件を満たすことは、 $S$ と交差するそのような任意の線分が $S^d$ における近傍のボクセルの少なくとも１つで生成するだろうことから、容易に確認できる。図7cにおける十字線の対象を用いた2Dボクセル化でも同じことが成り立つ。ピクセル中心をそのカドや辺の中間点と接続する交差対象を用いることによって2Dでの8-tunnel-freeボクセル化を、ボクセル中心を面の中心や辺の中間点と接続する対象を用いて3Dでの18-tunnel-freeボクセル化を、ボクセル中心が面の中心や辺の中間点やカドと接続される対象を用いて26-tunnel-freeボクセル化を同様に得ることができるだろう。

6. 拡張（Extensions）#

これまでに我々は交差対象がすべてのピクセルまたはボクセルで同一となる状況のみを検討してきた。これは、我々の接続性や分離可能性の議論のいずれもこの性質に直接依存するものではないため、必須ではない。

提案されるいずれの交差対象も様々な方法で変更できるが、一方で、我々は、最も操作《manipilate》しやすいという理由から、2Dにおける1次元入力に対する4分離の十字線の対象（図7c）と3Dにおける2次元入力に対する6分離の十字線の対象（図12b）のみを考慮するだろう。

図13aは前述の交差対象の変種とその結果のボクセル化を図示しており、この変種において、その接続はピクセル辺上のランダムな点とピクセル内のランダムな点の間に作られる。この”泡《foam》”はボクセル化の接続性と分離可能性を保持するが、はるかに規則的でない構造をしている。これにより、例えば結果のボクセル化のスペクトル的性質が、もしそれが特定のアプリケーションにとって重要《interest》であるならば、改善されるかもしれない。

（図13：2Dにおける1次元入力に対する十字線の対象への修正。(a)ピクセル内やピクセル辺上にある接続点を無作為化すると、依然として4分離であり、すなわち、8接続である不規則なパターンを生成する。(b)辺の接続点をピクセルのカドへ完全に押しやると、各ピクセルにおける交差対象が単一の対角線分から成る所のパターンを生み出す。）

交差対象への更に極端な修正は、図13bに示される通り、ピクセルのカドで接するように接続する線分を押し出すことである。4分離性が節5.2.1にある分離可能性の証明の2D類推《analog》を用いて示されるときに成り立つことは容易に確認できる。単純な十字線の対象から相当《considerably》逸脱しているものの、対角線の対象を交互に配置したこれは依然として連続的な4接続の $C(\Pi)$ が $\Pi$ におけるボクセルのみを用いて形成できる。これにより、4分離可能性および8接続性が導かれる。結果のボクセル化は幾分ぎこちない《clunky》が、依然として入力のcoverの部分集合であり、それ故に、入力ジオメトリから｜際限なく逸脱する《arbitrarily far》ことは決してない。

似た修正が3Dにおける2次元入力をボクセル化するために十字線の対象に対して行うことができる（図12b）。格子の無作為化は2Dの場合でも機能し、そして、接続の頂点をボクセルのカドに押し出すことによって、我々は、図14に示されるような、各ボクセルに単一の体対角線《space diagonal》から成る｜ひときわ《strikingly》単純な交差対象を得る。4つの取り得る体対角線は、ボクセル間の接続性を維持するため、示される通りに、交互に配置されなければならず、そのパターンは $2^3$ 個のボクセル周期で繰り返される。結果のボクセル化は2Dの場合にあるものと似たぎこちなさを｜示す《exhibits》が、それでもなおcoverの6分離の部分集合であり、それ故に、入力ジオメトリに対して｜それなりに忠実《reasonably faithful》である。

交差対象の単純さや結果のボクセル数の少なさが審美的側面より重要 --- 例えば、直接的に可視化しないボクセル化の場合 --- である所のアプリケーションでは、単一の対角線の対象を交互に配置する方法が最も効率的な戦略であるかもしれない。