Am 17.08.2013 19:00, schrieb Bald Eagle:
>
>> It can only (1) find individual points on the surface of any single
>> primitive, and then (2) check whether any such individual point is
>> inside a given set of other primitives.
>
> Indeed, but given those 2 facts, it seems that there should be some function or
> method for implementing them to determine where the intersection points are.
> -x is inside, and +x is outside, so somewhere in between is the intersection
> point.  I suppose I could asymptotically approach from either end with a loop
> and the trace and inside functions, but since it seems that POV-Ray is _already
> doing this when it parses/renders a scene...

POV-Ray does not use any iterative approaches for finding surfaces (*). 
Instead, it uses a bunch of straightforward formulae to compute the 
intersection points between a line (light ray) and any of the geometric 
primitives it supports. That's all it does in (1).

If the primitive is a member of a CSG intersection (or difference, which 
is internally represented as an intersection with some of the objects 
inverted) POV-Ray then uses another bunch of straightforward formulae to 
check whether the points it has found are inside all the other 
primitives participating in the CSG intersection; any point that isn't 
must be part of a surface section that was intersected away. (POV-Ray 
also uses a similar mechanism to suppress internal surfaces in CSG merge 
objects.) That's all POV-Ray does in (2).


(*) There is one exception: Intersections between a light ray and an 
Isosurface are evaluated using some iterative approach to find a point 
<x,y,z> along the ray such that f(x,y,z) = 0. You /might/ have a chance 
to use this for solving your ellipsis intersection problem, but you're 
on your own there.


> In the case of the loop, what is the minimum recommended dx of the increment?
> I'd rather not divide the distance between 2 points and test 10,000
> subdivisions, if 1000 would do the job.

One simple approach to greatly reduce the number of points to test would 
be binary subdivision: Presuming A is inside and B is outside, test a 
point C exactly halfway between; if C is inside, let A'=C, otherwise let 
B'=C. Repeat until you're ok with the precision.

If you have a formula that gives different values depending on how close 
you are to the point you're searching for, you can use this property to 
speed up the test by selecting C not halfway between A and B, but closer 
to A if |f(A)| > B|f(B)|, or closer to B otherwise.


> I guess I was just thinking that given the results of intersection, merge,
> difference, bounding boxes, minextent and maxextent, that it's reinventing the
> wheel and doing an awful lot of extra work to redo what POV-Ray already seems to
> do in order to properly render the scene.

As far as bounding boxes are concerned (and also min_extent and 
max_extent, which in fact give the bounding box dimensions), POV-Ray 
uses a rather simple approach: The bounding box of a CSG intersection is 
simply the intersection of the bounding boxes of all participating objects.

Post a reply to this message