[Insight-developers] Fwd: Making cuberille polygonization work with QuadEdgeMesh

[Dan Mueller]

This time cc'd to developer list...

---------- Forwarded message ----------
From: Dan Mueller <dan.muel at gmail.com>
Date: 25 July 2010 15:18
Subject: Re: [Insight-developers] Making cuberille polygonization work
with QuadEdgeMesh
To: Alexandre GOUAILLARD <agouaillard at gmail.com>


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...?

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

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