<div dir="ltr">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.<div>
<div><br></div><div><div style>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.</div>
</div></div></div><div class="gmail_extra"><br><br><div class="gmail_quote">On Wed, Mar 20, 2013 at 7:50 PM, Bill Lorensen <span dir="ltr"><<a href="mailto:bill.lorensen@gmail.com" target="_blank">bill.lorensen@gmail.com</a>></span> wrote:<br>
<blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex">ITK's mesh implements Guibas' quad edge mesh data structure:<div><div>/** \class QuadEdge</div><div> * \brief Base class for the implementation of a quad-edge data structure as</div>
<div> * proposed in "Guibas and Stolfi 1985"</div>
<div> *</div><div> * \author Alexandre Gouaillard, Leonardo Florez-Valencia, Eric Boix</div><div> *</div><div> * This implementation was contributed as a paper to the Insight Journal</div><div> * <a href="http://www.insight-journal.org/browse/publication/122" target="_blank">http://www.insight-journal.org/browse/publication/122</a></div>
<div> */</div><div>It is only valid for surfaces.</div><div><br></div><div>I agree with all of Will's cautions.</div><span class="HOEnZb"><font color="#888888"><div><br></div><div>Bill</div></font></span><div><div><div class="h5">
<br><div class="gmail_quote">On Wed, Mar 20, 2013 at 4:35 PM, Will Schroeder <span dir="ltr"><<a href="mailto:will.schroeder@kitware.com" target="_blank">will.schroeder@kitware.com</a>></span> wrote:<br>
<blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex"><div dir="ltr">David-<div><br></div><div>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).</div>
<div><br></div><div>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).</div>
<div><br></div><div>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 :-)</div>
<div><br></div><div>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.</div>
<div><br></div><div>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.</div>
<div><br></div><div>W</div><div><br></div><div><br></div></div><div class="gmail_extra"><br><br><div class="gmail_quote"><div>On Wed, Mar 20, 2013 at 5:22 PM, David Lonie <span dir="ltr"><<a href="mailto:david.lonie@kitware.com" target="_blank">david.lonie@kitware.com</a>></span> wrote:<br>
</div><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex"><div><div><div dir="ltr">Hi list,<div><br></div><div>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.</div>
<div><br></div><div>First, some background:</div><div><br></div><div>The vtkCellArray currently stores cell information in the form</div><div><br></div><div>[ cellSize1 id id ... cellSize2 id id ... cellSizeN id id ... ]</div>
<div><br></div><div>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:</div><div><br></div><div>
[(2) 0 1 (4) 3 2 0 4 (3) 1 3 5 (3) 3 5 7]</div><div><br></div><div>where the numbers in parenthesis are the sizes of the cells.</div><div><br></div><div>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.<br>
</div><div><br></div><div>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:</div>
<div><br></div><div>[0 2 6 9 12] (offsets, last entry points to end of ids)</div><div>[(0 1) (3 2 0 4) (1 3 5) (3 5 7)] (ids)</div><div><br></div><div>The parentheses in ids just group cells for readability.</div>
<div><br></div><div>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.</div>
<div><br></div><div>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.</div>
<div><br></div><div>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.</div>
<div><br></div><div>Thoughts? Discussions? Alternate perspectives? All are welcome :-)</div><div><br></div><div>Thanks,</div><div>Dave</div></div>
<br></div></div><div>_______________________________________________<br>
Powered by <a href="http://www.kitware.com" target="_blank">www.kitware.com</a><br>
<br>
Visit other Kitware open-source projects at <a href="http://www.kitware.com/opensource/opensource.html" target="_blank">http://www.kitware.com/opensource/opensource.html</a><br>
<br>
Follow this link to subscribe/unsubscribe:<br>
<a href="http://www.vtk.org/mailman/listinfo/vtk-developers" target="_blank">http://www.vtk.org/mailman/listinfo/vtk-developers</a><br>
<br>
<br></div></blockquote></div><span><font color="#888888"><br><br clear="all"><div><br></div>-- <br>William J. Schroeder, PhD<br>Kitware, Inc.<br>28 Corporate Drive<br>Clifton Park, NY 12065<br><a href="mailto:will.schroeder@kitware.com" target="_blank">will.schroeder@kitware.com</a><br>
<a href="http://www.kitware.com" target="_blank">http://www.kitware.com</a><br><a href="tel:%28518%29%20881-4902" value="+15188814902" target="_blank">(518) 881-4902</a>
</font></span></div>
<br>_______________________________________________<br>
Powered by <a href="http://www.kitware.com" target="_blank">www.kitware.com</a><br>
<br>
Visit other Kitware open-source projects at <a href="http://www.kitware.com/opensource/opensource.html" target="_blank">http://www.kitware.com/opensource/opensource.html</a><br>
<br>
Follow this link to subscribe/unsubscribe:<br>
<a href="http://www.vtk.org/mailman/listinfo/vtk-developers" target="_blank">http://www.vtk.org/mailman/listinfo/vtk-developers</a><br>
<br>
<br></blockquote></div><br><br clear="all"><div><br></div>-- <br></div></div><div class="im">Unpaid intern in BillsBasement at noware dot com<br>
</div></div></div>
<br>_______________________________________________<br>
Powered by <a href="http://www.kitware.com" target="_blank">www.kitware.com</a><br>
<br>
Visit other Kitware open-source projects at <a href="http://www.kitware.com/opensource/opensource.html" target="_blank">http://www.kitware.com/opensource/opensource.html</a><br>
<br>
Follow this link to subscribe/unsubscribe:<br>
<a href="http://www.vtk.org/mailman/listinfo/vtk-developers" target="_blank">http://www.vtk.org/mailman/listinfo/vtk-developers</a><br>
<br>
<br></blockquote></div><br><br clear="all"><div><br></div>-- <br>Robert Maynard
</div>