Introduction

Math is fun, especially if you can use the math to solve problems you have. In this tutorial you will learn how to use math to solve problems in Unity. This area is often called Computational Geometry, so if you want to learn more you should read the book Computational Geometry: Algorithms and Applications.

Here you will learn how to solve the following problems:

How to figure out if an enemy is in front or behind you? If you are following a series of waypoints how do you know if you have passed a waypoint? If you are steering towards a waypoint, how do you determine if you should steer left or right? You will also learn if you should turn left or right to reach a direction. How can you find the coordinate where a ray intersects with a plane? How can you tell if two line segments in 2D space intersect? Are two triangles in 2D space intersecting? Are two rectangles with orientation in 2D space intersecting? How can you find the convex hull of random points? A bunch of useful algorithms, such as if a point is to the left, to the right, or on the line between two points. How to triangulate polygons and random points? How to make good looking triangles with the Delaunay Triangulation algorithm? How to cut polygons and do boolean operations on polygons? How to create a Voronoi diagram? How can I cut a hole in a triangulation with the Constrained Delaunay Triangulation algorithm?

Data structures

In some tutorials I will use classes to store positions like Vector3 and edges. Some algorithms require that you store everything as a Doubly connected edge list. So its easier to display them once in the beginning than in each tutorial.

using System.Collections; using System.Collections.Generic; using UnityEngine; public class Vertex { public Vector3 position; //The outgoing halfedge (a halfedge that starts at this vertex) //Doesnt matter which edge we connect to it public HalfEdge halfEdge; //Which triangle is this vertex a part of? public Triangle triangle; //The previous and next vertex this vertex is attached to public Vertex prevVertex; public Vertex nextVertex; //Properties this vertex may have //Reflex is concave public bool isReflex; public bool isConvex; public bool isEar; public Vertex(Vector3 position) { this.position = position; } //Get 2d pos of this vertex public Vector2 GetPos2D_XZ() { Vector2 pos_2d_xz = new Vector2(position.x, position.z); return pos_2d_xz; } }

using System.Collections; using System.Collections.Generic; using UnityEngine; public class HalfEdge { //The vertex the edge points to public Vertex v; //The face this edge is a part of public Triangle t; //The next edge public HalfEdge nextEdge; //The previous public HalfEdge prevEdge; //The edge going in the opposite direction public HalfEdge oppositeEdge; //This structure assumes we have a vertex class with a reference to a half edge going from that vertex //and a face (triangle) class with a reference to a half edge which is a part of this face public HalfEdge(Vertex v) { this.v = v; } }

using System.Collections; using System.Collections.Generic; using UnityEngine; public class Triangle { //Corners public Vertex v1; public Vertex v2; public Vertex v3; //If we are using the half edge mesh structure, we just need one half edge public HalfEdge halfEdge; public Triangle(Vertex v1, Vertex v2, Vertex v3) { this.v1 = v1; this.v2 = v2; this.v3 = v3; } public Triangle(Vector3 v1, Vector3 v2, Vector3 v3) { this.v1 = new Vertex(v1); this.v2 = new Vertex(v2); this.v3 = new Vertex(v3); } public Triangle(HalfEdge halfEdge) { this.halfEdge = halfEdge; } //Change orientation of triangle from cw -> ccw or ccw -> cw public void ChangeOrientation() { Vertex temp = this.v1; this.v1 = this.v2; this.v2 = temp; } }

using System.Collections; using System.Collections.Generic; using UnityEngine; //And edge between two vertices public class Edge { public Vertex v1; public Vertex v2; //Is this edge intersecting with another edge? public bool isIntersecting = false; public Edge(Vertex v1, Vertex v2) { this.v1 = v1; this.v2 = v2; } public Edge(Vector3 v1, Vector3 v2) { this.v1 = new Vertex(v1); this.v2 = new Vertex(v2); } //Get vertex in 2d space (assuming x, z) public Vector2 GetVertex2D(Vertex v) { return new Vector2(v.position.x, v.position.z); } //Flip edge public void FlipEdge() { Vertex temp = v1; v1 = v2; v2 = temp; } }

using System.Collections; using System.Collections.Generic; using UnityEngine; public class Plane { public Vector3 pos; public Vector3 normal; public Plane(Vector3 pos, Vector3 normal) { this.pos = pos; this.normal = normal; } }

Back