Tag Archives: LDraw

Level of detail and geometries merger

The Level Of Detail avoids to display a far object with lot of details. In fact, if an object is far, we can't see the complexity of the object. So the aim of the LOD methods is to decrease the complexity of the object depending of the distance on the point of view.

A model with two resolutions. The studs are composed of 16 quads or 64 quads.
A model with two resolutions. The studs are composed of 16 quads or 64 quads.

Ldraw uses a basic LOD: many objects may use two different resolutions (it concerns cylinders and curved surfaces). On the picture, meshes of stud are more detailed in the second case. The LDraw format file has been created before the 3D evolution in computer sciences, so it considers non smoothed primitive. With this technical limitation, if you want great visual result, you need to increase the number for primitives. So using smoothed surface may resolve the using of detailed meshes. Next, the Ldraw format is a tree structure. Each file contains an average of 15 primitives (quads, triangles, lines) and a list of links to other files. This structure is convenient if you have memory limitation but today graphical cards prefer big meshs than lot of little parts of an object. The program wastes time during tree traversal, transformation selection and culling. The best way is certainly to merge the object whose the memory size is relatively small. So the culling time is insignificant and the global time is lower even with a high resolution.

These screenshot show the computation time to display the same object. The top left image corresponds to the low resolution. At the top-right, the merged low resolution. At the bottom-left, the high resolution. At the bottom-right, the merged high resolution case.
These screenshot show the computation time to display the same object. The top left image corresponds to the low resolution. At the top-right, the merged low resolution. At the bottom-left, the high resolution. At the bottom-right, the merged high resolution case.

The screen-shots show that we obtain speed-up of 25 and 33 for respectively the low and high resolution.

  • low resolution non-merged: 10.4 + 4.5 = 14.9ms
  • low resolution merged: 0.2 + 0.4 = 0.6ms
  • high resolution non-merged: 29 + 14.2 = 43.2ms
  • high resolution merged: 0.2 + 1.1 = 1.3ms

Three points needs to be implemented:

  • LDraw format proposes two type of line (line and optional line) which are merged. These type of line need to be splitted to use them correctly.
  • The second point concern the color, it exists two type of objects: the monochrome parts and the part with motifs (patern). Commonly, monochrome part use the color 16 for each primitive. So color mechanism don't need to be implemented as a color vector. But for patern part, object should be splitted to separate monochrome color and motif.
  • The third point, concern the propagation of the color during the merge. An color indexes vector exists but we don't use it because there are difficulty which the color 16. During the merge, the color 16 may needs to be replace by an other color and I'm sceptique about the interrest to use indexes vectors to group colors.
  • From the application point of view, we need to create a mechanism to exclude a part of the object during the merge. Many times, we will need to separated parts of an object (for example: a door need to be be separate from an house to allows interaction with the door).

Geometry

This third post concerns many points of a LDraw Loader with OpenSceneGraph Library. OSG has plugins with read different format. Each plugin is related to a file format. OSG offers to create customized loader plugins. To be honest, I don't know how are constructed all formats of different 3D models. OBJ format need to read a file with the material properties and I'm not sure that it exists 3D model format which use more complex tree structure. So the LDraw format is special, made of repetitive patterns, and it needs to load many files to complete a model. A file which needs to load a file which needs to load a file ...

Application which uses Qt and OpenSceneGraph. It displays LDraw format. At the right of the window, the tree corresponds to the graph of OSG. At the left, there are many data about the selected item (here transformmatrix)
Application which uses Qt and OpenSceneGraph. It displays LDraw format. At the right of the window, the tree corresponds to the graph of OSG. At the left, there are many data about the selected item (here transformmatrix)

For the LDraw loader, I don't want use recursive algorithms because bugs may easily appear. The second point, I need to keep all of the loaded file in memory and avoid to load many times the same pattern. I think it exists in OSG a mechanism to avoid this but I'm not sure of its use. So I have chosen to have a list of models and I have split the loading process into 2 parts: the loading of the data from a file and a mechanism which links models. So when the program load data, it creates a geometry model and stores the name of the model. Next, the model is put in the models list. During the second step, for each loaded model, the program reads the name of children. If the file is already loaded, it creates a link to the corresponding model, else it loads the file and store it in the queue of the list of models. This system is easy to implement but I don't know if it is the best method. Nevertheless, it appears that LDraw models are a support to avoid to recreate model and I will use an another format in my future applications.

A second difficulty concerns a strange choice about the Back Face Culling. The BFC avoids to display faces which aren't visible by the camera. In fact, it is interesting for speed gain during rendering. There are two modes: Clockwise and Counter-Clockwise. LDraw use CCW by default but can use CW and many time a subpart of a model need to invert the BFC mode. For example, to create a hollow cylinder, the author need use twice a cylindrical surface: an external surface and an internal surface. The two surfaces correspond to the same model with a different scale. If the BFC mode is the same for all surfaces, a camera in the center of the hollow cylinder will display no one of the surfaces. So the author of the part needs to invert the BFC of the internal surface. In the LDraw format, the Meta-Command 'INVERTNEXT' allows to change the BFC of the next submodel. I have chose to duplicate the model and flip all geometries and submodels. The new model is registered to the models list with the suffix '_INVERT'. My main use of the BFC concerns the direction of the normal vectors (for light reflexion). There is an another problem with BFC: if there are a negative scale for a submodel (the determinant of the transformation matrix is negative), BFC need to be inverted. So there are two types of inversion: an inversion of a model and a inversion due to transformations (translate, rotate, scale). An inverted model has inverted normal but transformation may change BFC but not normals. For display a brick as an group of submodel, I prefer deactivate the BFC. When I will merge all geometries of a brick in a unique object, it will be possible to reactivate BFC.

In the next post, I will talk about the colors and the Level Of Detail. Currently, only a basic LOD is implemented. This corresponds to a Ldraw specifications for the resolution mesh of a curved surface (as cylinders).

A file format for Lego Models

From LDraw website:

LDraw is an open standard for LEGO CAD programs that allow the user to create virtual LEGO models and scenes.

Ldraw standard has been created in 1995. Many softwares have been created based on this format: LeoCad, MLCAD, SR 3D Builder, Bricksmith LDView... Each of them has their specificities, SR 3D Building is used for Technic model, LDView modify primitive for best rendering, ... Also there are WebGL Viewer and many other tools (LSynth allow to create bending part, exporters to modeler 3D...).

The main competitor of softwares based on LDraw is the official LEGO software: LEGO Digital Designer. Even if a user can create models, he can't use his creation with other softwares. In fact, model exporters exist but the geometry of bricks is unavailable and the user needs an another source of geometries (as LDraw).

So today, I think to create a new LDraw viewer is a needless work. The purpose of my project is the creation of content and games based brick (I avoid to use the 'LEGO' Trademark). But before to aim this dream, we need a basic renderer. Format explanation is described in the tab 'Documentation' of the LDraw website.

My first subject is the color of brick. In a file of the LDraw library (LDCfgalt.ldr), there are the list of available colors. Each color is associated with a number. Obviously, each brick will be associated with a color. A special color exists which allows to define sub-model without specified color. It allows to create a model with many identical sub-model with different colors. The color will be propagated to children of this model. The most of basic bricks use this special color. For others, many bricks have motifs and pictures. Theses motifs are primitives with fixed color. To create new motif, you need a software which manipulates vectorial image (DAT2QP). The color may be propagated by several methods: it depends of many parameters as the file structure. Presently, I don't know the best choice of propagation method.

ghosts
Each ghost corresponds to the same sub-model with a undefined color (except eyes which are white and black). The colors are defined in the model with the four ghosts.

The second point concerns the format files. LDraw has three different extensions MPD, LDR and DAT. In fact, the three types of file use the same format. MPD is the extension of multi-parts document, it aims to group many subparts. LDR is the default extension, it contents the model. DAT is the extension for parts, it concerns basic bricks geometries. In a file, there are many types of primitives, they concern geometries (lines, triangles, quads, optional lines), relative files (children part), and meta-commands (informations, color, back-face-culling,...). So a basic brick is composed of lots of subfiles. For example, the brick 3001 (2x4) is composed of 12 different subfiles (some of them is used many times as studs). Each brick is associated with a big graph. This choice of the structure was certainly due to the memory capacity of computers: bricks use the same primitives, so few different primitives. Today, computers lost lots of time to display a brick by going though graph.

This first post is an overview of LDraw format. So Ldraw is an open format and is easy to use. There are two problems to fix: how should we gain computing time and how can we manage colors.