|
CS 7491 Spring 2004 Project 2
Brandon Beck, Nguyen Truong, Howard Zhou
Source: cs7491.zip
Project Description
Project Objective: To experiment on the compression and decompression of
polygonal curves and using hausdorff distance to measure similarities between
curves.
Mini-paper
Report
Link to the source code:
Language :C++
System: Windows, Visual Studio.net 2003
Sources of inspiration:
Result
Uniform dense set point clouds
| Type |
Geometric Description |
Point Clouds |
Point Clouds on Bounding Geometry |
| Ball (113 points) |
CPointSet<CPoint3D>(avgDist,
BALL, CPoint3D(0,
0,
0),
3,
true)
ball001.txt |
 |
 |
| Ball with cavity (113 points generated, 93 left after
the cut) |
pointSet = CPointSet<CPoint3D>(avgDist,
BALL, CPoint3D(0,
0,
0),
3,
true)
- CPointSet<CPoint3D>(avgDist, BLOCKER, CPoint3D(1.5,
1,
0),
2);
ball002.txt |
 |
 |
| Sphere (113 points) |
CPointSet<CPoint3D>(avgDist,
SPHERE, CPoint3D(0,
0,
0),
3,
true)
sphere001.txt |
 |
 |
| Sphere with cut (113 points generated, 69 points left
after the cut) |
CPointSet<CPoint3D>(avgDist,
SPHERE, CPoint3D(0,
0,
0),
3,
true)
- CPointSet<CPoint3D>(avgDist,
BLOCKER, CPoint3D(1,
1,
0),
3);
sphere002.txt |
 |
 |
| Combination 1 (113 points generated, 53 points left
after the cut) |
pointSet = CPointSet<CPoint3D>(,
BALL, CPoint3D(0,
0,
0),
3,
true)
- CPointSet<CPoint3D>(avgDist, BLOCKER, CPoint3D(0,
0,
0),
1.5)
- CPointSet<CPoint3D>(avgDist, BLOCKER, CPoint3D(0,
2,
0),
1.5)
- CPointSet<CPoint3D>(avgDist, BLOCKER, CPoint3D(0,
-2,
0),
1.5)
- CPointSet<CPoint3D>(avgDist, BLOCKER, CPoint3D(0,
4,
0),
3.5)
- CPointSet<CPoint3D>(avgDist, BLOCKER, CPoint3D(0,
-4,
0),
3.5);
comb001.txt |
 |
 |
| Combination 2 (134 points) |
CPointSet<CPoint3D>(avgDist,
SPHERE, CPoint3D(-3,
-2,
0),
1.5,
true)
+ CPointSet<CPoint3D>(avgDist, BALL, CPoint3D(2,
1,
0),
1.5,
true)
+ CPointSet<CPoint3D>(avgDist, BALL, CPoint3D(1,
0,
0),
2,
true)
- CPointSet<CPoint3D>(avgDist, BLOCKER, CPoint3D(1,
2,
0),
2)
- CPointSet<CPoint3D>(avgDist, BLOCKER, CPoint3D(-2,
-2,
1),
1.5);
comb002.txt |
 |
 |
| Combination 3 (196 points) |
pointSet = CPointSet<CPoint3D>(avgDist,
SPHERE, CPoint3D(-3,
-2,
0),
1,
true)
+ CPointSet<CPoint3D>(avgDist, BALL, CPoint3D(2,
1.5,
0),
1)
+ CPointSet<CPoint3D>(avgDist, BALL, CPoint3D(0,
-0.8,
0),
1)
- CPointSet<CPoint3D>(avgDist, BLOCKER, CPoint3D(-2,
-2,
1),
1);
comb003.txt |
 |
 |
Shell Traversal
| |
Shell and Genus |
|
|
pointSet = CPointSet<CPoint3D>(,
BALL, CPoint3D(0,
0,
0),
3,
true)
- CPointSet<CPoint3D>(avgDist, BLOCKER, CPoint3D(0,
0,
0),
1.5)
- CPointSet<CPoint3D>(avgDist, BLOCKER, CPoint3D(0,
2,
0),
1.5)
- CPointSet<CPoint3D>(avgDist, BLOCKER, CPoint3D(0,
-2,
0),
1.5)
- CPointSet<CPoint3D>(avgDist, BLOCKER, CPoint3D(0,
4,
0),
3.5)
- CPointSet<CPoint3D>(avgDist, BLOCKER, CPoint3D(0,
-4,
0),
3.5);
comb001.txt
# Shells: 1
# Genus
shell[0]: 1 |
|
|
pointSet = CPointSet<CPoint3D>(avgDist,
SPHERE, CPoint3D(-3,
-2,
0),
1,
true)
+ CPointSet<CPoint3D>(avgDist, BALL, CPoint3D(2,
1.5,
0),
1)
+ CPointSet<CPoint3D>(avgDist, BALL, CPoint3D(0,
-0.8,
0),
1)
- CPointSet<CPoint3D>(avgDist, BLOCKER, CPoint3D(-2,
-2,
1),
1);
comb003.txt
# Shells: 3
# Genus:
shell[0]: 0
shell[1]: 0
shell[2]: 0
|
Performance comparison: Brute Force vs. Quantization
Shape : CPointSet<CPoint3D>(nPoints,
SPHERE, CPoint3D(0,
0,
0),
3,
true)
| |
|
Brute Force Method |
Quantization Method |
| points |
triangles |
time (sec) |
time (sec) |
# of cells |
| 50 |
192 |
1.875 |
1.797 |
<2, 2, 2> |
| 100 |
392 |
7.234 |
3.202 |
<3, 3, 3> |
| 150 |
592 |
19.967 |
7.093 |
<3, 3, 3> |
| 200 |
792 |
42.966 |
11.812 |
<3, 3, 3> |
| 250 |
992 |
62.965 |
10.687 |
<4, 4, 4> |
| 300 |
1192 |
111.04 |
15.077 |
<4, 4, 4> |
| 350 |
1392 |
154.82 |
19.233 |
<4, 4, 4> |
| 400 |
1592 |
262.688 |
17.453 |
<5, 5, 5> |
| 450 |
1792 |
314.451 |
20.874 |
<5, 5, 5> |
| 500 |
1992 |
399.742 |
26.936 |
<5, 5, 5> |
| |
|
not n^4, but close to n^2, maybe we did
too much optimization? related to the nature of sphere? |
super linear, close to linear |
|
Performance of "makeManifold" Shape:
CPointSet<CPoint3D>(avgDist, SPHERE, CPoint3D(0,
0,
0),
3,
true)
- CPointSet<CPoint3D>(avgDist, BLOCKER, CPoint3D(1.5,
1,
0),
3);
| # original vertices |
# total vertices |
# triangles |
time (sec) |
| 29 |
47 |
90 |
0.000 |
| 175 |
323 |
642 |
0.000 |
| 323 |
615 |
1226 |
0.015 |
| 460 |
881 |
1758 |
0.031 |
| 610 |
1176 |
2348 |
0.031 |
| 748 |
1446 |
2888 |
0.062 |
|
This is an image of the sphere with cut in this performance test. All the duplicated
vertices with the original vertices overlapped are colored blue and all the
other vertices which are not duplicated are colored white. The result is what we
have expected; all the vertices that are not on the "crossing edges" are duplicated,
which effectively transformed this half sphere shell into a shape that is
topologically equivalent to a ball (imaging this shell as a deflated bubble)
The performance of our "makeManifold" algorithm is linear to the
number of corners (triangles) and vertices since it goes through the corner
table exactly once and creates new vertices as it sees fit. Our test result
listed above confirms this analysis. Notice that the discrepancies are
introduced by the lack of precision of our clock.
|
|
