Joining Faces for any Mesh - What's the Most Fitting Data Structure?

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

Joining Faces for any Mesh - What's the Most Fitting Data Structure?

one_eyed_cat
Hello everyone,
I would like to reduce a model's complexity as much as possible by merging
adjacent, (nearly for an ε) coplanar faces. The model's surfaces can be
closed or contain holes. Currently. I am using a Polyhedron with plane
equations (like here
https://doc.cgal.org/latest/Polyhedron/Polyhedron_2polyhedron_prog_planes_8cpp-example.html
<https://doc.cgal.org/latest/Polyhedron/Polyhedron_2polyhedron_prog_planes_8cpp-example.html>
), iteratively iterating the halfedges and calling `join_facet`when needed
until there's nothing left to merge. However, I encounter problems like
antennas for more than one overlapping edge for adjacent facets or
overlapping edges in the same facet, ending up trying to merge with itself
in the merging process which makes me doubt my approach (examples appened).
I get the feeling I would have to consider a lot of factors and edge cases
if I am staying with `join_facet`. So I wonder if Polyhedron is really the
right class to use regarding the joining of any faces and not having exactly
coplanar surfaces.
If you could help a newcomer out with your experience, that would make my
day :)
Best regards
<http://cgal-discuss.949826.n4.nabble.com/file/t376194/resulting_antenna.jpg>
<http://cgal-discuss.949826.n4.nabble.com/file/t376194/overlapping.png>



--
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: Joining Faces for any Mesh - What's the Most Fitting Data Structure?

Sebastien Loriot (GeometryFactory)
In such a case the best way to proceed is to identify the set of faces
that defines an almost coplanar patch of faces and retriangulate it
directly.

You can achieve this by first find a plane for the fitting of the
patch boundary [1], then project the patch boundary points in 2D [2]
while keeping the relationship with the input vertices [3]. Then You can
triangulate that polygon [4], remove the patch faces [5] from the mesh
and refit the new one extracted from the 2D triangulation [6].

For the projection step you should use a kernel with exact
constructions such as
CGAL::Exact_predicates_inexact_constructions_kernel. More precisely,
the Plane_3 should be from that Kernel and input points provided to
the to_2d() member function can be converted on the fly using
Cartesian_converter [7].

I have a more complicated version of that code that does not use any
explicit projection but it is not yet ready to be publicly distributed.
If you contact me in private and can share your affiliation and some
details of your usage scenario, we'll see how we can get you a copy.

Best regards,

Sebastien.

[1]
https://doc.cgal.org/latest/Principal_component_analysis/index.html#Chapter_Principal_Component_Analysis
[2]
https://doc.cgal.org/latest/Kernel_23/classCGAL_1_1Plane__3.html#a24c55e9e8c0250c70f377cba0d66f330
[3]
https://doc.cgal.org/latest/Triangulation_2/Triangulation_2_2info_insert_with_pair_iterator_2_8cpp-example.html
[4]
https://doc.cgal.org/latest/Triangulation_2/Triangulation_2_2polygon_triangulation_8cpp-example.html
[5]
https://doc.cgal.org/latest/BGL/group__PkgBGLEulerOperations.html#gacfae7ff8e782da55b941e4487e86c738
[6]
https://doc.cgal.org/latest/BGL/group__PkgBGLEulerOperations.html#gaa386d0cdef3b5d6ef43d6b503392dbcd
[7]
https://doc.cgal.org/latest/Kernel_23/classCGAL_1_1Cartesian__converter.html

On 2/24/20 8:03 PM, one_eyed_cat wrote:

> Hello everyone,
> I would like to reduce a model's complexity as much as possible by merging
> adjacent, (nearly for an ε) coplanar faces. The model's surfaces can be
> closed or contain holes. Currently. I am using a Polyhedron with plane
> equations (like here
> https://doc.cgal.org/latest/Polyhedron/Polyhedron_2polyhedron_prog_planes_8cpp-example.html
> <https://doc.cgal.org/latest/Polyhedron/Polyhedron_2polyhedron_prog_planes_8cpp-example.html>
> ), iteratively iterating the halfedges and calling `join_facet`when needed
> until there's nothing left to merge. However, I encounter problems like
> antennas for more than one overlapping edge for adjacent facets or
> overlapping edges in the same facet, ending up trying to merge with itself
> in the merging process which makes me doubt my approach (examples appened).
> I get the feeling I would have to consider a lot of factors and edge cases
> if I am staying with `join_facet`. So I wonder if Polyhedron is really the
> right class to use regarding the joining of any faces and not having exactly
> coplanar surfaces.
> If you could help a newcomer out with your experience, that would make my
> day :)
> Best regards
> <http://cgal-discuss.949826.n4.nabble.com/file/t376194/resulting_antenna.jpg>
> <http://cgal-discuss.949826.n4.nabble.com/file/t376194/overlapping.png>
>
>
>
> --
> 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: Joining Faces for any Mesh - What's the Most Fitting Data Structure?

Marc Alexa
Dear Sebastien,

your last paragraph sounds like you had code for triangulating planar 3D polygons. If you have a constrained Delaunay triangulation for planar polygons in 3D avoiding the projection into the plane I think this would be very useful addition to CGAL. And I would be interested in the code in any case.

Best,
Marc





> On 26. Feb 2020, at 13:31, Sebastien Loriot (GeometryFactory) <[hidden email]> wrote:
>
> In such a case the best way to proceed is to identify the set of faces
> that defines an almost coplanar patch of faces and retriangulate it
> directly.
>
> You can achieve this by first find a plane for the fitting of the
> patch boundary [1], then project the patch boundary points in 2D [2]
> while keeping the relationship with the input vertices [3]. Then You can
> triangulate that polygon [4], remove the patch faces [5] from the mesh
> and refit the new one extracted from the 2D triangulation [6].
>
> For the projection step you should use a kernel with exact
> constructions such as CGAL::Exact_predicates_inexact_constructions_kernel. More precisely,
> the Plane_3 should be from that Kernel and input points provided to
> the to_2d() member function can be converted on the fly using
> Cartesian_converter [7].
>
> I have a more complicated version of that code that does not use any explicit projection but it is not yet ready to be publicly distributed.
> If you contact me in private and can share your affiliation and some
> details of your usage scenario, we'll see how we can get you a copy.
>
> Best regards,
>
> Sebastien.
>
> [1] https://doc.cgal.org/latest/Principal_component_analysis/index.html#Chapter_Principal_Component_Analysis
> [2] https://doc.cgal.org/latest/Kernel_23/classCGAL_1_1Plane__3.html#a24c55e9e8c0250c70f377cba0d66f330
> [3] https://doc.cgal.org/latest/Triangulation_2/Triangulation_2_2info_insert_with_pair_iterator_2_8cpp-example.html
> [4] https://doc.cgal.org/latest/Triangulation_2/Triangulation_2_2polygon_triangulation_8cpp-example.html
> [5] https://doc.cgal.org/latest/BGL/group__PkgBGLEulerOperations.html#gacfae7ff8e782da55b941e4487e86c738
> [6] https://doc.cgal.org/latest/BGL/group__PkgBGLEulerOperations.html#gaa386d0cdef3b5d6ef43d6b503392dbcd
> [7] https://doc.cgal.org/latest/Kernel_23/classCGAL_1_1Cartesian__converter.html
>
> On 2/24/20 8:03 PM, one_eyed_cat wrote:
>> Hello everyone,
>> I would like to reduce a model's complexity as much as possible by merging
>> adjacent, (nearly for an ε) coplanar faces. The model's surfaces can be
>> closed or contain holes. Currently. I am using a Polyhedron with plane
>> equations (like here
>> https://doc.cgal.org/latest/Polyhedron/Polyhedron_2polyhedron_prog_planes_8cpp-example.html
>> <https://doc.cgal.org/latest/Polyhedron/Polyhedron_2polyhedron_prog_planes_8cpp-example.html>
>> ), iteratively iterating the halfedges and calling `join_facet`when needed
>> until there's nothing left to merge. However, I encounter problems like
>> antennas for more than one overlapping edge for adjacent facets or
>> overlapping edges in the same facet, ending up trying to merge with itself
>> in the merging process which makes me doubt my approach (examples appened).
>> I get the feeling I would have to consider a lot of factors and edge cases
>> if I am staying with `join_facet`. So I wonder if Polyhedron is really the
>> right class to use regarding the joining of any faces and not having exactly
>> coplanar surfaces.
>> If you could help a newcomer out with your experience, that would make my
>> day :)
>> Best regards
>> <http://cgal-discuss.949826.n4.nabble.com/file/t376194/resulting_antenna.jpg>
>> <http://cgal-discuss.949826.n4.nabble.com/file/t376194/overlapping.png>
>> --
>> 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
>
>


--
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: Joining Faces for any Mesh - What's the Most Fitting Data Structure?

Sebastien Loriot (GeometryFactory)
On 2/28/20 10:34 AM, Marc Alexa wrote:
> Dear Sebastien,
>
> your last paragraph sounds like you had code for triangulating planar 3D polygons. If you have a constrained Delaunay triangulation for planar polygons in 3D avoiding the projection into the plane I think this would be very useful addition to CGAL. And I would be interested in the code in any case.


That's indeed the case and when I find time I will integrate it into
CGAL. But for now the code is not clean enough to be publicly
distributed and I want to know with who I'm sharing it.

Best,

Sebastien.

>
> Best,
> Marc
>
>
>
>
>
>> On 26. Feb 2020, at 13:31, Sebastien Loriot (GeometryFactory) <[hidden email]> wrote:
>>
>> In such a case the best way to proceed is to identify the set of faces
>> that defines an almost coplanar patch of faces and retriangulate it
>> directly.
>>
>> You can achieve this by first find a plane for the fitting of the
>> patch boundary [1], then project the patch boundary points in 2D [2]
>> while keeping the relationship with the input vertices [3]. Then You can
>> triangulate that polygon [4], remove the patch faces [5] from the mesh
>> and refit the new one extracted from the 2D triangulation [6].
>>
>> For the projection step you should use a kernel with exact
>> constructions such as CGAL::Exact_predicates_inexact_constructions_kernel. More precisely,
>> the Plane_3 should be from that Kernel and input points provided to
>> the to_2d() member function can be converted on the fly using
>> Cartesian_converter [7].
>>
>> I have a more complicated version of that code that does not use any explicit projection but it is not yet ready to be publicly distributed.
>> If you contact me in private and can share your affiliation and some
>> details of your usage scenario, we'll see how we can get you a copy.
>>
>> Best regards,
>>
>> Sebastien.
>>
>> [1] https://doc.cgal.org/latest/Principal_component_analysis/index.html#Chapter_Principal_Component_Analysis
>> [2] https://doc.cgal.org/latest/Kernel_23/classCGAL_1_1Plane__3.html#a24c55e9e8c0250c70f377cba0d66f330
>> [3] https://doc.cgal.org/latest/Triangulation_2/Triangulation_2_2info_insert_with_pair_iterator_2_8cpp-example.html
>> [4] https://doc.cgal.org/latest/Triangulation_2/Triangulation_2_2polygon_triangulation_8cpp-example.html
>> [5] https://doc.cgal.org/latest/BGL/group__PkgBGLEulerOperations.html#gacfae7ff8e782da55b941e4487e86c738
>> [6] https://doc.cgal.org/latest/BGL/group__PkgBGLEulerOperations.html#gaa386d0cdef3b5d6ef43d6b503392dbcd
>> [7] https://doc.cgal.org/latest/Kernel_23/classCGAL_1_1Cartesian__converter.html
>>
>> On 2/24/20 8:03 PM, one_eyed_cat wrote:
>>> Hello everyone,
>>> I would like to reduce a model's complexity as much as possible by merging
>>> adjacent, (nearly for an ε) coplanar faces. The model's surfaces can be
>>> closed or contain holes. Currently. I am using a Polyhedron with plane
>>> equations (like here
>>> https://doc.cgal.org/latest/Polyhedron/Polyhedron_2polyhedron_prog_planes_8cpp-example.html
>>> <https://doc.cgal.org/latest/Polyhedron/Polyhedron_2polyhedron_prog_planes_8cpp-example.html>
>>> ), iteratively iterating the halfedges and calling `join_facet`when needed
>>> until there's nothing left to merge. However, I encounter problems like
>>> antennas for more than one overlapping edge for adjacent facets or
>>> overlapping edges in the same facet, ending up trying to merge with itself
>>> in the merging process which makes me doubt my approach (examples appened).
>>> I get the feeling I would have to consider a lot of factors and edge cases
>>> if I am staying with `join_facet`. So I wonder if Polyhedron is really the
>>> right class to use regarding the joining of any faces and not having exactly
>>> coplanar surfaces.
>>> If you could help a newcomer out with your experience, that would make my
>>> day :)
>>> Best regards
>>> <http://cgal-discuss.949826.n4.nabble.com/file/t376194/resulting_antenna.jpg>
>>> <http://cgal-discuss.949826.n4.nabble.com/file/t376194/overlapping.png>
>>> --
>>> 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
>>
>>
>
>

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