delaunay not working for simple 3D point set.

[Kevin-Mattheus-Moerman]

I'm interested in 3D Delaunay tesselation, by which I mean the tetrahedralisation of points. Is it correct that your package can do this?

I tried your package using the following:

using Quickhull
using GeometryBasics

# Create points on cube for testing
P = Point{3, Float64}[[-1.0, -1.0, -1.0], [-1.0, 1.0, -1.0], [1.0, 1.0, -1.0], [1.0, -1.0, -1.0], [-1.0, -1.0, 1.0], [-1.0, 1.0, 1.0], [1.0, 1.0, 1.0], [1.0, -1.0, 1.0]]

# Convex hull should produce 12-faces ("slashed" quads)
hull = quickhull(P)

# Delaunay tesselation should produce set of tetrahedrons
D = Quickhull.delaunay(P)

The quickhull bit seems to work, but I cannot get the delaunay bit to work, I get:

ERROR: ArgumentError: All the points are coplanar. Try projecting into a lower dimension.
Stacktrace:
 [1] goodsimplex(pts::Quickhull.LiftedPoints{4, Vector{…}, Point{…}, Float64}, I::Type, K::Type, nsamp::Int64)
   @ Quickhull ~/.julia/packages/Quickhull/P8kG6/src/Quickhull.jl:185
 [2] goodsimplex
   @ ~/.julia/packages/Quickhull/P8kG6/src/Quickhull.jl:130 [inlined]
 [3] _quickhull_main(pts::Quickhull.LiftedPoints{…}, opts::Quickhull.Options{…})
   @ Quickhull ~/.julia/packages/Quickhull/P8kG6/src/Quickhull.jl:474
 [4] _quickhull
   @ ~/.julia/packages/Quickhull/P8kG6/src/Quickhull.jl:506 [inlined]
 [5] quickhull
   @ ~/.julia/packages/Quickhull/P8kG6/src/Quickhull.jl:537 [inlined]
 [6] delaunay(pts::Vector{…}, opts::Quickhull.Options{…})
   @ Quickhull ~/.julia/packages/Quickhull/P8kG6/src/delaunay.jl:116
 [7] top-level scope
   @ Untitled-1:11

I also tried:

D = delaunay(P,opts=Quickhull.Options())

Although the documentation says D = delaunay(P, options=Quickhull.Options()), however, both produce this error:

ERROR: MethodError: no method matching delaunay(::Vector{Point{…}}; opts::Quickhull.Options{Quickhull.HyperplaneKernelExactSIMD, Int32, Quickhull.NoSubdivide})
This method may not support any kwargs.

Closest candidates are:
  delaunay(::Any, ::Any) got unsupported keyword argument "opts"
   @ Quickhull ~/.julia/packages/Quickhull/P8kG6/src/delaunay.jl:116
  delaunay(::Any) got unsupported keyword argument "opts"
   @ Quickhull ~/.julia/packages/Quickhull/P8kG6/src/delaunay.jl:116
  delaunay(::Matrix, ::Any) got unsupported keyword argument "opts"
   @ Quickhull ~/.julia/packages/Quickhull/P8kG6/src/delaunay.jl:118
  ...

Stacktrace:
 [1] top-level scope
   @ Untitled-1:11

I've also tested with denser data e.g. featuring a couple thousand points but the code seems to crash Julia entirely.

Any help would be appreciated. Thanks.

[augustt198]

The error message here is a bit unhelpful, but the problem is that all of the points lie on the same sphere (i.e. not in general position). The input can be perturbed to make it work with delaunay(P, Quickhull.Options(joggle=true)).

I'll change the documentation to make it clear that options is an optional argument, not a kwarg.

Could you share the denser data you tested?

[Kevin-Mattheus-Moerman]

@augustt198 thanks for the quick response. I tried your suggestion with the following but it crashes Julia:

using Quickhull
using GeometryBasics

P = Point{3, Float64}[[-1.0, -1.0, -1.0], [-1.0, 1.0, -1.0], [1.0, 1.0, -1.0], [1.0, -1.0, -1.0], [-1.0, -1.0, 1.0], [-1.0, 1.0, 1.0], [1.0, 1.0, 1.0], [1.0, -1.0, 1.0]]
D = delaunay(P, Quickhull.Options(joggle=true))

If I run it in the REPL I can see this text:

[13226] signal 11 (128): Segmentation fault
in expression starting at REPL[4]:1
getproperty at /home/kevin/.julia/packages/Quickhull/P8kG6/src/smallvec.jl:150 [inlined]
iter at /home/kevin/.julia/packages/Quickhull/P8kG6/src/Quickhull.jl:413
_quickhull_main at /home/kevin/.julia/packages/Quickhull/P8kG6/src/Quickhull.jl:489
_quickhull at /home/kevin/.julia/packages/Quickhull/P8kG6/src/Quickhull.jl:506 [inlined]
quickhull at /home/kevin/.julia/packages/Quickhull/P8kG6/src/Quickhull.jl:537 [inlined]
delaunay at /home/kevin/.julia/packages/Quickhull/P8kG6/src/delaunay.jl:116
unknown function (ip: 0x7f4cdc7c5d60)
jl_apply at /cache/build/builder-demeter6-6/julialang/julia-master/src/julia.h:2157 [inlined]
do_call at /cache/build/builder-demeter6-6/julialang/julia-master/src/interpreter.c:126
eval_value at /cache/build/builder-demeter6-6/julialang/julia-master/src/interpreter.c:223
eval_stmt_value at /cache/build/builder-demeter6-6/julialang/julia-master/src/interpreter.c:174 [inlined]
eval_body at /cache/build/builder-demeter6-6/julialang/julia-master/src/interpreter.c:663
jl_interpret_toplevel_thunk at /cache/build/builder-demeter6-6/julialang/julia-master/src/interpreter.c:821
jl_toplevel_eval_flex at /cache/build/builder-demeter6-6/julialang/julia-master/src/toplevel.c:943
jl_toplevel_eval_flex at /cache/build/builder-demeter6-6/julialang/julia-master/src/toplevel.c:886
ijl_toplevel_eval_in at /cache/build/builder-demeter6-6/julialang/julia-master/src/toplevel.c:994
eval at ./boot.jl:430 [inlined]
eval_user_input at /cache/build/builder-demeter6-6/julialang/julia-master/usr/share/julia/stdlib/v1.11/REPL/src/REPL.jl:245
repl_backend_loop at /cache/build/builder-demeter6-6/julialang/julia-master/usr/share/julia/stdlib/v1.11/REPL/src/REPL.jl:342
#start_repl_backend#59 at /cache/build/builder-demeter6-6/julialang/julia-master/usr/share/julia/stdlib/v1.11/REPL/src/REPL.jl:327
start_repl_backend at /cache/build/builder-demeter6-6/julialang/julia-master/usr/share/julia/stdlib/v1.11/REPL/src/REPL.jl:324
#run_repl#72 at /cache/build/builder-demeter6-6/julialang/julia-master/usr/share/julia/stdlib/v1.11/REPL/src/REPL.jl:483
run_repl at /cache/build/builder-demeter6-6/julialang/julia-master/usr/share/julia/stdlib/v1.11/REPL/src/REPL.jl:469
jfptr_run_repl_10088 at /home/kevin/.julia/juliaup/julia-1.11.1+0.x64.linux.gnu/share/julia/compiled/v1.11/REPL/u0gqU_GYsA8.so (unknown line)
#1139 at ./client.jl:446
jfptr_YY.1139_14649 at /home/kevin/.julia/juliaup/julia-1.11.1+0.x64.linux.gnu/share/julia/compiled/v1.11/REPL/u0gqU_GYsA8.so (unknown line)
jl_apply at /cache/build/builder-demeter6-6/julialang/julia-master/src/julia.h:2157 [inlined]
jl_f__call_latest at /cache/build/builder-demeter6-6/julialang/julia-master/src/builtins.c:875
#invokelatest#2 at ./essentials.jl:1055 [inlined]
invokelatest at ./essentials.jl:1052 [inlined]
run_main_repl at ./client.jl:430
repl_main at ./client.jl:567 [inlined]
_start at ./client.jl:541
jfptr__start_72144.1 at /home/kevin/.julia/juliaup/julia-1.11.1+0.x64.linux.gnu/lib/julia/sys.so (unknown line)
jl_apply at /cache/build/builder-demeter6-6/julialang/julia-master/src/julia.h:2157 [inlined]
true_main at /cache/build/builder-demeter6-6/julialang/julia-master/src/jlapi.c:900
jl_repl_entrypoint at /cache/build/builder-demeter6-6/julialang/julia-master/src/jlapi.c:1059
main at /cache/build/builder-demeter6-6/julialang/julia-master/cli/loader_exe.c:58
__libc_start_main at /lib/x86_64-linux-gnu/libc.so.6 (unknown line)
unknown function (ip: 0x4010b8)
Allocations: 18884109 (Pool: 18883536; Big: 573); GC: 15
Segmentation fault (core dumped)

[augustt198]

Thanks for reporting, that's really weird. Base.getfield should always be safe so I don't see what could be segfaulting. Does the same thing happen if you run with julia --check-bounds=yes?

[Kevin-Mattheus-Moerman]

@augustt198 tested it with julia --check-bounds=yes and that did not produce the error.

The error is repeatable across two different computers. I do think it relates to that "All the points are coplanar" thing with the set of points on the cube. If I try it with points that are not on a sphere it seems to be doing fine.

[IlianPihlajamaa]

I had similar issues, where the package segfaults on 3D data (but not on 2D), with julia 1.11. It works with 1.10.5 though. Can you try with Julia 1.10?