source packed in images.

I'm sick of posting source code in the text. I want to be able to upload any file, but all they let you upload is images. I wrote some c++ code to input any file and embed the contents as the pixels of an image (will only work with lossless encoding). The source code for this example is in one of the small images in this blog (the other is the python source of the previous posting). Too bad I couldn't upload a tga,tiff,or pgm, because those files you could just open as text and see the source. I leave it up to you to extract the code from the png.

Hint: convert to pgm (gray-scale) and open with an image editor.

convert image.png p.pgm
cat p.pgm

pyJoy

We just watched Control the other night and both my girlfriend and I liked a poster in the movie. Not knowing that this was an album cover, I immediately thought I should make something like that. So I wrote a script in a couple minutes to generate some images. Source code:

import cairo, sys
import math, random

def gen_row(w, smth=10, shft=0.2, wid=0.5):
    mid = w/2
    shft = mid*shft
    wid = mid*wid

    vals = [0]*w
    for x in xrange(0, w):
        sc = (x-random.uniform(mid-wid, mid+wid))/random.uniform(wid*0.9, wid*1.1)
        sc = math.exp(-sc*sc/2)
        ht = random.uniform(0,sc)
        vals[x] = ht

    for i in xrange(0, smth):
        v = [0]*w
        for x in xrange(1, w-1):
            v[x] = (vals[x] + vals[x-1] + vals[x+1])/3
        vals = v

    return vals

w, h = 256, 512
x0, sc = 4, 20
wid = 0.2

if len(sys.argv)>=3:
    w = int(sys.argv[1])
    h = int(sys.argv[2])

if len(sys.argv)>=4:
    wid = float(sys.argv[3])

surf = cairo.SVGSurface('joy.svg', w, h)
ctx  = cairo.Context(surf)

for y in xrange(10, h, 5):

    ctx.move_to(x0, y)
    row = gen_row(w, wid=wid)
    
    for x in xrange(x0, w-x0):
        ctx.line_to(x, y-row[x]*sc)

    ctx.set_source_rgba(0,0,0,1)
    ctx.stroke_preserve()

    ctx.set_source_rgba(1,1,1,1)
    ctx.line_to(w-x0, y+10)
    ctx.line_to(0, y+10)
    ctx.line_to(0, y)    
    ctx.fill()
    
surf.finish()

how slow is dynamic_cast?

I was wondering how slow dynamic_cast really is the other day when I considering designing something in a way that would require it's use. The other alternatives is to have some a virtual functions that performs a cast (requires the parent class to know about all children) or have a virtual function that exposes the type followed by a cast.

One of the first references I found on the web indicated the virtual-function-then-cast approach being up to 20x faster.
http://www.nerdblog.com/2006/12/how-slow-is-dynamiccast.html

That reference didn't provide code, so I wrote a quick test with the hierarchy of following classes:

ClassA, ClassB: public ClassA, and ClassC: public ClassB.

My tests suggest that this approach is about 5x faster when compiled with g++ -O3 (same speed with no optimization). For my application dynamic_cast should be perfectly fine.

Times for 3*100 million cast and function evaluations (in a smidge more than trivial loop)

Not optimized:

mycast 0m13.879s
dynamic_cast 0m0.060s


Optimized

mycast 0m0.919s
dynamic_cast 0m4.729s


a.h

class AClassA{
 public:
  static const int flag = 0x1;

  AClassA(){}
  virtual ~AClassA(){}

  virtual int name() const ;

  int a(){return 1;}
};

class BClassB: public AClassA {
public:
  static const int flag = 0x2;

  BClassB(){}
  virtual ~BClassB(){}

  int name() const ;

  int b(){return 2;}
};

class CClassC: public BClassB {
public:
  static const int flag = 0x4;
  CClassC(){}
  virtual ~CClassC(){}

  int name() const ;

  int c(){return 3;}
};

a.cc

#include "a.h"

#ifdef use_mycast
#warning "using mycast"
#define caster mycast
#define extras
#else
#define caster dynamic_cast
#define extras *
#endif

int AClassA::name() const {return AClassA::flag;}

int BClassB::name() const {return AClassA::flag | BClassB::flag;}

int CClassC::name() const {return AClassA::flag | BClassB::flag | CClassC::flag;}

template 
T * mycast(AClassA * a){
  if(a->name() & T::flag)return (T*)a;
}

int func_dcast(AClassA * a){
  CClassC * c = caster(a);
  if(c)return c->c();
  else {
    BClassB * b = caster(a);
    if(b)return b->b();
  }
  return a->a();
}

int main(int ac, char * av[]){
  const int ntrials = 100000000;
  int sums[8] = {0,0,0,0};

  AClassA a;
  BClassB b;
  CClassC c;

  for(int i=0; i!=ntrials; i++){
    sums[func_dcast(&a)]++;
    sums[func_dcast(&b)]++;
    sums[func_dcast(&c)]++;
  }
  printf("%d %d %d %d\n", sums[0], sums[1], sums[2], sums[3]);
  return 0;
}

makefile

all:
   g++ a.cc -Duse_mycast -o mycast.opt -O3 -fno-rtti
   g++ a.cc -Duse_mycast -o mycast -fno-rtti
   g++ a.cc -o dcast.opt -O3
   g++ a.cc -o dcast

test.sh

echo "Unoptimized (mycast then dcast)"
time ./mycast | grep real
time ./dcast  | grep real
echo "Optimimzed (mycast then dcast)"
time ./mycast.opt | grep real
time ./dcast.opt | grep real

Bitten again...and again

I think my poor long term memory is causing me to run into the same problems over and over again. One of the dumbest oversights I've made in the past (when I had no experience using a laptop), was forgetting to enable the wireless on the case before trying to connect to a network. Yesterday I was given a laptop to fix and wasn't given any indication of what was wrong. Upon booting, it seemed like someone had attempted a fresh install but had failed to complete installing all the drivers. I figured this was the only problem and set out to install the drivers. Before attempting to get wifi working I checked for the wifi toggle on the case and didn't find one; I then checked in the bios and there was only a disable or use last state option. So I just figured it was on, got driver installed which had option to enable/disable radio. After several driver installs and related utility installs with no luck when scanning for networks I noticed the function key to turn on the wifi. Can't believe I didn't look for it from the start. I knew it wasn't on but continued to repeatedly do something that wasn't working.

Another bite in the ass that I am sure I have received before (although not sure when) is due to gl_ClipVertex not being set in OpenGL shaders. I had a working graphics demo that was using reflections for water and used user-defined clip planes for rendering the reflection. The rendering is based on a scene graph that has shader nodes. Originally the rendering of the reflected image wasn't under a default shader node, meaning it was using the fixed-function pipeline. After improving the scene, everything was changed to use a different default shader, and all of a sudden the reflection wasn't correct. Assuming the change had something to do with the scene-graph, or traversal of it, I spent a bunch of time digging through other code looking for the problem, when it reality it was that I wasn't setting gl_ClipVertex. I have no idea why you would want gl_ClipVertex to be different than gl_Position. But that doesn't matter. All that matters is that I never make this mistake again.

MinGW "ln -s"

I just spent about an hour looking for a problem that didn't exist, and it is all due to the fact that "ln -s" doesn't do what I expected it to in Msys/MinGW. I have an project that uses plugins for most of the UI and assumes that the plugins reside in a specific directory (./plugins in the application directory). Most of the time I use a cross-compiler so I don't have to leave linux land. When developing in windows, with release/debug targets, I link the plugin directory to the release directory that my plugins are compiled in (ln -s plugins/release plugins). The only reason plugins have ever not loaded was due to them missing some flags during link, or when one of my plugins has the same name as a core library that I use (only because the dll's aren't prefixed with "lib" like they are in linux). Anyway, some plugins were not loading, and I couldn't figure out why--trying of course the obvious aforementioned problems. As it turned out, the linked plugin directory was not being updated with the newly compiled plugins, meaning the minor changes that I made, which would have resulted in valid plugins, were not being used. Anyhow, I spent far too long on this until realizing that the sym link was not a sym link at all.

Lighting rod simulation

Have been talking with a friend about simulating and rendering electricity for some other projects recently. I encountered a self-contained paper (http://www.cs.unc.edu/~geom/LIGHTNING/lightning.pdf) on the subject and spent a little time this evening hacking up a quick implementation of the simulating a bolt. It's way simpler than I expected, and gives me one more reason to be glad (yes I'm glad) I'm friends, I'm friends, with the Laplace/Poisson equations.

Anyhow, a crappy rendering using a coarse grid (no tracing lines, or anything fancy), blurred and combined with the gimp. I guess blogger doesn't like the gif I uploaded, so this entire post was a waste.

Voronoi

I can officially almost add 2D delaunay triangulation (or voronoi diagrams) to the list of things I have implemented (if I actually had a list it would be pretty long by now). But why bother, you ask? Well, every time I have needed Delaunay, which is more often than you would think, I seemed to end up using popen with the program qhull and writing my input data to a file and reading from the popen (or by setting up a fifo to do the writing with dup/dup2). Although this works, it is nice to have a lightweight version.

Anyway, this is blog more about debugging than anything. I implemented a version of Fortune's algorithm (from Computational Geometry: Algorithms and Applications) without using an AvlTree (yeah, I know it is not quite n*log(n), but it is fast enough). The implementation is rather straightforward, but I stumbled on a few oversights. First, was determining when the breakpoints on the beach line will converge, and second was the allowance of the sweep line to move in the reverse direction for circle events.

For the first problem, I ended up just computing the circumcenter of the 3 points, hypothetically moving the sweep-line to its y-coordinate and testing whether the breakpoints were close enough to each other. Detecting these events incorrectly will result in the data structure representation of the beach line becoming inconsistent. This for the most part made everything almost work.

Unfortunately, while checking for possible circle events, I was throwing away those events that should have already happened (e.g., y-coordinate greater than current sweep line). This turns out to be a no-no, as when I removed this check (after looking several other places for the source of the problem) everything worked great. Just finished running a script to check the triangulations with those returned from Octave, and the number of triangles seems to check out, so I am assuming that the results are okay--not very thorough, I know, but the ones I inspected visually seemed to be identical.

There are several algorithms that are named after people (e.g., Dijkstra), that seem like they are rather obvious and someone surely others would have come up with if. I'm not so sure Fortune's algorithm fits into this category.

Anyway, it sure looks neat to watch it in action. I almost gave up looking for the problem this evening. I wonder how many problems were really close to being solved and just needed a little more perseverance. I'm glad I wasted about 2 hours looking for these problems, even if I never end up using this code. Still some cleaning up to do.