Loading...
Searching...
No Matches
gsdrape.c File Reference

OGSF library - functions to intersect line segments with edges of surface polygons. More...

`#include <stdlib.h>`
`#include <grass/ogsf.h>`
`#include <grass/glocale.h>`
`#include "gsget.h"`
`#include "rowcol.h"`
`#include "math.h"`
Include dependency graph for gsdrape.c:

Go to the source code of this file.

## Macros

#define | DONT_INTERSECT 0
#define | DO_INTERSECT 1
#define | COLLINEAR 2
#define | LERP(a, l, h)
#define | EQUAL(a, b)
#define | ISNODE(p, res)
#define | SAME_SIGNS(a, b)

## Functions

int | gsdrape_set_surface (geosurf *gs)
| ADD.
int | seg_intersect_vregion (geosurf *gs, float *bgn, float *end)
| Check if segment intersect vector region.
Point3 * | gsdrape_get_segments (geosurf *gs, float *bgn, float *end, int *num)
| ADD.
Point3 * | gsdrape_get_allsegments (geosurf *gs, float *bgn, float *end, int *num)
| Get all segments.
void | interp_first_last (geosurf *gs, float *bgn, float *end, Point3 f, Point3 l)
| ADD.
int | _viewcell_tri_interp (geosurf *gs, Point3 pt)
| ADD.
int | viewcell_tri_interp (geosurf *gs, typbuff *buf, Point3 pt, int check_mask)
| ADD.
int | in_vregion (geosurf *gs, float *pt)
| ADD.
int | order_intersects (geosurf *gs, Point3 first, Point3 last, int vi, int hi, int di)
| ADD.
int | get_vert_intersects (geosurf *gs, float *bgn, float *end, float *dir)
| ADD.
int | get_horz_intersects (geosurf *gs, float *bgn, float *end, float *dir)
| Get horizontal intersects.
int | get_diag_intersects (geosurf *gs, float *bgn, float *end, float *dir)
| Get diagonal intersects.
int | segs_intersect (float x1, float y1, float x2, float y2, float x3, float y3, float x4, float y4, float *x, float *y)
| Line intersect.
int | Point_on_plane (Point3 p1, Point3 p2, Point3 p3, Point3 unk)
| Check if point is on plane.
int | XY_intersect_plane (float *intersect, float *plane)
| Check for intersection (point and plane).
int | P3toPlane (Point3 p1, Point3 p2, Point3 p3, float *plane)
| Define plane.
int | V3Cross (Point3 a, Point3 b, Point3 c)
| Get cross product.

## Detailed Description

OGSF library - functions to intersect line segments with edges of surface polygons.

GRASS OpenGL gsurf OGSF Library

For efficiency, intersections are found without respect to which specific triangle edge is intersected, but on a broader sense with the horizontal, vertical, and diagonal seams in the grid, then the intersections are ordered. If quadstrips are used for drawing rather than tmesh, triangulation is not consistent; for diagonal intersections, the proper diagonal to intersect would need to be determined according to the algorithm used by qstrip (look at nearby normals). It may be faster to go ahead and find the intersections with the other diagonals using the same methods, then at sorting time determine which diagonal array to look at for each quad. It would also require a mechanism for throwing out unused intersections with the diagonals during the ordering phase. Do intersections in 2D, fill line structure with 3D pts (maybe calling routine will cache for redrawing). Get Z value by using linear interp between corners.

- check for easy cases:
- single point
- colinear with horizontal or vertical edges
- colinear with diagonal edges of triangles
- calculate three arrays of ordered intersections:
- with vertical edges
- with horizontal edges
- with diagonal edges and interpolate Z, using simple linear interpolation.
- eliminate duplicate intersections (need only compare one coord for each)
- build ordered set of points.

Return static pointer to 3D set of points. Max number of intersections will be rows + cols + diags, so should allocate this number to initialize. Let calling routine worry about copying points for caching.

(C) 1999-2008 by the GRASS Development Team

This program is free software under the GNU General Public License (>=v2). Read the file COPYING that comes with GRASS for details.

Author
  Bill Brown UI GMS Lab
  Doxygenized by Martin Landa <landa.martin gmail.com> (May 2008)

Definition in file gsdrape.c.

## Macro Definition Documentation

## COLLINEAR

#define COLLINEAR 2

Definition at line 62 of file gsdrape.c.

Referenced by segs_intersect().

## DO_INTERSECT

#define DO_INTERSECT 1

Definition at line 61 of file gsdrape.c.

Referenced by segs_intersect().

## DONT_INTERSECT

#define DONT_INTERSECT 0

Definition at line 60 of file gsdrape.c.

Referenced by segs_intersect().

## EQUAL

#define EQUAL | ( |  | a,
|  |  | b )

Value:
(fabs((a) - (b)) < EPSILON)
EPSILON
#define EPSILON
Definition blas_level_2.c:26
b
double b
Definition driver/set_window.c:5

Definition at line 65 of file gsdrape.c.

Referenced by order_intersects(), and segs_intersect().

## ISNODE

#define ISNODE | ( |  | p,
|  |  | res )

Value:
(fmod((double)p, (double)res) < EPSILON)

Definition at line 66 of file gsdrape.c.

Referenced by get_diag_intersects().

## LERP

#define LERP | ( |  | a,
|  |  | l,
|  |  | h )

Value:
((l) + (((h) - (l)) * (a)))
l
double l
Definition driver/set_window.c:5

Definition at line 64 of file gsdrape.c.

Referenced by get_diag_intersects(), get_horz_intersects(), get_vert_intersects(), and viewcell_tri_interp().

## SAME_SIGNS

#define SAME_SIGNS | ( |  | a,
|  |  | b )

Value:
((a >= 0 && b >= 0) || (a < 0 && b < 0))

Definition at line 68 of file gsdrape.c.

Referenced by segs_intersect().

## Function Documentation

## _viewcell_tri_interp()

int _viewcell_tri_interp | ( | geosurf * | gs,
|  | Point3 | pt )

ADD.

Parameters

  | gs | surface (geosurf)
  [in,out] | pt |

Definition at line 464 of file gsdrape.c.

References gs_get_att_typbuff(), and viewcell_tri_interp().

Referenced by GS_draw_X().

## get_diag_intersects()

int get_diag_intersects | ( | geosurf * | gs,
|  | float * | bgn,
|  | float * | end,
|  | float * | dir )

Get diagonal intersects.

Colinear already eliminated

Parameters

  | gs | surface (geosurf)
  [in] | bgn | begin point
  [in] | end | end point
  | dir | ? (unused)

Returns
  number of intersects

Definition at line 1073 of file gsdrape.c.

References DCOL2X, DRC2OFF, DROW2Y, EPSILON, GET_MAPATT, ISNODE, LERP, segs_intersect(), VCOL2X, VCOLS, VROW2Y, VROWS, VXRES, VYRES, X, X2VCOL, Y, and Y2VROW.

## get_horz_intersects()

int get_horz_intersects | ( | geosurf * | gs,
|  | float * | bgn,
|  | float * | end,
|  | float * | dir )

Get horizontal intersects.

Parameters

  | gs | surface (geosurf)
  [in] | bgn | begin point
  [in] | end | end point
  [in] | dir |

Returns
  number of intersects

Definition at line 978 of file gsdrape.c.

References DRC2OFF, EPSILON, GET_MAPATT, LERP, segs_intersect(), VCOLS, VROW2Y, VROWS, VXRES, X, X2VCOL, Y, and Y2VROW.

## get_vert_intersects()

int get_vert_intersects | ( | geosurf * | gs,
|  | float * | bgn,
|  | float * | end,
|  | float * | dir )

ADD.

Todo
  For consistency, need to decide how last row & last column are displayed - would it look funny to always draw last row/col with finer resolution if necessary, or would it be better to only show full rows/cols?

Colinear already eliminated

Parameters

  | gs | surface (geosurf)
  [in] | bgn | begin point
  [in] | end | end point
  [in] | dir | direction

Returns

Definition at line 884 of file gsdrape.c.

References DRC2OFF, EPSILON, GET_MAPATT, LERP, segs_intersect(), VCOL2X, VCOLS, VROWS, VYRES, X, X2VCOL, Y, and Y2VROW.

## gsdrape_get_allsegments()

Point3 * gsdrape_get_allsegments | ( | geosurf * | gs,
|  | float * | bgn,
|  | float * | end,
|  | int * | num )

Get all segments.

Parameters

  | gs | surface (geosurf)
  [in,out] | bgn | begin point
  [in,out] | end | end point
  [out] | num |

Returns
  pointer to Point3 struct

Definition at line 400 of file gsdrape.c.

References gs_get_att_src(), GS_v3eq(), gsdrape_set_surface(), interp_first_last(), l, NULL, seg_intersect_vregion(), X, and Y.

Referenced by gs_los_intersect(), and gsd_wall().

## gsdrape_get_segments()

Point3 * gsdrape_get_segments | ( | geosurf * | gs,
|  | float * | bgn,
|  | float * | end,
|  | int * | num )

ADD.

Parameters

  | gs | surface (geosurf)
  [in,out] | bgn | begin point (x,y)
  [in,out] | end | end point (x,y)
  [out] | num |

Returns
  pointer to Point3 struct

Definition at line 350 of file gsdrape.c.

References gs_get_att_src(), GS_v3eq(), gsdrape_set_surface(), interp_first_last(), l, NULL, seg_intersect_vregion(), X, and Y.

Referenced by gs_distance_onsurf(), gsd_line_onsurf(), gsd_nline_onsurf(), gvd_draw_lineonsurf(), and gvd_vect().

## gsdrape_set_surface()

int gsdrape_set_surface | ( | geosurf * | gs | ) |

ADD.

Parameters

  gs | surface (geosurf)

Returns
  -1 on failure
  1 on success

Definition at line 198 of file gsdrape.c.

References G_warning(), gs_get_att_typbuff(), and NULL.

Referenced by gsdrape_get_allsegments(), and gsdrape_get_segments().

## in_vregion()

int in_vregion | ( | geosurf * | gs,
|  | float * | pt )

ADD.

Parameters

  | gs | surface (geosurf)
  [in] | pt |

Returns
  1
  0

Definition at line 698 of file gsdrape.c.

References VCOL2X, VCOLS, VROW2Y, VROWS, X, and Y.

Referenced by gs_distance_onsurf(), GS_get_cat_at_xy(), GS_get_norm_at_xy(), GS_get_val_at_xy(), order_intersects(), and seg_intersect_vregion().

## interp_first_last()

void interp_first_last | ( | geosurf * | gs,
|  | float * | bgn,
|  | float * | end,
|  | Point3 | f,
|  | Point3 | l )

ADD.

Parameters

  | gs | surface (geosurf)
  [in] | bgn | begin point
  [in] | end | end point
  [out] | f | first
  [out] | l | last

Definition at line 439 of file gsdrape.c.

References l, viewcell_tri_interp(), X, and Y.

Referenced by gsdrape_get_allsegments(), and gsdrape_get_segments().

## order_intersects()

int order_intersects | ( | geosurf * | gs,
|  | Point3 | first,
|  | Point3 | last,
|  | int | vi,
|  | int | hi,
|  | int | di )

ADD.

After all the intersections between the segment and triangle edges have been found, they are in three lists. (intersections with vertical, horizontal, and diagonal triangle edges)

Each list is ordered in space from first to last segment points, but now the lists need to be woven together. This routine starts with the first point of the segment and then checks the next point in each list to find the closest, eliminating duplicates along the way and storing the result in I3d.

Parameters

  | gs | surface (geosurf)
  [in] | first | first point
  [in] | last | last point
  [in] | vi |
  [in] | hi |
  [in] | di |

Returns

Definition at line 731 of file gsdrape.c.

References EPSILON, EQUAL, G_debug(), in_vregion(), X, and Y.

## P3toPlane()

int P3toPlane | ( | Point3 | p1,
|  | Point3 | p2,
|  | Point3 | p3,
|  | float * | plane )

Define plane.

Parameters

  [in] | p1,p2,p3 | three point on plane
  [out] | plane | plane definition

Returns
  1

Definition at line 1335 of file gsdrape.c.

References V3Cross(), X, and Y.

Referenced by Point_on_plane().

## Point_on_plane()

int Point_on_plane | ( | Point3 | p1,
|  | Point3 | p2,
|  | Point3 | p3,
|  | Point3 | unk )

Check if point is on plane.

Plane defined by three points here; user fills in unk[X] & unk[Y]

Parameters

  [in,out] | p1,p2,p3 | points defining plane
  [in,out] | unk | point

Returns
  1 point on plane
  0 point not on plane

Definition at line 1290 of file gsdrape.c.

References P3toPlane(), and XY_intersect_plane().

Referenced by viewcell_tri_interp().

## seg_intersect_vregion()

int seg_intersect_vregion | ( | geosurf * | gs,
|  | float * | bgn,
|  | float * | end )

Check if segment intersect vector region.

Clipping performed:

- bgn and end are replaced so that both points are within viewregion
- if seg intersects

Parameters

  | gs | surface (geosurf)
  [in,out] | bgn | begin point
  [in,out] | end | end point

Returns
  0 if segment doesn't intersect the viewregion, or intersects only at corner
  otherwise returns 1

Definition at line 233 of file gsdrape.c.

References GS_P2distance(), in_vregion(), segs_intersect(), VCOL2X, VCOLS, VROW2Y, VROWS, X, and Y.

Referenced by gsdrape_get_allsegments(), and gsdrape_get_segments().

## segs_intersect()

int segs_intersect | ( | float | x1,
|  | float | y1,
|  | float | x2,
|  | float | y2,
|  | float | x3,
|  | float | y3,
|  | float | x4,
|  | float | y4,
|  | float * | x,
|  | float * | y )

Line intersect.

Author: Mukesh Prasad Modified for floating point: Bill Brown

This function computes whether two line segments, respectively joining the input points (x1,y1) – (x2,y2) and the input points (x3,y3) – (x4,y4) intersect. If the lines intersect, the output variables x, y are set to coordinates of the point of intersection.

Parameters

  [in] | x1,y1,x2,y2 | coordinates of endpoints of one segment
  [in] | x3,y3,x4,y4 | coordinates of endpoints of other segment
  [out] | x,y | coordinates of intersection point

Returns
  0 no intersection
  1 intersect
  2 collinear

Definition at line 1210 of file gsdrape.c.

References COLLINEAR, DO_INTERSECT, DONT_INTERSECT, EQUAL, SAME_SIGNS, and x.

Referenced by get_diag_intersects(), get_horz_intersects(), get_vert_intersects(), gs_los_intersect(), gsd_ortho_wall(), and seg_intersect_vregion().

## V3Cross()

int V3Cross | ( | Point3 | a,
|  | Point3 | b,
|  | Point3 | c )

Get cross product.

Parameters

  [in] | a,b |
  [out] | c |

Returns
  cross product c = a cross b

Definition at line 1365 of file gsdrape.c.

References b, X, and Y.

Referenced by P3toPlane().

## viewcell_tri_interp()

int viewcell_tri_interp | ( | geosurf * | gs,
|  | typbuff * | buf,
|  | Point3 | pt,
|  | int | check_mask )

ADD.

In gsd_surf, tmesh draws polys like so:

    --------------
    |           /|
    |          / |
    |         /  |
    |        /   |
    |       /    |
    |      /     |
    |     /      |
    |    /       |
    |   /        |
    |  /         |
    | /          |
    |/           |
    --------------

UNLESS the top right or bottom left point is masked, in which case a single triangle with the opposite diagonal is drawn. This case is not yet handled here & should only occur on edges. pt has X & Y coordinates in it, we interpolate Z here

This could probably be much shorter, but not much faster.

Parameters

  | gs |
  | buf |
  [in,out] | pt |
  [in] | check_mask |

Returns
  1 if point is in view region
  otherwise 0 (if masked)

Definition at line 509 of file gsdrape.c.

References DRC2OFF, GET_MAPATT, gs_get_att_src(), gs_point_is_masked(), LERP, Point_on_plane(), VCOL2DCOL, VCOL2X, VCOLS, VROW2DROW, VROW2Y, VROWS, VXRES, VYRES, X, X2VCOL, Y, and Y2VROW.

Referenced by _viewcell_tri_interp(), gpd_2dsite(), gs_los_intersect(), gs_los_intersect1(), and interp_first_last().

## XY_intersect_plane()

int XY_intersect_plane | ( | float * | intersect,
|  | float * | plane )

Check for intersection (point and plane).

Ax + By + Cz + D = 0, so z = (Ax + By + D) / -C

User fills in intersect[X] & intersect[Y]

Parameters

  [in,out] | intersect | intersect coordinates
  [in] | plane | plane definition

Returns
  0 doesn't intersect
  1 intesects

Definition at line 1312 of file gsdrape.c.

References X, x, and Y.

Referenced by Point_on_plane().