3 * Mesa 3-D graphics library
5 * Copyright (C) 1995-2000 Brian Paul
7 * This library is free software; you can redistribute it and/or
8 * modify it under the terms of the GNU Library General Public
9 * License as published by the Free Software Foundation; either
10 * version 2 of the License, or (at your option) any later version.
12 * This library is distributed in the hope that it will be useful,
13 * but WITHOUT ANY WARRANTY; without even the implied warranty of
14 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
15 * Library General Public License for more details.
17 * You should have received a copy of the GNU Library General Public
18 * License along with this library; if not, write to the Free
19 * Software Foundation, Inc., 675 Mass Ave, Cambridge, MA 02139, USA.
24 * NURBS implementation written by Bogdan Sikorski (bogdan@cira.it)
25 * See README2 for more info.
39 GLenum
test_knot(GLint nknots
, GLfloat
* knot
, GLint order
)
47 for (i
= 1; i
< nknots
; i
++) {
48 if (knot
[i
] < tmp_knot
)
49 return GLU_NURBS_ERROR4
;
50 if (fabs(tmp_knot
- knot
[i
]) > EPSILON
) {
51 if (knot_mult
> order
)
52 return GLU_NURBS_ERROR5
;
64 #if defined(WIN32) && !defined(OPENSTEP)
67 knot_sort(const void *a
, const void *b
)
73 if (fabs(x
- y
) < EPSILON
)
80 /* insert into dest knot all values within the valid range from src knot */
81 /* that do not appear in dest */
83 collect_unified_knot(knot_str_type
* dest
, knot_str_type
* src
,
84 GLfloat maximal_min_knot
, GLfloat minimal_max_knot
)
86 GLfloat
*src_knot
, *dest_knot
;
87 GLint src_t_min
, src_t_max
, dest_t_min
, dest_t_max
;
88 GLint src_nknots
, dest_nknots
;
89 GLint i
, j
, k
, new_cnt
;
90 GLboolean not_found_flag
;
92 src_knot
= src
->unified_knot
;
93 dest_knot
= dest
->unified_knot
;
94 src_t_min
= src
->t_min
;
95 src_t_max
= src
->t_max
;
96 dest_t_min
= dest
->t_min
;
97 dest_t_max
= dest
->t_max
;
98 src_nknots
= src
->unified_nknots
;
99 dest_nknots
= dest
->unified_nknots
;
101 k
= new_cnt
= dest_nknots
;
102 for (i
= src_t_min
; i
<= src_t_max
; i
++)
103 if (src_knot
[i
] - maximal_min_knot
> -EPSILON
&&
104 src_knot
[i
] - minimal_max_knot
< EPSILON
) {
105 not_found_flag
= GL_TRUE
;
106 for (j
= dest_t_min
; j
<= dest_t_max
; j
++)
107 if (fabs(dest_knot
[j
] - src_knot
[i
]) < EPSILON
) {
108 not_found_flag
= GL_FALSE
;
111 if (not_found_flag
) {
112 /* knot from src is not in dest - add this knot to dest */
113 dest_knot
[k
++] = src_knot
[i
];
115 ++(dest
->t_max
); /* the valid range widens */
116 ++(dest
->delta_nknots
); /* increment the extra knot value counter */
119 dest
->unified_nknots
= new_cnt
;
120 qsort((void *) dest_knot
, (size_t) new_cnt
, (size_t) sizeof(GLfloat
),
124 /* basing on the new common knot range for all attributes set */
125 /* t_min and t_max values for each knot - they will be used later on */
126 /* by explode_knot() and calc_new_ctrl_pts */
128 set_new_t_min_t_max(knot_str_type
* geom_knot
, knot_str_type
* color_knot
,
129 knot_str_type
* normal_knot
, knot_str_type
* texture_knot
,
130 GLfloat maximal_min_knot
, GLfloat minimal_max_knot
)
132 GLuint t_min
= 0, t_max
= 0, cnt
= 0;
134 if (minimal_max_knot
- maximal_min_knot
< EPSILON
) {
135 /* knot common range empty */
136 geom_knot
->t_min
= geom_knot
->t_max
= 0;
137 color_knot
->t_min
= color_knot
->t_max
= 0;
138 normal_knot
->t_min
= normal_knot
->t_max
= 0;
139 texture_knot
->t_min
= texture_knot
->t_max
= 0;
142 if (geom_knot
->unified_knot
!= NULL
) {
143 cnt
= geom_knot
->unified_nknots
;
144 for (t_min
= 0; t_min
< cnt
; t_min
++)
145 if (fabs((geom_knot
->unified_knot
)[t_min
] - maximal_min_knot
) <
147 for (t_max
= cnt
- 1; t_max
; t_max
--)
148 if (fabs((geom_knot
->unified_knot
)[t_max
] - minimal_max_knot
) <
151 else if (geom_knot
->nknots
) {
152 cnt
= geom_knot
->nknots
;
153 for (t_min
= 0; t_min
< cnt
; t_min
++)
154 if (fabs((geom_knot
->knot
)[t_min
] - maximal_min_knot
) < EPSILON
)
156 for (t_max
= cnt
- 1; t_max
; t_max
--)
157 if (fabs((geom_knot
->knot
)[t_max
] - minimal_max_knot
) < EPSILON
)
160 geom_knot
->t_min
= t_min
;
161 geom_knot
->t_max
= t_max
;
162 if (color_knot
->unified_knot
!= NULL
) {
163 cnt
= color_knot
->unified_nknots
;
164 for (t_min
= 0; t_min
< cnt
; t_min
++)
165 if (fabs((color_knot
->unified_knot
)[t_min
] - maximal_min_knot
) <
167 for (t_max
= cnt
- 1; t_max
; t_max
--)
168 if (fabs((color_knot
->unified_knot
)[t_max
] - minimal_max_knot
) <
170 color_knot
->t_min
= t_min
;
171 color_knot
->t_max
= t_max
;
173 if (normal_knot
->unified_knot
!= NULL
) {
174 cnt
= normal_knot
->unified_nknots
;
175 for (t_min
= 0; t_min
< cnt
; t_min
++)
176 if (fabs((normal_knot
->unified_knot
)[t_min
] - maximal_min_knot
) <
178 for (t_max
= cnt
- 1; t_max
; t_max
--)
179 if (fabs((normal_knot
->unified_knot
)[t_max
] - minimal_max_knot
) <
181 normal_knot
->t_min
= t_min
;
182 normal_knot
->t_max
= t_max
;
184 if (texture_knot
->unified_knot
!= NULL
) {
185 cnt
= texture_knot
->unified_nknots
;
186 for (t_min
= 0; t_min
< cnt
; t_min
++)
187 if (fabs((texture_knot
->unified_knot
)[t_min
] - maximal_min_knot
)
190 for (t_max
= cnt
- 1; t_max
; t_max
--)
191 if (fabs((texture_knot
->unified_knot
)[t_max
] - minimal_max_knot
)
194 texture_knot
->t_min
= t_min
;
195 texture_knot
->t_max
= t_max
;
200 /* modify all knot valid ranges in such a way that all have the same */
201 /* range, common to all knots */
202 /* do this by knot insertion */
204 select_knot_working_range(GLUnurbsObj
* nobj
, knot_str_type
* geom_knot
,
205 knot_str_type
* color_knot
,
206 knot_str_type
* normal_knot
,
207 knot_str_type
* texture_knot
)
210 GLfloat maximal_min_knot
, minimal_max_knot
;
213 /* find the maximum modified knot length */
214 max_nknots
= geom_knot
->nknots
;
215 if (color_knot
->unified_knot
)
216 max_nknots
+= color_knot
->nknots
;
217 if (normal_knot
->unified_knot
)
218 max_nknots
+= normal_knot
->nknots
;
219 if (texture_knot
->unified_knot
)
220 max_nknots
+= texture_knot
->nknots
;
221 maximal_min_knot
= (geom_knot
->knot
)[geom_knot
->t_min
];
222 minimal_max_knot
= (geom_knot
->knot
)[geom_knot
->t_max
];
223 /* any attirb data ? */
224 if (max_nknots
!= geom_knot
->nknots
) {
225 /* allocate space for the unified knots */
226 if ((geom_knot
->unified_knot
=
227 (GLfloat
*) malloc(sizeof(GLfloat
) * max_nknots
)) == NULL
) {
228 call_user_error(nobj
, GLU_OUT_OF_MEMORY
);
231 /* copy the original knot to the unified one */
232 geom_knot
->unified_nknots
= geom_knot
->nknots
;
233 for (i
= 0; i
< geom_knot
->nknots
; i
++)
234 (geom_knot
->unified_knot
)[i
] = (geom_knot
->knot
)[i
];
235 if (color_knot
->unified_knot
) {
236 if ((color_knot
->knot
)[color_knot
->t_min
] - maximal_min_knot
>
238 maximal_min_knot
= (color_knot
->knot
)[color_knot
->t_min
];
239 if (minimal_max_knot
- (color_knot
->knot
)[color_knot
->t_max
] >
241 minimal_max_knot
= (color_knot
->knot
)[color_knot
->t_max
];
242 if ((color_knot
->unified_knot
=
243 (GLfloat
*) malloc(sizeof(GLfloat
) * max_nknots
)) == NULL
) {
244 free(geom_knot
->unified_knot
);
245 call_user_error(nobj
, GLU_OUT_OF_MEMORY
);
248 /* copy the original knot to the unified one */
249 color_knot
->unified_nknots
= color_knot
->nknots
;
250 for (i
= 0; i
< color_knot
->nknots
; i
++)
251 (color_knot
->unified_knot
)[i
] = (color_knot
->knot
)[i
];
253 if (normal_knot
->unified_knot
) {
254 if ((normal_knot
->knot
)[normal_knot
->t_min
] - maximal_min_knot
>
256 maximal_min_knot
= (normal_knot
->knot
)[normal_knot
->t_min
];
257 if (minimal_max_knot
- (normal_knot
->knot
)[normal_knot
->t_max
] >
259 minimal_max_knot
= (normal_knot
->knot
)[normal_knot
->t_max
];
260 if ((normal_knot
->unified_knot
=
261 (GLfloat
*) malloc(sizeof(GLfloat
) * max_nknots
)) == NULL
) {
262 free(geom_knot
->unified_knot
);
263 free(color_knot
->unified_knot
);
264 call_user_error(nobj
, GLU_OUT_OF_MEMORY
);
267 /* copy the original knot to the unified one */
268 normal_knot
->unified_nknots
= normal_knot
->nknots
;
269 for (i
= 0; i
< normal_knot
->nknots
; i
++)
270 (normal_knot
->unified_knot
)[i
] = (normal_knot
->knot
)[i
];
272 if (texture_knot
->unified_knot
) {
273 if ((texture_knot
->knot
)[texture_knot
->t_min
] - maximal_min_knot
>
275 maximal_min_knot
= (texture_knot
->knot
)[texture_knot
->t_min
];
276 if (minimal_max_knot
- (texture_knot
->knot
)[texture_knot
->t_max
] >
278 minimal_max_knot
= (texture_knot
->knot
)[texture_knot
->t_max
];
279 if ((texture_knot
->unified_knot
=
280 (GLfloat
*) malloc(sizeof(GLfloat
) * max_nknots
)) == NULL
) {
281 free(geom_knot
->unified_knot
);
282 free(color_knot
->unified_knot
);
283 free(normal_knot
->unified_knot
);
284 call_user_error(nobj
, GLU_OUT_OF_MEMORY
);
287 /* copy the original knot to the unified one */
288 texture_knot
->unified_nknots
= texture_knot
->nknots
;
289 for (i
= 0; i
< texture_knot
->nknots
; i
++)
290 (texture_knot
->unified_knot
)[i
] = (texture_knot
->knot
)[i
];
292 /* work on the geometry knot with all additional knot values */
293 /* appearing in attirbutive knots */
294 if (minimal_max_knot
- maximal_min_knot
< EPSILON
) {
295 /* empty working range */
296 geom_knot
->unified_nknots
= 0;
297 color_knot
->unified_nknots
= 0;
298 normal_knot
->unified_nknots
= 0;
299 texture_knot
->unified_nknots
= 0;
302 if (color_knot
->unified_knot
)
303 collect_unified_knot(geom_knot
, color_knot
, maximal_min_knot
,
305 if (normal_knot
->unified_knot
)
306 collect_unified_knot(geom_knot
, normal_knot
, maximal_min_knot
,
308 if (texture_knot
->unified_knot
)
309 collect_unified_knot(geom_knot
, texture_knot
, maximal_min_knot
,
311 /* since we have now built the "unified" geometry knot */
312 /* add same knot values to all attributive knots */
313 if (color_knot
->unified_knot
)
314 collect_unified_knot(color_knot
, geom_knot
, maximal_min_knot
,
316 if (normal_knot
->unified_knot
)
317 collect_unified_knot(normal_knot
, geom_knot
, maximal_min_knot
,
319 if (texture_knot
->unified_knot
)
320 collect_unified_knot(texture_knot
, geom_knot
, maximal_min_knot
,
324 set_new_t_min_t_max(geom_knot
, color_knot
, normal_knot
, texture_knot
,
325 maximal_min_knot
, minimal_max_knot
);
330 free_unified_knots(knot_str_type
* geom_knot
, knot_str_type
* color_knot
,
331 knot_str_type
* normal_knot
, knot_str_type
* texture_knot
)
333 if (geom_knot
->unified_knot
)
334 free(geom_knot
->unified_knot
);
335 if (color_knot
->unified_knot
)
336 free(color_knot
->unified_knot
);
337 if (normal_knot
->unified_knot
)
338 free(normal_knot
->unified_knot
);
339 if (texture_knot
->unified_knot
)
340 free(texture_knot
->unified_knot
);
343 GLenum
explode_knot(knot_str_type
* the_knot
)
345 GLfloat
*knot
, *new_knot
;
346 GLint nknots
, n_new_knots
= 0;
352 if (the_knot
->unified_knot
) {
353 knot
= the_knot
->unified_knot
;
354 nknots
= the_knot
->unified_nknots
;
357 knot
= the_knot
->knot
;
358 nknots
= the_knot
->nknots
;
360 ord
= the_knot
->order
;
361 t_min
= the_knot
->t_min
;
362 t_max
= the_knot
->t_max
;
364 for (i
= t_min
; i
<= t_max
;) {
366 for (j
= 0; j
< ord
&& (i
+ j
) <= t_max
; j
++)
367 if (fabs(tmp_float
- knot
[i
+ j
]) > EPSILON
)
369 n_new_knots
+= ord
- j
;
372 /* alloc space for new_knot */
375 (GLfloat
*) malloc(sizeof(GLfloat
) * (nknots
+ n_new_knots
+ 1))) == NULL
) {
376 return GLU_OUT_OF_MEMORY
;
378 /* fill in new knot */
379 for (j
= 0; j
< t_min
; j
++)
380 new_knot
[j
] = knot
[j
];
381 for (i
= j
; i
<= t_max
; i
++) {
383 for (k
= 0; k
< ord
; k
++) {
384 new_knot
[j
++] = knot
[i
];
385 if (tmp_float
== knot
[i
+ 1])
389 for (i
= t_max
+ 1; i
< (int) nknots
; i
++)
390 new_knot
[j
++] = knot
[i
];
391 /* fill in the knot structure */
392 the_knot
->new_knot
= new_knot
;
393 the_knot
->delta_nknots
+= n_new_knots
;
394 the_knot
->t_max
+= n_new_knots
;
398 GLenum
calc_alphas(knot_str_type
* the_knot
)
403 GLfloat
*alpha
, *alpha_new
, *tmp_alpha
;
405 GLfloat
*knot
, *new_knot
;
408 knot
= the_knot
->knot
;
409 order
= the_knot
->order
;
410 new_knot
= the_knot
->new_knot
;
411 n
= the_knot
->nknots
- the_knot
->order
;
412 m
= n
+ the_knot
->delta_nknots
;
413 if ((alpha
= (GLfloat
*) malloc(sizeof(GLfloat
) * n
* m
)) == NULL
) {
414 return GLU_OUT_OF_MEMORY
;
416 if ((alpha_new
= (GLfloat
*) malloc(sizeof(GLfloat
) * n
* m
)) == NULL
) {
418 return GLU_OUT_OF_MEMORY
;
420 for (j
= 0; j
< m
; j
++) {
421 for (i
= 0; i
< n
; i
++) {
422 if ((knot
[i
] <= new_knot
[j
]) && (new_knot
[j
] < knot
[i
+ 1]))
426 alpha
[i
+ j
* n
] = tmp_float
;
429 for (k
= 1; k
< order
; k
++) {
430 for (j
= 0; j
< m
; j
++)
431 for (i
= 0; i
< n
; i
++) {
432 denom
= knot
[i
+ k
] - knot
[i
];
433 if (fabs(denom
) < EPSILON
)
436 tmp_float
= (new_knot
[j
+ k
] - knot
[i
]) / denom
*
438 denom
= knot
[i
+ k
+ 1] - knot
[i
+ 1];
439 if (fabs(denom
) > EPSILON
)
440 tmp_float
+= (knot
[i
+ k
+ 1] - new_knot
[j
+ k
]) / denom
*
441 alpha
[(i
+ 1) + j
* n
];
442 alpha_new
[i
+ j
* n
] = tmp_float
;
444 tmp_alpha
= alpha_new
;
448 the_knot
->alpha
= alpha
;
454 calc_new_ctrl_pts(GLfloat
* ctrl
, GLint stride
, knot_str_type
* the_knot
,
455 GLint dim
, GLfloat
** new_ctrl
, GLint
* ncontrol
)
457 GLsizei i
, j
, k
, l
, m
, n
;
458 GLsizei index1
, index2
;
462 new_knot
= the_knot
->new_knot
;
463 n
= the_knot
->nknots
- the_knot
->order
;
464 alpha
= the_knot
->alpha
;
466 m
= the_knot
->t_max
+ 1 - the_knot
->t_min
- the_knot
->order
;
468 /* allocate space for new control points */
469 if ((*new_ctrl
= (GLfloat
*) malloc(sizeof(GLfloat
) * dim
* m
)) == NULL
) {
470 return GLU_OUT_OF_MEMORY
;
472 for (j
= 0; j
< m
; j
++) {
473 for (l
= 0; l
< dim
; l
++)
474 (*new_ctrl
)[j
* dim
+ l
] = 0.0;
475 for (i
= 0; i
< n
; i
++) {
476 index1
= i
+ (j
+ k
) * n
;
478 for (l
= 0; l
< dim
; l
++)
479 (*new_ctrl
)[j
* dim
+ l
] += alpha
[index1
] * ctrl
[index2
+ l
];
482 *ncontrol
= (GLint
) m
;
487 calc_factor(GLfloat
* pts
, GLint order
, GLint indx
, GLint stride
,
488 GLfloat tolerance
, GLint dim
)
490 GLdouble model
[16], proj
[16];
492 GLdouble x
, y
, z
, w
, winx1
, winy1
, winz
, winx2
, winy2
;
494 GLdouble len
, dx
, dy
;
496 glGetDoublev(GL_MODELVIEW_MATRIX
, model
);
497 glGetDoublev(GL_PROJECTION_MATRIX
, proj
);
498 glGetIntegerv(GL_VIEWPORT
, viewport
);
500 w
= (GLdouble
) pts
[indx
+ 3];
501 x
= (GLdouble
) pts
[indx
] / w
;
502 y
= (GLdouble
) pts
[indx
+ 1] / w
;
503 z
= (GLdouble
) pts
[indx
+ 2] / w
;
504 gluProject(x
, y
, z
, model
, proj
, viewport
, &winx1
, &winy1
, &winz
);
506 for (i
= 1; i
< order
; i
++) {
507 w
= (GLdouble
) pts
[indx
+ i
* stride
+ 3];
508 x
= (GLdouble
) pts
[indx
+ i
* stride
] / w
;
509 y
= (GLdouble
) pts
[indx
+ i
* stride
+ 1] / w
;
510 z
= (GLdouble
) pts
[indx
+ i
* stride
+ 2] / w
;
512 (x
, y
, z
, model
, proj
, viewport
, &winx2
, &winy2
, &winz
)) {
515 len
+= sqrt(dx
* dx
+ dy
* dy
);
522 x
= (GLdouble
) pts
[indx
];
523 y
= (GLdouble
) pts
[indx
+ 1];
527 z
= (GLdouble
) pts
[indx
+ 2];
528 gluProject(x
, y
, z
, model
, proj
, viewport
, &winx1
, &winy1
, &winz
);
530 for (i
= 1; i
< order
; i
++) {
531 x
= (GLdouble
) pts
[indx
+ i
* stride
];
532 y
= (GLdouble
) pts
[indx
+ i
* stride
+ 1];
536 z
= (GLdouble
) pts
[indx
+ i
* stride
+ 2];
538 (x
, y
, z
, model
, proj
, viewport
, &winx2
, &winy2
, &winz
)) {
541 len
+= sqrt(dx
* dx
+ dy
* dy
);
548 return ((GLint
) len
+ 1);
551 /* we can't use the Mesa evaluators - no way to get the point coords */
552 /* so we use our own Bezier point calculus routines */
553 /* because I'm lazy, I reuse the ones from eval.c */
556 bezier_curve(GLfloat
* cp
, GLfloat
* out
, GLfloat t
,
557 GLuint dim
, GLuint order
, GLint offset
)
560 GLuint i
, k
, bincoeff
;
563 bincoeff
= order
- 1;
566 for (k
= 0; k
< dim
; k
++)
567 out
[k
] = s
* cp
[k
] + bincoeff
* t
* cp
[offset
+ k
];
569 for (i
= 2, cp
+= 2 * offset
, powert
= t
* t
; i
< order
;
570 i
++, powert
*= t
, cp
+= offset
) {
571 bincoeff
*= order
- i
;
574 for (k
= 0; k
< dim
; k
++)
575 out
[k
] = s
* out
[k
] + bincoeff
* powert
* cp
[k
];
578 else { /* order=1 -> constant curve */
580 for (k
= 0; k
< dim
; k
++)
586 calc_parametric_factor(GLfloat
* pts
, GLint order
, GLint indx
, GLint stride
,
587 GLfloat tolerance
, GLint dim
)
589 GLdouble model
[16], proj
[16];
591 GLdouble x
, y
, z
, w
, x1
, y1
, z1
, x2
, y2
, z2
, x3
, y3
, z3
;
595 GLdouble len
= 0.0, tmp
, z_med
;
598 glGetDoublev(GL_MODELVIEW_MATRIX
, model
);
599 glGetDoublev(GL_PROJECTION_MATRIX
, proj
);
600 glGetIntegerv(GL_VIEWPORT
, viewport
);
601 z_med
= (viewport
[2] + viewport
[3]) * 0.5;
604 for (i
= 1; i
< P
; i
++) {
605 bezier_curve(pts
+ indx
, bez_pt
, (GLfloat
) i
/ (GLfloat
) P
, 4,
607 w
= (GLdouble
) bez_pt
[3];
608 x
= (GLdouble
) bez_pt
[0] / w
;
609 y
= (GLdouble
) bez_pt
[1] / w
;
610 z
= (GLdouble
) bez_pt
[2] / w
;
611 gluProject(x
, y
, z
, model
, proj
, viewport
, &x3
, &y3
, &z3
);
613 bezier_curve(pts
+ indx
, bez_pt
, (GLfloat
) (i
- 1) / (GLfloat
) P
, 4,
615 w
= (GLdouble
) bez_pt
[3];
616 x
= (GLdouble
) bez_pt
[0] / w
;
617 y
= (GLdouble
) bez_pt
[1] / w
;
618 z
= (GLdouble
) bez_pt
[2] / w
;
619 gluProject(x
, y
, z
, model
, proj
, viewport
, &x1
, &y1
, &z1
);
621 bezier_curve(pts
+ indx
, bez_pt
, (GLfloat
) (i
+ 1) / (GLfloat
) P
, 4,
623 w
= (GLdouble
) bez_pt
[3];
624 x
= (GLdouble
) bez_pt
[0] / w
;
625 y
= (GLdouble
) bez_pt
[1] / w
;
626 z
= (GLdouble
) bez_pt
[2] / w
;
627 gluProject(x
, y
, z
, model
, proj
, viewport
, &x2
, &y2
, &z2
);
629 /* calc distance between point (x3,y3,z3) and line segment */
630 /* <x1,y1,z1><x2,y2,z2> */
634 tmp
= sqrt(x
* x
+ y
* y
+ z
* z
);
638 tmp
= x3
* x
+ y3
* y
+ z3
* z
- x1
* x
- y1
* y
- z1
* z
;
639 x
= x1
+ x
* tmp
- x3
;
640 y
= y1
+ y
* tmp
- y3
;
641 z
= z1
+ z
* tmp
- z3
;
642 tmp
= sqrt(x
* x
+ y
* y
+ z
* z
);
648 for (i
= 1; i
< P
; i
++) {
649 bezier_curve(pts
+ indx
, bez_pt
, (GLfloat
) i
/ (GLfloat
) P
, 3,
651 x
= (GLdouble
) bez_pt
[0];
652 y
= (GLdouble
) bez_pt
[1];
653 z
= (GLdouble
) bez_pt
[2];
654 gluProject(x
, y
, z
, model
, proj
, viewport
, &x3
, &y3
, &z3
);
656 bezier_curve(pts
+ indx
, bez_pt
, (GLfloat
) (i
- 1) / (GLfloat
) P
, 3,
658 x
= (GLdouble
) bez_pt
[0];
659 y
= (GLdouble
) bez_pt
[1];
660 z
= (GLdouble
) bez_pt
[2];
661 gluProject(x
, y
, z
, model
, proj
, viewport
, &x1
, &y1
, &z1
);
663 bezier_curve(pts
+ indx
, bez_pt
, (GLfloat
) (i
+ 1) / (GLfloat
) P
, 3,
665 x
= (GLdouble
) bez_pt
[0];
666 y
= (GLdouble
) bez_pt
[1];
667 z
= (GLdouble
) bez_pt
[2];
668 gluProject(x
, y
, z
, model
, proj
, viewport
, &x2
, &y2
, &z2
);
670 /* calc distance between point (x3,y3,z3) and line segment */
671 /* <x1,y1,z1><x2,y2,z2> */
675 tmp
= sqrt(x
* x
+ y
* y
+ z
* z
);
679 tmp
= x3
* x
+ y3
* y
+ z3
* z
- x1
* x
- y1
* y
- z1
* z
;
680 x
= x1
+ x
* tmp
- x3
;
681 y
= y1
+ y
* tmp
- y3
;
682 z
= z1
+ z
* tmp
- z3
;
683 tmp
= sqrt(x
* x
+ y
* y
+ z
* z
);
689 for (i
= 1; i
< P
; i
++) {
690 bezier_curve(pts
+ indx
, bez_pt
, (GLfloat
) i
/ (GLfloat
) P
, 2,
692 x
= (GLdouble
) bez_pt
[0];
693 y
= (GLdouble
) bez_pt
[1];
695 gluProject(x
, y
, z
, model
, proj
, viewport
, &x3
, &y3
, &z3
);
697 bezier_curve(pts
+ indx
, bez_pt
, (GLfloat
) (i
- 1) / (GLfloat
) P
, 2,
699 x
= (GLdouble
) bez_pt
[0];
700 y
= (GLdouble
) bez_pt
[1];
702 gluProject(x
, y
, z
, model
, proj
, viewport
, &x1
, &y1
, &z1
);
704 bezier_curve(pts
+ indx
, bez_pt
, (GLfloat
) (i
+ 1) / (GLfloat
) P
, 2,
706 x
= (GLdouble
) bez_pt
[0];
707 y
= (GLdouble
) bez_pt
[1];
709 gluProject(x
, y
, z
, model
, proj
, viewport
, &x2
, &y2
, &z2
);
711 /* calc distance between point (x3,y3,z3) and line segment */
712 /* <x1,y1,z1><x2,y2,z2> */
716 tmp
= sqrt(x
* x
+ y
* y
+ z
* z
);
720 tmp
= x3
* x
+ y3
* y
+ z3
* z
- x1
* x
- y1
* y
- z1
* z
;
721 x
= x1
+ x
* tmp
- x3
;
722 y
= y1
+ y
* tmp
- y3
;
723 z
= z1
+ z
* tmp
- z3
;
724 tmp
= sqrt(x
* x
+ y
* y
+ z
* z
);
734 return (GLint
) (sqrt(len
/ tolerance
) * (order
+ 2) + 1);
738 calc_sampling_3D(new_ctrl_type
* new_ctrl
, GLfloat tolerance
, GLint dim
,
739 GLint uorder
, GLint vorder
, GLint
** ufactors
,
743 GLint tmp_factor1
, tmp_factor2
;
744 GLint ufactor_cnt
, vfactor_cnt
;
745 GLint offset1
, offset2
, offset3
;
748 ufactor_cnt
= new_ctrl
->s_bezier_cnt
;
749 vfactor_cnt
= new_ctrl
->t_bezier_cnt
;
750 if ((*ufactors
= (GLint
*) malloc(sizeof(GLint
) * ufactor_cnt
* 3))
752 return GLU_OUT_OF_MEMORY
;
754 if ((*vfactors
= (GLint
*) malloc(sizeof(GLint
) * vfactor_cnt
* 3))
757 return GLU_OUT_OF_MEMORY
;
759 ctrl
= new_ctrl
->geom_ctrl
;
760 offset1
= new_ctrl
->geom_t_stride
* vorder
;
761 offset2
= new_ctrl
->geom_s_stride
* uorder
;
762 for (j
= 0; j
< vfactor_cnt
; j
++) {
763 *(*vfactors
+ j
* 3 + 1) = tmp_factor1
= calc_factor(ctrl
, vorder
,
766 /* loop ufactor_cnt-1 times */
767 for (i
= 1; i
< ufactor_cnt
; i
++) {
768 tmp_factor2
= calc_factor(ctrl
, vorder
,
769 j
* offset1
+ i
* offset2
, dim
, tolerance
,
771 if (tmp_factor2
> tmp_factor1
)
772 tmp_factor1
= tmp_factor2
;
774 /* last time for the opposite edge */
775 *(*vfactors
+ j
* 3 + 2) = tmp_factor2
= calc_factor(ctrl
, vorder
,
781 if (tmp_factor2
> tmp_factor1
)
782 *(*vfactors
+ j
* 3) = tmp_factor2
;
784 *(*vfactors
+ j
* 3) = tmp_factor1
;
786 offset3
= new_ctrl
->geom_s_stride
;
787 offset2
= new_ctrl
->geom_s_stride
* uorder
;
788 for (j
= 0; j
< ufactor_cnt
; j
++) {
789 *(*ufactors
+ j
* 3 + 1) = tmp_factor1
= calc_factor(ctrl
, uorder
,
793 /* loop vfactor_cnt-1 times */
794 for (i
= 1; i
< vfactor_cnt
; i
++) {
795 tmp_factor2
= calc_factor(ctrl
, uorder
,
796 j
* offset2
+ i
* offset1
, offset3
,
798 if (tmp_factor2
> tmp_factor1
)
799 tmp_factor1
= tmp_factor2
;
801 /* last time for the opposite edge */
802 *(*ufactors
+ j
* 3 + 2) = tmp_factor2
= calc_factor(ctrl
, uorder
,
809 if (tmp_factor2
> tmp_factor1
)
810 *(*ufactors
+ j
* 3) = tmp_factor2
;
812 *(*ufactors
+ j
* 3) = tmp_factor1
;
818 calc_sampling_param_3D(new_ctrl_type
* new_ctrl
, GLfloat tolerance
, GLint dim
,
819 GLint uorder
, GLint vorder
, GLint
** ufactors
,
823 GLint tmp_factor1
, tmp_factor2
;
824 GLint ufactor_cnt
, vfactor_cnt
;
825 GLint offset1
, offset2
, offset3
;
828 ufactor_cnt
= new_ctrl
->s_bezier_cnt
;
829 vfactor_cnt
= new_ctrl
->t_bezier_cnt
;
830 if ((*ufactors
= (GLint
*) malloc(sizeof(GLint
) * ufactor_cnt
* 3))
832 return GLU_OUT_OF_MEMORY
;
834 if ((*vfactors
= (GLint
*) malloc(sizeof(GLint
) * vfactor_cnt
* 3))
837 return GLU_OUT_OF_MEMORY
;
839 ctrl
= new_ctrl
->geom_ctrl
;
840 offset1
= new_ctrl
->geom_t_stride
* vorder
;
841 offset2
= new_ctrl
->geom_s_stride
* uorder
;
842 for (j
= 0; j
< vfactor_cnt
; j
++) {
843 *(*vfactors
+ j
* 3 + 1) = tmp_factor1
=
844 calc_parametric_factor(ctrl
, vorder
, j
* offset1
, dim
, tolerance
,
846 /* loop ufactor_cnt-1 times */
847 for (i
= 1; i
< ufactor_cnt
; i
++) {
848 tmp_factor2
= calc_parametric_factor(ctrl
, vorder
,
849 j
* offset1
+ i
* offset2
, dim
,
851 if (tmp_factor2
> tmp_factor1
)
852 tmp_factor1
= tmp_factor2
;
854 /* last time for the opposite edge */
855 *(*vfactors
+ j
* 3 + 2) = tmp_factor2
=
856 calc_parametric_factor(ctrl
, vorder
,
857 j
* offset1
+ i
* offset2
-
858 new_ctrl
->geom_s_stride
, dim
, tolerance
, dim
);
859 if (tmp_factor2
> tmp_factor1
)
860 *(*vfactors
+ j
* 3) = tmp_factor2
;
862 *(*vfactors
+ j
* 3) = tmp_factor1
;
864 offset3
= new_ctrl
->geom_s_stride
;
865 offset2
= new_ctrl
->geom_s_stride
* uorder
;
866 for (j
= 0; j
< ufactor_cnt
; j
++) {
867 *(*ufactors
+ j
* 3 + 1) = tmp_factor1
=
868 calc_parametric_factor(ctrl
, uorder
, j
* offset2
, offset3
, tolerance
,
870 /* loop vfactor_cnt-1 times */
871 for (i
= 1; i
< vfactor_cnt
; i
++) {
872 tmp_factor2
= calc_parametric_factor(ctrl
, uorder
,
873 j
* offset2
+ i
* offset1
,
874 offset3
, tolerance
, dim
);
875 if (tmp_factor2
> tmp_factor1
)
876 tmp_factor1
= tmp_factor2
;
878 /* last time for the opposite edge */
879 *(*ufactors
+ j
* 3 + 2) = tmp_factor2
=
880 calc_parametric_factor(ctrl
, uorder
,
881 j
* offset2
+ i
* offset1
-
882 new_ctrl
->geom_t_stride
, offset3
, tolerance
,
884 if (tmp_factor2
> tmp_factor1
)
885 *(*ufactors
+ j
* 3) = tmp_factor2
;
887 *(*ufactors
+ j
* 3) = tmp_factor1
;
893 calc_sampling_2D(GLfloat
* ctrl
, GLint cnt
, GLint order
,
894 GLfloat tolerance
, GLint dim
, GLint
** factors
)
901 factor_cnt
= cnt
/ order
;
902 if ((*factors
= (GLint
*) malloc(sizeof(GLint
) * factor_cnt
)) == NULL
) {
903 return GLU_OUT_OF_MEMORY
;
905 offset
= order
* dim
;
906 for (i
= 0; i
< factor_cnt
; i
++) {
907 tmp_factor
= calc_factor(ctrl
, order
, i
* offset
, dim
, tolerance
, dim
);
911 (*factors
)[i
] = tmp_factor
;
917 set_sampling_and_culling(GLUnurbsObj
* nobj
)
919 if (nobj
->auto_load_matrix
== GL_FALSE
) {
923 glPushAttrib((GLbitfield
) (GL_VIEWPORT_BIT
| GL_TRANSFORM_BIT
));
924 for (i
= 0; i
< 4; i
++)
925 m
[i
] = nobj
->sampling_matrices
.viewport
[i
];
926 glViewport(m
[0], m
[1], m
[2], m
[3]);
927 glMatrixMode(GL_PROJECTION
);
929 glLoadMatrixf(nobj
->sampling_matrices
.proj
);
930 glMatrixMode(GL_MODELVIEW
);
932 glLoadMatrixf(nobj
->sampling_matrices
.model
);
937 revert_sampling_and_culling(GLUnurbsObj
* nobj
)
939 if (nobj
->auto_load_matrix
== GL_FALSE
) {
940 glMatrixMode(GL_MODELVIEW
);
942 glMatrixMode(GL_PROJECTION
);
949 glu_do_sampling_3D(GLUnurbsObj
* nobj
, new_ctrl_type
* new_ctrl
,
950 GLint
** sfactors
, GLint
** tfactors
)
957 dim
= nobj
->surface
.geom
.dim
;
958 set_sampling_and_culling(nobj
);
959 if ((err
= calc_sampling_3D(new_ctrl
, nobj
->sampling_tolerance
, dim
,
960 nobj
->surface
.geom
.sorder
,
961 nobj
->surface
.geom
.torder
, sfactors
,
962 tfactors
)) == GLU_ERROR
) {
963 revert_sampling_and_culling(nobj
);
964 call_user_error(nobj
, err
);
967 revert_sampling_and_culling(nobj
);
972 glu_do_sampling_uv(GLUnurbsObj
* nobj
, new_ctrl_type
* new_ctrl
,
973 GLint
** sfactors
, GLint
** tfactors
)
975 GLint s_cnt
, t_cnt
, i
;
976 GLint u_steps
, v_steps
;
978 s_cnt
= new_ctrl
->s_bezier_cnt
;
979 t_cnt
= new_ctrl
->t_bezier_cnt
;
982 if ((*sfactors
= (GLint
*) malloc(sizeof(GLint
) * s_cnt
* 3))
984 return GLU_OUT_OF_MEMORY
;
986 if ((*tfactors
= (GLint
*) malloc(sizeof(GLint
) * t_cnt
* 3))
989 return GLU_OUT_OF_MEMORY
;
991 u_steps
= nobj
->u_step
;
992 v_steps
= nobj
->v_step
;
993 for (i
= 0; i
< s_cnt
; i
++) {
994 *(*sfactors
+ i
* 3) = u_steps
;
995 *(*sfactors
+ i
* 3 + 1) = u_steps
;
996 *(*sfactors
+ i
* 3 + 2) = u_steps
;
998 for (i
= 0; i
< t_cnt
; i
++) {
999 *(*tfactors
+ i
* 3) = v_steps
;
1000 *(*tfactors
+ i
* 3 + 1) = v_steps
;
1001 *(*tfactors
+ i
* 3 + 2) = v_steps
;
1003 return GLU_NO_ERROR
;
1008 glu_do_sampling_param_3D(GLUnurbsObj
* nobj
, new_ctrl_type
* new_ctrl
,
1009 GLint
** sfactors
, GLint
** tfactors
)
1016 dim
= nobj
->surface
.geom
.dim
;
1017 set_sampling_and_culling(nobj
);
1020 calc_sampling_param_3D(new_ctrl
, nobj
->parametric_tolerance
, dim
,
1021 nobj
->surface
.geom
.sorder
,
1022 nobj
->surface
.geom
.torder
, sfactors
,
1023 tfactors
)) == GLU_ERROR
) {
1024 revert_sampling_and_culling(nobj
);
1025 call_user_error(nobj
, err
);
1028 revert_sampling_and_culling(nobj
);
1029 return GLU_NO_ERROR
;
1034 glu_do_sampling_2D(GLUnurbsObj
* nobj
, GLfloat
* ctrl
, GLint cnt
, GLint order
,
1035 GLint dim
, GLint
** factors
)
1039 set_sampling_and_culling(nobj
);
1040 err
= calc_sampling_2D(ctrl
, cnt
, order
, nobj
->sampling_tolerance
, dim
,
1042 revert_sampling_and_culling(nobj
);
1048 glu_do_sampling_u(GLUnurbsObj
* nobj
, GLfloat
* ctrl
, GLint cnt
, GLint order
,
1049 GLint dim
, GLint
** factors
)
1055 if ((*factors
= (GLint
*) malloc(sizeof(GLint
) * cnt
))
1057 return GLU_OUT_OF_MEMORY
;
1059 u_steps
= nobj
->u_step
;
1060 for (i
= 0; i
< cnt
; i
++)
1061 (*factors
)[i
] = u_steps
;
1062 return GLU_NO_ERROR
;
1067 glu_do_sampling_param_2D(GLUnurbsObj
* nobj
, GLfloat
* ctrl
, GLint cnt
,
1068 GLint order
, GLint dim
, GLint
** factors
)
1074 set_sampling_and_culling(nobj
);
1075 tolerance
= nobj
->parametric_tolerance
;
1077 if ((*factors
= (GLint
*) malloc(sizeof(GLint
) * cnt
))
1079 revert_sampling_and_culling(nobj
);
1080 return GLU_OUT_OF_MEMORY
;
1082 u_steps
= nobj
->u_step
;
1083 for (i
= 0; i
< cnt
; i
++) {
1084 (*factors
)[i
] = calc_parametric_factor(ctrl
, order
, 0,
1085 dim
, tolerance
, dim
);
1088 revert_sampling_and_culling(nobj
);
1089 return GLU_NO_ERROR
;
1093 glu_do_sampling_crv(GLUnurbsObj
* nobj
, GLfloat
* ctrl
, GLint cnt
,
1094 GLint order
, GLint dim
, GLint
** factors
)
1099 switch (nobj
->sampling_method
) {
1100 case GLU_PATH_LENGTH
:
1101 if ((err
= glu_do_sampling_2D(nobj
, ctrl
, cnt
, order
, dim
, factors
)) !=
1103 call_user_error(nobj
, err
);
1107 case GLU_DOMAIN_DISTANCE
:
1108 if ((err
= glu_do_sampling_u(nobj
, ctrl
, cnt
, order
, dim
, factors
)) !=
1110 call_user_error(nobj
, err
);
1114 case GLU_PARAMETRIC_ERROR
:
1117 glu_do_sampling_param_2D(nobj
, ctrl
, cnt
, order
, dim
,
1118 factors
)) != GLU_NO_ERROR
) {
1119 call_user_error(nobj
, err
);
1127 return GLU_NO_ERROR
;
1130 /* TODO - i don't like this culling - this one just tests if at least one */
1131 /* ctrl point lies within the viewport . Also the point_in_viewport() */
1132 /* should be included in the fnctions for efficiency reasons */
1135 point_in_viewport(GLfloat
* pt
, GLint dim
)
1137 GLdouble model
[16], proj
[16];
1139 GLdouble x
, y
, z
, w
, winx
, winy
, winz
;
1141 glGetDoublev(GL_MODELVIEW_MATRIX
, model
);
1142 glGetDoublev(GL_PROJECTION_MATRIX
, proj
);
1143 glGetIntegerv(GL_VIEWPORT
, viewport
);
1145 x
= (GLdouble
) pt
[0];
1146 y
= (GLdouble
) pt
[1];
1147 z
= (GLdouble
) pt
[2];
1148 gluProject(x
, y
, z
, model
, proj
, viewport
, &winx
, &winy
, &winz
);
1151 w
= (GLdouble
) pt
[3];
1152 x
= (GLdouble
) pt
[0] / w
;
1153 y
= (GLdouble
) pt
[1] / w
;
1154 z
= (GLdouble
) pt
[2] / w
;
1155 gluProject(x
, y
, z
, model
, proj
, viewport
, &winx
, &winy
, &winz
);
1157 if ((GLint
) winx
>= viewport
[0] && (GLint
) winx
< viewport
[2] &&
1158 (GLint
) winy
>= viewport
[1] && (GLint
) winy
< viewport
[3])
1164 fine_culling_test_3D(GLUnurbsObj
* nobj
, GLfloat
* pts
, GLint s_cnt
,
1165 GLint t_cnt
, GLint s_stride
, GLint t_stride
, GLint dim
)
1169 if (nobj
->culling
== GL_FALSE
)
1171 set_sampling_and_culling(nobj
);
1174 for (i
= 0; i
< s_cnt
; i
++)
1175 for (j
= 0; j
< t_cnt
; j
++)
1176 if (point_in_viewport(pts
+ i
* s_stride
+ j
* t_stride
, dim
)) {
1177 revert_sampling_and_culling(nobj
);
1182 for (i
= 0; i
< s_cnt
; i
++)
1183 for (j
= 0; j
< t_cnt
; j
++)
1184 if (point_in_viewport(pts
+ i
* s_stride
+ j
* t_stride
, dim
)) {
1185 revert_sampling_and_culling(nobj
);
1189 revert_sampling_and_culling(nobj
);
1194 fine_culling_test_3D(GLUnurbsObj *nobj,GLfloat *pts,GLint s_cnt,GLint t_cnt,
1195 GLint s_stride,GLint t_stride, GLint dim)
1198 GLfloat feedback_buffer[5];
1199 GLsizei buffer_size;
1202 if(nobj->culling==GL_FALSE)
1205 set_sampling_and_culling(nobj);
1207 glFeedbackBuffer(buffer_size,GL_2D,feedback_buffer);
1208 glRenderMode(GL_FEEDBACK);
1211 for(i=0;i<s_cnt;i++)
1213 glBegin(GL_LINE_LOOP);
1214 for(j=0;j<t_cnt;j++)
1215 glVertex3fv(pts+i*s_stride+j*t_stride);
1218 for(j=0;j<t_cnt;j++)
1220 glBegin(GL_LINE_LOOP);
1221 for(i=0;i<s_cnt;i++)
1222 glVertex3fv(pts+i*s_stride+j*t_stride);
1228 for(i=0;i<s_cnt;i++)
1230 glBegin(GL_LINE_LOOP);
1231 for(j=0;j<t_cnt;j++)
1232 glVertex4fv(pts+i*s_stride+j*t_stride);
1235 for(j=0;j<t_cnt;j++)
1237 glBegin(GL_LINE_LOOP);
1238 for(i=0;i<s_cnt;i++)
1239 glVertex4fv(pts+i*s_stride+j*t_stride);
1243 visible_cnt=glRenderMode(GL_RENDER);
1245 revert_sampling_and_culling(nobj);
1246 return (GLboolean)(visible_cnt==0);
1250 fine_culling_test_2D(GLUnurbsObj
* nobj
, GLfloat
* pts
, GLint cnt
,
1251 GLint stride
, GLint dim
)
1255 if (nobj
->culling
== GL_FALSE
)
1257 set_sampling_and_culling(nobj
);
1260 for (i
= 0; i
< cnt
; i
++)
1261 if (point_in_viewport(pts
+ i
* stride
, dim
)) {
1262 revert_sampling_and_culling(nobj
);
1267 for (i
= 0; i
< cnt
; i
++)
1268 if (point_in_viewport(pts
+ i
* stride
, dim
)) {
1269 revert_sampling_and_culling(nobj
);
1273 revert_sampling_and_culling(nobj
);
1278 fine_culling_test_2D(GLUnurbsObj *nobj,GLfloat *pts,GLint cnt,
1279 GLint stride, GLint dim)
1282 GLfloat feedback_buffer[5];
1283 GLsizei buffer_size;
1286 if(nobj->culling==GL_FALSE)
1289 set_sampling_and_culling(nobj);
1291 glFeedbackBuffer(buffer_size,GL_2D,feedback_buffer);
1292 glRenderMode(GL_FEEDBACK);
1293 glBegin(GL_LINE_LOOP);
1297 glVertex3fv(pts+i*stride);
1302 glVertex4fv(pts+i*stride);
1305 visible_cnt=glRenderMode(GL_RENDER);
1307 revert_sampling_and_culling(nobj);
1308 return (GLboolean)(visible_cnt==0);