MIRA
Geometry

# Contents

This document acts as a user manual. For further details on design requirements see Geometry (Requirements). These requirements lead to design decisions made within the geometry module.

# What is the geometry module?

The geometry module is a loose collection of geometry primitives like points (see mira::Point), lines (mira::Line), triangles (mira::createTriangle), and polygons (mira::Polygon3f). These primitives are all realized as template classes where you can define the required dimension and also the data type like int, float or double. The most common 2D and 3D data types are already defined.

These abstract data types can be used to perform intersections, unions, distance tests and etc.

Within the geometry module, also rasterization of geometric 2D primitives is supported (details see Rasterization). The rasterization concept is not only used to draw these primitives (this is better done with openCV), but can be used to implement other operations, like integration, min-max-search , blending operations, collision test etc.

Note that the geometry module only provides multidimensional primitives, it does not support the definition of complex 3D meshes like cylinder, torus, chamfer boxes or any other objects known from 3D modelling tools.

# The geometry foundations

Basic operations like geometric intersections, unions, distances are provided by the boost::geometry library. For a detailed description of possibilities:

http://geometrylibrary.geodan.nl/

MIRA's collection of geometric primitives ensures not only compatibility towards the boost component but also most data types can be converted to the Eigen Math framework, which is extensivly used within MIRA. Also compatibility towards the OpenCV library is ensured on the point class. Therefore, it should be no problem to draw lines and points with the openCV. All other primitives have to use the rasterization algorithms provided here to work with openCV or have to be converted point-wise to openCV primitives.

# Getting started

The <geometry/geometry.h> header provides all the functionalites of the MIRA geometry module.

## Points

Points are derived from Eigen::Matrix, consisting of one column and N rows. To learn more about the capabilities of the Eigen::Matrix, see

http://eigen.tuxfamily.org/dox/index.html

The Point base class takes a member type and a dimension (number of elements) as template parameters:

mira::Point<unsigned short, 10> d; //a point in a 10-dimensional space

Some frequently used Point types are pre-defined (2D and 3D, integer, float and double members):

Point2i a(3,4); // a 2D integer point
Point2f b(1.5f,2.f); // a 2D float point
Point2d b(1.5,2.0); // a 2D double point
Point3i c(1,2,3); // a 3D integer point
Point3f c(1.5f,2.f,-2.f); // a 3D float point
Point3d c(1.5,2.0,-2.0); // a 3D double point

Point members can be accessed either using the ()- or [] operator:

a = 2;
a = a;
b(0) = 3.0;
b(1) = a(1);

For the 2D and 3D variants, the special members x(), y() and z() are defined, referring to the first, second and third element, respectively (A.x() is equivalent to A etc.).

b.x() = a.x();
a.y() = a.y();
c.z() = d;

## Lines

The Line class does not represent one straight line, but a sequence of two or more points defining a sequence of line segments. Internally, it is realized as a vector of points, a so-called line string. This line string can be accessed like std::vector.

Like points, special line types can be defined with a base type and a dimension.

mira::Line<float, 3> l; //a line in 3D

As for points, there are a predefined line types for lines in 2D and 3D, integer, float and double spaces.

Point2i start(0,0);
Point2i end(3,3);
Point2i middle(1,2);
Line2i line1(start,end); // create the first line segment
std::vector<Point2i>::iterator it = line1.begin(); it++; // go behind first point
line1.insert(it,middle); // insert the middle point between start and end
line1.push_back(Point2i(4,4)); // add an extra point at the very end

For a line with one segment only (two points), boost::geometry::segment<PointType> can be used as alternative.

If only a line with 2 points is needed, a line segment will be used. There are also predefined segment types for 2D and 3D data, but also own types can be defined. The benefit of line segment is also the easy access.

LineSegment3f line1;
boost::geometry::segment<Point2f> myVeryShortLine(Point2f(1.0,1.0),Point2f(5.0,1.0));

## Rectangles

The Rect class and its specializations can be used to represent rectangular boxes in arbitrary dimension (rectangle, cuboid, hyper-cuboid). All these structures have in common that they can be defined by two corner points.

mira::Rect<float, 3> r; // a rectangle (box) in 3D, default-constructed = invalid state

Again, there are predefined data types for 2D and 3D cases.

Point3i minCorner(0,0,0);
// constructs a 3d box with the lower corner at 0,0,0 with width,height and depth of 10
Box3i b(minCorner, 10,10,10);

Access is easy, since only the min-corner and max-corner can be accessed.

Point3i min = a.minCorner;
Point3i max = a.maxCorner;

You can get also get the size of a rect / box by calling:

Size3i = a.size();

## Size

The size is a simple container, defining a (multidimensional) rectangular region or bounding box around a geometric primitive. In the 2D case you can access the width and height using mira::Size<T,2>::width() and mira::Size<T,2>::height(). The 3D case also supports mira::Size<T,3>::depth(). In any other case you can access the size along one dimension by using the dimension index.

Point<float,5> minP;
Point<float,5> maxP;
minP = 0.0; minP = 0.0; minP = 0.0; minP = 0.0; minP = 0.0;
maxP = 10.0; maxP = 10.0; maxP = 10.0; maxP = 10.0; maxP = 10.0;
Rect<float,5> rect(minP, maxP);
Size<float,5> size = rect.size();
std::cout << size << std::endl;

## Polygon

Polygons are well known constructs in computer graphics. In principal they are almost like line strings, but closed, so the first and last point are the same. So in 2D this construct has an area and also can have holes. This is defined in the boost::geometry::polygon class, here each polygon has an outer ring (a closed linestring) and can have many inner rings. Refer to

http://geometrylibrary.geodan.nl/classboost_1_1geometry_1_1polygon.html

to get more details on polygons and their usage.

## Important note

Note that high dimensional geometric primitives cannot be processed by boost::geometry intersection or union operands, since each union, intersection is specialized to one dimension and today only traits for 2D are existing. You will get an error if you try.

# Type conversions

## Points

Points can be converted to boost::geometry::point using

Point3f A(1,1,1);
boost::geometry::point<float,3,boost::geometry::cs::cartesian> B = A;

Since they are naturally Eigen matrices, no conversion to Eigen is needed. 2D and 3D Points have special conversion operators, allowing to convert also to OpenCV Point types.

Point3f A(1,1,1);
Point2f B(1,1);
cv::Point_<float> C = B;
cv::Point3_<float> D = A;

You can use all functionalities provided by Eigen, like arithmetic operations, element wise operations and also casting operations to cast from one data type to another. Off course dimensionality is not cast-able. It is not possible to cast a 2D point into a 3D point since members will be left uninitialized.

Point2f C(1,1);
Point2i D(3,2);
Point2f res = C + D.cast<float>();

## Lines

Lines are only supported by boost::geometry. That's why no conversions to other libs are needed. If you want to use cv::polylines(), you have to create your own structs anyway.

## Ellipsoid

Ellipsoids can only be converted into line strings in the 2D case.

Point2f center(0,0);
mira::Ellipsoid<float,2> ellipse(center,radii); // construct the ellipsoid
boost::geometry::polygon<Point2f> ellipse.toPoly(1); // convert into polygon with 1 deg steps

## Polygon

Polygons are only supported by boost::geometry. That's why no conversions to other libs are needed. If you want to use cv::fillPoly(), you have to create your own structs anyway.

# Rasterization

The idea of rasterization is based on the visitor principle. The goal of all rasterization tasks is to project a geometric object into a grid where the rasterizer tells the visitor which cells of the grid are covered by the geometrical object. Currently, only 2D Objects can be rasterized. 3D Voxel rasterization is planned for future work.

In order to keep the rasterizer as universal as possible, we do not assume certain types of raster targets like OpenCV images, QT images or own 2D arrays. Only the visitor knows on which data structure it operates. The rasterization entity only tells the visitor which pixels it has to visit to cover the area of the geometric object.

That way, the visitor implements all functionality processing the actual pixels. The designer can implement visitors to integrate the values of all pixels, find the maximum or minimum pixel or simply draw a color to the pixels.

In the following examples, we always try to find the maximum pixel inside an image for our geometric primitives.

## Line

Here we create a line string and parse it segment by segment.

// the visitor to find maximum values
class MaxVisitor
{
public:
MaxVisitor(mira::Img8U1& img) : myImg(img)
{
max = 0
};
// the rasterization callback for runslice algorithm
void operator()(int x,int y,int length)
{
uint8* tStart=myImg[y];
tStart += x;
for(unsigned int i=0; i<length;i++)
{
if(max < *tStart) max = *tStart;
tStart++;
}
}
uint8 max;
private:
mira::Img8U1& myImg;
}
int main()
{
//define the line
myLine.push_back(mira::Point2i(5,5));
// perform rasterization
MaxVisitor myVisitor(img);
for(unsigned int i=0; i < myLine.size()-1; i++)
{
mira::Point2i first = myLine[i];
mira::Point2i second = myLine[i+1];
mira::bresenhamRunSlice(first,second,myVisitor);
}
std::cout << "maximum pixel of line string is: " << myVisitor.max << std::endl;
}

## Triangle

For rastering a triangle, a very similar visitor has to be created.

#include <RasterTriangle.h>
// the visitor to find maximum values
class MaxVisitor
{
public:
MaxVisitor(mira::Img8U1& img):myImg(img)
{
max = 0
};
// the rasterization callback for runslice algorithm
void operator()(int xl, int xr, int y)
{
assert(xl <= xr);
uint8* tStart=myImg[y];
tStart += xl;
while(xl != xr)
{
if(max < *tStart) max = *tStart;
tStart++;
xl++;
}
// and check the last pixel
if(max < *tStart) max = *tStart;
}
uint8 max;
private:
mira::Img8U1& myImg;
}
int main()
{
//define the triangle
mira::Point2i A(3,3);
mira::Point2i B(5,3);
mira::Point2i C(5,5));
// perform rasterization
MaxVisitor myVisitor(img);
mira::rasterTriangle(A,B,C,myVisitor);
std::cout << "maximum pixel of the triangle is: " << myVisitor.max << std::endl;
}

## Rects

To raster a rect is a simple task. We can again use the visitor from line rasterization.

#include <RasterRect.h>
using namespace mira;
int main()
{
//define the rect
Rect2i myRect(Point2i(3,3), Point2i(5,10));
// perform rasterization
MaxVisitor myVisitor(img);
rasterRect(myRect,myVisitor);
std::cout << "maximum pixel of the rect is: " << myVisitor.max << std::endl;
}

# Geometric operations

A theoretical overview about geometric operations is given in: