<p>What it means to "triangulate complex 3D objects" is not unambiguous.
Just one possible interpretation: You have a 3D polygon in space, and you
want to triangulate that. This is NP-hard:</p>

<blockquote>
  <p>Barequet, Gill, Matthew Dickerson, and David Eppstein. "On triangulating three-dimensional polygons." <em>Proceedings of the 12th Symposium on Computational Geometry</em>. ACM, 1996. (<a href="http://dl.acm.org/citation.cfm?id=237234&amp;dl=ACM&amp;coll=DL&amp;CFID=644220912&amp;CFTOKEN=23394613" rel="nofollow noreferrer">ACM link</a>.)</p>
</blockquote>

<p><hr />
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;
<img src="https://i.sstatic.net/PeHXb.png" width="400" /></p>

CC BY-SA 3.0
2016-07-16T01:18:44.440Z
2016-07-16T01:18:44.440Z
Joseph O'Rourke
<p>I'm trying to triangulate complex 3D objects, that may have holes in them. Now I tried going over the problem myself, after a few hours I didn't get anything that would work all of the time, so I've been searching around and without much luck. Does anyone know of any algorithms, or free libraries, that would suit my needs. Links to any relevant documentation would be appreciated as well.</p>

<p>Also as a note, I'm a self taught programmer/cs-tist. </p>

<p>I have a set of points and I need to provide a game engine the shape in triangles. I get these points from a shape, I then add points to add area, subtract area, or split the shape. After modifying/adding points I need to give the game engine the shape in triangles as well as other information. Holes could be anywhere in any shape.</p>

CC BY-SA 3.0
2016-07-16T05:26:07.157Z
Can you expand on what you mean by "complex 3D objects"? How are you representing the objects currently?
Nathan Reed
CC BY-SA 3.0
2016-07-17T10:35:59.927Z
Are you dealing only with closed surfaces with holes (such as a bagel or doughnut) or also with holes that lead to the interior of the surface (such as a sphere with a hole leading inside)?
trichoplax is on Codidact now
CC BY-SA 3.0
2016-07-17T10:51:29.487Z
A given collection of points can be connected into a wide variety of different shape surfaces. Could you explain how these points are produced or how they relate to the intended surface?
trichoplax is on Codidact now
CC BY-SA 3.0
2016-08-06T22:10:58.320Z
Would using some algorithm like [marching cubes](https://en.wikipedia.org/wiki/Marching_cubes) over a density field work for you? You could populate a density field with contributions from the points and then sample from that.
porglezomp
<computational-geometry><triangulation>
Computational Geometry - Triangulation
Aaron
# Computational Geometry - Triangulation

(Asked by: username_0 on 2016-07-15)

I'm trying to triangulate complex 3D objects, that may have holes in them. Now I tried going over the problem myself, after a few hours I didn't get anything that would work all of the time, so I've been searching around and without much luck. Does anyone know of any algorithms, or free libraries, that would suit my needs. Links to any relevant documentation would be appreciated as well.

Also as a note, I'm a self taught programmer/cs-tist.

I have a set of points and I need to provide a game engine the shape in triangles. I get these points from a shape, I then add points to add area, subtract area, or split the shape. After modifying/adding points I need to give the game engine the shape in triangles as well as other information. Holes could be anywhere in any shape.

**Tags:** computational-geometry, triangulation

> **Comments:**
> **username_1**: Can you expand on what you mean by "complex 3D objects"? How are you representing the objects currently?  
> **username_2**: Are you dealing only with closed surfaces with holes (such as a bagel or doughnut) or also with holes that lead to the interior of the surface (such as a sphere with a hole leading inside)?  
> **username_2**: A given collection of points can be connected into a wide variety of different shape surfaces. Could you explain how these points are produced or how they relate to the intended surface?  
> **username_3**: Would using some algorithm like [marching cubes](https://en.wikipedia.org/wiki/Marching_cubes) over a density field work for you? You could populate a density field with contributions from the points and then sample from that.  

---

## 1 answers

### Answer by username_4 on 2016-07-16. Score: 5

What it means to "triangulate complex 3D objects" is not unambiguous.
Just one possible interpretation: You have a 3D polygon in space, and you
want to triangulate that. This is NP-hard:

> Barequet, Gill, Matthew Dickerson, and David Eppstein. "On triangulating three-dimensional polygons." *Proceedings of the 12th Symposium on Computational Geometry*. ACM, 1996. ([ACM link](http://dl.acm.org/citation.cfm?id=237234&dl=ACM&coll=DL&CFID=644220912&CFTOKEN=23394613).)

---

         
![](https://i.sstatic.net/PeHXb.png)


---

