Trouble cutting polyhedron using a plane.

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

Trouble cutting polyhedron using a plane.

frederic.depourcq

Hi,

I am writing code that constructs bsp-trees. For this I need a robust way of
cutting polyhedra (K-dops, K-discrete oriented polytopes) using a plane. Given
a plane description and a polyhedron I want 2 polyhedra back. As simple as
cutting a block of cheese in 2 with a knife.

I could not find a solution to my problem in the documentation, but I did find
the function polyhedron_cut_plane_3  in header CGAL/polyhedron_cut_plane_3.h

I also found an example program for it: Polyhedron/polyhedron_prog_cut_cube.cpp
That example works, but when trying to use different splitting planes I get
problems.

Plane  pl = Plane(0,1,0,0.5 ); // orientation (0,1,0) offset 0.5, straight
through the [0,1]^3 cube

ERROR: coplanar planes used for computing intersecting point.
       Return ORIGIN. Don't trust result.
ERROR: coplanar planes used for computing intersecting point.
       Return ORIGIN. Don't trust result.

And it does not modify the given polyhedron.

What is going on? A cutting function that can not cut a cube in 2 equal halves?
How can I get rid of this problem?

Any help is appreciated,

Thanks,

F!
--
You are currently subscribed to cgal-discuss.
To unsubscribe or access the archives, go to
https://lists-sop.inria.fr/wws/info/cgal-discuss
Reply | Threaded
Open this post in threaded view
|

Re: Trouble cutting polyhedron using a plane.

frederic.depourcq



Hi again,

Ok, I found out what I did wrong:

* my offset was wrong, resulting in the exception, the plane must have been
outside.
* my halfedge wasn't passing through the plane, if it doesn't the program gets
stuck in a loop.
* the halfedge had to come from the correct side, I had to invert the plane or
use the opposite of my halfedge. If this is not done a segfault occurs.

Greetings,

F!


On Tuesday 24 February 2009 01:16:05 [hidden email] wrote:

> Hi,
>
> I am writing code that constructs bsp-trees. For this I need a robust way
> of cutting polyhedra (K-dops, K-discrete oriented polytopes) using a plane.
> Given a plane description and a polyhedron I want 2 polyhedra back. As
> simple as cutting a block of cheese in 2 with a knife.
>
> I could not find a solution to my problem in the documentation, but I did
> find the function polyhedron_cut_plane_3  in header
> CGAL/polyhedron_cut_plane_3.h
>
> I also found an example program for it:
> Polyhedron/polyhedron_prog_cut_cube.cpp That example works, but when trying
> to use different splitting planes I get problems.
>
> Plane  pl = Plane(0,1,0,0.5 ); // orientation (0,1,0) offset 0.5, straight
> through the [0,1]^3 cube
>
> ERROR: coplanar planes used for computing intersecting point.
>        Return ORIGIN. Don't trust result.
> ERROR: coplanar planes used for computing intersecting point.
>        Return ORIGIN. Don't trust result.
>
> And it does not modify the given polyhedron.
>
> What is going on? A cutting function that can not cut a cube in 2 equal
> halves? How can I get rid of this problem?
>
> Any help is appreciated,
>
> Thanks,
>
> F!

--
You are currently subscribed to cgal-discuss.
To unsubscribe or access the archives, go to
https://lists-sop.inria.fr/wws/info/cgal-discuss
Reply | Threaded
Open this post in threaded view
|

Accessing Finite_Vertex_Iterator as std::iterator or boost iterator

Tom Kazimiers
Hi there,

I have an interface which represents access to delaunay triangulation.
Part of this interface should be an iterator which allows me to go
through all the vertices of the triangulation. As an implementation of
this interface I built an adapter to CGAL which works pretty well -
except for the iterator.
From CGAL I can get an Finite_vertices_iterator but I need a
std::iterator (or a boost iterator) (part of the interface)
- now I wonder if there is any other way for this then writing a wrapper
class?

Thanks in advance,
Tom
--
You are currently subscribed to cgal-discuss.
To unsubscribe or access the archives, go to
https://lists-sop.inria.fr/wws/info/cgal-discuss
Reply | Threaded
Open this post in threaded view
|

Re: Accessing Finite_Vertex_Iterator as std::iterator

Sylvain Pion
Administrator
Tom Kazimiers wrote:
> I have an interface which represents access to delaunay triangulation.
> Part of this interface should be an iterator which allows me to go
> through all the vertices of the triangulation. As an implementation of
> this interface I built an adapter to CGAL which works pretty well -
> except for the iterator.
> From CGAL I can get an Finite_vertices_iterator but I need a
> std::iterator (or a boost iterator) (part of the interface)
> - now I wonder if there is any other way for this then writing a wrapper
> class?

It would be interesting to know the reason why you have such a requirement.

--
Sylvain Pion
INRIA Sophia-Antipolis
Geometrica Project-Team
CGAL, http://cgal.org/

smime.p7s (5K) Download Attachment
Reply | Threaded
Open this post in threaded view
|

Re: Accessing Finite_Vertex_Iterator as std::iterator

Tom Kazimiers
Sylvain Pion schrieb:

> Tom Kazimiers wrote:
>> I have an interface which represents access to delaunay triangulation.
>> Part of this interface should be an iterator which allows me to go
>> through all the vertices of the triangulation. As an implementation of
>> this interface I built an adapter to CGAL which works pretty well -
>> except for the iterator.
>> From CGAL I can get an Finite_vertices_iterator but I need a
>> std::iterator (or a boost iterator) (part of the interface)
>> - now I wonder if there is any other way for this then writing a wrapper
>> class?
>
> It would be interesting to know the reason why you have such a
> requirement.
>
I am working currently on an university project in which I would like to
easyly switch between delaunay triangulation variants (like between CGAL
and an implementation of one of my professors). For this I wrote an
interface (lots of "virtual ... = 0;" functions) to write code only
against this interface (which is good habbit anyway I guess). This again
would it make easy to see the behaviour of different triangulations
without changing much code.

Thanks and regards,
Tom
--
You are currently subscribed to cgal-discuss.
To unsubscribe or access the archives, go to
https://lists-sop.inria.fr/wws/info/cgal-discuss
Reply | Threaded
Open this post in threaded view
|

Re: Accessing Finite_Vertex_Iterator as std::iterator

Sylvain Pion
Administrator
Tom Kazimiers wrote:

> Sylvain Pion schrieb:
>> Tom Kazimiers wrote:
>>> I have an interface which represents access to delaunay triangulation.
>>> Part of this interface should be an iterator which allows me to go
>>> through all the vertices of the triangulation. As an implementation of
>>> this interface I built an adapter to CGAL which works pretty well -
>>> except for the iterator.
>>> From CGAL I can get an Finite_vertices_iterator but I need a
>>> std::iterator (or a boost iterator) (part of the interface)
>>> - now I wonder if there is any other way for this then writing a wrapper
>>> class?
>> It would be interesting to know the reason why you have such a
>> requirement.
>>
> I am working currently on an university project in which I would like to
> easyly switch between delaunay triangulation variants (like between CGAL
> and an implementation of one of my professors). For this I wrote an
> interface (lots of "virtual ... = 0;" functions) to write code only
> against this interface (which is good habbit anyway I guess). This again
> would it make easy to see the behaviour of different triangulations
> without changing much code.
Then I guess the answer is that you have to write wrappers.

You can also go on the generic programming path using a concept,
and write adaptors for the 2 implementations.

--
Sylvain Pion
INRIA Sophia-Antipolis
Geometrica Project-Team
CGAL, http://cgal.org/

smime.p7s (5K) Download Attachment
Reply | Threaded
Open this post in threaded view
|

Re: Accessing Finite_Vertex_Iterator as std::iterator

Tom Kazimiers
Sylvain Pion schrieb:

> Tom Kazimiers wrote:
>> Sylvain Pion schrieb:
>>> Tom Kazimiers wrote:
>>>> I have an interface which represents access to delaunay triangulation.
>>>> Part of this interface should be an iterator which allows me to go
>>>> through all the vertices of the triangulation. As an implementation of
>>>> this interface I built an adapter to CGAL which works pretty well -
>>>> except for the iterator.
>>>> From CGAL I can get an Finite_vertices_iterator but I need a
>>>> std::iterator (or a boost iterator) (part of the interface)
>>>> - now I wonder if there is any other way for this then writing a
>>>> wrapper
>>>> class?
>>> It would be interesting to know the reason why you have such a
>>> requirement.
>>>
>> I am working currently on an university project in which I would like to
>> easyly switch between delaunay triangulation variants (like between CGAL
>> and an implementation of one of my professors). For this I wrote an
>> interface (lots of "virtual ... = 0;" functions) to write code only
>> against this interface (which is good habbit anyway I guess). This again
>> would it make easy to see the behaviour of different triangulations
>> without changing much code.
>
> Then I guess the answer is that you have to write wrappers.
>
> You can also go on the generic programming path using a concept,
> and write adaptors for the 2 implementations.
>
Sylvain, thanks for your suggestions. CGAL makes a lot use of the
concept/template approach, doesn't it?

Regards,
Tom
--
You are currently subscribed to cgal-discuss.
To unsubscribe or access the archives, go to
https://lists-sop.inria.fr/wws/info/cgal-discuss
Reply | Threaded
Open this post in threaded view
|

Re: Accessing Finite_Vertex_Iterator as std::iterator

Sylvain Pion
Administrator
Tom Kazimiers wrote:

> Sylvain Pion schrieb:
>> Tom Kazimiers wrote:
>>> Sylvain Pion schrieb:
>>>> Tom Kazimiers wrote:
>>>>> I have an interface which represents access to delaunay triangulation.
>>>>> Part of this interface should be an iterator which allows me to go
>>>>> through all the vertices of the triangulation. As an implementation of
>>>>> this interface I built an adapter to CGAL which works pretty well -
>>>>> except for the iterator.
>>>>> From CGAL I can get an Finite_vertices_iterator but I need a
>>>>> std::iterator (or a boost iterator) (part of the interface)
>>>>> - now I wonder if there is any other way for this then writing a
>>>>> wrapper
>>>>> class?
>>>> It would be interesting to know the reason why you have such a
>>>> requirement.
>>>>
>>> I am working currently on an university project in which I would like to
>>> easyly switch between delaunay triangulation variants (like between CGAL
>>> and an implementation of one of my professors). For this I wrote an
>>> interface (lots of "virtual ... = 0;" functions) to write code only
>>> against this interface (which is good habbit anyway I guess). This again
>>> would it make easy to see the behaviour of different triangulations
>>> without changing much code.
>> Then I guess the answer is that you have to write wrappers.
>>
>> You can also go on the generic programming path using a concept,
>> and write adaptors for the 2 implementations.
>>
> Sylvain, thanks for your suggestions. CGAL makes a lot use of the
> concept/template approach, doesn't it?
Yes.  You can even call it abuse, sometimes :)

You will find the basic principles in the design of the STL.

--
Sylvain Pion
INRIA Sophia-Antipolis
Geometrica Project-Team
CGAL, http://cgal.org/

smime.p7s (5K) Download Attachment
Reply | Threaded
Open this post in threaded view
|

Re: Accessing Finite_Vertex_Iterator as std::iterator

Tom Kazimiers
Sylvain Pion schrieb:

> Tom Kazimiers wrote:
>> Sylvain Pion schrieb:
>>> Tom Kazimiers wrote:
>>>> Sylvain Pion schrieb:
>>>>> Tom Kazimiers wrote:
>>>>>> I have an interface which represents access to delaunay
>>>>>> triangulation.
>>>>>> Part of this interface should be an iterator which allows me to go
>>>>>> through all the vertices of the triangulation. As an
>>>>>> implementation of
>>>>>> this interface I built an adapter to CGAL which works pretty well -
>>>>>> except for the iterator.
>>>>>> From CGAL I can get an Finite_vertices_iterator but I need a
>>>>>> std::iterator (or a boost iterator) (part of the interface)
>>>>>> - now I wonder if there is any other way for this then writing a
>>>>>> wrapper
>>>>>> class?
>>>>> It would be interesting to know the reason why you have such a
>>>>> requirement.
>>>>>
>>>> I am working currently on an university project in which I would
>>>> like to
>>>> easyly switch between delaunay triangulation variants (like between
>>>> CGAL
>>>> and an implementation of one of my professors). For this I wrote an
>>>> interface (lots of "virtual ... = 0;" functions) to write code only
>>>> against this interface (which is good habbit anyway I guess). This
>>>> again
>>>> would it make easy to see the behaviour of different triangulations
>>>> without changing much code.
>>> Then I guess the answer is that you have to write wrappers.
>>>
>>> You can also go on the generic programming path using a concept,
>>> and write adaptors for the 2 implementations.
>>>
>> Sylvain, thanks for your suggestions. CGAL makes a lot use of the
>> concept/template approach, doesn't it?
>
> Yes.  You can even call it abuse, sometimes :)
>
> You will find the basic principles in the design of the STL.
>
Hehe, I see. Sorry, but I got one more littel question regarding the the
concept thing:
Concepts seem to be something like a not-written-out interface contract
- is this true? Like one assumes serveral methods in a instantiated
template.


--
You are currently subscribed to cgal-discuss.
To unsubscribe or access the archives, go to
https://lists-sop.inria.fr/wws/info/cgal-discuss
Reply | Threaded
Open this post in threaded view
|

Re: Accessing Finite_Vertex_Iterator as std::iterator

Sylvain Pion
Administrator
Tom Kazimiers wrote:

> Sylvain Pion schrieb:
>> Tom Kazimiers wrote:
>>> Sylvain Pion schrieb:
>>>> Tom Kazimiers wrote:
>>>>> Sylvain Pion schrieb:
>>>>>> Tom Kazimiers wrote:
>>>>>>> I have an interface which represents access to delaunay
>>>>>>> triangulation.
>>>>>>> Part of this interface should be an iterator which allows me to go
>>>>>>> through all the vertices of the triangulation. As an
>>>>>>> implementation of
>>>>>>> this interface I built an adapter to CGAL which works pretty well -
>>>>>>> except for the iterator.
>>>>>>> From CGAL I can get an Finite_vertices_iterator but I need a
>>>>>>> std::iterator (or a boost iterator) (part of the interface)
>>>>>>> - now I wonder if there is any other way for this then writing a
>>>>>>> wrapper
>>>>>>> class?
>>>>>> It would be interesting to know the reason why you have such a
>>>>>> requirement.
>>>>>>
>>>>> I am working currently on an university project in which I would
>>>>> like to
>>>>> easyly switch between delaunay triangulation variants (like between
>>>>> CGAL
>>>>> and an implementation of one of my professors). For this I wrote an
>>>>> interface (lots of "virtual ... = 0;" functions) to write code only
>>>>> against this interface (which is good habbit anyway I guess). This
>>>>> again
>>>>> would it make easy to see the behaviour of different triangulations
>>>>> without changing much code.
>>>> Then I guess the answer is that you have to write wrappers.
>>>>
>>>> You can also go on the generic programming path using a concept,
>>>> and write adaptors for the 2 implementations.
>>>>
>>> Sylvain, thanks for your suggestions. CGAL makes a lot use of the
>>> concept/template approach, doesn't it?
>> Yes.  You can even call it abuse, sometimes :)
>>
>> You will find the basic principles in the design of the STL.
>>
> Hehe, I see. Sorry, but I got one more littel question regarding the the
> concept thing:
> Concepts seem to be something like a not-written-out interface contract
> - is this true? Like one assumes serveral methods in a instantiated
> template.
This is getting off-topic for this list.
I'd suggest that you take a look at some good book,
like Matt Austern's "Generic Programming and the STL".

--
Sylvain Pion
INRIA Sophia-Antipolis
Geometrica Project-Team
CGAL, http://cgal.org/

smime.p7s (5K) Download Attachment
Reply | Threaded
Open this post in threaded view
|

Re: Accessing Finite_Vertex_Iterator as std::iterator

Tom Kazimiers
Sylvain Pion schrieb:

> Tom Kazimiers wrote:
>> Sylvain Pion schrieb:
>>> Tom Kazimiers wrote:
>>>> Sylvain Pion schrieb:
>>>>> Tom Kazimiers wrote:
>>>>>> Sylvain Pion schrieb:
>>>>>>> Tom Kazimiers wrote:
>>>>>>>> I have an interface which represents access to delaunay
>>>>>>>> triangulation.
>>>>>>>> Part of this interface should be an iterator which allows me to go
>>>>>>>> through all the vertices of the triangulation. As an
>>>>>>>> implementation of
>>>>>>>> this interface I built an adapter to CGAL which works pretty
>>>>>>>> well -
>>>>>>>> except for the iterator.
>>>>>>>> From CGAL I can get an Finite_vertices_iterator but I need a
>>>>>>>> std::iterator (or a boost iterator) (part of the interface)
>>>>>>>> - now I wonder if there is any other way for this then writing a
>>>>>>>> wrapper
>>>>>>>> class?
>>>>>>> It would be interesting to know the reason why you have such a
>>>>>>> requirement.
>>>>>>>
>>>>>> I am working currently on an university project in which I would
>>>>>> like to
>>>>>> easyly switch between delaunay triangulation variants (like between
>>>>>> CGAL
>>>>>> and an implementation of one of my professors). For this I wrote an
>>>>>> interface (lots of "virtual ... = 0;" functions) to write code only
>>>>>> against this interface (which is good habbit anyway I guess). This
>>>>>> again
>>>>>> would it make easy to see the behaviour of different triangulations
>>>>>> without changing much code.
>>>>> Then I guess the answer is that you have to write wrappers.
>>>>>
>>>>> You can also go on the generic programming path using a concept,
>>>>> and write adaptors for the 2 implementations.
>>>>>
>>>> Sylvain, thanks for your suggestions. CGAL makes a lot use of the
>>>> concept/template approach, doesn't it?
>>> Yes.  You can even call it abuse, sometimes :)
>>>
>>> You will find the basic principles in the design of the STL.
>>>
>> Hehe, I see. Sorry, but I got one more littel question regarding the the
>> concept thing:
>> Concepts seem to be something like a not-written-out interface contract
>> - is this true? Like one assumes serveral methods in a instantiated
>> template.
>
> This is getting off-topic for this list.
> I'd suggest that you take a look at some good book,
> like Matt Austern's "Generic Programming and the STL".
>
Sure, I will take a look into this.

Thanks,
Tom

--
You are currently subscribed to cgal-discuss.
To unsubscribe or access the archives, go to
https://lists-sop.inria.fr/wws/info/cgal-discuss
Reply | Threaded
Open this post in threaded view
|

Re: Trouble cutting polyhedron using a plane.

gunshi
In reply to this post by frederic.depourcq
Hi Frederic,
could you share the code/sample snippet using which you are testing the function and inverting the plane, this is exactly what i want to do as well, as i've stated in another thread, (http://cgal-discuss.949826.n4.nabble.com/polyhedron-clipping-using-a-plane-td4661242.html) and inverting the plane is an essential step for me as well, though i don't know how to get the other half space except by taking the NOT of the half space of the plane using nef_polyhedra.
Thanks!
Gunshi