BRL-CAD
nurb_tess.c
Go to the documentation of this file.
1 /* N U R B _ T E S S . C
2  * BRL-CAD
3  *
4  * Copyright (c) 1990-2014 United States Government as represented by
5  * the U.S. Army Research Laboratory.
6  *
7  * This library is free software; you can redistribute it and/or
8  * modify it under the terms of the GNU Lesser General Public License
9  * version 2.1 as published by the Free Software Foundation.
10  *
11  * This library is distributed in the hope that it will be useful, but
12  * WITHOUT ANY WARRANTY; without even the implied warranty of
13  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
14  * Lesser General Public License for more details.
15  *
16  * You should have received a copy of the GNU Lesser General Public
17  * License along with this file; see the file named COPYING for more
18  * information.
19  */
20 /** @addtogroup nurb */
21 /** @{ */
22 /** @file primitives/bspline/nurb_tess.c
23  *
24  * Given Epsilon, compute the number of internal knots to add so that
25  * every triangle generated in parametric space is within epsilon of
26  * the original surface.
27  *
28  */
29 /** @} */
30 
31 #include "common.h"
32 
33 #include <math.h>
34 #include "bio.h"
35 
36 #include "vmath.h"
37 #include "raytrace.h"
38 #include "nurb.h"
39 
40 /**
41  * Algorithm -
42  *
43  * See paper in Computer Aided Design (CAD) Volume 27, Number 1,
44  * January 1995 TESSELATING TRIMMED NURBS SURFACES, Leslie A Piegl
45  * and Arnaud Richard.
46  *
47  * There is a slight deviation from the paper; since libnurb
48  * (rt_nurb_s_diff) differentiation correctly handles rational
49  * surfaces, no special processing for rational is needed.
50  *
51  * The idea is to compute the longest edge size in parametric space
52  * such that a the edge (or curve) in real space is within epsilon
53  * tolerance. The mapping from parametric space is done as a separate
54  * step.
55  *
56  */
57 
58 fastf_t
59 rt_nurb_par_edge(const struct face_g_snurb *srf, fastf_t epsilon)
60 {
61  struct face_g_snurb * us, *vs, * uus, * vvs, *uvs;
62  fastf_t d1, d2, d3;
63  int i;
64  fastf_t *pt;
65 
66 
67  us = rt_nurb_s_diff(srf, RT_NURB_SPLIT_ROW);
68  vs = rt_nurb_s_diff(srf, RT_NURB_SPLIT_COL);
69  uus = rt_nurb_s_diff(us, RT_NURB_SPLIT_ROW);
70  vvs = rt_nurb_s_diff(vs, RT_NURB_SPLIT_COL);
71  uvs = rt_nurb_s_diff(vs, RT_NURB_SPLIT_ROW);
72 
73  d1 = 0.0;
74  d2 = 0.0;
75  d3 = 0.0;
76 
77  pt = (fastf_t *) uus->ctl_points;
78 
79  /* Find the maximum value of the 2nd derivative in U */
80 
81  for (i = 0; i < uus->s_size[0] * uus->s_size[1]; i++) {
82  fastf_t mag;
83 
84  mag = MAGNITUDE(pt);
85 
86  if (mag > d1) d1 = mag;
87 
88  pt += RT_NURB_EXTRACT_COORDS(uus->pt_type);
89 
90  }
91 
92  /* Find the maximum value of the partial derivative in UV */
93 
94  pt = (fastf_t *) uvs->ctl_points;
95 
96  for (i = 0; i < uvs->s_size[0] * uvs->s_size[1]; i++) {
97  fastf_t mag;
98 
99  mag = MAGNITUDE(pt);
100 
101  if (mag > d2) d2 = mag;
102 
103  pt += RT_NURB_EXTRACT_COORDS(uvs->pt_type);
104 
105  }
106 
107 
108  /* Find the maximum value of the 2nd derivative in V */
109  pt = (fastf_t *) vvs->ctl_points;
110 
111  for (i = 0; i < vvs->s_size[0] * vvs->s_size[1]; i++) {
112  fastf_t mag;
113 
114  mag = MAGNITUDE(pt);
115 
116  if (mag > d3) d3 = mag;
117 
118  pt += RT_NURB_EXTRACT_COORDS(vvs->pt_type);
119 
120  }
121 
122  /* free up storage */
123 
124  rt_nurb_free_snurb(us, (struct resource *)NULL);
125  rt_nurb_free_snurb(vs, (struct resource *)NULL);
126  rt_nurb_free_snurb(uus, (struct resource *)NULL);
127  rt_nurb_free_snurb(vvs, (struct resource *)NULL);
128  rt_nurb_free_snurb(uvs, (struct resource *)NULL);
129 
130 
131  /* The paper uses the following to calculate the longest edge size
132  * 1/2
133  * 3.0 * ()
134  * (2.0)
135  * _________________________
136  * (2.0 * (d1 + 2 D2 + d3)
137  */
138 
139  return 3.0 * sqrt(epsilon / (2.0*(d1 + (2.0 * d2)+ d3)));
140 }
141 
142 
143 /**
144  * Calculate the maximum edge length (in parameter space) that will
145  * keep the curve approximation within epsilon of the true curve
146  *
147  * This is a temporary guess until legitimate code can be found
148  *
149  * returns:
150  * -1.0 if the curve is a straight line
151  * maximum parameter increment otherwise
152  */
153 fastf_t
154 rt_cnurb_par_edge(const struct edge_g_cnurb *crv, fastf_t epsilon)
155 {
156  struct edge_g_cnurb *d1, *d2;
157  fastf_t der2[5], t, *pt;
158  fastf_t num_coord_factor, final_t;
159  int num_coords;
160  int i, j;
161 
162  if (crv->order < 3)
163  return -1.0;
164 
165  num_coords = RT_NURB_EXTRACT_COORDS(crv->pt_type);
166  if (num_coords > 5) {
167  bu_log("ERROR: rt_cnurb_par_edge() cannot handle curves with more than 5 coordinates (curve has %d)\n",
168  num_coords);
169  bu_bomb("ERROR: rt_cnurb_par_edge() cannot handle curves with more than 5 coordinates\n");
170  }
171 
172  for (i=0; i<num_coords; i++) {
173  der2[i] = 0.0;
174  }
175 
176  final_t = MAX_FASTF;
177  num_coord_factor = sqrt((double)num_coords);
178 
179  d1 = rt_nurb_c_diff(crv);
180  d2 = rt_nurb_c_diff(d1);
181 
182  pt = d2->ctl_points;
183  for (i=0; i<d2->c_size; i++) {
184  for (j=0; j<num_coords; j++) {
185  fastf_t abs_val;
186 
187  abs_val = *pt > 0.0 ? *pt : -(*pt);
188  if (abs_val > der2[j])
189  der2[j] = abs_val;
190  pt++;
191  }
192  }
193 
194  rt_nurb_free_cnurb(d1);
195  rt_nurb_free_cnurb(d2);
196 
197  for (j=0; j<num_coords; j++) {
198  if (ZERO(der2[j]))
199  continue;
200 
201  t = sqrt(2.0 * epsilon / (num_coord_factor * der2[j]));
202  if (t < final_t)
203  final_t = t;
204  }
205 
206  if (ZERO(final_t - MAX_FASTF))
207  return -1.0;
208  else
209  return final_t/2.0;
210 }
211 
212 
213 /*
214  * Local Variables:
215  * mode: C
216  * tab-width: 8
217  * indent-tabs-mode: t
218  * c-file-style: "stroustrup"
219  * End:
220  * ex: shiftwidth=4 tabstop=8
221  */
void rt_nurb_free_snurb(struct face_g_snurb *srf, struct resource *res)
Definition: nurb_util.c:127
void bu_log(const char *,...) _BU_ATTR_PRINTF12
Definition: log.c:176
Header file for the BRL-CAD common definitions.
#define MAX_FASTF
Definition: defines.h:340
fastf_t rt_cnurb_par_edge(const struct edge_g_cnurb *crv, fastf_t epsilon)
Definition: nurb_tess.c:154
#define ZERO(val)
Definition: units.c:38
struct face_g_snurb * rt_nurb_s_diff(const struct face_g_snurb *srf, int dir)
Definition: nurb_diff.c:58
struct edge_g_cnurb * rt_nurb_c_diff(const struct edge_g_cnurb *crv)
Definition: nurb_diff.c:133
void rt_nurb_free_cnurb(struct edge_g_cnurb *crv)
Definition: nurb_util.c:170
fastf_t rt_nurb_par_edge(const struct face_g_snurb *srf, fastf_t epsilon)
Definition: nurb_tess.c:59
void bu_bomb(const char *str) _BU_ATTR_NORETURN
Definition: bomb.c:91
double fastf_t
Definition: defines.h:300