[vtk-developers] Extending the ordered triangulator for templates for octants from an octree

[Bryn Lloyd]

Hi

 

I am trying to work out how I could modify/extend the vtkOrderedTriangulator
to cells with more than 8 nodes.

 

Currently the triangulator will only build templates for cells with a max.
of 8 nodes (vtkHexahedron). However, I would like to use the template option
also for octants from a balanced octree.

In this case each octant can have at most one point per edge of the cube,
making a total of max. 8+12 points.

 

I identified some things I would need to modify/implement:

 

1.       The template id currently can only deal with 8 points max. I need
to extend the id to deal with up to 20 points.

2.       I would need to create e.g. a lookup table for each octant case, to
assign a unique CellType identifier for the triangulator to store the
template. Since there are 12 edges, this would consist of 2^12 = 4096 cases.
I could reduce the number by defining transforms (indirection tables) to
some reference case. Storing these transforms in memory might be expensive.
Computing them on the fly might not be much faster than computing the
Delaunay triangulation.

 

Does this sound correct? 

What speed-up can I expect from using templates? According to the paper
("Compatible triangulations of Spatial Decompositions"), using templates
might speed-up triangulation by a factor of 5-10. However, if there are more
cases due to an increase in the number of nodes from 8 to 20, this might
deteriorate the speed-up. How does the Delaunay algorithm scale with number
of points?

What are your thoughts on this?

 

Thanks a lot!

Bryn

-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://public.kitware.com/pipermail/vtk-developers/attachments/20111114/18d277d7/attachment.html>