Blender  V3.3
Classes | Macros | Typedefs | Enumerations | Functions
voronoi_2d.c File Reference
#include "MEM_guardedalloc.h"
#include "BLI_listbase.h"
#include "BLI_math.h"
#include "BLI_utildefines.h"
#include "BLI_voronoi_2d.h"

Go to the source code of this file.

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 VoronoiEdgevoronoiEdge_new (const float start[2], const float left[2], const float right[2])
 
static VoronoiParabolavoronoiParabola_new (void)
 
static VoronoiParabolavoronoiParabola_newSite (const float site[2])
 
static VoronoiParabolavoronoiParabola_getLeftChild (VoronoiParabola *parabola)
 
static VoronoiParabolavoronoiParabola_getRightChild (VoronoiParabola *parabola)
 
static VoronoiParabolavoronoiParabola_getLeftParent (VoronoiParabola *parabola)
 
static VoronoiParabolavoronoiParabola_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 VoronoiParabolavoronoi_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 18 of file voronoi_2d.c.

Typedef Documentation

◆ VoronoiEvent

typedef struct VoronoiEvent VoronoiEvent

◆ VoronoiParabola

◆ VoronoiProcess

Enumeration Type Documentation

◆ anonymous enum

anonymous enum
Enumerator
voronoiEventType_Site 
voronoiEventType_Circle 

Definition at line 20 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 
)

◆ 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 
)

◆ testVoronoiEdge()

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

Definition at line 702 of file voronoi_2d.c.

References isect_seg_seg_v2_point(), len_squared_v2v2(), point, and VORONOI_EPS.

Referenced by BLI_voronoi_triangulate().

◆ voronoi_addParabola()

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

◆ voronoi_addTriangle()

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

Definition at line 755 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 
)
static

◆ voronoi_checkCircle()

static void voronoi_checkCircle ( VoronoiProcess process,
VoronoiParabola b 
)
static

◆ voronoi_clampEdges()

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

◆ voronoi_clampEdgeVertex()

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

Definition at line 509 of file voronoi_2d.c.

References copy_v2_v2(), height, IN_RANGE_INCL, isect_seg_seg_v2_point(), v1, v2, and width.

Referenced by voronoi_clampEdges().

◆ voronoi_createBoundaryEdges()

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

◆ voronoi_finishEdge()

static void voronoi_finishEdge ( VoronoiProcess process,
VoronoiParabola parabola 
)
static

◆ voronoi_getEdgeIntersection()

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

Definition at line 273 of file voronoi_2d.c.

References Freestyle::a, usdtokens::b(), x, and y.

Referenced by voronoi_checkCircle().

◆ voronoi_getNextSideCoord()

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

◆ voronoi_getParabolaByX()

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

◆ voronoi_getXOfEdge()

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

◆ voronoi_getY()

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

Definition at line 202 of file voronoi_2d.c.

References x.

Referenced by voronoi_addParabola(), and voronoi_removeParabola().

◆ voronoi_insertEvent()

static void voronoi_insertEvent ( VoronoiProcess process,
VoronoiEvent event 
)
static

◆ voronoi_removeParabola()

static void voronoi_removeParabola ( VoronoiProcess process,
VoronoiEvent event 
)
static

◆ voronoiEdge_new()

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

Definition at line 70 of file voronoi_2d.c.

References copy_v2_v2(), left, MEM_callocN, NULL, and right.

Referenced by voronoi_addParabola(), and voronoi_removeParabola().

◆ voronoiParabola_getLeftChild()

static VoronoiParabola* voronoiParabola_getLeftChild ( VoronoiParabola parabola)
static

◆ voronoiParabola_getLeftParent()

static VoronoiParabola* voronoiParabola_getLeftParent ( VoronoiParabola parabola)
static

Definition at line 155 of file voronoi_2d.c.

References VoronoiParabola::left, NULL, and VoronoiParabola::parent.

Referenced by voronoi_checkCircle(), and voronoi_removeParabola().

◆ voronoiParabola_getRightChild()

static VoronoiParabola* voronoiParabola_getRightChild ( VoronoiParabola parabola)
static

◆ voronoiParabola_getRightParent()

static VoronoiParabola* voronoiParabola_getRightParent ( VoronoiParabola parabola)
static

Definition at line 173 of file voronoi_2d.c.

References NULL, VoronoiParabola::parent, and VoronoiParabola::right.

Referenced by voronoi_checkCircle(), and voronoi_removeParabola().

◆ voronoiParabola_new()

static VoronoiParabola* voronoiParabola_new ( void  )
static

◆ voronoiParabola_newSite()

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

◆ voronoiParabola_setLeft()

static void voronoiParabola_setLeft ( VoronoiParabola parabola,
VoronoiParabola left 
)
static

Definition at line 190 of file voronoi_2d.c.

References VoronoiParabola::left, and left.

Referenced by voronoi_addParabola(), and voronoi_removeParabola().

◆ voronoiParabola_setRight()

static void voronoiParabola_setRight ( VoronoiParabola parabola,
VoronoiParabola right 
)
static

Definition at line 196 of file voronoi_2d.c.

References VoronoiParabola::right, and right.

Referenced by voronoi_addParabola(), and voronoi_removeParabola().