POV-Ray obviously knows "where" two objects intersect.

Is there a way to get that information?
I worked out - mathematically - the points where 2 circles intersect.
But doing 2 ellipses is apparently WAY tougher.

The end goal is to get information to use in positioning things or to pass along
to trace().
So, for example, if I wanted to define two circles, how would I know at what
point or two that they intersect at, without doing all the math?

It seems to me that without already knowing what exact point to have trace look
at, you'd have to do a heck of a lot of "scanning" to narrow down the point of
interest.

But then again, there may be an easy was that I'm just overlooking.

Post a reply to this message

Bald Eagle <cre### [at] netscapenet> wrote:
> POV-Ray obviously knows "where" two objects intersect.

Actually, it doesn't. Not really.

What POV-Ray does is that it tests the ray against one object and then
the other, and if the ray hits both, it just looks which hit point is
closer.

In other words, POV-Ray knows which surface is closer (for that particular
ray), but doesn't really know where exactly the two surfaces interset.
That information is not really needed for raytracing.

-- 
                                                          - Warp

Post a reply to this message

Am 17.08.2013 01:54, schrieb Bald Eagle:
> POV-Ray obviously knows "where" two objects intersect.

No, it doesn't.

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.

(Note that this is exactly what the trace() and inside() functions do.)

This is the way POV-Ray does all its CSG operations.

Post a reply to this message

> 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...

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.  Similarly, the mathematically infinite
number of points between the inside and outside starting points gets bumped up
to another order of infinity when I'd then work around the axis of the
intersecting circles.
Clearly, I could do 2 or 3 tests, and then some more math to get an idea of the
plane where the circle of intersection lies, but that breaks down when using
other shaped primitives intersecting at angles, which aren't intersecting, which
are coincident, etc.

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.

I mean, it seems like it should be a trivial task to place a disk, or align a
plane, or draw a skinny torus around exactly where two spheres intersect in a
scene.  But I must admit that I'm lost as to a fast and efficient means of doing
this.  Expand that problem to "drawing an outline" around the intersection of
any given arbitrary CSG primitives, and it seems like a tough nut to crack all
by my lonesome.
Granted there may be a clever way to implement incidental results of colors or
textures or normals to _visualize_ those points, but the user is still left with
no usable information about those points from which to build upon.

Thanks for your time and patience.

Post a reply to this message

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

> 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).

Would I be wrong to then think that if:
Instance A = POV-Ray calculating where a ray hits Sphere 1, and
Instance B = POV-Ray calculating where a ray hits Sphere 2,
then there ought to be a way
to add / subtract / solve a simultaneous equation for both instances to find out
where they coincide?

I mean without knowing the details of the guts of the POV-Ray source code, I'm
just working by analogy, and looking at the output of the render engine.
At the intersection, there ought to be some ... detectable change.  Like the
minima and maxima of a curve, or an inflection point, or a discontinuity, or the
myriad of other computable equation properties.

> If the primitive is a member of a CSG intersection ... 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.

This does nothing to dissuade me from thinking there has to be a way to
capitalize on how POV-Ray finds and checks all those points.


> 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.

Well, yes.  I was also thinking about doing some other sort of thing like the
"squeeze" theorem, where I look for a limit.


You and I can SEE where the intersection of 2 spheres is.  It's a bloody obvious
and sudden change from one convex surface to another.  It just seems that if
height_field has water_level, then the "low" point between the two spheres ought
to be detectable.  Maybe something about the sudden change of slope or normal to
the surface or ... something.

BTW, 2 ellipses was just an example.  Apparently it's a wicked hairy problem to
solve, and things like matrices and numerical methods were suggested to find the
intersection.

Post a reply to this message

> I mean without knowing the details of the guts of the POV-Ray source code, I'm
> just working by analogy, and looking at the output of the render engine.
> At the intersection, there ought to be some ... detectable change.

If you modified POV-ray to return some kind of object id for each
ray that is hit you could notice that neighboring pixels hit different
objects. You can emulate the same thing with trace().

However, if the object changes for two neighboring rays it can either
be an intersection, two objects that are "touching" or one object that
is in front of another object (the latter case can be mostly filtered
by checking how close the two ray "hit points" are in 3d space).

You could also direct more trace() calls at regions of interest
to find the intersection point with higher precision and possibly
attempt to actually "follow" a line of intersection.

But this technique limits detection of intersections to those that
are "visible" from some outside point. And all you get is a bunch of
points where intersections might occur.

Post a reply to this message

Christian Froeschlin <chr### [at] chrfrde> wrote:
> However, if the object changes for two neighboring rays it can either
> be an intersection, two objects that are "touching" or one object that
> is in front of another object (the latter case can be mostly filtered
> by checking how close the two ray "hit points" are in 3d space).

POV-Ray knows if a ray is inside an object at a certain point (or at
least can resolve it.) Therefore if a ray intersects two objects, it
can determine of one of the intersection points is inside the other
object.

Using two adjacent rays to try to determine the intersection line between
two surfaces still sounds a bit error-prone. If the first ray intersects
both objects, one being inside the other, and the other ray intersects
only one of the objects, which conclusion should be made from that?

-- 
                                                          - Warp

Post a reply to this message

> If the first ray intersects
> both objects, one being inside the other, and the other ray intersects
> only one of the objects, which conclusion should be made from that?

Well, in any event, that would be a start.
Naturally, as you say, there would be SOME error, say, in "corners" 
where 2 objects touch or intersect and there is adjacent empty space or 
a more distant surface of one of the objects - but that would likely 
only lead to a few extra pixels in the thickness of the drawn outline at 
that point.

 From the perspective of pixels, "close enough is good enough".  At 
least for the proof of concept.

I also remember seeing somewhere that there was a "POV Outline" or 
somesuch thing that someone wrote on the web...  does anyone have any 
experience with that?

Let's say you had 3 objects - you could shoot a Trace() ray in order to 
see what it hits.  Do so for all 3 objects, and compare the results - of 
the same ray trajectory.

If one object is in front of the other, then it will get hit with the 
trace, if not, it will pass right through.
In the actual rendered scene, if one object is INSIDE the other, then 
the outer object gets hit.

So a positive result from both trace and the scene, would say that there 
is an edge.

It occurs to me (to answer a question that I posed earlier) that the 
smallest resolution one would need to test is based on the displayed 
pixels in the final render.  Divide up the rendered scene into pixels, 
do the same for "POV units", and define the step of any loop to 
increment the number of Pixel-equivalent POV-units.

Post a reply to this message

>  From the perspective of pixels, "close enough is good enough".  At
> least for the proof of concept.
>
> I also remember seeing somewhere that there was a "POV Outline" or
> somesuch thing that someone wrote on the web...  does anyone have any
> experience with that?

If you only want a rough approximation of the intersection, why not use 
the "intersection" keyword?

Example of the locus of intersection between two hollow spheres:

#declare HollowSphere = difference{sphere{0,1}sphere{0,0.99}}

intersection
{
  object{ HollowSphere }
  object{ HollowSphere translate x*.3}
  pigment{ color rgb .1 }
}

You could then use trace with that object to find the surface if you 
want to place other objects on it.

Post a reply to this message