STL の格子上の位置の検出

2022年9月25日

はじめに

STL で表された形状について、格子上の位置を検出する方法を考える。

位置の検出方法

3次元空間を格子状に区切って、その中のセル (点の間の空間) に STL の形状があるかどうかを判別したい。ちゃんとやろうと考えると、セルと STL の facet (三角形) が交差しているか調べることになるが、めんどくさい。そこで、適当に三角形の上に点を生成して、セルがその点を含んでいるかどうかといういい加減な方法で形状を検出することにする。

点の生成

三角形上の点の座標を次式で表現する。

v = x1*v1 + x2*v2 + x3*v3

v1, v2, v3 は三角形の点 (vertex) の座標、x1, x2, x3 はパラメータである。x1, x2, x3 を動かして、v1-v2 線に平行な線の上に点を次々と生成していく。

x1, x2, x3 は局所座標などと呼ばれる。それぞれの成分は独立しておらず、制約がある。x1 の初期値は x1 = 1 - x3 であり、x2 は x2 = 1 - x1 - x3 で決まる。

{点の間隔を格子幅の最小値とする}
delta = min(dx, dy, dz)

foreach facet
  v1, v2, v3: vertex
  l1 = |v2 - v1|, l2 = |v3 - v2|, l3 = |v3 - v1|
  lmax = max(l1, l2, l3)

  {局所座標の分割数と分割幅}
  n = ceil(lmax/delta)
  d = 1/n
  
  x3 = 0
  for i = 0 to n do
    x1 = 1 - x3
    x2 = 0
    for j = 0 to n - i do
      v = x1*v1 + x2*v2 + x3*v3
      点を生成
      x1 = x1 - d
      x2 = 1 - x1 - x3
    end do
    x3 = x3 + d
  end do

三角形が 2 つの場合は次のようになる (ParaView で可視化)。

以下は Teapot の例である。

セルの検出

点ができれば、あとは点を含むセルを探せばよい。いわゆる構造格子 (structured grid) において、ある点を含むセルを見つけるのは簡単である。以下のようにすればよい。

i = floor((px - x0)/dx)
j = floor((py - y0)/dy)
k = floor((pz - z0)/dz)

(x0, y0, z0) は領域の端っこの座標、(px, py, pz) は点の座標、(i, j, k) はセルのインデックスである。

Teapot の例を以下に示す。形状が検出されたセルの半分だけ表示している。

非構造格子の場合は少し面倒である。非構造格子のセル情報を別の構造格子に入れてしまって候補を絞るとか、あるセルからお隣さんを辿っていくとか、工夫が必要であろう。

参考

• Utah teapot (Wikipedia)