Coverage for trimesh/path/arc.py: 89%
101 statements
« prev ^ index » next coverage.py v7.14.1, created at 2026-06-24 04:40 +0000
1from dataclasses import dataclass
3import numpy as np
5from .. import util
6from ..constants import log
7from ..constants import res_path as res
8from ..constants import tol_path as tol
9from ..typed import ArrayLike, NDArray, Number, float64
11# floating point zero
12_TOL_ZERO = 1e-12
15@dataclass
16class ArcInfo:
17 # What is the radius of the circular arc?
18 radius: float
20 # what is the center of the circular arc
21 # it is either 2D or 3D depending on input.
22 center: NDArray[float64]
24 # what is the 3D normal vector of the plane the arc lies on
25 normal: NDArray[float64] | None = None
27 # what is the starting and ending angle of the arc.
28 angles: NDArray[float64] | None = None
30 # what is the angular span of this circular arc.
31 span: Number | None = None
33 def __getitem__(self, item):
34 # add for backwards compatibility
35 return getattr(self, item)
38def arc_center(
39 points: ArrayLike, return_normal: bool = True, return_angle: bool = True
40) -> ArcInfo:
41 """
42 Given three points on a 2D or 3D arc find the center,
43 radius, normal, and angular span.
45 Parameters
46 ---------
47 points : (3, dimension) float
48 Points in space, where dimension is either 2 or 3
49 return_normal : bool
50 If True calculate the 3D normal unit vector
51 return_angle : bool
52 If True calculate the start and stop angle and span
54 Returns
55 ---------
56 info
57 Arc center, radius, and other information.
58 """
59 points = np.asanyarray(points, dtype=np.float64)
61 # get the non-unit vectors of the three points
62 vectors = points[[2, 0, 1]] - points[[1, 2, 0]]
63 # we need both the squared row sum and the non-squared
64 abc2 = np.dot(vectors**2, [1] * points.shape[1])
65 # same as np.linalg.norm(vectors, axis=1)
66 abc = np.sqrt(abc2)
68 # perform radius calculation scaled to shortest edge
69 # to avoid precision issues with small or large arcs
70 scale = abc.min()
71 # get the edge lengths scaled to the smallest
72 edges = abc / scale
73 # half the total length of the edges
74 half = edges.sum() / 2.0
75 # check the denominator for the radius calculation
76 denom = half * np.prod(half - edges)
77 if denom < tol.merge:
78 raise ValueError("arc is colinear!")
79 # find the radius and scale back after the operation
80 radius = scale * ((np.prod(edges) / 4.0) / np.sqrt(denom))
82 # use a barycentric approach to get the center
83 ba2 = (abc2[[1, 2, 0, 0, 2, 1, 0, 1, 2]] * [1, 1, -1, 1, 1, -1, 1, 1, -1]).reshape(
84 (3, 3)
85 ).sum(axis=1) * abc2
86 center = points.T.dot(ba2) / ba2.sum()
88 if tol.strict:
89 # all points should be at the calculated radius from center
90 assert util.allclose(np.linalg.norm(points - center, axis=1), radius)
92 # start with initial results
93 result = {"center": center, "radius": radius}
94 if return_normal:
95 if points.shape == (3, 2):
96 # for 2D arcs still use the cross product so that
97 # the sign of the normal vector is consistent
98 result["normal"] = util.unitize(
99 np.cross(np.append(-vectors[1], 0), np.append(vectors[2], 0))
100 )
101 else:
102 # otherwise just take the cross product
103 result["normal"] = util.unitize(np.cross(-vectors[1], vectors[2]))
105 if return_angle:
106 # vectors from points on arc to center point
107 vector = util.unitize(points - center)
108 edge_direction = np.diff(points, axis=0)
109 # find the angle between the first and last vector
110 dot = np.dot(*vector[[0, 2]])
111 if dot < (_TOL_ZERO - 1):
112 angle = np.pi
113 elif dot > 1 - _TOL_ZERO:
114 angle = 0.0
115 else:
116 angle = np.arccos(dot)
117 # if the angle is nonzero and vectors are opposite direction
118 # it means we have a long arc rather than the short path
119 if abs(angle) > _TOL_ZERO and np.dot(*edge_direction) < 0.0:
120 angle = (np.pi * 2) - angle
121 # convoluted angle logic
122 angles = np.arctan2(*vector[:, :2].T[::-1]) + np.pi * 2
123 angles_sorted = np.sort(angles[[0, 2]])
124 reverse = angles_sorted[0] < angles[1] < angles_sorted[1]
125 angles_sorted = angles_sorted[:: (1 - int(not reverse) * 2)]
126 result["angles"] = angles_sorted
127 result["span"] = angle
129 return ArcInfo(**result)
132def discretize_arc(points, close=False, scale=1.0):
133 """
134 Returns a version of a three point arc consisting of
135 line segments.
137 Parameters
138 ---------
139 points : (3, d) float
140 Points on the arc where d in [2,3]
141 close : boolean
142 If True close the arc into a circle
143 scale : float
144 What is the approximate overall drawing scale
145 Used to establish order of magnitude for precision
147 Returns
148 ---------
149 discrete : (m, d) float
150 Connected points in space
151 """
152 # make sure points are (n, 3)
153 points, is_2D = util.stack_3D(points, return_2D=True)
154 # find the center of the points
155 try:
156 # try to find the center from the arc points
157 center_info = arc_center(points)
158 except BaseException:
159 # if we hit an exception return a very bad but
160 # technically correct discretization of the arc
161 if is_2D:
162 return points[:, :2]
163 return points
165 center, R, N, angle = (
166 center_info.center,
167 center_info.radius,
168 center_info.normal,
169 center_info.span,
170 )
172 # if requested, close arc into a circle
173 if close:
174 angle = np.pi * 2
176 # the number of facets, based on the angle criteria
177 count_a = angle / res.seg_angle
178 count_l = (R * angle) / (res.seg_frac * scale)
180 # figure out the number of line segments
181 count = np.max([count_a, count_l])
182 # force at LEAST 4 points for the arc
183 # otherwise the endpoints will diverge
184 count = np.clip(count, 4, np.inf)
185 count = int(np.ceil(count))
187 V1 = util.unitize(points[0] - center)
188 V2 = util.unitize(np.cross(-N, V1))
189 t = np.linspace(0, angle, count)
191 discrete = np.tile(center, (count, 1))
192 discrete += R * np.cos(t).reshape((-1, 1)) * V1
193 discrete += R * np.sin(t).reshape((-1, 1)) * V2
195 # do an in-process check to make sure result endpoints
196 # match the endpoints of the source arc
197 if not close:
198 if tol.strict:
199 arc_dist = util.row_norm(points[[0, -1]] - discrete[[0, -1]])
200 arc_ok = (arc_dist < tol.merge).all()
201 if not arc_ok:
202 log.warning(
203 "failed to discretize arc (endpoint_distance=%s R=%s)",
204 str(arc_dist),
205 R,
206 )
207 log.warning("Failed arc points: %s", str(points))
208 raise ValueError("Arc endpoints diverging!")
209 # snap the discrete result to exact control points
210 discrete[[0, -1]] = points[[0, -1]]
212 # clip to the dimension of input
213 discrete = discrete[:, : (3 - is_2D)]
215 return discrete
218def to_threepoint(center, radius, angles=None):
219 """
220 For 2D arcs, given a center and radius convert them to three
221 points on the arc.
223 Parameters
224 -----------
225 center : (2,) float
226 Center point on the plane
227 radius : float
228 Radius of arc
229 angles : (2,) float
230 Angles in radians for start and end angle
231 if not specified, will default to (0.0, pi)
233 Returns
234 ----------
235 three : (3, 2) float
236 Arc control points
237 """
238 # if no angles provided assume we want a half circle
239 if angles is None:
240 angles = [0.0, np.pi]
241 # force angles to float64
242 angles = np.asanyarray(angles, dtype=np.float64)
243 if angles.shape != (2,):
244 raise ValueError("angles must be (2,)!")
245 # provide the wrap around
246 if angles[1] < angles[0]:
247 angles[1] += np.pi * 2
249 center = np.asanyarray(center, dtype=np.float64)
250 if center.shape != (2,):
251 raise ValueError("only valid on 2D arcs!")
253 # turn the angles of [start, end]
254 # into [start, middle, end]
255 angles = np.array([angles[0], angles.mean(), angles[1]], dtype=np.float64)
256 # turn angles into (3, 2) points
257 three = (np.column_stack((np.cos(angles), np.sin(angles))) * radius) + center
259 return three