Parallel Convex Hull CUDA

1) gHull - http://www.comp.nus.edu.sg/~tants/gHull.html
- They haven't released the source code till now.

2) Parallelizing Two Dimensional Convex Hull on NVIDIA GPU and Cell BE, by IIIT Hydrabad folks.

- They specifically focus on CUDA.

3) Graham Scan algorithm for convex hull also seemed quite popular for parallelizing
- Chris Harrison's page on the same algorithm is helpful; also has a sequential-version source-code.

4) Mathematica's page on CUDA convex hulls

5) Optimal Multi-Core Convex Hull

6) Doing QuickHull on GPU - NVIDIA research summit poster here

- That's a research paper.

- Source Code: No idea

Among most of the above algorithms I think that QuickHull is the most amenable for parallelization.

SIFT features

http://blogs.oregonstate.edu/hess/code/sift/
http://stackoverflow.com/questions/5461224/package-gtk-engines-2-was-not-found-in-the-pkg-config-search-path

Digging even more with ICP

The options that come with the CICP class are crucial
- icp.options.smallestThresholdDist(playing with this creates horribly bad clouds)
- icp.options.thresholdDist
- icp.options.thresholdAng

- icp.options.ICP_algorithm(Only 'icpClassic' is implemented for ICP-3D)
- icp.options.maxIterations(its default may create a problem, better explicitly keep it very high)
-icp.options.doRANSAC



Why is ICP not coverging?
How to control the internal RANSAC within ICP (can we provide known correspondences to it?)
Why ICP returns pdf and then we need to take mean? Isn't ICP supposed to compute just one R,T?

Digging more with ICP

This post is a continuation of my last post that talks about using ICP to register two coarsely registered point clouds. That post talked about getting the test.cpp code that comes with MRPT library to perform ICP on two point-clouds. That code synthetically creates two small point-clouds, introduces a random small difference in there poses, and then calls ICMP::align3D() to register the point-clouds.

My plan is to use the ICP API for kinect-generated point-clouds, which are naturally much bigger and noisier than the synthetic point-clouds the original test.cpp generates. 

Until now I did the following tests:

case 1) A single kinect-generated point-cloud was fed as two point clouds, the difference being the same random pose difference that the original example introduces. This worked great. The point-cloud were aligned nicely. Note that the same point-cloud was fed (with some small pose difference), so there was 100% overlap between the two point-clouds. 

case 2) So now I fed two point-clouds with around 20% overlap, but already almost registered (manually in MeshLab). This worked horribly. 

So, we see that, initial coarse registration doesn't really help as much as the overlap does.

case 3) Now I am thinking, before feeding the point-clouds to ICP,  we can delete the non-overlapping regions from the both the pointclouds, so that the %-overlap would be much much higher. Note that doing ICP with such new point-clouds would still result in the same R,T output. So, we would get the same output conservatively. The advantage is two-fold: smaller input point-clouds means faster ICP and higher-%-overlap means much more accurate answer.

As expected, This worked better: much much more accurate answer, plus, much faster :)

Note that though the point clouds had more %-overlap they were NOT coarsely registered already as we had in case(2), that makes it little harder. So if we had an initial coarse pose estimate, then I believe we should get awesome results. 

So let's do that-

Now, we will not only keep just the overlapped parts of the point cloud, but keep them coarsely aligned. That would be our case (4).

case 4) Shockingly and sadly, it went horrible x-( .... I should try it again !!!!

my progressive photon mapping implementation

Finally I have got progressive photon mapping (without participating media, with surfaces) working :) yay!

Details on that would come later, when I would get some time margin to write about it descriptively, but the following output image may give you an idea of how much has been done till now...

Let me be honest, I loved the caustics :) If you see carefully, you may find some color bleeding happening too...which makes me even happier! The rendering is with a single light-source emitting 1 billion photons, and took around 4-5 minutes of execution time.

The next task in line is inclusion of participating media. I have been reading [0], [1], and [2] to understand the concepts needed, although they won't tell me how to do that in my framework of progressive photon mapping. So, I will be needing to understand how it works with participating media in regular photon mapping, and then design how it should be done in progressive framework. Hope that's fun...;)

Other important resources which would be helpful sooner or later
1. Praca dyplomowa's CUDA implementation for participating media rendering with photon mapping

2. Really good wiki that explains that concepts of participating media rendering in a very friendly and grounds-up manner
3. A survey on participating media rendering techniques (2005)
3. 

References

[0] A Practical Guide to Global Illumination using Photon Maps Sig'2000

[1] Efficient Simulation of Light Transport in Scenes with Participating Media using Photon Maps Henrik Wann Jensen

[2] Jensens Book Realistic-Image-Synthesis-Using-Photon-Mapping (Chapter 10)

Loading .OBJ 3D model files in OpenGL code

Tudor Carean provides an extended version of GLM and tutorial on how to use it in your code. He also provides tutorials on Creating a 3D Model, Exporting the model, Getting GLM, Importing the model in C++ and Details about GLM structure.
I would personally prefer sticking to the original GLM, instead of the one Tudor wrote, just because I believe its would be safer. You can download the original GLM from here.


What is GLM?[0]
Glm is a library that was provided in the examples folder of the GLUT source distribution. It provides API functions to read Wavefront .OBJ file (and corresponding .mtl materials file), and also for rendering these models in your openGL program. The required input files can be generated using 3DS Max or MeshLab (see here to know how to do that). Basically GLM knows how to read a Wavefront .OBJ file and knows how to draw it on the screen exactly the way it looked in 3D Studio Max. Well actually it can do a lot more[0].
GLM reads the model files into a data structure it calls as _GLMmodel. To know more about this data structure and understand its internals you can read Tudor Carean's tutorial for the same.


Good Online Sources for Downloading Free 3D Models 

• http://www.chromesphere.com/3dmodels.html
• http://www.3dm3.com/modelsbank/cat.htm
• http://people.sc.fsu.edu/~jburkardt/data/obj/obj.html
  (This page is an excellent page that summarizes everything pertinent to OBJ files)
• http://gts.sourceforge.net/samples.html

[0] http://www.3dcodingtutorial.com/Working-with-3D-models/Getting-GLM.html

CUDA Kd-tree Implementations

My motivation of going after CUDA kd-tree implementations is to be able to do the k-Nearest-Neighbors (a.k.a. KNN queries) queries in Delaunay triangulation (DT) procedure. The incremental algorithm of DT requires us, to find the a point with nearest delaunay distance to the given edge. The delaunay distance of a point to the line is not equal to the Euclidean distance between the two, but the points that are Euclidean-distance-wise closer to the edge, are more probably of being closer delaunay-distance-wise. Without any optimization or acceleration structure, finding the delaunay-closest point would require us to check every point in the input point-cloud to find the minimum. So, if we could somehow conservatively limit ourselves to a subset of all n points, that would speed-up the algorithm significantly. Ergo, I thought of kd-tree. If we could do a prepass where we take all n points and organize them in a kd-tree, finding such a subset of points is equivalent to doing KNN queries. There is still one unanswered question in my mind, why isn't the euclidean-nearest point to an edge equal to the delaunay-nearest point to the edge? Or is it? If yes, then why don't we just find the closest find (the nearest neighbor), why to do all the circumcircle computations? There should be some reason why we do so, that makes the euclidean-closest point not necessarily the delaunay-closest point to a given edge.
Well, following are, in my opinion, good resources for kd-tree on CUDA:

[0] http://www.nvidia.com/content/nvision2008/tech_presentations/Game_Developer_Track/NVISION08-Interactive_Ray_Tracing.pdf


[1]  MNRT  (here)
The "Source Code Availability" section of the documentation of MNRT says that "Source code of MNRT will be available soon. I still need to update some Doxygen comments to be ready for this step". So no source code for now.
so, MNRT rating: 1/5 - mainly because lack of source code ;)

[2] <<TODO>> http://code.google.com/p/cuda-kdtree/source/checkout
I could download and compile the code successfully. The code is meant for Windows and uses some Windows-specific calls for setting up the timers, which can be simply commented out to make the code run on Linux (I use Ubuntu Maverick 10.10). The code takes an .obj model file, reads its vertices, and constructs a kd-tree with those points on GPU. It writes the kd-tree blocks into an output file (named "kdtree.will").
I suspect that the code is an implementation of [0], simply because the one authors of the code and that of the paper is named Rui. But that's just a guess. If it's so, the paper can help understand the code more.
The only problem I found with the code is that it does not provide the nearest-neighbor queries to the kd-tree, yet. It just constructs it. The next code I will talk about even provides such functions.
so, rating:  3/5 - good code but no nearest neighbor queries yet.

[3] <<TODO>> Nghia Ho's blog post on KD-tree on GPU for 3D point searching discusses his implementation and results. His implementation also includes the nearest neighbor searching.

so, rating:  ??/5 - good code but no nearest neighbor queries yet.


[4] <<TODO>> Shawn Brown's implementation - http://www.cs.unc.edu/~shawndb/
* is 2010 work.
* has source-code.
* support for 2D, 3D, 4D point data.
* has GPU kernels for Query nearest neighbor (QNN), All-Nearest Neighbor (All-NN), 'k' nearest neighbor (kNN), and All 'k' Nearest Neighbor (All-kNN).
* has documentation- has corresponding 2010 paper by himself.
so, rating:  ??/5 - all above reasons.

[5] Zidan's implementation: http://www.mahmoudzidan.com/WorkArchive/
* Not tested yet!


[6] Kd tree on GPU for 3D point searching: http://nghiaho.com/?p=437