[Insight-developers] Making cuberille polygonization work with QuadEdgeMesh

[Dan Mueller]

See inline below.

On 25 July 2010 15:44, Alex Gouaillard <agouaillard at gmail.com> wrote:
>
>
> Sent from my iPhone
>
> On Jul 25, 2010, at 21:18, Dan Mueller <dan.muel at gmail.com> wrote:
>
>> Hi Alex,
>>
>> Thanks for your investigation. Indeed, there is more than just one
>> test failing when QEMesh is enabled, blob2 is just the simplest
>> example.
>>
>> So, if I understand correctly, the way of solving the issue is to
>> detect situations which will cause a non-2-manifold mesh, and
>> duplicate the vertices at these locations? For example:
>>
>> R +----+ S
>>     |     | U
>> T +----+----+V
>>          |      |
>>     W +----+ X
>>
>> The vertex U is shared between the quadrilateral faces RSUT and UVXW.
>> If the vertex U were actually two points (U1, U2), the issue would be
>> resolved...?
>>
>
>
> Yes.
>
>
>
>>> In a QE Mesh, those points are not duplicated, as the QEPoint as an
>>> extra attribute (on top of the coordinates) which is a link to a
>>> QEGeom (the entry into the ORing) so you're good.
>> Can you please explain this further? I don't quite understand what you
>> are meaning...
>>
>
>
> We can skip that detail for now:-) an old story with bill lorensen about point types and hash tables.

I was just curious: what if I were to duplicate *all* points
(regardless of condition), does QEMesh prevent duplication?

>
>
>> Cheers, Dan
>>
>> On 25 July 2010 14:16, Alexandre GOUAILLARD <agouaillard at gmail.com> wrote:
>>> hi dan,
>>>
>>> I could reproduce the errors. I have a few more failing tests, but it
>>> looks like I have more tests all together (19):
>>> The following tests FAILED:
>>>          3 - Cuberille_Blob2_01 (Failed)
>>>          4 - Cuberille_Blob3_01 (Failed)
>>>          6 - Cuberille_MarschnerLobb_01 (Failed)
>>>         11 - Cuberille_Neghip_01 (Failed)
>>>         12 - Cuberille_Neghip_02 (Failed)
>>>         13 - Cuberille_Neghip_03 (Failed)
>>> Errors while running CTest
>>>
>>> <the why>
>>>
>>> When building a mesh, you eventually always end up calling
>>> InsertAfterNextBorderEdgeWithUnsetLeft() method, which in turn call
>>> GetNextBorderEdgeWithUnsetLeft() to get a pointer to the right
>>> position where the candidate Edge should be "graft".
>>>
>>> In terms of structure, GetNextBorderEdgeWithUnsetLeft() in the
>>> GeometricalQuadEdge mesh is where the core of the construction
>>> happens. You can take a look at the 50 lines or so comments with ascii
>>> art to get an idea. when fed with a triangle, at one point, it looks
>>> around the points to see if there is space to insert one more edge. If
>>> the Oring of the point is full, e.g., if it is already a surface
>>> locally, it will send you the "internal point" error.
>>>
>>> Then you go back to InsertAfterNextBorderEdgeWithUnsetLeft() with
>>> throws the "face is yet surrounded by faces" which, translated from
>>> our poor frenglish, means: "You cannot insert anymore face around this
>>> point. You are possibly trying to import a non 2-manifold mesh" ^____^
>>>
>>> <how to fix it>
>>>
>>> now, the case wanlin gave you is one example. Indeed everywhere the
>>> surface folds and come in contact you will have this problem. The
>>> solution is simple in itself, you duplicate the point in the middle.
>>> let me take wanling example:
>>>
>>> AB
>>> CD
>>>
>>> gives you a cross with a point in the middle. Put two points, one will
>>> belong to the isosurface going around A, the other one going around D.
>>> In a QE Mesh, those points are not duplicated, as the QEPoint as an
>>> extra attribute (on top of the coordinates) which is a link to a
>>> QEGeom (the entry into the ORing) so you're good.
>>>
>>> <the what s problem?>
>>>
>>> Now, the solution is easy, but to catch the cases where you need it
>>> might not be. I always wanted to throw an exception there which would
>>> allow to catch non manifold cases and let the user try to make
>>> something smart only when needed. To be honest, I was not good with
>>> exception at that time ( 2001) and did know better. Maybe now would be
>>> a good time.
>>>
>>> I m going to investigate a little bit more your code to see if I can
>>> propose something better.
>>>
>>> alex.
>>>
>>>
>>>
>>> On Sat, Jul 24, 2010 at 10:23 PM, Dan Mueller <dan.muel at gmail.com> wrote:
>>>> Hi Wanlin,
>>>>
>>>> I can confirm that the case you present is the issue. I have updated
>>>> the source on the IJ to include a minimal dataset (Data/blob2.mha)
>>>> which fails for QuadEdgeMesh.
>>>>
>>>> While the/an issue has been identified, I'm still not sure how to
>>>> solve it. Any ideas welcome!
>>>>
>>>> Cheers, Dan
>>>>
>>>> On 23 July 2010 16:06, wanlin <wanlinzhu at gmail.com> wrote:
>>>>> Hi, dan
>>>>>     Is there possible such a case, for voxels
>>>>>
>>>>>     AB
>>>>>     CD
>>>>>
>>>>> Intensity values at locations A and D are larger than isosurfacevalue,
>>>>> intensity values at location B and C are smaller than isosurfacevalue. hence
>>>>> faces AB and AC, faces CD and BD are faces have isosuface, which will lead
>>>>> to the mesh not a 2-manifolds. The errors might come from when adding faces
>>>>> AB and AC, the edge between A and D (it is the common edge between A,B,C,D)
>>>>> has been set with both left and right faces. When adding face BD or face CD,
>>>>> errors occurred.
>>>>>
>>>>>
>>>>> wanlin
>