Rotation by 90 degrees in 2D is simply

xrot = -y
yrot = x

For an arbitrary rotation it is

xrot = x*cos(a) - y*sin(a)
yrot = x*sin(a) + y*cos(a)



- WitchLord

tcs - checked out your code.. it seems to be specific to triangles or convex n-gons at best, which is ok for most purposes, but what if, say, your polygon is an n-sided concave portal?

-goltrpoat


--
Float like a butterfly, bite like a crocodile.

If you wan''t to check if a point is inside a concave polygon you can do it by shooting a ray from the point in the plane of the polygon. If this ray crosses an odd number of edges in the polygon the point is inside, if it crosses an even number the point is outside.

Again it is much faster to do this in 2D and you convert from 3D to 2D as I stated before.

- WitchLord

of course its much faster to do it in 2d.. barycentric coordinates DO exist in 2d you know . badouel''s algorithm is normally implemented by collapsing the polygon to 2d.

--
Float like a butterfly, bite like a crocodile.

I have found two algorithms that are both fast:

Möller-Trumbore and Badouel

you can find the source code for these and a comparison at this page: http://www.acm.org/jgt/papers/MollerTrumbore97/

Although Badouel''s algorithm is slightly faster than Möller and Trumbore''s its major disadvantage is that is requires the triangles plane equation to be precalculated and stored together with the triangle vertices. For a model with 1000 triangles this is 4000 bytes, and it can be difficult to animate them as well.

If I were to choose algorithm I would choose the Möller-Trumbore algorithm because it is almost as fast as Badouel''s and it requires less data to keep track of. Not to mention the work of making sure you have correct normals after animation.

I hope the finding of these algorithms with source code can settle this litte dispute of which algorithm is faster. (Not that I didn''t enjoy it )


- WitchLord

I think I''ll keep my method. I HAVE to precalculate everything for some other reasons. And concave polygons ? I mean, how cares about such stuff ;-))))) Any API that renders concave polygons ? I hardly can imagine that anyone cares about poylgons that are not triangles, but concave polys ? No, this isn''t of any use in a fast realtime 3D engine.

But I''m interested in your method, can you post it ???

I hope you spoke to me, otherwise ignore this post.

Instead of showing you my algorithm, which I have never implemented. I will show you Badouel's algorithm instead, but I will remove the optimizations so that it is easier to understand. If you follow the link above you can see the optimized implementation of it.

bool IsPointInTriangle(float I[3], float V0[3], float V1[3], float V2[3], float N[3]){  // Collapse the largest component of   // the normal in order to convert to 2D  int i1,i2;  if( fabs(N[0]) > fabs(N[1]) && fabs(N[0]) > fabs(N[2]) )  {    // x is the largest component, ignore it in further calculations    i1 = 1;    i2 = 2;  }  else if( fabs(N[1]) > fabs(N[0]) && fabs(N[1]) > fabs(N[2)) )  {    // y is the largest    i1 = 0;    i2 = 2;  }  else  {    // z is the largest    i1 = 0;    i2 = 1;  }  // Compute the barycentric coordinates, by computing   // the signed area of each subtriangle made up of the  // intersection point and two vertices. The signed area  // of a triangle is computed as the crossproduct of two   // edges divided by two.   float areaTimes2 = (V1[i1]-V0[i1])*(V2[i2]-V0[i2]) - (V1[i2]-V0[i2])*(V2[i1]-V0[i1]);  float u = ((V2[i1]-I[i1])*(V0[i2]-I[i2]) - (V2[i2]-I[i2])*(V0[i1]-I[i1]))/areaTimes2;  float v = ((V0[i1]-I[i1])*(V1[i2]-I[i2]) - (V0[i2]-I[i2])*(V1[i1]-I[i1]))/areaTimes2;  // The triangle can be described with barycentric   // coordinates with the following formula:  // T(u,v) = (1-u-v)*V0 + u*V1 + v*V2  // Restrictions: u >= 0, v >= 0, u + v <= 1  // Test if the any of the restrictions are violated, if  // they are the point is outside the triangle  if( u < 0 // v < 0 // (u+v) > 1 )    return false;  // The point is inside the area  return true;} 

You should be able to spot a lot of optimizations here, but I think optimizations just make the code more difficult to read so I leave that until the last moment.

Beware that the code above is untested and may contain some nasty bugs. So make sure you understand what it does before you deside to use it.

A general pointer as to which algorithm to use: If you have the normal precalculated for you triangles you should use Badouel's algorithm since it is the fastest there is. If you don't have the normal you should instead use the one that Möller and Trumbore presents in their article, since it is almost as fast and doesn't need the normal.

- WitchLord

Edited by - WitchLord on 5/2/00 4:08:55 PM

I didn''t say anything about rendering concave polygons. I said that you may need determining whether a point falls within a concave polygon. Portal effects ring a bell?


--
Float like a butterfly, bite like a crocodile.