## Developing engage3D – Phase 1October 25, 2012

Posted by Andor Salga in Kinect, Open Source, point cloud, webgl.
1 comment so far

A point cloud of Bill Brock rendered with WebGL

I am working with Bill Brock (a PhD student from Tennessee) to develop an open source 3D video conferencing system that we are calling engage3D. We are developing this application as part of Mozilla’s Ignite Challenge.

During the past few days, Bill and I made some major breakthroughs in terms of functionality. Bill sent me Kinect depth and color data via a server he wrote. We then managed to render that data in the browser (on my side) using WebGL. We are pretty excited about this since we have been hacking away for quite some time!

There has been significant drawbacks to developing this application over commodity internet, I managed to download over 8Gb of data in only one day while experimenting with the code. Hopefully, this will soon be able to be ported to the GENI resources in Chattanooga, TN for further prototyping and testing.

Even though we are still limited to a conventional internet connection, we want to do some research into data compression. Also, we have been struggling with calibrating the Kinect. This is also something we hope to resolve soon.

## Experimenting with Normal MappingSeptember 26, 2012

Posted by Andor Salga in Game Development, Open Source, Processing, Processing.js.
Tags: ,

Quick note about the demo above. I’m aware the performance on Firefox is abysmal and I know it’s wonky on Chrome. Fixes to come!

I’ve heard and seen the use of normal mapping many times, but I have never experimented with it myself, so I decided I should, just to learn something new. Normal mapping is a type of bump mapping. It is a way of simulating bumps on an object, usually in a 3D game. These bumps are simulated with the use of lights. To get a better sense of this technique, click on the image above to see a running demo. The example uses a 2D canvas and simulates Phong lighting.

### So why use it and how does it work?

The great thing with normal mapping is that you can simulate vertex detail of a simplified object without providing the extra vertices. By only providing the normals and then lighting the object, it will seem like the object has more detail than it actually does. If we wanted to place the code we had in a 3D game, we would only need 4 vertices to define a quad (maybe it could be a wall), and along with the normal map, we could render some awesome Phong illumination.

So, how does it work? Think of what a bitmap is. It is just a 2D map of bits. Each pixel contains a color components making up a the entire graphic. A normal map is also a 2D map. What makes normal maps special is how their data is interpreted. Instead of each pixel holding a ‘color’ value, each pixel actually stores a vector that defines where the corresponding part in the color image is ‘facing’ also known as our normal vector.

These normals need to be somehow encoded into an image. This can be easily done since we have three floating point components (x,y,z) that need to be converted into three 8 or 16 bit color components (r,g,b). When I began playing with this stuff, I wanted to see what the data actually looked like. I first dumped out all the color values from the normal map and found the range of the data:

Red (X) ranges from 0 to 255
Green (Y) ranges from 0 to 255
Blue (Z) ranges from 127 to 255

Why is Z different? When I first looked at this, it seemed to me that each component needs to be subtracted by 127 so the values map to their corresponding negative number lines in a 3D coordinate system. However, Z will always point directly towards the viewer, never away. If you do a search for normal map images, you will see the images are blue in color. So it would make sense why the blue is pronounced. The normal is always pointing ‘out’ of the image. If it ranged from 0-255, subtracting 127 would result in a negative number which doesn’t make sense. So, after subtracting each by 127:

X -127 to 128
Y -127 to 128
Z 0 to 128

The way I picture this is I imagine that all the normals are contained in a translucent semi-sphere with the semi-sphere’s base lying on the XY-plane. But since the Z range is half of that of X and Y, it would appear more like a squashed semi-sphere. This tells us the vectors aren’t normalized. But that can be solved easily with normalize(). Once normalized, they can be used in our lighting calculations. So now that we have some theoretical idea of how this rendering technique works, let’s step through some code. I wrote a Processing sketch, but of course the technique can be used in other environments.

// Declare globals to avoid garbage collection

// colorImage is the original image the user wants to light
// targetImage will hold the result of blending the
// colorImage with the lighting.
PImage colorImage, targetImage;

// normalMap holds our 2D array of normal vectors.
// It will be the same dimensions as our colorImage
// since the lighting is per-pixel.
PVector normalMap[][];

// shine will be used in specular reflection calculations
// The higher the shine value, the shinier our object will be
float shine = 40.0f;
float specCol[] = {255, 128, 50};

// rayOfLight will represent a vector from the current
// pixel to the light source (cursor coords);
PVector rayOfLight = new PVector(0, 0, 0);
PVector view = new PVector(0, 0, 1);
PVector specRay = new PVector(0, 0, 0);
PVector reflection = new PVector(0, 0, 0);

// These will hold our calculated lighting values
// diffuse will be white, so we only need 1 value
// Specular is orange, so we need all three components
float finalDiffuse = 0;
float finalSpec[] = {0, 0, 0};

// nDotL = Normal dot Light. This is calculated once
// per pixel in the diffuse part of the algorithm, but we may
// want to reuse it if the user wants specular reflection
// Define it here to avoid calculating it twice per pixel
float nDotL;

void setup(){
size(256, 256);

// Create targetImage only once
targetImage = createImage(width, height, RGB);

// Load the normals from the normalMap into a 2D array to
// avoid slow color lookups and clarify code
PImage normalImage =  loadImage("data/normalMap.jpg");
normalMap = new PVector[width][height];

// i indexes into the 1D array of pixels in the normal map
int i;

for(int x = 0; x < width; x++){
for(int y = 0; y < height; y++){
i = y * width + x;

// Convert the RBG values to XYZ
float r = red(normalImage.pixels[i]) - 127.0;
float g = green(normalImage.pixels[i]) - 127.0;
float b = blue(normalImage.pixels[i]) - 127.0;

normalMap[x][y] = new PVector(r, g, b);

// Normal needs to be normalized because Z
// ranged from 127-255
normalMap[x][y].normalize();
}
}
}

void draw(){
// When the user is no longer holding down the mouse button,
// the specular highlights aren't used. So reset the values
// every frame here and set them only if necessary
finalSpec[0] = 0;
finalSpec[1] = 0;
finalSpec[2] = 0;

// Per frame we iterate over every pixel. We are performing
// per-pixel lighting.
for(int x = 0; x < width; x++){
for(int y = 0; y < height; y++){

// Simulate a point light which means we need to
// calculate a ray of light for each pixel. This vector
// will go from the light/cursor to the current pixel.
// Don't use PVector.sub() because that's too slow.
rayOfLight.x = x - mouseX;
rayOfLight.y = y - mouseY;

// We only have two dimensions with the mouse, so we
// have to create third dimension ourselves.
// Force the ray to point into 3D space down -Z.
rayOfLight.z = -150;

// Normalize the ray it can be used in a dot product
// operation to get a sensible values(-1 to 1)
// The normal will point towards the viewer
// The ray will be pointing into the image
rayOfLight.normalize();

// We now have a normalized vector from the light
// source to the pixel. We need to figure out the
// angle between this ray of light and the normal
// to calculate how much the pixel should be lit.

// Say the normal is [0,1,0] and the light is [0,-1,0]
// The normal is pointing up and the ray, directly down.
// In this case, the pixel should be fully 100% lit
// The angle would be PI

// If the ray was [0,-1,0] it would
// not contribute light at all, 0% lit
// The angle would be 0 radians

// We can easily calculate the angle by using the
// dot product and rearranging the formula.
// Omitting  magnitudes since they are = 1
// ray . normal = cos(angle)
// angle = acos(ray . normal)

// Taking the acos of the dot product returns
// a value between 0 and PI, so we normalize
// that and scale to 255 for the color amount
nDotL = rayOfLight.dot(normalMap[x][y]);
finalDiffuse = acos(nDotL)/PI * 255.0;

// Avoid more processing by only calculating
// specular lighting if the users wants to do it.
// It is fairly processor intensive.
if(mousePressed){
// The next 5 lines calculates the reflection vector
// using Phong specular illumination. I've written
// a detailed blog about how this works:
// http://asalga.wordpress.com/2012/09/23/understanding-vector-reflection-visually/
// Also, when we have to perform vector subtraction
// as part of calculating the reflection vector,
// do it manually since calling sub() is slow.
reflection = new PVector(normalMap[x][y].x,
normalMap[x][y].y,
normalMap[x][y].z);
reflection.mult(2.0 * nDotL);
reflection.x -= rayOfLight.x;
reflection.y -= rayOfLight.y;
reflection.z -= rayOfLight.z;

// The view vector points down (0, 0, 1) that is,
// directly towards the viewer. The dot product
// of two normalized vector returns a value from
// (-1 to 1). However, none of the normal vectors
// point away from the user, so we don't have to
// deal with making sure the result of the dot product
// is negative and thus a negative specular intensity.

// Raise the result of that dot product value to the
// power of shine. The higher shine is, the shinier
// the surface will appear.
float specIntensity = pow(reflection.dot(view),shine);

finalSpec[0] = specIntensity * specCol[0];
finalSpec[1] = specIntensity * specCol[1];
finalSpec[2] = specIntensity * specCol[2];
}

// Now that the specular and diffuse lighting are
// calculated, they need to be blended together
// with the original image and placed in the
// target image. Since blend() is too slow,
// perform our own blending operation for diffuse.
targetImage.set(x,y,
color(finalSpec[0] + (finalDiffuse *
red(colorImage.get(x,y)))/255.0,

finalSpec[1] + (finalDiffuse *
green(colorImage.get(x,y)))/255.0,

finalSpec[2] + (finalDiffuse *
blue(colorImage.get(x,y)))/255.0));
}
}

// Draw the final image to the canvas.
image(targetImage, 0,0);
}


Whew! Hope that was a fun read, Let me know what you think!

## Understanding Vector Reflection VisuallySeptember 23, 2012

Posted by Andor Salga in Game Development, Math.

I started experimenting with normal maps when I came to the subject of specular reflection. I quickly realized I didn’t understand how the vector reflection part of the algorithm worked. It prompted me to investigate exactly how all this magic was happening. Research online didn’t prove very helpful. Forums are littered with individuals throwing around the vector reflection formula with no explanation whatsoever. This forced me to step through the formula piecemeal until I could make sense of it. This blog post attempts to guide readers through how one vector can be reflected onto another via logic and geometry.

Vector reflection is used in many graphics and gaming applications. As I mentioned, it is an important part of normal mapping since it is used to calculate specular highlights. There are other applications other than lighting, but let’s use the lighting problem for illustration.

Let’s start with two vectors. We would know the normal of the plane we are reflecting off of along with a vector pointing to the light source. Both of these vectors are normalized.

L is a normalized vector pointing to our light source. N is our normal vector.

We are going to work in 2D, but the principle works in 3D as well. What we are trying to do is figure out: if a light in the direction L hits a surface with normal N, what would be the reflected vector? Keep in mind, all the vectors here are normalized.

I drew R here geometrically, but don’t assume we can simply negate the x component of L to get R. If the normal vector was not pointing directly up, it would not be that easy. Also, this diagram assumes we have a mirror-like reflecting surface. That is, the angle between N and L is equal to the angle between N and R. I drew R as a unit vector since we only really care about its direction.

So, right now, we have no idea how to get R.
$R = ?$

However, we can use some logic to figure it out. There are two vectors we can play with. If you look at N, you can see that if we scale it, we can create a meaningful vector, call it sN. Then we can add another vector from sN to R.

What we are doing here is exploiting the parallelogram law of vectors. Our parallelogram runs from the origin to L to sN to R back to the origin. What is interesting is that this new vector from sN to R has the opposite direction of L. It is -L!

Now our formula says that if we scale N by some amount s and subtract L, we get R.
$R = sN - L$

Okay, now we need to figure out how much to scale N. To do this, we need to introduce yet another vector from the origin to the center of the parallelogram.

Let’s call this C. If we multiply C by 2, we can get sN (since C is half of the diagonal of the parallelogram).
$2C = sN$

Replacing sN in our formula with 2C:
$R = 2C - L$

Figuring out C isn’t difficult, since we can use vector projection. If you are unsure about how vector projection works, watch this KhanAcademy video.

If we replace C with our projection work, the formula starts to look like something! It says we need to project L onto N (to get C), scale it by two then subtract L to get R!
$R = 2((\frac{N \cdot L}{|N|^2})N) - L$

However, this can be simplified since N is normalized and getting the magnitude of a normalized vector yields 1.
$R = 2(N \cdot L)N - L$

Woohoo! We just figured out vector reflection geometrically, fun!

I hope this has been of some help to anyone trying to figure out where the vector reflection formula comes from. It has been frustrating piecing it all together and challenging trying to explain it. Let me know if this post gave you any ‘Ah-ha’ moments (:

## Reflections on Hackanooga 2012September 19, 2012

Posted by Andor Salga in Hackanooga, Kinect, point cloud.

This past weekend, I had the opportunity to participate in Hackanooga, a 48-hour hackathon in Chattanooga, Tennessee. The event was hosted by Mozilla and US Ignite with the purpose of encouraging and bringing together programmers, designers, and entrepreneurs to hack together demos that make use of Chattanooga’s gigabit network.

We only had two days to hack something together, so I wanted to make my goals simple and realistic. My plan was to set up a server on the gig network, upload dynamic point cloud data to the server and then stream the data back in real-time. In case I got that working, I wanted to try to avoid disk access altogether and stream the data from a Kinect and render it using WebGL.

Before the hacking began, anyone who wasn’t assigned a project had the chance to join one. I was surprised that several developers from the University of Tennessee at Chattanooga approached my table to hear more about my project. We quickly formed a group of four and dove right into setting up the server, editing config files, checking out the super-fast gig connection, and making sure our browsers supported WebGL. After a lot of frustration we finally managed to ‘stream’ the dynamic point cloud from the server. Although the data seemed to stream, it took a while to kick in on the client side. It was almost as if the files were being cached on the server before being sent over the wire. This is still something I need to investigate.

Once we had that working, we moved on to the Kinect. We created a c++ server that read the Kinect data and transferred that data to a node server via sockets. The node server then sent the data off to any client connections. My browser was one of the clients rendering the data, however, the rendered point clouds were a mess. One of the applications we wrote had a bug that we didn’t manage to fix in time ): Even though we didn’t manage to hammer out all the issues, I still had a lot of fun working with a team of developers.

Rumor has it that Hackanooga may become a yearly event. I’m already excited (:

## Excuses, excuses…June 13, 2012

Posted by Andor Salga in Personal Development.

Yesterday, my legs hurt like hell. It was my second day running and after my run, I had trouble with stairs and even walking. Moving my legs in any way was painful.

I began running as a form of mental exercise, not a physical one. I wanted to practice getting past the mental barriers I create in my life. I figured, if I can overcome the pain, the doubt and fear of a physical exercise, I can get past any mental barriers too.

Today was the third day and things were different. I slept in to recover and I thought my legs would be better by morning, but they were in a worse shape than ever. Getting out of bed was hard and walking was slow. I had to go downstairs one stair at a time. I looked my window and saw people, cars—I was too late. The streets were busy, it was cold, I didn’t want to cause any damage to my muscles, yesterday I had a beer, I’m tired, I have to work—these were my excuses. Look inside yourself and understand your excuses are just as stupid and these stupid excuses are holding you back from your potential.

I remembered this was a mental exercise. The whole point was to break through any mental barriers. I got honest with myself and realized my excuses were ridiculous. If I didn’t get outside, I could rest my legs, yes, but mentally it would be worst thing I could do for myself.

I asked myself, “What if?”. What if I did run today? Would my legs break? Probably not. But more importantly, how would I feel if I could do it? I would have overcome a huge obstacle. I would cry in pain, but hell, I would feel incredible mentally. That was enough for me. I put on my shoes and I was out the door. My run was about 3KM total. By the end of it, I had snot running down my nose and I was gasping for air. It was ugly, but I loved it. I had broken past my mental and physical barrier.

Tomorrow holds a new challenge, but I believe I have the courage to take it on.

Get honest with yourself today, what are your excuses? Write them down. Are these going to hold you back from your ultimate potential? Will you be on your deathbed telling everyone stories about why you couldn’t fulfill your dreams? Or will you tell everyone you managed to fulfill your ambitions even in spite of all your many challenges?

## Porting Crayon Physics to the WebJune 12, 2012

Posted by Andor Salga in Game Development, Games, Open Source, Processing.js.

click that: ^^

It’s been a while since I gave my blog some love, so here goes.

Many semesters ago, I tried to make an HTML5 port of Crayon Physics Deluxe using Processing.js and Box2DJS. I got the rendering right, but I couldn’t get the physics to work correctly. My demo was limited to bounding box collisions.

I recently tried again to see if I could make this thing work. When I hacked together a demo of a ball rolling across the canvas, which was composed of several shapes, I became super-giddy. I knew it was indeed possible to port Crayon Physics to the Web. So I kept hacking on it, and I now have something semi-decent. There are of course a bunch of bugs to work out, but I’m excited to see this project’s potential.

## No Comply Game Prototype with ProcessingJanuary 25, 2012

Posted by Andor Salga in Game Development, Gladius, Open Source, Processing.
1 comment so far

Last week I met with Dave Humphrey and Jon Buckley to discuss creating a game for the HTML5 games week which will take place at Mozilla’s Toronto office in mid-February. The main purpose of this is to drive the development and showcase the Gladius game engine.

At the end of the meeting we decided it would make the most sense to upgrade the No Comply demo by adding interaction—making a small game. Since we only have a few weeks, we decided to keep it simple. Keeping that in mind I created a game specification.

## Play Analysis

After putting together the spec, I started on a prototype. I began the prototype by playing and analyzing the game mechanics of Mortal Kombat I. The game is simple enough to emulate given the time frame. I took some notes and concluded characters always appear to be in discrete states. If characters are in a particular state, they may or may not be able to transition into another state. Initially a player is idle. From there, they can transition into a jumping. Once jumping they cannot block, but are allowed to punch an kick. Having understood the basic rules, I drew a diagram to visually represent some states.

The diagram led me to believe I could use the state pattern to keep the game extensible. We can get a basic game working and the design should lend itself to later (painless) modification.

## Prototyping the Prototype

Having worked with Processing for some time I knew it would be an ideal tool to construct a prototype of the game. Processing enables developers to get graphical interactive software up and running quickly and easily. The structure is elegant and the language inherits Java’s simple object-oriented syntax.

I began creating a Processing sketch by adding the necessary classes for player states such as moving, jumping and punching. I hooked in keyboard input to allow changing states and rendered text to indicate the current state. I was able to fix most of the bugs by playing around with different key combinations and just looking at the text output.

I eventually added graphical content, but intentionally kept it crappy. I resisted the urge to create attractive assets since they would be replaced with the No Comply sprites anyway. Neglecting the aesthetics was a challenge—if you cringe at the graphics, I succeeded.

Okay, still want to play it?

## Next Steps

I omitted collision detection and some simple game logic from the prototype, but I believe it demonstrates we can create a structure good enough for a fighting game for Gladius. Today I’ll be switching gears and starting to hack on Gladius to get COLLADA importing working which we’ll discuss in a Paladin meeting early next week.

## Learning to Wield and Forge GladiusJanuary 23, 2012

Posted by Andor Salga in Game Development, Gladius, Open Source.

## Wielding

For the next few weeks I’ll be working on the open source project Gladius. More specifically, I’ll be working on CubicVR.js, a rendering engine which is one part of the Gladius 3D game engine. Gladius in turn is part of Paladin, Mozilla’s initiative to bring awesome gaming technologies to the Web.

Since Gladius is a game engine, it is essentially a conglomeration of many game-related technologies:

#### Drawing Stuff

CubicVR.js is a JavaScript port of Charles Cliffe’s CubicVR game engine which is responsible for rendering using WebGL.

#### Saving Stuff

GameSaver is a project which uses Node.js and BrowserID to save JSON game state on a server. Check out a prototype which uses GameSaver at MyFavoriteBeer.org.

#### Physics Stuff

For collision detection and response, Gladius uses AMMO.js: a JavaScript port of the C++ Bullet physics engine.

#### Controlling Stuff

My supervisor, David Humphrey and colleagues in my lab have been working on two important aspects of game input: the Gamepad API and the Mouse Lock API. Check them out, they’re very interesting.

#### Other Stuff

This list is not exhaustive. As the project matures it is expected other libraries and technologies will be incorporated.

#### Forging

The release date for Gladius 0.1 is mid February, so I’ll be contributing where I can to help out with the release. Last week I started by making a minor tweak to CubicVR.js. Not much, but it’s a start. I also noticed there wasn’t a way for developers to simply check for AABB-AABB intersection. So I filed the issue and began working on that as well. This week I’ll be working with Bobby Richter to fix COLLADA related bugs which is super exciting. (:

Do you want to get involved? You can find a number of ways to get in contact with developers and start contributing right here.

## Extending Processing.js with a OBJ Importer Part 4January 5, 2012

Posted by Andor Salga in Open Source, Processing, Processing.js, Processing.js OBJ Support, webgl.

Run Me!

This sketch demonstrates more .obj file support for Processing.js.

This blog post is the continuation of a series of blogs [1, 2, 3] related to adding .obj file support to Processing.js. This code I’m working on is important since it will allow developers to easily load 3D models from files and it will increase the performance of rendering 3D objects in Processing.js.

Since my last blog, I have added some small but critical changes to the code, some of which I outline here.

## Interface Change

I contacted one of the developers of Processing, Andrés Colubri, who is reworking most of the OpenGL code. Some of his rework includes making Saito’s .obj loader native in Processing. This is great for Processing, but it means that all the time I spent making the Processing.js .obj loader work like Saito’s was wasted ): On the other hand, it means that pushing this code in the next release of Processing.js might actually be done! (:

The sketch below is a simple example of using Saito’s .obj extension, which my code expected.

OBJModel obj;

void setup(){
size(100, 100, P3D);
obj = new OBJModel();
}

void draw(){
obj.drawMode(POLYGON);
}


The problem was that I had no idea what loading 3D models was supposed to look like natively. So I asked Andréas for a simple sketch that worked in Processing and that I could emulate in Processing.js.

After receiving the sketch, I was glad to see it wasn’t much different.

PShape obj;

void setup() {
size(100, 100, P3D);
}

void draw() {
shape(obj);
}


I was able to quickly add a few hacks to make Processing.js work with the new interface. I didn’t want to rewrite my entire parser just yet since all my tests rely on the old method. I also don’t want to rewrite my code a third time (:

## Triangulation

I found that many 3D authoring tools export .obj models with triangle fans. In my last blog about .obj importing I wrote about the lack of support in my code for this scenario, but I recently wrote a patch that fixes the issue. It was not difficult to write, but because of this fix, many more models can now be properly parsed. This includes the 3D model at the top of this post.

## Testing, testing, …

I found a few more issues with the parser so I fixed them and added reference tests. I’m finding these tests invaluable since I’m often tweaking the parser as I go. I have just over 30 right now, but I hope to have many more since I expect the code will go through many more transformations.

## Feedback

If you are using my ‘extension’ and you find a file that isn’t being properly loaded, please send me your file so that I can fix it and add a test.

## Shadows in WebGL Part 1December 12, 2011

Posted by Andor Salga in FSOSS, Open Source, point cloud, webgl, XB PointStream.

In my last blog I wrote about an anaglyph demo I created for my FSOSS presentation in October. It was part of a series of delayed blogs which I only recently had time to write up. So, in this blog I’ll be proceeding with my next fun experiment: Shadows in WebGL.

Shadows are useful since they not only add realism, but can also provide additional visual cues in a scene. Having never implemented any type of shadows, I started by performing some preliminary research and found that there are numerous methods to achieve this effect. Some of the more common techniques include:

• vertex projection
• projected planar shadows

I chose vertex projection since it seemed very straightforward. After a few sketches, I got a fairly good grasp of the idea. Given the position for a light and vertex, the shadow cast (for that vertex) will appear at the line intersection between the slope created by those points and the x-intercept. If we had the following values:

• Light = [4, 4]
• Vertex = [1, 2]

Our shadow would be drawn at [-2, 0]. Note that the y component is zero and would be equal to zero for all other vertices since we’re concentrating on planar shadows.

At this point, I understood the problem well; I just needed a simple formula to get this result. If you run a search for “vertex projection” and “shadows” you’ll find a snippet of code on GameDev.net which provides the formula for calculating the x and z components of the shadow. But if you actually try it for the x component:

$Sx = Vx - \frac{Vy}{Ly} - Lx$
$Sx = 1 - \frac{2}{4} - 4$
$Sx =-3.5$

It doesn’t work.

When I ran into this, I had to take a step back to think about the problem and review my graphs. I was convinced that I could contrive a working formula that would be just as simple as the one above. So I conducted additional research until I eventually found the point-slope equation of a line.

## Point-Slope Equation

The point-slope equation of a line is useful for determining a single point on the slope give the slope and another point on the line. This is exactly the scenario we have!

$y - y1 = m(x - x1)$

Where:
m – The slope. This is known since we have two given points on the line: the vertex and the light.

[x1, y1] – A known point on the line. In this case: the light.

[x, y] – Another point on the line which we’re trying to figure out: the shadow.

Since the final 3D shadow will lie on the xz-plane, the y components will always be zero. We can therefore remove that variable which gives us:

$-y1 = m(x - x1)$

Now that the only unknown is x, we can start isolating it by dividing both sides by the slope:
$-\frac{y1}{m} = \frac{m(x - x1)}{m}$

Which gives us:
$-\frac{y1}{m} = x - x1$

And after rearranging we get our new formula, but is it sound?
$x = x1 - \frac{y1}{m}$

If we use the same values as above as a test:
$x = 4 - \frac{4}{\frac{2}{3}}$
$x = -2$

It works!

I now had a way to get the x component for the shadow, but what about the z component? What I did so far was create a solution for shadows in 2 dimensions. But if you think about it, both components can be broken down into 2 2D problems. We just need to use the z components for the light and point to get the z component of the shadow.

The shader code is a bit verbose, but at the same time, very easy to understand:

void drawShadow(in vec3 l, in vec4 v){
// Calculate slope.
float slopeX = (l.y-v.y)/(l.x-v.x);
float slopeZ = (l.y-v.y)/(l.z-v.z);

// Flatten by making all the y components the same.
v.y = 0.0;
v.x = l.x - (l.y / slopeX);
v.z = l.z - (l.y / slopeZ);

gl_Position = pMatrix * mVMatrix * v;
frontColor = vec4(0.0, 0.0, 0.0, 1.0);
}


## Double Trouble

The technique works, but its major issue is that objects need to be drawn twice. Since I’m using this technique for dense point clouds, it significantly affects performance. The graph below shows the crippling effects of rendering the shadow of a cloud consisting of 1.5 million points—performance is cut is half.

Fortunately, this problem isn’t difficult to address. Since detail is not an important property for shadows, we can simply render the object with a lower level of detail. I had already written a level of detail python script which evenly distributes a cloud between multiple files. This script was used to produce a sparse cloud—about 10% of the original.

## Matrix Trick

It turns out that planar shadows can be alternatively rendered using a simple matrix.

void drawShadow(in vec3 l, in vec4 v){
// Projected planar shadow matrix.
mat4 sMatrix = mat4 ( l.y,  0.0,  0.0,  0.0,
-l.x,  0.0, -l.z, -1.0,
0.0,  0.0,  l.y,  0.0,
0.0,  0.0,  0.0,  l.y);

gl_Position = pMatrix * mVMatrix * sMatrix * v;
frontColor = vec4(0.0, 0.0, 0.0, 1.0);
}


This method doesn’t offer any performance increase versus vertex projection, but the code is quite terse. More importantly, using a matrix opens up the potential for drawing shadows on arbitrary planes. This is done by modifying all the elements of the above matrix.

## Future Work

Sometime in the future I’d like to experiment with implementing shadows for arbitrary planes. After that I can begin investigating other techniques such as shadow mapping and shadow volumes. Exciting! (: