Mesh Type Requirements¶
In order to be able to do procedural mesh generation/modeling, a data structure for the Mesh type is needed. Instances of this type will be passed around when a node graph, that represents data flow, is evaluated.
The requirements mentioned below might be a bit subjective. In theory, a different set of requirements could work as well. The examples are just mockups, it probably won't look like this in the end.
This document does not propose a concrete data structure.
Hard Requirements¶
The aspects mentioned below are a must-have. Without these, we loose significant parts of functionality and flexibility.
Primitives¶
The mesh can consist of multiple primitives. A primitive contains an arbitrary number of mesh islands. The complexity of a primitive largely depends on what the user is working on. Possible primitives in different contexts are:
- an empty mesh,
- a single point,
- a single triangle,
- multiple of those and
- the entire mesh (with potentially millions of polygons).
Vertices within separate primitives must not be connected by an edge.
Further Thoughts¶
It could be possible to have primitives within primitives within primitives etc. However, I'm against this idea because:
- It makes it much harder to grasp the concept.
- Individual functions are simpler when they don't have to deal with a recursive structure.
- Usually one only works at a single "abstraction level". E.g. one is either interested in working on individual polygons, or in moving entire buildings.
Example Usage¶
Attributes¶
The next key concept are attributes. An attribute is identified by its name. Therefore it is not possible to have two attributes with the same name on a single mesh.
Attributes can be dynamically added, modified and removed from a mesh.
Every Attribute has a specific type (int, float, vector, ...).
Attributes can be stored per vertex, per loop (corner of a polygon), per edge, per polygon and per primitive.
All primitives within a mesh have the same attributes.
Attributes can be queried on the vertex/loop/edge/polygon/primitive level. If the attribute has not been specified at the level it has been queried from, it has to be interpolated from another level. In some cases, that interpolation is simple. E.g. when the color of a vertex is queried, but the color is only stored per primitive. In that case, the color of the primitive is simply used as vertex color. Sometimes, multiple values have to be mixed. E.g. when the color has been stored per polygon in the above example.
Some attribute names are reserved for intrinsic attributes. These attributes can be derived from other attributes automatically and cannot be changed by the user. The most obvious examples for this are Vertex Normal and Face Normal. If custom normals are required, those should be stored in a separate attribute.
Further Thoughts¶
The automatic conversion is not strictly necessary, but it keeps the node tree more clean in common cases. The alternative would be, that the user had to insert conversion nodes. This is still possible, when more control is needed.
There are more aspects of a mesh, that could hold attributes. I mainly think of half-edges here (i.e. one value per edge per vertex). There could be some use cases for this, but it does not feel like this is worth the effort.
I'm not sure yet, if the vertex position should be an attribute as any other. If not, then there could be a mesh, that does not store any information per vertex. Such a mesh could not be rendered. Furthermore, the number of vertices would have to be stored separately. It might be a good idea to have vertex positions as attributes internally, but ensure that the vertex position attribute always exists.
Example Usage¶
Groups¶
In classical polygon modeling, the user selects the mesh elements that should be modified. In a procedural setting, this can't be done easily, because the user would have to re-select everything when the mesh changes.
Instead, groups become much more important. A group is just like a selection. There can be groups of vertices, edges, polygons and primitives.
Each group is identified by its name within the entire mesh.
A group can contain elements from a single or multiple primitives.
Groups can be ordered or unordered.
Groups can be created, modified and removed dynamically.
Further Thoughts¶
I'm not yet sure, if groups of loops should be supported.
We could keep all groups ordered. Unordered groups mainly exist for optimization reasons.
Example Usage¶
Desirable Properties¶
These requirements are not strictly necessary, but would be good to have.
Different Implementations¶
Different kinds of polygon mesh algorithms query and modify a mesh in different ways. There is no single data structure that supports all types equally well. Therefore, it would be nice if the used data structure could change, depending on what operations are performed.
Note: I'm not suggesting that we put different implementations behind a common interface. If a specific function does not support the given data structure, it has to convert it first.
Right now, I can think of three different access patterns, that should be considered:
- No topology lookup (e.g. all vertices are moved one unit on the x axis).
- With topology lookup (e.g. all vertices are set the the center of their neighbors).
- With topology lookup and topology changes (e.g. extrude operation).
Shared Memory¶
The general idea is to save memory by using the same buffer for multiple things. This concept can be applied at different scales.
A typical example would be to use topology information in two meshes, when they share the same topology, even though their vertex positions are different.
Shared memory can also be used when, on the user level, a color is stored per vertex, but Blender knows that the color is the same for all vertices in a primitive. In that case, the color itself only has to be stored once.
Instancing¶
When a mesh contains the same sub-mesh very often, instancing should be used. It should work when the individual instances are primitives, but also when there are multiple instances within a primitive.
When a function does not know how to deal with instancing, or it has to modify data of individual instances, the instances are "made real".
Efficient Group Operations¶
It should be possible to invert groups efficiently. Meaning that, all elements that were in the group before, are not in the group afterwards and vice versa. This becomes important when e.g. there is a large mesh, and the original group only contains a single polygon.
Other set operations like union, difference, etc. should be efficient as well.
Wrap Existing Structures¶
We already have different mesh data structures in Blender. Afaik, they do not fulfill the requirements I have for a data structure that can be used in a node based context successfully. Nevertheless, it would be good, if a conversion could be avoided as long as possible.
Independence¶
It should be possible for any part of Blender to take full ownership of a mesh. That also means, that others must not modify it anymore. Ideally, this should be possible without doing defensive copies of everything.
Plain Arrays¶
As much as possible, data should be stored in plain arrays. Different attributes should not be mixed in the same array. That benefits re-usability of buffers and simplifies interfaces to functions, that only care about these plain arrays (many functions don't need more than that).