Any plan to refactory the lib with modern cpp?

[xarthurx]

Hi, first of all, thank you for the great lib. I'm implementing some app to generate adaptive voronoi cells using a spatial adaptively sampled point clouds. After trying qHull for some time, I finally found this lib and made it work.

However, since I'm working on Windows, integrating the lib and make everything work costs a considerable amount of time... Especially:

1. incorporating the lib into my CMake complication system.
2. understanding the indexing logic and retrieve the data I want.

Since the lib is written in earlier years, in an old-style (for instance, memory management, a lot of pointers, etc.), it is not easy for people like me who learned cpp in the modern way (c++11, c++14, c++17).

I think the 2 most important thing are:

1. Incorporating this lib with a modern CMake build system. This will allow programs from different build system to use the lib without too much effort.
2. Re-factory the code using modern cpp resource management and data structures. This will make the code more readable and extensible.

Since there aren't many libs doing 3D Voronoi at the moment, it would be really great to make this lib more popular to the open-source community. Is there any plan from the author side to do this? Or how should I help and contribute without re-writing the whole thing?

[chr1shr]

Thanks for your interest in the library and I am glad to hear you have found it useful.

For a number of years I did not have any research funding to develop this project, but I recently got a grant to work on it. My student and I are planning to release an updated version in the next month that adds: (A) native 2D calculations, (B) improved iteration over Voronoi cells, (C) multithreading support via OpenMP, and (D) general cleanups throughout the library to make it better suited for package management systems.

Let me address your two points. For CMake integration, there is already a CMakeLists.txt file that has been contributed by @junghans. I don't use CMake much myself, but you are welcome to contribute improvements to this.

For your second point, our new version overhauls some aspects of the library. In particular, looping over particles has been brought more in line with standard C++ functionality and offers tangible benefits to the user. But currently there are no plans to overhaul core components of the library. There are two main reasons for this:

1. The library is used widely on many systems, often as a low-level component, and I want to keep as close to the base C++ standard as possible and not require that users have compilers that support newer language extensions. Other scientific software libraries (e.g. FFTW, LAPACK) do not depend on newer language extensions.
2. In many cases, the custom memory management and pointer usage has been tailored to take advantage of the particular problem structure and offers noticeable performance improvements over using more general C++ data types such as those found in the STL. For example, the ed array for storing Voronoi edge tables uses custom pointers to take advantage of the fact that most vertices have order 3, but occasionally some might have higher order. In the past someone did try to rewrite this using STL vectors but it resulted in a 30% performance drop.

I have tried to make the user-facing side as straightforward as possible, with many functions for accessing all aspects of the Voronoi cell (e.g. faces, perimeter, surface area), and I'm open to comments about how that could be improved. I'm also open to general layout improvements. I do not currently see a benefit in overhauling low-level data structures, although you're welcome to give it a try if you wish.

[junghans]

cmake-wise it should be be pretty easy to use voro++

find_package(VORO REQUIRED)
target_link_libraries(<your_cmake_target> PRIVATE VORO::VORO)

[xarthurx]

@chr1shr Thank you for the quick response.

CMake

I guess I've used the version downloaded from voro++ website and found this repo later so that I didn't notice the CMakelist.

Since this repo is a standard formatted CMake lib now, I've added a package request at https://github.com/microsoft/vcpkg/issues/18494 for the vcpkg package management system. (FYI, a easy-to-use, cross-platform packagement management system that make using 3rd-party libs so much easier)

And it may help to link this github repo to the original voro++ website.

Overhaul

I agree with you on this point. Then I'll list my suggestions for the additional user interface for accessing data produced from voro++ here:

General suggestions

• More import/export options. pov-ray is outdated, and gnuplot is not widely used anymore (at least from the CS field). So besides the functions of exporting data to outside files like draw_cells_gnuplot or draw_cells_pov, additional functions should also be provided to export data of cells, edges, etc, directly to some STL containers. Similarly, when using voro as a lib rather than a cmd tool, I would like to load points directly from popular-used containers std::vector or Eigen::Matrix, beside the current importing mechanism from a file.

• General container format. Issue https://github.com/chr1shr/voro/issues/4 is related to this point. I guess the lib is not originally developed for using mesh as containers, but this functionality is super useful and needed to generalize Voronoi application for differents type of geometries. It can also save the effort to define wall manually.

• Multithreading Since you mentioned OpenMP, I guess it is good to also point out that for cross-platform compatibility, tbb is a better option, as some of the newer OpenMP features are not available on Windows. Just be aware that using the tbb lib will require the re-written of some for functions using the tbb version for function.

Function suggestions/data storage styles

Related to the first point above, the representation of cells, edges, vertices are not very easy to read. I struggled a for while to understand the logic behind draw_cells_gnuplot to be able to re-construct edges of the cells, but in the end, fall back to read the file exported from those draw_cell functions instead of accessing them directly from methods inside the container class. So here're some feedback from a user's side:

• voronoicell_base::vertices, voronoicell_base::face_vertices: these functions outputs different types of data in the same container. For instance, the first one output the vertex number and index in the same container. It is very counter-intuitive and cost extra efforts to access the data. taking to containers to store them separately or using data structures like std::tuple or std::pair will make things much easier and user-friendly.
  • I think a good reference is how libigl stores mesh data. A type structure to store vertex data, and a type structure to store connections (faces, edges, etc.) This has been proved very efficient in the graphics field where intensive computation is needed.
• edge access: Currently there's no easy way to access the individual edges or export edges (even from each cell) directly. Though the lib is cell-based computation, adding access to these general data will be very helpful than asking the user to do it (and also cleaning the duplicated edges on a global scale).
• compute_all_cells: Just adding a function for calculating computation cost looks strange to me. I think an improved version is to add on bool option to:
  • allow either the current functionality, or
  • compute all data and store it inside the container class, so that when accessing the specific data afterwards, no additional computation is needed.

Hope this feedback will help, and I'm open to any further involvement in the development.

[junghans]

Since this repo is a standard formatted CMake lib now, I've added a package request at microsoft/vcpkg#18494 for the vcpkg package management system. (FYI, a easy-to-use, cross-platform packagement management system that make using 3rd-party libs so much easier)

FYI voro is part of the spack package manager as well.

[xarthurx]

FYI voro is part of the spack package manager as well.

Thanks, but that manager does not support Windows...

[xarthurx]

find_package(VORO REQUIRED)
target_link_libraries(<your_cmake_target> PRIVATE VORO::VORO)

I got the following error when trying to use the above command in my main CMakelist.txt

  By not providing "FindVORO.cmake" in CMAKE_MODULE_PATH this project has
  asked CMake to find a package configuration file provided by "VORO", but
  CMake did not find one.

  Could not find a package configuration file provided by "VORO" with any of
  the following names:

    VOROConfig.cmake
    voro-config.cmake

  Add the installation prefix of "VORO" to CMAKE_PREFIX_PATH or set
  "VORO_DIR" to a directory containing one of the above files.  If "VORO"
  provides a separate development package or SDK, be sure it has been
  installed.
Call Stack (most recent call first):
  CMakeLists.txt:64 (find_package)

[junghans]

find_package(VORO REQUIRED)
target_link_libraries(<your_cmake_target> PRIVATE VORO::VORO)

I got the following error when trying to use the above command in my main CMakelist.txt

  By not providing "FindVORO.cmake" in CMAKE_MODULE_PATH this project has
  asked CMake to find a package configuration file provided by "VORO", but
  CMake did not find one.

  Could not find a package configuration file provided by "VORO" with any of
  the following names:

    VOROConfig.cmake
    voro-config.cmake

  Add the installation prefix of "VORO" to CMAKE_PREFIX_PATH or set
  "VORO_DIR" to a directory containing one of the above files.  If "VORO"
  provides a separate development package or SDK, be sure it has been
  installed.
Call Stack (most recent call first):
  CMakeLists.txt:64 (find_package)

Most like you install installed voro++ in a non-standard path, as the cmake error message suggest try to add use CMAKE_PREFIX_PATH to add a search path, e.g. -DCMAKE_PREFIX_PATH=/path/to/voro/root.

[junghans]

FYI voro is part of the spack package manager as well.

Thanks, but that manager does not support Windows...

See https://github.com/spack/spack/issues/9323, spack works at least under WLS (Windows 10 bash).

[xarthurx]

Most like you install installed voro++ in a non-standard path, as the cmake error message suggest try to add use CMAKE_PREFIX_PATH to add a search path, e.g. -DCMAKE_PREFIX_PATH=/path/to/voro/root.

This is where on Windows it is different if not installed by package manager. There is no "universal install path" like /usr/share. The path needs to be managed by the package maintainer. Normally in a {package}-config.cmake file provided, as what the error suggested.

See spack/spack#9323, spack works at least under WLS (Windows 10 bash). In that issue, there's also address in MSVC compiler. WSL is not an option for native Windows support, and is just a lightweight virtual machine. I have no means to push for supporting Windows, as I know that this lib is originally developed for scientific computing, and you guys usually only use Linux.

BUT, IMO, if you really want to extend this lib to a general available package that can be install and used by a wider range of people, then cross-platform support and better user interface are needed.

A good example is the spdlog lib: https://github.com/gabime/spdlog

[junghans]

Most like you install installed voro++ in a non-standard path, as the cmake error message suggest try to add use CMAKE_PREFIX_PATH to add a search path, e.g. -DCMAKE_PREFIX_PATH=/path/to/voro/root.

This is where on Windows it is different if not installed by package manager. There is no "universal install path" like /usr/share. The path needs to be managed by the package maintainer. Normally in a {package}-config.cmake file provided, as what the error suggested.

I am not a Windows user, but https://stackoverflow.com/a/15663114 suggests setting CMAKE_PREFIX_PATH as well.

We generate and install such a config file for voro here:

https://github.com/chr1shr/voro/blob/122531fbe162ea9a94b7e96ee9d57d3957c337ca/CMakeLists.txt#L60

spdlog does the same and installs it's exports in CMAKE_INSTALL_LIBDIR as well: https://github.com/gabime/spdlog/blob/12df172575bf43ed6b879dabff4ba59c72e738e3/CMakeLists.txt#L289

Again I am not a Windows user, so if you have specific suggestions how to improve the cmake please go ahead make a PR, I am happy to review it.

[ltalirz]

For what it's worth, I just wanted to mention that voro++ is available on the conda-forge conda channel as well, i.e. you can install it via conda install -c conda-forge voro on linux and macos.

conda supports windows natively but I got stuck when trying to add the windows build - I think it was just some stupid issue of using the correct executable to build the library archive file, see https://github.com/conda-forge/voro-feedstock/issues/1

Also, I was using the makefile rather than the cmake approach - perhaps cmake would be easier? If someone can post a working set of commands to build voro on windows (or directly make a PR to the feedstock) I'm happy to add it to conda.

[xarthurx]

@ltalirz https://preshing.com/20170511/how-to-build-a-cmake-based-project/

Usually, if a lib is well configured, using

mkdir build
cd build
cmake -G "Visual Studio 15 2019" ..

should be enough.

I'm currently using it as source-code version directly build into my project, rather than building a static lib and install it to some shared folder. But that only works for cpp project I guess.