[Insight-developers] simplex mesh topological operators

Sun Aug 22 12:59:25 EDT 2010

We have generated meshes of the brain in the past using the tools available
in IA-FEMesh. It is likely that this could be automated using image
registration and the mapping the building blocks. While we generate
hexahedral elements, you can readily turn these into tets. In fact, the code
for this is in the Slicer 3 verion of IA-FEMesh, but is commented out. I can
provide more details if you are interested in pursuing this further.

An example figure is posted here
http://www.ccad.uiowa.edu/mimx/IA-FEMesh/

Vince

On 8/18/10 9:38 AM, "Michel Audette" <michel.audette at kitware.com> wrote:

> Hi Alex,
> 
> depends how much of the implementation that I have to do and what
> timeline you have in mind. I am on a tight schedule to produce
> neurosurgery simulation results by end of December (for a NIH year-end
> report on which year 2 funding hinges), which includes surface and tet
> meshing, and integration with Total Lagrangian Explicit Dynamics
> biomechanics, as well as get some haptic results with a 6 and 7 dof
> device that will be delivered shortly. This is on year 1 of a 2-year
> phase 1 budget. I would have more resources to allocate to this in
> year 2 of my phase 1, which will start in March next year, assuming
> the funding is renewed (but by then you are likely to have much of it
> implemented, I assume).
> 
> [As for the tetrahedralization, I have a good rapport with Nikos
> Chrisochoides, and in any event, I have some source by Alexander Fuchs
> that produces tets with very good edge length control that I can use.
> ]
> 
> Do you plan on getting a start right away, or do this over the course of V4?
> 
> Best wishes,
> 
> Michel
> 
> 
> On Wed, Aug 18, 2010 at 1:11 AM, Alexandre GOUAILLARD
> <agouaillard at gmail.com> wrote:
>> hi michel,
>> 
>> in the original article, we were speaking about replacing the simplex
>> implementation with QE as we wouldn't need the triangular2simplex and
>> simplex2triangular and half of the currently needed filters.
>> 
>> We never found motivation AND time to do it (we had either but not both :) )
>> 
>> If you were willing to join the effort, and if bill or luis would be
>> ok to kindly supervise/review our design along the way. I'm ok to do
>> it (all design and most implementation).
>> 
>> Here would be the proposed schedule:
>> 
>> = core modifications =
>> - implement a QE container and modify QE allocation / free mechanism (1~2
>> week)
>> - implement a Reserve function that reserves all the containers
>> (cells, edgecells, QE). Fix the current getContainer()->Reserve() bug
>> found by Michel A. (1 week)
>> - throw exception when non-2-manifold (2 days)
>> - handle non-2-manifold to 2-manifold in some specific cases (enough
>> to cover Dan M. filter) ( one week )
>> 
>> = Simplex Meshes =
>> - implement a simplex/triangular Mesh data structure ( 1~2 week )
>> - recode simplex mesh (with segmentation filters) ( 1~2 weeks )
>> - code 2 "functions" for T1 and T2 operators ( 1 week )
>> - code the final algorithm ( ? )
>> 
>> For tetrahedral meshing, you might want to involve vincent magnotta at
>> least. He is working on very similar topic for v4, and you might want
>> to tag along to be sure that eventually you'll be compatible. He is
>> mister 3-manifolds, I am mister 2-manifold :-)
>> 
>> what do you guys say?
>> 
>> alex.
>> 
>> 
>> 
>> On Wed, Aug 18, 2010 at 1:04 AM, Michel Audette
>> <michel.audette at kitware.com> wrote:
>>> Hi again,
>>> 
>>> It does have to work properly, otherwise, I could see the topology not
>>> being preserved, and introducing holes in the surface would make the
>>> subsequent tetrahedralization impossible. As to the time factor,
>>> depends how much time you mean. I can get by with my old code in the
>>> near term (a few weeks or even months), but it would be great to
>>> integrate everything under ITK ultimately.
>>> 
>>> Would you be adding to the Quad Edge Mesh, or to the Simplex Mesh?
>>> Because the balloon force, the image attraction force and the
>>> regularization of the simplex model are also important to this
>>> exercise.
>>> 
>>> If you endow ITK with something like that, it has tremendous
>>> implications for surface meshing, and ultimately tetrahedral meshing
>>> as well. Makes ITK extremely relevant to soft-tissue motion
>>> estimation, as is often needed in surgical guidance. IGSTK and SLICER
>>> would benefit greatly.
>>> 
>>> Cheers,
>>> 
>>> Michel
>>> 
>>> 
>>> 
>>> On Tue, Aug 17, 2010 at 12:56 PM, Alexandre GOUAILLARD
>>> <agouaillard at gmail.com> wrote:
>>>> yes, I think we have a shot.
>>>> let me get more familiar with those two operators, and we can come up
>>>> with a design quickly I think.
>>>> 
>>>> We do you actually ned it, do we have time to make it right, or do we
>>>> need to have something working quickly first and then try to make it
>>>> right?
>>>> 
>>>> alex.
>>>> 
>>>> 
>>>> On Wed, Aug 18, 2010 at 12:32 AM, Michel Audette
>>>> <michel.audette at kitware.com> wrote:
>>>>> Hi Alex,
>>>>> 
>>>>> the algorithm that I have in mind is my adaptation of Herve
>>>>> Delingette's simplex mesh, where I use T1 and T2 operators to delete
>>>>> specific edges in order to explicitly control surface mesh resolution
>>>>> (prior to controlled-resolution tetrahedralization).
>>>>> 
>>>>> The operators are on page 119 of Herve's IJCV paper General Object
>>>>> Reconstruction Based on Simplex Meshes
>>>>> which can still be found at
>>>>> http://www-sop.inria.fr/asclepios/biblio/REP/publi.php?name=Author/DELINGE
>>>>> TTE-H.html
>>>>> .
>>>>> 
>>>>> My adaptation appears in ICCV Workshop 2005...
>>>>> 
>>>>> Yanxi Liu, Tianzi Jiang, Changshui Zhang  (Eds.): Computer Vision for
>>>>> Biomedical Image Applications, First International Workshop, CVBIA
>>>>> 2005, Beijing, China, October 21, 2005, Proceedings. Lecture Notes in
>>>>> Computer Science 3765 Springer 2005, ISBN 3-540-29411-2
>>>>> 
>>>>> Michel A. Audette, Hervé Delingette, Alexander Fuchs, Oliver R.
>>>>> Astley, Kiyoyuki Chinzei:
>>>>> A Topologically Faithful, Tissue-Guided, Spatially Varying Meshing
>>>>> Strategy for Computing Patient-Specific Head Models for Endoscopic
>>>>> Pituitary Surgery Simulation. 178-188
>>>>> 
>>>>> (and later in Computer Aided Surgery...
>>>>> http://www.informaworld.com/smpp/content~db=all~content=a770815634~frm=abs
>>>>> link )
>>>>> 
>>>>> Was hoping to do this on ITK, without relying on my old code based on
>>>>> stuff contributed by Herve.
>>>>> 
>>>>> What do you think? Feasible?
>>>>> 
>>>>> Cheers,
>>>>> 
>>>>> Michel
>>>>> 
>>>>> On Tue, Aug 17, 2010 at 3:03 AM, Alexandre GOUAILLARD
>>>>> <agouaillard at gmail.com> wrote:
>>>>>> 
>>>>>> hi michel,
>>>>>> 
>>>>>> the simplex mesh code is one of the very first contribution to the
>>>>>> toolkit roughly 10 years ago and it seems to be showing it s age here
>>>>>> and then ( the segmentation based on simplex meshes in tk does not
>>>>>> take into account spacing, move the mesh out of the image and so on).
>>>>>> 
>>>>>> Note that simplex / triangular meshes being dual, both topologies are
>>>>>> included by default in a QuadEdgeMesh. THe only thing that could be
>>>>>> missing (depending on what you do) is the container for the geometry
>>>>>> of the dual mesh (depending on your point of view, each can be primal
>>>>>> or dual).
>>>>>> 
>>>>>> What algorithm did you have in mind ?
>>>>>> 
>>>>>> I'm re-motivating myself to work on QuadEdgeMesh (thanks to dan for
>>>>>> pointing out a nice algorithm I'd like to work on) and that could be
>>>>>> of interest to me too ;-) I could definitly help with the design, and
>>>>>> even implement some.
>>>>>> 
>>>>>> regards,
>>>>>> 
>>>>>> alex.
>>>>>> 
>>>>>> 
>>>>>> On Mon, Aug 16, 2010 at 9:51 PM, Michel Audette
>>>>>> <michel.audette at kitware.com> wrote:
>>>>>>> Dear fellow developers,
>>>>>>> 
>>>>>>> I would like to find out if anyone in the community has implemented T1
>>>>>>> and
>>>>>>> T2 topological operators for the simplex mesh model. I need this kind of
>>>>>>> operator to use the simplex for highly controlled decimation and high
>>>>>>> quality surface triangulation. I don't see it doing a google on simplex
>>>>>>> and
>>>>>>> Insight Journal.
>>>>>>> 
>>>>>>> Best wishes,
>>>>>>> 
>>>>>>> Michel
>>>>>>> 
>>>>>>> --
>>>>>>> Michel Audette, Ph.D.
>>>>>>> R & D Engineer,
>>>>>>> Kitware Inc.,
>>>>>>> Chapel Hill, N.C.
>>>>>>> 
>>>>>>> 
>>>>>>> _______________________________________________
>>>>>>> Powered by www.kitware.com
>>>>>>> 
>>>>>>> Visit other Kitware open-source projects at
>>>>>>> http://www.kitware.com/opensource/opensource.html
>>>>>>> 
>>>>>>> Kitware offers ITK Training Courses, for more information visit:
>>>>>>> http://kitware.com/products/protraining.html
>>>>>>> 
>>>>>>> Please keep messages on-topic and check the ITK FAQ at:
>>>>>>> http://www.itk.org/Wiki/ITK_FAQ
>>>>>>> 
>>>>>>> Follow this link to subscribe/unsubscribe:
>>>>>>> http://www.itk.org/mailman/listinfo/insight-developers
>>>>>>> 
>>>>>>> 
>>>>> 
>>>>> 
>>>>> 
>>>>> --
>>>>> Michel Audette, Ph.D.
>>>>> R & D Engineer,
>>>>> Kitware Inc.,
>>>>> Chapel Hill, N.C.
>>>>> 
>>>> 
>>> 
>>> 
>>> 
>>> --
>>> Michel Audette, Ph.D.
>>> R & D Engineer,
>>> Kitware Inc.,
>>> Chapel Hill, N.C.
>>> 
>> 
> 
> 

----------------------
Associate Professor
Department of Radiology
0453-D JCP
200 Hawkins Drive
Iowa City, IA 52242
E-mail: vincent-magnotta at uiowa.edu
Phone: 319-356-8255 Fax: 319-353-6275
Website: http://www.radiology.uiowa.edu