Skip to main content
Share Your Experience: Take the 2024 Developer Survey

Questions tagged [graphics]

The tag has no usage guidance.

Filter by
Sorted by
Tagged with
19 votes
3 answers
2k views

Ray Tracing versus object-based rendering?

Intro graphics courses usually have a project that asks you to build a ray tracer to render a scene. Many graphics students entering grad school say that they want to work on ray tracing. And yet it ...
Suresh's user avatar
  • 5,387
15 votes
2 answers
401 views

Which method is preferred for storing large geometric objects in a quadtree?

When placing geometric objects in a quadtree (or octree), you can place objects that are larger than a single node in a few ways: Placing the object's reference in every leaf for which it is ...
nsantorello's user avatar
10 votes
3 answers
2k views

Intuition for convolution in image processing

I have read many documents about convolution in image processing, and most of them say about its formula, some additional parameters. No one explains the intuition and real meaning behind doing ...
hqt's user avatar
  • 223
10 votes
2 answers
7k views

What is the difference between luma and luminance?

I understand the following (correct me if I'm wrong): Statements Luma as the weighted sum of RGB gamma corrected components, but luminance is the weighted sum of RGB linear components. The gamma ...
winnie99's user avatar
  • 155
10 votes
1 answer
2k views

How to find contour lines for Appel's Hidden Line Removal Algorithm

For fun I am trying to make a wire-frame viewer for the DCPU-16. I understand how do do everything except how to hide the lines that are hidden in the wire frame. All of the questions here on SO all ...
Scott Chamberlain's user avatar
10 votes
1 answer
1k views

Is the shadow ray in a Whitted ray tracer occluded by transparent objects?

In a Whitted ray tracer, each ray-object intersection spawns a transmitted ray (if the object was translucent), a reflected ray and a shadow ray. The shadow ray contributes the direct lighting ...
user11171's user avatar
  • 203
9 votes
1 answer
3k views

What is the difference between a R-tree and a BVH?

I've just read about R-Trees: The key idea of the data structure is to group nearby objects and represent them with their minimum bounding rectangle in the next higher level of the tree; the "R" in ...
Martin Thoma's user avatar
  • 2,360
7 votes
2 answers
1k views

What are all the differences between the Gibbs phenomenon artefects and JPEG artefacts?

I thought the Gibbs phenomenom is the result of Fourier analysis estimation (but was it Fourier Series estimation or can it also be Fourier Transform estimation?) JPEG uses the Discrete cosines ...
Higgins's user avatar
  • 91
7 votes
1 answer
2k views

Line smoothing algorithm that perserve data uniformity

Intro: I'm working with huge data set that i need to plot in browser, and since there may be up to 1M points my idea was to create different representations for different zoom levels lets say i have ...
Dragan B.'s user avatar
  • 171
6 votes
1 answer
873 views

What are some interesting applications of the skyline problem?

You are given a set of $n$ rectangles in no particular order. They have varying widths and heights, but their bottom edges are collinear, so that they look like buildings on a skyline. For each ...
jsguy's user avatar
  • 629
6 votes
1 answer
348 views

Radon transform for advanced 3d graphics and games?

The Radon transform is used to take 2d projections of an object and create a 3d representation. It seems like it would be possible to apply such a transform in 3d graphics in games (although possibly ...
Archival's user avatar
  • 171
5 votes
3 answers
4k views

What's the point of 48 bit colour?

I've read that the human eye can only really decipher around 10 million different colours, so what's the point in technology that uses 48-bit colour, which allows for $2.81\times 10^{14}$ colours....
Eric's user avatar
  • 73
5 votes
2 answers
777 views

Segmenting a human body point cloud into limbs

I have a human body point cloud taken through a Kinect (v1). Now, I want to segment the point cloud into different parts, namely hands, lower arms, upper arms, torso, upper legs, lower legs, feet and ...
Ranveer's user avatar
  • 153
4 votes
4 answers
4k views

How to generate stereo image pair from a stationary mono camera?

I have a stationary mono camera which captures a single image frame at some fps. Assume the camera is not allowed to move,how do i generate a stereo image pair of the acquired frame? Is there any ...
veerendra's user avatar
4 votes
1 answer
382 views

Why there is light source?

In ray tracing if we are tracing a ray from camera to the object, then why there is need for light source as in this image and also rays are going towards the light source instead of outgoing from the ...
Mr.Grey's user avatar
  • 171
4 votes
2 answers
545 views

Detecting if an edge is "inside" a polygon?

I have computed a constrained triangulation of a set of points. The constraint happens to be a closed polygon. The objective is to detect all edges which are inside the polygon, that is, an edge where ...
Makogan's user avatar
  • 341
4 votes
2 answers
2k views

Algorithm for antialiasing thin lines

A very tricky problem in graphics rendering is drawing thin lines ($1px$ width) that do not look jaggy. The only implementation I have seen that is very good is that in Mathematica, but their ...
Tyler Durden's user avatar
4 votes
1 answer
738 views

Why are division/floating points inefficient in comparison to integer addition/multiplication/subtraction?

Why does Bresenham's line algorithm eliminate dy/dx division and the multiplication of that (potentially floating point) number?
Dylanthepiguy's user avatar
4 votes
1 answer
490 views

Point in Polygon Problem: Has anybody invoked the line integral?

Some twenty years prior I was given the task to solve the Point in Polygon problem for a piece of commercial software. I solved it invoking the ray casting algorithm. After a variety of enhancements ...
Mountainview's user avatar
4 votes
1 answer
776 views

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

Suppose I have a set of points in 3D which are all co-planar, and which describe the vertices of a convex polygon. I know the coordinates of all of these vertices, I know the unit normal to the plane ...
John Barber's user avatar
4 votes
1 answer
164 views

BVH construction without sorting

Common algorithms for creating bounding-volume-hierarchies (BVH) rely on grouping primitives together that are not necessarily adjacent in memory. This is either done by rearranging the primitives ...
thessalchips's user avatar
4 votes
1 answer
56 views

Detecting rotational symmetries of spatial structures

I have a spatial graph-like structure. The structure consists of vertices in the 3D space and connecting edges. Are there any algorithms available that would identify the rotational symmetries of ...
Botond's user avatar
  • 143
4 votes
0 answers
108 views

Computing average tile size (grid)

I am trying to compute the average cell size on the following set of points, as seen on the picture: . The picture was generated using gnuplot: ...
malat's user avatar
  • 141
3 votes
1 answer
1k views

Convert NURBS curve into Cubic Bezier Curve

From this: Maybe you already know this, but it's impossible to convert nurbs to bezier splines exactly because nurbs are rational functions, and bezier splines are polynomials. I don't understand ...
Lance's user avatar
  • 2,243
3 votes
1 answer
209 views

Complexity of "Fast Poisson Disk Sampling in Arbitrary Dimensions"

I came across the paper Fast Poisson Disk Sampling in Arbitrary Dimensions which gives an algorithm for generating Poisson disk points in $\mathbb{R}^n$. It's claimed that the algorithm is linear ...
overfull hbox's user avatar
3 votes
1 answer
1k views

Finding all faces in a wireframe mesh

I'm trying to find an algorithm for finding all faces in a wireframe mesh. Wireframe means only the vertices and edges are given as input. There is no restriction on the number of edges a resulting ...
hgs3's user avatar
  • 253
3 votes
1 answer
390 views

How can I efficiently plot the inside of an ellipse?

I am given the the coefficients for an ellipse in the form: $$Ax^2 + Bxy + Cy^2 + Dx + Ey + F=0.$$ I have a 2 dimensional array of point objects (in Python) called "pixels", and I need to give each ...
Jbag1212's user avatar
  • 133
3 votes
1 answer
126 views

compute a gradient with "minimal" colorstops from a ordered set of RGB colors

I got a array of colors that are closely related = most of the time there is no sharp transition between color[n] and color[n+1]. Exemple of such an array of colors [0,.1,.2,.3,.4,.5,.6,.7,.8,.9,1.0,...
v1nce's user avatar
  • 133
3 votes
1 answer
282 views

Image Comparison tuned to Human Perception

Say I have two systems that take the same drawing commands and starts drawing on their respective platforms (i.e. HTML Canvas). After this is done, I want to save and compare these two images to ...
Greg's user avatar
  • 33
3 votes
1 answer
1k views

How does the Sutherland-Hodgman Algorithm work?

The following are the Pages-96 and Page-97 of the book Schaum's outline series of Computer Graphics. The algorithm considers several things: (1) Whether the polygon is Convex or Concave. (2) ...
user avatar
3 votes
2 answers
340 views

Closing shapes at non-endpoints

Consider how one would represent the following image in vector graphics: Pretty simple, right? The entire shape can be represented by a single path element. But suppose additionally that you want ...
Guest's user avatar
  • 53
3 votes
1 answer
3k views

What the difference between the Fourier Transform of an image and an image histogram?

Consider this small picture of a sunflower, and its histogram: What would the Fourier transform of the first picture look like? Is there any relationship between the histogram and the Fourier ...
user8005's user avatar
3 votes
0 answers
111 views

Algorithm to count number of overlapping rectangles of the same colour?

Say you have a grid of pixels. And there are 20 overlapping red rectangles on a blue background. I want to find an algorithm to count the minimum number of rectangles that are needed to form the image....
zooby's user avatar
  • 263
3 votes
0 answers
74 views

area of the projection of a mesh

Given: a quadrilateral mesh that forms the surface of a sphere a linear projection from 3D to 2D (a 2x3 matrix) The mesh is not convex in general, but it is regular enough that we know that the ...
Glenn Davis's user avatar
3 votes
0 answers
170 views

Is it possible to simulate/emulate non-euclidean geometry using computer graphics?

I am aware of the frequent use of "smoke and mirrors" in order to achieve the effect of non-euclidean geometry, but I was wondering it if it possible to implement spherical (sometimes called elliptic) ...
Joe Carr's user avatar
  • 131
3 votes
0 answers
701 views

Available algorithms for drawing (filled) Bézier paths

There are plenty of libraries around allowing to draw Bézier paths, but not that much information about how to implement one of those libraries. The question is: What algorithms are used for drawing ...
Adrian Maire's user avatar
3 votes
0 answers
33 views

What is the most efficient algorithm for finding the bounding inequalities of a cone given the extremal rays?

Say that I am given a cone, as specified by the extremal rays whose facets form its convex hull, what is the most efficient algorithm that finds the linear-rank inequalities whose intersection defines ...
Ning Bao's user avatar
3 votes
0 answers
549 views

Algorithm to outline a group of points

I have a set of coordinates, in practice gps coordinates. Some of them are in clusters and some of them are scattered. Which are which is allready determined. Thus I know which ones are in a ...
Einar Sundgren's user avatar
3 votes
0 answers
217 views

Simplify closed-path points without intruding into the inside of the path

I want to: Simplify a set of points that outlines a closed opaque image on a transparent background. The simplified set of points should not intrude into the closed opaque image. I use a Marching ...
markE's user avatar
  • 131
2 votes
1 answer
344 views

How curves are represented in a computer

I am confused now (in thinking about limits and continuity) how curves are represented in a typical modern computer. Curves are "continuous" in that there is no discrete change from one angle to the ...
Lance's user avatar
  • 2,243
2 votes
1 answer
14k views

How do I compute the luminance of a pixel?

I have a color (say $R=100, G=150, B=130$). How do I compute its intensity? Do I just sum up all three components? Or are the colors not evenly weighted?
David Faux's user avatar
  • 1,607
2 votes
2 answers
413 views

Is there a working O(1)-space flood fill algorithm?

This is a purely theoretical question: among the known flood fill algorithms, there is one which does not require any dynamically-sized data structures, explicit or implicit: the so-called Walk-based ...
Leo B.'s user avatar
  • 133
2 votes
1 answer
188 views

Bresenham's line drawing algorithm guarantees

I am considering implementing my own version of Bresenham's line drawing algorithm, found here, my one question is does the algorithm guarantee that both endpoints will be covered/drawn. I am doubting ...
yosmo78's user avatar
  • 187
2 votes
1 answer
134 views

Hyperplane through origin which goes through most number of points

Given $M$ points in $\mathbb{R}^{N}$ (where $M$ is larger than $N$), I was wondering if there is an algorithm to find a $N-1$-dimensional hyperplane which goes through the origin and also intersects ...
mathplebeian's user avatar
2 votes
1 answer
52 views

UV Projection of 3D shape onto 2D images

Given a 2D image of a human face and the corresponding 3D shape, how do I project the shape onto the images to extract texture patches from them to form a partial UV map?
Abhinay B's user avatar
  • 121
2 votes
1 answer
94 views

Iterate over each cell of a grid through whose interior a given line segment passes

Let $a,b>0$ and suppose we have divided the domain $\Lambda:=[0,a]\times[0,b]$ into a grid of width $n_x$ and height $h_y$. We enumerate the grid from bottom to top and left to right. Given $(x_0,...
0xbadf00d's user avatar
  • 217
2 votes
1 answer
447 views

Most Efficient Method To Determine Triangle Fill Values Based On Corner Values

I have a triangle and the value of the pixel intensity at each of the three corners of the triangle. I want to interpolate to find interpolated pixel intensities for a set of points inside the ...
RunJumpSleep's user avatar
2 votes
1 answer
257 views

Resizing and aliasing in computer science [closed]

If you resize an 1000x1000 raster image to 10x10 and resize it back to 1000x1000 is this considered to be an example of aliasing?
Higgins's user avatar
  • 91
2 votes
1 answer
1k views

How to do pixel array rotation whose angle not a multiple of 90 degree?

It is easy to rotate pixel array if the angle is a multiple of 90 degree. For example, (quote from Computer Graphics with OpenGL) We can rotate a two-dimensional object or pattern 90' counterwise ...
Jichao's user avatar
  • 121
2 votes
0 answers
109 views

A Single Row GUI Layout Algorithm

I need a layout algorithm and use it in the GUI, but I can't use existing GUI toolkits at the moment, so I would like to find a layout algorithm. I only need to do a single row layout, and here is the ...
skiars's user avatar
  • 21