gdalgorithms-list

Re: [Algorithms] Ideas for an AI scheme

[Jon W. <jw...@gm...>]

An alternative form of structured data is JSON. Especially if you use Flex
or SpiderMonkey or V8 for scripting... (which is a real alternative these
days!)
The benefit is similar to Lua, except with some of the JavaScript
implementations, you get a GUI system free with adoption! (thinking of
WebKit or the Mozilla stuff here)

Sincerely,

jw


--
Americans might object: there is no way we would sacrifice our living
standards for the benefit of people in the rest of the world. Nevertheless,
whether we get there willingly or not, we shall soon have lower consumption
rates, because our present rates are unsustainable.



On Tue, Dec 15, 2009 at 4:28 PM, <der...@he...> wrote:

> I've been playing around with Lua for AI HFSM and state implementations and
> I'd also suggest it as a good match for the OP's case.
>
> A code base I worked with a lot recently used Ruby to generate CPP files
> and data structures offline and that could have been used very elegantly to
> build AI. The only thing I'm unsure of there is whether Ruby is a useful
> runtime option. At least with Lua you know that it can and has been
> significantly used at runtime on some not particularly powerful platforms.
>
> On the topic raised, the scheme the OP is proposing to implement sounds
> like a solid approach to me.
>
> Cheers
> Derek
>
> Sent via BlackBerry® from Vodafone
>
> -----Original Message-----
> From: "lei...@co..." <lei...@co...>
> Date: Tue, 15 Dec 2009 17:02:04
> To: Game Development Algorithms<gda...@li...>
> Subject: Re: [Algorithms] Ideas for an AI scheme
>
> I actually dumped all my xml except for exporting assets from XSI.  I
> switched to lua.  Even if you have a tool to edit the files you still
> have to write code for DOM and/or SAX parsing.  I found I could just get
> more done much faster with lua.
>
> Leigh
>
> Nicholas "Indy" Ray wrote:
> > The largest problem I see is that XML (or really any text based
> > format) is terrible for design and editing of any complicated FSM, I
> > think a FSM is one of the instances where a graphical editing tool
> > actually makes sense.
> >
> > Indy
> >
> > On Tue, Dec 15, 2009 at 11:35 AM, Stuart Golodetz
> > <gda...@gx...> wrote:
> >
> >> Hi,
> >>
> >> I've been having a think about how to approach the AI for my game and
> >> was wondering if I could have some thoughts on the scheme I'm pondering
> >> before I sit down and implement it please? I'd like to make sure I'm not
> >> over-engineering it (it's not something I've tried before) :)
> >>
> >> What I'm thinking of is a hybrid hierarchical FSM / behaviour tree
> >> scheme. The hierarchical FSM structure would be defined in XML, and each
> >> state/transition could be defined either to reference a state/transition
> >> coded in C++ or a script. A state would yield a behaviour when executed
> >> (possibly a composite behaviour, which is where the behaviour trees come
> >> in). The behaviour could either be one defined in C++ or a behaviour
> >> tree defined in XML which has C++ behaviours as its nodes. A behaviour
> >> should ultimately yield object commands, such as "accelerate in
> >> direction d", or "fire weapon", etc. Steering-related behaviours (such
> >> as going to a particular position) could delegate to a steering
> pipeline.
> >>
> >> Does this make sense as a scheme? I realise there's a lot to code there,
> >> which is why I'm asking beforehand - but is it a sensible way to go?
> >> Also, does anyone have any alternative suggestions please?
> >>
> >> Cheers,
> >> Stuart
> >>
> >>
> ------------------------------------------------------------------------------
> >> 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
> >> GDA...@li...
> >> 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
> > GDA...@li...
> > 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
> GDA...@li...
> 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
> GDA...@li...
> https://lists.sourceforge.net/lists/listinfo/gdalgorithms-list
> Archives:
> http://sourceforge.net/mailarchive/forum.php?forum_name=gdalgorithms-list
>

Re: [Algorithms] Ideas for an AI scheme

[<der...@he...>]

I've been playing around with Lua for AI HFSM and state implementations and I'd also suggest it as a good match for the OP's case. 

A code base I worked with a lot recently used Ruby to generate CPP files and data structures offline and that could have been used very elegantly to build AI. The only thing I'm unsure of there is whether Ruby is a useful runtime option. At least with Lua you know that it can and has been significantly used at runtime on some not particularly powerful platforms.

On the topic raised, the scheme the OP is proposing to implement sounds like a solid approach to me.

Cheers
Derek

Sent via BlackBerry® from Vodafone

-----Original Message-----
From: "lei...@co..." <lei...@co...>
Date: Tue, 15 Dec 2009 17:02:04 
To: Game Development Algorithms<gda...@li...>
Subject: Re: [Algorithms] Ideas for an AI scheme

I actually dumped all my xml except for exporting assets from XSI.  I 
switched to lua.  Even if you have a tool to edit the files you still 
have to write code for DOM and/or SAX parsing.  I found I could just get 
more done much faster with lua.

Leigh

Nicholas "Indy" Ray wrote:
> The largest problem I see is that XML (or really any text based
> format) is terrible for design and editing of any complicated FSM, I
> think a FSM is one of the instances where a graphical editing tool
> actually makes sense.
>
> Indy
>
> On Tue, Dec 15, 2009 at 11:35 AM, Stuart Golodetz
> <gda...@gx...> wrote:
>   
>> Hi,
>>
>> I've been having a think about how to approach the AI for my game and
>> was wondering if I could have some thoughts on the scheme I'm pondering
>> before I sit down and implement it please? I'd like to make sure I'm not
>> over-engineering it (it's not something I've tried before) :)
>>
>> What I'm thinking of is a hybrid hierarchical FSM / behaviour tree
>> scheme. The hierarchical FSM structure would be defined in XML, and each
>> state/transition could be defined either to reference a state/transition
>> coded in C++ or a script. A state would yield a behaviour when executed
>> (possibly a composite behaviour, which is where the behaviour trees come
>> in). The behaviour could either be one defined in C++ or a behaviour
>> tree defined in XML which has C++ behaviours as its nodes. A behaviour
>> should ultimately yield object commands, such as "accelerate in
>> direction d", or "fire weapon", etc. Steering-related behaviours (such
>> as going to a particular position) could delegate to a steering pipeline.
>>
>> Does this make sense as a scheme? I realise there's a lot to code there,
>> which is why I'm asking beforehand - but is it a sensible way to go?
>> Also, does anyone have any alternative suggestions please?
>>
>> Cheers,
>> Stuart
>>
>> ------------------------------------------------------------------------------
>> 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
>> GDA...@li...
>> 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
> GDA...@li...
> 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
GDA...@li...
https://lists.sourceforge.net/lists/listinfo/gdalgorithms-list
Archives:
http://sourceforge.net/mailarchive/forum.php?forum_name=gdalgorithms-list

Re: [Algorithms] Ideas for an AI scheme

[<lei...@co...>]

I actually dumped all my xml except for exporting assets from XSI.  I 
switched to lua.  Even if you have a tool to edit the files you still 
have to write code for DOM and/or SAX parsing.  I found I could just get 
more done much faster with lua.

Leigh

Nicholas "Indy" Ray wrote:
> The largest problem I see is that XML (or really any text based
> format) is terrible for design and editing of any complicated FSM, I
> think a FSM is one of the instances where a graphical editing tool
> actually makes sense.
>
> Indy
>
> On Tue, Dec 15, 2009 at 11:35 AM, Stuart Golodetz
> <gda...@gx...> wrote:
>   
>> Hi,
>>
>> I've been having a think about how to approach the AI for my game and
>> was wondering if I could have some thoughts on the scheme I'm pondering
>> before I sit down and implement it please? I'd like to make sure I'm not
>> over-engineering it (it's not something I've tried before) :)
>>
>> What I'm thinking of is a hybrid hierarchical FSM / behaviour tree
>> scheme. The hierarchical FSM structure would be defined in XML, and each
>> state/transition could be defined either to reference a state/transition
>> coded in C++ or a script. A state would yield a behaviour when executed
>> (possibly a composite behaviour, which is where the behaviour trees come
>> in). The behaviour could either be one defined in C++ or a behaviour
>> tree defined in XML which has C++ behaviours as its nodes. A behaviour
>> should ultimately yield object commands, such as "accelerate in
>> direction d", or "fire weapon", etc. Steering-related behaviours (such
>> as going to a particular position) could delegate to a steering pipeline.
>>
>> Does this make sense as a scheme? I realise there's a lot to code there,
>> which is why I'm asking beforehand - but is it a sensible way to go?
>> Also, does anyone have any alternative suggestions please?
>>
>> Cheers,
>> Stuart
>>
>> ------------------------------------------------------------------------------
>> 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
>> GDA...@li...
>> 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
> GDA...@li...
> https://lists.sourceforge.net/lists/listinfo/gdalgorithms-list
> Archives:
> http://sourceforge.net/mailarchive/forum.php?forum_name=gdalgorithms-list
>
>   

Re: [Algorithms] Ideas for an AI scheme

[Stuart G. <gda...@gx...>]

I think my FSM's definitely going to be nearer to 10 states than 100. 
All the same, it would be nice to write a GUI tool at a later stage - 
sounds like an interesting project :) I guess integrating the scripting 
might not be such a bad idea either.

Nicholas "Indy" Ray wrote:
> It also depends on the scale of the FSM, I've been able to hand manage
> a FSM of about 10 different states before without a too large problem,
> which may be closer to the count in a hobby game then the FSM we used
> in the last game I worked on, which I think shipped with with over 100
> states, and countless transitions.
>
> Indy
>
> On Tue, Dec 15, 2009 at 2:09 PM, Stuart Golodetz
> <gda...@gx...> wrote:
>   
>> I had been planning to write the XML files by hand (it's a hobby game, so
>> the only game designer is me) - but judging by Indy's response it looks like
>> I should think about writing a tool.
>>
>> I'm hoping to write the code myself for this game rather than use middleware
>> because I want to understand how it all fits together (part of the reason
>> I'm writing the game is to make sure I've seen how to write as many
>> different subsystems as possible, because I want to understand what everyone
>> else is doing ultimately) - but I'd be interested to see how it's done
>> properly nonetheless. I'll take a look :)
>>
>> Cheers,
>> Stuart
>>
>> Jon Watte wrote:
>>
>> Will you have tools to generate the XML, or will game designers code the XML
>> by hand?
>> Have you looked at existing middleware packages with state machine set-ups,
>> like AI.Implant, SimBionics, xaitment etc? (I don't think Kynapse is that
>> high leve, but I could be wrong)
>> Sincerely,
>> jw
>>
>> --
>> Americans might object: there is no way we would sacrifice our living
>> standards for the benefit of people in the rest of the world. Nevertheless,
>> whether we get there willingly or not, we shall soon have lower consumption
>> rates, because our present rates are unsustainable.
>>
>>
>>
>> On Tue, Dec 15, 2009 at 11:35 AM, Stuart Golodetz
>> <gda...@gx...> wrote:
>>     
>>> Hi,
>>>
>>> I've been having a think about how to approach the AI for my game and
>>> was wondering if I could have some thoughts on the scheme I'm pondering
>>> before I sit down and implement it please? I'd like to make sure I'm not
>>> over-engineering it (it's not something I've tried before) :)
>>>
>>> What I'm thinking of is a hybrid hierarchical FSM / behaviour tree
>>> scheme. The hierarchical FSM structure would be defined in XML, and each
>>> state/transition could be defined either to reference a state/transition
>>> coded in C++ or a script. A state would yield a behaviour when executed
>>> (possibly a composite behaviour, which is where the behaviour trees come
>>> in). The behaviour could either be one defined in C++ or a behaviour
>>> tree defined in XML which has C++ behaviours as its nodes. A behaviour
>>> should ultimately yield object commands, such as "accelerate in
>>> direction d", or "fire weapon", etc. Steering-related behaviours (such
>>> as going to a particular position) could delegate to a steering pipeline.
>>>
>>> Does this make sense as a scheme? I realise there's a lot to code there,
>>> which is why I'm asking beforehand - but is it a sensible way to go?
>>> Also, does anyone have any alternative suggestions please?
>>>
>>> Cheers,
>>> Stuart
>>>
>>>
>>> ------------------------------------------------------------------------------
>>> 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
>>> GDA...@li...
>>> 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
>> GDA...@li...
>> 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
>> GDA...@li...
>> 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
> GDA...@li...
> https://lists.sourceforge.net/lists/listinfo/gdalgorithms-list
> Archives:
> http://sourceforge.net/mailarchive/forum.php?forum_name=gdalgorithms-list

Re: [Algorithms] Ideas for an AI scheme

[Nicholas \Indy\ R. <ar...@gm...>]

It also depends on the scale of the FSM, I've been able to hand manage
a FSM of about 10 different states before without a too large problem,
which may be closer to the count in a hobby game then the FSM we used
in the last game I worked on, which I think shipped with with over 100
states, and countless transitions.

Indy

On Tue, Dec 15, 2009 at 2:09 PM, Stuart Golodetz
<gda...@gx...> wrote:
> I had been planning to write the XML files by hand (it's a hobby game, so
> the only game designer is me) - but judging by Indy's response it looks like
> I should think about writing a tool.
>
> I'm hoping to write the code myself for this game rather than use middleware
> because I want to understand how it all fits together (part of the reason
> I'm writing the game is to make sure I've seen how to write as many
> different subsystems as possible, because I want to understand what everyone
> else is doing ultimately) - but I'd be interested to see how it's done
> properly nonetheless. I'll take a look :)
>
> Cheers,
> Stuart
>
> Jon Watte wrote:
>
> Will you have tools to generate the XML, or will game designers code the XML
> by hand?
> Have you looked at existing middleware packages with state machine set-ups,
> like AI.Implant, SimBionics, xaitment etc? (I don't think Kynapse is that
> high leve, but I could be wrong)
> Sincerely,
> jw
>
> --
> Americans might object: there is no way we would sacrifice our living
> standards for the benefit of people in the rest of the world. Nevertheless,
> whether we get there willingly or not, we shall soon have lower consumption
> rates, because our present rates are unsustainable.
>
>
>
> On Tue, Dec 15, 2009 at 11:35 AM, Stuart Golodetz
> <gda...@gx...> wrote:
>>
>> Hi,
>>
>> I've been having a think about how to approach the AI for my game and
>> was wondering if I could have some thoughts on the scheme I'm pondering
>> before I sit down and implement it please? I'd like to make sure I'm not
>> over-engineering it (it's not something I've tried before) :)
>>
>> What I'm thinking of is a hybrid hierarchical FSM / behaviour tree
>> scheme. The hierarchical FSM structure would be defined in XML, and each
>> state/transition could be defined either to reference a state/transition
>> coded in C++ or a script. A state would yield a behaviour when executed
>> (possibly a composite behaviour, which is where the behaviour trees come
>> in). The behaviour could either be one defined in C++ or a behaviour
>> tree defined in XML which has C++ behaviours as its nodes. A behaviour
>> should ultimately yield object commands, such as "accelerate in
>> direction d", or "fire weapon", etc. Steering-related behaviours (such
>> as going to a particular position) could delegate to a steering pipeline.
>>
>> Does this make sense as a scheme? I realise there's a lot to code there,
>> which is why I'm asking beforehand - but is it a sensible way to go?
>> Also, does anyone have any alternative suggestions please?
>>
>> Cheers,
>> Stuart
>>
>>
>> ------------------------------------------------------------------------------
>> 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
>> GDA...@li...
>> 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
> GDA...@li...
> 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
> GDA...@li...
> https://lists.sourceforge.net/lists/listinfo/gdalgorithms-list
> Archives:
> http://sourceforge.net/mailarchive/forum.php?forum_name=gdalgorithms-list
>

Re: [Algorithms] Ideas for an AI scheme

[Stuart G. <gda...@gx...>]

I had been planning to write the XML files by hand (it's a hobby game, 
so the only game designer is me) - but judging by Indy's response it 
looks like I should think about writing a tool.

I'm hoping to write the code myself for this game rather than use 
middleware because I want to understand how it all fits together (part 
of the reason I'm writing the game is to make sure I've seen how to 
write as many different subsystems as possible, because I want to 
understand what everyone else is doing ultimately) - but I'd be 
interested to see how it's done properly nonetheless. I'll take a look :)

Cheers,
Stuart

Jon Watte wrote:
> Will you have tools to generate the XML, or will game designers code 
> the XML by hand?
> Have you looked at existing middleware packages with state machine 
> set-ups, like AI.Implant, SimBionics, xaitment etc? (I don't think 
> Kynapse is that high leve, but I could be wrong)
>
> Sincerely,
>
> jw
>
> --
> Americans might object: there is no way we would sacrifice our living 
> standards for the benefit of people in the rest of the world. 
> Nevertheless, whether we get there willingly or not, we shall soon 
> have lower consumption rates, because our present rates are 
> unsustainable.
>
>
>
> On Tue, Dec 15, 2009 at 11:35 AM, Stuart Golodetz 
> <gda...@gx... <mailto:gda...@gx...>> wrote:
>
>     Hi,
>
>     I've been having a think about how to approach the AI for my game and
>     was wondering if I could have some thoughts on the scheme I'm
>     pondering
>     before I sit down and implement it please? I'd like to make sure
>     I'm not
>     over-engineering it (it's not something I've tried before) :)
>
>     What I'm thinking of is a hybrid hierarchical FSM / behaviour tree
>     scheme. The hierarchical FSM structure would be defined in XML,
>     and each
>     state/transition could be defined either to reference a
>     state/transition
>     coded in C++ or a script. A state would yield a behaviour when
>     executed
>     (possibly a composite behaviour, which is where the behaviour
>     trees come
>     in). The behaviour could either be one defined in C++ or a behaviour
>     tree defined in XML which has C++ behaviours as its nodes. A behaviour
>     should ultimately yield object commands, such as "accelerate in
>     direction d", or "fire weapon", etc. Steering-related behaviours (such
>     as going to a particular position) could delegate to a steering
>     pipeline.
>
>     Does this make sense as a scheme? I realise there's a lot to code
>     there,
>     which is why I'm asking beforehand - but is it a sensible way to go?
>     Also, does anyone have any alternative suggestions please?
>
>     Cheers,
>     Stuart
>
>     ------------------------------------------------------------------------------
>     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
>     GDA...@li...
>     <mailto:GDA...@li...>
>     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
> GDA...@li...
> https://lists.sourceforge.net/lists/listinfo/gdalgorithms-list
> Archives:
> http://sourceforge.net/mailarchive/forum.php?forum_name=gdalgorithms-list

Re: [Algorithms] Ideas for an AI scheme

[Nicholas \Indy\ R. <ar...@gm...>]

The largest problem I see is that XML (or really any text based
format) is terrible for design and editing of any complicated FSM, I
think a FSM is one of the instances where a graphical editing tool
actually makes sense.

Indy

On Tue, Dec 15, 2009 at 11:35 AM, Stuart Golodetz
<gda...@gx...> wrote:
> Hi,
>
> I've been having a think about how to approach the AI for my game and
> was wondering if I could have some thoughts on the scheme I'm pondering
> before I sit down and implement it please? I'd like to make sure I'm not
> over-engineering it (it's not something I've tried before) :)
>
> What I'm thinking of is a hybrid hierarchical FSM / behaviour tree
> scheme. The hierarchical FSM structure would be defined in XML, and each
> state/transition could be defined either to reference a state/transition
> coded in C++ or a script. A state would yield a behaviour when executed
> (possibly a composite behaviour, which is where the behaviour trees come
> in). The behaviour could either be one defined in C++ or a behaviour
> tree defined in XML which has C++ behaviours as its nodes. A behaviour
> should ultimately yield object commands, such as "accelerate in
> direction d", or "fire weapon", etc. Steering-related behaviours (such
> as going to a particular position) could delegate to a steering pipeline.
>
> Does this make sense as a scheme? I realise there's a lot to code there,
> which is why I'm asking beforehand - but is it a sensible way to go?
> Also, does anyone have any alternative suggestions please?
>
> Cheers,
> Stuart
>
> ------------------------------------------------------------------------------
> 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
> GDA...@li...
> https://lists.sourceforge.net/lists/listinfo/gdalgorithms-list
> Archives:
> http://sourceforge.net/mailarchive/forum.php?forum_name=gdalgorithms-list
>

Re: [Algorithms] Ideas for an AI scheme

[Jon W. <jw...@gm...>]

Will you have tools to generate the XML, or will game designers code the XML
by hand?
Have you looked at existing middleware packages with state machine set-ups,
like AI.Implant, SimBionics, xaitment etc? (I don't think Kynapse is that
high leve, but I could be wrong)

Sincerely,

jw

--
Americans might object: there is no way we would sacrifice our living
standards for the benefit of people in the rest of the world. Nevertheless,
whether we get there willingly or not, we shall soon have lower consumption
rates, because our present rates are unsustainable.



On Tue, Dec 15, 2009 at 11:35 AM, Stuart Golodetz <
gda...@gx...> wrote:

> Hi,
>
> I've been having a think about how to approach the AI for my game and
> was wondering if I could have some thoughts on the scheme I'm pondering
> before I sit down and implement it please? I'd like to make sure I'm not
> over-engineering it (it's not something I've tried before) :)
>
> What I'm thinking of is a hybrid hierarchical FSM / behaviour tree
> scheme. The hierarchical FSM structure would be defined in XML, and each
> state/transition could be defined either to reference a state/transition
> coded in C++ or a script. A state would yield a behaviour when executed
> (possibly a composite behaviour, which is where the behaviour trees come
> in). The behaviour could either be one defined in C++ or a behaviour
> tree defined in XML which has C++ behaviours as its nodes. A behaviour
> should ultimately yield object commands, such as "accelerate in
> direction d", or "fire weapon", etc. Steering-related behaviours (such
> as going to a particular position) could delegate to a steering pipeline.
>
> Does this make sense as a scheme? I realise there's a lot to code there,
> which is why I'm asking beforehand - but is it a sensible way to go?
> Also, does anyone have any alternative suggestions please?
>
> Cheers,
> Stuart
>
>
> ------------------------------------------------------------------------------
> 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
> GDA...@li...
> https://lists.sourceforge.net/lists/listinfo/gdalgorithms-list
> Archives:
> http://sourceforge.net/mailarchive/forum.php?forum_name=gdalgorithms-list
>

[Algorithms] Ideas for an AI scheme

[Stuart G. <gda...@gx...>]

Hi,

I've been having a think about how to approach the AI for my game and 
was wondering if I could have some thoughts on the scheme I'm pondering 
before I sit down and implement it please? I'd like to make sure I'm not 
over-engineering it (it's not something I've tried before) :)

What I'm thinking of is a hybrid hierarchical FSM / behaviour tree 
scheme. The hierarchical FSM structure would be defined in XML, and each 
state/transition could be defined either to reference a state/transition 
coded in C++ or a script. A state would yield a behaviour when executed 
(possibly a composite behaviour, which is where the behaviour trees come 
in). The behaviour could either be one defined in C++ or a behaviour 
tree defined in XML which has C++ behaviours as its nodes. A behaviour 
should ultimately yield object commands, such as "accelerate in 
direction d", or "fire weapon", etc. Steering-related behaviours (such 
as going to a particular position) could delegate to a steering pipeline.

Does this make sense as a scheme? I realise there's a lot to code there, 
which is why I'm asking beforehand - but is it a sensible way to go? 
Also, does anyone have any alternative suggestions please?

Cheers,
Stuart

[Algorithms] GPU HDR ToneMapping

[JSeb <Js...@na...>]

Hello,

I'm investigating since quite a long time for a good hdr tone-mapping 
formula

For the time being, we're using the following:
a) a classic global operator defined by:
   LinearLDR.rgb = pow(1 - exp(-UserScale*HDR.rgb*AutoScale), UserGamma)
   SrgbLDR.rgb = LinearToSrgb(LinearLDR.rgb)  (display gamma convertion)
   With AutoScale = clamp(MiddleGray/AverageLuminance, MinScale, MaxScale)

This formula works quite well with dynamic adaptation of AverageLuminance.

b) Yet, we've some situations where dynamic range of hdr input is too 
high and tone mapping
output burns too much (for instance when getting out of a dark tunnel, 
outside locally burns)

I've a big belief that a local operator could behaves better in case (b).

I've made an old try with a self-made multi-scale gaussian blur of 
intensity
(with downsizes/upscales to reach big scales) which was triggering 
another "AutoScale" factor,
yet results were not so good.

c) I've recently implement gpu histograms first to visualize hdr input,
then i've tried a naive histogram equalization in log space which 
results is very poor.
I'm appealed by some histogram mapping like
c.1) "black & white 2" , (minIntens(<1%)=>0, maxIntens(>99%)=>1, 
midIntens(50%) controling a gamma)
   yet minIntens=>black is quite odd
c.2) smarter histogram equalization (ward histogram adjustement)
Yet, I've the feelling histogram won't really solve case (b)
(pdf: 2007 "Efficient Histogram Generation Using scattering on GPUs")

d) I've more recently implemented a approximation of Reinhard local 
operator (with box filters computed by summed area tables)
 result beging to be interesting yet, I've some artifacts, the biggest 
being banding & aliasing, I fear theses are inhere in the operator...
 and even if Alpha & Teta parameters default value works (0.05 & 8), 
others values (like 0.025 proposed by the paper) don't work so well.
 in addition very high luminance colors don't go to white & made "pure" 
saturated colors (but this defect may be tweaked)
(pdf: 2008 "Real-Time Photographic Local Tone Reproduction Using 
Summed-Area Tables" Slomp/Oliveira CGI2008)

Have you any advices or know local operators which really works for big 
hdr range images ??
Many thanks
JSeb

Re: [Algorithms] approximation to pow(n,x)?

[Nathaniel H. <na...@io...>]

Half-vector doesn't break down for very smooth surfaces, you just get a
very peaked NDF that is vanishingly small outside a very small solid angle
- so there are only reflections when H is very close to N. In the limit
you get the perfect mirror behavior where there are only reflections when
N == H (which is the same as saying V == R). In other words, H formulation
behavior converges cleanly to R formulation in the limit.

Getting "half-vector" like behavior out of an environment map (which is
inherently R-based) is possible, but more expensive than traditional
methods. There are a few approaches in the literature (note that I haven't
tried out any of these myself):

1) The paper "Antialiasing of Environment Maps" by Andreas Schilling has
an approach that could be implemented using TEXDD (if hardware supports
anisotropic filtering of cubemaps) or with manual filtering.

2) The body of work on prefiltered environment maps could be used for this
as well, though there are complex fitting procedures to follow. The
relevant papers here are "A Unified Approach to Prefiltered Environment
Maps" by Kautz et. al., "Approximation of Glossy Reflection with
Prefiltered Environment Maps" by Kautz and McCool, and (much newer)
"Efficient Reflectance and Visibility Approximations for Environment Map
Rendering" by Green et. al.

3) BRDF importance sampling approaches have also been applied to
environment maps. Colbert and Krivanek's work is most relevant here: a
SIGGRAPH sketch ("Real-Time Shading with Filtered Importance Sampling")
and a GPU Gems 3 chapter ("GPU-Based Importance Sampling").

4) The SIGGRAPH Asia 2009 paper "All-Frequency Rendering of Dynamic,
Spatially-Varying Reflectance" by Wang et. al. warps reflectance lobes
from H-space into L-space, for use with prefiltered environment maps.
Their technique can even work with a single lookup (in this case it just
shrinks the lobe rather than distorting it, but this is still better than
the naive approach which results in grossly oversized highlights in some
cases).

Naty Hoffman

> The progression Jon mentioned between a rough surface and a smooth one is
> interesting to me though. The use of the half-vector does break down for
> very smooth surfaces, it seems. It could be worth considering what that
> means exactly.
>
> I just finished a game where we used cube maps for specular lighting
> contributions from the sun & sky. Several cube images were used, each
> "pre-blurred" to a set specular power around the reflection vector.
> Half-vector was not an option I think (every pixel in the map is a light
> source). Is there a way to get this "half-vector-like" behavior out of a
> cube lookup? Feels like the answer is no...
>
> On Wed, Nov 11, 2009 at 12:31 PM, Nathaniel Hoffman <na...@io...> wrote:
>
>> Jon,
>>
>> It is inarguable that H produces much more realistic results - a simple
>> observation of light streaks on wet roads and similar scenes with a
>> comparison to renderings of the two formulations proves this without a
>> doubt.
>>
>> However, there are also good, fundamental, theoretical reasons to prefer
>> H. I seem to be explaining this poorly - I will give it another try, but
>> first, here are some pointers to other explanations:
>>
>> There is a good diagram illustrating the difference in behavior of the
>> two
>> vectors in Figure 7 of this paper:
>> http://people.csail.mit.edu/addy/research/ngan05_brdf_eval.pdf.
>>
>> There is also some discussion about it in Appendix A of this paper:
>>
>> http://graphics.stanford.edu/courses/cs448-05-winter/Schilling-1997-TechRep.pdf
>>
>> "Real-Time Rendering, 3rd edition" also has some discussion of it on
>> pages
>> 249-251. If you don't have a copy of the book, you can "look inside" at
>> Amazon:
>>
>> http://www.amazon.com/Real-Time-Rendering-Third-Tomas-Akenine-Moller/dp/1568814240
>> ,
>> click on "search inside this book", look for "half vector" (in quotes) -
>> you will get  a link to page 249.
>>
>> OK, now I'll have another go As we both agree, the reflection vector is
>> fundamental for a perfectly flat mirror. Imagine a directional or point
>> light shining on the mirror. There are only visible reflections when V
>> ==
>> R(L, N) (view vector is equal to the reflection of the light vector
>> around
>> the surface normal).
>>
>> Now how should we treat a surface which is not perfectly flat? A good
>> model (which comes to us from fields outside graphics but has been very
>> successful in graphics) is to treat such a surface as a statistical
>> collection of stochastically-oriented perfect mirrors, each one too tiny
>> to be individually visible. A useful description of such a surface for
>> purposes of rendering is a normal distribution function, or NDF, which
>> gives the statistical distribution of the microfacet normals relative to
>> the overall macroscopic normal.
>>
>> Given a light direction L and a view direction V, how bright will we
>> observe the surface to be? Let's assume for simplicity that each of
>> these
>> mirrors is 100% reflective at all angles (silver comes close to that).
>> Then it is clear that the brightness is proportional to the percentage
>> of
>> microfacets from which there are visible reflections, in other words
>> those
>> for which V == R(L, N_u) (here I use N_u for the microfacet normal to
>> distinguish from the overall surface normal N).
>>
>> It is simple to demonstrate that this is equivalent to N_u == H.
>> Therefore
>> we should "plug" H into the microfacet distribution function, which
>> yields
>> the (N dot H) formulation for isotropic surfaces.
>>
>> I can think of no similarly-principled way to derive the reflection
>> vector
>> formulation, and none has appeared in the literature.
>>
>> I hope this has convinced you that the H formulation is superior to R
>> both
>> in terms of realism and theoretical soundness.
>>
>> Thanks,
>>
>> Naty Hoffman
>>
>> > But that's equally true for the reflection vector! If all the
>> > micro-mirrors were perfectly flat, then an infinite specular power
>> > would be applied, and you'd get a perfect reflection of the lighting
>> > environment -- in fact, this is what environment mapping gives you.
>> >
>> > As the mirrors start deviating from the perfectly flat state, the
>> > specular power would decrease, and the specular reflection area would
>> > grow in size. I don't see how you can say that the half-angle
>> > formulation is more meaningful. We're still talking about reflected
>> > light. In the perfectly reflected case, clearly the reflection vector
>> > is 100% meaningful and accurate, and any other formulation would be
>> > less meaningful. I don't see how "meaningfulness" would change as
>> > smoothness goes from 100% to 99.9% or 95% or 50%.
>> >
>> > I do agree that the math gives you a different assumed microfacet
>> > distribution in the case of the reflection formulation versus the
>> > half-angle formulation. Both are approximations, of course. However,
>> > what I don't get, is why the reflection vector approximation is
>> > considered so inferior to the more expensive half-angle vector
>> > approximation. Does it have anything to do with the space integral of
>> > the reflection cone formed by the vector in question spread out by the
>> > power function? If so, how?
>> >
>> > Sincerely,
>> >
>> > jw
>> >
>> >
>> > On Sun, Nov 8, 2009 at 9:41 AM, Nathaniel Hoffman <na...@io...> wrote:
>> >
>> >> The half-angle formulation is not just more physically correct than
>> the
>> >> reflection-vector formulation, it is fundamentally more meaningful.
>> > ...
>> >> The half-vector comes from microfacet theory. Imagine that the
>> surface
>> >> is
>> >> actually a large collection of tiny flat mirrors when viewed under
>> >> magnification. Recall that a mirror only reflects light in the
>> >> reflection
>> >> direction. For given light vector L and view vector V, only mirrors
>> >> which
>> >
>> >
>> > --
>> > Americans might object: there is no way we would sacrifice our living
>> > standards for the benefit of people in the rest of the world.
>> > Nevertheless, whether we get there willingly or not, we shall soon
>> > have lower consumption rates, because our present rates are
>> > unsustainable.
>> >
>> >
>> ------------------------------------------------------------------------------
>> > Let Crystal Reports handle the reporting - Free Crystal Reports 2008
>> > 30-Day
>> > trial. Simplify your report design, integration and deployment - and
>> focus
>> > on
>> > what you do best, core application coding. Discover what's new with
>> > Crystal Reports now.  http://p.sf.net/sfu/bobj-july
>> > _______________________________________________
>> > GDAlgorithms-list mailing list
>> > GDA...@li...
>> > https://lists.sourceforge.net/lists/listinfo/gdalgorithms-list
>> > Archives:
>> >
>> http://sourceforge.net/mailarchive/forum.php?forum_name=gdalgorithms-list
>> >
>>
>>
>>
>>
>> ------------------------------------------------------------------------------
>> Let Crystal Reports handle the reporting - Free Crystal Reports 2008
>> 30-Day
>> trial. Simplify your report design, integration and deployment - and
>> focus
>> on
>> what you do best, core application coding. Discover what's new with
>> Crystal Reports now.  http://p.sf.net/sfu/bobj-july
>> _______________________________________________
>> GDAlgorithms-list mailing list
>> GDA...@li...
>> https://lists.sourceforge.net/lists/listinfo/gdalgorithms-list
>> Archives:
>> http://sourceforge.net/mailarchive/forum.php?forum_name=gdalgorithms-list
>>
>
>
>
> --
> Jeff Russell
> Engineer, 8monkey Labs
> www.8monkeylabs.com
> ------------------------------------------------------------------------------
> Let Crystal Reports handle the reporting - Free Crystal Reports 2008
> 30-Day
> trial. Simplify your report design, integration and deployment - and focus
> on
> what you do best, core application coding. Discover what's new with
> Crystal Reports now.
> http://p.sf.net/sfu/bobj-july_______________________________________________
> GDAlgorithms-list mailing list
> GDA...@li...
> https://lists.sourceforge.net/lists/listinfo/gdalgorithms-list
> Archives:
> http://sourceforge.net/mailarchive/forum.php?forum_name=gdalgorithms-list

Re: [Algorithms] approximation to pow(n,x)?

[Jeff R. <je...@8m...>]

The progression Jon mentioned between a rough surface and a smooth one is
interesting to me though. The use of the half-vector does break down for
very smooth surfaces, it seems. It could be worth considering what that
means exactly.

I just finished a game where we used cube maps for specular lighting
contributions from the sun & sky. Several cube images were used, each
"pre-blurred" to a set specular power around the reflection vector.
Half-vector was not an option I think (every pixel in the map is a light
source). Is there a way to get this "half-vector-like" behavior out of a
cube lookup? Feels like the answer is no...

On Wed, Nov 11, 2009 at 12:31 PM, Nathaniel Hoffman <na...@io...> wrote:

> Jon,
>
> It is inarguable that H produces much more realistic results - a simple
> observation of light streaks on wet roads and similar scenes with a
> comparison to renderings of the two formulations proves this without a
> doubt.
>
> However, there are also good, fundamental, theoretical reasons to prefer
> H. I seem to be explaining this poorly - I will give it another try, but
> first, here are some pointers to other explanations:
>
> There is a good diagram illustrating the difference in behavior of the two
> vectors in Figure 7 of this paper:
> http://people.csail.mit.edu/addy/research/ngan05_brdf_eval.pdf.
>
> There is also some discussion about it in Appendix A of this paper:
>
> http://graphics.stanford.edu/courses/cs448-05-winter/Schilling-1997-TechRep.pdf
>
> "Real-Time Rendering, 3rd edition" also has some discussion of it on pages
> 249-251. If you don't have a copy of the book, you can "look inside" at
> Amazon:
>
> http://www.amazon.com/Real-Time-Rendering-Third-Tomas-Akenine-Moller/dp/1568814240
> ,
> click on "search inside this book", look for "half vector" (in quotes) -
> you will get  a link to page 249.
>
> OK, now I'll have another go As we both agree, the reflection vector is
> fundamental for a perfectly flat mirror. Imagine a directional or point
> light shining on the mirror. There are only visible reflections when V ==
> R(L, N) (view vector is equal to the reflection of the light vector around
> the surface normal).
>
> Now how should we treat a surface which is not perfectly flat? A good
> model (which comes to us from fields outside graphics but has been very
> successful in graphics) is to treat such a surface as a statistical
> collection of stochastically-oriented perfect mirrors, each one too tiny
> to be individually visible. A useful description of such a surface for
> purposes of rendering is a normal distribution function, or NDF, which
> gives the statistical distribution of the microfacet normals relative to
> the overall macroscopic normal.
>
> Given a light direction L and a view direction V, how bright will we
> observe the surface to be? Let's assume for simplicity that each of these
> mirrors is 100% reflective at all angles (silver comes close to that).
> Then it is clear that the brightness is proportional to the percentage of
> microfacets from which there are visible reflections, in other words those
> for which V == R(L, N_u) (here I use N_u for the microfacet normal to
> distinguish from the overall surface normal N).
>
> It is simple to demonstrate that this is equivalent to N_u == H. Therefore
> we should "plug" H into the microfacet distribution function, which yields
> the (N dot H) formulation for isotropic surfaces.
>
> I can think of no similarly-principled way to derive the reflection vector
> formulation, and none has appeared in the literature.
>
> I hope this has convinced you that the H formulation is superior to R both
> in terms of realism and theoretical soundness.
>
> Thanks,
>
> Naty Hoffman
>
> > But that's equally true for the reflection vector! If all the
> > micro-mirrors were perfectly flat, then an infinite specular power
> > would be applied, and you'd get a perfect reflection of the lighting
> > environment -- in fact, this is what environment mapping gives you.
> >
> > As the mirrors start deviating from the perfectly flat state, the
> > specular power would decrease, and the specular reflection area would
> > grow in size. I don't see how you can say that the half-angle
> > formulation is more meaningful. We're still talking about reflected
> > light. In the perfectly reflected case, clearly the reflection vector
> > is 100% meaningful and accurate, and any other formulation would be
> > less meaningful. I don't see how "meaningfulness" would change as
> > smoothness goes from 100% to 99.9% or 95% or 50%.
> >
> > I do agree that the math gives you a different assumed microfacet
> > distribution in the case of the reflection formulation versus the
> > half-angle formulation. Both are approximations, of course. However,
> > what I don't get, is why the reflection vector approximation is
> > considered so inferior to the more expensive half-angle vector
> > approximation. Does it have anything to do with the space integral of
> > the reflection cone formed by the vector in question spread out by the
> > power function? If so, how?
> >
> > Sincerely,
> >
> > jw
> >
> >
> > On Sun, Nov 8, 2009 at 9:41 AM, Nathaniel Hoffman <na...@io...> wrote:
> >
> >> The half-angle formulation is not just more physically correct than the
> >> reflection-vector formulation, it is fundamentally more meaningful.
> > ...
> >> The half-vector comes from microfacet theory. Imagine that the surface
> >> is
> >> actually a large collection of tiny flat mirrors when viewed under
> >> magnification. Recall that a mirror only reflects light in the
> >> reflection
> >> direction. For given light vector L and view vector V, only mirrors
> >> which
> >
> >
> > --
> > Americans might object: there is no way we would sacrifice our living
> > standards for the benefit of people in the rest of the world.
> > Nevertheless, whether we get there willingly or not, we shall soon
> > have lower consumption rates, because our present rates are
> > unsustainable.
> >
> >
> ------------------------------------------------------------------------------
> > Let Crystal Reports handle the reporting - Free Crystal Reports 2008
> > 30-Day
> > trial. Simplify your report design, integration and deployment - and
> focus
> > on
> > what you do best, core application coding. Discover what's new with
> > Crystal Reports now.  http://p.sf.net/sfu/bobj-july
> > _______________________________________________
> > GDAlgorithms-list mailing list
> > GDA...@li...
> > https://lists.sourceforge.net/lists/listinfo/gdalgorithms-list
> > Archives:
> >
> http://sourceforge.net/mailarchive/forum.php?forum_name=gdalgorithms-list
> >
>
>
>
>
> ------------------------------------------------------------------------------
> Let Crystal Reports handle the reporting - Free Crystal Reports 2008 30-Day
> trial. Simplify your report design, integration and deployment - and focus
> on
> what you do best, core application coding. Discover what's new with
> Crystal Reports now.  http://p.sf.net/sfu/bobj-july
> _______________________________________________
> GDAlgorithms-list mailing list
> GDA...@li...
> https://lists.sourceforge.net/lists/listinfo/gdalgorithms-list
> Archives:
> http://sourceforge.net/mailarchive/forum.php?forum_name=gdalgorithms-list
>



-- 
Jeff Russell
Engineer, 8monkey Labs
www.8monkeylabs.com

Re: [Algorithms] approximation to pow(n,x)?

[Nathaniel H. <na...@io...>]

Jon,

It is inarguable that H produces much more realistic results - a simple
observation of light streaks on wet roads and similar scenes with a
comparison to renderings of the two formulations proves this without a
doubt.

However, there are also good, fundamental, theoretical reasons to prefer
H. I seem to be explaining this poorly - I will give it another try, but
first, here are some pointers to other explanations:

There is a good diagram illustrating the difference in behavior of the two
vectors in Figure 7 of this paper:
http://people.csail.mit.edu/addy/research/ngan05_brdf_eval.pdf.

There is also some discussion about it in Appendix A of this paper:
http://graphics.stanford.edu/courses/cs448-05-winter/Schilling-1997-TechRep.pdf

"Real-Time Rendering, 3rd edition" also has some discussion of it on pages
249-251. If you don't have a copy of the book, you can "look inside" at
Amazon:
http://www.amazon.com/Real-Time-Rendering-Third-Tomas-Akenine-Moller/dp/1568814240,
click on "search inside this book", look for "half vector" (in quotes) -
you will get  a link to page 249.

OK, now I'll have another go As we both agree, the reflection vector is
fundamental for a perfectly flat mirror. Imagine a directional or point
light shining on the mirror. There are only visible reflections when V ==
R(L, N) (view vector is equal to the reflection of the light vector around
the surface normal).

Now how should we treat a surface which is not perfectly flat? A good
model (which comes to us from fields outside graphics but has been very
successful in graphics) is to treat such a surface as a statistical
collection of stochastically-oriented perfect mirrors, each one too tiny
to be individually visible. A useful description of such a surface for
purposes of rendering is a normal distribution function, or NDF, which
gives the statistical distribution of the microfacet normals relative to
the overall macroscopic normal.

Given a light direction L and a view direction V, how bright will we
observe the surface to be? Let's assume for simplicity that each of these
mirrors is 100% reflective at all angles (silver comes close to that).
Then it is clear that the brightness is proportional to the percentage of
microfacets from which there are visible reflections, in other words those
for which V == R(L, N_u) (here I use N_u for the microfacet normal to
distinguish from the overall surface normal N).

It is simple to demonstrate that this is equivalent to N_u == H. Therefore
we should "plug" H into the microfacet distribution function, which yields
the (N dot H) formulation for isotropic surfaces.

I can think of no similarly-principled way to derive the reflection vector
formulation, and none has appeared in the literature.

I hope this has convinced you that the H formulation is superior to R both
in terms of realism and theoretical soundness.

Thanks,

Naty Hoffman

> But that's equally true for the reflection vector! If all the
> micro-mirrors were perfectly flat, then an infinite specular power
> would be applied, and you'd get a perfect reflection of the lighting
> environment -- in fact, this is what environment mapping gives you.
>
> As the mirrors start deviating from the perfectly flat state, the
> specular power would decrease, and the specular reflection area would
> grow in size. I don't see how you can say that the half-angle
> formulation is more meaningful. We're still talking about reflected
> light. In the perfectly reflected case, clearly the reflection vector
> is 100% meaningful and accurate, and any other formulation would be
> less meaningful. I don't see how "meaningfulness" would change as
> smoothness goes from 100% to 99.9% or 95% or 50%.
>
> I do agree that the math gives you a different assumed microfacet
> distribution in the case of the reflection formulation versus the
> half-angle formulation. Both are approximations, of course. However,
> what I don't get, is why the reflection vector approximation is
> considered so inferior to the more expensive half-angle vector
> approximation. Does it have anything to do with the space integral of
> the reflection cone formed by the vector in question spread out by the
> power function? If so, how?
>
> Sincerely,
>
> jw
>
>
> On Sun, Nov 8, 2009 at 9:41 AM, Nathaniel Hoffman <na...@io...> wrote:
>
>> The half-angle formulation is not just more physically correct than the
>> reflection-vector formulation, it is fundamentally more meaningful.
> ...
>> The half-vector comes from microfacet theory. Imagine that the surface
>> is
>> actually a large collection of tiny flat mirrors when viewed under
>> magnification. Recall that a mirror only reflects light in the
>> reflection
>> direction. For given light vector L and view vector V, only mirrors
>> which
>
>
> --
> Americans might object: there is no way we would sacrifice our living
> standards for the benefit of people in the rest of the world.
> Nevertheless, whether we get there willingly or not, we shall soon
> have lower consumption rates, because our present rates are
> unsustainable.
>
> ------------------------------------------------------------------------------
> Let Crystal Reports handle the reporting - Free Crystal Reports 2008
> 30-Day
> trial. Simplify your report design, integration and deployment - and focus
> on
> what you do best, core application coding. Discover what's new with
> Crystal Reports now.  http://p.sf.net/sfu/bobj-july
> _______________________________________________
> GDAlgorithms-list mailing list
> GDA...@li...
> https://lists.sourceforge.net/lists/listinfo/gdalgorithms-list
> Archives:
> http://sourceforge.net/mailarchive/forum.php?forum_name=gdalgorithms-list
>

Re: [Algorithms] More SH exponentiation questions

[Ben Y. <shu...@gm...>]

Okay. Figured out the issue. PIX saved me on this one.

So multiplying the log visibility coefficients by N amount of spheres and
fitting it to the single sphere case to derive the AB table actually does
work. And all this time I'm wondering why it didn't. Turns out that I was
also stupidly storing the post-multiplied log coefficients in the sphere
visibility lookup table instead of the original log values... Sigh.

Re: [Algorithms] More SH exponentiation questions

[Ben Y. <shu...@gm...>]

Sorry, hit enter a bit prematurely.

Regarding Figure 3, I wanted to also ask how the values for AB were derived
for multiple overlapping spheres. It's basically what I'm trying to
accomplish...



On Wed, Nov 11, 2009 at 12:04 PM, Ben Yeoh <shu...@gm...> wrote:

> Hi Peter,
>
> Thanks for chiming in!
>
> Okay, let me elaborate a bit.
>
> Basically, I'm trying to avoid doing any factorization to reduce the log
> magnitude (besides DC isolation) in the pixel shader for performance
> reasons. It still looks prohibitively expensive even with 3rd order SHs and
> John's code generator. I was hoping that the artifacts arising with just the
> OL approach with overlapping sphere occluders would be similar to what is
> shown in the bunny example in Figure 9 in the paper, which looks to me like
> fainter shadows. I think I'm willing to live with that if that's the case...
>
> So the pure OL approach (fit to a single sphere) with 1 sphere occluder in
> the scene works fine. But when I have multiple overlapping spheres though as
> in the bunny example, there's some pretty objectionable "shadow
> saturation"/ringing artifacts when those overlapping spheres are "close" to
> the receiver. In fact, it looks very different compared to the Figure 9
> example. I'm guessing that's because the OL approximation in Figure 9 was
> fit to multiple spheres (ie, 63 spheres for the bunny?), wheares I was only
> fitting to a single sphere. Am I right to assume this?
>
> Now, going along this line, I've tried a couple of things to "fit" the AB
> table to multiple sphere occluders (which didn't work) :
>
> 1. Multiply the log visibility coeffs by 2 (for 2 sphere occluders) and use
> that to find AB instead.
>
> 2. Do a triple product on the sphere visibility coeffs (ie, F * F) and use
> that to find the log and AB.
>
>
>
>
>
>
>
> On Wed, Nov 11, 2009 at 2:29 AM, Peter-Pike Sloan <
> pet...@ho...> wrote:
>
>>
>> I'm not really sure what you are talking about.  You might want to email
>> John directly, I think we just computed a bunch of pairs and then built the
>> table as a function of log magnitude (after DC isolation.)
>>
>> You could pose computing the ab texture itself as a least squares problem,
>> and include training examples that were the result of multiple spheres
>> (instead of just single spheres), but I don't think we did that...
>>
>> Are you referring to figure 3 in the paper?  It is really just showing the
>> OL pretty much just works as long as the magnitude is small enough...
>>
>> Peter-Pike Sloan
>>
>> ------------------------------
>> Date: Tue, 10 Nov 2009 16:58:04 +0800
>> From: shu...@gm...
>> To: gda...@li...
>> Subject: [Algorithms] More SH exponentiation questions
>>
>> Has anyone implemented SH exponentiation AND managed to approximate the
>> optimal linear (OL) values for 2 or more sphere occluders?
>>
>> The SH paper briefly mentioned/implied that the authors managed to fit the
>> OL approximation to multiple spheres, which still has some artifacts with
>> inaccurate/lighter occlusion, but is still preferable to the single sphere
>> approximation when dealing with multiple sphere occluders, which is common
>> in most "practical" cases.
>>
>> If anyone has some idea how the fitting to multiple spheres thing is done
>> - that'll be awesome.
>>
>>
>>
>> ------------------------------------------------------------------------------
>> Let Crystal Reports handle the reporting - Free Crystal Reports 2008
>> 30-Day
>> trial. Simplify your report design, integration and deployment - and focus
>> on
>> what you do best, core application coding. Discover what's new with
>> Crystal Reports now.  http://p.sf.net/sfu/bobj-july
>> _______________________________________________
>> GDAlgorithms-list mailing list
>> GDA...@li...
>> https://lists.sourceforge.net/lists/listinfo/gdalgorithms-list
>> Archives:
>> http://sourceforge.net/mailarchive/forum.php?forum_name=gdalgorithms-list
>>
>
>

Re: [Algorithms] approximation to pow(n,x)?

[Jon W. <jw...@gm...>]

But that's equally true for the reflection vector! If all the
micro-mirrors were perfectly flat, then an infinite specular power
would be applied, and you'd get a perfect reflection of the lighting
environment -- in fact, this is what environment mapping gives you.

As the mirrors start deviating from the perfectly flat state, the
specular power would decrease, and the specular reflection area would
grow in size. I don't see how you can say that the half-angle
formulation is more meaningful. We're still talking about reflected
light. In the perfectly reflected case, clearly the reflection vector
is 100% meaningful and accurate, and any other formulation would be
less meaningful. I don't see how "meaningfulness" would change as
smoothness goes from 100% to 99.9% or 95% or 50%.

I do agree that the math gives you a different assumed microfacet
distribution in the case of the reflection formulation versus the
half-angle formulation. Both are approximations, of course. However,
what I don't get, is why the reflection vector approximation is
considered so inferior to the more expensive half-angle vector
approximation. Does it have anything to do with the space integral of
the reflection cone formed by the vector in question spread out by the
power function? If so, how?

Sincerely,

jw


On Sun, Nov 8, 2009 at 9:41 AM, Nathaniel Hoffman <na...@io...> wrote:

> The half-angle formulation is not just more physically correct than the
> reflection-vector formulation, it is fundamentally more meaningful.
...
> The half-vector comes from microfacet theory. Imagine that the surface is
> actually a large collection of tiny flat mirrors when viewed under
> magnification. Recall that a mirror only reflects light in the reflection
> direction. For given light vector L and view vector V, only mirrors which


--
Americans might object: there is no way we would sacrifice our living
standards for the benefit of people in the rest of the world.
Nevertheless, whether we get there willingly or not, we shall soon
have lower consumption rates, because our present rates are
unsustainable.

Re: [Algorithms] More SH exponentiation questions

[Ben Y. <shu...@gm...>]

Hi Peter,

Thanks for chiming in!

Okay, let me elaborate a bit.

Basically, I'm trying to avoid doing any factorization to reduce the log
magnitude (besides DC isolation) in the pixel shader for performance
reasons. It still looks prohibitively expensive even with 3rd order SHs and
John's code generator. I was hoping that the artifacts arising with just the
OL approach with overlapping sphere occluders would be similar to what is
shown in the bunny example in Figure 9 in the paper, which looks to me like
fainter shadows. I think I'm willing to live with that if that's the case...

So the pure OL approach (fit to a single sphere) with 1 sphere occluder in
the scene works fine. But when I have multiple overlapping spheres though as
in the bunny example, there's some pretty objectionable "shadow
saturation"/ringing artifacts when those overlapping spheres are "close" to
the receiver. In fact, it looks very different compared to the Figure 9
example. I'm guessing that's because the OL approximation in Figure 9 was
fit to multiple spheres (ie, 63 spheres for the bunny?), wheares I was only
fitting to a single sphere. Am I right to assume this?

Now, going along this line, I've tried a couple of things to "fit" the AB
table to multiple sphere occluders (which didn't work) :

1. Multiply the log visibility coeffs by 2 (for 2 sphere occluders) and use
that to find AB instead.

2. Do a triple product on the sphere visibility coeffs (ie, F * F) and use
that to find the log and AB.







On Wed, Nov 11, 2009 at 2:29 AM, Peter-Pike Sloan <
pet...@ho...> wrote:

>
> I'm not really sure what you are talking about.  You might want to email
> John directly, I think we just computed a bunch of pairs and then built the
> table as a function of log magnitude (after DC isolation.)
>
> You could pose computing the ab texture itself as a least squares problem,
> and include training examples that were the result of multiple spheres
> (instead of just single spheres), but I don't think we did that...
>
> Are you referring to figure 3 in the paper?  It is really just showing the
> OL pretty much just works as long as the magnitude is small enough...
>
> Peter-Pike Sloan
>
> ------------------------------
> Date: Tue, 10 Nov 2009 16:58:04 +0800
> From: shu...@gm...
> To: gda...@li...
> Subject: [Algorithms] More SH exponentiation questions
>
> Has anyone implemented SH exponentiation AND managed to approximate the
> optimal linear (OL) values for 2 or more sphere occluders?
>
> The SH paper briefly mentioned/implied that the authors managed to fit the
> OL approximation to multiple spheres, which still has some artifacts with
> inaccurate/lighter occlusion, but is still preferable to the single sphere
> approximation when dealing with multiple sphere occluders, which is common
> in most "practical" cases.
>
> If anyone has some idea how the fitting to multiple spheres thing is done -
> that'll be awesome.
>
>
>
> ------------------------------------------------------------------------------
> Let Crystal Reports handle the reporting - Free Crystal Reports 2008 30-Day
> trial. Simplify your report design, integration and deployment - and focus
> on
> what you do best, core application coding. Discover what's new with
> Crystal Reports now.  http://p.sf.net/sfu/bobj-july
> _______________________________________________
> GDAlgorithms-list mailing list
> GDA...@li...
> https://lists.sourceforge.net/lists/listinfo/gdalgorithms-list
> Archives:
> http://sourceforge.net/mailarchive/forum.php?forum_name=gdalgorithms-list
>

Re: [Algorithms] More SH exponentiation questions

[Peter-Pike S. <pet...@ho...>]

I'm not really sure what you are talking about.  You might want to email John directly, I think we just computed a bunch of pairs and then built the table as a function of log magnitude (after DC isolation.)  
You could pose computing the ab texture itself as a least squares problem, and include training examples that were the result of multiple spheres (instead of just single spheres), but I don't think we did that...
Are you referring to figure 3 in the paper?  It is really just showing the OL pretty much just works as long as the magnitude is small enough...
Peter-Pike Sloan

Date: Tue, 10 Nov 2009 16:58:04 +0800
From: shu...@gm...
To: gda...@li...
Subject: [Algorithms] More SH exponentiation questions

Has anyone implemented SH exponentiation AND managed to approximate the optimal linear (OL) values for 2 or more sphere occluders? 

The SH paper briefly mentioned/implied that the authors managed to fit the OL approximation to multiple spheres, which still has some artifacts with inaccurate/lighter occlusion, but is still preferable to the single sphere approximation when dealing with multiple sphere occluders, which is common in most "practical" cases.


If anyone has some idea how the fitting to multiple spheres thing is done - that'll be awesome.

 		 	   		  

[Algorithms] More SH exponentiation questions

[Ben Y. <shu...@gm...>]

Has anyone implemented SH exponentiation AND managed to approximate the
optimal linear (OL) values for 2 or more sphere occluders?

The SH paper briefly mentioned/implied that the authors managed to fit the
OL approximation to multiple spheres, which still has some artifacts with
inaccurate/lighter occlusion, but is still preferable to the single sphere
approximation when dealing with multiple sphere occluders, which is common
in most "practical" cases.

If anyone has some idea how the fitting to multiple spheres thing is done -
that'll be awesome.

Re: [Algorithms] Area of convex shape inside of a BSP tree

[Jason H. <jh...@st...>]

Since you're not looking for precision, there's a hacky solution that 
might send you off in a fruitful direction (or not).  You could do a 
little preprocessing to pack a bunch of spheres inside your level 
geometry that are equal-sized.  These would represent your volume.  When 
you split the geometry by a plane, you simply dot-product each sphere to 
see if it's on one side or the other.  You can trade off performance vs. 
precision by having more or less spheres. 

The volume of spheres won't be correct, but they're representative of an 
equal portion.  You could figure out the actual volume of the geometry 
offline, then assign each sphere one share of that amount...  The point 
of using spheres is there are (many) algorithms to pack them in a space, 
and the dot product to determine side of a splitting plane is cheap.

Maybe a bad idea, but it's relatively runtime friendly.  :-)

JH

Jason Hughes
President
Steel Penny Games, Inc.
Austin, TX



Juan Linietsky wrote:
> Well, i was wondering about doing it realtime and without having to
> create polygons..
> but it doesn't sound so simple after all. I guess the fastest way to
> do it "correctly" is to traverse the BSP "save" the planes
> intersecting the polygon along the way. In the end i guess i'd end up
> with a set of convex objects delimited by the planes, but computing
> area from that seems a little expensive to me.
>
> Since what i need to know does not need to be super precise, I was
> thinking doing  something similar to a montecarlo method should be
> best, as in.. throwing N random points inside the convex volume i want
> to test against the BSP tree, and use them to traverse the BSP. At the
> end, the number of points inside vs outside should give me an
> approximation of the area taken up by the intersection.. but i was
> wondering if there could be a better way to do something like this.
>
> Juan Linietsky
>
> On Sun, Nov 8, 2009 at 7:21 PM, Alen Ladavac <ale...@cr...> wrote:
>   
>> Juan,
>>
>> There are ways to make a boolean intersection of two objects
>> represented by BSP trees and get the resulting volume in form of a
>> polygon-soup. It is not trivial, but it not overly complex either. And
>> from the resulting polygon-soup you can determine volume or area of
>> the intersection. Is that what you need?
>>
>> Cheers,
>> Alen
>>
>>
>> Sunday, November 8, 2009, 5:41:57 PM, you wrote:
>>
>>     
>>> Hi! Here's another question about an algorithm i've been wondering
>>> since a few days, to implement an idea i had about interior
>>> rendering..
>>>       
>>> Basically, take a BSP tree of a closed, concave shape that encloses an
>>> area, and also a convex object (that provides a support function), how
>>> could the area of the convex object that is inside the concave object
>>> represented by a BSP tree be calculated?
>>> Finding if they intersect is easy, but it seems to me that calculating
>>> how much of the convex object is inside the BSP tree area is not so
>>> simple.. but maybe i'm missing something?
>>> Also maybe there is another structure that best fits this problem than
>>> a BSP tree?
>>>       
>>> Cheers
>>>       
>>> Juan Linietsky
>>>       
>>> ------------------------------------------------------------------------------
>>> Let Crystal Reports handle the reporting - Free Crystal Reports 2008 30-Day
>>> trial. Simplify your report design, integration and deployment - and focus on
>>> what you do best, core application coding. Discover what's new with
>>> Crystal Reports now.  http://p.sf.net/sfu/bobj-july
>>> _______________________________________________
>>> GDAlgorithms-list mailing list
>>> GDA...@li...
>>> https://lists.sourceforge.net/lists/listinfo/gdalgorithms-list
>>> Archives:
>>> http://sourceforge.net/mailarchive/forum.php?forum_name=gdalgorithms-list
>>>       
>> --
>> Best regards,
>>  Alen                            mailto:ale...@cr...
>>
>>
>>     
>
> ------------------------------------------------------------------------------
> Let Crystal Reports handle the reporting - Free Crystal Reports 2008 30-Day 
> trial. Simplify your report design, integration and deployment - and focus on 
> what you do best, core application coding. Discover what's new with
> Crystal Reports now.  http://p.sf.net/sfu/bobj-july
> _______________________________________________
> GDAlgorithms-list mailing list
> GDA...@li...
> https://lists.sourceforge.net/lists/listinfo/gdalgorithms-list
> Archives:
> http://sourceforge.net/mailarchive/forum.php?forum_name=gdalgorithms-list
>
>   

Re: [Algorithms] Area of convex shape inside of a BSP tree

[Jason H. <jh...@st...>]

Since you're not looking for precision, there's a hacky solution that 
might send you off in a fruitful direction (or not).  You could do a 
little preprocessing to pack a bunch of spheres inside your level 
geometry that are equal-sized.  These would represent your volume.  When 
you split the geometry by a plane, you simply dot-product each sphere to 
see if it's on one side or the other.  You can trade off performance vs. 
precision by having more or less spheres. 

The volume of spheres won't be correct, but they're representative of an 
equal portion.  You could figure out the actual volume of the geometry 
offline, then assign each sphere one share of that amount...  The point 
of using spheres is there are (many) algorithms to pack them in a space, 
and the dot product to determine side of a splitting plane is cheap.

Maybe a bad idea, but it's relatively runtime friendly.  :-)

JH

Jason Hughes
President
Steel Penny Games, Inc.
Austin, TX



Juan Linietsky wrote:
> Well, i was wondering about doing it realtime and without having to
> create polygons..
> but it doesn't sound so simple after all. I guess the fastest way to
> do it "correctly" is to traverse the BSP "save" the planes
> intersecting the polygon along the way. In the end i guess i'd end up
> with a set of convex objects delimited by the planes, but computing
> area from that seems a little expensive to me.
>
> Since what i need to know does not need to be super precise, I was
> thinking doing  something similar to a montecarlo method should be
> best, as in.. throwing N random points inside the convex volume i want
> to test against the BSP tree, and use them to traverse the BSP. At the
> end, the number of points inside vs outside should give me an
> approximation of the area taken up by the intersection.. but i was
> wondering if there could be a better way to do something like this.
>
> Juan Linietsky
>
> On Sun, Nov 8, 2009 at 7:21 PM, Alen Ladavac <ale...@cr...> wrote:
>   
>> Juan,
>>
>> There are ways to make a boolean intersection of two objects
>> represented by BSP trees and get the resulting volume in form of a
>> polygon-soup. It is not trivial, but it not overly complex either. And
>> from the resulting polygon-soup you can determine volume or area of
>> the intersection. Is that what you need?
>>
>> Cheers,
>> Alen
>>
>>
>> Sunday, November 8, 2009, 5:41:57 PM, you wrote:
>>
>>     
>>> Hi! Here's another question about an algorithm i've been wondering
>>> since a few days, to implement an idea i had about interior
>>> rendering..
>>>       
>>> Basically, take a BSP tree of a closed, concave shape that encloses an
>>> area, and also a convex object (that provides a support function), how
>>> could the area of the convex object that is inside the concave object
>>> represented by a BSP tree be calculated?
>>> Finding if they intersect is easy, but it seems to me that calculating
>>> how much of the convex object is inside the BSP tree area is not so
>>> simple.. but maybe i'm missing something?
>>> Also maybe there is another structure that best fits this problem than
>>> a BSP tree?
>>>       
>>> Cheers
>>>       
>>> Juan Linietsky
>>>       
>>> ------------------------------------------------------------------------------
>>> Let Crystal Reports handle the reporting - Free Crystal Reports 2008 30-Day
>>> trial. Simplify your report design, integration and deployment - and focus on
>>> what you do best, core application coding. Discover what's new with
>>> Crystal Reports now.  http://p.sf.net/sfu/bobj-july
>>> _______________________________________________
>>> GDAlgorithms-list mailing list
>>> GDA...@li...
>>> https://lists.sourceforge.net/lists/listinfo/gdalgorithms-list
>>> Archives:
>>> http://sourceforge.net/mailarchive/forum.php?forum_name=gdalgorithms-list
>>>       
>>
>> --
>> Best regards,
>>  Alen                            mailto:ale...@cr...
>>
>>
>>     
>
> ------------------------------------------------------------------------------
> Let Crystal Reports handle the reporting - Free Crystal Reports 2008 30-Day 
> trial. Simplify your report design, integration and deployment - and focus on 
> what you do best, core application coding. Discover what's new with
> Crystal Reports now.  http://p.sf.net/sfu/bobj-july
> _______________________________________________
> GDAlgorithms-list mailing list
> GDA...@li...
> https://lists.sourceforge.net/lists/listinfo/gdalgorithms-list
> Archives:
> http://sourceforge.net/mailarchive/forum.php?forum_name=gdalgorithms-list
>
>   

Re: [Algorithms] Area of convex shape inside of a BSP tree

[Juan L. <re...@gm...>]

Well, i was wondering about doing it realtime and without having to
create polygons..
but it doesn't sound so simple after all. I guess the fastest way to
do it "correctly" is to traverse the BSP "save" the planes
intersecting the polygon along the way. In the end i guess i'd end up
with a set of convex objects delimited by the planes, but computing
area from that seems a little expensive to me.

Since what i need to know does not need to be super precise, I was
thinking doing  something similar to a montecarlo method should be
best, as in.. throwing N random points inside the convex volume i want
to test against the BSP tree, and use them to traverse the BSP. At the
end, the number of points inside vs outside should give me an
approximation of the area taken up by the intersection.. but i was
wondering if there could be a better way to do something like this.

Juan Linietsky

On Sun, Nov 8, 2009 at 7:21 PM, Alen Ladavac <ale...@cr...> wrote:
> Juan,
>
> There are ways to make a boolean intersection of two objects
> represented by BSP trees and get the resulting volume in form of a
> polygon-soup. It is not trivial, but it not overly complex either. And
> from the resulting polygon-soup you can determine volume or area of
> the intersection. Is that what you need?
>
> Cheers,
> Alen
>
>
> Sunday, November 8, 2009, 5:41:57 PM, you wrote:
>
>> Hi! Here's another question about an algorithm i've been wondering
>> since a few days, to implement an idea i had about interior
>> rendering..
>
>> Basically, take a BSP tree of a closed, concave shape that encloses an
>> area, and also a convex object (that provides a support function), how
>> could the area of the convex object that is inside the concave object
>> represented by a BSP tree be calculated?
>> Finding if they intersect is easy, but it seems to me that calculating
>> how much of the convex object is inside the BSP tree area is not so
>> simple.. but maybe i'm missing something?
>> Also maybe there is another structure that best fits this problem than
>> a BSP tree?
>
>> Cheers
>
>> Juan Linietsky
>
>> ------------------------------------------------------------------------------
>> Let Crystal Reports handle the reporting - Free Crystal Reports 2008 30-Day
>> trial. Simplify your report design, integration and deployment - and focus on
>> what you do best, core application coding. Discover what's new with
>> Crystal Reports now.  http://p.sf.net/sfu/bobj-july
>> _______________________________________________
>> GDAlgorithms-list mailing list
>> GDA...@li...
>> https://lists.sourceforge.net/lists/listinfo/gdalgorithms-list
>> Archives:
>> http://sourceforge.net/mailarchive/forum.php?forum_name=gdalgorithms-list
>
>
>
> --
> Best regards,
>  Alen                            mailto:ale...@cr...
>
>

Re: [Algorithms] Area of convex shape inside of a BSP tree

[Alen L. <ale...@cr...>]

Juan,

There are ways to make a boolean intersection of two objects
represented by BSP trees and get the resulting volume in form of a
polygon-soup. It is not trivial, but it not overly complex either. And
from the resulting polygon-soup you can determine volume or area of
the intersection. Is that what you need?

Cheers,
Alen


Sunday, November 8, 2009, 5:41:57 PM, you wrote:

> Hi! Here's another question about an algorithm i've been wondering
> since a few days, to implement an idea i had about interior
> rendering..

> Basically, take a BSP tree of a closed, concave shape that encloses an
> area, and also a convex object (that provides a support function), how
> could the area of the convex object that is inside the concave object
> represented by a BSP tree be calculated?
> Finding if they intersect is easy, but it seems to me that calculating
> how much of the convex object is inside the BSP tree area is not so
> simple.. but maybe i'm missing something?
> Also maybe there is another structure that best fits this problem than
> a BSP tree?

> Cheers

> Juan Linietsky

> ------------------------------------------------------------------------------
> Let Crystal Reports handle the reporting - Free Crystal Reports 2008 30-Day
> trial. Simplify your report design, integration and deployment - and focus on
> what you do best, core application coding. Discover what's new with
> Crystal Reports now.  http://p.sf.net/sfu/bobj-july
> _______________________________________________
> GDAlgorithms-list mailing list
> GDA...@li...
> https://lists.sourceforge.net/lists/listinfo/gdalgorithms-list
> Archives:
> http://sourceforge.net/mailarchive/forum.php?forum_name=gdalgorithms-list



-- 
Best regards,
 Alen                            mailto:ale...@cr...

Re: [Algorithms] approximation to pow(n,x)?

[Nathaniel H. <na...@io...>]

Robin is correct in that the problem with reflection-vector highlights is
the shape (the center of the highlight will be in the same location under
both formulations), and that the problem is most noticeable at grazing
angles. However, the images he gives don't show the effect as much as a
flat surface would.

Consider the following examples of real-life highlights:

* The "golden path" formed by the setting sun on the ocean
* Vertical streaks from car highlights on wet streets

And similar cases. Half-angle highlights will give you the correct shape.
Reflection-vector highlights will always stay circular - in these cases
you will get a large circular blob instead of the narrow vertical streak
you would get in real life.

The half-angle formulation is not just more physically correct than the
reflection-vector formulation, it is fundamentally more meaningful. This
affects things other than highlight shape, for example the correct way to
compute the Fresnel factor.

The half-vector comes from microfacet theory. Imagine that the surface is
actually a large collection of tiny flat mirrors when viewed under
magnification. Recall that a mirror only reflects light in the reflection
direction. For given light vector L and view vector V, only mirrors which
happen to be angled just right to reflect L into V will matter for the
purpose of shading. All other mirrors will be reflecting L into other
directions. The intensity of the reflection is proportional to the
percentage of mirrors that are angled "just right".

To be angled "just right" to reflect L into V, the surface normal of the
mirror has to be half-way between them - in other words the microfacet
normal needs to be equal to H. The question "what percentage of mirrors
are angled just right" becomes "what percentage of mirrors have a normal
equal to H".

The way to answer this question is to define a microfacet normal
distribution function, or NDF for the surface. You can plug into this
function any example direction, and it will tell you the percentage of
microfacets with normals pointing in that direction (I'm glossing over a
few mathematical details here). NDFs are defined in the local tangent
space of the surface. In isotropic NDFs the only parameter is the
elevation angle of the microfacet normal in tangent space - in other words
the angle between N and H.

Since in most cases surface microstructure results from random processes,
the NDF is a Gaussian-ish blob. The cosine raised to a power is simply an
approximation of this blob (there should also be a normalization factor,
which I don't discuss since this email is already too long).

When you calculate (N.H)^m, you are actually evaluating the NDF for the
case of microfacet normal equal to H, or in other words calculating the
answer to the question "what percentage of microfacets are participating
in the reflection of light from L to V". When you calculate (V.R)^m, you
aren't calculating anything with a physical meaning.

Understanding this helps with things like Fresnel. The Fresnel factor for
a mirror is a function of the angle between the mirror normal and the
light vector (or reflection vector). Since all microfacets participating
in the reflection have their microfacet normal equal to H, the angle for
Fresnel can be found by computing (L dot H) or (V dot H). This is the
cosine you should plug into the Shlick Fresnel approximation, for example
((V dot N) is correct for Fresnel applied to an environment map, but not
for specular highlights).

I hope this clears up some of the confusion. (begin shameless plug)There
is also a fairly detailed explanation of this in "Real-Time Rendering, 3rd
edition"(end shameless plug).

Naty Hoffman

> The difference is in the shape of specular highlights. Where
> Phong specular highlights at grazing angles are streched out
> moon shapes, the Blinn half-angle highlights retain a more
> circular shape. Real world photos of specular surfaces at
> grazing angles more closely resemble Blinn shapes than Phong,
> plus the Blinn model has some good physical reasoning behind
> it to do with reflection from distributions of microfacets.
>
> http://img22.imageshack.us/img22/7/blinn.jpg
> http://img526.imageshack.us/img526/758/phong.jpg
>
> - Robin Green.
>
> On Wed, Nov 4, 2009 at 10:14 AM, Jeff Russell <je...@8m...>
> wrote:
>> Not to derail the conversation, but I've never really understood
>> why half vectors are preferable to an actual reflection vector,
>> either in terms of efficiency or realism. I've always just used
>> reflection, am I missing something?

[Algorithms] Area of convex shape inside of a BSP tree

[Juan L. <re...@gm...>]

Hi! Here's another question about an algorithm i've been wondering
since a few days, to implement an idea i had about interior
rendering..

Basically, take a BSP tree of a closed, concave shape that encloses an
area, and also a convex object (that provides a support function), how
could the area of the convex object that is inside the concave object
represented by a BSP tree be calculated?
Finding if they intersect is easy, but it seems to me that calculating
how much of the convex object is inside the BSP tree area is not so
simple.. but maybe i'm missing something?
Also maybe there is another structure that best fits this problem than
a BSP tree?

Cheers

Juan Linietsky