test_polygon.c (8863B)
1 /* Copyright (C) 2014-2017, 2021-2023 Vincent Forest (vaplv@free.fr) 2 * 3 * This program is free software: you can redistribute it and/or modify 4 * it under the terms of the GNU General Public License as published by 5 * the Free Software Foundation, either version 3 of the License, or 6 * (at your option) any later version. 7 * 8 * This program is distributed in the hope that it will be useful, 9 * but WITHOUT ANY WARRANTY; without even the implied warranty of 10 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the 11 * GNU General Public License for more details. 12 * 13 * You should have received a copy of the GNU General Public License 14 * along with this program. If not, see <http://www.gnu.org/licenses/>. */ 15 16 #include "polygon.h" 17 #include "test_polygon_utils.h" 18 19 #include <rsys/float3.h> 20 #include <rsys/mem_allocator.h> 21 22 #include <string.h> 23 24 static float /* Return the area of the triangulated polygon */ 25 check_triangulation 26 (struct polygon* poly, 27 const uint32_t* indices, 28 const uint32_t nindices, 29 const uint32_t nedges_contour) 30 { 31 float area = 0.f; 32 uint32_t i; 33 /* List the counter edges retrieved after the polygon triangulation. This 34 * array must be indexed by the smallest index of the edge */ 35 char* contour; 36 ASSERT(poly && indices && nindices && nedges_contour); 37 38 contour = mem_calloc(nedges_contour, sizeof(char)); 39 CHK(contour != NULL); 40 41 memset(contour, 0, nedges_contour * sizeof(char)); 42 CHK(nindices % 3 == 0); 43 FOR_EACH(i, 0, nindices/3) { 44 const uint32_t* tri = indices + (i*3); 45 float e0[3], e1[3], N[3]; 46 float v0[3], v1[3], v2[3]; 47 float len; 48 CHK(polygon_vertex_get(poly, tri[0], v0) == RES_OK); 49 CHK(polygon_vertex_get(poly, tri[1], v1) == RES_OK); 50 CHK(polygon_vertex_get(poly, tri[2], v2) == RES_OK); 51 /* Compute the triangle area and add it to the overall polygon area */ 52 f3_sub(e0, v1, v0); 53 f3_sub(e1, v2, v0); 54 len = f3_normalize(N, f3_cross(N, e0, e1)); 55 CHK(eq_eps(len, 0.f, 1.e-6f) == 0); 56 area += len * 0.5f; 57 /* Update the contour edge flag */ 58 if(tri[1] == (tri[0] + 1) % nedges_contour) { 59 CHK(contour[tri[0]] == 0); 60 contour[tri[0]] = 1; 61 } 62 if(tri[2] == (tri[1] + 1) % nedges_contour) { 63 CHK(contour[tri[1]] == 0); 64 contour[tri[1]] = 1; 65 } 66 if(tri[0] == (tri[2] + 1) % nedges_contour) { 67 CHK(contour[tri[2]] == 0); 68 contour[tri[2]] = 1; 69 } 70 } 71 FOR_EACH(i, 0, nedges_contour) /* All the contour edges may be found */ 72 CHK(contour[i] == 1); 73 74 mem_rm(contour); 75 return area; 76 } 77 78 int 79 main(int argc, char** argv) 80 { 81 /* Input polygon contour : 82 * 1-------------2 5---6 83 * | | | | 84 * | 10----9 | | | 85 * | | | 3-----4 | 86 * | | | | 87 * 0---11 8-------------7 */ 88 const float vertices[] = { 89 0.f, 0.f, 0.f, 90 0.f, 1.f, 0.f, 91 1.f, 1.f, 0.f, 92 1.f, 0.25f, 0.f, 93 1.5f, 0.25f, 0.f, 94 1.5f, 1.f, 0.f, 95 1.75f, 1.f, 0.f, 96 1.75f, 0.f, 0.f, 97 0.75f, 0.f, 0.f, 98 0.75f, 0.75f, 0.f, 99 0.25f, 0.75f, 0.f, 100 0.25f, 0.f, 0.f 101 }; 102 struct mem_allocator allocator_proxy; 103 struct polygon* poly; 104 const uint32_t* indices; 105 float pos[3]; 106 uint32_t nindices; 107 uint32_t ivertex, nvertices; 108 (void)argc, (void)argv; 109 110 mem_init_proxy_allocator(&allocator_proxy, &mem_default_allocator); 111 112 CHK(polygon_create(NULL, NULL) == RES_BAD_ARG); 113 CHK(polygon_create(&allocator_proxy, NULL) == RES_BAD_ARG); 114 CHK(polygon_create(NULL, &poly) == RES_OK); 115 116 CHK(polygon_ref_get(NULL) == RES_BAD_ARG); 117 CHK(polygon_ref_get(poly) == RES_OK); 118 CHK(polygon_ref_put(NULL) == RES_BAD_ARG); 119 CHK(polygon_ref_put(poly) == RES_OK); 120 CHK(polygon_ref_put(poly) == RES_OK); 121 122 CHK(polygon_create(&allocator_proxy, &poly) == RES_OK); 123 124 CHK(polygon_vertices_count_get(NULL, NULL) == RES_BAD_ARG); 125 CHK(polygon_vertices_count_get(poly, NULL) == RES_BAD_ARG); 126 CHK(polygon_vertices_count_get(NULL, &nvertices) == RES_BAD_ARG); 127 CHK(polygon_vertices_count_get(poly, &nvertices) == RES_OK); 128 CHK(nvertices == 0); 129 130 CHK(polygon_vertex_add(NULL, NULL) == RES_BAD_ARG); 131 CHK(polygon_vertex_add(poly, NULL) == RES_BAD_ARG); 132 CHK(polygon_vertex_add(NULL, vertices + 3) == RES_BAD_ARG); 133 CHK(polygon_vertex_add(poly, vertices + 3) == RES_OK); 134 135 CHK(polygon_vertices_count_get(poly, &nvertices) == RES_OK); 136 CHK(nvertices == 1); 137 138 /* The last vertex is equal to the new one => skip it */ 139 CHK(polygon_vertex_add(poly, vertices + 3) == RES_OK); 140 CHK(polygon_vertices_count_get(poly, &nvertices) == RES_OK); 141 CHK(nvertices == 1); 142 143 CHK(polygon_vertex_add(poly, vertices + 6) == RES_OK); 144 CHK(polygon_vertices_count_get(poly, &nvertices) == RES_OK); 145 CHK(nvertices == 2); 146 147 /* The new vertex is aligned with the 2 previous one => replace the last 148 * vertex by the new one */ 149 CHK(polygon_vertex_add(poly, vertices + 15) == RES_OK); 150 CHK(polygon_vertices_count_get(poly, &nvertices) == RES_OK); 151 CHK(nvertices == 2); 152 153 CHK(polygon_vertex_get(NULL, UINT32_MAX, NULL) == RES_BAD_ARG); 154 CHK(polygon_vertex_get(poly, UINT32_MAX, NULL) == RES_BAD_ARG); 155 CHK(polygon_vertex_get(NULL, 0, NULL) == RES_BAD_ARG); 156 CHK(polygon_vertex_get(poly, 0, NULL) == RES_BAD_ARG); 157 CHK(polygon_vertex_get(NULL, UINT32_MAX, pos) == RES_BAD_ARG); 158 CHK(polygon_vertex_get(poly, UINT32_MAX, pos) == RES_BAD_ARG); 159 CHK(polygon_vertex_get(NULL, 0, pos) == RES_BAD_ARG); 160 CHK(polygon_vertex_get(poly, 0, pos) == RES_OK); 161 CHK(f3_eq_eps(pos, vertices + 3, 1.e-6f) == 1); 162 163 CHK(polygon_vertex_get(poly, 1, pos) == RES_OK); 164 CHK(f3_eq_eps(pos, vertices + 15, 1.e-6f) == 1); 165 166 CHK(polygon_vertex_get(poly, 2, pos) == RES_BAD_ARG); 167 168 CHK(polygon_clear(NULL) == RES_BAD_ARG); 169 CHK(polygon_clear(poly) == RES_OK); 170 171 CHK(polygon_vertices_count_get(poly, &nvertices) == RES_OK); 172 CHK(nvertices == 0); 173 174 FOR_EACH(ivertex, 0, sizeof(vertices)/(3*sizeof(float))) 175 CHK(polygon_vertex_add(poly, vertices + ivertex * 3) == RES_OK); 176 177 CHK(polygon_vertices_count_get(poly, &nvertices) == RES_OK); 178 CHK(nvertices == sizeof(vertices)/(3*sizeof(float))); 179 180 FOR_EACH(ivertex, 0, sizeof(vertices)/(3*sizeof(float))) { 181 CHK(polygon_vertex_get(poly, ivertex, pos) == RES_OK); 182 CHK(f3_eq_eps(pos, vertices + ivertex*3, 1.e-6f) == 1); 183 } 184 185 CHK(polygon_triangulate(NULL, NULL, NULL) == RES_BAD_ARG); 186 CHK(polygon_triangulate(poly, NULL, NULL) == RES_BAD_ARG); 187 CHK(polygon_triangulate(NULL, &indices, NULL) == RES_BAD_ARG); 188 CHK(polygon_triangulate(poly, &indices, NULL) == RES_BAD_ARG); 189 CHK(polygon_triangulate(NULL, NULL, &nindices) == RES_BAD_ARG); 190 CHK(polygon_triangulate(poly, NULL, &nindices) == RES_BAD_ARG); 191 CHK(polygon_triangulate(NULL, &indices, &nindices) == RES_BAD_ARG); 192 193 /* Check full triangulation */ 194 CHK(polygon_triangulate(poly, &indices, &nindices) == RES_OK); 195 CHK(nindices == 30); 196 CHK(eq_eps(check_triangulation(poly, indices, nindices, 12), 1.f, 1.e-6f)); 197 198 /* After the triangulation the input polygon may be unchanged */ 199 CHK(polygon_vertices_count_get(poly, &nvertices) == RES_OK); 200 CHK(nvertices == sizeof(vertices)/(3*sizeof(float))); 201 FOR_EACH(ivertex, 0, sizeof(vertices)/(3*sizeof(float))) { 202 CHK(polygon_vertex_get(poly, ivertex, pos) == RES_OK); 203 CHK(f3_eq_eps(pos, vertices + ivertex*3, 1.e-6f) == 1); 204 } 205 206 /* Check that the input polygon can be retriangulated */ 207 CHK(polygon_triangulate(poly, &indices, &nindices) == RES_OK); 208 CHK(nindices == 30); 209 CHK(eq_eps(check_triangulation(poly, indices, nindices, 12), 1.f, 1.e-6f)); 210 211 /* One can triangulate empty polygon */ 212 CHK(polygon_clear(poly) == RES_OK); 213 CHK(polygon_triangulate(poly, &indices, &nindices) == RES_OK); 214 CHK(nindices == 0); 215 216 /* Check the triangulation of an updated polygon */ 217 CHK(polygon_vertex_add(poly, vertices + 0) == RES_OK); 218 CHK(polygon_vertex_add(poly, vertices + 3) == RES_OK); 219 CHK(polygon_triangulate(poly, &indices, &nindices) == RES_OK); 220 CHK(nindices == 0); 221 CHK(polygon_vertex_add(poly, vertices + 6) == RES_OK); 222 CHK(polygon_triangulate(poly, &indices, &nindices) == RES_OK); 223 CHK(nindices == 3); 224 CHK(eq_eps(check_triangulation(poly, indices, nindices, 3), 0.5f, 1.e-6f)); 225 CHK(polygon_vertex_add(poly, vertices + 9) == RES_OK); 226 CHK(polygon_vertex_add(poly, vertices + 12) == RES_OK); 227 CHK(polygon_vertex_add(poly, vertices + 15) == RES_OK); 228 CHK(polygon_vertex_add(poly, vertices + 18) == RES_OK); 229 CHK(polygon_vertex_add(poly, vertices + 21) == RES_OK); 230 CHK(polygon_vertex_add(poly, vertices + 21) == RES_OK); 231 CHK(polygon_triangulate(poly, &indices, &nindices) == RES_OK); 232 CHK(nindices == 18); 233 CHK(eq_eps(check_triangulation(poly, indices, nindices, 8), 1.375f, 1.e-6f)); 234 235 CHK(polygon_ref_put(poly) == RES_OK); 236 237 check_memory_allocator(&allocator_proxy); 238 mem_shutdown_proxy_allocator(&allocator_proxy); 239 CHK(mem_allocated_size() == 0); 240 return 0; 241 } 242