cmtool_core/utils/
polygon.rs

1// SPDX-License-Identifier: GPL-3.0-or-later
2
3use crate::coordinates::*;
4
5///A tetra cut by a plane gives at most 4 vertices, and clipping a convex polygon by a half space
6///adds at most one, so four bounds can never take it past 8
7pub(crate) const MAX_POLYGON_VERTICES: usize = 12;
8
9///Points kept by  clipper are the ones with `normal . point >= offset`
10pub(crate) struct HalfSpace {
11    pub(crate) normal: CartesianVec3,
12    pub(crate) offset: f64,
13}
14
15impl HalfSpace {
16    fn signed_distance(&self, point: &Coords3) -> f64 {
17        self.normal.dot(&CartesianVec3(*point)) - self.offset
18    }
19}
20
21///Convex polygon of the intersection, kept on the stack: this runs once per element per interface
22pub(crate) struct Polygon {
23    points: [Coords3; MAX_POLYGON_VERTICES],
24    len: usize,
25}
26
27impl Polygon {
28    pub(crate) fn from_slice(points: &[Coords3]) -> Self {
29        let mut polygon = Self {
30            points: [[0.; 3]; MAX_POLYGON_VERTICES],
31            len: points.len().min(MAX_POLYGON_VERTICES),
32        };
33        polygon.points[..polygon.len].copy_from_slice(&points[..polygon.len]);
34        polygon
35    }
36
37    pub(crate) fn as_slice(&self) -> &[Coords3] {
38        &self.points[..self.len]
39    }
40
41    fn push(&mut self, point: Coords3) {
42        if self.len < MAX_POLYGON_VERTICES {
43            self.points[self.len] = point;
44            self.len += 1;
45        }
46    }
47
48    ///Sutherland-Hodgman clipping of the polygon by one half space, the polygon has to be convex
49    ///and its vertices ordered. See https://en.wikipedia.org/wiki/Sutherland%E2%80%93Hodgman_algorithm
50    ///
51    ///        keep | drop            keep |
52    ///     +-------|---+          +-------+
53    ///     |       |  /           |      /
54    ///     |  poly | /     =      |     /
55    ///     |       |/             |    /
56    ///     +-------+              +---+
57    ///
58    pub(crate) fn clip(&self, half_space: &HalfSpace) -> Self {
59        let mut clipped = Self {
60            points: [[0.; 3]; MAX_POLYGON_VERTICES],
61            len: 0,
62        };
63
64        for i in 0..self.len {
65            let current = self.points[i];
66            let previous = self.points[(i + self.len - 1) % self.len];
67
68            let d_current = half_space.signed_distance(&current);
69            let d_previous = half_space.signed_distance(&previous);
70
71            //The edge crosses the boundary, the crossing point belongs to the clipped polygon
72            if (d_current >= 0.) != (d_previous >= 0.) {
73                let t = d_previous / (d_previous - d_current);
74                clipped.push([
75                    previous[0] + t * (current[0] - previous[0]),
76                    previous[1] + t * (current[1] - previous[1]),
77                    previous[2] + t * (current[2] - previous[2]),
78                ]);
79            }
80
81            if d_current >= 0. {
82                clipped.push(current);
83            }
84        }
85
86        clipped
87    }
88}
cmtool_core/utils/polygon.rs

cmtool_core/utils/
polygon.rs
