Re: [boost] Generic Point class and algorithms (was: [GTL]-geometric template library - determininginterest)

From: John Femiani (JOHN.FEMIANI_at_[hidden])
Date: 2007-10-05 15:42:21

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

> -----Original Message-----
> From: boost-bounces_at_[hidden]
[mailto:boost-bounces_at_[hidden]]
> On Behalf Of Michael Fawcett
> Sent: Friday, October 05, 2007 12:01 PM
> To: boost_at_[hidden]
> Subject: Re: [boost] Generic Point class and algorithms (was: [GTL]-
> geometric template library - determininginterest)
> 
> On 10/5/07, John Femiani <JOHN.FEMIANI_at_[hidden]> wrote:
> >
> > > On 10/5/07, John Femiani <JOHN.FEMIANI_at_[hidden]> 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
> _______________________________________________
> Unsubscribe & other changes:
> http://lists.boost.org/mailman/listinfo.cgi/boost