kicad-developers team mailing list archive

[Andrew Zonenberg <azonenberg@xxxxxxxxxxxxxxx>]

The attached patch parallelizes per-vertex normal calculation using
OpenMP. I see a nearly 4x speedup of model loading on my quad-core
machine.

This does not address the fact that models are constantly reloaded in
lots of places they don't need to be. It's a band-aid on top of that
problem but it will also speed up first-time loading of models when
proper caching is implemented.

On Sat, 2014-08-02 at 14:14 -0400, Andrew Zonenberg wrote:
> I think one of the easiest optimizations is to add some kind of
> application-wide cache in RAM such that individual models are only
> loaded once (but still of course reloaded when kicad is restarted).
> 
> It's OK to have O(n) load time for N distinct models, even with a large
> constant factor. What's not OK is to have O(N*M*P) load time if you have
> M instances each of N models and refresh the 3D view P times.
> 
> Based on my measurements of X3D files in particular (as this is what all
> of my large models are) normal calculation is indeed one of the biggest
> bottlenecks.
> 
> For the Molex HDMI connector in particular, I measure:
> * 502.45 ms for wxXmlDocument::Load()
> * 217.92 ms for the sum of all of the ReadTransform() calls
> * 2092.19 ms for the sum of all openGL_RenderAllChilds() calls
> * Of this, 2082.76 ms is spent in calcPerFaceNormals().
> 
> I'm going to try slightly refactoring calcPerFaceNormals to use OpenMP
> and multithread the normal calculations, will report on my results
> shortly.
> 
> On Sat, 2014-08-02 at 17:53 +0000, Mário Luzeiro wrote:
> > Hi Andrew,
> > 
> > You are right, it will be special noticeable for very large (> 10K faces) models.
> > The major time consuming are now in normal calculation. The algorithm I had implemented IMO is good (probably can be optimized a little more) but it is a nature slow algorithm. (you can see lots of for loops)..
> > 
> > Since I post my first patch with this new additions I point some of this issues, see "Know issues / missing features"
> > https://lists.launchpad.net/kicad-developers/msg14136.html
> > 
> > I believe that a correct proper implementation for this will need some internal discussion with KiCad masters, because I think we have some options to be discussed:
> > 
> > - Calc the normals and update the original file with the processed normals so next time they don't need to be calculated. (it will change / overwrite the original file. It need some type of exporter to that file or to some unique format for all models).
> > - Calc the normals per project and store it in a cache folder in the project?
> > - Use faster normal algorithm for large models.
> > - Do not calc normals, just use if the model have embedded normals. (So you must use an external software to process it)
> > ....
> > 
> > Meanwhile there are some options that can be made:
> > First read all different files, then, render it. (Now as you pointed it reads and process every copies :/ .. It was like that and I didn't had time to change)
> > For this, the functions
> > BuildFootprintShape3DList
> > ReadAndInsert3DComponentShape
> > ReadData and all S3D_MODEL_PARSER Load (for the different filetypes) must be changed in the way it removes the openGL render from Loadfile.. so it will first load then other function will call the render.
> > 
> > This is relative easy to be done, but sorry I don't have time now to spend on this improvement. so answering your question, I am not working on it and I don't thing anybody is working.
> > 
> > If you will start doing it, fell free to enter in contact with me and I can help and discuss ideas / implementation with you!
> > 
> > thanks!
> > 
> > Regards,
> > Mario Luzeiro
> > 
> > p.s.: because I will soon start using kicad again as a user and will need to load beautiful 3d models.. and faster :) so it would be nice to have this optimized feature!
> > 
> > ________________________________________
> > From: Kicad-developers [kicad-developers-bounces+mrluzeiro=ua.pt@xxxxxxxxxxxxxxxxxxx] on behalf of Andrew Zonenberg [azonenberg@xxxxxxxxxxxxxxx]
> > Sent: 02 August 2014 19:30
> > To: kicad-developers@xxxxxxxxxxxxxxxxxxx
> > Subject: [Kicad-developers] Very inefficient loading of 3D models
> > 
> > So I added a few print statements to my copy of the 3D viewer in order
> > to figure out why the 3D viewer was so slow...
> > 
> > The results were very interesting.
> > 
> > http://pastebin.com/7s8gXVjY
> > 
> > 1) There is no caching whatsoever! The VRML/X3D files are loaded from
> > scratch each time they're instantiated in the board. If I have three
> > copies of a high-poly connector model, the VRML is loaded from disk and
> > parsed three times. This should be an O(1) operation rather than O(n),
> > with polygon data stored in some kind of application-wide cache and
> > referenced for each model instance.
> > 
> > 2) The instantiated models are thrown out as soon as the 3D viewer
> > window is closed or the "reload board" button in the 3D viewer window is
> > clicked.
> > 
> > 3) Models take an absurd amount of time to load. Three seconds for an
> > optimized release build to load a Molex HDMI connector (14k vertices and
> > 9k faces) is completely unreasonable, FreeCad loads it in a few hundred
> > ms (too fast to measure easily).
> > 
> > Is anybody working on this already or should I start optimizing myself?
> > 
> > --
> > Andrew Zonenberg
> > PhD student, security group
> > Computer Science Department
> > Rensselaer Polytechnic Institute
> > http://colossus.cs.rpi.edu/~azonenberg/
> 
> _______________________________________________
> Mailing list: https://launchpad.net/~kicad-developers
> Post to     : kicad-developers@xxxxxxxxxxxxxxxxxxx
> Unsubscribe : https://launchpad.net/~kicad-developers
> More help   : https://help.launchpad.net/ListHelp

-- 
Andrew Zonenberg
PhD student, security group
Computer Science Department
Rensselaer Polytechnic Institute
http://colossus.cs.rpi.edu/~azonenberg/

=== modified file '3d-viewer/3d_mesh_model.cpp'
--- 3d-viewer/3d_mesh_model.cpp	2014-08-02 07:46:47 +0000
+++ 3d-viewer/3d_mesh_model.cpp	2014-08-02 18:26:30 +0000
@@ -354,13 +354,16 @@
     }
 
     m_PerFaceVertexNormals.clear();
+    
+    // Pre-allocate space for the entire vector of vertex normals so we can do parallel writes
+    m_PerFaceVertexNormals.resize(m_CoordIndex.size());
 
     // for each face A in mesh
+    #pragma omp parallel for
     for( unsigned int each_face_A_idx = 0; each_face_A_idx < m_CoordIndex.size(); each_face_A_idx++ )
     {
         // n = face A facet normal
-        std::vector< glm::vec3 > face_A_normals;
-        face_A_normals.clear();
+        std::vector< glm::vec3 >& face_A_normals = m_PerFaceVertexNormals[each_face_A_idx];
         face_A_normals.resize(m_CoordIndex[each_face_A_idx].size());
 
         // loop through all 3 vertices
@@ -402,7 +405,5 @@
             }
             
         }
-
-        m_PerFaceVertexNormals.push_back( face_A_normals );
     }
 }

Attachment: signature.asc
Description: This is a digitally signed message part