CAD Development : 2919


CAD / Development / 2919	2918 \| 2920

Special:	[DAT] (requires LDraw-compatible viewer)
Subject:	CW/CCW, vertex sequence, co-planar, convex, (115kB)
Newsgroups:	lugnet.cad.dev
Date:	Wed, 29 Sep 1999 15:18:49 GMT
Viewed:	794 times

Here are 50 messages regarding the above subjects. The first from January 1998 where Leonardo Zide suggested CW/CCW. I support the CW/CCW idea (isn't it annoying knowing almost 50% of all faces are drawn to waste), though it will cost a considerable effort fixing old parts. The process can however be automated: Leonardo already has a program showing faces as red or green and Gary suggested a ray-algorithm for automatically determining CW/CCW-ness. You should watch out for all kinds of degenerate quads (and triangles), but e.g. L3P can spot these using the -check option. Degenerations are bow-ties, non co-planar quads, concave quads, vertices-on-a-line, etc. Rendering programs would benefit immediately from any available CW/CCW parts, so we could start with the primitives and most used parts. Happy reading - who will summarize the ideas into a working concept? /Lars PS. Some ASCII art requires a monospaced font. ************************************************************************* From: LEGO-style Computer Aided Design [mailto:L-CAD@LISTSERV.UH.EDU] On Behalf Of Leonardo Zide Sent: 31. januar 1998 13:33 To: L-CAD@LISTSERV.UH.EDU Subject: Another Ldraw idea Someone posted a message about adding connection information (I really like the 0 HOT idea) to the Ldraw parts, so I have another suggestion: If the parts are going to be revised, why not fix the order of the vertices placing all of them on clockwise or counter-clockwise order so that it would be possible to have backface culling ? It would also be possible to create normals for each vertex, making possible some other lighting calculations. It would be worth to spend some time fixing the old parts, we would have a great speed increase on the drawing time and a much better editor for the models. And if we share the work, it wouldn't be very hard to do it. ************************************************************************* From: LEGO-style Computer Aided Design [mailto:L-CAD@LISTSERV.UH.EDU] On Behalf Of Jeffrey N Findley Sent: 10. juni 1998 18:15 To: L-CAD@LISTSERV.UH.EDU Subject: Everyone, While debugging my line/optional line generation program, I ran across something I thought was a bug in my code, but was really something unexpected in a .dat file I was using for a test. The .dat file in question contained some quadrilaterals that did not have their points in the order I expected. I expected that all quads would have their points going in order around the edge of the quad. Like so (I'm using a fixed font for the ASCII graphics): 1----2 | | 4----3 The some of the quads in this model had their points in an order like: 1----3 | | 4----2 Because I wasn't expecting this, my program was putting edge lines along the diagonals of these quads. Since LDraw does not seem to mind either format for the quads, does this mean that these quads are acceptable? I would think that others may have run into this problem when writing programs to convert .dat files into other formats like VRML. I can work around this problem in my program (with a little restructuring), but I thought I'd see what others thought before I started hacking away at my code. Thanks, Jeff -- Doesn't everyone want CATS? Not cats silly, Cheap Access To Space! ************************************************************************* From: LEGO-style Computer Aided Design [mailto:L-CAD@LISTSERV.UH.EDU] On Behalf Of K and S Bliss Sent: 11. juni 1998 07:01 To: L-CAD@LISTSERV.UH.EDU Subject: Jeff, Would this be the wrong time to mention that LDraw doesn't care if the quadrilateral is concave (it draws concave quads as triangles) or even if all the points are co-planar? It just maps all the points to the screen, and starts drawing the pixels that lie between the edge-lines. Steve ************************************************************************* From: LEGO-style Computer Aided Design [mailto:L-CAD@LISTSERV.UH.EDU] On Behalf Of Jeffrey N Findley Sent: 11. juni 1998 15:44 To: L-CAD@LISTSERV.UH.EDU Subject: Re: LDraw and quads On Thu, 11 Jun 1998 01:01:16 -0400 Steve Bliss <blisses@WORLDNET.ATT.NET> writes: > Jeff, > > Would this be the wrong time to mention that LDraw doesn't care if the > quadrilateral is concave (it draws concave quads as triangles) If I understand correctly, I think I've heard this referred to as a degenerate quad. It's the case where only three of the four points are really necessary. The fourth point lies within or on the boundary of the triangle defined by the other three points. Is this what you mean? If so, that sounds like something I can detect and fix by turning the quad into a triangle (at least internal to my program). > or even > if > all the points are co-planar? If the points are not co-planar, I suppose that the quad is really drawn like a tetrahedron when you view it from all angles. This is something that I could detect and fix by treating the quad as four separate triangles that make up a tetrahedron. > It just maps all the points to the screen, and starts drawing the > pixels > that lie between the edge-lines. That explains it. Not at all what I would have expected, but it still explains the behavior. How will LDraw II handle this issue? What I'm wondering is if detecting and fixing this problem on the fly will be a performance issue or if the low level graphics will behave like LDraw and still be fast. Jeff -- Doesn't everyone want CATS? Not cats silly, Cheap Access To Space! ************************************************************************* From: LEGO-style Computer Aided Design [mailto:L-CAD@LISTSERV.UH.EDU] On Behalf Of Leonardo Zide Sent: 12. juni 1998 13:59 To: L-CAD@LISTSERV.UH.EDU Subject: Re: LDraw and quads > Subject: Re: LDraw and quads > Date: Thu, 11 Jun 1998 09:44:00 -0400 > From: Jeffrey N Findley <jeffnf@JUNO.COM> > > If I understand correctly, I think I've heard this referred to as a > degenerate quad. It's the case where only three of the four points are > really necessary. The fourth point lies within or on the boundary of the > triangle defined by the other three points. Is this what you mean? If > so, that sounds like something I can detect and fix by turning the quad > into a triangle (at least internal to my program). No, that's not the case. The problem here is that LDraw doesn't care about the order of the points, so people create the quads in any order but you're assuming that the quads were created in a particular order. > How will LDraw II handle this issue? What I'm wondering is if detecting > and fixing this problem on the fly will be a performance issue or if the > low level graphics will behave like LDraw and still be fast. Here's what I did, it's part of the conversion routines from the .DAT files to the LeoCAD library. Use it at your own risk... :) for (i = 0; i < qua; i+=4) { Point3f p1 = { quads[i][0], quads[i][1], quads[i][2] }, p2 = { quads[i+1][0], quads[i+1][1], quads[i+1][2] }, p3 = { quads[i+2][0], quads[i+2][1], quads[i+2][2] }, p4 = { quads[i+3][0], quads[i+3][1], quads[i+3][2] }; Point3f ac = { p3.x-p1.x, p3.y-p1.y, p3.z-p1.z }, ab = { p2.x-p1.x, p2.y-p1.y, p2.z-p1.z }, ad = { p4.x-p1.x, p4.y-p1.y, p4.z-p1.z }; double a1 = acos (V3Dot(&ac,&ab) / (V3Length(&ac)*V3Length(&ab))); double a2 = acos (V3Dot(&ad,&ab) / (V3Length(&ad)*V3Length(&ab))); if (a2 < a1) { quads[i+2][0] = p4.x; quads[i+2][1] = p4.y; quads[i+2][2] = p4.z; quads[i+3][0] = p3.x; quads[i+3][1] = p3.y; quads[i+3][2] = p3.z; } } > Subject: Re: Comprehensive LDraw Parts List > Date: Thu, 11 Jun 1998 23:44:31 +0300 > From: Selcuk Gore <sgore@SUPERONLINE.COM> > > By the way, Leonardo, I almost (95%) completed the Titanic, but decided to wait > for the next version of LeoCAD with your new way of group rotation, to finish > the last parts, the masts. It won't take too long for a ne version, I just have to fix the new bugs. > (I'm not so wrong with the initial piece count assumption, it has 1827 > parts..:-) That's a lot ! I think I never built anything that size. ************************************************************************* From: LEGO-style Computer Aided Design [mailto:L-CAD@LISTSERV.UH.EDU] On Behalf Of Jeffrey N Findley Sent: 15. juni 1998 00:56 To: L-CAD@LISTSERV.UH.EDU Subject: Re: LDraw and quads On Fri, 12 Jun 1998 08:59:27 -0300 Leonardo Zide <leonardo@CENTROIN.COM.BR> writes: > The problem here is that LDraw doesn't care > about the order of the points, so people create the quads in any order > but you're assuming that the quads were created in a particular order. > > Here's what I did, it's part of the conversion routines from the > .DAT > files to the LeoCAD library. Use it at your own risk... :) <snip> Thanks. I used the code you sent as a starting point and came up with a slightly different algorithm (based partly on some thoughts I had before I saw your code). Here it is (in case anyone is curious). It's also use at your own risk. :-) /* * Code before this removes empty space at the beginning and end of a line, then does * a switch statement on the first character (line type). */ else if ( pcLine[0] == '4' ) { nPoint = 4; sscanf(pcLine, "%d %d %lf %lf %lf %lf %lf %lf %lf %lf %lf %lf %lf %lf", &iType, &iColor, &afPoint[0][0], &afPoint[0][1], &afPoint[0][2], &afPoint[1][0], &afPoint[1][1], &afPoint[1][2], &afPoint[2][0], &afPoint[2][1], &afPoint[2][2], &afPoint[3][0], &afPoint[3][1], &afPoint[3][2]); /* * Define three imaginary lines going from the first point * to each of the other points. */ afLine[0][0] = afPoint[1][0] - afPoint[0][0]; afLine[0][1] = afPoint[1][1] - afPoint[0][1]; afLine[0][2] = afPoint[1][2] - afPoint[0][2]; afLine[1][0] = afPoint[2][0] - afPoint[0][0]; afLine[1][1] = afPoint[2][1] - afPoint[0][1]; afLine[1][2] = afPoint[2][2] - afPoint[0][2]; afLine[2][0] = afPoint[3][0] - afPoint[0][0]; afLine[2][1] = afPoint[3][1] - afPoint[0][1]; afLine[2][2] = afPoint[3][2] - afPoint[0][2]; /* Calculate the magnitude of each line */ afMag[0] = vect_mag(afLine[0]); afMag[1] = vect_mag(afLine[1]); afMag[2] = vect_mag(afLine[2]); /* * Define three angles between the first and second line, * the first and third line, and the second and third line. */ a1 = acos(dot_product(afLine[0], afLine[1]) / (afMag[0] * afMag[1])); a2 = acos(dot_product(afLine[0], afLine[2]) / (afMag[0] * afMag[2])); a3 = acos(dot_product(afLine[1], afLine[2]) / (afMag[1] * afMag[2])); /* * If the third angle is greater than the other two, then * the first line (first and second points) is one of the * diagonals of the quad. */ if ( a1 < a3 && a2 < a3 ) { ppzPoint[0] = add_point(ppzFirstPoint, &afPoint[0][0]); ppzPoint[1] = add_point(ppzFirstPoint, &afPoint[2][0]); ppzPoint[2] = add_point(ppzFirstPoint, &afPoint[3][0]); ppzPoint[3] = add_point(ppzFirstPoint, &afPoint[1][0]); } else { /* The first line is along an outer edge */ ppzPoint[0] = add_point(ppzFirstPoint, &afPoint[0][0]); ppzPoint[1] = add_point(ppzFirstPoint, &afPoint[1][0]); /* * If the angle between the first and second lines is * less than the angle between the second and third lines, * then the points are already in order */ if (a1 < a2) { ppzPoint[2] = add_point(ppzFirstPoint, &afPoint[2][0]); ppzPoint[3] = add_point(ppzFirstPoint, &afPoint[3][0]); } else { /* The last two points need to be reversed */ ppzPoint[2] = add_point(ppzFirstPoint, &afPoint[3][0]); ppzPoint[3] = add_point(ppzFirstPoint, &afPoint[2][0]); } } } /* * The ppzPoint array now has the point structures in the proper order for the add_face * function (no bow-ties). */ Thanks for the help. Jeff -- Doesn't everyone want CATS? Not cats silly, Cheap Access To Space! ************************************************************************* From: Lars C. Hassing Sent: 18. juni 1998 12:30 To: L-CAD@LISTSERV.UH.EDU Subject: Re: LDraw and quads On Thu, 11 Jun 1998 09:44:00 -0400 Jeffrey N Findley <jeffnf@JUNO.COM> writes: > > On Thu, 11 Jun 1998 01:01:16 -0400 Steve Bliss <blisses@WORLDNET.ATT.NET> > writes: > > Jeff, > > > > Would this be the wrong time to mention that LDraw doesn't care if the > > quadrilateral is concave (it draws concave quads as triangles) > > If I understand correctly, I think I've heard this referred to as a > degenerate quad. It's the case where only three of the four points are > really necessary. The fourth point lies within or on the boundary of the > triangle defined by the other three points. Is this what you mean? If > so, that sounds like something I can detect and fix by turning the quad > into a triangle (at least internal to my program). > > > or even > > if > > all the points are co-planar? > > If the points are not co-planar, I suppose that the quad is really drawn > like a tetrahedron when you view it from all angles. This is something > that I could detect and fix by treating the quad as four separate > triangles that make up a tetrahedron. I think it is an error if the four points of a quad do not lie in a plane. If you are going to draw a quad as two triangles, which of the two triangle pairs would you choose ? On Thu, 14 May 1998 09:22:50 +0200 Jacob Sparre Andersen <sparre@CATS.NBI.DK> wrote: > I am going to implement the quadrilateral command from LDraw as two > triangles, so it is going to be similar to the current implementation. - I > find that command most annoying, since it is most illogical. Polygons do > not exist in 3D space. They are limited to two dimensions, so the "correct" > definition of that command would be a 3D point and two 3D vectors (to > define a 2D plane in 3D space), and then a sequence of 2D points defining > the polygon. You are right, the 4 points of a quad should be coplanar. To Leonardo Zide <leonardo@CENTROIN.COM.BR> and Jeffrey N Findley <jeffnf@JUNO.COM>: I think that both of your algorithms are wrong. They do not cover all cases and may even produce "false alarms". Here is what I did: You have three vertices 0, 1 and 2. Where is the fourth vertex 3 located ? If 3 is in I (the most common case) you have a quad which can be divided into two triangles by the diagonal 02. The quad may be either convex (if 3 is in the area below V) or concave. If 3 is in III or IV you have a bow-tie error and you may choose a new sequence of vertices. If 3 is in II or V you have a concave quad which can be divided into two triangles by the diagonal 13. (PLEASE USE A MONOSPACED FONT) \ / \ II / \ / \ / \ / III 1 IV / \ / \ / \ / V \ / \ -------0-----------2-------- . . . I . . . __ __ __ __ A: (01 x 02).(02 x 03) > 0 then 3 is in I else in II, III, IV or V __ __ __ __ B: (12 x 10).(10 x 13) > 0 then 3 is in II or III else in IV or V __ __ __ __ C: (20 x 21).(21 x 23) > 0 then 3 is in II or IV else in III or V void QuadTest(float quad[4][3]) { float v01[3], v02[3], v03[3]; float v12[3], v13[3], v23[3]; float cp1[3], cp2[3]; float dotA, dotB, dotC; int A, B, C; /* Calculate A */ Sub3(v01, quad[1], quad[0]); Sub3(v02, quad[2], quad[0]); Sub3(v03, quad[3], quad[0]); Cross3(cp1, v01, v02); Cross3(cp2, v02, v03); dotA = Dot3(cp1, cp2); A = (dotA > 0.0); /* Calculate B and C (may be postponed/discarded) */ Sub3(v12, quad[2], quad[1]); Sub3(v13, quad[3], quad[1]); Sub3(v23, quad[3], quad[2]); Cross3(cp1, v12, v01); Cross3(cp2, v01, v13); dotB = Dot3(cp1, cp2); B = (dotB > 0.0); Cross3(cp1, v02, v12); Cross3(cp2, v12, v23); dotC = -Dot3(cp1, cp2); C = (dotC > 0.0); if (A) { /* 3 is in I, typical case, OK: 0123 D02 (convex/concave) */ /* CONVEXINFO: quad is convex if (!B && !C): OK: 0123 D02/13 (convex) */ } else { /* 3 is in II, III, IV or V. Calculation of B and C could be postponed to here if CONVEXINFO (above) is not needed */ if (B) { /* 3 is in II or III */ if (C) { /* 3 is in II, OK: 0123 D13 (concave) */ Resequence(quad, 1, 2, 3, 0); /* just to shift diagonal */ } else { /* 3 is in III, bow-tie error: using 0312 D01/D23 (convex) */ Warning("Bad vertex sequence, using 0312"); Resequence(quad, 0, 3, 1, 2); } } else { /* 3 is in IV or V */ if (C) { /* 3 is in IV, bow-tie error: using 0132 D12/D03 (convex) */ Warning("Bad vertex sequence, using 0132"); Resequence(quad, 0, 1, 3, 2); } else { /* 3 is in V, OK: 0123 D13 (concave) */ Resequence(quad, 1, 2, 3, 0); /* just to shift diagonal */ } } } /* The four vertices quad[0], quad[1], quad[2] and quad[3] now have the correct sequence, the polygon can be divided by the diagonal 02 into two triangles, 012 and 230. */ } void Resequence(float v[4][3], int a, int b, int c, int d) { float o[4][3]; memcpy(o, v, sizeof(o)); memcpy(v[0], o[a], sizeof(o[0])); memcpy(v[1], o[b], sizeof(o[0])); memcpy(v[2], o[c], sizeof(o[0])); memcpy(v[3], o[d], sizeof(o[0])); } I hope that you can follow what I mean from the very short description and the code excerpt. Please make any comments. Best regards from Århus, Denmark (only 90 km from Billund :-) /Lars ************************************************************************* From: LEGO-style Computer Aided Design [mailto:L-CAD@LISTSERV.UH.EDU] On Behalf Of Rui Martins Sent: 18. juni 1998 16:10 To: L-CAD@LISTSERV.UH.EDU Subject: Re: LDraw and quads Hi, back again On Thu, 18 Jun 1998, Geoffrey Hyde wrote: > I'm not sure I understand this debate and discussion. But from what ... It seems to me that you don't. You are confusing QUADS, which are only 4 sided polygons, with quads, as in <x,y,z,w> which are normalized coordinates. The last ones are used by the rasterization program, the user never gets to see them. QUADS, its the Ldraw command which starts with the number (4), meanning a polygon with for sides. The problems beeing discussed are related to implementation issues, since its common to define a polygon with a certain winding, clock wise or Counter clock wise. So that the Side of the polygon that is to be seen can be determined. Just imagine 4 points, now in what ways can we combine them. Ex. 1---2 1--4 1---4 | | \/ | | | | /\ | | 4---3 3--2 2---3 C-W wrong C-C-W The first and third polygon are correct, the second is not. Some people want the second to be accepted or converted to the first or third situation But there can another problem, when you are defining a QUAD, since you can give the points by hand, there is a very strong chance that the points are not coplanar. This is, if you define a plane based only on 3 of those points, the fourth point will not belong the plane. This is especialy true, if you are defining an oblique plane. Ex. imagine a 3d View like this \ Four points beeing coplanar 2 / \ / \ 1 3 \ / \ / 4 lets assume the point 4 is not coplanar with the others , but the polygon is supossed to be the same, we now get: 2 / \ / \ 1 3 \ / \ / 4 So to have a correct way to represent this, the QUAD should be broken in to two triangles. like this (for example): 2 / \ / \ 1--------3 \ / \ / 4 In this case the Surface (triangles) Normals are NOT Parallel. I think this error should be prevented, but the real error is in the DAT file, there is the source of the problem. Bad Conception. Preventing this error, may prevent a possible crash. Hope this helps. Sorry for the ascii art. By the way > 1. Two pairs of points (IE: (A,B,C) to (X,Y,Z) make a vertex. NOTE: We're > talking 3d here so we need 3 points for each end of a pair otherwise our Two pairs of points, make 4 points. And 2 points make a line, or an edge. ;) Correct me if I am wrong. Rui Martins ************************************************************************* From: LEGO-style Computer Aided Design [mailto:L-CAD@LISTSERV.UH.EDU] On Behalf Of Leonardo Zide Sent: 20. juni 1998 14:58 To: L-CAD@LISTSERV.UH.EDU Subject: Re: LDraw and quads Wow ! Now we're going to scare half of the subscribers with this 3D talk. :) > Subject: Re: LDraw and quads > Date: Thu, 18 Jun 1998 10:29:51 +0200 > From: "Lars C. Hassing" <lch@CCI.DK> > > To Leonardo Zide <leonardo@CENTROIN.COM.BR> > and Jeffrey N Findley <jeffnf@JUNO.COM>: > > I think that both of your algorithms are wrong. They do not cover all > cases and may even produce "false alarms". Here is what I did: <snip> > I hope that you can follow what I mean from the very short description > and the code excerpt. > Please make any comments. Thanks for the code, I'll take a look and see if it's better than mine later.I haven't found any piece that had problems using my simplified version so far. > Best regards from Århus, Denmark (only 90 km from Billund :-) You said that just to make me jealous ? :) > Subject: Re: LDraw and quads > Date: Thu, 18 Jun 1998 15:09:50 +0100 > From: Rui Martins <Rui.Martins@INESC.PT> > > You are confusing QUADS, which are only 4 sided polygons, with quads, as > in <x,y,z,w> which are normalized coordinates. > The last ones are used by the rasterization program, the user never gets > to see them. > QUADS, its the Ldraw command which starts with the number (4), > meanning a polygon with for sides. You're right. Saved me a lot of typing... :) > The problems beeing discussed are related to implementation issues, since > its common to define a polygon with a certain winding, clock > wise or Counter clock wise. So that the Side of the polygon that is to be > seen can be determined. > Just imagine 4 points, now in what ways can we combine them. > Ex. > 1---2 1--4 1---4 > | | \/ | | > | | /\ | | > 4---3 3--2 2---3 > > C-W wrong C-C-W I think we should also define a certain order to the faces, they all should be CW or CCW. That way the programs could skip the faces that are not facing the user (backfaces), after converting some parts to CW direction and testing them with LeoCAD, I got a 30% speed increase. Jacob, do you have plans to make LDraw2 remove the backfaces ? ************************************************************************* From: LEGO-style Computer Aided Design [mailto:L-CAD@LISTSERV.UH.EDU] On Behalf Of Jeffrey N Findley Sent: 20. juni 1998 16:37 To: L-CAD@LISTSERV.UH.EDU Subject: Re: LDraw and quads On Sat, 20 Jun 1998 09:58:06 -0300 Leonardo Zide <leonardo@CENTROIN.COM.BR> writes: > Wow ! Now we're going to scare half of the subscribers with this 3D > talk. :) > > > I think we should also define a certain order to the faces, they all > should be CW or CCW. That way the programs could skip the faces that > are > not facing the user (backfaces), after converting some parts to CW > direction and testing them with LeoCAD, I got a 30% speed increase. > Jacob, do you have plans to make LDraw2 remove the backfaces ? I know I'm not Jacob, but I thought I'd throw in a comment. If we were to require that faces (triangles and quads) are drawn with the points in the correct order, doesn't this mean that we'd have to modify some (many?) of the original parts to make them conform to the new standard? This breaks upwards compatability with LDraw and forces us to make changes to James' parts (which would require permission). Something to consider. Jeff -- Doesn't everyone want CATS? Not cats silly, Cheap Access To Space! ************************************************************************* From: LEGO-style Computer Aided Design [mailto:L-CAD@LISTSERV.UH.EDU] On Behalf Of Jeffrey N Findley Sent: 20. juni 1998 17:33 To: L-CAD@LISTSERV.UH.EDU Subject: Re: LDraw and quads On Thu, 18 Jun 1998 10:29:51 +0200 "Lars C. Hassing" <lch@CCI.DK> writes: > To Leonardo Zide <leonardo@CENTROIN.COM.BR> > and Jeffrey N Findley <jeffnf@JUNO.COM>: > > I think that both of your algorithms are wrong. They do not cover all > cases and may even produce "false alarms". Here is what I did: > > You have three vertices 0, 1 and 2. Where is the fourth vertex 3 > located ? > If 3 is in I (the most common case) you have a quad which can be > divided > into two triangles by the diagonal 02. The quad may be either convex > (if > 3 is in the area below V) or concave. > If 3 is in III or IV you have a bow-tie error and you may choose a new > sequence of vertices. > If 3 is in II or V you have a concave quad which can be divided > into two triangles by the diagonal 13. > > (PLEASE USE A MONOSPACED FONT) > > \ / > \ II / > \ / > \ / > \ / > III 1 IV > / \ > / \ > / \ > / V \ > / \ > -------0-----------2-------- > . . > . I . > . . The last case above is one way to handle this case, but I don't believe that this is the way LDraw actually draws the quad. From what I understand, LDraw just does a fill between the four points after they're projected onto the screen. This means that if you can never draw a concave quad. To prove this to myself, I created a short test file. To see the behavior for yourself, just try the following .dat file in LDraw. The comments contain viewing help. In each of the quads, I've added the outline of the first three points in black to help visualize what happens by adding the fourth point in different locations. Jeff -- Doesn't everyone want CATS? Not cats silly, Cheap Access To Space! <begin attached .dat file, use monospaced font to view embedded ascii art> o FILE quadtest.dat 0 Jeffrey N. Findley 0 Test .dat file to show behavior of quads in LDraw 0 Best viewed at 300% with Front view (I used ldl) 0 0 Baseline triangle 0 0 0-------1 0 \ / 0 \ / 0 \ / 0 2 0 3 7 0 -14 0 10 -14 0 5 -7 0 2 0 0 -14 0 10 -14 0 2 0 10 -14 0 5 -7 0 2 0 0 -14 0 5 -7 0 0 0 Now draw quads with last point in each of six quadrants defined by 0 the infinite lines which a portion of is used in the baseline triangles: 0 0 \ / 0 I \ II / III 0 \ / 0 \ / 0 -----------------0-------1----------------- 0 \ / 0 \ / 0 VI \ / IV 0 2 0 / \ 0 / \ 0 / \ 0 / V \ 0 / \ 0 0 0 Quad with fourth point in quadrant I 4 7 -90 10 0 -80 10 0 -85 17 0 -97 7 0 2 0 -90 10 0 -80 10 0 2 0 -80 10 0 -85 17 0 2 0 -90 10 0 -85 17 0 0 0 Quad with fourth point in quadrant II 4 7 -60 10 0 -50 10 0 -55 17 0 -55 3 0 2 0 -60 10 0 -50 10 0 2 0 -50 10 0 -55 17 0 2 0 -60 10 0 -55 17 0 0 0 Quad with fourth point in quadrant III 4 7 -30 10 0 -20 10 0 -25 17 0 -13 7 0 2 0 -30 10 0 -20 10 0 2 0 -20 10 0 -25 17 0 2 0 -30 10 0 -25 17 0 0 0 Quad with fourth point in quadrant IV 4 7 10 10 0 20 10 0 15 17 0 23 16 0 2 0 10 10 0 20 10 0 2 0 20 10 0 15 17 0 2 0 10 10 0 15 17 0 0 0 Quad with fourth point in quadrant V 4 7 50 10 0 60 10 0 55 17 0 55 24 0 2 0 50 10 0 60 10 0 2 0 60 10 0 55 17 0 2 0 50 10 0 55 17 0 0 0 Quad with fourth point in quadrant VI 4 7 90 10 0 100 10 0 95 17 0 87 16 0 2 0 90 10 0 100 10 0 2 0 100 10 0 95 17 0 2 0 90 10 0 95 17 0 ************************************************************************* From: LEGO-style Computer Aided Design [mailto:L-CAD@LISTSERV.UH.EDU] On Behalf Of Jeffrey N Findley Sent: 20. juni 1998 19:25 To: L-CAD@LISTSERV.UH.EDU Subject: Re: LDraw and quads Another reply to Lars' message since it really got me thinking. :-) After creating the test file I just sent to the list, I decided to run the quads in that file through my lines program. The input file was (one triangle and 7 different quads): 0 FILE quadtst2.dat 3 7 0 -14 0 10 -14 0 5 -7 0 4 7 -90 10 0 -80 10 0 -85 17 0 -97 7 0 4 7 -60 10 0 -50 10 0 -55 17 0 -55 3 0 4 7 -30 10 0 -20 10 0 -25 17 0 -13 7 0 4 7 10 10 0 20 10 0 15 17 0 23 16 0 4 7 50 10 0 60 10 0 55 17 0 55 24 0 4 7 90 10 0 100 10 0 95 17 0 87 16 0 4 7 0 46 0 10 46 0 5 39 0 5 43 0 The output file was wrong, so I fixed the code: else if ( pcLine[0] == '4' ) { nPoint = 4; sscanf(pcLine, "%d %d %lf %lf %lf %lf %lf %lf %lf %lf %lf %lf %lf %lf", &iType, &iColor, &afPoint[0][0], &afPoint[0][1], &afPoint[0][2], &afPoint[1][0], &afPoint[1][1], &afPoint[1][2], &afPoint[2][0], &afPoint[2][1], &afPoint[2][2], &afPoint[3][0], &afPoint[3][1], &afPoint[3][2]); /* * Define three imaginary lines going from the first point * to each of the other points. */ afLine[0][0] = afPoint[1][0] - afPoint[0][0]; afLine[0][1] = afPoint[1][1] - afPoint[0][1]; afLine[0][2] = afPoint[1][2] - afPoint[0][2]; afLine[1][0] = afPoint[2][0] - afPoint[0][0]; afLine[1][1] = afPoint[2][1] - afPoint[0][1]; afLine[1][2] = afPoint[2][2] - afPoint[0][2]; afLine[2][0] = afPoint[3][0] - afPoint[0][0]; afLine[2][1] = afPoint[3][1] - afPoint[0][1]; afLine[2][2] = afPoint[3][2] - afPoint[0][2]; /* Determine the length of each line */ afLen[0] = vect_mag(afLine[0]); afLen[1] = vect_mag(afLine[1]); afLen[2] = vect_mag(afLine[2]); /* * Define three angles between the first and second line, * the first and third line, and the second and third line. */ afAng[0] = acos(dot_product(afLine[0], afLine[1]) / (afLen[0] * afLen[1])); afAng[1] = acos(dot_product(afLine[0], afLine[2]) / (afLen[0] * afLen[2])); afAng[2] = acos(dot_product(afLine[1], afLine[2]) / (afLen[1] * afLen[2])); /* * If the third angle is greater than the other two, then * the first line (first and second points) is one of the * diagonals of the quad. */ if ( afAng[0] < afAng[2] && afAng[1] < afAng[2] ) { ppzPoint[0] = add_point(ppzFirstPoint, &afPoint[0][0]); ppzPoint[1] = add_point(ppzFirstPoint, &afPoint[2][0]); ppzPoint[2] = add_point(ppzFirstPoint, &afPoint[1][0]); ppzPoint[3] = add_point(ppzFirstPoint, &afPoint[3][0]); } else { /* The first line is along an outer edge */ ppzPoint[0] = add_point(ppzFirstPoint, &afPoint[0][0]); ppzPoint[1] = add_point(ppzFirstPoint, &afPoint[1][0]); /* * If the angle between the first and second lines is * less than the angle between the second and third lines, * then the points are already in order */ if (afAng[0] < afAng[1]) { ppzPoint[2] = add_point(ppzFirstPoint, &afPoint[2][0]); ppzPoint[3] = add_point(ppzFirstPoint, &afPoint[3][0]); } else { /* The last two points need to be reversed */ ppzPoint[2] = add_point(ppzFirstPoint, &afPoint[3][0]); ppzPoint[3] = add_point(ppzFirstPoint, &afPoint[2][0]); } } } The output file from this code I consider acceptable: 0 FILE quadtst3.dat 3 7 0 -14 0 10 -14 0 5 -7 0 4 7 -90 10 0 -80 10 0 -85 17 0 -97 7 0 4 7 -60 10 0 -50 10 0 -55 17 0 -55 3 0 4 7 -30 10 0 -20 10 0 -25 17 0 -13 7 0 4 7 10 10 0 20 10 0 15 17 0 23 16 0 4 7 50 10 0 60 10 0 55 17 0 55 24 0 4 7 90 10 0 100 10 0 95 17 0 87 16 0 4 7 0 46 0 10 46 0 5 39 0 5 43 0 0 0 Begin block of lines from lines.exe 2 8 5 -7 0 0 -14 0 2 8 10 -14 0 0 -14 0 2 8 10 -14 0 5 -7 0 2 8 -90 10 0 -97 7 0 2 8 -80 10 0 -90 10 0 2 8 -80 10 0 -85 17 0 2 8 -85 17 0 -97 7 0 2 8 -55 3 0 -60 10 0 2 8 -55 17 0 -60 10 0 2 8 -50 10 0 -55 17 0 2 8 -50 10 0 -55 3 0 2 8 -13 7 0 -30 10 0 2 8 -25 17 0 -30 10 0 2 8 -20 10 0 -25 17 0 2 8 -13 7 0 -20 10 0 2 8 15 17 0 10 10 0 2 8 20 10 0 10 10 0 2 8 23 16 0 20 10 0 2 8 23 16 0 15 17 0 2 8 55 24 0 50 10 0 2 8 60 10 0 50 10 0 2 8 60 10 0 55 17 0 2 8 55 24 0 55 17 0 2 8 90 10 0 87 16 0 2 8 100 10 0 90 10 0 2 8 100 10 0 95 17 0 2 8 95 17 0 87 16 0 2 8 5 39 0 0 46 0 2 8 10 46 0 0 46 0 2 8 10 46 0 5 43 0 2 8 5 43 0 5 39 0 0 End block of lines from lines.exe 0 If you look at the output file in LDraw, you'll notice that I do not handle the cases where one of the points is inside of a triangle defined by the other three points. This could either be considered a triangle by eliminating the inside point, or it could be considered a concave quad as Lars suggests. However, to treat this quad as concave, which of the edges of the outer triangle would the user want to delete and instead connect to the central point? In the end, I ignore this case (partly bcause LDraw seems to always draw them as triangles). The user will notice I ignore this case because my program will output bad edge lines which will need to be addressed by replacing the quad with one or two triangles, or the edge lines could be edited by hand (not recommended since I currently just dump them all out at the end). Anyway, anyone should feel free to use the code included in this mssage. I'd also encourage anyone developing programs that read .dat files to keep a copy of the .dat file in this message to use as a test. By the way Lars, thanks for the suggestion. It got me thinking more about quads and prompted me to write a proper test for my code based on your ASCII drawings. Even though I chose to ignore the concave case (since LDraw does too), your suggestions were helpful and I will keep your code example around since I think it could be useful to me in the future. I'm still not handling non-planar quads, but considering how LDraw behaves, I think they'll end up looking like tetrahedrons. Although Lars is less than 90km from Billund (of which I am definately jealous), I live about the same distance from the USAF Museum in Dayton, Ohio. It's pretty cool if you're into military aircraft and spacecraft like I am. :-) Thanks, Jeff -- Doesn't everyone want CATS? Not cats silly, Cheap Access To Space! ************************************************************************* From: LEGO-style Computer Aided Design [mailto:L-CAD@LISTSERV.UH.EDU] On Behalf Of Leonardo Zide Sent: 21. juni 1998 14:54 To: L-CAD@LISTSERV.UH.EDU Subject: Re: LDraw and quads > Subject: Re: LDraw and quads > Date: Sat, 20 Jun 1998 10:36:40 -0400 > From: Jeffrey N Findley <jeffnf@JUNO.COM> > > I know I'm not Jacob, but I thought I'd throw in a comment. If we were > to require that faces (triangles and quads) are drawn with the points in > the correct order, doesn't this mean that we'd have to modify some > (many?) of the original parts to make them conform to the new standard? > This breaks upwards compatability with LDraw and forces us to make > changes to James' parts (which would require permission). > > Something to consider. We would have to modify all parts to make them correct. That's something I've been doing for some time, I wrote a small program to help me fix the parts and I've fixed about 60 parts (all bricks, tiles and plates). We only have to change the order of the points, so the files are still 100% compatible with the current version of LDraw. As we would be just fixing some of James parts, I don't think there's any problem doing it (for example, on the last update I sent fixes to 1.DAT and 2.DAT). And the speed increase is worth the effort... :) What do the rest of you think ? Any volunteers to help fix the parts ? ************************************************************************* From: Lars C. Hassing Sent: 24. juni 1998 17:38 To: L-CAD@LISTSERV.UH.EDU Subject: Re: LDraw and quads > Subject: Re: LDraw and quads > Date: Sat, 20 Jun 1998 09:58:06 -0300 > From: Leonardo Zide <leonardo@CENTROIN.COM.BR> > > Wow ! Now we're going to scare half of the subscribers with this 3D > talk. :) > > > Subject: Re: LDraw and quads > > Date: Thu, 18 Jun 1998 10:29:51 +0200 > > From: "Lars C. Hassing" <lch@CCI.DK> > > > > To Leonardo Zide <leonardo@CENTROIN.COM.BR> > > and Jeffrey N Findley <jeffnf@JUNO.COM>: > > > > I think that both of your algorithms are wrong. They do not cover all > > cases and may even produce "false alarms". Here is what I did: > > <snip> > > > I hope that you can follow what I mean from the very short description > > and the code excerpt. > > Please make any comments. > > Thanks for the code, I'll take a look and see if it's better than mine > later.I haven't found any piece that had problems using my simplified > version so far. I believe that your simplified version fails to complain about this rectangle: (0,1) 3-------1 (2,1) | | (0,0) 0-------2 (2,0) You are welcome to use my code. You then also get the choice of making concave quads into triangles (by removing the identified included point), or keeping the concave polygon (and picking the correct diagonal). I don't think that performance is much of an issue here, as this test happens only during loading of parts. But anyway I think that my algorithm is faster than Jeff's (some more adds/muls but no sqrt/acos). > > > Best regards from Århus, Denmark (only 90 km from Billund :-) > > You said that just to make me jealous ? :) Yes, couldn't resist :-) > > > > Subject: Re: LDraw and quads > > Date: Thu, 18 Jun 1998 15:09:50 +0100 > > From: Rui Martins <Rui.Martins@INESC.PT> > > > > You are confusing QUADS, which are only 4 sided polygons, with quads, as > > in <x,y,z,w> which are normalized coordinates. > > The last ones are used by the rasterization program, the user never gets > > to see them. > > QUADS, its the Ldraw command which starts with the number (4), > > meanning a polygon with for sides. > > You're right. Saved me a lot of typing... :) True. > > > The problems beeing discussed are related to implementation issues, since > > its common to define a polygon with a certain winding, clock > > wise or Counter clock wise. So that the Side of the polygon that is to be > > seen can be determined. > > Just imagine 4 points, now in what ways can we combine them. > > Ex. > > 1---2 1--4 1---4 > > | | \/ | | > > | | /\ | | > > 4---3 3--2 2---3 > > > > C-W wrong C-C-W > > I think we should also define a certain order to the faces, they all > should be CW or CCW. That way the programs could skip the faces that are > not facing the user (backfaces), after converting some parts to CW > direction and testing them with LeoCAD, I got a 30% speed increase. > Jacob, do you have plans to make LDraw2 remove the backfaces ? See below next mail. > Subject: Re: LDraw and quads > Date: Sun, 21 Jun 1998 09:53:30 -0300 > From: Leonardo Zide <leonardo@CENTROIN.COM.BR> > > > Subject: Re: LDraw and quads > > Date: Sat, 20 Jun 1998 10:36:40 -0400 > > From: Jeffrey N Findley <jeffnf@JUNO.COM> > > > > I know I'm not Jacob, but I thought I'd throw in a comment. If we were > > to require that faces (triangles and quads) are drawn with the points in > > the correct order, doesn't this mean that we'd have to modify some > > (many?) of the original parts to make them conform to the new standard? > > This breaks upwards compatability with LDraw and forces us to make > > changes to James' parts (which would require permission). > > > > Something to consider. > > We would have to modify all parts to make them correct. That's > something I've been doing for some time, I wrote a small program to help > me fix the parts and I've fixed about 60 parts (all bricks, tiles and > plates). Did you submit these ? > We only have to change the order of the points, so the files are still > 100% compatible with the current version of LDraw. As we would be just > fixing some of James parts, I don't think there's any problem doing it > (for example, on the last update I sent fixes to 1.DAT and 2.DAT). And > the speed increase is worth the effort... :) > What do the rest of you think ? Any volunteers to help fix the parts ? I think it would be a perceptible advantage for any user of an interactive application if all/most/many parts were checked/modified. But it is a huge task. Is it possible to get some computer assistance ? Don't you need to add a line like "0 CW-CHECKED Leonardo Zide 19980624" to know whether a .dat file is CW-safe or not ? /Lars ************************************************************************* From: Lars C. Hassing Sent: 24. juni 1998 18:17 To: L-CAD@LISTSERV.UH.EDU Subject: Re: LDraw and quads > Subject: Re: LDraw and quads > Date: Sat, 20 Jun 1998 13:24:58 -0400 > From: Jeffrey N Findley <jeffnf@JUNO.COM> > > Another reply to Lars' message since it really got me thinking. :-) I'll take that as a compliment :-) > (snip) > > The output file was wrong, so I fixed the code: > > (snip) > /* > * If the angle between the first and second lines is > * less than the angle between the second and third lines, ^^^^^^ you mean first, don't you? > * then the points are already in order > */ Jeff, I think you've got the resequencing right this time. > > If you look at the output file in LDraw, you'll notice that I do not > handle the cases where one of the points is inside of a triangle defined > by the other three points. This could either be considered a triangle by > eliminating the inside point, or it could be considered a concave quad as > Lars suggests. However, to treat this quad as concave, which of the > edges of the outer triangle would the user want to delete and instead > connect to the central point? The sequence of the four points already defines a concave polygon. > In the end, I ignore this case (partly > bcause LDraw seems to always draw them as triangles). My algorithm identifies the inside points (Ia:0 Ic:2 II:1 V:3) so you could choose to do as LDraw. > The user will notice I ignore this case because my program will output > bad edge lines which will need to be addressed by replacing the quad with > one or two triangles, or the edge lines could be edited by hand (not > recommended since I currently just dump them all out at the end). I too think that these quads are problem-quads. It would be nice if we could agree that quads should be 1) coplanar 2) convex 3) CW-defined and then fix all parts that have problem-quads. /Lars ************************************************************************* From: LEGO-style Computer Aided Design [mailto:L-CAD@LISTSERV.UH.EDU] On Behalf Of Rui Martins Sent: 24. juni 1998 19:35 To: L-CAD@LISTSERV.UH.EDU Subject: Re: LDraw and quads On Wed, 24 Jun 1998, Lars C. Hassing wrote: > I too think that these quads are problem-quads. > It would be nice if we could agree that quads should be > 1) coplanar > 2) convex > 3) CW-defined > and then fix all parts that have problem-quads. > /Lars I agree with the last lines. One thing that could be done easily, is a program to test and possibly certify if a specific .DAT file has any of these errors. It's easyer to detect the errorss than correcting them. If this program was available, every one could test there home made .DAT files (parts) to minimize or eliminate these errors. Rui Martins ************************************************************************* From: LEGO-style Computer Aided Design [mailto:L-CAD@LISTSERV.UH.EDU] On Behalf Of Joshua Delahunty Sent: 25. juni 1998 02:54 To: L-CAD@LISTSERV.UH.EDU Subject: Re: LDraw and quads > > It would be nice if we could agree that quads should be > > 1) coplanar > > 2) convex > > 3) CW-defined > > and then fix all parts that have problem-quads. > > > But without a different piece of software, what difference does it make? > LDraw is going to run the same, no matter what order the points are in. LeoCAD works now. LDRAW II is on the way. Knowing what a fascinating project this is, there will no-doubt be more. (requoted) > LDraw is going to run the same, no matter what order the points are in. This is a big point in the favor of this fix-it project. The gains are many for future software, no drawbacks exist for folks still using current software. Sure, it's a major drawback that parts authors might be distracted from new parts while fixing old, but performance gains from backface culling certainly help outweigh this criterion. -- joshua ************************************************************************* From: LEGO-style Computer Aided Design [mailto:L-CAD@LISTSERV.UH.EDU] On Behalf Of Jeffrey N Findley Sent: 25. juni 1998 07:15 To: L-CAD@LISTSERV.UH.EDU Subject: Re: LDraw and quads On Wed, 24 Jun 1998 16:16:31 +0200 "Lars C. Hassing" <lch@CCI.DK> writes: > > It would be nice if we could agree that quads should be > 1) coplanar > 2) convex > 3) CW-defined > and then fix all parts that have problem-quads. I agree. When we say clockwise defined, are we saying that the quad is only drawn if it's points are in clockwise order when projected onto the screen? Just want to be clear. Jeff -- Doesn't everyone want CATS? Not cats silly, Cheap Access To Space! ************************************************************************* From: LEGO-style Computer Aided Design [mailto:L-CAD@LISTSERV.UH.EDU] On Behalf Of Chris Dee Sent: 25. juni 1998 14:47 To: L-CAD@LISTSERV.UH.EDU Subject: Re: LDraw and quads Rui Martins wrote: > On Thu, 25 Jun 1998, Jeffrey N Findley wrote: > > > On Wed, 24 Jun 1998 16:16:31 +0200 "Lars C. Hassing" <lch@CCI.DK> • writes: > > > > > > It would be nice if we could agree that quads should be > > > 1) coplanar > > > 2) convex > > > 3) CW-defined > > > and then fix all parts that have problem-quads. > > > > I agree. When we say clockwise defined, are we saying that the quad • is > > only drawn if it's points are in clockwise order when projected onto • the > > screen? Just want to be clear. > > > > Jeff > > YES. > > Rui Martins I agree with the future benefits of drawing all quads in clockwise order, but admit that I have not followed this scheme with all my new parts (its so easy to reflect symetrical parts across the x-axis, and reverse the sequence). I suggest we add a line in the header of new parts, to indicate that they are *backface culling complient* or something similar. Terry, could you possibly suggest something? ChrisD ______________________________________________________ Get Your Private, Free Email at http://www.hotmail.com ************************************************************************* From: LEGO-style Computer Aided Design [mailto:L-CAD@LISTSERV.UH.EDU] On Behalf Of K and S Bliss Sent: 25. juni 1998 02:35 To: L-CAD@LISTSERV.UH.EDU Subject: Backface culling Backface culling (not drawing sides facing away) is a big performance boost. But an even bigger one is to only translate each element once. There are a few certain items which are drawn litterally hundreds of times in an LDraw rendering. Like studs. Typically, 99% of the studs in a rendering face the same direction. This should be rendered once, and bitblt'ed hundreds of times. Steve ************************************************************************* From: Lars C. Hassing Sent: 25. juni 1998 19:05 To: L-CAD@LISTSERV.UH.EDU Subject: Re: Backface culling > From: K and S Bliss <blisses@WORLDNET.ATT.NET> > Date: Wed, 24 Jun 1998 20:34:37 -0400 > Subject: Backface culling > > Backface culling (not drawing sides facing away) is a big performance boost. > But an even bigger one is to only translate each element once. There are a > few certain items which are drawn litterally hundreds of times in an LDraw > rendering. Like studs. Typically, 99% of the studs in a rendering face the > same direction. This should be rendered once, and bitblt'ed hundreds of > times. > > Steve This is only true for parallel projections (orthographic/isometric) and only without reflections, shadows, transparency etc. In perspective projections all studs look (slightly) different. /Lars ************************************************************************* From: LEGO-style Computer Aided Design [mailto:L-CAD@LISTSERV.UH.EDU] On Behalf Of Leonardo Zide Sent: 25. juni 1998 19:53 To: L-CAD@LISTSERV.UH.EDU Subject: Re: LDraw and quads > Subject: Re: LDraw and quads > Date: Wed, 24 Jun 1998 15:37:47 +0200 > From: "Lars C. Hassing" <lch@CCI.DK> > > I believe that your simplified version fails to complain about this rectangle: > > (0,1) 3-------1 (2,1) > | | > (0,0) 0-------2 (2,0) > > You are welcome to use my code. You then also get the choice of making > concave quads into triangles (by removing the identified included point), > or keeping the concave polygon (and picking the correct diagonal). > I don't think that performance is much of an issue here, as this test > happens only during loading of parts. But anyway I think that my algorithm > is faster than Jeff's (some more adds/muls but no sqrt/acos). > > > You said that just to make me jealous ? :) > Yes, couldn't resist :-) Ok, let's see... I just have to cross the street to go to the beach. :) > > We would have to modify all parts to make them correct. That's > > something I've been doing for some time, I wrote a small program to help > > me fix the parts and I've fixed about 60 parts (all bricks, tiles and > > plates). > Did you submit these ? No, I had to create a new version of the primitives (the files on the "\P" dir), and as it would take a some discussion, I didn't. But they are only available on the latest LeoCAD library. > I think it would be a perceptible advantage for any user of an interactive > application if all/most/many parts were checked/modified. But it is a > huge task. Is it possible to get some computer assistance ? I've written a simple program to help me. It displays a part with all faces that are correct in green and the wrong ones in red, I use the TAB key to go through all faces and press SPACE to flip the order of the points. > Don't you need to add a line like "0 CW-CHECKED Leonardo Zide 19980624" > to know whether a .dat file is CW-safe or not ? I just fixed a few files for test with LeoCAD and as it has an option to turn backface culling on/off I didn't add anything. > I too think that these quads are problem-quads. > It would be nice if we could agree that quads should be > 1) coplanar > 2) convex > 3) CW-defined > and then fix all parts that have problem-quads. I agree with that. > Subject: Backface culling > Date: Wed, 24 Jun 1998 20:34:37 -0400 > From: K and S Bliss <blisses@WORLDNET.ATT.NET> > > Backface culling (not drawing sides facing away) is a big performance boost. > But an even bigger one is to only translate each element once. There are a > few certain items which are drawn litterally hundreds of times in an LDraw > rendering. Like studs. Typically, 99% of the studs in a rendering face the > same direction. This should be rendered once, and bitblt'ed hundreds of > times. But that would be a problem for the Z buffer, wouldn't it ? ************************************************************************* From: LEGO-style Computer Aided Design [mailto:L-CAD@LISTSERV.UH.EDU] On Behalf Of Joshua Delahunty Sent: 25. juni 1998 21:16 To: L-CAD@LISTSERV.UH.EDU Subject: Re: LDraw and quads > Date: Thu, 25 Jun 1998 22:30:07 +1000 > From: Geoffrey Hyde <ghyde@FASTINTERNET.NET.AU> > > On Thu, 25 Jun 1998, Jeffrey N Findley wrote: > > > > It would be nice if we could agree that quads should be > > > > 1) coplanar > > > > 2) convex > > > > 3) CW-defined > > > > and then fix all parts that have problem-quads. > > > On Wed, 24 Jun 1998 16:16:31 +0200 "Lars C. Hassing" <lch@CCI.DK> wrote: > > > I agree. When we say clockwise defined, are we saying that the quad is > > > only drawn if it's points are in clockwise order when projected onto • the > > > screen? Just want to be clear. > > > > > > Jeff Rui Martins: > > YES. Geoffrey Hyde: > One question. If your quad drawn on-screen has been rotated 180 degrees, > and it's points are in an anticlockwise direction, relative to the screen, > does it still get drawn or not? It does not. That's exactly what's being done in backface culling. A routine "walks" through the data structure of faces (polygons, objects) to be shown (or walks through all of them as it displays them), and it avoids pointless calculations by "discarding" from the list of items to draw those items that are facing away from the viewer (and so don't contribute to the current view). IF the points are all generated consistently (this can also work for CCW defined polys -- they just all have to match), then it's a quick calculation to determine whether a face is visible or not when the time comes to display it. This series of calculations is to be done each time the viewpoint changes, so the faces aren't permanently discarded, they're just discarded for the current display of information. This doesn't just discard large flat areas, either. Half of EVERY stud doesn't get drawn this way, as the faces on the back aren't drawn, all the pie slices of the top aren't drawn if you view from below, etc. Leonardo is indicating that he's getting a 30% increase in speed when using backface culling -- that's pretty darned significant. While most LDRAW/DOS users won't notice much of an advantage to that kind of increase (since the viewpoint isn't changing too often), the help this will provide to current (LeoCAD) and perhaps future versions of the LDRAW application (LDRAW II, etc.) is immense, as mouse-based view rotation, as in high-end CAD packages, changes the view constantly as the mouse is moved. LeoCAD supports this style of mouse-based rotation now, but the horsepower required to do this without backface culling makes LeoCAD (arguably) unusable on lower-end machines. A 30% increase would make this sort of usability accessible to many more people (for that matter, it will make it EVEN better on big-guns machines, allowing extra speed for features like brick snap-to, auto-alignment, and perhaps even physical object manipulation (imagine turning the cross axle and having the package "figure out" to turn the gear that's been placed on the axle automatically, and having that automatically turn another gear that's meshed with it). I apologize for making this so long, but I've supported Leonardo in his quest for BC-compliant parts for awhile now, and think it's a really important idea. Then again, I'm a LeoCAD user rather than an LDRAW user, so I'm obviously biased. :-) -- joshua ************************************************************************* From: LEGO-style Computer Aided Design [mailto:L-CAD@LISTSERV.UH.EDU] On Behalf Of Leonardo Zide Sent: 26. juni 1998 14:54 To: L-CAD@LISTSERV.UH.EDU Subject: Re: LDraw and quads Subject: Re: Voting page UP Date: Thu, 25 Jun 1998 01:14:54 -0400 From: Jeffrey N Findley <jeffnf@JUNO.COM> > Actually, this isn't so stupid. There are cases in 3D where it's > difficult (impossible) to say which way the hose will bend. One such > case is starting with the hose straight, then pushing the ends a little > bit closer together (say the length of a 2 stud brick) while keeping the > center lines of the ends in a straight line. It's easy to see the hose > will start straight, curve up and over into a hump, then end up straight > again, but you can't predict exactly where the hump will be. The hump is > still free to rotate about the axis that runs between the two ends. Actually I think you can, because of precision errors you probably won't have a 100% centered force so you will be able to calculate the direction of the hump. I don't know the name of that in english, but that's a common engineering problem. > Still, in ambiguous cases, you could simply ask the user which way to put > the curve. > > Anyway, it's a cool idea worth further thought, but it's not exactly a > simple problem to solve. Now I know where I can use what I'm learning at the university... :) > Subject: Re: LDraw and quads > Date: Thu, 25 Jun 1998 12:16:28 -0700 > From: Joshua Delahunty <dulcaoin@ALUMNI.CSE.UCSC.EDU> <...> Thanks for explaining it all... I'm subscribed to the digest version of the list so I only got the messages now. > This doesn't just discard large flat areas, either. Half of EVERY > stud doesn't get drawn this way, as the faces on the back aren't > drawn, all the pie slices of the top aren't drawn if you view from > below, etc. Actually only half of every *piece* gets drawn, as all objects are solid (closed) there will always be a backface for each front face. Subject: Re: LDraw and quads Date: Thu, 25 Jun 1998 18:51:12 -0400 From: K and S Bliss <blisses@WORLDNET.ATT.NET> > > But that would be a problem for the Z buffer, wouldn't it ? > > I don't follow that one. How would you update the Z buffer after bitblting the image ? Besides that, how would you resize the studs ? If you use the same image for a stud that is close and for a stud that is away from the user things wouldn't look good on an perspective projection. ************************************************************************* From: LEGO-style Computer Aided Design [mailto:L-CAD@LISTSERV.UH.EDU] On Behalf Of Joshua Delahunty Sent: 26. juni 1998 19:47 To: L-CAD@LISTSERV.UH.EDU Subject: Backface culling (Re: LDraw and quads) (LONG) > ChrisD wrote > > I agree with the future benefits of drawing all quads in clockwise > > order, but admit that I have not followed this scheme with all my new > > parts (its so easy to reflect symetrical parts across the x-axis, and > > reverse the sequence). I suggest we add a line in the header of new > > parts, to indicate that they are *backface culling complient* or > > something similar. Terry, could you possibly suggest something? > > > I read all these posts, totally clueless as to what your talking about. > As authors, if you want to discuss this amongst yourselves and make a > decision, fine. Adding a line to parts is no problem. For uniformity, I > just ask that it come after the first four lines. If you're confused, Terry, others might be too. I'll try to explain it from the beginning. I don't think you've caught on to the magnitude of what's being discussed. I'll try to keep it as non-technical, non-mathie as possible (because that's how *I* like to think of it anyway), so please noone jump on me for simplifying the terminology unless I REALLY mess up a concept. ---- Summary ---- What's being discussed here is nearly a wholesale change to the entire set of LDRAW elements -- not adjustment of any values, or moving around of lines within parts files, but rather the reordering of the different points (vertices) that make up the "corners" of the different surfaces/faces/polygons/triangles/quads that make up the different elements. This change will not benefit LDRAW per se, but it will make use of the elements more universal and it will improve the drawing speed of the elements in interactive 3D packages (such as LeoCAD). Paul Gyugyi once asked about this as well, when he wanted to convert LDRAW elements to some other form. This _is_ important to several people, at least. ---- Discussion ---- Here's how it works: (Note that I'm not sure about whether LDRAW supports triangles and quads[1], so I'm discussing a little bit generically) When the computer draws three dimensional objects, those objects are often drawn using either triangles or quads[1] to define the different "facets" on an object. These shapes work really well as they're easy to do "fast"[2] math on, they draw quickly, and if you make them small enough, you can "fake" the look of nearly any shaped surface, even curved surfaces When a triangle or a quad is drawn in the computer, one of the (optional but important) optimization steps that a program can take is known as "backface culling". This is skipping drawing of any polygon (triangle or quad) that faces "away" from the viewer, since to draw those would be a waste of time, as you can prove (through geometrical means, knowing how all of the elements are constructed) that all of these polygons are invisible from the current viewpoint (they're all obstructed by other polygons that ARE pointed towards the viewer). The polygons that are pointed "away" are known as backfaces, and this process "culls" them out of the "list" of polygons that the computer draws each time it does a redraw. This can really make a difference in the redraw time of 3D objects, and nearly every package is going to use this technique. The trick here is that one needs a quick way, mathematically, to tell whether a given polygon faces the viewer or not. As it turns out, there's a very simple means for doing this. Given the values for the first three points in the polygon (that's why this works for either triangles or quads), you can calculate a vector (think of this as an arrow in space, if you like) that will point in the direction the polygon is "facing". _However_, in order for this calculation to work, the points have to be in a certain order. (You also need all the points to be set up so the object is "flat" -- see note 1 below about coplanar polygons). If they're not in the right order, the "arrow" will be pointing the wrong way! That means you might have things drawn that you don't want (which slows things down), or even worse, things will get skipped that are very important to draw. The order we're looking for here is that they're all defined in a clockwise[3] rotation around the center of the polygon when we're looking at it from the "front" or "outside". Let's say that this is the side of a 1x2 brick: Notice that I've defined the polygon in a clockwise (CW) order. The diagrams to the right show other ways it could be defined that are just as good. What matters is that the points are defined in a clockwise "rotation" around the sides of the quad. 1------->2 4------->1 2------->3 ^ | ^ | ^ | | | | | | | | v | v | v 4<-------3 3<-------2 1<-------4 Here are some "bad" quads, that won't work with backface culling that's defined on clockwise rotation (they still might draw fine if the program doesn't try to DO backface culling): 2<-------1 1 3 | ^ ^\ / ^ | | | X | v | |/ \ | 3------->4 4 2 The second quad really breaks the rules of most optimizations, but LDRAW handles it fine since LDRAW simply takes all the "outside" lines of the quad and then fills in the middle. Right now, many (most?) of the LDRAW elements have been defined by creating a polygon, such as the side of the 1x2 brick, and then this is duplicated by copying the same values over again, but changing one of the coordinates (x, y, or z) to "move" that polygon to the other side of the brick. An Example: This is hard to draw in ASCII, but imagine the first diagram I made up there. It points towards you right now (imagine that there's an arrow coming out of the center of it at your forehead). Now try to imagine placing another of those quads about an inch out in front of the screen (perhaps think about holding a cutout piece of cardboard in front of the screen). It's still pointing at your forehead, right? But so's the one that's still on the screen, and it's supposed to be the "back" of the brick, and it's pointing towards you when it should be pointed away from you. Now try to imagine some fellow sitting behind your monitor, facing you. The two polygons are both pointing AWAY from his forehead, when the one that's in the back to you is in the front to him, and SHOULD be pointed towards him. Stop imagining the cardboard, and start with the quad as it appears above, pointing at your forehead. It has an order that looks like 12 34 The back of the brick, in order to work with backface culling, would need to be defined like the first one in the second list 21 34 NOTE: these are examples only, the 1's and 2's don't have to match like this, neither do the 3's and 4's. They only have to follow the same rotation. If the top (1234) points towards your forehead, then the same calculation would indicate that the bottom (2134) points INTO the screen which is what we need. SO; the job being discussed is that pieces need to be fixed so that the arrows that get calculated always point in the correct direction. Part of this job will be made easier because of P\ entries that define sections of a lot of elements. Right now, the same P\ entry might be used for both right and left halves of a piece. The fix is to duplicate the P\ entry, "flip" the rotation on all the polygons, and then fix the pieces that reference the first P\ entry to reference that entry for one side ONLY, and then to also reference the second P\ entry for the rest of that piece. (This P\ business is also why Leonardo hasn't submitted any of his fixes to the library yet -- messing with P\ entries is big-deal stuff around here, no?) ---- Footnotes ---- [1] a quad is an object defined by 4 points representing the "corners" of the object, just like a triangle has 3 points at the "corners" of it. We often maintain that triangles and quads must have "corners" that are _coplanar_, which means they all need to "sit" on the same plane, which basically means they must define a "flat" shape. Quads are often also required to be _convex_, which means that all have to be shaped like bent rectangles, and never have a "Pacman" shape, with a mouth, or have an "hourglass" appearance. [2] Fast math means math that a computer can do very quickly, usually in hardware. This means addition and subtraction are preferred, multiplication and division can be OK, and floating point or transcendental functions (trigonometry, etc.) are out. [3] "So what's so special about clockwise? Does that make the math work?" There's nothing magic about choosing clockwise. We could go with everything being counter-clockwise, instead, it just means all the arrows would be reversed, and we could adjust our logic for that. Most people like to have the arrow pointing "outside", or toward the viewer, so clockwise is most often chosen. By sticking with clockwise, we keep the pieces in their most flexible form for most people to use in other ways. ---- Hope this was helpful to everyone. -- joshua ************************************************************************* From: Jacob Sparre Andersen [mailto:sparre@ALF.NBI.DK] Sent: 25. januar 1999 19:28 To: L-CAD@LISTSERV.UH.EDU Subject: Re: .dat file face orientation [ I'm copying this message to L-CAD for comments. ] Hi Ken, > One question that I have come across is the orientation of > the faces (triangle and quad instructions) in the .dat > file. Are they oriented counterclockwise, clockwise, or > "no guaranteewise"? I'm afraid it's still "no guaranteewise". There will probably be included some sort of identification of the orientation of the faces in the parts files in the future. - But not yet. You could implement a function so 0 FACE CCW in the beginning of a part file identified the following faces in that file as counterclockwise, and 0 FACE CW similarly identified the following faces in that file as clockwise. You would of cause have to accept that any face that appears before a FACE meta-command is "no guaranteewise", and that the FACE meta-commands are limited to exactly the file they appear in. You should also remember that using a CW face with a negative determinant orientation matrix changes it to a CCW face. Implementing a meta-command is the way to get it accepted around here. Play well, Jacob ---------------------------------------------- -- E-mail: Jacob.Sparre.Andersen@risoe.dk -- -- Web...: <URL:http://hugin.risoe.dk/> -- ---------------------------------------------- LDraw FAQ: <URL:http://fys.ku.dk/%7Esparre/LEGO/V%E6rkt%F8j/LDraw-FAQ.html> ************************************************************************* From: Leonardo Zide [mailto:leonardo@CENTROIN.COM.BR] Sent: 3. februar 1999 15:38 To: L-CAD@LISTSERV.UH.EDU Subject: Re: .dat file face orientation Subject: Re: .dat file face orientation Date: Mon, 25 Jan 1999 19:28:13 +0100 From: Jacob Sparre Andersen <sparre@ALF.NBI.DK> > I'm afraid it's still "no guaranteewise". There will probably be > included some sort of identification of the orientation of the faces > in the parts files in the future. - But not yet. There are some parts done by Steve that have a "0 not CW-Compliant" line and some others done by Chris that have "0 CW compliant" line but some of those files do have CCW faces. Only a few parts can have all their faces on the correct direction, some primitives (like BOX5.DAT) have faces with their normals pointing to the inside and to the outside. That makes it impossible to fix those files that use it without editing the primitives. > You should also remember that using a CW face with a negative > determinant orientation matrix changes it to a CCW face. Never tried this, are you sure ? Leonardo ************************************************************************* From: S & K Bliss [mailto:blisses@WORLDNET.ATT.NET] Sent: 4. februar 1999 01:39 To: L-CAD@LISTSERV.UH.EDU Subject: Re: .dat file face orientation Leonardo wrote: > Only a few parts can have all their faces on the correct direction, > some primitives (like BOX5.DAT) have faces with their normals pointing > to the inside and to the outside. That makes it impossible to fix those > files that use it without editing the primitives. If the primitive is non-(C)CW, that doesn't affect the parts that use it. The rendering program must be smart enough to not assume that subfiles have the same CW standing as the parent file. Steve ************************************************************************* From: Jacob Sparre Andersen [mailto:sparre@CATS.NBI.DK] Sent: 4. februar 1999 10:18 To: L-CAD@LISTSERV.UH.EDU Subject: Re: .dat file face orientation Leonardo: First I should clarify that a FACE (C)CW only can/should account for planes _in_ that file. Sub-files (parts and sub-models) should be treated separately because of possible problems with mirroring (negative determinant orientation matrix). > There are some parts done by Steve that have a "0 not CW-Compliant" > line and some others done by Chris that have "0 CW compliant" line but > some of those files do have CCW faces. Ups. We need a renderer that understands 0 FACE (C)CW to test the parts. > Only a few parts can have all their faces on the correct direction, > some primitives (like BOX5.DAT) have faces with their normals pointing > to the inside and to the outside. That makes it impossible to fix those > files that use it without editing the primitives. Fixing the primitives is probably the first thing we should do when we have a renderer that understands 0 FACE (C)CW. > > You should also remember that using a CW face with a negative > > determinant orientation matrix changes it to a CCW face. > > Never tried this, are you sure ? Yep. It corresponds to mirroring. If you want to do a simple test, you should draw a cube and label its corners. Establish which vector products of vectors from one label to another points out of the cube. Multiplying all points by / -1 0 0 \ | 0 1 0 | \ 0 0 1 / corresponds to swapping the labels on the left and right. If you look at the directions of the vector products now, they will all point into the cube. Play well, Jacob ---------------------------------------------- -- E-mail: Jacob.Sparre.Andersen@risoe.dk -- -- Web...: <URL:http://hugin.risoe.dk/> -- ---------------------------------------------- LDraw FAQ: <URL:http://hugin.risoe.dk/meyer/LEGO/V%E6rkt%F8j/LDraw-FAQ.html> ************************************************************************* From: Lars C. Hassing [mailto:lch@CCI.DK] Sent: 4. februar 1999 11:22 To: L-CAD@LISTSERV.UH.EDU Subject: Re: .dat file face orientation Rendering programs will definitely be able to benefit from (C)CW information. The symmetric nature of the parts suggests that half of the faces may be skipped. If you spend 70% of the time filling faces, you can easily spot the time saving. However, as Steve pointed out the rendering programs should be aware of the mix of CW, CCW, and 'no guaranteewise' information. Also, as Jacob just explained in detail, the programs should detect clockwiseness changes caused by negative determinants. Defining CW/CCW for the primitives also forces us to clearly define what is supposed to be inside and outside. Consider STUD2.DAT, it uses: 1 16 0 -4 0 4 0 0 0 4 0 0 0 4 4-4cyli.dat 1 16 0 -4 0 6 0 0 0 4 0 0 0 6 4-4cyli.dat The inside of the first cylinder is the outside of the stud, while the outside of the second cylinder is also the outside of the stud. So, we need two cylinder primitives... And when can the rendering programs trust (C)CW information? If a part author didn't pay attention, it won't help if the primitives he used are clockwiseness-aware. Leo, didn't you a long time ago mention that you once did a program, that could show clockwiseness as red or green, and you could click on faces to change their clockwiseness? And you mentioned 30% saving? /Lars ************************************************************************* From: Leonardo Zide [mailto:leonardo@CENTROIN.COM.BR] Sent: 4. februar 1999 12:35 To: L-CAD@LISTSERV.UH.EDU Subject: Re: .dat file face orientation Subject: Re: .dat file face orientation Date: Wed, 3 Feb 1999 19:39:06 -0500 From: S & K Bliss <blisses@WORLDNET.ATT.NET> > Only a few parts can have all their faces on the correct direction, > some primitives (like BOX5.DAT) have faces with their normals pointing > to the inside and to the outside. That makes it impossible to fix those > files that use it without editing the primitives. > If the primitive is non-(C)CW, that doesn't affect the parts that use > it. The rendering program must be smart enough to not assume that > subfiles have the same CW standing as the parent file. Maybe I didn't explain myself correclty, the are primitives that have faces CW and CCW, if a program is able to know what's correct than there's no reason to fix the files. A good example is if you try to export from LeoCAD to 3D Studio, 3DS doesn't know which faces are CW so you have to disable backface culling and force the model to be 2-sided. I guess we all agree that 3DS is an advanced program so if it was possible for a program to find CW and CCW faces, it would do it but it doesn't. Leonardo ************************************************************************* From: Jacob Sparre Andersen [mailto:sparre@CATS.NBI.DK] Sent: 4. februar 1999 14:18 To: L-CAD@LISTSERV.UH.EDU Subject: Re: .dat file face orientation Leonardo: > Maybe I didn't explain myself correclty, the are primitives that have > faces CW and CCW, if a program is able to know what's correct than > there's no reason to fix the files. We shouldn't expect the programs to _guess_ if faces are CW or CCW. - It should be _written_ in the files. > A good example is if you try to export from LeoCAD to 3D Studio, 3DS > doesn't know which faces are CW so you have to disable backface culling > and force the model to be 2-sided. I guess we all agree that 3DS is an > advanced program so if it was possible for a program to find CW and CCW > faces, it would do it but it doesn't. There exists algorithms for determining if faces are (counter) clockwise, but there is no point in using them when we can do it just as fast by hand once and for all. Play well, Jacob ---------------------------------------------- -- E-mail: Jacob.Sparre.Andersen@risoe.dk -- -- Web...: <URL:http://hugin.risoe.dk/> -- ---------------------------------------------- LDraw FAQ: <URL:http://hugin.risoe.dk/meyer/LEGO/V%E6rkt%F8j/LDraw-FAQ.html> ************************************************************************* From: John VanZwieten [mailto:john_vanzwieten@EMAIL.MSN.COM] Sent: 4. februar 1999 16:49 To: L-CAD@LISTSERV.UH.EDU Subject: Re: .dat file face orientation :Rendering programs will definitely be able to benefit from (C)CW :information. The symmetric nature of the parts suggests that :half of the faces may be skipped. If you spend 70% of the time :filling faces, you can easily spot the time saving. Even if CW/CCW compliance could be obtained for the most commonly used (and esp. large) parts and primitives, significant time saving would result. Just cutting in half the time needed to draw studs would be great. :However, as Steve pointed out the rendering programs should be aware :of the mix of CW, CCW, and 'no guaranteewise' information. :Also, as Jacob just explained in detail, the programs should :detect clockwiseness changes caused by negative determinants. :Defining CW/CCW for the primitives also forces us to clearly define :what is supposed to be inside and outside. Consider STUD2.DAT, it uses: :1 16 0 -4 0 4 0 0 0 4 0 0 0 4 4-4cyli.dat :1 16 0 -4 0 6 0 0 0 4 0 0 0 6 4-4cyli.dat :The inside of the first cylinder is the outside of the stud, while :the outside of the second cylinder is also the outside of the stud. :So, we need two cylinder primitives... If the rendering program is aware of the mix of CW and CCW, then STUD2.DAT could use: 0 CCW 1 16 0 -4 0 4 0 0 0 4 0 0 0 4 4-4cyli.dat 0 CW 1 16 0 -4 0 6 0 0 0 4 0 0 0 6 4-4cyli.dat :If a part author didn't pay attention, it won't help if the :primitives he used are clockwiseness-aware. Good point, except in the case of studs, axles, and maybe a couple others. A box5.dat might stick out of a part and be CW, or stick into a part and be CCW--it doesn't have an inherent inside or outside. However, a stud2.dat does have inherent inside and outside, so CW/CCW could be coded into the primitive. For other primitives, CW/CCW would have to be coded at the part level. And, as noted, the program would have to be able to deal with "-"s in the transformation matrix. :Leo, didn't you a long time ago mention that you once did a program, :that could show clockwiseness as red or green, and you could click :on faces to change their clockwiseness? And you mentioned 30% saving? That would be cool. Standard bricks, plates, tiles, etc. could be made compliant quickly this way. Keeping CW compliance while creating a part is a real pain, but viewing it afterward and making corrections might not be so bad. -John Van ************************************************************************* From: S & K Bliss [mailto:blisses@WORLDNET.ATT.NET] Sent: 5. februar 1999 00:13 To: L-CAD@LISTSERV.UH.EDU Subject: Re: .dat file face orientation Hey guys: About inversion, and needing two versions for each primitive, and etc. As I understand, mirroring/inverting an object should be treated as if all the faces on the object were turned inside out. So, if 4-4cyli.dat is certified (C)CW, with the faces facing outward, stud2.dat could draw its cylinders like this: 1 16 0 -4 0 6 0 0 0 1 0 0 0 6 4-4cyli.dat 1 16 0 4 0 4 0 0 0 -1 0 0 0 4 4-4cyli.dat On the first line, the cylinder is not inverted, and the resulting quads will face outward. On the second line, the cylinder *is* inverted, and the quads now face inward. I could be misremembering, but as long as inversions are treated this way, there's no need for the rendering program to worry about objects getting mis-verted. Steve ************************************************************************* From: Leonardo Zide [mailto:leonardo@CENTROIN.COM.BR] Sent: 5. februar 1999 21:58 To: L-CAD@LISTSERV.UH.EDU Subject: Re: .dat file face orientation > Subject: Re: .dat file face orientation > Date: Thu, 4 Feb 1999 10:17:51 +0100 > From: Jacob Sparre Andersen <sparre@CATS.NBI.DK> > > Leonardo: > > First I should clarify that a FACE (C)CW only can/should > account for planes _in_ that file. Sub-files (parts and > sub-models) should be treated separately because of possible > problems with mirroring (negative determinant orientation > matrix). I disagree with that, in my opinion a part should only be considered CW compliant if all subfiles used by it are also correctly oriented. There should be one statement at the beginning of the file saying that it is CW compliant, not only sections of it. > > There are some parts done by Steve that have a "0 not CW-Compliant" > > line and some others done by Chris that have "0 CW compliant" line but > > some of those files do have CCW faces. > > Ups. We need a renderer that understands 0 FACE (C)CW to > test the parts. LeoCAD uses backface culling for some parts that I've edited by hand using a program that draws the CW faces green and the CCW faces red. Using this program I found some errors on some parts that do not appear in LDraw due to the fact that it uses flat rendering. > > Only a few parts can have all their faces on the correct direction, > > some primitives (like BOX5.DAT) have faces with their normals pointing > > to the inside and to the outside. That makes it impossible to fix those > > files that use it without editing the primitives. > > Fixing the primitives is probably the first thing we should > do when we have a renderer that understands 0 FACE (C)CW. I agree with that, I've had to fix a few on my HD to be able to fix some of those parts. > Subject: Re: .dat file face orientation > Date: Thu, 4 Feb 1999 11:22:22 +0100 > From: "Lars C. Hassing" <lch@CCI.DK> > > Rendering programs will definitely be able to benefit from (C)CW > information. The symmetric nature of the parts suggests that > half of the faces may be skipped. If you spend 70% of the time > filling faces, you can easily spot the time saving. You don't spend that much time with the rasterization, the parts have so many vertexes that the most important part of the rendering is the transformation. LeoCAD is more geometry-bound than fill limited (I don't know how Ldraw was done but I believe it has the same problems). > Leo, didn't you a long time ago mention that you once did a program, > that could show clockwiseness as red or green, and you could click > on faces to change their clockwiseness? And you mentioned 30% saving? I still have that program, I'm moving it to the main LeoCAD package to work as a piece editor. The 30% saving only happens for software rendering, I have a 3D card that has a very good fill rate so it doesn't show much difference here but as LDraw is not capable of using the hardware to help you should get that speed increase. > Subject: Re: .dat file face orientation > Date: Thu, 4 Feb 1999 13:59:03 +0100 > From: Jacob Sparre Andersen <sparre@CATS.NBI.DK> > > Lars: > > > Defining CW/CCW for the primitives also forces us to clearly define > > what is supposed to be inside and outside. Consider STUD2.DAT, it uses: > > 1 16 0 -4 0 4 0 0 0 4 0 0 0 4 4-4cyli.dat > > 1 16 0 -4 0 6 0 0 0 4 0 0 0 6 4-4cyli.dat > > The inside of the first cylinder is the outside of the stud, while > > the outside of the second cylinder is also the outside of the stud. > > So, we need two cylinder primitives... > > It appears to be so. Any ideas for circumventing this? Check the file before sending it for voting. :) > > And when can the rendering programs trust (C)CW information? > > When they have been verfied by the L-CAD group. I agree, we could add a "0 CW" line to the header of the correct files. > Subject: Re: .dat file face orientation > Date: Thu, 4 Feb 1999 14:17:33 +0100 > From: Jacob Sparre Andersen <sparre@CATS.NBI.DK> > > Leonardo: > > > Maybe I didn't explain myself correclty, the are primitives that have > > faces CW and CCW, if a program is able to know what's correct than > > there's no reason to fix the files. > > We shouldn't expect the programs to _guess_ if faces are CW > or CCW. - It should be _written_ in the files. I know but if it was possible it would save a lot of work... :) > > A good example is if you try to export from LeoCAD to 3D Studio, 3DS > > doesn't know which faces are CW so you have to disable backface culling > > and force the model to be 2-sided. I guess we all agree that 3DS is an > > advanced program so if it was possible for a program to find CW and CCW > > faces, it would do it but it doesn't. > > There exists algorithms for determining if faces are > (counter) clockwise, but there is no point in using them > when we can do it just as fast by hand once and for all. I've proposed that a long time ago but as the only program that would take advantage of it right now is LeoCAD and people here do prefer LDraw, nobody paid much attention. > Subject: Re: .dat file face orientation > Date: Thu, 4 Feb 1999 09:48:30 -0600 > From: John VanZwieten <john_vanzwieten@EMAIL.MSN.COM> > > If the rendering program is aware of the mix of CW and CCW, then STUD2.DAT > could use: > 0 CCW > 1 16 0 -4 0 4 0 0 0 4 0 0 0 4 4-4cyli.dat > 0 CW > 1 16 0 -4 0 6 0 0 0 4 0 0 0 6 4-4cyli.dat I think it would be better to just set a line "0 CW-compliant" at the header instead of changing the orientation multiple times. > :Leo, didn't you a long time ago mention that you once did a program, > :that could show clockwiseness as red or green, and you could click > :on faces to change their clockwiseness? And you mentioned 30% saving? > > That would be cool. Standard bricks, plates, tiles, etc. could be made > compliant quickly this way. Keeping CW compliance while creating a part is a > real pain, but viewing it afterward and making corrections might not be so > bad. I've already fixed most of the bricks/plates/tiles, they only needed to have one box5 swapped and in some cases 2 other faces too. > Subject: Archive of LDraw'n models (Was: Official Lego Model Standard) > Date: Thu, 4 Feb 1999 18:42:23 +0100 > From: Jacob Sparre Andersen <sparre@CATS.NBI.DK> > > Kevin: > > > If anyone is willing to put up the space, I would be more than happy to move > > my site there and administer the site. I already have several more TLGs to > > put up on my site, and I would welcome any submissions that anybody is > > willing to make. > > I wouldn't mind hosting an archive of LDraw'n models, but I will ask > TLG for permission before instructions for official models (i.e. models > TLG has published _building_instructions_ for) on the server. I have about 100 official sets in my page, feel free to use them if you wish (but contact the authors first). Leonardo ************************************************************************* From: Jacob Sparre Andersen [mailto:sparre@CATS.NBI.DK] Sent: 5. februar 1999 22:05 To: L-CAD@LISTSERV.UH.EDU Subject: Re: .dat file face orientation John: [...] > If the rendering program is aware of the mix of CW and CCW, then STUD2.DAT > could use: > 0 FACE CCW > 1 16 0 -4 0 4 0 0 0 4 0 0 0 4 4-4cyli.dat > 0 FACE CW > 1 16 0 -4 0 6 0 0 0 4 0 0 0 6 4-4cyli.dat Since (C)CW information shouldn't propagate through part file references ("0" commands), this wouldn't have any effect. Play well, Jacob ---------------------------------------------- -- E-mail: Jacob.Sparre.Andersen@risoe.dk -- -- Web...: <URL:http://hugin.risoe.dk/> -- ---------------------------------------------- LDraw FAQ: <URL:http://hugin.risoe.dk/meyer/LEGO/V%E6rkt%F8j/LDraw-FAQ.html> ************************************************************************* From: John VanZwieten [mailto:john_vanzwieten@EMAIL.MSN.COM] Sent: 5. februar 1999 23:40 To: L-CAD@LISTSERV.UH.EDU Subject: Re: .dat file face orientation I don't write these programs, so I guess you can take my input with a grain of salt, but it seems to me the best implementation of (C)CW would assign a CW or CCW value to each quad/tri, then if the rendered orientation matches that value, the quad/tri gets drawn, otherwise not. Actually, a third possible value would be needed: "Unknown" in which case the quad/tri always gets drawn. I know the use of multiple 0 Face commands in a part seems like creating a mess, but I think it would actually solve more problems than it causes. Consider this method: Every quad starts with a Face value of "unknown" (UK). If the renderer encounters a 0 FACE command then subsequent lines are given CW, CCW, or UK values until the renderer encounters another 0 FACE command. If in a part a primitive is marked CW, then the quads in that primitive are given CW values unless a 0 FACE CCW or 0 FACE UK command is encountered in the primitive. If a primitive is marked CCW, and a quad or other primitive contained in the first primitive is also marked CCW, they would cancel so the quads would become CW. Negative determinates would also change a subfile or primitive from CW to CCW. I think you would get much better participation from part authors using this method. Mirroring and other CW non-complient practices are just so convenient when creating a part that it would be hard to give them up. But if I could mirror a subfile and just stick a 0 FACE CCW in front of it, I would do it. Also if I could ignore CW while doing particularly difficult sections of a part but pay attention while doing studs, large quads, etc. then significant rendering time savings might result. : It only works for primitives that have their center at (0,0,0) and are :symmetrical in the x axis, because all that the multiplication does is a :change to the signal of x coordinate of the points. : Try something like this: :1 16 10 0 0 10 0 0 0 5 0 0 0 10 1-4cyli.dat :1 16 -10 0 0 -10 0 0 0 5 0 0 0 10 1-4cyli.dat : The second file will be rotated 180 degrees and will not have the :orientation of the first so you can't use it to fix CCW faces. That :solution can be used in some cases like studs, cubes (not all of them) :and 360 degrees cylinders. Correct me if I'm wrong, but wouldn't the "outside" faces of the first line be CW while the "inside" faces of the second line would be CW. :> First I should clarify that a FACE (C)CW only can/should :> account for planes _in_ that file. Sub-files (parts and :> sub-models) should be treated separately because of possible :> problems with mirroring (negative determinant orientation :> matrix). : I disagree with that, in my opinion a part should only be considered :CW compliant if all subfiles used by it are also correctly oriented. :There should be one statement at the beginning of the file saying that :it is CW compliant, not only sections of it. So would a model be CW compliant only if all parts are CW compliant? What about all the models that use mirroring? Suddenly a CW compliant part would become CCW. :> > There are some parts done by Steve that have a "0 not CW-Compliant" :> > line and some others done by Chris that have "0 CW compliant" line but :> > some of those files do have CCW faces. :> :> Ups. We need a renderer that understands 0 FACE (C)CW to :> test the parts. : LeoCAD uses backface culling for some parts that I've edited by hand :using a program that draws the CW faces green and the CCW faces red. :Using this program I found some errors on some parts that do not appear :in LDraw due to the fact that it uses flat rendering. Don't you have to rotate a part many different ways to see if maybe some "underside" quad is CCW when it should be CW? This seems a tiring process for any but the most basic parts. :> Rendering programs will definitely be able to benefit from (C)CW :> information. The symmetric nature of the parts suggests that :> half of the faces may be skipped. If you spend 70% of the time :> filling faces, you can easily spot the time saving. : You don't spend that much time with the rasterization, the parts have :so many vertexes that the most important part of the rendering is the :transformation. LeoCAD is more geometry-bound than fill limited (I don't :know how Ldraw was done but I believe it has the same problems). Hmmm, then maybe all this CW stuff would only add to the "geometry time". :> > And when can the rendering programs trust (C)CW information? :> :> When they have been verfied by the L-CAD group. : I agree, we could add a "0 CW" line to the header of the correct :files. L-CAD has enough trouble ferriting out missing quads, let alone CCW ones :) -John Van ************************************************************************* From: Leonardo Zide [mailto:leonardo@CENTROIN.COM.BR] Sent: 6. februar 1999 12:35 To: L-CAD@LISTSERV.UH.EDU Subject: Re: .dat file face orientation Subject: Re: .dat file face orientation Date: Fri, 5 Feb 1999 16:40:26 -0600 From: John VanZwieten <john_vanzwieten@EMAIL.MSN.COM> > I don't write these programs, so I guess you can take my input with a > grain of salt, but it seems to me the best implementation of (C)CW > would assign a CW or CCW value to each quad/tri, then if the rendered > orientation matches that value, the quad/tri gets drawn, otherwise > not. Actually, a third possible value would be needed: "Unknown" > in which case the quad/tri always gets drawn. I know the use of > multiple 0 Face commands in a part seems like creating a mess, but > I think it would actually solve more problems than it causes. If you can check and see if a face is CCW, why not invert it and make everything CW ? This makes the files simpler and makes it faster for a program to read it. Remember that programs like LDraw spend time reading the files from the disk while rendering, so unnecessary lines should be avoided. : It only works for primitives that have their center at (0,0,0) and are :symmetrical in the x axis, because all that the multiplication does is a :change to the signal of x coordinate of the points. : Try something like this: :1 16 10 0 0 10 0 0 0 5 0 0 0 10 1-4cyli.dat :1 16 -10 0 0 -10 0 0 0 5 0 0 0 10 1-4cyli.dat : The second file will be rotated 180 degrees and will not have the :orientation of the first so you can't use it to fix CCW faces. That :solution can be used in some cases like studs, cubes (not all of them) :and 360 degrees cylinders. > Correct me if I'm wrong, but wouldn't the "outside" faces of the first > line be CW while the "inside" faces of the second line would be CW. But they are not at the same position, my point was to say that this cannot be used to turn a CCW faces into CW. : I disagree with that, in my opinion a part should only be considered :CW compliant if all subfiles used by it are also correctly oriented. :There should be one statement at the beginning of the file saying that :it is CW compliant, not only sections of it. So would a model be CW compliant only if all parts are CW compliant? What about all the models that use mirroring? Suddenly a CW compliant part would become CCW. Mirroring does not change the inside/outside of a part, it only changes the position. And the "0 CW" line should only be added to parts, not models. > Don't you have to rotate a part many different ways to see if maybe > some "underside" quad is CCW when it should be CW? This seems a > tiring process for any but the most basic parts. It's extremely boring, that's why I only have about 40 files fixed. : You don't spend that much time with the rasterization, the parts have :so many vertexes that the most important part of the rendering is the :transformation. LeoCAD is more geometry-bound than fill limited (I don't :know how Ldraw was done but I believe it has the same problems). > Hmmm, then maybe all this CW stuff would only add to the "geometry > time". It turns out that the extra math is worth if you don't have to draw half of the faces. : I agree, we could add a "0 CW" line to the header of the correct :files. > L-CAD has enough trouble ferriting out missing quads, let alone CCW > ones :) This could be an optional line, add it if you wish. ************************************************************************* From: S & K Bliss [mailto:blisses@WORLDNET.ATT.NET] Sent: 6. februar 1999 05:49 To: L-CAD@LISTSERV.UH.EDU Subject: More on (C)CW Here's another point about inversions. The user can invert the entire model while launching the program. ldraw car.dat -a-1,0,0,0,1,0,0,0,1 Steve ************************************************************************* From: Leonardo Zide [mailto:leonardo@CENTROIN.COM.BR] Sent: 5. februar 1999 22:27 To: L-CAD@LISTSERV.UH.EDU Subject: Matrix stuff In that discussion about CW and CCW, Jacob said: > Yep. It corresponds to mirroring. If you want to do a simple > test, you should draw a cube and label its corners. > Establish which vector products of vectors from one label to > another points out of the cube. Multiplying all points by > > / -1 0 0 \ > | 0 1 0 | > \ 0 0 1 / > > corresponds to swapping the labels on the left and right. If > you look at the directions of the vector products now, they > will all point into the cube. I have to say that Jacob made think about how it works and I came with the conclusion that it's just a hack that works with the LDraw cube (and some other primitives), it's not a general rule that can be always applied. It only works for primitives that have their center at (0,0,0) and are symmetrical in the x axis, because all that the multiplication does is a change to the signal of x coordinate of the points. Try something like this: 1 16 10 0 0 10 0 0 0 5 0 0 0 10 1-4cyli.dat 1 16 -10 0 0 -10 0 0 0 5 0 0 0 10 1-4cyli.dat The second file will be rotated 180 degrees and will not have the orientation of the first so you can't use it to fix CCW faces. That solution can be used in some cases like studs, cubes (not all of them) and 360 degrees cylinders. Leonardo ************************************************************************* From: S & K Bliss [mailto:blisses@WORLDNET.ATT.NET] Sent: 6. februar 1999 03:24 To: L-CAD@LISTSERV.UH.EDU Subject: Re: Matrix stuff Leonardo wrote: Try something like this: 1 16 10 0 0 10 0 0 0 5 0 0 0 10 1-4cyli.dat 1 16 -10 0 0 -10 0 0 0 5 0 0 0 10 1-4cyli.dat The second file will be rotated 180 degrees and will not have the orientation of the first so you can't use it to fix CCW faces. That solution can be used in some cases like studs, cubes (not all of them) and 360 degrees cylinders. No, the second primitive is not rotated. It's mirrored. Because one coordinate was negated, the (previously) outward-faces will now be inward-facing. What does LeoCAD do with the example above? If it uses back-face culling, I would expect that the second primitive is drawn, and the first primitive is not (from a front view). Better yet, try this with two 4-4cyli.dat primitives. In that case, you should get two half-cylinders. The one on the left (the mirrored one) should have the concave side drawn, and the one on the right should have the convex side drawn. Steve ************************************************************************* From: Leonardo Zide [mailto:leonardo@CENTROIN.COM.BR] Sent: 6. februar 1999 13:00 To: L-CAD@LISTSERV.UH.EDU Subject: Re: Matrix stuff Subject: Re: Matrix stuff Date: Fri, 5 Feb 1999 21:23:38 -0500 From: S & K Bliss <blisses@WORLDNET.ATT.NET> > No, the second primitive is not rotated. It's mirrored. Because > one coordinate was negated, the (previously) outward-faces will now > be inward-facing. Mirroring is the same as rotating 180 degrees (in this case around the Z axis), if you don't believe me try it in LEdit. > What does LeoCAD do with the example above? If it uses back-face > culling, I would expect that the second primitive is drawn, and the > first primitive is not (from a front view). It does only use backface culling with pieces that I've fixed, the others are drawn as 2-sided. > Better yet, try this with two 4-4cyli.dat primitives. In that case, > you should get two half-cylinders. The one on the left (the mirrored > one) should have the concave side drawn, and the one on the right > should have the convex side drawn. You mean 4-8cyli.dat, right ? My point was to say that mirroring does not always make a CW primitive CCW but it does work in some cases. Imagine that you want to use those 2 half-cylinders to draw a complete cylinder (and there's no 8-8cyli.dat), the faces wouldn't be pointing to the same direction. Or another situation, the box5.dat if you take the top quad: 1---2 | | ^ X | | | 4---3 .-> Z If you use the (-1 0 0 0 1 0 0 0 1) matrix, you'd get: 3---4 | | ^ X | | | 1---2 .-> Z The order of the points is wrong. All I'm trying to say is that with that matrix you don't always turn CCW faces into CW, nothing more. Leonardo ************************************************************************* From: Jacob Sparre Andersen [mailto:sparre@CATS.NBI.DK] Sent: 6. februar 1999 15:01 To: L-CAD@LISTSERV.UH.EDU Subject: Re: Matrix stuff Leonardo: > Mirroring is the same as rotating 180 degrees (in this case around the > Z axis), if you don't believe me try it in LEdit. No. And here's an example: A o B C "o" marks origo (0,0), and "A", "B", and "C" are some points we are going to rotate 180° around an axis perpendicular to the monitor... C B o A ...and mirror in a plane perpendicular to the line going through "B" and "o"... A B o C There is a difference, don't you think? Play well, Jacob ---------------------------------------------- -- E-mail: Jacob.Sparre.Andersen@risoe.dk -- -- Web...: <URL:http://hugin.risoe.dk/> -- ---------------------------------------------- LDraw FAQ: <URL:http://hugin.risoe.dk/meyer/LEGO/V%E6rkt%F8j/LDraw-FAQ.html> ************************************************************************* From: S & K Bliss [mailto:blisses@WORLDNET.ATT.NET] Sent: 7. februar 1999 01:35 To: L-CAD@LISTSERV.UH.EDU Subject: Re: Matrix stuff Leonardo wrote: .Subject: Re: Matrix stuff . Date: Fri, 5 Feb 1999 21:23:38 -0500 . From: S & K Bliss <blisses@WORLDNET.ATT.NET> . .> No, the second primitive is not rotated. It's mirrored. Because .> one coordinate was negated, the (previously) outward-faces will now .> be inward-facing. . . Mirroring is the same as rotating 180 degrees (in this case around the .Z axis), if you don't believe me try it in LEdit. OK. Take a standard part-line: 1 16 0 0 0 1 0 0 0 1 0 0 0 1 3001.dat Now, rotate it 180 degrees around the Y-axis: 1 16 0 0 0 -1 0 0 0 1 0 0 0 -1 3001.dat That is definitely not the same as mirroring, which would only involve negating one dimension's components. .> What does LeoCAD do with the example above? If it uses back-face .> culling, I would expect that the second primitive is drawn, and the .> first primitive is not (from a front view). . . It does only use backface culling with pieces that I've fixed, the .others are drawn as 2-sided. OK, let's say you fixed 1-4cyli.dat. Then what would LeoCAD do with the example? .> Better yet, try this with two 4-4cyli.dat primitives. In that case, .> you should get two half-cylinders. The one on the left (the mirrored .> one) should have the concave side drawn, and the one on the right .> should have the convex side drawn. . . You mean 4-8cyli.dat, right ? No, I meant 4-4cyli.dat, a complete cylinder primitive. With backface culling, only half of this primitive would ever be drawn, because half of the quads would be facing away from the viewer. .My point was to say that mirroring does .not always make a CW primitive CCW but it does work in some cases. But mirroring always reverses the directions of quads (and triangles), without toggling their CW-ness to CCW. .Imagine that you want to use those 2 half-cylinders to draw a complete .cylinder (and there's no 8-8cyli.dat), the faces wouldn't be pointing to .the same direction. When you say you want to *draw* a complete cylinder, do you mean you want all the faces rendered, or do you mean you want the faces which are facing the viewer to be rendered? If you want all faces rendered, you'd do this: 1 16 0 0 0 1 0 0 0 1 0 0 0 1 2-4cyli.dat 1 16 0 0 0 -1 0 0 0 1 0 0 0 1 2-4cyli.dat If you want the cylinder rendering correctly (ie, faces on the backside of the cylinder would not be rendered), do this: 1 16 0 0 0 1 0 0 0 1 0 0 0 1 2-4cyli.dat 1 16 0 0 0 -1 0 0 0 1 0 0 0 -1 2-4cyli.dat . Or another situation, the box5.dat if you take the top quad: . .1---2 .| | ^ X .| | | .4---3 .-> Z . . If you use the (-1 0 0 0 1 0 0 0 1) matrix, you'd get: . .3---4 .| | ^ X .| | | .1---2 .-> Z . . The order of the points is wrong. Not quite. What you'd get is: 4---3 | | ^ X | | | 1---2 .-> Z (You negated Z on points 3 and 4) This is either a CCW quad, facing the viewer, or a CW quad, facing away from the viewer. It is a more useful interpretation to see this as CW. . All I'm trying to say is that with that matrix you don't always turn .CCW faces into CW, nothing more. Right. You never do. Steve ************************************************************************* From: Leonardo Zide [mailto:leonardo@CENTROIN.COM.BR] Sent: 7. februar 1999 13:23 To: L-CAD@LISTSERV.UH.EDU Subject: Re: Matrix stuff Subject: Re: Matrix stuff Date: Sat, 6 Feb 1999 19:35:11 -0500 From: S & K Bliss <blisses@WORLDNET.ATT.NET> > No, I meant 4-4cyli.dat, a complete cylinder primitive. With > backface culling, only half of this primitive would ever be drawn, > because half of the quads would be facing away from the viewer. You're right, only half of the quads would be drawn. All LDraw parts are solid objects, so if you make all quads CW you won't see the backfaces because they are facing the inside of the object and another face will be drawn above it (unless you set the viewpoint inside the object). > If you want the cylinder rendering correctly (ie, faces on the > backside of the cylinder would not be rendered), do this: > 1 16 0 0 0 1 0 0 0 1 0 0 0 1 2-4cyli.dat > 1 16 0 0 0 -1 0 0 0 1 0 0 0 -1 2-4cyli.dat It's going to be hard to explain part authors that they should make those extra transformations while creating parts. The best solution would be to have 2 sets of primitives but I know that 99% of you are going to be against this idea. Leonardo ************************************************************************* From: S & K Bliss [mailto:blisses@WORLDNET.ATT.NET] Sent: 7. februar 1999 22:32 To: L-CAD@LISTSERV.UH.EDU Subject: Re: Matrix stuff Leonardo said: . It's going to be hard to explain part authors that they should make .those extra transformations while creating parts. The best solution .would be to have 2 sets of primitives but I know that 99% of you are .going to be against this idea. I don't think explaining the proper transforms is much harder than explaining: a) don't use improper transforms b) and if you do want to turn some primitive inside out, use this second copy of it, please. If someone (and I've done this plenty of times) draws some complex structure, then does a copy/paste, and negates all the X-coords to create the other side of the part, they've just killed all the CW-ness of the part. If parts authors are going to implement CW-ness in their parts, they have to be very aware of what they are doing with primitives. Duplicating primitives to have inside and outside versions will just complicate the issue. Steve ************************************************************************* From: Chris Dee [mailto:chris_w_dee@HOTMAIL.COM] Sent: 9. februar 1999 11:16 To: L-CAD@LISTSERV.UH.EDU Subject: Re: Matrix stuff Steve Bliss wrote : > > Leonardo said: > > . It's going to be hard to explain part authors that they should make > .those extra transformations while creating parts. The best solution > .would be to have 2 sets of primitives but I know that 99% of you are > .going to be against this idea. > > > I don't think explaining the proper transforms is much harder than > explaining: > > a) don't use improper transforms > b) and if you do want to turn some primitive inside out, use this • second > copy of it, please. > > If someone (and I've done this plenty of times) draws some complex > structure, then does a copy/paste, and negates all the X-coords to • create > the other side of the part, they've just killed all the CW-ness of the • part. > Yup, but now I mostly use LDS MIRRORing to do this, so if this could be fixed it would be easier. Rather than just inverting the sign it would need to resequence the points too. Any chance Tore? P1-----P2 | P2-----P1 | | | | | | | | | | P4-----P3 | P3-----P4 So P1 P2 P3 P4 should become -P2 -P1 -P4 -P3 instead of -P1 -P2 -P3 -P4 > > If parts authors are going to implement CW-ness in their parts, they • have to > be very aware of what they are doing with primitives. Duplicating > primitives to have inside and outside versions will just complicate the > issue. > > Steve ************************************************************************* From: S & K Bliss [mailto:blisses@WORLDNET.ATT.NET] Sent: 10. februar 1999 00:12 To: L-CAD@LISTSERV.UH.EDU Subject: Re: Matrix stuff [hoping I got the lugnet mailing address right] Chris said: .Yup, but now I mostly use LDS MIRRORing to do this, so if this could be .fixed it would be easier. Rather than just inverting the sign it would .need to resequence the points too. Any chance Tore? . .P1-----P2 | P2-----P1 .| | | | | .| | | | | .P4-----P3 | P3-----P4 . .So P1 P2 P3 P4 should become -P2 -P1 -P4 -P3 . instead of -P1 -P2 -P3 -P4 Seems like it would be best to have a flag to reorder the points or not. Sometimes you'd want to have the points reversed. Steve ************************************************************************* From: Ben Bennett [mailto:sink@AYUP.limey.net] Sent: 16. februar 1999 20:27 To: lugnet.cad@lugnet.com Subject: Re: LUBNET... hmmm.. now where could that lead us??? > LUBNET.. hmmm... (jeff ponders a moment, needing a break from processing > triangles into quads with edge lines and faces and determinants of 4x4 > matrices to prove coplanarism of... aaaahhhhhhhhhhhhhhhh!!!!!) Ah but you don't need to compute the determinant. For 3D points A, B, C, and D represented as vectors, and AB is the line segment from A to B (or B-A): (AD x AB) . AC = det ( Ax, Ay, Az, 0, Bx, By, Bz, 0, Cx, Cy, Cz, 0, Dx, Dy, Dz, 0) Where x represents the cross product and . is the dot product and det is the determinant. I am not sure which is cheaper to calculate, but if you happen to have ADxAB sitting around then you can do it this way. I am writing a perl program that allows you to manipulate LDraw files and let you examine it interactively. At the moment it is displaying files in a rudimentary way and rotating them. Issues that I encountered was determining if a quad was coplanar, and making sure that the quad was not "twisted" i.e. the points were defined in either clockwise or counter clockwise order since OpenGL has restrictions on that. The major remainging problem that I need to address before this displays perfectly is determining if a quad faces forward or backwards and changing the ordering of the points in the quad so that the quad is shaded correctly and backface culling can be done. If anyone has any suggestions on this, please let me know. I should also clean up the interface so that the errors are detected and corrected rather than just detecting the error and telling the user what it is and making them fix the model file. This requires automatically tesselating quads into triangles where the quads are not planar. Then of course I need to add the interaction to allow the user to control the point of view rather than just simply rotating the model. -ben ************************************************************************* End of CW/CCW, vertex sequence, co-planar, convex, (115kB)

Message has 3 Replies:

		Re: CW/CCW, vertex sequence, co-planar, convex, (115kB)
(...) I miss that kind of discussion, those were very interesting subjects. Also, where's Jeff Findley ? (...) I've already thought about a ray intersection algorithm but I've never tried to implement it, I might try do it now. Some problems that I (...) (25 years ago, 29-Sep-99, to lugnet.cad.dev)

		(canceled)

		Re: CW/CCW, vertex sequence, co-planar, convex [DAT]
It seems to me that there are two major "camps" in the CW/CCW debate. A. Face-by-Face Method This method suggests that CW-ness be ultimately evaluated on a face-by-face basis. Each quad in a primitive or part would hold a value of CW,CCW, or (...) (25 years ago, 4-Oct-99, to lugnet.cad.dev)

53 Messages in This Thread:

Entire Thread on One Page:: Nested: All | Brief | Compact | Dots
Linear: All | Brief | Compact

Custom Search