Munther Hindi has updated some timing tests comparing creation of CAD type Solids by Tessellation compared to a number of booleans
Dear @KeithSloan
Thank you for the detailed study. I do not have the insights of how the tracking within a tessellated solid works, but by doing something similar to you (I parametrized points on the surface of a sphere and then built a tessellated solid with different number of facets) I got to the conclusion the tracking speed depends on the number of facets squared. Maybe you can conduct a similar study by changing the number of facets?
By the way, may I ask if have you noticed any bug in FreeCAD when translating the geometry to GDML/stl?
Thank you for your time.
Best,
Alvaro
Thanks for your comment.
Munther is very busy trying to look at symmetry and spreadsheet support and I am trying to check things still work with the upcoming FreeCAD 1.0 Release. candidates. Munther does not check the forum very often so I have given him a heads up on your comment.
As to FreeCAD created Tessellations, there are a number of ways of creating a mesh, I am aware that sometimes facets get created that Geant4 is not happy about, normally too small and this is frustrating as one only finds out when loading the Geometry in Geant4
Similarly using Gmsh Min, it can sometimes produce a Quad Facet that should be planar and Geant4 is not happy about, saying it is not.
I should add these to known issues, I started a branch trying to look into solutions but not got very far, we ideally need more hands to the pumps ( Just the two of us )
By the way the latest version of the workbench does automatic tessellations for FreeCAD objects which are FeaturePython objects and not native GDMLObjects. Best to set the material via workbenches Set Material facility, otherwise it uses the default.
I don’t know how Geant4 builds its geometry, but the few tests I have done do not show that tracking speed depends on the square of the number of facets. In one case the number of faces was increased by a factor of 3.64, but the tracking time only increased by a factor of 1.92. I did another test specifically testing sphere tessellations. In one test the number of facets was 80 and in another 320. Although the number of facets increased by a factor of 4, the tracking time increased by only a factor of 2.3, not a factor of 16 (4^2). The results will depend very much on the type of particle, how frequently a test of which face has been crossed is needed, etc; hard to generalize.
Munther
Just to butt in here…
I do know that navigation of tessellations has been “optimised” by Evgueni Tchernaev over the last few years. He has introduced some very smart algorithms. He is a very smart guy. So it is not a huge penalty to use tessellations, and there is a huge gain, of course, in ease and reliability of implementation.
Evgueni, do have any comments?
For the record, the tests I did were with geant4-v11.2.1, but I was obtaining qualitatively similar results in 10.5. A small writeup on the tests is here
@Munther_Hindi I am sure you mentioned to me that it was important to run the tests in a certain way, otherwise you got strange results, maybe Alvaro’s @atolosad runs being related to square of facets might also not have been done in the best environment?
The “optimised” navigation in G4TessellatedSolid (as well as in G4MultiUnion) was not implemented by me, but by Marek Gayer in 2012. I don’t know the details of the implementation, but in my experience this optimisation works well, and I would expect that in general the dependence “tracking time vs number of triangles” should be better than the number of triangles squared. However, I do not exclude that this may depend on the shape of the solid.
The “strange” results were obtained when I neglected to turn off visualization during the tests. With visualization turned on, most of the time was spent waiting for the visualizer to process events and the timing did not reflect the tracking time. I found a comment by @allison in the forum that reminded me I should turn off visualization when doing timing tests. I am not sure what timing tests @atolosad was conducting, so I don’t know why he might have gotten the results he did.
Evgueny, do you know by any chance if the facets are traversed in any particular order when testing which facet a particle crossed? One can imagine an optimization where the facets are first sorted by area and the facets with the largest area tested first. If the facets are traversed in the order they were defined for the tessellation, then perhaps we can pre-sort them in the input (ie., in the gdml file, in our case).
As far as I know, the area is not used for optimisation. If I am not mistaken, the structure used for the optimisation is a 3D grid, where each grid cell contains a list of triangles that intersect the cell.
Thank you! One of these days I might get the courage to look into the code and try to understand what’s going on.