Cell Locators: Support Linear Transformations

I’m pretty sure that pcoord and weights are linear transform invariant (am I wrong?). So you will get the same values in both cases.

I see a problem for vtkGenericCell when the cell is a vtkPixel or a vtkVoxel. Is it your concern?

pcoords and weights, should be the same indeed, but closestPoint will not be, which could be transformed, or re-evaluated, and generic cell needs to be re-extracted, or transform its points.

Can’t you do that in the new class? You find the cell, the closest point, and then you transform it back.

Basically, input point is p:

q ← T p
FindCell(q, transformedClosestPoint)
closestPoint ← T^-1 transformedClosestPoint

You can go back and forth between both original and transformed space within the cell locator you’re writing. The internal one doesn’t need to know about what is your space.

1 Like

And you do the same with the points of the output cell, you transform them back to your world.

I could, i was just trying to avoid performing extra transformation for better performance, but apparently this comes at the cost of adding code to the existing classes. Do you think it’s better to pay that extract cost for cleaner code?

I don’t see how you can avoid performing extra transformations if the data you’re working on needs to be transformed to be represented correctly. Even if you write the code for 10 locators, you’ll need to transform it back at some point, won’t you?

If i use the transformed dataset and x instead of xTransform to GetCell, EvaluatePosition, I don’t need to transform anything back. But i agree that it would better to pay the implementation cost in one class instead of many. So I will go with the solution that WIll suggested.

If you use the transformed data set, don’t you need to rebuild the locator? Maybe not in all cases but any locators that rely on world main axes (kd trees for instance) would need to be rebuilt.

I don’t see/understand why it’s needed.

In the case of a locator that uses a search structure that relies on world axes (kd tree, octrees, r-trees are the most obvious ones), the search is done using a subdivision of the space that is directed by those axes. If you rotate or scale them by a linear transform, you have to rebuild it to have a search structure that works.

Or maybe you wanted to provide the transformed data set so when you find the correct cell id you directly read it in the transformed data set? That might work but it makes things quite complicated for a negligible gain I would say. Searching has usually a complexity of O(log n) at best (unless using some hash table), and copying / transforming a handful of points has a constant complexity. You won’t see the difference.

1 Like

I see, I will follow that idea then. Thanks for the suggestions!

Yes. And a transformation is just math which adds negligible costs compared to data movement from/to memory.

Thanks Yohann, this is what I had in mind (transforming back and forth and leaving the cell locators alone).

I could, i was just trying to avoid performing extra transformation for better performance, but apparently this comes at the cost of adding code to the existing classes. Do you think it’s better to pay that extract cost for cleaner code?

Warning old codger on a soapbox: As a person that has maintained code bases for long periods of time, there is a huge cost to code that is too “complex”. Whenever I can I favor a simpler design, and less code, as compared to optimizations that are really hard to figure out (and change) in the future - these are significant maintenance burdens. To me overly complex code can be a warning that an algorithm / data structure needs rethinking. It drives me crazy when all sorts of fancy code is added to get a small <25% performance increase, when often rewriting the algorithm you can get cleaner code with 2, 5, 10x, or more performance increases. Of course I’ve written my share of complex code (and hopefully learned something :-)), but as Einstein says “Genius is making complex ideas simple, not making simple ideas complex” – this is my goal.

2 Likes

A new version that implements vtkLinearTransformCellLocator can be seen here https://gitlab.kitware.com/vtk/vtk/-/merge_requests/9149