PDA

View Full Version : Simple Computational Geometry Library



arash
24-12-2004, 12:37 AM
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
24-12-2004, 04:28 AM
Looks interesting. I've downloaded it and will have a look at it from a 2D point of view.

JernejL
26-12-2004, 07:22 PM
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
27-12-2004, 09:10 AM
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
27-12-2004, 06:23 PM
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
29-12-2004, 03:59 AM
[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.

type
{$IFDEF USE_DOUBLE}
TFloat = Double;
{$ELSE}
TFloat = Single;
{$ENDIF}
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
29-12-2004, 04:32 AM
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
29-12-2004, 11:05 AM
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
29-12-2004, 11:41 AM
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
29-12-2004, 08:46 PM
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. ;)

arash
29-12-2004, 11:12 PM
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/CS250/2004/32.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
29-12-2004, 11:28 PM
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}
03-01-2005, 08:24 PM
Hi! does the library contains quaternion algebra? That would be great (and what i need, btw :P )

Would you consider adding it in the case?

Also, it would be great to have matrix support too

{MSX}
03-01-2005, 08:39 PM
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
06-01-2005, 03:49 AM
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
06-01-2005, 05:51 PM
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