subsphere/
hex.rs

1//! Contains types related to [`HexSphere`].
2use crate::prelude::*;
3use crate::proj::{self, BaseTriProjector};
4use crate::tri::{self, BaseRegion, BaseRegionType, TriSphere};
5use std::num::NonZero;
6
7/// A tessellation of the unit sphere into *mostly* hexagonal [`Face`]s, constructed by grouping
8/// triangles of a [`TriSphere`].
9///
10/// Equivalently, this is a tessellation formed by projecting a
11/// [Goldberg polyhedron](https://en.wikipedia.org/wiki/Goldberg_polyhedron) onto
12/// the sphere.
13#[derive(Clone, Copy, Debug, PartialEq, Eq, Hash)]
14pub struct HexSphere<Proj = proj::Default> {
15    kis: TriSphere<Proj>,
16}
17
18impl<Proj: Clone + BaseTriProjector> TriSphere<Proj> {
19    /// [Truncates](https://en.wikipedia.org/wiki/Truncation_(geometry)) the vertices of this
20    /// [`TriSphere`] to create a [`HexSphere`].
21    ///
22    /// This will convert all existing faces into hexagons, and create a new face at each vertex.
23    pub fn truncate(self) -> HexSphere<Proj> {
24        HexSphere {
25            kis: self.subdivide_edge(NonZero::new(3).unwrap()),
26        }
27    }
28}
29
30impl<Proj> HexSphere<Proj> {
31    /// Attempts to construct a [`HexSphere`] whose [`kis`](HexSphere::kis) is the given
32    /// [`TriSphere`].
33    ///
34    /// For this to succeed, the [`TriSphere`] parameters must satisfy `b % 3 == c % 3`.
35    /// This will return [`None`] otherwise.
36    pub fn from_kis(kis: TriSphere<Proj>) -> Option<Self> {
37        if (kis.b() + 2 * kis.c()) % 3 == 0 {
38            Some(Self { kis })
39        } else {
40            None
41        }
42    }
43
44    /// Performs the
45    /// [kis](https://en.wikipedia.org/wiki/Conway_polyhedron_notation#Original_operations)
46    /// operation on this [`HexSphere`].
47    ///
48    /// This creates a [`Face`](crate::Face) for each [`HalfEdge`] in the [`HexSphere`].
49    pub fn kis(self) -> TriSphere<Proj> {
50        self.kis
51    }
52
53    /// Replaces the projector of this sphere with the given one.
54    ///
55    /// The resulting sphere will be topologically identical to this one, but the positions
56    /// of the vertices will be changed according to the new projection.
57    pub fn with_projector<NProj>(self, proj: NProj) -> HexSphere<NProj> {
58        HexSphere {
59            kis: self.kis.with_projector(proj),
60        }
61    }
62
63    /// [`TriSphere::num_divisions`] for the dual of this [`HexSphere`].
64    const fn dual_num_divisions(&self) -> usize {
65        let b = self.kis.b() as usize;
66        let c = self.kis.c() as usize;
67        let dual_c = (b - c) / 3;
68        let dual_b = c + dual_c;
69        dual_b * (dual_b + dual_c) + dual_c * dual_c
70    }
71
72    /// The number of faces per edge [`BaseRegion`].
73    fn num_faces_per_edge_region(&self) -> usize {
74        let b = self.kis.b() as usize;
75        let c = self.kis.c() as usize;
76        num_faces_on_edge(b, c + 1)
77    }
78
79    /// The number of faces per interior [`BaseRegion`].
80    fn num_faces_per_interior_region(&self) -> usize {
81        let b = self.kis.b() as usize;
82        let c = self.kis.c() as usize;
83        let n = b - c;
84        if n == 0 {
85            (c % 3 == 0) as usize
86        } else {
87            num_faces_on_interior(c, n, n)
88        }
89    }
90
91    /// The number of vertices per edge [`BaseRegion`], assuming that the origin vertex is not
92    /// counted.
93    fn num_vertices_per_edge_region(&self) -> usize {
94        self.kis.num_vertices_per_edge_region() - self.num_faces_per_edge_region()
95    }
96
97    /// The number of vertices per interior [`BaseRegion`].
98    fn num_vertices_per_interior_region(&self) -> usize {
99        self.kis.num_vertices_per_interior_region() - self.num_faces_per_interior_region()
100    }
101}
102
103/// Counts the number of points `(u, v)` such that `0 < u < b`, `v < d` and `u % 3 == v % 3`.
104fn num_faces_on_edge(b: usize, d: usize) -> usize {
105    ((b - 1) * d + (b % 3) / 2) / 3
106}
107
108#[test]
109fn test_num_faces_on_edge() {
110    for b in 1..10 {
111        for d in 0..10 {
112            let mut count = 0;
113            for u in 1..b {
114                for v in 0..d {
115                    if u % 3 == v % 3 {
116                        count += 1;
117                    }
118                }
119            }
120            assert_eq!(
121                num_faces_on_edge(b, d),
122                count,
123                "failed for b = {}, d = {}",
124                b,
125                d
126            );
127        }
128    }
129}
130
131/// Counts the number of points `(u, v)` such that `0 < u + v < n`, `v < d` and
132/// `u % 3 == (v + k) % 3`. Assumes that `n` is a multiple of 3.
133fn num_faces_on_interior(k: usize, n: usize, d: usize) -> usize {
134    (d - 1) * (2 * n - d - 2) / 6 + ((k % 3 == 0) & (d % 3 != 1)) as usize
135}
136
137#[test]
138fn test_num_faces_on_interior() {
139    for k in 0..2 {
140        for n_3 in 1..10 {
141            let n = n_3 * 3;
142            for d in 1..n {
143                let mut count = 0;
144                for u in 1..n {
145                    for v in 1..d {
146                        if u + v < n && u % 3 == (v + k) % 3 {
147                            count += 1;
148                        }
149                    }
150                }
151                assert_eq!(
152                    num_faces_on_interior(k, n, d),
153                    count,
154                    "failed for k = {}, n = {}, d = {}",
155                    k,
156                    n,
157                    d
158                );
159            }
160        }
161    }
162}
163
164impl<Proj: Eq + Clone + BaseTriProjector> crate::Sphere for HexSphere<Proj> {
165    type Face = Face<Proj>;
166    type Vertex = Vertex<Proj>;
167    type HalfEdge = HalfEdge<Proj>;
168
169    fn num_faces(&self) -> usize {
170        self.num_vertices() / 2 + 2
171    }
172
173    fn face(&self, index: usize) -> Face<Proj> {
174        // TODO: "Real" implementation with constant-time performance
175        self.faces().nth(index).expect("face index out of bounds")
176    }
177
178    fn faces(&self) -> impl Iterator<Item = Face<Proj>> {
179        FaceIter {
180            sphere: self.clone(),
181            region: self.kis.base().first_region(),
182            u: 0,
183            u_end: self.kis.b(),
184            v: 0,
185        }
186    }
187
188    fn face_at(&self, point: [f64; 3]) -> Face<Proj> {
189        Face::from_kis_unchecked(self.kis.face_at(point))
190    }
191
192    fn num_vertices(&self) -> usize {
193        self.dual_num_divisions() * self.kis.base().num_faces()
194    }
195
196    fn vertex(&self, _index: usize) -> Vertex<Proj> {
197        todo!()
198    }
199
200    fn vertices(&self) -> impl Iterator<Item = Vertex<Proj>> {
201        VertexIter {
202            sphere: self.clone(),
203            region: self.kis.base().first_region(),
204            u: 1,
205            u_end: self.kis.b(),
206            v: 0,
207            skip: false,
208        }
209    }
210}
211
212/// Represents a face on a [`HexSphere`].
213#[derive(Clone, Copy, Debug, PartialEq, Eq, Hash)]
214pub struct Face<Proj> {
215    center: tri::Vertex<Proj>,
216}
217
218impl<Proj: Eq + Clone + BaseTriProjector> Face<Proj> {
219    /// Gets the hexsphere face whose central vertex, in the [kised](HexSphere::kis) [`TriSphere`],
220    /// is the given [`Vertex`](tri::Vertex).
221    ///
222    /// This will return [`None`] if the given vertex does not correspond to a face on any
223    /// [`HexSphere`].
224    ///
225    /// # Examples
226    /// ```
227    /// # use subsphere::prelude::*;
228    /// let sphere = subsphere::icosphere().truncate();
229    /// let face = sphere.face(0);
230    /// let center = face.center();
231    /// assert_eq!(subsphere::hex::Face::from_center(center), Some(face));
232    /// ```
233    pub fn from_center(center: tri::Vertex<Proj>) -> Option<Self> {
234        if center.sphere.b() % 3 != center.sphere.c() % 3 {
235            return None;
236        }
237        if center.u % 3 != center.adjusted_v() % 3 {
238            return None;
239        }
240        Some(Self { center })
241    }
242
243    /// Gets the hexsphere face which, when [kised](HexSphere::kis), produces the given
244    /// triangular [`Face`](tri::Face).
245    ///
246    /// This will return [`None`] if there is no way to produce the given face by performing a
247    /// kis operation.
248    ///
249    /// # Examples
250    /// ```
251    /// # use subsphere::prelude::*;
252    /// let sphere = subsphere::icosphere().truncate();
253    /// let face = sphere.face(0);
254    /// let kis_face = face.side(0).kis().inside();
255    /// assert_eq!(subsphere::hex::Face::from_kis(kis_face), Some(face));
256    /// ```
257    pub fn from_kis(kis: tri::Face<Proj>) -> Option<Self> {
258        if kis.sphere.b() % 3 != kis.sphere.c() % 3 {
259            return None;
260        }
261
262        Some(Self::from_kis_unchecked(kis))
263    }
264
265    /// Unchecked variant of [from_center](Face::from_center).
266    fn from_center_unchecked(center: tri::Vertex<Proj>) -> Self {
267        debug_assert_eq!(
268            center.sphere.b() % 3,
269            center.sphere.c() % 3,
270            "Sphere b and c parameters must be congruent mod 3."
271        );
272        debug_assert_eq!(
273            center.u % 3,
274            center.adjusted_v() % 3,
275            "Vertex u and adjusted v must be congruent mod 3."
276        );
277        Self { center }
278    }
279
280    /// Unchecked variant of [from_kis](Face::from_kis).
281    fn from_kis_unchecked(kis: tri::Face<Proj>) -> Self {
282        debug_assert_eq!(
283            kis.sphere.b() % 3,
284            kis.sphere.c() % 3,
285            "Kis b and c parameters must be congruent mod 3."
286        );
287
288        let adj_v = if !kis.region.ty().is_edge() {
289            kis.sphere.c()
290        } else {
291            0
292        };
293
294        let [u, v] = match ((kis.u_0 + 2 * (kis.v_0 + adj_v)) % 3, kis.boundary_along_v) {
295            (0, _) => [kis.u_0, kis.v_0],
296            (1, _) => [kis.u_0, kis.v_0 + 1],
297            (_, false) => [kis.u_0 + 1, kis.v_0],
298            (_, true) => [kis.u_0 - 1, kis.v_0 + 1],
299        };
300
301        Self::from_center_unchecked(tri::Vertex::new(kis.sphere, kis.region, u, v))
302    }
303
304    /// The [`HexSphere`] that this [`Face`] belongs to.
305    pub fn sphere(&self) -> HexSphere<Proj> {
306        HexSphere {
307            kis: self.center.sphere.clone(),
308        }
309    }
310
311    /// The central vertex of this face on the [kised](HexSphere::kis) [`TriSphere`].
312    pub fn center(self) -> tri::Vertex<Proj> {
313        self.center
314    }
315
316    /// Indicates whether this is a hexagonal face.
317    pub fn is_hex(&self) -> bool {
318        self.center.as_base().is_none()
319    }
320}
321
322impl<Proj: Eq + Clone + BaseTriProjector> crate::Face for Face<Proj> {
323    type Vertex = Vertex<Proj>;
324    type HalfEdge = HalfEdge<Proj>;
325
326    fn index(&self) -> usize {
327        let b = self.center.sphere.b() as usize;
328        let c = self.center.sphere.c() as usize;
329        if self.center.region.ty().is_edge() {
330            self.sphere().base_face_index(self.center.region)
331                + num_faces_on_edge(b, self.center.v as usize)
332                + (self.center.u as usize).div_ceil(3)
333        } else if c < b {
334            self.sphere().base_face_index(self.center.region)
335                + num_faces_on_interior(c, b - c, self.center.v as usize)
336                + (self.center.u as usize).div_ceil(3)
337        } else {
338            self.sphere().base_face_index(self.center.region) + 1
339        }
340    }
341
342    fn area(&self) -> f64 {
343        crate::util::poly_area(self.vertices().map(|v| v.pos()))
344    }
345
346    fn num_sides(&self) -> usize {
347        if let Some(base) = self.center.as_base() {
348            base.degree()
349        } else {
350            6
351        }
352    }
353
354    fn side(&self, index: usize) -> HalfEdge<Proj> {
355        HalfEdge {
356            kis: self.center.outgoing(index).next(),
357        }
358    }
359}
360
361/// Represents a vertex on a [`HexSphere`].
362#[derive(Clone, Copy, Debug, PartialEq, Eq, Hash)]
363pub struct Vertex<Proj> {
364    kis: tri::Vertex<Proj>,
365}
366
367impl<Proj> Vertex<Proj> {
368    /// Constructs a [`Vertex`] from the given [`tri::Vertex`].
369    fn new(kis: tri::Vertex<Proj>) -> Self {
370        debug_assert_ne!(kis.u % 3, kis.adjusted_v() % 3);
371        Self { kis }
372    }
373}
374
375impl<Proj> tri::Vertex<Proj> {
376    /// The `v` coordinate of this vertex, measured from the base vertex of its region, rather
377    /// than the local origin.
378    ///
379    /// The combination of `u` and `adjusted_v` can be used to tell whether a [`tri::Vertex`]
380    /// corresponds to a face or a vertex on a [`HexSphere`].
381    fn adjusted_v(&self) -> u32 {
382        let mut v = self.v;
383        if !self.region.ty().is_edge() {
384            v += self.sphere.c();
385        }
386        v
387    }
388}
389
390impl<Proj: Clone> Vertex<Proj> {
391    /// The [`HexSphere`] that this [`Vertex`] belongs to.
392    pub fn sphere(&self) -> HexSphere<Proj> {
393        HexSphere {
394            kis: self.kis.sphere.clone(),
395        }
396    }
397
398    /// The corresponding vertex on the [kised](HexSphere::kis) [`TriSphere`].
399    pub fn kis(self) -> tri::Vertex<Proj> {
400        self.kis
401    }
402}
403
404impl<Proj: Eq + Clone + BaseTriProjector> crate::Vertex for Vertex<Proj> {
405    type Face = Face<Proj>;
406    type HalfEdge = HalfEdge<Proj>;
407
408    fn index(&self) -> usize {
409        let b = self.kis.sphere.b() as usize;
410        let c = self.kis.sphere.c() as usize;
411        if self.kis.region.ty().is_edge() {
412            self.sphere().base_vertex_index(self.kis.region) + self.kis.v as usize * (b - 1)
413                - num_faces_on_edge(b, self.kis.v as usize)
414                + (self.kis.u as usize * 2 - 1 - (self.kis.v % 3 == 1) as usize) / 3
415        } else if c < b {
416            let n = b - c;
417            self.sphere().base_vertex_index(self.kis.region)
418                + (self.kis.v as usize - 1) * (2 * n - self.kis.v as usize - 2) / 2
419                - num_faces_on_interior(c, n, self.kis.v as usize)
420                + (self.kis.u as usize * 2 - 1 - ((self.kis.v as usize + c) % 3 == 1) as usize) / 3
421        } else {
422            self.sphere().base_vertex_index(self.kis.region)
423        }
424    }
425
426    fn pos(&self) -> [f64; 3] {
427        self.kis.pos()
428    }
429
430    fn degree(&self) -> usize {
431        3
432    }
433
434    fn outgoing(&self, index: usize) -> HalfEdge<Proj> {
435        assert!(index < 3, "index out of bounds");
436        let phase = (self.kis.u + 2 * self.kis.adjusted_v()) % 3;
437        debug_assert_ne!(phase, 0);
438        HalfEdge {
439            kis: tri::HalfEdge::new(
440                self.kis.sphere.clone(),
441                self.kis.region,
442                self.kis.u,
443                self.kis.v,
444                tri::HalfEdgeDir::from_index(2 * index + phase as usize - 1),
445            ),
446        }
447    }
448}
449
450/// Represents one "side" of an edge on a [`HexSphere`].
451#[derive(Clone, Copy, Debug, PartialEq, Eq, Hash)]
452pub struct HalfEdge<Proj> {
453    kis: tri::HalfEdge<Proj>,
454}
455
456impl<Proj> HalfEdge<Proj> {
457    /// The corresponding half-edge on the [kised](HexSphere::kis) [`TriSphere`].
458    pub fn kis(self) -> tri::HalfEdge<Proj> {
459        self.kis
460    }
461}
462
463impl<Proj: Eq + Clone + BaseTriProjector> crate::HalfEdge for HalfEdge<Proj> {
464    type Face = Face<Proj>;
465    type Vertex = Vertex<Proj>;
466
467    fn side_index(&self) -> usize {
468        self.kis.prev().outgoing_index()
469    }
470
471    fn length(&self) -> f64 {
472        self.kis.length()
473    }
474
475    fn angle(&self) -> f64 {
476        let v_a = self.prev().start().pos();
477        let v_b = self.start().pos();
478        let v_c = self.next().start().pos();
479        crate::util::angle(v_a, v_b, v_c)
480    }
481
482    fn inside(&self) -> Face<Proj> {
483        Face {
484            center: self.kis.prev().start(),
485        }
486    }
487
488    fn start(&self) -> Vertex<Proj> {
489        Vertex {
490            kis: self.kis.start(),
491        }
492    }
493
494    fn twin(&self) -> Self {
495        Self {
496            kis: self.kis.twin(),
497        }
498    }
499
500    fn prev(&self) -> Self {
501        Self {
502            kis: self.kis.prev().twin().prev(),
503        }
504    }
505
506    fn next(&self) -> Self {
507        Self {
508            kis: self.kis.next().twin().next(),
509        }
510    }
511}
512
513impl<Proj> HexSphere<Proj> {
514    /// Gets the index of the first face which is owned by the given base region,
515    /// not counting the one corresponding to the first vertex of the base shape.
516    fn base_face_index(&self, region: BaseRegion) -> usize {
517        let face = region.owner();
518        let num_owned_vertices_before = face.num_owned_vertices_before()
519            + (face.owns_vertex_1() && region.ty() > BaseRegionType::EDGE_0) as usize;
520        let num_edge_regions_before =
521            face.num_owned_edges_before() + (region.ty() > BaseRegionType::EDGE_0) as usize;
522        let num_interior_regions_before =
523            face.index() + (region.ty() > BaseRegionType::INTERIOR) as usize;
524        num_owned_vertices_before
525            + num_edge_regions_before * self.num_faces_per_edge_region()
526            + num_interior_regions_before * self.num_faces_per_interior_region()
527    }
528
529    /// Gets the index of the first vertex which is owned by the given base region.
530    fn base_vertex_index(&self, region: BaseRegion) -> usize {
531        let face = region.owner();
532        let num_edge_regions_before =
533            face.num_owned_edges_before() + (region.ty() > BaseRegionType::EDGE_0) as usize;
534        let num_interior_regions_before =
535            face.index() + (region.ty() > BaseRegionType::INTERIOR) as usize;
536        num_edge_regions_before * self.num_vertices_per_edge_region()
537            + num_interior_regions_before * self.num_vertices_per_interior_region()
538    }
539}
540
541impl<Proj> HexSphere<Proj> {
542    /// Iterates over the faces of this [`HexSphere`], starting with the given region.
543    fn faces_from(self, region: BaseRegion) -> FaceIter<Proj> {
544        let b = self.kis.b();
545        let c = self.kis.c();
546        if region.ty().is_edge() {
547            FaceIter {
548                sphere: self,
549                region,
550                u: 3,
551                u_end: b,
552                v: 0,
553            }
554        } else if c < b {
555            let n = b - c;
556            FaceIter {
557                sphere: self,
558                region,
559                u: 1 + c % 3,
560                u_end: n - 1,
561                v: 1,
562            }
563        } else {
564            // This is a special case. When `b == c` and `c % 3 == 0`, there is exactly one
565            // interior face, at (0, 0).
566            FaceIter {
567                sphere: self,
568                region,
569                u: c % 3,
570                u_end: 1,
571                v: 0,
572            }
573        }
574    }
575}
576
577/// An iterator over the faces of an [`TriSphere`].
578#[derive(Clone, Debug)]
579pub struct FaceIter<Proj> {
580    sphere: HexSphere<Proj>,
581    region: BaseRegion,
582    u: u32,
583    u_end: u32,
584    v: u32,
585}
586
587impl<Proj: Eq + Clone + BaseTriProjector> Iterator for FaceIter<Proj> {
588    type Item = Face<Proj>;
589    fn next(&mut self) -> Option<Face<Proj>> {
590        loop {
591            if self.u < self.u_end {
592                let res = Face::from_center_unchecked(tri::Vertex {
593                    sphere: self.sphere.kis.clone(),
594                    region: self.region,
595                    u: self.u,
596                    v: self.v,
597                });
598                self.u += 3;
599                return Some(res);
600            } else if self.region.ty().is_edge() {
601                if self.v < self.sphere.kis.c() {
602                    self.v += 1;
603                    self.u = 1 + (self.v + 2) % 3;
604                    continue;
605                } else if self.u <= self.u_end
606                    && self.region.ty() == BaseRegionType::EDGE_0
607                    && self.region.owner().owns_vertex_1()
608                {
609                    let res = Face::from_center_unchecked(tri::Vertex {
610                        sphere: self.sphere.kis.clone(),
611                        region: self.region,
612                        u: self.u,
613                        v: self.v,
614                    });
615                    self.u += 3;
616                    return Some(res);
617                }
618            } else {
619                let n = self.sphere.kis.b() - self.sphere.kis.c();
620                if self.v + 1 < n {
621                    self.v += 1;
622                    self.u = 1 + (self.v + self.sphere.kis.c() + 2) % 3;
623                    self.u_end = n - self.v;
624                    continue;
625                }
626            }
627            if let Some(region) = self.sphere.kis.base().next_region(self.region) {
628                *self = self.sphere.clone().faces_from(region);
629                continue;
630            } else {
631                return None;
632            }
633        }
634    }
635}
636
637impl<Proj: Eq + Clone + BaseTriProjector> HexSphere<Proj> {
638    /// Iterates over the vertices of this [`HexSphere`], starting with the given region.
639    fn vertices_from(self, region: BaseRegion) -> VertexIter<Proj> {
640        let b = self.kis.b();
641        let c = self.kis.c();
642        if region.ty().is_edge() {
643            VertexIter {
644                sphere: self,
645                region,
646                u: 1,
647                u_end: b,
648                v: 0,
649                skip: false,
650            }
651        } else if c < b {
652            let n = b - c;
653            VertexIter {
654                sphere: self,
655                region,
656                u: 1 + (c % 3 == 0) as u32,
657                u_end: n.saturating_sub(1),
658                v: 1,
659                skip: c % 3 == 1,
660            }
661        } else {
662            // This is a special case. When `b == c` and `c % 3 > 0`, there is exactly one
663            // interior vertex, at (0, 0).
664            VertexIter {
665                sphere: self,
666                region,
667                u: (c % 3 == 0) as u32,
668                u_end: 1,
669                v: 0,
670                skip: c % 3 == 2,
671            }
672        }
673    }
674}
675
676/// An iterator over the vertices of an [`HexSphere`].
677#[derive(Clone, Debug)]
678pub struct VertexIter<Proj> {
679    sphere: HexSphere<Proj>,
680    region: BaseRegion,
681    u: u32,
682    u_end: u32,
683    v: u32,
684    skip: bool,
685}
686
687impl<Proj: Eq + Clone + BaseTriProjector> Iterator for VertexIter<Proj> {
688    type Item = Vertex<Proj>;
689    fn next(&mut self) -> Option<Vertex<Proj>> {
690        loop {
691            if self.u < self.u_end {
692                let res = Vertex::new(tri::Vertex {
693                    sphere: self.sphere.kis.clone(),
694                    region: self.region,
695                    u: self.u,
696                    v: self.v,
697                });
698                self.u += 1;
699                self.u += self.skip as u32;
700                self.skip = !self.skip;
701                return Some(res);
702            } else if self.region.ty().is_edge() {
703                if self.v < self.sphere.kis.c() {
704                    self.v += 1;
705                    (self.u, self.skip) = match self.v % 3 {
706                        0 => (1, false),
707                        1 => (2, false),
708                        _ => (1, true),
709                    };
710                    continue;
711                }
712            } else {
713                let n = self.sphere.kis.b() - self.sphere.kis.c();
714                if self.v + 1 < n {
715                    self.v += 1;
716                    self.u_end = n - self.v;
717                    (self.u, self.skip) = match (self.v + self.sphere.kis.c()) % 3 {
718                        0 => (1, false),
719                        1 => (2, false),
720                        _ => (1, true),
721                    };
722                    continue;
723                }
724            }
725            if let Some(region) = self.sphere.kis.base().next_region(self.region) {
726                *self = self.sphere.clone().vertices_from(region);
727                continue;
728            } else {
729                return None;
730            }
731        }
732    }
733}