#include "MEM_guardedalloc.h"
#include "BLI_listbase.h"
#include "BLI_math.h"
#include "BLI_utildefines.h"
#include "BLI_voronoi_2d.h"

Classes
struct	VoronoiEvent

struct	VoronoiParabola

struct	VoronoiProcess

Macros
#define	VORONOI_EPS 1e-2f

Typedefs
typedef struct VoronoiEvent	VoronoiEvent

typedef struct VoronoiParabola	VoronoiParabola

typedef struct VoronoiProcess	VoronoiProcess

Enumerations
enum	{ voronoiEventType_Site = 0 , voronoiEventType_Circle = 1 }

Functions
static void	voronoi_insertEvent (VoronoiProcess process, VoronoiEvent event)

static VoronoiEdge *	voronoiEdge_new (const float start[2], const float left[2], const float right[2])

static VoronoiParabola *	voronoiParabola_new (void)

static VoronoiParabola *	voronoiParabola_newSite (const float site[2])

static VoronoiParabola *	voronoiParabola_getLeftChild (VoronoiParabola *parabola)

static VoronoiParabola *	voronoiParabola_getRightChild (VoronoiParabola *parabola)

static VoronoiParabola *	voronoiParabola_getLeftParent (VoronoiParabola *parabola)

static VoronoiParabola *	voronoiParabola_getRightParent (VoronoiParabola *parabola)

static void	voronoiParabola_setLeft (VoronoiParabola parabola, VoronoiParabola left)

static void	voronoiParabola_setRight (VoronoiParabola parabola, VoronoiParabola right)

static float	voronoi_getY (VoronoiProcess *process, const float p[2], float x)

static float	voronoi_getXOfEdge (VoronoiProcess process, VoronoiParabola par, float y)

static VoronoiParabola *	voronoi_getParabolaByX (VoronoiProcess *process, float xx)

static int	voronoi_getEdgeIntersection (VoronoiEdge a, VoronoiEdge b, float p[2])

static void	voronoi_checkCircle (VoronoiProcess process, VoronoiParabola b)

static void	voronoi_addParabola (VoronoiProcess *process, float site[2])

static void	voronoi_removeParabola (VoronoiProcess process, VoronoiEvent event)

static void	voronoi_finishEdge (VoronoiProcess process, VoronoiParabola parabola)

static void	voronoi_clampEdgeVertex (int width, int height, float coord, float other_coord)

static void	voronoi_clampEdges (ListBase edges, int width, int height, ListBase clamped_edges)

static int	voronoi_getNextSideCoord (ListBase *edges, const float coord[2], int dim, int dir, float next_coord[2])

static void	voronoi_createBoundaryEdges (ListBase *edges, int width, int height)

void	BLI_voronoi_compute (const VoronoiSite sites, int sites_total, int width, int height, ListBase edges)

static bool	testVoronoiEdge (const float site[2], const float point[2], const VoronoiEdge *edge)

static int	voronoi_addTriangulationPoint (const float coord[2], const float color[3], VoronoiTriangulationPoint *triangulated_points, int triangulated_points_total)

static void	voronoi_addTriangle (int v1, int v2, int v3, int(*r_triangles)[3], int r_triangles_total)

void	BLI_voronoi_triangulate (const VoronoiSite sites, int sites_total, ListBase edges, int width, int height, VoronoiTriangulationPoint *r_triangulated_points, int r_triangulated_points_total, int(*r_triangles)[3], int r_triangles_total)

Detailed Description

Fortune's algorithm implemented using explanation and some code snippets from http://blog.ivank.net/fortunes-algorithm-and-implementation.html

Definition in file voronoi_2d.c.

Macro Definition Documentation

◆ VORONOI_EPS

#define VORONOI_EPS 1e-2f

Definition at line 34 of file voronoi_2d.c.

Typedef Documentation

◆ VoronoiEvent

typedef struct VoronoiEvent VoronoiEvent

◆ VoronoiParabola

typedef struct VoronoiParabola VoronoiParabola

◆ VoronoiProcess

typedef struct VoronoiProcess VoronoiProcess

Enumeration Type Documentation

◆ anonymous enum

anonymous enum

Enumerator
voronoiEventType_Site
voronoiEventType_Circle

Definition at line 36 of file voronoi_2d.c.

Function Documentation

◆ BLI_voronoi_compute()

void BLI_voronoi_compute	(	const VoronoiSite *	sites,
		int	sites_total,
		int	width,
		int	height,
		ListBase *	edges
	)

Definition at line 667 of file voronoi_2d.c.

References BLI_freelinkN(), BLI_movelisttolist(), VoronoiSite::co, copy_v2_v2(), process::edges, VoronoiEdge::end, height, MEM_callocN, MEM_freeN, VoronoiEdge::neighbor, VoronoiEdge::next, process(), VoronoiEdge::start, voronoi_addParabola(), voronoi_finishEdge(), voronoi_insertEvent(), voronoi_removeParabola(), voronoiEventType_Site, and width.

Referenced by blender::compositor::KeyingScreenOperation::buildVoronoiTriangulation().

◆ BLI_voronoi_triangulate()

void BLI_voronoi_triangulate	(	const VoronoiSite *	sites,
		int	sites_total,
		ListBase *	edges,
		int	width,
		int	height,
		VoronoiTriangulationPoint **	r_triangulated_points,
		int *	r_triangulated_points_total,
		int(**)	r_triangles[3],
		int *	r_triangles_total
	)

Definition at line 792 of file voronoi_2d.c.

References BLI_freelistN(), VoronoiSite::color, VoronoiTriangulationPoint::color, VoronoiEdge::end, ListBase::first, height, mul_v3_fl(), VoronoiEdge::next, NULL, VoronoiTriangulationPoint::power, VoronoiEdge::start, testVoronoiEdge(), v1, v2, voronoi_addTriangle(), voronoi_addTriangulationPoint(), voronoi_clampEdges(), voronoi_createBoundaryEdges(), and width.

Referenced by blender::compositor::KeyingScreenOperation::buildVoronoiTriangulation().

◆ testVoronoiEdge()

static bool testVoronoiEdge	(	const float	site[2],
		const float	point[2],
		const VoronoiEdge *	edge
	)

static

Definition at line 718 of file voronoi_2d.c.

References VoronoiEdge::end, isect_seg_seg_v2_point(), len_squared_v2v2(), VoronoiEdge::start, and VORONOI_EPS.

Referenced by BLI_voronoi_triangulate().

◆ voronoi_addParabola()

static void voronoi_addParabola	(	VoronoiProcess *	process,
		float	site[2]
	)

static

Definition at line 359 of file voronoi_2d.c.

References BLI_addtail(), BLI_freelinkN(), VoronoiParabola::edge, process::edges, VoronoiParabola::event, VoronoiParabola::is_leaf, VoronoiParabola::left, VoronoiEdge::neighbor, NULL, VoronoiParabola::site, voronoi_checkCircle(), voronoi_getParabolaByX(), voronoi_getY(), voronoiEdge_new(), voronoiParabola_new(), voronoiParabola_newSite(), voronoiParabola_setLeft(), and voronoiParabola_setRight().

Referenced by BLI_voronoi_compute().

◆ voronoi_addTriangle()

static void voronoi_addTriangle	(	int	v1,
		int	v2,
		int	v3,
		int(**)	r_triangles[3],
		int *	r_triangles_total
	)

static

Definition at line 771 of file voronoi_2d.c.

References MEM_callocN, MEM_reallocN, v1, and v2.

Referenced by BLI_voronoi_triangulate().

◆ voronoi_addTriangulationPoint()

static int voronoi_addTriangulationPoint	(	const float	coord[2],
		const float	color[3],
		VoronoiTriangulationPoint **	triangulated_points,
		int *	triangulated_points_total
	)