Procedural Modeling and Metaballs Quiz

Object Modelling

• Object modelling is the process of describing an object's shape, appearance, and behavior. Shape is a central theme. It's also known as shape representation or shape modelling.
• Sometimes, the description is the final product, as in Computer Aided Design (CAD) and Computer Aided Manufacturing (CAM). These models are precise descriptions.
• In graphics, the model is often used for rendering. In this case, the model's purpose is to create an image, which may be an approximation as long as the visual result is satisfactory.
• A historical computer graphics motto was "If it looks right, it is right". This is not sufficient for CAD.
• More recently, simulating physics and using AI are important for creating realistic appearance and behaviour.

Issues in Shape Modelling

• There are many ways to represent an object's shape.
• Key considerations when choosing a representation include accuracy, rendering ease (converting to polygons), storage/transmission efficiency, creation ease (by hand, procedurally, or from measurements), interaction ease (modification and animation), geometric computation ease (distance, intersections, normal vectors, curvature), and smoothness.

Choosing a Representation Scheme

• How accurately represents the object?
• How easy is it to render or convert to polygons?
• How compact is it (to store and transmit)?
• How easy is it to create? (by hand, procedurally, measurements)
• How easy to interact with? (modification, animation)
• How easy to perform geometric computations (distance, intersection, normals, curvature)?
• How smooth is it?

Categorizing Shape Representation Schemes

• 1. Surface vs. Volume:

  • Often, only the surface is important (for rendering and calculations)
  • Sometimes, the volume (inside) is needed (medical data)
  • Some representations focus on the filled space rather than the surface.

• 2. Parametric vs. Implicit:

• Parametric representations generate points on a surface or volume by plugging in parameters (equations). This is useful in cases where continuity (smoothness) is critical.

  • Examples: spheres, cylinders
  • Use of Spline Curves/Surfaces (Bezier, B-splines, NURBS)

• Implicit representations define a surface via an equation where any point inside/on/outside the surface satisfies the equation (e.g. X^2 + Y^2 + Z^2=r2 = Sphere)

Shape Representation Schemes

• Polygon Mesh:
  • A set of adjacent polygons representing the object's exterior.
  • Operations are linear and fast.
  • Can approximate non-polyhedron shapes.
  • Smoothness is achieved via more polygons or interpolated shading.

Polygons Dominate

• Everything can be approximated by polygons.
• Polygons are fast to render.
• Many operations on polygons are simple.
• Memory and disk space for polygons is efficient.
• Polygons are simple and common in practice.

Polygons Aren't Great

• Polygons are approximations of curved surfaces.
• Accuracy can be improved by increasing the number of polygons
• Normal vectors are approximate
• Information is lost using polygons that are not perfect shapes.
• Many real-world surfaces are curved.
• Polygons can be very unstructured (irregular shapes)

Parametric Modeling

• Many objects (primaries) are simply described by a label and parameters.
  • Examples include cylinder (radius, height), bolts (length, diameter, pitch)
• Software functions convert parameters into triangle/quad mesh.
• Parameterization enables exact representations via equations.
• Derivatives give exact normal vectors.
• Often defined by equations (e.g., sphere). Useful for modeling surfaces where continuity is important
  • Examples: spheres, cylinders
  • Use of spline curves/surfaces (Bezier, B-splines, NURBS, B-splines)

Example of Parametric Modelling: Quadric Surfaces

• Described by second-degree (quadric) equations.
  • Includes spheres, ellipsoids, tori, paraboloids, hyperboloids

Example: Sphere

• The parametric equation for a sphere uses spherical coordinates.
• An implicit equation for a sphere is X^2 + Y^2 + Z^2 = R^2.

Cylinder

• Parametric equations for a cylinder use parameters to describe its position and size along a given axis
  • x = r cos (2πu)
  • y = r sin (2πu)
  • z = vh

Example: Ellipsoid

• Ellipsoids are defined by an equation involving squared components.
  • Implicit equation: (x/rx)^2 +(y/ry)^2 +(z/rz)^2 = 1
  • Parametric equation using spherical coordinates:
    • x = rx cos(φ) cos(θ)
    • y = ry cos(φ) sin(θ)
    • z = rz sin(φ)

Example: Superellipse / Superellipsoid

• Parametric/Implicit equation is used by industrial designers frequently.

OpenGL Parametric Shape Primitives

• Cylinder
• Sphere
• Cone
• Disk
• Torus

OpenGL Quadric-Surface and Cubic-Surface Functions

• Provide functions to draw quadric surfaces.
  • Also has functions for spheres, cones, tori, cubes, cylinders, tapered cylinders, cones, circular rings, flat circular rings, and sections of circular rings
  • Has a function to draw a "teapot".

OpenGL GLUT Primitive Functions

• Provides functions for wireframe and solid shape primitives (spheres, cones, tori, etc.).

GLU Quadric-Surface Functions

• These functions use names for the quadric object.
• The function needs to:
  • Be initialized.
  • Be given parameters (eg. radius, radius, etc).

Quadric Draw Styles

• Drawing styles for quadrics beyond GLU_LINE (GLU_POINT, GLU_SILHOUETTE, GLU_FILL)
• Easy texture mapping.

Other GLU Quadric Objects

• Functions for drawing other quadric objects (gluCylinder, gluDisk, gluPartialDisk).

More Functions for Manipulating GLU Quadric Objects

• Functions for deleting quadrics (gluDeleteQuadric).
• Functions to set orientation (gluQuadricOrientation)
• Function to set normals (gluQuadricNormals)

Parametric Modeling: Splines

• Spline interpolation from thin strips of wood (or metal).
• Defines a curve using control points.
• Defines curves, including Cardinal splines, Hermite, B-spline, Bezier curve and NURBS

Spline Representations

• Splines approximate or interpolate curves defined by control points.

Spline Continuity

• Zero order: Curves intersect at one end point.
• First order: Curves have the same tangent at points that intersect.
• Second order: Same second derivative at intersection points
• Geometric Continuity (G⁰, G¹,G²): Similar to parametric continuity, focusing on continuity of direction (or derivatives)

Spline Curve Equations

• Use cubic polynomial curve equations.
• General form: X(u) = ∑(i=0 to 3) Mᵢᵤᵢ where M represents the control points.

Spline Surfaces

• Surfaces formed from a pair of curves.

Spline Surfaces: Bézier Patches

• Bézier patches formed using Bernstein
• Basis functions from a specific set of control points

Sweep Objects

• Define a polygon by its edges.
• Sweep the polygon along a path to create a surface (the sweep surface).

Special Sweep Cases

• Surface of revolution: Rotate the edges around an axis.
• Extrusion: Sweep the polygon along a straight line to create a solid.

General Sweeps

• Sweep path to determine the type of sweep.
• Transforming by scaling and rotations/rotations with respect to path orientation.
• Polygon that is swept can be transformed.
• Give a poly-line as the path, poly-line as the profile, and transformation to apply at the vertices of each path segment.
• Difficult to avoid self-intersection.

General Sweep Example: Seashells

• Create 3D polygonal surface models of seashells
• Sweep generating curve around helico-spiral axis

Rendering Sweeps

• Convert to polygons by breaking paths into segments
• Create copies of polygons
• Connect corresponding vertices between segments
• May require end-caps (for shapes of revolution, extrusions).

Solid Modelling

• Represents the solid interiors of the objects
• Surface definition might only be implied.

Motivation

• Some acquisition methods generate solids (e.g., CAT scan).
• Some applications (e.g, CAD/CAM) require solid representations.

A - Constructive Solid Geometry (CSG)

• A tree-based approach for defining 3D objects.
• Internal nodes are set operations. Each leaf node represents a geometric shape.
• Edges can have transformations.
• Defines complex objects by combining simple primitives (cylinders, cubes, or quadric surfaces).
• Motivated by computer aided design and manufacture.
• Set operations provide analogies to design tools (drilling/milling).

Rendering CSG

• Convert to polygons to use existing rendering systems.
• Removing redundant faces is critical.
• Basic algorithm: Split polygons until they are classified as inside, outside, or on surfaces. Then select appropriate subsets.
• Numerical imprecision can be a serious issue.

Alternative: Rendering CSG with Ray Casting

• A different approach for rendering CSG structures.
• Rendering done using raycasting (beams that trace between points).

CSG Summary

• Advantages: Good for easily defined machined objects, rich primitives, intuitive approach
• Disadvantages: Not ideal in all scenarios; some objects are challenging to represent, computing with them may be easy or hard.
• It uses a volume implementation (in relation to the word 'solid'). A boundary (surface representation of object) can also work.

B - Spatial Enumeration: Voxels

• Describe an object by the space it occupies using tiny cubes (voxels). Useful for medical data (MRI/CAT scans).
• Associated data with each voxel (e.g., x-ray absorption).
• Problem: The number of voxels expands rapidly for anything other than small volume/low resolution objects

Voxels

• Partitioning 3D space into uniform grids (voxels).
• Storing properties: Occupancy, Color, Density, Temperature, etc
• Precision is affected by voxel size.
• The more voxels increases precision, and increases memory and computation.

Voxel Acquisition

• Methods for acquiring voxel data (e.g., MRI, CAT scans).

Voxel Storage

• Storage complexity is proportional to the cubic of the grid resolution.
• Storage costs for very high resolution voxel datasets can be tremendous.

Voxel Boolean Operations

• Comparing objects voxel by voxel using boolean operations (union, difference).
• Simple operations in voxel space.

Voxel Display

• 1. Isosurface Rendering:
  • Render surfaces that bound regions of constant value (e.g., density, color).
    • Uses algorithms like 3D marching cubes.
• 2. Ray Casting: also known as volume rendering
  • Integrate voxel values along rays to color the object.

1 - Isosurface Rendering: 3D Marching Cubes

• Set threshold
• Identify cubes where density values change (inside/outside).
• Construct triangles inside/on surfaces of each cube.

2 - Volume Rendering via Ray Casting

• Integrate voxel density along rays to get color and opacity.

Voxel Representation Summary

• Advantages: Simple, easy to represent, natural data acquisition for specific applications (e.g., medical), straightforward comparisons.
• Disadvantages: Approximate, consumes lots of memory, precision limitations are evident
• Memory usage grows proportionally to the cube of linear dimension

C - Octrees (3D) and Quadtrees (2D)

• Space subdivision into smaller regions, progressively improving resolution
• Quadtrees are used for 2-dimensional space, octrees for 3-dimensional space.
• Structure is a tree with nodes.
• Non-uniform space can be represented efficiently (e.g., non-uniform object).

Quadtrees & Octrees

• Shapes (full/empty regions) are represented in hierarchical tree structures.
• Resolution or refinement depends on the depth of the tree.
• More efficient for non-uniform objects.
• The number of nodes varies directly proportional to perimeter/boundary (versus area)

Quadtrees & Octrees (Boolean operations)

• Boolean operations (intersection, union, difference) are easily performed.

Rendering Octrees

• Volume rendering method renders octrees directly.
• Ray casting is a common technique.

Octrees (rendering).

• Converting to polygons can be done via multiple methods to produce boundary polygons
• Isosurface determination often used.

Aside: Spatial Data Structures

• Octrees are spatial structures for storing spatial information (polygons, other objects).
• Dividing space into smaller regions. Useful in graphics for rendering information about where things are located (shapes objects, etc)

6 - Implicit Functions

• Represent surfaces as vanishing points of implicit functions.
  • Functions are defined over 3D space for implicit modelling
  • e.g., f(x,y,z)=0 is defined for all values (x,y,z).
• Easy to represent spheres, ellipses and other similar shapes.
• More generally useful in representing quadric-based surfaces (shapes depend on their parameters).
• It is important to note that implicitly defined surfaces often have parametric representations as well (e.g., spheres, cylinders).

Blobs and Metaballs

• Define blobs by using points (center points) each representing a specific type of 'blob'.
• Define functions for distance around each center point.
• Sum these functions.
• Blobs/Metaballs are generally constructed using Gaussian functions of distance, or another type of mathematical form.

Blobs and Metaballs (Equations)

• Blobby/Metaball objects are described by functions,
• g(x,y,z) = ∑Bk f(r-rₖ) -T = 0

Blobs and Metaballs (Density Functions)

• Density functions (often exponential functions) are used.

Examples: Blobs and Metaballs

• Many different types of blob/metaball models
  • Images provided in the slides show examples.

Rendering Implicit Surfaces

• Some methods render implicit surfaces directly (e.g., raytracing).
• Polygonal renderers must convert to polygons.
• Advantages: Useful for natural looking shapes (e.g., organic shapes, human body).
• Disadvantages: Difficult to render/animate, common limitation/issue in animating.

7 - Procedural Modeling

• Procedural modeling uses rules to generate objects.
  • Often used in generating objects iteratively
• Procedural rules are algorithms used in creating objects (e.g. trees, mountains, grass, fur, lightning, fire, etc)
• Rules can be deterministic or stochastic

Procedural Modeling (Possibilities)

• Procedural grammars: Models may be generated with a certain stochastic rule/approach (probabilistic).
• Physical laws: Uses laws of motion (attraction/repulsion) like those between particles.
• Mathematical functions: Iterative procedures based on maths or functions (fractals, which are often self-similar objects)

Procedural Modeling (Advantages)

• Automatic object generation.
• Concise object representations, using relatively few parameters to generate quite complex shapes
• Parameterized models for large groups or families of similar objects, with adjustments on a small number of parameters

Procedural Grammars: Production Rules

• Describing objects by defining rules or a grammar (used in creating plants).

Grammar

• Generate a description of a model by using production rules based on other objects (e.g. for plants: Tree-> Branch | Tree | Leaf; Branch -> Cylinder | Tree|...).

L-Systems

• A procedural language used to create biological structures
  • Image provided in the slides show examples.

L-Systems (Images)

• Examples from the course slides shows examples of plants (bluebells, cacti, lilacs, etc).

Fractals

• Fractals have self-similarity across scales.
  • Magnifying a small part of the fractal statistically appears the same as the whole fractal

Fractal Generation

 - **Deterministic:** Subparts are exact or scaled copies


 - **Statistical**: Subparts random patterns

Example: Random Mid-point Variation

• A method to generate height maps (mountains, clouds) or plants using random variables and recursive steps.

Statistically Self-Similar Fractal

• Use in creating 3D mountains, and plants.

8 - Al Generated Objects

• AI can be used to create 3D objects from text-to-3D
• It's also possible to generate 3D shapes from 2D images
• Methods like deep convolutional networks are used to extract 3D information from 2D images.

Test your knowledge on the characteristics of density functions, rendering methods for implicit surfaces, and the advantages and disadvantages of using metaballs in animation. Dive into procedural modeling and explore the rules applied to evolve or grow objects. This quiz is perfect for students of computer graphics.