Final Submission

Update: This was featured as a demo on the WebGL site! :D

Code: http://www.assembla.com/code/cis565-final-project/subversion/nodes/raymarchBox.c?rev=35 or http://glsl.heroku.com/e#2306.2

Slides: http://alice-yang.com/cis565/FinalPresentation.pptx

Video:

Windows

Added windows (coloring the box inside each building blue) and some geometry variation. Think I'm going to call it a day. Code can be found here.

We have bricks

Bricks!

Added bricks. The code is referenced from The Orange Book.

Small Update

Added a taller building type with a different mod value.



With more types of buildings it should be easy to achieve a believable city. However, since there isn't much time left, I'm considering focusing more on texturing and making what I have look pretty.

Progress

Riccardo (aka h3r3) kindly helped me out with generating random heights for the buildings, and it worked great (thanks again!) What he suggested was to create a position vector (pos) that remained the same for each building/cell:

vec2 pos = vec2(ceil(p.x/c.x), ceil(p.z/c.z));

 The idea behind this is: Using the mod function for repetition is like dividing the space into individual cells. By dividing p by c, you get the 2D position of the cell in this "checkerboard". The ceil function serves to ensure each cell is represented by only one (int) value, since the rand function always returns the same output when given the same input.

While I was trying to think of ways around generating random heights, Gabe suggested to try using multiple repetition patterns to simulate a varied but modular city. I think combining both these methods would produce good results, and I will be working on this this week.

I've been experimenting with adding details to buildings, and I decided to use IQ's method in his menger fractals to create windows. The basic idea is to create a cross that extends infinitely, and subtract it from the rectangular building bodies repeatedly to create window spaces. The rand function from before also resulted in some "free" variations, as seen below:

Windows and Ledges

I guess these buildings can be considered generic residential ones. I'll be experimenting with some more different types this week to add variation to the city. You can see the current work in progress here.

Running into Trouble

I've been trying to implement the procedural generation part of the project the past few days, but so far things haven't been looking that great. My first approach was to use IQ's repetition function (which is basically a modulo function) to duplicate one building infinitely. The idea was to assign each drawn building a random attribute (starting with height). However, the distance function, which is where the height would be determined, operates on each point of the ray, and there is no unifying "seed" I can pass to the random function that would return a height that would be the same for points hitting the same building. As such, all the available things I can pass into the random function (it takes in a vec2 and returns a float) result in flickering static at the tops of the buildings. I think the reason this isn't working is because the distance function is impartial to what object is being hit and describes the entire scene instead, and because there's no way to tell if the hits are landing on the same object, there is no way to set attributes for individual objects.

My backup plan was to individually construct buildings on an i by j grid that fills up the screen, and add/remove buildings to the scene as the camera moves. However, because the distance function for this implementation involves taking the union of all the objects, and the union is finding the smallest distance to the camera among all the objects, each pass of the fragment shader has to loop through every object in the scene to find the smallest distance. With the number of objects (around 255 in the sreenshot) in the scene, the lag became unbearably slow (and this is on the machine with the Fermi card).

Variation at the price of speed

I wasn't expecting something like this to happen, and I'm kind of out of ideas at this point. I've been reading on terrain ray marching to see if there's anything useful, since that was what inspired this project. What I noticed was in terrain ray marching, there is no need to differentiate between individual objects (the terrain is basically one big fractal field), so it never runs into my problem. Right now I'm emailing some people for advice. In the meantime I'll be thinking of other ways around this (hopefully) and looking into geometry.

Repeating City

After I decided to ignore the camera messing up, I happened to have to restart glsl sandbox, and found that the same code from my previous session produced scene at a different angle. I tried setting the cos and sin inputs to constants this time and it works now. Go figure.

I have a rudimentary infinite city with the camera continuously panning backwards here, and I'll be building the geometry this week. I'm still not happy with the shading (still can't figure out why dark lines are showing up at the edges of some of the buildings, I'm guessing its some kind of problem with the normal), but I'm a bit behind schedule with the geometry so it's time to move along.

Trouble with the camera

While trying to figure out a way to let the user control the camera, I ran into the problem where changing the camera location messes up the shading of the scene.

With the eye position of  E=vec3(-sin(time/10000.0)*10.0,5,cos(time/10000.0)*10.0); I get the following result:

However, when I try to set the position using a constant, such as E=vec3(-sin(0.0001)*10.0,5,cos(0.0001)*10.0); the lighting messes up compeltely:

I'm not really sure why this is happening, since the x and z values of the eye are basically sin waves going between 0 to 1, so replacing the time function with a constant should at most only change the viewing angle. I've been kind of stuck on this for a while, so if nothing changes in the next few days, I'll probably stick to the hack of dividing time by a really large float so it looks constant. 

Midpoint Slides

Midpoint slides can be downloaded from here

Random Heights

Using a double for loop makes it possible to generate a random height for each building using the following function:

float rand(vec2 n)
{
return 0.5 + 0.5 *
fract(sin(dot(n.xy, vec2(12.9898, 78.233)))* 43758.5453);
}

Since the loop variables (i,j in this instance) are unique for each building, I can use vec2(i,j) as the seed for the rand function, which guarantees a unique value for each call. Not sure if this is the best way, but for now it will do.

Fog + Sun

Added fog and sunlight, referenced from Mazapan. Planning on changing some code  later so the horizon isn't as harsh/blends into the fog.

Also tried creating buildings with different heights in a for loop. Still need to figure out the random function.

Current Progress

SVN URL: http://subversion.assembla.com/svn/cis565-final-project/
(decided not to use git because rolling back changes is a pain)

I've been playing around with Paulo Falcao's raymarching experiment  and IQ's distance functions. The camera has been tweaked to be closer to the one from Norm's 460 slides. The original framework comes with simple phong shading by calculating a gradient vector on the ray-surface contact point and plugging it into the phong algorithm with the camera as the light. It looks good with one cube, but with an infinite field of cubes some odd artifacts come up:

I implemented a different method based on the number of steps taken by the ray. This produces slightly crisper results (and fake AO) but results in a halo around objects if the max number of steps is too low. Again, the light source is coming from the camera (since it's the original of all the rays). I hope to be able to set a light source in the future but the focus right now is geometry creation.

I've been trying to figure out how to create a box with a random height. Since glsl doesn't seem to have a rand() function, I've been looking at noise functions. Some of them result in interesting shapes, such as the fuzzy box. 

The next item to consider is how to create multiple boxes/rudimentary buildings with random heights. I had initially wanted to use IQ's repetition function (seen above), but I'm not sure if it is limited to only one exact shape (I think it boils down to whether the random float value will returns different values each time the primitive is rendered). This is what I will be working on the coming week. 

Reading List

http://www.swiftless.com/tutorials/glsl/1_setup.html
http://glsl.heroku.com/
http://nehe.gamedev.net/article/glsl_an_introduction/25007/
http://www.iquilezles.org/www/material/nvscene2008/nvscene2008.htm
http://www.youtube.com/watch?v=Hbw1Xx7K0xc&list=UUEbJErBsmPdnbhxrjAw56Vw&index=4&feature=plcp
http://www.rozengain.com/blog/2010/08/10/using-webgl-glsl-shaders-to-create-a-tunnel-effect/
http://http.developer.nvidia.com/GPUGems3/gpugems3_ch01.html
http://www.geisswerks.com/about_terrain.html
http://www.rpenalva.com/blog/?p=254 (raymarching)
http://www.iquilezles.org/www/articles/terrainmarching/terrainmarching.htm (terrain raymarching)
http://www.dasprinzip.com/prinzipiell/2011/03/22/ray-marching-the-distance/
http://www.cs.uic.edu/~kjoshi/GPU_Project3/GPU_Project3.html (terrain project)
http://www.youtube.com/watch?v=IdYP0PUPQpA (procedural terrain)
http://illogictree.com/blog/masters-thesis/ (procedural grass)
http://alteredqualia.com/three/examples/webgl_terrain_dynamic.html (webgl dynamic terrain)
http://www.mit.edu/~danz/marti/intro/lights/high/0.html (intro to raytracing)
http://fuzzyphoton.tripod.com/howtowrt.htm (how to raytrace)
http://glsl.heroku.com/e#1686.0 (sphere example)

http://www.opengl.org/archives/resources/faq/technical/transformations.htm (transformations)
http://www.khronos.org/files/opengl-quick-reference-card.pdf (OpenGL quick reference card)
http://www.pouet.net/topic.php?which=8177&page=1&x=32&y=5 (raymarching intro)
http://cboard.cprogramming.com/game-programming/118838-matrices-confusion-modelview-projection.html (model-view-projection)
http://db-in.com/blog/2011/04/cameras-on-opengl-es-2-x/ (camera openGL)

More Cities: GPU Final Project Proposal

Procedurally Generating an Infinite City

Procedural generation has always been a topic of interest for me. In the previous year I worked on procedurally generating cities on the CPU (in Maya), and now I feel that this project is a good opportunity to experiment with something similar on the GPU.

Currently there is not much work on generating view-dependent cities, and existing
implementations of GPU-based city generation are limited to commercial software such
as CityEngine. For my project, I plan on writing an application that generates buildings on the fly based on view parameters (and a maximum view distance that will be covered by fog or shadows), basically creating an infinite city.

At the moment I am considering two approaches. The first method would procedurally
generate buildings in CUDA, where the threads are positioned in 2D blocks and each
thread calculates the vertices of the building based on the block and thread indices. These are pushed into vertex buffers, which are shared along with textures with OpenGL for rendering. For each frame, the vertex buffers are sorted from front to back. New buildings are generated when needed, replacing the most distant building when a free vertex buffer is needed. Building height can be randomized using a fractal algorithm, such as the Diamond Square Algorithm which is commonly used in procedural Terrain Generation.

The alternate approach is to ray-march distance fields in a fragment shader using GLSL. In this case, a viewport-aligned quad is rendered using two triangles. No additional geometry is generated; instead, the fragment shader is used to march a ray through each pixel and into a scene described by distance functions across the entire window.

The first step for my project would be to explore both these methods and choose one
that produces the best results. The rest of the project will focus more on the procedural generation and less on individual building, although I hope to add more details as time allows.

References:
Terrain Generation and Smoothing
Experiment: Cityscape with Raymarching
Raymarching Distance Fields
Modeling with Distance Functions
Email correspondence with Patrick

Belated Final Report