Geometry
From Bots-United Wiki
Contents |
Vector spaces
Coordinate systems
Line Equation
All points on a line can be described providing one point and the direction . Each point on the line can thus be described this way :
with
Plane Equations
parametric form
All points on a line can be descibed providing one point and two directions 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![]()
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 . 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.
with
- Failed to parse (unknown error): \overrightarrow{r} \overrightarrow{n} = d
inserting the line equation into the equation of the plane you get
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![]()
inserting the parametric form into the normal form we get
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