Integral Geometry Tools for Computer Graphics
Mateu Sbert*, IIiA, Universitat de Girona, Spain Andrei Iones, Saber Interactive, NY, USA Anton Krupkin, Saber Interactive , NY, USA Sergei Zukhov, Creat Studio and St Petersburg State Technical University
*Partially supported by SIMULGEN ESPRIT Open LTR Project #35772
Bertrand paradox
Question: probability for the length of random chord in unit circle to exceed (length of inscribed equilateral triangle). The answer depends on what is meant by random!
3
Bertrand paradox. First density
θ
Take a random direction in the circle and then a random point in the circle. Chord has to intersect from half of the radius towards the center. Probability = 1/2
πθ
θ 2
, (
1
x dx d f )=
x
Homogeneous and isotropic!
Bertrand paradox. Second density
2 2
2 1
, (
x x dx d
f )= −
π θ θ
Take two random points P,Q on the circle. Q has to be on the arc with length subtended by angle at P. Probability = 1/3
P
Q
3 π
Bertrand paradox. Third density
π θ θ xdx d x
f ( , )=
3
Take a random point M, the chord midpoint, in the circle . M has to be in the concentric circle with radius 1/2. Probability = 1/4
M
Integral Geometry target: densities of geometric objects invariant under
rotations and translations and associated measures
- densities of lines;
- densities of planes;
- densities of bodies, kinematic density;
- measures of intersections,e.g.,lines intersecting a body
Geometric probability: quotient of associated measures, Laplace rule
2D line density
φ dpd dG=
φ G
O p y
x
K
L dG G n( ) =2
∫
If n(G) is the number of intersections of line G with curve K:
Measure of lines intersecting a convex body
Measure of lines intersecting a convex body (n(G) =2):
K1 K2
Probability that a line intersecting K1 also intersects K2:
2 1
L L
L dG=
∫
Support functions
-K –convex body
-O ∈ K – coord system origin
-l – support line
-p(ϕ) – the distance from O to l, perpendicular to the direction ϕ
ϕ p(ϕ)
l
O
Definition. Function p(ϕ) is called the support function of the convex body K, related to the origin O.
L – the perimeter of convex body K
=2∫π ϕ ϕ
0
) ( d p L
Breadth (or thickness)
Definition. The breadth ∆(ϕ) of the convex body K in the direction ϕ is the distance between to two parallel support lines to K, that are perpendicular to the direction ϕ, such that the body K is in-between them.
∆(ϕ) = p(ϕ) + p(ϕ+π).
L= p(ϕ)
ϕ
∆(ϕ)
∫∆
π
ϕ ϕ
0
) ( d
Densities of bodies
ϕ
O O’
x x’
y y’
K
a b
ϕ dadbd dK= kinematic density:
3D line density
ς η ωd d d dG=
ω η O
z
y
x ς
' ' cosθdωdηdς dG=
ς' η' θ
E ω
Lines intersecting a surface
σ ω θd d dG=cos
θ ω
σ d S
A dG G
n =π
∫ ( )
For a convex body:
If n(G) is the number of intersections of line G with surface S:
A dG 2
=π
∫
Probability of line intersection for a convex body interior to a second one
K1 K2
2 1
A A
For an interior polygon:
Prob. of intersection (3D):
2
2 1
A A
→0 ε A1
Measure of chords
Average length of chord for a convex body:
A V A V 4 2 2ππ = σ G
V d d d
dG ω σ η ς π σ =∫ ∫ =2
∫ Ω
(i.e., for a sphere:4/3r)
3D plane density
ω dpd dE=
Measure of planes intersecting a convex body: Mean curvature M For a convex polygon of perimeter L:
Parallelepiped with edges a,b,c: 2 M=πL
) (a b c M=π + +
3D thickness
Measure of planes intersecting a body:
∫
=
fixed
) (
ω
ω dp
T
∫
=
2
) ( ) (
S
E K Tω dω
µ
ω
For a convex body total thickness is equal to mean curvature M
Measure of sections
Average section of a random
plane with a convex body: M V M
dE π σ =2
∫
E σ
∫
∫ ∫ ∫
∫ Ω − Ω
=
=
=
= dpd d dp V d V
dE
p
p
π ω σ
ω ω σ
σ ω
ω
2
) (
) (
Optimality criteria
Optimality criterion for line shooting: minimization of the perimeter of the bounding volume.
Line shooting - similar to ray shooting.
Difference: the measure of lines intersecting a body is finite, while the measure of rays is infinite.
Bounding volumes & optimality criteria
- The use of bounding volumes in CG
- Hierarchical and non-hierarchical Bvolumes
- Types of volumes (AABB, OBB, spheres, slabs) T = Nv*Cv + Np*Cp
upper-level bvolume
scene object
minimal enclosing sphere
minimal enclosing sphere that is constrained to belong to upper-level bvolume
“Hierarchical nested-ness criterion” may yield bounding volumes that are not optimal
Bounding volume optimality criteria (ray shooting)
Theorem: Optimal bounding volume for ray shooting has minimal perimeter
Note: Importance of uniform distribution of rays
Fixed direction θ
scene object K0 bounding volume K O
a(θ) b(θ)
∆0(θ)
∆(θ)
bounding volume K a scene object K0
G1 G3
G2
Improper intersections:
all improper
m p=m
Bounding volume optimality criteria (frustum culling)
Theorem: Optimal bounding volume for frustum culling has minimal perimeter
γ γ
scene object K0
enclosing volume K
pyramid of vision with angle 2γ direction of view θ
point of view (x, y)
object K0
enclosing volume K
γ γ θ
θ-γ θ+γ γγ
γ γ
Construction algorithms
2D case
minimal perimeter bounding rectangle:
convex polygon - O(N) point sets - O(NlogN) 3D case
Optimal bounding prisms
Hierarchical bounding volumes
upper-level bvolume
scene object
minimal enclosing sphere
minimal enclosing sphere that is constrained to belong to upper-level bvolume
R m(R)
l
“Quality” of bounding volumes as a function of radius R
Polygon triangulations
q
P Q
P' Camera
coordinate system
Optimal triangulation – minimal perimeter triangulation
Global lines generation: from the walls of a convex bb
Random point on bb wall and random direction according to
i.e., random “local” lines from the walls, taking into account all intersections.
ω θd cos
Global lines generation: from the bounding sphere
Pairs of random points on the sphere define global lines (valid in 3D, but not in 2D!)
Correct and incorrect global lines generation
Q
Q’
d r θ
θ’
θ θ
R
xi xj
r/2 r Ni
Nj
(a) Geometry for two points on sphere line generation.
(b) Geometry for incorrect line generation. Ratio of densities equal to:
a) b)
2 '
cos cosθr θ
Global lines generation: from tangent plane
Bundles of parallel lines from tangent plane to bounding sphere. Average intersections with surface i
where is the bundle section (pixel area)
∆ 2
Ai
∆
Geometry for Form Factors
Form Factor as area integral (a)
and hemisphere integral (b).
Ai Ai
Aj
Aj
dAi
dAj
r(xi, xj) θi
θj
V(xi, xj)
dω
a ) b)
= ∫ ∫
i j
A A i j ij i j
i
ij V dAdA
A r
F 1 cosθcos2 θ π
∫ ∫Ω
= A ij i
ij V x dAd
F π1A ( ,ω)cosθ ω
Monte Carlo Integral
Using Monte Carlo integral with pdf to compute Form Factor integral we obtain a sum of binary visibilities .
Ai
x
f π
ω cosθ ) ,
( =
) , (
cos ) , 1 ( 1
1 k k
k k k k N ij
k i
ij f x
sin x
V A F N
ω θ θ ω
∑ π
=
≈
i k k
k k k k N ij
k i
A sin
sin x
V A N
π θ θ
θ θ ω
π cos
cos ) , 1 ( 1
1
∑=
=
, ∑
= N= k Vij k xk
N1 1 (ω , )
Local lines to compute Form Factors
Fij=2/7 Fik=4/7 Fkj=?
i
k
j
Local lines from patch i distributed according to pdf are used to compute Form Factors from i.Ai
x
f π
ω) cosθ ,
( =
Relationship between Form Factor and global lines densities
A global density of lines submits on each surface the “local” density corresponding to the Form Factors one.
With global line parametrization from a surface:
σ ω θd d dG=cos
θ ω
σ d S
∫
∫ ∫Ω = ∩≠
=
φ
ω θ
π i A ij ω i G i ij
ij V x dAd V GdG
F A
i
) ( cos
) , 1 (
Local and global lines
With “global” lines we can use bidirectionally all intersections.
With “local” lines we can only use the first intersection.
Global lines to compute Form Factors
Fij=2/7 Fik=4/7 Fkj=4/6
i
k
j
Random “global” lines can be used to compute Form Factors for all intersected patches.
Random walk generated with local lines
A local line makes advance one single path a)keeping impinging point b)sorting new exiting point
Source Source
a) b)
Random walk generated with global lines
A global line makes advance several paths ad once a)idealized situation b)actual paths
Source Source
a) b)
Some Radiosity results
R.Martínez et al.:Multipath algorithm with bundles of lines
Global lines can be used with dynamic environments: Multiframe method
(Besuievski et al.)
Intersection list:w1,ot11,ot12,ot21,ot22,ot31,ot32,w2 Three intersections list extracted for t1,t2 and t3:
w1,ot11,ot12,w2; w1,ot21,ot22,w2; w1,ot31,ot32,w2 t3
t2
t1 ot12
ot21 ot22
ot31 ot32
ot11 w1
w2
Scene statistics-1. Int.by lines
W
Average number of intersections of a line crossing convex cavity W with interior bodies Ki:
Ki
) (
) ( 2 int AW
K G A n =
) (
)
* (
int G K
K G A
n µ
=π Idem intersecting K:
U
i
Ki
K=
∑
=
i
Ki
A K
A( ) ( )
Scene statistics-2
Average length of the sum of the chords per global line:
) (
) ( 4
W A
Ki
∑V
Idem per chord:
Probability of 0 intersections:
* int
1 int
) 0
( G
G
n p = −n
Probability of i intersections:
) (
) ) (
( iAW
K i A p ≤
) (
) ( 4
K AV Ki
∑
Scene statistics-3. Int. By planes
Average number of objects in K
intersected by a plane intersecting W: ( ) ) (
int MW
Ki E T
n ∑
= Idem intersecting K:
U
i
Ki
K=
W Ki
) (
) (
int T K
Ki E T
n ∑
=
Which scene statistics gives more useful info about the scene?
But different p(i) distribution.
Same average number of intersections!
Objective: given scene statistics obtain the best structuration for ray-tracing intersection.
Some steps begun in Vlastimil Havran PhD.
Visibility continuous mutual information is the least upper bound to the visibility discrete mutual information:
Cheap cost Monte Carlo computation:
Continuous mutual information computation
∑
∑= = =
≈ N
k
y x N T
k
k k T c
s r
A y N
x F N A
I
1 2
1
cos ) log( cos
)) 1 , ( 1 log(
π θ θ dxdy y x F A y x A F
I xS yS T
T c
s 1 ( , )log( ( , ))
∫ ∫∈ ∈
=
x
y d(x,y) θy
θx
My contribution is ) ) ( p 2
cos log( cos
x,y d LT θx θy Scene Length = LT
Lines Cast = K Line Segments = N
Scene complexity is ...
∑=
≈ N
k
y x c T
s d
L
I N k k
1
2 ) cos log( cos
1
π θ θ
