Cell Locators: Support Linear Transformations

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 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. 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
  • Support Linear Transformations inside each existing Locator
  • Create a new subclass for every locator to support linear transformation

0 voters

Any further thoughts or input would be more than welcome!

Ideally, support it on abstract level as much as possible so that the effort in each locator is minimal

1 Like

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.

1 Like

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

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).

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.

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.

Yup

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.

2 Likes

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.

Sounds awesome !

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.

For locators for now AFAIK

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:

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

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

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

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).

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.

Okay this is pretty funny, I must be missing something, please enlighten me :slight_smile: 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).

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);

}

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.

Okay now we’re getting somewhere, can you elaborate on what you mean by “resetting the dataset” ?

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

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.

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.

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:

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?

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.