パズルゲームのご紹介

パズルゲームのご紹介 キューブを転がしてパズルを解こう

CuOnPa ブラウザゲームです。THREE.jsを使ったポリゴンのパズルが楽しめます

操作ルール 1 2 3 サイコロを転がす 色の一致が条件 パネルが消える 上下左右に1マスずつ転がして 移動できる 移動先のパネルがカラーパネル の場合、 上面の色が一致する時だけ移 動できる カラーパネルに乗ると、その パネルは白パネルに変わる

クリア条件 カラーパネルをすべて消去！ ⏱ 🎯 ステップ数制限あり 決められた手数以内でクリアを目指す 全パネルが対象 1枚も残さず消すとステージクリア

ステージ構成 50 ステージ 🔓 順番にクリアすると次のステージが解放される 🧩 ステージが進むほど難易度が上がっていく 🏆 すべてのステージを制覇しよう！

それでは楽しんで！ ゲームのありかは後ほどお伝えします

C++で書いてみよう ブラウザゲームは便利だけど…

ブラウザゲーム ・WebGLで3D描画 ・THREE.jsがレンダリングを担当 ・ブラウザ上で即座に動作 ・GPU任せで手軽に実装

• http://three.js

Windows アプリ C++、Win32、CPU描画 ・GPUを一切使わない ・3Dライブラリも使わない ・CPUでポリゴンを描画 ・Win32 API で画面に出力

ポリゴンを描いてみよう 3Dグラフィックスの原点、ラスタライズの仕組みと最適化

多角形ポリゴンが抱える「ねじれ」の問題 ❖ 幾何学的な事実 ➢ 4角形以上の多角形は、すべての頂点が 「同一平面」にあるとは限らない。

多角形ポリゴンが抱える問題 ❖ テクスチャマッピングへの影響 ➢ 四角形以上のポリゴンは、絵の割り当てを計算するための補間基準が一意 に決まらず、描画エラーやテクスチャの歪みの原因になる。

多角形ポリゴンが抱える「ねじれ」の問題 ❖ 解決策 ➢ どんな多角形であっても、必ず3点が同一平面を保証する最 小単位＝「三角形」に分割する。

遠近感（パース）の表現とテクスチャの歪み アフィン写像（初代PlayStation方式）： ● ● 画面上の2D座標だけで単純に線形補間（Z深度を無視）。 カメラが動くと、床や壁のテクスチャがグニャグニャと歪む。

遠近感（パース）の表現とテクスチャの歪み パースペクティブ・コレクト（現代の方式）： ● ● 3次元の深度（1/Z）を考慮してテクスチャを補間。 奥に行くほど綺麗に縮小し、正しい遠近感を表現。

ラスタライズ（フラットシェーディング） ラスタライズとは 3D空間から2Dの画面座標（ピクセル）に投影された三角形を、画面上 のドットへと分解して塗りつぶす処理。

ラスタライズ（フラットシェーディング） ステップ1：頂点のソートとパターン分岐 3つの頂点をY軸（縦方向）の座標で昇順に並 べ替える （Top ➔ Middle ➔ Bottom）。

ラスタライズ（フラットシェーディング） ステップ1：頂点のソートとパターン分岐 2つの基本パターン Middle（中点）の頂点が、TopとBottom を結ぶ直線に対して「左側」にあるか 「右側」にあるかで、スキャンラインの エッジ計算が2通りに分岐する。

ラスタライズ（フラットシェーディング） ステップ2：スキャンライン分解（三角形の2分割） 三角形の2分割 任意の三角形を、Middle頂点を通る「水平線」で上下 2つに分解してループ処理する。 1. 2. 上半分：TopからMiddleまで（底辺が水平な「フ ラットボトム」三角形） 下半分：MiddleからBottomまで（上辺が水平な 「フラットトップ」三角形）

ラスタライズ（フラットシェーディング） ステップ2：スキャンライン分解（三角形の2分割） 三角形の2分割 任意の三角形を、Middle頂点を通る「水平線」で上下 2つに分解してループ処理する。 1. 2. 上半分：TopからMiddleまで（底辺が水平な「フ ラットボトム」三角形） 下半分：MiddleからBottomまで（上辺が水平な 「フラットトップ」三角形）

ラスタライズ（フラットシェーディング） 頂点座標の精度 整数座標の罠 頂点座標を整数（ピクセル単位）に丸めると、エッジ（直線）の傾きに誤差が生まれ、場合 により輪郭の震えになる。 固定小数点（Fixed-Point）の導入 ピクセル未満の細かい位置（例：1/16ピクセル単位）を保持してエッジ計算を行う。移動 時にポリゴンの輪郭がブルブルと震える「ジッター現象」を劇的に軽減する。

ラスタライズ（フラットシェーディング） 頂点座標の精度

ステップ 6 ディザリングによる半透明 // Bayer 4×4 行列（0〜14 の 16 段階しきい値） static const uint8_t BAYER4[4][4] = { { 0, 8, 2, 9 }, { 11, 4, 13, 6 }, { 3, 10, 1, 8 }, { 14, 7, 12, 5 }, }; // alpha = カラー値の上位 4bit（0〜15） uint32_t alpha = tri.color >> 28; // スパン内（ピクセルごと） if (alpha > BAYER4[py % 4][px & 3]) { rowColor[px] = shadedColor; // 描画 } // → しきい値以下のピクセルはスキップ Bayer 4×4 行列 0 8 2 9 11 4 13 6 3 10 1 8 14 7 12 5 小 = 描画されやすい（暗い） 大 = 描画されにくい（明るい） 4×4 = 16 種類のしきい値 → 16 段階の alpha alpha=0 全ピクセルスキップ（完全透明） alpha=15 全ピクセル描画（完全不透明）

ディザリングによる半透明

現代のGPUラスタライズアルゴリズム ● ● ● アーキテクチャの激変: 数千個のコアが同時に動くGPUの登場 スキャンライン法の限界: 1行ずつ順番に処理する方式では、数千のコアを遊ばせ てしまう 目指すべきゴール: 「各ピクセルが、お互いを気にせず完全に独立して計算できる アルゴリズム」への転換

現代の主流「バウンディングボックス方式」 「エッジに沿って塗る」から 「四角い枠の中をまとめて判定する」へ 1. 三角形の3頂点（最小・最大のX, Y座標）から、完全に 囲む四角い枠（Bounding Box）を作る 2. その枠内にあるすべてのピクセルに対して、一斉に「内 か外か」のテストを行う

どうやって判定しているのか？（エッジ関数） ● 数式による一発判定 : ○ 辺のベクトルとピクセル座標から、内外を判定する関数 ● 3つの辺でチェック : ○ 線の「右側」にあるか「左側」にあるかをプラス・マイナスの 符号で返す3つのエッジすべてで「内側」と判定されたピクセ ルだけが合格 ● ハードウェア化 : ○ GPU内の専用回路（ Rasterizer）がこの計算を高速に処理

無駄を省く「階層的（Hierarchical）ラスタライズ」 巨大な三角形でも重くならない「階層的ラスタライズ」 全ピクセル判定の罠 : 大きな三角形で、枠内の全ピクセルを愚直に調べると非効率 ブロック単位の先行カリング : ● ● まず「8x8」や「4x4」といった粗いブロック単位でエッジ関数をかける 完全に外側のブロック、完全に内側のブロックを大雑把に見分ける 処理の最適化: 境界線がまたがるブロックだけ、詳細なピクセル単位の判定を行う

以上 ご清聴ありがとうございました