# Questions tagged [triangulation]

The tag has no usage guidance.

35 questions
Filter by
Sorted by
Tagged with
0 votes
1 answer
147 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,161
0 votes
1 answer
95 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,161
0 votes
1 answer
79 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 ...
• 13
1 vote
1 answer
138 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
2 votes
2 answers
244 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,696
1 vote
1 answer
311 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
3 votes
1 answer
662 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
0 votes
1 answer
120 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
0 votes
0 answers
41 views

• 1,696
0 votes
2 answers
298 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
1 vote
2 answers
172 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
0 votes
1 answer
738 views

### How to triangulate a simple 2d surface to generate a constrained surface trimesh

I want to split a couple of simple 2d forms into tri meshes. The meshes should conserve the original geometry and ideally I'd like a possibility to influence refinement vs. tris count. I have the 2d ...
• 101
1 vote
1 answer
312 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
0 answers
980 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
3 votes
1 answer
290 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
2 votes
1 answer
612 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
8 votes
1 answer
4k 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 ...
25 votes
5 answers
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 ...
0 votes
3 answers
820 views

### Return x; y; coordinates of vertex C of triangle

I would like to return the XY coordinates of vertex C using math formula. I have 5 input data what I always know and can be used for solution (green in the image): I know X; Y; coordinates of point A ...
11 votes
3 answers
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
4 votes
1 answer
474 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 ...
7 votes
1 answer
211 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
8 votes
1 answer
415 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
4 votes
2 answers
843 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?
2 votes
1 answer
178 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 ...
4 votes
2 answers
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
14 votes
1 answer
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
3 votes
0 answers
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
5 votes
1 answer
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
12 votes
3 answers
537 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 ...