New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

Refactor SpatialObjects for clarity #465

Open
hjmjohnson opened this Issue Feb 5, 2019 · 6 comments

Comments

Projects
None yet
4 participants
@hjmjohnson
Copy link
Member

hjmjohnson commented Feb 5, 2019

Description

The SpatialObject classes have an unnecessarily complex hierarchy of transforms, contain the same (redundant) information (e.g., parent-child relationships and transforms) in multiple member variables, and impose the use of index space for object definitions when conceptually objects should simply exist in physical space. Additionally, there are many logic bugs and inconsistent concepts in the SpatialObject implementations.

We are seeking to increase the use and utility of spatial objects by simplifying and fixing their implementations.

This will break backward compatibility, but the hope is that the few who will be inconvenienced by this change will ultimately benefit from the bug fixes, speed improvements, and broad user base of spatialObjects that should result. Additionally, our hope is that a highly functional set of SpatialObjects can provide another data format for sharing analyses with other toolkits, such as VTK.

Challenges Being Addressed by Refactoring

Challenge 1) The SpatialObject classes have problematic APIs related to redundant constructs in SpatialObject variables and member functions and VNL TreeNode variables and member functions. For example, SpatialObjects have treenode member variables, treenodes have a set of transforms associated with them, and SpatialObjects provide a member functions for getting/setting treenode transforms, e.g., GetObjectToNodeTransform, GetNodeToParentNodeTransform. However, SpatialObjects also have their own transforms and associated member functions (e.g., GetIndexToObjectTransform, GetObjectToParentObjectTransform). These sets of transforms are partially redundant, are not conceptually consistent, and add unnecessary complexity to the classes.

Proposed Solution to Challenge 1) We are removing treenodes from SpatialObjects. There was no reason for the added complexity of treenodes. It is possible to represent objects and their relationships using only one ObjectToParent transform per object. Any additional transforms are gratuitous. Eliminating TreeNodes also reduce ITK's dependencies on VNL.

Challenge 2) TreeNodes also maintained the parent-child relationships between SpatialObjects, but SpatialObjects also had "InternalChildrenList" member variable and a "Parent" member variable for maintaining parent-child relationships. Maintaining these redundant representations was prone to errors.

Proposed Solution to Challenge 2) Eliminate the VNL treenodes from the SpatialObjects so that there is only one record of parent-child relationships. This also reduces ITK's dependency on VNL.

Challenge 3) The handling of children in various computations of IsInside, ValueAt, and Bounds is inconsistent and/or buggy for many SpatialObjects. Some implementations make these computations O(n^2) instead of O(n).

Proposed Solution to Challenge 3) Adding IsInsideChildren, ValueAtChildren and other helper classes to the top-level SpatialObject class simplifies the specification of the IsInside, ValueAt and other such object-specific classes in the derived classes. Also, now most derived classes need only implement IsInside and ComputeObjectBoundingBox member functions.

Challenge 4) All SpatialObjects must be specified in index space. This creates an unnecessary transform (and mental effort) for every object.

Proposed Solution to Challenge 4) After refactoring, if you want a Box or other object, you create it in physical space and manipulate it in physical space. You don't have to create an index space for the box before placing it in space using an indexToObject transform.

Challenge 5) While SpatialObjects have the concept of Index space, they do not use cosine directions with their index space. The segmentation of spatialObjects from images requires careful attention to handling multiple transforms that are inconsistent between images and the SpatialObjects.

Proposed Solution to Challenge 5) By having all objects exist in physicalSpace, then simply calling an image's TransformIndexToPhysicalPoint function is all that is needed to define the representation of a SpatialObject that is segmented from an image. This also simplifies viewing and combining SpatialObjects across and/or without images.

Challenge 6) Adding or removing an object to/from a parent could cause the object to move in space because their parent's parent's transforms were no longer being applied.

Proposed Solution to Challenge 6) With the refactoring, updates to ObjectToParentTransform are much easier to maintain as parent/child relationships change and as parameters change - rather than trying to maintain the many other transforms that use to come into play.

WIP Pull Request

See WIP :SpatialObjects V5 pull request #464

Versions

In preparation for ITKv5 release

API Changes: Philosophy

The philosophy that is driving the changes to the API is that we seek to clarify what coordinate space is being referenced when a function is called. We also want to make the interface more consistent with the rest of ITK, relying more heavily on ITK's Get/Set macros and the use of Update to harden parameter changes.

Migration Guide

Object Space

SpatialObjects have one primary coordinate space that is readily available to them, their ObjectSpace. This is the space in which the object was inherently defined. No transforms are applied to the points/values that get/set into this space. All children of an object are added into this space.

ObjectToParentTransform

SpatialObjects have only one transform that they directly control, their ObjectToParentTransform.
This transform specifies how an object's space is transformed to fit into its parent's ObjectSpace. The ObjectToParentTransform is an affine transform, and it is confirmed to be invertible when assigned, or the assignment fails.

WorldSpace

WorldSpace is not directly controlled by any SpatialObject except the SpatialObject at the top level of the parent-child tree hierarchy of Spatial Objects. That is, any SpatialObject that does not have a parent exists in a WorldSpace that is defined by applying its ObjectToParentTransform to its ObjectSpace.

Several member functions and variables are available to every SpatialObject so that they can readily access the WorldSpace in which they exist:

  • ComputeObjectToWorldTransform: Composes its ObjectToParentTransform with its parent's cached ObjectToObjectToWorldTransform, to determine the transform from the object's ObjectSpace to WorldSpace. This transform is always invertible. This call will cause all children objects to also update their cached ObjectToWorldTransform. This function should be called on the top level object once all children object's ObjectToParentTransforms have been set. This function should be called on children objects when their ObjectToParentTransforms have been changed. Due to the potentially high computational cost of this function, this function must be manually called by users.
  • GetObjectToWorldTransform: Returns the cached ObjectToWorldTransform. It is the user's responsibility to call ComputeObjectToWorldTransform when necessary, prior to calling GetObjectToWorldTransform, otherwise the returned transform may be "stale."
  • SetObjectToWorldTransform: This function updates the object's ObjectToParentTransform, using an inverse of the parent's cached ObjectToWorldTransform, so that the composition of those transforms equal the transform passed to this function. If an object has no parent, its ObjectToParentTransform is equal to its ObjectToWorldTransform.

Queries into ObjectSpace and WorldSpace

The member functions of SpatialObjects now specify if they reference ObjectSpace or WorldSpace

IsInside( point ) is now either IsInsideInObjectSpace( point ) or IsInsideInWorldSpace( point )
ValueAt( point, value ) is now either ValueAtInObjectSpace or ValueAtInWorldSpace
... the same holds true for EvaluateAt, DerivativeAt, IsEvaluableAt, ComputeMyBoundingBox

Other changes in the SpatialObjects base class

  • Update() calls ComputeMyBoundingBoxInWorldSpace and updates member variables that cache WorldSpace values.
  • Get/SetTypeName now accepts and returns std:string
  • MyBoundingBox and FamilyBoundBox replace LocalBoundingBox and BoundBox, respectively. These bounding boxes always exist in WorldSpace, so the function calls have been updated to be "GetMyBoundingBoxInWorldSpace".
  • AddObject has been changed to AddChild. Similarly, the SpaitalObject class also defines RemoveChild, RemoveAllChildren, GetChildren, GetNumberOfChildren.

Other changes in top-level SpatialObject classes

  • SpatialObjectPropery is no longer templated and does not derive from any other class. It is no longer referenced via a pointer.
  • SpaitalObjectPoints have also been updated to have member functions that make their space explicit, for example, you can query SOPoint.GetPositionInObjectSpace or GetPositionInWorldSpace. This necessitated each point now also maintaining a pointer to the SpatialObject that holds it (in order to access its ObjectToWorldTransform).
  • SceneSpatialObjects were eliminated. Their member functions GetNextAvailableId, CheckIdValidity, FixIdValidity, and FixParentChildHierarchyUsingParentIds are now member functions of all SpatialObjects.

Changes in SpatialObjects

The changes in specific SpatialObjects (e.g., ArrowSpatialObjects) have been extensive. Their APIs were changed to explicitly mention which space is being referenced. For example, the ArrowSpatialObject now has the member function SetDirectionInObjectSpace (rather than SetDirection). There were significant inconsistencies in such functions across SpatialObjects.

@hjmjohnson

This comment has been minimized.

Copy link
Member Author

hjmjohnson commented Feb 5, 2019

@aylward Thanks for the explanation. I made an issue to track discussions about this publically. Would you mind fixing the message of the issues/motivations for PR #464 so that we have a transparent history of this change?

👍 THANKS FOR TAKING THIS ON!

  • Will there be software guide changes needed?
  • Migration guide documentation updates.
  • Other wiki examples changes needed?
@aylward

This comment has been minimized.

Copy link
Member

aylward commented Feb 5, 2019

@hjmjohnson I have edited the description.

Yes, there will be software guide changes, migration guide documentation updates, and wiki example changes needed.

Volunteers are welcomed! :)

See WIP pull request #464.

@blowekamp

This comment has been minimized.

Copy link
Member

blowekamp commented Feb 5, 2019

This is awesome you are getting these fixes done!
I have couple initial thoughts/comments:

  • What is the compatibility with the file format (MetaIO)? Are previously saved SpacialObject going to exist at the same location when loaded?
  • Methods which did take index space coordinates, are they going to change the method name? ( I'm in favor of not silently changing the coordinates, and making the old code not compile )
  • More Testing. Testing is good but time consuming. Some of the newer GTest based vector comparisons may make this a little easier.
@aylward

This comment has been minimized.

Copy link
Member

aylward commented Feb 6, 2019

@blowekamp

  • Regarding I/O: I'm just beginning to work on the MetaIO component. Images will definitely not change/move. However, for other objects, because of errors in implementation and ambiguities in proper use, different applications will be impacted in different ways. If the objects were used stand alone (i.e., not in scenes/trees) then they are likely to appear in the same location.
    -- For this reason, I was thinking of creating a "new version" of the MetaIO file format. We could provide converters - and allow different apps to create different converters based on how they interpreted the transforms in spatialObjects. We could designate these new file formats by appending 2 to their suffix (e.g., ".tre2" and ".lnd2" or by adding and updating a "version" tag within those files.

  • Regarding member functions involving Index coordinates: they have been removed. Code that used them will no longer compile.

  • Regarding testing: this is going to be a big portion of this effort. The changes are so pervasive (and the prior logic bugs/inconsistencies were so pervasive), it is clear that extensive testing is needed.

@aylward

This comment has been minimized.

Copy link
Member

aylward commented Feb 19, 2019

Just added details on the API changes (and the driving philosophy for them) to the top-level box in this discussion. Looking forward to everyone's feedback!

Thanks goes to @HastingsGreer and @floryst for significant help - past and ongoing

@thewtex

This comment has been minimized.

Copy link
Member

thewtex commented Feb 19, 2019

Beautiful! The naming and behavior is much clearer, simpler, and it should be easy to use.

@phcerdan please take a look.

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment