Closest point on mesh

Helper

THE POST BELOW IS MORE THAN 5 YEARS OLD. RELATED SUPPORT INFORMATION MIGHT BE OUTDATED OR DEPRECATED

On 01/09/2012 at 02:21, xxxxxxxx wrote:

Hi everyone! I'm currently looking into ways of finding the point on a polygonal mesh that is closest to an arbitrary point in space.
In Maya there is a pointOnSurface command in the Python SDK and in Cinema we have the Shrinkwrap Deformer and Constraints (set to clamp and surface), that must use similar algorithms internally.
Contrary to what I thought at first the problem is far from trivial and so far I haven't been able to find a sure fire way to find that point.
A method like this could be very useful for particles interacting with surfaces, so if anybody here knows more about the subject than I do and likes to share, it would be of great help.

Helper

THE POST BELOW IS MORE THAN 5 YEARS OLD. RELATED SUPPORT INFORMATION MIGHT BE OUTDATED OR DEPRECATED

On 01/09/2012 at 14:58, xxxxxxxx wrote:

Hello Sparkle,

have you actually tried to accomplish something like this? Thinking about this step-by-step actually reveals a solid algorithm (although it may not be the fastest).

- Iterate over each point
- Compute the distance of the current point and your point
- Save a reference to the point that resulted in the smallest distance-value.

An example implenentation could look like this:

def nearest_point(op, point) :  
  """ @param op: The polygon-object to operate on  
      @param point: A c4d.Vector in global space.  
      @returns: ``[point, distance, index]`` *point* is given in local space.  
                None on failure.  
      """  
  points = op.GetAllPoints()  
  if not points: return None  
  
  matrix = op.GetMg()  
  points = iter(points)  
  
  mesh_point = points.next()  
  result = [mesh_point, (mesh_point * matrix - point).GetLength(), 0]  
  index  = 1  
  while True:  
      try:  
          mesh_point = points.next()  
      except StopIteration:  
          break  
  
      distance = (mesh_point * matrix - point).GetLength()  
      if distance < result[1]:  
          result = [mesh_point, distance, index]  
  
      index += 1  
  
  return result

-Niklas

Helper

THE POST BELOW IS MORE THAN 5 YEARS OLD. RELATED SUPPORT INFORMATION MIGHT BE OUTDATED OR DEPRECATED

On 02/09/2012 at 00:44, xxxxxxxx wrote:

Hey Niklas, thanks for your detailed answer. Unfortunately I think wasn't specific enough about what I want to achieve.
I actually want find the closest point on the surface of the mesh, which can be very different from the closest vertex.

At first I thought it would be enough to calculate the closest vertex, get the adjacent polygons and their normals and then shoot a ray for each normal from the query point, but apart from being inaccurate this method might not get you any point at all, when there clearly has to be a closest point at all times.

Helper

THE POST BELOW IS MORE THAN 5 YEARS OLD. RELATED SUPPORT INFORMATION MIGHT BE OUTDATED OR DEPRECATED

On 02/09/2012 at 01:05, xxxxxxxx wrote:

As i remember a presentation of Manuel Merkle from Aixsponza, they used Closest point on mesh - node in project. But he unwrapped idea/algo that multiple ray/points scattered mesh so need density of clone-mesh in memory(also remember density of fluid engines for obstacles)

Helper

THE POST BELOW IS MORE THAN 5 YEARS OLD. RELATED SUPPORT INFORMATION MIGHT BE OUTDATED OR DEPRECATED

On 02/09/2012 at 01:21, xxxxxxxx wrote:

The pointer to Manuel isn't bad. At Aixsponza they have all sorts of custom built goodies. Though, as far as Manuel is willing to give out information on this is on another page.
Unfortunately I didn't really understand your last sentence.

Helper

THE POST BELOW IS MORE THAN 5 YEARS OLD. RELATED SUPPORT INFORMATION MIGHT BE OUTDATED OR DEPRECATED

On 02/09/2012 at 02:24, xxxxxxxx wrote:

Not quite sure if we're talking of the same person, but I think so. (Dunno his name anymore). I saw a presentation on the Siggraph 2012 for C4D where he presented the breakdown of a commercial project. They created a node for calculating the closest vertex on the mesh. But this is a far more advanced technique. There's an XPresso node in the presets that does what you want, but is very slow because it sends rays throughout the whole mesh. Their implementation created an OcTree of the mesh before sending out rays.

Helper

THE POST BELOW IS MORE THAN 5 YEARS OLD. RELATED SUPPORT INFORMATION MIGHT BE OUTDATED OR DEPRECATED

On 03/09/2012 at 01:17, xxxxxxxx wrote:

We are definitely talking about the same person. I think his Siggraph talk must be online somewhere on Cineversity, so I'll check that out.
The only XPresso preset I could find that looks close to what I'm after is called GetNearestPoint, but again it will only calculate the closest vertex and not the closest point on the surface.
Like you said, the query for the nearest neigbour is best done with an OcTree or an KdTree (Oc probably being better), but my real problem is the algorithm for finding that surface point.

*edit*
Ok, by now I found the setup, that you are probably talking about (Called OnSurface from Prime/Misc). While this will gibe me a point on the surface it is not the closest point, but simply the point projected onto the surface with the direction specified.
I have also watched Manuels presentation and he is doing exactly what I was looking for. I know he works closely with Maxon, so maybe some day his custom Xpresso node will be part of Cinema.

Helper

THE POST BELOW IS MORE THAN 5 YEARS OLD. RELATED SUPPORT INFORMATION MIGHT BE OUTDATED OR DEPRECATED

On 03/09/2012 at 03:40, xxxxxxxx wrote:

You may have already seen this but here is Sandi DolÅ¡ak's version in xpresso in case you would like to have a look. http://forums.cgsociety.org/showpost.php?p=7401860&postcount=9

Helper

THE POST BELOW IS MORE THAN 5 YEARS OLD. RELATED SUPPORT INFORMATION MIGHT BE OUTDATED OR DEPRECATED

On 03/09/2012 at 05:35, xxxxxxxx wrote:

Thanks for the link, but again this is just a closest vertex algorithm used. In the example the density of the mesh is so high, that the closest vertex is pretty close to the closest point on the surface. That's why the effect still works.

Knowing how brilliantly this was already implemented at Aixsponza I'm really debating with myself if I still feel like going through the lengths of understanding the BruteForce/OcTree approach. After all a Python implementation could never compete with C++ in terms of speed.

Hopefully the custom node gets released some day, or maybe even integrated in C4D R15.