Booleweave

Boolean weaving of raytracing segments. More...

Collaboration diagram for Booleweave:

Files
file	boolweave.h

Functions
void	rt_boolweave (struct seg *out_hd, struct seg *in_hd, struct partition *PartHeadp, struct application *ap)
	Weave segs into partitions. More...
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)
	Eval booleans over partitions. More...
void	rt_bool_growstack (struct resource *res)

Detailed Description

Boolean weaving of raytracing segments.

Function Documentation

rt_boolweave()

void rt_boolweave	(	struct seg *	out_hd,
		struct seg *	in_hd,
		struct partition *	PartHeadp,
		struct application *	ap
	)

Weave segs into partitions.

Weave a chain of segments into an existing set of partitions. The edge of each partition is an inhit or outhit of some solid (seg).

NOTE: When the final partitions are completed, it is the user's responsibility to honor the inflip and outflip flags. They can not be flipped here because an outflip=1 edge and an inflip=0 edge following it may in fact be the same edge. This could be dealt with by giving the partition struct a COPY of the inhit and outhit rather than a pointer, but that's more cycles than the neatness is worth.

Inputs - Pointer to first segment in seg chain. Pointer to head of circular doubly-linked list of partitions of the original ray.

Outputs - Partitions, queued on doubly-linked list specified.

Notes - It is the responsibility of the CALLER to free the seg chain, as well as the partition list that we return.

rt_boolfinal()

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
	)

Eval booleans over partitions.

Consider each partition on the sorted & woven input partition list. If the partition ends before this box's start, discard it immediately. If the partition begins beyond this box's end, return.

Next, evaluate the boolean expression tree for all regions that have some presence in the partition.

If 0 regions result, continue with next partition.

If 1 region results, a valid hit has occurred, so transfer the partition from the Input list to the Final list.

If 2 or more regions claim the partition, then an overlap exists.

If the overlap handler gives a non-zero return, then the overlapping partition is kept, with the region ID being the first one encountered.

Otherwise, the partition is eliminated from further consideration.

All partitions in the indicated range of the ray are evaluated. All partitions which really exist (booleval is true) are appended to the Final partition list. All partitions on the Final partition list have completely valid entry and exit information, except for the last partition's exit information when a_onehit!=0 and a_onehit is odd.

The flag a_onehit is interpreted as follows:

If a_onehit = 0, then the ray is traced to +infinity, and all hit points in the final partition list are valid.

If a_onehit != 0, the ray is traced through a_onehit hit points. (Recall that each partition has 2 hit points, entry and exit). Thus, if a_onehit is odd, the value of pt_outhit.hit_dist in the last partition may be incorrect; this should not matter because the application specifically said it only wanted pt_inhit there. This is most commonly seen when a_onehit = 1, which is useful for lighting models. Not having to correctly determine the exit point can result in a significant savings of computer time.

If a_onehit is negative, it indicates the number of non-air hits needed.

Returns - 0 If more partitions need to be done 1 Requested number of hits are available in FinalHdp

The caller must free whatever is in both partition chains.

NOTES for code improvements -

With a_onehit != 0, it is difficult to stop at the 'enddist' value (or the a_ray_length value), and always get correct results. Need to take into account some additional factors:

1) A region shouldn't be evaluated until all its solids have been intersected, to prevent the "CERN" problem of out points being wrong because subtracted solids aren't intersected yet.

Maybe "all" solids don't have to be intersected, but some strong statements are needed along these lines.

A region is definitely ready to be evaluated IF all its solids have been intersected.

2) A partition shouldn't be evaluated until all the regions within it are ready to be evaluated.

rt_bool_growstack()

void rt_bool_growstack

(

struct resource *

res

)

Increase the size of re_boolstack to double the previous size. Depend on bu_realloc() to copy the previous data to the new area when the size is increased.

Return the new pointer for what was previously the last element.