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.