POV-Ray : Newsgroups : povray.advanced-users : Density filling option for polygon Server Time
28 Mar 2024 04:46:53 EDT (-0400)
  Density filling option for polygon (Message 1 to 10 of 19)  
Goto Latest 10 Messages Next 9 Messages >>>
From: Hedrondude
Subject: Density filling option for polygon
Date: 2 Jun 2018 23:25:00
Message: <web.5b135f5ec27af4a4478b32bb0@news.povray.org>
I'm using POV-Ray to render cross sections of four and five dimensional uniform
polytopes - especially star polytopes.  These renders can be seen on my website
http://www.polyope.htm/hedrondude/polychora.htm  I use the polygon keyword quite
a bit, but it only renders with the binary filling (all odd density regions gets
filled in, even density are left as holes) which forces me to manually fill in
all the non-0 even density regions.  This isn't too bad for simple polytopes,
but with more complex ones, this gets very tedious.  Is it possible to render
polygons with density filling (all non-0 density regions gets filled in - i.e.
filled in by the 'winding method') or better yet could this be a feature for
POV-Ray 3.8 where there is a density filling option for the polygon keyword.  I
would suggest something like this:

#local obj=polygon {45,v1,v2,v3,......,v44,v1 density}


Post a reply to this message

From: Le Forgeron
Subject: Re: Density filling option for polygon
Date: 3 Jun 2018 03:35:11
Message: <5b139a2f$1@news.povray.org>
Le 03/06/2018 à 05:24, Hedrondude a écrit :
> I'm using POV-Ray to render cross sections of four and five dimensional uniform
> polytopes - especially star polytopes.  These renders can be seen on my website
> http://www.polyope.htm/hedrondude/polychora.htm  I use the polygon keyword quite
> a bit, but it only renders with the binary filling (all odd density regions gets
> filled in, even density are left as holes) which forces me to manually fill in
> all the non-0 even density regions.  This isn't too bad for simple polytopes,
> but with more complex ones, this gets very tedious.  Is it possible to render
> polygons with density filling (all non-0 density regions gets filled in - i.e.
> filled in by the 'winding method') or better yet could this be a feature for
> POV-Ray 3.8 where there is a density filling option for the polygon keyword.  I
> would suggest something like this:
> 
> #local obj=polygon {45,v1,v2,v3,......,v44,v1 density}
> 
> 

Fixing the url: http://www.polytope.net/hedrondude/polychora.htm

You seems to already have some works on filling

(http://www.polytope.net/hedrondude/glossary.htm , Filling method)


Post a reply to this message

From: clipka
Subject: Re: Density filling option for polygon
Date: 3 Jun 2018 05:28:01
Message: <5b13b4a1$1@news.povray.org>
Am 03.06.2018 um 05:24 schrieb Hedrondude:
> I'm using POV-Ray to render cross sections of four and five dimensional uniform
> polytopes - especially star polytopes.  These renders can be seen on my website
> http://www.polyope.htm/hedrondude/polychora.htm  I use the polygon keyword quite
> a bit, but it only renders with the binary filling (all odd density regions gets
> filled in, even density are left as holes) which forces me to manually fill in
> all the non-0 even density regions.  This isn't too bad for simple polytopes,
> but with more complex ones, this gets very tedious.  Is it possible to render
> polygons with density filling (all non-0 density regions gets filled in - i.e.
> filled in by the 'winding method') or better yet could this be a feature for
> POV-Ray 3.8 where there is a density filling option for the polygon keyword.  I
> would suggest something like this:
> 
> #local obj=polygon {45,v1,v2,v3,......,v44,v1 density}

I'm not sure I understand how Density Filling is defined; I had a look
at http://www.polytope.net/hedrondude/fillings.png, but the technical
terms "density" and "orientable" used in there are greek to me. (Also,
it certainly doesn't help that it is depicted as giving results
indentical to Natural Filling).

At the end of the day, we'll need an algorithm to implement, so ideally,
can you describe how one would test whether a given point (Xp,Yp) is to
be coloured black or white, based on the list of points (X1,Y1),
(X2,Y2), ... (Xn,Yn)?

The closer that algorithm is to our current Binary Filling method, the
easier it would be to implement.

The current algorithm implementing Binary Filling takes each edge
(Xa,Ya)->(Xb,Yb), tests whether it intersects the ray
(Xp,Yp)->(+inf,Yp), and keeps track of whether the number of
intersecting edges is odd or even.

For example, this algorithm would be easy to adapt to Solid Filling, by
just keeping track of whether the number of intersecting edges is non-zero.


I have a hunch that a similar algorithm to implement Density Filling
would take each edge (Xa,Ya)->(Xb,Yb), test whether it intersects the
ray (Xp,Yp)->(+inf,Yp), and if so, test whether Ya>Yb -- and then do
/something/ with the result; compute the difference between the Ya>Yb
and Ya<Yb intersections, maybe? Or keep tabs on the distances of the
intersections, and colour the point depending on whether Ya>Yb?

I'd like to point out that such an algorithm may break down "near"
regions where a portion of the polygon is "flipped over" (if you know
what I mean; but I suspect that's what is meant by "non-orientable", so
you probably already know that).


Note that an algorithm along the lines of, "examine all edges
immediately adjacent to the region the point is in", would require
drastic changes to the polygon code, as the current implementation has
no concept of "regions": All it knows about are the coordinates and
ordering of the original defining vertices.


Post a reply to this message

From: clipka
Subject: Re: Density filling option for polygon
Date: 3 Jun 2018 05:52:30
Message: <5b13ba5e$1@news.povray.org>
Am 03.06.2018 um 11:27 schrieb clipka:

> The current algorithm implementing Binary Filling takes each edge
> (Xa,Ya)->(Xb,Yb), tests whether it intersects the ray
> (Xp,Yp)->(+inf,Yp), and keeps track of whether the number of
> intersecting edges is odd or even.
> 
> For example, this algorithm would be easy to adapt to Solid Filling, by
> just keeping track of whether the number of intersecting edges is non-zero.

Ha, that's of course nonsense, as it would leave everything "left" of
the polygon filled. Solid filling is far more difficult to implement
than binary filling, and I guess it can't be done without first
analyzing the topology of the polygon boundary.


Post a reply to this message

From: Hedrondude
Subject: Re: Density filling option for polygon
Date: 3 Jun 2018 22:30:01
Message: <web.5b14a3df4a5570bb478b32bb0@news.povray.org>
clipka <ano### [at] anonymousorg> wrote:
> Am 03.06.2018 um 05:24 schrieb Hedrondude:
> > I'm using POV-Ray to render cross sections of four and five dimensional uniform
> > polytopes - especially star polytopes.  These renders can be seen on my website
> > http://www.polyope.htm/hedrondude/polychora.htm  I use the polygon keyword quite
> > a bit, but it only renders with the binary filling (all odd density regions gets
> > filled in, even density are left as holes) which forces me to manually fill in
> > all the non-0 even density regions.  This isn't too bad for simple polytopes,
> > but with more complex ones, this gets very tedious.  Is it possible to render
> > polygons with density filling (all non-0 density regions gets filled in - i.e.
> > filled in by the 'winding method') or better yet could this be a feature for
> > POV-Ray 3.8 where there is a density filling option for the polygon keyword.  I
> > would suggest something like this:
> >
> > #local obj=polygon {45,v1,v2,v3,......,v44,v1 density}
>
> I'm not sure I understand how Density Filling is defined; I had a look
> at http://www.polytope.net/hedrondude/fillings.png, but the technical
> terms "density" and "orientable" used in there are greek to me. (Also,
> it certainly doesn't help that it is depicted as giving results
> indentical to Natural Filling).
>
> At the end of the day, we'll need an algorithm to implement, so ideally,
> can you describe how one would test whether a given point (Xp,Yp) is to
> be coloured black or white, based on the list of points (X1,Y1),
> (X2,Y2), ... (Xn,Yn)?
>
> The closer that algorithm is to our current Binary Filling method, the
> easier it would be to implement.
>
> The current algorithm implementing Binary Filling takes each edge
> (Xa,Ya)->(Xb,Yb), tests whether it intersects the ray
> (Xp,Yp)->(+inf,Yp), and keeps track of whether the number of
> intersecting edges is odd or even.
>
> For example, this algorithm would be easy to adapt to Solid Filling, by
> just keeping track of whether the number of intersecting edges is non-zero.
>
>
> I have a hunch that a similar algorithm to implement Density Filling
> would take each edge (Xa,Ya)->(Xb,Yb), test whether it intersects the
> ray (Xp,Yp)->(+inf,Yp), and if so, test whether Ya>Yb -- and then do
> /something/ with the result; compute the difference between the Ya>Yb
> and Ya<Yb intersections, maybe? Or keep tabs on the distances of the
> intersections, and colour the point depending on whether Ya>Yb?


Thanks for the replies everyone.

For density filling, take each edge (Xa,Ya)->(Xb,Yb) and it's direction (if
heading downwards (clockwise) then direction=+1, if heading upwards (counter
clockwise) then direction=-1) and test if it intersects the ray
(Xp,Yp)->(+inf,Yp) - add up all of the direction values to get the density of
the region.  That should do it.

Another cool feature would be to color polygons according to density or to leave
some densities unfilled.


Post a reply to this message

From: clipka
Subject: Re: Density filling option for polygon
Date: 4 Jun 2018 10:08:54
Message: <5b1547f6@news.povray.org>
Am 04.06.2018 um 04:29 schrieb Hedrondude:

> Another cool feature would be to color polygons according to density or to leave
> some densities unfilled.

I don't think the former would be possible /per se/ with reasonable
effort. The latter would probably be quite easy to implement (and could
then be used to emulate the former, by using copies of the polygon with
different colours and different density ranges), but we'd need to find a
neat syntax for such a feature.


Post a reply to this message

From: Le Forgeron
Subject: Re: Density filling option for polygon
Date: 4 Jun 2018 11:30:01
Message: <5b155af9$1@news.povray.org>
Le 04/06/2018 à 04:29, Hedrondude a écrit :

> Thanks for the replies everyone.
> 
> For density filling, take each edge (Xa,Ya)->(Xb,Yb) and it's direction (if
> heading downwards (clockwise) then direction=+1, if heading upwards (counter
> clockwise) then direction=-1) and test if it intersects the ray
> (Xp,Yp)->(+inf,Yp) - add up all of the direction values to get the density of
> the region.  That should do it.
> 
> Another cool feature would be to color polygons according to density or to leave
> some densities unfilled.
> 

After thought, I'm afraid there is a big problem: in Povray, polygon
(and actually triangle too) are not oriented. This is basically the root
of the non-handness commitment.

As long as "density" would need an orientation to work correctly, it
would be not-compatible with the parsing of polygon using 3D vectors.

On the other hand, the polygon of Povray allows the removal of inner
parts, something usual polygons do not allow without tricking (such as
zero-width links between outside perimeter and inner holes).

polygon { Number, V1, V2, ... Vk, V1,
H1, H2, ... Hm, H1 }

Vx being outside perimeter
Hx being inside hole perimeter (and holes can be repeated)


Post a reply to this message

From: clipka
Subject: Re: Density filling option for polygon
Date: 4 Jun 2018 12:27:33
Message: <5b156875@news.povray.org>
Am 04.06.2018 um 17:30 schrieb Le_Forgeron:
> Le 04/06/2018 à 04:29, Hedrondude a écrit :
> 
>> Thanks for the replies everyone.
>>
>> For density filling, take each edge (Xa,Ya)->(Xb,Yb) and it's direction (if
>> heading downwards (clockwise) then direction=+1, if heading upwards (counter
>> clockwise) then direction=-1) and test if it intersects the ray
>> (Xp,Yp)->(+inf,Yp) - add up all of the direction values to get the density of
>> the region.  That should do it.
>>
>> Another cool feature would be to color polygons according to density or to leave
>> some densities unfilled.
> 
> After thought, I'm afraid there is a big problem: in Povray, polygon
> (and actually triangle too) are not oriented. This is basically the root
> of the non-handness commitment.
> 
> As long as "density" would need an orientation to work correctly, it
> would be not-compatible with the parsing of polygon using 3D vectors.

That would only be true if the algorithm would be asymmetric with
respect to winding order.

Note that, in the above algorithm, reversing the definition of "positive
direction" will only affect the /sign/ of the computed "direction sum",
while the magnitude will remain unaffected; and it's only the magnitude
that matters in the "in" vs. "out" test (specifically whether that
magnitude is non-zero).

So no, there's nothing "not-compatible" about density filling; it only
adds one requirement that the user must pay attention to: They must use
a /consistent/ winding order for all "sub-polygons" of any /one/ polygon
primitive (with "holes" using the "reverse" of that winding order).
Whether that winding order is left- or right-handed from any given
perspective is entirely irrelevant. It may even differ between polygons
on the very same plane, provided they reside in separate primitives.


Post a reply to this message

From: Hedrondude
Subject: Re: Density filling option for polygon
Date: 4 Jun 2018 21:30:00
Message: <web.5b15e64c4a5570bb478b32bb0@news.povray.org>
clipka <ano### [at] anonymousorg> wrote:
> Am 04.06.2018 um 04:29 schrieb Hedrondude:
>
> > Another cool feature would be to color polygons according to density or to leave
> > some densities unfilled.
>
> I don't think the former would be possible /per se/ with reasonable
> effort. The latter would probably be quite easy to implement (and could
> then be used to emulate the former, by using copies of the polygon with
> different colours and different density ranges), but we'd need to find a
> neat syntax for such a feature.

ideas for syntax:

binary filling, leave as is:

polygon {n, v1,v2,v3,...v1}

density filling:

polygon {n, v1,v2,v3,...v1 density}

fill in one particular density

polygon {m,v1,v2,v3,...v1 density d}

fill in m particular densities:

polygon {n, v1,v2,v3,...v1 density {m,d1,d2,d3,..,dn}}


Post a reply to this message

From: William F Pokorny
Subject: Re: Density filling option for polygon
Date: 5 Jun 2018 08:20:29
Message: <5b16800d$1@news.povray.org>
On 06/04/2018 12:27 PM, clipka wrote:
> Am 04.06.2018 um 17:30 schrieb Le_Forgeron:
>> Le 04/06/2018 à 04:29, Hedrondude a écrit :
>>
...
> 

I'd like to suggest, if we are looking at polygon enhancements - 
canonical point ordering for fill options etc, we consider staying 
compatible with packages like:

https://sourceforge.net/projects/polyclipping/

even if not looking to support that package specifically - though it 
would be my choice at present.

Integrating 'polyclipping' in some fashion with POV-Ray via new SDL 
options would open up new capabilities related to linear splines, 
polygons, prisms for sure(1). Perhaps also additional bounding options, 
fonts and such too.

Bill P.

(1) - SDL having a general 'list' (C++ std::vector like) features 
alongside too for point lists would be very handy too.


Post a reply to this message

Goto Latest 10 Messages Next 9 Messages >>>

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