Thread: Re: Hidden3d Bug Fix

SourceForge Headquarters 1320 Columbia Street Suite 310 San Diego, CA 92101 +1 (858) 422-6466

Hans-Bernhard Bröker wrote:
 > Daniel J Sebald wrote:
 >
 >> I put a bug fix for the hidden3d spics and specs bug on SourceForge.
 >> Patch #1726236.  Please move that into CVS soon.
 >
 >
 > Not without further discussion, please.  Fiddling with the EPSILON
 > doesn't really fix any problem --- it only moves it elsewhere.

OK, I agree with you on the EPSILON issue.  I've abandoned the EPSILON^2 idea on 
area quantities.  Enough on that...

Well, rather than discuss the bug, let me offer up an alternative implementation 
of Test 4 through Test 9 of the hidden3d code.  It is in patch [ 1725993 ] 
Alternate Hidden3d Edge Segmentation.  I think it is a more organized algorithm 
and it inherently does all this classification stuff by way of the mathematical 
equations.  I kept the few mathematical snippets of Test 4-9 such as plane 
equation and cross product area for inside/outside polygon and put them in a 
more mathematical surrounding.  The rest was removed.  I think the result is 
really easy to follow.  Give it a try and let me know of any problems.

Here are the main points.

[1]  I added the following short utilities for sake of reuse and organization.

/* Find the intersection of a line and plane in 3d space in
  * terms of parameterization u where v = v1 + u * (v2 - v1) */
intersect_line_plane(p_vertex v1, p_vertex v2, t_plane p)

/* Find the intersection of two lines in 2d space in terms
  * of parameterization u where v = v1 + u * (v2 - v1) */
intersect_line_line(p_vertex v1, p_vertex v2, p_vertex w1, p_vertex w2)

/* Check whether the point is covered by the plane in 3d space
  *
  * 0 - point not covered
  * 1 - point covered and does not lie in plane
  * 2 - point covered and lies in plane
  */
cover_point_poly(p_vertex v1, p_vertex v2, double u, p_polygon poly)

The new algorithm takes the approach that if we look at a line segment v1, v2 
and a triangular region that might cover it and create a hidden section, there 
are four points along that segment that cuts can be made.  Call these u1, u2, 
u3, and u4.  Some u will be outside the range (0,1) and discarded.  The rest are 
ordered and then each segment is tested as being covered by the triangle.  (See 
Patch #1725993 for a PDF file that gives a better explanation.)

[2]  An important part of this approach is to classify the end points of segments as

0 - not covered by polygon
1 - covered by polygon
2 - on the polygon

the logic that follows from that is to draw the line either of the two points is
not covered *or* if both points are on the polygon.

With the new algorithm and drawing rule results are pretty much the same as with
the existing version.  However, there are differences.  And I think that if one
looks at the hidden demos

load 'animate2.dem'
load 'animate.dem'
load 'binary.dem'
load 'contours.dem'
load 'hidden.dem'
load 'image2.dem'
load 'molecule.dem'
load 'multimsh.dem'
load 'pm3d.dem'
load 'pointsize.dem'
load 'random.dem'
load 'rgb_variable.dem'
load 'scatter.dem'
load 'singulr.dem'
load 'surface1.dem'
load 'transparent_solids.dem'
load 'world.dem'

you'll notice little differences (be sure to rotate the plots using the mouse) 
in which I think the patch performs in a preferred manner.  For example, I've 
attached PNGs for one example without (before_patch.png) and with the patch 
(after_patch.png).  The result with the patch properly hides the axis lines.

[3]  I removed this test from split_line_at_ratio():

      if (EQ(w, 0.0))
  	return vnum1;
      if (EQ(w, 1.0))
  	return vnum2;

because there is still the additional test

     /* additional checks to prevent adding unnecessary vertices */
     if (V_EQUAL(v, vlist + vnum1)) {
	droplast_dynarray(&vertices);
	return vnum1;
     }
     if (V_EQUAL(v, vlist + vnum2)) {
	droplast_dynarray(&vertices);
	return vnum2;
     }

and I like the second test better than the first.  The reason I don't like the 
first test is that the value "w" is between 0 and 1 and is the parameter similar 
to u in v = v1 + u * (v2 - v1).  But "w" doesn't say anything about the final 
distance because v1 and v2 could be relatively close or relative distant 
depending upon the length of the line.  (Remember, things like axes can be a 
factor of 10 or 100 longer than the mesh edges.)

[4]  Here's a bonus FIXME with the patch:  I cleaned up the vertices created by 
in_front(), i.e.,

- * it. FIXME: allocates new vertices when splitting, but never frees
- * them, currently. */

by simply keeping track of vertices.end at the start of in_front(), and right
before the two return locations of the function remove the vertices until
vertices.end matches what it was at the beginning of in_front().

[5]  The sort_edges_by_z() shouldn't be necessary in the quad-tree version of 
the code since there isn't a speed-up test hinged on the order of edges. 
However, it doesn't hurt things and in fact it helps.  I tried without it and 
got pretty much the same results but in some circumstances a line will show 
through.  The reason is described in [6], but in any case, I've left the sort as is.

[6]  In all the demos above using hidden lines, with the patch I've noticed no 
flaws except one.  It is shown in the attached PNG file "tiny_flaw.png".  Look 
inside the upper left tube and you'll notice a red line that should be green. 
This happens because (conjecture!) there is a parallel crossing there where the 
red edge and the green edge are coincident.  Therefore when the corresponding 
polygons from which these edges originate are cover tested, both the green and 
red lines are on the other polygon's plane.  Hence by rule [2], both are 
visible.  Based upon the sort_edges_by_z, the red comes out ahead of the green.

This is the same kind of thing as when we discussed the pm3d ordering and for 
now it is an "oh well" kind of thing.  The way to fix this is to somehow keep 
information about which polygon element the edge originates from.  (Lines, 
points and axes have now polygon they originate from so they must simply be 
treated as the way the currently are.)  For example, if each edge simply had the 
centroid of the element it originated from, we'd be able to tell if it is the 
green line or red line in the above example that should be printed.  We'd know 
which side is facing the viewer, i.e., green in this case.

Dan

PS:  If interested, we might be able to implement a hidden surface algorithm 
using some formulas of http://local.wasp.uwa.edu.au/~pbourke/geometry/.  But the 
real work is setting up the networks (or whatever it would be called in the case 
of surfaces).

Thread: Re: Hidden3d Bug Fix

A portable, multi-platform, command-line driven graphing utility

gnuplot-beta