Re: surface elements for transparent_solids.dem

[Daniel J S. <dan...@ie...>]

I've gotten a little further with some ideas.  As far as uncertainty with implementing ideas and the potential for bugs in the code, I think I'm to the point where thoughts are beginning to gel.

I understand the issues that Hans has raised (and actually one he hasn't raise that I think is also a problem here, I'll come back to that).  However, I think this Kuen example is one function where a sequence of tiling exists that will produce the desired appearance.  The question is finding that sequence... and I will propose some further ideas later.

I've written a routine that can tell whether a surface element (e.g., kuen demo) covers a point.  That's not too difficult.  Break things into triangles and use simple linear algebra equations using hyperplanes, matrix inverse, etc.  I've put some numbers into the equations and printed them to screen and I'm fairly confident they are correct.

OK, so with a "quadrangle cover point" routine, it is possible to correct some errors due to the depth sorting approach.  That is, after the sort, sweep through the list and examine the corners of quadrangles.  Is there:

1) Any quadrangle with a corner hidden by a "lower" quandrangle?  If so, move that quadrangle down in the list.

2) Any quadrangle that does not cover the corners of a lower quandrangle?  If so, move that quadrangle down in the list.

(Note, the above sweep is done by rearranging points only after all tests are complete.  Doing so before the sweep is complete would only lead to other problems I think.)

Barring any bugs (it's a painstaking use of pointers and such), the result is in the attached PNG.  The method does an OK job.  It cleans up a good deal of the tiling problems, but notice there are a few flaws remaining.  To search for the reason of these, I've fooled around with coloring the tiles that the code thinks should be moved downward.  Most of these flawed tiles you see are ones that the routine thinks should not be moved.

However, if I look at the flaws, there are some cases where a flawed corner lands inside a tile.  Those should be found by the routine.  (The ones that will pose a problem are those quandrangles that overlap yet no corner is inside the other quadrangle.)  So what is the issue?

Reasons for this might be:

1) Bug in the sorting approach.  (Let's say I'm 75% confident in what I've written.)

2) Issue with the map3d_xyz routine, or the manner in which it is used.  I assume people are confident with map3d_xyz.  However, one small issue (and I don't think it is the ultimate problem) is that pm3d code will call map3d_xyz and then cast the x and y values to integers.  That isn't exactly good if later your code depends on some computations involving relationships between x, y and z.  The z value is no longer the actual z value associated with x and y after x and y have been rounded to integers.  Probably only a slight discrepency in most cases.

3) Mutual cover, i.e., QA covers QB covers QC covers QA kind of problem.  Like I said, I don't think this Kuen function is an example of that.

4) *sample resolution*  could be an issue here.  And not in the manner of having to choose a greater sample resolution.  Let me try to explain with the Kuen example.  Notice that a lot of the tiles that are sticking through from the back to the front are big tiles.  Could it be that the curvature of the surface is such that a linear approximation interpolating points in the quad_covers_point() test fails?  That is, per my added test, the tiles that are flaws really do have corners that look to be on the other side of the surface (which also uses linear approximations)?

I suggest number 4 is likely an issue here.  Well, this requires more thought.  Anyway, let me propose a few things, because I think we'd like to be able to give the user the facility to generate a plot to their desires.

A)  Might we have more success by going to a more robust "quad_covers_line" approach as opposed to the quad_covers_point() approach for determining if an element should be moved down in depth (i.e., plotted sooner)?  This would mean that quadrangles overlapping quadrangles but neither has a corner landing inside the other quadrangle are addressed.  As I've shown, the hidden3d example of Kuen surface looks good.

B)  Can we introduce some heuristic options.  For example, one rule would be "the group of quadrangles for which all four corners are hidden are plotted first before the groups with at least one point visible".  Not the a good universal approach for sure, but as far as an option it could serve a purpose.

C)  Better interpolation than just linear?  Dodgy.  It is complicated because we have to keep track of neighboring quadrangles.  Also, it will really slow things down.

D)  A new feature perhaps, called "touchup".  Here me out :-).  Let's say the user can provide a list of x,y coordinates pertaining to the view.  These coordinates are problem areas where the pm3d routine should--after the depth order is done--go back and find the top-most element in the list corresponding to the (x,y) view coordinate and move it down in the depth order somehow.  Kind of of clunky, but generating the data might be made easier using the mouse.  I.e., user clicks on "bad tiles" and then types "replot".  (In 'transparent_solids.dem' the data would be known ahead of time.)

Dan


Daniel J Sebald wrote:
> Hans-Bernhard Bröker wrote:
> 
>>Daniel J Sebald wrote:
>>
>>
>>>Hans-Bernhard Bröker wrote:
>>>
>>>
>>>>Daniel J Sebald wrote:
>>
>>
>>>>>Hmm, might there be a slight alteration of this that would work
>>>>>"better"? 
>>
>>
>>>>No.  The whole idea of "depth sorting" is fundamentally flawed.  No 
>>>>slight alteration can make it work correctly.  The only real effect a 
>>>>slight alteration will have is to move the errors to a different 
>>>>region of parameter space, i.e. replace a known-bad guess by an 
>>>>unknown one.
>>>
>>>
>>>Depth sorting with something like qsort() is fundamentally flawed.  
>>
>>
>>No.  It's the "sorting" itself that is based on incorrect assumptions 
>>--- not the choice of sort algorithm or implementation.  The "covered 
>>by" relation is not an ordering.
>>
>>To get correct display, an algorithm has to go beyond sorting.  It has 
>>to be prepared to split some objects into smaller fragments to get a 
>>list that can be sorted.
>>
>>
>>>The assumption of equality is a problem in a sort like that.
>>
>>
>>Equality is not really a problem --- transitivity is.  For a set to be 
>>ordered by a relation '<', it has to be transitive, i.e. the condition
>>
>>    (a < b) and (b < c)  ==> a < c
>>
>>has to hold.  But doesn't hold for the relation "object obstructs (part 
>>of) other object from view)".
> 
> 
> Right.
> 
> 
> 
>>And worse yet, the ordering isn't local.  I.e. you can have two polygons 
>>A and B whose drawing order cannot be determined in any way looking at 
>>these two polygons alone (think of disjoint polygons in a plane parallel 
>>to the view plane).  Adding a third polygon, C, can cause them to have 
>>to be drawn either A before B, or B before A, depending on C.
> 
> 
> Those, for the time being, aren't a concern.  Two reasons.  They are rare (if those start occurring at too high a percentage in one's plot, s/he has not selected the sampling interval large enough or your function has some kind of singularity problem, e.g., 1/sin(x)).  The plotting of the quadrangle which doesn't have convex points is not unique, so you get what you get.
> 
> Barring that class of nasty quadrangles, one can sort but can't use the transitive property.  Hence, almost anything below O(N^2) algorithm is out for a good approximation.
> 
> 
> 
>>Painters' algorithm is a different problem from sorting.  Calling it 
>>"depth sorting" is ultimately a lie.  It's actually harder than sorting. 
>> For vector graphics output like gnuplot's terminal API it has a lower 
>>bound of O(N^2) output size, and thus O(N^2) time for N polygons, 
>>compared to sorting's O(N*log(N)).
> 
> 
> Well, gnuplot is doing depth sorting.  There may be a subtle difference I'm not aware of.
> 
> Dan
> 
> -------------------------------------------------------------------------
> Take Surveys. Earn Cash. Influence the Future of IT
> Join SourceForge.net's Techsay panel and you'll get the chance to share your
> opinions on IT & business topics through brief surveys - and earn cash
> http://www.techsay.com/default.php?page=join.php&p=sourceforge&CID=DEVDEV
> _______________________________________________
> gnuplot-beta mailing list
> gnu...@li...
> https://lists.sourceforge.net/lists/listinfo/gnuplot-beta
> 


-- 

Dan Sebald
phone: 608 256 7718
email: daniel DOT sebald AT ieee DOT org
URL: http://webpages DOT charter DOT net/dsebald/