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
⎧
⎨
⎪
⎩
⎪