## 3 Path Planning Algorithm Based on the Offset Curve
### Generation of the Offset Curve on a Triangular Mesh Surface
#### 3.2.2 Details of CODP  
(1) The calculation of offset points on a triangular mesh surface  
Here are the main steps of the CODP. Figure 7 shows the schematic diagram of the offset point calculation on a triangular mesh surface. Point P is one of the discrete points on the original curve, \(\overrightarrow{n}\) is the normal vector of the surface where P is located, \(\overrightarrow{T}\) is the tangent vector of the curve where P is located, and \(\overrightarrow{T_{0}}\) is calculated by \(\overrightarrow{T}\) and \(\overrightarrow{n}\) (\(\overrightarrow{T_{0}}=\overrightarrow{T}\times\overrightarrow{n}\)) and regarded as the geodesic vector of P to the original curve. The offset section \(\Pi\) is generated by \(\overrightarrow{n}\) and \(\overrightarrow{T_{0}}\). The offset trajectory Ot is generated by calculating the intersection polyline between the offset section and the triangular mesh surface. The offset point P' is obtained on the offset trajectory, which has a distance of the offset value to P along Ot. (2) Judgment of invalid points  
Definition of Invalid Points. As shown in Figure 8, on the original curve, P1 and P3 are the two points on two sides of P2. A judgment plane can be created by the line P1P2 and the normal direction of the triangular facet where the line P1P2 is located. T is the offset direction of the line P1P2. If T and P3 are located on the same side of the judgment plane, P2 is defined as a convex point. According to the relevant research about curve offsetting, the line near the convex point will cause a local self-intersection, like the red segment shown in Figure 8, and it is defined as an invalid edge. Similarly, the edges which cause global self-intersection are also defined as invalid edges. In this paper, the discrete points are generated on the original curve, and the points on the invalid edge are called invalid points. Figure 7: Offset point generation on a triangular mesh. Judgment of Invalid Points. To judge the invalid points, we propose an offset region judgment method. The offset region is a close area surrounded by the original segment (\(L_{2}\)), the two offset trajectory polylines of the two ends of the original segment, and the offset segment, as shown in Figure 9. The method is used to determine if there are intersections between the offset region of the segment on the original curve and the offset trajectories of the other discrete points. For example, Figure 9 shows the intersection between the offset region and the offset trajectory. P1\({}^{\prime}\) and P2\({}^{\prime}\) are the two discrete points. The offset trajectory of P1\({}^{\prime}\) intersects with the offset region of \(L_{2}\), while P2\({}^{\prime}\) does not. For a discrete point, except for the line where the point is located, intersection judgments for all the other segments on the original curve are needed. As long as there is one segment whose offset region intersects with the offset trajectory of a discrete point on the original curve, the point is defined as an invalid point. All the discrete points on the original curve need to be judged point-by-point to determine whether they are invalid points or not. For example, as shown in Figure 10, taking three of the discrete points on the original curve as an example, the offset trajectory of P3\({}^{\prime}\) does not intersect with the offset region of other segments, which is a valid point. However, the offset trajectory of P4\({}^{\prime}\) intersects with the offset region of \(L_{4}\)\({}^{\prime}\), so it is an invalid point. In addition, since P5\({}^{\prime}\) would intersect with the opposite segment \(L_{2}\)\({}^{\prime}\), it is also an invalid point. The invalid points would not be taken into the offset calculation. Therefore, the method can effectively remove the local self-intersection and global self-intersection in the offset process. Figure 8: Convex point and local self-intersection. Figure 9: Intersection judgment between the offset region and the offset trajectories of the other discrete points.