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...@lists.launchpad.net] on behalf of > > Andrew Zonenberg [azonenb...@drawersteak.com] > > Sent: 02 August 2014 19:30 > > To: kicad-developers@lists.launchpad.net > > 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@lists.launchpad.net > 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 );
}
}
signature.asc
Description: This is a digitally signed message part
_______________________________________________ Mailing list: https://launchpad.net/~kicad-developers Post to : kicad-developers@lists.launchpad.net Unsubscribe : https://launchpad.net/~kicad-developers More help : https://help.launchpad.net/ListHelp
