Extending C++, The “const public” Section

A few years ago I came into contact with a nifty language called C#. For situations where the language itself will not be the bottleneck C# can prove a huge improvement in productivity over C and C++. Still, I mainly program in C++ as I often dabble in graphics engines where language can sometimes have far too big of an impact to disregard it. C# does however carry some really cool ideas that I would have wanted C++ to have. One idea in particular strikes me as a feature that I sorely miss.

The concept is called “properties” in C#. Basically, they are an elegant way to eliminate accessor and mutator functions (more commonly known as “getters” and “setters”). What these properties do is that they hide the fact that the user of an object is effectively calling a function that returns a private field by looking like the user is simply reading or writing to data directly.



However, since properties are essentially functions, these functions may perform any number of operations before reading or writing. Sometimes, there lies a really costly algorithm beneath calling a property that the programmer might be unaware of. This is generally considered bad practice, but not prohibited.

In C++, I would write the above code differently. If I am absolutely certain that the variables are pure getters and setters that are free from indirect effects I would simply declare them public and be done with it. However, sometimes declaring something public might be a too invasive action. Sometimes, you just want a programmer to be able to read, but not write from a public scope. You could write a function that returns the data, but that results in more code (not by a lot) and function calls all over the place. You could achieve this by declaring the data itself const, but that would prohibit the object it belongs to from manipulating it save for the time of construction. Because of this I thought of a construct that takes the best from both worlds; The “const public” section.



The “const public” section is essentially only a subset of the concept of properties by only exposing a bare bones way of reading data from any scope. Therefore, the construct still falls in line with the low-level thinking that pervades C++. By extension, a “const protected” section might also make sense, where data is not readable or writable publicly, read-only from a subclass, and readable and writable from the base class that declares it.

Initially, I thought this was a clear win for the language as a whole. However, if you are a somewhat well versed C++ programmer, or you come from any object oriented language background, you have probably already spotted the flaw of the construct; Encapsulation, or more specifically, the way it breaks encapsulation. This is where I am currently struggling to reconcile my own differing views. On the one hand a good interface is agnostic to the  implementation, where if the implementation changes the interface remains the same, and thus keeps the amount of code changes that need to be made to a minimum. On the other hand, C++ is a very special kind of language. It sails the seas between different programming paradigms by being flexible enough for the programmer to craft her own paradigms to adhere by.

Extending a language should always be done with caution. The main question is, will a const public section result in a big enough improvement, or detriment, to the language as a whole to be considered worth the effort? My guess is that it will have a minimal impact either way, but can prove to be a major convenience when the situation arises. Regardless, const public sections are not intended to be abused, and should be approached with the same caution as declaring data public. However, const public might at the same time be a better alternative to the programmer than just declaring data public.

The Illusive Multiplication Operator

As you may know, vectors define a multitude of operations. Three of these operations are commonly used as a basis to overload the multiplication operator in C++; component-wise multiplication, cross product, and dot product. However, there seems to be no actual consensus regarding what operation to overload the operator with. Most often, the multiplication operator is overloaded to mean dot product. However, some people prefer to overload it to mean the cross product, which is a completely separate concept.

Some, myself included, always preferred to define the multiplication operator as a component-wise multiplication as there is too much confusion regarding whether the operator meant cross or dot product, and we 'bypass' the problem by simply not having the operator defined as either. For those operations it would be better to explicitly call functions named after what they do to so as to eliminate any confusion. However, overloading the multiplication operator to mean component-wise multiplication is also more in line with vector subtraction and addition, and becomes very useful for various forms of interpolation, not to mention its usefulness with regards to color arithmetic.

However, a few months ago Jonathan Blow tweeted a simple insight that struck me as profound.

@paniq @keefjudge @id_aa_carmack Everyone overloads operator *(vec, vec) differently, which is a good reason not to overload it at all.
— Jonathan Blow (@Jonathan_Blow) March 12, 2013

Actually, he is completely right. Avoid all confusion by simply not overloading the multiplication operator at all. While I am sad to say that I still implement my vector multiplication as a component-wise multiplication I still feel that the point being made has affected me in other ways where if there is a risk of confusion in anything I do, I try to rethink the situation instead of perpetuating the problem.

The Importance of a Stable Clipping Algorithm

I recently started working on a new project involving a software renderer while at the same time trying out rendering techniques that I never got around to learning before. One such technique is the binary space partitioning tree. While the concept of BSP trees are fairly straightforward it surfaced an error in some old code that I imported into the project, namely the code that clips polygons against a single plane and outputs two polygons; one polygon wholly in front of the clipping plane, and one polygon wholly behind the clipping plane.

The general idea behind the creation of a BSP tree is to recursively subdivide the geometry by picking a an existing polygon hyperplane to split the geometry by and sorting them in three lists; a list for geometry in front of the hyperplane, a list for geometry behind the hyperplane, and a list for geometry that is coplanar in relation to the hyperplane. This process then recursively repeats for each of the newly created lists, except for the coplanar list which is already sorted. The exact stopping condition is determined by the programmer, although common stopping conditions include lists that only contain a single polygon, or lists that only contain a certain minimum amount of polygons. Care has to be taken when choosing the hyperplane to split by so as to avoid the tree from becoming too deep, or unbalanced. This is a science of its own and will be discussed in some other context.

When determining which list a polygon should be sorted in there can be four separate cases; a polygon is entirely in front of the hyperplane, a polygon is entirely behind the hyperplane, a polygon is coplanar in relation to the hyperplane, or a polygon intersects the hyperplane. For this last case a clipping algorithm is used. This algorithm literally splits a polygon into two parts; one part wholly in front of the hyperplane, and one part wholly behind the hyperplane, and then sorts the resulting polygons into their respective lists for further processing. This is the situation where a stable clipping algorithm becomes very important.

A stable clipping algorithm should never clip a polygon by a plane that it has already been clipped by once. More precisely, it should not generate a polygon on the opposite side of the plane, since that part has already been clipped away from the input polygon. An unstable clipping algorithm might generate two polygons despite the fact that such a polygon should not exist. For view frustum clipping a stable algorithm is not all too important since the polygons behind the clipping planes are discarded. As such, I was never able to identify the error earlier. For BSP tree generation an unstable clipping algorithm will almost certainly cause an infinite loop by constantly clipping the polygons that share an edge with the hyperplane.

The code I eventually came up with an algorithm that looks like the following:

The basic rundown of the algorithm is as follows. First, make room for the output polygon. Then pre-calculate all of the input vertices' signed distances to the plane. If all vertices are either behind the plane, or coinciding with the plane, then return an empty output polygon. The next part is the actual clipping. This requires comparing two connected vertices' distances. If the first vertex is in front of the plane, and the other is behind or coinciding with it, or if the first vertex is behind or coinciding with the plane, and the other is in front of it, then linearly project the first vertex to coincide with the plane. Additionally, if the first vertex is in front or coinciding with the plane then add it to the array of output vertices. A counter keeps track of the number of output vertices generated so far. Outside of the loop this counter will be used to re-size the output vertex array to correspond to the number of generated vertices. In order to get the polygon on the opposite side of the clipping plane, simply negate the plane normal and apply the algorithm to the original input data.

Remember that the output polygon has to be able to hold room for one more vertex than the number of input vertices since clipping against a single plane can logically only output that many vertices at most. Alternatively, you could use a list as the output data structure to avoid preallocation and resizing of data. If your algorithm potentially outputs more than one extra vertex then your algorithm is unstable and you should reconsider using it.

While the algorithm now ideally should work as expected, we are working with a finite amount of bits for out floating point types. This means that in practice the algorithm will not work reliably for anything but axis-aligned planes. This is where numerical stability becomes important. Implementing numerical stability in this case usually means nothing more than allowing some leeway in the classification of points as being either behind, in front, or coinciding. Therefore, the general algorithm remains exactly the same, with only a few adjustments in the implementation:

I wish to express some degree of caution. While the code works as expected for any input that I have given it I can not guarantee it to work for all possible inputs. Even I can err. As such, there may yet be come classes of cases that the above algorithm does not handle properly. If so, my apologies.

Resources

BSP Tree Frequently Asked Questions (FAQ) - Question 8 
Clipping a Convex Polygon Against a Plane

What is a Voxel Renderer?

I often see both scholars and novices alike point out what a voxel engine is and what it is not. 'Minecraft does not use voxels', 'Resogun does not use voxels', and '3D Dot Heroes does not use voxels' is tossed around a lot. I agreed with them for a long while, basing my opinion on the fact that many, if not all of the examples thrown around are hardware accelerated and as such are rendered using triangles as rendering primitives. After actually writing my own voxel renderer I came to a different conclusion about what constitutes a voxel renderer by separating the term 'voxel', which is a spatial data structure, from 'renderer', which is an algorithm used for the visualization of spatial data. In this post I will attempt show the logic of that argument by examining the individual terms of 'voxel renderer' with the hopes of showing people that the concept is far less binary than originally thought.

The first component of the term 'voxel renderer' is of course 'voxel'. Thus, we should have a look at what the basic concept of voxels means. Simply put voxels are volumetric data stored in a three dimensional grid, meant to convey a three dimensional image. It can therefore be said that a voxel is to three dimensions what a pixel is to two dimensions. Therefore, a way to think of a single voxel is to imagine a singularly colored, axis aligned cube (although it is ultimately the renderer that decides how to visualize the input data). It should also be noted that a cube is really only a convenient way of imagining a voxel. A cube is a volume defined by six points in an unrestricted three dimensional space, while a voxel is a single grid cell in an axis aligned space. As such cubes are free to move around the space, while a voxel is forever confined to the location of the cell in which it resides. Because of this we can really only say that a voxel is represented by a cube rather than actually being a cube.

Voxels can often contain more data than a color. They can also contain many properties that describe the surface that the voxels are representing such as surface normals and roughness. However, voxels will not need to contain information about position or size since their position is defined by their relation to one another in the voxel grid, while their size is homogenous along the individual axis. However, voxel volumes can be made to rotate and move independently of other, separate voxel volumes by attaching individual transformation parameters to each volume for the engine to regard when handling the data.

Given the information provided above it should be obvious that any game storing spatial data in a three dimensional grid can be said to use voxels in one form or another. Yet, another interesting facet of voxels is the rendering of voxels. A game engine encompasses many components that work together in tandem. Undeniably, one of those components is the renderer, which is often the single most characteristic and generally identifiable component in an engine. 'Renderer' is an umbrella term for all kinds of visualization algorithms; rasterizers, ray casters, ray tracers, splatters and so on, but it also has a much broader significance by encompassing things like transformation, hidden surface removal, and lighting and shadowing amongst other things.

Taken at face value, 'voxel renderer' does not make any pretense to dictate the actual algorithm used in the rendering process. In fact, it does not dictate anything except the predominant use of voxels in the process. A predominant use of voxels should be an obvious prerequisite when determining if a renderer is a voxel renderer since the term voxel is used as a classification of the renderer. Classifying by something other than a main characteristic feature would be misleading. However, 'renderer' is a much too open ended term to actually mean much (try substituting the word 'pixel' for 'voxel' in 'voxel renderer', and it should become abundantly clear just how without any meaning term is). Additionally, 'voxel renderer', as it stands, has not been used in such a was as to load it with a specific meaning regarding what method of delivery is employed in the rendering process. Therefore, the only prerequisite for a correct use of the term 'voxel renderer' is then the use of voxels as the main source of data used for rendering.

This leads to the question 'when are voxels considered the main source of rendering information'? It is common knowledge that modern day graphics cards provide an ad hoc solution for rendering triangles. Barring the use of OpenCL or the like, any rendering algorithm that seeks to accelerate the process via hardware has to ultimately render primitives as triangles. However, a voxel is converted into triangles merely as a final step to in the rendering process, which arguably is the smallest segment of the rendering pipeline. Aside from that, the mere fact that a voxel is rendered as a set of triangles does not mean that the end result is not a voxel. Rasterization is merely a delivery method for rendering voxels and should not, in and of itself, exclude a renderer that otherwise predominantly uses voxels from being considered a voxel renderer.

In conclusion, voxels are a form of spatial data, while rendering is a form of visualization algorithm. Voxel rendering is a form of algorithm (unspecified) used for the visualization of voxels. Thus, many different things can be considered voxel renderers, as long as there is a predominant, albeit not necessarily persistent, use of voxels throughout the renderer so as to not undermine the classifying term. Other than that, the definition is very open ended and may be used liberally until practice establishes a narrower use for the term.