はじめに
nortikinさんよりノードツリーを紹介してもらった。その中で使われていたノードで使ったこと無いものがあったので調べた。
Sverchok.0.6.0.0 | Blender.2.82(sub7) | NodeTree | 2020.05.29 | 13:46 · GitHub
参照元
Intersect Edges
機能
このノードは入力された辺の交差を見つけます、そして交差に基づいたメッシュを返します。
このノードは辺を見つけるためのいくつかのアルゴリズムが含まれています。
初期アルゴリズム
コードは、Blender Contrib ディストリビューションの一部である TinyCAD プラグインの XALL 演算子をそのまま使用しています。
Sweep line algorithm
このアルゴリズムはsweep lineアプローチに基づいています。
これは多数の辺を扱えますが、交差が大量にある場合は処理が劇的に重くなります。例えば、もしそれぞれの辺が他の全てに交差している場合など。そのような場合はいくつかの辺のみが扱われます。
- このアルゴリズムは二重点を生成しません
- 堅牢性があまりなくエラーを吐きます
- このアルゴリズムではNパネルにあるエプシロンパラメータがより重要になります。もしエラーが出てる場合はこのパラメータを変更して修復してみてください。
アルゴリズム間の違いは端の扱いで見ることが出来ます。
10個の四角が微妙に回転して交差している場合。
2Dが意味するのはノードに入力されるメッシュがフラットである事を期待する事を意味します。しかしそれはXY平面のみを意味するわけではありません。メッシュはXY平面の上下または相対的に傾いていても問題ありません。
このアルゴリズムの新しい交差を見つける方法は下記のようになります:
２つの辺を取り、Z座標を削除しそこから交差を見つけます。しかし交差が見つかった後、与えられた辺上に交差ポイントを投影します。この意味は入力されるメッシュはフラットでなければなりませんが、どこに配置されていても良いことを意味します。
Z軸に沿ったフラットなメッシュだけはエラーを吐き出します。
Blender mode – for 2D mode only
このモードはBlender内部にあるmathutilsモジュールの関数を使います。これは多数の交差(1000位)がある場合でもかなり早いですが、かなり安定感は無いです、そしてBlenderを簡単にクラッシュさせます。そしてまた一つの辺がその他の辺の多数または全てに交差しているようなケースは想定していません。気をつけて使ってください。Blender 2.81以上で使えます
2Dアルゴリズムのベンチマーク
時間での分類
| 交差数 | Alg 1 | Sweep line | Blender |
|---|---|---|---|
| 100 | 0.05 | 0.15 | 0.009 |
| 1000 | 1.43 | 2.20 | 0.12 |
| 10000 | 150 | 27 | 8.2 |
| 20000 | too long | 65 | 48 |
| 30000 | too long | 97 | 150 |
入力
頂点と辺のみ。注意: 面とベクトル化(ネストされたリスト)された入力はサポートしていません。
Note: sweep algorithm はベクトル化
Nパネルのパラメータ
- Epsilon 浮動小数点数の比較に使用します。性能には影響しません。
出力
頂点と辺。メッシュは、高速な交点ルックアップに使用されるハッシングアルゴリズムにより、古い頂点やエッジインデックスの順序を保持しません。
例
- 左は入力、右は結果
- Mesh joinによってそもそも交差部分に頂点が作られている
- 上記の例においてSweep line のみ頂点のindexを変更したため記録しておく
