Intersection of polyhedrons

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

Intersection of polyhedrons

EgorU
This post was updated on .
Hi all!

I need to calculate volume of intersection of two polyhedron_3. I tried to
use nef_polyhedron_3, but it is too slow.

Also I  tried to use  PMP::corefine_and_compute_boolean_operations but it
also slow. May be I am do something wrong.

I also know about AABB tree or
https://doc.cgal.org/latest/Box_intersection_d/index.html

But I can't find any examples for my task.

Can you help me with it?

Thanks



--
Sent from: http://cgal-discuss.949826.n4.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: Intersection of polyhedrons

Sebastien Loriot (GeometryFactory)
Could you give more information about the size of the polyhedra
(number of simplices) and the expected runtime?
How accurate does the solution should be?
If you don't need too much accuracy, you could use a Monte Carlo
approach to estimate the intersection volume by using the class
Side_of_triangle_mesh.

https://doc.cgal.org/latest/Polygon_mesh_processing/classCGAL_1_1Side__of__triangle__mesh.html

Sebastien.

On 10/16/19 7:37 PM, EgorU wrote:

> Hi all!
>
> I need to calculate volume of intersection of two polyhedron_3. I tried to
> use nef_polyhedron_3, but it is too slow.
>
> Also I  tried to use  PMP::corefine_and_compute_boolean_operations but it
> also slow.
>
> I also know about AABB tree or
> https://doc.cgal.org/latest/Box_intersection_d/index.html
>
> But I can't find any examples for my task.
>
> Can you help me with it?
>
> Thanks
>
>
>
> --
> Sent from: http://cgal-discuss.949826.n4.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: Intersection of polyhedrons

EgorU
Hi Sebastien,

Thank you a lot for your quick response.
I'm beginner in cgal.
I'll clarify my issue.

I have one big polyhedron_3 (> 1000 vertexes or more)
and many different small polyhedron_3's  (like cube or brick, about 10
vertex )

I want to estimate a volume of intersection between big and one of small
polyhedron fast (ideally not more than 4-10 ms).

I don't need too much accuracy, only relative rating.
I saw this class
https://doc.cgal.org/latest/Polygon_mesh_processing/classCGAL_1_1Side__of__triangle__mesh.html.
But how do you propose using it? I mean, I can to check where is point
relative to the body, but if I will sort through a large number of points, I
think it will not be very effective.




--
Sent from: http://cgal-discuss.949826.n4.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: Intersection of polyhedrons

Sebastien Loriot (GeometryFactory)
Is it an option to compute the intersection of the small polys with the
big one at once and compute the volume independently?
Note that this will be possible if the small polys do not intersect each
other.

Sebastien.

On 10/17/19 8:49 AM, EgorU wrote:

> Hi Sebastien,
>
> Thank you a lot for your quick response.
> I'm beginner in cgal.
> I'll clarify my issue.
>
> I have one big polyhedron_3 (> 1000 vertexes or more)
> and many different small polyhedron_3's  (like cube or brick, about 10
> vertex )
>
> I want to estimate a volume of intersection between big and one of small
> polyhedron fast (ideally not more than 4-10 ms).
>
> I don't need too much accuracy, only relative rating.
> I saw this class
> https://doc.cgal.org/latest/Polygon_mesh_processing/classCGAL_1_1Side__of__triangle__mesh.html.
> But how do you propose using it? I mean, I can to check where is point
> relative to the body, but if I will sort through a large number of points, I
> think it will not be very effective.
>
>
>
>
> --
> Sent from: http://cgal-discuss.949826.n4.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: Intersection of polyhedrons

EgorU
No,
Look

I rotate and translate small polys near the border of a large poly.
And I need every moment to calculate intersection of it.
I have 18 different small polys. And 64 combinations of their rotations.

And for each polys and for each combination I need to calculate "weight" of
intersection of small poly and big one.  

So/ It's important for me, that I'get some "weight" of their intersection
fast.



--
Sent from: http://cgal-discuss.949826.n4.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: Intersection of polyhedrons

Sebastien Loriot (GeometryFactory)
I guess you could use the AABB-tree to extract all the faces intersected
by your small poly and create a smaller mesh out of those faces (+ some
extra faces to make it a topological disk). Then you can use the
coref+intersection to get a close mesh for which you can compute the
volume.

However, I'm afraid you won't have the runtime you expect.

Sebastien.

On 10/17/19 9:25 AM, EgorU wrote:

> No,
> Look
>
> I rotate and translate small polys near the border of a large poly.
> And I need every moment to calculate intersection of it.
> I have 18 different small polys. And 64 combinations of their rotations.
>
> And for each polys and for each combination I need to calculate "weight" of
> intersection of small poly and big one.
>
> So/ It's important for me, that I'get some "weight" of their intersection
> fast.
>
>
>
> --
> Sent from: http://cgal-discuss.949826.n4.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: Intersection of polyhedrons

EgorU
Thank very much for your help.

Did I understand correctly , that
1. I build AABB tree for big poly
2. Make a query wiith faces of small poly
3. call all_intersections function

and etc



--
Sent from: http://cgal-discuss.949826.n4.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