Simple Computational Geometry Library

[arash]

Hi Sly,

The algorithm used in the convex hull demo as described in the source code
is the graham scan with a complexity of O(nlogn), for 2D its the most
efficient method for calculating a convex hull however for higher dimensional
hulls 3D,4D,5D etc, QHull algorithm is advisable.

these are some good intros into the topic:

http://crypto.cs.mcgill.ca/~crepeau/...ConvexHull.pdf
http://camwiki.ucam.org/index.php?title=Graham_scan


As far as the record passing issue, AFAIK in object pascal when you pass
a type in a procedure or function with "var" or "out" reserved words you
are actually telling the compiler to pass the type by reference hence
there are no extra copy operations occurring.

As for inlining, I've had a chance to use Delphi 2005, however at this
point I don't see any need to begin modifying the code for compatibility
with "extra" features that have not yet become mainstream in the Delphi
world. Inlining is good if you know when and where to use it properly...


Regards




Arash Partow

__________________________________________________ ______
Be one who knows what they don't know,
Instead of being one who knows not what they don't know,
Thinking they know everything about all things.

[arash]

Hi Will,

I've got no intention for FastGEO to become a big project, its just a simple
set of routines that I like tinkering with.

One of the main reasons I wrote the library was because there was very little
available in the way of computational geometry for object pascal developers.
Hence for that reason and many others FastGEO came about.



Regards



Arash Partow

__________________________________________________ _____
Be one who knows what they don't know,
Instead of being one who knows not what they don't know,
Thinking they know everything about all things.

[{MSX}]

Hi! does the library contains quaternion algebra? That would be great (and what i need, btw )

Would you consider adding it in the case?

Also, it would be great to have matrix support too

[{MSX}]

My approach to this would be to declare a new type based on a define.
[CUT]
and then do a find/replace to change 'Double' to 'TFloat'.

I agree with that 100%
One can use it for whatever he wants, but in this way one can change between single and double very quickly.
I'll take away the compiler directive too, just leave

type TFloat = single;

and then people can change it to whatever (string for example :mrgreen: )

[arash]

Hi msx,

As I explained before and will try again, computational geometry
algorithms are implemented through a series of layering and folding
sequences. (for more info read topics regarding advanced principles
of software engineering - relating to computational science)

In many of these algorithms a problem known as proliferation occurs,
basically it means the output may require a higher resolution than
the input. Now in gaming you may decide you can round off the output
values (i.e.: rounding off the new x and y's that come out of a rotation
etc...)

The issue there is that you are rounding off the final answer not the
precision of the values in the intermediary steps - this is acceptable
to some degree because you can estimate and measure the potential error.

However If you were to go and replace the word double with some if-def'ed
type such as TMyNumeric or something like that, you would also be replacing
the types of the variables within the routines and not just the types of
the final output. This would lead to various types of inconsistencies
such as errors and different result on different types of processors etc,
depending on what the if-def'ed type is (i.e.: integer, cardinal etc)

For this reason I would not advise doing a "replace-all" of the type
double, but then in the end its up to you so do what you like.


As for quaternions and the transforms related to them, there are a
lot of libraries already dedicated to quaternion arithmetic they do
a much better job than I could ever manage, plus they all seem to
have very large support bases.
You may want to look at JEDI Math or SDL for starters.




Arash Partow

__________________________________________________
Be one who knows what they don't know,
Instead of being one who knows not what they don't know,
Thinking they know everything about all things.
http://www.partow.net

[Huehnerschaender]

Hi Arash,

I've just downloaded your library and I took a first look into it. It seems that there are all functions someone needs to test collisions of different objects against each other. That's what I was searching for, because I am not that genius in mathematics. Very nice work!

I will try to use it in my actual project (maybe I'll release it for the dogfight contest).

Thank you very much for making this open source!

Greetings,

Dirk