CG・CAD・CAM 3Dアルゴリズム用語集

CG（コンピュータグラフィックス）・CAD・CAM の開発現場で頻出する 3D幾何アルゴリズム関連の専門用語 を、分野別に整理した用語集です。

NURBS曲面やB-Rep幾何演算、メッシュ処理、空間分割構造、レンダリング、工具経路生成など、20年以上のCAD/CAM/CAEソフトウェア開発・3D形状処理の実務経験をもとに、実務でよく登場する用語を厳選しています。

3D幾何表現の基礎

同次座標 (Homogeneous Coordinates) — 3次元の点を4成分ベクトル (x, y, z, w) で表現する方法。平行移動・回転・拡大縮小・透視投影をすべて4x4行列の掛け算で統一的に扱えるため、CGやCADの座標変換パイプラインの基礎となる。
パラメトリック曲線・曲面 (Parametric Curve / Surface) — パラメータ t（曲線）や (u, v)（曲面）を変数として空間座標を出力する関数で幾何形状を表現する方式。CADモデリングカーネルの中核をなす表現形式。
陰関数曲面 (Implicit Surface) — f(x, y, z) = 0 を満たす点の集合として形状を表現する方式。ブーリアン演算やメタボールとの親和性が高く、SDF（符号付き距離関数）と組み合わせて使われることが多い。
ベジエ曲線 (Bézier Curve) — 制御点群からBernstein基底関数を用いて生成される多項式曲線。少数の制御点で滑らかな曲線を直感的に編集できる、スプライン系曲線の原点。
B-スプライン (B-spline) — 複数の低次多項式（セグメント）をノットベクトルで滑らかに接続した曲線・曲面表現。ベジエ曲線と異なり、制御点を動かしても影響範囲が局所的（ローカル制御性）なのが特長。
NURBS (Non-Uniform Rational B-Spline) — B-splineに各制御点の重み（ウェイト）を加えた有理表現。円・楕円・球などの2次曲線を完全に表現でき、業界標準のCADカーネル（ACIS, Parasolid など）の基幹表現として採用されている。
制御点とノットベクトル (Control Point / Knot Vector) — 制御点は曲線・曲面の形状を決める基準点、ノットベクトルはパラメータ空間をどこで区切って基底関数を切り替えるかを定める非減少数列。両者の組み合わせで曲線の形状と滑らかさが決まる。
連続性 G0/G1/G2 (Geometric Continuity) — 曲線・曲面の接続部の滑らかさの度合い。G0は位置連続、G1は接線方向連続、G2は曲率連続を意味し、意匠面（クラスA サーフェス）ではG2以上が要求されることが多い。

ソリッド・サーフェスモデリング（CAD）

B-Rep (Boundary Representation) — 立体形状を面（Face）・辺（Edge）・頂点（Vertex）とその接続関係（トポロジー）で表現する方式。ほぼすべての商用CADカーネルが採用する厳密形状表現。
CSG (Constructive Solid Geometry) — 直方体・円柱・球などのプリミティブ形状をブーリアン演算（和・差・積）で組み合わせて立体を構築する表現方式。B-Repと組み合わせて使われることも多い。
トポロジー要素 (Face / Edge / Vertex / Loop / Shell) — B-Repを構成する階層構造。Faceは面、Edgeは稜線、Vertexは頂点、Loopは面の境界を成す閉じた辺の列、Shellは面の集合が閉じた殻を成す構造を指す。
ブーリアン演算 (Boolean Operation) — 2つの立体に対して和（Union）・差（Subtract）・積（Intersect）を計算し、新しい形状を生成する演算。B-Repカーネルにおいて実装が最も複雑な演算のひとつ。
トリムサーフェス (Trimmed Surface) — 基となるパラメトリック曲面に対し、パラメータ空間上の境界曲線（トリム曲線）で有効領域を切り出したサーフェス。複雑な自由曲面形状の表現に不可欠。
オフセット曲面/曲線 (Offset Surface / Curve) — 元の曲面・曲線から法線方向に一定距離だけシフトさせた形状。金型設計や板金モデリング、CAMの工具経路生成で多用される。
フィレット・シャンファー (Fillet / Chamfer) — フィレットは稜線を滑らかな円弧・自由曲面で丸める処理、シャンファーは平面で面取りする処理。応力集中の緩和や意匠性向上のためCADモデリングで頻繁に使われる。
フィーチャーベース・パラメトリックモデリング (Feature-based Parametric Modeling) — 押し出し・回転・穴あけなどの操作（フィーチャー）を履歴（ヒストリーツリー）として積み重ね、寸法パラメータを変更すると形状が自動再構築されるモデリング手法。
ダイレクトモデリング (Direct Modeling) — 履歴を持たず、形状の面や辺を直接プッシュ・プル操作で編集するモデリング手法。他社CADデータの修正など、フィーチャーベースが不得手な場面で有効。
デジェネレート/縮退 (Degeneracy) — 曲面の一部がエッジや点に潰れる特異な状態（例：円錐の頂点）。B-Repカーネルの実装で特別なハンドリングが必要となる代表的な難所。

メッシュ処理・離散幾何

ポリゴンメッシュ (Polygon Mesh) — 頂点・辺・面（多くは三角形または四角形）の集合で立体表面を近似する離散表現。リアルタイムCGレンダリングやFEM解析の基本データ構造。
テッセレーション / 三角形分割 (Tessellation / Triangulation) — NURBSなどのパラメトリック曲面を、指定した許容誤差（トレランス）内でポリゴンメッシュに変換する処理。表示・干渉チェック・3Dプリントの前処理として必須。
半辺データ構造 (Half-edge Data Structure) — 各辺を2つの有向半辺に分割して隣接面・隣接頂点への参照を保持するメッシュ表現。トポロジー走査（隣接面探索など）が高速に行えるため、メッシュ編集アルゴリズムで広く使われる。
ドロネー三角形分割 (Delaunay Triangulation) — 任意の三角形の外接円内に他の点を含まないという条件を満たす三角形分割。ボロノイ図の双対であり、有限要素メッシュ生成の基礎アルゴリズム。
ボロノイ図 (Voronoi Diagram) — 平面・空間上の各点に対し、最も近い母点ごとに領域を分割した図。メッシュ生成、経路計画、最近傍探索などに応用される。
メッシュ簡略化 (Mesh Decimation / Simplification) — 見た目や誤差の許容範囲を保ちながらポリゴン数を削減する処理。QEM（Quadric Error Metrics）による辺の縮約が代表的な手法。
サブディビジョンサーフェス (Subdivision Surface) — 粗いポリゴンメッシュを再帰的に分割・平滑化して滑らかな曲面を得る手法。Catmull-Clark方式が代表例で、アニメーション映画のキャラクターモデリングで広く使われる。
Marching Cubes — ボクセルグリッド上のスカラー場（陰関数値）から等値面（Isosurface）を三角形メッシュとして抽出するアルゴリズム。CTスキャンデータの表面復元や陰関数曲面のポリゴン化に使われる。
点群からの表面再構成 (Surface Reconstruction, Poisson Reconstruction) — 3Dスキャナーで取得した点群データから、法線情報をもとに滑らかで水密（watertight）なメッシュを復元する処理。逆問題として定式化されたポアソン再構成が代表的手法。
メッシュ修復 (Mesh Repair / Watertight化) — 穴・自己交差・非多様体（Non-manifold）といったメッシュの不整合を検出・修正し、3Dプリントや解析に耐える閉じた形状に整える処理。
法線推定 (Normal Estimation) — 点群やメッシュの各点・面における法線ベクトルを近傍情報（主成分分析や隣接面の外積など）から算出する処理。シェーディングやオフセット計算の前提となる。
測地線距離 (Geodesic Distance) — 曲面・メッシュの表面から離れずに2点間を移動する最短経路の長さ。直線距離（ユークリッド距離）とは異なり凹凸のある表面では常に大きな値をとる。メッシュ上ではグラフ近似（Dijkstra法）やFast Marching Method、Heat Methodなどで計算される。詳細とThree.jsによるインタラクティブな可視化は特集記事「測地線距離（Geodesic Distance）とは何か」を参照。

空間分割・高速化構造

BVH (Bounding Volume Hierarchy) — オブジェクトを包含する境界ボリューム（AABBなど）を階層的なツリー構造にまとめたデータ構造。レイトレーシングや干渉チェックの探索を対数オーダーに高速化する。
AABB / OBB (Axis-Aligned / Oriented Bounding Box) — AABBは座標軸に平行な直方体、OBBは任意方向に回転可能な直方体による形状の簡易包含表現。衝突判定の一次スクリーニングに使われる。
Octree（八分木） — 3D空間を再帰的に8等分して階層化する空間分割構造。ボクセル表現、点群の間引き、衝突判定の高速化などに利用される。
kd-tree — 空間を軸に垂直な超平面で再帰的に2分割する木構造。最近傍探索（k-NN）や点群処理で標準的に使われるデータ構造。
BSPツリー (Binary Space Partitioning Tree) — 任意の平面（多くは形状の面自体）で空間を再帰的に2分割する木構造。可視面判定やブーリアン演算の高速化に古くから用いられる。
空間ハッシュ (Spatial Hashing) — 3D座標をハッシュ関数でバケットに写像し、近傍探索を平均O(1)で行う手法。パーティクルシミュレーションや衝突検出の近傍探索で多用される。
干渉チェック / 衝突検出 (Interference / Collision Detection) — 2つ以上の形状が空間的に重なっているかを判定する処理。BVHなどの空間構造による粗判定（Broad Phase）と、GJKアルゴリズムなどによる精密判定（Narrow Phase）の2段階で構成されるのが一般的。

CGレンダリング・シェーディング

ラスタライズ (Rasterization) — 3Dポリゴンを2Dスクリーン上のピクセルに変換する処理。GPUのリアルタイムレンダリングパイプラインの基幹アルゴリズムで、Zバッファと組み合わせて可視面判定を行う。
Zバッファ / 深度バッファ (Z-buffer / Depth Buffer) — 各ピクセルにおける視点からの最短距離を記録し、遮蔽されたオブジェクトの描画を除外する可視面判定手法。
レイトレーシング (Ray Tracing) — 視点から光線（レイ）を飛ばしてシーン中の形状との交差判定を行い、反射・屈折・影を物理的に正確に計算するレンダリング手法。
パストレーシング (Path Tracing) — レイトレーシングを拡張し、光の経路をモンテカルロ法で確率的にサンプリングすることで、間接照明を含むフォトリアルな大域照明（Global Illumination）を実現する手法。
レイマーチング / SDF (Ray Marching / Signed Distance Field) — 陰関数曲面（符号付き距離関数）に沿ってレイを段階的に進め、距離がしきい値以下になった点を交差点とみなすレンダリング手法。フラクタルや流体表現などプロシージャルな形状表現と相性が良い。
BRDF (Bidirectional Reflectance Distribution Function) — 物体表面において、入射光がどの方向にどれだけ反射するかを表す関数。物理ベースレンダリング（PBR）の中核をなす概念。
PBR (Physically Based Rendering) — 実世界の光の反射・エネルギー保存則に基づいたシェーディングモデルで質感を表現するレンダリング手法。マテリアルをアルベド・ラフネス・メタルネスなどのパラメータで統一的に扱う。
UVマッピング (UV Mapping) — 3Dメッシュの表面を2Dテクスチャ画像の座標系（U, V）に展開する処理。テクスチャペイントや法線マップ適用の前提となる。
法線マップ (Normal Mapping) — 低ポリゴンメッシュの表面に、法線情報をテクスチャとして焼き込むことで、実際のジオメトリを増やさずに凹凸のディテールを表現する手法。
シェーダー (Vertex / Fragment / Compute Shader) — GPU上で並列実行される小規模プログラム。頂点変換を担うVertex Shader、ピクセル単位の色計算を担うFragment（Pixel）Shader、汎用並列計算を担うCompute Shaderに大別される。

CAM・工具経路生成

ツールパス生成 (Toolpath Generation) — CADの形状データから、工作機械の切削工具が実際にたどる移動経路（CLデータ）を計算するCAMの中核処理。形状・工具径・切削条件を考慮して生成される。
CLデータ (Cutter Location Data) — 工具先端の位置と工具軸方向を時系列で記述した中間データ形式。CAM側で生成され、ポストプロセッサによって機械依存のNCコードへ変換される。
ポストプロセッサ (Post Processor) — CAMが生成した工具中心座標のCLデータを、特定の工作機械・制御装置固有のNCコード（Gコード等）に変換するモジュール。
ポケット加工 (Pocket Milling) — 閉じた輪郭の内側をくり抜くように切削する加工パターン。オフセットベースの等距離パスや、ジグザグ（往復）パスなどの経路生成アルゴリズムが用いられる。
等高線加工 / ウォーターライン加工 (Contour / Waterline Machining) — 一定のZ高さごとに形状をスライスし、その等高線に沿って工具を移動させる荒加工・仕上げ加工手法。急峻な斜面の仕上げに強い。
5軸加工 (5-axis Machining) — 直交3軸（X, Y, Z）に加えて2つの回転軸を制御し、工具姿勢を自由に傾けながら切削する加工方式。アンダーカット形状やタービンブレードなど複雑形状の一発加工が可能。
工具干渉チェック / ガウジチェック (Gouge Check) — 工具やホルダーが加工対象・治具と意図せず干渉（過削り）していないかをシミュレーション上で検証する処理。B-Repやボクセルモデルとの距離計算で実装される。
残り材認識 / ストックモデル (Rest Material Recognition / Stock Model) — 前工程までの加工で削り残された材料形状をボクセルやメッシュで追跡し、後工程の効率的な工具パス生成（無駄な空振りの削減）に利用する技術。
切削シミュレーション (Machining Simulation) — 工具経路に沿って素材形状を仮想的に除去し、加工結果や干渉・過削りを事前検証するシミュレーション。ボクセルベース、ソリッドベース（B-Rep）など複数の実装方式がある。

数値計算・最適化アルゴリズム

ニュートン法 (Newton’s Method / Newton–Raphson) — 関数の根を反復的に求める数値解法。曲線・曲面上の最近点探索や、非線形連立方程式を解く交差判定アルゴリズムの内部で広く利用される。
最小二乗法 (Least Squares Fitting) — 観測データ・点群に対して誤差の二乗和を最小化するようにパラメトリック曲線・曲面をフィッティングする手法。逆エンジニアリング（点群からNURBS曲面を生成する処理）で使われる。
ICP (Iterative Closest Point) — 2つの点群・メッシュ間の最近傍点対応を反復的に求め、剛体変換（回転・並進）を推定して位置合わせ（レジストレーション）するアルゴリズム。3Dスキャンデータの統合で必須の手法。
ロバスト幾何述語 (Robust Geometric Predicate) — 浮動小数点演算の誤差により「点が線のどちら側にあるか」等の判定が誤る問題を、適応精度演算（多倍長演算）で回避する技術。ドロネー三角形分割やブーリアン演算の頑健性を支える。
数値積分 (Numerical Integration, Gaussian Quadrature) — 曲線長・曲面積・体積・質量特性など解析的に解きにくい積分値を、離散サンプル点の重み付き和で近似計算する手法。CAD形状の質量特性計算やFEM解析で用いられる。
有限要素法 (FEM: Finite Element Method) — 連続体をメッシュ分割した有限個の要素に離散化し、各要素内で近似関数を用いて応力・変位・熱などの物理量を数値的に解く解析手法。CAEソフトウェアの中核アルゴリズム。

この用語集は当サイトの更新に合わせて随時拡充していく予定です。CAD/CAM/CAE・3D幾何処理の技術に関するより詳しい解説は、Posts の技術記事もあわせてご覧ください。