WebGLでレイマーチングを使ったCSGを実現する

2019/04/08
このエントリーをはてなブックマークに追加

TL;DR これ作った。

こんにちは。カブクでThree.js周りを担当していたけど、現状ほとんど触れていないあんどうです。

今はもうただひたすらに、目標をセンターに入れて座標変換、目標をセンターに入れて座標変換・・・。もちろんそれはそれで面白みもありますが、たまにはもうちょっとキラキラしたこともやりたい!輝きたい!ということで、今回開発者ブログの場を借りて輝こうと思います。

CSG

現在、弊社の開発しているサービスの主なターゲットは製造業です。個人的にはもう少し付加製造(3Dプリンタ)が流行ると嬉しいのですが、現実問題として世の中のほとんどのものは切削加工で製造されています。成形加工もありますが、そこで使用される型はほとんどが切削加工品でしょう。私が3Dモデル生成している製品もご多分に漏れず切削加工で製造されます。最終的にはこのモデルをブラウザ上で3Dプレビュー表示したいのですが、こういった切削で製造される製品の3Dモデルはどういう形式で表現するのが適切なのでしょう?

ここで、切削は「土台となる形状から不要な形状を除く」という加工です。つまり

最終形状 = 土台形状 - 不要形状

と表すことができます。実はこのような関係をそのままの形で表現できるモデリング技法があるのです。それがCSG(Constructive Solid Geometry)です。

https://ja.wikipedia.org/wiki/Constructive_Solid_Geometry

CSGでは直方体や円柱、球などの基本形状と、それらに対するブーリアン演算(和・差・交差)の組み合わせで形状を表現します。このCSGであれば切削加工で製造される形状を自然に表現できそうです。ただ、ひとつ問題があります。任意のポリゴンモデルに対するCSGは非常に重たい処理なのです。なぜそうなるかは実際の処理を想像してみるとわかるでしょう。ナイーブな実装では、モデルごとに全ポリゴン同士の交差を計算し、交差する場合は交線でポリゴンを分割してモデルを再構築することを、一回のブーリアン演算ごとに行います。交差計算の頻度はBSPなどを使用して減らすこともできますが、それでもブラウザ上でJavaScriptを使用して実行するとなるとなかなかの重さです。下記のサイトでCSGを実際に実行できるので、試してみるといいでしょう。(と書きましたが試してみると意外とサクサクでした。たぶん頂点数が増えると急激に重くなるはず)

https://evanw.github.io/csg.js/

ではCSGは今回のプレビューには使用できないのでしょうか?実はそういうわけでもありません。確かに実際に製造するのであればどこかで上記のような負荷の高い計算が必要になります。しかし、そのような計算はサーバー上で行えばよく、ブラウザ上で行う必要はありません。ブラウザ上で実行したいのはあくまでプレビュー表示であって、実際のポリゴン操作ではないのです。

レイマーチング

レイマーチングはレイトレーシングの一種で、形状をポリゴンではなく距離関数(数式)で定義します。ポリゴンモデルのブーリアン演算は先ほど説明したとおり面倒な処理でしたが、距離関数のブーリアン演算はどうでしょう?

それが実は、ものすごく簡単なのです。

距離関数はある座標からその形状表面への最短距離を返す関数で、返り値はひとつの数値です。例えば形状1の距離関数の値がdist1、形状2の距離関数の値がdist2だとすると、形状1と形状2のブーリアン演算の結果は次のように表せます。

  • 和: min(dist1, dist2)
  • 差: max(dist1, -dist2)
  • 交差: max(dist1, dist2)

ブーリアン演算の説明は後述しますが、レイマーチングではCSGを非常に簡単に実現できることがわかるでしょう。

それではレイマーチングの説明に移ります。先ほども書きましたがレイマーチングでは形状を、与えられた座標からその形状までの最短距離を返す距離関数で表現します。例えば原点にある半径rの球の距離関数は次のようになります。

float sphereDist(vec3 p, float r) {
  return length(p) - r;
}

pから原点にある半径rの球までの最短距離は、点pから原点までの距離から半径rを引いた値です。なぜそのような式になるかは下の図を見ると明らかでしょう。

直方体や円柱などの形状も同様に与えられた座標からの最短距離を単純な関数で取得できます。

それでは、それらの距離関数を使用してシーンを描画するにはどうすればいいのでしょう?

上の図を見てください。レイマーチングはフラグメントシェーダーで実装します。フラグメントシェーダーは簡単に言うと、ピクセルごとに実行されて、そのピクセルの色を決定する小さなプログラムです。左側の垂線がシーンを表示する画面(視錐台の近平面)、その上の緑・黄色・赤の円がスクリーン上の各ピクセル(フラグメント)、そしてその各ピクセルから右に伸びる線がスクリーンから視線方向に伸びるレイ(半直線)だと考えてください。レイがなにかに衝突すると、その衝突した位置の色がフラグメントに設定されます。レイマーチングでフラグメントの色を求める手順は次のとおりです。

  1. フラグメントの現在の色を黒(背景色、物体なし)に設定する
  2. シーンに存在するすべての物体と現在のレイの先端との距離(距離関数の値)を求める
  3. 最も小さい(近い)距離関数の値を選択する
  4. 最も小さい距離関数の値が大きければ、レイを進行方向にその距離だけ進め、2に戻る
  5. 最も小さい距離関数の値が十分に小さければ、その位置の色を現在の色に加える
    1. 反射を処理する場合は、レイの位置は変更せず、レイの進行方向を衝突位置の法線を使用して反射して、2に戻る
    2. 反射を処理しない場合は、終了する

真ん中の黄色いフラグメントを例にしてレイマーチングの処理を具体的に説明しましょう。まずは左側の黄色い円の位置にレイの先端があるものとします。レイの先端から緑の四角と赤の丸までの最短距離をそれぞれ求めると赤い丸との距離のほうが小さく、しかし十分に小さいわけではないので、得られた距離だけレイを進めます。するとレイの先端が最も左側の白丸の位置に移動します(1)。

同様に緑四角と赤丸との距離を求めると今度も赤丸との距離のほうが小さく、しかし十分に小さいわけではないので、真ん中の白い円の位置までレイを進めます。同様に距離関数の値を求めると今度は緑四角との距離が近いので、右の白い円の位置までレイを進めます。同様に繰り返すと緑の円の位置までレイの先端が進みます(2)。

レイが衝突した点の色が緑なのでフラグメントの色を仮に緑とします。今回は緑四角も赤丸も光を鏡面反射するので、衝突位置の法線を中心として対照になるようにレイの進行方向を変更します。そしてこれまでと同様にレイを進めます。はじめはレイの先端と緑四角が近いためゆっくりと最初の衝突点を離れますが、次第に一回の移動量が大きくなります。そして赤丸との衝突点が近づくに連れて移動量が再び小さくなり、いずれ赤丸に衝突します(3)。

赤丸に衝突したということは、緑四角の衝突点には赤丸の鏡像が写っていることになるので、視点から直接見える緑と、その緑に写っている赤を合成して、フラグメントの色を黄色に設定します(4)。

同様の処理をすべてのフラグメントに対して行うと、次の図の左端の垂線のような(1次元の)シーンが描画されます。

同様な処理を次元をひとつ増やして行えば、3次元空間を平面上に射影できます。

実装

全体的な処理の流れの説明は以上です。ここからはソースコードの説明に移りましょう。レイマーチングの主要なコードについてはThree.jsに付属している例をほぼそのまま使用しています。この例の作者であるgamさんによる説明がQiitaにありますので、そちらも参考にしてください。

https://threejs.org/examples/?q=ray#webgl_raymarching_reflect

なお、今回説明するのは実際にレイマーチングを行っているフラグメントシェーダーのコードだけです。それ以外の部分についてはここでは特に説明しません。興味のある方はソースコードを自分で読んでみてください。Three.jsを使用しているので、それなりに雰囲気で理解できるのではないかと思います。

それでははじめに処理全体を駆動する部分を見ていきます。

void main(void) {
  // レイは画面内でのフラグメントの位置からカメラの向いている方向に飛ばす
  vec2 screenPos = (gl_FragCoord.xy * 2.0 - resolution) / resolution;
  vec4 ndcRay = vec4(screenPos.xy, 1.0, 1.0);
  vec3 rayDirection = (cameraWorldMatrix * cameraProjectionMatrixInverse * ndcRay).xyz;
  rayDirection = normalize(rayDirection);

  // レイの始点はカメラ位置
  vec3 rayOrigin = cameraPosition;

  // フラグメントの初期色を黒に設定
  vec3 color = vec3(0.0);

  vec3 nextRayPos, normal;
  bool hit;
  float attenuation = 1.0;

  // 反射は2回まで処理
  for (int i = 0; i < 3; i++) {
    // レイを飛ばして衝突した位置の色を加算
    color += attenuation * getRayColor(rayOrigin, rayDirection, nextRayPos, normal, hit);

    if (!hit) {
      // レイが物体表面と衝突していなければ反射せずにループを抜ける
      break;
    }

    // レイが物体表面と衝突していれば反射して処理を繰り返す
    
    // 反射するたびに次の色の影響を弱める
    attenuation *= 0.3;

    // 衝突点の法線を使用してレイを反射
    rayDirection = normalize(reflect(rayDirection, normal));

    // 同じ位置で衝突を繰り返さないようにレイの始点をずらす
    rayOrigin = nextRayPos + normal * OFFSET;

  }
  gl_FragColor = vec4(color, 1.0);
}

コメントを多めに入れたのでなんとなく読めるのではないでしょうか。レイマーチングによるレイの衝突確認はforループ内のgetRayColor関数で行います。レイが物体表面に衝突していた場合は同じ処理を繰り返して2回まで反射を処理します。

getRayColor関数のコードは次のとおりです。

vec3 getRayColor(vec3 rayOrigin, vec3 rayDirection, out vec3 rayPosition, out vec3 normal, out bool hit) {
  float dist;
  float depth = 0.0;
  rayPosition = rayOrigin;

  // 距離関数の値だけレイを進める処理を64回繰り返す
  for (int i = 0; i < 64; i++) {
    // 距離関数を実行
    dist = sceneDist(rayPosition);

    // 距離関数の値が十分に小さければ探索を停止
    if (abs(dist) < EPS) {
      hit = true;
      break;
    }

    // 距離関数の値がまだ大きければレイを進めてから処理を繰り返す
    depth += dist;
    rayPosition = rayOrigin + depth * rayDirection;
  }

  if (!hit) {
    // 衝突していなければ物体表面の色は黒
    return vec3(0.0);
  }
    
  // 衝突したら反射の処理で使用するための法線を設定しておく
  normal = getNormal(rayPosition);

  // 光の向きと法線の向きから物体表面の色を取得
  vec3 color = getLightColor(light1Dir, rayDirection, rayPosition, normal)
    + getLightColor(light2Dir, rayDirection, rayPosition, normal);

  // 視点から表面までの距離分だけ色を減衰して返す
  return color - pow(clamp(0.05 * depth, 0.0, 0.6), 2.0);
}

forループ内で呼び出しているsceneDist関数が今回の距離関数で、シーン内の最も近い物体からの距離distを返します。distの値が小さければレイの進行を停止して、その位置の色を返します。distの値が大きければレイを進める処理を繰り返し、64回レイを進めても物体との衝突が発生しなければ、黒色を返します。

それでは今回の距離関数sceneDistの実装を見てみましょう。

float sceneDist(vec3 p) {
  float cube = boxDist(p, vec3(2., 2., 2.));
  float cylinder = cylinderDist(p, 0.5, 4.0);
  float sphere = sphereDist(p, 1.);
  return differ(unite(cube, cylinder), sphere);
}

まだ説明していない関数ばかりですが、やりたいことは何となく分かるのではないでしょうか。各辺の長さ2の立方体(cube)と、半径0.5で高さ4の円柱(cylinder)と、半径1の球(sphere)があり、立方体と円柱を結合(unite(cube, cylinder))した形状から、球の形状を取り除いて(differ(..., sphere))います。

原点にある球と立方体と円柱の距離関数はそれぞれ次のようになります。

float sphereDist(vec3 p, float r) {
  return length(p) - r;
}

float boxDist(vec3 p, vec3 size) {
  vec3 d = abs(p) - size / 2.0;
  return length(max(d,0.0)) + min(max(d.x,max(d.y,d.z)),0.0);
}

float cylinderDist(vec3 p, float radius, float height) {
  vec2 d = vec2( length(p.xz)-radius, abs(p.y) - height / 2.0);
  return min(max(d.x,d.y),0.0) + length(max(d,0.0));
}

詳細は省略しますが、非常に簡単な式で基本形状を定義できていることがわかります。下のサイトでさまざまな形状の距離関数が紹介されているので興味のある方はぜひ見てみてください。

http://iquilezles.org/www/articles/distfunctions/distfunctions.htm

最後にCSGの実装について説明します。先ほど紹介しましたが、ここでソースコードを再掲しておきます。

float unite(float dist1, float dist2) {
  return min(dist1, dist2);
}

float differ(float dist1, float dist2) {
  return max(dist1, -dist2);
}

float intersect(float dist1, float dist2) {
  return max(dist1, dist2);
}

なぜこれでうまくいくのか、単純すぎて逆にわかりにくいかもしれませんが、図にすると明らかでしょう。

左側に縦一列に並んでいる丸から右方向にレイを飛ばし、各物体(大きな赤丸と青丸)と交わる点までの距離を計算して、maxであれば右側にある方、minであれば左側にある方を採用します。なお、距離を負数にすると画面から見て裏面が使用されます。基本的にはただ距離の大小を比較するだけの非常に単純な処理ですが、それぞれ対象となる点までの距離を正しく返すことができています。

確認

それでは実際に動かしてみましょう。

https://technohippy.github.io/raymarching-csg/

立方体と円柱を結合してから球が取り除かれた期待通りの形状が描画されています。上記サンプルではワイヤーフレームのオーバーレイに加え、各形状の回転や平行移動、拡大縮小も試せるようにしてありますので、ぜひいろいろと触ってみてください。ソースコードも以下で確認できます。

https://github.com/technohippy/raymarching-csg

さいごに

株式会社カブクではキラキラ輝きたいピュアで素敵な開発者を募集しています。

その他の記事

Other Articles

2019/08/14
Maker Faire Tokyo 2019でARゲームを出展しました

2019/07/25
夏休みだョ!WebAssembly Proposal全員集合!!

2019/07/08
鵜呑みにしないで! —— 書籍『クリーンアーキテクチャ』所感 ≪null 篇≫

2019/07/03
W3C Workshop on Web Games参加レポート

2019/06/28
TypeScriptでObject.assign()に正しい型をつける

2019/06/25
カブクエンジニア開発合宿に行ってきました 2019夏

2019/06/21
Hola! KubeCon Europe 2019の参加レポート

2019/06/19
Clean Resume きれいな環境できれいな履歴書を作成する

2019/05/20
[Web フロントエンド] 状態更新ロジックをフレームワークから独立させる

2019/04/16
C++のenable_shared_from_thisを使う

2019/04/12
OpenAPI 3 ファーストな Web アプリケーション開発(Python で API 編)

2019/04/02
『エンジニア採用最前線』に感化されて2週間でエンジニア主導の求人票更新フローを構築した話

2019/03/29
その1 Jetson TX2でk3s(枯山水)を動かしてみた

2019/03/27
任意のブラウザ上でJestで書いたテストを実行する

2019/02/08
TypeScript で “radian” と “degree” を間違えないようにする

2019/02/05
Python3でGoogle Cloud ML Engineをローカルで動作する方法

2019/01/18
SIGGRAPH Asia 2018 参加レポート

2019/01/08
お正月だョ!ECMAScript Proposal全員集合!!

2019/01/08
カブクエンジニア開発合宿に行ってきました 2018秋

2018/12/25
OpenAPI 3 ファーストな Web アプリケーション開発(環境編)

2018/12/23
いまMLKitカスタムモデル(TF Lite)は使えるのか

2018/12/21
[IoT] Docker on JetsonでMQTTを使ってCloud IoT Coreと通信する

2018/12/11
TypeScriptで実現する型安全な多言語対応(Angularを例に)

2018/12/05
GASでCompute Engineの時間に応じた自動停止/起動ツールを作成する 〜GASで簡単に好きなGoogle APIを叩く方法〜

2018/12/02
single quotes な Black を vendoring して packaging

2018/11/14
3次元データに2次元データの深層学習の技術(Inception V3, ResNet)を適用

2018/11/04
Node Knockout 2018 に参戦しました

2018/10/24
SIGGRAPH 2018参加レポート-後編(VR/AR)

2018/10/11
Angular 4アプリケーションをAngular 6に移行する

2018/10/05
SIGGRAPH 2018参加レポート-特別編(VR@50)

2018/10/03
Three.jsでVRしたい

2018/10/02
SIGGRAPH 2018参加レポート-前編

2018/09/27
ズーム可能なSVGを実装する方法の解説

2018/09/25
Kerasを用いた複数入力モデル精度向上のためのTips

2018/09/21
競技プログラミングの勉強会を開催している話

2018/09/19
Ladder Netwoksによる半教師あり学習

2018/08/10
「Maker Faire Tokyo 2018」に出展しました

2018/08/02
Kerasを用いた複数時系列データを1つの深層学習モデルで学習させる方法

2018/07/26
Apollo GraphQLでWebサービスを開発してわかったこと

2018/07/19
【深層学習】時系列データに対する1次元畳み込み層の出力を可視化

2018/07/11
きたない requirements.txt から Pipenv への移行

2018/06/26
CSS Houdiniを味見する

2018/06/25
不確実性を考慮した時系列データ予測

2018/06/20
Google Colaboratory を自分のマシンで走らせる

2018/06/18
Go言語でWebAssembly

2018/06/15
カブクエンジニア開発合宿に行ってきました 2018春

2018/06/08
2018 年の tree shaking

2018/06/07
隠れマルコフモデル 入門

2018/05/30
DASKによる探索的データ分析(EDA)

2018/05/10
TensorFlowをソースからビルドする方法とその効果

2018/04/23
EGLとOpenGLを使用するコードのビルド方法〜libGLからlibOpenGLへ

2018/04/23
技術書典4にサークル参加してきました

2018/04/13
Python で Cura をバッチ実行するためには

2018/04/04
ARCoreで3Dプリント風エフェクトを実現する〜呪文による積層造形映像制作の舞台裏〜

2018/04/02
深層学習を用いた時系列データにおける異常検知

2018/04/01
音声ユーザーインターフェースを用いた新方式積層造形装置の提案

2018/03/31
Container builderでコンテナイメージをBuildしてSlackで結果を受け取る開発スタイルが捗る

2018/03/23
ngUpgrade を使って AngularJS から Angular に移行

2018/03/14
Three.jsのパフォーマンスTips

2018/02/14
C++17の新機能を試す〜その1「3次元版hypot」

2018/01/17
時系列データにおける異常検知

2018/01/11
異常検知の基礎

2018/01/09
three.ar.jsを使ったスマホAR入門

2017/12/17
Python OpenAPIライブラリ bravado-core の発展的な使い方

2017/12/15
WebAssembly(wat)を手書きする

2017/12/14
AngularJS を Angular に移行: ng-annotate 相当の機能を TypeScrpt ファイルに適用

2017/12/08
Android Thingsで4足ロボットを作る ~ Android ThingsとPCA9685でサーボ制御)

2017/12/06
Raspberry PIとDialogflow & Google Cloud Platformを利用した、3Dプリンターボット(仮)の開発 (概要編)

2017/11/20
カブクエンジニア開発合宿に行ってきました 2017秋

2017/10/19
Android Thingsを使って3Dプリント戦車を作ろう ① ハードウェア準備編

2017/10/13
第2回 魁!! GPUクラスタ on GKE ~PodからGPUを使う編~

2017/10/05
第1回 魁!! GPUクラスタ on GKE ~GPUクラスタ構築編~

2017/09/13
「Maker Faire Tokyo 2017」に出展しました。

2017/09/11
PyConJP2017に参加しました

2017/09/08
bravado-coreによるOpenAPIを利用したPythonアプリケーション開発

2017/08/23
OpenAPIのご紹介

2017/08/18
EuroPython2017で2名登壇しました。

2017/07/26
3DプリンターでLチカ

2017/07/03
Three.js r86で何が変わったのか

2017/06/21
3次元データへの深層学習の適用

2017/06/01
カブクエンジニア開発合宿に行ってきました 2017春

2017/05/08
Three.js r85で何が変わったのか

2017/04/10
GCPのGPUインスタンスでレンダリングを高速化

2017/02/07
Three.js r84で何が変わったのか

2017/01/27
Google App EngineのFlexible EnvironmentにTmpfsを導入する

2016/12/21
Three.js r83で何が変わったのか

2016/12/02
Three.jsでのクリッピング平面の利用

2016/11/08
Three.js r82で何が変わったのか

2016/12/17
SIGGRAPH 2016 レポート

2016/11/02
カブクエンジニア開発合宿に行ってきました 2016秋

2016/10/28
PyConJP2016 行きました

2016/10/17
EuroPython2016で登壇しました

2016/10/13
Angular 2.0.0ファイナルへのアップグレード

2016/10/04
Three.js r81で何が変わったのか

2016/09/14
カブクのエンジニアインターンシッププログラムについての詩

2016/09/05
カブクのエンジニアインターンとして3ヶ月でやった事 〜高橋知成の場合〜

2016/08/30
Three.js r80で何が変わったのか

2016/07/15
Three.js r79で何が変わったのか

2016/06/02
Vulkanを試してみた

2016/05/20
MakerGoの作り方

2016/05/08
TensorFlow on DockerでGPUを使えるようにする方法

2016/04/27
Blenderの3DデータをMinecraftに送りこむ

2016/04/20
Tensorflowを使ったDeep LearningにおけるGPU性能調査

→
←

関連職種

Recruit

バックエンドエンジニア(Python・Go)

業務内容

当ポジションは弊社Webサービスのバックエンド機能設計及び実装を担当します。 サービス毎の開発チームで2週間スプリントのスクラム開発を実施しています。 週次で開発チームミーティングを実施し、実装設計の相談や工数見積もりを行います。 全ての開発コードはレビューと自動テストによって品質を保っています。 また、リファクタリングやフレームワークのバージョンアップも開発フローに組込み、技術的負債を放置しない開発を目指しています。

フロントエンドエンジニア(TypeScript)

業務内容

当ポジションは弊社Webサービスのフロントエンド機能設計及び実装を担当します。 サービス毎の開発チームで2週間スプリントのスクラム開発を実施しています。 週次で開発チームミーティングを実施し、実装設計の相談や工数見積もりを行います。 全ての開発コードはレビューと自動テストによって品質を保っています。 また、リファクタリングやフレームワークのバージョンアップも開発フローに組込み、技術的負債を放置しない開発を目指しています。

インターン(Webエンジニア)

業務内容

業務から独立した、調査・研究系のタスクをおまかせしています。コードレビュー、 社内での報告会、 ブログ記事執筆を通して着実にスキルアップしていただくことを目指しています。 (希望があれば、プロダクトの開発業務もおまかせします。)

→
←

お客様のご要望に「Kabuku」はお応えいたします。
ぜひお気軽にご相談ください。

お電話でも受け付けております
03-6380-2750
営業時間:09:30~18:00
※土日祝は除く