Computing Clipped Voronoi Diagram

[Rumi381]

Does Geogram offer the computation of '3D Clipped Voronoi Diagram (CVD)' as the authors showed in "Efficient Computation of 3D Clipped Voronoi Diagram"? I need help with generating 3D CVD from an input mesh file. Suppose I have an arbitrarily shaped 3D region defied by a triangular mesh as a .obj file. Can anyone please help guide me on how I can generate 3D CVD by applying the proper CVT method to generate the polyhedral mesh as the CVD and save the mesh as a .obj file? I really this for my research.

[BrunoLevy]

Hello,
See this example program
Use:

compute_RVD volumetric=true my_mesh.obj

Your mesh needs to be a clean manifold mesh, that defines an interior region (it will be tetrahedralized). It will generate the restricted Voronoi diagram as a collection of tetrahedralized clipped Voronoi cells.

See also this part of the Graphite modeler, here. It will generate the restricted Voronoi diagram as a set of surfaces that represent the boundary of the clipped Voronoi cells.

If you want to install Graphite, see instructions here.

[Rumi381]

Thank you, Dr. @BrunoLevy. I am new to exploring Geogram, so I may have questions to ask. Would you please help with the following queries?:

1. I tried the compute_RVD with 'compute_RVD volumetric=true RVD_cells=true 3_holes.obj'. I got the out.obj file. When I tried to open this obj file in Meshlab, I got the error error as the attached file.
   
   However, ignoring the error, when I view the mesh, I have two observations:
   a) In the following View1.png file, you will find that each Voronoi cell on the surface has been triangulated or tetrahedralized in 3D.
   However, for my use case in a Finite Element simulation, I need the original Voronoi structure or cells. Basically, I am approximating
   the grans of a material as the Vonoino cells (Polyhedral cells). So, I need the original Voronoi structures in the out.obj file.
   

   b) The most concerning observation is that when I tried to inspect what was happening inside the volume, I saw that there were no cells
   inside the volume (Please see the View2.png file below). But we are expecting a 3D Voronoi diagram in the volume. I don't know if it
   is happening because of the error in Meshlab or if I just got the Voronoi structure only on the surface.
   
   I need the 3D Clipped Voronoi Diagram, where I will have the 3D Voronoi cells inside the volume of the given mesh, as shown in Figures
   3(c), 7(c), 7(g), 8(c), 8(g) in your "Efficient Computation of 3D Clipped Voronoi Diagram" paper. Dr., please guide me on how I can
   achieve this.

2. With the 'compute_RVD volumetric=true RVD_cells=true 3_holes. obj' command, we do not control how many cells will be generated. Can we specify or control the desired number of 3D Voronoi cells in the given mesh?

3. Is the CVT algorithm automatically applied when we execute compute_RVD, or do we need to apply it separately? Dr., as I have to use the output Clipped Voronoi Diagram in a finite element simulation, I must generate the optimized cell structure, as you also showed in your paper with your proposed CVT algorithm. If the CVT is not automatically applied, please guide me on how I can leverage Geogram functionality to do that. However, if the CVT is automatically applied, can we control the optimization level with any parameters?

I know I asked a lot, and please excuse me for that. I badly need your help to achieve the target I shared here.

[BrunoLevy]

By default, compute_RVD computes the VD of the input mesh's vertices restricted to the input mesh. What you observe in meshlab is a set of 3D Voronoi cells that land on the medial axis of the input mesh (which is expected because there is no vertex inside the volume).

You can specify a points file on the command line, use:

compute_RVD volumetric=true RVD_cells=true 3_holes.obj points.xyz

where points.xyz is an ASCII file, with point's x,y,z coordinates on each line.

To see all options of compute_RVD, use:

compute_RVD -h

then it will display all supported command-line options (there are many...). The -h option works with all geogram programs.

To generate a restricted Voronoi diagram for a pointset optimized with CVT (Centroidal Voronoi Tesselation), you may also use:

vorpalite profile=poly three_holes.obj nbpts=NNN

where NNN is the desired number of points.

For visualization purposes, you may use:

vorpalite profile=poly three_holes.obj nbpts=300 poly:cells_shrink=0.1

Here is the result (you can visualize it with vorpaview bundled with geogram):

If you plan to use the API, I recommend you take a look at the sources of compute_RVD, they are here, and the sources of vorpalite are here. See in particular this function

[Rumi381]

Thank you, Dr. @BrunoLevy, for the detailed explanation of my questions. As you suggested, I have tried vorpalite. However, I want to share some of my findings and problems with you.

1. In the resulting output file, the outer surface of the mesh has kind of triangulated textures (the faces are not polygonal), as shown in the figure:
   
   Can we achieve the polygonal faces on the outer surface, as shown in the figure?:
   

2. I tried the following hollowThickCylinder.obj as the input mesh with the 'vorpalite profile=poly hollowCylinder.obj hollowCylinder_poly.obj remesh:nb_pts=1000 poly:cells_shrink=0.1' command.
   

But the vorpalite program just exited without generating any output file! I got the following output in the terminal:

---

| |
| o-[config ] Configuration file name:geogram.ini |
| Home directory:C:/Users/jalal |
| o-[I/O ] Output = hollowCylinder_poly.obj |

---

/ =====[Polyhedral meshing]===== _________________________________________
| |
| o-[I/O ] Loading file hollowCylinder.obj... |
| (FP64) nb_v:320873 nb_e:239670 nb_f:319560 nb_b:4154 tri:1 |
| dim:3 |
| Attributes on vertices: point[3] |
| o-[Poly ] Mesh is not a volume |
| Trying to tetrahedralize |
| o-[Validate ] Removed 1313 duplicated vertices |
| (FP64) nb_v:319560 nb_e:239670 nb_f:319560 nb_b:0 tri:1 di |
| m:3 |
| Attributes on vertices: point[3] |
| o-[Intersect ] start. |
| get intersections |
| build AABB |
| get candidate facet pairs |
| compute intersections |
| o-[Detect isect] Elapsed time: 4.297 s |
| o-[Intersect ] remesh intersections |
| Intersections: 0 |
| Intersected triangles: 0 |
| Max intersections in triangle: 0 |
| o-[Isect ] [ 0] done |
| o-[Remesh isect] Elapsed time: 0.004 s |
| o-[Intersect ] epilogue |
| o-[Colocate new] Elapsed time: 0 s |
| o-[Intersect ] Found 958680 bundles |
| Found 0 polylines |
| Found 2 charts |
| o-[Radial sort ] Nb radial polylines:0 |
| [ 0] done |
| Elapsed time: 0.001 s |
| o-[Intersect ] Found 2 regions |
| finished. |
| Simplifying coplanar facets |
| o-[TetMeshing ] Tetrahedralizing... |

The program just exited without doing anything else. Is there any specific reason for that? In my use case, I need to analyze this type of structure. Please advise me on achieving the desired Clipped Voronoi diagram for such structures.

[BrunoLevy]

• of course the outer faces are triangulated: what you compute is the intersection between a Voronoi diagram and the interior of a triangulated mesh, so the outer faces correspond to the triangulated mesh. You can simplify the boundary as follows, but this will generate non-planar polygonal facets on the boundary, which may be not good (depending on what you want to do with the result):

vorpalite three_holes.obj profile=poly nb_pts=10000 poly:simplify=tets_voronoi_boundary poly:normal_angle_threshold=90

(try this: use nb_pts=300 you will see what I mean)

• use vorpalite -h for the list of options

[Rumi381]

Thank you, Dr. @BrunoLevy. I'd like to ask you about the options with the 'poly:simplify' argument. I am not quite sure what the 'tets_voronoi', 'tets', and the 'tets_voronoi_boundary' options are actually doing or when we should use certain options. And also, the other arguments in *poly, especially the 'poly:normal_angle_threshold,' 'poly:generate_ids,' and the 'poly:tessellate_non_convex_facets' argument. I would like to learn more details about the use cases of these arguments and their associated options. Would you please guide me on this? Another thing I needed to share with you is that I tried the options like 'nl:MKL=true' and 'nl:CUDA=true'. Though I have MKL and CUDA installed in my system, I am getting the following:

---

| |
| o-[config ] Configuration file name:geogram.ini |
| Home directory:C:/Users/jalal |
| Error: OpenNL error in nlOpenDLL(): Not implemented |
| Error: OpenNL error in nlOpenDLL(): Not implemented |
| Error: OpenNL error in nlOpenDLL(): Not implemented |
| Error: OpenNL error in nlOpenDLL(): Not implemented |
| Error: OpenNL MKL: could not initialize |
| o-[I/O ] Output = out.meshb |

and

---

| |
| o-[config ] Configuration file name:geogram.ini |
| Home directory:C:/Users/jalal |
| Error: OpenNL error in nlOpenDLL(): Not implemented |
| Error: OpenNL error in nlFindFunction(): Not implemented |
| Error: OpenNL error in nlInitExtension_CUDA: function not found(): cudaDriv |
| erGetVersion |
| Error: OpenNL CUDA: could not initialize |
| o-[I/O ] Output = out.meshb |

Is there any issue related to my system? Please guide me on this.

[BrunoLevy]

nl:CUDA is for linear system solving, you do not need it for Voronoi meshing.

[Rumi381]

Thank you, Dr. @BrunoLevy. I have a clear idea about most of the arguments and options. However, I am still unclear about the 'poly:normal_angle_threshold' argument and how the different values affect the mesh. It would be great if you could explain briefly how we can leverage this argument and how the range of values of 'normal_angle_threshold'. Another thing is that if our input mesh is a 2D region, does Geogram offer any functionality to generate the Polygonal mesh inside a 2D region?

[BrunoLevy]

Would you share your hollow_cylinder.obj file ? I can take a look to see what happens (seeing the log, your mesh is not a clean closed manifold mesh, and geogram's automatic reparation did not manage to fix it)

[Rumi381]

Here is the file I tried.
hollowCylinder.zip

[BrunoLevy]

Your mesh has many borders (highlighted in white):

I recommend you install Graphite, instructions here, then, in Graphite

• Surface->repair->merge vertices
• Mesh->remove mesh elements-> edges (your mesh has some floating edges, probably there for visualization)
• Mesh->remove isolated vertices (there were dangling vertices)
• Save current object as hollowCylinder_cleaned.obj

Now:

vorpalite profile=poly hollowCylinder_cleaned.obj nb_pts=10000 poly:simplify=tets_voronoi_boundary poly:normal_angle_threshold=45

Cleaned mesh was still not completely correct, but now geogram manages to fix it, and you get the result:

When you manipulate meshes, I highly recommend you visually inspect your meshes to make sure they are clean with a software that shows the boundaries, shows the isolated vertices etc... (make sure your mesh is not a mess before starting computations !)

[Rumi381]

Thank you, Dr. @BrunoLevy. I am getting familiar with Graphite. I will get back to you soon with some of my observations and queries on Graphite.

[Rumi381]

Dr. @BrunoLevy, I have tried to explore most of Graphite's functionalities following the instructions provided in the Graphite Wiki. This is a great tool, and thank you for making it open-source. I will explore Graphite more in the coming days. However, I have some quick observations, and I need your instruction for the following:

1. If we create a volume sample, can we save this points set as points.pts or xyz file? And can we use this generated points set to generate the Voronoi meshing since we cannot control the CVT parameters when directly generating the Voronoi mesh?

2. I generated the Voronoi mesh in Graphite from an input mesh. But when I saved the mesh as a .obj or .msh file with 'Save current object as,' I saw the saved files were problematic and could not be loaded in Graphite or any other software. For example, with 'vorpalite', we could generate the desired polyhedral mesh it had no problem to be loaded. I tried the same input mesh with the same number of cells in Graphite. Still, I see the generated Voronoi mesh file is incomplete (it has significantly fewer data than the file created by vopalite) and can be loaded due to errors, and sometimes the program just crushes. Is there any specific reason why this issue is happening? Please guide me on how to solve it.
   

3. Though the 'volume style' option is on with a yellow color, why don't I see the color for the polyhedral cells? What should I do?
   

4. Currently, I am using Graphite through the 'graphite.bat' file option you provided for Windows installation. Can we add the available plugins in this manner? However, I tried to build it on Windows many times, but I got the following error every time, as shown in the screenshot. Please guide me on how to solve the issues.
   

[BrunoLevy]

1. Graphite has a "sample volume" command that generates a pointset that you can save, then compute_RVD can use it (see previous answers)
2. Can you send one of the generated files to me, I'll double check (I observed that so-generated files cannot always be loaded in meshlab (that seemingly only supports triangulated meshes), but they can be loaded in Graphite, Vorpaview and other softwares)
3. A .obj file is in fact a surface, not a volume. It is because there is no standard file format for general polyhedral meshes.
4. It is weird, are you sure you exactly followed the instructions here (I'll double check if I did not break anything). Regarding plugins, they are automatically loaded when starting Graphite (directly or from graphite.bat)

[Rumi381]

Thank you, Dr. @BrunoLevy. My current observations are as follows:

1. Thank you. I was able to generate the volume sample points file.
2. The attached zip folder contains the following files:
   Graphite_outputs.zip
   a) 3holes.obj -> the input mesh
   b) 3holes_poly_graphite.obj -> output file of the Voronoi mesh as a .obj file, which is just the surface, as you said. However, my confusion is if I generate the same output as a .obj file from the 'vorpalite', I see that it correctly represents the volumetric cells as you will see in the 3holes_poly.obj file, which was created by 'vorpalite' with the same inputs. Then why does the output .obj from Graphite represent just the surface?
   c) 3holes_poly_graphite.msh -> I tried to save the output as a .msh file, but it does not have anything, and I don't know why.
   d) Finally, I tried to save the output as a .ovm file, but it failed due to the error shown in the screenshot, even though I enabled the 'generate ids' option in Voronoi meshing.
   
3. I have tried all the instructions to build Graphite in Windows provided in the link but got the error I shared earlier. However, I added the following in GraphiteThree\plugins\OGF\Plugins.txt file:
   add_subdirectory(WarpDrive)
   add_subdirectory(RayTracing)
   add_subdirectory(gompy)
   But I don't see the plugins when I run the graphite.bat file.

[BrunoLevy]

• I confirm meshlab does not support polygonal meshes. For instance, try with a simple cube, like this one:
  cube.zip, it crashes
• but you can open all your files in graphite, geobox, vorpaview. You can also probably load them in softwares that fully implement the .obj file format (like Maya for instance)
• about plugins, what do you mean by "I do not see the plugins" (BTW, for what you are doing you do not need them)

[Rumi381]

Yes, Dr. @BrunoLevy, I sometimes see Meshlab crashes when opening .obj files. However, by I don't see the plugins, I meant that according to Installing Python, I don't see the Python option in the dropdown, as shown in the screenshot, though I added 'add_subdirectory(gompy)' in GraphiteThree/plugins/OGF/plugins.txt file.

I don't need the plugins for my use cases; I'm checking that everything works fine. However, I need your help with two specific issues:

1. As I am using Abaqus for my FEM simulations, I generally model the geometry in Abaqus and export it as a .obj file. I use this file as the input mesh for vorpalite or graphite. However, as I shared with you earlier, the .obj file from Abaqus is often messy and creates problems when we directly pass it to vorpalite. For a remedy, you suggested me to use 'graphite' to preprocess the file as follows:
   ..* Surface->repair->merge vertices
   ..* Mesh->remove mesh elements-> edges (your mesh has some floating edges, probably there for visualization)
   ..* Mesh->remove isolated vertices (there were dangling vertices)
   ..* Save the current object as hollowCylinder_cleaned.obj

...I see vorpalite receives arguments for specific preprocessing steps. Can we add the preprocessing steps we have done in ...graphite into vorpalite so we can handle everything in vorpalite when the input mesh is messy?

2. Can we leverage geogram to generate Polygonal mesh when the input mesh is a 2D mesh?

[Rumi381]

Hi, Dr. @BrunoLevy. If you have time, please let me know about the two specific issues in the previous comment. I am eagerly waiting for your answer.