Geometric Primitive Design

From K-3D

(Redirected from Array Based Mesh Design)
Jump to: navigation, search

Overview

K-3D rendering 540,000 vertices, 3.2 million edges, and 1.08 million triangles at interactive rates.

This article describes K-3D's geometric primitive data structures, which support rendering more than one million polygons with usable interactivity while providing unprecedented flexibility, including the ability to introduce new geometric primitive types at runtime. Many of K-3D's features - including the Visualization Pipeline, Mesh Painters, and pluggable render engines - make it a natural choice for working with new geometric primitive types, and the new data structures make this easy.

k3d::mesh

Geometric data in the K-3D pipeline is stored using the k3d::mesh class. Each instance of k3d::mesh is a container for a collection of geometric points, and a collection of k3d::mesh::primitive objects. The points in k3d::mesh are globally-accessible to every primitive within the mesh, so primitives can "share" control-points, "stitching" them together.

k3d::mesh::primitive

Every instance of k3d::mesh::primitive stores a specific type of geometric primitive, such as a polyhedron, collection of curves, collection of NURBS patches, collection of quadrics, etc. Within the primitive, data is stored compactly using collections of named arrays. In fact, every piece of data in the primitive is stored using arrays:

  • k3d::array is an abstract class for use in heterogeneous containers of arrays. There are no public members in k3d::array, callers must dynamic_cast it to a concrete derivative in order to access the array data.
  • The k3d::typed_array template class "wraps" std::vector to implement the k3d::array interface, providing a strongly-typed array.
  • Arrays are stored indirectly using k3d::pipeline_data, which provides shallow-copy / copy-on-write semantics for array storage.
  • Arrays are named, with the purpose and name of each array defined by the individual primitive type.

The arrays in a primitive are grouped into Components. Each component is a named k3d::table data structure, which contains a heterogeneous collection of named k3d::array data structures, all of which are the same length. Components are further grouped into two categories: Structure, which contains required arrays that must be present in all instances of a primitive; and Attributes, which are optional user-defined arrays.


Data Structure


  • The set of components in a primitive will vary, based on the primitive type. A "foo" component stores "per-foo" data, where "foo" is some aspect of the primitive. This is pretty intuitive: a patch primitive has a component that stores per-patch data, a polyhedron primitive has components to store per-face and per-edge data, etc.
  • The set of arrays in a component will vary, based on the primitive type. Where an array is located says a lot about its function: if the "foo" component has a selection array, it means that users can make "per-foo" component selections. If the "foo" component has a material array, it means materials can be assigned on a "per-foo" basis.
  • Many array types can be defined over multiple components. For example, a polyhedron has selection arrays in both the "face" and "edge" components, meaning that users can make selections on both a per-face and per-edge basis. An attribute such as "color" might be defined both per-face and per-vertex.
  • Note that interactive selection is intimately coupled to components: a selection is fundamentally a set of selection-state changes, applied to a specific selection array in a specific component. The list of available component names bounds the list of available selection types.
  • In-general, the designer of a new primitive type has carte blanche to use as many component types as they want, and call them whatever they want.
  • However, there are a couple of incentives not to run too wild: the code that does OpenGL selection can only distinguish selection records based on integers, implying an enumeration of "available interactive selection types." Similarly, the UI has to present users with some reasonably fixed list of selection (component) types.

Grouping the arrays that define a primitive in this way makes it possible to perform many generic operations on primitives, without any a-priori knowledge of what a primitive "looks like" or how it is used. For example:

  • We can validate that every array in a given component is the same length.
  • We can validate that the number of rows in an attribute table match the number of rows in the corresponding structure table.
  • We can validate that "constant" tables always have length 1.
  • Modifiers such as SetMaterial can modify any generic primitive type, simply by searching for a structure table that contains a selection array and a material array.

Component Types

The following summarizes the components currently used by each primitive type:


Primitive TypeStructureAttributes
Bezier Triangle Patch Primitivepatch, vertexconstant, parameter, patch, vertex
Bicubic Patch Primitivepatch, vertexconstant, parameter, patch, vertex
Bilinear Patch Primitivepatch, vertexconstant, parameter, patch, vertex
Blobby Primitivefloat, operand, operator, surface, vertexconstant, parameter, surface, vertex
Cone Primitivesurfaceconstant, parameter, surface
Cubic Curve Primitiveconstant, curve, vertexconstant, curve, parameter, vertex
Cylinder Primitivesurfaceconstant, parameter, surface
Disk Primitivesurfaceconstant, parameter, surface
Hyperboloid Primitivesurfaceconstant, parameter, surface
Linear Curve Primitiveconstant, curve, vertexconstant, curve, parameter, vertex
NURBS Curve Primitiveconstant, curve, knot, vertexconstant, curve, parameter, vertex
NURBS Patch Primitivepatch, trim_knot, trim_loop, trim_point, trim_uniform, trim_vertex, u_knot, v_knot, vertexconstant, parameter, patch, vertex
Paraboloid Primitivesurfaceconstant, parameter, surface
Particle Primitiveconstant, vertexconstant, vertex
Polyhedron Primitiveedge, face, loop, shell, vertexconstant, edge, face, vertex
Sphere Primitivesurfaceconstant, parameter, surface
Teapot Primitivesurfaceconstant, surface
Torus Primitivesurfaceconstant, parameter, surface


Here, we summarize a set of commonly-used components and their semantics:

Component TypeDescription
constantContains values that are constant over the entire primitive. A constant component must always store exactly one value.
curveUsed to store per-curve data for primitives that are explicitly not surfaces. A curve component stores one value for each curve in the primitive.
edgeUsed to store per-edge data for polygon edges. An edge component stores one value for each edge in a polyhedron.
faceUsed to store per-face data for polygon faces. Note that faces are explicitly polyhedral - i.e. neither patches nor general surfaces such as quadrics are considered to be 'faces'. A face component stores one value for each face in a polyhedron.
patchUsed to store per-patch data for parametric patch primitives. Note that patches are explicitly parametric - i.e. they are not polygons or general surfaces. A patch component stores one value for each patch in a primitive.
parameterUsed to store data at the parametric corners of primitives such as patches and curves, e.g. the two "endpoints" of a curve or the four "corners" of a typical patch. Note that quadric primitives support parameter data, because each quadric can be treated as a single four-sided 'patch' that has been curved to form the quadric surface. Parameter components will store: two values for each curve in a curve primitive; three values for each patch in a Bezier triangle patch primitive; four values for each patch in most other patch primitives.
surfaceUsed to store data for generic surface primitives, including quadrics and special-purpose primitives such as teapots. Note that in this context, 'surface' components are a generic 'catch-all' for primitives that are not parametric primitives or polygon faces. A surface component stores one value for each surface in the primitive, e.g. one value for each sphere in a sphere primitive or one value for each teapot in a teapot primitive.
vertexUsed to store per-vertex data for primitives that are defined by vertices. This includes control vertices for curves and patches, and the vertices in polyhedron faces. A vertex component stores one value for each vertex in a primitive - note that this is not the same as each point in a mesh, since mesh points may be shared across multiple primitives.

Benefits

While some may find this ubiquitous use of arrays counterintuitive, it delivers many benefits:

  • Creating a shallow-copy of a mesh or a primitive is trivial.
  • Serializing a mesh by serializing its tables and arrays is trivial.
  • Deserializing a mesh by restoring its tables and arrays is trivial.
  • Comparing two meshes for equality by comparing their arrays and all their gprim containers' arrays is trivial.
  • Eliminates small allocations - by grouping data into arrays, many individual heap allocations can be replaced with a few large allocations.
  • Easy copying - simple array objects can be copied by-value in a single operation, without the need to remap values (such as memory pointers).
  • Easy sharing - arrays not altered by a modifier can be shared throughout the pipeline using shallow-copy semantics, leading to a significant reduction in memory consumption.
  • Efficient drawing - drawing code can easily determine whether a mesh contains a specific attribute (such as per-vertex color or explicit normals) in constant time and execute a different code path accordingly.
  • Cache coherence - iteration over the contents of an array is efficient and easily parallelized, benefitting fully from modern CPU designs including pipelining, cache, and multi-core computation.
  • Vertex arrays - arrays of vertex and normal data can be passed to OpenGL using single function calls for multiple-order-of-magnitude improvements in performance.
  • Faster rendering - arrays of attributes can be passed directly to RenderMan without the memory and CPU overhead of "grouping" operations.

As should be clear, a K-3D mesh is - literally - a large collection of arrays. Some arrays are structural and play well-defined roles based on the primitive type while others are user-defined named-attributes, but at the end-of-the-day they are all simply arrays.

Historical Background

In the past, geometric data was stored within k3d::mesh using containers-of-pointers that pointed to instances of the individual geometric types created on the heap. For example, the collection of points within a mesh was stored using std::vector<k3d::point*>; the faces within a polyhedron were stored using std::vector<k3d::face*>, and-so-on. Data objects that referenced each other did so using pointers, and the ubiquitous use of pointers within meshes made for easy navigation and maintenance of data structures. As an example, every k3d::split_edge referenced the (optional) adjacent edge using a k3d::split_edge*, so performing an operation on an adjacent edge was as simple as

if(edge->companion)
  edge->companion->do_something();

Similarly, primitives used k3d::point* to reference their control-points. Again, this led to easy access:

if(edge->vertex)
  edge->vertex->do_something_else();

Unfortunately, this convenience in programming API negatively impacted performance for a variety of reasons:

  • Lots of small objects - geometry was made-up of large numbers of small objects (points, edges, faces, curves, patches, etc). Allocating and freeing these objects individually introduced a lot of overhead, even with memory pooling.
  • Complicated copying - because modifiers cannot modify their inputs, they must make a deep copy for output. The code for copying meshes was complex since it had to individually allocate copies of every object, remapping each pointer in an original object to its corresponding copy in the new mesh.
  • Lost opportunities for shared memory - many modifiers modify geometry or attributes but not both, making them excellent candidates for sharing memory between mesh copies. Unfortunately, the way in which geometry and attributes were "interleaved" made the overhead of shared pointers impractical.
  • Lost opportunities for efficient drawing - determining whether a particular set of attributes was available such as per-vertex colors or explicitly-assigned geometric normals required iterating over the set of all geometric objects, or querying the attribute map repeatedly in an inner loop.
  • Lost opportunities for cache coherence - iterating over large collections of pointers was inefficient because because it reduced the benefits of CPU cache.
  • Lost opportunities for using vertex arrays - because geometric coordinates and normal data were spread across many individual objects, using many modern OpenGL techniques for efficient rendering was not possible without making additional copies of the data.
  • Slower Rendering - because the RenderMan API expects attributes to be grouped together into arrays of homogeneous attributes, the RIB generation code had to iterate over all of the geometry in a mesh to "group" attributes together.

Compatibility

Due to the amount and complexity of work invested in the legacy mesh design, it will be necessary to handle compatibility between legacy and current mesh data structures during a transition period. Existing user documents should continue to "just work" while this work is performed. We currently define functionality that converts between legacy and current meshes. Legacy helper classes such as k3d::legacy::mesh_source and k3d::legacy::mesh_modifier can perform automatic conversion of their inputs and outputs so legacy plugins are unaffected by the current design. We are actively working to eliminate all legacy code before version 1.0.

See Also