Gint — Technical Architecture

Geographic Interleaved Binary Format
int = interleave（Mortonビットインターリーブ）· integer（64bit整数コード）· intended（設計意図を持ったLOD）
空間インデックス × LODエンコーディング × GPU描画の統合パイプライン

1. 従来手法の問題点

ウェブGISの一般的な実装では、地図タイル（スライプトタイル / MVT）を使い、 ズームレベルごとに独立したファイル群をサーバに事前生成して配信する。

問題	原因	コスト
タイル数の爆発	zoom z での総タイル数は 4z	z=14 で 268 M tiles
ズームごとのネットワーク	各ズームで別タイルを取得	ズームのたびに複数リクエスト
CPU三角形分割	ポリゴンは GPU に直接送れない（凹形・穴）	フレームごとに earcut O(n²) 実行
LODの静的管理	複数解像度を別ファイルで事前生成	ストレージ × LOD数だけ増加

Gint はこれら 4 つの問題を「1ファイル × ゼロ追加ネットワーク × CPU三角分割なし」で解決する。

2. パイプライン概観

3. Stage 1 — エンコーディング

3.1 Morton Order（Z順序曲線）

Mortonコードは 2 次元座標 (x, y) を 1 次元の整数に変換する手法で、 X のビットと Y のビットを インターリーブ（交互配置） することで生成される。

// 2D → Morton コード（32bit座標対応）
function morton2D(x, y) {
	let r = 0;
	for (let i = 0; i < 32; i++) {
		r |= ((x >> i) & 1) << (2*i);      // X bit at even positions
		r |= ((y >> i) & 1) << (2*i + 1);  // Y bit at odd positions
	}
	return r;
}

// ビューポート内フィーチャの抽出（ズームレベル z のビットマスク）
// z=6 なら上位12ビット（2×6）がタイルアドレス
const mask = ~(0xFFFFFFFFFFFFFFFFn >> BigInt(2*z));
const tileKey = mortonCode & mask;  // → タイル内の全フィーチャが同じ prefix を共有

3.2 Visvalingam-Whyatt Weight（LODウェイト）

各頂点に「削除されたとき形状が失う面積」をウェイトとして事前計算し、バイナリに埋め込む。 低ズーム時は高ウェイト頂点のみ使用し、ズームインにつれて閾値を下げ、より細かい頂点を加える。

// エンコード時に全頂点のウェイトを計算して保存
function computeVWWeights(polygon) {
	const n = polygon.length;
	return polygon.map((_, i) => triangleArea(
		polygon[(i - 1 + n) % n],
		polygon[i],
		polygon[(i + 1) % n]
	));
}

// ズームレベルに対応する頂点フィルタ（デコード時）
// ズームレベル z における 1px の地図単位換算
// （例: メルカトル投影、タイルサイズ 256px の場合）
const metersPerPx = (40075016 / (256 * Math.pow(2, z)));
const threshold   = metersPerPx * metersPerPx;  // 1px² → これ未満の頂点はサブピクセル
const activeVerts  = vertices.filter(v => v.weight >= threshold);

4. Stage 2 — GPU VB 書き込み（一度だけ）

クライアントはサーバから GeoPBF を受け取り、一度だけ gint 形式（Morton順ソート済み・VWビット付き）にデコードして GPU 頂点バッファへ転送する。 以降のズーム・パン操作では追加ネットワークリクエストは発生しない。LOD（頂点の間引き）は Stage 3 の vertex shader が毎フレーム VW 閾値で処理する。

4.1 Morton ビットシフトによるビューポートクエリ

// ズームレベル z でのビューポート内フィーチャ検索
// 64bit Morton コードの上位 2z ビットがタイルアドレスを示す

const tileAddr  = morton2D(tileX, tileY);     // ビューポート左上のタイル
const shiftBits = 64 - 2 * z;                    // 右シフト量
const prefix    = tileAddr >> BigInt(shiftBits);  // 上位 2z ビット

// ソート済み配列に対して二分探索
const lo = lowerBound(features, prefix << BigInt(shiftBits));
const hi = upperBound(features, ((prefix + 1n) << BigInt(shiftBits)) - 1n);
const viewport = features.slice(lo, hi);  // O(log n) で絞り込み完了

4.2 ズームレベルと LOD の対応

Zoom	LOD	VW Threshold（例）	有効頂点数（例）	タイル方式ならば
z = 2	LOD 0	maxW × 0.50	22 vertices	1 tile fetch
z = 4	LOD 1	maxW × 0.20	44 vertices	4 tile fetches
z = 6	LOD 2	maxW × 0.07	88 vertices	16 tile fetches
z = 8	LOD 3	maxW × 0.018	176 vertices	64 tile fetches
z = 10	LOD 4	0（全頂点）	352 vertices	256 tile fetches

5. Stage 3 — GPU ステンシルテッセレーション

WebGL でポリゴンを描画するには、通常 CPU で三角形分割（Earcut 等）を行ってから GPU に送る必要がある。 凹ポリゴン・穴あきポリゴンは特に複雑で、高フレームレートを維持することが難しい。

ステンシルテッセレーションは、CPU による三角形分割を完全に排除し、 頂点列をそのまま GPU に渡して 2 パスで描画する手法である。

5.1 Pass 1: ステンシルパス（偶奇カウント）

// 頂点列から NDC 原点(0,0) をファン中心としたトライアングルを生成
// 頂点数 N のポリゴン → N 個のトライアングル（CPU 処理不要）

for (let i = 0; i < N; i++) {
	drawTriangle(
		[0, 0],          // NDC 原点（固定）
		vertices[i],       // 現在の頂点
		vertices[i+1]    // 次の頂点
	);
}

// WebGL ステンシル設定
gl.stencilOp(gl.KEEP, gl.KEEP, gl.INVERT);  // 重なるたびに XOR（0→1→0→1...）
gl.stencilFunc(gl.ALWAYS, 0, 0xFF);
gl.colorMask(false, false, false, false); // カラーバッファは書かない

各ファントライアングルが重なった回数が 奇数 のピクセル = ポリゴン内部、 偶数 = ポリゴン外部（穴・背景）という even-odd ルールが自然に成立する。

5.2 Pass 2: カラーパス

// ステンシルが奇数（内部）のピクセルのみ描画
gl.stencilFunc(gl.EQUAL, 1, 0x01);  // ビット0 = 1 のピクセルのみ通過
gl.colorMask(true, true, true, true);
drawFullscreenQuad(fillColor);     // 全画面クワッドを塗るだけ（GPU 爆速）

5.3 凹ポリゴン・穴の自動処理

5.4 球体カリング — 地平線またぎポリゴン

ファンステンシルは 2D 平面レンダリングでは正しく機能する。しかし正射影（orthographic）の地球儀では、 ポリゴンが地平線（球面の前後境界）をまたぐ場合がある。背面半球の頂点はアイスペースで p.z < 0 となり画面に表示されないが、それでもファントライアングルに参加するため問題が生じる。

単純な対処：裏面頂点を NDC 原点に潰す

// ❌ 地平線付近に縮退トライアングルが発生する
if (p.z < 0.0) { gl_Position = vec4(0.0, 0.0, 0.0, 1.0); return; }

ファンの軸点（NDC 原点）に重ねると、地平線をまたぐエッジで面積ゼロの縮退トライアングルが生じる：

• EXIT（可視 → 裏面）：裏面頂点がファン軸と同点になる → 面積ゼロ。
• BACK-BACK（両方裏面）：両端が同点に潰れる → 2 点間の地平線円弧が塗られない。
• ENTRY（裏面 → 可視）：EXIT と対称。

解決策：裏面頂点を地平線円上に押し出す

潰すのではなく、各裏面頂点を地平線円（球面の投影外縁、半径 u_scale px）上へ、 球中心からの画面方向を保ったまま押し出す：

// ✅ 地平線円上に押し出し — 縮退トライアングルを排除
if (p.z < 0.0) {
	vec2 v = p.xy - u_viewport * 0.5;     // 球中心からの方向ベクトル
	float d = length(v);
	gl_Position = d < 1e-4                 // ガード：頂点が完全に中心と一致
		? vec4(0.0, 0.0, 0.0, 1.0)
		: toNDC(u_viewport * 0.5 + v * (u_scale / d));
	return;
}

6. 性能比較

指標	従来タイル方式	Gint
ファイル数	O(4z) タイル	1 ファイル
初回ロード	現在の z に必要なタイルのみ	全 LOD を含む 1 ファイル
ズームイン時の追加転送	ズームごとに複数タイル	+0 bytes
ビューポートクエリ	tile x/y/z でサーバ問い合わせ	Morton bit-shift O(log n)（ローカル）
LOD 切り替え	別タイルを再取得	メモリ内フィルタのみ（即座）
CPU 三角分割	フレームごとに earcut O(n²)	不要（GPU ステンシル）
穴・凹形ポリゴン	earcut で特別処理が必要	even-odd ルールで自動解決
事前生成コスト	全ズームレベル × 全タイルを生成	1 回のエンコード（Morton sort + VW）

7. 設計思想

地理空間データの表現方法は、どの「詳細さ」を現実として採用するかという選択でもある。 NaturalEarth の physical/cultural という分類が地球上の現象を人間の視点から整理したものであるように、 gint の LOD 設計はスケールによって「見えるもの」を動的に変化させるという概念を実装している。

VW ウェイトは「ある頂点を削除したとき形状が失う情報量」を定量化する。 これは情報理論的には「重要度」の測定であり、 地形や境界線において何が「本質的な構造」で何が「観測スケール依存の詳細」かを数値化したものとも言える。

もうひとつ、正射影地球儀に特有の問題として：日付変更線（経度 ±180°）をまたぐポリゴンは、 描画前にその境界で分割しなければ球の逆側をぐるっと回って描かれてしまう。 球体カリングとこの反子午線（アンチメリジアン）処理、この 2 つが、 平面地図レンダラーと球体レンダラーを分ける、静かに非自明な関門である。

---

デモファイル

ファイル	内容	対応 Stage
GINT.html	Morton オーダーのアニメーション、VW ウェイトの対話的可視化	Stage 1 エンコーディング
LOD.html	動的 LOD：vertex shader が毎フレーム VW 閾値で頂点を破棄	Stage 3 GPU 描画
ST.html	GPU ステンシルテッセレーション：CPU 三角分割との比較	Stage 3 GPU 描画