Add experimental functions to compute the kernel of a triangle mesh #9131

sloriot · 2025-11-12T14:47:23Z

Add experimental functions to compute the kernel of a mesh

Release Management

Affected package(s): PMP, BGL
Issue(s) solved (if any):
Feature/Small Feature (if any):
Link to compiled documentation (obligatory for small feature) wrong link name to be changed
License and copyright ownership:

…tion on the bound of coordinates

…numbers

Polygon_mesh_processing/include/CGAL/Polygon_mesh_processing/clip_convex.h

…lip_convex.h Co-authored-by: Andreas Fabri <[email protected]>

sloriot · 2026-01-13T13:44:13Z

Polygon_mesh_processing/include/CGAL/Polygon_mesh_processing/kernel.h

+  std::size_t seed = choose_parameter(get_parameter(np, internal_np::random_seed), std::random_device()());
+
+  // Immediate exit if the input is not of gender zero to speedup on stupid benchmarks
+  // if (vertices(pm).size() - edges(pm).size() + faces(pm).size() != 2)


why is it no longer active? are you benchmark then wrong?

My benchmark does not contain meshes with genus different from zero and was therefore not impacted. I disabled it to be able to compute the kernel of a mesh with holes.

How can a mesh with holes have a kernel?

The definition of the kernel is equivalent to the intersection of the halfspaces defined by the faces of the mesh. With this second definition, the kernel is correctly defined and can be used to compute the kernel of only a subpart of a mesh.

Note that functions like vertices() are only tight on garbage collected meshes.

vertices.size() is always tight, num_vertices() is not.

Polygon_mesh_processing/include/CGAL/Polygon_mesh_processing/kernel.h

Co-authored-by: Andreas Fabri <[email protected]>

github-actions · 2026-01-14T10:57:23Z

The documentation is built. It will be available, after a few minutes, here: https://cgal.github.io/9131/v0/Manual/index.html

Polygon_mesh_processing/include/CGAL/Polygon_mesh_processing/kernel.h

Polygon_mesh_processing/include/CGAL/Polygon_mesh_processing/clip_convex.h

Polygon_mesh_processing/include/CGAL/Polygon_mesh_processing/kernel.h

Polygon_mesh_processing/test/Polygon_mesh_processing/test_mesh_kernel.cpp

STL_Extension/include/CGAL/STL_Extension/internal/parameters_interface.h

Co-authored-by: Andreas Fabri <[email protected]>

afabri · 2026-01-14T17:40:33Z

I think it would be reasonable to have as precondition that the surface is a watertight 2manifold with a single connected component. Probably also free of self intersections.

…_with_plane and remove_and_fill

LeoValque · 2026-01-15T11:02:30Z

I think it would be reasonable to have as precondition that the surface is a watertight 2manifold with a single connected component. Probably also free of self intersections.

None of these conditions are required for the functions to operate correctly. Should we specify preconditions that are not strictly necessary?
Side note: the absence of degenerate faces is a required precondition.

afabri · 2026-01-15T11:55:14Z

As Leo just explained me, when the surface is open, the kernel could be an unbounded polytope. Therefore the algorithm clips with the bounding box of the vertices. This must be either documented, or the function could have as second parameter a bounding object. @sloriot ???

add experimental functions to compute the kernel of a triangle mesh

6db0179

sloriot added Pkg::PMP Work in progress labels Nov 12, 2025

sloriot and others added 13 commits November 12, 2025 16:21

add an early exit option

8467e71

kernel is empty if not a topological sphere

7df4982

handle case of empty kernel

02ca6fe

update the test to accept a filename as input

5954d07

handle all file types

fd54a41

do not construct plane

3b96bc9

Add test without rounding before computing the kernel

1509582

Modify 3 planes intersections to used Ring type instead of field type

82adcbc

Working but not optimized trettner inspired kernel algorithm

a06e595

clean kernel.h and add assertions

66bcb88

Getting homogenous coordinate instead of common coordinates and asser…

ca66e33

…tion on the bound of coordinates

Clean planes storage of Plane_based_traits and refine bound check of …

5dbcc09

…numbers

Add clip_convex a specialization of clip for convex mesh

f142aa0

sloriot commented Dec 3, 2025

View reviewed changes

LeoValque added 4 commits December 3, 2025 17:18

clean clip convex

c380cda

use vector and binary_search instead of set for boundaries vertices

0fb60af

Clean clip_convex and tools to remove duplicate planes

5825620

Add comments suggested by the review

db72464

afabri reviewed Dec 9, 2025

View reviewed changes

Polygon_mesh_processing/include/CGAL/Polygon_mesh_processing/clip_convex.h Outdated Show resolved Hide resolved

LeoValque and others added 7 commits December 11, 2025 11:39

Bounding box optimization and other variant

d83067e

Factorize bbox filtering of clip_convex

1a4a78a

Update Polygon_mesh_processing/include/CGAL/Polygon_mesh_processing/c…

cc1fb56

…lip_convex.h Co-authored-by: Andreas Fabri <[email protected]>

Clean kernel and small optimization

47c1a6b

Merge branch 'PMP-kernel' of github.com:sloriot/cgal into PMP-kernel

9c4d593

Switch to EPECK to work with EPICK

4e35467

converting planes in exact on fly instead on the beginning

108e554

MaelRL added this to the 6.2-beta milestone Jan 6, 2026

sloriot commented Jan 13, 2026

View reviewed changes

correct biblio, license position

7f0368a

afabri reviewed Jan 13, 2026

View reviewed changes

Polygon_mesh_processing/include/CGAL/Polygon_mesh_processing/kernel.h Outdated Show resolved Hide resolved

correct parameters name

20f8831

This comment was marked as outdated.

Sign in to view

LeoValque and others added 4 commits January 13, 2026 16:28

change default_visitor of clip_convex

545604f

Small improvement of the doc and an image for the user manual

330f63b

Add an example for mesh kernel

8b28f5a

Apply suggestions from code review

29030f8

Co-authored-by: Andreas Fabri <[email protected]>

This comment was marked as outdated.

Sign in to view

MaelRL marked this pull request as ready for review January 14, 2026 11:02

afabri reviewed Jan 14, 2026

View reviewed changes

Apply suggestions from code review

cb11870

Co-authored-by: Andreas Fabri <[email protected]>

LeoValque added 2 commits January 14, 2026 21:00

separate clip_convex in three_functions: crossing_edge, refine_convex…

b3ec9a6

…_with_plane and remove_and_fill

Solved conflict

b210642

sloriot added Not yet approved The feature or pull-request has not yet been approved. Small feature and removed Work in progress labels Jan 15, 2026

LeoValque added 3 commits January 15, 2026 10:02

Clean clip_convex and make clip_convex a parameter of clip

b1f3d95

Move clip_convex in internal folder

e9edd55

Add a make_hexahedron taking as argument a bbox

4d0ef96

Specific code for degenerate kernels

d5d0f7e

MaelRL added CHANGES.md not updated TODO (web) labels Jan 17, 2026

MaelRL mentioned this pull request Jan 17, 2026

Breakup and improve PMP's documentation #9286

Open

1 task

Add experimental functions to compute the kernel of a triangle mesh #9131

Are you sure you want to change the base?

Add experimental functions to compute the kernel of a triangle mesh #9131

Uh oh!

Conversation

sloriot commented Nov 12, 2025 • edited by MaelRL Loading Uh oh! There was an error while loading. Please reload this page.

Uh oh!

Release Management

Uh oh!

Uh oh!

Uh oh!

Uh oh!

Uh oh!

Uh oh!

Uh oh!

Uh oh!

Uh oh!

Uh oh!

Uh oh!

Uh oh!

sloriot Jan 13, 2026

Choose a reason for hiding this comment

Uh oh!

LeoValque Jan 13, 2026

Choose a reason for hiding this comment

Uh oh!

afabri Jan 14, 2026

Choose a reason for hiding this comment

Uh oh!

LeoValque Jan 14, 2026

Choose a reason for hiding this comment

Uh oh!

afabri Jan 14, 2026

Choose a reason for hiding this comment

Uh oh!

sloriot Jan 15, 2026

Choose a reason for hiding this comment

Uh oh!

Uh oh!

This comment was marked as outdated.

This comment was marked as outdated.

This comment was marked as outdated.

github-actions bot commented Jan 14, 2026

Uh oh!

Uh oh!

Uh oh!

Uh oh!

Uh oh!

Uh oh!

Uh oh!

Uh oh!

Uh oh!

Uh oh!

Uh oh!

afabri commented Jan 14, 2026

Uh oh!

LeoValque commented Jan 15, 2026

Uh oh!

afabri commented Jan 15, 2026

Uh oh!

Reviewers

Assignees

Labels

Projects

Milestone

Development

Uh oh!

4 participants

sloriot commented Nov 12, 2025 •

edited by MaelRL

Loading