幾何データと演算

MoNo.Geometries.dll に定義されているデータ型や関数について説明します。

Overview

MoNo.Geometries.dll に定義されているものは基本的には以下のものになります。

  • 折れ線
  • 点群
  • ポリゴン
  • 上記の関連するデータ型

曲線や曲面といった高度な幾何形状データは定義されていません。

これらの多くのデータ型が、ジェネリック引数として頂点型を指定できます。 指定できる頂点型は MoNo.IPoint3d インターフェイスを実装している必要があります。 MoNo.IPoint3d インターフェイス及びそれを実装するデータ型については IPoint3d と IBoundary3d を参照してください。

また、これらの型は基本的にイミュータブル(immutable; 不変)に設計されています。 例えば折れ線やメッシュといったオブジェクトは、構築された後に値が変更される(例えば座標値が書き換えられる)ことはありません。 これは関数型プログラミングの思想に則った設計方針です。 これにより幾何データの不変性が保証されるため、様々な処理をシンプルに保つことができます。

ポリゴンを表すデータ型にはいくつかの種類があります。

  • Soup<’a>, Tris3d, Tris3f
    ジェネリック引数 ‘a には要素のデータ型(基本的には三角形)を指定します。 面と面の隣接情報は一切持たず、単に複数の面データを配列で保持するだけのデータ型です。
  • Mesh<’TVertex>, Mesh3d, MeshNormal3d, …
    ジェネリック引数 'TVertex には頂点型を指定します。 頂点の配列と、頂点をインデックスで参照する Facet の配列を保持します。 互いに隣接する2つの面(Facet)は、共有するエッジで同じ頂点番号を参照します。
  • CG.MeshObj
    CG のためのメッシュデータ型です。 純粋な幾何形状を保持するだけではなく、マテリアル情報やテクスチャ情報も保持します。
  • Shell<’a>
    ハーフエッジ構造による位相情報を持ったメッシュデータです。

Types

主要な型の一覧です。

Type Description
Segment<’a> 線分
Triangle<’a> 三角形
Triangle2d 2次元の三角形
Triangle3d = Triangle<Point3d>
Triangle3f = Triangle<Point3f>
TriangleNormal3d = Triangle<PointNormal3d>
IPolyline<’TPoint> 折れ線インターフェイス
Polyline<’TPoint> 折れ線
Polyline3d = Polyline<Point3d>
Polyline3f = Polyline<Point3f>
PolylineNormal3d = Polyline<PointNormal3d>
PolylineNormal3f = Polyline<PointNormal3f>
Cloud<’TPoint> 点群
Cloud3d = Cloud<Point3d>
Cloud3f = Cloud<Point3f>
CloudNormal3d = Cloud<PointNormal3d>
CloudNormal3f = Cloud<PointNormal3f>
Soup<’a> ポリゴンスープ
Tris3d = Soup<Triangle3d>
Tris3f = Soup<Triangle3f>
IMesh<’TVertex> メッシュインターフェイス
Mesh<’TVertex> メッシュ
IMesh3d = IMesh<Point3d>
IMesh3f = IMesh<Point3f>
IMeshNormal3d = IMesh<PointNormal3d>
IMeshNormal3f = IMesh<PointNormal3f>
Mesh3d = Mesh<Point3d>
Mesh3f = Mesh<Point3f>
MeshNormal3d = Mesh<PointNormal3d>
MeshNormal3f = Mesh<PointNormal3f>
CG.MeshObj CG 用のメッシュ(マテリアル、テクスチャ付き)
Shell<’a> ハーフエッジ構造によるメッシュ
Halfedge<’a> Shell のハーフエッジ
HalfedgeFace<’a> Shell の面
HalfedgeVertex<’a> Shell の頂点

一点、注意事項があります。 例えば Triangle3dTris3d などは F# の型略称(Type Abbreviation)を使って次のように定義されています。

型略称による定義
type Triangle3d = Triangle<Point3d>
type Tris3d = Soup<Triangle3d>

しかし型略称は F# 固有の機能であるため、C# からはこれらの定義が認識されません。 従って C# から Tris3d を使うときは Soup<Triangle<Point3d>> のように略称を使わずに記述する必要があります。 あるいはソースファイルの先頭で次のように using 宣言をする必要があります。

using 宣言(C# から使う場合)
using Tris3d = Soup<Triangle<Point3d>>

ポリゴンデータの変換

ポリゴンデータの変換関数の一覧を下記に示します。

function from to
STLFormat.readTris3d STL file Tris3d
STLFormat.writeTris3d Tris3d STL file
OBJFormat.read OBJ file CG.MeshObj
OBJFormat.write CG.MeshObj OBJ file
Mesh.toTris3d Mesh<’a> Tris3d
Mesh.ofTris3d Tris3d Mesh3d
Mesh.toMesh3d Mesh<’a> Mesh3d
Mesh.toSmooth Mesh<’a> MeshNormal3d
CG.MeshObj.toMesh3d CG.MeshObj Mesh3d
CG.MeshObj.ofMesh3d Mesh3d CG.MeshObj
CG.MeshObj.ofMeshNormal3d MeshNormal3d CG.MeshObj
CG.MeshObj.toSmooth CG.MeshObj CG.MeshObj
Shell.convertShellToMesh Shell<’a> Mesh<’a>
Shell.fromMesh Mesh<’a> Shell<’a>
digraph conversion {
graph[
   compound = true
]

node [
   shape = box
];

subgraph cluster_Mesh {
   Mesh [label="Mesh<'a>"];
   Mesh -> MeshNormal3d [label = "Mesh.toSmooth"];
   Mesh -> Mesh3d [label = "Mesh.toMesh3d"]
};

STL [label="STL file", shape=octagon]
OBJ [label="OBJ file", shape=octagon]

CGMeshObj [label = "CG.MeshObj"]
Shell [label = "Shell<'a>"]

STL -> Tris3d [label="STLFormat.readTris3d"]
Tris3d -> STL [label="STLFormat.writeTris3d"]
OBJ -> CGMeshObj [label="OBJFormat.read"]
CGMeshObj -> OBJ [label="OBJFormat.write"]

Mesh -> Tris3d [label = "Mesh.toTris3d"]
Tris3d -> Mesh3d [label = "Mesh.ofTris3d"]
CGMeshObj -> Mesh3d [label = "CG.MeshObj.toMesh3d"]
CGMeshObj -> CGMeshObj [label = "CG.MeshObj.toSmooth"]
Mesh3d -> CGMeshObj [label = "CG.MeshObj.ofMesh3d"]
MeshNormal3d -> CGMeshObj [label = "CG.MeshObj.ofMeshNormal3d"]
Mesh -> Shell [label = "Shell.fromMesh", lhead="cluster_Mesh"]
Shell -> Mesh [label = "Shell.convertShellToMesh", ltail="cluster_Mesh"]
}

線分と折れ線

線分を表す Segment 構造体が次のように定義されています。

Segment<’a> 構造体
Member 説明
P1 始点
P2 終点
Vector 始点から終点へ向かうベクトル
Length 線分の長さ
LengthSquared 線分の長さの自乗
ToSegment3d () MoNo.Segment3d 型へ変換
ToLine3d () MoNo.Line3d 型へ変換

MoNo.dll に定義されている MoNo.Segment3d とよく似ていますが、頂点型をジェネリック引数として指定できるところが異なります。

折れ線を表す IPolyline インターフェイスが次のように定義されています。

IPolyline インターフェイス
type IPolyline<'TPoint when 'TPoint :> IPoint3d and 'TPoint : equality> =
  inherit IBoundary3d
  abstract IsLoop : bool
  abstract Points : Immutarray<'TPoint>
  abstract Segments : IReadOnlyList<Segment<'TPoint>>

このインターフェイスを実装した Polyline クラスが定義されています。

Polyline クラス
type Polyline<'TPoint when 'TPoint :> IPoint3d and 'TPoint : equality>( isLoop : bool, points : 'TPoint Immutarray ) =
  ...
  interface IPolyline<'TPoint> with
    ...

IsLoop プロパティが true のときは折れ線ループを表し、頂点列の末尾の頂点と先頭の頂点を結んだ線分が追加されます。従って、頂点数と線分数の間には次の関係が成り立ちます。

  • IsLoop == false のとき: Segments.Count == Points.Length - 1
  • IsLoop == true のとき: Segments.Count == Points.Length

Polyline を操作する関数群が Polyline モジュールにまとめられています。

Polyline モジュール
name type description
empty<’a> Polyline<’a> 空の折れ線
map (‘a -> ‘b) -> IPolyline<_> -> Polyline<’b> 折れ線の頂点をマッピング
globalize CodSys3d -> IPolyline<_> -> Polyline3d グローバル座標系に座標変換
localize CodSys3d -> IPolyline<_> -> Polyline3d ローカル座標系に座標変換
globalize3d CodSys3d -> IPolyline<Point3d> -> Polyline3d グローバル座標系に座標変換
globalize3f CodSys3d -> IPolyline<Point3f> -> Polyline3f グローバル座標系に座標変換
localize3d CodSys3d -> IPolyline<Point3d> -> Polyline3d ローカル座標系に座標変換
localize3f CodSys3d -> IPolyline<Point3f> -> Polyline3f ローカル座標系に座標変換
length IPolyline<_> -> float 折れ線の長さ
ofArray bool -> ‘a[] -> Polyline<’a> 頂点配列から折れ線を構築
ofImmutarray bool -> isLoop Immutarray<’a’> -> Polyline<’a> 頂点配列から折れ線を構築
toPolyline3d IPolyline<_> -> Polyline3d Polyline3d に変換
rev IPolyline<’a> -> Polyline<’a> 向きを反転
concat bool -> seq<IPolyline<’a’>> -> Polyline<’a> 複数の折れ線を連結
append bool -> IPolyline<’a> -> IPolyline<’a> -> Polyline<’a> 2つの折れ線を連結

メッシュ

型定義

メッシュに関連する型定義を要約したコードを下記に示します。

Edge 構造体
type Edge = struct
  new( vtx1 : int, vtx2 : int ) = ...
  member this.Vertex1 = ...
  member this.Vertex2 = ...
end
Facet 構造体
type Facet( vtx1 : int, vtx2 : int, vtx3 : int ) = struct
  member this.Vertex1 = vtx1
  member this.Vertex2 = vtx2
  member this.Vertex3 = vtx3
  member this.Edge1 = Edge( vtx1, vtx2 )
  member this.Edge2 = Edge( vtx2, vtx3 )
  member this.Edge3 = Edge( vtx3, vtx1 )
  member this.Vertices  = [| vtx1; vtx2; vtx3 |]
  member this.Edges     = [| this.Edge1; this.Edge2; this.Edge3 |]
  ...
end
IMesh インターフェイスと Mesh クラス
type IMesh<'TVertex when 'TVertex :> IPoint3d and 'TVertex : equality> =
  inherit IBoundary3d
  abstract Vertices : Immutarray<'TVertex>
  abstract Facets   : Immutarray<Facet>

type Mesh<'TVertex when 'TVertex :> IPoint3d and 'TVertex : equality>
  (vertices : 'TVertex Immutarray, facets : Facet Immutarray) =
  ...
  interface IMesh<'TVertex> with
     ...

Edge 構造体は、2つの頂点番号を結ぶエッジを表現します。 重要な注意点として、Edge 構造体はエッジの向きを表現しません。 Edge 構造体のコンストラクタは、引数に指定された2つの頂点番号の並び順にかかわらず、かならず Vertex1 < Vertex2 となるように初期化します。

Facet 構造体は、3つの頂点番号を結ぶ三角面を表現します。 Edge 構造体と違い Facet 構造体はコンストラクタで指定された頂点の並び順をそのまま保持します。これにより面の向き(反時計回りに並ぶ向きをオモテ面、その逆を裏面)を表現します。

メッシュ(IMesh インターフェイスおよび Mesh クラス)は頂点列とファセット列から構成されます。ファセット列は頂点列のインデックスを頂点番号として参照します。ファセットが頂点列の長さを超えるインデックスを参照するとバグ(例外)の原因となります。

Mesh モジュール

メッシュを操作する関数群が Mesh モジュールにまとめられています。

Mesh モジュール
name type description
vertices IMesh<’a> -> Immutarray<’a> メッシュの頂点列を取得
facets IMesh<’a> -> Immutarray<Facet> メッシュのファセット列を取得
empty<’a> Mesh<’a> 空のメッシュ
getTriangle int -> IMesh<’a> -> Triangle<’a> 指定ファセット番号の三角形を取得
getTriangle3d int -> IMesh<’a> -> Triangle3d 指定ファセット番号の三角形を取得
map (‘a -> ‘b) -> IMesh<’a> -> Mesh<’b> 頂点をマッピング
mapi (int -> ‘a -> ‘b) -> IMesh<’a> -> Mesh<’b> 頂点をマッピング
toMesh3d IMesh<’a> -> Mesh3d Mesh3d に変換
toMesh3f IMesh<’a> -> Mesh3f Mesh3f に変換
globalize CodSys3d -> IMesh<’a> -> Mesh3d グローバル座標系に座標変換
localize CodSys3d -> IMesh<’a> -> Mesh3d ローカル座標系に座標変換
filterByVertex (‘a -> bool) -> IMesh<’a> -> Mesh<’a> 述語関数をパスする頂点のみからなるメッシュに変換
filterByFacet (Facet -> bool) IMesh<’a> -> Mesh<’a> 述語関数をパスするファセットのみからなるメッシュに変換
toTris3d IMesh<’a> -> Tris3d Tris3d に変換
ofTris3dProgressive Tris3d -> Progress<Mesh3d> Tris3d からメッシュを構築。 三角形間で座標値が厳密に一致する頂点が共有されるように構築される。
ofTris3d Tris3d -> Mesh3d 同上
calcSmoothNormalVectors IMesh<’a’> -> Vector3d[] 頂点ごとに周りの三角形から法線ベクトルを算出
toSmooth IMesh<’a> -> MeshNormal3d 頂点ごとに法線ベクトルを付けて smooth shading されるメッシュを構築
merge (int -> int option) -> IMesh<’a> -> IMesh<’a> -> Mesh<’a> 2つのメッシュをマージ。第1引数 vtxMergeMap には、2つ目のメッシュの頂点番号からマージ先の1つ目のメッシュの頂点番号(マージしない場合はNone)を得る関数を指定する。
append IMesh<’a> -> IMesh<’a> -> Mesh<’a> 2つのメッシュを連結する
concat Mesh<’a>[] -> Mesh<’a> 複数のメッシュを連結する

位相的な計算

メッシュの位相的な計算処理(ファセットの隣接関係に関する処理)を実行するにあたって頂点配列は必要なく、ファセット列のみから計算できます。そういった計算処理が Facets モジュールにまとめられています。

位相の計算では、次の FacetEdge 構造体が大きな役割を果たします。

FacetEdge 構造体
type FacetEdge private( data : int ) = struct
  new( facet : int, index : int ) = FacetEdge( (facet <<< 2) ||| (index &&& 0b11) )
  member this.Data = data
  member this.Facet = data >>> 2
  member this.Index = data &&& 0b11
  member this.Next = FacetEdge( this.Facet, (this.Index + 1) % 3 )
  member this.Prev = FacetEdge( this.Facet, (this.Index + 2) % 3 )
  static member Null = FacetEdge( -1 )
end

FacetEdge 構造体はファセット番号(facet)と index \(\in \{0, 1, 2\}\) のペアで構成され、facet 番目のファセットの index 番目のエッジを表します。 (内部表現は int 変数(32bit)の上位30bitに facet、下位2ビットに index を格納する実装となっています)

1本のエッジを共有して隣接する2枚のファセットでは、そのエッジ上で2つの FacetEdge がペアになっていると考えられます。そういう意味で FacetEdge はハーフエッジとやや近い概念です。(ただしハーフエッジと違って、FacetEdge 自体は隣接する FacetEdge へのリンクを持ちません)

Facets モジュールには、FacetEdge の隣接 FacetEdge を取得する関数の型略称が次のように定義されています。

隣接 FacetEdge の取得関数の型略称
module Facets
...
type EdgePairing = FacetEdge -> FacetEdge option

以上を踏まえ、Facets モジュールには下記の関数群が用意されています。

Facets モジュール
name type description
collectVertices seq<Facet> -> seq<int> ファセット列に含まれる頂点列を重複なく集めます
collectFacetEdges facetCount:int -> seq<FacetEdge> facetCount 個のファセットの FacetEdge をすべて集めます
reconstructFacets Immutarray<Facet> -> Facet[] * int[] ファセット列から、参照されていない頂点番号を廃した無駄のないファセット列(と頂点列)を再構築します。
generateEdgePairing Immutarray<Facet> -> EdgePairing ファセット列から隣接関係を構築します
aroundVertexToRight EdgePairing -> head:FacetEdge -> seq<FacetEdge> head から頂点周りに時計回りに FacetEdge を辿ります
collectBoundaryLoopEdges EdgePairing -> head:FacetEdge -> list<FacetEdge> 先頭の境界エッジ head を起点として反時計回りに境界ループを辿り、FacetEdge を集めます
collectConnectingFacets EdgePairing -> fid:int -> seq<int> ファセット fid に連結な(=隣接関係で辿ることができる)ファセットをすべて集めます
extractBoundaryLoops Immutarray<Facet> -> seq<FacetEdge[]> 境界ループをすべて集めます