COMP3421
COMP3421
Vector geometry, Clipping
Transformations
• We specify objects in model co-ordinates
• Transform them into world co-ordinates
• Transform the world into eye/camera-
coordinates
• We represent our vertices/points as 1D
Matrices in homogeneous co-ordinates
• We multiply by matrices to transform
them
Homogenous
coordinates
We can use a single notation to describe
both points and vectors.
Homogenous coordinates have an extra
dimension representing the origin:
Includes Origin Does not include origin
Points and vectors
We can add two vectors to get a vector:
We can add a vector to a point to get a new
point:
We cannot add two points.
Coordinate frames
We can now think of a coordinate frame in
terms of vectors.
A 2D frame is defined by:
• an origin: ϕ
• 2 axis vectors: i, j
i
j
ϕ
Points
A point in a coordinate frame can be
described as a displacement from the
origin:
i
j
ϕ
2j
2i 3i
P = 3i + 2j + ϕ
Transformation
To convert P to a different coordinate frame,
we just need to know how to convert i, j
and ϕ.
ij
ϕ
i’
j’
ϕ’
Transformation
So in local co-ordinates if P was (0,1),
given
ij
ϕ
i’
j’
ϕ’
P(global) = 0i + 1j + ϕ
= 0(0.4i’ + 0.4j’) +
1(-0.4i’ + 0.4j’) +
1i’ + 1j’ + ϕ’
= 0.6i’ + 1.4j’ + ϕ’
Transformation
So in local co-ordinates if P was (3,2),
given
ij
ϕ
i’
j’
ϕ’
P(global) = 3i + 2j + ϕ
= 3(0.4i’ + 0.4j’) +
2(-0.4i’ + 0.4j’) +
1i’ + 1j’ + ϕ’
= 1.4i’ + 3j’ + ϕ’
Transformation
These transformations are much easier to
represent as a matrices:
P(global)
1.4
3
2
Affine transformations
Transformations between coordinate
frames can be represented as matrices:
Matrices in this form (note the 0s with the 1
at the end of the bottom row) are called
affine transformations .
Affine transformations
Similarly for vectors:
Basic transformations
All affine transformations can be expressed
as combinations of four basic types:
• Translation
• Rotation
• Scale
• Shear
Affine transformations
Affine transformations preserve straight
lines:
They maintain parallel lines
They maintain relative distances on lines (ie
midpoints are still midpoints etc)
They don’t always preserve angles or area
point vector
2D Translation
To translate the origin to a new point ϕ.
p2
ϕ
p1
2D Translation
To translate the origin to a new point ϕ.
ϕ
q1
q2
2D Translation
In this example we translated by (1,0.5)
then plotted the point
P = (0.5,0.5) in the local frame.
We can see that the global co-ordinates
would be (1.5,1)
ϕ
q1
q2
2D Translation
2D Translation
Note: translating a vector has no effect.
2D Rotation
To rotate a point about the origin:
p1
p2
2D Rotation
To rotate a point about the origin:
q1
q2
2D Rotation
Likewise to rotate a vector:
2D Scale
To scale a point by factors (sx, sy) about
the origin:
p1
p2
2D Scale
To scale a point by factors (sx, sy) about
the origin:
q2
q1
2D Scale
Likewise to scale vectors:
Exercise
What would the matrix for scaling -1 in the x
and y direction look like?
What would the matrix for rotating by 180
degrees look like?
Solution
Shear
Shear is not very useful most of the time.
It can occur when you scale axes non-
uniformly and then rotate.
It does not preserve angles.
Usually it is not something you want.
It can be avoided by always scaling
uniformly.
Horizontal:
Vertical:
Shear
2D Shear
Horizontal:
Vertical:
Shear in OpenGL
No shear command in opengl.
Can use gl.glMultMatrixf to set up any
matrix.
Matrices are in column major order.
See ShearTransformationMatrix.java
for more details
Composing
transformations
We can combine a series of
transformations by post-multiplying their
matrices. The composition of two affine
transformations is also affine.
Eg: Translate, then rotate, then scale:
In OpenGL
gl.glMatrixMode(GL2.GL_MODELVIEW);
//Current Transform (CT) is the MODELVIEW
//Matrix
gl.glLoadIndentity();
//CT = identity matrix (I)
gl.glTranslated(dx, dy, 0);
//CT = IT
gl.glRotated(theta, 0, 0, 1);
//CT = ITR
gl.glScaled(sx, sy, 1);
//CT = ITRS
In OpenGL
gl.glBegin(GL2.GL_POINTS);
{
gl.glVertex2d(px, py);
//Point drawn at Q = CT P
// Q = ITRS P
}
gl.glEnd();
Exercise
What would the value of the current
transform be after the following?
gl.glMatrixMode(GL2.GL_MODELVIEW);
gl.glLoadIdentity();
gl.glTranslated(1,2,0);
gl.glRotated(90,0,0,1);
Solution
CT = I
I
1 0 0
0 1 0
0 0 1
Solution
Solution
Solution
Solution
CT = ITR
IT R ITR
1 0 1
0 1 2
0 0 1
0 −1 0
1 0 0
0 0 1
=
0 −1 1
1 0 2
0 0 1
Exercise
Suppose we continue from our last
example and do the following
gl.glPushMatrix();
gl.glScaled(2,2,1);
//1. What is CT now?
gl.glPopMatrix();
//2. What is CT now?
Solution
CT = ITRS
*ITR S ITRS
0 −1 1
1 0 2
0 0 1
2 0 0
0 2 0
0 0 1
=
0 −2 1
2 0 2
0 0 1
*ITR was pushed onto the stack so once
we pop it gets restored to ITR
Decomposing
transformations
Every 2D affine transformation can be
decomposed as:
If scaling is always uniform in both axes,
the shear term can be eliminated:
Decomposing
transformations
To decompose the transform, consider the
matrix form:
axes origin
Decomposing
transformations
Assuming uniform scaling and no shear
Note: arctan(i1,i2) is arctan(i2/i1) aka tan-1(i2/i1)
adjusting for i1 being 0. If i1 == 0 (and i2 is not) we
get 90 degrees if y is positive or -90 if y is negative.
Example
Exercise
Solution
Exercise
Suppose my parent in a scene graph had
the following transformations:
Translate (2,3), Rotate 30, Scale 1.5
(assume uniform scaling)
And my transformations are:
Translate(-1,4), Rotate 15, Scale 3
What is the translation of my co-ordinate
frame? What is the rotation? Scale?
Solution
Solution
Solution
However, the rotation is 45 degrees. Which
IS the same as adding together the parent
and child rotations
The scale is 4.5, which IS the same as
MULTIPLYING the parent and child scales.
Note: This only works if we assume uniform
scaling and only TRS transformations
Inverse
Transformations
If the local-to-global transformation is:
then the global-to-local transformation is
the inverse:
Inverse
Transformations
Inverses are easy to compute:
Translation: MT(dx,dy) = MT
-1(-dx,-dy)
Rotation: MR (theta) = MR
-1(-theta)
Scale: Ms(sx,sy) = Ms
-1(1/sx,1/sy)
Shear: MH(h) = MH
-1 (-h)
World To Local
Exercise
Suppose the following transformations had
been applied:
gl.glTranslated(3,2,0);
gl.glRotated(-45,0,0,1);
gl.glScaled(0.5,0.5,1);
What point in the local co-ordinate frame
would correspond to the world co-ordinate
Q (2,-1)?
Solution
Solution
Solution
–
Assignment
ROOT
/ \
Table Lego Man
/ \
Cup Lego Man Hand
Assignment Change
Parent
ROOT
/ \
Table Lego Man
\
Lego Man Hand
\
Cup
Linear combinations
Any equation of the form:
Affine combinations
A linear combination where:
Affine Combinations
Affine Combinations
If we have an affine combination of 2 points
a0P + a1Q
We know that a0 + a1 = 1
so a0 = 1 – a1
Therefore we can rewrite it as:
(1 – a1) P + a1 Q or
P + a1 ( Q – P)
Lerping
We often use this to do linear interpolation
between points:
lerp(P,Q,t) = (1-t) P + tQ
P
Q
lerp(P, Q, 0.3)
Lerping Exercise
Using linear interpolation, what is the
midpoint between P(4,9) and Q=(3,7).
Lerping Solution
Using linear interpolation, what is the
midpoint between P(4,9) and Q=(3,7).
Would be at t = 0.5 so
lerp(P,Q,t) = (1 – 0.5) (4,9) + (0.5)(3,7)
= (2,4.5) + (1.5,3.5)
= (3.5,8)
Lines
Parametric form:
L(t) = P + tv
v = Q – P
Point-normal form in 2D:
P
Q
t < 0 0 < t < 1 t >1
P
n
L(t)
L
Planes in 3D
Parametric form:
Point-normal form:
n
P C
Line intersection
Two lines
Solve simultaneous equations:
A + (B – A) t = C + (D – C) u
Line Intersection
Example
A = (0,3) B = (12,7)
C = (2,0) D = (7,20)
LAB(t) = (0,3) + (12-0,7-3)t = (0,3) + (12,4)t
LCD(u) = (2,0) + (7-2,20-0)u = (2,0) + (5,20)u
Intersect for values of t and u where
LAB(t) = LCD(u)
Line Intersection
Example…
(0,3) + (12,4)t = (2,0) + (5,20)u
In 2D that is 2 equations, one for x and y
0 + 12t = 2 + 5u
3 + 4t = 0 + 20u (multiply by 3 and subtract)
Gives: -9 = 2 – 55u, so u = 0.2
Substitute u into equation 1 gives t = 0.25
Substitute into either line equation to get
intersection at point (3,4)
Line Intersection
Example 2
Find where the L(t) = A + ct intersects with
the line n.(P-B) = 0 where
A(2,3), c = (4,-4), n = (6,8), B=(7,7)
(6,8).((A + ct) – (7,7)) = 0
(6,8).((2,3) + (4,-4) t – (7,7)) = 0
(6,8).( 2+4t-7, 3-4t-7) = 0
(6,8).(-5+4t, -4-4t) = 0
Line Intersection …
(6,8).(-5+4t,-4-4t) = 0
6(-5+4t) + 8(-4-4t) = 0
-30 + 24t -32 – 32t = 0
t = 62/-8 = -7.75
P = A + ct = (2, 3) + (4, -4)*(-7.75)
= (-29, 34)
The graphics pipeline
Projection
transformation
Illumination
Clipping
Perspective
division
ViewportRasterisation
Texturing
Frame
buffer
Display
Hidden
surface
removal
Model-View Transform
Model
Transform
View
Transform
Model
User
Clipping
The world is often much bigger than the
camera window. We only want to render
the parts we can see.
Window
Clipping
The world is often much bigger than the
camera window. We only want to render
the parts we can see.
Window
Clipping algorithms
There are a number of different clipping
algorithms:
• Cohen-Sutherland (line vs rect)
• Cyrus-Beck (line vs convex poly)
• Sutherland-Hodgman
(poly vs convex poly)
• Weiler-Atherton (poly vs poly)
Clipping lines to an axis-aligned rectangle.
Cohen-Sutherland
Trivial accept/reject
accept: both
ends inside
reject: both ends
on same side (top)more
testing
Labelling
00001000 0010
01001100 0110
00011001 0011
Label ends
Outcode(x, y):
code = 0;
if (x < left) code |= 8; if (y > top) code |= 4;
if (x > right) code |= 2;
if (y < bottom) code |= 1; return code; Clip Once ClipOnce(px, py, qx, qy): p = Outcode(px, py); q = Outcode(qx, qy); if (p == 0 && q == 0) { // trivial accept } if (p & q != 0) { // trivial reject } Clip Once // cont... if (p != 0) { // p is outside, clip it } else { // q is outside, clip it } Clip Loop Clip(px, py, qx, qy): accept = false; reject = false; while (!accept && !reject): ClipOnce(px, py, qx, qy) Clipping a point A P Q Using similar triangles: Clipping a point A P(-1.5,-2) Q(0,0) Assume bottom left of clipping rectangle is (-1,-1) Clipping a point A P(-1.5,-2) Q(0,0) Assume bottom left of clipping rectangle is (-1,-1) ax = -1 ay = -2+ (0.5)(2/1.5) Clipping a point A(-1,-1.333) P(-1.5,-2) Q(0,0) Assume bottom left of clipping rectangle is (-1,-1) ax = -1 ay = -2+ (0.5)(2/1.5) Case needing 4 Clips P1 P Q P2 Q1 Q2 Cyrus Beck Clipping a line to a convex polygon. Edge Intersection Parametric line (line that we are clipping): Point normal line (edge): Collide when: A B c n R(t) Hit time / point Entering / exiting Assuming all normals point out of the polygon: c n c n entering exiting Cyrus-Beck Initialise tin to 0 and tout to 1 Compare the line to each edge of the (convex) polygon. Compute thit for each edge. Keep track of maximum tin Keep track of minimum tout. Example tin tout 0 1 P0 P1 P2 P3P4 Example tin tout 0 1 P0 P1 P2 P3P4 Example tin tout 0 1 0.1 1 P0 P1 P2 P3P4 Example tin tout 0 1 0.1 1 P0 P1 P2 P3P4 Example tin tout 0 1 0.1 1 0.1 0.9 P0 P1 P2 P3P4 Example tin tout 0 1 0.1 1 0.1 0.9 P0 P1 P2 P3P4 Example tin tout 0 1 0.1 1 0.1 0.9 0.1 0.85 P0 P1 P2 P3P4 Example tin tout 0 1 0.1 1 0.1 0.9 0.1 0.85 P0 P1 P2 P3P4 Example tin tout 0 1 0.1 1 0.1 0.9 0.1 0.85 0.1 0.85 P0 P1 P2 P3P4 Example tin tout 0 1 0.1 1 0.1 0.9 0.1 0.85 0.1 0.85 P0 P1 P2 P3P4 Example tin tout 0 1 0.1 1 0.1 0.9 0.1 0.85 0.1 0.85 0.2 0.85 P0 P1 P2 P3P4 Example tin tout 0 1 0.1 1 0.1 0.9 0.1 0.85 0.1 0.85 0.2 0.85 P0 P1 P2 P3P4 Point in Polygon We can use a similar approach to see if a point is in a polygon. For any ray from the point: • Check whether the ray intersects with each edge of the polygon • Count the number of crossings with the polygon • If there is an odd number of crossings the point is inside Point in polygon Point in polygon 1 6 2 3 2 3 Difficult points Solution Only count crossings at the lower vertex of an edge. don't count 1 0 2 1 count Point in polygon 2 0 1 10 1 1 2 3 0 2 2 0 Computational Geometry Computational Geometry in C, O'Rourke http://cs.smith.edu/~orourke/books/compge om.html CGAL Computational Geometry Algorithms Library http://cgal.org/ http://cs.smith.edu/~orourke/books/compgeom.html http://cgal.org/