My Papers

This page assembles the various brief papers and algorithms I’ve sketched out over the years on this blog. Some of these papers may be of use to you; I don’t know.

I’ve taken the liberty to surface those papers here for future reference.

Learning the Metal API (Link to updated paper.)

The Metal API is Apple’s replacement of the OpenGL API on the Macintosh, iOS and tvOS. Metal is a low level API which permits you to develop 3D graphics applications and create compute tasks to send to the GPU, and thus combines the functionality of OpenGL and OpenCL. Because it’s a low level API it takes more work to get an image up on the screen, and this article (and the attached PDF paper) runs through several sample applications from the basic plumbing to a working deferred shader application.

Generating LR(1) grammars

This paper (in PDF form available on GitHub) provides a detailed description of the algorithms used to generate an LR parser. This covers concepts from the basic power-set construction algorithm to building LR(0), SLR, LALR and LR(1) grammars. The concepts should be at a level that a beginning Computer Science student should be able to understand and hopefully apply to their own parser-generator system, if they so wish.

Constructing a cyclic polygon given the edge lengths.

So I have a problem: given the length of the edges L = {l0, l1, … lN} of an N-sided irregular polygon with N > 3, I need to construct the values for the radius R and the angles A = {a0, a1, … aN} such that the points P = { R, ai } form a closed polygon with the lengths given.

I searched through the internet and found all sorts of articles on the subject, but a day of searching and I was unable to find a way that I could construct the values R and A. I’m sure it’s out there, but I figured it’d be a good exercise to do it myself.

Finding the boundary of a one-bit-per-pixel monochrome blob

Recently I’ve had need to develop an algorithm which can find the boundary of a 1-bit per pixel monochrome blob. (In my case, each pixel had a color quality which could be converted to a single-bit ‘true’/’false’ test, rather than a literal monochrome image, but essentially the problem set is the same.)

In this post I intend to describe the algorithm I used.

Goodbye Far Clipping Plane.

This paper discusses a minor variation to the perspective transformation matrix in computer graphics which permits one to dispense with the far clipping plane, yet maintain a high degree of numeric accuracy no matter how far away an object moves. (Theoretically one could even use this to render objects at the infinite plane; the plane of objects whose homogeneous coordinates are represented as (x,y,z,0).)

Leave a Reply

Please log in using one of these methods to post your comment:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google+ photo

You are commenting using your Google+ account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s