2

I have a 3D wire-frame consisting of 3D points and edges. How do I go about identifying sets of vertices forming a face of the 3D object?

I am using QT and want to render a 3D object given its point set and edge set. The best I have been able to do is given three points forming a triangular face, I am able to render it in 3D. But how to do the same given more points and edges? Or, alternatively, how to break down the set in sets of 3 points forming a triangular face?

arpanmangal
  • 1,770
  • 1
  • 17
  • 34
  • Are you talking about https://en.wikipedia.org/wiki/Polygon_triangulation ? – Severin Pappadeux Mar 15 '18 at 14:20
  • @SeverinPappadeux polygon triangulation will come after recognising the faces. But first, how to recognise the faces, which are essentially planar cycles in the 3D graph. – arpanmangal Mar 15 '18 at 14:43
  • Ok, I see. So from https://en.wikipedia.org/wiki/Polygon_mesh what kind of vertices-edges representation do you have? – Severin Pappadeux Mar 15 '18 at 14:47
  • @SeverinPappadeux I have 3D points as (x,y,z) array and edges as (point1, point2). I want to derive the (triangular) faces using this information so that I can render the object using QT. – arpanmangal Mar 15 '18 at 15:13
  • So, you have your basic VV mesh, no faces, and want to get faces and triangulate them and send them to some 3D display tool, right? Mmm... I would look at openmesh.org and read Smith dissertation http://algorithmicbotany.org/papers/smithco.dis2006.pdf. – Severin Pappadeux Mar 15 '18 at 15:45
  • Thanks for the pointers. :) – arpanmangal Mar 15 '18 at 15:53
  • And CGAL might have something useful https://www.cgal.org/ – Severin Pappadeux Mar 15 '18 at 17:35

1 Answers1

0
  • Just take your first edge and its vertices (V1 and V2).
  • Find all edges that use V2 - their second vertices are your potential V3's.
  • For each potential V3 check if you have edge V1-V3 - if so, then you've found a triangle V1-V2-V3. For most meshes you should have one or two such triangles. When you're adding a new triangle always check if wasn't found already.
  • Do the same for edges that use V1.
  • Take next edge and repeat.

Depending on your exact data, edge directions, etc. it may need slight modifications but you should get the point.

kolenda
  • 2,741
  • 2
  • 19
  • 30