What Mick said... I'm dying to know if it was some little oversight, or some
bigger problem causing the buggy meshes.

Post a reply to this message

"Tony[B]" wrote:
> 
> What Mick said... I'm dying to know if it was some little oversight, or some
> bigger problem causing the buggy meshes.

Ok, Take a deep breath now and everybody try to relax.

Here come the reason for the bug of the moving sphere... 

I would say it's a design assumption which turns out to be wrong, sometimes:
The Inside test and the trace test may disagree; 
They should not, but they do in some occurences.

The decision to add a triangle is determined by the value of Inside
at each vertex of the Tetrahedron. 
The triangle vertices are determined by the trace test between an outside/inside pair
of vertices. 
Alas, the code assumes that if one vertex is outside, and the other one is inside,
then Intersection() will always gives a valid result. 

If you really want to have fun (NOT), Try YOffs=3.5 in the sphere scene.
(Expect a Segmentation Fault, at render time, at least on my system!).


I successfully removed that bug by testing the Intersection() return 
in CalcIntersection().
I had to choose a "good" answer when Intersect failed. I choose the middle
of the segment, but there is maybe a better values ?

Here some code, for those that want to try it: 

        if (Intersection(&tess_intersect, info->Object, &tess_Ray))
        {
        Assign_Vector(info->Intersection[outs][ins][0], tess_intersect.IPoint);
        if(Smooth)
            Normal(info->Intersection[outs][ins][1],
                   tess_intersect.Object, &tess_intersect);
       }
       else
       { /* Cheating */
       Assign_Vector(info->Intersection[outs][ins][0], info->Coord[ins]);
       VScaleEq(Dir,-1/2);
       VAddEq(info->Intersection[outs][ins][0],Dir);
         if (Smooth)
           {
              VNormalizeEq(Dir);
              Assign_Vector(info->Intersection[outs][ins][1],Dir);
           }
       
       }

If you do not believe me, the demonstration of the bug is left as an exercice
to the reader.

Last point, Because good news always comes with bad news, my test with the torus
gives strange results... Still another bug, but maybe not at the same place.
Other objects seems to have survived the tesselation.

Post a reply to this message

> 
> [...]
> 
> I would say it's a design assumption which turns out to be wrong, sometimes:
> The Inside test and the trace test may disagree;
> They should not, but they do in some occurences.
> 

Is it allowed to ask, *why* there is no intersection if one point is
outside and the other inside?

Anyway, nice it works, now looking forward to the release.

Christoph

-- 
Christoph Hormann <chr### [at] gmxde>
IsoWood include, radiosity tutorial, TransSkin and other 
things on: http://www.schunter.etc.tu-bs.de/~chris/

Post a reply to this message

On Fri, 5 Oct 2001 17:45:10 +0100, "Mick Hazelgrove"
<mic### [at] mhazelgrovefsnetcouk> wrote:

>I look forward to seeing this patch working and integrated into the next
>incarnation of megapov based on the 3.5 code as I belive it to be
>potentially one of the most useful additions to Pov. So good luck, fingers
>crossed.

Ditto. With proper tessellation, I might start working on a doodle
I've been delaying for way too long now.


Peter Popov ICQ : 15002700
Personal e-mail : pet### [at] vipbg
TAG      e-mail : pet### [at] tagpovrayorg

Post a reply to this message

Christoph Hormann wrote:
> 

> >
> > [...]
> >
> > I would say it's a design assumption which turns out to be wrong, sometimes:
> > The Inside test and the trace test may disagree;
> > They should not, but they do in some occurences.
> >
> 
> Is it allowed to ask, *why* there is no intersection if one point is
> outside and the other inside?
> 

All questions are allowed... Even "How many angels can dance on the head of a pin ?"
Getting the correct answer might be harder.

The code for inside and trace is always different (by design).
I guess that different algorithms can give different results.
(Just look at the sturm solver option for example)...

Post a reply to this message

>All questions are allowed... Even "How many angels can dance on the head of a pin ?"
>Getting the correct answer might be harder.
>
>The code for inside and trace is always different (by design).
>I guess that different algorithms can give different results.
>(Just look at the sturm solver option for example)...

My guess would be that you're running afoul of the provisions in all of the
intersection code that throw out intersections that are too close to the
start of the ray.

-- 
#macro R(L P)sphere{L F}cylinder{L P F}#end#macro P(V)merge{R(z+a z)R(-z a-z)R(a
-z-z-z a+z)torus{1F clipped_by{plane{a 0}}}translate V}#end#macro Z(a F T)merge{
P(z+a)P(z-a)R(-z-z-x a)pigment{rgbf 1}hollow interior{media{emission 3-T}}}#end 
Z(-x-x.2x)camera{location z*-10rotate x*90normal{bumps.02scale.05}}

Post a reply to this message

Ron Parker wrote:
> 

> >All questions are allowed... Even "How many angels can dance on the head of a pin
?"
> >Getting the correct answer might be harder.
> >
> >The code for inside and trace is always different (by design).
> >I guess that different algorithms can give different results.
> >(Just look at the sturm solver option for example)...
> 
> My guess would be that you're running afoul of the provisions in all of the
> intersection code that throw out intersections that are too close to the
> start of the ray.

Maybe, Maybe not. That aspect was already taken care of in the initial patch by
making the start point of the ray a little more on the outside that it would
have
been needed to if only the segment to test was really done.

There is two things in my posting of a solution:

 1. Where the bug manifest itself, and why.
 2. How to correct that.

Point 2 is probably open to wide discussion (and holy war). 
    As Warp is the author of the patch, he is the one to choose.

Point 1 is hard-fact, and now that it has been found, it is easy to
demonstrate (just put a dirty "printf" before the Intersection() call,
 and another in the "then" part of the "if" that is testing the return value
of Intersection; If the assumption of design was correct, you should get
the same number of first printf than of the second; Alas, take any bogus scene
and you will see that there is more of the first!(*)
As provided, the intersection should have been tested.

My correction was to "Add the test and an else behaviour", because it
was simpler to implement and easier to prove.
Another possible may have been "Fix the parameters of Intersection so
that the problem never occurs again", which seems to me to be harder
to implement and probably impossible to prove.
A third solution was also "Fix the insideness structure on the fly so
that no tesselation of that tetrahedron will occurs", which seems a good idea
if one wants to have some goto in the code. Moreover, it may have opened a
tricky flickering case in which we would be in an infinite loop.


(*): If you do not like printf, you can simply have a ++/-- on a counter.
By the end of the tesselation, it should have been as it was before.
It will not with a bogus scene. So, you may even have a detection of the bogus
scene and have the tesselation failed at parse time, if you want.
I find that approach a little too much hostile, because the user has probably
no way to make the scene works correctly, other than playing randomly with
the tesselation parameters...

Post a reply to this message

:     As Warp is the author of the patch, he is the one to choose.

  I have an idea. It will probably make the tesselating slower, but if it
works, it works.

  As you say, the problem is probably in the insideness test, which can
differ slightly from what the intersection test does. Thus, we should just
get rid of the insideness test completely. (Of course as the main purpose of
the insideness test is speed, we will lose this seedup, but it seems that it's
out of question.)

  So we should do it solely with the intersection calculation. But how?
  As we know, POV-Ray doesn't start the intersection calculation from the
starting point of the ray but moves a small amount forward before actually
shooting the ray (this is necessary for many things, such as reflection,
refraction etc. where the starting point of the ray is exactly on the surface
of an object).
  I don't like the idea of moving the starting point back a bit before making
the intersection test because it can give a wrong result (it can intersect
the surface even though the tetrahedron is not intersecting it).

  However, I have another idea: Move the starting point back a considerable
amount (not a huge step, but more than just a tiny fraction; something like
0.1 units or whatever) and then get *ALL* the intersections of the ray and
the object. After this look if any of these intersection points is between
the real start and end points. If there is any, take it.
  Of course there could be more than one point between the start and end
points, but that's an accuracy thing. We take just one of them (it doesn't
really matter which).
  The advantage of this is that you don't miss points by accident (because
of the inside vs. intersection problem) and you get an accurate result (only
points which are truely at the edges of the tetrahedron are taken, not points
outside it).

  Yes, this is slow, I know. But if it works, it works...

  I have to test this when I got the time...

-- 
#macro N(D,I)#if(I<6)cylinder{M()#local D[I]=div(D[I],104);M().5,2pigment{
rgb M()}}N(D,(D[I]>99?I:I+1))#end#end#macro M()<mod(D[I],13)-6,mod(div(D[I
],13),8)-3,10>#end blob{N(array[6]{11117333955,
7382340,3358,3900569407,970,4254934330},0)}//                     - Warp -

Post a reply to this message

Warp wrote:
> 
>   As you say, the problem is probably in the insideness test, which can
> differ slightly from what the intersection test does. Thus, we should just
> get rid of the insideness test completely. (Of course as the main purpose of
> the insideness test is speed, we will lose this seedup, but it seems that it's
> out of question.)
> 
> [...]

I'm not sure, but this could slow down things enormously, especially for
isosurfaces.

It would be nice to have another method and implement both to compare.

Christoph

-- 
Christoph Hormann <chr### [at] gmxde>
IsoWood include, radiosity tutorial, TransSkin and other 
things on: http://www.schunter.etc.tu-bs.de/~chris/

Post a reply to this message

Christoph Hormann <chr### [at] gmxde> wrote:
: I'm not sure, but this could slow down things enormously, especially for
: isosurfaces.

  Note that shadow calculations also calculate all intersections. And it
isn't that slow, is it?

-- 
#macro N(D,I)#if(I<6)cylinder{M()#local D[I]=div(D[I],104);M().5,2pigment{
rgb M()}}N(D,(D[I]>99?I:I+1))#end#end#macro M()<mod(D[I],13)-6,mod(div(D[I
],13),8)-3,10>#end blob{N(array[6]{11117333955,
7382340,3358,3900569407,970,4254934330},0)}//                     - Warp -

Post a reply to this message