# Questions tagged [triangulation]

The tag has no usage guidance.

35 questions
Filter by
Sorted by
Tagged with
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 ...
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 ...
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 ...
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 ...
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. ...
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 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 ...
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 ...
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 ...
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 ...
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 ...
41 views

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) ...
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 ...
767 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 ...
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 ...
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 ...
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{...
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 ...
832 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 ...
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 ...
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 ...
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 ...
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 ...
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 ...
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 ...
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?
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 ...
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-...