[vtk-developers] vtkCellArray memory layout

Wed Mar 20 19:50:59 EDT 2013

ITK's mesh implements Guibas' quad edge mesh data structure:
/** \class QuadEdge
 * \brief Base class for the implementation of a quad-edge data structure as
 * proposed in "Guibas and Stolfi 1985"
 *
 * \author Alexandre Gouaillard, Leonardo Florez-Valencia, Eric Boix
 *
 * This implementation was contributed as a paper to the Insight Journal
 * http://www.insight-journal.org/browse/publication/122
 */
It is only valid for surfaces.

I agree with all of Will's cautions.

Bill

On Wed, Mar 20, 2013 at 4:35 PM, Will Schroeder
<will.schroeder at kitware.com>wrote:

> 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
>
> _______________________________________________
> 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/a065d55e/attachment.html>