Archive | C++ RSS for this section

Reboot Early, and Often!

A wise man once said to me “Reboot early, and often!” He said it many times actually. When you’re trying to troubleshoot programs for which you don’t have the source code, you tend to develop little rituals that you go through to “fix” them…

So here I was today, trying to power through the boilerplate to draw a triangle in Vulkan. I had just finished up creating my Pipeline object, and ran my program to see if it worked. As you can imagine, it didn’t work.

Shockingly, C++ Causes Problems

First up: my shaders are invalid. The error:

validation layer: ObjectTracker : Invalid Shader Module Object 0xa.

Of course, the Object Tracker layer is there to tell you when you try to use objects that are not valid handles. Usually this is because vKcreateFoo did not return VK_SUCCESS. Of course, vkCreateShaderModule definitely did return VK_SUCCESS, because if it hadn’t my program would have died in a fire thanks to my expect assertion macro. Surely either I have a driver bug or C++ is doing “exactly what I told it to.”

So I do some troubleshooting. I upgrade my driver which does nothing. Then I examine my code. Buried in a comment thread on this stackoverflow question is the suggestion that a destructor is being called. I examine my code, and sure enough, the RAII object that I’m storing my shader in is being destructed before the call to vkCreateGraphicsPipeline. C++ was doing “exactly what I told it to.”

Sound Advice

So an hour later, and one problem down. I recompile and try again:

vkEnumeratePhysicalDevices: returned VK_ERROR_INITIALIZATION_FAILED, indicating that initialization of an object has failed

Shenanigans! There’s no way that vkEnumeratePhysicalDevices is messed up, that’s been working for weeks! I turn to the Googler, but to no avail. Then the words rang in my head “Reboot early and often!” It’s not like I just updated my graphics driver without rebooting or anything… Oh wait!

Moral of the story: reboot early, and often!

Procedural Moonbase: 30 Seconds to Launch

Mere hours from the deadline, the project comes to its conclusion. However, some sacrifices had to be made. Andrew tried valiantly to get the procedural city generation working, but it was a lost cause. Instead he implemented shadow mapping.

Honestly, I think this works better for our concept. I was a bit worried that the scene might be a bit too busy with the city, but I think the addition of shadows really works, and gives the trees the last little bit of “oomph” that they needed. The “Octopus” tree especially casts a nice ominous shadow over the landscape, and it all plays quite nicely with the orbiting light.

One Last Push

On the eve of the deadline, work continues at a feverish pace…

Procedural Terrain and L-systems

Work on procedural terrain generation and crystal formations was mostly done for last Friday’s post. A bit of polish work has occurred since then. Most notably, I’ve smoothed out the terrain of the real world moon heightmap data. The result is much more moon-like:

smoother

Also, I’ve tweaked the shader for the crystal growths. I’ve used a technique similar to what is done in cel shading to recognize the silhouettes of the growths. At first I was planning on implementing actual cel shading, but it did not look good. However, I discovered that I could favor the external shell portion of the texture in the silhouette area, much like how if you look at a transparent object from an extreme angle, you see more of the surface material. I find the result to be quite satisfying:

newShader

… compared to last week:

anemone

Procedural Cities and Buildings

This weekend, Andrew added functionality to render the smaller heightmap for the city on top of the buildable area of the larger heightmap.

The main C++ program invokes a Python script to generate the heightmap and road network, then reads the data into a new LandscapeModel at the appropriate location. The program then renders the road network using a solid color shader for now. By rendering only a portion of the road network at a time, it’s possible to animate the process, showing how the network grows from the population centers and intersects with itself.

roads

The more significant challenge has been extracting buildable areas from the road network. Implementing the road network growth required hacking together a spatially indexed graph database. The generated graphs are subtly broken – some roads cross without an intersection, so the graph is not necessarily planar.

Andrew need to resolve this issue before he can reliably extract cycles, and he needs to extract buildable plots before he can place and generate buildings. He will be working on that tonight.

Where the graph is sensible, he is able to extract a cycle:

cycleSuccess

But in a case where the edges intersect somewhere besides an intersection point, this fails:

cycleFail

Plumbing

There is an additional requirement that all procedural elements be able to be regenerated at runtime. I’ve implemented the plumbing to ensure that this happens. At the press of a button, the terrain can be regenerated, the crystals can be regenerated and the real world heightmap data can be toggled on and off. Additionally, when the city generation is complete, the plumbing is in place for that as well.

All this regeneration happens much faster than I’d thought it would, which was nice. There was no need to optimize the regeneration or implement asynchronous regeneration.

Onwards To The Moon

As the deadline looms, work continues at a feverish pace. Much has happened, and much remains to be done.

Procedural Terrain Generation

The terrain generation is basically done. We are generating random landscape heightmaps using the Diamond-Square algorithm. After generating the heightmaps, we carve out a flat space for the city, and then place various mineral deposits and crystal growths. After the features are set, we tessellate the landscape.

progGenTerrain

We are also capable of reading in external heightmap data, and I’ve located a heightmap of the surface of the moon, which we are capable of turning into a 3D surface.

As you can see, the lunar surface is much rougher than one would think.

theMoon

Crystalline Structures

New this week are the crystalline structures seen in the screenshots above. These are generated using L-systems, with the following grammar:

V = { D(len, topScale, bottomScale, topLen, bottomLen), C(len, topScale, bottomScale, topLen, bottomLen), S(scale), T(minSegs) } S = { F(theta), K(theta), A(r, s) } ω1 = { A(C(6,1,1,1,1), D(1.0f, 3.0f, 2.5f, 0.5f, 1.0f)) } ω2 = { A(C(6,1,1,1,1), A(F(1), S(1))) } ω3 = { A(S(1), A(K(1), T(3)) } P = { D -> A(D, A((K(1), C(2,1,1,1,1)))), C -> A(C, A(F(0.75), T(3))), T : final iteration -> A(T, S(0.5)), T : otherwise -> A(T, T(1)), S : -> A(S, D(3,2,1,1,1)) }

There is a basic crystal building block, represented by D and C. These are the same shape, but D has 5 branching points, and C has 1 (the center.) To build on a mounting point, one uses the A rule, which states “For all mounting points produced by r, build s on it.”

Rounding out the bunch, are S a “scepter” shaped crystal, F, which fans out in three directions, and K, which forks in two directions. Last but not least is the “angry tentacle” formation T.

Here we see ω1:

anemone

… ω2:

coral

…and ω3:

octopus

Procedural City Generation

We’ll be placing a procedurally generated moon base on the flat build site carved out of the terrain. The moon’s surface is very rough, so we can only place the base on the flat area.

However, the area under the city isn’t completely flat; we are using a technique called spectral synthesis to generate a smoother heightmap underneath the city. The edges of this heightmap will coincide smoothly with the surrounding terrain to ensure a natural transition.

167cg1

After generating the heightmaps, we generate a population density map using a similar procedure, attenuating it where the terrain is steepest (it’s difficult to build on the side of a hill!). Then we sample the density map and place population centers using k-means clustering. Finally, we triangulate the set of population centers to generate a connectivity graph for road generation.

167cg2

Once we have a connectivity graph, we draw adaptive highways between population centers using the technique described in Citygen: An Interactive System for Procedural City Generation, using a heuristic combining Least Elevation Difference, population density, and the degree to which the road would deviate from its current direction. As these are drawn, we create additional perpendicular roads in areas of high population density. These roads are extended using the same heuristic until they reach a less populated area.

167cg3

So far, we’ve implemented the above in Python so we can leverage the performant array operations from NumPy and SciPy, in addition to the spatial indexing functionality from Rtree. We’ll need to use the Python C API to call into our Python code and store the resulting road graph in a buffer for rendering.

The Way Ahead

Much work remains to be done. For terrain and L-systems, there remains polish work. I’ve implemented the required algorithms, and it technically “works.” However, it’s still a bit rough. I hope to refine the shaders of the crystals to make them appear more 3-dimensional. Additionally, I’d like to increase the density of “trees” on the landscape as I think it looks a bit sparse. I hope to have this work wrapped up by tomorrow night.

For city generation, the road graph needs to be converted to buildable cells, and subdivided/populated with buildings. Andrew plans to have this done by tomorrow night. By Sunday, he plans to have the rendering set up for this, with basic buildings. Then by Monday, more elaborate buildings will follow.

Additionally, we need the capability to regenerate the various procedurally generated components at runtime. This is a simple matter of plumbing, and should not be difficult. Time allowing, I’d like to do this asynchronously, so there is no frame hiccup during regeneration. The user will press a button, and a few seconds later, the change will be reflected.

Procedural Moonbase

Having reached the end of UCSD’s Intro to Computer Graphics course, I have been tasked with creating a real-time demo that implements a subset of features covered in the class. Today is the first of three posts about the progress of this project.

For this project myself (Chris Tetreault) and my partner Andrew Buss will be implementing 4 features:

  • Procedurally modelled city
  • Procedurally modelled buildings
  • Procedurally generated terrain
  • Procedurally generated “plants” with L-systems

With all of these, we’ll be creating a procedurally generated moon base. First, we will generate a landscape, and carve out a flat spot for the base. Next, we will generate a city, which consists of a procedurally generated layout populated by procedurally generated buildings. Finally, we will procedurally generate doodads to be placed on the landscape throughout the undeveloped portion of the terrain.

All of this will be implemented in modern C++ with modern OpenGL.

Terrain and “Plants”

This portion of the project is coming along nicely. We are currently generating the landscape, with the exception of textures. We currently have the surface normals set as the pixel color in the fragment shader.

Procedurally Generated landscape

At some elevation lower than the city, I plan to add lava. Additionally, I plan to have two land based-textures that I will select between based on the elevation gain. Likely, this will be a smooth rock texture for steep hills, and gravel for flatter areas.

After completing this, I will use L-systems to generate stuff to put on the landscape. This will likely take the form of geological formations, such as rocks or lava flows as one isn’t likely to find trees on a blasted lunar wasteland.

Cities and Buildings

For the city portion, we’ll be procedurally generating moon base buildings. We decided to go with the moon base, as opposed to a traditional city because we felt this could give us more creative freedom to do what we want. After all; if the task is to procedurally generate a “City”, how many urban downtown areas are you likely to see?

This portion of the project is still in the planning phase, so expect to see more on this next week.

Making C++ Exceptions Less Terrible

If you’re a fan of doingmyprogramming, you’ve likely heard me opine on the subject of exceptions. If you’re new around here, I’ll spare you a link to some required reading and just let you know: they’re poop. With the exception of Java and it’s checked exceptions, they just represent secret ways that a function can crash your whole program. Just about nobody gets it right, not C++, not C#, and the worst offender is probably my beloved Haskell where you can’t even catch them unless you’re in the IO monad.

C++ used to have an annotation (throw()), where you could specify what exceptions a function throws, and if none are specified then the function cannot throw. This was considered poor form and deprecated long before I came on the scene. It turns out that there is good news though; throw() wasn’t forgotten! It was replaced by noexcept, and that is what we’ll be talking about today.

What is noexcept?

noexcept is an annotation that basically says “this function will never throw an exception”. You can think of it as being like const. If you some class method:

void myClass::isPure() const;

… then you know that, whatever it does, the state of the object will not be mutated. Similarly, if you see some function:

void neverThrows() noexcept;

… then you know that, whatever it does, the function will never throw an exception. Optimization implications aside, this is great because if you see a function declared noexcept, then you know for sure that you don’t have to put it in a try/catch block. If we ever start living in a world where people use this annotation, then a function not marked noexcept is a function that likely throws, and we can act accordingly without having to read through mountains of likely incorrect or incomplete documentation!

Specifically, the meaning of noexcept (according to Microsoft) is:

noexcept ( and its synonym noexcept(true)) specify that the function will never throw an exception or allow an exception to be propagated from any other function that it invokes either directly or indirectly. More specifically, noexcept means the function is noexcept only if all the functions that it calls are also noexcept or const, and there are no potentially evaluated dynamic casts that require a run-time check, typeid expressions applied to a glvalue expression whose type is a polymorphic class type, or throw expressions.

The Burning Quetion

So I read that blurb, and thought to myself: “…only if all the functions it calls are noexcept? So, I can’t catch all possible exceptions and be noexcept?”. I felt despair wash over me as C++ got something wrong yet again. Then I thought “there’s no way that’s correct… To the Googler!”

Of course, the Googler didn’t help my case. I decided to give it a shot. First, let’s consider two functions: one that throws and one that is noexcept:

static void doesThrow() noexcept(false) { std::cerr << "Entering doesThrow..." << std::endl; throw 42; std::cerr << "Still in doesThrow. Up is down, cats and dogs living together!" << std::endl; } static void catchesAll() noexcept(true) { std::cerr << "About to enter the try/catch..." << std::endl; try { doesThrow(); } catch (...) { std::cerr << "Caught the exception..." << std::endl; } std::cerr << "Exited the try/catch..." << std::endl; }

doesThrow is annotated noexcept(false), which is the same as saying “This function can throw an exception.” And sure enough, it throws in 100% of its code paths.

catchesAll is annotated noexcept(true), which is just the long form of noexcept. noexcept accepts arguments that evalutate to bool, and compile-time magic happens to allow conditional noexcept-ness. noexcept(expr) can also be used in an if/then/else to conditionally do something based on if some expr is noexcept.

In catchesAll, we have a try/catch block that prevents the exception thrown by doesThrow() from propagating out of catchesAll(). Does this work? Let’s write a test harness and see:

int main(int argc, char ** argv) { std::cerr << "About to call catchesAll..." << std::endl; catchesAll(); std::cerr << "Managed to not die!" << std::endl; }

… if we compile it with gcc (with -std=c++11) and run it, we see that all is well!

About to call catchesAll... About to enter the try/catch... Entering doesThrow... Caught the exception... Exited the try/catch... Managed to not die!

You may be wondering what happens if we don’t catch the exception. Let’s find out! If we remove the try/catch, but leave everything else the same:

About to call catchesAll... About to enter the try/catch... Entering doesThrow... terminate called after throwing an instance of 'int' Aborted (core dumped)

We see that the exception propagated out of catchesAll() and caused a core dump. This is the expected behavior. In fact, there’s no way we could have prevented this. If some function marked noexcept throws, then that function has a bug. If you wrote it, you have to fix it. If somebody else wrote it, then they have to fix it. There’s no band-aid that will keep it from crashing your program. If you find this happening often, then you should consider finding an alternative library that does what the broken dependency claims to do, since they clearly don’t know what they’re doing…

Operator Overloading in C++

My thoughts on Operator Overloading are hardly a secret. Some languages, such as Haskell, support it in a sane manner. Some languages, such as C++ don’t. Either way though, I’m not a fan.

That said, there is one case where I support it; when what you are trying to overload an operator to do makes sense for your type. In other words, if it makes sense to multiply an Employee object, feel free to overload the multiplication operator. Since we don’t usually model mating when we implement an employee object, I don’t usually approve.

Multiplying a Fraction

However, if we have a fraction class, that has a numerator and denominator component, overloading the multiplication operator suddenly becomes reasonable:

frac<T> operator *(const frac<T> & rhs) const { return frac<T>(numer * rhs.numer, denom * rhs.denom); };

In C++, many of the built in operators are available to be overloaded. You can do basically anything in an operator overload, but if you do, that makes you a bad person. Here we have a straightforward implementation, that I’m going to assume you don’t need to have explained to you. But let’s talk const correctness.

In this signature, the const appears twice. The right hand side argument is a const reference. Since this is a reference, no copy occurs, but with references can come mutability. The const here prevents any mutation from occurring. There is also a const at the end of the signature. That means that this function cannot modify the this pointer.

This function returns a new frac<t>, so no need for const there.

Convert a Fraction to a Double

Next, you can overload the casting operator, and if you are a good person you’ll use this for type conversions. Let’s implement (double) for our fraction:

operator double() const { return (double) numer / denom; }

This code is pretty straight forward. We divide the numerator by the denominator, and cast it to double in case integer division occurs. Cast operator overloads don’t have a return type, which is a bit strange but something we can work with.

Streaming operators

Finally, I’d like to talk about streaming operator overloads. For any overloaded operator, there are two forms: member and non-member. Member overloads take n - 1 arguments, where the minus 1 is the current object (and the left hand side). Non member overloads can’t access the this pointer, so they need to take the left hand side as a parameter.

Member overloads obviously have access to private class members, which makes them more powerful than non-member. Which leads us to the streaming operators. Streaming operators need to return std::ostream &, so they must be non-member. The problem is that we want to print the private numerator and denominator fields. The solution? make it a friend:

friend std::ostream & operator <<(std::ostream & lhs, const frac<T> & rhs) { lhs << rhs.numer << '/' << rhs.denom; return lhs; };

With that problem solved, this function becomes pretty straight forward. We stream the fields, formatted correctly, into the left hand side std::ostream &, then we return the left hand side argument for further use by the next part of the streaming chain.

%d bloggers like this: