Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

Thinking about writing an Openscad to Libfive converter #310

Open
kasbah opened this issue Oct 9, 2019 · 10 comments

Comments

@kasbah
Copy link

commented Oct 9, 2019

Hey, I am thinking about attempting to write a converter from Openscad to high level Libfive Guile.

  • My current thinking is to implement it in Haskell (because it will be more fun for me and there's and Openscad parser) but maybe learning a bit of Guile and using that would be the better way forward?
  • Any immediate thoughts on roadblocks I might encounter?
  • Any resources that you think would help, like a reference of all the functions available in libfive? (I am still new to libfive)
@kasbah

This comment has been minimized.

Copy link
Author

commented Oct 9, 2019

I made a start on this (https://github.com/kasbah/openscad2libfive - currently just parses Openscad and nothing more). I also found the Help->Shape reference in Studio which is helpful.

@mkeeter

This comment has been minimized.

Copy link
Member

commented Oct 9, 2019

Awesome! A tool that lets folks run (most) OpenSCAD files in libfive would be a useful step towards wider adoption.

I had thought about implementing it in Studio itself (e.g. as an alternate language mode), but bounced off the challenge of parsing + understanding OpenSCAD – whatever's easiest on that front (i.e. the Haskell parser) makes sense as a first draft.

You should be able to translate most of the primitives and CSG operations directly, other than the minkowski operator. The documentation in the shape reference pane is generated from docstrings in these Scheme files:

@doug-moen

This comment has been minimized.

Copy link
Contributor

commented Oct 9, 2019

If you take the easy path, then you will implement an OpenSCAD-like language that isn't fully compatible with existing OpenSCAD programs. Many important primitives will be missing, and the primitives that are implemented won't be fully compatible. However, it will be possible to write simple programs that are portable between your language and OpenSCAD, if some guidelines are followed.

If you are writing a one way converter, with the intent of getting a rough translation that can be manually cleaned up afterwards, then this is probably good enough.

However, if you want an accurate implementation that is compatible with 90% of real OpenSCAD programs, then there are major challenges ahead. I'd have to write a long essay to explain, so full details on request.

For just a one-way converter, the initial challenge will be some primitives that are hard to implement. Matt mentioned minkowski. I would add hull. The import and surface modules, for importing various file formats, are probably a lot of work. polyhedron will be challenging. OpenSCAD can deal with huge polyhedra, with 10,000 or 100,000 faces, and I imagine you might encounter deadly performance problems here. The OpenSCAD text primitive can render arbitrary Unicode text using an arbitrary truetype font, and the Libfive text primitive is a very loose approximation. The OpenSCAD language has bizarre semantics, unlike any other programming language. It would be very time consuming to reverse engineer and reproduce these semantics, but for a converter, you just hack the original OpenSCAD source until the conversion works.

@kasbah

This comment has been minimized.

Copy link
Author

commented Oct 9, 2019

Thanks to both of you for your input. My motivating example is to be able to convert our microscope design. It doesn't use minkowski and text and import (dxf) are only used for non-functional bits, but it would require hull and polyhedron

I think I'll just have to have a go and see how far I get before it stops being fun. Sometime down the line I am sure we can get into the nitty gritty of OpenSCAD's bizarre semantics but it's probably too early and would just make me lose motivation at this stage 😆

EDIT: just found it does use minkowski as well, oh well, will still have a go

@doug-moen

This comment has been minimized.

Copy link
Contributor

commented Oct 10, 2019

It is possible to work around the problem with minkowski. I have catalogued all of the uses of minkowski in OpenSCAD that have been reported in the forums, and I've come up with specialized operators that support each special use case. The most common use for minkowski is computing offsets, by computing the minkowski sum of a shape with a sphere. Offsets are easy in libfive.

@doug-moen

This comment has been minimized.

Copy link
Contributor

commented Oct 10, 2019

Polyhedron is easy if polyhedra are convex. Then you just compute the intersection of a collection of half-spaces, converting each face to a half-space. It gets a lot more complicated if the polyhedron is not convex. Then you need to perform a Nef polyhedron construction.

@doug-moen

This comment has been minimized.

Copy link
Contributor

commented Oct 10, 2019

Just like minkowski, I think hull is impossible to implement in libfive in the general case. But you can look at how hull is used in your project, and maybe find a way to recognize those special cases and generate code specific to those cases.

@kasbah

This comment has been minimized.

Copy link
Author

commented Oct 10, 2019

For starters I will just aim to convert things that have a one-to-one equivalence. Out of curiosity though, is there something about the way libfive works that these advanced operations could never be implemented in libfive itself @mkeeter?

@doug-moen

This comment has been minimized.

Copy link
Contributor

commented Oct 10, 2019

Libfive currently represents shapes as signed distance fields, which are represented by closed-form expressions. Closed form means no conditional expressions or iteration.

I've gone looking for a signed distance field representation of the Minkowski sum, with no working code so far, just partial results. Another person I know has gone looking for an SDF representation of convex hull, again with no success. I've found no solutions reported in the research literature.

The only known algorithms for Minkowski sum and convex hull are approximate solutions. There are known ways to compute these operations for triangle meshes, or point clouds, or voxel grids, but if you are working with curved objects then these representations are only approximations.

In my project, Curv, signed distance fields are represented by arbitrary recursive functions. Conditionals and iteration are supported, which means that the Curv representation for SDFs is Turing Complete. That means it is theoretically possible to solve the problem, but doesn't guarantee that the solution will be fast, and I don't have an efficient implementation yet. In Libfive, the restriction to closed form expressions means that the representation is not Turing Complete, and I think I could prove that no solution to Minkowski sum is possible.

Maybe Libfive can be extended in the future to support Turing complete SDFs. That would enable a larger set of shapes to be represented.

@mkeeter

This comment has been minimized.

Copy link
Member

commented Oct 13, 2019

Yup, Doug has covered the main points – the challenge is that there's not a closed-form solution for a general convolutions, and libfive is deliberately not Turing-complete. There are certain cases that could be closed-form, e.g. sweeping a 2D shape along a line, but not the general case.

A few more thoughts for context:

One theoretically pleasing solution is to expand to a 6-dimensional space, with three dimensions for each of the shapes in the convolution. After rendering in 6D, you collapse the three extra dimensions back down into normal 3D space. Unfortunately, that scales as N^6, so the performance is probably prohibitive, but it would be fun to try :)

A more practical approach would be using libfive's Oracle interface, which lets you plug arbitrary black boxes into the otherwise-pure math tree. This is the universal escape hatch for anything that can't be represnted with the limited power of non-recursive trees. In this case, you could construct an Oracle which performs the convolution. It would probably want to do things in discrete space (e.g. a voxel-wise search to see if the models touch).

In many cases, convolving with a sphere is meant to thicken a model. In libfive, this could be accomplished with the offset function, as long as the f-rep has a gradient of 1. The behavior near corners could be slightly different, depending on the shape of the underlying distance field.

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Projects
None yet
3 participants
You can’t perform that action at this time.