C++ で 3 次元 Delaunay 分割

某所にて、『2 次元の Delaunay 分割は簡単だから別にいらない。むしろ 3 次元 Delaunay 分割のソースコードが欲しい』という要望を間接的に頂いたので、みんなが大好きな C++ で作ってみましたよー (´-ω-`)

OpenProcessing に投稿した 3D Delaunay Triangulation よりも、若干ですがソースコードがブラッシュアップされているような気がします。

---

今回は 3D という事もあり、結果表示用のプログラムには DirectX 9 を使用しました。最新バージョンを使わなかったのは、Windows XP でも実行できるようにという配慮からです。あ、あくまで環境依存のプログラムは GUI 部分のみであり、アルゴリズム（Delaunay3d.h）は標準 C++ のみで実装しているため、他の環境にもそのまま移植できると思います。

使用方法は昨日の 2 次元 Delaunay 分割とほぼ同じで、以下の通りです（Main.cpp のコールバック関数、および render() 関数に実際のサンプルがあります）。

（※ただし、2 次元と 3 次元のモジュールを共存させようとすると、いたるところで名前が衝突するので注意）

1. 頂点セット（std::set<Tercel::Vector> オブジェクト）を宣言します。
2. 先ほどの頂点セットに、適当な頂点オブジェクトを格納します。
3. 三角形セット（std::set<Tercel::Triangle> オブジェクト）を宣言します。
4. Tercel::Delaunay3d::getDelaunayTriangles() 関数を呼びます。

このとき、getDelaunayTriangles() の第一引数に頂点セットの『参照』を、第2引数には三角形セットの『ポインタ』を渡します。

例によって、三角形（Tercel::Triangle）は、頂点オブジェクトのポインタを保持していますので、頂点セットから要素を削除した場合（あるいはメモリ上の位置が変わるような事が起きた場合）には、三角形の頂点は不正なポインタになってしまいます。

ご注意ください。

続： C++ で Delaunay 分割

昨日、C++ で Delaunay 分割を実装しました。

で。昨日はデータ構造に線形リスト（std::list）のみを用いており、コーディングしやすい代わりにあまり効率的とはいえない実装になっていました。

今回は、リストの代わりにセット（std::set）を用いる事で、内部処理の効率化を図りました。セットの実体は二分探索木（おそらくは赤黒木）であり、『重複する要素を持たない』『要素の探索が対数時間』というなかなかおいしいデータ構造のため、昨日の段階でネックになっていた冗長な重複判定処理がかなり省かれています。

ではなぜ最初からそれを使わなかったかというと、ずばり std::set の使い方をよく知らなかったからです。……恥ずかしい。

前述の通り、セットの内部構造は二分探索木ですので、セットに格納する要素同士の大小関係を判定できなくてはなりません。単純に比較できない『頂点』や『三角形』の大小関係をどう定義するかで悩みましたが、結局辞書式順序で順序づける事にしました（Tercel::Vector や Tercel::Triangle 構造体の operator< が、比較関数として機能します）。

ソースコードは以下。

C++ で Delaunay 分割（ただし2次元）

ちょっと学業の方が忙しくなってしまい、ウェブログを放置していました……。

忘れていたわけじゃないんだよ。ただちょっとモチベーションが足りなかっただけ。

今日は、某所（CG 系の研究室）で需要がありそうだったので、以前 Processing で書いていた Delaunay 分割を C++ で実装し直してみる事にしました。

ただし、C++ はものすごく苦手なので、ちょっと残念なソースになってしまっています。 ⇒ 11月20日追記：もうちょっと内部実装がマシになりました。

ソースコード上部の「view plain」という文字をクリックするとコピペ用の窓が出ますので、使いたい方はご自由にどうぞ。

Processing : P3D モードのヘンなクセ

現行バージョンの Processing には、ソフトウェアレンダリングで 3D を描画できる『P3D モード』が備わっています。

これは、3次元的な情報を視覚化する際にたいへん便利なのですが、実はちょっとした癖もあるため、うまく使うにはそれなりのコツが必要となってきます。

というわけで今日は、P3D モードで遭遇しがちな不具合と、その回避策を紹介したいと思います。

---

【地面のグリッド表示がおかしくなる現象】

以下のように、地面をグリッドで描画したい場合があったとしましょう。

素直にコードを書くとこんな感じになります（展開してご覧ください）。

void setup() {
  size(800, 600, P3D);
}

void draw() {
  // カメラを適当に設定
  camera(0, -100, 500, 0, 0, 0, 0, 1, 0);
  
  background(255);

  /* ====================== */
  /* 地面の描画（てきとう） */
  /* ====================== */
  stroke(100);
  noFill();  // ←塗りつぶさない
  
  final int step = 20;  
  for(int i = -width; i < width; i += step) {
    beginShape(QUAD_STRIP);
    for(int j = -width; j <= width; j += step) {
      vertex(i, 0, j);
      vertex(i + step, 0, j);
    }
    endShape();
  }
}

上記のプログラムは、いっけん正しく動きそうですが、いざ実行してみるとこんなふうにぶっ飛んだ結果になってしまいます。

なぜこんな事になったのでしょうか。