efficient fixed size vector/matrix represenation+operations
Posted: Sun Feb 07, 2010 6:32 am
Hello,
at first I have to say that i am programming in C++ for about 10 years and are now trying to do my first steps with Lisp. I also use Python for a lot of stuff, so dynamic typing and some other non-C++-like concepts of Lisp are not completely new to me. I use SBCL with Emacs + Slime and use Practical Common Lisp as my primary guide to learn Lisp.
As my first toy projects i want to write small OpenGL programs. This way i can use an API i am already familiar with and will have some visible results that hopefully keep up my motivation. So far i have a small program that uses lispbuilder-sdl to show an OpenGL window. All runs fine.
But now to my problem: To do some 3D-stuff i need at least 3D-vectors, matrices and quaternions. All have the same size and the same type of elements (usually single-float). Sometimes 2D and 4D variants are also useful, maybe even with other element types. There will be a lot of instances of this data structures either as parts of other lightweight structures (for example to represent position and extend of a bounding box in an octree) or in arrays to represent geometry. Also there are operations like dotproduct, crossproduct and transformations that should be as efficient as possible. An operation does the same thing regardless of dimension and type of the used operands (the steps to calculate a dot product are always the same, no matter what dimension or element-type the operands have). Now i wonder how to express this with Lisp.
I actually have two questions:
1. How do i efficiently represent the vectors, matrices etc. ? Internally they should be stored as "C-arrays" in memory so i can pass vertex arrays to OpenGL without any conversion.
2. How do i implement the operations to be "generic" (for example one name "dot-product" that implements a dot product for all vector types)?
For the first problem I looked at "defstruct" and "vector". I would expect that "defstruct" gives me the compact memory representation that i aspire. Unfortunately i dont know if i can access structure-elements by index. The "vector" on the other hand allows access by index but i suspect it to also store the length even in situations where i know it will always be a fixed number. This way the length-informations will pollute anything that could be a vertex array.
I think the second problem could easily be implemented with CLOS. But that would conflict with the first problem: I dont want the vertices to have any runtime type information attached to them, i want "pure" data. Also I would expect that the overhead of CLOS would be pretty high when it is used for every single vector operation (the operations are simple and called very frequently).
In C++ the first problem is trivially solved by putting elements in a class/struct as a member that is a fixed size array. The second problem is also easy to solve: The operations can be implemented as templates. For every call of such an operation the correct implementation is chosen at compiletime. See for example GMTL.
I see that in Lisp I could write macros that implement the variants of all the different operations. But then i still have to call the right variant explicitly: Something like (dot3f a b) for 3D single-float vectors, dot3d for double-float, dot2f for 2D and so on. I would like to be less explicit. What i want to say is (dot a b) and Lisp figuring out at compiletime what specific function should be used.
I understand that this requires something like static type information. But it may be possible to implement some macros that extract type information out of "declare" expressions and insert the right function (and maybe instantiating the function out of some kind of template if necessary). I also found this other thread that is about static typing.
While i am interested to find a solution to my problem it would also be nice if someone could point me out a 3D-math library that fits my needs. So far all math libraries i found for Lisp offered more scientific functionality than the lightweight 3D stuff i need. Every 3D-graphics code i saw so far used the standard vector.
Btw. this is not intended to be a C++ vs. Lisp topic! I mentioned the C++ way to solve my problem only to clarify my intention.
at first I have to say that i am programming in C++ for about 10 years and are now trying to do my first steps with Lisp. I also use Python for a lot of stuff, so dynamic typing and some other non-C++-like concepts of Lisp are not completely new to me. I use SBCL with Emacs + Slime and use Practical Common Lisp as my primary guide to learn Lisp.
As my first toy projects i want to write small OpenGL programs. This way i can use an API i am already familiar with and will have some visible results that hopefully keep up my motivation. So far i have a small program that uses lispbuilder-sdl to show an OpenGL window. All runs fine.
But now to my problem: To do some 3D-stuff i need at least 3D-vectors, matrices and quaternions. All have the same size and the same type of elements (usually single-float). Sometimes 2D and 4D variants are also useful, maybe even with other element types. There will be a lot of instances of this data structures either as parts of other lightweight structures (for example to represent position and extend of a bounding box in an octree) or in arrays to represent geometry. Also there are operations like dotproduct, crossproduct and transformations that should be as efficient as possible. An operation does the same thing regardless of dimension and type of the used operands (the steps to calculate a dot product are always the same, no matter what dimension or element-type the operands have). Now i wonder how to express this with Lisp.
I actually have two questions:
1. How do i efficiently represent the vectors, matrices etc. ? Internally they should be stored as "C-arrays" in memory so i can pass vertex arrays to OpenGL without any conversion.
2. How do i implement the operations to be "generic" (for example one name "dot-product" that implements a dot product for all vector types)?
For the first problem I looked at "defstruct" and "vector". I would expect that "defstruct" gives me the compact memory representation that i aspire. Unfortunately i dont know if i can access structure-elements by index. The "vector" on the other hand allows access by index but i suspect it to also store the length even in situations where i know it will always be a fixed number. This way the length-informations will pollute anything that could be a vertex array.
I think the second problem could easily be implemented with CLOS. But that would conflict with the first problem: I dont want the vertices to have any runtime type information attached to them, i want "pure" data. Also I would expect that the overhead of CLOS would be pretty high when it is used for every single vector operation (the operations are simple and called very frequently).
In C++ the first problem is trivially solved by putting elements in a class/struct as a member that is a fixed size array. The second problem is also easy to solve: The operations can be implemented as templates. For every call of such an operation the correct implementation is chosen at compiletime. See for example GMTL.
I see that in Lisp I could write macros that implement the variants of all the different operations. But then i still have to call the right variant explicitly: Something like (dot3f a b) for 3D single-float vectors, dot3d for double-float, dot2f for 2D and so on. I would like to be less explicit. What i want to say is (dot a b) and Lisp figuring out at compiletime what specific function should be used.
I understand that this requires something like static type information. But it may be possible to implement some macros that extract type information out of "declare" expressions and insert the right function (and maybe instantiating the function out of some kind of template if necessary). I also found this other thread that is about static typing.
While i am interested to find a solution to my problem it would also be nice if someone could point me out a 3D-math library that fits my needs. So far all math libraries i found for Lisp offered more scientific functionality than the lightweight 3D stuff i need. Every 3D-graphics code i saw so far used the standard vector.
Btw. this is not intended to be a C++ vs. Lisp topic! I mentioned the C++ way to solve my problem only to clarify my intention.