10 3D Object Representations

T. Raghuveera

 

Objectives:

  • Understand Mesh Modeling
  • Understand spline based modeling.

 

Discussion:

 

3D Object Representations:

 

So far we have discussed only the 2D aspects of Computer Graphics. Let’s focus on the 3D part of Computer Graphics. In short 3D is simply an extension of 2D with an extra dimension called the ‘depth’, added. In reality the objects in the world are 3D, and thus 2D is only a hypothetic case. Most of the transformations, algorithms, techniques that we have learnt in the context of 2D, can be extended for 3D by adding the third coordinate, the z-coordinate. The aim of this study of 3D Computer Graphics is to imitate the real world as closely as possible. 3D modeling and rendering software APIs like OpenGL, DirectX enable creation, representation, manipulation and rendering of 3D scenes.

 

Now the fundamental question is how to create / model / represent 3D objects? There are various techniques and tools used to create them. Some of them are mesh, splines, fractals, NURBS, BSP Trees, Octrees, particle systems, physically based modeling, kinematics, Extrusion, sweep representation, Constructive Solid Geometry and so on. Each of these or a combination of these can be used to model / represent / render 3D objects. We needed a vast collection of modeling tools, because of the highly complex nature of a wide variety of real world objects that we wish to model.

 

The first step in the process of modeling is to create a skeletal representation of the object, and then apply various shading and rendering procedures to make it a real world look- alike object. Towards achieving this visual realism, the steps are

  • Mesh / Spline model
  • Shade model
  • Texture model
  • Light model
  • Environment map

Fundamentally an object is modelled in either of the two ways.

 

Surface modeling (boundary representation)

Solid Modeling (Space-partitioning representation)

 

Surface Modeling: Here we try to model only the outer surface / skin of the object that encloses the object, i.e., we ignore the inside of it assuming that the inside is empty space. Example techniques: Mesh, splines, NURBS, sweep representations.

 

Solid Modeling: Here we try to model the outside as well as inside of the object.

 

Example techniques: Constructive Solid Geometry (CSG), Octrees, BSP Trees

 

Just because the inside of an object is of less interest in general, it is the surface modeling that we will use often, but only when it is really necessary to model the inside we will go for solid modeling. It is also unnecessary and wastage of resources to model the inside of an object, when we never have something to do with the inside.

 

Polygonal / Mesh Modeling:

 

 

Let’s look at the figures above, each of them are modelled using mesh. A Mesh is a collection of connected polygonal faces / polygons. i.e., we try to approximate the shape of an object by set of connected polygons. The process of modeling a surface using a collection of triangles is called triangulation or tessellation. If you observe the fish shape above, it is all triangles, but the sphere object is made up of quadrilaterals for its entire shape except for top and bottom parts which use triangles.

 

Consider the standard shapes as shown here, a standard Cube and a Cylinder. A cube has 6 polygonal faces that can be easily modelled using 6 connected polygons, while cylinder has one single curved surface which can be modelled using many thin connected polygonal strips as shown. So it can be inferred that with polygonal mesh modeling, surfaces that are flat are best modelled, while spherical or curved or other irregular surfaces can only be approximated. So cube is best modelled while cylindrical surface is approximated. The word ‘approximation’ is used while modeling non-flat surfaces because, we never get the true underlying surface using meshes, for instance, look at the sphere model above, its shape is only approximated by many connected polygons. The more the number of polygons used to model the better is the approximation to the underlying smoother surface. The essence is that we are trying to use flat planar polygons to model non-flat smoother / curved surfaces, the net effect is ‘approximation’.

 

 

To construct or represent a shape using a polygonal Mesh, we need to start with vertices, connect them with edges, join edges to for polygons, connect many polygons to form a face / surface of the object. Observe the figure below.

  Polygonal mesh data is represented by the data structure comprising of vertices, edges, faces, surfaces, surface normals. As shown in the figure below, mesh data is entered into various lists like, vertex list, edge list, surface / face list, normal list.

 

 

Vertex List – {V0 (x0,y0,z0), V1 (x1,y1,z1), V2, ….., V7(x7,y7,z7)}

Edge List – {E0 – (V0V1),

E1  – (V1V2)

E2 – (V2V3)

——-E11 – (V0V7)},

Face List – {S0 (E2, E9, E6, E10),

S1 (E0, E1, E2, E3),

S2 (E5, E9, E1, E8),

S3 (E4, E11, E0, E8),

S4 (E4, E5, E6, E7),

S5 (E7, E10, E3, E11)}

Normal List – { n0, n1, n2, n3, n4, n5}

 

Consider a standard unit cube as shown in the diagram above. Vertices are where few or more edges meet. Edges connect vertices. Faces are formed by planes containing edges and Normals are for faces. The mesh model can be represented through various lists as given: Vertex list containing vertex information, Edge List (12 edges, E0 to E11) containing Edge information, where each edge connects two vertices, Face list (6 in number from S0 to S5), containing list of surfaces / faces, Normal List (6, from n0 to n5 one for each face) containing normal vector information.

 

It is important to store normal vector information for a face in the normal list. A normal is the direction perpendicular and outward to the plane of the polygon. This data is important because the orientation of a face towards the light source is better understood from its normal vector. It is also useful to compute the angle between the viewing direction and the direction of light source, which is a clue to compute the intensity of the pixel at point of incidence. These lists mentioned comprise the geometric information of the mesh model. Along with this we can also store attribute information (color, texture etc.,) in separate lists.

 

Splines:

 

These are purely mathematical modeling tools that can be used to model planar, or non-planar or curvy or irregular surfaces. Splines are used in automotive design, CAD etc., Splines are fundamentally space curves, and when they are extended in two different directions, they form spline surfaces. With spline surfaces we can model, flowing cloth, water bodies, wrap a spline surface around another object and much more. Spline curves give utmost flexibility to designers to design / model shapes of their choice. There are a variety of splines discussed in literature viz:

  • Hermite Splines
  • Cardinal Splines
  • Bezier Splines
  • Basis Splines
  • NURBS (Non-Uniform Rational Basis Splines)

 

Spline definition:

 

Any composite curve formed with polynomial sections satisfying specified continuity conditions at the boundary of the pieces.

 

If the above definition is closely observed, it is evident that, a spline curve is formed by joining many smaller curves end to end to form a single continuous smoothly flowing spline curve, and at each joint the curve satisfies specified continuity conditions. Each of the smaller curves is a polynomial function, so the spline curve is a polynomial curve.

 

Spline Terminology:

  • Parametric forms
  • Control Points
  • Convex Hull
  • Boundary conditions
  • Order and degree
  • Approximating
  • Interpolating
  • Blending functions
  • Local Control
  • Basis
  • Cox-De Boor recurrence relations

Spline curves are represented in parametric form, which uses a parameter U that varies in the range 0 to 1.

 

P (u) = (x (u), y (u), z (u)) where the parameter u varies from 0 to 1

 For a cubic spline:

x(u) = axu3 + bxu2 + cxu + dx

y(u) = ayu3 + byu2 + cyu + dy

0≤u≤ 1

z(u) = azu3 + bzu2 + czu + dz

 

P(u) = au3 + bu2 + cu + d

 

The curve P (U) is a cubic parametric curve, and is a function of x(u), y(u), z(u), each of which is a cubic parametric polynomial curve by itself. And coefficients, a (ax, ay, a z), b(bx, by, bz) and c (cx, cy, cz) are vectors. The parameter u is raised to the highest power 3 (called the degree of the curve), so we call the curve a cubic curve.

 

Due to the flexibility that the spline curve offers, the designer has the freedom to decide on the shape of the curve, i.e., the shape of the curve is fully controlled by the designers. The designer has the task of choosing or placing points in some sequence in 3D space, such that the points when connected or approximated by curves, gives the desired shape. It also similar to fitting a polynomial curve section on a given set of points placed strategically. These strategically positioned sequence of points that are meant to control the shape of the curve are called control points.

 

In real world there are many analogies to spline curves, for ex: while drawing kolams/    Rangolis during festive occasions, a set of dots are initially placed and they are approximated by curves of choice. Another example being, a road side welding shop where doors, windows, gates, grills of iron are made, it starts by placing long strips of iron on a table that has sequence of strategically arranged firm protrusions or posts on it and using a hand bender they bend the iron strip along the protrusions, to give it a nice curvy shape of choice.

 

Curves that exactly touch these control points are called interpolating curves and curves that approximate the control points are called approximating curves.

As spline is a piece-wise polynomial curve, the many smaller curve sections that make up the curve, must join smoothly at the boundary. To determine how smoothly curve sections join at the boundary, we need to check for boundary conditions / continuity conditions. There are two types of continuity checked for, parametric continuity and geometric continuity.

 

Parametric continuity:

 

Two curves, joining at a boundary are said to exhibit levels of continuity as below.

1. C0 (Zero-order) – curves meet
2. C1 (First-order) – tangents equal
3. C2 (Second-order) – curvatures equal

 

Two curves satisfying C0 or Zeroeth – order parametric continuity, just meet at the boundary. The two curves appear as if they have one common boundary position, but do not appear to join smoothly.

Two curves satisfying C1 or first – order parametric continuity, not only meet at the boundary, but their tangents are also equal. The two curves appear as if one curve is smoothly joining with the second curve.

 

Two curves satisfying C2 or second – order parametric continuity, not only meet at the boundary, but their tangents are also equal, and their curvatures are also equal. The two sections appear as if they are pieces of one single smooth curve joined together.

The higher the degree of the curve sections, the smoother they will be joining at the boundary. Some more examples of splines are shown below.

 

In the above figures, the spline curve is formed by 4 control points, P0, P1, P2, and P3. The curve touches P0 and P3 and approximates P1, and P2.

 

Summary:

  • The two fundamental ways of modeling are surface modeling and solid modeling
  • Mesh modeling is simpler, and superior for modeling flat surfaces, but can only provide approximation for smoother surfaces.
  • Splines are space curves, which can be used to model any variety of shapes and surfaces
  • Splines are either interpolating type or approximating type.
  • Splines should satisfy continuity conditions at the boundary.

************************************************************************************************