Path: chuka.playstation.co.uk!scea!greg_labrec@interactive.sony.com
From: David White <dwhite2@san.rr.com>
Newsgroups: scea.yaroze.programming.3d_graphics
Subject: Solved flashing polygon problem!
Date: Sat, 08 Nov 1997 22:28:44 -0800
Organization: SCEA News Server
Lines: 58
Message-ID: <3465580B.4D4A@san.rr.com>
Reply-To: dwhite2@san.rr.com
NNTP-Posting-Host: dt3h1n35.san.rr.com
Mime-Version: 1.0
Content-Type: text/plain; charset=us-ascii
Content-Transfer-Encoding: 7bit
X-Mailer: Mozilla 3.01-C-MACOS8 (Macintosh; I; PPC)
CC: goneil@chat.carleton.ca

Well guys, I've squashed my flashing polygon bug. 

As Andreas Schrattenecker suggested, it had to do with quads being
tesselated into 2 triangles with different normals. I was getting
different normals because some of my quads were very close to triangles
with 2 of the 4 verticies close together. These quads convert to a
regular and rather narrow triangle. With the verticies converted to
integer coordinates, the normal for the narrow triangle would likely be
incorrect. When the narrow triangle was listed first in the quad vertex
list, the Yaroze assigned its incorrect normal to the whole quad.

The solution was simple. I first calculated the area for each triangle
in the quad and made sure that the larger triangle was listed first. 

My code looked like this...

if a polygon is a quad...
Point3D_Subtract(&PolyPoint[PolyFace[a][1]],
				 &PolyPoint[PolyFace[a][0]], &Vector_A);
Point3D_Subtract(&PolyPoint[PolyFace[a][2]],
				 &PolyPoint[PolyFace[a][0]], &Vector_B);
Vector3D_Cross(&Vector_A, &Vector_B, &Face_Normal);
Area1 = 0.5 *  sqrt((Face_Normal.x * Face_Normal.x) + 
					(Face_Normal.y * Face_Normal.y) +
					(Face_Normal.z * Face_Normal.z));

Point3D_Subtract(&PolyPoint[PolyFace[a][3]],
				 &PolyPoint[PolyFace[a][2]], &Vector_A);
Point3D_Subtract(&PolyPoint[PolyFace[a][1]],
				 &PolyPoint[PolyFace[a][2]], &Vector_B);
Vector3D_Cross(&Vector_A, &Vector_B, &Face_Normal);
Area2 = 0.5 *  sqrt((Face_Normal.x * Face_Normal.x) + 
					(Face_Normal.y * Face_Normal.y) +
					(Face_Normal.z * Face_Normal.z));

if (Area1 < Area2)
{
	// Swap triangles. (0,1,2,3 becomes 3,2,1,0)
	TempFace = PolyFace[a][0];
	PolyFace[a][0] = PolyFace[a][3];
	PolyFace[a][3] = TempFace;								
	TempFace = PolyFace[a][1];
	PolyFace[a][1] = PolyFace[a][2];
	PolyFace[a][2] = TempFace;								
}
 
where PolyFace is an array of vertex indicies and PolyPoint is an array
of vertex X,Y,Z values.

I also had to make sure that I cleaned up some errors in my modeler's
output where a few polygons had verticies with the same X,Y,Z values.

For those of you using the RSD tool and don't have the ability to use
this programming technique, you should probably avoid narrow polygons
(with respect to integer units) and quads that look a lot like
triangles.

David White