Before we jump into algorithms, a few things. The algorithm I'm about to lay out is a version of the Bowyer-Watson algorithm I've referenced in a previous post. It's been pretty heavily modified since, and it was not my initial intent for it to be thins similar. Nonetheless, I think that my implementation has better asymptotic time than any implementation of the original I've yet seen, since (as we'll see) the most intensive parts of the algorithm (most of which were related to searches over the point set) have been offloaded to a simple graph search. We'll also be looking at things through the lens of the Voroni Graph, rather than the Delaunay Triangulation.
6/17/12
6/15/12
A Simple 2D Graphics Engine Powered by OpenGL/GLUT.
In the course of coding up my ideas on the Voroni Graph, it became apparent that a CLI wasn't going to cut it. I needed some sort of graphical library, both for the final visualization, and for debugging. For this, I've chosen to use OpenGL with my own wrappers on top. This is a log of what I've been working on for the past few evenings.
This is, without the slightest doubt, overkill for what I'm doing right now (2D, very few colors, order of 100 different positions.). Screw that, I'm using OpenGL anyways. Why? I want the experience, and I want to write my own graphics engines that won't be limited by the underlying platform.
In any case, the process of getting to where I am now has been fairly frustrating. The documentation for all sorts of things involving OpenGL on the web is scant and often contradictory. Some things didn't work, other important aspects of a simple program had been depreciated. Getting even a blank screen to compile was a significant achievement.
In any case, this was all difficult enough to warrant a post and some preliminary code. Below is a sort of black box on the whole process, written as I worked through everything. For this reason, please excuse the weird tenses.
This is, without the slightest doubt, overkill for what I'm doing right now (2D, very few colors, order of 100 different positions.). Screw that, I'm using OpenGL anyways. Why? I want the experience, and I want to write my own graphics engines that won't be limited by the underlying platform.
In any case, the process of getting to where I am now has been fairly frustrating. The documentation for all sorts of things involving OpenGL on the web is scant and often contradictory. Some things didn't work, other important aspects of a simple program had been depreciated. Getting even a blank screen to compile was a significant achievement.
In any case, this was all difficult enough to warrant a post and some preliminary code. Below is a sort of black box on the whole process, written as I worked through everything. For this reason, please excuse the weird tenses.
6/8/12
Prelude and Fugue
There's a long story behind these: Basically, they were written for me in about 10 minutes during orientation after an off comment that I played the cello. Yes this is in pen (though I did enhance the contrast). Hit the break to see scans...
Subscribe to:
Posts (Atom)