Efficient Bounding Plane Approximation Techniques in Computer Graphics

 
A
p
e
x
 
P
o
i
n
t
 
M
a
p
 
f
o
r
 
C
o
n
s
t
a
n
t
-
T
i
m
e
B
o
u
n
d
i
n
g
 
P
l
a
n
e
 
A
p
p
r
o
x
i
m
a
t
i
o
n
 
S
a
m
u
l
i
 
L
a
i
n
e
T
e
r
o
 
K
a
r
r
a
s
NVIDIA
T
h
e
 
P
r
o
b
l
e
m
How to quickly find a good bounding plane with a given
orientation?
U
s
e
 
C
a
s
e
 
1
:
 
R
a
y
 
T
r
a
c
i
n
g
 
a
n
d
 
R
i
g
i
d
 
M
o
t
i
o
n
Say we have a world-space BVH with leaves containing
object ID + transformation matrix
Each object has a
pre-built BVH in
model space
When ray finds an
object, it descends
into per-model BVH
U
s
e
 
C
a
s
e
 
1
:
 
R
a
y
 
T
r
a
c
i
n
g
 
a
n
d
 
R
i
g
i
d
 
M
o
t
i
o
n
 
When objects move and rotate, the world-space BVH
needs to be rebuilt / refit, but per-object BVHs stay
unchanged
Very fast
But: Where do we get
the world-space
AABBs for the
transformed objects?
T
h
e
 
N
a
ï
v
e
 
S
o
l
u
t
i
o
n
 
Take the object’s
model-space AABB
Transform it along
with the object
Wrap a world-space
AABB around it
Declare victory
Model space
World space
 
T
h
e
 
N
a
ï
v
e
 
S
o
l
u
t
i
o
n
 
Woefully conservative!
Stats for Armadillo:
Average = 94% larger surface area
than for a tightly fit AABB
Worst case = +169% surface area
A spherical model 
is even worse
Average = +125% AABB area
Worst case = +179% AABB area
This kills the world-space BVH
 
 
A
 
B
e
t
t
e
r
 
S
o
l
u
t
i
o
n
 
Start with world-
space AABB
normals
Take them to
model space
Query tight
bounding plane
offsets
Apply in world space
Model space
World space
U
s
e
 
C
a
s
e
 
2
:
 
V
i
e
w
 
F
r
u
s
t
u
m
 
C
u
l
l
i
n
g
 
Both world-space AABB and
transformed object-space
AABB are suboptimal for view
frustum culling
What we really want to know is
whether a bounding plane
oriented along frustum plane is
inside the frustum or not
 
 
Eye
U
s
e
 
C
a
s
e
 
3
:
 
P
e
r
-
O
b
j
e
c
t
 
S
h
a
d
o
w
 
M
a
p
 
E
x
t
e
n
t
s
 
Directional light source
Choosing projection extents
based on object bounding box
wastes shadow map resolution
Tight bounding planes come to
the rescue
 
 
U
s
e
 
C
a
s
e
 
4
:
 
C
o
l
l
i
s
i
o
n
 
D
e
t
e
c
t
i
o
n
 
Transformed object-space
AABBs may intersect
Tightly fit world-space
AABBs may intersect
But if you can guess a
separating plane normal,
it is very cheap to test
Could try, e.g., vector
between object centers
 
 
 
C
o
n
s
t
r
a
i
n
t
s
 
If we want the bounding plane fit to be fast, precalculation
is unavoidable
Otherwise must loop over all* vertices
Mesh needs to be static
Except: See paper for extension
to skinned meshes
 
* Vertices on the convex hull would obviously be enough, but then we’d need to
precalculate the convex hull 
 
 
 
A
A
B
B
:
 
T
h
e
 
G
o
o
d
 
The amount of precalculated data is small and constant
The precalculation is fast and simple
Fitting an arbitrarily oriented bounding plane is really fast
 
 
 
 
 
 
A
A
B
B
:
 
T
h
e
 
B
a
d
 
An arbitrarily oriented bounding plane fit to an AABB can
be extremely conservative
 
H
O
W
E
V
E
R
Fitting an axis-aligned plane works fine (exact result)
Fitting an 
almost
 axis-aligned plane is still okay-ish
 
 
 
 
 
 
 
M
o
r
e
 
I
s
 
M
o
r
e
 
Why not precalculate a many-
sided bounding volume?
T
h
i
s
 
i
s
 
k
n
o
w
n
 
a
s
 
a
 
k
-
D
O
P
Intersection of half-spaces
k
 is the number of plane normals
AABB belongs to the 6-DOP family
Determining the 
k
 plane equations
for a mesh is easy and fast
But…
 
 
 
 
 
 
T
h
e
 
T
r
o
u
b
l
e
 
w
i
t
h
 
k
-
D
O
P
s
 
Determining the vertices of the 
k
-DOP surface is non-
trivial, to say the least
Known as the 
vertex enumeration problem 
in linear
optimization circles
2D case looks deceptively simple, problems start at 3D
 
 
 
 
k
-
D
O
P
 
S
u
r
f
a
c
e
 
T
o
p
o
l
o
g
y
 
I
s
 
N
o
t
 
F
i
x
e
d
A
B
C
 
* Except when it is (e.g., in case of AABBs)
 
*
 
A
p
e
x
 
P
o
i
n
t
 
M
a
p
 
Start with a 
k
-DOP, but instead of trying to find the 
k
-DOP
surface vertices, find some other vertices
T
h
e
s
e
 
a
r
e
 
w
h
a
t
 
w
e
 
c
a
l
l
 
a
p
e
x
 
p
o
i
n
t
s
T
h
e
y
 
m
a
y
 
b
e
 
k
-
D
O
P
 
s
u
r
f
a
c
e
 
v
e
r
t
i
c
e
s
,
 
b
u
t
 
p
o
s
s
i
b
l
y
 
a
r
e
n
t
 
I
n
 
a
d
d
i
t
i
o
n
,
 
c
h
o
o
s
e
 
k
-
D
O
P
 
n
o
r
m
a
l
s
 
c
a
r
e
f
u
l
l
y
 
s
o
 
t
h
a
t
 
w
e
c
a
n
 
e
a
s
i
l
y
 
d
e
c
i
d
e
 
a
 
s
i
n
g
l
e
 
a
p
e
x
 
p
o
i
n
t
 
t
o
 
f
i
t
 
t
h
e
 
b
o
u
n
d
i
n
g
p
l
a
n
e
 
a
g
a
i
n
s
t
Makes bounding plane construction extremely fast
 
 
 
k
-
D
O
P
 
N
o
r
m
a
l
s
 
We choose the 
k
-DOP
normals to point at the
vertices of a regularly
tessellated cube
With each face tessellated
to 
n
×
n
 squares, we get
6
n
2 
+ 2 normal directions
In this figure, 
n
 = 8 
 
k
 = 386
 
 
k
-
D
O
P
 
N
o
r
m
a
l
s
T
h
e
 
d
i
r
e
c
t
i
o
n
 
s
p
a
c
e
 
i
s
 
d
i
v
i
d
e
d
 
i
n
t
o
 
t
r
i
a
n
g
u
l
a
r
 
f
a
c
e
t
s
Each facet covers the directions that are convex
combinations of three 
k
-DOP normal directions
 
C
o
n
s
t
r
u
c
t
i
n
g
 
t
h
e
 
A
p
e
x
 
P
o
i
n
t
 
Apex point for this facet is the intersection of the 
k
-DOP
planes that were generated using the shown normals
Lies on the 
k
-DOP surface iff corresponding 
k
-DOP faces meet
 
U
s
i
n
g
 
t
h
e
 
A
p
e
x
 
P
o
i
n
t
 
When fitting a bounding plane with normal in a given
facet of direction space, set the plane offset so that it
passes through the apex point for the facet
 
W
h
y
 
D
o
e
s
 
T
h
i
s
 
W
o
r
k
?
 
k
-DOP is an intersection of half-spaces 
 
Taking 
any
subset of 
k
-DOP planes yields a valid conservative bound
for the mesh
Taking three planes yields an infinite triangular pyramid
If we’re fitting a bounding plane, we can make it pass
through the apex of the pyramid – if it can bound the
pyramid at all, it will bound it there too
Plane bounds the pyramid, pyramid bounds the mesh 
plane bounds the mesh
 
S
u
m
m
a
r
y
 
o
f
 
t
h
e
 
M
e
t
h
o
d
 
Precalculation:
Construct a 
k
-DOP with normals according to tessellated cube
For each direction space facet, compute one apex point as the
intersection of three 
k
-DOP planes
Store these apex points, nothing else
To fit a bounding plane:
Find the facet that contains the plane normal direction
Fetch the apex point for the facet
Set plane offset so that it passes through the apex point
R
e
s
u
l
t
s
:
 
Q
u
a
l
i
t
y
 
R
e
s
u
l
t
s
:
 
S
p
e
e
d
 
For 
n
=8, tops out at ~1.5M vertices / ms on NVIDIA GTX 980
Precalculated data consumes 9 KB / mesh for 
n
=8
 
 
C
o
n
c
l
u
s
i
o
n
Don’t do this!
Do this
 
C
o
n
c
l
u
s
i
o
n
 
Mesh vs plane
 
Projection bounds
 
Object overlap
 
T
h
a
n
k
 
Y
o
u
 
Questions
Slide Note
Embed
Share

Discover advanced techniques for quickly finding optimal bounding planes with specific orientations in computer graphics applications such as ray tracing, world-space optimization, view frustum culling, and shadow mapping. Learn how to improve efficiency and precision in bounding volume hierarchy construction through innovative solutions.

  • Computer Graphics
  • Bounding Plane
  • Ray Tracing
  • Optimization
  • Efficiency

Uploaded on Aug 21, 2024 | 0 Views


Download Presentation

Please find below an Image/Link to download the presentation.

The content on the website is provided AS IS for your information and personal use only. It may not be sold, licensed, or shared on other websites without obtaining consent from the author. Download presentation by click this link. If you encounter any issues during the download, it is possible that the publisher has removed the file from their server.

E N D

Presentation Transcript


  1. Apex Point Map for Constant-Time Bounding Plane Approximation Samuli Laine Tero Karras NVIDIA

  2. The Problem How to quickly find a good bounding plane with a given orientation?

  3. Use Case 1: Ray Tracing and Rigid Motion Say we have a world-space BVH with leaves containing object ID + transformation matrix Each object has a pre-built BVH in model space When ray finds an object, it descends into per-model BVH

  4. Use Case 1: Ray Tracing and Rigid Motion When objects move and rotate, the world-space BVH needs to be rebuilt / refit, but per-object BVHs stay unchanged Very fast But: Where do we get the world-space AABBs for the transformed objects?

  5. The Nave Solution Take the object s model-space AABB Transform it along with the object Wrap a world-space AABB around it Declare victory Model space World space

  6. The Nave Solution Woefully conservative! Stats for Armadillo: Average = 94% larger surface area than for a tightly fit AABB Worst case = +169% surface area A spherical model is even worse Average = +125% AABB area Worst case = +179% AABB area This kills the world-space BVH

  7. A Better Solution Start with world- space AABB normals Take them to model space Query tight bounding plane offsets Apply in world space Model space World space

  8. Use Case 2: View Frustum Culling Both world-space AABB and transformed object-space AABB are suboptimal for view frustum culling What we really want to know is whether a bounding plane oriented along frustum plane is inside the frustum or not Eye

  9. Use Case 3: Per-Object Shadow Map Extents Directional light source Choosing projection extents based on object bounding box wastes shadow map resolution Tight bounding planes come to the rescue

  10. Use Case 4: Collision Detection Transformed object-space AABBs may intersect Tightly fit world-space AABBs may intersect But if you can guess a separating plane normal, it is very cheap to test Could try, e.g., vector between object centers

  11. Constraints If we want the bounding plane fit to be fast, precalculation is unavoidable Otherwise must loop over all* vertices Mesh needs to be static Except: See paper for extension to skinned meshes * Vertices on the convex hull would obviously be enough, but then we d need to precalculate the convex hull

  12. AABB: The Good The amount of precalculated data is small and constant The precalculation is fast and simple Fitting an arbitrarily oriented bounding plane is really fast

  13. AABB: The Bad An arbitrarily oriented bounding plane fit to an AABB can be extremely conservative HOWEVER Fitting an axis-aligned plane works fine (exact result) Fitting an almost axis-aligned plane is still okay-ish

  14. More Is More Why not precalculate a many- sided bounding volume? This is known as a k-DOP Intersection of half-spaces k is the number of plane normals AABB belongs to the 6-DOP family Determining the k plane equations for a mesh is easy and fast But

  15. The Trouble with k-DOPs Determining the vertices of the k-DOP surface is non- trivial, to say the least Known as the vertex enumeration problem in linear optimization circles 2D case looks deceptively simple, problems start at 3D

  16. k-DOP Surface Topology Is Not Fixed * C C B B A A * Except when it is (e.g., in case of AABBs)

  17. Apex Point Map Start with a k-DOP, but instead of trying to find the k-DOP surface vertices, find some other vertices These are what we call apex points They may be k-DOP surface vertices, but possibly aren t In addition, choose k-DOP normals carefully so that we can easily decide a single apex point to fit the bounding plane against Makes bounding plane construction extremely fast

  18. k-DOP Normals We choose the k-DOP normals to point at the vertices of a regularly tessellated cube With each face tessellated to n n squares, we get 6n2 + 2 normal directions In this figure, n = 8 k = 386

  19. k-DOP Normals The direction space is divided into triangular facets Each facet covers the directions that are convex combinations of three k-DOP normal directions

  20. Constructing the Apex Point Apex point for this facet is the intersection of the k-DOP planes that were generated using the shown normals Lies on the k-DOP surface iff corresponding k-DOP faces meet

  21. Using the Apex Point When fitting a bounding plane with normal in a given facet of direction space, set the plane offset so that it passes through the apex point for the facet

  22. Why Does This Work? k-DOP is an intersection of half-spaces Taking any subset of k-DOP planes yields a valid conservative bound for the mesh Taking three planes yields an infinite triangular pyramid If we re fitting a bounding plane, we can make it pass through the apex of the pyramid if it can bound the pyramid at all, it will bound it there too Plane bounds the pyramid, pyramid bounds the mesh plane bounds the mesh

  23. Summary of the Method Precalculation: Construct a k-DOP with normals according to tessellated cube For each direction space facet, compute one apex point as the intersection of three k-DOP planes Store these apex points, nothing else To fit a bounding plane: Find the facet that contains the plane normal direction Fetch the apex point for the facet Set plane offset so that it passes through the apex point

  24. Results: Quality

  25. Results: Speed For n=8, tops out at ~1.5M vertices / ms on NVIDIA GTX 980 Precalculated data consumes 9 KB / mesh for n=8

  26. Conclusion Do this Don t do this!

  27. Conclusion Eye Object overlap Projection bounds Mesh vs plane

  28. Thank You Questions

More Related Content

giItT1WQy@!-/#giItT1WQy@!-/#giItT1WQy@!-/#giItT1WQy@!-/#giItT1WQy@!-/#giItT1WQy@!-/#