21

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 resulting surface. For an example, take a look at these two boxes: The left one is all quads; the right one has the same overall shape, but one corner is made ...


19

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 (or more) can only happen when two (or more) vertices coincide. That means there is a zero-length edge between them. But that edge should still have a ...


11

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 between the same two vertices, which will have opposite directions if the winding order is consistent. These half-edges will have references to one another as ...


11

The idea I would try to apply would be the following: I make the example for the curve, but it should be straightforward for the application for the surface. Let's say we have a curve $\gamma$ uniformly parametrized. Let's say the parameter of the curve is $s$. Your goal is to sample point corresponding to value of $s$ such that the curvature is high. If ...


8

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 quads. There are other options to model meshes, one idea would be to use signed distance functions as for example in constructive solid geometry. So back to the ...


8

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 explain why that is the case. Which is useful information and explains why quads are preferred and how to use them. First, observe that a triangle does gets ...


5

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 because that is that it is designed for. On a CPU, one of the most efficient ways is to more-or-less mimic what rasterisation hardware does. GPU vendors are ...


5

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, Gill, Matthew Dickerson, and David Eppstein. "On triangulating three-dimensional polygons." Proceedings of the 12th Symposium on Computational Geometry. ACM, ...


4

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 you have no info about how the object should relate to other objects it does not really matter operator can move it where they want. Everything is relative, if ...


4

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 and pick edges joining that point. Use the outbound boundary edge and cross it with the other outbound edge, if it points in the direction of the face normal ...


4

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 Bunnell. It uses edge flatness test to adaptively tessellate the geometry which results in better quality with the same number of triangles. With your current ...


4

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, skinny triangles, which are generally undesirable both for visual and performance reasons. See this article: Deformation and Triangulation in Maya for some ...


4

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 quadrilateral. To get triangles, you just have to split each quad in two by a diagonal. So in the example, you'd split the quadrilateral $\{v_{00},v_{01},v_{11},v_{...


3

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 temporarily stable. If your quad vertices are moving and you were otherwise using the "shortest diagonal" approach Nathan has suggested, the tessellation ...


3

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 your geometry but for the particular set shown and many similar ones it would work.) For your example with 3 points: Find the intersection vertex from the ...


3

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 split the triangle is pretty fast. It's also a parallel problem. The hardest part is reserving the space for the output. Preparing the data to start computing this ...


2

The following naïve approach will probably not yield as nicely distributed points as the ones given by Lhf, but it should be much easier to implement and computationally faster: For two points $x$ and $y$ let $d(x,y)$ denote the average distance you want points with the average curvature of $x$ and $y$ to have, e.g., some constant multiplied with the ...


2

A good starting point is the classic paper Using particles to sample and control implicit surfaces, published in SIGGRAPH 1994. A simple particle simulation described in the paper Sampling implicit objects with physically-based particle systems (Computers & Graphics, 1996) for curves works for surfaces as well; see Dynamic Texture for Implicit Surfaces ...


2

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 all our objects and even the camera in it and the math works out pretty well. The short answer is, that you imagine that the model is defined in the origin of ...


2

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 at hand but I found this following paper which does seem to handle exactly this kind of coordinates. Barycentric Coordinates On Surfaces


2

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 so performance/speed is much more crucial than quality. Hence when it comes to video games people try to find the best way to "approximate" or "fake" the look ...


2

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 a quad. Software renderers dont have to rely on triangles. And did not for a long time. But then if you microdice your surface who cares its not like you can ...


2

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 are farther apart. This is equivalent to – when using a 2160p (4K UHD) screen – the preference of watching a 1080p video in fullscreen mode to watching the ...


1

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 are: vertex 0 => u0,v0 vertex 1 => u1,v1 vertex 2 => u2,v2 A point inside the triangle has UV coordinates value expressed in function of its barycentric ...


1

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 can calculate their intersection points, which leaves you with 2 points (iff C is not on a line between A and B). I am not entirely sure how you want to ...


1

None of today's graphics interfaces support quads by default in the first place. This means that quads, when actually set up for rendering, are just pairs of triangles.


1

Start from any triangle. Traverse it's edge's and check that the angle between the two triangles is less than 180deg. If it is add it to the current selection and continue expanding. The check is actually really simple if you use vector geometry. Say A - B is the common edge with C on the selected side and D on the other. Then just check if dot((D-B), cross(...


1

The endpoint of the line doesn't extend out to the edge of the box because you're using the circle equation with a fixed radius: double x2 = x1 + (lenght * cos(radians)); double y2 = y1 + (lenght * sin(radians)); This makes the endpoint trace out a circle as the angle is changed. If you want the endpoint to be on the edge of the box, one way is to set up ...


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