## Re: [Algorithms] Re : Re : R: Sphere to rectangle

 Re: [Algorithms] Re : Re : R: Sphere to rectangle From: Gino van den Bergen - 2010-01-13 08:55:58 Attachments: Message as HTML ```You may want to check this article http://web4.cs.ucl.ac.uk/staff/t.weyrich/projects/quadrics/pbg06.pdf Basically, you need to find the bounding box in clip space (after applying the perspective projection). As you can see there are no trigonometric functions involved here. Gino On 1/11/2010 1:02 PM, Diogo de Andrade wrote: > > Hi Benjamin, > > I’ve looked at your explanation, and after you put it like that, I was > all “doh!”… The problem is way simpler to solve in that form > (extending the main line (center to red) so the projected point has > the same characteristics of the purple points). After that it was > pretty simple to get right… > > Thanks a lot for the help! > > Diogo > > *From:* Benjamin Rouveyrol [mailto:pthiben77@...] > *Sent:* sexta-feira, 8 de Janeiro de 2010 16:36 > *To:* Game Development Algorithms; drizzt.du@... > *Subject:* [Algorithms] Re : Re : R: Sphere to rectangle > > Hi Diogo, > > You pretty much spotted the problem with > http://www.spellcasterstudios.com/sphere_problem.jpg > > What I wanted to do is to keep the old direction (ie center of the > sphere towards the red dots), but change the vector's magnitude so > that the point is on the line made by the camera position and the pink > dot. > So you compute first an angle (alpha = asin(R/D) ) on the triangle > made by light center, camera position and pink dot. > Then you apply Thales (tan(alpha) = x / D <=> x = D * tan(alpha) ) to > get your final point outside the circle, and which is on the pink > line. And yes, I computed the right/up vectors the same way you did > (with a normalize for Right ;-) ) > > When I look at my source code, I see that the 2D bounding rectangle > checks all the xy coordinates of all the points to get the > left/right/top/bottom. > I can't remember why I did that, but I believe this was to solve the > problem you're showing. > > Ben > > ------------------------------------------------------------------------ > > *De :* Diogo de Andrade > *À :* Game Development Algorithms > ; drizzt.du@... > *Envoyé le :* Ven 8 Janvier 2010, 10 h 51 min 22 s > *Objet :* Re: [Algorithms] Re : R: Sphere to rectangle > > Hi Benjamin, > > Your solution almost works for me… > > It works when the camera is head on to the center of the sphere: > > http://www.spellcasterstudios.com/sphere_rect_problem01.jpg > > But when I turn left or right, I get: > > http://www.spellcasterstudios.com/sphere_rect_problem02.jpg > > http://www.spellcasterstudios.com/sphere_rect_problem03.jpg > > This might be related to the projection part, I’ll look into it… > > What do you mean by: “Up and right vectors based on the camera and > light positions (and the camera Up).”? I’m just accounting for camera > orientation to calculate the up and right vectors… Are you suggesting > something like: > > View=LightPos-CameraPos > > Right=cross(CameraUp,View) > > Up=cross(View,Right) > > ? > > From the more practical standpoint, from what I understand, you’re > applying a scale factor to the radius to account for distance… How did > you came about this formula? > > You didn’t happen to need something similar for spotlights/cones? > > Thanks, > > Diogo > > *From:* Benjamin Rouveyrol [mailto:pthiben77@...] > *Sent:* sexta-feira, 8 de Janeiro de 2010 15:03 > *To:* Game Development Algorithms; drizzt.du@... > *Subject:* [Algorithms] Re : R: Sphere to rectangle > > Hi, > > The way I solved this (but a bit math heavy): > If R is the light Radius and D the distance between the camera and the > light: > NewR = D * tan(asin(R/D)) > > Then you compute Up and right vectors based on the camera and light > positions (and the camera Up). > You end up with 4 corners: LightCenter +|- Up * NewR +|- Right * NewR > > > You can project them and this should give you your bounding rectangle. > If someone has a simpler solution, I'd be most interested ^_^ > > Ben > > ------------------------------------------------------------------------ > > *De :* Diogo de Andrade > *À :* drizzt.du@...; Game Development Algorithms > > *Envoyé le :* Ven 8 Janvier 2010, 9 h 28 min 54 s > *Objet :* Re: [Algorithms] R: Sphere to rectangle > > Hi! > > That's basically what I'm trying to do with the "wrong" solution, > although I don't tell it like that... > It was a good thought... I had to think about it for 2 mins before I > understood that was exactly what I was trying to do... > > Visually, you can see the problem at > http://www.spellcasterstudios.com/sphere_problem.jpg > > With your solution (and my initial one), I'd get the red points (and > their projection, the yellow line), which is smaller than the correct > solution (the purple points/projection), which has the correct size... > > Thanks! > > Diogo > > > -----Original Message----- > From: drizzt.du@... > [mailto:drizzt.du@... ] > Sent: sexta-feira, 8 de Janeiro de 2010 13:54 > To: gdalgorithms-list@... > > Subject: [Algorithms] R: Sphere to rectangle > > ----Messaggio originale---- > Da: diogo.andrade@... > Data: 08/01/2010 13.45 > > > Hi all… > > > > I’ve been wrestling with a problem for some days now, and I > > honestly can’t seem to figure an elegant solution… > > > > I want to find the rectangle that bounds a omni light source, > > so the problem is: given a sphere with center C=(x0,y0,z0) and radius > RADIUS, what is the bounding rectangle rect=(rx1,ry1,rx2,ry2) on screen? > > Ok, I read this ML only for educational purpose, so...well, I'm sure I > will > suggest the wrong solution :-D > > Arent'you simply trying to do screen-aligned billboarding? > I mean...the bounding rectangle around a sphere of a given radius, on > screen...is not always the same rectangle simply billboarded? > > > > ------------------------------------------------------------------------------ > This SF.Net email is sponsored by the Verizon Developer Community > Take advantage of Verizon's best-in-class app development support > A streamlined, 14 day to market process makes app distribution fast > and easy > Join now and get one step closer to millions of Verizon customers > http://p.sf.net/sfu/verizon-dev2dev > _______________________________________________ > GDAlgorithms-list mailing list > GDAlgorithms-list@... > > https://lists.sourceforge.net/lists/listinfo/gdalgorithms-list > Archives: > http://sourceforge.net/mailarchive/forum.php?forum_name=gdalgorithms-list > > > ------------------------------------------------------------------------------ > This SF.Net email is sponsored by the Verizon Developer Community > Take advantage of Verizon's best-in-class app development support > A streamlined, 14 day to market process makes app distribution fast > and easy > Join now and get one step closer to millions of Verizon customers > http://p.sf.net/sfu/verizon-dev2dev > _______________________________________________ > GDAlgorithms-list mailing list > GDAlgorithms-list@... > > https://lists.sourceforge.net/lists/listinfo/gdalgorithms-list > Archives: > http://sourceforge.net/mailarchive/forum.php?forum_name=gdalgorithms-list > > > ------------------------------------------------------------------------------ > This SF.Net email is sponsored by the Verizon Developer Community > Take advantage of Verizon's best-in-class app development support > A streamlined, 14 day to market process makes app distribution fast and easy > Join now and get one step closer to millions of Verizon customers > http://p.sf.net/sfu/verizon-dev2dev > > > _______________________________________________ > GDAlgorithms-list mailing list > GDAlgorithms-list@... > https://lists.sourceforge.net/lists/listinfo/gdalgorithms-list > Archives: > http://sourceforge.net/mailarchive/forum.php?forum_name=gdalgorithms-list ```

 [Algorithms] R: Sphere to rectangle From: - 2010-01-08 13:54:26 ```----Messaggio originale---- Da: diogo.andrade@... Data: 08/01/2010 13.45 > Hi all… > > I’ve been wrestling with a problem for some days now, and I > honestly can’t seem to figure an elegant solution… > > I want to find the rectangle that bounds a omni light source, > so the problem is: given a sphere with center C=(x0,y0,z0) and radius RADIUS, what is the bounding rectangle rect=(rx1,ry1,rx2,ry2) on screen? Ok, I read this ML only for educational purpose, so...well, I'm sure I will suggest the wrong solution :-D Arent'you simply trying to do screen-aligned billboarding? I mean...the bounding rectangle around a sphere of a given radius, on screen...is not always the same rectangle simply billboarded? ```
 Re: [Algorithms] R: Sphere to rectangle From: Diogo de Andrade - 2010-01-08 14:28:17 ```Hi! That's basically what I'm trying to do with the "wrong" solution, although I don't tell it like that... It was a good thought... I had to think about it for 2 mins before I understood that was exactly what I was trying to do... Visually, you can see the problem at http://www.spellcasterstudios.com/sphere_problem.jpg With your solution (and my initial one), I'd get the red points (and their projection, the yellow line), which is smaller than the correct solution (the purple points/projection), which has the correct size... Thanks! Diogo -----Original Message----- From: drizzt.du@... [mailto:drizzt.du@...] Sent: sexta-feira, 8 de Janeiro de 2010 13:54 To: gdalgorithms-list@... Subject: [Algorithms] R: Sphere to rectangle ----Messaggio originale---- Da: diogo.andrade@... Data: 08/01/2010 13.45 > Hi all… > > I’ve been wrestling with a problem for some days now, and I > honestly can’t seem to figure an elegant solution… > > I want to find the rectangle that bounds a omni light source, > so the problem is: given a sphere with center C=(x0,y0,z0) and radius RADIUS, what is the bounding rectangle rect=(rx1,ry1,rx2,ry2) on screen? Ok, I read this ML only for educational purpose, so...well, I'm sure I will suggest the wrong solution :-D Arent'you simply trying to do screen-aligned billboarding? I mean...the bounding rectangle around a sphere of a given radius, on screen...is not always the same rectangle simply billboarded? ------------------------------------------------------------------------------ This SF.Net email is sponsored by the Verizon Developer Community Take advantage of Verizon's best-in-class app development support A streamlined, 14 day to market process makes app distribution fast and easy Join now and get one step closer to millions of Verizon customers http://p.sf.net/sfu/verizon-dev2dev _______________________________________________ GDAlgorithms-list mailing list GDAlgorithms-list@... https://lists.sourceforge.net/lists/listinfo/gdalgorithms-list Archives: http://sourceforge.net/mailarchive/forum.php?forum_name=gdalgorithms-list ```
 [Algorithms] Re : R: Sphere to rectangle From: Benjamin Rouveyrol - 2010-01-08 15:29:36 Attachments: Message as HTML ```Hi, The way I solved this (but a bit math heavy): If R is the light Radius and D the distance between the camera and the light: NewR = D * tan(asin(R/D)) Then you compute Up and right vectors based on the camera and light positions (and the camera Up). You end up with 4 corners: LightCenter +|- Up * NewR +|- Right * NewR You can project them and this should give you your bounding rectangle. If someone has a simpler solution, I'd be most interested ^_^ Ben ________________________________ De : Diogo de Andrade À : drizzt.du@...; Game Development Algorithms Envoyé le : Ven 8 Janvier 2010, 9 h 28 min 54 s Objet : Re: [Algorithms] R: Sphere to rectangle Hi! That's basically what I'm trying to do with the "wrong" solution, although I don't tell it like that... It was a good thought... I had to think about it for 2 mins before I understood that was exactly what I was trying to do... Visually, you can see the problem at http://www.spellcasterstudios.com/sphere_problem.jpg With your solution (and my initial one), I'd get the red points (and their projection, the yellow line), which is smaller than the correct solution (the purple points/projection), which has the correct size... Thanks! Diogo -----Original Message----- From: drizzt.du@... [mailto:drizzt.du@...] Sent: sexta-feira, 8 de Janeiro de 2010 13:54 To: gdalgorithms-list@... Subject: [Algorithms] R: Sphere to rectangle ----Messaggio originale---- Da: diogo.andrade@... Data: 08/01/2010 13.45 > Hi all… > > I’ve been wrestling with a problem for some days now, and I > honestly can’t seem to figure an elegant solution… > > I want to find the rectangle that bounds a omni light source, > so the problem is: given a sphere with center C=(x0,y0,z0) and radius RADIUS, what is the bounding rectangle rect=(rx1,ry1,rx2,ry2) on screen? Ok, I read this ML only for educational purpose, so...well, I'm sure I will suggest the wrong solution :-D Arent'you simply trying to do screen-aligned billboarding? I mean...the bounding rectangle around a sphere of a given radius, on screen...is not always the same rectangle simply billboarded? ------------------------------------------------------------------------------ This SF.Net email is sponsored by the Verizon Developer Community Take advantage of Verizon's best-in-class app development support A streamlined, 14 day to market process makes app distribution fast and easy Join now and get one step closer to millions of Verizon customers http://p.sf.net/sfu/verizon-dev2dev _______________________________________________ GDAlgorithms-list mailing list GDAlgorithms-list@... https://lists.sourceforge.net/lists/listinfo/gdalgorithms-list Archives: http://sourceforge.net/mailarchive/forum.php?forum_name=gdalgorithms-list ------------------------------------------------------------------------------ This SF.Net email is sponsored by the Verizon Developer Community Take advantage of Verizon's best-in-class app development support A streamlined, 14 day to market process makes app distribution fast and easy Join now and get one step closer to millions of Verizon customers http://p.sf.net/sfu/verizon-dev2dev _______________________________________________ GDAlgorithms-list mailing list GDAlgorithms-list@... https://lists.sourceforge.net/lists/listinfo/gdalgorithms-list Archives: http://sourceforge.net/mailarchive/forum.php?forum_name=gdalgorithms-list ```
 Re: [Algorithms] Re : R: Sphere to rectangle From: Diogo de Andrade - 2010-01-08 15:50:46 Attachments: Message as HTML ```Hi Benjamin, Your solution almost works for me… It works when the camera is head on to the center of the sphere: ; http://www.spellcasterstudios.com/sphere_rect_problem01.jpg But when I turn left or right, I get: ; http://www.spellcasterstudios.com/sphere_rect_problem02.jpg ; http://www.spellcasterstudios.com/sphere_rect_problem03.jpg This might be related to the projection part, I’ll look into it… What do you mean by: “Up and right vectors based on the camera and light positions (and the camera Up).”? I’m just accounting for camera orientation to calculate the up and right vectors… Are you suggesting something like: View=LightPos-CameraPos Right=cross(CameraUp,View) Up=cross(View,Right) ? >From the more practical standpoint, from what I understand, you’re applying a scale factor to the radius to account for distance… How did you came about this formula? You didn’t happen to need something similar for spotlights/cones? Thanks, Diogo From: Benjamin Rouveyrol [mailto:pthiben77@...] Sent: sexta-feira, 8 de Janeiro de 2010 15:03 To: Game Development Algorithms; drizzt.du@... Subject: [Algorithms] Re : R: Sphere to rectangle Hi, The way I solved this (but a bit math heavy): If R is the light Radius and D the distance between the camera and the light: NewR = D * tan(asin(R/D)) Then you compute Up and right vectors based on the camera and light positions (and the camera Up). You end up with 4 corners: LightCenter +|- Up * NewR +|- Right * NewR You can project them and this should give you your bounding rectangle. If someone has a simpler solution, I'd be most interested ^_^ Ben _____ De : Diogo de Andrade À : drizzt.du@...; Game Development Algorithms Envoyé le : Ven 8 Janvier 2010, 9 h 28 min 54 s Objet : Re: [Algorithms] R: Sphere to rectangle Hi! That's basically what I'm trying to do with the "wrong" solution, although I don't tell it like that... It was a good thought... I had to think about it for 2 mins before I understood that was exactly what I was trying to do... Visually, you can see the problem at http://www.spellcasterstudios.com/sphere_problem.jpg With your solution (and my initial one), I'd get the red points (and their projection, the yellow line), which is smaller than the correct solution (the purple points/projection), which has the correct size... Thanks! Diogo -----Original Message----- From: drizzt.du@... [mailto:drizzt.du@...] Sent: sexta-feira, 8 de Janeiro de 2010 13:54 To: gdalgorithms-list@... Subject: [Algorithms] R: Sphere to rectangle ----Messaggio originale---- Da: diogo.andrade@... Data: 08/01/2010 13.45 > Hi all… > > I’ve been wrestling with a problem for some days now, and I > honestly can’t seem to figure an elegant solution… > > I want to find the rectangle that bounds a omni light source, > so the problem is: given a sphere with center C=(x0,y0,z0) and radius RADIUS, what is the bounding rectangle rect=(rx1,ry1,rx2,ry2) on screen? Ok, I read this ML only for educational purpose, so...well, I'm sure I will suggest the wrong solution :-D Arent'you simply trying to do screen-aligned billboarding? I mean...the bounding rectangle around a sphere of a given radius, on screen...is not always the same rectangle simply billboarded? ------------------------------------------------------------------------------ This SF.Net email is sponsored by the Verizon Developer Community Take advantage of Verizon's best-in-class app development support A streamlined, 14 day to market process makes app distribution fast and easy Join now and get one step closer to millions of Verizon customers http://p.sf.net/sfu/verizon-dev2dev _______________________________________________ GDAlgorithms-list mailing list GDAlgorithms-list@... https://lists.sourceforge.net/lists/listinfo/gdalgorithms-list Archives: http://sourceforge.net/mailarchive/forum.php?forum_name=gdalgorithms-list ------------------------------------------------------------------------------ This SF.Net email is sponsored by the Verizon Developer Community Take advantage of Verizon's best-in-class app development support A streamlined, 14 day to market process makes app distribution fast and easy Join now and get one step closer to millions of Verizon customers http://p.sf.net/sfu/verizon-dev2dev _______________________________________________ GDAlgorithms-list mailing list GDAlgorithms-list@... https://lists.sourceforge.net/lists/listinfo/gdalgorithms-list Archives: http://sourceforge.net/mailarchive/forum.php?forum_name=gdalgorithms-list ```
 [Algorithms] Re : Re : R: Sphere to rectangle From: Benjamin Rouveyrol - 2010-01-08 16:36:08 Attachments: Message as HTML ```Hi Diogo, You pretty much spotted the problem with http://www.spellcasterstudios.com/sphere_problem.jpg What I wanted to do is to keep the old direction (ie center of the sphere towards the red dots), but change the vector's magnitude so that the point is on the line made by the camera position and the pink dot. So you compute first an angle (alpha = asin(R/D) ) on the triangle made by light center, camera position and pink dot. Then you apply Thales (tan(alpha) = x / D <=> x = D * tan(alpha) ) to get your final point outside the circle, and which is on the pink line. And yes, I computed the right/up vectors the same way you did (with a normalize for Right ;-) ) When I look at my source code, I see that the 2D bounding rectangle checks all the xy coordinates of all the points to get the left/right/top/bottom. I can't remember why I did that, but I believe this was to solve the problem you're showing. Ben ________________________________ De : Diogo de Andrade À : Game Development Algorithms ; drizzt.du@... Envoyé le : Ven 8 Janvier 2010, 10 h 51 min 22 s Objet : Re: [Algorithms] Re : R: Sphere to rectangle Hi Benjamin, Your solution almost works for me… It works when the camera is head on to the center of the sphere: http://www.spellcasterstudios.com/sphere_rect_problem01.jpg But when I turn left or right, I get: http://www.spellcasterstudios.com/sphere_rect_problem02.jpg http://www.spellcasterstudios.com/sphere_rect_problem03.jpg This might be related to the projection part, I’ll look into it… What do you mean by: “Up and right vectors based on the camera and light positions (and the camera Up).”? I’m just accounting for camera orientation to calculate the up and right vectors… Are you suggesting something like: View=LightPos-CameraPos Right=cross(CameraUp,View) Up=cross(View,Right) ? From the more practical standpoint, from what I understand, you’re applying a scale factor to the radius to account for distance… How did you came about this formula? You didn’t happen to need something similar for spotlights/cones? Thanks, Diogo From:Benjamin Rouveyrol [mailto:pthiben77@...] Sent: sexta-feira, 8 de Janeiro de 2010 15:03 To: Game Development Algorithms; drizzt.du@... Subject: [Algorithms] Re : R: Sphere to rectangle Hi, The way I solved this (but a bit math heavy): If R is the light Radius and D the distance between the camera and the light: NewR = D * tan(asin(R/D)) Then you compute Up and right vectors based on the camera and light positions (and the camera Up). You end up with 4 corners: LightCenter +|- Up * NewR +|- Right * NewR You can project them and this should give you your bounding rectangle. If someone has a simpler solution, I'd be most interested ^_^ Ben ________________________________ De :Diogo de Andrade À : drizzt.du@...; Game Development Algorithms Envoyé le : Ven 8 Janvier 2010, 9 h 28 min 54 s Objet : Re: [Algorithms] R: Sphere to rectangle Hi! That's basically what I'm trying to do with the "wrong" solution, although I don't tell it like that... It was a good thought... I had to think about it for 2 mins before I understood that was exactly what I was trying to do... Visually, you can see the problem at http://www.spellcasterstudios.com/sphere_problem.jpg With your solution (and my initial one), I'd get the red points (and their projection, the yellow line), which is smaller than the correct solution (the purple points/projection), which has the correct size... Thanks! Diogo -----Original Message----- From: drizzt.du@... [mailto:drizzt.du@...] Sent: sexta-feira, 8 de Janeiro de 2010 13:54 To: gdalgorithms-list@... Subject: [Algorithms] R: Sphere to rectangle ----Messaggio originale---- Da: diogo.andrade@... Data: 08/01/2010 13.45 > Hi all… > > I’ve been wrestling with a problem for some days now, and I > honestly can’t seem to figure an elegant solution… > > I want to find the rectangle that bounds a omni light source, > so the problem is: given a sphere with center C=(x0,y0,z0) and radius RADIUS, what is the bounding rectangle rect=(rx1,ry1,rx2,ry2) on screen? Ok, I read this ML only for educational purpose, so...well, I'm sure I will suggest the wrong solution :-D Arent'you simply trying to do screen-aligned billboarding? I mean...the bounding rectangle around a sphere of a given radius, on screen...is not always the same rectangle simply billboarded? ------------------------------------------------------------------------------ This SF.Net email is sponsored by the Verizon Developer Community Take advantage of Verizon's best-in-class app development support A streamlined, 14 day to market process makes app distribution fast and easy Join now and get one step closer to millions of Verizon customers http://p.sf.net/sfu/verizon-dev2dev _______________________________________________ GDAlgorithms-list mailing list GDAlgorithms-list@... https://lists.sourceforge.net/lists/listinfo/gdalgorithms-list Archives: http://sourceforge.net/mailarchive/forum.php?forum_name=gdalgorithms-list ------------------------------------------------------------------------------ This SF.Net email is sponsored by the Verizon Developer Community Take advantage of Verizon's best-in-class app development support A streamlined, 14 day to market process makes app distribution fast and easy Join now and get one step closer to millions of Verizon customers http://p.sf.net/sfu/verizon-dev2dev _______________________________________________ GDAlgorithms-list mailing list GDAlgorithms-list@... https://lists.sourceforge.net/lists/listinfo/gdalgorithms-list Archives: http://sourceforge.net/mailarchive/forum.php?forum_name=gdalgorithms-list ```
 Re: [Algorithms] Re : Re : R: Sphere to rectangle From: Diogo de Andrade - 2010-01-11 12:02:41 Attachments: Message as HTML ```Hi Benjamin, I’ve looked at your explanation, and after you put it like that, I was all “doh!”… The problem is way simpler to solve in that form (extending the main line (center to red) so the projected point has the same characteristics of the purple points). After that it was pretty simple to get right… Thanks a lot for the help! Diogo From: Benjamin Rouveyrol [mailto:pthiben77@...] Sent: sexta-feira, 8 de Janeiro de 2010 16:36 To: Game Development Algorithms; drizzt.du@... Subject: [Algorithms] Re : Re : R: Sphere to rectangle Hi Diogo, You pretty much spotted the problem with http://www.spellcasterstudios.com/sphere_problem.jpg What I wanted to do is to keep the old direction (ie center of the sphere towards the red dots), but change the vector's magnitude so that the point is on the line made by the camera position and the pink dot. So you compute first an angle (alpha = asin(R/D) ) on the triangle made by light center, camera position and pink dot. Then you apply Thales (tan(alpha) = x / D <=> x = D * tan(alpha) ) to get your final point outside the circle, and which is on the pink line. And yes, I computed the right/up vectors the same way you did (with a normalize for Right ;-) ) When I look at my source code, I see that the 2D bounding rectangle checks all the xy coordinates of all the points to get the left/right/top/bottom. I can't remember why I did that, but I believe this was to solve the problem you're showing. Ben _____ De : Diogo de Andrade À : Game Development Algorithms ; drizzt.du@... Envoyé le : Ven 8 Janvier 2010, 10 h 51 min 22 s Objet : Re: [Algorithms] Re : R: Sphere to rectangle Hi Benjamin, Your solution almost works for me… It works when the camera is head on to the center of the sphere: ; http://www.spellcasterstudios.com/sphere_rect_problem01.jpg But when I turn left or right, I get: ; http://www.spellcasterstudios.com/sphere_rect_problem02.jpg ; http://www.spellcasterstudios.com/sphere_rect_problem03.jpg This might be related to the projection part, I’ll look into it… What do you mean by: “Up and right vectors based on the camera and light positions (and the camera Up).”? I’m just accounting for camera orientation to calculate the up and right vectors… Are you suggesting something like: View=LightPos-CameraPos Right=cross(CameraUp,View) Up=cross(View,Right) ? >From the more practical standpoint, from what I understand, you’re applying a scale factor to the radius to account for distance… How did you came about this formula? You didn’t happen to need something similar for spotlights/cones? Thanks, Diogo From: Benjamin Rouveyrol [mailto:pthiben77@...] Sent: sexta-feira, 8 de Janeiro de 2010 15:03 To: Game Development Algorithms; drizzt.du@... Subject: [Algorithms] Re : R: Sphere to rectangle Hi, The way I solved this (but a bit math heavy): If R is the light Radius and D the distance between the camera and the light: NewR = D * tan(asin(R/D)) Then you compute Up and right vectors based on the camera and light positions (and the camera Up). You end up with 4 corners: LightCenter +|- Up * NewR +|- Right * NewR You can project them and this should give you your bounding rectangle. If someone has a simpler solution, I'd be most interested ^_^ Ben _____ De : Diogo de Andrade À : drizzt.du@...; Game Development Algorithms Envoyé le : Ven 8 Janvier 2010, 9 h 28 min 54 s Objet : Re: [Algorithms] R: Sphere to rectangle Hi! That's basically what I'm trying to do with the "wrong" solution, although I don't tell it like that... It was a good thought... I had to think about it for 2 mins before I understood that was exactly what I was trying to do... Visually, you can see the problem at http://www.spellcasterstudios.com/sphere_problem.jpg With your solution (and my initial one), I'd get the red points (and their projection, the yellow line), which is smaller than the correct solution (the purple points/projection), which has the correct size... Thanks! Diogo -----Original Message----- From: drizzt.du@... [mailto:drizzt.du@...] Sent: sexta-feira, 8 de Janeiro de 2010 13:54 To: gdalgorithms-list@... Subject: [Algorithms] R: Sphere to rectangle ----Messaggio originale---- Da: diogo.andrade@... Data: 08/01/2010 13.45 > Hi all… > > I’ve been wrestling with a problem for some days now, and I > honestly can’t seem to figure an elegant solution… > > I want to find the rectangle that bounds a omni light source, > so the problem is: given a sphere with center C=(x0,y0,z0) and radius RADIUS, what is the bounding rectangle rect=(rx1,ry1,rx2,ry2) on screen? Ok, I read this ML only for educational purpose, so...well, I'm sure I will suggest the wrong solution :-D Arent'you simply trying to do screen-aligned billboarding? I mean...the bounding rectangle around a sphere of a given radius, on screen...is not always the same rectangle simply billboarded? ------------------------------------------------------------------------------ This SF.Net email is sponsored by the Verizon Developer Community Take advantage of Verizon's best-in-class app development support A streamlined, 14 day to market process makes app distribution fast and easy Join now and get one step closer to millions of Verizon customers http://p.sf.net/sfu/verizon-dev2dev _______________________________________________ GDAlgorithms-list mailing list GDAlgorithms-list@... https://lists.sourceforge.net/lists/listinfo/gdalgorithms-list Archives: http://sourceforge.net/mailarchive/forum.php?forum_name=gdalgorithms-list ------------------------------------------------------------------------------ This SF.Net email is sponsored by the Verizon Developer Community Take advantage of Verizon's best-in-class app development support A streamlined, 14 day to market process makes app distribution fast and easy Join now and get one step closer to millions of Verizon customers http://p.sf.net/sfu/verizon-dev2dev _______________________________________________ GDAlgorithms-list mailing list GDAlgorithms-list@... https://lists.sourceforge.net/lists/listinfo/gdalgorithms-list Archives: http://sourceforge.net/mailarchive/forum.php?forum_name=gdalgorithms-list ```
 Re: [Algorithms] Re : Re : R: Sphere to rectangle From: Diogo de Andrade - 2010-01-11 12:43:24 Attachments: Message as HTML ```Hey everyone… I’ve done a simple algorithm to get the cone area (for spot lights)… It’s basically the same as the omni light, but I find the bounding rectangle of a sphere S=(C,R), where C=LightPos+LightDir*range and R=range*tan(light_fov). After I do that, I calculate the projection of the position of light source, and do a min/max test to build the final bounding rectangle. I’m sure there’s probably a much better way to do this, but this one actually works pretty well, considering how simple it is… Again, thanks all for the help! Diogo From: Diogo de Andrade [mailto:diogo.andrade@...] Sent: segunda-feira, 11 de Janeiro de 2010 12:03 To: 'Game Development Algorithms' Subject: Re: [Algorithms] Re : Re : R: Sphere to rectangle Hi Benjamin, I’ve looked at your explanation, and after you put it like that, I was all “doh!”… The problem is way simpler to solve in that form (extending the main line (center to red) so the projected point has the same characteristics of the purple points). After that it was pretty simple to get right… Thanks a lot for the help! Diogo From: Benjamin Rouveyrol [mailto:pthiben77@...] Sent: sexta-feira, 8 de Janeiro de 2010 16:36 To: Game Development Algorithms; drizzt.du@... Subject: [Algorithms] Re : Re : R: Sphere to rectangle Hi Diogo, You pretty much spotted the problem with http://www.spellcasterstudios.com/sphere_problem.jpg What I wanted to do is to keep the old direction (ie center of the sphere towards the red dots), but change the vector's magnitude so that the point is on the line made by the camera position and the pink dot. So you compute first an angle (alpha = asin(R/D) ) on the triangle made by light center, camera position and pink dot. Then you apply Thales (tan(alpha) = x / D <=> x = D * tan(alpha) ) to get your final point outside the circle, and which is on the pink line. And yes, I computed the right/up vectors the same way you did (with a normalize for Right ;-) ) When I look at my source code, I see that the 2D bounding rectangle checks all the xy coordinates of all the points to get the left/right/top/bottom. I can't remember why I did that, but I believe this was to solve the problem you're showing. Ben _____ De : Diogo de Andrade À : Game Development Algorithms ; drizzt.du@... Envoyé le : Ven 8 Janvier 2010, 10 h 51 min 22 s Objet : Re: [Algorithms] Re : R: Sphere to rectangle Hi Benjamin, Your solution almost works for me… It works when the camera is head on to the center of the sphere: ; http://www.spellcasterstudios.com/sphere_rect_problem01.jpg But when I turn left or right, I get: ; http://www.spellcasterstudios.com/sphere_rect_problem02.jpg ; http://www.spellcasterstudios.com/sphere_rect_problem03.jpg This might be related to the projection part, I’ll look into it… What do you mean by: “Up and right vectors based on the camera and light positions (and the camera Up).”? I’m just accounting for camera orientation to calculate the up and right vectors… Are you suggesting something like: View=LightPos-CameraPos Right=cross(CameraUp,View) Up=cross(View,Right) ? >From the more practical standpoint, from what I understand, you’re applying a scale factor to the radius to account for distance… How did you came about this formula? You didn’t happen to need something similar for spotlights/cones? Thanks, Diogo From: Benjamin Rouveyrol [mailto:pthiben77@...] Sent: sexta-feira, 8 de Janeiro de 2010 15:03 To: Game Development Algorithms; drizzt.du@... Subject: [Algorithms] Re : R: Sphere to rectangle Hi, The way I solved this (but a bit math heavy): If R is the light Radius and D the distance between the camera and the light: NewR = D * tan(asin(R/D)) Then you compute Up and right vectors based on the camera and light positions (and the camera Up). You end up with 4 corners: LightCenter +|- Up * NewR +|- Right * NewR You can project them and this should give you your bounding rectangle. If someone has a simpler solution, I'd be most interested ^_^ Ben _____ De : Diogo de Andrade À : drizzt.du@...; Game Development Algorithms Envoyé le : Ven 8 Janvier 2010, 9 h 28 min 54 s Objet : Re: [Algorithms] R: Sphere to rectangle Hi! That's basically what I'm trying to do with the "wrong" solution, although I don't tell it like that... It was a good thought... I had to think about it for 2 mins before I understood that was exactly what I was trying to do... Visually, you can see the problem at http://www.spellcasterstudios.com/sphere_problem.jpg With your solution (and my initial one), I'd get the red points (and their projection, the yellow line), which is smaller than the correct solution (the purple points/projection), which has the correct size... Thanks! Diogo -----Original Message----- From: drizzt.du@... [mailto:drizzt.du@...] Sent: sexta-feira, 8 de Janeiro de 2010 13:54 To: gdalgorithms-list@... Subject: [Algorithms] R: Sphere to rectangle ----Messaggio originale---- Da: diogo.andrade@... Data: 08/01/2010 13.45 > Hi all… > > I’ve been wrestling with a problem for some days now, and I > honestly can’t seem to figure an elegant solution… > > I want to find the rectangle that bounds a omni light source, > so the problem is: given a sphere with center C=(x0,y0,z0) and radius RADIUS, what is the bounding rectangle rect=(rx1,ry1,rx2,ry2) on screen? Ok, I read this ML only for educational purpose, so...well, I'm sure I will suggest the wrong solution :-D Arent'you simply trying to do screen-aligned billboarding? I mean...the bounding rectangle around a sphere of a given radius, on screen...is not always the same rectangle simply billboarded? ------------------------------------------------------------------------------ This SF.Net email is sponsored by the Verizon Developer Community Take advantage of Verizon's best-in-class app development support A streamlined, 14 day to market process makes app distribution fast and easy Join now and get one step closer to millions of Verizon customers http://p.sf.net/sfu/verizon-dev2dev _______________________________________________ GDAlgorithms-list mailing list GDAlgorithms-list@... https://lists.sourceforge.net/lists/listinfo/gdalgorithms-list Archives: http://sourceforge.net/mailarchive/forum.php?forum_name=gdalgorithms-list ------------------------------------------------------------------------------ This SF.Net email is sponsored by the Verizon Developer Community Take advantage of Verizon's best-in-class app development support A streamlined, 14 day to market process makes app distribution fast and easy Join now and get one step closer to millions of Verizon customers http://p.sf.net/sfu/verizon-dev2dev _______________________________________________ GDAlgorithms-list mailing list GDAlgorithms-list@... https://lists.sourceforge.net/lists/listinfo/gdalgorithms-list Archives: http://sourceforge.net/mailarchive/forum.php?forum_name=gdalgorithms-list ```
 Re: [Algorithms] Re : Re : R: Sphere to rectangle From: Gino van den Bergen - 2010-01-13 08:55:58 Attachments: Message as HTML ```You may want to check this article http://web4.cs.ucl.ac.uk/staff/t.weyrich/projects/quadrics/pbg06.pdf Basically, you need to find the bounding box in clip space (after applying the perspective projection). As you can see there are no trigonometric functions involved here. Gino On 1/11/2010 1:02 PM, Diogo de Andrade wrote: > > Hi Benjamin, > > I’ve looked at your explanation, and after you put it like that, I was > all “doh!”… The problem is way simpler to solve in that form > (extending the main line (center to red) so the projected point has > the same characteristics of the purple points). After that it was > pretty simple to get right… > > Thanks a lot for the help! > > Diogo > > *From:* Benjamin Rouveyrol [mailto:pthiben77@...] > *Sent:* sexta-feira, 8 de Janeiro de 2010 16:36 > *To:* Game Development Algorithms; drizzt.du@... > *Subject:* [Algorithms] Re : Re : R: Sphere to rectangle > > Hi Diogo, > > You pretty much spotted the problem with > http://www.spellcasterstudios.com/sphere_problem.jpg > > What I wanted to do is to keep the old direction (ie center of the > sphere towards the red dots), but change the vector's magnitude so > that the point is on the line made by the camera position and the pink > dot. > So you compute first an angle (alpha = asin(R/D) ) on the triangle > made by light center, camera position and pink dot. > Then you apply Thales (tan(alpha) = x / D <=> x = D * tan(alpha) ) to > get your final point outside the circle, and which is on the pink > line. And yes, I computed the right/up vectors the same way you did > (with a normalize for Right ;-) ) > > When I look at my source code, I see that the 2D bounding rectangle > checks all the xy coordinates of all the points to get the > left/right/top/bottom. > I can't remember why I did that, but I believe this was to solve the > problem you're showing. > > Ben > > ------------------------------------------------------------------------ > > *De :* Diogo de Andrade > *À :* Game Development Algorithms > ; drizzt.du@... > *Envoyé le :* Ven 8 Janvier 2010, 10 h 51 min 22 s > *Objet :* Re: [Algorithms] Re : R: Sphere to rectangle > > Hi Benjamin, > > Your solution almost works for me… > > It works when the camera is head on to the center of the sphere: > > http://www.spellcasterstudios.com/sphere_rect_problem01.jpg > > But when I turn left or right, I get: > > http://www.spellcasterstudios.com/sphere_rect_problem02.jpg > > http://www.spellcasterstudios.com/sphere_rect_problem03.jpg > > This might be related to the projection part, I’ll look into it… > > What do you mean by: “Up and right vectors based on the camera and > light positions (and the camera Up).”? I’m just accounting for camera > orientation to calculate the up and right vectors… Are you suggesting > something like: > > View=LightPos-CameraPos > > Right=cross(CameraUp,View) > > Up=cross(View,Right) > > ? > > From the more practical standpoint, from what I understand, you’re > applying a scale factor to the radius to account for distance… How did > you came about this formula? > > You didn’t happen to need something similar for spotlights/cones? > > Thanks, > > Diogo > > *From:* Benjamin Rouveyrol [mailto:pthiben77@...] > *Sent:* sexta-feira, 8 de Janeiro de 2010 15:03 > *To:* Game Development Algorithms; drizzt.du@... > *Subject:* [Algorithms] Re : R: Sphere to rectangle > > Hi, > > The way I solved this (but a bit math heavy): > If R is the light Radius and D the distance between the camera and the > light: > NewR = D * tan(asin(R/D)) > > Then you compute Up and right vectors based on the camera and light > positions (and the camera Up). > You end up with 4 corners: LightCenter +|- Up * NewR +|- Right * NewR > > > You can project them and this should give you your bounding rectangle. > If someone has a simpler solution, I'd be most interested ^_^ > > Ben > > ------------------------------------------------------------------------ > > *De :* Diogo de Andrade > *À :* drizzt.du@...; Game Development Algorithms > > *Envoyé le :* Ven 8 Janvier 2010, 9 h 28 min 54 s > *Objet :* Re: [Algorithms] R: Sphere to rectangle > > Hi! > > That's basically what I'm trying to do with the "wrong" solution, > although I don't tell it like that... > It was a good thought... I had to think about it for 2 mins before I > understood that was exactly what I was trying to do... > > Visually, you can see the problem at > http://www.spellcasterstudios.com/sphere_problem.jpg > > With your solution (and my initial one), I'd get the red points (and > their projection, the yellow line), which is smaller than the correct > solution (the purple points/projection), which has the correct size... > > Thanks! > > Diogo > > > -----Original Message----- > From: drizzt.du@... > [mailto:drizzt.du@... ] > Sent: sexta-feira, 8 de Janeiro de 2010 13:54 > To: gdalgorithms-list@... > > Subject: [Algorithms] R: Sphere to rectangle > > ----Messaggio originale---- > Da: diogo.andrade@... > Data: 08/01/2010 13.45 > > > Hi all… > > > > I’ve been wrestling with a problem for some days now, and I > > honestly can’t seem to figure an elegant solution… > > > > I want to find the rectangle that bounds a omni light source, > > so the problem is: given a sphere with center C=(x0,y0,z0) and radius > RADIUS, what is the bounding rectangle rect=(rx1,ry1,rx2,ry2) on screen? > > Ok, I read this ML only for educational purpose, so...well, I'm sure I > will > suggest the wrong solution :-D > > Arent'you simply trying to do screen-aligned billboarding? > I mean...the bounding rectangle around a sphere of a given radius, on > screen...is not always the same rectangle simply billboarded? > > > > ------------------------------------------------------------------------------ > This SF.Net email is sponsored by the Verizon Developer Community > Take advantage of Verizon's best-in-class app development support > A streamlined, 14 day to market process makes app distribution fast > and easy > Join now and get one step closer to millions of Verizon customers > http://p.sf.net/sfu/verizon-dev2dev > _______________________________________________ > GDAlgorithms-list mailing list > GDAlgorithms-list@... > > https://lists.sourceforge.net/lists/listinfo/gdalgorithms-list > Archives: > http://sourceforge.net/mailarchive/forum.php?forum_name=gdalgorithms-list > > > ------------------------------------------------------------------------------ > This SF.Net email is sponsored by the Verizon Developer Community > Take advantage of Verizon's best-in-class app development support > A streamlined, 14 day to market process makes app distribution fast > and easy > Join now and get one step closer to millions of Verizon customers > http://p.sf.net/sfu/verizon-dev2dev > _______________________________________________ > GDAlgorithms-list mailing list > GDAlgorithms-list@... > > https://lists.sourceforge.net/lists/listinfo/gdalgorithms-list > Archives: > http://sourceforge.net/mailarchive/forum.php?forum_name=gdalgorithms-list > > > ------------------------------------------------------------------------------ > This SF.Net email is sponsored by the Verizon Developer Community > Take advantage of Verizon's best-in-class app development support > A streamlined, 14 day to market process makes app distribution fast and easy > Join now and get one step closer to millions of Verizon customers > http://p.sf.net/sfu/verizon-dev2dev > > > _______________________________________________ > GDAlgorithms-list mailing list > GDAlgorithms-list@... > https://lists.sourceforge.net/lists/listinfo/gdalgorithms-list > Archives: > http://sourceforge.net/mailarchive/forum.php?forum_name=gdalgorithms-list ```
 Re: [Algorithms] Sphere to rectangle From: Fabian Giesen - 2010-01-08 16:09:42 ```Benjamin Rouveyrol wrote: > Hi, > > The way I solved this (but a bit math heavy): > If R is the light Radius and D the distance between the camera and the > light: > NewR = D * tan(asin(R/D)) > > Then you compute Up and right vectors based on the camera and light > positions (and the camera Up). > You end up with 4 corners: LightCenter +|- Up * NewR +|- Right * NewR > > > You can project them and this should give you your bounding rectangle. > If someone has a simpler solution, I'd be most interested ^_^ Eric Lengyel explains one way to solve this on the last page of his "The Mechanics of Robust Stencil Shadows" article: http://www.gamasutra.com/view/feature/2942/the_mechanics_of_robust_stencil_.php?page=6 I derived an alternative method for some hobby project around 2004 that is somewhat more straightforward. I don't have the original derivation anymore, but I remember that it was fairly straightforward trig: // Calculates bounding rectangle in normalized device coordinates for // the view-space sphere with center "center" and radius "r". "zoom" // contains the first two diagonal entries of your projection matrix // (which is assumed to be perspective). You should do a rough rejection // test of the sphere against the frustum first. static void CalcSphereBounds(const Vector& center, float r, const float zoom[2], float minb[2], float maxb[2]) { // by default, assume that full screen covered minb[0] = minb[1] = -1.0f; maxb[0] = maxb[1] = 1.0f; // once for x, once for y for(int i=0;i<2;i++) { float x = center[i]; float z = center.z; float ds = x*x + z*z; float l = ds - r * r; if(l > 0.0f) { float s,c; l = sqrt(l); s = x * l - z * r; // ds*sin(alpha) c = x * r + z * l; // ds*cos(alpha) if(z*ds > -r*s) // left/top intersection has positive z minb[i] = max(-1.0f, s*zoom[i]/c); s = z * r + x * l; // ds*sin(beta) c = z * l - x * r; // ds*cos(beta) if(z*ds > r*s) // right/bottom intersection has positive z maxb[i] = min(1.0f, s*zoom[i]/c); } } } I'll try to re-derive this so as not to leave a bunch of unexplained formulas standing in the room, but it's a relatively short solution and it's worked fine for me, so I guess it's of interest. Kind regards, -Fabian ```
 Re: [Algorithms] Sphere to rectangle From: Diogo de Andrade - 2010-01-08 16:50:18 ```Hi Fabian, I've just plugged in your code into mine and it works like a charm! I've looked into Eric Lengyel's explanation, but I've been unable to make it work properly (probably did the same mistake in implementing the equations I did on my own derivation, since the result was exactly the same)... Looking forward to see your derivation, although I think I understood the gist of it... By any chance you don't have something similar for a cone for spotlights? :) Thanks a million! Diogo -----Original Message----- From: Fabian Giesen [mailto:f.giesen@...] Sent: sexta-feira, 8 de Janeiro de 2010 15:57 To: Game Development Algorithms Subject: Re: [Algorithms] Sphere to rectangle Benjamin Rouveyrol wrote: > Hi, > > The way I solved this (but a bit math heavy): > If R is the light Radius and D the distance between the camera and the > light: > NewR = D * tan(asin(R/D)) > > Then you compute Up and right vectors based on the camera and light > positions (and the camera Up). > You end up with 4 corners: LightCenter +|- Up * NewR +|- Right * NewR > > > You can project them and this should give you your bounding rectangle. > If someone has a simpler solution, I'd be most interested ^_^ Eric Lengyel explains one way to solve this on the last page of his "The Mechanics of Robust Stencil Shadows" article: http://www.gamasutra.com/view/feature/2942/the_mechanics_of_robust_stencil_. php?page=6 I derived an alternative method for some hobby project around 2004 that is somewhat more straightforward. I don't have the original derivation anymore, but I remember that it was fairly straightforward trig: // Calculates bounding rectangle in normalized device coordinates for // the view-space sphere with center "center" and radius "r". "zoom" // contains the first two diagonal entries of your projection matrix // (which is assumed to be perspective). You should do a rough rejection // test of the sphere against the frustum first. static void CalcSphereBounds(const Vector& center, float r, const float zoom[2], float minb[2], float maxb[2]) { // by default, assume that full screen covered minb[0] = minb[1] = -1.0f; maxb[0] = maxb[1] = 1.0f; // once for x, once for y for(int i=0;i<2;i++) { float x = center[i]; float z = center.z; float ds = x*x + z*z; float l = ds - r * r; if(l > 0.0f) { float s,c; l = sqrt(l); s = x * l - z * r; // ds*sin(alpha) c = x * r + z * l; // ds*cos(alpha) if(z*ds > -r*s) // left/top intersection has positive z minb[i] = max(-1.0f, s*zoom[i]/c); s = z * r + x * l; // ds*sin(beta) c = z * l - x * r; // ds*cos(beta) if(z*ds > r*s) // right/bottom intersection has positive z maxb[i] = min(1.0f, s*zoom[i]/c); } } } I'll try to re-derive this so as not to leave a bunch of unexplained formulas standing in the room, but it's a relatively short solution and it's worked fine for me, so I guess it's of interest. Kind regards, -Fabian ---------------------------------------------------------------------------- -- This SF.Net email is sponsored by the Verizon Developer Community Take advantage of Verizon's best-in-class app development support A streamlined, 14 day to market process makes app distribution fast and easy Join now and get one step closer to millions of Verizon customers http://p.sf.net/sfu/verizon-dev2dev _______________________________________________ GDAlgorithms-list mailing list GDAlgorithms-list@... https://lists.sourceforge.net/lists/listinfo/gdalgorithms-list Archives: http://sourceforge.net/mailarchive/forum.php?forum_name=gdalgorithms-list ```