Ross Ptacek Computer and Information Sciences University of

Ross Ptacek Computer and Information Sciences University of

Ross Ptacek
Computer and Information Sciences
University of Alabama at Birmingham
[email protected]

Controlling the entire path of a virtual camera

John K. Johnstone
Computer and Information Sciences
University of Alabama at Birmingham
[email protected]

The
The work
work of
of both
both authors
authors was
was partially
partially supported
supported by
by the
the NSF
NSF under
under grant
grant CCR-0203586.
CCR-0203586.

Creating a path
Introduction
Introduction
In computer animation, the path of a virtual camera
through the scene is often controlled interactively.
However, it is also reasonable to define the desired
camera path by some keyframes that the camera must
pass through. This is a reasonable model in an
architectural walkthrough, for example, where a tour of
the building is desired, which could be predefined. The
keyframes can be generated automatically by a higher
level motion planner, or designed by hand.
A major issue in animation is that the camera path may
collide with the scene, resulting in unattractive
cutthroughs. An advantage of the keyframe approach
to camera control is that collisions can be detected and
avoided before the motion is begun. Moreover, optimal
smooth motions can be planned, both globally and
locally.

Keyframes
Keyframes
Keyframes are positions and orientations that the
camera is constrained to pass through.
They can be thought of as snapshots taken by the
camera as it moves along the desired path.
We have to choose how the camera will transition
from keyframe to keyframe.

Keyframes
Keyframes can
can also
also be
be
represented
represented with
with quadrilaterals
quadrilaterals
as
Why
as shown
shown here.
here.
Why
quadrilaterals?
quadrilaterals? Read
Read on!
on!

This
This figure
figure shows
shows aa sampling
sampling of
of frames
frames from
from aa flythrough.
flythrough. A
A key
key step
step in
in the
the construction
construction of
of aa natural
natural flythrough
flythrough is
is the
the collision
collision detection,
detection, and
and collision
collision
correction,
correction, of
of the
the near
near quadrilateral
quadrilateral of
of the
the view
view frustum
frustum with
with the
the scene.
scene.

Camera
Camera model
model and
and collision
collision detection
detection

Tracking
Tracking the
the corners
corners

The visible part of a scene is defined by a view frustum, a
rectangular cone bounded by near and far clipping planes.
It is natural for objects to penetrate the back or sides of the
view frustum, as the object moves out of our field of vision.
However, objects that penetrate the near clipping plane are
unnatural, creating ugly cutaways.

Camera positions are interpolated using a cubic B-spline
B(t). This represents the position of the center of the
near quadrilateral.
Camera orientations are interpolated using a rational
quaternion spline Q(t).
Quaternions are points on the unit sphere in 4-space.
A B-spline is interpolated through these points,
constrained to the sphere.
A rational method is more efficient and robust.
A corner of the near quadrilateral at time t is calculated as
follows:
V = vector from the center of the near quadrilateral to
a corner.
Rotate V by Q(t), then translate by B(t).
We want to find the entire path of a corner.
Using a result from Johnstone and Williams 1995, we find
a rational B-spline representing the path of each corner
curve.

The near boundary of the
view frustum is a quadrilateral
in the near clipping plane,
called the near quadrilateral.
We need to track the near
quadrilateral as the camera
moves along its path, so that
we can find its collisions with
the scene.
It suffices to track its four
corners.

The
The near
near clipping
clipping plane
plane intersects
intersects part
part of
of
the
the scene,
scene, creating
creating an
an ugly
ugly cutaway
cutaway

We find problem areas where collisions occur
and push the path away from them. The path is
pushed away from the collision by adding new
keyframes. There are three steps, as follows.
1. Find intervals of the swept camera volume that
intersect the scene.
2. Measure how deeply the near quadrilateral
penetrates the scene over each interval.

Determining
Determining a
a New
New Keyframe
Keyframe

Determining
Determining a
a New
New Keyframe
Keyframe

Consider a collision interval (si,sf).
We consider the frame at the middle of the collision
interval, identify the direction and depth of the
collision, and use this information to define a new
keyframe nearby that is hopefully collision-free.
The parameter value of the inserted keyframe is
smid = (sf si) / 2.
The orientation of the inserted keyframe is Q(smid).

The position of the inserted keyframe is
Finding d:
B(smid) + d * v, where
For each bad vertex of C(smid),
B(smid) = position at center of interval
intersect the two adjacent edges of
the near quadrilateral and record the
d = approximate depth of intersection
distance to the closest intersection
v = a vector away from the
on each edge.
intersections
Define the vertex depth to be the
Finding v:
maximum of these two distances.
Intersect the four line segments from
Define d to be the maximum of
the center of C(smid) to the vertices of
these vertex depths.
this near quadrilateral with the scene. This extra keyframe may still intersect
If a line segment intersects the
some scene geometry, in which case
scene, classify the associated vertex
we will have to repeat the procedure.
good, otherwise bad.
Multiple keyframes may have to be
v is the normalized sum of vectors
inserted over an interval to completely
from the center of C(smid) to each good
fix it.
corner.

3. Insert a new keyframe in the middle of each
parameter interval.
Finding
Finding Collision
Collision Intervals
Intervals
Sample the swept surface to triangles Tp.
Annotate each triangle of Tp with a parameter value
from C(t).
Each collision interval is found by binary search
with respect to the parameters, at both ends of the
interval.
This gives us a series of parameter intervals over
which there is continuously a collision.
We add a new keyframe in the center of each
collision interval, as described below.
Once this keyframe has been added, the interval is
rescanned to make sure that the new path is
collision-free. If necessary, additional keyframes
are recursively added over the interval.
Typically fewer than three iterations are required.

There are four curves representing the paths
of the four corners of the near quadrilateral
during the motion, which we call corner
curves.
A ruled surface is lofted between adjacent
corner curves.
These four lofted surfaces bound the swept
volume of the near quadrilateral.
We want to detect
collisions of the scene
with this volume, and
correct them.
Let C(t) be the
parameterized near
quadrilateral represented
by this swept volume.

The
The swept
swept volume
volume defined
defined by
by the
the near
near
quadrilateral
quadrilateral of
of the
the view
view frustum.
frustum.

Results

Path Correction
Detecting
Detecting Collisions
Collisions

Swept
Swept volume
volume of
of the
the near
near quadrilateral
quadrilateral

Before
Before

After
After

Green
Green lines:
lines: Corner
Corner curves
curves
Red
Red line:
line: B(t)
B(t)
Numbers
Numbers indicate
indicate keyframes
keyframes
Black
Black quadrilaterals
quadrilaterals indicate
indicate
the
the near
near quadrilateral
quadrilateral collision
collision
intervals
intervals in
in the
the original
original path.
path.

The
The corner
corner curves
curves (represented
(represented in
in green)
green) show
show the
the
camera
camera running
running into
into the
the wall
wall ahead.
ahead.

After
After collision
collision correction,
correction, the
the corner
corner curves
curves avoid
avoid
the
the wall,
wall, while
while still
still interpolating
interpolating the
the user-specified
user-specified
keyframes.
keyframes.
The
The correction
correction took
took two
two iterations
iterations to
to completely
completely
correct
correct this
this segment,
segment, as
as the
the first
first iteration
iteration fixed
fixed the
the
original
original collision
collision but
but introduced
introduced aa new
new one.
one.

The
The parameter
parameter finding
finding algorithm.
algorithm. Red
Red lines
lines represent
represent the
the
true
true beginning
beginning and
and end
end of
of the
the collision.
collision. The
The triangles
triangles are
are
triangles
triangles from
from one
one side
side of
of C(t).
C(t). The
The number
number indicates
indicates
order
order when
when sorted
sorted by
by parameter
parameter value
value of
of C(t).
C(t).

The
The black
black rectangle
rectangle is
is the
the near
near quadrilateral
quadrilateral
C(s
). The grey lines represent pieces of scene
C(smid
mid). The grey lines represent pieces of scene
geometry
geometry that
that intersect
intersect the
the quadrilateral.
quadrilateral. Lines
Lines are
are
intersected
intersected to
to determine
determine good
good (green)
(green) and
and bad
bad
(red)
(red) vertices.
vertices.

We tested the algorithm on the U.C. Berkeley Walkthrough Groups Soda Hall WALKTHRU Model.
The entire algorithm has been implemented in C++.
Each collision interval took at most 3 iterations to correct.
References
References and
and Acknowledgments
Acknowledgments
J.K. Johnstone and J.P. Williams (1995) A Rational Model of the Surface Swept by a Curve. Computer
Graphics Forum 14(3), 7788.
We thank the U.C. Berkeley Walkthrough Group for the U.C. Berkeley Soda Hall WALKTHRU Model.

Recently Viewed Presentations

  • Eschatology, a Broad Perspective From Genesis to Revelation

    Eschatology, a Broad Perspective From Genesis to Revelation

    Alexander the Great (vv3-4); swept through Asia Minor, Syria, Egypt, and Mesopotamia (334-331) ... May 29 Hosea and Israel's Relationship with God Clint. Jun 5 IBC Band - No Morning Song. Jun 12 Ezekiel 37, The Valley of Dry Bones...
  • EDU Agreement Briefing - Microsoft HiEd

    EDU Agreement Briefing - Microsoft HiEd

    Microsoft in Higher Education Conference. Bellevue, WA. October 15, 2018. Agenda. Solution. Trends. Agreement. Outcomes. Feedback. Refinement. ... Organizations will need to balance the flood of new customer data available with securing and maintaining user trust in order to deliver...
  • 4/23-4/25 - Schoolwires

    4/23-4/25 - Schoolwires

    is a 14-line lyric poem, usually written in iambic pentameter. A . tragedy . is dramatic play that tells the story of a character, usually of a noble class, who meets a ultimately and unhappy death or downfall, often because...
  • Chapter 28 Stars and Galaxies

    Chapter 28 Stars and Galaxies

    Shift of the emission spectra can indicate if the object is moving towards or away from Earth. ... Parallax . an apparent change in an object's positiondue to a change in the observer's position. Parsec short for "parallax second" equal...
  • Psychology - Gordon State College

    Psychology - Gordon State College

    Definition of Consciousness. Learning Objective 4.1 Define what it means to be conscious. Consciousness. A person's awareness of everything that is going on around him or her at any given moment . Generated by set of action potentials in communication...
  • Education & Training

    Education & Training

    Medical Knowledge Fiesta (MKF) The College, in collaboration with the African Partners Medical (APM) and the Ghana Physicians and Surgeons Foundation (GPSF) have been organising this yearly conference since 2011. It is a 4 day intensive conference and brings together...
  • Cotton Results - World Bank

    Cotton Results - World Bank

    Chinese and Indian producers; EU and US consumers Rice Mature but important market—staple food in Asia, small-holder production, potential trade growth World average tariffs of 43% (217% for short/medium grain rice).
  • Thermochemistry (4 lectures)

    Thermochemistry (4 lectures)

    Shriver & Atkins, 'Inorganic Chemistry', OUP, 4th Edition, 2006 Week 4: Electronic Spectroscopy Jahn-Teller effect Electronic spectra of multi-electron atoms Nephelauxetic effect and the spectrochemical series Selection rules Charge transfer transitions Week 5: Bonding in Complexes, Metalloproteins and Materials π-Donor...