OpenSCAD Examples sped up by fast-csg feature

README.md

Here are some micro benchmarks that demonstrate big gains of OpenSCAD rendering with --enable=fast-csg (a feature I developed in this pull request).

Note: some (but not all) models making heavy use of minkowski may be slower with the feature enabled, as CGALUtils::applyMinkowski is forcing conversions to the old nef format. I hope to address that + publish benchmarks involving minkowski operations soon!*

Note2: these figures need updating, lots of changes since last time I tested these files! Most notably, I'm now proactively falling back to Nef computations in many cases that could have been handled by fast PMP operations on surface meshes, just by fear of hitting corner cases that might corrupt the data. Makes things slower :-(

• uncacheable-grid.scad (see below): 35sec -> 1.5sec (31x faster)
• chainmail.scad (see below): 24min 15sec -> 4min 27sec (5x faster)
• spheres_nested_for_loops.scad (see below): 44sec -> 0.42sec (104x faster)
• spheres_single_for_loop.scad (see below): 48sec -> 0.33sec (146x faster)
• cube-with-half-spheres-dents.scad (see below): 3min 32sec -> 1.2sec (178x faster)
• spheres-grid.scad (see below): 188sec -> 1.1sec (170x faster)
• spheres-grid.scad -Doverlap=true (see below): 206sec -> 2.2sec (93x faster)
• scalemail.scad -Duse_sweep=true: 39sec -> 1.5sec (27x faster)
• Bricks benchmark: 61sec -> 0.6s (108x faster)
• maze.scad: ? (more than 10 hours) -> 5min15 (!)
• testdata/scad/issues/issue2342.scad: 3hours 30min -> 17min 26sec (12x faster); Note that lazy-union does better here, but this is a weird test anyway.
• menger.scad: todo
• Cyclone.scad: todo

Note that in almost all these examples, lazy-union makes things slower when combined with fast-csg (tested combinations of features, see results here)

To reproduce these figures / test your own files:

• Get OpenSCAD w/ the fast-csg feature (in the GUI, enable fast-csg from the settings; in command line just add --enable=fast-csg): two options:
  • Download a prebuilt image from openscad/openscad#3641 (see continuous integration, e.g. Linux AppImage, Windows 32bits or Windows 64bits)
  • Build from sources: see full instructions here, but you'll need to clone my repo and use the right branch to get the feature, which is under review:

    git clone https://github.com/ochafik/openscad ochafik-openscad
    cd openscad-ochafik
    git checkout fast-csg-exact-callbacks
    

• Clone this gist and a couple of helper repositories, set the OPENSCAD environment variable to the executable with fast-csg support and run the benchmarks script:

  export OPENSCAD=$PWD/OpenSCAD.app/Contents/MacOS/OpenSCAD
  # export OPENSCAD=$PWD/openscad
  
  git clone https://github.com/openscad/scad-utils
  git clone https://github.com/openscad/list-comprehension-demos
  # Allows importing sweep.scad
  export OPENSCADPATH=$PWD:$OPENSCADPATH
  
  git clone https://gist.github.com/ochafik/2db96400e3c1f73558fcede990b8a355 openscad-fast-csg-benchmarks
  cd openscad-fast-csg-benchmarks
  ./benchmark.sh $OPENSCAD local *.scad
  

• Note that 4 benchmarks are run in parallel so make sure you have a fast hard drive and cores to spare. You can run the benchmark multiple times to get less noisy data.
• You'll get a benchmark_results/benchmark_results.tsv file you can import in any spreadsheet software to do stats over the various runs (example here), and a benchmark_results/output folder with full logs + output STL files to inspect visually)

Please report any success / failures on the PR!

benchmark.sh

#!/bin/bash
# Copyright 2021 Google LLC.
# SPDX-License-Identifier: Apache-2.0
#
# Usage:
#   ./benchmark.sh openscad-binary binary-name <scad files...>
#
# Example:
#   export OPENSCAD=$PWD/../openscad/build/OpenSCAD.app/Contents/MacOS/OpenSCAD
#   ./benchmark.sh $OPENSCAD local ../openscad/testdata/scad/issues/issue2342.scad `find ../openscad/examples/ -name '*.scad'` *.scad
#
# TODO(ochafik): Read .json parameter files and expand the test cases accordingly.
# TODO(ochafik): Explore more libraries as possible benchmarks:
#
#   mkdir -p ~/Documents/OpenSCAD/libraries
#   git clone https://github.com/clothbot/ClothBotCreations ~/Documents/OpenSCAD/libraries/ClothBotCreations
#   git clone https://github.com/hyperair/projector-mount ~/Documents/OpenSCAD/libraries/projector-mount
#   git clone https://github.com/ochafik/scad-utils ~/Documents/OpenSCAD/libraries/scad-utils
#   git clone https://github.com/ochafik/list-comprehension-demos ~/Documents/OpenSCAD/libraries/list-comprehension-demos
#   git clone https://github.com/ochafik/miscellaneous-scad ~/Documents/OpenSCAD/libraries/miscellaneous-scad
#   git clone https://github.com/ochafik/Round-Anything ~/Documents/OpenSCAD/libraries/Round-Anything
#   git clone https://github.com/JustinSDK/dotSCAD ~/Documents/OpenSCAD/libraries/dotSCAD
#   git clone https://github.com/nophead/NopSCADlib ~/Documents/OpenSCAD/libraries/NopSCADlib
#   git clone https://github.com/CarlosGS/Cyclone-PCB-Factory ~/Documents/OpenSCAD/libraries/Cyclone-PCB-Factory
#
set -eu

benchmark_results_dir="$PWD/benchmark_results"
lock_dir="$benchmark_results_dir/lock.dir"
stats_file="$benchmark_results_dir/benchmark_results.tsv"
output_dir="$benchmark_results_dir/output"
mkdir -p "$benchmark_results_dir"

bin_path="$1"
bin_name="$2"
shift 2
files=( "$@" )

if [[ -z "$bin_path" || -z "$bin_name" || "${#files[@]}" -eq 0 ]]; then
  echo >&2 "Syntax: bin_path bin_name files..."
  exit 1
fi
if ! "$bin_path" --help >/dev/null 2>&1 ; then
  echo >&2 "$bin_path is not an executable!"
  exit 1
fi

trap 'jobs -p | xargs kill' EXIT

function write_stats() {
  local FeatureSet="$1"
  local File="$2"
  local ExecutionTime="$3"
  local Arguments="$4"
  local Binary="$5"
  local Timestamp=$( gdate '+%Y%m%d-%H%M' )

  while ! mkdir "$lock_dir" ; do
      printf >&2 'Waiting for lock %s to write to %s\n' "$lock_dir" "$stats_file"
      sleep 0.$(( $RANDOM % 100 ))
  done
  trap 'rm -rf "$lock_dir"' 0    # remove directory when script finishes
  # printf >&2 'successfully acquired lock\n'

  if [[ ! -f "$stats_file" ]]; then
    echo -e "FeatureSet\tFile\tExecutionTime\tArguments\tBinary\tTimestamp" > "$stats_file"
  fi
  echo -e "$FeatureSet\t$File\t$ExecutionTime\t$Arguments\t$Binary\t$Timestamp" >> "$stats_file"

  echo >&2 "Updated $stats_file"
  rm -rf "$lock_dir"
}

function run_benchmark() {
  # Allow failures, obvsly
  set +e

  local feature_set_name="$1"
  local arguments="$2"
  shift 2

  local bench_out_dir="$output_dir/$feature_set_name"
  mkdir -p "$bench_out_dir"

  for file in "$@" ; do
    local start_time=$( gdate +%s.%N )
    local filename=$( basename "$file" )
    # local out_file="$bench_out_dir/$filename.png"
    local out_file="$bench_out_dir/$filename.stl"
    local log_file="$bench_out_dir/$filename.log"

    echo "# [$feature_set_name] Running $file..."
    # "$bin_path" $arguments "$file" -o "$out_file" --render=cgal 2>&1 | tee "$log_file"
    "$bin_path" $arguments "$file" -o "$out_file" 2>&1 | tee "$log_file"
    local exit_code=$?
    local elapsed_time=""
    if [[ $exit_code -eq 0 ]]; then
      local end_time=$( gdate +%s.%N )
      elapsed_time=$(echo "$end_time - $start_time" | bc)
    fi
    echo "# [${elapsed_time} sec] $filename --> $out_file"
    echo ""
    write_stats "$feature_set_name" "$file" "$elapsed_time" "$arguments" "$bin_name"
  done
}

has_error=0
for file in "$@" ; do
  if [[ ! -e "$file" ]]; then
    echo >&2 "Error: file not found: $file"
    has_error=1
  fi
done
if [[ $has_error -eq 1 ]] ; then
  exit 1
fi

trap 'kill $(jobs -p)' EXIT

run_benchmark "fast-csg"         "--enable=fast-csg" "$@" &
run_benchmark "fast-csg exact"   "--enable=fast-csg --enable=fast-csg-exact" "$@" &
run_benchmark "fast-csg exactcb" "--enable=fast-csg --enable=fast-csg-exact-callbacks" "$@" &

run_benchmark "baseline" "" "$@" &

wait

chainmail.scad

// Copyright 2021 Google LLC.
// SPDX-License-Identifier: Apache-2.0
//
// This one has local overlaps all over the place, and needs a heuristic to find non-overlapping subsets.
// (that's under development, expect CGAL::hilbert_sort, CGAL::Union_find and hopefully some good benchmarks!)

$fn=20;
step = 0.01; //$preview ? 0.01 : 0.001;
thickness = 0.5;
height = 1;
r1 = 2;
r2 = 3;

N = 5;
stride = r1 + r2;

// Use sweep.scad
use_sweep = false;

function f(t, r1, r2, h, m=4, n=1) =
  let (avgRadius = (r1 + r2) / 2)
  [
    cos(n * t) * (avgRadius + (r2 - r1) / 2 * cos(m * t)),
    sin(n * t) * (avgRadius + (r2 - r1) / 2 * cos(m * t)),
    h * sin(m * t)
  ];

use <list-comprehension-demos/sweep.scad>
use <scad-utils/shapes.scad>
module draw_curve_sweep(p, thickness)
  sweep(circle(thickness / 2), construct_transform_path(p), true);

module draw_curve(p, thickness)
  if (use_sweep)
    draw_curve_sweep(p, thickness);
  else
    for (i=[0:len(p)-2])
        hull() {
            translate(p[i]) sphere(d=thickness);
            translate(p[i+1]) sphere(d=thickness);
        }

module torus_knot() {
  points = [for (t=[0:step:1]) f(t * 360, r1=r1, r2=r2, h=height)];
  draw_curve(points, thickness);
}

translate([-N * stride / 2 + stride / 2, -N * stride / 2 + stride / 2, height + thickness / 2]) {
  for (i=[0:N-1], j=[0:N-1]) translate([i * stride, j * stride,0])
    torus_knot();
}

cube-with-half-spheres-dents.scad

// Copyright 2021 Google LLC.
// SPDX-License-Identifier: Apache-2.0
//
// Context: https://github.com/openscad/openscad/pull/3636
//
// openscad --enable=fast-union cube-with-half-spheres-dents.scad -o cube-with-half-spheres-dents.stl
// Runs in 1min8sec with the feature, 4min25sec without (almost 4x speedup)

N = 5;

difference() {
  translate([-0.5, -0.5, -0.5]) cube([N, N, 0.5]);
  // Explicit union here, as difference isn't optimized yet (only union is).
  union() {
      for (i=[0:N-1], j=[0:N-1])
        translate([i, j, 0])
          sphere(d=(overlap ? 1.1 : 0.9), $fn=50);
  }
}

menger.scad

// Menger Sponge by Hans Loeblich
// From https://gist.github.com/thehans/f2bcf3b7d8d5a49378f71e437fa870d0

// The 3d shape is created by the intersection of 3 orthogonal linear_extruded sierpinski carpets.

//menger(100,3);
//menger_cut(100,3);
//animated_menger(100,3); 
optimized_menger(4);

// Optimized for smaller ASCII STL file sizes.  Object size is scaled so that points fall on whole number coordinates only.
// These file size savings are negligible if you convert to binary STL format anyways (not supported in OpenSCAD, but can be converted after saving)
// This technique is also not applicable to diagonally cut menger sponge
module optimized_menger(n) {
  s=pow(3,n);
  translate([s/2,s/2,s/2]) menger(s,n);
}

// cube cut along diagonal for ease of printing, two prints will form the whole shape
module menger_cut(size, n) {
  difference() {
    rotate([45,atan(1/sqrt(2)),0]) menger(size,n);
    translate([0,0,-size]) cube(size*2, center=true);
  }
}

module menger(s, n) {
  intersection() {
    rotate([ 0,90,0]) translate([0,0,-s/2-1]) linear_extrude(s+2, convexity=pow(2,n)) sierpinski(s,n);
    rotate([90, 0,0]) translate([0,0,-s/2-1]) linear_extrude(s+2, convexity=pow(2,n)) sierpinski(s,n);
    rotate([ 0, 0,0]) translate([0,0,-s/2-1]) linear_extrude(s+2, convexity=pow(2,n)) sierpinski(s,n);
  }
}

module sierpinski(s, n) {
  difference() { 
    square(s, center=true);
    _sierpinski(0,0,s,n);
  }
}

module _sierpinski(x, y, s, n) {
  translate([x,y]) {
    if (n>0) {
      i = n-1;
      scale([1/3,1/3]) {
        square(s, center=true);
        if (i>0) {
          _sierpinski(-s,-s, s, i);
          _sierpinski(-s, 0, s, i);
          _sierpinski(-s, s, s, i);
          _sierpinski( 0,-s, s, i);
          //_sierpinski( 0, 0, s, i);
          _sierpinski( 0, s, s, i);
          _sierpinski( s,-s, s, i);
          _sierpinski( s, 0, s, i);
          _sierpinski( s, s, s, i);
        }
      }
    }
  }
}

module animated_menger(s, n) {
  t0 = get_step_t(0, 6);
  t1 = get_step_t(1, 6);
  t2 = get_step_t(2, 6);
  t3 = get_step_t(3, 6);
  t4 = get_step_t(4, 6);
  t5 = get_step_t(5, 6);

  //echo(t0,t1,t2,t3,t4,t5);

  if (t0 > 0) color([1,0,0,0.8]) scale([1.01,1,0.99]) rotate([ 0,90, 0]) translate([0,0,-3*s/2]) linear_extrude(s*t0, convexity=pow(2,n)) sierpinski(s,n);
  if (t2 > 0) color([0,1,0,0.8]) scale([0.99,1.01,1]) rotate([90, 0, 0]) translate([0,0,-3*s/2]) linear_extrude(s*t2, convexity=pow(2,n)) sierpinski(s,n);
  if (t4 > 0) color([0,0,1,0.8]) scale([1,0.99,1.01]) rotate([ 0, 0, 0]) translate([0,0,-3*s/2]) linear_extrude(s*t4, convexity=pow(2,n)) sierpinski(s,n);

  intersection() {
    if (t1 > 0) color([1,0,0,0.8]) scale([1.01,1,0.99]) rotate([ 0,90, 0]) translate([0,0,-s/2]) linear_extrude(s*t1, convexity=pow(2,n)) sierpinski(s,n);
    if (t3 > 0) color([0,1,0,0.8]) scale([0.99,1.01,1]) rotate([90, 0, 0]) translate([0,0,-s/2]) linear_extrude(s*t3, convexity=pow(2,n)) sierpinski(s,n);
    if (t5 > 0) color([0,0,1,0.8]) scale([1,0.99,1.01]) rotate([ 0, 0, 0]) translate([0,0,-s/2]) linear_extrude(s*t5, convexity=pow(2,n)) sierpinski(s,n);
  }
}

function get_step_t(step, total) = let(t = $t*total - step) min(1,t);

spheres-grid.scad

// Copyright 2021 Google LLC.
// SPDX-License-Identifier: Apache-2.0

N = 5;

// When this is true, we end up with lots of overlaps, which goes in the way of some optimizations but is still very fast with fast-csg
overlap = false;

// A simple grid of smooth spheres
union() {
  for (i=[0:N-1], j=[0:N-1])
    translate([i, j, 0])
      sphere(d=(overlap ? 1.1 : 0.9), $fn=50);
}

spheres_nested_for_loops.scad

// Copyright 2021 Google LLC.
// SPDX-License-Identifier: Apache-2.00

N = 3;
overlap = false;

union() {
  for (i=[0:N-1]) translate([i,0,0])
  for (j=[0:N-1]) translate([0,j,0])
    sphere(d=(overlap ? 1.1 : 0.9), $fn=50);
}

spheres_single_for_loop.scad

// Copyright 2021 Google LLC.
// SPDX-License-Identifier: Apache-2.0

N = 3;
overlap = false;

union() {
  for (i=[0:N-1], j=[0:N-1])
    translate([i,j,0])
      sphere(d=(overlap ? 1.1 : 0.9), $fn=50);
}

uncacheable-grid.scad

// Copyright 2021 Google LLC.
// SPDX-License-Identifier: Apache-2.0

top_transform = true;
top_union = true;
N = 5;
size = 2;
$fn=12;

module grid(N)
{
  for (i=[0:N-1], j=[0:N-1]) translate([i * size, j * size, 0])
  // for (i=[0:N-1]) translate([i * size, 0, 0]) for (j=[0:N-1]) translate([0, j * size, 0])
    {
        sphere(d=1, $fn=16);

        difference() {
            h = 1 + (i + N * j) / pow(N, 2);
            hull() {
              cube(h, center=true);
              cylinder(h / 2 - 0.01, d=h * 1.3);
            }

            cylinder(h, r=0.45);
            translate([0, 0.5, 0])
              cylinder(h, r=0.2);
        }
    }
}

if (top_union)
  union() {
    if (top_transform)
      translate([0, 0, 1])
        grid(N);
    else
      grid(N);
  }
else if (top_transform)
  translate([0, 0, 1])
    grid(N);
else
  grid(N);

Hello @ochafik , thank you for this writeup. I'm curious if you would still recommend checking out your specific branch, given it is a couple of years behind openscad master?

Hi @cysidron1, please use a nightly build of OpenSCAD (look in the downloads page under development version), and fast-csg is now being obsoleted by Manifold (also merged in the main branch: openscad/openscad#4533 )

Oh amazing, that’s so much quicker! Appreciate the prompt response

…

On Sunday, December 17, 2023, Olivier Chafik ***@***.***> wrote: ***@***.**** commented on this gist. ------------------------------ Hi @cysidron1 <https://github.com/cysidron1>, please use a nightly build of OpenSCAD (look in the downloads page under development version), and fast-csg is now being obsoleted by Manifold (also merged in the main branch: openscad/openscad#4533 <openscad/openscad#4533> ) — Reply to this email directly, view it on GitHub <https://gist.github.com/ochafik/2db96400e3c1f73558fcede990b8a355#gistcomment-4796875> or unsubscribe <https://github.com/notifications/unsubscribe-auth/ARWAIXNIGZNI6E2US75HGJDYJ6V7LBFKMF2HI4TJMJ2XIZLTSKBKK5TBNR2WLJDHNFZXJJDOMFWWLK3UNBZGKYLEL52HS4DFQKSXMYLMOVS2I5DSOVS2I3TBNVS3W5DIOJSWCZC7OBQXE5DJMNUXAYLOORPWCY3UNF3GS5DZVRZXKYTKMVRXIX3UPFYGLK2HNFZXIQ3PNVWWK3TUUZ2G64DJMNZZDAVEOR4XAZNEM5UXG5FFOZQWY5LFVEYTANZWGM3DQMRRU52HE2LHM5SXFJTDOJSWC5DF> . You are receiving this email because you were mentioned. Triage notifications on the go with GitHub Mobile for iOS <https://apps.apple.com/app/apple-store/id1477376905?ct=notification-email&mt=8&pt=524675> or Android <https://play.google.com/store/apps/details?id=com.github.android&referrer=utm_campaign%3Dnotification-email%26utm_medium%3Demail%26utm_source%3Dgithub> .