An LGPL/GPL-licensed artwork library
You can not select more than 25 topics Topics must start with a letter or number, can include dashes ('-') and can be up to 35 characters long.

art_svp_intersect.c 45KB

12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152535455565758596061626364656667686970717273747576777879808182838485868788899091929394959697989910010110210310410510610710810911011111211311411511611711811912012112212312412512612712812913013113213313413513613713813914014114214314414514614714814915015115215315415515615715815916016116216316416516616716816917017117217317417517617717817918018118218318418518618718818919019119219319419519619719819920020120220320420520620720820921021121221321421521621721821922022122222322422522622722822923023123223323423523623723823924024124224324424524624724824925025125225325425525625725825926026126226326426526626726826927027127227327427527627727827928028128228328428528628728828929029129229329429529629729829930030130230330430530630730830931031131231331431531631731831932032132232332432532632732832933033133233333433533633733833934034134234334434534634734834935035135235335435535635735835936036136236336436536636736836937037137237337437537637737837938038138238338438538638738838939039139239339439539639739839940040140240340440540640740840941041141241341441541641741841942042142242342442542642742842943043143243343443543643743843944044144244344444544644744844945045145245345445545645745845946046146246346446546646746846947047147247347447547647747847948048148248348448548648748848949049149249349449549649749849950050150250350450550650750850951051151251351451551651751851952052152252352452552652752852953053153253353453553653753853954054154254354454554654754854955055155255355455555655755855956056156256356456556656756856957057157257357457557657757857958058158258358458558658758858959059159259359459559659759859960060160260360460560660760860961061161261361461561661761861962062162262362462562662762862963063163263363463563663763863964064164264364464564664764864965065165265365465565665765865966066166266366466566666766866967067167267367467567667767867968068168268368468568668768868969069169269369469569669769869970070170270370470570670770870971071171271371471571671771871972072172272372472572672772872973073173273373473573673773873974074174274374474574674774874975075175275375475575675775875976076176276376476576676776876977077177277377477577677777877978078178278378478578678778878979079179279379479579679779879980080180280380480580680780880981081181281381481581681781881982082182282382482582682782882983083183283383483583683783883984084184284384484584684784884985085185285385485585685785885986086186286386486586686786886987087187287387487587687787887988088188288388488588688788888989089189289389489589689789889990090190290390490590690790890991091191291391491591691791891992092192292392492592692792892993093193293393493593693793893994094194294394494594694794894995095195295395495595695795895996096196296396496596696796896997097197297397497597697797897998098198298398498598698798898999099199299399499599699799899910001001100210031004100510061007100810091010101110121013101410151016101710181019102010211022102310241025102610271028102910301031103210331034103510361037103810391040104110421043104410451046104710481049105010511052105310541055105610571058105910601061106210631064106510661067106810691070107110721073107410751076107710781079108010811082108310841085108610871088108910901091109210931094109510961097109810991100110111021103110411051106110711081109111011111112111311141115111611171118111911201121112211231124112511261127112811291130113111321133113411351136113711381139114011411142114311441145114611471148114911501151115211531154115511561157115811591160116111621163116411651166116711681169117011711172117311741175117611771178117911801181118211831184118511861187118811891190119111921193119411951196119711981199120012011202120312041205120612071208120912101211121212131214121512161217121812191220122112221223122412251226122712281229123012311232123312341235123612371238123912401241124212431244124512461247124812491250125112521253125412551256125712581259126012611262126312641265126612671268126912701271127212731274127512761277127812791280128112821283128412851286128712881289129012911292129312941295129612971298129913001301130213031304130513061307130813091310131113121313131413151316131713181319132013211322132313241325132613271328132913301331133213331334133513361337133813391340134113421343134413451346134713481349135013511352135313541355135613571358135913601361136213631364136513661367136813691370137113721373137413751376137713781379138013811382138313841385138613871388138913901391139213931394139513961397139813991400140114021403140414051406140714081409141014111412141314141415141614171418141914201421142214231424142514261427142814291430143114321433143414351436143714381439144014411442144314441445144614471448144914501451145214531454145514561457145814591460146114621463146414651466146714681469147014711472147314741475147614771478147914801481148214831484148514861487148814891490149114921493149414951496149714981499150015011502150315041505150615071508150915101511151215131514151515161517151815191520152115221523152415251526152715281529153015311532153315341535153615371538153915401541154215431544154515461547154815491550155115521553155415551556155715581559156015611562156315641565156615671568156915701571157215731574157515761577157815791580158115821583158415851586158715881589159015911592159315941595159615971598159916001601160216031604160516061607160816091610161116121613161416151616161716181619162016211622162316241625162616271628162916301631163216331634163516361637163816391640164116421643164416451646164716481649165016511652165316541655165616571658165916601661166216631664166516661667166816691670167116721673167416751676167716781679168016811682168316841685168616871688168916901691169216931694169516961697169816991700170117021703170417051706170717081709171017111712171317141715171617171718171917201721172217231724172517261727172817291730173117321733173417351736173717381739174017411742174317441745174617471748174917501751175217531754175517561757175817591760176117621763176417651766176717681769177017711772177317741775177617771778177917801781178217831784178517861787178817891790179117921793179417951796179717981799180018011802180318041805
  1. /* Libart_LGPL - library of basic graphic primitives
  2. * Copyright (C) 2001 Raph Levien
  3. *
  4. * This library is free software; you can redistribute it and/or
  5. * modify it under the terms of the GNU Library General Public
  6. * License as published by the Free Software Foundation; either
  7. * version 2 of the License, or (at your option) any later version.
  8. *
  9. * This library is distributed in the hope that it will be useful,
  10. * but WITHOUT ANY WARRANTY; without even the implied warranty of
  11. * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
  12. * Library General Public License for more details.
  13. *
  14. * You should have received a copy of the GNU Library General Public
  15. * License along with this library; if not, write to the
  16. * Free Software Foundation, Inc., 59 Temple Place - Suite 330,
  17. * Boston, MA 02111-1307, USA.
  18. */
  19. /* This file contains a testbed implementation of the new intersection
  20. code.
  21. */
  22. #include "config.h"
  23. #include "art_svp_intersect.h"
  24. #include <math.h> /* for sqrt */
  25. /* Sanitychecking verifies the main invariant on every priority queue
  26. point. Do not use in production, as it slows things down way too
  27. much. */
  28. #define noSANITYCHECK
  29. /* This can be used in production, to prevent hangs. Eventually, it
  30. should not be necessary. */
  31. #define CHEAP_SANITYCHECK
  32. #define noVERBOSE
  33. #include "art_misc.h"
  34. /* A priority queue - perhaps move to a separate file if it becomes
  35. needed somewhere else */
  36. #define ART_PRIQ_USE_HEAP
  37. typedef struct _ArtPriQ ArtPriQ;
  38. typedef struct _ArtPriPoint ArtPriPoint;
  39. struct _ArtPriQ {
  40. int n_items;
  41. int n_items_max;
  42. ArtPriPoint **items;
  43. };
  44. struct _ArtPriPoint {
  45. double x;
  46. double y;
  47. void *user_data;
  48. };
  49. static ArtPriQ *
  50. art_pri_new (void)
  51. {
  52. ArtPriQ *result = art_new (ArtPriQ, 1);
  53. result->n_items = 0;
  54. result->n_items_max = 16;
  55. result->items = art_new (ArtPriPoint *, result->n_items_max);
  56. return result;
  57. }
  58. static void
  59. art_pri_free (ArtPriQ *pq)
  60. {
  61. art_free (pq->items);
  62. art_free (pq);
  63. }
  64. static art_boolean
  65. art_pri_empty (ArtPriQ *pq)
  66. {
  67. return pq->n_items == 0;
  68. }
  69. #ifdef ART_PRIQ_USE_HEAP
  70. /* This heap implementation is based on Vasek Chvatal's course notes:
  71. http://www.cs.rutgers.edu/~chvatal/notes/pq.html#heap */
  72. static void
  73. art_pri_bubble_up (ArtPriQ *pq, int vacant, ArtPriPoint *missing)
  74. {
  75. ArtPriPoint **items = pq->items;
  76. int parent;
  77. parent = (vacant - 1) >> 1;
  78. while (vacant > 0 && (missing->y < items[parent]->y ||
  79. (missing->y == items[parent]->y &&
  80. missing->x < items[parent]->x)))
  81. {
  82. items[vacant] = items[parent];
  83. vacant = parent;
  84. parent = (vacant - 1) >> 1;
  85. }
  86. items[vacant] = missing;
  87. }
  88. static void
  89. art_pri_insert (ArtPriQ *pq, ArtPriPoint *point)
  90. {
  91. if (pq->n_items == pq->n_items_max)
  92. art_expand (pq->items, ArtPriPoint *, pq->n_items_max);
  93. art_pri_bubble_up (pq, pq->n_items++, point);
  94. }
  95. static void
  96. art_pri_sift_down_from_root (ArtPriQ *pq, ArtPriPoint *missing)
  97. {
  98. ArtPriPoint **items = pq->items;
  99. int vacant = 0, child = 2;
  100. int n = pq->n_items;
  101. while (child < n)
  102. {
  103. if (items[child - 1]->y < items[child]->y ||
  104. (items[child - 1]->y == items[child]->y &&
  105. items[child - 1]->x < items[child]->x))
  106. child--;
  107. items[vacant] = items[child];
  108. vacant = child;
  109. child = (vacant + 1) << 1;
  110. }
  111. if (child == n)
  112. {
  113. items[vacant] = items[n - 1];
  114. vacant = n - 1;
  115. }
  116. art_pri_bubble_up (pq, vacant, missing);
  117. }
  118. static ArtPriPoint *
  119. art_pri_choose (ArtPriQ *pq)
  120. {
  121. ArtPriPoint *result = pq->items[0];
  122. art_pri_sift_down_from_root (pq, pq->items[--pq->n_items]);
  123. return result;
  124. }
  125. #else
  126. /* Choose least point in queue */
  127. static ArtPriPoint *
  128. art_pri_choose (ArtPriQ *pq)
  129. {
  130. int i;
  131. int best = 0;
  132. double best_x, best_y;
  133. double y;
  134. ArtPriPoint *result;
  135. if (pq->n_items == 0)
  136. return NULL;
  137. best_x = pq->items[best]->x;
  138. best_y = pq->items[best]->y;
  139. for (i = 1; i < pq->n_items; i++)
  140. {
  141. y = pq->items[i]->y;
  142. if (y < best_y || (y == best_y && pq->items[i]->x < best_x))
  143. {
  144. best = i;
  145. best_x = pq->items[best]->x;
  146. best_y = y;
  147. }
  148. }
  149. result = pq->items[best];
  150. pq->items[best] = pq->items[--pq->n_items];
  151. return result;
  152. }
  153. static void
  154. art_pri_insert (ArtPriQ *pq, ArtPriPoint *point)
  155. {
  156. if (pq->n_items == pq->n_items_max)
  157. art_expand (pq->items, ArtPriPoint *, pq->n_items_max);
  158. pq->items[pq->n_items++] = point;
  159. }
  160. #endif
  161. #ifdef TEST_PRIQ
  162. #include <stdlib.h> /* for rand() */
  163. #include <stdio.h>
  164. static double
  165. double_rand (double lo, double hi, int quant)
  166. {
  167. int tmp = rand () / (RAND_MAX * (1.0 / quant)) + 0.5;
  168. return lo + tmp * ((hi - lo) / quant);
  169. }
  170. /*
  171. * This custom allocator for priority queue points is here so I can
  172. * test speed. It doesn't look like it will be that significant, but
  173. * if I want a small improvement later, it's something.
  174. */
  175. typedef ArtPriPoint *ArtPriPtPool;
  176. static ArtPriPtPool *
  177. art_pri_pt_pool_new (void)
  178. {
  179. ArtPriPtPool *result = art_new (ArtPriPtPool, 1);
  180. *result = NULL;
  181. return result;
  182. }
  183. static ArtPriPoint *
  184. art_pri_pt_alloc (ArtPriPtPool *pool)
  185. {
  186. ArtPriPoint *result = *pool;
  187. if (result == NULL)
  188. return art_new (ArtPriPoint, 1);
  189. else
  190. {
  191. *pool = result->user_data;
  192. return result;
  193. }
  194. }
  195. static void
  196. art_pri_pt_free (ArtPriPtPool *pool, ArtPriPoint *pt)
  197. {
  198. pt->user_data = *pool;
  199. *pool = pt;
  200. }
  201. static void
  202. art_pri_pt_pool_free (ArtPriPtPool *pool)
  203. {
  204. ArtPriPoint *pt = *pool;
  205. while (pt != NULL)
  206. {
  207. ArtPriPoint *next = pt->user_data;
  208. art_free (pt);
  209. pt = next;
  210. }
  211. art_free (pool);
  212. }
  213. int
  214. main (int argc, char **argv)
  215. {
  216. ArtPriPtPool *pool = art_pri_pt_pool_new ();
  217. ArtPriQ *pq;
  218. int i, j;
  219. const int n_iter = 1;
  220. const int pq_size = 100;
  221. for (j = 0; j < n_iter; j++)
  222. {
  223. pq = art_pri_new ();
  224. for (i = 0; i < pq_size; i++)
  225. {
  226. ArtPriPoint *pt = art_pri_pt_alloc (pool);
  227. pt->x = double_rand (0, 1, 100);
  228. pt->y = double_rand (0, 1, 100);
  229. pt->user_data = (void *)i;
  230. art_pri_insert (pq, pt);
  231. }
  232. while (!art_pri_empty (pq))
  233. {
  234. ArtPriPoint *pt = art_pri_choose (pq);
  235. if (n_iter == 1)
  236. printf ("(%g, %g), %d\n", pt->x, pt->y, (int)pt->user_data);
  237. art_pri_pt_free (pool, pt);
  238. }
  239. art_pri_free (pq);
  240. }
  241. art_pri_pt_pool_free (pool);
  242. return 0;
  243. }
  244. #else /* TEST_PRIQ */
  245. /* A virtual class for an "svp writer". A client of this object creates an
  246. SVP by repeatedly calling "add segment" and "add point" methods on it.
  247. */
  248. typedef struct _ArtSvpWriterRewind ArtSvpWriterRewind;
  249. /* An implementation of the svp writer virtual class that applies the
  250. winding rule. */
  251. struct _ArtSvpWriterRewind {
  252. ArtSvpWriter super;
  253. ArtWindRule rule;
  254. ArtSVP *svp;
  255. int n_segs_max;
  256. int *n_points_max;
  257. };
  258. static int
  259. art_svp_writer_rewind_add_segment (ArtSvpWriter *self, int wind_left,
  260. int delta_wind, double x, double y)
  261. {
  262. ArtSvpWriterRewind *swr = (ArtSvpWriterRewind *)self;
  263. ArtSVP *svp;
  264. ArtSVPSeg *seg;
  265. art_boolean left_filled, right_filled;
  266. int wind_right = wind_left + delta_wind;
  267. int seg_num;
  268. const int init_n_points_max = 4;
  269. switch (swr->rule)
  270. {
  271. case ART_WIND_RULE_NONZERO:
  272. left_filled = (wind_left != 0);
  273. right_filled = (wind_right != 0);
  274. break;
  275. case ART_WIND_RULE_INTERSECT:
  276. left_filled = (wind_left > 1);
  277. right_filled = (wind_right > 1);
  278. break;
  279. case ART_WIND_RULE_ODDEVEN:
  280. left_filled = (wind_left & 1);
  281. right_filled = (wind_right & 1);
  282. break;
  283. case ART_WIND_RULE_POSITIVE:
  284. left_filled = (wind_left > 0);
  285. right_filled = (wind_right > 0);
  286. break;
  287. default:
  288. art_die ("Unknown wind rule %d\n", swr->rule);
  289. }
  290. if (left_filled == right_filled)
  291. {
  292. /* discard segment now */
  293. #ifdef VERBOSE
  294. art_dprint ("swr add_segment: %d += %d (%g, %g) --> -1\n",
  295. wind_left, delta_wind, x, y);
  296. #endif
  297. return -1;
  298. }
  299. svp = swr->svp;
  300. seg_num = svp->n_segs++;
  301. if (swr->n_segs_max == seg_num)
  302. {
  303. swr->n_segs_max <<= 1;
  304. svp = (ArtSVP *)art_realloc (svp, sizeof(ArtSVP) +
  305. (swr->n_segs_max - 1) *
  306. sizeof(ArtSVPSeg));
  307. swr->svp = svp;
  308. swr->n_points_max = art_renew (swr->n_points_max, int,
  309. swr->n_segs_max);
  310. }
  311. seg = &svp->segs[seg_num];
  312. seg->n_points = 1;
  313. seg->dir = right_filled;
  314. swr->n_points_max[seg_num] = init_n_points_max;
  315. seg->bbox.x0 = x;
  316. seg->bbox.y0 = y;
  317. seg->bbox.x1 = x;
  318. seg->bbox.y1 = y;
  319. seg->points = art_new (ArtPoint, init_n_points_max);
  320. seg->points[0].x = x;
  321. seg->points[0].y = y;
  322. #ifdef VERBOSE
  323. art_dprint ("swr add_segment: %d += %d (%g, %g) --> %d(%s)\n",
  324. wind_left, delta_wind, x, y, seg_num,
  325. seg->dir ? "v" : "^");
  326. #endif
  327. return seg_num;
  328. }
  329. static void
  330. art_svp_writer_rewind_add_point (ArtSvpWriter *self, int seg_id,
  331. double x, double y)
  332. {
  333. ArtSvpWriterRewind *swr = (ArtSvpWriterRewind *)self;
  334. ArtSVPSeg *seg;
  335. int n_points;
  336. #ifdef VERBOSE
  337. art_dprint ("swr add_point: %d (%g, %g)\n", seg_id, x, y);
  338. #endif
  339. if (seg_id < 0)
  340. /* omitted segment */
  341. return;
  342. seg = &swr->svp->segs[seg_id];
  343. n_points = seg->n_points++;
  344. if (swr->n_points_max[seg_id] == n_points)
  345. art_expand (seg->points, ArtPoint, swr->n_points_max[seg_id]);
  346. seg->points[n_points].x = x;
  347. seg->points[n_points].y = y;
  348. if (x < seg->bbox.x0)
  349. seg->bbox.x0 = x;
  350. if (x > seg->bbox.x1)
  351. seg->bbox.x1 = x;
  352. seg->bbox.y1 = y;
  353. }
  354. static void
  355. art_svp_writer_rewind_close_segment (ArtSvpWriter *self, int seg_id)
  356. {
  357. /* Not needed for this simple implementation. A potential future
  358. optimization is to merge segments that can be merged safely. */
  359. #ifdef SANITYCHECK
  360. ArtSvpWriterRewind *swr = (ArtSvpWriterRewind *)self;
  361. ArtSVPSeg *seg;
  362. if (seg_id >= 0)
  363. {
  364. seg = &swr->svp->segs[seg_id];
  365. if (seg->n_points < 2)
  366. art_warn ("*** closing segment %d with only %d point%s\n",
  367. seg_id, seg->n_points, seg->n_points == 1 ? "" : "s");
  368. }
  369. #endif
  370. #ifdef VERBOSE
  371. art_dprint ("swr close_segment: %d\n", seg_id);
  372. #endif
  373. }
  374. ArtSVP *
  375. art_svp_writer_rewind_reap (ArtSvpWriter *self)
  376. {
  377. ArtSvpWriterRewind *swr = (ArtSvpWriterRewind *)self;
  378. ArtSVP *result = swr->svp;
  379. art_free (swr->n_points_max);
  380. art_free (swr);
  381. return result;
  382. }
  383. ArtSvpWriter *
  384. art_svp_writer_rewind_new (ArtWindRule rule)
  385. {
  386. ArtSvpWriterRewind *result = art_new (ArtSvpWriterRewind, 1);
  387. result->super.add_segment = art_svp_writer_rewind_add_segment;
  388. result->super.add_point = art_svp_writer_rewind_add_point;
  389. result->super.close_segment = art_svp_writer_rewind_close_segment;
  390. result->rule = rule;
  391. result->n_segs_max = 16;
  392. result->svp = art_alloc (sizeof(ArtSVP) +
  393. (result->n_segs_max - 1) * sizeof(ArtSVPSeg));
  394. result->svp->n_segs = 0;
  395. result->n_points_max = art_new (int, result->n_segs_max);
  396. return &result->super;
  397. }
  398. /* Now, data structures for the active list */
  399. typedef struct _ArtActiveSeg ArtActiveSeg;
  400. /* Note: BNEG is 1 for \ lines, and 0 for /. Thus,
  401. x[(flags & BNEG) ^ 1] <= x[flags & BNEG] */
  402. #define ART_ACTIVE_FLAGS_BNEG 1
  403. /* This flag is set if the segment has been inserted into the active
  404. list. */
  405. #define ART_ACTIVE_FLAGS_IN_ACTIVE 2
  406. /* This flag is set when the segment is to be deleted in the
  407. horiz commit process. */
  408. #define ART_ACTIVE_FLAGS_DEL 4
  409. /* This flag is set if the seg_id is a valid output segment. */
  410. #define ART_ACTIVE_FLAGS_OUT 8
  411. /* This flag is set if the segment is in the horiz list. */
  412. #define ART_ACTIVE_FLAGS_IN_HORIZ 16
  413. struct _ArtActiveSeg {
  414. int flags;
  415. int wind_left, delta_wind;
  416. ArtActiveSeg *left, *right; /* doubly linked list structure */
  417. const ArtSVPSeg *in_seg;
  418. int in_curs;
  419. double x[2];
  420. double y0, y1;
  421. double a, b, c; /* line equation; ax+by+c = 0 for the line, a^2 + b^2 = 1,
  422. and a>0 */
  423. /* bottom point and intersection point stack */
  424. int n_stack;
  425. int n_stack_max;
  426. ArtPoint *stack;
  427. /* horiz commit list */
  428. ArtActiveSeg *horiz_left, *horiz_right;
  429. double horiz_x;
  430. int horiz_delta_wind;
  431. int seg_id;
  432. };
  433. typedef struct _ArtIntersectCtx ArtIntersectCtx;
  434. struct _ArtIntersectCtx {
  435. const ArtSVP *in;
  436. ArtSvpWriter *out;
  437. ArtPriQ *pq;
  438. ArtActiveSeg *active_head;
  439. double y;
  440. ArtActiveSeg *horiz_first;
  441. ArtActiveSeg *horiz_last;
  442. /* segment index of next input segment to be added to pri q */
  443. int in_curs;
  444. };
  445. #define EPSILON_A 1e-5 /* Threshold for breaking lines at point insertions */
  446. /**
  447. * art_svp_intersect_setup_seg: Set up an active segment from input segment.
  448. * @seg: Active segment.
  449. * @pri_pt: Priority queue point to initialize.
  450. *
  451. * Sets the x[], a, b, c, flags, and stack fields according to the
  452. * line from the current cursor value. Sets the priority queue point
  453. * to the bottom point of this line. Also advances the input segment
  454. * cursor.
  455. **/
  456. static void
  457. art_svp_intersect_setup_seg (ArtActiveSeg *seg, ArtPriPoint *pri_pt)
  458. {
  459. const ArtSVPSeg *in_seg = seg->in_seg;
  460. int in_curs = seg->in_curs++;
  461. double x0, y0, x1, y1;
  462. double dx, dy, s;
  463. double a, b, r2;
  464. x0 = in_seg->points[in_curs].x;
  465. y0 = in_seg->points[in_curs].y;
  466. x1 = in_seg->points[in_curs + 1].x;
  467. y1 = in_seg->points[in_curs + 1].y;
  468. pri_pt->x = x1;
  469. pri_pt->y = y1;
  470. dx = x1 - x0;
  471. dy = y1 - y0;
  472. r2 = dx * dx + dy * dy;
  473. s = r2 == 0 ? 1 : 1 / sqrt (r2);
  474. seg->a = a = dy * s;
  475. seg->b = b = -dx * s;
  476. seg->c = -(a * x0 + b * y0);
  477. seg->flags = (seg->flags & ~ART_ACTIVE_FLAGS_BNEG) | (dx > 0);
  478. seg->x[0] = x0;
  479. seg->x[1] = x1;
  480. seg->y0 = y0;
  481. seg->y1 = y1;
  482. seg->n_stack = 1;
  483. seg->stack[0].x = x1;
  484. seg->stack[0].y = y1;
  485. }
  486. /**
  487. * art_svp_intersect_add_horiz: Add point to horizontal list.
  488. * @ctx: Intersector context.
  489. * @seg: Segment with point to insert into horizontal list.
  490. *
  491. * Inserts @seg into horizontal list, keeping it in ascending horiz_x
  492. * order.
  493. *
  494. * Note: the horiz_commit routine processes "clusters" of segs in the
  495. * horiz list, all sharing the same horiz_x value. The cluster is
  496. * processed in active list order, rather than horiz list order. Thus,
  497. * the order of segs in the horiz list sharing the same horiz_x
  498. * _should_ be irrelevant. Even so, we use b as a secondary sorting key,
  499. * as a "belt and suspenders" defensive coding tactic.
  500. **/
  501. static void
  502. art_svp_intersect_add_horiz (ArtIntersectCtx *ctx, ArtActiveSeg *seg)
  503. {
  504. ArtActiveSeg **pp = &ctx->horiz_last;
  505. ArtActiveSeg *place;
  506. ArtActiveSeg *place_right = NULL;
  507. #ifdef CHEAP_SANITYCHECK
  508. if (seg->flags & ART_ACTIVE_FLAGS_IN_HORIZ)
  509. {
  510. #ifdef VERBOSE
  511. art_warn ("*** attempt to put segment in horiz list twice\n");
  512. #endif
  513. return;
  514. }
  515. seg->flags |= ART_ACTIVE_FLAGS_IN_HORIZ;
  516. #endif
  517. #ifdef VERBOSE
  518. art_dprint ("add_horiz %lx, x = %g\n", (unsigned long) seg, seg->horiz_x);
  519. #endif
  520. for (place = *pp; place != NULL && (place->horiz_x > seg->horiz_x ||
  521. (place->horiz_x == seg->horiz_x &&
  522. place->b < seg->b));
  523. place = *pp)
  524. {
  525. place_right = place;
  526. pp = &place->horiz_left;
  527. }
  528. *pp = seg;
  529. seg->horiz_left = place;
  530. seg->horiz_right = place_right;
  531. if (place == NULL)
  532. ctx->horiz_first = seg;
  533. else
  534. place->horiz_right = seg;
  535. }
  536. static void
  537. art_svp_intersect_push_pt (ArtIntersectCtx *ctx, ArtActiveSeg *seg,
  538. double x, double y)
  539. {
  540. ArtPriPoint *pri_pt;
  541. int n_stack = seg->n_stack;
  542. if (n_stack == seg->n_stack_max)
  543. art_expand (seg->stack, ArtPoint, seg->n_stack_max);
  544. seg->stack[n_stack].x = x;
  545. seg->stack[n_stack].y = y;
  546. seg->n_stack++;
  547. seg->x[1] = x;
  548. seg->y1 = y;
  549. pri_pt = art_new (ArtPriPoint, 1);
  550. pri_pt->x = x;
  551. pri_pt->y = y;
  552. pri_pt->user_data = seg;
  553. art_pri_insert (ctx->pq, pri_pt);
  554. }
  555. typedef enum {
  556. ART_BREAK_LEFT = 1,
  557. ART_BREAK_RIGHT = 2
  558. } ArtBreakFlags;
  559. /**
  560. * art_svp_intersect_break: Break an active segment.
  561. *
  562. * Note: y must be greater than the top point's y, and less than
  563. * the bottom's.
  564. *
  565. * Return value: x coordinate of break point.
  566. */
  567. static double
  568. art_svp_intersect_break (ArtIntersectCtx *ctx, ArtActiveSeg *seg,
  569. double x_ref, double y, ArtBreakFlags break_flags)
  570. {
  571. double x0, y0, x1, y1;
  572. const ArtSVPSeg *in_seg = seg->in_seg;
  573. int in_curs = seg->in_curs;
  574. double x;
  575. x0 = in_seg->points[in_curs - 1].x;
  576. y0 = in_seg->points[in_curs - 1].y;
  577. x1 = in_seg->points[in_curs].x;
  578. y1 = in_seg->points[in_curs].y;
  579. x = x0 + (x1 - x0) * ((y - y0) / (y1 - y0));
  580. if ((break_flags == ART_BREAK_LEFT && x > x_ref) ||
  581. (break_flags == ART_BREAK_RIGHT && x < x_ref))
  582. {
  583. #ifdef VERBOSE
  584. art_dprint ("art_svp_intersect_break: limiting x to %f, was %f, %s\n",
  585. x_ref, x, break_flags == ART_BREAK_LEFT ? "left" : "right");
  586. x = x_ref;
  587. #endif
  588. }
  589. /* I think we can count on min(x0, x1) <= x <= max(x0, x1) with sane
  590. arithmetic, but it might be worthwhile to check just in case. */
  591. if (y > ctx->y)
  592. art_svp_intersect_push_pt (ctx, seg, x, y);
  593. else
  594. {
  595. seg->x[0] = x;
  596. seg->y0 = y;
  597. seg->horiz_x = x;
  598. art_svp_intersect_add_horiz (ctx, seg);
  599. }
  600. return x;
  601. }
  602. /**
  603. * art_svp_intersect_add_point: Add a point, breaking nearby neighbors.
  604. * @ctx: Intersector context.
  605. * @x: X coordinate of point to add.
  606. * @y: Y coordinate of point to add.
  607. * @seg: "nearby" segment, or NULL if leftmost.
  608. *
  609. * Return value: Segment immediately to the left of the new point, or
  610. * NULL if the new point is leftmost.
  611. **/
  612. static ArtActiveSeg *
  613. art_svp_intersect_add_point (ArtIntersectCtx *ctx, double x, double y,
  614. ArtActiveSeg *seg, ArtBreakFlags break_flags)
  615. {
  616. ArtActiveSeg *left, *right;
  617. double x_min = x, x_max = x;
  618. art_boolean left_live, right_live;
  619. double d;
  620. double new_x;
  621. ArtActiveSeg *test, *result = NULL;
  622. double x_test;
  623. left = seg;
  624. if (left == NULL)
  625. right = ctx->active_head;
  626. else
  627. right = left->right;
  628. left_live = (break_flags & ART_BREAK_LEFT) && (left != NULL);
  629. right_live = (break_flags & ART_BREAK_RIGHT) && (right != NULL);
  630. while (left_live || right_live)
  631. {
  632. if (left_live)
  633. {
  634. if (x <= left->x[left->flags & ART_ACTIVE_FLAGS_BNEG] &&
  635. /* It may be that one of these conjuncts turns out to be always
  636. true. We test both anyway, to be defensive. */
  637. y != left->y0 && y < left->y1)
  638. {
  639. d = x_min * left->a + y * left->b + left->c;
  640. if (d < EPSILON_A)
  641. {
  642. new_x = art_svp_intersect_break (ctx, left, x_min, y,
  643. ART_BREAK_LEFT);
  644. if (new_x > x_max)
  645. {
  646. x_max = new_x;
  647. right_live = (right != NULL);
  648. }
  649. else if (new_x < x_min)
  650. x_min = new_x;
  651. left = left->left;
  652. left_live = (left != NULL);
  653. }
  654. else
  655. left_live = ART_FALSE;
  656. }
  657. else
  658. left_live = ART_FALSE;
  659. }
  660. else if (right_live)
  661. {
  662. if (x >= right->x[(right->flags & ART_ACTIVE_FLAGS_BNEG) ^ 1] &&
  663. /* It may be that one of these conjuncts turns out to be always
  664. true. We test both anyway, to be defensive. */
  665. y != right->y0 && y < right->y1)
  666. {
  667. d = x_max * right->a + y * right->b + right->c;
  668. if (d > -EPSILON_A)
  669. {
  670. new_x = art_svp_intersect_break (ctx, right, x_max, y,
  671. ART_BREAK_RIGHT);
  672. if (new_x < x_min)
  673. {
  674. x_min = new_x;
  675. left_live = (left != NULL);
  676. }
  677. else if (new_x >= x_max)
  678. x_max = new_x;
  679. right = right->right;
  680. right_live = (right != NULL);
  681. }
  682. else
  683. right_live = ART_FALSE;
  684. }
  685. else
  686. right_live = ART_FALSE;
  687. }
  688. }
  689. /* Ascending order is guaranteed by break_flags. Thus, we don't need
  690. to actually fix up non-ascending pairs. */
  691. /* Now, (left, right) defines an interval of segments broken. Sort
  692. into ascending x order. */
  693. test = left == NULL ? ctx->active_head : left->right;
  694. result = left;
  695. if (test != NULL && test != right)
  696. {
  697. if (y == test->y0)
  698. x_test = test->x[0];
  699. else /* assert y == test->y1, I think */
  700. x_test = test->x[1];
  701. for (;;)
  702. {
  703. if (x_test <= x)
  704. result = test;
  705. test = test->right;
  706. if (test == right)
  707. break;
  708. new_x = x_test;
  709. if (new_x < x_test)
  710. {
  711. art_warn ("art_svp_intersect_add_point: non-ascending x\n");
  712. }
  713. x_test = new_x;
  714. }
  715. }
  716. return result;
  717. }
  718. static void
  719. art_svp_intersect_swap_active (ArtIntersectCtx *ctx,
  720. ArtActiveSeg *left_seg, ArtActiveSeg *right_seg)
  721. {
  722. right_seg->left = left_seg->left;
  723. if (right_seg->left != NULL)
  724. right_seg->left->right = right_seg;
  725. else
  726. ctx->active_head = right_seg;
  727. left_seg->right = right_seg->right;
  728. if (left_seg->right != NULL)
  729. left_seg->right->left = left_seg;
  730. left_seg->left = right_seg;
  731. right_seg->right = left_seg;
  732. }
  733. /**
  734. * art_svp_intersect_test_cross: Test crossing of a pair of active segments.
  735. * @ctx: Intersector context.
  736. * @left_seg: Left segment of the pair.
  737. * @right_seg: Right segment of the pair.
  738. * @break_flags: Flags indicating whether to break neighbors.
  739. *
  740. * Tests crossing of @left_seg and @right_seg. If there is a crossing,
  741. * inserts the intersection point into both segments.
  742. *
  743. * Return value: True if the intersection took place at the current
  744. * scan line, indicating further iteration is needed.
  745. **/
  746. static art_boolean
  747. art_svp_intersect_test_cross (ArtIntersectCtx *ctx,
  748. ArtActiveSeg *left_seg, ArtActiveSeg *right_seg,
  749. ArtBreakFlags break_flags)
  750. {
  751. double left_x0, left_y0, left_x1;
  752. double left_y1 = left_seg->y1;
  753. double right_y1 = right_seg->y1;
  754. double d;
  755. const ArtSVPSeg *in_seg;
  756. int in_curs;
  757. double d0, d1, t;
  758. double x, y; /* intersection point */
  759. #ifdef VERBOSE
  760. static int count = 0;
  761. art_dprint ("art_svp_intersect_test_cross %lx <-> %lx: count=%d\n",
  762. (unsigned long)left_seg, (unsigned long)right_seg, count++);
  763. #endif
  764. if (left_seg->y0 == right_seg->y0 && left_seg->x[0] == right_seg->x[0])
  765. {
  766. /* Top points of left and right segments coincide. This case
  767. feels like a bit of duplication - we may want to merge it
  768. with the cases below. However, this way, we're sure that this
  769. logic makes only localized changes. */
  770. if (left_y1 < right_y1)
  771. {
  772. /* Test left (x1, y1) against right segment */
  773. double left_x1 = left_seg->x[1];
  774. if (left_x1 <
  775. right_seg->x[(right_seg->flags & ART_ACTIVE_FLAGS_BNEG) ^ 1] ||
  776. left_y1 == right_seg->y0)
  777. return ART_FALSE;
  778. d = left_x1 * right_seg->a + left_y1 * right_seg->b + right_seg->c;
  779. if (d < -EPSILON_A)
  780. return ART_FALSE;
  781. else if (d < EPSILON_A)
  782. {
  783. /* I'm unsure about the break flags here. */
  784. double right_x1 = art_svp_intersect_break (ctx, right_seg,
  785. left_x1, left_y1,
  786. ART_BREAK_RIGHT);
  787. if (left_x1 <= right_x1)
  788. return ART_FALSE;
  789. }
  790. }
  791. else if (left_y1 > right_y1)
  792. {
  793. /* Test right (x1, y1) against left segment */
  794. double right_x1 = right_seg->x[1];
  795. if (right_x1 > left_seg->x[left_seg->flags & ART_ACTIVE_FLAGS_BNEG] ||
  796. right_y1 == left_seg->y0)
  797. return ART_FALSE;
  798. d = right_x1 * left_seg->a + right_y1 * left_seg->b + left_seg->c;
  799. if (d > EPSILON_A)
  800. return ART_FALSE;
  801. else if (d > -EPSILON_A)
  802. {
  803. /* See above regarding break flags. */
  804. double left_x1 = art_svp_intersect_break (ctx, left_seg,
  805. right_x1, right_y1,
  806. ART_BREAK_LEFT);
  807. if (left_x1 <= right_x1)
  808. return ART_FALSE;
  809. }
  810. }
  811. else /* left_y1 == right_y1 */
  812. {
  813. double left_x1 = left_seg->x[1];
  814. double right_x1 = right_seg->x[1];
  815. if (left_x1 <= right_x1)
  816. return ART_FALSE;
  817. }
  818. art_svp_intersect_swap_active (ctx, left_seg, right_seg);
  819. return ART_TRUE;
  820. }
  821. if (left_y1 < right_y1)
  822. {
  823. /* Test left (x1, y1) against right segment */
  824. double left_x1 = left_seg->x[1];
  825. if (left_x1 <
  826. right_seg->x[(right_seg->flags & ART_ACTIVE_FLAGS_BNEG) ^ 1] ||
  827. left_y1 == right_seg->y0)
  828. return ART_FALSE;
  829. d = left_x1 * right_seg->a + left_y1 * right_seg->b + right_seg->c;
  830. if (d < -EPSILON_A)
  831. return ART_FALSE;
  832. else if (d < EPSILON_A)
  833. {
  834. double right_x1 = art_svp_intersect_break (ctx, right_seg,
  835. left_x1, left_y1,
  836. ART_BREAK_RIGHT);
  837. if (left_x1 <= right_x1)
  838. return ART_FALSE;
  839. }
  840. }
  841. else if (left_y1 > right_y1)
  842. {
  843. /* Test right (x1, y1) against left segment */
  844. double right_x1 = right_seg->x[1];
  845. if (right_x1 > left_seg->x[left_seg->flags & ART_ACTIVE_FLAGS_BNEG] ||
  846. right_y1 == left_seg->y0)
  847. return ART_FALSE;
  848. d = right_x1 * left_seg->a + right_y1 * left_seg->b + left_seg->c;
  849. if (d > EPSILON_A)
  850. return ART_FALSE;
  851. else if (d > -EPSILON_A)
  852. {
  853. double left_x1 = art_svp_intersect_break (ctx, left_seg,
  854. right_x1, right_y1,
  855. ART_BREAK_LEFT);
  856. if (left_x1 <= right_x1)
  857. return ART_FALSE;
  858. }
  859. }
  860. else /* left_y1 == right_y1 */
  861. {
  862. double left_x1 = left_seg->x[1];
  863. double right_x1 = right_seg->x[1];
  864. if (left_x1 <= right_x1)
  865. return ART_FALSE;
  866. }
  867. /* The segments cross. Find the intersection point. */
  868. in_seg = left_seg->in_seg;
  869. in_curs = left_seg->in_curs;
  870. left_x0 = in_seg->points[in_curs - 1].x;
  871. left_y0 = in_seg->points[in_curs - 1].y;
  872. left_x1 = in_seg->points[in_curs].x;
  873. left_y1 = in_seg->points[in_curs].y;
  874. d0 = left_x0 * right_seg->a + left_y0 * right_seg->b + right_seg->c;
  875. d1 = left_x1 * right_seg->a + left_y1 * right_seg->b + right_seg->c;
  876. if (d0 == d1)
  877. {
  878. x = left_x0;
  879. y = left_y0;
  880. }
  881. else
  882. {
  883. /* Is this division always safe? It could possibly overflow. */
  884. t = d0 / (d0 - d1);
  885. if (t <= 0)
  886. {
  887. x = left_x0;
  888. y = left_y0;
  889. }
  890. else if (t >= 1)
  891. {
  892. x = left_x1;
  893. y = left_y1;
  894. }
  895. else
  896. {
  897. x = left_x0 + t * (left_x1 - left_x0);
  898. y = left_y0 + t * (left_y1 - left_y0);
  899. }
  900. }
  901. /* Make sure intersection point is within bounds of right seg. */
  902. if (y < right_seg->y0)
  903. {
  904. x = right_seg->x[0];
  905. y = right_seg->y0;
  906. }
  907. else if (y > right_seg->y1)
  908. {
  909. x = right_seg->x[1];
  910. y = right_seg->y1;
  911. }
  912. else if (x < right_seg->x[(right_seg->flags & ART_ACTIVE_FLAGS_BNEG) ^ 1])
  913. x = right_seg->x[(right_seg->flags & ART_ACTIVE_FLAGS_BNEG) ^ 1];
  914. else if (x > right_seg->x[right_seg->flags & ART_ACTIVE_FLAGS_BNEG])
  915. x = right_seg->x[right_seg->flags & ART_ACTIVE_FLAGS_BNEG];
  916. if (y == left_seg->y0)
  917. {
  918. if (y != right_seg->y0)
  919. {
  920. #ifdef VERBOSE
  921. art_dprint ("art_svp_intersect_test_cross: intersection (%g, %g) matches former y0 of %lx, %lx\n",
  922. x, y, (unsigned long)left_seg, (unsigned long)right_seg);
  923. #endif
  924. art_svp_intersect_push_pt (ctx, right_seg, x, y);
  925. if ((break_flags & ART_BREAK_RIGHT) && right_seg->right != NULL)
  926. art_svp_intersect_add_point (ctx, x, y, right_seg->right,
  927. break_flags);
  928. }
  929. else
  930. {
  931. /* Intersection takes place at current scan line; process
  932. immediately rather than queueing intersection point into
  933. priq. */
  934. ArtActiveSeg *winner, *loser;
  935. /* Choose "most vertical" segement */
  936. if (left_seg->a > right_seg->a)
  937. {
  938. winner = left_seg;
  939. loser = right_seg;
  940. }
  941. else
  942. {
  943. winner = right_seg;
  944. loser = left_seg;
  945. }
  946. loser->x[0] = winner->x[0];
  947. loser->horiz_x = loser->x[0];
  948. loser->horiz_delta_wind += loser->delta_wind;
  949. winner->horiz_delta_wind -= loser->delta_wind;
  950. art_svp_intersect_swap_active (ctx, left_seg, right_seg);
  951. return ART_TRUE;
  952. }
  953. }
  954. else if (y == right_seg->y0)
  955. {
  956. #ifdef VERBOSE
  957. art_dprint ("*** art_svp_intersect_test_cross: intersection (%g, %g) matches latter y0 of %lx, %lx\n",
  958. x, y, (unsigned long)left_seg, (unsigned long)right_seg);
  959. #endif
  960. art_svp_intersect_push_pt (ctx, left_seg, x, y);
  961. if ((break_flags & ART_BREAK_LEFT) && left_seg->left != NULL)
  962. art_svp_intersect_add_point (ctx, x, y, left_seg->left,
  963. break_flags);
  964. }
  965. else
  966. {
  967. #ifdef VERBOSE
  968. art_dprint ("Inserting (%g, %g) into %lx, %lx\n",
  969. x, y, (unsigned long)left_seg, (unsigned long)right_seg);
  970. #endif
  971. /* Insert the intersection point into both segments. */
  972. art_svp_intersect_push_pt (ctx, left_seg, x, y);
  973. art_svp_intersect_push_pt (ctx, right_seg, x, y);
  974. if ((break_flags & ART_BREAK_LEFT) && left_seg->left != NULL)
  975. art_svp_intersect_add_point (ctx, x, y, left_seg->left, break_flags);
  976. if ((break_flags & ART_BREAK_RIGHT) && right_seg->right != NULL)
  977. art_svp_intersect_add_point (ctx, x, y, right_seg->right, break_flags);
  978. }
  979. return ART_FALSE;
  980. }
  981. /**
  982. * art_svp_intersect_active_delete: Delete segment from active list.
  983. * @ctx: Intersection context.
  984. * @seg: Segment to delete.
  985. *
  986. * Deletes @seg from the active list.
  987. **/
  988. static /* todo inline */ void
  989. art_svp_intersect_active_delete (ArtIntersectCtx *ctx, ArtActiveSeg *seg)
  990. {
  991. ArtActiveSeg *left = seg->left, *right = seg->right;
  992. if (left != NULL)
  993. left->right = right;
  994. else
  995. ctx->active_head = right;
  996. if (right != NULL)
  997. right->left = left;
  998. }
  999. /**
  1000. * art_svp_intersect_active_free: Free an active segment.
  1001. * @seg: Segment to delete.
  1002. *
  1003. * Frees @seg.
  1004. **/
  1005. static /* todo inline */ void
  1006. art_svp_intersect_active_free (ArtActiveSeg *seg)
  1007. {
  1008. art_free (seg->stack);
  1009. #ifdef VERBOSE
  1010. art_dprint ("Freeing %lx\n", (unsigned long) seg);
  1011. #endif
  1012. art_free (seg);
  1013. }
  1014. /**
  1015. * art_svp_intersect_insert_cross: Test crossings of newly inserted line.
  1016. *
  1017. * Tests @seg against its left and right neighbors for intersections.
  1018. * Precondition: the line in @seg is not purely horizontal.
  1019. **/
  1020. static void
  1021. art_svp_intersect_insert_cross (ArtIntersectCtx *ctx,
  1022. ArtActiveSeg *seg)
  1023. {
  1024. ArtActiveSeg *left = seg, *right = seg;
  1025. for (;;)
  1026. {
  1027. if (left != NULL)
  1028. {
  1029. ArtActiveSeg *leftc;
  1030. for (leftc = left->left; leftc != NULL; leftc = leftc->left)
  1031. if (!(leftc->flags & ART_ACTIVE_FLAGS_DEL))
  1032. break;
  1033. if (leftc != NULL &&
  1034. art_svp_intersect_test_cross (ctx, leftc, left,
  1035. ART_BREAK_LEFT))
  1036. {
  1037. if (left == right || right == NULL)
  1038. right = left->right;
  1039. }
  1040. else
  1041. {
  1042. left = NULL;
  1043. }
  1044. }
  1045. else if (right != NULL && right->right != NULL)
  1046. {
  1047. ArtActiveSeg *rightc;
  1048. for (rightc = right->right; rightc != NULL; rightc = rightc->right)
  1049. if (!(rightc->flags & ART_ACTIVE_FLAGS_DEL))
  1050. break;
  1051. if (rightc != NULL &&
  1052. art_svp_intersect_test_cross (ctx, right, rightc,
  1053. ART_BREAK_RIGHT))
  1054. {
  1055. if (left == right || left == NULL)
  1056. left = right->left;
  1057. }
  1058. else
  1059. {
  1060. right = NULL;
  1061. }
  1062. }
  1063. else
  1064. break;
  1065. }
  1066. }
  1067. /**
  1068. * art_svp_intersect_horiz: Add horizontal line segment.
  1069. * @ctx: Intersector context.
  1070. * @seg: Segment on which to add horizontal line.
  1071. * @x0: Old x position.
  1072. * @x1: New x position.
  1073. *
  1074. * Adds a horizontal line from @x0 to @x1, and updates the current
  1075. * location of @seg to @x1.
  1076. **/
  1077. static void
  1078. art_svp_intersect_horiz (ArtIntersectCtx *ctx, ArtActiveSeg *seg,
  1079. double x0, double x1)
  1080. {
  1081. ArtActiveSeg *hs;
  1082. if (x0 == x1)
  1083. return;
  1084. hs = art_new (ArtActiveSeg, 1);
  1085. hs->flags = ART_ACTIVE_FLAGS_DEL | (seg->flags & ART_ACTIVE_FLAGS_OUT);
  1086. if (seg->flags & ART_ACTIVE_FLAGS_OUT)
  1087. {
  1088. ArtSvpWriter *swr = ctx->out;
  1089. swr->add_point (swr, seg->seg_id, x0, ctx->y);
  1090. }
  1091. hs->seg_id = seg->seg_id;
  1092. hs->horiz_x = x0;
  1093. hs->horiz_delta_wind = seg->delta_wind;
  1094. hs->stack = NULL;
  1095. /* Ideally, the (a, b, c) values will never be read. However, there
  1096. are probably some tests remaining that don't check for _DEL
  1097. before evaluating the line equation. For those, these
  1098. initializations will at least prevent a UMR of the values, which
  1099. can crash on some platforms. */
  1100. hs->a = 0.0;
  1101. hs->b = 0.0;
  1102. hs->c = 0.0;
  1103. seg->horiz_delta_wind -= seg->delta_wind;
  1104. art_svp_intersect_add_horiz (ctx, hs);
  1105. if (x0 > x1)
  1106. {
  1107. ArtActiveSeg *left;
  1108. art_boolean first = ART_TRUE;
  1109. for (left = seg->left; left != NULL; left = seg->left)
  1110. {
  1111. int left_bneg = left->flags & ART_ACTIVE_FLAGS_BNEG;
  1112. if (left->x[left_bneg] <= x1)
  1113. break;
  1114. if (left->x[left_bneg ^ 1] <= x1 &&
  1115. x1 * left->a + ctx->y * left->b + left->c >= 0)
  1116. break;
  1117. if (left->y0 != ctx->y && left->y1 != ctx->y)
  1118. {
  1119. art_svp_intersect_break (ctx, left, x1, ctx->y, ART_BREAK_LEFT);
  1120. }
  1121. #ifdef VERBOSE
  1122. art_dprint ("x0=%g > x1=%g, swapping %lx, %lx\n",
  1123. x0, x1, (unsigned long)left, (unsigned long)seg);
  1124. #endif
  1125. art_svp_intersect_swap_active (ctx, left, seg);
  1126. if (first && left->right != NULL)
  1127. {
  1128. art_svp_intersect_test_cross (ctx, left, left->right,
  1129. ART_BREAK_RIGHT);
  1130. first = ART_FALSE;
  1131. }
  1132. }
  1133. }
  1134. else
  1135. {
  1136. ArtActiveSeg *right;
  1137. art_boolean first = ART_TRUE;
  1138. for (right = seg->right; right != NULL; right = seg->right)
  1139. {
  1140. int right_bneg = right->flags & ART_ACTIVE_FLAGS_BNEG;
  1141. if (right->x[right_bneg ^ 1] >= x1)
  1142. break;
  1143. if (right->x[right_bneg] >= x1 &&
  1144. x1 * right->a + ctx->y * right->b + right->c <= 0)
  1145. break;
  1146. if (right->y0 != ctx->y && right->y1 != ctx->y)
  1147. {
  1148. art_svp_intersect_break (ctx, right, x1, ctx->y,
  1149. ART_BREAK_LEFT);
  1150. }
  1151. #ifdef VERBOSE
  1152. art_dprint ("[right]x0=%g < x1=%g, swapping %lx, %lx\n",
  1153. x0, x1, (unsigned long)seg, (unsigned long)right);
  1154. #endif
  1155. art_svp_intersect_swap_active (ctx, seg, right);
  1156. if (first && right->left != NULL)
  1157. {
  1158. art_svp_intersect_test_cross (ctx, right->left, right,
  1159. ART_BREAK_RIGHT);
  1160. first = ART_FALSE;
  1161. }
  1162. }
  1163. }
  1164. seg->x[0] = x1;
  1165. seg->x[1] = x1;
  1166. seg->horiz_x = x1;
  1167. seg->flags &= ~ART_ACTIVE_FLAGS_OUT;
  1168. }
  1169. /**
  1170. * art_svp_intersect_insert_line: Insert a line into the active list.
  1171. * @ctx: Intersector context.
  1172. * @seg: Segment containing line to insert.
  1173. *
  1174. * Inserts the line into the intersector context, taking care of any
  1175. * intersections, and adding the appropriate horizontal points to the
  1176. * active list.
  1177. **/
  1178. static void
  1179. art_svp_intersect_insert_line (ArtIntersectCtx *ctx, ArtActiveSeg *seg)
  1180. {
  1181. if (seg->y1 == seg->y0)
  1182. {
  1183. #ifdef VERBOSE
  1184. art_dprint ("art_svp_intersect_insert_line: %lx is horizontal\n",
  1185. (unsigned long)seg);
  1186. #endif
  1187. art_svp_intersect_horiz (ctx, seg, seg->x[0], seg->x[1]);
  1188. }
  1189. else
  1190. {
  1191. art_svp_intersect_insert_cross (ctx, seg);
  1192. art_svp_intersect_add_horiz (ctx, seg);
  1193. }
  1194. }
  1195. static void
  1196. art_svp_intersect_process_intersection (ArtIntersectCtx *ctx,
  1197. ArtActiveSeg *seg)
  1198. {
  1199. int n_stack = --seg->n_stack;
  1200. seg->x[1] = seg->stack[n_stack - 1].x;
  1201. seg->y1 = seg->stack[n_stack - 1].y;
  1202. seg->x[0] = seg->stack[n_stack].x;
  1203. seg->y0 = seg->stack[n_stack].y;
  1204. seg->horiz_x = seg->x[0];
  1205. art_svp_intersect_insert_line (ctx, seg);
  1206. }
  1207. static void
  1208. art_svp_intersect_advance_cursor (ArtIntersectCtx *ctx, ArtActiveSeg *seg,
  1209. ArtPriPoint *pri_pt)
  1210. {
  1211. const ArtSVPSeg *in_seg = seg->in_seg;
  1212. int in_curs = seg->in_curs;
  1213. ArtSvpWriter *swr = seg->flags & ART_ACTIVE_FLAGS_OUT ? ctx->out : NULL;
  1214. if (swr != NULL)
  1215. swr->add_point (swr, seg->seg_id, seg->x[1], seg->y1);
  1216. if (in_curs + 1 == in_seg->n_points)
  1217. {
  1218. ArtActiveSeg *left = seg->left, *right = seg->right;
  1219. #if 0
  1220. if (swr != NULL)
  1221. swr->close_segment (swr, seg->seg_id);
  1222. seg->flags &= ~ART_ACTIVE_FLAGS_OUT;
  1223. #endif
  1224. seg->flags |= ART_ACTIVE_FLAGS_DEL;
  1225. art_svp_intersect_add_horiz (ctx, seg);
  1226. art_svp_intersect_active_delete (ctx, seg);
  1227. if (left != NULL && right != NULL)
  1228. art_svp_intersect_test_cross (ctx, left, right,
  1229. ART_BREAK_LEFT | ART_BREAK_RIGHT);
  1230. art_free (pri_pt);
  1231. }
  1232. else
  1233. {
  1234. seg->horiz_x = seg->x[1];
  1235. art_svp_intersect_setup_seg (seg, pri_pt);
  1236. art_pri_insert (ctx->pq, pri_pt);
  1237. art_svp_intersect_insert_line (ctx, seg);
  1238. }
  1239. }
  1240. static void
  1241. art_svp_intersect_add_seg (ArtIntersectCtx *ctx, const ArtSVPSeg *in_seg)
  1242. {
  1243. ArtActiveSeg *seg = art_new (ArtActiveSeg, 1);
  1244. ArtActiveSeg *test;
  1245. double x0, y0;
  1246. ArtActiveSeg *beg_range;
  1247. ArtActiveSeg *last = NULL;
  1248. ArtActiveSeg *left, *right;
  1249. ArtPriPoint *pri_pt = art_new (ArtPriPoint, 1);
  1250. seg->flags = 0;
  1251. seg->in_seg = in_seg;
  1252. seg->in_curs = 0;
  1253. seg->n_stack_max = 4;
  1254. seg->stack = art_new (ArtPoint, seg->n_stack_max);
  1255. seg->horiz_delta_wind = 0;
  1256. seg->wind_left = 0;
  1257. pri_pt->user_data = seg;
  1258. art_svp_intersect_setup_seg (seg, pri_pt);
  1259. art_pri_insert (ctx->pq, pri_pt);
  1260. /* Find insertion place for new segment */
  1261. /* This is currently a left-to-right scan, but should be replaced
  1262. with a binary search as soon as it's validated. */
  1263. x0 = in_seg->points[0].x;
  1264. y0 = in_seg->points[0].y;
  1265. beg_range = NULL;
  1266. for (test = ctx->active_head; test != NULL; test = test->right)
  1267. {
  1268. double d;
  1269. int test_bneg = test->flags & ART_ACTIVE_FLAGS_BNEG;
  1270. if (x0 < test->x[test_bneg])
  1271. {
  1272. if (x0 < test->x[test_bneg ^ 1])
  1273. break;
  1274. d = x0 * test->a + y0 * test->b + test->c;
  1275. if (d < 0)
  1276. break;
  1277. }
  1278. last = test;
  1279. }
  1280. left = art_svp_intersect_add_point (ctx, x0, y0, last, ART_BREAK_LEFT | ART_BREAK_RIGHT);
  1281. seg->left = left;
  1282. if (left == NULL)
  1283. {
  1284. right = ctx->active_head;
  1285. ctx->active_head = seg;
  1286. }
  1287. else
  1288. {
  1289. right = left->right;
  1290. left->right = seg;
  1291. }
  1292. seg->right = right;
  1293. if (right != NULL)
  1294. right->left = seg;
  1295. seg->delta_wind = in_seg->dir ? 1 : -1;
  1296. seg->horiz_x = x0;
  1297. art_svp_intersect_insert_line (ctx, seg);
  1298. }
  1299. #ifdef SANITYCHECK
  1300. static void
  1301. art_svp_intersect_sanitycheck_winding (ArtIntersectCtx *ctx)
  1302. {
  1303. #if 0
  1304. /* At this point, we seem to be getting false positives, so it's
  1305. turned off for now. */
  1306. ArtActiveSeg *seg;
  1307. int winding_number = 0;
  1308. for (seg = ctx->active_head; seg != NULL; seg = seg->right)
  1309. {
  1310. /* Check winding number consistency. */
  1311. if (seg->flags & ART_ACTIVE_FLAGS_OUT)
  1312. {
  1313. if (winding_number != seg->wind_left)
  1314. art_warn ("*** art_svp_intersect_sanitycheck_winding: seg %lx has wind_left of %d, expected %d\n",
  1315. (unsigned long) seg, seg->wind_left, winding_number);
  1316. winding_number = seg->wind_left + seg->delta_wind;
  1317. }
  1318. }
  1319. if (winding_number != 0)
  1320. art_warn ("*** art_svp_intersect_sanitycheck_winding: non-balanced winding number %d\n",
  1321. winding_number);
  1322. #endif
  1323. }
  1324. #endif
  1325. /**
  1326. * art_svp_intersect_horiz_commit: Commit points in horiz list to output.
  1327. * @ctx: Intersection context.
  1328. *
  1329. * The main function of the horizontal commit is to output new
  1330. * points to the output writer.
  1331. *
  1332. * This "commit" pass is also where winding numbers are assigned,
  1333. * because doing it here provides much greater tolerance for inputs
  1334. * which are not in strict SVP order.
  1335. *
  1336. * Each cluster in the horiz_list contains both segments that are in
  1337. * the active list (ART_ACTIVE_FLAGS_DEL is false) and that are not,
  1338. * and are scheduled to be deleted (ART_ACTIVE_FLAGS_DEL is true). We
  1339. * need to deal with both.
  1340. **/
  1341. static void
  1342. art_svp_intersect_horiz_commit (ArtIntersectCtx *ctx)
  1343. {
  1344. ArtActiveSeg *seg;
  1345. int winding_number = 0; /* initialization just to avoid warning */
  1346. int horiz_wind = 0;
  1347. double last_x = 0; /* initialization just to avoid warning */
  1348. #ifdef VERBOSE
  1349. art_dprint ("art_svp_intersect_horiz_commit: y=%g\n", ctx->y);
  1350. for (seg = ctx->horiz_first; seg != NULL; seg = seg->horiz_right)
  1351. art_dprint (" %lx: %g %+d\n",
  1352. (unsigned long)seg, seg->horiz_x, seg->horiz_delta_wind);
  1353. #endif
  1354. /* Output points to svp writer. */
  1355. for (seg = ctx->horiz_first; seg != NULL;)
  1356. {
  1357. /* Find a cluster with common horiz_x, */
  1358. ArtActiveSeg *curs;
  1359. double x = seg->horiz_x;
  1360. /* Generate any horizontal segments. */
  1361. if (horiz_wind != 0)
  1362. {
  1363. ArtSvpWriter *swr = ctx->out;
  1364. int seg_id;
  1365. seg_id = swr->add_segment (swr, winding_number, horiz_wind,
  1366. last_x, ctx->y);
  1367. swr->add_point (swr, seg_id, x, ctx->y);
  1368. swr->close_segment (swr, seg_id);
  1369. }
  1370. /* Find first active segment in cluster. */
  1371. for (curs = seg; curs != NULL && curs->horiz_x == x;
  1372. curs = curs->horiz_right)
  1373. if (!(curs->flags & ART_ACTIVE_FLAGS_DEL))
  1374. break;
  1375. if (curs != NULL && curs->horiz_x == x)
  1376. {
  1377. /* There exists at least one active segment in this cluster. */
  1378. /* Find beginning of cluster. */
  1379. for (; curs->left != NULL; curs = curs->left)
  1380. if (curs->left->horiz_x != x)
  1381. break;
  1382. if (curs->left != NULL)
  1383. winding_number = curs->left->wind_left + curs->left->delta_wind;
  1384. else
  1385. winding_number = 0;
  1386. do
  1387. {
  1388. #ifdef VERBOSE
  1389. art_dprint (" curs %lx: winding_number = %d += %d\n",
  1390. (unsigned long)curs, winding_number, curs->delta_wind);
  1391. #endif
  1392. if (!(curs->flags & ART_ACTIVE_FLAGS_OUT) ||
  1393. curs->wind_left != winding_number)
  1394. {
  1395. ArtSvpWriter *swr = ctx->out;
  1396. if (curs->flags & ART_ACTIVE_FLAGS_OUT)
  1397. {
  1398. swr->add_point (swr, curs->seg_id,
  1399. curs->horiz_x, ctx->y);
  1400. swr->close_segment (swr, curs->seg_id);
  1401. }
  1402. curs->seg_id = swr->add_segment (swr, winding_number,
  1403. curs->delta_wind,
  1404. x, ctx->y);
  1405. curs->flags |= ART_ACTIVE_FLAGS_OUT;
  1406. }
  1407. curs->wind_left = winding_number;
  1408. winding_number += curs->delta_wind;
  1409. curs = curs->right;
  1410. }
  1411. while (curs != NULL && curs->horiz_x == x);
  1412. }
  1413. /* Skip past cluster. */
  1414. do
  1415. {
  1416. ArtActiveSeg *next = seg->horiz_right;
  1417. seg->flags &= ~ART_ACTIVE_FLAGS_IN_HORIZ;
  1418. horiz_wind += seg->horiz_delta_wind;
  1419. seg->horiz_delta_wind = 0;
  1420. if (seg->flags & ART_ACTIVE_FLAGS_DEL)
  1421. {
  1422. if (seg->flags & ART_ACTIVE_FLAGS_OUT)
  1423. {
  1424. ArtSvpWriter *swr = ctx->out;
  1425. swr->close_segment (swr, seg->seg_id);
  1426. }
  1427. art_svp_intersect_active_free (seg);
  1428. }
  1429. seg = next;
  1430. }
  1431. while (seg != NULL && seg->horiz_x == x);
  1432. last_x = x;
  1433. }
  1434. ctx->horiz_first = NULL;
  1435. ctx->horiz_last = NULL;
  1436. #ifdef SANITYCHECK
  1437. art_svp_intersect_sanitycheck_winding (ctx);
  1438. #endif
  1439. }
  1440. #ifdef VERBOSE
  1441. static void
  1442. art_svp_intersect_print_active (ArtIntersectCtx *ctx)
  1443. {
  1444. ArtActiveSeg *seg;
  1445. art_dprint ("Active list (y = %g):\n", ctx->y);
  1446. for (seg = ctx->active_head; seg != NULL; seg = seg->right)
  1447. {
  1448. art_dprint (" %lx: (%g, %g)-(%g, %g), (a, b, c) = (%g, %g, %g)\n",
  1449. (unsigned long)seg,
  1450. seg->x[0], seg->y0, seg->x[1], seg->y1,
  1451. seg->a, seg->b, seg->c);
  1452. }
  1453. }
  1454. #endif
  1455. #ifdef SANITYCHECK
  1456. static void
  1457. art_svp_intersect_sanitycheck (ArtIntersectCtx *ctx)
  1458. {
  1459. ArtActiveSeg *seg;
  1460. ArtActiveSeg *last = NULL;
  1461. double d;
  1462. for (seg = ctx->active_head; seg != NULL; seg = seg->right)
  1463. {
  1464. if (seg->left != last)
  1465. {
  1466. art_warn ("*** art_svp_intersect_sanitycheck: last=%lx, seg->left=%lx\n",
  1467. (unsigned long)last, (unsigned long)seg->left);
  1468. }
  1469. if (last != NULL)
  1470. {
  1471. /* pairwise compare with previous seg */
  1472. /* First the top. */
  1473. if (last->y0 < seg->y0)
  1474. {
  1475. }
  1476. else
  1477. {
  1478. }
  1479. /* Then the bottom. */
  1480. if (last->y1 < seg->y1)
  1481. {
  1482. if (!((last->x[1] <
  1483. seg->x[(seg->flags & ART_ACTIVE_FLAGS_BNEG) ^ 1]) ||
  1484. last->y1 == seg->y0))
  1485. {
  1486. d = last->x[1] * seg->a + last->y1 * seg->b + seg->c;
  1487. if (d >= -EPSILON_A)
  1488. art_warn ("*** bottom (%g, %g) of %lx is not clear of %lx to right (d = %g)\n",
  1489. last->x[1], last->y1, (unsigned long) last,
  1490. (unsigned long) seg, d);
  1491. }
  1492. }
  1493. else if (last->y1 > seg->y1)
  1494. {
  1495. if (!((seg->x[1] >
  1496. last->x[last->flags & ART_ACTIVE_FLAGS_BNEG]) ||
  1497. seg->y1 == last->y0))
  1498. {
  1499. d = seg->x[1] * last->a + seg->y1 * last->b + last->c;
  1500. if (d <= EPSILON_A)
  1501. art_warn ("*** bottom (%g, %g) of %lx is not clear of %lx to left (d = %g)\n",
  1502. seg->x[1], seg->y1, (unsigned long) seg,
  1503. (unsigned long) last, d);
  1504. }
  1505. }
  1506. else
  1507. {
  1508. if (last->x[1] > seg->x[1])
  1509. art_warn ("*** bottoms (%g, %g) of %lx and (%g, %g) of %lx out of order\n",
  1510. last->x[1], last->y1, (unsigned long)last,
  1511. seg->x[1], seg->y1, (unsigned long)seg);
  1512. }
  1513. }
  1514. last = seg;
  1515. }
  1516. }
  1517. #endif
  1518. void
  1519. art_svp_intersector (const ArtSVP *in, ArtSvpWriter *out)
  1520. {
  1521. ArtIntersectCtx *ctx;
  1522. ArtPriQ *pq;
  1523. ArtPriPoint *first_point;
  1524. #ifdef VERBOSE
  1525. int count = 0;
  1526. #endif
  1527. if (in->n_segs == 0)
  1528. return;
  1529. ctx = art_new (ArtIntersectCtx, 1);
  1530. ctx->in = in;
  1531. ctx->out = out;
  1532. pq = art_pri_new ();
  1533. ctx->pq = pq;
  1534. ctx->active_head = NULL;
  1535. ctx->horiz_first = NULL;
  1536. ctx->horiz_last = NULL;
  1537. ctx->in_curs = 0;
  1538. first_point = art_new (ArtPriPoint, 1);
  1539. first_point->x = in->segs[0].points[0].x;
  1540. first_point->y = in->segs[0].points[0].y;
  1541. first_point->user_data = NULL;
  1542. ctx->y = first_point->y;
  1543. art_pri_insert (pq, first_point);
  1544. while (!art_pri_empty (pq))
  1545. {
  1546. ArtPriPoint *pri_point = art_pri_choose (pq);
  1547. ArtActiveSeg *seg = (ArtActiveSeg *)pri_point->user_data;
  1548. #ifdef VERBOSE
  1549. art_dprint ("\nIntersector step %d\n", count++);
  1550. art_svp_intersect_print_active (ctx);
  1551. art_dprint ("priq choose (%g, %g) %lx\n", pri_point->x, pri_point->y,
  1552. (unsigned long)pri_point->user_data);
  1553. #endif
  1554. #ifdef SANITYCHECK
  1555. art_svp_intersect_sanitycheck(ctx);
  1556. #endif
  1557. if (ctx->y != pri_point->y)
  1558. {
  1559. art_svp_intersect_horiz_commit (ctx);
  1560. ctx->y = pri_point->y;
  1561. }
  1562. if (seg == NULL)
  1563. {
  1564. /* Insert new segment from input */
  1565. const ArtSVPSeg *in_seg = &in->segs[ctx->in_curs++];
  1566. art_svp_intersect_add_seg (ctx, in_seg);
  1567. if (ctx->in_curs < in->n_segs)
  1568. {
  1569. const ArtSVPSeg *next_seg = &in->segs[ctx->in_curs];
  1570. pri_point->x = next_seg->points[0].x;
  1571. pri_point->y = next_seg->points[0].y;
  1572. /* user_data is already NULL */
  1573. art_pri_insert (pq, pri_point);
  1574. }
  1575. else
  1576. art_free (pri_point);
  1577. }
  1578. else
  1579. {
  1580. int n_stack = seg->n_stack;
  1581. if (n_stack > 1)
  1582. {
  1583. art_svp_intersect_process_intersection (ctx, seg);
  1584. art_free (pri_point);
  1585. }
  1586. else
  1587. {
  1588. art_svp_intersect_advance_cursor (ctx, seg, pri_point);
  1589. }
  1590. }
  1591. }
  1592. art_svp_intersect_horiz_commit (ctx);
  1593. art_pri_free (pq);
  1594. art_free (ctx);
  1595. }
  1596. #endif /* not TEST_PRIQ */