/* * mesh.c -- heightfield mesh generation for ez3d. * * The object is closed by three surfaces, all sharing one global vertex * height grid (which is what makes the result watertight by construction -- * every emitted vertex is read from the same array, so adjacent faces can * never disagree about a corner): * * top : the terrain, triangles per pixel cell, or greedy-merged * rectangles over flat regions (see below) * walls : a quad wherever a solid cell edge borders a non-solid cell or * the outside of the grid -- this covers both the outer skirt * and interior cliffs cut by the alpha mask * bottom : the solid-cell footprint extruded down to z = 0, greedy-meshed * flat (a fully solid image is exactly 2 triangles) * * Coordinate mapping: cell height (i, j) comes directly from the image heightmap. * * Image pixel at (i, j) will map to cell (i, j) and finding neighbour cell * is not guaranteed safe. * * Vertex height values are generated by averaging the cell heights. * Vertex grid represents the corners of the cells (see README.md) and thus * needs to be size (w+1) * (h+1) allowing every cell to always guarantee * that all corners at least exist in the array. * * Cells are squares between four verticies. Cell grid size is w * h. * The cell (i, j) is touching the following: * - vertex (i, j) * - vertex (i+1, j) * - vertex (i, j+1) * - vertex (i+1, j+1) * * Winding: all facets are CCW seen from outside. For the top that is CCW * seen from +Z, for the bottom CCW seen from -Z (i.e. the reverse of the * matching top facet). Every side wall must traverse its top edge in the * direction OPPOSITE to the top triangle that shares it, so that each * edge is used once in each direction around the solid. */ #include #include #include #include #include "mesh.h" #include "trimesh.h" /* Facet destination: stream straight to the STL writer, or accumulate an * indexed mesh that a later decimation pass can chew on. */ typedef struct { stl_writer_t *direct; trimesh_t *buf; } mesh_sink_t; enum status_e { STATUS_UNKNOWN = 0, // DEFAULT: Has not been visited yet STATUS_CUTOUT = 1, // Cell unusable, it gets cut away /* * Non-empty cells are defined as being able to produce at * least one triangle, but the status does not in itself * record exactly which triangles are valid. It goes back * and re-checks all the triangles during the emit phase. */ STATUS_REGULAR = 2, // Not solid, only regular triangles STATUS_SPECIAL = 3, // Not solid, only specials STATUS_MIXED = 4, // Mixed regular and specials /* * Solid cells have all four corners solid and draw as blocks. * Flatness check upgrades some STATUS_SOLID to STATUS_FLAT. * Grouping upgrades some STATUS_FLAT to STATUS_GROUP. */ STATUS_SOLID = 15, /* All corners are good. */ STATUS_FLAT = 16, /* Flat with all corners. */ STATUS_GROUP = 17, /* Flat and also grouped. */ }; typedef struct { int i0, i1, j0, j1; // Corners of the group: (i0, j0) and (i1, j1) } mesh_group_t; typedef struct { int w, h; // image size in pixels float *v0_hght; // (w+1) * (h+1) corner vertex heights, z < 0 is cut float *v1_hght; // (w+1) * (h+1) left & right mid vertex heights float *v2_hght; // (w+1) * (h+1) top & bottom mid vertex heights float *c_hght; // [w * h], cell center height, z < 0 cuts whole cell mesh_group_t *grp; // size [alloc_grp] array of groups int alloc_grp; // space to allocate for groups int used_grp; // actually used groups int cells_grp; // count of cells pushed into groups int min_group_xy; // Place to start group search. int max_group_xy; // Setting to speed up group search. double tol; // Tolerance copied from original command line config uint8_t *c_stat; // [w * h] see enum status_e, classification of cells mesh_sink_t sink; // Where to send the triangles int fold; // Copied from command line config } mesh_ctx_t; /* * Does this cell still carry a region piece * (solid cell, or chamfered triangle)? * * Returns a condensed version of the status: * - STATUS_CUTOUT: don't want this cell at all. * - STATUS_SOLID: do want this cell, and ungrouped. * - STATUS_GROUP: do want this cell, and grouped. * * It ignores the nuance of exactly how the cell is shaped. */ static enum status_e cell_present(const mesh_ctx_t *ctx, int i, int j) { const int w = ctx->w; /* * We allow i or j off the edge of the world. * to simplify side wall generation, without array overflow. */ if (i >= w || j >= ctx->h) return STATUS_CUTOUT; if (i < 0 || j < 0) return STATUS_CUTOUT; const enum status_e status = ctx->c_stat[j * w + i]; assert(status > STATUS_UNKNOWN); // All cells should be visited. if (status == STATUS_CUTOUT) return STATUS_CUTOUT; if (status == STATUS_GROUP) return STATUS_GROUP; return STATUS_SOLID; } /* * Similar to `cell_present()` but solid, flat, or group returns solid. * It considers any partial or mixed cell as a cutout. */ static enum status_e cell_solid(const mesh_ctx_t *ctx, int i, int j) { const int w = ctx->w; if (i >= w || j >= ctx->h) return STATUS_CUTOUT; if (i < 0 || j < 0) return STATUS_CUTOUT; const enum status_e status = ctx->c_stat[j * w + i]; assert(status > STATUS_UNKNOWN); // All cells should be visited. if (status == STATUS_SOLID || status == STATUS_FLAT || status == STATUS_GROUP) return STATUS_SOLID; return STATUS_CUTOUT; } /* * Return 1 if this is a good triangle, based on z values. * Return 0 if we don't want it. */ static int check_tri(float tol, float za, float zb, float zc) { if (za < 0 || zb < 0 || zc < 0) return 0; if (za < tol && zb < tol && zc < tol) return 0; return 1; } static void sink_tri(const mesh_ctx_t *m, vertex_t *a, vertex_t *b, vertex_t *c) { assert(m); assert(a); assert(b); assert(c); if (m->sink.direct) { stl_tri(m->sink.direct, a, b, c); } else { assert(m->sink.buf); trimesh_t *buf = m->sink.buf; triangle_t t; t.v[0] = tm_vertex(buf, a); t.v[1] = tm_vertex(buf, b); t.v[2] = tm_vertex(buf, c); tm_tri(buf, &t); } } /* * World position of grid vertex (i, j). * * The image convention follows English language text layout, starting at * top-left corner then scanning left to right, then dropping down to next * line and scanning left to right. * * However, CAD systems, mathematical graphs, and 3D printer slicers follow * the Cartesian convention with origin in the bottom-left corner. Thus, the * vertical scale is reversed, and if we do not follow this conversion here * then a clockwise turning arrow in the image will end up counterclockwise * in the 3D printer slicer (i.e. output gets mirrored top for bottom). */ static void vert_pos(const mesh_ctx_t *ctx, int i, int j, vertex_t *out) { const int w = ctx->w, h = ctx->h; const int w1 = w + 1; assert(w > 0); assert(h > 0); // Must have real size. assert(i >= 0); assert(i <= w); assert(j >= 0); assert(j <= h); out->x = (float)i; // span is [0, w] out->y = (float)(h - j); // span is [0, h] out->z = ctx->v0_hght[j * w1 + i]; } /* * Equivalent for cells as explained above on vert_pos() * Output is the midpoint of the cell therefore offset by 0.5 * See also diagram in README.md */ static void cell_pos(const mesh_ctx_t *ctx, int i, int j, vertex_t *out) { const int w = ctx->w, h = ctx->h; assert(w > 0); assert(h > 0); // Must have real size. assert(i >= 0); assert(i < w); assert(j >= 0); assert(j < h); out->x = 0.5 + (float)i; // span is [0.5, w - 0.5] out->y = (float)(h - j) - 0.5; // span is [0.5, h - 0.5] out->z = ctx->c_hght[j * w + i]; } /* * Edge position of type 1. * * These are horizontal edges at the top and bottom of cells. */ static void edge_pos1(const mesh_ctx_t *ctx, int i, int j, vertex_t *out) { const int w = ctx->w, h = ctx->h; const int w1 = w + 1; assert(w > 0); assert(h > 0); // Must have real size. assert(i >= 0); assert(i < w); assert(j >= 0); assert(j <= h); out->x = 0.5 + (float)i; // span is [0.5, w - 0.5] out->y = (float)(h - j); // span is [0, h] out->z = ctx->v1_hght[j * w1 + i]; } /* * Edge position of type 2. * * These are vertical edges to the left and right of each cell. */ static void edge_pos2(const mesh_ctx_t *ctx, int i, int j, vertex_t *out) { const int w = ctx->w, h = ctx->h; const int w1 = w + 1; assert(w > 0); assert(h > 0); // Must have real size. assert(i >= 0); assert(i <= w); assert(j >= 0); assert(j < h); out->x = (float)i; // span is [0, w] out->y = (float)(h - j) - 0.5; // span is [0.5, h - 0.5] out->z = ctx->v2_hght[j * w1 + i]; } /* * We can take a cell, then expand it right out into verticies * plus triangle checks. This is a reasonably mechanical process * and does not involve any deep algorithms. */ typedef struct { vertex_t c00, c01, c11, c10; // Corners of the cell. vertex_t e_up, e_dwn; // Horizontal edges of the cell. vertex_t e_lft, e_rht; // Vertical edges of the cell. vertex_t mid; // Middle of the cell. uint32_t tri_flags; // 16 possible triangles. } expanded_cell_t; enum tri_flag_e { TRI_REGULAR_1 = 0x00001, TRI_REGULAR_2 = 0x00002, TRI_REGULAR_3 = 0x00004, TRI_REGULAR_4 = 0x00008, TRI_REGULAR_5 = 0x00010, TRI_REGULAR_6 = 0x00020, TRI_REGULAR_7 = 0x00040, TRI_REGULAR_8 = 0x00080, TRI_OUTER_23 = 0x00100, TRI_OUTER_45 = 0x00200, TRI_OUTER_67 = 0x00400, TRI_OUTER_81 = 0x00800, TRI_INNER_23 = 0x01000, TRI_INNER_45 = 0x02000, TRI_INNER_67 = 0x04000, TRI_INNER_81 = 0x08000, }; /* * The "regular" triangles all touch the midpoint. * In any given quarter they are incompatible with the inner/outer style. */ static void cell_fold_regular(double tol, expanded_cell_t *ecell) { if (ecell->mid.z >= 0) { if (!(ecell->tri_flags & (TRI_INNER_23 | TRI_OUTER_23))) { if (check_tri(tol, ecell->mid.z, ecell->e_lft.z, ecell->c01.z)) ecell->tri_flags |= TRI_REGULAR_2; if (check_tri(tol, ecell->mid.z, ecell->c01.z, ecell->e_dwn.z)) ecell->tri_flags |= TRI_REGULAR_3; } if (!(ecell->tri_flags & (TRI_INNER_45 | TRI_OUTER_45))) { if (check_tri(tol, ecell->mid.z, ecell->e_dwn.z, ecell->c11.z)) ecell->tri_flags |= TRI_REGULAR_4; if (check_tri(tol, ecell->mid.z, ecell->c11.z, ecell->e_rht.z)) ecell->tri_flags |= TRI_REGULAR_5; } if (!(ecell->tri_flags & (TRI_INNER_67 | TRI_OUTER_67))) { if (check_tri(tol, ecell->mid.z, ecell->e_rht.z, ecell->c10.z)) ecell->tri_flags |= TRI_REGULAR_6; if (check_tri(tol, ecell->mid.z, ecell->c10.z, ecell->e_up.z)) ecell->tri_flags |= TRI_REGULAR_7; } if (!(ecell->tri_flags & (TRI_INNER_81 | TRI_OUTER_81))) { if (check_tri(tol, ecell->mid.z, ecell->e_up.z, ecell->c00.z)) ecell->tri_flags |= TRI_REGULAR_8; if (check_tri(tol, ecell->mid.z, ecell->c00.z, ecell->e_lft.z)) ecell->tri_flags |= TRI_REGULAR_1; } } } /* * The inner/outer cut corner triangles are often better than the regular. * Preference for these is available as a command line option triggering the * alternate configuration. Exact best case depends on the job at hand. */ static void cell_fold_special(double tol, expanded_cell_t *ecell) { if (!(ecell->tri_flags & (TRI_REGULAR_2 | TRI_REGULAR_3))) { if (check_tri(tol, ecell->e_lft.z, ecell->c01.z, ecell->e_dwn.z)) ecell->tri_flags |= TRI_OUTER_23; if (check_tri(tol, ecell->e_dwn.z, ecell->mid.z, ecell->e_lft.z)) ecell->tri_flags |= TRI_INNER_23; } if (!(ecell->tri_flags & (TRI_REGULAR_4 | TRI_REGULAR_5))) { if (check_tri(tol, ecell->e_dwn.z, ecell->c11.z, ecell->e_rht.z)) ecell->tri_flags |= TRI_OUTER_45; if (check_tri(tol, ecell->e_rht.z, ecell->mid.z, ecell->e_dwn.z)) ecell->tri_flags |= TRI_INNER_45; } if (!(ecell->tri_flags & (TRI_REGULAR_6 | TRI_REGULAR_7))) { if (check_tri(tol, ecell->e_rht.z, ecell->c10.z, ecell->e_up.z)) ecell->tri_flags |= TRI_OUTER_67; if (check_tri(tol, ecell->e_up.z, ecell->mid.z, ecell->e_rht.z)) ecell->tri_flags |= TRI_INNER_67; } if (!(ecell->tri_flags & (TRI_REGULAR_8 | TRI_REGULAR_1))) { if (check_tri(tol, ecell->e_up.z, ecell->c00.z, ecell->e_lft.z)) ecell->tri_flags |= TRI_OUTER_81; if (check_tri(tol, ecell->e_lft.z, ecell->mid.z, ecell->e_up.z)) ecell->tri_flags |= TRI_INNER_81; } } static void cell_expansion(const mesh_ctx_t *ctx, int i0, int j0, expanded_cell_t *ecell) { // Should not be 100% necessary but seems easiest way to confidently init. memset(ecell, 0, sizeof *ecell); /* * We allow i0 or j0 off the edge of the world. * to simplify side wall generation, without array overflow. * * Entire ecell will be blank in this situation. * In particular, tri_flags will also be empty (i.e. no triangles). */ if (i0 >= ctx->w || j0 >= ctx->h || i0 < 0 || j0 < 0) return; const int i1 = i0 + 1; const int j1 = j0 + 1; cell_pos(ctx, i0, j0, &ecell->mid); vert_pos(ctx, i0, j0, &ecell->c00); vert_pos(ctx, i0, j1, &ecell->c01); vert_pos(ctx, i1, j1, &ecell->c11); vert_pos(ctx, i1, j0, &ecell->c10); edge_pos1(ctx, i0, j0, &ecell->e_up); edge_pos1(ctx, i0, j1, &ecell->e_dwn); edge_pos2(ctx, i0, j0, &ecell->e_lft); edge_pos2(ctx, i1, j0, &ecell->e_rht); if (ctx->fold) { // Reversed style, can be better. cell_fold_special(ctx->tol, ecell); cell_fold_regular(ctx->tol, ecell); } else { // Give preference to regular layout. cell_fold_regular(ctx->tol, ecell); cell_fold_special(ctx->tol, ecell); } } /* * Verticies `a` and `b` are on the top surface, and we need to drop down * to the base level. Generate two triangles making the rectangle. */ static void emit_side_wall(const mesh_ctx_t *ctx, vertex_t *a, vertex_t *b) { vertex_t bc_a; // Bottom corner of the side wall. vertex_t bc_b; // Bottom corner of the side wall. /* Protect against internal bugs. */ assert(a != b); bc_a.x = a->x; bc_a.y = a->y; bc_a.z = 0; bc_b.x = b->x; bc_b.y = b->y; bc_b.z = 0; /* * The quad runs a -> b -> bc_b -> bc_a (CCW seen from outside), so it * splits along the b..bc_a diagonal into (a, b, bc_a) and (b, bc_b, bc_a). * The degenerate cases keep the same rotational direction around the * remaining triangle. Getting this wrong makes both halves of the quad * traverse the shared diagonal the same way, which the verifier flags * as an inconsistently wound edge. */ if (a->z > 0) { if (b->z > 0) { sink_tri(ctx, a, b, &bc_a); sink_tri(ctx, b, &bc_b, &bc_a); } else { sink_tri(ctx, a, &bc_b, &bc_a); } return; } else if (b->z > 0) { sink_tri(ctx, b, &bc_b, &bc_a); } } /* * Check that one flag or the other is set but not both. * Slightly clunky but hopefully many compilers can optimize this out. */ static int side_detect(uint32_t tri_flags, enum tri_flag_e flg1, enum tri_flag_e flg2) { if (tri_flags & flg1) { if (tri_flags & flg2) return 0; return 1; } if (tri_flags & flg2) return 1; return 0; } /* * Emit a wall whose top edge is shared by two alternative quarter * triangles of a cell. The caller has already checked via side_detect() * that exactly one of the pair is present, so testing `first` alone * decides which one. * * The wall must traverse the top edge opposite to whichever top triangle * survives, so the direction depends on which one it is: `pa` -> `pb` is * the order that is correct when `first` is the present quarter. */ static void emit_quarter_wall(const mesh_ctx_t *ctx, uint32_t tri_flags, uint32_t first, vertex_t *pa, vertex_t *pb) { if (tri_flags & first) emit_side_wall(ctx, pa, pb); else emit_side_wall(ctx, pb, pa); } /* * Bottom facets face -Z, so they are the reverse of the matching top * facet: swap the last two vertices to flip the winding. */ static void sink_face_tri(const mesh_ctx_t *m, int bottom, vertex_t *a, vertex_t *b, vertex_t *c) { if (bottom) sink_tri(m, a, c, b); else sink_tri(m, a, b, c); } /* * Split the cell into eight triangles, but not all eight reliably exist. * See `check_tri()` above for triangle acceptance criteria. * * The "regular" eight triangle model has everything structured to fan out * from the middle of the cell. This midpoint is honestly faithful to the * orginal heightmap, and the various edge and corner verticies are * calculated by local mean, therefore about the best we can do without * additional presumptions about the user intentions. * * The alternative (special) model works with the eight triangles around * the middle and is slightly better for cut corners, etc. The intention is * that each quarter will optimize by using whatever triangle fits. */ static void emit_single_cell(const mesh_ctx_t *ctx, int i0, int j0, int bottom) { expanded_cell_t ecell; cell_expansion(ctx, i0, j0, &ecell); const int i1 = i0 + 1; const int j1 = j0 + 1; if (bottom) { /* * Bottom of block will honour the triangle flags because * checks were based on original values, but force `z = 0` here. */ ecell.mid.z = 0.0f; ecell.c00.z = ecell.c01.z = ecell.c11.z = ecell.c10.z = 0.0f; ecell.e_up.z = ecell.e_dwn.z = ecell.e_lft.z = ecell.e_rht.z = 0.0f; } /* * Regular triangles. They all touch: midpoint, corner, edge. * The bottom versions run through sink_face_tri() to reverse the * winding, because they face away from the top ones. */ if (ecell.tri_flags & TRI_REGULAR_1) sink_face_tri(ctx, bottom, &ecell.mid, &ecell.c00, &ecell.e_lft); if (ecell.tri_flags & TRI_REGULAR_2) sink_face_tri(ctx, bottom, &ecell.mid, &ecell.e_lft, &ecell.c01); if (ecell.tri_flags & TRI_REGULAR_3) sink_face_tri(ctx, bottom, &ecell.mid, &ecell.c01, &ecell.e_dwn); if (ecell.tri_flags & TRI_REGULAR_4) sink_face_tri(ctx, bottom, &ecell.mid, &ecell.e_dwn, &ecell.c11); if (ecell.tri_flags & TRI_REGULAR_5) sink_face_tri(ctx, bottom, &ecell.mid, &ecell.c11, &ecell.e_rht); if (ecell.tri_flags & TRI_REGULAR_6) sink_face_tri(ctx, bottom, &ecell.mid, &ecell.e_rht, &ecell.c10); if (ecell.tri_flags & TRI_REGULAR_7) sink_face_tri(ctx, bottom, &ecell.mid, &ecell.c10, &ecell.e_up); if (ecell.tri_flags & TRI_REGULAR_8) sink_face_tri(ctx, bottom, &ecell.mid, &ecell.e_up, &ecell.c00); /* * Outer triangles. They avoid the midpoint and touch a corner. */ if (ecell.tri_flags & TRI_OUTER_23) sink_face_tri(ctx, bottom, &ecell.e_lft, &ecell.c01, &ecell.e_dwn); if (ecell.tri_flags & TRI_OUTER_45) sink_face_tri(ctx, bottom, &ecell.e_dwn, &ecell.c11, &ecell.e_rht); if (ecell.tri_flags & TRI_OUTER_67) sink_face_tri(ctx, bottom, &ecell.e_rht, &ecell.c10, &ecell.e_up); if (ecell.tri_flags & TRI_OUTER_81) sink_face_tri(ctx, bottom, &ecell.e_up, &ecell.c00, &ecell.e_lft); /* * Inner triangles. They touch: edge, midpoint, edge. */ if (ecell.tri_flags & TRI_INNER_23) sink_face_tri(ctx, bottom, &ecell.e_dwn, &ecell.mid, &ecell.e_lft); if (ecell.tri_flags & TRI_INNER_45) sink_face_tri(ctx, bottom, &ecell.e_rht, &ecell.mid, &ecell.e_dwn); if (ecell.tri_flags & TRI_INNER_67) sink_face_tri(ctx, bottom, &ecell.e_up, &ecell.mid, &ecell.e_rht); if (ecell.tri_flags & TRI_INNER_81) sink_face_tri(ctx, bottom, &ecell.e_lft, &ecell.mid, &ecell.e_up); if (bottom) return; /* * Emit sides by checking nearby cells, and the diagonal of this cell. * The additional `tri_flags` ensure we have something to join onto * that side wall. None of this is overly complex, but quite a few * permutations exist, depending on which triangles are valid. */ expanded_cell_t ec_abv, ec_blw, ec_lft, ec_rht; cell_expansion(ctx, i0, j0 - 1, &ec_abv); cell_expansion(ctx, i0 - 1, j0, &ec_lft); cell_expansion(ctx, i0, j1, &ec_blw); cell_expansion(ctx, i1, j0, &ec_rht); /* * Outer half-walls need to check against neighbour. * There are eight possible of these walls. Each must traverse its top * edge opposite to this cell's triangle on that edge, hence the * alternating argument order below. */ if (ecell.tri_flags & (TRI_REGULAR_1 | TRI_OUTER_81) && !(ec_lft.tri_flags & (TRI_REGULAR_6 | TRI_OUTER_67))) emit_side_wall(ctx, &ecell.e_lft, &ecell.c00); if (ecell.tri_flags & (TRI_REGULAR_2 | TRI_OUTER_23) && !(ec_lft.tri_flags & (TRI_REGULAR_5 | TRI_OUTER_45))) emit_side_wall(ctx, &ecell.c01, &ecell.e_lft); if (ecell.tri_flags & (TRI_REGULAR_3 | TRI_OUTER_23) && !(ec_blw.tri_flags & (TRI_REGULAR_8 | TRI_OUTER_81))) emit_side_wall(ctx, &ecell.e_dwn, &ecell.c01); if (ecell.tri_flags & (TRI_REGULAR_4 | TRI_OUTER_45) && !(ec_blw.tri_flags & (TRI_REGULAR_7 | TRI_OUTER_67))) emit_side_wall(ctx, &ecell.c11, &ecell.e_dwn); if (ecell.tri_flags & (TRI_REGULAR_5 | TRI_OUTER_45) && !(ec_rht.tri_flags & (TRI_REGULAR_2 | TRI_OUTER_23))) emit_side_wall(ctx, &ecell.e_rht, &ecell.c11); if (ecell.tri_flags & (TRI_REGULAR_6 | TRI_OUTER_67) && !(ec_rht.tri_flags & (TRI_REGULAR_1 | TRI_OUTER_81))) emit_side_wall(ctx, &ecell.c10, &ecell.e_rht); if (ecell.tri_flags & (TRI_REGULAR_7 | TRI_OUTER_67) && !(ec_abv.tri_flags & (TRI_REGULAR_4 | TRI_OUTER_45))) emit_side_wall(ctx, &ecell.e_up, &ecell.c10); if (ecell.tri_flags & (TRI_REGULAR_8 | TRI_OUTER_81) && !(ec_abv.tri_flags & (TRI_REGULAR_3 | TRI_OUTER_23))) emit_side_wall(ctx, &ecell.c00, &ecell.e_up); /* * Diagonal side-walls if the cell is cut down the middle. * There are four half-walls to consider. */ if (side_detect(ecell.tri_flags, TRI_REGULAR_2, TRI_REGULAR_3)) emit_quarter_wall(ctx, ecell.tri_flags, TRI_REGULAR_2, &ecell.mid, &ecell.c01); if (side_detect(ecell.tri_flags, TRI_REGULAR_4, TRI_REGULAR_5)) emit_quarter_wall(ctx, ecell.tri_flags, TRI_REGULAR_4, &ecell.mid, &ecell.c11); if (side_detect(ecell.tri_flags, TRI_REGULAR_6, TRI_REGULAR_7)) emit_quarter_wall(ctx, ecell.tri_flags, TRI_REGULAR_6, &ecell.mid, &ecell.c10); if (side_detect(ecell.tri_flags, TRI_REGULAR_8, TRI_REGULAR_1)) emit_quarter_wall(ctx, ecell.tri_flags, TRI_REGULAR_8, &ecell.mid, &ecell.c00); /* * Non-diagonal internal side-walls. Again four possibilities. */ if (side_detect(ecell.tri_flags, TRI_REGULAR_1 | TRI_INNER_81, TRI_REGULAR_2 | TRI_INNER_23)) emit_quarter_wall(ctx, ecell.tri_flags, TRI_REGULAR_1 | TRI_INNER_81, &ecell.mid, &ecell.e_lft); if (side_detect(ecell.tri_flags, TRI_REGULAR_3 | TRI_INNER_23, TRI_REGULAR_4 | TRI_INNER_45)) emit_quarter_wall(ctx, ecell.tri_flags, TRI_REGULAR_3 | TRI_INNER_23, &ecell.mid, &ecell.e_dwn); if (side_detect(ecell.tri_flags, TRI_REGULAR_5 | TRI_INNER_45, TRI_REGULAR_6 | TRI_INNER_67)) emit_quarter_wall(ctx, ecell.tri_flags, TRI_REGULAR_5 | TRI_INNER_45, &ecell.mid, &ecell.e_rht); if (side_detect(ecell.tri_flags, TRI_REGULAR_7 | TRI_INNER_67, TRI_REGULAR_8 | TRI_INNER_81)) emit_quarter_wall(ctx, ecell.tri_flags, TRI_REGULAR_7 | TRI_INNER_67, &ecell.mid, &ecell.e_up); /* * Also the corner cuts, for outer triangles and inner triangles. */ if (side_detect(ecell.tri_flags, TRI_INNER_81, TRI_OUTER_81)) emit_quarter_wall(ctx, ecell.tri_flags, TRI_INNER_81, &ecell.e_lft, &ecell.e_up); if (side_detect(ecell.tri_flags, TRI_INNER_23, TRI_OUTER_23)) emit_quarter_wall(ctx, ecell.tri_flags, TRI_INNER_23, &ecell.e_dwn, &ecell.e_lft); if (side_detect(ecell.tri_flags, TRI_INNER_45, TRI_OUTER_45)) emit_quarter_wall(ctx, ecell.tri_flags, TRI_INNER_45, &ecell.e_rht, &ecell.e_dwn); if (side_detect(ecell.tri_flags, TRI_INNER_67, TRI_OUTER_67)) emit_quarter_wall(ctx, ecell.tri_flags, TRI_INNER_67, &ecell.e_up, &ecell.e_rht); } void ez3d_cleanup(mesh_ctx_t *ctx) { free(ctx->v0_hght); free(ctx->v1_hght); free(ctx->v2_hght); free(ctx->c_hght); free(ctx->c_stat); free(ctx->grp); ctx->alloc_grp = 0; ctx->used_grp = 0; } /* * Trimmed mean, used for a vertex surrounded by four cells. * Genuine mean gives -INFINITY too much power, but if we have three * sensible values and only one -INFINITY then we want a sensible answer. * On the other hand if we have two -INFINITY values then might as well * just accept it's going to be -INFINITY. * * Trimmed mean also works better near corners, it will tend to slightly * round out the square corner, usually desirable. */ static float trimmed_mean(float a, float b, float c, float d) { float tmp; /* Sort them to get `a` smallest and `d` largest. */ if (a > b) { tmp = a; a = b; b = tmp; } if (c > d) { tmp = c; c = d; d = tmp; } if (a > c) { tmp = a; a = c; c = tmp; } if (b > d) { tmp = b; b = d; d = tmp; } tmp = 0.5 * (b + c); // Keep the less extreme values. return tmp; } /* * Figure out the basic Z values and status of cells. * Does not output anything, just store the results in `mesh_ctx_t`. * * return 0 if no errors. */ int ez3d_mesh_zval(const ez3d_image_t *img, const ez3d_config_t *cfg, mesh_ctx_t *ctx) { const int w = img->w, h = img->h; const int w1 = w + 1; const int h1 = h + 1; int use_alpha; long solid_cells = 0; /* * Cell center heights, sampled from real pixels; * We apply a very simple height formula, * then if alpha channel is present we inject the edge-of-world value * into any transparent cells (default -INFINITY). */ use_alpha = img->has_alpha && cfg->alpha_thresh < 256; for (int j = 0; j < h; j++) { for (int i = 0; i < w; i++) { const int c_ix = j * w + i; // Image & Cell index. double z = img->gray[c_ix]; // unsigned int => double. z *= (cfg->height / 255.0); z += cfg->base; // We are now into world height. if (use_alpha && img->alpha[j * w + i] < cfg->alpha_thresh) { z = cfg->edge; // Genuine alpha channel. } /* z < 0 operates as alpha channel. */ ctx->c_hght[c_ix] = (float)z; /* Add cell height to edges of this cell */ const int v_ix = j * w1 + i; ctx->v1_hght[v_ix] += z; ctx->v1_hght[v_ix + w1] += z; ctx->v2_hght[v_ix] += z; ctx->v2_hght[v_ix + 1] += z; } } /* * Edges get a simple mean value, obtained by dividing by 2. * Corners are a bit more complex, we want a trimmed mean. * Thus we need to go and dig up nearby cell values and feed * those through the calculator function. */ for (int j = 0; j < h1; j++) { for (int i = 0; i < w1; i++) { const int v_ix = j * w1 + i; /* Edge of world compensation on verticals */ if (i == 0) ctx->v2_hght[v_ix] += cfg->edge; if (i == w) ctx->v2_hght[v_ix] += cfg->edge; /* Edge of world compensation on horizontals */ if (j == 0) ctx->v1_hght[v_ix] += cfg->edge; if (j == h) ctx->v1_hght[v_ix] += cfg->edge; ctx->v2_hght[v_ix] /= 2; // vertical edge ctx->v1_hght[v_ix] /= 2; // horizontal edge /* Load the corners, where they exist */ double z00, z01, z11, z10; // corner z values. z00 = z01 = z11 = z10 = cfg->edge; // default to edge-of-world. const int c_ix = j * w + i; if (i > 0 && j > 0) z00 = ctx->c_hght[c_ix - 1 - w]; if (i > 0 && j < h) z01 = ctx->c_hght[c_ix - 1]; if (i < w && j > 0) z10 = ctx->c_hght[c_ix - w]; if (i < w && j < h) z11 = ctx->c_hght[c_ix]; ctx->v0_hght[v_ix] = trimmed_mean(z00, z01, z11, z10); } } // The regular flags for a solid cell. const uint32_t full_house_reg = (TRI_REGULAR_1 | TRI_REGULAR_2 | TRI_REGULAR_3 | TRI_REGULAR_4 | TRI_REGULAR_5 | TRI_REGULAR_6 | TRI_REGULAR_7 | TRI_REGULAR_8); // Using alternate folding the flags are slightly different. const uint32_t full_house_spcl = (TRI_OUTER_23 | TRI_OUTER_45 | TRI_OUTER_67 | TRI_OUTER_81 | TRI_INNER_23 | TRI_INNER_45 | TRI_INNER_67 | TRI_INNER_81); const uint32_t full_house = (ctx->fold) ? full_house_spcl : full_house_reg; /* * Resolve the basic status of the cell, based on cell center height * and which triangles are value. See `cell_expansion()` for more * details of the flags. */ for (int j = 0; j < h; j++) { for (int i = 0; i < w; i++) { enum status_e s = STATUS_CUTOUT; expanded_cell_t ecell; cell_expansion(ctx, i, j, &ecell); if ((ecell.tri_flags & full_house) == full_house) { // This is exactly the default setting based on config. s = STATUS_SOLID; } else if (ecell.tri_flags & full_house_reg) { if (ecell.tri_flags & full_house_spcl) { s = STATUS_MIXED; } else { s = STATUS_REGULAR; } } else if (ecell.tri_flags& full_house_spcl) { s = STATUS_SPECIAL; } /* * Flatness test for proper solid cells only. * This is simply a comparison of diagonals, since all corners are available. * In a flat region we expect linearity, therefore both diagonals will reach * the same midpoint. In a curved region, we get folded squares. * * Locally flat regions allow a fill algorithm to collect them into * a single patch, and thus reduce triangle count significantly. */ if (s == STATUS_SOLID) { double zdiag_a = 0.5 * ((double)ecell.c00.z + (double)ecell.c11.z); double zdiag_b = 0.5 * ((double)ecell.c01.z + (double)ecell.c10.z); if (fabs(zdiag_a - zdiag_b) < cfg->tolerance) s = STATUS_FLAT; } /* Anything uncut counts as solid for error check purposes. */ if (s != STATUS_CUTOUT) { solid_cells++; } ctx->c_stat[j * w + i] = (uint8_t)s; } } if (solid_cells == 0) { fprintf(stderr, "ez3d: nothing to print, all cells have been cut away.\n"); if (use_alpha) fprintf(stderr, "ez3d: alpha threshold %d might need adjustment.\n", cfg->alpha_thresh); if (cfg->base < 0) fprintf(stderr, "ez3d: negative base %f can cause cells to be removed.\n", cfg->base); if (cfg->height < 0) fprintf(stderr, "ez3d: negative height %f can cause cells to be removed.\n", cfg->height); return -1; } return 0; } /* * To make it compact but hopefully easier to read than plain text. */ static const char *status_sym[] = { // 0 1 2 3 4 5 6 7 "?", ".", "R", "S", "!", "!", "!", "!", // 8 9 10 11 12 13 14 15 "!", "!", "!", "!", "!", "!", "!", "\u25A0", // 16 17 "\u29C8", "G", }; /* * Output a TAB separated list, showing cell & vertex values. */ void ez3d_mesh_dump_cells(mesh_ctx_t *ctx) { const int w = ctx->w, h = ctx->h; const int w1 = w + 1; const int h1 = h + 1; printf("type\ti\tj\tx\ty\tz\tsymbol\n"); for (int j = 0; j < h1; j++) { for (int i = 0; i < w1; i++) { vertex_t v = {0}; vert_pos(ctx, i, j, &v); printf("V\t%d\t%d\t%.3f\t%.3f\t%.3f\t%s\n", i, j, v.x, v.y, v.z, (v.z < 0) ? "\u25CB" : "\u25CF"); if (i < w) { edge_pos1(ctx, i, j, &v); printf("H\t%d\t%d\t%.3f\t%.3f\t%.3f\t%s\n", i, j, v.x, v.y, v.z, (v.z < 0) ? "\u25CB" : "\u25CF"); } } // Row of cells in between vertex rows. if (j == h) continue; for (int i = 0; i < w1; i++) { const int c_ix = j * w + i; vertex_t v = {0}; const char *sym = "!"; int status = (int)ctx->c_stat[c_ix]; if ((size_t)status < (sizeof status_sym / sizeof *status_sym)) sym = status_sym[status]; edge_pos2(ctx, i, j, &v); printf("E\t%d\t%d\t%.3f\t%.3f\t%.3f\t%s\n", i, j, v.x, v.y, v.z, (v.z < 0) ? "\u25CB" : "\u25CF"); if (i < w) { expanded_cell_t ecell; cell_expansion(ctx, i, j, &ecell); printf("C\t%d\t%d\t%.3f\t%.3f\t%.3f\t%s\t%d\t%06X\n", i, j, ecell.mid.x, ecell.mid.y, ecell.mid.z, sym, status, ecell.tri_flags); } } } } /* * Output a group as a big rectangle, but it won't have any side walls * because the perimiter should all be solid cells. */ static void emit_cell_group(const mesh_ctx_t *ctx, mesh_group_t *grp) { vertex_t c00, c01, c11, c10; vertex_t top_mid, bot_mid; vert_pos(ctx, grp->i0, grp->j0, &c00); vert_pos(ctx, grp->i0, grp->j1 + 1, &c01); vert_pos(ctx, grp->i1 + 1, grp->j1 + 1, &c11); vert_pos(ctx, grp->i1 + 1, grp->j0, &c10); bot_mid.x = top_mid.x = 0.5 * (c00.x + c11.x); bot_mid.y = top_mid.y = 0.5 * (c00.y + c11.y); top_mid.z = 0.25 * (c00.z + c01.z + c11.z + c10.z); bot_mid.z = 0; /* * Loop the perimeter and generate all triangles around the rectangle, * with each one linking back to the middle. This guarantees the triangle * corners fall in line with connecting cells, and removes bulk from the * mesh without requiring too much deep analysis. The later decimation * phase can work with this, and will run faster when fewer triangles * need scanning. Winding matches the single-cell emissions: top fans * CCW from +Z, bottom fans reversed to face -Z. */ for (int i = grp->i0; i <= grp->i1; i++) { expanded_cell_t ecell; cell_expansion(ctx, i, grp->j0, &ecell); sink_tri(ctx, &top_mid, &ecell.e_up, &ecell.c00); sink_tri(ctx, &top_mid, &ecell.c10, &ecell.e_up); ecell.c00.z = ecell.e_up.z = ecell.c10.z = 0; sink_tri(ctx, &bot_mid, &ecell.c00, &ecell.e_up); sink_tri(ctx, &bot_mid, &ecell.e_up, &ecell.c10); cell_expansion(ctx, i, grp->j1, &ecell); sink_tri(ctx, &top_mid, &ecell.c01, &ecell.e_dwn); sink_tri(ctx, &top_mid, &ecell.e_dwn, &ecell.c11); ecell.c01.z = ecell.e_dwn.z = ecell.c11.z = 0; sink_tri(ctx, &bot_mid, &ecell.e_dwn, &ecell.c01); sink_tri(ctx, &bot_mid, &ecell.c11, &ecell.e_dwn); } for (int j = grp->j0; j <= grp->j1; j++) { expanded_cell_t ecell; cell_expansion(ctx, grp->i0, j, &ecell); sink_tri(ctx, &top_mid, &ecell.c00, &ecell.e_lft); sink_tri(ctx, &top_mid, &ecell.e_lft, &ecell.c01); ecell.c00.z = ecell.e_lft.z = ecell.c01.z = 0; sink_tri(ctx, &bot_mid, &ecell.e_lft, &ecell.c00); sink_tri(ctx, &bot_mid, &ecell.c01, &ecell.e_lft); cell_expansion(ctx, grp->i1, j, &ecell); sink_tri(ctx, &top_mid, &ecell.e_rht, &ecell.c10); sink_tri(ctx, &top_mid, &ecell.c11, &ecell.e_rht); ecell.c10.z = ecell.e_rht.z = ecell.c11.z = 0; sink_tri(ctx, &bot_mid, &ecell.c10, &ecell.e_rht); sink_tri(ctx, &bot_mid, &ecell.e_rht, &ecell.c11); } } /* * Check to see if a group is acceptable. Criteria: * - All cells must be STATUS_FLAT * - Height difference on diagonals must be within tolerance * - Group does not hang out over the edge of the world * * Return `cell_count > 0` for a good group and 0 for unacceptable. */ static int check_group(mesh_ctx_t *ctx, mesh_group_t *grp, double *worst, int ignore_status) { const int w = ctx->w, h = ctx->h; /* * To simplify the algorithm for calculation of sides: * - don't run groups right up to the edge of world. * - don't make groups unless all cells surrounding the group are solid. * - block groups which are too big because inefficient to calculate. */ if (grp->i0 < 1 || grp->j0 < 1) return 0; if (grp->i0 > grp->i1 || grp->j0 > grp->j1) return 0; if (grp->i1 >= (w-1) || grp->j1 >= (h-1)) return 0; if (grp->i1 - grp->i0 >= ctx->max_group_xy) return 0; if (grp->j1 - grp->j0 >= ctx->max_group_xy) return 0; vertex_t c00, c01, c11, c10; vert_pos(ctx, grp->i0, grp->j0, &c00); vert_pos(ctx, grp->i0, grp->j1 + 1, &c01); vert_pos(ctx, grp->i1 + 1, grp->j1 + 1, &c11); vert_pos(ctx, grp->i1 + 1, grp->j0, &c10); /* * OK, the block is within bounds so identify diagonals. * If the diagonals are out of tolerance then the block * must be folded and we can give up right away. */ int cell_count = 0; double delta = fabs(0.5 * (c00.z + c11.z - c01.z - c10.z)); if (worst) *worst = delta; if (delta >= ctx->tol) return 0; if (!ignore_status) { /* * Check around the edges. If we find something not solid then give up. * This guarantees that groups never have vertical sides to worry about. */ for (int j = grp->j0 - 1; j <= grp->j1 + 1; j++) { if (cell_solid(ctx, grp->i0 - 1, j) != STATUS_SOLID) return 0; if (cell_solid(ctx, grp->i0 + 1, j) != STATUS_SOLID) return 0; } for (int i = grp->i0 - 1; i <= grp->i1 + 1; i++) { if (cell_solid(ctx, i, grp->j0 - 1) != STATUS_SOLID) return 0; if (cell_solid(ctx, i, grp->j0 + 1) != STATUS_SOLID) return 0; } } /* * Next step is to construct a bilinear model of the surface, * then compare every cell center to that model and reject * the whole group should any center be out of tolerance. */ double x_factor = 1.0 / (double)(c11.x - c00.x); double y_factor = 1.0 / (double)(c11.y - c00.y); for (int j = grp->j0; j <= grp->j1; j++) { for (int i = grp->i0; i <= grp->i1; i++) { if (!ignore_status) { if (ctx->c_stat[j * w + i] != STATUS_FLAT) return 0; } vertex_t cell; cell_pos(ctx, i, j, &cell); double x_lambda = x_factor * (cell.x - c00.x); double y_lambda = y_factor * (cell.y - c00.y); double z_model = x_lambda * y_lambda * c00.z + (1 - x_lambda) * y_lambda * c10.z + x_lambda * (1 - y_lambda) * c01.z + (1 - x_lambda) * (1 - y_lambda) * c11.z; delta = fabs(cell.z - z_model); // printf("check\t%d\t%d\t%d\t%d\t%d\t%d\t%f\t%f\t%f\t%f\n", grp->i0, grp->i1, grp->j0, grp->j1, i, j, x_lambda, y_lambda, cell.z, z_model); if (worst) { if (delta > *worst) *worst = delta; } if (delta >= ctx->tol) return 0; cell_count++; } } return cell_count; // Made it through! } /* * Mark the status of all these cells. */ static int mark_group(mesh_ctx_t *ctx, mesh_group_t *grp) { const int w = ctx->w; for (int j = grp->j0; j <= grp->j1; j++) { for (int i = grp->i0; i <= grp->i1; i++) { ctx->c_stat[j * w + i] = STATUS_GROUP; ctx->cells_grp ++; } } if (!ctx->alloc_grp || !ctx->grp) return 0; assert (ctx->used_grp <= ctx->alloc_grp); if (ctx->used_grp == ctx->alloc_grp) return 0; // NOTE: We could grow the array but groups are discovered largest first // and it gets into diminishing returns, so better move on and not worry. ctx->grp[ctx->used_grp] = *grp; ctx->used_grp++; return 1; } /* * Grouping mechanism is designed to be a crude and fast initial run before * the decimation round. We have a tolerance value `ctx->tol` for each group * which means the patch must remain flat to within tolerance. * * Current system only supports rectangular groupings, therefore four integers * defines the group by simply defining the corners. The smallest group is a * pair of connected cells. These groups should be sufficient to reduce the * bulk of the mesh and speed up the decimator. */ static int ez3d_group_cells(mesh_ctx_t *ctx) { const int w = ctx->w; const int h = ctx->h; while(1) { int biggest_group = 0; for (int pass = 0; pass < 2; pass++) { for (int j = 0; j < h; j++) { for (int i = 0; i < w; i++) { int test_group = 0; int this_group = 0; if (ctx->c_stat[j * w + i] != STATUS_FLAT) continue; // Start searching here. mesh_group_t grp; grp.i0 = i; grp.j0 = j; grp.i1 = i + ctx->min_group_xy; grp.j1 = j + ctx->min_group_xy; while(1) { int can_grow = 0; /* Grow in the X direction */ grp.i1++; test_group = check_group(ctx, &grp, NULL, 0); if (test_group > 0) { can_grow = 1; this_group = test_group; } else { grp.i1--; // It's a no grow. } /* Grow in the Y direction */ grp.j1++; test_group = check_group(ctx, &grp, NULL, 0); if (test_group > 0) { can_grow = 1; this_group = test_group; } else { grp.j1--; // It's a no grow. } if (!can_grow) break; } if (pass == 0) { // This pass is only to find the biggest group. if (this_group > biggest_group) { biggest_group = this_group; } } else { // Now we go and mark out that group. if (this_group == biggest_group) if (!mark_group(ctx, &grp)) { // We are out of group space. return 0; } } } } if (biggest_group < 2) return 0; } } return 0; } /* * Testing and debug for grouping, dump out the groups and exit. */ void ez3d_dump_groups(mesh_ctx_t *ctx) { for (int g = 0; g < ctx->used_grp; g++) { mesh_group_t *grp = &ctx->grp[g]; double tolerance = 0; int group_size = check_group(ctx, grp, &tolerance, 1); printf("G#%d\t%d\t%d\t%d\t%d\t%d\t%f\n", g, grp->i0, grp->i1, grp->j0, grp->j1, group_size, tolerance); } } /* * Loop through the group list and create triangles. */ static void emit_all_groups(mesh_ctx_t *ctx) { for (int g = 0; g < ctx->used_grp; g++) { emit_cell_group(ctx, &ctx->grp[g]); } } /* * Emit all the cells which are not part of any grouping. * Can't really fail but return 0 for success anyhow. */ int ez3d_emit_single_cells(mesh_ctx_t *ctx) { const int w = ctx->w; const int h = ctx->h; for (int j = 0; j < h; j++) { for (int i = 0; i < w; i++) { if (cell_present(ctx, i, j) == STATUS_SOLID) { emit_single_cell(ctx, i, j, 0); // top & sides emit_single_cell(ctx, i, j, 1); // bottom } } } return 0; } /* * This is the core of the meshing process. */ long ez3d_build_mesh(const ez3d_image_t *img, const ez3d_config_t *cfg, stl_writer_t *direct, trimesh_t *buf) { mesh_ctx_t m; if ((!direct) == (!buf)) { fprintf(stderr, "ez3d: internal: exactly one sink required\n"); return -1; } m.sink.direct = direct; m.sink.buf = buf; m.tol = cfg->tolerance; m.fold = cfg->fold; m.min_group_xy = 1; m.max_group_xy = 12; m.grp = 0; m.alloc_grp = 0; m.used_grp = 0; m.cells_grp = 0; const int w = m.w = img->w; const int h = m.h = img->h; const int w1 = w + 1; const int h1 = h + 1; /* * These first three vertex arrays must start at zero because they are * used as accumulators and then get divided down to make an average. * - **v0** is the corner vertex height between four cells. * - **v1** is the middle edge vertex height between two cells. * - **v2** is the other edge between two cells. * * See `ez3d_mesh_dump_cells()` and run some test dumps to get the * idea of where all the height bits fit together. */ m.v0_hght = calloc((size_t)w1 * h1, sizeof(float)); m.v1_hght = calloc((size_t)w1 * h1, sizeof(float)); m.v2_hght = calloc((size_t)w1 * h1, sizeof(float)); /* * The cell height is at the center of the cell. * It comes direct from the image but might as well start with all * zero to ensure at least we get predictable results. * Zero status value means "not visited yet". */ m.c_hght = calloc((size_t)w * h, sizeof(float)); m.c_stat = calloc((size_t)w1 * h1, 1); if (!m.v0_hght || !m.v1_hght || !m.v2_hght || !m.c_stat || !m.c_hght) { fprintf(stderr, "ez3d: out of memory building %dx%d mesh\n", w, h); ez3d_cleanup(&m); return -1; } const int zval_error = ez3d_mesh_zval(img, cfg, &m); if (zval_error != 0) { ez3d_cleanup(&m); return -1; } if (cfg->test_dump_cells) { printf("base=%f\theight=%f\ttolerance=%f\tedge=%f\n", cfg->base, cfg->height, cfg->tolerance, cfg->edge); ez3d_mesh_dump_cells(&m); ez3d_cleanup(&m); fprintf(stderr, "ez3d: Exit early because of test mode.\n"); return -1; } if (cfg->simplify > 0) { m.alloc_grp = 4096; m.grp = calloc(m.alloc_grp, sizeof(mesh_group_t)); if (!m.grp) { fprintf(stderr, "ez3d: out of memory building %dx%d mesh\n", w, h); ez3d_cleanup(&m); return -1; } const int group_error = ez3d_group_cells(&m); if (group_error != 0) { ez3d_cleanup(&m); return -1; } printf("ez3d: discovered %d groups, containing %d cells\n", m.used_grp, m.cells_grp); if (cfg->test_dump_groups) { ez3d_dump_groups(&m); ez3d_cleanup(&m); fprintf(stderr, "ez3d: Exit early because of test mode.\n"); return -1; } emit_all_groups(&m); } /* * Triangle output round, visit every pixel and emit valid triangles. */ const int cell_error = ez3d_emit_single_cells(&m); if (cell_error != 0) { ez3d_cleanup(&m); return -1; } ez3d_cleanup(&m); if (m.sink.direct) return (long)m.sink.direct->ntri; return (long)m.sink.buf->ntri; }