[vtk-developers] vtkCellArray memory layout

Wed Mar 20 19:35:19 EDT 2013

David-

It's hard to answer this in a short manner which is what I prefer so please
forgive the length of this email. I am not sure what is motivating this
work so it's hard to address what you are doing. Having said this, I would
be very,very careful messing around with the innards of this class, since
it might mean delving deep into some very nasty algorithms like decimation,
etc. which could get ugly very fast (this may be FUD I'm not sure how hard
it would be without further investigation).

First, what you are describing is well known as documented in the VTK
Textbook which I assume you have read. Remember this structure is almost 20
years old and back in the day the cell array mapped directly into some
display list representations (I believe). We were supporting OpenGL, plus
other graphics systems and this was a very convenient way to represent
primitives like polygons and triangles, etc. Given this, it was very easy
to incrementally add other data structures to provide random access (cell
types) and links from points back to cells (cell links).

The other thing driving this structure was the ease/speed of memory
allocation into large contiguous arrays. It was and still is much faster to
allocate, and communicate such structures (read/write, sockets, etc.).For a
comparison look at the ITK mesh sometime, it's a mess, few use it, and it's
very fragmented. VTK has the virtue of simplicity which should not be
underrated. Sometimes we developers get too caught up in cool
implementation tricks and forget about our users and applications :-)

Having said all of this, times change as do underlying technologies
(graphics libraries) and our understanding of technology and how it is
used. VTK was originally envisioned as a read-only, demonstration
system:load data, demonstrate some algorithms, and visualize. To my
astonishment people now want to use it for crazy stuff like editing meshes
:-) I certainly think some clean up of the API is most likely warranted
since it grew organically over 20 years. And as you point out there are
definitely inefficiencies, and so on.

If I was going to do something today I would ditch the old stuff and create
a new vtkMesh. As a matter of fact Bob O'Bara and I did precisely this in a
project a while back; it held great promise and really enabled cool things
like editing, full topological hierarchy representation, etc. It would also
be nice to add modern concepts like iterators, etc. into the mix. But since
I don't quite now what you are trying to accomplish it's hard to make
recommendations.

W

On Wed, Mar 20, 2013 at 5: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
>
>
>

-- 
William J. Schroeder, PhD
Kitware, Inc.
28 Corporate Drive
Clifton Park, NY 12065
will.schroeder at kitware.com
http://www.kitware.com
(518) 881-4902
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://public.kitware.com/pipermail/vtk-developers/attachments/20130320/b2d17019/attachment.html>