Array Based Mesh Design
From K-3D
Overview
 This document describes changes to K-3D's geometric mesh datatype. The combination of the new array-based mesh design with the new Mesh Painters architecture have led to multiple-order-of-magnitude improvements in pipeline and render performance. As an example, K-3D is able to load the Stanford "Happy Buddha" dataset, rendering more than one million polygons with usable interactivity. |
Historical Design
Geometric data in the K-3D pipeline is represented by the k3d::mesh datatype. Each instance of k3d::mesh is a heterogeneous container for the union of all the geometric types supported by K-3D (points, polyhedra, subdivision surfaces, curves, patches, etc). In the past this data was organized within the mesh using containers-of-pointers that pointed to instances of the individual geometric types created on the heap. As an 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();
In similar fashion, all of the geometric types require varying amounts of positional information, and used k3d::point* to reference points that were owned by the mesh. Again, this led to easy access:
if(edge->vertex) edge->vertex->do_something_else();
Further, each geometric type maintained its own private list of "attributes", such as per-vertex color, explicitly-assigned geometric normals, etc. using maps typedef'd as std::map<std::string, boost::any>. Once again, this was great for coding clarity:
if(edge->vertex) edge->vertex->vertex_data["Cs"] = k3d::color(0, 0, 1); // blue
Unfortunately, this convenience in programming API took a toll on performance in many ways:
- Lots of small objects - each mesh 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 (which we were already using).
- Complicated copying - because modifiers cannot modify their inputs, they must make a copy. The code for copying meshes was complex since it had to individually allocate copies of every object, remapping each pointer to 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 is 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 is inefficient because the widely-varying memory addresses can negate 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.
New Design
Now, K-3D has been updated to use a lower-level API where mesh data is stored efficiently using arrays. For example, all of the vertices in a mesh are stored in an array. Geometric types reference vertices using zero-based indices. Edges and faces are defined using arrays of connectivity information. Attributes are stored using named, typed arrays of homogeneous data. Each mesh stores its arrays using shared pointers. The benefits:
- Eliminate most 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 indices.
- Memory can be shared - arrays that are not changed by a modifier can be easily shared throughout the pipeline, 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 - iterating over the contents of an array is more efficient, benefitting fully from CPU cache.
- 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 are passed directly to RenderMan without the memory and CPU overhead of "grouping" operations.
Implementation Details
The implementation of the array-based meshes is ongoing in K-3D 0.7:
- See the new mesh source documentation.
- See early documentation on how the new mesh uses arrays to represent mesh topology.
- 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 make it a k3d::array derivative.
- k3d::mesh is the new array-based mesh class. The old mesh class is k3d::legacy::mesh. k3d::legacy::mesh and related functionality will likely be around for a long time until all plugins have been rewritten to use the array-based mesh. Compatibility code will ensure that legacy plugins continue to Just Work.
- All data in k3d::mesh is stored in k3d::typed_array instances.
- Predefined arrays (such as the array of points that is an essential part of every mesh) are stored using boost::shared_ptr, so copying the mesh is blazingly fast and array memory is shared up-and-down the visualization pipeline unless an array is modified (copy-on-write).
- User-defined arrays (per-vertex color and opacity, per-vertex normals, texture coordinates, RenderMan attributes, etc) are stored in heterogeneous named collections using std::map<std::string, boost::shared_ptr<k3d::array> >. This allows quick lookup of arrays by name, and (again) very fast copying and shared memory until an array is modified.
- Plugin authors need only call k3d::make_unique() before modifying an array to handle all memory-management issues.
Compatibility
Due to the amount and complexity of work invested in the existing mesh design, it will be necessary to handle compatibility between the different mesh designs during the transition to the array-based mesh. Existing user documents should continue to "just work" while the work is performed. The best approach will likely be to use the new mesh throughout the pipeline and define functions that convert between the new and old mesh designs. Legacy helper classes such as k3d::legacy::mesh_source and k3d::legacy::mesh_modifier can perform automatic conversion of their inputs and outputs so that existing plugins will be unaffected by the new mesh design. It is expected that the overhead introduced by this conversion will be negligible, since the time spent performing conversions will be comparable to the time that is normally spent copying mesh instances throughout the pipeline.
Polyhedra traversal
The relations between the different arrays in k3d::mesh::polyhedra_t and the k3d::mesh::points array are shown in the next figure:
Note that this is all the connectivity information stored in the basic mesh structure, and the entire mesh can be traversed using only these arrays. The higher level, not mentioned in the figure, is the first_faces array, which contains the first face number (index into face_first_loops) for each polyhedron in the mesh. The use of this array is only needed if it is necessary to make a distinction between the polyhedra. If you simply want to iterate over all polyhedra it can be ignored.
Sometimes, it can be useful to have some extra connectivity data, such as the "companion" edges from the legacy mesh structure. These (and other data) can be obtained through the methods declared in k3dsdk/mesh_topology_data.h. The next figure shows an example on how to traverse the edges and vertices around a vertex:
See Also
Performance and Mesh Painters, both of which should benefit from the proposed design.
