1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
|
/*
* vrwpick.c - VRwave picking
* Copyright (c) 1995,96,97 IICM
*
* created: mpichler, 19970724 (based on VRweb picking code)
*
* changed: mpichler, 19970724
*
* $Id: vrwpick.c,v 1.1 1997/07/25 11:39:20 mpichler Exp $
*/
#ifdef __cplusplus
extern "C" {
#endif
#include "Picker.h"
#ifdef __cplusplus
} // C++
#endif
#ifdef macintosh
# include <vectors.h>
# include <ge3d.h>
# define M_PI _PI
# define PACKAGE iicm_vrml_vrwave_
#else
# include <ge3d/vectors.h>
# include <ge3d/ge3d.h>
#endif
#include "jutils.h"
#include <math.h>
#include <stdio.h> /* debugging */
/* usage: Debug ((stderr, "format", arguments)) */
#if 0
#define Debug(body) fprintf body
#else
#define Debug(body) /**/
#endif
/*
* Intersection test between a line from P towards infinity +y and and
* edge from A to B; lines passing through a vertex point tangentially
* do not change the intersection count
* projection axis paxis: which coordinate to discard (0, 1, 2)
* Author: Keith Andrews <kandrews@iicm>
* adaption for projections of 3D points: Michael Pichler
*/
static int Intersection (
const point3D* p,
const point3D* a,
const point3D* b,
int paxis
)
{
register point2D P, A, B; /* test point, leftmost, and rightmost point */
#define ASSIGN(u,v) \
{ \
init2D (P, p->u, p->v); \
if (a->u < b->u) \
init2D (A, a->u, a->v), init2D (B, b->u, b->v); \
else \
init2D (A, b->u, b->v), init2D (B, a->u, a->v); \
} /* now A.u <= B.u */
if (!paxis) /* discard x */
ASSIGN (y,z)
else if (paxis == 1) /* discard y */
ASSIGN (x,z)
else /* discard z */
ASSIGN (x,y)
#undef ASSIGN
/* check intersection */
if (A.x < P.x && B.x >= P.x) /* cases 1, 3, 5, 6 */
if (A.y > P.y) { /* cases 1, 6 */
if ((B.y > P.y) || /* case 1 or */
(A.y + ((B.y-A.y)/(B.x-A.x))*(P.x-A.x) > P.y)) /* case 6a */
return 1; /* count intersection */
}
else { /* cases 3, 5 */
if (A.y + ((B.y-A.y)/(B.x-A.x))*(P.x-A.x) > P.y) /* case 5a */
return 1; /* count intersection */
}
return 0;
} /* Intersection */
/* rayhitsfaceset */
/* test whether ray hits IndexedFaceset */
/*
* the FaceSet hit test used here projects each face to one of the
* three planes formed by the coordinate axis (by throwing away the
* largest absolute coordinate in the normal; see Foley/v.Dam p. 704)
* and does a 2D intersection test. This test works also for arbitrary
* vertex order and non-convex polygons.
*/
/* compare with QvIndexedFaceSet::pick of VRweb */
float name2(PACKAGE,Picker_rayhitsfaceset) (struct name3(H,PACKAGE,Picker)* handle,
HArrayOfFloat* hraystart, HArrayOfFloat* hraydir, float raynear, float rayfar, /* picking ray */
HArrayOfFloat* hverts, /* vertices */
jn_int32 numcoordinds, HArrayOfInt* hcoordinds, /* vertex indices */
HArrayOfFloat* hfnormals, /* face normal vectors */
jn_boolean twosided, /* whether to pick backfaces too */
HArrayOfFloat* hhitnormal /* out: normal vector at hitpoint (if non-NULL) */
) /* return value: hittime or 0 if no hit */
{
const vector3D* ray_A = (const vector3D*) unhand (hraystart)->body;
const vector3D* ray_b = (const vector3D*) unhand (hraydir)->body;
const point3D* vertexlist = (const point3D*) unhand (hverts)->body;
int nv = numcoordinds;
const int* cind = (const int*) unhand (hcoordinds)->body;
const vector3D* fn = (const vector3D*) unhand (hfnormals)->body;
vector3D* hitnormal = hhitnormal ? (vector3D*) unhand (hhitnormal) : 0;
point3D hitpoint;
const point3D *p, *q;
float hit, denom; /* for current face */
float hittime = 0.0f; /* return value */
int paxis;
while (nv)
{
/* here at the beginning of a new face */
int v0 = cind [0];
int v1 = cind [1];
int v2 = cind [2];
if (v0 >= 0 && v1 >= 0 && v2 >= 0 && nv > 2)
{
Debug ((stderr, "picking face %d, %d, %d ...: ", v0, v1, v2));
/* *fn ... curent face normal */
if ((denom = dot3D (*fn, *ray_b)) < 0 || (twosided && denom)) /* entering ray or twosided */
{
/* hit time: <n.(P-A)>/<n.b> */
p = vertexlist + v0;
sub3D (*p, *ray_A, hitpoint); /* not yet the hitpoint */
hit = dot3D (*fn, hitpoint) / denom;
if (raynear < hit && hit < rayfar) /* this face plane hit first */
{
unsigned intersect = 0; /* odd-even intersection test */
/* compute the hit point and check wheter it lies within the face */
pol3D (*ray_A, hit, *ray_b, hitpoint);
/* projection direction: largest abs. value of face normal */
/* might precompute this during build */
paxis = 0; /* x */
{
float nmax = fabs (fn->x);
if (fabs (fn->y) > nmax)
{ paxis = 1; /* y */
nmax = fabs (fn->y);
}
if (fabs (fn->z) > nmax)
paxis = 2; /* z */
}
Debug ((stderr, "+%d ", paxis));
q = vertexlist + v0;
while (nv > 1 && cind[1] >= 0)
{ /* test edge cind[0] to cind[1] (well defined when nv > 1) */
p = q;
Debug ((stderr, "{%d/%d}", cind[0], cind[1]));
q = vertexlist + *++cind;
nv--;
intersect += Intersection (&hitpoint, p, q, paxis);
/* int val = Intersection (&hitpoint, p, q, paxis); intersect += val; cerr << '=' << val << ' '; */
}
p = q; /* last edge (back to v0) */
q = vertexlist + v0;
Debug ((stderr, "{%d/%d}", cind[0], v0));
intersect += Intersection (&hitpoint, p, q, paxis);
/* int val = Intersection (&hitpoint, p, q, paxis); intersect += val; cerr << '=' << val << ' '; */
Debug ((stderr, " i = %d\n", intersect));
if (intersect & 0x1) /* hitpoint found */
{ /* HITENCOUNTERED */
hittime = rayfar = hit; /* search next hit */
if (hitnormal)
*hitnormal = *fn;
}
} /* nearest face */
} /* entering ray or twosided */
} /* face with at least 3 vertices */
/* faces with less than 3 vertices are not drawn and therefore not picked */
/* (see OpenGL Programming Guide, p. 36.: GL_POLYGON) */
/* goto next face */
fn++;
while (*cind >= 0 && nv)
cind++, nv--;
if (nv) /* skip index -1 (face separator) */
cind++, nv--;
} /* for all faces */
/* reverse normal vector if hit occured from back side */
if (hittime && hitnormal)
{
if (dot3D (*hitnormal, *ray_b) > 0)
neg3D (*hitnormal);
}
return hittime;
} /* rayhitsfaceset */
|
