use crate::nalgebra::{center, Isometry2, Point2, Vector2, Vector3};
use bevy::prelude::Mesh;
use bevy_rapier2d::prelude::*;
use rand::prelude::*;
use std::collections::HashSet;
pub fn generate_random_mesh(
num_of_verticles: u16,
max_distance_from_verticles: f32,
max_distance_to_create_triangle: f32,
) -> Result<Mesh, &'static str> {
if num_of_verticles < 3 {
return Err("Number of verticles should be greater than 3!");
}
// list of verticles
let mut verts = Vec::new();
// list of indices
let mut indices: Vec<[usize; 3]> = Vec::new();
// list of edges, contains points of edges, verts and middle point
let mut edges: Vec<([Point2<f32>; 2], [usize; 2], Point2<f32>)> = Vec::new();
//first vert
verts.push(Point2::new(0.0, 0.0));
//second vert
verts.push(generate_random_point_in_a_circle(
max_distance_from_verticles,
));
//third vert
let last_verticle = verts.last().expect("wtf").clone();
let random_point = generate_random_point_in_a_circle(max_distance_from_verticles);
verts.push(last_verticle + Vector2::new(random_point.x, random_point.y));
//first triangle has been created, push indices
indices.push([0, 1, 2]);
//push edges for later
edges.push(([verts[0], verts[1]], [0, 1], center(&verts[0], &verts[1])));
edges.push(([verts[1], verts[2]], [1, 2], center(&verts[1], &verts[2])));
edges.push(([verts[2], verts[0]], [2, 0], center(&verts[2], &verts[0])));
//rng
let mut rng = rand::thread_rng();
let mut current_num_of_verticles = 3;
//creating rest of the verticles
while current_num_of_verticles < num_of_verticles {
use rand::seq::SliceRandom;
//randomly choosing one edge from verticles
let random_edge: ([Point2<f32>; 2], [usize; 2], Point2<f32>) =
*edges.choose(&mut rng).unwrap();
//generating middle point of the selected edge
let middle_of_the_edge = Vector2::new(random_edge.2.x, random_edge.2.y);
//randomly tries n times to choose new verticle
for _ebe in 0..5 {
//generate new verticle by randomly translating the middle of the edge choosen
let random_point = Point2::new(0.0, 0.0)/*generate_random_point_in_a_circle(max_distance_from_verticles)*/ + middle_of_the_edge + (perpendicular_vector(&random_edge.0[0], &random_edge.0[1])*(max_distance_from_verticles));
//checking if this verticle is inside already generated triangles
let is_inside = indices.iter().fold(false, |acc, curr_triangle| {
acc || point_in_triangle(
&random_point,
&verts[curr_triangle[0]],
&verts[curr_triangle[1]],
&verts[curr_triangle[2]],
)
});
//if point is not inside, then we create new triangle from this point and nearest edges
if !is_inside {
let mut new_vert_added = false;
//iter of distances from new verticle to nearest edges
let mut distances: Vec<(usize, f32)> = edges
.iter()
.map(|edge| crate::nalgebra::distance(&edge.2, &random_point))
.enumerate()
.filter(|distance| distance.1 < max_distance_to_create_triangle)
.collect();
distances.sort_by(|a, b| a.1.partial_cmp(&b.1).unwrap());
let potential_edges: Vec<([Point2<f32>; 2], [usize; 2], Point2<f32>)> =
distances.iter().map(|distance| edges[distance.0]).collect();
//distances.sort_by(|a, b| a.1.partial_cmp(&b.1).unwrap());
//now we have set of edges with whom create new triangles to the newly created verticle
//We can create new triangle only if its two new edges do not intersect existing edges
for potential_edge in potential_edges {
//checks if first possible edge intersects existing edges
let first_edge_intersect = edges.iter().fold(false, |acc, curr_edge| {
acc || line_intersection_test(
&random_point,
&potential_edge.0[0],
&curr_edge.0[0],
&curr_edge.0[1],
)
});
//println!("1: {:?} 2: {:?} 3: {?} 4: {?}", random_point, potential_edge.0[0]);
if !first_edge_intersect {
//println!("dont intersect");
//checks if second possible edge intersects
let second_edge_intersect = edges.iter().fold(false, |acc, curr_edge| {
acc || line_intersection_test(
&random_point,
&potential_edge.0[1],
&curr_edge.0[0],
&curr_edge.0[1],
)
});
if !second_edge_intersect {
//Two potential edges do not intersect, add new triangle to the mesh
//add new verticle
if !new_vert_added {
verts.push(random_point);
current_num_of_verticles += 1;
new_vert_added = true;
}
//add indices
indices.push([
potential_edge.1[0],
potential_edge.1[1],
verts.len() - 1,
]);
//add to edges lists
edges.push((
[verts[verts.len() - 1], verts[potential_edge.1[0]]],
[verts.len() - 1, potential_edge.1[0]],
center(&verts[verts.len() - 1], &potential_edge.0[0]),
));
edges.push((
[verts[verts.len() - 1], verts[potential_edge.1[1]]],
[verts.len() - 1, potential_edge.1[1]],
center(&verts[verts.len() - 1], &potential_edge.0[1]),
));
}
}
}
break;
} else {
println!("INSIDE");
}
}
}
//now we have all verts and all triangle indices, generating mesh
let mut mesh = Mesh::new(bevy::render::pipeline::PrimitiveTopology::LineList);
let v_pos: Vec<[f32; 2]> = verts.iter().map(|point| [point.x, point.y]).collect();
mesh.set_attribute(Mesh::ATTRIBUTE_POSITION, v_pos);
let v_normal = vec![[0.0, 0.0, 1.0]; verts.len()];
mesh.set_attribute("Vertex_Normal", v_normal);
let uv = vec![[0.5, 0.5]; verts.len()];
mesh.set_attribute("Vertex_Uv", uv);
//let indices = indices.iter().flat_map(|tup| [tup.0 as u32, tup.1 as u32, tup.2 as u32].iter().cloned()).collect();
//let indices = indices.iter().fold(Vec::with_capacity(indices.len() * 3),
//|mut acc, p| { acc.extend(&[p.0 as u32, p.1 as u32, p.2 as u32]); acc });
/*let mut final_indices = Vec::with_capacity(indices.len() * 3);
for indice in indices {
if is_triangle_ccw(&verts[indice[0]], &verts[indice[1]], &verts[indice[2]]) {
final_indices.push(indice[0] as u32);
final_indices.push(indice[1] as u32);
final_indices.push(indice[2] as u32);
} else {
final_indices.push(indice[2] as u32);
final_indices.push(indice[1] as u32);
final_indices.push(indice[0] as u32);
}
}*/
let mut final_indices = Vec::with_capacity(indices.len() * 6);
for edge in edges {
final_indices.push(edge.1[0] as u32);
final_indices.push(edge.1[1] as u32);
}
mesh.set_indices(Some(bevy::render::mesh::Indices::U32(final_indices)));
Ok(mesh)
}
pub fn generate_random_mesh2(
num_of_verticles: u16,
max_distance_from_verticles: f32,
max_distance_to_create_triangle: f32,
) -> Result<(Mesh, Vec<Point2<f32>>), &'static str> {
// list of verticles
let mut verts = Vec::new();
// list of indices
let mut indices: Vec<[usize; 3]> = Vec::new();
// list of edges, contains points of edges, verts and middle point
let mut edges2: Vec<[usize; 2]> = Vec::new();
// list of outer indices, to which outer edges from edges2 belong
let mut indices: Vec<[usize; 3]> = Vec::new();
//rng
let mut rng = rand::thread_rng();
//first vert
verts.push(Point2::new(0.0, 0.0));
//second vert
verts.push(Point2::new(max_distance_from_verticles, 0.0));
//third vert
verts.push(Point2::new(
max_distance_from_verticles / 2.0,
max_distance_from_verticles * 0.86602,
));
//first triangle has been created, push indices
indices.push([0, 1, 2]);
//push edges for later
edges2.push([0, 1]);
edges2.push([1, 2]);
edges2.push([2, 0]);
//rng
let mut rng = rand::thread_rng();
let mut current_num_of_verticles = 3;
//creating rest of the verticles
while current_num_of_verticles < num_of_verticles {
//randomly choosing one edge from verticles
let random_edge_index = (rand::random::<f32>() * edges2.len() as f32).floor() as usize;
let random_edge = edges2[random_edge_index];
let mut new_vert = center(&verts[random_edge[0]], &verts[random_edge[1]])
+ (perpendicular_vector(&verts[random_edge[0]], &verts[random_edge[1]])
* (max_distance_from_verticles * 0.86602));
let mut new_vert_index = verts.len();
let mut distances: Vec<(usize, f32)> = verts
.iter()
.map(|vert| crate::nalgebra::distance(&vert, &new_vert))
.enumerate()
.filter(|distance| distance.1 < 0.0001)
.collect();
if distances.len() == 1 {
//println!("eee");
new_vert = verts[distances[0].0];
new_vert_index = distances[0].0;
edges2.remove(random_edge_index);
//println!("{:?}, {:?}, {:?}", new_vert, verts[random_edge[0]], verts[random_edge[1]]);
let first_edge = [new_vert_index, random_edge[1]];
if let Some(index) = edges2
.iter()
.position(|edge| *edge == [random_edge[1], new_vert_index])
{
edges2.remove(index);
} else {
edges2.push(first_edge);
}
let second_edge = [random_edge[0], new_vert_index];
if let Some(index) = edges2
.iter()
.position(|edge| *edge == [new_vert_index, random_edge[0]])
{
edges2.remove(index);
} else {
edges2.push(second_edge);
}
indices.push([random_edge[1], random_edge[0], new_vert_index]);
//current_num_of_verticles = num_of_verticles;
} else {
verts.push(new_vert);
let first_edge = [new_vert_index, random_edge[1]];
let second_edge = [random_edge[0], new_vert_index];
edges2.push(first_edge);
edges2.push(second_edge);
indices.push([random_edge[1], random_edge[0], new_vert_index]);
edges2.remove(random_edge_index);
}
current_num_of_verticles += 1;
}
//softing edge
let mut random_edge_index = 0;
while random_edge_index < edges2.len() {
let random_edge = edges2[random_edge_index];
let mut new_vert = center(&verts[random_edge[0]], &verts[random_edge[1]])
+ (perpendicular_vector(&verts[random_edge[0]], &verts[random_edge[1]])
* (max_distance_from_verticles * 0.86602));
let mut distances: Vec<(usize, f32)> = verts
.iter()
.map(|vert| crate::nalgebra::distance(&vert, &new_vert))
.enumerate()
.filter(|distance| distance.1 < 0.0001)
.collect();
let mut new_vert_index = verts.len();
if distances.len() == 1 {
//println!("eee");
new_vert = verts[distances[0].0];
new_vert_index = distances[0].0;
edges2.remove(random_edge_index);
//println!("{:?}, {:?}, {:?}", new_vert, verts[random_edge[0]], verts[random_edge[1]]);
let first_edge = [new_vert_index, random_edge[1]];
if let Some(index) = edges2
.iter()
.position(|edge| *edge == [random_edge[1], new_vert_index])
{
edges2.remove(index);
} else {
edges2.push(first_edge);
}
let second_edge = [random_edge[0], new_vert_index];
if let Some(index) = edges2
.iter()
.position(|edge| *edge == [new_vert_index, random_edge[0]])
{
edges2.remove(index);
} else {
edges2.push(second_edge);
}
indices.push([random_edge[1], random_edge[0], new_vert_index]);
//current_num_of_verticles = num_of_verticles;
}
random_edge_index += 1;
}
let mut random_edge_index = 0;
while random_edge_index < edges2.len() {
let random_edge = edges2[random_edge_index];
let mut new_vert = center(&verts[random_edge[0]], &verts[random_edge[1]])
+ (perpendicular_vector(&verts[random_edge[0]], &verts[random_edge[1]])
* (max_distance_from_verticles * 0.86602));
let mut distances: Vec<(usize, f32)> = verts
.iter()
.map(|vert| crate::nalgebra::distance(&vert, &new_vert))
.enumerate()
.filter(|distance| distance.1 < 0.0001)
.collect();
let mut new_vert_index = verts.len();
if distances.len() == 1 {
//println!("eee");
new_vert = verts[distances[0].0];
new_vert_index = distances[0].0;
edges2.remove(random_edge_index);
//println!("{:?}, {:?}, {:?}", new_vert, verts[random_edge[0]], verts[random_edge[1]]);
let first_edge = [new_vert_index, random_edge[1]];
if let Some(index) = edges2
.iter()
.position(|edge| *edge == [random_edge[1], new_vert_index])
{
edges2.remove(index);
} else {
edges2.push(first_edge);
}
let second_edge = [random_edge[0], new_vert_index];
if let Some(index) = edges2
.iter()
.position(|edge| *edge == [new_vert_index, random_edge[0]])
{
edges2.remove(index);
} else {
edges2.push(second_edge);
}
indices.push([random_edge[1], random_edge[0], new_vert_index]);
//current_num_of_verticles = num_of_verticles;
}
random_edge_index += 1;
}
/*let mut random_edge_index = 0;
while random_edge_index < edges2.len() {
let first_edge = edges2[random_edge_index];
let second_edge = edges2[random_edge_index];
let first_point = verts[first_edge[0]];
let second_point = verts[second_edge[1]];
let dist = crate::nalgebra::distance(&first_point, &second_point);
if dist < max_distance_from_verticles+0.01 {
let index = indices.iter().position(|indice| (*indice == [first_edge[0], first_edge[1], second_edge[1]]) || (*indice == [second_edge[1], first_edge[0], first_edge[1]]) || (*indice == [first_edge[1], second_edge[1], first_edge[0]]));
if let Some(i) = index {
indices.remove(i);
}
}
random_edge_index += 1;
}
let mut random_edge_index = 0;
while random_edge_index < edges2.len() {
let first_edge = edges2[random_edge_index];
let second_edge = edges2[random_edge_index];
let first_point = verts[first_edge[0]];
let second_point = verts[second_edge[1]];
let dist = crate::nalgebra::distance(&first_point, &second_point);
if dist < max_distance_from_verticles+0.01 {
let index = indices.iter().position(|indice| (*indice == [first_edge[0], first_edge[1], second_edge[1]]) || (*indice == [second_edge[1], first_edge[0], first_edge[1]]) || (*indice == [first_edge[1], second_edge[1], first_edge[0]]));
if let Some(i) = index {
indices.remove(i);
}
}
random_edge_index += 1;
}*/
//now we have all verts and all triangle indices, generating mesh
//randomly translate verts
//let verts: Vec<Point2<f32>> = verts.iter().map(|vert| vert+point2vec(generate_random_point_in_a_circle(max_distance_from_verticles/8.0)) ).collect();
//let mut mesh = Mesh::new(bevy::render::pipeline::PrimitiveTopology::LineList);
let mut mesh = Mesh::new(bevy::render::pipeline::PrimitiveTopology::TriangleList);
let v_pos: Vec<[f32; 3]> = verts.iter().map(|point| [point.x, point.y, 0.0]).collect();
mesh.set_attribute(Mesh::ATTRIBUTE_POSITION, v_pos);
let v_normal = vec![[0.0, 0.0, 1.0]; verts.len()];
mesh.set_attribute("Vertex_Normal", v_normal);
let uv = vec![[0.5, 0.5]; verts.len()];
mesh.set_attribute("Vertex_Uv", uv);
let mut final_indices = Vec::with_capacity(indices.len() * 6);
for indice in &indices {
final_indices.push(indice[0] as u32);
final_indices.push(indice[1] as u32);
final_indices.push(indice[2] as u32);
}
mesh.set_indices(Some(bevy::render::mesh::Indices::U32(final_indices)));
let final_outline = edges2.iter().fold(Vec::new(), |mut acc, curr_edge| {
acc.push(verts[curr_edge[0] as usize]);
acc.push(verts[curr_edge[1] as usize]);
acc
});
Ok((mesh, final_outline))
}
pub fn generate_shape_collider_from_mesh(mesh: &Mesh) -> Option<SharedShape> {
let points = match mesh.attribute(Mesh::ATTRIBUTE_POSITION).unwrap() {
bevy::render::mesh::VertexAttributeValues::Float3(verts) => verts
.iter()
.map(|vert| nalgebra::Point2::new(vert[0], vert[1]))
.collect(),
_ => {
panic!("U SUK");
vec![]
}
};
/*let new_indices = match mesh.indices().unwrap() {
bevy::render::mesh::Indices::U32(indices) => {
indices
.iter()
.zip(indices.iter().skip(1))
.map(|tuple| [tuple.0.clone(), tuple.1.clone()])
//.inspect(|(a, b)| println!("a: {}, b: {}", a, b)
.collect::<Vec<_>>()
}
_ => {panic!("U SUK")}
};*/
let indices = match mesh.indices().unwrap() {
bevy::render::mesh::Indices::U32(indices) => indices,
_ => {
panic!("U SUK")
}
};
let positions_and_shapes: Vec<(Isometry2<f32>, SharedShape)> = indices
.chunks(3)
//.inspect(|chunk| println!("{} {} {}", points[chunk[0] as usize], points[chunk[1] as usize], points[chunk[2] as usize]))
.map(|indice| {
(
Isometry2::new(Vector2::new(0.0, 0.0), 0.0),
ColliderShape::convex_polyline(vec![
points[indice[0] as usize],
points[indice[1] as usize],
points[indice[2] as usize],
])
.unwrap(),
)
})
.collect();
//println!("{}", positions_and_shapes.len());
Some(ColliderShape::compound(positions_and_shapes))
//Some(ColliderShape::convex_decomposition(&points, &*new_indices))
//ColliderShape::convex_hull(&points)
}
/*pub fn generate_shape_collider_from_outline(outline: &Vec<Point2<f32>>) -> Option<SharedShape> {
}*/
pub fn point2vec(point: Point2<f32>) -> Vector2<f32> {
Vector2::new(point.x, point.y)
}
pub fn generate_middle_point_of_triangle(
vert1: &Point2<f32>,
vert2: &Point2<f32>,
vert3: &Point2<f32>,
) -> Vector2<f32> {
(Vector2::new(vert1.x, vert1.y)
+ Vector2::new(vert2.x, vert2.y)
+ Vector2::new(vert3.x, vert3.y))
/ 3.0
}
pub fn generate_random_point_in_a_circle(radius: f32) -> Point2<f32> {
let mut rng = thread_rng();
let r = radius * rng.gen::<f32>().sqrt();
let theta = rng.gen::<f32>() * 2.0 * std::f32::consts::PI;
//converting to Cartesian
let x = r * theta.cos();
let y = r * theta.sin();
Point2::new(x, y)
}
pub fn sign_of_point(point: &Point2<f32>, vert1: &Point2<f32>, vert2: &Point2<f32>) -> f32 {
(point.x - vert2.x) * (vert1.y - vert2.y) - (vert1.x - vert2.x) * (point.y - vert2.y)
}
pub fn point_in_triangle(
point: &Point2<f32>,
vert1: &Point2<f32>,
vert2: &Point2<f32>,
vert3: &Point2<f32>,
) -> bool {
let d1 = sign_of_point(point, vert1, vert2);
let d2 = sign_of_point(point, vert2, vert3);
let d3 = sign_of_point(point, vert3, vert1);
let has_neg = (d1 < 0.0) || (d2 < 0.0) || (d3 < 0.0);
let has_pos = (d1 > 0.0) || (d2 > 0.0) || (d3 > 0.0);
!(has_neg && has_pos)
}
pub fn is_triangle_ccw(vert1: &Point2<f32>, vert2: &Point2<f32>, vert3: &Point2<f32>) -> bool {
let first_vector = Vector3::from(*vert2) - Vector3::from(*vert1);
let second_vector = Vector3::from(*vert2) - Vector3::from(*vert3);
first_vector.cross(&second_vector)[2] < 0.0
}
pub fn cross2d(first_vector2: &Vector2<f32>, second_vector2: &Vector2<f32>) -> f32 {
(first_vector2.x * second_vector2.y) - (first_vector2.y * second_vector2.x)
}
pub fn vector2_div2scalar(first_vector2: &Vector2<f32>, second_vector2: &Vector2<f32>) -> f32 {
first_vector2.y / second_vector2.y
}
pub fn perpendicular_vector(first_point: &Point2<f32>, second_point: &Point2<f32>) -> Vector2<f32> {
let vector =
Vector2::new(first_point.x, first_point.y) - Vector2::new(second_point.x, second_point.y);
-Vector2::new(vector.y, -vector.x).normalize()
}
//If True, then lines intersect or are collinear
pub fn line_intersection_test(
first_line_start: &Point2<f32>,
first_line_end: &Point2<f32>,
second_line_start: &Point2<f32>,
second_line_end: &Point2<f32>,
) -> bool {
let p = Vector2::new(first_line_start.x, first_line_start.y);
let r = Vector2::new(first_line_end.x, first_line_end.y) - p;
let q = Vector2::new(second_line_start.x, second_line_start.y);
let s = Vector2::new(second_line_end.x, second_line_end.y) - q;
let det_numerator = cross2d(&(q - p), &(r));
let det_denominator = cross2d(&r, &s);
if det_denominator == 0.0 {
if det_numerator == 0.0 {
//collinear
true
} else {
//parallel, not intersecting
false
}
} else {
let u = det_numerator / det_denominator;
if u < 0.99 && u > 0.01 {
let t = cross2d(&(q - p), &(s)) / det_denominator;
if t < 0.99 && t > 0.01 {
true
} else {
false
}
} else {
false
}
}
}
#[cfg(test)]
mod tests {
use super::*;
#[test]
fn itersection_test() {
let first_point = Point2::new(0.0, 0.0);
let second_point = Point2::new(1.0, 0.0);
let third_point = Point2::new(0.0, 1.0);
let fourth_point = Point2::new(1.0, 1.0);
//collinear
assert_eq!(
true,
line_intersection_test(&first_point, &second_point, &first_point, &second_point)
);
//parallel, not intersecting
assert_eq!(
false,
line_intersection_test(&first_point, &second_point, &third_point, &fourth_point)
);
//intersection
assert_eq!(
true,
line_intersection_test(&first_point, &fourth_point, &third_point, &second_point)
);
//intersection
assert_eq!(
true,
line_intersection_test(&fourth_point, &first_point, &third_point, &second_point)
);
//intersection
assert_eq!(
true,
line_intersection_test(&first_point, &fourth_point, &second_point, &third_point)
);
//intersection
assert_eq!(
true,
line_intersection_test(&fourth_point, &first_point, &second_point, &third_point)
);
//not parallel, not intersect
assert_eq!(
false,
line_intersection_test(
&first_point,
&second_point,
&third_point,
&Point2::new(1.0, 0.5)
)
);
}
#[test]
fn point_in_triangle_test() {
let first_vert = Point2::new(0.0, 0.0);
let second_vert = Point2::new(1.0, 0.0);
let third_vert = Point2::new(0.0, 1.0);
let point = Point2::new(0.5, 0.5);
let outside_point = Point2::new(1.0, 1.0);
assert_eq!(
true,
point_in_triangle(&point, &first_vert, &second_vert, &third_vert)
);
assert_eq!(
true,
point_in_triangle(&point, &first_vert, &third_vert, &second_vert)
);
assert_eq!(
true,
point_in_triangle(&point, &second_vert, &first_vert, &third_vert)
);
assert_eq!(
true,
point_in_triangle(&point, &second_vert, &third_vert, &first_vert)
);
assert_eq!(
true,
point_in_triangle(&point, &third_vert, &first_vert, &second_vert)
);
assert_eq!(
true,
point_in_triangle(&point, &third_vert, &second_vert, &first_vert)
);
assert_eq!(
false,
point_in_triangle(&outside_point, &first_vert, &second_vert, &third_vert)
);
assert_eq!(
false,
point_in_triangle(&outside_point, &first_vert, &third_vert, &second_vert)
);
assert_eq!(
false,
point_in_triangle(&outside_point, &second_vert, &first_vert, &third_vert)
);
assert_eq!(
false,
point_in_triangle(&outside_point, &second_vert, &third_vert, &first_vert)
);
assert_eq!(
false,
point_in_triangle(&outside_point, &third_vert, &first_vert, &second_vert)
);
assert_eq!(
false,
point_in_triangle(&outside_point, &third_vert, &second_vert, &first_vert)
);
}
}