Karto... 3DEER Commercial Implementation.

Alsalam alikom wa ra7mat Allah wa barakatoh

I was checking MSRS blog today, and found this interesting post...

What I see is interesting about the post is that Karto does some of the services that 3DEER can do as well as supporting more hardware too...

We are now back to think of how to exploit the market need for such type of software...
Any ideas?

Thanks,
Haytham Alaa

Opensource or what !

Alsalam alikom wa ra7mat Allah wa barakatoh

Yesterday, we have delivered our 3DEER Project to the faculty..
Today, we began to think about the future of 3DEER... will it be one of those projects kept on the shelf of FCIS Library without anyone noticing it... of course this is not what we want.

We thought to open-source it, we thought to sell it, the first choice was most preferred by me cause this let's us see whether the community will accept it and encourage it or not...

The purpose of this post is to ask whoever reads this blog about his/her opinion..

Thanks in advance

Alsalam alikom wa ra7mat Allah wa barakatoh

CCR.... Paper 1

Alsalam alikom wa ra7mat Allah wa barakatoh

It's so long since we've posted anything here...

Today we will speak a little about CCR... "Microsoft's light weight concurrency
library"

What is CCR?

It's the abbreviation for Concurrency and Coordination Runtime.. which is a library
that Microsoft recently released with Microsoft
Robotics Studio library..

CCR solves a lot of troubles we usually face when coding using Threads (and we will
see shortly how)..

Consider this sample (non-real) code:

void OnOkay(Okay state)
{
// Dothings
}

void OnCancel(Cancel state)
{
// Do Other things
}

and considering that you want to work asynchronously, that's you want to wait for a message (Okay or Cancel), know it's type and then call the aproperciate method for it, then wait for another message... etc, something like this:

void ReadMessages()
{
while (true)
{
Message message = PullMessage(DispatchQueue);
switch(typeof(message))
{
case Okay:
OnOkay(message as Okay);
...
}
}

Just that simple...
BUT, now your method waits till the handler finishes before polling the next message...
What to do ?
We can make a thread to run the handler in.. so, instead of doing this:
case Okay:
OnOkay(message as Okay);

we will replace it with
case Okay:
Thread thread = new Thread(new ThreadStart(delegate(){
OnOkay(message as Okay);
}));
thread.Start();

Again, just simple..
Now, what if I told you that the DispatcherQueue is accessed from so many threads,
What to do?
Okay, simple, put a lock statement to prevent multiple threads from accessing the
Queue at the same time..

Simple...
Now, What if it's just like this:
port.Post(new Okay());
and
port.Post(new Cancel());

and it's thread safe, controls the number of threads open, just that neat.
Isn't that better?

CCR doesn't offer a new technology, it's just an elegant way to manage you thread
pools and conccurent tasks.

A few definitions:

• Dispatcher Class:
  It's basically a ThreadPool.. which we can consider like a List of threads.. but it has a predefined number of threads (that can be passed in the constructor)
  Dispatcher Dispatcher = new Dispatcher(5);
  


• DispatcherQueue Class:
  It's a queue of delegates each holds a handler that's waiting for certain type of messages.
  
  
• Port:
  Something that you send/receive through... it's a virtual port (think about it like your printer/scanner port)
  
  
• Arbiter:
  A static class that manges adding/removing your methods (wrapped in delegate objects)

So, enough speaking about how nice CCR is...
Wait the next paper to give some sample code and explanation...

Till then, you can check a good resource: MSDN.. About CCR

Stay in touch...

Alsalam alikom wa ra7mat Allah wa barakatoh

3D- How to choose the "best point"... Part2

Alsalam alikom wa ra7mat Allah wa barakatoh

Figure 1. Cylinder shape + Flooded Contour. The surface is generated using Huang, Menq Approach explained here

Just few minutes ago, we managed to output the above image using an incremental approach. Thanks Allah.

So, what's the progress so far?

• Robotics APIs (Zezo): Managed to move the robot in an arbitrary direction.
• Motion Planning (Kisho & Moussa): Finished their first approach, working on A* (for shortest route).
• 3D Model Construction (Mustafa & Me): Just managed to output acceptable models of the Incremental Algorithm (after the Brutal Force approach)

Let's get into the topic... the "best point" in Huang Menq approach we explained in the previous post has three criteria:

1. It must fall in the K-Nearest Neighbors of both end points of the edge.
   Just get the K-NN for one end point -> List1
   then use this list to get the K-NN for the other end point.
   
2. It must fall within the area formed by neighboring edges.
   p is the boundary vertex. Any candidate to p must fall within the range defined by that semi-circle.
   
3. It must form the biggest angle to the boundary vertex.

One problem was facing us in choosing the Best Angle, is how to determine the angle in the 3D Space... I tried to draw a diagram for explanation but it was not clear... think about it. In 3D, angles are somehow meaningless.
We had to think of a way to project 3D Points onto an estimated plane so that we can measure the angle easily.
We had two ideas (Actually the first is our idea, the second is from a online document):

1. Given a vertex v, and a plane P (Normal: N, Centroid: C). The procedure is as follows:
   vec = (v - C) -> gets origin based vector for v
   norm1 = (N*vec) -> gets a normal vector to the plane that contains N & vec (norm1 will definitely fall in P)
   result = (norm1 * N) -> gets a normal to the plane that contains N & norm1 (which now falls in P & the plane that contains vec & N)
   This method we are not sure about it... so just don't use it
   
2. result = N * (N.DotMultiplyPositionVector(vec)) * -1;
   Explained here
   

The output above is generated using K = 1000. Which made the algorithm runs in a long time. We are working to know why is that.

That's all till now..

Alsalam alikom wa ra7mat Allah wa barkatoh

What 3D in 3DEER means!!

Alsalam alikom wa ra7mat Allah wa barakatoh

Mustafa and me has the 3D part of the project. Let me tell u a brief about it..

Our problem we are tying to solve is: Given a scattered 3D Points (that the robot returned) we are asked to build a smooth 3D Model.

The first time I sat to think about this task, I just thought "What a pity, we can finish this in a day and have rest for the end of the year"... I was wrong!


What you see above is how the project goes from 3D Perspective... a 3D Model (to the left), the robot returns some scattered points (the middle) we should output a 3D Model (to the right)..


The Algorithms:
We have read about a lot of algorithms.. mainly we read about two types:

• Volumetric: Which works in O(n^2) (bad of course) but produces a fine smooth surface..
  Sample : Hoppe's Paper
  

• Incremental: Which works in O(nlgn) or O(n)... (fast of course) but needs some refining after generating the mesh. Besides, it assumes the points contain no noise..
  Sample: Huang, Menq (this is not their paper, but I couldn't find their original paper free online, and this is the only source I found that explains their algorithm and implements it)
  

Hoppe's Algorithms is as follows (brief of course):

• Use K-Nearest Neighbor (we used kdTree as our data structure Implementation) to calculate the Tangent Plane for every Xi. You need two data about each tangent plane; the Centroid and the Normal.
  The centroid calculation is pretty easy, just sum the K-points and divide them by k
  To calculate the Normal, you will need to use an algorithm called Principal Component Analysis (Implementation)... this link also contains a full java implementation for Hoppe's algorithm.
  

• Now build a graph (n^2 edges) from all points to all points and do a minimum spanning tre algorithm to reduce the number of edges

• The last problem to solve is the orientation of the Normals, those generated tangent planes' normals may need to be flipped to be right-oriented with respect to the whole other surfaces.
  To do this, we decide that the surface having the maximum Z will have its normal pointing to the +ve Z direction. Starting from this oriented surface, we just propagate to determine the orientation of the planes connected to it...
  

Huang, Menq Algorithm:

• We start by building the first triangle which has one point that is the most far point in the Z-Direction and the closet two points to it this triangle 's normal is set to +ve Z Direction

• We start by considering each of the border edges, we find the Best Point (which should lie in the K-Neighbors of the two edge points. More about selecting the Best Point will come in a later Post In Shaa Allah)

This candidate point can be one of the following cases:

Case 1: the B (Best Point) is not visited yet.. just create two edges and form a new triangle.. and add it as a boundary Point.







Case 2: The B is a boundary vertex AND is a close
neighbor to e (which means it lies in the next or previous edge to e)... Add One edge to B, Add the new triangle to your list, remove the internal vertex from the boundary list.







Case 3: B is on the boundary and is NOT a direct neighbor to e.... add two edges to B, add the new Triangle to the list..







That last Algorithm, is the one we are working on now... it's fast which would enable us to make runtime model generation (while the robot is exploring) In Shaa Allah.

That's it for now..

Alsalam alikom wa ra7mat Allah wa barakatoh

First Seminar - Presentation

el salamo 3alikom wa ra7amtoo ALLAH wa baraktoo

need to see our presentation...

Click on the photo ;)

hope you enjoy it...

el salamo 3alikom wa ra7amtoo ALLAH wa baraktoo

3DEER... First Seminar.

Alsalam alikom wa ra7mat allah wa barkatoh

Today we held our first seminar at the faculty, we were really afraid cuz we felt we are not ready + we don't have a WOW thing to speak about + we just made the presentation and rehursal yesterday (from 11:00am till 12:30am)...

Al 7amd lellah the seminar was good and the professor liked it.
Here are some pictures for our seminar:

Kamal... speaking

Zezo... Speaking

Moussa... Speaking, Our friend Sara taking photos with her mobile

We will be putting our presentation soon In Shaa Allah.

Stay in touch,

Alsalam alikom wa ra7mat Allah wa barakatoh

Yours,
Haytham Alaa