Re: [boost] [geometry] area, length, centroid, behavior

Subject: Re: [boost] [geometry] area, length, centroid, behavior
From: Michael Fawcett (michael.fawcett_at_[hidden])
Date: 2009-03-02 12:58:42

On Sat, Feb 28, 2009 at 7:18 PM, Bruno Lalande <bruno.lalande_at_[hidden]> wrote:
>
> Me and Barend discussed a bit about this, as I'm personally more
> concerned about game programing than GIS. So I guess that until now,
> my participation to the library has been influenced by this point of
> view.

Good to know.  While I work in GIS, I used to work in games, and it's
still a hobby of mine.

> What you say is true about what the library currently *provides*
> (GIS-oriented algorithms, even if polygons with holes can be used in
> games contrary to what you say, to display 2D vectorial fonts for
> instance).

Sure games *can*, but the base rendering API (e.g. D3D or OpenGL)
doesn't take care of it.  It's extra CPU work, and in the end, it
still becomes just a triangle.  For instance, OpenGL GL_POLYGON can
only do convex polygons with holes, and if the vertices are non-planar
you get undefined behavior.  Direct3D DrawPrimitives takes a
PrimitiveType to define how to interpret the data in the vertex stream
- valid PrimitiveTypes are LineList, LineStrip, PointList,
TriangleFan, TriangleList, and TriangleStrip.

Most video game teams will allow artists to model however they are
most comfortable.  As part of the export process, a custom exporter
will convert their 3D models (maybe with concave polygons, maybe with
holes, maybe non-planer) into the triangle only equivalent; triangles,
tri-strips, or fans, but it doesn't matter - they're still triangles
(3 vertices only) by the time they get to the game.  The modeling
package also handles polygon winding.

> I focused my efforts until now on the kernel because I think that the
> different application domains (GIS, games or whatever) won't
> necessarily share the same algorithms but can share the same kernel.
> If an algorithm is to slow because it can handles polygons with holes
> while game programmers use plain triangles, the key of the problem is
> to know if the library has been designed generically enough to sort
> that out. If mechanisms like tag dispatching and/or concept refinement
> are present and designed so well that I can add a triangle concept,
> take advantage of the algorithms already present for polygons, and
> specialize the ones that deserve to be, there's no problem. We can do
> that and game programmers will be happy with the library, like GIS
> ones were happy with the stuff already present.
>
> So the kernel is the key.

What types of things does the kernel encompass?  If the data types are
user-defined and the algorithms simply work over types that match
particular concepts, what is left?  It's all user defined types and
algorithms...or do you mean the kernel is all the concepts and
tag-dispatching machinery?

> Now the question is: is a Boost.Geometry library meant to contain all
> the stuff necessary for every application domain (which is basically
> impossible)? Personally, my approach would rather be to have
> Boost.Geometry proposing just a kernel and the most basic algorithms
> like point arithmetics, dot and cross products, etc... and having
> extensions for more precise application containing potentially a lot
> of algorithms...

Well, I sort of agree.  I can't figure out what the kernel
encompasses.  I think that GIS algorithms belong in Boost.GIS or
Boost.Geometry.GIS and that they should use concepts.  I also think
that Lucanus Simonson's work could co-exist in some other library or
extension since he only works with polygons that have angles of
multiples of 45 degrees (or something like that, I'm not sure on
specifics).  I also think that they should use the same concepts and
tags where appropriate.

I'm ambivalent as to whether they would be separate libraries or
simply extensions to a Boost.Geometry library as long as they work
together.

--Michael Fawcett