It is currently Mon, 18-12-17, 18:31 GMT

All times are UTC




Post new topic Reply to topic  [ 47 posts ]  Go to page 1, 2, 3, 4  Next
Author Message
PostPosted: Mon, 28-09-09, 22:30 GMT 
Offline
Site Admin
User avatar

Joined: Fri, 31-08-07, 7:01 GMT
Posts: 4514
Location: Hamburg, Germany
Friends,

in this thread, I want to present my new results about an almost complete reduction of the familiar polar pinch effect at the level of (ascii) shape models! I am quite happy how well this works.

For concreteness, let me discuss things via my recent Perl script for conversion of shape model data of Phobos to ascii CMOD format. For now I'll assume that anisotropic filtering gets rid of polar pinching at the level of textures. Hence, I won't bother about texture pinch now.

I'll present the main algorithm in some hopefully intuitive detail. I shall dispense with math formulae and rather show you with a couple of drawings what the new algorithm amounts to. In detail, the procedure is a bit tricky, yet I ask you to bear with me...the algorithm may open up a number of further important applications and certainly lends itself to generalizations!

The corresponding code and the results you can study explicitly in my new update 1.2 of the Perl script that I have again made available for download towards the end of this post.

The underlying idea arose from the fact that my conversion script for Phobos had to generate the triangular faces for the required tesselation of the shape model.

I noted that conceptually this task is quite related to the previous (pinch) optimizations long available in my F-TexTools for VT-tile generation. Unlike simple cylindrical maps, in both cases, the lengths of circles around the North and South poles for fixed polar angle theta decreases to ZERO towards the poles. Hence, to avoid pinch problems due to a huge overlap of data along these small circles, the data must be "thinned out" around there.

Analogously, in shape models, the sizes of tesselation triangles must strongly increase towards the poles. This is less straightforward in practice than it might at first appear... ;-)

In the previous version 1.1 of my Perl script I conventionally used a constant triangular mesh, as illustrated in this first drawing.

Image

Apparently, the whole (i,j) plane is covered by triangles of same size. Of course, after a map to 3D this simplicity will be considerably distorted. But never mind for now.

The integers (i,j) are to label a regular latitude and longitude mesh in a simple rectangular map. The entire lines (j=0..180) at i=0 and i=90 will be mapped into ONE point, respectively, the South pole and the North pole of the Phobos model. That's actually why I deleted half of the triangles in the top and bottom rows, since in reality these will become degenerate "two-point" triangles.

According to my above observation, the task was to decrease the number of triangles in the polar rows by increasing their sizes in longitude (= jstep). How much can be easily estimated. Note that initially (in the above figure), we had jstep = 1 throughout!,

A strong constraint is that the jstep has to remain integer AND the number of triangles/row = 180/jstep must also be integer!! A possibly unique solution is this
set (Note that I only discuss the south pole now for simplicity)

Code:
i   = 0:   jstep = 36,   # triangles = 180/36 = 5
i   = 1:   jstep = 18,   # triangles = 180/18 =10
i   = 2:   jstep =   9,   # triangles =  180/9  = 20
i   = 3:   jstep =   3,   # triangles =  180/3  = 60
i >= 4:   jstep =   1,    # triangles =  180/1 = 180


and analogously for the North pole, of course.

With these considerations, one might naively try a tesselation around the south pole like in diagram A) of the following display (to be continued a lot on the right, of course).

Image

The triangular sizes in longitude (jstep)have been precisely drawn as indicated in the table above and also shown in the Jstep column on the right.

BUT this cannot work right, yet!

The reason resides in the purple dots drawn in figura A). Once the 3D mapping of this arrangement takes place, you will see black triangular spaces in-between the individual rows (<=> successive circles around the pole), precisely since at the purple dots triangle vertices remained DISCONNECTED to others!. Obviously, we need to be a little more sophisticated.

We do have to connect ALL vertices together, to get rid of this artefact!

How to do this uniquely was a bit of a chore, but figure B) shows the unique result.
I have drawn the additional triangle insertions ("bionds") in purple, so you may compare easily with figure A). Still, we got significantly less triangles than originally with the equal sized mesh. This is good, since it gives rise to a significantly smaller file size in the end.

Now let me show you how much the polar pinch situation has improved with my new tesselation.

Firstly, here is a large zoom of the original pinch appearance around the North pole:

Image

The disturbing starlike pattern should be familiar by now....

Next we look what my new algorithm has done to exactly the same region:

Image

Not at all bad, I would say ;-), and here is the South pole after the pinch correction:

Image

Note that until VERY close to the actual pole (purple S), you can see graphical detail and NO pinch rays! If you don't use excessive zoom, you are not able to tell anymore where the poles are precisely located!

++++++++++++++++++++++++++++++++++++
Finally, here is my updated set of files for you to try out. For your convenience, I have added again the scientific data file along with the processed ascii and binary CMODs. The latter you can directly try out in Celestia.

http://www.celestialmatters.org/users/t ... os_1.2.zip

A convenient new feature is that the required number of faces is now calculated and printed out by computer, since with this more complex tesselation the analytical calculation might be a bit heavy for some ;-) .
++++++++++++++++++++++++++++++++++++

Let me know,
Fridger


Last edited by t00fri on Tue, 29-09-09, 0:36 GMT, edited 1 time in total.

Top
 Profile  
 
 Post subject:
PostPosted: Mon, 28-09-09, 22:52 GMT 
Offline
Site Admin
User avatar

Joined: Thu, 30-08-07, 22:52 GMT
Posts: 2726
Location: France, South, not far from Montpellier
Ok, just tested it and it's already a way better pinch than before!
Hey wait, a better pinch?? :shock:
Ok, what I mean is that despite now the pinch seems smoothed, we still can feel it. So I was curious and turn the wireframe mode to see better the model to discover your decimation concern only the first 3 rows. I guess you can easily decimate till raw 10 or even a bit more. In such case I'm pretty sure the pinch felling could be eliminated completely... What do you think?


Top
 Profile  
 
 Post subject:
PostPosted: Mon, 28-09-09, 23:03 GMT 
Offline
Site Admin
User avatar

Joined: Fri, 31-08-07, 7:01 GMT
Posts: 4514
Location: Hamburg, Germany
ElChristou wrote:
Ok, just tested it and it's already a way better pinch than before!
Hey wait, a better pinch?? :shock:
Ok, what I mean is that despite now the pinch seems smoothed, we still can feel it. So I was curious and turn the wireframe mode to see better the model to discover your decimation concern only the first 3 rows. I guess you can easily decimate till raw 10 or even a bit more. In such case I'm pretty sure the pinch felling could be eliminated completely... What do you think?


I don't think so, because we need to profit from properties of certain integer numbers, the number of which is limited ;-) . This is related to the given 2 degree mesh, of course. If data have a finer spacing there will be better possibilities.

But certainly, I am thinking about generalizations as I have announced.

Actually, the first 5-6 rows are modified close to the North pole and South pole, each.


On the other hand, it it's a bit of a joke, NOT to be content with the present high degree of pinch-absence for a texture that has only 4k ;-) . Users are simply NOT supposed to look at a 4k texture with a MONSTER zoom. The texture is not made for it.

Fridger


Top
 Profile  
 
 Post subject:
PostPosted: Mon, 28-09-09, 23:25 GMT 
Offline
Site Admin
User avatar

Joined: Thu, 30-08-07, 22:52 GMT
Posts: 2726
Location: France, South, not far from Montpellier
t00fri wrote:
ElChristou wrote:
Ok, just tested it and it's already a way better pinch than before!
Hey wait, a better pinch?? :shock:
Ok, what I mean is that despite now the pinch seems smoothed, we still can feel it. So I was curious and turn the wireframe mode to see better the model to discover your decimation concern only the first 3 rows. I guess you can easily decimate till raw 10 or even a bit more. In such case I'm pretty sure the pinch felling could be eliminated completely... What do you think?


I don't think so, because we need to profit from properties of certain integer numbers, the number of which is limited ;-) . This is related to the given 2 degree mesh, of course. If data have a finer spacing there will be better possibilities.

But certainly, I am thinking about generalizations as I have announced.

Actually, the first 5-6 rows are modified close to the North pole and South pole, each.


On the other hand, it it's a bit of a joke, NOT to be content with the present high degree of pinch-absence for a texture that has only 4k ;-) . Users are simply NOT supposed to look at a 4k texture with a MONSTER zoom. The texture is not made for it.


Ok, a pict better than a thousand words:

Image

Blue arrows: what i call "pinch feeling" (pinch smoothed)
Green circle: what I think is the decimated zone, I count 3 rows, 4 if you count the pole itself; I do note that almost no pinch is visible in the circle.
Yellow circle: the zone in where most features are still visible. Reporting it on the wireframe view makes me count 10 to 12 rows to eventually smooth even more (eliminate?) the "pinch feeling"...

So no joke here, I just think what I call "pinch feeling" is well visible and I guess (with my little experience in modelling) decimating a few more rows could do the trick...


Top
 Profile  
 
 Post subject:
PostPosted: Mon, 28-09-09, 23:56 GMT 
Offline
User avatar

Joined: Thu, 25-10-07, 15:20 GMT
Posts: 992
Location: NE PA, USA
From what I seen in your images of the north and south poles, the pinch seems to be gone but the texture is not mapped to the new triangle structure. Is there a way to map the UV's to the new structure. If so, it would probably look better.
cartrite


Top
 Profile  
 
 Post subject:
PostPosted: Tue, 29-09-09, 0:19 GMT 
Offline
Site Admin
User avatar

Joined: Fri, 31-08-07, 7:01 GMT
Posts: 4514
Location: Hamburg, Germany
ElChristou wrote:
Ok, a pict better than a thousand words:

Image

Blue arrows: what i call "pinch feeling" (pinch smoothed)
Green circle: what I think is the decimated zone, I count 3 rows, 4 if you count the pole itself; I do note that almost no pinch is visible in the circle.
Yellow circle: the zone in where most features are still visible. Reporting it on the wireframe view makes me count 10 to 12 rows to eventually smooth even more (eliminate?) the "pinch feeling"...

So no joke here, I just think what I call "pinch feeling" is well visible and I guess (with my little experience in modelling) decimating a few more rows could do the trick...


Christophe,

honestly, I don't understand what the purpose of this is supposed to be. I am working on this stuff quite a bit since several days, while you have just spent 30 minutes, say, to tell me in "excessive graphical detail" what OF COURSE I know already! When I present results, I normally have investigated a lot more before ... and I am not exactly a beginner in this business, who might accidentally have forgotten to make such checks.

If instead you had spent some time looking at my triangle figures, you would know why in the present scenario it is not easy to add just a few more rows. Or do you really think I would not have added a few more rows if that was straightforward? Actually, I would have made the number of anti-pinch rows a parameter to be adjusted for best results, for example.

I rather plea that the whole issue should be seen constructively: there is little doubt that I was able to demonstate with a few clever tesselation optimizations that the pinch problem can be strongly reduced with almost NO effort and no price to pay. That's something we should realize and then think about further interesting applications.


Fridger


Top
 Profile  
 
 Post subject:
PostPosted: Tue, 29-09-09, 1:40 GMT 
Offline
Site Admin
User avatar

Joined: Thu, 30-08-07, 22:52 GMT
Posts: 2726
Location: France, South, not far from Montpellier
t00fri wrote:
Christophe,

honestly, I don't understand what the purpose of this is supposed to be. I am working on this stuff quite a bit since several days, while you have just spent 30 minutes, say, to tell me in "excessive graphical detail" what OF COURSE I know already! When I present results, I normally have investigated a lot more before ... and I am not exactly a beginner in this business, who might accidentally have forgotten to make such checks.

If instead you had spent some time looking at my triangle figures, you would know why in the present scenario it is not easy to add just a few more rows. Or do you really think I would not have added a few more rows if that was straightforward? Actually, I would have made the number of anti-pinch rows a parameter to be adjusted for best results, for example.

I rather plea that the whole issue should be seen constructively: there is little doubt that I was able to demonstate with a few clever tesselation optimizations that the pinch problem can be strongly reduced with almost NO effort and no price to pay. That's something we should realize and then think about further interesting applications.


What do you want me to say? I post depending on what I see! What you call "excessive graphical detail" is a way to explain better what I thought wasn't clear (due to my limited English) in my first post because of your response to it!
Your "let me know" makes me think you wanted feedback but apparently not that much... Well forget, I just don't get it, perhaps it's too late over here and I'm too tired... :|

PS, I do have read your post and see no problem in decimating more rows, but perhaps not in the way you think it should be done...


Top
 Profile  
 
 Post subject:
PostPosted: Tue, 29-09-09, 2:04 GMT 
Offline
User avatar

Joined: Thu, 25-10-07, 15:20 GMT
Posts: 992
Location: NE PA, USA
Has anyone taken a look at John's model? There is no polar pinch I can see in his model. I'm pretty sure that he used a python script that comes with Blender called "mesh_poly_reduce.py" to get that result. If you look at his in Celestia with ctrl w, you see a model that has a strange configuration of triangles. but no polar pinch. With that strange configuration of triangles, the UV's seem like they are mapped correctly too.
cartrite


Top
 Profile  
 
 Post subject:
PostPosted: Tue, 29-09-09, 10:38 GMT 
Offline
Site Admin
User avatar

Joined: Fri, 31-08-07, 7:01 GMT
Posts: 4514
Location: Hamburg, Germany
ElChristou wrote:
Your "let me know" makes me think you wanted feedback but apparently not that much...


Christophe,

it should be obvious to you that a guy with my experience will always do such kind of checks before going public (and many more, actually). So your re-checking and graphical "pinch-feeling" insistence turned matters into a somewhat strange light. Sorry.

I could imagine a LOT of valuable, constructive and non-trivial feedback besides such public checks whether I have done my homework right ;-)

Quote:
PS, I do have read your post and see no problem in decimating more rows, but perhaps not in the way you think it should be done...


For instance, taking your suggestion to extend the pinch correction zone further out, how would you propose to implement other integer triangle sizes than the "fitting" ones with jstep = 36,18,9,3? And that WITHOUT generating those black circular seams around the pole or misplaced triangles that typically signal the non-matching of the triangle size ( 180/jstep = non-integer, un-connected triangle vertices,...).

An obvious way of extending the correction zone is to insert multiple rows for some of the "matching" triangle sizes (36,18,9,3) above 1. That could get me e.g. twice as far out from the pole. Clearly, I could try this explicitly by modifying the script.

More theoretically, one may compare in this respect to the expected behavior e.g. for a purely spherical shape model. The latter formula we know exactly for each row i. It's VERY simple.

Code:
theta = pi*(1-i/90);        ( polar angle: theta=0 at the pole, theta=90 degrees at equator)
jstep_sph = int(180/(180 * sin(theta)-1)+0.5);


It tells us, how the triangle size should ideally be as function of the polar angle theta to retain CONSTANT resolution towards the pole. But NOTE, this formula knows NOTHING about the further constraints on jstep, like 180/jstep = integer and that the triangle vertices must all be connected!

Anyway, here are the numbers from that spherical formula. In the third column I put my present jstep values for comparison:
Code:
i     jstep_sph    jstep
------------------------------------
1,     34              36
2,     16              18
3,     10                9
4,     7                  3
5,     6                  rest 1
6,     5
7,     4
8,     4
9,     3
10,     3
11,     3
12,     2
13,     2
14,     2
15,     2
16,     2
17,     2
18,     2
19,     2
20,     2
21,     2
22,     1
thereafter jstep =1 until the North polar zone


So one observes that surprisingly, my jstep numbers satifying 180/jstep = integer (and thus jstep integer), are quite close initially. But indeed, the approach of my jstep numbers to 1 is faster then the purely spherical correction. So presumably, it is worthwhile to try to insert a few more 9's and 3's in the outer zone.

While being aware of all these considerations, I had adopted a practical point of view in my approach so far. I thought, before getting to massive complexification of the triangulation and the code, I first show with my comparatively simple above correction that one can obtain a high amount of improvement already in combination with the task of CMOD conversion of the shape model.

Of course, I have also derived a corresponding, more involved formula for an ARBITRARY model shape. The corrections from a NON- spherical form can be very substantial. Generally, on sees that it leads to a FASTER decrease towards 1, compared to the spherical case. Our phobos model is strongly NON-spherical ...

One finds instead of the above
Code:
jstep_exact(i) = sum_j{ r(i,j)}/ sum_j{r(equator, j)} * jstep_sph(i)


Hence there is a prefactor to the spherical formula (jstep_sph(i)) that is a sum over the given radii in each row, divided by the same sum over radii taken at the model's equator. It's easy to see qualitatively that this gives a faster decrease towards 1 for each row i.

These were some examples, how and where lots of non-trivial feedback would have been possible from someone with your experience. There are clearly many other possibilities as well

Fridger


Top
 Profile  
 
 Post subject:
PostPosted: Tue, 29-09-09, 11:35 GMT 
Offline
User avatar

Joined: Thu, 25-10-07, 15:20 GMT
Posts: 992
Location: NE PA, USA
Here are 3 images.
1st is Phobos with Fridger's first script in wiremode. There are triangles here but that should not matter. If it does, then I'm sure quads can be drawn instead.

The second image shows John's quad version of Phobos imported into Blender. Notice that it looks similar to the model that was produced by Fridger's first script.

The 3rd image shows John's reduced version of Phobos. Not only was it transformed to triangles but look at the triangle structure after the reduce script was run on it. I'm sure John did some further culling by hand but most of this structure was probably done by the reducer script.

The script that does this is very complicated. The initial script looks simple but when you dig deeper to see what all the keywords mean.........Actually, it goes through a number of scripts/math libraries. It basically calls a module called BPyMesh which calls BPyMesh_redux which uses
Code:
Vector= Blender.Mathutils.Vector
Ang= Blender.Mathutils.AngleBetweenVecs
MidpointVecs= Blender.Mathutils.MidpointVecs



I may never understand what is done here but I am taking a look. Maybe someone else will understand this better. Anyhow, here are the images.

Image

Image

Image

cartrite


Top
 Profile  
 
 Post subject:
PostPosted: Tue, 29-09-09, 12:10 GMT 
Offline
Site Admin
User avatar

Joined: Fri, 31-08-07, 7:01 GMT
Posts: 4514
Location: Hamburg, Germany
Steve,

before getting into that:

-- I have not seen John's ascii CMOD offered for download.

-- I was unable to find out, whether his model is strictly the scientific one that I also use! From some of his images, though, it seemed to clearly involve "handicrafting". John normally likes to do this here and there.. Anyway, his model looked much more "bumpy" than the scientific ones are.

If true then I am not interested in John's model.

-- the main charm of my method is that strictly scientific models can be transferred easily AND transparently into ascii CMOS. Hence I don't have to use some obscure blender script, like "mesh_poly_reduce.py" in yet another scripting language... Precisely all those basically unnecessary complications I want to avoid from the onset.

I would be much more interested in further developing Perl code of a more flexible (and optimized) tesselation algorithm given just the vertices or similar of a shape model. That's why I have started simple in order to REALLY understand what I am doing. I know definitely that a number of such algorithms exist in the applied math/computer science literature. Just have to sort them out.

And to repeat it again, I don't think multiple import-export actions are justified when we are talking about textures as small a a few k in size. But other people may have a different opinions here. At least, when I look at my complete Phobos model with the new pinch improvement AND using a zoom level that is ADEQUATE for a 4k texture, then I can't help, my Phobos looks simply perfect ;-)


Fridger


Top
 Profile  
 
 Post subject:
PostPosted: Tue, 29-09-09, 12:20 GMT 
Offline
User avatar

Joined: Thu, 25-10-07, 15:20 GMT
Posts: 992
Location: NE PA, USA
I think you are missing my point. I'm trying to show that there is a way of reducing the triangles "via a script" in a very complicated way. I've seen Blender do this with the reducer script. All texture coordinates are preserved along with vertex locations. It just rearranges and reduces the triangles somehow. With this method, there is no pole pinching and the texture is seamlessly mapped.
cartrite


Last edited by cartrite on Tue, 29-09-09, 12:25 GMT, edited 2 times in total.

Top
 Profile  
 
 Post subject:
PostPosted: Tue, 29-09-09, 12:21 GMT 
Offline
Site Admin
User avatar

Joined: Thu, 30-08-07, 22:52 GMT
Posts: 2726
Location: France, South, not far from Montpellier
t00fri wrote:
...besides such public checks whether I have done my homework right ;-)


Sorry you take it this way, wasn't the goal, really.

t00fri wrote:
For instance, taking your suggestion to extend the pinch correction zone further out, how would you propose to implement other integer triangle sizes than the "fitting" ones with jstep = 36,18,9,3? And that WITHOUT generating those black circular seams around the pole or misplaced triangles that typically signal the non-matching of the triangle size ( 180/jstep = non-integer, un-connected triangle vertices,...).


Why do you ask me if you already see the obvious solution? My 2 neurons cannot think in complex maths but at least they can process such simple solution:

t00fri wrote:
An obvious way of extending the correction zone is to insert multiple rows for some of the "matching" triangle sizes (36,18,9,3) above 1. That could get me e.g. twice as far out from the pole. Clearly, I could try this explicitly by modifying the script.


That what I was about to ask yesterday! I had even prepare another of my "excessive graphical detail" show but I guess it's quite useless!

So to not repeat such embarrassing situation, perhaps if you begin your speech with a "I want to present my new preliminary results" or shows picts with the actual global pinch smoothed THEN zoom on the center to continue your speech THEN my 2 neurons would not have interpreted your post as an almost final work! (and then of course no obvious checks whether you have done your homework right!)

So on the constructive side, yes please a test with a few more 3 and 9 rows would be for sure interesting!


Last edited by ElChristou on Tue, 29-09-09, 12:26 GMT, edited 1 time in total.

Top
 Profile  
 
 Post subject:
PostPosted: Tue, 29-09-09, 12:25 GMT 
Offline
Site Admin
User avatar

Joined: Thu, 30-08-07, 22:52 GMT
Posts: 2726
Location: France, South, not far from Montpellier
cartrite wrote:
I think you are missing my point. I'm trying to show that there is a way of reducing the triangles "via a script" in a very complicated way. I've seen Blender do this with the reducer script. All texture coordinates are preserved along with vertex locations. It just rearranges the triangles somehow.
cartrite


Blender is not the only soft to use such decimation process. The goal is to respect the geometry, joining 2 closer points and this in general is done in several passes. From my experience (not in Blender), the result is pretty effective BUT you also end with quite some artifacts (bad positioning of points) you can only fix by hand. I don't know if it was the case for John, but if it is that represent too much work for a general tool...


Top
 Profile  
 
 Post subject:
PostPosted: Tue, 29-09-09, 12:33 GMT 
Offline
Site Admin
User avatar

Joined: Fri, 31-08-07, 7:01 GMT
Posts: 4514
Location: Hamburg, Germany
cartrite wrote:
I think you are missing my point. I'm trying to show that there is a way of reducing the triangles "via a script" in a very complicated way. I've seen Blender do this with the reducer script. All texture coordinates are preserved along with vertex locations. It just rearranges and reduces the triangles somehow. With this method, there is no pole pinching and the texture is seamlessly mapped.
cartrite


OK Steve, you may well be right ...

yet, it would have been great if the first sentence of your post was

"I'm trying to show that there is a way of reducing the triangles "via a script" in a very complicated way." ;-) . Why hiding such clear sentences?

Instead your post started quite cryptical:

"Here are 3 images..."

Fridger


Top
 Profile  
 
Display posts from previous:  Sort by  
Post new topic Reply to topic  [ 47 posts ]  Go to page 1, 2, 3, 4  Next

All times are UTC


Who is online

Users browsing this forum: No registered users and 2 guests


You cannot post new topics in this forum
You cannot reply to topics in this forum
You cannot edit your posts in this forum
You cannot delete your posts in this forum
You cannot post attachments in this forum

Search for:
Jump to:  
Powered by phpBB® Forum Software © phpBB Group