Matrix multiplication and row vectors
Actually a list of vec4s is a n x 4 matrix---each vector is a row---and you
can multiply on the right by a 4x3 (which is the transpose of that 3x4 you
were talking about) to get a n x 3 matrix, which is a list of vec3s.
nophead wrote
A list of vec4s is also an 4 x n matrix. So you can post multiply by 3 x 4
matrix and get a 3 x n matrix which is a list of vec3s.
On Thu, 4 Apr 2019 at 15:28, Ronaldo Persiano <
rcmpersiano@
> wrote:
Wouldn't simply
p*transpose(M)
be better, where M is 3x4?
It is a pity that my emphasis that p is a list of vectors has been
misunderstood.
OpenSCAD mailing list
Discuss@.openscad
Discuss@.openscad
--
Sent from: http://forum.openscad.org/
Sorry yes got my rows and columns mixed up.
So yes I transpose my 3 x 3 rotation matrix and add the translation to the
bottom row to make a 4 x 3 transformation matrix.
function orientate(p, r) =
let(x = r[0], y = r[1], z = r[2])
[[x.x, y.x, z.x],
[x.y, y.y, z.y],
[x.z, y.z, z.z],
[p.x, p.y, p.z]];
I augment my profile points with 1s to make it a list of 4 vectors and post
multiply that by the matrix.
//
// Generate all the surface points of the swept volume.
//
function skin_points(profile, path, loop, twist = 0) =
let(len = len(path),
last = len - 1,
profile4 = [for(p = profile) [p.x, p.y, p.z, 1]],
tangents = [tangent(path, loop ? last : 0, 0, 1),
for(i = [1 : last - 1]) tangent(path, i - 1, i, i + 1),
tangent(path, last - 1, last, loop ? 0 : last)],
rotations = [for(i = 0, rot = fs_frame(tangents);
i < len;
i = i + 1,
rot = i < len ? rotate_from_to(tangents[i - 1],
tangents[i]) * rot : undef) rot],
missmatch = loop ? calculate_twist(rotations[0], rotations[last]) :
0,
rotation = missmatch + twist
)
[for(i = [0 : last])
let(za = rotation * i / last)
each profile4 * orientate(path[i], rotations[i] * rot3_z(za))
];
It is a little faster doing a single multiplication instead of a loop that
adds the 1, multiplies and removes it again.
I think OpenSCAD matrix multiplication could be optimised a bit because it
just pushes results onto the end of vector whereas it could preallocate a
vector of the correct size and just fill it in.
On Fri, 5 Apr 2019 at 02:12, adrianv avm4@cornell.edu wrote:
Actually a list of vec4s is a n x 4 matrix---each vector is a row---and you
can multiply on the right by a 4x3 (which is the transpose of that 3x4 you
were talking about) to get a n x 3 matrix, which is a list of vec3s.
nophead wrote
A list of vec4s is also an 4 x n matrix. So you can post multiply by 3 x
4
matrix and get a 3 x n matrix which is a list of vec3s.
On Thu, 4 Apr 2019 at 15:28, Ronaldo Persiano <
rcmpersiano@
> wrote:
Wouldn't simply
p*transpose(M)
be better, where M is 3x4?
It is a pity that my emphasis that p is a list of vectors has been
misunderstood.
OpenSCAD mailing list
Discuss@.openscad
Discuss@.openscad
--
Sent from: http://forum.openscad.org/
OpenSCAD mailing list
Discuss@lists.openscad.org
http://lists.openscad.org/mailman/listinfo/discuss_lists.openscad.org
nop head wrote:
I think OpenSCAD matrix multiplication could be optimised a bit because it just pushes results onto the end of vector whereas it could preallocate a vector of the correct size and just fill it in.
Based on my reading of the source, I don't think this will speed things up significantly. OpenSCAD dynamically allocated 2 objects for each number or boolean, and 3 objects for each list or string. A 4x3 matrix has 5 lists and 12 numbers, which is 39 dynamically allocated objects. The optimization you mentioned might eliminate 1 or 2 allocations, but that's a small fraction of the total number of allocations involved.
Curv uses tagged pointers and NaN boxing (an idea I copied from Javascript and LuaJIT). Numbers and booleans occupy 64 bits (the size of a pointer or double), and require no memory allocation, instead of 2 objects: the value is stored directly. Lists and strings only use 1 allocated object, not 3. So a 4x3 matrix requires 6 dynamically allocated objects, instead of 39. Curv is significantly faster than OpenSCAD, I think this is one of the reasons.
If you want to make OpenSCAD run faster, changing the internal representation of values might make a significant difference. The simplest change is to consistently use std::make_shared for allocating all values. That would eliminate one dynamically allocated object from each value, reducing the number of objects in a 4x3 matrix from 39 to 22.
Doug Moen.
On Tue, Apr 9, 2019, at 1:25 PM, nop head wrote:
Sorry yes got my rows and columns mixed up.
So yes I transpose my 3 x 3 rotation matrix and add the translation to the bottom row to make a 4 x 3 transformation matrix.
function orientate(p, r) =
let(x = r[0], y = r[1], z = r[2])
[[x.x, y.x, z.x],
[x.y, y.y, z.y],
[x.z, y.z, z.z],
[p.x, p.y, p.z]];
I augment my profile points with 1s to make it a list of 4 vectors and post multiply that by the matrix.
//
// Generate all the surface points of the swept volume.
//
function skin_points(profile, path, loop, twist = 0) =
let(len = len(path),
last = len - 1,
profile4 = [for(p = profile) [p.x, p.y, p.z, 1]],
tangents = [tangent(path, loop ? last : 0, 0, 1),
for(i = [1 : last - 1]) tangent(path, i - 1, i, i + 1),
tangent(path, last - 1, last, loop ? 0 : last)],
rotations = [for(i = 0, rot = fs_frame(tangents);
i < len;
i = i + 1,
rot = i < len ? rotate_from_to(tangents[i - 1], tangents[i]) * rot : undef) rot],
missmatch = loop ? calculate_twist(rotations[0], rotations[last]) : 0,
rotation = missmatch + twist
)
[for(i = [0 : last])
let(za = rotation * i / last)
each profile4 * orientate(path[i], rotations[i] * rot3_z(za))
];
It is a little faster doing a single multiplication instead of a loop that adds the 1, multiplies and removes it again.
I think OpenSCAD matrix multiplication could be optimised a bit because it just pushes results onto the end of vector whereas it could preallocate a vector of the correct size and just fill it in.
On Fri, 5 Apr 2019 at 02:12, adrianv avm4@cornell.edu wrote:
Actually a list of vec4s is a n x 4 matrix---each vector is a row---and you
can multiply on the right by a 4x3 (which is the transpose of that 3x4 you
were talking about) to get a n x 3 matrix, which is a list of vec3s.
nophead wrote
A list of vec4s is also an 4 x n matrix. So you can post multiply by 3 x 4
matrix and get a 3 x n matrix which is a list of vec3s.
On Thu, 4 Apr 2019 at 15:28, Ronaldo Persiano <
rcmpersiano@
> wrote:
Wouldn't simply
p*transpose(M)
be better, where M is 3x4?
It is a pity that my emphasis that p is a list of vectors has been
misunderstood.
OpenSCAD mailing list
Discuss@.openscad
Discuss@.openscad
--
Sent from: http://forum.openscad.org/
OpenSCAD mailing list
Discuss@lists.openscad.org
http://lists.openscad.org/mailman/listinfo/discuss_lists.openscad.org
In this operation I am multiplying all the points of a 2D profile in one
multiply, so the result can be a lot bigger than the transform matrix.
Typically hundreds x 3, so that big list could be allocated and filled in
rather than grown. Probably not a great saving as you say because each
element is a 3 vector and each number is still a separate allocation.
Yes I think Python uses boxing as well and there is a lot of scope for
speeding up OpenSCAD's list handling and value handling in general.
This test sweep test takes 0 seconds in the GUI and 2.4 seconds on the
command line to generate a PNG. My fastest tests take 1.5 seconds on the
command line, so that seems to be startup and image export overhead. So I
think the computation is about 0.9 seconds. I suspect most of that is list
handling. Transforming the whole profile with one matrix multiply saves
about 0.3s
[image: sweep.png]
On Tue, 9 Apr 2019 at 23:02, Doug Moen doug@moens.org wrote:
nop head wrote:
I think OpenSCAD matrix multiplication could be optimised a bit because
it just pushes results onto the end of vector whereas it could preallocate
a vector of the correct size and just fill it in.
Based on my reading of the source, I don't think this will speed things up
significantly. OpenSCAD dynamically allocated 2 objects for each number or
boolean, and 3 objects for each list or string. A 4x3 matrix has 5 lists
and 12 numbers, which is 39 dynamically allocated objects. The optimization
you mentioned might eliminate 1 or 2 allocations, but that's a small
fraction of the total number of allocations involved.
Curv uses tagged pointers and NaN boxing (an idea I copied from Javascript
and LuaJIT). Numbers and booleans occupy 64 bits (the size of a pointer or
double), and require no memory allocation, instead of 2 objects: the value
is stored directly. Lists and strings only use 1 allocated object, not 3.
So a 4x3 matrix requires 6 dynamically allocated objects, instead of 39.
Curv is significantly faster than OpenSCAD, I think this is one of the
reasons.
If you want to make OpenSCAD run faster, changing the internal
representation of values might make a significant difference. The simplest
change is to consistently use std::make_shared for allocating all values.
That would eliminate one dynamically allocated object from each value,
reducing the number of objects in a 4x3 matrix from 39 to 22.
Doug Moen.
On Tue, Apr 9, 2019, at 1:25 PM, nop head wrote:
Sorry yes got my rows and columns mixed up.
So yes I transpose my 3 x 3 rotation matrix and add the translation to the
bottom row to make a 4 x 3 transformation matrix.
function orientate(p, r) =
let(x = r[0], y = r[1], z = r[2])
[[x.x, y.x, z.x],
[x.y, y.y, z.y],
[x.z, y.z, z.z],
[p.x, p.y, p.z]];
I augment my profile points with 1s to make it a list of 4 vectors and
post multiply that by the matrix.
//
// Generate all the surface points of the swept volume.
//
function skin_points(profile, path, loop, twist = 0) =
let(len = len(path),
last = len - 1,
profile4 = [for(p = profile) [p.x, p.y, p.z, 1]],
tangents = [tangent(path, loop ? last : 0, 0, 1),
for(i = [1 : last - 1]) tangent(path, i - 1, i, i + 1),
tangent(path, last - 1, last, loop ? 0 : last)],
rotations = [for(i = 0, rot = fs_frame(tangents);
i < len;
i = i + 1,
rot = i < len ? rotate_from_to(tangents[i - 1],
tangents[i]) * rot : undef) rot],
missmatch = loop ? calculate_twist(rotations[0], rotations[last])
: 0,
rotation = missmatch + twist
)
[for(i = [0 : last])
let(za = rotation * i / last)
each profile4 * orientate(path[i], rotations[i] * rot3_z(za))
];
It is a little faster doing a single multiplication instead of a loop that
adds the 1, multiplies and removes it again.
I think OpenSCAD matrix multiplication could be optimised a bit because it
just pushes results onto the end of vector whereas it could preallocate a
vector of the correct size and just fill it in.
On Fri, 5 Apr 2019 at 02:12, adrianv avm4@cornell.edu wrote:
Actually a list of vec4s is a n x 4 matrix---each vector is a row---and you
can multiply on the right by a 4x3 (which is the transpose of that 3x4 you
were talking about) to get a n x 3 matrix, which is a list of vec3s.
nophead wrote
A list of vec4s is also an 4 x n matrix. So you can post multiply by 3 x
4
matrix and get a 3 x n matrix which is a list of vec3s.
On Thu, 4 Apr 2019 at 15:28, Ronaldo Persiano <
rcmpersiano@
> wrote:
Wouldn't simply
p*transpose(M)
be better, where M is 3x4?
It is a pity that my emphasis that p is a list of vectors has been
misunderstood.
OpenSCAD mailing list
Discuss@.openscad
Discuss@.openscad
--
Sent from: http://forum.openscad.org/
OpenSCAD mailing list
Discuss@lists.openscad.org
http://lists.openscad.org/mailman/listinfo/discuss_lists.openscad.org
OpenSCAD mailing list
Discuss@lists.openscad.org
http://lists.openscad.org/mailman/listinfo/discuss_lists.openscad.org
OpenSCAD mailing list
Discuss@lists.openscad.org
http://lists.openscad.org/mailman/listinfo/discuss_lists.openscad.org
