Geometric Primitives and Geomtric Operations with Matlab
Matlab does not come by default with a geometric primitives library. About for some simple function like the “sphere” command, using some geometric entities may be an issue. Fortunately on Matlab file exchange are available these two packages, from David Legland ,that help us to develop geometric projects.
- Geom2D Download Now
- Geom3D Download Now
The packages include functions for computations on planar and spatial geometrical shapes (points, lines, circles, polygons…)
The goal is to provide a low-level library for manipulating geometrical primitives, making easier the development of more complex geometric algorithms.
The library proposes functions to:
- create various shapes (points, circles, lines, ellipses, polylines, polygons) using an intuitive syntax. Ex: createCircle(p1, p2, p3) to create a circle through 3 points.
- derive new shapes: intersection between 2 lines, between a line and a circle, parallel and perpendicular lines
Functions to compute intersections - work on polylines and polygons: compute centroid and area, expand, clip with half-plane…
- measure distances (between points, a point and a line, a point and a group of points), angle (of a line, between 3 points), or test geometry (point on a line, on a circle).
- manipulate planar transformation. Ex: P2 = transformPoint(P1, createRotation(CENTER, THETA));
- draw shapes easily. Ex: drawCircle([50 50], 25), drawLine([X0 Y0 DX DY]). Some clipping is performed for infinite shapes such as lines or rays.
- functions for 3D polygons and polyhedra. Polyhedra use classical vertex-faces arrays (face array contain indices of vertices), and support faces with any number of vertices. Some basic models are provided (createOctaedron, createCubeoctaedron…), as well as some computation (like faceNormal or centroid)
- direct drawing of shapes with specialized functions. Clipping is performed automatically for unbounded shapes such as lines or rays. Ex:
drawPoint3d([50 50 25; 20 70 10], ‘ro’); % draw some points
drawLine3d([X0 Y0 Z0 DX DY DZ]); % clip and draw straight line
Popularity: 3% [?]
GLTree Pro Version: a fast nearest neighbour library for Matlab and C++
Filed under: Algorithms, Computational Geometry, Geometry, Graphics
Contents
Introduction
The nearest neighbor search problem arises in numerous fields of application, including:
- Pattern recognition – in particular for optical character recognition
- Statistical classification- see k-nearest neighbor algorithm
- Computer vision
- Databases – e.g. content-based image retrieval
- Coding theory – see maximum likelihood decoding
- Data compression – see MPEG-2 standard
- Recommendation systems
- Internet marketing - see contextual advertising and behavioral targeting
- DNA sequencing
- Spell checking - suggesting correct spelling
- Plagiarism detection
- Contact searching algorithms in FEA
- Similarity scores for predicting career paths of professional athletes.
- Cluster analysis – assignment of a set of observations into subsets (called clusters) so that observations in the same cluster are similar in some sense, usually based on Euclidean distance
The algorithm
The reason that pushed me to develop this algorithm was the need of more speed in nearest neighbors search. The first implementation of GLTree was coded in the September 2008, and a first, rough, but very fast version was uploaded on Matlab File Exchange as C++ code to compile into MEX file in November. These version are still available and open-source:
After using this library for about a year I released the potential and I decided to make a step further. In this page a faster and low memory version is proposed. Many more functions have been developed like: a nearest neighbour filter radius search and a cuboid search and many more can be developed.
Perfomances
This are the timings for a NNGraph in 2D and 3D on my 2.4Ghz laptop. Test is run on uniform randomly points in 0-1 range. Given a set of N random points, for each one finds his nearest neighbour.
START NNGraph Test: 2D NNGraph of 10 points took: 0.0001 s NNGraph of 100 points took: 0.0001 s NNGraph of 1000 points took: 0.0004 s NNGraph of 10000 points took: 0.0039 s NNGraph of 100000 points took: 0.0629 s NNGraph of 1000000 points took: 1.1897 s 3D NNGraph of 10 points took: 0.0014 s NNGraph of 100 points took: 0.0001 s NNGraph of 1000 points took: 0.0007 s NNGraph of 10000 points took: 0.0075 s NNGraph of 100000 points took: 0.1219 s NNGraph of 1000000 points took: 2.4760 s TEST SUCCESFULLY COMPLETED !!!
You can run this test by downloading the demo version (linux and win32):
Download GLTreePro Demo
For very sparse data, like logspace data, GLTree becomes slower. It may be convenient using others algorithm. For more see this post:
A comparison of GLTree with Kd-Tree and Bd-Tree
Release
- 15/02/2010 GLTreePro_v1.0
Matlab
This release includes the following MEX files:
- 2D
- K-Nearest Neighbor Search
- K-Nearest Neighbour Graph
- Nearest Neighbour Filter
- Radius Search
- Cuboid Search
- BuildTree
- DeleteTree
- 3D
- K-Nearest Neighbor Search
- K-Nearest Neigbour Graph
- Nearest Neighbour Filter
- Radius Search
- Cuboid Search
- BuildTree
- DeleteTree
We support Win32 and Linux platform. Source code is currently not supported. The package includes all the MEX files plus .m files for the help command.
| Version | Minimum Support amount |
| 2D | 10 euro |
| 3D | 10 euro |
| 2D&3D | 15 euro |
or on the following bank account:
| Name | Luigi Giaccari |
| IBAN | IT 07 E05550 77710 000000483947 |
Please e-mail at: giaccariluigi@msn.com after the donation. You will soon receive the latest version of the GLTree library and all following updates.
C++
Under Construction. You need it? tell me and I may speed up the development.
Examples
See the examples for 2D:
Popularity: 2% [?]
Delaunay2_5D: a Straightforward Algorithm for Fast Surface Reconstruction
Filed under: Algorithms, Computational Geometry, Graphics
Description
Delaunay2_5D is an algorithm for fast surface reconstruction from scattered points cloud. The algorithm is designed to be quick and light. With this tool you’ll be able to reconstruct on your “little” laptop huge points cloud (several millions of points) which are generally considered a Workstation Job.
The project was made possible thanks to the collaboration of Luca Di Angelo and Di Stefano Paolo.
The algorithm uses a mesh growing approach: starting form a seed triangle a front propagation is performed. This technique is generally less accurate than the ones that use Delaunay Triangulation, on the other side they are terribly faster and lighter, so they are preferred for huge models
Perfomances
Models
A few models to test the algorithm and verify the perfomances:
| Model | Number of points | Call |
| Nicolò da Uzzano (the one in the picture) | 1M | Delaunay2_5D.exe |
| Thai Statue | 5M | Delaunay2_5D.exe i 3 p1 a 20 |
| Foot | 10k | Delaunay2_5D.exe i 2 p1 |
| Armadillo | 170k | Delaunay2_5D.exe |
| Happy Buddha | 500k | Delaunay2_5D.exe i3 p1 f5 a 25 |
| Dragon | 430k | Delaunay2_5D.exe i2 p1 f5 a 30 |
| Rolling Stage | 600k | Delaunay2_5D.exe |
| Pala(Turbine Blade) | 350k | Delaunay2_5D.exe i 3 f 20 p 4 |
| Neptune | 2M | Delaunay2_5D.exe i 3 p1 a 20 |
| Blade | 850k | Delaunay2_5D i 5 p 2 f 20 a 25 |
| Pulley | 580k | Delaunay2_5D a 25 |
Delaunay2_5D take as input a binary file. To build your own input file see the usage below.
Usage
How to build an input file and how input parameter works can be found here:
Release
We currently have only one Win32 version of Delaunay2_5D.
Download for Win32
Release History:
- Delaunay2_5D v1.0 ( 01/02/2010)
- Delaunay2_5D v1.1 ( 15/02/2010)(It is now possible to insert the input file name as parameter)
Demo version
The demo version differs from the original in the output mode. It has no output parameter so it forces tha user to suppress STL file creation and to visualize the reconstructed surface in output window.
Contributor version
The contributor version returns an STL binary file of the reconstructed surface. It can be obtained with a small donation as encouragement to improve the code itself. The project was realized without any kind of economical help from any academic or commercial organizations.
|
Delaunay2_5D: Fast Surface Reconstruction– Contributor version is reserved to donators. The amount of the donation is 30 euro.
|
|||
| Once you have done this, please email us: giaccariluigi@msn.com As soon as possible (in a few days) you will receive our new release (and all future updates) of Delaunay2_5D. Alternatively, you can bestow using our banking coordinates:
|
|||
| Name : | Luigi Giaccari | ||
| IBAN (International Bank Account Number) : | IT 07 E05550 77710 000000483947 | ||
Further informations can be obtained on my skype contact: luigi.giaccari
Release notes
The Software provided has to be considered “as is” and it is without any kind of warranty. The authors deny any kind of warranty concerning the code as well as any kind of responsibility for problems and damages which may be caused by the use of the code itself including all parts of the source code.
Contacts
Delaunay2_5D is always under development…
For any problem, suggestion, question, bug report, whatever….
- giaccariluigi@msn.com
- skype contact: luigi.giaccari
Popularity: 4% [?]
Delaunay2_5D: Performances
Filed under: Algorithms, Computational Geometry, Graphics
Go to Main Post
Perfomances
| Model | n° of input points | n° of output triangles | Time [s] | Mem. Usage [MB] | Rate [ktriangle/s] | Defectivness | |||
| nnmv | holes | ||||||||
| nholes | nbe | ||||||||
| Open surfaces | Foot (**) | 10010 | 19972 | 0.31 | 2.39 | 630.1 | 0 | 0 | – |
| Rolling Stage (**) | 596903 | 1193303 | 2.58 | 150.72 | 460.1 | 3 | 15 | 505 | |
| Valve seat (†) | 675049 | 1348338 | 3.08 | 170.55 | 438.2 | 8 | 20 | 1456 | |
| Nicolò da Uzzano (**) | 946760 | 1891992 | 3.81 | 238.96 | 454.2 | 1 | 0 | – | |
| Thai Statue (*) | 4999997 | 9994088 | 20.43 | 1238.62 | 489.0 | ||||
| Closed surfaces | Rocker-arm (**) | 10044 | 20084 | 0.38 | 2.39 | 515.2 | 0 | 0 | – |
| Stanford Bunny (*) | 35947 | 71884 | 0.097 | 9.05 | 735.3 | 0 | 0 | – | |
| Horse (**) | 48485 | 96859 | 0.14 | 12.61 | 673.9 | 2 | 2 | 19 | |
| Armadillo (*) | 172975 | 345934 | 0.520 | 41.79 | 665.7 | 0 | 0 | – | |
| Pulley (**) | 293672 | 587181 | 0.88 | 77.23 | 661.0 | 1 | 2 | 10 | |
| Turbine Blade 2 (†) | 346103 | 791948 | 1.74 | 100.06 | 449.1 | 14 | 3 | 18 | |
| Dragon (***) | 435545 | 805376 | 1.71 | 107.58 | 427.1 | 12 | 28 | 249 | |
| Bimba (**) | 502694 | 1005172 | 1.49 | 126.99 | 676.1 | 16 | 12 | 220 | |
| Happy Buddha (***) | 503897 | 1004540 | 2.09 | 136.95 | 480.4 | 32 | 47 | 462 | |
| Chinese Dragon (**) | 655980 | 1311296 | 1.81 | 165.59 | 723.7 | 47 | 35 | 928 | |
| Turbine Blade (***) | 869555 | 1759357 | 2.73 | 227.74 | 454.8 | 42 | 66 | 1054 | |
| Amphora (**) | 1308237 | 2616596 | 5.99 | 332.56 | 439.2 | 0 | 1 | 10 | |
| Neptune (**) | 2003933 | 4007628 | 8.32 | 488.79 | 481.6 | X | X | X | |
| Asian Dragon (*) | 3609601 | 7218442 | 12.2 | 894.23 | 587.5 | X | X | X | |
| (*) http://www.graphics.stanford.edu/data/3Dscanrep/ (**) http://shapes.aimatshape.net/ |
|||||||||
The test was performed on My laptop: Asus pro31s. It has 2.4Ghz dual core processor and 2GB of RAM. For some of the models (bigger ones) I was able to mesh them but not to analyze their defectiveness on meshlab or CATIA.
Speed
Tests shows that Delaunay2_5D has a triangles rate production of 400-700 kTriangles/sec. It can mesh a million points cloud in about 4 secs.
Memory Usage
The algorithm is also designed to save memory, the RAM memory usage (in byte) can be estimate before launching the algorithm with the following formula: 240 x N. Where N is the number of points, each points requires about 240 byte of memory. A million points cloud requires only 240MB of RAM.
Quality of Triangles
The quality of triangles is comparable with Delaunay based methods.
Defectiveness
Non manifold vertices and holes
Delaunay2_5D can generated non manifold vertexes and odes not give warranty of a watertight surface reconstruction. If you care about them you have to use a post processing tool.
Non manifold edges
Delaunay2_5D can generate non manifold edges, if you found some, check your clouds has no duplicated points. If it hasn’t you just found a bug, please send me a report.
Duplicated triangles or triangles with different orientation
They can not be generated. if you found some, check your clouds has no duplicated points. If it hasn’t you just found a bug, please send me a report.
Popularity: 5% [?]
Delaunay2_5D: Usage
Filed under: Algorithms, Computational Geometry, Graphics
Contents
When can it be used
Delaunay2_5D is designed for densely sampled surfaces, both open and closed one. The surface must be not too much rough and possibly with higher sampling in high curvature feature.
…and when can not
Delaunay2_5D wont work on:
- Sliced data: when the distance among slices is much higher than the distance among point of the same slice.
- Rough surfaces
- Not orientable surfaces
- Sharp edges coming from cad models (scanned ones should be meshed).
How to use it
Input format
After struggling on hundreds of points cloud formats I decided to feed the algorithm with a simple binary file. The file is composed by an integer indicating the number of points and a list of doubles indicating the coordinates.
The number of point is the first data and it is an “int” type. Points are stored this way: X1,Y1,Z1,X2,Y2,Z2…….
These are the Matlab commands to generate such file:
fid=fopen(name,'wb');%open input file for Delaunay2_5D fwrite(fid, np, 'int');%first data=the numbers of points; fwrite(fid,p,'double');%points; fclose(fid);%close the file
You can download tools to use D2_5D on matlab here: Download Now
And this are the C++ ones:
pFile =fopen("D2_5DInput.dat", "wb");//open input file for Delaunay2_5D nwritten=fwrite(&N, sizeof(int), 1, pFile);//first line (the number of points) nwritten=fwrite(&p, sizeof(double), N*3, pFile);//Write the points coordinate fclose(pFile);//close the file
Launching the .exe
In Matlab you can use:
!Delaunay2_5D.exe i 2 p 1 f 0 a 90
where the letters after the executable path are the input parameters described in the next section.
In C++, given an array p of Nx3 elemnts representing the points coordinate:
system("Delaunay2_5D.exe i 2 p 1 f 0 a 90 ");
Input parameters
The basic call is:
A professional use of Delaunay2_5D requires some knowledge about its input parameters.
- ‘i’=Number of meshing iteration. Default=1. Too high meshing iteration can slow down the algorithm and sometimes generates bad triangles. On the other side, it helps to fill big holes, so rise up the number of operation only if you find undesired holes in the output.
- ‘f’= enables a nearest neighbour filter. A nearest neighbour graph is computed, the meandist among points calculated. Points with distance less than meandist/f will be deleted. f must be >1, a 0 value will turn off the filtering. Use this parameter only if you have duplicated points in the input or points too close too each other.
- ‘p’=The “strength” of the post-processor. Set to zero turn off post-processing operations. Set to >0 attempts to fill small holes in the output. Default value is 1.
- ‘file’= the input file name. Ex Delaunay2_5D.exe file Bunny.dat . If omitted the input filename must be later inserted as console input.
- ‘w’: output window,(only contributor version) set to 0 suppress output window
- ‘o’: output file:(only contributor version) set to 0 returns an stl file. Set to 1 returns a binary file (this mode is for the developper). Set to 2 returns both of them.
There are several others option but for now it is clearer not considering all of them. A complete documentation will be published shortly.
I the meantime, to run some tests, you can use settings suggested in the model section.
Popularity: 2% [?]
Translator
By N2H Follow Us
Video Posts
-
