Drawing triangles

Сентябрь 16, 2022

Содержание

2. David Luebke Admin Homework 1 graded, will post this afternoon
3. David Luebke Rasterizing Polygons In interactive graphics, polygons rule the world Two main reasons: Lowest common
4. David Luebke Rasterizing Polygons Triangle is the minimal unit of a polygon All polygons can be
5. David Luebke Convex Shapes A two-dimensional shape is convex if and only if every line segment
6. David Luebke Convex Shapes Why do we want convex shapes for rasterization? One good answer: because
7. David Luebke Decomposing Polys Into Tris Any convex polygon can be trivially decomposed into triangles Draw
8. David Luebke Rasterizing Triangles Interactive graphics hardware commonly uses edge walking or edge equation techniques for
9. David Luebke Recursive Triangle Subdivision
10. David Luebke Recursive Screen Subdivision
11. David Luebke Edge Walking Basic idea: Draw edges vertically Fill in horizontal spans for each scanline
12. David Luebke Edge Walking: Notes Order vertices in x and y 3 cases: break left, break
13. David Luebke Edge Walking: Notes Fractional offsets: Be careful when interpolating color values! Also: beware gaps
14. David Luebke Edge Equations An edge equation is simply the equation of the line containing that
15. David Luebke Edge Equations Edge equations thus define two half-spaces:
16. David Luebke Edge Equations And a triangle can be defined as the intersection of three positive
17. David Luebke Edge Equations So…simply turn on those pixels for which all edge equations evaluate to
18. David Luebke Using Edge Equations An aside: How do you suppose edge equations are implemented in
19. David Luebke Using Edge Equations Which pixels: compute min,max bounding box Edge equations: compute from vertices
20. David Luebke Computing a Bounding Box Easy to do Surprising number of speed hacks possible See
21. David Luebke Computing Edge Equations Want to calculate A, B, C for each edge from (xi,
22. David Luebke Computing Edge Equations Set up the linear system: Multiply both sides by matrix inverse:
23. David Luebke Computing Edge Equations: Numerical Issues Calculating C = x0 y1 - x1 y0 involves
24. David Luebke Computing Edge Equations: Numerical Issues We can avoid the problem in this case by
25. David Luebke Edge Equations So…we can find edge equation from two verts. Given three corners C0,
26. David Luebke Edge Equations: Code Basic structure of code: Setup: compute edge equations, bounding box (Outer
27. David Luebke Optimize This! findBoundingBox(&xmin, &xmax, &ymin, &ymax); setupEdges (&a0,&b0,&c0,&a1,&b1,&c1,&a2,&b2,&c2); /* Optimize this: */ for (int
28. David Luebke Edge Equations: Speed Hacks Some speed hacks for the inner loop: int xflag =
29. David Luebke Edge Equations: Interpolating Color Given colors (and later, other parameters) at the vertices, how
30. David Luebke Edge Equations: Interpolating Color Given redness at the 3 vertices, set up the linear
31. David Luebke Edge Equations: Interpolating Color Notice that the columns in the matrix are exactly the
33. Скачать презентацию

Слайд 2

David Luebke
Admin
Homework 1 graded, will post this afternoon

Слайд 3

David Luebke
Rasterizing Polygons
In interactive graphics, polygons rule the world
Two main

reasons:
Lowest common denominator for surfaces
Can represent any surface with arbitrary accuracy
Splines, mathematical functions, volumetric isosurfaces…
Mathematical simplicity lends itself to simple, regular rendering algorithms
Like those we’re about to discuss…
Such algorithms embed well in hardware

Слайд 4

David Luebke
Rasterizing Polygons
Triangle is the minimal unit of a polygon
All

polygons can be broken up into triangles
Convex, concave, complex
Triangles are guaranteed to be:
Planar
Convex
What exactly does it mean to be convex?

Слайд 5

David Luebke
Convex Shapes
A two-dimensional shape is convex if and only

if every line segment connecting two points on the boundary is entirely contained.

Слайд 6

David Luebke
Convex Shapes
Why do we want convex shapes for rasterization?
One

good answer: because any scan line is guaranteed to contain at most one segment or span of a triangle
Another answer coming up later
Note: Can also use an algorithm which handles concave polygons. It is more complex than what we’ll present here!

Слайд 7

David Luebke
Decomposing Polys Into Tris
Any convex polygon can be trivially

decomposed into triangles
Draw it
Any concave or complex polygon can be decomposed into triangles, too
Non-trivial!

Слайд 8

David Luebke
Rasterizing Triangles
Interactive graphics hardware commonly uses edge walking or

edge equation techniques for rasterizing triangles
Two techniques we won’t talk about much:
Recursive subdivision of primitive into micropolygons (REYES, Renderman)
Recursive subdivision of screen (Warnock)

Слайд 9

David Luebke
Recursive Triangle Subdivision

Слайд 10

David Luebke
Recursive Screen Subdivision

Слайд 11

David Luebke
Edge Walking
Basic idea:
Draw edges vertically
Fill in horizontal spans

for each scanline
Interpolate colors down edges
At each scanline, interpolate edge colors across span

Слайд 12

David Luebke
Edge Walking: Notes
Order vertices in x and y
3 cases:

break left, break right, no break
Walk down left and right edges
Fill each span
Until breakpoint or bottom vertex is reached
Advantage: can be made very fast
Disadvantages:
Lots of finicky special cases
Tough to get right
Need to pay attention to fractional offsets

Слайд 13

David Luebke
Edge Walking: Notes
Fractional offsets:
Be careful when interpolating color values!
Also:

beware gaps between adjacent edges

Слайд 14

David Luebke
Edge Equations
An edge equation is simply the equation of

the line containing that edge
Q: What is the equation of a 2D line?
A: Ax + By + C = 0
Q: Given a point (x,y), what does plugging x & y into this equation tell us?
A: Whether the point is:
On the line: Ax + By + C = 0
“Above” the line: Ax + By + C > 0
“Below” the line: Ax + By + C < 0

Слайд 15

David Luebke
Edge Equations
Edge equations thus define two half-spaces:

Слайд 16

David Luebke
Edge Equations
And a triangle can be defined as the

intersection of three positive half-spaces:

Слайд 17

David Luebke
Edge Equations
So…simply turn on those pixels for which all

edge equations evaluate to > 0:

Слайд 18

David Luebke
Using Edge Equations
An aside: How do you suppose edge

equations are implemented in hardware?
How would you implement an edge-equation rasterizer in software?
Which pixels do you consider?
How do you compute the edge equations?
How do you orient them correctly?

Слайд 19

David Luebke
Using Edge Equations
Which pixels: compute min,max bounding box
Edge equations:

compute from vertices
Orientation: ensure area is positive (why?)

Слайд 20

David Luebke
Computing a Bounding Box
Easy to do
Surprising number of speed

hacks possible
See McMillan’s Java code for an example

Слайд 21

David Luebke
Computing Edge Equations
Want to calculate A, B, C for

each edge from (xi, yi) and (xj, yj)
Treat it as a linear system:
Ax1 + By1 + C = 0
Ax2 + By2 + C = 0
Notice: two equations, three unknowns
Does this make sense? What can we solve?
Goal: solve for A & B in terms of C

Слайд 22

David Luebke
Computing Edge Equations
Set up the linear system:
Multiply both sides by

matrix inverse:
Let C = x0 y1 - x1 y0 for convenience
Then A = y0 - y1 and B = x1 - x0

Слайд 23

David Luebke
Computing Edge Equations: Numerical Issues
Calculating C = x0 y1

- x1 y0 involves some numerical precision issues
When is it bad to subtract two floating-point numbers?
A: When they are of similar magnitude
Example: 1.234x104 - 1.233x104 = 1.000x101
We lose most of the significant digits in result
In general, (x0,y0) and (x1,y1) (corner vertices of a triangle) are fairly close, so we have a problem

Слайд 24

David Luebke
Computing Edge Equations: Numerical Issues
We can avoid the problem in

this case by using our definitions of A and B:
A = y0 - y1 B = x1 - x0 C = x0 y1 - x1 y0
Thus:
C = -Ax0 - By0 or C = -Ax1 - By1
Why is this better?
Which should we choose?
Trick question! Average the two to avoid bias:
C = -[A(x0+x1) + B(y0+y1)] / 2

Слайд 25

David Luebke
Edge Equations
So…we can find edge equation from two verts.

Given three corners C0, C1, C0 of a triangle, what are our three edges?
How do we make sure the half-spaces defined by the edge equations all share the same sign on the interior of the triangle?
A: Be consistent (Ex: [C0 C1], [C1 C2], [C2 C0])
How do we make sure that sign is positive?
A: Test, and flip if needed (A= -A, B= -B, C= -C)

Слайд 26

David Luebke
Edge Equations: Code
Basic structure of code:
Setup: compute edge equations,

bounding box
(Outer loop) For each scanline in bounding box...
(Inner loop) …check each pixel on scanline, evaluating edge equations and drawing the pixel if all three are positive

Слайд 27

David Luebke
Optimize This!
findBoundingBox(&xmin, &xmax, &ymin, &ymax);
setupEdges (&a0,&b0,&c0,&a1,&b1,&c1,&a2,&b2,&c2);
/* Optimize this: */
for

(int y = yMin; y <= yMax; y++) {
for (int x = xMin; x <= xMax; x++) {
float e0 = a0*x + b0*y + c0;
float e1 = a1*x + b1*y + c1;
float e2 = a2*x + b2*y + c2;
if (e0 > 0 && e1 > 0 && e2 > 0) setPixel(x,y);
}
}

Слайд 28

David Luebke
Edge Equations: Speed Hacks
Some speed hacks for the inner

loop:
int xflag = 0;
for (int x = xMin; x <= xMax; x++) {
if (e0|e1|e2 > 0) {
setPixel(x,y);
xflag++;
} else if (xflag != 0) break;
e0 += a0; e1 += a1; e2 += a2;
}
Incremental update of edge equation values (think DDA)
Early termination (why does this work?)
Faster test of equation values

Слайд 29

David Luebke
Edge Equations: Interpolating Color
Given colors (and later, other parameters)

at the vertices, how to interpolate across?
Idea: triangles are planar in any space:
This is the “redness” parameter space
Note:plane follows form z = Ax + By + C
Look familiar?

Слайд 30

David Luebke
Edge Equations: Interpolating Color
Given redness at the 3 vertices,

set up the linear system of equations:
The solution works out to:

Слайд 31

David Luebke
Edge Equations: Interpolating Color
Notice that the columns in the matrix

are exactly the coefficients of the edge equations!
So the setup cost per parameter is basically a matrix multiply
Per-pixel cost (the inner loop) cost equates to tracking another edge equation value

Drawing triangles

Содержание

David Luebke AdminHomework 1 graded, will post this afternoon

David Luebke Rasterizing PolygonsIn interactive graphics, polygons rule the worldTwo main

David Luebke Rasterizing PolygonsTriangle is the minimal unit of a polygonAll

David Luebke Convex ShapesA two-dimensional shape is convex if and only

David Luebke Convex ShapesWhy do we want convex shapes for rasterization?One

David Luebke Decomposing Polys Into TrisAny convex polygon can be trivially

David Luebke Rasterizing TrianglesInteractive graphics hardware commonly uses edge walking or

David Luebke Recursive Triangle Subdivision

David Luebke Recursive Screen Subdivision

David Luebke Edge WalkingBasic idea: Draw edges verticallyFill in horizontal spans

David Luebke Edge Walking: NotesOrder vertices in x and y3 cases:

David Luebke Edge Walking: NotesFractional offsets:Be careful when interpolating color values!Also:

David Luebke Edge EquationsAn edge equation is simply the equation of

David Luebke Edge EquationsEdge equations thus define two half-spaces:

David Luebke Edge EquationsAnd a triangle can be defined as the

David Luebke Edge EquationsSo…simply turn on those pixels for which all

David Luebke Using Edge EquationsAn aside: How do you suppose edge

David Luebke Using Edge EquationsWhich pixels: compute min,max bounding boxEdge equations:

David Luebke Computing a Bounding BoxEasy to doSurprising number of speed

David Luebke Computing Edge EquationsWant to calculate A, B, C for

David Luebke Computing Edge EquationsSet up the linear system:Multiply both sides by

David Luebke Computing Edge Equations: Numerical IssuesCalculating C = x0 y1

David Luebke Computing Edge Equations: Numerical IssuesWe can avoid the problem in

David Luebke Edge EquationsSo…we can find edge equation from two verts.

David Luebke Edge Equations: CodeBasic structure of code:Setup: compute edge equations,

David Luebke Optimize This!findBoundingBox(&xmin, &xmax, &ymin, &ymax);setupEdges (&a0,&b0,&c0,&a1,&b1,&c1,&a2,&b2,&c2);/* Optimize this: */for

David Luebke Edge Equations: Speed HacksSome speed hacks for the inner

David Luebke Edge Equations: Interpolating ColorGiven colors (and later, other parameters)

David Luebke Edge Equations: Interpolating ColorGiven redness at the 3 vertices,

David Luebke Edge Equations: Interpolating ColorNotice that the columns in the matrix

Похожие презентации