T&C LAB-AI
Dept. of Intelligent Robot Eng. MU
Robotics
Computer Graphics and Programming
Lecture 4
Jeong-Yean Yang
2020/10/22
1
T&C LAB-AI
Normal Vector
1
2
T&C LAB-AI
Dept. of Intelligent Robot Eng. MU
Robotics
Normal Vector for
Hidden Surface Removal
• Three Basic Components in Graphics
– Vertices
– Polygon
– Normal vector
• Normal vector is used for
– Material and Light ( 95%)
– Hidden Surface Removal (5%)
• Normal vector is very important.
• Two types
– 1) Calculation by three vertices
– 2) Given for Light and Material
3
p1
p2
p3
n: normal vector
T&C LAB-AI
Dept. of Intelligent Robot Eng. MU
Robotics
4. Vector Operation
• Cross Product (외적)
• Determinant of AxB
4
A
B
C
C=A X B
i
j
k
|i|=1, |j|=1, |k|=1
k=ixj , i=jxk , j = kxi
-k=jxi , -i=kxj , -j = ixk
x
y
z
y
z
z
y
z
x
x
z
x
y
y
x
x
y
z
i
j
k
A B
A
A
A
A B
A B i
A B
A B
j
A B
A B k
B
B
B
Ref.
Calculus, Spring
|
| |
| |
||
| sin
C
A B
A B
T&C LAB-AI
Dept. of Intelligent Robot Eng. MU
Robotics
Determinant of A x B
• Cross Product, AxB
– i x i = j x j = k x k = 0
• Why i x i =0 ?
– |C| = |AxB| = |A||B| sin q
– |C| = |AxA| = |A||A| sin 0 = 0
5
y
z
x
y
x
z
x
y
z
y
z
x
y
x
z
x
y
z
y
z
z
y
z
x
x
z
x
y
y
x
i
j
k
A
A
A
A
A
A
A B
A
A
A
i
j
k
B
B
B
B
B
B
B
B
B
A B
A B i
A B
A B
j
A B
A B k
Ref.
Calculus, Spring
T&C LAB-AI
Dept. of Intelligent Robot Eng. MU
Robotics
Cross Product for What?
• Example) Hidden surface removal
6
x
y
z
Eye (1,1,1)
(a,0,0)
(a,b,0)
(a,b,c)
(a,0,c)
A = (a,b,0)-(a,0,0)
= (0,b,0)
A
B
B = (a,0,c)-(a,0,0)
= (0,0,c)
A x B = (bc,0,0)
Eye position
(1,1,1)
(0, 0, 0) - (1,1,1)
(-1, -1, -1)
(
)
0
!
v
v A B
bc
show
Eye (1,1,1)
n1
n2
T&C LAB-AI
Dept. of Intelligent Robot Eng. MU
Robotics
Cross Product of Cube’s Polygon
7
• Remind
z
x
y
0
1
2
3
4
5
6
7
Polygon 0=[0,1,2]
Polygon 1=[0,2,3]
Polygon 2=[6,2,1]
Polygon 3=[6,1,5]
Polygon 4=[4,0,3]
Polygon 5=[4,3,7]
Polygon 6=[7,3,2]
Polygon 7 =[7,2,6]
Polygon 8=[5,1,0]
Polygon 9 =[5,0,4]
Polygon 10=[4,7,6]
Polygon 11=[4,6,5]
p0
p1
p2
n: normal vector
0
1
2
1
2
1
0
1
ˆ
ˆ
,
ˆ ˆ
B
p
p
A
p
p
A B
p
p
p
p
P0= [0,0,0]
P1=[1,0,0]
P2=[1,0,1]
P3=[0,0,1]
P4=[0,1,0]
P5=[1,1,0]
P6=[1,1,1]
P7=[0,1,1]
T&C LAB-AI
Dept. of Intelligent Robot Eng. MU
Robotics
Cross Product in uVector
• Use operator *
• Example of Cross Product of uVector (HW6)
8
y
z
z
y
z
x
x
z
x
y
y
x
A B
A B
A B i
A B
A B
j
A B
A B k
T&C LAB-AI
Dept. of Intelligent Robot Eng. MU
Robotics
Example
uWnd-21-Hidden surface
• Compare
Normal vector and Z vector
9
z
x
y
0
1
2
3
4
5
6
7
2
1
0
1
ˆ ˆ
ˆn A B
p
p
p
p
ˆ [ , , ]
n
0 :
Draw
else:
pass
x
y
z
z
n
n n n
if
n
0
z
n
0
z
n
0
z
T&C LAB-AI
Camera Work
2
10
T&C LAB-AI
Dept. of Intelligent Robot Eng. MU
Robotics
uWnd-21-Hidden surface
Operation Architecture
• uObj::Draw()
11
Object
Transform
H
vertex
Get
Normal
Object
is rotating
temp
normal
Draw
Polygon
Or
Not
temp
Projection
temp
T&C LAB-AI
Dept. of Intelligent Robot Eng. MU
Robotics
Object Transform Vs. Camera Work
ex) uWnd-22-Camera Work
12
• Object Transform Camera Work
z
x
y
'
S
P Hv
S
P v
Scale projection
Object transform
z
x
y
'
c
S
P TR Hv
S
P H
v
H
c
H
TR
T&C LAB-AI
Dept. of Intelligent Robot Eng. MU
Robotics
Camera Work: Rotation and Translation
Hc=TR in uCam
• Remind Fixed Coordinate
13
R
H
0
1
0
1
0
1
T
R
I
T
R
O
R T
H
H
H
T
H
T&C LAB-AI
Dept. of Intelligent Robot Eng. MU
Robotics
Example and HW 7
• Click Left mouse button and drag.
– Left and right direction rotates along Y-axis
– Up and Down direction rotates along X-axis
14
z
x
y
'
c
S
P TR Hv
S
P H
v
c
H
TR
z
x
y
RotY
z
x
y
RotY
RotX
c
Y
X
H
TR
TR R
T&C LAB-AI
Dept. of Intelligent Robot Eng. MU
Robotics
Hidden Surface Removal with Camera Work
Is it Good?
• Normal vector is a directional vector.
• Transform of Direction vector is wrong.
15
z
x
y
c
H
TR
z
x
y
n
0 for Draw
ˆ
ˆ n 0
z
z
ˆ
ˆ
(
)
c
z H n Bad
Case 1)
Case 2)
ˆn
z
y
ˆn'
z
y
H
H
T&C LAB-AI
Dept. of Intelligent Robot Eng. MU
Robotics
Hidden Surface Removal:
• Example) uWnd-25-Camera Walk2-Hidden
16
Object
Transform
H
vertex
Camera
Transform
Hc
temp
temp
Get
Normal
Draw
Polygon
Or
Not
normal
Projection
2D
3D
good
Bad
Bad
Bad case for Perspective Projection
T&C LAB-AI
Dept. of Intelligent Robot Eng. MU
Robotics
Why it is Wrong?
17
z
x
y
0
1
2
1
0
1
2
1
ˆ
ˆ
'
(
) (
)
ˆ ' (
) (
)
c
c
c
c
c
c
n
H n
H
p
p
p
p
n
H p
H p
H p
H p
z
x
y
• Normal vectors are same in both cases
• But, Perspective projection has skewed and warped
plane.
Projection View
Perspective view
T&C LAB-AI
Dept. of Intelligent Robot Eng. MU
Robotics
Hidden Surface Removal
for Perspective Projection
• Counter Clockwise Direction in 3D is changed in 2D
Space
• Drawing Clockwise is removed
18
2
1
3
1
2
3
3D vertices
Draw polygon
Counter clockwise
2D vertices
(counter clockwise)
2D vertices
(clockwise!!)
Draw
Remove
T&C LAB-AI
Dept. of Intelligent Robot Eng. MU
Robotics
Normal Vector in Projected 2D Space
Case of Drawing Counter Clockwise
19
f
s
t
f
s
t
ˆ
ˆ
,
ˆ ˆ
ˆ ˆ
ˆ
0
B
f
s
A
t
s
A B
t
s
f
s
z A B
ˆ
ˆ
,
ˆ ˆ
ˆ ˆ
ˆ
0
B
f
s
A
t
s
A B
t
s
f
s
z A B
Draw
Remove
• Example) uWnd-26-Camera Walk3-Hidden
T&C LAB-AI
Object Designs
3
20
T&C LAB-AI
Dept. of Intelligent Robot Eng. MU
Robotics
Graphic Primitives
• Primitives
– Box, Plane, Sphere, Donut, Tube, and so on
– The shapes are NOT fantastic, BUT these are useful for
mathematical calculation of some parameters
• Primitives = Parametric Space
• Parametric Vs Polygon-based geometry
– Parametric object is good for calculation
– Polygon takes long time of calculating all polygon
21
Parameteric
Distance
From here
T&C LAB-AI
Dept. of Intelligent Robot Eng. MU
Robotics
New Class : uPolygon
• uPolygon: Polygon class with three vertices index
– What is INDEX?
– Polygon has three indices that are the offsets of vertices
buffer
22
0
1
2
Polygon
vertices
T&C LAB-AI
Dept. of Intelligent Robot Eng. MU
Robotics
Ex) uWnd-27-class-Polygon-Complete
uWnd-uObj-uCam-uPolygon
23
uWnd
uCam
Projection,P
Scale, S
Camera Position, H
uObj
uObj box;
Draw() { box.draw()}
MouseMove() { cam}
uPolygon
pPoly;
uPolygon
Index f,s,t
Run() { box.update() }
Vertices
Array
3D
Temp
Array
2D
Update()
H
Draw
Draw
T&C LAB-AI
Dept. of Intelligent Robot Eng. MU
Robotics
uObj::Update()
• Update() function calculates
– original 3D vertex(pVer) into 2D projected vertex(pTemp)
• uObj has Object Drawing and Vertex Calculation
24
uObj::Draw()
With pTemp
uObj::Update()
Vertex temp
T&C LAB-AI
Dept. of Intelligent Robot Eng. MU
Robotics
uObj::Update()
25
2
3
cam cam
cam
object
t
S
P H
H
v
f
s
t
ˆ ˆ
ˆ
ˆ ˆ
ˆ
0
n
A B
t
s
f
s
z A B
T&C LAB-AI
Dept. of Intelligent Robot Eng. MU
Robotics
Dynamic Memory Allocation
new and delete from C++
26
uObj.h
Cube has 8 vertices and 12 polygons.
Cylinder has 36x2 vertices and 72
polygons
Numbers of Vertices and Polygon are
variable.
Dynamic Memory Allocation
T&C LAB-AI
Dept. of Intelligent Robot Eng. MU
Robotics
Dynamic Memory Allocation
new and delete from C++
27
uObj box;
uObj.h
box.pVer = NULL
T&C LAB-AI
Dept. of Intelligent Robot Eng. MU
Robotics
Dynamic Memory Allocation
new and delete from C++
28
uObj box;
box.Alloc( 8,12)
uObj.h
box.pVer = NULL
Nothing
done
T&C LAB-AI
Dept. of Intelligent Robot Eng. MU
Robotics
Dynamic Memory Allocation
new and delete from C++
29
uObj box;
box.Alloc( 8,12)
uObj.h
box.pVer = NULL
box.pTemp=NULL
box.pPoly = NULL
box.pVer[8]
box.pTemp[8]
box.pPoly[12]
T&C LAB-AI
Dept. of Intelligent Robot Eng. MU
Robotics
After using uObj,
Created Memory MUST be Deleted
30
uObj box;
box.Alloc( 8,12)
uObj.h
box.pVer[8]
C++ starts to destroy box
box.pVer[8]!=NULL
delete box.pVer
box.pVer[ ]
No 8 Storage
T&C LAB-AI
Dept. of Intelligent Robot Eng. MU
Robotics
Allocation of Pointer Variable in C++
31
uVector *p;
Pointer variable
p=NULL;
Application Heap memory
0
P has NO storage
p = new uVector [3];
0
6
p=6;
P has 3 storages
Initial
state
“new”
in C++
delete p;
x
x
x
0
6
p=6;
“delete”
in C++
Be careful!!
Don’t use like
p[0]=1
p=NULL;
x
x
x
0
6
p=0;
Remark
p= NULL
Confusion!!!
NO storage
P has NO storage
T&C LAB-AI
Dept. of Intelligent Robot Eng. MU
Robotics
Ex 1) uObj::MakeBox(1,2,3)
32
8
vertices
12
polygons
z
x
y
0
1
2
3
4
5
6
7
T&C LAB-AI
Dept. of Intelligent Robot Eng. MU
Robotics
Ex 2) Make Box by Arrays
33
Remind that
sizeof(vs)=3*float*8=3*4*8 = 96
sizeof(ps)=3*int*8 = 3*4*12=144
T&C LAB-AI
Dept. of Intelligent Robot Eng. MU
Robotics
Then, if we change vertices and polygons,
Everything can be rendered in Graphics
• Vertices = 1489, Polygons= 2974
• See uWnd-29-complex
34
T&C LAB-AI
Dept. of Intelligent Robot Eng. MU
Robotics
Example) Draw a Dog
• https://3dwarehouse.sketchup.com/
• https://3dwarehouse.sketchup.com/model/u24f15eea
-ce38-414e-ae9b-512ccbda2eb8/dog
• See dog.obj file in example
35
Sketchup
program
Export
3ds
3d Max
Wavefront
*.obj
C++
Program
Vs[]
Ps[]
T&C LAB-AI
Dept. of Intelligent Robot Eng. MU
Robotics
Wavefront Object file, *.obj
36
Vertex vector
v X Y Z
Polygon index
f f s t
Be careful!
It is NOT zero index. Start from 1.
But, general array has zero index that
starts from 0.
-1 for zero index
T&C LAB-AI
Dept. of Intelligent Robot Eng. MU
Robotics
But, Something is Wrong in Dog Drawing
• Why Dog’s Ear is drawn?
37
Hidden
Surface
Removal
(HSR)
Is OK
HSR fail.
HSR fail.
HSR fail.
T&C LAB-AI
Dept. of Intelligent Robot Eng. MU
Robotics
Final Problems of Graphics is
Depth Problem
• Hidden Surface Removal(HSR) is NOT the sufficient
condition for 3D Graphics
• HSR is that opposite polygons are Hidden.
– It does NOT determine if far polygon is overlapped by closer
polygon
38
Torus
HSR is
good
HSR is
NOT
good
A
A
B
B
T&C LAB-AI
Dept. of Intelligent Robot Eng. MU
Robotics
Z direction Depth Problem
• HSR has no function of Which One is close or far
• How Graphics solve this problem?
– Z buffering from Unit Space Mapping in Ch. 3
– But, we do NOT implement it.
– OpenGL or Direct X has Z-buffering, too.
39
Draw
wireframe
T&C LAB-AI
Example of Object Primitives
4
40
T&C LAB-AI
Dept. of Intelligent Robot Eng. MU
Robotics
Make Cylinder ( Radius, height, Resolution)
• uWnd-25-Cylinder before uPolygon Class
• uWnd-30-cylinder after uPolygon Class
41
Hidden surface removal works
bottom
If resolution=3, angle gap is 360/3 = 120.
top
T&C LAB-AI
Dept. of Intelligent Robot Eng. MU
Robotics
Example) uWnd-30-cylinder
42
N(resolution)=36
Vertex = N*2
Polygon= N*2*2
Two triangles
bottom
0
1
2
35
top
N+0
N+1
N+2
N+35
0
1
N+0
N+1
35
0
N+0
N+35
T&C LAB-AI
Dept. of Intelligent Robot Eng. MU
Robotics
Top and Bottom of Cylinder
• Vertex = 2* N+ 2
(top+bottom)
• Polygon = 2N(side) +
N(top) + N(bottom)
43
• Modify MakeCyl function for top and bottom.
