Not logged in, Join Here! or Log In Below:  
News Articles Search    

 Home / 3D Theory & Graphics / Particle Repulsion Account Manager
Archive Notice: This thread is old and no longer active. It is here for reference purposes. This thread was created on an older version of the flipcode forums, before the site closed in 2005. Please keep that in mind as you view this thread, as many of the topics and opinions may be outdated.

March 08, 2005, 03:27 AM


I am searching for the solution of the next problem, but i dont see it.
I wanna move particles across a mesh. A particle P can move outside his original polygon A. Now I have to rotate P around the common edge E of polygon B and A. Polygon B is the neighbour of A that is closest to Particle P.
How do I calculate the rotation axis and rotation angle?
Can anyone put me on the right way. Thanks.

Now i do the following in pseudocode:

  2. Vector3D p0=Edge[0];
  3. Vector3D p1=Edge[1];
  4. Vector3d axis;
  5. axis.crossproduct(p0-Particle.position, p1-Particle.position);
  6. axis.normalize();
  7. float rotAngle=dotproduct(PolA.normal, polB.normal);
  9. Quaternion q;
  10. q.setFromRotation(axis, rotAngle);
  11. Vector3D new=q.rotate(Particle.position);
  14. void Quaternion::setFromRotation(const Vector3D& axis, float angle)
  15. {
  16.         float sin=sinf(angle*0.5f);
  17.         m_vector.setXYZ(axis.getX()*sin, axis.getY()*sin, axis.getZ()*sin);
  18.         m_scalar=cosf(angle*0.5f);
  20.         normalize();
  21. }
  23. Vector3D Quaternion::rotate(const Vector3D &src)
  24. {
  25.         // v' = q * [0, v] * q^-1              
  26.         Quaternion v(src, 0.0f);
  27.         Quaternion tmp;
  29.         tmp=*this;
  30.         tmp.conjugate();
  31.         v.product(v,tmp);
  32.         tmp.product(*this,v);
  34.         return tmp.m_vector;
  36. }

Greetz takis.

Rui Martins

March 08, 2005, 05:38 AM

I would recommend you reread your post and pretend you don't know nothing about the problem in question (like we don't) and see if you can understand your question 8) ?

You have to think outside your context, so that you can explain your problem to us, or else we won't get it (different contexts).

In my view, a particle is a dot, a point, so why are you rotating it ?
A simple translation along the current poly surface should suffice.

"I wanna move particles across a mesh."
How ?
What does it have to do with the edge and the nearest neighbour ?

Why do you "... have to rotate P around the common edge E of polygon B and A. Polygon B is the neighbour of A that is closest to Particle P." ?

What is really the problem ?
You are telling us a solution and asking what is the problem with it, without telling us what the problem actually is.

What is the expect behaviour?
Is it due to gravity ? Other ?

Hope you get my point.


March 08, 2005, 06:38 AM

I am trying to simulate corrosion with particles.
A particle in my context is:
struct Particle{
Vector3d position, color;
int PolygonIndex ;

I make corrosion spots directly on the surface of a mesh. So i choose an existing particle P on the mesh. I put a new particle Pn on a distance 2*R from P.
There are now two possibilities:
- Pn falls in the same polygon as P. No problem.
- Pn falls outside the polygon that contains P.

In the second case, Pn does not lie on the surface of the mesh. So i have to get it back on the mesh. So the question is : How do i get Pn back on the mesh?

I hope this makes my problem more clearly.


Rui Martins

March 08, 2005, 08:42 AM

Yes it does !

So your problem is something like this:

  2.      P   v
  3.  ----+--.
  7.             + Pn
  10. Sideways View

  1.         |    /
  2.  Poly1  |   + Pn
  3.         |  /
  4.         | /
  5.         |/
  6.         . v
  7.        /|
  8.     P / |
  9.      +  |  Poly 2
  10.         |
  11.         |Edge (common)
  13. Top View

Basicly, what you have is a line between point P and Pn, and you want to wrap that line on the existing polys, right ?

You have to take an important fact into account, the Point Pn, may not be on an imediatly adjacent polygon either, depending on radius and polygon sizes.

You can search for texture splat and clipping for similar computation needs.

In my view, it's a recursive process, where you have something like this (in Pseudo Code)

  1. function drawWrapLine ( p0, p1, roly )
  2. {
  3.   cliPoint = ClipLine_with_currPoly ( p0, p1, poly)
  4.   if ( clipPoint exists )
  5.   {
  6.     drawLine ( P0, clipPoint )
  7.     adjPoly = get_adjacent_poly_on_point( clipPoint )
  8.     pr0 = findPointProjectionInPolyPlane( clipPoint, adjPoly)
  10.     // Recurse
  11.     drawWrapLine( pr0, p1, newPoly )
  12.   }
  13.   else
  14.     drawLine ( p0, p1 )
  15. }

NOTE 1: clipPoint "v" in ASCII drawing .
NOTE 2: The result of function findPointProjectionInPolyPlane is in the same infinite plane as newPoly, but it may not be inside the poly, hence the need for recursion.

I believe your question is:
How to implement function "findPointProjectionInPolyPlane" ?

Depending on the importance of using the actual radius or an aproximation:
1 - You could try to just project p1 into the newPoly, but this will distort distance (radius) depending on the manifold polys angle.
2 - If you want the length of the clip line to be exactly the radius, then you have to rotate p1 using the common edge.
3 - if you want the exact 3D Radius from the original particle, you have to use a sphere (of the specififed radius) and intersect it with the newPoly, which will give you a curve (equation) that you can solve by using a system, by adding an extra equation (line equation) that will restrict your result to a single value.
Basicly this is similar to solution 2, but to get the correct radius, you have to do some extra work.

Hope this helps, in your quest.


March 08, 2005, 09:00 AM

Thanks, i was already working on solution 2. Rotating p1 using the common edge.
If you want to translate it into quaternions.
Then the RotAxis=Edge.point1-Edge.point2 and the RotAngle=dotproduct(pol.normal, adjPol.normal).

But if i use this : i get the opposite z-value after rotation.
particle(3, 1, 10);
After rotation over (edgepoint2-edgepoint1) and angle Pi i get:


Rui Martins

March 08, 2005, 09:13 AM

Don't use quaternions for this !
They are very good for SLERPS, which you have no use for here!

Use regular matrix Math, of rotation using a vector (axis).

Your result is incorrect yes, but your example doesn't make much sense either, since Pi = 180 degrees, which means you are back at the same original poly.

You may be getting the incorrect Z because you are rotating on origin and not using the specific edge.
Rotating through origin will give you that result, that is how quaternions work, they can't have translation "baked" into them, only rotation.

Rui Martins

March 08, 2005, 11:01 AM

It just hit me a possibly simpler implementation is to define a perpendicular plane to the initial poly (the one where P0 is located, use the normal) and the direction vector (p1 - p0).

Then use always this plane to intersect with all the polys required (determined by recursion).After determining each new line-segment, just account the total length how you prefer, surface length, or 3D length (actual radius, nearest path, straight line).

This has the extra property that the final Pn points on a neighbour poly will keep it's orientation (direction) relative to it's original heading (direction), which in your case may be a desirable feature.

This also seems a lot simpler to implement, since intersection of 2 planes is a problem with a common solution and available tutorial and source on the web.


March 08, 2005, 11:21 AM

Read Greg Turk's paper... I don't remember if it's him or one of his references that describes in detail how to push particles across the surface of polygonal meshes

This thread contains 8 messages.
Hosting by Solid Eight Studios, maker of PhotoTangler Collage Maker.