#
source:
trunk/third/libart_lgpl/art_svp_vpath.c
@
18256

Revision 18256, 5.4 KB checked in by ghudson, 22 years ago (diff) |
---|

Line | |
---|---|

1 | /* Libart_LGPL - library of basic graphic primitives |

2 | * Copyright (C) 1998-2000 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 | |

20 | /* Sort vector paths into sorted vector paths */ |

21 | |

22 | #include "config.h" |

23 | #include "art_svp_vpath.h" |

24 | |

25 | #include <stdlib.h> |

26 | #include <math.h> |

27 | |

28 | #include "art_misc.h" |

29 | |

30 | #include "art_vpath.h" |

31 | #include "art_svp.h" |

32 | |

33 | |

34 | /* reverse a list of points in place */ |

35 | static void |

36 | reverse_points (ArtPoint *points, int n_points) |

37 | { |

38 | int i; |

39 | ArtPoint tmp_p; |

40 | |

41 | for (i = 0; i < (n_points >> 1); i++) |

42 | { |

43 | tmp_p = points[i]; |

44 | points[i] = points[n_points - (i + 1)]; |

45 | points[n_points - (i + 1)] = tmp_p; |

46 | } |

47 | } |

48 | |

49 | /** |

50 | * art_svp_from_vpath: Convert a vpath to a sorted vector path. |

51 | * @vpath: #ArtVPath to convert. |

52 | * |

53 | * Converts a vector path into sorted vector path form. The svp form is |

54 | * more efficient for rendering and other vector operations. |

55 | * |

56 | * Basically, the implementation is to traverse the vector path, |

57 | * generating a new segment for each "run" of points in the vector |

58 | * path with monotonically increasing Y values. All the resulting |

59 | * values are then sorted. |

60 | * |

61 | * Note: I'm not sure that the sorting rule is correct with respect |

62 | * to numerical stability issues. |

63 | * |

64 | * Return value: Resulting sorted vector path. |

65 | **/ |

66 | ArtSVP * |

67 | art_svp_from_vpath (ArtVpath *vpath) |

68 | { |

69 | int n_segs, n_segs_max; |

70 | ArtSVP *svp; |

71 | int dir; |

72 | int new_dir; |

73 | int i; |

74 | ArtPoint *points; |

75 | int n_points, n_points_max; |

76 | double x, y; |

77 | double x_min, x_max; |

78 | |

79 | n_segs = 0; |

80 | n_segs_max = 16; |

81 | svp = (ArtSVP *)art_alloc (sizeof(ArtSVP) + |

82 | (n_segs_max - 1) * sizeof(ArtSVPSeg)); |

83 | |

84 | dir = 0; |

85 | n_points = 0; |

86 | n_points_max = 0; |

87 | points = NULL; |

88 | i = 0; |

89 | |

90 | x = y = 0; /* unnecessary, given "first code must not be LINETO" invariant, |

91 | but it makes gcc -Wall -ansi -pedantic happier */ |

92 | x_min = x_max = 0; /* same */ |

93 | |

94 | while (vpath[i].code != ART_END) { |

95 | if (vpath[i].code == ART_MOVETO || vpath[i].code == ART_MOVETO_OPEN) |

96 | { |

97 | if (points != NULL && n_points >= 2) |

98 | { |

99 | if (n_segs == n_segs_max) |

100 | { |

101 | n_segs_max <<= 1; |

102 | svp = (ArtSVP *)art_realloc (svp, sizeof(ArtSVP) + |

103 | (n_segs_max - 1) * |

104 | sizeof(ArtSVPSeg)); |

105 | } |

106 | svp->segs[n_segs].n_points = n_points; |

107 | svp->segs[n_segs].dir = (dir > 0); |

108 | if (dir < 0) |

109 | reverse_points (points, n_points); |

110 | svp->segs[n_segs].points = points; |

111 | svp->segs[n_segs].bbox.x0 = x_min; |

112 | svp->segs[n_segs].bbox.x1 = x_max; |

113 | svp->segs[n_segs].bbox.y0 = points[0].y; |

114 | svp->segs[n_segs].bbox.y1 = points[n_points - 1].y; |

115 | n_segs++; |

116 | points = NULL; |

117 | } |

118 | |

119 | if (points == NULL) |

120 | { |

121 | n_points_max = 4; |

122 | points = art_new (ArtPoint, n_points_max); |

123 | } |

124 | |

125 | n_points = 1; |

126 | points[0].x = x = vpath[i].x; |

127 | points[0].y = y = vpath[i].y; |

128 | x_min = x; |

129 | x_max = x; |

130 | dir = 0; |

131 | } |

132 | else /* must be LINETO */ |

133 | { |

134 | new_dir = (vpath[i].y > y || |

135 | (vpath[i].y == y && vpath[i].x > x)) ? 1 : -1; |

136 | if (dir && dir != new_dir) |

137 | { |

138 | /* new segment */ |

139 | x = points[n_points - 1].x; |

140 | y = points[n_points - 1].y; |

141 | if (n_segs == n_segs_max) |

142 | { |

143 | n_segs_max <<= 1; |

144 | svp = (ArtSVP *)art_realloc (svp, sizeof(ArtSVP) + |

145 | (n_segs_max - 1) * |

146 | sizeof(ArtSVPSeg)); |

147 | } |

148 | svp->segs[n_segs].n_points = n_points; |

149 | svp->segs[n_segs].dir = (dir > 0); |

150 | if (dir < 0) |

151 | reverse_points (points, n_points); |

152 | svp->segs[n_segs].points = points; |

153 | svp->segs[n_segs].bbox.x0 = x_min; |

154 | svp->segs[n_segs].bbox.x1 = x_max; |

155 | svp->segs[n_segs].bbox.y0 = points[0].y; |

156 | svp->segs[n_segs].bbox.y1 = points[n_points - 1].y; |

157 | n_segs++; |

158 | |

159 | n_points = 1; |

160 | n_points_max = 4; |

161 | points = art_new (ArtPoint, n_points_max); |

162 | points[0].x = x; |

163 | points[0].y = y; |

164 | x_min = x; |

165 | x_max = x; |

166 | } |

167 | |

168 | if (points != NULL) |

169 | { |

170 | if (n_points == n_points_max) |

171 | art_expand (points, ArtPoint, n_points_max); |

172 | points[n_points].x = x = vpath[i].x; |

173 | points[n_points].y = y = vpath[i].y; |

174 | if (x < x_min) x_min = x; |

175 | else if (x > x_max) x_max = x; |

176 | n_points++; |

177 | } |

178 | dir = new_dir; |

179 | } |

180 | i++; |

181 | } |

182 | |

183 | if (points != NULL) |

184 | { |

185 | if (n_points >= 2) |

186 | { |

187 | if (n_segs == n_segs_max) |

188 | { |

189 | n_segs_max <<= 1; |

190 | svp = (ArtSVP *)art_realloc (svp, sizeof(ArtSVP) + |

191 | (n_segs_max - 1) * |

192 | sizeof(ArtSVPSeg)); |

193 | } |

194 | svp->segs[n_segs].n_points = n_points; |

195 | svp->segs[n_segs].dir = (dir > 0); |

196 | if (dir < 0) |

197 | reverse_points (points, n_points); |

198 | svp->segs[n_segs].points = points; |

199 | svp->segs[n_segs].bbox.x0 = x_min; |

200 | svp->segs[n_segs].bbox.x1 = x_max; |

201 | svp->segs[n_segs].bbox.y0 = points[0].y; |

202 | svp->segs[n_segs].bbox.y1 = points[n_points - 1].y; |

203 | n_segs++; |

204 | } |

205 | else |

206 | art_free (points); |

207 | } |

208 | |

209 | svp->n_segs = n_segs; |

210 | |

211 | qsort (&svp->segs, n_segs, sizeof (ArtSVPSeg), art_svp_seg_compare); |

212 | |

213 | return svp; |

214 | } |

215 |

**Note:**See TracBrowser for help on using the repository browser.