summaryrefslogtreecommitdiff
path: root/src/lib/evas/include/evas_3d_utils.h
diff options
context:
space:
mode:
authorperepelits.m <perepelits.m@samsung.com>2015-07-04 02:39:08 +0200
committerCedric BAIL <cedric@osg.samsung.com>2015-07-04 02:39:11 +0200
commite40c223181ec6b46437796809f6c2a7595bfc9bd (patch)
treec2c8e43ff253aa3f02dbf6a08509322f14576004 /src/lib/evas/include/evas_3d_utils.h
parent68d9c3d6f0595179199afbe37f07a3f2be5d6df4 (diff)
edje: add Convex Hull logic
Summary: This is an algorithm which calcuates a convex hull of some mesh, in fact it returns vertex, index, normal and color datas, though the new mesh could be build just as for AABB Reviewers: raster, Hermet, cedric Subscribers: cedric, artem.popov Differential Revision: https://phab.enlightenment.org/D2585 Signed-off-by: Cedric BAIL <cedric@osg.samsung.com>
Diffstat (limited to 'src/lib/evas/include/evas_3d_utils.h')
-rw-r--r--src/lib/evas/include/evas_3d_utils.h681
1 files changed, 681 insertions, 0 deletions
diff --git a/src/lib/evas/include/evas_3d_utils.h b/src/lib/evas/include/evas_3d_utils.h
index 828348df77..bd6aaa60ac 100644
--- a/src/lib/evas/include/evas_3d_utils.h
+++ b/src/lib/evas/include/evas_3d_utils.h
@@ -7,6 +7,10 @@
7 7
8#define DEGREE_TO_RADIAN(x) (((x) * M_PI) / 180.0) 8#define DEGREE_TO_RADIAN(x) (((x) * M_PI) / 180.0)
9#define EVAS_MATRIX_IS_IDENTITY 0x00000001 9#define EVAS_MATRIX_IS_IDENTITY 0x00000001
10#define MIN_DIFF 0.00000000001
11
12#define FLT_COMPARISON(a, b) \
13 (fabs(a - b) > FLT_EPSILON)
10 14
11typedef struct _Evas_Color Evas_Color; 15typedef struct _Evas_Color Evas_Color;
12typedef struct _Evas_Vec2 Evas_Vec2; 16typedef struct _Evas_Vec2 Evas_Vec2;
@@ -345,6 +349,15 @@ evas_vec3_distance_square_get(const Evas_Vec3 *a, const Evas_Vec3 *b)
345 return evas_vec3_length_square_get(&v); 349 return evas_vec3_length_square_get(&v);
346} 350}
347 351
352static inline Evas_Real
353evas_vec3_angle_get(const Evas_Vec3 *a, const Evas_Vec3 *b)
354{
355 Evas_Real angle;
356
357 angle = evas_vec3_dot_product(a, b) / (evas_vec3_length_get(a) * evas_vec3_length_get(b));
358 return angle;
359}
360
348static inline void 361static inline void
349evas_vec3_normalize(Evas_Vec3 *out, const Evas_Vec3 *v) 362evas_vec3_normalize(Evas_Vec3 *out, const Evas_Vec3 *v)
350{ 363{
@@ -571,6 +584,25 @@ evas_vec4_transform(Evas_Vec4 *out, const Evas_Vec4 *v, const Evas_Mat4 *m)
571} 584}
572 585
573static inline void 586static inline void
587evas_vec4_plain_by_points(Evas_Vec4 *out, const Evas_Vec3 *a, const Evas_Vec3 *b, const Evas_Vec3 *c)
588{
589 out->x = (b->y - a->y) * (c->z - a->z) - (b->z - a->z) * (c->y - a->y);
590 out->y = -(b->x - a->x) * (c->z - a->z) + (b->z - a->z) * (c->x - a->x);
591 out->z = (b->x - a->x) * (c->y - a->y) - (b->y - a->y) * (c->x - a->x);
592 out->w = (-a->x) * ((b->y - a->y)*(c->z - a->z) - (b->z - a->z) * (c->y - a->y)) -
593 (-a->y) * ((b->x - a->x) * (c->z - a->z) - (b->z - a->z) * (c->x - a->x)) +
594 (-a->z) * ((b->x - a->x) * (c->y - a->y) - (b->y - a->y) * (c->x - a->x));
595}
596
597static inline Evas_Real
598evas_vec4_angle_plains(Evas_Vec4 *a, Evas_Vec4 *b)
599{
600 return (Evas_Real) ((a->x * b->x) + (a->y * b->y) + (a->z * b->z)) / ((sqrt((a->x * a->x) +
601 (a->y * a->y) + (a->z * a->z))) * (sqrt((b->x * b->x) + (b->y * b->y) +
602 (b->z * b->z))));
603}
604
605static inline void
574evas_vec3_homogeneous_position_set(Evas_Vec3 *out, const Evas_Vec4 *v) 606evas_vec3_homogeneous_position_set(Evas_Vec3 *out, const Evas_Vec4 *v)
575{ 607{
576 /* Assume "v" is a positional vector. (v->w != 0.0) */ 608 /* Assume "v" is a positional vector. (v->w != 0.0) */
@@ -590,6 +622,95 @@ evas_vec3_homogeneous_direction_set(Evas_Vec3 *out, const Evas_Vec4 *v)
590 out->z = v->z; 622 out->z = v->z;
591} 623}
592 624
625static inline Eina_Bool
626evas_vec3_if_equivalent(Evas_Vec3 *a, const Evas_Vec3 *b)
627{
628 /* Assume "v" is a directional vector. (v->w == 0.0) */
629 return ((a->x == b->x) && (a->y == b->y) && (a->z == b->z));
630}
631
632static inline void
633evas_triangle3_set(Evas_Triangle3 *v, Evas_Vec3 *a, Evas_Vec3 *b, Evas_Vec3 *c)
634{
635 evas_vec3_copy(&v->p0, a);
636 evas_vec3_copy(&v->p1, b);
637 evas_vec3_copy(&v->p2, c);
638}
639
640static inline Eina_Bool
641evas_triangle3_is_line(Evas_Triangle3 *v)
642{
643 if (evas_vec3_if_equivalent(&v->p0, &v->p1) ||
644 evas_vec3_if_equivalent(&v->p0, &v->p2) ||
645 evas_vec3_if_equivalent(&v->p1, &v->p2))
646 return EINA_TRUE;
647
648 return EINA_FALSE;
649}
650
651static inline Eina_Bool
652convex_hull_triangle3_if_not_first_edje(Evas_Triangle3 *v, Evas_Vec3 *a, Evas_Vec3 *b)
653{
654 if (((v->p1.x == a->x) && (v->p1.y == a->y) && (v->p1.z == a->z)) &&
655 ((v->p2.x == b->x) && (v->p2.y == b->y) && (v->p2.z == b->z)))
656 return EINA_TRUE;
657 else if (((v->p2.x == a->x) && (v->p2.y == a->y) && (v->p2.z == a->z)) &&
658 ((v->p1.x == b->x) && (v->p1.y == b->y) && (v->p1.z == b->z)))
659 return EINA_TRUE;
660
661 return EINA_FALSE;
662}
663
664static inline Eina_Bool
665convex_hull_triangle3_if_first_edje(Evas_Triangle3 *v, Evas_Vec3 *a, Evas_Vec3 *b)
666{
667 if ((!FLT_COMPARISON(v->p0.x, a->x) && !FLT_COMPARISON(v->p0.y, a->y) &&
668 !FLT_COMPARISON(v->p0.z, a->z)) && (!FLT_COMPARISON(v->p1.x, b->x) &&
669 !FLT_COMPARISON(v->p1.y, b->y) && !FLT_COMPARISON(v->p1.z, b->z)))
670 return EINA_TRUE;
671 else if ((!FLT_COMPARISON(v->p1.x, a->x) && !FLT_COMPARISON(v->p1.y, a->y) &&
672 !FLT_COMPARISON(v->p1.z, a->z)) && (!FLT_COMPARISON(v->p0.x, b->x) &&
673 !FLT_COMPARISON(v->p0.y, b->y) && !FLT_COMPARISON(v->p0.z, b->z)))
674 return EINA_TRUE;
675
676 return EINA_FALSE;
677}
678
679static inline Eina_Bool
680convex_hull_triangle3_if_first_point(Evas_Triangle3 *v, Evas_Vec3 *a)
681{
682 return ((v->p0.x == a->x) && (v->p0.y == a->y) && (v->p0.z == a->z));
683}
684
685static inline Eina_Bool
686evas_vec3_if_equivalent_as_triangle(Evas_Vec3 *v0, Evas_Vec3 *v1, Evas_Vec3 *v2,
687 Evas_Vec3 *w0, Evas_Vec3 *w1, Evas_Vec3 *w2)
688{
689 if (((v0->x == w0->x) && (v0->y == w0->y) && (v0->z == w0->z)) &&
690 ((v1->x == w1->x) && (v1->y == w1->y) && (v1->z == w1->z)) &&
691 ((v2->x == w2->x) && (v2->y == w2->y) && (v2->z == w2->z)))
692 return EINA_TRUE;
693
694 return EINA_FALSE;
695}
696
697
698static inline Eina_Bool
699evas_triangle3_if_equivalent(Evas_Triangle3 *a, Evas_Triangle3 *b)
700{
701 /* to compare two triangles there are six permutations
702 to test because vertices are unordered */
703 if (evas_vec3_if_equivalent_as_triangle(&a->p0, &a->p1, &a->p2, &b->p0, &b->p1, &b->p2) ||
704 evas_vec3_if_equivalent_as_triangle(&a->p0, &a->p1, &a->p2, &b->p0, &b->p2, &b->p1) ||
705 evas_vec3_if_equivalent_as_triangle(&a->p0, &a->p1, &a->p2, &b->p1, &b->p0, &b->p2) ||
706 evas_vec3_if_equivalent_as_triangle(&a->p0, &a->p1, &a->p2, &b->p1, &b->p2, &b->p0) ||
707 evas_vec3_if_equivalent_as_triangle(&a->p0, &a->p1, &a->p2, &b->p2, &b->p0, &b->p1) ||
708 evas_vec3_if_equivalent_as_triangle(&a->p0, &a->p1, &a->p2, &b->p2, &b->p1, &b->p0))
709 return EINA_TRUE;
710
711 return EINA_FALSE;
712}
713
593static inline void 714static inline void
594evas_vec4_homogeneous_position_set(Evas_Vec4 *out, const Evas_Vec3 *v) 715evas_vec4_homogeneous_position_set(Evas_Vec4 *out, const Evas_Vec3 *v)
595{ 716{
@@ -2035,3 +2156,563 @@ box_intersection_box(Evas_Box3 *v1, Evas_Box3 *v2)
2035 return EINA_TRUE; 2156 return EINA_TRUE;
2036} 2157}
2037 2158
2159static inline void
2160convex_hull_vertex_set(Evas_Triangle3 *el, int *vertex_count, float **vertex,
2161 unsigned short int **index, unsigned int k, int *leader, int coord)
2162{
2163 int color_coords, normal_coords;
2164 Evas_Vec3 vect;
2165 switch (coord)
2166 {
2167 case 0:
2168 vect = el->p0;
2169 break;
2170 case 1:
2171 vect = el->p1;
2172 break;
2173 case 2:
2174 vect = el->p2;
2175 break;
2176 }
2177 (*vertex_count)++;
2178 *vertex = (float*) realloc(*vertex, (10 * (*vertex_count)) * sizeof(float));
2179
2180 (*vertex)[10 * (*vertex_count) - 10] = vect.x;
2181 (*vertex)[10 * (*vertex_count) - 9] = vect.y;
2182 (*vertex)[10 * (*vertex_count) - 8] = vect.z;
2183 /* set alpha canal */
2184 (*vertex)[10 * (*vertex_count) - 1] = 1.0;
2185 /* set color */
2186 for (color_coords = 2; color_coords < 5; color_coords++)
2187 (*vertex)[10 * (*vertex_count) - color_coords] = (float) rand() / RAND_MAX;
2188 /* set normal coords */
2189 for (normal_coords = 5; normal_coords < 8; normal_coords++)
2190 (*vertex)[10 * (*vertex_count) - normal_coords] = 1.0;
2191 (*index)[3 * k + coord] = *leader;
2192 (*leader)++;
2193}
2194
2195static inline Evas_Triangle3
2196convex_hull_first_tr_get(float *data, int count, int stride)
2197{
2198 Evas_Triangle3 out;
2199
2200 Evas_Vec3 triangle1;
2201 Evas_Vec3 triangle2, triangle2_candidate;
2202 Evas_Vec3 triangle3, triangle3_candidate;
2203 Evas_Vec3 first, second, complanar1, complanar2, candidate;
2204 Evas_Vec4 normal_a, normal_b;
2205
2206 Evas_Real cos = 0.0, new_cos = 0.0, tan = 0.0, new_tan = 0.0, cos_2d = 0.0, new_cos_2d = 0.0;
2207 int first_num = 0, second_num = 0;
2208 int i = 0, j = 0;
2209
2210 evas_vec3_set(&triangle1, data[0], data[1], data[2]);
2211
2212 for (i = 1, j = stride; i < count; i++, j += stride)
2213 {
2214 if ((triangle1.z > data[j + 2]) ||
2215 ((triangle1.z == data[j + 2]) && (triangle1.y > data[j + 1])) ||
2216 ((triangle1.z == data[j + 2]) && (triangle1.y == data[j + 1]) && (triangle1.x > data[j])))
2217 {
2218 evas_vec3_set(&triangle1, data[j], data[j + 1], data[j + 2]);
2219 first_num = i;
2220 }
2221 }
2222
2223 if (first_num)
2224 evas_vec3_set(&triangle2, data[0], data[1], data[2]);
2225 else
2226 {
2227 evas_vec3_set(&triangle2, data[3], data[4], data[5]);
2228 second_num = 1;
2229 }
2230
2231 tan = fabs(triangle2.z - triangle1.z) / fabs(triangle2.y - triangle1.y);
2232
2233#define COMPARE_ANGLES(trigonom, triangle, previous, big, little) \
2234 if (little > big + FLT_EPSILON) \
2235 { \
2236 trigonom = new_##trigonom; \
2237 cos_2d = new_cos_2d; \
2238 evas_vec3_set(&triangle, data[j], data[j + 1], data[j + 2]); \
2239 } \
2240 else if(!FLT_COMPARISON(little, big) && \
2241 (evas_vec3_distance_get(&triangle##_candidate, &previous) > \
2242 evas_vec3_distance_get(&triangle, &previous))) \
2243 { \
2244 evas_vec3_set(&triangle, data[j], data[j + 1], data[j + 2]); \
2245 }
2246 evas_vec3_set(&complanar1, 1, 0, 0);
2247 for (i = 0, j = 0; i < count; i++, j += stride)
2248 {
2249 if (FLT_COMPARISON(data[j], triangle1.x) ||
2250 FLT_COMPARISON(data[j + 1], triangle1.y) ||
2251 FLT_COMPARISON(data[j + 2], triangle1.z))
2252 {
2253 new_tan = fabs(data[j + 2] - triangle1.z) / fabs(data[j + 1] - triangle1.y);
2254
2255 if (FLT_COMPARISON(data[j + 1], triangle1.y) &&
2256 FLT_COMPARISON(triangle2.y, triangle1.y))
2257 {
2258 if (tan > new_tan + FLT_EPSILON)
2259 {
2260 tan = new_tan;
2261 evas_vec3_set(&triangle2, data[j], data[j + 1], data[j + 2]);
2262 second_num = i;
2263 evas_vec3_subtract(&first, &complanar1, &triangle1);
2264 evas_vec3_subtract(&second, &triangle2, &triangle1);
2265 cos_2d = evas_vec3_angle_get(&complanar1, &second);
2266 }
2267 else if (!FLT_COMPARISON(tan, new_tan))
2268 {
2269 evas_vec3_subtract(&first, &complanar1, &triangle2);
2270 evas_vec3_set(&triangle2_candidate, data[j], data[j + 1], data[j + 2]);
2271 evas_vec3_subtract(&first, &complanar1, &triangle1);
2272 evas_vec3_subtract(&second, &triangle2_candidate, &triangle1);
2273 new_cos_2d = evas_vec3_angle_get(&complanar1, &second);
2274 if (new_cos_2d > cos_2d + FLT_EPSILON)
2275 second_num = i;
2276
2277 COMPARE_ANGLES(cos, triangle2, triangle1, cos_2d, new_cos_2d)
2278 }
2279 }
2280
2281 else if (!FLT_COMPARISON(data[j + 1], triangle1.y) &&
2282 !FLT_COMPARISON(data[j + 2], triangle1.z) &&
2283 FLT_COMPARISON(triangle2.y, triangle1.y))
2284 evas_vec3_set(&triangle2, data[j], data[j + 1], data[j + 2]);
2285
2286 else if (!FLT_COMPARISON(data[j + 1], triangle1.y) &&
2287 !FLT_COMPARISON(data[j + 2], triangle1.z) &&
2288 !FLT_COMPARISON(triangle2.z, triangle1.z) &&
2289 !FLT_COMPARISON(triangle2.y, triangle1.y))
2290 {
2291 evas_vec3_set(&triangle2_candidate, data[j], data[j + 1], data[j + 2]);
2292 if (evas_vec3_distance_get(&triangle2_candidate, &triangle1) >
2293 evas_vec3_distance_get(&triangle2, &triangle1))
2294 evas_vec3_set(&triangle2, data[j], data[j + 1], data[j + 2]);
2295 }
2296 }
2297 }
2298
2299 evas_vec3_set(&complanar1, triangle1.x + 1, triangle1.y, triangle1.z);
2300 evas_vec3_set(&complanar2, triangle1.x, triangle1.y + 1, triangle1.z);
2301 evas_vec4_plain_by_points(&normal_a, &triangle1, &complanar1, &complanar2);
2302
2303 if (normal_a.z < 0)
2304 evas_vec4_scale(&normal_a, &normal_a, -1);
2305
2306 evas_vec3_set(&triangle3, data[0], data[1], data[2]);
2307
2308 cos = -1.0;
2309 cos_2d = 1.0;
2310
2311 for (i = 0, j = 0; i < count; i++, j += stride)
2312 {
2313 if ((i != first_num) && (i != second_num))
2314 {
2315 evas_vec3_set(&candidate, data[j], data[j + 1], data[j + 2]);
2316 evas_vec4_plain_by_points(&normal_b, &triangle1, &candidate, &triangle2);
2317
2318 if (normal_b.z < 0)
2319 evas_vec4_scale(&normal_b, &normal_b, -1);
2320
2321 new_cos = evas_vec4_angle_plains(&normal_a, &normal_b);
2322
2323 if (new_cos > cos + FLT_EPSILON)
2324 {
2325 evas_vec3_set(&triangle3_candidate, data[j], data[j + 1], data[j + 2]);
2326 evas_vec3_subtract(&first, &triangle2, &triangle1);
2327 evas_vec3_subtract(&second, &triangle3, &triangle1);
2328 cos = new_cos;
2329 evas_vec3_set(&triangle3, data[j], data[j + 1], data[j + 2]);
2330 cos_2d = evas_vec3_angle_get(&second, &first);
2331 }
2332 else if (!FLT_COMPARISON(new_cos, cos))
2333 {
2334 evas_vec3_set(&triangle3_candidate, data[j], data[j + 1], data[j + 2]);
2335 evas_vec3_subtract(&first, &triangle1, &triangle2);
2336 evas_vec3_subtract(&second, &triangle3_candidate, &triangle2);
2337 new_cos_2d = evas_vec3_angle_get(&first, &second);
2338
2339 COMPARE_ANGLES(tan, triangle3, triangle2, new_cos_2d, cos_2d)
2340 }
2341 }
2342 }
2343
2344 evas_triangle3_set(&out, &triangle1, &triangle2, &triangle3);
2345
2346#undef COMPARE_ANGLES
2347 return out;
2348}
2349
2350static inline void
2351evas_convex_hull_get(float *data, int count, int stride, float **vertex,
2352 unsigned short int **index, int *vertex_count, int *index_count)
2353{
2354 Evas_Triangle3 first_elem, second_elem, *third_elem = NULL, *el = NULL;
2355
2356 Evas_Vec3 *next = NULL, *best = NULL, *next_2d = NULL, *el_vec3 = NULL;
2357 Evas_Vec3 tmp1, tmp2;
2358 Evas_Vec4 normal_a, normal_b;
2359
2360 Eina_Array arr_elems;
2361 Eina_Array arr_triangles;
2362 Eina_Array arr_candidates;
2363 Eina_Array arr_ch;
2364 Eina_Array_Iterator iterator;
2365
2366 Evas_Real cos = 0.0, new_cos = 0.0, cos_2d = 0.0;
2367 float *found_vertex = NULL;
2368 int i = 0, j = 0, new_stride = 0, leader = 0;
2369 int if_two = 0, first_exist_twice = 0, second_exist_twice = 0;
2370 unsigned int k = 0;
2371 unsigned short int *found_index = NULL;
2372
2373 Eina_Bool exist1 = EINA_FALSE, pushed;
2374 Eina_Bool equivalent_triangle = EINA_FALSE, triangle_chain = EINA_FALSE;
2375 Eina_Bool on_plain = EINA_FALSE, right = EINA_FALSE;
2376
2377 eina_array_step_set(&arr_elems, sizeof(Eina_Array), 1);
2378 eina_array_step_set(&arr_triangles, sizeof(Eina_Array), 1);
2379 eina_array_step_set(&arr_candidates, sizeof(Eina_Array), 1);
2380 eina_array_step_set(&arr_ch, sizeof(Eina_Array), 1);
2381
2382 /* Finding of first triangle in convex hull */
2383 first_elem = convex_hull_first_tr_get(data, count, stride);
2384
2385 eina_array_push(&arr_triangles, &first_elem);
2386 eina_array_push(&arr_elems, &first_elem);
2387
2388 evas_triangle3_set(&second_elem, &first_elem.p1, &first_elem.p2, &first_elem.p0);
2389 eina_array_push(&arr_elems, &second_elem);
2390 eina_array_push(&arr_triangles, &second_elem);
2391
2392 third_elem = malloc(sizeof(Evas_Triangle3));
2393 evas_triangle3_set(third_elem, &first_elem.p2, &first_elem.p0, &first_elem.p1);
2394 eina_array_push(&arr_elems, third_elem);
2395 eina_array_push(&arr_triangles, third_elem);
2396 eina_array_push(&arr_ch, third_elem);
2397
2398 el = eina_array_data_get(&arr_elems, 0);
2399
2400 /* arr_ellems is an array of triangles, in fact it is a queue of edjes
2401 because vertices in triangles are ordered, every edje in this queue
2402 should have a conjugate edje in some other triangle */
2403 while (eina_array_count(&arr_elems) > 0)
2404 {
2405 Evas_Triangle3 *new_elem1 = NULL, *new_elem2 = NULL;
2406
2407 Evas_Triangle3 *elem = eina_array_pop(&arr_elems);
2408
2409 cos = -1.0;
2410
2411 /* searching of next triangle in convex hull as given conjugate edje
2412 and one new vertex, all vertices should be checked */
2413 for (i = 0, j = 0; i < count; i++, j += stride)
2414 {
2415 if ((FLT_COMPARISON(elem->p0.x, data[j]) || FLT_COMPARISON(elem->p0.y, data[j + 1]) ||
2416 FLT_COMPARISON(elem->p0.z, data[j + 2])) && (FLT_COMPARISON(elem->p1.x, data[j]) ||
2417 FLT_COMPARISON(elem->p1.y, data[j + 1]) || FLT_COMPARISON(elem->p1.z, data[j + 2])) &&
2418 (FLT_COMPARISON(elem->p2.x, data[j]) || FLT_COMPARISON(elem->p2.y, data[j + 1]) ||
2419 FLT_COMPARISON(elem->p2.z, data[j + 2])))
2420 {
2421 next = malloc(sizeof(Evas_Vec3));
2422 evas_vec3_set(next, data[j], data[j + 1], data[j + 2]);
2423 pushed = EINA_FALSE;
2424
2425 /* something like the dihedral angle between the triangles
2426 is a determining factor in searching the necessary points */
2427
2428 evas_vec4_plain_by_points(&normal_a, &elem->p0, &elem->p1, &elem->p2);
2429 evas_vec4_plain_by_points(&normal_b, &elem->p0, &elem->p1, next);
2430
2431 /* MIN_DIFF because vertices that belong to plain shouldn't be included */
2432 if (fabs(normal_a.x * data[j] + normal_a.y * data[j + 1] + normal_a.z * data[j + 2] + normal_a.w) < MIN_DIFF)
2433 {
2434 /* based on the construction of triangles, parallel but not collinear normal
2435 means that the triangles overlap, which is the worst case */
2436 if ((normal_a.x * normal_b.x <= 0) && (normal_a.y * normal_b.y <= 0) && (normal_a.z * normal_b.z <= 0) &&
2437 ((fabs(normal_a.x) > DBL_EPSILON) || (fabs(normal_a.y) > DBL_EPSILON) || (fabs(normal_a.z) > DBL_EPSILON)) &&
2438 ((fabs(normal_b.x) > DBL_EPSILON) || (fabs(normal_b.y) > DBL_EPSILON) || (fabs(normal_b.z) > DBL_EPSILON)))
2439 new_cos = 1.0;
2440 else new_cos = -1.0;
2441 }
2442
2443 else
2444 {
2445 if (normal_a.x * data[j] + normal_a.y * data[j+1] + normal_a.z * data[j+2] + normal_a.w < 0)
2446 evas_vec4_scale(&normal_a, &normal_a, -1);
2447 if (normal_b.x * elem->p2.x + normal_b.y * elem->p2.y + normal_b.z * elem->p2.z + normal_b.w < 0)
2448 evas_vec4_scale(&normal_b, &normal_b, -1);
2449
2450 new_cos = evas_vec4_angle_plains(&normal_a, &normal_b);
2451 }
2452
2453 /* MIN_DIFF is more useful for dihedral angles apparently */
2454 if (new_cos > cos + MIN_DIFF)
2455 {
2456 cos = new_cos;
2457 EINA_ARRAY_ITER_NEXT(&arr_candidates, k, el_vec3, iterator)
2458 free(el_vec3);
2459
2460 /* Vertex gets into arr_candidates if the corresponding cosine is the maximum */
2461 eina_array_flush(&arr_candidates);
2462 eina_array_step_set(&arr_candidates, sizeof(Eina_Array), 1);
2463 eina_array_push(&arr_candidates, next);
2464 pushed = EINA_TRUE;
2465 }
2466 else if (fabs(new_cos - cos) < MIN_DIFF)
2467 {
2468 exist1 = EINA_FALSE;
2469
2470 for (k = 0; (k < eina_array_count(&arr_candidates)) && !exist1; k++)
2471 {
2472 next_2d = eina_array_data_get(&arr_candidates, k);
2473 exist1 = evas_vec3_if_equivalent(next, next_2d);
2474 }
2475 if (!exist1)
2476 {
2477 eina_array_push(&arr_candidates, next);
2478 pushed = EINA_TRUE;
2479 }
2480 }
2481
2482 if (!pushed)
2483 free(next);
2484 }
2485 }
2486
2487 on_plain = EINA_FALSE;
2488 right = EINA_FALSE;
2489
2490 /* The case when several points are found, is discussed below.
2491 This case is interesting because the convex hull in the
2492 two-dimensional subspace should be filled further */
2493 if ((cos != 1.0) && (1 < eina_array_count(&arr_candidates)))
2494 {
2495 Evas_Vec3 angle_from, angle_to;
2496 next_2d = eina_array_data_get(&arr_candidates, 0);
2497 evas_vec4_plain_by_points(&normal_b, &elem->p1, &elem->p0, next_2d);
2498
2499 if (normal_b.x * elem->p2.x + normal_b.y * elem->p2.y + normal_b.z * elem->p2.z + normal_b.w > 0)
2500 {
2501 evas_vec3_subtract(&angle_from, &elem->p0, &elem->p1);
2502 right = EINA_TRUE;
2503 }
2504 else
2505 evas_vec3_subtract(&angle_from, &elem->p1, &elem->p0);
2506
2507 cos_2d = -1.0;
2508
2509 EINA_ARRAY_ITER_NEXT(&arr_candidates, k, next_2d, iterator)
2510 {
2511 /* Selection of the required vertex occurs on the basis of a specific angle */
2512 if (right)
2513 evas_vec3_subtract(&angle_to, next_2d, &elem->p0);
2514 else
2515 evas_vec3_subtract(&angle_to, next_2d, &elem->p1);
2516
2517 new_cos = evas_vec3_dot_product(&angle_from, &angle_to) /
2518 (evas_vec3_length_get(&angle_from) * evas_vec3_length_get(&angle_to));
2519 if (new_cos > cos_2d + FLT_EPSILON)
2520 {
2521 cos_2d = new_cos;
2522 best = eina_array_data_get(&arr_candidates, k);
2523 }
2524 else if (!FLT_COMPARISON(new_cos, cos_2d))
2525 {
2526 if ((right && (evas_vec3_distance_get(best, &elem->p0) < evas_vec3_length_get(&angle_from))) ||
2527 (!right && (evas_vec3_distance_get(best, &elem->p1) < evas_vec3_length_get(&angle_from))))
2528 best = eina_array_data_get(&arr_candidates, k);
2529 }
2530 }
2531 }
2532
2533 /* This event will take place after the previous,
2534 in fact, choice of first triangle in a new two-dimensional
2535 convex hull allows to fill it fan counterclockwise when viewed from the inside */
2536 else if ((cos == 1.0) && (1 < eina_array_count(&arr_candidates)))
2537 {
2538 Evas_Vec3 angle_from, angle_to;
2539 evas_vec3_subtract(&angle_from, &elem->p0, &elem->p1);
2540 cos_2d = -1.0;
2541 EINA_ARRAY_ITER_NEXT(&arr_candidates, k, next_2d, iterator)
2542 {
2543 evas_vec3_subtract(&angle_to, next_2d, &elem->p0);
2544
2545 evas_vec4_plain_by_points(&normal_a, &elem->p0, &elem->p1, &elem->p2);
2546 evas_vec4_plain_by_points(&normal_b, &elem->p0, &elem->p1, next_2d);
2547 if ((normal_a.x * normal_b.x <= 0) && (normal_a.y * normal_b.y <= 0) && (normal_a.z * normal_b.z <= 0))
2548 {
2549 new_cos = evas_vec3_dot_product(&angle_from, &angle_to) /
2550 (evas_vec3_length_get(&angle_from) * evas_vec3_length_get(&angle_to));
2551 if (new_cos > cos_2d + FLT_EPSILON)
2552 {
2553 cos_2d = new_cos;
2554 best = eina_array_data_get(&arr_candidates, k);
2555 }
2556 else if (!FLT_COMPARISON(new_cos, cos_2d))
2557 {
2558 if (evas_vec3_distance_get(best, &elem->p0) < evas_vec3_length_get(&angle_to))
2559 best = eina_array_data_get(&arr_candidates, k);
2560 }
2561 on_plain = EINA_TRUE;
2562 }
2563 }
2564 }
2565
2566 else
2567 best = eina_array_data_get(&arr_candidates, 0);
2568
2569 evas_vec4_plain_by_points(&normal_b, &elem->p0, &elem->p1, best);
2570
2571 if_two = 0;
2572 first_exist_twice = 0;
2573 second_exist_twice = 0;
2574 equivalent_triangle = EINA_FALSE;
2575 triangle_chain = EINA_FALSE;
2576 evas_vec3_copy(&tmp1, &elem->p0);
2577 evas_vec3_copy(&tmp2, &elem->p1);
2578 new_elem1 = malloc(sizeof(Evas_Triangle3));
2579 evas_triangle3_set(new_elem1, best, &tmp1, &tmp2);
2580 pushed = EINA_FALSE;
2581
2582 /* verification that the edje has not been found previously */
2583 EINA_ARRAY_ITER_NEXT(&arr_triangles, k, el, iterator)
2584 {
2585 if (convex_hull_triangle3_if_first_edje(el, &elem->p0, &elem->p1))
2586 if_two++;
2587 if (evas_triangle3_if_equivalent(el, new_elem1))
2588 equivalent_triangle++;
2589 }
2590
2591
2592 EINA_ARRAY_ITER_NEXT(&arr_triangles, k, el, iterator)
2593 {
2594 if ((k > 2) && (convex_hull_triangle3_if_not_first_edje(el, &elem->p0, best) ||
2595 convex_hull_triangle3_if_not_first_edje(el, &elem->p1, best)))
2596 triangle_chain = EINA_TRUE;
2597 }
2598
2599 /* There is a specific order according to which the edjes are entered in arr_elems */
2600 if (!on_plain && !right)
2601 {
2602 if ((!equivalent_triangle) && (!second_exist_twice) && (!triangle_chain) && (if_two < 2))
2603 {
2604 if (new_elem2)
2605 free (new_elem2);
2606 new_elem2 = malloc(sizeof(Evas_Triangle3));
2607 evas_triangle3_set(new_elem2, best, &tmp2, &tmp1);
2608 eina_array_push(&arr_elems, new_elem2);
2609
2610 /* triangles whose edges have been found should be entered into the arr_triangles
2611 to optimize the algorithm */
2612 if ((first_exist_twice < 2) && (second_exist_twice < 2))
2613 eina_array_push(&arr_triangles, eina_array_data_get(&arr_elems, eina_array_count(&arr_elems) - 1));
2614 }
2615 if ((!equivalent_triangle) && (!first_exist_twice) && (!triangle_chain) && (if_two < 2))
2616 {
2617 eina_array_push(&arr_elems, new_elem1);
2618 if ((first_exist_twice < 2) && (second_exist_twice < 2))
2619 {
2620 pushed = EINA_TRUE;
2621
2622 /* eina_ch is the resultant vector of all triangles in convex hull */
2623 eina_array_push(&arr_ch, eina_array_data_get(&arr_elems, eina_array_count(&arr_elems) - 1));
2624 eina_array_push(&arr_triangles, eina_array_data_get(&arr_elems, eina_array_count(&arr_elems) - 1));
2625 }
2626 }
2627 }
2628
2629 else
2630 {
2631 if ((!equivalent_triangle) && (!first_exist_twice) && (!triangle_chain) && (if_two < 2))
2632 {
2633 eina_array_push(&arr_elems, new_elem1);
2634 if ((first_exist_twice < 2) && (second_exist_twice < 2))
2635 {
2636 pushed = EINA_TRUE;
2637 eina_array_push(&arr_ch, eina_array_data_get(&arr_elems, eina_array_count(&arr_elems) - 1));
2638 eina_array_push(&arr_triangles, eina_array_data_get(&arr_elems, eina_array_count(&arr_elems) - 1));
2639 }
2640 }
2641
2642 if ((!equivalent_triangle) && (!second_exist_twice) && (!triangle_chain) && (if_two < 2))
2643 {
2644 if (new_elem2)
2645 free (new_elem2);
2646 new_elem2 = malloc(sizeof(Evas_Triangle3));
2647 evas_triangle3_set(new_elem2, best, &tmp2, &tmp1);
2648 eina_array_push(&arr_elems, new_elem2);
2649
2650 if ((first_exist_twice < 2) && (second_exist_twice < 2))
2651 eina_array_push(&arr_triangles, eina_array_data_get(&arr_elems, eina_array_count(&arr_elems)-1));
2652 }
2653 }
2654 if (!pushed)
2655 free (new_elem1);
2656 }
2657
2658
2659 *vertex_count = 0;
2660 *index_count = 3 * eina_array_count(&arr_ch);
2661
2662 found_vertex = (float*) malloc(10 * sizeof(float));
2663 found_index = (unsigned short int*) malloc((*index_count) * sizeof(unsigned short int));
2664 j = 0;
2665
2666#define CHECK_AND_SET_VERTEX(coord) \
2667 exist1 = EINA_FALSE; \
2668 for (i = 0, new_stride = 0; i < (*vertex_count) && !exist1; i++, new_stride += 10) \
2669 { \
2670 if ((k > 0) && (el->p##coord.x == found_vertex[new_stride]) && \
2671 (el->p##coord.y == found_vertex[new_stride + 1]) && \
2672 (el->p##coord.z == found_vertex[new_stride + 2])) \
2673 { \
2674 exist1 = EINA_TRUE; \
2675 found_index[3 * k + coord] = i; \
2676 } \
2677 } \
2678 if (!exist1) \
2679 convex_hull_vertex_set(el, vertex_count, &found_vertex, \
2680 &found_index, k, &leader, coord);
2681
2682 EINA_ARRAY_ITER_NEXT(&arr_ch, k, el, iterator)
2683 {
2684 CHECK_AND_SET_VERTEX(0)
2685 CHECK_AND_SET_VERTEX(1)
2686 CHECK_AND_SET_VERTEX(2)
2687
2688 j += 30;
2689 }
2690
2691 *vertex = (float*) malloc((10 * (*vertex_count)) * sizeof(float));
2692 memcpy(*vertex, found_vertex, (10 * (*vertex_count)) * sizeof(float));
2693 free(found_vertex);
2694
2695 *index = (unsigned short int*) malloc((*index_count) * sizeof(unsigned short int));
2696 memcpy(*index, found_index, (*index_count) * sizeof(unsigned short int));
2697 free(found_index);
2698
2699 EINA_ARRAY_ITER_NEXT(&arr_triangles, k, el, iterator)
2700 {
2701 if (k > 2)
2702 free(el);
2703 }
2704
2705 free(third_elem);
2706
2707 EINA_ARRAY_ITER_NEXT(&arr_candidates, k, el_vec3, iterator)
2708 free(el_vec3);
2709
2710 eina_array_flush(&arr_candidates);
2711 eina_array_flush(&arr_ch);
2712 eina_array_flush(&arr_elems);
2713 eina_array_flush(&arr_triangles);
2714
2715#undef CHECK_AND_SET_VERTEX
2716
2717 return;
2718}