# Cell Locators: Support Linear Transformations
**URL:** https://discourse.vtk.org/t/cell-locators-support-linear-transformations/8449
**Category:** Development
**Created:** [May 9, 2022, 4:40pm UTC](https://discourse.vtk.org/t/cell-locators-support-linear-transformations/8449 "2022-05-09T16:40:09Z")
**Posts on this page:** 20
**Page:** 1
### Author:  [@spyridon97](https://discourse.vtk.org/u/spyridon97)
#### Post date: [May 9, 2022, 4:40pm UTC](https://discourse.vtk.org/t/cell-locators-support-linear-transformations/8449/1 "2022-05-09T16:40:09Z")
When operating on datasets that vary over time, the new timesteps are **often** either the same or a linear transformation of the first timestep.
As of now, in the case of linear transformations, when a cell locator is utilized, you would have to rebuild the cell locator for the follow-up timesteps of a dataset.
[https://gitlab.kitware.com/vtk/vtk/-/merge\_requests/9149](https://gitlab.kitware.com/vtk/vtk/-/merge_requests/9149) introduces the concept of SupportLinearTransformation for cell-locators. This flag will be available for all vtkAbstractCellLocator subclasses except vtkOBBTree.
The implementation idea is the following:
When you call BuildLocator for the first timestep, you also ShallowCopy the initial points of the timestep.
At any subsequent timestep when you call BuildLocator, instead of re-building the cell locator, you extract the transformation matrix (and its inversion) from the subsequent timestep to the initial timestep using the [Kabsch algorithm](https://en.wikipedia.org/wiki/Kabsch_algorithm). The transformation matrix can be used inside any cell locator operation to query the first time timestep’s cell locator.
E.g. for the FindCell operation, the query point x is converted to xTrasform using the inverted transformation matrix back to the first timestep dataset’s space, then you get the correct sub-part of the cell locator that includes this cell, and then call EvaluatePosition using x.
One design choice that i would like your input for is if you think it would be better instead of adding this functionality to every cell locator, to create a new cell locator sub-class for every cell locator to support transformations.
1. Use transformation information in existing classes
1. Pros: no need to create and maintain new classes (there are 5 locator classes)
2. Cons: special case code is embedded into simple code which adds maintainability complexity
2. Create new sub-classes
1. Pros: special case code is handled in classes specifically designed for this special case, and possibly in the future more transformation types could be supported
2. Cons: new subclasses classes for each cell locator (there are 5 cell locator classes) add maintainability cost, and additional development cost
_Poll ([view on site](https://discourse.vtk.org/t/cell-locators-support-linear-transformations/8449/1))_
Any further thoughts or input would be more than welcome!
---
### Author:  [@mwestphal](https://discourse.vtk.org/u/mwestphal)
#### Post date: [May 9, 2022, 4:42pm UTC](https://discourse.vtk.org/t/cell-locators-support-linear-transformations/8449/2 "2022-05-09T16:42:01Z")
Ideally, support it on abstract level as much as possible so that the effort in each locator is minimal
---
### Author:  [@will.schroeder](https://discourse.vtk.org/u/will.schroeder)
#### Post date: [May 9, 2022, 5:10pm UTC](https://discourse.vtk.org/t/cell-locators-support-linear-transformations/8449/3 "2022-05-09T17:10:33Z")
Why can’t a single, new superclass (vtkLinearTransformCellLocator) do this work? The vtkLinearTransformCellLocator would hold an internal instance of _any_ cell locator (specified by the user), and it would be responsible for transforming points to be used by the initial, internal cell locator. Of course it would have to override each of the vtkCellLocators’s virtual methods etc, but the bulk of the implementation would be in the existing cell locator classes (which would be delegated to). This would avoid mucking up the existing implementations in the many cell locators and isolate what is a very specialized workflow, and only one new class would be needed.
---
### Author:  [@spyridon97](https://discourse.vtk.org/u/spyridon97)
#### Post date: [May 9, 2022, 5:25pm UTC](https://discourse.vtk.org/t/cell-locators-support-linear-transformations/8449/4 "2022-05-09T17:25:17Z")
Because all the cell locators would have to accept x, and xtranform for the FIndCell operation,
p1, p1Transform, p2, p2Transform, for IntersectWithLine operation, etc. So, the only benefit is moving TransformPointIfNeeded to vtkLinearTransformCellLocator, while the _complexity_ of the transformation is still preserved inside every cell locator.
Important note: You need **both** the x point, and xTransform point.
Also, if a function requires an internal Transfomation like
```nohighlight
IntersectWithLine(const double p1[3], const double p2[3], const double tol,
vtkPoints* points, vtkIdList* cellIds, vtkGenericCell* cell)
```
vtkLinearTransformCellLocator can not implement it in a straight forward way (maybe a function pointer could be added).
---
### Author:  [@Yohann\_Bearzi](https://discourse.vtk.org/u/Yohann_Bearzi)
#### Post date: [May 9, 2022, 5:30pm UTC](https://discourse.vtk.org/t/cell-locators-support-linear-transformations/8449/5 "2022-05-09T17:30:30Z")
I think what @will.schroeder proposed could work. You add an internal field `Transform` in the new cell locator class, and you transform any input using this transform, and then call the internal cell locator instance. It just needs to be made clear that queries in this locator are transformed using the internal `Transform`.
---
### Author:  [@will.schroeder](https://discourse.vtk.org/u/will.schroeder)
#### Post date: [May 9, 2022, 5:34pm UTC](https://discourse.vtk.org/t/cell-locators-support-linear-transformations/8449/6 "2022-05-09T17:34:56Z")
> I think what [@will.schroeder](https://discourse.vtk.org/u/will.schroeder) proposed could work. You add an internal field `Transform` in the new cell locator class, and you transform any input using this transform, and then call the internal cell locator instance. It just needs to be made clear that queries in this locator are transformed using the internal `Transform`.
Yup
---
### Author:  [@Timothee\_Chabat](https://discourse.vtk.org/u/Timothee_Chabat)
#### Post date: [May 10, 2022, 6:19am UTC](https://discourse.vtk.org/t/cell-locators-support-linear-transformations/8449/7 "2022-05-10T06:19:29Z")
I like the idea of composition proposed by @will.schroeder instead of doing yet another tons of subclasses, if it is possible. I think supporting it in each existing locator is a bad idea.
Also I was just thinking (though this is not the subject of this thread) : for this kind of dataset a file format where each subsequent timestep is saved as a transformation matrix and not the whole dataset could save a lot of RAM and disk space.
---
### Author:  [@will.schroeder](https://discourse.vtk.org/u/will.schroeder)
#### Post date: [May 10, 2022, 9:55am UTC](https://discourse.vtk.org/t/cell-locators-support-linear-transformations/8449/8 "2022-05-10T09:55:17Z")
I agree Timothee, the composition is a much cleaner design and it is reminiscent of vtkImplicitFunction (which has an internal transform and transforms points into and out of object space).
Also, your idea of using transformation matrices, whether specified from a file or programmatically, is what Spiros is trying to address - there are many symmetric datasets, or those that are transformed through space, that should not require rebuilding the locator. Also Spiros is working on ways to avoid rebuilding the locators when the geometry/topology of the dataset does _not_ change, but the attributes (cell data and point data) change.
---
### Author:  [@Timothee\_Chabat](https://discourse.vtk.org/u/Timothee_Chabat)
#### Post date: [May 10, 2022, 10:04am UTC](https://discourse.vtk.org/t/cell-locators-support-linear-transformations/8449/9 "2022-05-10T10:04:19Z")
Sounds awesome !
> [@will.schroeder](#):
>
> Also, your idea of using transformation matrices, whether specified from a file or programmatically, is what Spiros is trying to address
Do you mean that there is a global VTK effort of optimizing the usage of such datasets ? I understand that Spiros is trying to improve the locators performance for this use case, but I was just wondering if this was global to VTK or if it’s just focused on locators for now.
---
### Author:  [@will.schroeder](https://discourse.vtk.org/u/will.schroeder)
#### Post date: [May 10, 2022, 10:07am UTC](https://discourse.vtk.org/t/cell-locators-support-linear-transformations/8449/10 "2022-05-10T10:07:40Z")
For locators for now AFAIK
---
### Author:  [@spyridon97](https://discourse.vtk.org/u/spyridon97)
#### Post date: [May 10, 2022, 10:27am UTC](https://discourse.vtk.org/t/cell-locators-support-linear-transformations/8449/11 "2022-05-10T10:27:58Z")
I would like to to show you what i mean by the fact You need **both** the x point, and xTransform point.
As of now, this is the implementation of vtkCellLocator::FindCell:
```auto
vtkIdType vtkCellLocator::FindCell(double x[3], double vtkNotUsed(tol2), vtkGenericCell* cell,
int& subId, double pcoords[3], double* weights)
{
this->BuildLocator();
if (this->Tree == nullptr)
{
return -1;
}
double xTrans[3];
this->LinearTransformationInfo.InverseTransformPointIfNeeded(x, xTrans);
// check if x outside of bounds
if (!vtkAbstractCellLocator::IsInBounds(this->Bounds, **xTrans** ))
{
return -1;
}
vtkIdList* cellIds;
int ijk[3];
double dist2;
vtkIdType idx, cellId;
int leafStart = this->NumberOfOctants -
this->NumberOfDivisions * this->NumberOfDivisions * this->NumberOfDivisions;
// Find bucket point is in.
this->GetBucketIndices( **xTrans** , ijk);
// Search the bucket that the point is in.
if ((cellIds = this->Tree[leafStart + ijk[0] + ijk[1] * this->NumberOfDivisions +
ijk[2] * this->NumberOfDivisions * this->NumberOfDivisions]) != nullptr)
{
// query each cell
for (idx = 0; idx < cellIds->GetNumberOfIds(); ++idx)
{
// get the cell
cellId = cellIds->GetId(idx);
// check whether we could be close enough to the cell by
// testing the cell bounds
if (this->InsideCellBoundsInternal( **xTrans** , cellId))
{
this->DataSet->GetCell(cellId, cell);
if (cell->EvaluatePosition( **x** , nullptr, subId, pcoords, dist2, weights) == 1)
{
return cellId;
}
}
}
}
return -1;
}
```
Let’s try now to implement the idea of vtkLinearTransformationCellLocator
```auto
vtkIdType vtkLinearTransformationCellLocator::FindCell(double x[3], double vtkNotUsed(tol2), vtkGenericCell* cell,
int& subId, double pcoords[3], double* weights)
{
double xTrans[3];
this->LinearTransformationInfo.InverseTransformPointIfNeeded(x, xTrans);
return this->CellLocator->FindCell(x, xTrans, tol2, cell, subId, pcoords, weights);
}
```
vtkCellLocator will need a change of signature as it needs both x, and xtransform
```auto
vtkIdType vtkCellLocator::FindCell(double x[3], double xTrans[3], double vtkNotUsed(tol2), vtkGenericCell* cell,
int& subId, double pcoords[3], double* weights)
{
this->BuildLocator();
if (this->Tree == nullptr)
{
return -1;
}
// check if x outside of bounds
if (!vtkAbstractCellLocator::IsInBounds(this->Bounds, **xTrans** ))
{
return -1;
}
vtkIdList* cellIds;
int ijk[3];
double dist2;
vtkIdType idx, cellId;
int leafStart = this->NumberOfOctants -
this->NumberOfDivisions * this->NumberOfDivisions * this->NumberOfDivisions;
// Find bucket point is in.
this->GetBucketIndices( **xTrans** , ijk);
// Search the bucket that the point is in.
if ((cellIds = this->Tree[leafStart + ijk[0] + ijk[1] * this->NumberOfDivisions +
ijk[2] * this->NumberOfDivisions * this->NumberOfDivisions]) != nullptr)
{
// query each cell
for (idx = 0; idx < cellIds->GetNumberOfIds(); ++idx)
{
// get the cell
cellId = cellIds->GetId(idx);
// check whether we could be close enough to the cell by
// testing the cell bounds
if (this->InsideCellBoundsInternal( **xTrans** , cellId))
{
this->DataSet->GetCell(cellId, cell);
if (cell->EvaluatePosition( **x** , nullptr, subId, pcoords, dist2, weights) == 1)
{
return cellId;
}
}
}
}
return -1;
}
```
So, the benefit is that the transformation is moved outside, but that requires a change of signature is and the complexity of having both x, and xtranform inside vtkCellLocator::FInd cell is still there.
Also, as i said previously, if a function requires an internal Transformation like
```auto
IntersectWithLine(const double p1[3], const double p2[3], const double tol,
vtkPoints* points, vtkIdList* cellIds, vtkGenericCell* cell)
```
vtkLinearTransformCellLocator can not implement it in a straight forward way (maybe a function pointer could be added).
---
### Author:  [@spyridon97](https://discourse.vtk.org/u/spyridon97)
#### Post date: [May 10, 2022, 10:33am UTC](https://discourse.vtk.org/t/cell-locators-support-linear-transformations/8449/12 "2022-05-10T10:33:53Z")
Having the transform information would be great indeed instead of having to calculate them.
This would require, though a lot of changes in many readers/writers, but we can always start with the vtk ones. I don’t know if it would save tons of ram, as 2 timesteps, if you don’t need both, should never co-exist in the memory at the same time, because otherwise you can run out of memory. But if you need both, then you can save double the space.
---
### Author:  [@will.schroeder](https://discourse.vtk.org/u/will.schroeder)
#### Post date: [May 10, 2022, 11:29am UTC](https://discourse.vtk.org/t/cell-locators-support-linear-transformations/8449/13 "2022-05-10T11:29:55Z")
Okay this is pretty funny, I must be missing something, please enlighten me 🙂 Both the locater and the dataset are “transformed”, so why wouldn’t this work? FindCell() is unchanged (as it is in VTK master right now).
```auto
vtkIdType vtkLinearTransformationCellLocator::FindCell(double x[3], double tol2, vtkGenericCell* cell,
int& subId, double pcoords[3], double* weights)
{
double xTrans[3];
this->LinearTransformationInfo.InverseTransformPointIfNeeded(x, xTrans);
return this->CellLocator->FindCell(xTrans, tol2, cell, subId, pcoords, weights);
}
```
---
### Author:  [@spyridon97](https://discourse.vtk.org/u/spyridon97)
#### Post date: [May 10, 2022, 11:46am UTC](https://discourse.vtk.org/t/cell-locators-support-linear-transformations/8449/14 "2022-05-10T11:46:12Z")
As of now (in the current MR), when we reuse the locator, we need to reset the dataset so we can compute the transformation matrix (initial points vs new dataset points). Therefore, the dataset-\>GetCell call inside FindCell will not use the initial dataset. Also, this is needed because we need to give the correct pcoords, weights, etc.
If we were to go about implementing vtkLinearTransformationCellLocator without reseting the dataset, we would have to call ComputeTransformation externally with a public function, and in the FIndCell, after finish calling the internal FindCell, we would have to recall the GetCell, EvaluatePosition again for the actual dataset. If you think that this is a cleaner approach, then i can go ahead and implement it.
---
### Author:  [@will.schroeder](https://discourse.vtk.org/u/will.schroeder)
#### Post date: [May 10, 2022, 12:01pm UTC](https://discourse.vtk.org/t/cell-locators-support-linear-transformations/8449/15 "2022-05-10T12:01:07Z")
Okay now we’re getting somewhere, can you elaborate on what you mean by “resetting the dataset” ?
---
### Author:  [@spyridon97](https://discourse.vtk.org/u/spyridon97)
#### Post date: [May 10, 2022, 12:03pm UTC](https://discourse.vtk.org/t/cell-locators-support-linear-transformations/8449/16 "2022-05-10T12:03:09Z")
You can check an example here of how it is supposed to be used.
[https://gitlab.kitware.com/vtk/vtk/-/blob/3f69a33cf683eb896feac6a04a11fe6cb2acc883/Common/DataModel/Testing/Cxx/TestCellLocatorsLinearTransform.cxx](https://gitlab.kitware.com/vtk/vtk/-/blob/3f69a33cf683eb896feac6a04a11fe6cb2acc883/Common/DataModel/Testing/Cxx/TestCellLocatorsLinearTransform.cxx)
---
### Author:  [@Yohann\_Bearzi](https://discourse.vtk.org/u/Yohann_Bearzi)
#### Post date: [May 10, 2022, 1:01pm UTC](https://discourse.vtk.org/t/cell-locators-support-linear-transformations/8449/17 "2022-05-10T13:01:50Z")
I don’t follow why you need both `x` and `xTransform` in the signature. If T is your transform and M your original data set (not transformed), T M is your transformed data set. looking for a point p in T M is equivalent with looking for a point q = T^-1 p in M. So fetching q in the internal point locator of M should work without touching anything in the current implementation of locators.
---
### Author:  [@spyridon97](https://discourse.vtk.org/u/spyridon97)
#### Post date: [May 10, 2022, 1:07pm UTC](https://discourse.vtk.org/t/cell-locators-support-linear-transformations/8449/18 "2022-05-10T13:07:34Z")
Because you need to somehow create the transformation matrix, and also get the correct closestPoint pcoords, weights with the actual cell instead of the transformed cell.
If we were to go about implementing vtkLinearTransformationCellLocator without reseting the dataset, we would have to call ComputeTransformation externally with a public function, and in the FIndCell, after finish calling the internal FindCell, we would have to recall the GetCell, EvaluatePosition again for the actual dataset. If you think that this is a cleaner approach, then i can go ahead and implement it.
---
### Author:  [@Yohann\_Bearzi](https://discourse.vtk.org/u/Yohann_Bearzi)
#### Post date: [May 10, 2022, 1:12pm UTC](https://discourse.vtk.org/t/cell-locators-support-linear-transformations/8449/19 "2022-05-10T13:12:57Z")
> Because you need to somehow create the transformation matrix, and also get the correct closestPoint pcoords, weights with the actual cell instead of the transformed cell.
You store the transformation matrix inside the new locator that looks like that:
```auto
class TransformCellLocator : public vtkAbstractCellLocator
{
public:
void FindCell(/* args */)
{
// copy implementation proposed by Will
}
protected:
vtkTransform* Transform;
vtkAbstractCellLocator* Locator;
};
```
> If we were to go about implementing vtkLinearTransformationCellLocator without reseting the dataset
What do yo mean by resetting the dataset?
---
### Author:  [@spyridon97](https://discourse.vtk.org/u/spyridon97)
#### Post date: [May 10, 2022, 1:15pm UTC](https://discourse.vtk.org/t/cell-locators-support-linear-transformations/8449/20 "2022-05-10T13:15:07Z")
You need to also get the correct vtkGenericCell object too and use that to get the correct closestPoint (in other functions), pcoords, weights. These require the transformed dataset.
[Next page](https://discourse.vtk.org/t/cell-locators-support-linear-transformations/8449.md?page=2)