Implement 3D Hull - Githubissues

z3dev commented 5 years ago

An implementation based in gl-vec3 points.

https://www.npmjs.com/package/quickhull3d

https://github.com/jscad/OpenJSCAD.org/issues/226

kaosat-dev commented 5 years ago

@z3dev that is a good one (I checked it out and experimented with it around a year ago).

Internally it uses half edge data structures (the main alternative geometric implementation I mentioned a few times for ...V3 ? :)
it sadly has a very big set of dependencies (at least as far as I remember)
still worth digging into at some point imho

hg42 commented 5 years ago

I read the PDF and I think it is a solid (<- pun unintended) library. See https://github.com/jscad/OpenJSCAD.org/issues/226#issuecomment-454322290 I will continue this here. I might also do a V2 implementation but I would tend to wait until I really use V2 (it's in heavy development I think, not a good time to add such second level functionality).

hg42 commented 5 years ago

btw. apart from being a newbie in node.js, I am also new to jscad (having used openscad with a python wrapper for several years). That's why I really need the hull function.

z3dev commented 5 years ago

@hg42 Cool!

@kaosat-dev and I are hashing out the guts of V2 now, and it looks like we are coming to a great plan. Hold on for a week or two. We should have something more stable to work with. All comments on V2 are also welcome. 😃

hg42 commented 5 years ago

ok, I'll try my best to wait :-)

hg42 commented 5 years ago

it's working now (first 3D tests) in cli and web, using csg master branch. I didn't check desktop, but it uses an older csg anyways (why?)

hg42 commented 5 years ago

z3dev commented 5 years ago

@hg42 Wow! That was fast! Awesome!

Basically, everything released is using the V1 CSG library at this time. So, your results (if based on the previous work) should work fine.

HOWEVER...

What we really want...

something that we own and maintain (dependencies NONE)
something that works with V2 solids (geometry)
something that can be represented via the API (declarative)

So, please dig deeply into V2. And let us know if the quickhull3D is compatible.

Again, this is a little early. But we are making some progress on V2.

hg42 commented 5 years ago

Do you mean rewriting quickhull3d with jscad data structures and embedding it? Or copying the necessary files? Or to browserify the package like @jallwine did?

something that we own and maintain (dependencies NONE)

hmm, I am a big fan of using modules and collaborating. In most cases the creator of a module will be the one who knows best how it works and how it can evolve and how it should be maintained. If you try to maintain it yourself, you are duplicating his work and you usually don't reach the expert level of the original creator. There are certainly algorithms that have an optimal implementation, no bugs and will not change. Like mathematics.

something that works with V2 solids (geometry)

the hull() function has the same interface as before. Or do you mean the quickhull3d function? I am currently not aware what is special with V2 solids. I can take a look and try to understand what you might mean.

something that can be represented via the API (declarative)

not sure what you mean here... the hull() function is a relatively small wrapper around quickhull3d, simply converting the data structures to pure arrays. This is a small overhead compared to what runs inside the function, the internal use of simpler structures might even be faster. But I don't know, this would have to be evaluated.

btw. chain_hull also works out of the box, because it doesn't check the type (which is the correct way):

kaosat-dev commented 5 years ago

@hg42 that was really fast, kudos ! To expand a bit on what @z3dev said:

for now csg.js has zero dependencies, and as much as possible we would like to keep the number of dependencies close to zero (unless a dependency has a huge benefit): I agree about specialized dependencies and their quality, unfortunately the indirect dependencies tend to turn that into a problem.
desktop: that is a mistake, but again the 'inbetween' status above makes it hard to maintain all.
V2 is still an early work in progress but a LOT of things are changing, and unfortunately right now we are in an in-between state where things are still messy , and we have 'frozen' V1 because we just do not have the time to maintain two versions, and V1 has too many fundamental problems to continue as such. It means we will not add any more code or do releases for V1 : however I am very curious about how you implemented the bridge between csg & quickHull3d as quickHull3D uses half edge data structures which is the most likely candidate for future internal geometric formats for jscad (we discussed this a bit with other people from the stack.gl/regl community)

hg42 commented 5 years ago

thanks, but the work was already done before by @jallwine and I already had my own bindings, I only had to adapt it to changes in data structures, coding style etc. Fortunately, @jallwin's code and mine complemented each other. Also, this wrapper was quite simple.

I know (because I see) that everything is in flux for V2. Despite of that I would like to have a running csg V2 for testing and investigating. Partly to continue with hull3d on V2 (it's partly ready). And also to look deeper into V2 (learning by doing).

However, currently it doesn't run in cli, because of an error (if using V2 branch of both repos): Error: Cannot find module './primitives3d-api' and web shows the same.

Are you already using the V2 code (even if incomplete)? If "no", then no problem, I will wait. if "yes", could you tell me which combination of branches/commits of OpenJSCAD.org and csg.js you are using which work for you? Additionally, which package are you using for testing? cli, web? (I guess not desktop) I mainly use cli (creating stl, displaying in an independent viewer), and web (currently displaying the jscad file via npm run dev).

I am asking because my setup could be wrong or I am doing something wrong, e.g. because my knowledge about node.js and tools is still limited. Usually I check out a working repo, try to become familiar with it and test it for a while and then start my own changes. This way I am mostly sure it's my fault. So, I want to start with a known working state that includes csg V2.

kaosat-dev commented 5 years ago

Are you already using the V2 code (even if incomplete)?

NO we are not in a state yet where even the basics are in place. It is getting there, slowly but surely. In a few weeks time, things will have changed a lot already and bits and pieces will be working.

kaosat-dev commented 5 years ago

If you want some stable, know code, then it is V1 , not V2

hg42 commented 5 years ago

ok, then I'll wait until anything is "runnable" enough to play with it

khjde1207 commented 5 years ago

I will cheer. will wait. Please add features!!!

z3dev commented 5 years ago

We love fans! Thanks, @khjde1207

pentacular commented 5 years ago

I put together my own quickhull a while back. The approach I used was to generate a point cloud and hull that. It was also simpler for me, since I use jscad as a library, so I could easily use quickhull as an external dependency.

The nice thing about a point cloud is that you can convert both 2d and 3d shapes to point clouds, translate, rotate, etc, then union, and then hull those together.

(Assuming that point clouds were a V2 geometry, that is)

hg42 commented 5 years ago

@pentacular yes, my pull request also extracts a point cloud from the objects. Mainly because it's the data quickhull expects. That's one of the reasons I asked for a stable API for the basic types, like points, lines, in 2D, 3D, etc. It should also allow to extract points from objects, lines from objects, etc.

pentacular commented 5 years ago

Yes, I think that's exactly right.

We need a set of geometries, which support operations like union, intersection, difference, transform, and a set of interchange representations which geometries can produce and be produced from.

Then perhaps we can support quickhull as a dependency of a model rather than of csg.

hg42 commented 5 years ago

Most operations make also sense when applied to any combination of 1D, 2D and 3D structures (note, all with 3D coordinates). E.g. you can intersect a point cloud with a sphere. Or a bunch of lines with a bunch of other lines. Or lines with a cube.

My use case was about implementing a slicer for 3D printing in jscad (as an experiment). E.g. in case of an infill pattern it would be useful to describe a pattern as lines in each layer (limited by min/max x,y,z of the object to be filled, which is filling a cuboid) and you could intersect all these lines with the 3D object. All operations of a slicer involve 3D and 2D objects.

pentacular commented 5 years ago

I've put together a design showing how we might get this done, and put in a number of PRs in this direction.

The doc is available here -- feel free to comment or edit (they'll show up as suggestions) https://docs.google.com/document/d/1nz7dhtErHBqBpuFcu7ooRU91miVTD4UxiJ6od1TbUgs/edit#

Hull should be implementable as a transformation of interchange formats.

e.g., geometries -> point arrays -> hull() -> polygon array -> geometry

It should also be possible to drop in user defined geometries.

And things like conversion functions can work the same way

geometry -> polygon array -> conversion() -> encoded string.

Please let me know what you think :)

z3dev commented 4 years ago

V2 now includes hull for 3D geometries, using quickhull.

I’m closing this issue as the general discussion has been resolved. Specific issues can be opened against V2 OpenJSCAD.org.

jscad / csg.js

Implement 3D Hull #133