Simple Computational Geometry Library

[arash]

Hi all,

I've developed a simple computational library called FastGEO. It contains
a basic set of routines which some of you might find useful during your
development process.

The url is: http://fastgeo.partow.net


Any suggestions or comments would be very much appreciated.


Arash

__________________________________________________ ______
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

[cairnswm]

Looks interesting. I've downloaded it and will have a look at it from a 2D point of view.

[JernejL]

Looks interesting. I've downloaded it and will have a look at it from a 2D point of view.

same here, i was building my own 2d geometry library for my game, i'll try it out and report feedback.

[arash]

Sounds good, get back to me if any of you have an suggestions or improvements etc...



Arash
__________________________________________________ ______
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

[cairnswm]

Still havn't had a chance yet. I'm spending all the time I can on my own stuff at the moment (that doesn;t need geometry - will try get to it sometime soon.

[Sly]

[Hint] FastGEO.pas(1594): H2164 Variable 'CalcResult' is declared but never used in 'VertexAngle'

I like my code to compile with no hints or warnings.

Also, is there any reason why we could not use the Single float type instead of Double? All games that I know of use single precision floating point, not double precision. My approach to this would be to declare a new type based on a define.

[pascal]type
{$IFDEF USE_DOUBLE}
TFloat = Double;
{$ELSE}
TFloat = Single;
{$ENDIF}[/pascal]
and then do a find/replace to change 'Double' to 'TFloat'.

Single precision uses less memory, is faster (I believe this is still true) and everything else in games uses single precision (therefore no need to cast from single to double when calling these functions).

[edit]I have now implemented the double->single change and the library and examples still work fine. Though I did get an FPU exception once, so I masked the FPU exceptions in the initialization section (same as we have to when using Direct3D and OpenGL) and the problem never appeared again.

[arash]

Hi Sly,

I already fixed the problem with the CalcResult, just forgot to upload
the new version cause I'm still working on some other improvements.

As far as using singal or double goes, i guess its based on what you are
using the library for.

I wrote the library for computational geometry purposes hence a little
extra attention is paid to the operations that occur and also the types
used. As you might have noticed there is a lot of use of the function
IsEqual and NotEqual etc, for a person using functions that call those
methods you could replace them with = or <> respectively to speed up things.

But as far as I know doube is pretty fast, has a larger range and is
significantly less prone to forward errors.

that said feel free to modifiy and use the library in any way you see fit,
if you add any new methods etc, I would be very interested to know about them,
I'm always trying to add more 2D/3D stuff, and everytime I look there is still
a world of routines out there that needs to be implemented.



Regards



Arash
__________________________________________________ ______
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.

[Sly]

With the new TFloat type, I can easily change between double or single precision. With games, high precision is not often required so single precision is usually more than enough.

I'm looking at using the convex hull routines for implementation of terrain analysis in an RTS (based on the article "Terrain Analysis in an RTS - The Hidden Giant" in Game Programming Gems 3). In that article they use Graham's method (from "Computational Geometry in C" by Joseph O'Rourke) for calculating the convex hull. What method do you use?

[edit]Ahh, okay. I hadn't looked close to see the comment in ConvexHullUnit that says you use the Graham-scan method.

[Sly]

One other speed-up that could be implemented is to avoid passing back results by value. Get the user to pass in a record (TVector2D, TVector3D or whatever) that the function takes by reference. Returning a record by value is essentially doing memory copies into and out of the temporary record on the stack. Passing a record into the function means that all we are passing is a single pointer and the function populates the given record.

The Mul function that takes two TVector2D parameters and returns a TVector3D is implemented as a stub function.

If you add support for Delphi 2005, many of those functions could be given the inline directive. This would result in a huge speed increase.

[WILL]

Hmm... seems like a library worth looking into. Had I only the time :?

Perhaps in the not-too-distant future I'll get the chance. I hope you find success with it though. If it becomes big project be sure to let us know about it.