[vtk-developers] vtkCellArray memory layout

Robert Maynard robert.maynard at kitware.com
Wed Mar 20 20:13:10 EDT 2013


The current layout is high advantageous when you consider a fixed pipeline,
where you iterate a single array and decide what cell types you are drawing
based on that single array. If we had a flat array of point ids without any
cell type we can easily create VBO's size based off that and quickly blast
the coordinates into that without branching.

I think a more complicated data structure is required, but dual arrays is
just the tip of the iceberg. The dual array structure still has really high
overhead for cell types like LINE, and TRIANGLE ( 50% and 33% increase in
size ). Currently we generally have datasets where cells are inserted into
CellArray grouped by cell type. So generally people load in all Tets and
than all Hexahedrons and so forth. This leads me to want to use a data
structure for cell types that represent contiguous spare ranges, ie [0,
300) are triangles, and [300,700] are quads. This reduces the memory
overhead dramatically when we have chunks of contiguous cells.


On Wed, Mar 20, 2013 at 7:50 PM, Bill Lorensen <bill.lorensen at gmail.com>wrote:

> 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
>
> _______________________________________________
> 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
>
>
>


-- 
Robert Maynard
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://public.kitware.com/pipermail/vtk-developers/attachments/20130320/9777fa61/attachment.html>


More information about the vtk-developers mailing list