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

#include <stdlib.h>
#include <grass/gstypes.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...

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

Point3 *	gsdrape_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.

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,
		h
	)	((l)+(((h)-(l))*(a)))

Definition at line 63 of file gsdrape.c.

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

#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

gs	surface (geosurf)
pt

Definition at line 467 of file gsdrape.c.

References buf, 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

gs	surface (geosurf)
bgn	begin point
end	end point
dir	? (unused)

Returns: number of intersects

Definition at line 1074 of file gsdrape.c.

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

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

Get horizontal intersects.

Parameters

gs	surface (geosurf)
bgn	begin point
end	end point
dir

Returns: number of intersects

Definition at line 978 of file gsdrape.c.

References dialogs::cols, DRC2OFF, EPSILON, GET_MAPATT, if(), LERP, num, segs_intersect(), VCOLS, VROW2Y, VROWS, VXRES, VYRES, X, X2VCOL, Y, and Y2VROW.

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

gs	surface (geosurf)
bgn	begin point
end	end point
dir	direction

Returns

Definition at line 882 of file gsdrape.c.

References dialogs::cols, DRC2OFF, EPSILON, GET_MAPATT, if(), LERP, num, segs_intersect(), VCOL2X, VCOLS, VROWS, VXRES, VYRES, X, X2VCOL, Y, and Y2VROW.

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

Get all segments.

Parameters

gs	surface (geosurf)
bgn	begin point
end	end point
num

Returns: pointer to Point3 struct

Definition at line 401 of file gsdrape.c.

References 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

gs	surface (geosurf)
bgn	begin point (x,y)
end	end point (x,y)
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(), NULL, seg_intersect_vregion(), X, and Y.

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

gs	surface (geosurf)

Returns: -1 on failure; 1 on success

Definition at line 199 of file gsdrape.c.

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

Referenced by gsdrape_get_allsegments(), and gsdrape_get_segments().

int in_vregion	(	geosurf *	gs,
		float *	pt
	)

ADD.

Parameters

gs	surface (geosurf)

Returns: 1; 0

Definition at line 696 of file gsdrape.c.

References VCOL2X, VCOLS, VROW2Y, and VROWS.

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

gs	surface (geosurf)
bgn	begin point
end	end point
f	first
l	last

Definition at line 441 of file gsdrape.c.

References viewcell_tri_interp(), X, and Y.

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

gs	surface (geosurf)
first	first point
last	last point
vi
hi
di

Returns

Definition at line 729 of file gsdrape.c.

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

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

Define plane.

Parameters

	p1,p2,p3	three point on plane
[out]	plane	plane defintion

Returns: 1

Definition at line 1335 of file gsdrape.c.

References V3Cross(), X, and Y.

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,p3	points defining plane
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().

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)
bgn	begin point
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().

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,y2	coordinates of endpoints of one segment
	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, 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, and Y.

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.