Hot answers tagged

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 (...
user avatar
  • 2,580
8 votes
Accepted

How can I check if a polygon can completely contain a circle of a certain radius?

This is likely more complicated than you would prefer, but: Compute the medial axis, which immediately yields the largest disks that fit inside the polygon: their centers are vertices (degree $\ge 3$) ...
user avatar
8 votes
Accepted

What is the benefit of using Half Edge over Winged Edge?

As far as I can tell, the main advantage of half-edge is that traversal can be a bit simpler due to a guarantee of edges having a consistent orientation within each face. Consider the problem of ...
user avatar
  • 23.7k
6 votes
Accepted

Converting cartesian pixels to polar pixels

I have implemented the cartesian-to-polar-conversion and have used different interpolation methods: 1) nearest neighbor 2) a subsampling approach, which averages 81 subpixel locations 3) bilinear ...
user avatar
  • 341
6 votes

Rounding corners of polygon given vertices of its corners

Ok, Xenapior and Reynolds together have the right idea. But the explanation is a bit lacking so here is a image to explain it all and some further musings. First let us start by drawing an image (yes ...
user avatar
  • 8,169
5 votes

Why do polygons have to be "simple" and "convex"?

Polygon rasterization (the conversion of the analog polygon data into a raster image) is a key operation in rasterization-based rendering. As such, performing this operation fast, and with predictable ...
user avatar
  • 8,141
5 votes
Accepted

How to compute the following integral over a polygon?

Triangulate the Voronoi cell then write the integral as a sum over the triangles: $$\int_{\Omega}\|P - Pi\|\,dP = \sum_{k=1}^{N}\int_{\Delta_k}\|P-P_i\|\,dP.$$ Write the integration over the ...
user avatar
  • 1,837
3 votes
Accepted

Polygons versus curve primitives in software rendering

Most software rendering engines dice the parametric primitives to micropolygons, usually on the fly as needed. In essence this reduces the needed complexity to determine intersections. The surface ...
user avatar
  • 8,169
3 votes

constrain based dynamic geometry generation

It is possible to generate geometry from constraints. However, some of your constraints are hard to formulate as continuous functions that can be minimized or maximized. Also the ones that can be ...
user avatar
  • 8,169
3 votes

Vertices of a regular polygon given the incircle radius

what is the relation between radius of the in-circle and circum-circle of a polygon? That is $cos ( \frac{2\pi}{n}*\frac{1}{2} ) = cos ( \frac{\pi}{n})$ The triangle with edges from the center to ...
user avatar
3 votes
Accepted

Maximal and minimal no. of angles obtained from clipping a convex polygon with n angles

Since this is a homework question, I'll give hints rather than a numerical answer. Clipping a convex polygon Think about how many times the polygon can cross each edge of the rectangle. In general, ...
user avatar
  • 5,902
3 votes

An algorithm to find the area of intersection between a convex polygon and a 3D polyhedron?

There are different numerical approximations you could use: A simple solution is to use brute-force Monte Carlo integration. Distribute $N$ random points on the polygon and calculate the number of ...
user avatar
  • 3,556
3 votes

How to understand Z-Fighting?

The camera does not need to move for this problem to exist. You can see the mixed polygons as in your linked image even with a static camera. Things are worse with a moving camera because it makes ...
user avatar
  • 1,575
3 votes

Finding the maximum number of disconnected fragments

A convex polygon has the property: A line drawn through a convex polygon will intersect the polygon exactly twice. From this follows that any line trough splits the convex polygon in 2 pieces. ...
user avatar
  • 8,169
3 votes

Spine. What is the name of the process?

This appears to be simply skeletal animation, which is a standard technique that is available in all modern animation packages. Whether applied to 3D meshes or (as here) 2D ones, the principle is the ...
user avatar
  • 23.7k
3 votes
Accepted

Finding the angle of any side of a polygon

Deducing the angle and rotating by that angle works quite well in 2D (describe in TLousky's post). This strategy, does not extend very well into three-dimensional realm. I will provide an alternative ...
user avatar
  • 8,169
3 votes
Accepted

How to calculate vertex normals on a mesh with non-planar polygons

If you're interested in vertex normals specifically, there's an easy answer even for non-planar polygons that avoids the question of defining what the exact surface is: for each vertex, calculate the ...
user avatar
  • 23.7k
2 votes

Finding the angle of any side of a polygon

This algorithm is based on this answer for finding the angle between vectors, and this answer for rotating polygon points. It's written in Python, and assumes you want to align an edge with the X axis ...
user avatar
  • 199
2 votes

Where should I project a polygon corner when it is behind me?

Trying to explain a problem seems to help the thought process. This is what eventually worked for me: I realized that I can easily find the point (in 3D space) where a line between two of the corners ...
user avatar
2 votes

An algorithm to find the area of intersection between a convex polygon and a 3D polyhedron?

If you have GL (or equivalent) available, the easiest way is probably to set up your projection matrix so that the plane of the polygon is the near clipping plane, draw the polygon into the stencil ...
user avatar
  • 6,490
2 votes

Projection of a Polyhedron on xy Plane with CGAL

A possible way to do this is tracing the silhouette edges of the polyhedron and projecting them to a 2d polygon only at the end of the process. A silhouette edge (in your context) is defined by its ...
user avatar
2 votes

Rounding a corner formed by Arc and Line

I suppose you want an arc of C0 and C1 continuity between the line and an arc. As illustrated above, you already have a vertex A which is the intersection of an edge and an arc of which the center ...
user avatar
1 vote
Accepted

Finding vertices of the outer contour of intersecting polygons

Sounds like you’re looking for a way to do a Boolean union operation. There’s a couple of algorithms linked from that article that should do the trick.
user avatar
1 vote

Rounding corners of polygon given vertices of its corners

The cut length from the vertex is x*ctan(t/2), where t is the angle at this vertex.
user avatar
1 vote
Accepted

Rounding corners of polygon given vertices of its corners

Since you're working on CAD software, you probably want some precise results. Here an algorithm that could work: For each side: Compute the segment's equation. Compute each round corner's circle ...
user avatar
  • 800
1 vote

Fill an irregular region with 2D shapes

There is no general algorithm for packing problems. Only some of the special cases have known, and optimal, solutions. If you are packing one shape then finding a reasonable solution is possible. Like ...
user avatar
  • 8,169
1 vote

List of triangles to minimum amount of convex polygons

If a edge corner is concave then it needs to border 2 of the output polygons. So one algorithm would be to find all concave corners (including the ones in the holes) and making cuts starting from ...
user avatar
1 vote

How to understand Z-Fighting?

As others mentioned, z-fighting/stiching occurs even if the camera is not moving. However, when the camera is moving and you're getting z-fighting, it will appear as though the polygons are ...
user avatar
  • 11
1 vote

How to understand Z-Fighting?

Z-fighting is not related with camera movement. But this issue can be avoided by moving the near plane of the view frustum a little further away from the viewer. As you know, depth testing is the ...
user avatar
1 vote

Explanation of the Vatti clipping algorithm

{𝑝0,𝑝8,𝑝7,𝑝6} and {𝑝4,𝑝3,𝑝2} are called "left bounds" because if you look at both these bounds, the polygon interior is to the right of them: Likewise, {𝑝0,𝑝1,𝑝2} and {𝑝4,𝑝5,𝑝6}...
user avatar

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