Work on general sweep

[Dario Pellegrini]

Hi Doug,

First of all, congrats for your work, it really resonates with my modus operandi down to the use of vi(m) in the presentation video on the home page! I have been struggling with the limitations of OpenSCAD for a while and I would like to step up to a more, powerful flexible and modern set of modelling techniques.

I have skimmed the documentation and gone through the future work. The general sweep problem looks particularly interesting to me. I would like to tackle that one in order to familiarize with the source.

Do you think that a generalized repetition built from a parametric affine transformation would be a feasible/good approach? Is it ok if I investigate that?

Thank you in advance for any guidance you can provide!

Dario

PS. the link to the swept volume of libigl is broken, I think that the correct one is this: https://libigl.github.io/tutorial/#swept-volume

[Doug Moen]

Hi Dario.

I do actually want to build a GUI for Curv, it's just lower priority than making the language and GPU compiler more powerful. Which is what I'm working on right now.

Sweep is an important problem. In retrospect, what I would like better than sweep is a primitive that takes a roughly cylindrical shape (centered on the Z axis) and warps this cylinder to follow the path of a parametric curve. I'll call this "conform_to_path" until I think of a better name. To sweep a 2D shape along a path, you use 'extrude' to extrude the shape along the Z axis, then pass the result into "conform_to_path".

The libigl sweep algorithm is to iteratively render the shape into a voxel grid at multiple points along the parametric path. One of my ideas is to add a voxel grid data type, and provide an operation for rendering an SDF shape into a voxel grid. The voxel grid can then be used as a shape. This will be roughly analogous to OpenSCAD's "render" operation. You could use it to implement the libigl sweep algorithm.

I've also considered how to implement sweep of a 2D shape along a 3D path (or conform-to-path) purely in the domain of signed distance functions (without using voxel grids).

Here's a paper that discusses the problem (sweeping a 2D template along a 3D path):

http://www.unknownroad.com/publications/SweepsGraphite05.pdf

I haven't read this in years, but here's my mental model. You have a parametric curve F through 3D space, parameterized by a 't' parameter. You need a function G that maps a 3D point to: the nearest point on the parametric curve, and to the value of 't' at this nearest point. That can be done using iterative root finding. G also needs to compute an angle theta. Then the 2D sweep or the conform_to_path distance function uses the distance to the nearest point, the t value, and theta, puts that into the distance function of the pseudo-cylinder that is the argument to conform_to_path, and computes a distance to the warped cylinder.

The good news is that it should be possible to implement this all in the Curv language (no C++). The bad news is, since the function G is using iterative root finding, it may be slow compared to the usual distance functions found in the Curv shape library. The frame rate in the preview window may be prohibitively low, in which case you would have to render it to a triangle mesh in order to view it (eg, export as an OBJ file).

Once Curv has a "render" function that converts a shape to a voxel grid, we'll be able to preview shapes with slow distance functions.

Do you think that a generalized repetition built from a parametric affine transformation would be a feasible/good approach? Is it ok if I investigate that?

I'm not sure how that would work, but if you can make it work, great! There may be more than one way to do the job, and I've given you my idea. I will say that repetition is maybe not as powerful, or works differently, than you are currently imagining, so I don't see it as being useful. Repetition partitions space into disjoint regions, and copies part of a distance field into each of these regions. If one of these regions is smaller than the shape you are copying into it, then only a slice of the object will appear in the region. This, I believe, is not what you want for sweeping a 3D shape through 3D space (based on a prior experiment that I ran). See also my comment about making a 2D slice of a 3D object and then extruding it, which is something you can easily try and experiment with.

[Dario Pellegrini]

I was hoping for repetition to work for unioning objects, therefore computing directly:

as from the libigl doc. But ok, this is a no-way.

I do not like much voxels for anything but previews. 

They might be implemented efficiently using a sparse 3D tensor (a dense tensor will be quite limited in resolution), but the thing is that once you drop down to voxels you stick to voxels.

If you accept the compromise and have an efficient set of algorithms to operate on voxels, do you still care about SDF?

I am happy to be proven wrong, but for me any operation involving SDF should stay in the SDF (or equivalent) domain.

The conform-to-path (2D shape on 3D path) is an interesting problem (although I was really looking at 3D on 3D).

For the implementation of the root finding I would definitely stay at the C++ level leveraging on a powerful algorithm such as Brent's.

I may come back to this. I will read the paper anyway, maybe it will be inspiring also for the 3D on 3D.

Another approach to 3D on 3D is this one: https://en.wikipedia.org/wiki/Envelope_(mathematics)#Envelope_of_a_family_of_surfaces

The derivative is a bit nasty, but hopefully a numerical approximation will suffice, otherwise the alternative is storing the SDF in a symbolic fashion (I have experience with GiNaC) but that would probably require a major design change.

[Doug Moen]

An SDF (signed distance field) is a map from (x,y,z) to a signed distance value. This map can be represented as a function (code), but it can also be represented by a data structure. Data structure representations of an SDF have different performance characteristics than functions, which broadens the set of shapes you can represent efficiently. A voxel grid that contains a signed distance in each cell is a data structure representation of an SDF. To look up a value in a voxel grid SDF, you perform trilinear interpolation, which on a GPU is directly implemented in hardware. This interpolation smooths the SDF, so it doesn't look like minecraft. Function and voxel grid SDFs are compatible with each other. A shape could be rendered to a voxel grid then used as input to other shape operators. And yes, we would use a sparse voxel representation.

I think there are probably multiple ways to implement a sweep efficiently, but I bet they will all involve building an intermediate data structure of some sort.

There is no exact solution to the problem of sweeping a 3D shape along an arbitrary 3D path. Only approximate solutions are possible. Voxels are an approximation. Numeric root finding is approximate.

When you preview a shape, the signed distance function (which is written in Curv) is compiled into GPU machine code, which runs faster than compiled C++ code. When you export a shape to a mesh file, the signed distance function is compiled into C++ code, which is then compiled into optimized machine code. So it's definitely possible to put a root finder into a distance function written in Curv.

I've never looked at GiNaC before, thanks for the ref. I am adding limited symbolic computation facilities to Curv (the ability to construct symbolic expressions, to partially evaluate and simplify them, to replace symbols with values). I'm not building a CAS, just the features normally found in an optimizing compiler or partial evaluator. Derivatives are very useful when working with SDFs, so there is a use for a "differentiable programming" feature as well, for automatically computing derivatives. (I'm thinking of a numerical approach, not symbolic differentiation.)

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.

To view this discussion on the web, visit https://groups.google.com/d/msgid/curv/9755563e-380c-47b1-9879-016df23cc645n%40googlegroups.com.

Attachments:

• Screenshot from 2021-01-10 20-31-46.png
  

[Dario Pellegrini]

Mmh, yes, a trilinear interpolation would boost the resolution, then voxels are probably much better than I expected.

Also I thought that curv lang was a frontend to a C++ core, eventually offloading to GPU. I didn't understand that there are actually two separate compilation paths from curv lang.

I'll take some time to digest all of this and do a bit of research. For the time being, thank you very much for this very constructive exchange.

Dario