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

Subject: Re: [boost] [geometry] area, length, centroid, behavior
From: Bruno Lalande (bruno.lalande_at_[hidden])
Date: 2009-03-03 04:29:41

Hi Michael,

>> 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.

I know all that, I was only thinking about the trick that consists in
using GL_TRIANGLE_FAN and the stencil buffer to display concave
polygons with concave holes. But indeed, it's a particular use case
and the base shape remains plain triangle.

> 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.

Agree completely.

> 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?

This is the good question, precisely. I think you guessed well in your
last sentence. Kernel could be a bunch of concepts with a ready-made
tag dispatching mechanism (or any other generic mechanism(s)). It can
seem very virtual, but if you look at the time we've already spent on
it and the number of discussions around that, it's far from being
trivial. And until an "official" library states all that, geometry
developers will continue to reinvent everything everywhere and work
with there do-it-all point classes.

In addition, I'd see a few algorithms on point. You can do what you
want, if you don't have points and basic arithmetics on them, you have
nothing, whatever the application domain. Things like dot and cross
product (wedge product if dimension-agnostic?) would also be included.
I find it pretty stupid to see programmers constantly rewriting such
widely used mathematical tools.

But as I was saying to Barend, finding the frontier is the hard part.
Do intersection algorithms belong in the kernel, and if yes, which
ones?...

Anyway, it doesn't sound ridiculous to me to have a very tiny (though
result of a long work) kernel. But again, is that kernel is not
validated by lots of algorithms in a wide range of specific domains,
it's worthless.

> 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.

Barend and me think like you.

> 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).

It's also my feeling but I can't be affirmative until I take a closer
look at his library. But indeed, as 45 degrees computations are
clearly a specific domain, it would belong in an extension, like GIS.

> I also think that they should use the same concepts and
> tags where appropriate.

Yes definitely.

> 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.

This is something I had thought about. I was wondering if all the
library authors could produce a kernel together, and continue to work
separately but on this same kernel. And the kernel would be proposed
as Boost.Geometry before any other more specific work. But I have to
elaborate all this, it's a bit unclear to me for now...

Bruno