Small Vector redux: requirements gathering
E. Mark Ping
matrices), and possible inclusion of a small vector/matrix library in
the C++ standard library. There was good discussion about the various
requirements, but I saw no post or posts that gathered the
requirements together. I've looked at Walter Landry's FTensor
library, as well as John Nagle's alebra3 library and the Blitz
tinyarray. I believe they are all good work, but don't address the
needs that most people are looking for in such a package (though I
could be wrong). The FTensor library, for instance, while technically
superb is likely unfamiliar to most C++ programmers (in fact, I just
missed getting a minor in physics, but am still a little shaky with
tensors). The algebra3 library is also quite nice, but the version
I've looked at assumes 'double' as the numerical type.
I've been working on a subset of the requirements mentioned in the
newsgroup (and got it working on both VC6 and Comeau 4.3) and would be
willing to pursue it to its conclusion. My background: I've worked
with graphics programming for several years, primarily in OpenGL, but
with some Direct3D experience, and some computational geometry. With
that in mind, I've collected most of the comments I could find, and
list the requirements below.
I don't know if this would belong in Boost, since it has explicitly
stated that optimization issues are not the primary concern. In
constrast, performance must be one of the overriding concerns for this
library if people are going to use it. I've roughly split up the
requirements into two groups: functionality and optimizations. Note
that I mark issues that I've already implemented with "+" and issues
that I haven't with "-"
Please add your comments, requirements, etc. Perhaps we can work
together to find a solution that will be useful for a large part of
the C++ community.
The master copy of this document is online at:
http://www.csua.berkeley.edu/~emarkp/small_vector.txt
Basic Assumptions:
+ The primary vectors and matrices would be vectors of 3 and 2
dimensions (and 4D homogeneous vectors). The primary matrices will
be of size (4,4) and (3,3) (perhaps (2,2) as well).
+ The classes will be templates for both the numerical type and size
of dimensions.
For discussion purposes, I'll call the vector class:
template <class T, int D> tvector;
and the matrix class:
template <class T, int M, int N> tmatrix;
- Additionally, there (likely) should be classes for homogeneous
matrices and vectors.
For discussion purposes, I'll call the homogeneous vector:
template <class T> hvec4; //for 4D homogeneous vectors
and the matrix class:
template <class T> hmat4; //for 4D homogeneous matrices
- hmat3 and hvec3 classes should be considered for 2D work.
- It is unclear if the library should reside in a namespace.
Requirements:
+ compile on VC6, VC7, Comeau 4.3.0
Issues:
gcc (which version(s)?
other compilers?
+ Specializations for square matrices which provide functions only
appropriate for a square matrix (invert, identity, etc.)
+ operator overloading ( vector: * for dot, ^ for cross, * for matrix)
+ row-major vs. column-major matrices specified at compile-time--can
convert from one to another (this is useful because OpenGL uses
column-major matrices, and Direct3D uses row-major matrices).
- Concatenate operation which is configurable -- for instance,
right-multiply vs. left-multiply. Again this would be useful for
OpenGL vs. Direct3D, for example.
+ Conversion operators from one vec type/size to another.
Issues:
Should conversion be explicit or implicit?
Should conversion be allowed for both size and type in one conversion?
+ As close to POD as possible
Issues:
I'm not sure if a template instantiation can be considered a POD.
I've had to deviate from pure POD to overcome limitations of VC6.
+ Access to data with begin(), end() like STL
Less-resolved issues:
- Should row vectors and column vectors be differentiated, and
corresponding matrix/vector operations be enforced as correct?
+ Should mixed type operations be allowed?
(tvec<3, float> ^ tvec<3, double> returns tvec<3, double>)
- Should traits be allowed for user-defined types?
(Especially for a square-root operator, for normalizing tvect<T>
where T isn't float or double.)
Performance
+ As much inline code as possible.
Ideally, this could be configured. Might be difficult with
operators, but the operators could have functions which are
explicitly inlined.
+ Loops unrolled where possible (matrix * vec, etc.)
+ no virtual functions
+ Optimized multiplication operations with homogeneous matrices and
non-homogeneous vectors. Allow operations like hmat4<T> * tvec<T,3>
without creating temporary 4D vector first.
+ All conditionals known at compile-time resolved at compile-time.
+ Default initialization does nothing--the user must explicitly set elements.
--
Mark Ping
ema...@soda.CSUA.Berkeley.EDU
---
[ comp.std.c++ is moderated. To submit articles, try just posting with ]
[ your news-reader. If that fails, use mailto:std...@ncar.ucar.edu ]
[ --- Please see the FAQ before posting. --- ]
[ FAQ: http://www.jamesd.demon.co.uk/csc/faq.html ]
Kresimir Fresl
E. Mark Ping wrote:
> A little while ago, there was a discussion about small vectors (and
> matrices), and possible inclusion of a small vector/matrix library in
> the C++ standard library. There was good discussion about the various
> requirements, but I saw no post or posts that gathered the
> requirements together. I've looked at Walter Landry's FTensor
> library, as well as John Nagle's alebra3 library and the Blitz
> tinyarray. I believe they are all good work, but don't address the
> needs that most people are looking for in such a package (though I
> could be wrong). The FTensor library, for instance, while technically
> superb is likely unfamiliar to most C++ programmers (in fact, I just
> missed getting a minor in physics, but am still a little shaky with
> tensors). The algebra3 library is also quite nice, but the version
> I've looked at assumes 'double' as the numerical type.
It could be also useful to look at `Tiny Vector Matrix library using
Expression Templates' (a.k.a. tvmet):
fres
Ross Smith
[I'll leave uncommented the parts I agree with]
> Basic Assumptions:
> + The primary vectors and matrices would be vectors of 3 and 2
> dimensions (and 4D homogeneous vectors). The primary matrices will
> be of size (4,4) and (3,3) (perhaps (2,2) as well).
>
> + The classes will be templates for both the numerical type and size
> of dimensions.
>
> For discussion purposes, I'll call the vector class:
> template <class T, int D> tvector;
>
> and the matrix class:
> template <class T, int M, int N> tmatrix;
>
> - Additionally, there (likely) should be classes for homogeneous
> matrices and vectors.
>
> For discussion purposes, I'll call the homogeneous vector:
> template <class T> hvec4; //for 4D homogeneous vectors
>
> and the matrix class:
> template <class T> hmat4; //for 4D homogeneous matrices
>
> - hmat3 and hvec3 classes should be considered for 2D work.
The homogeneous types, if present, should be templated in the same way
as the normal ones. Personally I'm not convinced that separate
homogeneous types are necessary.
> - It is unclear if the library should reside in a namespace.
>
> Requirements:
> + compile on VC6, VC7,
Absolutely not. Losing partial specialisation is far too restrictive.
> Comeau 4.3.0
> Issues:
> gcc (which version(s)?
> other compilers?
You're making the same mistake as the web design dweebs with their "this
page only usable with MSIE 6.1234" crap. Taking specific compilers into
account is the wrong approach. Design it in C++ -- as in, the language
defined by ISO 14882 -- and _after_ finishing the design, implement it
to work with as many compilers as can handle it.
> + Specializations for square matrices which provide functions only
> appropriate for a square matrix (invert, identity, etc.)
>
> + operator overloading ( vector: * for dot, ^ for cross, * for matrix)
The ^ operator is definitely wrong for cross product, since it has a
lower precedence than +. The only reasoanble choice for the second
multiplication operator is %. I tried using * for cross and % for dot
for a while, but eventually switched to named functions. I'm still
undecided about the best approach.
> + row-major vs. column-major matrices specified at compile-time--can
> convert from one to another (this is useful because OpenGL uses
> column-major matrices, and Direct3D uses row-major matrices).
>
> - Concatenate operation which is configurable -- for instance,
> right-multiply vs. left-multiply. Again this would be useful for
> OpenGL vs. Direct3D, for example.
This makes no sense. Right vs left multiplication would be determined by
the order in which you write the operands, obviously.
> + Conversion operators from one vec type/size to another.
> Issues:
> Should conversion be explicit or implicit?
> Should conversion be allowed for both size and type in one
> conversion?
Why would conversion between different sizes be allowed at all?
> + As close to POD as possible
> Issues:
> I'm not sure if a template instantiation can be considered a POD.
> I've had to deviate from pure POD to overcome limitations of VC6.
We don't need a POD, all we need is a pointer to the internal array
representation.
> + Access to data with begin(), end() like STL
>
> Less-resolved issues:
> - Should row vectors and column vectors be differentiated, and
> corresponding matrix/vector operations be enforced as correct?
I'm undecided on this one too. At the moment I don't make the
distinction, but after reading Jim Blinn's articles on the subject, I'm
starting to lean towards implementing the full tensor concept. As he
points out, that's the only way to make vector and matrix geometry
operations that really make sense, without introducing arbitrary rules
of thumb.
> + Should mixed type operations be allowed?
> (tvec<3, float> ^ tvec<3, double> returns tvec<3, double>)
>
> - Should traits be allowed for user-defined types?
> (Especially for a square-root operator, for normalizing tvect<T>
> where T isn't float or double.)
>
> Performance
> + As much inline code as possible.
> Ideally, this could be configured. Might be difficult with
> operators, but the operators could have functions which are
> explicitly inlined.
Why would it be difficult with operators?
> + Loops unrolled where possible (matrix * vec, etc.)
>
> + no virtual functions
>
> + Optimized multiplication operations with homogeneous matrices and
> non-homogeneous vectors. Allow operations like hmat4<T> * tvec<T,3>
> without creating temporary 4D vector first.
>
> + All conditionals known at compile-time resolved at compile-time.
>
> + Default initialization does nothing--the user must explicitly set
> elements.
--
Ross Smith ..................................... Auckland, New Zealand
r-s...@ihug.co.nz ...................................................
"A specter is haunting Wall Street; it is the specter
of honest accounting." -- Arthur D. Hlavaty
E. Mark Ping
>
>It could be also useful to look at `Tiny Vector Matrix library using
>Expression Templates' (a.k.a. tvmet):
>
> http://tvmet.sourceforge.net/
>
Good point. I hadn't heard of this library before. A brief perusal
adds one more requirement:
- The License must be totally free--that is, anyone can
use/modify/fold/spindle/mutilate the library at will, use source
anywhere, etc. No GPL or LGPL.
The library looks very sound technically, and appears to address many
of the issues that were raised. It's sad about the license. I can't
imagine any production code using it.
--
Mark Ping
ema...@soda.CSUA.Berkeley.EDU
Noah Stein
news:alp7k7$1u0t$1...@agate.berkeley.edu...
> - Additionally, there (likely) should be classes for homogeneous
> matrices and vectors.
I've been reading up on some relevant mathematical topics lately, and I
think that "homogenous" lacks specificity when referring to what the
computer graphics community is using vis a vis vectors and matrices.
Affine, projective, and Grassman spaces all use a homogeneous representation
but have some differing fundamentals under the hood. Please check out "On
the Algebraic and Geometric Foundations of Computer Graphics" by Ron Goldman
in ACM Transactions on Graphics, Vol. 21, No. 1 (January 2002). It has a
good overview of the subject.
> Requirements:
> + compile on VC6, VC7, Comeau 4.3.0
> Issues:
> gcc (which version(s)?
> other compilers?
Moving forward, VC6 compatibility will become less and less of an issue.
>From the standpoint of a proposal to be added to the next standard, a
non-PTS Microsoft compiler will long have since been a non-issue for over
98% of the coding public. The other 2% probably isn't expecting the ability
to use much of anything from a future standards document.
> + Specializations for square matrices which provide functions only
> appropriate for a square matrix (invert, identity, etc.)
I agree. It's trivial to implement with compile-time checking.
> + row-major vs. column-major matrices specified at compile-time--can
> convert from one to another (this is useful because OpenGL uses
> column-major matrices, and Direct3D uses row-major matrices).
I agree: the library should support different storage orders for matrices.
> - Concatenate operation which is configurable -- for instance,
> right-multiply vs. left-multiply. Again this would be useful for
> OpenGL vs. Direct3D, for example.
I agree with Ross about this. I've posted before on the original thread of
this topic that it's dangerous to change the definition of a vector-matrix
or matrix-vector multiplication from its mathematical definition.
> + Conversion operators from one vec type/size to another.
> Issues:
> Should conversion be explicit or implicit?
> Should conversion be allowed for both size and type in one conversion?
Disagree. There is no "natural" conversion between vectors of different
dimensionality. I believe that the correct way is to use an NxM matrix to
represent the mapping between spaces. Having said that, if you have
application-specific shortcuts, by all means write a simple conversion
function that strips the last N coordinates when reducing dimesion or adds
zeros when increasing dimension... if that's what you want.
>
> + As close to POD as possible
> Issues:
> I'm not sure if a template instantiation can be considered a POD.
> I've had to deviate from pure POD to overcome limitations of VC6.
I disagree. I think that a number of useful formats do not fit the
definition of POD.
> + Access to data with begin(), end() like STL
This doesn't hurt. At the same time, what's the rationale? From the little
I've read on MTL, it uses an STL-style abstraction to support its
operations. I think the proper handling of iteration requires some serious
thought. What's the order of elements? Is a matrix considered to be a
container of vectors which have their own iterators? I don't think so, but
I know others who do.
> Less-resolved issues:
> - Should row vectors and column vectors be differentiated, and
> corresponding matrix/vector operations be enforced as correct?
I have not made up my mind on this issue. I've implemented it in a library
before, but I'm not entirely sure its importance. What do others think?
> + Should mixed type operations be allowed?
> (tvec<3, float> ^ tvec<3, double> returns tvec<3, double>)
I've found implicit type promotion to be the most difficult part of template
expressions. It's tough to get a system that's simple and extensible. With
a nod towards Ross, I think it's impossible to have a simple, extensible
promotoin system without the aid of PTS. I'm not convinced yet, but I'm
very close. With that said, I think that implicit promotion is a good
feature or at least a good one to argue about. :)
> - Should traits be allowed for user-defined types?
> (Especially for a square-root operator, for normalizing tvect<T>
> where T isn't float or double.)
I think this issue is not part of the vector-matrix library's
responsibilities. It is the responsibility of the UDT author.
> Performance
> + As much inline code as possible.
> Ideally, this could be configured. Might be difficult with
> operators, but the operators could have functions which are
> explicitly inlined.
There's more to performance than inlining everything. If every
matrix-matrix multiply is inlined, the code might get much larger and slower
because of the lack of cache coherency.
> + Loops unrolled where possible (matrix * vec, etc.)
>
> + no virtual functions
>
Agree with both.
> + Optimized multiplication operations with homogeneous matrices and
> non-homogeneous vectors. Allow operations like hmat4<T> * tvec<T,3>
> without creating temporary 4D vector first.
I disagree. I don't think you can multiply a 3d vector with a homogeneous
matrix. Does that vector represent a vector or a point, i.e. in affine
space, is the 4th value a 0 or 1? You really can't say; therefore, I
believe some sort of explicit "conversion" must occur. I believe, though,
that this specified conversion may be done with no overhead.
> + All conditionals known at compile-time resolved at compile-time.
>
> + Default initialization does nothing--the user must explicitly set
elements.
Agree 100%
-------------------------
A few weeks ago, I started another vector-matrix library with template
expressions. It already contains all the features here I agree with and it
works under VC6. Currently, the promotion engine is only stubbed out, but
it does do implict conversions. It currently uses explicit for loops, but
those will be unrolled at compilation time soon. There's also some caching
I'd like to add (so expressions of the form M*M*M don't completely unroll
and bloat). Besides that, there's some algorithms I haven't implemented
such as inverse and the determinant. I'd also like to examine the assembly
code first so I can ensure that the architecture is performing efficiently.
The library is similar to the last one I did, so I expect the efficiency to
be there. I'd just like to ensure it.
-- Noah
E. Mark Ping
Ross Smith <r-s...@ihug.co.nz> wrote:
>> - hmat3 and hvec3 classes should be considered for 2D work.
>
>The homogeneous types, if present, should be templated in the same way
>as the normal ones. Personally I'm not convinced that separate
>homogeneous types are necessary.
Agreed with the first sentence. My existing implementation has hvec4
derived from tvec4, with additional member functions. The primary
benefit is to allow the matrix and vectors to do any special
optimization for homogeneous cases. For instance, an
hmat4<T> * hvec4<T> is the same operation as tmat<T,4,4> * tvec<T,4>
but hmat4<T> * tvec<T,3> can remove 4 multiplications because the
corresponding hvec4<T> has 1 as the value of the homogeneous
component.
>> Comeau 4.3.0
>> Issues:
>> gcc (which version(s)?
>> other compilers?
>
>You're making the same mistake as the web design dweebs with their "this
>page only usable with MSIE 6.1234" crap. Taking specific compilers into
>account is the wrong approach. Design it in C++ -- as in, the language
>defined by ISO 14882 -- and _after_ finishing the design, implement it
>to work with as many compilers as can handle it.
The only compiler I have which does PTS is Comeau 4.3.0. I don't
evevn know how well current gcc works (haven't stress tested it much).
Implementing to the standard in such a way that few people can compile
the library isn't very useful.
Functionally, I don't see a difference between what I proposed and
what your last sentence (after the --) reads.
>The ^ operator is definitely wrong for cross product, since it has a
>lower precedence than +.
Good point.
> The only reasoanble choice for the second
>multiplication operator is %. I tried using * for cross and % for dot
>for a while, but eventually switched to named functions. I'm still
>undecided about the best approach.
I've waffled back and forth too on the operator vs. named function
approach. Ideally, both would be available. I don't know
>> - Concatenate operation which is configurable -- for instance,
>> right-multiply vs. left-multiply. Again this would be useful for
>> OpenGL vs. Direct3D, for example.
>
>This makes no sense. Right vs left multiplication would be determined by
>the order in which you write the operands, obviously.
Have you implemented code that handles both OpenGL and Direct3D?
OpenGL uses a right-handed coordinate system. Direct3D is
left-handed. This in addition to the difference in the matrices.
The idea of a concatenate operator would be to allow this to be
configurable. However, your point is valid--perhaps this is a
function best implented outside the library, but following similar
design.
>> + Conversion operators from one vec type/size to another.
>> Issues:
>> Should conversion be explicit or implicit?
>> Should conversion be allowed for both size and type in one
>> conversion?
>
>Why would conversion between different sizes be allowed at all?
It's not uncommon to work with 2D vectors in the plane and then push
them into 3D space, or vice versa.
>> + As close to POD as possible
>> Issues:
>> I'm not sure if a template instantiation can be considered a POD.
>> I've had to deviate from pure POD to overcome limitations of VC6.
>
>We don't need a POD, all we need is a pointer to the internal array
>representation.
Fair enough.
>> Less-resolved issues:
>> - Should row vectors and column vectors be differentiated, and
>> corresponding matrix/vector operations be enforced as correct?
>
>I'm undecided on this one too. At the moment I don't make the
>distinction, but after reading Jim Blinn's articles on the subject, I'm
>starting to lean towards implementing the full tensor concept. As he
>points out, that's the only way to make vector and matrix geometry
>operations that really make sense, without introducing arbitrary rules
>of thumb.
Again, I suspect that the vast majority of programmers are familiar
with vectors, fewer with matrices, and very few with tensors.
>> Performance
>> + As much inline code as possible.
>> Ideally, this could be configured. Might be difficult with
>> operators, but the operators could have functions which are
>> explicitly inlined.
>
>Why would it be difficult with operators?
Perhaps I was overly terse. I meant that having an inline version and
a non-inline version might be difficult for operators. I think it's
not as much of an issue as I thought at first.
--
Mark Ping
ema...@soda.CSUA.Berkeley.EDU
Noah Stein
> >Why would conversion between different sizes be allowed at all?
>
> It's not uncommon to work with 2D vectors in the plane and then push
> them into 3D space, or vice versa.
Although common, there's no definite method of converting between the plane
and space. When modelling the real world, if the y-axis is used to denote
elevation, most plane operations will involve the x & z coordinates. To
remove a coordinate from the middle is probably not intuitive for a library.
I prefer to have x & y define the ground plane, but I know more people who
prefer x & z, and I don't think that the library should prefer one over the
other for an implicit conversion.
-- Noah
Walter Landry
> The FTensor library, for instance, while technically superb is
> likely unfamiliar to most C++ programmers (in fact, I just missed
> getting a minor in physics, but am still a little shaky with
> tensors).
I feel that Tensor's and Index's are similar in complexity to
Container's and Iterator's. It is certainly valid to reduce
complexity as much as possible, but some of the issues you discuss
(operator overloading and resizing) have simple solutions with tensor
notation.
> Basic Assumptions:
> + The primary vectors and matrices would be vectors of 3 and 2
> dimensions (and 4D homogeneous vectors). The primary matrices will
> be of size (4,4) and (3,3) (perhaps (2,2) as well).
>
> + The classes will be templates for both the numerical type and size
> of dimensions.
I'm not exactly sure what you mean here. You're saying that there are
only certain sizes, but that the size is a template argument? Are you
saying that these sizes of vectors and matrices are preferred? That
is, only these sizes will have all of the operations defined? I
wouldn't be happy with such a limitation, especially since it doesn't
seem necessary.
> - Additionally, there (likely) should be classes for homogeneous
> matrices and vectors.
>
> For discussion purposes, I'll call the homogeneous vector:
> template <class T> hvec4; //for 4D homogeneous vectors
>
> and the matrix class:
> template <class T> hmat4; //for 4D homogeneous matrices
>
> - hmat3 and hvec3 classes should be considered for 2D work.
Homogeneous vectors seem a bit too specialized for standards. As far
as I can tell, they are only used in graphics work.
I also don't understand why they wouldn't be templated by dimension.
> - It is unclear if the library should reside in a namespace.
Why wouldn't it just go into std::?
> Requirements:
> + compile on VC6, VC7, Comeau 4.3.0
> Issues:
> gcc (which version(s)?
This one is easy. The GCC people have recently released version 3.2,
and all of the major Linux distributors (RedHat, Mandrake, Suse,
Debian) as well as FreeBSD are committed to using that version. GCC
3.2 also has a (mostly) stable ABI. For most other platforms, GCC is
not the system compiler, so it is not crucial to specify a version.
> + operator overloading ( vector: * for dot, ^ for cross, * for matrix)
So there will be no way to perform an outer product? Also, using the
^ operator for cross products, while understandable, is a little
confusing for the same reason it wasn't used for exponentiation.
Also, cross products only work in 3D.
> + row-major vs. column-major matrices specified at compile-time--can
> convert from one to another (this is useful because OpenGL uses
> column-major matrices, and Direct3D uses row-major matrices).
This is also useful for people who have to interoperate with Fortan,
since it stores arrays in a different order than C.
> - Concatenate operation which is configurable -- for instance,
> right-multiply vs. left-multiply. Again this would be useful for
> OpenGL vs. Direct3D, for example.
I thought the consensus was that this was too dangerous. What people
really wanted was to be able to change storage order (above).
> + Conversion operators from one vec type/size to another.
> Issues:
> Should conversion be explicit or implicit?
Size should be explicit, but type follows the usual rules.
> Should conversion be allowed for both size and type in one conversion?
Why not?
> Less-resolved issues:
> - Should row vectors and column vectors be differentiated, and
> corresponding matrix/vector operations be enforced as correct?
I considered doing the equivalent thing for my tensor library. For
me, the extra effort wasn't worth the additional implementation
effort. Be aware that this will require four versions of a matrix
because you have to make these four operations work
Row=M*Row
Row=M*Column
Column=M*Row
Column=M*Column
> + Should mixed type operations be allowed?
> (tvec<3, float> ^ tvec<3, double> returns tvec<3, double>)
>
> - Should traits be allowed for user-defined types?
> (Especially for a square-root operator, for normalizing tvect<T>
> where T isn't float or double.)
For both of these, why not?
> Performance
<snip lots of useful techniques>
All good things, though some of them may be redundant. You may find
that it takes a *lot* of work to get it all fast, though. Since you
claimed to aready have an implementation, what are the performance
results like with your compilers compared to hand coding? How does it
compare to ublas, tinyarray, algebra3, and my library?
Regards,
Walter Landry
wla...@ucsd.edu
Noah Stein
news:alqqjm$i87$1...@lust.ihug.co.nz...
> > - Should row vectors and column vectors be differentiated, and
> > corresponding matrix/vector operations be enforced as correct?
>
> I'm undecided on this one too. At the moment I don't make the
> distinction, but after reading Jim Blinn's articles on the subject, I'm
> starting to lean towards implementing the full tensor concept. As he
> points out, that's the only way to make vector and matrix geometry
> operations that really make sense, without introducing arbitrary rules
> of thumb.
>
Can you reference the Blinn articles that cover this subject? I'd be very
interested to read what he's written on this subject. Thanks.
-- Noah
Ross Smith
> In article <alqqjm$i87$1...@lust.ihug.co.nz>,
> Ross Smith <r-s...@ihug.co.nz> wrote:
>>> - hmat3 and hvec3 classes should be considered for 2D work.
>>
>>The homogeneous types, if present, should be templated in the same way
>>as the normal ones. Personally I'm not convinced that separate
>>homogeneous types are necessary.
>
> Agreed with the first sentence. My existing implementation has hvec4
> derived from tvec4, with additional member functions. The primary
> benefit is to allow the matrix and vectors to do any special
> optimization for homogeneous cases. For instance, an
> hmat4<T> * hvec4<T> is the same operation as tmat<T,4,4> * tvec<T,4>
> but hmat4<T> * tvec<T,3> can remove 4 multiplications because the
> corresponding hvec4<T> has 1 as the value of the homogeneous
> component.
But as Noah Stein pointed out, the implicit conversion from the
homogeneous type to the full type is often ambiguous. I don't really
feel strongly for or against having special homogenous types, but I do
feel definitely that, if you do have a homogenous type, you need more
than one.
>>> Comeau 4.3.0
>>> Issues:
>>> gcc (which version(s)?
>>> other compilers?
>>
>>You're making the same mistake as the web design dweebs with their
>>"this page only usable with MSIE 6.1234" crap. Taking specific
>>compilers into account is the wrong approach. Design it in C++ -- as
>>in, the language defined by ISO 14882 -- and _after_ finishing the
>>design, implement it to work with as many compilers as can handle it.
>
> The only compiler I have which does PTS is Comeau 4.3.0. I don't
> evevn know how well current gcc works (haven't stress tested it much).
> Implementing to the standard in such a way that few people can compile
> the library isn't very useful.
As far as I know, MSVC is the only compiler left that doesn't do partial
specialisation. Certainly the only widely used one. Since pretty much
every other compiler can do it and many of them are free, any argument
based on people having difficulty getting PTS-handling compilers
doesn't hold water.
> Functionally, I don't see a difference between what I proposed and
> what your last sentence (after the --) reads.
The difference is that not having PTS constrains the design
significantly -- not just the implementation. E.g. providing
conversions between vectors or matrices with different element types
but the same dimensions becomes very difficult if you can't partially
specialise the conversion functions.
>>> - Concatenate operation which is configurable -- for instance,
>>> right-multiply vs. left-multiply. Again this would be useful for
>>> OpenGL vs. Direct3D, for example.
>>
>>This makes no sense. Right vs left multiplication would be determined
>>by the order in which you write the operands, obviously.
>
> Have you implemented code that handles both OpenGL and Direct3D?
> OpenGL uses a right-handed coordinate system. Direct3D is
> left-handed. This in addition to the difference in the matrices.
You've lost me here, I'm afraid. What do right-handed vs left-handed
coordinates have to do with it?
The difference between DX and GL conventions is handled by the
compile-time column-major vs row-major choice.
>>> Performance
>>> + As much inline code as possible.
>>> Ideally, this could be configured. Might be difficult with
>>> operators, but the operators could have functions which are
>>> explicitly inlined.
>>
>>Why would it be difficult with operators?
>
> Perhaps I was overly terse. I meant that having an inline version and
> a non-inline version might be difficult for operators. I think it's
> not as much of an issue as I thought at first.
I think letting the user select inline vs out-of-line is
microoptimisation overkill. Since these are templates, the definitions
have to be visible across modules anyway (no, export doesn't change
that), so they're always available for inlining. Let the compilers
worry about it, they're much better than humans at such low-level
optimisations these days.
--
Ross Smith ..................................... Auckland, New Zealand
r-s...@ihug.co.nz ...................................................
"A specter is haunting Wall Street; it is the specter
of honest accounting." -- Arthur D. Hlavaty
---
Uwe Schnitker
> >representation.
>
> Fair enough.
>
Both of you are quite sure, aren't you. Some time ago, I discussed
this point with someone apparently experienced in graphics programming
with OpenGL/DirectX.
>>My question: Is it also important to you to be able to pass a lot of those
>>small matrices or vectors to a C-API which requires array-like storage?
>Often It is necessarty to be able to pass an array of valvectors to a
>C-API and often it is necessary to use array of structs containing one
>or more valvectors plus other datas (for example colors and/or texture
>informations), in both cases i think valvectors must be POD.
>Instead it is not so common to pass arrays of matrixes, so i think
>matrixes can be non-POD (if this buy some advantage) with a fast
>member function to access the underlying representation.
This points out that there are situations where you need your
small vector to be a POD. It is not sufficient to get access to
an underlying POD struct.
Since the
> >We don't need a POD, all we need is a pointer to the internal array
> >representation.
attitude is often explained with the string.c_str() example,
let me translate the aforementioned discussion to it:
You can call a C function expecting a char* like this:
std::string strA, strB;
strcmp(strA.c_str(),strB.c_str());
but you cannot call a C function expecting a char** in the same way
directly:
const char* first = "First";
const char* second = "Second";
const char* third = "Third";
const char** cTable = {first, second, third};
std::vector<std::string> cppTable;
cppTable.push_back(first);
cppTable.push_back(second);
cppTable.push_back(third);
Now if
f(cTable,3);
is a correct function call, you cannot do
f(cppTable.xxx(),cppTable.size());
If std::string were a POD with a char* as the only non-static data member,
you could just write
f(cppTable.begin(),cppTable.size());
So you have to do some copying, e.g:
std::vector<const char*> xTable(cppTable.size());
std::transform(cppTable.begin(),
cppTable.end(),
xTable.begin(),
mem_fun_ref(std::string::*c_char)); // is this correct?
f(xTable.begin(),xTable.size());
which means wasting time.
With an array of many small vectors representing lots of image points you
wouldn't tolerate the wasteful copying.
Regards,
Uwe
Ross Smith
> "Ross Smith" <r-s...@ihug.co.nz> wrote in message
> news:alqqjm$i87$1...@lust.ihug.co.nz...
>
>> > - Should row vectors and column vectors be differentiated, and
>> > corresponding matrix/vector operations be enforced as correct?
>>
>> I'm undecided on this one too. At the moment I don't make the
>> distinction, but after reading Jim Blinn's articles on the subject,
>> I'm starting to lean towards implementing the full tensor concept. As
>> he points out, that's the only way to make vector and matrix geometry
>> operations that really make sense, without introducing arbitrary
>> rules of thumb.
>>
>
> Can you reference the Blinn articles that cover this subject? I'd be
> very
> interested to read what he's written on this subject. Thanks.
I read them in _Jim Blinn's Corner: Dirty Pixels_ (Morgan Kauffman,
1998, ISBN 1-55860-455-3), chapters 9-10. As far as I know they're not
online (a Google search for a fragment of text from the articles didn't
turn up anything).
--
Ross Smith ..................................... Auckland, New Zealand
r-s...@ihug.co.nz ...................................................
"A specter is haunting Wall Street; it is the specter
of honest accounting." -- Arthur D. Hlavaty
---
E. Robert Tisdale
> A little while ago,
> there was a discussion about small vectors (and matrices)
> and possible inclusion of a small vector/matrix library
> in the C++ standard library.
Why?
Do you mean to compel C++ compiler developers
to provide a small vector/matrix library with every compiler?
And, if so, why must C++ compiler developers
provide a small vector/matrix library?
Do C++ compiler developers need to modify their compilers
to recognize small vectors and matrices as built in types
so that they can perform special optimizations?
> There was good discussion about the various requirements
> but I saw no post or posts that gathered the requirements together.
> I've looked at Walter Landry's FTensor library
> as well as John Nagle's algebra3 library and the Blitz tinyarray.
> I believe they are all good work but don't address the needs
> that most people are looking for in such a package
> (though I could be wrong). The FTensor library, for instance,
> while technically superb, is likely unfamiliar
> to most C++ programmers (in fact,
> I just missed getting a minor in physics
> but am still a little shaky with tensors).
> The algebra3 library is also quite nice,
> but the version that I've looked at
> assumes 'double' as the numerical type.
>
> I've been working on a subset
> of the requirements mentioned in the newsgroup
> (and got it working on both VC6 and Comeau 4.3)
> and would be willing to pursue it to its conclusion.
> My background:
> I've worked with graphics programming for several years
> primarily in OpenGL but with some Direct3D experience
> and some computational geometry. With that in mind,
> I've collected most of the comments I could find
> and list the requirements below.
>
> I don't know if this would belong in Boost
> since it has explicitly stated that
> optimization issues are not the primary concern.
> In contrast, performance must be
> one of the overriding concerns for this library
> if people are going to use it.
> I've roughly split up the requirements into two groups:
> functionality and optimizations.
> Note that I mark issues that I've already implemented
> with "+" and issues that I haven't with "-"
>
> Please add your comments, requirements, etc.
> Perhaps we can work together to find a solution
> that will be useful for a large part of the C++ community.
>
> The master copy of this document is online at:
>
> http://www.csua.berkeley.edu/~emarkp/small_vector.txt
>
> Basic Assumptions:
> + The primary vectors and matrices would be
> vectors of 3 and 2 dimensions (and 4D homogeneous vectors).
> The primary matrices will be of size (4,4) and (3,3)
> (perhaps (2,2) as well).
>
> + The classes will be templates
> for both the numerical type and size of dimensions.
>
> For discussion purposes, I'll call the vector class:
>
> template <class T, int D> tvector;
>
> and the matrix class:
>
> template <class T, int M, int N> tmatrix;
Why are you specifying templates?
Vector and matrix objects are not generic containers.
class T will be restricted to real and complex floating-point types,
perhaps, a few integral types and, possibly, bool.
D, M and N will be restricted to small integers -- 2, 3 and 4.
Evidently, the use of templates is an implementation detail
that should be left small vector and matrix class library developer.
> - Additionally, there (likely) should be classes
> for homogeneous matrices and vectors.
>
> For discussion purposes, I'll call the homogeneous vector:
>
> template <class T> hvec4; //for 4D homogeneous vectors
>
> and the matrix class:
>
> template <class T> hmat4; //for 4D homogeneous matrices
>
> - hmat3 and hvec3 classes should be considered for 2D work.
>
> - It is unclear if the library should reside in a namespace.
It should reside in its own namespace.
> Requirements:
> + compile on VC6, VC7, Comeau 4.3.0
> Issues:
> gcc (which version(s)?
> other compilers?
If you are going to specify a portable vector and matrix class library,
you don't need a standard.
All you need to do is code it up and distribute it.
> + Specializations for square matrices
> which provide functions only appropriate for a square matrix
> (invert, identity, etc.)
You need a square matrix type which could be derived
from the rectangular matrix type.
> + operator overloading ( vector: * for dot, ^ for cross, * for matrix)
These are poor choices.
The four fundamental binary arithmetic operators (*, /, +, -)
should be reserved for element by element operations
as they are in Fortran 90. The inner product, cross product,
matrix-vector product and matrix-matrix product
are very special operations which deserve their own names.
operator^ has the wrong precedence for a product.
> + row-major vs. column-major matrices specified at compile-time--
> can convert from one to another
> (this is useful because OpenGL uses column-major matrices
> and Direct3D uses row-major matrices).
This is unnecessary.
The only difference between column and row major
is the order in which subscripts appear.
A simple pseudo-constructor (a function used as a constructor)
can be used to switch the dimensions of new rectangular matrix objects.
and operator() can be overloaded
to reference elements in column-major order.
> - Concatenate operation which is configurable --
> for instance, right-multiply vs. left-multiply.
> Again this would be useful for OpenGL vs. Direct3D, for example.
>
> + Conversion operators from one vec type/size to another.
> Issues:
> Should conversion be explicit or implicit?
> Should conversion be allowed for both size and type in one conversion?
Vector an matrix operations are universally defined
on objects of "conformant" sizes only.
If an object of the wrong size appear in an expression,
it is almost certainly a mistake.
Conversion must be explicit.
Implicit conversion will only make it more difficult
for application programs to track down their mistakes.
> + As close to POD as possible
> Issues:
> I'm not sure if a template instantiation can be considered a POD.
> I've had to deviate from pure POD to overcome limitations of VC6.
>
> + Access to data with begin(), end() like STL
One of the goals of a vector and matrix class
is to obviate subscripts, loops and iterators.
> Less-resolved issues:
> - Should row vectors and column vectors be differentiated
> and corresponding matrix/vector operations be enforced as correct?
They are vectors.
Neither the computer or the C++ computer programming language
know anything about rows or columns.
Fortran programmers naturally think of matrix objects
as a collection of column vectors and
C and C++ programmers naturally think of matrix objects
as a collection of row vectors
but Fortran, C and C++ all store matrix object in exactly the same way --
one vector after another in a contiguous block of [virtual] memory.
> + Should mixed type operations be allowed?
> (tvec<3, float> ^ tvec<3, double> returns tvec<3, double>)
The question that you should ask is,
"Should we compel class library developers to implement
operations on mixed types?"
There will be a lot of different operations
and a lot of specializations if they use templates.
> - Should traits be allowed for user-defined types?
> (Especially for a square-root operator
> for normalizing tvect<T> where T isn't float or double.)
I don't think that this is going to very useful.
Vector and matrix operations make sense only for a few base types.
The aren't really containers for anything except numbers.
Other "user-defined types" will require so many specializations
that application programmers are unlike benefit much from templates.
> Performance
> + As much inline code as possible. Ideally, this could be configured.
> Might be difficult with operators
> but the operators could have functions which are explicitly inlined.
>
> + Loops unrolled where possible (matrix * vec, etc.)
>
> + no virtual functions
>
> + Optimized multiplication operations
> with homogeneous matrices and non-homogeneous vectors.
> Allow operations like hmat4<T> * tvec<T,3>
> without creating temporary 4D vector first.
>
> + All conditionals known at compile-time resolved at compile-time.
>
> + Default initialization does nothing--the user must explicitly set elements.
Library standards don't usually specify optimization
or any other details of the implementation.
These details are irrelevant to standardizing a library API.
What you really need to do is back up a bit
and try to describe the underlying Abstract Data Types (ADTs)
that your proposed small vector and matrix class library
is supposed to support.
You should not consider any particular language binding
even though you obviously intend to provide one for C++.
After that, you should try to design a C++ language binding
without regard to how you might implement it in C++.
You might find that it is actually better
to implement your class library in C or even Fortran.
The ADTs together with the language bindings specify
the Application Programmer's Interface (API).
Only after you have designed the API, should you consider
implementing the class library in C++ or any other language.
James Russell Kuyper Jr.
>
> ema...@CSUA.Berkeley.EDU (E. Mark Ping) writes:
> > The FTensor library, for instance, while technically superb is
> > likely unfamiliar to most C++ programmers (in fact, I just missed
> > getting a minor in physics, but am still a little shaky with
> > tensors).
>
> I feel that Tensor's and Index's are similar in complexity to
> Container's and Iterator's. It is certainly valid to reduce
The thing that makes a Tensor more sophisticated than a simple matrix is
it's transformation properties under coordinate tranformations. I'm
unfamiliar with the FTensor library, but I've put a lot of thought into
the correct way to represent those transformation properties in tensor
library. I never came up with a workable design, but I did come away
from it with a realization of just how much extra complexity that idea
adds.
....
> > - It is unclear if the library should reside in a namespace.
>
> Why wouldn't it just go into std::?
For the same reason it doesn't make sense to put all of your files in
your root directory. Major subcomponents of the standard library should
occupy namespaces under std::, just to keep the namespace pollution
under control.
John Nagle
> It could be also useful to look at `Tiny Vector Matrix library using
> Expression Templates' (a.k.a. tvmet):
>
> http://tvmet.sourceforge.net/
What's the thinking on "expression templates"? It seems
a painful way of doing something. Should they be avoided,
tolerated, or should something comparable be supported in
the language?
We had a bad time in the LISP world with attempts
to extend the language via compile-time macros.
There were many years of huge, hard to debug macros.
(The classic is the "MIT Loop Macro"; look it up.)
In the end, SCHEME incorporated the most useful
higher level constructs and cleaned up the language.
I see a tendency for C++ to go down this dark
alley. Templates are a painful way to produce an
extensible programming language. Let's face it,
debugging them is very difficult.
If we really need inline function declaration,
maybe C++ should have inline function declaration.
Something like this, maybe:
float tot =
integrate(float f(float x) { return(sin(x));} , 0, pi/2);
It would be understandable, and you'd get the usual
diagnostics.
John Nagle
Animats
John Nagle
> In article <3D808DEA...@grad.hr>, Kresimir Fresl <fr...@grad.hr> wrote:
>
>>It could be also useful to look at `Tiny Vector Matrix library using
>>Expression Templates' (a.k.a. tvmet):
>>
>> http://tvmet.sourceforge.net/
>>
>>
>
> Good point. I hadn't heard of this library before. A brief perusal
> adds one more requirement:
>
> - The License must be totally free--that is, anyone can
> use/modify/fold/spindle/mutilate the library at will, use source
> anywhere, etc. No GPL or LGPL.
>
> The library looks very sound technically, and appears to address many
> of the issues that were raised. It's sad about the license. I can't
> imagine any production code using it.
LGPL is OK for libraries. You can use them in commercial
programs without making the programs free software.
Expression templates bother me, though. That comes close
to writing a compiler in the template language. That's
more of a desperation move to get around a language
limitation than something to be encouraged
by the language standard.
John Nagle
Animats
Natale Fietta
Stein") wrote:
>Moving forward, VC6 compatibility will become less and less of an issue.
I'd strongly hope you are correct in your assumption.
>"E. Mark Ping" <ema...@CSUA.Berkeley.EDU> wrote
>> + Conversion operators from one vec type/size to another.
>> Issues:
>> Should conversion be explicit or implicit?
>> Should conversion be allowed for both size and type in one conversion?
>Disagree. There is no "natural" conversion between vectors of different
>dimensionality.
But there is a "natural" conversione between cartesian and homogeneous
coordinates, for example:
point(x,y,z) => Hpoint(x,y,z,1) and vector(x,y,z) => Hvector(x,y,z,0)
and Hpoint(x,y,z,w) => point(x/w,y/w,z/w) [obviously Hpoint must
enforce the invariant w!=0].
>> + Access to data with begin(), end() like STL
>
>This doesn't hurt. At the same time, what's the rationale?
I also do not need it, but as Noah said: it do not hurt...
>> Less-resolved issues:
>> - Should row vectors and column vectors be differentiated, and
>> corresponding matrix/vector operations be enforced as correct?
>I have not made up my mind on this issue. I've implemented it in a library
>before, but I'm not entirely sure its importance. What do others think?
I usually do not make this distinction, but i also do other strange
and dangerous thing, so my opinion is not the more autoritative on
this topic.
>> + Should mixed type operations be allowed?
>> (tvec<3, float> ^ tvec<3, double> returns tvec<3, double>)
I do not need this, but have no objection to allow it.
>> + Optimized multiplication operations with homogeneous matrices and
>> non-homogeneous vectors. Allow operations like hmat4<T> * tvec<T,3>
>> without creating temporary 4D vector first.
>I disagree. I don't think you can multiply a 3d vector with a homogeneous
>matrix. Does that vector represent a vector or a point, i.e. in affine
>space, is the 4th value a 0 or 1? You really can't say; therefore, I
>believe some sort of explicit "conversion" must occur. I believe, though,
>that this specified conversion may be done with no overhead.
I disagree with your disagreement.
i do think different classes can (must?) be used to represent vectors
an points (and also versors), so the ambiguity you tell of disappear.
>A few weeks ago, I started another vector-matrix library with template
>expressions. It already contains all the features here I agree with and it
>works under VC6.
Sound interesting, do you plan to publicly release it ?
Regards,
Natale Fietta
John Nagle
> "E. Mark Ping" wrote:
>
>
>>A little while ago,
>>there was a discussion about small vectors (and matrices)
>>and possible inclusion of a small vector/matrix library
>>in the C++ standard library.
>>
>
> Why?
Because there are many such libraries now, and
programs that use code from multiple sources find
it necessary to convert back and forth between different
representations of these simple objects. A game
might have different representations of 3D vectors and
4D matrices (the most common cases) in a scene engine,
a graphics API, a physics engine, a collision
detection system, and a client-server object system.
Conversion gets to be a pain, and adds overhead.
It's not that the needed classes are hard to implement.
It's not that they need to be fancy. It's just that they need to
be uniform, for interoperability. Thus, standardization
is appropriate.
This is easy to do. Let's not get carried away
with the theory here. These are simple objects.
John Nagle
Animats
Walter Landry
> The only compiler I have which does PTS is Comeau 4.3.0. I don't
> evevn know how well current gcc works (haven't stress tested it
> much). Implementing to the standard in such a way that few people
> can compile the library isn't very useful.
I have access to nine compilers (Comeau, Compaq, GNU, Intel, KAI,
Portland Group, IBM xlC, SGI, Sun) on five architectures (Linux/x86,
Tru64, Solaris, AIX, Irix), and the only compiler that really doesn't
completely handle partial specialization is Sun's (it is unhappy
partially specializing non-type template parameters). To be fair,
IBM's compiler has problems too, with frequent Internal Compiler
Errors. I think it is fair to say that almost all compilers can
handle PTS these days, with a few exceptions.
This is all detailed in the paper I wrote about my tensor library
http://superbeast.ucsd.edu/~landry/FTensor/FTensor.pdf
Reagrds,
Walter Landry
wla...@ucsd.edu
Natale Fietta
Mark Ping) wrote:
> For instance, an
>hmat4<T> * hvec4<T> is the same operation as tmat<T,4,4> * tvec<T,4>
>but hmat4<T> * tvec<T,3> can remove 4 multiplications because the
>corresponding hvec4<T> has 1 as the value of the homogeneous
>component.
As Noah Stein already pointed out in another sub-thread, it is
necessary to distinguish between points and vectors to know if the
homogeneous component is 1 or 0, this can be easily done using
different classes for free vectors and points (applied vectors).
This also permit optimization in hmat4*hvect4 case, if hvect enforce
the fact that homogeneous component is always 0 (not possible the same
with hpoint, in this case any value !=0 is valid for homogeneous
component)
I'm unsure if the distinction between mat4 and hmat4 is useful, i'd
surely like a distinction between perspective hmat4 and
non-perspective hmat4.
>Ross Smith <r-s...@ihug.co.nz> wrote:
>> The only reasoanble choice for the second
>>multiplication operator is %. I tried using * for cross and % for dot
>>for a while, but eventually switched to named functions. I'm still
>>undecided about the best approach.
Very interesting advice !
I have alway used a named function for Cross because of the wrong
precedence of ^, i've never thinked to use %, next time i'll try it.
(incidentally, i do find more "natural" * for Dot and % for Cross
instead of the reverse)
>I've waffled back and forth too on the operator vs. named function
>approach. Ideally, both would be available. I don't know
Agree, to have both is better.
>Have you implemented code that handles both OpenGL and Direct3D?
>OpenGL uses a right-handed coordinate system. Direct3D is
>left-handed. This in addition to the difference in the matrices.
>
>The idea of a concatenate operator would be to allow this to be
>configurable. However, your point is valid--perhaps this is a
>function best implented outside the library, but following similar
>design.
I am confused by your affirmation, left/right-ness of coordinate
system has nothing to do with multiplication order, the different
multiplication order is needed because of the different column/row
matrixes representation...
>>> + As close to POD as possible
>>> Issues:
>>> I'm not sure if a template instantiation can be considered a POD.
On Thu, 1 Aug 2002 15:09:35 GMT, ka...@gabi-soft.de (James Kanze)
in message <d6651fb6.0208...@posting.google.com> wrote:
>Templates don't define a type; they
>define a schema for defining a type. And there is nothing in the
>standard which says that a type so generated differs in any way from the
>same type declared explicitly.
So i presume template instantiantion can be a POD.
>>We don't need a POD, all we need is a pointer to the internal array
>>representation.
I strongly disagree!
For matrix i can live without POD-ness, but not for vectors; it is
both inefficient and error prone to have to explicitly create a
temporary copy in an array of POD to pass an array of vectors to a
C-API. this operation is very frequent.
>Again, I suspect that the vast majority of programmers are familiar
>with vectors, fewer with matrices, and very few with tensors.
The majoritiy of programmers i do work with are familiar only with
arrays, and they do think std::vector is a vector :-(
(incidentally i am unhappy with the name chosen for std::vector, i'd
have preferred std::dynamic_array or similar)
Regards,
Natale Fietta
Ross Smith
>
>>Ross Smith <r-s...@ihug.co.nz> wrote:
>
>>>We don't need a POD, all we need is a pointer to the internal array
>>>representation.
>
> I strongly disagree!
> For matrix i can live without POD-ness, but not for vectors; it is
> both inefficient and error prone to have to explicitly create a
> temporary copy in an array of POD to pass an array of vectors to a
> C-API. this operation is very frequent.
Yes, but you don't need a POD to handle this. My vector class has a
template argument that determines whether it uses internal or external
representation (i.e. whether it contains the actual array or just a
pointer to an external array). Internal and external vectors can be
freely mixed in vector and matrix arithmetic (returned vectors are
always internal, for obvious reasons). This lets me wrap a vector
around an arbitrary segment of an array, with no copying, which makes
it easy to handle the likes of glInterleavedArrays() efficiently.
--
Ross Smith ......... r-s...@ihug.co.nz ......... Auckland, New Zealand
"I'm deeply concerned about a leader who has ignored the United Nations
for all these years, refused to conform to resolution after resolution
after resolution, who has weapons of mass destruction."
-- George W. Bush, Jr.
E. Robert Tisdale
> Because there are many such libraries now
> and programs that use code from multiple sources
> find it necessary to convert back and forth
> between different representations of these simple objects.
> A game might have different representations
> of 3D vectors and 4D matrices (the most common cases)
> in a scene engine, a graphics API, a physics engine,
> a collision detection system, and a client-server object system.
> Conversion gets to be a pain, and adds overhead.
These are great arguments for a standard but
what do they have to do with the ANSI/ISO C++ standard?
There doesn't appear to be reason to compel C++ compiler developers
to provide a small vector and matrix class library
as part of the C++ standard library.
> It's not that the needed classes are hard to implement.
> It's not that they need to be fancy.
> It's just that they need to be uniform, for interoperability.
> Thus, standardization is appropriate.
>
> This is easy to do.
> Let's not get carried away with the theory here.
> These are simple objects.
In fact, it's so easy that you could probably write
a portable class library to do the job
so there would be no need for a standard.
You just implement it and encourage everybody to use it.
If, on the other hand, you can convince us that
there is no single best implementation
which is portable to every target platform,
there may be a need for a standard.
Then all you need to do is convince us that
nobody but the C++ compiler developer
can adequately implement these class libraries
for the target platforms.
Walter Landry
> Walter Landry wrote:
> >
> > ema...@CSUA.Berkeley.EDU (E. Mark Ping) writes:
> > > The FTensor library, for instance, while technically superb is
> > > likely unfamiliar to most C++ programmers (in fact, I just missed
> > > getting a minor in physics, but am still a little shaky with
> > > tensors).
> >
> > I feel that Tensor's and Index's are similar in complexity to
> > Container's and Iterator's. It is certainly valid to reduce
>
> The thing that makes a Tensor more sophisticated than a simple matrix is
> it's transformation properties under coordinate tranformations. I'm
> unfamiliar with the FTensor library, but I've put a lot of thought into
> the correct way to represent those transformation properties in tensor
> library. I never came up with a workable design, but I did come away
> from it with a realization of just how much extra complexity that idea
> adds.
I agree that the general concept of tensors and indices can be more
complication than some people would like. That is why I said Tensor's
and Index's, not tensors and indices. You can happily multiply
vectors and matrices together without understanding metrics or
covariant and contravariant indices. The only real difference from a
library like algebra3 is that you have to worry about indices.
However, those indices mean that you don't have to worry about left vs
right multiplication, or inner vs outer vs cross products.
> > > - It is unclear if the library should reside in a namespace.
> >
> > Why wouldn't it just go into std::?
>
> For the same reason it doesn't make sense to put all of your files in
> your root directory. Major subcomponents of the standard library should
> occupy namespaces under std::, just to keep the namespace pollution
> under control.
While I agree with you in principle, I think it is a little too late.
The current standard puts everything in std:: and these small vectors
and matrices aren't really a big enough concept to go into their own
separate namespace. But I don't have strong feelings about this.
Regards,
Walter Landry
wla...@ucsd.edu
Walter Landry
> Kresimir Fresl wrote:
>
>
> > It could be also useful to look at `Tiny Vector Matrix library using
> > Expression Templates' (a.k.a. tvmet):
> > http://tvmet.sourceforge.net/
>
>
> What's the thinking on "expression templates"? It seems
> a painful way of doing something. Should they be avoided,
> tolerated, or should something comparable be supported in
> the language?
It seems like the best way to avoid problems is to leave that as an
implementation detail. I haven't seen any interface proposed so far
that would require an expression template implementation.
However, in an attempt to see whether expression templates actually
buys you anything, I ran algebra3 on a microbenchmark that I developed
for my Tensor library. It tests how well the library optimizes
expressions.
You can find the details of what the code looks like and what the
compiler setting were in my paper. For this little test, I only used
the Intel and GCC compilers on my Pentium II laptop. The results are
parametrized by the number of operators in an expression. The larger
the number of operators, the more complicated the expression (so A*B
has one operator, A*B + B*C*D has four). The results for the
execution time I got are (smaller is faster)
GCC
# of C-arrays algebra3 FTensor
operators
1 4.64 2.98 4.71
3 19.58 36.25 27.58
7 7.07 5.39 7.95
13 10.08 7.70 12.80
19 13.33 10.71 17.63
27 4.50 5.67 5.33
35 10.53 11.13 9.96
45 17.18 17.43 15.47
55 24.54 24.94 22.05
Intel
# of C-arrays algebra3 FTensor
operators
1 2.67 2.75 5.01
3 6.97 6.10 8.90
7 1.40 1.68 1.65
13 3.15 2.35 31.81
19 4.28 3.33 43.19
27 4.17 3.45 9.23
35 8.90 7.51 15.93
45 13.92 12.64 24.69
55 17.93 22.63 35.79
So even when the algebra3 library is slower than writing things out by
hand, it is (usually) not that much slower. Tensor's, on the other
hand, can be quite a dog.
> We had a bad time in the LISP world with attempts
> to extend the language via compile-time macros.
> There were many years of huge, hard to debug macros.
> (The classic is the "MIT Loop Macro"; look it up.)
> In the end, SCHEME incorporated the most useful
> higher level constructs and cleaned up the language.
>
> I see a tendency for C++ to go down this dark
> alley. Templates are a painful way to produce an
> extensible programming language. Let's face it,
> debugging them is very difficult.
>
> If we really need inline function declaration,
> maybe C++ should have inline function declaration.
The problem is that we don't really know what we need. This is
something that Arch Robison touched on in his paper "Impact of
Economics on Compiler Optimization". Templates allow us to write our
own optimizers.
Also, there is a lot more to templates than inline function
declarations.
Regards,
Walter Landry
wla...@ucsd.edu
Frank Compagner
news:87wupnk...@grue.ucsd.edu:
> Mark Ping wrote:
>> The only compiler I have which does PTS is Comeau 4.3.0. I don't
>> evevn know how well current gcc works (haven't stress tested it
>> much). Implementing to the standard in such a way that few people
>> can compile the library isn't very useful.
>
> I have access to nine compilers (Comeau, Compaq, GNU, Intel, KAI,
> Portland Group, IBM xlC, SGI, Sun) on five architectures (Linux/x86,
> Tru64, Solaris, AIX, Irix), and the only compiler that really doesn't
> completely handle partial specialization is Sun's (it is unhappy
> partially specializing non-type template parameters). To be fair,
> IBM's compiler has problems too, with frequent Internal Compiler
> Errors. I think it is fair to say that almost all compilers can
> handle PTS these days, with a few exceptions.
Yes, but one of those exceptions is MSVC (both v.6 and v.7), which is by
far the most popular (as in widespread, not necesarilly well-liked) C++
compiler in use today. It is especially well entrenched among the
intended target audience for this proposed library (notably games
developers and developers of library's and tools supporting interactive
computer graphics). The upcoming 7.1 release will not fix this, and while
PTS has been promised for version 7.2 (promised for about Q1 2003), it
will be quite some time for the average MSVC developer has access to PTS.
Given the understandable reluctance op developers of switching compilers
in mid-project (even upgrading from v.6 to v.7 of the same vendor can be
a big issue), i suspect that it will be a good two years before a
vector/matrix library that requires PTS has any chance of being used,
much less become popular among game developers. Given the deplorable
state of affairs right now, i'd rather not wait that long, and had much
rather have a pratical solution now, than a perfect one in a few years.
That said, this has of course little relevance to standard C++ (and
extensions thereof) and if this discussion was truly intended to discuss
future extensions of the std::lib, this would be completely irrelevant.
But i don't see a small vector/library lib targeted at (interative)
computer graphics as a likely candidate for C++0x. Although the intended
target audience is pretty big, the subject is still way to specialized to
merrit inclusion in the next standard of C++. The comittee surely has it
work cut out for it as it is. It seems to me that the goal of most people
in this discussion is to establish some sort of lingua franca to describe
matrix and vector objects in a way that facilitates reuse and the
effective use of combinations of libray's that are currently
incompatible.
While this is likely too ambititous a goal for the next C++ standard, it
is still a very worthwile goal to pursue. These are essentially pretty
straightforward objects, and the basic problems are not _that_ difficult.
I would much rather have something that can be used today, on the
prevalent compilers, than a solution that is extremely elegant and will
likely be of use to me in a couple of years. I can see a library that
uses PTS where it's available, and falls back to less sophisticated
default behaviour where it's not as an acceptable compromise.
I say this discussion would be more profitably pursued on
comp.lang.c++.moderated and/or the boost mailing list; I'd like to
encourage the original poster of this thread (Mark Ping) to submit his
implementation to the boost mailing list as a first shot of implementing
a small vector/matrix lib. No doubt there will be a lot of discussion and
room for improvements, but that is by far the most productive way to
obtain a reasonably usefull implementation in the short term.
Frank Compagner.
Natale Fietta
E.Robert...@jpl.nasa.gov ("E. Robert Tisdale") wrote:
>"E. Mark Ping" wrote:
>
>> A little while ago,
>> there was a discussion about small vectors (and matrices)
>> and possible inclusion of a small vector/matrix library
>> in the C++ standard library.
>Why?
>Do you mean to compel C++ compiler developers
>to provide a small vector/matrix library with every compiler?
>And, if so, why must C++ compiler developers
>provide a small vector/matrix library?
Why no ?
We already have a complex library included in any C++ compiler...
>> + operator overloading ( vector: * for dot, ^ for cross, * for matrix)
>These are poor choices.
>The four fundamental binary arithmetic operators (*, /, +, -)
>should be reserved for element by element operations
Are you serious ?
Do you really want Matrix operator*(Matrix, Matrix) to be element by
element product instead of matrix multiplication ???
For me this is a big violation of the "minimal surprise principle" !
Incidentally: what is the usefulness of element by element product ?
real curiosity, not irony, i have never used it.
>Vector an matrix operations are universally defined
>on objects of "conformant" sizes only.
>If an object of the wrong size appear in an expression,
>it is almost certainly a mistake.
Not in my application domain.
However i do admit that in a general purpose library conversions
between different sizes must be explicit to evitate mistakes.
>You might find that it is actually better
>to implement your class library in C or even Fortran.
>Only after you have designed the API, should you consider
>implementing the class library in C++ or any other language.
If the goal is to write a library useful for C++ programmers, writing
it in another language is not an option...
Regards,
Natale Fietta
Allan W
> > A little while ago,
> > there was a discussion about small vectors (and matrices)
> > and possible inclusion of a small vector/matrix library
> > in the C++ standard library.
E.Robert...@jpl.nasa.gov ("E. Robert Tisdale") wrote
> Why?
This has been addressed earlier in this topic. Not meaning to speak
on behalf of the proponents of this idea, but my own interpretation
can be summarized: they want standardized high-performance matrixes,
both row-major and column-major, for use in high-speed applications
and with various third-party APIs not specifically designed for C++.
> Do you mean to compel C++ compiler developers
> to provide a small vector/matrix library with every compiler?
> And, if so, why must C++ compiler developers
> provide a small vector/matrix library?
Yes, this is exactly what I think that they mean. That's true about
any proposal for a standard library routine or template. Since there
are already third-party implementations to use for reference, this
doesn't seem so heinous -- as a first cut, implementations can simply
copy one of these third-party implementations and transplant them into
the std namespace.
> Do C++ compiler developers need to modify their compilers
> to recognize small vectors and matrices as built in types
> so that they can perform special optimizations?
I doubt anyone would mind this -- but it's not a requirement of the
proposal, and I doubt that the optimizations could be much better by
doing so. A standard template would suffice, and that's exactly what
most platforms would deliver.
[Snip]
> > For discussion purposes, I'll call the vector class:
> > template <class T, int D> tvector;
> > and the matrix class:
> > template <class T, int M, int N> tmatrix;
> Why are you specifying templates?
> Vector and matrix objects are not generic containers.
> class T will be restricted to real and complex floating-point types,
> perhaps, a few integral types and, possibly, bool.
> D, M and N will be restricted to small integers -- 2, 3 and 4.
With two types for T and nearly-identical implementation, you should
start considering a template. You've listed at least 4 data types,
and perhaps as many as 11, depending on how you count "floating-point
types" and "integral types" -- multiply this by the three values
you've given for D, M, and N, and you certainly have enough
combinations to justify using a template.
As for restricting class T to real and complex floating-point types,
the use of templates wouldn't require that. One might question the
utility of tvector<bigint<1000> > (where bigint is some third-party
multiple-precison integer), but there doesn't seem to be any reason
to prohibit it.
> Evidently, the use of templates is an implementation detail
> that should be left small vector and matrix class library developer.
Perhaps, but if the standard required that, I suspect that most
libraries would create the template anyway, and then create
typedefs for specific instantiations -- unless the standard
specifically prohibited this practice. But why would it?
[Snip]
> > - It is unclear if the library should reside in a namespace.
>
> It should reside in its own namespace.
But should it be the "std" namespace, or something underneath such
as "std::tvector" ? In my opinion, if it's standardized, it should
NOT be in the global namespace or in a new top-level namespace such
as "tvector" -- this could collide with existing namespaces.
> If you are going to specify a portable vector and matrix class library,
> you don't need a standard.
> All you need to do is code it up and distribute it.
That's a valid differing point of view. There are good arguments on
each side.
> > + Specializations for square matrices
> > which provide functions only appropriate for a square matrix
> > (invert, identity, etc.)
>
> You need a square matrix type which could be derived
> from the rectangular matrix type.
This is a fundamental mistake -- like trying to derive shape::circle
from shape::ellipse. Mathematically, a square is a special case of
rectangle, but in terms of object-oriented programming, this heirarchy
would be a bad idea because it breaks the substitution principle.
If code tries to alter the ellipse's width but not it's height, and
the ellipse is actually a circle, things simply don't work right.
Deriving ellipse from circle has similar problems. Similarly, trying
to derive square from rectangle is usually a bad idea, and I suspect
(but haven't yet proved to myself) that this extends to matrixes.
> > + row-major vs. column-major matrices specified at compile-time--
> > can convert from one to another
> > (this is useful because OpenGL uses column-major matrices
> > and Direct3D uses row-major matrices).
>
> This is unnecessary.
> The only difference between column and row major
> is the order in which subscripts appear.
> A simple pseudo-constructor (a function used as a constructor)
> can be used to switch the dimensions of new rectangular matrix objects.
> and operator() can be overloaded
> to reference elements in column-major order.
One of the design goals was to have access to the raw elements to
pass them directly to non-C++ APIs. Different APIs expect the data
in different order, and switching them (especially on-the-fly) can
be expensive. Therefore, Mark would like two different versions of
vector that work essentially the same way, but internally use two
different orders.
> > - Concatenate operation which is configurable --
> > for instance, right-multiply vs. left-multiply.
> > Again this would be useful for OpenGL vs. Direct3D, for example.
> >
> > + Conversion operators from one vec type/size to another.
> > Issues:
> > Should conversion be explicit or implicit?
> > Should conversion be allowed for both size and type in one conversion?
>
> Vector an matrix operations are universally defined
> on objects of "conformant" sizes only.
> If an object of the wrong size appear in an expression,
> it is almost certainly a mistake.
> Conversion must be explicit.
> Implicit conversion will only make it more difficult
> for application programs to track down their mistakes.
I would agree. tvector<int,3,3> times tvector<double,4,4> should
not compile. You want to convert them, you can write your own
conversion trivially.
> > + As close to POD as possible
> > Issues:
> > I'm not sure if a template instantiation can be considered a POD.
> > I've had to deviate from pure POD to overcome limitations of VC6.
> >
> > + Access to data with begin(), end() like STL
>
> One of the goals of a vector and matrix class
> is to obviate subscripts, loops and iterators.
But another one, for this particular proposal, is to allow access
to explicit elements directly, and even to pass them directly to
third-party non-C++ APIs. One could do this with operator[], but
I can't see a reason not to allow begin().
> > Less-resolved issues:
> > - Should row vectors and column vectors be differentiated
> > and corresponding matrix/vector operations be enforced as correct?
>
> They are vectors.
> Neither the computer or the C++ computer programming language
> know anything about rows or columns.
> Fortran programmers naturally think of matrix objects
> as a collection of column vectors and
> C and C++ programmers naturally think of matrix objects
> as a collection of row vectors
> but Fortran, C and C++ all store matrix object in exactly the same way --
> one vector after another in a contiguous block of [virtual] memory.
This particular proposal removes that particular detail from the
realm of encapsulation. We want to control that aspect when passing
the data to third-party APIs, and therefore we DO want to know the
difference.
Personally, I think that two different templates should be used,
as opposed to one template with two different template args. This
might vastly increase the number of possible operators -- for
instance, rowvector<int,3,3> times colvector<int,3,3> -- but it
would also increase the possibility of optimizing each of these
cases.
That's assuming that there are times you would want to do it on
purpose, of course. We would need some easily-digested rules about
return types. Obviously, rowvector *= colvector returns a rowvector,
and colvector *= rowvector returns a colvector. But does
rowvector * colvector follow the same pattern, or opposite? Probably
best to make it the same, 'cause it's easier to teach and remember.
> > + Should mixed type operations be allowed?
> > (tvec<3, float> ^ tvec<3, double> returns tvec<3, double>)
>
> The question that you should ask is,
> "Should we compel class library developers to implement
> operations on mixed types?"
That's right, though I wouldn't have phrased it that way.
Should we compel the library developers to implement a function that
copies arbitrary memory blocks (memcpy), or finds the cosine of any
arbitrary circle segment (cos)? Yes, we should.
> There will be a lot of different operations
> and a lot of specializations if they use templates.
The sheer number won't matter much, especially if these are
template specializations, because the code won't be pulled into the
project unless it's instantiated. A bigger question: is
tvec<3,float> * tvec<3,double>
more likely to be someone assuming it would work (and potentially
surprised that it doesn't), or would it be more likely to be an
accident (which we could diagnose by failing to define it).
I raise the question, because I don't have the answer.
> > - Should traits be allowed for user-defined types?
> > (Especially for a square-root operator
> > for normalizing tvect<T> where T isn't float or double.)
It beats making sqrt() a template parameter, or writing your own
version of sqrt(long)! I think it comes down to how often you're
going to need to normalize tvect<long>. If this happens a lot,
then there ought to be some way to handle it.
> I don't think that this is going to very useful.
> Vector and matrix operations make sense only for a few base types.
> The aren't really containers for anything except numbers.
> Other "user-defined types" will require so many specializations
> that application programmers are unlike benefit much from templates.
An interesting point. Would we ever want to have a tvect<bigint<1000> >,
where bigint is some third-party large-precision integer? If so, then
we might need to either overload sqrt(bigint<T>), or else use the traits.
> > Performance
> Library standards don't usually specify optimization
> or any other details of the implementation.
> These details are irrelevant to standardizing a library API.
But they very often specify the level of complexity, so that we can
judge if the library function will have reasonable performance in
a given application.
> What you really need to do is back up a bit
> and try to describe the underlying Abstract Data Types (ADTs)
> that your proposed small vector and matrix class library
> is supposed to support.
> You should not consider any particular language binding
> even though you obviously intend to provide one for C++.
> After that, you should try to design a C++ language binding
> without regard to how you might implement it in C++.
> You might find that it is actually better
> to implement your class library in C or even Fortran.
> The ADTs together with the language bindings specify
> the Application Programmer's Interface (API).
> Only after you have designed the API, should you consider
> implementing the class library in C++ or any other language.
I think that the point of this section, was that tvector<> is
likely to overlap functionality with vector<> quite a bit. The
point is stipulated -- but the devil is in the details. tvector<>
may have a lot of similarities to vector<>, but the design goals
are completely different -- there are likely to be at least some
minor differences in the available methods (such as the lack of
resize or capacity), and there are likely to be some major
differences in the implementation (such as allocating the
low-level array inside the object, rather than seperately on the
heap).
One goal of library code is to eliminate the need to tinker with
messy implementation details. Hopefully, users will be able to
trade vector<> versus tvector<> depending on the specific use
and performance needs. That way they can have the best of both
worlds, without having to worry about the inner details of either.
E. Mark Ping
John Nagle <na...@animats.com> wrote:
>E. Mark Ping wrote:
>
>> In article <3D808DEA...@grad.hr>, Kresimir Fresl <fr...@grad.hr> wrote:
>>
>>>It could be also useful to look at `Tiny Vector Matrix library using
>>>Expression Templates' (a.k.a. tvmet):
>>>
>>> http://tvmet.sourceforge.net/
>>>
>>>
>>
>> Good point. I hadn't heard of this library before. A brief perusal
>> adds one more requirement:
>>
>> - The License must be totally free--that is, anyone can
>> use/modify/fold/spindle/mutilate the library at will, use source
>> anywhere, etc. No GPL or LGPL.
>>
>> The library looks very sound technically, and appears to address many
>> of the issues that were raised. It's sad about the license. I can't
>> imagine any production code using it.
>
>
> LGPL is OK for libraries. You can use them in commercial
>programs without making the programs free software.
But it's most certainly inappropriate for possible inclusion in the
standard. And the law is pretty murky on the GPL (see
http://www.linuxdevices.com/articles/AT4528760742.html) and the LGPL
hasn't been seriously studied AFAIK. Even if it's allowed, the onus
of figuring out the needs of the LGPL and satisfying them may be more
than many groups are willing to bear.
> Expression templates bother me, though. That comes close
>to writing a compiler in the template language. That's
>more of a desperation move to get around a language
>limitation than something to be encouraged
>by the language standard.
Indeed, that may be a good way to implement it on one platform or
another, but I don't think it should be set in stone.
--
Mark Ping
ema...@soda.CSUA.Berkeley.EDU
James Russell Kuyper Jr.
> kuy...@wizard.net ("James Russell Kuyper Jr.") writes:
> > Walter Landry wrote:
> I agree that the general concept of tensors and indices can be more
> complication than some people would like. That is why I said Tensor's
> and Index's, not tensors and indices. You can happily multiply
> vectors and matrices together without understanding metrics or
> covariant and contravariant indices. The only real difference from a
Properly, it should be possible to do arithmetic operations on two
different tensors, only if they are defined at the same point in the
manifold (regardless of which coordinate system is used to describe that
point). A tensor defined at one location can be converted to a
corresponding tensor defined at a different location, but for any
sufficiently large displacement, the result depends upon the path used
to move the tensor from the first location to the second. And, unless
they're defined using the same coordinate system, multiplying two
tensors defined using different coordinate systems should require
invoking coordinate conversion functions. I tried to figure out an
efficient way to design a general purpose tensor library that would make
the validity checks and conversions occur automatically, and came to the
conclusion that it could either be efficient, general purpose, or
automatic, but not all three at once. I'd love to be proven wrong.
....
> > your root directory. Major subcomponents of the standard library should
> > occupy namespaces under std::, just to keep the namespace pollution
> > under control.
>
> While I agree with you in principle, I think it is a little too late.
> The current standard puts everything in std:: and these small vectors
Not so. We've already got std::rel_ops (20.2p1). Even if it were true
that std has no subspaces, that wouldn't be a barrier to adding some in
the future.
E. Mark Ping
E. Robert Tisdale <E.Robert...@jpl.nasa.gov> wrote:
>"E. Mark Ping" wrote:
>
>> A little while ago,
>> there was a discussion about small vectors (and matrices)
>> and possible inclusion of a small vector/matrix library
>> in the C++ standard library.
>
>Why?
>Do you mean to compel C++ compiler developers
>to provide a small vector/matrix library with every compiler?
>And, if so, why must C++ compiler developers
>provide a small vector/matrix library?
>Do C++ compiler developers need to modify their compilers
>to recognize small vectors and matrices as built in types
>so that they can perform special optimizations?
Please note that I pointed out that the discussion was about adding it
to the standard. I was hesitant to post the followup thread to this
group because I wasn't (and I'm still not) sure that inclusion in the
C++ standard is a good solution. Perhaps simply having *a* standard
vec/matrix library is sufficient, as you point out later in your post.
And I think that explicitly pointing that out is a good idea--I should
have done so myself.
>Why are you specifying templates?
>Vector and matrix objects are not generic containers.
>class T will be restricted to real and complex floating-point types,
>perhaps, a few integral types and, possibly, bool.
When writing various versions of an implementation, I found that the
templated solution was much more robust, easy to code, and (in fact)
easier to read than writing code for many different types.
Additionally, I found it easier to extend for special user-defined
types that were neither float nor double but were intended as
higher-precision floating types with software implementations.
>It should reside in its own namespace.
That's how I felt from the beginning.
>> Requirements:
>> + compile on VC6, VC7, Comeau 4.3.0
>> Issues:
>> gcc (which version(s)?
>> other compilers?
>
>If you are going to specify a portable vector and matrix class library,
>you don't need a standard.
>All you need to do is code it up and distribute it.
Indeed, that was my plan. I realize now that I was more affected by
the idea to provide a standard library than I was by the idea to add
to the C++ standard. The goal after gathering requirements (in my
mind) is to then implement the whole thing and distribute it freely,
but only after reaching some agreement about the desired library.
>You need a square matrix type which could be derived
>from the rectangular matrix type.
That's a terrible idea IMO, as bad as creating a Square type and
deriving from a Rectangle type.
>This is unnecessary.
>The only difference between column and row major
>is the order in which subscripts appear.
Internal layout is very important to people who use API's like OpenGL
and Direct3D. Passing the contents of the matrices to the API's
with low overhead requires proper layout (column-major for OpenGL,
row-major for Direct3D).
>> + Access to data with begin(), end() like STL
>
>One of the goals of a vector and matrix class
>is to obviate subscripts, loops and iterators.
That's a good point. Will have to think about that more.
--
Mark Ping
ema...@soda.CSUA.Berkeley.EDU
E. Mark Ping
Ross Smith <r-s...@ihug.co.nz> wrote:
>Noah Stein wrote:
>
>>
>> Can you reference the Blinn articles that cover this subject? I'd be
>> very
>> interested to read what he's written on this subject. Thanks.
>
>I read them in _Jim Blinn's Corner: Dirty Pixels_ (Morgan Kauffman,
>1998, ISBN 1-55860-455-3), chapters 9-10. As far as I know they're not
>online (a Google search for a fragment of text from the articles didn't
>turn up anything).
A quick perusal suggests that the book is a republication of his
articles for IEEE. The list of articles can be found at:
http://research.microsoft.com/~blinn/cga.htm
Looks like chapter 9 and 10 in the book correspond to Uppers and
Downers parts 1 and 2, the May and July 1999 issues of IEEE Computer
Graphics and Applications.
--
Mark Ping
ema...@soda.CSUA.Berkeley.EDU
E. Robert Tisdale
> E. Robert Tisdale wrote:
>
> > You need a square matrix type which could be derived
> > from the rectangular matrix type.
>
> That's a terrible idea IMO, as bad as creating a Square type and
> deriving from a Rectangle type.
Take a look at
The C++ Scalar, Vector, Matrix and Tensor class library
http://www.netwood.net/~edwin/svmtl/
You will find that a square matrix class derived from
a rectangular matrix class works quite nicely.
> > The only difference between column and row major
> > is the order in which subscripts appear.
>
> Internal layout is very important to people
> who use API's like OpenGL and Direct3D.
> Passing the contents of the matrices to the API's
> with low overhead requires proper layout
> (column-major for OpenGL, row-major for Direct3D).
There is no difference in the "internal layout".
The only difference is the order
in which subscripts appear after the name of the matrix.
They appear in order from left to right
in a column-major order matrix and
they appear in reverse order from right to left
in a row-major order matrix.
If, in your mind, a matrix is "laid out" in row-major order,
you only need to remember that
it appears to be its transpose to an API that expects
matrix objects "laid out" column-major order.
If you really want to support Fortran programmers,
use operator[i][j] to subscript matrix objects
"laid out" in row-major order and
use operator(1+j, 1+i) to subscript matrix objects
"laid out" in column-major order.
Walter Landry
> articles for IEEE. The list of articles can be found at:
> http://research.microsoft.com/~blinn/cga.htm
>
> Looks like chapter 9 and 10 in the book correspond to Uppers and
> Downers parts 1 and 2, the May and July 1999 issues of IEEE Computer
> Graphics and Applications.
Thanks for the reference. Having just read it, it seems like the
thing that he most likes about tensor notation is the distinction
between covariant and contravariant tensors. In vector-matrix speak,
that is the difference between row vectors and column vectors. I must
say, however, as a practicing astrophysicist in numerical General
Relativity, that having the library enforce the distinction is not
that important. The more important thing for me is that the library
keep all of the indices in order.
Regards,
Walter Landry
wla...@ucsd.edu
James Russell Kuyper Jr.
>
> On Sun, 15 Sep 2002 13:18:09 +0000 (UTC),
> E.Robert...@jpl.nasa.gov ("E. Robert Tisdale") wrote:
>
> >"E. Mark Ping" wrote:
> Do you really want Matrix operator*(Matrix, Matrix) to be element by
> element product instead of matrix multiplication ???
>
> For me this is a big violation of the "minimal surprise principle" !
It wouldn't be a surprise to anyone used to APL or IDL.
....
> >You might find that it is actually better
> >to implement your class library in C or even Fortran.
> >Only after you have designed the API, should you consider
> >implementing the class library in C++ or any other language.
>
> If the goal is to write a library useful for C++ programmers, writing
> it in another language is not an option...
Why not? Carefully written C code can be ported without modification to
a C++ compiler. And of course, the whole idea is that it will be
re-written to take advantage of C++ features upon being ported.
E. Mark Ping
>
>> E. Robert Tisdale wrote:
>>
>> > You need a square matrix type which could be derived
>> > from the rectangular matrix type.
>>
>> That's a terrible idea IMO, as bad as creating a Square type and
>> deriving from a Rectangle type.
>
>Take a look at
>The C++ Scalar, Vector, Matrix and Tensor class library
>
> http://www.netwood.net/~edwin/svmtl/
>
>You will find that a square matrix class derived from
>a rectangular matrix class works quite nicely.
Have downloaded the pdf, and will be reading it soon. It's funny, but
that objection was the first one I thought of (i.e. deriving square
from rectangle). The violation there is that a square doesn't really
fit the IS-A model. However, the square matrix *does* fit the model.
It can be used everywhere a non-square matrix can be, and additionally
has more capabilites (identity, determinant, inverse, etc.).
Furthermore, a templated matrix can't change its size, so there's no
worry about that issue.
>> > The only difference between column and row major
>> > is the order in which subscripts appear.
>>
>> Internal layout is very important to people
>> who use API's like OpenGL and Direct3D.
>> Passing the contents of the matrices to the API's
>> with low overhead requires proper layout
>> (column-major for OpenGL, row-major for Direct3D).
>
>There is no difference in the "internal layout".
>The only difference is the order
>in which subscripts appear after the name of the matrix.
Not so. For instance, you can dump a matrix (or load it) as a flat
array to OpenGL if it memory layout is in column major order.
Similarly for Direct3D if the layout is row major order.
To be perhaps overly specific, if the numbers indicate an offset into
a flat array mat[16]:
0 4 8 12
1 5 9 13
2 6 10 14
3 7 11 15
works for OpenGL, and
0 1 2 3
4 5 6 7
8 9 10 11
12 13 14 15
works for Direct3D. It doesn't matter for the user, except when you
want to load/store the full matrix as a flat array to the API in
question.
--
Mark Ping
ema...@soda.CSUA.Berkeley.EDU
E. Robert Tisdale
> E. Robert Tisdale wrote:
>
> >There is no difference in the "internal layout".
> >The only difference is the order
> >in which subscripts appear after the name of the matrix.
>
> Not so. For instance, you can dump a matrix (or load it) as a flat
> array to OpenGL if it memory layout is in column major order.
> Similarly for Direct3D if the layout is row major order.
>
> To be perhaps overly specific,
> if the numbers indicate an offset into a flat array mat[16]:
>
> 0 4 8 12
> 1 5 9 13
> 2 6 10 14
> 3 7 11 15;
>
> works for OpenGL, and
>
> 0 1 2 3
> 4 5 6 7
> 8 9 10 11
> 12 13 14 15
>
> works for Direct3D. It doesn't matter for the user
> except when you want to load/store the full matrix
> as a flat array to the API in question.
Suppose
double A[4][4] =
{{ 0, 1, 2, 3},
{ 4, 5, 6, 7},
{ 8, 9, 10, 11},
{12, 13, 14, 15}};
is a two dimensional array of double precision
floating-point numbers that I wish to pass by reference
to a Fortran 77
subroutine f(A)
double precision A(4, 4)
I write a function prototype:
extern "C" {
void f(double&);
}
then I would call it using
f(A[0][0]);
where
A(1+i, 1+j) = A[i][j]
for all 0 <= i < 4 and 0 <= j < 4.
In other words,
from the point of view of the calling C++ program,
the Fortran 77 subroutine f(double&) appears to be
an operation on the transpose of A.
This works because both Fortran 77 and C++ compilers
represent a two-dimensional array in exactly the same way --
a one-dimensional array of one-dimensional arrays.
The problem is that both Fortran 77 and C++ programmers
insist upon interpreting a two-dimensional array
as a matrix where the left-most subscript represents the row
and the right-most subscript represents the column.
Fortran 77 programmers naturally think of a two-dimensional array
as a collection of column vectors and
C++ programmers naturally think of a two-dimensional array
as a collection of row vectors.
Fortran 77 programmers naturally think of a one-dimensional array
as a column vector and
C++ programmers naturally think of a one-dimensional array
as a row vector.
You only create confusion if you get these two views mixed up.
If, for example, you wish to call a Fortran 77 matrix-vector multiply
c y <-- Ax
subroutine mvmul(y, A, x, n)
integer n
double precision y(n), A(n, n), x(n)
from a C++ program, you simply transpose the whole expression
y^T <-- (x^T)(A^T)
then transpose each of the operands individually
y <-- xA
Evidently, y and x are row vectors
as far as the C++ program can tell.
Suppose, instead, that the C++ programmer were to insist that,
while two-dimensional C++ arrays are "stored" in row-major order,
one-dimensional arrays represent column vectors.
Then, from a Fortran 77 programmer's point of view,
the C++ marix-vector multiplication
y <-- Ax
would become matrix-vector inner product
y <-- (A^T)x
Ross Smith
>
> To be perhaps overly specific, if the numbers indicate an offset into
> a flat array mat[16]:
>
> 0 4 8 12
> 1 5 9 13
> 2 6 10 14
> 3 7 11 15
>
> works for OpenGL, and
>
> 0 1 2 3
> 4 5 6 7
> 8 9 10 11
> 12 13 14 15
>
> works for Direct3D. It doesn't matter for the user, except when you
> want to load/store the full matrix as a flat array to the API in
> question.
It matters in one other way: Gauss-Jordan elimination can be done more
efficiently in row-major than in column-major (because you can handle a
whole row in one chunk). (That was the main reason I put the RM/CM
switch in my own matrix template; all the graphics I do is in OpenGL, I
don't care about DirectX.)
--
Ross Smith ......... r-s...@ihug.co.nz ......... Auckland, New Zealand
"I'm deeply concerned about a leader who has ignored the United Nations
for all these years, refused to conform to resolution after resolution
after resolution, who has weapons of mass destruction."
-- George W. Bush, Jr.
---
E. Robert Tisdale
> It matters in one other way: Gauss-Jordan elimination
> can be done more efficiently in row-major than in column-major
> (because you can handle a whole row in one chunk).
> (That was the main reason I put the RM/CM switch
> in my own matrix template;
> all the graphics I do is in OpenGL, I don't care about DirectX.)
Gauss-Jordan elimination can be applied just as efficiently
to the columns of a "column-major" matrix
as it can to the rows of a "row-major" matrix.
The same can be said for most other algorithms
implemented in numerical linear algebra packages.
In general, for every linear operation applied to the left side of a matrix
there is a corresponding operation that may be applied
to the right side of a matrix.
A complete numerical linear algebra package must provide both
whether the matrix objects are "stored" in row or column major.
If the package supports only one of the operators,
the application programmer will be obliged transpose the matrix,
apply the operator, and transpose it back again
whenever the other operator is required.
Gauss-Jordan elimination is discouraged in numerical computing
because it is much more expensive than an LU decomposition
followed by back substitution and because it fails awkwardly
if the matrix is singular or merely ill conditioned.
E. Robert Tisdale
it isn't practical to implement a high performance small vector class library
that is portable to every target platform that you wish to support.
The standard API would permit independent small vector class library developers
to implement high performance small vector class libraries customized
for a particular platform that would still support portable applications
which use the standard small vector class library API.
You need to provide two things:
1. a document which specifies the small vector class API and
2. a [portable] small vector class reference library.
The API specifies two things:
1. the underlying Abstract Data Types (ADTs) and
2. a language binding for each target language.
Even though you have identified just one target language binding,
you should specify the API without regard to any language binding
or implementation of any particular language binding.
The purpose of the reference library is to help
small vector class library developers verify the correct behavior
of their own high performance implementations.
It need not be a high performance implementation itself.
It should probably be as straight forward, transparent
and easy to maintain as possible
because you probably won't be able to get money
to pay for maintenance.
Stardardization of large vector and matrix library APIs
has been going on for a very long time so it might help
to look into some of them in order to get an idea
of what needs to be done.
Check out the archives of
the Basic Linear Algebra Subprogram Technical (BLAST) Forum
http://www.netlib.org/blast/index.html
The scope of the BLAS library and
the Linear Algebra PACKage (LAPACK)
is restricted to linear algebra
and the C++ language binding LAPACK++
is nothing more than a set of thin interface adapters.
The Vector, Signal and Image Processing Library (VSIPL)
has an ANSI/ISO C language binding and
an ANSI/ISO C++ language binding is in the works.
The scope of VSIPL is restricted mostly to
Digital Signal Processing (DSP) and more specifically
to embedded Digital Signal Processor (DSP) systems.
The Object Oriented Numerics Mailing List Archive
http://www.oonumerics.org/MailArchives/oon-list/
includes an extensive discussion of standardization
including contributions by Kent Budge
Re: OON: Usefulness (or otherwise) of valarray for numerical work in C++
who introduced the valarray class template into the standard library.
Apparently, valarray was introduced at a time when super computers
with large vector processors were popular
but compiler developers for these computers never took advantage
of valarray (they just weren't interested in supporting C++ compilers)
which disappointed Kent and caused him to regret proposing
valarray in the first place. Today, we have very fast little
microprocessors with small vector pipelines -- AltiVec
for example that require extensions to [GNU] C and C++ compilers
in order to support practical applications --
but I am not sure that this is sufficient reason
to make these extensions part of the ANSI/ISO C++ standard
and compel C++ compiler developers to support them.
Natale Fietta
Russell Kuyper Jr.") wrote:
>Natale Fietta wrote:
>>
>> E.Robert...@jpl.nasa.gov ("E. Robert Tisdale") wrote:
>>
>> >You might find that it is actually better
>> >to implement your class library in C or even Fortran.
>>
>> If the goal is to write a library useful for C++ programmers, writing
>> it in another language is not an option...
>
>Why not? Carefully written C code can be ported without modification to
>a C++ compiler.
The main pourpose of my comment was to criticize the possible use of
Fortran or others C++ unrelated languages.
Regards,
Natale Fietta
John Nagle
1. There are lots of useful small vector/matrix libraries
out there, and they're all incompatible. So this is
a suitable area for standardization.
2. A templated small vector/matrix library, where size
and orientation are determined at template instantiation
time, appears to work well with current compilers.
Existing optimizers make essentially all the abstraction
overhead go away for such simply written classes.
3. We probably don't need expression templates, partial
specialization, or Blitz-like tricks to get good
performance.
4. For compatibility with existing code (most importantly
OpenGL and Direct-X), we need access to the internal
data as an array of base types. The whole object
doesn't have to be a POD, although so far, that's not
ruled out as an option.
So it looks like a base templated class like
template <class T, size_t isize, size_t jsize, bool colmajor>
class valmatrix;
is the way to go. Any objections? Is "valmatrix" the
appropriate name?
If we can settle on this, then we can talk about operations
on these objects.
John Nagle
Animats
E. Robert Tisdale
> What we've learned so far:
>
> 1. There are lots of useful small vector/matrix libraries
> out there, and they're all incompatible.
> So this is a suitable area for standardization.
What do you mean by incompatible?
There may be a large number of small vector/matrix libraries
but they support a very small number of different
Abstract Data Types (ADTs).
If you mean to specify interoperability,
you should specify it separately from the specification
of the Application Program Interface (API)
so that small vector and matrix class library developers
can provide implementations which conform to the API
but are not interoperable with every other implementation.
Actually, the interoperability issue should be decided
among the library developers themselves
since it is irrelevant to application programmers.
> 2. A templated small vector/matrix library,
> where size and orientation are determined
> at template instantiation time,
> appears to work well with current compilers.
> Existing optimizers make essentially all the abstraction
> overhead go away for such simply written classes.
>
> 3. We probably don't need expression templates,
> partial specialization or Blitz-like tricks
> to get good performance.
Please be careful not to preclude "Blitz-like tricks".
The API need not specify the return type
for any small vector and matrix functions --
only that an implicit conversion be defined
from the actual return type to the expected return type.
> 4. For compatibility with existing code
> (most importantly OpenGL and Direct-X),
> we need access to the internal data as an array of base types.
> The whole object doesn't have to be a POD,
> although, so far, that's not ruled out as an option.
>
> So it looks like a base templated class like
>
> template <class T, size_t isize, size_t jsize, bool colmajor =
false>
> class valmatrix;
namespace small {
typedef size_t extent;
template <class T, extent m, extent n>
class Matrix;
template <class T, extent n, extent m>
class ColumnMatrix;
};
If you really want both row and column-major matrix classes.
I think that
small::ColumnMatrix<double, 3, 2> A;
is more readable than
std::valmatrix<double, 3, 2, true> A;
At least, it's more clear that a small column matrix is desired.
Again, I would caution that introducing column-major matrix
types is unnecessary and will create and perpetuate confusion
among application programmers.
> is the way to go. Any objections?
> Is "valmatrix" the appropriate name?
The class template name isn't really very important.
Application programmers can use a typedef
to change the matrix class name.
What is really important is a new namespace
for small vector and matrix class templates
that precludes collisions with standard names.
> If we can settle on this,
> then we can talk about operations on these objects.
Actually, we should talk about the operations
before we decide upon any particular
C++ language binding for those operations
or even the class templates.
The operations define the ADT.
For example,
Should the ADT support subvector or submatrix
views of vector and matrix objects?
Should there be an operation which returns a reference
to a row of a row-major order matrix?
Should there be an operation which returns a reference
to a column of a column-major order matrix?
Should the ADT support strided subvector or submatrix
views of vector and matrix objects?
Should there be an operation which returns a reference
to a column of a row-major order matrix?
Should there be an operation which returns a reference
to a row of a column-major order matrix?
Should the ADT support element-by-element
multiplication, division, addition and subtraction
like Fortran 90, Matlab and most popular vector and matrix
arithmetic libraries?
Ross Smith
> What we've learned so far:
>
> 1. There are lots of useful small vector/matrix libraries
> out there, and they're all incompatible. So this is
> a suitable area for standardization.
>
> 2. A templated small vector/matrix library, where size
> and orientation are determined at template instantiation
> time, appears to work well with current compilers.
> Existing optimizers make essentially all the abstraction
> overhead go away for such simply written classes.
>
> 3. We probably don't need expression templates, partial
> specialization, or Blitz-like tricks to get good
> performance.
I disagree. We do need partial specialisation/partial ordering. (Given
the matrix template declaration you suggest below, how would you write
a matrix multiplication function without it?)
> 4. For compatibility with existing code (most importantly
> OpenGL and Direct-X), we need access to the internal
> data as an array of base types. The whole object
> doesn't have to be a POD, although so far, that's not
> ruled out as an option.
>
> So it looks like a base templated class like
>
> template <class T, size_t isize, size_t jsize, bool colmajor>
> class valmatrix;
>
> is the way to go. Any objections? Is "valmatrix" the
> appropriate name?
Why not just matrix? I don't think an analogy to valarry is appropriate;
valarray is dynamically sized so it would be too inefficient for most
of the applications we want the matrix class for, so we're going to
need a corresponding fixed-size vector type anyway.
--
Ross Smith ......... r-s...@ihug.co.nz ......... Auckland, New Zealand
"I'm deeply concerned about a leader who has ignored the United Nations
for all these years, refused to conform to resolution after resolution
after resolution, who has weapons of mass destruction."
-- George W. Bush, Jr.
---
Natale Fietta
E.Robert...@jpl.nasa.gov ("E. Robert Tisdale") wrote:
>John Nagle wrote:
>> 3. We probably don't need expression templates,
>> partial specialization or Blitz-like tricks
>> to get good performance.
>Please be careful not to preclude "Blitz-like tricks".
John Nagle has written "probably don't need" and i do read this to be
very different from "prohibited"...
>> we need access to the internal data as an array of base types.
>> The whole object doesn't have to be a POD,
>> although, so far, that's not ruled out as an option.
Agree for matrixes, but remember the vector situation is different (i
do think small vector must be POD, or at least almost-POD).
>If you really want both row and column-major matrix classes.
>I think that
>
> small::ColumnMatrix<double, 3, 2> A;
>
>is more readable than
>
> std::valmatrix<double, 3, 2, true> A;
My personal preference is to something similar:
//i dislike the name "small" but i do not have a better alternative
namespace small
{
enum Order { RowMajor, ColumnMajor };
template <class T, size_t m, size_t n, Order order>
class Matrix;
};
>Again, I would caution that introducing column-major matrix
>types is unnecessary and will create and perpetuate confusion
>among application programmers.
In my application domain the confusion is already there and no one can
be able to eliminate it ! :-(
a standard support for both conventions is a very useful step for
dealing with this confusion.
>For example,
>Should the ADT support subvector or submatrix
>views of vector and matrix objects?
>Should there be an operation which returns a reference
>to a row of a row-major order matrix?
>Should there be an operation which returns a reference
>to a column of a column-major order matrix?
>Should the ADT support strided subvector or submatrix
>views of vector and matrix objects?
>Should there be an operation which returns a reference
>to a column of a row-major order matrix?
>Should there be an operation which returns a reference
>to a row of a column-major order matrix?
My personal point of view is to answer "no" to all these questions.
These are general pourpose oparations good for a full blown matrix
library, but unneeded for a library specifically optimized for small
matrix operations.
>Should the ADT support element-by-element
>multiplication, division, addition and subtraction
>like Fortran 90, Matlab and most popular vector and matrix
>arithmetic libraries?
My view can be tainted (i do use matrixes only to represent
geometrical transformations), but i do not need any of these.
I do not have objections to define addition and subtraction this way,
but matrix multiplication for me is the usual (natural?) row by column
multiplication, not the strange element by element operation i do not
even understand the usefulness of...
Regards,
Natale Fietta
E. Robert Tisdale
> //i dislike the name "small" but i do not have a better alternative
> namespace small {
> enum Order { RowMajor, ColumnMajor };
> template <class T, size_t m, size_t n, Order order>
> class Matrix;
> };
#include<cstddef>
namespace small {
typedef size_t extent;
typedef size_t offset;
template <class T, extent M, extent N>
class Matrix {
private:
T P[M][N];
public:
typedef T Row[N];
const
Row& operator[](offset i) const {
return P[i]; }
Row& operator[](offset i) {
return P[i]; }
};
template <class T, extent M, extent N>
class ColumnMatrix: public Matrix<T, N, M> {
public:
const
T& operator()(offset i, offset j) const {
return Matrix<T, N, M>::operator[](j)[i]; }
T& operator()(offset i, offset j) {
return Matrix<T, N, M>::operator[](j)[i]; }
};
typedef Matrix<double, 2, 2> double2x2Matrix;
typedef Matrix<double, 2, 3> double2x3Matrix;
typedef Matrix<double, 3, 2> double3x2Matrix;
typedef Matrix<double, 3, 3> double3x3Matrix;
// . . .
};
E. Mark Ping
John Nagle <na...@animats.com> wrote:
> is the way to go. Any objections? Is "valmatrix" the
>appropriate name?
I don't think so. "valmatrix" suggests a relationship with
"valarray". valarray's operations are element-by-element, whereas
I (and some others in this discussion) would prefer the standard
mathematical idea of matrix*matrix or matrix*vector as the definition
for the appropriate operators.
If we do decide that the element-by-element operation is preferred,
then "valmatrix" might be a good choice--although a corresponding
"valvector" might be confused with "valarray".
--
Mark Ping
ema...@soda.CSUA.Berkeley.EDU
E. Mark Ping
been reading much of the reference material people have pointed out.
After reading over the FTensor library (as well as Blinn's articles on
Tensors), I still believe that the full Tensor implementation is
simply too complex for basic use. I think it would be valuable to
make the two beasts compatible, so that it's easy to graduate to
FTensor if your needs require it.
E. Robert Tisdale's SVMTL library is also impressive, but it's coming
from a different set of requirements. Or at least the philosophy
seems to be at odds (at least slightly) with the standard library--the
addition of a different Complex class than the complex<> of the
standard library seems problematic. The explicit implementations of
various types is (I assume) more portable, but I find it cumbersome.
My desire for this library is for use with geometric modelling and
visualization--hence the geometric operations are more important to me
than other issues (for instance, my desire for operator*(matrix,
matrix) to perform matrix multiplication instead of element-by-element
multiplication).
Though I've seen similar requests for the same type of functionality,
I am starting to think there might be fundamental differences between
a simple vector/matrix implementation and an implementation which more
clearly maps to general linear algebra.
Should we distinguish between this "geometric vector" idea and the
more general linear algebra vector?
E. Robert Tisdale
> E. Robert Tisdale's SVMTL library is also impressive
> but it's coming from a different set of requirements.
Large, dense, vector, matrix and tensor objects.
> Or at least the philosophy seems to be at odds (at least slightly)
> with the standard library--the addition of a different Complex class
> than the complex<> of the standard library seems problematic.
Do you need complex vector and matrix objects?
If you do, you may find that you can't abide std::complex either.
The ANSI/ISO C++ standard does NOT specify Cartesian complex numbers.
Neither the real or imaginary part of a std::complex number
can appear on the left hand side of an assignment statement.
> The explicit implementations of various types is (I assume) more portable
> but I find it cumbersome.
The SVMTL does NOT specify the implementation -- just the type names.
It could be implemented as a template class library
but that is an implementation detail best left up to the library developer.
Remember, vector and matrix classes are NOT generic containers.
The elements are pretty much restricted to numbers.
Your proposal should specify all of the specializations
for all of the scalar types that you think should be supported.
> My desire for this library
> is for use with geometric modeling and visualization --
> hence the geometric operations are more important to me
> than other issues (for instance, my desire
> for operator*(matrix, matrix) to perform matrix multiplication
> instead of element-by-element multiplication).
>
> Though I've seen similar requests for the same type of functionality,
> I am starting to think there might be fundamental differences
> between a simple vector/matrix implementation
> and an implementation which more clearly maps to general linear algebra.
>
> Should we distinguish between this "geometric vector" idea
> and the more general linear algebra vector?
The fundamental differences distinguish
the different Abstract Data Types (ADTs).
There are lots of different implementations
but the differences between them are mostly superficial.
At this point, some scholarship is probably in order.
A survey of all of the available and/or proposed
small vector and matrix class libraries
may help you identify all of the really useful ADTs.
I have done this for large dense
vector, matrix and tensor class libraries
but I could not begin to tell you how to classify or name
the ADTs for small vector and matrix class libraries.
Why don't you start by describing the ADT
for "geometric vector" objects?
Remember that the ADT is defined by the methods
which can be applied to an object of that type
and NOT by the data representation or
the implementation of those methods
in any particular computer programming language.
Once you have described the ADT
for "geometric vector" objects, it should be relatively easy
to describe all of the other ADTs
for small vector and matrix objects.
I would be surprised if you found more than a handful
of distinct ADTs that were actually useful.
Natale Fietta
E.Robert...@jpl.nasa.gov ("E. Robert Tisdale") wrote:
>Natale Fietta wrote:
>> enum Order { RowMajor, ColumnMajor };
>> template <class T, size_t m, size_t n, Order order>
>> class Matrix;
<code abriged to show only essential differences>
> template <class T, extent M, extent N>
> class Matrix {
> T P[M][N];
> public:
> typedef T Row[N];
> Row& operator[](offset i) { return P[i]; }
> };
> template <class T, extent M, extent N>
> class ColumnMatrix: public Matrix<T, N, M> {
> public:
> T& operator()(offset i, offset j) { return Matrix<T, N, M>::operator[](j)[i]; }
> };
It is difficult to answer to a bunch of code without any comment to
say why do you think this approach is better than my little
suggestion, i'm not psychic...
can you please elaborate a bit ?
In any case i find unpleasant (and dangerous) the fact that your
Matrix elements are accessed with [i][j] syntax and instead
ColumnMatrix elements with a (i,j) syntax.
Regards,
Natale Fietta
E. Robert Tisdale
> It is difficult to answer to a bunch of code
> without any comment to say why do you think
> this approach is better than my little suggestion.
> I'm not psychic. Can you please elaborate a bit?
My example shows that the only difference between
column-major order and row major-order
is the order in which the subscripts appear.
you don't need to redefine all of the other
functions and operators.
> In any case, I find unpleasant (and dangerous)
> the fact that your Matrix elements are accessed with [i][j] syntax
> and instead ColumnMatrix elements with a (i, j) syntax.
What do you find unpleasant and dangerous?
The convention C/C++ subscript operator[]?
Or the unconventional use of operator()?
How would you define an subscript operator
to access the elements of a ColumnMatrix?
Natale Fietta
Mark Ping) wrote:
>Though I've seen similar requests for the same type of functionality,
>I am starting to think there might be fundamental differences between
>a simple vector/matrix implementation and an implementation which more
>clearly maps to general linear algebra.
>
>Should we distinguish between this "geometric vector" idea and the
>more general linear algebra vector?
Yes, i think: in geometry i (we?) need to distinguish various type of
vectors (applied vectors, free vectors, normalized vectors; cartesian
or homogeneous coordinates, etc...) and i do not know if these
distinctions are useful (or also meaningful) in other contextes...
Regards,
Natale Fietta
Gabriel Dos Reis
| > 3. We probably don't need expression templates,
| > partial specialization or Blitz-like tricks
| > to get good performance.
|
| Please be careful not to preclude "Blitz-like tricks".
| The API need not specify the return type
| for any small vector and matrix functions --
| only that an implicit conversion be defined
| from the actual return type to the expected return type.
That is insufficient. Especially in presence of function templates.
--
Gabriel Dos Reis g...@integrable-solutions.net
Gabriel Dos Reis
| On Thu, 26 Sep 2002 22:46:06 +0000 (UTC), ema...@CSUA.Berkeley.EDU (E.
| Mark Ping) wrote:
|
| >Though I've seen similar requests for the same type of functionality,
| >I am starting to think there might be fundamental differences between
| >a simple vector/matrix implementation and an implementation which more
| >clearly maps to general linear algebra.
| >
| >Should we distinguish between this "geometric vector" idea and the
| >more general linear algebra vector?
|
| Yes, i think: in geometry i (we?) need to distinguish various type of
| vectors (applied vectors, free vectors, normalized vectors; cartesian
| or homogeneous coordinates, etc...) and i do not know if these
| distinctions are useful (or also meaningful) in other contextes...
Well, if you do want to base your design on the purely abstract notion
of mathematical vector, then you'll quickly run into trouble with
current C++. A 1-form is also a vector (I'm not taking into account
any scalar product). A bare function is also a vector.
Fortunately, I do not think we need to work at that purely abstract
level.
--
Gabriel Dos Reis g...@integrable-solutions.net
---
Gabriel Dos Reis
[...]
| The ANSI/ISO C++ standard does NOT specify Cartesian complex numbers.
Sure, it does.
| Neither the real or imaginary part of a std::complex number
| can appear on the left hand side of an assignment statement.
This is an issue which I hope will be addressed in the future.
--
Gabriel Dos Reis g...@integrable-solutions.net
---
E. Robert Tisdale
===================================== MODERATOR'S COMMENT:
Please don't overquote replied-to postings.
===================================== END OF MODERATOR'S COMMENT
Gabriel Dos Reis wrote:
> E. Robert Tisdale wrote:
>
> | The ANSI/ISO C++ standard does NOT specify Cartesian complex numbers.
>
> Sure, it does.
Please cite and quote the relevant passage
in the ANSI/ISO C++ standard.
> | Neither the real or imaginary part of a std::complex number
> | can appear on the left hand side of an assignment statement.
>
> This is an issue which I hope will be addressed in the future.
---
Natale Fietta
E.Robert...@jpl.nasa.gov ("E. Robert Tisdale") wrote:
>My example shows that the only difference between
>column-major order and row major-order
>is the order in which the subscripts appear.
Maybe for square matrixes, but for rectangulars also the underlying
representation is different, for example a 3x2 matrix as RowMatrix use
array[3][2], instead as ColumnMatrix use array[2][3].
>you don't need to redefine all of the other
>functions and operators.
Well, if you are only worried about the unneeded redefinition it is
possible to evitate it also with my approach using some little
trickery.
but you have a point, trickery is unwanted if unneeded...
>> In any case, I find unpleasant (and dangerous)
>> the fact that your Matrix elements are accessed with [i][j] syntax
>> and instead ColumnMatrix elements with a (i, j) syntax.
>
>What do you find unpleasant and dangerous?
>The convention C/C++ subscript operator[]?
>Or the unconventional use of operator()?
It is the difference itself that i find dangerous, it is error prone
to have a different syntax for the same operation on two strongly
related classes.
It also defeat the only reason i am interested in two different
representations, my typical usage can be something similar to
#if defined USE_DIRECT_X
typedef RowMatrix<float, 4, 4> MyMatrix;
#elif defined USE_OPEN_GL
typedef ColumnMatrix<float, 4, 4> MyMatrix;
#endif
So i obviously want the same syntax for both.
>How would you define an subscript operator
>to access the elements of a ColumnMatrix?
For example using a proxy class to represent a column...
but i do think it is easier (and probably also more efficient) to
simply use operator() for both classes.
Regards,
Natale Fietta.
E. Robert Tisdale
> E. Robert Tisdale wrote:
>
> | The API need not specify the return type
> | for any small vector and matrix functions --
> | only that an implicit conversion be defined
> | from the actual return type to the expected return type.
>
> That is insufficient. Especially in presence of function templates.
Please give an example.
Gabriel Dos Reis
| Please cite and quote the relevant passage
| in the ANSI/ISO C++ standard.
26.2.2/1
The class complex describes an object that can store the Cartesian
components, real() and imag(), of a complex number.
--
Gabriel Dos Reis g...@integrable-solutions.net
---
James Russell Kuyper Jr.
> On Sat, 28 Sep 2002 04:27:46 +0000 (UTC),
> E.Robert...@jpl.nasa.gov ("E. Robert Tisdale") wrote:
>
>
>>My example shows that the only difference between
>>column-major order and row major-order
>>is the order in which the subscripts appear.
>
>
> Maybe for square matrixes, but for rectangulars also the underlying
> representation is different, for example a 3x2 matrix as RowMatrix use
> array[3][2], instead as ColumnMatrix use array[2][3].
Well, of course - that's why the subscript order is changed. It's not a
separate difference.
E. Robert Tisdale
> E. Robert Tisdale wrote:
>
> > My example shows that the only difference between
> > column-major order and row major-order
> > is the order in which the subscripts appear.
>
> Maybe for square matrixes, but for rectangulars also the underlying
> representation is different, for example a 3x2 matrix as RowMatrix use
> array[3][2], instead as ColumnMatrix use array[2][3].
The only difference between array[3][2] and array[2][3]
is the order in which the subscipts appear.
Allan W
> is the order in which the subscipts appear.
Sure.
And the only difference between memset(a, 255, 1) and memset(a, 1, 255)
is the order in which the two last parameters appear.
But what a difference that is!