## Re: [antiprism] Re: lines_intersection

Expand Messages
• Hi Roger ... Well done for finding the solution. I have checked and I introduced this error into the development code when I was renaming function arguments to
Message 1 of 22 , Feb 1 4:13 AM
• 0 Attachment
Hi Roger

On Mon, 1 Feb 2010, Roger Kaufman wrote:
> I went over the code they have on their page. The noteworthy change is
> the P = P0 + sc*u change from P = P1 + ... same for Q.

Well done for finding the solution. I have checked and I introduced
this error into the development code when I was renaming function
arguments to try to make them consistent between the various
functions.

I use the function in kcycle and the examples I have tried
have worked with both forms of the function!

You are right about the need for these functions to
take an epsilon argument.

> if(lines_nearest_points(P, P_dir, Q, Q_dir, N1, N2, epsilon)) {
...
> The call to lines_nearest_points uses P_dir instead of P+P_dir. Same for Q.

I don't think that should work, generally. lines_nearest_points
is expecting two points that lie on a line and P_dir won't
generally lie on the line through P and P+P_dir (only
in the case where the line passes through the origin.)

Regarding the parameters, it is probably better for
lines_intersection to have the same line parameters
as lines_nearest_points. I will change it to take all
point parameters. (No plans to add it in, but it would
be nice to be able to distinguish position vectors and
free vectors).

> This maybe should be the only way it can work. If N1 and N2 are two far
> apart it probably shouldn't give an answer? (it is suppose to be
> intersection)

I originally added it as a convenience function to find the
intersection of lines lying in the same plane. It therefore
always returns a "best" intersection point (the lines may
just miss), and returns an unset vector if the lines are
parallel. Maybe it would be better to call the function
coplanar_lines_intersection. I will also improve the
documentation.

> vec3d lines_intersection_in_segment(vec3d P, vec3d P_dir, vec3d Q, vec3d Q_dir, double epsilon)
> bool in_segment(vec3d intersection_point, vec3d P, vec3d P_dir, vec3d Q, vec3d Q_dir)
...
> So far in what I have tested this works.

I'll wait until you send me something, and then add them into vec_utils
with the others.

> I am finding the triangle overlap code is going to be fairly complex!

Did you look into using the GLU Tesselator? It appeared that
it would make it quite straightforward to pick out the overlapped
and non-overlapped parts.

--
• Hi Adrian, ... But it will not work (for me) when I have P+P_dir. I suppose I am using it as though it were P0,P1,Q0,Q1. When I use P+P_dir the found
Message 2 of 22 , Feb 1 7:31 AM
• 0 Attachment

> > if(lines_nearest_points(P, P_dir, Q, Q_dir, N1, N2, epsilon)) {
> ...
> > The call to lines_nearest_points uses P_dir instead of P+P_dir. Same for Q.
>
> I don't think that should work, generally. lines_nearest_points
> is expecting two points that lie on a line and P_dir won't
> generally lie on the line through P and P+P_dir (only
> in the case where the line passes through the origin.)

But it will not work (for me) when I have P+P_dir. I suppose I am using it as though it were P0,P1,Q0,Q1. When I use P+P_dir the found intersections are never on the lines but always a little bit to the side of them.

> Regarding the parameters, it is probably better for
> lines_intersection to have the same line parameters
> as lines_nearest_points. I will change it to take all

I think you are right. P_dir suggests it will find the nearpoints in only that direction. But actually it finds the intersection as though the line were theoretically infinite. Unless I am wrong, there is no directionality implied in the outcome.

> I originally added it as a convenience function to find the
> intersection of lines lying in the same plane. It therefore
> always returns a "best" intersection point (the lines may
> just miss), and returns an unset vector if the lines are
> parallel. Maybe it would be better to call the function
> coplanar_lines_intersection. I will also improve the
> documentation.

Actually it works quite fine in 3D! So I don't think the name needs to be restricted to coplanar. The problem is, if two lines are not parallel but don't come near one another, the nearest points on those two lines are identified. Then the function returns a point midway on that segment. I included an OFF file below in which I tested this.

OFF
4 2 0
1 1 10
1 1 -10
10 -1 1
-10 -1 1
2 0 1
2 2 3

The function finds the nearpoints quite nicely but the lines don't interesect. I changed (my copy of) the function because I think it should always test for this. The average of N1 and N2 is sort of moot after that.

If the midpoint of the shortest segment were wanted, perhaps another function (without the mag() test), would be called lines_average_nearpoints()?

vec3d lines_intersection(vec3d P, vec3d P_dir, vec3d Q, vec3d Q_dir, double epsilon)
{
vec3d N1, N2;
if(lines_nearest_points(P, P_dir, Q, Q_dir, N1, N2, epsilon) && ((N1-N2).mag() < epsilon))
return (N1+N2)/2.0;
else
return vec3d();
}

> Did you look into using the GLU Tesselator? It appeared that
> it would make it quite straightforward to pick out the overlapped
> and non-overlapped parts.

In my searches nothing like this ever came up. Could you point me to something? (I have searched using GLU Tessalator and finding hints of it). Is this something available or does it need to be linked in? I would rather avoid having to add anything library-wise. Actually I find this an interesting problem.

Roger
• Hi Roger ... I have included a test program at the end of the email that checks the nearpoints on a couple of diagonals through a unit cube (that don t pass
Message 3 of 22 , Feb 1 10:28 AM
• 0 Attachment
Hi Roger

On Mon, 1 Feb 2010, Roger Kaufman wrote:
>>> if(lines_nearest_points(P, P_dir, Q, Q_dir, N1, N2, epsilon)) {
>> ...
>>> The call to lines_nearest_points uses P_dir instead of P+P_dir. Same for Q.
>>
>> I don't think that should work, generally. lines_nearest_points
>> is expecting two points that lie on a line and P_dir won't
>> generally lie on the line through P and P+P_dir (only
>> in the case where the line passes through the origin.)
>
> But it will not work (for me) when I have P+P_dir. I suppose I am using
> it as though it were P0,P1,Q0,Q1. When I use P+P_dir the found
> intersections are never on the lines but always a little bit to the side
> of them.

I have included a test program at the end of the email that
checks the nearpoints on a couple of diagonals through a unit
cube (that don't pass through the origin!). lines_nearest_points()
using P+P_dir.

If you have the right answer using P_dir it may be that your
P_dir vector is really a position vector of a point on the
line rather than a free vector in the direction of the line.

>> Regarding the parameters, it is probably better for
>> lines_intersection to have the same line parameters
>> as lines_nearest_points. I will change it to take all
>
> I think you are right. P_dir suggests it will find the nearpoints in
> only that direction. But actually it finds the intersection as though
> the line were theoretically infinite. Unless I am wrong, there is no
> directionality implied in the outcome.

I meant to comment on this from your other email. There
are two ways that you might set up a parametric equation
of a line using vectors.

R is a point on the line passing through P and Q
R = tQ + (1-t)P for some number t (-inf<t<inf)

R is a point on the line through P with direction v
R = P + sv for some number s (-inf<s<inf)

To see the connection. v = k(Q-P) for some number k
R = P + sv
R = P + sk(Q-P)
R = P + skQ - skP
R = skQ + (1-sk)P

So, a line can be represented by (P, Q) or by (P, v).
The parameters are related by t = sk so any point
given by one equation form can also given by the other.

I thought that for consistency just one of the forms
could be used, and that it might as well be the form
using all points (just because that is what the original
function used).

> Actually it works quite fine in 3D! So I don't think the name needs to
> be restricted to coplanar. The problem is, if two lines are not parallel
> but don't come near one another, the nearest points on those two lines
...
> If the midpoint of the shortest segment were wanted, perhaps another
> function (without the mag() test), would be called
> lines_average_nearpoints()?

The easiest way to sort this out might be to get
rid of the function! It is only a convenience function
and it isn't a clear choice what will be generally
convenient so programs could just set up their own.

>> Did you look into using the GLU Tesselator? It appeared that
>> it would make it quite straightforward to pick out the overlapped
>> and non-overlapped parts.
>
> In my searches nothing like this ever came up. Could you point me to
> something? (I have searched using GLU Tessalator and finding hints of
> it). Is this something available or does it need to be linked in? I
> would rather avoid having to add anything library-wise. Actually I find
> this an interesting problem.

It is described in "CSG Uses for Winding Rules" in the
OpenGL Red Book

http://glprogramming.com/red/chapter11.html

as it is used for the triangulation. The fallback triangulation
routine fails in many cases, but is handy for building Antiprism
without OpenGL (although the development build is currently broken
for building without OpenGL.) I may add the GLU Tesselator code
into Antiprism to be built if a GLU library is not available.
That way everything, apart from antiview, could be built and work
properly without needing OpenGL to be installed.

--
Message 4 of 22 , Feb 1 10:36 AM
• 0 Attachment
Hi Roger

On Mon, 1 Feb 2010, Adrian Rossiter wrote:
> I have included a test program at the end of the email that

I forgot to include it. It is below.

--

#include "../anti/base/antiprism.h"

int main()
{
vec3d C100 = vec3d(1,0,0);
vec3d C011 = vec3d(0,1,1);
vec3d C010 = vec3d(0,1,0);
vec3d C101 = vec3d(1,0,1);

vec3d P0 = C100;
vec3d P1 = C011;
vec3d P_dir = P1-P0;
vec3d Q0 = C010;
vec3d Q1 = C101;
vec3d Q_dir = Q1-Q0;

vec3d N1, N2;

lines_nearest_points(P0, P_dir, Q0, Q_dir, N1, N2);
fprintf(stderr, "\nintersect: point, dir\n");
N1.dump("N1");
N2.dump("N2");

lines_nearest_points(P0, P0+P_dir, Q0, Q0+Q_dir, N1, N2);
fprintf(stderr, "\nintersect: point, point+dir\n");
N1.dump("N1");
N2.dump("N2");

return 0;
}
• Hi Adrian, ... Then my P_dir is really a position vector as you say. You have vec3d P0 = C100; vec3d P1 = C011; vec3d P_dir = P1-P0; but the P0+P_dir would be
Message 5 of 22 , Feb 1 11:58 AM
• 0 Attachment

> I have included a test program at the end of the email that
> checks the nearpoints on a couple of diagonals through a unit
> cube (that don't pass through the origin!). lines_nearest_points()
> using P+P_dir.
>
> If you have the right answer using P_dir it may be that your
> P_dir vector is really a position vector of a point on the
> line rather than a free vector in the direction of the line.

Then my P_dir is really a position vector as you say. You have

vec3d P0 = C100;
vec3d P1 = C011;
vec3d P_dir = P1-P0;

but the P0+P_dir would be P1-P0+P0.

I am going to change my parameter names not to use the term P_dir because it is (for me) really the other end point of the line segment.

Alternatively I could call it as, however this seems a bit absurd since they will be added back in right away.

vec3d intersection = lines_intersection(P0, P1-P0, Q0, Q1-Q0, epsilon);

> The easiest way to sort this out might be to get
> rid of the function! It is only a convenience function
> and it isn't a clear choice what will be generally
> convenient so programs could just set up their own.

I agree with this! Then my convienience function will just specify the segment end points and I can keep it local to this program.

I still want to point out, though, that it is possible that the outcome of the current function might look like an intersection when in fact the lines can't intersect.

> > would rather avoid having to add anything library-wise. Actually I find
> > this an interesting problem.
>
> It is described in "CSG Uses for Winding Rules" in the
> OpenGL Red Book
>
> http://glprogramming.com/red/chapter11.html

I was looking at this a long while back. It is a bit involved reading for me so I didn't pursue it.

I like the problem and I think I can solve all intersection types simply by knowing the following info

1) what vertices are internal and external to the opposite triangle
2) what line intersections happened.

The Star of David pattern seems hard, but it is actually the case that line intersections occured and no vertices are internal to either triangle.

There are rules to find the circuits of the seperate polygons which I won't elaborate on here. (also I haven't gone over them all yet)

> The GLU Tesselator is already linked in, if it is available,
> as it is used for the triangulation. The fallback triangulation
> routine fails in many cases, but is handy for building Antiprism
> without OpenGL (although the development build is currently broken
> for building without OpenGL.) I may add the GLU Tesselator code
> into Antiprism to be built if a GLU library is not available.
> That way everything, apart from antiview, could be built and work
> properly without needing OpenGL to be installed.

I wonder if it would be allowed to compile in just the tesselator code like you did with qhull? But perhaps it would require too much supporting GL code to be included.

Roger
• Hi Adrian, ... I found this on opengl blending. I had seen it before and even have some example programs about it. This site says
Message 6 of 22 , Feb 1 4:13 PM
• 0 Attachment

> > It is described in "CSG Uses for Winding Rules" in the
> > OpenGL Red Book
> >
> > http://glprogramming.com/red/chapter11.html
>
> I was looking at this a long while back. It is a bit involved reading for me so I didn't pursue it.

I found this on opengl blending. I had seen it before and even have some example programs about it.

This site says

it is as simple as

glEnable(GL_BLEND);
glBlendFunc(GL_SRC_ALPHA, GL_ONE);

However, even if this were implimented it would only be in antiview.

I am working to make a physical model of the blending which can be shown in any viewer.

Just one problem will be how to blend a triangle which is totally within another triangle. Because the outer triangle would cover the inner triangle, the coplanar clash of colors would still occur in the viewer. The outer triangle needs to be re-built as a polygon with a hole in it. Then the inner triangle's color needs to be the average of the two.

Triangle within triangles could occur in compounds for instance.

Then there could be triangles within triangles and so on. These would have to be a blending of all the parent triangles.

Sounds hard, but not impossible. It will be fun.

Roger
• Hi Roger ... I ll remove it then. ... The approach is quite difficult to follow! I didn t really get it until I had written some code. ... SGI changed the
Message 7 of 22 , Feb 2 4:27 AM
• 0 Attachment
Hi Roger

On Mon, 1 Feb 2010, Roger Kaufman wrote:
>> The easiest way to sort this out might be to get
>> rid of the function! It is only a convenience function
...
> I agree with this! Then my convienience function will just specify the
> segment end points and I can keep it local to this program.

I'll remove it then.

>> It is described in "CSG Uses for Winding Rules" in the
>> OpenGL Red Book
>>
>> http://glprogramming.com/red/chapter11.html
>
> I was looking at this a long while back. It is a bit involved reading
> for me so I didn't pursue it.

The approach is quite difficult to follow! I didn't really get
it until I had written some code.

>> for building without OpenGL.) I may add the GLU Tesselator code
>> into Antiprism to be built if a GLU library is not available.
...
> I wonder if it would be allowed to compile in just the tesselator code
> like you did with qhull? But perhaps it would require too much
> supporting GL code to be included.

SGI changed the license on their sample OpenGL implementation
about a year ago and it should be fine now to include the code
directly in Antiprism.

It looks like it may be possible to extract the tesselator
library. Running some searches through the code the only GL
and GLU dependencies I could see were types and constants.
However, if there is a GL or GLU function in there that I
missed then it could easily introduce a dependency on lots
of other code.

--
• Hi Roger ... It is interesting, but it looks like the problem of blending coplanar polygons might require a bit more than this. Each plane would probably need
Message 8 of 22 , Feb 2 5:02 AM
• 0 Attachment
Hi Roger

On Tue, 2 Feb 2010, Roger Kaufman wrote:
> I found this on opengl blending. I had seen it before and even have some
>
> This site says
>
>
> it is as simple as
>
> glEnable(GL_BLEND);
> glBlendFunc(GL_SRC_ALPHA, GL_ONE);

It is interesting, but it looks like the problem of blending
coplanar polygons might require a bit more than this.

Each plane would probably need to be rendered seperately and
then combined together afterwards. Also, I can't work out
offhand how the face colours could be given equal weight in
an overlap without it depending on how many are involved in
the overlap. For consistency it would probably be necessary
to order the faces of a plane by colour.

--
• Hi Adrian, ... For dealing with two triangles only, I think what I can write will be fairly efficient and not too complex. If it were to deal with large
Message 9 of 22 , Feb 2 7:04 AM
• 0 Attachment

> >> It is described in "CSG Uses for Winding Rules" in the
> >> OpenGL Red Book
> >>
> >> http://glprogramming.com/red/chapter11.html
> >
> > I was looking at this a long while back. It is a bit involved reading
> > for me so I didn't pursue it.
>
> The approach is quite difficult to follow! I didn't really get
> it until I had written some code.

For dealing with two triangles only, I think what I can write will be fairly efficient and not too complex. If it were to deal with large polygons then that would be another matter.

One thing I have to experiment with is seeing if a vertex is on the opposite face. I think I should be able to utilize the existing

is_point_on_surface_hull()

but I have never tried this on a 2D surface. Even if it works, it looks like this might be faster even if it is more specialize. (the fastest code is at the bottom with a demostration applet)

http://www.blackpawn.com/texts/pointinpoly/default.html

It looks like it isn't true for edges. But the intersection test should find those. I also have to test for congruent corners.

I have also been interested in the outcome of the winding rules idea. I don't want to keep track of windings, but it looks like, before it were sent to sort_merge, that any even number stack of congruent triangles could be deleted (or perhaps better to be made invisible) and at least simulate this sort of effect. I think this is modulo-2. It is something to try at least.

Roger
• Hi Adrian, ... By the letter of the definition congruent triangles are just have the same angles and edge lengths. What I meant to say is simulataneous
Message 10 of 22 , Feb 2 11:51 AM
• 0 Attachment

>before it were sent to sort_merge, that any even number stack of >congruent triangles could be deleted (or perhaps better to be made >invisible) and at least simulate this sort of effect. I think this is >modulo-2. It is something to try at least.

By the letter of the definition "congruent triangles" are just have the same angles and edge lengths. What I meant to say is simulataneous triangles such as the faces that are considered duplicate by sort_merge.

In looking for code examples of finding the results of overlapping triangles, what I have found instead is code just to determine if triangles collide and returning a truth value. Coders seem to have competed on this and have theoretically most efficient codings, many in publications. But just a truth value doesn't do me much good!

I also wanted to mention that when using the triangulation (as with off_util -t), overlapping triangles are not triangulated into their "sub-parts". Even if all the triangles edges are replaced with two edges and the intersection points, the triangulation of the result is not the desired one. Edges will be put in place that go across the boundries of the sub-parts. Triangulation doesn't seem to care about overlapping polygons.

There is no way around it. I have to find the intersection parts myself and rebuild the faces. I have researched this quite a lot and haven't found much to help it. I should have spent the time coding! Looks like I am the pioneer in this respect.

Roger
• ... Somehow, this reminds me of the discussion of the orientation of the figure-8
Message 11 of 22 , Feb 2 7:33 PM
• 0 Attachment

> It is described in "CSG Uses for Winding Rules" in the

> Open GL Red Book

> http://glprogramming.com/red/chapter11.html

Somehow, this reminds me of the discussion of the orientation of the figure-8 in synergeo. See the Even-odd rule - Wikipedia, the free encyclopedia.

• Hi Adrian, ... I have given this some more thought and the algorithm gets simpler. Redefine the problem as this. Given two triangles which intersect, the aim
Message 12 of 22 , Feb 3 8:27 AM
• 0 Attachment

> There is no way around it. I have to find the intersection parts myself and rebuild the faces. I have researched this quite a lot and haven't found much to help it. I should have spent the time coding! Looks like I am the pioneer in this respect.

I have given this some more thought and the algorithm gets simpler.

Redefine the problem as this. Given two triangles which intersect, the aim is to inscribe the intersecting part of the one triangle in the other and vise-versa. This is done by introducing new edges, and sub-dividing existing edges.

Once this is done, a skeleton graph of the sub-divided triangles exist. Use graph traveral to traverse the circuits of the holes that have formed. This forms the new faces. No circuit can encompass more than one hole.

There is just the one special case where one triangle complete encompasses another triangle. That just requires a special traversal.

I may be done with this sooner than I thought!

Roger
• Hi Roger ... It depends on the winding. If you join a couple of triangles that wind in opposite directions by a bridging (double) edge then you get a zero
Message 13 of 22 , Feb 4 2:59 AM
• 0 Attachment
Hi Roger

On Tue, 2 Feb 2010, Roger Kaufman wrote:
> I also wanted to mention that when using the triangulation (as with
> off_util -t), overlapping triangles are not triangulated into their
> "sub-parts". Even if all the triangles edges are replaced with two edges
> and the intersection points, the triangulation of the result is not the
> desired one. Edges will be put in place that go across the boundries of
> the sub-parts. Triangulation doesn't seem to care about overlapping
> polygons.

It depends on the winding. If you join a couple of
triangles that wind in opposite directions by a bridging
(double) edge then you get a zero density where they
overlap, which is removed by triangulation. You can see
this viewing the following file in Antiview

OFF
6 1 0
0 0 0
1 0 0
0 1 0
-0.2 0.5 0
0.5 -0.2 0
1 1 0
8 0 1 2 0 3 5 4 3 0.0 0.0 0.0

Of the six triangle tips that are displayed three from
one triangle have positive density, and three from the
other have negative density. In the triangulation
code the GLU tesselator selects non-zero density
regions, but can also select based on positive
and negative density, which would then assign the
non-overlapping parts to the triangle that they
came from.

--
• Hi Roger ... I thought about the how you might solve this, and you seem to be describing what I was thinking of, except the the triangle in triangle wouldn t
Message 14 of 22 , Feb 4 3:44 AM
• 0 Attachment
Hi Roger

On Wed, 3 Feb 2010, Roger Kaufman wrote:
> Redefine the problem as this. Given two triangles which intersect, the
> aim is to inscribe the intersecting part of the one triangle in the
> other and vise-versa. This is done by introducing new edges, and
> sub-dividing existing edges.
>
> Once this is done, a skeleton graph of the sub-divided triangles exist.
> Use graph traveral to traverse the circuits of the holes that have
> formed. This forms the new faces. No circuit can encompass more than one
> hole.
>
> There is just the one special case where one triangle complete
> encompasses another triangle. That just requires a special traversal.

I thought about the how you might solve this, and you
seem to be describing what I was thinking of, except the
the triangle in triangle wouldn't be a special case.

This is the method I was think of. You have two triangles.
Replace their edges by lines. Merge the lines that are close
enough. Find the insersections of these lines with each
other. Keep the intersection points that lie on either
triangle. Merge points that are close enough. Order the points
on each line, taking note of the geometric direction of the
ordering. Order the rays coming out of each intersection by
angle around the plane normal (each line giving two rays
one in its point-order direction and one in the opposite
direction.)

You can now find the (convex) areas that tile the two
triangles by selecting a point and a ray, and moving
along the ray to the next point, then coming out the
following ray to the next point etc. If there is no
further point on a ray then discard the area. Once you
get back to the original point then an area has been
found. Carry on until all the point/ray rairs are
exhausted.

With the final set of areas each area is wholly in
one triangle, or in the other triangle, or in both
triangles. The centroid of the area can be checked
to see which region it lies in, and hence the whole
area.

This same technique can be used in code for stellation.
The plane is divided up by lines and the required face
is built up from the convex areas which are found in the
same way as above

http://www.uwgb.edu/dutchs/SYMMETRY/stelicos.htm

P.S. I have to go out now and I haven't had chance to check
through what I have written carefully.
--
• Hi Adrian, ... I was looking at this a bit. First I didn t know that antiview did this! I ve been looking at winding number and there seems to be algorithms
Message 15 of 22 , Feb 4 6:05 PM
• 0 Attachment

> Of the six triangle tips that are displayed three from
> one triangle have positive density, and three from the
> other have negative density. In the triangulation
> code the GLU tesselator selects non-zero density
> regions, but can also select based on positive
> and negative density, which would then assign the
> non-overlapping parts to the triangle that they
> came from.

I was looking at this a bit. First I didn't know that antiview did this!

I've been looking at "winding number" and there seems to be algorithms having to do with calculating them. I would be interesting to be able to do this and color by winding number. I should look into it.

Then with winding number, one could also make invisible even number windings which is what I think modula-2 rendering is. There are a few regular polyhedra with star polygons that look nice this way.

But regular polyhedra I am at a loss to find anything with 0 density. In fact I can't make anything that does this in antiview. Something that will have 0 density seems to have to be contrived.

I am not sure that my idea of even stacked triangles (from my output) will always work. I will try it when I get far enough.

One thing I wanted to mention is that while make two-triangle test models I was able to make them such that one face would have an inward normal and the other have an outward normal. At first I thought the program was not finding the co-planar faces! This could would not work in this case

vec3d norm = face_norm(verts, faces[i]).unit();
double D = vdot(verts[faces[i][0]]-C, norm);
if(D < 0) // Make sure the normal points outwards
norm = -norm;

Is it because the centroid is also on the plane with the two coplanar triangles? I think that was the reason.

The interesting thing is that the model was considered oriented. I thought when it was oriented, all the normals were the same way. e.g. J85 as generated had all the normals pointed in. But if I do

off_util -O J85

then all the normals point out. However, I see this is not always true as in U75.

I also found is that when U75 is triangulated it is no longer orientable! This means that the coplanar coloring isn't going to work on U75! There are several others which for which this is the case. An interesting situation is U72 which off_report says it is oriented by it is not orientable!

off_util -t U72 | off_report

However

off_util -t U72 -O | off_report

says that is is oriented. But then

off_util -t U72 | off_util -O | off_report

says that is is not orientable and is not oriented! I am hoping there is a bug going on somewhere. Or perhaps some limitation happened.

Thanks for the link on stellations. It is something I was thinking might be fun to do in the future. Have you ever thought about it?

As for my color blending method, I should have something in a week or two, given I have enough time. Then you can look at the program and we can discuss the method and what else could have been done if anything.

But this thing about triangulation producing non-orientable models has me bumbed out. This means that some of models I want to make with blended colors might not be possible with my method.

Roger

Roger
• Hi Roger ... If you mean regular polygon, in this case all the edges wind the same way around the centre. If you choose a point in some closed region and shoot
Message 16 of 22 , Feb 5 4:46 AM
• 0 Attachment
Hi Roger

On Fri, 5 Feb 2010, Roger Kaufman wrote:
> But regular polyhedra I am at a loss to find anything with 0 density. In
> fact I can't make anything that does this in antiview. Something that
> will have 0 density seems to have to be contrived.

If you mean regular polygon, in this case all the edges wind
the same way around the centre. If you choose a point in some
closed region and shoot out a ray from this point away from the
centre at least one edge crosses the ray and all the edges cross
the ray in the same direction. The region therefore has a non-zero
density.

> One thing I wanted to mention is that while make two-triangle test
> models I was able to make them such that one face would have an inward
> normal and the other have an outward normal. At first I thought the
> program was not finding the co-planar faces! This could would not work
> in this case
>
> vec3d norm = face_norm(verts, faces[i]).unit();
> double D = vdot(verts[faces[i][0]]-C, norm);
> if(D < 0) // Make sure the normal points outwards
> norm = -norm;
>
> Is it because the centroid is also on the plane with the two coplanar
> triangles? I think that was the reason.

If you have a triangle on a plane then the vertices, in
order, wind in some direction around the triangle centroid
relative to one side of the plane. The direction of the
normal depends on this winding direction. If you have two
triangles on the same plane that wind in different
direcions then they will have normals that point in
opposite directions.

> The interesting thing is that the model was considered oriented. I
> thought when it was oriented, all the normals were the same way. e.g.
> J85 as generated had all the normals pointed in. But if I do
>
> off_util -O J85
>
> then all the normals point out. However, I see this is not always true
> as in U75.

normals yet. I was thinking that the face attached normals
would be of visual interest and could be an option in off2*
and antiview. If there is a geometric use then an option
could be added to off_util for now.

As regards normal direction. The orientable resource
models should be oriented to have a positive volume. I
haven't checked this recently. I notice that U75 has
zero volume but the reported figure is on the negative
side of zero on my machine. I guess it might come
out positive on someone elses.

U75 is like the octahemioctahedron in having faces
with inward and outward pointing normals. If you
look at the vertex figure

http://en.wikipedia.org/wiki/File:Great_dirhombicosidodecahedron_vertfig.png

The lower pentagam and upper triangle are attached to
the square running bottom left to upper right on
opposite sides of its plane (i.e. their centres lie
on opposite sides). They therefore wind in different
directions with respect to the centre of the polyhedron,
and one will have its normal pointing out and the
other one has its normal pointing in.

> I also found is that when U75 is triangulated it is no longer
> orientable! This means that the coplanar coloring isn't going to work on
> U75! There are several others which for which this is the case. An
> interesting situation is U72 which off_report says it is oriented by it
> is not orientable!
>
> off_util -t U72 | off_report
>
> However
>
> off_util -t U72 -O | off_report
>
> says that is is oriented. But then
>
> off_util -t U72 | off_util -O | off_report
>
> says that is is not orientable and is not oriented! I am hoping there is
> a bug going on somewhere. Or perhaps some limitation happened.

This is a good one to find. I haven't checked but I
think I know what is going on. It looks like a bug
caused by having incomplete information about how
faces are connected when more than two meet at an edge.

The first minor issue is that after finding a polyhedron
is oriented it isn't necessary to try and orient it to
check whether it is orientable!

The main problem though is that the orientation process
probably changes the connections, and its choice of
connection may not be that by which the polyhedron
is oriented, and may make the polyhedron unorientable.

If this is is the case, I will report that orientability
is not determinable where a polyhedron has edges shared
by more than two faces (but never an odd number of faces).
I will also have to review what happens for the number of
parts.

> Thanks for the link on stellations. It is something I was thinking might
> be fun to do in the future. Have you ever thought about it?

Only as something to keep in mind. It probably needs a GUI to
select the faces.

> But this thing about triangulation producing non-orientable models has
> me bumbed out. This means that some of models I want to make with
> blended colors might not be possible with my method.

If you are choosing your normals relative to a point then it
shouldn't matter whether the polyhedron is oriented. For
faces passing through the point then you could "normalise"
the direction using the coordinate axes.

If you are using the original orientation then you could
assign a triangle the normal of the face it came from.

--
• Hi Roger ... Here is an example. Three prisms are joined, each sharing an edge with the other two http://www.antiprism.com/misc/orient_choice.jpg The
Message 17 of 22 , Feb 5 7:23 AM
• 0 Attachment
Hi Roger

On Fri, 5 Feb 2010, Adrian Rossiter wrote:
> The main problem though is that the orientation process
> probably changes the connections, and its choice of
> connection may not be that by which the polyhedron
> is oriented, and may make the polyhedron unorientable.

Here is an example. Three prisms are joined, each sharing
an edge with the other two

http://www.antiprism.com/misc/orient_choice.jpg

The orientation of the top face of each pyramid determines
the orientation of its other faces. Orientation starts at
the vertical square face at "start" and progresses to the
vertical square face at "current".

There are two possibilities for orienting the next face,
which is on the starting pyramid. One choice is consistent
with the orientation of the "start" face and will find the
shape is orientable. The other choice leads to a clash of
orientations and will find that the sphape is non-orientable.

If the connections were given as part of the description
of the shape then there would be no ambiguity.

--
Message 18 of 22 , Feb 5 7:37 AM
• 0 Attachment
On Fri, 5 Feb 2010, Adrian Rossiter wrote:
> Here is an example. Three prisms are joined, each sharing
...
> The orientation of the top face of each pyramid determines
...
> which is on the starting pyramid. One choice is consistent

That should have said prism instead of pyramid (there were
no pyramids!)

--
• Each perpendicular line segment is really the cross product of the area of the face. For example, if each face were a parallelogram, then the resulting
Message 19 of 22 , Feb 5 6:03 PM
• 0 Attachment
Each perpendicular line segment is really the cross product of the area of the face. For example, if each face were a parallelogram, then the resulting AREA-vector would be the product of two adjacent edges of that parallelogram times the sine of the angle between them. If the angle were a right angle, then the resulting rectangle would have more area than an oblique parallelogram, of course, since the sine of a right angle reaches the maximum of 1. If you are using a triangle, then you are dealing with half of a parallelogram, so your "cross product" would be half as much of course. See http://mathworld.wolfram.com/CrossProduct.html

Note that the only consistency we need to worry about is whether all the vectors point in or point out of the closed polyhedron. Please, let's all not get hung-up whether this is a left-hand or a right-hand coordinate system. I think that either http://mathworld.wolfram.com/Left-HandedCoordinateSystem.html
and/or http://mathworld.wolfram.com/Right-HandedCoordinateSystem.html
are both arbitrary.

Yes, I know about the breakdown of parity and the "right-hand rule" of physics as told in http://scienceworld.wolfram.com/biography/Ampere.html

After all, the vectors have to total to a closed loop, so it really doesn't matter which direction around the loop to go!

http://groups.yahoo.com/group/synergeo/message/22818

>
> If you have a triangle on a plane then the vertices, in
> order, wind in some direction around the triangle centroid
> relative to one side of the plane. The direction of the
> normal depends on this winding direction. If you have two
> triangles on the same plane that wind in different
> directions then they will have normals that point in
> opposite directions.
• Hi Adrian, ... This was a bit of a panic on my part. The code works on everything unitile2d produces. But is possible to create a tiling by hand such that the
Message 20 of 22 , Feb 7 6:07 AM
• 0 Attachment

> > program was not finding the co-planar faces! This could would not work
> > in this case
> >
> > vec3d norm = face_norm(verts, faces[i]).unit();
> > double D = vdot(verts[faces[i][0]]-C, norm);
> > if(D < 0) // Make sure the normal points outwards
> > norm = -norm;
> >
> > Is it because the centroid is also on the plane with the two coplanar
> > triangles? I think that was the reason.
>
> If you have a triangle on a plane then the vertices, in
> order, wind in some direction around the triangle centroid
> relative to one side of the plane. The direction of the
> normal depends on this winding direction. If you have two
> triangles on the same plane that wind in different
> direcions then they will have normals that point in
> opposite directions.

This was a bit of a panic on my part. The code works on everything unitile2d produces. But is possible to create a tiling by hand such that the normals point in opposite directions and it isn't possible using the code above to determine direction. The program doesn't need to be able to work with models that are already just one plane.

> I haven't had chance to comment on your utility to display
> normals yet. I was thinking that the face attached normals
> would be of visual interest and could be an option in off2*
> and antiview. If there is a geometric use then an option
> could be added to off_util for now.

The program is becoming a mix of code. Where it should all end up can be dealt with later. It is possible some of it might go in src_extra if desired.

But it is nice to plot the normals and see how they stay put no matter what position the model is translated to. I am wondering if a polyhedra can be scaled and positioned such that all the normal to face distances are minimial.

> > says that is is not orientable and is not oriented! I am hoping there is
> > a bug going on somewhere. Or perhaps some limitation happened.
>
> This is a good one to find. I haven't checked but I
> think I know what is going on. It looks like a bug
> caused by having incomplete information about how
> faces are connected when more than two meet at an edge.
>
> The first minor issue is that after finding a polyhedron
> is oriented it isn't necessary to try and orient it to
> check whether it is orientable!

Again more panic on my part. The planes only need to be found before triangulation. On 3D models it is no problem to force normals to all point one way. So in that respect it doesn't even matter of the model is oriented on the way into the program!

It also doesn't matter if the output is orientable. The models are being produced for the sake of viewing. I am not even sure yet, that the output will always come out as closed polyhedra, although I am hoping this is the case!

Roger
Your message has been successfully submitted and would be delivered to recipients shortly.