menpo icon indicating copy to clipboard operation
menpo copied to clipboard

PWA is very naive and should be optimised for small n_tri, large n_points

Open jabooth opened this issue 11 years ago • 2 comments

At the moment for PWA we query every point against every triangle to decide which triangle a point lies in (if it lies in one at all). After discusions with @patricksnape we decided it would be much more efficient to:

  • Calculate the bounding box of each triangle
  • Loop over each triangle and find the indices that fit in this bounding box. Test only these indices for containment of this triangle.
  • Any points that are outside the bounding box of each triangle are necessarily not in any triangle.

This assumes finding which points lie in which bounding box is fast (which it is relative to the alternative).

jabooth avatar Oct 10 '14 13:10 jabooth

I have a branch that has a very stupid implementation of this by changing the CythonPWA class to use a Ray-Intersection C++ framework. Then, looking up what triangles each point is in is extremely fast. However, the library I used (opcode) is way more heavyweight than we really need. All we probably need is a little OctTree type implementation to segment the triangles and then a simple point in triangle check written in C++.

patricksnape avatar Jan 05 '16 03:01 patricksnape

Also note that I looked around for a simple JS octree for the Landmarker for vertex/mesh intersection and in the end rolled my own which has been holding up very well:

https://github.com/menpo/landmarker.io/blob/master/src/js/app/model/octree.js

I'm sure a 2D variant of this in Cython be more than sufficient. All the code is there and tested in production, except for the intersection logic which would be slightly different (simpler in the PWA case).

jabooth avatar Jan 10 '16 07:01 jabooth