WebSVN - shark - Blame - Rev 1618 - /shark/branches/xen/ports/mesa/src-glu/polytest.c

Rev	Author	Line No.	Line
55	pj	1	/* $Id: polytest.c,v 1.1 2003-02-28 11:42:07 pj Exp $ */
		2
		3	/*
		4	* Mesa 3-D graphics library
		5	* Version: 3.3
		6	* Copyright (C) 1995-2000 Brian Paul
		7	*
		8	* This library is free software; you can redistribute it and/or
		9	* modify it under the terms of the GNU Library General Public
		10	* License as published by the Free Software Foundation; either
		11	* version 2 of the License, or (at your option) any later version.
		12	*
		13	* This library is distributed in the hope that it will be useful,
		14	* but WITHOUT ANY WARRANTY; without even the implied warranty of
		15	* MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
		16	* Library General Public License for more details.
		17	*
		18	* You should have received a copy of the GNU Library General Public
		19	* License along with this library; if not, write to the Free
		20	* Software Foundation, Inc., 675 Mass Ave, Cambridge, MA 02139, USA.
		21	*/
		22
		23
		24	/*
		25	* This file is part of the polygon tesselation code contributed by
		26	* Bogdan Sikorski
		27	*/
		28
		29
		30	#ifdef PC_HEADER
		31	#include "all.h"
		32	#else
		33	#include <math.h>
		34	#include <stdlib.h>
		35	#include "gluP.h"
		36	#include "tess.h"
		37	#endif
		38
		39
		40
		41	static GLenum store_polygon_as_contour(GLUtriangulatorObj *);
		42	static void free_current_polygon(tess_polygon *);
		43	static void prepare_projection_info(GLUtriangulatorObj *);
		44	static GLdouble twice_the_polygon_area(tess_vertex , tess_vertex );
		45	static GLenum verify_edge_vertex_intersections(GLUtriangulatorObj *);
		46	void tess_find_contour_hierarchies(GLUtriangulatorObj *);
		47	static GLenum test_for_overlapping_contours(GLUtriangulatorObj *);
		48	static GLenum contours_overlap(tess_contour , tess_polygon );
		49	static GLenum is_contour_contained_in(tess_contour , tess_contour );
		50	static void add_new_exterior(GLUtriangulatorObj , tess_contour );
		51	static void add_new_interior(GLUtriangulatorObj , tess_contour ,
		52	tess_contour *);
		53	static void add_interior_with_hierarchy_check(GLUtriangulatorObj *,
		54	tess_contour , tess_contour );
		55	static void reverse_hierarchy_and_add_exterior(GLUtriangulatorObj *,
		56	tess_contour *,
		57	tess_contour *);
		58	static GLboolean point_in_polygon(tess_contour *, GLdouble, GLdouble);
		59	static void shift_interior_to_exterior(GLUtriangulatorObj , tess_contour );
		60	static void add_exterior_with_check(GLUtriangulatorObj , tess_contour ,
		61	tess_contour *);
		62	static GLenum cut_out_hole(GLUtriangulatorObj , tess_contour ,
		63	tess_contour *);
		64	static GLenum merge_hole_with_contour(GLUtriangulatorObj *,
		65	tess_contour , tess_contour ,
		66	tess_vertex , tess_vertex );
		67
		68	static GLenum
		69	find_normal(GLUtriangulatorObj * tobj)
		70	{
		71	tess_polygon *polygon = tobj->current_polygon;
		72	tess_vertex va, vb, *vc;
		73	GLdouble A, B, C;
		74	GLdouble A0, A1, A2, B0, B1, B2;
		75
		76	va = polygon->vertices;
		77	vb = va->next;
		78	A0 = vb->location[0] - va->location[0];
		79	A1 = vb->location[1] - va->location[1];
		80	A2 = vb->location[2] - va->location[2];
		81	for (vc = vb->next; vc != va; vc = vc->next) {
		82	B0 = vc->location[0] - va->location[0];
		83	B1 = vc->location[1] - va->location[1];
		84	B2 = vc->location[2] - va->location[2];
		85	A = A1 * B2 - A2 * B1;
		86	B = A2 * B0 - A0 * B2;
		87	C = A0 * B1 - A1 * B0;
		88	if (fabs(A) > EPSILON \|\| fabs(B) > EPSILON \|\| fabs(C) > EPSILON) {
		89	polygon->A = A;
		90	polygon->B = B;
		91	polygon->C = C;
		92	polygon->D =
		93	-A * va->location[0] - B * va->location[1] - C * va->location[2];
		94	return GLU_NO_ERROR;
		95	}
		96	}
		97	tess_call_user_error(tobj, GLU_TESS_ERROR7);
		98	return GLU_ERROR;
		99	}
		100
		101	void
		102	tess_test_polygon(GLUtriangulatorObj * tobj)
		103	{
		104	tess_polygon *polygon = tobj->current_polygon;
		105
		106	/* any vertices defined? */
		107	if (polygon->vertex_cnt < 3) {
		108	free_current_polygon(polygon);
		109	return;
		110	}
		111	/* wrap pointers */
		112	polygon->last_vertex->next = polygon->vertices;
		113	polygon->vertices->previous = polygon->last_vertex;
		114	/* determine the normal */
		115	if (find_normal(tobj) == GLU_ERROR)
		116	return;
		117	/* compare the normals of previously defined contours and this one */
		118	/* first contour define ? */
		119	if (tobj->contours == NULL) {
		120	tobj->A = polygon->A;
		121	tobj->B = polygon->B;
		122	tobj->C = polygon->C;
		123	tobj->D = polygon->D;
		124	/* determine the best projection to use */
		125	if (fabs(polygon->A) > fabs(polygon->B))
		126	if (fabs(polygon->A) > fabs(polygon->C))
		127	tobj->projection = OYZ;
		128	else
		129	tobj->projection = OXY;
		130	else if (fabs(polygon->B) > fabs(polygon->C))
		131	tobj->projection = OXZ;
		132	else
		133	tobj->projection = OXY;
		134	}
		135	else {
		136	GLdouble a[3], b[3];
		137	tess_vertex *vertex = polygon->vertices;
		138
		139	a[0] = tobj->A;
		140	a[1] = tobj->B;
		141	a[2] = tobj->C;
		142	b[0] = polygon->A;
		143	b[1] = polygon->B;
		144	b[2] = polygon->C;
		145
		146	/* compare the normals */
		147	if (fabs(a[1] * b[2] - a[2] * b[1]) > EPSILON \|\|
		148	fabs(a[2] * b[0] - a[0] * b[2]) > EPSILON \|\|
		149	fabs(a[0] * b[1] - a[1] * b[0]) > EPSILON) {
		150	/* not coplanar */
		151	tess_call_user_error(tobj, GLU_TESS_ERROR9);
		152	return;
		153	}
		154	/* the normals are parallel - test for plane equation */
		155	if (fabs(a[0] * vertex->location[0] + a[1] * vertex->location[1] +
		156	a[2] * vertex->location[2] + tobj->D) > EPSILON) {
		157	/* not the same plane */
		158	tess_call_user_error(tobj, GLU_TESS_ERROR9);
		159	return;
		160	}
		161	}
		162	prepare_projection_info(tobj);
		163	if (verify_edge_vertex_intersections(tobj) == GLU_ERROR)
		164	return;
		165	if (test_for_overlapping_contours(tobj) == GLU_ERROR)
		166	return;
		167	if (store_polygon_as_contour(tobj) == GLU_ERROR)
		168	return;
		169	}
		170
		171	static GLenum
		172	test_for_overlapping_contours(GLUtriangulatorObj * tobj)
		173	{
		174	tess_contour *contour;
		175	tess_polygon *polygon;
		176
		177	polygon = tobj->current_polygon;
		178	for (contour = tobj->contours; contour != NULL; contour = contour->next)
		179	if (contours_overlap(contour, polygon) != GLU_NO_ERROR) {
		180	tess_call_user_error(tobj, GLU_TESS_ERROR5);
		181	return GLU_ERROR;
		182	}
		183	return GLU_NO_ERROR;
		184	}
		185
		186	static GLenum
		187	store_polygon_as_contour(GLUtriangulatorObj * tobj)
		188	{
		189	tess_polygon *polygon = tobj->current_polygon;
		190	tess_contour *contour = tobj->contours;
		191
		192	/* the first contour defined */
		193	if (contour == NULL) {
		194	if ((contour = (tess_contour *) malloc(sizeof(tess_contour))) == NULL) {
		195	tess_call_user_error(tobj, GLU_OUT_OF_MEMORY);
		196	free_current_polygon(polygon);
		197	return GLU_ERROR;
		198	}
		199	tobj->contours = tobj->last_contour = contour;
		200	contour->next = contour->previous = NULL;
		201	}
		202	else {
		203	if ((contour = (tess_contour *) malloc(sizeof(tess_contour))) == NULL) {
		204	tess_call_user_error(tobj, GLU_OUT_OF_MEMORY);
		205	free_current_polygon(polygon);
		206	return GLU_ERROR;
		207	}
		208	contour->previous = tobj->last_contour;
		209	tobj->last_contour->next = contour;
		210	tobj->last_contour = contour;
		211	contour->next = NULL;
		212	}
		213	/* mark all vertices in new contour as not special */
		214	/* and all are boundary edges */
		215	{
		216	tess_vertex *vertex;
		217	GLuint vertex_cnt, i;
		218
		219	for (vertex = polygon->vertices, i = 0, vertex_cnt =
		220	polygon->vertex_cnt; i < vertex_cnt; vertex = vertex->next, i++) {
		221	vertex->shadow_vertex = NULL;
		222	vertex->edge_flag = GL_TRUE;
		223	}
		224	}
		225	contour->vertex_cnt = polygon->vertex_cnt;
		226	contour->area = polygon->area;
		227	contour->orientation = polygon->orientation;
		228	contour->type = GLU_UNKNOWN;
		229	contour->vertices = polygon->vertices;
		230	contour->last_vertex = polygon->last_vertex;
		231	polygon->vertices = polygon->last_vertex = NULL;
		232	polygon->vertex_cnt = 0;
		233	++(tobj->contour_cnt);
		234	return GLU_NO_ERROR;
		235	}
		236
		237	static void
		238	free_current_polygon(tess_polygon * polygon)
		239	{
		240	tess_vertex vertex, vertex_tmp;
		241	GLuint i;
		242
		243	/* free current_polygon structures */
		244	for (vertex = polygon->vertices, i = 0; i < polygon->vertex_cnt; i++) {
		245	vertex_tmp = vertex->next;
		246	free(vertex);
		247	vertex = vertex_tmp;
		248	}
		249	polygon->vertices = polygon->last_vertex = NULL;
		250	polygon->vertex_cnt = 0;
		251	}
		252
		253	static void
		254	prepare_projection_info(GLUtriangulatorObj * tobj)
		255	{
		256	tess_polygon *polygon = tobj->current_polygon;
		257	tess_vertex vertex, last_vertex_ptr;
		258	GLdouble area;
		259
		260	last_vertex_ptr = polygon->last_vertex;
		261	switch (tobj->projection) {
		262	case OXY:
		263	for (vertex = polygon->vertices; vertex != last_vertex_ptr;
		264	vertex = vertex->next) {
		265	vertex->x = vertex->location[0];
		266	vertex->y = vertex->location[1];
		267	}
		268	last_vertex_ptr->x = last_vertex_ptr->location[0];
		269	last_vertex_ptr->y = last_vertex_ptr->location[1];
		270	break;
		271	case OXZ:
		272	for (vertex = polygon->vertices; vertex != last_vertex_ptr;
		273	vertex = vertex->next) {
		274	vertex->x = vertex->location[0];
		275	vertex->y = vertex->location[2];
		276	}
		277	last_vertex_ptr->x = last_vertex_ptr->location[0];
		278	last_vertex_ptr->y = last_vertex_ptr->location[2];
		279	break;
		280	case OYZ:
		281	for (vertex = polygon->vertices; vertex != last_vertex_ptr;
		282	vertex = vertex->next) {
		283	vertex->x = vertex->location[1];
		284	vertex->y = vertex->location[2];
		285	}
		286	last_vertex_ptr->x = last_vertex_ptr->location[1];
		287	last_vertex_ptr->y = last_vertex_ptr->location[2];
		288	break;
		289	}
		290	area = twice_the_polygon_area(polygon->vertices, polygon->last_vertex);
		291	if (area >= 0.0) {
		292	polygon->orientation = GLU_CCW;
		293	polygon->area = area;
		294	}
		295	else {
		296	polygon->orientation = GLU_CW;
		297	polygon->area = -area;
		298	}
		299	}
		300
		301	static GLdouble
		302	twice_the_polygon_area(tess_vertex * vertex, tess_vertex * last_vertex)
		303	{
		304	tess_vertex *next;
		305	GLdouble area, x, y;
		306
		307	area = 0.0;
		308	x = vertex->x;
		309	y = vertex->y;
		310	vertex = vertex->next;
		311	for (; vertex != last_vertex; vertex = vertex->next) {
		312	next = vertex->next;
		313	area +=
		314	(vertex->x - x) * (next->y - y) - (vertex->y - y) * (next->x - x);
		315	}
		316	return area;
		317	}
		318
		319	/* test if edges ab and cd intersect */
		320	/* if not return GLU_NO_ERROR, else if cross return GLU_TESS_ERROR8, */
		321	/* else if adjacent return GLU_TESS_ERROR4 */
		322	static GLenum
		323	edge_edge_intersect(tess_vertex * a,
		324	tess_vertex * b, tess_vertex * c, tess_vertex * d)
		325	{
		326	GLdouble denom, r, s;
		327	GLdouble xba, ydc, yba, xdc, yac, xac;
		328
		329	xba = b->x - a->x;
		330	yba = b->y - a->y;
		331	xdc = d->x - c->x;
		332	ydc = d->y - c->y;
		333	xac = a->x - c->x;
		334	yac = a->y - c->y;
		335	denom = xba * ydc - yba * xdc;
		336	r = yac * xdc - xac * ydc;
		337	/* parallel? */
		338	if (fabs(denom) < EPSILON) {
		339	if (fabs(r) < EPSILON) {
		340	/* colinear */
		341	if (fabs(xba) < EPSILON) {
		342	/* compare the Y coordinate */
		343	if (yba > 0.0) {
		344	if (
		345	(fabs(a->y - c->y) < EPSILON
		346	&& fabs(c->y - b->y) < EPSILON)
		347	\|\| (fabs(a->y - d->y) < EPSILON
		348	&& fabs(d->y - b->y) <
		349	EPSILON)) return GLU_TESS_ERROR4;
		350
		351	}
		352	else {
		353	if (
		354	(fabs(b->y - c->y) < EPSILON
		355	&& fabs(c->y - a->y) < EPSILON)
		356	\|\| (fabs(b->y - d->y) < EPSILON
		357	&& fabs(d->y - a->y) <
		358	EPSILON)) return GLU_TESS_ERROR4;
		359	}
		360	}
		361	else {
		362	/* compare the X coordinate */
		363	if (xba > 0.0) {
		364	if (
		365	(fabs(a->x - c->x) < EPSILON
		366	&& fabs(c->x - b->x) < EPSILON)
		367	\|\| (fabs(a->x - d->x) < EPSILON
		368	&& fabs(d->x - b->x) <
		369	EPSILON)) return GLU_TESS_ERROR4;
		370	}
		371	else {
		372	if (
		373	(fabs(b->x - c->x) < EPSILON
		374	&& fabs(c->x - a->x) < EPSILON)
		375	\|\| (fabs(b->x - d->x) < EPSILON
		376	&& fabs(d->x - a->x) <
		377	EPSILON)) return GLU_TESS_ERROR4;
		378	}
		379	}
		380	}
		381	return GLU_NO_ERROR;
		382	}
		383	r /= denom;
		384	s = (yac * xba - xac * yba) / denom;
		385	/* test if one vertex lies on other edge */
		386	if (((fabs(r) < EPSILON \|\| (r < 1.0 + EPSILON && r > 1.0 - EPSILON)) &&
		387	s > -EPSILON && s < 1.0 + EPSILON) \|\|
		388	((fabs(s) < EPSILON \|\| (s < 1.0 + EPSILON && s > 1.0 - EPSILON)) &&
		389	r > -EPSILON && r < 1.0 + EPSILON)) {
		390	return GLU_TESS_ERROR4;
		391	}
		392	/* test for crossing */
		393	if (r > -EPSILON && r < 1.0 + EPSILON && s > -EPSILON && s < 1.0 + EPSILON) {
		394	return GLU_TESS_ERROR8;
		395	}
		396	return GLU_NO_ERROR;
		397	}
		398
		399	static GLenum
		400	verify_edge_vertex_intersections(GLUtriangulatorObj * tobj)
		401	{
		402	tess_polygon *polygon = tobj->current_polygon;
		403	tess_vertex vertex1, last_vertex, *vertex2;
		404	GLenum test;
		405
		406	last_vertex = polygon->last_vertex;
		407	vertex1 = last_vertex;
		408	for (vertex2 = vertex1->next->next;
		409	vertex2->next != last_vertex; vertex2 = vertex2->next) {
		410	test = edge_edge_intersect(vertex1, vertex1->next, vertex2,
		411	vertex2->next);
		412	if (test != GLU_NO_ERROR) {
		413	tess_call_user_error(tobj, test);
		414	return GLU_ERROR;
		415	}
		416	}
		417	for (vertex1 = polygon->vertices;
		418	vertex1->next->next != last_vertex; vertex1 = vertex1->next) {
		419	for (vertex2 = vertex1->next->next;
		420	vertex2 != last_vertex; vertex2 = vertex2->next) {
		421	test = edge_edge_intersect(vertex1, vertex1->next, vertex2,
		422	vertex2->next);
		423	if (test != GLU_NO_ERROR) {
		424	tess_call_user_error(tobj, test);
		425	return GLU_ERROR;
		426	}
		427	}
		428	}
		429	return GLU_NO_ERROR;
		430	}
		431
		432	static int
		433	#ifdef WIN32
		434	__cdecl
		435	#endif
		436	area_compare(const void a, const void b)
		437	{
		438	GLdouble area1, area2;
		439
		440	area1 = (((tess_contour *) a))->area;
		441	area2 = (((tess_contour *) b))->area;
		442	if (area1 < area2)
		443	return 1;
		444	if (area1 > area2)
		445	return -1;
		446	return 0;
		447	}
		448
		449	void
		450	tess_find_contour_hierarchies(GLUtriangulatorObj * tobj)
		451	{
		452	tess_contour *contours; / dinamic array of pointers */
		453	tess_contour *tmp_contour_ptr = tobj->contours;
		454	GLuint cnt, i;
		455	GLenum result;
		456	GLboolean hierarchy_changed;
		457
		458	/* any contours? */
		459	if (tobj->contour_cnt < 2) {
		460	tobj->contours->type = GLU_EXTERIOR;
		461	return;
		462	}
		463	if ((contours = (tess_contour **)
		464	malloc(sizeof(tess_contour ) (tobj->contour_cnt))) == NULL) {
		465	tess_call_user_error(tobj, GLU_OUT_OF_MEMORY);
		466	return;
		467	}
		468	for (tmp_contour_ptr = tobj->contours, cnt = 0;
		469	tmp_contour_ptr != NULL; tmp_contour_ptr = tmp_contour_ptr->next)
		470	contours[cnt++] = tmp_contour_ptr;
		471	/* now sort the contours in decreasing area size order */
		472	qsort((void ) contours, (size_t) cnt, (size_t) sizeof(tess_contour ),
		473	area_compare);
		474	/* we leave just the first contour - remove others from list */
		475	tobj->contours = contours[0];
		476	tobj->contours->next = tobj->contours->previous = NULL;
		477	tobj->last_contour = tobj->contours;
		478	tobj->contour_cnt = 1;
		479	/* first contour is the one with greatest area */
		480	/* must be EXTERIOR */
		481	tobj->contours->type = GLU_EXTERIOR;
		482	tmp_contour_ptr = tobj->contours;
		483	/* now we play! */
		484	for (i = 1; i < cnt; i++) {
		485	hierarchy_changed = GL_FALSE;
		486	for (tmp_contour_ptr = tobj->contours;
		487	tmp_contour_ptr != NULL; tmp_contour_ptr = tmp_contour_ptr->next) {
		488	if (tmp_contour_ptr->type == GLU_EXTERIOR) {
		489	/* check if contour completely contained in EXTERIOR */
		490	result = is_contour_contained_in(tmp_contour_ptr, contours[i]);
		491	switch (result) {
		492	case GLU_INTERIOR:
		493	/* now we have to check if contour is inside interiors */
		494	/* or not */
		495	/* any interiors? */
		496	if (tmp_contour_ptr->next != NULL &&
		497	tmp_contour_ptr->next->type == GLU_INTERIOR) {
		498	/* for all interior, check if inside any of them */
		499	/* if not inside any of interiors, its another */
		500	/* interior */
		501	/* or it may contain some interiors, then change */
		502	/* the contained interiors to exterior ones */
		503	add_interior_with_hierarchy_check(tobj,
		504	tmp_contour_ptr,
		505	contours[i]);
		506	}
		507	else {
		508	/* not in interior, add as new interior contour */
		509	add_new_interior(tobj, tmp_contour_ptr, contours[i]);
		510	}
		511	hierarchy_changed = GL_TRUE;
		512	break;
		513	case GLU_EXTERIOR:
		514	/* ooops, the marked as EXTERIOR (contours[i]) is */
		515	/* actually an interior of tmp_contour_ptr */
		516	/* reverse the local hierarchy */
		517	reverse_hierarchy_and_add_exterior(tobj, tmp_contour_ptr,
		518	contours[i]);
		519	hierarchy_changed = GL_TRUE;
		520	break;
		521	case GLU_NO_ERROR:
		522	break;
		523	default:
		524	abort();
		525	}
		526	}
		527	if (hierarchy_changed)
		528	break; /* break from for loop */
		529	}
		530	if (hierarchy_changed == GL_FALSE) {
		531	/* disjoint with all contours, add to contour list */
		532	add_new_exterior(tobj, contours[i]);
		533	}
		534	}
		535	free(contours);
		536	}
		537
		538	/* returns GLU_INTERIOR if inner is completey enclosed within outer */
		539	/* returns GLU_EXTERIOR if outer is completely enclosed within inner */
		540	/* returns GLU_NO_ERROR if contours are disjoint */
		541	static GLenum
		542	is_contour_contained_in(tess_contour * outer, tess_contour * inner)
		543	{
		544	GLenum relation_flag;
		545
		546	/* set relation_flag to relation of containment of first inner vertex */
		547	/* regarding outer contour */
		548	if (point_in_polygon(outer, inner->vertices->x, inner->vertices->y))
		549	relation_flag = GLU_INTERIOR;
		550	else
		551	relation_flag = GLU_EXTERIOR;
		552	if (relation_flag == GLU_INTERIOR)
		553	return GLU_INTERIOR;
		554	if (point_in_polygon(inner, outer->vertices->x, outer->vertices->y))
		555	return GLU_EXTERIOR;
		556	return GLU_NO_ERROR;
		557	}
		558
		559	static GLboolean
		560	point_in_polygon(tess_contour * contour, GLdouble x, GLdouble y)
		561	{
		562	tess_vertex v1, v2;
		563	GLuint i, vertex_cnt;
		564	GLdouble xp1, yp1, xp2, yp2;
		565	GLboolean tst;
		566
		567	tst = GL_FALSE;
		568	v1 = contour->vertices;
		569	v2 = contour->vertices->previous;
		570	for (i = 0, vertex_cnt = contour->vertex_cnt; i < vertex_cnt; i++) {
		571	xp1 = v1->x;
		572	yp1 = v1->y;
		573	xp2 = v2->x;
		574	yp2 = v2->y;
		575	if ((((yp1 <= y) && (y < yp2)) \|\| ((yp2 <= y) && (y < yp1))) &&
		576	(x < (xp2 - xp1) * (y - yp1) / (yp2 - yp1) + xp1))
		577	tst = (tst == GL_FALSE ? GL_TRUE : GL_FALSE);
		578	v2 = v1;
		579	v1 = v1->next;
		580	}
		581	return tst;
		582	}
		583
		584	static GLenum
		585	contours_overlap(tess_contour * contour, tess_polygon * polygon)
		586	{
		587	tess_vertex vertex1, vertex2;
		588	GLuint vertex1_cnt, vertex2_cnt, i, j;
		589	GLenum test;
		590
		591	vertex1 = contour->vertices;
		592	vertex2 = polygon->vertices;
		593	vertex1_cnt = contour->vertex_cnt;
		594	vertex2_cnt = polygon->vertex_cnt;
		595	for (i = 0; i < vertex1_cnt; vertex1 = vertex1->next, i++) {
		596	for (j = 0; j < vertex2_cnt; vertex2 = vertex2->next, j++)
		597	if ((test = edge_edge_intersect(vertex1, vertex1->next, vertex2,
		598	vertex2->next)) != GLU_NO_ERROR)
		599	return test;
		600	}
		601	return GLU_NO_ERROR;
		602	}
		603
		604	static void
		605	add_new_exterior(GLUtriangulatorObj * tobj, tess_contour * contour)
		606	{
		607	contour->type = GLU_EXTERIOR;
		608	contour->next = NULL;
		609	contour->previous = tobj->last_contour;
		610	tobj->last_contour->next = contour;
		611	tobj->last_contour = contour;
		612	}
		613
		614	static void
		615	add_new_interior(GLUtriangulatorObj * tobj,
		616	tess_contour * outer, tess_contour * contour)
		617	{
		618	contour->type = GLU_INTERIOR;
		619	contour->next = outer->next;
		620	contour->previous = outer;
		621	if (outer->next != NULL)
		622	outer->next->previous = contour;
		623	outer->next = contour;
		624	if (tobj->last_contour == outer)
		625	tobj->last_contour = contour;
		626	}
		627
		628	static void
		629	add_interior_with_hierarchy_check(GLUtriangulatorObj * tobj,
		630	tess_contour * outer,
		631	tess_contour * contour)
		632	{
		633	tess_contour *ptr;
		634
		635	/* for all interiors of outer check if they are interior of contour */
		636	/* if so, change that interior to exterior and move it of of the */
		637	/* interior sequence */
		638	if (outer->next != NULL && outer->next->type == GLU_INTERIOR) {
		639	GLenum test;
		640
		641	for (ptr = outer->next; ptr != NULL && ptr->type == GLU_INTERIOR;
		642	ptr = ptr->next) {
		643	test = is_contour_contained_in(ptr, contour);
		644	switch (test) {
		645	case GLU_INTERIOR:
		646	/* contour is contained in one of the interiors */
		647	/* check if possibly contained in other exteriors */
		648	/* move ptr to first EXTERIOR */
		649	for (; ptr != NULL && ptr->type == GLU_INTERIOR; ptr = ptr->next);
		650	if (ptr == NULL)
		651	/* another exterior */
		652	add_new_exterior(tobj, contour);
		653	else
		654	add_exterior_with_check(tobj, ptr, contour);
		655	return;
		656	case GLU_EXTERIOR:
		657	/* one of the interiors is contained in the contour */
		658	/* change it to EXTERIOR, and shift it away from the */
		659	/* interior sequence */
		660	shift_interior_to_exterior(tobj, ptr);
		661	break;
		662	case GLU_NO_ERROR:
		663	/* disjoint */
		664	break;
		665	default:
		666	abort();
		667	}
		668	}
		669	}
		670	/* add contour to the interior sequence */
		671	add_new_interior(tobj, outer, contour);
		672	}
		673
		674	static void
		675	reverse_hierarchy_and_add_exterior(GLUtriangulatorObj * tobj,
		676	tess_contour * outer,
		677	tess_contour * contour)
		678	{
		679	tess_contour *ptr;
		680
		681	/* reverse INTERIORS to EXTERIORS */
		682	/* any INTERIORS? */
		683	if (outer->next != NULL && outer->next->type == GLU_INTERIOR)
		684	for (ptr = outer->next; ptr != NULL && ptr->type == GLU_INTERIOR;
		685	ptr = ptr->next) ptr->type = GLU_EXTERIOR;
		686	/* the outer now becomes inner */
		687	outer->type = GLU_INTERIOR;
		688	/* contour is the EXTERIOR */
		689	contour->next = outer;
		690	if (tobj->contours == outer) {
		691	/* first contour beeing reversed */
		692	contour->previous = NULL;
		693	tobj->contours = contour;
		694	}
		695	else {
		696	outer->previous->next = contour;
		697	contour->previous = outer->previous;
		698	}
		699	outer->previous = contour;
		700	}
		701
		702	static void
		703	shift_interior_to_exterior(GLUtriangulatorObj * tobj, tess_contour * contour)
		704	{
		705	contour->previous->next = contour->next;
		706	if (contour->next != NULL)
		707	contour->next->previous = contour->previous;
		708	else
		709	tobj->last_contour = contour->previous;
		710	}
		711
		712	static void
		713	add_exterior_with_check(GLUtriangulatorObj * tobj,
		714	tess_contour * outer, tess_contour * contour)
		715	{
		716	GLenum test;
		717
		718	/* this contour might be interior to further exteriors - check */
		719	/* if not, just add as a new exterior */
		720	for (; outer != NULL && outer->type == GLU_EXTERIOR; outer = outer->next) {
		721	test = is_contour_contained_in(outer, contour);
		722	switch (test) {
		723	case GLU_INTERIOR:
		724	/* now we have to check if contour is inside interiors */
		725	/* or not */
		726	/* any interiors? */
		727	if (outer->next != NULL && outer->next->type == GLU_INTERIOR) {
		728	/* for all interior, check if inside any of them */
		729	/* if not inside any of interiors, its another */
		730	/* interior */
		731	/* or it may contain some interiors, then change */
		732	/* the contained interiors to exterior ones */
		733	add_interior_with_hierarchy_check(tobj, outer, contour);
		734	}
		735	else {
		736	/* not in interior, add as new interior contour */
		737	add_new_interior(tobj, outer, contour);
		738	}
		739	return;
		740	case GLU_NO_ERROR:
		741	/* disjoint */
		742	break;
		743	default:
		744	abort();
		745	}
		746	}
		747	/* add contour to the exterior sequence */
		748	add_new_exterior(tobj, contour);
		749	}
		750
		751	void
		752	tess_handle_holes(GLUtriangulatorObj * tobj)
		753	{
		754	tess_contour contour, hole;
		755	GLenum exterior_orientation;
		756
		757	/* verify hole orientation */
		758	for (contour = tobj->contours; contour != NULL;) {
		759	exterior_orientation = contour->orientation;
		760	for (contour = contour->next;
		761	contour != NULL && contour->type == GLU_INTERIOR;
		762	contour = contour->next) {
		763	if (contour->orientation == exterior_orientation) {
		764	tess_call_user_error(tobj, GLU_TESS_ERROR5);
		765	return;
		766	}
		767	}
		768	}
		769	/* now cut-out holes */
		770	for (contour = tobj->contours; contour != NULL;) {
		771	hole = contour->next;
		772	while (hole != NULL && hole->type == GLU_INTERIOR) {
		773	if (cut_out_hole(tobj, contour, hole) == GLU_ERROR)
		774	return;
		775	hole = contour->next;
		776	}
		777	contour = contour->next;
		778	}
		779	}
		780
		781	static GLenum
		782	cut_out_hole(GLUtriangulatorObj * tobj,
		783	tess_contour * contour, tess_contour * hole)
		784	{
		785	tess_contour *tmp_hole;
		786	tess_vertex v1, v2, *tmp_vertex;
		787	GLuint vertex1_cnt, vertex2_cnt, tmp_vertex_cnt;
		788	GLuint i, j, k;
		789	GLenum test = 0;
		790
		791	/* find an edge connecting contour and hole not intersecting any other */
		792	/* edge belonging to either the contour or any of the other holes */
		793	for (v1 = contour->vertices, vertex1_cnt = contour->vertex_cnt, i = 0;
		794	i < vertex1_cnt; i++, v1 = v1->next) {
		795	for (v2 = hole->vertices, vertex2_cnt = hole->vertex_cnt, j = 0;
		796	j < vertex2_cnt; j++, v2 = v2->next) {
		797	/* does edge (v1,v2) intersect any edge of contour */
		798	for (tmp_vertex = contour->vertices, tmp_vertex_cnt =
		799	contour->vertex_cnt, k = 0; k < tmp_vertex_cnt;
		800	tmp_vertex = tmp_vertex->next, k++) {
		801	/* skip edge tests for edges directly connected */
		802	if (v1 == tmp_vertex \|\| v1 == tmp_vertex->next)
		803	continue;
		804	test = edge_edge_intersect(v1, v2, tmp_vertex, tmp_vertex->next);
		805	if (test != GLU_NO_ERROR)
		806	break;
		807	}
		808	if (test == GLU_NO_ERROR) {
		809	/* does edge (v1,v2) intersect any edge of hole */
		810	for (tmp_vertex = hole->vertices,
		811	tmp_vertex_cnt = hole->vertex_cnt, k = 0;
		812	k < tmp_vertex_cnt; tmp_vertex = tmp_vertex->next, k++) {
		813	/* skip edge tests for edges directly connected */
		814	if (v2 == tmp_vertex \|\| v2 == tmp_vertex->next)
		815	continue;
		816	test =
		817	edge_edge_intersect(v1, v2, tmp_vertex, tmp_vertex->next);
		818	if (test != GLU_NO_ERROR)
		819	break;
		820	}
		821	if (test == GLU_NO_ERROR) {
		822	/* does edge (v1,v2) intersect any other hole? */
		823	for (tmp_hole = hole->next;
		824	tmp_hole != NULL && tmp_hole->type == GLU_INTERIOR;
		825	tmp_hole = tmp_hole->next) {
		826	/* does edge (v1,v2) intersect any edge of hole */
		827	for (tmp_vertex = tmp_hole->vertices,
		828	tmp_vertex_cnt = tmp_hole->vertex_cnt, k = 0;
		829	k < tmp_vertex_cnt; tmp_vertex = tmp_vertex->next, k++) {
		830	test = edge_edge_intersect(v1, v2, tmp_vertex,
		831	tmp_vertex->next);
		832	if (test != GLU_NO_ERROR)
		833	break;
		834	}
		835	if (test != GLU_NO_ERROR)
		836	break;
		837	}
		838	}
		839	}
		840	if (test == GLU_NO_ERROR) {
		841	/* edge (v1,v2) is good for eliminating the hole */
		842	if (merge_hole_with_contour(tobj, contour, hole, v1, v2)
		843	== GLU_NO_ERROR)
		844	return GLU_NO_ERROR;
		845	else
		846	return GLU_ERROR;
		847	}
		848	}
		849	}
		850	/* other holes are blocking all possible connections of hole */
		851	/* with contour, we shift this hole as the last hole and retry */
		852	for (tmp_hole = hole;
		853	tmp_hole != NULL && tmp_hole->type == GLU_INTERIOR;
		854	tmp_hole = tmp_hole->next);
		855	contour->next = hole->next;
		856	hole->next->previous = contour;
		857	if (tmp_hole == NULL) {
		858	/* last EXTERIOR contour, shift hole as last contour */
		859	hole->next = NULL;
		860	hole->previous = tobj->last_contour;
		861	tobj->last_contour->next = hole;
		862	tobj->last_contour = hole;
		863	}
		864	else {
		865	tmp_hole->previous->next = hole;
		866	hole->previous = tmp_hole->previous;
		867	tmp_hole->previous = hole;
		868	hole->next = tmp_hole;
		869	}
		870	hole = contour->next;
		871	/* try once again - recurse */
		872	return cut_out_hole(tobj, contour, hole);
		873	}
		874
		875	static GLenum
		876	merge_hole_with_contour(GLUtriangulatorObj * tobj,
		877	tess_contour * contour,
		878	tess_contour * hole,
		879	tess_vertex * v1, tess_vertex * v2)
		880	{
		881	tess_vertex v1_new, v2_new;
		882
		883	/* make copies of v1 and v2, place them respectively after their originals */
		884	if ((v1_new = (tess_vertex *) malloc(sizeof(tess_vertex))) == NULL) {
		885	tess_call_user_error(tobj, GLU_OUT_OF_MEMORY);
		886	return GLU_ERROR;
		887	}
		888	if ((v2_new = (tess_vertex *) malloc(sizeof(tess_vertex))) == NULL) {
		889	tess_call_user_error(tobj, GLU_OUT_OF_MEMORY);
		890	return GLU_ERROR;
		891	}
		892	v1_new->edge_flag = GL_TRUE;
		893	v1_new->data = v1->data;
		894	v1_new->location[0] = v1->location[0];
		895	v1_new->location[1] = v1->location[1];
		896	v1_new->location[2] = v1->location[2];
		897	v1_new->x = v1->x;
		898	v1_new->y = v1->y;
		899	v1_new->shadow_vertex = v1;
		900	v1->shadow_vertex = v1_new;
		901	v1_new->next = v1->next;
		902	v1_new->previous = v1;
		903	v1->next->previous = v1_new;
		904	v1->next = v1_new;
		905	v2_new->edge_flag = GL_TRUE;
		906	v2_new->data = v2->data;
		907	v2_new->location[0] = v2->location[0];
		908	v2_new->location[1] = v2->location[1];
		909	v2_new->location[2] = v2->location[2];
		910	v2_new->x = v2->x;
		911	v2_new->y = v2->y;
		912	v2_new->shadow_vertex = v2;
		913	v2->shadow_vertex = v2_new;
		914	v2_new->next = v2->next;
		915	v2_new->previous = v2;
		916	v2->next->previous = v2_new;
		917	v2->next = v2_new;
		918	/* link together the two lists */
		919	v1->next = v2_new;
		920	v2_new->previous = v1;
		921	v2->next = v1_new;
		922	v1_new->previous = v2;
		923	/* update the vertex count of the contour */
		924	contour->vertex_cnt += hole->vertex_cnt + 2;
		925	/* remove the INTERIOR contour */
		926	contour->next = hole->next;
		927	if (hole->next != NULL)
		928	hole->next->previous = contour;
		929	free(hole);
		930	/* update tobj structure */
		931	--(tobj->contour_cnt);
		932	if (contour->last_vertex == v1)
		933	contour->last_vertex = v1_new;
		934	/* mark two vertices with edge_flag */
		935	v2->edge_flag = GL_FALSE;
		936	v1->edge_flag = GL_FALSE;
		937	return GLU_NO_ERROR;
		938	}

Subversion Repositories shark

(root)/shark/branches/xen/ports/mesa/src-glu/polytest.c - Rev 1618