Unsolved Mesh offset problem #9460
-
|
Hi, I do not know who to ask, and CGAL is the most professional open-source geometry kernel I know. I have been facing a geometrical problem for almost a decade and still cannot figure out how to solve it. Professional geometry kernels can handle this, but there is no open-source library available, and more affordable CAD modelers like Rhinoceros 3D cannot handle it either: Context:
Problem is that that at the vertex corners the faces intersect. The commercial expensive kernels somehow create little triangles so that the offsets are clean. I did not find any logic how to make this work. The problem that is described in detail: 
Does CGAL had any such project before? Do you have any ideas how to solve this problem? |
Beta Was this translation helpful? Give feedback.
Replies: 3 comments 19 replies
-
|
You need to precisely define what you want to achieve.
You can compute the Minkowski sum of a mesh with a small cube:
1. Decompose the mesh into convex pieces.
2. Compute the pairwise sums of the pieces with the cube.
3. Compute the union of sums.
If this suits you, I can provide more details.
____ _ ____ _
/_____/_) o /__________ __ //
(____ ( ( ( (_/ (_/-(-'_(/
_/
…On Sun, 3 May 2026 at 13:43, Petras Vestartas ***@***.***> wrote:
Hi,
I do not know who to ask, and CGAL is the most professional open-source
geometry kernel I know.
I have been facing a geometrical problem for almost a decade and still
cannot figure out how to solve it. Professional geometry kernels can handle
this, but there is no open-source library available, and more affordable
CAD modelers like Rhinoceros 3D cannot handle it either.
*Context:*
- You have a planar mesh
- You offset the planar mesh such that the sides of the mesh remain
planar
Problem is that that at the vertex corners the offsets must create small
triangles:
Screenshot.2026-05-03.122159.png (view on web)
<https://github.com/user-attachments/assets/da36f8c7-b8c3-466c-a529-be3240ee42bf>
Screenshot.2026-05-03.122219.png (view on web)
<https://github.com/user-attachments/assets/e24db958-7798-4990-9746-ccddd98b8c1e>
Screenshot.2026-05-03.122339.png (view on web)
<https://github.com/user-attachments/assets/23330540-2dab-4a08-ab53-e4359e13f612>
Does CGAL had any such project before? Do you have any ideas how to solve
this problem?
—
Reply to this email directly, view it on GitHub
<#9460>, or unsubscribe
<https://github.com/notifications/unsubscribe-auth/ABVBNOASDFTNQZ6HTYTQTSL4Y4PELAVCNFSM6AAAAACYO6MOESVHI2DSMVQWIX3LMV43ERDJONRXK43TNFXW4OZZHE4TKNRSHE>
.
Triage notifications on the go with GitHub Mobile for iOS
<https://apps.apple.com/app/apple-store/id1477376905?ct=notification-email&mt=8&pt=524675>
or Android
<https://play.google.com/store/apps/details?id=com.github.android&referrer=utm_campaign%3Dnotification-email%26utm_medium%3Demail%26utm_source%3Dgithub>.
You are receiving this because you are subscribed to this thread.Message
ID: ***@***.***>
|
Beta Was this translation helpful? Give feedback.
-
I attach the mesh input and output. This is the offset I can get from Solidworks. As a researcher I would like to have such method coming from CGAL. The obj files contains polylines because these are polygonal meshes. If you know how to do it would be a brilliant use case by many people who does any digital fabrication of flat elements. Thank you a lot . |
Beta Was this translation helpful? Give feedback.
-
|
Inward and outward face offsetting of polyhedral meshes is implemented in #9397. You can in particular specify different weights (speeds) for each face. Here is the simplest example for polyhedral offsetting: https://github.com/MaelRL/cgal/blob/SPS_3-Skeleton_3-GF/Straight_skeleton_3/examples/Straight_skeleton_3/create_offset_polyhedra.cpp Contrary to the paper you cite, the approach is not limited to local offsets and can handle any global combinatorial change. The limitation is that an infinitesimal perturbation must be applied to the input such that the polyhedron is in generic position (i.e., no three face may intersect in more than a point). Is this what you mean? |
Beta Was this translation helpful? Give feedback.
-
|
You can change the value "coplanarity_epsilon" in the .ini file, but it's not what causes the extra edges here. As I was saying in #9460 (reply in thread), the algorithm starts by sanitizing your input such that points are exactly on faces. As you said, for a typical input, nothing is ever exactly coplanar. So this step applies infinitesimal perturbations to vertices and faces, and in addition can triangulate some faces to find a valid solution, which is what happened here. You could apply a post processing step to merge almost-coplanar faces (see this function). Another option would be that I add an option to track input faces that are subdivided in the input, and merge them at the end. I have a correspondence map between input and output faces (not yet pushed), so that should be doable. Note that in both of these cases, you would get polygons that are not exactly coplanar. |
Beta Was this translation helpful? Give feedback.
-
|
In my opinion this would be ideal: Unless there would be an algorithm that make input faces planar. |
Beta Was this translation helpful? Give feedback.
-
|
The difficulty here of making faces planar is that almost all your vertices have degree > 3. When a vertex has degree 3, a nudge of the incident planes moves the position of the point, and that's it. But when your vertices have degree > 3, a nudge of the incident planes "breaks" the vertex into multiple degree 3 vertices. So the algorithm tries to find valid planes passing through your degree > 3 vertices, but is over-constrained, and adds breathing room by triangulating. I'll have a look at the map correspondence stuff. Let me know if you have more questions or data for the algorithm. |
Beta Was this translation helpful? Give feedback.
-
|
Added a single call to Polyhedron_transformation::merge_coplanar_facets(result_p) on the SS3 internal output polyhedron, before it gets converted to the standard output type. Please dont stop push this package to release this is amazing stuff: |
Beta Was this translation helpful? Give feedback.
-
@afabri Please include this in the 6.2 CGAL release, this stuff is supercool! |
Beta Was this translation helpful? Give feedback.
-
|
After super excitement, does it work for open meshes? |
Beta Was this translation helpful? Give feedback.
-
|
origami_closed.zip
|
Beta Was this translation helpful? Give feedback.
-
|
I added two examples in create_offset_of_non_triangle_polyhedron.cpp is a direct face to face correspondence: you give it an input, it might triangulate them during the offsetting process, but at the end of the algorithm, it will merge faces in the result if they have the same face in the input (and the merged polygonal face is representable). But: this might give surprising results due to numerical issues and the perturbation mechanisms that I mentioned above: there may be very thin "spikes" in some faces of the output polyhedra, which are caused by two faces being almost parallel in the perturbed (hence, possibly partially triangulated) input. This is the correct output given the perturbed input, but not really what we expect as result. create_offset_and_remesh.cpp is a different approach: it does not try to retain a correspondence to the input. Instead, it post-processes the meshes to remove nasty faces, and partition it in (almost) planar regions and merge faces that are part of the same region. This is a heuristic, but yields results that are what is usually expected as output. 
|
Beta Was this translation helpful? Give feedback.
-
|
@MaelRL Wow! Thank you! I will try it! Do you think there could be some good way for open meshes too? |
Beta Was this translation helpful? Give feedback.
-
|
Open meshes is more complex: what movement do you expect for a vertex with only two incident faces? |
Beta Was this translation helpful? Give feedback.
-
|
If we follow the constant mesh face offset, then at the boundary the offset would be cut by edge plane constructed from the edge line and the face normal. When vertices at boundaries dont touch it is fine: |
Beta Was this translation helpful? Give feedback.
Inward and outward face offsetting of polyhedral meshes is implemented in #9397. You can in particular specify different weights (speeds) for each face. Here is the simplest example for polyhedral offsetting: https://github.com/MaelRL/cgal/blob/SPS_3-Skeleton_3-GF/Straight_skeleton_3/examples/Straight_skeleton_3/create_offset_polyhedra.cpp
Contrary to the paper you cite, the approach is not limited to local offsets and can handle any global combinatorial change. The limitation is that an infinitesimal perturbation must be applied to the input such that the polyhedron is in generic position (i.e., no three face may intersect in more than a point).
Is this what you mean?