CS代考计算机代写 flex algorithm Computer Graphics CSI4130 – Winter 2019
Computer Graphics CSI4130 – Winter 2019
Jochen Lang
EECS, University of Ottawa Canada
Summary: Representations for Curves and Surfaces
– Parametric curves and surfaces
– Implicit curves in 2D and implicit surfaces in 3D
– Gradient
– Line equations
CSI4130 – Computer Graphics
This Lecture
• Triangles and Rasterization – Textbook: Chapter 2
– Triangles
– Baricentric coordinates
– Triangle rasterization – Simple Anti-Aliasing
CSI4130 – Computer Graphics
Triangles
• Fundamental modeling primitive
– OpenGL pipeline is optimized for triangles as geometric
primitive
– A triangle is in a plane defined by its 3 vertices
– Triangles interpolate their endpoints linearly along their edges and in the plane
– Trianglesdefinebaricentriccoordinates(non-orthogonal axes)
• Triangle area (2D) is the determinant – Vertices a,b,c in rhs
CSI4130 – Computer Graphics
Triangles 2D
• Baricentric coordinates
– Anypointinthetrianglecanbedescribedasthesumoftwo
edge vectors plus an origin.
CSI4130 – Computer Graphics
Baricentric Coordinates
• Given a point find its baricentric coordinates w.r.t. the triangle a,b,c
CSI4130 – Computer Graphics
Reminder: Distance of a Point from a Line
• Use implicit formulation
• Signed distance d
0
CSI4130 – Computer Graphics
Baricentric Coordinates via Implicit Line Equations
• Given a point find its baricentric coordinates w.r.t. the triangle a,b,c
CSI4130 – Computer Graphics
Baricentric Coordinates via Triangle Area
• Given a point find its baricentric coordinates w.r.t. the triangle a,b,c
CSI4130 – Computer Graphics
Triangles 3D
• Baricentric coordinates carry over
• Normal via cross products
• Area via length of normal
• Baricentric coordinates require signed area – Calculate dot product between normals
– Same side +1 other side -1
CSI4130 – Computer Graphics
Triangle Rasterization
• How to decide if pixels belong to a triangle?
– Triangle defined by 3 points
– Assume2Dcoordinates,otherwise
apply orthographic and perspective
projection first
– Utilize baricentric coordinates
for all x do
for all y do
compute ( alpha, beta, gamma ) of (x,y)
if 0<=alpha<=1 and 0<=beta<=1 and 0<=gamma<=1
c = alpha c_a + beta c_b + gamma c_c
drawpixel(x,y,c)
CSI4130 - Computer Graphics
Smooth Shading of Triangle
• Color defined at vertices
CSI4130 - Computer Graphics
12
Aside:
Setting the Drawing Color in OpenGL
• OpenGL Immediate Mode
– Drawing color is a state. The current vertex is drawn with the
current color.
– Example: glColor3f( 1.0f, 0.0f, 0.0f );
• WebGL and Modern OpenGL
– Need to look at buffers for data transfer
– Example will be for WebGL 2 (using a Vertex Array Object VAO) or for OpenGL 3.3+
CSI4130 - Computer Graphics
Data Transfer to WebGL/OpenGL
• Uniforms
– Variablesthatstayconstantforoneexecutionofthebuffer
• Buffer objects hold data in WebGL/OpenGL (GL)
– AbufferobjecttoholdvertexdataiscalledaVertexBuffer
Object (VBO)
• Vertex Array Objects (VAO)
– Organizeoneorseveralvertexarraybuffersintoacommon object
– VAOstoresstateincluding:
• Parametersofthecalltogl.VertexAttribPointer (size, type, stride, and offset)
• gl.ARRAY_BUFFER in use when gl.VertexAttribPointer was called.
CSI4130 - Computer Graphics
Program Structure with VAO/VBO
• Set-up in initialization routine
– generate and bind VAO
– generate, bind and fill (multiple) VBO for storing vertices and their attributes (e.g., colors, normals, texture coordinates)
– unbind VAO and possibly go the next set-up • Drawing routine
– bind the desired VAO
– call draw using data stored in the VBOs of the VAO – unbind the VAO
• Clean-up
– If there is lot of data in GL, free up the space taken up by the
VAO/VBO (see gl.deleteVertexArrays) CSI4130 Computer Graphics
Vertex Shader Program
• •
Vertex shader program is flexible to use (many) different buffers
We have used so far
– 1VBOatlocation0forthevertexpositionsoftypevec2or vec4.
– 2 uniforms for the modelview and projection matrices.
#version 300 es
layout (location=0) in vec4 position;
uniform mat4 ModelViewMatrix;
uniform mat4 ProjectionMatrix;
CSI4130 - Computer Graphics
Buffer Memory Allocation
– Buffers are identified by name (an unsigned integer number). – Need to perform the following steps
1. ask WebGL for a buffer name
2. bind the name to a binding point
– here use the gl.ARRAY_BUFFER binding point
3. Tell WebGL how big the buffer needs to be and optionally fill it with data
// Generate an array of handles to VBO const vertBuf = gl.createBuffer(); gl.bindBuffer(gl.ARRAY_BUFFER, vertBuf); gl.bufferData(gl.ARRAY_BUFFER,
verts,
gl.STATIC_DRAW);
CSI4130 Computer Graphics
Vertex Array Objects (VAO)
– Organize one or several vertex array buffers into a common object
– Available since WebGL 2.0
• OpenGL 4 always uses a VAO
– Once the VAO is bound VBOs can be bound to it
// Generate an VAO and bind it const vao = gl.createVertexArray(); gl.bindVertexArray( vao );
CSI4130 Computer Graphics
Drawing with a VBO/VAO
– LetGLknowhowthedataistobeused
• index, size of a single data, data type, normalize, stride (if there are gaps in the array), offset
– Enable the attribute in the buffer object for drawing
// offset into the buffer and data format gl.vertexAttribPointer(0, 2, gl.FLOAT, false, 0, 0 ); gl.enableVertexAttribArray(0);
– Drawing with the currently bound VAO
• type of primitive, starting index and number of vertices
gl.drawArrays( gl.TRIANGLES, 0, 3 );
CSI4130 Computer Graphics
More Vertex Attributes
• •
Our models (normally) have additional vertex attributes
– color, normals, texture coordinates, ...
Example: Color as an additional vertex attribute
– need to transfer the data to GL in a buffer – adjust our vertex program to use the data
• exactly the same as for vertex coordinates ...
// Additional attributes in separate buffer object const colorBuf = gl.createBuffer(); gl.bindBuffer(gl.ARRAY_BUFFER, colorBuf); gl.BufferData(gl.ARRAY_BUFFER,
colors,
gl.STATIC_DRAW);
CSI4130 - Computer Graphics
Using Additional Vertex Attributes
•
Adjust the shader program
•
Query the locations for the attributes in your initialization
•
Use the location
layout (location=0) in vec4 position; layout (location=1) in vec4 color;
locPos = gl.getAttribLocation( program, "position"); locColor = gl.getAttribLocation(program, "color");
gl.vertexAttribPointer(locColor, 4, gl.FLOAT, false, 0, 0);
gl.enableVertexAttribArray(locColor);
CSI4130 - Computer Graphics
Format of VBO
VAO
VBO VBO
v0 c0
v1 c1
v2 c2
• One buffer per attribute
– The approach on the previous slide
– Uses many buffers but independent buffer exchanges are easy
• Sequential storage in one buffer
– Can store position, color, normal as blocks in a single vertex
buffer object
– Less overhead because of fewer openGL calls and more
VBO v0
v1
v2
resource conscious
VAO
gl.vertexAttribPointer(locColor, 3, gl.FLOAT, false,
c0 0, c1
Float32Array.BYTES_PER_ELEMENT * 3 * nVerts);
c2
CSI4130 - Computer Graphics
Format of VBO: Interleaved
• Interleaved storage in one buffer
– Keep all information about a vertex together and make use
of the stride parameter
VBO v0
c0
v1
– Here assuming a vertex is stored as three floats
gl.vertexAttribPointer(locColor, 3, gl.FLOAT, false, Float32Array.BYTES_PER_ELEMENT * 3 ) Float32Array.BYTES_PER_ELEMENT * 3 );
CSI4130 - Computer Graphics
offset
c1 v2 c2
VAO
stride
Details of Triangle Rasterization
• Which pixel belongs to a triangle?
Offscreen Point
– triangles usually share edges
1, 1
– holes are bad
– double coloring is bad because of transparency
• Solution
– draw pixel only if we inside of triangle
– treat pixel exactly on the edge differently
CSI4130 - Computer Graphics
Edge Pixels
determine x_min, x_max, y_min, y_max
calculate f_alpha, f_beta, f_gamma
for x=x_min to x_max do
for y=y_min to y_max do
alpha = f12(x,y)/f_alpha
beta = f20(x,y)/f_beta
gamma = f01(x,y)/f_gamma
if alpha>=0 and beta>=0 and gamma>=0
if (alpha>0 or f_alpha * f12(-1,-1)>0) and (beta>0 or f_beta * f20(-1,-1)>0) and (gamma>0 or f_gamma * f01(-1,-1)>0)
c = alpha c_a + beta c_b + gamma c_c
drawpixel(x,y,c)
CSI4130 – Computer Graphics
Anti-Aliasing
• Box-filter: average pixel over an area
• e.g., 2x, 4x, 6x
– simple implementation
– use images 2x, 4x or 6x the size of the original image
– pixel in original image is the average of a 2×2 area, 4×4 area or 6×6 area of the enlarged image
CSI4130 – Computer Graphics
Line Drawing
– Bresenham Algorithm or
– Incremental Midpoint Algorithm
• use implicit lines
CSI4130 – Computer Graphics
Integer Line Drawing
– avoid floating point operations
– incrementalalgorithm • Key observations
– Ateachpixeldecideifpositionalongminoraxisneedstobe changed
– 4 Cases
• Line mainly along x with gradient • Line mainly along x with gradient • Line mainly along y with gradient • Line mainly along y with gradient
CSI4130 – Computer Graphics
Decide the Next Pixel
• Incremental Midpoint Algorithm
– Decision based on which side of the midpoint the line
crosses
– on the left/right of midpoint
CSI4130 – Computer Graphics
Incremental Midpoint Algorithm
// Integer start position
y=y0
// Initialize decision variable at (x0,y0+0.5)
// use 2f(x,y) = 0
d=(y0-y1)(2*x0)+(x1-x0)(2*y0+1)+2*(x0*y1-x1*y0)=x1-x0
for x=x0 to x1
draw( x, y )
if d<0 then
// left of midpoint
y=y+1
// next midpoint
d=d+2*(x1-x0)+2*(y0-y1)
else
// right of midpoint -- next midpoint
d=d+2*(y0-y1)
CSI4130 - Computer Graphics
Next
• Shading
– Textbook: Chapter 5.1, 5.2, 5.3 – Shading
– Diffuse Shading
– Blinn-Phong Shading
CSI4130 - Computer Graphics