mmg3d
octree_3d.c File Reference

Tools for local search around coordinates based on octree. More...

#include "mmg3d.h"
#include <stdio.h>
Include dependency graph for octree_3d.c:

Functions

void _MMG3D_initOctree_s (_MMG3D_octree_s *q)
 
int _MMG3D_initOctree (MMG5_pMesh mesh, _MMG3D_pOctree *q, int nv)
 
void _MMG3D_freeOctree_s (MMG5_pMesh mesh, _MMG3D_octree_s *q, int nv)
 
void _MMG3D_freeOctree (MMG5_pMesh mesh, _MMG3D_pOctree *q)
 
int64_t _MMG3D_getOctreeCoordinate (_MMG3D_pOctree q, double *ver, int dim)
 
int _MMG3D_moveOctree (MMG5_pMesh mesh, _MMG3D_pOctree q, int no, double *newVer, double *oldVer)
 
int _MMG3D_isCellIncluded (double *cellCenter, double l, double *zoneCenter, double l0)
 
void _MMG3D_placeInListDouble (double *distList, double dist, int index, int size)
 
void _MMG3D_placeInListOctree (_MMG3D_octree_s **qlist, _MMG3D_octree_s *q, int index, int size)
 
int _MMG3D_seekIndex (double *distList, double dist, int indexMin, int indexMax)
 
int _MMG3D_intersectRect (double *rectin, double *rectinout)
 
int _MMG3D_getListSquareRec (_MMG3D_octree_s *q, double *center, double *rect, _MMG3D_octree_s ***qlist, double *dist, double *ani, double l0, int nc, int dim, int *index)
 
int _MMG3D_getListSquare (MMG5_pMesh mesh, double *ani, _MMG3D_pOctree q, double *rect, _MMG3D_octree_s ***qlist)
 
int _MMG3D_addOctreeRec (MMG5_pMesh mesh, _MMG3D_octree_s *q, double *ver, const int no, int nv)
 
int _MMG3D_addOctree (MMG5_pMesh mesh, _MMG3D_pOctree q, const int no)
 
int _MMG3D_delOctreeVertex (MMG5_pMesh mesh, _MMG3D_octree_s *q, int indNo)
 
void _MMG3D_mergeBranchesRec (_MMG3D_octree_s *q0, _MMG3D_octree_s *q, int dim, int nv, int *index)
 
void _MMG3D_mergeBranches (MMG5_pMesh mesh, _MMG3D_octree_s *q, int dim, int nv)
 
int _MMG3D_delOctreeRec (MMG5_pMesh mesh, _MMG3D_octree_s *q, double *ver, const int no, const int nv)
 
int _MMG3D_delOctree (MMG5_pMesh mesh, _MMG3D_pOctree q, const int no)
 
void _MMG3D_printArbreDepth (_MMG3D_octree_s *q, int depth, int nv, int dim)
 
void _MMG3D_printArbre (_MMG3D_pOctree q)
 
void _MMG3D_printSubArbre (_MMG3D_octree_s *q, int nv, int dim)
 
void _MMG3D_sizeArbreRec (_MMG3D_octree_s *q, int nv, int dim, int *s1, int *s2)
 
int * _MMG3D_sizeArbre (_MMG3D_pOctree q, int dim)
 
static int _MMG3D_sizeArbreLinkRec (_MMG3D_octree_s *q, int nv, int dim)
 
static int _MMG3D_sizeArbreLink (_MMG3D_pOctree q)
 
static int NearNeighborSquare (MMG5_pMesh mesh, double *ani, _MMG3D_pOctree q, int no, double l, int dim)
 
int _MMG3D_octreein_iso (MMG5_pMesh mesh, MMG5_pSol sol, _MMG3D_pOctree octree, int ip, double lmax)
 
int _MMG3D_octreein_ani (MMG5_pMesh mesh, MMG5_pSol sol, _MMG3D_pOctree octree, int ip, double lmax)
 

Detailed Description

Tools for local search around coordinates based on octree.

Author
Jean Mercat (Inria/UBordeaux)
Version
1

An octree of the nodes is created and used for local neighbor search. This helps deciding if a position is too close to other nodes to refine with an insertion of a new node.

commande test : ctest -D Experimental -VV avec tunel ssh ouvert ssh : ssh -f -L 2000:vulcain.bordeaux.inria.fr:80 jmerc.nosp@m.at@v.nosp@m.ulcai.nosp@m.n.bo.nosp@m.rdeau.nosp@m.x.in.nosp@m.ria.f.nosp@m.r sleep <temps voulu>="">

se connecter : localhost:2000/CDash

Function Documentation

◆ _MMG3D_addOctree()

int _MMG3D_addOctree ( MMG5_pMesh  mesh,
_MMG3D_pOctree  q,
const int  no 
)
Parameters
pointertoward the mesh structure
qpointer toward the global octree structure
noindex of the point to add to the octree

Add the vertex of index no to the octree.

Here is the call graph for this function:
Here is the caller graph for this function:

◆ _MMG3D_addOctreeRec()

int _MMG3D_addOctreeRec ( MMG5_pMesh  mesh,
_MMG3D_octree_s q,
double *  ver,
const int  no,
int  nv 
)
Parameters
meshpointer toward the mesh structure.
qpointer toward an octree cell.
ververtex coordinates scaled such that the quadrant is [0;1]x[0;1]x[0;1]
novertex index in the mesh.
nvmaximum number of points in an octree cell.
Returns
1 if ok 0 if memory saturated

Add vertex in the suitable quadrant of the octree. This function is recursively called until we reach the last one. At each step, the vertex coordinates are scaled such as the quadrant is the [0;1]x[0;1]x[0;1] box.

Here is the call graph for this function:
Here is the caller graph for this function:

◆ _MMG3D_delOctree()

int _MMG3D_delOctree ( MMG5_pMesh  mesh,
_MMG3D_pOctree  q,
const int  no 
)
Parameters
meshpointer toward the mesh structure.
qpointer toward the global octree.
noreference of the vertex to be deleted.
Returns
1 if ok 0 if memory saturated

Delete the vertex no from the octree structure.

Here is the call graph for this function:
Here is the caller graph for this function:

◆ _MMG3D_delOctreeRec()

int _MMG3D_delOctreeRec ( MMG5_pMesh  mesh,
_MMG3D_octree_s q,
double *  ver,
const int  no,
const int  nv 
)
Parameters
meshpointer toward the mesh structure.
qpointer toward an octree cell.
ververtex coordinates scaled such that the quadrant is [0;1]x[0;1]x[0;1]
novertex index in the mesh.
nvmaximum number of points in an octree cell.
Returns
1 if ok 0 if memory saturated

Delete vertex no from the octree. This function is recursively called until we reach the terminal octree cell containing the vertex no. At each step, the vertex coordinates are scaled such as the quadrant is the [0;1]x[0;1]x[0;1] box.

Here is the call graph for this function:
Here is the caller graph for this function:

◆ _MMG3D_delOctreeVertex()

int _MMG3D_delOctreeVertex ( MMG5_pMesh  mesh,
_MMG3D_octree_s q,
int  indNo 
)
Parameters
qpointer toward a terminal octree cell (containing vertex)
noindex of the point to delete from the octree
Returns
1 if ok 0 if memory saturated

Delete the vertex of index no from the terminal octree cell, merge the cells if necessary.

Here is the caller graph for this function:

◆ _MMG3D_freeOctree()

void _MMG3D_freeOctree ( MMG5_pMesh  mesh,
_MMG3D_pOctree q 
)
Parameters
meshpointer toward the mesh structure.
qpointer toward a pointer toward the global octree.

Free the global octree structure.

Here is the call graph for this function:

◆ _MMG3D_freeOctree_s()

void _MMG3D_freeOctree_s ( MMG5_pMesh  mesh,
_MMG3D_octree_s q,
int  nv 
)
Parameters
meshpointer toward the mesh structure.
qpointer toward the octree cell
nvnumber of vertices in the cell subtree

Free the octree cell.

Here is the caller graph for this function:

◆ _MMG3D_getListSquare()

int _MMG3D_getListSquare ( MMG5_pMesh  mesh,
double *  ani,
_MMG3D_pOctree  q,
double *  rect,
_MMG3D_octree_s ***  qlist 
)
Parameters
meshpointer toward the mesh structure
animetric to use for the cell ordering from closest to farthest
qpointer toward the global octree structure.
rectrectangle that we want to intersect with the subtree. We define it given: the coordinates of one corner of the rectangle and the length of the rectangle in each dimension.
qlistpointer toward the list of pointer over the sub octrees that intersect rect.
Returns
index, the number of subtrees in the list, -1 if fail.

List the number of octree cells that intersect the rectangle rect.

Here is the call graph for this function:
Here is the caller graph for this function:

◆ _MMG3D_getListSquareRec()

int _MMG3D_getListSquareRec ( _MMG3D_octree_s q,
double *  center,
double *  rect,
_MMG3D_octree_s ***  qlist,
double *  dist,
double *  ani,
double  l0,
int  nc,
int  dim,
int *  index 
)
Parameters
qpointer toward the octree cell.
centercoordinates of the centre of the current subtree.
rectrectangle that we want to intersect with the subtree. We define it given: the coordinates of one corner of the rectange and the length of the rectangle in each dimension.
qlistpointer toward the list of pointer over the sub octrees that intersect rect.
distpointer toward the list of distances between center of the octree cells in qlist and the last 3 elements are the coordinates of the center of the whole recangle.
animetric of the point.
l0radius of the search zone.
ncnumber max of cell in the list +3 (the three last.
dimdimension =3.
indexnumber of octree cells that intersect rect
Returns
0 if the rectangle doesn't intersect the octree (possible due to the surface reconstruction), 1 otherwise.

List the number of octree cells that intersect the rectangle rect. To avoid counting of the cells, a maximum is set.

Here is the call graph for this function:
Here is the caller graph for this function:

◆ _MMG3D_getOctreeCoordinate()

int64_t _MMG3D_getOctreeCoordinate ( _MMG3D_pOctree  q,
double *  ver,
int  dim 
)
Parameters
qpointer toward the global octree.
vercoordinates of the point.
dimspace dimension (should be 3).
Returns
the integer containing the coordinates

Get the integer containing the coordinates

Here is the caller graph for this function:

◆ _MMG3D_initOctree()

int _MMG3D_initOctree ( MMG5_pMesh  mesh,
_MMG3D_pOctree q,
int  nv 
)
Parameters
meshpointer toward the mesh structure.
qpointer toward the global octree
nvmaximum number of vertices in each cell before subdivision
Returns
1 if ok 0 if memory saturated

Initialisation of the octree cell.

Here is the call graph for this function:
Here is the caller graph for this function:

◆ _MMG3D_initOctree_s()

void _MMG3D_initOctree_s ( _MMG3D_octree_s q)
Parameters
qpointer toward the octree cell

Initialisation of the octree cell.

Here is the caller graph for this function:

◆ _MMG3D_intersectRect()

int _MMG3D_intersectRect ( double *  rectin,
double *  rectinout 
)
Parameters
rectinrectangle to intersect, is not modified.
rectinoutrectangle to intersect, is set to the intersection.
Returns
1 if rectinout intersect rectin, 0 otherwise (possible because the surface reconstruction may leads to point outside the [0;1]x[0;1]x[0;1] bounding box)

Set rectinout to the intersection of the two rectangles. Rectangles are defined by: the coordinates of the lower left corner of the rectange and the length of the rectangle in each dimension.

Here is the caller graph for this function:

◆ _MMG3D_isCellIncluded()

int _MMG3D_isCellIncluded ( double *  cellCenter,
double  l,
double *  zoneCenter,
double  l0 
)
Parameters
cellCenter3 coordinates of the center of the octree cell to test.
lsize of the cell
zoneCenter3 coordinates of the center of the search zone
radiusof the search zone
Returns
wether the cell is included in the search zone.

◆ _MMG3D_mergeBranches()

void _MMG3D_mergeBranches ( MMG5_pMesh  mesh,
_MMG3D_octree_s q,
int  dim,
int  nv 
)
Parameters
meshpointer toward the mesh structure.
qpointer toward an octree cell.
dimdimension of the space (=3)
nvmaximum number of points in an octree cell.

Merge branches that have a parent counting less than nv vertices.

Here is the call graph for this function:
Here is the caller graph for this function:

◆ _MMG3D_mergeBranchesRec()

void _MMG3D_mergeBranchesRec ( _MMG3D_octree_s q0,
_MMG3D_octree_s q,
int  dim,
int  nv,
int *  index 
)
Parameters
q0pointer toward an octree cell.
qpointer toward an octree cell.
dimdimension of the space (=3).
nvmaximum number of points in an octree cell.
indexnext index in the array to be filled.

Merge sub-branches q of q0, in their parent q0. q0 should contain no more than nv vertices.

Here is the caller graph for this function:

◆ _MMG3D_moveOctree()

int _MMG3D_moveOctree ( MMG5_pMesh  mesh,
_MMG3D_pOctree  q,
int  no,
double *  newVer,
double *  oldVer 
)
Parameters
meshpointer toward the mesh structure.
qpointer toward the global octree.
noindex of the moved point.
newVernew coordinates for the moved point.
oldVerold coordinates for the moved point.
Returns
1 if ok 0 if memory saturated

Move one point in the octree structure. /!\ the vertex of index no can have either the new or the old coordinates in the mesh but all other vertice should have the same coordinates as when they were inserted into the octree. (ie: one move at a time in the mesh and the octree)

Here is the call graph for this function:
Here is the caller graph for this function:

◆ _MMG3D_octreein_ani()

int _MMG3D_octreein_ani ( MMG5_pMesh  mesh,
MMG5_pSol  sol,
_MMG3D_pOctree  octree,
int  ip,
double  lmax 
)
Parameters
meshpointer toward the mesh structure.
solpointer toward the solution structure.
octreepointer toward the octree structure.
ipindex of point to check.
Returns
1 if we can insert ip, 0 otherwise

Check if the vertex ip is not too close from another one (for an anisotropic metric).

Here is the call graph for this function:
Here is the caller graph for this function:

◆ _MMG3D_octreein_iso()

int _MMG3D_octreein_iso ( MMG5_pMesh  mesh,
MMG5_pSol  sol,
_MMG3D_pOctree  octree,
int  ip,
double  lmax 
)
Parameters
meshpointer toward the mesh structure.
solpointer toward the solution structure.
octreepointer toward the octree structure.
ipindex of point to check.
Returns
1 if we can insert ip, 0 otherwise

Check if the vertex ip is not too close from another one (for an isotropic metric).

Here is the call graph for this function:
Here is the caller graph for this function:

◆ _MMG3D_placeInListDouble()

void _MMG3D_placeInListDouble ( double *  distList,
double  dist,
int  index,
int  size 
)
Parameters
distListlist of values.
distvalue to insert in the list.
indexposition of the element before the place where dist should be inserted.
sizesize of the list before insertion.

Insert the value dist in the list distList at position index+1. Moves other data so nothing is lost. No memory check performed, this function should be called with coherent parameters.

Here is the caller graph for this function:

◆ _MMG3D_placeInListOctree()

void _MMG3D_placeInListOctree ( _MMG3D_octree_s **  qlist,
_MMG3D_octree_s q,
int  index,
int  size 
)
Parameters
qListlist of pointer on octree.
qpointer on octree to be inserted in the list.
indexposition of the element before the place where q should be inserted.
sizesize of the list before insertion.

Insert the pointer q in the list qList at position index+1. Moves other data so nothing is lost. No memory check performed, this function should be called with coherent parameters.

Here is the caller graph for this function:

◆ _MMG3D_printArbre()

void _MMG3D_printArbre ( _MMG3D_pOctree  q)
Parameters
qpointer toward the global octree structure

Print the octree.

Warning
debug function, not safe
Here is the call graph for this function:

◆ _MMG3D_printArbreDepth()

void _MMG3D_printArbreDepth ( _MMG3D_octree_s q,
int  depth,
int  nv,
int  dim 
)
Parameters
qpointer toward an octree cell
depthdepth of the subtree
nvnumber of vertices in the subtree
dimdimension in which we work

Print the depth depth of the subtree of q.

Warning
debug function, not safe
Here is the caller graph for this function:

◆ _MMG3D_printSubArbre()

void _MMG3D_printSubArbre ( _MMG3D_octree_s q,
int  nv,
int  dim 
)
Parameters
qpointer toward an octree cell
nvmaximum number of vertices in an octree leaf
dimspacial dimension

Print the octree.

Warning
debug function, not safe
Here is the call graph for this function:

◆ _MMG3D_seekIndex()

int _MMG3D_seekIndex ( double *  distList,
double  dist,
int  indexMin,
int  indexMax 
)
Parameters
distListordered list of value from smallest to largest.
distvalue to be compared to elements in the list.
indexMinminimum index of the list.
indexMaxmaximum index of the list.
Returns
Index of the biggest value of disList that is strictly smaller than dist. Only search in the bounds of indexMin and indexMax.
Here is the caller graph for this function:

◆ _MMG3D_sizeArbre()

int* _MMG3D_sizeArbre ( _MMG3D_pOctree  q,
int  dim 
)
Parameters
qpointer toward the global octree structure
dimdimension in which we work
Returns
the size of the tree or NULL pointer if fail

Print the octree memory size.

Warning
debug function, not safe
Here is the call graph for this function:

◆ _MMG3D_sizeArbreLink()

static int _MMG3D_sizeArbreLink ( _MMG3D_pOctree  q)
inlinestatic
Parameters
qpointer toward the global octree

Print the memory size of the octree for point stored with a linked list.

Warning
debug function, not safe
Here is the call graph for this function:

◆ _MMG3D_sizeArbreLinkRec()

static int _MMG3D_sizeArbreLinkRec ( _MMG3D_octree_s q,
int  nv,
int  dim 
)
inlinestatic
Parameters
qpointer toward an octree cell
nvnumber of vertices in the subtree
dimdimension in which we work

Print the memory size of the octree for point stored with a linked list.

Warning
debug function, not safe
Here is the caller graph for this function:

◆ _MMG3D_sizeArbreRec()

void _MMG3D_sizeArbreRec ( _MMG3D_octree_s q,
int  nv,
int  dim,
int *  s1,
int *  s2 
)
Parameters
qpointer toward an octree cell
nvmaximum number of vertices in an octree leaf
dimdimension in which we work
ssize of the octree

Print the memory size of the octree.

Warning
debug function, not safe
Here is the caller graph for this function:

◆ NearNeighborSquare()

static int NearNeighborSquare ( MMG5_pMesh  mesh,
double *  ani,
_MMG3D_pOctree  q,
int  no,
double  l,
int  dim 
)
inlinestatic
Parameters
qpointer toward the global octree

???

Here is the call graph for this function: