3章 3次元形状をモデリングする

3章
3次元形状をモデリングする
ここでは，3次元形状(立体)をコンピュータ内に定
義する手法について説明する．
3.1 境界表現



境界表現(boundary representation)
頂点，稜線，面分などの幾何情報およびそれらの接続情報
幾何情報(geometrical data)
3次元空間内の座標値（ｘ，ｙ，ｚ）
接続情報(topological data)
面分はどの稜線で区切られているかの情報
3.1 境界表現



多面体を構成する曲面群と，曲面を構成する稜線群と，
稜線を構成する頂点群との間の接続関係(位相情報)を
表したもの．
境界表現法では多面体を構成する頂点，稜線，曲面の
接続関係をウィングドエッジデータ構造を用いて表現する
ことが多い．
ウィングドエッジデータ構造：多面体の各稜線を中心とし
た形状要素の接続関係を表現する位相データ構造
3.1 境界表現
1．ポリゴン表現

多角形は基本的な形状要素
稜線
稜線
頂点
稜線
頂点
頂点
穴
凸多角形
凹多角形
穴のある多角形
3.1 境界表現
ポリゴンの法線ベクトル
y
ax+by+cz=1
1/b
v2
1
1
i k
a
c
1
1
v2  j  k
b
c
v1 
i
1/c
n
v1
1/a
x
z
単位法線ベクトルnは3次元CGにお
いて，陰影づけなどの処理で重要な
役割を果たす．
j
k
1
1
1
v1  v 2  1 / a 0  1 / c  i  j  k
bc ca ab
0 1/ b 1/ c
v1  v 2 a b c
n
 i  j k
v1  v 2 s s s
s  a2  b2  c2
3.1 境界表現
多角形の三角形分割
Q0
Q1
三角形
多角形
Q2
Q2
多角形
Q3
Q0
Q1
Q4
Q0
Q5
Q8
Q7
Q6
Q1
Q9
Q10
Q3
Q4
Q2
Q5
Q8
Q7
Q6
Q9
Q10
Q3
仮想の稜線
(ブリッジ稜線)
Q4
3.1 境界表現
多角形メッシュによる物体の近似




CGでは，3次元空間に定義された2次曲面や自由曲面は，
複数の小さな多角形(ポリゴン)で近似して表示する．
多角形メッシュでは粗いことがある．その場合は，四角形
メッシュや三角形メッシュを用いる．
四角形メッシュの頂点は同一平面内にない場合がある．
その場合，曲面の最小単位である三角形メッシュを用い
て，物体を近似して表示する．
3.1 境界表現
2．ウィングドエッジデータ構造
NCCW
NCCW
Edge
Nface
NCW
PCW
PVT
Nface
PVT
Edge
Pface
NVT
Pface
PCCW
オイラーの関係式
V－E＋F＝２
PCCW
稜線Edge：頂点PVTと頂点NVTで構成
稜線Edge＝曲面Nfaceと曲面Pfaceの稜線
稜線NCCWと稜線PCWは頂点PVTに接続
稜線NCWと稜線PCCWは頂点NVTに接続
NVT
NCW
PCW
頂点の数
（８）
多面体を構成するすべての稜線に適用し接続関係を記述
稜線の数
（１２）
曲面の数
（６）
3.1 境界表現
(例題)ウィングドエッジデータ構造
PCW
NCCW
PVT
Nface
E
PCW
NCCW PVT
Pface
E
Nface
PCCW
NCW
NCW
NVT
5
⑤
1
②
①
Ⅰ
4
④
6
⑥
Ⅱ
⑦
⑧
Ⅲ
2③ 7
NCCW：③
Nface：Ⅲ
Pface
NVT
PVT：2
⑦
PCCW
PCW：②
Pface：Ⅱ
⑨
3
NCW：⑧
PCCW：⑥
NVT：6
3.2 CSG表現
1．プリミティブ

円柱や直方体などの形状プリミティブ(形状要素)を組み
合わせて物体を生成する方法
f(x，y，z)=0
f ij ( x, y, z )  0
半空間Sij
n
S j   ( f ij ( x, y, z )  0)
i 1
形状プリミティブSj
Sj=∩Sij
3.2 CSG表現
プリミティブ例
z
f1 ( x, y, z )  x 2  y 2  r 2
ｒ
f 2 ( x, y , z )  z  h
f 3 ( x, y , z )   z
ｈ
3
0
x
y
S cyl   ( f i ( x, y, z )  0)
i 1
3.2 CSG表現
2．集合演算
B
A
和（A∪B）
差（A－B）
積（A∩B）
3.2 CSG表現
CSGのトリー構造
∪
∩
∪
－
－
3.2 CSG表現
3．境界評価関数
境界評価関数Bi(x,y,z)は，ある点が立体形状の内部にあるか，
外部にあるか，境界(形状の表面)にあるか，さらに境界表面から
どのくらい離れているかを評価する．
n
プリミティブPi
Pi   ( f j ( x, y, z )  0)
j 1
n
Bi ( x, y , z )  max ( f j ( x, y , z ))
j 1
 min{Bi ( x, y , z ), Bk ( x, y , z )} : Pi  Pk 


B ( x, y , z )  max{Bi ( x, y , z ), Bk ( x, y , z )} : Pi  Pk 
 max{B ( x, y , z ), B ( x, y , z )} : P  P 
i
k
i
k 

3.2 CSG表現
3．境界評価関数(例)
y
円Pと楕円Q
1.5
境界評価関数の値を求めなさい.
(0,1.2)
1
-1
0
-1
BP Q ( x , y )
1
x
BP  Q ( x , y )
BP Q ( x , y )
3-１章
3次元形状をモデリングする
境界表現、ＣＳＧ表現、スイープ表現
立体の表現方法(1)

境界表現(B-rep(Boundary Representation))

ＣＳＧ表現(Constructive Solid Geometry Representation)
立体の表現方法(2)

スイープ表現(Sweep Representation)
f1: v1, v2, v3, v4, v5, v6
S: Sweep(f1, dir: (0, 0, -1), length: 4)
境界表現（１）
境界表現とは，頂点・稜線・面と，これらの相互
関係を表すデータによって立体データを表現す
るものである．
境界表現（２）
境界表現によるデータは，以下の２種類のデー
タにより構成される．
幾何データ
：座標，方程式の係数などのような数値データ
トポロジーデータ
：頂点・稜線・面間の関係を表すデータ
幾何データ
トポロジーデータ
ウィングドエッジデータ構造（１）
境界表現の一実現例
ウィングドエッジデータとは，立体を稜線の集まりで
あると定義し，各稜線について，他の稜線・頂点・
面との関係を保持するトポロジーデータ構造である．
各稜線につき一つの
ウィングドエッジデータを生成
ウィングドエッジデータ構造（２）
E3
E2
V2
E
F1
F2
E4
E1
V1
E
V 1 V2
E1 E2
E4 E3
F1 F2
各稜線につき一つの
ウィングドエッジデータを生成
ウィングドエッジデータ構造（３）
E
E
E
E
EVV11 VV22
EV1 V2
1 EV
VV
1 E
V1212EE33
V1 V
E
12 E3
1 EE23 E4
EE
1 E
E23 E4
E1 E22 E4
2 FE
EE
2 F
E1414FF22
E4 E
F
13 F2
F1F1F2F2
F1 F2
稜線の数だけ
ウィングドエッジデータを生成
内部と外部の判定
点Ｐ(x0,y0,z0)が，多面体の中に存在するかを調べる．
面F1のどちら側に点Pが存在するかを調べる．
以上のような処理を，各面について調べる．
全ての面について，点Pは各面の実体側にあると判
断された場合，点Pは立体中に存在するものとする．
F1 V1 E4 F2
V4
F3 E1
E6
E2 E5
V2
E3
V3
F4
点Ｐ(x0,y0,z0)
ＣＳＧ表現(Constructive Solid Geometry)
ＣＳＧ表現とは，立体を３次元空間における点の集合とと
らえ，集合演算を基本に立体をモデル化する方法である．
＋
CSG表現の集合演算
AB
A∩B
A∪B または A＋B
A－B
B－A
ＣＳＧ表現の例（１）
例えば，下図の立体Ｓは，Ａ＋Ｂ
(Ａ:直方体Ｂ:円柱)で表される．
＝
立体Ｓ
＋
Ａ:直方体
Ｂ:円柱
ＣＳＧ表現の例（２）
点集合Ａ0:
(x, y, z) 0  x  11, 0  y  12, 0  z  3
z
y
12
3
点集合Ｂ0:
(x, y, z)
o
x
11

y 2  z 2  3, 0  x  20
z
20
y
o
3
x
ＣＳＧ表現の例（３）
z
変換行列Ｔa
20
y
o
z
x
3
z
y
o
12
3
o
11
x
変換行列Ｔb
y
x
プリミティブの例
内部と外部の判定（１）
例えば，点P(x0,y0,z0)が，下図に示す立体の中
に存在するかを調べる．
点P(x0,y0,z0)
z
o
y
x
内部と外部の判定（2）
この場合，点Pの同次座標 P'(wx0,wy0,wz0,w)を考え，
P'Ｔa-1 が集合Ａ0中に存在するか？
P'Ｔb-1 が集合Ｂ0中に存在するか？
z
点P(x0,y0,z0)
を調べる．
20
y
o
z
3
x
z
y
y
o
x
o
x
形状ＳはＡとＢの和集合なので，上記のいずれかが満たされ
れば，点Pは形状Ｓ中に存在するものとする．
境界表現とＣＳＧ表現の比較
境界表現の利点
形状の幾何データが数値で与えられているので，
形状の表示，シミュレーションに，形状データをその
まま流用できる．
面・稜線・頂点がデータとして別個に管理されてい
るため，形状以外の情報を，面・稜線・頂点に関連
付けやすい．
CSGの利点
形状の定義が明確．
スイープ表現



平面図形を一定方向に移動したときの軌跡で立体を表現
局所変形との組み合わせで，様々な形状を表現可能
平行移動スイープ，回転移動スイープ

Download Report