e
, e->halfedge(->twin)^n
is a cycle of exactly two halfedges, and these are exactly the halfedges with h->edge
equal to e
.f
, f->halfedge(->next)^n
is a cycle of at least three halfedges, and these are exactly the halfedges with h->face
equal to f
.v
, v->halfedge(->twin->next)^n
is a cycle of at least two halfedges, and these are exactly the halfedges with h->vertex
equal to v
.
int32_t orientation(Vec2 p, Vec2 q, Vec2 v) {
float o = (p.y - q.y) * (q.x - v.x) - (q.y - v.y) * (p.x - q.x);
if (o > 0.f) { return 1;
} else if (o < 0.f) { return -1;
} else { return 0; }
}
bool biased_in_between(Vec2 p, Vec2 q, Vec2 v, bool q_inline, bool p_inline) {
float pvN = (v - p).norm_squared();
float vqN = (q - v).norm_squared();
float pqN = (q - p).norm_squared();
if (p_inline && q_inline) { return pqN >= pvN && pqN >= vqN;
} else if (p_inline && !q_inline) { return pqN >= pvN && pqN > vqN;
} else if (!p_inline && q_inline) { return pqN > pvN && pqN >= vqN;
} else { eturn pqN > pvN && pqN > vqN; }
}
bool line_intersection(Vec2 va, Vec2 vb, Vec2 ua, Vec2 ub) {
int32_t o1 = orientation(va, vb, ua);
int32_t o2 = orientation(va, vb, ub);
int32_t o3 = orientation(ua, ub, va);
int32_t o4 = orientation(ua, ub, vb);
if (o1 != o2 && o3 != o4) return true;
// colinear cases
if (o1 == 0 && biased_in_between(va, vb, ua, true, true)) return true;
if (o2 == 0 && biased_in_between(va, vb, ub, true, true)) return true;
if (o3 == 0 && biased_in_between(ua, ub, va, true, true)) return true;
if (o4 == 0 && biased_in_between(ua, ub, vb, true, true)) return true;
return false;
}
float triangle_screen_times_two(Vec2 va, Vec2 vb, Vec2 vc) {
Vec2 edge1 = vb - va;
Vec2 edge2 = vc - va;
return cross(Vec3(edge1, 0.0f), Vec3(edge2, 0.0f)).norm();
}
Vec3 barycentric_coordinate(Vec2 x, Vec2 va, Vec2 vb, Vec2 vc) {
float nominator_a = triangle_screen_times_two(x, vb, vc);
float nominator_b = triangle_screen_times_two(va, x, vc);
float nominator_c = triangle_screen_times_two(va, vb, x);
return Vec3(nominator_a, nominator_b, nominator_c) /
triangle_screen_times_two(va, vb, vc);
}
float barycentric_interpolate_2D(Vec3 barycentric, float va, float vb,
float vc) {
return dot(Vec3(va, vb, vc), barycentric);
}
float z =
1.0f / barycentric_interpolate_2D(barycentric, a.inv_w, b.inv_w, c.inv_w);
frag.attributes[i] =
z * barycentric_interpolate_2D(barycentric, a.attributes[i] * a.inv_w,
b.attributes[i] * b.inv_w,
c.attributes[i] * c.inv_w);
Table of Content