123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256257258259260261262263264265266267268269270271272273274275276277278279280281282283284285286287288289290291292293294295296297298299300301302303304305306307308309310311312313314315316317318319320321322323324325326327328329330331332333334335336337338339340341342343344345346347348349350351352353354355356357358359360361362363364365366367368369370371372373374375376377378379380381382383384385386387388389390391392393394395396397398399400401402403404405406407408409410411412413414415416417418419420421422423424425426427428429430431432433434435436437438439440441442443444445446447448449450451452453454455456457458459460461462463464465466467468469470471472473474475476477478479480481482483484485486487488489490491492493494495496497498499500501502503504505506507508509510511512513514515516517518519520521522523524525526527528529530531532533534535536537538539540541542543544545546547548549550551552553554555556557558559560561562563564565566567568569570571572573574575576577578579580581582583584585586587588589590591592593594595596597598599600601602603604605606607608609610611612613614615616617618619620621622623624625626627628629630631632633634635636637638639640641642643644645646647648649650651652653654655656657658659660661662663664665666667668669670671672673674675676677678679680681682683684685686687688689690691692693694695696697698699700701702703704705706707708709710711712713714715716717718719720721722723724725726727728729730731732733734735736737738739740741742743744745746747748749750751752753754755756757758759760761762763764765766767768769770771772773774775776777778779780781782783784785786787788789790791792793794795796797798799800801802803804805806807808809810811812813814815816817818819820821822823824825826827828829830831832833834835836837838839840841842843844845846847848849850851852853854855856857858859860861862863864865866867868869870871872873874875876877878879880881882883884885886887888889890891892893894895896897898899900901902903904905906907908909910911912913914915916917918919920921922923924925926927928929930931932933 |
- #ifndef GEOMETRY_H
- #define GEOMETRY_H
- #include "core/dvector.h"
- #include "core/math/face3.h"
- #include "core/math/rect2.h"
- #include "core/math/triangulate.h"
- #include "core/math/vector3.h"
- #include "core/object.h"
- #include "core/print_string.h"
- #include "core/vector.h"
- class Geometry {
- Geometry();
- public:
- static real_t get_closest_points_between_segments(const Vector2 &p1, const Vector2 &q1, const Vector2 &p2, const Vector2 &q2, Vector2 &c1, Vector2 &c2) {
- Vector2 d1 = q1 - p1;
- Vector2 d2 = q2 - p2;
- Vector2 r = p1 - p2;
- real_t a = d1.dot(d1);
- real_t e = d2.dot(d2);
- real_t f = d2.dot(r);
- real_t s, t;
-
- if (a <= CMP_EPSILON && e <= CMP_EPSILON) {
-
- c1 = p1;
- c2 = p2;
- return Math::sqrt((c1 - c2).dot(c1 - c2));
- }
- if (a <= CMP_EPSILON) {
-
- s = 0.0;
- t = f / e;
- t = CLAMP(t, 0.0, 1.0);
- } else {
- real_t c = d1.dot(r);
- if (e <= CMP_EPSILON) {
-
- t = 0.0;
- s = CLAMP(-c / a, 0.0, 1.0);
- } else {
-
- real_t b = d1.dot(d2);
- real_t denom = a * e - b * b;
-
-
- if (denom != 0.0) {
- s = CLAMP((b * f - c * e) / denom, 0.0, 1.0);
- } else
- s = 0.0;
-
-
- t = (b * s + f) / e;
-
-
-
- if (t < 0.0) {
- t = 0.0;
- s = CLAMP(-c / a, 0.0, 1.0);
- } else if (t > 1.0) {
- t = 1.0;
- s = CLAMP((b - c) / a, 0.0, 1.0);
- }
- }
- }
- c1 = p1 + d1 * s;
- c2 = p2 + d2 * t;
- return Math::sqrt((c1 - c2).dot(c1 - c2));
- }
- static void get_closest_points_between_segments(const Vector3 &p1, const Vector3 &p2, const Vector3 &q1, const Vector3 &q2, Vector3 &c1, Vector3 &c2) {
- #define d_of(m, n, o, p) ((m.x - n.x) * (o.x - p.x) + (m.y - n.y) * (o.y - p.y) + (m.z - n.z) * (o.z - p.z))
-
- real_t mua = (d_of(p1, q1, q2, q1) * d_of(q2, q1, p2, p1) - d_of(p1, q1, p2, p1) * d_of(q2, q1, q2, q1)) / (d_of(p2, p1, p2, p1) * d_of(q2, q1, q2, q1) - d_of(q2, q1, p2, p1) * d_of(q2, q1, p2, p1));
- real_t mub = (d_of(p1, q1, q2, q1) + mua * d_of(q2, q1, p2, p1)) / d_of(q2, q1, q2, q1);
-
- if (mua < 0) mua = 0;
- if (mub < 0) mub = 0;
- if (mua > 1) mua = 1;
- if (mub > 1) mub = 1;
- c1 = p1.linear_interpolate(p2, mua);
- c2 = q1.linear_interpolate(q2, mub);
- }
- static real_t get_closest_distance_between_segments(const Vector3 &p_from_a, const Vector3 &p_to_a, const Vector3 &p_from_b, const Vector3 &p_to_b) {
- Vector3 u = p_to_a - p_from_a;
- Vector3 v = p_to_b - p_from_b;
- Vector3 w = p_from_a - p_to_a;
- real_t a = u.dot(u);
- real_t b = u.dot(v);
- real_t c = v.dot(v);
- real_t d = u.dot(w);
- real_t e = v.dot(w);
- real_t D = a * c - b * b;
- real_t sc, sN, sD = D;
- real_t tc, tN, tD = D;
-
- if (D < CMP_EPSILON) {
- sN = 0.0;
- sD = 1.0;
- tN = e;
- tD = c;
- } else {
- sN = (b * e - c * d);
- tN = (a * e - b * d);
- if (sN < 0.0) {
- sN = 0.0;
- tN = e;
- tD = c;
- } else if (sN > sD) {
- sN = sD;
- tN = e + b;
- tD = c;
- }
- }
- if (tN < 0.0) {
- tN = 0.0;
-
- if (-d < 0.0)
- sN = 0.0;
- else if (-d > a)
- sN = sD;
- else {
- sN = -d;
- sD = a;
- }
- } else if (tN > tD) {
- tN = tD;
-
- if ((-d + b) < 0.0)
- sN = 0;
- else if ((-d + b) > a)
- sN = sD;
- else {
- sN = (-d + b);
- sD = a;
- }
- }
-
- sc = (Math::abs(sN) < CMP_EPSILON ? 0.0 : sN / sD);
- tc = (Math::abs(tN) < CMP_EPSILON ? 0.0 : tN / tD);
-
- Vector3 dP = w + (sc * u) - (tc * v);
- return dP.length();
- }
- static inline bool ray_intersects_triangle(const Vector3 &p_from, const Vector3 &p_dir, const Vector3 &p_v0, const Vector3 &p_v1, const Vector3 &p_v2, Vector3 *r_res = 0) {
- Vector3 e1 = p_v1 - p_v0;
- Vector3 e2 = p_v2 - p_v0;
- Vector3 h = p_dir.cross(e2);
- real_t a = e1.dot(h);
- if (a > -CMP_EPSILON && a < CMP_EPSILON)
- return false;
- real_t f = 1.0 / a;
- Vector3 s = p_from - p_v0;
- real_t u = f * s.dot(h);
- if (u < 0.0 || u > 1.0)
- return false;
- Vector3 q = s.cross(e1);
- real_t v = f * p_dir.dot(q);
- if (v < 0.0 || u + v > 1.0)
- return false;
-
-
- real_t t = f * e2.dot(q);
- if (t > 0.00001) {
- if (r_res)
- *r_res = p_from + p_dir * t;
- return true;
- } else
-
- return false;
- }
- static inline bool segment_intersects_triangle(const Vector3 &p_from, const Vector3 &p_to, const Vector3 &p_v0, const Vector3 &p_v1, const Vector3 &p_v2, Vector3 *r_res = 0) {
- Vector3 rel = p_to - p_from;
- Vector3 e1 = p_v1 - p_v0;
- Vector3 e2 = p_v2 - p_v0;
- Vector3 h = rel.cross(e2);
- real_t a = e1.dot(h);
- if (a > -CMP_EPSILON && a < CMP_EPSILON)
- return false;
- real_t f = 1.0 / a;
- Vector3 s = p_from - p_v0;
- real_t u = f * s.dot(h);
- if (u < 0.0 || u > 1.0)
- return false;
- Vector3 q = s.cross(e1);
- real_t v = f * rel.dot(q);
- if (v < 0.0 || u + v > 1.0)
- return false;
-
-
- real_t t = f * e2.dot(q);
- if (t > CMP_EPSILON && t <= 1.0) {
- if (r_res)
- *r_res = p_from + rel * t;
- return true;
- } else
-
- return false;
- }
- static inline bool segment_intersects_sphere(const Vector3 &p_from, const Vector3 &p_to, const Vector3 &p_sphere_pos, real_t p_sphere_radius, Vector3 *r_res = 0, Vector3 *r_norm = 0) {
- Vector3 sphere_pos = p_sphere_pos - p_from;
- Vector3 rel = (p_to - p_from);
- real_t rel_l = rel.length();
- if (rel_l < CMP_EPSILON)
- return false;
- Vector3 normal = rel / rel_l;
- real_t sphere_d = normal.dot(sphere_pos);
-
- real_t ray_distance = sphere_pos.distance_to(normal * sphere_d);
- if (ray_distance >= p_sphere_radius)
- return false;
- real_t inters_d2 = p_sphere_radius * p_sphere_radius - ray_distance * ray_distance;
- real_t inters_d = sphere_d;
- if (inters_d2 >= CMP_EPSILON)
- inters_d -= Math::sqrt(inters_d2);
-
- if (inters_d < 0 || inters_d > rel_l)
- return false;
- Vector3 result = p_from + normal * inters_d;
- if (r_res)
- *r_res = result;
- if (r_norm)
- *r_norm = (result - p_sphere_pos).normalized();
- return true;
- }
- static inline bool segment_intersects_cylinder(const Vector3 &p_from, const Vector3 &p_to, real_t p_height, real_t p_radius, Vector3 *r_res = 0, Vector3 *r_norm = 0) {
- Vector3 rel = (p_to - p_from);
- real_t rel_l = rel.length();
- if (rel_l < CMP_EPSILON)
- return false;
-
- Vector3 normal = (rel / rel_l);
- Vector3 crs = normal.cross(Vector3(0, 0, 1));
- real_t crs_l = crs.length();
- Vector3 z_dir;
- if (crs_l < CMP_EPSILON) {
-
- z_dir = Vector3(1, 0, 0);
- } else {
- z_dir = crs / crs_l;
- }
- real_t dist = z_dir.dot(p_from);
- if (dist >= p_radius)
- return false;
-
- real_t w2 = p_radius * p_radius - dist * dist;
- if (w2 < CMP_EPSILON)
- return false;
- Size2 size(Math::sqrt(w2), p_height * 0.5);
- Vector3 x_dir = z_dir.cross(Vector3(0, 0, 1)).normalized();
- Vector2 from2D(x_dir.dot(p_from), p_from.z);
- Vector2 to2D(x_dir.dot(p_to), p_to.z);
- real_t min = 0, max = 1;
- int axis = -1;
- for (int i = 0; i < 2; i++) {
- real_t seg_from = from2D[i];
- real_t seg_to = to2D[i];
- real_t box_begin = -size[i];
- real_t box_end = size[i];
- real_t cmin, cmax;
- if (seg_from < seg_to) {
- if (seg_from > box_end || seg_to < box_begin)
- return false;
- real_t length = seg_to - seg_from;
- cmin = (seg_from < box_begin) ? ((box_begin - seg_from) / length) : 0;
- cmax = (seg_to > box_end) ? ((box_end - seg_from) / length) : 1;
- } else {
- if (seg_to > box_end || seg_from < box_begin)
- return false;
- real_t length = seg_to - seg_from;
- cmin = (seg_from > box_end) ? (box_end - seg_from) / length : 0;
- cmax = (seg_to < box_begin) ? (box_begin - seg_from) / length : 1;
- }
- if (cmin > min) {
- min = cmin;
- axis = i;
- }
- if (cmax < max)
- max = cmax;
- if (max < min)
- return false;
- }
-
- Vector3 result = p_from + (rel * min);
- Vector3 res_normal = result;
- if (axis == 0) {
- res_normal.z = 0;
- } else {
- res_normal.x = 0;
- res_normal.y = 0;
- }
- res_normal.normalize();
- if (r_res)
- *r_res = result;
- if (r_norm)
- *r_norm = res_normal;
- return true;
- }
- static bool segment_intersects_convex(const Vector3 &p_from, const Vector3 &p_to, const Plane *p_planes, int p_plane_count, Vector3 *p_res, Vector3 *p_norm) {
- real_t min = -1e20, max = 1e20;
- Vector3 rel = p_to - p_from;
- real_t rel_l = rel.length();
- if (rel_l < CMP_EPSILON)
- return false;
- Vector3 dir = rel / rel_l;
- int min_index = -1;
- for (int i = 0; i < p_plane_count; i++) {
- const Plane &p = p_planes[i];
- real_t den = p.normal.dot(dir);
-
- if (Math::abs(den) <= CMP_EPSILON)
- continue;
- real_t dist = -p.distance_to(p_from) / den;
- if (den > 0) {
-
- if (dist < max)
- max = dist;
- } else {
-
- if (dist > min) {
- min = dist;
- min_index = i;
- }
- }
- }
- if (max <= min || min < 0 || min > rel_l || min_index == -1)
- return false;
- if (p_res)
- *p_res = p_from + dir * min;
- if (p_norm)
- *p_norm = p_planes[min_index].normal;
- return true;
- }
- static Vector3 get_closest_point_to_segment(const Vector3 &p_point, const Vector3 *p_segment) {
- Vector3 p = p_point - p_segment[0];
- Vector3 n = p_segment[1] - p_segment[0];
- real_t l = n.length();
- if (l < 1e-10)
- return p_segment[0];
- n /= l;
- real_t d = n.dot(p);
- if (d <= 0.0)
- return p_segment[0];
- else if (d >= l)
- return p_segment[1];
- else
- return p_segment[0] + n * d;
- }
- static Vector3 get_closest_point_to_segment_uncapped(const Vector3 &p_point, const Vector3 *p_segment) {
- Vector3 p = p_point - p_segment[0];
- Vector3 n = p_segment[1] - p_segment[0];
- real_t l = n.length();
- if (l < 1e-10)
- return p_segment[0];
- n /= l;
- real_t d = n.dot(p);
- return p_segment[0] + n * d;
- }
- static Vector2 get_closest_point_to_segment_2d(const Vector2 &p_point, const Vector2 *p_segment) {
- Vector2 p = p_point - p_segment[0];
- Vector2 n = p_segment[1] - p_segment[0];
- real_t l = n.length();
- if (l < 1e-10)
- return p_segment[0];
- n /= l;
- real_t d = n.dot(p);
- if (d <= 0.0)
- return p_segment[0];
- else if (d >= l)
- return p_segment[1];
- else
- return p_segment[0] + n * d;
- }
- static bool is_point_in_triangle(const Vector2 &s, const Vector2 &a, const Vector2 &b, const Vector2 &c) {
- Vector2 an = a - s;
- Vector2 bn = b - s;
- Vector2 cn = c - s;
- bool orientation = an.cross(bn) > 0;
- if ((bn.cross(cn) > 0) != orientation) return false;
- return (cn.cross(an) > 0) == orientation;
- }
- static bool is_point_in_polygon(const Vector2 &p_point, const Vector<Vector2> &p_polygon);
- static Vector2 get_closest_point_to_segment_uncapped_2d(const Vector2 &p_point, const Vector2 *p_segment) {
- Vector2 p = p_point - p_segment[0];
- Vector2 n = p_segment[1] - p_segment[0];
- real_t l = n.length();
- if (l < 1e-10)
- return p_segment[0];
- n /= l;
- real_t d = n.dot(p);
- return p_segment[0] + n * d;
- }
- static bool line_intersects_line_2d(const Vector2 &p_from_a, const Vector2 &p_dir_a, const Vector2 &p_from_b, const Vector2 &p_dir_b, Vector2 &r_result) {
-
- const real_t denom = p_dir_b.y * p_dir_a.x - p_dir_b.x * p_dir_a.y;
- if (Math::abs(denom) < CMP_EPSILON) {
- return false;
- }
- const Vector2 v = p_from_a - p_from_b;
- const real_t t = (p_dir_b.x * v.y - p_dir_b.y * v.x) / denom;
- r_result = p_from_a + t * p_dir_a;
- return true;
- }
- static bool segment_intersects_segment_2d(const Vector2 &p_from_a, const Vector2 &p_to_a, const Vector2 &p_from_b, const Vector2 &p_to_b, Vector2 *r_result) {
- Vector2 B = p_to_a - p_from_a;
- Vector2 C = p_from_b - p_from_a;
- Vector2 D = p_to_b - p_from_a;
- real_t ABlen = B.dot(B);
- if (ABlen <= 0)
- return false;
- Vector2 Bn = B / ABlen;
- C = Vector2(C.x * Bn.x + C.y * Bn.y, C.y * Bn.x - C.x * Bn.y);
- D = Vector2(D.x * Bn.x + D.y * Bn.y, D.y * Bn.x - D.x * Bn.y);
- if ((C.y < 0 && D.y < 0) || (C.y >= 0 && D.y >= 0))
- return false;
- real_t ABpos = D.x + (C.x - D.x) * D.y / (D.y - C.y);
-
- if (ABpos < 0 || ABpos > 1.0)
- return false;
-
- if (r_result)
- *r_result = p_from_a + B * ABpos;
- return true;
- }
- static inline bool point_in_projected_triangle(const Vector3 &p_point, const Vector3 &p_v1, const Vector3 &p_v2, const Vector3 &p_v3) {
- Vector3 face_n = (p_v1 - p_v3).cross(p_v1 - p_v2);
- Vector3 n1 = (p_point - p_v3).cross(p_point - p_v2);
- if (face_n.dot(n1) < 0)
- return false;
- Vector3 n2 = (p_v1 - p_v3).cross(p_v1 - p_point);
- if (face_n.dot(n2) < 0)
- return false;
- Vector3 n3 = (p_v1 - p_point).cross(p_v1 - p_v2);
- if (face_n.dot(n3) < 0)
- return false;
- return true;
- }
- static inline bool triangle_sphere_intersection_test(const Vector3 *p_triangle, const Vector3 &p_normal, const Vector3 &p_sphere_pos, real_t p_sphere_radius, Vector3 &r_triangle_contact, Vector3 &r_sphere_contact) {
- real_t d = p_normal.dot(p_sphere_pos) - p_normal.dot(p_triangle[0]);
- if (d > p_sphere_radius || d < -p_sphere_radius)
- return false;
- Vector3 contact = p_sphere_pos - (p_normal * d);
-
- if (Geometry::point_in_projected_triangle(contact, p_triangle[0], p_triangle[1], p_triangle[2])) {
- r_triangle_contact = contact;
- r_sphere_contact = p_sphere_pos - p_normal * p_sphere_radius;
-
- return true;
- }
-
- const Vector3 verts[4] = { p_triangle[0], p_triangle[1], p_triangle[2], p_triangle[0] };
- for (int i = 0; i < 3; i++) {
-
- Vector3 n1 = verts[i] - verts[i + 1];
- Vector3 n2 = p_sphere_pos - verts[i + 1];
-
-
- Vector3 axis = n1.cross(n2).cross(n1);
- axis.normalize();
- real_t ad = axis.dot(n2);
- if (ABS(ad) > p_sphere_radius) {
-
- continue;
- }
-
-
- real_t sphere_at = n1.dot(n2);
- if (sphere_at >= 0 && sphere_at < n1.dot(n1)) {
- r_triangle_contact = p_sphere_pos - axis * (axis.dot(n2));
- r_sphere_contact = p_sphere_pos - axis * p_sphere_radius;
-
-
- return true;
- }
- real_t r2 = p_sphere_radius * p_sphere_radius;
- if (n2.length_squared() < r2) {
- Vector3 n = (p_sphere_pos - verts[i + 1]).normalized();
-
- r_triangle_contact = verts[i + 1];
- r_sphere_contact = p_sphere_pos - n * p_sphere_radius;
-
- return true;
- }
- if (n2.distance_squared_to(n1) < r2) {
- Vector3 n = (p_sphere_pos - verts[i]).normalized();
-
- r_triangle_contact = verts[i];
- r_sphere_contact = p_sphere_pos - n * p_sphere_radius;
-
- return true;
- }
- break;
- }
- return false;
- }
- static real_t segment_intersects_circle(const Vector2 &p_from, const Vector2 &p_to, const Vector2 &p_circle_pos, real_t p_circle_radius) {
- Vector2 line_vec = p_to - p_from;
- Vector2 vec_to_line = p_from - p_circle_pos;
-
- real_t a, b, c;
- a = line_vec.dot(line_vec);
- b = 2 * vec_to_line.dot(line_vec);
- c = vec_to_line.dot(vec_to_line) - p_circle_radius * p_circle_radius;
-
- real_t sqrtterm = b * b - 4 * a * c;
-
- if (sqrtterm < 0) return -1;
-
- sqrtterm = Math::sqrt(sqrtterm);
- real_t res1 = (-b - sqrtterm) / (2 * a);
-
- return (res1 >= 0 && res1 <= 1) ? res1 : -1;
- }
- static inline Vector<Vector3> clip_polygon(const Vector<Vector3> &polygon, const Plane &p_plane) {
- enum LocationCache {
- LOC_INSIDE = 1,
- LOC_BOUNDARY = 0,
- LOC_OUTSIDE = -1
- };
- if (polygon.size() == 0)
- return polygon;
- int *location_cache = (int *)alloca(sizeof(int) * polygon.size());
- int inside_count = 0;
- int outside_count = 0;
- for (int a = 0; a < polygon.size(); a++) {
-
- real_t dist = p_plane.distance_to(polygon[a]);
- if (dist < -CMP_POINT_IN_PLANE_EPSILON) {
- location_cache[a] = LOC_INSIDE;
- inside_count++;
- } else {
- if (dist > CMP_POINT_IN_PLANE_EPSILON) {
- location_cache[a] = LOC_OUTSIDE;
- outside_count++;
- } else {
- location_cache[a] = LOC_BOUNDARY;
- }
- }
- }
- if (outside_count == 0) {
- return polygon;
- } else if (inside_count == 0) {
- return Vector<Vector3>();
- }
- long previous = polygon.size() - 1;
- Vector<Vector3> clipped;
- for (int index = 0; index < polygon.size(); index++) {
- int loc = location_cache[index];
- if (loc == LOC_OUTSIDE) {
- if (location_cache[previous] == LOC_INSIDE) {
- const Vector3 &v1 = polygon[previous];
- const Vector3 &v2 = polygon[index];
- Vector3 segment = v1 - v2;
- real_t den = p_plane.normal.dot(segment);
- real_t dist = p_plane.distance_to(v1) / den;
- dist = -dist;
- clipped.push_back(v1 + segment * dist);
- }
- } else {
- const Vector3 &v1 = polygon[index];
- if ((loc == LOC_INSIDE) && (location_cache[previous] == LOC_OUTSIDE)) {
- const Vector3 &v2 = polygon[previous];
- Vector3 segment = v1 - v2;
- real_t den = p_plane.normal.dot(segment);
- real_t dist = p_plane.distance_to(v1) / den;
- dist = -dist;
- clipped.push_back(v1 + segment * dist);
- }
- clipped.push_back(v1);
- }
- previous = index;
- }
- return clipped;
- }
- static Vector<int> triangulate_polygon(const Vector<Vector2> &p_polygon) {
- Vector<int> triangles;
- if (!Triangulate::triangulate(p_polygon, triangles))
- return Vector<int>();
- return triangles;
- }
- static Vector<Vector<Vector2> > (*_decompose_func)(const Vector<Vector2> &p_polygon);
- static Vector<Vector<Vector2> > decompose_polygon(const Vector<Vector2> &p_polygon) {
- if (_decompose_func)
- return _decompose_func(p_polygon);
- return Vector<Vector<Vector2> >();
- }
- static bool is_polygon_clockwise(const Vector<Vector2> &p_polygon) {
- int c = p_polygon.size();
- if (c < 3)
- return false;
- const Vector2 *p = p_polygon.ptr();
- real_t sum = 0;
- for (int i = 0; i < c; i++) {
- const Vector2 &v1 = p[i];
- const Vector2 &v2 = p[(i + 1) % c];
- sum += (v2.x - v1.x) * (v2.y + v1.y);
- }
- return sum > 0.0f;
- }
- static PoolVector<PoolVector<Face3> > separate_objects(PoolVector<Face3> p_array);
- static PoolVector<Face3> wrap_geometry(PoolVector<Face3> p_array, real_t *p_error = NULL);
- struct MeshData {
- struct Face {
- Plane plane;
- Vector<int> indices;
- };
- Vector<Face> faces;
- struct Edge {
- int a, b;
- };
- Vector<Edge> edges;
- Vector<Vector3> vertices;
- void optimize_vertices();
- };
- _FORCE_INLINE_ static int get_uv84_normal_bit(const Vector3 &p_vector) {
- int lat = Math::fast_ftoi(Math::floor(Math::acos(p_vector.dot(Vector3(0, 1, 0))) * 4.0 / Math_PI + 0.5));
- if (lat == 0) {
- return 24;
- } else if (lat == 4) {
- return 25;
- }
- int lon = Math::fast_ftoi(Math::floor((Math_PI + Math::atan2(p_vector.x, p_vector.z)) * 8.0 / (Math_PI * 2.0) + 0.5)) % 8;
- return lon + (lat - 1) * 8;
- }
- _FORCE_INLINE_ static int get_uv84_normal_bit_neighbors(int p_idx) {
- if (p_idx == 24) {
- return 1 | 2 | 4 | 8;
- } else if (p_idx == 25) {
- return (1 << 23) | (1 << 22) | (1 << 21) | (1 << 20);
- } else {
- int ret = 0;
- if ((p_idx % 8) == 0)
- ret |= (1 << (p_idx + 7));
- else
- ret |= (1 << (p_idx - 1));
- if ((p_idx % 8) == 7)
- ret |= (1 << (p_idx - 7));
- else
- ret |= (1 << (p_idx + 1));
- int mask = ret | (1 << p_idx);
- if (p_idx < 8)
- ret |= 24;
- else
- ret |= mask >> 8;
- if (p_idx >= 16)
- ret |= 25;
- else
- ret |= mask << 8;
- return ret;
- }
- }
- static real_t vec2_cross(const Point2 &O, const Point2 &A, const Point2 &B) {
- return (real_t)(A.x - O.x) * (B.y - O.y) - (real_t)(A.y - O.y) * (B.x - O.x);
- }
-
-
- static Vector<Point2> convex_hull_2d(Vector<Point2> P) {
- int n = P.size(), k = 0;
- Vector<Point2> H;
- H.resize(2 * n);
-
- P.sort();
-
- for (int i = 0; i < n; ++i) {
- while (k >= 2 && vec2_cross(H[k - 2], H[k - 1], P[i]) <= 0)
- k--;
- H.write[k++] = P[i];
- }
-
- for (int i = n - 2, t = k + 1; i >= 0; i--) {
- while (k >= t && vec2_cross(H[k - 2], H[k - 1], P[i]) <= 0)
- k--;
- H.write[k++] = P[i];
- }
- H.resize(k);
- return H;
- }
- static MeshData build_convex_mesh(const PoolVector<Plane> &p_planes);
- static PoolVector<Plane> build_sphere_planes(real_t p_radius, int p_lats, int p_lons, Vector3::Axis p_axis = Vector3::AXIS_Z);
- static PoolVector<Plane> build_box_planes(const Vector3 &p_extents);
- static PoolVector<Plane> build_cylinder_planes(real_t p_radius, real_t p_height, int p_sides, Vector3::Axis p_axis = Vector3::AXIS_Z);
- static PoolVector<Plane> build_capsule_planes(real_t p_radius, real_t p_height, int p_sides, int p_lats, Vector3::Axis p_axis = Vector3::AXIS_Z);
- static void make_atlas(const Vector<Size2i> &p_rects, Vector<Point2i> &r_result, Size2i &r_size);
- };
- #endif
|