CGAL users discussion list

[Michel Audette <>]

Hi Andreas,

playing around with the debugger and the perturbation, as well as high-verbosity flag, I'm finding that build_prior_queue returns a null pqueue_size in Sliver_perturber.h, and the while loop at line 484 never executes, so nothing gets perturbed...

The output looks like this...

./mesh_two_implicit_spheres_with_balls

Inserting protection balls...
insert_corners() done. Nb of points in triangulation: 0
insert_balls_on_edges() done. Nb of points in triangulation: 13
D vertices.size() 0
refine_balls() done. Nb of points in triangulation: 13

construct initial points:
12/12 initial point(s) found...

Start surface scan...end scan. [Bad facets:35]

Refining Surface...
Legende of the following line: (#vertices,#steps,#facets to refine,#tets to refine)

(121,95,0,0) (791.7 vertices/s))
Total refining surface time: 0.12s

Start volume scan...end scan. [Bad tets:300]

Refining...
Legende of the following line: (#vertices,#steps,#facets to refine,#tets to refine)

(202,92,0,0) (1533.3 vertices/s)))

Total refining volume time: 0.06s

Total refining time: 0.19s

Fill sizing field...done (0.02s)
Running Odt-smoothing...
end interation 13 (82.2 frozen), 36 / 202 (4), last step:0.02s, step avg:0.14s, avg large move:0.061            
Convergence reached
Total optimization time: 1.96s

Running sliver perturbation...
Perturb sliver vertices (bound: 1) ...
Build pqueue...done (0 vertices inserted in 0.01s)

Legend of the following line: (#vertices in pqueue, #iterations, #fails)

No perturbation done at this step
Step perturbation time: 0.01s

Perturb sliver vertices (bound: 2) ...
Build pqueue...done (0 vertices inserted in 0s)

Legend of the following line: (#vertices in pqueue, #iterations, #fails)

No perturbation done at this step
Step perturbation time: 0s

(and so on, 0 vertices throughout, you get the picture...)

Perturb sliver vertices (bound: 8) ...
Build pqueue...done (0 vertices inserted in 0.01s)

Legend of the following line: (#vertices in pqueue, #iterations, #fails)

No perturbation done at this step
Step perturbation time: 0.01s

Perturb sliver vertices (bound: 9) ...
Build pqueue...done (4 vertices inserted in 0s)

Legend of the following line: (#vertices in pqueue, #iterations, #fails)

(0,1,0) (inf iteration/s)

Sq radius gradient perturbation: 100% (1 in 0s)
Volume gradient perturbation: 0% (0 in 0s)
Dihedral angle gradient perturbation: 0% (0 in 0s)
Li random perturbation [100, 0.15, in]: 0% (0 in 0s)

Step perturbation time: 0s

Perturb sliver vertices (bound: 10) ...
Build pqueue...done (4 vertices inserted in 0.01s)

Legend of the following line: (#vertices in pqueue, #iterations, #fails)

(0,2,0) (200.0 iteration/s)
Sq radius gradient perturbation: 100% (1 in 0.01s)

Volume gradient perturbation: 0% (0 in 0s)
Dihedral angle gradient perturbation: 0% (0 in 0s)
Li random perturbation [100, 0.15, in]: 0% (0 in 0s)

Step perturbation time: 0.02s


Total perturbation time: 0.06s
Perturbation statistics:
Sq radius gradient perturbation: 100% (2 in 0.01s)

Volume gradient perturbation: 0% (0 in 0s)
Dihedral angle gradient perturbation: 0% (0 in 0s)
Li random perturbation [100, 0.15, in]: 0% (0 in 0s)

Exuding...
Legend of the following line: (#cells left,#vertices pumped,#vertices ignored)

(0,2,1) (inf vertices/s)
Total exuding time: 0s

Once again, this is the modification to the mesh_two_implicit_spheres... code:

 Mesh_criteria criteria(edge_size = 0.5,
                        facet_angle = 25, facet_size = 0.5,
                        cell_radius_edge_ratio = 2, cell_size = 0.5);
 

 // Create edge that we want to preserve
 Polylines polylines (1);
 Polyline& polyline = polylines.front();
...
 // Mesh generation with feature preservation

 c3t3 = CGAL::make_mesh_3<C3t3>(domain, criteria, //);
                                     odt(time_limit=30),
                                     perturb(sliver_bound=10, time_limit=30),
                                     exude(time_limit=30, sliver_bound=15));

#ifndef VTKOUTPUT 
  std::ofstream medit_file("out-with-protection.mesh");
  //medit_file.open("out-with-protection.mesh");
  c3t3.output_to_medit(medit_file);
  medit_file.close();
#else 

  vtkSmartPointer<vtkUnstructuredGrid>
    outputUnstructuredGrid = vtkSmartPointer<vtkUnstructuredGrid>::New();

  CGAL::output_c3t3_to_vtk_unstructured_grid(c3t3, outputUnstructuredGrid);
  outputUnstructuredGrid->Squeeze();
 
  vtkSmartPointer<vtkUnstructuredGridWriter> writer =
    vtkSmartPointer<vtkUnstructuredGridWriter>::New();

  writer->SetInput(outputUnstructuredGrid);
  writer->SetFileName("out.vtk");
  writer->Write();

#endif

I'm also playing around with Stellar 1.0 (based on a meshconvert from .mesh to .node, when outputting in non-VTK mode), in the hopes of using it to improve the mesh, and I'm getting an odd summary of the input mesh... There do not appear to be any slivers in these results, according to Stellar. See below...

I don't know what to make of it, except that what I'm seeing in Paraview either

• indicates that the .vtk file does not reflect the results of the .mesh file, or
  
• Paraview and the vtk file are right on, but some of these tets overlap. 

Thoughts? Best wishes,

Michel

PS:
Stellar 1.0 summary of input
Mesh quality before improvement:
Mesh quality statistics (PHYSICAL SPACE)

  Smallest volume:      0.0090213   |  Largest volume:       0.050776
  Shortest edge:          0.36031   |  Longest edge:           1.0143
  Shortest altitude:      0.15979   |  Largest aspect ratio:   5.1695

  Tetrahedron aspect ratio histogram:
  1.2247 - 1.5       :         25   |     15 - 25         :         0
     1.5 - 2         :        394   |     25 - 50         :         0
       2 - 2.5       :        261   |     50 - 100        :         0
     2.5 - 3         :         46   |    100 - 300        :         0
       3 - 4         :         17   |    300 - 1000       :         0
       4 - 6         :          4   |   1000 - 10000      :         0
       6 - 10        :          0   |  10000 - 100000     :         0
      10 - 15        :          0   | 100000 -            :         0
  (Aspect ratio is longest edge divided by shortest altitude)

  Largest circumradius-to-shortest-edge ratio:                 1.1286

  Tetrahedron circumradius-to-shortest-edge ratio histogram:
  0.6123 - 0.75      :        190   |     15 - 25         :         0
    0.75 - 1         :        520   |     25 - 50         :         0
       1 - 1.5       :         37   |     50 - 100        :         0
     1.5 - 2         :          0   |    100 - 300        :         0
       2 - 3         :          0   |    300 - 1000       :         0
       3 - 5         :          0   |   1000 - 10000      :         0
       5 - 10        :          0   |  10000 - 100000     :         0
      10 - 15        :          0   | 100000 -            :         0

  Smallest dihedral:       16.404   |  Largest dihedral:       156.44

  Dihedral angle histogram:
       0 - 10 degrees:          0   |     90 - 100 degrees:       316
      10 - 20 degrees:          8   |    100 - 110 degrees:       268
      20 - 30 degrees:         45   |    110 - 120 degrees:       142
      30 - 40 degrees:        242   |    120 - 130 degrees:        54
      40 - 50 degrees:        588   |    130 - 140 degrees:        33
      50 - 60 degrees:        861   |    140 - 150 degrees:        10
      60 - 70 degrees:        775   |    150 - 160 degrees:         3
      70 - 80 degrees:        615   |    160 - 170 degrees:         0
      80 - 90 degrees:        522   |    170 - 180 degrees:         0

  For a histogram, input the following line to hist.c:
  0 0 0 0 0 0 0 0 3 5 6 5 7 10 17 30 36 52 57 67 81 103 118 135 151 146 170 167 196 182 189 165 138 155 128 135 135 123 111 111 115 119 106 91 91 74 69 62 56 55 56 47 54 60 51 48 25 26 23 20 13 11 11 9 10 7 11 4 8 3 3 3 1 3 0 1 0 1 1 0 0 0 0 0 0 0 0 0 0 0     16.40352     156.4417

  For a rnrrratio histogram, input the following line to hist.c:
  0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 1 0 0 1 0 0 1 2 0 0 0 0 1 2 0 0 1 1 3 3 2 1 2 1 2 3 4 4 3 5 2 3 4 6 11 8 10 10 15 16 15 9 17 19 24 25 24 28 28 33 33 35 29 27 31 39 35 28 29 37 20 23 14 11 5 0    0.2966215    0.9854242

  For a vlrms3ratio histogram, input the following line to hist.c:
  0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 3 0 1 0 1 0 0 1 1 1 0 2 1 1 2 2 2 1 1 3 3 0 6 4 3 3 7 6 9 3 4 8 12 9 13 17 11 16 7 18 13 16 19 28 18 16 22 29 24 32 36 18 24 27 26 23 25 30 28 23 23 24 11 9 13 6 1 0    0.2724383     0.981271

worstqual:    0.2824005

The worst input angle is 2.67587 radians (153.316 degrees).
Performing vertex classification.
Computing intial surface quadrics
Quadriccheck:
    Average quadric error: -2.62828e-16
    Number non-zero:       98
    Minimum quadric error: -1.42109e-14
    Maximum quadric error: 1.06581e-14
    Average gradient mag:  1.38175e-15
    Minimum gradient mag:  0
    Maximum gradient mag:  1.07043e-14
    Average dot mag:       1.07678
    Minimum dot mag:       0.522799
    Maximum dot mag:       1.69926
Edge length statistics:
    Longest edge:          1.01426
    Longest desired edge:  0.75
    Shortest edge:         0.360311
    Shortest desired edge: 0.4
    Mean edge:             0.664016
    Median edge:           0.661525
    Ideal edge:            0.5


The VTK output is visualized with slice through the volume in

On Mon, Jun 20, 2011 at 4:57 PM, Michel Audette <> wrote:
> Hi Andreas,
>
> it does not look very different with . The post-processing is being
> triggered, but looks like it might not be well tuned. I'm including the
> readout in verbose mode below...
>
> I'm open to tuning it further, if there is something that I'm not doing
> right. If I didn't know better, some of these look like thin hexes, or at
> least the slice-intersection looks like thin quads, for some shapes, but
> every cell is indeed 4 points, from what I can tell. I'm going to poke
> around with high verbosity.
>
> Cheers,
>
> Michel
>
> michel@michel-desktop:~/simProject/NeuroSurgSim/SimplexDecimationBuild/bin$
> !./me
> ./mesh_two_implicit_spheres_with_balls
> Inserting protection balls...
> insert_corners() done. Nb of points in triangulation: 0
> insert_balls_on_edges() done. Nb of points in triangulation: 13
>  D vertices.size() 0
> refine_balls() done. Nb of points in triangulation: 13
>
> construct initial points:
> 12/12 initial point(s) found...
> Start surface scan...end scan. [Bad facets:32]
>
> Refining Surface...
> Legende of the following line: (#vertices,#steps,#facets to refine,#tets to
> refine)
> (129,106,0,0) (706.7 vertices/s)
> Total refining surface time: 0.15s
>
> Start volume scan...end scan. [Bad tets:299]
>
> Refining...
> Legende of the following line: (#vertices,#steps,#facets to refine,#tets to
> refine)
> (207,87,0,0) (1450.0 vertices/s)))
> Total refining volume time: 0.06s
> Total refining time: 0.22s
>
> Fill sizing field...done (0.03s)
> Running Odt-smoothing...
> end interation 12 (77.8 frozen), 46 / 207 (5), last step:0.03s, step
> avg:0.16s, avg large move:0.078          
> Convergence reached
> Total optimization time: 2.1s
>
> Running sliver perturbation...
> Legend of the following line: (#vertices in pqueue, #iterations, #fails)
> bound 9: (0,1,0) (25.0 iteration/s)
> Total perturbation time: 0.05s
> Perturbation statistics:
> Sq radius gradient perturbation: 100% (1 in 0s)
> Volume gradient perturbation: 0% (0 in 0s)
> Dihedral angle gradient perturbation: 0% (0 in 0s)
> Li random perturbation [100, 0.15, in]: 0% (0 in 0s)
>
> Exuding...
> Legend of the following line: (#cells left,#vertices pumped,#vertices
> ignored)
> (0,5,10) (500.0 vertices/s)
> Total exuding time: 0.02s
>
>
>
>
>
> On Mon, Jun 20, 2011 at 3:42 PM, Michel Audette <>
> wrote:
>>
>> Hi Andreas,
>>
>> thanks for your prompt reply, and I apologize if the email just sent is
>> also covered by this workaround.
>>
>> I'll give it a try and report back.
>>
>> Best wishes,
>>
>> Michel
>>
>> On Mon, Jun 20, 2011 at 3:35 PM, Andreas Fabri
>> <> wrote:
>>>
>>> Hi Michel,
>>>
>>> Some days ago we found a bug in the code that removes slivers.
>>> The workaround is to define the macro
>>> CGAL_MESH_3_USE_RELAXED_HEAP
>>>
>>> Can you report back if it helped in your case.
>>>
>>> andreas
>>>
>>>
>>> On 20/06/2011 20:58, Michel Audette wrote:
>>>>
>>>> Dear CGAL developers,
>>>>
>>>> In the past week or so, I've become interested in the new capacity of
>>>> 3.8 to offer boundary-faithful and controlled-resolution
>>>> tetrahedralization.
>>>>
>>>> Returning to the example in
>>>>
>>>> examples/Mesh_3/mesh_two_implicit_spheres_with_balls.cpp,
>>>> playing with the mesh size a little bit,
>>>>
>>>>  Mesh_criteria criteria(edge_size = 0.5,
>>>>                         facet_angle = 25, facet_size = 0.5,
>>>>                         cell_radius_edge_ratio = 2, cell_size = 0.5);
>>>>
>>>>
>>>>   c3t3 = CGAL::make_mesh_3<C3t3>(domain, criteria,
>>>>                                       odt(time_limit=30),
>>>>                                       perturb(sliver_bound=10,
>>>> time_limit=30),
>>>>                                       exude(time_limit=30,
>>>> sliver_bound=15));
>>>>
>>>> and visualizing the interior with Paraview (by producing a vtk file),
>>>>   vtkSmartPointer<vtkUnstructuredGrid>
>>>>     outputUnstructuredGrid =
>>>> vtkSmartPointer<vtkUnstructuredGrid>::New();
>>>>
>>>>   CGAL::output_c3t3_to_vtk_unstructured_grid(c3t3,
>>>> outputUnstructuredGrid);
>>>>   outputUnstructuredGrid->Squeeze();
>>>>
>>>>   vtkSmartPointer<vtkUnstructuredGridWriter> writer =
>>>>     vtkSmartPointer<vtkUnstructuredGridWriter>::New();
>>>>
>>>>   writer->SetInput(outputUnstructuredGrid);
>>>>   writer->SetFileName("out.vtk");
>>>>   writer->Write();
>>>>
>>>> I'm finding nonetheless that some slivers remain in the peanut... See
>>>> the enclosed visualization. I'd be happy to help track down the problem.
>>>> Is this a parameter of odt(), perturb() or exude() that I am not using
>>>> properly?
>>>>
>>>> Best wishes,
>>>>
>>>> Michel
>>>>
>>>>
>>>> --
>>>> Michel Audette, Ph.D.
>>>> R & D Engineer,
>>>> Kitware Inc.,
>>>> Chapel Hill, N.C.
>>>>
>>>
>>>
>>> --
>>> Andreas Fabri, PhD
>>> Chief Officer, GeometryFactory
>>> Editor, The CGAL Project
>>>
>>> phone: +33.492.954.912    skype: andreas.fabri
>>>
>>> --
>>> You are currently subscribed to cgal-discuss.
>>> To unsubscribe or access the archives, go to
>>> https://lists-sop.inria.fr/wws/info/cgal-discuss
>>>
>>
>>
>>
>> --
>> 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.
>
>

--

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.

Attachment: out.vtk
Description: Binary data

Attachment: out-with-protection.mesh
Description: Mesh model

Attachment: outputStellar
Description: Binary data