- originally from pr 94
- commits from: jcapriot
- review from: rowanc1, fourndo, lheagy
New Implementation of the TreeMesh
At this point consider this branch as EXPERIMENTAL. There are many possible unsafe operations that could arise, so be careful (which will need to be enforced at a later time). The code is certainly not completely up to format standards, but at this point, just wanted to get a pull request going and allow anyone who wants to use it to test it out to find any bugs.
There are many changes to the TreeMesh implementation within this pull request, However it is mostly feature complete compared to the previous implementation with regards to the public members of the class.
It was mostly rewritten in a way that made the construction of the mesh and construction of the operators all done in c++/cython, which resulted in dramatic speedups. As a reference, the 97 nosetests on the tree in the previous implementation took 238.476s on my personal computer. This implementation took 20.281s.
The basic idea is that each object, (`node`, `edge`, etc.) is aware of the structure of the `TreeMesh` as each is a cpp class that contains references to other objects.
A few key differences:
- All tree construction is balanced (no need to call `tree.balance`, or pass `balance=True` to functions)
- `tree.refine` should only be called once (at this point) as it "finalizes" the tree. It might be good to add a flag to the tree initialization that would allow incremental additions (similar to `scipy.spatial.ConvexHull`) and then require a finalization operation to be done before any other operations.
- Interpolation is "lazy" 2nd order now for all `E`, `CC`, and `F` interpolation, meaning we triangulate the grid points to interpolate. Interpolating without triangulation on the TreeMesh is still a point of research. This is not as fast as it could be, but still faster than previously.
- Both `face` and `edge` operations are defined for 2D, (basically a re-ording of x-edges -> y-faces)
- Do not expect any ordering for the faces, edges, and nodes. They are whatever they have decided to be.
- Do not expect any of the private members of the class to have remained consistent between implementations.
- There are many other changes which should hopefully be apparent as you look through the code.
Big things that still need to be implemented
- Serialization, (do not expect to pickle this object and have it work, however with construction being much faster, this shouldn't slow down anyone too much while it is being worked on).
- `PlotImage` and `PlotSlice`.
There are also many areas that this code could be extended to handle different types of underlying meshs, as well as support for differing sizes of axes, but as I said before, the initial goal of this pull request is to mimic the behavior of the current implementation.
Other than that, I hope this speeds up the operations for those who need them.
Update
- Serialization should be implemented now (the `TreeMesh` is pickle-able)
- PlotImage and PlotSlice are also implemented.
- It also now support differing dimensions of the underlying `TensorMesh`
- Interpolation is now NOT triangulated, so do there is no longer 2nd order convergence of the non-node interpolation matrices.
- the `refine` and `insert_cells` function now have a `finalize` keyword arg that can be set to false if you want to do multiple steps of tree building