25
1 Terrain Rendering Case Study: Flytastic II
1
Terra
in R
end
ering
Ca
se Stud
y: Fly
tastic
II
2
Terra
in R
end
ering 2
Pro
blem
•G
iven
Sw
itzerla
nd
(350 x
220 km
) as
–O
rtho
ph
oto
s
•2m
pe
r pix
el
•175’0
00
x 110
’00
0 p
ixels
•H
eig
ht fie
ld:
•10
m m
esh
•35’0
00
x 22’0
00
=
770’0
00
’00
0 h
eig
ht va
lue
s
•Fly th
rou
gh
the
scen
e in
rea
l-time
3
Terra
in R
end
ering 3
Overview
•LO
D M
eth
od
Te
rrain
simp
lificatio
n sim
plifie
d:
A g
en
era
l fram
ew
ork
for vie
w-d
ep
en
de
nt
ou
t-of-co
re visu
aliza
tion
Lind
strom
, P.
Pa
scucci, V
.,IEEE T
ran
sactio
ns o
n V
isua
lizatio
n a
nd
C
om
pu
ter Gra
ph
ics, 200
2, Vo
l8, Issu
e 3, p
ag
es 239
-254
•E
xte
nsio
ns
–T
erra
in file
form
at
–O
rtho
ph
oto
(tex
ture
) ha
nd
ling
4
Terra
in R
end
ering 4
View
Dep
end
ent LO
D
•N
ea
r cam
era
: Hig
h d
eta
il
•Fa
r aw
ay: C
oa
rse m
esh
Co
urte
sy Pe
ter Lin
dstro
mN
o LO
D
5
Terra
in R
end
ering 5
Pro
gressive M
esh
•S
plit lo
ng
est e
dg
e
•La
yers o
f vertice
s (colo
rs)
•D
AG
: In g
en
era
l eve
ry verte
x h
as
–Fo
ur ch
ildre
nin
ne
xt le
vel
–T
wo
pa
ren
tsin
pre
viou
s leve
l
6
Terra
in R
end
ering 6
Refin
emen
t Op
eratio
n
•A
ctivate
verte
x v
/ split e
dg
e e
ee
v
7
Terra
in R
end
ering 7
Loca
l Refin
emen
t
•T
op
view
on
terra
in:
•S
ide
view
of e:
ee
v
e
v
wo
rlde
rror o
f v
terra
in e
leva
tion
•R
efin
e if p
roje
cted
erro
r > thre
sho
ld
8
Terra
in R
end
ering 8
Avo
idin
g T
-jun
ction
s•
If vis a
ctive, a
ll its pa
ren
ts m
ust b
e a
ctive (re
cursive
)
•M
ultip
le p
are
nts!
•C
ho
ose
erro
r(v) su
ch th
at th
is criterio
n
is alw
ays tru
e!
9
Terra
in R
end
ering 9
Refin
emen
t Criterio
n
•S
cree
n sp
ace
(pro
jecte
d) e
rror ρ
i of ve
rtex
i
),
,(
ep
ii
iε
ρρ
= pro
jectio
n fu
nctio
n
wo
rld e
rror
verte
x lo
catio
n eye
po
sition
),
,(
),
,(
ep
ep
jj
ii
ερ
ερ
≥•
We
ne
ed
for a
ll child
ren
jof ve
rtex
i
10
Terra
in R
end
ering 10
Refin
emen
t Criterio
n
•W
e g
et fo
r all ch
ildre
n jo
f verte
x i
ji
εε≥
•b
y de
finin
g
otherwise node
leaf is
}}
{m
ax ,
oferror
wold
max{
of
error
world
of
child
ie
ii
ji
ji
=
ε
•ca
n b
e p
re-co
mp
ute
d
11
Terra
in R
end
ering 11
Refin
emen
t Criterio
n
•W
e w
an
t for a
ll child
ren
jof ve
rtex
i
•D
efin
e b
alls a
rou
nd
vertice
s
otherwise node
leaf is
}
p-p
{m
ax0
of
child
ir
rj
ji
ij
i
+=
•a
nd
),
,(
),
,(
ep
ep
jj
ii
ερ
ερ
≥
}p-
:{
)(ball
ii
ri
≤=
xx
12
Terra
in R
end
ering 12
Ba
lls of V
ertices
•b
all(i) co
nta
ins a
ll de
scen
da
nts o
f i
13
Terra
in R
end
ering 13
Refin
emen
t Criterio
n
•W
e g
et fo
r all ch
ildre
n jo
f verte
x i
•w
ith
ji
ρρ≥
),
,(
max
)ball(
ex
xi
ii
ερ
ρ∈
=
•m
ea
sure
dista
nce
to b
all(i) fo
r pro
jectio
n
14
Terra
in R
end
ering 14
Refin
emen
t Criterio
n
•Fo
r isotro
pic p
roje
ction
–
elevatio
n erro
r assu
me
d p
ara
llel to p
rojectio
n p
lan
e
–d
erivatio
n in
the p
ap
er
•w
ith
–im
ag
e w
ith in
pix
els w
–p
ixe
l erro
r tole
ran
ce τ
–fie
ld o
f view
ϕ
()
22
))2/
tan(2
/()(
activei
ii
rw
ip
e−>
+⋅
⋅=
ϕτ
ε
15
Terra
in R
end
ering 15
Ren
derin
g th
e Terra
in
•S
tart w
ith co
arse
st leve
l
•R
ecu
rsively te
st if child
ren
active
•R
ecu
rsive p
roce
du
re in
pa
pe
r g
en
era
tes tria
ng
le strip
!
16
Terra
in R
end
ering 16
View
Frustu
m C
ullin
g
•M
od
ify active
test:
0)V
F
)(
ball(
)(active
),V
F(
active≠
∧∧
=i
ii
Co
urte
sy Pe
ter Lin
dstro
m
17
Terra
in R
end
ering 17
File Da
taM
od
el
•Lo
cality
–A
void
ran
do
m a
ccess (ca
chin
g)
–S
ave
ea
ch la
yer se
pa
rate
ly
–D
on
‘t save
laye
r row
/colu
mn
-wise
•S
pa
rsity
–M
an
y valu
es in
fine
laye
rs d
on
‘t ne
ed
to b
e sto
red
(lake
s, pla
ne
s)
18
Terra
in R
end
ering 18
Layer P
ara
metriza
tion
Eve
n la
yer
Od
d la
yer
0,00,1
0,20,3
1,01,1
1,21,3
2,02,1
2,22,3
3,03,1
3,23,3
0,00,1
0,2
1,01,1
1,21,3
2,02,1
2,2
4,04,1
4,2
6,06,1
6,2
3,03,1
3,23,3
5,05,1
5,25,3
19
Terra
in R
end
ering 19
Co
ord
ina
tes of C
hild
ren
Eve
n →
od
dO
dd
→e
ven
2y,x
2y+1,xy,x
2y+1,x+1
2y+2,x
y-1,2x-(y%2)
y,x
y-1,2x+1-(y%2)
y,2x+1-(y%2)y,2x-(y%2)
20
Terra
in R
end
ering
20
2D →
1D M
ap
pin
g
Bin
ary a
dd
ress in
file fro
m (x
,y):
x7 x6 x5 x4 x3 x2 x1 x0y7 y6 y5 y4 y3 y2 y1 y0
•R
ow
-wise
(far ju
mp
s wh
en
y cha
ng
es)
x7 x6 x5 x4 x3 x2 x1 x0 y7 y6 y5 y4 y3 y2 y1 y0•
Co
lum
ns-w
ise (fa
r jum
ps w
he
n x
cha
ng
es)
x7x6
x5x4
x3x2
x1x0
y7y6
y5y4
y3y2
y1y0
•M
ixe
d (lo
cal in
2D →
likely
to b
e lo
cal in
file)
21
Terra
in R
end
ering 21
Gen
eralized
Qu
ad
-Tree
•If ε
i > static th
resh
old
do
n‘t sto
re ve
rtex
i•
Ca
n yie
ld sp
arse
laye
rs →sto
re a
s tree
x7x6
x5x4
x3x2
x1x0
y7y6
y5y4
y3y2
y1y0
Ro
ot ta
ble
(2
4e
ntrie
s)
Inte
rna
l ta
ble
s
Lea
f ta
ble
22
Terra
in R
end
ering 22
Gen
eralized
Qu
ad
Tree
•R
oo
t an
d in
tern
al ta
ble
s store
po
inte
rs
•Le
af ta
ble
s store
he
igh
ts, static e
rrors ε
•S
ub
-tree
s can
be
ab
sen
t:
x7x6
x5x4
y7y6
y5y4
•V
ertice
s ab
sen
t sub
-tree
ca
n n
ot b
e a
ctivate
d
23
Terra
in R
end
ering 23
Orth
oP
ho
tos
•S
tore
d a
s 512 x 512 p
ixe
l tiles
•T
rian
gle
s mu
st be
sub
divid
ed
alo
ng
tile
bo
un
da
ries!
•JP
EG
com
pre
ssed
•S
eve
ral la
yers: 2, 8
, 32, ... me
ters p
er p
ixe
l
•C
oa
rsest le
vel (o
nly 3x
2 tiles) a
lwa
ys loa
de
d
•n
x n
tiles o
f fine
r leve
ls pre
sen
t ne
ar ca
me
ra
•D
raw
ea
ch tria
ng
le w
ith b
est a
vaila
ble
leve
l
24
Terra
in R
end
ering 24
Orth
oP
ho
tos
Ca
me
ra
25
Terra
in R
end
ering 25
Exten
sion
s
•R
em
ove
po
pp
ing
with
ge
o-m
orp
hin
g
•S
ph
erica
l mo
de
l for la
rge
cou
ntrie
s / e
ntire
wo
rld
•C
lou
ds
•D
ay, su
n a
ng
le, n
igh
t
•B
uild
ing
s
