cgal
cgal copied to clipboard
CGAL
Speed up transformation by calculating the transposed inverse matrix once
Summary of Changes
Within Nef_polyhedron_3::transform, transforming a Plane_3 (used to represent the Sphere_circle of the sphere map) requires calculating transpose().inverse() for transformation of the orthogonal vector. When transforming many planes the transposed inverse has to be recalculated many times, even though it doesn't change. Furthermore the calculation of is_even requires calculating the sign_of_determinant, again a pre-calculated value for this can be passed in.
The proposed change allows a previously calculated transformation and is_even values, to be passed as parameters to the Plane_3 transform methods thus eliminating re-computation.
Release Management
- Affected package(s): Nef_3/Nef_S2
- Feature/Small Feature (if any): performance/speed
- License and copyright ownership: Returned to CGAL authors.
Hi @GilesBathgate. I would like to better understand your use case. Are affine transformations something important? When do you apply them. Just after loading a polyhedron? Or you create N copies and move them all individually, Or you move the result of some Boolean operation? Or all of the above? I ask, because I thought that we can make the K3_tree faster and replace the orientation tests with the split planes just comparisons of x, y, or z coordinate as when the split planes get created they are parallel to the xy, xz, or yz plane, but then I realized that when a Nef polyhedron gets transformed, its K3_tree gets also transformed. I might also check how expensive it would be to create the kd-tree after each affine transformation.
Hi @GilesBathgate. I would like to better understand your use case. Are affine transformations something important? When do you apply them. Just after loading a polyhedron? Or you create N copies and move them all individually, Or you move the result of some Boolean operation? Or all of the above?
Yes all of these are valid depending on the CAD script used. RapCAD, and openscad will often create/build a polyhedron at the origin, do the transformation and then construct a nef from it. However its also possible to do some boolean operation and then transform the result.
I ask, because I thought that we can make the K3_tree faster and replace the orientation tests with the split planes just comparisons of x, y, or z coordinate as when the split planes get created they are parallel to the xy, xz, or yz plane, but then I realized that when a Nef polyhedron gets transformed, its K3_tree gets also transformed.
I might also check how expensive it would be to create the kd-tree after each affine transformation.
Transforming the K3_tree seems to be faster than re-creating it, however the code which determines whether a transformation of the K3_tree is done, seems to favor re-creating it, and discussed in: https://github.com/CGAL/cgal/commit/acda85233a06041f55cb62758a458bcacf801b37#r49249337
Note that with translation and scaling the split planes stay parallel to the xy xz, yz planes.
Ah so maybe the code tests !is_scaling && !is_translation then re-create the point locator, otherwise transform?
I just vtuned an affine transformation, and more specifically a translation Aff_transformation_3 translate(CGAL::Translation(), Vector_3(0.1, 0.2, 0.3));
The thing is that here the linear part of the matrix is taken to apply it to the sphere maps. We can probably improve there, as the linear part is just the identity matrix, so there is nothing to do. We have to detect it though.
Are pure translations something you do a lot?
@afabri Yes for script CAD (RapCAD, and OpenSCAD) do translation, rotation, scale, mirror, shear, etc. For example:
https://github.com/nophead/NopSCADlib/search?q=translate
The question is, if for a translation you generate a 4x3 matrix, or if you generate a transformation with the tag that makes that it only stores the translation vector.
In RapCAD I just generalized all transformation modules to construct a 4x4 matrix, and then convert to a Aff_transformation_3. https://github.com/GilesBathgate/RapCAD/blob/master/src/cgalprimitive.cpp#L632 https://github.com/GilesBathgate/RapCAD/blob/master/src/transformmatrix.cpp#L46
I think OpenSCAD does something similar: https://github.com/openscad/openscad/blob/master/src/CGAL_Nef_polyhedron.cc#L120
@afabri Test results for the above using ./transation benchmark of Nef_3_benchmarks
master | 3.47863,3.55981,3.58852,3.62595,3.76185,3.72015,3.72747,3.71695,3.62252,3.81363 | 3.661548 sec average
contender | 2.38492,2.35819,2.30894,2.42091,2.43411,2.49426,2.51332,2.48339,2.58183,2.48997 | 2.446984 sec average
Hi @GilesBathgate, is this PR still of interest or does #5617 solve the problem or sketch an alternative approach?
@afabri This is intended to address the situation in which transformations are not of the specialised implementations, and then this should increase the performance of the plane transformations by precalculating the inverse transposed matrix. The use case is probably now more of an edge case given #5617
@GilesBathgate Can you then please fix the conflicts with master, so we can start testing the branch ?
Whole testsuite lines are red. See for example: https://cgal.geometryfactory.com/CGAL/testsuite/CGAL-5.4-Ic-51/Nef_3/TestReport_lrineau_ArchLinux-CXX17-Release.gz
@GilesBathgate @sloriot This PR has a conflict with other PRs that were recently merged. Can you please resolve that conflict?
@sloriot As Giles has force-pushed a new version of the branch, there is no way to compare with the version that was tested. It will have to be re-tested.
@lrineau Of course there is a way to compare: https://github.com/CGAL/cgal/compare/1e422cc20e8d2c7cee45fd0407c335fb2ab0e4d1..55ddf453d993cdf33509adec797d877a64fae74c
But it shows the changes made to master since the original PR too. I think this would be the same if you inspected a merge commit.
Either way, all I did was a git rebase master, and then fix the conflict with git mergetool. The mergetool UI was able to resolve the conflict automatically.
I think however re-testing is always a good idea.