aboutsummaryrefslogtreecommitdiff
path: root/src/mtx_qhull
diff options
context:
space:
mode:
authorFranz Zotter <fzotter@users.sourceforge.net>2012-08-29 06:58:22 +0000
committerFranz Zotter <fzotter@users.sourceforge.net>2012-08-29 06:58:22 +0000
commit291c783983b64f4b0ae4f6f67a016233193efa8c (patch)
treef9a6f7876170e4ef5f2afbf5a65e6706c067a965 /src/mtx_qhull
parent72b3745f0d901e4ea12837554801f23f8afc20f8 (diff)
cleaned up code for mtx_qhull
svn path=/trunk/externals/iem/iemmatrix/; revision=16183
Diffstat (limited to 'src/mtx_qhull')
-rw-r--r--src/mtx_qhull/entry.h14
-rw-r--r--src/mtx_qhull/list.c54
-rw-r--r--src/mtx_qhull/list.h14
-rw-r--r--src/mtx_qhull/test_write_conv_hull_obj.pd176
-rw-r--r--src/mtx_qhull/vectors.c91
-rw-r--r--src/mtx_qhull/vectors.h60
-rw-r--r--src/mtx_qhull/zhull.c95
-rw-r--r--src/mtx_qhull/zhull.h22
8 files changed, 365 insertions, 161 deletions
diff --git a/src/mtx_qhull/entry.h b/src/mtx_qhull/entry.h
index bc22f35..d85da9a 100644
--- a/src/mtx_qhull/entry.h
+++ b/src/mtx_qhull/entry.h
@@ -4,6 +4,20 @@
#include <sys/types.h>
#include <stdio.h>
+
+/*
+ * variable entry types for
+ * list operations in zhull
+ *
+ * Copyright (c) 2012, IOhannes zmoelnig,
+ * with friendly help from
+ * IEM, Graz, Austria
+ *
+ *
+ */
+
+
+
typedef size_t index_t;
typedef union {
diff --git a/src/mtx_qhull/list.c b/src/mtx_qhull/list.c
index 6f3b416..cf2b797 100644
--- a/src/mtx_qhull/list.c
+++ b/src/mtx_qhull/list.c
@@ -2,6 +2,20 @@
#include <stdlib.h>
#include <stdio.h>
+/*
+ * list operations for zhull
+ *
+ * Copyright (c) 2012, Franz Zotter,
+ * with friendly help from
+ * IOhannes zmoelnig
+ * for variable entry types
+ * in entry.h
+ * IEM, Graz, Austria
+ *
+ *
+ */
+
+
// memory things:
list_t emptyList(void) {
list_t generated_list;
@@ -16,7 +30,6 @@ list_t allocateList(const size_t length) {
generated_list.entries= (entry_t*) malloc(length*sizeof(entry_t));
if (generated_list.entries!=0) {
generated_list.length=length;
- // printf("got list %li\n",generated_list.entries);
}
}
return generated_list;
@@ -26,7 +39,7 @@ void reallocateList(list_t *list,
const size_t length) {
entry_t *old_entries = list->entries;
if (length>0) {
- if (list->length==0)
+ if (getLength(*list)==0)
*list = allocateList(length);
else {
if (list->length != length)
@@ -39,18 +52,11 @@ void reallocateList(list_t *list,
}
else
freeList(list);
- /* if ((list->entries!=old_entries)&&(old_entries!=0)) {
- if (list->entries!=0)
- printf("moved %li by realloc to %li\n",old_entries,list->entries);
- else
- printf("freed %li by realloc\n", old_entries);
- }*/
}
void freeList(list_t *list) {
if (list->entries!=0) {
- // printf("deleting list %li\n",list->entries);
free(list->entries);
}
list->entries=0;
@@ -72,24 +78,27 @@ entry_t getEntry(const list_t list, const index_t index) {
}
}
-void setEntry(const list_t list, const index_t index, const entry_t entry) {
+void setEntry(const list_t list, const index_t index,
+ const entry_t entry) {
if ((index>=0)&&(index<getLength(list)))
list.entries[index]=entry;
}
-list_t initList(const entry_t *entries, const size_t length) {
+list_t initList(const entry_t *entries,
+ const size_t length) {
index_t i;
list_t l = allocateList(length);
- if (l.entries!=0)
+ if (getLength(l)!=0)
for (i=0; i<(index_t)length; i++)
setEntry(l,i,entries[i]);
return l;
}
+
list_t initListIndex(const index_t *entries, const size_t length) {
index_t i;
list_t l = allocateList(length);
- if (l.entries!=0)
+ if (getLength(l)!=0)
for (i=0; i<(index_t)length; i++)
setEntry(l,i,entry_makeIndex(entries[i]));
return l;
@@ -111,7 +120,7 @@ list_t initListFromTo(const index_t start, const index_t stop) {
incr=-1;
}
list_t l = allocateList(length);
- if (l.entries!=0) {
+ if (getLength(l)!=0) {
for (i=0,c=start; i<length; i++, c+=incr) {
entry_setIndex(&e, c);
setEntry(l,i,e);
@@ -123,7 +132,7 @@ list_t initListFromTo(const index_t start, const index_t stop) {
list_t initConstantList(const entry_t c, const size_t length){
index_t i;
list_t l = allocateList(length);
- if (l.entries!=0)
+ if (getLength(l)!=0)
for (i=0; i<length; i++)
setEntry(l,i,c);
return l;
@@ -143,7 +152,7 @@ list_t mergeLists(const list_t list1, const list_t list2) {
list_t list_out;
index_t i,j;
list_out = allocateList(getLength(list1)+ getLength(list2));
- if (list_out.entries!=0) {
+ if (getLength(list_out)>=getLength(list1)) {
for (i=0; i<getLength(list1); i++)
setEntry(list_out,i,getEntry(list1,i));
for (j=0; i<getLength(list_out); i++, j++)
@@ -184,9 +193,9 @@ list_t getSubListFromTo(const list_t list, const index_t start,
}
void appendToList(list_t *list, const entry_t entry) {
- const index_t i=(index_t)getLength(*list);
+ const size_t i=getLength(*list);
reallocateList(list,getLength(*list)+1);
- if (getLength(*list)>(size_t)i) {
+ if (getLength(*list)>i) {
setEntry(*list,i,entry);
}
}
@@ -213,13 +222,10 @@ void removeValueFromList(list_t *list, const entry_t entry) {
void appendListToList(list_t *list1, const list_t list2) {
index_t i,j;
- size_t siz_old = getLength(*list1);
- siz_old=list1->length;
+ const size_t siz_old = getLength(*list1);
reallocateList(list1, getLength(*list1) + getLength(list2));
- if (getLength(*list1)>siz_old) {
- for (i=siz_old, j=0; i<list1->length; i++, j++)
- setEntry(*list1,i,getEntry(list2,j));
- }
+ for (i=siz_old, j=0; i<getLength(*list1); i++, j++)
+ setEntry(*list1,i,getEntry(list2,j));
}
void removeEntryListFromList(list_t *list, const list_t indices) {
diff --git a/src/mtx_qhull/list.h b/src/mtx_qhull/list.h
index 6b05531..31453ad 100644
--- a/src/mtx_qhull/list.h
+++ b/src/mtx_qhull/list.h
@@ -7,6 +7,20 @@
#include "entry.h"
+/*
+ * list operations for zhull
+ *
+ * Copyright (c) 2012, Franz Zotter,
+ * with friendly help from
+ * IOhannes zmoelnig
+ * for variable entry types
+ * in entry.h
+ * IEM, Graz, Austria
+ *
+ *
+ */
+
+
typedef struct list_ {
entry_t *entries;
size_t length;
diff --git a/src/mtx_qhull/test_write_conv_hull_obj.pd b/src/mtx_qhull/test_write_conv_hull_obj.pd
index 49d5af3..1b6aa39 100644
--- a/src/mtx_qhull/test_write_conv_hull_obj.pd
+++ b/src/mtx_qhull/test_write_conv_hull_obj.pd
@@ -83,7 +83,7 @@
#X obj -9 358 color 0.9 0.9 0.9;
#X obj 335 426 mtx_* 1.5;
#X obj -10 338 ortho;
-#X obj 137 309 tgl 15 0 empty empty empty 17 7 0 10 -262144 -1 -1 1
+#X obj 137 309 tgl 15 0 empty empty empty 17 7 0 10 -262144 -1 -1 0
1;
#X obj 112 358 f;
#X obj 167 358 % 360;
@@ -113,12 +113,10 @@
1;
#X obj 71 180 t b f;
#X msg 190 85 9 180;
-#X msg 48 70 1.5 6;
#X msg 97 66 2 14;
#X msg 46 88 2.5 12;
#X floatatom 323 249 5 0 0 0 - - -;
#X obj 317 269 t b f;
-#X obj 237 319 mtx_qhull 500;
#X msg -123 202 read Rls.mtx \, bang;
#X msg 100 85 2.5 20;
#X obj 107 239 mtx_size;
@@ -183,12 +181,12 @@
#X obj -103 229 t a a;
#X obj -103 250 mtx_size;
#X obj -101 293 mtx_*;
-#X obj -32 342 tgl 15 0 empty empty empty 17 7 0 10 -262144 -1 -1 1
+#X obj -32 342 tgl 15 0 empty empty empty 17 7 0 10 -262144 -1 -1 0
1;
#X msg 251 5 matrix 4 3 0 0 0 1 0 0 2 0 0 0 1 0;
-#X obj -99 8 metro 100;
-#X obj -94 -12 tgl 15 0 empty empty empty 17 7 0 10 -262144 -1 -1 1
-1;
+#X obj -115 -11 tgl 15 0 empty empty empty 17 7 0 10 -262144 -1 -1
+0 1;
+#N canvas 547 27 715 363 combine_objects 1;
#X obj -127 48 mtx;
#X obj -124 69 t a a;
#X obj -74 31 mtx_size;
@@ -198,13 +196,81 @@
#X obj -86 175 mtx_+;
#X obj -41 175 mtx_* 0.94;
#X obj -89 152 mtx_* 0.06;
-#X floatatom -27 -10 5 0 0 0 - - -;
#X obj -67 92 mtx_* -2;
-#X obj -55 110 mtx_+ 1;
-#X obj -40 130 mtx_* 0.3;
-#X floatatom 19 36 5 0 0 0 - - -;
-#X obj 23 16 hsl 128 15 0 3 0 0 empty empty empty -2 -8 0 10 -262144
+#X obj -37 131 mtx_* 0.3;
+#X obj -99 8 metro 38;
+#X obj 264 5 inlet;
+#X obj -100 -13 inlet;
+#X obj -81 256 outlet;
+#X obj 204 2 inlet;
+#X obj 87 106 bng 15 250 50 0 empty empty empty 17 7 0 10 -262144 -1
+-1;
+#X obj -52 112 mtx_+ 1;
+#X obj 73 225 mtx_concat;
+#X obj 56 63;
+#X obj 150 205 mtx_* 1;
+#X obj 78 204 mtx;
+#X obj 270 127 max 0.1;
+#X obj 238 46 t b f;
+#X obj 271 82 f;
+#X obj 192 64 delay 50;
+#X obj 243 106 t b b f;
+#X msg 434 97 4 40;
+#X obj 166 178 mtx;
+#X msg 473 99 9 180;
+#X msg 326 138 read designsN/N\$1_\$2.mtx;
+#X msg 374 75 1 4;
+#X msg 373 104 1.5 6;
+#X obj 380 51 loadbang;
+#X connect 0 0 1 0;
+#X connect 1 0 5 0;
+#X connect 1 1 2 0;
+#X connect 2 0 3 0;
+#X connect 2 1 3 1;
+#X connect 3 0 4 0;
+#X connect 4 0 9 0;
+#X connect 5 0 8 0;
+#X connect 6 0 7 0;
+#X connect 6 0 14 0;
+#X connect 7 0 6 1;
+#X connect 8 0 6 0;
+#X connect 9 0 17 0;
+#X connect 10 0 5 1;
+#X connect 11 0 0 0;
+#X connect 12 0 23 0;
+#X connect 13 0 11 0;
+#X connect 15 0 0 1;
+#X connect 15 0 7 0;
+#X connect 15 0 21 1;
+#X connect 16 0 0 0;
+#X connect 17 0 10 0;
+#X connect 18 0 14 0;
+#X connect 20 0 18 1;
+#X connect 21 0 18 0;
+#X connect 22 0 20 1;
+#X connect 23 0 25 0;
+#X connect 23 1 24 1;
+#X connect 24 0 26 0;
+#X connect 25 0 24 0;
+#X connect 26 0 21 0;
+#X connect 26 1 28 0;
+#X connect 26 2 22 0;
+#X connect 27 0 30 0;
+#X connect 28 0 20 0;
+#X connect 29 0 30 0;
+#X connect 30 0 28 0;
+#X connect 31 0 30 0;
+#X connect 32 0 30 0;
+#X connect 33 0 31 0;
+#X restore -108 23 pd combine_objects;
+#X obj -95 -12 hsl 128 15 0 3 0 0 empty empty empty -2 -8 0 10 -262144
-1 -1 0 1;
+#X msg 48 69 1.5 6;
+#X floatatom 58 14 5 0 0 0 - - -;
+#X msg 20 46 0.573;
+#X obj 236 316 mtx_qhull;
+#X floatatom 302 333 5 0 0 0 - - -;
+#X obj 441 382 mtx_print;
#X connect 1 0 2 0;
#X connect 2 0 1 0;
#X connect 3 0 4 0;
@@ -248,10 +314,9 @@
#X connect 35 0 37 0;
#X connect 36 0 37 0;
#X connect 37 0 38 0;
-#X connect 38 0 52 0;
-#X connect 38 0 73 1;
-#X connect 38 0 80 0;
-#X connect 39 0 48 0;
+#X connect 38 0 50 0;
+#X connect 38 0 70 1;
+#X connect 39 0 75 0;
#X connect 39 1 32 0;
#X connect 40 0 41 0;
#X connect 41 0 38 0;
@@ -259,51 +324,38 @@
#X connect 42 0 37 0;
#X connect 43 0 37 0;
#X connect 44 0 37 0;
-#X connect 45 0 37 0;
-#X connect 46 0 47 0;
+#X connect 45 0 46 0;
+#X connect 46 0 38 0;
+#X connect 46 1 75 0;
#X connect 47 0 38 0;
-#X connect 47 1 48 0;
-#X connect 48 0 27 0;
-#X connect 49 0 38 0;
-#X connect 50 0 37 0;
-#X connect 51 0 53 0;
-#X connect 52 0 10 0;
-#X connect 52 1 33 0;
-#X connect 52 2 51 0;
-#X connect 53 0 54 0;
-#X connect 54 0 55 0;
-#X connect 57 0 38 0;
-#X connect 59 0 62 0;
-#X connect 60 0 38 0;
-#X connect 61 0 60 1;
-#X connect 62 0 60 0;
-#X connect 62 1 61 0;
-#X connect 63 0 38 0;
-#X connect 64 0 59 0;
-#X connect 65 0 68 0;
-#X connect 66 0 67 0;
-#X connect 66 1 68 1;
-#X connect 67 0 65 0;
-#X connect 68 0 52 0;
-#X connect 69 0 14 0;
-#X connect 70 0 38 0;
+#X connect 48 0 37 0;
+#X connect 49 0 51 0;
+#X connect 50 0 10 0;
+#X connect 50 1 33 0;
+#X connect 50 2 49 0;
+#X connect 51 0 52 0;
+#X connect 52 0 53 0;
+#X connect 55 0 38 0;
+#X connect 57 0 60 0;
+#X connect 58 0 38 0;
+#X connect 59 0 58 1;
+#X connect 60 0 58 0;
+#X connect 60 1 59 0;
+#X connect 61 0 38 0;
+#X connect 62 0 57 0;
+#X connect 63 0 66 0;
+#X connect 64 0 65 0;
+#X connect 64 1 66 1;
+#X connect 65 0 63 0;
+#X connect 66 0 50 0;
+#X connect 67 0 14 0;
+#X connect 68 0 38 0;
+#X connect 69 0 70 0;
+#X connect 70 0 50 0;
+#X connect 71 0 70 2;
#X connect 71 0 73 0;
-#X connect 72 0 71 0;
-#X connect 73 0 74 0;
-#X connect 74 0 78 0;
-#X connect 74 1 75 0;
-#X connect 75 0 76 0;
-#X connect 75 1 76 1;
-#X connect 76 0 77 0;
-#X connect 77 0 83 0;
-#X connect 78 0 81 0;
-#X connect 79 0 52 0;
-#X connect 79 0 80 0;
-#X connect 80 0 79 1;
-#X connect 81 0 79 0;
-#X connect 82 0 71 1;
-#X connect 83 0 84 0;
-#X connect 84 0 85 0;
-#X connect 85 0 78 1;
-#X connect 86 0 85 1;
-#X connect 87 0 86 0;
+#X connect 72 0 37 0;
+#X connect 74 0 70 2;
+#X connect 75 0 27 0;
+#X connect 75 0 77 0;
+#X connect 75 1 76 0;
diff --git a/src/mtx_qhull/vectors.c b/src/mtx_qhull/vectors.c
index 655ed94..5e520a3 100644
--- a/src/mtx_qhull/vectors.c
+++ b/src/mtx_qhull/vectors.c
@@ -1,12 +1,21 @@
#include "vectors.h"
+/*
+ * vector operations for zhull
+ *
+ * Copyright (c) 2012, Franz Zotter
+ * IEM, Graz, Austria
+ *
+ *
+ */
+
-vector_t initVector (float x, float y, float z) {
+vector_t initVector (const float x, const float y, const float z) {
vector_t vec={x, y, z};
return vec;
}
-float lengthVector(vector_t v) {
+float lengthVector(const vector_t v) {
return sqrtf(v.c[0]*v.c[0]+v.c[1]*v.c[1]+v.c[2]*v.c[2]);
}
vector_t normalizeVector(vector_t v) {
@@ -17,33 +26,36 @@ vector_t normalizeVector(vector_t v) {
return v;
}
-plane_t initPlane (vector_t normal, vector_t point) {
+plane_t initPlane (vector_t normal, const vector_t point) {
plane_t plane;
plane.point = point;
plane.normal = normalizeVector(normal);
return plane;
}
-line_t initLine (vector_t direction, vector_t point) {
+line_t initLine (vector_t direction, const vector_t point) {
line_t line;
line.point = point;
line.direction = normalizeVector(direction);
return line;
}
+points_t allocatePoints (const size_t num_points) {
+ points_t points;
+ points.v = (vector_t *) malloc(sizeof(vector_t)*num_points);
+ if (points.v!=0)
+ points.num_points = num_points;
+ return points;
+}
+
points_t initPoints (const float *x,
const float *y, const float *z,
- size_t num_points) {
- points_t points;
+ const size_t num_points) {
+ points_t points = allocatePoints(num_points);
size_t i;
- points.v = (vector_t*) malloc (sizeof(vector_t)*num_points);
- if (points.v!=0) {
-// printf("created %li\n",points.v);
- points.num_points = num_points;
- for (i=0; i<num_points; i++) {
- points.v[i] = initVector(x[i],y[i],z[i]);
- }
+ for (i=0; i<getNumPoints(points); i++) {
+ points.v[i] = initVector(x[i],y[i],z[i]);
}
return points;
}
@@ -58,7 +70,36 @@ void freePoints (points_t *points) {
}
}
-vector_t crossProduct (vector_t v1, vector_t v2) {
+void reallocatePoints (points_t *points, const size_t num_points) {
+ if ((num_points>0)&&(points!=0)) {
+ if (getNumPoints(*points)==0)
+ *points=allocatePoints(num_points);
+ else {
+ points->v = (vector_t *) realloc(points->v,sizeof(vector_t)*num_points);
+ if (points->v!=0)
+ points->num_points=num_points;
+ else
+ points->num_points=0;
+ }
+ if (points->v!=0)
+ points->num_points = num_points;
+ }
+ else
+ freePoints(points);
+}
+
+void appendPoints(points_t *points,
+ const float *x, const float *y,
+ const float *z, const size_t num_points) {
+ const size_t n=getNumPoints(*points);
+ size_t i,j;
+ reallocatePoints(points,getNumPoints(*points)+num_points);
+ for (i=n,j=0; i<getNumPoints(*points); i++, j++) {
+ points->v[i] = initVector(x[j],y[j],z[j]);
+ }
+}
+
+vector_t crossProduct (const vector_t v1, const vector_t v2) {
vector_t cp;
cp.c[0]= v1.c[1]*v2.c[2]-v1.c[2]*v2.c[1];
cp.c[1]=-v1.c[0]*v2.c[2]+v1.c[2]*v2.c[0];
@@ -66,7 +107,7 @@ vector_t crossProduct (vector_t v1, vector_t v2) {
return cp;
}
-float innerProduct (vector_t v1, vector_t v2) {
+float innerProduct (const vector_t v1, const vector_t v2) {
return v1.c[0]*v2.c[0] + v1.c[1]*v2.c[1] + v1.c[2]*v2.c[2];
}
@@ -76,24 +117,24 @@ float distancePointPoint(const vector_t a,
return lengthVector(d);
}
-float distancePointPlane (vector_t point, plane_t plane) {
+float distancePointPlane (const vector_t point, const plane_t plane) {
return innerProduct(point, plane.normal) -
innerProduct(plane.point, plane.normal);
}
-float distancePointLine (vector_t point, line_t line) {
+float distancePointLine (const vector_t point, const line_t line) {
return lengthVector(crossProduct(line.direction,
subtractVectors(point,line.point)));
}
-float distancePointLineOnPlane (vector_t point,
- line_t line, plane_t plane) {
+float distancePointLineOnPlane (vector_t const point,
+ const line_t line, const plane_t plane) {
vector_t normal_in_plane = normalizeVector(crossProduct(
line.direction, plane.normal));
return innerProduct(subtractVectors(point,line.point),normal_in_plane);
}
-vector_t addVectors(vector_t v1, vector_t v2) {
+vector_t addVectors(const vector_t v1, const vector_t v2) {
vector_t v3;
v3.c[0]=v1.c[0]+v2.c[0];
v3.c[1]=v1.c[1]+v2.c[1];
@@ -101,7 +142,7 @@ vector_t addVectors(vector_t v1, vector_t v2) {
return v3;
}
-vector_t subtractVectors(vector_t v1, vector_t v2) {
+vector_t subtractVectors(const vector_t v1, const vector_t v2) {
vector_t v3;
v3.c[0]=v1.c[0]-v2.c[0];
v3.c[1]=v1.c[1]-v2.c[1];
@@ -109,7 +150,7 @@ vector_t subtractVectors(vector_t v1, vector_t v2) {
return v3;
}
-vector_t scaleVector(vector_t v1, float f) {
+vector_t scaleVector(vector_t v1, const float f) {
vector_t v2;
v2.c[0]=f*v1.c[0];
v2.c[1]=f*v1.c[1];
@@ -227,18 +268,18 @@ line_t lineFromListedPoints(const points_t points, const list_t list) {
return l;
}
-void printVector(vector_t v) {
+void printVector(const vector_t v) {
printf("[%5.2f,%5.2f,%5.2f], ", v.c[0],v.c[1],v.c[2]);
}
-void printPlane(plane_t p) {
+void printPlane(const plane_t p) {
printf("n=");
printVector(p.normal);
printf(", p=");
printVector(p.point);
}
-void printLine(line_t l) {
+void printLine(const line_t l) {
printf("d=");
printVector(l.direction);
printf(", p=");
diff --git a/src/mtx_qhull/vectors.h b/src/mtx_qhull/vectors.h
index 06a302a..3267df9 100644
--- a/src/mtx_qhull/vectors.h
+++ b/src/mtx_qhull/vectors.h
@@ -4,6 +4,16 @@
#include <math.h>
#include <stdlib.h>
#include <stdio.h>
+
+/*
+ * vector operations for zhull
+ *
+ * Copyright (c) 2012, Franz Zotter
+ * IEM, Graz, Austria
+ *
+ *
+ */
+
typedef struct vec_ {
float c[3];
} vector_t;
@@ -24,43 +34,43 @@ typedef struct line_ {
} line_t;
-vector_t initVector (float x, float y, float z);
-float lengthVector(vector_t v);
-vector_t normalizeVector(vector_t v);
+vector_t initVector (const float x, const float y, const float z);
+float lengthVector(const vector_t v);
+vector_t normalizeVector(const vector_t v);
-plane_t initPlane (vector_t normal, vector_t point);
-line_t initLine (vector_t direction, vector_t point);
+plane_t initPlane (vector_t normal, const vector_t point);
+line_t initLine (vector_t direction, const vector_t point);
points_t initPoints (const float *x,
const float *y, const float *z,
- size_t num_points);
+ const size_t num_points);
void freePoints (points_t *points);
size_t getNumPoints(const points_t points);
vector_t getPoint(const points_t points, const index_t index);
-vector_t crossProduct (vector_t v1, vector_t v2);
-float innerProduct (vector_t v1, vector_t v2);
+vector_t crossProduct (const vector_t v1, const vector_t v2);
+float innerProduct (const vector_t v1, const vector_t v2);
float distancePointPoint(const vector_t a, const vector_t b);
-float distancePointPlane (vector_t point, plane_t plane);
-float distancePointLine (vector_t point, line_t line);
-float distancePointLineOnPlane (vector_t point,
- line_t line, plane_t plane);
-vector_t addVectors(vector_t v1, vector_t v2);
-vector_t subtractVectors(vector_t v1, vector_t v2);
-vector_t scaleVector(vector_t v1, float f);
+float distancePointPlane (const vector_t point, const plane_t plane);
+float distancePointLine (const vector_t point, const line_t line);
+float distancePointLineOnPlane (const vector_t point,
+ const line_t line, const plane_t plane);
+vector_t addVectors(const vector_t v1, const vector_t v2);
+vector_t subtractVectors(const vector_t v1, const vector_t v2);
+vector_t scaleVector(vector_t v1, const float f);
/*vector_t averagePoints(points_t points);
vector_t normalOfPoints(points_t points);
plane_t planeFromPoints(points_t points);*/
-plane_t planeFromThreePoints (vector_t a, vector_t b, vector_t c);
-line_t lineFromTwoPoints (vector_t a, vector_t b);
+plane_t planeFromThreePoints (const vector_t a, const vector_t b, const vector_t c);
+line_t lineFromTwoPoints (const vector_t a, const vector_t b);
-vector_t averageListedPoints(points_t points, list_t list);
-vector_t normalOfListedPoints(points_t points, list_t list);
-vector_t directionOfListedPoints(points_t points, list_t list);
-plane_t planeFromListedPoints(points_t points, list_t list);
-line_t lineFromListedPoints(points_t points, list_t list);
+vector_t averageListedPoints(const points_t points, const list_t list);
+vector_t normalOfListedPoints(const points_t points, const list_t list);
+vector_t directionOfListedPoints(const points_t points, const list_t list);
+plane_t planeFromListedPoints(const points_t points, const list_t list);
+line_t lineFromListedPoints(const points_t points, const list_t list);
-void printPlane(plane_t p);
-void printLine(line_t l);
-void printVector(vector_t v);
+void printPlane(const plane_t p);
+void printLine(const line_t l);
+void printVector(const vector_t v);
#endif /* QHULL_VECTOR_H */
diff --git a/src/mtx_qhull/zhull.c b/src/mtx_qhull/zhull.c
index 6454289..0c4409e 100644
--- a/src/mtx_qhull/zhull.c
+++ b/src/mtx_qhull/zhull.c
@@ -1,7 +1,30 @@
#include "zhull.h"
+/*
+ * zhull
+ *
+ * own qhull algorithm implementation
+ *
+ * Copyright (c) 2012, Franz Zotter
+ * with friendly help from
+ * IOhannes zmoelnig
+ * IEM, Graz, Austria
+ *
+ * own Implementation after the QHULL algorithm
+ * that is documented in
+ * Barber, C.B., Dobkin, D.P., and Huhdanpaa, H.T.,
+ * "The Quickhull algorithm for convex hulls," ACM Trans.
+ * on Mathematical Software, 22(4):469-483, Dec 1996,
+ * http://www.qhull.org
+ *
+ */
+
+
+
+
+
/* facets, memory things */
-void freeFacet(facet_t *facet) {
+static void freeFacet(facet_t *facet) {
/* printf("deleting facet %li\n",facet);
printList(facet->corners);
printList(facet->outsideset);
@@ -13,7 +36,7 @@ void freeFacet(facet_t *facet) {
freeList(&(facet->neighbors));
}
-list_t appendNewFacets(zhull_t * const zh, const size_t num_facets) {
+static list_t appendNewFacets(zhull_t * const zh, const size_t num_facets) {
facet_t *new_facet;
index_t i;
entry_t e0=entry_makeIndex(0);
@@ -50,7 +73,7 @@ list_t appendNewFacets(zhull_t * const zh, const size_t num_facets) {
}
*/
-facet_t *getFacetByIndex(const list_t facets,
+static facet_t *getFacetByIndex(const list_t facets,
const index_t index) {
entry_t e=getEntry(facets,index);
return ((facet_t*)entry_getPointer(&e));
@@ -66,11 +89,11 @@ index_t getTriangleCorner(const zhull_t * const zh,
return 0;
}
-facet_t *getFacetByPointer(const entry_t e) {
+static facet_t *getFacetByPointer(const entry_t e) {
return (facet_t*) entry_getPointer(&e);
}
-void getHorizonEdgeByIndex(index_t *corners,
+static void getHorizonEdgeByIndex(index_t *corners,
const list_t horizon_fcts, const list_t horizon_fcts_edges,
const list_t other_horizon_edges, const index_t index) {
index_t i=(index+getLength(horizon_fcts_edges))
@@ -98,18 +121,17 @@ void getHorizonEdgeByIndex(index_t *corners,
}
-void removeFacetByPointer(zhull_t * const zh,
+static void removeFacetByPointer(zhull_t * const zh,
facet_t * const pointer) {
removeValueFromList(&(zh->facets), entry_makePointer(pointer));
removeValueFromList(&(zh->facets_with_outsidepoints),
entry_makePointer(pointer));
removeValueFromList(&(zh->facets_with_insidepoints),
entry_makePointer(pointer));
-#warning FIXXXME
- freeFacet((facet_t*)pointer);
+ freeFacet(pointer);
}
-void removeFacetByPointerList(zhull_t * const zh,
+static void removeFacetByPointerList(zhull_t * const zh,
const list_t pointers) {
index_t i;
for (i=0; i<getLength(pointers); i++) {
@@ -118,13 +140,13 @@ void removeFacetByPointerList(zhull_t * const zh,
}
}
-void removeFacetByIndex(zhull_t * const zh,
+static void removeFacetByIndex(zhull_t * const zh,
const index_t index) {
removeFacetByPointer(zh,
getFacetByIndex(zh->facets, index));
}
-void removeFacetByIndexList(zhull_t * const zh,
+static void removeFacetByIndexList(zhull_t * const zh,
const list_t indices) {
facet_t *f;
index_t i;
@@ -135,7 +157,7 @@ void removeFacetByIndexList(zhull_t * const zh,
}
}
-void freeFacets(zhull_t * const zh) {
+static void freeFacets(zhull_t * const zh) {
int i;
facet_t *f;
if (getLength(zh->facets)>0) {
@@ -166,7 +188,7 @@ void freeZhull(zhull_t *zh) {
-line_t getLine(const zhull_t * const zh,
+static line_t getLine(const zhull_t * const zh,
const facet_t * const f,
const index_t corner) {
vector_t a, b;
@@ -189,7 +211,7 @@ zhull_t zhullInitPoints(const float *x, const float *y,
-void dividePointsBetweenNewFacets (
+static void dividePointsBetweenNewFacets (
zhull_t * const zh, const list_t assoc,
const list_t new_facets) {
index_t i,j;
@@ -236,7 +258,7 @@ void dividePointsBetweenNewFacets (
freeList(&point_inside_facet_list);
}
-void zhullInitialFacets(zhull_t *zh) {
+static void zhullInitialFacets(zhull_t *zh) {
list_t assoc = emptyList();
list_t new_facets = emptyList();
index_t i;
@@ -269,6 +291,7 @@ void zhullInitialFacets(zhull_t *zh) {
} while (idx[2]<getNumPoints(zh->pts));
if (idx[2]<getNumPoints(zh->pts)) {
getFacetByIndex(new_facets,0)->corners = list;
+ appendListToList(&(zh->used_pts),list);
list=initListIndex(idx,3);
reverseList(&list);
getFacetByIndex(new_facets,1)->corners = list;
@@ -297,7 +320,7 @@ void zhullInitialFacets(zhull_t *zh) {
}
}
-void printHorizonEdges(list_t *horizon_fcts,
+static void printHorizonEdges(list_t *horizon_fcts,
list_t *horizon_fcts_edges,
list_t *other_horizon_edges) {
index_t i;
@@ -318,7 +341,7 @@ void printHorizonEdges(list_t *horizon_fcts,
}
-void sortHorizonEdges(list_t *horizon_fcts,
+static void sortHorizonEdges(list_t *horizon_fcts,
list_t *horizon_fcts_edges,
list_t *other_horizon_edges) {
index_t i,j;
@@ -372,7 +395,7 @@ void sortHorizonEdges(list_t *horizon_fcts,
}
}
-void removeVisibleFacetsGetHorizonAndAvailablePoints(
+static void removeVisibleFacetsGetHorizonAndAvailablePoints(
zhull_t * const zh, index_t point_index,
facet_t *f,
list_t *horizon_fcts,
@@ -487,7 +510,7 @@ void removeVisibleFacetsGetHorizonAndAvailablePoints(
}
}
-void initNewFacets(zhull_t *zh, index_t point_index,
+static void initNewFacets(zhull_t *zh, index_t point_index,
list_t new_facets, list_t horizon_fcts,
list_t horizon_fcts_edges, list_t other_horizon_edges) {
index_t i,j;
@@ -572,12 +595,13 @@ void initNewFacets(zhull_t *zh, index_t point_index,
}
}
-void makePyramidFacetsToHorizon(zhull_t *zh, index_t point_index,
+static void makePyramidFacetsToHorizon(zhull_t *zh, index_t point_index,
list_t horizon_fcts, list_t horizon_fcts_edges,
list_t other_horizon_edges, list_t avail_points) {
list_t new_facets = appendNewFacets(zh, getLength(horizon_fcts_edges));
// printf("making new pyramid of %d facets\n",getLength(horizon_fcts_edges));
initNewFacets(zh,point_index,new_facets,horizon_fcts,horizon_fcts_edges,other_horizon_edges);
+ appendToList(&(zh->used_pts),entry_makeIndex(point_index));
/* printf("available points: ");
printList(avail_points);
printf("new facets : ");
@@ -586,12 +610,35 @@ void makePyramidFacetsToHorizon(zhull_t *zh, index_t point_index,
freeList(&new_facets);
}
-void calculateZHull(zhull_t *zh,int maxit) {
+static appendExteriorPoints(zhull_t *zh) {
+ index_t i;
+ vector_t center = initVector(0.0f,0.0f,0.0f);
+ list_t facet_delete_list=emptyList();
+ facet_t *f;
+ center=averageListedPoints(zh->pts,zh->used_pts);
+ printf("central point\n");
+ printVector(center);
+ printf("\n");
+ for (i=0; i<getLength(zh->facets); i++) {
+ f=getFacetByIndex(zh->facets,i);
+ printf("distance of plane %d, d=%5.2f\n",i,
+ distancePointPlane(center,f->plane));
+ if (distancePointPlane(center,f->plane)>-0.5f) {
+ appendToList(&facet_delete_list,entry_makePointer(f));
+ }
+ }
+ printList(facet_delete_list);
+ removeFacetByPointerList(zh,facet_delete_list);
+ freeList(&facet_delete_list);
+}
+
+int calculateZHull(zhull_t *zh) {
index_t fli=0;
index_t pi;
facet_t *f;
list_t outsideset;
int cnt=0;
+ int maxit=getNumPoints(zh->pts);
list_t horizon_fcts=emptyList();
list_t horizon_fcts_edges=emptyList();
list_t other_horizon_edges=emptyList();
@@ -599,8 +646,8 @@ void calculateZHull(zhull_t *zh,int maxit) {
entry_t e;
- if (maxit>MAXIT)
- maxit=MAXIT;
+// if (maxit>MAXIT)
+// maxit=MAXIT;
if (getNumPoints(zh->pts)!=0){
zhullInitialFacets(zh);
//printZhull(zh);
@@ -635,7 +682,9 @@ void calculateZHull(zhull_t *zh,int maxit) {
freeList(&available_points);
fli++;
}
+// appendExteriorPoints(zh);
}
+ return cnt;
}
void printZhull(const zhull_t * const zh) {
diff --git a/src/mtx_qhull/zhull.h b/src/mtx_qhull/zhull.h
index fc0ff14..cc40f47 100644
--- a/src/mtx_qhull/zhull.h
+++ b/src/mtx_qhull/zhull.h
@@ -10,7 +10,24 @@
#define TOL_INSIDEPOINT -1e-7
#define TOL_DEGENERATE 1e-6
#define MAXIT 1000000
-
+/*
+ * zhull
+ *
+ * own qhull algorithm implementation
+ *
+ * Copyright (c) 2012, Franz Zotter
+ * with friendly help from
+ * IOhannes zmoelnig
+ * IEM, Graz, Austria
+ *
+ * own Implementation after the QHULL algorithm
+ * that is documented in
+ * Barber, C.B., Dobkin, D.P., and Huhdanpaa, H.T.,
+ * "The Quickhull algorithm for convex hulls," ACM Trans.
+ * on Mathematical Software, 22(4):469-483, Dec 1996,
+ * http://www.qhull.org
+ *
+ */
typedef struct facet_ {
plane_t plane;
@@ -24,12 +41,13 @@ typedef struct facet_ {
typedef struct zhull_ {
points_t pts;
+ list_t used_pts;
list_t facets;
list_t facets_with_outsidepoints;
list_t facets_with_insidepoints;
} zhull_t;
-void calculateZHull(zhull_t *zh,int maxit);
+int calculateZHull(zhull_t *zh);
index_t getTriangleCorner(const zhull_t * const zh,
const index_t triangle_idx,
const index_t corner_idx);