B-reps（境界表現）をC、C++で実装するには？

質問

OpenGLで境界表現によってソリッドモデルを表現したいのですが、うまくできません。
ウィングドエッジデータ構造やHalf-Edgeデータ構造などのデータ構造を用いることによって表現する方法があるようなのですが、どのように実装したらよいでしょうか？

回答No.1

noocyte · ベストアンサー

> OpenGLで境界表現によってソリッドモデルを表現したいのですが、うまくできません。

そりゃそうです．OpenGL が扱う幾何モデルは，
バラバラの頂点や多角形の集まりに過ぎません．

OpenGL とソリッドモデルはほとんど無関係で，
モデルを表示するときに OpenGL を使うというだけのことです．
実際，OpenGL にはソリッドモデルを扱うためのデータ構造も関数もありません．

OpenGL が行うことは，ぶっちゃけて言えば，３次元空間内の
多角形を座標変換して２次元平面に描画することだけです．
したがって OpenGL にとっては，複数の多角形の間の関係など
どうでもよくて，表示すべきすべての多角形を片っ端から
描画していけばいいわけです．

他方，境界表現では，頂点，稜線，面などの位相構造
(隣接関係，順序，向きなど) を管理する必要があります．
これらは OpenGL とは全く無関係なものです．

> どのように実装したらよいでしょうか

一例を挙げると，頂点，稜線，面をそれぞれオブジェクトとして，

・頂点は，それに接続する稜線と面へのポインタを，(立体の外側から見て左回りに)
　稜線 → 面 → 稜線 → 面 → … とつないだ双方向リストを持つ．

・面は，それを構成する頂点と稜線へのポインタを，(立体の外側から見て左回りに)
　頂点 → 稜線 → 頂点 → 稜線 → … とつないだ双方向リストを持つ．

・稜線は次のデータを持つ．
　・両端に接続する頂点Ａ，Ｂへのポインタ．
　・立体の外側から見て，Ａ→Ｂ方向に対して右側にある面へのポインタ．
　・立体の外側から見て，Ｂ→Ａ方向に対して右側にある面へのポインタ．

CGによる画像生成の流れ (同志社大学 知識情報処理研究室)
http://indy.doshisha.ac.jp/~watabe/cg/99/polygon/index.htm

情報組織論III Advanced Computer Graphics
http://graphics.c.u-tokyo.ac.jp/lectures/io3/notes/io3-01.pdf
→ Half-Edge データ構造 (p.5)

産業情報システム (東大 生産システム工学研究室)
http://www.msel.t.u-tokyo.ac.jp/class/IMI/PDF/IMI020425.pdf
→ 境界表現によるソリッドモデル (p.21～)

厳密に正確な演算を用いたソリッドモデリングに関する研究
http://dspace.wul.waseda.ac.jp/dspace/bitstream/2065/531/1/Honbun-3794.pdf

「"境界表現" 面 稜線 頂点」で検索
http://www.google.co.jp/search?q=%22%E5%A2%83%E7%95%8C%E8%A1%A8%E7%8F%BE%22+%E9%9D%A2+%E7%A8%9C%E7%B7%9A+%E9%A0%82%E7%82%B9&sourceid=navclient-ff&ie=UTF-8&rls=GGGL,GGGL:2006-34,GGGL:ja

お礼

ありがとうございます。

補足

たびたび申し訳ありません。

>頂点は，それに接続する稜線と面へのポインタを，(立体の外側から見て左回りに)
　稜線 → 面 → 稜線 → 面 → … とつないだ双方向リストを持つ．

・面は，それを構成する頂点と稜線へのポインタを，(立体の外側から見て左回りに)
　頂点 → 稜線 → 頂点 → 稜線 → … とつないだ双方向リストを持つ．

・稜線は次のデータを持つ．
　・両端に接続する頂点Ａ，Ｂへのポインタ．
　・立体の外側から見て，Ａ→Ｂ方向に対して右側にある面へのポインタ．
　・立体の外側から見て，Ｂ→Ａ方向に対して右側にある面へのポインタ．

これを実際に簡単な立体(立方体やリブなど)に対して実装するとどのようなプログラムになるのでしょうか？

回答No.2

noocyte

> これを実際に簡単な立体(立方体やリブなど)に対して
> 実装するとどのようなプログラムになるのでしょうか？

作ったことはないけど，基本的なデータ構造は↓こんな感じかな．

typedef struct Vertex Vertex_t; // 頂点
typedef struct Edge Edge_t; // 稜線
typedef struct Face Face_t; // 面

// Vertex_t，Edge_t，Face_t へのポインタの双方向リストの要素
typedef struct VEFListElement VEFListElement_t;

struct VEFListElement {
　// 双方向リストを構成するポインタ
　VEFListElement_t *next; // 次の要素
　VEFListElement_t *previous; // 直前の要素

　union {
　　Vertex_t *vertex;
　　Edge_t *edge;
　　Face_t *face;
　};
};

// Vertex_t，Edge_t，Face_t へのポインタの双方向リスト
typedef struct {
　VEFListElement_t *first; // 先頭要素を指す．
　VEFListElement_t *last; // 末尾要素を指す．
} VEFList_t;

struct Vertex {
　// 幾何データ
　double x, y, z; // 座標

　// 位相構造：この頂点に接続する稜線と面へのポインタの双方向リスト
　// (立体の外側から見て左回り順，稜線と面を交互に)
　VEFList_t edgesAndFaces;
};

struct Edge {
　// 位相構造

　Vertex_t *vertex[2]; // この辺の両端点

　// face[0]：立体の外側から見て，vertex[0] → vertex[1]
　//　　　　　方向に対して右側にある面へのポインタ．
　// face[1]：立体の外側から見て，vertex[1] → vertex[0]
　//　　　　　方向に対して右側にある面へのポインタ．
　Face_t *face[2];
};

struct Face {
　// 位相構造：この面を構成する頂点と稜線へのポインタの双方向リスト
　// (立体の外側から見て左回り順，頂点と稜線を交互に)
　VEFList_t verticesAndEdges;
};

このデータ構造に対してどういう操作をすればいいかは，
#1 で挙げた３番目の URL の「オイラー操作」を参考にしてください．
実装方法がわからなければ，双方向リストの勉強も必要．

上記データ構造以外に，１つの立体を構成する頂点，稜線，面をひとまとめに
するコンテナが必要．特に，同時に複数の立体を扱う場合は必須．

複雑な立体であっても，単連結な立体ならば基本的にこれでできると思う．
逆に穴が明いてたりすると，追加の情報が必要になるかも．

また，頂点数などが膨大な場合には，幾何学的処理 (最も近い頂点を
検索する，指定された領域内の頂点を列挙するなど) を効率良く行う
ために多次元木などのデータ構造も必要になる．
(その場合，計算幾何学も勉強してください．)

お礼

とても参考になりました。ありがとうございます。
実装するには足りない知識が多いようなのでまずは、その部分の勉強をしていきたいと思います。
ありがとうございました！