Jump to content

  • Log In with Google      Sign In   
  • Create Account

Richards Software Ramblings

Voronoi Diagrams

Posted by , 26 August 2016 - * * * * * · 1,592 views
C#., Voronoi, Geometry

A little over two years ago, I first saw Amit Patel's article on Polygonal Map Generation, and thought it was incredibly cool. The use of Voronoi regions created a very nice, slightly irregular look, compared to grid-based terrains. At the time, I had just finished up working on my DX11 random terrain code, and it looked like a fun project to try to tackle.


I then proceeded to spend several months messing around with different implementations of Fortune's Algorithm in C# to get started and generate the Voronoi polygons used to generate a terrain along the lines of Amit's example. At this point, I've lost track of all of the different versions that I've sort of melded together to produce the code that I've ended up with in the end, but some of the more influential are:

The original goal was to create a map generator, suitable for a kind of overworld/strategic level map. But, alas, life happened, and I got bogged down before I got that far. I did, however, wind up with a fairly cool tool for generating Voronoi diagrams. Because I had spent so much time trying to iron out bugs in my implementation of the algorithm, I ended up producing a WinForms application that allows you to step through the algorithm one iteration at a time, visualizing the sites that are added to the diagram, the vertices and edges, as well as the position of the beach and sweep lines. Eventually I also worked in options to show the circles through three sites that define where a Voronoi vertex is located, as well as the Delauney triangulation of the sites.
Posted Image
Voronoi regions, with the edges drawn in white, and the sites as the blue points.

Posted Image
Delauney triangulation, with triangle edges in green.

Posted Image
Showing both the Voronoi regions and the Delauney triangles.

I won't pretend that this code is fantastic, but it's kind of interesting, and I worked at it for quite a while, so better to have it out here than moldering on a hard drive somewhere. If you'd like to see the source, it is available on GitHub. You can also download the executable below if you like - I make no promises that it will work everywhere, but it is a pretty standard .Net 4.5 Windows Forms application. I've also got some videos below the fold, if you'd like to see this in action.


Download Voronoi



Ray Tracing #3: Let's Get Some Actual Rays!

Posted by , 11 April 2016 - - - - - - · 690 views
C#, Ray Tracing

Alright, ready for the third installment of this ray tracing series? This time, we'll get some actual rays, and start tracing them through a scene. Our scene is still going to be empty, but we're starting to get somewhere. Although the book I'm working from is titled Ray Tracing in One Weekend, it's starting to look like my project is going to be more like Ray Tracing in One Year...


Once again, I'm going to put all of the relevant new code for this segment up here, but if you want to see the bits I've missed, check out my GitHub project. We will be circling back to the Vector3 structure I created last time, since I inevitably left out some useful operations...


The core of what a ray tracer does is to trace rays from an origin, often called the eye, for obvious reasons, through each pixel in the image, and then out into our scene to whatever objects lie beyond. We don't have any objects to actually hit, yet, but we are going to lay the groundwork to start doing that next time. Below, you can see the setup of our eye, the image plane, and the rays that shoot from the eye through the image and into the scene beyond.
Posted Image



Ray Tracing #2: Abstractions

Posted by , 11 April 2016 - - - - - - · 601 views
C#, Ray Tracing

It's going to take me considerably longer than one weekend to build out a ray tracer...


Last time, I laid the groundwork to construct a PPM image and output a simple gradient image, like the one below.
Posted Image
This time around, I'm going to focus on building some useful abstractions that will make work going forward easier. This is going to focus on two areas:

  • A Vector3 class, which will be helpful for representing 3D points, directional vector, RGB colors and offsets. We'll implement some useful operators and geometric methods in addition.
  • A Bitmap class, which will represent our output raster and handle the details of saving that raster out as a PPM image file.
Ultimately, we'll be producing the same image as in the last installment, but with considerably less boilerplate code, and lay the groundwork for making our lives much easier going forward when we get to some more meaty topics. As always, the full code is available on GitHub, but I'll be presenting the full code for this example in this post.



Hello Raytracing

Posted by , 18 February 2016 - - - - - - · 724 views
C#, Ray tracing

Whew, it's been a while...


A few weeks ago, I happened across a new book by Peter Shirley, Ray Tracing in One Weekend. Longer ago than I like to remember, I took a computer graphics course in college, and the bulk of our project work revolved around writing a simple ray tracer in Java. It was one of the few really code-heavy CS courses I took, and I really enjoyed it; from time to time I keep pulling down that old project and port it over to whatever new language I'm trying to learn. One of the primary textbooks for that course was Fundamentals of Computer Graphics, aka "the tiger book," of which Mr. Shirley was also an author. Since that's one of the more accessible graphics textbooks I've encountered, I figured this new offering was worth a look. It didn't disappoint.


Ray Tracing in One Weekend is, true to its title, a quick read, but it packs a punch in its just under 50 pages. Even better, it's running at around $3 (or free if you have Kindle Unlimited). I paged through it in a couple of hours, then, as I often do, set about working through the code.


If you want to follow along, I've put my code up on Github, although it's still a work in progress; we're wrapping up a new release at the day job and so I've not had a huge amount of time to work on anything extra. Fortunately, each example I'll be doing here is pretty self-contained, and so all of the code will be up here. We'll start at the beginning, with a simple Hello World a la raytracing.


Posted Image



Finite State Machines, Part 1

Posted by , 02 August 2015 - - - - - - · 894 views
AI, Finite-State Machines, C#
One of my favorite books on AI programming for games is Matt Buckland's Programming Game AI By Example. Many AI programming books lean more towards presenting topics and theories, leaving the dirty work of implementing the techniques and algorithms up to the reader. This book takes a very different tack, with each chapter featuring one or more fully implemented examples illustrating the techniques covered. Even better, it comes in a format similar to a trade-paperback, rather than a coffee table book-sized tome, so it's relatively handy to carry around and read a bit at a time, as programming books go. It is also decidedly focused on the kinds of real-world, relatively simple techniques that one would actually use in the majority of games. And, mixed in the right combinations, these simple techniques can be very powerful, as the second half of the book displays, building an increasingly sophisticated top-down, 2D shooter game.

What I particularly like about this book though, is that while it is presented as a book for programming game AI, it may be the best practical explanation of a number of fundamental AI techniques and patterns that I have seen. The lessons that I learned reading through this book have been just as applicable in my day-job as an enterprise developer as in my hobby work programming games, much more so than what I learned toiling through a semester-long AI course based on Artificial Intelligence: A Modern Approach...

The first real chapter of Mr. Buckland's book (leaving aside the obligatory math primer chapter), is devoted to finite state machines. Finite State Machines are one of the simpler ways of organizing decision making, and are probably one of the most intuitive. I'll let Mr. Buckland's definition stand by itself:

A finite state machine is a device, or a model of a device, which has a finite number of states it can be in at any given time and can operate on input to either make transitions from one state to another or to cause an output or action to take place. A finite state machine can only be in one state at any moment in time.
Matt Buckland Programming Game AI By Example, p.44

I've been working on porting the first example from Mr. Buckland's FSM chapter from C++ to C#, featuring a mildly alcoholic, spaghetti Western gold miner named Bob. I'm going to focus mostly on the FSM-specific code here, but you can get the full code from https://github.com/ericrrichards/ai/tree/master/trunk/WestWorld1.

Posted Image


Setting up Chocolate Wolfenstein 3D in Visual Studio 2013

Posted by , 20 May 2015 - - - - - - · 1,206 views
C++, Wolfenstein 3D, Id Software
For the past few weeks, I've been once again noodling on the idea of starting a .NET port of a classic Id FPS. As a kid on my first computer, an off-brand 486 with DOS, I just hit the tail end of the good old days of shareware. And amongst all the floppy disks of kiddy and educational software and sliming Gruzzles couldn't really hold a candle to exploring Indiana Jones and the Last Crusade-esque Gothic castles and knifing Nazis.

While the original source-code for Wolfenstein 3D has been available for some time, it is a bit of a slog trying to wade through C code that was written 20 years ago, with near and far pointers, blitting directly to VGA memory, and hand-rolled assembly routines, let alone build the project successfully. Consequently, converting over to C# is a bit of a struggle, particularly for some of the low-level pointer manipulation and when loading in binary assets - it is very helpful to be able to step through both codebases side by side in the debugger to figure out any discrepancies.

Because of these difficulties, I have started looking at the Chocolate Wolfenstein 3D project, by Fabien Sanglard. Mr. Sanglard is a great student of the Id Software engine source code, and has done several very nice writeups of the different engines open-sourced by Id. He was even planning on writing a book-length analysis of Wolfenstein 3D, which hopefully is still underway. Chocolate Wolfenstein 3D is a more modernized C++ conversion of the original Id code, with some of the more gnarly bits smoothed out, and using SDL for cross-platform window-management, graphics, input, and sound. Even better, it can be built and run using current versions of Visual Studio.

The only problem I had with the Chocolate Wolfenstein 3D GitHub repository is that it is missing some dependencies and requires a small amount of tweaking in order to get it to build and run on Visual Studio 2013. These steps are not particularly difficult, but if you simply clone the repo and hit F5, it doesn't work right out of the box. If you are working on a Mac, there is a very nice guide on setting up the project in XCode, but I have not found a similar guide for Windows, so I decided to document the steps that I went through and share those here.

Posted Image


Model Loading Code Updated to AssimpNet 3.3.1

Posted by , 11 February 2015 - - - - - - · 1,316 views
AssimpNet, C#, 3D Models and 1 more...
Just a quick update today. I've updated the 3D model loading code to use the latest version of AssimpNet that is on Nuget now. The latest code is updated on GitHub.

The biggest changes appear to be that the AssimpImporter/Exporter classes have been merged into a single AssimpContext class that can do both. Some of the GetXXX methods to retrieve vertex elements and textures also appear to be replaced with properties. The way that one hooks into the internal Assimp logging has also changed. I haven't discovered many other changes, besides some additional file format support yet, but I haven't gotten around to really explore it that closely. Mildly irritating that the interface has changed here, but hey, at least it is being actively worked on (which is more than I can say for some of my stuff at times...).

I've been quite busy with work lately, so I haven't had a huge amount of time to work on anything here. I'm also a little burned out on doing straight DX11 graphics stuff, so I think I'm going to try to transition into doing some more applied work for a while. I've got some stuff in the pipeline on making simple games with Direct2D, and ideally I'd like to get involved with One Game a Month, to give me a little additional motivation.


Serving HTML5 Video using Nancy

Posted by , 17 January 2015 - - - - - - · 1,282 views
C#, Nancy, OWIN, HTML5 Video and 1 more...
Not really game related, but something I've been working on lately.

Recently, I have been using OWIN a good deal for developing internal web applications. One of the chief benefits of this is that OWIN offers the ability to host its own HTTP server, which allows me to get out of the business of installing and configuring IIS on windows, which is one of the main points of pain when deploying the products I work on to our customers. Unfortunately, when I first started using OWIN, there was not a version of ASP.NET MVC available that was compatible with OWIN. Most of my previous experience with programming web servers has been based on MVC (except for briefly experiencing WebForms hell), so finding a similar framework that was compatible with OWIN was one of my first priorities.

In my search, I discovered Nancy, a fairly similar MVC-style framework which offered OWIN support. It also was capable of using the same Razor view engine as ASP.NET MVC, with some minor differences, so I was able to convert existing IIS ASP.NET MVC applications to OWIN/Nancy using most of the existing views and front-end code. At some point I plan to write an article illustrating how one would do this type of conversion, but for now, I'm going to examine one particular gotcha I discovered when converting my personal Netflix-type video application to OWIN/Nancy: serving HTML5 video files.


Geodesic Sphere Tessellation

Posted by , 21 December 2014 - - - - - - · 1,430 views
C#, SlimDX, DirectX 11 and 1 more...
A couple of weeks ago as I was browsing HackerNews, I stumbled onto an article about creating spherical procedural maps by Andy Gainey. Procedural terrain/map generation is always something I find interesting, having grown up slightly obsessed with Civilization and its successors. Various methods of tiling a sphere in order to make a game grid have been bouncing around the back of my mind for a while now - unfortunately finding time to explore some of those ideas has been problematic. But, after reading through Mr. Gainey's piece and looking over the source for his demo, I got inspired to take a stab at something similar. My first attempt was to try to directly port his Javascript implementation, which got bogged down in the impedance mismatch between going from JS to C# and WebGL to DirectX at the same time, so I stepped back, and decided to come at the idea again, working in smaller steps.

The first step was to generate a spherical triangle mesh. For this purpose, the spherical mesh that we have previously worked with is not very well suited, as its topology is very inconsistent, particularly around the poles, as you can see in the screenshot below. Instead of this kind of lattitude/longitude subdivision, we will instead use an alternate method, which starts from an icosahedron, then subdivides each face of the icosahedron into four triangles, and finally projects the resulting vertices onto the sphere. This produces a much more regular tessellation, known as a geodesic grid, as you can see in the right screenshot below. This tessellation is not without artifacts - at the vertices of the original icosahedron, the resulting geodesic will have five edges, while all other vertices have six edges, similar to a real-life soccer ball.

Posted Image
Lattitude/Longitude tessellation, with artifacts at the poles
Posted Image
Geodesic tessellation

Frank Luna's Introduction to 3D Game Programming with Direct3D 11.0, Chapter 6, presented a method of generating of generating a geodesic sphere, which I previously skipped over. The code for this example is based upon his example, with some improvements to eliminate redundant vertices.

The code for this example can be obtained from my GitHub repository.


HLSL Cookbook: Directional Lighting

Posted by , 24 November 2014 - - - - - - · 926 views
HLSL, C#, SlimDX, Direct3D11 and 2 more...
Moving along with Chapter 1 of the HLSL Development Cookbook, we're on to handling directional lighting. I've covered most of the theory behind directional lighting previously, so this is going to be quite brief.

To recap, in case anyone is unfamiliar with the term, a directional light is a light which illuminates the entire scene equally from a given direction. Typically this means a light source which is so large and far away from the scene being rendered, such as the sun or moon, that any attenuation in light intensity, via the inverse-square law or variations in the direction from any point in the scene to the light source location are neglible. Thus, we can model a directional light simply by using a directional vector, representing the direction of incoming light from the source, and the color of the light emitted by the light source.

Generally, we model the light hitting a surface by breaking it into two components, diffuse and specular, according to an empirical lighting equation called the Phong reflection model. Diffuse light is the light that reflects from a surface equally in all directions which is calculated from the angle between the surface normal vector and the vector from the surface to the light source. Specular light is light that is reflected off of glossy surfaces in a view-dependant direction. This direction of this specular reflection is controlled by the surface normal, the vector from the surface to the light, and the vector from the surface to the viewer of the scene, while the size and color of the specular highlights are controlled by properties of the material being lit, the specular exponent, approximating the "smoothness" of the object, and the specular color of the material. Many objects will reflect specular reflections in all color frequencies, while others, mostly metals, will absorb some frequencies more than others. For now, we're only going to consider the first class of materials.

Below you can see a model being lit by directional light, in addition to the ambient lighting we used in the last example. Here, the directional light is coming downward and and from the lower-left to the upper-right. Surfaces with normals facing more directly towards the light source are lit more brightly than surfaces which are angled partly away from the light, while surfaces facing away from the light are lit only by ambient lighting. In addition, you can see a series of brighter spots along the back of the rabbit model, where there are specular highlights.

Full code for this example can be downloaded from my GitHub repository.

Posted Image


October 2016 »

161718192021 22

Recent Comments

Latest Visitors