#include "testing/testing.h"
#include "MEM_guardedalloc.h"
#include "BLI_array_utils.h"
#include "BLI_map.hh"
#include "BLI_math_geom.h"
#include "BLI_ordered_edge.hh"
#include "BLI_polyfill_2d.h"
#include "BLI_utildefines.h"
#include "BLI_heap.h"
#include "BLI_memarena.h"
#include "BLI_polyfill_2d_beautify.h"

Macros
#define	USE_COMBINATIONS_ALL

#define	USE_BEAUTIFY

#define	TRI_ERROR_VALUE uint(-1)

#define	TEST_POLYFILL_TEMPLATE_STATIC(poly, test_flag)

#define	POLY_TRI_COUNT(len) ((len)-2)

Typedefs
using	ePolyFill2DTestFlag

Functions
static void	polyfill_to_obj (const char *id, const float poly[][2], const uint poly_num, const uint tris[][3], const uint tris_num)

static void	test_valid_polyfill_prepare (uint tris[][3], uint tris_num)

static void	test_polyfill_simple (const float[][2], const uint poly_num, const uint tris[][3], const uint tris_num)

static void	test_polyfill_topology (const float[][2], const uint poly_num, const uint tris[][3], const uint tris_num)

static void	test_polyfill_winding (const float poly[][2], const uint, const uint tris[][3], const uint tris_num)

static void	test_polyfill_area (const float poly[][2], const uint poly_num, const uint tris[][3], const uint tris_num)

static void	test_polyfill_area_tri_nonzero (const float poly[][2], const uint, const uint tris[][3], const uint tris_num)

static void	test_polyfill_template_check (const char *id, const ePolyFill2DTestFlag test_flag, const float poly[][2], const uint poly_num, const uint tris[][3], const uint tris_num)

static void	test_polyfill_template (const char *id, const ePolyFill2DTestFlag test_flag, const float poly[][2], const uint poly_num, uint tris[][3], const uint tris_num)

static void	test_polyfill_template_flip_sign (const char *id, const ePolyFill2DTestFlag test_flag, const float poly[][2], const uint poly_num, uint tris[][3], const uint tris_num)

static void	test_polyfill_template_main (const char *id, const ePolyFill2DTestFlag test_flag, const float poly[][2], const uint poly_num, uint tris[][3], const uint tris_num)

	TEST (polyfill2d, TriangleCCW)

	TEST (polyfill2d, SquareCCW)

	TEST (polyfill2d, SquareCW)

	TEST (polyfill2d, Starfleet)

	TEST (polyfill2d, StarfleetDegenerate)

	TEST (polyfill2d, 3Colinear)

	TEST (polyfill2d, 4Colinear)

	TEST (polyfill2d, UnorderedColinear)

	TEST (polyfill2d, PlusShape)

	TEST (polyfill2d, StarShape)

	TEST (polyfill2d, UShape)

	TEST (polyfill2d, Spiral)

	TEST (polyfill2d, TestFlipCode)

	TEST (polyfill2d, SelfIntersect)

	TEST (polyfill2d, SelfTouch)

	TEST (polyfill2d, SelfOverlap)

	TEST (polyfill2d, TestDavData)

	TEST (polyfill2d, Issue815)

	TEST (polyfill2d, Issue207_1)

	TEST (polyfill2d, Issue207_11)

	TEST (polyfill2d, Issue1407)

	TEST (polyfill2d, Issue1407_pt)

	TEST (polyfill2d, IssueT40777_colinear)

	TEST (polyfill2d, IssueT41986_axis_align)

	TEST (polyfill2d, IssueT52834_axis_align_co_linear)

	TEST (polyfill2d, IssueT67109_axis_align_co_linear_a)

	TEST (polyfill2d, IssueT67109_axis_align_co_linear_b)

	TEST (polyfill2d, IssueT67109_axis_align_co_linear_c)

	TEST (polyfill2d, Issue103913_axis_align_co_linear_no_zero_area_tri)

Macro Definition Documentation

◆ POLY_TRI_COUNT

#define POLY_TRI_COUNT ( len ) ((len)-2)

Script to generate the data below:

# This example assumes we have a mesh object in edit-mode
 
import bpy
import bmesh
 
obj = bpy.context.edit_object
me = obj.data
bm = bmesh.from_edit_mesh(me)
 
def clean_float(num):
    if int(num) == num:
        return str(int(num))
    prec = 1
    while True:
        text = f"{num:.{prec}f}"
        if float(text) == num:
            return text
        prec += 1
 
for f in bm.faces:
    if f.select:
        print(f"\t// data for face: {f.index}")
        print("\tconst float poly[][2] = {", end="")
        coords = [[clean_float(num) for num in l.vert.co[0:2]] for l in f.loops]
        print("\t    ", end="")
        for i, (x, y) in enumerate(coords):
            if (i % 2) == 0:
                print("\n\t    ", end="")
            print(f"{{{x}, {y}}}", end=",")
        print("\n\t};")

Definition at line 398 of file BLI_polyfill_2d_test.cc.

◆ TEST_POLYFILL_TEMPLATE_STATIC

#define TEST_POLYFILL_TEMPLATE_STATIC	(		poly,
			test_flag )

Value:

  { \
    uint tris[POLY_TRI_COUNT(ARRAY_SIZE(poly))][3]; \
    const uint poly_num = ARRAY_SIZE(poly); \
    const uint tris_num = ARRAY_SIZE(tris); \
    const char *id = typeid(*this).name(); \
\
    test_polyfill_template_main(id, test_flag, poly, poly_num, tris, tris_num); \
  } \
  (void)0

Definition at line 303 of file BLI_polyfill_2d_test.cc.

Referenced by TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), and TEST().

◆ TRI_ERROR_VALUE

#define TRI_ERROR_VALUE uint(-1)

Definition at line 48 of file BLI_polyfill_2d_test.cc.

Referenced by test_polyfill_simple(), and test_valid_polyfill_prepare().

◆ USE_BEAUTIFY

#define USE_BEAUTIFY

Definition at line 12 of file BLI_polyfill_2d_test.cc.

◆ USE_COMBINATIONS_ALL

#define USE_COMBINATIONS_ALL

Definition at line 11 of file BLI_polyfill_2d_test.cc.

Typedef Documentation

◆ ePolyFill2DTestFlag

using ePolyFill2DTestFlag

Initial value:

 enum ePolyFill2DTestFlag {
  POLYFILL2D_TEST_IS_DEGENERATE = (1 << 0),
  POLYFILL2D_TEST_NO_ZERO_AREA_TRIS = (1 << 1),
  POLYFILL2D_TEST_NOP = 0,
}

Definition at line 39 of file BLI_polyfill_2d_test.cc.

Function Documentation

◆ polyfill_to_obj()

static void polyfill_to_obj	(	const char *	id,
		const float	poly[][2],
		const uint	poly_num,
		const uint	tris[][3],
		const uint	tris_num )

static

Definition at line 346 of file BLI_polyfill_2d_test.cc.

Referenced by test_polyfill_template_check().

◆ TEST() [1/29]

TEST	(	polyfill2d	,
		3Colinear	)

Definition at line 436 of file BLI_polyfill_2d_test.cc.

References TEST_POLYFILL_TEMPLATE_STATIC.

◆ TEST() [2/29]

TEST	(	polyfill2d	,
		4Colinear	)

Definition at line 443 of file BLI_polyfill_2d_test.cc.

References TEST_POLYFILL_TEMPLATE_STATIC.

◆ TEST() [3/29]

TEST	(	polyfill2d	,
		Issue103913_axis_align_co_linear_no_zero_area_tri	)

Definition at line 776 of file BLI_polyfill_2d_test.cc.

References TEST_POLYFILL_TEMPLATE_STATIC.

◆ TEST() [4/29]

TEST	(	polyfill2d	,
		Issue1407	)

Definition at line 653 of file BLI_polyfill_2d_test.cc.

References TEST_POLYFILL_TEMPLATE_STATIC.

◆ TEST() [5/29]

TEST	(	polyfill2d	,
		Issue1407_pt	)

Definition at line 666 of file BLI_polyfill_2d_test.cc.

References TEST_POLYFILL_TEMPLATE_STATIC.

◆ TEST() [6/29]

TEST	(	polyfill2d	,
		Issue207_1	)

Definition at line 614 of file BLI_polyfill_2d_test.cc.

References TEST_POLYFILL_TEMPLATE_STATIC.

◆ TEST() [7/29]

TEST	(	polyfill2d	,
		Issue207_11	)

Definition at line 634 of file BLI_polyfill_2d_test.cc.

References TEST_POLYFILL_TEMPLATE_STATIC.

◆ TEST() [8/29]

TEST	(	polyfill2d	,
		Issue815	)

Definition at line 598 of file BLI_polyfill_2d_test.cc.

References TEST_POLYFILL_TEMPLATE_STATIC.

◆ TEST() [9/29]

TEST	(	polyfill2d	,
		IssueT40777_colinear	)

Definition at line 679 of file BLI_polyfill_2d_test.cc.

References TEST_POLYFILL_TEMPLATE_STATIC.

◆ TEST() [10/29]

TEST	(	polyfill2d	,
		IssueT41986_axis_align	)

Definition at line 690 of file BLI_polyfill_2d_test.cc.

References TEST_POLYFILL_TEMPLATE_STATIC.

◆ TEST() [11/29]

TEST	(	polyfill2d	,
		IssueT52834_axis_align_co_linear	)

Definition at line 705 of file BLI_polyfill_2d_test.cc.

References TEST_POLYFILL_TEMPLATE_STATIC.

◆ TEST() [12/29]

TEST	(	polyfill2d	,
		IssueT67109_axis_align_co_linear_a	)

Definition at line 721 of file BLI_polyfill_2d_test.cc.

References TEST_POLYFILL_TEMPLATE_STATIC.

◆ TEST() [13/29]

TEST	(	polyfill2d	,
		IssueT67109_axis_align_co_linear_b	)

Definition at line 739 of file BLI_polyfill_2d_test.cc.

References TEST_POLYFILL_TEMPLATE_STATIC.

◆ TEST() [14/29]

TEST	(	polyfill2d	,
		IssueT67109_axis_align_co_linear_c	)

Definition at line 757 of file BLI_polyfill_2d_test.cc.

References TEST_POLYFILL_TEMPLATE_STATIC.

◆ TEST() [15/29]

TEST	(	polyfill2d	,
		PlusShape	)

Definition at line 457 of file BLI_polyfill_2d_test.cc.

References TEST_POLYFILL_TEMPLATE_STATIC.

◆ TEST() [16/29]

TEST	(	polyfill2d	,
		SelfIntersect	)

Definition at line 539 of file BLI_polyfill_2d_test.cc.

References TEST_POLYFILL_TEMPLATE_STATIC.

◆ TEST() [17/29]

TEST	(	polyfill2d	,
		SelfOverlap	)

Definition at line 566 of file BLI_polyfill_2d_test.cc.

References TEST_POLYFILL_TEMPLATE_STATIC.

◆ TEST() [18/29]

TEST	(	polyfill2d	,
		SelfTouch	)

Definition at line 546 of file BLI_polyfill_2d_test.cc.

References TEST_POLYFILL_TEMPLATE_STATIC.

◆ TEST() [19/29]

TEST	(	polyfill2d	,
		Spiral	)

Definition at line 492 of file BLI_polyfill_2d_test.cc.

References TEST_POLYFILL_TEMPLATE_STATIC.

◆ TEST() [20/29]

TEST	(	polyfill2d	,
		SquareCCW	)

Definition at line 408 of file BLI_polyfill_2d_test.cc.

References TEST_POLYFILL_TEMPLATE_STATIC.

◆ TEST() [21/29]

TEST	(	polyfill2d	,
		SquareCW	)

Definition at line 415 of file BLI_polyfill_2d_test.cc.

References TEST_POLYFILL_TEMPLATE_STATIC.

◆ TEST() [22/29]

TEST	(	polyfill2d	,
		Starfleet	)

Definition at line 422 of file BLI_polyfill_2d_test.cc.

References TEST_POLYFILL_TEMPLATE_STATIC.

◆ TEST() [23/29]

TEST	(	polyfill2d	,
		StarfleetDegenerate	)

Definition at line 429 of file BLI_polyfill_2d_test.cc.

References TEST_POLYFILL_TEMPLATE_STATIC.

◆ TEST() [24/29]

TEST	(	polyfill2d	,
		StarShape	)

Definition at line 477 of file BLI_polyfill_2d_test.cc.

References TEST_POLYFILL_TEMPLATE_STATIC.

◆ TEST() [25/29]

TEST	(	polyfill2d	,
		TestDavData	)

Definition at line 586 of file BLI_polyfill_2d_test.cc.

References TEST_POLYFILL_TEMPLATE_STATIC.

◆ TEST() [26/29]

TEST	(	polyfill2d	,
		TestFlipCode	)

Definition at line 516 of file BLI_polyfill_2d_test.cc.

References TEST_POLYFILL_TEMPLATE_STATIC.

◆ TEST() [27/29]

TEST	(	polyfill2d	,
		TriangleCCW	)

Definition at line 401 of file BLI_polyfill_2d_test.cc.

References TEST_POLYFILL_TEMPLATE_STATIC.

◆ TEST() [28/29]

TEST	(	polyfill2d	,
		UnorderedColinear	)

Definition at line 450 of file BLI_polyfill_2d_test.cc.

References TEST_POLYFILL_TEMPLATE_STATIC.

◆ TEST() [29/29]

TEST	(	polyfill2d	,
		UShape	)

Definition at line 484 of file BLI_polyfill_2d_test.cc.

References TEST_POLYFILL_TEMPLATE_STATIC.

◆ test_polyfill_area()

static void test_polyfill_area	(	const float	poly[][2],
		const uint	poly_num,
		const uint	tris[][3],
		const uint	tris_num )

static

Check the accumulated triangle area is close to the original area.

Definition at line 143 of file BLI_polyfill_2d_test.cc.

References area_poly_v2(), area_tri_v2(), and eps.

Referenced by test_polyfill_template_check().

◆ test_polyfill_area_tri_nonzero()

static void test_polyfill_area_tri_nonzero	(	const float	poly[][2],
		const uint	,
		const uint	tris[][3],
		const uint	tris_num )

static

Check that none of the tessellated triangles are zero area.

Definition at line 162 of file BLI_polyfill_2d_test.cc.

References area_tri_v2(), and EXPECT_EQ().

Referenced by test_polyfill_template_check().

◆ test_polyfill_simple()

static void test_polyfill_simple	(	const float	[][2],
		const uint	poly_num,
		const uint	tris[][3],
		const uint	tris_num )

static

Basic check for face index values:

no duplicates.
all tris set.
all verts used at least once.

Definition at line 68 of file BLI_polyfill_2d_test.cc.

References MEM_callocN, MEM_freeN(), and TRI_ERROR_VALUE.

Referenced by test_polyfill_template_check().

◆ test_polyfill_template()

static void test_polyfill_template	(	const char *	id,
		const ePolyFill2DTestFlag	test_flag,
		const float	poly[][2],
		const uint	poly_num,
		uint	tris[][3],
		const uint	tris_num )

static

Definition at line 205 of file BLI_polyfill_2d_test.cc.

References BLI_heap_free(), BLI_heap_new_ex(), BLI_memarena_free(), BLI_memarena_new(), BLI_POLYFILL_ALLOC_NGON_RESERVE, BLI_POLYFILL_ARENA_SIZE, BLI_polyfill_beautify(), BLI_polyfill_calc(), test_polyfill_template_check(), and test_valid_polyfill_prepare().

Referenced by test_polyfill_template_flip_sign().

◆ test_polyfill_template_check()

static void test_polyfill_template_check	(	const char *	id,
		const ePolyFill2DTestFlag	test_flag,
		const float	poly[][2],
		const uint	poly_num,
		const uint	tris[][3],
		const uint	tris_num )

static

Main template for polyfill testing.

Definition at line 182 of file BLI_polyfill_2d_test.cc.

References polyfill_to_obj(), test_polyfill_area(), test_polyfill_area_tri_nonzero(), test_polyfill_simple(), test_polyfill_topology(), and test_polyfill_winding().

Referenced by test_polyfill_template().

◆ test_polyfill_template_flip_sign()

static void test_polyfill_template_flip_sign	(	const char *	id,
		const ePolyFill2DTestFlag	test_flag,
		const float	poly[][2],
		const uint	poly_num,
		uint	tris[][3],
		const uint	tris_num )

static

Definition at line 234 of file BLI_polyfill_2d_test.cc.

References float, MEM_freeN(), MEM_mallocN, and test_polyfill_template().

Referenced by test_polyfill_template_main().

◆ test_polyfill_template_main()

static void test_polyfill_template_main	(	const char *	id,
		const ePolyFill2DTestFlag	test_flag,
		const float	poly[][2],
		const uint	poly_num,
		uint	tris[][3],
		const uint	tris_num )

static

Definition at line 257 of file BLI_polyfill_2d_test.cc.

References BLI_array_reverse, copy_v2_v2(), float, MEM_freeN(), MEM_mallocN, and test_polyfill_template_flip_sign().

◆ test_polyfill_topology()

static void test_polyfill_topology	(	const float	[][2],
		const uint	poly_num,
		const uint	tris[][3],
		const uint	tris_num )

static

Definition at line 91 of file BLI_polyfill_2d_test.cc.

References blender::Map< Key, Value, InlineBufferCapacity, ProbingStrategy, Hash, IsEqual, Slot, Allocator >::add_or_modify(), blender::Map< Key, Value, InlineBufferCapacity, ProbingStrategy, Hash, IsEqual, Slot, Allocator >::contains(), ELEM, EXPECT_EQ(), blender::Map< Key, Value, InlineBufferCapacity, ProbingStrategy, Hash, IsEqual, Slot, Allocator >::lookup(), blender::Map< Key, Value, InlineBufferCapacity, ProbingStrategy, Hash, IsEqual, Slot, Allocator >::size(), v2, and blender::Map< Key, Value, InlineBufferCapacity, ProbingStrategy, Hash, IsEqual, Slot, Allocator >::values().

Referenced by test_polyfill_template_check().

◆ test_polyfill_winding()

static void test_polyfill_winding	(	const float	poly[][2],
		const uint	,
		const uint	tris[][3],
		const uint	tris_num )

static

Check all faces are flipped the same way

Definition at line 124 of file BLI_polyfill_2d_test.cc.

References count, cross_tri_v2(), ELEM, and fabsf.

Referenced by test_polyfill_template_check().

◆ test_valid_polyfill_prepare()

static void test_valid_polyfill_prepare	(	uint	tris[][3],
		uint	tris_num )

static

Definition at line 50 of file BLI_polyfill_2d_test.cc.

References TRI_ERROR_VALUE.

Referenced by test_polyfill_template().

Macros

Typedefs

Functions

Macro Definition Documentation

◆ POLY_TRI_COUNT

◆ TEST_POLYFILL_TEMPLATE_STATIC

◆ TRI_ERROR_VALUE

◆ USE_BEAUTIFY

◆ USE_COMBINATIONS_ALL

Typedef Documentation

◆ ePolyFill2DTestFlag

Function Documentation

◆ polyfill_to_obj()

◆ TEST() [1/29]

◆ TEST() [2/29]

◆ TEST() [3/29]

◆ TEST() [4/29]

◆ TEST() [5/29]

◆ TEST() [6/29]

◆ TEST() [7/29]

◆ TEST() [8/29]

◆ TEST() [9/29]

◆ TEST() [10/29]

◆ TEST() [11/29]

◆ TEST() [12/29]

◆ TEST() [13/29]

◆ TEST() [14/29]

◆ TEST() [15/29]

◆ TEST() [16/29]

◆ TEST() [17/29]

◆ TEST() [18/29]

◆ TEST() [19/29]

◆ TEST() [20/29]

◆ TEST() [21/29]

◆ TEST() [22/29]

◆ TEST() [23/29]

◆ TEST() [24/29]

◆ TEST() [25/29]

◆ TEST() [26/29]

◆ TEST() [27/29]

◆ TEST() [28/29]

◆ TEST() [29/29]

◆ test_polyfill_area()

◆ test_polyfill_area_tri_nonzero()

◆ test_polyfill_simple()

◆ test_polyfill_template()

◆ test_polyfill_template_check()

◆ test_polyfill_template_flip_sign()

◆ test_polyfill_template_main()

◆ test_polyfill_topology()

◆ test_polyfill_winding()

◆ test_valid_polyfill_prepare()