程序代写代做代考 algorithm PowerPoint Presentation

PowerPoint Presentation

5. Barycentric Rasterisation

Dr. Hamish Carr

COMP 5812M: Foundations of Modelling & Rendering
Dot Product
Length of a vector:
Angle between vectors: =

Test for right angles:
Projection onto a line:
Distance to a line:

COMP 5812M: Foundations of Modelling & Rendering

COMP 5812M: Foundations of Modelling & Rendering

Equations of Lines
Explicit Form:
Implicit Form:
Normal Form:
Parametric Form:
We use normal & parametric forms

COMP 5812M: Foundations of Modelling & Rendering

COMP 5812M: Foundations of Modelling & Rendering
Explicit Form
y is a function of x:

Does this work for vertical lines?

COMP 5812M: Foundations of Modelling & Rendering

COMP 5812M: Foundations of Modelling & Rendering
Implicit Form
A form that allows vertical lines
but harder to draw
Any (x,y) that satisfies:

is on the line

COMP 5812M: Foundations of Modelling & Rendering

COMP 5812M: Foundations of Modelling & Rendering
Normal Form
Rewrite to use a dot product

If we can do dot product with points

COMP 5812M: Foundations of Modelling & Rendering

COMP 5812M: Foundations of Modelling & Rendering
Distance to a Line

O

d
What is d?

d is the distance from the origin to the line
c is the distance scaled by the length of the normal

COMP 5812M: Foundations of Modelling & Rendering

COMP 5812M: Foundations of Modelling & Rendering
Which side of a line
+: in direction of normal
0: on line
-: away from normal

Testing which side a point is on is easy with the normal form

COMP 5812M: Foundations of Modelling & Rendering

COMP 5812M: Foundations of Modelling & Rendering
Drawing A Line
Loop through explicit form:
for (x = x0; x < x1; x++) { y = mx + c; setPixel(x, y); } COMP 5812M: Foundations of Modelling & Rendering COMP 5812M: Foundations of Modelling & Rendering Bresenham’s Algorithm rise = y1 - y0; run = x1 - x0; if (run > 0)
if (rise > 0)
if (run > rise)
for (x = x0; x < x1; x++) { y = (rise/run) x + c; setPixel(x, y); } else for (y = y0; y < y1; y++) { x = (run/rise) y + b; setPixel(x, y); } else if (run > -rise)
for (x = x0; x < x1; x++) { y = (rise/run) x + c; setPixel(x, y); } else for (y = y1; y > y0; y–) {
x = (run/rise) y + b;
setPixel(x, y); }
&c., &c., &c.

COMP 5812M: Foundations of Modelling & Rendering

COMP 5812M: Foundations of Modelling & Rendering
Colour Interpolation
What if we want a coloured gradient?
At p, the line is 100% red, 0% blue
At q, the line is 0% red, 100% blue
In between, it varies smoothly
This process is called interpolation

COMP 5812M: Foundations of Modelling & Rendering

COMP 5812M: Foundations of Modelling & Rendering
Implicit Form
We want to draw a line 1 pixel wide
all pixels within 0.5 pixels of line
we know how to measure distance
But this draws a line, not a segment
for (x = xMin; x < xMax; x++) for (y = yMin; y < yMax; y++) if (abs(distance((x, y), (x0, y0), (x1, y1))) < 0.5) setPixel(x, y); COMP 5812M: Foundations of Modelling & Rendering COMP 5812M: Foundations of Modelling & Rendering Parametric Form This is the easiest one yet! Walk along the line one step at a time: for (t = 0.0; t <= 1.0; t += 0.001) { point_r = point_p + (point_q - point_p) * t; setPixel(round(r_x), round(r_y)); } COMP 5812M: Foundations of Modelling & Rendering COMP 5812M: Foundations of Modelling & Rendering Linear Interpolation Assume parametric line Let f(t) be the colour we use a straight line f changes linearly: COMP 5812M: Foundations of Modelling & Rendering COMP 5812M: Foundations of Modelling & Rendering Interpolating Colour Easiest in parametric form: for (t = 0.0; t <= 1.0; t += 0.001) { point_r = point_p + (point_q - point_p) * t; colour = colour_p + (colour_q - colour_p) * t; setColour(colour); setPixel(round(r_x), round(r_y)); } COMP 5812M: Foundations of Modelling & Rendering COMP 5812M: Foundations of Modelling & Rendering Triangles Defined by 3 points: Or by 3 lines Drawing three lines is easy But what about filled triangles? Start with equations of triangles COMP 5812M: Foundations of Modelling & Rendering COMP 5812M: Foundations of Modelling & Rendering Explicit Form For any x, specify valid y Assumes B is above AC COMP 5812M: Foundations of Modelling & Rendering COMP 5812M: Foundations of Modelling & Rendering Explicit Form, II If B is below AC: COMP 5812M: Foundations of Modelling & Rendering COMP 5812M: Foundations of Modelling & Rendering Raster Scan Algorithm Algorithm scans one line at a time raster scan (raster is Latin for a rake) scan conversion of triangles to pixels COMP 5812M: Foundations of Modelling & Rendering COMP 5812M: Foundations of Modelling & Rendering Explicit Algorithm Sort A, B, C so Ax < Bx < Cx Find slopes mAB, mAC, mBC, Find y-intercepts cAB, cAC, cBC for (x = Ax; x <= Bx; x++) { // for each column yMin = mAC * x + cAC; yMax = mAB * x + cAB; if (yMin < yMax) swap(yMin, yMax); for (y = yMin; y <= yMax; y++) setPixel(x,y); } // for each column Also called linewise scan or raster scan usually loops horizontally, not vertically COMP 5812M: Foundations of Modelling & Rendering COMP 5812M: Foundations of Modelling & Rendering Linewise Interpolation To compute f(G): Interpolate f(E) from f(A), f(B) Interpolate f(F) from f(A), f(C) Interpolate f(G) from f(E), f(F) Perform for each of R,G,B COMP 5812M: Foundations of Modelling & Rendering COMP 5812M: Foundations of Modelling & Rendering Implicit / Normal Form Based on normal form of lines: Also known as the half-plane test COMP 5812M: Foundations of Modelling & Rendering COMP 5812M: Foundations of Modelling & Rendering Winding Order Inside depends on the winding order which direction we wind ABC is clockwise (CW) inside on right ACB is counterclockwise (CCW) inside on left COMP 5812M: Foundations of Modelling & Rendering COMP 5812M: Foundations of Modelling & Rendering Half-Plane Test Each test divides plane in half: Red vs. Not-Red Green vs. Not-Green Blue vs. Not-Blue Triangle is inside each COMP 5812M: Foundations of Modelling & Rendering COMP 5812M: Foundations of Modelling & Rendering Implicit Algorithm Assume CCW winding order (left is inside) But what about colour interpolation? As with lines, we need parametric form for (x = xMin; x < xMax; x++) for (y = yMin; y < yMax; y++) if ( (x,y) leftOf (A,B) && (x,y) leftOf (B,C) && (x,y) leftOf (C,A)) setPixel(x,y); COMP 5812M: Foundations of Modelling & Rendering COMP 5812M: Foundations of Modelling & Rendering Parametric Form For a line pq, t = 0.0 at p, t = 1.0 at q How can we parameterize a triangle? We need at least two parameters Start with one parameter Use it to interpolate colour as well COMP 5812M: Foundations of Modelling & Rendering COMP 5812M: Foundations of Modelling & Rendering Triangle Interpolation Pick a vertex A Set 100% blue at A Set 0% blue at CB In between, varies linearly perpendicular to CB COMP 5812M: Foundations of Modelling & Rendering COMP 5812M: Foundations of Modelling & Rendering The Parameter α Colour depends on distance from CB Call this distance α Parametrize so that: α = 1.0 at A α = 0.0 at BC P α COMP 5812M: Foundations of Modelling & Rendering COMP 5812M: Foundations of Modelling & Rendering And, obviously. . . For any point P COMP 5812M: Foundations of Modelling & Rendering COMP 5812M: Foundations of Modelling & Rendering Barycentric Coordinates α,β,γ are called barycentric coordinates Conveniently, So we really only have two parameters But we have three weights This lets us interpolate from three vertices to get colour, normals, textures, &c. COMP 5812M: Foundations of Modelling & Rendering COMP 5812M: Foundations of Modelling & Rendering Parametric Algorithm for (x = xMin; x < xMax; x++) for (y = yMin; y < yMax; y++) alpha = distance((x,y), BC) / distance(A, BC); beta = distance((x,y), AC) / distance(B, AC); gamma = distance((x,y), AB) / distance(C, AB); if ((alpha < 0.0) || (beta < 0.0) || (gamma < 0.0)) continue; colour = alpha * colour(A) + beta * colour(B) + gamma * colour(C); setColour(colour); setPixel(x,y); COMP 5812M: Foundations of Modelling & Rendering COMP 5812M: Foundations of Modelling & Rendering Perspective Interpolation Assume ABCD is a square E is not half-way between B & D visually But it needs to be mathematically So we have to correct it for the depth z Depth 0 Depth z COMP 5812M: Foundations of Modelling & Rendering COMP 5812M: Foundations of Modelling & Rendering Hyperbolic Interpolation Do perspective division on the value u (for each vertex) Interpolate both colour and 1/z Then reconstruct u: (using interpolated values) Usually done with the linewise raster scan Otherwise it gets really messy COMP 5812M: Foundations of Modelling & Rendering COMP 5812M: Foundations of Modelling & Rendering Summary Barycentric interpolation is cleanest But doesn’t work in perspective We will still use it for raytracing Raster scan can work in perspective If you do perspective division But not for raytracing COMP 5812M: Foundations of Modelling & Rendering COMP 5812M: Foundations of Modelling & Rendering Brief Article The Author September 28, 2016 ✓ = � w � � v cos ✓ = cos� v cos� w + sin� v sin� w = v x k~vk w x k~wk + w x k~wk w x k~wk = v x w x + v y w y k~vkk~wk = ~v · ~w k~vkk~wk ~v · ~w = k~vkk~wk cos ✓ ⇧ ~v (~w) = (Length)(Unit Vector) = (k~wk cos ✓) ~v k~vk = ✓ k~vk ~v · ~w k~vkk~wk ◆ ~v k~vk = ~v · ~w k~vk2 ~v = ~v · ~w ~v · ~v ~v ~n · p� c k~nk = ~n · ~v = k~nkk~vk cos ✓ cos ✓ < 0 when ~n · p� c 1 ! n ⋅ p − c = − to left of line 0 on line + to right of line ⎧ ⎨ ⎪ ⎩ ⎪