Wednesday, November 30, 2016

On the Road to Splines 2

After a bit of work this evening, I managed to implement the nonuniform splines as described in Game Programming Gems 4 Chapter 2.4. "Nonuniform Splines" by Thomas Lowe presents three times of pleasantly-rounded splines, the rounded nonuniform spline, the smooth nonuniform spline, and the timed nonuniform spline.  While I implemented the code for all three splines in my drawing program, only the rounded nonuniform spline is actually available through the GUI.

A rounded nonuniform spline

As you can see, it is a relatively-smooth shape, despite the fact that I've turned it into line segments roughly ten pixels long each.  A second spline is shown below, selected so that the end points of the line segments are visible.

A spline selected.  The green circles represent the end points of the line segments.
I've sorted out in my head the concepts on the topological graph vs. the shapes.  I've thought through how to do serialize the shapes and substances into simple XML.  I'm also thinking up other ways to utilize this.  There are several published articles on terrain and other feature generation using lines, splines, polygons, etc. and I've thought up several variants, as well.  The function graphs from several weeks back were related to one of those ideas.

So what's next, in the immediate future?  The polyline with curved corners, and making the edit mode display the vertices as drawn, rather that the line segment vertices.  Pan and zoom, too.  Then comes the real work, with the substances/layers.  Road, rail, river, etc.  Stay tuned for more.

BBQ at Last!

On Monday, I mentioned that the local BBQ joints were all closed on Mondays.  In fact, most were also closed today, Tuesday, but luckily one was not.  Alas, it took me a while to find the Butt Shack BBQ restaurant, which recently relocated from Greenhills, Ohio (one of the Depression-era greenbelt towns) to Fairfield, OH.  It is located in the former location of Symmes Tavern on the Green.  Why did it take me a while to find it?

First, Google Maps has the location for that address off by about 1500 feet.  Second, the old Symmes Tavern on the Green signs are still up on the facade.  Third, the only signage for the Butt Shack is a banner, tied to a low fence - a few feet in front of which was a bench - and just beyond that were parked cars.  Not trying to make it easy to find, were they?

In any event, after I finally found it, I was quite pleased.  The same tasty menu was being served as at the old location.  Service was a bit chaotic - I think this was the start of their first full week of operation.  The food did arrive in a reasonable time frame - slower than at the old location, but reasonable enough.  However, I'd barely had time to take my second bite from the side salad when the beef brisket and cole slaw arrived.  The brisket was juicy and flavorful, and the spicy BBQ sauce complemented it well.  The cole slaw was decent but not spectacular.  All in all, it was a good meal, and I enjoyed it.  I suspect that as the staff gets a bit more experience the service will be less chaotic.

The new location is larger and full of natural light, but does take an extra five minutes to reach from work (assuming traffic lights cooperate), or 15 minutes from home.  This makes Pit-to-Plate BBQ in Mount Healthy a better choice when I'm craving BBQ and at home.  The Butt Shack is the only nearby BBQ place open on Tuesday, and is just as close to work, so I'm likely to visit both places.

Given the prevalence of chain restaurants, it's nice to be able to find a few good, local places that aren't chains.  I just know not to seek food at such places on Mondays.

Tuesday, November 29, 2016

On the Road to Splines

A rounded non-uniform spline can offer a pleasant-looking route for a river, road, or railroad.  A fence or utility line may be represented by a polyline.  I need someplace to try all of that out, before I look to incorporate it into anything useful.  Hence my Drawing Example application, which does only a little bit now.  It lets me draw lines, polygons, and polylines.  I can select the shapes I've drawn, move them, and delete them.  In the screenshot, there are also toolbar items for polylines with curved corners (via circular arc fillet), arcs, and rounded splines - but I still have to add the code for them.

A few shapes drawn using the program: polygon, line, polyline

Things are just getting started, really.  The points (vertices, corners) of the multi-segment shapes should be adjustable after a shape is drawn.  Those other shapes I mentioned also need to be supported.  And right now, all it does is draw line segments.  I need to experiment with having it generate road, river, railroad, etc.  Persistence (saving/loading) would also be useful.

There's also an unresolved design issue, something that I'm having trouble resolving in my mind conceptually.  The shapes drawn represent things that can form networks: a river network, a road network, etc.  Such networks have their own topology, which is often described in terms of graphs, with nodes and links (or vertices and edges).  Short version: nodes are intersections, and links are the segments connecting them.  But how well does that relate to the shapes themselves?  And how about the points of a spline?  If you run one road into another, how does the intersection get formed - does a new vertex get added?  How is this all tracked?  Are shapes of each "substance" (road, water, etc.) handled separately?  What about when shapes made of such substances interact, such as when a road crosses a river, or a railroad crosses (or even runs down) a street?

Current architecture is trending toward MVC (model-view-controller) though it didn't start that way. But the shapes and "substances" seem like good candidates for model (along with topology when I have that figured out), and the rendering mechanisms are a good fit for view, so add in a little bit of controller and MVC makes a reasonable paradigm here.

There will probably be follow-up posts on this topic in the future.  And at some point this functionality will likely migrate into the 3D engine.

Monday, November 28, 2016

Book Review: At the Sign of Triumph

It took me until several weeks after its release before I finally purchased a copy of the latest book in David Weber's Safehold series, At the Sign of Triumph.  Perhaps if Tor's e-book pricing was more reasonable I'd have picked up an electronic copy rather than waiting to visit a bookstore.  In any case, the book is quite hefty, but it is a good read.  It flows rather more readily than the previous tome in the series, which seemed to get bogged down in logistics at times.  There were a few points in the book where I found myself pausing for a moment to remember who the viewpoint characters were, but not often, and I'm perfectly happy that Weber left out the lengthy character list included in some volumes.

While the war itself seemed to get bogged down at times, the plot of the book moved along with greater alacrity than it had in the previous couple volumes.  In fact, without offering any real spoilers, it is fair to say that this book caps off the initial arc that begins with Off Armageddon Reef.  Not all of the mysteries that originated there or since have been clearly answered, but this volume marks a conclusion to that arc and ties up quite a few loose ends.  Still, it is a lengthy read.  Budget time or expect to take a while to finish it.

Overall, I was quite happy with the book.  It flowed well.  It contained scenes I loved.  Some dastardly foes received their just desserts.  There were outbreaks of sanity and self-interest among key characters.  It was lots of fun.  I dare say little more without spoiling it.  Let me just conclude that I felt it was worth every single penny I paid.


Mondays suck.  Even if you generally like your job, Mondays suck.  After being gone for several days visiting family over the Thanksgiving holiday, the abrupt return to work came as something of a shock to the system.  So come lunch time, I decided to assuage my shocked system by seeking out some good old food.

This isn't to say I didn't have good food over the holiday trip.  I did - New Haven pizza is among the best, New Jersey diners make some awesome meals, and my cousins didn't slouch on Thanksgiving dinner - but I wanted something familiar.  Not something from a chain, either, but some good down home cooking.  I'd exercised restraint over the holidays, so I was perfectly happy with the thought of going to a local restaurant and chowing down on something tasty, rather than visiting the cafeteria.

Alas, reality set in.  It is Monday.  Almost every local place that isn't a chain is closed on Mondays. The BBQ place to the north, finally open in its new location, is closed.  The two BBQ places to the south are closed.  The Indian place nearby is closed, as is the Mexican place.  In fact, just about everything that's not a chain is closed today.  Did I mention that Mondays suck?

Crossing the Rubicon (or not)

Every now and then I encounter something quite wrong in non-fiction.  Sometimes I can just let it go, and move on.  Other times it puts an end to reading farther.  While I was returning from my parents over Thanksgiving weekend, I ran into an example of the latter.  First, let me just acknowledge that we all make mistakes sometimes, myself included.  I hope I don't come across as unfairly condemnatory, but certain types of mistakes can drive me nuts.

For whatever reason, I'm particularly attuned to catching errors of geography when reading. I've encountered quite a number.  For example, a non-fiction book describing the New Deal era Resettlement Administration's greenbelt towns misidentified the town constructed in Ohio. Another non-fiction book described the Connecticut River as flowing through New Haven, Connecticut, past the campus of Yale University.  As any map should show, the Connecticut River doesn't get within twenty miles of New Haven.  I got past those points after cringing and shaking my head, and continued reading.  The books otherwise seemed good enough, though I can only hope that the rest of the content didn't contain additional errors I wasn't knowledgeable enough to catch.

Anyway, what I ran into the other night was even worse.  Still, I may have moved past it, where it not for the tone of the book having already rubbed me the wrong way in places - and its shear wrongness. What had me so disturbed?  "Yet by the time Washington was crossing the Potomac in December 1776. . ."

Washington Crossing the Delaware by Emanuel Leutze
(Image from the Met web site)
Washington may have crossed the Potomac River many months earlier when traveling north from Virginia to assume command of the army forming around Boston, in the wake of the battles of Lexington, Concord, and Bunker (Breed's) Hill.  However, he was assuredly not doing so in December 1776, when he was instead crossing the Delaware River to attack the Hessians in their Trenton barracks. There's a famous painting and a couple of state parks that tend to bear that out.

I stopped reading at that point.  The book is headed back to the library come morning.  One wonders how many similar errors are floating around out there, in how many different books.  Just something to ponder.

Tomorrow, I should have either a book review or some technical progress to report upon.  For now, good night.

Thursday, November 24, 2016

Happy Thanksgiving!

I've been scarce online due to holiday preparations.  Happy Thanksgiving!  I am thankful for my wonderful parents, who taught me so much.  I am thankful for my health.  I am thankful for friends and family.  And I am thankful for this great country, America.  I shall resume normal blogging in the near future.  For mow, I hope anybody reading this is having a great day, and have much to be thankful for.

Monday, November 21, 2016

Memory Lane

Sometimes we remember the strangest things.  Sometimes we forget the outstanding.  Sometimes it all just blurs together.  And sometimes events, experiences, writings can prod you to remember things you hadn't thought of in ages.

Why am I bringing this up?  Because last night when I was reading a blog, one of those memories was dredged up.  I'm not sure why, or how, or what triggered it, but for the first time in ages I remembered a book from my childhood.  No, it wasn't one I owned.  It wasn't one from the library, from school, or one that a friend or relative had.  No, it was a book in the waiting room at the dentist's office.

Alas, I remembered only the general gist, and the art style.  Title and author eluded my recollection. Thus began nearly an hour of searching, until finally I found it.  The Summerfolk by Doris Burn is an extensively-illustrated children's book published in 1968.  It was over a decade later that I must have first encountered it.  It's the tale of a fisherman's son in coastal area, and an adventure in the swamps nearby along with the children of "the summerfolk," the summer-time vacationers.  That's all I can remember.  I may order a used copy via Amazon.

Anyhow, I have no idea what it was about the blog post that triggered my memories of the book.  But trigger it they did, and suddenly I was having vivid recollections of reading it on the colorful stools in the waiting room, or when I was a bit older on the sectional couch.  The smell, the sights, the sounds of sitting there, reading that book, just washed over me.  Memory is a stranger thing.

Sunday, November 20, 2016

Random Thoughts

I'd planned to do more today that I could share, but that alas did not happen.  I decided to play the game World of Warships a bit before getting started.  It had been months since I'd last done so, and the end result was my computer had to download and apply thirteen gigabytes worth of updates before I could play, during which time my computer wasn't very smooth doing anything else.  It took darn near two hours.

I washed dishes in the kitchen.  I cleaned my shower and replaced the old shower curtain liner.  I replaced a burned out bulb.  I threw out trash.  I sorted through my old code and tracked down stuff I prototyped days, weeks, months, or even years ago - this included a partial implementation of algorithms for computing the minimal cycle basis of planar graph, complete code for implementing circular arc fillets (my own C# implementation of the venerable algorithm from the 90's Graphics Gems series), C# and C++ versions of basic drawing functionality, an incomplete but partially-functional CPU-based terrain brush program, and a host of others things I'd written at one point or another.  I found that I'd written a lot of code with which I'd then done nothing, but which ties in nicely with the projects I'm working on now, and that I'm blogging about.  You may see some of that mentioned in coming months.

Earlier in the day, I went to the movie theater and watched the movie Fantastic Beasts and Where to Find Them.  I really enjoyed the movie, and perhaps I'll do a review on it at some point.  My point here, right this moment, is not to discuss my day or the movie in terms of plot, characters, or pacing. Instead, I'd like to briefly touch on the amazing rendition of Manhattan in the 1920's that was an integral part of the movie.  It felt very much like that age should feel in a movie.  Subways, streetcars, and elevated railroads provide mass transit.  Cars and trucks of the era line the streets.  The buildings look right.  The newer skyscrapers that we're accustomed today are absent.  Very well done, with the tiniest of exceptions: the streetcars.

The streetcars of New York City were electrically powered.  In Manhattan, they were largely powered by an electrical conductor in an underground conduit, which opened to the outside via a narrow slot between the rails.  It looked a bit like the cable cars of San Francisco, but instead of the streetcar gripping a cable that moved in the conduit, the electric streetcars had a plow that extended below the car and into the conduit to make contact with the conductor.  In some cases, the conduit was in fact the conduit of former cable car lines.  Only a few other cities employed such a technique, such as Washington, D.C. and London.  In the rest of New York City, the more traditional means of overhead wires supplied the electricity needed to power the motors of the streetcars.  In the movie, almost entirely set in Manhattan, neither means of supplying electricity to the streetcars were seen, but the streetcars were observed rolling along with no problems.  I found this immensely amusing.

Assuming I have enough time tomorrow, I hope to do something worthy of posting about.  Until then, world, try not to blow up.  Thanks.

Saturday, November 19, 2016

Post Later

I went to sleep early yesterday evening, spent a couple hours up in the wee hours, and just finally woke up again.  Now I have other things I need to do.  There should be a post later.  Until then, take care!

Thursday, November 17, 2016

Victory Over the Swiss!

In yesterday's blog post, I described my battles with the Swiss turbulence (or erosive noise) Giliam de Carpentier describes in his blog post and publication.  An hour's work this evening has largely resolved the outstanding problems.  As I suspected, a bit of analysis of the algorithm for Perlin noise derivative calculation, and comparison with the algorithm for Perlin noise generation, allowed me to figure out what must be done.  After about 30 minutes of experimenting with the parameters, I was generating terrains with excellent mountain topography.

Seven octaves of Swiss turbulence, with gain 0.8, vertical scale 175, and a horizontal scale of 0.0003
There's a bit more that can be done to improve it, with some smoothing or alternate interpolation methods.  I imagine that adding a little bit of erosion, perhaps as part of a river model, will improve the appearance further.

I'll be on to other things for now.  I want to look at integrating some roads and settlements into the current "endless" dynamic terrain that I've been playing with in my engine test.  Dynamic road and building generation, even without complex city generation algorithms, should be possible.  Maybe basic Perlin noise as a lookup to indicate if terrain should be mountains, hills, or flatter land that is forest, field, or varying densities of development.

In case you're trying to implement this yourself and have run into problems because the gradients and permutation tables in the examples are implemented very differently than you've implemented Perlin noise, I've included a bit of my C# code below.  The solution to the problem was darn simple.  Using any of the examples I linked in yesterday's post, the calls to the myRandomMagic function are simply replaced calls to GetGradient.

private const int GradientSizeTable = 256;

private readonly double[] _gradients = new double[GradientSizeTable * 3];
/* Gradient table borrowed from code by Darwyn Peachey.
   The gradient table is indexed with an XYZ triplet, which is first turned
   into a single random index using a lookup in this table. The table simply
   contains all numbers in [0..255] in random order. */

private readonly byte[] _perm = new byte[] {
 225,155,210,108,175,199,221,144,203,116, 70,213, 69,158, 33,252,
5, 82,173,133,222,139,174, 27,  9, 71, 90,246, 75,130, 91,191,
 169,138,  2,151,194,235, 81,  7, 25,113,228,159,205,253,134,142,
 248, 65,224,217, 22,121,229, 63, 89,103, 96,104,156, 17,201,129,
  36,  8,165,110,237,117,231, 56,132,211,152, 20,181,111,239,218,
 170,163, 51,172,157, 47, 80,212,176,250, 87, 49, 99,242,136,189,
 162,115, 44, 43,124, 94,150, 16,141,247, 32, 10,198,223,255, 72,
  53,131, 84, 57,220,197, 58, 50,208, 11,241, 28,  3,192, 62,202,
  18,215,153, 24, 76, 41, 15,179, 39, 46, 55,  6,128,167, 23,188,
 106, 34,187,140,164, 73,112,182,244,195,227, 13, 35, 77,196,185,
  26,200,226,119, 31,123,168,125,249, 68,183,230,177,135,160,180,
  12,  1,243,148,102,166, 38,238,251, 37,240,126, 64, 74,161, 40,
 184,149,171,178,101, 66, 29, 59,146, 61,254,107, 42, 86,154,  4,
 236,232,120, 21,233,209, 45, 98,193,114, 78, 19,206, 14,118,127,
  48, 79,147, 85, 30,207,219, 54, 88,234,190,122, 95, 67,143,109,
 137,214,145, 93, 92,100,245,  0,216,186, 60, 83,105, 97,204, 52};

private int Permutate(int x)
const int mask = GradientSizeTable - 1;
return _perm[x & mask];

private int Index(int ix, int iy, int iz)
// Turn an XYZ triplet into a single gradient table index.
return Permutate(ix + Permutate(iy + Permutate(iz)));

private float GetGradient(int i, int j, int k)
int index = Index(i, j, k);
int g = index * 3;
return (float)_gradients[g];

Fighting the Swiss

No, this post isn't about a battle with the people of Switzerland.  Instead, it regards a struggle to implement the "Swiss turbulence" algorithm that Giliam de Carptentier wrote about in a blog post. It is also referred to as erosive noise in his article with Radael Bidarra, "Interactive GPU-based procedural heightfield brushes."  It produces more realistic looking mountain shapes than the ridged hybrid fractal that was one of the best I'd previously found, of which I've shown screenshots.  The blog post contains the code for an implementation in Nvidia's Cg shader language, but I'm coding in C# for execution by the CPU, not GPU.  Fine, I thought, I'll just port it...

Except it relies upon computing the derivative of Perlin noise, the included implementation of which
was implemented totally differently.  In the implementation in the article, the traditional permutations and gradient arrays are implemented as two-dimensional textures containing vectors derived from RGB values, rather than one-dimensional arrays of integers and floating-point numbers.  Ugh.  OK, maybe I can still deal with this, I think to myself, and give it a go.  Alas, over the course of an hour I become very frustrated, as a whole slew of issues come up.  The vector structures I'm using from OpenTK don't support adding or subtracting vectors and single floats.  Fine.  I implement extension methods, which are rather clunky in comparison to actual operators.  That works fine, but the rest of it I just can't seem to get it right.  But then I remember that article I mentioned, which references de Carpentier's source for the Perlin noise derivative, Inigo Quilez.

A quick search turns up Inigo Quilez's web page on the subject.  But it involves calls to functions such as myRandomMagic and iGetIntegerAndFractional, that aren't defined anywhere I could find on Quilez's web site.  The second one was easy enough to puzzle out by comparison with de Carpentier's code (it computes the integral and fractional portions of a number), but myRandomMagic was more problematic.  So I do a Google search and find an implementation of Quilez's code... in Go.  I've never used Go before, but the syntax was easy enough to puzzle out, and I used what I found to construct the missing function myRandomMagic, which was simply a lookup from the gradient and permutations arrays.  Fine.  Code finally done.  Run.

Exception!  The code doesn't handle negative coordinates well. (For all I know, it doesn't handle large coordinates well, either.)  I guess its time to go through my Perlin noise implementation and see how its addressed there.  Certainly it isn't addressed at all by the example code I based my implementation on.  But that'll have to wait for another day.  I'm going to call it a night, and resume my fight  with the Swiss tomorrow evening, after work.

Tuesday, November 15, 2016

Filter Forge terrain generation

This is just a quick post to point out something neat.  I was searching Filter Forge's catalog of filters for some texture generation filters and stumbled upon a variety of terrain and planet generation options.  Unsurprisingly, most suffer from the same obviously-fractal origin as some of the other techniques I've mentioned in the past.  Nevertheless, some may be of use under certain circumstances, so I thought I'd make not of them.

Book Review: Caine's Mutiny

The eARC of the most recent novel in Charles E. Gannon's Caine Riordan series, Caine's Mutiny, was released on Monday by Baen Books.  I purchased a copy after dinner and have just spent far too many hours reading it.

First off, let me say that I thoroughly enjoyed this book, and would recommend it.  This one is slightly more of a military tale than others, but it as easily qualifies as space opera as the previous novels in the series.

The story delves into the situation teased at the end of the previous novel in the series, Raising Caine. Human broadcasts from an ostensibly alien world draws our cast of heroes from Raising Caine to investigate.  They promptly find themselves wrapped up in a conflict between human soldiers and the aliens on the planet, while troublesome adversaries lurk elsewhere.

In many ways, Gannon's Caine Riordan novels remind me of a space opera version of technothrillers, along the lines of Tom Clancy or Stephen Coonts.  Gadgets, intelligence work, military operations, schemers, plotters, and politics all combine with dynamic characters and understandable motivations. Even many of the alien characters are well fleshed out, and their motivations are understandable, even if different from those of the average modern human.

There's more I'd like to say, but there's little I more I wish to say that wouldn't involve spoilers. Therefore, I'll just add a few more points.  Like many of the other novels in this series, it ends on something of a cliff-hanger for the series' eponymous character, Caine Riordan.  Hopefully, that portends that the series will continue.  I hope Charles Gannon writes more.

Sunday, November 13, 2016

No Post Today

No post today.  Post tomorrow, no post today.  Words don't wish to flow, and I've accomplished little today on which to write.

PandoraCon 2016

This weekend I've been attending PandoraCon, a local science fiction convention.  I gather they're having some trouble this year, as attendance seems sparse, there were a large number of panel/program cancellations, and panels wasn't very plentiful to begin with in some of the time slots. Musical guests were very good, though.  I understand PandoraCon was up against at least one major convention and one minor convention, and that one of the local fan groups was otherwise engaged in some sort of costuming activity this week.  My late convention, Millennicon, was doing no better than this when the decision was made to shut down.  I wish the folks at PandoraCon the best and hope they pull through this year and have better luck next year.  Greater Cincinnati seems like it should be large enough it should be able to support at least one science fiction convention with real programming (as distinct from Midwestcon, the long-lived local Relaxacon).

EDIT: As I was reflecting this morning, I realized I need to give kudos to the folks running PandoraCon for two additional areas where they did very well this year.  Their vendor room was chock full of costuming, art, jewelry, and miscellany, though books seems to be sold mostly by authors - there were no real booksellers present.  Also, the gaming seemed to be going quite well, be it video gaming, RPG's, or other tabletop games.  There were anywhere from two to five games going on at any time.  Still, as I said, traditional programming was on the weak side.

On the other hand, the lack of decent programming this year led me to spend some time reading on my tablet.  I ran across a couple papers by George Kelly from the 2007-2008 time frame.  I'd downloaded from his web site and read "An Interactive System for Procedural City Generation" and other articles, but ran across them on my tablet again.  The aforementioned work is a lengthy masters thesis that provides implementation details on some of the techniques I've been playing with, so may be of some use, and I'm glad I stumbled across them.

Saturday, November 12, 2016

Offsets and editing

As I mentioned in my post earlier, I've made some progress on algorithms for straight skeleton and offset calculation.  They're nowhere near done yet, but you can see some of the progress in the screenshot below.  There algorithms so far are my independent implementations based upon little more than simple explanations of the concepts found on Wikipedia.

The offset (inset or outset) code relies upon the use of cross-products of 3D vectors to displace copies of the line segments making up the polygon.  Then it calculates the intersections between the displaced copies, using the topological relationships from the original polygon to help.  The resulting line intersections then become the new end points of the displaced copy line segments.  In this way the line segments are extended or truncates as necessary.  As can be seen from the bottom left example, further work is needed to deal with concave polygons more comprehensively.

Offset and straight skeleton examples.  The upper right is incomplete.
The straight skeleton code relies upon the offset code to determine vectors from the vertices toward the "center" of that portion of the polygon.  The code works well with convex polygons, but a more complex implementation is required to address concave polygons properly.

I've also got the initial GUI work for the scripted model generation code into better shape.  It is still far from complete, but is at least presentable.  The main inspirations are the Windows GUI for POV-Ray and the OpenSCAD GUI.  I was aided by a tutorial at CodeProject, and by the MVVM example provided with the AvalonDock component (look under Version 2.0/AvalonDock.MVVMTestApp). Various bits of documentation for the AvalonEdit component, including forums, were also of some assistance.

Tabbed editor for PowerShell scripts that can create 3D models

I hope to have something more to show in the next few days.

Friday, November 11, 2016

Status of the blogger

This blogger is tired, largely thanks to his day job, from which he is taking a break while writing this blog entry.  However, I have managed to make a bit of progress on various things, but have no pretty pictures to show at this time.  I'm doing some experiments with scripted generation of 3D models.  That is hardly new - in addition to scripting capabilities in traditional CAD packages, there are slew of other applications that employ various such approaches: POV-Ray, OpenSCAD, OpenJSCAD, and (via a rule-based system) City Engine.  My approach is probably closest to OpenJSCAD, but with a few additional ideas added in.

Alas, there are no pictures because I got temporarily sidetracked learning a bit more about WPF and MVVM while putting together a GUI for it.  I've used both in the past, but mostly applied them to database applications.  This was a bit different, there were some third-party controls (AvalonEdit for a syntax-highlighting text editor, and AvalonDock to organize the various chunks of UI) I wanted to use, around which I was having a hard time applying MVVM.  I think I've got the basics worked out now.

In terms of the core of the experiment, it is all pure C# code, and can therefore be utilized by any .NET language.  My plan for the scripting approach is to do so using PowerShell.  I've used PowerShell somewhat in my day job, and even implemented a custom host, so this should actually be pretty easy.  We'll see.

There should be a few pictures later from prototypes in testing certain algorithms that are still under development, such as implementations of polygonal offsetting/buffering and generation of the straight skeleton of a polygon.  Once all this is figured out, it'll be integrated with the engine from previous posts, so buildings, vehicles, etc. can be generated via script in the engine - or models generated and saved can be, depending upon usage.

In addition to all that, I recently purchased FilterForge, and have been having a bit of fun seeing what it can do.  As its name implies, it largely consists of filters, which can be applied to photos, renderings, art, etc.  But it also has a fairly significant capability for texture generation, as well - very useful for 3D modelling.  I may do a longer post on it at some point.

I'm continuing to read Arch Whitehouse's The Zeppelin Fighters, regarding British anti-Zeppelin operations during the Great War.  Its well written and an easy read, but I've only been reading it when I've been out to lunch - er, literally, that is - which hasn't happened as often as normal due to various factors this week (elections, overslept one day, problem at work, etc. etc.).  I'll do a review in full when I finish it, but that might be pushed back a bit, as David Weber's At the Sign of Triumph, the last book in his Safehold series (at least the current arc of it), has just been released.

Wednesday, November 9, 2016

Election's Over!

Thank goodness, and good riddance, to Decision 2016.  I shall now return to my usual posting ways starting this evening.  I'm so glad that mess is done with.

Tuesday, November 8, 2016

Choose the Form of the Destructor

The polls shall be opening in about six and half hours.  All I can think of is that line towards the end of the original Ghostbusters movie: "Choose the form of the destructor."  I can't think about books, computers, fiction, and all of that, all I can think of is the horrifying choice awaiting me on my ballot when day breaks.  I'm going to shower and go to bed.  And wash an unpleasant taste from my mouth. I'll be back with a longer post sometime tomorrow, or perhaps Wednesday if the horrors of election night force me to seek solace at the movies and catch Doctor Strange.

Sunday, November 6, 2016

Instanced Rendering Yields Forests

I've got crude code to use OpenGL instanced rendering working.  Each page measuring 2000 meters on a side has been populated with 150,000 trees.  There are 9 such pages being rendered each frame, for a total of 1,350,000 trees, and its running smoothly!  When making one rendering calls per tree using glDrawElements, a tenth that number of trees was causing the program to lag.  With instanced rendering, for each page I make a single call to glDrawElementsInstanced to render 150,000 trees, and all is smooth.

Possible areas to improve later today: slope and elevation awareness for object placement.  When mountains are tall enough (or far enough pole-ward) they tend to have a treeline, and elevation above which trees do not grow.  Also, trees tend to grow less commonly on the steepest portions of mountains, regardless of elevation or latitude.  Both of these properties should be fairly easy to implement.

Alas, there is yard work calling for my attention now, so I shall leave the virtual world alone for the moment and focus on the physical realm.

One hundred fifty thousand trees per 2 km x 2 km page of terrain

Saturday, November 5, 2016

Seamless in Cincinnati

We're now (almost) seamless in the terrains.  The surface normals calculated at the edges of each page of terrain are almost correct now.  In many cases, the seam is almost unnoticeable, while in other cases it amounts to nothing more than a slight difference in color to either side of the seam.  It was more glaringly apparently before because the normals at the edge were so far off that they were resulting in a "steep" normal that was in turn causing the rocky "steep" texture to be applied.  Next hurdle to jump: instanced rendering, so I can have decent foliage density rather than a sparse (pseudo) random scattering of trees here and there..

Anomaly at border has been vastly reduced.

Yesterday, normals were so far off the "steep texture" was being applied.

Book Review: Fighting the Flying Circus

Fighting the Flying Circus is Captain Edward V. Rickenbacker's memoir of his service as a combat pilot during the Great War (WWI).  It is a gripping book which I found it hard to put down.  It covers a bit less than a year of time, from when Rickenbacker first joined the 94th Aero Squadron until just after the Armistice of November 11, 1918.

Over the course of less than a year, Rickenbacker went from a novice to the holder of the informal title Ace of Aces, the living American with most number of aircraft confirmed shot down. Notice the emphasis on that word "living": his predecessors largely pre-deceased him.  As time went on, he was eventually placed in charge of a flight of fighters, and then promoted to captain and given command of the 94th Aero Squadron.  He commanded the squadron from the Meuese Argonne Offensive of September 1918 through the Armistice two months later.

His tales cover that entire period.  He recounts tales from variety of missions.  He went on patrols for enemy aircraft, escorted friendly reconnaissance aircraft into German territory, attacked German observation balloons in support of ground offensives, and shot down German reconnaissance aircraft and their escorts.  He recounts the demise of friend and foe alike, and tells of the triumphs and tragedies of his squadron and the others in the First Pursuit Group.

The title of the book derives from Rickenbacker's opposition during some of the latter months of the war. The German's most famous fighter group, Jagdgeschwader 1, known as "The Flying Circus" or "Richthofen's Circus," had been redeployed into the area of German-held territory opposite the 94th Aero Squadron, in an effort to defend against attacks by the British Independent Air Force.  "The Flying Circus" by this point was no longer led by the Red Baron, Manfred von Richthofen, but instead by Hermann Goring, with Ernst Udet as commander of one of the consitutent squadrons, Jasta 4.  These were the skilled, experienced opponents against which Rickenbacker and his comrades fought.

Interestingly, at least individuals appear in Fighting the Flying Circus who were prominent in Kosciuszko, We Are Here!, a book I reviewed back in August.  Merian Cooper plays a prominent role in a chapter or two of Rickenbacker's tale, involving a captured German fighter and attempts at aerial photography.  Cedric Fauntleroy also makes a brief appearance.

A recurrent feature of the tales Rickenbacker tells is the mechanical unreliability of their aircraft. Engines fail, guns jam, and hapless pilots suddenly find themselves turning from predator to prey, having to turn tail and run home, or plunging helplessly to their deaths.  The death of some of those who thus died wouldn't have been as likely had it not been for a deadly policy of the American Air Service during the war.

Per policy, American pilots, were not issued parachutes.  German pilots, by comparison, were issued parachutes, and even in their unreliable 1918 state those parachutes saved a lot of German lives.  American aircraft pilots were not so lucky.  Rickenbacker personally witnessed the sad sight of his fellow American pilots jumping from burning planes at altitude, or riding wrecked planes into the ground, for want of parachutes.  His squadron mates relayed even more tales.  Among those who perished thus were Rickenbacker's predecessors as Ace of Aces, such as Raoul Lufbery.  It was a tragedy, and a sad statement on American policy of the time.

As it was published immediately after the war, it is out of copyright and available for free in electronic form and in print form at reasonable cost.  I picked up a hardback printed copy for $15 at a bookseller during the The Dawn Patrol Rendezvous at Dayton last month.  For a first-hand American account of air combat at the time, I've yet to find anything better.  I highly recommend this book.  It's a fast read, and in electronic form the price is certainly right.


Night fell, midnight rolled passed, and once more I find myself bedward bound with no book review. Saturday sounds more promising.  I did make a bit of progress with the program.  The geometric seam problem at page borders has been resolved (bug), though there's still a visible seam in terms of the color/texture at the borders, because the normal calculations there are wrong (another bug).  I'll have to handle that (literal) edge case later.  I finished some code so that the trees are back again.

Geometry matches up now, but bad normals at the edge negatively impact the texture.

I tried out three algorithms from a chapter by F. Kenton Musgrave.  His warped fBm, hybrid multifractal, and ridged multifractal all produced interesting results.  Also, I ported Ian Parberry's exponential noise algorithm from his article in the Journal of Computer Graphics Techniques; the source code to accompany the article is on GitHub.

An example terrain created using the hybrid multifractal algorithm

All these algorithms work fairly well to produce terrain ranging from gently rolling to outright mountainous, but few produce more than one such result given the same set of parameters.  That is, the terrain generated with them may be almost flat, gently rolling, hilly, or mountainous, but it will not be gently rolling and mountain.  The main exception is heterogeneous fBm (hfBm), which produces flat and mountainous though not much in between.  Exponential noise is a little different, as well, but doesn't seem to produce major mountains.

Maybe tomorrow I'll experiment with combining Parberry's exponential noise and hfBm.  Or maybe I'll take a look at instanced drawing.  As it is, I can't add more than around fifteen thousand trees without frame rate seriously dropping.  Hopefully instanced drawing will speed things up.  Or maybe something else entirely.

Friday, November 4, 2016

Short progress post

Sorry, still no review.  I did make a bit more progress on the terrain.  The dialog box for generating the terrain is a bit better.  It now has a drop down list for algorithm selection, rather than an unruly clump of radio buttons at the bottom.  Musgrave's heterogeneous fractional Brownian motion produces some nice mountains with the parameters I'm using, producing tall rounded and peaked mountains with wide, relatively flat valleys in between.  I've also got paging working for terrains in combination with the fractal terrain generation, in a multi-threaded manner.  Get within a page or two (it's configurable) of the edge of loaded terrains, and more pages of terrain are generated.  Alas, I have to integrate the code for the entities (trees, foliage, etc.) back in.  The views below are from before the paging changes.  I also need better code for unloading "stale" pages.  The underlying OpenGL resources need to be released in addition to the regular .NET objects - currently that only happens upon application shutdown.

Terrain dialog with fractal landscape in background.

View from atop a virtual ridgeline

Thursday, November 3, 2016

If At First You Don't Succeed, Terrain, Terrain Again

So once again midnight creeped up and I was still busily writing code, so there's still no book review. [sigh]  I need to plan better.  Anyhow, I made a bit more progress.  The UI now has radio buttons, because I used them when I created the form for generating terrain using fractals.  Terrain and the auto-placed objects (trees) in the scene can be completely regenerated in different form at the touch of a few buttons (and a few seconds wait).

Terrain parameters form
As can be seen in the screenshot below, the terrains is less boring than what I showed in yesterday's post.  There are now flat areas, and mountainous ones, not merely an endless mixture of gently-rounded hills and valleys.
Heterogeneous fractional Brownian motion is varied
But I wasn't satisfied with just that.  I added some slope-based texturing.  I found the boundary between rock and other textures a bit too sharp, so I tried another approach as well.

Original slope-based texture.  Note sharpness of texture change at rock boundary.

Transitional blending between rock texture and other textures

Wednesday, November 2, 2016

Procedural terrain in engine

I managed to get some crude procedural terrain generation functioning in the engine test program. The elevation is produced by five octaves of fractional Brownian motion (fBm) with a Perlin noise basis function.  The blend map, which controls which textures appear where, was based upon Perlin noise.  Tree placement was random.
Procedural landscape
Bottom of a hill

It is not without its flaws.  Still, its not too horrible for maybe 90 minutes effort.  The distribution of the noise is a bit of problem.  There's virtually no flat land!  This is a known issue with many fractal algorithms.  I can try out Musgrave's heterogeneous fBm and terrain algorithms or the recent approaches Ian Parberry published in the Journal of Computer Graphics Techniques.

Besides the homogeneity of the terrain (mostly rounded hills and valleys) there are a few other problems.  The blend map generating algorithm is not quite right; only three of the four textures are appearing.  Another problem is with world size and frame rate.  Currently the world is a square measuring 3200 feet on a side, with 10000 trees scattered about.  25000 looks better, but bogs it down.  Some sort of paging may be required, or perhaps instanced drawing.  The last issue is seams at the edges of the sections of terrain.

It "seams" there is a problem.

Seams are a known issue with many terrain partitioning or paging schemes.  It literally presents an edge case at section boundaries.  There are several known solutions: special logic along edges, transitional geometry (shims), etc. that I'll have to dredge back up and look at.

Dynamically generating the terrain on the CPU at startup takes less than ten seconds for about a third of a square mile.  I suspect that can be sped up by moving the terrain generation to GPU, or by generating the sections on an ongoing basis.  In other words, generate only one section at first (where the camera is), then the eight sections around it.  From then on, as the camera moves, only render the camera's section and those in the neighborhood.  Additional sections can be generated asynchronously when it is suspected they're needed, or upon demand, discarding any that are far enough away.  But I also need to do that with the related foliage.  A fascinating challenge for another day.

Good night for now.

Tuesday, November 1, 2016

ColladaFix utilty

Over on GitHub I've released under the MIT license a small utility named ColladaFix, which fixes Collada DAE files so they have relative paths to image files

About 70% of the Collada DAE files I've downloaded from the internet contain references to the texture images in the form of absolute paths. Such paths are inevitably wrong, and the images are almost always in the same folder as the DAE file. This can be fixed with a couple minutes effort per model, but why bother? This utility searches for such absolute paths (e.g. init_from elements having values starting with file:///) and strips the path part form them. A file being processed is automatically backed up (model.dae has a copy named model.dae.bak_20161101T183001 made, for example) and output is written back over the original file

Usage: ColladaFix model.dae

On Windows machines, you can also simply place the executable (or a shortcut to it) on the desktop and drag Collada files to it.

The Best Laid Plans...

I had planned to write a review of Eddie Rickenbacker's memoir of the Great War, Fighting the Flying Circus.  Alas, it was after midnight when I stopped my coding efforts for the evening. A horde of goblins, ghosts, pirates, princesses, and superheroes had paraded past earlier in the evening, and I sent them packing properly sugared up.  The candy ran out before the trick-or-treaters this years; I shall have to stock up better next year.

One of my neighbors was dressed up as a whoopie cushion this year, and was handing out candy in her yard.  She complained that none of the youngsters got it.  I told her not to worry, because the old farts got it.

Anyhow, with that out of the way, I fell to the code and the next thing I knew it was midnight.  In that respect it was fairly productive.  I finished porting my old OBJ file format loader into the new engine. Now I have trees and other models again.  Yay.  I also implemented a very basic first-person walking mode and a first-person flight mode.  Now my menu for switching movement modes is actually useful!

The trees have returned and all is well.
Dialog box informing me that I've crashed while testing flight mode.

And then it was midnight, and any review will have to come another day.  So goodnight, great world!