JavaScript fun for 3D

Yesterday I wrote about a few of the JavaScript libraries I found that would help solve some needs at Day Job (tm).  Today I'll mention another one I played with yesterday evening that may be of some interest.  I'd heard of three.js before, as it was used in the web-based planet generator I've mentioned in the past, but this was the first time I really looked at in depth.

three.js is a JavaScript library for loading, displaying, and interacting with 3D graphics inside a web browser.  WebGL was introduced as a web version of the venerable OpenGL technology years ago, but OpenGL (and, by extension, WebGL) are very low level.  three.js provides a higher-level interface, with support for loading models in various formats.  The website offers a multitude of example web pages with working examples.  It even has a few examples using fractal methods to generate a terrain that can be moved around in.

Alas, there aren't built-in loaders for the formats I need for Day Job (tm), but that's simply a matter of writing a compatible loader, or a separate converter program to take models in the formats we have them in and convert them to formats three.js can load.

Beyond work, though, it has the potential to be useful as the display end for some of the other things I've been experimenting with for fun.  I wouldn't want to write the code to generate things in JavaScript, but a web page using three.js to display the results would be entirely feasible. 

Surprisingly, three.js even offers a web-based 3D scene editor.  It isn't Blender, SketchUp, 3D Max, or AutoCAD, and there's no real mesh modeling support, only primitives like box, sphere, cylinder, torus, etc.  Nevertheless, it can be used to create a 3D scene relatively easily, and does have import capabilities so that models in other formats, like OBJ, can be imported.  It can export to OBJ, STL, and its own JSON-based format.  It can even publish scenes and a web page to view the scene.  Pretty slick.

Anyhow, if you need 3D on your web page, this is worth checking out.

Thickening with Falloff

Yesterday I was looking for a way to generate decreasing intensity extending outward from initial shapes.  It is something that  may be useful for some other techniques going forward, though is of some limited use in and of itself, and the effect itself is somewhat interesting.  It might look nicer with some smoothing, though.

Here's a more : Given a raster representation of some initial geometry, this program calculates distance of pixels from the initial geometry, then visually represents the distance as a gradient between white (initial geometry) and black (at and beyond threshold).

The program has two required command line arguments (input and output files) and an optional argument specifying the threshold in pixels.  Here's an example of the arguments I was using:

Thicken.exe -in C:\test\input.png -out C:\test\output.png -threshold 48

In the input image, black is treated as no geometry, any other color counts as geometry.

Input was a 512 x 512 PNG file

Output image with a 48 pixel falloff threshold

I'm releasing the C# source code under the MIT license, with no warranty.  Use at own risk.  Since I used the Vector2 struct you'll need to add the System.Numerics.Vectors package (which can be done with Install-Package System.Numerics.Vectors -Version 4.4.0 from the Package Manager Console in Visual Studio) or substitute your own implementation of Vector2.

using System;
using System.Collections.Generic;
using System.Drawing;
using System.Linq;
using System.Numerics;
using System.Text;
using System.Threading.Tasks;

namespace Thickening
{
    class Program
    {
        private static void ReadImageAsMap(string fileName, out int[] map,
            out int width, out int height)
        {
            // Read input image into map array.  Any non-black pixel is a starting point.
            Bitmap inputImage = (Bitmap)Bitmap.FromFile(fileName);
            width = inputImage.Width;
            height = inputImage.Height;
            map = new int[width * height];
            for (int y = 0; y < height; y++)
            {
                for (int x = 0; x < width; x++)
                {
                    int i = y * width + x;
                    Color c = inputImage.GetPixel(x, y);
                    if (c.R > 0 || c.G > 0 || c.B > 0)
                    {
                        map[i] = 0;
                    }
                    else
                    {
                        map[i] = -1;
                    }
                }
            }
        }

        private static void Thicken(int[] map, int width, int height)
        {
            // Find starting points (zero).
            List<Vector2> current = new List<Vector2>();
            for (int y = 0; y < height; y++)
            {
                for (int x = 0; x < width; x++)
                {
                    int i = y * width + x;
                    if (map[i] == 0)
                        current.Add(new Vector2(x, y));
                }
            }

            // Iterative set distance around starting points or points
            // where distance has already been calculated.
            while (current.Count > 0)
            {
                List<Vector2> next = new List<Vector2>();
                foreach (var curr in current)
                {
                    int cx = (int)curr.X;
                    int cy = (int)curr.Y;
                    int val = map[cy * width + cx];

                    // Look at neighbors.
                    for (int y = cy - 1; y <= cy + 1; y++)
                    {
                        if (y < 0 || y >= height) continue;
                        int ny = y;

                        for (int x = cx - 1; x <= cx + 1; x++)
                        {
                            int nx = x;
                            if (nx < 0) nx = width - 1;
                            else if (nx >= width) nx = 0;

                            int j = ny * width + nx;
                            int nval = map[j];

                            if (nval < 0)
                            {
                                Vector2 neighbor = new Vector2(nx, ny);
                                if (!current.Contains(neighbor) 
                                    && !next.Contains(neighbor))
                                {
                                    map[j] = val + 1;
                                    next.Add(neighbor);
                                }
                            }
                        }
                    }

                }
                current = next;
            }
        }

        private static float Clamp(float min, float val, float max)
        {
            if (val < min) return min;
            if (val > max) return max;
            return val;
        }


        private static void WriteMapAsImage(string fileName, int[] map, 
            int width, int height, float threshold)
        {
            Bitmap outputImage = new Bitmap(width, height, 
                System.Drawing.Imaging.PixelFormat.Format32bppArgb);
            for (int y = 0; y < height; y++)
            {
                for (int x = 0; x < width; x++)
                {
                    int i = y * width + x;
                    int val = map[i];
                    Color c = Color.Black;
                    if (val >= 0)
                    {
                        // Calculate percentage closeness to initial geometry.
                        // Intensity is 100% at initial geometry, 
                        // 0 % at or beyond threshold.
                        float closePercent = (threshold - val) / threshold;
                        closePercent = Clamp(0, closePercent, 1.0f);
                        int val2  = (int)(closePercent * 255.0);
                        c = Color.FromArgb(val2, val2, val2);
                    }    
                    outputImage.SetPixel(x, y, c);
                }
            }
            outputImage.Save(fileName);
        }


        private static string ParseForArgumentValue(string[] args, 
            string argumentName, bool caseInsensitive = true, 
            string defaultValue = null)
        {
            if (args == null || args.Length == 0)
                return defaultValue;

            string prevArg = "";
            foreach (string arg in args)
            {
                bool isMatch = false;
                if (caseInsensitive)
                    isMatch = (prevArg.ToLower() == argumentName.ToLower());
                else
                    isMatch = (prevArg == argumentName);
                if (isMatch)
                    return arg;
                prevArg = arg;
            }
            return defaultValue;
        }


        static void Main(string[] args)
        {
            if (args == null || args.Length == 0)
            {
                string msg = "Thicken.exe -in input.png -out output.png [-threshold 32]";
                Console.Error.WriteLine(msg);
                Environment.Exit(1); 
            }

            string input = ParseForArgumentValue(args, "-in", true, null);
            string output = ParseForArgumentValue(args, "-out", true, null);
            string thresholdString = ParseForArgumentValue(args, "-threshold", true, "32");
            int threshold = 32;
            bool thresholdOk = Int32.TryParse(thresholdString, out threshold);
            if (!thresholdOk)
            {
                string msg = "Invalid value for -threshold argument.  " +
                    "Omit -threshold argument or supply a valid positive integer " + 
                    "less than two billion.";
                Console.Error.WriteLine(msg);
                Environment.Exit(2);
            }

            try
            {

                int width, height;
                int[] map;
                ReadImageAsMap(input, out map, out width, out height);
                Thicken(map, width, height);
                WriteMapAsImage(output, map, width, height, threshold);
            }
            catch (Exception ex)
            {
                Console.Error.WriteLine("Unexpected error: {0}", ex.ToString());
                Environment.Exit(3);
            }
        }
    }
}

Coming Soon: Shapes!

Coming in the near future shall be Shapes!  Shapes is a (possibly) exciting tutorial series on some programming techniques that do interesting things with shapes.  However, I've still got some more example code to finish, text to write up, screenshots to take, etc. to give it some polish.  Expect something sometime next week.  Until then, I leave with you with a few simple, not-particularly-exciting images that emerged from parts 1 and 2.  (Yes, parts 3 and later are some

Example output from part 1

Example output from part 2

Example output from part 3

    

Essential Geometry 2: Basic operations

Yesterday's post covered geometric primitives and basic shapes for use in a 3D procedural modeling framework.  Today's post covers some basic operations that can be performed using those primitives and shapes.

We'll start off with the basic transformation operations.  A geometric primitive can be translated (moved), rotated (orientation adjusted), or scaled (made larger or smaller).  These are fairly basic operations which are well understood, and are typically performed using linear algebra (matrix math). Since this is such a well-documented area, I won't address it in great depth, other than to say these are truly fundamental operations for 2D and 3D geometry on a computer.  Even if you're not planning on procedural modeling, any framework needs to support them.

Figure 1: Transformation operations

Next we'll discuss three operations for generating 3D content from 2D polygons.  Extrusion, revolution, and sweeping can all be powerful operations.  I mentioned extrusion briefly a few posts back.  It can be used to generate tubes, columns, boxes, ducts, buildings, etc. from a simply polygon like a rectangle, octagon, etc.  Implementing extrusion is fairly simply.  Make a copy of the polygon. Translate the copy along the extrusion vector (red arrow in figure 2).  Then for each edge of the original polygon, create a new rectangular face that connects that edge with the corresponding edge on the copy.

Figure 2: Extrusion

Revolution is similar but a bit more complex.  With revolution, a polygon is swept through space in a circular arc around an axis.  (In figure 3, the axis is shown as the red vertical line.)  The arc may be partial (e.g. 90 degrees) or may be a complete circle.  To implement, we perform the rotation as an iterative process.  Make a copy of the polygon and rotate it some fraction of the desired rotation.  As with extrusion, create faces between edges of the previous polygon and the next polygon.  Repeat the process until the desired rotation is accomplished.

Figure 3: Revolution

Sweep is similar to revolution, but rather than simple rotation about an axis it involves following a path.  The path could be defined by a line segment (like extrusion), an arc (like revolution), a polyline, or a spline.  I cannot fully describe implementation at this time as it is something I am actively working on a proper implementation for, as I intend to use sweep for road and railroad shapes.

Figure 4: Sweep

Constructive solid geometry (CSG) operations are used to manipulate 3D solids (polyhedrons) much like boolean or set operations.  A union combines two solids.  An intersection yields the portion of solids that overlap.  A difference removes that part of solid A which solid B overlaps.  The simplified 2D equivalent of these operations is shown in figure 5.

Figure 5: Constructive solid geometry (CSG) operations

You may be wondering why CSG is useful.  If you wanted to create a dimpled cube, you could take the difference between a cube and a sphere.  If you wanted a thick-walled hollow tube, you could take the difference between one cylinder and a cylinder of smaller diameter.  You could use CSG to put window and door shaped holes into walls, carve star-shaped patterns into a box representing a frieze, or carve or raise decorative elements for columns.

Figure 6: Some scenarios for CSG use

CSG operations can be implemented using BSP (binary space partitioning) trees.  In Game Programming Gems 5, Octavian Marius Chincisan has an article on doing so, "CSG Construction Using BSP Trees," with an accompanying C++ implementation.  The OpenJSCAD uses a JavaScript implementation (CSG.js) to perform CSG operations inside a web browser, rendering them via OpenGL.  I ported CSG.js to C# but have yet to fully integrate it into anything just yet.  The tests for it produce output files which I can view using Blender.

Figure 7: Rendering of a shape produced using CSG operations.

There are more useful operations to discuss - such as those used in CGA Shape, and some common operations for edges - but those will wait for a future day.  This post covers some of the basic essential operations and provides some details to aid in implementation.

Essential Geometry 1: Primitives and Basic Shapes

I've been thinking about the architecture for dealing with procedural generation for material culture: buildings, bridges, roads, fountains, etc.  I mentioned a bit in previous posts about procedural generation of buildings, terrain, and even language.  The building blocks of these different types of procedural content vary greatly, but for material culture it is represented in a virtual world by geometry.  Culture and semantics may drive arrangement and meaning, but the representation ultimately takes the form of geometry.

Mostly it is simple angular or curved geometry, not organic shapes.  As such, such geometry is often easily described in terms of primitives.  The most basic primitives are simple, generic representations of shapes in zero to three dimensions.  In the example below, a four-sided rectangle is shown for the face (polygon), but that could as easily be a hexagon, an octagon, etc.  Likewise, the polyhedron could be a dodecahedron, a tetrahedron, or an arbitrary mesh.

Figure 1: Essential geometric primitives

Because rendering 3D graphics usually requires a similar representation to what I've just described (triangles are best), more complex representations are built upon these basic geometric primitives. When rendering, even a cylinder, sphere, cone, or torus is an approximation in the form of a polyhedron.  (Ray tracing is sometimes an exception.)  All of the shapes in the figure 2 below could be represented as either a face/polygon or as a polyhedron.

Figure 2: Useful basic shapes

For procedural modeling, being able to easily create the basic shapes above can be quite useful. However, we still only need to have classes that represent the four primitives in figure 1. Any shape from figure 2 can be generated as an instance of one of the classes from figure 1.  A shape factory can generate the required instances based upon supplied parameters.  As such, a class representing each basic shape is not required in all situations; I do not plan to create such classes, and plan to rely upon a shape factory utility class to generate instances of the figure 1 classes that represent figure 2 shapes.

There are well-known algorithms for most of them.  The GLUT library used with OpenGL contains implementations of algorithms for generating the sphere, cube, cone, torus, dodecahedron, octahedron, tetrahedron, icosahedron, and the ever-populate teapot shapes.  The FreeGLUT library is an open-source (MIT X licensed) alternative to GLUT so you could review that source code for examples, or search online.  Paul Bourke's web site has descriptions and details for some of them, such as the superellipsoid.  

Some of the 3D shapes can also be produced by performing an extrusion or revolution of a sphere or rectangle.  I'll address that more in a future post on geometric operations that should be supported in order to provide for procedural modeling capabilities.   This post has covered the primitives and the basic shapes at a high level.  More details will be discussed in future posts.

  

Dealing with the Great Big World 3

I've discussed some of the terrain-related portions of dealing with the Great Big World before.  I'm going to touch on another aspect in this post - buildings.

I'm working on the (software) architecture for a fresh prototype for the splines and sketching that I've posted about in the past.  I'd originally planned to continue work with that prototype, but the architecture is just poorly suited as it stands now.  I'll be reusing a lot of the code, but trying to shoehorn the changes into the original prototype wasn't working well.  Nothing from that is even close to ready to show, though.  So let's discuss buildings.

The old prototype, showing a river, road, railroad, and three buildings.

There are three buildings in the screenshot above, represented by the dark blue-gray polygons at upper left, near where the railroad crosses the road (to get to the other side).  For a decent 3D representation, what would we do?  We could substituted manually-modeled building models, be they free, purchased, or created personally.  But imagine trying to store a 3D model for every planet on a building, let alone model them all.  Its not very practical, although it is perfectly feasible to do for some signature structures, such as a few buildings in a national capital, or the tallest, signature skyscrapers in a city.  What does that leave us as an alternative?  Procedural modeling of buildings.

That's start with a very simple form of procedural modeling.  Our starting point will be the polygons in the map that represent buildings.  Each such polygon is the footprint of a building.  If each such a polygon were extruded upwards, we would get a polyhedron from each polygon.

Extrusion process - from polygon to polyhedron

But that only gives us a simple three dimensional form.  We could apply a texture to it.  If there's a nice tiling (repeatable) texture for brick or stone, it could allow one to accept the polyhedron as a building - especially if some windows and doors were part of the pattern.  This may even work well enough in some scenarios, in fact.  If each polyhedron had a random texture from a set of of such textures assigned, the buildings wouldn't all look alike, either.  A couple examples of such textures, generated via Filter Forge 5 filters, are shown below.  It might be good enough for a flight simulator or a train simulator, or for more-distant background buildings in any game or simulation.

Brick texture created using filter Bricks version 1

Window in wall texture created using filter Window gen

For buildings that are more close up, as in a driving game, a first person shooter, or just a VR scenario that involves walking down the street, it'll fall flat pretty fast.  Thankfully, there are solutions.  There are plug-ins and packages for many game engines and modeling tools that will help with some of this.  Unity features the BuildR asset in its Asset Store, for example.  And then there's perhaps the ultimate expression of procedural building generation, ESRI's CityEngine.

ESRI is primarily a GIS (geographic information systems) company, producers of the ArcGIS product.  However, they purchased a company out of Zurich named Procedural, Inc. that had produced a product called CityEngine.  CityEngine can create entire cities, including detailed building models.  For building generation, it uses something called CGA Shape Grammar.  CGA Shape Grammar is discussed at length in a 2006 paper by Pascal Mueller, Peter Wonka, Simon Haegler, Andreas Ulmer, Luc Van Gool, Procedural Modeling of Buildings.  You can look at that paper and the online documentation for CityEngine if you want to learn all the details, but I'll cover a few high points below, greatly simplified.

Geometric primitives

Basically, CGA Shape Grammar is a production system like L-systems in which a set of rules are defined.  When fed some initial data (such as the polygon of the building footprint) the rules are iteratively applied and a building is generated.  The rules can use operators such as extrude and split to manipulate the 3D dimensional polyhedron or the polygon faces.  Extrude works in much the manner as described above.

Split lets a polyhedron or polygonal face be split into multiple parts, so different rules can be applied to different parts.  For example, in the image below a polyhedron has been split in two and two different textures have been applied to the top half and the bottom half.  This is a common scenario.  Note the difference in fenestration between the first and second stories in the photo.

Polyhedron split process

Note difference in windows between first and second floors.

Implementing split of a polyhedron or polygon is fairly simple.  Since the polyhedron is little more than a collection of polygons, splitting a polyhedron is simply a matter of splitting the polygons. A plane defines where splitting takes place.  See Graphic Gems V "Spatial Partitioning of the Polygon by a Plane" for details on implementing such an algorithm.

Polygon split process

The split operation in CGA Shape can take a set of mixed absolute and relative dimensions for the split operation.  This involves calculating a set of planes to split by.  The splits are then performed sequentially.  The outputs of the split can then be addressed by further rules.

I am not planning to implement the full CGA Shape Grammar system as described in the paper. Even the rule-based approach is probably more than I care to bother with.  However, a few of the operations defined therein could be useful.  If the CGA Shape Grammar style of extrude, split, and repeat operations are implemented as C# methods that are part of a broader set of geometric primitives and procedural modeling capabilities, C# code or PowerShell scripts could access them. Combined with Constructive Solid Geometry (CSG) techniques they could provide a very compact representation of buildings without requiring prohibitively-extensive modeling.  Can a few scripts generate the buildings for an entire world?  Perhaps.

(PS - The roof generating operations would be nice to have for residential architecture.  More thoughts on that later.)

Dealing with the Great Big World 2

My post yesterday entitled "Dealing with the Great Big World" failed to fully make clear what part of the "Great Big World" problem was being addressed. It is the storage aspect which is being addressed there.  Storing a complete high resolution elevation data set for a planet as raster data, or contours, or meshes, is possible but impractical without consuming extremely large quantities of disk space.  The combination of coarse raster data and details via vector-based definitions that can drive a procedural representation offer a better option with respect to stoarage size.

This is part of the reason for the "spline" series of posts I'm making.  Splines for defining mountain ridgelines have a great potential for a compact representation of mountain ranges.  Alternately, the splines can define the center line of a wider ranger.  Note that I'm using "splines" here as a shorthand for any open linear skeletal primitive, including not only the rounded nonuniform splines used in my "spline" examples but also line segments, polylines, etc.  They're all transformed "behind the scenes" to a sequence of one or more line segments.

Using a related technique, a polygon can be used to define the boundaries of a larger and less linear area of mountains.  This also applies to other closed primitives such as squares, circles, etc.  All of these can be converted into a closed sequence of line segments.

The other two areas of concern in dealing with the "Great Big World" are coordinate precision and the rounded shape of the world.  How those are resolved in conjunction with the solution I mentioned above is unclear.  Persisting the coordinates that define splines (and other skeletal primitives) using double precision numbers may be part of the solution, as could using the "segmented distance" approach for perssistence.  Storing coordinates as double precision latitude and longitude might work.  In all cases, conversion to an appropriate coordinate system for rendering will be required.  It is entirely possible that conversion for preprocessing will also be required.  I have more thinking to do in that regards.

On the Road to Splines 5

There may be more this evening, but for now a few thoughts came up while I was eating lunch. Under the hood, so to speak, the set of parameters for spline-based terrain generation can be quite large.  There can easily be tens of different parameters whose exact impacts may not be readily understandable when presented to a casual user in the GUI.  The solution I've thought up is presets.

An excellent example of the presets concept, and my immediate source of inspiration, is Filter Forge, a 2D image effects program.  The "filters" in Filter Forge are effects that can be applied to an image, and are built upon a node graph and/or code.  They can have a large number of parameters.  To simplify use a Presets list can be used that sets the parameters to values that are geared toward a particular end.

A similar concept fits the spline-based terrain concept very well.  For example, mountain terrains will involve multiple parameters describing the general dimensions (width, height, slope, etc.), noise generation, and erosion.  A simple set of presets for different mountain forms would make this much simpler.  For example, the Canadian Rockies are more eroded than the more southerly Rocky Mountains, which are rougher than the Appalachians, which are more strongly oriented into parallel ridges than the Catskills.  So there could be Canadian Rockies, Rocky Mountains, Appalachian, and Catskill presets.

Anyhow, enough blogging.  I finished lunch and need to get back to work.

On the Road to Splines 4

Yesterday I posted about the spline progress.  I made only a little progress coding tonight, as I spent much of the evening out enjoying the Christmas lights.  Still, I have made progress towards making the mountains work right.  Elevation is computed by calculating distance from the center line of the spline outwards, and using simple linear interpolation between base elevation and elevation at the ridge line.

Mountain spline is now colored to represent elevation.  Note lighter color along ridge line.

This is equivalent to the absolute simplest form of mountain generation by Soon Tee Teoh in his 2008 paper "River and Coastal Action in Automatic Terrain Generation."  All points along the ridge line are of the same height.  The rest of Teoh's ideas should be easy enough to incorporate, as should some of my own ideas.

However, much of that will have to wait.  This application increasingly needs refactoring.  For example, I think it needs to incorporate some limited level-of-detail (LOD) capability.  At minimum, it needs a symbolic cartographic representation for when viewed zoomed out, and a detailed geometric representation when zoomed in.  Also, there is that whole laundry list of items from my earlier post.  Those also need to be addressed.

Beyond that, though, I have that town analysis I mentioned in a post yesterday that needs to continue. I'm putting together a small database to let me record detailed data collected from digital Sanborn maps.  I'm interested in generating terrain, but I'd also like to be able to generate believable towns upon those terrains, as well.

For those curious about the underlying algorithm, I present the C# code snippet below.  A segment of mountain is rendered to a height map using the code.  This is the initial version of the code used for the mountain in the screenshot above.  A mountain is defined by a spline that represents the ridge line of the mountain.  The spline is segmented into individual line segments.  Height declines linearly based upon a point's distance from the ridge line segment.

private void RenderLineSegment(Vector3 start, Vector3 end, float height1, float height2, 
    float slope, int offsetX, int offsetY, float[,] heights)
{
    // Calculate the maximum distance the mountain may extend from 
    // the ridge line.
    float maxExtent = (1 / slope) * Math.Max(height1, height2);
    float maxExtentSq = maxExtent * maxExtent;

    // Calculate the dimensions of this segment of mountain.
    Vector3 min = Vector3.Min(start, end) - 
        new Vector3(maxExtent, maxExtent, 0);
    Vector3 max = Vector3.Max(start, end) + 
        new Vector3(maxExtent, maxExtent, 0);

    // Calculate segment length, and difference in height between 
    // start and end points.
    LineSegment seg = new LineSegment(start, end);
    float segLength = Vector3.Distance(start, end);
    float deltaH = height2 - height1;

    // Render the height (elevation) data.
    for (float y = min.Y; y < max.Y; y++)
    {
        for (float x = min.X; x < max.X; x++)
        {
            Vector3 curr = new Vector3(x, y, 0);
            Vector3 nearest = seg.NearestPointOnSegment(curr);
            float distSq = Vector3.DistanceSquared(curr, nearest);
            if (distSq <= maxExtentSq)
            {
                // linear interpolate height at point on segment.
                float ndist = Vector3.Distance(nearest, start);
                float nPercent = ndist / segLength;
                float h = height1 + (deltaH * nPercent);

                // linear interpolate height at current point.
                float extent = (1 / slope) * h;
                float currPercent = 1 - ((float)Math.Sqrt(distSq) / extent);
                float currH = currPercent * h;

                // set elevation only if greater than elevation already 
                // present at point.
                int gridX = (int)x + offsetX;
                int gridY = (int)y + offsetY;
                heights[gridX, gridY] = Math.Max(heights[gridX, gridY], currH);
            }                  
        }
    }
}

On the Road to Splines 3

I continued work on splines a little bit at a time over the past few days.  The results aren't perfect, but can at least be shown.  Instead of mere thin black lines, we now have roads and railroads.

As you can see from the screenshot below, there are a few areas that need to be addressed.  The left-most roads were drawn using the polyline tool.  You can see the problems at the corners.  Less obvious are the smaller artifacts along the spline.  These need to be addressed to get a smooth shape.

Railroads and roads drawn using lines, polylines, and splines

The other big areas that obviously need to be addressed are the intersections and crossings.  Where roads intersect other roads, or tracks intersect other tracks, additional rendering logic is required. Where roads and tracks cross, there is also the need for more rendering logic.  At the moment, all they do is overlap.

Related to the last paragraph is the current total lack of any topological representation.  Each line segment, polyline, spline, or polygon is essentially independent of all others.  A graph structure for each type is required to add some semblance of order and contribute to improves in the areas mentioned above.

Road, railroad, river, and a trio of buildings

Just a quick note about current rendering.  The example application is implemented in C# and Windows Forms, with the graphics being rendered using GDI+.  That's not necessarily the long-term solution, as I hope to integrate this code with the 3D stuff I've also posted about here.  It may work well enough for basic editing operations, though - in which case I need some zooming and panning controls, as well as the ability to load and save what has been drawn.

I'll post more on this when there's been more progress worth sharing.

Sine, Sine, Everywhere a Sine

Lord, give me a sine, please!

Sine wave

Alas, I haven't made enough progress today to have something to show.  I will briefly mention that in the approach to terrain generation that I'm thinking of, various functions such as sine, cosine, sawtooth, and triangle waves can be combined with linear shapes (such as polylines, splines, etc.) and noise functions to produce terrain.

This is hardly novel, in and of itself.  Several articles on the subject have been written over the past decade.  Here's a brief list of some of them.

Soon Tee Teoh.  River and Coastal Action in Automatic Terrain Generation.  Proceedings of the 2008 International Conference on Computer Graphics & Virtual Reality, CGVR 2008, July 14-17, 2008, Las Vegas, Nevada, USA

Houssam Hnaidi et al.  Feature based terrain generation using diffusion equation.  Pacific Graphics Volume 29 (2010), Number 7

J.D. Génevaux et al.  Terrain Modeling from Feature Primitives.  Computer Graphics Forum 2015

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.

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.

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.

Function Junction

Due to still being ill, I've not made demonstrable progress on much of anything that I can show you. And between tiredness and illness, I can't really apply my mind to writing reviews on any of the books I've recently finished, although I shall mention that I've recent started reading Arch Whitehouse's The Zeppelin Fighters and find it engrossing.

One thing I did manage to complete was a very small program for function graphing.  I had some thoughts on using trigonemetric and other math functions, and combinations thereof, for various simulation or generation purposes.  Light levels and sun elevation for day/night cycles, terrain generation, and waves can all be modified with functions.

Absolute value of sine: y = abs(sin(x))

Sawtooth function: too messy for including in the caption, so see below.

private double Sawtooth(double x)

{

double a = 2;

double t = x;

double toa = t / a;

double y = 2 * ((toa) - Floor(toa + 0.5));

return y;

}

private double Clamp(double value, double low, double high)

{

if (value < low) return low;

if (value > high) return high;

return value;

}

Clamped sine:  y = clamp(sin(x), 0, 1)

None of these are likely to be original ideas, as I'm aware of some use of them for such purposes.For example, cosine is used for mountain ranges in the "River and Coastal Action" article I've mentioned before.  This tiny little program is helping me do a little visualization of how these functions work. There are math programs that can do this, I think (my TI calculator can do some of it), but whatever functions I come up with will have to be expressed in code anyway so I can use them in other code, so being able to quickly prototype is nice.

Some of the functions are useful in and of themselves, while otherwise would need to be combined with other techniques (such as noise) to be of use.  For now, though, I shall bid the world a fond goodnight and get some sleep.