Changed boolean_manifold iteration for improved performance.

[dbukenberger]

Hey Mike,

I was at a point where I had to perform a massive boolean union operation for a lot of small meshes. The incremental way this was implemented became slower and slower with each manifold that was added. Therefore, I've implemented a more binary-reduction-like iteration, going like this: [a, b, c, d, e, f, g] [ab, cd, ef, g] [abcd, efg] [abcdefg]

It still performs the same boolean operation for all objects in the input list, but is drastically more performant - especially if the input list is huge. I have also added a test, verifying that it produces the same result as the original code.

As I was writing this, I realized that it should actually work analogously for the intersection - so I rewrote it too.

Cheers Dennis

[mikedh]

This looks awesome thanks for the PR! I quickly modified it to have the same function signature as functools.reduce to make it easier to check the index logic:

from typing import Callable, Sequence

def cascade(operation: Callable, items: Sequence):
    """
    Call a function in a cascaded pairwise way against a
    flat sequence of items. This should produce the same
    result as `functools.reduce` but may be faster for some
    functions that for example perform only as fast as their
    largest input.

    For example on `a b c d e f g` this function would run and return:
        a b
        c d
        e f
        ab cd
        ef g
        abcd efg
     -> abcdefg

    Where `functools.reduce` would run and return:
        a b
        ab c
        abc d
        abcd e
        abcde f
        abcdef g
     -> abcdefg

    Parameters
    ----------
    operation
      The function to call on pairs of items.
    items
      The flat list of items to apply operation against.
    """
    if len(items) == 0:
        return None

    for _lvl in range(int(1 + np.log2(len(items)))):
        results = []
        for i in np.arange(len(items) // 2) * 2:
            results.append(operation(items[i], items[i + 1]))
            print(items[i], items[i + 1])

        if len(items) % 2:
            results.append(items[-1])

        items = results

    # logic should have reduced to a single item
    assert len(results) == 1

    return results[0]

It's the same number of function calls as the reduce, I totally believe that the complexity of the boolean is proportional to the largest mesh in a pair. It also seems preferable for regular addition as it stays further away from overflowing. Let me know if I screw something up on merging it haha, thanks for the fix!

[mikedh]

This should produce the same result as functools.reduce

This should probably also say "if the operation is commutative (i.e. addition or multiplication.)"