Bounding boxes trees

GTS_BBOX_CLASS()

#define     GTS_BBOX_CLASS(klass)

Casts klass to GtsBBoxClass.

GTS_BBOX()

#define     GTS_BBOX(obj)

Casts obj to GtsBBox.

GTS_IS_BBOX()

#define     GTS_IS_BBOX(obj)

Evaluates to TRUE if obj is a GtsBBox, FALSE otherwise.

GtsBBoxClass

typedef struct {
  GtsObjectClass parent_class;
} GtsBBoxClass;

The bounding box class derived from GtsObjectClass.

GtsBBox

typedef struct {
  GtsObject object;
  gpointer bounded;
  gdouble x1, y1, z1;
  gdouble x2, y2, z2;
} GtsBBox;

The bounding box structure.

gts_bbox_class ()

GtsBBoxClass* gts_bbox_class                (void);

gts_bbox_new ()

GtsBBox*    gts_bbox_new                    (GtsBBoxClass *klass,
                                             gpointer bounded,
                                             gdouble x1,
                                             gdouble y1,
                                             gdouble z1,
                                             gdouble x2,
                                             gdouble y2,
                                             gdouble z2);

gts_bbox_set ()

void        gts_bbox_set                    (GtsBBox *bbox,
                                             gpointer bounded,
                                             gdouble x1,
                                             gdouble y1,
                                             gdouble z1,
                                             gdouble x2,
                                             gdouble y2,
                                             gdouble z2);

Sets fields of bbox.

gts_bbox_segment ()

GtsBBox*    gts_bbox_segment                (GtsBBoxClass *klass,
                                             GtsSegment *s);

gts_bbox_triangle ()

GtsBBox*    gts_bbox_triangle               (GtsBBoxClass *klass,
                                             GtsTriangle *t);

gts_bbox_surface ()

GtsBBox*    gts_bbox_surface                (GtsBBoxClass *klass,
                                             GtsSurface *surface);

gts_bbox_points ()

GtsBBox*    gts_bbox_points                 (GtsBBoxClass *klass,
                                             GSList *points);

gts_bbox_bboxes ()

GtsBBox*    gts_bbox_bboxes                 (GtsBBoxClass *klass,
                                             GSList *bboxes);

gts_bbox_draw ()

void        gts_bbox_draw                   (GtsBBox *bb,
                                             FILE *fptr);

Writes in file fptr an OOGL (Geomview) description of bb.

gts_bbox_point_is_inside()

#define     gts_bbox_point_is_inside(bbox, p)

Evaluates to TRUE if p is inside (or on the boundary) of bbox, FALSE otherwise.

gts_bboxes_are_overlapping ()

gboolean    gts_bboxes_are_overlapping      (GtsBBox *bb1,
                                             GtsBBox *bb2);

gts_bbox_diagonal2 ()

gdouble     gts_bbox_diagonal2              (GtsBBox *bb);

gts_bbox_point_distance2 ()

void        gts_bbox_point_distance2        (GtsBBox *bb,
                                             GtsPoint *p,
                                             gdouble *min,
                                             gdouble *max);

Sets min and max to lower and upper bounds for the square of the Euclidean distance between the object contained in bb and p. For these bounds to make any sense the bounding box must be "tight" i.e. each of the 6 faces of the box must at least be touched by one point of the bounded object.

gts_bbox_is_stabbed ()

gboolean    gts_bbox_is_stabbed             (GtsBBox *bb,
                                             GtsPoint *p);

gts_bbox_overlaps_triangle ()

gboolean    gts_bbox_overlaps_triangle      (GtsBBox *bb,
                                             GtsTriangle *t);

This is a wrapper around the fast overlap test of Tomas Akenine-Moller (http://www.cs.lth.se/home/Tomas_Akenine_Moller/).

GtsBBTreeTraverseFunc ()

void        (*GtsBBTreeTraverseFunc)        (GtsBBox *bb1,
                                             GtsBBox *bb2,
                                             gpointer data);

User function called for each pair of overlapping bounding boxes. See gts_bb_tree_traverse_overlapping().

gts_bb_tree_new ()

GNode*      gts_bb_tree_new                 (GSList *bboxes);

Builds a new hierarchy of bounding boxes for bboxes. At each level, the GNode->data field contains a GtsBBox bounding box of all the children. The tree is binary and is built by repeatedly cutting in two approximately equal halves the bounding boxes at each level until a leaf node (i.e. a bounding box given in bboxes) is reached. In order to minimize the depth of the tree, the cutting direction is always chosen as perpendicular to the longest dimension of the bounding box.

gts_bb_tree_surface ()

GNode*      gts_bb_tree_surface             (GtsSurface *s);

gts_bb_tree_overlap ()

GSList*     gts_bb_tree_overlap             (GNode *tree,
                                             GtsBBox *bbox);

gts_bb_tree_is_overlapping ()

gboolean    gts_bb_tree_is_overlapping      (GNode *tree,
                                             GtsBBox *bbox);

gts_bb_tree_traverse_overlapping ()

void        gts_bb_tree_traverse_overlapping
                                            (GNode *tree1,
                                             GNode *tree2,
                                             GtsBBTreeTraverseFunc func,
                                             gpointer data);

Calls func for each overlapping pair of leaves of tree1 and tree2.

gts_bb_tree_draw ()

void        gts_bb_tree_draw                (GNode *tree,
                                             guint depth,
                                             FILE *fptr);

Write in fptr an OOGL (Geomview) description of tree for the depth specified by depth.

gts_bb_tree_destroy ()

void        gts_bb_tree_destroy             (GNode *tree,
                                             gboolean free_leaves);

Destroys all the bounding boxes created by tree and destroys the tree itself. If free_leaves is set to TRUE, destroys boxes given by the user when creating the tree (i.e. leaves of the tree).

GtsBBoxDistFunc ()

gdouble     (*GtsBBoxDistFunc)              (GtsPoint *p,
                                             gpointer bounded);

User function returning the (minimum) distance between the object defined by bounded and point p.

GtsBBoxClosestFunc ()

GtsPoint*   (*GtsBBoxClosestFunc)           (GtsPoint *p,
                                             gpointer bounded);

User function returning a GtsPoint belonging to the object defined by bounded and closest to p.

gts_bb_tree_point_distance ()

gdouble     gts_bb_tree_point_distance      (GNode *tree,
                                             GtsPoint *p,
                                             GtsBBoxDistFunc distance,
                                             GtsBBox **bbox);

gts_bb_tree_point_closest ()

GtsPoint*   gts_bb_tree_point_closest       (GNode *tree,
                                             GtsPoint *p,
                                             GtsBBoxClosestFunc closest,
                                             gdouble *distance);

gts_bb_tree_segment_distance ()

void        gts_bb_tree_segment_distance    (GNode *tree,
                                             GtsSegment *s,
                                             GtsBBoxDistFunc distance,
                                             gdouble delta,
                                             GtsRange *range);

Given a segment s, points are sampled regularly on its length using delta as increment. The distance from each of these points to the closest object of tree is computed using distance and the gts_bb_tree_point_distance() function. The fields of range are filled with the number of points sampled, the minimum, average and maximum value and the standard deviation.

gts_bb_tree_triangle_distance ()

void        gts_bb_tree_triangle_distance   (GNode *tree,
                                             GtsTriangle *t,
                                             GtsBBoxDistFunc distance,
                                             gdouble delta,
                                             GtsRange *range);

Given a triangle t, points are sampled regularly on its surface using delta as increment. The distance from each of these points to the closest object of tree is computed using distance and the gts_bb_tree_point_distance() function. The fields of range are filled with the number of points sampled, the minimum, average and maximum value and the standard deviation.

gts_bb_tree_point_closest_bboxes ()

GSList*     gts_bb_tree_point_closest_bboxes
                                            (GNode *tree,
                                             GtsPoint *p);

gts_bb_tree_surface_boundary_distance ()

void        gts_bb_tree_surface_boundary_distance
                                            (GNode *tree,
                                             GtsSurface *s,
                                             GtsBBoxDistFunc distance,
                                             gdouble delta,
                                             GtsRange *range);

Calls gts_bb_tree_segment_distance() for each edge boundary of s. The fields of range are filled with the minimum, maximum and average distance. The average distance is defined as the sum of the average distances for each boundary edge weighthed by their length and divided by the total length of the boundaries. The standard deviation is defined accordingly. The n field of range is filled with the number of sampled points used.

gts_bb_tree_surface_distance ()

void        gts_bb_tree_surface_distance    (GNode *tree,
                                             GtsSurface *s,
                                             GtsBBoxDistFunc distance,
                                             gdouble delta,
                                             GtsRange *range);

Calls gts_bb_tree_triangle_distance() for each face of s. The fields of range are filled with the minimum, maximum and average distance. The average distance is defined as the sum of the average distances for each triangle weighthed by their area and divided by the total area of the surface. The standard deviation is defined accordingly. The n field of range is filled with the number of sampled points used.

gts_bb_tree_stabbed ()

GSList*     gts_bb_tree_stabbed             (GNode *tree,
                                             GtsPoint *p);