Archive | Library 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:


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:


… compared to last week:


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.


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:


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



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.


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.


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:


… ω2:


…and ω3:


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.


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.


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.


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.

Aeson Revisited

As many of you know, the documentation situation in Haskell leaves something to be desired. Sure, if you are enlightened, and can read the types, you’re supposedly good. Personally, I prefer a little more documentation than “clearly this type is a monoid in the category of endofunctors”, but them’s the breaks.

Long ago, I wrote about some tricks I found out about using Aeson, and I found myself using Aeson again today, and I’d like to revisit one of my suggestions.

Types With Multiple Constructors

Last time we were here, I wrote about parsing JSON objects into Haskell types with multiple constructors. I proposed a solution that works fine for plain enumerations, but not types with fields.

Today I had parse some JSON into the following type:

data Term b a = App b [Term b a] | Var VarId | UVar a

I thought “I’ve done something like this before!” and pulled up my notes. They weren’t terribly helpful. So I delved into the haddocs for Aeson, and noticed that Aeson's Result type is an instance of MonadPlus. Could I use mplus to try all three different constructors, and take whichever one works?

instance (FromJSON b, FromJSON a) => FromJSON (Term b a) where parseJSON (Object v) = parseVar `mplus` parseUVar `mplus` parseApp where parseApp = do ident <- v .: "id" terms <- v .: "terms" return $ App ident terms parseVar = Var <$> v .: "var" parseUVar = UVar <$> v .: "uvar" parseJSON _ = mzero

It turns out that I can.

Pretty Printing our Pretty Program with Pretty

Tell me if you’ve heard this one before. You’re making some complicated data structure in Haskell. Something like the following:

data Expr = EVal Int | EIdent String | EFunc String [String] [Expr] | ECall String [Expr] | ELet String Expr | EWhile Expr [Expr] | EShizzy Expr Expr Expr | EIfElse Expr Expr Expr | EReturn Expr deriving (Show)

You throw that deriving (Show) because it’ll totally help you debug! Time goes by, and you use your fancy Expr to write a robust imperative function:

test = EFunc "testFunc" ["gatito", "moogle"] [ELet "foo" $ ECall "petCat" $ [EIdent "gatito", EIdent "moogle"], EWhile (ECall "catsPlacated" []) [EShizzy (EIfElse (EVal 5) (ELet "foo" $ ECall "malloc" [ECall "sizeof" [EVal 2]]) (ECall "petCat" $ [EIdent "gatito", EIdent "moogle"])) (ECall "petCat" $ [EIdent "gatito", EIdent "moogle"]) (ELet "foo" $ ECall "safeLeakMemory" []) ], EReturn $ EIdent "foo" ]

You’re still good, you got Rainbow Delimiters to keep that all sorted. Now, more time goes by and you’re in the repl and something doesn’t work. What was this test thing again?

*Shizzy> test EFunc "testFunc" ["gatito","moogle"] [ELet "foo" (ECall "petCat" [EIdent "gatito",EIdent "moogle"]),EWhile (ECall "catsPlacated" []) [EShizzy (EIfElse (EVal 5) (ELet "foo" (ECall "malloc" [ECall "sizeof" [EVal 2]])) (ECall "petCat" [EIdent "gatito",EIdent "moogle"])) (ECall "petCat" [EIdent "gatito",EIdent "moogle"]) (ELet "foo" (ECall "safeLeakMemory" []))],EReturn (EIdent "foo")]

Well that’s unfortunate. What do we do now? Aside from the fact that this is completely useless to us, this certainly wouldn’t be OK to print out to a user…

The good news is that pretty printing is a snap thanks to the HughesPJ Pretty Printer. One simply has to implement the Pretty class for one’s type, and then they can get some reasonable output:

testFunc(gatito moogle) { let foo = petCat(gatito moogle) while(catsPlacated()) { +-- { if (5) let foo = malloc(sizeof(2)) else petCat(gatito moogle) } +++ + + +++ { petCat(gatito moogle) } +++ + + +++ { let foo = safeLeakMemory() } +-- } produceResult foo }

Let’s see how we get there, constructor by constructor.

EVal and EIdent

First up are the easy ones: EVal and EIdent, which represent bare values:

instance Pretty Expr where pPrint (EVal v) = int v pPrint (EIdent s) = text s

First we have to declare our instance, but next we can just print the values. int pretty prints an integer, and text pretty prints a string.

EFunc and ECall

Next we have function calls and definitions:

pPrint (EFunc n a b) = text n <> (parens $ hsep $ fmap text a) <+> lbrace $+$ (nest 2 $ vcat $ fmap pPrint b) $+$ rbrace pPrint (ECall n a) = text n <> (parens $ hsep $ fmap pPrint a)

There are some operators here that require explanation. All of these operators have type (Doc -> Doc -> Doc ), and are used to combine two Doc into one. A Doc is the type of thing that can be pretty printed, which is returned by calls to pPrint and various other primitive pretty printing functions provided by the library (like text and int)

<> glues the thing on the left next to the thing on the right with no space in between, where <+> does the same, but leaves 1 space in between. Similarly, $$ and $+$ glues the thing on the right to the bottom of the thing on the left. $+$ allows the right hand side to overlap with the left (more on this later). There are also hsep, and vcat which takes lists of Doc. These functions work similarly to <>, $$ and friends; they glue Docs together horizontally and vertically. *cat are the non-plus variants, and *sep are the plus variants.

Other functions introduced here are parens, which takes a Doc and surrounds it by parens. lbrace and rbrace insert { and } respectively. There is a braces function as well, but I didn’t use it because I want to control how the braces are shown. Finally, we have nest, which indents its argument. This function is great because it takes into account outer nest calls, so we can get arbitrary nesting.

ELet, EWhile, EIfElse, and EReturn

pPrint (ELet n e) = text "let" <+> text n <+> equals <+> pPrint e pPrint (EWhile p b) = text "while" <> (parens $ pPrint p) <+> lbrace $+$ (nest 2 $ vcat $ fmap pPrint b) $+$ rbrace pPrint (EIfElse p t f) = text "if" <+> (parens $ pPrint p) <+> pPrint t $+$ text "else" <+> pPrint f pPrint (EReturn v) = text "produceResult" <+> pPrint v

Nothing particularly fancy here. in ELet, we have equals which inserts an equals sign and we have more nesting throughout. As you can see, this is very simple once you get the hang of it; there are few abstract instances involved, and most functions do what they say.


As we all know, any programming language that doesn’t have Shizzy statements isn’t worth knowing, so of course I implement them:

pPrint (EShizzy u d t) = onFire $+$ (nest 6 (lbrace $+$ (nest 2 (pPrint u)) $+$ rbrace)) $+$ noRules $+$ (lbrace $+$ (nest 2 (pPrint d)) $+$ rbrace) $+$ noRules $+$ (nest 6 (lbrace $+$ (nest 2 (pPrint t)) $+$ rbrace)) $+$ onFire where onFire = nest 2 $ text "+--" noRules = nest 2 $ (text "+++" $$ text "+ +" $$ text "+++")

This produces the following output as we’d expect:

+-- { if (5) let foo = malloc(sizeof(2)) else petCat(gatito moogle) } +++ + + +++ { petCat(gatito moogle) } +++ + + +++ { let foo = safeLeakMemory() } +--

and this gives me a good opportunity to demonstrate the difference between $$ and $+$. Let’s swap all the plus variants out:

onFire $$ (nest 6 (lbrace $$ (nest 2 (pPrint u)) $$ rbrace)) $$ noRules $$ (lbrace $$ (nest 2 (pPrint d)) $$ rbrace) $$ noRules $$ (nest 6 (lbrace $$ (nest 2 (pPrint t)) $$ rbrace)) $$ onFire where onFire = nest 2 $ text "+--" noRules = nest 2 $ (text "+++" $$ text "+ +" $$ text "+++")

Now, the pretty printer outputs the following:

+-- { if (5) let foo = malloc(sizeof(2)) else petCat(gatito moogle) } +++ + + +++ { petCat(gatito moogle) } +++ + + +++ { let foo = safeLeakMemory() } +--

Basically, if something is nested far enough that it would appear after the end of the left hand side argument, it is pasted to the right of it instead of below it. Honestly, it’s pretty strange behavior to me, I say just avoid $$ for the most part and you’ll be fine. It’s not a huge stretch for me to think of a use for this, but I think I’d just use <> or <+> if I wanted this to happen.

Regardless, I’ve worked on projects that use this pretty printing library before, and now that I’ve given it a shot I know why!

%d bloggers like this: