BRL-CAD
vshoot.c
Go to the documentation of this file.
1 /* V S H O O T . C
2  * BRL-CAD
3  *
4  * Copyright (c) 1985-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 ray */
21 /** @{ */
22 /** @file librt/vshoot.c
23  *
24  * EXPERIMENTAL vector version of the Ray Tracing program shot
25  * coordinator.
26  *
27  */
28 
29 #include "common.h"
30 
31 #include <stdio.h>
32 #include <math.h>
33 #include "vmath.h"
34 #include "raytrace.h"
35 
36 
37 /**
38  * Stub function which will "simulate" a call to a vector shot routine
39  */
40 HIDDEN void
41 vshot_stub(struct soltab **stp, struct xray **rp, struct seg *segp, int n, struct application *ap)
42 /* An array of solid pointers */
43 /* An array of ray pointers */
44 /* array of segs (results returned) */
45 /* Number of ray/object pairs */
46 /* pointer to an application */
47 {
48  register int i;
49  register struct seg *tmp_seg;
50  struct seg seghead;
51  int ret;
52 
53  BU_LIST_INIT(&(seghead.l));
54 
55  /* go through each ray/solid pair and call a scalar function */
56  for (i = 0; i < n; i++) {
57  if (stp[i] != 0) {
58  /* skip call if solid table pointer is NULL */
59  /* do scalar call, place results in segp array */
60  ret = -1;
61  if (OBJ[stp[i]->st_id].ft_shot) {
62  ret = OBJ[stp[i]->st_id].ft_shot(stp[i], rp[i], ap, &seghead);
63  }
64  if (ret <= 0) {
65  segp[i].seg_stp=(struct soltab *) 0;
66  } else {
67  tmp_seg = BU_LIST_FIRST(seg, &(seghead.l));
68  BU_LIST_DEQUEUE(&(tmp_seg->l));
69  segp[i] = *tmp_seg; /* structure copy */
70  RT_FREE_SEG(tmp_seg, ap->a_resource);
71  }
72  }
73  }
74 }
75 
76 
77 /**
78  * Given a ray, shoot it at all the relevant parts of the model,
79  * (building the HeadSeg chain), and then call rt_boolregions() to
80  * build and evaluate the partition chain. If the ray actually hit
81  * anything, call the application's a_hit() routine with a pointer to
82  * the partition chain, otherwise, call the application's a_miss()
83  * routine.
84  *
85  * It is important to note that rays extend infinitely only in the
86  * positive direction. The ray is composed of all points P, where
87  *
88  * P = r_pt + K * r_dir
89  *
90  * for K ranging from 0 to +infinity. There is no looking backwards.
91  *
92  * It is also important to note that the direction vector r_dir must
93  * have unit length; this is mandatory, and is not ordinarily checked,
94  * in the name of efficiency.
95  *
96  * Input: Pointer to an application structure, with these mandatory fields:
97  * a_ray.r_pt Starting point of ray to be fired
98  * a_ray.r_dir UNIT VECTOR with direction to fire in (dir cosines)
99  * a_hit Routine to call when something is hit
100  * a_miss Routine to call when ray misses everything
101  *
102  * Calls user's a_miss() or a_hit() routine as appropriate. Passes
103  * a_hit() routine list of partitions, with only hit_dist fields
104  * valid. Normal computation deferred to user code, to avoid needless
105  * computation here.
106  *
107  * Returns: whatever the application function returns (an int).
108  *
109  * NOTE: The application functions may call rt_shootray() recursively.
110  * Thus, none of the local variables may be static.
111  *
112  * An open issue for execution in a PARALLEL environment is locking of
113  * the statistics variables.
114  */
115 int
117 {
118  struct seg *HeadSeg;
119  int ret;
120  vect_t inv_dir; /* inverses of ap->a_ray.r_dir */
121  struct bu_bitv *solidbits; /* bits for all solids shot so far */
122  struct bu_ptbl *regionbits; /* bits for all involved regions */
123  char *status;
124  struct partition InitialPart; /* Head of Initial Partitions */
125  struct partition FinalPart; /* Head of Final Partitions */
126  int nrays = 1; /* for now */
127  int vlen;
128  int id;
129  int i;
130  struct soltab **ary_stp; /* array of pointers */
131  struct xray **ary_rp; /* array of pointers */
132  struct seg *ary_seg; /* array of structures */
133  struct rt_i *rtip;
134  int done;
135 
136 #define BACKING_DIST (-2.0) /* mm to look behind start point */
137  rtip = ap->a_rt_i;
138  RT_AP_CHECK(ap);
139  if (!ap->a_resource) {
140  ap->a_resource = &rt_uniresource;
141  }
143 
145  bu_log("\n**********mshootray cpu=%d %d, %d lvl=%d (%s)\n",
146  ap->a_resource->re_cpu,
147  ap->a_x, ap->a_y,
148  ap->a_level,
149  ap->a_purpose != (char *)0 ? ap->a_purpose : "?");
150  VPRINT("Pnt", ap->a_ray.r_pt);
151  VPRINT("Dir", ap->a_ray.r_dir);
152  }
153 
154  rtip->rti_nrays++;
155  if (rtip->needprep)
156  rt_prep(rtip);
157 
158  /* Allocate dynamic memory */
159  vlen = nrays * rtip->rti_maxsol_by_type;
160  ary_stp = (struct soltab **)bu_calloc(vlen, sizeof(struct soltab *),
161  "*ary_stp[]");
162  ary_rp = (struct xray **)bu_calloc(vlen, sizeof(struct xray *),
163  "*ary_rp[]");
164  ary_seg = (struct seg *)bu_calloc(vlen, sizeof(struct seg),
165  "ary_seg[]");
166 
167  /**** for each ray, do this ****/
168 
169  InitialPart.pt_forw = InitialPart.pt_back = &InitialPart;
170  FinalPart.pt_forw = FinalPart.pt_back = &FinalPart;
171 
172  HeadSeg = RT_SEG_NULL;
173 
174  solidbits = rt_get_solidbitv(rtip->nsolids, ap->a_resource);
175 
177  BU_ALLOC(regionbits, struct bu_ptbl);
178  bu_ptbl_init(regionbits, 7, "rt_shootray() regionbits ptbl");
179  } else {
180  regionbits = BU_LIST_FIRST(bu_ptbl, &ap->a_resource->re_region_ptbl);
181  BU_LIST_DEQUEUE(&regionbits->l);
182  BU_CK_PTBL(regionbits);
183  }
184 
185  /* Compute the inverse of the direction cosines */
186  if (!ZERO(ap->a_ray.r_dir[X])) {
187  inv_dir[X]=1.0/ap->a_ray.r_dir[X];
188  } else {
189  inv_dir[X] = INFINITY;
190  ap->a_ray.r_dir[X] = 0.0;
191  }
192  if (!ZERO(ap->a_ray.r_dir[Y])) {
193  inv_dir[Y]=1.0/ap->a_ray.r_dir[Y];
194  } else {
195  inv_dir[Y] = INFINITY;
196  ap->a_ray.r_dir[Y] = 0.0;
197  }
198  if (!ZERO(ap->a_ray.r_dir[Z])) {
199  inv_dir[Z]=1.0/ap->a_ray.r_dir[Z];
200  } else {
201  inv_dir[Z] = INFINITY;
202  ap->a_ray.r_dir[Z] = 0.0;
203  }
204 
205  /*
206  * XXX handle infinite solids here, later.
207  */
208 
209  /*
210  * If ray does not enter the model RPP, skip on.
211  * If ray ends exactly at the model RPP, trace it.
212  */
213  if (!rt_in_rpp(&ap->a_ray, inv_dir, rtip->mdl_min, rtip->mdl_max) ||
214  ap->a_ray.r_max < 0.0) {
215  rtip->nmiss_model++;
216  if (ap->a_miss)
217  ret = ap->a_miss(ap);
218  else
219  ret = 0;
220  status = "MISS model";
221  goto out;
222  }
223 
224  /* For each type of solid to be shot at, assemble the vectors */
225  for (id = 1; id <= ID_MAX_SOLID; id++) {
226  register int nsol;
227 
228  if ((nsol = rtip->rti_nsol_by_type[id]) <= 0) continue;
229 
230  /* For each instance of this solid type */
231  for (i = nsol-1; i >= 0; i--) {
232  ary_stp[i] = rtip->rti_sol_by_type[id][i];
233  ary_rp[i] = &(ap->a_ray); /* XXX, sb [ray] */
234  ary_seg[i].seg_stp = SOLTAB_NULL;
235  BU_LIST_INIT(&ary_seg[i].l);
236  }
237  /* bounding box check */
238  /* bit vector per ray check */
239  /* mark elements to be skipped with ary_stp[] = SOLTAB_NULL */
240  ap->a_rt_i->nshots += nsol; /* later: skipped ones */
241  if (OBJ[id].ft_vshot) {
242  OBJ[id].ft_vshot(ary_stp, ary_rp, ary_seg, nsol, ap);
243  } else {
244  vshot_stub(ary_stp, ary_rp, ary_seg, nsol, ap);
245  }
246 
247 
248  /* set bits for all solids shot at for each ray */
249 
250  /* append resulting seg list to input for boolweave */
251  for (i = nsol-1; i >= 0; i--) {
252  register struct seg *seg2;
253 
254  if (ary_seg[i].seg_stp == SOLTAB_NULL) {
255  /* MISS */
256  ap->a_rt_i->nmiss++;
257  continue;
258  }
259  ap->a_rt_i->nhits++;
260 
261  /* For now, do it the slow way. sb [ray] */
262  /* MUST dup it -- all segs have to live till after a_hit() */
263  RT_GET_SEG(seg2, ap->a_resource);
264  *seg2 = ary_seg[i]; /* struct copy */
265  /* rt_boolweave(seg2, &InitialPart, ap); */
266  bu_bomb("FIXME: need to call boolweave here");
267 
268  /* Add seg chain to list of used segs awaiting reclaim */
269 
270 #if 0
271  /* FIXME: need to use waiting_segs/finished_segs here in
272  * conjunction with rt_boolweave()
273  {
274  register struct seg *seg3 = seg2;
275  while (seg3->seg_next != RT_SEG_NULL)
276  seg3 = seg3->seg_next;
277  seg3->seg_next = HeadSeg;
278  HeadSeg = seg2;
279  }
280  */
281 #endif
282  }
283  }
284 
285  /*
286  * Ray has finally left known space.
287  */
288  if (InitialPart.pt_forw == &InitialPart) {
289  if (ap->a_miss)
290  ret = ap->a_miss(ap);
291  else
292  ret = 0;
293  status = "MISSed all primitives";
294  goto freeup;
295  }
296 
297  /*
298  * All intersections of the ray with the model have been computed.
299  * Evaluate the boolean trees over each partition.
300  */
301  done = rt_boolfinal(&InitialPart, &FinalPart, BACKING_DIST, INFINITY, regionbits, ap, solidbits);
302 
303  if (done > 0) goto hitit;
304 
305  if (FinalPart.pt_forw == &FinalPart) {
306  if (ap->a_miss)
307  ret = ap->a_miss(ap);
308  else
309  ret = 0;
310  status = "MISS bool";
311  goto freeup;
312  }
313 
314  /*
315  * Ray/model intersections exist. Pass the list to the user's
316  * a_hit() routine. Note that only the hit_dist elements of
317  * pt_inhit and pt_outhit have been computed yet. To compute both
318  * hit_point and hit_normal, use the
319  *
320  * RT_HIT_NORMAL(NULL, hitp, stp, rayp, 0);
321  *
322  * macro. To compute just hit_point, use
323  *
324  * VJOIN1(hitp->hit_point, rp->r_pt, hitp->hit_dist, rp->r_dir);
325  */
326 hitit:
327  if (RT_G_DEBUG&DEBUG_SHOOT) rt_pr_partitions(rtip, &FinalPart, "a_hit()");
328 
329  if (ap->a_hit)
330  ret = ap->a_hit(ap, &FinalPart, HeadSeg/* &finished_segs */);
331  else
332  ret = 0;
333  status = "HIT";
334 
335  /*
336  * Processing of this ray is complete. Free dynamic resources.
337  */
338 freeup:
339  {
340  register struct partition *pp;
341 
342  /* Free up initial partition list */
343  for (pp = InitialPart.pt_forw; pp != &InitialPart;) {
344  register struct partition *newpp;
345  newpp = pp;
346  pp = pp->pt_forw;
347  FREE_PT(newpp, ap->a_resource);
348  }
349  /* Free up final partition list */
350  for (pp = FinalPart.pt_forw; pp != &FinalPart;) {
351  register struct partition *newpp;
352  newpp = pp;
353  pp = pp->pt_forw;
354  FREE_PT(newpp, ap->a_resource);
355  }
356  }
357 
358 out:
359  bu_free((char *)ary_stp, "*ary_stp[]");
360  bu_free((char *)ary_rp, "*ary_rp[]");
361  bu_free((char *)ary_seg, "ary_seg[]");
362 
363  if (solidbits != NULL) {
364  bu_bitv_free(solidbits);
365  }
366  if (RT_G_DEBUG&(DEBUG_ALLRAYS|DEBUG_SHOOT|DEBUG_PARTITION)) {
367  bu_log("----------mshootray cpu=%d %d, %d lvl=%d (%s) %s ret=%d\n",
368  ap->a_resource->re_cpu,
369  ap->a_x, ap->a_y,
370  ap->a_level,
371  ap->a_purpose != (char *)0 ? ap->a_purpose : "?",
372  status, ret);
373  }
374  return ret;
375 }
376 
377 
378 /** @} */
379 /*
380  * Local Variables:
381  * mode: C
382  * tab-width: 8
383  * indent-tabs-mode: t
384  * c-file-style: "stroustrup"
385  * End:
386  * ex: shiftwidth=4 tabstop=8
387  */
void(* ft_vshot)(struct soltab *[], struct xray *[], struct seg *, int, struct application *)
Definition: raytrace.h:2107
struct xray a_ray
Actual ray to be shot.
Definition: raytrace.h:1583
int rti_nsol_by_type[ID_MAX_SOLID+1]
Definition: raytrace.h:1803
void bu_log(const char *,...) _BU_ATTR_PRINTF12
Definition: log.c:176
point_t mdl_min
min corner of model bounding RPP
Definition: raytrace.h:1769
size_t nhits
solid ft_shot() returned a hit
Definition: raytrace.h:1788
#define RT_FREE_SEG(p, res)
Definition: raytrace.h:389
int rt_vshootray(struct application *ap)
Definition: vshoot.c:116
struct soltab * seg_stp
pointer back to soltab
Definition: raytrace.h:372
void bu_ptbl_init(struct bu_ptbl *b, size_t len, const char *str)
Definition: ptbl.c:32
Definition: raytrace.h:215
#define BU_LIST_IS_EMPTY(hp)
Definition: list.h:295
Definition: raytrace.h:368
#define RT_SEG_NULL
Definition: raytrace.h:374
#define DEBUG_SHOOT
3 Info about rt_shootray() processing
Definition: raytrace.h:84
Header file for the BRL-CAD common definitions.
#define BU_CK_PTBL(_p)
Definition: ptbl.h:74
struct resource * a_resource
dynamic memory resources
Definition: raytrace.h:1591
int rt_in_rpp(struct xray *rp, const fastf_t *invdir, const fastf_t *min, const fastf_t *max)
int(* a_hit)(struct application *, struct partition *, struct seg *)
called when shot hits model
Definition: raytrace.h:1584
#define HIDDEN
Definition: common.h:86
struct bu_list l
Definition: raytrace.h:369
Definition: ptbl.h:62
#define RT_AP_CHECK(_ap)
Definition: raytrace.h:1685
Definition: color.c:49
struct rt_i * a_rt_i
this librt instance
Definition: raytrace.h:1588
#define DEBUG_PARTITION
14 Info about bool_weave()
Definition: raytrace.h:99
struct resource rt_uniresource
default. Defined in librt/globals.c
Definition: globals.c:41
#define RT_G_DEBUG
Definition: raytrace.h:1718
#define BU_ALLOC(_ptr, _type)
Definition: malloc.h:223
void * bu_calloc(size_t nelem, size_t elsize, const char *str)
Definition: malloc.c:321
HIDDEN void vshot_stub(struct soltab **stp, struct xray **rp, struct seg *segp, int n, struct application *ap)
Definition: vshoot.c:41
int(* ft_shot)(struct soltab *stp, struct xray *rp, struct application *ap, struct seg *seghead)
Definition: raytrace.h:2052
int a_x
Screen X of ray, if applicable.
Definition: raytrace.h:1596
int rti_maxsol_by_type
Definition: raytrace.h:1804
#define BACKING_DIST
fastf_t r_max
exit dist from bounding sphere
Definition: raytrace.h:221
int a_level
recursion level (for printing)
Definition: raytrace.h:1595
struct bu_list l
Definition: ptbl.h:63
const char * a_purpose
Debug string: purpose of ray.
Definition: raytrace.h:1598
size_t nmiss
solid ft_shot() returned a miss
Definition: raytrace.h:1787
void rt_pr_partitions(const struct rt_i *rtip, const struct partition *phead, const char *title)
goto out
Definition: nmg_mod.c:3846
struct partition * pt_back
backwards link
Definition: raytrace.h:575
struct bu_list re_region_ptbl
head of freelist
Definition: raytrace.h:1453
vect_t r_dir
Direction of ray (UNIT Length)
Definition: raytrace.h:219
#define RT_GET_SEG(p, res)
Definition: raytrace.h:379
struct bu_bitv * rt_get_solidbitv(size_t nbits, struct resource *resp)
Definition: prep.c:828
#define ZERO(val)
Definition: units.c:38
#define BU_LIST_INIT(_hp)
Definition: list.h:148
point_t r_pt
Point at which ray starts.
Definition: raytrace.h:218
const struct rt_functab OBJ[]
Definition: table.c:159
#define RT_CK_RESOURCE(_p)
Definition: raytrace.h:1490
#define DEBUG_ALLRAYS
1 Print calls to rt_shootray()
Definition: raytrace.h:82
size_t nshots
of calls to ft_shot()
Definition: raytrace.h:1786
size_t nsolids
total # of solids participating
Definition: raytrace.h:1783
point_t mdl_max
max corner of model bounding RPP
Definition: raytrace.h:1770
int a_y
Screen Y of ray, if applicable.
Definition: raytrace.h:1597
void rt_prep(struct rt_i *rtip)
void bu_bitv_free(struct bu_bitv *bv)
Definition: bitv.c:113
Definition: color.c:51
int re_cpu
processor number, for ID
Definition: raytrace.h:1442
void bu_free(void *ptr, const char *str)
Definition: malloc.c:328
#define SOLTAB_NULL
backwards compat
Definition: raytrace.h:450
int(* a_miss)(struct application *)
called when shot misses
Definition: raytrace.h:1585
int rt_boolfinal(struct partition *InputHdp, struct partition *FinalHdp, fastf_t startdist, fastf_t enddist, struct bu_ptbl *regionbits, struct application *ap, const struct bu_bitv *solidbits)
Definition: bool.c:1490
#define FREE_PT(p, res)
Definition: raytrace.h:622
int st_id
Solid ident.
Definition: raytrace.h:431
#define BU_LIST_DEQUEUE(cur)
Definition: list.h:209
Definition: bitv.h:105
struct partition * pt_forw
forwards link
Definition: raytrace.h:574
#define ID_MAX_SOLID
Maximum defined ID_xxx for solids.
Definition: raytrace.h:494
void bu_bomb(const char *str) _BU_ATTR_NORETURN
Definition: bomb.c:91
#define VPRINT(a, b)
Definition: raytrace.h:1881
struct soltab ** rti_sol_by_type[ID_MAX_SOLID+1]
Definition: raytrace.h:1802
int needprep
needs rt_prep
Definition: raytrace.h:1776
Definition: color.c:50
size_t rti_nrays
calls to rt_shootray()
Definition: raytrace.h:1784
size_t nmiss_model
rays missed model RPP
Definition: raytrace.h:1785
#define BU_LIST_FIRST(structure, hp)
Definition: list.h:312