[SOLVED] 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<=1c = alpha c_a + beta c_b + gamma c_cdrawpixel(x,y,c)CSI4130 – Computer Graphics Smooth Shading of Triangle Color defined at verticesCSI4130 – Computer Graphics
  12Aside:Setting the Drawing Color in OpenGL OpenGL Immediate Mode Drawing color is a state. The current vertex is drawn with thecurrent 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) AbufferobjecttoholdvertexdataiscalledaVertexBufferObject (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 theVAO/VBO (see gl.deleteVertexArrays) CSI4130 Computer GraphicsVertex Shader Program Vertex shader program is flexible to use (many) different buffersWe have used so far 1VBOatlocation0forthevertexpositionsoftypevec2or vec4. 2 uniforms for the modelview and projection matrices.#version 300 eslayout (location=0) in vec4 position;uniform mat4 ModelViewMatrix;uniform mat4 ProjectionMatrix;CSI4130 – Computer GraphicsBuffer Memory Allocation Buffers are identified by name (an unsigned integer number). Need to perform the following steps1. ask WebGL for a buffer name2. bind the name to a binding point here use the gl.ARRAY_BUFFER binding point3. 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 GraphicsVertex 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 verticesgl.drawArrays( gl.TRIANGLES, 0, 3 );CSI4130 Computer GraphicsMore 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 GraphicsUsing Additional Vertex AttributesAdjust the shader programQuery the locations for the attributes in your initializationUse the locationlayout (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 VBOVAOVBO VBOv0 c0v1 c1v2 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 vertexbuffer object Less overhead because of fewer openGL calls and moreVBO v0v1v2resource consciousVAOgl.vertexAttribPointer(locColor, 3, gl.FLOAT, false,c0 0, c1Float32Array.BYTES_PER_ELEMENT * 3 * nVerts);c2CSI4130 – Computer Graphics Format of VBO: Interleaved Interleaved storage in one buffer Keep all information about a vertex together and make useof the stride parameterVBO v0c0v1 Here assuming a vertex is stored as three floatsgl.vertexAttribPointer(locColor, 3, gl.FLOAT, false, Float32Array.BYTES_PER_ELEMENT * 3 ) Float32Array.BYTES_PER_ELEMENT * 3 );CSI4130 – Computer Graphicsoffsetc1 v2 c2VAOstride Details of Triangle Rasterization Which pixel belongs to a triangle?Offscreen Point triangles usually share edges1, 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 differentlyCSI4130 – Computer Graphics Edge Pixelsdetermine x_min, x_max, y_min, y_maxcalculate f_alpha, f_beta, f_gammafor x=x_min to x_max dofor 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 22 area, 44 area or 66 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 midpointy=y+1// next midpointd=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 ShadingCSI4130 – Computer Graphics