Optimization of Matrix operations

[thehans]

I noticed that matrix transformations as they are currently implemented are applied immediately to the CSG objects one at a time.
This misses out on one of the most powerful features of applying matrix tranformations in that the small 4x4 matrices can be combined before applying to every vertex in a possibly very complex model.

I would suggest that CSG objects can each store their own transformation matrix as a property, and the application of this matrix to the vertices is deferred until polygons are requested.

So if there are multiple consecutive transformations, the CSG object just multiplies the transformation matrices and and sets a needsTransform flag if not already set.

I think this would require most if not all internal references to [CSG].polygons replaced with a getter that will check if needsTransform is set, and apply the internal matrix at that time.

If I have some time in the near future I can work on implementing this, but also wanted to open a discussion and see what others think.

[joostn]

Hi Hans,

For the CSG operations (union etc) the actual transformed coordinates are needed. In my designs I usually have one or two transformations on objects (usually a translation and a rotation), typically followed by union or subtract. The CSG operations are much more costly (quadratic complexity) than the transformations (linear complexity). So I expect it will speed things up a bit but not very much in practise.

If you have time to look into improving performance (great!) my approach would be to profile a running rendering (use the Profiler tab in Chrome, and Debug mode in OpenJsCad so that it doesn't use web workers) and see where the bottlenecks are. Probably some improvements can be made by reorganising bits of code inside the inner loops.

Just my idea though, I might be wrong of course.

[bebbi]

I like the general idea behind queuing. Though like joostn I’m not sure about concrete impact for my designs, they mostly have transforms and booleans following one another. Might be worth a thought experiment whether booleans could be lazy too - to pull together all transforms before and after bools, and to execute bools late together, profiting from balanced tree feature. Not sure it’s a benefit in all cases though.

On 27 Mar 2015, at 08:02, joostn notifications@github.com wrote:

Hi Hans,

For the CSG operations (union etc) the actual transformed coordinates are needed. In my designs I usually have one or two transformations on objects (usually a translation and a rotation), typically followed by union or subtract. The CSG operations are much more costly (quadratic complexity) than the transformations (linear complexity). So I expect it will speed things up a bit but not very much in practise.

If you have time to look into improving performance (great!) my approach would be to profile a running rendering (use the Profiler tab in Chrome, and Debug mode in OpenJsCad so that it doesn't use web workers) and see where the bottlenecks are. Probably some improvements can be made by reorganising bits of code inside the inner loops.

Just my idea though, I might be wrong of course.

— Reply to this email directly or view it on GitHub.

[z3dev]

@thehans this issue was a true inspiration to OpenSCAD.org V2. The implementation of each geometry in V2 has both data structure and transformation matrix. And transforms (rotate, translate, scale, etc) only apply to the matrix. Thanks.

I think this can be closed now.

[thehans]

Oh, what a blast from the past! As I'm sure you know, I haven't been actively involved in the project for years, but still neat to hear I inspired some changes like that.

I'll go ahead and close it then :)