A new type of primitive I've made for CSharpCAD, that might be of interest to JSCAD.

[briansturgill]

So these two primitives are what I'm calling a "negative geometry object"... basically it's an object that is created only so that it can be subtracted from another object (yielding a presumably useful object).

(BTW, if you've ever seen a package contain "negative geometry objects" before, I'd love to know about it!)

I created Cutter2D and Cutter 3D. Their function is to remove a "pie slice" from circular/elliptical objects.

One of the few things I like better about OpenSCAD over JSCAD is that it's API is more simple.
Circle for example has those annoying startAngle and endAngle options.
Within JSCAD, the complexity of having Semi and Full circles in the same API has caused problems.

As no one is using CSharpCAD, I can make reasonable changes in the API... and this allows me to simplify all the circular/elliptical APIs, yet still be able for end users to make semi-objects easily.

JSCAD may want to adopt Cutter2D/3D, even if the APIs are not changed as it works with GeodesicSphere, Ellipsoid and Sphere, which don't have semi-versioning in their API. And also on any round compound objects.

Example:

var g = Subtract(Cylinder(height: 10, radius: 5), Cutter3D(radius: 5, angle: 90));

Here's my C# implementation. Remember to translate to radians! (CSharpCAD uses degrees.)

namespace CSharpCAD;

public static partial class CSCAD
{
    /// <summary>Construct a "cutter", a negative geometry object, suitable to cut a "pie slice" out of a circlular 2d object of radius r.</summary>
    /// <remarks>
    /// This object would normally be used as a second argument to "Subtract".
    /// To use with an elliptical object, specify radius as the largest radius of the elliptical.
    /// </remarks>
    /// <param name="radius">Radius that matches the circle you want to cut.</param>
    /// <param name="angle" default="90">Angle formed by the cut (in degrees).</param>
    /// <param name="center" default="(0,0)">Center that coincides with the center of the circular target.</param>
    /// <example>
    /// // Cuts the fourth quadrant of the circle away.
    /// var g = Subtract(Circle(radius: 5), Rotate((0, 0, 90), Cutter2D(radius: 6, angle: 90)));
    /// </example>
    /// <group>2D Primitives</group>
    public static Geom2 Cutter2D(double radius = 1, double angle = 90, Vec2? center = null)
    {
        if (radius <= 0.0) throw new ArgumentException("Radius value must be postive.");
        if (LessThanish(angle, 1)) throw new ArgumentException("Angle must be greater than one.");
        if (GreaterThanish(angle, 360)) throw new ArgumentException("Angle must be less than a full circle.");
        var _center = center ?? new Vec2(0, 0);

        radius = radius * 2 + 1; // Using +1 to make sure we are bigger than the diameter.

        var points = new List<Vec2>(5); // 3 90 degree points, and possibly an end point and a center point
        void addPoint(double x, double y) => points.Add(_center.Add(new Vec2(x, y)));

        if (!Equalish(angle, 180.0)) points.Add(_center); // Can't add addPoint, also, if 180ish then colinear with start and end.

        points.Add(new Vec2(radius * Cos(0), radius * Sin(0)));
        for (var pointAngle = 90.0 ; LessThanish(pointAngle, angle); pointAngle += 90.0)
        {
            addPoint(radius * Cos(pointAngle), radius * Sin(pointAngle));
        }
        addPoint(radius * Cos(angle), radius * Sin(angle));

        var cutter2D = new Geom2(points);
        return cutter2D;
    }

    /// <summary>Construct a "cutter", a negative geometry object, suitable to cut a "pie slice" out of a circlular 3D object of radius r.</summary>
    /// <remarks>
    /// This object would normally be used as a second argument to "Subtract".
    /// To use with an elliptical object, specify radius as the largest radius of the elliptical.
    /// </remarks>
    /// <param name="radius">Radius that matches the circular 3D object you want to cut.</param>
    /// <param name="height" default="radius*2+2">Height that matches the cylinder or other circular 3D object you want to cut.</param>
    /// <param name="angle" default="90">Angle formed by the cut (in degrees).</param>
    /// <param name="center" default="(0,0,0)">Center that coincides with the center of the circular target.</param>
    /// <example>
    /// var g = Subtract(Cylinder(height: 10, radius: 5), Cutter3D(radius: 5, angle: 90));
    /// </example>
    /// <group>3D Primitives</group>
    public static Geom3 Cutter3D(double radius = 1, double? height = null, double angle = 90, Vec3? center = null)
    {
        if (radius <= 0.0) throw new ArgumentException("Radius value must be postive.");
        if (LessThanish(angle, 1)) throw new ArgumentException("Angle must be greater than one.");
        if (GreaterThanish(angle, 360)) throw new ArgumentException("Angle must be less than a full circle.");
        var _center = center ?? new Vec3(0, 0, 0);
        var _height = height ?? radius * 2;

        _height = _height + 2; // Make sure we cut everything.

        var cutter2D = Cutter2D(radius, angle);
        var cutter3D = (Geom3)Translate(new Vec3(_center.X, _center.Y, _center.Z - (_height / 2.0)), ExtrudeLinear(cutter2D, height: _height));
        return cutter3D;
    }
}

[hrgdavor]

var g = Subtract(Circle(radius: 5), Rotate((0, 0, 90), Cutter2D(radius: 6, angle: 90)));

I am curious

• does radius have to be the same, if it can differ, how it affects end-result?
• can there be arbitrary rotation, or it needs to be only on one axis ?

[briansturgill]

Starting
Sphere 32 loops: 1: 83ms
Starting
Sphere 64 loops: 1: 318ms
Starting
Sphere 128 loops: 1: 2782ms

Perhaps the algorithm does need looked at (again, I've done that at least 5 times).
It occurs to me that possibly it's garbage collection related. Generally GC gets ignored in academic algorithm analysis.
I say this because the change in time between 32 and 64 is reasonable.

[briansturgill]

@hrgdavor Well, here's an argument for leaving startAngle/endAngle in CSharpCAD:
Starting
Subtract(Sphere(radius: 10, segments: 128), Cutter3D(radius: 10, angle: 90)); loops: 1: 2444ms
For Spheres, it's your only option, but clearly making Cutter's output small isn't the overriding concern.
Make's me believe even more that the problem is memory management, not algorithm.

[briansturgill]

@hrgdavor No, no, no... I can't believe I didn't spot this immediately, the problem isn't with the algorithm... it's the object chosen.
Sphere by definition is quadrupling the points at each doubling.
Vertex count:
Sphere(32) 1984
Sphere(64) 8064
Sphere(128) 32512

[hrgdavor]

I doubt that gc is culprit in 64 to 128, but if nothing else, it shows that current boolean speed is not logarithmic compared to point count :)

[briansturgill]

@hrgdavor Yes, but you were increasing point count exponentially when you doubled segments. (I.E. in a sphere, doubling segments, quadruples vertices. So, of course, time went up exponentially.)
Here is a paper by Joseph O'Rourke (a well known academic in the area and author of Computation Geometry in C.)
He is claiming an O(n+m) algorithm for the intersection of 2 polygons (n and m the number of vertices in the two polygons).
Intersection algorithms can do union and difference with minor modifications.
https://www.cs.jhu.edu/~misha/Spring16/ORourke82.pdf
He talks about the Shamos O(n*log(n)) which is the algorithm I was referring to above.

If you really believe JSCAD booleans are O(n^2) or worse, then something is very wrong.
I suspected this, but currently believe that things like Math.Hypot was making the "constant" high.
O(n) means linear, but really is a a short hand for C*n+K where C and K are "constants"... but if high, can dominate the algorithm.
(C would refer to operations conducted on each n, K would be things like setup/teardown time.)

[briansturgill]

@hrgdavor Putting this in a new thread.
Here is an intensive test of the Boolean subtract. It will largely hold true for Union and Intersect as well.
I think it shows a real world implementation of an O(n*log(n)) algorithm. As things get truly large, a combination of garbage
collection and cache misses caused by the shear volume of what is going on makes things get slightly worse over time.

Starting
Subtract(CylinderElliptic(startRadius: (10, 10), endRadius: (10, 10), segments: 32), Cutter3D(radius: 10, angle: 90)); loops: 1: 97ms
Starting
Subtract(CylinderElliptic(startRadius: (10, 10), endRadius: (10, 10), segments: 64), Cutter3D(radius: 10, angle: 90)); loops: 1: 1ms
Starting
Subtract(CylinderElliptic(startRadius: (10, 10), endRadius: (10, 10), segments: 128), Cutter3D(radius: 10, angle: 90)); loops: 1: 4ms
Starting
Subtract(CylinderElliptic(startRadius: (10, 10), endRadius: (10, 10), segments: 256), Cutter3D(radius: 10, angle: 90)); loops: 1: 10ms
Starting
Subtract(CylinderElliptic(startRadius: (10, 10), endRadius: (10, 10), segments: 512), Cutter3D(radius: 10, angle: 90)); loops: 1: 34ms
Starting
Subtract(CylinderElliptic(startRadius: (10, 10), endRadius: (10, 10), segments: 1024), Cutter3D(radius: 10, angle: 90)); loops: 1: 107ms
Starting
Subtract(CylinderElliptic(startRadius: (10, 10), endRadius: (10, 10), segments: 2048), Cutter3D(radius: 10, angle: 90)); loops: 1: 305ms
Starting
Subtract(CylinderElliptic(startRadius: (10, 10), endRadius: (10, 10), segments: 4096), Cutter3D(radius: 10, angle: 90)); loops: 1: 914ms
Starting
Subtract(CylinderElliptic(startRadius: (10, 10), endRadius: (10, 10), segments: 8192), Cutter3D(radius: 10, angle: 90)); loops: 1: 2424ms
Starting
Subtract(CylinderElliptic(startRadius: (10, 10), endRadius: (10, 10), segments: 16384), Cutter3D(radius: 10, angle: 90)); loops: 1: 6427ms
Starting
Subtract(CylinderElliptic(startRadius: (10, 10), endRadius: (10, 10), segments: 32768), Cutter3D(radius: 10, angle: 90)); loops: 1: 22192ms
Starting
Subtract(CylinderElliptic(startRadius: (10, 10), endRadius: (10, 10), segments: 65536), Cutter3D(radius: 10, angle: 90)); loops: 1: 84821ms
Starting
Subtract(CylinderElliptic(startRadius: (10, 10), endRadius: (10, 10), segments: 131072), Cutter3D(radius: 10, angle: 90)); loops: 1: 354742ms

As expected Cyllinder Elliptic grows linearly with the number of segments:
CylinderElliptic(32) 320
CylinderElliptic(64) 640
CylinderElliptic(128) 1280
CylinderElliptic(256) 2560
CylinderElliptic(512) 5120
CylinderElliptic(1024) 10240
CylinderElliptic(2048) 20480
CylinderElliptic(4096) 40960
CylinderElliptic(8192) 81920
CylinderElliptic(16384) 163840
CylinderElliptic(32768) 327680
CylinderElliptic(65536) 655360
CylinderElliptic(131072) 1310720

[hrgdavor]

@briansturgill thanks for the extensive tests. It gives a better insight into how booleans scale :)
Also thanks for the link to the paper. My knowledge on computational geometry is bit thin :)

If you have more to share, please do :) :)

My claims were based on experience and was guesswork (it is a big nono to make assumptions about performance) :)

hope I did not waste too much of your time :)

[briansturgill]

No waste of my time at all, I've been meaning to do a more thorough timing test of the booleans anyway. (Nothing like actually checking to see if you understand things correctly.) As to the startAngle/endAngle, I'm still not fully decided what to do. I have some more timing tests to do. I want to see if the presence of the code and the sharing of code between like circle/ellipse have significant effects. I'm sure it does somewhat in JSCAD because of the work you have to do with handling options, though I'm not sure just how significant that is. I also noticed an anomaly where circle + extrude was faster (a lot) than cylinderElliptic. I keep thinking I'm missing something, but at least the output of the two tests matched in prusaslicer. Anyway, as always, if I find anything significant, I'll let JSCAD people know!

[hrgdavor]

Cool, I really like the insights you bring here. Can't wait to free-up some time to do more jscad stuff. Currently all I can manage is comment a bit here and there.