49 #define SF_EPSILON 0.00003f
50 #define SF_EPSILON_SQ (SF_EPSILON * SF_EPSILON)
54 #define SF_VERT_AVAILABLE 1
55 #define SF_VERT_ZERO_LEN 2
62 #define SF_EDGE_INTERNAL 2
66 #define SF_POLY_VALID 1
74 if (x1->
vert->
xy[1] <
x2->vert->xy[1]) {
77 if (x1->
vert->
xy[1] >
x2->vert->xy[1]) {
80 if (x1->
vert->
xy[0] >
x2->vert->xy[0]) {
83 if (x1->
vert->
xy[0] <
x2->vert->xy[0]) {
90 static int vergpoly(
const void *a1,
const void *a2)
100 if (x1->
min_xy[1] >
x2->min_xy[1]) {
103 if (x1->
min_xy[1] <
x2->min_xy[1]) {
174 if (pf1->
edges == 0 ||
pf2->edges == 0) {
231 pf2->verts =
pf2->edges = 0;
232 pf1->
f = (pf1->
f |
pf2->f);
240 inp = (
v2[0] -
v1[0]) * (
v1[1] - v3[1]) + (
v1[1] -
v2[1]) * (
v1[0] - v3[0]);
246 if (
v1[0] == v3[0] &&
v1[1] == v3[1]) {
249 if (
v2[0] == v3[0] &&
v2[1] == v3[1]) {
260 float fac, fac1,
x,
y;
271 fac1 = eed->
v2->
xy[1] -
y;
273 fac1 = 1.0e10f * (eed->
v2->
xy[0] -
x);
276 fac1 = (
x - eed->
v2->
xy[0]) / fac1;
281 if (ed->
v2 == eed->
v2) {
285 fac = ed->
v2->
xy[1] -
y;
287 fac = 1.0e10f * (ed->
v2->
xy[0] -
x);
290 fac = (
x - ed->
v2->
xy[0]) / fac;
317 if (eed->
v1->
xy[1] == eed->
v2->
xy[1]) {
318 if (eed->
v1->
xy[0] > eed->
v2->
xy[0]) {
324 else if (eed->
v1->
xy[1] < eed->
v2->
xy[1]) {
334 printf(
"Error in search edge: %p\n", (
void *)eed);
348 float minx, maxx, miny, maxy;
350 if (eed->
v1->
xy[0] < eed->
v2->
xy[0]) {
351 minx = eed->
v1->
xy[0];
352 maxx = eed->
v2->
xy[0];
355 minx = eed->
v2->
xy[0];
356 maxx = eed->
v1->
xy[0];
358 if (eve->
xy[0] >= minx && eve->
xy[0] <= maxx) {
359 if (eed->
v1->
xy[1] < eed->
v2->
xy[1]) {
360 miny = eed->
v1->
xy[1];
361 maxy = eed->
v2->
xy[1];
364 miny = eed->
v2->
xy[1];
365 maxy = eed->
v1->
xy[1];
367 if (eve->
xy[1] >= miny && eve->
xy[1] <= maxy) {
392 if (ed1->
v1 == eve) {
443 for (eve = tempve->
first; eve; eve = eve_next) {
444 eve_next = eve->
next;
451 for (eed = temped->
first; eed; eed = eed_next) {
452 eed_next = eed->
next;
466 unsigned int a,
b,
verts, maxface, totface;
467 const unsigned short nr =
pf->nr;
468 bool twoconnected =
false;
474 printf(
"vert: %x co: %f %f\n", eve, eve->
xy[0], eve->
xy[1]);
478 printf(
"edge: %x verts: %x %x\n", eed, eed->
v1, eed->
v2);
508 sc = scdata =
MEM_mallocN(
sizeof(*scdata) *
pf->verts,
"Scanfill1");
528 eed_next = eed->
next;
553 if (eed->
v1 != eed->
v2) {
560 eed_next = eed->
next;
562 if (eed->
v1 != eed->
v2) {
568 sc = sf_ctx->_scdata;
570 printf(
"\nscvert: %x\n", sc->
vert);
572 printf(
" ed %x %x %x\n", eed, eed->
v1, eed->
v2);
598 for (ed1 = sc->
edge_first; ed1; ed1 = eed_next) {
599 eed_next = ed1->
next;
621 if (totface >= maxface) {
637 float angle_best_cos = -1.0f;
639 bool firsttime =
false;
646 if (
v1 ==
v2 ||
v2 == v3) {
656 if (sc1->vert->xy[1] <= miny) {
667 if (best_sc ==
NULL) {
674 if (firsttime ==
false) {
679 const float angle_test_cos =
cos_v2v2v2(
v2->xy,
v1->xy, sc1->vert->xy);
680 if (angle_test_cos > angle_best_cos) {
682 angle_best_cos = angle_test_cos;
737 for (ed3 = sc1->edge_first; ed3; ed3 = ed3->
next) {
738 if ((ed3->
v1 ==
v1 && ed3->
v2 == v3) || (ed3->
v1 == v3 && ed3->
v2 ==
v1)) {
753 for (ed1 = sc->
edge_first; ed1; ed1 = eed_next) {
754 eed_next = ed1->
next;
781 memset(sf_ctx, 0,
sizeof(*sf_ctx));
788 memset(sf_ctx, 0,
sizeof(*sf_ctx));
790 sf_ctx->
arena = arena;
827 float *min_xy_p, *max_xy_p;
828 unsigned int totfaces = 0;
829 unsigned short a,
c, poly = 0;
898 poly = (
unsigned short)(sf_ctx->
poly_nr + 1);
908 unsigned int toggle = 0;
919 eed = (toggle & 1) ? eed->
next : eed->
prev) {
965 unsigned int toggle = 0;
977 printf(
"No vertices with 250 edges allowed!\n");
992 eed_next = (toggle & 1) ? eed->
next : eed->
prev;
1038 pflist =
MEM_mallocN(
sizeof(*pflist) * (
size_t)poly,
"edgefill");
1040 for (
a = 0;
a < poly;
a++) {
1041 pf->edges =
pf->verts = 0;
1042 pf->min_xy[0] =
pf->min_xy[1] = 1.0e20f;
1043 pf->max_xy[0] =
pf->max_xy[1] = -1.0e20f;
1057 min_xy_p[0] = (min_xy_p[0]) < (eve->
xy[0]) ? (min_xy_p[0]) : (eve->
xy[0]);
1058 min_xy_p[1] = (min_xy_p[1]) < (eve->
xy[1]) ? (min_xy_p[1]) : (eve->
xy[1]);
1059 max_xy_p[0] = (max_xy_p[0]) > (eve->
xy[0]) ? (max_xy_p[0]) : (eve->
xy[0]);
1060 max_xy_p[1] = (max_xy_p[1]) > (eve->
xy[1]) ? (max_xy_p[1]) : (eve->
xy[1]);
1072 unsigned short *polycache, *pc;
1079 for (
a = 0;
a < poly;
a++) {
1080 printf(
"poly:%d edges:%d verts:%d flag: %d\n",
a,
pf->edges,
pf->verts,
pf->f);
1081 PRINT2(f, f,
pf->min[0],
pf->min[1]);
1086 polycache = pc =
MEM_callocN(
sizeof(*polycache) * (
size_t)poly,
"polycache");
1088 for (
a = 0;
a < poly;
a++,
pf++) {
1089 for (
c = (
unsigned short)(
a + 1);
c < poly;
c++) {
1101 while (pc != polycache) {
1110 printf(
"after merge\n");
1112 for (
a = 0;
a < poly;
a++) {
1113 printf(
"poly:%d edges:%d verts:%d flag: %d\n",
a,
pf->edges,
pf->verts,
pf->f);
1128 for (
a = 0;
a < poly;
a++) {
1129 if (
pf->edges > 1) {
BLI_INLINE bool BLI_listbase_is_empty(const struct ListBase *lb)
BLI_INLINE void BLI_listbase_clear(struct ListBase *lb)
void void void BLI_movelisttolist(struct ListBase *dst, struct ListBase *src) ATTR_NONNULL(1
void BLI_addtail(struct ListBase *listbase, void *vlink) ATTR_NONNULL(1)
void BLI_remlink(struct ListBase *listbase, void *vlink) ATTR_NONNULL(1)
void BLI_insertlinkbefore(struct ListBase *listbase, void *vnextlink, void *vnewlink) ATTR_NONNULL(1)
MINLINE float min_ff(float a, float b)
void axis_dominant_v3_to_m3_negate(float r_mat[3][3], const float normal[3])
float dist_squared_to_line_v2(const float p[2], const float l1[2], const float l2[2])
void mul_v2_m3v3(float r[2], const float M[3][3], const float a[3])
MINLINE bool compare_v3v3(const float a[3], const float b[3], float limit) ATTR_WARN_UNUSED_RESULT
MINLINE float len_squared_v3(const float v[3]) ATTR_WARN_UNUSED_RESULT
MINLINE float normalize_v3(float r[3])
MINLINE void add_newell_cross_v3_v3v3(float n[3], const float v_prev[3], const float v_curr[3])
MINLINE void copy_v3_v3(float r[3], const float a[3])
float cos_v2v2v2(const float p1[2], const float p2[2], const float p3[2]) ATTR_WARN_UNUSED_RESULT
MINLINE bool compare_v2v2(const float a[2], const float b[2], float limit) ATTR_WARN_UNUSED_RESULT
MINLINE bool equals_v2v2(const float v1[2], const float v2[2]) ATTR_WARN_UNUSED_RESULT
MINLINE void zero_v2(float r[2])
MINLINE void zero_v3(float r[3])
void BLI_memarena_free(struct MemArena *ma) ATTR_NONNULL(1)
struct MemArena * BLI_memarena_new(size_t bufsize, const char *name) ATTR_WARN_UNUSED_RESULT ATTR_RETURNS_NONNULL ATTR_NONNULL(2) ATTR_MALLOC
void * BLI_memarena_alloc(struct MemArena *ma, size_t size) ATTR_WARN_UNUSED_RESULT ATTR_NONNULL(1) ATTR_MALLOC ATTR_ALLOC_SIZE(2)
void void BLI_memarena_clear(MemArena *ma) ATTR_NONNULL(1)
#define BLI_SCANFILL_ARENA_SIZE
@ BLI_SCANFILL_CALC_LOOSE
@ BLI_SCANFILL_CALC_POLYS
@ BLI_SCANFILL_CALC_HOLES
@ BLI_SCANFILL_CALC_REMOVE_DOUBLES
Strict compiler flags for areas of code we want to ensure don't do conversions without us knowing abo...
_GL_VOID GLfloat value _GL_VOID_RET _GL_VOID const GLuint GLboolean *residences _GL_BOOL_RET _GL_VOID GLsizei GLfloat GLfloat GLfloat GLfloat const GLubyte *bitmap _GL_VOID_RET _GL_VOID GLenum const void *lists _GL_VOID_RET _GL_VOID const GLdouble *equation _GL_VOID_RET _GL_VOID GLdouble GLdouble blue _GL_VOID_RET _GL_VOID GLfloat GLfloat blue _GL_VOID_RET _GL_VOID GLint GLint blue _GL_VOID_RET _GL_VOID GLshort GLshort blue _GL_VOID_RET _GL_VOID GLubyte GLubyte blue _GL_VOID_RET _GL_VOID GLuint GLuint blue _GL_VOID_RET _GL_VOID GLushort GLushort blue _GL_VOID_RET _GL_VOID GLbyte GLbyte GLbyte alpha _GL_VOID_RET _GL_VOID GLdouble GLdouble GLdouble alpha _GL_VOID_RET _GL_VOID GLfloat GLfloat GLfloat alpha _GL_VOID_RET _GL_VOID GLint GLint GLint alpha _GL_VOID_RET _GL_VOID GLshort GLshort GLshort alpha _GL_VOID_RET _GL_VOID GLubyte GLubyte GLubyte alpha _GL_VOID_RET _GL_VOID GLuint GLuint GLuint alpha _GL_VOID_RET _GL_VOID GLushort GLushort GLushort alpha _GL_VOID_RET _GL_VOID GLenum mode _GL_VOID_RET _GL_VOID GLint y
_GL_VOID GLfloat value _GL_VOID_RET _GL_VOID const GLuint GLboolean *residences _GL_BOOL_RET _GL_VOID GLsizei GLfloat GLfloat GLfloat GLfloat const GLubyte *bitmap _GL_VOID_RET _GL_VOID GLenum const void *lists _GL_VOID_RET _GL_VOID const GLdouble *equation _GL_VOID_RET _GL_VOID GLdouble GLdouble blue _GL_VOID_RET _GL_VOID GLfloat GLfloat blue _GL_VOID_RET _GL_VOID GLint GLint blue _GL_VOID_RET _GL_VOID GLshort GLshort blue _GL_VOID_RET _GL_VOID GLubyte GLubyte blue _GL_VOID_RET _GL_VOID GLuint GLuint blue _GL_VOID_RET _GL_VOID GLushort GLushort blue _GL_VOID_RET _GL_VOID GLbyte GLbyte GLbyte alpha _GL_VOID_RET _GL_VOID GLdouble GLdouble GLdouble alpha _GL_VOID_RET _GL_VOID GLfloat GLfloat GLfloat alpha _GL_VOID_RET _GL_VOID GLint GLint GLint alpha _GL_VOID_RET _GL_VOID GLshort GLshort GLshort alpha _GL_VOID_RET _GL_VOID GLubyte GLubyte GLubyte alpha _GL_VOID_RET _GL_VOID GLuint GLuint GLuint alpha _GL_VOID_RET _GL_VOID GLushort GLushort GLushort alpha _GL_VOID_RET _GL_VOID GLenum mode _GL_VOID_RET _GL_VOID GLint GLsizei GLsizei GLenum type _GL_VOID_RET _GL_VOID GLsizei GLenum GLenum const void *pixels _GL_VOID_RET _GL_VOID const void *pointer _GL_VOID_RET _GL_VOID GLdouble v _GL_VOID_RET _GL_VOID GLfloat v _GL_VOID_RET _GL_VOID GLint GLint i2 _GL_VOID_RET _GL_VOID GLint j _GL_VOID_RET _GL_VOID GLfloat param _GL_VOID_RET _GL_VOID GLint param _GL_VOID_RET _GL_VOID GLdouble GLdouble GLdouble GLdouble GLdouble zFar _GL_VOID_RET _GL_UINT GLdouble *equation _GL_VOID_RET _GL_VOID GLenum GLint *params _GL_VOID_RET _GL_VOID GLenum GLfloat *v _GL_VOID_RET _GL_VOID GLenum GLfloat *params _GL_VOID_RET _GL_VOID GLfloat *values _GL_VOID_RET _GL_VOID GLushort *values _GL_VOID_RET _GL_VOID GLenum GLfloat *params _GL_VOID_RET _GL_VOID GLenum GLdouble *params _GL_VOID_RET _GL_VOID GLenum GLint *params _GL_VOID_RET _GL_VOID GLsizei const void *pointer _GL_VOID_RET _GL_VOID GLsizei const void *pointer _GL_VOID_RET _GL_BOOL GLfloat param _GL_VOID_RET _GL_VOID GLint param _GL_VOID_RET _GL_VOID GLenum GLfloat param _GL_VOID_RET _GL_VOID GLenum GLint param _GL_VOID_RET _GL_VOID GLushort pattern _GL_VOID_RET _GL_VOID GLdouble GLdouble GLint GLint const GLdouble *points _GL_VOID_RET _GL_VOID GLdouble GLdouble GLint GLint GLdouble GLdouble GLint GLint const GLdouble *points _GL_VOID_RET _GL_VOID GLdouble GLdouble u2 _GL_VOID_RET _GL_VOID GLdouble GLdouble GLint GLdouble GLdouble v2 _GL_VOID_RET _GL_VOID GLenum GLfloat param _GL_VOID_RET _GL_VOID GLenum GLint param _GL_VOID_RET _GL_VOID GLenum mode _GL_VOID_RET _GL_VOID GLdouble GLdouble nz _GL_VOID_RET _GL_VOID GLfloat GLfloat nz _GL_VOID_RET _GL_VOID GLint GLint nz _GL_VOID_RET _GL_VOID GLshort GLshort nz _GL_VOID_RET _GL_VOID GLsizei const void *pointer _GL_VOID_RET _GL_VOID GLsizei const GLfloat *values _GL_VOID_RET _GL_VOID GLsizei const GLushort *values _GL_VOID_RET _GL_VOID GLint param _GL_VOID_RET _GL_VOID const GLuint const GLclampf *priorities _GL_VOID_RET _GL_VOID GLdouble y _GL_VOID_RET _GL_VOID GLfloat y _GL_VOID_RET _GL_VOID GLint y _GL_VOID_RET _GL_VOID GLshort y _GL_VOID_RET _GL_VOID GLdouble GLdouble z _GL_VOID_RET _GL_VOID GLfloat GLfloat z _GL_VOID_RET _GL_VOID GLint GLint z _GL_VOID_RET _GL_VOID GLshort GLshort z _GL_VOID_RET _GL_VOID GLdouble GLdouble GLdouble w _GL_VOID_RET _GL_VOID GLfloat GLfloat GLfloat w _GL_VOID_RET _GL_VOID GLint GLint GLint w _GL_VOID_RET _GL_VOID GLshort GLshort GLshort w _GL_VOID_RET _GL_VOID GLdouble GLdouble x2
_GL_VOID GLfloat value _GL_VOID_RET _GL_VOID const GLuint GLboolean *residences _GL_BOOL_RET _GL_VOID GLsizei GLfloat GLfloat GLfloat GLfloat const GLubyte *bitmap _GL_VOID_RET _GL_VOID GLenum const void *lists _GL_VOID_RET _GL_VOID const GLdouble *equation _GL_VOID_RET _GL_VOID GLdouble GLdouble blue _GL_VOID_RET _GL_VOID GLfloat GLfloat blue _GL_VOID_RET _GL_VOID GLint GLint blue _GL_VOID_RET _GL_VOID GLshort GLshort blue _GL_VOID_RET _GL_VOID GLubyte GLubyte blue _GL_VOID_RET _GL_VOID GLuint GLuint blue _GL_VOID_RET _GL_VOID GLushort GLushort blue _GL_VOID_RET _GL_VOID GLbyte GLbyte GLbyte alpha _GL_VOID_RET _GL_VOID GLdouble GLdouble GLdouble alpha _GL_VOID_RET _GL_VOID GLfloat GLfloat GLfloat alpha _GL_VOID_RET _GL_VOID GLint GLint GLint alpha _GL_VOID_RET _GL_VOID GLshort GLshort GLshort alpha _GL_VOID_RET _GL_VOID GLubyte GLubyte GLubyte alpha _GL_VOID_RET _GL_VOID GLuint GLuint GLuint alpha _GL_VOID_RET _GL_VOID GLushort GLushort GLushort alpha _GL_VOID_RET _GL_VOID GLenum mode _GL_VOID_RET _GL_VOID GLint GLsizei GLsizei GLenum type _GL_VOID_RET _GL_VOID GLsizei GLenum GLenum const void *pixels _GL_VOID_RET _GL_VOID const void *pointer _GL_VOID_RET _GL_VOID GLdouble v _GL_VOID_RET _GL_VOID GLfloat v _GL_VOID_RET _GL_VOID GLint GLint i2 _GL_VOID_RET _GL_VOID GLint j _GL_VOID_RET _GL_VOID GLfloat param _GL_VOID_RET _GL_VOID GLint param _GL_VOID_RET _GL_VOID GLdouble GLdouble GLdouble GLdouble GLdouble zFar _GL_VOID_RET _GL_UINT GLdouble *equation _GL_VOID_RET _GL_VOID GLenum GLint *params _GL_VOID_RET _GL_VOID GLenum GLfloat *v _GL_VOID_RET _GL_VOID GLenum GLfloat *params _GL_VOID_RET _GL_VOID GLfloat *values _GL_VOID_RET _GL_VOID GLushort *values _GL_VOID_RET _GL_VOID GLenum GLfloat *params _GL_VOID_RET _GL_VOID GLenum GLdouble *params _GL_VOID_RET _GL_VOID GLenum GLint *params _GL_VOID_RET _GL_VOID GLsizei const void *pointer _GL_VOID_RET _GL_VOID GLsizei const void *pointer _GL_VOID_RET _GL_BOOL GLfloat param _GL_VOID_RET _GL_VOID GLint param _GL_VOID_RET _GL_VOID GLenum GLfloat param _GL_VOID_RET _GL_VOID GLenum GLint param _GL_VOID_RET _GL_VOID GLushort pattern _GL_VOID_RET _GL_VOID GLdouble GLdouble GLint GLint const GLdouble *points _GL_VOID_RET _GL_VOID GLdouble GLdouble GLint GLint GLdouble v1
Read Guarded memory(de)allocation.
ATTR_WARN_UNUSED_RESULT const BMVert * v2
#define pf2(_x, _i)
Prefetch 128.
#define pf(_x, _i)
Prefetch 64.
void(* MEM_freeN)(void *vmemh)
void *(* MEM_callocN)(size_t len, const char *str)
void *(* MEM_mallocN)(size_t len, const char *str)
static const pxr::TfToken b("b", pxr::TfToken::Immortal)
static void addfillface(ScanFillContext *sf_ctx, ScanFillVert *v1, ScanFillVert *v2, ScanFillVert *v3)
static bool testedgeside(const float v1[2], const float v2[2], const float v3[2])
void BLI_scanfill_begin(ScanFillContext *sf_ctx)
struct ScanFillVertLink ScanFillVertLink
void BLI_scanfill_end_arena(ScanFillContext *sf_ctx, MemArena *arena)
ScanFillVert * BLI_scanfill_vert_add(ScanFillContext *sf_ctx, const float vec[3])
static int vergpoly(const void *a1, const void *a2)
static unsigned int scanfill(ScanFillContext *sf_ctx, PolyFill *pf, const int flag)
void BLI_scanfill_end(ScanFillContext *sf_ctx)
static bool boundinsideEV(ScanFillEdge *eed, ScanFillVert *eve)
static void mergepolysSimp(ScanFillContext *sf_ctx, PolyFill *pf1, PolyFill *pf2)
unsigned int BLI_scanfill_calc(ScanFillContext *sf_ctx, const int flag)
static bool boundisect(PolyFill *pf2, PolyFill *pf1)
static int vergscdata(const void *a1, const void *a2)
ScanFillEdge * BLI_scanfill_edge_add(ScanFillContext *sf_ctx, ScanFillVert *v1, ScanFillVert *v2)
void BLI_scanfill_begin_arena(ScanFillContext *sf_ctx, MemArena *arena)
unsigned int BLI_scanfill_calc_ex(ScanFillContext *sf_ctx, const int flag, const float nor_proj[3])
static bool addedgetoscanvert(ScanFillVertLink *sc, ScanFillEdge *eed)
static ScanFillVertLink * addedgetoscanlist(ScanFillVertLink *scdata, ScanFillEdge *eed, unsigned int len)
static void splitlist(ScanFillContext *sf_ctx, ListBase *tempve, ListBase *temped, unsigned short nr)
#define SF_VERT_AVAILABLE
static void testvertexnearedge(ScanFillContext *sf_ctx)
struct ScanFillEdge * prev
struct ScanFillEdge * next
union ScanFillEdge::@122 tmp
ScanFillEdge * edge_first
struct ScanFillVert * next
union ScanFillVert::@121 tmp