CGAL users discussion list

["Sebastien Loriot (GeometryFactory)" <>]

On 04/10/2012 12:28 PM, Oleg wrote:
> Wednesday, April 4, 2012, 13:16, you wrote:
>
>  > On 04/03/2012 03:02 PM, Oleg wrote:
>  >> Thanks, Sebastien! It works. The only problem is that it's very slow
>  >> and the intersection boundary triangulation is a bit chaotic. What
>  >> would be the best way to check if a point or triangle lies inside a
>  >> polyhedron? Since I've already made the procedure to find two surfaces
>  >> intersection, I'd like to try to make a faster code for two
>  >> polyhedrons union and a better boundary triangulation.
>  >>
>  > What do you compute exactly as surface intersection? A list of segments?
>  > Is yes, then for each pair of intersecting triangles, an orientation
>  > test around the intersection segment is the only thing you need.
>
> Yes, a list of segments. Could you specify a little bit more what you
> mean by the orientation test? Do you mean detecting if a vertex is on
> the negative or positive side of the other triangle? I guess, it would
> help to exclude the vertices of the intersecting triangles that fall
> inside the polyhedrons, but not sure how it can help me to exclude the
> other triangles. I can try the method with random rays though, which
> Laurent Rineau recommended here:
> http://cgal-discuss.949826.n4.nabble.com/Determine-if-a-point-is-interior-or-exterior-to-a-Polyhedron-3-td4466730.html
>
>  > What is your ultimate goal?
>  > If you want to have a faster but less robust union function for two
>  > polyhedra, we'll probably release such an algorithm in the next release.
>  > You can also have a look at the source code of mepp which has a similar
>  > algorithm.
>
> My ultimate goal is building a uniform mesh for a union of different
> shapes, like spheres, cylinders, cones, and adapting it in the process
> of the body deformation. Robustness is important. The main problem for
> now is that the default mesh I obtain for different shapes union in
> CGAL is not uniform enough near the intersection boundary. Is there
> any way to control how CGAL places points on the intersection
> boundary? There are too many of them. I've tried MEPP, and it makes a
> similar mesh with too many points on the boundary placed in a manner
> that looks a bit chaotic. Although, it is definitely faster.

You can then use CGAL to remesh it, keeping the intersection polylines 
as features.

Sebastien.

> Oleg
>
>  >> Monday, April 2, 2012, 14:05, you wrote:
>  >>
>  >> > Since you are using Nef, what about computing the union of the two
>  >> > spheres and then extract the boundary?
>  >>
>  >> > N1+=N2;
>  >> > Polyhedron result;
>  >> > N1.convert_to_polyhedron(result);
>  >>
>  >> > see:
>  >> >
>  >>
> http://www.cgal.org/Manual/latest/doc_html/cgal_manual/Nef_3_ref/Class_Nef_polyhedron_3.html
>  >>
>  >> > Sebastien.
>  >>
>  >>
>  >> > On 04/01/2012 04:13 PM, Oleg wrote:
>  >> >> Hi all!
>  >> >>
>  >> >> Newbie question. I have two triangulated intersecting spheres (3D
>  >> >> polyhedrons) and want to exclude the triangles from each sphere
>  >> surface that
>  >> >> are inside the other sphere. What would be the easiest way to do
>  >> that? Here
>  >> >> is what I'm trying and so far it doesn't work (skipping the
> unnecessary
>  >> >> code):
>  >> >>
>  >> >> #include<CGAL/Exact_predicates_exact_constructions_kernel.h>
>  >> >> #include<CGAL/Polyhedron_3.h>
>  >> >> #include<CGAL/Nef_polyhedron_3.h>
>  >> >>
>  >> >> typedef CGAL::Exact_predicates_exact_constructions_kernel Kernel;
>  >> >> typedef Kernel::Triangle_3 Triangle;
>  >> >> typedef CGAL::Polyhedron_3<Kernel> Polyhedron;
>  >> >> typedef Polyhedron::Facet_const_iterator Facet_const_iterator;
>  >> >> typedef Nef_polyhedron::Volume_const_handle Volume_const_handle;
>  >> >>
>  >> >> std::vector<Triangle> triangles;
>  >> >>
>  >> >> //The spheres are represented by two 3D polyhedrons:
>  >> >>
>  >> >> Polyhedron P1;
>  >> >> Polyhedron P2;
>  >> >> Volume_const_handle v;
>  >> >>
>  >> >> //I convert each polyhedron to a nef_polyhedron:
>  >> >>
>  >> >> Nef_polyhedron N1(P1);
>  >> >> Nef_polyhedron N2(P2);
>  >> >>
>  >> >> //and check if a vertex from P1 belongs to N2:
>  >> >>
>  >> >> for ( Facet_const_iterator i = P1.facets_begin(); i !=
> P1.facets_end();
>  >> >> ++i){
>  >> >> if (!assign(v, N2.locate(i->halfedge()->vertex()->point()))&&
>  >> >> !assign(v, N2.locate(i->halfedge()->next()->vertex()->point()))&&
>  >> >> !assign(v,
>  >> >> N2.locate(i->halfedge()->next()->next()->vertex()->point()))) {
>  >> >> Triangle t(i->halfedge()->vertex()->point(),
>  >> >> i->halfedge()->next()->vertex()->point(),
>  >> >> i->halfedge()->next()->next()->vertex()->point());
>  >> >> triangles.push_back(t);
>  >> >> }
>  >> >> }
>  >> >> //Same for P2
>  >> >>
>  >> >> The goal is to have vector 'triangles' with those triangles from
> each
>  >> >> surface that are not inside the other sphere. So far it compiles,
>  >> but I get
>  >> >> empy vector in the output. What do I miss here? Or is there an
>  >> easier way to
>  >> >> achieve the same goal? Thanks for any help.
>  >> >>
>  >> >>
>  >> >> --
>  >> >> View this message in context:
>  >>
> http://cgal-discuss.949826.n4.nabble.com/Determining-if-a-point-is-inside-a-polyhedron-tp4523460p4523460.html
>  >> >> Sent from the cgal-discuss mailing list archive at Nabble.com.
>  >>
>  >>
>  >>
>  >>
> ------------------------------------------------------------------------
>  >> View this message in context: Re[2]: Determining if a point is inside a
>  >> polyhedron
>  >>
> <http://cgal-discuss.949826.n4.nabble.com/Determining-if-a-point-is-inside-a-polyhedron-tp4523460p4528701.html>
>
>  >> Sent from the cgal-discuss mailing list archive
>  >> <http://cgal-discuss.949826.n4.nabble.com/> at Nabble.com.
>
>
>
> ------------------------------------------------------------------------
> View this message in context: Re[4]: Determining if a point is inside a
> polyhedron
> <http://cgal-discuss.949826.n4.nabble.com/Determining-if-a-point-is-inside-a-polyhedron-tp4523460p4545182.html>
> Sent from the cgal-discuss mailing list archive
> <http://cgal-discuss.949826.n4.nabble.com/> at Nabble.com.