N - dimensional surface on a vertex array. More...

#include <Realm.h>

Collaboration diagram for Realm:

Classes
class	RealmPrinter
	Auxiliary class encapsulating printing and conversion to std::string. More...
Public Types
typedef std::vector < VecMath::Vector< 4 > >	vertex_container_type
	Storage type for the vertices.
typedef std::vector< Realm >	realm_container_type
	Must support push_back, forward iterator, reverse iterator, operator[].
Public Member Functions
	Realm ()
	Default constructor: Realm points to the first vertex in the array.
	Realm (unsigned i)
	Construct a Realm pointing to a specified vertex.
	Realm (const realm_container_type &sr)
	Construct a Realm from a number of subrealms.
	~Realm ()
	Destructor. Frees managed Realms automatically.
unsigned	size () const
	Returns the number of subrealms the Realm is made of, emulating realm_container_type interface.
void	clear ()
	Returns the Realm to a completely empty state, emulating realm_container_type interface.
void	push_back (const Realm &r)
	Add a new subrealm to the list, emulating realm_container_type interface.
realm_container_type::iterator	begin ()
	Pointer to first subrealm, emulating realm_container_type interface.
realm_container_type::const_iterator	cbegin () const
	Const pointer to first subrealm, emulating realm_container_type interface.
realm_container_type::iterator	end ()
	Pointer past last subrealm, emulating realm_container_type interface.
realm_container_type::const_iterator	cend () const
	Const pointer past last subrealm, emulating realm_container_type interface.
realm_container_type::reverse_iterator	rbegin ()
	Reverse pointer to last subrealm, emulating realm_container_type interface.
realm_container_type::reverse_iterator	rend ()
	Reverse pointer before first subrealm, emulating realm_container_type interface.
unsigned	dimension () const
	Returns the dimension of the realm.
void	setDimension (unsigned d)
	Sets the dimension of the realm.
unsigned	toIndex () const
	Makes a Realm of dimension 0 usable as index into the vertex array.
Realm	extruded (unsigned delta) const
	Create a new Realm by extruding the present Realm.
Realm	tapered (unsigned taper_index) const
	Create a new Realm by tapering the present Realm.
Realm	rotated (unsigned num_segments, unsigned size) const
	Create a new Realm by rotating the present Realm.
void	merge (const Realm &r)
	Merge `r` into the current Realm, keeping the dimension as it is.
const realm_container_type &	getSubrealms () const
	Get the list of subrealms this Realm is made up from.
void	setSubrealms (realm_container_type sr)
	Manually set the list of subrealms.
bool	operator== (const Realm &other) const
	Whether all the elements in two Realms are equal.
bool	contains (const Realm &other) const
	Whether a Realm contains another, either directly or in any subrealm.
std::string	toString () const
	String representation.
void	addOffset (unsigned delta)
	Add an offset to all indices into the vertex array.
Private Member Functions
Realm	extrudedPoint (unsigned delta) const
	Extrude a point to a line.
Realm	extrudedLine (unsigned delta) const
	Extrude a line to a square.
Realm	extrudedPolygon (unsigned delta) const
	Extrude a polygon to a prism.
Realm	extrudedRealm (unsigned delta) const
	Extrude an N-dimensional Realm to a N+1-dimensional one, where N > 2.
Realm	taperedLine (unsigned taper_index) const
	Taper a line to a triangle.
Realm	taperedPolygon (unsigned taper_index) const
	Taper a polygon to a pyramid.
Realm	taperedRealm (unsigned taper_index) const
	Taper an N-dimensional Realm to a N+1-dimensional one, where N > 2.
Realm	rotatedLine (unsigned num_segments, unsigned size) const
	Rotate a line into a polygon approximating a circle.
std::list< realm_container_type >	generateListOfPointsToAdd (std::list< Realm > original_list, unsigned num_segments, unsigned size) const
	Which points are generated when rotating a line.
void	insertNewPoints (std::list< Realm > &original_list, const std::list< Realm::realm_container_type > &new_points) const
	Add points generated from rotating a line.
Realm	rotatedPolygon (unsigned num_segments, unsigned size) const
	Rotate a polygon into a quasi-sphere, cylinder or cone.
Realm	rotatedPolygonCap (const realm_container_type &temp_subrealms) const
	Upper and lower cap for a rotated polygon.
Realm	rotatedRealm (unsigned num_segments, unsigned size) const
	Rotate a Realm of at least 3 dimensions.
Realm	rotateStep (unsigned index, unsigned base, unsigned delta) const
	Create a Realm by extruding edges for one step of a rotation.
Realm	generateStripBetweenGreatCircles (unsigned base, unsigned delta) const
	Create a three-dimensional Realm from a polygon for one rotation step.
realm_container_type	rectsBetweenGreatCircles (unsigned base, unsigned delta) const
	Generates a list of rectangular surface segments which make up a strip between two great circles.
Realm	reorderRectsBetweenGreatCircles (Realm::realm_container_type subrealms, unsigned int index) const
	Makes elements of a strip between great circles have the correct orders.
Realm	generateRectSegment (unsigned i, unsigned base, unsigned delta) const
	Generates a rectangular surface segment of a sphere.
void	addRotationStrip (Realm &all_strips, unsigned rotation_step, unsigned num_segments) const
	Accumulate the rectangles generated by connecting the edges of a polygon with the polygon rotated into a new dimension.
void	addStayingWithinSameStrip (unsigned total_vertices, unsigned rotation_step)
	Transforms a rectangle on a sphere to the rectangle lying directly across the sphere.
void	checkArgumentsForAddStayingWithinSameStrip () const
	Make sure addStayingWithinSameStrip() is called only on a valid Realm.
std::pair< unsigned, unsigned >	wrapToStayWithinStrip (unsigned base, unsigned extruded, unsigned num_segments, unsigned rotation_step) const
	If `base` or `extruded` point beyond the current rotation strip, wrap them around so they remain within it.
Static Private Member Functions
static Realm	generateEmpty3DRealm ()
Private Attributes
unsigned	_dimension
	Dimension of the realm.
realm_container_type	_subrealm
	Subrealms the Realm is made of.
unsigned	_index
	If _dimension == 0, this is the index into the vertex array.
Static Private Attributes
static const bool	DEBUG_ROTATE = false
	Whether to print debug output in the rotate() function.
static const unsigned	OFFSET_BETWEEN_NEIGHBORING_INDICES = 2
	How far vertices, that are actually neighbors in geometry, are apart in the vertex array.

Detailed Description

N - dimensional surface on a vertex array.

A Realm stores a N-dimensional surface in the form of indices into the object's vertex array. The vertex array is not managed by the Realm and must be independently managed.

Every Realm is made up of subrealms: E.g. a rectangle, as part of the surface of a three-dimensional object, is made up of lines, and a line is made up of its endpoints. Thus, a Realm stores its subrealms, except for points, which are stored as the index of the corresponding N - dimensional vertex in the vertex array of the described object.

Realm emulates the interface of std::vector<Realm>, as far as this interface is used.

Todo:

fully understand and document rotating polygons

add caps for polygons

It looks as if it would make sense for Realm to manage the vertex array too. Look into this.

refactor to have shorter functions.

Author:: Lene Preuss <lene.preuss@gmail.com>

Constructor & Destructor Documentation

Realm::Realm ( unsigned i ) [inline]

Construct a Realm pointing to a specified vertex.

Parameters:

i	The index of the vertex in the vertex array.

Realm::Realm ( const realm_container_type & sr ) [inline]

Construct a Realm from a number of subrealms.

Parameters:

sr	The subrealms which together make up the new Realm.

References _dimension, and std::vector< _Tp, _Alloc >::empty().

Here is the call graph for this function:

Member Function Documentation

void Realm::addOffset ( unsigned delta )

Add an offset to all indices into the vertex array.

public only to satisfy unit tests.

Todo:: find a better way.

References _dimension, _index, _subrealm, std::vector< _Tp, _Alloc >::begin(), and std::vector< _Tp, _Alloc >::end().

Referenced by addStayingWithinSameStrip(), extrudedPolygon(), and extrudedRealm().

Here is the call graph for this function:

Here is the caller graph for this function:

void Realm::addStayingWithinSameStrip	(	unsigned	total_vertices,
		unsigned	rotation_step
	)		`[private]`

Transforms a rectangle on a sphere to the rectangle lying directly across the sphere.

Adds an offset to indices in the realm, generating the rectangle that is generated by rotating the line that is opposite (in the original polygon) of the line that generated this realm.

in other words, transforms a rectangle on a sphere to the rectangle lying directly across the sphere.

keep the "+1%num_segments" operation constrained to the two offending indices, but not the other two.
ensure that both of the transformed indices stay in the target range, which is the vertices in the original strip for the smaller one and the vertices in the rotated strip for the bigger one. What is the target range? Well, every quad can be seen as a pair of pairs of indices: [ (base1, extruded1), (extruded2, base2)]. the base points need to remain in the base range [j*N, ..., j*(N+1)-1], while the extruded points lie in [j*(N+1), ..., j*(N+2)-1].

Parameters:

total_vertices	Number of vertices per polygon.
rotation_step	Between 0 and num_segments-1.

References _dimension, _subrealm, addOffset(), std::vector< _Tp, _Alloc >::begin(), checkArgumentsForAddStayingWithinSameStrip(), std::vector< _Tp, _Alloc >::end(), std::pair< _T1, _T2 >::first, OFFSET_BETWEEN_NEIGHBORING_INDICES, std::pair< _T1, _T2 >::second, toIndex(), and wrapToStayWithinStrip().

Referenced by addRotationStrip().

Here is the call graph for this function:

Here is the caller graph for this function:

Realm Realm::extruded ( unsigned delta ) const

Create a new Realm by extruding the present Realm.

There is an annoying problem with the circumstance that I'd like to store realms as [sets of] point sets of their dimension, and that OpenGL needs point sets to draw two dimensional surfaces (as opposed to sets of lines). I cannot, therefore, store a two dimensional Realm as a set of one dimensional Realm s in any efficient way. I need to treat two dimensional Realm s differently.

That leads to special cases for each of the following operations:

Going from zero to one dimensions: Make a line from the point and its extruded image. Handled by extrudePoint().
Going from one to two dimensions: make a surface from the two end points of the line and their extruded images, storing the Realm not as a set of lines, but as a set of points and manually setting its dimension to two. Handled by extrudeLine().
Going from two to three dimensions: The top and bottom caps can be copies of the current object, as in the default algorithm below, but the sides must be treated as lines, and thus repeat the algorithm described above. Handled by extrudePolygon.
Default: Top and bottom caps are (shifted) copies of the current Realm, while for the side connections the extrusion algorithm is called recursively. Handled by extrudeRealm().

Parameters:

delta How many elements there were in the original vertex array - IOW, how much there needs to be added to each index from the original Realm to be pointing to the corresponding vertex in the extruded vertex array. (Gee, that's a mouthful.)

References _dimension, extrudedLine(), extrudedPoint(), extrudedPolygon(), and extrudedRealm().

Referenced by extrude_base< D >::extrude(), and extrudedRealm().

Here is the call graph for this function:

Here is the caller graph for this function:

Realm Realm::extrudedLine ( unsigned delta ) const [private]

Extrude a line to a square.

Special case: make surfaces so OpenGL can draw them. _subrealm.size() should be 2.

References _dimension, _index, _subrealm, std::vector< _Tp, _Alloc >::push_back(), std::vector< _Tp, _Alloc >::size(), and toString().

Referenced by extruded().

Here is the call graph for this function:

Here is the caller graph for this function:

Realm Realm::generateEmpty3DRealm ( ) [static, private]

Returns:: A Realm of dimension 3, with no Realms contained.

References setDimension().

Referenced by rotatedPolygon().

Here is the call graph for this function:

Here is the caller graph for this function:

Realm Realm::generateStripBetweenGreatCircles	(	unsigned	base,
		unsigned	delta
	)		const `[private]`

Create a three-dimensional Realm from a polygon for one rotation step.

split procedure: once for points on the positive and once for negative points. what happens and actually seems to be necessary here is this. when i comment out the second loop in the case of a cylinder only half is drawn. in the case of a sphere only a quarter sphere is drawn regardless of whether the second loop runs or not.
i suspect that there should be _subrealm.size()/2 loops of length 2. in the cylinder case, this happens to be the same as what we have here, because _subrealm.size() == 4.

Todo:

Split into smaller functions.

Fix for triangles.

References push_back(), rectsBetweenGreatCircles(), reorderRectsBetweenGreatCircles(), std::vector< _Tp, _Alloc >::size(), and size().

Referenced by rotateStep().

Here is the call graph for this function:

Here is the caller graph for this function:

bool Realm::operator== ( const Realm & other ) const

Whether all the elements in two Realms are equal.

Todo:: rewrite to make independent of realm_container_type::operator[]

References _subrealm, dimension(), std::vector< _Tp, _Alloc >::size(), and toIndex().

Here is the call graph for this function:

Realm Realm::rotated	(	unsigned	num_segments,
		unsigned	size
	)		const

Create a new Realm by rotating the present Realm.

Todo:: more documentation

Parameters:

num_segments	How many segments to use approximating a circle.
size	Size of the original vertex array. See extrude().

References _dimension, rotatedLine(), rotatedPolygon(), rotatedRealm(), and toString().

Referenced by rotate_base< D >::rotate(), and rotatedRealm().

Here is the call graph for this function:

Here is the caller graph for this function:

Realm Realm::rotatedLine	(	unsigned	num_segments,
		unsigned	size
	)		const `[private]`

Rotate a line into a polygon approximating a circle.

To rotate a line we must do the following.

Rotate both endpoints of the line num_segments times, first the one, then the other. Connect the last rotated image of the first endpoint to the original second point and the last rotated image of the second point to the first point. If we start with the line [0, 1] and rotate it with num_segments = 3, we get [ 0, 2, 3, 1, 4, 5 ].

Parameters:

num_segments	How many segments to use approximating a circle.
size	Size of the original vertex array. See extrude().

Copy the subrealms to a list for easier insertion in the middle.

Copy the subrealms back from the temporary list to a vector

References _subrealm, std::vector< _Tp, _Alloc >::begin(), copy(), std::vector< _Tp, _Alloc >::end(), generateListOfPointsToAdd(), insertNewPoints(), and std::vector< _Tp, _Alloc >::size().

Referenced by rotated().

Here is the call graph for this function:

Here is the caller graph for this function:

Realm Realm::rotatedPolygon	(	unsigned	num_segments,
		unsigned	size
	)		const `[private]`

Rotate a polygon into a quasi-sphere, cylinder or cone.

For a two-dimensional surface we have to do the following.

First, because the surface is not stored as a list of lines, but rather as a list of points (because drawing the surface from lines in OpenGL would be too tedious) we have to split the surface corner points into line segments. Say we have a square defined as [0, 1, 3, 2] we must first split it into its edges: [0, 1], [1, 3], [3, 2], [2, 1].

Say we have num_segments = 3. What we want in the end is for the sides of the prism: [0, 1, 5, 4], [4, 5, 7, 6], [6, 7, 3, 2], [2, 3, 9, 8], [8, 9, 11, 10], [10, 11, 1, 0] and for the caps: [0, 4, 6, 2, 8, 10], [1, 5, 7, 3, 9, 11].

Nietzsche said (I paraphrase), "Philosophers are often poor writers because they not only tell us what they think, but also how they developed their thoughts." If I were a good writer, my code would express the solution for the numbering and ordering of indices in a "rotated" Realm clearly. Because I am not, I include my musings as a reference to whom it may concern.

A polygon's indices are numbered like this:

       5 *       * 3


  0 * - original-line - * 1


       2 *        * 4

A rotation step leads to the following situation, unsatisfactorily depicted in ASCII art.

               5 *           * 3

             11 *           * 9  <- rotated up

  0,6,12 *                           * 1,7,13



               2 *-----------* 4
                  \          \      <- one resulting face
 rotated down-> 8 *-----------* 10

To generate a polygon strip that adds a surface to all these vertices, we connect each neighboring pair [original vertex, neighboring vertex] and their rotated images. Naively we would just add num_segments (6) to connect to the rotated vertex, then add the offset 2 to connect to the neighbour in the rotated polygon, then subtract 6 again to connect to the neighbor in the original polygon. In traversing the list of vertices we must use each vertex twice, because it is part of two line segments/resulting faces. The idea is to simply add 2 to each vertex in a face, that would lead to the next neighboring face. Let's see how that works out.

  [0,  6,  8, 2] -> [2,  8, 10, 4]     ok.
  [4, 10,  7, 1] -> [6, 12, 13, 3]     wrong face! 12 and 13 lie across the center.
  [3,  9, 11, 5] -> [5, 11, 13, 7]     wrong face again! 5 and 11 don't neighbor 13 and 7.

Clearly, if an "overflow" occurs, ie. vertices are connected to other vertices that do not result from the same rotation step, errors creep in. addKeepingInRange() ensures that the vertices are kept within the same plane:

  [0,  6,  8, 2] -> [2,  8, 10, 4]
  [4, 10,  7, 1] -> [6, 12, 11, 5]
  [3,  9, 11, 5] -> [5, 11,  6, 0]

Todo:: Add the caps.

References addRotationStrip(), generateEmpty3DRealm(), getSubrealms(), and rotatedPolygonCap().

Referenced by rotated().

Here is the call graph for this function:

Here is the caller graph for this function:

Realm Realm::rotatedPolygonCap ( const realm_container_type & rotated_walls ) const [private]

Upper and lower cap for a rotated polygon.

Create the cap (perpendicular to the rotation axis).

Make the first edge the first line in the temporary list of subrealms (assuming we have a square). To do that remove the last two vertices from the square.

Todo:: achieve the desired effect for any polygon

then add the following edges by using only the first point of the edge

References _subrealm, std::vector< _Tp, _Alloc >::pop_back(), std::vector< _Tp, _Alloc >::push_back(), and std::vector< _Tp, _Alloc >::size().

Referenced by rotatedPolygon().

Here is the call graph for this function:

Here is the caller graph for this function:

Realm Realm::rotateStep	(	unsigned	index,
		unsigned	base,
		unsigned	delta
	)		const `[private]`

Create a Realm by extruding edges for one step of a rotation.

The edges of the current Realm are rotated about some (clarify!) axis. The resulting image is connected to the current Realm, resulting in a Realm of the same dimension. The total set of thusly created Realms, for all degrees from 0 to 360, constitute the surface Realm of the rotated object. Phoo, another mouthful.