Dev:Source/Modeling/DerivedMesh2.0

Motivation

The current state of Blender’s mesh code represents the results of several parallel threads of development throughout the program’s history. While it may seem to the end user that a Blender mesh is a distinct and singular data type the reality is that several separate structures and systems are needed to provide the current level of functionality. Unfortunately Blender lacks a unified infrastructure for dealing with these various mesh systems and application features such as transformations, modifiers and sculpting are usually tied to a specific mesh format in such a way that has profound implications for performance, code maintenance and future development. The purpose of this document is to propose a system that will address these issues by providing a common interface for Blender to work with multiple mesh data types that is independent of implementation details.

Requirements

• Minimize costly conversions
• Eliminate code duplication
• Allow optimizations of individual back ends

As stated previously Blender already does utilize several mesh systems. However instead of accessing them through a common interface the current approach is to convert to whatever mesh format is understood by the current tool. Unfortunately these conversions can happen quite often, be very costly and in the worst case make no good sense at all.

A good example of this sort of behavior is in the way Multi-resolution meshes are currently dealt with. In order to utilize the edit-mode transform tools on multi-resolution data it must first be converted to an Edit-Mesh. However the huge memory overhead of the editmesh data structures make no sense when applied to mesh whose topology is for all intents and purposes fixed. This problem is further exacerbated by the fact that the highest levels of a multi-resolution mesh can frequently contain millions of polygons.

This example may sound bad, but it is after all isolated to Editmode. Unfortunately the lack of a common mesh interface has a severe impact on memory usage of multi-resolution meshes in object mode as well. Currently much of Blender’s object mode code expects a mesh to be in the format of ‘Mesh DNA’. Therefore the active level of a multi-resolution mesh must always be ‘baked’ to Mesh DNA. In the best case the effect of this is negligible. In the worst case however, which also happens to be the most common, it represents a doubling of memory requirements.

Another area in Blender where conversion of mesh data occurs too frequently is in the modifier stack. For all non-deforming modifiers a full copy of the derived mesh, with needed modifications, is created every time the modifier is evaluated. Although Blender’s dependency graph insures that modifiers are not evaluated needlessly, in the worst case scenario a full evaluation can occur during every redraw loop. Therefore it is appropriate to investigate solutions that would only require conversion when absolutely necessary.

In addition to conversion problems, Blender in general, and the modifier stack in specific suffers from a great amount of duplicated code when dealing with meshes. For example, in most cases each modifier’s effect can be understood in terms of a combination of very common, lower level operations, such as, “Duplicate these faces and then apply some transformations to them”. Unfortunately each modifier more or less re-implements these primitive operators for itself instead of utilizing a library of common functions. This leads to code that is not only monolithic, but also difficult to maintain and debug.

Although identifying common functionality in the existing implementation and separating it out into discrete functions would help to alleviate these problems, it would still leave the problems one faces when using a common format to manipulate mesh data, mostly to do with efficiency and memory overhead. The solution is to move nearly all modeling functions into various mesh kernel back-ends that appear identical to the individual modifiers and other Blender facilities.

An added benefit of separating mesh back-end implementations completely from their interface is that it would become possible to tune the various back-ends for maximum performance. For instance it is now very difficult, if not impossible to optimize drawing of sculpt mode when used in conjunction with the modifier stack. However a sculpt specific backend could be written that would appear the same as any other mesh to the modifier stack and allow for tremendous speed-ups while keeping all implementation details hidden.

Design Constraints

• No assumptions made about how data is stored in the backend
• All access to mesh data (including changes to data) must be made through the abstract interface
• Strict control over modifying data (model begin/end blocks)
• Support callbacks for standard set of modeling operations as well as adjacency queries and mesh iterators
• Standard interface for querying mesh backend about capabilities and providing conversion services

The structure

See current sketch of the new structure design (called Abstract Mesh) at the Abstract Mesh .h wiki page.

Discussion

I have some doubts about the proposed structure design by Joedh. I have not yet fully dissect it but i think it does not fullfill what we need to aim for.

keygoals as i see them to respect the design constraints are :

1. efficiency
2. encapsulation of the gritty details by a comprehensive API without exposing at all the back-end
3. allow per-backend optimizations and/or overloads of the basic API if better ops are available
4. be not too cumbersome to use and expandable later.

• in the proposed system, we need to pass a self pointer to each of the functions stored in the structures, so you call e.g. am->drawer.drawFacesShaded(am); this fix completly the structure and functions of the backend to be identical to API even if it could do things more efficiently. Something like amdrawer(am,DRAWFACESHADEDOP) is imho both nicer to write but also allow your backend to do it the most efficient way. If the requested op is not implemented/available, an error code is raised. The drawback of this approach is of course argument passing, but there is solutions for that. this is especially important for queries (topological infos) and modeling ops. It is also easily expandable.
• instead of the current system of creating a new derived mesh each time a modification is done, in place conversions are huge deal.
• you can have a does backend support this op request easily and use an alternative if needed.
• that does not forbid to use callback too in a two tier system
  • the abstract mesh higher level operations are built on callback calls (not exposed in API)
  • the backend provide the needed pointers
• the operations that need to be very efficient are the foreach*** and get***atindex funcs

Lukep 01:16, 17 February 2008 (CET)

Overall I think the design here goes in the right direction, but some points:

• I don't understand Lukep's the comments about the API being fixed for backends. As I understand it that is exactly the point, if each backend support slightly different functions then it becomes messy. Part of the confusion with derivedmesh was exactly that some backends don't support certain functions. When you're in the drawing code and then have to check if it can actually draw shaded faces, that's _very_ bad in my opinion. A backend should just support all drawing functions or none. I think it is very hard in practice to predict what a mesh will be used for at the moment that it is made (e.g. in object_handle_update as part of the the depsgrah evaluation). If you then later find out it doesn't support certain functionality that is needed, you don't want to do a conversion each time.
• For modelling functions I can understand you have to query capabilities and possibly convert, but for drawing and querying data that's a bad idea in my opinion. A lot of functions fall back to just using the derivedmesh as an array, since it is very convenient to do that, and you know it is supported. Moving to an iterator type access instead is fine for me, but then that should also be supported for every backend in the same way.
• The AbstractDrawer function should not be tied to the drawmodes in my opinion. The calling function should be able to specify certain layers (position, normal, texture coords, vertex colors) to be used, and can then do all opengl material setup itself. It's not that different from what is there now, but I think it's a direction that the mesh drawing system should move in, not being so bound to the modes and drawmodes.
  • I agree, the latest version of the header now works roughly like you said, though it's probably not quite all there yet. Joeedh 06:03, 25 February 2008 (CET)
• From the design here it's not clear to me how modelling would work. There is AbstractModeler which presumably will mostly be a frontend to a bmesh backend. I don't see how an array based mesh could support those kinds of operations with reasonable efficiency. So does that mean that nearly all modifiers will work with a bmesh type backend, with the exception of those that have their own backend (subsurf)? Or will there be AbstractModeler functions suitable for tools like mirror that work with an array based mesh?
  • Part of this is the array pool allocator for fixed-size elements. It will eventually be used to implement a compact structure that'll support these modeling interfaces without sacrificing speed (or memory space). Joeedh 06:03, 25 February 2008 (CET)
• And also another point about implementation. For anyone working on this, I would advise to not just throw out derivedmesh and start from scratch, but rather gradually change derivedmesh to follow this design. Derivedmesh works, and by changing it's API gradually it will be much easier to debug, since you can debug each step individually, and not spend time tying up a lot of loose ends at end. Complete rewrites tend to get stuck because the task is so big, and there is no good overview of what still needs to be done. By changing things gradually you can ensure that even if not everything gets implemented, you will still have improved some part of the system.
  • Discussed on irc. It will be a gradual task, starting with the modifier system. Joeedh 06:03, 25 February 2008 (CET)

Brecht 15:21, 17 February 2008 (CET)

• of course Abstract mesh API should be fixed. My point was that doing it via function pointers restrict a lot flexibility how the backend implement it. Doing it via message calls may allow a backend with particular needs to do it in a different way. This mostly apply to the modeling part, draw and query are fine with pointers.
• the problem is imho mostly the modeling part in any case. backend need to be reasonabilly efficient on the basic ops, so that the modifiers can use exclusively the API.

Lukep