Geometry

From Bots-United Wiki

Jump to: navigation, search

Contents

Vector spaces

Coordinate systems

Line Equation

All points on a line can be described providing one point and the direction \overrightarrow{u}. Each point on the line can thus be described this way :

\overrightarrow{r} = \overrightarrow{r_0} + \mu \overrightarrow{u} with \mu \in \mathbb{R}

Plane Equations

parametric form

All points on a line can be descibed providing one point and two directions \overrightarrow{u} and Failed to parse (unknown error): \overrightarrow{v} . Each point on the line can thus be described this way :

Failed to parse (unknown error): \overrightarrow{r} = \overrightarrow{r_0} + \mu \overrightarrow{u} + \lambda \overrightarrow{v}
with \mu,\lambda \in \mathbb{R}

normal form

A plane can also be described by a scalar describing the distance to the origin and the normal vector Failed to parse (unknown error): \overrightarrow{n}

which is perpendicular to the plane and can easily be calculated using the cross product. ( in Failed to parse (unknown error): \mathbb{R}^3
)

Then each point Failed to parse (unknown error): \overrightarrow{r}

on the plane complies with the following equation :
Failed to parse (unknown error): \overrightarrow{r} \overrightarrow{n} = d


where d is the distance to the origin if |\overrightarrow{n}| = 1. In this case this is called the Hesse form of the plane.

Frequent Problems

line hitting line

line hitting a plane

Just take the equation of the line and the normal description of your plane.

\overrightarrow{r} = \overrightarrow{r_0} + \mu \overrightarrow{u} with \mu \in \mathbb{R}
Failed to parse (unknown error): \overrightarrow{r} \overrightarrow{n} = d


inserting the line equation into the equation of the plane you get

(\overrightarrow{r_0} + \mu \overrightarrow{u}) \overrightarrow{n} = d

which can be solved for μ. Then you can insert this μ to your equation of the line and you'll have the point where the plane is hit.

planes hitting each other

representing one plane using the parametric description and one using the normal description, things get really easy :

Failed to parse (unknown error): \overrightarrow{r} \overrightarrow{n} = d
Failed to parse (unknown error): \overrightarrow{r} = \overrightarrow{r_0} + \mu \overrightarrow{u} + \lambda \overrightarrow{v}
with \mu,\lambda \in \mathbb{R}

inserting the parametric form into the normal form we get

(\overrightarrow{r_0} + \mu \overrightarrow{u} + \lambda \overrightarrow{v}) \overrightarrow{n} = d

This way we have a linear equation, which can be solved for either λ or μ. inserting this value into the parametric form of the plane, we removed one degree of freedom, thus we have the equation of the line. Please take care of those cases where planes are parallel to each other, thus having Failed to parse (unknown error): \infty

or 0 points together.

On which side of the plane is a vector ?

If the vector Failed to parse (unknown error): \overrightarrow{r}

is on the side the normal vector is pointing to, we get
Failed to parse (unknown error): \overrightarrow{r} \overrightarrow{n} > d


otherwise

Failed to parse (unknown error): \overrightarrow{r} \overrightarrow{n} < d


Did a line hit a triangle ?

First you have to check if the line has a point where it hits the plane. Normally this is the case. In bot coding, you often want to determine if you hit the surface between 2 points, i.e. you have to check if one point is on another side of the plane than the other. Another problem is that you might not have a plane, but a polygon, or a triangle ( to which all polygons can be broken down ). This polygon is normally not infinite, therefore you also have to check if the hit point is within the triangle. This can be done in several ways :

Regarding Angles

The angles within a triangle have to sum up to Failed to parse (unknown error): \pi . You can calculate the angles by using the relation about the angle from the dot product. This is pretty cpu intense, because you need to do 6 vector additions, 6 normalizations, 3 dot products and 3 acos, which is a lot. You have to bear in mind, that you won't get exactly Failed to parse (unknown error): \pi

due to floating point rounding errors.

Regarding Orientation

You can also subdivide the triangle using the hit point as a point of the new 3 triangles. For each of those triangles you can calculate the normals and compare them using the dot-product. When they are all pointing to the same direction ( i.e. the dot product is always > 0 ), the hit point lies within the triangle. This method isn't much faster than the angle method, but you have less problems comparing the result with some value, and the result looks more precise to me.

Another possibility

... is described here. It's probably one of the fastest methods there is. C Source download-able, just a couple of lines.

Angles between Planes

Using the relation from the dot product : Failed to parse (unknown error): \overrightarrow{A} . \overrightarrow{B} = |\overrightarrow{A}| |\overrightarrow{B}| cos \alpha

and applying this to the normal vectors of your planes, you can easily determine Failed to parse (unknown error): \alpha