[Insight-developers] Making cuberille polygonization work with QuadEdgeMesh

[Alexandre GOUAILLARD]

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
>