1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
|
\documentstyle[jart12]{jarticle}
\pagestyle{plain}
\oddsidemargin=0cm
\evensidemargin=0cm
\textwidth=17.5cm
\textheight=24cm
\begin{document}
\jintercharskip=0pt plus 6pt minus 1pt
\newenvironment{xlist}[0]{\begin{list}{$B!&(J}{
\setlength{\rightmargin}{0mm}\topsep=0mm\partopsep=0mm\parskip=1mm\parsep=0.2mm
\itemsep=0.3mm}}{\end{list}}
\section{$B@\?(J*BN$N9g@.(J}
\subsection{$B%"%k%4%j%:%`$N35MW(J}
2$B$D$NJ*BN$r(Jbody1, body2$B$H$9$k!#(J
$B9g@.$N7W;;$O!"<!$N$h$&$K?JE8$9$k!#(J
\begin{enumerate}
\item $B8r:9$NEPO?(J(insert-intersections)
\item $B8r:9$K$h$C$F6h@Z$i$l$?@~J,$+$i(Jedge$B$r@8@.(J(make-edge-segments)
\item $B8r:9$rLL$N>e$G$D$J$$$GAj4S@~$r@8@.(J(make-crossing-edges)
\item $B@~J,$rLL$4$H$K%=!<%H(J
\item $B@\?($7$F$$$kLL$NH/8+(J(find-contacting-faces)
\item $B=E$J$C$F$$$kLL$NH/8+(J(find-aligned-faces)
\item $B@\?($7$F$$$kLL$NJ;9g(J(merge-contacting-faces)
\item $B=E$J$C$F$$$kLL$NJ;9g(J(merge-aligned-faces)
\item $B6&DL$NLL$KM3Mh$9$k@~J,$N%j%9%H$+$iJDO)$r8+$D$1!"LL!"7j$r:n$k(J
(construct-faces)
\item $BLL$+$i(Jbody$B$N@8@.(J
\end{enumerate}
\subsubsection{insert-intersections}
body1$B$N$9$Y$F$N%(%C%8$H(Jbody2$B$N$9$Y$F$NLL$N8r:9$r(Jintersect1$B$K!"(J
body2$B$N$9$Y$F$N%(%C%8$H(Jbody1$B$N$9$Y$F$NLL$N8r:9$r(Jintersects2$B$K5-O?$9$k!#(J
intersects[12]$B$N3FMWAG$O!"0J2<$N$h$&$J%j%9%H!#(J
(edge (param1 point1 [face1])
(param2 point2 [face2])
. . .)
$B%(%C%8$,LL$H$[$H$s$IJ?9T$J>l9g$O!"8r:9$,$J$$$b$N$H$_$J$9!#(J
$BJ?9T@-$O!"%(%C%8$NC<E@$HLL$H$N(Jplane-distance$B$r(J*coplanar-threshold*
$B$HHf3S$7$F8!::$9$k!#(J
$B0l$D$N%(%C%8$,!"$=$N>e$N0l$D$NE@$N6aK5$GFs$D0J>e$NLL$H8r:9$9$k$H(J
$BH=Dj$5$l$k>l9g$,$"$k!#$?$H$($P!"1_Cl$N>e$K1_?m$,>h$C$F$$$k>l9g!"(J
$B1_Cl$NB&LL$N<4J}8~$N%(%C%8$O!"$=$NC<E@$K$*$$$F!"1_?m$NDlLL$*$h$S(J
$BB&LL$NN>J}$H8r:9$9$k$HH=Dj$5$l$k2DG=@-$,$"$k!#$3$l$r0l$D$NLL$K(J
$B9J$kJ}K!$O$$$/$D$+9M$($i$l$k$,!"$3$3$G$O!":G$bD>3Q$K6a$$3QEY$G(J
$B8r:9$9$kLL$rA*$S!"B>$r<N$F$k!#(J
$B%(%C%8$NC<E@!"$9$J$o$A(Jparam=0 or 1$B$NE@$O!"$?$H$(8r:9$,$J$/$F$b(J
intersects$B$K5-O?$5$l$k!#$3$l$O!"%(%C%8%;%0%a%s%H$r<h$j=P$9:n6H$r(J
$B4JC1$K$9$k$?$a!#$^$?!"(Jintlist$B$N3FMWAG$O!"(Jparameter$B$,(J0$B$+$i(J1$B$K8~$+$C$F(J
$B>.$5$$=g$K%=!<%H$5$l$k!#(J
\subsubsection{make-edge-segments}
intersects[12]$BCf$N3FMWAG$K$D$$$F!"%(%C%8$N%;%0%a%s%H$r@Z$j=P$9!#(J
$B%Q%i%a!<%?$G6h@Z$i$l$?%;%0%a%s%H$NCfE@$r5a$a!"$=$l$,Aj<jJ*BN$N(J
$BFbIt(J(inside)$B$+!"LL>e(J(border)$B$+!"30It(J(outside)$B$+$rH=Dj$9$k!#(J
union$B$r<h$k>l9g$O!"(Jinside$B$HH=Dj$5$l$?%;%0%a%s%H$r<N$F!"(Jborder, outside
$B$N%;%0%a%s%H$r(Jedge$B%*%V%8%'%/%H$H$7$F@8@.$9$k!#7k2L$O!"(Jsegments[12]
$B$K%j%9%H$5$l$k!#(Jedge$B%*%V%8%'%/%H$N(Jpface, nface$B%9%m%C%H$K$O!"JX59E*$K(J
$B85$N%(%C%8$N(Jpface, nface$B$r%3%T!<$7$F$*$/!#$3$l$O!"8e$KLL$N2s$j$K(J
$B1h$C$F%(%C%8$r%H%i%P!<%9$7$F%5!<%-%C%H(J(closed-region)$B$r7A@.$9$k$?$a!#(J
\subsubsection{body :insidep}
$BE@$,J*BN$NFbIt$K$"$k$+30It$K$"$k$+$NH=Dj$K$O!"(Jbody$B$N(J:insidep$B%a%=%C%I$r(J
$BMQ$$$k!#(J:insidep$B$O!"J*BN$,FLJ*BN$+1zJ*BN$+$G0[$J$k%"%k%4%j%:%`$r(J
$B<B9T$9$k!#FL$N>l9g!"E@$HJ*BN$r9=@.$9$k3FLL$H$NId9g$D$-5wN%$r7W;;$9$k!#(J
$B5wN%$,!"@5$G(J*coplanar-threshold*$B0J>e$G$"$l$P!"30It$G$"$k!#5wN%$,(J
*coplanar-threshold*$B$NHO0OFb$G$[$H$s$I%<%m$G$"$j!"$=$NLL$NFbIt$K$"$l$P(J
border$B$HH=Dj$9$k!#%(%C%8>e$K$"$k$+!"LL>e$K$"$k$+$OH=Dj$7$J$$!#(J
$B1z$N>l9g!"$^$:!"E@$HLL$H$N5wN%$r7W;;$7!"(J*coplanar-threshold*$B$NHO0OFb$G(J
$B@\?($7$F$$$l$P(Jborder$B$HH=Dj$9$k!#<!$K!"E@$+$i%i%s%@%`$JJ}8~$KD>@~$rEj<M$7!"(J
$B3FLL$H$N8r:9$rNs5s$9$k!#8r:9$N?t$,4q?t$G$"$l$PFbIt!"6v?t$G$"$l$P30It$H(J
$BH=Dj$9$k!#(J
\subsubsection{face :insidep}
$BLL$NFb30H=Dj$O!"(Jface, closed-region$B$N(J:insidep$B%a%=%C%I$,9T$J$&!#(Jconvexp$B$,(J
T$B$N>l9g!"(Jtriangle$B4X?t$rMQ$$$F!"E@$,%(%C%8$NF1$8B&LL$K$"$&$3$H$rD4$Y$k!#(J
triangle$B$O!"(J3$B$D$NE@$,:n$k;03Q7A$NId9gIULL@Q$N(J2$BG\$rJV$9!#$3$NCM$,!"(J
$B%(%C%8$ND9$5$KHf$Y$F(J(*epsilon*$B$NHO0OFb$G(J)$B$[$H$s$I%<%m$G$"$k>l9g!"(J
border$B$HH=Dj$9$k!#1z$N>l9g!"E@$+$iLL$N3F%(%C%8$r8+9~$`3QEY$r!"(Jvector-angle
$B4X?t$rMQ$$$F7W;;$7!"$=$NAmOB$r<h$k!#FbE@$G$O$3$NAmOB$,(J2pi$B$K$J$j!"(J
$B30E@$G$O%<%m$K$J$k!#$"$k%(%C%8$K$D$$$F8+9~$_3Q$,(Jpi$B$K6a$$>l9g!"(J
border$B$HH=Dj$9$k!#(J
\subsubsection{make-crossing-edges}
intfaces1, intfaces2, first$B$N;0$D$r0z?t$H$7$F<u$1$H$k!#(J
intfaces1$B$O!"(Jbody1$B$N%(%C%8$K$D$$$F(Jbody2$B$NLL$H$N8r:9$r(Jbody1$B$NLLKh$K%j%9%H$7$?$b$N!"(J
intfaces2$B$O!"(Jbody2$B$N%(%C%8$K$D$$$F(Jbody1$B$NLL$H$N8r:9$r(Jbody2$B$NLLKh$K%j%9%H$7$?$b$N$G$"$k!#(J
intfaces1$B$N0l$D$NMWAG$O!"<!$N$h$&$JFbMF$N%j%9%H!#(J
\begin{verbatim}
(face1
(original-edge11
created-edge111
crossing-face-p
crossing-face-n
location (inside/outside/border)
parameter11a
parameter11b)
. . .)
\end{verbatim}
body1$B$NLL(J$face1_i$$B$H(Jbody2$B$NLL(J$face2_j$$B$N8r:9$r(Jvlist1, vlist2$B$K%j%9%H$9$k!#(J
intfaces1$B$N0l$D$NMWAG(J$intfaces1_i$$B$r<h$j=P$9$H!"(J
$face1_i$$B$N%(%C%8$K4X$9$k5-=R$,F@$i$l$k!#(J
$B$=$N(Jcrossing-face-p, crossing-face-n$B$K8=$l$k(Jface$B$N=89g$r(J$f2s$$B$H$9$k!#(J
$f2s$$B$NMWAG$r(J$face2_j, j=1...k$ $B$H$9$k!#(J
$f2s$$B$,!"(J$face_i$$B$,8r:9$9$kLL$N0lIt$G$"$C$F!"(J$face1_i$$B$N%(%C%8$O(J
$face2_j$$B$H8r:9$7$J$$$,!"(J$face2_j$$B$N%(%C%8$,(J$face1_i$$B$H8r:9$9$k>l9g$,$"$k!#(J
$B$=$3$G!"(Jintfaces2$B$r%9%-%c%s$7$F!"(Jcrossing-face-p, crossing-face-n$B$K(J
$face1_i$$B$,8=$l$kLL(J$face2_j, j=k+1...n$$B$r=8$a$k!#(J
$B$3$&$7$F!"(J$face1_i$$B$H8r:9$9$kLL(J$face2_j, (j=1...n)$$B$,8+$D$1$i$l$k!#(J
$B$3$l$i$N8r:9$N$&$A!"(J
(1) $B8r:9$,%(%C%8$NC<E@$G5/$3$C$F$$$k(J
(parameter$B$,(J*epsilon*$B$NHO0OFb$G(J0.0$B$+(J1.0)$B$b$N!"(J
(2) $B8r:9$,Aj<j$NLL$N%(%C%8$NC<E@$G5/$3$C$F$$$k$b$N(J(:on-vertex)$B!"(J
$B$O<N$F$k!#(J
$B8r:9$O!"LL$H%(%C%8$NAH9g$;$K$D$$$F7W;;$5$l$k!#(J
$face1_i$$B$H(J$face_j$$B$N$9$Y$F$NAH9g$;$K$D$$$F!"(J$face1_i$$B$N%(%C%8$H(J
$face_j$$B$N8r:9$r(J$vlist1$$B$K!"(J$face1_i$$B$H(J$face_j$$B$N%(%C%8$N8r:9$r(J
$vlist2$$B$K5-O?$9$k!#(J
$B$3$l$i$NFs$D$NLL$N8r:9$O!"0lD>@~>e$KJB$V!#$3$ND>@~$N>e$G!"(J
$vlist1, vlist2$$B$NMWAG(J$v$$B$r%=!<%H$9$k!#(J
$face1, face2$$B$NK!@~%Y%/%H%k$N30@Q(J
$face1_{normal} \times face2_{normal} = n$ $B$r<h$k$H!"(J
$B$3$l$O8r@~$NJ}8~$K0lCW$9$k!#(J
$v \cdot n$$B$N=g$K%=!<%H$7!"(J$vlist$$B$H$9$k!#(J
$vlist$$B$+$i!"Fs$D$:$DE@$r<h$j$@$7!"$=$N%Z%"$G%(%C%8$r:n$k!#(J
$B$?$@$7!"(J
(1) $BFs$D$NE@$,Hs>o$K6a@\$7$F$$$k;~(J($B5wN%$,(J*epsilon*$B0J2<(J)$B!"(J
(2) $B@8@.$5$l$k%(%C%8$,!"Aj<jLL$N%(%C%8$H=E$J$k>l9g(J(:on-edge)
(3) make-crossing-edges$B$,(J2$B2sL\$K8F$P$l$k>l9g$G!"C<E@$,(Jvlist2$B$K4^$^$l$k>l9g!"(J
$B$O%(%C%8$r:n$i$J$$!#(J
(3)$B$N>r7o$O!"(Jmake-crossing-edges$B$O(J2$B2s8F$P$l$k$,!"(J1$B2s$a$K:n$C$?(J
$B%(%C%8$r=EJ#$7$F:n$i$J$$$h$&$K$9$k$?$a$N>r7o$G$"$k!#(J
$B@8@.$7$?%(%C%8$O!"85$K$J$C$?(Jface$B$G$"$k(J
$face1_i$$B$H(J$face_j$$B$H6&$K%j%9%H$9$k!#(J
\subsubsection{merge-segments}
$B0J>e$G!"%\%G%#$r:F9=@.$9$k$N$K==J,$J@~J,$,5a$a$i$l$?!#(J
$B$3$l$i$r!"$b$H$NLLKh$K%=!<%H$7!"(J
$
((face_1 edge_{11} edge_{12} ... edge_{1i}) \\
(face_2 edge_{21} edge_{22} ... edge_{2j}) \\
...) \\
$
$B$H$$$&7A<0$N%j%9%H$r:n$k!#(J$edge_{ij}$$B$O!"$=$N(Jpface$B$+(Jnface$B$H$7$F(J
$BI,$:(J$face_i$$B$r;}$D!#(J
\subsubsection{contacting-faces}
$body1$$B$N>e$K(J$body2$$B$rCV$$$?;~!"(J$body1$$B$N(Jtop$BLL$H(J$body2$$B$N(Jbottom$BLL$O(Jcontact
($B@\(J)$B$9$k!#(Jcontacting-faces$B$O!"$=$N$h$&$JLL$NAH9g$;$r8+$D$1$k!#(J
contacting-faces$B$O!"3FLL$NAH9g$;$K$D$$$F!"(Jface$B$N(J:contactp$B%a%=%C%I$r(J
$B<B9T$9$k!#(J
$BFs$D$NLL$r(J$f1, f2$$B$H$9$k$H!"(J:contactp$B$O!"<!$N$h$&$K$7$F@\?($rH=Dj$9$k!#(J \\
$f1_{normal} \cdot f2_{normal} \approx -1.0 \wedge $
$f1_{distance} \approx f2_{distance} \wedge $
($f1$$B$N%(%C%8(J$e1_i$$B$H(J$f2$$B$N%(%C%8(J$e2_j$$B$H$N8r:9$,>/$J$/$H$b0l$D$"$k!"$^$?$O(J
$f1$$B$N$9$Y$F$ND:E@$,(J$f2$$B$NFbIt$K$"$k!"$^$?$O(J
$f2$$B$N$9$Y$F$ND:E@$,(J$f1$$B$NFbIt$K$"$k(J)
$B$3$3$G!"(J$face1$$B$H(J$face2$$B$,@\$7$F$$$k$HH=Dj$5$l$?$H$9$k!#(J
$face1$$B$r9=@.$9$k%(%C%8$r(J$e1_i \in edges1, (i=1...m)$$B!"(J
$face2$$B$r9=@.$9$k%(%C%8$r(J$e2_j \in edges2, (j=1...n)$$B$H$9$k!#(J
$B$^$?!"$3$l$i$N%(%C%8$N$=$l$>$l$N$b$&JRB&$NLL$r!"(J$fx1_i, fx2_j$$B$H$9$k!#(J
$e1_i \in edges1$$B$HEy2A$J%(%C%8(J$e2_j \in edges2$$B$rC5$9!#(J
$BEy2A$J%(%C%8$H$O!"$=$NC<E@$,$[$H$s$IEy$7$$$b$N$G$"$k!#(J
$B$b$7!"(J$e2_j$$B$,$"$k$H$9$k$H!"$3$l$O(J$fx1_i$$B$H(J$fx2_j$$B$G6&M-$5$l$k%(%C%8$G$"$j!"(J
$B0lJ}$OITMW$G$"$k!#(J
$B$=$3$G!"(J$e2_j$$B$r(J$edges2$$B$+$i(Jdelete$B$7!"Be$o$j$K(J$e1_i$$B$r(J$edges2$$B$K2C$($k!#(J
$e1_i$$B$O!"(Jpface$B$"$k$$$O(Jnface$B$K(J$face1$$B$r;}$D%(%C%8$G$"$k$,!"$3$l$r(J$fx2_j$
$B$HCV49$9$k!#(J
$B$5$i$K!"(J$fx1_i, fx2_j$$B$NK!@~%Y%/%H%k$rHf3S$7!"$[$H$s$IEy$7$$>l9g!"(J
$e1_i$$B$r$b>C5n$9$k!#(J
$BK!@~%Y%/%H%k$,Ey$7$$>l9g$H$$$&$N$O!"D>J}BN$N>e$K!"JU$r9g$o$;$F(J
$B$b$&0l$D$ND>J}BN$r:\$;$?>l9g$KAjEv$9$k!#(J
$BEy$7$/$J$$>l9g$H$O!"$?$H$($PD>J}BN$N>e$K;M3Q?m$r:\$;$?>l9g$KAjEv$9$k!#(J
$BN>J}$N%(%C%8$r>C5n$7$?>l9g!"$5$i$K(J2$B<oN`$N:n6H$,I,MW$G$"$k!#(J
$B$^$:!"(J$fx1_i$$B$NA4%(%C%8$N(Jpface$B$^$?$O(Jnface$B$H$7$F$N(J$face1$$B$X$N(J
$B;2>H$O!"$9$Y$F(J$face2$$B$X$N;2>H$KCV$-49$($k!#(J
$B<!$K!"(J$e1_i$$B$NC<E@$K=8$^$C$F$$$kB>$N(J2$BK\$N(J
$B%(%C%8$,6&D>@~(J(colinear)$B$G!"N><T$r@\B3$7$F$d$kI,MW$,$"$k>l9g$,$"$k!#(J
$B0lJ}$r>C5n$7!"$b$&0lJ}$N(Jpvert$B$"$k$$$O(Jnvert$B$r1dD9$9$k!#(J
$B6&M-%(%C%8$r;}$?$J$$>l9g!"(J$e1_i$$B$,(J$face2$$B$KFbJq$5$l$k$N$G$"$l$P!"(J
$e1_i$$B$r(J$edges1$$B$+$i(Jdelete$B$9$k!#(J
$e1_i$$B$N(Jpface$B$+(Jnface$B$N(J$face1$$B$r(J$face2$$B$KCV49$9$k!#(J
$e1_i$$B$r(J$edges2$$B$K2C$($k!#(J
$B6&M-%(%C%8$r;}$?$:!"(J$e1_i$$B$,(J$face2$$B$N30It$K$"$k>l9g!"(J
$B2?$b$7$J$$!#(J
$BJQ99$r<u$1$?LL$N%(%C%8$O!"6a$/$K$"$C$F$b!"(Jeq$B$G$J$$D:E@:BI8$r(J
$B;2>H$9$k$h$&$K$J$C$F$$$k2DG=@-$,$"$k!#(J
$B$=$3$G!"(Junify-vertex$B$r8F$s$G!"Hs>o$K6a@\$7$?(J2$BE@$O6&DL$ND:E@$G(J
$BCV$-49$(!"6&DL$ND:E@$,%(%C%8$N4V$G6&M-$5$l$k$h$&$K$9$k!#(J
\subsubsection{merge-aligned-faces}
aligned-faces$B$H$O!"Fs$D$NLL$,F10lJ?LL>e(J(coplanar)$B$K$"$j!"(J
$BK!@~$N8~$-$,F1$8$b$N$r$$$&!#(J
$B$?$H$($P!"$U$?$D$ND>J}BN$r=E$M!"B&LL$r9g$o$;$?>l9g$K$3$3$G8@$&(J
aligned-faces$B$,@8$:$k!#(J
$B$?$@$7!"2<$ND>J}BN$N>eLL(J(top)$B$H>e$ND>J}BN$NDlLL(J(bottom)
$B$,@\$7$F$$$k>l9g$O!"(Jmerge-contacting-faces$B$G=hM}$5$l$k$N$G!"(J
merge-aligned-faces$B$,07$&$N$O!">e$ND>J}BN$,2<$ND>J}BN$K?)$$9~$s$G$$$F(J
contacting-faces$B$,$J$$>l9g$G$"$k!#(J
$B$3$N$h$&$JFs$D$N(Jaligned-faces$B$O!"4pK\E*$KJ;9g$7$F0l$D$K$^$H$a$J$1$l$P(J
$B$J$i$J$$!#(J
$B6qBNE*$J=hM}$O!"(Jmerge-contacting-faces$B$H$h$/;w$F$$$k$,!"(J
$B!#(J
\end{document}
|
