[Insight-developers] Making cuberille polygonization work with QuadEdgeMesh

[Alexandre GOUAILLARD]

Here is the full explication:

all the faces and edges that use a point are in the 0-ring of this
point. For a surface, the 0-ring can be seen as a linked list of edges
with respect for the orientation of the surface, each edge having a
link to the face on its left. if some faces are missing, it's fine, as
you still have a linked list of edges.

R +----+ S
    |     | U
T +----+----+V
         |      |
    W +----+ X

let's take the point U. If it is a QuadEdgeMeshPoint, it has the
coordinate and a pointer to a geometricalQuadEdge (that allows for
example duplication of all points, to answer your question, but would
not make sense as you would have a separated component for each face.
VIsually it would be ok, but computationally you wouldn't have 1
surface anymore).

let's say that the entry edge is UV (arbitrary). let's suppose that
the normal are consistent and oriented toward the viewer.
the list is:
US -> face on the left
UT -> empty on the left
UW -> face on the left
UV -> empty on the left
Locally, you can make the list, so it's a two manifold, so you're good.

In this specific case, actually, you could still have inconsistent
normals, the link would be different, but as there is a space between
all faces, it's ok. You would have a problem with orientation when/if
you add the connecting faces.

now suppose two copies of the following surface:

      _C
   _/ / |
  /  /   |
A------B
|  /  _/
| |  /
| | /
 D

and make them share the vertex A. Locally, around A, you can not
define a 0-ring with respect for orientation. This is not 2-manifold.

alex.




On Sun, Jul 25, 2010 at 9:48 PM, Dan Mueller <dan.muel at gmail.com> wrote:
>> Note. If this is just quads this is still ok. If those are Cubes touching by one vertex then it is not ok.
>
> Ah. Thanks for the clarification. There needs to be a shared edge, not
> just a shared vertex.
>
> On 25 July 2010 15:46, 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...?
>>
>>
>> Note. If this is just quads this is still ok. If those are Cubes touching by one vertex then it is not ok.
>>
>>
>>>
>>>> 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
>>
>