28 votes
Accepted

Why are quads used in filmmaking and triangle in gaming?

For 3D modeling, the usual reason to prefer quads is that subdivision surface algorithms work better with them—if your mesh is getting subdivided, triangles can cause problems in the curvature of the ...
Noah Witherspoon's user avatar
19 votes
Accepted

How to triangulate from a Voronoï diagram?

The centre point in your diagram is a degenerate edge of the Voronoi diagram. If you generate a Voronoi diagram for an irregular point cloud, every vertex will have degree 3. A vertex with degree 4 (...
Martin Ender's user avatar
  • 2,720
13 votes
Accepted

What is the definition of a Half Edge?

A half-edge is an edge split along its length, and having a directional component, that is, a beginning vertex and an end vertex. Where two polygons share an edge, each polygon gets a single half-edge ...
russ's user avatar
  • 2,382
9 votes

Why are quads used in filmmaking and triangle in gaming?

As @Noah Witherspoon correctly, says triangle subdivision does not work as well as quad subdivision. Although, in the beginning triangles could not be subdivided at all. However, he does not really ...
joojaa's user avatar
  • 8,407
8 votes
Accepted

Combination of Triangles and Quads in a mesh

Topologically correct is a very vague. I believe you think of Polygon-Meshes when you say meshes, which is to represent the surface of the object by a patch of polygons, in most cases triangles or ...
Dragonseel's user avatar
  • 1,810
6 votes
Accepted

How to decide which way to triangulate a quad?

A simple heuristic that many 3D content creation apps use is to split along the shorter of the two diagonals of the quad. This generally seems to work pretty well. It minimizes the appearance of long, ...
Nathan Reed's user avatar
5 votes
Accepted

Efficient methods to rasterize a scene of connected triangles

It's an interesting question, because the advice changes over time. Having said that: On a GPU, by far the most efficient way, as Nathan Reed said in the comment, is to use the rasterisation hardware ...
Pseudonym's user avatar
  • 771
5 votes

Computational Geometry - Triangulation

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, ...
Joseph O'Rourke's user avatar
4 votes
Accepted

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

There is an alternative method that relies on flood filling. First arrange your edge data into a loop where the edges are forming a counterclockwise loop. Then start at an arbitrary point on the loop ...
joojaa's user avatar
  • 8,407
4 votes
Accepted

How to determine the object-to-world matrix

No! If you dont have this info and must have a extra frame, just assume the reference frame is a identity matrix*. The point of the extra reference frame is just to be able to move the object but if ...
joojaa's user avatar
  • 8,407
4 votes

What is this triangle sub-division scheme called?

Instead of subdividing until reaching certain edge length on screen, you should look into GPU Gems 2 article "Adaptive Tessellation of Subdivision Surfaces with Displacement Mapping" by Michael ...
JarkkoL's user avatar
  • 3,626
4 votes
Accepted

Triangulation of vertices of an ellipsoid

If you sample the two parameters $\eta$ and $\omega$ with steps $d\eta$ and $d\omega$, then you'll get a grid of points $v_{ij} = f(i\;d\eta,j\;d\omega)$. Any four adjacent points will define a ...
gilgamec's user avatar
  • 901
4 votes

How to decide which way to triangulate a quad?

One other, albeit more expensive approach, is to subdivide your quad into 4 triangles by putting a point at the centre of each quad. There are some advantages to this in that: It will be more ...
Simon F's user avatar
  • 4,231
3 votes
Accepted

Smooth triangular mesh interpolation

You may be able to eliminate the triangular artifacts by using Natural Neighbor Interpolation. You can find a description of the technique and an associated description of the algorithm at An ...
Gary Lucas's user avatar
3 votes

How to decide which way to triangulate a quad?

This isn't a dumb question. This is a much more important question than most people realize. Here's the worst case scenario for triangulating a quad: No sane artist will ever make this for static ...
user2206636's user avatar
3 votes

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

I've already commented on the use of flood fill and how it would be better as it's more flexible but another possible solution is scanline. (I say possible because it makes a lot of assumptions about ...
Andrew Wilson's user avatar
3 votes
Accepted

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

doing the calculation to decide whether a point is on one side of a plane or the other is very simple (a single dot product). Doing that 3 times and having a special case when they don't match to ...
ratchet freak's user avatar
2 votes

How to determine the object-to-world matrix

The Object-To-World matrix is often called "model-matrix". This martix tells us how the object relates to some "World". This world is relative and arbitrary but really convenient because we can place ...
Dragonseel's user avatar
  • 1,810
2 votes

Why are quads used in filmmaking and triangle in gaming?

I know this is old but game engines/graphics cards run in "triangles" because that is how they calculate mesh. They do not calculate mesh in quads. That was something created to allow all of the ...
Mike's user avatar
  • 21
2 votes

Why are quads used in filmmaking and triangle in gaming?

One thing i see most people forget is in film making it's mostly about quality not speed. That's cause film making is concerned more with Offline rendering where as in Video games it's all real time ...
gallickgunner's user avatar
2 votes

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

I think you can calculate some surface-bound barycentric coordinates for each point on the surface, and then use them to check for inside or outside of the triangle. I don't have an exact algorithm ...
Dragonseel's user avatar
  • 1,810
2 votes
Accepted

What tris and quads need for?

Because the geometry will be subdivided into quads. Anyway the primary reason for this is if you have a function with 2 directions it is easer for humans to think it out andcanticipate results if its ...
2 votes

Why does skinny triangle is avoided in triangulation algorithm?

We don't want to avoid skinny triangles as much as we want to avoid really long triangles. Long triangles make interpolation of properties less accurate because the points in which the data is stored ...
HelloGoodbye's user avatar
2 votes
Accepted

How to compute a bounding tetrahedron

While it's an old question, someone may find the following approach useful nonetheless. Calculate the (axis aligned) bounding box for your input point cloud. From that, calculate the (axis aligned) ...
Herbert Jensch's user avatar
2 votes

3D triangle rasterization to voxels

A brute force method which works well and we use in production code: Calculate AABB of triangle to create a sublist of voxels that may or may not be intersected by the triangle, also calculate the ...
lfgtm's user avatar
  • 446
1 vote
Accepted

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

You can calculate the perpendicular distance from each edge, and then take the minimum of the three edges. This is related to barycentric coordinates (which are normalized edge distances). If you ...
Nathan Reed's user avatar
1 vote

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

Bowyer's version looks like it's expressed in terms of the vertices of a Voronoi diagram. Voronoi diagrams and Delaunay triangulations are "dual" to each other, meaning that each vertex of ...
Nathan Reed's user avatar
1 vote
Accepted

Subdivide a triangle along its UVs

You can use barycentric coordinates to calculate points inside the triangle with a determinate value for uv. The process is easy => Let's say that the UV coordinates of each vertex of the triangle ...
Jordi Cruzado's user avatar
1 vote

Return x; y; coordinates of vertex C of triangle

You can get the coordinates of C by using circle equations for one circle C_A with point A as center and AC as its radius and one circle C_B with point B as its center and BC as its radius. Now you ...
Tare's user avatar
  • 1,541

Only top scored, non community-wiki answers of a minimum length are eligible