Two pictures here. The first is a wire frame showing how the different
vertices each have 2 to 8 triangles including them. The second is a picture
of the smoothed mesh.

 -Shay

Post a reply to this message

Attachments:
Download 'Irregular_Mesh_WF.jpg' (33 KB) Download 'Irregular_Mesh.jpg' (7 KB)

Preview of image 'Irregular_Mesh_WF.jpg'

Preview of image 'Irregular_Mesh.jpg'

Forgot to add. Source is in pbs-f

 -Shay

"Shay" <shi### [at] houstonrrcom> wrote in message
news:3c84365e@news.povray.org...

Post a reply to this message

> Two pictures here. The first is a wire frame showing how the different
> vertices each have 2 to 8 triangles including them. The second is a
picture
> of the smoothed mesh.

Wow, you did it!!  :o)  That's great!  I already had a look at the
sourcecode. It is well-documented and understandable. I like the long names
to variables. Your idea is a much better approch to the many different
states of a square (2 to 8 faces).

Now I'll try to implement it to my code. I create the faces prior to
deciding which case [/] [\] to use, so this shouldn't happen twice. The
output should be mesh2, but I think I'll easily solve these things.. I'll be
back after a closer look..

I have a working code now, it can't go fully wrong!  :o)
*Thanks!*

Hugo

Post a reply to this message

On Tue, 5 Mar 2002 09:02:46 -0800, "Shay" <shi### [at] houstonrrcom> wrote:
> Two pictures here. The first is a wire frame showing how the different
> vertices each have 2 to 8 triangles including them. The second is a picture
> of the smoothed mesh.

I have checked your source and found comment:
        // normalize the sums of the triangle normals
        // for each vertex to get the normal for the vertex
So I assume you use simple averaging of normals.
You can consider weighted averaging - look into my post at
http://news.povray.org/3a30d5ac%40news.povray.org

ABX

Post a reply to this message

Hugo <hua### [at] post3teledk> wrote in message
news:3c84dc24$1@news.povray.org...

> Wow, you did it!!  :o)  That's great!  I already had a look at the
> sourcecode. It is well-documented and understandable. I like the long
names
> to variables. Your idea is a much better approch to the many different
> states of a square (2 to 8 faces).

Sometimes it just takes another set of eyes looking at a problem.

>
> Now I'll try to implement it to my code. I create the faces prior to
> deciding which case [/] [\] to use, so this shouldn't happen twice. The
> output should be mesh2, but I think I'll easily solve these things.. I'll
be
> back after a closer look..
>
> I have a working code now, it can't go fully wrong!  :o)
> *Thanks!*

Glad it helped. As far as converting to #mesh2. The vertices and normals are
already in arrays, so there will not be any problem writing it out as
#mesh2. I used #mesh because it is easier for another person to read.

I'm looking forward to using your final macro. I experimented last night
with dividing all of the squares with one or the other case, and it does
make a very big difference.

 -Shay

Post a reply to this message

!

W³odzimierz ABX Skiba <abx### [at] babilonorg> wrote in message
news:g7n98u4uu4aqisuol998h2j3e3qip2i0or@4ax.com...
> So I assume you use simple averaging of normals.
> You can consider weighted averaging - look into my post at
> http://news.povray.org/3a30d5ac%40news.povray.org

The weighted normals look better. Is this the case with every mesh? This
goes against everything I have seen concerning mesh normals.
By a weighted average, do you mean simply not normalizing the normal of each
triangle?

 -Shay

Post a reply to this message

On Tue, 5 Mar 2002 09:12:47 -0600, "Shay" <sah### [at] simcopartscom> wrote:
> The weighted normals look better. Is this the case with every mesh?

This is just more accurate method of averaging.

> This goes against everything I have seen concerning mesh normals.

Not exactly. Weighting is just longer and result is visible when there are
differences in triangle area.

> By a weighted average, do you mean simply not normalizing the normal of each
> triangle?

Considering you have N triangles with vertex P:
- take all N normals as previously
- normalize them as previously
- new step: multiply/adjust according to area of triangle
- add all N normals as previously
- normalize this sum as previously (I'm not sure it is necessary)

So only new thing is muliplying. This is done to save larger triangles more
float.

ABX

Post a reply to this message

I will implement this next time I get a little PoV time. Thank you.

 -Shay

W³odzimierz ABX Skiba <abx### [at] babilonorg> wrote in message
news:k7o98ugqa229jtfbhpkniat3g83n791lnt@4ax.com...

Post a reply to this message

ABX wrote:
> only new thing is muliplying.
> This is just more accurate method of averaging.

Sounds interesting!

Shay wrote:
> I will implement this next time I get a little PoV time.

Superb!
Today I haven't got so much Pov time either, but tomorrow.

:o)
Regards,
Hugo

Post a reply to this message

Things are a little slow at work, so I wrote a new version. New version uses
a height-field only optimised method for finding the triangle areas, so it
is very fast and finds the weighted normal. New version also creates a
#mesh2 output file. I am very busy now so will post the source in a few
minutes when I have time.

 -Shay

Shay <shi### [at] houstonrrcom> wrote in message
news:3c84365e@news.povray.org...
> Two pictures here. The first is a wire frame showing how the different
> vertices each have 2 to 8 triangles including them. The second is a
picture
> of the smoothed mesh.
>
>  -Shay
>
>
>

Post a reply to this message

There is a big mistake in the new version!!! I am fixing it now.

 -Shay

Post a reply to this message

Allright, corrected my mistake. Corrected source posted to pbs-f. That will
teach me not to PoV at work!

 -Shay
"Shay" <shi### [at] houstonrrcom> wrote in message
news:3c856818@news.povray.org...
>
> There is a big mistake in the new version!!! I am fixing it now.
>
>  -Shay
>
>

Post a reply to this message

Hi Shay,

Thank you once again for the various versions of the mesh-smoothing code!
I'll try to implement it today!

> height-field only optimised method for finding the triangle areas
> ....finds the weighted normal

I'm not sure what this is about. Maybe I can find out by reading your code.
Will I be limited in the way I can bend / move the vertices around?

> That will teach me not to PoV at work!

Hmm you know better than me, but if you had the necessary time and decided
to PoV, I surely don't mind! Your new version was done quicker than it would
otherwise have been.  :o)

Best regards,
Hugo

Post a reply to this message

It is with pleasure I can announce that the normal-smoothing routine in my
macro now works, thanks to Shay!  So far I only implemented the idea from
version 1 ... it was simpler to begin with, so I will add the weighted
normals as soon as possible.

I will also add a few more features and then post some examples of results..
This won't take so long, I think.  :o)

Regards,
Hugo

Post a reply to this message

Hugo <hua### [at] post3teledk> wrote in message
news:3c8626aa$1@news.povray.org...
> It is with pleasure I can announce that the normal-smoothing routine in my
> macro now works

Excellent. Like I said, can't wait to use it.

Regarding the heightfield only method for finding the area of the triangle:

The formula I used was Area = (Side_1_Length * Side_2_Length *
sin(Included_Angle))/2
A 100x100 array of vertices would require finding 39,204 angles!!
With a heightfield, however, the verices are only moved up and down, so the
angle at any corner of a square will always be pi/2 radians. The sin of pi/2
radians is 1, so the sin(Included_Angle) part can be dropped!!

For a mesh with different angles at the corners of a "square," an angle must
be found for each triangle. There are two ways I can think of to do this.
Both are slow, but one should shurely be faster than the other.

The first way is to use PoV's vangle() macro. This macro requires vectors as
inputs, so in addition to finding the lengths of the square sides, you will
also have to find the vectors.

The second and probably faster way is to use your own math. In addition to
the lengths of the sides of the square, you will need to find the lengths of
the [/] and [\] diagonals. You can then find the angle with something like
this:
#declare Included_Angle = acos  ((Side_1_Length^2 + Side_2_Length^2 -
Diagonal^2) / (2 * Side_1_Length * Side_2_Length));
(above is NOT TESTED! And I am using my WORK brain.)

 -Shay

Post a reply to this message

On Wed, 6 Mar 2002 09:11:10 -0600, "Shay" <sah### [at] simcopartscom> wrote:
> For a mesh with different angles at the corners of a "square," an angle must
> be found for each triangle. There are two ways I can think of to do this.
> Both are slow, but one should shurely be faster than the other.

universal formula for area of triangle:

S=sqrt(p*(p-a)*(p-b)*(p-c))

where a,b,c are lengths of edges and p is half of perimeter = (a+b+c)/2

as you see you don't need angle at all

ABX
--
disc{z,-z 5#macro O()asc(substr("-+((1*(,1,/.-,*/(,&.323/'1"e,1))*.1-4#declare
e=e-1;#end#local e=26;pigment{#local g=function(_){ceil(_)-_}function#local//X
k=function{pattern{object{sphere_sweep{linear_spline 13#while(e>0)<O(),O()//AB
>.01#end}}}}{k(g(atan2(x,y)),g(ln((y+x)^2+1e-5)),0)}}finish{ambient 1}}//POV35

Post a reply to this message

On Wed, 06 Mar 2002 16:16:59 +0100, W�odzimierz ABX Skiba <abx### [at] babilonorg>
wrote:
> universal formula for area of triangle:

btw: if you are interested in background theory then
http://mathworld.wolfram.com/HeronsFormula.html

ABX

Post a reply to this message

Thank you again, ABX. It seems that you are always waiting in a dark corner
ready to jump out with a formula the way Ken is with a link.
I never went to college, so most of the math I know is self tought. This
leaves BIG holes in my math knowledge.

The formula you supplied will help a lot, because I will henceforth be
adding a "weighted" switch to all of my vertex normalizing macros.

 -Shay

W³odzimierz ABX Skiba <abx### [at] babilonorg> wrote in message
news:2tcc8uk708tgec598p843g17v5gf6ajjld@4ax.com...

Post a reply to this message

Thanks for the formulas and explanations, but I am not sure how to implement
them.. I like math too (more than I did in school!) but I'm not educated
enough to understand what ABX wrote.. I'd very much like to have the best
smoothing algoritm in my program.. If Shay codes it for personal use, maybe
I will get a copy too and some insight.  :o)  At the moment I'm
concentrating on another part of my macros that needs to be written before
the overall results will look good enough to open your eyes.  ;o)

Regards,
Hugo

Post a reply to this message

Hugo <hua### [at] post3teledk> wrote in message
news:3c864b48$1@news.povray.org...
> Thanks for the formulas and explanations, but I am not sure how to
implement
> them.. I like math too (more than I did in school!) but I'm not educated
> enough to understand what ABX wrote.. I'd very much like to have the best
> smoothing algoritm in my program..

You do. For heightfields, the method I used is as effecient as any. Nothing
can simplify (Base*Height)/2. Writing the formula as a function MIGHT speed
it up, but with only 2 operations per calculations I'm not sure.
The method described by ABX is necessary only for non-square meshes.
 -Shay

Post a reply to this message

On Wed, 6 Mar 2002 18:08:12 +0100, "Hugo" <hua### [at] post3teledk> wrote:
> I'd very much like to have the best
> smoothing algoritm in my program..

Algorithm is very simple:

1. start loop on all triangles and calculate
a) triangle has vertices V1,V2,V3
b) normal=vnormalize(vcross(V2-V1,V3-V1))
c) area=triangle_area(V1.x,V1.y,V1.z,V2.x,V2.y,V2.z,V3.x,V3.y,V3.z)
d) multiply above and store area*normal in temporary array

2. start second loop on all vertices
a) for each vertex find all its triangles: triangle1, triangle2, ... triangleN
b) calculate weighted normal with equation:
Normal=(area1*normal1+area2*normal2+...+areaN*normalN)/N
(note all multiplications was precalculated and stored in array)
c) store new weighted normal for triangle

That's all.

Of course there can be variations and optimizations according to particular
situation but it is how it looks in general

ABX

Post a reply to this message

On Wed, 6 Mar 2002 11:13:31 -0600, "Shay" <sah### [at] simcopartscom> wrote:
> Writing the formula as a function MIGHT speed
> it up, but with only 2 operations per calculations I'm not sure.

Well, you can check my investigation in
http://news.povray.org/f4sa5uomgj1v158rjs159ms75midq7qm52%404ax.com
that function is fastest way of calculations

> The method described by ABX is necessary only for non-square meshes.

I can be wrong becouse I not studied your sources enough but looking at
pictures on http://news.povray.org/3c84365e%40news.povray.org your triangles
are non-square. Only projection onto xz plane (considering y is up) are
square.

ABX

Post a reply to this message

On Wed, 06 Mar 2002 18:14:40 +0100, W�odzimierz ABX Skiba <abx### [at] babilonorg>
wrote:
> c) store new weighted normal for triangle

should be:
c) store new weighted normal for vertex

sorry

ABX

Post a reply to this message

W³odzimierz ABX Skiba <abx### [at] babilonorg> wrote in message
news:opjc8u8qk2a9s20e037adocejo9ccvii6i@4ax.com...
> On Wed, 6 Mar 2002 11:13:31 -0600, "Shay" <sah### [at] simcopartscom> wrote:

> I can be wrong becouse I not studied your sources enough but looking at
> pictures on http://news.povray.org/3c84365e%40news.povray.org your
triangles
> are non-square. Only projection onto xz plane (considering y is up) are
> square.

OH DAMN!!! I really screwed up. I was only thinking about elevating one
vertex in ... (well, not important what I was thinking).
I will implement the method you outlined ASAP. This is really going to slow
the macro down, but as long as you're writing out the results for possibly
hundreds of renders, you may as well get the best results possible.

 -Shay

Post a reply to this message

W³odzimierz ABX Skiba <abx### [at] babilonorg> wrote in message
news:5mdc8ukvplcavtnekp4f0cvtebe8rtlbob@4ax.com...
> #include "functions.inc"
> #local triangle_area_engine=function{(x+y+z)*(y+z-x)*(x+y-z)*(x+z-y)/16}
> #local triangle_area=
>   function(x1,y1,z1,x2,y2,z2,x3,y3,z3)
>     {sqrt(triangle_area_engine(
>         f_r(x2-x1,y2-y1,z2-z1),
>         f_r(x3-x2,y3-y2,z3-z2),
>         f_r(x3-x1,y3-y1,z3-z1)
>     ))};

I've haven't used any functions yet, so I would like to know if my version
of your function will work..
I see a slight problem with your function in that the lengths of most of the
triangle sides will be calculated twice.
The demonstration file I wrote finds all of the side lengths first and
stores them in an array. A #local statement at the beginning  of each "case"
macro could find the length of the diagonal. So, would this give an accurate
result?

 #include "functions.inc"
 #local triangle_area_engine=function{(x+y+z)*(y+z-x)*(x+y-z)*(x+z-y)/16}
 #local Triangle_Area =  triangle_area_engine(Side_1_Length, Side_2_Length,
Side_3_Length);

Seems right to me, but I might be missing something.

Thank you,
 -Shay

Post a reply to this message

Well, the results *look* correct. I implemented the formula you suggested,
and the parse is still pretty quick. I tested a 100x100 mesh on my P2 650 at
work with lots of memory-hogging programs running on it, and the parse was
still under a minute.

I cancelled the version from pbs-f that I posted from work and will cancel
the others when I get home, but I might run several tests, or at least get
confirmation from ABX that my function is correct, before I post this new
version.

 -Shay

Shay <sah### [at] simcopartscom> wrote in message news:3c866379@news.povray.org...
> The demonstration file I wrote finds all of the side lengths first and
> stores them in an array. A #local statement at the beginning  of each
"case"
> macro could find the length of the diagonal. So, would this give an
accurate
> result?
>
>  #include "functions.inc"
>  #local triangle_area_engine=function{(x+y+z)*(y+z-x)*(x+y-z)*(x+z-y)/16}
>  #local Triangle_Area =  triangle_area_engine(Side_1_Length,
Side_2_Length,
> Side_3_Length);
>
> Seems right to me, but I might be missing something.
>
> Thank you,
>  -Shay

Post a reply to this message

Very good. Let me just add that I'm going to turn the heightfield data
around lathes and let them follow the path of splines. I don't know if this
is going to break the non-square type of mesh. It's still a grid. But these
turns will, of course, happen before normal calculations.

> This is really going to slow the macro down
I can always have both methods, and let the user decide which one to use.
:o)

Regards,
Hugo

Post a reply to this message

W³odzimierz ABX Skiba wrote:
> universal formula for area of triangle:
> 
> S=sqrt(p*(p-a)*(p-b)*(p-c))
> 
> where a,b,c are lengths of edges and p is half of perimeter = (a+b+c)/2
> 

Is that faster than using half the cross product of two of the sides? 
(cosidering vcross is internal...)

Something like:
area = vlength(vcross(P1-P2,P3-P2))/2;

-josh

Post a reply to this message

Hugo <hua### [at] post3teledk> wrote in message news:3c867a5b@news.povray.org...
> Very good. Let me just add that I'm going to turn the heightfield data
> around lathes and let them follow the path of splines. I don't know if
this
> is going to break the non-square type of mesh. It's still a grid. But
these
> turns will, of course, happen before normal calculations.

It's not as slow as I thought it might be, and nothing will break this new
algorithm. As long as the vertices can be put into an n-by-n array, the
algorithm will work.

 -Shay

Post a reply to this message

Don't think so. sqrt needs more cpu cycles. But maybe I'm wrong!

--
Apache
http://geitenkaas.dns2go.com/experiments/
apa### [at] yahoocom

Post a reply to this message

Apache <apa### [at] yahoocom> wrote in message
news:3c868ca3$1@news.povray.org...
> Don't think so. sqrt needs more cpu cycles. But maybe I'm wrong!

PoV's going to use square root anyway to find those lengths.
 -Shay

Post a reply to this message

>>> universal formula for area of triangle:
>>> S=sqrt(p*(p-a)*(p-b)*(p-c))

>> Is that faster than using half the cross product of two of the sides?
>> Something like:
>> area = vlength(vcross(P1-P2,P3-P2))/2;

> Don't think so. sqrt needs more cpu cycles. But maybe I'm wrong!

Vlength uses sqrt internally. But the major slowdown is Povrays interpreter
and not the cpu.

Regards
Hugo

Post a reply to this message

Josh Seagoe wrote:
> 
> W³odzimierz ABX Skiba wrote:
> > universal formula for area of triangle:
> >
> > S=sqrt(p*(p-a)*(p-b)*(p-c))
> >
> > where a,b,c are lengths of edges and p is half of perimeter = (a+b+c)/2
> >
> 
> Is that faster than using half the cross product of two of the sides?
> (cosidering vcross is internal...)
> 
> Something like:
> area = vlength(vcross(P1-P2,P3-P2))/2;

I have not looked at their mesh code yet,
but I assume that they are calculating
the normal vectors for the triangles by
just taking the cross product of a pair
of each triangle's "edge vectors".

And if this is the case, then I don't see
the point in first calculating this cross
product, normalize it and then multiply
it by your area expression.

I.e.:

vnormalize(vcross(P1 - P2, P3 - P2))
*vlength(vcross(P1 - P2, P3 - P2))/2

They could just use the cross product
directly:

vcross(P1 - P2, P3 - P2)/2

And they don't even have to divide it
by 2 prior to the summing. Because
every triangle normal will be "double"
length.

The final normalizing of the sum of
all the "weighted" normal vectors will
eliminate it anyway.


Tor Olav

Post a reply to this message

"W³odzimierz ABX Skiba" wrote:
> 
> On Tue, 5 Mar 2002 09:12:47 -0600, "Shay" <sah### [at] simcopartscom> wrote:
> > The weighted normals look better. Is this the case with every mesh?
> 
> This is just more accurate method of averaging.
> 
> > This goes against everything I have seen concerning mesh normals.
> 
> Not exactly. Weighting is just longer and result is visible when there are
> differences in triangle area.
> 
> > By a weighted average, do you mean simply not normalizing the normal of each
> > triangle?
> 
> Considering you have N triangles with vertex P:
> - take all N normals as previously
> - normalize them as previously
> - new step: multiply/adjust according to area of triangle
> - add all N normals as previously
> - normalize this sum as previously (I'm not sure it is necessary)
> 
> So only new thing is muliplying. This is done to save larger triangles more
> float.

Wlodek,
if the triangle normals are calculated
with cross products, then step 2 and 3
above are not necessary.

Also see my reply in this thread to Josh
Seagoe some minutes ago:

http://news.povray.org/%3C3C86A730.785EA5C1%40hotmail.com%3E
news://news.povray.org/3C86A730.785EA5C1%40hotmail.com


Tor Olav

Post a reply to this message

On Thu, 07 Mar 2002 00:56:33 +0100, Tor Olav Kristensen
<tor### [at] hotmailcom> wrote:
> Wlodek,
> if the triangle normals are calculated
> with cross products, then step 2 and 3
> above are not necessary.

I feeled this...

ABX

Post a reply to this message

On Wed, 6 Mar 2002 12:45:09 -0600, "Shay" <sah### [at] simcopartscom> wrote:
> > #local triangle_area_engine=function{(x+y+z)*(y+z-x)*(x+y-z)*(x+z-y)/16}
> > #local triangle_area=
> >   function(x1,y1,z1,x2,y2,z2,x3,y3,z3)
> >     {sqrt(triangle_area_engine(
> >         f_r(x2-x1,y2-y1,z2-z1),
> >         f_r(x3-x2,y3-y2,z3-z2),
> >         f_r(x3-x1,y3-y1,z3-z1)
> >     ))};
>
> #include "functions.inc"
> #local triangle_area_engine=function{(x+y+z)*(y+z-x)*(x+y-z)*(x+z-y)/16}
> #local Triangle_Area =  triangle_area_engine(Side_1_Length, Side_2_Length,
Side_3_Length);
>
> Seems right to me, but I might be missing something.

You forgot about sqrt applied but since others mentioned that not normalized
cross product is sufficient then I think my method is wasting of pov-time ;-)

ABX

Post a reply to this message