Object Representations PDF

OBJECT MODELLING Object Modelling  Modelling is the process of describing an object  shape, appearance and behavior  shape is theme of this lecture ◼ also called Shape Representation or Shape Modelling  Sometimes the description is an end in itself  Computer Ai...

OBJECT MODELLING Object Modelling  Modelling is the process of describing an object  shape, appearance and behavior  shape is theme of this lecture ◼ also called Shape Representation or Shape Modelling  Sometimes the description is an end in itself  Computer Aided Design (CAD), Computer Aided Manufacturing (CAM) ◼ The model is an exact description  More typically in graphics, the model is then used for rendering  The model only exists to produce a picture  It can be an approximation, as long as the visual result is good Object Modelling  Historical computer graphics motto: “If it looks right it is right”  Doesn’t work for CAD  In recent years, simulating physics for more realistic appearance and behavior has been the rule  Even more recently AI is used to generate realistic objects/scenes Issues in Shape Modeling  There are many ways to represent the shape of an object  What are some things to think about when choosing a representation? Choosing a Representation Scheme  How accurately does it represents the objects of interest?  How easy is it to render (or convert to polygons)?  How compact is it (how cheap to store and transmit)?  How easy is it to create?  By hand, procedurally, by fitting to measurements, …  How easy is it to interact with?  Modifying it, animating it  How easy is it to perform geometric computations?  Distance, intersection, normal vectors, curvature, …  How smooth is it? Categorizing Shape Representation Schemes  1. Surface vs. Volume  Sometimes (most of the time) we only care only about the surface ◼ rendering and geometric computations  Sometimes we want to know about the volume (the “inside”) ◼ Medical data with information attached to the space ◼ Some representations are best thought of defining the space filled, rather than the surface around the space Categorizing Representation Schemes  2. Parametric vs. Implicit  Parametric generates all x = r cos  cos  , the points on a surface (volume) by “plugging in a y = r cos  sin  , parameter” z = r sin   Implicit models tell you if a point is on (or inside) the f ( x, y , z ) = x 2 + y 2 + z 2 − r 2 surface (volume) e.g. Shape Representation Schemes Shape Representation Schemes 1. Polygon Mesh 2. Parametric modelling 3. Hierarchical modelling 4. Sweep Objects 5. Solid Modelling  Constructive Solid Geometry  Spatial Enumeration 6. Implicit Functions (Blobs and Metaballs) 7. Procedural Modelling 8. AI Generated 1 - Polygon Mesh Polygon Surface Mesh  Set of adjacent polygons representing the object exteriors.  All operations linear, so fast.  Non-polyhedron shapes can be approximated by polygon meshes.  Smoothness is provided either by increasing the number of polygons or interpolated shading methods. Levels of detail Interpolated shading Polygons Dominate  Everything can be turned into polygons (almost everything)  We know how to render polygons quickly  Many operations are easy to do with polygons  Memory and disk space is cheap  Simplicity and inertia Polygons Aren’t Great  They are always an approximation to curved surfaces  But can be as good as you want, if you are willing to pay in size  Normal vectors are approximate  They throw away information  Most real-world surfaces are curved, particularly natural surfaces  They can be very “unstructured”  It is difficult to perform many geometric operations  Results can be unduly complex 2 - Parametric Modelling Parametric Modelling  Many things, called shape primitives, are conveniently described by a label and a few parameters  Cylinder: radius, height, does it have end-caps, …  Bolts: length, diameter, thread pitch, …  Other examples?  Need software function that knows how to draw the object given the parameters  Typically by generating a triangle/quad mesh  Can be an exact representation via parametric equations  Can differentiate to get exact parametric equations for normal vectors Parametric Modelling  Often defined by equations of the form: x = r cos (2u) x(u,v) = … y = r sin (2u) y(u,v) = … z = vh  Useful for modeling surfaces where continuity is important  Various examples:  Shape primitives (spheres, cylinders etc.)  Spline Curves/Surfaces: Bezier, B-splines, NURBS (Non-Uniform Rational BSplines)  Example of Parametric Modeling: Quadric Surfaces  Described with second degree (quadric) equations.  Examples:  Spheres  Ellipsoids  Tori  Paraboloids  Hyperboloids  Can also be created using spline representations. Example: Sphere  Parametric equation using spherical coords: x = r cos  cos  , − / 2     / 2 y = r cos  sin  , −     z = r sin   Non-parametric (implicit) equation x2 + y2 + z 2 = r 2 Cylinder  Cylinder x = r cos (2u) y = r sin (2u) z = vh parametric coordinates r = radius h = height Example: Ellipsoid  Implicit equation 2 x  y z 2 2   +   +   = 1 r   x   y   rz  r  Parametric equation using spherical coords: x = rx cos  cos  , − / 2     / 2 y = ry cos  sin  , −     z = rz sin   Example: Superellipse x = rx cos  , −      2/ n  y 2/ n n x   +  =1 r  y = ry sin n   rx   y rx = ry Example: Superellipsoid s2 / s1  x  2 / s2  y 2 / s2  z  2 / s1   +   +   =1  rx  r   y   rz    x = rx cos s1  cos s2  , − / 2     / 2 y = ry cos s1  sin s2  , −     z = rz sin s1  Superellipse/Superellipsoid  Used by industrial designers often OpenGL Parametric Shape Primitives  Parametric:  Cylinder  Sphere  Cone  Disk  Torus OpenGL Quadric-Surface and Cubic-Surface Functions  GLUT and GLU provide functions to draw quadric-surface objects.  GLUT functions  Sphere, cone, torus, cube  GLU functions  Sphere, cylinder, tapered cylinder, cone, flat circular ring (or hollow disk), and a section of a circular ring (or disk)  GLUT also provides a function to draw a “teapot” (modeled with bicubic surface pathces). OpenGL GLUT Shape Primitives  glutWireSphere (r, nLongitudes, nLatitudes);  glutSolidSphere (r, nLongitudes, nLatitudes);  glutWireCone(rBase, height, nLong, nLat);  glutSolidCone(rBase, height, nLong, nLat);  glutWireTorus(rCrossSection, rAxial, nConcentric, nRadial);  glutWireTorus(rCrossSection, rAxial, nConcentric, nRadial);  glutWireTeapot(size);  glutSolidTeapot(size); GLU Quadric-Surface Functions  GLU functions are slightly harder to use.  You have to assign a name to the quadric.  Activate the GLU quadric renderer  Designate values for the surface parameters  Example: GLUquadricObj *mySphere; mySphere = gluNewQuadric(); gluQuadricStyle (mySphere, GLU_LINE); gluSphere (mySphere, r, nLong, nLat); Quadric Draw Styles  Other than GLU_LINE we have the following drawing styles:  GLU_POINT  GLU_SILHOUETTE  GLU_FILL  Can be easily texture mapped!!  GLUT primitives cannot unless you use a shader Other GLU quadric objects  gluCylinder (name, rBase, rTop, height, nLong, nLat);  gluDisk (name, rInner, rOuter, nRadii, nRings);  gluPartialDisk (… parameters …); More functions for manipulating GLU quadric objects  gluDeleteQuadric (name);  gluQuadricOrientation (name, normalDirection);  To specify front/back directions.  normalVector is GLU_INSIDE or GLU_OUTSIDE  gluQuadricNormals (name, generationMode);  Mode can be GLU_NONE, GLU_FLAT, or GLU_SMOOTH based on the lighting conditions you want to use for the quadric object. Parametric Modeling: Splines  Spline interpolation:  Mathematical theory of interpolation arose from study of thin strips of wood or metal (“splines”) under various forces Parametric Modeling: Spline Curves  Use control points to specify a curve.  Intuitive interface  Curve should be smooth.  Cardinal spline, Hermite, B-spline, Bezier curve, NURBS (Non-Uniform Rational B-spline) Spline Representations  Spline curve: Curve consists of continuous curve segments approximated or interpolated on polygon control points.  Interpolated : curve passes through control points  Approximated: guided by control points but not necessarily passing through all or any of them. Interpolated Approximated Spline Continuity  Parametric equations: x = x(u), y = y(u), z = z (u), u1  u  u2  Parametric continuity: Continuity properties of curve segments.  Zero order: Curves intersects at one end-point: C0  First order: C0 and curves has same tangent at intersection: C1  Second order: C0 , C1 and curves has same second order derivative: C2  Geometric continuity:  Similar to parametric continuity but only the direction of derivatives are significant (not magnitude), less exact but less restrictive  G0, G1, G2 : zero order, first order, and second order geometric continuity. Spline Curve Equations  Cubic polynomial curve equations: x(u ) = a x u 3 + bx u 2 + c x u + d x y (u ) = a y u 3 + by u 2 + c y u + d y 0  u 1 z (u ) = a z u 3 + bz u 2 + c z u + d z ax  b   Rewrite as:  x (u ) = u 3 u 2  u 1   x  = UC  cx    d x   General Form: x(u) = U  Ms  Mg  Ms: spline transformation (blending functions)  Mg: geometric constraints (control points) Spline Surfaces  Can use a pair of curves to get a surface  Value at any point (u, v) given by product of a curve f at u and a curve g at v (sometimes  called the “tensor product”): Spline Surfaces: Bézier patches  Bézier patch is sum of (tensor) products of Bernstein bases Control points Spline Surfaces: Bézier patches  Just as we connected Bézier curves, can connect Bézier patches to get a surface:  Very easy to draw: just dice each patch into regular (u, v) grid! Spline Surfaces  There are many alternatives!  NURBS, Gregory, Pm, polar…  Tradeo#s:  degrees of freedom  continuity  difficulty of editing  cost of evaluation  generality  … Rendering of Parametric Models  Generally, provide a procedure that takes the parameters and generate a polygonal representation  May include texture maps, normal vectors, colors, etc  The procedure may be dynamic ◼ For example, adjust the polygon resolution according to distance from the viewer Subdivision Curves and Surfaces  Subdivision Curves  https://www.youtube.com/watch?v=cwXXBfqBWOs Chaikin’s Corner Cutting Algorithm Subdivision Surfaces  Alternative to spline surfaces  Take an existing mesh, increase its resolution (refine), and add curvature to the new regions (smooth)  Two flavors: approximating and interpolating  Various types: Loop, Modified Butterfly, Catmull-Clark Subdivision Surfaces: Catmull-Clark  Approximating scheme  Works on non-triangle meshes (others don’t)  Generates quads each iteration  Generate new vertex at each face centroid, then new points from edges, then update old vertices Subdivision Surfaces: Catmull-Clark  Works well on basically any mesh, loses only a small amount of volume  Now totally ubiquitous in modeling software Subdivision Surfaces: Summary Not really a parametric scheme but related to splines  Subdivision Surface Modeling Tutorial  https://www.youtube.com/watch?v=ckOTl2GcS-E&list=PL6A7DF3D7866EB076&index=7 3 - Hierarchical Modeling Hierarchical Modeling  Combine smaller/simpler shapes to construct complex objects and scenes.  Stored in trees or similar data structures (Scene Graphs)  Rendered by traversing the tree, applying the transformations, and rendering the instances  Keeping information like bounding boxes in tree nodes accelerates the operations. Scene Graphs  DAG's (Directed Acyclic Graphs) to represent entire scenes and complex objects.  Nodes:  Grouping nodes, Transform nodes, Level Of Detail nodes, Light Source nodes, Attribute nodes, State nodes.  Leaves:  Object geometric descriptions.  Available libraries: i.e. www.openscenegraph.org  Java3D is also based on Scene Graph Model  Efficient display of objects, picking objects, state change and animations. Example Scene Graph Representation G T T L T T T T G G T T T T T T T Example 1: Scene Graph Representation 51 Hierarchical Modeling: Skin and Bones  Skeleton with joined “bones” in hierarchy (scene graph)  Can add “skin” on top of bones  Automatic or hand-tuned “skinning”  Supported by Modeling Packages like Blender Skin and Bones OpenGL Support for Hierarchical Objects  OpenGL defines glPushMatrix() and glPopMatrix()  Takes the current matrix and pushes it onto a stack, or pops the matrix off the top of the stack and makes it the current matrix  Note: Pushing does not change the current matrix  Rendering a hierarchy (recursive): procedure RenderNode(tree) glPushMatrix() Apply node transformation Draw node contents RenderNode(children) glPopMatrix() 4 - Sweep Objects Sweep Objects  Define a polygon by its edges  Sweep it along a path  The path taken by the edges form a surface - the sweep surface  Special cases  Surface of revolution: Rotate edges about an axis  Extrusion: Sweep along a straight line Sweep Objects: Translational Sweep Sweep Objects: Rotational Sweep Sweep Objects General Sweeps  The sweep path maybe any 3D curve  The polygon that is swept may be transformed as it is moved along the path  i.e. Scale, rotate with respect to path orientation, …  One common way to specify is:  Give a poly-line (sequence of line segments) as the path  Give a poly-line as the profile (i.e. cross-section) shape to sweep  Give a transformation to apply at the vertex of each path segment  Problem: Can be difficult to avoid self-intersection General Sweep Example  Example: Seashells  Create3D polygonal surface models of seashells  Sweep generating curve around helico-spiral axis ◼ Helico-spiraldefinition: Qi+1 = Qi + DQ ri+1 = ri lr zi+1 = zi lz General Sweep Example  Generate Different Shells by Varying Parameters Different helico-spirals Different generating curves Rendering Sweeps  Convert to polygons 1. Break path into short segments 2. Create a copy of the sweep polygon at each segment 3. Join the corresponding vertices between the polygons  May need things like end-caps on surfaces of revolution and extrusions  Normals come from sweep polygon and path orientation  Sweep polygon defines one texture parameter, sweep path defines the other 5 - Solid Modeling Solid Modeling  Represent Solid Interiors of Objects  Surface may not be described explicitly, only implicitly Motivation  Some Acquisition Methods Generate Solids  Example: CAT scan  Some Applications Require Solids  Example: CAD/CAM A - Constructive Solid Geometry (CSG)  Based on a tree structure, like hierarchical modelling, but now:  internal nodes are set operations: ◼ union, intersection or difference  edges of the tree have transformations associated with them  leaves contain only geometry  Allows complex shapes with only a few primitives  Common primitives are cylinders, cubes, etc., or quadric surfaces  Motivated by computer aided design and manufacture  Set Difference operation is analogous to drilling or milling  A common format in CAD products A - Constructive Solid Geometry (CSG) Tree Structure A - Constructive Solid Geometry (CSG) Rendering CSG  Normals and texture coordinates typically come from underlying primitives  Some rendering algorithms can render CSG directly  e.g. Raytracing  For OpenGL and other polygon renderers, must convert CSG to polygonal representation  Must remove redundant faces, and chop faces up ◼ Basic algorithm: Split polygons until they are inside, outside, or on boundary. Then choose appropriate set for final answer.  Generally difficult, messy and slow  Numerical imprecision is the major problem Alternative: Rendering CSG with Ray Casting CSG Summary  Advantages:  Good for describing many things, particularly machined objects  Better if the primitive set is rich ◼ Early systems used quadratic surfaces  Moderately intuitive and easy to understand  Disadvantages:  Not a good match for polygon renderers  Some objects may be very hard to describe, if at all  Geometric computations are sometimes easy, sometimes hard  A volume representation (hence word Solid in the name)  Boundary (surface representation) can also work B - Spatial Enumeration: Voxels  Basic idea: Describe something by the space it occupies  For example, break the volume of interest into lots of tiny cubes, and say which cubes are inside the object and which are outside  Works well for things like medical data ◼ The process itself, like MRI or CAT scans, generates the volume ◼ Data is associated with each voxel (volume element) ◼ e.g. xray absorption  Problem to overcome:  For anything other than small volumes or low resolutions, the number of voxels explodes  Note that the number of voxels grows with the cube (3) power of linear dimension Voxels  Partition Space into Uniform Grid  Grid cells are called a voxels (like pixels)  Store Properties of Solid Object with Each Voxel  Occupancy  Color  Density  Temperature  Etc.  Precision of the scene is the size of the voxel  The more voxels you have the more precise but also the expense of memory and computation increase Voxel Acquisition  Scanning Devices  MRI  CAT  Simulation  FEM Voxel Storage  O(n3) Storage for n x n x n Grid 1 billion voxels for 1000 x 1000 x 1000 Voxel Boolean Operations  Compare Objects Voxel by Voxel Voxel Display  1 - Isosurface Rendering  Render surfaces bounding volumetric regions of constant value (e.g., density)  2 - Ray Casting (called Volume Rendering) 1 - Isosurface Rendering: 3D Marching Cubes  Set threshold T, find cubes with density values at 8 corner vertices that are both inside and outside  Construct triangles inside these cubes by interpolating along edges all 256 cases can be derived from 15 base cases 79 2 - Volume Rendering via Ray Casting  Ray Casting  Integratevoxel density along rays through voxels and map to color + opacity Voxel Representation Summary  Advantages  Simple, intuitive, unambiguous  Same complexity for all objects  Natural acquisition for some applications  Trivial boolean operations  Disadvantages  Approximate  Large storage requirements  Expensive display  Precision - no partial occupancy, so only an approximation  No analytic form for faces or surfaces  Require N3 voxels for resolution of N in each of 3 dimensions C - Octrees (3D) and Quadtrees (2D)  Build a tree where successive levels represent better resolution (smaller voxels)  Large uniform spaces result in shallow trees  Quadtree is for 2D (four children for each node)  Octree is for 3D (eight children for each node) Quadtrees & Octrees  Shape is stored in a tree structure where leaves are full(F) or empty(E) regions:  Finest resolution is determined by depth of tree Quadtrees & Octrees  Refine Resolution of Voxels Hierarchically  More concise and efficient for non-uniform objects Uniform Voxel Quadtree Quadtrees & Octrees  Quadtrees are like a spatial-occupancy enumeration with adaptive resolution (divide-and-conquer)  Net compression: O(d2) goes to O(d) for shapes (rather than patterns) Number of nodes is proportional to perimeter  Intersection, union and difference operations are easy to perform Quadtree Boolean Operations Octrees  The quadtree principle extends naturally to 3D (like adaptive sized voxels):  3 dimensions means subdivision produces 8 equal voxels  Generated from other representations  Render from front to back  visible surface determination  Logically equivalent to quadtrees so boolean operations easily possible  Explicit tree representation has high memory costs, we can use various linear encodings Rendering Octrees  Volume rendering renders octrees and associated data directly  Ray casting  Can convert to polygons by a few methods:  Just take faces of voxels that are on the boundary  Find iso-surfaces within the volume and render those  Typically do some interpolation (smoothing) to get rid of the artifacts from the voxelization  Typically render with colors that indicate something about the data, but other methods exist Aside: Spatial Data Structures  Octrees are an example of a spatial data structure  i.e. a data structure specifically designed for storing information of a spatial nature ◼ Divide space into smaller regions  In graphics, Octrees are frequently used to store information about where polygons, or other primitives, are located in a scene  Speeds up many computations by making it fast to determine when something is relevant or not  Other spatial data structures include BSP trees, KD-Trees, Interval trees, … 6 - Implicit Functions  Implicit Functions  Some surfaces can be represented as the vanishing points of implicit functions (defined over 3D space)  i.e. set of all points (x,y,z) where function f(x,y,z)=0  Some objects are easy represent this way  Spheres, ellipses, and similar  More generally, quadratic surfaces:  Shapes depends on all the parameters a, b, c, d, e, f, g 2 + ax+ bx2 + cy+ dy2 + ez + fz g=0  Note that some implicitly defined surfaces also have a parametric representation (spheres, cylinders etc.) Implicit Functions Level sets in physical simulation  See http://physbam.stanford.edu Example Quadrics Blobs and Metaballs  Define the location of some points, each representing center of a “blob”  For each blob center point, define a function on the distance to any given point p(x,y,z)  typically p(x,y,z) points are vertices of a grid  Sum these functions up  More generally, use Gaussian functions of distance, or other forms  Various results are called blobs or metaballs Blobs and Metaballs  Known as blobby models  Useful for modeling soft curving objects: e.g. muscles for humans, animals  Have equations of the form: where f(r) is the density function, rk is the kth blob center (xk, yk zk), r - rk is the distance from the point p to blob center, bk is a scale factor controlling the blob size  Surfaces are then generated for a given density T (levelset) Blobs and Metaballs  Density functions can be exponential: Examples: Blobs and Metaballs Examples: Blobs and Metaballs 99 Blobs and Metaballs  Image courtesy Spencer Arts  Muscular structure is created using Metareyes plug-in and involved creating hundreds of metaballs. Rendering Implicit Surfaces  Some methods can render them directly  Raytracing - find intersections with Newton’s method  For polygonal renderer, must convert to polygons  Advantages:  Good for organic looking shapes e.g. human body  Reasonable interfaces for design  Disadvantages:  Difficult to render and control when animating  Has been replaced with subdivision surfaces? 7 - Procedural Modeling Procedural Modeling  Uses procedural rules (algorithm) to evolve/grow objects  Algorithms for trees, mountains, grass, fur, lightning, fire, …  Iterative application of rules is typical  Possibilities include:  Procedural grammars where rules may be applied deterministically or stochastically  Modeling physical laws of motion and forces, such as attraction/repulsion between particles  Iterative evaluation of mathematical functions such as fractals Procedural Modeling  Best for Models Resulting from...  Repeating processes  Self-similar processes  Random processes  Advantages:  Automatic generation  Concise representation  Parameterized classes of models Procedural Grammars: Production Rules  Model object by giving a set of rules to follow to generate it  Works best for things like plants:  Start with a stem  Replace it with stem + branches  Replace some part with more stem + branches, and so on  Essentially, generate a string that describes the object by replacing sub-strings with new sub-strings  Render by generating geometry of each object part  Parametric instances of branch, leaf, flower, etc  Or polygons, or blobs, or …  Can work for whole gardens and forests Grammar  Generate Description of Geometric Model by Applying Production Rules  Useful for creating plants ◼ Example: Tree → Branch Tree | Leaf Branch → Cylinder | [ Tree ] C[*]C[*][*] C[CL]C[C[CL][CL]]C[[CL][CL]] L-Systems  Images: Przemyslaw Prusinkiewicz, University of Calgary, Canada L-Systems Fractals  Shape is self-similar across scales.  Zooming in, the shape (statistically) looks the same.  Example: Mountain.  Zoom in and boulders look like mountain.  Many real objects have fractal appearance. Fractal  Defining Property:  Self-similar with infinite resolution Mandelbrot Set Fractal Generation  Deterministically Self-Similar Fractals  Parts are scaled copies of original ◼ Initiator: start with a shape ◼ Generator: replace subparts with scaled copy of original  Statistically Self-Similar Fractals  Parts have same statistical properties as original ◼ Initiator: start with a shape ◼ Generator: replace subparts with a self-similar random pattern Deterministically Self-Similar Fractal  Useful for Creating Interesting Shapes Statistically Self-Similar Fractal  Useful for Creating Mountains  Useful for Creating 3D Plants Make Fractal Example: Random Mid-point Variation  Find the midpoint of an edge A-B. Add a random factor and divide the edge in two as: A-M, M-A at each step.  Useful for height maps, clouds, plants.  2D: r is a random number selected xm = ( x A + xB ) / 2 from Gaussian distribution with ym = ( y A + y B ) / 2 + r mean 0 and variance that depends on D and the length between end points  3D: For corners of a square: A, B, C, D A B Z AB = ( Z A + Z B ) / 2 + r , Z BC = ( Z B + Z C ) / 2 + r , M Z CD = ( Z C + Z D ) / 2 + r , Z DA = ( Z D + Z A ) / 2 + r , Z M = ( Z AB + Z BC + Z CD + Z DA ) / 4 + r , D C Random Mid-point Variation Statistically Self-Similar Fractals Example Program  Terrain generation using random midpoint displacement (diamond square algorithm): Terrain.zip 117 8 - AI Generated Objects AI Generators  https://www.unite.ai/best-ai-3d-object-generators/  Examples:  AI-powered text-to-3D generation  2D image to 3D model generator  Deep convolutional network to extract the depth information from an image and create a point cloud representation of the 3D object.