CGAL users discussion list

[Oleg <>]

Wednesday, April 11, 2012, 13:26, you wrote:

> 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.

I consider this option. The problem with it is that we are going to
use the mesh to simulate unsteady processes, so remeshing all the
domain on each time step would take much time. It seems that remeshing
the near-intersection region only would be much faster, so I'm trying
to figure out what would be the best way to do it..

Oleg

>>
>> 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: Re[6]: Determining if a point is inside a polyhedron
Sent from the cgal-discuss mailing list archive at Nabble.com.