程序代写代做代考 algorithm Java COMP3421

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/