Walnut integration

[bluelightning32]

Jscad works great for simple models. However, currently if one creates too complicated of a model, it exposes one of the geometry rounding errors in Jscad, such as #451. It is extremely frustrating to investigate such issues, and it is extremely difficult to fix them.

I was motivated by the experience to create a new 3d boolean operation library using exact arithmetic: https://github.com/bluelightning32/walnut.

• The library has great unit test coverage.
• The documentation is better than other libraries.
• It uses the same MIT as Jscad.
• Its only dependencies (VTK and Gtest) are optional.

hrg@ and I built a working prototype to show how Walnut could be integrated into Jscad: https://github.com/bluelightning32/walnut-javascript. Walnut is written in C++, so the prototype uses WebAssembly to call it from Javascript. 91% of current browsers support WebAssembly.

My primary focus was on making Walnut accurate and robust. However, the performance ended up pretty good too. The prototype tested intersecting two spheres together. These were the results from Firefox on my computer when the spheres had 70 segments:

• Walnut: 0.67 seconds
• Jscad: 6.2 seconds

And these were the results when the spheres had 99 segments:

• Walnut: 1.1 seconds
• Jscad: 21.6 seconds

Even Walnut has extensive unit tests, some integration tests in VTK, and the jscad integration prototype, the Walnut code has not been hardened through many user models like Jscad has. So I would prefer for Walnut to be officially supported as an alternate backend until it is proven stable enough to fully replace the Javascript backend. I would like the backend to be selectable at runtime.

I would prefer to keep Walnut in a separate repository from Jscad. Keeping the repositories separate helps build good component layering. However, if you choose to integrate Walnut into Jscad, I will give collaborator access to the Walnut repository to any Jscad developers that are interested. Or we can host the main Walnut repository under the jscad account, as long as I still have access.

Why did I write Walnut in C++ instead of Javascript? The main reason is that I'm more familiar with C++. Also, given the complexity of the algorithm, I found the static typing to be helpful for catching bugs when I refactored APIs.

Can Walnut be ported to C++? I documented the algorithm in case someone is really motivated to port it. However, a port would be time consuming, because the code is long and very nuanced. As long as the unit tests are ported with the algorithm, they would catch most translation errors, but debugging the unit test failures is difficult.

The larger issue is that the Walnut performance would likely be much worse if it were translated to Javascript. Internally it uses variable length integers in order to do exact arithmetic. Those variable length integers are implemented as arrays of unsigned 64 bit integers. It also uses unsigned 128 bit integers for some operations if available on the target platform. Unfortunately, that does not translate well to Javascript. Only up to a 48 bit integer can be emulated with a Javascript floating point number. In the C++ code, when the variable length integer is under 64 bits, the value is stored inline instead of as a separate array. I worry that 48 bits would not be enough to inline the values a sufficient percentage of the time, which would cause worse performance.

Why did I create a new algorithm instead of using an existing open source library? I could not find an existing library that was well documented, robust, with a permissive license. CGAL is robust but has a GPL-3 license. Libigl claims to be LGPLv3 if Cork is used, but really it still depends on CGAL.

Why did I create a new algorithm instead of implementing something from a research paper? I found the research papers to be confusing. They do not explain the algorithms well enough. Furthermore, when the author actually publishes the source code, the boolean operation algorithm often ends up depending on parts from CGAL, such as Delaunay triangulation, such that it is difficult to implement the algorithm entirely from scratch.

[hrgdavor]

the prototype was easy to make in V2 since booleans are standalone functions, and it was just a matter of declaring substitute functions before the main. I am in favor of this integration, and my question is for @z3dev what would be the best approach.

[z3dev]

WOW! All these cool side projects happening around JSCAD. Exciting times!

@bluelightning32 thanks for the very long and very informative introduction to Walnut. it must have been a challenging library given the nature of research papers, and various half-cooked implementations.

i think that you made the correct choice to base the library on very long integers. that will keep the precision high and eliminate a lot of doubts. i'm not sure how you managed the math yet, but took a quick look at the code. (FYI, someday... JavaScript will have support for proper 64 bit integers. when that happens, JSCAD will re-implement for the same reasons.)

as far as integration, i totally agree with keeping Walnut separate today. it will allow you do improve Walnut without getting pulled into Javascript issues and this larger project. It would be cool if the JSCAD runtime could determine if Walnut was installed, and use it. If not then maybe we need a 'shim' to perform the magic.

I was thinking that a first step might be easier as part of NODE, integrating with the CLI of JSCAD. But you can decided.

[bluelightning32]

Per hrg@'s suggestion, I published walnut as an npm.

Please take a look at my progress so far on integrating it with JSCAD and offer any suggestions:
bluelightning32@88b4cba

JSCAD is using browserify to pack all of the js files together into a single file. However, that doesn't work with wasm, because the wasm is a separate binary file (not javascript). I tried wasmify but that just base64 encodes the wasm file and sticks it in the javascript, which increases the size.

The best solution I could come up with is to have the web package's postinstall script copy the wasm file to the dist directory (and add similar postinstall scripts to any other packages that need walnut). Then the locateFile function can be overridden to point to the wasm file in the dist directory.

I copied a lot of hrg@'s code from the prototype. I can tell the Walnut is getting run and generating output, but JSCAD isn't rendering it. I'm guessing the special 'mesh' type geometry isn't supported by jscad.

filter result 1 
Object { indices: Uint16Array(4464), vertices: Float32Array(4464), type: "mesh", color: (4) […], transforms: (16) […] }
color: Array(4) [ 1, 0, 0, … ]
indices: Uint16Array(4464) [ 0, 1, 2, … ]
transforms: Array(16) [ 1, 0, 0, … ]
type: "mesh"
vertices: Float32Array(4464) [ -5.125, -0.98046875, -0.1806640625, … ]
<prototype>: Object { … }

[hrgdavor]

I copied a lot of hrg@'s code from the prototype. I can tell the Walnut is getting run and generating output, but JSCAD isn't rendering it. I'm guessing the special 'mesh' type geometry isn't supported by jscad.

the reason is that the specific code there was producing intermediate data for then conversion to threejs renderer, and not data compatible with jscad modeling.

[bluelightning32]

Intersecting two jscad polygons using Walnut works on my fork now. It's still hacky because it's hard coded for intersecting exactly 2 polygons.

bluelightning32@daab77c

[bluelightning32]

Intersection, union, and subtraction are working through walnut now in the web version. I need feedback on whether I'm integrating the wasm correctly.

It appears that the web worker is restarted every time the script is changed, and that's forcing it to reload the wasm each time. However, I timed it, and loading the wasm only takes 100ms on Firefox on my computer once the binary is cached.

This message is showing up in the console:

total time for design regeneration 3058 36

However, I added some temporary log lines around the Walnut functions, and they only contributed 685ms to the total time.

[z3dev]

@bluelightning32 cool.

that's correct. The web-workers are created each time the evaluation is required, however I don't think this is required.

I just submitted a new PR to improve error handling, which catches all errors and sends a message to the main thread. This will probably allow the web-worker to persist.

maybe @hrgdavor can assist here.

[hrgdavor]

Yes, it is unfortunate that web worker is recreated each time. I did try to fix that some time ago, but navigating what happens in the code that uses the 'most' library where everything is streamed proved too much for my brain (does not compute :D).

Little free time I have, I am focusing o n the the new prototype, and I just find most library too frustrating to deal with 😢.
in the prototype worker is reused, so even the time to load wasm will happen only once.

[bluelightning32]

I realized that since the jscad scripts are already directly importing the boolean operations, I can change it so that its up to the jscad script to either import the jscad or walnut boolean operations, similar to what @hrgdavor's demo was doing. This has a few benefits:

1. The script developer can choose which implementation to use.
2. There are fewer changes to the rest of jscad
3. Scripts that are not using walnut don't have to wait for it to load.
4. There is minimal chance of breaking existing jscad scripts.

Here's an example of using it:

/**
 * Basic Booleans Demonstration
 * @category Manipulating Shapes
 * @skillLevel 2
 * @description Demonstrating the basics of boolean shape combinations
 * @tags cube, sphere, union, subtract, difference, subtraction, intersect, intersection
 * @authors Simon Clark
 * @licence MIT License
 */

const jscad = require('@jscad/modeling')
const walnut = jscad.booleans.walnut
const { cube, sphere } = jscad.primitives
const { translate } = jscad.transforms
const { colorize } = jscad.colors
const { union, subtract, intersect } = walnut

const main = async () => {
  await walnut.init()
  const aCube = colorize([1, 0, 0], translate([-4.5, 0, 0], cube()))
  const aSphere = colorize([0, 1, 0], translate([-5.2, -0.8, 0.8], sphere({ segments: 32 })))

  const aUnion = union(aCube, aSphere)
  const aSubtract = subtract(aCube, aSphere)
  const aIntersection = intersect(aCube, aSphere)
  return [
    aCube,
    aSphere,
    translate([3, 0, 0], aUnion),
    translate([6, 0, 0], aSubtract),
    translate([9, 0, 0], aIntersection)
  ]
}

module.exports = { main }

Please take a look at bluelightning32@1386226.

Does anyone have any major design concerns? If not, should I start a PR?

[hrgdavor]

I was curious if changes made will work when main is not async or a Promise, but from some simple tests I made await is smart enough to handle both cases when function is "normal" or async.

The changes you are making are welcome, if there are no major sideffects on existing code. This would allow more freedom for jscad script in general, as some users were asking for ability to fetch data for the script based on a parameter.