Coverage for trimesh/convex.py: 87%
124 statements
« prev ^ index » next coverage.py v7.14.1, created at 2026-06-24 04:40 +0000
1"""
2convex.py
4Deal with creating and checking convex objects in 2, 3 and N dimensions.
6Convex is defined as:
71) "Convex, meaning "curving out" or "extending outward" (compare to concave)
82) having an outline or surface curved like the exterior of a circle or sphere.
93) (of a polygon) having only interior angles measuring less than 180
10"""
12from dataclasses import dataclass, fields
14import numpy as np
16from . import triangles, util
17from .constants import tol
18from .parent import Geometry3D
19from .typed import NDArray
21try:
22 from scipy.spatial import ConvexHull
23except ImportError as E:
24 from .exceptions import ExceptionWrapper
26 ConvexHull = ExceptionWrapper(E)
28try:
29 from scipy.spatial import QhullError
30except BaseException:
31 QhullError = BaseException
34@dataclass
35class QhullOptions:
36 """
37 A helper class for constructing correct Qhull option strings.
38 More details available at: http://www.qhull.org/html/qh-quick.htm#options
40 Currently only includes the boolean flag options, which is most of them.
42 Parameters
43 -----------
44 Qa
45 Allow input with fewer or more points than coordinates
46 Qc
47 Keep coplanar points with nearest facet
48 Qi
49 Keep interior points with nearest facet.
50 QJ
51 Joggled input to avoid precision problems
52 Qt
53 Triangulated output.
54 Qu
55 Compute upper hull for furthest-site Delaunay triangulation
56 Qw
57 Allow warnings about Qhull options
58 Qbb
59 Scale last coordinate to [0,m] for Delaunay
60 Qs
61 Search all points for the initial simplex
62 Qv
63 Test vertex neighbors for convexity
64 Qx
65 Exact pre-merges (allows coplanar facets)
66 Qz
67 Add a point-at-infinity for Delaunay triangulations
68 QbB
69 Scale input to fit the unit cube
70 QR0
71 Random rotation (n=seed, n=0 time, n=-1 time/no rotate)
72 Qg
73 only build good facets (needs 'QGn', 'QVn', or 'Pdk')
74 Pp
75 Do not print statistics about precision problems and remove
76 some of the warnings including the narrow hull warning.
77 """
79 Qa: bool = False
80 """ Allow input with fewer or more points than coordinates"""
82 Qc: bool = False
83 """ Keep coplanar points with nearest facet"""
85 Qi: bool = False
86 """ Keep interior points with nearest facet. """
88 QJ: bool = False
89 """ Joggled input to avoid precision problems """
91 Qt: bool = False
92 """ Triangulated output. """
94 Qu: bool = False
95 """ Compute upper hull for furthest-site Delaunay triangulation """
97 Qw: bool = False
98 """ Allow warnings about Qhull options """
100 # Precision handling
101 Qbb: bool = False
102 """ Scale last coordinate to [0,m] for Delaunay """
104 Qs: bool = False
105 """ Search all points for the initial simplex """
107 Qv: bool = False
108 """ Test vertex neighbors for convexity """
110 Qx: bool = False
111 """ Exact pre-merges (allows coplanar facets) """
113 Qz: bool = False
114 """ Add a point-at-infinity for Delaunay triangulations """
116 QbB: bool = False
117 """ Scale input to fit the unit cube """
119 QR0: bool = False
120 """ Random rotation (n=seed, n=0 time, n=-1 time/no rotate) """
122 # Select facets
123 Qg: bool = False
124 """ Only build good facets (needs 'QGn', 'QVn', or 'Pdk') """
126 Pp: bool = False
127 """ Do not print statistics about precision problems and remove
128 some of the warnings including the narrow hull warning. """
130 # TODO : not included non-boolean options
131 # QBk: Floating | None = None
132 # """ Scale coord[k] to upper bound of n (default 0.5) """
134 # Qbk: Floating | None = None
135 # """ Scale coord[k] to low bound of n (default -0.5) """
137 # Qbk:0Bk:0
138 # """ drop dimension k from input """
140 # QGn
141 # good facet if visible from point n, -n for not visible
143 # QVn
144 # good facet if it includes point n, -n if not
146 def __str__(self) -> str:
147 """
148 Construct the `qhull_options` string used by `scipy.spatial`
149 objects and functions.
151 Returns
152 ----------
153 qhull_options
154 Can be passed to `scipy.spatial.[ConvexHull,Delaunay,Voronoi]`
155 """
156 return " ".join(f.name for f in fields(self) if getattr(self, f.name))
159QHULL_DEFAULT = QhullOptions(QbB=True, Pp=True, Qt=True)
162def convex_hull(
163 obj: Geometry3D | NDArray,
164 qhull_options: QhullOptions | str | None = QHULL_DEFAULT,
165 repair: bool = True,
166) -> "trimesh.Trimesh": # noqa: F821
167 """
168 Get a new Trimesh object representing the convex hull of the
169 current mesh attempting to return a watertight mesh with correct
170 normals.
172 Arguments
173 --------
174 obj
175 Mesh or `(n, 3)` points.
176 qhull_options
177 Options to pass to qhull.
179 Returns
180 --------
181 convex
182 Mesh of convex hull.
183 """
184 # would be a circular import at the module level
185 from .base import Trimesh
187 # compose the
188 if qhull_options is None:
189 qhull_str = None
190 elif isinstance(qhull_options, QhullOptions):
191 # use the __str__ method to compose this options string
192 qhull_str = str(qhull_options)
193 elif isinstance(qhull_options, str):
194 qhull_str = qhull_options
195 else:
196 raise TypeError(type(qhull_options))
198 if hasattr(obj, "vertices"):
199 points = obj.vertices.view(np.ndarray)
200 else:
201 # will remove subclassing
202 points = np.asarray(obj, dtype=np.float64)
203 if not util.is_shape(points, (-1, 3)):
204 raise ValueError("Object must be Trimesh or (n,3) points!")
206 try:
207 hull = ConvexHull(points, qhull_options=qhull_str)
208 except QhullError:
209 util.log.debug("Failed to compute convex hull: retrying with `QJ`", exc_info=True)
210 # try with "joggle" enabled
211 hull = ConvexHull(points, qhull_options="QJ")
213 # hull object doesn't remove unreferenced vertices
214 # create a mask to re- index faces for only referenced vertices
215 vid = np.sort(hull.vertices)
216 mask = np.zeros(len(hull.points), dtype=np.int64)
217 mask[vid] = np.arange(len(vid))
218 # remove unreferenced vertices here
219 faces = mask[hull.simplices].copy()
220 # rescale vertices back to original size
221 vertices = hull.points[vid].copy()
223 if not repair:
224 # create the Trimesh object for the convex hull
225 return Trimesh(vertices=vertices, faces=faces, process=True, validate=False)
227 # qhull returns faces with random winding
228 # calculate the returned normal of each face
229 crosses = triangles.cross(vertices[faces])
231 # qhull returns zero magnitude faces like an asshole
232 normals, valid = util.unitize(crosses, check_valid=True)
234 # remove zero magnitude faces
235 faces = faces[valid]
236 crosses = crosses[valid]
238 # each triangle area and mean center
239 triangles_area = triangles.area(crosses=crosses)
240 triangles_center = vertices[faces].mean(axis=1)
242 # since the convex hull is (hopefully) convex, the vector from
243 # the centroid to the center of each face
244 # should have a positive dot product with the normal of that face
245 # if it doesn't it is probably backwards
246 # note that this sometimes gets screwed up by precision issues
247 try:
248 centroid = np.average(triangles_center, weights=triangles_area, axis=0)
249 except ZeroDivisionError:
250 # degenerate hull (e.g. s390x: every simplex rounded to zero area)
251 centroid = vertices.mean(axis=0) if len(vertices) else np.zeros(3)
252 # a vector from the centroid to a point on each face
253 test_vector = triangles_center - centroid
254 # check the projection against face normals
255 backwards = util.diagonal_dot(normals, test_vector) < 0.0
257 # flip the winding outward facing
258 faces[backwards] = np.fliplr(faces[backwards])
259 # flip the normal
260 normals[backwards] *= -1.0
262 # save the work we did to the cache so it doesn't have to be recomputed
263 initial_cache = {
264 "triangles_cross": crosses,
265 "triangles_center": triangles_center,
266 "area_faces": triangles_area,
267 "centroid": centroid,
268 }
270 # create the Trimesh object for the convex hull
271 convex = Trimesh(
272 vertices=vertices,
273 faces=faces,
274 face_normals=normals,
275 initial_cache=initial_cache,
276 process=True,
277 validate=False,
278 )
280 # we did the gross case above, but sometimes precision issues
281 # leave some faces backwards anyway
282 # this call will exit early if the winding is consistent
283 # and if not will fix it by traversing the adjacency graph
284 convex.fix_normals(multibody=False)
286 # sometimes the QbB option will cause precision issues
287 # so try the hull again without it and
288 # check for qhull_options is None to avoid infinite recursion
289 if qhull_options is None and not convex.is_winding_consistent:
290 return convex_hull(convex, qhull_options=None)
292 return convex
295def adjacency_projections(mesh):
296 """
297 Test if a mesh is convex by projecting the vertices of
298 a triangle onto the normal of its adjacent face.
300 Parameters
301 ----------
302 mesh : Trimesh
303 Input geometry
305 Returns
306 ----------
307 projection : (len(mesh.face_adjacency),) float
308 Distance of projection of adjacent vertex onto plane
309 """
310 # normals and origins from the first column of face adjacency
311 normals = mesh.face_normals[mesh.face_adjacency[:, 0]]
312 # one of the vertices on the shared edge
313 origins = mesh.vertices[mesh.face_adjacency_edges[:, 0]]
315 # faces from the second column of face adjacency
316 vid_other = mesh.face_adjacency_unshared[:, 1]
317 vector_other = mesh.vertices[vid_other] - origins
319 # get the projection with a dot product
320 dots = util.diagonal_dot(vector_other, normals)
322 return dots
325def is_convex(mesh):
326 """
327 Check if a mesh is convex.
329 Parameters
330 -----------
331 mesh : Trimesh
332 Input geometry
334 Returns
335 -----------
336 convex : bool
337 Was passed mesh convex or not
338 """
339 # non-watertight meshes are not convex
340 # meshes with multiple bodies are not convex
341 if not mesh.is_watertight or mesh.body_count != 1:
342 return False
344 # don't consider zero- area faces
345 nonzero = mesh.area_faces > tol.zero
346 # adjacencies with two nonzero faces
347 adj_ok = nonzero[mesh.face_adjacency].all(axis=1)
349 # if none of our face pairs are both nonzero exit
350 # TODO : is this the correct check?
351 # or should we just compare the projections
352 # to the mesh scale
353 if not adj_ok.any():
354 return False
356 # make threshold of convexity scale- relative
357 threshold = tol.planar * mesh.scale
359 # if projections of vertex onto plane of adjacent
360 # face is negative, it means the face pair is locally
361 # convex, and if that is true for all faces the mesh is convex
362 convex = bool(mesh.face_adjacency_projections[adj_ok].max() < threshold)
364 return convex
367def hull_points(obj, qhull_options="QbB Pp"):
368 """
369 Try to extract a convex set of points from multiple input formats.
371 Details on qhull options:
372 http://www.qhull.org/html/qh-quick.htm#options
374 Parameters
375 ---------
376 obj: Trimesh object
377 (n,d) points
378 (m,) Trimesh objects
380 Returns
381 --------
382 points: (o,d) convex set of points
383 """
384 if hasattr(obj, "convex_hull"):
385 return obj.convex_hull.vertices
387 initial = np.asanyarray(obj, dtype=np.float64)
388 if len(initial.shape) != 2:
389 raise ValueError("points must be (n, dimension)!")
390 hull = ConvexHull(initial, qhull_options=qhull_options)
391 points = hull.points[hull.vertices]
393 return points