Game Development Reference
In-Depth Information
p
n−1
=
x
n−1
y
n−1
z
n−1
,
p
n
=
x
n
y
n
z
n
,
the best fit perpendicular vector
n
is given by
n
x
=(z
1
+ z
2
)(y
1
− y
2
) + (z
2
+ z
3
)(y
2
− y
3
) +
Computing the best-fit
plane normal from n
points
+ (z
n−1
+ z
n
)(y
n−1
− y
n
) + (z
n
+ z
1
)(y
n
− y
1
),
n
y
=(x
1
+ x
2
)(z
1
− z
2
) + (x
2
+ x
3
)(z
2
− z
3
) +
(9.13)
+ (x
n−1
+ x
n
)(z
n−1
− z
n
) + (x
n
+ x
1
)(z
n
− z
1
),
n
z
=(y
1
+ y
2
)(x
1
− x
2
) + (y
2
+ y
3
)(x
2
− x
3
) +
+ (y
n−1
+ y
n
)(x
n−1
− x
n
) + (y
n
+ y
1
)(x
n
− x
1
).
This vector must then be normalized if we wish to enforce the restriction
that
n
be of unit length.
We can express Equation (9.13) succinctly by using summation notation.
Adopting a circular indexing scheme such that
p
n+1
≡
p
1
, we can write
n
n
x
=
(z
i
+ z
i+1
)(y
i
− y
i+1
),
i=1
n
n
y
=
(x
i
+ x
i+1
)(z
i
− z
i+1
),
i=1
n
n
z
=
(y
i
+ y
i+1
)(x
i
− x
i+1
).
i=1
Listing 9.5 illustrates how we might compute a best-fit plane normal for
a set of points.
V e c t o r 3
c o m p u t e B e s t F i t N o r m a l (
c o n s t
V e c t o r 3
v [ ] ,
i n t
n )
{
/ /
Zero
o u t
sum
V e c t o r 3
r e s u l t
=
k Z e r o V e c t o r ;
/ /
S t a r t
w i t h
t h e
' ' p r e v i o u s ' '
v e r t e x
a s
t h e
l a s t
one .
/ /
T h i s
a v o i d s
an
i f
−
s t a t e m e n t
i n
t h e
l o o p
c o n s t
V e c t o r 3
∗
p
=
&v [ n
−
1];
/ /
I t e r a t e
t h r o u g h
t h e
v e r t i c e s
f o r
(
i n t
i
=
0
;
i
<
n
;
++ i )
{
/ /
Get
s h o r t c u t
t o
t h e
' ' c u r r e n t ' '
v e r t e x
c o n s t
V e c t o r 3
∗
c
=
&v [ i ] ;
/ /
Add
i n
edge
v e c t o r
p r o d u c t s
a p p r o p r i a t e l y
r e s u l t . x
+=
( p
−>
z
+
c
−>
z )
∗
( p
−>
y
−
c
−>
y ) ;
r e s u l t . y
+=
( p
−>
x
+
c
−>
x )
∗
( p
−>
z
−
c
−>
z ) ;
r e s u l t . z
+=
( p
−>
y
+
c
−>
y )
∗
( p
−>
x
−
c
−>
x ) ;
Search WWH ::
Custom Search