WikipediaのCatmull-Clark、間違ってない?
ハマったのでメモ。
以前実装した細分割曲面(subdivision-surface)は制御メッシュが三角形メッシュに限定されていた。任意の多角形メッシュに拡張したかったので、Catmull-Clarkのアルゴリズムを実装することにした。
Googleで検索すると次のWikipediaのページがヒットした。
http://en.wikipedia.org/wiki/Catmull-Clark_subdivision_surface
このロジックにしたがって実装したのだけど、どうもおかしい。滑らかな曲面に収束しないのだ。アルゴリズムを意訳するとこんな感じ。
- face point = 面の全頂点の平均値(重心の位置)
- edge point = 隣接するface pointとエッジ両端点の平均値
- original point を P、P に隣接するn個のface pointの平均値を F、P に隣接するn個のedge pointの平均値を E と置く。各priginal pointを次の点に移動する。
Wikipediaのページをよく見ると、末尾に次のページが参考として挙げられていた。
http://symbolcraft.com/graphics/subdivision/
こちらのアルゴリズムは正しいようだ。意訳するとこんな感じ。
- face point = 面の全頂点の平均値(重心の位置)
- edge point = 隣接するface pointとエッジ両端点の平均値
- 元の頂点を次式にしたがって再配置する。
ただし
- Qは頂点周りのface pointの平均値
- Rは頂点周りのエッジの中点の平均値
- Sは元の頂点
- nは元の頂点に接続するエッジの本数
1. face point と 2. edge point までは同じ。3の元の頂点の移動方法が違っている。
誰か英語が得意な人、Wikipediaを直してくださいヨ。
ちなみに、最後の頂点移動のロジックは次のように書き換えられる。こちらのほうがちょっとだけシンプルだと思うのだけどどうだろうか。
元の頂点を次式にしたがって再配置する。
ただし
- Qは頂点周りのface pointの平均値
- Rは頂点に隣接する頂点(隣接エッジの反対側の端点)の平均値
- Sは元の頂点
- nは元の頂点に接続するエッジの本数