[vtk-developers] vtkCellArray memory layout

[Bill Lorensen]

 A backward compatible approach might use an additional offset array into
the existing cell ids array.

On Wed, Mar 20, 2013 at 2:22 PM, David Lonie <david.lonie at kitware.com>wrote:

> Hi list,
>
> I have some questions about the vtkCellArray implementation, as well as
> some concerns about it after seeing some widespread abuses of its
> "internal" access methods.
>
> First, some background:
>
> The vtkCellArray currently stores cell information in the form
>
> [ cellSize1 id id ... cellSize2 id id ... cellSizeN id id ... ]
>
> where the cell sizes tell the number of points in each cell, and the ids
> are offsets into an array of points. So a real vtkCellArray may look
> something like:
>
> [(2) 0 1 (4) 3 2 0 4 (3) 1 3 5 (3) 3 5 7]
>
> where the numbers in parenthesis are the sizes of the cells.
>
> The docs do point out the current implementation is "totally inadequate"
> for random access, and I'm trying to understand what benefit it offers at
> the expense of random cell lookup? There is a vtkCellTypes class that will
> build up an offset array like the one I propose above, but this approach
> effectively doubles the amount of memory needed to store the cell sizes
> (per vtkCellTypes instance, which is often used by parent containers as
> well as filters), and time must be spent generating these supplemental
> structures each time the data changes.
>
> It seems to me that another implementation would be more useful. In
> particular, splitting the array into two, one with cell offsets and another
> with just point ids, transforming the above list into:
>
> [0 2 6 9 12] (offsets, last entry points to end of ids)
> [(0 1) (3 2 0 4) (1 3 5) (3 5 7)] (ids)
>
> The parentheses in ids just group cells for readability.
>
> This offers random access by cell id for free, and eliminates the
> time/memory spent building the supplemental vtkCellTypes objects. There is
> a slightly higher penalty for sequential access than before, due to having
> to iterate through two arrays, but I doubt that this would have serious
> performance impacts.
>
> I've also noticed that there are a number of "random access" methods like
> vtkCellArray::GetCell(vtkIdType loc, ...) that take an offset into the
> "mixed" internal array. This breaks encapsulation and is rather unintuitive
> -- I think it's safe to say that most developers would expect the "loc"
> argument to be a cell id. Since these methods depend on implementation
> details they are labeled as internal in the docs. However, they have public
> visibility and are used commonly throughout various filters, which often
> build up a structure similar to vtkCellTypes in order to perform their
> lookups.
>
> I'm asking at this time because I'm looking at some changes that may
> modify the vtkCellArray API/implementation anyway, and it'd be nice to fix
> up this mix of sequential access, unintuitive random-access, and auxiliary
> lookup structures into a more friendly and intuitive API. These changes
> would not be effected until after VTK 6.0 is out.
>
> Thoughts? Discussions? Alternate perspectives? All are welcome :-)
>
> Thanks,
> Dave
>
> _______________________________________________
> Powered by www.kitware.com
>
> Visit other Kitware open-source projects at
> http://www.kitware.com/opensource/opensource.html
>
> Follow this link to subscribe/unsubscribe:
> http://www.vtk.org/mailman/listinfo/vtk-developers
>
>
>


-- 
Unpaid intern in BillsBasement at noware dot com
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://public.kitware.com/pipermail/vtk-developers/attachments/20130320/c7e0ab37/attachment.html>