- Added the main boolean weaving code. Eliminated gotos in boolfinal.
- Made the code more thread-safe by reducing amount of direct uses of the
global app pointer.
This was a good exercise to see the amount of effort that will be required
to do a full reimplementation of the rendering pipeline in OpenCL.
The main obstacle to an OpenCL port is, as I expected, the boolean code
which is branch and goto heavy and uses dynamic linked lists.
What I did not expect was that the total LOC count in that boolean weaving
code dwarfs everything else put together (traversal, ray generation, shade,
writing to the frame buffer).
The current code already supports threaded execution with some heavy app
context data structures. These probably have too large of a memory
footprint per thread for the kind of fine grained parallelism with
thousands of threads in flight that we desire (see 'struct resource').
As discussed with Sean a couple of days ago I am going to stop working on
this angle and start working on the grid spatial partitioning in OpenCL
next.
On Fri, Jun 5, 2015 at 12:16 AM, Vasco Alexandre da Silva Costa <
vasco.co...@gmail.com> wrote:
> Simplify the shading code some more.
>
> On Thu, Jun 4, 2015 at 11:10 PM, Vasco Alexandre da Silva Costa <
> vasco.co...@gmail.com> wrote:
>
>> Phong shading with a default material.
>>
>> The idea here is to create a simplified self-contained rendering pipeline
>> that we can use as a basis for a port to OpenCL later.
>>
>> Things to be done:
>> - rip the acceleration structure out and replace it with the simplified
>> grid we want to use.
>> - cleanly separate the shots from the boolean weaving with minimal
>> context between stages.
>> - cleanly mark all data in/out on each stage and minimize CPU<->GPU data
>> transfers.
>>
>> On Thu, Jun 4, 2015 at 5:04 PM, Vasco Alexandre da Silva Costa <
>> vasco.co...@gmail.com> wrote:
>>
>>> Now with the actual patch attached...
>>>
>>>
>>> On Thu, Jun 4, 2015 at 5:03 PM, Vasco Alexandre da Silva Costa <
>>> vasco.co...@gmail.com> wrote:
>>>
>>>> Simplified code for:
>>>> - ray generation
>>>> - writing the color output to the frame buffer
>>>>
>>>> On Tue, Jun 2, 2015 at 11:55 PM, Vasco Alexandre da Silva Costa <
>>>> vasco.co...@gmail.com> wrote:
>>>>
>>>>> Hello,
>>>>> I've been trying to make a really simple bare bones rendering loop in
>>>>> C without branches, recursion, etc that we can try to parallelize later.
>>>>>
>>>>> For now I managed to do this for the ray generation part (patch
>>>>> attached). Still need to work on the ray traversal and color computation
>>>>> proper.
>>>>>
>>>>> Regards,
>>>>>
>>>>> --
>>>>> Vasco Alexandre da Silva Costa
>>>>> PhD Student at Department of Information Systems and Computer Science
>>>>> Instituto Superior Técnico/University of Lisbon, Portugal
>>>>>
>>>>
>>>>
>>>>
>>>> --
>>>> Vasco Alexandre da Silva Costa
>>>> PhD Student at Department of Information Systems and Computer Science
>>>> Instituto Superior Técnico/University of Lisbon, Portugal
>>>>
>>>
>>>
>>>
>>> --
>>> Vasco Alexandre da Silva Costa
>>> PhD Student at Department of Information Systems and Computer Science
>>> Instituto Superior Técnico/University of Lisbon, Portugal
>>>
>>
>>
>>
>> --
>> Vasco Alexandre da Silva Costa
>> PhD Student at Department of Information Systems and Computer Science
>> Instituto Superior Técnico/University of Lisbon, Portugal
>>
>
>
>
> --
> Vasco Alexandre da Silva Costa
> PhD Student at Department of Information Systems and Computer Science
> Instituto Superior Técnico/University of Lisbon, Portugal
>
--
Vasco Alexandre da Silva Costa
PhD Student at Department of Information Systems and Computer Science
Instituto Superior Técnico/University of Lisbon, Portugal
Index: src/rt/do.c
===================================================================
--- src/rt/do.c (revision 65232)
+++ src/rt/do.c (working copy)
@@ -50,7 +50,9 @@
#include "./rtuif.h"
#include "./ext.h"
+#include "scanline.h"
+
/***** Variables shared with viewing model *** */
extern FILE *outfp; /* optional pixel output file */
extern mat_t view2model;
@@ -541,8 +543,1583 @@
}
}
+static int ibackground[3] = {0, 0, 50}; /* integer 0..255 version */
+static int inonbackground[3] = {0, 0, 51}; /* integer non-background */
+static size_t pwidth = 3; /* Width of each pixel (in bytes) */
+extern fb *fbp; /* Framebuffer handle */
+static struct scanline scanline;
/**
+ * If a zero thickness segment abuts another partition, it will be
+ * fused in, later.
+ *
+ * If it is free standing, then it will remain as a zero thickness
+ * partition, which probably signals going through some solid an odd
+ * number of times, or hitting an NMG wire edge or NMG lone vertex.
+ */
+void
+my_weave0seg(struct resource *res, struct seg *segp, struct partition *PartHdp, fastf_t tol_dist)
+{
+ register struct partition *pp;
+
+ RT_CK_PT_HD(PartHdp);
+
+ if (PartHdp->pt_forw == PartHdp) bu_bomb("rt_weave0seg() with empty partition list\n");
+
+ /* See if this segment ends before start of first partition */
+ if (segp->seg_out.hit_dist < PartHdp->pt_forw->pt_inhit->hit_dist) {
+ GET_PT_INIT(0, pp, res);
+ bu_ptbl_ins_unique(&pp->pt_seglist, (long *)segp);
+ pp->pt_inseg = segp;
+ pp->pt_inhit = &segp->seg_in;
+ pp->pt_outseg = segp;
+ pp->pt_outhit = &segp->seg_out;
+ APPEND_PT(pp, PartHdp);
+ return;
+ }
+
+ /*
+ * Cases: seg at start of pt, in middle of pt, at end of pt, or
+ * past end of pt but before start of next pt.
+ *
+ * XXX For the first 3 cases, we might want to make a new 0-len pt,
+ * XXX especially as the NMG ray-tracer starts reporting wire hits.
+ */
+ for (pp=PartHdp->pt_forw; pp != PartHdp; pp=pp->pt_forw) {
+ if (NEAR_EQUAL(segp->seg_in.hit_dist, pp->pt_inhit->hit_dist, tol_dist) ||
+ NEAR_EQUAL(segp->seg_out.hit_dist, pp->pt_inhit->hit_dist, tol_dist)
+ ) {
+ return;
+ }
+ if (NEAR_EQUAL(segp->seg_in.hit_dist, pp->pt_outhit->hit_dist, tol_dist) ||
+ NEAR_EQUAL(segp->seg_out.hit_dist, pp->pt_outhit->hit_dist, tol_dist)
+ ) {
+ return;
+ }
+ if (segp->seg_out.hit_dist <= pp->pt_outhit->hit_dist &&
+ segp->seg_in.hit_dist >= pp->pt_inhit->hit_dist) {
+ return;
+ }
+ if (pp->pt_forw == PartHdp ||
+ segp->seg_out.hit_dist < pp->pt_forw->pt_inhit->hit_dist) {
+ struct partition *npp;
+ GET_PT_INIT(0, npp, res);
+ bu_ptbl_ins_unique(&npp->pt_seglist, (long *)segp);
+ npp->pt_inseg = segp;
+ npp->pt_inhit = &segp->seg_in;
+ npp->pt_outseg = segp;
+ npp->pt_outhit = &segp->seg_out;
+ APPEND_PT(npp, pp);
+ return;
+ }
+ }
+ bu_bomb("rt_weave0seg() fell out of partition loop?\n");
+}
+
+
+void
+my_boolweave(struct resource *res, struct seg *out_hd, struct seg *in_hd, struct partition *PartHdp, fastf_t tol_dist, size_t nsolids, int a_no_booleans)
+{
+ register struct seg *segp;
+ register struct partition *pp;
+
+ register fastf_t diff, diff_se;
+
+ RT_CK_PT_HD(PartHdp);
+
+ while (BU_LIST_NON_EMPTY(&(in_hd->l))) {
+ register struct partition *newpp = PT_NULL;
+ register struct seg *lastseg = RT_SEG_NULL;
+ register struct hit *lasthit = HIT_NULL;
+ int lastflip = 0;
+
+ segp = BU_LIST_FIRST(seg, &(in_hd->l));
+ RT_CHECK_SEG(segp);
+ RT_CK_HIT(&(segp->seg_in));
+ RT_CK_RAY(segp->seg_in.hit_rayp);
+ RT_CK_HIT(&(segp->seg_out));
+ RT_CK_RAY(segp->seg_out.hit_rayp);
+ if ((size_t)segp->seg_stp->st_bit >= nsolids)
+ bu_bomb("rt_boolweave: st_bit");
+
+ BU_LIST_DEQUEUE(&(segp->l));
+ BU_LIST_INSERT(&(out_hd->l), &(segp->l));
+
+ /* Make nearly zero be exactly zero */
+ if (NEAR_ZERO(segp->seg_in.hit_dist, tol_dist))
+ segp->seg_in.hit_dist = 0;
+ if (NEAR_ZERO(segp->seg_out.hit_dist, tol_dist))
+ segp->seg_out.hit_dist = 0;
+
+ /* Totally ignore things behind the start position */
+ if (segp->seg_out.hit_dist < -10.0)
+ continue;
+
+ if (segp->seg_stp->st_aradius < INFINITY &&
+ !(segp->seg_in.hit_dist >= -INFINITY &&
+ segp->seg_out.hit_dist <= INFINITY)) {
+ continue;
+ }
+ if (segp->seg_in.hit_dist > segp->seg_out.hit_dist) {
+ continue;
+ }
+
+ /*
+ * Weave this segment into the existing partitions, creating
+ * new partitions as necessary.
+ */
+ if (PartHdp->pt_forw == PartHdp) {
+ /* No partitions yet, simple! */
+ GET_PT_INIT(0, pp, res);
+ bu_ptbl_ins_unique(&pp->pt_seglist, (long *)segp);
+ pp->pt_inseg = segp;
+ pp->pt_inhit = &segp->seg_in;
+ pp->pt_outseg = segp;
+ pp->pt_outhit = &segp->seg_out;
+ APPEND_PT(pp, PartHdp);
+ goto done_weave;
+ }
+
+ if (a_no_booleans) {
+ lastseg = segp;
+ lasthit = &segp->seg_in;
+ lastflip = 0;
+ /* Just sort in ascending in-dist order */
+ for (pp=PartHdp->pt_forw; pp != PartHdp; pp=pp->pt_forw) {
+ if (lasthit->hit_dist < pp->pt_inhit->hit_dist) {
+ GET_PT_INIT(0, newpp, res);
+ bu_ptbl_ins_unique(&newpp->pt_seglist, (long *)segp);
+ newpp->pt_inseg = segp;
+ newpp->pt_inhit = &segp->seg_in;
+ newpp->pt_outseg = segp;
+ newpp->pt_outhit = &segp->seg_out;
+ INSERT_PT(newpp, pp);
+ goto done_weave;
+ }
+ }
+ GET_PT_INIT(0, newpp, res);
+ bu_ptbl_ins_unique(&newpp->pt_seglist, (long *)segp);
+ newpp->pt_inseg = segp;
+ newpp->pt_inhit = &segp->seg_in;
+ newpp->pt_outseg = segp;
+ newpp->pt_outhit = &segp->seg_out;
+ INSERT_PT(newpp, PartHdp);
+ goto done_weave;
+ }
+
+ /* Check for zero-thickness segment, within tol */
+ diff = segp->seg_in.hit_dist - segp->seg_out.hit_dist;
+ if (NEAR_ZERO(diff, tol_dist)) {
+ my_weave0seg(res, segp, PartHdp, tol_dist);
+ goto done_weave;
+ }
+
+ if (segp->seg_in.hit_dist >= PartHdp->pt_back->pt_outhit->hit_dist) {
+ /*
+ * Segment starts exactly at last partition's end, or
+ * beyond last partitions end. Make new partition.
+ */
+ GET_PT_INIT(0, pp, res);
+ bu_ptbl_ins_unique(&pp->pt_seglist, (long *)segp);
+ pp->pt_inseg = segp;
+ pp->pt_inhit = &segp->seg_in;
+ pp->pt_outseg = segp;
+ pp->pt_outhit = &segp->seg_out;
+ APPEND_PT(pp, PartHdp->pt_back);
+ goto done_weave;
+ }
+
+ /* Loop through current partition list weaving the current
+ * input segment into the list. The following three variables
+ * keep track of the current starting point of the input
+ * segment. The starting point of the segment moves to higher
+ * hit_dist values (as it is woven in) until it is entirely
+ * consumed.
+ */
+ lastseg = segp;
+ lasthit = &segp->seg_in;
+ lastflip = 0;
+ for (pp=PartHdp->pt_forw; pp != PartHdp; pp=pp->pt_forw) {
+ diff_se = lasthit->hit_dist - pp->pt_outhit->hit_dist;
+ if (diff_se > tol_dist) {
+ /* Seg starts beyond the END of the
+ * current partition.
+ * PPPP
+ * SSSS
+ * Advance to next partition.
+ */
+ continue;
+ }
+ diff = lasthit->hit_dist - pp->pt_inhit->hit_dist;
+ if (diff_se > -(tol_dist) && diff > tol_dist) {
+ /*
+ * Seg starts almost "precisely" at the
+ * end of the current partition.
+ * PPPP
+ * SSSS
+ * FUSE an exact match of the endpoints,
+ * advance to next partition.
+ */
+ lasthit->hit_dist = pp->pt_outhit->hit_dist;
+ continue;
+ }
+
+ /*
+ * diff < ~~0
+ * Seg starts before current partition ends
+ * PPPPPPPPPPP
+ * SSSS...
+ */
+ if (diff > tol_dist) {
+ /*
+ * lasthit->hit_dist > pp->pt_inhit->hit_dist
+ * pp->pt_inhit->hit_dist < lasthit->hit_dist
+ *
+ * Segment starts after partition starts,
+ * but before the end of the partition.
+ * Note: pt_seglist will be updated in equal_start.
+ * PPPPPPPPPPPP
+ * SSSS...
+ * newpp|pp
+ */
+ RT_DUP_PT(0, newpp, pp, res);
+ /* new partition is the span before seg joins partition */
+ pp->pt_inseg = segp;
+ pp->pt_inhit = &segp->seg_in;
+ pp->pt_inflip = 0;
+ newpp->pt_outseg = segp;
+ newpp->pt_outhit = &segp->seg_in;
+ newpp->pt_outflip = 1;
+ INSERT_PT(newpp, pp);
+ goto equal_start;
+ }
+ if (diff > -(tol_dist)) {
+ /*
+ * Make a subtle but important distinction here. Even
+ * though the two distances are "equal" within
+ * tolerance, they are not exactly the same. If the
+ * new segment is slightly closer to the ray origin,
+ * then use its IN point.
+ *
+ * This is an attempt to reduce the deflected normals
+ * sometimes seen along the edges of e.g. a cylinder
+ * unioned with an ARB8, where the ray hits the top of
+ * the cylinder and the *side* face of the ARB8 rather
+ * than the top face of the ARB8.
+ */
+ diff = segp->seg_in.hit_dist - pp->pt_inhit->hit_dist;
+ if (!pp->pt_back ||
+ pp->pt_back == PartHdp ||
+ pp->pt_back->pt_outhit->hit_dist <=
+ segp->seg_in.hit_dist) {
+ if (NEAR_ZERO(diff, tol_dist) &&
+ diff < 0) {
+ pp->pt_inseg = segp;
+ pp->pt_inhit = &segp->seg_in;
+ pp->pt_inflip = 0;
+ }
+ }
+ equal_start:
+ /*
+ * Segment and partition start at (roughly) the same
+ * point. When fusing 2 points together i.e., when
+ * NEAR_ZERO(diff, tol) is true, the two points MUST
+ * be forced to become exactly equal!
+ */
+ diff = segp->seg_out.hit_dist - pp->pt_outhit->hit_dist;
+ if (diff > tol_dist) {
+ /*
+ * Seg & partition start at roughly
+ * the same spot,
+ * seg extends beyond partition end.
+ * PPPP
+ * SSSSSSSS
+ * pp | newpp
+ */
+ bu_ptbl_ins_unique(&pp->pt_seglist, (long *)segp);
+ lasthit = pp->pt_outhit;
+ lastseg = pp->pt_outseg;
+ lastflip = 1;
+ continue;
+ }
+ if (diff > -(tol_dist)) {
+ /*
+ * diff ~= 0
+ * Segment and partition start & end
+ * (nearly) together.
+ * PPPP
+ * SSSS
+ */
+ bu_ptbl_ins_unique(&pp->pt_seglist, (long *)segp);
+ goto done_weave;
+ } else {
+ /*
+ * diff < ~0
+ *
+ * Segment + Partition start together,
+ * segment ends before partition ends.
+ * PPPPPPPPPP
+ * SSSSSS
+ * newpp| pp
+ */
+ RT_DUP_PT(0, newpp, pp, res);
+ /* new partition contains segment */
+ bu_ptbl_ins_unique(&newpp->pt_seglist, (long *)segp);
+ newpp->pt_outseg = segp;
+ newpp->pt_outhit = &segp->seg_out;
+ newpp->pt_outflip = 0;
+ pp->pt_inseg = segp;
+ pp->pt_inhit = &segp->seg_out;
+ pp->pt_inflip = 1;
+ INSERT_PT(newpp, pp);
+ goto done_weave;
+ }
+ /* NOTREACHED */
+ } else {
+ /*
+ * diff < ~~0
+ *
+ * Seg starts before current partition starts,
+ * but after the previous partition ends.
+ * SSSSSSSS...
+ * PPPPP...
+ * newpp|pp
+ */
+ GET_PT_INIT(0, newpp, res);
+ bu_ptbl_ins_unique(&newpp->pt_seglist, (long *)segp);
+ newpp->pt_inseg = lastseg;
+ newpp->pt_inhit = lasthit;
+ newpp->pt_inflip = lastflip;
+ diff = segp->seg_out.hit_dist - pp->pt_inhit->hit_dist;
+ if (diff < -(tol_dist)) {
+ /*
+ * diff < ~0
+ * Seg starts and ends before current
+ * partition, but after previous
+ * partition ends (diff < 0).
+ * SSSS
+ * pppp PPPPP...
+ * newpp pp
+ */
+ newpp->pt_outseg = segp;
+ newpp->pt_outhit = &segp->seg_out;
+ newpp->pt_outflip = 0;
+ INSERT_PT(newpp, pp);
+ goto done_weave;
+ }
+ if (diff < tol_dist) {
+ /*
+ * diff ~= 0
+ *
+ * Seg starts before current
+ * partition starts, and ends at or
+ * near the start of the partition.
+ * (diff == 0). FUSE the points.
+ * SSSSSS
+ * PPPPP
+ * newpp|pp
+ * NOTE: only copy hit point, not
+ * normals or norm private stuff.
+ */
+ newpp->pt_outseg = segp;
+ newpp->pt_outhit = &segp->seg_out;
+ newpp->pt_outhit->hit_dist = pp->pt_inhit->hit_dist;
+ newpp->pt_outflip = 0;
+ INSERT_PT(newpp, pp);
+ goto done_weave;
+ }
+ /*
+ * Seg starts before current partition
+ * starts, and ends after the start of the
+ * partition. (diff > 0).
+ * SSSSSSSSSS
+ * PPPPPPP
+ * newpp| pp | ...
+ */
+ newpp->pt_outseg = pp->pt_inseg;
+ newpp->pt_outhit = pp->pt_inhit;
+ newpp->pt_outflip = 1;
+ lastseg = pp->pt_inseg;
+ lasthit = pp->pt_inhit;
+ lastflip = newpp->pt_outflip;
+ INSERT_PT(newpp, pp);
+ goto equal_start;
+ }
+ /* NOTREACHED */
+ }
+
+ /*
+ * Segment has portion which extends beyond the end
+ * of the last partition. Tack on the remainder.
+ * PPPPP
+ * SSSSS
+ */
+ GET_PT_INIT(0, newpp, res);
+ bu_ptbl_ins_unique(&newpp->pt_seglist, (long *)segp);
+ newpp->pt_inseg = lastseg;
+ newpp->pt_inhit = lasthit;
+ newpp->pt_inflip = lastflip;
+ newpp->pt_outseg = segp;
+ newpp->pt_outhit = &segp->seg_out;
+ APPEND_PT(newpp, PartHdp->pt_back);
+
+ done_weave: ; /* Sorry about the goto's, but they give clarity */
+ }
+}
+
+/* Boolean values. Not easy to change, but defined symbolically */
+#define BOOL_FALSE 0
+#define BOOL_TRUE 1
+
+extern int
+rt_bool_partition_eligible(register const struct bu_ptbl *regiontable, register const struct bu_bitv *solidbits, register const struct partition *pp);
+extern int
+rt_booleval(register union tree *treep, struct partition *partp, struct region **trueregp, struct resource *resp);
+extern int
+rt_overlap_tables_equal(struct region *const*a, struct region *const*b);
+
+
+int
+my_boolfinal(struct partition *InputHdp, struct partition *FinalHdp, fastf_t enddist, struct bu_ptbl *regiontable, struct application *ap, const struct bu_bitv *solidbits)
+{
+ struct region *lastregion = (struct region *)NULL;
+ struct region *TrueRg[2];
+ register struct partition *pp;
+ register int claiming_regions;
+ int hits_avail = 0;
+ int hits_needed;
+ int indefinite_outpt = 0;
+ fastf_t diff;
+
+#define HITS_TODO (hits_needed - hits_avail)
+
+ RT_CK_PT_HD(InputHdp);
+ RT_CK_PT_HD(FinalHdp);
+ BU_CK_PTBL(regiontable);
+ RT_CK_RTI(ap->a_rt_i);
+ BU_CK_BITV(solidbits);
+
+ if (!ap->a_multioverlap)
+ ap->a_multioverlap = rt_default_multioverlap;
+
+ if (!ap->a_logoverlap)
+ ap->a_logoverlap = rt_default_logoverlap;
+
+ if (enddist <= 0) {
+ return 0;
+ }
+
+ if (ap->a_onehit < 0)
+ hits_needed = -ap->a_onehit;
+ else
+ hits_needed = ap->a_onehit;
+
+ if (ap->a_onehit != 0) {
+ register struct partition *npp = FinalHdp->pt_forw;
+
+ for (; npp != FinalHdp; npp = npp->pt_forw) {
+ if (npp->pt_inhit->hit_dist < 0.0)
+ continue;
+ if (ap->a_onehit < 0 && npp->pt_regionp->reg_aircode != 0)
+ continue; /* skip air hits */
+ hits_avail += 2; /* both in and out listed */
+ }
+ if (hits_avail >= hits_needed) {
+ return 1;
+ }
+ }
+
+ if (ap->a_no_booleans) {
+ while ((pp = InputHdp->pt_forw) != InputHdp) {
+ RT_CK_PT(pp);
+ DEQUEUE_PT(pp);
+ pp->pt_regionp = (struct region *)
+ BU_PTBL_GET(&pp->pt_inseg->seg_stp->st_regions, 0);
+ RT_CK_REGION(pp->pt_regionp);
+ INSERT_PT(pp, FinalHdp);
+ }
+ return 0;
+ }
+
+ pp = InputHdp->pt_forw;
+ while (pp != InputHdp) {
+ RT_CK_PT(pp);
+ claiming_regions = 0;
+ RT_CHECK_SEG(pp->pt_inseg);
+ RT_CHECK_SEG(pp->pt_outseg);
+
+ /* Force "very thin" partitions to have exactly zero thickness. */
+ if (NEAR_EQUAL(pp->pt_inhit->hit_dist, pp->pt_outhit->hit_dist, ap->a_rt_i->rti_tol.dist)) {
+ pp->pt_outhit->hit_dist = pp->pt_inhit->hit_dist;
+ }
+
+
+ /* Sanity checks on sorting. */
+ if (pp->pt_inhit->hit_dist > pp->pt_outhit->hit_dist) {
+ rt_pr_partitions(ap->a_rt_i, InputHdp, "With problem");
+ }
+ if (pp->pt_forw != InputHdp) {
+ diff = pp->pt_outhit->hit_dist - pp->pt_forw->pt_inhit->hit_dist;
+ if (!ZERO(diff)) {
+ if (NEAR_ZERO(diff, ap->a_rt_i->rti_tol.dist)) {
+ pp->pt_forw->pt_inhit->hit_dist = pp->pt_outhit->hit_dist;
+ } else if (diff > 0) {
+ return 0;
+ }
+ }
+ }
+
+ /*
+ * If partition is behind ray start point, discard it.
+ *
+ * Partition may start before current box starts, because it's
+ * still waiting for all its solids to be shot.
+ */
+ if (pp->pt_outhit->hit_dist < ap->a_rt_i->rti_tol.dist) {
+ register struct partition *zap_pp;
+ zap_pp = pp;
+ pp = pp->pt_forw;
+ DEQUEUE_PT(zap_pp);
+ FREE_PT(zap_pp, ap->a_resource);
+ continue;
+ }
+
+ /*
+ * If partition begins beyond current box end, the state of
+ * the partition is not fully known yet, and new partitions
+ * might be added in front of this one, so stop now.
+ */
+ diff = pp->pt_inhit->hit_dist - enddist;
+ if (diff > ap->a_rt_i->rti_tol.dist) {
+ return 0;
+ }
+
+ /*
+ * If partition ends somewhere beyond the end of the current
+ * box, the condition of the outhit information is not fully
+ * known yet. The partition might be broken or shortened by
+ * subsequent segments, not discovered until entering future
+ * boxes.
+ */
+ diff = pp->pt_outhit->hit_dist - enddist;
+ if (diff > ap->a_rt_i->rti_tol.dist) {
+ if (ap->a_onehit != 1) {
+ return 0;
+ }
+ /* pt_outhit may not be correct */
+ indefinite_outpt = 1;
+ } else {
+ indefinite_outpt = 0;
+ }
+
+ /* XXX a_ray_length checking should be done here, not in
+ * rt_shootray()
+ */
+
+ /* Start with a clean slate when evaluating this partition */
+ bu_ptbl_reset(regiontable);
+
+ /*
+ * For each segment's solid that lies in this partition, add
+ * the list of regions that refer to that solid into the
+ * "regiontable" array.
+ */
+ {
+ struct seg **segpp;
+
+ for (BU_PTBL_FOR(segpp, (struct seg **), &pp->pt_seglist)) {
+ struct soltab *stp = (*segpp)->seg_stp;
+ RT_CK_SOLTAB(stp);
+ bu_ptbl_cat_uniq(regiontable, &stp->st_regions);
+ }
+ }
+
+ if (indefinite_outpt) {
+ /*
+ * More hits still needed. HITS_TODO > 0. If every solid
+ * in every region participating in this partition has
+ * been intersected, then it is OK to evaluate it now.
+ */
+ if (!rt_bool_partition_eligible(regiontable, solidbits, pp)) {
+ return 0;
+ }
+ }
+
+ /* Evaluate the boolean trees of any regions involved */
+ {
+ struct region **regpp;
+ for (BU_PTBL_FOR(regpp, (struct region **), regiontable)) {
+ register struct region *regp;
+
+ regp = *regpp;
+ RT_CK_REGION(regp);
+ if (regp->reg_all_unions) {
+ claiming_regions++;
+ lastregion = regp;
+ continue;
+ }
+ if (rt_booleval(regp->reg_treetop, pp, TrueRg,
+ ap->a_resource) == BOOL_FALSE) {
+ /* Null out non-claiming region's pointer */
+ *regpp = REGION_NULL;
+ continue;
+ }
+ /* This region claims partition */
+ claiming_regions++;
+ lastregion = regp;
+ }
+ }
+ if (claiming_regions == 0) {
+ pp = pp->pt_forw; /* onwards! */
+ continue;
+ }
+
+ if (claiming_regions > 1) {
+ /*
+ * There is an overlap between two or more regions, invoke
+ * multi-overlap handler.
+ */
+ bu_ptbl_rm(regiontable, (long *)NULL);
+ ap->a_logoverlap(ap, pp, regiontable, InputHdp);
+ ap->a_multioverlap(ap, pp, regiontable, InputHdp);
+
+ /* Count number of remaining regions, s/b 0 or 1 */
+ claiming_regions = 0;
+ {
+ register struct region **regpp;
+ for (BU_PTBL_FOR(regpp, (struct region **), regiontable)) {
+ if (*regpp != REGION_NULL) {
+ claiming_regions++;
+ lastregion = *regpp;
+ }
+ }
+ }
+
+ /*
+ * If claiming_regions == 0, discard partition.
+ * If claiming_regions > 1, signal error and discard.
+ * There is nothing further we can do to fix it.
+ */
+ if (claiming_regions > 1) {
+ rt_pr_pt(ap->a_rt_i, pp);
+ }
+
+ if (claiming_regions != 1) {
+ register struct partition *zap_pp;
+
+ zap_pp = pp;
+ pp = pp->pt_forw; /* onwards! */
+ DEQUEUE_PT(zap_pp);
+ FREE_PT(zap_pp, ap->a_resource);
+ continue;
+ }
+ }
+
+ /*
+ * claiming_regions == 1
+ *
+ * Remove this partition from the input queue, and append it
+ * to the result queue.
+ */
+ {
+ register struct partition *newpp;
+ register struct partition *lastpp;
+ newpp = pp;
+ pp=pp->pt_forw; /* onwards! */
+ DEQUEUE_PT(newpp);
+ RT_CHECK_SEG(newpp->pt_inseg); /* sanity */
+ RT_CHECK_SEG(newpp->pt_outseg); /* sanity */
+ /* Record the "owning" region. pt_regionp = NULL before here. */
+ newpp->pt_regionp = lastregion;
+
+ /* See if this new partition extends the previous last
+ * partition, "exactly" matching.
+ */
+ lastpp = FinalHdp->pt_back;
+ if (lastpp != FinalHdp &&
+ lastregion == lastpp->pt_regionp &&
+ NEAR_EQUAL(newpp->pt_inhit->hit_dist,
+ lastpp->pt_outhit->hit_dist,
+ ap->a_rt_i->rti_tol.dist) &&
+ (ap->a_rt_i->rti_save_overlaps == 0 ||
+ rt_overlap_tables_equal(
+ lastpp->pt_overlap_reg,
+ newpp->pt_overlap_reg))
+ ) {
+ /* same region, merge by extending last final partition */
+ RT_CK_PT(lastpp);
+ RT_CHECK_SEG(lastpp->pt_inseg); /* sanity */
+ RT_CHECK_SEG(lastpp->pt_outseg);/* sanity */
+ lastpp->pt_outhit = newpp->pt_outhit;
+ lastpp->pt_outflip = newpp->pt_outflip;
+ lastpp->pt_outseg = newpp->pt_outseg;
+
+ /* Don't lose the fact that the two solids of this
+ * partition contributed.
+ */
+ bu_ptbl_ins_unique(&lastpp->pt_seglist, (long *)newpp->pt_inseg);
+ bu_ptbl_ins_unique(&lastpp->pt_seglist, (long *)newpp->pt_outseg);
+
+ FREE_PT(newpp, ap->a_resource);
+ newpp = lastpp;
+ } else {
+ APPEND_PT(newpp, lastpp);
+ if (!(ap->a_onehit < 0 && newpp->pt_regionp->reg_aircode != 0))
+ hits_avail += 2;
+ }
+
+ RT_CHECK_SEG(newpp->pt_inseg); /* sanity */
+ RT_CHECK_SEG(newpp->pt_outseg); /* sanity */
+ }
+
+ /* See if it's worthwhile breaking out of partition loop early */
+ if (ap->a_onehit != 0 && HITS_TODO <= 0) {
+ return 1;
+ }
+ }
+ if (ap->a_onehit != 0 && HITS_TODO <= 0) {
+ return 1;
+ } else {
+ return 0;
+ }
+}
+
+
+fastf_t
+rt_find_backing_dist(struct rt_shootray_status *ss, struct bu_bitv *backbits);
+const union cutter *
+rt_advance_to_next_cell(register struct rt_shootray_status *ssp);
+
+
+int
+my_shootray(struct resource *resp, struct xray *a_ray, struct rt_i *rtip, register struct application *ap, struct partition *pFinalPart, struct seg *pfinished_segs)
+{
+ struct rt_shootray_status ss;
+ struct seg new_segs; /* from solid intersections */
+ struct seg waiting_segs; /* awaiting rt_boolweave() */
+ struct bu_bitv *solidbits; /* bits for all solids shot so far */
+ struct bu_bitv *backbits=NULL; /* bits for all solids using pieces that need to be intersected behind
+ the ray start point */
+ struct bu_ptbl *regionbits; /* table of all involved regions */
+ struct partition InitialPart; /* Head of Initial Partitions */
+ struct soltab **stpp;
+ register const union cutter *cutp;
+ fastf_t pending_hit = 0; /* dist of closest odd hit pending */
+
+ ss.ap = ap;
+ ss.resp = resp;
+
+ InitialPart.pt_forw = InitialPart.pt_back = &InitialPart;
+ InitialPart.pt_magic = PT_HD_MAGIC;
+
+ BU_LIST_INIT(&new_segs.l);
+ BU_LIST_INIT(&waiting_segs.l);
+
+ if (!BU_LIST_IS_INITIALIZED(&resp->re_parthead)) {
+ /*
+ * We've been handed a mostly un-initialized resource struct,
+ * with only a magic number and a cpu number filled in. Init
+ * it and add it to the table. This is how
+ * application-provided resource structures are remembered for
+ * later cleanup by the library.
+ */
+ rt_init_resource(resp, resp->re_cpu, rtip);
+ }
+
+ solidbits = rt_get_solidbitv(rtip->nsolids, resp);
+
+ if (BU_LIST_IS_EMPTY(&resp->re_region_ptbl)) {
+ BU_ALLOC(regionbits, struct bu_ptbl);
+ bu_ptbl_init(regionbits, 7, "rt_shootray() regionbits ptbl");
+ } else {
+ regionbits = BU_LIST_FIRST(bu_ptbl, &resp->re_region_ptbl);
+ BU_LIST_DEQUEUE(®ionbits->l);
+ BU_CK_PTBL(regionbits);
+ }
+
+ if (!resp->re_pieces && rtip->rti_nsolids_with_pieces > 0) {
+ /* Initialize this processors 'solid pieces' state */
+ rt_res_pieces_init(resp, rtip);
+ }
+ if (UNLIKELY(!BU_LIST_MAGIC_EQUAL(&resp->re_pieces_pending.l, BU_PTBL_MAGIC))) {
+ /* only happens first time through */
+ bu_ptbl_init(&resp->re_pieces_pending, 100, "re_pieces_pending");
+ }
+ bu_ptbl_reset(&resp->re_pieces_pending);
+
+ /*
+ * Record essential statistics in per-processor data structure.
+ */
+ resp->re_nshootray++;
+
+ /* Compute the inverse of the direction cosines */
+ if (a_ray->r_dir[X] < -SQRT_SMALL_FASTF) {
+ ss.abs_inv_dir[X] = -(ss.inv_dir[X]=1.0/a_ray->r_dir[X]);
+ ss.rstep[X] = -1;
+ } else if (a_ray->r_dir[X] > SQRT_SMALL_FASTF) {
+ ss.abs_inv_dir[X] = (ss.inv_dir[X]=1.0/a_ray->r_dir[X]);
+ ss.rstep[X] = 1;
+ } else {
+ a_ray->r_dir[X] = 0.0;
+ ss.abs_inv_dir[X] = ss.inv_dir[X] = INFINITY;
+ ss.rstep[X] = 0;
+ }
+ if (a_ray->r_dir[Y] < -SQRT_SMALL_FASTF) {
+ ss.abs_inv_dir[Y] = -(ss.inv_dir[Y]=1.0/a_ray->r_dir[Y]);
+ ss.rstep[Y] = -1;
+ } else if (a_ray->r_dir[Y] > SQRT_SMALL_FASTF) {
+ ss.abs_inv_dir[Y] = (ss.inv_dir[Y]=1.0/a_ray->r_dir[Y]);
+ ss.rstep[Y] = 1;
+ } else {
+ a_ray->r_dir[Y] = 0.0;
+ ss.abs_inv_dir[Y] = ss.inv_dir[Y] = INFINITY;
+ ss.rstep[Y] = 0;
+ }
+ if (a_ray->r_dir[Z] < -SQRT_SMALL_FASTF) {
+ ss.abs_inv_dir[Z] = -(ss.inv_dir[Z]=1.0/a_ray->r_dir[Z]);
+ ss.rstep[Z] = -1;
+ } else if (a_ray->r_dir[Z] > SQRT_SMALL_FASTF) {
+ ss.abs_inv_dir[Z] = (ss.inv_dir[Z]=1.0/a_ray->r_dir[Z]);
+ ss.rstep[Z] = 1;
+ } else {
+ a_ray->r_dir[Z] = 0.0;
+ ss.abs_inv_dir[Z] = ss.inv_dir[Z] = INFINITY;
+ ss.rstep[Z] = 0;
+ }
+ VMOVE(ap->a_inv_dir, ss.inv_dir);
+
+ /*
+ * If ray does not enter the model RPP, skip on. If ray ends
+ * exactly at the model RPP, trace it.
+ */
+ if (!rt_in_rpp(a_ray, ss.inv_dir, rtip->mdl_min, rtip->mdl_max) ||
+ a_ray->r_max < 0.0) {
+ cutp = &rtip->rti_inf_box;
+ if (cutp->bn.bn_len > 0) {
+ /* Model has infinite solids, need to fire at them. */
+ ss.box_start = BACKING_DIST;
+ ss.model_start = 0;
+ ss.box_end = ss.model_end = INFINITY;
+ ss.lastcut = CUTTER_NULL;
+ ss.old_status = (struct rt_shootray_status *)NULL;
+ ss.curcut = cutp;
+ ss.lastcell = ss.curcut;
+ VMOVE(ss.curmin, rtip->mdl_min);
+ VMOVE(ss.curmax, rtip->mdl_max);
+ ss.newray = *a_ray; /* struct copy */
+ ss.odist_corr = ss.obox_start = ss.obox_end = -99;
+ ss.dist_corr = 0.0;
+ goto start_cell;
+ }
+ resp->re_nmiss_model++;
+ if (ap->a_miss)
+ ap->a_return = ap->a_miss(ap);
+ else
+ ap->a_return = 0;
+ goto out;
+ }
+
+ /*
+ * The interesting part of the ray starts at distance 0. If the
+ * ray enters the model at a negative distance, (i.e., the ray
+ * starts within the model RPP), we only look at little bit behind
+ * (BACKING_DIST) to see if we are just coming out of something,
+ * but never further back than the intersection with the model
+ * RPP. If the ray enters the model at a positive distance, we
+ * always start there. It is vital that we never pick a start
+ * point outside the model RPP, or the space partitioning tree
+ * will pick the wrong box and the ray will miss it.
+ *
+ * BACKING_DIST should probably be determined by floating point
+ * noise factor due to model RPP size -vs- number of bits of
+ * floating point mantissa significance, rather than a constant,
+ * but that is too hideous to think about here. Also note that
+ * applications that really depend on knowing what region they are
+ * leaving from should probably back their own start-point up,
+ * rather than depending on it here, but it isn't much trouble
+ * here.
+ *
+ * Modification by JRA for pieces methodology:
+ *
+ * The original algorithm here assumed that if we encountered any
+ * primitive along the positive direction of the ray, ALL its
+ * intersections would be calculated. With pieces, we may see
+ * only an exit hit if the entrance piece is in a space partition
+ * cell that is more than "BACKING_DIST" behind the ray start
+ * point (leading to incorrect results). I have modified the
+ * setting of "ss.box_start" (when pieces are present and the ray
+ * start point is inside the model bounding box) as follows (see
+ * rt_find_backing_dist()):
+ *
+ * - The ray is traced through the space partitioning tree.
+ *
+ * - The ray is intersected with the bounding box of each
+ * primitive using pieces in each cell
+ *
+ * - The minimum of all these intersections is set as the initial
+ * "ss.box_start".
+ *
+ * - The "backbits" bit vector has a bit set for each of the
+ * primitives using pieces that have bounding boxes that extend
+ * behind the ray start point
+ *
+ * Further below (in the "pieces" loop), I have added code to
+ * ignore primitives that do not have a bit set in the backbits
+ * vector when we are behind the ray start point.
+ */
+
+ /* these two values set the point where the ray tracing actually
+ * begins and ends
+ */
+ ss.box_start = ss.model_start = a_ray->r_min;
+ ss.box_end = ss.model_end = a_ray->r_max;
+
+ if (rtip->rti_nsolids_with_pieces > 0) {
+ /* pieces are present */
+ if (ss.box_start < BACKING_DIST) {
+ /* the first ray intersection with the model bounding box
+ * is more than BACKING_DIST behind the ray start point
+ */
+
+ /* get a bit vector to keep track of which primitives need
+ * to be intersected behind the ray start point (those
+ * having bounding boxes extending behind the ray start
+ * point and using pieces)
+ */
+ backbits = rt_get_solidbitv(rtip->nsolids, resp);
+
+ /* call "rt_find_backing_dist()" to calculate the required
+ * start point for calculation, and to fill in the
+ * "backbits" bit vector
+ */
+ ss.box_start = rt_find_backing_dist(&ss, backbits);
+ }
+ } else {
+ /* no pieces present, use the old scheme */
+ if (ss.box_start < BACKING_DIST)
+ ss.box_start = BACKING_DIST; /* Only look a little bit behind */
+ }
+
+ ss.lastcut = CUTTER_NULL;
+ ss.old_status = (struct rt_shootray_status *)NULL;
+ ss.curcut = &rtip->rti_CutHead;
+ if (ss.curcut->cut_type == CUT_NUGRIDNODE) {
+ ss.lastcell = CUTTER_NULL;
+ VSET(ss.curmin, ss.curcut->nugn.nu_axis[X][0].nu_spos,
+ ss.curcut->nugn.nu_axis[Y][0].nu_spos,
+ ss.curcut->nugn.nu_axis[Z][0].nu_spos);
+ VSET(ss.curmax, ss.curcut->nugn.nu_axis[X][ss.curcut->nugn.nu_cells_per_axis[X]-1].nu_epos,
+ ss.curcut->nugn.nu_axis[Y][ss.curcut->nugn.nu_cells_per_axis[Y]-1].nu_epos,
+ ss.curcut->nugn.nu_axis[Z][ss.curcut->nugn.nu_cells_per_axis[Z]-1].nu_epos);
+ } else if (ss.curcut->cut_type == CUT_CUTNODE ||
+ ss.curcut->cut_type == CUT_BOXNODE) {
+ ss.lastcell = ss.curcut;
+ VMOVE(ss.curmin, rtip->mdl_min);
+ VMOVE(ss.curmax, rtip->mdl_max);
+ }
+
+ ss.newray = *a_ray; /* struct copy */
+ ss.odist_corr = ss.obox_start = ss.obox_end = -99;
+ ss.dist_corr = 0.0;
+ ss.box_num = 0;
+
+ /*
+ * While the ray remains inside model space, push from box to box
+ * until ray emerges from model space again (or first hit is
+ * found, if user is impatient). It is vitally important to
+ * always stay within the model RPP, or the space partitioning tree
+ * will pick wrong boxes & miss them.
+ */
+ while ((cutp = rt_advance_to_next_cell(&ss)) != CUTTER_NULL) {
+ start_cell:
+ if (cutp->bn.bn_len <= 0 && cutp->bn.bn_piecelen <= 0) {
+ /* Push ray onwards to next box */
+ ss.box_start = ss.box_end;
+ resp->re_nempty_cells++;
+ continue;
+ }
+
+ /* Consider all "pieces" of all solids within the box */
+ pending_hit = ss.box_end;
+ if (cutp->bn.bn_piecelen > 0) {
+ register struct rt_piecelist *plp;
+
+ plp = &(cutp->bn.bn_piecelist[cutp->bn.bn_piecelen-1]);
+ for (; plp >= cutp->bn.bn_piecelist; plp--) {
+ struct rt_piecestate *psp;
+ struct soltab *stp;
+ int ret;
+ int had_hits_before;
+
+ RT_CK_PIECELIST(plp);
+
+ /* Consider all pieces of this one solid in this
+ * cell.
+ */
+ stp = plp->stp;
+ RT_CK_SOLTAB(stp);
+
+ if (backbits && ss.box_end < BACKING_DIST && BU_BITTEST(backbits, stp->st_bit) == 0) {
+ /* we are behind the ray start point and this
+ * primitive is not one that we need to intersect
+ * back here.
+ */
+ continue;
+ }
+
+ psp = &(resp->re_pieces[stp->st_piecestate_num]);
+ RT_CK_PIECESTATE(psp);
+ if (psp->ray_seqno != resp->re_nshootray) {
+ /* state is from an earlier ray, scrub */
+ BU_BITV_ZEROALL(psp->shot);
+ psp->ray_seqno = resp->re_nshootray;
+ rt_htbl_reset(&psp->htab);
+
+ /* Compute ray entry and exit to entire solid's
+ * bounding box.
+ */
+ if (!rt_in_rpp(&ss.newray, ss.inv_dir,
+ stp->st_min, stp->st_max)) {
+ resp->re_prune_solrpp++;
+ BU_BITSET(solidbits, stp->st_bit);
+ continue; /* MISS */
+ }
+ psp->mindist = ss.newray.r_min + ss.dist_corr;
+ psp->maxdist = ss.newray.r_max + ss.dist_corr;
+ had_hits_before = 0;
+ } else {
+ if (BU_BITTEST(solidbits, stp->st_bit)) {
+ /* we missed the solid RPP in an earlier cell */
+ resp->re_ndup++;
+ continue; /* already shot */
+ }
+ had_hits_before = psp->htab.end;
+ }
+
+ /*
+ * Allow this solid to shoot at all of its 'pieces' in
+ * this cell, all at once. 'newray' has been
+ * transformed to be near to this cell, and
+ * 'dist_corr' is the additive correction factor that
+ * ft_piece_shot() must apply to hits calculated using
+ * 'newray'.
+ */
+ resp->re_piece_shots++;
+ psp->cutp = cutp;
+
+ ret = -1;
+ if (stp->st_meth->ft_piece_shot) {
+ ret = stp->st_meth->ft_piece_shot(psp, plp, ss.dist_corr, &ss.newray, ap, &waiting_segs);
+ }
+ if (ret <= 0) {
+ /* No hits at all */
+ resp->re_piece_shot_miss++;
+ } else {
+ resp->re_piece_shot_hit++;
+ }
+
+ /* See if this solid has been fully processed yet. If
+ * ray has passed through bounding volume, we're done.
+ * ft_piece_hitsegs() will only be called once per
+ * ray.
+ */
+ if (ss.box_end > psp->maxdist && psp->htab.end > 0) {
+ /* Convert hits into segs */
+ /* Distance correction was handled in ft_piece_shot */
+ if (stp->st_meth->ft_piece_hitsegs)
+ stp->st_meth->ft_piece_hitsegs(psp, &waiting_segs, ap);
+ rt_htbl_reset(&psp->htab);
+ BU_BITSET(solidbits, stp->st_bit);
+
+ if (had_hits_before)
+ bu_ptbl_rm(&resp->re_pieces_pending, (long *)psp);
+ } else {
+ if (!had_hits_before)
+ bu_ptbl_ins_unique(&resp->re_pieces_pending, (long *)psp);
+ }
+ }
+ }
+
+ /* Consider all solids within the box */
+ if (cutp->bn.bn_len > 0 && ss.box_end >= BACKING_DIST) {
+ stpp = &(cutp->bn.bn_list[cutp->bn.bn_len-1]);
+ for (; stpp >= cutp->bn.bn_list; stpp--) {
+ register struct soltab *stp = *stpp;
+ int ret;
+
+ if (BU_BITTEST(solidbits, stp->st_bit)) {
+ resp->re_ndup++;
+ continue; /* already shot */
+ }
+
+ /* Shoot a ray */
+ BU_BITSET(solidbits, stp->st_bit);
+
+ /* Check against bounding RPP, if desired by solid */
+ if (stp->st_meth->ft_use_rpp) {
+ if (!rt_in_rpp(&ss.newray, ss.inv_dir,
+ stp->st_min, stp->st_max)) {
+ resp->re_prune_solrpp++;
+ continue; /* MISS */
+ }
+ if (ss.dist_corr + ss.newray.r_max < BACKING_DIST) {
+ resp->re_prune_solrpp++;
+ continue; /* MISS */
+ }
+ }
+
+ resp->re_shots++;
+ BU_LIST_INIT(&(new_segs.l));
+
+ ret = -1;
+
+ if (stp->st_meth->ft_shot) {
+ ret = stp->st_meth->ft_shot(stp, &ss.newray, ap, &new_segs);
+ }
+ if (ret <= 0) {
+ resp->re_shot_miss++;
+ continue; /* MISS */
+ }
+
+ /* Add seg chain to list awaiting rt_boolweave() */
+ {
+ register struct seg *s2;
+ while (BU_LIST_WHILE(s2, seg, &(new_segs.l))) {
+ BU_LIST_DEQUEUE(&(s2->l));
+ /* Restore to original distance */
+ s2->seg_in.hit_dist += ss.dist_corr;
+ s2->seg_out.hit_dist += ss.dist_corr;
+ s2->seg_in.hit_rayp = s2->seg_out.hit_rayp = a_ray;
+ BU_LIST_INSERT(&(waiting_segs.l), &(s2->l));
+ }
+ }
+ resp->re_shot_hit++;
+ }
+ }
+
+ /*
+ * If a_onehit == 0 and a_ray_length <= 0, then the ray is
+ * traced to +infinity.
+ *
+ * If a_onehit != 0, then it indicates how many hit points
+ * (which are greater than the ray start point of 0.0) the
+ * application requires, i.e., partitions with inhit >= 0. (If
+ * negative, indicates number of non-air hits needed). If
+ * this box yielded additional segments, immediately weave
+ * them into the partition list, and perform final boolean
+ * evaluation. If this results in the required number of
+ * final partitions, then cease ray-tracing and hand the
+ * partitions over to the application. All partitions will
+ * have valid in and out distances. a_ray_length is treated
+ * similarly to a_onehit.
+ */
+ if (BU_LIST_NON_EMPTY(&(waiting_segs.l))) {
+ if (ap->a_onehit != 0) {
+ int done;
+
+ /* Weave these segments into partition list */
+ my_boolweave(resp, pfinished_segs, &waiting_segs, &InitialPart, rtip->rti_tol.dist, rtip->nsolids, ap->a_no_booleans);
+
+ if (BU_PTBL_LEN(&resp->re_pieces_pending) > 0) {
+
+ /* Find the lowest pending mindist, that's as far
+ * as boolfinal can progress to.
+ */
+ struct rt_piecestate **psp;
+ for (BU_PTBL_FOR(psp, (struct rt_piecestate **), &resp->re_pieces_pending)) {
+ register fastf_t dist;
+
+ dist = (*psp)->mindist;
+ if (dist < pending_hit) {
+ pending_hit = dist;
+ }
+ }
+ }
+
+ /* Evaluate regions up to end of good segs */
+ if (ss.box_end < pending_hit) pending_hit = ss.box_end;
+ done = my_boolfinal(&InitialPart, pFinalPart, pending_hit, regionbits, ap, solidbits);
+
+ /* See if enough partitions have been acquired */
+ if (done > 0) goto hitit;
+ }
+ }
+
+ if (ap->a_ray_length > 0.0 &&
+ ss.box_end >= ap->a_ray_length &&
+ ap->a_ray_length < pending_hit)
+ goto weave;
+
+ /* Push ray onwards to next box */
+ ss.box_start = ss.box_end;
+ }
+
+ /*
+ * Ray has finally left known space -- Weave any remaining
+ * segments into the partition list.
+ */
+weave:
+ /* Process any pending hits into segs */
+ if (BU_PTBL_LEN(&resp->re_pieces_pending) > 0) {
+ struct rt_piecestate **psp;
+ for (BU_PTBL_FOR(psp, (struct rt_piecestate **), &resp->re_pieces_pending)) {
+ if ((*psp)->htab.end > 0) {
+ /* Convert any pending hits into segs */
+ /* Distance correction was handled in ft_piece_shot */
+ (*psp)->stp->st_meth->ft_piece_hitsegs(*psp, &waiting_segs, ap);
+ rt_htbl_reset(&(*psp)->htab);
+ }
+ *psp = NULL;
+ }
+ bu_ptbl_reset(&resp->re_pieces_pending);
+ }
+
+ if (BU_LIST_NON_EMPTY(&(waiting_segs.l))) {
+ my_boolweave(resp, pfinished_segs, &waiting_segs, &InitialPart, rtip->rti_tol.dist, rtip->nsolids, ap->a_no_booleans);
+ }
+
+ /* finished_segs chain now has all segments hit by this ray */
+ if (BU_LIST_IS_EMPTY(&(pfinished_segs->l))) {
+ ap->a_return = 0;
+ goto out;
+ }
+
+ /*
+ * All intersections of the ray with the model have been computed.
+ * Evaluate the boolean trees over each partition.
+ */
+ (void)my_boolfinal(&InitialPart, pFinalPart, INFINITY, regionbits, ap, solidbits);
+
+ if (pFinalPart->pt_forw == pFinalPart) {
+ ap->a_return = 0;
+ RT_FREE_PT_LIST(&InitialPart, resp);
+ goto out;
+ }
+
+ /*
+ * Ray/model intersections exist. Pass the list to the user's
+ * a_hit() routine. Note that only the hit_dist elements of
+ * pt_inhit and pt_outhit have been computed yet. To compute both
+ * hit_point and hit_normal, use the
+ *
+ * RT_HIT_NORMAL(NULL, hitp, stp, rayp, 0);
+ *
+ * macro. To compute just hit_point, use
+ *
+ * VJOIN1(hitp->hit_point, rp->r_pt, hitp->hit_dist, rp->r_dir);
+ */
+hitit:
+ /*
+ * Before recursing, release storage for unused Initial
+ * partitions. finished_segs can not be released yet, because
+ * FinalPart partitions will point to hits in those segments.
+ */
+ RT_FREE_PT_LIST(&InitialPart, resp);
+
+ /*
+ * finished_segs is only used by special hit routines which don't
+ * follow the traditional solid modeling paradigm.
+ */
+ ap->a_return = 1;
+
+ /*
+ * Processing of this ray is complete.
+ */
+out:
+ /* Return dynamic resources to their freelists. */
+ BU_CK_BITV(solidbits);
+ BU_LIST_APPEND(&resp->re_solid_bitv, &solidbits->l);
+ if (backbits) {
+ BU_CK_BITV(backbits);
+ BU_LIST_APPEND(&resp->re_solid_bitv, &backbits->l);
+ }
+ BU_CK_PTBL(regionbits);
+ BU_LIST_APPEND(&resp->re_region_ptbl, ®ionbits->l);
+
+ /* Clean up any pending hits */
+ if (BU_PTBL_LEN(&resp->re_pieces_pending) > 0) {
+ struct rt_piecestate **psp;
+ for (BU_PTBL_FOR(psp, (struct rt_piecestate **), &resp->re_pieces_pending)) {
+ if ((*psp)->htab.end > 0)
+ rt_htbl_reset(&(*psp)->htab);
+ }
+ bu_ptbl_reset(&resp->re_pieces_pending);
+ }
+
+ /* Terminate any logging */
+ return ap->a_return;
+}
+
+/**
+ * Arrange to have the pixel output. a_uptr has region pointer, for
+ * reference.
+ */
+void
+my_view_pixel(int a_x, int a_y, int a_user, point_t a_color)
+{
+ int r, g, b;
+ unsigned char *pixelp;
+ struct scanline *slp;
+
+ if (a_user == 0) {
+ /* Shot missed the model, don't dither */
+ r = ibackground[0];
+ g = ibackground[1];
+ b = ibackground[2];
+ VSETALL(a_color, -1e-20); /* background flag */
+ } else {
+ r = a_color[0]*255;
+ g = a_color[1]*255;
+ b = a_color[2]*255;
+ if (r > 255) r = 255;
+ else if (r < 0) r = 0;
+ if (g > 255) g = 255;
+ else if (g < 0) g = 0;
+ if (b > 255) b = 255;
+ else if (b < 0) b = 0;
+ if (r == ibackground[0] && g == ibackground[1] && b == ibackground[2]) {
+ r = inonbackground[0];
+ g = inonbackground[1];
+ b = inonbackground[2];
+ }
+
+ /* Make sure it's never perfect black */
+ if (r==0 && g==0 && b==0)
+ b = 1;
+ }
+
+ slp = &scanline;
+ if (slp->sl_buf == (unsigned char *)0) {
+ slp->sl_buf = (unsigned char *)bu_calloc(width, pwidth, "sl_buf scanline buffer");
+ slp->sl_left = width;
+ }
+ pixelp = slp->sl_buf+(a_x*pwidth);
+ *pixelp++ = r;
+ *pixelp++ = g;
+ *pixelp++ = b;
+ if (--(slp->sl_left) <= 0) {
+ /* do_eol */
+ if (fbp != FB_NULL) {
+ size_t npix;
+ bu_semaphore_acquire(BU_SEM_SYSCALL);
+ npix = fb_write(fbp, 0, a_y, (unsigned char *)slp->sl_buf, width);
+ bu_semaphore_release(BU_SEM_SYSCALL);
+ if (npix < width)
+ bu_exit(EXIT_FAILURE, "scanline fb_write error");
+ }
+ bu_free(slp->sl_buf, "sl_buf scanline buffer");
+ slp->sl_buf = (unsigned char *)0;
+ }
+}
+
+/**
+ * Call the material-specific shading function, after making certain
+ * that all shadework fields desired have been provided.
+ *
+ * Returns -
+ * 0 on failure
+ * 1 on success
+ *
+ * But of course, nobody cares what this returns. Everyone calls us
+ * as (void)viewshade()
+ */
+int
+my_viewshade(struct xray *a_ray, double perp, const struct partition *pp, struct hit *sw_hit, point_t *color)
+{
+ fastf_t cosine;
+ point_t matcolor; /* Material color */
+
+ /* Default color is white (uncolored) */
+ VSETALL(matcolor, 1);
+
+ if (sw_hit->hit_dist < 0.0)
+ sw_hit->hit_dist = 0.0; /* Eye inside solid */
+
+ /* If optional inputs are required, have them computed */
+ VJOIN1(sw_hit->hit_point, a_ray->r_pt, sw_hit->hit_dist, a_ray->r_dir);
+
+ /* shade inputs */
+ if (sw_hit->hit_dist < 0.0) {
+ /* Eye inside solid, orthoview */
+ VREVERSE(sw_hit->hit_normal, a_ray->r_dir);
+ } else {
+ fastf_t f;
+ /* Get surface normal for hit point */
+ if (pp->pt_inseg->seg_stp->st_meth->ft_norm) {
+ pp->pt_inseg->seg_stp->st_meth->ft_norm(sw_hit, pp->pt_inseg->seg_stp, a_ray);
+ }
+ if (pp->pt_inflip) {
+ VREVERSE(sw_hit->hit_normal, sw_hit->hit_normal);
+ } else {
+ VMOVE(sw_hit->hit_normal, sw_hit->hit_normal);
+ }
+
+ /* Check to make sure normals are OK */
+ f = VDOT(a_ray->r_dir, sw_hit->hit_normal);
+ if (f > 0.0 && !(((f) < 0) ? ((-f)<=perp) : (f <= perp))) {
+ /* reverse the normal so it's lit */
+ VREVERSE(sw_hit->hit_normal, sw_hit->hit_normal);
+ }
+ }
+
+ /* Invoke the actual shader (diffuse) */
+ /* Diffuse reflectance from "Ambient" light source (at eye) */
+ if ((cosine = -VDOT(sw_hit->hit_normal, a_ray->r_dir)) > 0.0) {
+ if (cosine > 1.00001) {
+ cosine = 1;
+ }
+ cosine *= AmbientIntensity;
+ VSCALE(*color, matcolor, cosine);
+ } else {
+ VSETALL(*color, 0);
+ }
+ return 1;
+}
+
+/**
+ * Manage the coloring of whatever it was we just hit. This can be a
+ * recursive procedure.
+ */
+int
+my_colorview(struct application *ap, struct partition *PartHeadp, point_t *color)
+{
+ struct partition *pp;
+ struct hit *hitp;
+
+ for (pp = PartHeadp->pt_forw; pp != PartHeadp; pp = pp->pt_forw)
+ if (pp->pt_outhit->hit_dist >= 0.0) break;
+
+ if (pp == PartHeadp) {
+ return 0;
+ }
+
+ hitp = pp->pt_inhit;
+ ap->a_uptr = (void *)pp->pt_regionp; /* note which region was shaded */
+
+ /* individual shaders must handle reflection & refraction */
+ (void)my_viewshade(&ap->a_ray, ap->a_rt_i->rti_tol.perp, pp, pp->pt_inhit, color);
+
+ /* XXX This is always negative when eye is inside air solid */
+ ap->a_dist = hitp->hit_dist;
+ return 1;
+}
+
+
+void
+my_pixel(struct resource *resp, int pixelnum)
+{
+ struct application a;
+ vect_t point; /* Ref point on eye or view plane */
+
+ struct seg finished_segs; /* processed by rt_boolweave() */
+ struct partition FinalPart; /* Head of Final Partitions */
+ int a_y, a_x;
+ int a_user;
+ point_t a_color;
+
+ int hit;
+ point_t color;
+
+ /* Obtain fresh copy of global application struct */
+ a = APP; /* struct copy */
+ a.a_magic = RT_AP_MAGIC;
+ a.a_ray.magic = RT_RAY_MAGIC;
+ a.a_resource = resp;
+
+ a_y = (int)(pixelnum/width);
+ a_x = (int)(pixelnum - (a_y * width));
+
+ /* our starting point, used for non-jitter */
+ VJOIN2 (point, viewbase_model, a_x, dx_model, a_y, dy_model);
+
+ /* not tracing the corners of a prism by default */
+ a.a_pixelext=NULL;
+
+ /* LOOP BELOW IS UNROLLED ONE SAMPLE SINCE THAT'S THE COMMON CASE.
+ *
+ * XXX - If you edit the unrolled or non-unrolled section, be sure
+ * to edit the other section.
+ */
+ /* not hypersampling, so just do it */
+
+ VMOVE(a.a_ray.r_pt, point);
+ VMOVE(a.a_ray.r_dir, APP.a_ray.r_dir);
+
+ a.a_level = 0; /* recursion level */
+ a.a_purpose = "main ray";
+
+ BU_LIST_INIT(&finished_segs.l);
+
+ FinalPart.pt_forw = FinalPart.pt_back = &FinalPart;
+ FinalPart.pt_magic = PT_HD_MAGIC;
+ a.a_Final_Part_hdp = &FinalPart;
+ a.a_finished_segs_hdp = &finished_segs;
+
+ hit = my_shootray(resp, &a.a_ray, a.a_rt_i, &a, &FinalPart, &finished_segs);
+
+ if (hit) {
+ /* hit */
+ a_user = 1; /* Signal view_pixel: HIT */
+ a.a_return = my_colorview(&a, &FinalPart, &color);
+ VMOVE(a_color, color);
+ } else {
+ /* miss */
+ a_user = 0; /* Signal view_pixel: MISS */
+ a.a_return = 0;
+ VMOVE(a_color, background); /* In case someone looks */
+ }
+
+ RT_FREE_SEG_LIST(&finished_segs, resp);
+ RT_FREE_PT_LIST(&FinalPart, resp);
+
+ my_view_pixel(a_x, a_y, a_user, a_color);
+ return;
+}
+
+void
+my_run(int cur_pixel, int last_pixel)
+{
+ size_t cpu = 0;
+ int per_processor_chunk = 0; /* how many pixels to do at once */
+
+ int pixelnum;
+ struct resource *resp;
+
+ /*
+ * SERIAL case -- one CPU does all the work.
+ */
+ npsw = 1;
+
+ /* The more CPUs at work, the bigger the bites we take */
+ if (per_processor_chunk <= 0) per_processor_chunk = npsw;
+
+ resp = &resource[cpu];
+ RT_CK_RESOURCE(resp);
+
+ if (resp == RESOURCE_NULL) {
+ resp = &rt_uniresource;
+ if (rt_uniresource.re_magic == 0)
+ rt_init_resource(&rt_uniresource, 0, APP.a_rt_i);
+ }
+
+ bu_semaphore_acquire(RT_SEM_WORKER);
+
+ for (pixelnum = cur_pixel; pixelnum <= last_pixel; pixelnum++) {
+ my_pixel(resp, pixelnum);
+ }
+
+ bu_semaphore_release(RT_SEM_WORKER);
+
+ /* Tally up the statistics */
+ if (resp->re_magic != RESOURCE_MAGIC) {
+ bu_log("ERROR: CPU %d resources corrupted, statistics bad\n", cpu);
+ } else {
+ rt_add_res_stats(APP.a_rt_i, resp);
+ }
+ return;
+}
+
+/**
* Do all the actual work to run a frame.
*
* Returns -1 on error, 0 if OK.
@@ -810,7 +2387,7 @@
* It may prove desirable to do this in chunks
*/
rt_prep_timer();
-
+#if 0
if (incr_mode) {
for (incr_level = 1; incr_level <= incr_nlevel; incr_level++) {
if (incr_level > 1)
@@ -835,6 +2412,15 @@
pix_start = 0;
pix_end = (int)(height*width - 1);
}
+#endif
+ printf("pix_start: %d, pix_end: %d\n", pix_start, pix_end);
+ my_run(pix_start, pix_end);
+
+ /* Reset values to full size, for next frame (if any) */
+ pix_start = 0;
+ pix_end = (int)(height*width - 1);
+ /**/
+
utime = rt_get_timer(×, &wallclock);
/*
------------------------------------------------------------------------------
_______________________________________________
BRL-CAD Developer mailing list
brlcad-devel@lists.sourceforge.net
https://lists.sourceforge.net/lists/listinfo/brlcad-devel
