CGAL_triangulation_precondition vs. CGAL_triangulation_expensive_precondition

classic Classic list List threaded Threaded
17 messages Options
Reply | Threaded
Open this post in threaded view
|

CGAL_triangulation_precondition vs. CGAL_triangulation_expensive_precondition

Adam Getchell
Hello all,

I’m searching for documentation on these two functions to determine if I am using them correctly. What is the difference between them? (What makes a particular check expensive?)

I have code which does a (2,6) Pachner move that starts out as:

void move_26(Delaunay* const D3,
             Cell_handle one_three_simplex,
             unsigned neighbor_index,
             Cell_handle three_one_simplex) noexcept {
  // Preconditions
  CGAL_triangulation_precondition((dimension() == 3)
                                   && (0 <= neighbor_index)
                                   && (neighbor_index < 4));
  CGAL_triangulation_precondition(one_three_simplex.has_neighbor
                                  (three_one_simplex));
  CGAL_triangulation_expensive_precondition(is_cell(one_three_simplex,
                                                    three_one_simplex));

  // Get vertices of common face
  unsigned i1 = (neighbor_index + 1)&3;
  unsigned i2 = (neighbor_index + 2)&3;
  unsigned i3 = (neighbor_index + 3)&3;



Reply | Threaded
Open this post in threaded view
|

Re: CGAL_triangulation_precondition vs. CGAL_triangulation_expensive_precondition

BRYang
Hi, Adam, I use the delaunay triangulation package for triangulation, and I found out that the four vertices of computed cells would lie on the same plane, as the images(I render only the cells incident to one point). But According to my understanding of delaunay triangulation, such kind of triangulation would not be a right delaunay triangulation.

Here is my code:

//define DT as delaunay triangulation.
std::vector< Point> points; //restores the points of input mesh, saying a uniformly sampled cube
DT.insert(points.begin(),points.end());

Any idea about the problem? Thank you very much.

Monica
Reply | Threaded
Open this post in threaded view
|

Re: CGAL_triangulation_precondition vs. CGAL_triangulation_expensive_precondition

teillaud
Administrator
In reply to this post by Adam Getchell
Le 25/04/15 08:06, Adam Getchell a écrit :
> Hello all,
>
> I’m searching for documentation on these two functions to determine if I
> am using them correctly. What is the difference between them? (What
> makes a particular check expensive?)

Hi Adam,

Preconditions are documented in the developer manual, see
http://doc.cgal.org/latest/Manual/devman_checks.html

To schematize:
Preconditions are "expensive" for instance when they need to browse all
vertices (complexity O(n)) or all cells (complexity O(n^2)).
"Normal" preconditions are in general constant-time.

Best,
--
Monique Teillaud
http://www.loria.fr/~teillaud/
INRIA Nancy - Grand Est, LORIA
Institut National de Recherche en Informatique et Automatique

--
You are currently subscribed to cgal-discuss.
To unsubscribe or access the archives, go to
https://sympa.inria.fr/sympa/info/cgal-discuss


Reply | Threaded
Open this post in threaded view
|

Re: CGAL_triangulation_precondition vs. CGAL_triangulation_expensive_precondition

TableYoung
In reply to this post by BRYang
Hi brYang,
           How do you draw the cells ?  or like the code show below:
  Delaunay_triangulation::finite_face_iterator begin=DT.finite_facets_begin(),end=finite_facets_end();
        for(;begin!=end;++begin){
                Delaunay_triangulation::Cell_handle cell_handle=(*begin).first;
                int index=(*begin).second;
                int i=(index+1)&3,j=(index+2)&3,k=(index+3)&3;
                std::cout<<cell_handle->vertex(i)->point()<<","\
                            <<cell_handle->vertex(j)->point()<<","\
                            <<cell_handle->vertex(k)->point()<<std::endl;
                        }
Maybe the code draw triangulation data struct is incorrect, because Delaunay triangulation algorithm is stable,
try to find out is there some wrong with your code;
BR
TobeYang
Reply | Threaded
Open this post in threaded view
|

Re: CGAL_triangulation_precondition vs. CGAL_triangulation_expensive_precondition

BRYang
Hi TableYoung,
I use fci->vertex(i)->point() ,where i = 0,1,2,3 to access the four vertices of cells.
And for the cells incident to a vertex, I use :

//suppose dt is the delaunay triangulation
std::list<Cell_handle> cell_vector;
dt.incident_cells(vh, std::back_inserter(cell_vector));

to access all the incidental cells of vh

Then I draw all the line segments of each cell by connecting any two of the four vertices of it.

But it still shows as the image above.

Is there any other possibility for causing this situation?

Baorong Yang
Reply | Threaded
Open this post in threaded view
|

Re: CGAL_triangulation_precondition vs. CGAL_triangulation_expensive_precondition

Adam Getchell
In reply to this post by teillaud
Thanks Monique!

Adam Getchell
about.me/adamgetchell

> On Apr 27, 2015, at 7:24 AM, Monique Teillaud <[hidden email]> wrote:
>
> Le 25/04/15 08:06, Adam Getchell a écrit :
>> Hello all,
>>
>> I’m searching for documentation on these two functions to determine if I
>> am using them correctly. What is the difference between them? (What
>> makes a particular check expensive?)
>
> Hi Adam,
>
> Preconditions are documented in the developer manual, see
> http://doc.cgal.org/latest/Manual/devman_checks.html
>
> To schematize:
> Preconditions are "expensive" for instance when they need to browse all vertices (complexity O(n)) or all cells (complexity O(n^2)).
> "Normal" preconditions are in general constant-time.
>
> Best,
> --
> Monique Teillaud
> http://www.loria.fr/~teillaud/
> INRIA Nancy - Grand Est, LORIA
> Institut National de Recherche en Informatique et Automatique
>
> --
> You are currently subscribed to cgal-discuss.
> To unsubscribe or access the archives, go to
> https://sympa.inria.fr/sympa/info/cgal-discuss
>
>


--
You are currently subscribed to cgal-discuss.
To unsubscribe or access the archives, go to
https://sympa.inria.fr/sympa/info/cgal-discuss


Reply | Threaded
Open this post in threaded view
|

Re: CGAL_triangulation_precondition vs. CGAL_triangulation_expensive_precondition

TableYoung
In reply to this post by BRYang
Hi,
     could you give me your points coordinate, i run it on my machine, and drawing the result.
BR
 Tobe Yang
Reply | Threaded
Open this post in threaded view
|

Re: CGAL_triangulation_precondition vs. CGAL_triangulation_expensive_precondition

TableYoung
In reply to this post by BRYang
Hi brYang
          pictures below is my result use your points make triangulation.i find it's incorrect on surface .inside is all right.i don't know why this happened.

Reply | Threaded
Open this post in threaded view
|

Re: CGAL_triangulation_precondition vs. CGAL_triangulation_expensive_precondition

BRYang
Thank you, TableYoung. I got the same result as you. But I also have no idea why this happens..

Baorong Yang
Reply | Threaded
Open this post in threaded view
|

Re: CGAL_triangulation_precondition vs. CGAL_triangulation_expensive_precondition

TableYoung
Hi BrYang
            i seemed to know why this happened, i have tested a case that i used part of your points(about 2560 ) then i made delaunay triangulation,the picture show below that the last point locate on surface .According to the principle of Delaunay algorithm, the CGAL code is always working right. You may search about the Delaunay algorithm.

Best Regards
TobeYang  
Reply | Threaded
Open this post in threaded view
|

Re: CGAL_triangulation_precondition vs. CGAL_triangulation_expensive_precondition

BRYang
Hi, TobeYang,
I got what you mean. My concern is what does the "empty sphere property" of Delaunay Triangulation mean? If a point is on the surface of a tetrahedron(cell), does it still satisfy the property of DT?
Reply | Threaded
Open this post in threaded view
|

Re: CGAL_triangulation_precondition vs. CGAL_triangulation_expensive_precondition

BRYang
In reply to this post by TableYoung
Hi TobeYang,
 
As shown in the picture attached, the cells fci in blue are the cells(tetrahedrons) incident to the vertex(the vertex in peacock blue) and with their circumcenter outside the input mesh domain  and the cells in red are the cells incident to the same vertex and with their circumcenter inside the bounding box of input mesh or on the surface of input mesh.

It's clearly that there are some cells(in blue) voiding the "empty sphere" property. Do you have any idea about why this happens? Thanks,

Best regards,
Baorong Yang
Reply | Threaded
Open this post in threaded view
|

Re: CGAL_triangulation_precondition vs. CGAL_triangulation_expensive_precondition

TableYoung
Hi brYang
         I think all this happened because of there are some degenerate tetrahedrons appeared.
four vertices of a tetrahedron are lie on a plane( in mesh generation ,it like silver), circumcircle is a circle not a sphere. above is my personal opinion, maybe it's incorrect.

BR
TobeYang
Reply | Threaded
Open this post in threaded view
|

Re: CGAL_triangulation_precondition vs. CGAL_triangulation_expensive_precondition

BRYang
yes, I check the mininum dihedral angle of each cell and it seems that there are so many slivers generated from delaunay triangulation, it could be the limitation of DT. Any way, thank you so much for your patience.

Best regards,
Baorong Yang
Reply | Threaded
Open this post in threaded view
|

Re: CGAL_triangulation_precondition vs. CGAL_triangulation_expensive_precondition

BRYang
In reply to this post by TableYoung
Hi TobeYang, another question about CGAL.. Do you know how to access the edge handle of edges of a facet, saying Facet fi , which is also a facet of a cell of DT.

Thanks,
Baorong Yang
Reply | Threaded
Open this post in threaded view
|

Re: CGAL_triangulation_precondition vs.CGAL_triangulation_expensive_precondition

TableYoung
In reply to this post by BRYang
hi,
  i don't know what you want to do ,but  i think you can try 3d mesh generation ,if you want get surface mesh , you can try to use
Surface mesh generation algorithm. 

------------------ Original ------------------
From:  "ybr";<[hidden email]>;
Date:  Thu, Apr 30, 2015 08:48 AM
To:  "cgal-discuss"<[hidden email]>;
Subject:  Re: [cgal-discuss] CGAL_triangulation_precondition vs.CGAL_triangulation_expensive_precondition

yes, I check the mininum dihedral angle of each cell and it seems that there
are so many slivers generated from delaunay triangulation, it could be the
limitation of DT. Any way, thank you so much for your patience.

Best regards,
Baorong Yang



--
View this message in context: http://cgal-discuss.949826.n4.nabble.com/CGAL-triangulation-precondition-vs-CGAL-triangulation-expensive-precondition-tp4660727p4660772.html
Sent from the cgal-discuss mailing list archive at Nabble.com.

--
You are currently subscribed to cgal-discuss.
To unsubscribe or access the archives, go to
https://sympa.inria.fr/sympa/info/cgal-discuss

Reply | Threaded
Open this post in threaded view
|

Re: CGAL_triangulation_precondition vs.CGAL_triangulation_expensive_precondition

BRYang
okay,  I will try to figure it out from the user manual.  Thanks.