Painter Cache

From K-3D

Jump to: navigation, search

Background

The painter cache system, currently implemented in modules/advanced_opengl_painters/painter_cache.h, needs to be rewritten for clarity, simplicity, and to align it with Hint Mapping, Node Visibility, and Per Render Engine Painters. The rewritten system will include / interact-with the following components:

MeshInstance

Purpose: provides a "handle" to a k3d::mesh*, an interactive selection, and a transformation matrix. See MeshInstance.

MeshPainterLink

Purpose: Represent the one-to-many links that exist between a MeshInstance and its MeshPainters. See Per Render Engine Painters.

Proposed implementation:

  • Two properties, one of type k3d::imesh_source and one of type k3d::imesh_painter_gl*.
  • Implements k3d::gl::idrawable, and executes the painter's paint_mesh() and select_mesh() methods when called.

Mesh Painter

Purpose: Knows how to render k3d::mesh data using OpenGL. See Mesh Painters.

Proposed changes: The mesh_changed method will be removed, and instead a changed_signal will be passed in the drawing methods along with the mesh. This signal can be connected to in order to be notified of changes in the mesh. Ths leaves the following methods to be implemented by painter authors:

virtual void paint_mesh(const mesh& Mesh, const painter_render_state& RenderState, iproperty::changed_signal_t& ChangedSignal) = 0;
virtual void select_mesh(const mesh& Mesh, const painter_render_state& RenderState, const painter_selection_state& SelectionState, iproperty::changed_signal_t& ChangedSignal) = 0;

Painter Cache

Purpose: Stores data that is too expensive to recalculate on every redraw.

Stored data

The cached data is stored and retrieved on the initiative of the mesh painter. This means some sort of "key" is required, so the painters can tell the cache manager what data they need. The key should be defined in such a way that it is unique for the data it is associated with, and only changes if the associated data also changed. With this in mind, the following associations are proposed:

DataKey
Non-VBO Painters
Face NormalsPolyhedron primitive pointer
TriangulationsPolyhedron primitive pointer
SDS dataPolyhedron primitive pointer and SDS level
Selection dataCorresponding selection array pointer
VBO Painters
PointsPoints array pointer
Normals (depends on the regular normals cache)Polyhedron primitive pointer
Index VBOs for edgesedge_points array pointer
VBOs for the triangulated data (depends on the regular triangle cache)Polyhedron primitive pointer
VBOs for the SDS data (depends on the regular SDS cache)Polyhedron primitive pointer and SDS level

Proposed implementation

The pointer_demand_storage policy is used in order to make use of the already present hint caching functionality. The base class cached_data is responsible for the processing of the hints and passing them on to virtual update methods. This class also provides a method to set the input mesh. It is templated by the stored data type, which in most cases will simply be a struct with the arrays of cached data. This system also provides a decoupling between the cache data format and the methods used to create/update the data. A base class for data relevant to polyhedron geometry would look something like this (based on bitmap_modifier.h):

template<class data_t>
class cached_polyhedron_data
{
 /// Get the up-to-date value of the cache, using InputMesh as input data
 const data_t& value(const k3d::mesh& InputMesh)
 {
   m_input_mesh = &InputMesh;
   return m_data.pipeline_value();
 }
protected:
 cached_data(k3d::iproperty::changed_signal_t& ChangedSignal)
 {
   m_input_mesh(0);
   m_data.set_update_slot(sigc::mem_fun(*this, &cached_data<data_t>::update));
   // connect to the CHangedSignal here, using appropriate hint mapping
 }
 void update(const std::vector<ihint*>& Hints, data_t& Data)
 {
   return_if_fail(m_input_mesh);
   k3d::bool_t topology_changed = false;
   k3d::bool_t selection_changed = false;
   std::vector<k3d::mesh::indices_t> changed_points;
   
   for(int i = 0; i != Hints.size(); ++i)
   {
     if(k3d::hint::mesh_geometry_changed* hint = dynamic_cast<k3d::hint::mesh_geometry_changed*>(Hints[i]))
     {
       changed_points.push_back(hint->changed_points);
     }
     else if(k3d::hint::selection_changed* hint = dynamic_cast<k3d::hint::selection_changed*>(Hints[i]))
     {
       selection_changed = true;
     }
     else if(k3d::hint::mesh_topology_changed* hint = dynamic_cast<k3d::hint::mesh_topology_changed*>(Hints[i]))
     {
       topology_changed = true;
     }
     else
     {
       selection_changed = true;
       topology_changed = true;
     }
   }
   if(topology_changed)
     on_topology_changed(Data, *m_input_mesh);
   if(selection_changed)
     on_selection_changed(Data, *m_input_mesh);
   for(k3d::uint_t i = 0; i != changed_points.size(); ++i)
     on_geometry_changed(Data, *m_input_mesh, changed_points[i]);
 }
private:
 
 virtual void on_topology_changed(data_t& Input, const k3d::mesh& InputMesh) = 0;
 virtual void on_selection_changed(data_t& Input, const k3d::mesh& InputMesh) = 0;
 virtual void on_geometry_changed(data_t& Input, const k3d::mesh& InputMesh, const k3d::mesh::indices_t& ChangedPoints) = 0;
 
 k3d_data(data_t*, immutable_name, change_signal, no_undo, local_storage, no_constraint, no_property, no_serialization) m_data;
 const k3d::mesh* m_input_mesh;
};

Painter cache manager

Purpose:

  • Keeps track of cached data for each mesh being painted
  • Keeps track of what painters use what cache, deleting caches that are no longer needed

Proposed implementation

The cache manager stores all cached data, meaning it has some sort of container at its heart. To facilitate retrieval of the data, this container should associate the data to the keys defined in the Painter Cache section. The cache manager will be templated on both key and data type. Rationale:

  • In the case of SDS data, the painters have an additional "level" property, which needs to be factored in. This could be done at the level of the SDS cache itself, but this results in the need for cache lifetime management inside the SDS cache, to keep track of what levels need to be kept. Simply making the cache key a combination of the level number and the primitive avoids this problem and automatically makes use of the central cache lifetime management system. The requirement to have both a combination of an integer and a pointer and various primitive and array pointers as keys makes it necessary for the key type to be a template parameter. This also offers the most flexibility for the future.
  • The data type must be a template: not doing this would result everything to be stored in one big container that could have more than one item per key, i.e. normal and triangle data for the same polyhedron. Using a template parameter ensures these are stored in different cache managers.

The basic functionality of the cache manager is to store the data. This implies methods are needed for storing and retrieving data. Because of the nature of the cache (calculate as little as needed when it is needed only) this is actually reduced to a single cache retrieval method:

  • Cache retrieval
    • Always returns up-to-date data
    • Create the data if it does not exist
    • Update the data if it is out-of-date, using the hints supplied through hint mapping
    • Note that in order to update and create data, the input (i.e. the mesh) must be passed to this method
    • The changed signal is passed so the cached data can connect to it and will be notified of changes

A concrete interface would be:

template<class key_t, class data_t> class painter_cache
{
public: 
  /// Retrieve (and create/update if needed) the data cache associated with Key and based on the input in Mesh
  const data_t& get_cached_data(const key_t& Key, const k3d::mesh& Mesh, k3d::iproperty::changed_signal_t& ChangedSignal);
};

Note that for each combination of key and data type, a separate cache will exist. These are made available through the singleton pattern. In order to avoid always having to type both template arguments, the following convenience functions will provide all access to the cache:

/// Convenience function for easy access to cache data
template<class data_t, class key_t> data_t& get_cached_data(const key_t& Key, const k3d::mesh& Mesh, k3d::iproperty::changed_signal_t& ChangedSignal)

This function puts the key_t as second template argument, so it can be omitted by the callers.

Cache lifetime management

Explicitly tracking what painter needs what cache, and especially determining when cached data is no longer needed, would result in much unneeded complexity. Instead, we will let us inspire by the classical caching algorithms (see references). Some variant of LRU seems the most likely candidate.

Cache size

Usually, a cache has some size limit. In the case of the painter cache, we are limited only by the size of the GPU- and main memory, so the two options are:

  1. Cache data for all meshes that need to be displayed
  2. Fix some limit on the maximum amount of cached data

Cache expiration criteria

Some possibilities for cache expiration, all based on LRU:

  1. Upon redraw, keep track of what cached data got used. Data that was not used during a redraw gets removed. This will require some sort of signal the cache can rely on to konw when a redraw starts/ends.
  2. In the case of some fixed cache limit, keep a stack of cache keys. When a cached item gets used, it is brought to the top of the stack. When the cache is full, the item at the bottom of the cache gets removed.

Hints

First we list the hints that already existed, and propose some minor changes for them:

selection_changed

Emitted whenever the selected components of a mesh have changed. This is important to caches, because there is a cache keeping track of ranges of selected data. An alternative is to store selection colors in VBO color arrays, that also need to change whenever the selection changes. Rebuilding the cached data is inexpensive, so there is no need to provide extra data. Since this hint is specific to meshes, it should be renamed to mesh_selection_changed.

mesh_geometry_changed

Emitted when the geometry of the mesh, i.e. the point positions have changed. This hint currently contains both a transformation matrix and a list of changed points, but the matrix is unused and will be removed.

mesh_topology_changed

Emitted when the topology of the mesh, i.e. information about the connectivity of edges, faces, ... changes. Since this can be basically anything, and it is difficult to optimize updates, no extra information is passed and this hint is usually taken as a sign that the data needs to be regenerated from scratch.

mesh_deleted

Emitted when the mesh is deleted. The new cache lifetime management makes this obsolete, so it can be removed.

Other hints

Note that some cases are not yet addressed by these hints, mostly because the painters either don't exist yet or are very basic:

  • Changes to attribute array data. These could be used in i.e. a painter that uses a precalculated normal array, to reflect manual changes in normal directions.
  • Changes to materials: Only useful for painters that can interpret materials data and show i.e. the color of faces
  • Changes specific to non-polyhedral data, i.e. the knot vector in the case of NURBS data.

The hints for these will be introduced on an as-needed basis.

References