Questions tagged [triangulation]

The tag has no usage guidance.

35 questions
Filter by
Sorted by
Tagged with
28k views

Why are quads used in filmmaking and triangle in gaming?

In film school, in the classes of 3D modeling, I was told that when we model something for films we maintain topology of 4 edged polygons. Any polygon which has more or less than 4 edge/vertex is ...
3k views

How to triangulate from a Voronoï diagram?

I computed a Voronoï diagram from a set of points (with Boost.polygon). I try to find a Delaunay triangulation, connecting each cell center for each Voronoï edge, but I miss some edges. In the ...
• 377
549 views

How can I concentrate points in areas of higher curvature?

How can I distribute points over an implicit surface, to concentrate them more densely in areas of higher curvature? I've considered adding points randomly and rejecting points not required based on ...
1k views

How can I perform a triangle inside test in polygon meshes?

I have 3 vertices (V1, V2, V3) randomly selected on a regular triangle mesh. For these 3 vertices, I have computed the geodesic distance and the path (by using ...
• 233
5k views

What is the definition of a Half Edge?

I ran into half-edges as part of the result of a Delaunay Triangulation library, but can't find an actual definition of what one is. I understand vertices, edges and faces, but can't find a concrete ...
416 views

Computational Geometry - Triangulation

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 ...
• 81
215 views

What is this triangle sub-division scheme called?

I have thought of a triangle sub-division for the purpose of smooth triangulation (no popping) over time on the fly. I think it is very likely the scheme is already invented and has a name but I can´t ...
• 359
949 views

How to decide which way to triangulate a quad?

Apologies if this is a dumb question... but given four arbitrary (non-coplanar) points in 3D space, there are obviously two different ways to triangulate the quad that they form. One triangulation may ...
• 193
2k views

Draw angles lines in raster graphics using bresenham line algorithm

I at the moment trying to draw some angled lines using bresenham line algorithm which can circulate a 2d array of size 21x21, as a line angled from 0 - 2pi. So the idea is that the program has to ...
• 183
868 views

Combination of Triangles and Quads in a mesh

Is it topological correct to combine triangles with quads to form a mesh. If not, why?
4k views

How to determine the object-to-world matrix

I want to ray trace a triangular mesh that I load from a file. The vertices' coordinates are expressed in the reference frame associated with the object (i.e the mesh) and I don't know the object-to-...
• 141
482 views

What is better to use for real-time computing Mesh - Plane intersection points, GPU or CPU?

I want to write plugin (library) for Unity3d (it doesn't matter which framework I will choose for this, question is ), for cutting arbitrary mesh with plane (for simplicity it will be plane for ...
578 views

Efficient methods to rasterize a scene of connected triangles

Assuming I wanted to rasterize a scene of triangles that are all connected that is similar to the image below, what would be an efficient way to do it on a GPU and a CPU? The triangles can be of any ...
• 33
727 views

Smooth triangular mesh interpolation

I am looking for an algorithm which would smoothly interpolate triangles of a mesh (computed by Delaunay triangulation) where each vertex has some value (elevation in my case). I need it for PDAL ...
• 133
302 views

Subdivide a triangle along its UVs

I'm looking into a problem that first occured very trivial to me, but i got stuck and it's becoming a major issue right now. I'd like to subdivide a triangle by its given UVs, e.g. if the UVs are ...
• 59
61 views

Compute angles and thereby endpoints in a raster grid?

I am at the moment having some issues with computing an endpoint in a raster grid that is also a valid position in a graph. I am trying to draw a line between these two points, but as the point I am ...
• 183
630 views

Triangulation of vertices of an ellipsoid

I have the parametric model of an ellipsoid like this: \begin{cases} x=a_1\,cos \,\eta \:cos\,\omega & -\pi\leq\omega\leq\pi \\𝑦 = 𝑎_2\,cos\,\eta\:sin\,\omega \\ z=a_3\,sin \,\eta & -\frac{...
• 321
276 views

3D triangle rasterization to voxels

Is there an algorithm to rasterize triangles into voxels (3D, not 2D) that is linear in the amount of voxels in the output? I.e. given a triangle and a grid, generate the exact voxels that the ...
• 1,706
193 views

How to compute a bounding tetrahedron

I'm wondering how to compute a bounding tetrahedron from a set of points so i can initialize a delaunay triangulation My first approach was to find the bounding box to my set of points and then ...
• 55
180 views

maximal convex patching in Computer graphics

Given a 3D object in Computer graphics, whose surface is represented as a 3D triangular mesh (mesh of 3D triangle objects), I need to find the maximum continual Convex patches on the surface of the ...
188 views

Ear-clipping algorithm for non-planar polygons

I was looking into the ear-clipping algorithm for triangulating simple polygons. I have successfully implemented it on planar polygons. However if polygon is non-planar the algorithm breaks down. ...
• 516
1 vote
331 views

Why does skinny triangle is avoided in triangulation algorithm?

I recently learned about Delaunay triangulation algorithm.. This algorithm prevents the generation of skinny triangles.. I haven't really seen any good explanation of why we don't want skinny ...
• 481
1 vote
170 views

How to get the accurate number of triangles of an wavefront obj model?

I am confused by a 'wavefront obj' file's true triangle number. For example, I downloaded the Rungholt scene from McGuire's Computer Graphics Archive. ...
• 135
1 vote
343 views

How to generate a gradient to the edges of a triangle in GLSL?

I'm looking for an effect similar to this image. Assuming the UV coordinates of the triangle are known, such as: p0 = [0, 0] p1 = [1, 0] p2 = [0, 1] I know the ...
• 113
1 vote
123 views

Constructing half-edges table from triangle list without hash

Motivation I am trying to refine a mesh such that each triangle gets subdivided into 4 triangles, but I want the vertices to be shared. For that purpose I need a half-edge data structure so I can ...
• 2,226
1 vote
991 views

How Skia uses OpenGL backend?

Skia 2D's one notable backend in OpenGL, but how does it work under the hood to render? Say, we need to draw an anti-aliased circle. Does Skia: make a quad (using 2 triangles) and paint the circle ...
• 111
1 vote
182 views

Convert triangulated object to a polygonized object

Is there an efficient algorithm to convert a 3D object described with a set of triangles to a 3D object described with a set of polygons. Polygons can have an arbitrary number of points, more is ...
• 111
148 views

Procedural generation of genus $k$ tori triangle meshes

I am looking for code or pseudo-code for the generation of genus $k$ tori triangle meshes. I want to get something like in the image here. Book/paper references, code, github links, etc. are all ...
• 2,226
134 views

Why the Bowyer's version and Watson's version of computing the Delaunay tessellation are equivalent?

Bowyer–Watson algorithm might be the most famous method for computing the Delaunay triangulation of a finite set of points in any number of dimensions. Its Wikipedia page and most textbooks on ...
• 123
305 views

What tris and quads need for?

I know that 3D artists make a 3D model with quads. And they advise to remesh with quads only (if it's possible). So I have some questions: Why do we use quads in CG (for games, cartoons, film, etc) ...
• 101
103 views

Triangle Rasterization Shaking Issues

I am making a Software renderer, and I noticed that there is a screen shaking like effect happening. shown in the first video: I tried doing filling without clipping against the small square, and the ...
• 23
41 views

• 1,706