GRASS GIS 7 Programmer's Manual  7.7.svn(2018)-r73666
 All Data Structures Files Functions Variables Typedefs Enumerations Enumerator Friends Macros Pages
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)   ((l)+(((h)-(l))*(a)))
 
#define EQUAL(a, b)   (fabs((a)-(b))<EPSILON)
 
#define ISNODE(p, res)   (fmod((double)p,(double)res)<EPSILON)
 
#define SAME_SIGNS(a, b)   ((a >= 0 && b >= 0) || (a < 0 && b < 0))
 

Functions

int gsdrape_set_surface (geosurf *gs)
 ADD. More...
 
int seg_intersect_vregion (geosurf *gs, float *bgn, float *end)
 Check if segment intersect vector region. More...
 
Point3gsdrape_get_segments (geosurf *gs, float *bgn, float *end, int *num)
 ADD. More...
 
Point3gsdrape_get_allsegments (geosurf *gs, float *bgn, float *end, int *num)
 Get all segments. More...
 
void interp_first_last (geosurf *gs, float *bgn, float *end, Point3 f, Point3 l)
 ADD. More...
 
int _viewcell_tri_interp (geosurf *gs, Point3 pt)
 ADD. More...
 
int viewcell_tri_interp (geosurf *gs, typbuff *buf, Point3 pt, int check_mask)
 ADD. More...
 
int in_vregion (geosurf *gs, float *pt)
 ADD. More...
 
int order_intersects (geosurf *gs, Point3 first, Point3 last, int vi, int hi, int di)
 ADD. More...
 
int get_vert_intersects (geosurf *gs, float *bgn, float *end, float *dir)
 ADD. More...
 
int get_horz_intersects (geosurf *gs, float *bgn, float *end, float *dir)
 Get horizontal intersects. More...
 
int get_diag_intersects (geosurf *gs, float *bgn, float *end, float *dir)
 Get diagonal intersects. More...
 
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. More...
 
int Point_on_plane (Point3 p1, Point3 p2, Point3 p3, Point3 unk)
 Check if point is on plane. More...
 
int XY_intersect_plane (float *intersect, float *plane)
 Check for intersection (point and plane) More...
 
int P3toPlane (Point3 p1, Point3 p2, Point3 p3, float *plane)
 Define plane. More...
 
int V3Cross (Point3 a, Point3 b, Point3 c)
 Get cross product. More...
 

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 consistant; 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

#define COLLINEAR   2

Definition at line 61 of file gsdrape.c.

Referenced by segs_intersect().

#define DO_INTERSECT   1

Definition at line 60 of file gsdrape.c.

Referenced by segs_intersect().

#define DONT_INTERSECT   0

Definition at line 59 of file gsdrape.c.

Referenced by segs_intersect().

#define EQUAL (   a,
  b 
)    (fabs((a)-(b))<EPSILON)

Definition at line 64 of file gsdrape.c.

#define ISNODE (   p,
  res 
)    (fmod((double)p,(double)res)<EPSILON)

Definition at line 65 of file gsdrape.c.

Referenced by get_diag_intersects().

#define LERP (   a,
  l,
 
)    ((l)+(((h)-(l))*(a)))
#define SAME_SIGNS (   a,
  b 
)    ((a >= 0 && b >= 0) || (a < 0 && b < 0))

Definition at line 67 of file gsdrape.c.

Referenced by segs_intersect().

Function Documentation

int _viewcell_tri_interp ( geosurf gs,
Point3  pt 
)

ADD.

Parameters
gssurface (geosurf)
pt

Definition at line 467 of file gsdrape.c.

References ATT_TOPO, gs_get_att_typbuff(), and viewcell_tri_interp().

Referenced by GS_draw_X().

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

Get diagonal intersects.

Colinear already eliminated

Parameters
gssurface (geosurf)
bgnbegin point
endend point
dir? (unused)
Returns
number of intersects

Definition at line 1074 of file gsdrape.c.

References g_surf::att, ATT_TOPO, g_surf::cols, gsurf_att::constant, DCOL2X, DRC2OFF, DROW2Y, EPSILON, GET_MAPATT, if(), ISNODE, LERP, num, g_surf::rows, segs_intersect(), VCOL2X, VCOLS, VROW2Y, VROWS, VXRES, VYRES, X, X2VCOL, g_surf::x_mod, Y, Y2VROW, g_surf::y_mod, g_surf::yrange, and Z.

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

Get horizontal intersects.

Parameters
gssurface (geosurf)
bgnbegin point
endend point
dir
Returns
number of intersects

Definition at line 978 of file gsdrape.c.

References g_surf::att, ATT_TOPO, g_surf::cols, gsurf_att::constant, DRC2OFF, EPSILON, GET_MAPATT, if(), LERP, num, segs_intersect(), VCOLS, VROW2Y, VROWS, VXRES, VYRES, X, X2VCOL, g_surf::x_mod, g_surf::xres, Y, Y2VROW, g_surf::y_mod, and Z.

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

ADD.

Todo:
For consistancy, 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
gssurface (geosurf)
bgnbegin point
endend point
dirdirection
Returns

Definition at line 882 of file gsdrape.c.

References g_surf::att, ATT_TOPO, gsurf_att::constant, DRC2OFF, EPSILON, GET_MAPATT, if(), LERP, num, g_surf::rows, segs_intersect(), VCOL2X, VCOLS, VROWS, VXRES, VYRES, X, X2VCOL, g_surf::x_mod, Y, Y2VROW, g_surf::y_mod, g_surf::yrange, g_surf::yres, and Z.

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

Get all segments.

Parameters
gssurface (geosurf)
bgnbegin point
endend point
num
Returns
pointer to Point3 struct

Definition at line 401 of file gsdrape.c.

References ATT_TOPO, CONST_ATT, gs_get_att_src(), GS_v3eq(), gsdrape_set_surface(), interp_first_last(), NULL, and seg_intersect_vregion().

Referenced by gs_los_intersect(), and gsd_wall().

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

ADD.

Parameters
gssurface (geosurf)
bgnbegin point (x,y)
endend point (x,y)
num
Returns
pointer to Point3 struct

Definition at line 350 of file gsdrape.c.

References g_surf::att, ATT_TOPO, CONST_ATT, gsurf_att::constant, gs_get_att_src(), GS_v3eq(), gsdrape_set_surface(), interp_first_last(), NULL, seg_intersect_vregion(), X, Y, and Z.

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

int gsdrape_set_surface ( geosurf gs)

ADD.

Parameters
gssurface (geosurf)
Returns
-1 on failure
1 on success

Definition at line 199 of file gsdrape.c.

References _, ATT_TOPO, g_surf::cols, G_warning(), gs_get_att_typbuff(), NULL, and g_surf::rows.

Referenced by gsdrape_get_allsegments(), and gsdrape_get_segments().

int in_vregion ( geosurf gs,
float *  pt 
)

ADD.

Parameters
gssurface (geosurf)
Returns
1
0

Definition at line 696 of file gsdrape.c.

References VCOL2X, VCOLS, VROW2Y, VROWS, and g_surf::yrange.

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().

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

ADD.

Parameters
gssurface (geosurf)
bgnbegin point
endend point
ffirst
llast

Definition at line 441 of file gsdrape.c.

References g_surf::att, ATT_TOPO, gsurf_att::constant, viewcell_tri_interp(), X, Y, and Z.

Referenced by gsdrape_get_allsegments(), and gsdrape_get_segments().

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
gssurface (geosurf)
firstfirst point
lastlast point
vi
hi
di
Returns

Definition at line 729 of file gsdrape.c.

References EPSILON, EQUAL, G_debug(), in_vregion(), num, X, g_surf::xrange, Y, g_surf::yrange, and Z.

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

Define plane.

Parameters
p1,p2,p3three point on plane
[out]planeplane defintion
Returns
1

Definition at line 1335 of file gsdrape.c.

References V3Cross(), W, X, Y, and Z.

Referenced by 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
p1,p2,p3points defining plane
unkpoint
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().

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
gssurface (geosurf)
bgnbegin point
endend 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().

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
x1,y1,x2,y2coordinates of endpoints of one segment
x3,y3,x4,y4coordinates of endpoints of other segment
[out]x,ycoordinates 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, num, and SAME_SIGNS.

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

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

Get cross product.

Parameters
a,b,c
Returns
cross product c = a cross b

Definition at line 1365 of file gsdrape.c.

References X, Y, and Z.

Referenced by P3toPlane().

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.

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

Definition at line 507 of file gsdrape.c.

References g_surf::att, ATT_TOPO, CONST_ATT, gsurf_att::constant, DRC2OFF, GET_MAPATT, gs_get_att_src(), gs_point_is_masked(), LERP, MAP_ATT, Point_on_plane(), VCOL2DCOL, VCOL2X, VCOLS, VROW2DROW, VROW2Y, VROWS, VXRES, VYRES, X, X2VCOL, Y, Y2VROW, g_surf::yrange, and Z.

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

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
[out]intersectintersect coordinates
planeplane definition
Returns
0 doesn't intersect
1 intesects

Definition at line 1312 of file gsdrape.c.

References W, x, X, Y, and Z.

Referenced by Point_on_plane().