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」という文字をクリックするとコピペ用の窓が出ますので、使いたい方はご自由にどうぞ。

いまさら DirectX10（なんちゃってオブジェクト指向篇）

昨日のソースコードが、あまりにもアレだったので、せめて DirectX の初期化関連だけでも別クラスに分けようと思いました。

本日はその成果報告です。

成果といっても、今日は簡単のためブルースクリーンを表示するだけ。昨日よりひどい。

さて。

オブジェクト指向というからには、本来ならウィンドウもクラスにすべきところですが、OS からコールバックされる関数（ウィンドウプロシージャ）をメンバ関数にするにはちょっとしたトリックを仕込まねばなりません。

※ C++ において、非 static なメンバ関数は、暗黙のうちに自クラスへのポインタを引数として受け渡す性質があるので、コールバック関数をそのままクラスのメンバにしようとすると、『引数の数が合わないよ！』と叱られちゃうのです。

原因が判れば回避策を講じるのもそう面倒ではないのですが（たとえば追加のメッセージ処理関数を独自にフックさせるとか、あるいは思い切ってウィンドウプロシージャだけ static なメンバ関数にしちゃうとか）、それだけに極端な『オレ流ソース』になりやすく、あんまりよろしくないなぁと思ったので、ウィンドウに関してはそのまま放置にしました。

いまさら DirectX10（はじめの一歩篇）

※ このブログはただのお勉強日記だよ！ 参考になるような解説記事は一切ないよ！

今は昔。

ぼくもネイティブな 3D プログラミングなるものに憧れ、当時主流だった DirectX9 をつまみ喰いした事がありました。

当時、DirectX9 をあれこれ試したときに作ったプログラミングノート

あれから時代は移ろい、いつの間にか最新のトレンドも DirectX11 に代わってしまったようです。

そんなわけで、そろそろ最新の API を学び直す時期かなぁと思い立ったわけですが、残念ながらぼくのパソコン（のグラボ）は DirectX11 には対応していないので、仕方なく DirectX10 に手をつけてみる事にしました。

さてさて。

DirectX10 からは固定機能パイプラインが無くなり、プログラマブルシェーダの理解が不可欠となってしまいました。 Vista 時代を迎えてかなり思い切った仕様変更だと思います。

何を隠そう、ぼくはこのシェーダに手を付ける事が怖くて、DirectX9 の頃まではほぼ固定機能パイプラインに頼りっきりだったため、DirectX10 になって開発の敷居ががくんと上がってしまいました。

こうやってどんどん梯子を外されていくうちにゲイツ様への忠誠心が確実に薄らいでいますが、それはさておき。

今回は、おっかなびっくり DirectX10 なるものに触れてみようかと思います。

魔法使いの弟子（その7-1）

【ミッション： Windows プログラミングに挑戦せよ】

中学の頃、ぼくは生まれて初めて C 言語の入門書を買った。

しかしそこに書いてあったのは、退屈なコマンドラインアプリケーションばかり。 GUI アプリケーションの構築を夢見ていたぼくにとって、それはあまりにもショッキングな現実であった。

そんなぼくも、やがて C 言語をひととおり学び（全然身についていないが）、ついに GUI アプリに手を付ける日が来た。

魔法使いの弟子（その6-1）

※ 今日は C++ と Windows プログラミングのお話だよ。

ぼくが C++ 言語で GUI プログラムを作るときには、なるべくユーザインタフェースと中核処理のコードを分離したいなと思っている。その理由は、ライブラリへの依存度をなるべく下げて他の環境への移植性を高める為と、処理そのものの安定性を保証する為である。

たとえば Windows API を積極的に用いて作成したプログラムは、当然ながら Windows 環境で動作させる事が前提となり、移植性は考慮の対象外になりがちだ。また、サードパーティ製ライブラリがプログラム全域に亘ってかっちり食い込んでいると、ライブラリの仕様変更に伴って厖大な修正作業が必要になる事がある（生産性も低下する）。もしかしたら、ライブラリに潜在するバグが処理に何らかの影響を及ぼす事だってあるかも知れない。

だが、本質的な処理をライブラリ非依存で書く事ができれば、当然ながら“本質を損なわずに” C++ の処理系を有する他環境へ移植する事が容易になるだろう。何らかの不具合が生じたときにも、その責任の所在も突き止めやすくなる。

では、これを実現するにはどうすればよいだろうか。

実はそれほど面倒な事ではない。ライブラリが独自に拡張したデータ型と、言語仕様で定義されている型を相互に変換する処理を実装すれば、（ライブラリ非依存の）中核処理の結果を Windows API から利用したり、あるいはその逆を行ったりする事ができるようになる。

Windows API の内部では、typedef を駆使しておびただしい量の型が定義されており、必要に応じてこれらを C++ で用意されている標準的な型に変換する必要がある。今回はその一例として、 Windows で定数文字列を表すためによく用いられる LPCTSTR 型から、 std::string 型への橋渡しを考えてみよう。

場合によっては、 Adapter パターンを適用した本格的なクラス設計が必要になる事もあるが、今回は変換用の関数を作るだけで充分だ。