203 lines
8.1 KiB
C++
203 lines
8.1 KiB
C++
#pragma once
|
|
|
|
#include "diffvg.h"
|
|
#include "scene.h"
|
|
#include "shape.h"
|
|
#include "solve.h"
|
|
#include "vector.h"
|
|
|
|
DEVICE
|
|
int compute_winding_number(const Circle &circle, const Vector2f &pt) {
|
|
const auto &c = circle.center;
|
|
auto r = circle.radius;
|
|
// inside the circle: return 1, outside the circle: return 0
|
|
if (distance_squared(c, pt) < r * r) {
|
|
return 1;
|
|
} else {
|
|
return 0;
|
|
}
|
|
}
|
|
|
|
DEVICE
|
|
int compute_winding_number(const Ellipse &ellipse, const Vector2f &pt) {
|
|
const auto &c = ellipse.center;
|
|
const auto &r = ellipse.radius;
|
|
// inside the ellipse: return 1, outside the ellipse: return 0
|
|
if (square(c.x - pt.x) / square(r.x) + square(c.y - pt.y) / square(r.y) < 1) {
|
|
return 1;
|
|
} else {
|
|
return 0;
|
|
}
|
|
}
|
|
|
|
DEVICE
|
|
bool intersect(const AABB &box, const Vector2f &pt) {
|
|
if (pt.y < box.p_min.y || pt.y > box.p_max.y) {
|
|
return false;
|
|
}
|
|
if (pt.x > box.p_max.x) {
|
|
return false;
|
|
}
|
|
return true;
|
|
}
|
|
|
|
DEVICE
|
|
int compute_winding_number(const Path &path, const BVHNode *bvh_nodes, const Vector2f &pt) {
|
|
// Shoot a horizontal ray from pt to right, intersect with all curves of the path,
|
|
// count intersection
|
|
auto num_segments = path.num_base_points;
|
|
constexpr auto max_bvh_size = 128;
|
|
int bvh_stack[max_bvh_size];
|
|
auto stack_size = 0;
|
|
auto winding_number = 0;
|
|
bvh_stack[stack_size++] = 2 * num_segments - 2;
|
|
while (stack_size > 0) {
|
|
const BVHNode &node = bvh_nodes[bvh_stack[--stack_size]];
|
|
if (node.child1 < 0) {
|
|
// leaf
|
|
auto base_point_id = node.child0;
|
|
auto point_id = - node.child1 - 1;
|
|
assert(base_point_id < num_segments);
|
|
assert(point_id < path.num_points);
|
|
if (path.num_control_points[base_point_id] == 0) {
|
|
// Straight line
|
|
auto i0 = point_id;
|
|
auto i1 = (point_id + 1) % path.num_points;
|
|
auto p0 = Vector2f{path.points[2 * i0], path.points[2 * i0 + 1]};
|
|
auto p1 = Vector2f{path.points[2 * i1], path.points[2 * i1 + 1]};
|
|
// intersect p0 + t * (p1 - p0) with pt + t' * (1, 0)
|
|
// solve:
|
|
// pt.x + t' = v0.x + t * (v1.x - v0.x)
|
|
// pt.y = v0.y + t * (v1.y - v0.y)
|
|
if (p1.y != p0.y) {
|
|
auto t = (pt.y - p0.y) / (p1.y - p0.y);
|
|
if (t >= 0 && t <= 1) {
|
|
auto tp = p0.x - pt.x + t * (p1.x - p0.x);
|
|
if (tp >= 0) {
|
|
if (p1.y - p0.y > 0) {
|
|
winding_number += 1;
|
|
} else {
|
|
winding_number -= 1;
|
|
}
|
|
}
|
|
}
|
|
}
|
|
} else if (path.num_control_points[base_point_id] == 1) {
|
|
// Quadratic Bezier curve
|
|
auto i0 = point_id;
|
|
auto i1 = point_id + 1;
|
|
auto i2 = (point_id + 2) % path.num_points;
|
|
auto p0 = Vector2f{path.points[2 * i0], path.points[2 * i0 + 1]};
|
|
auto p1 = Vector2f{path.points[2 * i1], path.points[2 * i1 + 1]};
|
|
auto p2 = Vector2f{path.points[2 * i2], path.points[2 * i2 + 1]};
|
|
// The curve is (1-t)^2p0 + 2(1-t)tp1 + t^2p2
|
|
// = (p0-2p1+p2)t^2+(-2p0+2p1)t+p0
|
|
// intersect with pt + t' * (1 0)
|
|
// solve
|
|
// pt.y = (p0-2p1+p2)t^2+(-2p0+2p1)t+p0
|
|
float t[2];
|
|
if (solve_quadratic(p0.y-2*p1.y+p2.y,
|
|
-2*p0.y+2*p1.y,
|
|
p0.y-pt.y,
|
|
&t[0], &t[1])) {
|
|
for (int j = 0; j < 2; j++) {
|
|
if (t[j] >= 0 && t[j] <= 1) {
|
|
auto tp = (p0.x-2*p1.x+p2.x)*t[j]*t[j] +
|
|
(-2*p0.x+2*p1.x)*t[j] +
|
|
p0.x-pt.x;
|
|
if (tp >= 0) {
|
|
if (2*(p0.y-2*p1.y+p2.y)*t[j]+(-2*p0.y+2*p1.y) > 0) {
|
|
winding_number += 1;
|
|
} else {
|
|
winding_number -= 1;
|
|
}
|
|
}
|
|
}
|
|
}
|
|
}
|
|
} else if (path.num_control_points[base_point_id] == 2) {
|
|
// Cubic Bezier curve
|
|
auto i0 = point_id;
|
|
auto i1 = point_id + 1;
|
|
auto i2 = point_id + 2;
|
|
auto i3 = (point_id + 3) % path.num_points;
|
|
auto p0 = Vector2f{path.points[2 * i0], path.points[2 * i0 + 1]};
|
|
auto p1 = Vector2f{path.points[2 * i1], path.points[2 * i1 + 1]};
|
|
auto p2 = Vector2f{path.points[2 * i2], path.points[2 * i2 + 1]};
|
|
auto p3 = Vector2f{path.points[2 * i3], path.points[2 * i3 + 1]};
|
|
// The curve is (1 - t)^3 p0 + 3 * (1 - t)^2 t p1 + 3 * (1 - t) t^2 p2 + t^3 p3
|
|
// = (-p0+3p1-3p2+p3) t^3 + (3p0-6p1+3p2) t^2 + (-3p0+3p1) t + p0
|
|
// intersect with pt + t' * (1 0)
|
|
// solve:
|
|
// pt.y = (-p0+3p1-3p2+p3) t^3 + (3p0-6p1+3p2) t^2 + (-3p0+3p1) t + p0
|
|
double t[3];
|
|
int num_sol = solve_cubic(double(-p0.y+3*p1.y-3*p2.y+p3.y),
|
|
double(3*p0.y-6*p1.y+3*p2.y),
|
|
double(-3*p0.y+3*p1.y),
|
|
double(p0.y-pt.y),
|
|
t);
|
|
for (int j = 0; j < num_sol; j++) {
|
|
if (t[j] >= 0 && t[j] <= 1) {
|
|
// t' = (-p0+3p1-3p2+p3) t^3 + (3p0-6p1+3p2) t^2 + (-3p0+3p1) t + p0 - pt.x
|
|
auto tp = (-p0.x+3*p1.x-3*p2.x+p3.x)*t[j]*t[j]*t[j]+
|
|
(3*p0.x-6*p1.x+3*p2.x)*t[j]*t[j]+
|
|
(-3*p0.x+3*p1.x)*t[j]+
|
|
p0.x-pt.x;
|
|
if (tp > 0) {
|
|
if (3*(-p0.y+3*p1.y-3*p2.y+p3.y)*t[j]*t[j]+
|
|
2*(3*p0.y-6*p1.y+3*p2.y)*t[j]+
|
|
(-3*p0.y+3*p1.y) > 0) {
|
|
winding_number += 1;
|
|
} else {
|
|
winding_number -= 1;
|
|
}
|
|
}
|
|
}
|
|
}
|
|
} else {
|
|
assert(false);
|
|
}
|
|
} else {
|
|
assert(node.child0 >= 0 && node.child1 >= 0);
|
|
const AABB &b0 = bvh_nodes[node.child0].box;
|
|
if (intersect(b0, pt)) {
|
|
bvh_stack[stack_size++] = node.child0;
|
|
}
|
|
const AABB &b1 = bvh_nodes[node.child1].box;
|
|
if (intersect(b1, pt)) {
|
|
bvh_stack[stack_size++] = node.child1;
|
|
}
|
|
assert(stack_size <= max_bvh_size);
|
|
}
|
|
}
|
|
return winding_number;
|
|
}
|
|
|
|
DEVICE
|
|
int compute_winding_number(const Rect &rect, const Vector2f &pt) {
|
|
const auto &p_min = rect.p_min;
|
|
const auto &p_max = rect.p_max;
|
|
// inside the rectangle: return 1, outside the rectangle: return 0
|
|
if (pt.x > p_min.x && pt.x < p_max.x && pt.y > p_min.y && pt.y < p_max.y) {
|
|
return 1;
|
|
} else {
|
|
return 0;
|
|
}
|
|
}
|
|
|
|
DEVICE
|
|
int compute_winding_number(const Shape &shape, const BVHNode *bvh_nodes, const Vector2f &pt) {
|
|
switch (shape.type) {
|
|
case ShapeType::Circle:
|
|
return compute_winding_number(*(const Circle *)shape.ptr, pt);
|
|
case ShapeType::Ellipse:
|
|
return compute_winding_number(*(const Ellipse *)shape.ptr, pt);
|
|
case ShapeType::Path:
|
|
return compute_winding_number(*(const Path *)shape.ptr, bvh_nodes, pt);
|
|
case ShapeType::Rect:
|
|
return compute_winding_number(*(const Rect *)shape.ptr, pt);
|
|
}
|
|
assert(false);
|
|
return 0;
|
|
}
|