Polygonal modeling
Encyclopedia
In 3D computer graphics
3D computer graphics
3D computer graphics are graphics that use a three-dimensional representation of geometric data that is stored in the computer for the purposes of performing calculations and rendering 2D images...

, polygonal modeling is an approach for modeling objects by representing or approximating their surface
Surface
In mathematics, specifically in topology, a surface is a two-dimensional topological manifold. The most familiar examples are those that arise as the boundaries of solid objects in ordinary three-dimensional Euclidean space R3 — for example, the surface of a ball...

s using polygon
Polygon
In geometry a polygon is a flat shape consisting of straight lines that are joined to form a closed chain orcircuit.A polygon is traditionally a plane figure that is bounded by a closed path, composed of a finite sequence of straight line segments...

s. Polygonal modeling is well suited to scanline rendering
Scanline rendering
Scanline rendering is an algorithm for visible surface determination, in 3D computer graphics,that works on a row-by-row basis rather than a polygon-by-polygon or pixel-by-pixel basis...

 and is therefore the method of choice for real-time computer graphics
Real-time computer graphics
Real-time computer graphics is the subfield of computer graphics focused on producing and analyzing images in real time. The term is most often used in reference to interactive 3D computer graphics, typically using a GPU, with video games the most noticeable users...

. Alternate methods of representing 3D objects include NURBS surfaces, subdivision surface
Subdivision surface
A subdivision surface, in the field of 3D computer graphics, is a method of representing a smooth surface via the specification of a coarser piecewise linear polygon mesh...

s, and equation-based representations used in ray tracers. See polygon mesh
Polygon mesh
A polygon mesh or unstructured grid is a collection of vertices, edges and faces that defines the shape of a polyhedral object in 3D computer graphics and solid modeling...

 for a description of how polygonal models are represented and stored.

Geometric theory and polygons

The basic object used in mesh modeling is a vertex
Vertex (geometry)
In geometry, a vertex is a special kind of point that describes the corners or intersections of geometric shapes.-Of an angle:...

, a point in three dimensional space. Two vertices connected by a straight line become an edge. Three vertices, connected to the each other by three edges, define a triangle
Triangle
A triangle is one of the basic shapes of geometry: a polygon with three corners or vertices and three sides or edges which are line segments. A triangle with vertices A, B, and C is denoted ....

, which is the simplest polygon in Euclidean space
Euclidean space
In mathematics, Euclidean space is the Euclidean plane and three-dimensional space of Euclidean geometry, as well as the generalizations of these notions to higher dimensions...

. More complex polygons can be created out of multiple triangles, or as a single object with more than 3 vertices. Four sided polygons (generally referred to as quads) and triangles are the most common shapes used in polygonal modeling. A group of polygons, connected to each other by shared vertices, is generally referred to as an element. Each of the polygons making up an element is called a face.

In Euclidean geometry
Euclidean geometry
Euclidean geometry is a mathematical system attributed to the Alexandrian Greek mathematician Euclid, which he described in his textbook on geometry: the Elements. Euclid's method consists in assuming a small set of intuitively appealing axioms, and deducing many other propositions from these...

, any three non-colinear points determine a plane. For this reason, triangles always inhabit a single plane. This is not necessarily true of more complex polygons, however. The flat nature of triangles makes it simple to determine their surface normal
Surface normal
A surface normal, or simply normal, to a flat surface is a vector that is perpendicular to that surface. A normal to a non-flat surface at a point P on the surface is a vector perpendicular to the tangent plane to that surface at P. The word "normal" is also used as an adjective: a line normal to a...

, a three-dimensional vector perpendicular to the triangle's surface. Surface normals are useful for determining light transport in ray tracing, and are a key component of the popular Phong shading
Phong shading
Phong shading refers to an interpolation technique for surface shading in 3D computer graphics. It is also called Phong interpolation or normal-vector interpolation shading. Specifically, it interpolates surface normals across rasterized polygons and computes pixel colors based on the interpolated...

 model. Some rendering systems use vertex normals instead of face normals to create a better-looking lighting system at the cost of more processing. Note that every triangle has two face normals, which are on the same line but opposite from each other. In many systems only one of these normals is considered valid – the other side of the polygon is referred to as a backface, and can be made visible or invisible depending on the programmer’s desires.

Many modeling programs do not strictly enforce geometric theory; for example, it is possible for two vertices to have two distinct edges connecting them, occupying exactly the same spatial location. It is also possible for two vertices to exist at the same spatial coordinates, or two faces to exist at the same location. Situations such as these are usually not desired and many packages support an auto-cleanup function. If auto-cleanup is not present, however, they must be deleted manually.

A group of polygons which are connected together by shared vertices is referred to as a mesh. In order for a mesh to appear attractive when rendered
Rendering (computer graphics)
Rendering is the process of generating an image from a model , by means of computer programs. A scene file contains objects in a strictly defined language or data structure; it would contain geometry, viewpoint, texture, lighting, and shading information as a description of the virtual scene...

, it is desirable that it be non-self-intersecting, meaning that no edge passes through a polygon. Another way of looking at this is that the mesh cannot pierce itself. It is also desirable that the mesh not contain any errors such as doubled vertices, edges, or faces. For some purposes it is important that the mesh be a manifold
Manifold
In mathematics , a manifold is a topological space that on a small enough scale resembles the Euclidean space of a specific dimension, called the dimension of the manifold....

 – that is, that it does not contain holes or singularities (locations where two distinct sections of the mesh are connected by a single vertex).

Construction of polygonal meshes

Although it is possible to construct a mesh by manually specifying vertices and faces, it is much more common to build meshes using a variety of tools. A wide variety of 3d graphics software
3D computer graphics software
3D computer graphics software refers to programs used to create 3D computer-generated imagery. This article covers only some of the software used.-Uses:...

 packages are available for use in constructing polygon meshes.

One of the more popular methods of constructing meshes is box modeling
Box modeling
Box modeling is a technique in 3D modeling where the model is created by modifying primitive shapes in a way to create a "rough draft" of the final model. This is in contrast with the edge modeling method, where the modeler edits individual vertices...

, which uses two simple tools:
  • The subdivide tool splits faces and edges into smaller pieces by adding new vertices. For example, a square would be subdivided by adding one vertex in the center and one on each edge, creating four smaller squares.
  • The extrude tool is applied to a face or a group of faces. It creates a new face of the same size and shape which is connected to each of the existing edges by a face. Thus, performing the extrude operation on a square face would create a cube connected to the surface at the location of the face.


A second common modeling method is sometimes referred to as inflation modeling or extrusion modeling. In this method, the user creates a 2d shape which traces the outline of an object from a photograph or a drawing. The user then uses a second image of the subject from a different angle and extrudes the 2d shape into 3d, again following the shape’s outline. This method is especially common for creating faces and heads. In general, the artist will model half of the head and then duplicate the vertices, invert their location relative to some plane, and connect the two pieces together. This ensures that the model will be symmetrical.

Another common method of creating a polygonal mesh is by connecting together various primitives, which are predefined polygonal meshes created by the modeling environment. Common primitives include:
  • Cubes
  • Pyramids
  • Cylinders
  • 2D primitives, such as squares, triangles, and disks
  • Specialized or esoteric primitives, such as the Utah Teapot
    Utah teapot
    The Utah teapot or Newell teapot is a 3D computer model which has become a standard reference object in the computer graphics community. It is a mathematical model of an ordinary teapot of fairly simple shape, which appears solid, cylindrical and partially convex...

     or Suzanne, Blender's
    Blender (software)
    Blender is a free and open-source 3D computer graphics software product used for creating animated films, visual effects, interactive 3D applications or video games. The current release version is 2.60, and was released on October 19, 2011...

     monkey mascot.
  • Spheres - Spheres are commonly represented in one of two ways:
    • Icospheres are icosahedron
      Icosahedron
      In geometry, an icosahedron is a regular polyhedron with 20 identical equilateral triangular faces, 30 edges and 12 vertices. It is one of the five Platonic solids....

      s which possess a sufficient number of triangles to resemble a sphere.
    • UV Spheres are composed of quads, and resemble the grid seen on some globes - quads are larger near the "equator" of the sphere and smaller near the "poles," eventually terminating in a single vertex.


Finally, some specialized methods of constructing high or low detail meshes exist. Sketch based modeling
Sketch based modeling
Sketch based modeling is a method of creating 3D models for use in 3D computer graphics applications. Sketch based modeling is differentiated from other types of 3D modeling by its interface - instead of creating a 3D model by directly editing polygons, the user draws a 2D shape which is converted...

 is a user-friendly interface for constructing low-detail models quickly, while 3d scanner
3D scanner
A 3D scanner is a device that analyzes a real-world object or environment to collect data on its shape and possibly its appearance . The collected data can then be used to construct digital, three dimensional models....

s can be used to create high detail meshes based on existing real-world objects in almost automatic way. These devices are very expensive, and are generally only used by researchers and industry professionals but can generate high accuracy sub-millimetric digital representations.

Operations

There are a very large number of operations which may be performed on polygonal meshes. Some of these roughly correspond to real-world manipulations of 3D objects, while others do not.

Polygonal mesh operations:

Creations - Create new geometry from some other mathematical object

Loft
Loft (3D)
Loft is a variant of a wireframe of the 3D object, a technique used in 3D modeling packages such as 3D Studio Max, SolidWorks, and NX. It's derivable from flat section by doubling it along the path given....

  - generate a mesh by sweeping a shape along a path

Extrude - same as loft, except the path is always a line

Revolve - generate a mesh by revolving (rotating) a shape around an axis

Marching cubes - algorithm to construct a mesh from an implicit function
Implicit function
The implicit function theorem provides a link between implicit and explicit functions. It states that if the equation R = 0 satisfies some mild conditions on its partial derivatives, then one can in principle solve this equation for y, at least over some small interval...



Binary Creations - Create a new mesh from a binary operation of two other meshes

Add - boolean addition of two meshes

Subtract - boolean subtraction of two meshes

Intersect - boolean intersection

Union - boolean union of two meshes

Attach - attach one mesh to another (removing the interior surfaces)

Chamfer - create a beveled surface which smoothly connected two surfaces

Deformations - Move only the verticies of a mesh

Deform - systematically move verticies (according to certain functions or rules)

Weighted Deform - move verticies based on localized weights per vertex

Morph - move verticies smoothly between a source and target mesh

Bend - move verticies to "bend" the object

Twist - move verticies to "twist" the object

Manipulations - Modify the geometry of the mesh, but not necessarily topology

Displace - introduce additional geometry based on a "displacement map" from the surface

Simplify - systematically remove and average verticies

Subdivide - smooth a course mesh by subdividing the mesh (Catmull-Clark, etc.)

Convex Hull - generate another mesh which minimally encloses a given mesh (think shrink-wrap)

Cut - create a hole in a mesh surface

Stitch - close a hole in a mesh surface

Measurements - Compute some value of the mesh

Volume - compute the 3D volume of a mesh (discrete volumetric integral)

Surface Area - compute the surface area of a mesh (discrete surface integral)

Collision Detection - determine if two complex meshes in motion have collided

Fitting - construct a parametric surface (NURBS, bicubic spline) by fitting it to a given mesh

Point-Surface Distance - compute distance from a point to the mesh

Line-Surface Distance - compute distance from a line to the mesh

Line-Surface Intersection - compute intersection of line and the mesh

Cross Section - compute the curves created by a cross-section of a plane through a mesh

Centroid - compute the centroid, geometric center, of the mesh

Center-of-Mass - compute the center of mass, balance point, of the mesh

Extensions

Once a polygonal mesh has been constructed, further steps must be taken before it is useful for games, animation, etc. The model must be texture mapped to add colors and texture to the surface and it must be given a skeleton for animation. Meshes can also be assigned weights and centers of gravity for use in physical simulation.

In order to display a model on a computer screen outside of the modeling environment, it is necessary to store that model in one of the file format
File format
A file format is a particular way that information is encoded for storage in a computer file.Since a disk drive, or indeed any computer storage, can store only bits, the computer must have some way of converting information to 0s and 1s and vice-versa. There are different kinds of formats for...

s listed below, and then use or write a program capable of loading from that format. The two main methods of displaying 3d polygon models are OpenGL
OpenGL
OpenGL is a standard specification defining a cross-language, cross-platform API for writing applications that produce 2D and 3D computer graphics. The interface consists of over 250 different function calls which can be used to draw complex three-dimensional scenes from simple primitives. OpenGL...

 and Direct3D
Direct3D
Direct3D is part of Microsoft's DirectX application programming interface . Direct3D is available for Microsoft Windows operating systems , and for other platforms through the open source software Wine. It is the base for the graphics API on the Xbox and Xbox 360 console systems...

. Both of these methods can be used with or without a 3d accelerated graphics card.

Advantages and disadvantages

There are many disadvantages to representing an object using polygons. Polygons are incapable of accurately representing curved surfaces, so a large number of them must be used to approximate curves in a visually appealing manner. The use of complex models has a cost in lowered speed. In scanline conversion
Scanline rendering
Scanline rendering is an algorithm for visible surface determination, in 3D computer graphics,that works on a row-by-row basis rather than a polygon-by-polygon or pixel-by-pixel basis...

, each polygon must be converted and displayed, regardless of size, and there are frequently a large number of models on the screen at any given time. Often, programmers must use multiple models at varying levels of detail to represent the same object in order to cut down on the number of polygons being rendered.

The main advantage of polygons is that they are faster than other representations. While a modern graphics card can show a highly detailed scene at a frame rate
Frame rate
Frame rate is the frequency at which an imaging device produces unique consecutive images called frames. The term applies equally well to computer graphics, video cameras, film cameras, and motion capture systems...

 of 60 frames per second or higher, raytracers, the main way of displaying non-polygonal models, are incapable of achieving an interactive frame rate (10 frame/s or higher) with a similar amount of detail.

File formats

A variety of formats are available for storing 3d polygon data. The most popular are:
  • .3ds, .max, which is associated with 3D Studio Max
    3D Studio Max
    Autodesk 3ds Max, formerly 3D Studio MAX, is for making 3D animations. It was developed and produced by Autodesk Media and Entertainment. It has modeling capabilities, a flexible plugin architecture and can be used on the Microsoft Windows platform. It's frequently used by video game developers, TV...

  • .mb and .ma, which are associated with Maya
    Maya (software)
    Autodesk Maya , commonly shortened to Maya, is 3D computer graphics software that runs on Microsoft Windows, Mac OS and Linux, originally developed by Alias Systems Corporation and currently owned and developed by Autodesk, Inc. It is used to create interactive 3D applications, including video...

  • .lwo, which is associated with Lightwave
    LightWave
    LightWave 3D is a high end computer graphics program developed by NewTek. The latest release of LightWave runs on Windows and Mac OS X.- Overview:...

  • .lxo, which is associated with modo (software)
    Modo (software)
    modo is a polygon and subdivision surface modeling, sculpting, 3D painting, animation and rendering package developed by Luxology, LLC. The program incorporates features such as n-gons, 3D painting and edge weighting, and runs on Mac OS X and Microsoft Windows platforms.-History:modo was created...

  • .obj (Wavefront's "The Advanced Visualizer")
  • .c4d associated with Cinema 4D
    Cinema 4D
    CINEMA 4D is a 3D modeling, animation and rendering application developed by MAXON Computer GmbH of Friedrichsdorf, Germany. It is capable of procedural and polygonal/subd modeling, animating, lighting, texturing, rendering, and common features found in 3d modelling applications.- Overview:The...

  • .dxf, .dwg, .dwf, associated with AutoCAD
    AutoCAD
    AutoCAD is a software application for computer-aided design and drafting in both 2D and 3D. It is developed and sold by Autodesk, Inc. First released in December 1982, AutoCAD was one of the first CAD programs to run on personal computers, notably the IBM PC...

  • .md2, .md3, associated with the Quake
    Quake (series)
    The Quake series is a line of first-person shooter video games produced by id Software.-Overview:The Quake series is somewhat unusual in that its focus changes frequently; the story of Quake II has nothing to do with Quake, and Quake III Arena has little to do with either of its predecessors...

     series of games
  • .fbx (Alias)
  • .rwx (Renderware)
  • .wrl (VRML 2.0)
  • .blend, which is associated with Blender
    Blender (software)
    Blender is a free and open-source 3D computer graphics software product used for creating animated films, visual effects, interactive 3D applications or video games. The current release version is 2.60, and was released on October 19, 2011...

  • .jt
    JT (visualization format)
    JT is a 3D data format developed by and is used for product visualization, collaboration, and CAD data exchange. It can contain any combination of approximate data, exact boundary representation surfaces , Product and Manufacturing Information , and Metadata either exported from the native CAD...

     originally developed by Siemens PLM Software
    Siemens PLM Software
    Siemens PLM Software is a computer software company specializing in 3D & 2D Product Lifecycle Management software. The company is a business unit of Siemens Industry Automation division, and is headquartered in Plano, Texas....

    ; now an ISO standard.
  • .stl
    STL (file format)
    STL is a file format native to the stereolithography CAD software created by 3D Systems. This file format is supported by many other software packages; it is widely used for rapid prototyping and computer-aided manufacturing. STL files describe only the surface geometry of a three dimensional...

     used in rapid prototyping
    Rapid prototyping
    Rapid prototyping is the automatic construction of physical objects using additive manufacturing technology. The first techniques for rapid prototyping became available in the late 1980s and were used to produce models and prototype parts. Today, they are used for a much wider range of applications...

  • .ply
    PLY (file format)
    PLY is a computer file format known as the Polygon File Format or the Stanford Triangle Format.The format was principally designed to store three dimensional data from 3D scanners. It supports a relatively simple description of a single object as a list of nominally flat polygons...

     used to store data from 3D scanner
    3D scanner
    A 3D scanner is a device that analyzes a real-world object or environment to collect data on its shape and possibly its appearance . The collected data can then be used to construct digital, three dimensional models....

    s
  • .dae (COLLADA
    COLLADA
    COLLADA is a COLLAborative Design Activity for establishing an interchange file format for interactive 3D applications. COLLADA is managed by the nonprofit technology consortium, the Khronos Group....

    )
  • .nif (NetImmerse/gamebryo
    Gamebryo
    Gamebryo is a game engine, originally from Numerical Design Limited , and the successor to NDL's NetImmerse engine.Since the creation of Gamebryo, NDL merged into Emergent Game Technologies...

    )

See also

  • Finite element method
    Finite element method
    The finite element method is a numerical technique for finding approximate solutions of partial differential equations as well as integral equations...

  • Polygon mesh
    Polygon mesh
    A polygon mesh or unstructured grid is a collection of vertices, edges and faces that defines the shape of a polyhedral object in 3D computer graphics and solid modeling...

  • Vector graphics
    Vector graphics
    Vector graphics is the use of geometrical primitives such as points, lines, curves, and shapes or polygon, which are all based on mathematical expressions, to represent images in computer graphics...

  • Geometry processing
    Geometry Processing
    Geometry processing, or mesh processing, is a fast-growing area of research that uses concepts from applied mathematics, computer science and engineering to design efficient algorithms for the acquisition, reconstruction, analysis, manipulation, simulation and transmission of complex 3D models...

  • 3D modeling
    3D modeling
    In 3D computer graphics, 3D modeling is the process of developing a mathematical representation of any three-dimensional surface of object via specialized software. The product is called a 3D model...

The source of this article is wikipedia, the free encyclopedia.  The text of this article is licensed under the GFDL.
 
x
OK