How to separate a geometry having distinct objects ?

classic Classic list List threaded Threaded
30 messages Options
12
Reply | Threaded
Open this post in threaded view
|

Re: How to separate a geometry having distinct objects ?

Ronaldo
I don't have either a solution to the task of finding the connected component of a model. Even if all mesh data needed to reproduce the model with a polyhedron call was available, the process of finding the components with the language would be rather inefficient because there is no effective way to mark vertices during a tour through the mesh. 

Jordan Brown <[hidden email]> wrote:
It is only when the geometry work is done that it starts to be possible to determine things like bounding boxes,
like how many solids result from a particular boolean operation, and so on - and that's too late for the OpenSCAD program to take any action, 
because it's already done.

As a side comment without arguing against that, with some ingenuity its is possible to generate fully parametric models like the one bellow:

fob.PNG
The design would be simple to be done from the bounding box data of the inscription and so we are tempted to give up before realizing that the data is not essential, the bounding box itself is enough.

// inscription data
text = "Any text here";
size = 10;

// fob data
margins   = [7, 4];
border    = 2;
thickness = 2;
depth     = 1;

fob(margins, border, thickness)
    union() {
        text(text,size=size,valign="center");
        translate([-size*7/16,0])
            rotate(18)
                circle(size*5/16,$fn=5);
    }

module fob(margins, border, thickness) {

    module simple_fob(dimens) {
            minkowski() {
            translate([0,0,.01])
            cube([dimens[0], dimens[1],.02], center=true);
            bbox()
                linear_extrude(dimens[2], convexity=10)
                    children();
        }
    }

    difference() {
        simple_fob([margins[0]+border,margins[1]+border, thickness])
            children();
        difference() {
            translate([0,0,thickness-depth])
                simple_fob([margins[0],margins[1], thickness])
                    children();
            linear_extrude(thickness, convexity=10)
                children();
        }
    }
}

The code relies on an operator (a module that handles children() ), bbox(), to generate the bounding box geometry that is a simple cube. That operator may be coded in OpenSCAD as it can be seen in the now overlooked OpenSCAD Manual section, Tips and Tricks. Although the code makes use of minkowski(), an operator usually considered slow, its operation involves only cubic shapes and it is fast. In my machine, the render (F6) of this model takes a few seconds.

The bbox() operator may be also helpful for defining a clipping box fitted to a design as discussed here elsewhere.

 

_______________________________________________
OpenSCAD mailing list
To unsubscribe send an email to [hidden email]
Reply | Threaded
Open this post in threaded view
|

Re: How to separate a geometry having distinct objects ?

RobWLakes
In reply to this post by JordanBrown
I find this response Jordan really informative/intriguing, really well written, and I really want to know more about how this division and sequence of processing occurs in OpenSCAD. You have flagged the top level reasons for why OpenSCAD can't "post process" objects, but I still don't understand the process how it works. Is a fuller explanation of your response available somewhere? Is there an OpenSCAD page that illuminates this?

Forgive my ignorance, but given the frequency of questions relating to these "limitations" on this forum I suspect I am not alone, but I think a lot of frustration with OpenSCAD could be quickly defused with a more in depth explanation along these lines that people like me could be referred to?

How can all the processing be completed, then the geometry completed after that?
Cheers, RobW

On 26 March 2021 11:46:55 am AEDT, Jordan Brown <[hidden email]> wrote:
It is certainly possible to imagine a 3D design tool, even a programming language like OpenSCAD, that can do things like cut up an object and then manipulate the separate solids that result.

OpenSCAD can't do that without a major overhaul, because it doesn't do any of the geometry processing until after the program has finished running.

The immediate output from an OpenSCAD program is not geometry, not a list of triangles, et cetera.  It is a tree representation of shapes, transformations, and the operations to be done on those shapes.  Look at Design / Display CSG Tree to see.  If you write "intersection() { sphere(); cube(); }", you'll see that that's pretty much what the CSG tree shows.  All of the expressions have been evaluated, all of the loops unrolled, all of the conditionals considered, but *none* of the geometry work has been done.  At that point in the processing, OpenSCAD doesn't *know* anything interesting about the geometry.

It is only when the geometry work is done that it starts to be possible to determine things like bounding boxes, like how many solids result from a particular boolean operation, and so on - and that's too late for the OpenSCAD program to take any action, because it's already done.

Could OpenSCAD have been designed differently, so that it did the geometry as it was processing the program, as Cascade Studio apparently does?  Sure.  But it wasn't, and that's a pretty fundamental design decision and a big job to change.

BTW, this isn't something that's a problem with the OpenSCAD language per se.  Another environment could easily make the same design decision.  Carsten's AngelCAD has the same architecture - in fact, it does the geometry work in a totally separate program.  I don't know about Doug's Curv - Doug?


_______________________________________________
OpenSCAD mailing list
To unsubscribe send an email to [hidden email]
Rob W
Lake Tyers Beach,
Victoria, Australia
Reply | Threaded
Open this post in threaded view
|

Re: How to separate a geometry having distinct objects ?

JordanBrown
On 3/26/2021 4:27 AM, Rob Ward wrote:
How can all the processing be completed, then the geometry completed after that?

The simplest explanation is to set up a model, F5 it, and then look at Design / View CSG Tree.

(Side note:  It would be nice if, once you have the CSG Tree Dump window up, it was updated on subsequent runs.)

Consider this program:
difference() {
    cube(20, center=true);
    for (x = [-5:10:5], z=[-5:10:5]) {
        if (x > 0 || z > 0) {
            translate([x, 0, z])
                rotate([90,0,0])
                cylinder(h=21, d=5, center=true);
        }
    }
}

which generates this object:

The output from the processing of the OpenSCAD language is this, from Design / Display CSG Tree:

difference() {
  cube(size = [20, 20, 20], center = true);
  group() {
    group() {
      multmatrix([[1, 0, 0, -5], [0, 1, 0, 0], [0, 0, 1, 5], [0, 0, 0, 1]]) {
        multmatrix([[1, 0, 0, 0], [0, 0, -1, 0], [0, 1, 0, 0], [0, 0, 0, 1]]) {
          cylinder($fn = 0, $fa = 12, $fs = 2, h = 21, r1 = 2.5, r2 = 2.5, center = true);
        }
      }
    }
    group() {
      multmatrix([[1, 0, 0, 5], [0, 1, 0, 0], [0, 0, 1, -5], [0, 0, 0, 1]]) {
        multmatrix([[1, 0, 0, 0], [0, 0, -1, 0], [0, 1, 0, 0], [0, 0, 0, 1]]) {
          cylinder($fn = 0, $fa = 12, $fs = 2, h = 21, r1 = 2.5, r2 = 2.5, center = true);
        }
      }
    }
    group() {
      multmatrix([[1, 0, 0, 5], [0, 1, 0, 0], [0, 0, 1, 5], [0, 0, 0, 1]]) {
        multmatrix([[1, 0, 0, 0], [0, 0, -1, 0], [0, 1, 0, 0], [0, 0, 0, 1]]) {
          cylinder($fn = 0, $fa = 12, $fs = 2, h = 21, r1 = 2.5, r2 = 2.5, center = true);
        }
      }
    }
  }
}

Note how all of the "program" stuff is gone.  There are no variables, there are no loops, there is no "if".  There's just shapes (a cube and three cylinders), transformations (the matrix multiplications), and boolean operations (the difference).

Note:  I assume that this is a textual representation of an in-memory data structure, rather than text that's actually generated in the middle of the pipeline.  But I don't know.

This is the data that comes out of executing the program, that then goes into the geometry engines.

For Carsten's AngelCAD environment it's more distinct - an AngelCAD execution generates an XML file with basically the same data as above, and then a separate program interprets and displays it.

Does that sort of make sense?



_______________________________________________
OpenSCAD mailing list
To unsubscribe send an email to [hidden email]
Reply | Threaded
Open this post in threaded view
|

Re: How to separate a geometry having distinct objects ?

MichaelAtOz
Administrator
In reply to this post by gilboonet
gilboonet wrote
Hello, I recently discovered Cascade Studio and with it I was able to make
those separation I needed.
So the subject question is now resolved.
OpenSCAD Admin - email* me if you need anything, or if I've done something stupid...
* on the Forum, click on my MichaelAtOz label, there is a link to email me.

Unless specifically shown otherwise above, my contribution is in the Public Domain;
to the extent possible under law, I have waived all copyright and related or neighbouring rights to this work.
Obviously inclusion of works of previous authors is not included in the above.


Sent from the OpenSCAD mailing list archive at Nabble.com.

_______________________________________________
OpenSCAD mailing list
To unsubscribe send an email to [hidden email]
OpenSCAD Admin - email* me if you need anything, or if I've done something stupid...
* on the Forum, click on my MichaelAtOz label, there is a link to email me.

Unless specifically shown otherwise above, my contribution is in the Public Domain;
to the extent possible under law, I have waived all copyright and related or neighbouring rights to this work.
Obviously inclusion of works of previous authors is not included in the above.
Reply | Threaded
Open this post in threaded view
|

Re: How to separate a geometry having distinct objects ?

gilboonet
Indeed, I already had two working scripts, OpenJSCAD v1, and a JSCAD (OpenJSCAD v2), this thread is about an OpenSCAD version and it's still not possible, but I now have a Cascade Studio working script. I hope that one day it will be possible with OpenSCAD.

Sent from the OpenSCAD mailing list archive at Nabble.com.

_______________________________________________
OpenSCAD mailing list
To unsubscribe send an email to [hidden email]
Reply | Threaded
Open this post in threaded view
|

Re: How to separate a geometry having distinct objects ?

gilboonet
And to be more precise, with OpenJSCAD (v1 and v2 versions) I needed to write my own function to separate distinct geometries, and with Cascade Studio there was already a built-in function to do that (GetSolidFromCompound).

Sent from the OpenSCAD mailing list archive at Nabble.com.

_______________________________________________
OpenSCAD mailing list
To unsubscribe send an email to [hidden email]
Reply | Threaded
Open this post in threaded view
|

Re: How to separate a geometry having distinct objects ?

doug.moen
In reply to this post by JordanBrown
On Thu, Mar 25, 2021, at 8:46 PM, Jordan Brown wrote:
It is certainly possible to imagine a 3D design tool, even a programming language like OpenSCAD, that can do things like cut up an object and then manipulate the separate solids that result.

Many of the OpenSCAD-like programs are capable of doing this. The primary requirement is that you treat shapes as values, and that you provide programmatic access to the representation of shape values. There are two reasons OpenSCAD can't do this. One is purely about syntax: the language is designed so that it is impossible to reference a shape as a value. The other reason is cultural: the feature has been left out of the language due to concerns about performance. Although, note, the operation to get a triangle mesh out of a shape would be no slower than render(). 

OpenSCAD can't do that without a major overhaul, because it doesn't do any of the geometry processing until after the program has finished running.

The render() module already exists: it renders the shape into a triangle mesh before the preview runs. So that's not the problem. The "major overhaul" is to the syntax, because it is currently impossible to write a function that takes a shape as an argument and returns a value.

Given that many or most modelling languages let you query geometry, I think the remaining question is whether you can implement this kind of algorithm efficiently in the modelling language. If you are doing this in the domain of triangle meshes, then some models have hundreds of thousands, or millions, of triangles. If you are doing this in Curv, then you are doing it over a voxel grid, and there can likewise be a huge number of voxels. If the performance is superlinear in the number of triangles/voxels, then the wait time could be substantial for complex models.

I don't know about Doug's Curv - Doug?

It's theoretically possible to implement this feature in the Curv language, but the performance would be terrible, because Curv is an interpreted language.

Ideally, you would want to perform this operation in about 50 milliseconds. That would be fast enough to support animation in the customizer, if you are dragging a slider around and watching the shape change in a preview window. I think the best way to get this kind of performance is to design a shape splitting algorithm that can be implemented on the GPU using massive parallelism. Curv programs can be compiled into GPU code, but only for the purpose of rendering, not for doing compute, which is what's needed here. The next major version of Curv will also support GPU compute, because in my opinion that's the missing feature in general purpose high performance 3D modelling languages.

_______________________________________________
OpenSCAD mailing list
To unsubscribe send an email to [hidden email]
Reply | Threaded
Open this post in threaded view
|

Re: How to separate a geometry having distinct objects ?

JordanBrown
On 3/27/2021 9:40 AM, Doug Moen wrote:
The primary requirement is that you treat shapes as values, and that you provide programmatic access to the representation of shape values.

No, or not exactly.  You have to actually *do* the various transforms and operations while the program is running.

I wrote a cheesy little Python-based environment, that processes a Python API that looks sort of like OpenSCAD.  It doesn't happen to offer access to the "insides" of objects, but it could.  But that access won't help here, because the "insides" are just the CSG tree.  The "insides" of a cylinder are two radii and a height - not a triangle mesh.  Just as in OpenSCAD, the "output" of the program is a CSG tree, that is then processed by another program to produce previews and STL.

The render() module already exists: it renders the shape into a triangle mesh before the preview runs. So that's not the problem.

Yes, it's before the preview.

No, it's not before the program proper finishes executing.  render() is just a node in the CSG tree.  It doesn't *do* anything until you start processing the tree, which is after the program finishes.

Try this program:
n = 3;
m = 6;
for (i=[1:n]) {
    render() {
        for (j=[1:m])
            translate([i,j,0]) sphere(d=i+j);
    }
    echo(i=i);
}

Watch the timing of the "echo" output.  Observe that the echo output comes out instantly, and *then* the slow part starts.


_______________________________________________
OpenSCAD mailing list
To unsubscribe send an email to [hidden email]
Reply | Threaded
Open this post in threaded view
|

Re: How to separate a geometry having distinct objects ?

gilboonet
In reply to this post by doug.moen
Curv seems very interesting. As I'm doing designs for cardboard crafting I didn't thought of using it, but I will try. Some months ago, Kurt Hutten (who is very active in the field of code-cad) wrote a post on OpenJSCAD forum about a list of curated code cad tools, and I told that it would be a good thing to have uses cases and see each tool efficiency, that's why I'm now trying to make the script that made me come to this question here, with as many design tools as possible, especially OpenSCAD that is the first of them (even if pov-ray was the first 3d tool I used on the 90').

Sent from the OpenSCAD mailing list archive at Nabble.com.

_______________________________________________
OpenSCAD mailing list
To unsubscribe send an email to [hidden email]
Reply | Threaded
Open this post in threaded view
|

Re: How to separate a geometry having distinct objects ?

doug.moen
In reply to this post by JordanBrown
If you have programmatic access to the CSG tree, and you have a Turing equivalent programming language, then it's guaranteed that you can write an algorithm to split the tree into disjoint shapes.  To solve the general case, you'd have to tessellate primitives into triangle meshes yourself, but that is doable in OpenSCAD. Obviously it would be slow, but that's why I said that performance considerations are really important. Obviously it would be better to have an operation that returns the mesh for a shape. I don't think it's that hard to implement (except for syntax). There's already a function that converts a CSG tree to a mesh, just call this function from the interpreter, then convert the mesh to an OpenSCAD value. You don't need to restructure OpenSCAD to do this (see below), except maybe for the syntax issues I mentioned. The arguments I've heard against providing this operation have mostly been about performance: the operation would slow down the onset of preview as much as render() does, and then iterating over the triangle mesh in OpenSCAD might be slow as well (depending on the model), potentially creating even more lag before the preview is rendered.

This rejected pull request demonstrates how to evaluate geometry from inside the interpreter. It's easy:
The relevant code is
   GeometryEvaluator geomEvaluator(tree);
   geom=geomEvaluator.evaluateGeometry(*nc,exact);

The scary part is the syntax. You might need to do major surgery on the parser. Maybe syntax like this:
   geom = evaluate_geometry( cube(10); )
or from inside a module,
   geom = evaluate_geometry( children(); )
The issue is that evaluate_geometry is not a module and not a function, it is some weird new syntax wired in to the parser. The argument is an OpenSCAD *statement*, making it a kind of syntax that isn't currently supported.

Doug Moen.

On Sat, Mar 27, 2021, at 1:08 PM, Jordan Brown wrote:
On 3/27/2021 9:40 AM, Doug Moen wrote:

The primary requirement is that you treat shapes as values, and that you provide programmatic access to the representation of shape values.

No, or not exactly.  You have to actually *do* the various transforms and operations while the program is running.

I wrote a cheesy little Python-based environment, that processes a Python API that looks sort of like OpenSCAD.  It doesn't happen to offer access to the "insides" of objects, but it could.  But that access won't help here, because the "insides" are just the CSG tree.  The "insides" of a cylinder are two radii and a height - not a triangle mesh.  Just as in OpenSCAD, the "output" of the program is a CSG tree, that is then processed by another program to produce previews and STL.

The render() module already exists: it renders the shape into a triangle mesh before the preview runs. So that's not the problem.

Yes, it's before the preview.

No, it's not before the program proper finishes executing.  render() is just a node in the CSG tree.  It doesn't *do* anything until you start processing the tree, which is after the program finishes.

Try this program:

n = 3;
m = 6;
for (i=[1:n]) {
    render() {
        for (j=[1:m])
            translate([i,j,0]) sphere(d=i+j);
    }
    echo(i=i);
}

Watch the timing of the "echo" output.  Observe that the echo output comes out instantly, and *then* the slow part starts.



_______________________________________________
OpenSCAD mailing list
To unsubscribe send an email to [hidden email]
12