[Feature Request] Add a way to get the max possible fillet

[qwelyt]

Often times you run into the problem of trying to fillet a thing (sketch, workplane, etc) but you set a too high fillet. You then have the "fun" journey of trying to figure out how much of a fillet you can actually do on your thing. Sometimes it's easy to figure out, other times it is just a pain and a lot of guess work.

Request: Add a built in function that finds the largest possible fillet given a provided acceptable range, or throw error if non can be found (like now).

We had this discussion over at the discord server. (tagging @gumyr and @dcowden as requested, and here is the start of the discussion https://discord.com/channels/964330484911972403/964330484911972406/968844115917824030 ) A function was devised by the good gumyr ( https://discord.com/channels/964330484911972403/964330484911972406/968869046332321822 )

import cadquery as cq
from OCP.StdFail import StdFail_NotDone

test_object1 = (
    cq.Workplane("XY")
    .rect(10, 8)
    .extrude(2)
    .faces(">Z")
    .workplane()
    .rect(8, 6)
    .extrude(1)
)
test_object2 = cq.Workplane("XY").rect(10, 8).extrude(2)
test_object3 = (
    cq.Workplane("XY").polygon(6, 10).workplane(offset=10).polygon(6, 6).loft()
)


def max_fillet(
    object: cq.Workplane,
    window_min: float = 0.0,
    window_max: float = None,
    tolerance=0.1,
) -> float:
    """Recurisely find the largest fillet value that doesn't fail"""
    if window_max is None:
        window_max = object.largestDimension()
    window_mid = (window_min + window_max) / 2
    print(f"{window_min=},{window_mid=},{window_max=}")

    # Do these numbers work - if not try with the smaller window
    try:
        object.edges().fillet(window_mid)
    except StdFail_NotDone:
        return max_fillet(object, window_min, window_mid, tolerance)
    else:
        if not object.edges().fillet(window_mid).val().isValid():
            return max_fillet(object, window_min, window_mid, tolerance)

    # These numbers work, are they close enough - if not try larger window
    if window_mid - window_min <= tolerance:
        return window_mid
    else:
        return max_fillet(object, window_mid, window_max, tolerance)


max_fillet_1 = max_fillet(test_object1)
max_test1 = test_object1.edges().fillet(max_fillet_1)
max_fillet_2 = max_fillet(test_object2)
max_test2 = test_object2.edges().fillet(max_fillet_2)
max_fillet_3 = max_fillet(test_object3)
max_test3 = test_object3.edges().fillet(max_fillet_3)

With perhaps an improvement ( https://discord.com/channels/964330484911972403/964330484911972406/968871675439493200 )

    try:
        trial = object.edges().fillet(window_mid)
    except StdFail_NotDone:
        return max_fillet(object, window_min, window_mid, tolerance)
    else:
        if not trial.val().isValid():
            return max_fillet(object, window_min, window_mid, tolerance)

So, please implement the given solution as a built in function. I'm sure it will save a lot of people a lot of time and pain.

[dcowden]

I definitely like the idea of adding this to core. @gumyr would you be willing to contribute your code that was mostly finished? I guess the main question is where it would belong. It's a little weird because its a purely stateless function, so it doesnt feel right as a workplane method. perhaps a method on Shape? @jmwright @adam-urbanczyk any thoughts?

[gumyr]

I could make versions for the Shape and Workplane (using Shape) classes if there is agreement on this feature. Cheers, Roger

…

On Wed, Apr 27, 2022 at 3:10 PM thebluedirt ***@***.***> wrote: I definitely like the idea of adding this to core. @gumyr <https://github.com/gumyr> would you be willing to contribute your code that was mostly finished? I guess the main question is where it would belong. It's a little weird because its a purely stateless function, so it doesnt feel right as a workplane method. perhaps a method on Shape? @jmwright <https://github.com/jmwright> @adam-urbanczyk <https://github.com/adam-urbanczyk> any thoughts? — Reply to this email directly, view it on GitHub <#1067 (comment)>, or unsubscribe <https://github.com/notifications/unsubscribe-auth/AUNL25SSM4PWXBX36F4PCVTVHGGKLANCNFSM5UQBP4IQ> . You are receiving this because you were mentioned.Message ID: ***@***.***>

[adam-urbanczyk]

I definitely like the idea of adding this to core. @gumyr would you be willing to contribute your code that was mostly finished? I guess the main question is where it would belong. It's a little weird because its a purely stateless function, so it doesnt feel right as a workplane method. perhaps a method on Shape? @jmwright @adam-urbanczyk any thoughts?

If you want to add it, I'd say Shape is where it belongs.

[gumyr]

How is this?

from typing import Iterable
from cadquery import Shape, Edge, Workplane, Solid
from OCP.StdFail import StdFail_NotDone


def _maxFillet(
    self: Shape,
    edgeList: Iterable[Edge],
    tolerance=0.1,
    maxIterations: int = 10,
    _window_min: float = 0.0,
    _window_max: float = None,
    _current_iteration: int = 0,
) -> float:
    """Find Maximum Fillet Size

    Find the largest fillet radius for the given Shape and Edges with a
    recursive binary search.

    :param edgeList: a list of Edge objects, which must belong to this solid
    :param tolerance: maximum error from actual value
    :param maxIterations: maximum number of recursive iterations
    :return: maximum fillet radius
    :raises: ValueError, RuntimeError

    As an example:
        max_fillet_radius = my_shape.maxFillet(shape_edges)
    or:
        max_fillet_radius = my_shape.maxFillet(shape_edges, tolerance=0.5, maxIterations=8)

    Users of this method must not provide values for: _window_min, _window_max,
    or _current_iteration.

    """
    # If this the first iteration, setup window and validate shape
    if _window_max is None:
        _window_max = 2 * self.BoundingBox().DiagonalLength
        if not self.isValid():
            raise ValueError("Invalid Shape")

    window_mid = (_window_min + _window_max) / 2

    if _current_iteration == maxIterations:
        raise RuntimeError(
            f"Failed to find the max value within {tolerance} in {maxIterations}"
        )

    # Do these numbers work? - if not try with the smaller window
    try:
        if not self.fillet(window_mid, edgeList).isValid():
            raise StdFail_NotDone
    except StdFail_NotDone:
        return self.maxFillet(
            edgeList,
            tolerance,
            maxIterations,
            _window_min,
            window_mid,
            _current_iteration + 1,
        )

    # These numbers work, are they close enough? - if not try larger window
    if window_mid - _window_min <= tolerance:
        return window_mid
    else:
        return self.maxFillet(
            edgeList,
            tolerance,
            maxIterations,
            window_mid,
            _window_max,
            _current_iteration + 1,
        )


Shape.maxFillet = _maxFillet

""" Tests """
test_solids = [Solid.makeBox(10, 8, 2), Solid.makeCone(5, 3, 8)]
test_workplanes = [
    Workplane("XY").box(10, 8, 2).box(8, 6, 4, combine=True),
    Workplane("XY").box(10, 8, 2),
    Workplane("XY").polygon(6, 10).workplane(offset=10).polygon(6, 6).loft(),
]
test_workplane_edge_selectors = ["", ">Z", ""]

for i, test_object in enumerate(test_solids):
    max_fillet_radius = test_object.maxFillet(test_object.Edges())
    filleted_object = test_object.fillet(max_fillet_radius, test_object.Edges())
    log(f"Is test object {i} valid: {filleted_object.isValid()}")
    log(f"{max_fillet_radius=}")
    show_object(test_object, name="solid_object" + str(i), options={"alpha": 0.8})
    show_object(filleted_object, name="solid_filleted_object" + str(i))

for i, test_object in enumerate(test_workplanes):
    edges_to_fillet = test_object.edges(test_workplane_edge_selectors[i]).vals()
    max_fillet_radius = test_object.val().maxFillet(edges_to_fillet)
    filleted_object = test_object.edges(test_workplane_edge_selectors[i]).fillet(
        max_fillet_radius
    )
    log(f"Is test object {i} valid: {filleted_object.val().isValid()}")
    log(f"{max_fillet_radius=}")
    show_object(test_object, name="workplane_object" + str(i), options={"alpha": 0.8})
    show_object(filleted_object, name="workplane_filleted_object" + str(i))

It's strange to have parameters that the user can't use - hopefully I've made that clear enough in the docstring. The tolerance could also be a fraction of the largest dimension which would maybe be a little more appropriate to all sized objects but different than any other use of tolerance that I know of.

[qwelyt]

I'm testing this on my project, and so far this seems to be exactly what I'm looking for.

About the code though. Personally, I really don't like having variables in a method that you shouldn't touch. It's asking for trouble. So I would suggest either of two things:

1. Let the user specify min and max. You get provided a lower value and a max value that is the upper limit for how far you should try. Both are nice to reduce the amount of work the user is willing to let the method do. If I only accept a fillet between 0.5 and 0.7, why should you calculate from 0 to INF?
2. Don't put the iteration in a public method. Make a public method that takes in all the paramn, let the public method call a private recursive method. The private method can have all the dirty params it wants. It's not meant for the outside anyway.

Like I said, I'm testing this on my project and it seems to work quite nicely. Had to up the number of iterations it can run but it seems to work correctly. Some results from my testing, though you don't know how the shape looks but it's a tapered cube with a sphereical cut at the top (keycaps). So complex-ish.

Row 1 , width 1 :    4.074580547705031
Row 1 , width 1.25 :    4.030910857530186
Row 1 , width 1.5 :    3.9999153729695696
Row 1 , width 1.75 :    3.978077782208352
Row 1 , width 2 :    3.961870057544239
Row 1 , width 2.25 :    3.949874741168877
Row 1 , width 2.5 :    3.9418478107719053
Row 1 , width 2.75 :    3.9346547061693906
Row 1 , width 3 :    3.9301502952729086
Row 1 , width 6.25 :    0.2278825994498276
Row 1 , width 7 :    0.31991586881297207
Row 2 , width 1 :    3.344338955788069
Row 2 , width 1.25 :    3.3270135785694395
Row 2 , width 1.5 :    3.314159842299097
Row 2 , width 1.75 :    3.305213304304208
Row 2 , width 2 :    3.2986502564085427
Row 2 , width 2.25 :    3.294165191260456
Row 2 , width 2.5 :    0.02711696168006375
Row 2 , width 2.75 :    0.13139326091820608
Row 2 , width 3 :    0.23630311738785073
Row 2 , width 6.25 :    1.3883437645806946
Row 2 , width 7 :    1.5913822681448968
Row 3 , width 1 :    3.1986795895743194
Row 3 , width 1.25 :    3.1719376206035195
Row 3 , width 1.5 :    3.152754766359381
Row 3 , width 1.75 :    3.140144278011375
Row 3 , width 2 :    3.1306830938649766
Row 3 , width 2.25 :    3.124197713982455
Row 3 , width 2.5 :    3.119954655859871
Row 3 , width 2.75 :    3.11632371846091
Row 3 , width 3 :    3.1134784037611762
Row 3 , width 6.25 :    3.102965410960199
Row 3 , width 7 :    3.1020380702899746
Row 4 , width 1 :    3.154491525189161
Row 4 , width 1.25 :    3.1125883423583987
Row 4 , width 1.5 :    3.082607151164352
Row 4 , width 1.75 :    3.0615182905465392
Row 4 , width 2 :    3.046674773133753
Row 4 , width 2.25 :    0.14147293417296583
Row 4 , width 2.5 :    0.28169854697677954
Row 4 , width 2.75 :    0.3550849026617422
Row 4 , width 3 :    0.5288356884707456
Row 4 , width 6.25 :    1.6687799801504828
Row 4 , width 7 :    1.841897593340013

All these values seems to be correct. And giving me a lot more to work with!

[gumyr]

Here is the version with the recursion private - not only does it not expose the variables that we didn't want the user to see, I think it puts less on the stack which should help to avoid overflows:

def _maxFillet(
    self: Shape,
    edgeList: Iterable[Edge],
    tolerance=0.1,
    maxIterations: int = 10,
) -> float:
    """Find Maximum Fillet Size

    Find the largest fillet radius for the given Shape and Edges with a
    recursive binary search.

    :param edgeList: a list of Edge objects, which must belong to this solid
    :param tolerance: maximum error from actual value
    :param maxIterations: maximum number of recursive iterations
    :return: maximum fillet radius
    :raises: ValueError, RuntimeError

    As an example:
        max_fillet_radius = my_shape.maxFillet(shape_edges)
    or:
        max_fillet_radius = my_shape.maxFillet(shape_edges, tolerance=0.5, maxIterations=8)

    """

    def __maxFillet(window_min: float, window_max: float, current_iteration: int):
        window_mid = (window_min + window_max) / 2

        if current_iteration == maxIterations:
            raise RuntimeError(
                f"Failed to find the max value within {tolerance} in {maxIterations}"
            )

        # Do these numbers work? - if not try with the smaller window
        try:
            if not self.fillet(window_mid, edgeList).isValid():
                raise StdFail_NotDone
        except StdFail_NotDone:
            return __maxFillet(window_min, window_mid, current_iteration + 1)

        # These numbers work, are they close enough? - if not try larger window
        if window_mid - window_min <= tolerance:
            return window_mid
        else:
            return __maxFillet(window_mid, window_max, current_iteration + 1)

    if not self.isValid():
        raise ValueError("Invalid Shape")
    max_radius = __maxFillet(0.0, 2 * self.BoundingBox().DiagonalLength, 0)

    return max_radius

Should the default maxIterations be set higher than 10?

When I get the go ahead I'll open a PR.

[dcowden]

I think 10 is good!

[qwelyt]

Regarding the stack and recursion. Why not get rid of it?

def _maxFillet(
        self: cq.Shape,
        edgeList: Iterable[cq.Edge],
        tolerance=0.1,
        maxIterations: int = 10,
) -> float:
    if not self.isValid():
        raise ValueError("Invalid Shape")
    window_max = 2 * self.BoundingBox().DiagonalLength
    window_min = 0
    for i in range(maxIterations):
        window_mid = (window_min + window_max) / 2
        try:
            if not self.fillet(window_mid, edgeList).isValid():
                raise StdFail_NotDone
        except StdFail_NotDone:
            window_max = window_mid
            continue

        if window_mid - window_min <= tolerance:
            return window_mid
        else:
            window_min = window_mid

    raise RuntimeError(
        f"Failed to find the max value within {tolerance} in {maxIterations},"
    )

Unless I'm missing something this does the same thing but we get rid of the possibility of a stack overflow if the user reeeeally wants to find the max and put in 10000000 iterations.

The downside is ofc mutating variables with the recursion avoids.

[gumyr]

Shape.maxFillet is now a cq_warehouse feature (see https://cq-warehouse.readthedocs.io/en/latest/extensions.html#extensions_doc.Shape.maxFillet) until it gets integrated into cadquery core.