3D Barycentric Coordinates for Convex Polyhedra with Triangular Faces

[antoniospg]

Antonio Gomes GSoC 2021 Submission

Overview

The package 3D Generalized Barycentric Coordinates offers an efficient and robust implementation of three-dimensional closed-form, generalized barycentric coordinates defined for convex simplicial polytopes. In particular, this package includes an implementation of Wachspress, discrete harmonic, mean value, and one extra function to calculate barycentric coordinates with respect to tetrahedra. In this implementation, we restrict our polyhedra to convex ones with triangular faces, although some of the coordinates may accept more general shapes.

Compiled docs Final report

Commit Log

CGAL/cgal-public-dev@31842cc9fad: Final fixes in the docs after revision CGAL/cgal-public-dev@65b4b83400e: final tweaks CGAL/cgal-public-dev@80a68837adb: updated doc after first revision CGAL/cgal-public-dev@d8a960b4145: WP boundary coordinates can now be any polygon CGAL/cgal-public-dev@cdc7d44f166: adding thumb CGAL/cgal-public-dev@ddab6f837d3: more fixes CGAL/cgal-public-dev@2185df54325: fixing issues after first revision CGAL/cgal-public-dev@5245b5b647b: fixing warnings in docs build CGAL/cgal-public-dev@87dcb2671a7: first version docs CGAL/cgal-public-dev@b1111af834e: fixed some examples + updated the docs CGAL/cgal-public-dev@999a602f198: adding final example CGAL/cgal-public-dev@b6df739dc28: one more example and update docs CGAL/cgal-public-dev@2e01a542646: added shape_deformation example CGAL/cgal-public-dev@5edff0732c1: final version edge_cases CGAL/cgal-public-dev@6af06f2dd72: fixes after review + adding doxygen files CGAL/cgal-public-dev@8a8a1222741: minor fix CGAL/cgal-public-dev@805e787a594: final version edge cases CGAL/cgal-public-dev@6ea12aeee09: first functional version of edge cases(only wp now) CGAL/cgal-public-dev@e0f6bf9e1a7: adding test to verify boundary CGAL/cgal-public-dev@d55d362e8a1: make it work with arbitrary face graphs + fixed warnings CGAL/cgal-public-dev@8aa9fb56660: modifying api to handle edge cases CGAL/cgal-public-dev@86807cf4c0c: more fixes and created first benchmark CGAL/cgal-public-dev@c545a66c48d: Fixing after first review, need to finish tests CGAL/cgal-public-dev@e10f9d6f7b6: First version voronoi coordinates (still debugging) CGAL/cgal-public-dev@f172a4c4416: functional version of mv coordinates + tests CGAL/cgal-public-dev@672ec0513b3: fixing some bugs CGAL/cgal-public-dev@c741b6ac269: draft version of mv coordinates CGAL/cgal-public-dev@9f096ea6936: dh coordinates final adjustments CGAL/cgal-public-dev@4569c22353b: adding tests, fix for wp coordinates, dh now working for cube CGAL/cgal-public-dev@80121761a11: functional version and first test of dh coordinates CGAL/cgal-public-dev@4afcecf75d4: fixing some bugs of the previous version CGAL/cgal-public-dev@00b6f364e41: First implementation of DH coordinates (not working yet) CGAL/cgal-public-dev@09b1974d3e1: fixing tests for wachspress coordinates after review CGAL/cgal-public-dev@c88da0746e5: finishing test for cube, add generator of random points inside tetraherdron CGAL/cgal-public-dev@1f264294132: first test with cube, testing unit partition, barycenter, weights between 0 and 1. Added utils.h to generate polyhedrons CGAL/cgal-public-dev@90427e76015: changing the name triangle_coordiantes_3 to tetrahedron_coordinates and removing -tol from the wp test CGAL/cgal-public-dev@2735bccdf0f: added tetrahedron vs wp test and the beginning of the general one CGAL/cgal-public-dev@12694239e98: fixed minor issue CGAL/cgal-public-dev@078fe7ae1d8: testing different kernels CGAL/cgal-public-dev@c9219d4b03b: fixing code issues after revision CGAL/cgal-public-dev@38052497b27: review 1 for wachspress coordinates 3 CGAL/cgal-public-dev@d3fbd5d93fd: Testing better examples and make code look cleaner CGAL/cgal-public-dev@4a73807afe2: FIRST FUNCTIONAL VERSION. Just implemented the equations, now I will make my code more organized CGAL/cgal-public-dev@cb0a44cea17: first part of the calculation of wp coordinates CGAL/cgal-public-dev@874ca15f0a3: making WP3 constructor work with default pmesh params CGAL/cgal-public-dev@d5d1f1132e5: better api, barycentric_enums and tests with tetrahedrons in the new api CGAL/cgal-public-dev@1b26e485638: enhancing the code structure, ran some tests with circulators, property_maps and surface mesh CGAL/cgal-public-dev@28cbc05268a: Created structure for wachspress coordinates CGAL/cgal-public-dev@d0e8e8bcbdb: fixing cmakelists of test and benchmark CGAL/cgal-public-dev@3fc1e1e851f: Fixing cmakelist and updating package_info CGAL/cgal-public-dev@a38f13fb9f5: Created tetrahedron_coordinates_3 that contains the functions to calculate tetrahedra coordinates, as well as utils_3 that do the actual calculation, and one example to test the possible 3 cases of points CGAL/cgal-public-dev@7d28cb67dba: adding basic file structure

[afabri]

Let me discuss it here and not on the wiki as it is easier to get others in the loop. I do not like the idea to have two functions, which compute the same thing, but as they have different arguments and return values have different names. There is tetra hedron_coordinates() and tetrahedron_cordinates_in array(). The first one gets an output iterator as argument and returns an ouptut iterator, while the second one returns an array. I would prefer that they have the same name, and that the array was a non-const reference. @lrineau @sloriot @efifogel (and others) what is your opinion on this?

[afabri]

@danston the function returning an array still mentions a tuple.

[afabri]

And in the @return it should be "an" array.

[lrineau]

Overload (same name) should be restricted to cases where the developer using the function should not have to ask herself which version she is calling. Here I agree it could be an overload (with the same name), because the caller clearly knows what she is doing if she passes an output iterator in the set of parameters.

As for the returned array, I think it cannot be a reference. It is was a reference, where would be the real array object? Let that returned value be returned "by copy", and the "return value optimization" will avoid the copy.

[afabri]

As the traits is an optional parameter the two overloads cannot be disambiguated. And what I meant was fct( array<FT,4>& ret)

[lrineau]

As the traits is an optional parameter the two overloads cannot be disambiguated.

Then why did you ask for our opinion?

And what I meant was fct( array<FT,4>& ret)

I do not like that. That sort of API:

• does not allow the use of auto, as in auto result = f(),
• does not take into account the return value optimization, or the move semantic,
• force the caller to write ugly code with uninitialized variable (one of my hated function in CGAL is Triangulation_3::locate(p, lt, i, j))

I would really not like to see that in a non-ancient code.

[afabri]

And what about the suffix _in_array? Should it be "as" or "to" instead of "in"?

[lrineau]

Actually, if it was my code, the function with the name tetrahedron_coordinates(a,b,c,d) would return the four coordinates by value (in an array), and there would be another function tetrahedron_coordinates_to_output_iterator(a, b, c, d, output_iterator). Here the infix _to_ is because the output of the function goes to an existing object.

If you want to keep it the way it is currently proposed, then in my opinion it should be tetrahedron_coordinates_as_array, because it creates a new array object.

The infix _in_ seems more adapted to something about the input of the algorithm (like "search a value in something").

[danston]

I actually like the idea of having tetrahedron_coordinates(a,b,c,d) and tetrahedron_coordinates_to_output_iterator(a,b,c,d,output_iterator) but it won't be consistent with the 2D package where the functions segment_coordinates(a,b,output_iterator) and triangle_coordinates(a,b,c,output_iterator) are defined. The way they are defined like that is to have the same API with generalized coordinates such as Wachspress e.g. where the number of returned coordinates n is greater than 2/3/4 and depends on the input. To accommodate all of them, we have wachspress_coordinates(polygon,output_iterator).

In general, we wanted to add the function with _in_array to have a simpler API because we know that we have only 2/3/4 coordinates, but it was a source of confusion in the 2D version and it is also now in the 3D version. Maybe the best is to avoid these extra functions at all.

[afabri]

In 2D it is in master, but not in a public release, right? So we could maybe still change it. The only disadvantage I see is that there are way more functions writing into an output iterator.

[danston]

Yes, 2D is in master. But since we brought this conversion a bit earlier, I undocumented the versions with _in_pair and _in_tuple to have them all consistent with the 3D package once we decide and avoid breaking changes in the next versions.