SphereTree

用あって スフィアツリー の構築方法について調べています。

スフィアツリーにまつわるアルゴリズムのまとめとソースコードは、Sphere-Tree Construction Toolkit　で公開されているようですが、何をやっているのかいまいち理解できません。

ソースが丸々公開されているので、二次利用することは可能っちゃ可能なのですが、もうちょっと中身を理解したいんですよね

Sphere-Tree Toolkit のページを流し読みしてみると、ツリーの構築が何段階かに分かれているのかと考えています。

OctTree のように、トップダウンでツリーを構築していくのか、ツリーの葉となるスフィアを求めてから、マージ(Marge)したり、バースト(Brust)したり、拡張したり(Expand)、結合したり(Combined)という感じなんでしょうか？

でもって、中間軸法(Hubbard のアルゴリズム)のアルゴリズムは、葉となるスフィアを作成して、上の階層に向かって、ツリーを構築していくんでしょうか？

lucille 開発日記によれば、

中間軸(Medial-Axis)法は、オクツリーとは逆に、葉ノードのスフィアから生成していきます。

まずオブジェクトのサーフェス上にランダムな点群を十分な数作成し、その点群から 3D ボロノイ図を作成します。

次に生成されたボロノイ頂点のうち、３次元内外判定により、オブジェクト内部にある頂点のみを抜き出します。この頂点を結ぶと、オブジェクトの中間軸(骨格)ができあがります。

この中間軸の頂点を中心として、スフィアを作成し、重複の大きなスフィア同士をマージしていくことで、スフィアでタイトフィットにオブジェクトを覆うことができます。

ってあるんですけど、ボロノイ頂点ってどうやって作成すりゃ良いんでしょ？
サーフェース上に作成された点群から、ボロノイ領域を作ってあげて、ボロノイ領域の交点になる点を求めれば良いんですかね？

...しかし、スフィアツリーに関する(日本語の)情報って、何でこんなに少ないんだろう...
OctTree を用いて、ツリーを構築するのは簡単なんですけど、ちょっとルーズすぎるので、もっとタイトフィットさせたいんですが...

ま、日本語で読める技術情報自体が少ないってことなんですかね
ほんと、英語が苦も無く読める人がうらやましいですよ