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

 Home / 3D Theory & Graphics / finding the crossed edge 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 29, 2005, 08:19 AM


I am trying to create particle repulsion on a 3d mesh with Greg Turk.
Making the points repel one another becomes straightforward once
we can map nearby points onto a given point’s plane. For each point
P on the surface we need to determine a vector S that is the sum of all
repelling forces from nearby points. The new position for the point
P on polygon A will be P’ = P + kS, where k is some small scaling
value. In many cases the new point P’ will lie on A. If P’ is not on
A, it will often not even lie on the surface of the polyhedron. In this
case, we determine which edge of A that P’ was “pushed” across and
also find which polygon (call it B) that shares this edge with A. The
point P’ can be rotated about the common edge between A and B so
that it lies in the plane of B. This new point may not lie on the polygon
B, but we can repeat the procedure to move the point onto the plane
of a polygon adjacent to B. Each step of this process brings the point
nearer to lying on a polygon and eventually this process will terminate.

I find the nearest edge as listing below. But if i run Turks alg, it sometimes comes in a infinite loop. I know the reason of this error. it has something to do with finding the nearest edge. If it is not in polygon A, it tests polygon B. But then he says the edge nearest to the new point is the edge that shares polygon A. So back to A and then back to B etc...
Does anyone knows a better solution?

Another question is to rotate all nearby points to a given point's plane.
I rotate all nearby points around the nearby edge so the lay in the given plane. Is there a more simple solution for this?

  2. // returns nearest point on a line segment [a,b]
  3. Vector3D Vector3D::nearestPoint(const Vector3D& a, const Vector3D& b, const Vector3D& p)
  4. {
  5.         // see if a is the nearest point
  6.         float dot_ta=Vector3D::dotProduct(p-a, b-a);
  7.         if(dot_ta<=0.0f)
  8.                 return Vector3D(a);
  10.         // see if b is the nearest point
  11.         float dot_tb=Vector3D::dotProduct(p-b, a-b);
  12.         if(dot_tb<=0.0f)
  13.                 return Vector3D(b);
  15.         // nearest point on line segment
  16.         float x=a[0]+((b[0]-a[0])*dot_ta)/(dot_ta+dot_tb);
  17.         float y=a[1]+((b[1]-a[1])*dot_ta)/(dot_ta+dot_tb);
  18.         float z=a[2]+((b[2]-a[2])*dot_ta)/(dot_ta+dot_tb);
  20.         return Vector3D(x,y,z);
  21. }


March 29, 2005, 02:49 PM

On each repulsion step, decrease the "factor" you move your point by, i.e. first step you have got A + k * V, so see how far the particle moves on the first polygon, and build a new distance d = k - oldmove - somesmallepsilon (0.00001 or similiar)... and then continue with that distance. Also, if k gets too small in any recursion step i.e. close to a certain epsilon, cull it to zero and leave your point on that polygon.

- Wernaeh

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