Showing posts with label nvidia. Show all posts
Showing posts with label nvidia. Show all posts

2011/09/30

research news

I don't have new stuff to show right now, but I've been busy in the last week. I'm currently implementing a more dynamic version of my renderer. CUDA is very nice, but when you need to add quickly new modules or do some rapid tweaks, it's not the best solution. So, for now the plan is to render to have a slower renderer that would be easier to change and adapt. When we're sure of the features that we really want to keep and we'll know the full limitation of our system, an implementation in CUDA would be possible.

One of the reason to change the renderer is that I needed some C++ features like virtual functions, which is very useful for designing rapidly a new system. I think there's some language that allows to create virtual function in CUDA or OpenCL by simply adding some hidden piece of code.

If it doesn't exist, here's how I'd do it:

First, in CUDA, there's no function pointers. But if we take a look at how polymorphism works, it's really just a way to disguise procedural code. Actually, the whole object oriented programming scheme is just a way to disguise procedural code by hiding some information to the programmer so (s)he doesn't have to worry about it. Just like many other languages do (Java is the most popular about that one because it hides a lot of security features like buffer overflows done during the execution to avoid major problems).

So, if we have:
class A
{
private:
  int value;
public:
  A(void);
  virtual ~A(void);
  virtual void test(T param1, U param2);
};
Then this piece of code is actually converted into something that look basically like this:
// prototypes
struct class_A;
void __class_A_constructor(struct class_A *this);
void __class_A_destructor(struct class_A *this);
void __class_A_test(struct class_A *this, T param1, U param2);
struct class_A_virtual_table
{
  void (*class_A_destructor)(struct class_A *this);
  void (*class_A_test)(struct class_A *this, T param1, U param2);
};

// create a single instance of the virtual table and assign the values for the function pointersstruct class_A_virtual_table class_A_virtual_table_only_instance_needed =
{
  __class_A_destructor,
  __class_A_test
};
struct class_A
{
  class_A_virtual_table *VT;
  int value;
};
void __class_A_constructor(struct class_A *this)
{
  this->value = 0; // or some other default value
  this->VT = &class_A_virtual_table_only_instance_needed;
}
void __class_A_destructor(struct class_A *this)
{
  // stuff to destroy
}
void __class_A_test(struct class_A *this, T param1, U param2)
{
  // stuff to test
}
// virtual functions
void virtual_class_A_destructor(struct class_A *this)
{
  this->VT.class_A_destructor(this);
}
void virtual_class_A_test(struct class_A*this, T param1, U param2)
{
  this->VT.class_A_test(this, param1, param2);
}
And then, with a subclass B, we have:
class B: public A
{
private:
  double value;
public:
  B(void);
  ~B(void);
  void test(T param1, U param2);  // version of test but for class B
  void function_in_B(void);
}; 
int main(void)
{
  B b;
  A *a = &b;
  a->test(1, 2);  // let way that type T and U are integers...
  b.function_in_B();
}
Then, all of this become:
struct class_B
{
  struct class_A super;
  double value;
};
// prototypes for class B
void __class_B_constructor(struct class_B *this);
void __class_B_destructor(struct class_B *this);
void __class_B_test(struct class_B *this, T param1, U param2);
void __class_B_function_in_B(struct class_B *this);
// virtual table for B, with the virtual functions for B
struct class_A_virtual_table class_B_virtual_table_only_instance_needed =
{
  __class_B_destructor,
  __class_B_test
};
void __class_B_constructor(struct class_B *this)
{
  __class_B_constructor(&(this->super));
  this->VT = &class_B_virtual_table_only_instance_needed;  // replace the virtual table
  this->value = 0.0; // or some other default value
}
void __class_B_destructor(struct class_B *this)
{
  // stuff to destroy in B
  __class_A_destructor(&(this->super));  // then, destroy the stuff in the parent
}
void __class_B_test(struct class_B *this, T param1, U param2)
{
  // stuff to test, but for B
}
void __class_B_function_in_B(struct class_B *this)
{
  // whatever that function does!
}
int main(void)
{
  struct class_B b;
  __class_B_constructor(&b);
  struct class_A *a = &(b.super);  // the address of the parent in struct class_B
  virtual_class_A_test(a, 1, 2);
   __class_B_function_in_B(&b);
  __class_B_destructor(&b);
}
So, as you can see, polymorphism is using function pointers to create the illusion that the right function is called each time.

But, without any function pointers, we need to recreate that illusion. So, one way that can be done in CUDA/OpenCL, is to add a unique ID for each class. And each instance of that class will have that ID assigned in the constructor. So:
enum CLASS_IDS { CLASS_A_ID, CLASS_B_ID, ..., CLASS_X_ID };
struct class_A
{
  int ID;
  int value;
};
void __class_A_constructor(struct class_A *this)
{
  this->ID = CLASS_A_ID;
  this->value = 0; // or some other default value
}
struct class_B
{
  struct class_A super;
  double value;
};
void __class_B_constructor(struct class_B *this)
{
  __class_A_constructor(&(this->super));  // always call the parent constructor first!
  this->ID = CLASS_B_ID;  // overwrite the ID
  this->value = 0.0; // or some other default value
}
Finally, write the virtual functions like this:
void virtual_class_A_destructor(struct class_A *this)
{
  switch(this->ID)
  {
  case CLASS_A_ID:
    __class_A_destructor(this);
    break;
  case CLASS_B_ID:
    __class_B_destructor((class_B*)this);
    break;
  // ...
  case CLASS_X_ID:
    __class_X_destructor((class_X*)this);
    break;
  };
}
So, with a switch statement, it's possible to replace the virtual table. So, a compiler that would be able to take C++ code and convert it in CUDA/OpenCL would be able to do polymorphism with that approach. It's much more slower than a function pointer, but the result of the computation would be the same.

I think that such compilers exist already, but I never used one of them. But it's probably using a method similar to the one above to emulate the virtual tables.

And for those of you who didn't know how polymorphism worked, now you have a better idea of the process the compiler has to do to convert classes and their virtual functions in machine bytecode. So, I hoped that post helps a bit for that. Otherwise, there's a couple of resources available on the web that would clearly describe that process.

If any of you know a (free if possible) compiler that convert basic C++ code in CUDA or OpenCL, but also has integrated some of the features of those languages like the synchronization between threads of the same bloc and atomic operations, I'd really like to see that and use it eventually. It must work on Linux!

2011/07/08

merging voronoi

Here we are playing again with the Voronoi diagram (VD). We wanted to see what happen when sites are merged together (MVD, merged VD).

VD partitions the plane in cells where each of these cell represents the closest part of the plane to a particular site. So, if you have sites on a map of various fast food restaurants, the Voronoi diagram tells you which one is physically the closest to your location.

But imagine that we want to consider all restaurant from a particular chain as one entity. We want to know the influence or the domination of a particular chain.

The following images are in pair. The first one is the influence of a chain of restaurant and the second is the actual VD that everyone knows. Cells with the same color represents a chain of restaurant.





In the images, you can see some brighter points (particularly in the first two images), this is the actual location of the site (or restaurant for in our example).

And just like the VD is well known for its role in texture synthesis, we hope to find a way to use the MVD to create some interesting results.

As for the diagram itself, we don't really know what to do with it or how to interpret it. VD has a dual graph called the Delaunay Triangulation. But what would be the dual graph of MVD ? Where do we put the edges ? That's an open question.

2011/07/04

More texture synthesis

In this post, I present some new result that we really like. Again, it's a variation of the Voronoi diagram. You can observe the Voronoi cells interacting with each other. The colors help to see clearly the cells. And because of the few number of color, some cells might share the same color but are not related at all.

Here's some of the results:








This method, if it produces the result we're expecting, can be used to create texture by simply specifying some parameters or an artist can use a program with that method implemented to place some control points and control other parameters.

Again, all these images can be computed with CUDA because each pixel is unique.

2011/06/27

mosaic

Yesterday I mentioned using images as a source for the points and orientations. And I managed to do something.

First, the original image (a South Park version of myself, before I lose some weight):



And here's the various mosaic:







I used various effects to control the orientation in the cell. Plus I tried a random point selection, except for the first output.

Which one do you prefer ?

Naturally, to produce the output, I'm still using CUDA. I didn't used any data structure to optimize, so it can be computed a bit faster.

More textures

In my research, I'm still working on my textures. Here's some results I produced today that I really like.








Those effects might be implemented in a next version of my live-wallpaper. I haven't decided yet. For the first two images, I put the orientation of the points right on the plane. Plus I tried a new function to compute the distance. This one allows some distance pixels to actually have a distance of zero when it's perfectly aligned with another points.

Next, I will try to use images as a source of points and orientations. To see if with this method it's possible to create mosaic from an image. Creating mosaic with the normal Voronoi diagram is something well known in the literature. But with this method of oriented points that creates cells that are not convex polygons might allow us to do something very unique.

Let me know what you think of these images.

2011/06/21

Yin Yang Texture

Here's a post on texture.

Previously, we were using a method to control images with points and normals. Alone, a point and a normal split the plane in two, a positive and negative part. But combined with other points and normals, we can actually control curve shapes. To visualize it, we assign white to the positive part and black for the other.

The textures proposed here are made by first splitting the plane in two parts. The two parts must be symmetrical just like the Yin Yang symbol.

We then distribute points and normals inside one of the part. We then reflect the point into the second part, but not the normal.

The method create a contrast and a perfect symmetry. Here's some results:




I won't describe the method to render those images because it's very complex. Also, the process is very slow. Unlike the live-wallpaper I'm working on, or the previous images I showed, we cannot compute those in real-time.

Unfortunately, we haven't implement this with CUDA. With CUDA, it wouldn't be in real-time, but it would be much faster. Specially the per-pixel rendering part. Let me know what you think about these Yin-Yang images.

2011/06/01

The Background

The image I used as the background, at least the one used when I created this post, is a Voronoi diagram. To draw this diagram, we don't use any algorithm to find the vertices and edges of the diagram.

Our procedure consists first of splitting the unit square in YxY cells where each cells contains between 1 and X points. To render the image, that is a square of ZxZ pixels, we first convert the coordinate of the pixel into the unit square, then find in which cell the pixel is.

To draw the diagram, we need the two closest points from that pixel. To find it we first compare the pixel with other points in its cell. Then we also explore the surrounding cells to be sure to find the exact two points. When a cell is on the border of the square we use the cell on the other side to create a texture that can be tiled.

Let d1 and d2 be the distance from the pixel to the closest and second closest point respectively. Then, we can determined the gray color of that pixel as (d1/d2) * 255. Other method can be used too to determined the right color. The ratio d1/d2 gets a value of 0 when the pixel is right on the closest point and a value of 1 when the pixel is right between the two points. Therefore, in this case, the white pixels are part of a segment on the Voronoi diagram. The following image was created with this approach.



For our image in the background, we use an interpolation to determined the color for the pixel. Plus, we used d3, the distance from the third closest point to the pixel.

For the interpolation, we solve the following linear system:


| 0 0 1 || x |    | 1 |
| 1 1 1 || y | = | 0 |
| a b 0 || z |    | 0 |


where a and b are two different constants.

Then, the color of the pixel is determined by 255 * ((d1/d2) * x + (d1/d3) * y + z). Naturally, if the value is above 255 or below 0, we considered them as 255 or 0.

To program this procedure, we used CUDA. With CUDA, each pixel gets his own thread and even with an older version of CUDA (I just have CUDA 1.1 on my GeForce 9800 GTX+) the computation is done in less than a second for a 1024x1024 images.

The work load associated with a pixel is determined by the value X, the maximum number of point in a cell. To find the two (or three) closest point to a pixel, the maximum number of point to check is 9X. The memory required for the diagram is proportional to Y*Y*X.


REFERENCE


Steven Worley. 1996. A cellular texture basis function. In Proceedings of the 23rd annual conference on Computer graphics and interactive techniques (SIGGRAPH '96). ACM, New York, NY, USA, 291-294. DOI=10.1145/237170.237267 http://doi.acm.org/10.1145/237170.237267