Level of Detail for Parts

[Ben Supnik]

Hi Y'all,

I hit a bottleneck in my performance optimization work with BrickSmith: LDraw parts have no concept of "level of detail."

If I open Datsville, I'm staring at 125,000,000 vertices. They aren't all necessary when drawing the entire model in an 800 x 600 window, but there isn't any meta-data to help me drop some of them.

This is half of the level-of-detail problem: for very low-resolution rendering of huge models, the parts are too detailed, burning GPU power. The flip side of this is that close up, the studs look like prisms and not cylinders because of the low vertex count.

This got me thinking: if parts (or sub-parts) had a level-of-detail scheme (with multiple versions of the parts for different resolutions) we could have our cake and eat it: for wide views a stud could be a cube or some other super-crude, super-cheap structure. At high res we could crank the vertex count, eliminating the need for viewers to do ad-hoc sub-part substitution.

Here's the question I have: how could/should a renderer decide _which_ level of detail to draw? I can think of a few heuristics:

- The levels of detail are arbitrary; the client program picks one based on current performance and context. In other words, when you say "export PNG" the highest level is always used. During rendering, the program steps down LOD one notch any time the framerate drops below 10 fps and cranks it up one notch any time it exceeds 30 fps.

- Levels of detail are based on scale. In other words, each level of detail specifies a range of pixels that an LDU covers. If the rendering scale is such that an LDU is less than "X" pixels, we go to the next LOD.

- (If LODs are based on scale, then we have to ask whether the cut-over points should be arbitrary or specified in the spec or library standards. There's a big technical win for programs if there aren't a million different cut-over points.)

Are the LODs advisory or required in their cut-over points (for programs that understand LOD)? Thoughts?

My hope with LOD is that with a little bit of work on a very small number of sub-parts, we could make a big difference. For examlpe, just by creating an octagon low-LOD stud, we could cut 90,112 vertices from every 32x32 baseplate - there are only 3 sub-parts that would need modification in this case. I think the strong factoring of the part library could be a big win here.

Cheers
Ben

[Tim Gould]

My hope with LOD is that with a little bit of work on a very small number of sub-parts, we could make a big difference. For examlpe, just by creating an octagon low-LOD stud, we could cut 90,112 vertices from every 32x32 baseplate - there are only 3 sub-parts that would need modification in this case. I think the strong factoring of the part library could be a big win here.

Cheers
Ben

Hi Ben,

Creating every part multiple times for different LOD would be, in my opinion, pretty much impossible. However... there already exists an octagon level stud by requirement. You simply replace stud.dat by stu2.dat. Other stud parts have similar replacements.

Tim

Here's a list
stu2.dat:0 Stud (Fast-Draw)
stu211.dat:0 Duplo Hollow Underside Stud Wide (Fast-Draw)
stu212.dat:0 Stud Underside Cross (Fast-Draw)
stu213.dat:0 Stud for Electric L & S Brick 2 x 2 x 1.333 (Fast-Draw)
stu215.dat:0 Stud for Round 2 x 2 Parts, 1 Face, Complete Edges (Fast-Draw)
stu216.dat:0 Stud Tube Open Split (Fast-Draw)
stu217a.dat:0 Stud Open For Octagonal Parts without Base Edges (Fast-Draw)
stu22.dat:0 Stud Open (Fast-Draw)
stu22a.dat:0 Stud Open without Base Edges (Fast-Draw)
stu22s.dat:0 Stud Tube Open Sliced (Fast-Draw)
stu23.dat:0 Stud Tube Solid (Fast-Draw)
stu23a.dat:0 Stud Tube Solid without Base Edges (Fast-Draw)
stu24.dat:0 Stud Tube Open (Fast-Draw)
stu24a.dat:0 Stud Tube Open without Base Edges (Fast-Draw)
stu24f1s.dat:0 Stud Tube Open with 1 Fillet Standard (Fast-Draw)
stu24f1w.dat:0 Stud Tube Open with 1 Fillet Wide (Fast-Draw)
stu24f2n.dat:0 Stud Tube Open with 2 Fillets Narrow Opposite (Fast-Draw)
stu24f2s.dat:0 Stud Tube Open with 2 Fillets Standard Opposite (Fast-Draw)
stu24f2w.dat:0 Stud Tube Open with 2 Fillets Wide Opposite (Fast-Draw)
stu24f3s.dat:0 Stud Tube Open with 3 Fillets Standard (Fast-Draw)
stu24f4n.dat:0 Stud Tube Open with 4 Fillets Narrow (Fast-Draw)
stu24f4s.dat:0 Stud Tube Open with 4 Fillets Standard (Fast-Draw)
stu24f5n.dat:0 Stud Tube Open with 2 Fillets Narrow Adjacent (Fast-Draw)
stu24h.dat:0 Stud Tube Open with Extended Hole (Fast-Draw)
stu24o.dat:0 Stud Tube Open without Outer Cylinder (Fast-Draw)
stu24s.dat:0 Stud Tube Open Sloped (Fast-Draw)
stu24s.dat:0 !HELP sloped - Y common border. (Fast-Draw)
stu24s2.dat:0 Stud Tube Open 0.500 Sloped (Fast-Draw)
stu24s2.dat:0 !HELP (Fast-Draw)
stu25.dat:0 Stud Scala (Fast-Draw)
stu26.dat:0 Stud Open For Round 2x2 Parts (Fast-Draw)
stu26a.dat:0 Stud Open For Round 2x2 Parts without Base Edges (Fast-Draw)
stu27.dat:0 Stud Duplo Open (Fast-Draw)
stu28.dat:0 Stud Duplo Tube (Fast-Draw)
stu29.dat:0 Stud Open with Small Hole (Fast-Draw)
stu2a.dat:0 Stud without Base Edges (Fast-Draw)
stu2p01.dat:0 Stud with Dot Pattern (Fast-Draw)
stu2x.dat:0 Stud Cross (Fast-Draw)
studline.dat:0 Stud Placeholder (SuperFast-Draw)

[Ben Supnik]

Hi Tim,

Right - there are around 25,000 parts using stud.dat, and around 900 sub-parts using stud.dat - too many to edit.

But there are only 50 or so actual low-res stud replacements.

So my idea is to have some kind of meta data on stud.dat itself saying "if you need lower quality and higher framerate, don't use me, use stu2.dat instead". The substitutions are made on the parts being replaced, and the 25,000 parts using stud.dat benefit automatically.

Right now to use this list I'd have to hard code it into the app, which will then be wrong if a new stud and low-quality pair are created.

As far as I can tell, stu2.dat is not actually directly used by the library.

cheers
Ben

[Philippe Hurbain]

Indeed, the substitution is hard coded in viewing software. stu2xxxx.dat is always the lo-fi version of studxxxx.dat (and AFAIK all studxxxx, at least official ones, have a lo-fi version).

[Ben Supnik]

Right - to me it seems like having the substitution be hard coded is a weakness that could be overcome with a meta-command extension.

With hard coding there is a dependency between supporting apps and changes in the library. A part author cannot create new low-detail sub-parts and have them be used without every program developer changing some kind of proprietary list, possibly in code.

The stud is the obvious example of low hanging fruit for LOD optimization, but:
- This cuts both ways - what about a high-LOD variant of studs.
- What about other parts that have high vertex count and are strong candidates for low-vertex approximation (if such parts even exist)?

So essentially what I am asking is: if we were to have meta data for low-fi variants of parts, what other meta data would we need, e.g. usage guidelines or metrics.

[Roland Melkert]

Actually hard coding won't be that bad, cause the primitives involved with mass detail don't change often as far I know.

But maybe we could use an alternative to metas by using different subfolders just like the 48 folder we could add a 'LQ' one containing primitives using the same names as their 'P' version but in lower res versions just like the 48 folder effectively holds the 'HQ' ones.

This will prevent updating files and makes cross look ups easier without adding duplicate information to all incarnations of the same primitive.

[Travis Cobbs]

It is a special case, but in the case of stud*.dat, any time you find a file of the same name, but with the d replaced by a 2, the "2" file is guaranteed to be a lower-quality version of the same file. This is a requirement of the library, as far as I know. So, there isn't a hard-code list, simply a check of: Is this a primitive with a filename that starts with "stud"? If so, is there an "stu2" version of the same primitive? If so, that's a guaranteed lower-quality drop-in replacement. (Lower quality in this case means 8-facet circle instead of 16-facet circle.)

[Michael Heidemann]

Code:

This is a requirement of the library, as far as I know.

I like to mention, that I am also of this opinion, but it is nowhere statet in our documents - and that is bad! - LSC please update the standards in regards to this item.

[Tim Gould]

It is a requirement of the part tracker. I know because I submitted a new stud primitive once and learned about this rule that way

[Ben Supnik]

Mmm....a file path convention could work as well as a meta-command I suppose.

Is it easier to add new files than to edit existing ones? I am not familiar with the organizational costs of poking at the part library.

[Travis Cobbs]

It's certainly easier to add new files than it is to get a new meta-command created, approved for use in official parts (by the LSC), and then into common usage in official parts. However, otherwise I think updating existinging files might be marginally easier.

[Chris Dee]

Actually it is only a manually administered requirement of the release process. The Parts Tracker doesn't enforce it, but I do. I agree with Mike that it should be in the standards. However, I think MLCad baulks if the stu2*.dat file is missing.