Is there a known algorithm to compute the (generalized) Voronoi diagram of a set of points, line segments and triangles in $\mathbb{R}^3$? If yes, are there any available implementations?
I know that there are two methods with available code for line segments and points on the plane, described in the following papers:
http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.112.8990 (CGAL)
https://www.sciencedirect.com/science/article/pii/S0925772101000037 (VRONI)
I am also aware of a method that computes voxelizations for a closely related 3D problem, where the sites/objects are surfaces:
http://sci.utah.edu/~jedwards/research/gvd/
But I'm not being able to find an algoithm for the case when the sites are vertices, line segments and triangles in space. The output should be the Voronoi diagram vertex coordinates and the (possibly curved) bisector descriptions.
Best Answer
Voronoi diagrams of points in $R^3$ are now implemented in several software libraries and can be computed, for example, in a few lines of Python code. This has not always been the case, so it still isn't trivial.
However, moving from Voronoi diagrams of points to diagrams of more complicated objects shifts the difficulty from asymptotical complexity issues (i.e., devising asymptotically efficient algorithms for point sets) to the difficulty of representing and computing with curved bisectors.
Furthermore, implementing algorithms that work on curved bisectors encounters inherent robustness difficulties. As an example, the vertex of a 3D Voronoi diagram is, by definition, a single intersection point of four edge curves in $R^3$, or equivalently of six face surfaces.
Robustness issues in geometric computing are a known research problem (see, for example, here, here or here), with many papers presenting problems even for simpler objects such as points and lines (for example, this one). Handling these degenerate cases in general and for curved objects, in particular, requires both theoretical and practical sophisticated methods. The book "Effective Computational Geometry for Curves and Surfaces" presents some of these methods for many known problems and in the context of your question, chapter 2 is especially relevant and can refer you to additional papers.
Even for the limited case of line segments in $R^2$, the two excellent implementations you cited apply advanced methods to handle these problems. The CGAL implementation adopts the Exact Geometric Computation (EGC) paradigm (including exact computations with square roots) and applies advanced geometric and arithmetic filtering for acceleration. The VRONI implementation, on the other hand, uses a more engineering approach for floating point computations, which combines the relaxation of epsilon thresholds with a multi-level recovery process. Both implementations are very impressive in their achievement. However, the problem in $R^2$ is relatively easy compared to the 3D problem in your question. In $R^2$, the bisectors are just parabola segments and there is no need to handle surfaces in $R^3$ and their intersection curves. In the Voronoi diagram of triangles, segments, and points in $R^3$, the bisector surfaces are quadric surfaces and the curves of the Voronoi edges can be polynomials of degree 4.
The only implementation I am aware of, which addresses these difficulties, is the one presented in this paper. They use a tracing algorithm (similar to the one in this previous paper) and apply exact arithmetic to handle the inherent robustness issues. In fact, they developed a special exact algebraic library (MAPC - library for manipulating algebraic points and curves) in order to be able to handle these curves and surfaces. The papers describing the implementation (short and long version) are a good reference to the algorithmic and practical difficulties of computing the Voronoi diagram of polyhedrons in $R^3$.
While their method was implemented in the past, I'd be surprised if the Voronoi code is still maintained. At the time, I managed to compile and run the MAPC library, but even compiling just the library on its own wasn't an easy task (and required dependencies on several outside libraries).
All this leads me to the conclusion that, unfortunately, it is unlikely that there are any available exact implementations to your problem. However, depending on your application, you may be able to use one of the non-exact solutions that exist. One direction, as you mentioned, is approximate solutions (such as this one) or voxelization methods, which can be accelerated using GPUs. Another practical approach, which may apply to you, is based on the Voronoi diagrams of points in $R^3$, for which there are software implementations as mentioned above. In these methods (mentioned in the book above), you sample the input objects, perform 3D Voronoi diagram computations on the sample points and then prune the output from unwanted faces.