Discussion - Possible way ahead for OpenSCAD hull and Minkowski requests?

Have some feature requests, feedback, cool stuff to share, or want to know where FreeCAD is going? This is the place.
Forum rules
Be nice to others! Read the FreeCAD code of conduct!
IPowIPi
Posts: 31
Joined: Sun Jul 25, 2021 9:37 am

Re: Discussion - Possible way ahead for OpenSCAD hull and Minkowski requests?

Post by IPowIPi »

Tried it with this 0.20 build: FreeCAD_0.20.25306_Win-LPv12.5.4_vc17.x-x86-64
Haven't built it myself from master, just took the weekly ci-build.

Good finding that it works with the alternative importer!
Here part of the original thing I was actually working on which also doesn't import with the alternative importer:

Code: Select all

width_bottom = 40;
height_bottom = 40;
width_top = 30;
height_top = 30;
border_width = 3;
border_height = 3;
roundness = 15;
length = 1000;
num_pipes = 4;
wall_thickness = 10;
round_corners = true;

full_width_bottom = width_bottom * num_pipes + wall_thickness * (num_pipes + 1);
full_width_top = width_top * num_pipes + wall_thickness * (num_pipes + 1);
full_height_bottom = height_bottom + wall_thickness + border_height;
full_height_top = height_top + wall_thickness + border_height;

module rect(width, height) {
    translate([-width / 2, -height / 2])
            cube([width, height, 1]);
}

module sphereRect(width, height) {
    if(round_corners) {
        translate([-width / 2 + roundness, -height / 2 + roundness])
            sphere(roundness);
        translate([width / 2 - roundness, -height / 2 + roundness])
            sphere(roundness);
        translate([width / 2 - roundness, height / 2 - roundness])
            sphere(roundness);
        translate([-width / 2 + roundness, height / 2 - roundness])
            sphere(roundness); 
    } else {
        rect(width, height);
    }
}

module pipeCarving(index) {
    // pipe
    hull() {
        rotate([90, 0, 90]) {
            translate([-full_width_bottom / 2 + wall_thickness + width_bottom / 2 + (width_bottom + wall_thickness) * index, (wall_thickness - border_height) / 2, -roundness * 2 - 1])
                sphereRect(width_bottom, height_bottom);
            translate([(-full_width_top / 2 + wall_thickness + width_top / 2 + (width_top + wall_thickness) * index), (wall_thickness - border_height) / 2, length - wall_thickness])
                sphereRect(width_top, height_top);
        }
    }
    // border
    hull() {
        rotate([90, 0, 90]) {
            translate([-full_width_bottom / 2 + wall_thickness - border_width + (width_bottom + border_width * 2) / 2 + (width_bottom + wall_thickness) * index, full_height_bottom / 2, -roundness * 2 - 1])
                rect(width_bottom + 2 * border_width, 2 * border_height + 1);
            translate([(-full_width_top / 2 + wall_thickness - border_width + (width_top + border_width * 2) / 2 + (width_top + wall_thickness) * index), full_height_top / 2, length - wall_thickness + border_width])
                rect(width_top + 2 * border_width, 2 * border_height + 1);
        }
    }
}


module body() {
    hull() {
        rotate([90, 0, 90]) {
            sphereRect(full_width_bottom, full_height_bottom);
            translate([0, 0, length])
                sphereRect(full_width_top, full_height_top);
        }
    }
}

difference() {
    body();

    for(i = [0 : num_pipes - 1])
        pipeCarving(i);
}


keithsloan52
Posts: 2089
Joined: Mon Feb 27, 2012 5:31 pm

Re: Discussion - Possible way ahead for OpenSCAD hull and Minkowski requests?

Post by keithsloan52 »

Your code
Hullproblem.scad
(2.6 KiB) Downloaded 13 times
Hullproblem.csg
(9.77 KiB) Downloaded 10 times
is quite complex in that it takes OpenSCAD some time to render.
On import, If one looks at the messages in FreeCAD's ReportView then one sees a lot of messages like

Code: Select all

07:26:04  hull function
07:26:04  Part::Fuse / Matrix_Union008: Links go out of the allowed scope
07:26:04  Hull Object Group : [<Part::PartFeature>]
As it is, it is a big ask to even understand what is going on let alone debug, could you create a test case that just produced one Part::Fuse out of scope message. Wonder : Are you trying to use overlapping spheres in hull requests? Maybe a single test case.
IPowIPi
Posts: 31
Joined: Sun Jul 25, 2021 9:37 am

Re: Discussion - Possible way ahead for OpenSCAD hull and Minkowski requests?

Post by IPowIPi »

Will try. Does anybody know what kind of problem "Part::Fuse / Matrix_Union008: Links go out of the allowed scope" is, so I know what to look for?
chrisb
Posts: 37790
Joined: Tue Mar 17, 2015 9:14 am

Re: Discussion - Possible way ahead for OpenSCAD hull and Minkowski requests?

Post by chrisb »

This happens if you make references across the Body border, either from inside out, e.g. by using in a sketch an external reference to an object outside of the body, or by using a feature from insode of a body in an operation outside, e.g. by using a Pad in a boolean operation.
A Sketcher Lecture with in-depth information is available in English, auf Deutsch, en français, en español.
keithsloan52
Posts: 2089
Joined: Mon Feb 27, 2012 5:31 pm

Re: Discussion - Possible way ahead for OpenSCAD hull and Minkowski requests?

Post by keithsloan52 »

Just a guess but think it might have something to do with have the importer handles OpenSCAD group requests/statements.

If I look at the CSG file ( That is what the importer deals with ) then there statements like

Code: Select all

hull() {
				multmatrix([[0, 0, 1, 0], [1, 0, 0, 0], [0, 1, 0, 0], [0, 0, 0, 1]]) {
					multmatrix([[1, 0, 0, -75], [0, 1, 0, 26.5], [0, 0, 1, -31], [0, 0, 0, 1]]) {
						group() {
							multmatrix([[1, 0, 0, -23], [0, 1, 0, -3.5], [0, 0, 1, 0], [0, 0, 0, 1]]) {
								cube(size = [46, 7, 1], center = false);
							}
						}
					}
					multmatrix([[1, 0, 0, -60], [0, 1, 0, 21.5], [0, 0, 1, 993], [0, 0, 0, 1]]) {
						group() {
							multmatrix([[1, 0, 0, -18], [0, 1, 0, -3.5], [0, 0, 1, 0], [0, 0, 0, 1]]) {
								cube(size = [36, 7, 1], center = false);
							}
						}
					}
				}
			}
which has a group with just a single object and others like

Code: Select all

hull() {
				multmatrix([[0, 0, 1, 0], [1, 0, 0, 0], [0, 1, 0, 0], [0, 0, 0, 1]]) {
					multmatrix([[1, 0, 0, -25], [0, 1, 0, 3.5], [0, 0, 1, -31], [0, 0, 0, 1]]) {
						group() {
							group() {
								multmatrix([[1, 0, 0, -5], [0, 1, 0, -5], [0, 0, 1, 0], [0, 0, 0, 1]]) {
									sphere($fn = 0, $fa = 12, $fs = 2, r = 15);
								}
								multmatrix([[1, 0, 0, 5], [0, 1, 0, -5], [0, 0, 1, 0], [0, 0, 0, 1]]) {
									sphere($fn = 0, $fa = 12, $fs = 2, r = 15);
								}
								multmatrix([[1, 0, 0, 5], [0, 1, 0, 5], [0, 0, 1, 0], [0, 0, 0, 1]]) {
									sphere($fn = 0, $fa = 12, $fs = 2, r = 15);
								}
								multmatrix([[1, 0, 0, -5], [0, 1, 0, 5], [0, 0, 1, 0], [0, 0, 0, 1]]) {
									sphere($fn = 0, $fa = 12, $fs = 2, r = 15);
								}
							}
						}
					}
					multmatrix([[1, 0, 0, -20], [0, 1, 0, 3.5], [0, 0, 1, 990], [0, 0, 0, 1]]) {
						group() {
							group() {
								multmatrix([[1, 0, 0, 0], [0, 1, 0, 0], [0, 0, 1, 0], [0, 0, 0, 1]]) {
									sphere($fn = 0, $fa = 12, $fs = 2, r = 15);
								}
								multmatrix([[1, 0, 0, 0], [0, 1, 0, 0], [0, 0, 1, 0], [0, 0, 0, 1]]) {
									sphere($fn = 0, $fa = 12, $fs = 2, r = 15);
								}
								multmatrix([[1, 0, 0, 0], [0, 1, 0, 0], [0, 0, 1, 0], [0, 0, 0, 1]]) {
									sphere($fn = 0, $fa = 12, $fs = 2, r = 15);
								}
								multmatrix([[1, 0, 0, 0], [0, 1, 0, 0], [0, 0, 1, 0], [0, 0, 0, 1]]) {
									sphere($fn = 0, $fa = 12, $fs = 2, r = 15);
								}
							}
						}
					}
				}
Which have a group of a group's.

A group will cause a Fuse request.
IPowIPi
Posts: 31
Joined: Sun Jul 25, 2021 9:37 am

Re: Discussion - Possible way ahead for OpenSCAD hull and Minkowski requests?

Post by IPowIPi »

Ok, I drilled it down to this:

Doesn't import (fails with one instance of the error message "Part::Fuse / Matrix_Union: Links go out of the allowed scope"):

hull() {
rotate([90, 0, 90]) {
cube([60, 53, 1]);
translate([0, 0, 1000]) {
cube([50, 43, 1]);
}
}
}


Works (with alternative importer):

hull() {
//rotate([90, 0, 90]) {
cube([60, 53, 1]);
translate([0, 0, 1000]) {
cube([50, 43, 1]);
}
//}
}


Edit: When removing all rotate lines (so the pipes stand upwards) then the alternative importer even imports the complex example from above correctly (on first sight). The model is still triangulated, but at least it imports. (This renders my initial endeavor of getting a STEP file with round shapes a little moot, might have to find a solution without hull then - not easy, will have to investigate)

Edit2: Interestingly this works:

rotate([90, 0, 90]) {
hull() {
cube([60, 53, 1]);
translate([0, 0, 1000]) {
cube([50, 43, 1]);
}
}
}
keithsloan52
Posts: 2089
Joined: Mon Feb 27, 2012 5:31 pm

Re: Discussion - Possible way ahead for OpenSCAD hull and Minkowski requests?

Post by keithsloan52 »

IPowIPi wrote: Fri Jul 30, 2021 2:06 pm The model is still triangulated, but at least it imports. (This renders my initial endeavour of getting a STEP file with round shapes a little moot, might have to find a solution without hull then - not easy, will have to investigate)
Whilst it is possible to hull mesh objects, I don't think it is possible to have a generic hull algorithm for Brep Shapes ( Same goes for minkowski requests) which is why the standard importer when it encounters a hull request, meshes the objects on the stack i.e the objects to be hulled,
calls the openscad modules to perform the hull request and pass back the result, which of course is meshed. OpenSCAD only deals with
mesh/triangulated objects.

The alternate importer checks for certain shapes and conditions and in some circumstances it is able to create a Brep shape.
It should for example handle two spheres, in theory it could handle more than two but it is more complicated to program.
The plan is to over time to expand the situations where it can handle things to create a Brep shape, at present the number of situations
is very limited and it will never be able to get to the situation of handling more than a minor number. If the alternate importer
cannot find one of the conditions it can handle, it goes down the same route as the standard importer i.e. mesh the objects on the
stack and call openscad etc etc
IPowIPi
Posts: 31
Joined: Sun Jul 25, 2021 9:37 am

Re: Discussion - Possible way ahead for OpenSCAD hull and Minkowski requests?

Post by IPowIPi »

Thanks for the feedback! The convex hull should theoretically be uniquely defined for all imaginable shapes, but no clue how to calculate this efficiently in the general case without approximations.
Will have to think about how I best tackle my model. Staying with OpenSCAD and outputting high res-enough STL for CAM, returning to CadQuery, using FreeCAD (even though some of the parametric stuff in there might get tricky), just dropping parametric for the moment and doing a few iterations from scratch with MoI, FreeCAD or Blender. Hmmm...
keithsloan52
Posts: 2089
Joined: Mon Feb 27, 2012 5:31 pm

Re: Discussion - Possible way ahead for OpenSCAD hull and Minkowski requests?

Post by keithsloan52 »

IPowIPi wrote: Fri Jul 30, 2021 5:17 pm The convex hull should theoretically be uniquely defined for all imaginable shapes, but no clue how to calculate this efficiently in the general case without approximations.
Well, consider something not so complicated like a hull of sphere and a cube. You have to determine various tangents and you would need to create various surfaces, displace/angle the cube from a line between their centres and even more difficult, somewhat challenging don't you think.

I think a more general approach would be to mesh all objects, perform a hull on the meshed objects, then surface fit the mesh, nice GPU application.
keithsloan52
Posts: 2089
Joined: Mon Feb 27, 2012 5:31 pm

Re: Discussion - Possible way ahead for OpenSCAD hull and Minkowski requests?

Post by keithsloan52 »

IPowIPi wrote: Fri Jul 30, 2021 2:06 pm Ok, I drilled it down to this:

Doesn't import (fails with one instance of the error message "Part::Fuse / Matrix_Union: Links go out of the allowed scope"):

hull() {
rotate([90, 0, 90]) {
cube([60, 53, 1]);
translate([0, 0, 1000]) {
cube([50, 43, 1]);
}
}
}


Works (with alternative importer):

hull() {
//rotate([90, 0, 90]) {
cube([60, 53, 1]);
translate([0, 0, 1000]) {
cube([50, 43, 1]);
}
//}
}
Found the problem looking at the CSG file ( both have the same problem )

Code: Select all

hull() {
    multmatrix([[0, 0, 1, 0], [1, 0, 0, 0], [0, 1, 0, 0], [0, 0, 0, 1]]) {	
		multmatrix([[1, 0, 0, -75], [0, 1, 0, 26.5], [0, 0, 1, -31], [0, 0, 0, 1]]) {
			group() {
				multmatrix([[1, 0, 0, -23], [0, 1, 0, -3.5], [0, 0, 1, 0], [0, 0, 0, 1]]) {
					cube(size = [46, 7, 1], center = false);
				}
			}
		}
		multmatrix([[1, 0, 0, -60], [0, 1, 0, 21.5], [0, 0, 1, 993], [0, 0, 0, 1]]) {
			group() {
				multmatrix([[1, 0, 0, -18], [0, 1, 0, -3.5], [0, 0, 1, 0], [0, 0, 0, 1]]) {
					cube(size = [36, 7, 1], center = false);
				}
			}
		}
	}
}
At the time of the hull request there is only one object on the stack, the multmatrix([[0, 0, 1, 0], [1, 0, 0, 0], [0, 1, 0, 0], [0, 0, 0, 1]]) {...}
and when it was parsed the other two multmatrix got fuse'd into one object.

A Rotation or Translation will result in a multmatrix statement in the CSG file.
which explains your test cases that worked and failed.

Going to have to think about this one.
Post Reply