The adventures of building a web renderer


The adventures of building a web renderer
#1
This thread is for sharing my learnings and war stories from the LDraw web-rendering project buildinginstructions.js.
You can see how it evolves on BrickHub.org.

Here is a current example of how it renders a LEGO model:

[Image: 14.png]

It was not always like this. While there are at least two other web renderers that I know of, I still decided to start this project from scratch. This way I would get practical experience with the technologies involved (WebGL, Three.js, GLSL, etc.), and focus on having performance in mind from the very beginning. While the project itself hopefully ends up being of practical use for many, my goal with this thread is to share my experiences, wins and losses, and perhaps even get some good feedback to help drive the project forward.

The project started in July 2018 with the first breakthrough being in August 1. Back then I had finished an MPV of the .ldr parser while trying to adhere to the Three.js best practices for building a Loader. By modifying one of the Three.js sample files, I was able to get it to render:

[Image: p4xuzyP.png]

As you can see, there were some massive BFC issues, but that was alright for a start. The important part was to get started and get something, anything really, up and running.
My top 3 takeaways from this early stage are:

- Ignore everything that is not absolutely needed in order to get started. This includes conditional lines, quads, BFC, colors, metadata, viewport clipping, etc, etc. While it is important to do things right, the proof of concept both gave me something tangible and came with a morale boost.

- Three.js and the LDraw file format work well together from the perspective of placing things in 3D. It is obvious that James Jessiman knew what he was doing when designing the specification.

- Depending on your approach of design, BFC can be very difficult to get right. There is psudocode in the spec, but unfortunately it did not fit into the data models I had chosen. The pseudocode assumes a single pass of computing both BFC information and triangle wrapping, while my code handles the BFC computation in a separate initial step that creates reusable components.

That is all for the first post. I will try to keep this thread alive with more war stories.
Reply
RE: The adventures of building a web renderer
#2
Geometries vs Buffer Geometries in Three.js

I found it to be a good idea to build the initial POC using geometry objects in Three.js. They offer a very simple interface to get started. However. If you have read any of the "Geometry vs BufferGeometry" threads on StackOverflow, etc., then BufferGeometries should be your choice if you want to render anything but the most basic of scenes.

I used this very "heavy" model to test the limits of my code base:

[Image: tWgxL6T.png]

It was not able to render in neither Firefox nor Chrome when using "Geometry". With "BufferGeometry" it took 10 minute to render and 1.2GB of memory!

The rendering time has since them been reduced to 6.6 seconds in Firefox and 8.8 seconds in Chrome. The memory usage has seen an even more dramatic decrease to 8.5MB!

Here are some steps and realizations that lead to this performance improvement.


Reducing the Number of Geometries

The first data model which used BufferGeometries had two "geometry" object for each part: One for the lines and one for the triangles (quads are split into triangles to simplify the data model. Besides. WebGL doesn't support quad primitives anymore anyway.)

The "Blueberry" from the first post was used to compare performance. For this data model it took 103MB of memory.

[Image: 200x200_14.png]
I changed the model to have geometries on "step"-level: Each step had a line geometry and a triangle geometry for each color of elements added in the step. This change meant nothing to the rendering of building instructions, since all parts of a step were added simultaneously.

The memory was reduced to 70MB!

The overhead of geometry objects is massive! Based on this result I started looking into other ways of reducing memory usage.

Naive Indexing

Trawling google searches for other common ways to optimize Three.js-based modeling lead me to the topic of "indexing". The idea was simple. Rather than storing points of lines and triangles as triplets of 32 bit floats (x,y,z), the points would be stored in a "static" data structure with the "dynamic" index being offsets into the static structure in order to identify points. Furthermore. If two points are identical (such as when two triangles share a corner), then points could be reused.

The data model had to be changed slightly to accommodate indexing. In the previous data model I used a simple algorithm to detect when lines had common endpoints. This algorithm had to be removed to allow for indexed lines, resulting in a render time of 27 seconds and 270MB of data.

Adding the indexing (but still no sharing of points) resulted in a reduction in render time to 2 seconds, while the memory usage was reduced to 36MB! 

This came as quite of a surprise to me. I was effectively using more memory when setting up the data model because the number of points remained the same while a list of indexes was added. The reason for the improved performance can be found in how Three.js handles attributes that are sent to shaders. Optimizing shaders will be a subject for a later post. I will leave you with this for now and continue with sharing of points in the next post.
Reply
RE: The adventures of building a web renderer
#3
Not beeing a software developper there are many things that gets over my head, but it's nonetheless an enlightening reading!
Reply
RE: The adventures of building a web renderer
#5
(2018-11-07, 13:52)Philippe Hurbain Wrote: Not beeing a software developper there are many things that gets over my head, but it's nonetheless an enlightening reading!

Yeah, I realize the audience for this thread might not be as wide as what we usually see.

You and many others have already helped this project a lot by contributing models to the LDraw all-in-one installer (not to mention the LDraw parts library itself!). I have used models from it to debug the software and make it more resilient. If I only tested it on my own models, I would be making many assumptions which do not always hold.
Reply
RE: The adventures of building a web renderer
#4
Hello Lasse,

I must say I'm impressed - can I test your code in my own page? I looked at github but I see no working example nor any instructions. And your pages contain a lot of in-page code in addition to your library.

According to the renderer itself: it produces very nice results. The only problem I see is that edges are drawn by 1 pixel wide lines, disappearing completely somewhere. On the other hand, there are big positives, like transparent parts rendering which is very, very good in this renderer category - I mean the renderer with (near-to-)immediate response. And, BTW, I see thicker edge lines in your "screenshots" you post here in this thread, so it might be you know to force your renderer...
Reply
RE: The adventures of building a web renderer
#6
(2018-11-07, 17:20)Milan Vančura Wrote: Hello Lasse,

I must say I'm impressed - can I test your code in my own page? I looked at github but I see no working example nor any instructions. And your pages contain a lot of in-page code in addition to your library.

According to the renderer itself: it produces very nice results. The only problem I see is that edges are drawn by 1 pixel wide lines, disappearing completely somewhere. On the other hand, there are big positives, like transparent parts rendering which is very, very good in this renderer category - I mean the renderer with (near-to-)immediate response. And, BTW, I see thicker edge lines in your "screenshots" you post here in this thread, so it might be you know to force your renderer...

Hi Milan. Thanks a lot. You should be able to test it by running sample_view.htm in a browser. The browser probably needs security disabled so it can async load files from the local drive. I have added a guide in readme.md.

As for the edge lines, I see different browsers render them differently. All lines should have "1" pixel as width, but when lines intersect triangles, they might appear thinner.

This is how it normally looks like when lines and triangles and lines intersect:

[Image: OJK3sks.png]
Notice how the lines at the bottom of the studs o the roof are very thin due to this.

This was remedied by making custom shaders. In particular, the vertex shader for lines move points a tiny bit toward the camera - it works on most devices I have tested it on, and is the reason why the lines look so clear in the first screenshot.

Let me just link to that one again, so it is easier to compare:

[Image: 14.png]
The screenshot is made by clicking "VIEW 3D" on this page.

Edit
Simple render example added and README.md updated with guide of how to get started. The new sample is less than 100 lines, so I hope it is easy to get started with it.
Reply
RE: The adventures of building a web renderer
#10
(2018-11-07, 22:54)Lasse Deleuran Wrote: The screenshot is made by clicking "VIEW 3D" on this page.
This is strange, I cannot achieve the same look in my browser, neither Firefox nor chromium. Edge lines in your screenshot are thicker and antialiased. In my browser, they are exactly 1px wide with no antialias. Sometimes it's hard to even understand what they mean, when two edges are too near. See the green person's right arm (the Tan hinge plate).
Edit: You need to click on the image to see it in the original size with no antialiasing made by browser on ldraw.org page.
   
(2018-11-07, 22:54)Lasse Deleuran Wrote: Edit
Simple render example added and README.md updated with guide of how to get started. The new sample is less than 100 lines, so I hope it is easy to get started with it.
Thanks a lot, I put this on my TODO list. Currently, I'm busy with an exhibition model preparation...
Reply
RE: The adventures of building a web renderer
#11
(2018-11-13, 16:20)Milan Vančura Wrote:
(2018-11-07, 22:54)Lasse Deleuran Wrote: The screenshot is made by clicking "VIEW 3D" on this page.
This is strange, I cannot achieve the same look in my browser, neither Firefox nor chromium. Edge lines in your screenshot are thicker and antialiased. In my browser, they are exactly 1px wide with no antialias. Sometimes it's hard to even understand what they mean, when two edges are too near. See the green person's right arm (the Tan hinge plate).
Edit: You need to click on the image to see it in the original size with no antialiasing made by browser on ldraw.org page.

(2018-11-07, 22:54)Lasse Deleuran Wrote: Edit
Simple render example added and README.md updated with guide of how to get started. The new sample is less than 100 lines, so I hope it is easy to get started with it.
Thanks a lot, I put this on my TODO list. Currently, I'm busy with an exhibition model preparation...

Thanks for the screenshot. I have been able to recreate it on one of my devices. Anti-aliasing is actually enabled - even in your screenshot. The sampling rate has just bottomed out because of how canvas size vs. css size and physical device pixel ratios can differ. I will try to fix the renderer. It seems to work fine when viewing building instructions - it is only the preview that currently is messy on some devices.

Update on Nov 19, 2018. I have now fixed the issue on my own device. It was caused by improper handling of canvas size vs canvas element size vs size of parent of canvas vs device pixel ratio. It took a lot of tries to get right!
Reply
RE: The adventures of building a web renderer
#7
Merging points efficiently

From my post regarding indexing, you could see how using 'indexes' could help reduce the amount of points.

As an example. Consider a 3D box. I has 8 corners. All lines and triangles use these 8 corners, but a box is constructed by 12 lines and 12 triangles. Each line has 2 points and each triangle has 3. With each point taking 3 numbers, the amount of numbers stored to show a box is:

(12*2 + 12*3)*3 = 180 numbers.

If we store the 8 corner points separately (8*3 = 24 numbers) and simply store offsets/indices, the "*3" from the previous equation can be removed, resulting in:

24 + (12*2 + 12*3) = 84 numbers.

Parts in the LDraw library (especially standard parts) have a lot of common points, so it makes sense to use this trick to save memory, and thereby also rendering time. In our example above we save roughly 50%, so let us take a look at how much we can save in our test model.

I would also like to introduce you to an additional test model. This is the very first LDraw model I ever built. It is quite big (3500+ parts) and is good for stress testing:

[Image: 112.png]


Here are the baseline numbers for just showing triangles and not using our trick to combine points. I call the two models 'Psych' (the blue car) and 'Executor':

Psych: Memory usage: 36.3MB. Rendering time: 1.039ms. Number of points: 375.432.
Executor: Memory usage: 862MB. Rendering time: 1.8185ms. Number of points: 11.333.253.

This is what happens when you combine points for the full models:

Psych: Memory usage: 16.6MBRendering time: 3.121ms. Number of points: 99.687.

Executor: Memory usage: 313MBRendering time: 99.495ms. Number of points: 2.700.145.


That rendering time is completely unacceptable. Here is what happens when points are only combined for the individual parts (not the full mode:

Psych: Memory usage: 20.5MBRendering time: 1.584ms. Number of points: 100.339.

Executor: Memory usage: 414MBRendering time: 17.096ms. Number of points: 2.751.714.



These tradeoffs are much more acceptable. Next up was adding normal lines to the mix.
Reply
RE: The adventures of building a web renderer
#8
(2018-11-09, 11:44)Lasse Deleuran Wrote: Psych: Memory usage: 36.3MB. Rendering time: 1.039ms. Number of points: 375.432.
Executor: Memory usage: 862MB. Rendering time: 1.8185ms. Number of points: 11.333.253.

This is what happens when you combine points for the full models:

Psych: Memory usage: 16.6MBRendering time: 3.121ms. Number of points: 99.687.

Executor: Memory usage: 313MBRendering time: 99.495ms. Number of points: 2.700.145.


That rendering time is completely unacceptable. Here is what happens when points are only combined for the individual parts (not the full mode:

I don't understand how can it become slower, or are you counting the preparations too?

In LDCad each part gets prepared for rendering separability and the result is stuffed in VBO.
Also finding the unique points is not only useful for indexed meshes but also very helpful during smoothing.
Reply
RE: The adventures of building a web renderer
#9
(2018-11-09, 19:38)Roland Melkert Wrote:
(2018-11-09, 11:44)Lasse Deleuran Wrote: Psych: Memory usage: 36.3MB. Rendering time: 1.039ms. Number of points: 375.432.
Executor: Memory usage: 862MB. Rendering time: 1.8185ms. Number of points: 11.333.253.

This is what happens when you combine points for the full models:

Psych: Memory usage: 16.6MBRendering time: 3.121ms. Number of points: 99.687.

Executor: Memory usage: 313MBRendering time: 99.495ms. Number of points: 2.700.145.


That rendering time is completely unacceptable. Here is what happens when points are only combined for the individual parts (not the full mode:

I don't understand how can it become slower, or are you counting the preparations too?

In LDCad each part gets prepared for rendering separability and the result is stuffed in VBO.
Also finding the unique points is not only useful for indexed meshes but also very helpful during smoothing.

Yes. I am counting the full time to sort all points of the model. Sorting 11mio. points takes forever in the browser, but I had to see it in practice in order to rule out the approach.

Three.js is putting an abstraction layer above what I actually have as individual VBO's. I am planning on reading up on this and try to take advantage of it, rather than allowing it to be some black box. I can also see that BrickSmith has had huge performance boosts by using parts being VBO's as you mention, so the rendering can simply be "draw this VBO/part here, there and there". If I can figure out how to do this as well, then I might get a similar big performance benefit.
Reply
RE: The adventures of building a web renderer
#14
Bricksmith doesn't just put each part in a VBO - it also builds (on the fly per render) an instance VBO - that is, a VBO full of transform data and color - for each part (e.g. a 2x4 brick), the VBO is drawn once* with an instance buffer describing where and what color each use of that part is.  The entire instance buffer is built once and sent to GPU memory, then each part is drawn once using part of the instance buffer.  This gives Bricksmith both minimal draw calls (one draw call per change of part) and minimal per-render GPU memory overhead (because we write all of the instance data into one big buffer).

The one exception is translucent parts, which are drawn later in Z order from far to near, even if this means changing VBOs per part.
Reply
RE: The adventures of building a web renderer
#12
The results from my previous post (Merging points efficiently) were only for rendering triangles. I started out by just focusing on getting triangles right because it wasn't a cake walk. Here is the result of my first attempt at merging points:

[Image: exeWsqW.png]


The issues were fixed and it was time to move on to

Also make the lines indexed

Adding non-indexed lines meant slightly different baselines. Here are the results from rendering with non-indexed lines and non-indexed triangles:

Psych: Memory usage: 36.0MB. Rendering time: 1.961ms.

Executor: Memory usage: 1.015MB. Rendering time: 32.913ms.

By using indexes the results were:

Psych: Memory usage: 22.0MB. Rendering time: 2.381ms.

Executor: Memory usage: 457MB. Rendering time: 27.040ms.

I believe the massive reduction in space usage for the big model offsets the poor results for the small one. Note how we still get an improvement in rendering (and setup) time for the large model. This is for the same reason as pointed out previously.

That was enough of not addressing the elephant in the room. In the next post I will start discussing conditional/optional lines.
Reply
RE: The adventures of building a web renderer
#13
(2018-11-22, 17:00)Lasse Deleuran Wrote: The results from my previous post (Merging points efficiently) were only for rendering triangles. I started out by just focusing on getting triangles right because it wasn't a cake walk. Here is the result of my first attempt at merging points:

[Image: exeWsqW.png]

Don't fix it! Start rendering your models this way for the next 10 years ... meanwhile twitter a render every day from a fake account ... don't reveal your identity ... organize an exhibition (don't forget the champagne). By 2028 Sothebys or Christie's will auction them for a million :-)

w.
LEGO ergo sum
Reply
RE: The adventures of building a web renderer
#15
There was a helpful post in this thread from someone who had tried the website. Unfortunately I can't see the post anymore, but here are the main areas of improvement as I remember them:
  • Size of PLI's can be too big.
  • Parts, such as cables on motors, do not render correctly
  • I'm sure there was a third point...
I think the post was by the one who was unlucky and uploaded while I was pushing a major update to the site... which broke the "take a snapshot" functionality for a day!

In any case. Thank you very much for testing the code! All your points seemed completely valid when I read them:
  • The size of PLI's was recently changed so they attempt to fill as much as possible while allowing the model to take up at least 55% of screen space. I must add some additional limits so that we don't see a single 1x1 plate being blown up to massive proportions.
  • It is not just cables. It is all kinds of assembled parts which are causing me major headaches. Minifig legs and torsos give similar issues. It has been on my TODO-list for a while because it is not easy to create automation for "merging" these assembled parts into single parts to be shown in PLI's. Right now you can simply have 'pants.dat' submodels in the LDraw file to force the PLI to show assembled pants, but I can't expect users to do this, and it will not work for all the files that people have already made. This needs more time in the thinking box.
Reply
RE: The adventures of building a web renderer
#16
Conditional Lines

[Image: 123.png]

From a technical perspective, 'conditional lines', or 'optional lines' seem to cause the most headache. The concept is rather simple: Optional lines highlight the outline of parts when the standard lines do not suffice. My go-to example is a stud:

[Image: 233.png]

The line on the right side show one of the two conditional lines which are currently visible in order to highlight the cylindrical section of the stud.

Try it for yourself by going to this page where the cylindrical part of a stud is the subject (And BFC mode is enabled).

Click on one of the 'Optional' icons in order to highlight a particular line and see how it only shows when the blue and purple dot are on the same side of the line (it will appear between the green and orange dot)

Naive implementation

My first shot at conditional lines was on October 7 and in each draw call evaluate all the conditional lines.

This is obviously going not going to perform, but it is a good start.

The math behind wether a conditional line should be shown is this primitive. Consider a line from 'lineStart' to 'lineEnd'. A point 'p' is on the left side of the line if the following is negative:

(lineEnd.x-lineStart.x)*(p.y-lineStart.y) - (lineEnd.y-lineStart.y)*(p.x-lineStart.x)

This function is basic matrix algebra 101, and it is based on screen coordinates, that is, how the 'camera' is seeing things. The following method from the Three.js 3D library can be used to get a point 'p' from 3D to screen coordinates:

p.project(camera)

The performance results are predictably rather dire since the function has to be computed for each of the conditional lines:

Psych
- Memory usage: 324MB
- Rendering time 12s
- Conditional lines to evaluate: 33.650

Executor
- Rendering crashes
- Conditional lines to evaluate: 1.181.960


Conditional Line Evaluator

The naive implementation needs to be drastically improved. One idea for improving performance is to do less work for the same results. Consider the standard LDraw 1x2 plate (shown here using the 'harlequin mode' on the parts page):

[Image: 241.png]

It has 3 cylinders: Two for the studs and one for the underside pin. Each cylinder has 16 sides, and thus 16 conditional lines.
The two studs on top are oriented the same way, so whenever a conditional line shows on one of them, the same conditional line will show on the other. The conditional lines of the first stud can thus be used as representatives for both. This is the idea behind the 'conditional line evaluator': You only have to compute the lines for the representatives and copy the results to all other. For the 32 conditional lines of the two studs, we thus only have to run the function for the 16 of them.

But we can do better. Whenever a conditional line is shown, the line on the opposite side should be shown as well. They should have the same representative. We can obtain this by the observation that instead of looking at lines, we can see them as vectors, and vectors to the two 'conditional points' can be reversed without changing the outcome. The vectors are said to be 'normalized' by giving them a preferred direction. There are also some technical details with the ordering of these vectors, but I will spare you the gritty details.

Instead we should take a look at the underside pin.

[Image: 240.png]

The angles involved are the same as for the studs - only the distances are different. Recall that the function is only interested in the fact that points lie on certain sides of lines - not how far from the line. We can thus further normalize the vectors by changing them to unit vectors, and do so for the lines as well. By doing this we reduce the 48 conditional lines of the 1x2 plate to 8 representative conditional lines that need to be handled in each draw call.

The results are now:

Psych
- Memory usage: 167MB
- Rendering time 7.789ms
- Conditional lines to evaluate: 8.011
Executor
- Still crashing
- Conditional lines to evaluate: 144.024

These are not the results I was hoping for. Luckily I found a way to tweak the 'window' of the sweep line algorithm that searches for representatives to obtain a better tradeoff between performance and matches. By changing this and reintroducing indexing (see the previous post), the results were improved to:

Psych
- Memory usage: 86.3MB
- Rendering time 3.795ms
- Conditional lines to evaluate: 8.829
Executor
- Memory usage: 1.219MB
- Rendering time 58.693ms
- Conditional lines 61.401

A small sacrifice in the number of conditional lines to evaluate for the small model was worth the ability to render the large one.

This was with the code changes of October 14.

In the next post I will explain how to delete all of the 7 days of work lying behind this post and obtain even better results.
Reply
RE: The adventures of building a web renderer
#17
I promised to delete those 7 days of work with conditional lines. I that code I reduced the 1.181.960 conditional lines to 61.401 to be evaluated in each draw call. How about going the other way and evaluate 1.363.920 in each call?

That is essentially what happened when I moved this code to:

Custom Shaders

The idea is to perform the costly calculations on the GPU instead of the CPU. The control points (and opposite line point) are pushed to the GPU and the calculation is performed for each of the two end points of each conditional line (hence the doubling of the calculations).

The technical details behind this is to write 'RawMaterials' which use custom WebGL shaders written in the shader language GLSL.

Moving the code was not pain free:

[Image: 235.png]

But after fixing the initial rendering problems I was able to get it to work. The main piece of code is in the vertex shader where the alpha component in the color of the conditional line is used to determine if the line should be shown or not:

     vColor.a *= sign(dot(d12, d13)*dot(d12, d14));

Here 'd12' is the vector difference between points 1 and 2 for the conditional line, 'd13' is between points 1 and 3, and so forth. The dot-operator computes the dot product of two vectors and the sign-operator returns '1', '0' or '-1' depending on the product. 

The 'fragment shader' can now discard conditional lines that should not be shown:


     if(vColor.a <= 0.001)
         discard;
     gl_FragColor = vColor;


The results on the test models are:

Psych
- Memory usage: 9.2MB
- Rendering time: 2.519ms


Executor
- Memory usage: 15.2MB
- Rendering time: 47.794ms
Reply
RE: The adventures of building a web renderer
#18
very nice!
Can you do something about the missing portions in the above render?
To me it looks like this trouble is simply caused by wrong winding / BFC orientation of surfaces,
so that the OpenGL renderer discards them.
Do you correctly parse the "0 BFC CERTIFY CW" vs "0 BFC CERTIFY CCW" statements?
Reply
RE: The adventures of building a web renderer
#19
(2019-01-04, 8:24)Steffen Wrote: very nice!
Can you do something about the missing portions in the above render?
To me it looks like this trouble is simply caused by wrong winding / BFC orientation of surfaces,
so that the OpenGL renderer discards them.
Do you correctly parse the "0 BFC CERTIFY CW" vs "0 BFC CERTIFY CCW" statements?

You are absolutely right in the source of the error being regarding BFC. The error you see in the screenshot is due to rotation matrices inverting the winding. The solution is to invert winding whenever the determinant of the rotation matrix is inverted. This is a problem other LDraw renderer authors have stumbled into before me, so it was easy to detect and fix.

Another good source of improvements is BrickSmith where there are some good tips and tricks from the author on the net. One of these tips is regarding drawing transparent polygons after drawing the solid ones.

This is how it looks when drawing transparent first:

[Image: 32.png]

And this is when drawing the transparent last:

[Image: 245.png]

I think the next area of interest should be for VBO's, since BrickSmith sees a big benefit using them. Hopefully my next post will be with findings of VBO's and Three.js.

Edit. I almost forgot. Moving the transparent triangles to be rendered last wasn't pain free either!

There was some art to be found in the intermediary codebase:

[Image: 236.png]
Reply
RE: The adventures of building a web renderer
#20
I have implemented the suggestion by Roland Melkert with VBO's as he wrote above (draw this VBO here, there and there) in order to see if there would be any benefits when doing this with three.js. 

The initial results were some really hairy models:

[Image: JcIPdqs.png]
Joke aside (although that was actually the result after the first code rewrite). To use VBO's with three.js boils down to reusing 'Mesh' objects. I have decided to build one mesh for each part in color '16. A model using a certain part with different colors will thus only use (and reuse) a single VBO. The color handling is performed in custom shaders.

If you remember some of my first posts in this thread, you might think "This sounds familiar... isn't this what you did before bringing down the space usage and improving the render time?" and you would be right.

So what has changed? 

Well. Pretty much the whole code base. By using the tricks from all the other posts (such as reusing points and using custom shaders), the memory usage is being kept under control. Performance is similarly improved by the following two improvements:

Bottom-up Constructions of Parts

I am now building the parts "bottom-up" in order to improve reusability of points. Previously a part, such as 3001 would be built like this:

Build 3001.dat by first building all line types 2, 3, 4 and 5. Then built each primitive (line type 1), such as stud.dat the same way.
Finally sort all the points collected for 3001.dat in order to reuse those that overlap.

Now parts are built like this:

First built all primitives without any inner primitives (such as 4-4edge.dat, which only consists of 16 normal lines). Sort the points of the primitives immediately.
Then built all primitives that only depend on the primitives that have been built. The effort used by sorting is now reduced since the other primitives already have their points sorted.
Continue until all parts are built.

The improvements with this method of building comes from having to sort less. There are also fewer points to sort each time anything needs to be sorted, which leads to better detection of overlapping points.


Client Storage

The second big improvement does absolutely nothing for performance... unless you have IndexedDB enabled in the browser. Parts are being stored in the IndexedDB of the client, which allows for much quicker rebuilding of parts. Retrieving parts from IndexedDB takes less than 2ms for all models I have tested with. This technology didn't work for me right away:

[Image: l3dBWfV.png]

Performance Improvements

The following two models are added to the test suite for variety:

UCS MF (10179) with 5163 parts

[Image: 201.png]
and this MAN TGS Cement Truck with 1523 parts

[Image: 111.png]

The results for performance are split up in two times. The first is for building parts and storing them in IndexedDB. This number is less than 2ms for repeated visits, but is encountered at the first visit and for everyone who does not use IndexedDB (such as Safari in Incognito mode):

Psych
- Memory usage: 8.8MB -> 9.7MB
- Rendering time: 3.325ms -> 1.270ms + 1.730ms = 3.000ms
MAN Cement Truck
- Memory usage: 20.2MB -> 18.5MB
- Rendering time: 12.090ms -> 4.619ms + 4.432ms = 9.051ms
Executor
- Memory usage: 16.4MB -> 27.5MB
- Rendering time: 44.922ms -> 4.008ms + 4.024ms = 8.032ms
UCS MF (10179)
- Memory usage: 20.5MB -> 37.8MB
- Rendering time: 134.709ms -> 4.561ms + 5.214ms = 9.775ms

This is a great success for rendering times and only a moderate decrement to space usage. Remember that these performance measures are from my now 10 year old mid range Sony Vaio laptop. A modern phone is quicker than this!
Reply
RE: The adventures of building a web renderer
#21
Improving load time for building instructions

The previous posts have all focused on rendering full models. The user experience for browsing building instructions should also be nice. As an example, opening the building instructions on the first page should display the image and BOM for the step with little to no delay.

As an example. Here is how BrickHub.org today displays the first step of the mod of 5580 With the contrast set to 'high' in settings, it is very similar to how LEGO originally displayed the instructions back in 1990 (or was it 1986 in some markets?)

[Image: vaeJzwP.png]

Unfortunately the construction of bottom-up geometries causes all parts of the model to be built in the browser before the first step is displayed. Yesterday evening I changed that to only include the parts that are necessary for the construction step that is displayed.

The rendering time for the first step has improved as follows:

Psych
- Cold cache: 2900ms -> 1500ms
- Warm cache: 1700ms -> 1500ms
MAN Cement Truck
- Cold cache: 9500ms -> 3300ms
- Warm cache: 3400ms -> 2900ms
Executor
- Cold cache: 6800ms -> 2700ms
- Warm cache: 3000ms -> 2500ms
UCS MF (10179)
- Cold cache: 7900ms -> 3600ms
- Warm cache: 4300ms -> 3000ms

Here 'cold cache' refers to the very first time the page is loaded into the browser (no cached parts in the browser storage), while 'warm cache' has the parts already stored.

The loading times for 'cold cache' are improved as expected. That the 'warm cache' numbers are also improved is due to the parts not all being fetched for this first step. I mentioned earlier that this process should at most take 2ms in total, which these numbers contradict. However. That was just for retrieving the parts for storage. Additional code is being run to prepare those parts for being used in instructions, hence the larger performance improvement observed here.
Reply
« Next Oldest | Next Newest »



Forum Jump:


Users browsing this thread: 1 Guest(s)
Forum Jump:


Users browsing this thread: 1 Guest(s)