Switch to QHull directly?

[saschatimme]

Hey there,

I use this in one of my packages and this dependency makes a little bit trouble during the installation / first use. On two of my colleagues systems (both Linux) I had to update the scipy version to get this working since Julia choose their global Python toolchain.
To avoid these kinds of problems, maybe we should instead wrap qhull directly? Or do you have other ideas to get the installation process more stable?

[saschatimme]

Okay the scipy bindings to qhull are definitely more involved than I thought, so this is easier said than done 😅

[blegat]

I agree, it would be nice to access qhull directly without scipy. It currently use scipy as it was easier to start with, see this discussion.

[stevengj]

This package calls Qhull directly: https://github.com/gridap/MiniQhull.jl

Maybe it should be merged with or replace Qhull.jl at some point?

[stevengj]

Now that Qhull 8.0.999 has been released on Yggdrasil (JuliaPackaging/Yggdrasil#3657) with the new accessors API (qhull/qhull#89), it should be much easier to call libqhull_r directly (as also discussed in gridap/MiniQhull.jl#5) without requiring a C compiler or building a wrapper (as in https://github.com/JuhaHeiskala/DirectQhull.jl).

My only question is where that development should take place. Here? MiniQhull (cc @fverdugo)? DirectQhull (cc @JuhaHeiskala)?

[JuhaHeiskala]

Hi, well I guess my question would be what development?
How much functionality should be implemented.

Its been some years since I originally implemented DirectQhull, only imported it to Github recently, so my recollection of the details below is a bit hazy.

The DirectQhullHelper wrapper uses slightly different approach to the accessor API, by returning the field offsets of qhT, facetT and vertexT structures. Then that information is used in the Julia side to access the qhull internals as required.
For this approach the functions to return the struct information could be added to the qhull accessor API, if qhull is willing to provide such an API. This method allows to access all the qhull internals and not only the fields that have an accessor function implemented. Though this comprehensive approach is not really needed to use qhull, but could be useful sometimes.

I suppose it should or could be possible to build types corresponding to facetT and vertexT purely from Julia and maybe enough of qhT to implement the (limited) functionality now supported by DirectQHull with the current accessor functions, but I haven't really thought trough this.

[stevengj]

I think that the goal would be to expose at least as much functionality as the Python API.

The facetT and vertexT structures are simple enough to mirror in Julia (or even autogenerate with Clang), and ABI stability is guaranteed now that we can specify particular binaries with JLL dependencies. qhT was the only problematic struct, because it has (a) hundreds of fields and (b) compiler/platform-dependent jmp_buf fields that are nigh-impossible to declare reliably in Julia.

Is there any field of qhT that you need which we didn't provide accessors to already? More accessors could easily be added.

[blegat]

Thanks for adding this accessor API to qhull. I just tried Qhull@8.0.999 and I get:

julia> using Qhull_jll

julia> ccall((:qh_alloc_qh, Qhull_jll.libqhull_r), Ptr{Cvoid}, (Ptr{Cvoid},), Base.stderr)
ERROR: could not load symbol "qh_alloc_qh":
/home/blegat/.julia/artifacts/79616aed563a579660c5bd4fb576b2ac6d64c475/lib/libqhull_r.so: undefined symbol: qh_alloc_qh
Stacktrace:
 [1] top-level scope
   @ ./REPL[11]:1

I also can't find the other symbols from src/libqhull_r/accessors_r.c in the library.

[stevengj]

@blegat, the qhull Makefile links the accessors API, but the Yggdrasil script uses cmake … I didn't realize qhull had both. I'll have to submit a patch for their CMakeLists.txt 😖 — qhull/qhull#101

[JuhaHeiskala]

@stevengj I have used "facet_tail", "vertex_tail", "num_good", "del_vertices", "input_dim" that did not have accessors.

Looks like "facet_tail" and "vertex_tail" can be detected by qhull's "getid_" function, so accessor should not be needed.

"num_good" I have used for returning Voronoi regions in a Julia array and "del_vertices" to calculate number of Voronoi regions.

"input_dim" is of course known by caller, but should then be saved somehow in the Julia side.

I haven't yet looked at the Python API, but will take a look.

[stevengj]

I have used "facet_tail", "vertex_tail", "num_good", "del_vertices", "input_dim" that did not have accessors.

facet_tail and vertex_tail are defined to have id == 0 and next == NULL, so you can just check for next == NULL when traversing the list — that's what FORALLfacets and FORALLvertices do in C — so it's not clear to me what facet_tail and vertex_tail are good for (to external code).

For del_vertices, can't you check the deleted flag when traversing the vertex list? Similarly,num_good is the number of facets with facet->good set. That being said, it would be easy to add more accessors and the qhull maintainers seem receptive.

It might be good to ensure that we export enough qhT fields to e.g. reproduce something like qh_printsummary in pure Julia.

[JuhaHeiskala]

I don't recall/know the details of qhull now, so I assume your instructions are valid for the those fields.

Just to check, you think what I did in: DirectQhullHelper.c
with extern void jl_qhull_qhT_offsets(size_t *vv)
is excessive? That does provide access to the full qhT structure. Though maybe the method might not work on some platforms. I can't say.

The scipy python API defines the below "redacted" copy of qhT in qhull.pyx

   ctypedef struct qhT:
        boolT DELAUNAY
        boolT SCALElast
        boolT KEEPcoplanar
        boolT MERGEexact
        boolT NOerrexit
        boolT PROJECTdelaunay
        boolT ATinfinity
        boolT UPPERdelaunay
        boolT hasTriangulation
        boolT hasAreaVolume
        int normal_size
        char *qhull_command
        facetT *facet_list
        facetT *facet_tail
        vertexT *vertex_list
        vertexT *vertex_tail
        int num_facets
        int num_visible
        int num_vertices
        int center_size
        unsigned int facet_id
        int hull_dim
        int num_points
        pointT *first_point
        pointT *input_points
        coordT* feasible_point
        realT last_low
        realT last_high
        realT last_newhigh
        realT max_outside
        realT MINoutside
        realT DISTround
        realT totvol
        realT totarea
        jmp_buf errexit
        setT *other_points
        unsigned int visit_id
        unsigned int vertex_visit

[stevengj]

Providing access to all of the fields seems excessive, since many of them are internal qhull state, but the scipy API seems like a good guide.

[JuhaHeiskala]

Ok, I thought just to take the qhull.pyx from Scipy and translate it to Julia more or less directly.

[JuhaHeiskala]

I have an initial version of updated DirectQhull in 8e43cd0d. In case someone wants to take a look/provide feedback on the design.
There is one kludge/workaround maybe due to issue in Julia itself. (Julia crashes with code I thought should work.)

So far building convex hull is supported with DirectQhull.ConvexHull(points)
ConvexHull now provides most of the features that Scipy ConvexHull has, but not yet all.

[thchr]

I have an initial version of updated DirectQhull in 8e43cd0d. In case someone wants to take a look/provide feedback on the design.

I wanted to try out your commit but I'm not able to load the package (tried on Linux and Windows):

pkg> add https://github.com/JuhaHeiskala/DirectQhull.jl#master

julia> using DirectQhull
ERROR: KeyError: key DirectQhull [c3f9d41a-afcb-471e-bc58-0b8d83bd86f4] not found
Stacktrace:
 [1] getindex
   @ ./dict.jl:482 [inlined]
 [2] root_module
   @ ./loading.jl:979 [inlined]
 [3] require(uuidkey::Base.PkgId)
   @ Base ./loading.jl:945
 [4] require(into::Module, mod::Symbol)
   @ Base ./loading.jl:923

I wonder if there's something off in the Project.toml?

[JuhaHeiskala]

Hi,
Yes, probably the Project.toml uuid is not correct. I have not yet published the updated version in Julia package system, so that might be the reason. And I don't now know how to best publish in development package (dev command in package manager)
You should be able to just include the DirectQhull.jl source file in Julia to try it out though. You do need the master version of Qhull_jll that has the new accessor functions included.

Maybe then better to move further issues to under DirectQhull from here. :)