Interactive Computer Graphics The Concept of a Halfspace

Y
Halfspace Infinite line
Lecture 4 f(x,y)<0 f(x,y) = 0
eg
Manipulation of Three Dimensional Objects x -y + 1 = 0

Halfspace
f(x,y)>0

Graphics Lecture 4: Slide 1 Graphics Lecture 4: Slide 2

The same idea extends to three dimensions Convex Objects

We can use the halfspace property for a number of

Plane Equation F(x,y,z) = 0
(a x + b y + c z + d = 0)
algorithms for manipulating graphics scenes.

We will consider first convex objects, and the first

Diagram 5.1
Planes and Halfspaces
algorithm is to determine whether an object is convex
or not.
For all points in
this halfspace
F(xi,yi,zi) <0 For all points in
this halfspace
F(xi,yi,zi) >0

Graphics Lecture 4: Slide 3 Graphics Lecture 4: Slide 4

Two Definitions of Convex Algorithm for determining if an object is convex

1. A line joining any two points on the boundary lies convex = true
inside the object. for each face of the object
{ find the plane equation of the face f (x,y,z) = 0
2. The object is the intersection of planar halfspaces. choose one object point (xi,yi,zi) not on the face
and find sign( f (xi,yi,zi) )
for all other points of the object
{ if (sign( f(xj,yj,zj) ) not = sign(f (xi,yi,zi) ) )
then convex = false
}
Graphics Lecture 4: Slide 5
}
Graphics Lecture 4: Slide 6

1
Testing for Convex Testing for Containment

A frequently encountered problem is to determine

whether a point is inside an object or not.

We need this for clipping algorithms

Graphics Lecture 4: Slide 7 Graphics Lecture 4: Slide 8

Algorithm for Containment Vector formulation

let the test point be [xt,yt,zt] The same test can be expressed in vector form.
contained = true
for each face of the object This avoids the need to calculate the Cartesian
{ find the plane equation of the face f (x,y,z) = 0 equation of the plane, if, in our data base we store the
choose one object point (xi,yi,zi) not on the face normal n vector to each face of our object.
and find sign( f (xi,yi,zi) )
if (sign( f(xt,yt,zt) ) not = sign(f (xi,yi,zi) ) )
then contained = false
}
Graphics Lecture 4: Slide 9 Graphics Lecture 4: Slide 10

Vector test for containment Normal vector to a face

Inner
Normal
The vector formulation does not require us to find the
One face of a
convex object
plane equation of a face, but it does require us to find
Contained if θ is acute
ie Cos(θ) is positive a normal vector to the plane.
n or n.(P-A) is positive
θ n.(P-A) = |n||P-A|Cos(θ)
(P-A) (same thing really since for plane ax + by +cz + d=0
A a normal vector is [a,b,c])
Diagram 5.2 Containment within
P a convex object

Point being
tested
Origin
Graphics Lecture 4: Slide 11 Graphics Lecture 4: Slide 12

2
Finding a normal vector But which normal vector points inwards?

The normal vector can be found from the cross

product of two vectors on the plane, say two edge
e2 e2
vectors e1 x e2

e2 e2 x e1
e1 e1

e2 X e1
e1

Graphics Lecture 4: Slide 13 Graphics Lecture 4: Slide 14

Checking the normal direction Problem Break

n
2 Faces of a A face of a convex object lies in the plane
Convex Object
3x+5y+7z +1 = 0 and a vertex is {-1,-1,1}
The normal vector is therefore n = {3,5,7}
(B-A)
A
1. If another vertex of the object is {1,1,1} determine
whether n is an inner or outer surface normal.
if n•(B-A) > 0 then n is (see fig 6.4)
B the inner surface normal
Origin
2. Determine whether the point {1,0,-1}is on the
inside or the outside of the face.
Graphics Lecture 4: Slide 15 Graphics Lecture 4: Slide 16

Solution 1 Solution 2

P-A = {1,1,1} - {-1,-1,1} Method 1:

= {2,2,0} The plane has equation 3x+5y+7z+1=0
n.(P-A) = 6 + 10 = 16 {-1,-1,1}
n= {3,5,7}
ie f(x,y,z) = 3x+5y+7z+1
θ
n.(P-A) is positive, (P-A)
A
θ is acute {1,1,1}
For the internal point {1,1,1} f(1,1,1) = 16
n is an inner normal P For the test point {1,0,-1} f(1,0,-1) = -3
The signs are different, so the test point is on the
Origin
outside

Graphics Lecture 4: Slide 17 Graphics Lecture 4: Slide 18

3
Solution 3 Clipping

Method 2: Containment is an important property used in clipping

The inner surface normal is n = {3,5,7} algorithms.
for the test point P = {1,0,-1} and vertex A={-1,-1,1}
P-A = {2,1,-2} Clipping is used to remove unwanted parts of a
n.(P-A) = -3 graphics scene before drawing.
Thus the angle to the normal is > 90
It can be applied in computer aided design, and
graphics scene design.
The point is on the outside

Graphics Lecture 4: Slide 19 Graphics Lecture 4: Slide 20

Clipping a line to a convex polyhedron Clipping algorithm

The algorithm checks the line against every face of

the convex polyhedron.
P2

P4 It determines whether the end points of the line are on

P3
the inside or the outside of the face
Given a line segment P1 to P2
determine the part of the line
P1 inside a convex object,
ie P3 to P4 This can be done by the halfspace or the dot product
with the inner normal as before.

Graphics Lecture 4: Slide 21 Graphics Lecture 4: Slide 22

Case 1: Both P1 and P2 are on the outside Case 2: Both P1 and P2 are on the inside

The line is completely clipped (no part of it is inside There is no new information.
the polyhedron)
If there are more faces to test the algorithm continues
The algorithm terminates to the next face.

Otherwise the line is completely inside the volume.

Graphics Lecture 4: Slide 23 Graphics Lecture 4: Slide 24

4
Case 3: P1 is outside and P2 is inside Case 3: P2 is outside and P1 is inside

Compute the intersection between the line and plane. This is equivalent to case 3 with P1 and P2 exchanged
for any vector p lying on the plane n.p = 0
let the intersection point be µi P2 + (1- µi)P1
if A ia a vertex of the object a vector on the plane is
µi P2 + (1- µi)P1 - A
thus n.(µi P2 + (1- µi)P1 - A) = 0
we can solve this for µi and hence find the point of
intersection
Replace P1 with the intersection

Graphics Lecture 4: Slide 25 Graphics Lecture 4: Slide 26

Clipping to a viewing volume Concave Objects

Containment and clipping can also be carried out with

concave objects.

Most algorithms are based on the ray containment

test.
Back clipping plane
Window (front clipping plane)

The visible parts of a graphics scene are bounded by six planes.

For efficient computation all invisible parts should be clipped

Graphics Lecture 4: Slide 27 Graphics Lecture 4: Slide 28

The Ray test in two dimensions Calculating intersections with rays

Ray Rays have equivalent equations to lines, but go in

Test Point
only one direction. For test point T a ray is defined as

R = T + µ d µ>0
Polygon
We choose a simple to compute direction eg

Find all intersections between the ray and the polygon edges.
If the number of intersections is odd the point is contained d = [1,0,0]

Graphics Lecture 4: Slide 29 Graphics Lecture 4: Slide 30

5
Valid Intersections Extending the ray test to 3D
Line segment
P = V2 + ν (V1 - V2)

V1
Test
Ray point
T P = T + µ d (d = [1,0])

V2 Intersection A ray is projected in any direction.

T + µ d = V2 + ν (V1 - V2)
Solve for ν and µ If the number of intersections with the
Valid intersection if object is odd, then the test point is inside
µ>0, 0<=ν<1

Graphics Lecture 4: Slide 31 Graphics Lecture 4: Slide 32

3D Ray test The plane of a face

There are two stages: Unfortunately the plane of a face does not in general
line up with the Cartesian axes, so the second part is
1. Compute the intersection of the ray with the plane of not a two dimensional problem.
each face.

However, containment is invariant under

2. If the intersection is in the positive part of the ray (µ>0)
orthographic projection, so it can be simply reduced
check whether the intersection point is contained in the
face. to two dimensions.

Graphics Lecture 4: Slide 33 Graphics Lecture 4: Slide 34

Clipping to concave volumes Splitting a volume into convex parts

Find every intersection of the line to be clipped with

the volume.

This divides the line into one or more segments.

Test a point on the first segment for containment

Adjacent segments will be alternately inside and out.

If all the object vertices lie on one
side of the plane of of a face, we
proceed to the next face
Graphics Lecture 4: Slide 35 Graphics Lecture 4: Slide 36

6
 If the plane of a face cuts the object: Split the Object
New Face
New Face

Split Face Split Face Repeat on all concave sub parts

Graphics Lecture 4: Slide 37 Graphics Lecture 4: Slide 38

Vj Ray, Pi + µ(Pb-Pi)

Vi Pb

Vl
Diagram 5.7
Pa
Vk Containment in 2D
Pi

Vm

Graphics Lecture 4: Slide 39