POV-Ray : Newsgroups : povray.programming : [RFC] Little isosurface patch ? Server Time
9 Oct 2026 02:47:14 EDT (-0400)
  [RFC] Little isosurface patch ? (Message 1 to 28 of 28)  
From: Wolfgang Wieser
Subject: [RFC] Little isosurface patch ?
Date: 26 Feb 2004 17:52:35
Message: <403e78b2@news.povray.org>
I am not completely sure about what I am talking here but at least 
what I propose in the following lines removed black spots on the isosurface 
of my Mars renderings. (These spots only occur when the light comes under 
a flat angle and when no_shadow is NOT set.)

In isosurf.cpp, the recursive part of the root finder reads: 

---------------------------------------
static int IsoSurface_Function_Find_Root_R(ISOSURFACE* ISOSRF, ISO_Pair*
EP1, 
        ISO_Pair* EP2, DBL dt, DBL t21, DBL len, bool in_shadow_test)
{
        DBL temp;

        temp = fabs((EP2->f - EP1->f) * len);
        if(ISOSRF->gradient < temp)  // update "max gradient found"
                ISOSRF->gradient = temp;

        if((ISOSRF->eval == true) && [...]
                [...]

        if(t21 < ISOSRF->accuracy)
        {
        #if ORIGINAL
                if(EP2->f < 0)
                {
                        ISOSRF->tl = EP2->t;
                        return true;
                }
                else return false;
        #else /* !ORIGINAL /
                if(EP2->f <= 0 && EP1->f >= 0.0)
                {
                        ISOSRF->tl = 0.5*(EP2->t+EP1->t);
                        return true;
                }
                else if(EP2->f < 0)  // This will normally not be reached (ww). 
                {
                        ISOSRF->tl = EP2->t;
                        return true;
                }
                else return false;
        #endif
        }
        [...]
---------------------------------------

The idea is that in case we cross the isosurface threshold and 
one point is outside (EP1) while the other one is inside (EP2), 
then the average of the two depth values should give a better 
estimate for the actual intersection than merely using EP2. 

(This works because the root solver continuously halfes the interval 
the root is in.)

The "else if" stmt is the original code which is probably not reached 
normally because in case both points are inside the isosurface, we 
should not be here. 

At least that is what I think from reading the code because unfortunately 
it completely lacks descriptive comments. 

Maybe somebody with a clue could comment on that. 

Wolfgang


Post a reply to this message

From: Thorsten Froehlich
Subject: Re: [RFC] Little isosurface patch ?
Date: 26 Feb 2004 20:55:33
Message: <403ea395$1@news.povray.org>
Why not just

    if(EP2->f < 0)
    {
         if(EP1->f > 0.0)
             ISOSRF->tl = 0.5*(EP2->t+EP1->t);
         else
             ISOSRF->tl = EP2->t;
         return true;
    }
    else return false;

???

    Thorsten


PS: You should really consider using a sane tab width with something like
four spaces per tab, and not unreadable eight spaces per tab!

____________________________________________________
Thorsten Froehlich, Duisburg, Germany
e-mail: tho### [at] trfde

Visit POV-Ray on the web: http://mac.povray.org


Post a reply to this message

From: Wolfgang Wieser
Subject: Re: [RFC] Little isosurface patch ?
Date: 27 Feb 2004 04:53:50
Message: <403f13ad@news.povray.org>
Thorsten Froehlich wrote:

> Why not just
> 
>     if(EP2->f < 0)
>     {
>          if(EP1->f > 0.0)
>              ISOSRF->tl = 0.5*(EP2->t+EP1->t);
>          else
>              ISOSRF->tl = EP2->t;
>          return true;
>     }
>     else return false;
> 
> ???
> 
>     Thorsten
> 
> 
> PS: You should really consider using a sane tab width with something like
> four spaces per tab, and not unreadable eight spaces per tab!
> 
I AM using a tab with of 4 but when I copy-and-paste into the 
news reader the tabs get expanded to 8. I actually thought, the 
news reader would transmit the \t characters but it looks like it 
is converting them to 8 spaces before sending. 
But no problem, I'll do better the next time. 

BTW, after posting, I wondered myself why I was using 0.5*(EP2->t+EP1->t), 
i.e. the average. We could even do a linear interpolation which should be 
much better: We know the f and the t values!

Since you (Thorsten) are the guy who ported the Suzuki code to povray: 
What do you think?

Wolfgang


Post a reply to this message

From: Nicolas Calimet
Subject: Re: [RFC] Little isosurface patch ?
Date: 27 Feb 2004 08:20:58
Message: <403f443a$1@news.povray.org>
> PS: You should really consider using a sane tab width with something like
> four spaces per tab, and not unreadable eight spaces per tab!

	IMO you should never use tabs when writing some code, as they
make it very unreadable for most people (who usually don't bother setting
the tab width -- if ever possible).  I'd say tabs can be used safely IF
your editor converts them automatically to a small amount of spaces
(ideally 2 -- my personal choice -- to 4).

	- NC


Post a reply to this message

From: Wolfgang Wieser
Subject: Re: [RFC] Little isosurface patch ?
Date: 27 Feb 2004 09:20:21
Message: <403f5224@news.povray.org>
Wolfgang Wieser wrote:

> Thorsten Froehlich wrote:
> 
>> Why not just
>> 
>>     if(EP2->f < 0)
>>     {
>>          if(EP1->f > 0.0)
>>              ISOSRF->tl = 0.5*(EP2->t+EP1->t);
>>          else
>>              ISOSRF->tl = EP2->t;
>>          return true;
>>     }
>>     else return false;
>> 
> [...]
> i.e. the average. We could even do a linear interpolation which should be
> much better: We know the f and the t values!
> 
I now suggest the following: This does a linar interpolation and I verified 
using my current mars rendering that it removes even more (_all_!) 
spurious black dots. 

---------------------------------------
if(EP2->f<=0.0)
{
    if(EP1->f >= 0.0)
    {
        double df = EP1->f-EP2->f;
        // Need to calc (EP1->t*EP2->f - EP2->t*EP1->f) / df
        // in a numerically stable way. 
        if(df>1e-14)
            ISOSRF->tl = EP2->t + t21*EP2->f/df;
        else
            ISOSRF->tl = 0.5*(EP2->t+EP1->t);
    }
    else
        ISOSRF->tl = EP2->t;
    return true;
}
return false;
---------------------------------------

The 1e-14 is just there to prevent a division by zero in 
case the isosurface has zero gradient (along the ray) at the 
intersection. Maybe we can even use smaller values. 

Wolfgang


Post a reply to this message

From: Thorsten Froehlich
Subject: Re: [RFC] Little isosurface patch ?
Date: 27 Feb 2004 09:30:02
Message: <403f546a$1@news.povray.org>
In article <403f443a$1@news.povray.org> , Nicolas Calimet 
<pov### [at] freefr>  wrote:

>> PS: You should really consider using a sane tab width with something like
>> four spaces per tab, and not unreadable eight spaces per tab!
>
>  IMO you should never use tabs when writing some code, as they
> make it very unreadable for most people (who usually don't bother setting
> the tab width -- if ever possible).  I'd say tabs can be used safely IF
> your editor converts them automatically to a small amount of spaces
> (ideally 2 -- my personal choice -- to 4).

Urgh, no, this is the 21st century!  Old junk DOS and ancient Unix editors
that do not support tabs properly should deleted, not used!  There is
progress, and spaces only cause problems when writing code, while tabs make
everything evry easy and fast to write and change.  One simply has to agree
on one tab size for shared code.  Of course, on a particular kind of
platform(s) this seems to be impossible.  Yet, on those platform(s)
everybody still writes C K&R style, so... ;-)

Actually, on Windows the practical standard is the one default of M$
Developer Studio (4 iirc) and on Mac OS the universal standard is 4 as well.
So if the myriad editors on that other "platform" cannot agree on a common
format, who cares? ;-)

    Thorsten

____________________________________________________
Thorsten Froehlich, Duisburg, Germany
e-mail: tho### [at] trfde

Visit POV-Ray on the web: http://mac.povray.org


Post a reply to this message

From: Thorsten Froehlich
Subject: Re: [RFC] Little isosurface patch ?
Date: 27 Feb 2004 09:35:26
Message: <403f55ae$1@news.povray.org>
In article <403f5224@news.povray.org> , Wolfgang Wieser <wwi### [at] gmxde>  
wrote:

> The 1e-14 is just there to prevent a division by zero in
> case the isosurface has zero gradient (along the ray) at the
> intersection. Maybe we can even use smaller values.

You really don't want an unnecessary division is such heavily used code.
Doesn't "len" provide you with all you need?

    Thorsten

____________________________________________________
Thorsten Froehlich, Duisburg, Germany
e-mail: tho### [at] trfde

Visit POV-Ray on the web: http://mac.povray.org


Post a reply to this message

From: Thorsten Froehlich
Subject: Re: [RFC] Little isosurface patch ?
Date: 27 Feb 2004 09:35:49
Message: <403f55c5$1@news.povray.org>
In article <403f13ad@news.povray.org> , Wolfgang Wieser <wwi### [at] gmxde>  
wrote:

> Since you (Thorsten) are the guy who ported the Suzuki code to povray:
> What do you think?

I haven't looked at that code for over a year...

    Thorsten

____________________________________________________
Thorsten Froehlich, Duisburg, Germany
e-mail: tho### [at] trfde

Visit POV-Ray on the web: http://mac.povray.org


Post a reply to this message

From: Christoph Hormann
Subject: Re: [RFC] Little isosurface patch ?
Date: 27 Feb 2004 09:58:03
Message: <cd24h1-ibf.ln1@triton.imagico.de>
Wolfgang Wieser wrote:
> I am not completely sure about what I am talking here but at least 
> what I propose in the following lines removed black spots on the isosurface 
> of my Mars renderings. (These spots only occur when the light comes under 
> a flat angle and when no_shadow is NOT set.)
> 
> [...]

What you describe seems to be specific to shadow rays, does your 
suggested change also influence the appearance of the actual surface 
(i.e. camera rays). You could try rendering with a fairly large accuracy 
value for testing.

I agree with Thorsten that the interpolation will probably cause 
slowdown without much advantage (and i don't think the simple version 
you posted will work correctly in all situations).  Also note we are 
talking about differences of a maximum of accuracy*0.5.

Christoph

-- 
POV-Ray tutorials, include files, Sim-POV,
HCR-Edit and more: http://www.tu-bs.de/~y0013390/
Last updated 11 Jan. 2004 _____./\/^>_*_<^\/\.______


Post a reply to this message

From: Wolfgang Wieser
Subject: Re: [RFC] Little isosurface patch ?
Date: 27 Feb 2004 09:58:19
Message: <403f5b09@news.povray.org>
Nicolas Calimet wrote:

>> PS: You should really consider using a sane tab width with something like
>> four spaces per tab, and not unreadable eight spaces per tab!
> 
> IMO you should never use tabs when writing some code, as they
> make it very unreadable for most people (who usually don't bother setting
> the tab width -- if ever possible).  I'd say tabs can be used safely IF
> your editor converts them automatically to a small amount of spaces
> (ideally 2 -- my personal choice -- to 4).
> 
I completely disagree. You _should_ always use tabs for indention because 
it saves a lot of bytes on your hd and because anybody can adjust the 
indention depth on his own editor to fit his needs. 

I, for example, am used to tab width 4 and I don't like code written 
with space-2 indention (too small indention). 

I once read that this indention issue was actually the reason for tabs 
being invented. 

One could argue that today disk space is cheap but see the following 
example: 
Linux-2.6.3 kernel code would be 24 Mb (!!) larger if people used 
4 spaces instead of one tab. That is nearly 15% more just for eye candy. 
And that would enlarge the .tgz archive by 770 kb (37.9 -> 38.7 Mb) which 
would take me 3 minutes longer for the download (my 56k modem has 
4.4k/sec average). 

The proper way to do intention is to use tabs. 

Wolfgang


Post a reply to this message

From: Wolfgang Wieser
Subject: Re: [RFC] Little isosurface patch ?
Date: 27 Feb 2004 10:04:02
Message: <403f5c62@news.povray.org>
Thorsten Froehlich wrote:
 
> well. So if the myriad editors on that other "platform" cannot agree on a
> common format, who cares? ;-)
> 
And which other platform are you talking about?

Even "good old" unix VI (and ViM, too, of course) can set the tab size: 
 :set tabstop=4
 :set shiftwidth=4

Wolfgang


Post a reply to this message

From: Nicolas Calimet
Subject: Re: [RFC] Little isosurface patch ?
Date: 27 Feb 2004 10:28:01
Message: <403f6201$1@news.povray.org>
> I completely disagree. You _should_ always use tabs for indention because 
> it saves a lot of bytes on your hd and because anybody can adjust the 
> indention depth on his own editor to fit his needs.

	I understand these arguments.

> I once read that this indention issue was actually the reason for tabs 
> being invented.

	I don't think so  :-)
	Tabs were invented for "tabulation", meaning aligning text columns
whatever the length (provided short enough) of their content.
	As a matter of fact it can also be used for indentation.

> And that would enlarge the .tgz archive by 770 kb (37.9 -> 38.7 Mb) which 
> would take me 3 minutes longer for the download (my 56k modem has 
> 4.4k/sec average). 

	Well, that's 3 minutes over 2 hours and half... a raw 2% more.
	(you'd better get some DSL model  ;-) )

	Okay, I knew I should not answer Thorsten's notice about tabs,
but what I mean is that you don't always use an editor to look through
the files in a package.  Personally I don't know how to make 'more' or
'less' change the tab width.  Maybe I'll learn something today.
	Anyway this is also a never-ending fight about how a source
code should or should not look like.  I choose to use two spaces instead
of a tab (and those will both compress very well anyway) and to break
long lines before the 80th caracter.  Therefore I can look at my code
even on a non-X term.

	Now, go on with your own style -- that doesn't matter much as
long as the program compiles and works as intended !

	- NC


Post a reply to this message

From: Thorsten Froehlich
Subject: Re: [RFC] Little isosurface patch ?
Date: 27 Feb 2004 10:52:34
Message: <403f67c2$1@news.povray.org>
In article <403f5c62@news.povray.org> , Wolfgang Wieser <wwi### [at] gmxde>  
wrote:

>> well. So if the myriad editors on that other "platform" cannot agree on a
>> common format, who cares? ;-)
>
> And which other platform are you talking about?
>
> Even "good old" unix VI (and ViM, too, of course) can set the tab size:
>  :set tabstop=4
>  :set shiftwidth=4

Yes, there are vi, then there are the vi clones and improvements.  Then
there is this editor that is its own operating system (you know which one I
am talking about), there are improved versions of it.  Then there is my
favorite pico, and then there is the myriad editors I did not mention.  I am
sure there are plenty that have hard-coded tabs.  In conclusion, for
compatibility (the holly cow) many argue to use spaces.  And I agree with
you that I don't see why spaces offer anything.

Anyway, as was already said in this thread, that doesn't matter much as
long as the program compiles and works as indented. ;-)

    Thorsten

____________________________________________________
Thorsten Froehlich, Duisburg, Germany
e-mail: tho### [at] trfde

Visit POV-Ray on the web: http://mac.povray.org


Post a reply to this message

From: Nicolas Calimet
Subject: Re: [RFC] Little isosurface patch ?
Date: 27 Feb 2004 11:05:24
Message: <403f6ac4@news.povray.org>
> and works as indented. ;-)

	:-D

	- NC


Post a reply to this message

From: Wolfgang Wieser
Subject: Re: [RFC] Little isosurface patch ?
Date: 27 Feb 2004 11:12:14
Message: <403f6c5d@news.povray.org>
Christoph Hormann wrote:

> Wolfgang Wieser wrote:
>> I am not completely sure about what I am talking here but at least
>> what I propose in the following lines removed black spots on the
>> isosurface of my Mars renderings. (These spots only occur when the light
>> comes under a flat angle and when no_shadow is NOT set.)
>> 
>> [...]
> 
> What you describe seems to be specific to shadow rays, does your
> suggested change also influence the appearance of the actual surface
> (i.e. camera rays). You could try rendering with a fairly large accuracy
> value for testing.
> 
Well, in iso code there is no difference between viewing and shadow rays. 
The in_shadow_test flag is never actually used except for some cache 
which is handeled at a higher level and should not matter here. 

What I describe seems to be specific to rays which come in a _very_ 
flat angle over the surface. And for these Mars renderings, the 
shadow rays come really flat on the shadow side of hills. 

> I agree with Thorsten that the interpolation will probably cause
> slowdown without much advantage 
>
I am not sure about that. Because the gain in accuracy is considerably. 
The original code will track the ray until its position is known to 
be within "surface +/- accuracy". But with the modification I propose, 
we gain significantly in accuracy because we can linarly interpolate the 
"exact" location of the surface. 

> (and i don't think the simple version 
> you posted will work correctly in all situations).  
>
You don't _think_ ...
Okay, I am not completely sure, too. 
Actually, 
--------------------------
    if(EP2->f<=0.0)
    {
            double df = EP1->f-EP2->f;
            // Need to calc (EP1->t*EP2->f - EP2->t*EP1->f) / df
            // in a numerically stable way. 
            ISOSRF->tl = (df>1e-14) ? 
            EP2->t + t21*EP2->f/df : 
            0.5*(EP2->t+EP1->t);
        return true;
    }
    return false;
--------------------------
should work as well (and does for my scenes). All the other conditions 
are just to work around conditions which I am not sure about. 

> Also note we are 
> talking about differences of a maximum of accuracy*0.5.
> 
So what?

Please see the following web page for a comparison: 
http://www.cip.physik.uni-muenchen.de/~wwieser/tmp/poviso.html

Wolfgang


Post a reply to this message

From: Wolfgang Wieser
Subject: Re: [RFC] Little isosurface patch ?
Date: 27 Feb 2004 11:22:52
Message: <403f6edb@news.povray.org>
Nicolas Calimet wrote:

> Well, that's 3 minutes over 2 hours and half... a raw 2% more.
> (you'd better get some DSL model  ;-) )
> 
I get the other one for free :) So I won't change. 

> the files in a package.  Personally I don't know how to make 'more' or
> 'less' change the tab width.  
>
Use 
  less -x4 file
Or better, use
  export LESS="-x4"
(in bash style) in your profile. (I am using LESS="-M -i -S -x4" or so.) 

> Maybe I'll learn something today. 
>
:)

> Anyway this is also a never-ending fight about how a source
> code should or should not look like.  I choose to use two spaces instead
> of a tab (and those will both compress very well anyway) 
>
I am using one tab per level and have tab size 4 as you already know. 

> and to break long lines before the 80th caracter. 
>
Me too. Because it is dangerous if one cannot see what gets clipped away 
on the right and uneasy to navigate when the lines are folded. 

> Now, go on with your own style -- that doesn't matter much as
> long as the program compiles and works as intended !
> 
Be careful. Code at www.ioccc.org also "works as intended" but 
I never want to read such code :p

Wolfgang


Post a reply to this message

From: Nicolas Calimet
Subject: Re: [RFC] Little isosurface patch ?
Date: 27 Feb 2004 11:30:53
Message: <403f70bd$1@news.povray.org>
> Use 
>   less -x4 file
> Or better, use
>   export LESS="-x4"
> (in bash style) in your profile. (I am using LESS="-M -i -S -x4" or so.) 

	Geeeee I already knew for a long time (but never did it) that I'd
better switch from 'more' to 'less'.  This tab stuff, among several others,
is a good reason for.
	<mode switch on>

>>Maybe I'll learn something today. 
> :)

	Cool, I didn't loose my day then.
	Was worth answering Thorsten afterall...  ;-)

	- NC


Post a reply to this message

From: Wolfgang Wieser
Subject: Re: [RFC] Little isosurface patch ?
Date: 27 Feb 2004 12:16:19
Message: <403f7b62@news.povray.org>
For those who did not read my last reply till the end: 

Here is a comparison: 
http://www.cip.physik.uni-muenchen.de/~wwieser/tmp/poviso.html

Sorry, I just notized that I mistyped the time (now corrected). 
It is: 
  Original code: 47.77 sec
  Patched code: 47.89 sec
  Difference: 0.25%
Hence, it can be neglected. 

The reason is that this computation is only done one for each intersection 
and thus not in the innermost loop. 

Wolfgang


Post a reply to this message

From: Christoph Hormann
Subject: Re: [RFC] Little isosurface patch ?
Date: 27 Feb 2004 12:18:03
Message: <fj84h1-qt2.ln1@triton.imagico.de>
Wolfgang Wieser wrote:
>>
>>What you describe seems to be specific to shadow rays, does your
>>suggested change also influence the appearance of the actual surface
>>(i.e. camera rays). You could try rendering with a fairly large accuracy
>>value for testing.
>>
> 
> Well, in iso code there is no difference between viewing and shadow rays. 
> The in_shadow_test flag is never actually used except for some cache 
> which is handeled at a higher level and should not matter here. 

So what?

My question was if your change makes a difference to the appearance of 
an isosurface despite possible effects on shadow ray tests.  This is 
best to test with high detail surface features of a size similar to the 
accuracy value.

>>I agree with Thorsten that the interpolation will probably cause
>>slowdown without much advantage 
>>
> 
> I am not sure about that. Because the gain in accuracy is considerably.

Note this is not a real gain in accuracy - it would be if the function 
value changed linearly between the two points but obviously it does not 
in most cases.  A comparitive test with raising accuracy and using your 
technique vs. current technique with low accuracy value would be necessary.

>[...]
> should work as well (and does for my scenes). All the other conditions 
> are just to work around conditions which I am not sure about. 

You should at least test with the most common special situations (use in 
CSG, view of the isosurface from inside, high gradient functions etc.).

Christoph

-- 
POV-Ray tutorials, include files, Sim-POV,
HCR-Edit and more: http://www.tu-bs.de/~y0013390/
Last updated 11 Jan. 2004 _____./\/^>_*_<^\/\.______


Post a reply to this message

From: Christoph Hormann
Subject: Re: [RFC] Little isosurface patch ?
Date: 27 Feb 2004 12:18:04
Message: <js74h1-ft2.ln1@triton.imagico.de>
Thorsten Froehlich wrote:
> 
> Yes, there are vi, then there are the vi clones and improvements.  Then
> there is this editor that is its own operating system (you know which one I
> am talking about), there are improved versions of it.  

Actually in *this* editor it is quite possible to customize the settings 
to a large extent, in most cases you just need to set:

tab-width
indent-tabs-mode

according to what you need.

(Not to mention that you can of course quickly re-indent a whole file if 
someone else has messed it up)

Christoph

-- 
POV-Ray tutorials, include files, Sim-POV,
HCR-Edit and more: http://www.tu-bs.de/~y0013390/
Last updated 11 Jan. 2004 _____./\/^>_*_<^\/\.______


Post a reply to this message

From: Wolfgang Wieser
Subject: Re: [RFC] Little isosurface patch ?
Date: 27 Feb 2004 13:27:40
Message: <403f8c1b@news.povray.org>
Christoph Hormann wrote:

> My question was if your change makes a difference to the appearance of
> an isosurface despite possible effects on shadow ray tests.  This is
> best to test with high detail surface features of a size similar to the
> accuracy value.
> 
I don't know. But since you are the isosurface expert around here, 
it would be nice if you could have a look at it and run some tests. 

>>>I agree with Thorsten that the interpolation will probably cause
>>>slowdown without much advantage
>>>
>> I am not sure about that. Because the gain in accuracy is considerably.
> 
> Note this is not a real gain in accuracy - it would be if the function
> value changed linearly between the two points but obviously it does not
> in most cases.  A comparitive test with raising accuracy and using your
> technique vs. current technique with low accuracy value would be
> necessary.
> 
It _is_ generally a real gain as long as 
- you use steady functions, i.e. functions with finite gradient which is 
  what you always do and 
- the function does not change very much in scale of accuracy. 

So it is a gain for nearly all real-life scenes. And for such things 
like high micro-details on the surface, it should at least not do 
worse. 

>>[...]
>> should work as well (and does for my scenes). All the other conditions
>> are just to work around conditions which I am not sure about.
> 
> You should at least test with the most common special situations (use in
> CSG, view of the isosurface from inside, high gradient functions etc.).
> 
Could you please?

Wolfgang


Post a reply to this message

From: Christopher James Huff
Subject: Re: [RFC] Little isosurface patch ?
Date: 27 Feb 2004 13:54:50
Message: <cjameshuff-E1E139.13554127022004@news.povray.org>
In article <403e78b2@news.povray.org>, Wolfgang Wieser <wwi### [at] gmxde> 
wrote:

> The idea is that in case we cross the isosurface threshold and 
> one point is outside (EP1) while the other one is inside (EP2), 
> then the average of the two depth values should give a better 
> estimate for the actual intersection than merely using EP2. 

Linear interpolation is a pretty common last step in the bisection 
algorithm...I did it for the blob2 object, I wasn't aware the isosurface 
object didn't do it.

This is also close to the regula falsi or false secant method. The idea 
with this method is that when you have a pair of points that bracket a 
root, approximate the function as linear within that interval and use 
the computed root as the new splitting point. It is similar to Newton's 
method, but doesn't require a derivative of the function. It converges 
faster than bisection in most cases, but is only guaranteed to converge 
if you start out with a bracketed root. I've considered using a variant 
of this as a second stage to the isosurface root solver...use bisection 
to locate the roots to within a certain crude precision, and then use 
regula falsi to refine the roots.

-- 
Christopher James Huff <cja### [at] earthlinknet>
http://home.earthlink.net/~cjameshuff/
POV-Ray TAG: <chr### [at] tagpovrayorg>
http://tag.povray.org/


Post a reply to this message

From: Christoph Hormann
Subject: Re: [RFC] Little isosurface patch ?
Date: 27 Feb 2004 14:14:05
Message: <cfh4h1-cjn.ln1@triton.imagico.de>
Christopher James Huff wrote:
> 
> This is also close to the regula falsi or false secant method. The idea 
> with this method is that when you have a pair of points that bracket a 
> root, approximate the function as linear within that interval and use 
> the computed root as the new splitting point. It is similar to Newton's 
> method, but doesn't require a derivative of the function. It converges 
> faster than bisection in most cases, but is only guaranteed to converge 
> if you start out with a bracketed root. I've considered using a variant 
> of this as a second stage to the isosurface root solver...use bisection 
> to locate the roots to within a certain crude precision, and then use 
> regula falsi to refine the roots.

I am quite sure you will miss some intersections this way (cases where 
the function is negative only in a very small interval along the ray and 
is positive otherwise for example).

Christoph

-- 
POV-Ray tutorials, include files, Sim-POV,
HCR-Edit and more: http://www.tu-bs.de/~y0013390/
Last updated 11 Jan. 2004 _____./\/^>_*_<^\/\.______


Post a reply to this message

From: Christopher James Huff
Subject: Re: [RFC] Little isosurface patch ?
Date: 27 Feb 2004 16:12:13
Message: <cjameshuff-37EED9.16130427022004@news.povray.org>
In article <cfh### [at] tritonimagicode>,
 Christoph Hormann <chr### [at] gmxde> wrote:

> I am quite sure you will miss some intersections this way (cases where 
> the function is negative only in a very small interval along the ray and 
> is positive otherwise for example).

You also miss roots with the bisection method. This is just one of the 
things you have to deal with when finding roots numerically.

However, if the function is monotonic on the interval you start with, 
either entirely increasing or entirely decreasing, there is only one 
root possible and this method will only tighten the interval closer to 
the root. If you break the function up into small enough intervals, for 
example with the variant of the bisection method the current solver 
uses, losing roots is rarely a problem. Neither method will find roots 
where the function just touches 0 without crossing it, though.

-- 
Christopher James Huff <cja### [at] earthlinknet>
http://home.earthlink.net/~cjameshuff/
POV-Ray TAG: <chr### [at] tagpovrayorg>
http://tag.povray.org/


Post a reply to this message

From: Wolfgang Wieser
Subject: Re: [RFC] Little isosurface patch ?
Date: 28 Feb 2004 12:02:51
Message: <4040c9bb@news.povray.org>
Christopher James Huff wrote:

> In article <403e78b2@news.povray.org>, Wolfgang Wieser <wwi### [at] gmxde>
> wrote:
> 
>> The idea is that in case we cross the isosurface threshold and
>> one point is outside (EP1) while the other one is inside (EP2),
>> then the average of the two depth values should give a better
>> estimate for the actual intersection than merely using EP2.
> 
> Linear interpolation is a pretty common last step in the bisection
> algorithm...I did it for the blob2 object, I wasn't aware the isosurface
> object didn't do it.
> 
To see the actual accuracy improvement achieved by my patch, I 
finally made some comparative renderings with different accuracy 
settings using a "Water on Mars" test scene. 

Details here: 
http://www.cip.physik.uni-muenchen.de/~wwieser/tmp/poviso.html#accuracy

Wolfgang


Post a reply to this message

From: Nicolas Calimet
Subject: Re: [RFC] Little isosurface patch ?
Date: 1 Mar 2004 06:51:05
Message: <404323a9$1@news.povray.org>
Sorry for buggin' again, but the following two sentences
seem to contradict each other, don't they ?

 > You _should_ always use tabs for indention because
 > [...] anybody can adjust the
 > indention depth on his own editor to fit his needs.

>> [me] and to break long lines before the 80th caracter.
> Me too. Because it is dangerous if one cannot see what gets clipped away 
> on the right and uneasy to navigate when the lines are folded.

	That is: how can you always guaranty the line-break to occur before
the (on-screen) 80th caracter using variable-length-customized tabs ?

	- NC


Post a reply to this message

From: Thorsten Froehlich
Subject: Re: [RFC] Little isosurface patch ?
Date: 1 Mar 2004 13:05:06
Message: <40437b52$1@news.povray.org>
In article <404323a9$1@news.povray.org> , Nicolas Calimet 
<pov### [at] freefr>  wrote:

>  > You _should_ always use tabs for indention because
>  > [...] anybody can adjust the
>  > indention depth on his own editor to fit his needs.
>
>>> [me] and to break long lines before the 80th caracter.
>> Me too. Because it is dangerous if one cannot see what gets clipped away
>> on the right and uneasy to navigate when the lines are folded.
>
>  That is: how can you always guaranty the line-break to occur before
> the (on-screen) 80th caracter using variable-length-customized tabs ?

If you still use 80 character per line terminals to edit text, you have
worse problems than tabs! ;-)

    Thorsten

____________________________________________________
Thorsten Froehlich, Duisburg, Germany
e-mail: tho### [at] trfde

Visit POV-Ray on the web: http://mac.povray.org


Post a reply to this message

From: Wolfgang Wieser
Subject: Re: [RFC] Little isosurface patch ?
Date: 1 Mar 2004 15:09:04
Message: <40439856@news.povray.org>
Thorsten Froehlich wrote:
> In article <404323a9$1@news.povray.org> , Nicolas Calimet
> <pov### [at] freefr>  wrote:
> 
>>  That is: how can you always guaranty the line-break to occur before
>> the (on-screen) 80th caracter using variable-length-customized tabs ?
> 
Easy. 
I am using tabwidth 4, so it is sufficient to make sure that lines 
do not get cut off on the right when using tabwith 4. 

> If you still use 80 character per line terminals to edit text, you have
> worse problems than tabs! ;-)
> 
If you hadn't used the smiley I'd probably say that sometimes it is 
of great advantage to _think_ prior to posting. :)

Because even if I can zoom my editor to width >=160, I prefer to 
be able to have 2 to 4 windows non-overlapping on the same screen. 
And because I do not want lines to get cut off at the right (too 
dangerous to overlook something), I need to use some horiz. limit. 
(Because I do not like folded lines.)

But I'd prefer not to discuss indention and window sizes but isosurface 
accuracy instead. Did anybody with some more isosurface experience 
and aproptiate test scenes on the hd have a run?
Even if, from my presence on this news server, I deduced the rule of 
thumb that "no response is good response". 

Wolfgang


Post a reply to this message

Copyright 2003-2023 Persistence of Vision Raytracer Pty. Ltd.