Transcript Modelling with Polygons

3D Modeling
Modeling Overview
• Modeling is the process of describing an object
• Sometimes the description is an end in itself
– eg: 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 (we will work on this assumption)
– The model only exists to produce a picture
– It can be an approximation, as long as the visual result is good
• The computer graphics motto: “If it looks right it is right”
– Doesn’t work for CAD
Issues in 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
•
•
•
•
How well 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, …
Categorizing Modeling Techniques
• Surface vs. Volume
– Sometimes we only care about the surface
• Rendering and geometric computations
– Sometimes we want to know about the volume
• 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
• Parametric vs. Implicit
– Parametric generates all the points on a surface (volume) by
“plugging in a parameter” eg (sin cos, sin sin, cos)
– Implicit models tell you if a point in on (in) the surface (volume) eg
x2 + y2 + z2- 1 = 0
Techniques We Will Examine
• Polygon meshes
– Surface representation, Parametric representation
• Prototype instancing and hierarchical modeling
– Surface or Volume, Parametric
• Volume enumeration schemes
– Volume, Parametric or Implicit
• Parametric curves and surfaces
– Surface, Parametric
• Subdivision curves and surfaces
• Procedural models
Polygon Modeling
• Polygons are the dominant force in modeling for
real-time graphics
• Why?
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
What’s Bad About Polygons?
• What are some disadvantages of polygonal
representations?
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, for instance
Properties of Polygon Meshes
• Convex/Concave
– Convexity makes many operations easier:
• Clipping, intersection, collision detection, rendering, volume
computations, …
• Closed/Open
– Closed if the polygons as a group contain a closed space
• Can’t have “dangling edges” or “dangling faces”
• Every edge lies between two faces
– Closed also referred to as watertight
• Simple
– Faces intersect each other only at edges and vertices
– Edges only intersect at vertices
Polygonal Data Structures
• There are many ways to store a model made up of polygons
– Choice affects ease of particular operations
– There is no one best way of doing things, so choice depends on
application
• There are typically three components to a polygonal model:
– The location of the vertices
– The connectivity - which vertices make up which faces
– Associated data: normals, texture coordinates, plane equations, …
• Typically associated with either faces or vertices
Polygon Soup
• Many polygon models are just lists of polygons
struct Vertex {
float coords[3];
}
struct Triangle {
struct Vertex verts[3];
}
struct Triangle mesh[n];
glBegin(GL_TRIANGLES)
for ( i = 0 ; i < n ; i++ )
{
glVertex3fv(mesh[i].verts[0]);
glVertex3fv(mesh[i].verts[1]);
glVertex3fv(mesh[i].verts[2]);
}
glEnd();
Important Point: OpenGL, and
almost everything else, assumes
a constant vertex ordering:
clockwise or counter-clockwise.
Default, and slightly more
standard, is counter-clockwise
Polygon Soup Evaluation
• What are the advantages?
• What are the disadvantages?
Polygon Soup Evaluation
• What are the advantages?
– It’s very simple to read, write, transmit, etc.
– A common output format from CAD modelers
– The format required for OpenGL
• BIG disadvantage: No higher order information
– No information about neighbors
– No open/closed information
– No guarantees on degeneracies
Vertex Indirection
v0
v4
v1
v2
vertices
faces
0
2
1
v0 v1 v2 v3 v4
0
1
4
1
2
3
1
3
4
v3
• There are reasons not to store the vertices explicitly at each polygon
– Wastes memory - each vertex repeated many times
– Very messy to find neighboring polygons
– Difficult to ensure that polygons meet correctly
• Solution: Indirection
– Put all the vertices in a list
– Each face stores the list indices of its vertices
• Advantages? Disadvantages?
Indirection Evaluation
• Advantages:
– Connectivity information is easier to evaluate because vertex
equality is obvious
– Saving in storage:
• Vertex index might be only 2 bytes, and a vertex is probably 12 bytes
• Each vertex gets used at least 3 and generally 4-6 times, but is only
stored once
– Normals, texture coordinates, colors etc. can all be stored the same
way
• Disadvantages:
– Connectivity information is not explicit
OpenGL and Vertex Indirection
struct Vertex {
float coords[3];
}
struct Triangle {
GLuint verts[3];
}
struct Mesh {
struct Vertex vertices[m];
struct Triangle triangles[n];
}
Continued…
OpenGL and Vertex Indirection (v1)
glEnableClientState(GL_VERTEX_ARRAY)
glVertexPointer(3, GL_FLOAT, sizeof(struct Vertex),
mesh.vertices);
glBegin(GL_TRIANGLES)
for ( i = 0 ; i < n ; i++ )
{
glArrayElement(mesh.triangles[i].verts[0]);
glArrayElement(mesh.triangles[i].verts[1]);
glArrayElement(mesh.triangles[i].verts[2]);
}
glEnd();
OpenGL and Vertex Indirection (v2)
glEnableClientState(GL_VERTEX_ARRAY)
glVertexPointer(3, GL_FLOAT, sizeof(struct Vertex),
mesh.vertices);
for ( i = 0 ; i < n ; i++ )
glDrawElements(GL_TRIANGLES, 3, GL_UNSIGNED_INT,
mesh.triangles[i].verts);
•
•
•
•
Minimizes amount of data sent to the renderer
Fewer function calls
Faster!
Another variant restricts the range of indices that can be used - even
faster because vertices may be cached
• Can even interleave arrays to pack more data in a smaller space
Yet More Variants
• Many algorithms can take advantage of neighbor
information
– Faces store pointers to their neighbors
– Edges may be explicitly stored
– Helpful for:
•
•
•
•
•
Building strips and fans for rendering
Collision detection
Mesh decimation (combines faces)
Slicing and chopping
Many other things
– Information can be extracted or explicitly saved/loaded
Normal Vectors
• Normal vectors give information about the true surface
shape
• Per-Face normals:
– One normal vector for each face, stored as part of face
– Flat shading
• Per-Vertex normals:
–
–
–
–
A normal specified for every vertex (smooth shading)
Can keep an array of normals analogous to array of vertices
Faces store vertex indices and normal indices separately
Allows for normal sharing independent of vertex sharing
A Cube
Vertices:
(1,1,1)
(-1,1,1)
(-1,-1,1)
(1,-1,1)
(1,1,-1)
(-1,1,-1)
(-1,-1,-1)
(1,-1,-1)
Normals:
(1,0,0)
(-1,0,0)
(0,1,0)
(0,-1,0)
(0,0,1)
(0,0,-1)
Faces ((vert,norm), …):
((0,4),(1,4),(2,4),(3,4))
((0,0),(3,0),(7,0),(4,0))
((0,2),(4,2),(5,2),(1,2))
((2,1),(1,1),(5,1),(6,1))
((3,3),(2,3),(6,3),(7,3))
((7,5),(6,5),(5,5),(4,5))
Computing Normal Vectors
• Many models do not come with normals
– Models from laser scans are one example
• Per-Face normals are easy to compute:
– Get the vectors along two edges, cross them and normalize
• For per-vertex normals:
– Compute per-face normals
– Average normals of faces surrounding vertex
• A case where neighbor information is useful
– Question of whether to use area-weighted samples
– Can define crease angle to avoid smoothing over edges
• Do not average if angle between faces is greater than crease angle
Storing Other Information
• Colors, Texture coordinates and so on can all be treated like
vertices or normals
• Lighting/Shading coefficients may be per-face or per-object,
rarely per vertex
• Key idea is sub-structuring:
–
–
–
–
Faces are sub-structure of objects
Vertices are sub-structure of faces
May have sub-objects
Associate data with appropriate level of substructure
Indexed Lists vs. Pointers
• Previous example have faces storing indices of vertices
– Access a face vertex with: mesh.vertices[mesh.faces[i].vertices[j]]
– Lots of address computations
– Works with OpenGL’s vertex arrays
• Can store pointers directly
–
–
–
–
–
–
Access a face vertex with: *(mesh.faces[i].vertices[j])
Probably faster because it requires fewer address computations
Easier to write
Doesn’t work directly with OpenGL
Messy to save/load (pointer arithmetic)
Messy to copy (more pointer arithmetic)
Vertex Pointers
struct Vertex {
float coords[3];
}
struct Triangle {
struct Vertex *verts[3];
}
struct Mesh {
struct Vertex vertices[m];
struct Triangle faces[n];
}
glBegin(GL_TRIANGLES)
for ( i = 0 ; i < n ; i++ )
{
glVertex3fv(*(mesh.gaces[i].verts[0]));
glVertex3fv(*(mesh.gaces[i].verts[1]));
glVertex3fv(*(mesh.gaces[i].verts[2]));
}
glEnd();
Meshes from Scanning
• Laser scanners sample 3D positions
–
–
–
–
One method uses triangulation
Another method uses time of flight
Some take images also for use as textures
Famous example: Scanning the David
• Software then takes thousands of points and builds a
polygon mesh out of them
• Research topics:
– Reduce the number of points in the mesh
– Reconstruction and re-sampling!
Scanning in Action
http://www-graphics.stanford.edu/projects/mich/
Level Of Detail
• There is no point in having more than 1 polygon per pixel
– Or a few, if anti-aliasing
• Level of detail strategies attempt to balance the resolution of
the mesh against the viewing conditions
– Must have a way to reduce the complexity of meshes
– Must have a way to switch from one mesh to another
– An ongoing research topic, made even more important as laser
scanning becomes popular
– Also called mesh decimation, multi-resolution modeling and other
things
Level of Detail
http://www.cs.unc.edu/~geom/SUCC_MAP/
Problems with Polygons
• They are inherently an approximation
– Things like silhouettes can never be prefect without very large
numbers of polygons, and corresponding expense
– Normal vectors are not specified everywhere
• Interaction is a problem
– Dragging points around is time consuming
– Maintaining things like smoothness is difficult
• Low level information
– Eg: Hard to increase, or decrease, the resolution
– Hard to extract information like curvature
More Object Representations
•
•
•
•
•
•
•
Parametric instancing
Hierarchical modeling
Constructive Solid Geometry
Sweep Objects
Octrees
Blobs and Metaballs and other such things
Production rules
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
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
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);
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
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()
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
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
Vitally Important Point:
•Every node has its own
local coordinate system.
•This makes specifying
transformations much
much easier.
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()
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
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
CSG Example
-
Fill it in!
scale
translate
-

cube

scale
translate
scale
translate
cylinder cylinder
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
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
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
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
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
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
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)
Quadtree Example
top left
top right bot left
bot right
Octree principle is the same, but there are 8 children
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
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, …
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