Lua is great, but it is missing a few things..
1. continue -- although Lua 5.2 adds goto, which does allow you to simulate this, but I don't see myself using goto..
2. no ++ or += etc. -- don't know why this isn't supported, shouldn't be too hard to add with custom pre-compiler
3. metaprogramming --Lua just doesn't have any good support for this, have to manipulate strings to accomplish anything
Lisp
Recently I've been teaching myself lisp-- so far it seems like a very creative language, which I like, as I view creativity as one of the most important skills for a programmer to have.
There are like a million different versions of lisp it seems and no single standard implementation.
And for whatever reason I decided to write yet another...
My lisp compiles to Lua, I figured that LuaJIT2 is the fastest dynamic language VM around, so targeting it should allow my Lisp implementation to perform better than most. I had no experience with Lisp prior to this, but I certainly learned lisp fairly well while writing a compiler for it-- also improved my Lua.
It is somewhat different from the lisp norm in that it does not use lists and cons cells, instead I use a Lua table in array form. No named arguments either, although you can fake them just as you would in Lua. I also use { to introduce raw Lua code, and } to return to Lisp.
Still have to implement most of the library functions that come with most lisp implementations, and I'm sure I'll have to fix a few bugs in the compiler yet, but it is working, including support for macros.
I also saw that the creator of Lisp, John McCarthy, died a few days ago:(
There are like a million different versions of lisp it seems and no single standard implementation.
And for whatever reason I decided to write yet another...
My lisp compiles to Lua, I figured that LuaJIT2 is the fastest dynamic language VM around, so targeting it should allow my Lisp implementation to perform better than most. I had no experience with Lisp prior to this, but I certainly learned lisp fairly well while writing a compiler for it-- also improved my Lua.
It is somewhat different from the lisp norm in that it does not use lists and cons cells, instead I use a Lua table in array form. No named arguments either, although you can fake them just as you would in Lua. I also use { to introduce raw Lua code, and } to return to Lisp.
Still have to implement most of the library functions that come with most lisp implementations, and I'm sure I'll have to fix a few bugs in the compiler yet, but it is working, including support for macros.
I also saw that the creator of Lisp, John McCarthy, died a few days ago:(
Fast Grid Aligned Noise
Here is a method to produce noise faster than the traditional approach, such as perlin noise, where you sample the 8 integer corners and perform trilinear interpolation, with the limitation that it must be axis aligned and have a constant frequency for a given octave.
I'm focusing on perlin/improved noise here, not simplex noise, which is not axis aligned to begin with.
One of the slowest aspects of perlin noise is generation the pseudo random values for the 8 corners. Perlin uses a LUT, others use integer hashing(particularly necessary if you want to use SSE/AVX).
Say you want to generate a 3D grid 32^3 of noise values, this requires 32,768 calls to noise, and internally the generation of 262,144 (32^3 * 8) pseudo random values.
Many of these values are identical, how many depends on the frequency you are sampling at. The smoother the resulting noise is, the less unique pseudo random values were required.
This approach only requires P^3 pseudo random values, where P is always less than or equal to half of N(most often P is only a small fraction of N, it depends on the frequency). Even at half of N this only requires 4096 (16^3) pseudo random values.
One case where this is particularly applicable is when summing multiple octaves. In many cases 20+ octaves will be used. The outer octaves are very low frequency, there is no need to be calculating so many pseudo random values.
A second major optimization is the interpolation pass. These passes are separable. This means we can interpolate all of the X, then all of the Y, and then all of the Z. This reduces the number of interpolations required from (N^3 * 7) to (N*P*P + N*N*P + N*N*N).
Here is the basic algorithm for generating grid aligned noise. It is much more complicated than perlin noise, and much less flexible. But it is far faster. It also allows for the use of cubic noise with no visible grid structure. It operates on blocks of noise, instead of on individual samples.
This is described in the context of 3D noise, but can be applied to other dimensions.
I'm focusing on perlin/improved noise here, not simplex noise, which is not axis aligned to begin with.
One of the slowest aspects of perlin noise is generation the pseudo random values for the 8 corners. Perlin uses a LUT, others use integer hashing(particularly necessary if you want to use SSE/AVX).
Say you want to generate a 3D grid 32^3 of noise values, this requires 32,768 calls to noise, and internally the generation of 262,144 (32^3 * 8) pseudo random values.
Many of these values are identical, how many depends on the frequency you are sampling at. The smoother the resulting noise is, the less unique pseudo random values were required.
This approach only requires P^3 pseudo random values, where P is always less than or equal to half of N(most often P is only a small fraction of N, it depends on the frequency). Even at half of N this only requires 4096 (16^3) pseudo random values.
One case where this is particularly applicable is when summing multiple octaves. In many cases 20+ octaves will be used. The outer octaves are very low frequency, there is no need to be calculating so many pseudo random values.
A second major optimization is the interpolation pass. These passes are separable. This means we can interpolate all of the X, then all of the Y, and then all of the Z. This reduces the number of interpolations required from (N^3 * 7) to (N*P*P + N*N*P + N*N*N).
Here is the basic algorithm for generating grid aligned noise. It is much more complicated than perlin noise, and much less flexible. But it is far faster. It also allows for the use of cubic noise with no visible grid structure. It operates on blocks of noise, instead of on individual samples.
This is described in the context of 3D noise, but can be applied to other dimensions.
- Using the initial location and the frequency determine how many psuedo random values are required for N^3 cube of noise. The result should be a much smaller cube P^3.
- Generate all the pseudo random values required for P^3
- Now we must perform some type of interpolation to create a smoothed representation of P^3. Perlins approach can be used, it is fast and only uses linear interpolation, but it does exhibit some grid structure. Alternatively cubic interpolation can be used, although this requires sampling 4 values per axis, and that we have padded P by 1 on either side.
- Perform interpolation along X axis of P^3, this will result in a block of data N*P*P size
- Perform interpolation along Y axis, resulting in a block of N*N*P size
- Perform interpolation along Z axis, now we have the final result that is N*N*N in size and is properly interpolated.
To make it fast, operate on blocks that fit in the L1 cache.
I used this technique for a project I worked on about six years ago. It is very fast, but I'm not using it for my current project as the grid aligned and constant frequency requirements got in the way. It is also only really efficient when you need large blocks of noise, which my current project does not.
Just thought I'd document it. I'm sure someone else has done this as it is fairly obvious.
Just thought I'd document it. I'm sure someone else has done this as it is fairly obvious.
Pacific Crest Trail
I was gone for a really long time.
Hiked the Pacific Crest Trail(PCT) from Mexico to Canada, started May 1st, ended on Oct 9th.
It was the best time I've ever had, and along the way I met some great people.
Now back to what is commonly called the real world...
Just a few images from the entire 2650 mile trail--
Southern California, not just a Desert after all
The monument by the Mexican border
Eagle Rock
We are descending into Tuolumne Meadows
Hiked the Pacific Crest Trail(PCT) from Mexico to Canada, started May 1st, ended on Oct 9th.
It was the best time I've ever had, and along the way I met some great people.
Now back to what is commonly called the real world...
Just a few images from the entire 2650 mile trail--
 |
| Wilson, my soccer ball-- he lasted 800 miles |
One of many raging creeks in the Sierras
Muir Hut 
One of the 10 or so passes in the Sierras
Southern California, not just a Desert after all
The monument by the Mexican border
Eagle Rock 
We are descending into Tuolumne Meadows Geometry shader = BSOD?
So I am rendering some points and wanted to quickly visualize them as billboards. The geometry shader is a good way to do this so I wrote a GS to output a screen aligned triangle where each point would be. This works-- mostly, except when I randomly get a nice blue screen of death while looking at the output.
I wonder if I'm stressing the GS too much somehow. While I am only outputting 3 verts for each incoming vert, I am rendering millions of points. I've tried a few different variations of the shader and they all seem to eventually BSOD on me.
Hard boot restart each time it happens, grrrr.
I wonder if I'm stressing the GS too much somehow. While I am only outputting 3 verts for each incoming vert, I am rendering millions of points. I've tried a few different variations of the shader and they all seem to eventually BSOD on me.
Hard boot restart each time it happens, grrrr.
Terrain Collision
NOTE: this post is old and nonsensical but I'll leave it for now..
 |
| Testing terrain collision with the green blocks near bottom. Here they are about to drop over the edge of the cliff. |
 |
| Dropped a few hundred balls on terrain as stress test. |
Added terrain collision last week, but as I'm not using heightfields I had to use
something slightly different from the norm.
First I tried a pure triangle mesh based approach, I knew this would be slow as
hell and use a ton of memory but I wanted to have a working baseline to compare
against.
Initially for physics I used Havok,but after getting the basic triangle mesh collision working I switched to Bullet. Why? I don't have $100,000 laying around to
waste on a physics engine for which I only have access to the binary version--and Havok only supplies libs for VS2008, not VS2010 which I what I am using, although I was able to
get the 2008 libs working, also I just like having the source code.
waste on a physics engine for which I only have access to the binary version--and Havok only supplies libs for VS2008, not VS2010 which I what I am using, although I was able to
get the 2008 libs working, also I just like having the source code.
I'd used Bullet before so it was easy to get it switched over, and once I had
the triangle mesh collision set up I gave it a trial run.
the triangle mesh collision set up I gave it a trial run.
The triangle mesh collision used approximatly one gig of memory, although
generation speed for the btBvhTriangleMeshShape was fairly quick. I created a
task to generate collision and spread the work across the cores which made
generation faster.
generation speed for the btBvhTriangleMeshShape was fairly quick. I created a
task to generate collision and spread the work across the cores which made
generation faster.
I added spheres and boxes that I could drop onto the terrain to test the accuracy
and performance of the collision detection.
and performance of the collision detection.
A gig of memory for terrain collision was obviously out of the question so I began
testing convex hulls.
testing convex hulls.
Bullet has a btConvexHullShapewhich takes an array of vertices in floating point format. This worked and reduced memory usage by more than half. Still wasn't good enough though.
I wrote my own convex hull shape which I called
btCompressedConvexHullShape, as the name implies it uses compressed verts
(about 1/4th the memory per vert).
btCompressedConvexHullShape, as the name implies it uses compressed verts
(about 1/4th the memory per vert).
I also started using Bullets utility class btShapeHull. This class takes in
an array of vertices and produces a convex tri mesh with a greatly reduced
number of vertices. Feed it 2000 verts and get back a 14 vert convex mesh,
that type of thing.
number of vertices. Feed it 2000 verts and get back a 14 vert convex mesh,
that type of thing.
I feed the results of the btShapeHull back into btCompressedConvexHullShape or a btConvexTriangleMeshShape(favoring btCompressedConvexHullShape as they both seem to produce the same results and it uses less memory).
Memory usage for the physics simulation was greatly reduced at this point,
down to about 100 megs. There are still a few optimizations I'd like to do,
mostly to reduce the allocations taking place in the btShapeHull step, but
overall the performance and memory usage is fairly good at this point.
down to about 100 megs. There are still a few optimizations I'd like to do,
mostly to reduce the allocations taking place in the btShapeHull step, but
overall the performance and memory usage is fairly good at this point.
I've also got the physics simulation running as it's own task, with adding and
removing of objects done asynchronously. This helps because as you move through
the world a great many terrain chunks(each as a convex hull) are being added and removed.
Collision seems to be fairly accurate as long as I don't have it too far off
from the visual representation.
My gravity is currently just set using Bullets built in system, which is directional.
This means if I navigate to the side of the planet I can start dropping objects
and watch them bounce along through mountains and valleys for miles as they
travel along the edge of the planet.
Need to add a character control system soon.
Subscribe to:
Posts (Atom)