Skip to main content

Questions tagged [triangulation]

The tag has no usage guidance.

Filter by
Sorted by
Tagged with
0 votes
1 answer
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 ...
lightxbulb's user avatar
  • 2,226
1 vote
1 answer
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 ...
lightxbulb's user avatar
  • 2,226
0 votes
1 answer
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 ...
Serilena's user avatar
1 vote
1 answer
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. ...
bim's user avatar
  • 135
2 votes
2 answers
277 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 ...
Makogan's user avatar
  • 1,706
1 vote
1 answer
344 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 ...
user2867288's user avatar
3 votes
1 answer
732 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 ...
Martin Ždila's user avatar
0 votes
1 answer
135 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 ...
8cold8hot's user avatar
  • 123
0 votes
0 answers
41 views

Zebra-Like Patterns Generated By Linear PDE

I wrote some code which basically computes the color value $c_{t+1,x,y}$ of a pixel at time $t+1$ and position $(x,y)$ by taking adding linear transformations of the values $c_{t,x,y}-c_{t-1,x,y}$, $...
fweth's user avatar
  • 127
2 votes
1 answer
195 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 ...
Tawfik's user avatar
  • 55
3 votes
1 answer
580 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 ...
Sarah's user avatar
  • 33
2 votes
0 answers
189 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. ...
Lenny White's user avatar
6 votes
4 answers
952 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 ...
andygeers's user avatar
  • 193
0 votes
0 answers
56 views

MMP Geodesic algorithm I need clarification

I am reading the 1987 paper on Geodesics on polyhedra and I am confused on something. The paper states: If $I1==NIL$, the channel is simply that part of $f’$ to the left of $\beta_2c_2$; and if $I2==...
Makogan's user avatar
  • 1,706
0 votes
2 answers
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) ...
Jo K's user avatar
  • 101
1 vote
2 answers
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 ...
Looft's user avatar
  • 111
0 votes
1 answer
770 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 ...
squarespiral's user avatar
1 vote
1 answer
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 ...
Bla...'s user avatar
  • 481
1 vote
0 answers
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 ...
Abrar Borno's user avatar
3 votes
1 answer
303 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 ...
Intrins's user avatar
  • 59
2 votes
1 answer
631 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{...
Nick's user avatar
  • 321
8 votes
1 answer
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 ...
Mark A. Ropper's user avatar
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 ...
Santosh Kumar's user avatar
0 votes
3 answers
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 ...
Perjés László's user avatar
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 ...
mkocabas's user avatar
  • 233
4 votes
1 answer
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 ...
Ivan Yakovlev's user avatar
7 votes
1 answer
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 ...
Andreas's user avatar
  • 359
8 votes
1 answer
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 ...
Aaron's user avatar
  • 81
4 votes
2 answers
870 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?
user55844's user avatar
2 votes
1 answer
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 ...
Sushovan Mandal's user avatar
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-...
S.E.K.'s user avatar
  • 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 ...
arthur.sw's user avatar
  • 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 ...
Bob Burt's user avatar
  • 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 ...
Bob Burt's user avatar
  • 183
12 votes
3 answers
550 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 ...
trichoplax is on Codidact now's user avatar