Computer Graphics Stack Exchange
Computer Graphics Stack Exchange

Questions tagged [polygon]

54 questions
14
votes
1 answer

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 following image, the red dots are my initial points,…
arthur.sw
  • 377
  • 2
  • 14
12
votes
1 answer

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

For mesh representation, what is the benefit of using Half Edge over Winged Edge data structure? I understand both mesh representations, the only difference is that half edge uses directional edge and winged edge uses undirectional edge. So far, I…
Bla...
  • 451
  • 4
  • 12
10
votes
0 answers

How to describe the bi-directional links for the Weiler-Atherton algorithm?

My postscript interpreter currently implements the Hodgeman-Sutherland clipping algorithm but this is limited to simpler shapes and doesn't have a provision for utilizing various winding-number rules. So it doesn't help me to implement even-odd…
luser droog
  • 1,328
  • 2
  • 12
  • 27
10
votes
1 answer

Pipeline to create Voronoi Meshes

I would like to implement a Maya plugin (this question is independent from Maya) to create 3D Voronoi patterns, Something like I just know that I have to start from point sampling (I implemented the adaptive poisson sampling algorithm described in…
Jiloc
  • 201
  • 1
  • 5
9
votes
1 answer

Find the longest straight line between two points on surface of polygon

My shape is a slightly concave polygon, and I'd like to know the maximal diameter. I imagine a straight line between two points on the surface of the polygon, such that the line does not pass outside the polygon. Is there a general algorithm for…
jiggunjer
  • 191
  • 3
7
votes
1 answer

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

How can I check if a polygon (can also be irregular) can completely contain a circle of a certain radius? I do not want to actually draw a circle inside the polygon but just a boolean outcome whether or not it can be fit. I need this for an…
user7413
  • 123
  • 3
6
votes
1 answer

List of triangles to minimum amount of convex polygons

I'm in search for an algorithm that takes the left side of the following graphic as an input and outputs a minimal amount of convex polygons as seen on the right side of the graphic. The input mesh can be very complex and could contain several…
Timm
  • 538
  • 2
  • 11
6
votes
2 answers

Converting cartesian pixels to polar pixels

(I've largely revamped this entire question, though the motivation remains the same.) revised question I want to convert a raster of cartesian pixels into polar pixels. Is there a sensible algorithm for doing this? For example, how do I compute…
fearless_fool
  • 163
  • 6
6
votes
3 answers

Explanation of the Vatti clipping algorithm

I am going through the Vatti Arbitrary Polygon Clipping Algorithm, but got stuck at their very initial explanation. It says the following: Call an edge of a polygon a left or right edge if the interior of the polygon is to the right or left,…
sajis997
  • 1,209
  • 1
  • 9
  • 13
6
votes
2 answers

Finding the angle of any side of a polygon

I'm trying to find the angle it would take for me to rotate a polygon so that a specific side is completely horizontal and on the bottom. For example, a shape like this: Needs to be rotated so the side with the red square on it is on the bottom and…
mmmeff
  • 163
  • 3
5
votes
3 answers

Rounding corners of polygon given vertices of its corners

Given a polygon (regular or irregular, convex or concave), I want to round its corner, with a given radius; let's say 'x'. I have the code to draw an arc given 2 points, but how can I find the start and end points of the arc? All I have is a list of…
user3453636
  • 105
  • 4
5
votes
1 answer

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

I am creating a simple 3D engine as a learning project to get the hang on spherical trigonometry. I am using the following approach. 1. A model consists of a lot of triangular faces. 2. Each triangle is rendered through finding where the vectors…
SE - stop firing the good guys
  • 171
  • 4
4
votes
1 answer

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

I'm new to computer graphics and just wanted a solid understanding of why? Why is it so important that polygons you push through the pipeline be "simple" and "convex"?
user9778
  • 191
  • 3
  • 7
4
votes
1 answer

Vertices of a regular polygon given the incircle radius

How can I find the vertices of a polygon (specifically hexagon) given the radius of the incircle? I want to calculate the vertices of a polygon given the face-to-face distance (inscribed circle diameter?) I've below code to calculate the vertices…
user7413
  • 123
  • 3
4
votes
1 answer

Polygons versus curve primitives in software rendering

Most 3D video games since the nineties have used hardware rendering based on polygons. Why polygons? They work well for some things, but not so well for others, e.g. a human figure rendered in polygons looks bad unless the polygon count is very…
rwallace
  • 143
  • 4
1
2 3 4