Procedural Geometry Lecture Notes PDF

1(81) Information Coding / Computer Graphics, ISY, LiTH TNM084! Procedural images Ingemar Ragnemalm, ISY 1(81) Information Coding / Computer Graphics, ISY, LiTH Lecture 6...

1(81) Information Coding / Computer Graphics, ISY, LiTH TNM084! Procedural images Ingemar Ragnemalm, ISY 1(81) Information Coding / Computer Graphics, ISY, LiTH Lecture 6! ! Procedural geometry! ! Fractals 2(81)2(81)  Information Coding / Computer Graphics, ISY, LiTH Lecture questions! ! 1. How can you calculate the normal vector of a surface?! ! 2. What kind of functions a suitable for blobby objects?! ! 3. What is the idea of turtle graphics?! ! 4. When is a matrix stack useful?! ! 5. What does the fractal dimension 2.5 mean for a 3D fractal?! ! 6. What determines the output of a self-squaring fractal? 3(81)3(81) Information Coding / Computer Graphics, ISY, LiTH Procedural geometry! ! Producing models with code:! ! Simple shapes with customizable detail! ! Shapes with repeating detail! ! Sampling functions! ! Sweeping! ! Tools for geometry generation 4(81)4(81)  Information Coding / Computer Graphics, ISY, LiTH Simple shapes with customizable detail! ! Example: Sphere! ! 1. Define in polar coordinates. Setting: Number of steps along each coordinate! ! 2. Define by tesselation. Setting: Number of tesselation steps ! ! 3. Generate a cube with desired resolution and project it to a sphere. Setting: Resolution of the cube. 5(81)5(81)  Information Coding / Computer Graphics, ISY, LiTH Sphere from polar coordinates! ! Decide number of steps for longitude and latitude! ! Go around the sphere using trigonometric functions (sin and cos) with steps by angle or height Few latitude (sideways) steps Few longitude (top-to-bottom) steps 6(81)6(81) Information Coding / Computer Graphics, ISY, LiTH Sphere by tesselation! ! Split each triangle into three triangles.! ! Move the new vertex to the surface. 7(81)7(81) Information Coding / Computer Graphics, ISY, LiTH Sphere by projection! ! Make a cube, project each vertex to a sphere 8(81)8(81)  Information Coding / Computer Graphics, ISY, LiTH Sampling a function! ! A model can be constructed from a mathematical function! ! Sample at suitable distance and create polygons (triangles)! ! Find functions that create closed models. 9(81)9(81)  Information Coding / Computer Graphics, ISY, LiTH Blobby objects, Metaballs! ! Build shapes from sets of points. Represent surfaces by distance functions! ! A shape = set of points + weights Yet another image stolen! from Wikipedia 10(81)10(81) Information Coding / Computer Graphics, ISY, LiTH Blobby objects! ! Gaussian functions (”Gaussian bumps”) f(x) = ∑ bk * exp(x - pk)! ! Surface at f(x) = threshold But Gaussians are not fast! 11(81)11(81)  Information Coding / Computer Graphics, ISY, LiTH Blobby objects! ! Gaussian: A function that falls off towards zero and has a top at 1!! ! Can we use something else? Best if:! ! Smooth! ! Reaches zero at a known radius! (Why?) 12(81)12(81)  Information Coding / Computer Graphics, ISY, LiTH Possible function:! ! f(x) = R / sqrt((x - x0)2)! ! Why can this work? Big peak in the middle, that is not a gaussian!! ! Even better if we can avoid division and square root.! ! Smoothstep is perfectly feasible and a decent approximation of a gaussian. 13(81)13(81)  Information Coding / Computer Graphics, ISY, LiTH Drawing blobby objects In 2D, blobby objects are easily made by just checking if a pixel is inside/outside. In 3D, we want to produce surfaces! How can we do that? 14(81)14(81) Information Coding / Computer Graphics, ISY, LiTH Marching cubes! ! Voxels with density values! Treshold in density! Voxels are corners of cubes! Create polygons in the treshold. Bild fr Wikipedia 15(81)15(81) Information Coding / Computer Graphics, ISY, LiTH Marching squares - Marching cubes i 2D 16(81)16(81)  Information Coding / Computer Graphics, ISY, LiTH Sweeping (Rotational sweep)! ! Circular symmetric shapes! ! Define by a curve (preferrably a spline) which is rotated and vertices created along it. 17(81)17(81)  Information Coding / Computer Graphics, ISY, LiTH Sweeping of 2D shapes! ! Sweeping can also be made with closed curves. Typical case: The torus, sweeping of a circle. 18(81)18(81)  Information Coding / Computer Graphics, ISY, LiTH Normal vectors! ! Hard problem for many procedural shapes! ! Calculate from known geometry. Easy for some shapes, but not all.! ! Sample the geometry to find differential steps and calculate normal from these.! ! Post-processing. Find polygons (e.g. triangles) touching each vertex. Caclulate normal. 19(81)19(81) Information Coding / Computer Graphics, ISY, LiTH Analytical normal vectors for sweeping! ! Variation along height and around object! ! Simple case: Cylinder r p(u, 𝞅) = (rsin𝞅, u, rcos𝞅) dp! u = (0, 1, 0) du dp! = (rcos𝞅, 0, -rsin𝞅) 𝞅 d𝞅 dp! dp! n(u, 𝞅) = x = (rsin𝞅, 0, rcos𝞅) du d𝞅 As expected: Straight out 20(81)20(81)  Information Coding / Computer Graphics, ISY, LiTH Harder case: Sin wave p(u, 𝞅) = (sin𝞅(sinu + r), u, cos𝞅(sinu + r)) r dp! = (sin𝞅cosu, 1, -sin𝞅cosu) du u dp! = (cos𝞅(sinu + r), 0, -sin𝞅(sinu + r)) d𝞅 𝞅 dp! dp! n(u, 𝞅) = x = (sin𝞅, (cos2𝞅 - sin2𝞅) cosu, cos𝞅) du d𝞅 Normal vector varies by height 21(81)21(81)  Information Coding / Computer Graphics, ISY, LiTH Calculating normal vectors from geometry! ! Find all neighbor triangles. Calculate normals for each triangle with cross product. Make a weighted average.! ! Triangle method: Find three vertices enclosing the vertex. Find normal by cross product of two edges.! ! Cross method. Find four vertices enclosing the vertex. Make a vector from each opposing pair, get normal with cross product.! ! If the geometry is known, find neighbor samples of the geometry and use the cross or triangle method. 22(81)22(81) Information Coding / Computer Graphics, ISY, LiTH All triangles method! ! Most precise and most general. Also most work. 23(81)23(81)  Information Coding / Computer Graphics, ISY, LiTH Triangle method! ! Only three vertices. Surprisingly good.! ! Note that the target vertex is not involved. How can that work? 24(81)24(81)  Information Coding / Computer Graphics, ISY, LiTH Cross method! ! Four vertices. Good if vertex locations are (more or less) axis aligned.! ! Again, the target vertex is not involved. 25(81)25(81)  Information Coding / Computer Graphics, ISY, LiTH Why can we get a good approximation from the neighbors alone?! ! The neighbors form a plane for which the normal tends to be a good normal for the vertex inside the triangle/cross. It doesn't matter hos the center vertex moves. 26(81)26(81)  Information Coding / Computer Graphics, ISY, LiTH Sweeping and normals! ! Simple case for normal vectors. Only the Y component varies along a vertical slice, the others are given by the rotation step. Thus, just taking one step up and down along the spline suffices!, Or use the mathematical derivative of the spline like above, if that is feasible for the shape. gives y φ cos φ, sin φ give x and z 27(81)27(81)  Information Coding / Computer Graphics, ISY, LiTH Tools for procedural geometry generation! ! C++ Vectors! ! Turtle graphics! ! OpenSCAD! ! Immediate mode! ! GLUGG 28(81)28(81)  Information Coding / Computer Graphics, ISY, LiTH C++ Vectors! ! C++ dynamic arrays! Create vertices one at a time, append to a Vector of vertices! ! Fast, built-in in C++! Messy if you want to do more than one thing at a time! No library of shapes to work from as part of the system! Only triangles! ! "The way" today? Or maybe we want some extras? 29(81)29(81) Information Coding / Computer Graphics, ISY, LiTH Turtle graphics! ! "Pen" in relative (local) coordinates.! ! Pen position and orientation! ! Simple commands, "forward", "turn 90 degrees"! ! 2D or 3D system. 30(81)30(81) Information Coding / Computer Graphics, ISY, LiTH Turtle graphics examples! ! From Wikipedia 31(81)31(81)  Information Coding / Computer Graphics, ISY, LiTH Turtle graphics examples! ! From Python lib/turtle.py! ! from turtle import *! color('red', 'yellow')! begin_fill()! while True:! forward(200)! left(170)! if abs(pos()) < 1:! break! end_fill()! done()! 32(81)32(81)  Information Coding / Computer Graphics, ISY, LiTH OpenSCAD, the procedural geometry CAD program! ! A CAD modelling software based on code! You are literally programming your models, and get a 3D model out.! ! Simple example just put together existing shapes.! ! Advanced use model with coordinates and splines.! 33(81)33(81)  Information Coding / Computer Graphics, ISY, LiTH OpenSCAD wheels, transformations! ! Uses existing parts! ! use ;! $fa = 1;! $fs = 0.4;! ! wheelbase = 40;! track = 35;! ! translate([-wheelbase/2, track/2])! simple_wheel();! translate([-wheelbase/2, -track/2])! simple_wheel();! translate([-wheelbase/2, 0, 0])! axle(track=track); 34(81)34(81)  Information Coding / Computer Graphics, ISY, LiTH OpenSCAD heart example! ! points = [ for (t=[0:step:359.999]) [16*pow(sin(t),3), 13*cos(t) - 5*cos(2*t) - 2*cos(3*t) - cos(4*t)]]; 35(81)35(81) Information Coding / Computer Graphics, ISY, LiTH Old OpenGL procedural geometry! ! Big thing in old OpenGL! ! Used the "immediate mode"! ! Recorded to "display lists" for performance! ! Phased out with OpenGL 3. 36(81)36(81)  Information Coding / Computer Graphics, ISY, LiTH Immediate mode! ! Specify geometry by function calls per vertex:! ! glBegin(GL_POLYGON);! glColor3f(1, 0, 0); glVertex3f(-0.6, -0.75, 0.5);! glColor3f(0, 1, 0); glVertex3f(0.6, -0.75, 0);! glColor3f(0, 0, 1); glVertex3f(0, 0.75, 0);! glEnd();! ! draws a triangle with different colors. Too many function calls for large models. https://cs.lmu.edu/~ray/notes/openglexamples/ 37(81)37(81) Information Coding / Computer Graphics, ISY, LiTH Classic examples! ! Gears (glxGears standard example in Mesa)! ! Creates three matching gears procedurally. 38(81)38(81) Information Coding / Computer Graphics, ISY, LiTH Display lists! ! Immediate mode was not slow - if you let it.! ! Generate to a "display list"! ! Converts the data to an array behind the surface.! ! But this was optional and more complex! 39(81)39(81)  Information Coding / Computer Graphics, ISY, LiTH The matrix stack! ! Old OpenGL managed a "matrix stack" for dealing with hierarcical models.! ! glPushMatrix()! glPopMatrix()! ! Makes it easier to build hierarchical models 40(81)40(81)  Information Coding / Computer Graphics, ISY, LiTH Revisited: Transformations to sub-systems under model coordinates! ! Used for dependencies in hierarchical models Model coordinates Top of windmill Axis for blades Blade Body of windmill with rotation for The axis can rotate Blades rotate by top (around y) (around x or z) following the rotation of the axis 41(81)41(81)  Information Coding / Computer Graphics, ISY, LiTH What if you have multiple braches/ dependencies?! ! Use the matrix stack to get back to earlier nodes back! back! M5 M3 back! For every node that you want to go M6 M2 back to, save the current matrix with back! glPushMatrix(). M4 M1 Go back with glPopMatrix() 42(81)42(81)  Information Coding / Computer Graphics, ISY, LiTH Why do we care?! ! Procedural modelling in OpenGL has fallen out of fashion - but is it useless?! ! How about doing this with modern code? 43(81)43(81)  Information Coding / Computer Graphics, ISY, LiTH OpenGL Utilities for Geometry Generation (GLUGG)! ! My code package for creating procedural geometry in a modern way, but similar to the old way.! ! Create geometry with similar calls, gluggVertex etc! Supports transformations and a matrix stack.! Generates a vertex/polygon list (optionally with an index array) for uploading to a VAO.! ! Intended for generating geometry at the initialization of a program. 44(81)44(81)  Information Coding / Computer Graphics, ISY, LiTH Simple usage of GLUGG: Triangle #include "MicroGlut.h"! void init(void)! #include "GL_utilities.h"! {! #include "glugg.h"! ! program = loadShaders("minimal.vert", "minimal.frag");! ! ! ! GLuint program; // Shader! ! ! gluggModel triangle;! ! gluggBegin(GLUGG_TRIANGLES);! ! ! gluggVertex(-0.5,-0.5,0);! void draw(void)! ! gluggVertex(0.5,-0.5,0);! {! ! gluggVertex(-0.5,0.5,0);! ! glClear(GL_COLOR_BUFFER_BIT);! ! triangle = gluggBuildModel(0);! ! ! }! ! gluggDrawModel(triangle, program);! ! ! ! int main(int argc, char *argv[])! ! glutSwapBuffers();! {! }! ! glutInit(&argc, argv);! ! ! ! ! glutInitDisplayMode(GLUT_RGB | GLUT_DOUBLE);! ! glutInitContextVersion(3, 2);! ! ! glutCreateWindow("GLUGG White Triangle");! ! init();! ! glutDisplayFunc(draw);! ! ! glutMainLoop();! ! return 0;! }! 45(81)45(81)  Information Coding / Computer Graphics, ISY, LiTH Building with multiple parts and the matrix stack! ! The snowman (based on old demo from lighthouse3d) 46(81)46(81)  Information Coding / Computer Graphics, ISY, LiTH The code for making the snowman! ! Parts made in other functions are built together using transformations and the matrix stack gluggModel MakeSnowman()! // Draw Eyes! {! ! gluggPushMatrix();! ! gluggBegin(GLUGG_TRIANGLES);! ! gluggColor(0.0f,0.0f,0.0f);! ! ! gluggTranslate(0.05f, 0.10f, 0.18f);! ! gluggColor(1.0f, 1.0f, 1.0f);! ! gluggSphere(10,10, 0.05f);! ! ! gluggTranslate(-0.1f, 0.0f, 0.0f);! // Draw Body!! ! gluggSphere(10,10, 0.05f);! ! gluggTranslate(0.0f ,0.75f, 0.0f);! ! gluggPopMatrix();! ! gluggSphere(20,20, 0.75f);! ! ! // Draw Nose! // Draw Head! ! gluggColor(1.0f, 0.5f , 0.5f);! ! gluggTranslate(0.0f, 0.95f, 0.0f);! ! gluggRotate(M_PI/2.0,1.0f, 0.0f, 0.0f);! ! gluggSphere(20,20, 0.25f);! ! gluggCone(10, 0.5, 0.08f);! ! ! return gluggBuildModel(0);! } 47(81)47(81) Information Coding / Computer Graphics, ISY, LiTH Building with Bézier surfaces! ! Bézier surfaces are built-in!! ! G1/C1 continuity is up to you (currently).! ! Used for the 4-patch "surface" and for the Utah Teaset! 48(81)48(81) Information Coding / Computer Graphics, ISY, LiTH Plenty of demos and a (hopefully) decent documentation! ! …but very little used by others than myself - until TNM084 came along. 49(81)49(81)  Information Coding / Computer Graphics, ISY, LiTH Usage in lab 3! ! GLUGG will be used in the first part of Lab 3. It has been used for that for three years with good results.! ! The latest version can be found here:! ! https://computer-graphics.se/packages/glugg.html 50(81)50(81) Information Coding / Computer Graphics, ISY, LiTH Procedural geometry, summary (so far)! ! Produces flexible, customizable and detailed geometry! ! Sweeping, normal vectors! ! Matrix stack for handling multiple branches! ! Several approaches:! ! C++ Vector! Turtle graphics! OpenSCAD! Old-style OpenGL! GLUGG! ! But where does the noise/randomness come in?! ! Right now: 51(81)51(81)