Thread: [Algorithms] (no subject)

SourceForge Headquarters 225 Broadway Suite 1600 San Diego, CA 92101 +1 (858) 422-6466

unsubscribe algorithms

Hi,

I have assembly code versions of sine, cosine and tangent functions but now
I need arcsine, arccosine and arctangent functions, some of which are needed
in my quaternion code.  Can anyone provide references to how these can be
implemented on the Pentium processor using the FPU?

Regards,

Matt Davies
Programmer
Acclaim Studios, Cheltenham
+44 (0) 1242 533682
ICQ: 78711743

Look at fpatan and fsqrt, you should be able to impliment asin,atan and acos
in terms of fpatan... You can get quite a bit more performance over compiler
intrinsics or CRT functions. If you have a restricted input or can overlap
parts.
It may also be possible to use approximations of these functions(eg with
polynomials), depending on your requirments.

David

http://www.dblack.btinternet.co.uk
ICQ #: 24402391
Mobile: (UK) 0778 7836188
----- Original Message -----
From: "Matthew Davies" <MD...@ac...>
To: "Algorithms List (E-mail)" <gda...@li...>
Sent: Thursday, September 28, 2000 2:39 PM
Subject: [Algorithms] (no subject)

> Hi,
>
> I have assembly code versions of sine, cosine and tangent functions but
now
> I need arcsine, arccosine and arctangent functions, some of which are
needed
> in my quaternion code.  Can anyone provide references to how these can be
> implemented on the Pentium processor using the FPU?
>
> Regards,
>
>
> Matt Davies
> Programmer
> Acclaim Studios, Cheltenham
> +44 (0) 1242 533682
> ICQ: 78711743
> _______________________________________________
> GDAlgorithms-list mailing list
> GDA...@li...
> http://lists.sourceforge.net/mailman/listinfo/gdalgorithms-list
>

From: "Matthew Davies" <MD...@ac...>
> I have assembly code versions of sine, cosine and tangent functions but
now
> I need arcsine, arccosine and arctangent functions, some of which are
needed
> in my quaternion code.  Can anyone provide references to how these can be
> implemented on the Pentium processor using the FPU?

http://www.magic-software.com/MgcNumerics.html , files
MgcFastFunction.{h,cpp}
The code includes polynomial approximations for sin, cos, tan, atan, a
couple of other approximations for atan, and approximations for asin and
acos that involve polynomials multiplied by sqrt(1-x) for 0 <= x <= 1.  This
code alone ran 2.5 times faster than using calls to asin/acos, but it should
be easy enough for you to swap out sqrt for your own Pentium-specific fast
square root calculator.

--
Dave Eberly
eb...@ma...
http://www.magic-software.com

(This is a repost since the first one apparently never made it to the
list... While I was at it I completed it :)

Hi,

The thread "Checking for duplicate vertices quickly" where I proposed to use
the collision detection code to weld some 10K vertices gave birth to one or
two interesting tests......................

Ever wondered what fun it was to detect exact collisions among 10.000
individual cubes? I tell you, it's a lot of pain. So let's push the
enveloppe quite a bit:

www.codercorner.com/CubeHell.jpg
www.codercorner.com/CubeHell2.jpg

AABBs are drawn on the second screenshot.
Green = no collision
Yellow = AABBs overlap but cubes do not collide
Red = cubes are colliding

Not all cubes are visible on the same screen, "only" ~3300, else you just
can't see anything :) And yes it's "slow" (see the framerate in the corner
but eh ...!! That's 10000 individual cubes colliding down to the triangle
level !

This is absolutely useless and I know that, but it was so much fun to code I
must share that one with the list!

Note that for "only" 1024 cubes, it runs at ~70 fps on on Celeron 500, which
is kind of cool regarding Chris Hecker and Jeff Lander's "stress" tests of
physics engines, where 40 objects are said to be "a lot".

The algorithms used are the standard ones:
- sweep & prune
- OBB tree
- GJK
- Separating vector

...so nothing special, except the implementation looks robust.

I can change the collision detection method on the fly.

Currently the fastest method is a mix of GJK+Separating vector, in a
Q-Collide fashion. OBB "tree" is especially useless when the object is a
single box, and hence it runs way slower than the two other algorithms.
(about 6 times slower than the mixed GJK/SV, but this is a quite
experimental OBB tree implementation where I decompress the tree on the
f:ly, so the comparison may not be very fair!)

Guess what? I love collision detection :)

Cheers,

Pierre

> Ever wondered what fun it was to detect exact collisions among 10.000
> individual cubes? I tell you, it's a lot of pain. So let's push the
> enveloppe quite a bit:
>
> www.codercorner.com/CubeHell.jpg
> www.codercorner.com/CubeHell2.jpg
>

cool.

> Note that for "only" 1024 cubes, it runs at ~70 fps on on Celeron 500,
which
> is kind of cool regarding Chris Hecker and Jeff Lander's "stress" tests of
> physics engines, where 40 objects are said to be "a lot".

I think the bottleneck for these test would be the contact force computation
or integration stepsize (if penalty methods are being used etc). Not the
collision detection and contact determination.

>
> The algorithms used are the standard ones:
> - sweep & prune
> - OBB tree
> - GJK
> - Separating vector
>
> ...so nothing special, except the implementation looks robust.
>
> I can change the collision detection method on the fly.
>
> Currently the fastest method is a mix of GJK+Separating vector, in a
> Q-Collide fashion. OBB "tree" is especially useless when the object is a
> single box, and hence it runs way slower than the two other algorithms.
> (about 6 times slower than the mixed GJK/SV, but this is a quite
> experimental OBB tree implementation where I decompress the tree on the
> f:ly, so the comparison may not be very fair!)
>
> Guess what? I love collision detection :)

I personally _HATE_ collision detection a lot. There are just too many
special cases and it is difficult to get really accurate contact
manifolds(not to mention debugging this)... But I love working on the other
physics simulation problems:-)

David

http://www.dblack.btinternet.co.uk
ICQ #: 24402391
Mobile: (UK) 0778 7836188

> Guess what? I love collision detection :)

You must not have any artists thrashing the special cases for you. Game
artists have "collision special case" radar and will blow  your coding
confidence cache in the first ten frames of the simulation. I used to enjoy
physics coding... :^(

I think there's only three states for a collision system codebase:

- simplistic
- buggy
- abandoned

Uh oh...here comes Ron...run...

Enjoy your cubes....

But seriously, great work. Gimme the code. ;^)

heh,
yeah i have always found this funny :)

we think our code is solid, but we "protect" it :) :) :)
then the art/other people come around and bash our stuff. 
guess it makes you think "diffrently" and forces us to code "those cases"

peace.
akbar A.

you have "heard";
now read,
www.beconvinced.com

-----Original Message-----
From: gda...@li...
[mailto:gda...@li...]On Behalf Of
Matthew MacLaurin
Sent: Friday, September 29, 2000 11:41 AM
To: gda...@li...
Subject: RE: [Algorithms] Collision fun in cube hell

> Guess what? I love collision detection :)

You must not have any artists thrashing the special cases for you. Game
artists have "collision special case" radar and will blow  your coding
confidence cache in the first ten frames of the simulation. I used to enjoy
physics coding... :^(

I think there's only three states for a collision system codebase:

- simplistic
- buggy
- abandoned

Uh oh...here comes Ron...run...

Enjoy your cubes....

But seriously, great work. Gimme the code. ;^)

_______________________________________________
GDAlgorithms-list mailing list
GDA...@li...
http://lists.sourceforge.net/mailman/listinfo/gdalgorithms-list

Ok,
Interested people can download the demo here:
www.codercorner.com/CubeHell.zip

Pierre

New version for curious minds.
http://www.codercorner.com/CubeHell.jpg
http://www.codercorner.com/CubeHell.zip

Press R for profiling information. Now you can choose the #cubes as well.
(and check it actually runs with 10000 of them)

Yeah, one more gloomy sunday.

Pierre

> I think the bottleneck for these test would be the contact force
computation
> or integration stepsize (if penalty methods are being used etc). Not the
> collision detection and contact determination.

Certainly. I'm just pleased to see I have a lot of CPU time left to handle
the rest of the story.

> I personally _HATE_ collision detection a lot. There are just too many
> special cases and it is difficult to get really accurate contact
> manifolds(not to mention debugging this)... But I love working on the
other
> physics simulation problems:-)

The main problem of "collision detection for dummies" is that there are a
lot of papers and libs all around, and no global overview to help you out.
You can read about SOLID, I-Collide, V-Clip, whatever, but I've never seen a
paper explicitely telling the differences/common points between all the
available libs and all the published methods. You must read all of them to
start guessing. When I first had a look at CD some months ago now, I just
didn't know where to start - I guess there are some mails in the archive
with my first CD questions. My original goal was to do something like the
Kano demo, but I got stuck in the CD part for quite a long time :) Now, I
see the whole picture and I think I'll move to the next level - I still have
your resting contact code to play with, but so far I've never really
examined it. Was too early.

BTW, don't you have a demo of your physics engine, or something? It must be
quite cool now.

What do you mean by "accurate contact manifolds", exactly? For the moment,
the GJK part gives me the standard 4 contact figures (I know, you have a
fifth one :), and I can use that to derive contact normals, impulses, and
all the things needed to handle colliding contacts. I don't know if it's
"enough". (I leave the resting contacts out of the way, I'd like all the
other parts to be perfect before even thinking about resting contacts and
quadratic programs.)

Unfortunately, and as you know, the GJK algorithm only works for convex
polytopes. So, for non-convex ones I'm stuck with OBB-trees, which can
provide a list of colliding triangles, no more. I just don't know how to
derive a correct distance function for non-convex meshes. So, when two
non-convex meshes collide, I get the pair of colliding triangles, back up
one frame, and computes the distance between those two triangles. Is this
correct? Duno. The real closest-points, as computed by GJK, may lie
somewhere else, anywhere. But since the collision can occur anywhere as
well, it looks like the real distance function is not needed.

Hmm, I also took some shortcuts which may hurt. When I get back in time in
search of the exact collision time for non-convex meshes, I only do the CD
on the two triangles whose collision has originally been detected, in order
to save precious cycles of course. Does someone know if that's a valid move?

Pierre

Unsubscribe algorithms <jo...@ci...>

I want to fit a bspline sort of surface (i'm not
picky, could be something else) to a grid of
heightfield type data points.  I'm starting with
evenly spaced points, but don't want to restrict it to
that.  I want to get out something to fit triangles
to, and that I can do modest collision checking with
(nearest point on surface, above below surface). 
Isthis asking a lot?

Anyone who can point me towards the math I need to do
this? Web (i.e., free) resources are most appreciated.

regards,
kristian olivero

__________________________________________________
Do You Yahoo!?
Yahoo! Messenger - Talk while you surf!  It's FREE.
http://im.yahoo.com/

You might look into something called the minimum norm network (MNN), which I
know nothing about except that it is used to do fit locally smooth surfaces
to scattered data such as you describe. It may have some relationship with
B-splines, but it is not the familiar B-spline representation and it does
not require uniform spacing. Search the web!

Graham Rhodes

> -----Original Message-----
> From: gda...@li...
> [mailto:gda...@li...]On Behalf Of
> kristian
> Sent: Wednesday, October 18, 2000 3:03 PM
> To: gda...@li...
> Subject: [Algorithms] (no subject)
>
>
> I want to fit a bspline sort of surface (i'm not
> picky, could be something else) to a grid of
> heightfield type data points.  I'm starting with
> evenly spaced points, but don't want to restrict it to
> that.  I want to get out something to fit triangles
> to, and that I can do modest collision checking with
> (nearest point on surface, above below surface).
> Isthis asking a lot?
>
> Anyone who can point me towards the math I need to do
> this? Web (i.e., free) resources are most appreciated.
>
> regards,
> kristian olivero
>
>
> __________________________________________________
> Do You Yahoo!?
> Yahoo! Messenger - Talk while you surf!  It's FREE.
> http://im.yahoo.com/
> _______________________________________________
> GDAlgorithms-list mailing list
> GDA...@li...
> http://lists.sourceforge.net/mailman/listinfo/gdalgorithms-list
>

You might want to check out some of Hugues Hoppe's eariler work; he did a 
lot with fitting b-spline surfaces to points.
His web page is http://www.research.microsoft.com/~hoppe/

Max

At 12:03 PM 10/18/00 -0700, you wrote:
>I want to fit a bspline sort of surface (i'm not
>picky, could be something else) to a grid of
>heightfield type data points.  I'm starting with
>evenly spaced points, but don't want to restrict it to
>that.  I want to get out something to fit triangles
>to, and that I can do modest collision checking with
>(nearest point on surface, above below surface).
>Isthis asking a lot?
>
>Anyone who can point me towards the math I need to do
>this? Web (i.e., free) resources are most appreciated.
>
>regards,
>kristian olivero
>
>
>__________________________________________________
>Do You Yahoo!?
>Yahoo! Messenger - Talk while you surf!  It's FREE.
>http://im.yahoo.com/
>_______________________________________________
>GDAlgorithms-list mailing list
>GDA...@li...
>http://lists.sourceforge.net/mailman/listinfo/gdalgorithms-list

So long as the grid is regular this should be pretty easy - for =
non-uniform grids you either need to somehow make the grid uniform again =
or use something else. Uniform in this sense doesn't mean the vertices =
are distributed evenly in space merely that they are connected together =
in the form of a grid.

Given a subsection of the surface defined by a 4x4 block of vertices
[p00,p01,p02,p03]
[p10,p11,p12,p13]
[p20,p21,p22,p23]
[p30,p31,p32,p33]
to interpolate a new point on the surface in the centre square
[p11,p12]
[p21,p22]
at u,v where u and v vary between 0 and 1 and (0,0) is at p11 and (1,1) =
is at p22.

Q(u,v)=3D    [B0(u),B1(u),B2(u),B3(u)][p00,p01,p02,p03][B0(v)]
                                    [p10,p11,p12,p13][B1(v)]
                                    [p20,p21,p22,p23][B2(v)]
                                    [p30,p31,p32,p33][B3(v)]
Where=20
B0(x)=3D(1-x)^3/6      =20
B1(x)=3D(3*x^3-6*x^2+4)/6  =20
B2(x)=3D(-3*x^3+3*x^2+3*x+1)/6
b3(x)=3Dx^3/6        =20

The B?(x) functions are called the basis functions and as x is confined =
to [0..1] can be precalculated to some resolution eg. 1/100ths and =
stored in a table.=20
So for a trivial example u,v=3D(0,0)
B0(u)=3D1/6 B0(v)=3D1/6
B1(u)=3D4/6 B1(v)=3D4/6
B2(u)=3D1/6 B2(v)=3D1/6
B3(u)=3D0   B3(v)=3D0
Q(u,v)=3D[1/6,4/6,1/6,0][p00,p01,p02,p03][1/6]
                      [p10,p11,p12,p13][4/6]
                      [p20,p21,p22,p23][1/6]
                      [p30,p31,p32,p33][0]

Thats a BSpline. Something to bear in mind is that this derivation of =
the basis functions can only be used to interpolate over the period =
between the 2nd and 3rd vertices in either direction. So to interpolate =
over
p22,p23
p32,p33
for instance requires we make a new point matrix with p11 at the top =
left. One side effect of this is that we loose one row/column of patch =
squares off each edge of the full grid - this is countered by either 1/ =
Enlarging the full grid by 1 invisible vertex in each +/- direction =
which is commonly done by graphics packages. 2/ Wrapping the edges to =
form a cylinder/sphere 3/ Deriving a new set of basis functions defined =
over the periods between the 1st to 2nd and 3rd to 4th sections.

BSplines behave quite nicely but are very unlikely to actually pass =
through the vertices defining them. Catmull Rom (untensioned Cardinals) =
actually pass through all control vertices and behave well until you =
really start to fold the surfaces back on themselves when they start to =
bulge.
For Catmull Rom swap the basis functions above with
B0(x)=3D(-x^3+2x^2-x)/2
B1(x)=3D(3x^3-5x^2+2)/2
B2(x)=3D(-3x^3+4x^2+x)/2
B3(x)=3D(x^3-x^2)/2

Don't know if this helps.

David Hunt=20

----- Original Message -----=20
From: kristian <fir...@ya...>
To: <gda...@li...>
Sent: Wednesday, October 18, 2000 8:03 PM
Subject: [Algorithms] (no subject)

> I want to fit a bspline sort of surface (i'm not
> picky, could be something else) to a grid of
> heightfield type data points.  I'm starting with
> evenly spaced points, but don't want to restrict it to
> that.  I want to get out something to fit triangles
> to, and that I can do modest collision checking with
> (nearest point on surface, above below surface).=20
> Isthis asking a lot?
>=20
> Anyone who can point me towards the math I need to do
> this? Web (i.e., free) resources are most appreciated.
>=20
> regards,
> kristian olivero
>=20
>=20
> __________________________________________________
> Do You Yahoo!?
> Yahoo! Messenger - Talk while you surf!  It's FREE.
> http://im.yahoo.com/
> _______________________________________________
> GDAlgorithms-list mailing list
> GDA...@li...
> http://lists.sourceforge.net/mailman/listinfo/gdalgorithms-list

This is a test mail.

remove

Hi All

I have two question about octree (kd-tree) implementation
1. When I make octree, i need split some tris on codes border, or make ref.
counter for every triangle. But I render block tringles, no one. I and can't
check every triangle, and I can't  check block, this make some errors.
 Example: we have 2 nodes
1st node have tri-block with texture A and tri-block with texture B
2nd node also have tri-block with texture A and tri-block with texture C
Some triangles with texture A cross adjacent nodes borders.
I don't see any solve for this case, except split tringales.

 2. May be anybody use c-buffer for oclussion culling.
As I understand c-buffer, this is software render single pass without
texturing. I'am right ?
imho with modern video card this method make render more _slower_, not
faster. We can simple render all octree nodes with frustum culling and this
would be more faster.

May be exists other methods for octree oclussion culling for modern video
cards i.e GeForce.
Any ideas ?

Thanks for reply.

Radchenko Alexander,  Programmer,  Media Art
mailto ale...@md...     ICQ 109707188

__________________________________________

DVD´óÆ¬£¬Ò»ÂÉ10Ôª  http://shopping.263.net/category02.htm
ÃÀÈÝÑøÑÕ¡¢¼õ·ÊÊÝÉíÃØ¾÷  http://shopping.263.net/category10.htm

>
>__________________________________________
>
>DVD´óÆ¬£¬Ò»ÂÉ10Ôª  http://shopping.263.net/category02.htm
>ÃÀÈÝÑøÑÕ¡¢¼õ·ÊÊÝÉíÃØ¾÷  http://shopping.263.net/category10.htm
>
>
>
>
>
>_______________________________________________
>GDAlgorithms-list mailing list
>GDA...@li...
>http://lists.sourceforge.net/lists/listinfo/gdalgorithms-list
>
__________________________________________

DVD´óÆ¬£¬Ò»ÂÉ10Ôª  http://shopping.263.net/category02.htm
ÃÀÈÝÑøÑÕ¡¢¼õ·ÊÊÝÉíÃØ¾÷  http://shopping.263.net/category10.htm

Does anybody know of any good resources on the web that explain to an artist
the best ways of building models so that they maximise triangle strip
lengths?  Or any good books?  Please remember that I'm looking for something
that I can hand over to an artist, so minimal techno-babble please.

Cheers,

Mark Allen

Is GeForce the only card to support cube maps? (In both GL and DX)

Odin

-----Original Message-----
From: gda...@li...
[mailto:gda...@li...] On Behalf Of Mark
Allen
Sent: 14. september 2001 13:37
To: 'gda...@li...'
Subject: [Algorithms] (no subject)

Does anybody know of any good resources on the web that explain to an
artist
the best ways of building models so that they maximise triangle strip
lengths?  Or any good books?  Please remember that I'm looking for
something
that I can hand over to an artist, so minimal techno-babble please.

Cheers,

Mark Allen

_______________________________________________
GDAlgorithms-list mailing list
GDA...@li...
https://lists.sourceforge.net/lists/listinfo/gdalgorithms-list

Odin Jensen wrote:

> Is GeForce the only card to support cube maps? (In both GL and DX)

What I'd like to know is how much slower a cube-mapped surface is to render
than a single textured surface?

Surely it would be six times slower since it has to render the object six times?

Cheers, Paul.

Well. If you specify 6 textures, it's rather fast.
For true environment reflection, you have to render the scene 6 times
into the texture. The speed of that really depends on your card.
On GeForce3 it's quite fast, but I haven't put it into our game yet.
I'll post some timings once it's done, since the engine can fallback to
a normal environment map if the hardware doesn't support it or the user
turns it off.

Odin

-----Original Message-----
From: gda...@li...
[mailto:gda...@li...] On Behalf Of Paul
Firth
Sent: 14. september 2001 15:06
To: gda...@li...
Subject: Re: [Algorithms] Cubemap support

Odin Jensen wrote:

> Is GeForce the only card to support cube maps? (In both GL and DX)

What I'd like to know is how much slower a cube-mapped surface is to
render
than a single textured surface?

Surely it would be six times slower since it has to render the object
six times?

Cheers, Paul.

_______________________________________________
GDAlgorithms-list mailing list
GDA...@li...
https://lists.sourceforge.net/lists/listinfo/gdalgorithms-list