Hot answers tagged

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 ...


8

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$) of the axis (see the figure below). Chin, Francis, Jack Snoeyink, and Cao An Wang. "Finding the medial axis of a simple polygon in linear time." Discrete &...


7

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 iterating over all the vertices or edges of a given face, in counterclockwise order. In the half-edge structure, this can be done by starting with an arbitrary half-...


6

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 interpolation The 2nd row in the image below shows detail magnifications of the output for the three approaches: Here is the GLSL shader code for approach 1 ...


6

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 performance, is key to the performance of graphics rendering. It is possible to rasterize any arbitrary polygon. But rasterizing triangles is extremely simple ...


6

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 i know that is what they say in school for you to do but nobody does it). From the image we can see that there are 2 equal right triangles $V_2, A, C$ and $...


3

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 will still look smooth, since each polygon is smaller than a pixel. This allows for Data caching. Discrete geometric derivates. Displacement is easy to ...


3

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 formulated this way have a staggering number of dimensions making gradient descents quite costly. This means, you can not use a gradient descent method to find ...


3

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 the middle of a side, from the center to an adjacent corner and half the side connecting them is a right angle triangle. The angle of the point at the center $ =\...


3

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, a polygon can cross one of the edges of the rectangle an arbitrarily large number of times. How is this number reduced if the polygon is convex? This will give ...


3

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 the position of the polygons change, which can lead to different rounding. This means it may not be the same polygon which comes up in front at a given location ...


3

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 points inside the 3D polyhedron $N_i$ using ray tracing. The area inside the polyhedron is $A_i=A\frac{N_i}{N}$, where $A$ is the area of the polygon. To improve ...


3

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. Image 1: convex polygon split by a line. Using this, and assuming the inner piece is discarded we can craw the conclusion that there are five cases: When the ...


3

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 same. The pseudo-3D effect on the sprites is created by using a mesh where vertices are placed along the contours of the sprite texture, then animated to ...


3

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 solution that shows a general strategy that works in a larger set of cases. As a bonus this without needing to think of trigonometry as it can be encoded away. ...


2

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 (horizontal axis). If you want to align it with the Y axis, replace the xVec in the code below with a yVec = [0,1]. EDITED: Added code for rotating the ...


2

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 buffer, and then draw the polyhedron such that inside faces output a 1 fragment. (You could do this by flipping the winding of the polyhedron and turning on back-...


2

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


2

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 positioned at O and radius equal to R. The question is thus pure mathematical: given A,O,R, edge direction BA, and a corner radius r, find C,B, and T. For ...


2

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.


1

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 neighboring facets having one upwards and one downwards normal (i.e., one positive normal z-coordinate and one negative). This can be checked using ...


1

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 equation. Compute the intersections between the segment and each circle. The 2 intersection points are the new endpoints for the line segment. This doesn't handle ...


1

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 the known cases of hexagonal packing etc. However, if you have multiple diffenently sized objects then easy just flew out of the door. Some heurestics have ...


1

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 them to other concave corners. This will split the polygon in two or join 2 holes into 1 or connect a hole to the outside. The cut from a concave corner should ...


1

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 flickering. This link helped me to understand the depth buffer much better. Here he generates depth values and simulates the different kinds of precision errors you ...


1

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 stage in the graphics pipeline which is used to determine whether one pixel is in front or back of the other pixel. It is done by having a buffer known as the z-...


1

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 brakes through one of the walls in my pyramid field of view, given the coordinates of the out-of-view corner and one of the visible ones. It is only a matter ...


1

(Promoting "comment" to an answer) It looks to me that it's just finding monotonic runs of edges. Given a defined winding order (in this case anticlockwise), then you can identify {P6, P7, P8, P0} as a decreasing run, as is {P2, P3, P4}. Since the left most vertex, P8, is in (**the middle of) a decreasing run, the decreasing runs define left boundaries and, ...


1

I don't have an exact answer for this, as the answer is far from trivial. I would suggest that you have a look into computational geometry as this clearly is a visibility problem - my guess is that a solution already exist. My own idea would be: for each line segment in polygon find the visible parts of the other line segments and then pick the pair of ...


1

http://www.cs.sandia.gov/~samitch/papers/vor_final.pdf There isn't the computer algorithm in any programming languague, but u should be able to replicate it easily with some Plane Reflections and the algorithms from the above link.


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