3D Enviroment Exploration using lego NXT Robot - 3DEER

Karto... 3DEER Commercial Implementation.

2007-12-20T08:47:00.001+02:00

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 !

2007-06-27T07:04:00.000+02:00

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

2007-04-25T17:56:00.000+02:00

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

2007-02-23T16:49:00.000+02:00

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:

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.
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.
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):

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
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!!

2007-02-12T16:55:00.000+02:00

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

2006-12-11T01:29:00.000+02:00

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.

2006-12-10T08:12:00.000+02:00

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

First Seminar Preparations - episode 1

2006-11-22T01:00:00.000+02:00

el salamo 3alikom wa ra7amtoo ALLAH wa barakatoo

Its my first post on 3DEER blog, I really feeling very interesting to work in that project with my team mates that I really respect.

we prepared for that seminar in just 2 meeting, first one was at my home, Haytham was the first one to arrive with our lovely baby robot, It was the first time for us to meet, It was really a shock when I first saw him,as it was small, cuty,tiny little one :D, but we had a deal that we're going to do the mission to gether ISA, and I really trust him.

While waiting for others to come, three of us began to play together with my LEGO toys, as me and Haytham remembered our past experience playing with LEGO, we really had fun :D.

Mustafa arrived but rest of the partners couldn't make it that day, Brainstorming..., to make the presentation.

we made it :D, we gathered all what we need to write in the presentation and we wrote a draft, we said that we need to meet another time with the rest of the team to finalize the presenation and begin the rehearsal, Mustafa and Haytham left with the lovely baby...

Thank you ALLAH

c u in the next episod

el salamo 3alikom wa ra7amtoo ALLAH wa barakatoo

3Deer is moving

2006-11-05T21:01:00.000+02:00

Alsalamalikom wa ra7mat allah wa barkatoh

Today,
I can say 3Deer learnt how to obay its master (Me :D)
I spent few days to figure out how to make it work probably with my MSRS(Microsot Robotics Studio), I got almost all errors found online :D..PleaseScroll down, for some reason, the rest of the Post is down there....

Action:

Connect from NXT to PC

Error Message:

Line is Busy

Resolution:

Restart the Serial Port Service from ur Bluetooth Manage on the PC

Action:

Sending msrs.rbt from LegoNXT Manager to the Brick

Error Message:

Cannot find needed files

Resolution:

Manually send the Config file in Samples\Platform\Lego\NXT\Resources to the Brick(You will still get the same error cuz of the start image and such things, u can ignore then or edit the msrs.rbt and choose one of the current images)

Action:

Starting the Tutorial1 Dss Node

Error Message:

Invalid Serial Port / Unable to connect to Lego NXT

Resolution:

1- Check ur Bluetooth connections to know the port given to you Brick and put it in the config page.
2- Disable the Second Serial Port in ur Bluetooth Stick manager.
3- Manually start the MSRS program on ur Brick.. it'll crash and close, try to start it again...

Action:

Using Tutorial1

Error Message:

The Bumper's message is not sent.

Resolution:

I couldn't figure out why till now. Howerver, Tutorial4 (which controls ur Motors) works very well..

Action:

Building RoboticsTutorialX

Error Message:

Cryptographic failure while signing assembly 'D:\Microsoft RoboticsStudio (1.0)\samples\RoboticsTutorials\Tutorial1\obj\Debug\RoboticsTutorial1.Y2006.M06.dll'-- 'Error reading key file 'c:\mri\main\share\version\35MSSharedLib1024.snk'

Resolution:

The default key file used for signing all the assemblies is calledmrisamples.snk and can be found at
D:\Microsoft Robotics Studio(1.0)\samples.
1) Check your project properties, right click the project name inSolution Explorer and choose Properties. Choose the Signing tab and makesure the Sign the assembly checkbox is checked and the URL is
D:\Microsoft Robotics Studio (1.0)\samples\ mrisamples.snk or..\..\mrisamples.snk
2) Go to the Build Events tab ad check the Post-build event command linehas the following parameter: /keyfile:"D:\Microsoft Robotics Studio(1.0)\samples\mrisamples.snk"
3) In the Debug tab, "Start external program", change it to be:D:\Microsoft Robotics Studio (1.0)\bin\DssHost.exe, and so the "Working Directory" to be: D:\Microsoft Robotics Studio (1.0)\Reference

3DEER is moving around.. my family is just saying "Hey haytham, call your Baby"

That's all for now..

C u next Post..

Alsalam alikom wa ra7mat allah wa barakatoh

Yours,Haytham Alaa

Ultrasonic Sensor tests

2006-10-15T20:24:00.000+02:00

Alsalam alikom wa ra7mat allah wa barakatoh

Today, I've been searching around a little bit to know more about ultrasonic sensors...

I found some interesting tests (done by students for their project too) here...

My doubts :
1- The sensor's accuracy :
if two sufaces with small difference in Z Axis, the robot may c them the same which may lead to bad model..
2- The StepperMotor steps:
if the stepper motor uses large steps, then we will not be able to get accurate results

Conclusion after today's search :
1- The best results taken from the sensor is when the measured distance was over 50cm & below 200cm which is a good sign, the worest case error is +/- 3cm.. which is not bad...
2- No new about motors yet....

Alsalam alikom wa ra7mat allah wa barakatoh

Yours,
Haytham Alaa

3DEER... What is this ?

2006-10-15T20:14:00.000+02:00

Alsalam alikom wa ra7mat allah wa barakatoh,

This is our first post here, so let's tell you what is this all about...

1st 3DEER means : 3D Environment Explorer using Lego NXT Robots..

2nd that long name means : You put your young robot inside an unknown room or building, and it'll explore there for some time then comes out with a 3d fine model for the room.. cool, huh ?

3rd Who are we ?
We are a group of 5 Computer Science Students, Faculty of Computer and Information Sciences, Ain Shams University, Cairo, Egypt.

Our names :
1- Mustafa Mahmoud Mohie
2- Mohammed Mustafa Moussa
3- Mohammed Abdul-Aziz
4- Kamal El-Dien Mohammed
5- Haytham Alaa Al-Dien Hussein

That's all for the first post,
Stay in touch....

Alsalam alikom wa ra7mat allah wa barkatoh

Yours,
Haytham Alaa.