The adventures of building a web renderer

[Lasse Deleuran]

Conditional Lines



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:



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):



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.



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.