Skip to content

Commit 9109078

Browse files
tylermorganwallsyoyo
tylermorganwall
and
syoyo
authored
Fix normal flipping during triangulation (tinyobjloader#340)
* Fix normal flipping during triangulation -Update triangulation routine to use Newell's method to ensure polygons aren't flipped when triangulated -Don't triangulate when npolys == 3 * Fix compile. * Update tiny_obj_loader.h -Remove dependency on C++11 by using a custom struct instead of an std::array * Update tiny_obj_loader.h -Fix compilation by adding default constructor and remove array access * Update tiny_obj_loader.h -Fix struct constructor * Update tiny_obj_loader.h -Change array access to struct member Co-authored-by: Syoyo Fujita <syoyo@lighttransport.com>
1 parent 6db06ee commit 9109078

1 file changed

Lines changed: 152 additions & 60 deletions

File tree

‎tiny_obj_loader.h‎

Lines changed: 152 additions & 60 deletions
Original file line numberDiff line numberDiff line change
@@ -1397,6 +1397,41 @@ static int pnpoly(int nvert, T *vertx, T *verty, T testx, T testy) {
13971397
return c;
13981398
}
13991399

1400+
struct TinyObjPoint {
1401+
real_t x, y, z;
1402+
TinyObjPoint() : x(0), y(0), z(0) {}
1403+
TinyObjPoint(real_t x_, real_t y_, real_t z_) :
1404+
x(x_), y(y_), z(z_) {}
1405+
};
1406+
1407+
inline TinyObjPoint cross(const TinyObjPoint &v1, const TinyObjPoint &v2) {
1408+
return TinyObjPoint(v1.y * v2.z - v1.z * v2.y,
1409+
v1.z * v2.x - v1.x * v2.z,
1410+
v1.x * v2.y - v1.y * v2.x);
1411+
}
1412+
1413+
inline real_t dot(const TinyObjPoint &v1, const TinyObjPoint &v2) {
1414+
return (v1.x * v2.x + v1.y * v2.y + v1.z * v2.z);
1415+
}
1416+
1417+
inline real_t GetLength(TinyObjPoint &e) {
1418+
return std::sqrt(e.x*e.x + e.y*e.y + e.z*e.z);
1419+
}
1420+
1421+
inline TinyObjPoint Normalize(TinyObjPoint e) {
1422+
real_t inv_length = 1.0 / GetLength(e);
1423+
return TinyObjPoint(e.x * inv_length, e.y * inv_length, e.z * inv_length );
1424+
}
1425+
1426+
1427+
inline TinyObjPoint WorldToLocal(const TinyObjPoint& a,
1428+
const TinyObjPoint& u,
1429+
const TinyObjPoint& v,
1430+
const TinyObjPoint& w) {
1431+
return TinyObjPoint(dot(a,u),dot(a,v),dot(a,w));
1432+
}
1433+
1434+
14001435
// TODO(syoyo): refactor function.
14011436
static bool exportGroupsToShape(shape_t *shape, const PrimGroup &prim_group,
14021437
const std::vector<tag_t> &tags,
@@ -1425,7 +1460,7 @@ static bool exportGroupsToShape(shape_t *shape, const PrimGroup &prim_group,
14251460
continue;
14261461
}
14271462

1428-
if (triangulate) {
1463+
if (triangulate && npolys != 3) {
14291464
if (npolys == 4) {
14301465
vertex_index_t i0 = face.vertex_indices[0];
14311466
vertex_index_t i1 = face.vertex_indices[1];
@@ -1534,65 +1569,59 @@ static bool exportGroupsToShape(shape_t *shape, const PrimGroup &prim_group,
15341569
shape->mesh.smoothing_group_ids.push_back(face.smoothing_group_id);
15351570

15361571
} else {
1572+
#ifdef TINYOBJLOADER_USE_MAPBOX_EARCUT
15371573
vertex_index_t i0 = face.vertex_indices[0];
1538-
vertex_index_t i1(-1);
1539-
vertex_index_t i2 = face.vertex_indices[1];
1574+
vertex_index_t i0_2 = i0;
15401575

1541-
// find the two axes to work in
1542-
size_t axes[2] = {1, 2};
1576+
// TMW change: Find the normal axis of the polygon using Newell's method
1577+
TinyObjPoint n;
15431578
for (size_t k = 0; k < npolys; ++k) {
1544-
i0 = face.vertex_indices[(k + 0) % npolys];
1545-
i1 = face.vertex_indices[(k + 1) % npolys];
1546-
i2 = face.vertex_indices[(k + 2) % npolys];
1579+
i0 = face.vertex_indices[k % npolys];
15471580
size_t vi0 = size_t(i0.v_idx);
1548-
size_t vi1 = size_t(i1.v_idx);
1549-
size_t vi2 = size_t(i2.v_idx);
15501581

1551-
if (((3 * vi0 + 2) >= v.size()) || ((3 * vi1 + 2) >= v.size()) ||
1552-
((3 * vi2 + 2) >= v.size())) {
1553-
// Invalid triangle.
1554-
// FIXME(syoyo): Is it ok to simply skip this invalid triangle?
1555-
continue;
1556-
}
1582+
size_t j = (k + 1) % npolys;
1583+
i0_2 = face.vertex_indices[j];
1584+
size_t vi0_2 = size_t(i0_2.v_idx);
1585+
15571586
real_t v0x = v[vi0 * 3 + 0];
15581587
real_t v0y = v[vi0 * 3 + 1];
15591588
real_t v0z = v[vi0 * 3 + 2];
1560-
real_t v1x = v[vi1 * 3 + 0];
1561-
real_t v1y = v[vi1 * 3 + 1];
1562-
real_t v1z = v[vi1 * 3 + 2];
1563-
real_t v2x = v[vi2 * 3 + 0];
1564-
real_t v2y = v[vi2 * 3 + 1];
1565-
real_t v2z = v[vi2 * 3 + 2];
1566-
real_t e0x = v1x - v0x;
1567-
real_t e0y = v1y - v0y;
1568-
real_t e0z = v1z - v0z;
1569-
real_t e1x = v2x - v1x;
1570-
real_t e1y = v2y - v1y;
1571-
real_t e1z = v2z - v1z;
1572-
real_t cx = std::fabs(e0y * e1z - e0z * e1y);
1573-
real_t cy = std::fabs(e0z * e1x - e0x * e1z);
1574-
real_t cz = std::fabs(e0x * e1y - e0y * e1x);
1575-
const real_t epsilon = std::numeric_limits<real_t>::epsilon();
1576-
// std::cout << "cx " << cx << ", cy " << cy << ", cz " << cz <<
1577-
// "\n";
1578-
if (cx > epsilon || cy > epsilon || cz > epsilon) {
1579-
// std::cout << "corner\n";
1580-
// found a corner
1581-
if (cx > cy && cx > cz) {
1582-
// std::cout << "pattern0\n";
1583-
} else {
1584-
// std::cout << "axes[0] = 0\n";
1585-
axes[0] = 0;
1586-
if (cz > cx && cz > cy) {
1587-
// std::cout << "axes[1] = 1\n";
1588-
axes[1] = 1;
1589-
}
1590-
}
1591-
break;
1592-
}
1593-
}
15941589

1595-
#ifdef TINYOBJLOADER_USE_MAPBOX_EARCUT
1590+
real_t v0x_2 = v[vi0_2 * 3 + 0];
1591+
real_t v0y_2 = v[vi0_2 * 3 + 1];
1592+
real_t v0z_2 = v[vi0_2 * 3 + 2];
1593+
1594+
const TinyObjPoint point1(v0x,v0y,v0z);
1595+
const TinyObjPoint point2(v0x_2,v0y_2,v0z_2);
1596+
1597+
TinyObjPoint a(point1.x - point2.x, point1.y - point2.y, point1.z - point2.z);
1598+
TinyObjPoint b(point1.x + point2.x, point1.y + point2.y, point1.z + point2.z);
1599+
1600+
n.x += (a.x * b.z);
1601+
n.y += (a.z * b.x);
1602+
n.z += (a.x * b.y);
1603+
}
1604+
real_t length_n = GetLength(n);
1605+
//Check if zero length normal
1606+
if(length_n <= 0) {
1607+
continue;
1608+
}
1609+
//Negative is to flip the normal to the correct direction
1610+
real_t inv_length = -1.0f / length_n;
1611+
n.x *= inv_length;
1612+
n.y *= inv_length;
1613+
n.z *= inv_length;
1614+
1615+
TinyObjPoint axis_w, axis_v, axis_u;
1616+
axis_w = n;
1617+
TinyObjPoint a;
1618+
if(abs(axis_w.x) > 0.9999999) {
1619+
a = TinyObjPoint(0,1,0);
1620+
} else {
1621+
a = TinyObjPoint(1,0,0);
1622+
}
1623+
axis_v = Normalize(cross(axis_w, a));
1624+
axis_u = cross(axis_w, axis_v);
15961625
using Point = std::array<real_t, 2>;
15971626

15981627
// first polyline define the main polygon.
@@ -1601,17 +1630,24 @@ static bool exportGroupsToShape(shape_t *shape, const PrimGroup &prim_group,
16011630

16021631
std::vector<Point> polyline;
16031632

1633+
//TMW change: Find best normal and project v0x and v0y to those coordinates, instead of
1634+
//picking a plane aligned with an axis (which can flip polygons).
1635+
16041636
// Fill polygon data(facevarying vertices).
16051637
for (size_t k = 0; k < npolys; k++) {
16061638
i0 = face.vertex_indices[k];
16071639
size_t vi0 = size_t(i0.v_idx);
16081640

16091641
assert(((3 * vi0 + 2) < v.size()));
16101642

1611-
real_t v0x = v[vi0 * 3 + axes[0]];
1612-
real_t v0y = v[vi0 * 3 + axes[1]];
1643+
real_t v0x = v[vi0 * 3 + 0];
1644+
real_t v0y = v[vi0 * 3 + 1];
1645+
real_t v0z = v[vi0 * 3 + 2];
1646+
1647+
TinyObjPoint polypoint(v0x,v0y,v0z);
1648+
TinyObjPoint loc = WorldToLocal(polypoint, axis_u, axis_v, axis_w);
16131649

1614-
polyline.push_back({v0x, v0y});
1650+
polyline.push_back({loc.x, loc.y});
16151651
}
16161652

16171653
polygon.push_back(polyline);
@@ -1626,19 +1662,19 @@ static bool exportGroupsToShape(shape_t *shape, const PrimGroup &prim_group,
16261662
index_t idx0, idx1, idx2;
16271663
idx0.vertex_index = face.vertex_indices[indices[3 * k + 0]].v_idx;
16281664
idx0.normal_index =
1629-
face.vertex_indices[indices[3 * k + 0]].vn_idx;
1665+
face.vertex_indices[indices[3 * k + 0]].vn_idx;
16301666
idx0.texcoord_index =
1631-
face.vertex_indices[indices[3 * k + 0]].vt_idx;
1667+
face.vertex_indices[indices[3 * k + 0]].vt_idx;
16321668
idx1.vertex_index = face.vertex_indices[indices[3 * k + 1]].v_idx;
16331669
idx1.normal_index =
1634-
face.vertex_indices[indices[3 * k + 1]].vn_idx;
1670+
face.vertex_indices[indices[3 * k + 1]].vn_idx;
16351671
idx1.texcoord_index =
1636-
face.vertex_indices[indices[3 * k + 1]].vt_idx;
1672+
face.vertex_indices[indices[3 * k + 1]].vt_idx;
16371673
idx2.vertex_index = face.vertex_indices[indices[3 * k + 2]].v_idx;
16381674
idx2.normal_index =
1639-
face.vertex_indices[indices[3 * k + 2]].vn_idx;
1675+
face.vertex_indices[indices[3 * k + 2]].vn_idx;
16401676
idx2.texcoord_index =
1641-
face.vertex_indices[indices[3 * k + 2]].vt_idx;
1677+
face.vertex_indices[indices[3 * k + 2]].vt_idx;
16421678

16431679
shape->mesh.indices.push_back(idx0);
16441680
shape->mesh.indices.push_back(idx1);
@@ -1652,7 +1688,63 @@ static bool exportGroupsToShape(shape_t *shape, const PrimGroup &prim_group,
16521688
}
16531689

16541690
#else // Built-in ear clipping triangulation
1691+
vertex_index_t i0 = face.vertex_indices[0];
1692+
vertex_index_t i1(-1);
1693+
vertex_index_t i2 = face.vertex_indices[1];
1694+
1695+
// find the two axes to work in
1696+
size_t axes[2] = {1, 2};
1697+
for (size_t k = 0; k < npolys; ++k) {
1698+
i0 = face.vertex_indices[(k + 0) % npolys];
1699+
i1 = face.vertex_indices[(k + 1) % npolys];
1700+
i2 = face.vertex_indices[(k + 2) % npolys];
1701+
size_t vi0 = size_t(i0.v_idx);
1702+
size_t vi1 = size_t(i1.v_idx);
1703+
size_t vi2 = size_t(i2.v_idx);
16551704

1705+
if (((3 * vi0 + 2) >= v.size()) || ((3 * vi1 + 2) >= v.size()) ||
1706+
((3 * vi2 + 2) >= v.size())) {
1707+
// Invalid triangle.
1708+
// FIXME(syoyo): Is it ok to simply skip this invalid triangle?
1709+
continue;
1710+
}
1711+
real_t v0x = v[vi0 * 3 + 0];
1712+
real_t v0y = v[vi0 * 3 + 1];
1713+
real_t v0z = v[vi0 * 3 + 2];
1714+
real_t v1x = v[vi1 * 3 + 0];
1715+
real_t v1y = v[vi1 * 3 + 1];
1716+
real_t v1z = v[vi1 * 3 + 2];
1717+
real_t v2x = v[vi2 * 3 + 0];
1718+
real_t v2y = v[vi2 * 3 + 1];
1719+
real_t v2z = v[vi2 * 3 + 2];
1720+
real_t e0x = v1x - v0x;
1721+
real_t e0y = v1y - v0y;
1722+
real_t e0z = v1z - v0z;
1723+
real_t e1x = v2x - v1x;
1724+
real_t e1y = v2y - v1y;
1725+
real_t e1z = v2z - v1z;
1726+
real_t cx = std::fabs(e0y * e1z - e0z * e1y);
1727+
real_t cy = std::fabs(e0z * e1x - e0x * e1z);
1728+
real_t cz = std::fabs(e0x * e1y - e0y * e1x);
1729+
const real_t epsilon = std::numeric_limits<real_t>::epsilon();
1730+
// std::cout << "cx " << cx << ", cy " << cy << ", cz " << cz <<
1731+
// "\n";
1732+
if (cx > epsilon || cy > epsilon || cz > epsilon) {
1733+
// std::cout << "corner\n";
1734+
// found a corner
1735+
if (cx > cy && cx > cz) {
1736+
// std::cout << "pattern0\n";
1737+
} else {
1738+
// std::cout << "axes[0] = 0\n";
1739+
axes[0] = 0;
1740+
if (cz > cx && cz > cy) {
1741+
// std::cout << "axes[1] = 1\n";
1742+
axes[1] = 1;
1743+
}
1744+
}
1745+
break;
1746+
}
1747+
}
16561748

16571749
face_t remainingFace = face; // copy
16581750
size_t guess_vert = 0;

0 commit comments

Comments
 (0)