Bezierize land outline
authorunc0rr
Tue, 06 Nov 2018 00:02:23 +0100
changeset 14161 3078123e84ea
parent 14160 37c99587825d
child 14162 477faa7b8a48
Bezierize land outline
rust/fpnum/src/lib.rs
rust/integral-geometry/src/lib.rs
rust/land2d/src/lib.rs
rust/landgen/src/outline.rs
rust/landgen/src/template_based.rs
--- a/rust/fpnum/src/lib.rs	Mon Nov 05 21:36:28 2018 +0100
+++ b/rust/fpnum/src/lib.rs	Tue Nov 06 00:02:23 2018 +0100
@@ -455,6 +455,17 @@
                           self.y().$name(rhs))
             }
         }
+    };
+    ($($op: tt)::+<$arg: tt>, $name: tt) => {
+        impl $($op)::+<$arg> for FPPoint {
+            type Output = Self;
+
+            #[inline]
+            fn $name(self, rhs: $arg) -> Self {
+                Self::new(self.x().$name(rhs),
+                          self.y().$name(rhs))
+            }
+        }
     }
 }
 
@@ -480,6 +491,7 @@
 right_scalar_bin_op_impl!(ops::Mul, mul);
 right_scalar_bin_op_impl!(ops::Sub, sub);
 right_scalar_bin_op_impl!(ops::Div, div);
+right_scalar_bin_op_impl!(ops::Div<u32>, div);
 left_scalar_bin_op_impl!(ops::Mul, mul);
 
 macro_rules! bin_assign_op_impl {
--- a/rust/integral-geometry/src/lib.rs	Mon Nov 05 21:36:28 2018 +0100
+++ b/rust/integral-geometry/src/lib.rs	Tue Nov 06 00:02:23 2018 +0100
@@ -3,8 +3,8 @@
 
 use fpnum::{distance, FPNum, FPPoint};
 use std::{
-    cmp::max,
-    ops::{Add, AddAssign, Div, DivAssign, Mul, MulAssign, Range, RangeInclusive, Sub, SubAssign}
+    cmp::{max, min},
+    ops::{Add, AddAssign, Div, DivAssign, Mul, MulAssign, Range, RangeInclusive, Sub, SubAssign},
 };
 
 #[derive(PartialEq, Eq, Clone, Copy, Debug)]
@@ -74,10 +74,7 @@
 
     #[inline]
     pub fn clamp(self, rect: &Rect) -> Point {
-        Point::new(
-            rect.x_range().clamp(self.x),
-            rect.y_range().clamp(self.y)
-        )
+        Point::new(rect.x_range().clamp(self.x), rect.y_range().clamp(self.y))
     }
 
     #[inline]
@@ -274,7 +271,10 @@
     pub fn new(top_left: Point, bottom_right: Point) -> Self {
         assert!(top_left.x <= bottom_right.x + 1);
         assert!(top_left.y <= bottom_right.y + 1);
-        Self { top_left, bottom_right }
+        Self {
+            top_left,
+            bottom_right,
+        }
     }
 
     pub fn from_box(left: i32, right: i32, top: i32, bottom: i32) -> Self {
@@ -284,7 +284,7 @@
     pub fn from_size(top_left: Point, size: Size) -> Self {
         Self::new(
             top_left,
-            top_left + Point::new(size.width as i32 - 1, size.height as i32 - 1)
+            top_left + Point::new(size.width as i32 - 1, size.height as i32 - 1),
         )
     }
 
@@ -354,10 +354,7 @@
     #[inline]
     pub fn with_margin(&self, margin: i32) -> Self {
         let offset = Point::diag(margin);
-        Self::new(
-            self.top_left() + offset,
-            self.bottom_right() - offset
-        )
+        Self::new(self.top_left() + offset, self.bottom_right() - offset)
     }
 
     #[inline]
@@ -404,11 +401,7 @@
 
     #[inline]
     pub fn quotient(self, x: usize, y: usize) -> Point {
-        self.top_left() +
-            Point::new(
-                (x % self.width()) as i32,
-                (y % self.height()) as i32
-            )
+        self.top_left() + Point::new((x % self.width()) as i32, (y % self.height()) as i32)
     }
 }
 
@@ -416,13 +409,13 @@
     fn contains(&self, value: T) -> bool;
 }
 
-impl <T: Ord> RangeContains<T> for Range<T> {
+impl<T: Ord> RangeContains<T> for Range<T> {
     fn contains(&self, value: T) -> bool {
         value >= self.start && value < self.end
     }
 }
 
-impl <T: Ord> RangeContains<T> for RangeInclusive<T> {
+impl<T: Ord> RangeContains<T> for RangeInclusive<T> {
     fn contains(&self, value: T) -> bool {
         value >= *self.start() && value <= *self.end()
     }
@@ -432,7 +425,7 @@
     fn clamp(&self, value: T) -> T;
 }
 
-impl <T: Ord + Copy> RangeClamp<T> for RangeInclusive<T> {
+impl<T: Ord + Copy> RangeClamp<T> for RangeInclusive<T> {
     fn clamp(&self, value: T) -> T {
         if value < *self.start() {
             *self.start()
@@ -479,7 +472,11 @@
         let edges_count = self.edges_count();
         let start = self.vertices.as_mut_ptr();
         let end = unsafe { start.add(self.vertices.len()) };
-        PolygonPointsIteratorMut { source: self, start, end }
+        PolygonPointsIteratorMut {
+            source: self,
+            start,
+            end,
+        }
     }
 
     fn force_close(&mut self) {
@@ -494,15 +491,66 @@
             .zip(&self.vertices[1..])
             .map(|(s, e)| Line::new(*s, *e))
     }
+
+    pub fn bezierize(&mut self, segments_number: u32) {
+        fn calc_point(p1: Point, p2: Point, p3: Point) -> FPPoint {
+            let diff13 = (p1 - p3).to_fppoint();
+            let diff13_norm = diff13.distance();
+
+            if diff13_norm.is_zero() {
+                diff13
+            } else {
+                let diff12_norm = (p1 - p2).to_fppoint().distance();
+                let diff23_norm = (p2 - p3).to_fppoint().distance();
+                let min_distance = min(diff13_norm, min(diff12_norm, diff23_norm));
+
+                diff13 * min_distance / diff13_norm / 3
+            }
+        }
+
+        if self.vertices.len() < 4 {
+            return;
+        }
+
+        let delta = fp!(1 / segments_number);
+        let mut bezierized_vertices = Vec::new();
+        let mut pi = 0;
+        let mut i = 1;
+        let mut ni = 2;
+        let mut right_point = calc_point(self.vertices[pi], self.vertices[i], self.vertices[ni]);
+        let mut left_point;
+
+        pi += 1;
+        while pi != 0 {
+            pi = i;
+            i = ni;
+            ni += 1;
+            if ni >= self.vertices.len() {
+                ni = 0;
+            }
+
+            left_point = right_point;
+            right_point = calc_point(self.vertices[pi], self.vertices[i], self.vertices[ni]);
+
+            bezierized_vertices.extend(BezierCurveSegments::new(
+                Line::new(self.vertices[pi], self.vertices[i]),
+                left_point,
+                -right_point,
+                delta,
+            ));
+        }
+
+        self.vertices = bezierized_vertices;
+    }
 }
 
 struct PolygonPointsIteratorMut<'a> {
     source: &'a mut Polygon,
     start: *mut Point,
-    end: *mut Point
+    end: *mut Point,
 }
 
-impl <'a> Iterator for PolygonPointsIteratorMut<'a> {
+impl<'a> Iterator for PolygonPointsIteratorMut<'a> {
     type Item = &'a mut Point;
 
     fn next(&mut self) -> Option<<Self as Iterator>::Item> {
@@ -518,7 +566,7 @@
     }
 }
 
-impl <'a> Drop for PolygonPointsIteratorMut<'a> {
+impl<'a> Drop for PolygonPointsIteratorMut<'a> {
     fn drop(&mut self) {
         self.source.force_close();
     }
@@ -537,7 +585,7 @@
 #[derive(PartialEq, Eq, Clone, Copy, Debug)]
 pub struct Ray {
     pub start: Point,
-    pub direction: Point
+    pub direction: Point,
 }
 
 impl Ray {
@@ -741,17 +789,21 @@
     c1: FPPoint,
     c2: FPPoint,
     offset: FPNum,
+    max_offset: FPNum,
     delta: FPNum,
+    have_finished: bool,
 }
 
 impl BezierCurveSegments {
-    pub fn new(segment: Line, p1: Point, p2: Point, delta: FPNum) -> Self {
+    pub fn new(segment: Line, p1: FPPoint, p2: FPPoint, delta: FPNum) -> Self {
         Self {
             segment,
-            c1: (segment.start - p1).to_fppoint(),
-            c2: (segment.end - p2).to_fppoint(),
+            c1: segment.start.to_fppoint() - p1,
+            c2: segment.end.to_fppoint() - p2,
             offset: fp!(0),
+            max_offset: fp!(4095 / 4096),
             delta,
+            have_finished: false,
         }
     }
 }
@@ -760,7 +812,7 @@
     type Item = Point;
 
     fn next(&mut self) -> Option<Self::Item> {
-        if self.offset < fp!(1) {
+        if self.offset < self.max_offset {
             let offset_sq = self.offset * self.offset;
             let offset_cub = offset_sq * self.offset;
 
@@ -780,6 +832,10 @@
             self.offset += self.delta;
 
             Some(Point::new(x.round(), y.round()))
+        } else if !self.have_finished {
+            self.have_finished = true;
+
+            Some(self.segment.end)
         } else {
             None
         }
--- a/rust/land2d/src/lib.rs	Mon Nov 05 21:36:28 2018 +0100
+++ b/rust/land2d/src/lib.rs	Tue Nov 06 00:02:23 2018 +0100
@@ -133,7 +133,7 @@
         ) {
             let yd = y as isize + dir;
 
-            if land.is_valid_coordinate(0, yd as i32) {
+            if land.is_valid_y(yd as i32) {
                 stack.push((xl, xr, yd as usize, dir));
             }
         };
--- a/rust/landgen/src/outline.rs	Mon Nov 05 21:36:28 2018 +0100
+++ b/rust/landgen/src/outline.rs	Tue Nov 06 00:02:23 2018 +0100
@@ -264,7 +264,11 @@
         }
     }
 
-    pub fn bezierize(&mut self) {}
+    pub fn bezierize(&mut self, segments_number: u32) {
+        for island in &mut self.islands {
+            island.bezierize(segments_number);
+        }
+    }
 
     pub fn distort<I: Iterator<Item = u32>>(
         &mut self,
--- a/rust/landgen/src/template_based.rs	Mon Nov 05 21:36:28 2018 +0100
+++ b/rust/landgen/src/template_based.rs	Tue Nov 06 00:02:23 2018 +0100
@@ -54,7 +54,7 @@
         }
 
         if !parameters.skip_bezier {
-            points.bezierize();
+            points.bezierize(5);
         }
 
         points.draw(&mut land, parameters.zero);