User:Someonewithpc/GSoC2019/Proposal

Synopsis

The current importers and exporters in Blender are written in Python and take a long time when handling complex models, especially for meshes with millions of vertices, which aren’t uncommon. These operations can take several minutes to process, which creates frustration in users and decreases their productivity. This project will provide faster Import and Export operators for OBJ, STL and PLY formats, achieved by porting to C/C++ and a common import/export framework.

Benefits

This projects will port and, where applicable, rewrite the Python implementation to a native C and C++ one, which, together with using memory mapped I/O and parallelism will significantly speed up these operations. This project will also provide a structure and library for other formats, making further development easier.

Deliverables

End users will experience a significant speed up, without any negative change in how the tools work. Aditionally, a new common framework will make it easier to integrate other Importers and Exporters for other formats. This would pave the way for a better integration with other industry tools and make Blender a more viable option for use by studios and professionals in the industry.

Specifically, I will make an OBJ file importer and exporter, complete with Nurbs and Material support and PLY and STL importers and exporters capable of both using the ASCII and binary variants. I will also create documentation on the shared framework, to make it easier for future developers. Internally, the tools could be parallelized where applicable, if, after measuring, it is deemed worth it. In addition, the existing test suit will be expanded to prevent regressions and ensure equivalency between the existing and new operators.

Project Details

The current OBJ, PLY and STL importers and exporters are written in Python and can be relatively slow. Writting these parts to C and C++ modules will reduce these times by a significant factor. There have been a few attempts at projects like this, which indicates this is a desired project. This project will start by creating a common framework, on top of which three new modules, one for each of the exporters, can be built, sharing as much code and structure as possible. This aproach will make maintenance easier, as it avoids violating DRY principles, as well as make adding new formats an easier tasks.

I opted for using C++ as it is a very expressive language which still allows for easy integration with the existing C code and fast compiled results. The common framework as well as the new module interfaces will be implemented in C as much as possible, in order to maintain a lowest common denominator and avoid locking in future developers to the choice of C++. The C++ will be implemented in a data oriented way, as opposed to object oriented, avoiding runtime polymorphism. This will make the code path more explicit. File input and output will be made with memory mapped IO, through boost::mapped_file. Aditionally, some parts of the process can be parallelized, through the use of OpenMP or the BLI_threads API. The relative advantages and performance of these alternatives will be measured and the fastest will be implemented. OMP support on macOS is still not completly developed as on other platforms, so, in that case, it would probably be best to use BLI threads, however the performance versus code complexity of each will be evaluated. BLI threads seem more favoured by the developer community and there were some efforts to move away from OMP. Additionally, in those aplications, BLI threads were faster.

This should significantly speed up the resulting operators. The input parsing will be handled by which ever version is faster, between the STL std::cin::operator>> and boost:spirit. These libraries are different in workings and capabilities, but they can both adapted to the needed work.

A primitive exploration of these ideas can be found in the patch D4575, which I wrote as a way of testing the feasibility of this project as well as to get myself more familiar with the code.

In summary, the code structure will be as follows:

The new file blender/editors/io/io_common.h contains definition of struct ExportSettings which will be common to all new formats, as well as definitions of utility functions which unify the defintion of new operators. A sketch of struct ExportSettings is as follows:

struct ExportSettings {
    struct ViewLayer *view_layer;  // Scene layer to export
    struct Depsgraph *depsgraph;   // Deps graph used for evalating objects
    ...
    char filepath[FILE_MAX];
    bool selected_only;
    ...
    float frame_start;
    ...
    bool export_normals;
    bool export_uvs;
    bool export_materials;
    ...
}

The OBJ export operator is defined as

void WM_OT_obj_export(struct wmOperatorType *ot) {
    ot->name = "Export Wavefront (.obj)";
        ... 
    ot->exec = wm_obj_import_exec;
    ...
        // Function in io_common.h which declares the RNA properties for this operator
        // These are made common to all new operators, to, again, reduce code duplication
    io_common_default_declare_export(ot, FILE_TYPE_OBJ);
}

Similarly, the exec function is defined in terms of a common function which allocates a struct ExportSettings struct, fills it in from the values the user provided by selecting the desired options in the interface, and calls the function pointer passed in with this struct. The called function is responsible for freeing the struct when it is done with it.

static int wm_obj_export_exec(bContext *C, wmOperator *op) {
    return io_common_export_exec(C, op, &OBJ_export /* pointer to export function */);
}

The OBJ_export function is defined in the new file blender/editors/io/intern/obj.cpp, thus a C++ file. This function is the entry point to the actual exporting.

bool OBJ_export(bContext *C, ExportSettings *settings);

A sketch of the export algorithm is as follows:

fs = fstream.open(settings.filepath)
for each frame
    for each object
        ob = DEG_get_evaluated_object(settings->depsgraph, object)
        if (common_should_export_object(settings, ob))
            common_get_final_mesh(settings, eob, &mesh /* OUT */)
            OBJ_export_mesh(C, settings, fs, eob, mesh, vertex_total, uv_total, normal_total)

This, again, is a general algorithm in the common library. For this one, as it’s written in C++, a templated function will be used to make it possible to adapt it to each format.

This also constitutes a point where paralelization is possible. It’s possible to export each object in parallel, to export each frame in parallel or to export each of vertices, normals and uvs in parallel. These all have different advantages and disadvantages, as well as different complexities. These will be evaluated and could be tuned based on the ExportSettings (no sense in parallelizing at the frame level when animation is disabled or when the file is small). OpenMP could be used for a quick way to gauge the performance difference, but, ultimately, BLI threads will be used, if it’s deemed worth it.

The OBJ, STL and PLY formats were selected because they’re simple, yet widely used. There’s no reason why other formats can’t fit the same framework, however, as this project has a limited timescale, they will be left for future implementations. A possible stretch goal would be unifying the current Collada and Allembic exporters with this new framework. This would be a significant time investment, so it’s not planned, but, if there’s time, I will attempt it.

The current patch, while limited in capabilities, already shows significant speed ups, in the order of 3x, for release builds. This difference is expected to increase with the use of memory mapped IO.

OBJ format

Using the C printf format specifiers as placeholders and [] to denote optional parts, the format can be summarized as:

# A comment
# List of vertices starting at 1
v %f %f %f [%f]
...
# List of texture coordinates
vt %f [%f [%f]]
...
# List of normals
vn %f %f %f
...
# List of faces
# v_i is a vertex index, vt_i is a UV coordinate index, vn_i is a normal index
# Each face can have three or more vertices and vertices may or may not have
# uv and normals associated
f v_0[/vt_0][/vn_0] v_1[/vt_1][/vn_1] v_2[/vt_2][/vn_2] [v_i/vt_i/vn_i ...]
...

MTL and Materials

The OBJ format also includes support for materials, through the MTL format. This support, however, is based on the Phong reflection model, which isn’t what Blender currently uses and the mapping is, therefore, not complete. Some implementations extend the standard to include more modern materials, however this behavior is not standard.

Some of the properties expected in a MTL file are:

Ka %f %f %f # Ambient color
Kd %f %f %f # Diffuse color
Ks %f %f %f # Specular color
Ns %f       # Specular exponent. Between 0 and 1000
illum %d    # Illumination model (defined below)

The illumination models allowed are based on a somewhat restrictive predefined set and the mapping to Blender’s can be somewhat fuzzy.

The specification lists the following illumination models:

0. Color on and Ambient off
1. Color on and Ambient on
2. Highlight on
3. Reflection on and Ray trace on
4. Transparency: Glass on, Reflection: Ray trace on
5. Reflection: Fresnel on and Ray trace on
6. Transparency: Refraction on, Reflection: Fresnel off and Ray trace on
7. Transparency: Refraction on, Reflection: Fresnel on and Ray trace on
8. Reflection on and Ray trace off
9. Transparency: Glass on, Reflection: Ray trace off
10. Casts shadows onto invisible surfaces

Aditionally, properties such as the diffuse color, the specular color and the ambient color can be mapped from textures, in which case they’re listed as:

map_Ka imagefile       # Ambient color map
map_Kd imagefile_diff  # Diffuse color map

In Blender, materials are represented inside a struct Material, which can be either be owned by an object or a data block. Therefore the materials can be accessed either through ob->mat or ob->data->mat, where ob is a struct Object, in the case of a simple object.

The struct Material is, in summary, as follows:

struct Material {
    float r, g, b;             // Diffuse
    float specr, specg, specb; // Specular color
    float spec;                // Specular intensity
    float roughness;
    float metallic;
        ...
}

Therefore the mapping for these properties can be made from these values.

ASCII STL format

The ASCII STL format consists of:

solid [%s(name)]
facet normal %f(n_i) %f(n_j) %f(n_k)
  {outer loop
    {vertex %f(vx) %f(vy) %f(vz)}{3,}
  endloop}+
endfacet
endsolid [name]

Where %f a floating point number in scientific notation and {}+ denotes a list of one or more facets. The orientation of a facet is redundantly specified by the normal, which defined to point in the “outwards” direction, and the vertices are required to be listed in counterclockwise order when looking from outside. The format allows facets with multiple loops and loops with more than three vertices, but this is not widely used in practice.

Binary STL format

As it is more widely used, the STL Binary format was selected instead of the ASCII variant. There’s no reason why both can’t be implemented, the choice exposed to the user in the export interface, however, as a start, only the binary format will be implemented.

The binary STL format consists of:

80 byte ASCII header
4 byte count of facets
{
  4 bytes for normal i
  4 bytes for normal j
  4 bytes for normal k
  4 bytes for x vertex 1
  4 bytes for y vertex 1
  4 bytes for z vertex 1
  4 bytes for x vertex 2
  4 bytes for y vertex 2
  4 bytes for z vertex 2
  4 bytes for x vertex 3
  4 bytes for y vertex 3
  4 bytes for z vertex 3
  2 bytes for an unspecified attribute
}+

Like in the ASCII variant, the order of vertices is important.

PLY format

This format is defined by a header, which specifies the elements of a mesh and their types, followed by a list of the elements themselves. It has two variants, an ASCII based one and a binary one.

The header is as follows:

ply
format [ascii | binary_little_endian | binary_big_endian] 1.0
comment This is an example comment
{
  element %s(name) %d(n)
  [{property %s(type) %s(name)}{n} |
   property list %s(type) %s(type) %s(name)]
}+
end_header

Where type is one of char, uchar, short, ushort, int, uint, float, double, int8, uint8, int16, uint16, int32, uint32, float32 or float64. For the case of lists, the first element is the length of the list and the remaining numbers are the elements.

In the ASCII version of the format, the vertices and faces are each described one per line with the numbers separated by white space. In the binary version, the data is simply packed closely together at the endianness is specified in the header and with the data types given in the property records..

Parallelization

The parallelization will be left as a secondary goal, as it’s not essential, but it should provide a signifcant performance boost. OpenMP will be used to explore the possible benefits of parallelization and if it’s deemed worth it, BLI threads will be used and the performance difference will be measured.

Regression Testing

There is a small test framework for OBJ, but it simply exports a cube. The tests for Alembic are more extensive. Initially, the testing will be expanded to make comparassion between the existing operators and the new code simpler and more methodical.

Project Schedule

As I already have a working patch, I expect the project to go rather smoothly. I think it will be possible to for the project to be completed in 12 weeks. I will begin working as soon as the results are announced.

The expected timeline is as follows:

1st week: Extend the OBJ exporter to include missing functionality like Nurbs

2nd week: Extend it further to include materials. Regression testing

3rd week: Implement the OBJ importer. Initial exploration of parallelization

4th week: Implement the ASCII STL exporter and importer. Evaluation

5th week: Extend the framework to generalize common tasks. Bug fixing

6th week: Implement the ASCII PLY exporter and importer

7th week: If parallelization is worth it, implement it

8th week: Implement the binary variants of PLY and STL exporters and importers. Evaluation

9th week: Refine the framework and bug fixes

10th week: Final documentation of the framework

11th week: Finalizing regression tests

12th week: Buffer week. Finalization and evaluation

I expect the timeline to be slightly fluid in terms of the order of operations, but it shouldn’t affect the overall success.

Bio

I am Computer Science student at the University of Porto. My interest in programming and Blender started at the beginning of middle school. I always wanted to start developing games, so I dedicated myself to learning these tools. Since then, I learned I really enjoy programming and I have gained a lot of experience working with Blender as a user, as well as some experience working with it as a developer. I enjoy learning languages (I speak Portuguese, Spanish, English and I am learning Esperanto and Polish), reading and solving Rubik’s cubes and other puzzles. I think Blender has very strong potential to become a major tool for game creation, where the problems I want to address are often faced. Free software is something I deeply care about, as I think users should have these fundamental freedoms. I have some experience with Blender’s code, having fixed T50132, in the bug tracker and having worked on trying to fix a few other bugs, as well as working on D4575 as a start for this project. I have a lot of experience with C, C++ and Python, as these were the languages I focused more on learning, since they’re commonly used in systems like games and robotics, which interest me.