Re: [boost] Generic Point class and algorithms (was: [GTL] - geometric template library - determininginterest)
On 10/5/07, John Femiani <JOHN.FEMIANI@asu.edu> wrote:
If we want boost to have a point class I think it will really have to be a set of point adapters and point concepts that work for existing types. There are too many points out there that we would have to interact with, both outside of boost and also within boost. For instance it would be nice if algorithms worked with both Boost.Point and the CGAL point.
I suggested something similar to this during a review (either Andy Little's Quan, or Boost.Units, I can't remember). For example, a Boost dot_product could be implemented as such: // Note: *SomethingDeducedHere* would be some BOOST_TYPEOF magic template <typename LHS, typename RHS> *SomethingDeducedHere* dot_product(const LHS &lhs, const RHS &rhs) { return get<0>(lhs) * get<0>(rhs) + get<1>(lhs) * get<1>(rhs) + get<2>(lhs) * get<2>(rhs); } Basically, just assume the point type acts like a tuple or Fusion sequence. Then all the algorithms written can be used with any point class (with a little work in some cases). --Michael Fawcett
On 10/5/07, John Femiani <JOHN.FEMIANI@asu.edu> wrote:
If we want boost to have a point class I think it will really have to be a set of point adapters and point concepts that work for existing types. There are too many points out there that we would have to interact with, both outside of boost and also within boost. For instance it would be nice if algorithms worked with both Boost.Point and the CGAL point.
I suggested something similar to this during a review (either Andy Little's Quan, or Boost.Units, I can't remember). For example, a Boost dot_product could be implemented as such:
// Note: *SomethingDeducedHere* would be some BOOST_TYPEOF magic template <typename LHS, typename RHS> *SomethingDeducedHere* dot_product(const LHS &lhs, const RHS &rhs) { return get<0>(lhs) * get<0>(rhs) + get<1>(lhs) * get<1>(rhs) + get<2>(lhs) * get<2>(rhs); }
Basically, just assume the point type acts like a tuple or Fusion sequence. Then all the algorithms written can be used with any point class (with a little work in some cases).
--Michael Fawcett
Sounds great to me. Can or should we formalize this into a set of concepts specific to points? Coordinate access is only a part of what a point rewuires; There is the tricky relationship between points and vectors (not std::vector!) and homogenous coordinates. I.e. point+point is undefined, point-point is a vector, etc... Also if there is a boost library (small or not) called point, I think awareness of it would benefit developers. Even if it did amount to little more than a fusion sequence (sorry I don't know fusion -- I plan to learn though :) ) -- John
On 10/5/07, John Femiani <JOHN.FEMIANI@asu.edu> wrote:
On 10/5/07, John Femiani <JOHN.FEMIANI@asu.edu> wrote:
If we want boost to have a point class I think it will really have to be a set of point adapters and point concepts that work for existing types. There are too many points out there that we would have to interact with, both outside of boost and also within boost. For instance it would be nice if algorithms worked with both Boost.Point and the CGAL point.
I suggested something similar to this during a review (either Andy Little's Quan, or Boost.Units, I can't remember). For example, a Boost dot_product could be implemented as such:
// Note: *SomethingDeducedHere* would be some BOOST_TYPEOF magic template <typename LHS, typename RHS> *SomethingDeducedHere* dot_product(const LHS &lhs, const RHS &rhs) { return get<0>(lhs) * get<0>(rhs) + get<1>(lhs) * get<1>(rhs) + get<2>(lhs) * get<2>(rhs); }
Basically, just assume the point type acts like a tuple or Fusion sequence. Then all the algorithms written can be used with any point class (with a little work in some cases).
--Michael Fawcett
Sounds great to me. Can or should we formalize this into a set of concepts specific to points? Coordinate access is only a part of what a point rewuires; There is the tricky relationship between points and vectors (not std::vector!) and homogenous coordinates.
I.e. point+point is undefined, point-point is a vector, etc...
This has been the source of quite a bit of contention in the past. The problem is, there are scientific users and applications where the distinction is highly important, and then there are game developers (and others I'm sure) who frequently mix both for optimization tricks and compatibility with the graphics API. If you can provide the distinction with no run-time overhead, and a no-overhead conversion to and from, I think both parties would sign off on it. --Michael Fawcett
On Fri, 5 Oct 2007, Michael Fawcett wrote:
On 10/5/07, John Femiani <JOHN.FEMIANI@asu.edu> wrote:
Sounds great to me. Can or should we formalize this into a set of concepts specific to points? Coordinate access is only a part of what a point rewuires; There is the tricky relationship between points and vectors (not std::vector!) and homogenous coordinates.
I.e. point+point is undefined, point-point is a vector, etc...
This has been the source of quite a bit of contention in the past. The problem is, there are scientific users and applications where the distinction is highly important, and then there are game developers (and others I'm sure) who frequently mix both for optimization tricks and compatibility with the graphics API.
If you can provide the distinction with no run-time overhead, and a no-overhead conversion to and from, I think both parties would sign off on it.
IIRC CGAL handles this quite nicely. http://www.tiny.cc/kbp7Z -- Francois Duranleau
Michael Fawcett wrote:
I.e. point+point is undefined, point-point is a vector, etc...
This has been the source of quite a bit of contention in the past. distinction is highly important, and then there are game developers (and others I'm sure) who frequently mix both for optimization tricks and compatibility with the graphics API.
Some folks in between those two groups argue that lineal combinations of points in the affine space is also well defined, and that uses point addition. Thus, I typically choose to define: - point -> point (reflexion) scalar * point -> point (affine scaling) point * scalar -> point (affine scaling) point * matrix -> point ( affine transformation) point + point -> point (lineal combination) point - point -> vector (subtraction) - vector -> vector (inversion) scalar * vector -> vector * scalar -> vector (scaling) vector + vector -> vector (addition) vector - vector -> vector (substraction) point + vector -> point point - vector -> point (displacement) vector * matrix -> vector (lineal transfomation) Which allow you to have your cacke and eat it too. Of course you could say that (ptA - ptA) is not the same as (ptA + (-ptA) ) and that is a problem (the former is a vector while the second is a point) Yet OTOH both results have the same components, so, why would that be a problem is a statically typed language? Furthermore, I sometimes like to use subtyping as in: cartesian <-- vector <-- point which in conjuction with the the curiously recurring pattern (to inject the "self" most-derived type into cartesian) can be used to define: unary - binary - + * right in the base class. (point-point) needs to be overriden in the point class though. But of course, as Joel said, these sort of thing (inheritance) is unnecesary when generic programming is _fully_ used. But the inheritance comes in handy in non-generic but parametrized contexts (where you can parametrize on "cartesian" and pass either points or vectors without conversion) Best -- Fernando Cacciola SciSoft http://fcacciola.50webs.com
-----Original Message----- From: boost-bounces@lists.boost.org [mailto:boost-bounces@lists.boost.org] On Behalf Of Fernando Cacciola Sent: Friday, October 05, 2007 12:35 PM To: boost@lists.boost.org Subject: Re: [boost] Generic Point class and algorithms (was:[GTL]- geometric template library - determininginterest)
Michael Fawcett wrote:
I.e. point+point is undefined, point-point is a vector, etc...
This has been the source of quite a bit of contention in the past. distinction is highly important, and then there are game developers (and others I'm sure) who frequently mix both for optimization
What would be the difference between the cartesian and the vector types? -- John tricks
and compatibility with the graphics API.
Some folks in between those two groups argue that lineal combinations of points in the affine space is also well defined, and that uses point addition.
Thus, I typically choose to define:
- point -> point (reflexion)
scalar * point -> point (affine scaling) point * scalar -> point (affine scaling)
point * matrix -> point ( affine transformation)
point + point -> point (lineal combination)
point - point -> vector (subtraction)
- vector -> vector (inversion)
scalar * vector -> vector * scalar -> vector (scaling)
vector + vector -> vector (addition)
vector - vector -> vector (substraction)
point + vector -> point point - vector -> point (displacement)
vector * matrix -> vector (lineal transfomation)
Which allow you to have your cacke and eat it too.
Of course you could say that (ptA - ptA) is not the same as (ptA + (-ptA) ) and that is a problem (the former is a vector while the second is a point)
Yet OTOH both results have the same components, so, why would that be a problem is a statically typed language?
Furthermore, I sometimes like to use subtyping as in:
cartesian <-- vector <-- point
which in conjuction with the the curiously recurring pattern (to inject the "self" most-derived type into cartesian) can be used to define:
unary - binary - + *
right in the base class.
(point-point) needs to be overriden in the point class though.
But of course, as Joel said, these sort of thing (inheritance) is unnecesary when generic programming is _fully_ used. But the inheritance comes in handy in non-generic but parametrized contexts (where you can parametrize on "cartesian" and pass either points or vectors without conversion)
Best
-- Fernando Cacciola SciSoft http://fcacciola.50webs.com
_______________________________________________ Unsubscribe & other changes: http://lists.boost.org/mailman/listinfo.cgi/boost
John Femiani wrote:
What would be the difference between the cartesian and the vector types?
the vector class support operations that don't make sense for cartesian, like inner/outer products, normalization, length, etc. That's why I don't derive point from vector. Fernando
John Femiani wrote:
What would be the difference between the cartesian and the vector types?
the vector class support operations that don't make sense for cartesian, like inner/outer products, normalization, length, etc.
That's why I don't derive point from vector.
Fernando
I see. I was thinking Cartesian would have all the operations of a point and a vector.
-----Original Message----- From: boost-bounces@lists.boost.org [mailto:boost-bounces@lists.boost.org] On Behalf Of Michael Fawcett Sent: Friday, October 05, 2007 12:01 PM To: boost@lists.boost.org Subject: Re: [boost] Generic Point class and algorithms (was: [GTL]- geometric template library - determininginterest)
On 10/5/07, John Femiani <JOHN.FEMIANI@asu.edu> wrote:
On 10/5/07, John Femiani <JOHN.FEMIANI@asu.edu> wrote:
If we want boost to have a point class I think it will really
have
to be
a set of point adapters and point concepts that work for existing types. There are too many points out there that we would have to interact with, both outside of boost and also within boost. For instance it would be nice if algorithms worked with both Boost.Point and the CGAL
I suggested something similar to this during a review (either Andy Little's Quan, or Boost.Units, I can't remember). For example, a Boost dot_product could be implemented as such:
// Note: *SomethingDeducedHere* would be some BOOST_TYPEOF magic template <typename LHS, typename RHS> *SomethingDeducedHere* dot_product(const LHS &lhs, const RHS &rhs) { return get<0>(lhs) * get<0>(rhs) + get<1>(lhs) * get<1>(rhs) + get<2>(lhs) * get<2>(rhs); }
Basically, just assume the point type acts like a tuple or Fusion sequence. Then all the algorithms written can be used with any
Just some thoughts on dealing on the ditinction: Game programmers use homogeneous coordinates; all points and vectors have an extra coordinate. Therefore a 3D point takes four coordinates, (w,x,y,z), but the same point has multiple representations. I.e. (1, x, y, z) == (2, 2*x, 2*y, 2*z). In homogenous coordinates a vector is the same as a point with w = 0. Most people think by default about points and vectors which are projected to the affine plane (divide by w to find an equivalent point with w == 1). Thus points have homogeneous coordinates with w=1, and vectors can not be projected because their homogenous coordinate is at zero (they are called points at infinity because a point approaches infinity on the plane when w approaches zero). A point library should support homogenous or projective coordinates, as well as affine points, and affine vectors. If an operation on an affine point would cause it to leave the affine plane, then the operations result type should be homogenous coordinates. Otherwise it should return an affine point. If an operation is guaranteed to produce an affine vector, then its result type should be a vector. Basically it should work like this (don't complain about my syntax pleas :): Template<...> class homogenous_coordinates; Template<...> class affine_point; Template<...> class affine_vector; homogenous_coordinates = affine_point+affine_point homogenous_coordinates = scalar*affine_point affine_vector = affine_point - affine_point affine_point = affine_point + affine_vector //... more .... //a point can be turned to a vector by subtracting the origin affine_vector = affine_point.minus_origin(); //homogenous coords can be assigned from affine points or vectors homogenous_coordinates = affine_point; homogenous_coordinates = affine_vector; //a homogenous point might have the same //syntax as a variant of affine_point and affine_vector affine_point* point = get<affine_point*>(&homogenous_coordinate) struct point_visitor: static_visitor<..> { void operator() (affine_point& ) { .. } void operator() (affine_vector& ) { .. } }; Apply_visitor(point, point_visitor() ); I hope this expresses the idea enough for discussion. -- John point. point
class (with a little work in some cases).
--Michael Fawcett
Sounds great to me. Can or should we formalize this into a set of concepts specific to points? Coordinate access is only a part of what a point rewuires; There is the tricky relationship between points and vectors (not std::vector!) and homogenous coordinates.
I.e. point+point is undefined, point-point is a vector, etc...
This has been the source of quite a bit of contention in the past. The problem is, there are scientific users and applications where the distinction is highly important, and then there are game developers (and others I'm sure) who frequently mix both for optimization tricks and compatibility with the graphics API.
If you can provide the distinction with no run-time overhead, and a no-overhead conversion to and from, I think both parties would sign off on it.
--Michael Fawcett _______________________________________________ Unsubscribe & other changes: http://lists.boost.org/mailman/listinfo.cgi/boost
Michael Fawcett wrote:
On 10/5/07, John Femiani <JOHN.FEMIANI@asu.edu> wrote:
If we want boost to have a point class I think it will really have to be a set of point adapters and point concepts that work for existing types. There are too many points out there that we would have to interact with, both outside of boost and also within boost. For instance it would be nice if algorithms worked with both Boost.Point and the CGAL point.
I suggested something similar to this during a review (either Andy Little's Quan, or Boost.Units, I can't remember). For example, a Boost dot_product could be implemented as such:
// Note: *SomethingDeducedHere* would be some BOOST_TYPEOF magic template <typename LHS, typename RHS> *SomethingDeducedHere* dot_product(const LHS &lhs, const RHS &rhs) { return get<0>(lhs) * get<0>(rhs) + get<1>(lhs) * get<1>(rhs) + get<2>(lhs) * get<2>(rhs); }
Basically, just assume the point type acts like a tuple or Fusion sequence. Then all the algorithms written can be used with any point class (with a little work in some cases).
In my world, structs are tuples and tuples are structs. Duality. The minimum interface, if you guys do not want to fuss around with fusion, is this: 1) a metafunction to get the size of the tuple (dimensions for points). 2) a metafunction to get the element type given an index. 3) a get/at_c function that returns the actual data. That's all. I can provide a non-intrusive adapter for that for Fusion easily for those who want to do more aggressive generic programming on these specialized tuples. Your interface itself need not have any hard dependency on fusion. Regards, -- Joel de Guzman http://www.boost-consulting.com http://spirit.sf.net
-----Original Message----- In my world, structs are tuples and tuples are structs. Duality. The minimum interface, if you guys do not want to fuss around with fusion, is this:
1) a metafunction to get the size of the tuple (dimensions for points). 2) a metafunction to get the element type given an index. 3) a get/at_c function that returns the actual data.
That's all. I can provide a non-intrusive adapter for that for Fusion easily for those who want to do more aggressive generic programming on these specialized tuples. Your interface itself need not have any hard dependency on fusion.
Regards, -- Joel de Guzman
Well coordinate access is only a part of what makes a point a hard-sell. There are hundreds of years of geometry and many API's to contend with as well. I kind of think (hope) that if the scope is kept extremely limited then it is possible to come up with generic point concepts, and maybe a reference implementation, that would make everybody happy. Is the boost wiki where these ideas could be fleshed out? -- John
John Femiani wrote:
-----Original Message----- In my world, structs are tuples and tuples are structs. Duality. The minimum interface, if you guys do not want to fuss around with fusion, is this:
1) a metafunction to get the size of the tuple (dimensions for points). 2) a metafunction to get the element type given an index. 3) a get/at_c function that returns the actual data.
That's all. I can provide a non-intrusive adapter for that for Fusion easily for those who want to do more aggressive generic programming on these specialized tuples. Your interface itself need not have any hard dependency on fusion.
Regards, -- Joel de Guzman
Well coordinate access is only a part of what makes a point a hard-sell. There are hundreds of years of geometry and many API's to contend with as well. I kind of think (hope) that if the scope is kept extremely limited then it is possible to come up with generic point concepts, and maybe a reference implementation, that would make everybody happy. Is the boost wiki where these ideas could be fleshed out?
Sure. That's why I said "minimum". The minimum I need involves only structural information. I'm sure there are more domain specific interfaces required of points. Regards, -- Joel de Guzman http://www.boost-consulting.com http://spirit.sf.net
Well coordinate access is only a part of what makes a point a
hard-sell.
There are hundreds of years of geometry and many API's to contend with as well. I kind of think (hope) that if the scope is kept extremely limited then it is possible to come up with generic point concepts, and maybe a reference implementation, that would make everybody happy. Is the boost wiki where these ideas could be fleshed out?
Sure. That's why I said "minimum". The minimum I need involves only structural information. I'm sure there are more domain specific interfaces required of points.
Regards, -- Joel de Guzman
Agreed -- but semantics get especially tricky here I think. The distinction between a point and a vector is lost if all you care about are lists of coordinates, for instance. You can do things to lists of coordinates that you should not be able to do with points. -- John
John Femiani wrote:
Well coordinate access is only a part of what makes a point a hard-sell. There are hundreds of years of geometry and many API's to contend with as well. I kind of think (hope) that if the scope is kept extremely limited then it is possible to come up with generic point concepts, and maybe a reference implementation, that would make everybody happy. Is the boost wiki where these ideas could be fleshed out? Sure. That's why I said "minimum". The minimum I need involves only structural information. I'm sure there are more domain specific interfaces required of points.
Regards, -- Joel de Guzman
Agreed -- but semantics get especially tricky here I think. The distinction between a point and a vector is lost if all you care about are lists of coordinates, for instance. You can do things to lists of coordinates that you should not be able to do with points.
Indeed. That's the domain specific (geometry domain) part. I do care about that, but I'll leave you guys to deal with that. My main concern is the most general mapping of different tuple types (including structs). That includes, but is not limited to, points and coordinate sequences. Regards, -- Joel de Guzman http://www.boost-consulting.com http://spirit.sf.net
participants (5)
-
Fernando Cacciola -
François Duranleau -
Joel de Guzman -
John Femiani -
Michael Fawcett