Asking about multiple boolean operations

23 views
Skip to first unread message

Xiaoyue Wang

unread,
Oct 26, 2020, 12:35:18 PM10/26/20
to cu...@googlegroups.com
Hi developers,

I am trying to use curv to union multiple objects together. But they have no pattern so that I cannot use the repeat operation to speed up the process. I found that the time for union n objects is exploding when n increases. For example, if I have 8 struts, it uses several seconds, but if I have 100, if never runs out the results.

Is there any attempt before by anyone to solve this problem? Or do you have some suggestions on which piece of code on the bottom layer should I look into?

BTW, the objects I am doing union with are not all intersecting with each other. So is it possible that I just deal with them region by region?

Sincerely
Serena
.

Doug Moen

unread,
Oct 26, 2020, 1:14:55 PM10/26/20
to Curv
This is a general problem with Curv right now.

You could try rendering directly to an OBJ file, then viewing the mesh using meshlab or some other mesh viewer. That will probably work with your existing code. If you are comfortable with sharing your code, then I can have a look and maybe make suggestions for speeding it up.

Doug Moen.
--
You received this message because you are subscribed to the Google Groups "Curv" group.
To unsubscribe from this group and stop receiving emails from it, send an email to curv+uns...@googlegroups.com.

Xiaoyue Wang

unread,
Oct 26, 2020, 2:34:22 PM10/26/20
to Doug Moen, Curv
Maybe I can add some contributions, if you don’t have enough time but have ideas on that?

Doug Moen

unread,
Oct 26, 2020, 3:45:58 PM10/26/20
to Curv
As you've already discovered, I call this the "large union" problem. It needs to be solved before a "Curv 1.0" release. I have many ideas about how to fix this.

A GUI with a Mesh Viewer
Create a GUI for Curv, similar to OpenSCAD. There are 3 panes: a text editor, a console, and graphics viewer. Similar to OpenSCAD, there are two ways to view a shape: using the current viewer, based on sphere tracing (Shadertoy technology), and by converting the shape to a mesh and displaying the mesh. Shapes that currently can't be viewed using the Sphere Tracer, either because they contain large unions, or because the distance function is not Lipschitz(1), can still be viewed using the Mesh Viewer.

I had planned to build the GUI using ImGUI plus Zep for the text editor (https://github.com/Rezonality/zep)

Render to a Voxel Grid
The video game "Dreams" by MacroMedia uses a signed distance field representation. The way they solve the "large union" problem is by rendering the functional representation of a signed distance field to a voxel grid, then displaying the voxel grid. I was planning to add a "voxelize" function that converts a shape to a voxel representation.

Note that Curv currently uses OpenGL 3.2, and Dreams uses a more advanced GPU API that supports compute shaders. They use a pipeline of compute shaders in their implementation. I have been planning to migrate Curv from OpenGL 3.2 to WebGPU (using Google's Dawn library). This gives me compute shaders, in a portable API that runs on MacOS and in web browsers. I don't actually know if compute shaders are a *requirement* for voxel grid rendering, but I had been planning to migrate to WebGPU before implementing voxel grid rendering.

Faster Rendering of Large Unions
This paper describes some ideas for making the bracelet distance function run faster:

One idea is the `linear_union` function. There are probably several ways to implement it. Some changes to the compiler are likely required. I haven't thought deeply about this yet.

Another idea is to use a BVH (Bounding Volume Hierarchy) to speed up sphere tracing of a large union. This is similar the BVH data structure used for ray tracing.Again, I'm skipping a lot of details.

Doug Moen.

Xiaoyue Wang

unread,
Oct 28, 2020, 11:01:21 AM10/28/20
to Doug Moen, Curv
Thank you so much for the reply, with abundant information, very helpful!
For the "Faster Rendering" approach, I find that the hardest core is about the coloring function. Is it possible that we just cancel calculating that part? 1) Is it possible to render without color but only the dist function?
2) For exporting STL, there is no color needed. I tried to export STL directly on large union samples, but it still runs very slow. Is this the same / similar to what you said about "A GUI with a Mesh Viewer"?

Also I would like to ask, do you have any schedule about when to release "Curv 1.0"? Or do you have any guess about the releasing time?

XIaoyue (Serena) Wang

To view this discussion on the web, visit https://groups.google.com/d/msgid/curv/0e1b7e49-dac1-44b6-9bcb-2b38b03a2c60%40www.fastmail.com.

Doug Moen

unread,
Oct 28, 2020, 3:11:16 PM10/28/20
to Xiaoyue Wang, Curv
Curv is a hobby project and a research project, so there is no schedule.

The "bracelet" model renders okay on my machine with 20 links, but at 100 links, it compiles into 700,000 lines of GLSL or C++, which is too much. Most of that code is in the colour function, which is stupid, because with a better code generator and an optimizing compiler, the colour function should be 1 line of code. So the compiler needs work. To work around the problem with the colour function, I have added
   >> colour red
to the bottom of the "bracelet" source file. At 100 links, it still won't render to a graphics window, because there is still 13,500 lines of GLSL, which is too much, but now I can export the bracelet to a mesh in a couple of seconds.

The existing implementation of 'union' inline expands the code for every object being unioned together, so the amount of code generated for the bracelet grows with the number of links, which is no good for large unions. When combined with a stupid code generator and a weak optimizer, this results in way too much code.

The idea behind the "linear_union" operator is to generate a small, fixed amount of code regardless of the number of links in the bracelet. Instead of inline expanding the code for each link, we generate a "for" loop that iterates N times (N is the number of links). I know how to implement "linear_union" in Curv, but due to another compiler limitation, that Curv code won't compile into GLSL or C++. It would be possible to implement "linear_union" directly in C++, but I would rather fix the compiler limitations.

The linear_union proposal fixes the problem of too much code being generated, but the code is still slow, because the time complexity of the distance function is O(N), where N is the number of links in the bracelet. bracelet(100) probably works, but bracelet(1000) is probably too slow. To speed this up further, we want to reduce the time complexity to O(log N) or even O(1).

The bracelet is symmetrical enough so that it could be programming using the "repeat_radial" function, and then the distance function would be O(1). That avoids the "large union" problem by using a different coding technique. I have considered creating a "Symmetry" library that would be effectively a DSL for describing a wide range of mathematical symmetries -- this is an extension of the "repeat" operators. This would allow complex symmetrical shapes to be constructed without using large unions. A well designed Symmetry library could open up new vistas for procedural generation of geometric shapes. Maybe your "struts" model has symmetries that could be leveraged to create an efficient distance function.

One general technique for speeding up the distance function of a large union is to use the approach used by ray tracers, and build an "acceleration structure". For the bracelet, this would mean putting each link into one node of a "bounding volume hierarchy" (BVH), which is a tree structure. Then, you walk this tree structure during sphere tracing or mesh generation, and the time complexity goes down to O(log N). Another approach, applicable to GPU rendering, is "tile based rendering".

There are other open source projects using these techniques, which I can borrow ideas and code from, but they generally rely on the use of compute shaders. Curv is limited right now because it uses OpenGL, and it runs on MacOS, and OpenGL on MacOS doesn't support compute shaders, because Apple wants developers to use Metal instead. OpenGL is dying, so I plan to transition to WebGPU, which is a high level and easy to use, but also higher performance than OpenGL and runs on more platforms, including the web. WebGPU is extremely new and the standard hasn't been finalized yet. Last week, Google announced that the Dawn implementation now supports Linux (previously only Windows and MacOS), and that they now support the WGSL shader language. If I wanted to start playing with WebGPU, it looks like Dawn is finally ready to be used in Curv on an experimental basis.

So given all of these considerations, and given that I'm the only one working on this right now, my first priority is to fix the compiler limitations I have mentioned. By the time that is done, WebGPU will be stable, so then I can transition to WebGPU and start implementing these advanced, high performance rendering techniques.

Does anything that I have mentioned sound like something you would like to work on? Do you have background in C++, or writing a compiler, or GPU/graphics programming? Do you want to build a GUI for Curv, or study the mathematics of symmetry and write a Symmetry library entirely in Curv?

Doug Moen.

Xiaoyue Wang

unread,
Nov 2, 2020, 11:28:42 AM11/2/20
to Doug Moen, Curv
Hi Doug,

Last week I tried adding  >> colour red to the code and successfully rendered it also exported it to STL. There's and interesting thing: I tried to render 30 links first, and then modified via -le flag to 100 links, and the 100 links just rendered instantly! I also exported 3169 struts within 2 mins. But if I want to export 3170, segmentation fault.
Now I am working on the bounding box thing to try reduce the number of union operations needed. I will have more tests on some cases and then reply more. Just want to let you know first.

I myself have background in C++, have some basic knowledge about compilers, but not too much. I don't have experience in GPU programming. Currently I am working so I may not have an entire bulk of time to write a library. But I generally found what you said helpful and would like to see whether I can find more insights.

Sincerely
Xiaoyue (Serena) Wang
.

To view this discussion on the web, visit https://groups.google.com/d/msgid/curv/601ba649-86cf-453f-8b42-adef8d92144c%40www.fastmail.com.

Xiaoyue Wang

unread,
Mar 9, 2021, 8:17:16 PM3/9/21
to Doug Moen, Curv
Hi Doug,

I am very thankful for your previous reply and I would like to give some updates on my current progress on this problem.

Previously with the help of >> colour red I successfully made large unions possible, but there's a limit to the number of structs. I found the main problem of the segmentation fault is due to the compiled c++ file being too large, too many lines, even hard to open. Later on I found that if I put the struts' information into an array, and write a for loop in the distance function manually, then all the information of the struts will be compiled into a single line in the c++ file. This solved my problem and I can export the union of many structs as long as the array is smaller than size of 2^16 = 65536.

Later on, I implement a special distance function so that the whole union object can be processed layer by layer or block by block to accelerate. That also works, although not fast enough. I found my current algorithm export every voxel slower with the size of the union object being greater.

The method above may not be very capable of generalizing to many other cases, but I hope that can be somewhat helpful or maybe inspiring.

Also I would like to ask if you have any idea on the limitation of the size of the array (65536), and other limitations of the grammar used in the Subcurv? (I found that I could not use irregular arrays or string, nor can I modify the elements in a 3D-array once I have already defined it.) Is there any way to bypass those limitations? Also did you ever encounter the case that the exporting speed (how many voxels processed per second) becomes slower when the size of the object becomes larger?

Sincerely
Xiaoyue (Serena) Wang
.


Doug Moen

unread,
Mar 9, 2021, 11:03:18 PM3/9/21
to Curv
There used to be a hard limit of 65536 array elements in Subcurv, but as far as I know I removed that limit in June 2020. Maybe you should file an issue on github about this, and give instructions on how to reproduce the problem, so that I can investigate.

Xiaoyue Wang

unread,
Mar 10, 2021, 1:18:51 PM3/10/21
to Doug Moen, Curv
Thank you! I upgraded and bypassed the 65536 limit. I found that now the speed limit is on the size of the arrays I used in the distance function. Do you know whether there's a way to slice a matrix inside the distance function? I currently have a matrix of m x n x vec2, I would like to only get out the ith row of the matrix.

To view this discussion on the web, visit https://groups.google.com/d/msgid/curv/0dd726c7-ceb8-4b40-86a0-4200c34f032d%40www.fastmail.com.

Doug Moen

unread,
Mar 10, 2021, 5:39:25 PM3/10/21
to Curv
I do have a plan to make SubCurv more powerful and expressive, so that this kind of code is easier to write and more efficient. The changes will be appearing this year.

There will always be limitations on modifying large arrays inside a distance or colour function, because of the way that GPUs work. Each GPU core only has a limited amount of local memory that can be efficiently modified while a distance function is evaluated. Large arrays must be readonly.

But I do plan better data structure support in SubCurv. And there will be a way to define 'types', so that you can control the memory layout of GPU data structures.

Export speed is determined by (a) how many voxels the model is partitioned into, and (b) how expensive it is to call the distance function. The distance function is called once per voxel, so the slower your distance function is, the longer it takes to export.

> Do you know whether there's a way to slice a matrix inside the distance function? I currently have a matrix of m x n x vec2, I would like to only get out the ith row of the matrix.

I don't support that kind of matrix slicing right now in SubCurv because I'm using OpenGL 3.3 (for Mac compatibility) and the Mac version of GLSL (which I am compiling into) is too primitive to support this. But I plan this for the future. I don't want to use different shading languages on different platforms, too much software complexity. So my plan is to rewrite Curv so that instead of OpenGL, I am using WebGPU. This API runs on Linux, Mac, Windows and future web browsers with the same API on all platforms. But the rewrite is a big job and won't happen too soon. In the WebGPU shader language, I'll represent that matrix as an array [m] of array [n] of vec2, and then that particular slicing will be easy.

Doug Moen.

On Tue, Mar 9, 2021, at 8:16 PM, Xiaoyue Wang wrote:

Xiaoyue Wang

unread,
Mar 11, 2021, 2:37:53 PM3/11/21
to Doug Moen, Curv
Hmm, I see.

I tried exporting the C++ source file and I found that the union does not consider the bounding box of each shape. I think it would be much faster if the bounding box is taken into consideration, since the number of objects in a certain area will be reduced. Is it possible to implement this?

Also I found that if using a if/else condition in the dist function, both results will be computed, instead of just judging the condition and then compute only one result. If that can be improved I think it will also work.


Doug Moen

unread,
Mar 13, 2021, 11:33:06 PM3/13/21
to Xiaoyue Wang, Curv
> union does not consider the bounding box of each shape
True, and this is something that needs to be included in Curv. One approach I'm considering is "tile based rendering" on the GPU, but that requires compute shaders, and won't be feasible until I switch to WebGPU. Another approach is to build a binary space partitioning tree from the bounding boxes of all the shapes in a large union. That's something that it might be possible to prototype in Curv right now. I've seen some stuff on ShaderToy.com that does this, so the same approach could work in Curv.

> using an if/else condition in the dist function, both results will be computed
That's a limitation of the SubCurv compiler that needs to be fixed.

You previously asked:
> Do you know whether there's a way to slice a matrix inside the distance function? I currently have a matrix of m x n x vec2, I would like to only get out the ith row of the matrix.

I changed my mind about this. This is something that can be fixed right now, if I am clever and use a different representation of arrays.

I see that the main problem you are dealing with is the limitations of the SubCurv language and compiler, which need to be fixed. The main challenge for me is that I need to redesign the SubCurv compiler to make it easier to work on. I'm at a stage in my other projects where it makes sense for me to spend some time on that now.

Doug Moen.

Xiaoyue Wang

unread,
Mar 30, 2021, 6:42:11 PM3/30/21
to Doug Moen, Curv
Hi Doug,

I am keep trying this and I would like to revise what I said previously:
> I found that now the speed limit is on the size of the arrays I used in the distance function. Do you know whether there's a way to slice a matrix inside the distance function?
Well, I found actually the problem is not with that indexing an array costs too much computation. Loading the array itself caused the problem. For testing, I added some padding elements which would not be used in calculation at all, after the original elements, and found the speed of exporting was lowered dramatically.
I exported the C++ file and see that in the calculation of every voxel, the array would be defined in the
extern "C" void dist(const vec4* param0, float* result)
function. Do you think the problem is here? That the constant arrays are defined inside the dist function so that it has to be re-loaded every time?

I have some time to spend on this project recently, let me know if I can help. Previously I was asked about my skill set, and to remind, I know well of C++, only the basic understanding of compilers but no coding experience on this, and no experience on GPU-related coding. I would love to learn beyond my skill set, but if there's something that only need C++ and a little bit of other things it might be easier for me to start on :D Please don't feel pushed if you don't have time to discuss a lot on this. Take your time.

Also I will reply you on the discussion panel about what I posted earlier today.

Thank you very much!

Sincerely
Xiaoyue.




Doug Moen

unread,
Mar 30, 2021, 9:55:45 PM3/30/21
to Xiaoyue Wang, Curv
Yes, this makes sense. I should probably be representing large arrays as OpenGL buffer objects, not as GLSL source code.
Reply all
Reply to author
Forward
0 new messages