Transcript Lecture notes

Last Time
• Intro to modeling
• Issues in evaluating modeling techniques:
–
–
–
–
–
–
How well does it represent objects?
What types of objects can it represent?
How easy is it to render?
How compact is it?
How easy is it to create/modify?
How easy is it to perform geometric computations?
• Polygonal modeling
– A multitude of ways to represent polygonal models and associated
data
04/11/02
(C) 2002 University of Wisconsin
Today
• A menagerie of other modeling techniques
• Homework 5
04/11/02
(C) 2002 University of Wisconsin
More Object Representations
•
•
•
•
•
•
•
Parametric instancing
Hierarchical modeling
Constructive Solid Geometry
Sweep Objects
Octrees
Blobs and Metaballs and other such things
Production rules
04/11/02
(C) 2002 University of Wisconsin
Parametric Instancing
• Many things, called primitives, are conveniently described
by a label and a few parameters
– Cylinder: Radius, length, does it have end-caps, …
– Bolts: length, diameter, thread pitch, …
– Other examples?
• This is a modeling format:
– Provide software that knows how to draw the object given the
parameters, or knows how to produce a polygonal mesh
– How you manage the model depends on the rendering style
– Can be an exact representation
04/11/02
(C) 2002 University of Wisconsin
Rendering Instances
• Generally, provide a routine that takes the parameters and
produces a polygonal representation
– Conveniently brings parametric instancing into the rendering
pipeline
– May include texture maps, normal vectors, colors, etc
– OpenGL utility library (GLu) defines routines for cubes, cylinders,
disks, and other common shapes
– Renderman does similar things, so does POVray, …
• The procedure may be dynamic
– For example, adjust the polygon resolution according to distance
from the viewer
04/11/02
(C) 2002 University of Wisconsin
OpenGL Support
• OpenGL defines display lists for encapsulating commands
that are executed frequently
– Not exactly parametric instancing, because you are very limited in
the parameters
list_id = glGenLists(1);
glNewList(list_id, GL_COMPILE);
glBegin(GL_TRIANGLES);
draw some stuff
glEnd();
glEndList();
And later
glCallList(list_id);
04/11/02
(C) 2002 University of Wisconsin
Display Lists (2)
• The list can be:
– GL_COMPILE: things don’t get drawn, just stored
– GL_COMPILE_AND_EXECUTE: things are drawn, and also stored
• The list can contain almost anything:
– Useful for encapsulating lighting set-up commands
– Cannot contain vertex arrays and other client state
• The list cannot be modified after it is compiled
– The whole point is that the list may be internally optimized, which
precludes modification
– For example, sequences of transformations may be composed into
one transformation
04/11/02
(C) 2002 University of Wisconsin
Display Lists (3)
• When should you use display lists:
– When you do the same thing over and over again
• Advantages:
– Can’t be much slower than the original way
– Can be much much faster
• Disadvantages:
– Doesn’t support real parameterized instancing, because you can’t
have any parameters (except transformations)!
– Can’t use various commands that would offer other speedups
• For example, can’t use glVertexPointer()
04/11/02
(C) 2002 University of Wisconsin
Hierarchical Modeling
• A hierarchical model unites several parametric instances
into one object
– For example: a desk is made up of many cubes
– Other examples?
• Generally represented as a tree, with transformations and
instances at any node
• Rendered by traversing the tree, applying the
transformations, and rendering the instances
• Particularly useful for animation
– Human is a hierarchy of body, head, upper arm, lower arm, etc…
– Animate by changing the transformations at the nodes
04/11/02
(C) 2002 University of Wisconsin
Hierarchical Model Example
Draw body
xarm
l
left arm
Rotate about shoulder
Draw upper arm
Translate (l,0,0)
Rotate about origin of
lower arm
Draw lower arm
04/11/02
Vitally Important Point:
•Every node has its own
local coordinate system.
•This makes specifying
transformations much
much easier.
(C) 2002 University of Wisconsin
OpenGL Support
• 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):
RenderNode(tree)
glPushMatrix()
Apply node transformation
Draw node contents
RenderNode(children)
glPopMatrix()
04/11/02
(C) 2002 University of Wisconsin
Regularized Set Operations
• Hierarchical modeling is not good enough if objects in the
hierarchy intersect each other
– Transparency will reveal internal surfaces that should not exist
– Computing properties like mass may count the same volume twice
• Solution is to define regularized set operations:
– Just a fancy name
– Every object must be a closed volume (mathematically closed)
– Define mathematical set operations (union, intersection, difference,
complement) to the sets of points within the volume
04/11/02
(C) 2002 University of Wisconsin
Constructive Solid Geometry (CSG)
• Based on a tree structure, like hierarchical modeling, but
now:
– The internal nodes are set operations: union, intersection or
difference (sometimes complement)
– The edges of the tree have transformations associated with them
– The 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
– Difference is like drilling or milling
– A common format in CAD products
04/11/02
(C) 2002 University of Wisconsin
CSG Example
-
Fill it in!
scale
translate
-

cube

scale
translate
scale
translate
cylinder cylinder
04/11/02
(C) 2002 University of Wisconsin
Rendering CSG
• Normals and texture coordinates typically come from underlying
primitives (not a big deal with CAD)
• Some rendering algorithms can render CSG directly
– Raytracing (later in the course)
– Scan-line with an A-buffer
– Can do 2D with tesselators in OpenGL
• 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
04/11/02
(C) 2002 University of Wisconsin
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 solid in the name)
– Boundary (surface representation) can also work
04/11/02
(C) 2002 University of Wisconsin
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
04/11/02
(C) 2002 University of Wisconsin
General Sweeps
• The path maybe any curve
• The polygon that is swept may be transformed as it is
moved along the path
– 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 shape to sweep
– Give a transformation to apply at the vertex of each path segment
• Difficult to avoid self-intersection
04/11/02
(C) 2002 University of Wisconsin
Rendering Sweeps
• Convert to polygons
–
–
–
–
Break path into short segments
Create a copy of the sweep polygon at each segment
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
04/11/02
(C) 2002 University of Wisconsin
Spatial Enumeration
• 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
– Works well for things like medical data
• The process itself, like MRI or CAT scans, enumerates the volume
• Data is associated with each voxel (volume element)
• 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 of linear
dimension
04/11/02
(C) 2002 University of Wisconsin
Octrees (and Quadtrees)
• 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)
04/11/02
(C) 2002 University of Wisconsin
Quadtree Example
top left
top right bot left
bot right
Octree principle is the same, but there are 8 children
04/11/02
(C) 2002 University of Wisconsin
Rendering Octrees
• Volume rendering renders octrees and associated data
directly
– A special area of graphics, visualization, not covered in this class
• 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
04/11/02
(C) 2002 University of Wisconsin
Spatial Data Structures
• Octrees are an example of a spatial data structure
– A data structure specifically designed for storing information of a spatial
nature
• eg Storing the location of fire hydrants in a city
• 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
– Just like BSP trees speed up visibility
• Other spatial data structures include BSP trees, KD-Trees,
Interval trees, …
04/11/02
(C) 2002 University of Wisconsin
Implicit Functions
• Some surfaces can be represented as the vanishing points of
functions (defined over 3D space)
– Places where a function f(x,y,z)=0
• Some objects are easy represent this way
– Spheres, ellipses, and similar
– More generally, quadratic surfaces:
ax 2  bx  cy 2  dy  ez 2  fz  g  0
– Shapes depends on all the parameters a,b,c,d,e,f,g
04/11/02
(C) 2002 University of Wisconsin
Blobs and Metaballs
• Define the location of some points
• For each point, define a function on the distance to a given
point, (x,y,z)
• Sum these functions up, and use them as an implicit
function
• Question: If I have two special points, in 2D, and my
function is just the distance, what shape results?
• More generally, use Gaussian functions of distance, or other
forms
– Various results are called blobs or metaballs
04/11/02
(C) 2002 University of Wisconsin
Example with Blobs
Rendered
with POVray. Not
everything
a blob, but the characters are.
04/11/02
(C) 2002
University is
of Wisconsin
Rendering Implicit Surfaces
• Some methods can render then directly
– Raytracing - find intersections with Newton’s method
• For polygonal renderer, must convert to polygons
• Advantages:
– Good for organic looking shapes eg human body
– Reasonable interfaces for design
• Disadvantages:
– Difficult to render and control when animating
– Being replaced with subdivision surfaces, it appears
04/11/02
(C) 2002 University of Wisconsin
Production Rules
• Model 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
– Parametric instances of branch, leaf, flower, etc
– Or polygons, or blobs, or …
• Can work for whole gardens and forests
04/11/02
(C) 2002 University of Wisconsin
L-Systems Generator
04/11/02
(C) 2002 University of Wisconsin
Prusinkiewicz, Hammel, Mech http://www.cpsc.ucalgary.ca/projects/bmv/vmm/title.html
L-Systems
04/11/02
(C) 2002 University of Wisconsin
Prusinkiewicz, Hammel, Mech http://www.cpsc.ucalgary.ca/projects/bmv/vmm/title.html
More L-Systems
Prusinkiewicz,
Hammel, Mech http://www.cpsc.ucalgary.ca/projects/bmv/vmm/title.html
04/11/02
(C) 2002 University of Wisconsin
Yet More L-systems
Prusinkiewicz,
Hammel, Mech http://www.cpsc.ucalgary.ca/projects/bmv/vmm/title.html
04/11/02
(C) 2002 University of Wisconsin